解説動画
符号多項式とは、符号の「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」になる。
符号「11001011」を符号多項式に置き換えたものを記述せよ。
課題1ヒント
- 4ビットの場合に符号が \(x^3\)~\(x^0\) の係数に対応したように、8ビットの場合は \(x^7\)~\(x^0\) の係数に対応する。
- 符号と符号多項式のあいだにイコールを書かないこと。符号と符号多項式は互いに対応するだけで、質的に全く異なるもの。
符号多項式「\(x^6+x^5+x^4+x+1\)」を8ビットの符号に置き換えたものを記述せよ。
課題2ヒント
- 先頭のビットが0だった場合でも、それを省略することはできない。「100 0000」と「0100 0000」は明確に異なる。
解説動画
符号多項式を使った検査符号を使うには、多項式どうしの四則演算、特に割り算のルールを知る必要がある。
符号多項式の係数は符号に対応するので、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\) |
|
符号多項式 \(x^3+x+1\) を \(x+1\) で割る筆算を行い、商と余りを記述せよ。
課題3ヒント
「割られる数」を書くときは、存在しない \(x^2\) の分だけスペースをあける。
係数を取り出して筆算を行ってもよい (割られる数が「1011」割る数が「11」になる)。
その場合でも商と余りは符号多項式の形で書くこと。
解説動画
送信者、受信者が以下のようなことを行えば、通信路で誤りが起きたかどうかを検出できる。
このとき、以下の情報はあらかじめ両者で共有されているものとする。
- 符号を区切る長さ \(k\)
- 検査符号を作るのに使う多項式 \(G(x)\)
(\(G(x)\) の次数 (\(x\) の肩の数値のうち一番大きいもの) を \(m\) とおく)
送信者
- 符号を長さ \(k\) ごとのブロックに区切る
- 1ブロック分の符号を符号多項式 \(P(x)\) に置き換える
- \(P(x)\) に \(x^m\) をかけて \(G(x)\) で割った余り \(R(x)\) を求める
- \(F(x)=x^mP(x)+R(x)\) を求める
- \(F(x)\) を符号に変換 (\(k+m\) ビットになる) して送信する
受信者
- 符号を長さ \(k+m\) ごとのブロックに区切る
- 1ブロック分の符号を符号多項式 \(\tilde{F}(x)\) に置き換える
- \(\tilde{F}(x)\) を \(G(x)\) で割る
- 割り切れる → 「変化なし」と判定 → ブロックの前側 \(k\) ビットを情報源符号として復元する
- 割り切れない → 「変化あり」と判定
例 (\(k=4\), \(G(x)=x^2+1\) とした場合。このときは \(m=2\) になる)
送信者
- (切り出した情報源符号が「1101」だったとする)
- 符号多項式に置き換えると \(P(x)=x^3+x^2+1\) になる
- \(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\) |
- 3の結果から
\(
\begin{eqnarray}
F(x)&=&x^2P(x)+R(x)\\
&=&x^5+x^4+x^2+x
\end{eqnarray}
\)
- \(F(x)\) を符号に置き換えると「110110」になる (後ろの2ビットが検査符号)。
受信者
- 符号を長さ \(k+m\) ごとのブロックに区切る (通信路で変化していなければ)「110110」が得られる。変化していると別のものになる)。
- それを符号多項式に置き換える (変化していなければ \(\tilde{F}(x)=x^5+x^4+x^2+x\) に、変化していれば別のものになる)。
- それを \(G(x)=x^2+1\) で割る
- 変化していない場合 → 割り切れる → 「1101」を情報源符号として復元
- 変化していた場合 → 割り切れない → 「変化あり」と判定して再送信を要求
概要の例と同じ条件 (\(k=4\), \(G(x)=x^2+1\)) で、情報源符号「1110」に検査符号を付け加えたものを記述せよ。
課題4ヒント
概要の太枠の説明のうち、「送信者」の手順2~4を行う。
3番目のステップの筆算も書くこと。筆算は多項式の形、係数だけの形のどちらでもよい。
ノート・紙に解いた課題を撮影したものを以下のフォームから送信してください。
課題提出用フォーム
※ 締切は12/7(土) 正午です。提出によって出席・点数がつきます。