Código de peso constante

En teoría de la codificación , un código de peso constante , también llamado código m de n o código m de n , es un código de detección y corrección de errores en el que todas las palabras clave comparten el mismo peso de Hamming . El código one-hot y el código balanceado son dos tipos de códigos de peso constante ampliamente utilizados.

Esta teoría está estrechamente relacionada con la de los diseños (como los diseños t y los sistemas de Steiner ). La mayor parte del trabajo en este campo de las matemáticas discretas se centra en los códigos binarios de peso constante.

Los códigos binarios de peso constante tienen varias aplicaciones, incluido el salto de frecuencia en redes GSM . ^{[ 1 ]} La mayoría de los códigos de barras utilizan un código binario de peso constante para simplificar el ajuste automático del umbral de brillo que distingue las franjas blancas y negras. La mayoría de los códigos de línea utilizan un código de peso constante o un código de disparidad emparejado de peso casi constante . Además de su uso como códigos de corrección de errores, el gran espacio entre las palabras del código también se puede utilizar en el diseño de circuitos asíncronos , como los circuitos insensibles al retardo .

Los códigos de peso constante, como los códigos de Berger , pueden detectar todos los errores unidireccionales.

El problema central con respecto a los códigos de peso constante es el siguiente: ¿cuál es el número máximo de palabras clave en un código binario de peso constante con longitud${\displaystyle n}$, distancia de Hamming${\displaystyle d}$y peso${\displaystyle w}$¿Este número se llama?${\displaystyle A(n,d,w)}$.

Aparte de algunas observaciones triviales, generalmente es imposible calcular estos números de forma directa. Los límites superiores vienen dados por varios teoremas importantes, como los primeros y segundos límites de Johnson , ^{[ 2 ]} y a veces se pueden encontrar mejores límites superiores de otras maneras. Los límites inferiores se encuentran con mayor frecuencia exhibiendo códigos específicos, ya sea con el uso de una variedad de métodos de matemáticas discretas o a través de una búsqueda computacional intensiva. Una gran tabla de tales códigos que batieron récords se publicó en 1990, ^{[ 3 ]} y una extensión a códigos más largos (pero solo para aquellos valores de${\displaystyle d}$y${\displaystyle w}$que son relevantes para la aplicación GSM) se publicó en 2006. ^{[ 1 ]}

Un caso especial de códigos de peso constante son los códigos uno de N , que codifican${\displaystyle \log _{2}N}$bits en una palabra clave de${\displaystyle N}$bits. El código uno de dos utiliza las palabras clave 01 y 10 para codificar los bits '0' y '1'. Un código uno de cuatro puede utilizar las palabras 0001, 0010, 0100, 1000 para codificar dos bits 00, 01, 10 y 11. Un ejemplo es la codificación de doble riel y el enlace de cadena ^{[ 4 ]} utilizado en circuitos insensibles al retardo. Para estos códigos,${\displaystyle n=N,~d=2,~w=1}$y${\displaystyle A(n,d,w)=n}$.

Algunos de los usos más notables de los códigos one-hot incluyen el código de marca bifásico que utiliza un código 1 de 2; la modulación por posición de pulso que utiliza un código 1 de n ; el decodificador de direcciones , etc.

En teoría de la codificación , un código balanceado es un código binario de corrección de errores hacia adelante en el que cada palabra clave contiene un número igual de bits cero y uno. Los códigos balanceados fueron introducidos por Donald Knuth ; ^{[ 5 ]} son ​​un subconjunto de los llamados códigos no ordenados, que son códigos que tienen la propiedad de que las posiciones de los unos en una palabra clave nunca son un subconjunto de las posiciones de los unos en otra palabra clave. Al igual que todos los códigos no ordenados, los códigos balanceados son adecuados para la detección de todos los errores unidireccionales en un mensaje codificado. Los códigos balanceados permiten una decodificación particularmente eficiente, que puede realizarse en paralelo. ^{[ 5 ] [ 6 ] [ 7 ]}

Algunos de los usos más notables de los códigos de peso equilibrado incluyen el código de marca bifásico que utiliza un código 1 de 2; la codificación 6b/8b utiliza un código 4 de 8; el código Hadamard es un${\displaystyle 2^{k-1}}$de${\displaystyle 2^{k}}$código (excepto la palabra clave cero), el código tres de seis ; etc.

La codificación de carril de 3 hilos utilizada en MIPI C-PHY puede considerarse una generalización del código de peso constante a ternario: cada hilo transmite una señal ternaria y, en cualquier instante, uno de los 3 hilos está transmitiendo una señal baja, otro una señal media y otro una señal alta. ^{[ 8 ]}

Un código m de n es un código de detección de errores separable con una longitud de palabra de código de n bits, donde cada palabra de código contiene exactamente m instancias de un "uno". Un error de un solo bit hará que la palabra de código tenga m + 1 o m − 1 "unos". Un ejemplo de código m de n es el código 2 de 5 utilizado por el Servicio Postal de los Estados Unidos .

La implementación más sencilla consiste en añadir una cadena de unos a los datos originales hasta que contenga m unos, y luego añadir ceros para crear un código de longitud n .

Ejemplo:

Algunos de los usos más notables de los códigos de peso constante, aparte de los códigos one-hot y de peso equilibrado ya mencionados anteriormente, incluyen el Código 39 que utiliza un código 3 de 9; el código decimal codificado biquinario que utiliza un código 2 de 7, el código 2 de 5 , etc.

• Tabla de límites inferiores en${\displaystyle A(n,d,w)}$Mantenido por Andries Brouwer
• Tabla de límites superiores en${\displaystyle A(n,d,w)}$Mantenido por Erik Agrell