Hispanopedia Wiki
Articulo de referencia

Código de Hadamard

n=2^k "},"message_length":{"wt":" k "},"rate":{"wt":" k/2^k "},"distance":{"wt":" d=2^{k-1} "},"alphabet_size":{"wt":" 2 "},"notation":{"wt":" [2^k,k,2^{k-1}]_2 -code"}},"i":0}}...

Hispanopedia WikiContenido en espanolLectura gratuita

Matriz del código Hadamard aumentado [32, 6, 16] para el código Reed-Muller (1, 5) de la sonda espacial Mariner 9 de la NASA.
Operaciones XOR Aquí, los campos blancos representan 0 y los campos rojos representan 1.

El código Hadamard es un código de corrección de errores que recibe su nombre del matemático francés Jacques Hadamard y se utiliza para la detección y corrección de errores al transmitir 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 la codificación , matemáticas e informática teórica . El código Hadamard también se conoce como código Walsh , familia Walsh [ 2 ] y código Walsh-Hadamard [ 3 ] en reconocimiento al matemático estadounidense Joseph Leonard Walsh .

La especificación matemática del código Hadamard es bastante compleja y se describe en Construcciones . Es un ejemplo de un código lineal de longitud2metro{\displaystyle 2^{m}}sobre un alfabeto binario . Desafortunadamente, este término es algo ambiguo, ya que algunas referencias asumen una longitud de mensaje.k=metro{\displaystyle k=m}mientras que otros asumen una longitud de mensaje dek=metro+1{\displaystyle k=m+1}En este artículo, el primer caso se denomina código de Hadamard, mientras que el segundo se denomina código de Hadamard aumentado .

El código Hadamard es único en el sentido de que cada palabra clave distinta de cero tiene un peso de Hamming de exactamente2k−1{\displaystyle 2^{k-1}}, lo que implica que la distancia del código también es2k−1{\displaystyle 2^{k-1}}. En la notación estándar de la teoría de codificación para códigos de bloques , el código de Hadamard es un[2k,k,2k−1]2{\displaystyle [2^{k},k,2^{k-1}]_{2}}-código, es decir, es un código lineal sobre un alfabeto binario , tiene longitud de bloque2k{\displaystyle 2^{k}}, longitud (o dimensión) del mensajek{\displaystyle k}y distancia mínima2k/2{\displaystyle 2^{k}/2}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 Hadamard aumentado es una versión ligeramente mejorada del código Hadamard; es un[2k,k+1,2k−1]2{\displaystyle [2^{k},k+1,2^{k-1}]_{2}}-código y por lo tanto tiene una tasa ligeramente mejor mientras mantiene la distancia relativa de1/2{\displaystyle 1/2}y, por lo tanto, es el preferido en aplicaciones prácticas. En teoría de la comunicación, se le llama simplemente código de Hadamard y es el mismo que el código de Reed-Muller de primer orden sobre el alfabeto binario. [ 4 ]

Normalmente, los códigos de Hadamard se basan en la construcción de matrices de Hadamard de Sylvester , pero el término "código de Hadamard" también se usa para referirse a códigos construidos a partir de matrices de 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(norte,2norte,norte/2)2{\displaystyle (n,2n,n/2)_{2}}, lo que significa que es un código binario no necesariamente lineal con 2 n palabras clave de longitud de bloque n y distancia mínima n /2. El esquema de construcción y decodificación que se describe a continuación se aplica para n general , pero la propiedad de linealidad y la identificación con los 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 examina 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 pruebas verificables probabilísticamente . Dado que la distancia relativa del código Hadamard es 1/2, normalmente solo se puede esperar recuperar como máximo 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 haya menos de12−ϵ{\displaystyle {\frac {1}{2}}-\epsilon }Algunos 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 . En la literatura sobre CDMA, es habitual referirse a las palabras clave como «códigos». Cada usuario utilizará una palabra clave, o «código», diferente para modular su señal. Dado que las palabras clave Walsh son matemáticamente ortogonales , una señal codificada con Walsh aparece como ruido aleatorio para un terminal móvil compatible con CDMA , a menos que dicho terminal utilice la misma palabra clave que la utilizada para codificar la señal entrante . [ 6 ]

Historia

El nombre más común para este código en la literatura es código Hadamard . Sin embargo, en la actualidad, estos códigos de corrección de errores se conocen como códigos Walsh-Hadamard.

Hay una razón para ello:

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 corrector de errores , el código de Hamming , en la década de 1940.

El código de Hadamard se basa en matrices de Hadamard, y aunque existen muchas matrices de Hadamard diferentes que podrían utilizarse, normalmente solo se utiliza la construcción de matrices de Hadamard de Sylvester para obtener las palabras clave del código de Hadamard.

James Joseph Sylvester desarrolló su construcción de matrices de Hadamard en 1867, lo cual, de hecho, es anterior al trabajo de Hadamard sobre dichas matrices. Por lo tanto, el nombre de código de Hadamard es objeto de controversia y, en ocasiones, se le denomina código de Walsh , en honor al matemático estadounidense Joseph Leonard Walsh .

Durante la misión Mariner 9 de 1971 se utilizó un código Hadamard aumentado para corregir los errores de transmisión de imágenes. Los valores binarios utilizados en esta misión tenían una longitud de 6 bits, que representaban 64 valores de escala de grises .

Debido a las limitaciones en la calidad de la alineación del transmisor en ese momento (debido a problemas con el bucle de seguimiento Doppler), la longitud máxima de datos útiles era de aproximadamente 30 bits. En lugar de usar un código de repetición , se utilizó un código Hadamard [32, 6, 16].

Mediante este esquema se podían corregir errores de hasta 7 bits por palabra de 32 bits. 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, aunque su velocidad 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 denominaba "Máquina Verde". Empleaba la transformada rápida de Fourier , que puede triplicar la velocidad de decodificación. Desde la década de 1990, el uso de este código por parte de los programas espaciales prácticamente ha cesado, y la Red del Espacio Profundo de la NASA no admite este sistema de corrección de errores para sus antenas de más de 26  metros.

Construcciones

Si bien todos los códigos de Hadamard se basan en matrices de Hadamard, su construcción difiere sutilmente según el campo científico, el autor y el uso. 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, suelen buscar que la tasa de transmisión sea lo más alta posible, incluso si esto implica que la construcción sea 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, por lo que se prefieren construcciones más simples de códigos de Hadamard, ya que se pueden analizar de manera más elegante.

Construcción utilizando productos internos

Cuando se le da un mensaje binarioincógnita∈{0,1}k{\displaystyle x\in \{0,1\}^{k}}de longitudk{\displaystyle k}El código Hadamard codifica el mensaje en una palabra clave.Tenía(incógnita){\displaystyle {\text{Tenía}}(x)}utilizando una función de codificaciónTenía:{0,1}k→{0,1}2k.{\displaystyle {\text{Tenía}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}.} Esta función utiliza el producto interno.⟨incógnita,y⟩{\displaystyle \langle x,y\rangle }de dos vectoresincógnita,y∈{0,1}k{\displaystyle x,y\in \{0,1\}^{k}}, que se define de la siguiente manera:

⟨incógnita,y⟩=∑i=1kincógnitaiyi mod 2.{\displaystyle \langle x,y\rangle =\sum _{i=1}^{k}x_{i}y_{i}\ {\bmod {\ }}2\,.}

Luego la codificación de Hadamard deincógnita{\displaystyle x}se define como la secuencia de todos los productos internos conincógnita{\displaystyle x}:

Tenía(incógnita)=(⟨incógnita,y⟩)y∈{0,1}k{\displaystyle {\text{Tenía}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{0,1\}^{k}}}

Como se mencionó anteriormente, el código Hadamard aumentado se utiliza en la práctica ya que el código Hadamard en sí mismo es algo ineficiente. Esto se debe a que, si el primer bit dey{\displaystyle y}es cero,y1=0{\displaystyle y_{1}=0}, entonces el producto interno no contiene información alguna sobreincógnita1{\displaystyle x_{1}}y por lo tanto, es imposible decodificarlo completamente.incógnita{\displaystyle x}a partir de esas posiciones de la palabra clave solamente. Por otro lado, cuando la palabra clave está restringida a las posiciones dondey1=1{\displaystyle y_{1}=1}, todavía es posible decodificar completamenteincógnita{\displaystyle x}Por lo tanto, tiene sentido restringir el código de Hadamard a estas posiciones, lo que da lugar a la codificación de Hadamard aumentada deincógnita{\displaystyle x}; eso es,pHad(incógnita)=(⟨incógnita,y⟩)y∈{1}×{0,1}k−1{\displaystyle {\text{pHad}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{1\}\times \{0,1\}^{k-1}}}.

Construcción mediante una matriz generadora

El código de Hadamard es un código lineal, y todos los códigos lineales pueden generarse mediante una matriz generadora.GRAMO{\displaystyle G}. Esta es una matriz tal queTenía(incógnita)=incógnita⋅GRAMO{\displaystyle {\text{Tenía}}(x)=x\cdot G}se aplica a todosincógnita∈{0,1}k{\displaystyle x\in \{0,1\}^{k}}donde el mensajeincógnita{\displaystyle x}se considera como un vector fila y el producto vector-matriz se entiende en el espacio vectorial sobre el campo finito.F2{\displaystyle \mathbb {F} _{2}}. En particular, una forma equivalente de escribir la definición del producto interno para el código de Hadamard surge al usar la matriz generadora cuyas columnas consisten en todas cadenasy{\displaystyle y}de longitudk{\displaystyle k}, eso es,

GRAMO=(↑↑↑y1y2…y2k↓↓↓).{\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\y_{1}&y_{2}&\dots &y_{2^{k}}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}\,.}

dóndeyi∈{0,1}k{\displaystyle y_{i}\in \{0,1\}^{k}}es eli{\displaystyle i}-ésimo vector binario en orden lexicográfico . Por ejemplo, la matriz generadora para el código Hadamard de dimensiónk=3{\displaystyle k=3}es:

GRAMO=[000011110011001101010101].{\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 matrizGRAMO{\displaystyle G}es un(k×2k){\displaystyle (k\times 2^{k})}-matriz y da lugar al operador linealTenía:{0,1}k→{0,1}2k{\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}}.

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

GRAMO′=[111100110101].{\displaystyle G'={\begin{bmatrix}1&1&1&1\\0&0&1&1\\0&1&0&1\end{bmatrix}}.}

EntoncespHad:{0,1}k→{0,1}2k−1{\displaystyle {\text{pHad}}:\{0,1\}^{k}\to \{0,1\}^{2^{k-1}}}es una aplicación lineal conpHad(incógnita)=incógnita⋅GRAMO′{\displaystyle {\text{pHad}}(x)=x\cdot G'}.

Para generalk{\displaystyle k}, la matriz generadora del código Hadamard aumentado es una matriz de verificación de paridad para el código Hamming extendido de longitud2k−1{\displaystyle 2^{k-1}}y dimensión2k−1−k{\displaystyle 2^{k-1}-k}lo que convierte al código de Hadamard aumentado en el código dual del código de 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 mediante matrices de Hadamard generales

Los códigos de Hadamard se obtienen a partir de una matriz de Hadamard H de n × n . En particular, las 2n palabras clave 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 a los elementos de la matriz la transformación −1 ↦ 1, 1 ↦ 0, o, equivalentemente, x ↦ (1 − x )/2. Que la distancia mínima del código sea n /2 se deduce de la propiedad definitoria de las matrices de Hadamard, a saber, 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 a la ortogonalidad, que cualquier fila de H difiere de cualquier fila de −H también en n /2 posiciones, excepto cuando las filas se corresponden, en cuyo caso difieren en n posiciones.        

Para obtener el código de Hadamard aumentado anterior connorte=2k−1{\displaystyle n=2^{k-1}}, la matriz de Hadamard elegida H debe ser de tipo Sylvester, lo que da lugar a una longitud de mensaje deregistro2⁡(2norte)=k{\displaystyle \log _{2}(2n)=k}.

Distancia

La distancia de un código es la distancia de Hamming mínima entre dos palabras clave distintas cualesquiera, es decir, el número mínimo de posiciones en las que dos palabras clave distintas difieren. Dado que el código de Walsh-Hadamard es un código lineal , la distancia es igual al peso de Hamming mínimo entre todas sus palabras clave no nulas. Todas las palabras clave no nulas del código de Walsh-Hadamard tienen un peso de Hamming exactamente igual a .2k−1{\displaystyle 2^{k-1}}mediante el siguiente argumento.

Dejarincógnita∈{0,1}k{\displaystyle x\in \{0,1\}^{k}}sea ​​un mensaje distinto de cero. Entonces, el siguiente valor es exactamente igual a la fracción de posiciones en la palabra clave que son iguales a uno:

Pry∈{0,1}k[(Tenía(incógnita))y=1]=Pry∈{0,1}k[⟨incógnita,y⟩=1].{\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 este último valor sea exactamente1/2{\displaystyle 1/2}Se denomina principio de subsuma aleatoria . Para comprobar que es cierto, supongamos sin pérdida de generalidad queincógnita1=1{\displaystyle x_{1}=1}. Luego, cuando se condiciona a los valores dey2,…,yk{\displaystyle y_{2},\dots ,y_{k}}, el evento es equivalente ay1⋅incógnita1=b{\displaystyle y_{1}\cdot x_{1}=b}para algunosb∈{0,1}{\displaystyle b\in \{0,1\}}Dependiendo deincógnita2,…,incógnitak{\displaystyle x_{2},\dots ,x_{k}}yy2,…,yk{\displaystyle y_{2},\dots ,y_{k}}. La probabilidad de quey1=b{\displaystyle y_{1}=b}Sucede exactamente1/2{\displaystyle 1/2}Por lo tanto, de hecho, todas las palabras clave no nulas del código Hadamard tienen un peso de Hamming relativo.1/2{\displaystyle 1/2}y por lo tanto, su distancia relativa es1/2{\displaystyle 1/2}.

La distancia relativa del código Hadamard aumentado es1/2{\displaystyle 1/2}también, pero ya no tiene la propiedad de que cada palabra clave distinta de cero tenga exactamente el mismo peso.1/2{\displaystyle 1/2}ya que todos1{\displaystyle 1}vector s12k−1{\displaystyle 1^{2^{k-1}}}es una palabra clave del código Hadamard aumentado. Esto se debe a que el vectorincógnita=10k−1{\displaystyle x=10^{k-1}}codifica apHad(10k−1)=12k−1{\displaystyle {\text{pHad}}(10^{k-1})=1^{2^{k-1}}}Además, siempre queincógnita{\displaystyle x}es distinto de cero y no es el vector10k−1{\displaystyle 10^{k-1}}, el principio de subsuma aleatoria se aplica de nuevo, y el peso relativo deTenía(incógnita){\displaystyle {\text{Had}}(x)}es exactamente1/2{\displaystyle 1/2}.

Decodificabilidad local

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

Un código esq{\displaystyle q}-consulta decodificable localmente si un bit de mensaje,incógnitai{\displaystyle x_{i}}, se puede recuperar comprobandoq{\displaystyle q}fragmentos de la palabra recibida. Más formalmente, un código,do:{0,1}k→{0,1}norte{\displaystyle C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}}, es(q,δ≥0,ϵ≥0){\displaystyle (q,\delta \geq 0,\epsilon \geq 0)}-localmente decodificable, si existe un decodificador probabilístico,D:{0,1}norte→{0,1}k{\displaystyle D:\{0,1\}^{n}\rightarrow \{0,1\}^{k}}, de tal manera que (Nota:Δ(incógnita,y){\displaystyle \Delta (x,y)}representa la distancia de Hamming entre vectoresincógnita{\displaystyle x}yy{\displaystyle y}) :

∀incógnita∈{0,1}k,∀y∈{0,1}norte{\displaystyle \forall x\in \{0,1\}^{k},\forall y\in \{0,1\}^{n}},Δ(y,do(incógnita))≤δnorte{\displaystyle \Delta (y,C(x))\leq \delta n}implica quePAGr[D(y)i=incógnitai]≥12+ϵ,∀i∈[k]{\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(2,δ,12−2δ){\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}-decodificable localmente para todos0≤δ≤14{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}.

Lema 1: Para todas las palabras clave,do{\displaystyle c}en un código Walsh-Hadamard,do{\displaystyle C},doi+doj=doi+j{\displaystyle c_{i}+c_{j}=c_{i+j}}, dóndedoi,doj{\displaystyle c_{i},c_{j}}representar los bits endo{\displaystyle c}en puestosi{\displaystyle i}yj{\displaystyle j}respectivamente ydoi+j{\displaystyle c_{i+j}}representa el bit en la posición(i+j){\displaystyle (i+j)}.

Demostración del lema 1

Dejardo(incógnita)=do=(do0,…,do2norte−1){\displaystyle C(x)=c=(c_{0},\dots ,c_{2^{n}-1})}ser la palabra clave endo{\displaystyle C}correspondiente al mensajeincógnita{\displaystyle x}.

DejarGRAMO=(↑↑↑gramo0gramo1…gramo2norte−1↓↓↓){\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\g_{0}&g_{1}&\dots &g_{2^{n}-1}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}}sea ​​la matriz generadora dedo{\displaystyle C}.

Por definición,doi=incógnita⋅gramoi{\displaystyle c_{i}=x\cdot g_{i}}. A partir de esto,doi+doj=incógnita⋅gramoi+incógnita⋅gramoj=incógnita⋅(gramoi+gramoj){\displaystyle c_{i}+c_{j}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j})}. Mediante la construcción deGRAMO{\displaystyle G},gramoi+gramoj=gramoi+j{\displaystyle g_{i}+g_{j}=g_{i+j}}. Por lo tanto, por sustitución,doi+doj=incógnita⋅gramoi+j=doi+j{\displaystyle c_{i}+c_{j}=x\cdot g_{i+j}=c_{i+j}}.

Demostración del teorema 1

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

Algoritmo

Entrada: Palabra recibiday=(y0,…,y2norte−1){\displaystyle y=(y_{0},\dots ,y_{2^{n}-1})}

Para cadai∈{1,…,norte}{\displaystyle i\in \{1,\dots ,n\}}:

  1. Elegirj∈{0,…,2norte−1}{\displaystyle j\in \{0,\dots ,2^{n}-1\}}uniformemente al azar.
  2. Elegirk∈{0,…,2norte−1}{\displaystyle k\in \{0,\dots ,2^{n}-1\}}de tal manera quej+k=mii{\displaystyle j+k=e_{i}}, dóndemii{\displaystyle e_{i}}es eli{\displaystyle i}-ésimo vector base estándar yj+k{\displaystyle j+k}es el xor bit a bit dej{\displaystyle j}yk{\displaystyle k}.
  3. incógnitai←yj+yk{\displaystyle x_{i}\gets y_{j}+y_{k}}.

Salida: Mensajeincógnita=(incógnita1,…,incógnitanorte){\displaystyle x=(x_{1},\dots ,x_{n})}

Prueba de corrección

Para cualquier mensaje,incógnita{\displaystyle x}y recibió noticiasy{\displaystyle y}de tal manera quey{\displaystyle y}difiere dedo=do(incógnita){\displaystyle c=C(x)}en como máximoδ{\displaystyle \delta }fracción de bits,incógnitai{\displaystyle x_{i}}puede ser decodificado con probabilidad al menos12+(12−2δ){\displaystyle {\frac {1}{2}}+({\frac {1}{2}}-2\delta )}.

Por el lema 1,doj+dok=doj+k=incógnita⋅gramoj+k=incógnita⋅mii=incógnitai{\displaystyle c_{j}+c_{k}=c_{j+k}=x\cdot g_{j+k}=x\cdot e_{i}=x_{i}}. Desdej{\displaystyle j}yk{\displaystyle k}se eligen uniformemente, la probabilidad de queyj≠doj{\displaystyle y_{j}\not =c_{j}}es como máximoδ{\displaystyle \delta }. De manera similar, la probabilidad de queyk≠dok{\displaystyle y_{k}\not =c_{k}}es como máximoδ{\displaystyle \delta }. Por el límite de unión , la probabilidad de que o bienyj{\displaystyle y_{j}}oyk{\displaystyle y_{k}}no coinciden con los bits correspondientes endo{\displaystyle c}es como máximo2δ{\displaystyle 2\delta }. Si ambosyj{\displaystyle y_{j}}yyk{\displaystyle y_{k}}corresponder ado{\displaystyle c}, entonces se aplicará el lema 1 y, por lo tanto, el valor propio deincógnitai{\displaystyle x_{i}}se calculará. Por lo tanto, la probabilidadincógnitai{\displaystyle x_{i}}se decodifica correctamente es al menos1−2δ{\displaystyle 1-2\delta }. Por lo tanto,ϵ=12−2δ{\displaystyle \epsilon ={\frac {1}{2}}-2\delta }y paraϵ{\displaystyle \epsilon }ser positivo,0≤δ≤14{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}.

Por lo tanto, el código Walsh-Hadamard es(2,δ,12−2δ){\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}decodificable localmente para0≤δ≤14{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}.

Optimalidad

Para k  ≤  7, se ha demostrado que los códigos lineales de Hadamard son óptimos en el sentido de distancia mínima. [ 7 ]

Véase también

Referencias

  1. ↑ Malek, Massoud (2006). "Códigos de Hadamard". Teoría de la codificación (PDF) . Archivado del original (PDF) el 9 de enero de 2020.
  2. ↑ 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 multicarrier con múltiples clases de usuarios". Conferencia Global de Telecomunicaciones, 2002. GLOBECOM'02. IEEE . Vol. 1. IEEE . págs. 841–845 . doi : 10.1109/GLOCOM.2002.1188196 . ISBN   0-7803-7632-3.
  3. ↑ Arora, Sanjeev ; Barak, Boaz (2009). "Sección 19.2.2". Complejidad computacional: un enfoque moderno . Cambridge University Press . ISBN 978-0-521-42426-4.
  4. ↑ Guruswami, Venkatesan (2009). Decodificación de listas de códigos binarios (PDF) . pág. 3. 
  5. ↑ Bose, Raj Chandra ; Shrikhande, Sharadchandra Shankar (junio de 1959). "Una nota sobre un resultado en la teoría de la construcción de códigos". Information and Control . 2 (2): 183– 194. CiteSeerX 10.1.1.154.2879 . doi : 10.1016/S0019-9958(59)90376-6 . 
  6. ↑ Langton, Charan [en Wikidata] (2002). "Tutorial de CDMA: Guía intuitiva de los principios de las comunicaciones" (PDF) . De lo complejo a lo real. Archivado (PDF) del original el 20 de julio de 2011. Recuperado el 10 de noviembre de 2017 .
  7. ↑ Jaffe, David B.; Bouyukliev, Iliya. "Códigos lineales binarios óptimos de dimensión como máximo siete" . Archivado del original el 8 de agosto de 2007. Recuperado el 21 de agosto de 2007 .

Lecturas adicionales

  • Rudra, Atri. "Código de Hamming y límite de Hamming" (PDF) . Apuntes de clase .
  • Rudolph, Dietmar; Rudolph, Matthias (12 de abril de 2011). "46.4. Códigos Hadamard o Walsh". Modulationsverfahren (PDF) (en alemán). Cottbus, Alemania: Universidad Tecnológica de Brandeburgo (BTU). pág.  214. Archivado (PDF) del original el 16 de junio de 2021. Consultado el 14 de junio de 2021 .(xiv+225 páginas)