Código Reed-Muller
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 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.
Codificador
Um código de bloco pode ter uma ou mais funções de codificação C : { 0 , 1 } k → { 0 , 1 } n {\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}} que mapeiam mensagens x ∈ { 0 , 1 } k {\textstyle x\in \{0,1\}^{k}} para palavras-código C ( x ) ∈ { 0 , 1 } n {\textstyle C(x)\in \{0,1\}^{n}} . O código de Reed–Muller RM(r, m) tem comprimento da mensagem k = ∑ i = 0 r ( m i ) {\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}} e comprimento de bloco n = 2 m {\displaystyle \textstyle n=2^{m}} . 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: p c ( Z 1 , … , Z m ) = ∑ S ⊆ { 1 , … , m } | S | ≤ r c S ⋅ ∏ i ∈ S Z i . {\displaystyle p_{c}(Z_{1},\dots ,Z_{m})=\sum _{\underset {|S|\leq r}{S\subseteq \{1,\dots ,m\}}}c_{S}\cdot \prod _{i\in S}Z_{i}\,.} As variáveis Z 1 , … , Z m {\textstyle Z_{1},\dots ,Z_{m}} são as variáveis do polinômio, e os valores c S ∈ { 0 , 1 } {\textstyle c_{S}\in \{0,1\}} são os coeficientes do polinômio. Note que há exatamente k = ∑ i = 0 r ( m i ) {\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}} coeficientes. Com isso em mente, uma mensagem de entrada consiste em k {\textstyle k} valores x ∈ { 0 , 1 } k {\textstyle x\in \{0,1\}^{k}} que são usados como esses coeficientes. Desta forma, cada mensagem x {\textstyle x} dá origem a um polinômio único p x {\textstyle p_{x}} em m variáveis. Para construir a palavra-código C ( x ) {\textstyle C(x)} , o codificador avalia o polinômio p x {\textstyle p_{x}} em todos os pontos Z = ( Z 1 , … , Z m ) ∈ { 0 , 1 } m {\textstyle Z=(Z_{1},\ldots ,Z_{m})\in \{0,1\}^{m}} , onde o polinômio é tomado com multiplicação e adição mod 2 ( p x ( Z ) mod 2 ) ∈ { 0 , 1 } {\textstyle (p_{x}(Z){\bmod {2}})\in \{0,1\}} . Ou seja, a função de codificação é definida por C ( x ) = ( p x ( Z ) mod 2 ) Z ∈ { 0 , 1 } m . {\displaystyle C(x)=\left(p_{x}(Z){\bmod {2}}\right)_{Z\in \{0,1\}^{m}}\,.}
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 p x {\textstyle p_{x}} de F 2 [ X 1 , X 2 , . . . , X m ] {\textstyle {\mathbb {F} }_{2}[X_{1},X_{2},...,X_{m}]} de grau no máximo r {\textstyle r} que você deseja encontrar. A sequência pode conter qualquer número de erros até 2 m − r − 1 − 1 {\textstyle 2^{m-r-1}-1} inclusive.
Generalização para alfabetos maiores via polinômios de baixo grau
Usando polinômios de baixo grau sobre um corpo finito F {\displaystyle \mathbb {F} } de tamanho q {\displaystyle q} , é possível estender a definição dos códigos de Reed–Muller para alfabetos de tamanho q {\displaystyle q} . Sejam m {\displaystyle m} e d {\displaystyle d} inteiros positivos, onde m {\displaystyle m} deve ser pensado como maior que d {\displaystyle d} . Para codificar uma mensagem x ∈ F k {\textstyle x\in \mathbb {F} ^{k}} de largura k = ( m + d m ) {\displaystyle k=\textstyle {\binom {m+d}{m}}} , a mensagem é novamente interpretada como um polinômio p x {\displaystyle p_{x}} de m {\displaystyle m} variáveis de grau total no máximo d {\displaystyle d} e com coeficientes em F {\displaystyle \mathbb {F} } . Tal polinômio tem de fato ( m + d m ) {\displaystyle \textstyle {\binom {m+d}{m}}} coeficientes. A codificação Reed–Muller de x {\displaystyle x} é a lista de todas as avaliações de p x ( a ) {\displaystyle p_{x}(a)} sobre todos os a ∈ F m {\displaystyle a\in \mathbb {F} ^{m}} . Assim, o comprimento de bloco é n = q m {\displaystyle n=q^{m}} .
Uma matriz geradora para um código de Reed–Muller RM(r, m) de comprimento N = 2m 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 F 2 N {\displaystyle \mathbb {F} _{2}^{N}} os vetores indicadores em subconjuntos A ⊂ X {\displaystyle A\subset X} por: juntamente com, também em F 2 N {\displaystyle \mathbb {F} _{2}^{N}} , a operação binária referida como produto cunha (não confundir com o produto cunha definido na álgebra exterior). Aqui, w = ( w 1 , w 2 , … , w N ) {\displaystyle w=(w_{1},w_{2},\ldots ,w_{N})} e z = ( z 1 , z 2 , … , z N ) {\displaystyle z=(z_{1},z_{2},\ldots ,z_{N})} são pontos em F 2 N {\displaystyle \mathbb {F} _{2}^{N}} (vetores binários N-dimensionais), e a operação ⋅ {\displaystyle \cdot } é a multiplicação usual no corpo F 2 {\displaystyle \mathbb {F} _{2}} . F 2 m {\displaystyle \mathbb {F} _{2}^{m}} é um espaço vetorial m-dimensional sobre o corpo F 2 {\displaystyle \mathbb {F} _{2}} , então é possível escrever
A matriz geradora
O código de Reed–Muller RM(r, m) de ordem r e comprimento N = 2m é o código gerado por v0 e pelos produtos cunha de até r dos vi, 1 ≤ i ≤ m (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 RM(r, m), usando vetores e suas permutações de produto cunha até r de cada vez v 0 , v 1 , … , v n , … , ( v i 1 ∧ v i 2 ) , … ( v i 1 ∧ v i 2 … ∧ v i r ) {\displaystyle {v_{0},v_{1},\ldots ,v_{n},\ldots ,(v_{i_{1}}\wedge v_{i_{2}}),\ldots (v_{i_{1}}\wedge v_{i_{2}}\ldots \wedge v_{i_{r}})}} , como as linhas da matriz geradora, onde 1 ≤ ik ≤ m.
Exemplo 1
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
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. tais vetores e F 2 N {\displaystyle \mathbb {F} _{2}^{N}} tem dimensão N, então é suficiente verificar que os N vetores geram; equivalentemente, é suficiente verificar que R M ( m , m ) = F 2 N {\displaystyle \mathrm {RM} (m,m)=\mathbb {F} _{2}^{N}} . Seja x um vetor binário de comprimento m, um elemento de X. Seja (x)i denote o i-ésimo elemento de x. Defina Então I { x } = y 1 ∧ ⋯ ∧ y m {\displaystyle \mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}}
Decodificação de códigos RM
Códigos RM(r, m) podem ser decodificados usando decodificação por lógica majoritária. A ideia básica da decodificação por lógica majoritária é construir várias somas de verificação para cada elemento da palavra-código recebida. Como cada uma das diferentes somas de verificação deve ter o mesmo valor (ou seja, o valor do elemento da palavra da mensagem), podemos usar uma lógica majoritária para decifrar o valor do elemento da palavra da mensagem. Uma vez que cada ordem do polinômio é decodificada, a palavra recebida é modificada adequadamente, removendo as palavras-código correspondentes ponderadas pelas contribuições da mensagem decodificada, até o estágio atual. Assim, para um código RM de ordem r, temos que decodificar iterativamente r+1 vezes antes de chegarmos à palavra-código final recebida. Além disso, os valores dos bits da mensagem são calculados através deste esquema; finalmente podemos calcular a palavra-código multiplicando a palavra da mensagem (recém-decodificada) pela matriz geradora.
Um código Reed–Muller RM(r,m) existe para quaisquer inteiros m ≥ 0 {\displaystyle m\geq 0} e 0 ≤ r ≤ m {\displaystyle 0\leq r\leq m} . RM(m, m) é definido como o código universo ( 2 m , 2 m , 1 {\displaystyle 2^{m},2^{m},1} ). RM(−1,m) é definido como o código trivial ( 2 m , 0 , ∞ {\displaystyle 2^{m},0,\infty } ). Os códigos RM restantes podem ser construídos a partir desses códigos elementares usando a construção de duplicação de comprimento A partir desta construção, RM(r,m) é um código de bloco linear binário (n, k, d) com comprimento n = 2m, dimensão k ( r , m ) = k ( r , m − 1 ) + k ( r − 1 , m − 1 ) {\displaystyle k(r,m)=k(r,m-1)+k(r-1,m-1)} e distância mínima d = 2 m − r {\displaystyle d=2^{m-r}} para r ≥ 0 {\displaystyle r\geq 0} . O código dual de RM(r,m) é RM(m-r-1,m). Isso mostra que códigos de repetição e SPC são duais, códigos biorthogonais e de Hamming estendidos são duais e que códigos com k = n/2 são autoduais.
Tabela de todos os códigos RM(r,m) para m≤5
Todos os códigos RM(r, m) com 0 ≤ m ≤ 5 {\displaystyle 0\leq m\leq 5} e tamanho de alfabeto 2 são exibidos aqui, anotados com a notação padrão [n,k,d] da teoria da codificação para códigos de bloco. O código RM(r, m) é um [ 2 m , k , 2 m − r ] 2 {\displaystyle \textstyle [2^{m},k,2^{m-r}]_{2}} -código, ou seja, é um código linear sobre um alfabeto binário, tem comprimento de bloco 2 m {\displaystyle \textstyle 2^{m}} , comprimento da mensagem (ou dimensão) k, e distância mínima 2 m − r {\displaystyle \textstyle 2^{m-r}} .
