動画の解説 を参照
前回見たように、符号多項式による検査符号は
符号を \(k\) bit ごとのブロックに区切る (これを P とします)
P の後ろに 0 を \(m\) 個くっつける (これを Q とします)
Q を G で「割った」余り R を求める (ただし、R は \(m\) bit分書きます)
P の後ろに R をくっつける (これを F とします)
(F を送信する)
という手順で追加できます。しかし、実は基本となる情報源符号に対応する検査符号を求めておけば、もっと簡単に検査符号を求める方法があります。
例として、\(k=4\), G = 1011 (\(m=3\)) の場合を考えてみましょう。
このケースでは4bitの情報源符号 P に3bitの検査符号 R が加わり、Fは7bitになります。
P が 1000, 0100, 0010, 0001 のように「1つだけ 1 で残りは 0」のものについて R を求めると以下のようになります。
(それぞれ上記の手順で地道に求めてまとめたものです)
表1
P
R
1000
101
0100
111
0010
110
0001
011
これらを組み合わせれば、どんな情報源符号に対応する検査符号も (2～4の計算をしなくても) 簡単に求められます。
例えば情報源符号が P = 1100 なら、1000 と 0100 に対応する R、つまり 101 と 111 の「足し算」で検査符号 R = 010 が得られます。
※ 準備 : 学籍番号を入れて「入力」をクリック (タップ) してください。
学籍番号
入力
\(k=4\), G = 1011 として、情報源符号 P =
に検査符号を追加した符号 F を求めてください。
課題1解説
動画の解説 を参照
前回は符号多項式を使った検査符号による誤り検出について解説しましたが、前項でみた P と R の関係を使うと誤り訂正を行うこともできます。
情報源符号 P と検査符号 R のそれぞれの桁には、いつでも成り立つ関係があります。
P と R をくっつけた符号 F の7bitの符号それぞれを、左から順に \(x_1\)～\(x_7\) と書くことにします。
前項で見たように、一般の情報源符号は4つの基本パターンの情報源符号の「足し算」で、検査符号も同様です。
しかし、\(x_5\) に限って言えば、無視できるものもあります。
表1 を縦に見ると、R の一番左の桁 \(x_5\) は P が 1000, 0100, 0010 のときに 1 で、0001 のときには 0 です。
つまり、上の3つの行だけを考えればいいことになります。
\(x_6, x_7\) についても同様に考えると、以下の関係が得られます。これらはいつでも成り立ちます。
数学の用語では、こういうものを「恒(つね)に成り立つ等式」という意味で
恒等式 と呼びます。
\(x_5=x_1\oplus x_2\oplus x_3\cdots(1)\)
(1)～(3) はいつでも成り立つはずなので、誤り訂正に使えます。
例えば受信側で F' = 1011110 を受け取ったとすると、(1)～(3)式の右辺は
\(x_1\oplus x_2\oplus x_3 = 1\oplus 0 \oplus 1 = 0\)
ですが、F' のうち検査符号に対応する部分は R' = 110 なので、(1), (2)式が成り立ちません。
7つの符号のうち1つだけが変化したと仮定すれば、この情報だけから変化したものを特定できます。
(3)式は成り立っているので \(x_1, x_2, x_4, x_7\) は正しく、残りの \(x_3, x_5, x_6\) のうち (1), (2)式の両方に含まれるものは \(x_3\) だけです。
つまり、「10
1 1110」はもともと「10
0 1110」だったということがわかります。
(1)～(3) は G = 1011 のときに限って成り立つものであることに注意してください。
G が変われば 1000～0001 に対応する R も変わります。たとえば G = 1101 なら
表2
P
R
1000
110
0100
011
0010
111
0001
101
となり、恒等式はこのようになります。
\(x_5=x_1\oplus x_3\oplus x_4\cdots(4)\)
\(k=4\), G = 1011 として検査符号を追加したものとし、受信側で F' =
を受け取った場合の誤り訂正を行い、情報源符号 P を書いてください。
ただし、F' には 1か所だけ変化した符号が含まれています。
課題2解説
\(k=4\), G = 1101 として検査符号を追加したものとし、受信側で F' =
を受け取った場合の誤り訂正を行い、情報源符号 P を書いてください。
ただし、F' には 1か所だけ変化した符号が含まれています。
課題3解説
※ G が課題2とは異なることに注意してください。使うのは(4)～(6)式です。