ジャステセンコード

バイナリ ジャステセン コード
名前の由来	ヨーン・ユステセン
分類
タイプ	線形ブロックコード
ブロック長	${\displaystyle n}$
メッセージの長さ	${\displaystyle k}$
レート	=${\displaystyle {\frac {R}{2}}={\frac {k}{2n}}}$
距離	${\displaystyle \delta n}$小さいところ。${\displaystyle \delta \geq {\Big (}1-R-\epsilon {\Big )}H_{2}^{-1}{\big (}{\frac {1}{2}}-\epsilon {\big )}\sim 0.11(1-R-\epsilon )}$${\displaystyle \epsilon >0}$
アルファベットのサイズ	2
表記	${\displaystyle \left[n,k/2,\delta n\right]_{2}}$-コード
プロパティ
一定の速度、一定の相対距離、一定のアルファベットサイズ
ヴ t e

符号理論において、ユステセン符号は、一定のレート、一定の相対距離、および一定のアルファベット サイズを持つ エラー訂正符号のクラスを形成します。

Justesen のエラー訂正コードが発見される前は、これら 3 つのパラメータすべてを定数として持つエラー訂正コードは知られていませんでした。

その後、この特性を持つ他の ECC コード、たとえばエクスパンダー コードが発見されました。これらのコードは、小さなバイアスのサンプル空間の構築など、コンピューター サイエンスの分野で重要な用途があります。

Justesen コードは、リード・ソロモン コードとWozencraft アンサンブルのコード連結として導出されます。

使用されるリード・ソロモン符号は、メッセージ長に 比例するアルファベット サイズを犠牲にして、一定のレートと一定の相対距離を実現します。

Wozencraftアンサンブルは、一定の速度と一定のアルファベット サイズを実現するコード ファミリですが、ファミリ内のほとんどのコードでは相対距離は一定です。

2 つのコードの連結では、まずリード・ソロモン コードを使用してメッセージをエンコードし、次にWozencraft アンサンブルのコードを使用してコードワードの各シンボルをさらにエンコードします。コードワードの各位置では、アンサンブルの異なるコードが使用されます。

これは、各位置の内部コードが同じである通常のコード連結とは異なります。Justesen コードは、対数空間のみを使用して非常に効率的に構築できます。

Justesen コードは、外部コードと異なる内部コードの連結です。 ${\displaystyle (N,K,D)_{q^{k}}}$${\displaystyle C_{out}}$${\displaystyle (n,k,d)_{q}}$${\displaystyle C_{in}^{i}}$${\displaystyle 1\leq i\leq N}$

より正確には、 で表されるこれらのコードの連結は次のように定義されます。 メッセージ が与えられた場合、外部コード によって生成されたコードワードを計算します 。${\displaystyle C_{out}\circ (C_{in}^{1},...,C_{in}^{N})}$${\displaystyle m\in [q^{k}]^{K}}$${\displaystyle C_{out}}$${\displaystyle C_{out}(m)=(c_{1},c_{2},..,c_{N})}$

次に、N 個の線形内部コードの各コードをそのコードワードの各座標に適用して、最終的なコードワードを生成します。 つまり、${\displaystyle C_{out}\circ (C_{in}^{1},..,C_{in}^{N})(m)=(C_{in}^{1}(c_{1}),C_{in}^{2}(c_{2}),..,C_{in}^{N}(c_{N}))}$

外部コードと線形内部コードの定義を振り返ってみると、外部コードのコードワードは要素を持つベクトルであり、それらの要素に適用する線形内部コードがあるため、この Justesen コードの定義は理にかなっています。 ${\displaystyle N}$${\displaystyle N}$${\displaystyle N}$

ここで、Justesen コードの場合、外部コードは、レート、< <で評価されるフィールド上のリード ソロモン コードとして選択されます。 ${\displaystyle C_{out}}$ ${\displaystyle \mathbb {F} _{q^{k}}}$${\displaystyle \mathbb {F} _{q^{k}}-\{0\}}$ ${\displaystyle R}$${\displaystyle 0}$${\displaystyle R}$${\displaystyle 1}$

外側の符号の相対距離とブロック長はです。内側の符号のセットはWozencraft アンサンブルです。 ${\displaystyle C_{out}}$${\displaystyle \delta _{out}=1-R}$${\displaystyle N=q^{k}-1}$ ${\displaystyle \{C_{in}^{\alpha }\}_{\alpha \in \mathbb {F} _{q^{k}}^{*}}}$

ウォンゼンクラフト アンサンブルの線形符号のレートが であるため、ジャステセン コードはレート の連結符号です。連結符号の距離を推定する次の定理が成り立ちます。 ${\displaystyle {\frac {1}{2}}}$${\displaystyle C^{*}=C_{out}\circ (C_{in}^{1},C_{in}^{2},..,C_{in}^{N})}$${\displaystyle {\frac {R}{2}}}$${\displaystyle C^{*}}$

すると、相対距離は少なくとも${\displaystyle \varepsilon >0.}$${\displaystyle C^{*}}$${\displaystyle (1-R-\varepsilon )H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right).}$

符号の距離の下限を証明するために、任意の異なる符号語のペアのハミング距離に下限があることを証明します。つまり、2つの符号語のハミング距離を、 とします。任意の与えられた ${\displaystyle C^{*}}$${\displaystyle \Delta (c^{1},c^{2})}$${\displaystyle c^{1}}$${\displaystyle c^{2}}$

${\displaystyle m_{1}\neq m_{2}\in \left(\mathbb {F} _{q^{k}}\right)^{K},}$

下限値を求めている${\displaystyle \Delta (C^{*}(m_{1}),C^{*}(m_{2})).}$

の場合、 となることに注意してください。したがって、下限については、 の距離を考慮する必要があります。${\displaystyle C_{out}(m)=(c_{1},\cdots ,c_{N})}$${\displaystyle C^{*}(m)=(C_{in}^{1}(c_{1}),\cdots ,C_{in}^{N}(c_{N}))}$${\displaystyle \Delta (C^{*}(m_{1}),C^{*}(m_{2}))}$${\displaystyle C_{in}^{1},\cdots ,C_{in}^{N}.}$

仮定する

${\displaystyle {\begin{aligned}C_{out}(m_{1})&=\left(c_{1}^{1},\cdots ,c_{N}^{1}\right)\\C_{out}(m_{2})&=\left(c_{1}^{2},\cdots ,c_{N}^{2}\right)\end{aligned}}}$

はWozencraftアンサンブルであることを思い出してください。「Wozencraftアンサンブル定理」により、少なくとも距離を持つ線形コードが存在します。したがって、あるに対して、コードに距離がある場合、 ${\displaystyle \left\{C_{in}^{1},\cdots ,C_{in}^{N}\right\}}$${\displaystyle (1-\varepsilon )N}$${\displaystyle C_{in}^{i}}$${\displaystyle H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$${\displaystyle 1\leqslant i\leqslant N,c_{i}^{1}\neq c_{i}^{2}}$${\displaystyle C_{in}^{i}}$${\displaystyle \geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k,}$

${\displaystyle \Delta \left(C_{in}^{i}\left(c_{i}^{1}\right),C_{in}^{i}\left(c_{i}^{2}\right)\right)\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$

さらに、もしそのような数値があり、コードに距離がある場合、 ${\displaystyle T}$${\displaystyle 1\leqslant i\leqslant N}$${\displaystyle c_{i}^{1}\neq c_{i}^{2}}$${\displaystyle C_{in}^{i}}$${\displaystyle \geqslant H_{q}^{-1}({\tfrac {1}{2}}-\varepsilon )\cdot 2k,}$

${\displaystyle \Delta \left(C^{*}(m_{1}),C^{*}(m_{2})\right)\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot T.}$

最後のタスクは、 の下限を見つけることです。定義: ${\displaystyle T}$

${\displaystyle S=\left\{i\ :\ 1\leqslant i\leqslant N,c_{i}^{1}\neq c_{i}^{2}\right\}.}$

すると、距離を持つ線形コードの数は${\displaystyle T}$${\displaystyle C_{in}^{i},i\in S}$${\displaystyle H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$

ここで、明らかに推定したいことがあります。 ${\displaystyle |S|.}$${\displaystyle |S|=\Delta (C_{out}(m_{1}),C_{out}(m_{2}))\geqslant (1-R)N}$

ウォゼンクラフトアンサンブル定理により、距離がこれ より小さい線形コードは最大で${\displaystyle \varepsilon N}$${\displaystyle H_{q}^{-1}({\tfrac {1}{2}}-\varepsilon )\cdot 2k,}$

${\displaystyle T\geqslant |S|-\varepsilon N\geqslant (1-R)N-\varepsilon N=(1-R-\varepsilon )N.}$

最後に、

${\displaystyle \Delta (C^{*}(m_{1}),C^{*}(m_{2}))\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot T\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot (1-R-\varepsilon )\cdot N.}$

これは任意の に対して当てはまります。相対距離も少なくとも なので、これで証明は完了です。 ${\displaystyle m_{1}\neq m_{2}}$${\displaystyle C^{*}}$${\displaystyle (1-R-\varepsilon )H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right),}$

「強く明示的なコード」について考えてみましょう。そこで疑問となるのは、「強く明示的なコード」とは何かということです。大まかに言えば、線形コードの場合、「明示的」な特性は、その生成行列 G を構築する複雑さに関連しています。

つまり、コードが所定の距離を満たしているかどうかを確認するために、ブルート フォース アルゴリズムを使用せずに、対数空間で行列を計算できることになります。

線形ではないその他のコードについては、エンコード アルゴリズムの複雑さを考慮することができます。

これまでのところ、ウォンゼンクラフト アンサンブルとリード ソロモン コードは強力に明示的であることがわかります。したがって、次の結果が得られます。

帰結:連結コードは漸近的に良いコード(つまり、小さい q に対してレート> 0 かつ相対距離> 0)であり、非常に明示的な構成を持ちます。 ${\displaystyle C^{*}}$${\displaystyle R}$${\displaystyle \delta }$

次のわずかに異なるコードは、MacWilliams/MacWilliams では Justesen コードと呼ばれています。これは、非常に特殊な Wonzencraft アンサンブルに対する、上で検討した Justesen コードの特殊なケースです。

Rを長さN = 2 ^m  − 1、ランク K、最小重みN  −  K + 1のリード・ソロモン符号とする 。

RのシンボルはF = GF(2 ^m )の元であり、コードワードはK未満の次数のF上のすべての多項式ƒを取り、 Fの非ゼロ元上のƒの値を所定の順序でリストすることによって得られます。

α をFの原始元とする。 Rからのコードワードa = ( a ₁ , ...,  a _N )に対して、b をF上の長さ 2 Nのベクトルとし、次のように 表される。

${\displaystyle \mathbf {b} =\left(a_{1},a_{1},a_{2},\alpha ^{1}a_{2},\ldots ,a_{N},\alpha ^{N-1}a_{N}\right)}$

そして、Fの各要素を長さmのバイナリベクトルとして表現することでbから得られる長さ 2 N mのベクトルをcとします。Justesenコードは、このようなc をすべて含む線形コードです。

このコードのパラメータは長さ2mN 、寸法 mK 、最小距離は少なくとも

${\displaystyle \sum _{i=1}^{\ell }i{\binom {2m}{i}},}$

ここで はを満たす最大の整数です。(証明については MacWilliams/MacWilliams を参照してください。) ${\displaystyle \ell }$${\displaystyle \sum _{i=1}^{\ell }{\binom {2m}{i}}\leq N-K+1}$

• 連結されたエラー訂正コード
• 線形コード
• リード・ソロモン誤り訂正
• ウーゼンクラフトアンサンブル

• 講義 28: Justesen コード。コーディング理論のコース。Atri Rudra 教授。
• 講義 6: 連結コード。Forney コード。Justesen コード。基本的な符号理論。
• J. Justesen (1972). 「構成的に漸近的に良好な代数符号のクラス」IEEE Trans. Inf. Theory . 18 (5): 652–656. doi :10.1109/TIT.1972.1054893.
• FJ MacWilliams ; NJA Sloane (1977)。誤り訂正符号の理論。ノースホランド。pp. 306–316。ISBN 0-444-85193-3。