Código de Hadamard
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.
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. 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.
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 x ∈ { 0 , 1 } k {\displaystyle x\in \{0,1\}^{k}} de comprimento k {\displaystyle k} , o código de Hadamard codifica a mensagem em uma palavra-código Had ( x ) {\displaystyle {\text{Had}}(x)} usando uma função de codificação Had : { 0 , 1 } k → { 0 , 1 } 2 k . {\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}.} Esta função faz uso do produto interno ⟨ x , y ⟩ {\displaystyle \langle x,y\rangle } de dois vetores x , y ∈ { 0 , 1 } k {\displaystyle x,y\in \{0,1\}^{k}} , que é definido como segue: Então, a codificação de Hadamard de x {\displaystyle x} é definida como a sequência de todos os produtos internos com x {\displaystyle x} :
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 G {\displaystyle G} . Esta é uma matriz tal que Had ( x ) = x ⋅ G {\displaystyle {\text{Had}}(x)=x\cdot G} vale para todo x ∈ { 0 , 1 } k {\displaystyle x\in \{0,1\}^{k}} , onde a mensagem x {\displaystyle x} é vista como um vetor linha e o produto vetor-matriz é entendido no espaço vetorial sobre o corpo finito F 2 {\displaystyle \mathbb {F} _{2}} . 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 y {\displaystyle y} de comprimento k {\displaystyle k} , ou seja,
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.
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 2 k − 1 {\displaystyle 2^{k-1}} pelo seguinte argumento. Seja x ∈ { 0 , 1 } k {\displaystyle x\in \{0,1\}^{k}} 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 1 / 2 {\displaystyle 1/2} é chamado de princípio da subsoma aleatória. Para ver que é verdade, assuma sem perda de generalidade que x 1 = 1 {\displaystyle x_{1}=1} . Então, quando condicionado aos valores de y 2 , … , y k {\displaystyle y_{2},\dots ,y_{k}} , o evento é equivalente a y 1 ⋅ x 1 = b {\displaystyle y_{1}\cdot x_{1}=b} para algum b ∈ { 0 , 1 } {\displaystyle b\in \{0,1\}} dependendo de x 2 , … , x k {\displaystyle x_{2},\dots ,x_{k}} e y 2 , … , y k {\displaystyle y_{2},\dots ,y_{k}} . A probabilidade de que y 1 = b {\displaystyle y_{1}=b} aconteça é exatamente 1 / 2 {\displaystyle 1/2} . Assim, de fato, todas as palavras-código não nulas do código de Hadamard têm peso de Hamming relativo 1 / 2 {\displaystyle 1/2} e, portanto, sua distância relativa é 1 / 2 {\displaystyle 1/2} .
Um código localmente decodificável é um código que permite que um único bit da mensagem original seja recuperado com alta probabilidade olhando apenas para uma pequena porção da palavra recebida. Um código é q {\displaystyle q} -consulta localmente decodificável se um bit de mensagem, x i {\displaystyle x_{i}} , pode ser recuperado verificando q {\displaystyle q} bits da palavra recebida. Mais formalmente, um código, C : { 0 , 1 } k → { 0 , 1 } n {\displaystyle C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}} , é ( q , δ ≥ 0 , ϵ ≥ 0 ) {\displaystyle (q,\delta \geq 0,\epsilon \geq 0)} -localmente decodificável, se existe um decodificador probabilístico, D : { 0 , 1 } n → { 0 , 1 } k {\displaystyle D:\{0,1\}^{n}\rightarrow \{0,1\}^{k}} , tal que (Nota: Δ ( x , y ) {\displaystyle \Delta (x,y)} representa a distância de Hamming entre os vetores x {\displaystyle x} e y {\displaystyle y} ): ∀ x ∈ { 0 , 1 } k , ∀ y ∈ { 0 , 1 } n {\displaystyle \forall x\in \{0,1\}^{k},\forall y\in \{0,1\}^{n}} , Δ ( y , C ( x ) ) ≤ δ n {\displaystyle \Delta (y,C(x))\leq \delta n} implica que P r [ D ( y ) i = x i ] ≥ 1 2 + ϵ , ∀ i ∈ [ k ] {\displaystyle Pr[D(y)_{i}=x_{i}]\geq {\frac {1}{2}}+\epsilon ,\forall i\in [k]}
Prova do lema 1
Seja C ( x ) = c = ( c 0 , … , c 2 n − 1 ) {\displaystyle C(x)=c=(c_{0},\dots ,c_{2^{n}-1})} a palavra-código em C {\displaystyle C} correspondente à mensagem x {\displaystyle x} . Seja G = ( ↑ ↑ ↑ g 0 g 1 … g 2 n − 1 ↓ ↓ ↓ ) {\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\g_{0}&g_{1}&\dots &g_{2^{n}-1}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}} a matriz geradora de C {\displaystyle C} . Por definição, c i = x ⋅ g i {\displaystyle c_{i}=x\cdot g_{i}} . Disto, c i + c j = x ⋅ g i + x ⋅ g j = x ⋅ ( g i + g j ) {\displaystyle c_{i}+c_{j}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j})} . Pela construção de G {\displaystyle G} , g i + g j = g i + j {\displaystyle g_{i}+g_{j}=g_{i+j}} . Portanto, por substituição, c i + c j = x ⋅ g i + j = c i + j {\displaystyle c_{i}+c_{j}=x\cdot g_{i+j}=c_{i+j}} .
Prova do teorema 1
Para provar o teorema 1, construiremos um algoritmo de decodificação e provaremos sua correção. Entrada: Palavra recebida y = ( y 0 , … , y 2 n − 1 ) {\displaystyle y=(y_{0},\dots ,y_{2^{n}-1})} Para cada i ∈ { 1 , … , n } {\displaystyle i\in \{1,\dots ,n\}} : Saída: Mensagem x = ( x 1 , … , x n ) {\displaystyle x=(x_{1},\dots ,x_{n})} Para qualquer mensagem, x {\displaystyle x} , e palavra recebida y {\displaystyle y} tal que y {\displaystyle y} difere de c = C ( x ) {\displaystyle c=C(x)} em no máximo δ {\displaystyle \delta } fração dos bits, x i {\displaystyle x_{i}} pode ser decodificado com probabilidade de pelo menos 1 2 + ( 1 2 − 2 δ ) {\displaystyle {\frac {1}{2}}+({\frac {1}{2}}-2\delta )} .
Para k ≤ 7, os códigos de Hadamard lineares foram provados ótimos no sentido de distância mínima.
