ブロックコードの種類
符号理論 では 、 巡回符号は ブロック符号 であり 、各符号語の 巡回シフト によって、その符号に属する別のワードが生成されます。巡回符号は、効率的な エラー検出と訂正 に便利な代数的特性を持つ エラー訂正符号 です。
00010111 が有効なコードワードである場合、右循環シフトを適用すると、文字列 10001011 が生成されます。コードが循環的である場合、10001011 は再び有効なコードワードになります。一般に、右循環シフトを適用すると、最下位ビット (LSB) が最も左の位置に移動され、最上位ビット (MSB) になります。他の位置は 1 ずつ右にシフトされます。
意味 をブロック長 の 有限体 ( ガロア体 とも呼ばれる) 上の 線形符号 とします 。 の すべて の 符号語に対して、要素の 巡回右シフト によって得られる の 語が再び符号語になるとき、 は 巡回符号 と呼ばれます。1 回の巡回右シフトは巡回左シフトに等しいため 、巡回符号は巡回左シフトによって定義することもできます。したがって、線形符号が巡回符号であるの は、すべての巡回シフトに対して不変である場合に限ります。
Ｃ
{\displaystyle {\mathcal {C}}}
グ ふ （ q ）
{\displaystyle GF(q)}
ん
{\displaystyle n}
Ｃ
{\displaystyle {\mathcal {C}}}
c = （
c
1
、 … 、
c
ん
）
{\displaystyle c=(c_{1},\ldots,c_{n})}
Ｃ
{\displaystyle {\mathcal {C}}}
（
c
ん
、
c
1
、 … 、
c
ん − 1
）
{\displaystyle (c_{n},c_{1},\ldots ,c_{n-1})}
グ ふ （ q
）
ん
{\displaystyle GF(q)^{n}}
ん − 1
{\displaystyle n-1}
Ｃ
{\displaystyle {\mathcal {C}}}
巡回コードには、コードに対する追加の構造的制約があります。巡回コードは ガロア体 に基づいており、その構造的特性により、エラー制御に非常に役立ちます。巡回コードの構造はガロア体と密接に関連しているため、巡回コードのエンコードおよびデコード アルゴリズムは計算効率が高くなります。
代数構造 巡回符号は、特定の環のイデアルにリンクできます。 を 有限体 上の 多項式環 とします 。巡回符号の元を、 多項式 にマップされる の
多項式
と同一視します 。したがって、 による乗算は 巡回シフトに対応します。すると は の イデアル と なり 、 は 主イデアル環 である ため、 主 と なります。イデアルは、最小次数の の一意のモニック元、つまり 生成多項式 によって生成されます。 [1]
これは の約数でなければなりません 。したがって、すべての巡回符号は 多項式符号 になります。生成多項式の 次数が の場合 、符号の階数 は です 。
R = あ [ x ]
/
（
x
ん
− 1 ）
{\displaystyle R=A[x]/(x^{n}-1)}
あ = グ ふ （ q ）
{\displaystyle A=GF(q)}
Ｃ
{\displaystyle C}
R
{\displaystyle R}
（
c
0
、 … 、
c
ん − 1
）
{\displaystyle (c_{0},\ldots,c_{n-1})}
c
0
+
c
1
x + ⋯ +
c
ん − 1
x
ん − 1
{\displaystyle c_{0}+c_{1}x+\cdots +c_{n-1}x^{n-1}}
x
{\displaystyle x}
Ｃ
{\displaystyle C}
R
{\displaystyle R}
R
{\displaystyle R}
Ｃ
{\displaystyle C}
グ
{\displaystyle g}
x
ん
− 1
{\displaystyle x^{n}-1}
グ
{\displaystyle g}
d
{\displaystyle d}
Ｃ
{\displaystyle C}
ん − d
{\displaystyle nd}
のべき等性 は 、 （つまり、 は のべき等元 ） となる コードワードであり 、 は コードの恒等元であり、つまり すべてのコードワード に対して となる 。 と が 互いに素で ある場合、 そのようなワードは常に存在し、一意である。 [2] それはコードの生成元である。
Ｃ
{\displaystyle C}
e
{\displaystyle e}
e
2
= e
{\displaystyle e^{2}=e}
e
{\displaystyle e}
Ｃ
{\displaystyle C}
e
{\displaystyle e}
e ⋅ c = c
{\displaystyle e\cdot c=c}
c
{\displaystyle c}
ん
{\displaystyle n}
q
{\displaystyle q}
既 約符号 とは、符号がイデアルとして既約でない、つまり が において最小であり 、その結果その検査多項式が 既約多項式 となる巡回符号 です。
R
{\displaystyle R}
例 例えば、 および の場合 、 によって生成される巡回符号に含まれる符号語の集合は 、正確に
あ =
ふ
2
{\displaystyle A=\mathbb {F} _{2}}
ん = 3
{\displaystyle n=3}
（ 1 、 1 、 0 ）
{\displaystyle (1,1,0)}
（ （ 0 、 0 、 0 ） 、 （ 1 、 1 、 0 ） 、 （ 0 、 1 、 1 ） 、 （ 1 、 0 、 1 ） ）
{\displaystyle ((0,0,0),(1,1,0),(0,1,1),(1,0,1))}
。 これは、 によって生成された の理想に対応します 。
ふ
2
[ x ]
/
（
x
3
− 1 ）
{\displaystyle \mathbb {F} _{2}[x]/(x^{3}-1)}
（ 1 + x ）
{\displaystyle (1+x)}
多項式は 多項式環において既約ではないため、コードは既約コードです。
（ 1 + x ）
{\displaystyle (1+x)}
このコードのべき等性は、コードワード に対応する 多項式 です 。
x +
x
2
{\displaystyle x+x^{2}}
（ 0 、 1 、 1 ）
{\displaystyle (0,1,1)}
些細な例 巡回コードの簡単な例としては、 自体と、ゼロ コードワードのみを含むコードがあります。これらはそれぞれジェネレータとに対応します 。 つまり、これら 2 つの多項式は常に の因数でなければなりません 。
あ
ん
{\displaystyle A^{n}}
1
{\displaystyle 1}
x
ん
− 1
{\displaystyle x^{n}-1}
x
ん
− 1
{\displaystyle x^{n}-1}
偶数の重みを持つすべてのワードで構成されるパリティ ビット コード上は 、ジェネレータ に対応します 。また、 これ 上は常に の因数である必要があります 。
グ ふ （ 2 ）
{\displaystyle GF(2)}
x + 1
{\displaystyle x+1}
グ ふ （ 2 ）
{\displaystyle GF(2)}
x
ん
− 1
{\displaystyle x^{n}-1}
準巡回符号と短縮符号 巡回コードの詳細に入る前に、まず巡回コードと密接に関連し、相互に変換可能な準巡回コードと短縮コードについて説明します。
意味 準巡回符号: [ 引用が必要 ]
準 巡回符号は、 と互いに素である に対して、 がコードワード多項式である ときは常に 、多項式が コードワード多項式 となる ような線形ブロック符号です 。
（ ん 、 け ）
{\displaystyle (n,k)}
b
{\displaystyle b}
ん
{\displaystyle n}
x
b
c （ x ）
（ モッド
x
ん
− 1 ）
{\displaystyle x^{b}c(x){\pmod {x^{n}-1}}}
c （ x ）
{\displaystyle c(x)}
ここで、 コードワード多項式は、コード ワードが 生成多項式 と呼ばれるより短い長さの多項式で割り切れる多項式である 線形コードの要素です。すべてのコードワード多項式は 、 の 形式で表現できます 。ここで、 は生成多項式です。 巡回コードの任意のコードワードは 、コードワード多項式、つまり に関連付けることができます。 が に等しい 準巡回コード は巡回コードです。
c （ x ） = 1つの （ x ） グ （ x ）
{\displaystyle c(x)=a(x)g(x)}
グ （ x ）
{\displaystyle g(x)}
（
c
0
、 。 。 、
c
ん − 1
）
{\displaystyle (c_{0},...,c_{n-1})}
Ｃ
{\displaystyle C}
∑
私 = 0
ん − 1
c
私
∗
x
私
{\displaystyle \sum _{i=0}^{n-1}c_{i}*x^{i}}
b
{\displaystyle b}
1
{\displaystyle 1}
意味 短縮コード:
巡回コードから位置を 削除することによって線形コードを取得できる場合、 その線形コードは 適切な短縮巡回コード と呼ばれます 。
（ ん 、 け ）
{\displaystyle (n,k)}
b
{\displaystyle b}
（ ん + b 、 け + b ）
{\displaystyle (n+b,k+b)}
短縮コードでは、設計ブロック長よりも短い所望のブロック長を得るために情報シンボルが削除されます。欠落した情報シンボルは通常、コードワードの先頭にあると想定され、0 と見なされます。したがって、 - は固定され、次に が 減少し、最終的に が減少します 。開始シンボルを削除する必要はありません。アプリケーションによっては、連続する位置が 0 と見なされ、削除されることがあります。
ん
{\displaystyle n}
け
{\displaystyle k}
け
{\displaystyle k}
ん
{\displaystyle n}
削除されたシンボルはすべて送信する必要はなく、受信側で再挿入できます。巡回コードを 短縮コード に変換するには、シンボルをゼロに設定し、各コードワードからシンボルを削除します。巡回コードは 、 が の因数である 番目のシンボル ごとに削除することで、準巡回コードに変換できます 。削除されたシンボルがチェック シンボルでない場合、この巡回コードも短縮コードになります。
（ ん 、 け ）
{\displaystyle (n,k)}
（ ん − b 、 け − b ）
{\displaystyle (nb,kb)}
b
{\displaystyle b}
b
{\displaystyle b}
b
{\displaystyle b}
ん
{\displaystyle n}
エラーを修正するため 巡回符号は 、 ハミング符号と同様に、 エラーの訂正 に使用できます。巡回符号は、単一エラーの訂正に使用できます。同様に、巡回符号は、二重エラーやバースト エラーの訂正にも使用されます。すべてのタイプのエラー訂正については、以降のサブセクションで簡単に説明します。
(7,4) ハミング コードには 生成多項式があります。この多項式は、 ガロア拡大体 の原始元 にゼロを持ち 、すべてのコードワードは を満たします 。巡回コードを使用して、体 上の二重エラーを訂正することもできます。ブロック長は に等しく 、原始元 と は の ゼロに なります。 これは、ここでは 2 つのエラーの場合を検討しているため、それぞれが 1 つのエラーを表すためです。
グ （ x ） =
x
3
+ x + 1
{\displaystyle g(x)=x^{3}+x+1}
グ ふ （ 8 ）
{\displaystyle GF(8)}
α
{\displaystyle \alpha}
Ｃ
（ α ） = 0
{\displaystyle {\mathcal {C}}(\alpha )=0}
グ ふ （ 2 ）
{\displaystyle GF(2)}
ん
{\displaystyle n}
2
メートル
− 1
{\displaystyle 2^{m}-1}
α
{\displaystyle \alpha}
α
3
{\displaystyle \alpha^{3}}
グ ふ （
2
メートル
）
{\displaystyle GF(2^{m})}
受信語は次数で与えられる
多項式である。
ん − 1
{\displaystyle n-1}
ヴ （ x ） = 1つの （ x ） グ （ x ） + e （ x ）
{\displaystyle v(x)=a(x)g(x)+e(x)}
ここで、 2 つのエラーに対応する非ゼロの係数を最大 2 つ持つことができます。
e （ x ）
{\displaystyle e(x)}
シンドローム多項式を 、多項式 を生成多項式で割った 余りとして 定義します 。つまり、
S （ x ）
{\displaystyle S(x)}
ヴ （ x ）
{\displaystyle v(x)}
グ （ x ）
{\displaystyle g(x)}
S （ x ） ≡ ヴ （ x ） ≡ （ 1つの （ x ） グ （ x ） + e （ x ） ） ≡ e （ x ） モッド グ （ x ）
{\displaystyle S(x)\equiv v(x)\equiv (a(x)g(x)+e(x))\equiv e(x)\mod g(x)}
として 。
（ 1つの （ x ） グ （ x ） ） ≡ 0 モッド グ （ x ）
{\displaystyle (a(x)g(x))\equiv 0\mod g(x)}
2つのエラーを修正するため フィールド要素 とを 2 つのエラー位置番号とします。エラーが 1 つだけ発生した場合は は ゼロになり、エラーが発生しない場合は両方ともゼロになります。
バツ
1
{\displaystyle X_{1}}
バツ
2
{\displaystyle X_{2}}
バツ
2
{\displaystyle X_{2}}
と します 。
S
1
=
ヴ
（ α ）
{\displaystyle S_{1}={v}(\alpha )}
S
3
=
ヴ
（
α
3
）
{\displaystyle S_{3}={v}(\alpha ^{3})}
これらの体元は「シンドローム」と呼ばれます。 は 原始元 とではゼロなので、 と と 書くことができます 。 2つのエラーが発生した場合、
グ （ x ）
{\displaystyle g(x)}
α
{\displaystyle \alpha}
α
3
{\displaystyle \alpha^{3}}
S
1
= e （ α ）
{\displaystyle S_{1}=e(\alpha )}
S
3
= e （
α
3
）
{\displaystyle S_{3}=e(\alpha ^{3})}
S
1
=
α
私
+
α
私 ′
{\displaystyle S_{1}=\alpha ^{i}+\alpha ^{i'}}
そして
。
S
3
=
α
3 私
+
α
3
私 ′
{\displaystyle S_{3}=\alpha ^{3i}+\alpha ^{3i'}}
そして、これら2つは2つの未知数を持つ
2組の方程式として考えることができるので、次のように書くことができる。
グ ふ （
2
メートル
）
{\displaystyle GF(2^{m})}
S
1
=
バツ
1
+
バツ
2
{\displaystyle S_{1}=X_{1}+X_{2}}
そして
。
S
3
= （
バツ
1
）
3
+ （
バツ
2
）
3
{\displaystyle S_{3}=(X_{1})^{3}+(X_{2})^{3}}
したがって、2 組の非線形方程式を解くことができれば、巡回コードを使用して 2 つのエラーを修正できます。
ハミングコード ハミング (7,4) 符号は、生成元 を持つGF(2)上の巡回符号として記述できます 。実際、形式Ham(r, 2)の任意の2元ハミング符号は巡回符号と同等であり、 [3] rとq-1が互いに素である形式Ham(r,q)の任意のハミング符号も巡回符号と同等です。 [4] を持つ形式Ham(r,2)のハミング符号が与えられた場合 、偶数コードワードの集合は巡回 -符号を形成します。 [5]
1 + x +
x
3
{\displaystyle 1+x+x^{3}}
r ≥ 3
{\displaystyle r\geq 3}
[
2
r
− 1 、
2
r
− r − 2 、 4 ]
{\displaystyle [2^{r}-1,2^{r}-r-2,4]}
単一エラーを訂正するハミングコード 最小距離が少なくとも 3 であるコードは、すべての列が異なっており、ゼロでないチェック マトリックスを持ちます。バイナリ コードのチェック マトリックスに行がある場合 、各列は ビットのバイナリ数です。可能な列は複数あります。したがって、 少なくとも 3 のバイナリ コードのチェック マトリックスに行がある場合、列は 1 つしか持てず、それ以上 は持てません。これが ハミング コードと呼ばれるコードを定義します。
メートル
{\displaystyle m}
メートル
{\displaystyle m}
2
メートル
− 1
{\displaystyle 2^{m}-1}
d
メートル 私 ん
{\displaystyle d_{min}}
メートル
{\displaystyle m}
2
メートル
− 1
{\displaystyle 2^{m}-1}
（
2
メートル
− 1 、
2
メートル
− 1 − メートル ）
{\displaystyle (2^{m}-1,2^{m}-1-m)}
サイズ の大きなアルファベットのハミング コードを定義するのは簡単です 。線形独立な列を持つ 1 つの行列を定義する必要があります 。 サイズの任意のワードには、 互いの倍数となる列があります。したがって、線形独立性を得るために、 最上位の非ゼロ要素として 1 を持つすべての非ゼロ タプルが列として選択されます。すると、コードの最小距離が 3 で 3 つの列が線形従属になる可能性があるため、2 つの列が線形従属になることはありません。
q
{\displaystyle q}
H
{\displaystyle H}
q
{\displaystyle q}
メートル
{\displaystyle m}
つまり、 最上位の非ゼロ要素として 1 を持つ非ゼロ列が存在します。したがって、ハミング コードはコードです 。
（
q
メートル
− 1 ）
/
（ q − 1 ）
{\displaystyle (q^{m}-1)/(q-1)}
[ （
q
メートル
− 1 ）
/
（ q − 1 ） 、 （
q
メートル
− 1 ）
/
（ q − 1 ） − メートル ]
{\displaystyle [(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m]}
ここで、巡回符号について、 を の原始元とし 、 とします 。すると、 となり 、したがって は 多項式の零点となり 、 はブロック長 の巡回符号の生成多項式となります 。
α
{\displaystyle \alpha }
G
F
(
q
m
)
{\displaystyle GF(q^{m})}
β
=
α
q
−
1
{\displaystyle \beta =\alpha ^{q-1}}
β
(
q
m
−
1
)
/
(
q
−
1
)
=
1
{\displaystyle \beta ^{(q^{m}-1)/(q-1)}=1}
β
{\displaystyle \beta }
x
(
q
m
−
1
)
/
(
q
−
1
)
−
1
{\displaystyle x^{(q^{m}-1)/(q-1)}-1}
n
=
(
q
m
−
1
)
/
(
q
−
1
)
{\displaystyle n=(q^{m}-1)/(q-1)}
しかし 、については となる 。そして、受信語は次数 の多項式で、 次のように与えられる。
q
=
2
{\displaystyle q=2}
α
=
β
{\displaystyle \alpha =\beta }
n
−
1
{\displaystyle n-1}
v
(
x
)
=
a
(
x
)
g
(
x
)
+
e
(
x
)
{\displaystyle v(x)=a(x)g(x)+e(x)}
ここ で、 またはは エラーの場所を表します。
e
(
x
)
=
0
{\displaystyle e(x)=0}
x
i
{\displaystyle x^{i}}
i
{\displaystyle i}
しかし、 をの要素として 使用して、エラー位置をインデックスすることもできます 。 で あるため、 となり 、 から までのすべての の累乗は異なります。したがって、 がエラーなしを表していない 限り、 から エラー位置を簡単に特定できます。したがって、ハミング コードは および 上 の単一のエラー訂正コードです 。
α
i
{\displaystyle \alpha ^{i}}
G
F
(
2
m
)
{\displaystyle GF(2^{m})}
g
(
α
)
=
0
{\displaystyle g(\alpha )=0}
v
(
α
)
=
α
i
{\displaystyle v(\alpha )=\alpha ^{i}}
α
{\displaystyle \alpha }
0
{\displaystyle 0}
2
m
−
2
{\displaystyle 2^{m}-2}
i
{\displaystyle i}
α
i
{\displaystyle \alpha ^{i}}
v
(
α
)
=
0
{\displaystyle v(\alpha )=0}
G
F
(
2
)
{\displaystyle GF(2)}
n
=
2
m
−
1
{\displaystyle n=2^{m}-1}
k
=
n
−
m
{\displaystyle k=n-m}
バーストエラーを修正するため ハミング距離の 概念から 、最小距離のコードはどんな エラー も訂正できます。しかし、多くのチャネルではエラーパターンはそれほどランダムではなく、メッセージの非常に短いセグメント内で発生します。このような種類のエラーは バーストエラー と呼ばれます。したがって、このようなエラーを訂正するには、制約が少ないため、より効率的な高レートのコードが必要になります。巡回コードはバーストエラーを訂正するために使用されます。実際、巡回コードはバーストエラーだけでなく巡回バーストエラーも訂正できます。巡回バーストエラーは次のように定義されます。
2
t
+
1
{\displaystyle 2t+1}
t
{\displaystyle t}
長さの巡回バーストは、非ゼロの成分が （巡回的に）連続する成分の中にあり、その最初と最後の成分が非ゼロである
ベクトルです。
t
{\displaystyle t}
t
{\displaystyle t}
多項式形式では、長さ の周期的バーストは、 非ゼロ係数 を持つ 次数 の多項式 として 記述できます 。ここで は パターンを定義し、 エラーの開始点を定義します。パターンの長さは deg で与えられます 。シンドローム多項式は各パターンに固有であり、次のように与えられます。
t
{\displaystyle t}
e
(
x
)
=
x
i
b
(
x
)
mod
(
x
n
−
1
)
{\displaystyle e(x)=x^{i}b(x)\mod (x^{n}-1)}
b
(
x
)
{\displaystyle b(x)}
t
−
1
{\displaystyle t-1}
b
0
{\displaystyle b_{0}}
b
(
x
)
{\displaystyle b(x)}
x
i
{\displaystyle x^{i}}
b
(
x
)
+
1
{\displaystyle b(x)+1}
s
(
x
)
=
e
(
x
)
mod
g
(
x
)
{\displaystyle s(x)=e(x)\mod g(x)}
長さ 以下のすべてのバースト エラーを訂正する線形ブロック コードには 、少なくとも 個の チェック シンボルが必要です。証明: 長さ 以下のバースト パターンを訂正できる線形コードは、長さ 以下のバーストを コードワードとして持つことはできません。これは、長さ のバーストが コードワードを長さ のバースト パターンに変更できるためです 。これは、すべてゼロのコードワードで長さ のバースト エラーを作成することによっても取得できます 。ここで、最初の 要素がゼロでない任意の 2 つのベクトルは、その差が長さ のバーストのコードワードになることを避けるために、配列の異なるコセットからのものである必要があります 。したがって、このようなコセットの数は、 であるこのようなベクトルの数と等しくなります 。したがって、少なくとも個の コセットがあり、したがって少なくとも 個の チェック シンボルがあります。
t
{\displaystyle t}
2
t
{\displaystyle 2t}
t
{\displaystyle t}
2
t
{\displaystyle 2t}
t
{\displaystyle t}
t
{\displaystyle t}
t
{\displaystyle t}
2
t
{\displaystyle 2t}
2
t
{\displaystyle 2t}
q
2
t
{\displaystyle q^{2t}}
q
2
t
{\displaystyle q^{2t}}
2
t
{\displaystyle 2t}
この特性は Rieger 境界とも呼ばれ、ランダム エラー訂正の
シングルトン境界 に似ています。
循環境界としての消防法 1959年、フィリップ・ファイア [6]は、 二項式と原始多項式の積によって生成される巡回符号の構成を発表した。二項式は、 ある正の奇数に対しての形をとる 。 [7] ファイア符号 は、 生成多項式
x
c
+
1
{\displaystyle x^{c}+1}
c
{\displaystyle c}
G
F
(
q
)
{\displaystyle GF(q)}
g
(
x
)
=
(
x
2
t
−
1
−
1
)
p
(
x
)
{\displaystyle g(x)=(x^{2t-1}-1)p(x)}
ここで、 は 以上の次数を持ち 、 を割り切れない 素多項式です 。消防法のブロック長は を割り切れる最小の 整数 です
。
p
(
x
)
{\displaystyle p(x)}
m
{\displaystyle m}
t
{\displaystyle t}
p
(
x
)
{\displaystyle p(x)}
x
2
t
−
1
−
1
{\displaystyle x^{2t-1}-1}
n
{\displaystyle n}
g
(
x
)
{\displaystyle g(x)}
x
n
−
1
{\displaystyle x^{n}-1}
ファイアコードは、2 つのバーストとが同じコセットに出現しない限り、長さ t 以下のすべてのバーストエラーを訂正できます。これは、背理法によって証明できます。長さ t 以下の 2 つの異なる非ゼロバーストとがあり 、 コード の 同じ コセットにあるとします。したがって、それらの差はコードワードです。差は の倍数であるため、 の倍数でもあります 。したがって、
b
(
x
)
{\displaystyle b(x)}
x
j
b
′
(
x
)
{\displaystyle x^{j}b'(x)}
b
(
x
)
{\displaystyle b(x)}
x
j
b
′
(
x
)
{\displaystyle x^{j}b'(x)}
t
{\displaystyle t}
g
(
x
)
{\displaystyle g(x)}
x
2
t
−
1
−
1
{\displaystyle x^{2t-1}-1}
b
(
x
)
=
x
j
b
′
(
x
)
mod
(
x
2
t
−
1
−
1
)
{\displaystyle b(x)=x^{j}b'(x)\mod (x^{2t-1}-1)}
。
これは が の倍数であることを示しています 。したがって
j
{\displaystyle j}
2
t
−
1
{\displaystyle 2t-1}
b
(
x
)
=
x
l
(
2
t
−
1
)
b
′
(
x
)
{\displaystyle b(x)=x^{l(2t-1)}b'(x)}
が より小さく 、 が より小さい ので 、 はコードワードです。したがって、
l
{\displaystyle l}
l
(
2
t
−
1
)
{\displaystyle l(2t-1)}
t
{\displaystyle t}
l
{\displaystyle l}
q
m
−
1
{\displaystyle q^{m}-1}
(
x
l
(
2
t
−
1
)
−
1
)
b
(
x
)
{\displaystyle (x^{l(2t-1)}-1)b(x)}
(
x
l
(
2
t
−
1
)
−
1
)
b
(
x
)
=
a
(
x
)
(
x
2
t
−
1
−
1
)
p
(
x
)
{\displaystyle (x^{l(2t-1)}-1)b(x)=a(x)(x^{2t-1}-1)p(x)}
。
次数は の次数より小さいため 、 を 割り切れません 。 が ゼロでない場合、も より小さい ため 割り切れません。 また、 の定義により 、 は より小さくなる と を 割り切れません 。したがって 、 と は ゼロに等しくなります。つまり、仮定に反して、両方のバーストは同じであるということです。
b
(
x
)
{\displaystyle b(x)}
p
(
x
)
{\displaystyle p(x)}
p
(
x
)
{\displaystyle p(x)}
b
(
x
)
{\displaystyle b(x)}
l
{\displaystyle l}
p
(
x
)
{\displaystyle p(x)}
x
l
(
2
t
−
1
)
−
1
{\displaystyle x^{l(2t-1)}-1}
l
{\displaystyle l}
q
m
−
1
{\displaystyle q^{m}-1}
m
{\displaystyle m}
p
(
x
)
{\displaystyle p(x)}
x
l
(
2
t
−
1
)
−
1
{\displaystyle x^{l(2t-1)}-1}
l
{\displaystyle l}
q
m
−
1
{\displaystyle q^{m}-1}
l
{\displaystyle l}
j
{\displaystyle j}
ファイア コードは、高レートの単一バースト訂正コードとして最適で、解析的に構築されています。 レートが非常に高く、 と が 等しい場合、冗長性は最小となり、 は に等しくなります 。 複数のファイア コードを使用することで、より長いバースト エラーも訂正できます。
m
{\displaystyle m}
t
{\displaystyle t}
3
t
−
1
{\displaystyle 3t-1}
エラー検出には巡回コードが広く使用されており、 巡回冗長コード と呼ばれます。
t
−
1
{\displaystyle t-1}
フーリエ変換 の応用は 信号処理で広く行われています。しかし、その応用は複素体だけに限定されず、ガロア体にもフーリエ変換が存在します 。フーリエ変換を使用した巡回符号は、信号処理に近い設定で記述できます。
G
F
(
q
)
{\displaystyle GF(q)}
有限体上のフーリエ変換
ベクトルの離散フーリエ変換は ベクトルで与えられ 、ここで、
v
=
v
0
,
v
1
,
.
.
.
.
,
v
n
−
1
{\displaystyle v=v_{0},v_{1},....,v_{n-1}}
V
=
V
0
,
V
1
,
.
.
.
.
.
,
V
n
−
1
{\displaystyle V=V_{0},V_{1},.....,V_{n-1}}
V
k
{\displaystyle V_{k}}
= ここで、
Σ
i
=
0
n
−
1
e
−
j
2
π
n
−
1
i
k
v
i
{\displaystyle \Sigma _{i=0}^{n-1}e^{-j2\pi n^{-1}ik}v_{i}}
k
=
0
,
.
.
.
.
.
,
n
−
1
{\displaystyle k=0,.....,n-1}
ここで、exp( ) は 1 の累乗根です。同様に有限体では 1 の累乗根は の位数要素です 。したがって
−
j
2
π
/
n
{\displaystyle -j2\pi /n}
n
{\displaystyle n}
n
{\displaystyle n}
ω
{\displaystyle \omega }
n
{\displaystyle n}
が 上のベクトルで が の位数 の要素である 場合 、ベクトルのフーリエ変換は ベクトルとなり 、その成分は次のように与えられる。
v
=
(
v
0
,
v
1
,
.
.
.
.
,
v
n
−
1
)
{\displaystyle v=(v_{0},v_{1},....,v_{n-1})}
G
F
(
q
)
{\displaystyle GF(q)}
ω
{\displaystyle \omega }
G
F
(
q
)
{\displaystyle GF(q)}
n
{\displaystyle n}
v
{\displaystyle v}
V
=
(
V
0
,
V
1
,
.
.
.
.
.
,
V
n
−
1
)
{\displaystyle V=(V_{0},V_{1},.....,V_{n-1})}
V
j
{\displaystyle V_{j}}
= ここで、
Σ
i
=
0
n
−
1
ω
i
j
v
i
{\displaystyle \Sigma _{i=0}^{n-1}\omega ^{ij}v_{i}}
k
=
0
,
.
.
.
.
.
,
n
−
1
{\displaystyle k=0,.....,n-1}
ここで は 時間 インデックス 、 は 周波数 、は スペクトル です 。複素体とガロア体におけるフーリエ変換の重要な違いの 1 つは、複素体では のすべての値に対して存在するの に対し、ガロア体ではが を 割り切る 場合にのみ存在することです。拡大体の場合、 が を 割り切る 場合、 拡大体でフーリエ変換が存在します 。ガロア体では、時間領域ベクトルは 体上にあります。 しかし、スペクトルは 拡大体上にある場合があります 。
i
{\displaystyle i}
j
{\displaystyle j}
V
{\displaystyle V}
ω
{\displaystyle \omega }
n
{\displaystyle n}
ω
{\displaystyle \omega }
n
{\displaystyle n}
q
−
1
{\displaystyle q-1}
G
F
(
q
m
)
{\displaystyle GF(q^{m})}
n
{\displaystyle n}
q
m
−
1
{\displaystyle q^{m}-1}
m
{\displaystyle m}
v
{\displaystyle v}
G
F
(
q
)
{\displaystyle GF(q)}
V
{\displaystyle V}
G
F
(
q
m
)
{\displaystyle GF(q^{m})}
スペクトルの説明 ブロック長 の巡回符号の任意の符号語は、 最大 次数の 多項式で表すことができます 。そのエンコーダは と記述できます 。したがって、周波数領域では、エンコーダは と記述できます 。ここで、 符号語スペクトルは の値を持ちます が、時間領域のすべての成分は からのものです 。データ スペクトルは 任意であるため、 の役割はがゼロ に なる
ものを指定することです。
n
{\displaystyle n}
c
(
x
)
{\displaystyle c(x)}
n
−
1
{\displaystyle n-1}
c
(
x
)
=
a
(
x
)
g
(
x
)
{\displaystyle c(x)=a(x)g(x)}
C
j
=
A
j
G
j
{\displaystyle C_{j}=A_{j}G_{j}}
C
j
{\displaystyle C_{j}}
G
F
(
q
m
)
{\displaystyle GF(q^{m})}
G
F
(
q
)
{\displaystyle GF(q)}
A
j
{\displaystyle A_{j}}
G
j
{\displaystyle G_{j}}
j
{\displaystyle j}
C
j
{\displaystyle C_{j}}
したがって巡回符号は次のように定義することもできる。
スペクトルインデックスのセット が与えられ、 その 要素はチェック周波数と呼ばれます。巡回コードは、 によってインデックス付けされたコンポーネントでスペクトルがゼロになる 上のワードのセットです 。 このようなスペクトルは、 という形式のコンポーネントを持ちます 。
A
=
(
j
1
,
.
.
.
.
,
j
n
−
k
)
{\displaystyle A=(j_{1},....,j_{n-k})}
C
{\displaystyle C}
G
F
(
q
)
{\displaystyle GF(q)}
j
1
,
.
.
.
,
j
n
−
k
{\displaystyle j_{1},...,j_{n-k}}
C
{\displaystyle C}
A
j
G
j
{\displaystyle A_{j}G_{j}}
したがって、巡回符号は体のベクトルであり 、その逆フーリエ変換によって与えられるスペクトルは体上にあり 、特定の成分でゼロになるように制約されます。しかし、体内のすべてのスペクトル と特定の成分でゼロは、体内の成分との逆変換を持たない可能性があります 。そのようなスペクトルは巡回符号として使用できません。
G
F
(
q
)
{\displaystyle GF(q)}
G
F
(
q
m
)
{\displaystyle GF(q^{m})}
G
F
(
q
m
)
{\displaystyle GF(q^{m})}
G
F
(
q
)
{\displaystyle GF(q)}
以下は巡回符号のスペクトルに関するいくつかの境界です。
BCHバウンド が何らかの に対して の因数である 場合、 の重み 以下のベクトルの うち、スペクトルの連続する成分がゼロである唯一のベクトルは 、すべてゼロのベクトルです。
n
{\displaystyle n}
(
q
m
−
1
)
{\displaystyle (q^{m}-1)}
m
{\displaystyle m}
G
F
(
q
)
n
{\displaystyle GF(q)^{n}}
d
−
1
{\displaystyle d-1}
d
−
1
{\displaystyle d-1}
ハルトマン-ツェング境界 が に対して の因数であり 、 が と 互いに素な整数である 場合。 （ および ）に対して スペクトル成分が ゼロとなる 重みまたはそれ以下の 内の 唯一のベクトルは 、全ゼロベクトルです。
n
{\displaystyle n}
(
q
m
−
1
)
{\displaystyle (q^{m}-1)}
m
{\displaystyle m}
b
{\displaystyle b}
n
{\displaystyle n}
v
{\displaystyle v}
G
F
(
q
)
n
{\displaystyle GF(q)^{n}}
d
−
1
{\displaystyle d-1}
V
j
{\displaystyle V_{j}}
j
=
ℓ
1
+
ℓ
2
b
(
mod
n
)
{\displaystyle j=\ell _{1}+\ell _{2}b(\mod n)}
ℓ
1
=
0
,
.
.
.
.
,
d
−
s
−
1
{\displaystyle \ell _{1}=0,....,d-s-1}
ℓ
2
=
0
,
.
.
.
.
,
s
−
1
{\displaystyle \ell _{2}=0,....,s-1}
ルース行き が、およびに対して の 因数である 場合。 および が 少なくとも の 範囲の値を取る、 に対して スペクトル成分が ゼロである 、 重みがまたはそれ以下の 内の唯一のベクトルは
、すべてゼロのベクトルです。
n
{\displaystyle n}
q
m
−
1
{\displaystyle q^{m}-1}
m
{\displaystyle m}
G
C
D
(
n
,
b
)
=
1
{\displaystyle GCD(n,b)=1}
G
F
(
q
)
n
{\displaystyle GF(q)^{n}}
d
−
1
{\displaystyle d-1}
V
j
{\displaystyle V_{j}}
j
=
l
1
+
l
2
b
(
mod
n
)
{\displaystyle j=l_{1}+l_{2}b(\mod n)}
l
1
=
0
,
.
.
.
,
d
−
s
−
2
{\displaystyle l_{1}=0,...,d-s-2}
l
2
{\displaystyle l_{2}}
s
+
1
{\displaystyle s+1}
0
,
.
.
.
.
,
d
−
2
{\displaystyle 0,....,d-2}
二次剰余コード 素数がを法とする平方剰余である 場合、長さ 、次元 、および最小重みが 以上 の巡回コードである 平方剰余コード が存在します 。
l
{\displaystyle l}
p
{\displaystyle p}
p
{\displaystyle p}
(
p
+
1
)
/
2
{\displaystyle (p+1)/2}
p
{\displaystyle {\sqrt {p}}}
G
F
(
l
)
{\displaystyle GF(l)}
一般化 コンスタ 巡回符号 は、ある定数 λ に対して ( c 1 ,c 2 ,..., c n ) が符号語であれば (λ c n ,c 1 ,..., c n -1 ) も符号語であるという性質を持つ線形符号です。 負巡回符号 は、 λ=-1 であるコンスタ巡回符号です。 [8] 準 巡回符号は、ある sに対して、符号語を s 桁巡回シフトすると 、再び符号語になる という性質を持っています。 [9] 二 重巡回符号は、 s =2である偶数長の準巡回符号です 。 [9] 準ツイスト符号 と マルチツイスト符号は、 コンスタ巡回 符号をさらに一般化したものです 。 [10] [11]
参照
注記
^ ヴァン・リント 1998、76 ページ ^ ヴァン・リント 1998、80ページ ^ ヒル 1988、159-160 ページ ^ Blahut 2003、定理 5.5.1 ^ ヒル 1988、162-163 ページ ^ P. Fire, E, P. (1959)。「 非独立エラーに対する多重エラー訂正バイナリコードのクラス」 Sylvania Reconnaissance Systems Laboratory、カリフォルニア州マウンテンビュー、レポート RSL-E-2、1959 年。 ^ Wei Zhou、Shu Lin、Khaled Abdel-Ghaffar。Fire コードとBCHコードに基づくバーストまたはランダムエラー訂正。ITA 2014：1-5 2013。 ^ ヴァン・リント 1998、75ページ ^ ab マクウィリアムズ & スローン 1977、p. 506 ^ Aydin, Nuh; Siap, Irfan; K. Ray-Chaudhuri, Dijen (2001). 「1 生成器の準ツイスト コードと新しい線形コードの構造」。 設計 、 コード、暗号化 。24 (3): 313–326。doi : 10.1023 /A:1011283523000。S2CID 17376783。 ^ Aydin, Nuh; Halilović, Ajdin ( 2017 ). 「準ツイストコードの一般化：マルチツイストコード」。 有限体とその応用 。45 ： 96–106。arXiv ： 1701.01044。doi ： 10.1016 / j.ffa.2016.12.002。S2CID 7694655 。
参考文献
さらに読む ランジャン・ボーズ 、情報理論、コーディング、暗号化 、 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 。 Scott A. Vanstone 、Paul C. Van Oorschot、 『誤り訂正符号入門とその応用』 、 ISBN 0-7923-9017-2
外部リンク John Gill (スタンフォード) の授業ノート – ノート #3、10 月 8 日、配布資料 #9、 Wayback Machine に 2012-10-23 にアーカイブ、EE 387。 ジョナサン・ホール（MSU）の授業ノート - 第8章 巡回コード - pp. 100 - 123 David Terr. 「巡回コード」 。MathWorld 。 この記事には、Creative Commons Attribution/Share-Alike License に基づいてライセンスされている PlanetMath の巡回コードの資料が組み込まれています 。
![{\displaystyle R=A[x]/(x^{n}-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8595f12ff1f64bc73a4e3e03851397cc877af6e2)
![{\displaystyle \mathbb {F} _{2}[x]/(x^{3}-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b419295ea611763fd442a22f8f56fe8dc30c023)
![{\displaystyle [2^{r}-1,2^{r}-r-2,4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbf755cb5b384b44e604aa2cc03660048b528348)
![{\displaystyle [(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6447e6a6ef3646859efcaa879911eae094aae869)
