巡回符号について

質問

以下の問題についてお解りになる方、どうかご教授お願いします。
なるべく文章で表現したつもりですが、実際には図を見て回答するため、これだけではわからない！となるかもしれません。

問題

符号長７の二元巡回（７，４）の符号器を使用する。
この時、巡回符号の生成多項式を

g(x) = x^3 + x + 1

とする。

問題１
情報桁を表す多項式が　x^2 + x +1 　であるとき
符号器が出力する符号多項式はどのようなものか。

問題２
この巡回符号のパリティ検査行列を求めよ。

問題３
この巡回符号の符号語を送信したとき、
受信多項式　y(x)　が　x^5 + x^4 + x^3 + x^2 +1
であるとする。この受信多項式y(x)の誤りを訂正せよ。

回答No.3

info22 · ベストアンサー

ネット上には巡回符号のことは書かれていますが
内容が難しく書かれているわりに実際に適用する方法が明快に書かれていない。問題だけで回答例がない。検査行列の作り方が書かれていない。
誤り訂正の例題が書かれていないので実際の誤り訂正の仕方が分からない。検査行列を求める前のg(x)で割り切れれば受信データは正しい（誤りなし）。割り切れなければ誤りありと判断する。という所まで書いてあって誤り訂正可能、しかしその仕方が書いてない。といった解説が多いですね。
今回のケースを考察してまとめると

検査行列H=
[1 0 1 1 1 0 0]
[1 1 0 1 0 1 0]
[0 1 1 1 0 0 1]

送信データX=[0111001]
２ビットのエラー発生して
受信データY=[0101101]
となった場合を考えると
誤りベクトルY・H~=[0 0 1]
これは検査行列Hの７列目に一致する。
誤りがない場合は誤りベクトルは[0 0 0]となるので誤りありと判定される。
受信データYに１ビットだけの誤りが含まれるなら
誤り訂正されたY'=[0101100]は正しい送信データとして判断してよい。
しかし２ビットの誤りが含まれている今回のケースでは
訂正された復号化されたデータY'[0101100]は正しい送信データと一致して
おらず正しく訂正されません。

つまり符号長７の二元巡回（７，４)符号のパリティチェックでは
誤りベクトルから判ることは次のことです。
■[0 0 0]→誤りなしで受信データは正しい。
■[0 0 0]以外→誤りあり、１ビットの誤りは訂正できる。２ビット以上の誤りは訂正できない。

お礼

教科書を見ても長い式がただ羅列しているので、時間に余裕がない私は
例題を解いて問題になれようと考えました。しかしinfo22様がおっしゃる通りネットでも
なかなか巡回符号の例題とその解答が見つかりませんでした。
ハミング距離や巡回符号の定義等を細かく自分で証明していき、
基本的な事項を理解すれば例題がなくても問題が解けるのでしょうが。

amazon等で何冊か符号の専門書を購入しましたが、やはり例題数が少なく私が最も知りたい「実際にどうやって検査するのか」等の具体例が省かれていることが多かったです。

例題まで作成して頂き、本当にありがとうございます。
専門書を何冊も読むよりはるかにinfo22様の解説の方が分かり易く、
実際に使えそうな知識として習得することができました。

お忙しい中、時間を割いていただきありがとうございました。

回答No.2

info22

#1です。
A#1の補足質問について
>問題２について
>最後の３列が単位行列ならば、そのほかの列はシャッフルしても
>可能、という事でしょうか。
４ビットの情報ビット列全ての組合せ（16通り）について生成多項式g(x)に対して、R(x)を求めて巡回符号を作って、最後の3ビットが単位行列が単位行列になるものをピックアップしてパリティ検査行列Hを作ります。

>H~ は　H の転置行列という意味でしょうか？
転置行列の意味で使っています。本来はHの肩に小さなTを書く代わりに簡便に書きました。

>>誤りベクトル=Y・H~=[1 0 0]
この通りです。
>転置行列として計算した場合、
>Y・H~=[1 1 1]
こうなりません。
計算過程が書いてありませんので計算の間違いの理由が分かりません。
計算は(行)・(列）の計算は要素のAND計算（積でも同じ）した後、それらを排他的論理和で計算します。つまり1の数が偶数であれば0,1の数が奇数であれば1になります。
そうすれば正しい誤りベクトル[1 0 0]が計算できるはずです。

お礼

度重なる質問に迅速にお答えいただき、ありがとうございます。

>４ビットの情報ビット列全ての組合せ（16通り）について生成多項式g(x)に対して、R(x)を求めて巡回符号を作って、最後の3ビットが単位行列が単位行列になるものをピックアップしてパリティ検査行列Hを作ります。

なるほど、このような検査行列の求め方があったのですね。
私は生成多項式 g(x)　の関係から　 a を代入し

a^3 + a +1 =0

から

1 = 1
a = a
a^2 = a^2
a^3 = a +1
a^4 = a^2 +a
a^5 = a^2 +a +1
a^6 = a^2+1

0 0 1
0 1 0
1 0 0
0 1 1
1 1 0
1 1 1
1 0 1

と係数よりパリティ検査行列を求める方法しか知りませんでした。
info22様の方法の方がスマートに計算できますね。
問題集などでは１つの答えしか掲載されていない事が多く、これであっているのかと不安でした。詳細にお答えいただきありがとうございます。

>　>Y・H~=[1 1 1]
>　こうなりません。
>　計算過程が書いてありませんので計算の間違いの理由が分かりません。

大変失礼いたしました。
計算し直した結果、info22様のおっしゃる通り
Y・H~=[1 0 0] となりました。
どうやら、行列の積と排他的論理和の計算の際に計算の手順を
間違えていたようです。

とある試験でこの分野から問題が出題されるのですが私にとって全くunfamiliarな分野で、かつ試験が迫っていますのでinfo22様からの解説はとても有難く、参考になりました。

お忙しいところ、ありがとうございました。

回答No.1

info22

問題１
＞符号長７の二元巡回（７，４）
符号長n=7,情報ビット数m=4,n-m=3
＞g(x) = x^3 + x + 1
＞x^2 + x +1 =P(x)
P(x)x^3=x^6+x^5+x^4=g(x)Q(x)+R(x)
=(x^3+x+1)(x^3+x^2)+x^2
Q(x)=x^3+x^2, R(x)=x^2
巡回符号の符号多項式
F(x)=P(x)x^3+R(x)=x^6+x^5+x^4+x^2

問題２
パリティ検査行列Hは3行7列の行列で
全ての列が異なり、列の全ての要素がゼロでないこと。最後の3列は単位行列であること。これらの条件を満たす検査行列Hは次の通り。
H=
[1 0 1 1 1 0 0]
[1 1 0 1 0 1 0]
[0 1 1 1 0 0 1]

問題３
＞受信多項式 y(x)　が　x^5 + x^4 + x^3 + x^2 +1
受信データY=[0111101]
誤りベクトル=Y・H~=[1 0 0]
これがH行列の前から5列目と一致する。
したがって受信データYの前から5ビット目がエラー。
5ビット目を反転させて誤り訂正する。
訂正後のY=[0111001]
正しい受信多項式はx^2の係数を反転させて
y(x)=x^5 + x^4 +x^3 + 1
となる。

お礼

詳細な解説ありがとうございます！！

問題１については、実際に計算して確認できました。
ご丁寧に途中の計算式まで書いて頂き、ありがとうございます。

問題２について
最後の３列が単位行列ならば、そのほかの列はシャッフルしても
可能、という事でしょうか。

問題３について
私の理解力が足りなく、まだわからない状態です。

>誤りベクトル=Y・H~=[1 0 0]

の　　H~ は　H の転置行列という意味でしょうか？
転置行列として計算した場合、
Y・H~=[1 1 1]

と、なってしまいます。