ビタビアルゴリズムは、あらゆる携帯電話が自らの信号を復号できるようにした

無線リンク上のデジタル通信は、アンテナが受信するビットを破損しうる雑音との戦いである。明白な解決策は誤り訂正符号を追加することだが、それを復号するには、雑音の多い受信ストリームから、実際に送信されたのはどのメッセージだったかを割り出す方法が必要になる。

ビタビの1967年のアルゴリズムはまさにそれを行った。畳み込み符号器は送信機を有限の状態集合の中を移動するよう制約し、受信機はそれらの状態のトレリスを保持する。各ステップで各状態への最も安価な経路だけを保持するため、最後には各ビットを独立に選ぶのではなく、単一の最も確からしいメッセージを見つけている。

実用的で短い拘束長の符号を扱いやすくすることで、このアルゴリズムは前方誤り訂正を実際の無線機に配備できるほど安価にした。それは漠然とした「メッセージは何だったのか」を、明快な動的計画法の探索に変え、現在では音声やデータを背景雑音から分離するために使われている。

最も確からしい隠れた状態系列を選び出す

各状態への単一の最も安価な経路だけを保持することで、探索に要する時間はメッセージ長に対して線形になる。

ビットごとの当て推量なしに、雑音の多いデータから最尤系列を復元する。

畳み込み符号は、このように復号されて初めて実際の誤り訂正能力を得る。

信号が雑音が多すぎて直接読めないときは、それが由来しうる単一の最も確からしい系列を再構成せよ。加えた構造によって、その探索はほとんど労力を要さなくなる。

ビタビアルゴリズムは世界中の大多数の携帯電話で、また衛星受信機、磁気記録、音声認識、DNA解析で使われている。ビタビは後に1985年にクアルコムを共同創業し、このアルゴリズムはCDMAとデジタル携帯電話を実用化する一助となった。