Gilbert-Varshamov destinado a códigos lineales

El límite de Gilbert-Varshamov para códigos lineales está relacionado con el límite general de Gilbert-Varshamov , que proporciona un límite inferior en el número máximo de elementos en un código de corrección de errores de una longitud de bloque determinada y un peso mínimo de Hamming sobre un campo . Esto puede traducirse en una declaración sobre la velocidad máxima de un código con una longitud y una distancia mínima determinadas. El límite de Gilbert-Varshamov para códigos lineales afirma la existencia de códigos lineales q -arios para cualquier distancia mínima relativa menor que el límite dado que simultáneamente tienen una tasa alta. La prueba de existencia utiliza el método probabilístico y, por tanto, no es constructiva. El límite de Gilbert-Varshamov es el más conocido en términos de distancia relativa para códigos sobre alfabetos de tamaño inferior a 49. ^{[ cita necesaria ]} Para alfabetos más grandes, los códigos de geometría algebraica a veces logran una relación asintóticamente mejor entre tasa y distancia que la dada por el Gilbert-Varshamov se dirige. ^[1] ${\displaystyle \mathbb {F} _{q}}$

Teorema ligado de Gilbert-Varshamov

Teorema: Sea . Para cada y existe un código con tasa y distancia relativa. ${\displaystyle q\geqslant 2}$ ${\displaystyle 0\leqslant \delta <1-{\tfrac {1}{q}}}$ ${\displaystyle 0<\varepsilon \leqslant 1-H_{q}(\delta ),}$ ${\displaystyle R\geqslant 1-H_{q}(\delta )-\varepsilon }$ ${\displaystyle \delta .}$

Aquí está la función de entropía q -aria definida de la siguiente manera: ${\displaystyle H_{q}}$

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

El resultado anterior fue probado por Edgar Gilbert para código general utilizando el método codicioso como aquí . Para el código lineal , Rom Varshamov demostró utilizar el método probabilístico para el código lineal aleatorio. Esta prueba se mostrará en la siguiente parte.

Prueba de alto nivel:

Para mostrar la existencia del código lineal que satisface esas restricciones, se utiliza el método probabilístico para construir el código lineal aleatorio. Específicamente, el código lineal se elige aleatoriamente eligiendo la matriz generadora aleatoria en la que el elemento se elige uniformemente en todo el campo . Además, la distancia de Hamming del código lineal es igual al peso mínimo de la palabra en clave . Entonces, para demostrar que el código lineal generado por tiene distancia de Hamming , lo mostraremos para cualquiera . Para probar eso, demostramos lo contrario; es decir, la probabilidad de que el código lineal generado por tenga la distancia de Hamming menor que es exponencialmente pequeña en . Entonces, por el método probabilístico, existe el código lineal que satisface el teorema. ${\displaystyle G}$ ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle m\in \mathbb {F} _{q}^{k}\smallsetminus \left\{0\right\},\operatorname {wt} (mG)\geq d}$ ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle n}$

Prueba formal:

Al utilizar el método probabilístico, para demostrar que existe un código lineal que tiene una distancia de Hamming mayor que , mostraremos que la probabilidad de que el código lineal aleatorio que tenga una distancia menor que sea exponencialmente pequeña en . ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle n}$

Sabemos que el código lineal se define mediante la matriz generadora . Por eso utilizamos la "matriz generadora aleatoria" como medio para describir la aleatoriedad del código lineal. Entonces, una matriz generadora aleatoria de tamaño contiene elementos que se eligen de manera independiente y uniforme en el campo . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle kn}$ ${\displaystyle kn}$ ${\displaystyle \mathbb {F} _{q}}$

Recuerde que en un código lineal , la distancia es igual al peso mínimo de la palabra de código distinta de cero. Sea el peso de la palabra clave . Entonces ${\displaystyle \operatorname {wt} (y)}$ ${\displaystyle y}$

${\displaystyle {\begin{aligned}P&=\Pr _{{\text{random }}G}({\text{linear code generated by }}G{\text{ has distance}}<d)\\[6pt]&=\Pr _{{\text{random }}G}({\text{there exists a non-zero codeword }}y{\text{ in a linear code generated by }}G{\text{ such that }}\operatorname {wt} (y)<d)\\[6pt]&=\Pr _{{\text{random }}G}\left({\text{there exists }}0\neq m\in \mathbb {F} _{q}^{k}{\text{ such that }}\operatorname {wt} (mG)<d\right)\end{aligned}}}$

La última igualdad se desprende de la definición: si una palabra clave pertenece a un código lineal generado por , entonces para algún vector . ${\displaystyle y}$ ${\displaystyle G}$ ${\displaystyle y=mG}$ ${\displaystyle m\in \mathbb {F} _{q}^{k}}$

Por la desigualdad de Boole , tenemos:

${\displaystyle P\leqslant \sum _{0\neq m\in \mathbb {F} _{q}^{k}}\Pr _{{\text{random }}G}(\operatorname {wt} (mG)<d)}$

Ahora, para un mensaje determinado queremos calcular ${\displaystyle 0\neq m\in \mathbb {F} _{q}^{k},}$

${\displaystyle W=\Pr _{{\text{random }}G}(\operatorname {wt} (mG)<d).}$

Sea una distancia de Hamming de dos mensajes y . Luego para cualquier mensaje , tenemos: . Por lo tanto: ${\displaystyle \Delta (m_{1},m_{2})}$ ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$ ${\displaystyle m}$ ${\displaystyle \operatorname {wt} (m)=\Delta (0,m)}$

${\displaystyle W=\sum _{\{y\in \mathbb {F} _{q}^{n}|\Delta (0,y)\leqslant d-1\}}\Pr _{{\text{random }}G}(mG=y)}$

Debido a la aleatoriedad de , es un vector uniformemente aleatorio de . Entonces ${\displaystyle G}$ ${\displaystyle mG}$ ${\displaystyle \mathbb {F} _{q}^{n}}$

${\displaystyle \Pr _{{\text{random }}G}(mG=y)=q^{-n}}$

Sea un volumen de bola de Hamming con radio . Entonces: ^[2] ${\displaystyle \operatorname {Vol} _{q}(r,n)}$ ${\displaystyle r}$

${\displaystyle P\leqslant q^{k}W=q^{k}\left({\frac {\operatorname {Vol} _{q}(d-1,n)}{q^{n}}}\right)\leqslant q^{k}\left({\frac {q^{nH_{q}(\delta )}}{q^{n}}}\right)=q^{k}q^{-n(1-H_{q}(\delta ))}}$

Al elegir , la desigualdad anterior se convierte en ${\displaystyle k=(1-H_{q}(\delta )-\varepsilon )n}$

${\displaystyle P\leqslant q^{-\varepsilon n}}$

Finalmente , que es exponencialmente pequeño en n, eso es lo que queremos antes. Luego, por el método probabilístico, existe un código lineal con distancia relativa y velocidad al menos , lo que completa la prueba. ${\displaystyle q^{-\varepsilon n}\ll 1}$ ${\displaystyle C}$ ${\displaystyle \delta }$ ${\displaystyle R}$ ${\displaystyle (1-H_{q}(\delta )-\varepsilon )}$

Comentarios

1. La construcción de Varshamov anterior no es explícita; es decir, no especifica el método determinista para construir el código lineal que satisface el límite de Gilbert-Varshamov. Un enfoque ingenuo es buscar en todas las matrices generadoras de tamaño en el campo para verificar si el código lineal asociado alcanza la distancia de Hamming predicha. Esta búsqueda exhaustiva requiere un tiempo de ejecución exponencial en el peor de los casos. ${\displaystyle G}$ ${\displaystyle kn}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle G}$
2. También existe una construcción de Las Vegas que toma un código lineal aleatorio y verifica si este código tiene una buena distancia de Hamming, pero esta construcción también tiene un tiempo de ejecución exponencial.
3. Para q no primo suficientemente grande y para ciertos rangos de la variable δ, el límite de Gilbert-Varshamov es superado por el límite de Tsfasman-Vladut-Zink. ^[3]

Ver también

• Gilbert-Varshamov obligado debido a la construcción de Gilbert para el código general
• Hamming atado
• método probabilístico

Referencias

1. Tsfasman, MA; Vladut, SG; Zink, T. (1982). "Las curvas modulares, las curvas de Shimura y los códigos Goppa son mejores que el límite de Varshamov-Gilbert". Mathematische Nachrichten . 104 .
2. La desigualdad posterior proviene del límite superior del volumen de la bola de Hamming Archivado el 8 de noviembre de 2013 en la Wayback Machine.
3. Stichtenoth, H. (2006). "Códigos transitivos y autoduales que alcanzan el límite Tsfasman-Vla/spl breve/dut$80-Zink". Transacciones IEEE sobre teoría de la información . 52 (5): 2218–2224. doi :10.1109/TIT.2006.872986. ISSN  0018-9448. S2CID  11982763.

• Conferencia 11: Gilbert-Varshamov atado. Curso de Teoría de la Codificación. Profesor Atri Rudra
• Conferencia 9: Límites del volumen de la bola de Hamming. Curso de Teoría de la Codificación. Profesor Atri Rudra
• Notas de teoría de codificación: Gilbert – Varshamov Bound. Venkatesan Guruswami