Código de corrección de errores concatenado

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 una probabilidad de error exponencialmente decreciente con una longitud de bloque creciente y una complejidad de decodificación de tiempo polinomial . ^[1] Los códigos concatenados se utilizaron 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 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 determinada.

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 inferiores a un cierto umbral , denominado 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 bloque del esquema de codificación llega 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 dicho decodificador óptimo rápidamente se vuelve inviable.${\displaystyle R}$${\displaystyle C}$${\displaystyle N}$${\displaystyle N}$

En su tesis doctoral , Dave Forney demostró que los códigos concatenados podrían usarse para lograr probabilidades de error decrecientes exponencialmente en todas las velocidades de datos inferiores a la capacidad, con una complejidad de decodificación que aumenta solo polinomialmente con la longitud del bloque de código.

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 velocidad r = k / n , sobre un alfabeto A :

El código interno C _en toma uno de | un | ^k = | B | posibles entradas, codifica en una n -tupla sobre A , transmite y decodifica en una de | B | salidas posibles. Consideramos esto como un (súper) 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 Cout _. La concatenación de C _out (como código externo) con C _in (como código interno), denominada C _out∘ C _in , es pues un código de longitud Nn sobre el alfabeto A : ^[1]

Representación esquemática de un código concatenado basado en un código interno y un código externo.

Esta es una representación pictórica de una concatenación de códigos y, en particular, el código Reed-Solomon con n=q=4 y k=2 se usa como código externo y el código Hadamard con n=q y k=log q es utilizado como el código interno. En general, el código concatenado es un -código.${\displaystyle [q^{2},k\log q]}$