Código Hadamard - Hadamard code

Código Hadamard
Lleva el nombre de	Jacques Hadamard
Clasificación
Escribe	Código de bloque lineal
Longitud del bloque	${\ Displaystyle n = 2 ^ {k}}$
Longitud del mensaje	${\ Displaystyle k}$
Índice	${\ Displaystyle k / 2 ^ {k}}$
Distancia	${\ Displaystyle d = 2 ^ {k-1}}$
Tamaño del alfabeto	${\ Displaystyle 2}$
Notación	${\ Displaystyle [2 ^ {k}, k, 2 ^ {k-1}] _ {2}}$-código
v t mi

Código Hadamard aumentado
Lleva el nombre de	Jacques Hadamard
Clasificación
Escribe	Código de bloque lineal
Longitud del bloque	${\ Displaystyle n = 2 ^ {k}}$
Longitud del mensaje	${\ Displaystyle k + 1}$
Índice	${\ Displaystyle (k + 1) / 2 ^ {k}}$
Distancia	${\ Displaystyle d = 2 ^ {k-1}}$
Tamaño del alfabeto	${\ Displaystyle 2}$
Notación	${\ Displaystyle [2 ^ {k}, k + 1,2 ^ {k-1}] _ {2}}$-código
v t mi

Matriz del código Hadamard aumentado [32, 6, 16] para el código Reed-Muller (1, 5) de la sonda espacial de la NASA Mariner 9

Operaciones XOR
Aquí los campos blancos representan 0
y los campos rojos 1

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 . Debido a sus propiedades matemáticas únicas, el código Hadamard no solo lo utilizan los ingenieros, sino que también se estudia intensamente en la teoría de la codificación , las matemáticas y la informática teórica . El código Hadamard se conoce también con los nombres de códigos de Walsh , de la familia de Walsh y códigos de Walsh-Hadamard en el reconocimiento del matemático estadounidense Joseph Leonard Walsh .

El código Hadamard es un ejemplo de un código lineal de longitud sobre un alfabeto binario . Desafortunadamente, este término es algo ambiguo ya que algunas referencias asumen una longitud de mensaje mientras que otras 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 . ${\ Displaystyle 2 ^ {m}}$${\ Displaystyle k = m}$${\ Displaystyle k = m + 1}$

El código de 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 lo es . En la notación de la teoría de codificación estándar para códigos de bloque , el código de Hadamard es un -código, es decir, es un código lineal sobre un alfabeto binario , tiene longitud de bloque , longitud (o dimensión) del mensaje 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. ${\ Displaystyle 2 ^ {k-1}}$${\ Displaystyle 2 ^ {k-1}}$${\ Displaystyle [2 ^ {k}, k, 2 ^ {k-1}] _ {2}}$ ${\ Displaystyle 2 ^ {k}}$${\ Displaystyle k}$ ${\ Displaystyle 2 ^ {k} / 2}$

El código de Hadamard aumentado es una versión ligeramente mejorada del código de Hadamard; es un código y, por lo tanto, tiene una velocidad ligeramente mejor mientras mantiene la distancia relativa de y, por lo 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. ${\ Displaystyle [2 ^ {k}, k + 1,2 ^ {k-1}] _ {2}}$${\ Displaystyle 1/2}$

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. 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. ${\ Displaystyle (n, 2n, n / 2) _ {2}}$

El código de Hadamard es un código decodificable localmente , que proporciona una forma de recuperar partes del mensaje original con alta probabilidad, mientras solo mira 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 se hayan corrompido menos de los bits de la palabra recibida. ${\ Displaystyle {\ frac {1} {2}} - \ epsilon}$

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 .

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 de Hadamard se basa en matrices de Hadamard, y aunque hay muchas matrices de Hadamard diferentes que podrían usarse aquí, normalmente solo se usa la construcción de Sylvester de las matrices de Hadamard para obtener las palabras de código del código de 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 representaba 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 se pueden corregir 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 de código 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: ${\ Displaystyle x \ in \ {0,1 \} ^ {k}}$${\ Displaystyle k}$${\ displaystyle {\ text {Tenía}} (x)}$${\ Displaystyle {\ text {Tenía}}: \ {0,1 \} ^ {k} \ a \ {0,1 \} ^ {2 ^ {k}}.}$ ${\ Displaystyle \ langle x, y \ rangle}$${\ Displaystyle x, y \ in \ {0,1 \} ^ {k}}$

${\ Displaystyle \ langle x, y \ rangle = \ sum _ {i = 1} ^ {k} x_ {i} y_ {i} \ {\ bmod {\}} 2 \ ,.}$

Entonces, la codificación de Hadamard se define como la secuencia de todos los productos internos con : ${\ Displaystyle x}$${\ Displaystyle x}$

${\ Displaystyle {\ text {Had}} (x) = {\ Big (} \ langle x, y \ rangle {\ Big)} _ {y \ in \ {0,1 \} ^ {k}}}$

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 a partir de esas posiciones de la palabra de código únicamente. Por otro lado, cuando la palabra de código está restringida a las posiciones donde , todavía es posible decodificar completamente . Por tanto, tiene sentido restringir el código Hadamard a estas posiciones, lo que da lugar a la codificación Hadamard aumentada de ; es decir, . ${\ Displaystyle y}$${\ Displaystyle y_ {1} = 0}$${\ Displaystyle x_ {1}}$${\ Displaystyle x}$${\ Displaystyle y_ {1} = 1}$${\ Displaystyle x}$${\ Displaystyle x}$${\ Displaystyle {\ text {pHad}} (x) = {\ Big (} \ langle x, y \ rangle {\ Big)} _ {y \ in \ {1 \} \ times \ {0,1 \} ^ {k-1}}}$

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 que se aplica a todos , donde el mensaje se ve como un vector de 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 utilizando la matriz generadora cuyas columnas constan de todas las cadenas de longitud , es decir, ${\ Displaystyle G}$${\ Displaystyle {\ text {Tenía}} (x) = x \ cdot G}$${\ Displaystyle x \ in \ {0,1 \} ^ {k}}$${\ Displaystyle x}$ ${\ Displaystyle \ mathbb {F} _ {2}}$${\ Displaystyle y}$${\ Displaystyle k}$

${\ displaystyle G = {\ begin {pmatrix} \ uparrow & \ uparrow && \ uparrow \\ y_ {1} & y_ {2} & \ dots & y_ {2 ^ {k}} \\\ downarrow & \ downarrow && \ downarrow \ end {pmatrix}} \ ,.}$

donde es el -ésimo vector binario en orden lexicográfico . Por ejemplo, la matriz generadora para el código de dimensión de Hadamard es: ${\ Displaystyle y_ {i} \ in \ {0,1 \} ^ {k}}$${\ Displaystyle i}$${\ Displaystyle k = 3}$

${\ displaystyle G = {\ begin {bmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \ end {bmatrix}}.}$

La matriz es una -matriz y da lugar al operador lineal . ${\ Displaystyle G}$${\ Displaystyle (k \ times 2 ^ {k})}$ ${\ Displaystyle {\ text {Had}}: \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {2 ^ {k}}}$

La matriz generadora del código Hadamard aumentado se obtiene restringiendo la matriz a las columnas cuya primera entrada es una. Por ejemplo, la matriz generadora para el código de dimensión de Hadamard aumentado es: ${\ Displaystyle G}$${\ Displaystyle k = 3}$

${\ displaystyle G '= {\ begin {bmatrix} 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \ end {bmatrix}}.}$

Entonces es un mapeo lineal con . ${\ Displaystyle {\ text {pHad}}: \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {2 ^ {k-1}}}$${\ Displaystyle {\ text {pHad}} (x) = x \ cdot G '}$

En general , la matriz generadora del código Hadamard aumentado es una matriz de verificación de paridad para el código Hamming extendido de longitud y dimensión , lo 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. ${\ Displaystyle k}$${\ Displaystyle 2 ^ {k-1}}$${\ Displaystyle 2 ^ {k-1} -k}$

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 anterior con , la matriz H de Hadamard elegida debe ser del tipo Sylvester, lo que da lugar a una longitud de mensaje de . ${\ Displaystyle n = 2 ^ {k-1}}$${\ Displaystyle \ log _ {2} (2n) = k}$

Distancia

La distancia de un código es la distancia de Hamming mínima 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 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. ${\ Displaystyle 2 ^ {k-1}}$

Sea 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: ${\ Displaystyle x \ in \ {0,1 \} ^ {k}}$

${\ Displaystyle \ Pr _ {y \ in \ {0,1 \} ^ {k}} {\ big [} ({\ text {Had}} (x)) _ {y} = 1 {\ big]} = \ Pr _ {y \ in \ {0,1 \} ^ {k}} {\ big [} \ langle x, y \ rangle = 1 {\ big]} \ ,.}$

El hecho de que el último valor sea exactamente se denomina principio de subsuma aleatorio . Para ver que es verdad, asuma sin pérdida de generalidad eso . Entonces, cuando está condicionado a los valores de , el evento es equivalente a para algunos dependiendo de y . La probabilidad de que suceda es exactamente . Por lo tanto, de hecho, todas las palabras de código distintas de cero del código Hadamard tienen un peso de Hamming relativo y, por lo tanto, su distancia relativa es . ${\ Displaystyle 1/2}$${\ Displaystyle x_ {1} = 1}$${\ Displaystyle y_ {2}, \ dots, y_ {k}}$${\ Displaystyle y_ {1} \ cdot x_ {1} = b}$${\ Displaystyle b \ in \ {0,1 \}}$${\ Displaystyle x_ {2}, \ dots, x_ {k}}$${\ Displaystyle y_ {2}, \ dots, y_ {k}}$${\ Displaystyle y_ {1} = b}$${\ Displaystyle 1/2}$${\ Displaystyle 1/2}$${\ Displaystyle 1/2}$

La distancia relativa del código de Hadamard aumentado también lo es , pero ya no tiene la propiedad de que cada palabra de código distinta de cero tenga un peso exacto, ya que el vector all es una palabra de código del código de Hadamard aumentado. Esto se debe a que el vector se codifica en . Además, siempre que sea ​​distinto de cero y no el vector , el principio de subsuma aleatorio se aplica de nuevo, y el peso relativo de es exactamente . ${\ Displaystyle 1/2}$${\ Displaystyle 1/2}$${\ Displaystyle 1}$${\ Displaystyle 1 ^ {2 ^ {k-1}}}$${\ Displaystyle x = 10 ^ {k-1}}$${\ displaystyle {\ text {pHad}} (10 ^ {k-1}) = 1 ^ {2 ^ {k-1}}}$${\ Displaystyle x}$${\ Displaystyle 10 ^ {k-1}}$${\ displaystyle {\ text {Tenía}} (x)}$${\ Displaystyle 1/2}$

Decodificabilidad local

Un código decodificable localmente es un código que permite que un solo bit del mensaje original se recupere con alta probabilidad con solo mirar una pequeña porción de la palabra recibida.

Un código es -query decodificable localmente si un bit de mensaje,, se puede recuperar verificando bits de la palabra recibida. Más formalmente, un código`` es -localmente decodificable, si existe un decodificador probabilístico`` tal que (Nota: representa la distancia de Hamming entre vectores y ) : ${\ Displaystyle q}$${\ Displaystyle x_ {i}}$${\ Displaystyle q}$${\ Displaystyle C: \ {0,1 \} ^ {k} \ rightarrow \ {0,1 \} ^ {n}}$${\ Displaystyle (q, \ delta \ geq 0, \ epsilon \ geq 0)}$${\ Displaystyle D: \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \} ^ {k}}$${\ Displaystyle \ Delta (x, y)}$${\ Displaystyle x}$${\ Displaystyle y}$

${\ Displaystyle \ para todos los x \ en \ {0,1 \} ^ {k}, \ para todos y \ en \ {0,1 \} ^ {n}}$, implica que${\ Displaystyle \ Delta (y, C (x)) \ leq \ delta n}$${\ Displaystyle Pr [D (y) _ {i} = x_ {i}] \ geq {\ frac {1} {2}} + \ epsilon, \ forall i \ in [k]}$

Teorema 1: El código de Walsh-Hadamard es decodificable localmente para todos . ${\ Displaystyle (2, \ delta, {\ frac {1} {2}} - 2 \ delta)}$${\ Displaystyle 0 \ leq \ delta \ leq {\ frac {1} {4}}}$

Lema 1: Para todas las palabras de código, en un código de Walsh-Hadamard, , , donde representan los bits en en posiciones y respectivamente, y representa el bit en la posición . ${\ Displaystyle c}$${\ Displaystyle C}$${\ Displaystyle c_ {i} + c_ {j} = c_ {i + j}}$${\ Displaystyle c_ {i}, c_ {j}}$${\ Displaystyle c}$${\ Displaystyle i}$${\ Displaystyle j}$${\ Displaystyle c_ {i + j}}$${\ Displaystyle (i + j)}$

Prueba del lema 1

Sea la palabra clave correspondiente al mensaje . ${\ Displaystyle C (x) = c = (c_ {0}, \ dots, c_ {2 ^ {n} -1})}$${\ Displaystyle C}$${\ Displaystyle x}$

Sea la matriz generadora de . ${\ displaystyle G = {\ begin {pmatrix} \ uparrow & \ uparrow && \ uparrow \\ g_ {0} & g_ {1} & \ dots & g_ {2 ^ {n} -1} \\\ downarrow & \ downarrow && \ flecha abajo \ end {pmatrix}}}$${\ Displaystyle C}$

Por definición, . De esto ,. Por la construcción de , . Por lo tanto, por sustitución, . ${\ Displaystyle c_ {i} = x \ cdot g_ {i}}$${\ Displaystyle c_ {i} + c_ {j} = x \ cdot g_ {i} + x \ cdot g_ {j} = x \ cdot (g_ {i} + g_ {j})}$${\ Displaystyle G}$${\ Displaystyle g_ {i} + g_ {j} = g_ {i + j}}$${\ Displaystyle c_ {i} + c_ {j} = x \ cdot g_ {i + j} = c_ {i + j}}$

Prueba del teorema 1

Para demostrar el teorema 1, construiremos un algoritmo de decodificación y probaremos su corrección.

Algoritmo

Entrada: palabra recibida${\ Displaystyle y = (y_ {0}, \ dots, y_ {2 ^ {n} -1})}$

Para cada uno : ${\ Displaystyle i \ in \ {1, \ dots, n \}}$

1. Elija uniformemente al azar.${\ Displaystyle j \ in \ {0, \ dots, 2 ^ {n} -1 \}}$
2. Elija tal que , donde es el -ésimo vector base estándar y es el xor bit a bit de y .${\ Displaystyle k \ in \ {0, \ dots, 2 ^ {n} -1 \}}$${\ Displaystyle j + k = e_ {i}}$${\ Displaystyle e_ {i}}$${\ Displaystyle i}$${\ Displaystyle j + k}$${\ Displaystyle j}$${\ Displaystyle k}$
3. ${\ Displaystyle x_ {i} \ obtiene y_ {j} + y_ {k}}$.

Salida: Mensaje${\ Displaystyle x = (x_ {1}, \ dots, x_ {n})}$

Prueba de corrección

Para cualquier mensaje, y la palabra recibida que difiera como máximo de una fracción de bits, se puede decodificar con probabilidad al menos . ${\ Displaystyle x}$${\ Displaystyle y}$${\ Displaystyle y}$${\ Displaystyle c = C (x)}$${\ Displaystyle \ delta}$${\ Displaystyle x_ {i}}$${\ Displaystyle {\ frac {1} {2}} + ({\ frac {1} {2}} - 2 \ delta)}$

Por el lema 1, . Dado que y se recogen de manera uniforme, la probabilidad de que sea ​​como máximo . Del mismo modo, la probabilidad de que sea ​​como máximo . Por el límite de unión , la probabilidad de que coincida o no con los bits correspondientes es como máximo . Si ambos y corresponden a , entonces se aplicará el lema 1 y, por lo tanto, se calculará el valor adecuado de . Por lo tanto, la probabilidad de que se decodifique correctamente es al menos . Por lo tanto, y de ser positivo, . ${\ Displaystyle c_ {j} + c_ {k} = c_ {j + k} = x \ cdot g_ {j + k} = x \ cdot e_ {i} = x_ {i}}$${\ Displaystyle j}$${\ Displaystyle k}$${\ Displaystyle y_ {j} \ not = c_ {j}}$${\ Displaystyle \ delta}$${\ Displaystyle y_ {k} \ not = c_ {k}}$${\ Displaystyle \ delta}$${\ Displaystyle y_ {j}}$${\ Displaystyle y_ {k}}$${\ Displaystyle c}$${\ Displaystyle 2 \ delta}$${\ Displaystyle y_ {j}}$${\ Displaystyle y_ {k}}$${\ Displaystyle c}$${\ Displaystyle x_ {i}}$${\ Displaystyle x_ {i}}$${\ Displaystyle 1-2 \ delta}$${\ Displaystyle \ epsilon = {\ frac {1} {2}} - 2 \ delta}$${\ Displaystyle \ epsilon}$${\ Displaystyle 0 \ leq \ delta \ leq {\ frac {1} {4}}}$

Por lo tanto, el código Walsh-Hadamard se puede decodificar localmente para . ${\ Displaystyle (2, \ delta, {\ frac {1} {2}} - 2 \ delta)}$${\ Displaystyle 0 \ leq \ delta \ leq {\ frac {1} {4}}}$

Optimalidad

Para k  ≤ 7, los códigos lineales de Hadamard han demostrado ser óptimos en el sentido de distancia mínima.

Ver también

• Secuencia Zadoff-Chu : mejora los códigos Walsh-Hadamard

Referencias

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)