巡回符号

巡回符号（じゅんかいふごう、英: Cyclic code）は、符号理論における誤り訂正符号の一種である。

概要

巡回符号の定義は以下の通りである。

n個のシンボルで構成されるある線形符号の符号語として (c0 , c1 , ... , cn-2 , cn-1 ) があるとする。この符号語を巡回シフトさせたもの(cn-1 , c0 , c1 , ... , cn-2 ) が、やはりその線形符号の符号語である場合、その線形符号を巡回符号という。

巡回符号は一般に符号語を符号語多項式で表す。これは例えば上記の符号語を

C ( x ) = c n − 1 x n − 1 + c n − 2 x n − 2 + ⋯ + c 1 x + c 0 {\displaystyle C(x)=c_{n-1}x^{n-1}+c_{n-2}x^{n-2}+\cdots +c_{1}x+c_{0}}

というように符号語を (n-1)次の多項式で表現する方法である。なおこの式は加算を排他的論理和で表す GF(2n-1)の拡張ガロア体上の多項式である事に注意する。特に a + b と a - b は基本的に同じ事を意味する。

巡回符号は以下のようにして作成される。まず n > m であり、 xn - 1 を割り切ることのできる m次の多項式

G ( x ) = x m + g m − 1 x m − 1 + ⋯ + g 1 x + g 0 {\displaystyle G(x)=x^{m}+g_{m-1}x^{m-1}+\cdots +g_{1}x+g_{0}}

を考える。このとき、(n-m-1) シンボルの情報を符号語多項式で表したものを I(x) と置いて G(x) と I(x) の積で表される n-1次の多項式

C ( x ) = I ( x ) × G ( x ) {\displaystyle C(x)=I(x)\times G(x)}

を符号語とする。この C(x)は必ず巡回符号の定義を満たすことが知られている。これは以下のように証明できる。

まず定義より xn - 1 は G(x)で割り切れるので

x n − 1 = G ( x ) × P ( x ) {\displaystyle x^{n}-1=G(x)\times P(x)}

で表すことが出来る。今 C(x)の多項式を

C ( x ) = c n − 1 x n − 1 + c n − 2 x n − 2 + ⋯ + c 1 x + c 0 {\displaystyle C(x)=c_{n-1}x^{n-1}+c_{n-2}x^{n-2}+\cdots +c_{1}x+c_{0}}

で表すとする。このときこの多項式を巡回シフトさせた多項式 C'(x) を考えると、

C ′ ( x ) = c n − 2 x n − 1 + c n − 3 x n − 2 + ⋯ + c 1 x 2 + c 0 x + c n − 1 {\displaystyle C'(x)=c_{n-2}x^{n-1}+c_{n-3}x^{n-2}+\cdots +c_{1}x^{2}+c_{0}x+c_{n-1}}

で表される。この式を C(x) との関係で表すと、

C ′ ( x ) = x × C ( x ) + c n − 1 − c n − 1 x n = x × C ( x ) − c n − 1 ( x n − 1 ) {\displaystyle C'(x)=x\times C(x)+c_{n-1}-c_{n-1}x^{n}=x\times C(x)-c_{n-1}(x^{n}-1)}

となる。 ここで C(x) = I(x) × G(x) である事と xn - 1 と G(x)との関係式より上記の式は

C ′ ( x ) = x × C ( x ) − c n − 1 ( x n − 1 ) = ( x ⋅ I ( x ) − c n − 1 P ( x ) ) × G ( x ) {\displaystyle C'(x)=x\times C(x)-c_{n-1}(x^{n}-1)=(x\cdot I(x)-c_{n-1}P(x))\times G(x)}

となり、この式も最初に定義した C(x) と同様の式で表すことが出来る。すなわちこの符号化は巡回符号であることが分かる。このときこの G(x) は生成多項式と呼ばれる。巡回符号の定義から、もとの符号語多項式を n 回巡回シフトした場合、もとの符号語多項式に戻ることは自明である。このとき元に戻るまでに n-1 個の符号語が現れることになるが、この符号語が全て相違になるような符号を生成する生成多項式を特に原始多項式と呼ぶ。

このようにして、巡回符号は単純な多項式同士の積で表すことができるが、この場合 C(x)は必ずしも組織符号（符号語の前半部分の係数が I(x) の係数と一致する符号）であるとは限らない。そこで一般には以下のような方法で符号化される。まず情報多項式 I(x) と xn-m との積を求める。この式を 生成多項式 G(x)で割った商を Q(x)、余りを R(x) と置けば、

I ( x ) × x n − m = Q ( x ) × G ( x ) + R ( x ) {\displaystyle I(x)\times x^{n-m}=Q(x)\times G(x)+R(x)}

で表すことが出来る。よって

C ( x ) = Q ( x ) × G ( x ) = I ( x ) × x n − m + R ( x ) {\displaystyle C(x)=Q(x)\times G(x)=I(x)\times x^{n-m}+R(x)}

とすることで、I(x) の組織符号となる巡回符号を定義することが出来る。

巡回符号の最大の利点は、単純なシフトレジスタ回路を用いて符号化が可能な事である。例えばハミング符号では符号語は情報ベクトルと生成行列の積で表されるが、この場合は符号長が長くなるにつれ回路の規模が加速度的に大きくなる。それに対し、上記の組織符号を満たす巡回符号の場合はI(x) × xn-m（これは実際には I(x) をシフトするだけである）を G(x) で割った余りを求める除算回路を1つ用意し、その結果を I(x) の後ろに添付するだけで実装することができる。

他の符号との関連

単一パリティビット

各多項式の係数を 1 と 0 のみとし生成多項式を G(x) = x + 1 とする時、任意の n で

x n − 1 = x n + 1 = ( x + 1 ) ( x n − 1 + x n − 2 + ⋯ + x + 1 ) {\displaystyle x^{n}-1=x^{n}+1=(x+1)(x^{n-1}+x^{n-2}+\cdots +x+1)}

となり巡回符号の条件を満たす。I(x) を G(x) で割った時、多項式の項の数が偶数なら余りは 0、奇数なら余りは 1 になる。よって上記の組織符号の公式で符号化すると、生成される符号は全て係数が1の項が偶数個になるので、これはevenのパリティビットを付加したコードであることを意味している。すなわちパリティビットは巡回符号のサブセットである。

ハミング符号

ハミング符号は必ずしも巡回符号ではないが、ある種のハミング符号は巡回符号の定義を満たすことが知られている。この符号のことを特に 巡回ハミング符号 と呼ぶ。巡回ハミング符号の生成行列を生成多項式で表した場合、 G(x) は m次の原始多項式であることが知られている。

BCH 符号とリード・ソロモン符号

BCH符号は m次の原始多項式を1つ選び、その根を αとし、αi を根とする多項式の内、最小の次数を持つものを Mi(x) で表したとき、 t個の誤りを訂正する生成多項式を

G ( x ) = L C M ( M l 0 ( x ) , M l 0 + 1 ( x ) , … , M l 0 + 2 t − 2 ( x ) ) {\displaystyle G(x)=LCM\left(M_{l_{0}}(x),M_{l_{0}+1}(x),\dots ,M_{l_{0}+2t-2}(x)\right)}

で表す巡回符号である。ここで LCMは 最小公倍多項式を意味する。すなわち G(x) は Ml0(x) 〜 Ml0 + 2t - 2(x) で割り切れる最小の次数をもつ多項式である。

リード・ソロモン符号は生成多項式だけでなく多項式の係数にも拡張ガロア体を用いた特殊な BCH符号であるため、やはり巡回符号の一種である。同様にαを用いて tシンボルの誤りを訂正する生成多項式は以下のようになる。

G ( x ) = ∏ i = b 2 t − 1 + b ( x − α i ) {\displaystyle G(x)=\prod _{i=b}^{2t-1+b}(x-\alpha ^{i})}

関連項目

参考文献

  • 江藤良純、金子敏信、『誤り訂正符号とその応用』、オーム社、1996年、ISBN 4-274-03486-0
  • J.ユステセン、T.ホーホルト、『誤り訂正符号入門』、阪田省二郎、栗原正純、松井 一、藤沢 匡哉 訳、森北出版、2005年、ISBN 4-627-81711-8
  • 笠原正雄、佐竹賢治、『誤り訂正符号と暗号の基礎数理』、コロナ社、2004年、ISBN 4-339-01054-5
  • 表示
  • 編集