Teoría de la codificación

Se estudia la teoría matemática de las reglas de codificación de señales en la transmisión de información. La teoría de la codificación está estrechamente relacionada con la teoría de la información, la estadística matemática, la teoría de la probabilidad, los procesos estocásticos, el álgebra lineal, el álgebra moderna, la teoría de números, la geometría finita y el análisis combinatorio, y se ha convertido en una rama de las matemáticas aplicadas. La codificación se refiere a la transformación de señales para lograr un determinado propósito. Su transformación inversa se llama decodificación o decodificación. Según los diferentes propósitos de la codificación, la teoría de la codificación tiene tres ramas:

①Código fuente. Transformar la señal emitida por la fuente de información, incluida la discretización de señales continuas, es decir, convertir señales analógicas en señales digitales mediante muestreo y cuantificación, y comprimir los datos para mejorar la efectividad de la transmisión de señales digitales.

②Codificación de canales. Vuelva a convertir la señal emitida por el codificador de origen, incluida la codificación para distinguir canales, adaptarse a las condiciones del canal y mejorar la confiabilidad de la comunicación.

③Codificación segura. La señal emitida por el codificador de canal se reconvierte, es decir, se codifica para que sea menos probable que la información sea robada durante la transmisión. La teoría de la codificación se utiliza ampliamente en los campos de la telemetría digital y los sistemas de control remoto, las comunicaciones eléctricas, las comunicaciones digitales, las comunicaciones de imágenes, las comunicaciones por satélite, las comunicaciones en el espacio profundo, la tecnología informática, el procesamiento de datos, el procesamiento de imágenes, el control automático, la inteligencia artificial y el reconocimiento de patrones. La corrección de errores hacia adelante (FEC) es una técnica para controlar errores de transmisión en sistemas de comunicación unidireccionales mediante la recuperación de errores mediante el envío de información adicional junto con los datos para reducir la tasa de errores de bits (BER). FEC se divide en FEC dentro de banda y FEC fuera de banda. El procesamiento de FEC suele ocurrir en las primeras etapas y la señal digital procesada se recibe por primera vez. En otras palabras, los circuitos de corrección de errores suelen ser una parte integral del proceso de conversión de analógico a digital, que también implica modulación y demodulación digital, o codificación y decodificación de línea.

FEC utiliza un algoritmo predeterminado añadiendo información redundante para la transmisión. En 1949, Hamming propuso un código Hamming que podía corregir un único error aleatorio. En 1960, Hoopueghem, Bose y Chaudhum inventaron el código BCH, y Reed y Solomon propusieron el código ReedSolomon (RS), que tiene fuertes capacidades de corrección de errores y más tarde se denominó código de corrección de errores Reed-Solomon (más tarde corrección de errores directa adicional). ). ITU-T G.975/G.709 estipula que "FEC fuera de banda" consiste en agregar una capa FEC debajo de la capa SDH para abordar los problemas de FEC. La codificación FEC fuera de banda tiene una gran redundancia y fuertes capacidades de corrección de errores. FEC, a diferencia de ARQ, no necesita notificar al remitente sobre errores de retransmisión. Una vez que el sistema pierde el paquete original, el mecanismo FEC puede complementarlo con paquetes redundantes. Por ejemplo, un paquete de datos es "10", que se divide en dos paquetes de datos, a saber, "1" y "0", y también hay un paquete de datos redundante "0". Después de recibir dos paquetes de datos cualesquiera, se pueden ensamblar los paquetes originales. Sin embargo, estos paquetes redundantes también crean una carga adicional. En 1843, el famoso pintor estadounidense S.F.B Morse diseñó cuidadosamente el código Morse, que se utilizó ampliamente en las comunicaciones telegráficas. El código Morse utiliza tres símbolos diferentes: puntos, rayas y espacios, y puede considerarse un código ternario secuencial. Según la teoría de la codificación, se puede demostrar que la diferencia entre el código Morse y el límite teóricamente alcanzable es de sólo 15. Pero no fue hasta las décadas de 1930 y 1940 que la teoría de la codificación comenzó a tomar forma. En 1928, el ingeniero de telecomunicaciones estadounidense H. Nyquist propuso el famoso teorema de muestreo, que sentó las bases para la discretización de señales continuas. En 1948, el matemático aplicado estadounidense C.E. Shannon propuso el concepto de entropía de la información en el artículo "Teoría matemática en la comunicación", que sentó las bases teóricas para la codificación de fuentes. En 1949, Shannon propuso el concepto de capacidad de canal y el teorema de codificación de canales en su artículo "Comunicaciones con ruido", que sentó las bases teóricas para la codificación de canales. El teorema de codificación de canales ruidosos (también conocido como primer teorema de Shannon) señala que la longitud promedio de la palabra clave solo puede ser mayor o igual a la entropía de la fuente. El teorema de codificación de canales ruidosos (también conocido como segundo teorema de Shannon) es el teorema de existencia de la codificación. (Ver los tres teoremas principales de Shannon) Señala que mientras la velocidad de transmisión de información sea menor que la capacidad del canal, existe una codificación que hace que la probabilidad de error en la transmisión de información sea arbitrariamente pequeña.

Con el desarrollo de la tecnología informática y las comunicaciones digitales, la codificación y la criptografía con corrección de errores se han desarrollado rápidamente.

En lo que respecta al código fuente

Shannon demostró en 1951 que cuando la fuente genera mensajes redundantes, la salida de la fuente se puede cambiar mediante codificación para que la velocidad de transmisión de información sea cerca de la capacidad del canal. En 1948, Shannon propuso una codificación que podría coincidir con la fuente y el canal. En 1949, R.M. Feno del MIT propuso la codificación Feno. En 1951, el ingeniero de telecomunicaciones estadounidense D.A. Huffman propuso un código Huffman más eficiente. Desde entonces, han aparecido la codificación de fax, la codificación de imágenes y la codificación de voz, y la compresión de datos se ha estudiado en profundidad para resolver muchos problemas prácticos en la comunicación digital.

En codificación de corrección de errores

En 1948, Shannon propuso un código de corrección de errores de bits (longitud de la palabra clave = 7, número de símbolos de información = 4). Código Gray con tres bits de corrección de errores en 1949 (longitud de la palabra clave = 23, número de símbolos del mensaje = 12). En 1950, el matemático estadounidense Richard Wesley Heming publicó el artículo "Códigos de detección y corrección de errores" y propuso el famoso código Hamming, que tuvo un impacto importante en la codificación de corrección de errores. Los códigos convolucionales aparecieron en 1955. Los códigos convolucionales todavía se utilizan ampliamente. 1957 Se introdujeron códigos cíclicos. El código cíclico tiene una estructura simple, es fácil de diseñar utilizando la teoría algebraica y es fácil de implementar. En 1959 aparecieron los códigos Hagberger y Fell, que pueden corregir errores repentinos. En 1959, R.C. Bos y D.K. Ray Chaudhry de Estados Unidos y A. Okungun de Francia publicaron casi simultáneamente e independientemente un famoso código cíclico, que más tarde se denominó código BCH (código Bose-Chaudhuri-Hocquenghem). La decodificación secuencial se propuso en 1965 y se ha utilizado en las comunicaciones espaciales. 1967 A.J. Viterbi propuso la decodificación de convolución de máxima verosimilitud, llamada decodificación de Viterbi. La codificación vectorial apareció en 1978. La codificación vectorial es una técnica de codificación eficaz. En 1980, se desarrolló el código Reed-Solomon (código RS para abreviar) utilizando la teoría de números. En realidad, es un código BCH multibanda. Esta técnica de codificación de corrección de errores puede reducir la cantidad de componentes en el circuito integrado del codificador en un orden de magnitud. Es ampliamente utilizado en comunicaciones por satélite. Los códigos concatenados compuestos de códigos RS y códigos convolucionales se pueden utilizar para comunicaciones en el espacio profundo.

En criptografía,

En 1949, Shannon publicó la "Teoría de la comunicación de sistemas seguros", que generalmente se considera como el trabajo pionero de la criptografía. En 1976, Duffy y Herman propusieron por primera vez el sistema de criptografía de clave pública, que abrió una nueva dirección para la investigación de la criptografía. La aplicación de circuitos integrados a muy gran escala y computadoras de alta velocidad ha promovido el desarrollo de la teoría de la codificación segura, pero también plantea una gran amenaza para la seguridad de las comunicaciones confidenciales. Desde la década de 1970, la teoría de la complejidad computacional se ha introducido en la criptografía y han surgido los llamados problemas de tipo P, tipo NP y NP completo. La función de complejidad del algoritmo aumenta exponencialmente, por lo que el espacio de claves se expande, lo que hace que el análisis y la búsqueda de contraseñas enfrenten severos desafíos. La criptografía comenzó a desarrollarse en profundidad.