En informática , telecomunicaciones , teoría de la información y teoría de la codificación , se utiliza un código de corrección de errores , a veces un código de corrección de errores , ( ECC ) para controlar errores en los datos a través de canales de comunicación ruidosos o poco fiables . [1] [2] La idea central es que el remitente codifica el mensaje con información redundante en forma de ECC. La redundancia permite al receptor detectar un número limitado de errores que pueden ocurrir en cualquier parte del mensaje y, a menudo, corregir estos errores sin retransmisión. El matemático estadounidenseRichard 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) . [2]
ECC contrasta con la detección de errores en que los errores que se encuentran pueden corregirse, no simplemente detectarse. La ventaja es que un sistema que usa ECC no requiere un canal inverso para solicitar la retransmisión de datos cuando ocurre un error. La desventaja es que hay una sobrecarga fija que se agrega al mensaje, lo que requiere un mayor ancho de banda de canal de avance. Por lo tanto, ECC se aplica en situaciones en las que las retransmisiones son costosas o imposibles, como enlaces de comunicación unidireccionales y 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 en órbita alrededor de Urano , la retransmisión debido a errores puede crear un retraso de cinco horas. La información de ECC generalmente se agrega adispositivos de almacenamiento masivo para permitir la recuperación de datos corruptos, se usa ampliamente en módems y se usa en sistemas donde la memoria principal es la memoria ECC .
El procesamiento de ECC en un receptor puede aplicarse a un flujo de bits digital o en la demodulación de una portadora modulada digitalmente. Para este último, ECC es una parte integral de la conversión inicial de analógico a digital en el receptor. El decodificador de Viterbi implementa un algoritmo de decisión suave para demodular datos digitales de una señal analógica corrompida por ruido. Muchos codificadores / decodificadores ECC también pueden generar una señal de tasa de error de bits (BER), que se puede utilizar como retroalimentación para ajustar la electrónica de recepción analógica.
Las fracciones máximas de errores o de bits faltantes que se pueden corregir están determinadas por el diseño del código ECC, por lo que diferentes códigos de corrección de errores son adecuados para diferentes condiciones. En general, un código más fuerte induce más redundancia que debe transmitirse 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 canales ruidosos de Claude Shannonse 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 da una idea de cómo construir un código de logro de capacidades. Después de años de investigación, algunos sistemas ECC avanzados en la actualidad [ ¿cuándo? ] se acercan mucho al máximo teórico.
Corrección de errores de reenvío [ editar ]
En telecomunicaciones , teoría de la información y teoría de la codificación , la corrección de errores hacia adelante ( FEC ) o la codificación de canal [3] [4] 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 codifica el mensaje de forma redundante , la mayoría de las veces mediante un ECC.
La redundancia permite al receptor detectar un número limitado de errores que pueden ocurrir en cualquier parte del mensaje y, a menudo, corregir estos errores sin retransmisión. FEC le da al receptor la capacidad de corregir errores sin necesidad de un canal inverso para solicitar la retransmisión de datos, pero a costa de un ancho de banda de canal de avance fijo más alto. Por lo tanto, FEC se aplica en situaciones en las que las retransmisiones son costosas o imposibles, como enlaces de comunicación unidireccionales y cuando se transmite a múltiples receptores en multidifusión . La información FEC generalmente se agrega a dispositivos de almacenamiento masivo (magnético, óptico y de estado sólido / flash) para permitir la recuperación de datos corruptos, se usa ampliamente en módems, se utiliza en sistemas en los que la memoria principal es la memoria ECC y en situaciones de transmisión, en las que el receptor no tiene la capacidad de solicitar la retransmisión o, al hacerlo, se produciría una latencia significativa. Por ejemplo, en el caso de un satélite que orbita alrededor de Urano , una retransmisión debido a errores de decodificación puede crear un retraso de al menos 5 horas.
El procesamiento FEC en un receptor se puede aplicar a un flujo de bits digital 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 de Viterbi implementa un algoritmo de decisión suave para demodular datos digitales de una señal analógica corrompida por ruido. Muchos codificadores FEC también pueden generar una señal de tasa de error de bits (BER) que se puede utilizar como retroalimentación para ajustar la electrónica de recepción analógica.
La proporción máxima de errores o bits faltantes que pueden corregirse 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 debe transmitirse 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 la codificación de canales ruidososde Claude Shannon responde a la pregunta de cuánto ancho de banda queda para la comunicación de datos mientras se usa el código más eficiente que convierte la probabilidad de error de decodificación en cero. 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. Su prueba no es constructiva y, por lo tanto, no da una idea de cómo construir un código de logro de capacidad. Sin embargo, después de años de investigación, algunos sistemas FEC avanzados como el código polar [4] logran la capacidad del canal de Shannon bajo la hipótesis de una trama de longitud infinita.
Cómo funciona [ editar ]
ECC se logra agregando redundancia a la información transmitida usando un algoritmo. Un bit redundante puede ser una función compleja 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 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 puede ver 8 versiones de la salida, consulte la tabla a continuación.
| Triplete recibido | Interpretado como |
|---|---|
| 000 | 0 (sin errores) |
| 001 | 0 |
| 010 | 0 |
| 100 | 0 |
| 111 | 1 (sin errores) |
| 110 | 1 |
| 101 | 1 |
| 011 | 1 |
Esto permite corregir un error en cualquiera de las tres muestras mediante "voto mayoritario" o "votación democrática". La capacidad de corrección de este ECC es:
- Hasta 1 bit de triplete con error, o
- se omiten hasta 2 bits de triplete (casos no mostrados en la tabla).
Aunque simple de implementar y ampliamente utilizado, esta triple redundancia modular es un 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).
Promedio de ruido para reducir errores [ editar ]
Se podría decir que 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 ruido normalmente permite extraer los datos originales del usuario de los otros 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 muy por encima de una determinada relación mínima señal / ruido y no por debajo de ella.
- Esta tendencia de todo o nada , el efecto acantilado , se vuelve más pronunciada a medida que se utilizan códigos más fuertes que se acercan más al límite teórico de Shannon .
- Intercalar datos codificados ECC puede reducir las propiedades de todo o nada de los códigos ECC transmitidos cuando los errores de canal tienden a ocurrir en ráfagas. Sin embargo, este método tiene límites; se utiliza mejor en 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 en el peor de los casos esperados , y luego no funcionan en absoluto si la tasa de errores de bits es cada vez peor. Sin embargo, algunos sistemas se adaptan a las condiciones de error de canal dadas: algunas instancias de solicitud repetida automática híbrida utilizan un método ECC fijo siempre que el ECC pueda manejar la tasa de error, luego cambia a ARQ cuando la tasa de error es demasiado alta; La codificación y modulació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.
Tipos de ECC [ editar ]
Las dos categorías principales de códigos ECC son códigos de bloque y códigos convolucionales .
- Los códigos de bloque funcionan en bloques de tamaño fijo (paquetes) de bits o símbolos de tamaño predeterminado. Los códigos de bloque prácticos generalmente se pueden decodificar de forma rígida en tiempo polinomial a su longitud de bloque.
- Los códigos convolucionales funcionan en flujos de bits o símbolos de longitud arbitraria. La mayoría de las veces se decodifican por software con el algoritmo de Viterbi , aunque a veces se utilizan otros algoritmos. La decodificación de Viterbi permite una eficiencia de decodificación óptima asintóticamente con una longitud de restricción creciente del código convolucional, pero a expensas de una complejidad que aumenta exponencialmente . Un código convolucional que se termina también es un 'código de bloque' en el sentido de que codifica un bloque de datos de entrada, pero el tamaño de bloque de un código convolucional es generalmente arbitrario, mientras que los códigos de bloque tienen un tamaño fijo dictado por sus características algebraicas. Los tipos de terminación para códigos convolucionales incluyen "mordisco" y "descarga de bits".
Hay muchos tipos de códigos de bloque; La codificación Reed-Solomon es digna de mención por su uso generalizado en discos compactos , DVD y unidades de disco duro . Otros ejemplos de códigos de bloque clásicos incluyen los códigos Golay , BCH , paridad multidimensional y Hamming .
Hamming ECC se usa comúnmente para corregir errores de memoria flash NAND . [5] Esto proporciona corrección de errores de un solo bit y detección de errores de 2 bits. Los códigos de Hamming solo son adecuados para NAND de celda de un solo nivel (SLC) más confiable . NAND de celdas multinivel más densas (MLC) puede utilizar ECC de corrección de multibits como BCH o Reed – Solomon. [6] [7] NOR Flash normalmente no utiliza ninguna corrección de errores. [6]
Los códigos de bloque clásicos generalmente se decodifican usando algoritmos de decisión rígida , [8] lo que significa que para cada señal de entrada y salida se toma una decisión difícil si corresponde a un bit uno o cero. Por el contrario, los códigos convolucionales se decodifican típicamente utilizando algoritmos de decisión suave 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 bloque clásicos aplican las propiedades algebraicas de campos finitos . Por lo tanto, los códigos de bloque clásicos a menudo se denominan códigos algebraicos.
En contraste con 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 en reenvío corrigen solo cambios de bits, pero no inserciones o eliminaciones de bits. En esta configuración, la distancia de Hamming es la forma adecuada de medir la tasa de error de bit . Algunos códigos de corrección de errores de reenvío 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.[9]
Tasa de código y compensación entre confiabilidad y tasa de datos [ editar ]
El principio fundamental de ECC es agregar bits redundantes para ayudar al decodificador a encontrar el verdadero mensaje que fue codificado por el transmisor. La tasa de código de un sistema ECC dado 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 dado. 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 usa 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 una compensación fundamental entre confiabilidad y velocidad de datos. [10] En un extremo, un código fuerte (con una tasa de código baja) puede inducir un aumento importante en el receptor SNR (relación señal-ruido) disminuyendo la tasa de error de bits, a costa de reducir la tasa de datos efectiva. . En el otro extremo, no usar ningún ECC (es decir, una tasa de código igual a 1) usa el canal completo para propósitos 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 insignificante? Claude Shannon respondió a esta pregunta con su segundo teorema, que dice que la capacidad del canal es la tasa de bits máxima que puede alcanzar cualquier ECC cuya tasa de error tiende a cero: [11] 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 máximo de rendimiento. Hoy en día, varios códigos pueden alcanzar casi el límite de Shannon. Sin embargo, la capacidad de lograr ECC suele ser extremadamente compleja de implementar.
Los ECC más populares tienen un compromiso entre rendimiento y complejidad computacional. Por lo general, sus parámetros brindan 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 mientras se minimiza el impacto en la tasa de datos. Otro criterio para optimizar la tasa de código es equilibrar la tasa de error baja y el número de retransmisiones para el costo de energía de la comunicación. [12]
Códigos ECC concatenados para mejorar el rendimiento [ editar ]
Los códigos de bloque clásicos (algebraicos) y los códigos convolucionales se combinan con frecuencia en esquemas de codificación concatenados en los que un código convolucional decodificado por Viterbi de longitud restringida 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 más grandes "limpia" cualquier error cometido 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 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 el espacio profundo desde que la Voyager 2 utilizó por primera vez la técnica en su encuentro de 1986 con Urano . La nave Galileo utilizó códigos concatenados iterativos para compensar las condiciones de tasa de error muy altas causadas por tener una antena defectuosa.
Verificación de paridad de baja densidad (LDPC) [ editar ]
Los códigos de verificación de paridad de baja densidad (LDPC) son una clase de códigos de bloques lineales altamente eficientes hechos 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 se basan en gran medida en 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 ahora se utilizan en muchos estándares recientes de comunicación de alta velocidad, 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 ), [13] Ethernet 10GBase-T (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 (ver códigos fuente ).
Códigos turbo [ editar ]
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 intercalador para producir un código de bloque que puede funcionar dentro de una fracción de un decibel del límite de Shannon . Al ser anteriores a los códigos LDPC en términos de aplicación práctica, 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).
Decodificación local y prueba de códigos [ editar ]
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 lo suficientemente rápido y donde solo unos pocos bits del mensaje son de interés por ahora. Además, dichos 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 se pueden recuperar probabilísticamente bits individuales del mensaje mirando solo un pequeño número (digamos 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 comprobar probabilísticamente si una señal está cerca de una palabra de código con solo mirar un pequeño número de posiciones de la señal.
Entrelazado [ editar ]
El entrelazado se utiliza con frecuencia en los sistemas de almacenamiento y comunicación 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 ocurrir en ráfagas en lugar de 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 puede 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. [14] 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 , generalmente asume una distribución independiente de errores. [15] Por lo tanto, los sistemas que utilizan códigos LDPC suelen emplear un entrelazado adicional a través de los símbolos dentro de una palabra de código. [dieciséis]
Para los códigos turbo, un intercalador es un componente integral y su diseño adecuado es crucial para un buen rendimiento. [14] [17] El algoritmo de decodificación iterativo 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:
- entrelazadores rectangulares (o uniformes) (similar al método que usa factores de omisión descritos anteriormente)
- intercaladores convolucionales
- intercaladores aleatorios (donde el intercalador es una permutación aleatoria conocida)
- Intercalador S-aleatorio (donde el intercalador es una permutación aleatoria conocida con la restricción de que no aparecen símbolos de entrada dentro de la distancia S dentro de una distancia de S en la salida). [18]
- un polinomio de permutación cuadrática libre de contención (QPP). [19] Un ejemplo de uso es el estándar de telecomunicaciones móviles 3GPP Long Term Evolution . [20]
En los 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. [21]
Ejemplo [ editar ]
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 de 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 incorrectamente .
Con entrelazado :
Palabras de código sin errores: aaaabbbbccccddddeeeeffffggggIntercalado: abcdefgabcdefgabcdefgabcdefgTransmisión con un 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", solo 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: ThisIsAnExampleOfInterleavingSentencia recibida con un error de ráfaga: ThisIs______pleOfInterleaving
El término "UnEjemplo" termina siendo en su mayoría ininteligible y difícil de corregir.
Con entrelazado :
Oración transmitida: ThisIsAnExampleOfInterleaving ...Transmisión sin errores: TIEpfeaghsxlIrv.iAaenli.snmOten.Sentencia recibida con un error de ráfaga: TIEpfe ______ Irv.iAaenli.snmOten.Sentencia 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.
Desventajas del entrelazado [ editar ]
El uso de técnicas de entrelazado aumenta el retraso total. Esto se debe a que se debe recibir todo el bloque intercalado antes de que los paquetes puedan decodificarse. [22] También los intercaladores ocultan la estructura de los errores; sin un intercalador, 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 intercalador [ cita requerida ] . Un ejemplo de tal algoritmo se basa en estructuras de redes neuronales [23] .
Software para códigos de corrección de errores [ editar ]
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 de radio en la nube (C-RAN) en un contexto de radio definido por software (SDR) . La idea es utilizar ECC de software directamente en las comunicaciones. Por ejemplo, en el 5G, los ECC de software podrían ubicarse en la nube y las antenas conectadas 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 software de código abierto disponibles que se enumeran a continuación (no exhaustivos).
- AFF3CT (A Fast Forward Error Correction Toolbox): una cadena de comunicación completa en C ++ (muchos códigos compatibles como Turbo, LDPC, códigos polares, etc.), muy rápida y especializada en codificación de canales (se puede utilizar como programa para simulaciones o como una biblioteca para el SDR).
- IT ++ : una biblioteca C ++ de clases y funciones para álgebra lineal, optimización numérica, procesamiento de señales, comunicaciones y estadísticas.
- OpenAir : implementación (en C) de las especificaciones 3GPP relativas a las Evolved Packet Core Networks.
Lista de códigos de corrección de errores [ editar ]
| Distancia | Código |
|---|---|
| 2 (detección de error único) | Paridad |
| 3 (corrección de un solo error) | Redundancia modular triple |
| 3 (corrección de un solo error) | Hamming perfecto como Hamming (7,4) |
| 4 ( SEGUNDO ) | Hamming extendido |
| 5 (corrección de doble error) | |
| 6 (corrección de error doble / detección de error triple) | |
| 7 (corrección de tres errores) | código Golay binario perfecto |
| 8 (TECFED) | código Golay binario extendido |
- Códigos AN
- Código BCH , que puede diseñarse para corregir cualquier número arbitrario de errores por bloque de código.
- Código Berger
- Código de peso constante
- Código convolucional
- Códigos de expansión
- Códigos de grupo
- Códigos Golay , de los cuales el código Golay binario es de interés práctico
- Código Goppa , utilizado en el criptosistema McEliece
- Código Hadamard
- Código de Hagelbarger
- Código de Hamming
- Código basado en cuadrados latinos para ruido no blanco (predominante, por ejemplo, en banda ancha sobre líneas eléctricas)
- Código lexicográfico
- Codificación de red lineal , un tipo de código de corrección de borrado a través de redes en lugar de enlaces punto a punto
- Código largo
- Código de verificación de paridad de baja densidad , también conocido como código de Gallager , como el arquetipo de códigos de gráficos dispersos
- Código LT , que es un código de corrección de borrado sin tasa casi óptimo (código fuente)
- m de n códigos
- Código en línea , un código de corrección de borrado sin velocidad casi óptimo
- Código polar (teoría de la codificación)
- Código Raptor , un código de corrección de borrado sin velocidad casi óptimo
- Corrección de errores de Reed-Solomon
- Código Reed-Muller
- Código de repetición y acumulación
- Códigos de repetición , como redundancia modular triple
- Código espinal, un código no lineal y sin velocidad basado en funciones hash pseudoaleatorias [24]
- Código Tornado , un código de corrección de borrado casi óptimo y el precursor de los códigos Fountain
- Código turbo
- Código de Walsh-Hadamard
- Las comprobaciones de redundancia cíclica (CRC) pueden corregir errores de 1 bit para mensajes con una longitud máxima de bits para obtener polinomios generadores óptimos de grado , consulte Matemáticas de comprobaciones de redundancia cíclica # Bitfilters
Ver también [ editar ]
- Tasa de código
- Códigos de borrado
- Decodificador de decisión suave
- Código de corrección de errores en ráfaga
- Detección y corrección de errores
- Códigos de corrección de errores con retroalimentación
Referencias [ editar ]
- ^ Glover, Neal; Dudley, Trent (1990). Diseño práctico de corrección de errores para ingenieros (Revisión 1.1, 2ª ed.). CO, Estados Unidos: Cirrus Logic . ISBN 0-927239-00-0. ISBN 978-0-927239-00-4 .
- ↑ a b Hamming, Richard Wesley (abril de 1950). "Códigos de detección y corrección de errores". Revista técnica de Bell System . Estados Unidos: AT&T . 29 (2): 147–160. doi : 10.1002 / j.1538-7305.1950.tb00463.x .
- ^ Charles Wang; Dean Sklar; Diana Johnson (invierno de 2001 a 2002). "Codificación de corrección de errores hacia adelante" . Crosslink . La Corporación Aeroespacial. 3 (1). Archivado desde el original el 25 de febrero de 2012 . Consultado el 5 de marzo de 2006 .
Cómo funcionan los códigos de corrección de errores de reenvío
- ↑ a b Maunder, Robert (2016). "Descripción general de la codificación de canales" .
- ^ "Códigos Hamming para dispositivos de memoria flash NAND" . EE Times-Asia. Aparentemente basado en la "Nota técnica de Micron TN-29-08: Códigos Hamming para dispositivos de memoria flash NAND" . 2005. Ambos dicen: "El algoritmo Hamming es un método aceptado por la industria para la detección y corrección de errores en muchas aplicaciones basadas en flash SLC NAND".
- ^ a b "¿Qué tipos de ECC se deben utilizar en la memoria flash?" (Nota de aplicación) . Spansion. 2011.
Tanto el algoritmo Reed-Solomon como el algoritmo BCH son opciones comunes de ECC para flash MLC NAND.
... Los códigos de bloque basados en Hamming son los ECC más comúnmente usados para SLC .... tanto Reed – Solomon como BCH pueden manejar múltiples errores y son ampliamente usados en flash MLC.
- ^ Jim Cooke (agosto de 2007). "Las incómodas verdades de la memoria flash NAND" (PDF) . pag. 28.
Para SLC, un código con un umbral de corrección de 1 es suficiente.
t = 4 requerido ... para MLC.
- ^ Baldi, M .; Chiaraluce, F. (2008). "Un esquema simple para la decodificación de propagación de creencias de códigos BCH y RS en transmisiones multimedia" . Revista Internacional de Radiodifusión Multimedia Digital . 2008 : 1–12. doi : 10.1155 / 2008/957846 .
- ^ Shah, Gaurav; Molina, Andrés; Blaze, Matt (2006). "Teclados y canales encubiertos" . USENIX . Consultado el 20 de diciembre de 2018 .
- ^ Tse, David; Viswanath, Pramod (2005), Fundamentos de la comunicación inalámbrica , Cambridge University Press , Reino Unido
- ^ Shannon, CE (1948). "Una teoría matemática de la comunicación" (PDF) . Revista técnica de Bell System . 27 (3–4): 379–423 y 623–656. doi : 10.1002 / j.1538-7305.1948.tb01338.x . hdl : 11858 / 00-001M-0000-002C-4314-2 .
- ↑ Rosas, F .; Brante, G .; Souza, RD; Oberli, C. (2014). "Optimización de la tasa de código para lograr comunicaciones inalámbricas energéticamente eficientes" . Actas de la Conferencia sobre redes y comunicaciones inalámbricas de IEEE (WCNC) .
- ^ Estándar IEEE, sección 20.3.11.6 "802.11n-2009" , IEEE, 29 de octubre de 2009, consultado el 21 de marzo de 2011.
- ^ a b Vucetic, B .; Yuan, J. (2000). Códigos turbo: principios y aplicaciones . Springer Verlag . ISBN 978-0-7923-7868-6.
- ^ Luby, Michael ; Mitzenmacher, M .; Shokrollahi, A .; Spielman, D .; Stemann, V. (1997). "Códigos prácticos resistentes a pérdidas". Proc. 29º Simposio anual de la Asociación de Maquinaria de Computación (ACM) sobre Teoría de la Computación .
- ^ "Transmisión de video digital (DVB); Estructura de encuadre de segunda generación, sistemas de codificación y modulación de canales para transmisión, servicios interactivos, recopilación de noticias y otras aplicaciones de banda ancha por satélite (DVB-S2)". En 302 307 . ETSI (V1.2.1). Abril de 2009.
- ^ 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 de espacio profundo". Actas del IEEE . 95 (11): 2142–2156. doi : 10.1109 / JPROC.2007.905132 .
- ^ Dolinar, S .; Divsalar, D. (15 de agosto de 1995). "Distribuciones de peso para códigos Turbo utilizando permutaciones aleatorias y no aleatorias". Informe de progreso de la TDA : 42–122. CiteSeerX 10.1.1.105.6640 .
- ^ Takeshita, Oscar (2006). "Intercaladores de polinomios de permutación: una perspectiva algebraico-geométrica". Transacciones IEEE sobre teoría de la información . 53 (6): 2116–2132. arXiv : cs / 0601048 . doi : 10.1109 / TIT.2007.896870 .
- ^ 3GPP TS 36.212 , versión 8.8.0, página 14
- ^ "Transmisión de video digital (DVB); Estructura de trama, codificación y modulación de canales para un sistema de transmisión de televisión digital terrestre de segunda generación (DVB-T2)". En 302 755 . ETSI (V1.1.1). Septiembre de 2009.
- ^ Techie (3 de junio de 2010). "Explicando el entrelazado" . Blog de W3 Techie . Consultado el 3 de junio de 2010 .
- ^ Krastanov, Stefan; Jiang, Liang (8 de septiembre de 2017). "Decodificador probabilístico de redes neuronales profundas para códigos estabilizadores" . Informes científicos . 7 (1): 1–7. doi : 10.1038 / s41598-017-11266-1 .
- ^ Perry, Jonathan; Balakrishnan, Hari; Shah, Devavrat (2011). "Códigos espinales Rateless" . Actas del 10º Taller de ACM sobre temas candentes en las redes . doi : 10.1145 / 2070562.2070568 . hdl : 1721,1 / 79676 .
Lectura adicional [ editar ]
- MacWilliams, Florence Jessiem ; Sloane, Neil James Alexander (2007) [1977]. Escrito en AT&T Shannon Labs, Florham Park, Nueva Jersey, EE. UU. La teoría de los códigos de corrección de errores . Biblioteca matemática de Holanda Septentrional. 16 (impresión digital de la 12ª impresión, 1ª ed.). Ámsterdam / Londres / Nueva York / Tokio: Holanda Septentrional / Elsevier BV . ISBN 0-444-85193-3. LCCN 76-41296 . ISBN 978-0-444-85193-2 . (xxii + 762 + 6 páginas)
- Clark, Jr., George C .; Caín, J. Bibb (1981). Codificación de corrección de errores para comunicaciones digitales . Nueva York, Estados Unidos: Plenum Press . ISBN 0-306-40615-2. ISBN 978-0-306-40615-7 .
- Arazi, Benjamin (1987). Swetman, Herb (ed.). Un enfoque de sentido común a la teoría de los códigos de corrección de errores . Serie de prensa del MIT en sistemas informáticos. 10 (1 ed.). Cambridge, Massachusetts, EE. UU. / Londres, Reino Unido: Instituto de Tecnología de Massachusetts . ISBN 0-262-01098-4. LCCN 87-21889 . (x + 2 + 208 + 4 páginas)
- Mimbre, Stephen B. (1995). Sistemas de control de errores para comunicación y almacenamiento digitales . Englewood Cliffs, Nueva Jersey, EE.UU .: Prentice-Hall . ISBN 0-13-200809-2. ISBN 978-0-13-200809-9 .
- Wilson, Stephen G. (1996). Modulación y codificación digital . Englewood Cliffs, Nueva Jersey, EE.UU .: Prentice-Hall . ISBN 0-13-210071-1. ISBN 978-0-13-210071-7 .
- "Código de corrección de errores en memorias flash NAND de celda de un solo nivel" 2007-02-16
- "Código de corrección de errores en memorias flash NAND" 2004-11-29
- Observaciones sobre errores, correcciones y confianza de sistemas dependientes , por James Hamilton, 2012-02-26
- Empaquetaduras, celosías y grupos de esferas, por JH Conway, Neil James Alexander Sloane, Springer Science & Business Media , 2013-03-09 - Matemáticas - 682 páginas.
Enlaces externos [ editar ]
- Morelos-Zaragoza, Robert (2004). "La página de códigos de corrección (ECC)" . Consultado el 5 de marzo de 2006 .
- lpdec: biblioteca para decodificación LP y cosas relacionadas (Python)
