ビタビ符号（Viterbi Algorithm）は、通信工学やデジタル信号処理で使用されるアルゴリズムの一つで、主に畳み込み符号の復号に利用されます。通信路で受信した信号には誤りが含まれる場合がありますが、ビタビ符号を使うことで、送信された符号語を高い精度で復元できます。
畳み込み符号とは？
• 畳み込み符号は、デジタル信号を送信する際に誤り訂正のために使用される符号化方式です。
• 入力ビット列を一定の長さのビット列（符号語）に変換し、送信します。
• 畳み込み符号では、入力ビット列に現在の入力だけでなく、過去の入力状態も反映されるため、連続したビットが符号化に影響を与えます。
ビタビアルゴリズムの基本概念
ビタビアルゴリズムは、受信された符号語から元の入力ビット列を推定するための動的計画法の一種です。
主な特徴
• 最尤復号（Maximum Likelihood Decoding）：
ビタビアルゴリズムは、受信した符号語が送信された可能性が最も高いビット列を選びます。
• 状態遷移図：
畳み込み符号は状態遷移図（トレリス図）で表されます。この図に基づき、ビタビアルゴリズムは最適な経路を探索します。
• コスト計算：
各遷移にコスト（誤差）が割り当てられ、受信した符号語と符号器出力との一致度を基に最小コストの経路を選択します。