ISEGORIA / 数学百科事典
符号理論：誤りを訂正する
保存したり送ったりするビットは、雑音で反転することがあります。そこでメッセージには冗長性を加え、いくつかの反転を見つけて元に戻せるように並べます。この並べ方は幾何学です。符号語はすべてのビット列の空間の点で、互いにハミング距離、つまり二つの列が異なる位置の数で遠く離れています。受け取った語は最も近い符号語に復号し、最小距離 d の符号は任意の ⌊(d − 1)/2⌋ 個の誤りを訂正します。ハミングは最初の符号を三つのパリティ検査から作り、検査の失敗が誤りの位置を二進数で表すようにしました。空間に球がいくつ入るかを数えると、どの符号の良さにも限界があることが分かります。リードとソロモンはビットを有限体上の多項式の値に置き換え、可能な限り大きな距離を実現しました。この符号は CD や QR コード、深宇宙探査機を守っています。
前提知識: 二進数、ベクトルと行列、多項式、合同算術
予想してから操作し、各実験の練習問題で理解を確かめてください。練習問題は三つの難易度で毎回新しく生成されます。グラフは数式の図示であり、証明ではありません。
1. ハミング (7,4)：シンドロームが誤りを指す
語の七つのビットに 1 から 7 まで番号をつけ、位置 1、2、4 にパリティビットを置きます。パリティビット 1 は、位置の二進表示の最下位の桁が 1 のビット（1、3、5、7）の和を偶数にします。ビット 2 は 2、3、6、7 について、ビット 4 は 4、5、6、7 について同じことをします。位置 3、5、6、7 が四つのメッセージのビットを運びます。あるビットが反転すると、その位置を含む検査だけがちょうど失敗し、失敗した検査を二進数として読むとその位置になります。ベン図では各検査が円、各位置が領域です。ビットを反転させて奇数の円を見てください。そのあと、4 ビットのメッセージが誤って届く確率を、符号を使う場合と使わない場合で比べてください。
計算例. メッセージ 1011 は位置 3、5、6、7 に入ります。検査 1 は位置 3、5、7 を含み、値は 1、0、1 なのでビット 1 は 0 です。検査 2 は 3、6、7 を含み、値は 1、1、1 なのでビット 2 は 1 です。検査 4 は 5、6、7 を含み、値は 0、1、1 なのでビット 4 は 0 です。符号語は 0110011 です。ビット 6 が反転すると受信語は 0110001 で、検査 1（位置 1、3、5、7：0、1、0、1）は通り、検査 2（位置 2、3、6、7：1、1、0、1）と検査 4（位置 4、5、6、7：0、0、0、1）が失敗します。シンドロームは二進数で 110、つまり 6 です。各ビットが独立に \(p=0.01\) で反転するとき、そのまま送った 4 ビットのメッセージが誤る確率は \(1-0.99^4=0.039\) ですが、符号化すると七つのうち二つ以上が反転したときだけ誤り、\(0.0020\) です。
注意点. この符号は四ビットごとに三ビットを余分に使うので、比較は通信路の一回の使用あたりではなく、メッセージあたりです。メッセージのビットあたりのエネルギーを同じにすると、利点は小さくなります。二つの反転は必ず誤って訂正され、三つ目の誤ったビットが加わります。三つの反転はある符号語を別の符号語に変え、気づかれずに通ることがあります。実際の通信路では誤りがまとまって起こるので、実用の方式はビットを並べ替えたり、次の二つの実験のような大きな符号を使ったりします。
なぜシンドロームはメッセージによらず、誤りだけで決まるのですか？
どの符号語も三つの検査をすべて満たし、\(H\mathbf c^{\mathsf T}=\mathbf 0\) で、検査は線形だからです。受信語は \(\mathbf r=\mathbf c+\mathbf e\)（mod 2 の和）なので、\(H\mathbf r^{\mathsf T}=H\mathbf c^{\mathsf T}+H\mathbf e^{\mathsf T}=H\mathbf e^{\mathsf T}\) です。位置 \(i\) の一つの誤りならこれは \(H\) の第 \(i\) 列で、ハミングは列を 1 から 7 の二進表示に選びました。
2. ハミング空間の球
長さ \(n\) のすべてのビット列は \(n\) 次元立方体の頂点をなし、一ビットだけ違う列どうしは辺で結ばれます。したがってハミング距離は、辺に沿った最短経路の長さです。符号は頂点の集合です。符号語どうしが少なくとも \(d\) 離れていれば、そのまわりの半径 \(t=\lfloor(d-1)/2\rfloor\) の球は重ならず、球の中に受け取った語はその中心に復号されます。球は立方体の頂点より多くの頂点を含めないので \(M\,V(n,t)\le 2^n\) で、これがハミング限界です。ちょうど等号になる符号を完全符号といいます。符号を選び、受信語を立方体のあちこちへ動かし、右の漸近的な限界と比べてください。
計算例. 繰り返し符号 {000, 111} は \(d=3\) なので \(t=1\) です。各球は符号語とその三つの隣を含み \(V(3,1)=1+3=4\) で、二つの球は \(2\times4=8=2^3\) 個、つまり立方体全体の頂点を含みます。完全符号です。受信語 001 は 000 に復号されます。\(n=4\) の {0000, 1111} は \(d=4\) ですが \(t=1\) のままで、二つの球は 16 頂点のうち \(2\times5=10\) 個を含み、重み 2 の六つの語は同点になります。ハミング (7,4) は \(16\times V(7,1)=16\times8=128=2^7\) で完全符号です。ゴレイ符号も \(2^{12}\times V(23,3)=2^{12}\times2048=2^{23}\) で完全符号です。
注意点. 4 次元立方体は立方体の中の立方体として描いています。辺に沿った距離は正確ですが、図の直線距離はハミング距離ではありません。右の曲線は、\(d/n\) を固定して \(n\to\infty\) としたときの極限です。二元の完全符号はまれで、自明なものを除くと、どれもハミング符号か二元ゴレイ符号と同じパラメータをもちます。ギルバート・ヴァルシャモフ限界が二元符号の本当の限界かどうかは、いまも未解決の問題です。
なぜ d = 4 の符号でも訂正できる誤りは一つだけなのですか？
二つの誤りで、二つの符号語から同時に距離 2、つまりちょうど中間の語に着くことがあり、復号器にはどちらへ向かうべきか分かりません。\(t\) 個の誤りを訂正するには半径 \(t\) の球が重ならないことが必要で、それには \(d\ge 2t+1\) が要ります。余分な距離は無駄ではありません。\(d=4\) の符号は一つの誤りを訂正し、同時に任意の二つの誤りを検出します。
3. リード・ソロモン：多項式は損傷に耐える
13 を法とする整数の体で考えます。ここでは 0 でないどの数にも逆数があります。\(k\) 個のメッセージの記号を、次数 \(k\) 未満の多項式 \(P\) の係数とし、\(n\) 個の点での値を送ります。正しい値が \(k\) 個あれば、二点で直線が決まるように \(P\) が決まるので、二つの符号語が一致するのは高々 \(k-1\) か所で、最小距離は \(n-k+1\) です。これはシングルトン限界が許す最大です。バーレカンプとウェルチは、誤った位置で 0 になる誤り位置多項式 \(E\) と \(Q=PE\) を合わせて探すことで復号します。条件 \(Q(x_i)=y_iE(x_i)\) は線形で、割り算を一回すると \(P\) が得られます。記号を誤らせたり消したりして、予算が尽きるまで復号器を見てください。
計算例. GF(13) 上で \(P(x)=5+2x^2\)（\(k=3\)）をとり、\(x=1,\dots,9\) での値 7、0、10、11、3、12、12、3、11 を送ります。\(d=7\) です。\(x=2\) と \(x=5\) の記号を 4 と 7 に変え、\(x=7\) の記号を消します。残る値は八つなので、復号器は \(\lfloor(8-3)/2\rfloor=2\) 個の誤りまで払えます。連立一次方程式を解くと \(E(x)=x^2+6x+10\) で、mod 13 では \(-7\equiv6\) なのでこれは \((x-2)(x-5)\) です。\(Q\) を \(E\) で割ると \(5+2x^2\) に戻ります。もう一つ誤りが増えると \(2e+s=7>6\) となり、復号器は何も保証できなくなります。
注意点. 実際のリード・ソロモン符号は 256 個の元をもつ体を使い、記号が 1 バイトになるようにし、長さは 255 までです。GF(13) は図を小さくするためです。予算を超えると、復号器は失敗を報告するか、まれに別の符号語にたどり着きます。この実験でもそれが見られます。復号した値をつなぐ灰色の線は目の助けにすぎません。有限体上の多項式は曲線ではなく、点の集合です。
なぜ消失は誤りの半分の費用で済むのですか？
消失は損傷の位置を復号器に教えるので、費用は未知の値一つ分です。誤りは値だけでなく位置も隠すので、費用は二つ分です。\(s\) 個の消失した点を除くと、長さ \(n-s\)、距離 \(n-s-k+1\) のリード・ソロモン符号が残り、\(\lfloor(n-s-k)/2\rfloor\) 個の誤りを訂正できます。これが条件 \(2e+s\le n-k\) です。