ビタビアルゴリズム既知のチャンネル歪みとAWGN (Additive White Gaussian Noise 加法的白色ガウス雑音）を仮定したとき、最良の受信方法は最尤（ユウ）系列推定でした。 その原理は次のようです。 送信シンボル系列を有限長とする。 既知チャンネル歪を用いて、可能なすべてのシンボル系列の受信信号（レプリカ）を作る。 実際の受信信号とすべてのレプリカの自乗誤差を計算し、最小を与えたシンボル系列を判定する。 この手順は極めて単純ですが、シンボル系列が長くなると、演算量はあっという間に爆発してしまいます。 この演算量をシンボル長に比例するように工夫したのがビタビ (Viterbi) ・アルゴリズムです。 これは、Richard Bellman による ＤＰ： Dynamic Programming （動的計画法）をストレートに応用したものです。 というわけで、まず ＤＰ の例題を説明します。
