En teoría de codificación , los códigos concatenados forman una clase de códigos de corrección 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 tenga una probabilidad de error exponencialmente decreciente con el aumento de la longitud del bloque y la complejidad de decodificación en tiempo polinomial . [1] Los códigos concatenados se empezaron a utilizar ampliamente 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 luego decodificar los datos originales de manera confiable 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 muestra que en muchos canales comunes existen esquemas de codificación de canal que pueden transmitir datos de manera confiable a todas las velocidades menores a un cierto umbral , llamado capacidad de canal del canal dado. De hecho, la probabilidad de error de decodificación se puede hacer que disminuya exponencialmente a medida que la longitud de bloque 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 palabra de código transmitida posible aumenta exponencialmente con , por lo que un decodificador óptimo de este tipo rápidamente se vuelve inviable.
En su tesis doctoral, Dave Forney demostró que se pueden utilizar códigos concatenados para lograr probabilidades de error exponencialmente decrecientes en todas las velocidades de datos menores que la capacidad, con una complejidad de decodificación que aumenta solo polinomialmente con la longitud del bloque de código.
Sea C un código [ n , k , d ], es decir, un código de bloque de longitud n , dimensión k , distancia mínima de Hamming d y tasa r = k / n , sobre un alfabeto A :
Sea C un código [ N , K , D ] sobre un alfabeto B con | B |=| A | k símbolos:
El código interno C in toma una de | A | k = | B | posibles entradas, codifica en una n -tupla sobre A , transmite y decodifica en una de | 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 de código de C out . La concatenación de C out (como código externo) con C in (como código interno), denotada C out ∘ C in , es por lo tanto un código de longitud Nn sobre el alfabeto A : [1]
Asigna cada mensaje de entrada m = ( m 1 , m 2 , ..., m K ) a una palabra de código ( C in ( m ' 1 ), C in ( m ' 2 ), ..., C in ( m ' N )), donde ( m ' 1 , m ' 2 , ..., m ' N ) = C out ( m 1 , m 2 , ..., m K ).
La idea clave de este enfoque es que si C in se decodifica utilizando un enfoque de máxima verosimilitud (mostrando así una probabilidad de error exponencialmente decreciente con el aumento de la longitud), y C out es un código con longitud N = 2 nr que se puede decodificar en un tiempo polinomial de N , entonces el código concatenado se puede decodificar en un tiempo polinomial de su longitud combinada n 2 nr = O ( N ⋅log( N )) y muestra una probabilidad de error exponencialmente decreciente, 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 códigos internos posibles C in , i y el i -ésimo símbolo en una palabra de código 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 ∘ C in es al menos dD , es decir, es un código [ nN , kK , D '] con D ' ≥ dD .
Demostración: Consideremos dos mensajes diferentes m 1 ≠ m 2 ∈ B K . Sea Δ la distancia entre dos palabras clave. Entonces
Por lo tanto, hay al menos D posiciones en las que la secuencia de N símbolos de las palabras de código C out ( m 1 ) y C out ( m 2 ) difieren. Para estas posiciones, denotadas i , tenemos
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,
2. Si C out y C in son códigos de bloque lineales , entonces C out ∘ C in también es un código de bloque 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 código externo. Para que el algoritmo sea práctico, debe ser de tiempo polinomial en la longitud del bloque final. Considere que existe un algoritmo de decodificación único de tiempo polinomial para el código externo. Ahora tenemos que encontrar un algoritmo de decodificación de tiempo polinomial para el código interno. Se entiende que el tiempo de ejecución polinomial aquí significa que el tiempo de ejecución es polinomial en la longitud del bloque final. La idea principal es que si se selecciona que la longitud del bloque interno sea logarítmica en el tamaño del código externo, entonces el algoritmo de decodificación para el código interno puede ejecutarse en tiempo exponencial de la longitud del bloque interno y, por lo tanto, podemos usar un decodificador de máxima verosimilitud (MLD) de tiempo exponencial pero óptimo para el código interno.
En detalle, supongamos que la entrada al decodificador es el vector y = ( y 1 , ..., y N ) ∈ ( A n ) N . Entonces, el algoritmo de decodificación es un proceso de dos pasos:
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 . Como 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 tiempo polinomial.
El algoritmo de decodificación descrito anteriormente se puede utilizar para corregir todos los errores hasta un número inferior a dD /4. Utilizando la decodificación de distancia mínima , el decodificador externo puede corregir todas las entradas y ' con menos de D /2 símbolos y ' i erróneos. De manera similar, el código interno puede corregir de manera confiable una entrada y i si menos de d /2 símbolos internos son erróneos. Por lo tanto, para que un símbolo externo y ' i sea incorrecto después de la decodificación interna, al menos d /2 símbolos internos deben haber sido erróneos, y para que el código externo falle, esto debe haber sucedido para al menos D /2 símbolos externos. En consecuencia, el número total de símbolos internos que se deben recibir incorrectamente para que el código concatenado falle debe ser al menos d /2⋅ D /2 = dD /4.
El algoritmo también funciona si los códigos internos son diferentes, por ejemplo, para los códigos Justesen . El algoritmo de distancia mínima generalizada , desarrollado por Forney, se puede utilizar para corregir hasta dD /2 errores. [2] Utiliza información de borrado del código interno para mejorar el rendimiento del código externo y fue el primer ejemplo de un algoritmo que utiliza decodificación de decisión suave . [3] [4]
Aunque ya se había implementado un esquema de concatenación simple para la misión orbital de Marte Mariner de 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 caballo de batalla para la codificación de corrección de errores eficiente, y se mantuvieron así al menos hasta la invención de los códigos turbo y los códigos LDPC . [5] [6]
Por lo general, el código interno no es un código de bloque, sino un código convolucional decodificado por Viterbi con decisión suave con una longitud de restricción corta. [7] Para el código externo, se utiliza un código de bloque de decisión dura más largo, con frecuencia un código Reed-Solomon con símbolos de ocho bits. [1] [5] El mayor tamaño de símbolo hace que el código externo sea más robusto a las ráfagas de error que pueden ocurrir debido a deficiencias del canal, y también porque la salida errónea del código convolucional en sí es ráfaga. [1] [5] Por lo general, se agrega una capa de intercalado entre los dos códigos para distribuir las ráfagas de error en un rango más amplio. [5]
La combinación de un código convolucional de 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 hoy en día en 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 (en serie) de dos o más códigos puede denominarse código concatenado. Por ejemplo, dentro del estándar DVB-S2 , un código LDPC altamente eficiente se combina con un código externo algebraico para eliminar cualquier error resiliente que quede del código LDPC interno debido a su nivel de error inherente . [10]
En el disco compacto (CD) también se utiliza un esquema de concatenación simple, donde una capa de entrelazado entre dos códigos Reed-Solomon de diferentes tamaños distribuye los errores en varios bloques.
La descripción anterior se da para lo que ahora se llama un código concatenado en serie. Los códigos Turbo , como se describieron por primera vez en 1993, implementaron una concatenación paralela de dos códigos convolucionales, con un entrelazador entre los dos códigos y un decodificador iterativo que pasa información de ida y vuelta entre los códigos. [6] Este diseño tiene 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 iterada. La decodificación iterada ahora también se aplica a las concatenaciones en serie para lograr mayores ganancias de codificación, como en los códigos convolucionales concatenados en serie (SCCC). Una forma temprana de decodificación iterada se implementó con dos a cinco iteraciones en el "código Galileo" de la sonda espacial Galileo . [5]
![{\displaystyle [q^{2},k\log q]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4e2fb4112d1d36c2376a54887a9caf6d8793833)
{{cite journal}}: Requiere citar revista |journal=( ayuda ){{cite journal}}: Requiere citar revista |journal=( ayuda ){{cite journal}}: Requiere citar revista |journal=( ayuda )