Código de corrección de errores concatenado

En teoría de la codificación , los códigos concatenados forman una clase de códigos correctores de errores que se derivan de la combinación de un código interno y un código externo . Fueron concebidos en 1966 por Dave Forney como una solución al problema de encontrar un código que tuviera una probabilidad de error que disminuyera exponencialmente con el aumento de la longitud del bloque y una complejidad de decodificación de tiempo polinomial . ^{[ 1 ]} Los códigos concatenados se generalizaron en las comunicaciones espaciales en la década de 1970.

El campo de la codificación de canales se ocupa de enviar un flujo de datos a la mayor velocidad posible a través de un canal de comunicaciones determinado y, posteriormente, decodificar los datos originales de forma fiable en el receptor, utilizando algoritmos de codificación y decodificación que sean factibles de implementar en una tecnología determinada.

El teorema de codificación de canal de Shannon demuestra que, en muchos canales comunes, existen esquemas de codificación de canal capaces de transmitir datos de forma fiable a todas las velocidades.${\displaystyle R}$menos de un cierto umbral${\displaystyle C}$, denominada capacidad del canal dado. De hecho, la probabilidad de error de decodificación puede disminuir exponencialmente a medida que aumenta la longitud del bloque.${\displaystyle N}$del esquema de codificación tiende al infinito. Sin embargo, la complejidad de un esquema de decodificación óptimo ingenuo que simplemente calcula la probabilidad de cada posible palabra clave transmitida aumenta exponencialmente con${\displaystyle N}$Por lo tanto, un decodificador óptimo de este tipo se vuelve rápidamente inviable.

En su tesis doctoral , Dave Forney demostró que los códigos concatenados podían utilizarse para lograr probabilidades de error que disminuyen exponencialmente en todas las velocidades de datos inferiores a la capacidad, con una complejidad de decodificación que aumenta únicamente de forma polinómica con la longitud del bloque de código.

Sea C _un código [ n , k , d ], es decir, un código de bloques de longitud n , dimensión k , distancia de Hamming mínima d , y tasa r = k / n , sobre un alfabeto A :

${\displaystyle C_{in}:A^{k}\rightarrow A^{n}}$

Sea C un código [ N , K , _D ] sobre un alfabeto B con | B | = | A | ^k símbolos:

${\displaystyle C_{out}:B^{K}\rightarrow B^{N}}$

El código interno C _in toma una de las | A | ^k = | B | posibles entradas, la codifica en una n -tupla sobre A , la transmite y la decodifica en una de las | B | posibles salidas. Consideramos esto como un (super)canal que puede transmitir un símbolo del alfabeto B. Usamos este canal N veces para transmitir cada uno de los N símbolos en una palabra clave de C _out . La concatenación de C _out (como código externo) con C _in (como código interno) se denota como C _out.${\displaystyle \circ }$C _en , es por lo tanto un código de longitud Nn sobre el alfabeto A : ^{[ 1 ]}

${\displaystyle C_{out}\circ C_{in}:A^{kK}\rightarrow A^{nN}}$

Asigna cada mensaje de entrada m = ( m ₁ , m ₂ , ..., m _K ) a una palabra clave ( C _in ( m ' ₁ ), C _in ( m ' ₂ ), ..., C _in ( m ' _N )), donde ( m ' ₁ , m ' ₂ , ..., m ' _N ) = C _out ( m ₁ , m ₂ , ..., m _K ).

La idea clave de este enfoque es que si C _in se decodifica usando un enfoque de máxima verosimilitud (mostrando así una probabilidad de error que disminuye exponencialmente con el aumento de la longitud), y C _out es un código con longitud N = 2 ^nr que se puede decodificar en tiempo polinomial de N , entonces el código concatenado se puede decodificar en tiempo polinomial de su longitud combinada n 2 ^nr = O ( N ⋅log( N )) y muestra una probabilidad de error que disminuye exponencialmente, incluso si C _in tiene una complejidad de decodificación exponencial. ^{[ 1 ]} Esto se analiza con más detalle en la sección Decodificación de códigos concatenados .

En una generalización de la concatenación anterior, hay N posibles códigos internos C _{in , i} y el i -ésimo símbolo en una palabra clave de C _out se transmite a través del canal interno utilizando el i -ésimo código interno. Los códigos Justesen son ejemplos de códigos concatenados generalizados, donde el código externo es un código Reed-Solomon .

1. La distancia del código concatenado C _out${\displaystyle \circ }$C _en es al menos dD , es decir, es un código [ nN , kK , D ' ] con D ' ≥ dD .

Demostración: Consideremos dos mensajes diferentes m ¹ ≠ m ² ∈ B ^K . Sea Δ la distancia entre dos palabras clave. Entonces

${\displaystyle \Delta (C_{out}(m^{1}),C_{out}(m^{2}))\geq D.}$

Por lo tanto, hay al menos D posiciones en las que la secuencia de N símbolos de las palabras clave C _out ( m ¹ ) y C _out ( m ² ) difiere. Para estas posiciones, denotadas i , tenemos

${\displaystyle \Delta (C_{in}(C_{out}(m^{1})_{i}),C_{in}(C_{out}(m^{2})_{i}))\geq d.}$

En consecuencia, hay al menos d ⋅ D posiciones en la secuencia de n ⋅ N símbolos tomados del alfabeto A en las que las dos palabras clave difieren y, por lo tanto,

${\displaystyle \Delta (C_{in}(C_{out}(m^{1})),C_{in}(C_{out}(m^{2})))\geq dD.}$

2. Si C _out y C _in son códigos de bloque lineales , entonces C _out${\displaystyle \circ }$C _también es un código de bloques lineal.

Esta propiedad se puede demostrar fácilmente basándose en la idea de definir una matriz generadora para el código concatenado en términos de las matrices generadoras de C _out y C _in .

Un concepto natural para un algoritmo de decodificación de códigos concatenados es decodificar primero el código interno y luego el externo. Para que el algoritmo sea práctico, debe tener una complejidad temporal polinómica con respecto a la longitud del bloque final. Supongamos que existe un algoritmo de decodificación único con complejidad temporal polinómica para el código externo. Ahora debemos encontrar un algoritmo de decodificación con complejidad temporal polinómica para el código interno. Se entiende que la complejidad temporal polinómica aquí significa que el tiempo de ejecución es polinómico con respecto a la longitud del bloque final. La idea principal es que si la longitud del bloque interno se selecciona de forma logarítmica con respecto al tamaño del código externo, entonces el algoritmo de decodificación para el código interno puede ejecutarse en un tiempo exponencial con respecto a la longitud del bloque interno, y por lo tanto podemos usar un decodificador de máxima verosimilitud (MLD) óptimo con complejidad temporal exponencial para el código interno.

En detalle, sea la entrada al decodificador el vector y = ( y ₁ , ..., y _N ) ∈ ( A ⁿ ) ^N . Entonces, el algoritmo de decodificación es un proceso de dos pasos:

1. Utilice el MLD del código interno C _in para reconstruir un conjunto de palabras de código interno y ' = ( y ' ₁ , ..., y ' _N ), con y ' _i = MLD _{C in} ( y _i ), 1 ≤ i ≤ N .
2. Ejecuta el algoritmo de decodificación único para C _en y ' .

Ahora bien, la complejidad temporal del primer paso es O ( N ⋅ exp( n )), donde n = O (log( N )) es la longitud del bloque interno. En otras palabras, es N ^{O (1)} (es decir, tiempo polinomial) en términos de la longitud del bloque externo N. Dado que se supone que el algoritmo de decodificación externo en el paso dos se ejecuta en tiempo polinomial, la complejidad del algoritmo de decodificación general también es polinomial.

Aunque ya se había implementado un esquema de concatenación simple para la misión orbital Mariner a Marte en 1971, ^{[ 5 ]} los códigos concatenados comenzaron a usarse regularmente para la comunicación en el espacio profundo con el programa Voyager , que lanzó dos sondas espaciales en 1977. ^{[ 6 ]} Desde entonces, los códigos concatenados se convirtieron en el método principal para la codificación de corrección de errores eficiente, y lo siguieron siendo al menos hasta la invención de los códigos turbo y los códigos LDPC . ^{[ 5 ] [ 6 ]}

Normalmente, el código interno no es un código de bloques, sino un código convolucional decodificado por Viterbi de decisión suave con una longitud de restricción corta. ^{[ 7 ]} Para el código externo, se utiliza un código de bloques de decisión dura más largo, frecuentemente un código Reed-Solomon con símbolos de ocho bits. ^{[ 1 ] [ 5 ]} El mayor tamaño del símbolo hace que el código externo sea más robusto a las ráfagas de errores que pueden ocurrir debido a las deficiencias del canal, y también porque la salida errónea del propio código convolucional es en ráfagas. ^{[ 1 ] [ 5 ]} Generalmente se agrega una capa de entrelazado entre los dos códigos para distribuir las ráfagas de errores en un rango más amplio. ^{[ 5 ]}

La combinación de un código convolucional Viterbi interno con un código Reed-Solomon externo (conocido como código RSV) se utilizó por primera vez en la Voyager 2 , ^{[ 5 ] [ 8 ]} y se convirtió en una construcción popular tanto dentro como fuera del sector espacial. Todavía se utiliza notablemente hoy en día para comunicaciones por satélite , como el estándar de transmisión de televisión digital DVB-S . ^{[ 9 ]}

En un sentido más amplio, cualquier combinación (serie) de dos o más códigos puede denominarse código concatenado. Por ejemplo, en el estándar DVB-S2 , un código LDPC de alta eficiencia se combina con un código externo algebraico para eliminar cualquier error persistente que quede del código LDPC interno debido a su umbral de error inherente . ^{[ 10 ]}

En el disco compacto (CD) también se utiliza un esquema de concatenación simple, donde una capa de intercalación entre dos códigos Reed-Solomon de diferentes tamaños distribuye los errores entre varios bloques.

La descripción anterior se refiere a lo que ahora se denomina código concatenado en serie. Los códigos turbo , descritos por primera vez en 1993, implementaban una concatenación paralela de dos códigos convolucionales, con un entrelazador entre ellos y un decodificador iterativo que intercambiaba información entre los códigos. ^{[ 6 ]} Este diseño ofrece un mejor rendimiento que cualquier código concatenado concebido anteriormente.

Sin embargo, un aspecto clave de los códigos turbo es su enfoque de decodificación iterativa. La decodificación iterativa también se aplica ahora a las concatenaciones seriales para lograr mayores ganancias de codificación, como en los códigos convolucionales concatenados serialmente (SCCC). Una forma temprana de decodificación iterativa se implementó con dos a cinco iteraciones en el "código Galileo" de la sonda espacial Galileo . ^{[ 5 ]}

• Gilbert-Varshamov vinculado
• Código Justesen
• Singleton
• Zyablov atado

• Shu Lin; Daniel J. Costello Jr. (1983). Codificación de control de errores: Fundamentos y aplicaciones . Prentice Hall . págs. 278-280 . ISBN  978-0-13-283796-5.
• FJ MacWilliams ; NJA Sloane (1977). La teoría de los códigos correctores de errores . North-Holland. págs. 307–316 . ISBN  978-0-444-85193-2.

• Dave Forney (ed.). "Códigos concatenados" . Scholarpedia .
• Apuntes de clase de la Universidad de Buffalo sobre teoría de la codificación – Dr. Atri Rudra