BCH符号を作ろう

例題で学ぶ符号理論入門の勉強メモ
BCH符号は、巡回符号の最小距離が生成多項式の連続根の数で決まることに出発して以下のように作られる。

BCH符号の作り方

$${\alpha}$$を$${GF(2^m)}$$の原始元とする。
t誤り訂正可能な符号が欲しい時は、生成多項式$${g(x) = LCM\lbrace M_1(x), M_2(x), \cdots, M_{2t}(x) \rbrace }$$とする。ただし$${M_i(x)}$$とは、$${\alpha^i}$$の最小多項式であり、LCMとは最小公倍多項式をとることを意味する。
符号長nは$${2^m-1}$$の約数で与えられ、特に$${n=2^m-1}$$ならば原始BCH符号という。情報多項式次数k = n - degg(x)である。

注意：g(x)の次数=連続根の数ではない。例題3.18でやったように、共役根すべてで$${(x-\beta^{2^i})}$$の積を取ったものが$${\beta}$$の最小多項式になるので、共役根の数の和が次数になる。

例題5.1意訳 $${\alpha}$$を$${GF(2^4)}$$の原始元とする。t=1,2,3のt重誤り訂正が可能な原始BCH符号について、以下を求めよ。生成多項式g(x)、情報ビット数k、設計距離d

解答 符号長nは$${2^4-1 = 15}$$。$${M_i(x)}$$を$${\alpha^i}$$の最小多項式とする。$${\alpha}$$は原始多項式$${x^4 + x + 1}$$の根であるとする。

t=1では2個の連続根があれば、設計距離(最小距離)が3になって1誤り訂正可能。よって、$${\alpha, \alpha^2, \alpha^4, \alpha^8}$$($${\alpha, \alpha^2}$$が連続根)の最小多項式$${M_1(x) = (x- \alpha)(x-\alpha^2)(x- \alpha^4)(x- \alpha^8)}$$が生成多項式となる。deg g(x) = 4だからk = 15-4=11。

t=2では、4個の連続根があれば、dが5になって2誤り訂正可能。$${\alpha^3 }$$の共役元$${\alpha^3 ,\alpha^6, \alpha^{12}, \alpha^9}$$の最小多項式$${M_3(x) = (x- \alpha^3)(x-\alpha^6)(x- \alpha^9)(x- \alpha^{12})}$$を加えて$${g(x) = LCM\lbrace M_1(x), M_3(x)\rbrace}$$とすれば$${\alpha, \alpha^2, \alpha^3, \alpha^4}$$が連続根となる。kはn - degg(x) = 15 - 8 = 7。

t=3では、6個の連続根があれば、dが7になって3誤り訂正可能。$${\alpha^5}$$の共役元$${\alpha^5 ,\alpha^{10}}$$の最小多項式$${M_5(x) = (x - \alpha^5)(x - \alpha^{10})}$$を加えて$${g(x) = LCM\lbrace M_1(x), M_3(x), M_5(x)\rbrace}$$とすれば$${\alpha, \alpha^2, \alpha^3, \alpha^4, \alpha^5, \alpha^6}$$が連続根となる。kはn - deg g(x) = 15 - 10 = 5。

t=2の時点で、情報ビットよりパリティの方が大きいから、伝送路のFECに使うなら転送効率50%以下になって使い物にならない。これはmが小さすぎるからで、実際はもっと大きいものが使われる。