Elias Bassalygo bunden

Elias Bassalygo-gränsen är en matematisk gräns som används i kodningsteori för felkorrigering under dataöverföring eller kommunikation.

Definition

Låt $C$ vara en $q$ -är kod med längden $n$ , dvs en delmängd av $[q]^{n}$ . Låt $R$ vara hastigheten för $C$ , $\delta$ det relativa avståndet och

$B_{q}(y,\rho n)=\left\{x\in [ q]^{n}\ :\ \Delta (x,y)\leqslant \rho n\right\}$

vara Hamming-kulan med radien $\rho n$ centrerad vid $y$ . Låt ${\displaystyle {\text{Vol}}_{q}(y,\rho n)=|B_{q}(y,\rho n)|} vara volymen för Hamming-kulan med$ radien ρ n $displaystyle \rho n}$ . Det är uppenbart att volymen på en Hamming Ball är translationsinvariant, dvs likgiltig för $y.$ I synnerhet $|B_{q}(y,\rho n)|=|B_{q}(0,\rho n)|.$

Med tillräckligt stor ${\displaystyle n} uppfyller$ hastigheten $R$ och det relativa avståndet $\delta$ Elias -Bassalygo-gränsen :

$R\leqslant 1-H_{q}(J_{q}(\delta))+o(1),$

var

$H_{q}(x)\equiv _{\text{def }}-x\log _{q}\left({x \över {q-1}}\right)-(1-x)\log _{q}{(1-x)}$

är q -är entropifunktionen och

$J_{q}(\delta )\equiv _{\text{def}}\left(1- {1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)$

är en funktion relaterad till Johnson bunden .

Bevis

För att bevisa Elias–Bassalygo-bunden, börja med följande Lemma:

Lemma. För $C\subseteq [q]^{n}$ och $0\leqslant e\leqslant n$ , finns det en Hamming-kula med radien $e$ med minst

${\displaystyle {\frac {|C|{\text{Vol}}_{q}(0,e)}{q^{n}}}} kodord i den$

.

Bevis på Lemma. Välj slumpmässigt ett mottaget ord $y\in [q]^{n}$ och låt $B_{q}(y,0)$ vara Hamming-bollen centrerad vid $y$ med radien $e$ . Eftersom $y$ är (uniform) slumpmässigt valt den förväntade storleken på det överlappade området $|B_{q}(y,e)\cap C|$ är

${\displaystyle {\frac {|C|{\text{Vol}}_{q}(y,e)}{q^{n}}}} Eftersom detta är den$

förväntade storleken, måste det finnas minst en $y$ så att

${\displaystyle |B_{q}(y,e)\cap C|\geqslant {{|C|{\text{Vol}}_{q}(y,e)} \over {q^{n}}}={{|C|{\text{Vol}}_{q}(0,e)} \over {q^{n}}},} annars måste förväntningen$

vara mindre än detta värde.

Nu bevisar vi Elias–Bassalygo-bunden. Definiera $e=nJ_{q}(\delta )-1.$ Av Lemma finns det en Hamming-boll med $B$ -kodord så att:

$B\geqslant {{|C|{\text{Vol}}(0,e)} \över {q^{n}}}$

Med Johnson-gränsen har vi $B\leqslant qdn$ . Således,

$|C|\leqslant qnd\cdot {{q^{ n}} \över {{\text{Vol}}_{q}(0,e)}}\leqslant q^{n(1-H_{q}(J_{q}(\delta ))+o( 1))}$

Den andra ojämlikheten följer av den nedre gränsen för volymen av en Hamming-boll:

${\text{Vol}}_{q}\left(0,\left\lfloor {\frac {d-1}{2}}\right\rfloor \right)\geqslant q^{H_{q }\left({\frac {\delta }{2}}\right)no(n)}.$

Att sätta in $d=2e+1$ och $\delta ={\tfrac {d}{n}}$ ger den andra olikheten.

Därför har vi

$R={\log _{q}{|C|} \över n}\leqslant 1-H_{q}(J_{ q}(\delta ))+o(1)$

Se även

• Singel bunden
• Hamming bunden
• Plotkin bunden
• Gilbert–Varshamov bunden
• Johnson bunden

gränser för felkorrigerande koder", Problems of Information Transmission , 1 (1): 32–35

Claude E. Shannon, Robert G. Gallager; Berlekamp, ​​Elwyn R. (1967), "Lägre gränser för felsannolikhet för kodning på diskreta minneslösa kanaler. Del I.", Information and Control , 10 : 65–103, doi : 10.1016/s0019-9958(67)90052-6

Claude E. Shannon, Robert G. Gallager; Berlekamp, ​​Elwyn R. (1967), "Lägre gränser för felsannolikhet för kodning på diskreta minneslösa kanaler. Del II.", Information and Control , 10 : 522–552, doi : 10.1016/s0019-9958(67)91200-4