Codificación de canal

En la ingeniería de comunicaciones , la codificación de canales (también conocida como codificación de canales ) se refiere al proceso de proteger los datos digitales contra errores de transmisión durante la transmisión a través de canales perturbados agregando redundancia .

La base matemática para la codificación de canales la proporciona la teoría de la codificación .

Debe distinguirse entre codificación de canal y codificación de fuente , que reduce la redundancia , y codificación de línea , que realiza una adaptación espectral a los requisitos del canal de transmisión .

Procedimiento

Transmisión con codificación de fuente, canal y línea

La codificación de canal agrega redundancia a los datos en la entrada de un canal de transmisión y decodifica los datos en su salida. Si la información adicional solo indica un error y requiere que los datos sean retransmitidos, esto se denomina corrección de errores hacia atrás . Si la información de redundancia es suficiente para corregir el error, es una corrección de error hacia adelante . La codificación de canal eficiente aumenta la relación señal / ruido mientras que la tasa de error de bit permanece sin cambios . Dependiendo del método de codificación del canal, la ganancia del código es de varios  dB .

Una propiedad esencial de un código de canal es su tasa de código (código) :

${\ Displaystyle R = k / n}$

en el cual

• ${\ Displaystyle k}$ es el número de símbolos en la entrada del codificador (símbolos de información) y
• ${\ Displaystyle n}$ el número de símbolos en la salida del codificador (símbolos de código).

Por tanto, los símbolos de información se asignan a los símbolos de código. Una tasa pequeña (grande ) significa una mayor proporción de símbolos de código en los símbolos transmitidos, es decir, una tasa de transmisión de datos más baja . Un código de canal con una tasa de código más baja normalmente puede corregir más errores que un código de canal comparable con una tasa de código alta; por lo tanto, es posible un intercambio entre la tasa de transmisión de datos y la capacidad de corrección de errores. ${\ Displaystyle k}$${\ Displaystyle n}$${\ Displaystyle n}$

Encadenamiento de código

Al encadenar hábilmente códigos (por ejemplo, con códigos turbo ), la capacidad de corrección del código encadenado creado de esta manera puede ser mucho mayor que la de los códigos individuales (códigos de componentes).

Punteado

La subperforación se refiere a los símbolos de código individuales de golpe objetivo, de modo que se reduce el número de símbolos de código transmitidos de a . Esto da como resultado una tasa más alta para el código pinchado . La perforación permite utilizar el mismo par de codificador / descodificador para códigos a diferentes velocidades. ${\ Displaystyle n}$${\ Displaystyle n '}$${\ Displaystyle R '= k / n'> k / n = R}$

historia

El trabajo pionero de Shannon en 1948

La publicación del trabajo pionero de Claude E. Shannon sobre la teoría de la información, Una teoría matemática de la comunicación , también marcó el nacimiento de la codificación de canales en 1948. Aunque ya existían esfuerzos para proteger los mensajes contra la transmisión incorrecta, estos no iban más allá de una simple transmisión múltiple. ( código de repetición ), lo que resultó ser un código de canal sin ganancia de código. Shannon demostró que cada canal de transmisión puede describirse mediante una capacidad de canal que limita la velocidad de información que se puede lograr de manera confiable a través de un canal. En este contexto, fiable significa que la tasa de error de símbolo no supera un valor límite especificado. También mostró que hay códigos de canal que se acercan tanto como se desee a esta capacidad (teorema de codificación de canal). Sin embargo, la prueba de existencia no proporciona una construcción práctica para los códigos de canal, ni cómo decodificarlos de manera eficiente. De hecho, los códigos que describió Shannon son infinitamente largos y aleatorios por naturaleza.

Primeras construcciones prácticas en la década de 1950

Poco después de la publicación de Shannon, se desarrollaron los primeros códigos de canal prácticos. Los trabajos de Marcel JE Golay ( Golay Code , 1949) y Richard W. Hamming ( Hamming Code , 1950) son particularmente innovadores . El trabajo de Hamming estuvo motivado por la falta de fiabilidad de las computadoras de relé de la época, en las que a menudo se producían errores de bits. El código de martilleo (7,4) puede corregir cualquier error de bit en 4 bits de mensaje con solo 3 bits de redundancia.

Irving S. Reed y David E. Muller desarrollaron los códigos de canal ahora conocidos como códigos Reed-Muller en 1954 . Los códigos Reed-Muller tienen la ventaja de que también se pueden construir para bloques de gran longitud y, por lo tanto, corrigen un número comparativamente grande de errores. Una subclase de códigos Reed-Muller son los códigos Hadamard , que pasaron a la historia como los primeros códigos de canal para la transmisión de datos desde sondas espaciales ( Mariner-9 ). ${\ Displaystyle n}$

Década de 1960: códigos algebraicos

Los códigos Reed-Solomon (según Irving S. Reed y Gustave Solomon , 1960) y sus códigos de subgrupo BCH (según RC Bose , DK Ray-Chaudhuri y A. Hocquenghem ) representan un hito . La idea básica aquí es consistir en codificar símbolos para usar un campo finito (en lugar de bits) y considerar los mensajes como polinomios sobre este campo, y codificar palabras como evaluación en los polinomios en diferentes lugares. Es posible separar las palabras de código entre sí tanto como sea posible ( Código separable de distancia máxima, código MDS ). Por lo tanto, los códigos Reed-Solomon tienen excelentes propiedades de corrección de errores y desde entonces se han utilizado en muchas aplicaciones como CD , DVD , DVB y códigos QR . Elvyn Berlekamp y James Massey desarrollaron un método de decodificación eficiente ( algoritmo de Berlekamp-Massey ) entre 1968 y 1969.${\ Displaystyle n}$

Décadas de 1970 y 1980: códigos convolucionales y encadenamiento de códigos

Con los códigos convolucionales , Peter Elias describió los primeros códigos basados ​​en flujo de datos ya en 1955, es decir, códigos de canal sin una longitud de bloque fija. Sin embargo, estos solo encontraron aplicación práctica con el eficiente algoritmo de decodificación de Andrew Viterbi ( algoritmo de Viterbi , 1967). Por primera vez, el algoritmo de Viterbi hizo posible utilizar simplemente la denominada decodificación de entrada suave , en la que se tienen en cuenta las probabilidades (en lugar de los valores de bits decididos) para cada símbolo. Por lo tanto, los códigos convolucionales se utilizaron en particular en aplicaciones de radio como GSM y WLAN ( 802.11a / g ) donde esta información está disponible. No obstante, su capacidad de corrección de errores depende de la longitud del registro de desplazamiento utilizado, que está implicado exponencialmente en la complejidad de la decodificación.

El encadenamiento de código en serie ( Dave Forney , 1966) demostró ser una tecnología clave para diseñar códigos cada vez mejores con un esfuerzo de decodificación manejable. Un mensaje se codifica primero con un código de canal (externo) (generalmente un código algebraico) y luego con un código convolucional (interno). Este método encontró un uso prominente en 1977 con las sondas espaciales Voyager y siguió siendo la fuerza impulsora detrás de la codificación de canales hasta el desarrollo de los códigos turbo .

Decodificación iterativa desde la década de 1990

Todos los códigos de canal mencionados hasta ahora operaban muy lejos (es decir, varios decibelios en la relación señal / ruido ) de la capacidad del canal indicada por Shannon, y se creía ampliamente que esto no se podía lograr de manera práctica. Así que el alboroto fue grande cuando los códigos turbo inventados por Claude Berrou a principios de la década de 1990 (Alain Glavieux y Punya Thitimajshima son coautores de la publicación de 1993) cerraron repentinamente esta brecha en la capacidad del canal a unas pocas décimas de dB. En los códigos turbo se utilizan dos códigos convolucionales concatenados en paralelo con un intercalador pseudoaleatorio . Para la decodificación se utilizan dos decodificadores BCJR con retroalimentación , un principio que recuerda al turbocompresor de un motor de combustión interna . Los dos decodificadores intercambian información en varias iteraciones para finalmente converger en una palabra de código. Se utilizan registros de desplazamiento comparativamente cortos para los códigos convolucionales, ya que con los códigos turbo el intercalador asegura que los bits de la palabra de código se entrelazan entre sí en toda la longitud del código. Por lo tanto, el esfuerzo de decodificación es solo lineal con la longitud de la palabra de código, lo que hizo que los códigos muy largos (muchos kilobits por palabra de código) fueran practicables por primera vez y, por lo tanto, se acerca mucho a los códigos ideados por Shannon. Los códigos turbo se utilizaron luego en los estándares celulares UMTS y LTE .

En 1996 , David JC MacKay demostró un rendimiento igualmente bueno que los códigos turbo con códigos LDPC , que también se decodifican iterativamente con el algoritmo de propagación de creencias . Aunque estos fueron inventados por Robert Gallager a principios de la década de 1960 , se olvidaron porque la tecnología en ese momento aún no permitía una implementación práctica. En los años siguientes, el trabajo de Tom Richardson y Rüdiger Urbanke desarrolló una teoría extensa para la construcción de códigos LDPC, por lo que estos ahora se consideran el cuasi-estado del arte en codificación de canales. Se utilizan en el celular 5G estándar , los nuevos WLAN estándares ( 802.11n y 802.11ac ) y DVB-X2 . En este último, los códigos internos de los códigos LDPC se utilizan concatenados con los códigos BCH .

Códigos polares

La tecnología avanzó aún más con los códigos polares introducidos por Erdal Arıkan en 2008 . Mostró que los códigos polares, junto con un algoritmo de decodificación recursivo simple, alcanzan la capacidad del canal de forma asintótica (es decir, para una longitud de bloque que se acerca al infinito). Los códigos polares son los primeros códigos para los que esto se ha demostrado matemáticamente, mientras que el buen rendimiento de los códigos Turbo y LDPC solo se ha demostrado de forma experimental. Para longitudes de bloque cortas, los códigos polares son inferiores a otros esquemas, pero al concatenar una suma de comprobación CRC, se podría lograr un rendimiento igualmente bueno que con los códigos LDPC cortos. Por lo tanto, se seleccionaron códigos polares CRC para los canales de control en redes celulares 5G .

Clases de código

Si se conocen los tipos de errores que ocurren en un canal de transmisión, se pueden construir varios códigos que pueden corregir bien los tipos frecuentes de errores y los tipos menos frecuentes de errores menos. La ilustración de al lado muestra una descripción general de las clases de código de uso frecuente.

Descripción general de las clases de código de uso frecuente

Básicamente, los códigos de canal se pueden dividir en códigos basados ​​en bloques y basados ​​en secuencias de caracteres.

Códigos basados ​​en bloques ( códigos de bloque )

Los códigos de bloque se caracterizan por una longitud de palabra de código constante y predefinida . ${\ Displaystyle n}$

Códigos algebraicos

Los códigos algebraicos se basan en construcciones algebraicas. Están diseñados para lograr propiedades muy específicas, por ejemplo, una gran distancia mínima. Por lo tanto, se pueden hacer declaraciones precisas sobre qué tipos de errores y cuántos errores pueden reconocer o corregir.

• Bit de paridad

• Código de Hamming
• Código Golay

• Código Reed-Muller
• Código de fuego
• Código Reed-Solomon y código BCH
• Comprobación de redundancia cíclica (código CRC)

Códigos de decodificación iterativos

Los códigos decodificados iterativamente también se conocen como códigos de canal modernos . A diferencia de los códigos algebraicos, el algoritmo de decodificación determina el diseño del código. Estos eficientes algoritmos permiten longitudes de bloque muy largas, con las que los códigos decodificados iterativamente pueden acercarse más a la capacidad del canal de Shannon . Se caracterizan por una construcción mayoritariamente pseudoaleatoria. Los dos representantes más importantes de esta clase de código son:

• Código de verificación de paridad de baja densidad (código LDPC)
• Código turbo
  • Código convolucional turbo (dos códigos convolucionales terminados como códigos básicos)
  • Código de producto Turbo (cualquier código algebraico como código básico)

Códigos de la teoría de la información

Con los códigos polares introducidos en 2008, se encontraron códigos de bloque que se basan en el principio teórico de la información de polarización de canal. No se pueden asignar a ninguna de las dos clases anteriores, pero están estrechamente relacionadas con el Código Reed-Muller .

• Código polar

Códigos basados ​​en flujo de caracteres

A diferencia de los códigos de bloque, los códigos basados ​​en flujo de caracteres no tienen una longitud de bloque fija. Por lo tanto, son adecuados para servicios de transmisión y redes de área amplia . Mediante la terminación, los códigos basados ​​en el flujo de caracteres se pueden convertir en códigos de bloque de cualquier longitud. Las clases más importantes de códigos basados ​​en secuencias de caracteres son:

• Códigos convolucionales
• Código Ungerboeck (también conocido como modulación codificada en trellis )
• Códigos de escalera
• Códigos LDPC acoplados espacialmente (también llamados códigos convolucionales LDPC)

Ejemplos de

• Error de canal que depende de la codificación de la fuente

La definición de un método de codificación tiene en cuenta tanto los requisitos de calidad de la señal a transmitir como las propiedades del canal. Si, por ejemplo, se falsifica un bit en la ruta de transmisión en el caso de una señal de televisión que se transmite sin comprimir, solo cambia un píxel de una (mitad) imagen. Si se produce el mismo error con una señal de televisión codificada en MPEG comprimida , se corrompe un macrobloque completo de un cierto número de píxeles (dependiendo del tamaño del macrobloque: 16 × 16 hasta 4 × 4 píxeles) y las imágenes subsiguientes; el error ya no está presente hasta que llega de nuevo una trama codificada independientemente (trama I).

• Ejemplo de corrección de errores hacia atrás

Agregar bits de paridad a una palabra de datos.

• Ejemplo de corrección de errores hacia atrás / adelante

Código ISBN : si el dígito de control no coincide , solo unos pocos códigos ISBN pueden considerarse valores correctos.

• Ejemplo de corrección de errores hacia adelante

Código postal e información de la ciudad: una ciudad mal escrita se puede corregir utilizando el código postal. De manera similar, Zahlendreher reconoció en el código postal haciendo coincidir el nombre del lugar.

• Ejemplo GSM

El teléfono limita el rango de frecuencia del habla a aproximadamente 4 kHz. El muestreo a 8 kHz con una cuantificación de 8 bits por muestra da como resultado un flujo de datos de 64 kbit / s. La codificación de la fuente GSM la reduce a aproximadamente 13 kbit / s. Las redundancias se agregan al flujo de datos para limitar la frecuencia de errores de bits en la transmisión de radio, que es susceptible a interferencias. La codificación del canal aumenta la tasa de bits a 22,8 kbit / s.

Ver también

• Procedimiento de corrección de errores
• Código lineal
• Código cíclico
• Función hash
• Tasa de error de bit
• Ocultación de errores
• Dispersión y codificador de energía (telecomunicaciones)

literatura

• John G. Proakis, Masoud Salehi: Ingeniería de sistemas de comunicación . 2ª Edición. Prentice Hall, 2002, ISBN 0-13-095007-6 . 

Evidencia individual

1. ^ CE Shannon: una teoría matemática de la comunicación . En: Revista técnica de Bell System . cinta 27 , no. 4 de octubre de 1948, ISSN  0005-8580 , p. 623-656 , doi : 10.1002 / j.1538-7305.1948.tb00917.x . 
2. ↑ Marcel Golay: Notas sobre codificación digital . En: Actas de la IRE . cinta 37 , no. 6 , junio de 1949, ISSN  0096-8390 , pág. 657-657 , doi : 10.1109 / jrproc.1949.233620 . 
3. ↑ Hamming, RW (Richard Wesley), 1915-1998.: Teoría de la codificación y la información . Prentice-Hall, Englewood Cliffs, Nueva Jersey 1980, ISBN 0-13-139139-9 . 
4. ^ ES Reed, G. Solomon: Códigos polinomiales sobre ciertos campos finitos . En: Revista de la Sociedad de Matemáticas Industriales y Aplicadas . cinta 8 , no. 2 de junio de 1960, ISSN  0368-4245 , pág. 300-304 , doi : 10.1137 / 0108018 . 
5. ↑ E. Berlekamp: Decodificación BCH no binaria . En: IEEE Transactions on Information Theory . cinta 14 , no. 2 , marzo de 1968, ISSN  0018-9448 , pág. 242-242 , doi : 10.1109 / tit.1968.1054109 . 
6. ↑ J. Massey: Síntesis de registro de cambios y decodificación BCH . En: IEEE Transactions on Information Theory . cinta 15 , no. 1 de enero de 1969, ISSN  0018-9448 , págs. 122-127 , doi : 10.1109 / tit.1969.1054260 . 
7. ^ Proyecto de asociación de tercera generación: "3GGP TS45.001: Red de acceso de radio GSM / EDGE del grupo de especificaciones técnicas; Capa física en la ruta de radio; Descripción general" . 
8. ↑ C. Berrou, A. Glavieux, P. Thitimajshima: Codificación y decodificación de corrección de errores de límite cercano a Shannon: códigos Turbo. 1 . En: Actas de ICC '93 - IEEE International Conference on Communications . cinta 2 . IEEE, Ginebra, Suiza 1993, ISBN 978-0-7803-0950-0 , págs. 1064-1070 , doi : 10.1109 / ICC.1993.397441 ( ieee.org [consultado el 1 de noviembre de 2020]). 
9. ↑ 3GPP: LTE; Acceso radioeléctrico terrestre universal evolucionado (E-UTRA); Multiplexación y codificación de canales (3GPP TS 36.212 versión 10.0.0 Release 10) . ( etsi.org [PDF; consultado el 1 de noviembre de 2020]). 
10. ↑ DJC MacKay, RM Neal: Rendimiento límite cercano a Shannon de códigos de verificación de paridad de baja densidad . En: Electronics Letters . cinta 33 , no. 6 , 1997, ISSN  0013-5194 , págs. 457 , doi : 10.1049 / el: 19970362 . 
11. ^ Robert G. Gallager: Códigos de verificación de paridad de baja densidad . The MIT Press, 1963, ISBN 978-0-262-25621-6 . 
12. ↑ Erdal Arikan: Polarización de canal: un método para construir códigos de logro de capacidad . En: Simposio internacional de IEEE 2008 sobre teoría de la información . IEEE, 2008, ISBN 978-1-4244-2256-2 , doi : 10.1109 / isit.2008.4595172 . 
13. ↑ 3GPP: 5G NR, 3GPP TS 38.212 versión 15.2.0 Release 15: Multiplexación y codificación de canales . ( etsi.org [PDF; consultado el 1 de noviembre de 2020]). 
14. ^ Tom Richardson, Ruediger Urbanke: Teoría de la codificación moderna . Cambridge University Press, Cambridge 2008, ISBN 978-0-511-79133-8 . 
15. ↑ Benjamin P. Smith, Arash Farhood, Andrew Hunt, Frank R. Kschischang, John Lodge: Códigos de escalera: FEC para OTN de 100 Gb / s . En: Revista de tecnología Lightwave . cinta 30 , no. 1 , enero de 2012, ISSN  0733-8724 , p. 110-117 , doi : 10.1109 / JLT.2011.2175479 ( ieee.org [consultado el 2 de noviembre de 2020]).