Codi d'Hadamard

El codi d'Hadamard és un codi de correcció d'errors que s'utilitza per a la detecció i correcció d'errors durant la transmissió de missatges a través de canals molt sorollosos o poc fiables. El 1971 es va utilitzar el codi per transmetre fotos de Mart a la Terra des de la sonda espacial Mariner 9 de la NASA. Degut a les seves propietats matemàtiques úniques, el codi d'Hadamard no solament és utilitzat pels enginyers sinó també molt estudiat en teoria de codificació, matemàtiques i ciències de computació. El codi d'Hadamard porta el nom del matemàtic francès Jacques Hadamard. També es coneix amb els noms de codi Walsh, de la família Walsh,^[1] i codi de Walsh-Hadamard,^[2] en reconeixement del matemàtic nord-americà Joseph Leonard Walsh.

El codi d'Hadamard és un exemple d'un codi lineal sobre un alfabet binari que mapeja els missatges de longitud k per paraules de codi de longitud 2^k. És l'únic en què cada paraula de codi diferent de zero té un pes de Hamming exactament 2^k/2, el que implica que la distància del codi és també 2^k/2. En la notació estàndard de teoria de la codificació per a codis de bloc, el codi d'Hadamard és un codi [2^k, k, 2^k/2]₂, és a dir, és un codi lineal sobre un alfabet binari, té longitud de bloc 2^k, longitud del missatge (o dimensió) k, i distància mínima 2^k/2.

La longitud del bloc és molt gran en comparació amb la longitud del missatge, però per altra banda, els errors es poden corregir fins i tot en condicions extremadament sorolloses. El codi Hadamard perforat és una versió lleugerament millorada del codi d'Hadamard; és un [2^{k – 1}, k, 2^{k – 2}/2]₂ codi i per tant té una mica millor taxa mentre es manté la distància relativa de 1/2, i per tant es prefereix en aplicacions pràctiques. El codi d'Hadamard perforat és el mateix que el codi de Reed-Muller de primer ordre sobre l'alfabet binari.^[3]

Normalment, els codis d'Hadamard es basen en la construcció de Sylvester de matrius d'Hadamard però el terme "codi d'Hadamard" també s'utilitza per fer referència als codis construïts a partir de matrius d'Hadamard arbitràries, que no són necessàriament de tipus Sylvester. En general un codi d'aquest tipus no és lineal. Aquests codis es van construir per primera vegada per R. C. Bose i S. S. Shrikhande en 1959.^[4] Si n és la mida de la matriu d'Hadamard, el codi té com a paràmetres (n, 2n, n/2)₂, el que significa que és un codi binari no necessàriament lineal amb 2n paraules de codi, de longitud de bloc n i distància mínima n/2. L'esquema de construcció i descodificació que es descriu s'aplica per valors de n en general però la propietat de linealitat i la identificació amb codis de Reed-Muller requereixen que n sigui una potència de 2 i que la matriu d'Hadamard sigui equivalent a la matriu construïda pel mètode de Sylvester.

El codi d'Hadamard és un codi desxifrable a nivell local, que proporciona una manera de recuperar parts del missatge original amb alta probabilitat, mirant només una petita fracció de la paraula rebuda. Això dona lloc a aplicacions en teoria de la complexitat computacional i en particular en el disseny de proves verificables probabilísticament. Com que la distància relativa del codi d'Hadamard és un 1/2, normalment només es pot esperar recuperar com a màxim una fracció 1/4 de l'error. Usant la llista de descodificació, però, és possible calcular una breu llista de possibles missatges candidats, tant llargs o menors que $(1/2)-\epsilon$ dels bits en la paraula rebuda estiguin corruptes.

En l'accés múltiple per divisió de codi (CDMA) de comunicació, el codi d'Hadamard es coneix com a codi Walsh i s'utilitza per definir els canals de comunicació individuals. És usual en la literatura CDMA per referir-se a paraules de codi com "codis". Cada usuari utilitza una paraula de codi o "codi" per modular el seu senyal. Com que les paraules de codi de Walsh són matemàticament ortogonals, un senyal codificat segons Walsh apareix com soroll aleatori a un terminal mòbil CDMA, llevat que el terminal utilitzi la mateixa paraula de codi que l'utilitzat per a codificar el senyal entrant.

Història

A la bibliografia, el nom que s'utilitza generalment per a aquest codi és codi d'Hadamard. No obstant això, en la pràctica aquests codis correctors d'errors es coneixen com a codis de Walsh-Hadamard.

Hi ha una raó per a això:

Jacques Hadamard no va inventar el codi si mateix, sinó que va definir les matrius d'Hadamard cap a 1893, molt abans que el primer codi de correcció d'errors, el codi de Hamming, que es va desenvolupar en la dècada de 1940.

El codi d'Hadamard es basa en les matrius d'Hadamard, i si bé hi ha moltes matrius d'Hadamard diferents que es podrien utilitzar, normalment s'utilitza només la construcció de matrius d'Hadamard de Sylvester per obtenir les paraules de codi del codi d'Hadamard.

James Joseph Sylvester va desenvolupar la seva construcció de matrius d'Hadamard en 1867, que en realitat és anterior treball d'Hadamard sobre les matrius de Hadamard. D'aquí que el nom de codi d'Hadamard no sigui indiscutible i, de vegades el codi s'anomena codi de Walsh, en honor del matemàtic nord-americà Joseph Leonard Walsh.

Construcció

Si bé tots els codis d'Hadamard es basen en les matrius d'Hadamard, les construccions difereixen a voltes subtilment segons els diferents camps científics, autors i aplicacions. Els enginyers, que fan servir els codis per a la transmissió de dades, els teòrics de la codificació, que analitzen les propietats extremes dels codis, en general volen que la taxa del codi sigui el més alta possible, fins i tot si això significa que la construcció es sigui matemàticament menys elegant. D'altra banda, per a moltes aplicacions de codis d'Hadamard en la informàtica teòrica no és tan important aconseguir la velocitat òptima, i per tant, es prefereixen les construccions més simples de codis d'Hadamard, ja que poden ser analitzats amb més elegància.

Construcció emprant els productes interns

Donat un missatge binari $x\in \{0,1\}^{k}$ de longitud k, el codi d'Hadamard codifica el missatge en una paraula de codi ${\text{Had}}(x)$ utilitzant una funció de codificació ${\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}$ . Aquesta funció utilitza el producte intern $\langle x,y\rangle$ de dos vectors $x,y\in \{0,1\}^{k}$ ,que es defineix com:

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

Llavors, la codificació d'Hadamard de $x$ es defineix com la seqüència de tots els productes interiors amb:

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

Com ja s'ha esmentat, el codi d'Hadamard perforat s'usa en la pràctica, ja que el propi codi Hadamard no és del tot eficient. Això és perquè, si el primer bit de $y$ és zero, $y_{1}=0$ , llavors el producte intern no conté cap tipus d'informació sobre $x_{1}$ , i per tant, és impossible descodificar completament $x$ d'aquestes posicions de la paraula de codi. D'altra banda, quan la paraula de codi es limita a les posicions en què $y_{1}=1$ , encara és possible descodificar $x$ completament. Per tant, té sentit restringir el codi d'Hadamard a aquestes posicions, el que dona lloc a la codificació Hadamard perforada de $x$ això és ${\text{pHad}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{1\}\times \{0,1\}^{k-1}}$ .

Construcció emprant una matriu generadora

El codi Hadamard és un codi lineal, i com tots els codis lineals pot ser generat per una matriu generadora $G$ . Aquesta és una matriu tal manera que ${\text{Had}}(x)=x\cdot G$ es compleix per a tots $x\in \{0,1\}^{k}$ , on el missatge $x$ és un vector fila i el producte vector-matriu s'entén en l'espai vectorial sobre el camp finit $\mathbb {F} _{2}$ . En particular, una forma equivalent d'escriure la definició del producte intern pel codi d'Hadamard és mitjançant l'ús de la matriu generadora on les seves columnes consisteixen en totes les cadenes $y$ de longitud $k$ , és a dir,

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

on $y_{i}\in \{0,1\}^{k}$ és el i-èsim vector binari en ordre lexicogràfic. Per exemple, la matriu generadora pel codi d'Hadamard de dimensió $k=3$ és:

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 matriu $G$ és una $(k\times 2^{k})$ -matriu i dona lloc al fet que l'operador lineal ${\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}$ .

La matriu generadora del codi d'Hadamard punxat s'obté mitjançant la restricció de la matriu a les columnes en les que la primera entrada és 1. Per exemple, la matriu generadora pel codi d'Hadamard punxat de dimensió $G$ és:

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

Llavors ${\text{pHad}}:\{0,1\}^{k}\to \{0,1\}^{2^{k-1}}$ és una aplicació lineal amb ${\text{pHad}}(x)=x\cdot G'$ .

En general $k$ , la matriu generadora del codi d'Hadamard perforada és una matriu de control de paritat del codi de Hamming estès de longitud $2^{k-1}$ i dimensió $2^{k-1}-k$ , el que fa que el codi d'Hadamard perforat el codi dual del codi de Hamming estès. Per tant una manera alternativa per definir el codi d'Hadamard és en termes de la seva matriu de control de paritat: la matriu de control de paritat del codi d'Hadamard és igual a la matriu generadora del codi de Hamming.

Construcció emprant matrius d'Hadamard generals

Els codis d'Hadamard generalitzats s'obtenen a partir d'una matriu d'Hadamard H n-per-n. En particular, les paraules de codi 2n del codi són les files de H i les files de –H. Per obtenir un codi sobre l'alfabet {0,1}, el mapeig –1 ↦ 1, 1 ↦ 0, o, de manera equivalent, x ↦ (1 – x)/2, s'aplica als elements de matriu. Així la distància mínima del codi és n/2 i es dedueix de la propietat definitòria de les matrius d'Hadamard, és a dir, que les seves files són mútuament ortogonals. Això implica que dues files diferents d'una matriu d'Hadamard difereixen en exactament n/2 posicions, i, ja que la cancel·lació d'una fila no afecta l'ortogonalitat, qualsevol fila de H difereix de qualsevol fila de –H en n/2 posicions, excepte quan les files es corresponen, en aquest cas difereixen en n posicions. Per obtenir el codi d'Hadamard perforat anterior amb $n=2^{k-1}$ , la matriu d'Hadamard H triada ha de ser de tipus Sylvester, el que dona lloc a una longitud del missatge de $\log _{2}(2n)=k$ .

Distància

La distància d'un codi és la distància de Hamming mínima entre dues paraules de codi diferents, és a dir, el nombre mínim de posicions en què difereixen dues paraules de codi diferents. Atès que el codi de Walsh-Hadamard és un codi lineal, la distància és igual al pes de Hamming mínima entre totes les paraules de codi diferents de zero. Totes les paraules de codi que no són zero del codi de Walsh-Hadamard tenen un pes de Hamming d'exactament $2^{k-1}$ pel següent raonament. Sigui $x\in \{0,1\}^{k}$ un missatge diferent de zero. Llavors el següent valor és exactament igual a la fracció de posicions en la paraula de codi que són igual a 1:

\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 fet que aquest últim valor sigui 1/2 s'anomena el principi subsuma aleatòria. Per veure que és cert, assumim sense pèrdua de generalitat, que $x_{1}=1$ . Llavors condicionat als valors de $y_{2},\dots ,y_{k}$ , l'esdeveniment és equivalent a $y_{1}\cdot x_{1}=b$ per algun $b\in \{0,1\}$ funció de $x_{2},\dots ,x_{k}$ i $y_{2},\dots ,y_{k}$ . La probabilitat que passi $y_{1}=b$ és exactament 1/2. Per tant, de fet, totes les paraules de codi no zero del codi d'Hadamard tenen un pes Hamming relatiu 1/2, i per tant, la seva distància relativa és 1/2. La distància relativa del codi Hadamard punxat és també 1/2 però ja no té la propietat que cada paraula de codi no nul·la té un pes exactament igual a 1/2, ja que tots els 1 del vector $1^{2^{k-1}}$ són paraula de codi del codi d'Hadamard punxat. Això és degut al fet que el vector $x=10^{k-1}$ codifica a ${\text{pHad}}(10^{k-1})=1^{2^{k-1}}$ . A més, sempre que $x$ no és zero i no el vector $10^{k-1}$ , el principi de la subsuma aleatòria s'aplica de nou, i el pes relatiu de ${\text{Had}}(x)$ és exactament 1/2.

Descodificació local

Un codi localment descodificable és un codi que permet recuperar amb alta probabilitat un sol bit del missatge original amb només mirar una petita part de la paraula rebuda. Un codi és una q consulta localment desxifrable si un bit del missatge $x_{i}$ es pot recuperar mitjançant la comprovació de q bits de la paraula rebuda. Més formalment, un codi, $C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}$ és $(q,\delta \geq 0,\epsilon \geq 0)$ localment descodificable, si existeix un descodificador probabilístic $D:\{0,1\}^{n}\rightarrow \{0,1\}^{k}$ de tal manera que (Nota: $\Delta (x,y)$ representa la distància de Hamming entre els vectors x i y): $\forall x\in \{0,1\}^{k},\forall y\in \{0,1\}^{n}$ , $\Delta (y,C(x))\leq \delta n$ , implica que $Pr[D(y)_{i}=x_{i}]\geq {\frac {1}{2}}+\epsilon ,\forall i\in [k]$

Teorema 1: El codi de Walsh-Hadamard és $(2,\delta ,{\frac {1}{2}}-2\delta )$ localment descodificable per a $0\leq \delta \leq {\frac {1}{4}}$ .

Lema 1: Per a totes les paraules de codi $c$ en un codi de Walsh-Hadamard, $C$ , $c_{i}+c_{j}=c_{i+j}$ , on $c_{i},c_{j}$ representen els bits de $c$ en les posicions $i$ i $j$ respectivament, i $c_{i+j}$ representa el bit de la posició $(i+j)$

Prova del lema 1

Sigui $C(x)=c=(c_{0},\dots ,c_{2^{n}-1})$ la paraula de codi en $C$ que correspon a missatge $x$ .

Sigui $G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\g_{0}&g_{1}&\dots &g_{2^{n}-1}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}$ la matriu generadora de $C$ .

Per definició, $c_{i}=x\cdot g_{i}$ . Així doncs $c_{i}+c_{j}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j})$ . Per la construcció de $G$ , $g_{i}+g_{j}=g_{i+j}$ . Per tant, per substitució, $c_{i}+c_{j}=x\cdot g_{i+j}=c_{i+j}$ .

Prova del teorema 1

Per demostrar el teorema 1 construirem un algoritme de descodificació i demostrarem la seva correcció.

Algorisme

Entrada: Paraula rebuda $y=(y_{0},\dots ,y_{2^{n}-1})$

Per cada $i\in \{1,\dots ,n\}$ :

1. S'escull $j\in \{0,\dots ,2^{n}-1\}$ uniformement a l'atzar

2. Es selecciona $k\in \{0,\dots ,2^{n}-1\}$ de manera que $j+k=e_{i}$ on $j+k$ és el XOR bit a bit de $j$ i $k$ .

3. $x_{i}\gets y_{j}+y_{k}$

Sortida: Missatge $x=(x_{1},\dots ,x_{n})$

Prova de correcció

Per a qualsevol missatge $x=(x_{1},\dots ,x_{n})$ i paraula rebuda $y$ tal que $y$ difereix de $c=C(x)$ en almenys una fracció de bits $\delta$ , $x_{i}$ poden ser descodificats amb una probabilitat d'almenys ${\frac {1}{2}}+(1-2\delta )$ .

Pel lema 1, $c_{j}+c_{k}=c_{j+k}=x\cdot g_{j+k}=x\cdot e_{i}=x_{i}$ . Com $j$ i $k$ són escollits de manera uniforme, la probabilitat que $y_{j}\not =c_{j}$ és com a màxim $\delta$ . Igualment, la probabilitat que $y_{k}\not =c_{k}$ és com a màxim $\delta$ .

Per la desigualtat de Boole, la probabilitat que $y_{j}$ o $y_{k}$ no coincideixin amb els bits corresponents a $c$ és com a màxim $2\delta$ . Si tots dos $y_{j}$ i $y_{k}$ corresponen a $c$ , llavors s'aplica el lema 1, i per tant es calcularà el valor apropiat de $x_{i}$ . Llavors la probabilitat que $x_{i}$ es descodifiqui correctament és almenys $1-2\delta$ . Per tant, $\epsilon ={\frac {1}{2}}-2\delta$ i per $\epsilon$ positiu, $0\leq \delta \leq {\frac {1}{4}}$ .

Per tant, el codi de Walsh-Hadamard es $(2,\delta ,{\frac {1}{2}}-2\delta )$ descodificable localment per a $0\leq \delta \leq {\frac {1}{4}}$ .

Optimalitat

Per a k ≤ 7 els codis lineals d'Hadamard han demostrat ser òptims en el sentit de la mínima distància.^[5]

Referències

↑ Amadei, M; Manzoli, U.; Merani, M. L. On the assignment of Walsh and quasi-orthogonal codes in a multicarrier DS-CDMA system with multiple classes of users. IEEE, 2002, p. 841 - 845 (Global Telecommunications Conference, 2002. GLOBECOM'02. IEEE). ISBN 0-7803-7632-3.
↑ Arora, S.; Barak, B. Computational Complexity: A Modern Approach. Cambridge: Cambridge University Press, 2009. ISBN 978-0-521-42426-4.
↑ «List decoding of binary codes». Guruswami, Venkatesan, 2009. [Consulta: 3 febrer 2016].
↑ Bose, R. C.; Shrikhande, S. S «A note on a result in the theory of code construction». Information and Control, 2, (2), 1959, pàg. 183 - 194. DOI: 10.1016/S0019-9958(59)90376-6.
↑ Jaffe, D. B.; Bouyukliev, I. «Optimal binary linear codes of dimension at most seven». Arxivat de l'original el 8 d'agost 2007. [Consulta: 3 febrer 2016].

[1] Amadei, M; Manzoli, U.; Merani, M. L. On the assignment of Walsh and quasi-orthogonal codes in a multicarrier DS-CDMA system with multiple classes of users. IEEE, 2002, p. 841 - 845 (Global Telecommunications Conference, 2002. GLOBECOM'02. IEEE). ISBN 0-7803-7632-3.

[2] Arora, S.; Barak, B. Computational Complexity: A Modern Approach. Cambridge: Cambridge University Press, 2009. ISBN 978-0-521-42426-4.

[3] «List decoding of binary codes». Guruswami, Venkatesan, 2009. [Consulta: 3 febrer 2016].

[4] Bose, R. C.; Shrikhande, S. S «A note on a result in the theory of code construction». Information and Control, 2, (2), 1959, pàg. 183 - 194. DOI: 10.1016/S0019-9958(59)90376-6.

[5] Jaffe, D. B.; Bouyukliev, I. «Optimal binary linear codes of dimension at most seven». Arxivat de l'original el 8 d'agost 2007. [Consulta: 3 febrer 2016].

[1]

[2]

[3]

[4]

[5]