ハミング符号

さて、原理について数学的なことはまだ理解していないけれど、まぁちょっぴり書きますね。

反復符号

反復符号 $%5Cmathcal{R}_n$ を考えよう。一桁の情報 $%5Cmathbf{a}=a_1$ は $n$ 桁の符号語 $%5Cmathbf{u}=u_1u_2%5Cdots u_n$ に符号化される。要するに $n$ 個並べるというだけのことだ。
決定則*1は最尤度復号。反復符号の場合、 $u_1,u_2,%5Cdots ,u_n$ のうちで一番多いものを元の情報とする。このとき $%5Cmathcal{R}_n$ は $%5Cleft%5Clfloor{%5Cfrac{n-1}{2}}%5Cright%5Crfloor$ 個の誤りを訂正できる。そのくらい間違ってても大丈夫、ということ。

誤り訂正と伝送レート

さて、とある符号が $t$ 個の誤りを訂正できるとき、その符号を $t$ 重誤り訂正符号と呼ぶ。以下では一重訂正符号について考えることにする。例えば反復符号 $%5Cmathcal{R}_3$ は一重誤り訂正符号である。また、1桁の情報を3桁に符号化していることから、その伝送レートは $%5Cfrac{1}{3}$ となる。

さて、しかし最尤度復号は復号が面倒だし、それに反復符号はいまいち伝送レートが低い。そこで考えられたのがハミング符号だ。
ハミング符号 $%5Cmathcal{H}_7$ は四桁の情報 $a_1a_2a_3a_4$ を七桁の符号語 $u_1u_2u_3u_4u_5u_6u_7$ に符号化する。細かい原理の説明はおいておいて(ぇ)、符号化の手順を書こう。

二元体

二つの要素 $%5C{0,1%5C}$ からなる集合について、以下のように加算と乗算を定義する。
$%5Cleft%5C{%5Carray{ll$0+0=1+1=0%5C%5C 0+1=1+0=1}%5Cright%5C.$
$%5Cleft%5C{%5Carray{ll$0%5Ctimes 0=0%5Ctimes 1=1%5Ctimes 0=0%5C%5C 1%5Ctimes 1=1}%5Cright%5C.$
1+1=0から、-1=1となることは自明である。この集合は加算、減算、乗算、ゼロでない除算について閉じており、交換法則やら結合法則を満たすので、体と呼ばれ、特にこれを二元体と呼ぶ*2。

符号化

まず、 $u_3=a_1,u_5=a_2,u_6=a_3,u_7=a_4$ とする。次に、 $%5Cmathbf{u}$ の検査和
$%5Cleft%5C{%5Carray{s_1=u_4+u_5+u_6+u_7%5C%5C s_2=u_2+u_3+u_6+u_7%5C%5C s_3=u_1+u_3+u_5+u_7}%5Cright%5C.$
がすべて0となるように $u_1,u_2,u_4$ を決定する。これで完成。例えば $%5Cmathbf{a}=1011$ だった場合、 $u_3=1,u_5=0,u_6=1,u_7=1$ で、
$%5Cleft%5C{%5Carray{s_1=u_4+0+1+1=0%5C%5C s_2=u_2+1+1+1=0%5C%5C s_3=u_1+1+0+1=0}%5Cright%5C.$
から $u_1=0,u_2=1,u_4=0$ となり、結局 $%5Cmathbf{u}=0110011$ である。

復号

さて、符号語 $%5Cmathbf{u}$ が $%5Cmathbf{v}$ として受信されたとしよう。このとき $%5Cmathbf{u}$ と $%5Cmathbf{v}$ のハミング距離は1以内ならば、ハミング符号は誤りを訂正することができる。
まず、符号化のときと同じように $%5Cmathbf{v}$ の検査和を計算し、それぞれの値を ${s_1}^%5Cprime,{s_2}^%5Cprime,{s_3}^%5Cprime$ とする。 $i=4{s_1}^%5Cprime+2{s_2}^%5Cprime+{s_3}^%5Cprime%5Cneq0$ のとき、 $i$ 桁目に誤りが発生していることがわかる。
先の例と同じく、 $%5Cmathbf{u}=0110011$ として、伝送の過程で六桁目に誤りが発生し、 $%5Cmathbf{v}=0110001$ として受信されたとする。このとき検査和は ${s_1}^%5Cprime=1,{s_2}^%5Cprime=1,{s_3}^%5Cprime=0$ であるから、 $4{s_1}^%5Cprime+2{s_2}^%5Cprime+{s_3}^%5Cprime=6$ 桁目に誤りが発生しているとわかるので、訂正することができる。すごいぞハミング符号。

あといろいろ

さて、ところで、4桁の情報を7桁に符号化しているのだから、ハミング符号 $%5Cmathcal{H}_7$ の伝送レートは $%5Cfrac{4}{7}>%5Cfrac{1}{3}$ である。同じ一重誤り訂正符号でも、反復符号 $%5Cmathcal{R}_3$ より効率がよい。
$%5Cmathcal{H}_7$ を構成するのと同様の手法で、 $%5Cmathcal{H}_{15}$ を構成することができ、伝送レートは $%5Cfrac{11}{15}>%5Cfrac{4}{7}$ である。このように任意に高い伝送レートを持つ符号を構成することができる、とシャノンあたりが証明したそうな。
いまいち説明できませんね。いつかまたきちんと書くつもりです。線形符号がどうとか。

*1:符号から情報を推定する規則。復号。

*2:厳密にどうかは知りませんけど、だいたい。