今回は実用的な符号である巡回符号を学びましたが、多項式表現に手こずった人、符号のエレガントさに感心した人など様々だったと思います。 最小ハミング距離の求め方では、CRC-16-CCITTの生成多項式の説明の通りに賢く求めている人が結構いて、ちゃんと勉強してくれているなと感心しました。 また、オプション問題は巡回符号の誤り訂正法で、これはスライドでは説明していないところだったのですが、とても賢い方法で解いている人が何人もいて、 正解を導いた人数も、解答の質も予想以上でした。
情報ビットは自由に決められるので、情報ビット数\(k\)を求めれば、２元符号であれば符号語数\(M\)は\(2^k\)となります。 この問題は情報ビット数が3なので、符号語数は8となります。周期が7、符号長が7なので、そこから考えたのか符号語数を7と答えた人が意外と多かったです。 専門用語は正しく覚えることが重要です。符号語の集合が符号で、符号長は各符号語の長さです。
巡回符号は線形符号なので、最小ハミング距離は最小ハミング重みに一致します。0000000以外の符号語をすべて書き出し、その中で1の個数が最も少ない符号語の1の数が最小ハミング重みであるので、最小ハミング距離もその値になります。だた、スライド10ページの定理より、符号長が周期以下であれば最小距離は３以上であることがわかり、スライド16ページの議論と全く同じ議論により、すべての符号語のハミング重みが偶数であること、しかもハミング重みがちょうど４の符号語が存在することがわかります。そこから最小ハミング重みが４、つまり最小ハミング距離が４ということが導かれます。
巡回符号の誤り訂正法に関しては、スライドで説明しませんでした。説明しないものを何故出したかというと、このレポートの(6)まで解けた人なら正しい答えを導けるからです。符号の最小ハミング距離は4です。これは、どの符号語も他の符号語と4ビット以上違っていることを意味します。ということは、どの符号語を送っても１ピットの誤りが生じた受信語を受け取った場合には、その受信語と送信語の違いは１ビットですが、他の符号語との違いは3ビット以上あるので、符号語の中から送信語を同定することが可能です。符号語は８つしかないので、全部書き出して１ビット違いのものを見つけてくれれば良いと思ったのですが、もっと賢い方法で解いている人が何人もいました。一番簡単な方法は受信語1011011に対応する多項式\(x^6+x^4+x^3+x+1\)を\(G(x)=x^4+x^2+x+1\)で割った余りを計算すると\(x^2+x+1\)であり、\(G(x)\)で割り切れるためには\(x^4\)足りないので、元の多項式に\(x^4\)足した式\(x^6+x^4+x^3+x+1+x^4=x^6+x^3+x+1\)であれば\(G(x)\)で割り切れる、つまりそれは符号語である。その符号語1001011は受信語とちょうど１ビット違いなので、それが送信語であるというものです。この方法は、\(x^i\)を足したときに割り切れるかチェックしなければならないので、\(i=6\)とか\(i=5\)の場合は、少し面倒にはなりますが、正解を導くことができます。何人かの人が使っていたもう１つの賢い方法は、ちょっと似ていますが、\(x^i\)を\(G(x)\)で割った余りを\(i=1,2,3,4,5,6,7\)について求め，その中から余りが同じ\(i\)をみつければ，\(x^i\)に対応するビットが誤りであるという方法です。受信語は符号語に誤りパターンが加わったものです。それは多項式表現でも変わらず、受信語の多項式は符号語の多項式と誤りパターンの多項式を足したものです。従って、受信語の多項式を\(G(x)\)で割った余りは、符号語の多項式を\(G(x)\)で割った余りと誤りパターンの多項式を\(G(x)\)で割った余りの和になります。符号語の多項式は\(G(x)\)で割り切れますから、受信語の多項式を\(G(x)\)で割った余りは誤りパターンの多項式を\(G(x)\)で割った余りと等しくなります。従って１ビットの誤りの７つの誤りパターンの多項式を\(G(x)\)で割った余りと比較して同じものを探すとどの１ビット誤りのパターンなのかわかることになります。 それから、送信語は符号語全体です。情報ビットのみ書いている人がいましが、それは誤りです。
確かに慣れていない概念や計算に戸惑ったかもしれませんが、非常に良くできている理論ですので、繰り返し読んだり聞いたりして勉強すれば必ず理解できると思います。
不安なところは質問してください。質問するためには、何がわからないのかはっきりさせる必要がありますが、そのプロセスを行うことにより、質問する前にわかることもあります。
コロナ禍、猛暑の中、最後まで受講ありがとうございます。期末演習で皆さんの成果が見られること、楽しみにしております。
2020.8.5 作成，担当：中村