Manual de procedimientos administrativos

TEMA 1. TEORÍA DE CÓDIGOS.

Introducción

Definición: Consideremos un conjunto finito A={a1, a2, ... aq}, al que denominaremos alfabeto, a sus elementos, a1, a2, ... aq , les llamaremos letras o símbolos. Las sucesiones finitas de elementos de A se llaman palabras.



La palabra ai1ai2...ain se dice que tiene longitud n o bien que es una n-palabra.
Una palabra de longitud n se puedeconsiderar como un elemento del producto cartesiano de A por si mismo n veces, es decir, de:

El producto cartesiano está formado por todas las n-tuplas de A:



Esto es igual que una palabra, sólo cambia la notación.
El conjunto de todas las palabras sobre el alfabeto A se denotará como A* (con independencia de la longitud de las palabras).



Definición: Un código sobre el alfabeto Aes un subconjunto C de A*, (conjunto formado por palabras del alfabeto).
A los elementos del código C se les llama palabras de código.
El número de elementos del código C, que normalmente será finito, se denota por |C| y se denomina tamaño del código.
Si C es un código sobre A y A tiene q elementos (|A|=q) entonces se dice que C es un código q-ario. El ejemplo más normal de alfabeto usado enteoría de códigos es A = Z2 = {0,1}y tendremos así códigos binarios.
Ejemplo de código binario:

C = {0100,0010,0111}

Definición: Si C es un código cuyas palabras tienen todas la misma longitud n, decimos que C es un código de longitud fija o un código de bloques y a n se le llama longitud del código C.

El código C anterior es un código de bloques de longitud 4.

C = {011,1011, 10}  No es un código de bloques (no podemos hablar de la longitud del código)

Si C es un código de longitud n y tamaño m se dice que C es un (n,m)-código.

C = {0100,0010,0111} (4,3) código

Dado un alfabeto S al que denominaremos alfabeto fuente y dado un código C sobre el alfabeto A, se llama función de codificación a una aplicación biyectiva f:



S es el alfabeto en el cualestá la información que queremos codificar. Una aplicación biyectiva entre 2 conjuntos es una aplicación inyectiva (elementos diferentes tienen imágenes diferentes) y sobreyectiva (los elementos del conjunto C son imágenes de algún elemento de S, en este caso de 1 ya que la aplicación es inyectiva). A veces f no será una aplicación biyectiva; si f no fuese inyectiva habría varios símbolos del alfabetofuente que se codificarían de la misma forma, lo que haría la decodificación muy difícil. Cuando f es biyectiva hablamos de códigos descifrables.
En muchas ocasiones se le llama código a la función de codificación; pero nosotros le llamamos código al conjunto C (imagen de f).

Ejemplo:



Ejemplos de códigos:

• Polivio (año 208 a.C.) o código de fuego griego.



55 no se incluyeya que el alfabeto A tiene 24 letras. Un alfabeto A de longitud q tiene qn palabras de longitud n (qn = |An| )



Este es un (2,24) código. Este código persigue claridad, facilidad de transmisión de mensajes a distancia. Este código no permite detectar y/o corregir errores. Se piensa que este código se usaba para ocultar la información. En criptografía no se habla de código sino de cifras ocriptosistemas. Este código se denomina cifra de Polivio.

Damero de Polivio:

1 2 3 4 5
1  
2
3
4
5 

f(= 11 f(=12 .......

• Código Morse. Se usa para transmisiones telegráficas. Se usa para codificar un mensaje fuente en lenguaje natural.

S = {a, b, c ......z}
A = {., _, }

Se usan 3 símbolos: punto, raya y espacio.



Este código no esde longitud fija. Las letras más frecuentes se codifican con palabras cortas, mientras que las letras menos usadas se codifican con palabras más largas; esto se usa para conseguir más eficiencia, cuanto más frecuentes sean las letras más cortas son las palabras del código.
Los espacios se usan para separar palabras (6 espacios) o letras entre palabras (3 espacios). Este código no permite...