En la teoría de la 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 tanto una probabilidad de error exponencialmente decreciente con una longitud de bloque creciente como una complejidad de decodificación en tiempo polinómico . [1] Los códigos concatenados se utilizaron ampliamente en las comunicaciones espaciales en la década de 1970.
Fondo
El campo de la codificación de canales se ocupa de enviar un flujo de datos a la velocidad más alta posible a través de un canal de comunicaciones dado y luego decodificar los datos originales de manera confiable en el receptor, utilizando algoritmos de codificación y decodificación que son factibles de implementar en una tecnología dada.
El teorema de codificación de canales de Shannon muestra que en muchos canales comunes existen esquemas de codificación de canales que pueden transmitir datos de manera confiable a todas las velocidades. menos de un cierto umbral , llamada capacidad de canal del canal dado. De hecho, se puede hacer que la probabilidad de error de decodificación disminuya exponencialmente a medida que la longitud del bloquedel esquema de codificación va al infinito. Sin embargo, la complejidad de un esquema de decodificación óptimo ingenuo que simplemente calcula la probabilidad de cada posible palabra de código transmitida aumenta exponencialmente con, por lo que un decodificador óptimo de este tipo se vuelve rápidamente inviable.
En su tesis doctoral , Dave Forney mostró que los códigos concatenados podrían usarse para lograr probabilidades de error decrecientes exponencialmente en todas las velocidades de datos por debajo de la capacidad, con una complejidad de decodificación que aumenta solo polinomialmente con la longitud del bloque de código.
Descripción
Sea C in 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 :
Deje C a cabo sea un [ N , K , D code] sobre un alfabeto B con | B | = | A | k símbolos:
El código interno C en toma uno de | A | k = | B | posibles entradas, codifica en una n- tupla sobre A , transmite y decodifica en una de | B | posibles salidas. Consideramos que esto es un canal (super) 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), denotado C out ∘ C in , es por 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 fuera ( m 1 , m 2 , ..., 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 decreciente exponencialmente con una longitud creciente), y C out es un código con una longitud N = 2 nr que se puede decodificar en polinomio tiempo 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 decreciente 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 códigos internos posibles C in , iy el i -ésimo símbolo en una palabra de código de C out se transmite a través del canal interno usando 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 .
Propiedades
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 .
Prueba: Considérese dos mensajes diferentes m 1 ≠ m 2 ∈ B K . Sea Δ la distancia entre dos palabras de código. Luego
Por tanto, hay al menos D posiciones en las que difiere la secuencia de N símbolos de las palabras de código C out ( m 1 ) y C out ( m 2 ). Para estas posiciones, denotadas con i , tenemos
En consecuencia, hay al menos d ⋅ D posiciones en la secuencia de n ⋅ N símbolos tomados del alfabeto A en los que las dos palabras de código 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 mostrar fácilmente con base 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 .
Decodificación de códigos concatenados
Un concepto natural para un algoritmo de decodificación para 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 tiempo polinomial en la longitud del bloque final. Considere que existe un algoritmo de decodificación único en 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 la longitud del bloque interno se selecciona para que 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 el tiempo exponencial de la longitud del bloque interno y, por lo tanto, podemos usar un tiempo exponencial pero decodificador de máxima verosimilitud (MLD) óptimo para el código interno.
En detalle, dejar que la entrada al decodificador el vector y = ( y 1 , ..., y N ) ∈ ( A n ) N . Entonces, el algoritmo de decodificación es un proceso de dos pasos:
- Utilice el MLD del código interno C en para reconstruir un conjunto de palabras de código interno y '= ( y ' 1 , ..., y ' N ), con y ' i = MLD C en ( y i ), 1 ≤ i ≤ N .
- Ejecutar el algoritmo de decodificación única para C cabo en Y '.
Ahora, 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, de tiempo polinómico) en términos de la longitud de bloque exterior 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 es también en tiempo polinomial.
Observaciones
El algoritmo de decodificación descrito anteriormente se puede utilizar para corregir todos los errores hasta menos de dD / 4 en número. Usando decodificación de distancia mínima , el decodificador externo puede corregir todas las entradas y 'con menos de D / 2 símbolos y ' i en error. 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 debe haber sido un error, y para que el código externo falle, esto debe haber ocurrido para al menos D / 2 símbolos externos. En consecuencia, el número total de símbolos internos que deben recibirse incorrectamente para que falle el código concatenado 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 generalizado , desarrollado por Forney, se puede utilizar para corregir errores de hasta dD / 2. [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 usa decodificación de decisión suave . [3] [4]
Aplicaciones
Aunque ya se implementó un esquema de concatenación simple para la misión del orbitador Mariner Mars 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 una codificación de corrección de errores eficiente, y permanecieron así 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 bloque, sino un código convolucional de decisión suave decodificado por Viterbi con una longitud de restricción corta. [7] Para el código externo , se usa un código de bloque de decisión dura más largo, frecuentemente un código Reed-Solomon con símbolos de ocho bits. [1] [5] El tamaño de símbolo más grande hace que el código externo sea más robusto a las ráfagas de error que pueden ocurrir debido a las degradaciones 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 entrelazado entre los dos códigos para distribuir ráfagas de error en un rango más amplio. [5]
La combinación de un código convolucional interno de Viterbi con un código externo Reed-Solomon (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 (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 resistente que quede del código LDPC interno debido a su piso de error inherente . [10]
También se utiliza un esquema de concatenación simple en el disco compacto (CD), donde una capa entrelazada entre dos códigos Reed-Solomon de diferentes tamaños distribuye los errores en varios bloques.
Códigos turbo: un enfoque de concatenación en paralelo
La descripción anterior se proporciona para lo que ahora se denomina 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 intercalador entre los dos códigos y un decodificador iterativo que pasa información entre los códigos. [6] Este diseño tiene un mejor rendimiento que cualquier código concatenado previamente concebido.
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 dentro de los códigos convolucionales concatenados en serie (SCCC). Se implementó una forma temprana de decodificación iterada con dos a cinco iteraciones en el "código Galileo" de la sonda espacial Galileo . [5]
Ver también
- Código Justesen
- Zyablov obligado
- Límite de singleton
- Con destino a Gilbert-Varshamov
Referencias
- ↑ a b c d e G. D. Forney (1967). "Códigos concatenados". Cambridge, Massachusetts: MIT Press. Cite journal requiere
|journal=
( ayuda ) - ^ Forney, G. David (abril de 1966). "Decodificación de distancia mínima generalizada". Transacciones IEEE sobre teoría de la información . 12 (2): 125-131. doi : 10.1109 / TIT.1966.1053873 .
- ^ Yu, Christopher CH; Costello, Daniel J. (marzo de 1980). "Decodificación de distancia mínima generalizada para canales de salida Q ary". Transacciones IEEE sobre teoría de la información . 26 (2): 238–243. doi : 10.1109 / TIT.1980.1056148 .
- ^ Wu, Yingquan; Hadjicostis, Christoforos (enero de 2007). "Decodificación de decisión suave de códigos de bloques lineales mediante preprocesamiento y diversificación". Transacciones IEEE sobre teoría de la información . 53 (1): 387–393. doi : 10.1109 / tit.2006.887478 .
- ^ a b c d e f g Robert J. McEliece ; Laif Swanson (20 de agosto de 1993). "Códigos Reed-Solomon y la exploración del sistema solar". JPL. Cite journal requiere
|journal=
( ayuda ) - ^ a b c K. Andrews et al., El desarrollo de códigos Turbo y LDPC para aplicaciones en el espacio profundo , Actas del IEEE, vol. 95, No. 11, noviembre de 2007.
- ^ JP Odenwalder (1970). "Decodificación óptima de códigos convolucionales". UCLA , Departamento de Ciencia de Sistemas (disertación). Cite journal requiere
|journal=
( ayuda ) - ^ R. Ludwig, J. Taylor, Voyager Telecommunications Manual , JPL DESCANSO (Serie de resumen de diseño y rendimiento) , marzo de 2002.
- ^ Difusión de vídeo digital (DVB); Estructura de trama, codificación y modulación de canales para servicios por satélite de 11/12 GHz , ETSI EN 300 421, V1.1.2, agosto de 1997.
- ^ Difusión de vídeo digital (DVB); Estructura de trama de segunda generación, codificación de canales y sistemas de modulación para radiodifusión, servicios interactivos, recopilación de noticias y otras aplicaciones de satélite de banda ancha (DVB-S2) , ETSI EN 302 307, V1.2.1, abril de 2009.
Otras lecturas
- 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 de corrección de errores . Holanda Septentrional. págs. 307–316 . ISBN 978-0-444-85193-2.
enlaces externos
- Dave Forney (ed.). "Códigos concatenados" . Scholarpedia .
- Notas de la conferencia de la Universidad de Buffalo sobre teoría de la codificación - Dr. Atri Rudra