ジョンソン行き

応用数学において、ジョンソン境界（セルマー・マーティン・ジョンソンにちなんで名付けられた）は、データ伝送や通信の符号理論で使用される誤り訂正符号のサイズの制限である。

を長さ のq元符号、つまり のサブセットとします。を の最小距離、つまり ${\displaystyle C}$${\displaystyle n}$${\displaystyle \mathbb {F} _{q}^{n}}$${\displaystyle d}$${\displaystyle C}$

${\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y),}$

ここで、と の間のハミング距離です。 ${\displaystyle d(x,y)}$${\displaystyle x}$${\displaystyle y}$

長さと最小距離を持つすべてのq元符号の集合を とし、すべての要素が正確にゼロ以外のエントリを持つ内の符号の集合を とします。 ${\displaystyle C_{q}(n,d)}$${\displaystyle n}$${\displaystyle d}$${\displaystyle C_{q}(n,d,w)}$${\displaystyle C_{q}(n,d)}$${\displaystyle w}$

を の要素数で表します。次に、を長さと最小距離 を持つコードの最大サイズ と定義します。 ${\displaystyle |C|}$${\displaystyle C}$${\displaystyle A_{q}(n,d)}$${\displaystyle n}$${\displaystyle d}$

${\displaystyle A_{q}(n,d)=\max _{C\in C_{q}(n,d)}|C|.}$

同様に、を におけるコードの最大サイズとして定義します。 ${\displaystyle A_{q}(n,d,w)}$${\displaystyle C_{q}(n,d,w)}$

${\displaystyle A_{q}(n,d,w)=\max _{C\in C_{q}(n,d,w)}|C|.}$

定理1（ジョンソン限界）:${\displaystyle A_{q}(n,d)}$

もし、 ${\displaystyle d=2t+1}$

${\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}-{d \choose t}A_{q}(n,d,d)}{A_{q}(n,d,t+1)}}}}.}$

もし、 ${\displaystyle d=2t+2}$

${\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}}{A_{q}(n,d,t+1)}}}}.}$

定理2（ジョンソン限界）:${\displaystyle A_{q}(n,d,w)}$

（i）もし${\displaystyle d>2w,}$

${\displaystyle A_{q}(n,d,w)=1.}$

(ii)の場合、変数を次のように定義します。 が偶数の場合、関係 を通じて定義します。が奇数の場合、関係 を通じて定義します。 とします。すると、 ${\displaystyle d\leq 2w}$${\displaystyle e}$${\displaystyle d}$${\displaystyle e}$${\displaystyle d=2e}$${\displaystyle d}$${\displaystyle e}$${\displaystyle d=2e-1}$${\displaystyle q^{*}=q-1}$

${\displaystyle A_{q}(n,d,w)\leq \left\lfloor {\frac {nq^{*}}{w}}\left\lfloor {\frac {(n-1)q^{*}}{w-1}}\left\lfloor \cdots \left\lfloor {\frac {(n-w+e)q^{*}}{e}}\right\rfloor \cdots \right\rfloor \right\rfloor \right\rfloor }$

床関数はどこですか？ ${\displaystyle \lfloor ~~\rfloor }$

注意:定理 2 の境界を定理 1 の境界に代入すると、 の数値的な上限が生成されます。 ${\displaystyle A_{q}(n,d)}$

• エリアス・バサリゴは拘束される
• ギルバート・ヴァルシャモフ境界
• グリースマー行き
• ハミング境界
• プロトキン縛り
• シングルトンバウンド

• ジョンソン、セルマー・マーティン(1962 年 4 月)。「誤り訂正符号の新しい上限」。IRE Transactions on Information Theory : 203–207。
• ハフマン、ウィリアム・ケアリー、プレス、ヴェラ・S（2003）。誤り訂正符号の基礎。ケンブリッジ大学出版局。ISBN 978-0-521-78280-7。