conjunto Wozencraft

En teoría de la codificación , el conjunto de Wozencraft es un conjunto de códigos lineales en el que la mayoría satisface la cota de Gilbert-Varshamov . Recibe su nombre de John Wozencraft , quien demostró su existencia. Massey (1963) describe este conjunto , atribuyéndolo a Wozencraft. Justesen (1972) utilizó el conjunto de Wozencraft como códigos internos en su construcción de un código asintóticamente bueno fuertemente explícito.

Teorema: Sea${\displaystyle \varepsilon >0.}$Para un tamaño suficientemente grande${\displaystyle k}$Existe un conjunto de códigos internos${\displaystyle C_{in}^{1},\cdots ,C_{in}^{N}}$tasa​${\displaystyle {\tfrac {1}{2}}}$, dónde${\displaystyle N=q^{k}-1}$, de tal manera que durante al menos${\displaystyle (1-\varepsilon )N}$valores de${\displaystyle i,C_{in}^{i}}$tiene distancia relativa${\displaystyle \geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)}$.

Aquí, la distancia relativa es la relación entre la distancia mínima y la longitud del bloque. Y${\displaystyle H_{q}}$La función de entropía q-aria se define de la siguiente manera:

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

De hecho, para demostrar la existencia de este conjunto de códigos lineales, especificaremos explícitamente este conjunto de la siguiente manera: para${\displaystyle \alpha \in \mathbb {F} _{q^{k}}-\{0\}}$, definir el código interno

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

Aquí podemos observar que${\displaystyle x\in \mathbb {F} _{q}^{k}}$y${\displaystyle \alpha \in \mathbb {F} _{q^{k}}}$Podemos hacer la multiplicación${\displaystyle \alpha x}$desde${\displaystyle \mathbb {F} _{q}^{k}}$es isomorfo a${\displaystyle \mathbb {F} _{q^{k}}}$.

Este conjunto se debe a Wozencraft y se llama conjunto Wozencraft.

A pesar de${\displaystyle x,y\in \mathbb {F} _{q}^{k}}$Tenemos los siguientes hechos:

1. ${\displaystyle C_{in}^{\alpha }(x)+C_{in}^{\alpha }(y)=(x,\alpha x)+(y,\alpha y)=(x+y,\alpha (x+y))=C_{in}^{\alpha }(x+y)}$
2. Para cualquier${\displaystyle a\in \mathbb {F} _{q},aC_{in}^{\alpha }(x)=a(x,\alpha x)=(ax,\alpha (ax))=C_{in}^{\alpha }(ax)}$

Entonces${\displaystyle C_{in}^{\alpha }}$es un código lineal para cada${\displaystyle \alpha \in \mathbb {F} _{q^{k}}-\{0\}}$.

Ahora sabemos que el conjunto de Wozencraft contiene códigos lineales con tasa${\displaystyle {\tfrac {1}{2}}}$En la siguiente demostración, mostraremos que hay al menos${\displaystyle (1-\varepsilon )N}$aquellos códigos lineales que tienen la distancia relativa${\displaystyle \geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)}$, es decir, se encuentran con el vínculo Gilbert-Varshamov.

Para demostrar que hay al menos${\displaystyle (1-\varepsilon )N}$número de códigos lineales en el conjunto de Wozencraft que tienen distancia relativa${\displaystyle \geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)}$, demostraremos que hay como máximo${\displaystyle \varepsilon N}$número de códigos lineales que tienen distancia relativa${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)}$es decir, tener distancia${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$

Nótese que en un código lineal, la distancia es igual al peso mínimo de todas las palabras clave de ese código. Este hecho es una propiedad del código lineal . Por lo tanto, si una palabra clave distinta de cero tiene peso${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k}$, entonces ese código tiene distancia${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$

Dejar${\displaystyle P}$sea ​​el conjunto de códigos lineales que tienen distancia${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$Luego están${\displaystyle |P|}$códigos lineales que tienen alguna palabra clave que tiene peso${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$

Lema. Dos códigos lineales${\displaystyle C_{in}^{\alpha _{1}}}$y${\displaystyle C_{in}^{\alpha _{2}}}$con${\displaystyle \alpha _{1},\alpha _{2}\in \mathbb {F} _{q^{k}}}$Son distintos y no nulos, y no comparten ninguna palabra clave distinta de cero.

Demostración. Supongamos que existen elementos distintos no nulos.${\displaystyle \alpha _{1},\alpha _{2}\in \mathbb {F} _{q^{k}}}$de tal manera que los códigos lineales${\displaystyle C_{in}^{\alpha _{1}}}$y${\displaystyle C_{in}^{\alpha _{2}}}$contienen la misma palabra clave distinta de cero${\displaystyle y.}$Ahora desde${\displaystyle y\in C_{in}^{\alpha _{1}},y=(y_{1},\alpha _{1}y_{1})}$para algunos${\displaystyle y_{1}\in \mathbb {F} _{q}^{k}}$y de manera similar${\displaystyle y=(y_{2},\alpha _{2}y_{2})}$para algunos${\displaystyle y_{2}\in \mathbb {F} _{q}^{k}.}$Además, dado que${\displaystyle y}$es distinto de cero tenemos${\displaystyle y_{1},y_{2}\neq 0.}$Por lo tanto${\displaystyle (y_{1},\alpha _{1}y_{1})=(y_{2},\alpha _{2}y_{2})}$, entonces${\displaystyle y_{1}=y_{2}\neq 0}$y${\displaystyle \alpha _{1}y_{1}=\alpha _{2}y_{2}.}$Esto implica${\displaystyle \alpha _{1}=\alpha _{2}}$, lo cual es una contradicción.

Cualquier código lineal que tenga distancia${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k}$tiene alguna palabra clave de peso${\displaystyle <H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}$Ahora el lema implica que tenemos al menos${\displaystyle |P|}$diferente${\displaystyle y}$de tal manera que${\displaystyle wt(y)<H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k}$(una de esas palabras clave)${\displaystyle y}$para cada código lineal). Aquí${\displaystyle wt(y)}$indica el peso de la palabra clave${\displaystyle y}$, que es el número de posiciones distintas de cero de${\displaystyle y}$.

Denotar

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

Entonces: ^{[ 1 ]}

${\displaystyle {\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{ is the volume of Hamming ball of radius }}r{\text{ in }}[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{ for }}k{\text{ large enough }}\\&=\varepsilon N\end{aligned}}}$

Entonces${\displaystyle |P|<\varepsilon N}$, por lo tanto, el conjunto de códigos lineales que tienen la distancia relativa${\displaystyle \geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k}$tiene al menos${\displaystyle N-\varepsilon N=(1-\varepsilon )N}$elementos.

• Bola de jamón
• Hamming se dirigió
• Código Justesen
• Código lineal

• Massey, James L. (1963), Decodificación de umbral , Informe técnico 410, Cambridge, Mass.: Instituto Tecnológico de Massachusetts, Laboratorio de Investigación de Electrónica, hdl : 1721.1/4415 , MR 0154763 .
• Justesen, Jørn (1972), "Una clase de códigos algebraicos constructivos asintóticamente buenos", IEEE Transactions on Information Theory , IT-18 (5): 652–656 , doi : 10.1109/TIT.1972.1054893 , MR 0384313 .

• Lección 25: Código de Justesen. Curso de teoría de la codificación. Prof. Atri Rudra .
• Lección 9: Límites del volumen de una bola de Hamming. Curso de teoría de la codificación. Prof. Atri Rudra .
• J. Justesen (1972). "Una clase de códigos algebraicos constructivos asintóticamente buenos". IEEE Transactions on Information Theory . 18 (5): 652– 656. doi : 10.1109/TIT.1972.1054893 .
• Notas sobre la teoría de la codificación: El límite de Gilbert-Varshamov. Venkatesan Guruswami