Código de corrección

El código de corrección (también código de corrección de errores ) es un código diseñado para detectar y corregir errores .

La técnica principal consiste en agregar información redundante especialmente estructurada (por ejemplo, el número de cheque ) a la carga útil al escribir (transmitir) y al leer (recibir), utilizando dicha información redundante para detectar y corregir errores. El número de errores que se pueden corregir es limitado y depende del código particular que se utilice.

Los códigos de detección de errores (que solo pueden establecer el hecho de un error) pertenecen a las mismas clases de códigos que los códigos de corrección de errores. De hecho, cualquier código de corrección de errores también se puede usar para detectar errores (al hacerlo, podrá detectar más errores de los que pudo corregir). Los códigos de corrección de errores se utilizan en sistemas de comunicación digital , incluidos: satélite, radioenlace, celular, transmisión de datos a través de canales telefónicos, así como en sistemas de almacenamiento de información, incluidos magnéticos y ópticos. Los códigos de detección de errores se utilizan en varios niveles de protocolos de red .

Según su forma de trabajar con los datos, los códigos correctores de errores se dividen en bloques , que dividen la información en fragmentos de longitud constante y procesan cada uno de ellos por separado, y convolucionales , que trabajan con los datos como un flujo continuo. .

Códigos de bloque

Un código de bloque que divide la información en fragmentos de longitud de bits y los convierte en palabras de código de longitud de bits generalmente se denota ; el número se llama tasa de código . Si el código deja los bits originales sin cambios y agrega controles, dicho código se llama sistemático , de lo contrario, no sistemático . $k$ $norte$ $(n,\;k)$ $R=\frac{k}{n}$ $k$ $nk$

Puede configurar el código de bloque de diferentes maneras, incluida una tabla donde cada conjunto de bits de información está asociado con un bit de la palabra de código. Sin embargo, un buen código debe cumplir al menos con los siguientes criterios: $k$ $norte$

la capacidad de corregir tantos errores como sea posible,
la menor redundancia posible,
facilidad de codificación y decodificación.

Los requisitos anteriores generalmente se contradicen entre sí, por lo que hay una gran cantidad de códigos, cada uno de los cuales es adecuado para una determinada gama de tareas. Casi todos los códigos utilizados son lineales , esto se debe a que los códigos no lineales son mucho más difíciles de estudiar, y es difícil que brinden una facilidad aceptable de codificación y decodificación.

Códigos lineales de forma general

Un código de bloque lineal es un código tal que el conjunto de sus palabras de código forma un subespacio lineal bidimensional en un espacio lineal bidimensional , isomorfo al espacio de vectores de bits . $k$ $C$ $norte$ $k$

Esto significa que la operación de codificación corresponde a la multiplicación del vector de bits original por una matriz no degenerada , denominada matriz generadora. $k$ $GRAMO$

Para un subespacio ortogonal con respecto a y una matriz que define la base de este subespacio, y para cualquier vector , se cumple lo siguiente: $C$ $C^{\perp}$ $H$ $\overrightarrow{v}\en C$

{\overrightarrow {v}}H^{T}={\overrightarrow {0}}

. Distancia mínima y poder corrector

La distancia de Hamming (métrica de Hamming) entre dos palabras de código es el número de bits diferentes en las posiciones correspondientes: $\overrightarrow{u}$ $\overrightarrow{v}$

d_H(\overrightarrow{u},\;\overrightarrow{v})=\sum_s{|u^{(s)}-v^{(s)}|}

La distancia mínima de Hamming es una característica importante de un código de bloque lineal. Muestra cuán "lejos" están los códigos entre sí. Define otra característica no menos importante: la capacidad correctiva : $d_\min=\min_{u\ne v}d_H(\overrightarrow{u},\;\overrightarrow{v})$

t=\left\lpiso\frac{d_\min-1}{2}\right\rpiso

El poder correctivo determina cuántos errores de transmisión de código (de tipo ) se puede garantizar que se corregirán. Es decir, alrededor de cada palabra clave tenemos -neighborhood , que consta de todas las opciones posibles para transmitir la palabra clave con un número de errores ( ) no superior a . No hay dos vecindades de dos palabras de código cualesquiera que se crucen entre sí, ya que la distancia entre las palabras de código (es decir, los centros de estas vecindades) siempre es mayor que dos de sus radios . $1\flecha izquierda-derecha 0$ $A$ $t$ $A$ $A$ $1\flecha izquierda-derecha 0$ $t$ $d_H(A,\;B)\geqslant d_\min>2t$

Así, habiendo recibido una combinación de código distorsionada de , el decodificador decide que la combinación de código original era , por lo que no corrige más errores. $A$ $A$ $t$

Por ejemplo, si solo hay dos palabras clave y con una distancia de Hamming entre ellas igual a 3, se puede corregir un error en un bit de la palabra, ya que incluso en este caso la palabra recibida está más cerca de la palabra clave que de . Pero si el canal introdujo errores en dos bits (en los que se diferenció de ), entonces el resultado de una transmisión errónea estará más cerca de , y el decodificador decidirá que la palabra fue transmitida . $A$ $B$ $A$ $A$ $B$ $A$ $B$ $A$ $B$ $A$ $B$

Códigos de Hamming

Los códigos de Hamming son los códigos lineales más simples con una distancia mínima de 3, es decir, capaces de corregir un error. El código de Hamming se puede representar de tal manera que el síndrome es:

\overrightarrow{s}=\overrightarrow{r}H^T

donde es el vector recibido, será igual al número de la posición en la que ocurrió el error. Esta propiedad hace que la decodificación sea muy fácil. $\overrightarrow{r}$

Método general para decodificar códigos de línea

Cualquier código (incluido el no lineal) se puede decodificar utilizando una tabla regular, donde cada valor de la palabra recibida corresponde a la palabra transmitida más probable . Sin embargo, este método requiere el uso de tablas enormes para palabras de código relativamente pequeñas. $\overrightarrow{r}_i$ $\overrightarrow{u}_i$

Para códigos lineales, este método se puede simplificar significativamente. En este caso, para cada vector recibido , se calcula el síndrome . Dado que , donde es la palabra clave y es el vector de error, entonces . Luego, utilizando la tabla de síndromes, se determina un vector de error, con la ayuda de la cual se determina la palabra de código transmitida. En este caso, la mesa es mucho más pequeña que cuando se usa el método anterior. $\overrightarrow{r}_i$ $\overrightarrow{s}_i=\overrightarrow{r}_i H^T$ $\overrightarrow{r}_i=\overrightarrow{v}_i+\overrightarrow{e}_i$ $\overrightarrow{v}_i$ $\overrightarrow{e}_i$ $\overrightarrow{s}_i=\overrightarrow{e}_i H^T$

Códigos cíclicos lineales

A pesar de que la decodificación de códigos lineales es mucho más fácil que la decodificación de la mayoría de los códigos no lineales, para la mayoría de los códigos este proceso sigue siendo bastante complicado. Los códigos cíclicos , además de una decodificación más sencilla, tienen otras propiedades importantes.

Un código cíclico es un código lineal con la siguiente propiedad: si es una palabra de código, entonces su permutación cíclica también es una palabra de código. $\overrightarrow{v}$

Las palabras de un código cíclico se representan convenientemente como polinomios. Por ejemplo, una palabra clave se representa como un polinomio . En este caso, el desplazamiento cíclico de la palabra clave es equivalente a multiplicar el polinomio por el módulo . $\overrightarrow{v}=(v_0,\;v_1,\;\ldots,\;v_{n-1})$ $v(x)=v_0+v_1 x+\ldots+v_{n-1}x^{n-1}$ $X$ $x^n-1$

La mayoría de las veces, se utilizan códigos cíclicos binarios (es decir, pueden tomar los valores 0 o 1). $v_0,\;v_1,\;\ldots$

Polinomio generador

Se puede demostrar que todas las palabras de código de un código cíclico particular son múltiplos de cierto polinomio generador (generador) . El polinomio generador es un divisor . $g(x)$ $x^n-1$

Con la ayuda de un polinomio generador, la codificación se realiza mediante un código cíclico. En particular:

la codificación no sistemática se realiza multiplicando el vector codificado por : ; $g(x)$ $v(x)=u(x)g(x)$
la codificación sistemática se lleva a cabo “añadiendo” a la palabra codificada el resto de la división por , es decir, . $x^{nk}u(x)$ $g(x)$ $v(x)=x^{nk}u(x)+[x^{nk}u(x)\,\bmod\,g(x)]$

Códigos CRC

Los códigos CRC ( en inglés Cyclic Redundancy Check - verificación redundante cíclica) son códigos sistemáticos diseñados no para corregir errores, sino para detectarlos. Utilizan el método de codificación sistemática descrito anteriormente: la "suma de control" se calcula dividiendo por . Dado que no se requiere corrección de errores, la validación de la transmisión se puede realizar de la misma manera. $x^{nk}u(x)$ $g(x)$

Así, la forma del polinomio especifica un código CRC específico. Ejemplos de los polinomios más populares: $g(x)$

Nombre clave	La licenciatura	Polinomio
CRC-12	12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$
CRC-16	dieciséis	$x^{16}+x^{15}+x^{2}+1$
CRC- CCITT	dieciséis	$x^{16}+x^{12}+x^{5}+1$
CRC-32	32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^ {8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$

Códigos BCH

Los códigos Bose-Chowdhury-Hockwingham (BCH) son una subclase de códigos cíclicos. Su característica distintiva es la capacidad de construir un código BCH con una distancia mínima no inferior a la dada. Esto es importante porque, en términos generales, determinar la distancia mínima del código es una tarea muy difícil.

Códigos de corrección de errores de Reed-Solomon

Los códigos Reed-Solomon son códigos cíclicos no binarios que le permiten corregir errores en bloques de datos. Los elementos del vector de código no son bits, sino grupos de bits (bloques). Los códigos Reed-Solomon que operan en bytes ( octetos ) son muy comunes.

Matemáticamente, los códigos Reed-Solomon son códigos BCH .

Ventajas y desventajas de los códigos de bloque

Aunque los códigos de bloque generalmente funcionan bien con ráfagas de errores infrecuentes pero grandes , son menos efectivos para errores frecuentes pero pequeños (por ejemplo, en un canal AWGN ).

Códigos convolucionales

Los códigos convolucionales, a diferencia de los códigos de bloque, no dividen la información en fragmentos y funcionan con ella como si fuera un flujo de datos continuo. Dichos códigos, por regla general, son generados por un sistema lineal discreto e invariante en el tiempo . Por lo tanto, a diferencia de la mayoría de los códigos de bloque, la codificación convolucional es una operación muy simple, lo que no se puede decir de la decodificación.

La codificación de código convolucional se realiza utilizando un registro de desplazamiento , cuyas derivaciones se suman módulo dos. Puede haber dos (la mayoría de las veces) o más de tales sumas.

Los códigos convolucionales suelen decodificarse utilizando el algoritmo de Viterbi , que intenta recuperar la secuencia transmitida según el criterio de máxima verosimilitud .

Los códigos convolucionales funcionan de manera efectiva en un canal de ruido blanco, pero no manejan bien las ráfagas de errores. Además, si el decodificador comete un error, siempre produce una ráfaga de error en su salida.

codificación en cascada. Decodificación iterativa

Las ventajas de los diferentes métodos de codificación se pueden combinar aplicando codificación concatenada . En este caso, la información se codifica primero con un código y luego con otro, lo que da como resultado un código de producto .

Por ejemplo, la siguiente construcción es popular: los datos se codifican con el código Reed-Solomon, luego se intercalan (con caracteres ubicados cerca, lejos unos de otros) y se codifican con un código convolucional. En el receptor, primero se decodifica el código convolucional, luego se realiza el intercalado inverso (en este caso, las ráfagas de errores en la salida del decodificador convolucional caen en diferentes palabras de código del código Reed-Solomon), y luego el Reed- Se decodifica el código de Solomon.

Algunos códigos de productos están diseñados específicamente para la decodificación iterativa, en la que la decodificación se realiza en varias pasadas, cada una de las cuales utiliza información de la anterior. Esto permite una gran eficiencia, pero la decodificación requiere muchos recursos. Estos códigos incluyen códigos turbo y códigos LDPC (códigos Gallager).

Evaluación de la eficacia de los códigos

La eficiencia de los códigos está determinada por la cantidad de errores que puede corregir, la cantidad de información redundante que debe agregarse y la complejidad de la implementación de la codificación y decodificación (tanto hardware como software ).

Códigos atados y perfectos de Hamming

Que exista un código de bloque binario con capacidad correctiva . Entonces la desigualdad (llamada límite de Hamming) se cumple: $(n,k)$ $t$

\sum_{i=0}^t {n\elegir i}\leqslant 2^{nk}.

Los códigos que satisfacen este límite de igualdad se llaman perfectos. Los códigos perfectos incluyen, por ejemplo, los códigos de Hamming . Los códigos con gran poder correctivo que se usan a menudo en la práctica (como los códigos Reed-Solomon ) no son perfectos.

Literatura

Blahut R. Teoría y práctica de los códigos de control de errores. — M .: Mir , 1986. — 576 p.
McWilliams F. J., Sloan N. J. A. Teoría de los códigos de corrección de errores. Moscú: Radio y comunicación, 1979.
Morelos-Zaragoza R. El arte de la codificación correctora de errores. Métodos, algoritmos, aplicación / per. De inglés. V. B. Afanasiev . - M. : Technosfera, 2006. - 320 p. — (Mundo de la comunicación). - 2000 copias. — ISBN 5-94836-035-0 .