Codificación de información

La codificación de la información se refiere a los medios de formalizar la información para poder manipularla, almacenarla o transmitirla. No le interesa el contenido sino solo la forma y el tamaño de la información a codificar.

Alfabeto, palabra, idiomas

Definiciones

Definimos un alfabeto como un conjunto de símbolos no vacíos, por ejemplo:

A = {a, b, c,…, z}, el alfabeto latino ;
A = {0,1,2,…, 9}, los llamados números arábigos
A = {0,1,…, 9, A, B,…, F}, los dígitos hexadecimales .
A = {0,1}, el alfabeto de la lógica booleana .
A = {A, T, G, C}, las bases del ADN que codifican nuestro genoma (este alfabeto es el tema principal de la bioinformática ).

Llamamos a una letra un elemento de un alfabeto .
Una palabra se llama serie finita de letras .
La secuencia de 0 letras se denomina palabra vacía y se indica ε.
Llamamos lenguaje a un conjunto de palabras asociadas a ciertas reglas de interpretación (sin esta última restricción, cualquier tabla de valores aleatorios podría llamarse lenguaje ). En el caso del ADN, estas reglas están contenidas en el ribosoma , en los lenguajes naturales, están contenidas en su léxico , en una computadora , están presentes en los circuitos de la unidad central .

Operaciones

Sea un alfabeto y un número natural . Denotamos el conjunto de todas las palabras de longitud over y el conjunto de todas las palabras de . Tenemos: ( cierre de Kleene ). Definimos la operación de concatenación que asocia una palabra que se compone de la secuencia de letras a partir de entonces la de . Ejemplo : "marc" "et sophie" = "marc et sophie" (las comillas se utilizan para delimitar los símbolos, no son elementos de ). $A$ $no$
$A ^ {n}$ $no$ $A$ $A ^ {*}$ $A$
$A ^ {*} = \ bigcup _ {{n \ geq 0}} ^ {{\ infty}} A ^ {n}$
$\ cdot: A ^ {*} \ times A ^ {*} \ rightarrow A ^ {*}$ $(u, v)$ $w$ $tu$ $v$
$\ cdot$ $A$

Propiedades :
- $\ cdot$ es asociativo : $\ forall u, v, w \ in A ^ {*}, (u \ cdot v) \ cdot w = u \ cdot (v \ cdot w)$
- $\ cdot$ admite ε como elemento neutro : $\ forall u \ in A ^ {*}, u \ cdot \ epsilon = \ epsilon \ cdot u = u$
- $\ cdot$ no es conmutativo .

Codificaciones y códigos

Codificación

Sean L y M dos idiomas.
Una codificación c de L en M es un morfismo inyectivo (para la operación ). En otras palabras, es una correspondencia entre las palabras de L y las de M, donde cada palabra de L está asociada con una sola palabra de M y tal que la codificación de los concatenados es igual a los concatenados de las codificaciones. ( ). $\ cdot$ $\ forall u, v \ in L, c (uv) = c (u) .c (v)$

Codigos

Una lengua L sobre un alfabeto A es un código si y solo si no hay dos factorizaciones diferentes de palabras con palabras de L. $A ^ {*}$