Wozencraft ensemble

I kodningsteori är Wozencraft -ensemblen en uppsättning linjära koder där de flesta koder uppfyller Gilbert-Varshamov-gränsen . Den är uppkallad efter John Wozencraft , som bevisade sin existens. Ensemblen beskrivs av Massey (1963) , som tillskriver den Wozencraft. Justesen (1972) använde Wozencraft-ensemblen som de inre koderna i sin konstruktion av starkt explicit asymptotiskt bra kod.

Existenssats

Sats: Låt $\varepsilon >0.$ För en tillräckligt stor ${\displaystyle k} ,$ finns det en ensemble av inre koder $C_{ i}^{1},\cdots ,C_{in}^{N}$ av hastighet ${\tfrac {1}{2}}$ , där $N= q^{k}-1$ , så att för åtminstone $(1-\varepsilon )N$ värden på $i,C_{in}^{ i}$ har relativt avstånd $\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)$ .

Här är det relativa avståndet förhållandet mellan minsta avstånd och blocklängd. Och $H_{q}$ är q-ary entropifunktionen definierad enligt följande:

$H_{q}(x)=x\log _{q}(q-1)-x\log _{q}x-(1-x)\log _{q}(1-x).$

I själva verket, för att visa existensen av denna uppsättning linjära koder, kommer vi att specificera denna ensemble uttryckligen enligt följande: för $\alpha \in \mathbb {F} _{q^{k }}-\{0\}$ , definiera den inre koden

${\begin{cases}C_{in}^{\alpha }:\mathbb { F} _{q}^{k}\to \mathbb {F} _{q}^{2k}\\C_{in}^{\alpha }(x)=(x,\alpha x)\end{ fall}}$

Här kan vi lägga märke till att $x\in \mathbb {F} _{q}^{k}$ och $\alpha \in \mathbb {F} _{ q^{k}}$ . Vi kan göra multiplikationen $\alpha x$ eftersom $\mathbb {F} _{q}^{k}$ är isomorf till $\mathbb {F} _ {q^{k}}$ .

Denna ensemble beror på Wozencraft och kallas Wozencraft-ensemblen.

För alla ${\displaystyle x,y\in \mathbb {F} _{q}^{k}} ,$ har vi följande fakta:

1. $C_{in}^{\alpha }(x)+C_{in}^{\alpha }(y)=(x,\alpha x)+(y,\alpha y)=(x+ y,\alfa (x+y))=C_{in}^{\alpha}(x+y)$
2. För vilken som helst $a\in \ mathbb {F} _{q},aC_{in}^{\alpha }(x)=a(x,\alpha x)=(ax,\alpha (ax))=C_{in}^{\alpha } (yxa)$

Så $C_{in}^{\alpha }$ är en linjär kod för varje $\alpha \in \mathbb {F} _{q^{k }}-\{0\}$ .

Nu vet vi att Wozencraft-ensemblen innehåller linjära koder med hastigheten ${\tfrac {1}{2}}$ . I följande bevis kommer vi att visa att det finns åtminstone $(1-\varepsilon )N$ de linjära koder som har det relativa avståndet ${\ displaystyle \geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)} ,$ dvs de möter Gilbert-Varshamov-bunden.

Bevis

För att bevisa att det finns minst $(1-\varepsilon )N$ antal linjära koder i Wozencraft-ensemblen som har ett relativt avstånd ${\displaystyle \ geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)} ,$ kommer vi att bevisa att det finns högst $\varepsilon N$ antal linjära koder som har relativt avstånd $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)$ dvs. , med avstånd $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$

Observera att i en linjär kod är avståndet lika med minimivikten för alla kodord i den koden. Detta faktum är linjär kods egenskap . Så om ett kodord som inte är noll har vikt $<H_{q}^{-1}\left({\tfrac {1}{2}}- \varepsilon \right)\cdot 2k$ , då har den koden avstånd $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$

Låt $P$ vara uppsättningen linjära koder med avstånd $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$ Sedan finns det $|P|$ linjära koder som har något kodord som har vikt $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.$

Lemma. Två linjära koder $C_{in}^{\alpha _{1}}$ och $C_{in}^{\alpha _{2}}$ med $\alpha _{1},\alpha _{2}\in \mathbb {F} _{q^{k}}$ distinkt och icke-noll, dela inga kodord som inte är noll.

Bevis. Anta att det finns distinkta icke-nollelement $\alpha _{1},\alpha _{2}\i \mathbb {F} _{q^{k}}$ såsom att de linjära koderna $C_{in}^{\alpha _{1}}$ och $C_{in}^{\alpha _{2}}$ innehåller samma kodord som inte är noll $y.$ Nu eftersom $y\in C_{in}^{\alpha _{1}},y=( y_{1},\alpha _{1}y_{1})$ för vissa $y_{1}\in \mathbb {F} _{q}^{k}$ och liknande $y=(y_{2},\alpha _{2}y_{2})$ för vissa $y_{2}\in \mathbb {F} _{q}^{k}.$ Eftersom ${\displaystyle y} dessutom$ inte är noll har vi $y_ {1},y_{2}\neq 0.$ Därför $(y_{1},\alpha _{1}y_{ 1})=(y_{2},\alpha _{2}y_{2})$ , sedan $y_{1}=y_{2}\neq 0$ och $\alpha _{1}y_{1}=\alpha _{2}y_{2}.$ Detta innebär $\alpha _{1}=\alpha _{2}$ , vilket är en motsägelse.

Vilken linjär kod som helst med avstånd $<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right )\cdot 2k$ har något kodord med vikt ${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.} Nu antyder$ Lemma att vi har åtminstone $|P|$ olika $y$ så att ${\displaystyle wt(y)<H_{q}^{- 1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k} ($ ett sådant kodord $y$ för varje linjär kod). Här $wt(y)$ vikten av kodord $y$ , vilket är antalet positioner som inte är noll för $y$ .

Beteckna

$S=\left\{y\ :\ wt(y)<H_{q}^{- 1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\right\}$

Sedan:

${\begin{aligned}|P|&\leqslant |S|\\&\leqslant {\text{Vol}}_{q}\left(H_ {q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k,2k\right)&&{\text{Vol}}_{q}(r, n){\text{ är volymen av Hamming ball med radie }}r{\text{ i }}[q]^{n}\\&\leqslant q^{H_{q}\left(H_{q} ^{-1}\left({\frac {1}{2}}-\varepsilon \right)\right)\cdot 2k}&&{\text{Vol}}_{q}(pn,n)\leqslant q^{H_{q}(p)n}\\&=q^{\left({\frac {1}{2}}-\varepsilon \right)\cdot 2k}\\&=q^{k (1-2\varepsilon )}\\&<\varepsilon (q^{k}-1)&&{\text{ för }}k{\text{ tillräckligt stor }}\\&=\varepsilon N\end{ Justerat}}$

Så $|P|<\varepsilon N$ , därför uppsättningen linjära koder som har det relativa avståndet $\geqslant H_{q}^{ -1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k$ har minst $N-\varepsilon N=( 1-\varepsilon )N$ element.

Se även

• Justesen kod
• Linjär kod
• Hamming bunden

•   Massey, James L. (1963), Threshold decoding , Tech. Rapport 410, Cambridge, Mass.: Massachusetts Institute of Technology, Research Laboratory of Electronics, hdl : 1721.1/4415 , MR 0154763 .
•   Justesen, Jørn (1972), "En klass av konstruktiva asymptotiskt bra algebraiska koder", Institute of Electrical and Electronics Engineers. Transaktioner på informationsteori , IT-18: 652–656, doi : 10.1109/TIT.1972.1054893 , MR 0384313 .

externa länkar

• Föreläsning 28: Justesen Code. Kodningsteoris kurs. Prof. Atri Rudra .
• Föreläsning 9: Gränser för volymen av en hamrande boll. Kodningsteoris kurs. Prof. Atri Rudra .
• J. Justesen (1972). "En klass av konstruktiva asymptotiskt bra algebraiska koder". IEEE Trans. Inf. Teori . 18 : 652–656. doi : 10.1109/TIT.1972.1054893 .
• Kodningsteorins anteckningar: Gilbert-Varshamov bunden. Venkatesan Guruswami