Teoría del código
En la teoría de la información , la teoría de la codificación se ocupa de los códigos y sus propiedades y su capacidad para servir en varios canales de comunicación . Hay dos modelos de comunicación: con y sin ruido . Sin ruido, la codificación de la fuente es suficiente para la comunicación. Con ruido, la comunicación es posible con códigos correctivos .
Historia
Al definir la información de forma tan matemática , Claude Shannon tomó la etapa fundacional de la teoría de la codificación . Existen otras definiciones, pero la entropía de Shannon ha sido la más exitosa. Por lo tanto, uno puede responder a las dos preguntas fundamentales de la teoría de la información : cuáles son los recursos necesarios para la transmisión de información y cuánta información se puede transmitir de manera confiable.
La teoría del código se ocupa de esta última cuestión de la codificación de canales . Al responder a las dos preguntas básicas de la teoría de la información, Shannon simplemente no pudo proporcionar un conjunto muy poderoso de códigos correctivos . En particular, no ha determinado un ejemplo de código que alcance el límite proporcionado por su teorema de codificación de canal.
Es este vacío el que llena la teoría del código. Hay una multitud de métodos hoy en día destinados a producir buenos códigos correctivos.
Propiedades del código
Los códigos se distinguen primero por la cantidad de información transmitida por un símbolo . El canal binario simétrico siendo la más común, que a menudo se considere un código binario . Sin embargo, también existen códigos trinarios y, en general, códigos q-arios.
Los siguientes nombres de variables se utilizan principalmente por convención. es un código que contiene palabras de código , es decir, de dimensión M. La longitud de una palabra de código se indica mediante . Tal código se llama código .
Detección y corrección de errores
La mayoría de los códigos se utilizan para la detección de errores o para la corrección de errores.
Distancia mínima y decodificación
La distancia mínima de un código influye en la probabilidad de error de decodificación. La distancia mínima es un parámetro importante, denotado . Tal código se llama código .
Familias de códigos
Códigos equivalentesDos códigos son equivalentes si todas sus propiedades de corrección de errores son iguales.
Tipos de códigosGeneralmente hay tres tipos de códigos.
- Un código lineal es un código de corrección sobre el que se impone una estructura de espacio vectorial .
- Un código cíclico es un código de corrección que tiene más estructura que la de un espacio vectorial. En general, puede pensar en las palabras de código como polinomios . Ejemplo: el código Reed-Solomon .
- Un código no lineal es un código de corrección que se puede construir de diversas formas, sin obtener la estructura de un espacio vectorial.
Hay una pequeña cantidad de casos especiales. Un código trivial es un código que copia literalmente el mensaje inicial, de ahí su trivialidad . Un código sistemático es un código para el cual el mensaje a codificar se incluye en el mensaje codificado.
Además, ciertos códigos correctivos se pueden utilizar como códigos cuánticos .
Otros tipos importantes de códigos son:
- codigo algebraico
- codigo aleatorio
Los códigos de corrección también se pueden clasificar por familias.
- Un código de paridad agrega uno o más bits de paridad al mensaje.
- Un código de repetición envía múltiples copias de cada bit para ser transmitido.
- Los códigos Hamming son la familia más conocida. Los códigos de Hamming binarios son equivalentes a los códigos cíclicos y algunos no binarios también lo son.
- Un código Golay es un código lineal que se considera importante en la teoría y en la práctica.
- Un código Reed-Müller es un código lineal cuyas propiedades de decodificación se consideran particularmente prácticas.
- Los códigos BCH son una generalización de los códigos Hamming . Estos también son códigos cíclicos. Un caso especial es el código Reed-Solomon .
- Un código de residuo cuadrático es un código cíclico basado en el residuo cuadrático .
- Un código Goppa que, como los códigos cíclicos, se basa en un polinomio, llamado polinomio Goppa.
- Un código estabilizador se basa en la medición de un síndrome , es decir de un vector en .
- Un código de expansión (in) es un código lineal con el que aún es posible corregir una fracción constante de errores.
- El código de superconcentrador Spielman son los únicos códigos que se pueden codificar y decodificar en tiempo lineal.
- Un código alterno es un código lineal de importancia práctica.
- Un código Hadamard es un código generado a partir de una matriz Hadamard .
- Un código LDPC es un código que tiene una matriz de paridad escasa.
Se pueden obtener nuevos códigos de operaciones que combinan uno o dos códigos base.
- operaciones triviales: punzonado o acortamiento
- concatenación: código Forney , código Justesen (en)
- producto
También distinguimos ciertas clases de códigos por sus propiedades.
- código de intersección
- código de separación
- (2014) disimile y hoe = 111110110
Código y "diseño"
Existe una conexión entre códigos y diseños combinatorios .
El principal problema con la teoría del código.
Sea el más grande para el que hay un código y un cuestionario. El principal problema de la teoría del código es determinar estos valores.
Codificación de fuente
El objetivo de la codificación fuente puede ser comprimir la información repetitiva del lenguaje, su redundancia . Para cualquier idioma, podemos considerar la entropía de un mensaje, es decir la cantidad de información transmitida. Esto da lugar al teorema de la codificación de fuentes .
Codificación de canal
El objetivo es agregar información redundante a un mensaje para compensar el ruido en el canal de comunicación . Esto da lugar al teorema de codificación de canales y es a esto a lo que debemos el origen de la teoría del código .
Algunos problemas criptográficos se basan en el supuesto de la dificultad de decodificar.
Teoría del código algebraico
La teoría del código algebraico es un subcampo de la teoría del código donde las propiedades de los códigos se expresan algebraicamente. En otras palabras, el enfoque es algebraico en oposición al enfoque tradicional que es probabilístico . Principalmente estudiamos:
- la construcción de códigos "buenos", es decir con ciertos parámetros deseables, tales como:
- la longitud de las palabras de código
- el número total de palabras de código válidas
- la distancia mínima de Hamming entre dos palabras de código válidas
- decodificación eficiente de estos códigos
Usos en el análisis de texto
El análisis de código es útil para intentar decodificar texto cifrado, si el código utilizado es débil (por ejemplo, código César o Vigenère ). La detección de las características estadísticas de un texto también permite comprobar, incluso sin comprender el idioma, si un texto ha tenido más de un autor (podemos así afirmar que el Papiro Voynich tuvo dos autores distintos; ver artículo correspondiente). También permite analizar textos de Víctor Hugo y, a través de estas características estadísticas, detectar la década de su redacción. El IBM Scientific Center también estudió los discursos de Charles de Gaulle y demostró que estos discursos se alargaban con el tiempo, salvo algunos discursos "críticos" (como el del30 de mayo de 1968). La Universidad de Stanford también comparó los vocabularios respectivos por Marcel Proust y Paul Valéry . El ingeniero Jean-Jacques Walter también realizó este análisis sobre el texto del Corán y defendió una tesis de Estado atribuyéndole, según él también, varias decenas de autores (al menos 30 autores diferentes, probablemente 50, como máximo 100), inicialmente en varios idiomas, durante un período de doscientos años.
En la literatura de ficción, esta teoría sirve de pivote para el periodista de Le Monde Robert Escarpit en su libro Le Littératron donde un especialista utiliza una computadora para construir a partir de comentarios hechos en conversaciones en cafés el último discurso populista , que en primer lugar suscita las burlas. , pero poco a poco muestra una formidable efectividad.
Referencias
- Prefacio (en) Elwyn R. Berlekamp , Teoría de la codificación algebraica , McGraw-Hill , 1968, 466 p.
- Entrevista a Jean-Jacques Walter 10/8/2013 en el programa "Le Grand Witness"
- Análisis estadístico del Corán .
Ver también
Artículos relacionados
Bibliografía
Obras- Jean-Guillaume Dumas, Jean-Louis Roch, Éric tannier y Sébastien Varrette, la teoría de código (compresión, encriptación, la corrección) , Dunod , 2013, 2 ª ed. ( 1 st ed. 2007), 384 p. ( ISBN 978-2-10-059911-0 ) [ presentación en línea ]
- Bruno Martin, Codificación, criptología y aplicaciones , Lausana, Prensas politécnicas et universitaire romandes ,2004, 354 p. ( ISBN 978-2-88074-569-1 , leer en línea ).
- Adam Woryna , " Sobre la proporción de códigos de prefijo en el conjunto de códigos de tres elementos ", Matemáticas discretas , vol. 343, n o 8,2020, Artículo n o 111939 ( DOI 10.1016 / j.disc.2020.111939 ).
enlaces externos
- Christine Bachoc, “ Curso de código ” , en la Universidad de Burdeos I , 2004-2005
- Joël Le Roux, Nociones de comunicación digital , Polytech Nice-Sophia , 2001
- Yves Denneulin, Jean-Guillaume Dumas, Gregory Mounié, Jean-Louis Roch, Karim Samaké, Eric Tannier, Sébastien Varrette, "Teoría de los códigos (folleto, por supuesto)" (versión del 15 de septiembre de 2008 en Internet Archive ) , en ENSIMAG