Gilbert–Varshamov bunden

I kodningsteori är Gilbert –Varshamov-bunden (på grund av Edgar Gilbert och oberoende Rom Varshamov ) en gräns för parametrarna för en (inte nödvändigtvis linjär ) kod . Det är ibland känt som Gilbert- Shannon -Varshamov-bunden (eller GSV-bunden ), men namnet "Gilbert-Varshamov-bunden" är överlägset mest populärt. Varshamov bevisade detta bundet genom att använda den probabilistiska metoden för linjära koder. För mer om det beviset, se Gilbert–Varshamov bunden för linjära koder .

Uttalande av bunden

Låta

$A_{q}(n,d)$

beteckna den maximala möjliga storleken på en q -ary-kod $C$ med längden n och minsta Hamming-avstånd d (en q -ary-kod är en kod över fältet $\mathbb {F} _{q }$ av q- element).

Sedan:

$A_{q}(n,d)\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}( q-1)^{j}}}.$

Bevis

Låt $C$ vara en kod med längden $n$ och minsta Hamming-avstånd $d$ med maximal storlek:

$|C|=A_{q}(n,d).$

Sedan för alla ${\displaystyle x\in \mathbb {F} _{q}^{n}} , finns det$ minst ett kodord $c_{x}\in C$ så att Hamming-avståndet $d(x,c_{x})$ mellan $x$ och $c_{x}$ uppfyller

$d(x,c_{x})\leqslant d-1$

eftersom vi annars skulle kunna lägga till x till koden med bibehållande av kodens minsta Hamming-avstånd $d$ – en motsägelse om maximaliteten av $|C|$ .

ingår hela ${\displaystyle \mathbb {F} _{q}^{n}} i$ föreningen av alla kulor med radien $d-1$ med mitten på något $c\in C$ :

$\mathbb {F} _{q}^{n}=\bigcup _{c\in C}B(c,d-1).$

Nu har varje boll storlek

$\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{ j}$

eftersom vi kan tillåta (eller välja ) upp till $d-1$ av de $n$ komponenterna i ett kodord att avvika (från värdet på motsvarande komponent i bollens centrum ) till en av $(q-1)$ möjliga andra värden (kom ihåg: koden är q-ary: den tar värden i $\mathbb {F} _{q}^{n}$ ). Därför drar vi slutsatsen

$q^{n}=\left|\mathbb {F} _{q}^{n}\right|=\left|\bigcup _{c\in C}B(c,d-1)\right|\leqslant \sum _{c\in C}|B(c,d-1)|=|C|\summa _{j=0 }^{d-1}{\binom {n}{j}}(q-1)^{j}$

Det är:

$A_{q}(n,d)=|C|\geqslant {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{ j}}(q-1)^{j}}}.$

En förbättring i prime power case

För q en primpotens kan man förbättra bunden till $A_{q}(n,d)\geq q^{k}$ där k är det största heltal för vilket

$q^{k}<{\frac {q^{n}}{\sum _{j=0}^{d-2}{\binom {n-1}{j}}(q-1 )^{j}}}.$

Se även

• Singel bunden
• Hamming bunden
• Johnson bunden
• Plotkin bunden
• Griesmer bunden
• Grå–Rankin bunden
• Gilbert–Varshamov på väg mot linjära koder
• Elias-Bassalygo bunden