第13回 符号多項式による検査符号 (2)

初めに必ず連絡事項を確認してください。

組み合わせによる検査符号の導出

概要

解説動画

前回見たように、符号多項式による検査符号は
  1. 符号を長さ \(k\) ごとのブロックに区切る
  2. 1ブロック分の符号を符号多項式 \(P(x)\) に置き換える
  3. \(P(x)\) に \(x^m\) をかけて \(G(x)\) で割った余り \(R(x)\) を求める
  4. \(F(x)=x^mP(x)+R(x)\) を求める
  5. \(F(x)\) を符号に変換する
という手順で追加できる。しかし、実は基本となる情報源符号に対応する検査符号を求めておけば、もっと簡単に検査符号を求める方法がある。
例として \(k=4\), \(G(x)=x^3+x+1\) の場合を考える。
このケースでは4ビットの情報源符号に3ビットの検査符号が加わることになるので、検査符号追加済みの7つの桁を左から順に \(x_1\)~\(x_7\) と書くことにする。
\(x_1~x_4\) が情報源符号、\(x_5~x_7\) が検査符号にあたる (例えば「1111111」なら\(x_1=1, x_2=1,\cdots,x_7=1\))。
1000~0001の4組の情報源符号につく検査符号は表1のようになる (これらは上記の手順でそれぞれ地道に求めたもの)。

表1
情報源符号 \(P(x)\) \(x^3P(x)\) \(R(x)\) 検査符号
1000 \(x^3\) \(x^6\) \(x^2+1\) 101
0100 \(x^2\) \(x^5\) \(x^2+x+1\) 111
0010 \(x\) \(x^4\) \(x^2+x\) 110
0001 \(1\) \(x^3\) \(x+1\) 011

これらを組み合わせれば、どんな情報源符号に対応する検査符号も (符号多項式の計算をしなくても) 簡単に求められる。
例えば情報源符号「0011」は表1の「0010」と「0001」を足したもので、それに対応する検査符号 (101) もそれぞれの行の検査符号の各ビットの排他的論理和 (繰り上がりのない足し算) で求められる。
情報源符号 検査符号
0010 110
0001 011
0011 101

同様に、例えば情報源符号「1110」につく検査符号は、表1の「1000」「0100」「0010」(1~3行目) の検査符号の排他的論理和で求められる (100) 。
情報源符号 検査符号
1000 101
0100 111
0010 110
1110 100

要するに、表のものを組み合わせてできる情報源符号のそれぞれの桁の検査符号は「1の数をカウントし、奇数なら1, 偶数なら0」になる。

一般化して考えると、\(x_1\) が1のときに1行目、\(x_2\) が1のときに2行目、…を計算に入れることになるので、情報源符号「\(x_1x_2x_3x_4\)」に対応する検査符号 「\(x_5x_6x_7\)」は
\(x_5=x_1\oplus x_2\oplus x_3\cdots(1)\)
\(x_6=x_2\oplus x_3\oplus x_4\cdots(2)\)
\(x_7=x_1\oplus x_2\oplus x_4\cdots(3)\)

で計算できる。
組み合わせで検査符号が作れる理由
組み合わせのもとになる情報源符号を置き換えた符号多項式を \(P_1(x), P_2(x)\)、それぞれに対して上記3番目の手順で求めた余りを \(R_1(x), R_2(x)\)、その割り算の商を \(Q_1(x), Q_2(x)\) とすると、それぞれ
\( \begin{eqnarray} x^mP_1(x)&=&Q_1(x)G(x)+R_1(x)\\ x^mP_2(x)&=&Q_2(x)G(x)+R_2(x)\\ \end{eqnarray} \)

という関係が成り立つ。これらの式を足すと
\(x^m\left(P_1(x)+P_2(x)\right)\) \(=\left(Q_1(x)+Q_2(x)\right)G(x)\) \(+R_1(x)+R_2(x)\)

となる。つまり、情報源符号の組み合わせからできる符号多項式 \(P(x)=P_1(x)+P_2(x)\) は「\(x^m\) をかけて \(G(x)\) で割った余りが \(P(x)=R_1(x)+R_2(x)\) になる」という関係をいつでも満たすことになる。これは情報源符号を3つ、4つ組み合わせた場合でも同様。
ただし、情報源符号と検査符号の関係はもちろん \(G(x)\) の形に依存する。例えば \(k=4\), \(G(x)=x^3+x^2+1\) の場合には表2のようになり、(1)~(3)にあたる計算式も別のものになる。

表2
情報源符号 \(P(x)\) \(x^3P(x)\) \(R(x)\) 検査符号
1000 \(x^3\) \(x^6\) \(x^2+x\) 110
0100 \(x^2\) \(x^5\) \(x+1\) 011
0010 \(x\) \(x^4\) \(x^2+x+1\) 111
0001 \(1\) \(x^3\) \(x^2+1\) 101

課題1

\(k=4\), \(G(x)=x^3+x+1\) (表1との条件) の場合に、情報源符号「0110」に検査符号を付け加えたものを記述せよ。
課題1ヒント

課題2

\(k=4\), \(G(x)=x^3+x^2+1\) (表2の条件)で、(1)~(3)に相当する関係式 (1)'~(3)'を求めよ。
課題2ヒント

符号多項式を使った検査符号による誤り訂正

概要

解説動画

(1)~(3)式は、検査符号を求めるだけでなく、受信者が誤り検出や誤り訂正に使うこともできる。
表1の条件の場合に受信者が「1011110」を受け取り、ブロック中の変化が1回以下だったと仮定する。
(1)~(3)にこの符号のそれぞれの桁の値を入れてみると、
(1):\(x_1\oplus x_2\oplus x_3\)\(=1\oplus0\oplus1=0\)\(\neq1\) (\(x_5\) と等しくならない)
(2):\(x_2\oplus x_3\oplus x_4\)\(=0\oplus1\oplus1=0\)\(\neq1\) (\(x_6\) と等しくならない)
(3):\(x_1\oplus x_2\oplus x_4\)\(=1\oplus0\oplus1=0\)\(=0\) (\(x_7\) と等しい)

で、(1)、(2)が成り立たない。(3)が成り立つことから \(x_1, x_2, x_4, x_7\) が正しいことは保証されているので、変化した可能性があるのは \(x_3, x_5, x_6\) のいずれかということになる。
このうち \(x_3\) が(1), (2)の両方に含まれているので、これが変化したことがわかる。つまり、本来受け取るはずだった符号は「1001110」で、情報源符号は「1001」。

課題3

\(k=4\), \(G(x)=x^3+x+1\) (表1の条件)で符号多項式を使った検査符号を追加し、受信者が符号「1101100」を受け取ったときの情報源符号を記述せよ。ただし、変化は1回以下であるものとし、導出過程も書くこと。
課題3ヒント

課題4

\(k=4\), \(G(x)=x^3+x^2+1\) (表2の条件)で符号多項式を使った検査符号を追加し、受信者が符号「1101100」を受け取ったときの情報源符号を記述せよ。ただし、変化は1回以下であるものとし、導出過程も書くこと。
課題4ヒント

提出

ノート・紙に解いた課題を撮影したものを以下のフォームから送信してください。
課題提出用フォーム
※ 締切は12/14(土) 正午です。提出によって出席・点数がつきます。