例題で学ぶ符号理論入門の勉強メモ

$${GF(2^m)}$$の原始元を$${\alpha}$$、その最小多項式を$${g(x)}$$とする。$${g(x)}$$を生成多項式とする巡回ハミング符号の復号を考えてみる。

送信された符号語は、通信路において誤りがくわわり受信される。受信後の多項式表現を受信多項式といい$${v(x)}$$で表す。誤りの多項式表現を誤り多項式といい$${e(x)}$$で表す。符号多項式を$${w(x)}$$とすると、

$$
v(x) = w(x) + e(x)
$$

が成り立つ。この式に$${\alpha}$$を代入すると、$${w(x) = a(x)g(x)}$$だから$${w(\alpha) = 0}$$。よって$${v(\alpha) = e(\alpha)}$$となる。この$${v(\alpha)}$$をシンドロームといい、$${S}$$で表す。

$$
S = v(\alpha)
$$

符号長$${n = 2^m-1}$$とし、 $${e(x) = e_0 + e_1x + \cdots + e_{n-1}x^{n-1}}$$する。$${\alpha}$$を代入すると$${e(\alpha) = e_0 + e_1\alpha + \cdots + e_{n-1}\alpha^{n-1}}$$。
単一誤りがある場合、$${i}$$ビット目にエラーがあるならば$${e_i = 1, e_j = 0(j \neq i)}$$となり、$${e(\alpha)=\alpha^i}$$。すなわち、シンドロームは

$$
S = v(\alpha)=e(\alpha)=\alpha^i
$$

したがって、復号方法は以下である。

1. シンドロームを計算して、$${\alpha}$$のべきと比較する

2. $${\alpha^i}$$に等しい時、$${i}$$ビット目にエラーがあることが分かる。

3. 受信語の$${i}$$ビット目を反転する。

例題6.1 $${GF(2^3)}$$の原始元$${\alpha}$$の最小多項式を$${x^3+x+1}$$とする。この最小多項式を生成多項式とする(7,4,3)巡回ハミング符号において、単一誤りがあるとして、誤り位置とシンドロームSの対応表を求めよ。

解答

誤り位置：Sで列挙してくと
誤りなし：0
0:1
1:$${\alpha }$$
2:$${\alpha^2 }$$
3:$${\alpha^3 }$$
4:$${\alpha^4 }$$
5:$${\alpha^5 }$$
6:$${\alpha^6 }$$