Johnsons gräns

Johnson - gränsen definierar effektgränsen för längdkoden och minimiavståndet . $n$ $d$

Formulering

Låt vara den -: e längdkoden över fältet , eller med andra ord delmängden av . Låt vara det minsta kodavståndet , dvs. $C$ $q$ $n$ $\mathbb{F} = \mathrm{GF}(q)$ ${\mathbb {F}}_{q}^{n}$ $d$ $C$

d = \min_{x,y \i C, \; x \neq y} \mathsf{d}(x,y)

var är Hamming-avståndet mellan kodord och . $\mathsf{d}(x,y)$ $x$ $y$

Låta vara uppsättningen av all -th koder av längd och minsta avstånd , och låt beteckna delmängden av alla jämviktskoder i , Med andra ord, alla koder vars vikt av alla kodord är lika med . $C_q(n,d)$ $q$ $n$ $d$ $C_q(n,d,w)$ $C_q(n,d)$ $w$

Låt oss beteckna med antalet kodord i , och med — längdkodens maximala kardinalitet och minsta avstånd , d.v.s. $|C|$ $C$ $A_q(n,d)$ $n$ $d$

A_q(n,d) = \max_{C \in C_q(n,d)} |C|.

På liknande sätt definierar vi som kodens maximala effekt i : $A_q(n,d,w)$ $C_q(n,d,w)$

A_q(n,d,w) = \max_{C \in C_q(n,d,w)} |C|.

Sats 1 (Johnson på väg till ): $A_q(n,d)$

På $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} - {d \choose t} A_q(n,d,d)}{A(n,d,t+1)}(q - 1)^{t + 1} }.

Obs: för att hitta den övre gränsen för jämna värden kan du använda följande likhet $A_q(n,d)$ $d=2t$

A_q(n,2t) = A_q(n-1,2t-1).

Sats 2 (Johnson på väg mot ): $A_q(n,d,w)$

På $d > 2w$

A_q(n,d,w) = 1.

När låt , och även , då $d\leq 2w$ $t = \lceil \frac{d}{2}\rceil$ $q^* = q - 1$

A_q(n,d,w) \leq \lfloor \frac{nq^*}{w} \lfloor \frac{(n-1)q^*}{w-1} \lfloor \cdots \lfloor \frac{ (n-w+t)q^*}{t} \rgolv \cdots \rgolv \rgolv,

där operatorn anger heltalsdelen av ett tal . $\lgolv ~~ \rgolv$

Notera: Genom att ersätta sats 2 med sats 1 får vi en övre gräns för . $A_q(n,d)$

Bevis för den första satsen

Låta vara en kod för längd , makt med minsta avstånd , som innehåller en noll vektor. Beteckna med uppsättningen vektorer som är på avstånd från koden , det vill säga, $C$ $n$ $M = A_q(n, d)$ $d=2t+1$ $Si}$ $i$ $C$

S_i = \left\lbrace u \in F^n: \forall v \in C\ d(u, v) \geq i \wedge \exists w \in C\ d(w, u) = i \right\rbrace .

Alltså ,. Sedan , eftersom om det fanns en vektor på ett avstånd eller mer från koden , så skulle vi kunna lägga till den och få en kod med ännu större kraft. Eftersom uppsättningarna inte skär varandra, innebär detta gränsen för den sfäriska packningen . För att erhålla den önskade gränsen uppskattar vi effekten . $S_0 = C$ $S_0 \cup S_1 \cup \dots \cup S_{d - 1} = F^n$ $d$ $C$ $C$ $S_0, S_1, S_2, \dots, S_t$ $S_{t + 1}$

Låt oss välja ett godtyckligt kodord och genom lämplig förskjutning av koden kommer vi att överföra det till koordinaternas ursprung. Viktkodord bildar en jämviktskod med ett minimiavstånd på minst , och därför överstiger inte antalet viktkodord . $P$ $d=2t+1$ $2t+1$ $d$ $A_q(n, 2t + 1, 2t + 1) = A_q(n, d, d)$

Beteckna med uppsättningen viktvektorer . Vilken vektor som helst från tillhör antingen , eller . Varje viktkodord motsvarar viktvektorer som är på avstånd från . $W_{t + 1}$ $F^{n}$ $t+1$ $W_{t + 1}$ $S_t$ $S_{t + 1}$ $F$ $d$ ${ d \välj t }$ $t+1$ $F$ $t$

Alla dessa vektorer är olika och tillhör mängden . Följaktligen, $W_{t + 1} \cap S_t$

|W_{t + 1} \cap S_{t+1}| = |W_{t + 1}| - |W_{t + 1} \cap S_t| \geq {n \välj t + 1}(q - 1)^{t + 1} - {d \välj t}(q - 1)^{t + 1} A_q(n, d, d).

Vektorn från mängden är på ett avstånd av inte mer än från kodorden. Låt oss faktiskt flytta ursprunget till en punkt och beräkna hur många kodord som kan vara på avstånd från och ha ett Hamming-avstånd mellan dem . De borde per definition inte vara fler . Därför kan vektorer från uppsättningen räknas vid de flesta tidpunkter, det vill säga varje kodord motsvarar åtminstone $R$ $W_{t + 1} \cap S_{t+1}$ $t+1$ $A_q(n,d,t+1)$ $R$ $R$ $t+1$ $d$ $A_q(n,d,t+1)$ $W_{t + 1} \cap S_{t+1}$ $A_q(n,d,t+1)$ $P$

\frac{{n \choose t+1} - {d \choose t} A_q(n,d,d)}{A(n,d,t+1)}(q - 1)^{t + 1}

olika vektorer på avstånd från . $t+1$ $P$

Litteratur

S. Johnson, En ny övre gräns för felkorrigerande koder, IRE Transactions on Information Theory , 203–207, april 1962.
FJ MacWilliams och NJA Sloane, The Theory of Error-Correcting Codes , Amsterdam, Nederländerna, Nord-Holland, § 17.2, § 17.3, 1977.
W.C. Huffman, V. Pless, Fundamentals of Error-Correcting Codes , Cambridge University Press, 2003.

Johnsons gräns

Formulering

Bevis för den första satsen

Litteratur

Se även