En teoría de la codificación , un código constante de peso , también llamado m -OF- n código , es una detección de errores y corrección de código donde todas las palabras de código comparten el mismo peso Hamming . El código one-hot y el código balanceado son dos tipos de código de peso constante ampliamente utilizados.
La teoría está estrechamente relacionada con la de diseños (tales como t -designs y sistemas de Steiner ). La mayor parte del trabajo en este campo tan vital de las matemáticas discretas se ocupa de 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 la configuración automática del umbral. 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 usarse como códigos de corrección de errores, el gran espacio entre las palabras de código también se puede usar en el diseño de circuitos asíncronos, tales como circuitos insensibles al retardo .
Los códigos de peso constante, como los códigos de Berger , pueden detectar todos los errores unidireccionales.
A ( n , d , w )
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 el peso ? Este número se llama.
Aparte de algunas observaciones triviales, generalmente es imposible calcular estos números de una manera sencilla. Los límites superiores vienen dados por varios teoremas importantes, como el primero y el segundo límites de Johnson , [2] ya veces se pueden encontrar mejores límites superiores de otras formas. Los límites inferiores se encuentran con mayor frecuencia al exhibir códigos específicos, ya sea con el uso de una variedad de métodos de matemáticas discretas o mediante una búsqueda intensiva en computadora. En 1990 se publicó una gran tabla de códigos récord de este tipo, [3] y una extensión a códigos más largos (pero solo para los valores de y relevantes para la aplicación GSM) se publicó en 2006. [1]
Códigos 1 de N
Un caso especial de códigos de peso constante son los códigos uno de N , que codifican bits en una palabra de código de bits. El código uno de dos usa las palabras de código 01 y 10 para codificar los bits '0' y '1'. Un código de 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 carril y el enlace de cadena [4] utilizado en retardo insensible circuitos. Para estos códigos, y .
Algunos de los usos más notables de los códigos one-hot incluyen el código de marca bifase que usa 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.
Código equilibrado
En la teoría de la codificación , un código balanceado 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. Donald Knuth ha introducido los códigos equilibrados ; [5] son un subconjunto de los llamados códigos desordenados, que son códigos que tienen la propiedad de que las posiciones de unos en una palabra de código nunca son un subconjunto de las posiciones de los unos en otra palabra de código. Como todos los códigos no ordenados, 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 se puede realizar 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 bifase que usa un código 1 de 2; La codificación 6b / 8b utiliza un código 4 de 8; el código Hadamard es un de código (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 puede considerarse 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 está transmitiendo un bajo, uno es transmitiendo un medio, y uno está transmitiendo una señal alta. [8]
m -of- n códigos
Un código m -of- 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:
3 bits de datos originales | Bits añadidos |
---|---|
000 | 111 |
001 | 110 |
010 | 110 |
011 | 100 |
100 | 110 |
101 | 100 |
110 | 100 |
111 | 000 |
Algunos de los usos más notables de los códigos de peso constante, además de los códigos de peso equilibrado y uno en caliente ya mencionados anteriormente, incluyen que el Código 39 usa un código 3 de 9; El código decimal codificado bi-quinario utiliza un código 2 de 7, el código 2 de 5 , etc.
Referencias
- ↑ a b D. H. Smith, LA Hughes y S. Perkins (2006). " Una nueva tabla de códigos de peso constante de longitud superior a 28 ". La Revista Electrónica de Combinatoria 13 .
- ^ Véanse las págs. 526-527 de FJ MacWilliams y NJA Sloane (1979). La teoría de los códigos de corrección de errores . Amsterdam: Holanda Septentrional.
- ^ AE Brouwer, James B. Shearer, NJA Sloane y Warren D. Smith (1990). "Una nueva tabla de códigos de peso constante". Teoría de las transacciones de información del IEEE 36 .
- ^ WJ Bainbridge; A. Bardsley; RW McGuffin. "Diseño de sistema en chip utilizando redes autotemporizadas en chip" .
- ^ a b DE Knuth (enero de 1986). "Códigos equilibrados eficientes" (PDF) . Transacciones IEEE sobre teoría de la información . 32 (1): 51–53. doi : 10.1109 / TIT.1986.1057136 .[ enlace muerto permanente ]
- ^ Sulaiman Al-Bassam; Bella Bose (marzo de 1990). "Sobre códigos equilibrados". Transacciones IEEE sobre teoría de la información . 36 (2): 406–408. doi : 10.1109 / 18.52490 .
- ^ K. Schouhamer Immink y J. Weber (2010). "Códigos equilibrados muy eficientes" . Revista IEEE sobre áreas seleccionadas en comunicaciones . 28 : 188-192. doi : 10.1109 / jsac.2010.100207 . Consultado el 12 de febrero de 2018 .
- ^ "Desmitificación del subsistema MIPI C-PHY / DPHY: compensaciones, desafíos y adopción" ( espejo )
enlaces externos
- Tabla de límites inferiores en A ( norte , D , w ) {\ Displaystyle A (norte, d, a)} mantenido por Andries Brouwer (actualización de la tabla anterior por Neil Sloane y EM Rains )
- Tabla de límites superiores en A ( norte , D , w ) {\ Displaystyle A (norte, d, a)} mantenido por Erik Agrell