thumb|250 px|Matriz do código de Hadamard aumentado [32, 6, 16] para o código de Reed-Muller (1, 5) da sonda espacial da NASA Mariner 9 thumb|250px|Operações XORAqui os campos brancos representam 0e os campos vermelhos representam 1 O código de Hadamard é um código corretor de erros nomeado em homenagem ao matemático francês Jacques Hadamard, usado para detecção e correção de erros ao transmitir mensagens por canais muito ruidosos ou não confiáveis. Em 1971, o código foi usado para transmitir fotos de Marte de volta à Terra a partir da sonda espacial da NASA Mariner 9. Devido às suas propriedades matemáticas únicas, o código de Hadamard não é apenas usado por engenheiros, mas também intensamente estudado em teoria da codificação, matemática e ciência da computação teórica. O código de Hadamard também é conhecido pelos nomes código de Walsh, família de Walsh, e código de Walsh–Hadamard em reconhecimento ao matemático americano Joseph Leonard Walsh.

A especificação matemática do código de Hadamard é bastante complexa e é descrita nas seções Construções. É um exemplo de um código linear de comprimento sobre um alfabeto binário. Infelizmente, este termo é um tanto ambíguo, pois algumas referências assumem um comprimento de mensagem enquanto outras assumem um comprimento de mensagem de . Neste artigo, o primeiro caso é chamado de código de Hadamard enquanto o segundo é chamado de código de Hadamard aumentado.

O código de Hadamard é único, pois cada palavra-código não nula tem um peso de Hamming de exatamente , o que implica que a distância do código também é . Na notação padrão da teoria da codificação para códigos de bloco, o código de Hadamard é um -código, ou seja, é um código linear sobre um alfabeto binário, tem comprimento de bloco , comprimento de mensagem (ou dimensão) , e distância mínima . O comprimento de bloco é muito grande comparado ao comprimento da mensagem, mas por outro lado, os erros podem ser corrigidos mesmo em condições extremamente ruidosas.

O código de Hadamard aumentado é uma versão ligeiramente melhorada do código de Hadamard; é um -código e, portanto, tem uma taxa ligeiramente melhor, mantendo a distância relativa de , sendo assim preferido em aplicações práticas. Na teoria das comunicações, isso é simplesmente chamado de código de Hadamard e é o mesmo que o código de Reed-Muller de primeira ordem sobre o alfabeto binário.

Normalmente, os códigos de Hadamard são baseados na construção de Sylvester de matrizes de Hadamard, mas o termo "código de Hadamard" também é usado para se referir a códigos construídos a partir de matrizes de Hadamard arbitrárias, que não são necessariamente do tipo Sylvester. Em geral, tal código não é linear. Tais códigos foram construídos pela primeira vez por Raj Chandra Bose e Sharadchandra Shankar Shrikhande em 1959. Se n é o tamanho da matriz de Hadamard, o código tem parâmetros , significando que é um código binário (não necessariamente linear) com 2n palavras-código de comprimento de bloco n e distância mínima n/2. A construção e o esquema de decodificação descritos abaixo se aplicam para n geral, mas a propriedade de linearidade e a identificação com códigos de Reed-Muller exigem que n seja uma potência de 2 e que a matriz de Hadamard seja equivalente à matriz construída pelo método de Sylvester.

O código de Hadamard é um código localmente decodificável, que fornece uma maneira de recuperar partes da mensagem original com alta probabilidade, enquanto olha apenas para uma pequena fração da palavra recebida. Isso dá origem a aplicações em teoria da complexidade computacional e particularmente no projeto de provas verificáveis probabilisticamente. Como a distância relativa do código de Hadamard é 1/2, normalmente só se pode esperar recuperar de no máximo uma fração de 1/4 de erro. Usando decodificação em lista, no entanto, é possível calcular uma lista curta de possíveis mensagens candidatas, desde que menos de dos bits na palavra recebida tenham sido corrompidos.

Na comunicação de acesso múltiplo por divisão de código (CDMA), o código de Hadamard é referido como código de Walsh e é usado para definir canais de comunicação individuais. É comum na literatura de CDMA referir-se às palavras-código como "códigos". Cada usuário usará uma palavra-código diferente, ou "código", para modular seu sinal. Como as palavras-código de Walsh são matematicamente ortogonais, um sinal codificado por Walsh aparece como ruído aleatório para um terminal móvel com capacidade CDMA, a menos que esse terminal use a mesma palavra-código que a usada para codificar o sinal de entrada.

História Código de Hadamard é o nome mais comumente usado para este código na literatura. No entanto, no uso moderno, esses códigos corretores de erros são chamados de códigos de Walsh–Hadamard.

Há uma razão para isso:

Jacques Hadamard não inventou o código em si, mas definiu matrizes de Hadamard por volta de 1893, muito antes do primeiro código corretor de erros, o código de Hamming, ter sido desenvolvido na década de 1940.

O código de Hadamard é baseado em matrizes de Hadamard, e embora existam muitas matrizes de Hadamard diferentes que poderiam ser usadas aqui, normalmente apenas a construção de Sylvester de matrizes de Hadamard é usada para obter as palavras-código do código de Hadamard.

James Joseph Sylvester desenvolveu sua construção de matrizes de Hadamard em 1867, que na verdade antecede o trabalho de Hadamard sobre matrizes de Hadamard. Portanto, o nome código de Hadamard é disputado e às vezes o código é chamado de código de Walsh, homenageando o matemático americano Joseph Leonard Walsh.

Um código de Hadamard aumentado foi usado durante a missão Mariner 9 de 1971 para corrigir erros de transmissão de imagens. Os valores binários usados durante esta missão tinham 6 bits de comprimento, representando 64 valores de escala de cinza.

Devido a limitações da qualidade do alinhamento do transmissor na época (devido a problemas no circuito de rastreamento Doppler), o comprimento máximo útil dos dados era de cerca de 30 bits. Em vez de usar um código de repetição, foi usado um código de Hadamard [32, 6, 16].

Erros de até 7 bits por palavra de 32 bits podiam ser corrigidos usando este esquema. Comparado a um código de repetição de 5 repetições, as propriedades de correção de erros deste código de Hadamard são muito melhores, embora sua taxa seja comparável. O algoritmo de decodificação eficiente foi um fator importante na decisão de usar este código.

O circuito usado foi chamado de "Green Machine". Ele empregava a transformada rápida de Fourier, que pode aumentar a velocidade de decodificação por um fator de três. Desde a década de 1990, o uso deste código por programas espaciais praticamente cessou, e a NASA Deep Space Network não suporta este esquema de correção de erros para suas antenas com mais de 26 m.

Construções Embora todos os códigos de Hadamard sejam baseados em matrizes de Hadamard, as construções diferem em aspectos sutis para diferentes campos científicos, autores e usos. Engenheiros, que usam os códigos para transmissão de dados, e teóricos da codificação, que analisam propriedades extremas de códigos, normalmente desejam que a taxa do código seja a mais alta possível, mesmo que isso signifique que a construção se torne matematicamente um pouco menos elegante.

Por outro lado, para muitas aplicações de códigos de Hadamard em ciência da computação teórica, não é tão importante alcançar a taxa ótima e, portanto, construções mais simples de códigos de Hadamard são preferidas, pois podem ser analisadas de forma mais elegante.

Construção usando produtos internos Quando dada uma mensagem binária de comprimento , o código de Hadamard codifica a mensagem em uma palavra-código usando uma função de codificação Esta função faz uso do produto interno de dois vetores , que é definido como segue:

Então, a codificação de Hadamard de é definida como a sequência de todos os produtos internos com :

Como mencionado acima, o código de Hadamard aumentado é usado na prática, pois o próprio código de Hadamard é um tanto desperdiçador. Isso ocorre porque, se o primeiro bit de é zero, , então o produto interno não contém nenhuma informação sobre e, portanto, é impossível decodificar completamente apenas a partir dessas posições da palavra-código. Por outro lado, quando a palavra-código é restrita às posições onde , ainda é possível decodificar completamente . Portanto, faz sentido restringir o código de Hadamard a essas posições, o que dá origem à codificação de Hadamard aumentada de ; ou seja, .

Construção usando uma matriz geradora O código de Hadamard é um código linear, e todos os códigos lineares podem ser gerados por uma matriz geradora . Esta é uma matriz tal que vale para todo , onde a mensagem é vista como um vetor linha e o produto vetor-matriz é entendido no espaço vetorial sobre o corpo finito . Em particular, uma maneira equivalente de escrever a definição do produto interno para o código de Hadamard surge usando a matriz geradora cujas colunas consistem em todas as strings de comprimento , ou seja,

onde é o -ésimo vetor binário em ordem lexicográfica. Por exemplo, a matriz geradora para o código de Hadamard de dimensão é:

A matriz é uma -matriz e dá origem ao operador linear .

A matriz geradora do código de Hadamard aumentado é obtida restringindo a matriz às colunas cuja primeira entrada é um. Por exemplo, a matriz geradora para o código de Hadamard aumentado de dimensão é:

Então é um mapeamento linear com .

Para geral, a matriz geradora do código de Hadamard aumentado é uma matriz de verificação de paridade para o código de Hamming estendido de comprimento e dimensão , o que torna o código de Hadamard aumentado o código dual do código de Hamming estendido. Portanto, uma maneira alternativa de definir o código de Hadamard é em termos de sua matriz de verificação de paridade: a matriz de verificação de paridade do código de Hadamard é igual à matriz geradora do código de Hamming.

Construção usando matrizes de Hadamard gerais Códigos de Hadamard são obtidos a partir de uma matriz de Hadamard H n-por-n. Em particular, as 2n palavras-código do código são as linhas de H e as linhas de −H. Para obter um código sobre o alfabeto {0,1}, o mapeamento −1 ↦ 1, 1 ↦ 0, ou, equivalentemente, x ↦ (1 − x)/2, é aplicado aos elementos da matriz. O fato de que a distância mínima do código é n/2 segue da propriedade definidora das matrizes de Hadamard, nomeadamente que suas linhas são mutuamente ortogonais. Isso implica que duas linhas distintas de uma matriz de Hadamard diferem em exatamente n/2 posições, e, como a negação de uma linha não afeta a ortogonalidade, qualquer linha de H difere de qualquer linha de −H em n/2 posições também, exceto quando as linhas correspondem, caso em que diferem em n posições.

Para obter o código de Hadamard aumentado acima com , a matriz de Hadamard H escolhida tem que ser do tipo Sylvester, o que dá origem a um comprimento de mensagem de .

Distância A distância de um código é a distância de Hamming mínima entre quaisquer duas palavras-código distintas, ou seja, o número mínimo de posições em que duas palavras-código distintas diferem. Como o código de Walsh–Hadamard é um código linear, a distância é igual ao peso de Hamming mínimo entre todas as suas palavras-código não nulas. Todas as palavras-código não nulas do código de Walsh–Hadamard têm um peso de Hamming de exatamente pelo seguinte argumento.

Seja uma mensagem não nula. Então o seguinte valor é exatamente igual à fração de posições na palavra-código que são iguais a um:

O fato de que o último valor é exatamente é chamado de princípio da subsoma aleatória. Para ver que é verdade, assuma sem perda de generalidade que .