既知のチャンネル歪みとAWGN (Additive White Gaussian Noise 加法的白色ガウス雑音）を仮定したとき、最良の受信方法は最尤（ユウ）系列推定でした。　その原理は次のようです。

送信シンボル系列を有限長とする。
既知チャンネル歪を用いて、可能なすべてのシンボル系列の受信信号（レプリカ）を作る。
実際の受信信号とすべてのレプリカの自乗誤差を計算し、最小を与えたシンボル系列を判定する。

この手順は極めて単純ですが、シンボル系列が長くなると、演算量はあっという間に爆発してしまいます。　この演算量をシンボル長に比例するように工夫したのがビタビ (Viterbi) ・アルゴリズムです。　これは、Richard Bellman による ＤＰ： Dynamic Programming （動的計画法）をストレートに応用したものです。　というわけで、まず ＤＰ の例題を説明します。

下図のような５本の川が流れる地図があります。　スタートからゴールまでの最短ルートを求めなさい。

総当たり的に、ルートの距離を計算すると、ごちゃごちゃして嫌になりそうですね。　そこで、川に注目しましょう。　川には橋が掛けられていますが、橋までの最短距離を段階的に（川を段階と考えて）求めていきます。　とりあえず、橋から橋への最短ルートを地図から読み取り、それを下図のように整理してみます。

第１段階はＡ川の橋 a1, a2, a3 を渡るときですが、各橋へはスタート地点から一本の道しかないので、その距離を橋の下に赤色で書き込みます。
第２段階は、Ｂ川を渡るときです。　橋 b1 へは３本の道が来ていますが、それを経由したルートのもっとも短い道を選び、その道を太線に書き換えて、橋までの距離を橋の下に赤色で書き込みます。　計算は３回の加算で済みます。　b2 と b3 についても同じ操作を実行します。　この結果、Ｂ川の３つの橋までの最短ルートが決定しました。
第３段階はＣ川を渡るときですが、同じ操作を c1, c2, c3 について実行します。　すでに、Ｂ川の橋までの最短ルートが橋の下に赤色で書かれているので、計算はＢ川とＣ川の道の数だけ加算を実行すれば済みます。　この結果、c1, c2, c3 それぞれに至る最短ルートが決定しました。
同じ操作をゴールまで実行すると、上の図のように太線が残ります。　各橋からスタート方向へは必ず一本の太線が描かれていますから、ゴールから太線に沿ってスタート地点まで、分岐することなく遡ることができます。　これが求める最短ルートです。　結果は下図のオレンジ色のルートになりました。

上の手順をまとめると、次のことが分かります。

川に掛けられた橋への最適な道は、一つ前の川に掛けられた橋までの最短ルートと無関係に決まる。
川に掛けられた橋までの最短距離の計算量は、それぞれの橋にいたる道の総数の加算回数となる。
したがって、計算量は川の本数に比例する。

特に、１．は、「現段階の最適戦略が、過去に遡ることなしに、直前の段階の最適結果だけから決まる」ことを意味しています。　このような原理を 「最適性の原理」 と呼んでいます。　ＤＰ はこの原理を前提にしていますが、その応用は非常に広い範囲にわたっています。

 では、最尤系列推定 (MLSE: Maximum Likelihood Sequence Estimation ) の簡単な例題を、ＤＰ の手順に書き直してみましょう。　既知のチャンネル応答を とし、送信シンボル を２値（)とします。　ガウス雑音  が加算された受信信号は次のように表せます。

受信機は、レプリカ

を次々と作って、永遠に続くであろう自乗誤差

を最小にしたい。　時刻ＫをＫ番目の川と見做し、この時刻のレプリカに含まれる送信シンボルの８通りの候補 を橋と見做してください。　そうすると、各候補に至るまでの最小自乗誤差がわかっていると、次のように最適性の原理が成り立ちます。　記号の簡単のため とし、 は橋 から橋 への道と考えてください。

時刻Ｋの候補 {+1,+1,-1} からは、 時刻Ｋ＋１の候補 ｛+1,+1,+1} と {-1,+1,+1} にしか行けません。　橋から出る道も入る道も２本に限定されます。　この様子を描くと下図のようになります。　赤い点は８個の候補を表し、左から右へ遷移します。　赤い点は下から上へ、

{-1,-1,-1,}  {-1,-1,+1}  {-1,+1,-1}  {-1,+1,+1}  {+1,-1,-1}  {+1,-1,+1}  {+1,+1,-1}  {+1,+1,+1}

に対応しています。　これをトレリスグラフ (trellis は植物を支えるフレーム構造）と呼んでいます。　この場合、赤い点に入る２本の道の距離はともに等しく、次の式で与えられます。

このグラフを冒頭の最短ルート問題に照らして考え、赤い点に入る短い方のルートを選択し、他の道をどんどん捨てると、生き残った道は下図のようになります。

左端は時刻 Ｋ＝１、右端は時刻 Ｋ＝１６に相当しています。　Ｋ＝１６のすべての赤い点から過去へ（左へ）遡ると、下図の黒いルートが浮かび上がります。

黒いルートは時刻Ｋ＝１３で合流(merge)しています。　そして、合流点より過去は一本のルートになっています。　したがって、時刻ｋ＝１６でＫ＝１３以前の最短ルートが確定したことがいえます。　このシミュレーションの送信信号は

{-1, -1, -1, -1, +1, -1, -1, +1, -1, +1, +1, +1, +1, -1, +1, +1, +1, -1}

であり、正しく判定されていることが分かります。　合流を見つけて、確定したルートをどんどん延ばしていくことができるので、延々と受信が可能になります。
信号に雑音が乗っているとき、合流がなかなか更新されないことが発生します。そうすると、ルートがなかなか確定できないので、長いトレリスグラフを記憶しなければなりません。この長さをどれぐらいに設定するかが重要な設計項目となります。

注：　チャンネル応答が未知、送信シンボル系列も未知のとき、何の条件もなしに送信シンボルを推定できません。　これはブラインド問題になります。　ビタビ・アルゴリズムのブラインド版の解説はこのページにあります。