ビタビ・アルゴリズム    Viterbi algorithm

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

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

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

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

img5.gif

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

img2.gif

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

img4.gif

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

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

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

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

 

受信機は、レプリカ

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

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

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

{-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 は植物を支えるフレーム構造)と呼んでいます。 この場合、赤い点に入る2本の道の距離はともに等しく、次の式で与えられます。

img1.gif

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

img2.gif

左端は時刻 K=1、右端は時刻 K=16に相当しています。 K=16のすべての赤い点から過去へ(左へ)遡ると、下図の黒いルートが浮かび上がります。

img3.gif

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

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

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

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