畳み込み符号化Visualizer

ここでは8bitの情報（0から255の整数）を符号化効率0.5（データ量は2倍）で送信する様子を可視化しています。 なお、前後に0埋めをするため、実際には2倍以上の長さになっています。具体的には2倍よりも4bit長くなります。

送信側

一番上の行にある0や1と書かれた8個の正方形が送信したい元データです。クリックする事で、送信内容を変更できます。 なお、四角で囲われていない0は「0埋め」されたデータなので変更できません。

上記のAとBからなる2×10=20bitのバイナリデータが送信内容となります。

この路線図のようなものはトレリス図と呼ばれています。 送信データの両端に0埋めをしたことによって、トレリス図の両端は必ず「00」状態になる事が見て取れます。

受信側

一番上の行にあるAやBと書かれた20個の四角形が受信したデータです。クリックすることで、bitを反転（送信ミス）を発生させる事が出来ます。

最も可能性が高い元データは00000000です。通信成功!!

受信側のプログラムは、送信元のトレリス図を再現することが目標となります。 どの経路をたどって左端の00から右端の00に辿り着いたのかが分かれば、送信内容を逆算する事が出来ます。 一見簡単な事のように聞こえますが、受信データには一定の確率で送信ミスが乗っています。受信データを鵜呑みには出来ません。

では、どうやって正しい経路を見つければよいでしょうか？ 一番簡単なのは考え得る全ての経路を列挙し「もしその経路が正解の場合、何個の送信ミスが存在するか」を数え上げ、それが最小になる経路を真の経路とする方法です。 しかしながら、それはあまりに非効率的かつ非現実的です。今回だと送信内容が8bitなので全列挙も可能ですが、送信内容が長くなればなるほど全列挙する事が困難になります。

そこで使うのが動的計画法という考え方です。難しい言葉を使っていますが、要は「チェックポイントで負けている経路は脱落者とする」という事です。 分かりやすくするため、トレリス図の各地点を「駅」、線を「交通手段」と考えてみましょうか。そして各線における送信ミスは「運賃」とします。 目標はスタートの駅からゴールの駅まで出来るだけ安くでたどり着く事です。

ここである駅に辿り着くルートが2通りあって、片方の経路が累計1ミス、もう片方の経路が累計4ミスだったとしましょう。 この時、後者の経路を辿る場合は絶対に最小の金額になりません。その駅へたどりつくもっと安い経路があるのに、わざわざ高い方は選ばないですよね？ このようにして「チェックポイントで負けている経路は脱落者とする」事で、計算量をぐっと減らすことが出来るのです。

上記の図では各地点で合流した2本のルートのそれぞれが抱える累計ミス数が書かれています。各地点で脱落者が出る様子がよく分かるのではないでしょうか？