El código Hadamard es un código de corrección de errores que lleva el nombre de Jacques Hadamard y se utiliza para la detección y corrección de errores cuando se transmiten mensajes a través de canales muy ruidosos o poco fiables. En 1971, el código se utilizó para transmitir fotos de Marte a la Tierra desde la sonda espacial Mariner 9 de la NASA . [1] Debido a sus propiedades matemáticas únicas, el código Hadamard no solo es utilizado por ingenieros, sino que también se estudia intensamente en teoría de codificación , matemáticas e informática teórica . El código Hadamard también se conoce bajo el nombre de código Walsh , de la familia de Walsh ,[2] y el código Walsh-Hadamard [3] en reconocimiento al matemático estadounidense Joseph Leonard Walsh .
Código Hadamard | |
---|---|
Lleva el nombre de | Jacques Hadamard |
Clasificación | |
Tipo | Código de bloque lineal |
Longitud del bloque | |
Longitud del mensaje | |
Velocidad | |
Distancia | |
Tamaño del alfabeto | |
Notación | -código |
Código Hadamard aumentado | |
---|---|
Lleva el nombre de | Jacques Hadamard |
Clasificación | |
Tipo | Código de bloque lineal |
Longitud del bloque | |
Longitud del mensaje | |
Velocidad | |
Distancia | |
Tamaño del alfabeto | |
Notación | -código |
El código Hadamard es un ejemplo de un código lineal de longitudsobre un alfabeto binario . Desafortunadamente, este término es algo ambiguo ya que algunas referencias asumen una longitud de mensaje mientras que otros asumen una longitud de mensaje de . En este artículo, el primer caso se llama código Hadamard mientras que el segundo se llama código Hadamard aumentado .
El código Hadamard es único en el sentido de que cada palabra de código distinta de cero tiene un peso Hamming de exactamente, lo que implica que la distancia del código también es. En la notación de teoría de codificación estándar para códigos de bloque , el código Hadamard es un-code, es decir, es un código lineal sobre un alfabeto binario , tiene una longitud de bloque , longitud del mensaje (o dimensión)y distancia mínima . La longitud del bloque es muy grande en comparación con la longitud del mensaje, pero por otro lado, los errores se pueden corregir incluso en condiciones extremadamente ruidosas.
El código de Hadamard aumentado es una versión ligeramente mejorada del código de Hadamard; es un-code y, por lo tanto, tiene una tasa ligeramente mejor manteniendo la distancia relativa de, y por tanto se prefiere en aplicaciones prácticas. En la teoría de la comunicación, esto simplemente se llama código Hadamard y es el mismo que el código Reed-Muller de primer orden sobre el alfabeto binario. [4]
Normalmente, los códigos Hadamard se basan en la construcción de matrices Hadamard de Sylvester , pero el término "código Hadamard" también se usa para referirse a códigos construidos a partir de matrices Hadamard arbitrarias , que no son necesariamente del tipo Sylvester. En general, dicho código no es lineal. Estos códigos fueron construidos por primera vez por Raj Chandra Bose y Sharadchandra Shankar Shrikhande en 1959. [5] Si n es el tamaño de la matriz de Hadamard, el código tiene parámetros, lo que significa que es un código binario no necesariamente lineal con 2 n palabras de código de longitud de bloque n y distancia mínima n / 2. El esquema de construcción y decodificación descrito a continuación se aplica para n general , pero la propiedad de linealidad y la identificación con códigos Reed-Muller requieren que n sea una potencia de 2 y que la matriz de Hadamard sea equivalente a la matriz construida por el método de Sylvester.
El código Hadamard es un código decodificable localmente , que proporciona una forma de recuperar partes del mensaje original con alta probabilidad, mientras que solo se observa una pequeña fracción de la palabra recibida. Esto da lugar a aplicaciones en la teoría de la complejidad computacional y particularmente en el diseño de demostraciones probabilísticamente verificables . Dado que la distancia relativa del código Hadamard es 1/2, normalmente solo se puede esperar recuperarse como máximo de una fracción de error de 1/4. Sin embargo, utilizando la decodificación de listas , es posible calcular una lista corta de posibles mensajes candidatos siempre que menos de de los bits de la palabra recibida se han corrompido.
En la comunicación de acceso múltiple por división de código (CDMA), el código Hadamard se denomina Código Walsh y se utiliza para definir canales de comunicación individuales . Es habitual en la literatura CDMA referirse a las palabras de código como "códigos". Cada usuario utilizará una palabra de código diferente, o "código", para modular su señal. Debido a que las palabras de código de Walsh son matemáticamente ortogonales , una señal codificada en Walsh aparece como ruido aleatorio en un terminal móvil con capacidad CDMA , a menos que ese terminal use la misma palabra de código que la utilizada para codificar la señal entrante . [6]
Historia
El código Hadamard es el nombre que se usa más comúnmente para este código en la literatura. Sin embargo, en el uso moderno, estos códigos de corrección de errores se denominan códigos Walsh-Hadamard.
Hay una razón para esto:
Jacques Hadamard no inventó el código él mismo, pero definió las matrices de Hadamard alrededor de 1893, mucho antes de que se desarrollara el primer código de corrección de errores , el código Hamming , en la década de 1940.
El código Hadamard se basa en matrices Hadamard, y aunque hay muchas matrices Hadamard diferentes que podrían usarse aquí, normalmente solo se usa la construcción de Sylvester de las matrices Hadamard para obtener las palabras en clave del código Hadamard.
James Joseph Sylvester desarrolló su construcción de matrices de Hadamard en 1867, que en realidad es anterior al trabajo de Hadamard sobre las matrices de Hadamard. Por lo tanto, se disputa el nombre código Hadamard y, a veces, el código se llama código Walsh , en honor al matemático estadounidense Joseph Leonard Walsh .
Se utilizó un código Hadamard aumentado durante la misión Mariner 9 de 1971 para corregir errores de transmisión de imágenes. Las palabras de datos utilizadas durante esta misión tenían una longitud de 6 bits, lo que representa 64 valores en escala de grises .
Debido a las limitaciones de la calidad de la alineación del transmisor en ese momento (debido a problemas de bucle de seguimiento Doppler), la longitud máxima de datos útiles era de unos 30 bits. En lugar de utilizar un código de repetición , se utilizó un código Hadamard [32, 6, 16].
Los errores de hasta 7 bits por palabra podrían corregirse utilizando este esquema. En comparación con un código de 5 repeticiones , las propiedades de corrección de errores de este código Hadamard son mucho mejores, pero su tasa es comparable. El algoritmo de decodificación eficiente fue un factor importante en la decisión de utilizar este código.
El circuito utilizado se denominó "Máquina verde". Empleó la transformada rápida de Fourier que puede aumentar la velocidad de decodificación en un factor de tres. Desde la década de 1990, el uso de este código por parte de los programas espaciales ha cesado más o menos, y la Red de Espacio Profundo de la NASA no admite este esquema de corrección de errores para sus antenas de más de 26 m.
Construcciones
Si bien todos los códigos de Hadamard se basan en matrices de Hadamard, las construcciones difieren en formas sutiles para diferentes campos científicos, autores y usos. Los ingenieros, que utilizan los códigos para la transmisión de datos, y los teóricos de la codificación , que analizan las propiedades extremas de los códigos, normalmente quieren que la velocidad del código sea lo más alta posible, incluso si esto significa que la construcción se vuelve matemáticamente un poco menos elegante.
Por otro lado, para muchas aplicaciones de los códigos de Hadamard en la informática teórica no es tan importante lograr la tasa óptima y, por lo tanto, se prefieren las construcciones más simples de los códigos de Hadamard, ya que se pueden analizar de manera más elegante.
Construcción con productos internos
Cuando se le da un mensaje binario de longitud , el código Hadamard codifica el mensaje en una palabra clave usando una función de codificación Esta función hace uso del producto interno de dos vectores , que se define de la siguiente manera:
Entonces la codificación Hadamard de se define como la secuencia de todos los productos internos con:
Como se mencionó anteriormente, el código aumentado de Hadamard se usa en la práctica, ya que el código de Hadamard en sí mismo es algo inútil. Esto se debe a que, si el primer bit de es cero, , entonces el producto interno no contiene información alguna sobre , y por lo tanto, es imposible decodificar completamente desde esas posiciones de la palabra clave solamente. Por otro lado, cuando la palabra clave se restringe a las posiciones donde, todavía es posible decodificar completamente . Por lo tanto, tiene sentido restringir el código Hadamard a estas posiciones, lo que da lugar a la codificación Hadamard aumentada de; es decir,.
Construcción usando una matriz generadora
El código Hadamard es un código lineal y todos los códigos lineales pueden ser generados por una matriz generadora. . Esta es una matriz tal que se mantiene para todos , donde el mensaje se ve como un vector fila y el producto vector-matriz se entiende en el espacio vectorial sobre el campo finito . En particular, surge una forma equivalente de escribir la definición del producto interno para el código Hadamard mediante el uso de la matriz generadora cuyas columnas constan de todas las cadenas. de longitud , es decir,
dónde es el -th vector binario en orden lexicográfico . Por ejemplo, la matriz generadora para el código de dimensión de Hadamard es:
La matriz es un -matriz y da lugar al operador lineal .
La matriz generadora del código Hadamard aumentado se obtiene restringiendo la matriza las columnas cuya primera entrada es uno. Por ejemplo, la matriz generadora para el código de dimensión de Hadamard aumentado es:
Luego es un mapeo lineal con .
En general , la matriz generadora del código Hadamard aumentado es una matriz de verificación de paridad para el código de longitud Hamming extendido y dimensión , que hace que el código Hadamard aumentado sea el código dual del código Hamming extendido. Por lo tanto, una forma alternativa de definir el código de Hadamard es en términos de su matriz de verificación de paridad: la matriz de verificación de paridad del código de Hadamard es igual a la matriz generadora del código de Hamming.
Construcción usando matrices generales de Hadamard
Los códigos de Hadamard se obtienen de una matriz H de n- por- n Hadamard . En particular, los 2 n palabras de código del código son las filas de H y las filas de - H . Para obtener un código sobre el alfabeto {0,1} , se aplica el mapeo −1, 1, 1, 0 o, de manera equivalente, x ↦ (1 - x ) / 2, a los elementos de la matriz. Que la distancia mínima del código es n / 2 se sigue de la propiedad definitoria de las matrices de Hadamard, es decir, que sus filas son mutuamente ortogonales. Esto implica que dos filas distintas de una matriz de Hadamard difieren exactamente en n / 2 posiciones y, dado que la negación de una fila no afecta la ortogonalidad, que cualquier fila de H difiere de cualquier fila de - H también en n / 2 posiciones, excepto cuando las filas corresponden, en cuyo caso difieren en n posiciones.
Para obtener el código Hadamard aumentado arriba con , la matriz H de Hadamard elegida debe ser del tipo Sylvester, lo que da lugar a una longitud de mensaje de.
Distancia
La distancia de un código es la distancia mínima de Hamming entre dos palabras de código distintas, es decir, el número mínimo de posiciones en las que difieren dos palabras de código distintas. Dado que el código de Walsh-Hadamard es un código lineal , la distancia es igual al peso mínimo de Hamming entre todas sus palabras de código distintas de cero. Todas las palabras de código distintas de cero del código Walsh-Hadamard tienen un peso Hamming de exactamente por el siguiente argumento.
Dejar ser un mensaje distinto de cero. Entonces el siguiente valor es exactamente igual a la fracción de posiciones en la palabra de código que son iguales a uno:
El hecho de que este último valor sea exactamente se llama el principio de subsum aleatorio . Para ver que es verdad, asuma sin pérdida de generalidad que. Entonces, cuando se condiciona a los valores de, el evento es equivalente a para algunos Dependiendo de y . La probabilidad de que sucede es exactamente . Por lo tanto, de hecho, todas las palabras de código distintas de cero del código Hadamard tienen un peso Hamming relativo, y por lo tanto, su distancia relativa es .
La distancia relativa del código Hadamard aumentado es también, pero ya no tiene la propiedad de que cada palabra de código distinta de cero tenga un peso exacto ya que el todo s vector es una palabra clave del código aumentado de Hadamard. Esto se debe a que el vector codifica a . Además, siempre que es distinto de cero y no es el vector , el principio de subsum aleatorio se aplica de nuevo, y el peso relativo de es exactamente .
Decodificabilidad local
Un código decodificable localmente es un código que permite recuperar un solo bit del mensaje original con alta probabilidad al observar solo una pequeña parte de la palabra recibida.
Un código es -consulta localmente decodificable si es un mensaje bit,, se puede recuperar marcando bits de la palabra recibida. Más formalmente, un código,, es -descodificable localmente, si existe un decodificador probabilístico, , tal que (Nota:representa la distancia de Hamming entre vectores y ) :
, implica que
Teorema 1: El código de Walsh-Hadamard es-localmente decodificable para todos .
Lema 1: Para todas las palabras de código, en un código Walsh-Hadamard, , , dónde representar los bits en en posiciones y respectivamente, y representa el bit en la posición .
Prueba del lema 1
Dejar ser la palabra clave en correspondiente al mensaje .
Dejar ser la matriz generadora de .
Por definición, . De esto,. Por la construcción de, . Por tanto, por sustitución,.
Prueba del teorema 1
Para demostrar el teorema 1, construiremos un algoritmo de decodificación y probaremos su corrección.
Algoritmo
Entrada: palabra recibida
Para cada :
- Elegir uniformemente al azar
- Elegir tal que dónde es el xor bit a bit de y .
Salida: Mensaje
Prueba de corrección
Para cualquier mensaje, , y recibí la palabra tal que difiere de como máximo fracción de bits, se puede decodificar con probabilidad al menos .
Por el lema 1, . Desde y se recogen uniformemente, la probabilidad de que es como máximo . De manera similar, la probabilidad de que es como máximo . Por el límite de unión , la probabilidad de que o no coinciden con los bits correspondientes en es como máximo . Si ambos y corresponden a las , entonces se aplicará el lema 1, y por lo tanto, el valor adecuado de será calculado. Por tanto, la probabilidad se decodifica correctamente es al menos . Por lo tanto, y para ser positivo, .
Por lo tanto, el código de Walsh-Hadamard es decodificable localmente para
Optimalidad
Para k ≤ 7, los códigos lineales de Hadamard han demostrado ser óptimos en el sentido de distancia mínima. [7]
Ver también
- Secuencia Zadoff-Chu : mejora los códigos Walsh-Hadamard
Referencias
- ^ Malek, Massoud (2006). "Códigos Hadarmark". Teoría de la codificación (PDF) . Archivado desde el original (PDF) el 9 de enero de 2020.
- ^ Amadei, M .; Manzoli, Umberto; Merani, Maria Luisa (17 de noviembre de 2002). "Sobre la asignación de códigos Walsh y cuasi-ortogonales en un sistema DS-CDMA multiportadora con múltiples clases de usuarios". Conferencia Global de Telecomunicaciones, 2002. GLOBECOM'02. IEEE . 1 . IEEE . págs. 841–845. doi : 10.1109 / GLOCOM.2002.1188196 . ISBN 0-7803-7632-3.
- ^ Arora, Sanjeev ; Barak, Boaz (2009). "Sección 19.2.2". Complejidad computacional: un enfoque moderno . Prensa de la Universidad de Cambridge . ISBN 978-0-521-42426-4.
- ^ Guruswami, Venkatesan (2009). Lista de decodificación de códigos binarios (PDF) . pag. 3.
- ^ Bose, Raj Chandra ; Shrikhande, Sharadchandra Shankar (junio de 1959). "Una nota sobre un resultado en la teoría de la construcción del código". Información y control . 2 (2): 183-194. CiteSeerX 10.1.1.154.2879 . doi : 10.1016 / S0019-9958 (59) 90376-6 .
- ^ Langton, Charan (2002). "Tutorial CDMA: Guía intuitiva de los principios de las comunicaciones" (PDF) . Complejo a Real. Archivado (PDF) desde el original el 20 de julio de 2011 . Consultado el 10 de noviembre de 2017 .
- ^ Jaffe, David B .; Bouyukliev, Iliya. "Códigos lineales binarios óptimos de dimensión como máximo siete" . Archivado desde el original el 8 de agosto de 2007 . Consultado el 21 de agosto de 2007 .
Otras lecturas
- Rudra, Atri. "Código Hamming y encuadernado Hamming" (PDF) . Apuntes de conferencias .
- Rudolph, Dietmar; Rudolph, Matthias (12 de abril de 2011). "46.4. Hadamard– oder Walsh – Codes". Modulationsverfahren (PDF) (en alemán). Cottbus, Alemania: Universidad Tecnológica de Brandenburgo (BTU). pag. 214. Archivado (PDF) desde el original el 16 de junio de 2021 . Consultado el 14 de junio de 2021 . (xiv + 225 páginas)