通信符号理論 03

1 通信符号理論 第3回 伊藤彰則

2 線形符号の実例 • いくつかの線形符号の実例を紹介する • 単一パリティ符号 (n,n-1,2)：1ビットの誤りを検出する • ハミング符号 (7,4,3)：1ビットの誤りを訂正する • 拡大ハミング符号 (8,4,4)：1ビットの誤りを訂正し、2ビットの誤りを 検出する

3 単一パリティ符号 • メッセージに1ビットのパリティを付加する • メッセージ 𝒎 = (𝑚1 , … 𝑚𝑘 ) • パリティ 𝑝 = 𝑚1 + ⋯ + 𝑚𝑘 • 符号語 𝒄 = (𝑚1 , … , 𝑚𝑘 , 𝑝) • 符号語のパリティは必ず0になる（1が偶数個含まれる） • 1ビット誤るとパリティが1になるので検出できる • 検査行列（n=3の例）𝐻 = (1 1 1) 符号語の全ビットを足して０にな ればよい 1 0 1 • 生成行列（n=3の例）𝐺 = 0 1 1 1ビット目＝メッセージの1ビット目 2ビット目＝メッセージの2ビット目 3ビット目＝1ビット目＋2ビット目

4 単一パリティ符号の例 • 符号𝐶 = {000,011,101,110} • 最初の2ビットがメッセージ、3ビット目がパリティ • メッセージ 𝒎 = (1 0)の場合 1 0 1 𝒎𝐺 = 1 0 = 1⋅1+0⋅0 1⋅0+0⋅1 1⋅1+0⋅1 0 1 1 = (1 0 1) 1 • パリティチェック 𝐻𝒙𝑇 = 1 1 1 0 = 1 + 0 + 1 = 0 1

5 ハミング符号 (7,4,3) 1 1 1 0 1 0 0 • 検査行列 𝐻 = 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 • 生成行列 𝐺 = 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 すべての列が異な るところに注目 どうしてこうなる のかは後ほど説明 します

6 ハミング符号の例 • メッセージ 𝒎 = (1 1 0 1) • 符号語 𝒙 = 𝒎𝐺 = 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 = (1 1 0 1 0 0 1) 0 1

7 ハミング符号の例 1 1 1 0 1 0 0 • パリティチェック 𝐻𝒙𝑇 = 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1+1+0+0+0+0+0 0 = 0+1+0+1+0+0+0 = 0 1+1+0+1+0+0+1 0 1 1 0 1 0 0 1

8 ハミング符号のしくみと復号 • ハミング符号の検査行列は、すべての列が異なる値 • 3ビットの値は8種類あるが、そのうち0を除く7種類が1回ずつ現れる • 𝐻 = (𝒉1 , … , 𝒉7 ) • 誤差ベクトル𝒆について𝑤ℎ 𝒆 = 1と仮定する（1ビット誤り） • 𝒆 = 𝑒1 , … , 𝑒7 , 𝑒𝑖 = 1とする • 𝐻𝒚𝑇 = 𝐻𝒆𝑇 = 𝒉1 , … , 𝒉7 𝑒1 ⋮ = 𝑒1 𝒉1 + ⋯ + 𝑒7 𝒉7 = 𝒉𝑖 𝑒7 • シンドロームは検査行列のどれかの列と一致し、 そのビットが誤り

9 生成行列と検査行列 • 生成行列𝐺: 𝑘 × 𝑛、検査行列𝐻: 𝑚 × 𝑛 • 行列𝑃: 𝑘 × 𝑚とし、𝐼𝑚 は𝑚 × 𝑚の単位行列とする • 𝐻 = 𝑃𝑇 𝐼𝑚 , 𝐺 = (𝐼𝑘 𝑃) と表されるとすると 𝐼𝑘 • 𝐻𝒄𝑇 = 𝐻 𝒎𝐺 𝑇 = 𝐻𝐺 𝑇 𝒎𝑇 = 𝑃𝑇 𝐼𝑚 𝒎 𝑇 𝑃 𝑇 𝑇 𝑇 = (𝑃 𝐼𝑘 + 𝐼𝑚 𝑃 )𝒎 = 𝑃 + 𝑃𝑇 𝒎 = 0 1 𝐻= 0 1 1 1 1 𝑃𝑇 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 単位行列 1 𝐺= 0 0 0 0 1 0 0 0 0 1 0 単位行列 0 0 0 1 1 1 1 0 0 1 1 1 𝑃 1 1 0 1

10 生成行列と検査行列 • 𝐺 = (𝐼𝑘 𝑃)の形式の場合、生成される符号語は 𝒎𝐺 = 𝒎 𝐼𝑘 𝑃 = 𝒎𝐼𝑘 𝒎𝑃 = (𝒎 𝒎𝑃) • 符号語の前半kビットはメッセージそのもの、後半mビットはパリティ • これを組織符号化という • GやHが単位行列を含まない形だったら？ 0 • 𝐻= 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 これでも性質は同じなので 符号はハミング符号になる

11 生成行列と検査行列 0 • 𝐻= 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 𝝓1 1 1 = 𝝓2 𝝓3 1 𝝓1 𝒄𝑇 • 符号𝒄について 𝐻𝒄𝑇 = 𝝓2 𝒄𝑇 = 𝟎より、各行が𝝓1 … 𝝓3 の線形結合になっ 𝝓 3 𝒄𝑇 ている行列𝐻′も同じ符号の検査行列である。 𝝓1 + 𝝓2 • 例 𝐻 ′ = 𝝓2 + 𝝓3 𝝓3 + 𝝓1

12 生成行列と検査行列 • 検査行列を変形することによって右半分を単位行列にできる • 掃き出し法と類似のアルゴリズム 0 0 1 2行目＋= 3行目 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1行目＋= 2行目 0 0 1 0 1 0 1 1 0 左半分を転置 単位行列をつ なげる 1 1 1 1 0 0 1 0 1 0 0 3行目＋= 1 1 1行目 0 1 1 𝐺= 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1

13 例と演習 1 0 0 0 1 0 1 𝐺= 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 • 上記のハミング符号で、受信語 𝒚 = 1101011 を復号せよ。 1 1 1 0 1 0 0 •𝐻= 0 1 1 1 0 1 0 1 1 0 1 0 0 1 • シンドロームは 0 1 0 𝑇 。これは検査行列の6ビット目にあたるので、6 ビット目を反転させて、 𝑥ො = 1101001 • メッセージは先頭4ビットなので 1101 • 演習：𝒚 = 1101010 を復号せよ。

14 一般ハミング符号 • (7,4,3)以外のハミング符号も同じ考え方で作れる • 長さ𝑚 ≥ 3のベクトル𝒗1 , … , 𝒗𝑛 ここで𝑛 = 2𝑚 − 1 • 𝒗𝑖 ≠ 0 かつ 𝑖 ≠ 𝑗ならば 𝒗𝑖 ≠ 𝒗𝑗 とする • 𝐻 = (𝒗1𝑇 , … , 𝒗𝑇𝑛 ) が一般ハミング符号の検査行列 • m=3なら (7,4,3), m=4 なら (15, 11, 3) • 一般には (2𝑚 − 1, 2𝑚 − 1 − 𝑚, 3)

15 拡大ハミング符号(8,4,4) • ハミング符号は1ビットの誤りを訂正できるが、2ビットの誤り は検出も訂正もできない •例 • 符号語𝒄 = 0000000、受信語𝒚 = 0000011 • シンドロームは 0 1 1 𝑇 したがって4ビット目が誤りと判定され、 ෝ = 0001011となる 𝒙 • せめて2ビット誤りを検出できるようにならないか ⇒拡大ハミング符号

16 拡大ハミング符号(8,4,4) • 拡大ハミング符号は、ハミング符号にパリティビットを付加し たもの • ハミング符号をさらに単一パリティ符号で符号化したのとおなじ • 例 符号語𝒄 = 00000000、受信語𝒚 = 00000110 • 最後の1ビットはパリティなので除いて復号すると、 ෝ = 0001011となる 𝒙 • 復号結果にもう一度元のパリティビットを連結すると ෝ = 00010110 となる 𝒙 • この復号結果には1が奇数個含まれているので、 パリティが合わない⇒誤りであることがわかる

17 きちんと説明すると • ハミング符号の符号語を𝒄とする • 受信語 𝒚 = 𝒄 + 𝒆, 𝑤ℎ 𝒆 = 2 とし、復号結果を𝒄′ ≠ 𝒄 とする • 誤差ベクトル 𝒆 = 𝒆1 + 𝒆2 , 𝑤ℎ 𝒆1 = 𝑤ℎ 𝒆2 = 1 とする • シンドローム 𝐻𝒚𝑇 = 𝐻𝒆𝑇 = 𝐻𝒆1𝑇 + 𝐻𝒆𝑇2 = 𝒉𝑖 + 𝒉𝑗 ≠ 0 • 誤りを1ビットと仮定して訂正するので、𝑑ℎ 𝒚, 𝒄′ = 1 • 𝑑ℎ 𝒚, 𝒄 = 2なので、𝑑ℎ (𝒄, 𝒄′ )は1または3である。符号の最小距 離は3なので、 𝑑ℎ 𝒄, 𝒄′ = 3 とわかる。 • したがって𝒄と𝒄′のパリティは異なるので、 単一パリティ符号によって誤りが検出できる

18 表による復号 • ハミング符号は、シンドロームを見ればただちにどのビットが 誤ったかわかるようになっていた • そのような特殊な符号ではなく、一般の線型符号に利用できる 復号法：シンドローム表復号 • シンドロームが同じ値になるベクトルの集合を「コセット」と呼ぶ • シンドロームの値ごとに、誤差ベクトルを記録しておく • 通常はコセットの中で最もハミング重みが小さいベクトル（コセットリーダー） • シンドロームがわかれば、そこから表を引くことで誤りがわかる

19 例 1 1 1 0 0 1 0 1 0 1 •𝐺= ,𝐻= 0 1 0 1 0 0 1 1 1 0 1 0 0 0 1 • 5ビットの値に対して片っ端からシンドロームを計算する 受信語 S 受信語 S 受信語 S 受信語 S 00000 000 01000 110 10000 101 11000 011 00001 001 01001 111 10001 100 11001 010 00010 010 01010 100 10010 111 11010 001 00011 011 01011 101 10011 110 11011 000 00100 100 01100 010 10100 001 11100 111 00101 101 01101 011 10101 000 11101 110 00110 110 01110 000 10110 011 11110 101 00111 111 01111 001 10111 010 11111 100

20 例 • シンドロームが001となる受信語と、それに最も近い符号語 受信語 シンドローム 復号結果 誤差ベクトル 00001 001 00000 00001 01111 001 01110 00001 10100 001 10101 00001 11010 001 11011 00001 シンドロームの値が同じ ＝誤り位置が同じ （シンドロームは誤りの情報の みを含むため） シンドロームが001 ⇒誤りベクトル＝00001 という情報を表にしておけばよい シンドロームの種類2𝑚 は、符号語の種類2𝑛 よりも少ないので表が小さくなる （例では2𝑛 = 32, 2𝑚 = 8）

21 シンドローム表 • シンドロームの値ごとに誤差ベクトルを記録したもの シンドローム 誤差ベクトル 001 00001 010 00010 011 00011/11000 100 00100 101 10000 110 01000 111 01001/10010 1ビットしか誤りがない場合は これらのシンドロームは現れ ない