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 , criptografía , detección y corrección de errores , transmisión y 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 confiables. Normalmente, esto implica la eliminación de 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 ZIP reduce el tamaño de los archivos de datos, con fines tales como 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 agrega una 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. Es posible que el usuario normal no conozca muchas aplicaciones que utilizan la corrección de errores. Un disco compacto (CD) de música 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 móviles 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 canales para transmitir 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 cuál es la mejor manera de codificar la información que un remitente quiere transmitir. En este trabajo fundamental utilizó herramientas de la teoría de la probabilidad, desarrolladas por Norbert Wiener , que se encontraban en sus etapas incipientes 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 esencialmente inventaba 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 discreta de coseno (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 aparece con probabilidad .
Los datos están codificados por 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 clave .
La palabra clave de la cadena vacía es la propia cadena vacía:
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 transporten 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 asumido particular se denomina codificación de entropía .
Varias técnicas utilizadas por los esquemas de codificación 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 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 fuente elimina todos los datos superfluos para las necesidades del transmisor, lo que reduce el ancho de banda necesario para la transmisión.
El propósito de la teoría de codificación de canales es encontrar códigos que se transmitan rápidamente, contengan muchas palabras de código válidas y puedan corregir o al menos detectar muchos errores. Si bien no son mutuamente excluyentes, el desempeño en estas áreas es una compensación. 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 los arañazos.
Los CD utilizan codificación Reed-Solomon entrelazada para distribuir los datos en el disco. [3]
Aunque no es un código muy bueno, una simple repetición del código puede servir como 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 poco a poco y tomaremos una votación mayoritaria. El giro de esto es que no nos limitamos a enviar los bits en orden. Los intercalamos. El bloque de bits de datos se divide primero en 4 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 potentes que son muy eficaces para corregir el error de "explosión" de un rasguño o una mancha de polvo cuando se utiliza esta técnica de entrelazado.
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 ráfagas. Asimismo, los módems de banda estrecha están limitados por el ruido, presente en la red telefónica y también mejor modelado como una perturbación continua. [ cita requerida ] Los teléfonos celulares están sujetos a un rápido desvanecimiento . Las altas frecuencias utilizadas pueden causar un rápido desvanecimiento 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 necesaria ]
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 necesaria ]
La teoría de la codificación algebraica se divide básicamente en dos tipos principales de códigos: [ cita necesaria ]
Analiza las siguientes tres propiedades de un código, principalmente: [ cita necesaria ]
Los códigos de bloques 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 bloques 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 bloques lineales se resumen por sus alfabetos de símbolos (por ejemplo, binarios o ternarios) y parámetros ( n , m , d min ) [5] donde
Hay muchos tipos de códigos de bloques lineales, como
Los códigos de bloque están vinculados al problema del empaquetado 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 de un centavo sobre la mesa y júntelas. El resultado es un patrón hexagonal como el de un nido de abejas. Pero los códigos de bloque dependen de más dimensiones que no se pueden visualizar fácilmente. El poderoso código Golay (24,12) utilizado en las comunicaciones en el espacio profundo utiliza 24 dimensiones. Si se utiliza como código binario (que suele serlo), las dimensiones se refieren a la longitud de la palabra clave como se define anteriormente.
La teoría de la codificación utiliza el modelo de esfera N -dimensional. Por ejemplo, ¿cuántas monedas de un centavo se pueden empaquetar en un círculo sobre una mesa, o en 3 dimensiones, cuántas canicas se pueden empaquetar en un globo terráqueo? Otras consideraciones entran en juego a la hora de elegir un código. Por ejemplo, el empaquetado hexagonal en la restricción de una caja rectangular dejará espacios vacíos en las esquinas. A medida que las dimensiones aumentan, el porcentaje de espacio vacío disminuye. Pero en determinadas dimensiones, el embalaje ocupa 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 Hamming de distancia 3 con parámetros que satisfacen (2 r – 1, 2 r – 1 – r , 3), y el binario [23,12,7] y [11,6,5 ] códigos Golay ternarios. [4] [5]
Otra propiedad del código es el número de vecinos que puede tener una sola palabra de código. [6] Nuevamente, considere los centavos como ejemplo. Primero empaquetamos las monedas de un centavo 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 también crece el número de formas en que el ruido puede hacer que el receptor elija un vecino (y, por tanto, un error). 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 del síndrome-coset de los códigos de bloques lineales se utiliza en la conformación enrejada, [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.
Por lo tanto, generalmente encontramos la salida del codificador convolucional del sistema, que es la convolución del bit de entrada, contra los estados del codificador de convolución, registros.
Básicamente, los códigos convolucionales no ofrecen más protección contra el ruido que un código de bloque equivalente. En muchos casos, generalmente ofrecen una mayor simplicidad de implementación que un código de bloque de igual potencia. El codificador suele ser un circuito simple que tiene memoria de estado y cierta lógica de retroalimentación, normalmente puertas XOR . El decodificador se puede implementar en software o firmware.
El algoritmo de Viterbi es el algoritmo óptimo utilizado para decodificar códigos convolucionales. Existen simplificaciones para reducir la carga computacional. Se basan en buscar sólo los caminos más probables. Aunque no son óptimos, generalmente se ha descubierto que 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 militares y por satélite.
La criptografía o codificación criptográfica es la práctica y 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 de cajero automático , contraseñas de computadoras y comercio electrónico .
Antes de la era moderna, la criptografía era efectivamente 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 compartió la técnica de decodificación necesaria para recuperar la información original sólo con los destinatarios previstos, evitando 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 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 parte de cualquier adversario. Es teóricamente posible romper dicho sistema, pero no es factible hacerlo por ningún 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 de información teóricamente seguros que probablemente no se pueden romper ni siquiera con una potencia informática ilimitada (un ejemplo es el bloc de notas 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íneas se utiliza a menudo para el transporte de datos digitales.
La codificación de línea consiste en representar la señal digital a transportar mediante una señal discreta en amplitud y tiempo que está óptimamente sintonizada para las propiedades específicas del canal físico (y del equipo receptor). El patrón de forma de onda de voltaje o corriente utilizado para representar los 1 y 0 de datos digitales en un enlace de transmisión se llama codificación de línea . Los tipos comunes de codificación de líneas son la codificación unipolar , polar , bipolar y Manchester .
Otra preocupación de la teoría de la codificación es diseñar códigos que ayuden a la sincronización . Se puede diseñar un código de modo que se pueda detectar y corregir fácilmente un cambio de fase y que se puedan enviar múltiples señales en el mismo canal. [ cita necesaria ]
Otra aplicación de códigos, utilizada en algunos sistemas de telefonía móvil, es el acceso múltiple por división de códigos (CDMA). A cada teléfono se le asigna una secuencia de códigos que aproximadamente no está correlacionada con los códigos de otros teléfonos. [ cita necesaria ] Al transmitir, la palabra 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 códigos diferentes) utilicen el mismo canal de radio al mismo tiempo. Para el receptor, las señales de otros usuarios aparecerán para el demodulador sólo como un ruido de bajo nivel. [ cita necesaria ]
Otra clase general de códigos son los códigos de solicitud de repetición automática (ARQ). En estos códigos, el remitente agrega redundancia a cada mensaje para verificar errores, generalmente agregando bits de verificación. Si los bits de verificación no son consistentes con el resto del mensaje cuando llega, el receptor le pedirá al remitente que retransmita el mensaje. Todos los protocolos de red de área amplia, excepto los más simples, utilizan ARQ. Los protocolos comunes incluyen SDLC (IBM), TCP (Internet), X.25 (internacional) y muchos otros. Existe un extenso campo de investigación sobre este tema debido al problema de hacer coincidir un paquete rechazado con un paquete nuevo. ¿Es uno 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 códigos de una manera diferente. Consideremos un grupo grande de artículos en los que muy pocos son diferentes de una manera 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 de pruebas posible. 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 de sífilis a sus soldados . [11]
La información se codifica de manera 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 se ocupa de cómo la información sensorial y de otro tipo se representa en el cerebro mediante redes de neuronas . 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 de 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 de el cerebro y el sistema nervioso en general.
Hay cuatro tipos de codificació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)
