En informática , telecomunicaciones , teoría de la información y teoría de la codificación , la corrección de errores directa ( FEC ) o codificación de canales [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 ruidosos o poco confiables .
La idea central es que el remitente codifique el mensaje de forma redundante , generalmente 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 sólo detectar errores que pueden ocurrir en cualquier parte del mensaje, sino que a menudo corrige un número limitado de errores. Por lo tanto, es posible que no sea necesario un canal inverso para solicitar la retransmisión. El costo es un ancho de banda de canal directo mayor y fijo.
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]
FEC se puede aplicar en situaciones donde las retransmisiones son costosas o imposibles, como enlaces de comunicación unidireccionales o cuando se transmite a múltiples receptores en multidifusión . Las conexiones de larga latencia también se benefician; En el caso de un satélite que orbita alrededor de Urano , la retransmisión debida a errores puede generar un retraso de cinco horas. FEC también se usa 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. Para este último, FEC es una parte integral de la conversión inicial de analógico a digital en el receptor. El decodificador Viterbi implementa un algoritmo de decisión suave para demodular datos digitales a partir de una señal analógica corrompida por ruido. Muchos decodificadores FEC también pueden generar una señal de tasa de error de bits (BER) que puede usarse como retroalimentación para ajustar la electrónica de recepción analógica.
La información FEC se agrega a dispositivos de almacenamiento masivo (magnéticos, ópticos y de estado sólido/flash) para permitir la recuperación de datos corruptos, y se utiliza como memoria de computadora ECC en sistemas que requieren disposiciones especiales para la 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 una mayor redundancia que debe transmitirse utilizando el ancho de banda disponible, lo que reduce la tasa de bits efectiva al tiempo que mejora la relación señal-ruido efectiva recibida . El teorema de codificación de canales ruidosos 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 a la velocidad de transferencia de información máxima teórica de un canal con un nivel de ruido base determinado. Sin embargo, la prueba no es constructiva y, por lo tanto, no proporciona información sobre cómo desarrollar una capacidad para lograr código. 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 un marco de longitud infinita.
ECC se logra agregando redundancia a la información transmitida mediante un algoritmo. Un bit redundante puede ser una función complicada de muchos bits de información originales. La información original puede aparecer o no literalmente en la salida codificada; Los códigos que incluyen la entrada no modificada en la salida son sistemáticos , mientras que los que no lo hacen no son 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 puede ver 8 versiones de la salida; consulte la tabla a continuación.
Esto permite corregir un error en cualquiera de las tres muestras mediante "voto mayoritario" o "votación democrática". La capacidad correctora de este ECC es:
Aunque es fácil de implementar y ampliamente utilizada, esta triple redundancia modular es una ECC relativamente ineficiente. Los mejores códigos ECC normalmente examinan 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 ECC funciona mediante "promediado de 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 que los datos de usuario originales se extraigan de otros símbolos recibidos no corrompidos que también dependen de los mismos datos de 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 no funcionan en absoluto si la tasa de error de bits es cada vez peor. Sin embargo, algunos sistemas se adaptan a las condiciones de error del canal dadas: algunos casos 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 aumenta demasiado; La modulación y codificación adaptativa utiliza 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 códigos de bloque y códigos convolucionales .
Existen muchos tipos de códigos de bloqueo; La codificación Reed-Solomon destaca por su uso generalizado en discos compactos , DVD y unidades de disco duro . Otros ejemplos de códigos de bloques clásicos incluyen los códigos Golay , BCH , paridad multidimensional y Hamming .
Hamming ECC se utiliza comúnmente 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. La NAND de celda multinivel (MLC) más densa puede utilizar ECC de corrección de múltiples bits, como BCH o Reed-Solomon. [7] [8] NOR Flash normalmente no utiliza ninguna corrección de errores. [7]
Los códigos de bloque clásicos generalmente se decodifican utilizando algoritmos de decisión estricta , [9] lo que significa que para cada señal de entrada y salida se toma una decisión estricta si corresponde a un bit uno o cero. Por el contrario, los códigos convolucionales normalmente se decodifican utilizando algoritmos de decisión suave como los algoritmos de 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 dura.
Casi todos los códigos de bloques clásicos aplican las propiedades algebraicas de campos finitos . De ahí que los códigos de bloques clásicos a menudo se denominen códigos algebraicos.
A diferencia de los códigos de bloque clásicos que a menudo especifican una capacidad de detección o corrección de errores, muchos códigos de bloque modernos, como los códigos LDPC, carecen de tales 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 corrigen sólo los cambios de bits, pero no las inserciones o eliminaciones de bits. En esta configuración, la distancia de Hamming es la forma adecuada de medir la tasa de error de bits . Algunos códigos de corrección de errores directos están diseñados para corregir inserciones y eliminaciones de bits, como códigos de marcador y códigos de marca de agua. La distancia de Levenshtein es una forma más apropiada de medir la tasa de error de bits cuando se utilizan dichos códigos. [10]
El principio fundamental de ECC es agregar bits redundantes para ayudar al decodificador a descubrir el verdadero mensaje codificado por el transmisor. La velocidad de código 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 código es, por tanto, un número real. Una tasa de código baja cercana a cero implica un código fuerte que utiliza muchos bits redundantes para lograr un buen rendimiento, mientras que una tasa de código grande 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 confiabilidad y velocidad de datos. [11] En un extremo, un código fuerte (con una tasa de código baja) puede inducir un aumento importante en la SNR (relación señal-ruido) del receptor, disminuyendo la tasa de error de bits, a costa de reducir la tasa de datos efectiva. . En el otro extremo, al no utilizar ningún ECC (es decir, una tasa de código igual a 1), se utiliza el canal completo 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 una ECC que tenga una tasa de error de decodificación insignificante? Esta pregunta fue respondida por Claude Shannon con su segundo teorema, que dice que la capacidad del canal es la velocidad de bits máxima alcanzable por cualquier ECC cuya tasa de error tienda 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 propuesto por el trabajo de Shannon inspiró un largo viaje en el diseño de ECC que puedan acercarse al límite máximo de rendimiento. Actualmente, varios códigos pueden alcanzar casi el límite de Shannon. Sin embargo, la capacidad para lograr ECC suele ser extremadamente compleja de implementar.
Los ECC más populares tienen un equilibrio entre rendimiento y complejidad computacional. Por lo general, sus parámetros proporcionan una variedad de velocidades de código posibles, 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 al mismo tiempo minimizar el impacto en la velocidad 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 coste de energía 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 limitada 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" cualquier error cometido por el decodificador convolucional. La decodificación de un solo paso 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 altamente eficientes elaborados a partir de muchos códigos de verificación de paridad única (SPC). Pueden proporcionar un rendimiento muy cercano a la capacidad del canal (el máximo teórico) utilizando un enfoque de decodificación de decisión suave iterada, con una complejidad de tiempo lineal en términos de la longitud de su 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 decodificador y la introducción de los códigos Reed-Solomon , fueron ignorados en su mayoría hasta la década de 1990.
Los códigos LDPC se utilizan ahora en muchos estándares recientes de comunicación de alta velocidad, como DVB-S2 (Difusión de vídeo 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 a través de 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 (ver códigos fuente ).
La codificación turbo es un esquema iterado de decodificación suave que combina dos o más códigos convolucionales relativamente simples y un entrelazador para producir un código de bloque que puede funcionar dentro de una fracción de un decibelio del límite de Shannon . Son anteriores 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 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 lo venden Verizon Wireless , Sprint y otros operadores (el nombre comercial de Verizon para 1xEV-DO es Broadband Access , los nombres comerciales de Sprint para consumidores y empresas para 1xEV-DO son Power Vision y Mobile). Banda Ancha , respectivamente).
A veces sólo es necesario decodificar bits individuales del mensaje, o comprobar si una señal determinada es una palabra en clave, y hacerlo sin mirar la señal completa. Esto puede tener sentido en un entorno de transmisión por secuencias, donde las palabras en clave son demasiado grandes para ser descodificadas de forma clásica con la suficiente rapidez y donde por ahora sólo interesan unos pocos fragmentos del mensaje. 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 comprobables probabilísticamente .
Los códigos decodificables localmente son códigos de corrección de errores para los cuales bits individuales del mensaje pueden recuperarse probabilísticamente con solo observar un número pequeño (digamos constante) de posiciones de una palabra clave, incluso después de que la palabra clave se haya corrompido en alguna fracción constante de posiciones. Los códigos comprobables localmente son códigos de corrección de errores para los cuales se puede verificar probabilísticamente si una señal está cerca de una palabra de código mirando solo un pequeño número de posiciones de la señal.
No todos los códigos de prueba se decodifican y prueban localmente
No todos los códigos decodificables localmente (LDC) son códigos comprobables localmente (LTC) [15] ni los códigos corregibles localmente (LCC), [16] Los LCC de consulta q están limitados exponencialmente [17] [18], mientras que los PMA pueden tener longitudes subexponenciales . [19] [20]
El entrelazado se utiliza con frecuencia en sistemas de almacenamiento y comunicación digital para mejorar el rendimiento de los códigos de corrección de errores directos. Muchos canales de comunicación no carecen de memoria: los errores suelen ocurrir en ráfagas y no de forma independiente. Si el número de errores dentro de una palabra de código excede la capacidad del código de corrección de errores, no podrá recuperar la palabra de código original. El entrelazado alivia este problema al mezclar los símbolos fuente en varias palabras de código, creando así una distribución más uniforme de 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 códigos turbo y códigos LDPC , normalmente 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 el decodificador; El intercalador se elige para evitar ciclos cortos.
Los diseños de intercaladores incluyen:
En sistemas de comunicación de múltiples portadoras , 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: aaaabbbbccccdddeeeeffffggggTransmisión con error de ráfaga: aaaabbbbccc____deeeeffffgggg
Aquí, cada grupo de la misma letra representa una palabra clave de corrección de errores de un bit y 4 bits. La palabra clave cccc se modifica en un bit y se puede corregir, pero la palabra clave dddd se modifica en tres bits, por lo que no se puede decodificar en absoluto o puede que se decodifica incorrectamente .
Con intercalado :
Palabras de código sin errores: aaaabbbbccccddddeeeeffffggggIntercalado: abcdefgabcdefgabcdefgabcdefgTransmisión con error de ráfaga: abcdefgabcd____bcdefgabcdefgPalabras de código recibidas después del desintercalado: aa_abbbbccccdddde_eef_ffg_gg
En cada una de las palabras en clave "aaaa", "eeee", "ffff" y "gggg", sólo se modifica 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: ThisIsAnExampleOfInterleavingFrase recibida con un error de ráfaga: ThisIs______pleOfInterleaving
El término "Un ejemplo" resulta en su mayor parte ininteligible y difícil de corregir.
Con intercalado :
Oración transmitida: ThisIsAnExampleOfInterleaving...Transmisión sin errores: TIEpfeaghsxlIrv.iAaenli.snmOten.Frase recibida con un error de ráfaga: TIEpfe______Irv.iAaenli.snmOten.Frase recibida después del desintercalado: T_isI_AnE_amp_eOfInterle_vin_...
Ninguna palabra se pierde por completo y las letras que faltan se pueden recuperar con un mínimo de conjeturas.
El uso de técnicas de entrelazado aumenta el retraso total. Esto se debe a que se debe recibir todo el bloque entrelazado antes de que se puedan decodificar los paquetes. [29] También los entrelazadores ocultan la estructura de los errores; Sin un entrelazador, los algoritmos de decodificación más avanzados pueden aprovechar la estructura de error y lograr una comunicación más confiable que un decodificador más simple combinado con un entrelazador [ cita necesaria ] . Un ejemplo de tal algoritmo se basa en estructuras de redes neuronales [30] .
Simular el comportamiento de los códigos de corrección de errores (ECC) en el software es una práctica común 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 a radio en la nube (C-RAN) en un contexto de radio definida por software (SDR) . La idea es utilizar directamente software ECC en las comunicaciones. Por ejemplo, en 5G, los ECC de software podrían ubicarse en la nube y las antenas conectarse a estos recursos informáticos: mejorando de esta manera la flexibilidad de la red de comunicación y, eventualmente, aumentando la eficiencia energética del sistema.
En este contexto, hay varios programas de código abierto disponibles que se enumeran a continuación (no exhaustivos).
Cómo funcionan los códigos de corrección de errores de reenvío]
Tanto el algoritmo Reed-Solomon como el algoritmo BCH son opciones ECC comunes para flash MLC NAND. ... Los códigos de bloque basados en Hamming son el ECC más utilizado para SLC... tanto Reed-Solomon como BCH son capaces de manejar múltiples errores y se utilizan ampliamente en flash MLC.
Para SLC, es suficiente un código con un umbral de corrección de 1. t=4 requerido... para MLC.
{{cite book}}: |journal=ignorado ( ayuda )