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

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

符号多項式

概要

解説動画

符号多項式とは、符号の「0」「1」を多項式の係数に置き換えたもの。
例えば「1101」を符号多項式にすると \(x^3\), \(x^2\), \(x^1\), \(x^0\) の係数がそれぞれ 1, 1, 0, 1 で「\(x^3+x^2+1\)」になる (\(x^1\) は\(x\)、\(x^0\) は \(1\)))。

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

課題1

符号「11001011」を符号多項式に置き換えたものを記述せよ。

課題1ヒント

課題2

符号多項式「\(x^6+x^5+x^4+x+1\)」を8ビットの符号に置き換えたものを記述せよ。

課題2ヒント

符号多項式の演算

概要

解説動画

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

足し算
それぞれの係数ごとに排他的論理和をとる。その結果は
\(0\oplus0=0\)
\(0\oplus1=1\)
\(1\oplus0=1\)
\(1\oplus1=0\)

なので、例えば
\( \begin{eqnarray} &&(x^3+x^2+x)+(x^2+x+1)\\ &=&(1\oplus0)x^3+(1\oplus1)x^2+(1\oplus1)x+(0\oplus1)\\ &=&x^3+1 \end{eqnarray} \)
のようになる。
1行目が
\((x^3+x^2+x)\oplus(x^2+x+1)\)
ではないことに注意。排他的論理和はあくまで係数に対して行われるものであり、多項式に対するものではない。

引き算
それぞれの係数ごとに排他的論理和をとる。要するに足し算と同じ。
\( \begin{eqnarray} &&(x^3+x^2+x)-(x^2+x+1)\\ &=&(1\oplus0)x^3+(1\oplus1)x^2+(1\oplus1)x+(0\oplus1)\\ &=&x^3+1 \end{eqnarray} \)
直感的な結果との違いは「0-1が1になる」ということ。

掛け算
基本的なルールは普通の掛け算と同じだが、係数同士の足し算が排他的論理和になる。
例えば
\( \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+x^4+x^3+x^4+x^3+x^2+x^3+x^2+x\\ &=&x^5+(1\oplus1)x^4+(1\oplus1\oplus1)x^3+(1\oplus1)x^2+x\\ &=&x^5+x^3+x \end{eqnarray} \)

割り算
基本的なルールは普通の10進数の筆算と同じだが、それぞれのステップでの引き算が係数の排他的論理和になる。
例えば \(x^3+1\) を \(x+1\) で割ると、以下の結果から商が \(x^2+x+1\) で 余りが \(0\) になる。
※ \(x^3-(x^3+x^2)\) は \(x^3+(x^3+x^2)\) と同じ。\(x^3\)の係数は0, \(x^2\)の係数は1になる
\(x^2\) \(+\) \(x\) \(+\) \(1\)
\(x+1\) \()\) \(x^3\) \(+\) \(1\)
\(x^3\) \(+\) \(x^2\)
\(x^2\)
\(x^2\) \(+\) \(x\)
\(x\) \(+\) \(1\)
\(x\) \(+\) \(1\)
\(0\)
係数の部分だけを取り出してこのように書くこともできる (繰り下がりはない。これは2進数の割り算とは別のもの)。
\(1\) \(1\) \(1\)
\(11\) \()\) \(1\) \(0\) \(0\) \(1\)
\(1\) \(1\)
\(1\) \(0\)
\(1\) \(1\)
\(1\) \(1\)
\(1\) \(1\)
\(0\)
商を書くときのそれぞれの桁の位置に注意。
通常の10進数の筆算では、「割られる数」と「商」の1の位、10の位、100の位、…を縦に揃えて書く。
\(1\) \(2\) \(1\)
\(25\) \()\) \(3\) \(0\) \(4\) \(2\)
\(2\) \(5\)
\(5\) \(4\)
\(5\) \(0\)
\(4\) \(2\)
\(2\) \(5\)
\(1\) \(7\)
\(1\) \(2\) \(1\)
\(25\) \()\) \(3\) \(0\) \(4\) \(2\)
\(2\) \(5\)
\(5\) \(4\)
\(5\) \(0\)
\(4\) \(2\)
\(2\) \(5\)
\(1\) \(7\)
これと同じ考え方で、符号多項式の割り算でも \(x^3, x^2, x, 1\) が縦に並ぶように「桁を揃えて」書く。
こうすることで計算間違いを防ぎやすくなる。
\(x^2\) \(+\) \(x\) \(+\) \(1\)
\(x+1\) \()\) \(x^3\) \(+\) \(1\)
\(x^3\) \(+\) \(x^2\)
\(x^2\)
\(x^2\) \(+\) \(x\)
\(x\) \(+\) \(1\)
\(x\) \(+\) \(1\)
\(0\)
\(x^2\) \(+\) \(x\) \(+\) \(1\)
\(x+1\) \()\) \(x^3\) \(+\) \(1\)
\(x^3\) \(+\) \(x^2\)
\(x^2\)
\(x^2\) \(+\) \(x\)
\(x\) \(+\) \(1\)
\(x\) \(+\) \(1\)
\(0\)
\(1\) \(1\) \(1\)
\(11\) \()\) \(1\) \(0\) \(0\) \(1\)
\(1\) \(1\)
\(1\) \(0\)
\(1\) \(1\)
\(1\) \(1\)
\(1\) \(1\)
\(0\)
\(1\) \(1\) \(1\)
\(11\) \()\) \(1\) \(0\) \(0\) \(1\)
\(1\) \(1\)
\(1\) \(0\)
\(1\) \(1\)
\(1\) \(1\)
\(1\) \(1\)
\(0\)

課題3

符号多項式 \(x^3+x+1\) を \(x+1\) で割る筆算を行い、商と余りを記述せよ。

課題3ヒント
「割られる数」を書くときは、存在しない \(x^2\) の分だけスペースをあける。
係数を取り出して筆算を行ってもよい (割られる数が「1011」割る数が「11」になる)。
その場合でも商と余りは符号多項式の形で書くこと。

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

概要

解説動画

送信者、受信者が以下のようなことを行えば、通信路で誤りが起きたかどうかを検出できる。
このとき、以下の情報はあらかじめ両者で共有されているものとする。

送信者
  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=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)\) とする)
    \(x^3\) \(+\) \(x^2\) \(+\) \(x\)
    \(x^2+1\) \()\) \(x^5\) \(+\) \(x^4\) \(\) \(\) \(+\) \(x^2\) \(\) \(\) \(\) \(\)
    \(x^5\) \(\) \(\) \(+\) \(x^3\)
    \(x^4\) \(+\) \(x^3\) \(+\) \(x^2\)
    \(x^4\) \(+\) \(x^2\)
    \(x^3\)
    \(x^3\) \(\) \(\) \(+\) \(x\)
    \(x\)
    \(1\) \(1\) \(1\) \(0\)
    \(101\) \()\) \(1\) \(1\) \(0\) \(1\) \(0\) \(0\)
    \(1\) \(0\) \(1\)
    \(1\) \(1\) \(1\)
    \(1\) \(0\) \(1\)
    \(1\) \(0\) \(0\)
    \(1\) \(0\) \(1\)
    \(1\) \(0\)
  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

概要の例と同じ条件 (\(k=4\), \(G(x)=x^2+1\)) で、情報源符号「1110」に検査符号を付け加えたものを記述せよ。

課題4ヒント
概要の太枠の説明のうち、「送信者」の手順2~4を行う。
3番目のステップの筆算も書くこと。筆算は多項式の形、係数だけの形のどちらでもよい。

提出

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