Johnson bunden

I tillämpad matematik är Johnson bound (uppkallad efter Selmer Martin Johnson ) en gräns för storleken på felkorrigerande koder, som används i kodningsteori för dataöverföring eller kommunikation.

Definition

Låt $C$ vara en q -är kod med längden $n$ , dvs en delmängd av $\mathbb {F} _{q}^{n}$ . Låt $d$ vara det minsta avståndet för $C$ , dvs

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

där $d(x,y)$ är Hamming-avståndet mellan $x$ och $y$ .

Låt $C_{q}(n,d)$ vara mängden av alla q -ary-koder med längden $n$ och minsta avstånd $d$ och låt $C_{q}(n,d,w)$ betecknar uppsättningen koder i $C_{q}(n,d)$ såsom att varje element har exakt $w$ poster som inte är noll.

Beteckna med $|C|$ antalet element i $C$ . Sedan definierar vi $A_{q}(n,d)$ som den största storleken på en kod med längden $n$ och minsta avståndet $d$ :

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

På liknande sätt definierar vi $A_{q}(n,d,w)$ som den största storleken på en kod i $C_ {q}(n,d,w)$ :

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

Sats 1 (Johnson bunden för ${\displaystyle A_{q}(n,d)} )$ :

Om $d=2t+1$ ,

$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)}}}}.$

Om $d=2t+2$ ,

$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)}}}}.$

Sats 2 (Johnson bunden för ${\displaystyle A_{q}(n,d,w)} )$ :

(i) Om $d>2w,$

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

(ii) Om $d\leq 2w$ , definiera då variabeln $e$ enligt följande. Om $d$ är jämnt, definiera då $e$ genom relationen $d=2e$ ; om $d$ är udda, definiera $e$ genom relationen $d=2e-1$ . Låt $q^{*}=q-1$ . Sedan,

$A_q$

där $\lfloor ~~\rfloor$ är golvfunktionen .

Anmärkning: Att koppla in gränsen för sats 2 till gränsen för sats 1 ger en numerisk övre gräns på $A_{q}(n,d)$ .

Se även

• Singel bunden
• Hamming bunden
• Plotkin bunden
• Elias Bassalygo bunden
• Gilbert–Varshamov bunden
• Griesmer bunden

• Johnson, Selmer Martin (april 1962). "En ny övre gräns för felkorrigerande koder". IRE Transactions on Information Theory : 203–207.
•   Huffman, William Cary; Pless, Vera S. (2003). Grunderna för felkorrigerande koder . Cambridge University Press . ISBN 978-0-521-78280-7 .