👨🏾‍🏫 🐤 🔚 Correção de vários erros ao codificar mensagens 🥫 🚣🏽 💛

Nos sistemas de informação, a troca de mensagens em redes de comunicação ou informática é acompanhada por influências perturbadoras do ambiente ou de um intruso, o que leva ao aparecimento de distorções de sinal e a erros nos símbolos durante a transmissão digital. O combate a este fenômeno é feito por meio de códigos de correção. Anteriormente, descrevi o código de Hamming e mostrei como corrigir um único erro em uma palavra de código. Naturalmente, surgiu a questão de situações com grande número de erros. Hoje vamos considerar o caso de dois erros em uma palavra-código (erro múltiplo). Por um lado, tudo em teoria é mais ou menos simples e compreensível, mas, por outro lado, não é nada óbvio. A apresentação do material é baseada na obra de E. Berlekamp.

Provisões teóricas

A ideia de usar redundância organizada nas mensagens levou R. Hamming à construção do código de correção aqui descrito . O código de correção linear (n, k) é caracterizado por uma matriz de verificação (m × n) H. Os requisitos para a matriz são simples: o número de linhas coincide com o número de símbolos de verificação, suas colunas devem ser diferentes de zero e todas são diferentes. Além disso, os valores da coluna descrevem os números de posição ocupados na palavra-código por caracteres de palavras que são elementos do campo final.

Freqüentemente, o decodificador usa o cálculo da síndrome calculada para aquela palavra para determinar se uma palavra transmitida está com erro. A síndrome é igual à soma das colunas dessa matriz multiplicada pelos componentes do vetor do erro. Se H contiver m linhas e o código permitir que você corrija erros simples, o comprimento do bloco (palavra-código) não excederá

. Também importante é a viabilidade da distância necessária das palavras de código umas das outras. Os códigos de Hamming atingem esse limite. Cada posição da palavra-código de Hamming pode ser numerada com um vetor binário que coincide com a coluna correspondente da matriz H. Neste caso, a síndrome coincidirá diretamente com o número da posição onde ocorreu o erro (se houver apenas um erro) ou com a soma binária dos números (se houver vários erros). A numeração vetorial é uma ideia muito frutífera. Além disso, vamos assumir

n \leq 2^{m} - 1

$n≤2^m-1$

e que a i-ésima posição da palavra é numerada como i. A numeração binária (ou seja, tal representação) é chamada delocalizador de posição.Suponha que você queira corrigir todos os erros duplos e simples. Aparentemente, isso exigirá uma grande redundância de código, ou seja, a matriz H deve ter mais linhas (duas vezes o número). Portanto, vamos formar uma matriz H com 2m linhas e com

n \leq 2^{m} - 1

$n≤2^m-1$

colunas, e é razoável escolher colunas diferentes. Para as primeiras m linhas, usaremos a matriz anterior do código de Hamming. Esses são os vetores básicos da palavra espaço.Exemplo 1 Seja m = 5 en = 31. Seria desejável obter um código (n, k) que corrige erros duplos, com uma matriz de verificação de paridade H na forma: Para as funções fj (ξ) indicadas na matriz, é desejável ter uma função que mapeia conjunto de vetores 5-dimensionais em si mesmo. As últimas 5 linhas da matriz definirão o código de Hamming se e somente se a função f for uma bijeção (permutação). Se as primeiras 5 linhas e as últimas 5 linhas separadamente permitem que você corrija erros únicos, então talvez juntas elas permitam a você corrigir dois erros.

n \leq 2^{m} - 1

$n≤2^m-1$

Devemos aprender a somar, subtrair, multiplicar e dividir vetores binários 5-dimensionais, representá-los por polinômios de grau no máximo 4, para encontrar a função necessária fj (ξ).

Exemplo 2

00000 ← → 0

00010 ← → 1

00011 ← → x

...

A soma e diferença de tais polinômios corresponde à soma e diferença dos vetores: 0 ± 0 = 0, 0 ± 1 = 1, 1 ± 0 = 1, 1 ± 1 = 0, os sinais ± têm no caso binário, o mesmo significado. Não é assim com a multiplicação, o expoente do resultado da multiplicação pode exceder 4.Exemplo 3

11011 \leftarrow\to х^{4} + х^{3} + х + 1

$11011 ←→ ^4 +^3++1$

(х^{3} + х + 1) х^{4} + х^{3} + х + 1) = х^{7} + х^{6} + х^{5} + 3 х^{4} + 2 х^{3} + х^{2} + 2 х + 1 =

$(^3++1)^4+^3++1)=^7+^6+^5+3^4+2^3+^2+2+1=$

. É necessário um método de abaixamento de graus maiores que 4. É denominado (redução) a construção do módulo de resíduos um polinômio irredutível M (x) de grau 5; o método consiste na transição dos polinômios dos produtos para seus remanescentes após a divisão por

= х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1

$=^7+^6+^5+^4+^2+1$

Então

M (x) = x^{5} + x^{2} + 1

$M(x)=x^5+x^2 + 1$

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 = (х^{2} + х + 1) (х^{5} + х^{2} + 1) + х^{3} + х^{2} + х

$^7+^6+^5+^4+^2+1 =(^2+ + 1)(^5 +^2 +1) +^3 +^2 +$

O símbolo ≡ diz "comparável a". Em geral, A (x) ≡a (x) mod M (x) Se e somente se existe um polinômio C (x) tal que A (x) = M (x) C (x) + a (x) os coeficientes dos polinômios são reduzidos módulo dois: A (x) ≡ a (x) mod (2, M (x)).

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 \equiv (х^{3} + х^{2} + x) m o d (х^{5} + х^{2} + 1) .

$^7+^6+^5+^4+^2+1 ≡(^3+^2 + x)mod(^5 +^2 +1).$

Propriedades importantes de comparações

Se a (x) ≡A (x) mod M (x) e b (x) ≡ B (x) mod M (x), então

a (x) ± b (x) ≡ A (x) ± B (x ) mod M (x) e à

(x) b (x) ≡ (x) B (x) mod M (x).

Além disso, se os graus dos polinômios a (x) e A (x) são menores que o grau de M (x),

segue -se da fórmula a (x) ≡ A (x) mod (2, M (x)) que a (x) = A (x).

Existem 2 classes de resíduos diferentes em graus degM (x) - isto é, tantos quantos polinômios diferentes de grau inferior a m, ou seja, quantos resíduos de divisão diferentes podem ter. A divisão é ainda mais difícil.

Algoritmo de divisão

Para números.

Para dados a e M, existem números definidos exclusivamente q e A, tais que a = qM + A, 0 ≤ A ≤ M,

para polinômios com coeficientes de um determinado campo.

Para dados a (x) e M (x), existem polinômios definidos exclusivamente q (x) e A (x) de modo que a (x) = q (x) M (x) + A (x), degA (x ) <deg M (x).

A possibilidade de dividir polinômios é fornecida pelo algoritmo Euclidiano.

Para números, um exemplo de GCD estendido é descrito aqui .

Para um dado aeb, existem números A e B tais que aA + bB = (a, b), onde (a, b) é o GCD dos números a e b.

Para polinômios com coeficientes de um determinado campo.

Para dados a (x) e b (x), existem polinômios A (x) e B (x) tais que

a (x) A (x) + b (x) B (x) = (a (x), b (x)),

onde (a (x), b (x)) é o divisor comum normalizado de a (x) e b (x) de maior grau.

Se a (x) e M (x) têm um divisor comum d (x) ≠ 1, então a divisão por a (x) mod M (x) nem sempre é possível.

É óbvio que a divisão por a (x) é equivalente à multiplicação por A (x).

Dado que se (a (x), b (x)) = 1 = GCD, então de acordo com o algoritmo de Euclides, existem A (x) e B (x) tais que a (x) A (x) + b (x) B (x) = 1, de modo que a (x) A (x) ≡ 1mod b (x). Verificar se um polinômio binário é irredutível no campo GF (

), é realizada por divisão direta por todos os divisores possíveis com graus menores que deg M (x). Exemplo 4.

2^{5}

$2^5$

dividido por x e (x + 1) por divisores lineares. O resultado da divisão não é zero. Divide por divisores quadrados

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$

.. Eles distribuem saldos diferentes de zero. Não há divisores de grau ≥ 3, já que seu produto dá grau ≥ 6. Assim, polinômios podem ser adicionados, subtraídos, multiplicados e divididos módulo

х^{2}, х^{2} + х = х (х + 1), х^{2} + 1, х^{2} + 2 х + 1 = (х + 1)^{2}, х^{2} + х + 1.

$^2 , ^2 +=( +1),^2 +1, ^2 +2 +1= ( +1)^2, ^2 + + 1.$

. Passamos à busca de uma função para a matriz de verificação de paridade H definindo um código de correção de erro duplo com um comprimento de bloco de 31 e uma taxa de 21/31; 31-21 = 10 = 2t - símbolos de verificação = 10. Tal função deve ter como raízes o número de posições erradas na palavra de código, ou seja, quando os números de posição são substituídos nesta função, ela a transforma em zero.

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$

Função de pesquisa

Suponha que β1 e β2 são os números dos caracteres distorcidos (posições) da palavra. Usando a notação binária dos números β1 e β2 , esses números podem ser representados como classes de resíduos módulo M (x), ou seja, estabelecer a correspondência βi → β ⁽ⁱ⁾ (x) - polinômios binários de grau <5.

As primeiras 5 condições de teste determinam β1 + β2 ; o segundo conjunto de equações de teste deve determinar f (β1) + f (β2) .

O decodificador deve determinar β1 e β2 de acordo com o sistema dado:

Qual deve ser a função f (x) ?

A função mais simples é a multiplicação por uma constante f (β) ≡ αβ () modM (x) .

Mas então ξ2 = αξ1 , ou seja, as equações do sistema são dependentes. As novas cinco condições de teste não darão ao decodificador nada de novo.

Da mesma forma, a função f (β) = β + α não altera a situação, pois ξ2 = ξ1 .

Experimentando funções de potência: primeiro tome

f (β) = β^{2}

$f(β) = β^2$ ... Além disso,

essas equações também são dependentes, uma vez que

ξ 1^{2} = (β 1 + β 2)^{2} = β 1^{2} + 2 β 1 β 2 + β 2^{2} = β 1^{2} + β 2^{2} = ξ 2

$ξ1^2 =(β1 + β2)^2=β1^2 + 2β1β2 + β2^2 = β1^2 + β2^2 =ξ2$

Portanto, a segunda equação é o quadrado da primeira.

Tentando

f (β) = β^{3}

$f(β) = β^3$ ... Alterar a forma da equação do decodificador:

Localização

ξ 2 = β 1^{3} + β 2^{3} = (β 1 + β 2) (β 1^{2} - β 1 β 2 + β 2^{2}) = ξ 1 (β 1 β 2 - ξ 1^{2}) .

$ξ2 =β1^3 + β2^3=(β1 + β2)(β1^2 -β1β2+ β2^2)=ξ1(β1β2-ξ1^2).$

Assim, para ξ1 ≠ 0 temos

Então, β1 e β2 satisfazem a equação.

Portanto, se exatamente dois erros ocorreram, seus localizadores satisfazem esta equação.

Uma vez que esta equação tem exatamente 2 raízes no campo de polinômios binários módulo M (x) , o decodificador pode sempre encontrar os dois localizadores necessários.

Se ocorrer apenas um erro, então β1 = ξ1 e $β1^2 = ξ2$ ... Portanto, neste caso, o único erro satisfaz a equação β + ξ1 = 0 ou 1+ ξ1β ^-1 = 0 .

Finalmente, o decodificador sempre realiza a decodificação, caso não ocorram erros, neste caso ξ1 + ξ2 = 0 .

É mais conveniente (na prática) operar não diretamente com um polinômio cujas raízes são localizadores de erro, mas com um polinômio cujas raízes são mútuas para os localizadores; Essa. são recíprocos multiplicativos para eles.

É claro que, com no máximo dois erros, o decodificador pode determinar os números dos erros. Se três ou mais símbolos estiverem distorcidos, ocorrerá um erro de decodificação ou falha de decodificação.

Então a função

f (x) = x^{3}

$f(x) = x^3$ adequado para construir as cinco filas inferiores da matriz de verificação H de um código binário com um comprimento de palavra-código de 31 e 10 símbolos de verificação, corrigindo todos os erros duplos.

As primeiras cinco verificações especificam a soma dos números dos erros (S1); as cinco verificações seguintes são a soma dos cubos de número de erro (S3).

O procedimento de decodificação consiste em três etapas principais:

cada palavra de código recebida é verificada e S1 e S3 são calculados;
encontre o polinômio localizador de erros em σ (z);
os valores mútuos para as raízes σ (z) são calculados e os símbolos nas posições correspondentes da palavra resultante são alterados.

Correção de vários erros ao codificar mensagens

Provisões teóricas

Propriedades importantes de comparações

Algoritmo de divisão

Função de pesquisa

More articles: