🍠 🐐 👨🏻‍🔬 Corrección de múltiples errores al codificar mensajes 🐿️ 🛀 📲

En los sistemas de información, el intercambio de mensajes en las redes de comunicación o informática va acompañado de influencias perturbadoras del entorno o de un intruso, lo que provoca la aparición de distorsiones de señal y errores en los símbolos durante la transmisión digital. La lucha contra este fenómeno se lleva a cabo mediante códigos de corrección. Anteriormente describí el código Hamming y mostré cómo corregir un solo error en una palabra de código. Naturalmente, surgió la pregunta sobre situaciones con una gran cantidad de errores. Hoy consideraremos el caso de dos errores en una palabra de código (error múltiple). Por un lado, todo en teoría es más o menos simple y comprensible, pero por otro, no es nada obvio. La presentación del material se basa en los trabajos de E. Berlekamp.

Disposiciones teóricas

La idea de utilizar la redundancia organizada en los mensajes llevó a R. Hamming a la construcción del código de corrección que se describe aquí . El código de corrección lineal (n, k) se caracteriza por una matriz de verificación (m × n) H. Los requisitos para la matriz son simples: el número de filas coincide con el número de símbolos de verificación, sus columnas deben ser diferentes de cero y todas son diferentes. Además, los valores de columna describen los números de posición ocupados en la palabra de código por caracteres de palabra que son elementos del campo final.

A menudo, el decodificador utiliza un cálculo de síndrome calculado para esa palabra para determinar si una palabra transmitida tiene un error. El síndrome es igual a la suma de las columnas de esta matriz multiplicada por los componentes del vector de error. Si H contiene m líneas y el código le permite corregir errores individuales, entonces la longitud del bloque (palabra de código) no excede

n \leq 2^{m} - 1

$n≤2^m-1$ ... También es importante la viabilidad de la distancia requerida de las palabras de código entre sí.

Los códigos de Hamming alcanzan este límite. Cada posición de la palabra del código de Hamming se puede numerar con un vector binario que coincida con la columna correspondiente de la matriz H. En este caso, el síndrome coincidirá directamente con el número de posición donde ocurrió el error (si solo hay un error) o con la suma binaria de números (si hay varios errores).

La numeración vectorial es una idea muy fructífera. Además, asumiremos

n \leq 2^{m} - 1

$n≤2^m-1$ y que la i-ésima posición de la palabra está numerada i.

La numeración binaria (es decir, dicha representación) se denomina localizador de posición. Suponga que desea corregir todos los errores dobles y simples. Aparentemente, esto requerirá una gran redundancia de código, es decir, la matriz H debe tener más filas (el doble del número). Por lo tanto, formaremos una matriz H con 2m filas y con

n \leq 2^{m} - 1

$n≤2^m-1$ columnas, y es aconsejable elegir columnas diferentes. Para las primeras m filas, tomaremos la matriz anterior del código de Hamming. Estos son los vectores de palabras básicos del espacio de palabras.

Ejemplo 1

Sea m = 5 yn = 31. Sería deseable obtener un código (n, k) que corrija errores dobles, con una matriz de verificación de paridad H en la forma:

Para las funciones fj (ξ) indicadas en la matriz, es deseable tener una función que mapee conjunto de vectores de 5 dimensiones en sí mismo. Las últimas 5 filas de la matriz definirán el código de Hamming si y solo si la función f es una biyección (permutación).

Si las primeras 5 líneas y las últimas 5 líneas le permiten corregir errores individuales por separado, entonces quizás juntas le permitan corregir dos errores.

Debemos aprender a sumar, restar, multiplicar y dividir vectores binarios de 5 dimensiones, representarlos por polinomios de grado 4 como máximo, para encontrar la función requerida fj (ξ).

Ejemplo 2

00000 ← → 0

00010 ← → 1

00011 ← → x

...

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

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

La suma y diferencia de tales polinomios corresponde a la suma y diferencia de vectores:

0 ± 0 = 0, 0 ± 1 = 1, 1 ± 0 = 1, 1 ± 1 = 0, los signos de ± tienen el mismo significado en el caso binario. No es así con la multiplicación, el exponente del resultado de la multiplicación puede exceder 4.

Ejemplo 3

(х^{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=$

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

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

Se necesita un método de reducción de grados superiores a 4.

Se denomina construcción (de reducción) de residuos módulo un polinomio irreducible M (x) de grado 5; el método consiste en la transición de los polinomios de los productos a sus residuos después de la división por

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

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

Así que eso

х^{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

х^{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).$

El símbolo ≡ dice "comparable a".

En forma general A (x) ≡a (x) mod M (x)

Si y solo si existe un polinomio C (x) tal que

A (x) = M (x) C (x) + a (x) los coeficientes de los polinomios se reducen módulo dos:

A (x) ≡ a (x) mod (2, M (x)).

Propiedades importantes de las comparaciones

Si a (x) ≡A (x) mod M (x) yb (x) ≡ B (x) mod M (x), entonces

a (x) ± b (x) ≡ A (x) ± B (x ) mod M (x) y a

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

Además, si los grados de los polinomios a (x) y A (x) son menores que el grado de M (x),

se sigue de la fórmula a (x) ≡ A (x) mod (2, M (x)) que a (x) = A (x).

Hay 2 clases de residuos diferentes en grados degM (x), es decir, tantos como polinomios diferentes de grado menor que m, es decir cuántos residuos de división diferentes pueden ser. La división es aún más difícil.

Algoritmo de división

Por números.

Para a y M dados, hay números q y A definidos de forma única, tales que a = qM + A, 0 ≤ A ≤ M,

para polinomios con coeficientes de un campo dado.

Para dados a (x) y M (x), hay polinomios q (x) y A (x) definidos de manera única tales que a (x) = q (x) M (x) + A (x), degA (x ) <grados M (x).

La posibilidad de dividir polinomios es proporcionada por el algoritmo euclidiano.

Para los números, aquí se describe un ejemplo de un GCD extendido .

Para a y b dados, hay números A y B tales que aA + bB = (a, b), donde (a, b) es el MCD de los números ay b.

Para polinomios con coeficientes de un campo determinado.

Para dados a (x) y b (x), existen polinomios A (x) y B (x) tales que

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

donde (a (x), b (x)) es el divisor común normalizado de a (x) y b (x) de mayor grado.

Si a (x) y M (x) tienen un divisor común d (x) ≠ 1, entonces la división por a (x) mod M (x) no siempre es posible.

Es obvio que la división por a (x) es equivalente a la multiplicación por A (x).

Dado que si (a (x), b (x)) = 1 = MCD, entonces de acuerdo con el algoritmo de Euclides, hay A (x) y B (x) tales que a (x) A (x) + b (x) B (x) = 1, de modo que a (x) A (x) ≡ 1mod b (x). Comprobando que un polinomio binario es irreducible sobre el campo GF (

2^{5}

$2^5$ ), se realiza mediante división directa por todos los posibles divisores con grados inferiores a grados M (x).

Ejemplo 4 .

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

$M(x) = x^5+x^2 +1$ dividido por xy por (x + 1)

por divisores lineales. El resultado de la división no es cero. Dividir por divisores cuadrados

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

$^2 , ^2 +=( +1),^2 +1, ^2 +2 +1= ( +1)^2, ^2 + + 1.$ ... Dan saldos distintos de cero. No existen divisores de grado ≥ 3, ya que su producto da un grado ≥ 6.

Así, los polinomios se pueden sumar, restar, multiplicar y dividir módulo

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

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

Pasamos a la búsqueda de una función para la matriz de verificación de paridad H que especifica un código de corrección de doble error con una longitud de bloque de 31 y una tasa de 21/31; 31-21 = 10 = 2t - símbolos de verificación = 10. Dicha función debe tener como raíz el número de posiciones erróneas en la palabra de código, es decir, cuando los números de posición se sustituyen en esta función, la convierte en cero.

Buscando función

Suponga que β1 y β2 son los números de los caracteres (posiciones) distorsionados de la palabra. Usando la notación binaria de los números β1 y β2 , estos números se pueden representar como clases de residuos módulo M (x), es decir, establecer la correspondencia βi → β ⁽ⁱ⁾ (x) - polinomios binarios de grado <5.

Las primeras 5 condiciones de prueba determinan β1 + β2 ; el segundo conjunto de ecuaciones de prueba debe determinar f (β1) + f (β2) .

El decodificador debe determinar β1 y β2 de acuerdo con el sistema dado:

¿Cuál debería ser la función f (x) ?

La función más simple es la multiplicación por una constante f (β) ≡ αβ () modM (x) .

Pero entonces ξ2 = αξ1 , es decir las ecuaciones del sistema son dependientes. Las cinco nuevas condiciones de prueba no darán nada nuevo al decodificador.

De manera similar, la función f (β) = β + α no cambia la situación, ya que ξ2 = ξ1 .

Probar funciones de potencia: primera toma

f (β) = β^{2}

$f(β) = β^2$ ... Además,

estas ecuaciones también son dependientes, ya 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$

Entonces, la segunda ecuación es el cuadrado de la primera.

Molesto

f (β) = β^{3}

$f(β) = β^3$ ... Cambiar la forma de la ecuación del decodificador:

Ubicación

ξ 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).$

Entonces para ξ1 ≠ 0 tenemos

Entonces, β1 y β2 satisfacen la ecuación

Por lo tanto, si ocurrieron exactamente dos errores, entonces sus localizadores satisfacen esta ecuación.

Dado que esta ecuación tiene exactamente 2 raíces en el campo de polinomios binarios módulo M (x) , el decodificador siempre puede encontrar los dos localizadores requeridos.

Si solo ocurre un error, entonces β1 = ξ1 y $β1^2 = ξ2$ ... Por tanto, en este caso, el único error satisface la ecuación β + ξ1 = 0 o 1+ ξ1β ^-1 = 0 .

Finalmente, el decodificador siempre realiza la decodificación, si no ocurrieron errores, en este caso ξ1 + ξ2 = 0 .

Es más conveniente (en la práctica) operar no directamente con un polinomio cuyas raíces son localizadores de errores, sino con un polinomio cuyas raíces son mutuas a los localizadores; aquellos. son recíprocos multiplicativos para ellos.

Está claro que con no más de dos errores, el decodificador puede determinar los números de error. Si se distorsionan tres o más símbolos, se producirá un error de decodificación o una falla de decodificación.

Entonces la función

f (x) = x^{3}

$f(x) = x^3$ adecuado para construir las cinco filas inferiores de la matriz de verificación H de un código binario con una longitud de palabra de código de 31 y 10 símbolos de verificación, corrigiendo todos los errores dobles.

Las primeras cinco verificaciones especifican la suma de los números de error (S1); las segundas cinco verificaciones especifican la suma de los cubos de números de error (S3).

El procedimiento de decodificación consta de tres pasos principales:

se comprueba cada palabra de código recibida y se calculan S1 y S3;
encuentre el polinomio del localizador de errores en σ (z);
se calculan los valores mutuos para las raíces σ (z) y se cambian los símbolos en las posiciones correspondientes de la palabra resultante.

Corrección de múltiples errores al codificar mensajes

Disposiciones teóricas

Propiedades importantes de las comparaciones

Algoritmo de división

Buscando función

More articles: