CM · 雑音と情報

誤り符号化

シャノンは容量の下で誤りを 0 に近づけられると約束したが、方法は言わなかった。データに規則で計算した余分なビットを足せば、雑音が反転したビットを検出し、さらにどこが誤ったかを突き止めて正せることを学ぶ。

反転したビット、三つの符号の対応

保護なし・パリティ・ハミングを順に押してみよう。同じ一ビット誤りに対し、データだけでは気づきもせず、パリティ一ビットは検出のみ、ハミングはどのビットかを突き止めて正す。

符号のビット数と最小距離

n = 4, k = 4 · d_min = 1

保護なし

雑音はビットを反転する

前に見たように、雑音は受信機で 0 を 1 に、1 を 0 に時折反転する。データビットだけを裸で送ると、受け取った 1011 が元の 1011 か、一ビット反転した 1001 だったかを見分ける術がない。すべての 4 ビットパターンが等しくもっともらしいデータなので、誤りが起きたことすら分からない。

余分なビットが番人

データから規則で計算した検査ビットを足すと事情が変わる。最も単純なパリティビットは全データビットの XOR で、1 の個数を常に偶数に保つ。雑音がどれか一ビットを反転すると 1 の個数が奇数になりパリティ検査が崩れるので、受信機は誤りが起きたと分かる。ただしパリティ一つではどのビットが誤ったかまでは突き止められない。

観察p = d₁ ⊕ d₂ ⊕ d₃ ⊕ d₄

パリティはデータビットの XOR。

選ぶdetect 1: d_min ?

単一誤りの検出は最小距離 2 でよい。

距離が訂正を生む

符号語を点と見れば、良い符号は有効な点どうしを遠く離す。二つの符号語が異なるビット位置の数をハミング距離という。すべての有効符号語間の最小距離が 2 なら一ビット誤りを検出でき、3 なら一ビット誤りを訂正までできる。誤った語が依然として元の符号語に最も近いからだ。ハミング(7,4) は検査ビット 3 個で 7 ビット中どの一ビット誤りも突き止めて正す。その代償は符号率 R = k/n = 4/7、情報 4 ビットに 3 ビットの余分を払うことだ。

空欄correct 1: d_min ≥ ?

単一誤りの訂正は最小距離 3 が要る。

自分でR = kn = ?

符号率はデータビットを全ビットで割った値。

最初の画面に戻ると

保護がないとき反転したビットは痕跡もなく有効なデータに見えて赤く、パリティ一ビットを足すと何かが崩れた信号は出たがどのビットかは分からず橙、ハミングの検査ビットがずれを集めてそのビットを正確に突き止め戻すと金色になった。誤り符号化で聞き取るべきはただ一つ。余分なビットで有効な語どうしを遠く離せば、雑音が一歩押しやった語も最も近い本来の語へ戻る。これがシャノンの約束、容量の下の信頼性を実際に守る方法だ。

誤り符号化はデータから規則で計算した余分な検査ビットを足し、雑音が反転したビットを検出し訂正する。パリティ一ビット(最小距離 2)は単一誤りを検出し、最小ハミング距離 3 以上の符号(例: ハミング(7,4))は単一誤りを突き止めて訂正する。有効符号語を離すほど強いが、その代償に符号率 R = k/n が 1 より小さくなる。これがシャノンの容量定理の構成的な裏面だ。

通信トラックを終えて

なぜ変調するのかから出発し、ここまで一つのメッセージの旅をたどってきた。基底帯域の小さな揺れを搬送波に載せて周波数軸へ上げ(AM・FM)、数値に変え(標本化・PCM)、ビットで搬送波を揺らし(ASK・FSK・PSK)、帯域幅の天井に出会い、雑音と SNR を測り、無作為を確率で飼いならし、シャノンの絶対限界を見て、ついにその限界の下で誤りを符号で戻した。通信とは結局、雑音に満ちた世界でメッセージを失わずに渡す技だ。