ブロックコード

エンコードされるデータストリームは、何らかのアルファベット上の文字列としてモデル化される。${\displaystyle \Sigma }$サイズ${\displaystyle |\Sigma |}$アルファベットの は、しばしば次のように書かれます。${\displaystyle q}$。 もし${\displaystyle q=2}$ブロックコードはバイナリブロックコードと呼ばれます。多くのアプリケーションでは、${\displaystyle q}$主要な勢力となること、そして特定すること${\displaystyle \Sigma }$有限体$\displaystyle \mathbb {F} _{q}}$。

メッセージは要素です${\displaystyle m}$の$\displaystyle \Sigma ^{k}}$つまり、長さの文字列${\displaystyle k}$したがって、その数は${\displaystyle k}$これはブロックコードのメッセージ長または次元と呼ばれます。

ブロックの長さ${\displaystyle n}$ブロックコードの要素は、ブロック内のシンボルの数です。したがって、要素${\displaystyle c}$の$\displaystyle \Sigma ^{n}}$長さの文字列です${\displaystyle n}$そして、受信側が受信する可能性のあるブロックに対応します。したがって、これらは受信ワードとも呼ばれます。${\displaystyle c=C(m)}$メッセージの一部${\displaystyle m}$、 それから${\displaystyle c}$はコードワードと呼ばれます${\displaystyle m}$。

ブロック符号のレートは、メッセージ長とブロック長の比として定義される。

${\displaystyle R=k/n}$。

レートが大きいということは、送信されるブロックあたりの実際のメッセージ量が多いことを意味します。この意味で、レートは送信速度と量の両方を測定します。${\displaystyle 1-R}$ブロックコードによるエンコードによって発生するオーバーヘッドを測定します。レートが超えることができないのは、単純な情報理論的事実です。${\displaystyle 1}$データは一般に可逆的に圧縮できないため。形式的には、これはコードが${\displaystyle C}$これは単射写像です。

ブロックコードの距離または最小距離dは、 2 つの異なるコードワードが異なる最小位置数であり、相対距離は${\displaystyle \delta }$分数は${\displaystyle d/n}$正式には、受け取られた言葉について$\displaystyle c_{1},c_{2}\in \Sigma ^{n}}$、 させて${\displaystyle \Delta (c_{1},c_{2})}$ハミング距離を表す。${\displaystyle c_{1}}$そして${\displaystyle c_{2}}$つまり、${\displaystyle c_{1}}$そして${\displaystyle c_{2}}$異なる。次に最小距離${\displaystyle d}$コードの${\displaystyle C}$は次のように定義される。

${\displaystyle d:=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]}$。

コードは単射でなければならないので、任意の 2 つのコードワードは少なくとも 1 つの位置で一致しないため、任意のコードの距離は少なくとも${\displaystyle 1}$さらに、線形ブロック符号の場合、距離は最小重みに等しくなります。理由は以下のとおりです。

${\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [\mathbf {0} ,C(m_{2})-C(m_{1})]=\min _{m\in \Sigma ^{k} \atop m\neq \mathbf {0} }w[C(m)]=w_{\min }}$。

距離が大きいほど、より多くの誤り訂正と検出が可能になります。たとえば、送信された符号語のシンボルを変更するだけで、消去や追加はしない誤りだけを考慮すると、誤りの数は、送信された符号語と受信された符号語が異なる位置の数になります。距離dの符号では、受信機は最大で${\displaystyle d-1}$変更後の伝送エラー${\displaystyle d-1}$符号語の位置が偶然別の符号語を生み出すことは決してない。さらに、${\displaystyle (d-1)/2}$伝送エラーが発生した場合でも、受信機は受信した単語を一意に復号して符号語に変換できます。これは、受信した単語は距離に応じて最大で1つの符号語しか持たないためです。${\displaystyle (d-1)/2}$. を超える場合${\displaystyle (d-1)/2}$伝送エラーが発生すると、受信側では受信した単語を一意に復号できない場合があります。これは、複数の符号語が存在する可能性があるためです。受信側がこの状況に対処する方法の一つとして、リスト復号があります。リスト復号では、復号器は一定の範囲内にあるすべての符号語のリストを出力します。

表記法${\displaystyle (n,k,d)_{q}}$アルファベット上のブロックコードを表す${\displaystyle \Sigma }$サイズの${\displaystyle q}$ブロック長${\displaystyle n}$メッセージの長さ${\displaystyle k}$距離${\displaystyle d}$ブロックコードが線形ブロックコードの場合、表記の角括弧は${\displaystyle [n,k,d]_{q}}$は、その事実を表すために使用されます。バイナリコードの場合、${\displaystyle q=2}$インデックスは時々削除されます。最大距離分離可能コードの場合、距離は常に${\displaystyle d=n-k+1}$しかし、正確な距離が不明な場合、証明または述べるのが困難な場合、または必要でない場合もあります。そのような場合、${\displaystyle d}$コンポーネントが不足している可能性があります。

特に非ブロックコードの場合、表記法${\displaystyle (n,M,d)_{q}}$含まれるコードに使用されます${\displaystyle M}$長さのコードワード${\displaystyle n}$長さが一定のメッセージを持つブロックコードの場合${\displaystyle k}$サイズのアルファベット以上${\displaystyle q}$この数字は${\displaystyle M=q^{k}}$。

${\displaystyle C=\{C_{i}\}_{i\geq 1}}$これは符号のファミリーと呼ばれ、${\displaystyle C_{i}}$は${\displaystyle (n_{i},k_{i},d_{i})_{q}}$単調増加するコード${\displaystyle n_{i}}$。

コードファミリーCのレートは次のように定義されます。${\displaystyle R(C)=\lim _{i\to \infty }{k_{i} \over n_{i}}}$

コードファミリーCの相対距離は次のように定義される。${\displaystyle \delta (C)=\lim _{i\to \infty }{d_{i} \over n_{i}}}$

関係性を探るために${\displaystyle R(C)}$そして${\displaystyle \delta (C)}$ブロック符号の下限値と上限値が既知である。

${\displaystyle R\leq 1-{1 \over n}\cdot \log _{q}\cdot \left[\sum _{i=0}^{\left\lfloor {{\delta \cdot n-1} \over 2}\right\rfloor }{\binom {n}{i}}(q-1)^{i}\right]}$

シングルトン境界とは、ブロック符号のレートと相対距離の合計が1よりはるかに大きくなることはない、というものである。

${\displaystyle R+\delta \leq 1+{\frac {1}{n}}}$。

言い換えれば、すべてのブロックコードは次の不等式を満たす。${\displaystyle k+d\leq n+1}$リード・ソロモン符号は、等号で単一点境界を満たす符号の非自明な例である。

のために${\displaystyle q=2}$、${\displaystyle R+2\delta \leq 1}$。 言い換えると、${\displaystyle k+2d\leq n}$。

一般的な場合、任意のに対して以下のプロトキン境界が成り立つ。${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$距離dで：

1. もし${\displaystyle d=\left(1-{1 \over q}\right)n,|C|\leq 2qn}$
2. もし${\displaystyle d>\left(1-{1 \over q}\right)n,|C|\leq {qd \over {qd-\left(q-1\right)n}}}$

距離がq進コードの場合${\displaystyle \delta }$、${\displaystyle R\leq 1-\left({q \over {q-1}}\right)\delta +o\left(1\right)}$

${\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }$、 どこ${\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \right)}$、 ${\displaystyle H_{q}\left(x\right)~{\overset {\underset {\mathrm {def} }{}}{=}}~-x\cdot \log _{q}{x \over {q-1}}-\left(1-x\right)\cdot \log _{q}{\left(1-x\right)}}$これはq項エントロピー関数です。

定義する${\displaystyle J_{q}\left(\delta \right)~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(1-{1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)}$。 させて${\displaystyle J_{q}\left(n,d,e\right)}$任意の符号について、半径eのハミング球内の符号語の最大数とする。${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$距離dの。

次に、ジョンソン・バウンドがあります 。${\displaystyle J_{q}\left(n,d,e\right)\leq qnd}$、 もし${\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\,\right)=J_{q}\left({d \over n}\right)}$

${\displaystyle R={\log _{q}{|C|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta \right)\right)+o\left(1\right)}$