今回はハミング符号と、符号の最小ハミング距離と限定距離復号法の誤り訂正・検出能力について学びました。 パリティ検査方程式やシンドロームの定義をしっかりと理解することが重要です。言葉の理解が曖昧な人、定義を見直して正しく理解するように努めましょう。
答えとしては、\(\{0,1\}\)-系列\(w_1w_2w_3w_4w_5w_6w_7\)に対するパリティ検査方程式は \[ \left\{\begin{array}{ccccccccc} w_1& +w_2& +w_3&&+w_5& & &=&0\\ &w_2& +w_3& +w_4&&+w_6& & =&0\\ w_1& +w_2&& +w_4&&&+w_7&=&0 \end{array}\right. \] である、というようなものを期待したのですが、「この符号の」という言葉を「この符号語の」と捉えて(1)の答えの符号語をこの方程式に入れた式を答えた人が多かったです。符号は符号語の集合です。前回のコメントの繰り返しになりますが、方程式といったら、変数がある式を書きましょう。また、\(x_1,x_2,x_3,x_4,c_1,c_2,c_3\)の式で書いている人も多かったです。パリティ検査方程式は何のための式でしょうか？記号(ビット)列が符号語であるか否かを検査するための式です。この目的のためには、与えられた長さ７の記号列列を，最初の４記号と残りの３記号で分ける意味はありません。
まず、シンドロームは、パリティ検査方程式の左辺に受信語の系列を代入したの値のベクトルです。
パリティ検査方程式が連立方程式である場合は、複数の値からなるベクトルになりますので、注意しましょう。
最初に習った単一パリティ検査符号のパリティ検査方程式が１本だったので、シンドロームも１つの値からなると思っている人も数名いるようですが、
そうではありませんので、正しく理解してください。
それからこれも前回ノートでも書きましたが、シンドロームは受信語のみで計算しますが、結果的に誤りパターンのみ入れて計算した値と一致します。
誤りパターンは説明のために導入したもので、実際の計算では、ただ、そのまま受信語の値を入れて計算すれば問題ありません。
もう1つ気をつけて欲しいのは、ハミング符号は一意に定まらず複数存在するということです。
答えの中には、教科書のシンドロームの計算式を用いた人がいましたが、教科書で説明に使ったハミング符号とこの演習の定義では検査ビットの作り方が異なります。
検査ビットの異なるハミング符号では、当然シンドロームも異なります。問題に与えられたハミング符号の定義に従ってシンドロームを計算してください。
これも前回のノートに書いたことの繰り返しになりますが、良くできていたのですが「情報ビット」ではなく「送信した符号語」を答えている人が多かったです。 「情報ビット」は最初の４ビットのみなので、答えはその４ビットとなります、
「訂正できるビット数を最大にとった場合に何ビットの誤りが確実に検出できるか」という問いに対して、「訂正」は「検出」を含むとして答えた人と、含まないとして答えた人の両方がいました。 復号領域の受信語を受け取り、それが符号語ではない場合訂正し、検出領域(復号領域の外）の受信語を受け取った場合検出を行います。 つまり、復号対象と検出対象は異なります。この問題では、検出対象の受信語のみ検出する場合、何ビットの誤りであれば確実に検出できるかを尋ねています。 スライドの説明に従って解くと、\(t_2=0\)になるから、訂正できないが検出可能な誤りビット数\(t\)の範囲\(t_1+1\le t \le t_1+t_2\)が空集合になってしまうので 「確実に検出できる誤りビット数はない」が正解です。 具体的に考えて見ましょう。最小距離にある２つの符号語を\(w_0\)と\(w_1\)し、\(w_0\)が送信された場合を考えます。訂正できるビット数の最大は１なので、１ビットの誤りのみ訂正するとすると、\(w_0\)を送って1ビットの誤りが生じた場合は正しく復号されますが、2ビットの誤りが生じた場合には、最小距離が３なので\(w_1\)と1ビット違いになっている場合があります。この場合は\(w_1\)が送信されたものだと解釈され間違った復号が行われることになります。従って、２ビットの誤りは、検出できないものが存在するということになります。
(9,4)組織符号である水平垂直パリティ検査符号の最小ハミング距離は4であり、これはハミング符号の3より大きな数字ですが、この１大きい最小ハミング距離のおかげでハミング符号より誤り検出能力に優れています。ただ、効率が4/9であり、情報ビット長4に対して検査ビット長5で冗長度が高く、情報速度が遅いという欠点があります。これはこれ以上改善できないのでしょうか？その質問の答えがこの問題となります。最小ハミング距離４で効率がもっと良い(8,4)組織符号である線形符号が存在します。その符号の検査行列を求めてくださいという問題でした。情報ビット列を\(x_1x_2x_3x_4\)、それに加える検査ビット列を\(c_1c_2c_3\)とすれば、加える検査ビット\(c_4\)は \[c_4=x_1+x_2+x_3+x_4+c_1+c_2+c_3\] となります。組織符号・線形符号の場合は検査ビットは情報ビットのみから計算できなければなりません。 この場合は、\(x_1x_2x_3x_4c_1c_2c_3\)はハミング符号の符号語なので、\(c_1, c_2, c_3\)は\(x_1, x_2, x_3, x_4\)の線形式でかけます。 結局\(c_4\)も\(x_1, x_2, x_3, x_4\)の線形式でかけることになります。そのように変形してから、パリティ検査方程式を書いて、それに対応する検査行列に変換することにより、こちらが期待する答えに辿りつきます。
その通りです。「2〜3個を検出可能」と書いてある場合でも4個以上の誤りが検出できる場合があります。実際、単純な単一パリティ検査符号の場合、奇数個の誤りはどんなに数が多くても全て検出可能です。
\(t_2=0\)の場合、確かにそうなります。符号語からハミング距離が\(t_1\)以下の領域を復号領域として訂正する方法に関する説明であり、復号領域に入るものは誤りの検出は行いません。 ですから、満たす値が存在しない場合は、「確実に検出できる誤りビット数はない」ということになります。
まず、言葉の使い方ですが、符号の効率は水平垂直パリティ検査符号が4/9、ハミング符号が4/7なのでハミング符号の方が良いです。質問の意図は、行列で扱うと、0を省略できないので余分な領域や計算が必要になるのではないかということだと思いますが、実は線形符号であれば、全て行列で計算できますので、水平垂直パリティ検査符号も行列で計算することができます。水平垂直パリティ検査符号の方が生成行列も検査行列も大きくなりますし、行列を使わずに計算しても水平垂直パリティ検査符号の方が計算が簡単であるとは言えないと思います。大きいのは、やはり効率で、４ビットの情報を送るのにハミング符号であれば、7ビット送れば良いものを水平垂直パリティ検査符号だと9ビットも送らなければならないことが大きいと思います。実は、最終回の巡回符号は、行列計算よりも効率的な多項式の割り算を用いて符号化や誤り検出を行うことができる符号です。
内容を理解すれば解ける基本問題を出しているつもりです。内容の理解ができないところがあったらスラックで質問してください。
解答の公開はしませんが、よくある間違いはノートに挙げてあるので、自分がそれにあてはならないかチェックしてください。
今の学生さんは、行列を習わずに大学に入学してくるのですよね。行列演算や行列表現はよく使われるので慣れることは重要だと思います。
2020.8.4 作成，担当：中村