Corrección de errores, ¿Cómo funciona?, Un promedio de ruido para reducir los errores, Tipos de FEC, Códigos FEC concatenados para mejorar el rendimiento, Baja densidad de comprobación de paridad, Códigos de Turbo, Decodificación y pruebas de los códigos locales, Intercalado, Lista de códigos correctores de errores

En telecomunicaciones, teoría de la información, y la teoría de la codificación, la corrección de errores o la codificación de canal es una técnica utilizada para el control de errores en la transmisión de datos a través de canales de comunicación no fiables o ruidosa. La idea central es que el remitente codifica su mensaje de una manera redundante mediante el uso de un código de corrección de errores. El matemático estadounidense Richard Hamming pionero de este campo en la década de 1940 e inventó la primera corrección de errores de código en 1950: el código de Hamming.

La redundancia permite que el receptor para la detección de un número limitado de errores que pueden ocurrir en cualquier parte en el mensaje, y, a menudo para corregir estos errores sin retransmisión. FEC da el receptor la capacidad de corregir errores sin necesidad de un canal de retorno para solicitar la retransmisión de los datos, pero a costa de un ancho de banda de canal fijo, superior hacia adelante. Por lo tanto, FEC se aplica en situaciones en las retransmisiones son costosos o imposibles, tales como vías de comunicación de ida y en la transmisión a varios receptores en multicast. Información FEC generalmente se añade a los dispositivos de almacenamiento masivo para permitir la recuperación de datos dañados, y es ampliamente utilizado en los módems.

Procesamiento de FEC en un receptor puede ser aplicado a un flujo de bits digital o en la demodulación de una portadora modulada digitalmente. En este último caso, FEC es una parte integral de la analógica inicial a la conversión digital en el receptor. El decodificador de Viterbi implementa un algoritmo de decisión blanda para demodular los 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 bit que se puede utilizar como realimentación para ajustar los receptores electrónicos analógicos.

Las fracciones máximas de errores de bits que faltan o que pueden ser corregidos está determinada por el diseño del código FEC, por lo que diferentes códigos de corrección de errores hacia delante son adecuados para diferentes condiciones.

¿Cómo funciona?

FEC se lleva a cabo mediante la adición de redundancia a la información transmitida mediante un algoritmo. Un poco redundante puede ser una función compleja de muchos bits de información originales. La información original puede o no puede aparecer literalmente en la salida codificada; códigos que incluyen la entrada no modificada en la salida son sistemáticos, mientras que los que no lo hacen son no sistemática.

Un ejemplo simplista de FEC es para transmitir cada bit de datos 3 veces, lo que se conoce como un código de repetición. A través de un canal ruidoso, un receptor puede ver 8 versiones del producto, consulte la tabla siguiente.

Esto permite un error en cualquiera de las tres muestras para ser corregidos por "voto de la mayoría" o "voto democrático". La capacidad de corrección de este FEC es:

  • Hasta 1 bit de triplete por error, o
  • hasta 2 bits de triplete omiten.

Aunque fácil de implementar y ampliamente utilizado, esta redundancia modular triple es una FEC relativamente ineficiente. Códigos de mejores FEC generalmente examinan el último varias docenas, o incluso el último varios cientos, previamente recibieron bits para determinar cómo descodificar la corriente pequeño puñado de bits.

Un promedio de ruido para reducir los errores

FEC podría decirse que trabajar por "un promedio de ruido"; ya que cada bit de datos afecta a muchos símbolos de transmisión, la corrupción de algunos símbolos por el ruido por lo general permite a los datos de usuario originales a ser extraídos de los otros símbolos, no corrompidos recibidos que también dependen de la misma los datos de usuario.

  • Debido a esta "puesta en común de riesgos" efecto, los sistemas de comunicación digitales que utilizan FEC tienden a trabajar muy por encima de un mínimo de señal determinada a ruido y nada debajo.
  • Este todo-o-nada tendencia - el efecto acantilado - se hace más pronunciado a medida que se utilizan los códigos más fuertes que más estrechamente se acercan al límite teórico de Shannon.
  • Intercalado de datos codificados FEC puede reducir las propiedades de todo o nada de códigos FEC transmitidos cuando los errores de canal tienden a ocurrir en ráfagas. Sin embargo, este método tiene sus límites, sino que es el más utilizado en los datos de banda estrecha.

La mayoría de los sistemas de telecomunicaciones utilizan un código de canal fija diseñada para tolerar la tasa de error de bit del peor caso esperado y, a continuación, no funcionan en absoluto si la tasa de error de bit es cada vez peor. Sin embargo, algunos sistemas se adaptan a las condiciones de error de canal dadas: híbrido de solicitud automática de repetición-utiliza un método FEC fija mientras el FEC puede manejar la tasa de error, y entonces cambia la ARQ, cuando la tasa de error es demasiado alta; modulación adaptativa y codificación de usos una variedad de tipos de FEC, la adición de más bits de corrección de errores por paquete, cuando hay mayores porcentajes de error en el canal, o sacarlos cuando no se necesitan.

Tipos de FEC

 Artículo principal: Código de Bloqueo y código convolucional

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

  • Códigos de bloque trabajar en bloques de tamaño fijo de bits o símbolos de tamaño predeterminado. Códigos de bloque prácticas generalmente pueden decodificar en tiempo polinomial a su longitud de bloque.
  • Los códigos convolucionales trabajan en bits o símbolo corrientes de longitud arbitraria. Con mayor frecuencia se descodifican con el algoritmo de Viterbi, aunque otros algoritmos se utilizan a veces. Decodificación de Viterbi permite la eficiencia de decodificación asintóticamente óptima con el aumento de longitud de restricción del código de convolución, pero a expensas de la complejidad creciente de forma exponencial. Un código de convolución se puede convertir en un código de bloque, si se desea, "caudofagia".

Hay muchos tipos de códigos de bloque, pero entre los clásicos de la más notable es la codificación Reed-Solomon, debido a su uso generalizado en el disco compacto, el DVD y en unidades de disco duro. Otros ejemplos de códigos de bloque clásicos incluyen Golay, BCH, la paridad multidimensional, y los códigos de Hamming.

Hamming ECC se utiliza comúnmente para corregir errores de memoria NAND flash. Esto proporciona la corrección de errores de un solo bit y detección de errores de 2 bits. Códigos Hamming sólo son adecuados para NAND celda de nivel único más fiable. Más denso de múltiples células NAND nivel requiere más fuerte de varios bits ECC corrección como BCH y Reed-Solomon.

Códigos de bloque clásicos se implementan normalmente el uso de algoritmos de decisión dura, lo que significa que por cada entrada y la señal de salida se toma una decisión difícil si corresponde a un uno o un cero bits. En contraste, los algoritmos de decisión flexible como el descodificador de señales analógicas de proceso de Viterbi, lo que permite para un rendimiento de corrección de errores mucho más alta que la decodificación de difícil decisión.

Casi todos los códigos de bloque clásicos se aplican las propiedades algebraicas de campos finitos.

En las capas superiores, la solución de FEC para los estándares de transmisión móvil es el código Raptor o RaptorQ.

Más adelante la corrección de errores sólo correcta bits tirones, pero no poco-inserciones o deleciones-bit. En esta configuración, la distancia Hamming es la manera adecuada de medir la tasa de error de bit. Unos códigos de corrección de errores están diseñadas para corregir bits inserciones y deleciones de bits, tales como códigos de marcación y códigos de la marca de agua. La distancia de Levenshtein es una forma más adecuada para medir la tasa de error de bit cuando se utiliza este tipo de códigos.

Códigos FEC concatenados para mejorar el rendimiento

Códigos de bloque y códigos convolucionales clásicos se combinan con frecuencia en los esquemas de codificación concatenada en la que un corto código convolucional limitación de longitud de Viterbi decodificada hace la mayor parte de la obra y un código de bloque con un mayor tamaño de símbolo y la longitud de bloque "mops hasta" los errores cometidos por el decodificador convolucional. Decodificación de una sola pasada con esta familia de códigos de corrección de errores puede producir tasas de error muy bajo, pero por las condiciones de transmisión a larga distancia de decodificación iterativa se recomienda.

Códigos concatenados han sido una práctica habitual en las comunicaciones espaciales de satélite y profundo desde el Voyager 2 utilizó por primera vez la técnica en su 1986 encuentro con Urano. La nave Galileo utilizó iterativo códigos concatenados para compensar las condiciones de muy alta tasa de error ocasionadas por tener una antena fallado.

Baja densidad de comprobación de paridad

Los códigos de control de paridad de baja densidad son una clase de códigos de bloque lineales altamente eficientes re-descubiertas recientemente. Ellos pueden proporcionar un rendimiento muy cerca de la capacidad del canal utilizando un enfoque de descodificación de decisión blanda iterada, en complejidad tiempo lineal en términos de su longitud de bloque. Las implementaciones prácticas se basará en gran medida de la utilización de paralelismo.

Códigos LDPC se introdujeron por primera vez por Robert G. Gallagher en su tesis doctoral en 1960, pero debido al esfuerzo computacional en la implementación de codificador y decodificador y la introducción de códigos de Reed-Solomon, que eran en su mayoría ignorados hasta hace poco.

Códigos LDPC ahora se utilizan en muchos estándares de comunicación de alta velocidad recientes, como DVB-S2, WiMAX, alta velocidad Wireless LAN, 10GBASE-T Ethernet y G.hn/G.9960. Otros códigos de LDPC están estandarizados para los estándares de comunicación inalámbrica dentro de 3GPP MBMS.

Códigos de Turbo

Turbo es un esquema de codificación-decodificación suave iterada que combina dos o más códigos convolucionales relativamente simples y un intercalador para producir un código de bloque que puede realizar dentro de una fracción de un decibelio del límite de Shannon. Precediendo códigos LDPC en términos de aplicación práctica, que ahora ofrecen un rendimiento similar.

Una de las primeras aplicaciones comerciales de codificación turbo fue la tecnología celular digital CDMA2000 1x desarrollado por Qualcomm y vendido 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, 1xEV-DO. Como 1x EV-DO fue desarrollado por Qualcomm, y se vende por Verizon Wireless, Sprint y otros operadores.

Decodificación y pruebas de los códigos locales

 Artículo principal: Código localmente descifrable y el código localmente comprobable

A veces sólo es necesario para decodificar los bits individuales del mensaje, o para comprobar si una señal dada es una palabra de código, y hacer así sin mirar a toda la señal. Esto puede tener sentido en un entorno de streaming, en palabras de código son demasiado grandes para ser clásicamente decodifica lo suficientemente rápido y que sólo unos pocos bits del mensaje son de interés para la empresa. También este tipo de códigos se han convertido en una herramienta importante en la teoría de la complejidad computacional, por ejemplo, para el diseño de pruebas probabilísticamente verificables.

Códigos localmente descifrables son códigos correctores de errores para que los bits individuales del mensaje pueden ser probabilísticamente recuperados con sólo mirar a un pequeño número de posiciones de una palabra de código, incluso después de la palabra de código se ha dañado en algún fracción constante de posiciones. Códigos localmente comprobables son códigos correctores de errores para los que se puede comprobar probabilísticamente si una señal está cerca de una palabra de código con sólo mirar a un pequeño número de posiciones de la señal.

Intercalado

Intercalado se utiliza con frecuencia en sistemas de almacenamiento de la comunicación digital y para mejorar el rendimiento de códigos de corrección de errores hacia adelante. Muchos canales de comunicación no son sin memoria: errores suelen ocurrir en ráfagas en lugar 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, que no se recupera la palabra código original. Intercalado aminora este problema por revolver símbolos de la fuente a través de varias palabras de código, creando de este modo una distribución más uniforme de errores. Por lo tanto, el intercalado se utiliza ampliamente para la ráfaga de corrección de errores.

El análisis de los códigos se repiten a lo moderno, como turbo códigos y códigos LDPC, por lo general asume una distribución independiente de los errores. Los sistemas que utilizan códigos LDPC tanto suelen emplear entrelazado adicional a través de los símbolos dentro de una palabra código.

Para los códigos turbo, un intercalador es un componente integral y su diseño adecuado es crucial para un buen rendimiento. El algoritmo de decodificación iterativo funciona mejor cuando no hay ciclos cortos en el gráfico que representa el factor de decodificador; el intercalador se elige para evitar ciclos cortos.

Diseños intercalador incluyen:

  • entrelazadores rectangulares
  • entrelazado convolucional
  • entrelazadores azar
  • S-aleatoria intercalador.
  • Otra interpretación posible es un polinomio de segundo grado de permutación libre de contención. Se utiliza por ejemplo en el Term Evolution estándar de telecomunicaciones móviles largo 3GPP.

En los sistemas de comunicación de portadora múltiple, intercalado adicional a través de portadores se puede emplear para mitigar los efectos del ruido prohibitivo en un único o pocos portadores específicos.

Ejemplo

Transmisión sin intercalación:

 Mensaje de error-libre: Transmisión aaaabbbbccccddddeeeeffffgggg con un error de ráfaga: aaaabbbbccc____deeeeffffgggg

La palabra de código CDDD se altera en cuatro bits, así que o bien no se puede descodificar en absoluto, o que podría ser decodificado incorrectamente.

Con intercalación:

 Palabras de código sin errores: aaaabbbbccccddddeeeeffffgggg Interleaved: Transmisión abcdefgabcdefgabcdefgabcdefg con un error de ráfaga: abcdefgabcd____bcdefgabcdefg Recibido palabras de código después de desentrelazado: aa_abbbbccccdddde_eef_ffg_gg

En cada una de las palabras en clave AAAA, eeee, ffff, gggg, sólo un poco se altera, por lo que un bit de código de corrección de error decodificar todo correctamente.

Transmisión sin intercalación:

 Original frase transmitida: ThisIsAnExampleOfInterleaving Recibido frase con una ráfaga de errores: ThisIs______pleOfInterleaving

El término "AnExample" termina su mayoría incomprensibles y difíciles de corregir.

Con intercalación:

 Frase transmitida: ThisIsAnExampleOfInterleaving ... Sin errores de transmisión: TIEpfeaghsxlIrv.iAaenli.snmOten. Frase Recibido con una ráfaga de errores: TIEpfe______Irv.iAaenli.snmOten. Pena recibidas después de desentrelazado: T_isI_AnE_amp_eOfInterle_vin_ ...

Ni una palabra se pierde por completo, y las letras que faltan se pueden recuperar con conjeturas mínimo.

Desventajas de entrelazado

El uso de técnicas de entrelazado aumenta la latencia. Esto se debe a que todo el bloque de entrelazado debe ser recibido antes de que los paquetes pueden ser decodificados. También dispositivos de entrelazado de ocultar la estructura de errores; sin un intercalador, algoritmos de decodificación más avanzados pueden tomar ventaja de la estructura de error y lograr una comunicación más fiable que un decodificador más sencillo combinado con un intercalador.

Lista de códigos correctores de errores

 Código distancia 2 3 paridad triple redundancia modular 3 Hamming perfecta como Hamming Hamming extendido 4 7 perfecta binario código Golay 8 Código Golay binario extendido