En informática , telecomunicaciones , teoría de la información y teoría de codificación , la corrección de errores hacia adelante ( FEC ) o codificación de canal [1] [2] [3] es una técnica utilizada para controlar errores en la transmisión de datos a través de canales de comunicación poco confiables o ruidosos .
La idea central es que el remitente codifica el mensaje de forma redundante , la mayoría de las veces mediante el uso de un código de corrección de errores o código de corrección de errores ( ECC ). [4] [5] La redundancia permite al receptor no solo detectar errores que puedan ocurrir en cualquier parte del mensaje, sino que a menudo corrige un número limitado de errores. Por lo tanto, puede que no sea necesario un canal inverso para solicitar la retransmisión. El costo es un ancho de banda de canal directo fijo y más alto.
El matemático estadounidense Richard Hamming fue pionero en este campo en la década de 1940 e inventó el primer código de corrección de errores en 1950: el código Hamming (7,4) . [5]
La FEC se puede aplicar en situaciones donde las retransmisiones son costosas o imposibles, como en enlaces de comunicación unidireccionales o cuando se transmite a múltiples receptores en multidifusión .
Las conexiones con latencia prolongada también se benefician; en el caso de satélites que orbitan planetas distantes, la retransmisión debido a errores crearía un retraso de varias horas. La FEC también se utiliza ampliamente en módems y redes celulares .
El procesamiento FEC en un receptor se puede aplicar a un flujo de bits digitales o en la demodulación de una portadora modulada digitalmente. En este último caso, el FEC es una parte integral de la conversión analógica a digital inicial en el receptor. El decodificador Viterbi implementa un algoritmo de decisión suave para demodular datos digitales de una señal analógica alterada por ruido. Muchos decodificadores FEC también pueden generar una señal de tasa de error de bit (BER) que se puede utilizar como retroalimentación para ajustar con precisión la electrónica de recepción analógica.
La información FEC se agrega a dispositivos de almacenamiento masivo (magnético, óptico y de estado sólido/basados en flash) para permitir la recuperación de datos dañados y se utiliza como memoria de computadora ECC en sistemas que requieren disposiciones especiales para mayor confiabilidad.
La proporción máxima de errores o bits faltantes que se pueden corregir está determinada por el diseño del ECC, por lo que diferentes códigos de corrección de errores directos son adecuados para diferentes condiciones. En general, un código más fuerte induce más redundancia que necesita ser transmitida utilizando el ancho de banda disponible, lo que reduce la tasa de bits efectiva mientras mejora la relación señal-ruido efectiva recibida . El teorema de codificación de canal ruidoso de Claude Shannon se puede utilizar para calcular el ancho de banda de comunicación máximo alcanzable para una probabilidad de error máxima aceptable dada. Esto establece límites en la tasa de transferencia de información máxima teórica de un canal con un nivel de ruido base dado. Sin embargo, la prueba no es constructiva y, por lo tanto, no brinda ninguna idea de cómo construir un código que logre capacidad. Después de años de investigación, algunos sistemas FEC avanzados como el código polar [3] se acercan mucho al máximo teórico dado por la capacidad del canal de Shannon bajo la hipótesis de una trama de longitud infinita.
La ECC se logra añadiendo redundancia a la información transmitida mediante un algoritmo. Un bit redundante puede ser una función complicada de muchos bits de información original. La información original puede aparecer o no literalmente en la salida codificada; los códigos que incluyen la entrada sin modificar en la salida son sistemáticos , mientras que los que no lo hacen son no sistemáticos .
Un ejemplo simplista de ECC es transmitir cada bit de datos 3 veces, lo que se conoce como código de repetición (3,1) . A través de un canal ruidoso, un receptor podría ver 8 versiones de la salida, consulte la tabla a continuación.
Esto permite corregir un error en cualquiera de las tres muestras mediante "votación mayoritaria" o "votación democrática". La capacidad de corrección de este ECC es:
Aunque es fácil de implementar y se utiliza ampliamente, esta redundancia modular triple es un código ECC relativamente ineficiente. Los códigos ECC mejores suelen examinar las últimas decenas o incluso los últimos cientos de bits recibidos previamente para determinar cómo decodificar el pequeño puñado de bits actual (normalmente en grupos de 2 a 8 bits).
Se podría decir que el ECC funciona "promediando el ruido"; dado que cada bit de datos afecta a muchos símbolos transmitidos, la corrupción de algunos símbolos por el ruido generalmente permite extraer los datos originales del usuario de los demás símbolos recibidos no corruptos que también dependen de los mismos datos del usuario.
La mayoría de los sistemas de telecomunicaciones utilizan un código de canal fijo diseñado para tolerar la tasa de error de bits esperada en el peor de los casos , y luego dejan de funcionar si la tasa de error de bits es aún peor. Sin embargo, algunos sistemas se adaptan a las condiciones de error de canal dadas: algunas instancias de solicitud de repetición automática híbrida utilizan un método ECC fijo siempre que el ECC pueda manejar la tasa de error, luego cambian a ARQ cuando la tasa de error se vuelve demasiado alta; la modulación y codificación adaptativas utilizan una variedad de tasas de ECC, agregando más bits de corrección de errores por paquete cuando hay tasas de error más altas en el canal, o eliminándolos cuando no son necesarios.
Las dos categorías principales de códigos ECC son los códigos de bloque y los códigos convolucionales .
Existen muchos tipos de códigos de bloque; la codificación Reed-Solomon es notable por su uso generalizado en discos compactos , DVD y unidades de disco duro . Otros ejemplos de códigos de bloque clásicos incluyen Golay , BCH , paridad multidimensional y códigos Hamming .
El código Hamming ECC se utiliza habitualmente para corregir errores de memoria flash NAND . [6] Esto proporciona corrección de errores de un solo bit y detección de errores de 2 bits. Los códigos Hamming solo son adecuados para NAND de celda de un solo nivel (SLC) más confiable. Las NAND de celda multinivel (MLC) más densas pueden utilizar ECC de corrección de múltiples bits como BCH o Reed–Solomon. [7] [8] La memoria flash NOR normalmente no utiliza ninguna corrección de errores. [7]
Los códigos de bloques clásicos suelen decodificarse mediante algoritmos de decisión estricta [9], lo que significa que para cada señal de entrada y salida se toma una decisión estricta sobre si corresponde a un bit 1 o 0. Por el contrario, los códigos convolucionales suelen decodificarse mediante algoritmos de decisión blanda como los algoritmos Viterbi, MAP o BCJR , que procesan señales analógicas (discretizadas) y que permiten un rendimiento de corrección de errores mucho mayor que la decodificación de decisión estricta.
Casi todos los códigos de bloques clásicos aplican las propiedades algebraicas de los cuerpos finitos . Por lo tanto, los códigos de bloques clásicos suelen denominarse códigos algebraicos.
A diferencia de los códigos de bloque clásicos, que suelen especificar una capacidad de detección o corrección de errores, muchos códigos de bloque modernos, como los códigos LDPC, carecen de dichas garantías. En cambio, los códigos modernos se evalúan en términos de sus tasas de error de bits.
La mayoría de los códigos de corrección de errores directos solo corrigen cambios de bits, pero no inserciones ni eliminaciones de bits. En este contexto, la distancia de Hamming es la forma adecuada de medir la tasa de errores de bits . Algunos códigos de corrección de errores directos están diseñados para corregir inserciones y eliminaciones de bits, como los códigos de marcadores y los códigos de marca de agua. La distancia de Levenshtein es una forma más adecuada de medir la tasa de errores de bits cuando se utilizan dichos códigos. [10]
El principio fundamental del ECC es añadir bits redundantes para ayudar al decodificador a descubrir el mensaje verdadero que fue codificado por el transmisor. La tasa de codificación de un sistema ECC determinado se define como la relación entre el número de bits de información y el número total de bits (es decir, información más bits de redundancia) en un paquete de comunicación determinado. La tasa de codificación es, por tanto, un número real. Una tasa de codificación baja, cercana a cero, implica un código fuerte que utiliza muchos bits redundantes para lograr un buen rendimiento, mientras que una tasa de codificación alta, cercana a 1, implica un código débil.
Los bits redundantes que protegen la información deben transferirse utilizando los mismos recursos de comunicación que intentan proteger. Esto provoca un equilibrio fundamental entre la fiabilidad y la velocidad de datos. [11] En un extremo, un código fuerte (con una tasa de código baja) puede inducir un aumento importante de la relación señal-ruido (SNR) del receptor, disminuyendo la tasa de errores de bits, a costa de reducir la tasa de datos efectiva. En el otro extremo, no utilizar ningún ECC (es decir, una tasa de código igual a 1) utiliza todo el canal para fines de transferencia de información, a costa de dejar los bits sin ninguna protección adicional.
Una pregunta interesante es la siguiente: ¿qué tan eficiente en términos de transferencia de información puede ser un ECC que tiene una tasa de error de decodificación despreciable? Esta pregunta fue respondida por Claude Shannon con su segundo teorema, que dice que la capacidad del canal es la tasa de bits máxima alcanzable por cualquier ECC cuya tasa de error tiende a cero: [12] Su prueba se basa en la codificación aleatoria gaussiana, que no es adecuada para aplicaciones del mundo real. El límite superior dado por el trabajo de Shannon inspiró un largo viaje en el diseño de ECC que pueden acercarse al límite de rendimiento máximo. Varios códigos actuales pueden alcanzar casi el límite de Shannon. Sin embargo, los ECC que logran capacidad suelen ser extremadamente complejos de implementar.
Los ECC más populares tienen un equilibrio entre el rendimiento y la complejidad computacional. Por lo general, sus parámetros proporcionan un rango de posibles tasas de código, que se pueden optimizar según el escenario. Por lo general, esta optimización se realiza para lograr una baja probabilidad de error de decodificación y minimizar el impacto en la tasa de datos. Otro criterio para optimizar la tasa de código es equilibrar la baja tasa de error y el número de retransmisiones con el costo energético de la comunicación. [13]
Los códigos de bloque clásicos (algebraicos) y los códigos convolucionales se combinan frecuentemente en esquemas de codificación concatenados en los que un código convolucional decodificado por Viterbi de longitud de restricción corta hace la mayor parte del trabajo y un código de bloque (generalmente Reed-Solomon) con un tamaño de símbolo y una longitud de bloque mayores "limpia" los errores cometidos por el decodificador convolucional. La decodificación de una sola pasada con esta familia de códigos de corrección de errores puede producir tasas de error muy bajas, pero para condiciones de transmisión de largo alcance (como el espacio profundo) se recomienda la decodificación iterativa.
Los códigos concatenados han sido una práctica estándar en las comunicaciones por satélite y en el espacio profundo desde que la Voyager 2 utilizó por primera vez la técnica en su encuentro con Urano en 1986. La nave Galileo utilizó códigos concatenados iterativos para compensar las condiciones de tasa de error muy alta causadas por tener una antena defectuosa.
Los códigos de verificación de paridad de baja densidad (LDPC) son una clase de códigos de bloque lineales de alta eficiencia formados a partir de muchos códigos de verificación de paridad simple (SPC). Pueden proporcionar un rendimiento muy cercano a la capacidad del canal (el máximo teórico) utilizando un enfoque de decodificación iterado de decisión suave, con una complejidad de tiempo lineal en términos de su longitud de bloque. Las implementaciones prácticas dependen en gran medida de la decodificación de los códigos SPC constituyentes en paralelo.
Los códigos LDPC fueron introducidos por primera vez por Robert G. Gallager en su tesis doctoral en 1960, pero debido al esfuerzo computacional en la implementación del codificador y el decodificador y la introducción de los códigos Reed-Solomon , fueron en su mayoría ignorados hasta la década de 1990.
Los códigos LDPC se utilizan ahora en muchos estándares de comunicación de alta velocidad recientes, como DVB-S2 (Transmisión de video digital - Satélite - Segunda generación), WiMAX ( estándar IEEE 802.16e para comunicaciones por microondas), LAN inalámbrica de alta velocidad ( IEEE 802.11n ), [14] 10GBase-T Ethernet (802.3an) y G.hn/G.9960 (estándar ITU-T para redes sobre líneas eléctricas, líneas telefónicas y cable coaxial). Otros códigos LDPC están estandarizados para estándares de comunicación inalámbrica dentro de 3GPP MBMS (consulte los códigos fuente ).
La codificación turbo es un esquema de decodificación suave iterado que combina dos o más códigos convolucionales relativamente simples y un entrelazador para producir un código de bloque que puede funcionar con una precisión de una fracción de decibel del límite de Shannon . Preceden a los códigos LDPC en términos de aplicación práctica y ahora ofrecen un rendimiento similar.
Una de las primeras aplicaciones comerciales de la codificación turbo fue la tecnología celular digital CDMA2000 1x (TIA IS-2000) desarrollada por Qualcomm y vendida por Verizon Wireless , Sprint y otros operadores. También se utiliza para la evolución de CDMA2000 1x específicamente para acceso a Internet, 1xEV-DO (TIA IS-856). Al igual que 1x, EV-DO fue desarrollado por Qualcomm y es vendido por Verizon Wireless , Sprint y otros operadores (el nombre de marketing de Verizon para 1xEV-DO es Broadband Access , los nombres de marketing de Sprint para consumidores y empresas son Power Vision y Mobile Broadband , respectivamente).
A veces, solo es necesario decodificar bits individuales del mensaje o verificar si una señal dada es una palabra de código, y hacerlo sin mirar la señal completa. Esto puede tener sentido en un entorno de transmisión, donde las palabras de código son demasiado grandes para ser decodificadas clásicamente con la suficiente rapidez y donde solo unos pocos bits del mensaje son de interés por ahora. Además, estos códigos se han convertido en una herramienta importante en la teoría de la complejidad computacional , por ejemplo, para el diseño de pruebas probabilísticamente comprobables .
Los códigos decodificables localmente son códigos de corrección de errores para los cuales se pueden recuperar de manera probabilística bits individuales del mensaje observando solo una pequeña cantidad (por ejemplo, constante) de posiciones de una palabra de código, incluso después de que la palabra de código se haya corrompido en una fracción constante de posiciones. Los códigos comprobables localmente son códigos de corrección de errores para los cuales se puede verificar de manera probabilística si una señal está cerca de una palabra de código observando solo una pequeña cantidad de posiciones de la señal.
No todos los códigos de prueba se decodifican y prueban localmente.
No todos los códigos localmente decodificables (LDC) son códigos localmente comprobables (LTC) [15] ni tampoco los códigos localmente corregibles (LCC), [16] los LCC de q-query están acotados exponencialmente [17] [18] mientras que los LDC pueden tener longitudes subexponenciales . [19] [20]
El entrelazado se utiliza con frecuencia en los sistemas de comunicación y almacenamiento digitales para mejorar el rendimiento de los códigos de corrección de errores de avance. Muchos canales de comunicación no carecen de memoria: los errores suelen producirse en ráfagas en lugar de de forma independiente. Si el número de errores dentro de una palabra de código supera la capacidad del código de corrección de errores, no puede recuperar la palabra de código original. El entrelazado alivia este problema al mezclar los símbolos de origen en varias palabras de código, creando así una distribución más uniforme de los errores. [21] Por lo tanto, el entrelazado se utiliza ampliamente para la corrección de errores en ráfagas .
El análisis de códigos iterados modernos, como los códigos turbo y los códigos LDPC , generalmente supone una distribución independiente de errores. [22] Por lo tanto, los sistemas que utilizan códigos LDPC suelen emplear un entrelazado adicional entre los símbolos dentro de una palabra de código. [23]
Para los códigos turbo, un intercalador es un componente integral y su diseño adecuado es crucial para un buen rendimiento. [21] [24] El algoritmo de decodificación iterativa funciona mejor cuando no hay ciclos cortos en el gráfico de factores que representa al decodificador; el intercalador se elige para evitar ciclos cortos.
Los diseños de intercaladores incluyen:
En sistemas de comunicación multiportadora , se puede emplear el entrelazado entre portadoras para proporcionar diversidad de frecuencia , por ejemplo, para mitigar el desvanecimiento selectivo de frecuencia o la interferencia de banda estrecha. [28]
Transmisión sin entrelazado :
Mensaje sin errores: aaaabbbbccccddddeeeeffffggggTransmisión con un error de ráfaga: aaaabbbbccc____deeeeffffgggg
Aquí, cada grupo de la misma letra representa una palabra de código de corrección de errores de un bit y 4 bits. La palabra de código cccc se modifica en un bit y se puede corregir, pero la palabra de código dddd se modifica en tres bits, por lo que no se puede decodificar en absoluto o se puede decodificar de forma incorrecta .
Con intercalado :
Palabras de código sin errores: aaaabbbbccccddddeeeeffffggggIntercalado: abcdefgabcdefgabcdefgabcdefgTransmisión con un error de ráfaga: abcdefgabcd____bcdefgabcdefgPalabras de código recibidas después del desentrelazado: aa_abbbbccccdddde_eef_ffg_gg
En cada una de las palabras clave "aaaa", "eeee", "ffff" y "gggg", solo se altera un bit, por lo que el código de corrección de errores de un bit decodificará todo correctamente.
Transmisión sin entrelazado :
Oración original transmitida: ThisIsAnExampleOfInterleavingSe recibió una oración con un error de ráfaga: ThisIs______pleOfInterleaving
El término “UnEjemplo” resulta en su mayor parte ininteligible y difícil de corregir.
Con intercalado :
Oración transmitida: EsteEsUnEjemploDeIntercalado...Transmisión sin errores: TIEpfeaghsxlIrv.iAaenli.snmOten.Sentencia recibida con un error de ráfaga: TIEpfe______Irv.iAaenli.snmOten.Sentencia recibida tras desentrelazado: T_isI_AnE_amp_eOfInterle_vin_...
Ninguna palabra se pierde completamente y las letras que faltan se pueden recuperar con un mínimo de conjeturas.
El uso de técnicas de entrelazado aumenta el retardo total. Esto se debe a que se debe recibir todo el bloque entrelazado antes de que se puedan decodificar los paquetes. [29] Además, los entrelazadores ocultan la estructura de los errores; sin un entrelazador, los algoritmos de decodificación más avanzados pueden aprovechar la estructura de los errores y lograr una comunicación más confiable que un decodificador más simple combinado con un entrelazador [ cita requerida ] . Un ejemplo de dicho algoritmo se basa en las estructuras de redes neuronales [30] .
Simular el comportamiento de los códigos de corrección de errores (ECC) en software es una práctica habitual para diseñar, validar y mejorar los ECC. El próximo estándar inalámbrico 5G plantea una nueva gama de aplicaciones para los ECC de software: las redes de acceso por radio en la nube (C-RAN) en un contexto de radio definida por software (SDR) . La idea es utilizar directamente los ECC de software en las comunicaciones. Por ejemplo, en el 5G, los ECC de software podrían estar ubicados en la nube y las antenas conectadas a estos recursos informáticos: mejorando así la flexibilidad de la red de comunicaciones y, en última instancia, aumentando la eficiencia energética del sistema.
En este contexto, hay varios programas de código abierto disponibles que se enumeran a continuación (sin carácter exhaustivo).
Cómo funcionan los códigos de corrección de errores hacia adelante]
Tanto el algoritmo Reed-Solomon como el algoritmo BCH son opciones ECC comunes para la memoria flash NAND MLC. ... Los códigos de bloque basados en Hamming son los ECC más utilizados para SLC.... tanto Reed-Solomon como BCH pueden manejar múltiples errores y se utilizan ampliamente en la memoria flash MLC.
Para SLC, un código con un umbral de corrección de 1 es suficiente. Se requiere t=4... para MLC.
{{cite book}}: |journal=ignorado ( ayuda )