巡回コード

Type of block code

符号理論において、巡回符号はブロック符号の一種であり、各符号語の巡回シフトによって、その符号に属する別の語が生成される。巡回符号は、効率的な誤り検出と訂正に便利な代数的性質を持つ誤り訂正符号である。

00010111 が有効なコードワードである場合、右循環シフトを適用すると文字列は 10001011 になります。コードが循環的である場合、10001011 は再び有効なコードワードになります。一般的に、右循環シフトを適用すると、最下位ビット (LSB) が左端に移動され、最上位ビット (MSB) になります。他の位置は 1 ずつ右にシフトされます。

意味

をブロック長の有限体（ガロア体とも呼ばれる）上の線形符号とします。が巡回符号と呼ばれるのは、の任意の符号語に対して、 の要素を巡回右シフトすることによって得られるの語が再び符号語となるときです。1回の巡回右シフトは巡回左シフトに等しいため、巡回符号は巡回左シフトによっても定義できます。したがって、線形符号が巡回符号であるとは、すべての巡回シフトに対して不変であることを意味します。 ${\displaystyle {\mathcal {C}}}$ ${\displaystyle GF(q)}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle c=(c_{1},\ldots ,c_{n})}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle (c_{n},c_{1},\ldots ,c_{n-1})}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle n-1}$ ${\displaystyle {\mathcal {C}}}$

巡回符号には、いくつかの追加の構造的制約があります。巡回符号はガロア体に基づいており、その構造的性質により誤り制御に非常に有用です。巡回符号の構造はガロア体と密接に関連しているため、巡回符号の符号化および復号化アルゴリズムは計算効率に優れています。

代数構造

巡回符号は、特定の環のイデアルに関連付けることができます。 を 有限体 上の多項式環の商とします。巡回符号の元を、多項式 にマップされる の 多項式 と同一視します。したがって 、 による乗算は巡回シフトに対応します。するとは のイデアルとなり、 は主イデアル環であるため、主となります。イデアルは、最小次数である の唯一のモニック元、つまり生成多項式によって生成されます。^[1]これは の約数でなければなりません。したがって、すべての巡回符号は多項式符号となります。生成多項式の次数が の場合、符号の階数は です。 ${\displaystyle R=A[x]/(x^{n}-1)}$ ${\displaystyle A=GF(q)}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle R}$ ${\displaystyle (c_{0},\ldots ,c_{n-1})}$ ${\displaystyle c_{0}+c_{1}x+\cdots +c_{n-1}x^{n-1}}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle g}$ ${\displaystyle x^{n}-1}$ ${\displaystyle g}$ ${\displaystyle d}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle n-d}$

が巡回符号である場合、双対符号も巡回符号となる。 の生成多項式は、パリティチェック多項式、あるいは単に のチェック多項式とも呼ばれる。 であることも示され、ここで はの逆数多項式を表す。^[2] ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}^{\perp }}$ ${\displaystyle h(x)}$ ${\displaystyle {\mathcal {C}}^{\perp }}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle g(x)h^{*}(x)=x^{n}-1}$ ${\displaystyle h^{*}(x)}$ ${\displaystyle h(x)}$

のべき等元とは、（つまり、はのべき等元）となる符号語であり、符号の恒等元であり、すべての符号語 に対してとなる。と が互いに素であるならば、そのような語は常に存在し、一意である。^[3]それは符号の生成元である。 ${\displaystyle {\mathcal {C}}}$ ${\displaystyle e}$ ${\displaystyle e^{2}=e}$ ${\displaystyle e}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle e}$ ${\displaystyle e\cdot c=c}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle q}$

既約コードとは、イデアルとして既約なコード、つまり が において最小であり、その検査多項式が既約多項式 となるような巡回コードです。 ${\displaystyle R}$

例

例えば、と の場合、 によって生成される巡回符号に含まれる符号語の集合は、正確に ${\displaystyle A=\mathbb {F} _{2}}$ ${\displaystyle n=3}$ ${\displaystyle (1,1,0)}$

$${\displaystyle \{(0,0,0),(1,1,0),(0,1,1),(1,0,1)\}.}$$

このコードは、 によって生成された の理想に対応します。 ${\displaystyle \mathbb {F} _{2}[x]/(x^{3}-1)}$ ${\displaystyle (1+x)}$

多項式は多項式環において既約ではないため、コードは既約コードです。 ${\displaystyle (1+x)}$

このコードのべき等性は、コードワード に対応する多項式 です。 ${\displaystyle x+x^{2}}$ ${\displaystyle (0,1,1)}$

些細な例

巡回符号の自明な例としては、自身と、ゼロ符号語のみを含む符号が挙げられます。これらはそれぞれ生成元とに対応します。これらの2つの多項式は常に の因数でなければなりません。 ${\displaystyle A^{n}}$ ${\displaystyle 1}$ ${\displaystyle x^{n}-1}$ ${\displaystyle x^{n}-1}$

偶数重みのワードすべてからなるパリティビットコードは、生成器 に対応します。また、は常に の因数である必要があります。 ${\displaystyle GF(2)}$ ${\displaystyle x+1}$ ${\displaystyle GF(2)}$ ${\displaystyle x^{n}-1}$

その他の例

一般的に使用される多くの種類の誤り訂正符号は、BCH符号、リード・ソロモン符号、有限幾何学から定義された低密度パリティ検査符号のいくつかのクラスなど、巡回符号として表すことができます。 ^[4]

エラーを修正するには

巡回符号はハミング符号と同様に、単一誤りの訂正に使用できるため、誤り訂正に使用できます。また、二重誤りやバースト誤りの訂正にも使用できます。すべての種類の誤り訂正については、以降のサブセクションで簡単に説明します。

(7,4)ハミング符号は生成多項式を持ちます。この多項式は ガロア拡大体の原始元に零点を持ち、すべての符号語は を満たします。巡回符号は体 上の二重誤りを訂正するためにも使用できます。ブロック長はに等しく、原始元 とは の零点として扱われます。これは、ここでは2つの誤りの場合を想定しているため、それぞれが1つの誤りを表すためです。 ${\displaystyle g(x)=x^{3}+x+1}$ ${\displaystyle GF(8)}$ ${\displaystyle \alpha }$ ${\displaystyle {\mathcal {C}}(\alpha )=0}$ ${\displaystyle GF(2)}$ ${\displaystyle n}$ ${\displaystyle 2^{m}-1}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{3}}$ ${\displaystyle GF(2^{m})}$

受信語は次 式の多項式である。 ${\displaystyle n-1}$ ${\displaystyle v(x)=a(x)g(x)+e(x)}$

ここで、2 つのエラーに対応する非ゼロの係数を最大 2 つ持つことができます。 ${\displaystyle e(x)}$

シンドローム多項式を、多項式を生成多項式で割った余りとして定義する。すなわち、 ${\displaystyle S(x)}$ ${\displaystyle v(x)}$ ${\displaystyle g(x)}$

${\displaystyle S(x)\equiv v(x)\equiv (a(x)g(x)+e(x))\equiv e(x)\mod g(x)}$として。 ${\displaystyle (a(x)g(x))\equiv 0\mod g(x)}$

2つのエラーを修正するため

体要素とを2つのエラー位置番号とします。エラーが1つだけ発生した場合、は0になり、エラーが1つも発生しない場合は、両方とも0になります。 ${\displaystyle X_{1}}$ ${\displaystyle X_{2}}$ ${\displaystyle X_{2}}$

ととします。 ${\displaystyle S_{1}={v}(\alpha )}$ ${\displaystyle S_{3}={v}(\alpha ^{3})}$

これらの体元は「シンドローム」と呼ばれます。ここで、 は原始元と ではゼロなので、と と書くことができます。例えば、2つのエラーが発生した場合、 ${\displaystyle g(x)}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{3}}$ ${\displaystyle S_{1}=e(\alpha )}$ ${\displaystyle S_{3}=e(\alpha ^{3})}$

${\displaystyle S_{1}=\alpha ^{i}+\alpha ^{i'}}$そして 。 ${\displaystyle S_{3}=\alpha ^{3i}+\alpha ^{3i'}}$

そしてこれら2つは2つの未知数を持つ2組の方程式として考えることができるので、次のように書くことができる。 ${\displaystyle GF(2^{m})}$

${\displaystyle S_{1}=X_{1}+X_{2}}$そして 。 ${\displaystyle S_{3}=(X_{1})^{3}+(X_{2})^{3}}$

したがって、2 組の非線形方程式を解くことができれば、巡回コードを使用して 2 つのエラーを修正できます。

ハミングコード

ハミング(7,4)符号は、生成元が である GF(2) 上の巡回符号として表すことができます。実際、 Ham(r, 2) の形式の任意の2元ハミング符号は巡回符号と同等であり、^[5] rとq-1が互いに素である Ham(r,q) の形式の任意のハミング符号も巡回符号と同等です。^[6] が である Ham(r,2) の形式のハミング符号が与えられた場合、偶数符号語の集合は巡回-符号を形成します。^[7] ${\displaystyle 1+x+x^{3}}$ ${\displaystyle r\geq 3}$ ${\displaystyle [2^{r}-1,2^{r}-r-2,4]}$

単一エラーを訂正するためのハミングコード

最小距離が3以上のコードは、すべての列が互いに異なり、かつ非ゼロである検査行列を持ちます。バイナリコードの検査行列が行を持つ場合、各列はビットのバイナリ数です。列は複数存在し得ます。したがって、バイナリコードの検査行列が行数3以上の場合、その行は列のみを持ち、それ以上の列を持つことはできません。これはハミングコードと呼ばれるコードを定義します。 ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle 2^{m}-1}$ ${\displaystyle d_{min}}$ ${\displaystyle m}$ ${\displaystyle 2^{m}-1}$ ${\displaystyle (2^{m}-1,2^{m}-1-m)}$

サイズ の大きなアルファベットに対するハミング符号の定義は簡単です。線形独立な列を持つ行列を1つ定義する必要があります。任意のサイズのワードには、互いに倍数となる列が存在します。したがって、線形独立性を得るためには、最上位の非ゼロ要素が 1 であるすべての非ゼロ組を列として選択します。こうすることで、コードの最小距離が 3 である 3 つの列が線形従属関係にある可能性があるため、2 つの列が線形従属関係になることは決してありません。 ${\displaystyle q}$ ${\displaystyle H}$ ${\displaystyle q}$ ${\displaystyle m}$

つまり、最上位の非ゼロ要素が1である非ゼロ列が存在する。したがって、ハミング符号は符号である。 ${\displaystyle (q^{m}-1)/(q-1)}$ ${\displaystyle [(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m]}$

ここで、巡回符号について、を の原始元とし、 とします。すると、は多項式の零点となり、 はブロック長 の巡回符号の生成多項式となります。 ${\displaystyle \alpha }$ ${\displaystyle GF(q^{m})}$ ${\displaystyle \beta =\alpha ^{q-1}}$ ${\displaystyle \beta ^{(q^{m}-1)/(q-1)}=1}$ ${\displaystyle \beta }$ ${\displaystyle x^{(q^{m}-1)/(q-1)}-1}$ ${\displaystyle n=(q^{m}-1)/(q-1)}$

しかし、については となる。そして、受信語は次数 の多項式で、 次のように与えられる 。 ${\displaystyle q=2}$ ${\displaystyle \alpha =\beta }$ ${\displaystyle n-1}$

${\displaystyle v(x)=a(x)g(x)+e(x)}$

ここで、またははエラーの場所を表します。 ${\displaystyle e(x)=0}$ ${\displaystyle x^{i}}$ ${\displaystyle i}$

しかし、を の元として使ってエラー位置を示すこともできます。 なので、 となり、からまでのすべての のべき乗は互いに異なるため、 がエラーなしを表す場合を除き、 からエラー位置を簡単に特定できます。つまり、ハミング符号はと を持つ単一のエラー訂正符号です。 ${\displaystyle \alpha ^{i}}$ ${\displaystyle GF(2^{m})}$ ${\displaystyle g(\alpha )=0}$ ${\displaystyle v(\alpha )=\alpha ^{i}}$ ${\displaystyle \alpha }$ ${\displaystyle 0}$ ${\displaystyle 2^{m}-2}$ ${\displaystyle i}$ ${\displaystyle \alpha ^{i}}$ ${\displaystyle v(\alpha )=0}$ ${\displaystyle GF(2)}$ ${\displaystyle n=2^{m}-1}$ ${\displaystyle k=n-m}$

バーストエラーを修正するため

ハミング距離の概念から、最小距離を持つ符号はあらゆる誤りを訂正できます。しかし、多くの通信路では誤りパターンは必ずしも一定ではなく、メッセージの非常に短い区間内で発生します。このような誤りはバースト誤りと呼ばれます。そのため、このような誤りを訂正するには、制約が少ないため、より効率的でレートの高い符号が必要になります。巡回符号はバースト誤りを訂正するために使用されます。実際、巡回符号はバースト誤りだけでなく巡回バースト誤りも訂正できます。巡回バースト誤りは以下のように定義されます。 ${\displaystyle 2t+1}$ ${\displaystyle t}$

長さの巡回バーストは、非ゼロの成分が（巡回的に）連続する成分の中にあり、その最初と最後の成分が非ゼロであるベクトルです。 ${\displaystyle t}$ ${\displaystyle t}$

多項式形式では、長さ の巡回バーストは、次数 の多項式で非ゼロ係数として記述されます。ここで はパターン を定義し、エラーの開始点を定義します。パターンの長さは deg で与えられます。シンドローム多項式は各パターンごとに一意であり、次のように与えられます 。 ${\displaystyle t}$ ${\displaystyle e(x)=x^{i}b(x)\mod (x^{n}-1)}$ ${\displaystyle b(x)}$ ${\displaystyle t-1}$ ${\displaystyle b_{0}}$ ${\displaystyle b(x)}$ ${\displaystyle x^{i}}$ ${\displaystyle b(x)+1}$

${\displaystyle s(x)=e(x)\mod g(x)}$

長さ 以下のすべてのバースト エラーを訂正する線形ブロック コードには、少なくとも 個のチェック シンボルが必要です。証明: 長さ以下のバースト パターンを訂正できる線形コードは、長さ 以下のバーストをコードワードとして持つことができません。もし持つと、長さ のバーストによってコードワードが長さ のバースト パターンに変わる可能性があり、これもすべてゼロのコードワードで長さ のバースト エラーを作成することによって取得できます。ここで、最初の要素がゼロでない任意の 2 つのベクトルは、その差が長さ のバーストのコードワードになることを避けるために、配列の異なるコセットからのものでなければなりません。したがって、このようなコセットの数は、 であるこのようなベクトルの数と等しくなります。したがって、少なくとも個のコセットがあり、したがって少なくとも 個のチェック シンボルがあります。 ${\displaystyle t}$ ${\displaystyle 2t}$ ${\displaystyle t}$ ${\displaystyle 2t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle 2t}$ ${\displaystyle 2t}$ ${\displaystyle q^{2t}}$ ${\displaystyle q^{2t}}$ ${\displaystyle 2t}$

この特性は Rieger 境界とも呼ばれ、ランダム エラー訂正のシングルトン境界に似ています。

循環境界としての火災コード

1959年、フィリップ・ファイア^[8]は、二項式と原始多項式の積によって生成される巡回符号の構成を提示した。この二項式は、ある正の奇数に対して[9]の形をとる。ファイア符号は、生成多項式^[10]を持つ巡回バースト誤り訂正符号である。 ${\displaystyle x^{c}+1}$ ${\displaystyle c}$ ${\displaystyle GF(q)}$

${\displaystyle g(x)=(x^{2t-1}-1)p(x)}$

ここで、 は 以上の次数を持つ素多項式であり、を割り切れません。消防法のブロック長は、 を割り切れる最小の整数です。 ${\displaystyle p(x)}$ ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle p(x)}$ ${\displaystyle x^{2t-1}-1}$ ${\displaystyle n}$ ${\displaystyle g(x)}$ ${\displaystyle x^{n}-1}$

ファイアコードでは、長さ t 以下のすべてのバースト誤りを訂正できます。ただし、2 つのバーストとが同じコセットに出現してはいけません。これは背理法によって証明できます。長さt 以下の 2 つの異なる非ゼロバーストとが、コードの同じコセットに出現するとします。この場合、それらの差はコードワードです。差は の倍数なので、の倍数でもあります。したがって、 ${\displaystyle b(x)}$ ${\displaystyle x^{j}b'(x)}$ ${\displaystyle b(x)}$ ${\displaystyle x^{j}b'(x)}$ ${\displaystyle t}$ ${\displaystyle g(x)}$ ${\displaystyle x^{2t-1}-1}$

${\displaystyle b(x)=x^{j}b'(x)\mod (x^{2t-1}-1)}$。

これはが の倍数であることを示しています。したがって ${\displaystyle j}$ ${\displaystyle 2t-1}$

${\displaystyle b(x)=x^{l(2t-1)}b'(x)}$

についてである。さて、が より小さく、 がより小さいので、はコードワードである。したがって、 ${\displaystyle l}$ ${\displaystyle l(2t-1)}$ ${\displaystyle t}$ ${\displaystyle l}$ ${\displaystyle q^{m}-1}$ ${\displaystyle (x^{l(2t-1)}-1)b(x)}$

${\displaystyle (x^{l(2t-1)}-1)b(x)=a(x)(x^{2t-1}-1)p(x)}$。

次数は の次数より小さいので、を割り切れません。がゼロでない場合、もより小さいので割り切れません。また、 の定義により、はより小さくなることはありません。したがって、 と はゼロになります。これは、仮定に反して、両方のバーストが同じであることを意味します。 ${\displaystyle b(x)}$ ${\displaystyle p(x)}$ ${\displaystyle p(x)}$ ${\displaystyle b(x)}$ ${\displaystyle l}$ ${\displaystyle p(x)}$ ${\displaystyle x^{l(2t-1)}-1}$ ${\displaystyle l}$ ${\displaystyle q^{m}-1}$ ${\displaystyle m}$ ${\displaystyle p(x)}$ ${\displaystyle x^{l(2t-1)}-1}$ ${\displaystyle l}$ ${\displaystyle q^{m}-1}$ ${\displaystyle l}$ ${\displaystyle j}$

ファイアコードは、高レートの単一バースト訂正コードとして最適であり、解析的に構築されています。非常に高いレートを持ち、 とが等しい場合、冗長性は最小となり、 は に等しくなります。複数のファイアコードを使用することで、より長いバーストエラーも訂正できます。 ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle 3t-1}$

エラー検出には巡回コードが広く使用されており、巡回冗長コードと呼ばれます。 ${\displaystyle t-1}$

フーリエ変換について

フーリエ変換は信号処理において広く応用されています。しかし、その応用は複素体に限定されるわけではなく、ガロア体にもフーリエ変換は存在します。フーリエ変換を用いた巡回符号は、信号処理に近い設定で記述することができます。 ${\displaystyle GF(q)}$

有限体上のフーリエ変換

有限体上のフーリエ変換

ベクトルの離散フーリエ変換は ベクトルで与えられ、ここで、 ${\displaystyle v=v_{0},v_{1},....,v_{n-1}}$ ${\displaystyle V=V_{0},V_{1},.....,V_{n-1}}$

${\displaystyle V_{k}}$=ここで、 ${\displaystyle \Sigma _{i=0}^{n-1}e^{-j2\pi n^{-1}ik}v_{i}}$

${\displaystyle k=0,.....,n-1}$

ここで、exp( ) は1の乗根である。同様に、有限体では 1 の乗根はの位数である。したがって、 ${\displaystyle -j2\pi /n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \omega }$ ${\displaystyle n}$

が 上のベクトルでの位数の要素である場合、ベクトルのフーリエ変換はベクトルとなり、その成分は次のように与えられる。 ${\displaystyle v=(v_{0},v_{1},....,v_{n-1})}$ ${\displaystyle GF(q)}$ ${\displaystyle \omega }$ ${\displaystyle GF(q)}$ ${\displaystyle n}$ ${\displaystyle v}$ ${\displaystyle V=(V_{0},V_{1},.....,V_{n-1})}$

${\displaystyle V_{j}}$=ここで、 ${\displaystyle \Sigma _{i=0}^{n-1}\omega ^{ij}v_{i}}$

${\displaystyle k=0,.....,n-1}$

ここでは時間インデックス、は周波数、はスペクトルです。複素体とガロア体におけるフーリエ変換の重要な違いは、複素体では の任意の値に対して存在するのに対し、ガロア体ではがを割り切る場合にのみ存在することです。拡大体の場合、 が を割り切る場合、拡大体におけるフーリエ変換が存在します。ガロア 体では、時間領域ベクトルは 体上にあります。しかし、スペクトルは拡大体 上にある場合があります。 ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle V}$ ${\displaystyle \omega }$ ${\displaystyle n}$ ${\displaystyle \omega }$ ${\displaystyle n}$ ${\displaystyle q-1}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle n}$ ${\displaystyle q^{m}-1}$ ${\displaystyle m}$ ${\displaystyle v}$ ${\displaystyle GF(q)}$ ${\displaystyle V}$ ${\displaystyle GF(q^{m})}$

スペクトル記述

ブロック長 の巡回符号の任意の符号語は、最大 次 の多項式で表すことができます。その符号化器は と表すことができます。したがって、周波数領域では符号化器は と表すことができます。ここで、符号語スペクトルはにおける値を持ちますが、時間領域のすべての成分は から得られます。データスペクトルは任意であるため、 の役割は がゼロとなるものを指定することです。 ${\displaystyle n}$ ${\displaystyle c(x)}$ ${\displaystyle n-1}$ ${\displaystyle c(x)=a(x)g(x)}$ ${\displaystyle C_{j}=A_{j}G_{j}}$ ${\displaystyle C_{j}}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle GF(q)}$ ${\displaystyle A_{j}}$ ${\displaystyle G_{j}}$ ${\displaystyle j}$ ${\displaystyle C_{j}}$

したがって巡回符号は次のように定義することもできる。

スペクトルインデックスの集合 （要素はチェック周波数と呼ばれる）が与えられた場合 、巡回符号は上のワード集合であり、そのスペクトルは でインデックス付けされた成分においてゼロとなる。このようなスペクトルはいずれもの形式の成分を持つ。 ${\displaystyle A=(j_{1},....,j_{n-k})}$ ${\displaystyle C}$ ${\displaystyle GF(q)}$ ${\displaystyle j_{1},...,j_{n-k}}$ ${\displaystyle C}$ ${\displaystyle A_{j}G_{j}}$

したがって、巡回符号は体上のベクトルであり、その逆フーリエ変換によって与えられるスペクトルは体上にあり、特定の成分でゼロになるという制約があります。しかし、体上のスペクトルで特定の成分でゼロになるスペクトルは、体上の成分との逆変換を持つとは限りません。そのようなスペクトルは巡回符号として使用できません。 ${\displaystyle GF(q)}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle GF(q)}$

以下は巡回符号のスペクトルに関するいくつかの境界です。

BCH境界

が何らかの に対しての因数である場合、の重み以下ののベクトルのうち、スペクトルの連続する成分がゼロで ある唯一のベクトルは、すべてゼロのベクトルです。 ${\displaystyle n}$ ${\displaystyle (q^{m}-1)}$ ${\displaystyle m}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle d-1}$ ${\displaystyle d-1}$

ハートマン-ツェング境界

が何らかの に対しての因数であり、と互いに素な整数である場合、 （ただし および）に対してスペクトル成分がゼロとなる重みまたはそれ以下のベクトルのみが、全零ベクトルとなる。 ${\displaystyle n}$ ${\displaystyle (q^{m}-1)}$ ${\displaystyle m}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle v}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle d-1}$ ${\displaystyle V_{j}}$ ${\displaystyle j=\ell _{1}+\ell _{2}b(\mod n)}$ ${\displaystyle \ell _{1}=0,....,d-s-1}$ ${\displaystyle \ell _{2}=0,....,s-1}$

カンガルーは縛られる

が、およびに対して、の因数である場合。の重み以下の における、スペクトル成分が（ただし、およびは少なくともの範囲の値）でゼロとなる唯一のベクトルは 、すべてゼロのベクトルです。 ${\displaystyle n}$ ${\displaystyle q^{m}-1}$ ${\displaystyle m}$ ${\displaystyle GCD(n,b)=1}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle d-1}$ ${\displaystyle V_{j}}$ ${\displaystyle j=l_{1}+l_{2}b(\mod n)}$ ${\displaystyle l_{1}=0,...,d-s-2}$ ${\displaystyle l_{2}}$ ${\displaystyle s+1}$ ${\displaystyle 0,....,d-2}$

二次剰余コード

素数が を法とする平方剰余である場合、長さ、次元、および少なくともを超える最小重みの巡回コードである平方剰余コードが存在します。 ${\displaystyle l}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle (p+1)/2}$ ${\displaystyle {\sqrt {p}}}$ ${\displaystyle GF(l)}$

一般化

コンスタサイクリックコード

コンスタ巡回符号は、ある定数に対して が符号語ならば も であるという性質を持つ線形符号である。負巡回符号は を満たすコンスタ巡回符号である。^[10] ${\displaystyle \lambda }$ ${\displaystyle (c_{1},c_{2},\dots ,c_{n})}$ ${\displaystyle (\lambda c_{n},c_{1},\dots ,c_{n-1})}$ ${\displaystyle \lambda =-1}$

準巡回符号

準巡回符号（ QC符号）は、 を で割った場合、任意の符号語を 桁ずつ巡回シフトしたものが再び符号語となるという性質を持つ。つまり、ある定数 に対して、 が符号語であれば も符号語となる。ここで、すべての添え字は を法として簡約される。 ^[11]このような符号は-QC 符号と呼ばれる。二重巡回符号は、 となる偶数長の準巡回符号である。^[11] ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}$ ${\displaystyle (c_{-s},c_{1-s},\dots ,c_{n-s-1})}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle s=2}$

短縮巡回コード

線形符号は、巡回符号から位置を削除することで得られる場合、短縮巡回符号と呼ばれます。この形式の符号は一般に巡回的ではありません。^[12] ${\displaystyle (n,k)}$ ${\displaystyle b}$ ${\displaystyle (n+b,k+b)}$

短縮符号では、情報シンボルを削除することで、元のブロック長よりも短いブロック長を実現します。最初のシンボルを削除するのが一般的な方法ですが、原理的には任意の情報シンボルセットを削除できます。^[12]任意の巡回符号は、-番目ごとにシンボルを削除することで準巡回符号に変換できます。ここで、 -は-の係数です。削除されたシンボルがチェックシンボルでない場合、この巡回符号も短縮巡回符号となります。 ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle n}$

その他の一般化

準ツイストコード（QTコード）は、コンスタサイクリックコードと準サイクリックコードの特性を組み合わせたもので、シフトは桁数分発生し、乗数は である。つまり、ある定数と に対して、がコードワードであれば もコードワードとなり、すべての添え字は を法として簡約される。^[13]マルチツイストコードはQTコードをさらに一般化したもので、複数のQTコードを端から端まで結合する。^{[13] [14]} ${\displaystyle s}$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle s}$ ${\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}$ ${\displaystyle (\lambda c_{-s},c_{1-s},\dots ,c_{n-s-1})}$ ${\displaystyle n}$

参照

• BCHコード
• バイナリゴレイコード
• 巡回冗長検査
• ユージン・プランジ
• リード・ミュラー符号
• 三元ゴレイコード

注記

1. ヴァン・リント 1998年、76ページ
2. ライアン＆リン 2009、108～109ページ
3. ヴァン・リント 1998年、80ページ
4. ライアン＆リン 2009、第10章
5. ヒル 1988、159–160ページ
6. Blahut 2003、定理5.5.1
7. ヒル 1988、162–163ページ
8. P. Fire, E, P. (1959).非独立誤りに対する多重誤り訂正バイナリコードの一種.シルバニア偵察システム研究所, カリフォルニア州マウンテンビュー, Rept. RSL-E-2, 1959.
9. Wei Zhou、Shu Lin、Khaled Abdel-Ghaffar. Fire符号とBCH符号に基づくバースト誤り訂正またはランダム誤り訂正. ITA 2014: 1-5 2013.
10. ヴァン・リント 1998年、75ページ
11. マクウィリアムズ & スローン 1977、p. 506
12. ライアン＆リン 2009、110ページ
13. Aydin, Nuh; Halilović, Ajdin (2017). 「準ツイスト符号の一般化：多重ツイスト符号」.有限体とその応用. 45 : 96–106 . arXiv : 1701.01044 . doi : 10.1016/j.ffa.2016.12.002 . S2CID  7694655.
14. Aydin, Nuh; Siap, Irfan; K. Ray-Chaudhuri, Dijen (2001). 「1生成子準ツイスト符号と新しい線形符号の構造」. Designs, Codes and Cryptography . 24 (3): 313– 326. doi :10.1023/A:1011283523000. S2CID  17376783.

参考文献

• Blahut, Richard E. (2003)、「データ伝送のための代数的コード（第2版）」、ケンブリッジ大学出版局、ISBN 0-521-55374-1
• ヒル、レイモンド（1988年）、コーディング理論入門、オックスフォード大学出版局、ISBN 0-19-853803-0
• MacWilliams, FJ ; Sloane, NJA (1977)、The Theory of Error-Correcting Codes、ニューヨーク：North-Holland Publishing、ISBN 0-444-85011-2
• ライアン、ウィリアム・E.; リン、シュウ（2009）『チャネルコード：古典と現代』（第1版）、ケンブリッジ大学出版局、ISBN 978-0521848688
• Van Lint, JH (1998)、符号理論入門、Graduate Texts in Mathematics 86 (第3版)、Springer Verlag、ISBN 3-540-64133-5

さらに読む

• ランジャン・ボーズ著『情報理論、符号化、暗号』ISBN 0-07-048297-7
• Irving S. ReedとXuemin Chen著『Error-Control Coding for Data Networks』、ボストン：Kluwer Academic Publishers、1999年、ISBN 0-7923-8528-4。
• スコット・A・ヴァンストーン、ポール・C・ヴァン・オーショット著『誤り訂正符号入門とその応用』ISBN 0-7923-9017-2

外部リンク

• John Gill (スタンフォード) の授業ノート – ノート #3、10 月 8 日、配布資料 #9、Wayback Machineに 2012 年 10 月 23 日にアーカイブ、EE 387。
• ジョナサン・ホール（ミシガン州立大学）の授業ノート - 第8章 巡回符号 - 100～123ページ
• David Terr. 「巡回コード」。MathWorld。

この記事には、Creative Commons Attribution/Share-Alike Licenseに基づいてライセンスされているPlanetMathの巡回コードの資料が組み込まれています。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Cyclic_code&oldid=1319561433"