Vés al contingut

Codi d'Hadamard

De la Viquipèdia, l'enciclopèdia lliure
Matriu del codi d'Hadamard (32, 6, 16) pel codi de Reed–Muller (1, 5) de la sonda Mariner 9 de la NASA

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 2k. És l'únic en què cada paraula de codi diferent de zero té un pes de Hamming exactament 2k/2, el que implica que la distància del codi és també 2k/2. En la notació estàndard de teoria de la codificació per a codis de bloc, el codi d'Hadamard és un codi [2k, k, 2k/2]₂, és a dir, és un codi lineal sobre un alfabet binari, té longitud de bloc 2k, longitud del missatge (o dimensió) k, i distància mínima 2k/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 [2k – 1, k, 2k – 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 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

[modifica]

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ó

[modifica]

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

[modifica]

Donat un missatge binari de longitud k, el codi d'Hadamard codifica el missatge en una paraula de codi utilitzant una funció de codificació . Aquesta funció utilitza el producte intern de dos vectors ,que es defineix com:

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

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 és zero, , llavors el producte intern no conté cap tipus d'informació sobre , i per tant, és impossible descodificar completament d'aquestes posicions de la paraula de codi. D'altra banda, quan la paraula de codi es limita a les posicions en què , encara és possible descodificar completament. Per tant, té sentit restringir el codi d'Hadamard a aquestes posicions, el que dona lloc a la codificació Hadamard perforada de això és .

Construcció emprant una matriu generadora

[modifica]

El codi Hadamard és un codi lineal, i com tots els codis lineals pot ser generat per una matriu generadora . Aquesta és una matriu tal manera que es compleix per a tots , on el missatge és un vector fila i el producte vector-matriu s'entén en l'espai vectorial sobre el camp finit . 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 de longitud , és a dir,

on és el i-èsim vector binari en ordre lexicogràfic. Per exemple, la matriu generadora pel codi d'Hadamard de dimensió és:

La matriu és una -matriu i dona lloc al fet que l'operador lineal .

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ó és:

Llavors és una aplicació lineal amb .

En general , la matriu generadora del codi d'Hadamard perforada és una matriu de control de paritat del codi de Hamming estès de longitud i dimensió , 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

[modifica]

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 , la matriu d'Hadamard H triada ha de ser de tipus Sylvester, el que dona lloc a una longitud del missatge de .

Distància

[modifica]

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 pel següent raonament. Sigui 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:

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 . Llavors condicionat als valors de , l'esdeveniment és equivalent a per algun funció de i . La probabilitat que passi é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 són paraula de codi del codi d'Hadamard punxat. Això és degut al fet que el vector codifica a . A més, sempre que no és zero i no el vector , el principi de la subsuma aleatòria s'aplica de nou, i el pes relatiu de és exactament 1/2.

Descodificació local

[modifica]
Operacions XOR
En blanc bit = 0
En vermell bit = 1

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 es pot recuperar mitjançant la comprovació de q bits de la paraula rebuda. Més formalment, un codi, és localment descodificable, si existeix un descodificador probabilístic de tal manera que (Nota: representa la distància de Hamming entre els vectors x i y): , , implica que

Teorema 1: El codi de Walsh-Hadamard és localment descodificable per a .

Lema 1: Per a totes les paraules de codi en un codi de Walsh-Hadamard, , , on representen els bits de en les posicions i respectivament, i representa el bit de la posició

Prova del lema 1

[modifica]

Sigui la paraula de codi en que correspon a missatge .

Sigui la matriu generadora de .

Per definició, . Així doncs . Per la construcció de , . Per tant, per substitució, .

Prova del teorema 1

[modifica]

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

Algorisme

[modifica]

Entrada: Paraula rebuda

Per cada  :

1. S'escull uniformement a l'atzar

2. Es selecciona de manera que on és el XOR bit a bit de i .

3.

Sortida: Missatge

Prova de correcció

[modifica]

Per a qualsevol missatge i paraula rebuda tal que difereix de en almenys una fracció de bits , poden ser descodificats amb una probabilitat d'almenys .

Pel lema 1, . Com i són escollits de manera uniforme, la probabilitat que és com a màxim . Igualment, la probabilitat que és com a màxim .

Per la desigualtat de Boole, la probabilitat que o no coincideixin amb els bits corresponents a és com a màxim . Si tots dos i corresponen a , llavors s'aplica el lema 1, i per tant es calcularà el valor apropiat de . Llavors la probabilitat que es descodifiqui correctament és almenys . Per tant, i per positiu, .

Per tant, el codi de Walsh-Hadamard es descodificable localment per a .

Optimalitat

[modifica]

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

[modifica]
  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].