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 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

k =

∑

i = 0

(

m i

)

{\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}

é 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.

Codificador Um código de bloco pode ter uma ou mais funções de codificação

C : { 0 , 1

}

→ { 0 , 1

}

{\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}

que mapeiam mensagens

x ∈ { 0 , 1

}

{\textstyle x\in \{0,1\}^{k}}

para palavras-código

C ( x ) ∈ { 0 , 1

}

{\textstyle C(x)\in \{0,1\}^{n}}

. O código de Reed–Muller RM(r, m) tem comprimento da mensagem

k =

∑

i = 0

(

m i

)

{\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}

e comprimento de bloco

n =

{\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:

(

, ... ,

) =

∑

S ⊆ { 1 , ... , m }

≤ r

⋅

∏

i ∈ S

{\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

, ... ,

{\textstyle Z_{1},\dots ,Z_{m}}

são as variáveis do polinômio, e os valores

∈ { 0 , 1 }

{\textstyle c_{S}\in \{0,1\}}

são os coeficientes do polinômio. Note que há exatamente

k =

∑

i = 0

(

m i

)

{\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}

coeficientes. Com isso em mente, uma mensagem de entrada consiste em

{\textstyle k}

valores

x ∈ { 0 , 1

}

{\textstyle x\in \{0,1\}^{k}}

que são usados como esses coeficientes. Desta forma, cada mensagem

{\textstyle x}

dá origem a um polinômio único

{\textstyle p_{x}}

em m variáveis. Para construir a palavra-código

C ( x )

{\textstyle C(x)}

, o codificador avalia o polinômio

{\textstyle p_{x}}

em todos os pontos

Z = (

, ... ,

) ∈ { 0 , 1

}

{\textstyle Z=(Z_{1},\ldots ,Z_{m})\in \{0,1\}^{m}}

, onde o polinômio é tomado com multiplicação e adição mod 2

(

( Z )

mod

) ∈ { 0 , 1 }

{\textstyle (p_{x}(Z){\bmod {2}})\in \{0,1\}}

. Ou seja, a função de codificação é definida por

C ( x ) =

(

( Z )

mod

)

Z ∈ { 0 , 1

}

{\displaystyle C(x)=\left(p_{x}(Z){\bmod {2}}\right)_{Z\in \{0,1\}^{m}}\,.}

O fato de que a palavra-código

C ( x )

{\displaystyle C(x)}

é suficiente para reconstruir unicamente

{\displaystyle x}

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

C ( 0 ) = 0

{\displaystyle C(0)=0}

C ( x + y ) = C ( x ) + C ( y )

mod

{\displaystyle C(x+y)=C(x)+C(y){\bmod {2}}}

vale para todas as mensagens

x , y ∈ { 0 , 1

}

{\displaystyle x,y\in \{0,1\}^{k}}

, a função

{\displaystyle C}

é um mapa linear. Assim, o código de Reed–Muller é um código linear.

Exemplo Para o código RM(2, 4), os parâmetros são os seguintes:

= 2

= 4

(

4 2

)

(

4 1

)

(

4 0

)

= 6 + 4 + 1 = 11

= 16

{\textstyle {\begin{aligned}r&=2\\m&=4\\k&=\textstyle {\binom {4}{2}}+{\binom {4}{1}}+{\binom {4}{0}}=6+4+1=11\\n&=2^{m}=16\\\end{aligned}}}

Seja

C : { 0 , 1

}

→ { 0 , 1

}

{\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}

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

{\textstyle p_{x}}

em 4 variáveis:

(

)

= 1 + ( 1 ⋅

+ 0 ⋅

+ 1 ⋅

+ 0 ⋅

) + ( 0 ⋅

+ 1 ⋅

+ 0 ⋅

+ 1 ⋅

+ 0 ⋅

+ 1 ⋅

)

= 1 +

{\displaystyle {\begin{aligned}p_{x}(Z_{1},Z_{2},Z_{3},Z_{4})&=1+(1\cdot Z_{1}+0\cdot Z_{2}+1\cdot Z_{3}+0\cdot Z_{4})+(0\cdot Z_{1}Z_{2}+1\cdot Z_{1}Z_{3}+0\cdot Z_{1}Z_{4}+1\cdot Z_{2}Z_{3}+0\cdot Z_{2}Z_{4}+1\cdot Z_{3}Z_{4})\\&=1+Z_{1}+Z_{3}+Z_{1}Z_{3}+Z_{2}Z_{3}+Z_{3}Z_{4}\end{aligned}}}

Então ele avalia este polinômio em todos os 16 pontos de avaliação (0101 significa

= 0 ,

= 1 ,

= 0 ,

= 1 )

{\displaystyle Z_{1}=0,Z_{2}=1,Z_{3}=0,Z_{4}=1)}

( 0000 ) = 1 ,

( 0001 ) = 1 ,

( 0010 ) = 0 ,

( 0011 ) = 1 ,

{\displaystyle p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=0,\;p_{x}(0011)=1,\;}

( 0100 ) = 1 ,

( 0101 ) = 1 ,

( 0110 ) = 1 ,

( 0111 ) = 0 ,

{\displaystyle p_{x}(0100)=1,\;p_{x}(0101)=1,\;p_{x}(0110)=1,\;p_{x}(0111)=0,\;}

( 1000 ) = 0 ,

( 1001 ) = 0 ,

( 1010 ) = 0 ,

( 1011 ) = 1 ,

{\displaystyle p_{x}(1000)=0,\;p_{x}(1001)=0,\;p_{x}(1010)=0,\;p_{x}(1011)=1,\;}

( 1100 ) = 0 ,

( 1101 ) = 0 ,

( 1110 ) = 1 ,

( 1111 ) = 0

{\displaystyle p_{x}(1100)=0,\;p_{x}(1101)=0,\;p_{x}(1110)=1,\;p_{x}(1111)=0\,.}

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

{\textstyle p_{x}}

[

, . . . ,

]

{\textstyle {\mathbb {F} }_{2}[X_{1},X_{2},...,X_{m}]}

de grau no máximo

{\textstyle r}

que você deseja encontrar. A sequência pode conter qualquer número de erros até

m − r − 1

− 1

{\textstyle 2^{m-r-1}-1}

inclusive. Se você considerar um monômio

{\textstyle \mu }

do maior grau

{\textstyle d}

{\textstyle p_{x}}

e somar todos os pontos de avaliação do polinômio onde todas as variáveis em

{\textstyle \mu }

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

{\textstyle \mu }

{\textstyle p_{x}}

(Há

{\textstyle 2^{d}}

tais pontos). Isso se deve ao fato de que todos os divisores monomiais inferiores de

{\textstyle \mu }

aparecem um número par de vezes na soma, e apenas

{\textstyle \mu }

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

{\textstyle \mu }

com valor 0, você a faz

m − d

{\textstyle 2^{m-d}}

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

{\textstyle \mu }

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

r = 2 , m = 4

{\textstyle r=2,m=4}

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

{\textstyle p_{x}}

é no máximo

r = 2

{\textstyle r=2}

, começamos procurando por monômios de grau 2.

μ =

{\textstyle \mu =X_{3}X_{4}}

começamos procurando pontos de avaliação com

= 0 ,

∈ { 0 , 1 } ,

∈ { 0 , 1 }

{\textstyle X_{1}=0,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}

. No código isso é: 1101 1110 0001 0110. A primeira soma é 1 (número ímpar de 1s). procuramos pontos de avaliação com

= 0 ,

= 1 ,

∈ { 0 , 1 } ,

∈ { 0 , 1 }

{\textstyle X_{1}=0,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}

. No código isso é: 1101 1110 0001 0110. A segunda soma é 1. procuramos pontos de avaliação com

= 1 ,

= 0 ,

∈ { 0 , 1 } ,

∈ { 0 , 1 }

{\textstyle X_{1}=1,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}

. No código isso é: 1101 1110 0001 0110. A terceira soma é 1. procuramos pontos de avaliação com

= 1 ,

∈ { 0 , 1 } ,

∈ { 0 , 1 }

{\textstyle X_{1}=1,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}

. 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

{\textstyle \mu }

é 1. Removemos

{\textstyle \mu }

do código antes de continuar: código: 1101 1110 0001 0110, valoração de

{\textstyle \mu }

é 0001000100010001, o novo código é 1100 1111 0000 0111

μ =

{\textstyle \mu =X_{2}X_{4}}

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.

μ =

{\textstyle \mu =X_{1}X_{4}}

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.

μ =

{\textstyle \mu =X_{2}X_{3}}

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

{\textstyle \mu }

é 0000 0011 0000 0011, código atual é agora 1100 1100 0000 0100.

μ =

{\textstyle \mu =X_{1}X_{3}}

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

{\textstyle \mu }

é 0000 0000 0011 0011, código atual é agora 1100 1100 0011 0111.

μ =

{\textstyle \mu =X_{1}X_{2}}

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.

μ =

{\textstyle \mu =X_{4}}

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.

μ =

{\textstyle \mu =X_{3}}

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

{\textstyle \mu }

é 0011 0011 0011 0011, código atual é agora 1111 1111 0000 0100. Então encontraremos 0 para

μ =

{\textstyle \mu =X_{2}}

, 1 para

μ =

{\textstyle \mu =X_{1}}

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

= 1 +

{\textstyle p_{x}=1+X_{1}+X_{3}+X_{1}X_{3}+X_{2}X_{3}+X_{3}X_{4}}

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

{\displaystyle \mathbb {F} }

de tamanho

{\displaystyle q}

, é possível estender a definição dos códigos de Reed–Muller para alfabetos de tamanho

{\displaystyle q}

. Sejam

{\displaystyle m}

{\displaystyle d}

inteiros positivos, onde

{\displaystyle m}

deve ser pensado como maior que

{\displaystyle d}

. Para codificar uma mensagem

x ∈

{\textstyle x\in \mathbb {F} ^{k}}

de largura

k =

(

m + d

)

{\displaystyle k=\textstyle {\binom {m+d}{m}}}

, a mensagem é novamente interpretada como um polinômio

{\displaystyle p_{x}}

{\displaystyle m}

variáveis de grau total no máximo

{\displaystyle d}

e com coeficientes em

{\displaystyle \mathbb {F} }

. Tal polinômio tem de fato

(

m + d

)

{\displaystyle \textstyle {\binom {m+d}{m}}}

coeficientes. A codificação Reed–Muller de

{\displaystyle x}

é a lista de todas as avaliações de

( a )

{\displaystyle p_{x}(a)}

sobre todos os

a ∈

{\displaystyle a\in \mathbb {F} ^{m}}

. Assim, o comprimento de bloco é

n =

{\displaystyle n=q^{m}}

Descrição usando uma matriz geradora 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:

X =

= {

, ... ,

} .

{\displaystyle X=\mathbb {F} _{2}^{m}=\{x_{1},\ldots ,x_{N}\}.}

Definimos no espaço N-dimensional

{\displaystyle \mathbb {F} _{2}^{N}}

os vetores indicadores

∈

{\displaystyle \mathbb {I} _{A}\in \mathbb {F} _{2}^{N}}

em subconjuntos

A ⊂ X

{\displaystyle A\subset X}

por:

(

)

{

∈ A

caso contrário

{\displaystyle \left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\text{ se }}x_{i}\in A\\0&{\text{ caso contrário}}\\\end{cases}}}

juntamente com, também em

{\displaystyle \mathbb {F} _{2}^{N}}

, a operação binária

w ∧ z = (

⋅

, ... ,

⋅

) ,

{\displaystyle w\wedge z=(w_{1}\cdot z_{1},\ldots ,w_{N}\cdot z_{N}),}

referida como produto cunha (não confundir com o produto cunha definido na álgebra exterior). Aqui,

w = (

, ... ,

)

{\displaystyle w=(w_{1},w_{2},\ldots ,w_{N})}

z = (

, ... ,

)

{\displaystyle z=(z_{1},z_{2},\ldots ,z_{N})}

são pontos em

{\displaystyle \mathbb {F} _{2}^{N}}

(vetores binários N-dimensionais), e a operação

⋅

{\displaystyle \cdot }

é a multiplicação usual no corpo

{\displaystyle \mathbb {F} _{2}}

{\displaystyle \mathbb {F} _{2}^{m}}

é um espaço vetorial m-dimensional sobre o corpo

{\displaystyle \mathbb {F} _{2}}

, então é possível escrever

(

)

= { (

, ... ,

) ∣

∈

} .

{\displaystyle (\mathbb {F} _{2})^{m}=\{(y_{m},\ldots ,y_{1})\mid y_{i}\in \mathbb {F} _{2}\}.}

Definimos no espaço N-dimensional

{\displaystyle \mathbb {F} _{2}^{N}}

os seguintes vetores com comprimento

N :

= ( 1 , 1 , ... , 1 )

{\displaystyle N:v_{0}=(1,1,\ldots ,1)}

{\displaystyle v_{i}=\mathbb {I} _{H_{i}},}

onde 1 ≤ i ≤ m e os Hi são hiperplanos em

(

)

{\displaystyle (\mathbb {F} _{2})^{m}}

(com dimensão m − 1):

= { y ∈ (

)

∣

= 0 } .

{\displaystyle H_{i}=\{y\in (\mathbb {F} _{2})^{m}\mid y_{i}=0\}.}

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

, ... ,

, ... , (

∧

) , ... (

∧

... ∧

)

{\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 Seja m = 3. Então N = 8, e

X =

= { ( 0 , 0 , 0 ) , ( 0 , 0 , 1 ) , ( 0 , 1 , 0 ) ... , ( 1 , 1 , 1 ) } ,

{\displaystyle X=\mathbb {F} _{2}^{3}=\{(0,0,0),(0,0,1),(0,1,0)\ldots ,(1,1,1)\},}

= ( 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 )

= ( 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 )

= ( 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 )

= ( 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 ) .

{\displaystyle {\begin{aligned}v_{0}&=(1,1,1,1,1,1,1,1)\\[2pt]v_{1}&=(1,0,1,0,1,0,1,0)\\[2pt]v_{2}&=(1,1,0,0,1,1,0,0)\\[2pt]v_{3}&=(1,1,1,1,0,0,0,0).\end{aligned}}}

O código RM(1,3) é gerado pelo conjunto

{

} ,

{\displaystyle \{v_{0},v_{1},v_{2},v_{3}\},\,}

ou mais explicitamente pelas linhas da matriz:

(

)

{\displaystyle {\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\end{pmatrix}}}

Exemplo 2 O código RM(2,3) é gerado pelo conjunto:

{

∧

}

{\displaystyle \{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2}\wedge v_{3}\}}

ou mais explicitamente pelas linhas da matriz:

(

)

{\displaystyle {\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\1&0&1&0&0&0&0&0\\1&1&0&0&0&0&0&0\\\end{pmatrix}}}

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

{\displaystyle \mathbb {F} _{2}^{N}}

. O código RM (r, m) tem rank

∑

s = 0

(

m s

)

{\displaystyle \sum _{s=0}^{r}{m \choose s}.}

RM (r, m) = RM (r, m − 1) | RM (r − 1, m − 1) onde '|' denota o produto barra de dois códigos. RM (r, m) 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 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. Uma pista se a decodificação foi bem-sucedida é ter uma palavra recebida modificada toda zero, no final da decodificação de estágio (r + 1) através da lógica majoritária. Esta técnica foi proposta por Irving S. Reed e é mais geral quando aplicada a outros códigos de geometria finita.

Descrição usando uma construção recursiva Um código Reed–Muller RM(r,m) existe para quaisquer inteiros

m ≥ 0

{\displaystyle m\geq 0}

0 ≤ r ≤ m

{\displaystyle 0\leq r\leq m}

. RM(m, m) é definido como o código universo (

, 1

{\displaystyle 2^{m},2^{m},1}

). RM(−1,m) é definido como o código trivial (

, 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

R M

( r , m ) = { (

) ∣

∈

R M

( r , m − 1 ) ,

∈

R M

( r − 1 , m − 1 ) } .

{\displaystyle \mathrm {RM} (r,m)=\{(\mathbf {u} ,\mathbf {u} +\mathbf {v} )\mid \mathbf {u} \in \mathrm {RM} (r,m-1),\mathbf {v} \in \mathrm {RM} (r-1,m-1)\}.}

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 =

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.

Casos especiais dos códigos de Reed–Muller

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

[

, k ,

m − r

]

{\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

{\displaystyle \textstyle 2^{m}}

, comprimento da mensagem (ou dimensão) k, e distância mínima

m − r

{\displaystyle \textstyle 2^{m-r}}

Propriedades dos códigos RM(r,m) para r≤1 ou r≥m-2 Códigos RM(0, m) são códigos de repetição de comprimento N = 2m, taxa

R =

1 N

{\displaystyle {R={\tfrac {1}{N}}}}

e distância mínima

min

= N

{\displaystyle d_{\min }=N}

. Códigos RM(1, m) são códigos de verificação de paridade de comprimento N = 2m, taxa

R =

m + 1

{\displaystyle R={\tfrac {m+1}{N}}}

e distância mínima

min

N 2

{\displaystyle d_{\min }={\tfrac {N}{2}}}

. Códigos RM(m − 1, m) são códigos de verificação de paridade única de comprimento N = 2m, taxa

R =

N − 1

{\displaystyle R={\tfrac {N-1}{N}}}

e distância mínima

min

= 2

{\displaystyle d_{\min }=2}

. Códigos RM(m − 2, m) são a família de códigos de Hamming estendidos de comprimento N = 2m com distância mínima

min

= 4

{\displaystyle d_{\min }=4}

Referências

Leitura adicional Shu Lin; Daniel Costello (2005). Error Control Coding 2 ed. [S.l.]: Pearson. ISBN 978-0-13-017973-9 Capítulo 4. J.H. van Lint (1992). Introduction to Coding Theory. Col: GTM. 86 2 ed. [S.l.]: Springer-Verlag. ISBN 978-3-540-54894-2 Capítulo 4.5.

Ligações externas MIT OpenCourseWare, 6.451 Principles of Digital Communication II, Lecture Notes seção 6.4 Implementação GPL em Matlab de códigos RM Código-fonte GPL da implementação em Matlab de códigos RM Weiss, E. (setembro de 1962). «Generalized Reed-Muller codes». Information and Control. 5 (3): 213–222. ISSN 0019-9958. doi:10.1016/s0019-9958(62)90555-7

Código Reed-Muller

Mais conteúdos de Ciência

Thrichomys apereoides apereoides

Neoplecostomus canastra