Os códigos de Reed–Muller são códigos corretores de erros usados em aplicações de comunicação sem fio, particularmente em comunicação no espaço profundo. Além disso, o padrão 5G proposto depende dos códigos polares intimamente relacionados para correção de erros no canal de controle. Devido às suas propriedades teóricas e matemáticas favoráveis, os códigos de Reed–Muller também têm sido extensivamente estudados em ciência da computação teórica. Por exemplo, foi demonstrado que eles alcançam assintoticamente a capacidade de Shannon em canais simétricos sem memória.
Os códigos de Reed–Muller generalizam os códigos de Reed–Solomon e o código de Walsh–Hadamard. Os códigos de Reed–Muller são de bloco lineares que são localmente testáveis, localmente decodificáveis e decodificáveis em lista. Essas propriedades os tornam particularmente úteis no projeto de provas verificáveis probabilisticamente.
Os códigos de Reed–Muller tradicionais são códigos binários, o que significa que mensagens e palavras-código são strings binárias. Quando r e m são inteiros com 0 ≤ r ≤ m, o código de Reed–Muller com parâmetros r e m é denotado como RM(r, m). Quando solicitado a codificar uma mensagem consistindo de k bits, onde é válido, o código RM(r, m) produz uma palavra-código consistindo de 2m bits.
Os códigos de Reed–Muller recebem o nome de David E. Muller, que descobriu os códigos em 1954, e Irving S. Reed, que propôs o primeiro algoritmo de decodificação eficiente.
Descrição usando polinômios de baixo grau Os códigos de Reed–Muller podem ser descritos de várias maneiras diferentes (mas em última análise equivalentes). A descrição baseada em polinômios de baixo grau é bastante elegante e particularmente adequada para sua aplicação como códigos localmente testáveis e códigos localmente decodificáveis.Prahladh Harsha et al., Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes), Seção 5.2.1.
Codificador Um código de bloco pode ter uma ou mais funções de codificação que mapeiam mensagens para palavras-código . O código de Reed–Muller tem comprimento da mensagem e comprimento de bloco . Uma maneira de definir uma codificação para este código é baseada na avaliação de polinômios multilineares com m variáveis e grau total no máximo r. Todo polinômio multilinear sobre o corpo finito com dois elementos pode ser escrito como segue:
As variáveis são as variáveis do polinômio, e os valores são os coeficientes do polinômio. Note que há exatamente coeficientes. Com isso em mente, uma mensagem de entrada consiste em valores que são usados como esses coeficientes. Desta forma, cada mensagem dá origem a um polinômio único em m variáveis. Para construir a palavra-código , o codificador avalia o polinômio em todos os pontos , onde o polinômio é tomado com multiplicação e adição mod 2 . Ou seja, a função de codificação é definida por
O fato de que a palavra-código é suficiente para reconstruir unicamente segue da interpolação de Lagrange, que afirma que os coeficientes de um polinômio são unicamente determinados quando pontos de avaliação suficientes são dados. Como e vale para todas as mensagens , a função é um mapa linear. Assim, o código de Reed–Muller é um código linear.
Exemplo Para o código , os parâmetros são os seguintes:
Seja a função de codificação recém-definida. Para codificar a string x = 1 1010 010101 de comprimento 11, o codificador primeiro constrói o polinômio em 4 variáveis:Então ele avalia este polinômio em todos os 16 pontos de avaliação (0101 significa :
Como resultado, C(1 1010 010101) = 1101 1110 0001 0010 vale.
Decodificador Como já mencionado, a interpolação de Lagrange pode ser usada para recuperar eficientemente a mensagem a partir de uma palavra-código. No entanto, um decodificador precisa funcionar mesmo se a palavra-código tiver sido corrompida em algumas posições, ou seja, quando a palavra recebida é diferente de qualquer palavra-código. Neste caso, um procedimento de decodificação local pode ajudar.
O algoritmo de Reed é baseado na seguinte propriedade: você começa a partir da palavra-código, que é uma sequência de pontos de avaliação de um polinômio desconhecido de de grau no máximo que você deseja encontrar. A sequência pode conter qualquer número de erros até inclusive.
Se você considerar um monômio do maior grau em e somar todos os pontos de avaliação do polinômio onde todas as variáveis em têm os valores 0 ou 1, e todas as outras variáveis têm valor 0, você obtém o valor do coeficiente (0 ou 1) de em (Há tais pontos). Isso se deve ao fato de que todos os divisores monomiais inferiores de aparecem um número par de vezes na soma, e apenas aparece uma vez.
Para levar em conta a possibilidade de erros, você também pode notar que pode fixar o valor de outras variáveis para qualquer valor. Então, em vez de fazer a soma apenas uma vez para outras variáveis não em com valor 0, você a faz vezes para cada valoração fixa das outras variáveis. Se não houver erro, todas essas somas devem ser iguais ao valor do coeficiente procurado. O algoritmo consiste aqui em tomar a maioria das respostas como o valor procurado. Se a minoria for maior que o número máximo de erros possível, a etapa de decodificação falha, sabendo que há muitos erros no código de entrada.
Uma vez que um coeficiente é calculado, se for 1, atualize o código para remover o monômio do código de entrada e continue para o próximo monômio, em ordem reversa de seu grau.
Exemplo Vamos considerar o exemplo anterior e começar a partir do código. Com podemos fixar no máximo 1 erro no código. Considere o código de entrada como 1101 1110 0001 0110 (este é o código anterior com um erro).
Sabemos que o grau do polinômio é no máximo , começamos procurando por monômios de grau 2.
começamos procurando pontos de avaliação com . No código isso é: 1101 1110 0001 0110. A primeira soma é 1 (número ímpar de 1s). procuramos pontos de avaliação com . No código isso é: 1101 1110 0001 0110. A segunda soma é 1. procuramos pontos de avaliação com . No código isso é: 1101 1110 0001 0110. A terceira soma é 1. procuramos pontos de avaliação com . No código isso é: 1101 1110 0001 0110. A terceira soma é 0 (número par de 1s). As quatro somas não concordam (então sabemos que há um erro), mas o relatório minoritário não é maior que o número máximo de erros permitido (1), então tomamos a maioria e o coeficiente de é 1.
Removemos do código antes de continuar: código: 1101 1110 0001 0110, valoração de é 0001000100010001, o novo código é 1100 1111 0000 0111
1100 1111 0000 0111. Soma é 0 1100 1111 0000 0111. Soma é 0 1100 1111 0000 0111. Soma é 1 1100 1111 0000 0111. Soma é 0 Um erro detectado, coeficiente é 0, nenhuma mudança no código atual.
1100 1111 0000 0111. Soma é 0 1100 1111 0000 0111. Soma é 0 1100 1111 0000 0111. Soma é 1 1100 1111 0000 0111. Soma é 0 Um erro detectado, coeficiente é 0, nenhuma mudança no código atual.
1100 1111 0000 0111. Soma é 1 1100 1111 0000 0111. Soma é 1 1100 1111 0000 0111. Soma é 1 1100 1111 0000 0111. Soma é 0 Um erro detectado, coeficiente é 1, valoração de é 0000 0011 0000 0011, código atual é agora 1100 1100 0000 0100.
1100 1100 0000 0100. Soma é 1 1100 1100 0000 0100. Soma é 1 1100 1100 0000 0100. Soma é 1 1100 1100 0000 0100. Soma é 0 Um erro detectado, coeficiente é 1, valoração de é 0000 0000 0011 0011, código atual é agora 1100 1100 0011 0111.
1100 1100 0011 0111. Soma é 0 1100 1100 0011 0111. Soma é 1 1100 1100 0011 0111. Soma é 0 1100 1100 0011 0111. Soma é 0 Um erro detectado, coeficiente é 0, nenhuma mudança no código atual. Sabemos agora todos os coeficientes de grau 2 para o polinômio, podemos começar os monômios de grau 1. Observe que para cada próximo grau, há duas vezes mais somas, e cada soma é duas vezes menor.
1100 1100 0011 0111. Soma é 0 1100 1100 0011 0111. Soma é 0 1100 1100 0011 0111. Soma é 0 1100 1100 0011 0111. Soma é 0 1100 1100 0011 0111. Soma é 0 1100 1100 0011 0111. Soma é 0 1100 1100 0011 0111. Soma é 1 1100 1100 0011 0111. Soma é 0 Um erro detectado, coeficiente é 0, nenhuma mudança no código atual.
1100 1100 0011 0111. Soma é 1 1100 1100 0011 0111. Soma é 1 1100 1100 0011 0111. Soma é 1 1100 1100 0011 0111. Soma é 1 1100 1100 0011 0111. Soma é 1 1100 1100 0011 0111. Soma é 1 1100 1100 0011 0111. Soma é 1 1100 1100 0011 0111. Soma é 0 Um erro detectado, coeficiente é 1, valoração de é 0011 0011 0011 0011, código atual é agora 1111 1111 0000 0100.
Então encontraremos 0 para , 1 para e o código atual se torna 1111 1111 1111 1011.
Para o grau 0, temos 16 somas de apenas 1 bit. A minoria ainda tem tamanho 1, e encontramos e a palavra inicial correspondente 1 1010 010101
Generalização para alfabetos maiores via polinômios de baixo grau Usando polinômios de baixo grau sobre um corpo finito de tamanho , é possível estender a definição dos códigos de Reed–Muller para alfabetos de tamanho . Sejam e inteiros positivos, onde deve ser pensado como maior que . Para codificar uma mensagem de largura , a mensagem é novamente interpretada como um polinômio de variáveis de grau total no máximo e com coeficientes em . Tal polinômio tem de fato coeficientes. A codificação Reed–Muller de é a lista de todas as avaliações de sobre todos os . Assim, o comprimento de bloco é .
Descrição usando uma matriz geradora Uma matriz geradora para um código de Reed–Muller de comprimento pode ser construída como segue. Vamos escrever o conjunto de todos os vetores binários de m dimensões como:
Definimos no espaço N-dimensional os vetores indicadores
em subconjuntos por:
juntamente com, também em , a operação binária
referida como produto cunha (não confundir com o produto cunha definido na álgebra exterior). Aqui, e são pontos em (vetores binários N-dimensionais), e a operação é a multiplicação usual no corpo .
é um espaço vetorial m-dimensional sobre o corpo , então é possível escrever
Definimos no espaço N-dimensional os seguintes vetores com comprimento e
onde 1 ≤ i ≤ m e os Hi são hiperplanos em (com dimensão ):
A matriz geradora O código de Reed–Muller de ordem r e comprimento N = 2m é o código gerado por v0 e pelos produtos cunha de até r dos vi, (onde por convenção um produto cunha de menos de um vetor é a identidade para a operação). Em outras palavras, podemos construir uma matriz geradora para o código , usando vetores e suas permutações de produto cunha até r de cada vez , como as linhas da matriz geradora, onde .
Exemplo 1 Seja m = 3. Então N = 8, e
e
O código RM(1,3) é gerado pelo conjunto
ou mais explicitamente pelas linhas da matriz:
Exemplo 2 O código RM(2,3) é gerado pelo conjunto:
ou mais explicitamente pelas linhas da matriz:
Propriedades As seguintes propriedades são válidas:
O conjunto de todos os produtos cunha possíveis de até m dos vi forma uma base para . O código RM (r, m) tem rank
onde '' denota o produto barra de dois códigos. tem peso de Hamming mínimo 2m − r.
A distribuição completa dos pesos das palavras-código é mais complicada do que a fórmula da distância mínima. Tadao Kasami e Nobuki Tokura estudaram a estrutura de pesos dos códigos de Reed–Muller, incluindo palavras-código de baixo peso além do peso mínimo.
Prova
Decodificação de códigos RM