第14回 符号多項式による検査符号 (1)

符号多項式

概要

符号多項式とは、符号の「0」「1」を多項式の係数に置き換えたもの。例えば4ビットの符号を符号多項式にすると
1101 → \(1\times x^3+1\times x^2+0\times x^1 + 1\times x^0 = x^3+x^2+1\)
0110 → \(0\times x^3+1\times x^2+1\times x^1 + 0\times x^0 = x^2+x\)
のようになる。

符号多項式から符号を得るには、これと逆の置き換えをすればよい。このときは、符号が何ビットであるかはあらかじめ指定される。「4ビットの符号」と指定されている場合には
\(x^2+1 = 0\times x^3+1\times x^2+0\times x^1+1\times x^0\) → 0101
\(x^3+x = 1\times x^3+0\times x^2+1\times x^1+0\times x^0\) → 1010
のようになる。

課題1

次の符号を符号多項式に置き換えたものを記述せよ。
  1. 11001000
  2. 01010101
  • 8ビットの符号 → 符号多項式の項のうち、もっとも \(x\) の次数が大きいのは \(x^7\)。一番左の符号がこの係数になる。
  • 「1101 = \(x^3+x^2+1\)」のような書き方は間違い。符号と符号多項式は互いに対応するだけで、イコールではない。

課題2

次の符号多項式を8ビットの符号に置き換えたものを記述せよ。
  1. \(x^7+x^6+x^4+x\)
  2. \(x^5+x^4+x^3+1\)
  • 先頭のビットが0だった場合でも、それを省略することはできない。「111 1010」と「0111 1010」は明確に異なる。
  • 「\(x^3+x^2+1\) = 1101」のような書き方は間違い。符号と符号多項式は互いに対応するだけで、イコールではない。

符号多項式の演算

概要

符号多項式を使った検査符号を使うには、多項式どうしの四則演算のルールを知る必要がある。
符号多項式の係数は符号に対応するので、0, 1以外の値をとることはできない。そのため、通常の算術とは異なったルールになる。

足し算
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 (これが通常と異なる)


\( \begin{eqnarray} &&(x^3+x^2+x)+(x^2+x+1)\\ &=&x^3+(1+1)x^2+(1+1)x+1\\ &=&x^3+1 \end{eqnarray} \)
引き算
0 - 0 = 0
0 - 1 = 1 (これが通常と異なる)
1 - 0 = 1
1 - 1 = 0


\( \begin{eqnarray} &&(x^3+x^2+x)-(x^2+x+1)\\ &=&x^3+(1-1)x^2+(1-1)x+(0-1)\\ &=&x^3+1 \end{eqnarray} \)
掛け算
基本的なルールは普通の掛け算と同じだが、係数同士の足し算が上記ルールになる


\( \begin{eqnarray} &&(x^3+x^2+x)(x^2+x+1)\\ &=&x^3(x^2+x+1)+x^2(x^2+x+1)+x(x^2+x+1)\\ &=&x^5+(1+1)x^4+(1+1+1)x^3+(1+1)x^2+x\\ &=&x^5+x^3+x \end{eqnarray} \)
割り算
基本的なルールは普通の割り算と同じだが、係数の引き算が上記ルールになる


  • ここでは「0から1を引いて1ができる」ことを明示するために「0-1」を書いているが、実際に計算するときはこのような表記は不要。
  • 商を書くときのそれぞれの桁の位置に注意。通常の10進数の筆算では、「割られる数」と「商」の1の位、10の位、100の位、…を縦に揃えて書く。

  • これと同じ考え方で、符号多項式の割り算でも \(x\) の次数が同じものを縦に揃える。

課題3

符号多項式 \(A=x^3+x+1, B=x+1\) について、以下の演算の結果を記述せよ。
  1. \(A+B\)
  2. \(A-B\)
  3. \(A\times B\)
  4. \(A\div B\) (商、余りの両方を求める)
符号多項式では、\(A\) と \(B\) がどんな形であっても、必ず \(A+B\) と \(A-B\) は同じになる。それはなぜか?

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

概要

送信者、受信者が以下のようなことを行えば、通信路で誤りが起きたかどうかを検出できる。
このとき、以下の情報はあらかじめ両者で共有されているものとする。
  • 符号を区切る長さ \(k\)
  • 検査符号を作るのに使う多項式 \(G(x)\)
  • (\(G(x)\) の次数 (\(x\) の肩の数値のうち一番大きいもの) を \(m\) とおく)

送信者
  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+m\) ビットになる) して送信する

受信者
  1. 符号を長さ \(k+m\) ごとのブロックに区切る
  2. 1ブロック分の符号を符号多項式 \(\tilde{F}(x)\) に置き換える
  3. \(\tilde{F}(x)\) を \(G(x)\) で割る
    • 割り切れる → 「変化なし」と判定 → ブロックの前側 \(k\) ビットを情報源符号として復元する
    • 割り切れない → 「変化あり」と判定
例 (\(k=4\), \(G(x)=x^2+1\) とした場合。このときは \(m=2\) になる)

送信者
  1. (切り出した情報源符号が「1101」だったとする)
  2. 符号多項式に置き換えると \(P(x)=x^3+x^2+1\) になる
  3. \(x^2P(x)=x^5+x^4+x^2\)となる。それを \(G(x)=x^2+1\) で割ると、余りは \(x\)。(これを \(R(x)\) とする)
  4. 3の結果から
    \( \begin{eqnarray} F(x)&=&x^2P(x)+R(x)\\ &=&x^5+x^4+x^2+x \end{eqnarray} \)
  5. \(F(x)\) を符号に置き換えると「110110」になる (後ろの2ビットが検査符号)。

受信者
  1. 符号を長さ \(k+m\) ごとのブロックに区切ると (通信路で変化していなければ)「110110」が得られる
  2. それを符号多項式に置き換えると \(\tilde{F}(x)=x^5+x^4+x^2+x\) になる
  3. それを \(G(x)=x^2+1\) で割る(割り切れる) → 「変化なし」と判定 → 「1101」を情報源符号として復元

課題4

上の例と同じ条件で、情報源符号「1110」に検査符号を付け加えたものを記述せよ。

課題5

課題4の符号を通信路に通し、途中で変化が起きなかった (つまり \(\tilde{F}(x)=F(x)\) ) 場合に、\(\tilde{F}(x)\) が \(G(x)\) で割り切れることを確認せよ (筆算を書く)。

課題6

課題4の符号を通信路に通し、前から3番目のビットが変化した場合の \(\tilde{F}(x)\) を \(G(x)\) で割った余りを求めよ (筆算を書く)。
inserted by FC2 system