Código largo (matemáticas)

En informática teórica y teoría de la codificación , el código largo es un código de corrección de errores que se puede decodificar localmente . Los códigos largos tienen una tasa extremadamente baja, pero desempeñan un papel fundamental en la teoría de la dificultad de la aproximación .

Dejar${\displaystyle f_{1},\dots ,f_{2^{n}}:\{0,1\}^{k}\to \{0,1\}}$para${\displaystyle k=\log n}$sea ​​la lista de todas las funciones de${\displaystyle \{0,1\}^{k}\to \{0,1\}}$. Luego, la codificación de código largo de un mensaje${\displaystyle x\in \{0,1\}^{k}}$es la cadena${\displaystyle f_{1}(x)\circ f_{2}(x)\circ \dots \circ f_{2^{n}}(x)}$dónde${\displaystyle \circ }$denota la concatenación de cadenas. Esta cadena tiene longitud${\displaystyle 2^{n}=2^{2^{k}}}$.

El código Walsh-Hadamard es un subcódigo del código largo y se puede obtener utilizando únicamente funciones.${\displaystyle f_{i}}$que son funciones lineales cuando se interpretan como funciones${\displaystyle \mathbb {F} _{2}^{k}\to \mathbb {F} _{2}}$en el cuerpo finito con dos elementos. Dado que solo hay${\displaystyle 2^{k}}$tales funciones, la longitud del bloque del código Walsh-Hadamard es${\displaystyle 2^{k}}$.

Una definición equivalente del código largo es la siguiente: La codificación de código largo de${\displaystyle j\in [n]}$se define como la tabla de verdad de la función de dictadura booleana en el${\displaystyle j}$la coordenada , es decir, la tabla de verdad de${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$con${\displaystyle f(x_{1},\dots ,x_{n})=x_{j}}$. ^{[ 1 ]} Por lo tanto, el código largo codifica un${\displaystyle (\log n)}$-cadena de bits como una${\displaystyle 2^{n}}$-cadena de bits.

El código largo no contiene repeticiones, en el sentido de que la función${\displaystyle f_{i}}$computando el${\displaystyle i}$El bit th de la salida es diferente de cualquier función.${\displaystyle f_{j}}$computando el${\displaystyle j}$el bit th de la salida para${\displaystyle j\neq i}$Entre todos los códigos que no contienen repeticiones, el código largo tiene la salida más larga posible. Además, incluye todos los códigos no repetitivos como subcódigos.