動画の解説を参照
符号多項式とは、符号の「0」「1」を多項式の係数に置き換えたものです。
例えば「1101」を符号多項式にすると
| 1 |
|
1 |
|
0 |
|
1 |
| ↓ |
|
↓ |
|
↓ |
|
↓ |
| \(1\times x^3\) |
\(+\) |
\(1\times x^2\) |
\(+\) |
\(0\times x^1\) |
\(+\) |
\(1\times x^0\) |
\(=x^3+x^2+1\) |
のようになります。
符号多項式から符号を得るには、これと逆の置き換えをします (このときは、符号が何bitであるかはあらかじめ指定されます)。
「4bitの符号」と指定されている場合には \(x^3, x^2, x^1, x^0\) の係数が何であるかを見れば符号がわかります。
例えば符号多項式が「\(x^2+1\)」なら
| \(x^2+1=\) |
\(0\times x^3\) |
\(+\) |
\(1\times x^2\) |
\(+\) |
\(0\times x^1\) |
\(+\) |
\(1\times x^0\) |
|
↓ |
|
↓ |
|
↓ |
|
↓ |
|
0 |
|
1 |
|
0 |
|
1 |
のようにして、符号「0101」が得られます。
※ 準備 : 学籍番号を入れて「入力」をクリック (タップ) してください。
符号
を符号多項式に変換してください。
課題1解説
符号多項式
\(x^7\)
\(+\)
\(x^6\)
\(+\)
\(x^5\)
\(+\)
\(x^4\)
\(+\)
\(x^3\)
\(+\)
\(x^2\)
\(+\)
\(x\)
\(+\)
\(1\)
\(0\)
を 8bitの符号に変換してください。
課題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}
\)
のようになります。引き算 \((x^3+x^2+x)-(x^2+x+1)\) でも
結果は同じです。
符号多項式に対応する符号を使って
|
1 |
1 |
1 |
0 |
| ⊕ |
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
のように書くこともできます。「＋」ではなく「⊕」であり、繰り上がりはないことに注意してください。
上記の計算では、符号どうしで足し算・引き算をしているわけではありません。
正確に言えば
1110 に対応する符号多項式に 0111 に対応する符号多項式を足して得られる符号多項式に対応する符号が 1001
1110 に対応する符号多項式から 0111 に対応する符号多項式を引いて得られる符号多項式に対応する符号が 1001
ですが、煩雑なので
この授業ではこれ以降以下の書き方にします。
1110 と 0111 を「足す」と 1001
1110 から 0111 を「引く」と 1001
カギカッコつきの「足す」「引く」が2進数の足し算・引き算ではないことに注意してください。
実際、2進数の足し算・引き算は以下のようになり、上記とはまったく違う結果になります。
\((1110)_2 + (0111)_2 = (10101)_2\)
\((1110)_2 - (0111)_2 = (111)_2\)
掛け算
基本的なルールは普通の掛け算と同じですが、係数同士の足し算が排他的論理和になります。
\(
\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}
\)
これも符号での「掛け算」で考えた方がずっと楽です。筆算はこのようになります。
|
|
|
1 |
1 |
1 |
0 |
| × |
|
|
0 |
1 |
1 |
1 |
|
|
|
1 |
1 |
1 |
0 |
|
|
1 |
1 |
1 |
0 |
|
|
1 |
1 |
1 |
0 |
|
|
|
1 |
0 |
1 |
0 |
1 |
0 |
3つの1110から下の段への計算は2進数の足し算ではなく「足し算」です (繰り上がりはありません)。
実際に符号どうしの掛け算をしているわけではないので、以下のような書き方はできません。
1110 × 0111 = 101010
割り算
基本的なルールは普通の10進数の筆算と同じですが、それぞれのステップでの引き算が係数の排他的論理和になります。
例えば \(x^3\) を \(x+1\) で割ると、以下の結果から商が \(x^2+x+1\) で 余りが \(1\) になります。
このときも「引き算」は⊕の計算で、繰り下がりはありません。
|
|
|
|
\(x^2\) |
\(+\) |
\(x\) |
\(+\) |
\(1\) |
| \(x+1\) |
\()\) |
\(x^3\) |
|
|
|
|
|
|
|
|
\(x^3\) |
\(+\) |
\(x^2\) |
|
|
|
\(x^2\) |
|
\(x^2\) |
\(+\) |
\(x\) |
|
|
|
\(x\) |
|
|
|
\(x\) |
\(+\) |
\(1\) |
|
\(1\) |
符号の「割り算」だとこうなります。
|
|
|
1 |
1 |
1 |
| 11 |
\()\) |
1 |
0 |
0 |
0 |
|
1 |
1 |
|
|
1 |
0 |
|
1 |
1 |
|
|
1 |
0 |
|
1 |
1 |
|
1 |
実際に符号どうしの割り算をしているわけではないので、以下のような書き方はできません。
1000 ÷ 11 = 111 余り 1
1000 / 11 = 111 余り 1
一見小さい数から大きい数を引いているように見えるこれも正しい計算です。
符号に大小はなく、「「足し算」で一番上の桁の1を消す組み合わせを作る」という考え方です。
商を書くときのそれぞれの桁の位置に注意してください。
普通の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 |
|
符号で「割り算」するときの桁の合わせ方も同様です。
正
|
|
|
1 |
1 |
1 |
| 11 |
\()\) |
1 |
0 |
0 |
0 |
|
1 |
1 |
|
|
1 |
0 |
|
1 |
1 |
|
|
1 |
0 |
|
1 |
1 |
|
1 |
|
誤
|
|
1 |
1 |
1 |
|
| 11 |
\()\) |
1 |
0 |
0 |
0 |
|
1 |
1 |
|
|
1 |
0 |
|
1 |
1 |
|
|
1 |
0 |
|
1 |
1 |
|
1 |
|
符号多項式
\(x^5\)
\(+\)
\(x^4\)
\(+\)
\(x^3\)
\(+\)
\(x^2\)
\(+\)
\(x\)
\(+\)
\(1\)
\(0\)
を \(x^2+1\) で割る演算を行い、商と余りを書いてください。
課題3解説
※ 割られる符号多項式、割る符号多項式をともに符号に置き換えて「割り算」した方が簡単です。
※ 商・余りは符号多項式です。符号に置き換えて計算した場合はその結果を符号多項式に変換してください。
動画の解説を参照
符号多項式を使って検査符号を追加し、受信側で変化の有無をチェックできます。
多くのテキストでは符号多項式での足し算と割り算を使って検査符号の決め方の手順を説明していますが、前項で見たようにどちらも符号のまま計算した方がずっと楽なので、
ここでは符号のまま計算する手順を紹介します。
以下の情報はあらかじめ送信側・受信側で共有されているものとします。
- G : 検査符号を作るのに使う符号 (必ず 1 で始まる)
- \(k\) : 1ブロックの情報源符号の長さ
- \(m\) : 1ブロックの情報源符号につける検査符号の長さ (値は「G の桁数 － 1」)
送信側がやること
- 符号を \(k\) bit ごとのブロックに区切る (これを P とします)
- P の後ろに 0 を \(m\) 個くっつける (これを Q とします)
- Q を G で「割った」余り R を求める (ただし、R は \(m\) bit分書きます)
- P の後ろに R をくっつける (これを F とします)
- F を送信する
受信側がやること
- 符号を \(k+m\) bit ごとのブロックに区切る (これを F' とします)
- F' を G で「割る」
- 割り切れる → 「変化なし」と判定 → ブロックの前側 \(k\) bit を情報源符号として復元する (後ろの \(m\) bit を削除する)
- 割り切れない → 「変化あり」と判定
\(k=4\), G = 101 の場合に、情報源符号 P =
に検査符号を付け加えたもの (つまり F) を書いてください。
課題4解説
F が G で割り切れる理由
動画の解説を参照
「送信側がやること」の3番目のステップから「Q を G で「割った余り」が R」なので
Q = (Gで割り切れる部分) ⊕ R
がわかります。さらに4番目のステップから
F = Q ⊕ R
= (Gで割り切れる部分) ⊕ R ⊕ R
= (Gで割り切れる部分) ⊕ (R ⊕ R)
ですが、
0 ⊕ 0 = 0
1 ⊕ 1 = 0
であるため、R が何であっても R ⊕ R = 0 になるので、
F = (Gで割り切れる部分)
つまり、F は G で割り切れます。
通信路で変化が起きていなければ F' = F なので割り切れるはず、変化が起きると割り切れなくなるというわけです。
ノート・紙に解いた課題を撮影したものを以下のフォームから送信してください。
課題提出用フォーム
※ 締切は12/5(金) 12:10です。提出によって出席・点数がつきます。