En teoría de codificación , un código de peso constante , también llamado código m -de- n , es un código de detección y corrección de errores donde todas las palabras en código comparten el mismo peso Hamming . El código one-hot y el código equilibrado son dos tipos de código de peso constante ampliamente utilizados.
La teoría está estrechamente relacionada con la de los diseños (como los diseños t y los sistemas Steiner ). La mayor parte del trabajo en este campo de las matemáticas discretas se ocupa de 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 la configuración automática del umbral de brillo que distingue las rayas 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 emparejada de peso casi constante . Además de usarse como códigos de corrección de errores, el gran espacio entre palabras de código también se puede usar en el diseño de circuitos asíncronos, como circuitos insensibles al retardo .
Los códigos de peso constante, como los códigos 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 de código en un código binario de peso constante con longitud , distancia de Hamming y peso ? Este número se llama .
Aparte de algunas observaciones triviales, generalmente es imposible calcular estos números de forma sencilla. Los límites superiores vienen dados por varios teoremas importantes, como el primer y segundo 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 mediante el uso de una variedad de métodos de matemáticas discretas o mediante búsquedas informáticas intensas. En 1990 se publicó una gran tabla de códigos récord, [3] y en 2006 se publicó una extensión a códigos más largos (pero sólo para aquellos valores y que son relevantes para la aplicación GSM) .
Un caso especial de códigos de peso constante son los códigos uno de N , que codifican bits en una palabra clave de bits. El código uno de dos utiliza las palabras de código 01 y 10 para codificar los bits '0' y '1'. Un código uno de cuatro puede usar las palabras 0001, 0010, 0100, 1000 para codificar dos bits 00, 01, 10 y 11. Un ejemplo es la codificación de doble carril y el eslabón de cadena [4] utilizado en insensibles al retardo. circuitos. Para estos códigos, y .
Algunos de los usos más notables de los códigos one-hot incluyen que el código de marca bifásico utiliza un código 1 de 2; la modulación de posición de pulso utiliza un código 1 de n ; decodificador de direcciones , etc.
En teoría de la codificación , un código equilibrado es un código binario de corrección de errores hacia adelante para el cual cada palabra de código contiene un número igual de bits cero y uno. Los códigos equilibrados han sido introducidos por Donald Knuth ; [5] son un subconjunto de los llamados códigos desordenados, 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. Como todos los códigos desordenados, los códigos equilibrados son adecuados para la detección de todos los errores unidireccionales en un mensaje codificado. Los códigos equilibrados permiten una decodificación especialmente eficaz, 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 código de (excepto la palabra de código cero), el código tres de seis ; etc.
La codificación de carril de 3 cables utilizada en MIPI C-PHY se puede considerar una generalización del código de peso constante a ternario: cada cable transmite una señal ternaria y, en cualquier instante, uno de los 3 cables transmite un nivel bajo, el otro es transmitiendo una señal media y otra está transmitiendo 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 -of- n es el código 2 de 5 utilizado por el Servicio Postal de los Estados Unidos .
La implementación más simple es agregar una cadena de unos a los datos originales hasta que contenga m unos, luego agregar ceros para crear un código de longitud n .
Ejemplo:
Algunos de los usos más notables de los códigos de peso constante, además de los códigos one-hot y de peso equilibrado ya mencionados anteriormente, incluyen que el Código 39 utiliza un código 3 de 9; El código decimal codificado biquinario utiliza un código 2 de 7, el código 2 de 5 , etc.
