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 pobre, pero juegan un papel fundamental en la teoría de la dureza de aproximación .
Lógica matemática | |
---|---|
Clasificación | |
Tipo | Código de bloque |
Longitud del bloque | para algunos |
Longitud del mensaje | |
Tamaño del alfabeto | |
Notación | -código |
Definición
Dejar por ser la lista de todas las funciones de. Luego, la codificación de código largo de un mensaje es la cuerda dónde denota concatenación de cadenas. Esta cuerda tiene longitud.
El código de Walsh-Hadamard es un subcódigo del código largo y se puede obtener solo usando funcionesque son funciones lineales cuando se interpretan como funcionesen el campo finito con dos elementos. Dado que solo hay tales funciones, la longitud de bloque del código Walsh-Hadamard es .
Una definición equivalente del código largo es la siguiente: La codificación de código largo de se define como la tabla de verdad de la función de dictadura booleana en el th coordenada, es decir, la tabla de verdad de con . [1] Por lo tanto, el código Long codifica un-bit cadena como un -cadena de bits.
Propiedades
El código largo no contiene repeticiones, en el sentido de que la función computando el El bit de la salida es diferente de cualquier función. computando el el bit de la salida para . Entre todos los códigos que no contienen repeticiones, el código largo tiene la salida más larga posible. Además, contiene todos los códigos no repetidos como subcódigo.