Hispanopedia Wiki
Articulo de referencia

Código de corrección de errores

En informática , telecomunicaciones , teoría de la información y teoría de la codificación , la corrección de errores hacia adelante ( FEC ) o codificación de canal [ 1 ] es una...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , telecomunicaciones , teoría de la información y teoría de la codificación , la corrección de errores hacia adelante ( FEC ) o codificación de canal [ 1 ] es una técnica utilizada para controlar los errores en la transmisión de datos a través de canales de comunicación poco fiables o ruidosos .

La idea central es que el emisor codifica el mensaje de forma redundante , generalmente mediante un código de corrección de errores ( ECC ) . [ 2 ] [ 3 ] La redundancia permite al receptor no solo detectar errores que puedan ocurrir en cualquier parte del mensaje, sino también corregir un número limitado de ellos. Por lo tanto, puede que no sea necesario un canal inverso para solicitar la retransmisión. El costo es un ancho de banda fijo y mayor en el canal directo.

El matemático estadounidense Richard Hamming fue pionero en este campo en la década de 1940 e inventó el primer código corrector de errores en 1950: el código Hamming (7,4) . [ 3 ]

La corrección de errores hacia adelante (FEC) se puede aplicar en situaciones donde las retransmisiones son costosas o imposibles, como en enlaces de comunicación unidireccionales o al transmitir a múltiples receptores en multidifusión .

Las conexiones de alta latencia también se benefician; en el caso de satélites que orbitan planetas distantes, la retransmisión debida a errores generaría un retraso de varias horas. La corrección de errores hacia adelante (FEC) también se utiliza ampliamente en módems y redes celulares .

El procesamiento FEC en un receptor puede aplicarse a un flujo de bits digital o a la demodulación de una portadora modulada digitalmente. En este último caso, FEC es parte integral de la conversión analógica-digital inicial 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 utilizarse como retroalimentación para ajustar con precisión la electrónica de recepción analógica.

La información FEC se agrega a los 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 ECC en sistemas que requieren disposiciones especiales para garantizar la fiabilidad.

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 hacia adelante son adecuados para diferentes condiciones. En general, un código más robusto induce mayor redundancia que debe transmitirse utilizando el ancho de banda disponible, lo que reduce la tasa de bits efectiva a la vez que 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 para la tasa máxima teórica de transferencia de información de un canal con un nivel de ruido base dado. Sin embargo, la demostración no es constructiva y, por lo tanto, no proporciona información sobre cómo construir un código que alcance la capacidad. Después de años de investigación, algunos sistemas FEC avanzados como el código polar [ 4 ] se acercan mucho al máximo teórico (límite de Shannon) dado por la capacidad del canal de Shannon bajo la hipótesis de una trama de longitud infinita.

Método

La codificación de evolución (ECC) se logra agregando redundancia a la información transmitida mediante un algoritmo. Un bit redundante puede ser una función compleja de muchos bits de la información original. La información original puede o no aparecer 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 sencillo de ECC consiste en transmitir cada bit de datos tres 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 ocho versiones de la salida; véase 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:

  • hasta un bit de triplete con error, o
  • Se omiten hasta dos bits del triplete (casos no mostrados en la tabla).

Aunque sencilla de implementar y de uso generalizado, esta redundancia modular triple es un código ECC relativamente ineficiente. Los códigos ECC más avanzados suelen analizar las últimas decenas o incluso los últimos cientos de bits recibidos previamente para determinar cómo decodificar el pequeño conjunto de bits actual (normalmente en grupos de dos a ocho bits).

Formalismo simplificado

Formalmente, un código corrector de errores viene dado por su función de codificación ( inyectiva ) que asigna a cada palabra de un alfabeto finito una palabra única (una concatenación de letras) del alfabeto .F:Σ∗↪Δ∗{\displaystyle f:\Sigma ^{*}\hookrightarrow \Delta ^{*}}tú∈Σ∗=dmiF⋃norte∈norteΣnorte{\displaystyle u\in \Sigma ^{*}\;{\stackrel {\mathrm {def} }{=}}\;\textstyle \bigcup _{n\in \mathbb {N} }\Sigma ^{n}}Σ{\displaystyle \Sigma }w∈Δ∗=dmiF⋃norte∈norteΔnorte{\displaystyle w\in \Delta ^{*}\;{\stackrel {\mathrm {def} }{=}}\;\textstyle \bigcup _{n\in \mathbb {N} }\Delta ^{n}}Δ{\displaystyle \Delta }

Lo más común es que sea un homomorfismo en el sentido de que si es la concatenación de y , entonces tenemos lo siguiente: Esto implica que basta con definir para palabras de una sola letra . El rango de la función es el conjunto de palabras código. Las capacidades del código para detectar y corregir errores se pueden entender a partir de la distancia del código, que es la distancia de Hamming mínima que separa dos palabras código distintas cualesquiera. Un código con distancia puede detectar errores en bits siempre que , y entre esos errores detectados, el código puede corregir errores de bits siempre que .f{\displaystyle f}x1∗x2{\displaystyle x_{1}*x_{2}}x1{\displaystyle x_{1}}x2{\displaystyle x_{2}}f(u1∗u2)=f(u1)∗f(u2){\displaystyle f(u_{1}*u_{2})=f(u_{1})*f(u_{2})}f(σ){\displaystyle f(\sigma )}σ{\displaystyle \sigma }Im(f){\displaystyle \mathrm {Im} (f)}f{\displaystyle f}d=minw1,w2∈Im(f); w1≠w2dH(w1,w2){\displaystyle d=\min _{w_{1},w_{2}\in \mathrm {Im} (f);\ w_{1}\neq w_{2}}d_{H}(w_{1},w_{2})}d{\displaystyle d}k{\displaystyle k}k<d{\displaystyle k<d}l{\displaystyle l}2l<d{\displaystyle 2l<d}

Promediar el ruido para reducir los errores.

Se podría decir que la corrección de errores 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 a partir de los demás símbolos recibidos no corruptos que también dependen de los mismos datos del usuario.

  • Debido a este efecto de "agrupación de riesgos", los sistemas de comunicación digital que utilizan ECC tienden a funcionar bien por encima de una determinada relación señal/ruido mínima y no por debajo de ella.
  • Esta tendencia de todo o nada —el efecto de precipicio— se vuelve más pronunciada a medida que se utilizan códigos más robustos que se aproximan más al límite teórico de Shannon .
  • La intercalación de datos codificados con ECC puede reducir las propiedades de transmisión simultánea de todo o nada de los códigos ECC transmitidos cuando los errores del canal tienden a ocurrir en ráfagas. Sin embargo, este método tiene limitaciones; se recomienda su uso con datos de banda estrecha.

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 dejan de funcionar por completo si la tasa de error de bits es aún mayor. Sin embargo, algunos sistemas se adaptan a las condiciones de error del canal: algunas instancias de solicitud de repetición automática híbrida utilizan un método ECC fijo mientras el ECC pueda manejar la tasa de error, y luego cambian a ARQ cuando la tasa de error es demasiado alta; la modulación y codificación adaptativa utiliza una variedad de tasas 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.

Tipos

Un código de bloques (específicamente un código de Hamming ) donde los bits redundantes se agregan como un bloque al final del mensaje inicial.
Un código convolucional continuo donde se agregan continuamente bits redundantes a la estructura de la palabra clave.

Las dos categorías principales de códigos ECC son los códigos de bloque y los códigos convolucionales .

  • Los códigos de bloques funcionan con bloques (paquetes) de tamaño fijo de bits o símbolos de tamaño predeterminado. En general, los códigos de bloques prácticos se pueden decodificar en tiempo polinomial a la longitud de su bloque.
  • Los códigos convolucionales operan sobre secuencias de bits o símbolos de longitud arbitraria. Suelen decodificarse mediante el algoritmo de Viterbi , aunque a veces se utilizan otros. La decodificación de Viterbi permite una eficiencia de decodificación asintóticamente óptima a medida que aumenta la longitud de restricción del código convolucional, pero a costa de una complejidad que aumenta exponencialmente . Un código convolucional terminado también se denomina "código de bloque", ya que codifica un bloque de datos de entrada. Sin embargo, el tamaño del bloque de un código convolucional suele ser arbitrario, mientras que los códigos de bloque tienen un tamaño fijo determinado por sus características algebraicas. Entre los tipos de terminación para códigos convolucionales se incluyen el "cola de la cola" y el "vaciado de bits".

Los códigos de bloques clásicos se suelen decodificar mediante algoritmos de decisión rígida [ 5 ] , lo que significa que para cada señal de entrada y salida se toma una decisión definitiva sobre si corresponde a un bit uno o cero. En cambio, los códigos convolucionales se suelen decodificar mediante algoritmos de decisión flexible como los algoritmos Viterbi, MAP o BCJR , que procesan señales analógicas (discretizadas) y permiten un rendimiento de corrección de errores mucho mayor que la decodificación de decisión rígida.

Casi todos los códigos de bloques clásicos aplican las propiedades algebraicas de los cuerpos finitos . Por lo tanto, a los códigos de bloques clásicos se les suele llamar códigos algebraicos.

Códigos de bloques

Existen muchos tipos de códigos de bloques; el código Reed-Solomon destaca por su amplio uso en discos compactos , DVD y unidades de disco duro . Otros ejemplos de códigos de bloques clásicos incluyen Golay , BCH , paridad multidimensional y códigos Hamming .

El código ECC de Hamming se usa comúnmente para corregir errores de memoria ECC y de memoria flash NAND SLC temprana . [ 6 ] Esto proporciona corrección de errores de un bit y detección de errores de dos bits. Los códigos de Hamming solo son adecuados para NAND de celda de un nivel (SLC) más confiable. Las NAND de celda multinivel (MLC) más densas pueden usar ECC de corrección de múltiples bits como BCH , Reed-Solomon o LDPC . [ 7 ] [ 8 ] La memoria flash NOR normalmente no usa ninguna corrección de errores. [ 7 ]

Códigos blandos

Control de paridad de baja densidad (LDPC)

Los códigos de verificación de paridad de baja densidad (LDPC) son una clase de códigos de bloque lineales de alta eficiencia, compuestos por numerosos códigos de verificación de paridad simple (SPC). Mediante un enfoque de decodificación iterativa de decisión suave, pueden ofrecer un rendimiento muy cercano a la capacidad del canal (el máximo teórico), con una complejidad temporal lineal en función de la longitud de sus bloques. Las implementaciones prácticas dependen en gran medida de la decodificación en paralelo de los códigos SPC constituyentes.

Los códigos LDPC fueron presentados por primera vez por Robert G. Gallager en su tesis doctoral en 1960, pero debido al esfuerzo computacional que suponía implementar el codificador y el decodificador, y a la introducción de los códigos Reed-Solomon , fueron prácticamente 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 (Digital Video Broadcasting – Satellite – Second Generation), WiMAX ( estándar IEEE 802.16e para comunicaciones por microondas), High-Speed ​​Wireless LAN ( IEEE 802.11n ), [ 9 ] 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 fountain ).

Código turbo

La codificación turbo es un esquema de decodificación suave iterativo que combina dos o más códigos convolucionales relativamente simples y un entrelazador para producir un código de bloques cuyo rendimiento se acerca al límite de Shannon a una fracción de decibelio . Si bien es anterior a los códigos LDPC en términos de aplicación práctica, actualmente ofrece 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 comercializada por Verizon Wireless , Sprint y otros operadores. También se utiliza para la evolución de CDMA2000 1x, específicamente para el acceso a Internet, denominada 1xEV-DO (TIA IS-856). Al igual que 1x, EV-DO fue desarrollada por Qualcomm y comercializada por Verizon Wireless , Sprint y otros operadores (el nombre comercial de Verizon para 1xEV-DO es Broadband Access , mientras que los nombres comerciales de Sprint para consumidores y empresas son Power Vision y Mobile Broadband , respectivamente).

Descripción del rendimiento de un ECC

A diferencia de los códigos de bloques clásicos, que suelen especificar la capacidad de detectar o corregir errores, muchos códigos de bloques modernos, como los códigos LDPC, carecen de tales garantías. En cambio, los códigos modernos se evalúan en función de sus tasas de error de bits.

La mayoría de los códigos de corrección de errores hacia adelante solo corrigen las inversiones de bits, pero no las inserciones ni las eliminaciones de bits. En este caso, la distancia de Hamming es la forma adecuada de medir la tasa de error de bits . Algunos códigos de corrección de errores hacia adelante están diseñados para corregir inserciones y eliminaciones de bits, como los códigos de marcador y los 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 ]

Tasa de codificación y la relación entre fiabilidad y velocidad de datos.

El principio fundamental de la codificación de error de codificación (ECC) consiste en añadir bits redundantes para ayudar al decodificador a descifrar el mensaje original codificado por el transmisor. La tasa de codificación de un sistema ECC se define como la relación entre el número de bits de información y el número total de bits (es decir, bits de información más bits de redundancia) en un paquete de comunicación determinado. Por lo tanto, la tasa de codificación es un número real. Una tasa de codificación baja, cercana a cero, implica un código robusto 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 genera una disyuntiva fundamental entre fiabilidad y velocidad de datos. [ 11 ] En un extremo, un código robusto (con una tasa de codificación baja) puede inducir un aumento significativo en la relación señal/ruido (SNR) del receptor, disminuyendo la tasa de error de bits, a costa de reducir la velocidad de datos efectiva. En el otro extremo, no utilizar ningún código de corrección de errores (ECC) (es decir, una tasa de codificación igual a 1) utiliza todo el canal para la transferencia de información, a costa de dejar los bits sin protección adicional.

Una pregunta interesante es la siguiente: ¿cuán eficiente en términos de transferencia de información puede ser un ECC con una tasa de error de decodificación insignificante? Claude Shannon respondió a esta pregunta con su segundo teorema, que establece 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 demostración 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 camino 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 alcanzan la capacidad máxima suelen ser extremadamente complejos de implementar.

Los códigos ECC más populares presentan un equilibrio entre rendimiento y complejidad computacional. Generalmente, sus parámetros ofrecen un rango de tasas de codificación posibles, que pueden optimizarse según el escenario. Esta optimización suele realizarse para lograr una baja probabilidad de error de decodificación, minimizando al mismo tiempo el impacto en la tasa de datos. Otro criterio para optimizar la tasa de codificación es equilibrar una baja tasa de error y el número de retransmisiones con el coste energético de la comunicación. [ 13 ]

Decodificación y prueba local de códigos

En ocasiones, basta con decodificar bits individuales del mensaje o comprobar si una señal dada es una palabra clave, sin necesidad de analizar la señal completa. Esto resulta útil en entornos de transmisión continua, donde las palabras clave son demasiado extensas para ser decodificadas con la suficiente rapidez mediante métodos clásicos y donde, por el momento, solo interesan unos pocos bits 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 verificables probabilísticamente .

Los códigos decodificables localmente son códigos correctores de errores en los que se pueden recuperar probabilísticamente bits individuales del mensaje analizando solo un número pequeño (por ejemplo, constante) de posiciones de una palabra clave, incluso después de que esta se haya corrompido en una fracción constante de posiciones. Los códigos comprobables localmente son códigos correctores de errores en los que se puede verificar probabilísticamente si una señal se aproxima a una palabra clave analizando solo un número pequeño de posiciones de la señal.

No todos los códigos localmente decodificables (LDC) son códigos localmente comprobables (LTC) [ 14 ] ni códigos localmente corregibles (LCC) [ 15 ] los LCC de q-query están acotados exponencialmente [ 16 ] mientras que los LDC pueden tener longitudes subexponenciales . [ 17 ]

Mejorar el rendimiento

Concatenación (combinación)

Los códigos de bloques clásicos (algebraicos) y los códigos convolucionales se combinan frecuentemente en esquemas de codificación concatenada , donde un código convolucional decodificado mediante Viterbi con una longitud de restricción corta realiza la mayor parte del trabajo, y un código de bloques (generalmente Reed-Solomon) con un tamaño de símbolo y una longitud de bloque mayores corrige 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 generar tasas de error muy bajas, pero para condiciones de transmisión de largo alcance (como en el espacio profundo) se recomienda la decodificación iterativa.

Los códigos concatenados han sido una práctica habitual en las comunicaciones por satélite y en el espacio profundo desde que la Voyager 2 utilizó por primera vez esta técnica en su encuentro con Urano en 1986. La sonda Galileo empleó códigos concatenados iterativos para compensar la altísima tasa de error causada por el fallo de la antena.

Intercalación

Una breve ilustración de la idea de intercalación.

El entrelazado se utiliza frecuentemente en sistemas de comunicación y almacenamiento digital para mejorar el rendimiento de los códigos de corrección de errores hacia adelante. Muchos canales de comunicación no carecen de memoria: los errores suelen producirse en ráfagas en lugar 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, este no logra recuperar la palabra de código original. El entrelazado mitiga este problema redistribuyendo los símbolos fuente entre varias palabras de código, creando así una distribución más uniforme de los errores. [ 18 ] Por lo tanto, el entrelazado se utiliza ampliamente para la corrección de errores en ráfagas .

El análisis de los códigos iterados modernos, como los códigos turbo y los códigos LDPC , suele asumir una distribución independiente de errores. [ 19 ] 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. [ 20 ]

Para los códigos turbo, un entrelazador es un componente integral y su diseño adecuado es crucial para un buen rendimiento. [ 18 ] [ 21 ] El algoritmo de decodificación iterativa funciona mejor cuando no hay ciclos cortos en el grafo de factores que representa el decodificador; el entrelazador se elige para evitar ciclos cortos.

Los diseños de intercalación incluyen:

  • intercaladores rectangulares (o uniformes) (similares al método que utiliza factores de salto descrito anteriormente)
  • entrelazadores convolucionales
  • intercaladores aleatorios (donde el intercalador es una permutación aleatoria conocida)
  • Entrelazador aleatorio S (donde el entrelazador es una permutación aleatoria conocida con la restricción de que ningún símbolo de entrada dentro de una distancia S aparezca dentro de una distancia de S en la salida). [ 22 ]
  • un polinomio de permutación cuadrático (QPP) sin contención . [ 23 ] Un ejemplo de uso se encuentra en el estándar de telecomunicaciones móviles 3GPP Long Term Evolution . [ 24 ]

En los sistemas de comunicación multiportadora , se puede emplear el entrelazado entre portadoras para proporcionar diversidad de frecuencia , por ejemplo, para mitigar el desvanecimiento selectivo en frecuencia o la interferencia de banda estrecha. [ 25 ]

Ejemplo de intercalación

Transmisión sin intercalación :

Mensaje sin errores: aaaabbbbccccddddeeeeffffgggg Transmisió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 4 bits y 1 bit. 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 o no se puede decodificar en absoluto o podría decodificarse incorrectamente .

Con intercalación :

Palabras clave sin errores: aaaabbbbccccddddeeeeffffgggg Entrelazado: abcdefgabcdefgabcdefgabcdefg Transmisión con error de ráfaga: abcdefgabcd____bcdefgabcdefg Palabras clave 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 intercalación :

Oración original transmitida: ThisIsAnExampleOfInterleaving Oración recibida con error de ráfaga: ThisIs______pleOfInterleaving

El término " AnExample " termina siendo en su mayor parte ininteligible y difícil de corregir.

Con intercalación :

Oración transmitida: ThisIsAnExampleOfInterleaving... Transmisión sin errores: TIEpfeaghsxlIrv.iAaenli.snmOten. Oración recibida con un error de ráfaga: TIEpfe______Irv.iAaenli.snmOten. Oración recibida después del desentrelazado: 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.

Desventajas de la intercalación

El uso de técnicas de entrelazado aumenta el retardo total. Esto se debe a que se debe recibir el bloque entrelazado completo antes de que se puedan decodificar los paquetes. [ 26 ] 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 errores y lograr una comunicación más fiable que un decodificador más simple combinado con un entrelazador . Un ejemplo de dicho algoritmo se basa en estructuras de redes neuronales [ 27 ] .

Software para códigos de corrección de errores

La simulación del comportamiento de los códigos de corrección de errores (ECC) mediante software es una práctica común para diseñar, validar y mejorar dichos códigos. El próximo estándar inalámbrico 5G abre un nuevo abanico de aplicaciones para los ECC basados ​​en software: las redes de acceso de radio en la nube (C-RAN) en el contexto de la radio definida por software (SDR) . La idea es utilizar directamente los ECC basados ​​en software en las comunicaciones. Por ejemplo, en 5G, los ECC basados ​​en software podrían ubicarse en la nube y las antenas conectarse a estos recursos informáticos, mejorando así la flexibilidad de la red de comunicación y, en consecuencia, aumentando la eficiencia energética del sistema.

En este contexto, a continuación se enumeran varios programas de código abierto disponibles (lista no exhaustiva).

  • AFF3CT (A Fast Forward Error Correction Toolbox): una cadena de comunicación completa en C++ (con soporte para muchos códigos como Turbo, LDPC, códigos polares, etc.), muy rápida y especializada en codificación de canales (puede utilizarse como programa para simulaciones o como biblioteca para SDR).
  • IT++ : una biblioteca de C++ con clases y funciones para álgebra lineal, optimización numérica, procesamiento de señales, comunicaciones y estadística.
  • OpenAir : implementación (en C) de las especificaciones 3GPP relativas a las redes centrales de paquetes evolucionadas.

Lista de códigos de corrección de errores

En la tabla anterior, para un código corrector de errores de distancia de Hamming mínima , el número máximo de errores que el código puede detectar viene dado por mientras que el número máximo de errores que puede corregir viene dado por .d{\displaystyle d}d−1{\displaystyle d-1}⌊d−12⌋{\displaystyle \left\lfloor {\frac {d-1}{2}}\right\rfloor }

Véase también

Referencias

  1. ↑ Charles Wang; Dean Sklar; Diana Johnson (invierno de 2001–2002). "Codificación de corrección de errores hacia adelante" . Crosslink . 3 (1). The Aerospace Corporation. Archivado del original el 14 de marzo de 2012. Recuperado el 5 de marzo de 2006 .
  2. ↑ Glover, Neal; Dudley, Trent (1990). Diseño práctico de corrección de errores para ingenieros (Revisión 1.1, 2.ª ed.). CO, EE. UU.: Cirrus Logic . ISBN  0-927239-00-0.
  3. 1 2 Hamming, Richard Wesley (abril de 1950). "Códigos de detección y corrección de errores". Bell System Technical Journal . 29 (2). EE. UU.: AT&T : 147– 160. Bibcode : 1950BSTJ...29..147H . doi : 10.1002/j.1538-7305.1950.tb00463.x . hdl : 10945/46756 . S2CID 61141773 . 
  4. ↑ Maunder, Robert (2016). "Descripción general de la codificación de canales" .
  5. ↑ Baldi, M.; Chiaraluce, F. (2008). "Un esquema simple para la decodificación por propagación de creencias de códigos BCH y RS en transmisiones multimedia" . International Journal of Digital Multimedia Broadcasting . 2008 : 1–12 . doi : 10.1155/2008/957846 .
  6. ↑ "Códigos de Hamming para dispositivos de memoria flash NAND" Archivado el 21 de agosto de 2016 en Wayback Machine . EE Times-Asia. Aparentemente basado en "Nota técnica de Micron TN-29-08: Códigos de Hamming para dispositivos de memoria flash NAND" Archivado el 29 de agosto de 2017 en Wayback Machine . 2005. Ambos dicen: "El algoritmo de Hamming es un método aceptado por la industria para la detección y corrección de errores en muchas aplicaciones basadas en memoria flash NAND SLC".
  7. 1 2 "¿Qué tipos de ECC se deben usar en la memoria flash?" (PDF) . Spansion. 2011. Archivado del original (nota de aplicación) el 14 de junio de 2016. Tanto el algoritmo Reed-Solomon como el algoritmo BCH son opciones comunes de ECC 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.
  8. ↑ Jim Cooke (agosto de 2007). "Las verdades incómodas de la memoria flash NAND" (PDF) . pág. 28. Para SLC, un código con un umbral de corrección de 1 es suficiente. Se requiere t=4... para MLC. 
  9. ↑ Norma IEEE, sección 20.3.11.6 "802.11n-2009" Archivada el 3 de febrero de 2013 en Wayback Machine , IEEE, 29 de octubre de 2009, consultada el 21 de marzo de 2011.
  10. ↑ Shah, Gaurav; Molina, Andres; Blaze, Matt (2006). "Teclados y canales encubiertos" . USENIX . Recuperado el 20 de diciembre de 2018 .
  11. ↑ Tse, David; Viswanath, Pramod (2005), Fundamentos de la comunicación inalámbrica , Cambridge University Press , Reino Unido
  12. ↑ Shannon, CE (1948). "Una teoría matemática de la comunicación" (PDF) . Bell System Technical Journal . 27 ( 3–4 ): 379–423 y 623–656. Bibcode : 1948BSTJ...27..379S . doi : 10.1002/j.1538-7305.1948.tb01338.x . hdl : 11858/00-001M-0000-002C-4314-2 .
  13. ↑ Rosas, F.; Brante, G.; Souza, RD; Oberli, C. (2014). "Optimización de la tasa de codificación para lograr comunicaciones inalámbricas energéticamente eficientes". Actas de la Conferencia IEEE sobre Comunicaciones y Redes Inalámbricas (WCNC) . págs. 775–780 . doi : 10.1109/WCNC.2014.6952166 . ISBN  978-1-4799-3083-8.
  14. ↑ Kaufman, Tali ; Viderman, Michael. "Códigos comprobables localmente frente a códigos decodificables localmente" .
  15. ↑ Brubaker, Ben (9 de enero de 2024) ."Se demostró que el esquema de corrección de errores 'mágico' era inherentemente ineficiente" . Quanta Magazine . Consultado el 9 de enero de 2024 .
  16. ↑ Kothari, Pravesh; Manohar, Peter (11 de junio de 2024). "Un límite inferior exponencial para códigos lineales de 3 consultas localmente corregibles" . Simposio sobre teoría de la computación . 56 : 776–787 . doi : 10.1145/3618260.3649640 . Recuperado el 24 de marzo de 2026 .
  17. ↑ Efremenko, Klim (31 de mayo de 2009). "Códigos decodificables localmente de 3 consultas de longitud subexponencial" . SIAM Journal on Computing . 41 (6): 39– 44. doi : 10.1145/1536414.1536422 . Recuperado el 24 de marzo de 2026 .
  18. 1 2 Vucetic, B.; Yuan, J. (2000). Códigos turbo: principios y aplicaciones . Springer Verlag . ISBN 978-0-7923-7868-6.
  19. ↑ Luby, Michael ; Mitzenmacher, M.; Shokrollahi, A.; Spielman, D.; Stemann, V. (1997). "Códigos prácticos resistentes a pérdidas". Actas del 29.º Simposio Anual de la Asociación para la Maquinaria de Computación (ACM) sobre Teoría de la Computación .
  20. ↑ "Digital Video Broadcast (DVB); Estructura de trama de segunda generación, codificación de canal y sistemas de modulación para radiodifusión, servicios interactivos, recopilación de noticias y otras aplicaciones de banda ancha por satélite (DVB-S2)". En 302 307 (V1.2.1). ETSI . Abril de 2009.
  21. ↑ Andrews, KS; Divsalar, D.; Dolinar, S.; Hamkins, J.; Jones, CR; Pollara, F. (noviembre de 2007). "El desarrollo de códigos Turbo y LDPC para aplicaciones en el espacio profundo". Actas del IEEE . 95 (11): 2142– 2156. doi : 10.1109/JPROC.2007.905132 . S2CID 9289140 . 
  22. ↑ Dolinar, S.; Divsalar, D. (15 de agosto de 1995). "Distribuciones de peso para códigos turbo usando permutaciones aleatorias y no aleatorias". Informe de progreso de TDA . 122 : 42–122 . Bibcode : 1995TDAPR.122...56D . CiteSeerX 10.1.1.105.6640 . 
  23. ↑ Takeshita, Oscar (2006). "Permutation Polynomial Interleavers: An Algebraic-Geometric Perspective". IEEE Transactions on Information Theory . 53 (6): 2116– 2132. arXiv : cs/0601048 . Bibcode : 2006cs........1048T . doi : 10.1109/TIT.2007.896870 . S2CID 660 . 
  24. ↑ 3GPP TS 36.212 , versión 8.8.0, página 14
  25. ↑ "Digital Video Broadcasting (DVB); Estructura de trama, codificación de canal y modulación para un sistema de radiodifusión de televisión digital terrestre de segunda generación (DVB-T2)". En 302 755 (V1.1.1). ETSI . Septiembre de 2009.
  26. ↑ Techie (3 de junio de 2010). "Explicando el entrelazado" . Blog de W3 Techie . Consultado el 3 de junio de 2010 .
  27. ↑ Krastanov, Stefan; Jiang, Liang (8 de septiembre de 2017). "Decodificador probabilístico de red neuronal profunda para códigos estabilizadores" . Scientific Reports . 7 (1): 11003. arXiv : 1705.09334 . Bibcode : 2017NatSR...711003K . doi : 10.1038/ s41598-017-11266-1 . PMC 5591216. PMID 28887480 .  
  28. ↑ Nordstrom, AW; Robinson, JP (1967), "Un código no lineal óptimo", Information and Control , 11 ( 5–6 ): 613–616 , doi : 10.1016/S0019-9958(67)90835-2
  29. ↑ Perry, Jonathan; Balakrishnan, Hari; Shah, Devavrat (2011). "Códigos espinales sin tasa" . Actas del 10.º Taller ACM sobre temas candentes en redes . págs. 1–6 . doi : 10.1145/2070562.2070568 . hdl : 1721.1/79676 . ISBN  9781450310598.

Lecturas adicionales

  • MacWilliams, Florence Jessiem ; Sloane, Neil James Alexander (2007) [1977]. Escrito en AT&T Shannon Labs, Florham Park, Nueva Jersey, EE. UU. The Theory of Error-Correcting Codes . North-Holland Mathematical Library. Vol.  16 (impresión digital de la 12.ª reimpresión, 1.ª  ed.). Ámsterdam / Londres / Nueva York / Tokio: North-Holland / Elsevier BV . ISBN 978-0-444-85193-2. LCCN 76-41296 . (xxii+762+6 páginas)
  • Clark, Jr., George C.; Cain, J. Bibb (1981). Codificación de corrección de errores para comunicaciones digitales . Nueva York, EE. UU.: Plenum Press . ISBN 0-306-40615-2.
  • Arazi, Benjamin (1987). Swetman, Herb (ed.). Un enfoque de sentido común a la teoría de los códigos correctores de errores . Serie de Sistemas Informáticos de MIT Press  . Vol. 10 (1.ª  ed.). Cambridge, Massachusetts, EE. UU. / Londres, Reino Unido: Instituto Tecnológico de Massachusetts . ISBN 0-262-01098-4. LCCN 87-21889 . (x+2+208+4 páginas)
  • Wicker, Stephen B. (1995). Sistemas de control de errores para comunicación y almacenamiento digital . Englewood Cliffs, Nueva Jersey, EE. UU.: Prentice-Hall . ISBN 0-13-200809-2.
  • Wilson, Stephen G. (1996). Modulación y codificación digital . Englewood Cliffs, Nueva Jersey, EE. UU.: Prentice-Hall . ISBN 0-13-210071-1.
  • "Código de corrección de errores en memorias flash NAND de celda de un solo nivel" 16/02/2007
  • "Código de corrección de errores en memorias flash NAND" 29/11/2004
  • Observaciones sobre errores, correcciones y confianza en sistemas dependientes , por James Hamilton, 26 de febrero de 2012
  • Empaquetamientos, retículos y grupos de esferas , por JH Conway, Neil James Alexander Sloane, Springer Science & Business Media , 09/03/2013 – Matemáticas – 682 páginas.
  • Morelos-Zaragoza, Robert (2004). "La página de códigos correctores (ECC)" . Recuperado el 5 de marzo de 2006 .
  • Zoológico de corrección de errores . Base de datos de códigos de corrección de errores.
  • lpdec: biblioteca descontinuada para la decodificación de lenguaje natural y funciones relacionadas (Python)
Obtenido de " https://en.wikipedia.org/w/index.php?title=Error_correction_code&oldid=1359264693#Interleaving "
Lecturas relacionadas
6 articulos
Simulación por computadoraComputaciónLa informática es cualquier actividad orientada a objetivos que requiera, se beneficie o cree maquinaria informática . [1] Incluye el estudio y la ...TelecomunicacionesTelecomunicacionesEstación terrestre en la instalación de comunicaciones por satélite de Raisting Estación terrestre en Raisting , Baviera , Alemania La telecomunica...Teoría de la informaciónTeoría de la informaciónLa teoría de la información es el estudio matemático de la cuantificación , el almacenamiento y la comunicación de la información . El campo fue es...Teoría de la codificaciónTeoría de la codificaciónLa teoría de la codificación es el estudio de las propiedades de los códigos y su respectiva idoneidad para aplicaciones específicas. Los códigos s...Comunicación de datosLa comunicación de datos , que incluye la transmisión y recepción de datos , es la transferencia de datos , transmitidos y recibidos a través de un...Communication channelCommunication channelA communication channel refers either to a physical transmission medium such as a wire, or to a logical connection over a multiplexed medium such a...