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 ${\displaystyle (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.