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

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

概要

前回見たように、符号多項式による検査符号は

符号を長さ \(k\) ごとのブロックに区切る
1ブロック分の符号を符号多項式 \(P(x)\) に置き換える
\(P(x)\) に \(x^m\) をかけて \(G(x)\) で割った余り \(R(x)\) を求める
\(F(x)=x^mP(x)+R(x)\) を求める
\(F(x)\) を符号に変換する

という手順で追加するが、あらかじめ 1000, 0100, ...などの「一つの桁だけが1で、他は0」という組み合わせの情報源符号につく検査符号を求めておけば、どんな情報源符号につく検査符号もこれらの組み合わせからすぐに求められる。
例えば \(k=4\), \(G(x)=x^3+x+1\) では

(1000～0001につく検査符号は、上記の手順でそれぞれ地道に求めたもの)

のようになり、「1001」につく検査符号は「1000」と「0001」につく検査符号を使い、それぞれの桁で排他的論理和をとれば求められる。

検査符号1桁目：\(1\oplus0=1\)
検査符号2桁目：\(0\oplus1=1\)
検査符号3桁目：\(1\oplus1=0\)

組み合わせで検査符号が作れる理由
組み合わせのもとになる情報源符号を置き換えた符号多項式を \(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} \)

という関係が成り立つ。これらの式を足すと

\( \begin{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) \end{eqnarray} \)

となる。つまり、情報源符号の組み合わせからできる符号多項式 \(P(x)=P_1(x)+P_2(x)\) は「\(x^m\) をかけて \(G(x)\) で割った余りが \(P(x)=R_1(x)+R_2(x)\) になる」という関係をいつでも満たすことになる。これは情報源符号を3つ、4つ組み合わせた場合でも同様。
(符号多項式での「1+1が0になる足し算」は、符号で考えれば排他的論理和になる。パリティ検査符号のように「1が奇数個なら1, 偶数個なら0」と考えても同じ)

課題1

\(k=4\), \(G(x)=x^3+x+1\) (上の概要と同じ条件) の場合に、以下の情報源符号に検査符号を加えたものを記述せよ。

0110
1111

1番目は上の図で縦に2行目と3行目を足し、2番目は縦に全部足せば求められる。

課題2

\(k=4\), \(G(x)=x^3+x^2+1\) の場合に、1000, 0100, 0010, 0001に検査符号を追加したものを記述せよ。

\(x^3P(x)\) (1000, 0100, 0010, 0001を符号多項式に置き換えて \(x^3\) をかけたもの) はそれぞれ \(x^6, x^5, x^4, x^3\) になる。
それらを \(G(x)=x^3+x^2+1\) で割って余りを求め (筆算を書く)、それを \(x^3P(x)\) に加えてから符号に置き換える。
まじめに \(F(x)=x^3P(x)+R(x)\) の形を書かなくても、「もとの符号4ビット」と「余りを符号に置き換えた3ビット」をつなげて7ビットにすればOK。

課題3

\(k=4\), \(G(x)=x^3+x^2+1\) の場合に、課題1の2つの情報源符号に検査符号を追加したものを求めよ。

やることは課題1と同様。最初の例の図のかわりに課題2の結果を使うだけ。

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

概要

検査符号が組み合わせで決まるという性質を利用すると、情報源符号と検査符号の間に成り立つ関係がわかる。
今日の最初の例 (\(k=4\), \(G(x)=x^3+x+1\)) で、検査符号追加済みの7つの桁を左から順に \(x_1\)～\(x_7\) (それぞれが0か1の値をとる) と書くことにすると、

\( \begin{eqnarray} (「1001」につくx_5)&=&(「1000」につくx_5)\oplus(「0001」につくx_5)\\ (「0110」につくx_5)&=&(「0100」につくx_5)\oplus(「0010」につくx_5)\\ (「1111」につくx_5)&=&(「1000」につくx_5)\oplus(「0100」につくx_5)\oplus(「0010」につくx_5)\oplus(「0001」につくx_5) \end{eqnarray} \)

のように、\(x_1\)～\(x_4\) の値が1であるものだけを足し合わせることになる。ということは、情報源符号 \(x_1x_2x_3x_4\) (それぞれの桁が0か1の値をとる) に対しては

\( \begin{eqnarray} x_5&=&\hspace{12pt}x_1\times(「1000」につくx_5)\\ &&\oplus x_2\times(「0100」につくx_5)\\ &&\oplus x_3\times(「0010」につくx_5)\\ &&\oplus x_4\times(「0001」につくx_5)\\ \end{eqnarray} \)

のような形で書くことができる。この例では (「0001」につく \(x_5\)) は0, それ以外は1なので、

\( \begin{eqnarray} x_5&=&(x_1\times 1)\oplus(x_2\times 1)\oplus(x_3\times 1)\oplus(x_4\times 0)\\ &=&x_1\oplus x_2\oplus x_3\cdots(1) \end{eqnarray} \)

という関係がいつでも成り立つ。\(x_6\), \(x_7\) についても同様に考えれば

\( \begin{eqnarray} x_6&=&x_2\oplus x_3\oplus x_4\cdots(2)\\ x_7&=&x_1\oplus x_2\oplus x_4\cdots(3) \end{eqnarray} \)

という関係が成り立つことがわかる。受信者側では (いちいち割り算をしなくても) (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」。

課題4

\(k=4\), \(G(x)=x^3+x+1\) (課題1, 上の概要と同じ条件)で、以下の符号を受け取ったときの情報源符号を記述せよ。ただし、変化は1回以下であるものとする。

1111000
0101110

課題5

\(k=4\), \(G(x)=x^3+x^2+1\) (課題2と同じ条件)で、(1)～(3)に相当する関係式を求めよ。

欲しいのは \(x_5～x_7\) を\(x_1～x_4\) の組み合わせで表わした形。課題2の結果を使えば求められる。