説明
符号語wを送り、e個以内の要素が誤って受信されたものとします。誤って受信された符号語はwから距離e以内にあります。e< (d -1)
/ 2 ならば、この範囲は他の符号語vから距離e以内の範囲と交差することはない。従って、この符号をwとすることにより、誤りを訂正できます。
また、e<=d-1 なら、e以内の距離に他の符号は存在しませんから、他の符号vと認識することはありまえん。従って、誤りを検出する事ができます。
検査ビット
データに検査ビットを付加し、これを送信します。受信したとき、正しく受信できたかを検査します。
誤りが検査可能な条件を検査能力、訂正できる条件を訂正能力といいます、
ハミング符号
nビットの検査符号を付加し、符号語のビット数を ｍ = 2n-1 とする距離３の符号をハミング符号と呼びます。送信可能なデータのビット数は
k = m-n
となります。
n=3 のとき m=7、k=4 となります。
また、送信データを（x1,x2,x3,x4）とすると、検査ビットは以下のように生成します。+ はEXORです。
c1 = x2 + x3 + x4
c2 = x1 + x3 + x4
c3 = x1 + x2 + x4
ハミング符号は1ビット訂正可能です。
符号の距離
送信するビット列の集合を符号と呼びます。二つの符号をx=(x1,x2,..xn)、y=(y1,y2..yn) とします。xi とyiの値が異なる
i の数をｘとｙの距離とよびます。
この距離は、一般の距離公理を満足します。パリティビットを付加した符号は、距離２の符号になります。
訂正、検出能力
符号Cの最小距離をdとします。Cの符号語を伝送するとき
e = (d -1) /
2
個以内の誤りは、もとの符号語に戻すことができます。eを符号の誤り訂正能力とよびます。
また、dより小さな誤りは（訂正はできませんが）誤りの検出が可能です。
パリティを付加した符号は、1ビットの誤りを検出できます。
パリティチェック
＋をモード２の加算（EXOR演算）とします。ei を 0/1 としたとき、en をパリティ検査ビットと呼びます。
en = e1 + e2 + .. + en-1
このとき
e1 + e2 + .. + en-1+ en
は0になります。0でないとき、どこかのビットが誤っています。