Código Reed – Muller - Reed–Muller code

Código Reed-Muller RM (r, m)
Nomeado após	Irving S. Reed e David E. Muller
Classificação
Modelo	Código de bloco linear
Comprimento do bloco	${\ displaystyle 2 ^ {m}}$
Comprimento da mensagem	${\ displaystyle k = \ sum _ {i = 0} ^ {r} {\ binom {m} {i}}}$
Avaliar	${\ displaystyle k / 2 ^ {m}}$
Distância	${\ displaystyle 2 ^ {mr}}$
Tamanho do alfabeto	${\ displaystyle 2}$
Notação	${\ displaystyle [2 ^ {m}, k, 2 ^ {mr}] _ {2}}$-código
v t e

Os códigos Reed-Muller são códigos de correção de erros usados ​​em aplicações de comunicação sem fio, particularmente em comunicação de espaço profundo. Além disso, o padrão 5G proposto depende de 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 foram extensivamente estudados na ciência da computação teórica .

Os códigos Reed-Muller generalizam os códigos Reed-Solomon e o código Walsh-Hadamard . Códigos de Reed-Muller são códigos de bloco lineares que são localmente testável , localmente decodable e lista decodable . Essas propriedades as tornam particularmente úteis no projeto de provas verificáveis ​​probabilisticamente .

Os códigos Reed-Muller tradicionais são códigos binários, o que significa que as mensagens e palavras-código são sequências 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 que consiste em k bits, onde se mantém, o código RM ( r ,  m ) produz uma palavra-código que consiste em 2 ^m bits. ${\ displaystyle \ textstyle k = \ sum _ {i = 0} ^ {r} {\ binom {m} {i}}}$

Os códigos Reed-Muller são nomeados em homenagem a 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 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 testáveis localmente e códigos decodificáveis ​​localmente .

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 Reed-Muller RM ( r , m ) tem comprimento de mensagem e comprimento de bloco . Uma forma de definir uma codificação para este código é baseada na avaliação de polinômios multilineares com m variáveis ​​e grau total r . Cada polinômio multilinear sobre o campo finito com dois elementos pode ser escrito da seguinte forma: ${\ textstyle C: \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {n}}$${\ textstyle x \ in \ {0,1 \} ^ {k}}$${\ textstyle C (x) \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle \ textstyle k = \ sum _ {i = 0} ^ {r} {\ binom {m} {i}}}$ ${\ displaystyle \ textstyle n = 2 ^ {m}}$

O são as variáveis do polinômio, e os valores são os coeficientes do polinômio. Como existem exatamente coeficientes, a mensagem consiste em valores que podem ser usados ​​como esses coeficientes. Dessa forma, cada mensagem dá origem a um polinômio único em m variáveis. Para construir a palavra-código , o codificador avalia em todos os pontos de avaliação , onde interpreta a soma como módulo dois de adição para obter um bit . Ou seja, a função de codificação é definida via${\ textstyle Z_ {1}, \ dots, Z_ {m}}$${\ textstyle c_ {S} \ in \ {0,1 \}}$${\ textstyle k}$${\ textstyle x \ in \ {0,1 \} ^ {k}}$${\ textstyle k}$${\ textstyle x}$${\ textstyle p_ {x}}$${\ textstyle C (x)}$${\ textstyle p_ {x}}$${\ textstyle a \ in \ {0,1 \} ^ {m}}$${\ textstyle (p_ {x} (a) {\ bmod {2}}) \ in \ {0,1 \}}$

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

O fato de a palavra-código ser suficiente para reconstruir com exclusividade decorre da

interpolação de Lagrange , que afirma que os coeficientes de um polinômio são determinados de forma única quando um número suficiente de pontos de avaliação é fornecido. Uma vez que e é válido para todas as mensagens , a função é um mapa linear . Portanto, o código Reed-Muller é um código linear . ${\ displaystyle C (x)}$${\ displaystyle x}$${\ displaystyle C (0) = 0}$${\ displaystyle C (x + y) = C (x) + C (y) {\ bmod {2}}}$${\ displaystyle x, y \ in \ {0,1 \} ^ {k}}$${\ displaystyle C}$

Exemplo

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

${\ textstyle {\ begin {alinhados} r & = 2 \\ m & = 4 \\ k & = \ textstyle {\ binom {4} {2}} + {\ binom {4} {1}} + {\ binom {4 } {0}} = 6 + 4 + 1 = 11 \\ n & = 2 ^ {m} = 16 \\\ fim {alinhado}}}$

Deixe ser a função de codificação que acabou de ser definida. Para codificar a string x = 1 1010 010101 de comprimento 11, o codificador primeiro constrói o polinômio em 4 variáveis:${\ textstyle C: \ {0,1 \} ^ {11} \ a \ {0,1 \} ^ {16}}$${\ textstyle p_ {x}}$

$${\ displaystyle {\ begin {alinhados} 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} \ fim {alinhado}}}$$

Em seguida, ele avalia este polinômio em todos os 16 pontos de avaliação:

$${\ displaystyle p_ {x} (0000) = 1, \; p_ {x} (0001) = 1, \; p_ {x} (0010) = 1, \; p_ {x} (0011) = 1, \ ; p_ {x} (0100) = 1, \; p_ {x} (0101) = 0, \; p_ {x} (0110) = 1, \; p_ {x} (0111) = 0, \; p_ {x} (1000) = 0, \; p_ {x} (1001) = 1, \; p_ {x} (1010) = 0, \; p_ {x} (1011) = 1, \; p_ {x } (1100) = 0, \; p_ {x} (1101) = 0, \; p_ {x} (1110) = 0, \; p_ {x} (1111) = 0 \ ,.}$$

Como resultado, C (1 1010 010101) = 1111 1010 0101 0000 é válido.

Decodificador

Como já foi mencionado, a interpolação de Lagrange pode ser usada para recuperar com eficiência a mensagem 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 for diferente de qualquer palavra-código. Nesse caso, um procedimento de decodificação local pode ajudar.

Generalização para alfabetos maiores por meio de polinômios de baixo grau

Usando polinômios de baixo grau sobre um campo finito de tamanho , é possível estender a definição dos códigos de Reed-Muller para alfabetos de tamanho . Let and be inteiros positivos, onde deve ser considerado maior que . Para codificar uma mensagem de largura , a mensagem é novamente interpretada como um polinômio variável de grau total no máximo e com coeficiente de . Esse polinômio de fato tem coeficientes. A codificação Reed-Muller de é a lista de todas as avaliações de todos . Assim, o comprimento do bloco é . ${\ displaystyle \ mathbb {F}}$${\ displaystyle q}$${\ displaystyle q}$${\ displaystyle m}$${\ displaystyle d}$${\ displaystyle m}$${\ displaystyle d}$${\ textstyle x \ in \ mathbb {F} ^ {k}}$${\ displaystyle k = \ textstyle {\ binom {m + d} {m}}}$${\ displaystyle m}$${\ displaystyle p_ {x}}$${\ displaystyle d}$${\ displaystyle \ mathbb {F}}$${\ displaystyle \ textstyle {\ binom {m + d} {m}}}$${\ displaystyle x}$${\ displaystyle p_ {x} (a)}$${\ displaystyle a \ in \ mathbb {F} ^ {m}}$${\ displaystyle n = q ^ {m}}$

Descrição usando uma matriz geradora

Uma matriz geradora para um código Reed-Muller RM ( r , m ) de comprimento N = 2 ^m pode ser construída como segue. Vamos escrever o conjunto de todos os vetores binários m- dimensionais como:

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

Definimos no espaço N- dimensional os

vetores indicadores${\ displaystyle \ mathbb {F} _ {2} ^ {N}}$

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

em subconjuntos por: ${\ displaystyle A \ subset X}$

${\ displaystyle \ left (\ mathbb {I} _ {A} \ right) _ {i} = {\ begin {cases} 1 & {\ mbox {if}} x_ {i} \ in A \\ 0 & {\ mbox {caso contrário}} \\\ fim {casos}}}$

junto com, também em , a operação binária ${\ displaystyle \ mathbb {F} _ {2} ^ {N}}$

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

referido como produto de cunha (não deve ser confundido com o produto de cunha definido na álgebra externa). Aqui, e estão pontos em ( vetores binários N- dimensionais), e a operação é a multiplicação usual no campo . ${\ displaystyle w = (w_ {1}, w_ {2}, \ ldots, w_ {N})}$${\ displaystyle z = (z_ {1}, z_ {2}, \ ldots, z_ {N})}$${\ displaystyle \ mathbb {F} _ {2} ^ {N}}$${\ displaystyle \ cdot}$${\ displaystyle \ mathbb {F} _ {2}}$

${\ displaystyle \ mathbb {F} _ {2} ^ {m}}$é um espaço vetorial m- dimensional sobre o campo , então é possível escrever ${\ displaystyle \ mathbb {F} _ {2}}$

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

Definimos no espaço N- dimensional os seguintes vetores com comprimento e ${\ displaystyle \ mathbb {F} _ {2} ^ {N}}$${\ displaystyle N: v_ {0} = (1,1, \ ldots, 1)}$

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

onde 1 ≤ i ≤ m e o H _i são hiperplanos em (com dimensão m - 1 ): ${\ displaystyle (\ mathbb {F} _ {2}) ^ {m}}$

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

A matriz geradora

O código Reed-Muller RM ( r , m ) de ordem r e comprimento N  = 2 ^m é o código gerado por v ₀ e os produtos em cunha de até r de v _i , 1 ≤ i ≤ m (onde por convenção a produto de cunha de menos de um vetor é a identidade da 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 em cunha até r por vez , como as linhas da matriz geradora, onde 1 ≤ i _k ≤ m . ${\ 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}})}}$

Exemplo 1

Seja m = 3. Então N = 8, e

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

e

${\ displaystyle {\ begin {alinhados} 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 {alinhado}}}$

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 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 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:

1. O conjunto de todos os produtos de cunha possíveis de até m da v _i forma uma base para .${\ displaystyle \ mathbb {F} _ {2} ^ {N}}$
2. O código RM ( r , m ) tem classificação

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

3. RM ( r , m ) = RM ( r , m - 1) | RM ( r - 1, m - 1) onde '|' denota o produto de barra de dois códigos.
4. RM ( r , m ) tem peso de Hamming mínimo de 2 ^{m - r} .

Prova

Decodificando códigos RM

Os códigos RM ( r , m ) podem ser decodificados usando a decodificação de lógica majoritária . A ideia básica da decodificação da lógica majoritária é construir várias somas de verificação para cada elemento de palavra de código recebido. Como cada uma das diferentes somas de verificação deve ter o mesmo valor (ou seja, o valor do peso do elemento da palavra da mensagem), podemos usar uma decodificação 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 de acordo com a remoção das palavras de código correspondentes ponderadas pelas contribuições da mensagem decodificada, até o estágio atual. Portanto, 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 de mensagem são calculados por meio desse 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 totalmente modificada em zero, no final da  decodificação de estágio ( r + 1) por meio da decodificação 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 e . RM ( m , m ) é definido como o código universe ( ). RM (−1, m) é definido como o código trivial ( ). Os códigos RM restantes podem ser construídos a partir desses códigos elementares usando a construção de duplicação de comprimento ${\ displaystyle m \ geq 0}$${\ displaystyle 0 \ leq r \ leq m}$${\ displaystyle 2 ^ {m}, 2 ^ {m}, 1}$${\ displaystyle 2 ^ {m}, 0, \ infty}$

${\ 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  = 2 ^m , dimensão e distância mínima para . O código duplo para RM ( r, m ) é RM ( m - r -1, m ). Isso mostra que os códigos de repetição e SPC são duais, os códigos de Hamming biortogonais e estendidos são duais e que os códigos com k  =  n / 2 são autoduais. ${\ displaystyle k (r, m) = k (r, m-1) + k (r-1, m-1)}$${\ displaystyle d = 2 ^ {mr}}$${\ displaystyle r \ geq 0}$

Casos especiais de códigos Reed-Muller

Tabela de todos os códigos RM (r, m) para m≤5

Todos os códigos RM ( r ,  m ) com tamanho de alfabeto 2 são exibidos aqui, anotados com a notação de teoria de codificação padrão [n, k, d] para códigos de bloco . O código RM ( r ,  m ) é um código, ou seja, é um código linear sobre um alfabeto binário , possui comprimento de bloco , comprimento (ou dimensão) de mensagem k e distância mínima . ${\ displaystyle m \ leq 5}$${\ displaystyle \ textstyle [2 ^ {m}, k, 2 ^ {mr}] _ {2}}$ ${\ displaystyle \ textstyle 2 ^ {m}}$ ${\ displaystyle \ textstyle 2 ^ {mr}}$

						RM ( m, m ) ( 2 m , 2 m , 1)	códigos do universo
					RM (5,5) (32,32,1)
				RM (4,4) (16,16,1)		RM ( m  - 1,  m ) (2 m , 2 m −1, 2)	Códigos SPC
			RM (3,3) (8,8,1)		RM (4,5) (32,31,2)
		RM (2,2) (4,4,1)		RM (3,4) (16,15,2)		RM ( m  - 2, m ) (2 m , 2 m - m −1, 4)	ramal Códigos de Hamming
	RM (1,1) (2,2,1)		RM (2,3) (8,7,2)		RM (3,5) (32,26,4)
RM (0,0) (1,1,1)		RM (1,2) (4,3,2)		RM (2,4) (16,11,4)
	RM (0,1) (2,1,2)		RM (1,3) (8,4,4)		RM (2,5) (32,16,8)		códigos autoduais
RM (-1,0) (1,0, ) ${\ displaystyle \ infty}$		RM (0,2) (4,1,4)		RM (1,4) (16,5,8)
	RM (-1,1) (2,0, ) ${\ displaystyle \ infty}$		RM (0,3) (8,1,8)		RM (1,5) (32,6,16)
		RM (-1,2) (4,0, ) ${\ displaystyle \ infty}$		RM (0,4) (16,1,16)		RM (1, m ) (2 m , m +1, 2 m -1 )	Códigos hadamard puncionados
			RM (-1,3) (8,0, ) ${\ displaystyle \ infty}$		RM (0,5) (32,1,32)
				RM (-1,4) (16,0, ) ${\ displaystyle \ infty}$		RM (0, m ) (2 m , 1, 2 m )	códigos de repetição
					RM (-1,5) (32,0, ) ${\ displaystyle \ infty}$
						RM (-1, m ) (2 m , 0, ∞)	códigos triviais

Propriedades dos códigos RM (r, m) para r≤1 ou r≥m-1

• Os códigos RM (0,  m ) são códigos de repetição de comprimento N  = 2 ^m , taxa e distância mínima .${\ displaystyle {R = {\ tfrac {1} {N}}}}$${\ displaystyle d _ {\ min} = N}$
• Os códigos RM (1,  m ) são códigos de verificação de paridade de comprimento N  = 2 ^m , taxa e distância mínima .${\ displaystyle R = {\ tfrac {m + 1} {N}}}$${\ displaystyle d _ {\ min} = {\ tfrac {N} {2}}}$
• Os códigos RM ( m  - 1,  m ) são códigos de verificação de paridade única de comprimento N  = 2 ^m , taxa e distância mínima .${\ displaystyle R = {\ tfrac {N-1} {N}}}$${\ displaystyle d _ {\ min} = 2}$
• Os códigos RM ( m  - 2,  m ) são a família de códigos de Hamming estendidos de comprimento N  = 2 ^m com distância mínima .${\ displaystyle d _ {\ min} = 4}$

Referências

Leitura adicional

• Shu Lin; Daniel Costello (2005). Codificação de controle de erros (2 ed.). Pearson. ISBN 978-0-13-017973-9. Capítulo 4.
• JH van Lint (1992). Introdução à Teoria da Codificação . GTM . 86 (2 ed.). Springer-Verlag . ISBN 978-3-540-54894-2. Capítulo 4.5.

links externos

• MIT OpenCourseWare , 6.451 Princípios de Comunicação Digital II, Notas de aula, seção 6.4
• Implementação GPL Matlab de códigos RM
• Fonte GPL Matlab-implementação de códigos RM
• Weiss, E. (setembro de 1962). "Códigos Reed-Muller generalizados" . Informação e controle . 5 (3): 213–222. doi : 10.1016 / s0019-9958 (62) 90555-7 . ISSN  0019-9958 .