La 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 se utilizan para la compresión de datos , la criptografía , la detección y corrección de errores , la transmisión de datos y el almacenamiento de datos . Los códigos son estudiados por diversas disciplinas científicas (como la teoría de la información , la ingeniería eléctrica , las matemáticas , la lingüística y la informática ) con el fin de diseñar métodos de transmisión de datos eficientes y fiables . Esto normalmente implica la eliminación de la redundancia y la corrección o detección de errores en los datos transmitidos.
Hay cuatro tipos de codificación: [1]
La compresión de datos intenta eliminar la redundancia no deseada de los datos de una fuente para transmitirlos de manera más eficiente. Por ejemplo, la compresión de datos DEFLATE reduce el tamaño de los archivos, por ejemplo para reducir el tráfico de Internet. La compresión de datos y la corrección de errores se pueden estudiar en combinación .
La corrección de errores añade redundancia útil a los datos de una fuente para hacer que la transmisión sea más robusta ante las perturbaciones presentes en el canal de transmisión. El usuario común puede no estar al tanto de muchas aplicaciones que utilizan la corrección de errores. Un disco compacto de música (CD) típico utiliza el código Reed-Solomon para corregir rayones y polvo. En esta aplicación, el canal de transmisión es el propio CD. Los teléfonos celulares también utilizan técnicas de codificación para corregir el desvanecimiento y el ruido de la transmisión de radio de alta frecuencia. Los módems de datos, las transmisiones telefónicas y la Red de Espacio Profundo de la NASA emplean técnicas de codificación de canal para hacer pasar los bits, por ejemplo, el código turbo y los códigos LDPC .
En 1948, Claude Shannon publicó " Una teoría matemática de la comunicación ", un artículo en dos partes en los números de julio y octubre del Bell System Technical Journal . Este trabajo se centra en el problema de cómo codificar mejor la información que un emisor quiere transmitir. En este trabajo fundamental utilizó herramientas de la teoría de la probabilidad, desarrollada por Norbert Wiener , que estaban en sus etapas iniciales de aplicación a la teoría de la comunicación en ese momento. Shannon desarrolló la entropía de la información como una medida de la incertidumbre en un mensaje mientras inventaba esencialmente el campo de la teoría de la información .
El código binario Golay fue desarrollado en 1949. Es un código corrector de errores capaz de corregir hasta tres errores en cada palabra de 24 bits y detectar un cuarto.
Richard Hamming ganó el premio Turing en 1968 por su trabajo en los Laboratorios Bell en métodos numéricos, sistemas de codificación automática y códigos de detección y corrección de errores. Inventó los conceptos conocidos como códigos de Hamming , ventanas de Hamming , números de Hamming y distancia de Hamming .
En 1972, Nasir Ahmed propuso la transformada de coseno discreta (DCT), que desarrolló con T. Natarajan y KR Rao en 1973. [2] La DCT es el algoritmo de compresión con pérdida más utilizado , la base de formatos multimedia como JPEG , MPEG y MP3 .
El objetivo de la codificación fuente es tomar los datos fuente y hacerlos más pequeños.
Los datos pueden verse como una variable aleatoria , donde aparecen con probabilidad .
Los datos se codifican mediante cadenas (palabras) sobre un alfabeto .
Un código es una función
es la palabra clave asociada con .
La longitud de la palabra clave se escribe como
La longitud esperada de un código es
La concatenación de palabras código .
La palabra clave de la cadena vacía es la cadena vacía en sí:
La entropía de una fuente es la medida de la información. Básicamente, los códigos fuente intentan reducir la redundancia presente en la fuente y representar la fuente con menos bits que transportan más información.
La compresión de datos que intenta explícitamente minimizar la longitud promedio de los mensajes de acuerdo con un modelo de probabilidad particular asumido se denomina codificación de entropía .
Varias técnicas utilizadas por los esquemas de codificación de fuente intentan alcanzar el límite de entropía de la fuente. C ( x ) ≥ H ( x ), donde H ( x ) es la entropía de la fuente (tasa de bits) y C ( x ) es la tasa de bits después de la compresión. En particular, ningún esquema de codificación de fuente puede ser mejor que la entropía de la fuente.
La transmisión por fax utiliza un código de longitud de ejecución simple . La codificación de origen elimina todos los datos superfluos para el transmisor, lo que reduce el ancho de banda necesario para la transmisión.
El objetivo de la teoría de codificación de canales es encontrar códigos que se transmitan rápidamente, que contengan muchas palabras de código válidas y que puedan corregir o al menos detectar muchos errores. Si bien no son mutuamente excluyentes, el rendimiento en estas áreas es un equilibrio. Por lo tanto, diferentes códigos son óptimos para diferentes aplicaciones. Las propiedades necesarias de este código dependen principalmente de la probabilidad de que se produzcan errores durante la transmisión. En un CD típico, el deterioro se debe principalmente al polvo o a los arañazos.
Los CD utilizan codificación Reed-Solomon entrelazada para distribuir los datos en el disco. [3]
Aunque no se trata de un código muy bueno, un código de repetición simple puede servir como un ejemplo comprensible. Supongamos que tomamos un bloque de bits de datos (que representan sonido) y lo enviamos tres veces. En el receptor examinaremos las tres repeticiones bit a bit y tomaremos una votación mayoritaria. La particularidad de esto es que no solo enviamos los bits en orden, sino que los intercalamos. El bloque de bits de datos se divide primero en cuatro bloques más pequeños. Luego, recorremos el bloque y enviamos un bit del primero, luego el segundo, etc. Esto se hace tres veces para distribuir los datos sobre la superficie del disco. En el contexto del código de repetición simple, esto puede no parecer efectivo. Sin embargo, se conocen códigos más poderosos que son muy efectivos para corregir el error de "ráfaga" de un rasguño o una mancha de polvo cuando se utiliza esta técnica de intercalación.
Otros códigos son más apropiados para diferentes aplicaciones. Las comunicaciones en el espacio profundo están limitadas por el ruido térmico del receptor, que es más de naturaleza continua que de naturaleza ráfaga. Del mismo modo, los módems de banda estrecha están limitados por el ruido, presente en la red telefónica y también modelado mejor como una perturbación continua. [ cita requerida ] Los teléfonos celulares están sujetos a un desvanecimiento rápido . Las altas frecuencias utilizadas pueden causar un desvanecimiento rápido de la señal incluso si el receptor se mueve unos centímetros. Nuevamente, existe una clase de códigos de canal que están diseñados para combatir el desvanecimiento. [ cita requerida ]
El término teoría de codificación algebraica denota el subcampo de la teoría de codificación donde las propiedades de los códigos se expresan en términos algebraicos y luego se investigan más a fondo. [ cita requerida ]
La teoría de codificación algebraica se divide básicamente en dos tipos principales de códigos: [ cita requerida ]
Analiza las siguientes tres propiedades de un código, principalmente: [ cita requerida ]
Los códigos de bloque lineales tienen la propiedad de linealidad , es decir, la suma de dos palabras de código cualesquiera también es una palabra de código, y se aplican a los bits de origen en bloques, de ahí el nombre de códigos de bloque lineales. Hay códigos de bloque que no son lineales, pero es difícil demostrar que un código es bueno sin esta propiedad. [4]
Los códigos de bloque lineales se resumen por sus alfabetos de símbolos (por ejemplo, binario o ternario) y parámetros ( n , m , d min ) [5] donde
Existen muchos tipos de códigos de bloque lineales, como
Los códigos de bloques están relacionados con el problema del empaquetamiento de esferas , que ha recibido cierta atención a lo largo de los años. En dos dimensiones, es fácil de visualizar. Tome un montón de monedas planas sobre la mesa y apriételas. El resultado es un patrón hexagonal como un nido de abejas. Pero los códigos de bloques dependen de más dimensiones que no se pueden visualizar fácilmente. El poderoso código Golay (24,12) utilizado en las comunicaciones del espacio profundo utiliza 24 dimensiones. Si se utiliza como un código binario (que es lo que suele ser), las dimensiones se refieren a la longitud de la palabra clave como se definió anteriormente.
La teoría de la codificación utiliza el modelo de esfera de N dimensiones. Por ejemplo, ¿cuántas monedas se pueden colocar en un círculo sobre una mesa?, o en 3 dimensiones, ¿cuántas canicas se pueden colocar en un globo?. Otras consideraciones entran en la elección de un código. Por ejemplo, el empaquetamiento de hexágonos en la restricción de una caja rectangular dejará espacio vacío en las esquinas. A medida que las dimensiones se hacen más grandes, el porcentaje de espacio vacío se hace más pequeño. Pero en ciertas dimensiones, el empaquetamiento utiliza todo el espacio y estos códigos son los llamados códigos "perfectos". Los únicos códigos perfectos no triviales y útiles son los códigos de Hamming de distancia-3 con parámetros que satisfacen (2 r – 1, 2 r – 1 – r , 3), y los códigos binarios [23,12,7] y ternarios [11,6,5] de Golay. [4] [5]
Otra propiedad del código es el número de vecinos que puede tener una sola palabra de código. [6] Nuevamente, consideremos los centavos como ejemplo. Primero, los colocamos en una cuadrícula rectangular. Cada centavo tendrá 4 vecinos cercanos (y 4 en las esquinas que están más alejadas). En un hexágono, cada centavo tendrá 6 vecinos cercanos. Cuando aumentamos las dimensiones, el número de vecinos cercanos aumenta muy rápidamente. El resultado es que el número de formas en que el ruido puede hacer que el receptor elija un vecino (y, por lo tanto, un error) también aumenta. Esta es una limitación fundamental de los códigos de bloque y, de hecho, de todos los códigos. Puede ser más difícil causar un error a un solo vecino, pero el número de vecinos puede ser lo suficientemente grande como para que la probabilidad total de error realmente se vea afectada. [6]
Las propiedades de los códigos de bloques lineales se utilizan en muchas aplicaciones. Por ejemplo, la propiedad de unicidad de síndrome-coset de los códigos de bloques lineales se utiliza en la conformación de enrejado, [7] uno de los códigos de conformación más conocidos .
La idea detrás de un código convolucional es hacer que cada símbolo de palabra de código sea la suma ponderada de los diversos símbolos del mensaje de entrada. Esto es como la convolución utilizada en los sistemas LTI para encontrar la salida de un sistema, cuando se conoce la entrada y la respuesta al impulso.
Así, generalmente encontramos la salida del codificador convolucional del sistema, que es la convolución del bit de entrada, contra los estados de los registros del codificador convolucional.
En principio, los códigos convolucionales no ofrecen mayor protección contra el ruido que un código de bloques equivalente. En muchos casos, suelen ofrecer una mayor simplicidad de implementación que un código de bloques de igual potencia. El codificador suele ser un circuito simple que tiene memoria de estados y cierta lógica de retroalimentación, normalmente puertas XOR . El decodificador puede implementarse en software o firmware.
El algoritmo de Viterbi es el algoritmo óptimo que se utiliza para decodificar códigos convolucionales. Existen simplificaciones para reducir la carga computacional. Se basan en buscar solo las rutas más probables. Aunque no son óptimas, se ha comprobado que, en general, dan buenos resultados en entornos con poco ruido.
Los códigos convolucionales se utilizan en módems de banda vocal (V.32, V.17, V.34) y en teléfonos móviles GSM, así como en dispositivos de comunicación satelital y militar.
La criptografía o codificación criptográfica es la práctica y el estudio de técnicas para la comunicación segura en presencia de terceros (llamados adversarios ). [8] De manera más general, se trata de construir y analizar protocolos que bloqueen a los adversarios; [9] varios aspectos de la seguridad de la información como la confidencialidad de los datos , la integridad de los datos , la autenticación y el no repudio [10] son fundamentales para la criptografía moderna. La criptografía moderna existe en la intersección de las disciplinas de las matemáticas , la informática y la ingeniería eléctrica . Las aplicaciones de la criptografía incluyen tarjetas ATM , contraseñas de computadora y comercio electrónico .
Antes de la era moderna, la criptografía era sinónimo de cifrado , la conversión de información de un estado legible a un estado aparentemente sin sentido . El autor de un mensaje cifrado compartía la técnica de descodificación necesaria para recuperar la información original únicamente con los destinatarios previstos, impidiendo así que personas no deseadas hicieran lo mismo. Desde la Primera Guerra Mundial y la llegada de la computadora , los métodos utilizados para llevar a cabo la criptología se han vuelto cada vez más complejos y su aplicación más extendida.
La criptografía moderna se basa en gran medida en la teoría matemática y la práctica de la ciencia informática; los algoritmos criptográficos están diseñados en torno a supuestos de dureza computacional , lo que hace que dichos algoritmos sean difíciles de romper en la práctica por cualquier adversario. Es teóricamente posible romper un sistema de este tipo, pero es inviable hacerlo por cualquier medio práctico conocido. Por lo tanto, estos esquemas se denominan computacionalmente seguros; los avances teóricos, por ejemplo, las mejoras en los algoritmos de factorización de números enteros y la tecnología informática más rápida requieren que estas soluciones se adapten continuamente. Existen esquemas teóricamente seguros de la información que se puede demostrar que no se pueden romper ni siquiera con un poder de cómputo ilimitado (un ejemplo es la libreta de un solo uso ), pero estos esquemas son más difíciles de implementar que los mejores mecanismos teóricamente rompibles pero computacionalmente seguros.
Un código de línea (también llamado modulación de banda base digital o método de transmisión de banda base digital ) es un código elegido para su uso dentro de un sistema de comunicaciones con fines de transmisión de banda base . La codificación de línea se utiliza a menudo para el transporte de datos digitales.
La codificación de línea consiste en representar la señal digital que se va a transportar mediante una señal discreta en amplitud y tiempo que esté óptimamente ajustada a las propiedades específicas del canal físico (y del equipo receptor). El patrón de forma de onda de voltaje o corriente que se utiliza para representar los 1 y 0 de los datos digitales en un enlace de transmisión se denomina codificación de línea . Los tipos comunes de codificación de línea son la unipolar , la polar , la bipolar y la codificación Manchester .
Otra preocupación de la teoría de codificación es el diseño de códigos que ayuden a la sincronización . Un código puede diseñarse de modo que un cambio de fase pueda detectarse y corregirse fácilmente y que se puedan enviar múltiples señales por el mismo canal. [ cita requerida ]
Otra aplicación de los códigos, utilizada en algunos sistemas de telefonía móvil, es el acceso múltiple por división de código (CDMA). A cada teléfono se le asigna una secuencia de códigos que no tiene correlación con los códigos de otros teléfonos. [ cita requerida ] Al transmitir, la palabra de código se utiliza para modular los bits de datos que representan el mensaje de voz. En el receptor, se realiza un proceso de demodulación para recuperar los datos. Las propiedades de esta clase de códigos permiten que muchos usuarios (con diferentes códigos) utilicen el mismo canal de radio al mismo tiempo. Para el receptor, las señales de otros usuarios aparecerán ante el demodulador solo como un ruido de bajo nivel. [ cita requerida ]
Otra clase general de códigos son los códigos de solicitud de repetición automática (ARQ). En estos códigos, el emisor añade redundancia a cada mensaje para comprobar si hay errores, normalmente añadiendo bits de comprobación. Si los bits de comprobación no son coherentes con el resto del mensaje cuando llega, el receptor pedirá al emisor que retransmita el mensaje. Todos los protocolos de red de área amplia, salvo los más sencillos, utilizan ARQ. Entre los protocolos más comunes se incluyen SDLC (IBM), TCP (Internet), X.25 (Internacional) y muchos otros. Existe un amplio campo de investigación sobre este tema debido al problema de hacer coincidir un paquete rechazado con un paquete nuevo. ¿Es un paquete nuevo o es una retransmisión? Normalmente se utilizan esquemas de numeración, como en TCP. "RFC793". RFCS . Grupo de trabajo de ingeniería de Internet (IETF). Septiembre de 1981.
Las pruebas grupales utilizan los códigos de una manera diferente. Consideremos un grupo grande de elementos en el que muy pocos son diferentes en un aspecto particular (por ejemplo, productos defectuosos o sujetos de prueba infectados). La idea de las pruebas grupales es determinar qué elementos son "diferentes" utilizando la menor cantidad posible de pruebas. El origen del problema tiene sus raíces en la Segunda Guerra Mundial , cuando las Fuerzas Aéreas del Ejército de los Estados Unidos necesitaban realizar pruebas a sus soldados para detectar la sífilis . [11]
La información se codifica de forma análoga en las redes neuronales del cerebro , en el procesamiento de señales analógicas y en la electrónica analógica . Los aspectos de la codificación analógica incluyen la corrección de errores analógicos, [12] la compresión de datos analógicos [13] y el cifrado analógico. [14]
La codificación neuronal es un campo relacionado con la neurociencia que estudia cómo las redes de neuronas representan la información sensorial y de otro tipo en el cerebro . El objetivo principal del estudio de la codificación neuronal es caracterizar la relación entre el estímulo y las respuestas neuronales individuales o del conjunto y la relación entre la actividad eléctrica de las neuronas del conjunto. [15] Se cree que las neuronas pueden codificar información tanto digital como analógica , [16] y que las neuronas siguen los principios de la teoría de la información y comprimen la información, [17] y detectan y corrigen [18] errores en las señales que se envían a través del cerebro y el sistema nervioso en general.
Hay cuatro tipos decodificación
![{\displaystyle \mathbb {P}[X=x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d04e6399915b2326b151a549d455f681833b7d1)
![{\displaystyle l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c917b0d3c751cb1d337c77c6e05d007733ee142d)
