Conceptos Clave en Codificación y Teoría de la Información

Conceptos Fundamentales de Codificación

Tipos de Códigos

Código de longitud constante: Código cuya longitud de palabra es la misma para todas las palabras que lo componen.

Código no singular: En un código no singular, todas las palabras deben ser diferentes.

Extensión de un código: Llamamos extensión de orden k de un código a aquel que hace corresponder las secuencias de k mensajes a las correspondientes secuencias de k palabras del código.

Código unívocamente decodificable: Se dice que un código es unívocamente decodificable si es no singular para cualquier extensión k del mismo.

Códigos instantáneos: Un código unívocamente decodificable es instantáneo si no necesitamos conocer los símbolos que suceden a una palabra para decodificarla.

Estos códigos se caracterizan porque ninguna de las palabras que lo componen es prefijo de otra.

Propiedades de los Códigos

Eficiencia: Cociente entre la entropía y la longitud media del código.

Redundancia: Complemento a 1 de la eficiencia.

Información y Errores

Conceptos de Información

Información mutua: Definimos la información mutua como la información que aporta una variable sobre otra.

Tipos de Errores

Error de desbordamiento: Error debido a que el resultado de una determinada operación es mayor o menor que los valores que se encuentran en el rango de representación del código.

Error de redondeo: Error debido a que el resultado de una determinada operación no puede representarse con la precisión del código que usamos.

Representación Numérica

Complemento a la base menos 1

Números enteros:

• Rango: [(2^p-1-1), -(2^p-1-1)]
• Precisión: 1
• Ventajas: Permite la operación directa sobre los números.

Números reales:

• Rango: [(2^p-1-1)+(1-2^-q), -(2^p-1-1)+(1-2^-q)]
• Precisión: 2^-q
• Ventajas: Sigue pudiéndose hacer operaciones aritméticas simplemente sumando.

Desventajas (tanto para los números enteros como para los reales): Tiene dos representaciones para el 0.

Complemento a la base (II)

• Rango: [(2^p-1-1)+(1-2^-q), -2^p-1]
• Precisión: enteros 1 y reales 2^-q
• Ventajas: Las mismas del complemento a 1, más que se tiene una única representación para el 0.
• Desventajas: El rango es asimétrico.

Componentes de la Representación

Signo: Positivo o negativo.

Mantisa: Representación del número positivo.

Exponente: Número entero que fija el valor al que se eleva la base para obtener el número.

Codificación de Caracteres

ASCII

• Símbolos insuficientes para algunas aplicaciones.
• Existen versiones ampliadas (no todos los símbolos tienen la misma longitud).
• Están basados en el alfabeto latino.

Unicode

• Universalidad: Pretende que se puedan representar la mayoría de los lenguajes escritos.
• Unicidad: A cada carácter se le asigna un único código.
• Uniformidad: Todos los símbolos se representan con un número fijo de dígitos binarios.

Métodos de Codificación

Método de Shannon-Fano

1. Dividimos el conjunto de mensajes en tantos grupos como elementos tenga el alfabeto que utilizamos.
2. Se asigna uno de los símbolos del alfabeto a cada grupo.
3. Se subdivide tantas veces como sea necesario aplicando los pasos anteriores hasta que todos los grupos contengan un único mensaje.

Método de Huffman

1. Ordenamos los mensajes por orden decreciente de probabilidad.
2. Asignamos como último símbolo de la palabra código.
3. Unimos los dos últimos mensajes y formamos.

Códigos Detectores y Correctores de Errores

Distancia entre palabras de código

Distancia entre palabras de código: Número de bits diferentes entre dos palabras del código.

• La distancia mínima debería ser al menos 2 para detectar un error.
• Para detectar k errores, la distancia mínima entre palabras del código debería ser al menos de k+1.

Códigos Detectores y Correctores

Este tipo de códigos son construidos de manera que permiten la detección de errores y la corrección de los mismos.

Para ello, añadimos unos dígitos de control al código original.

Códigos de Hamming

Códigos de Hamming: Son códigos detectores y correctores de errores. A partir de los dígitos de control que añadimos, somos capaces de determinar la posición del error cometido.

Teoría de la Computación

Conceptos Fundamentales

Teoría de la computabilidad: Es la parte de la computación que se encarga de determinar si un problema dado puede ser resuelto mediante un algoritmo.

Algoritmo: Conjunto de reglas ordenadas que permiten efectuar un cálculo. La ejecución de un algoritmo no debe implicar decisiones subjetivas.

Máquina de Turing

Máquina de Turing: Modelo abstracto de un computador. Cualquier función computable puede ser llevada a cabo por una máquina de Turing en un número finito de pasos.

Máquina de Turing (II): Está compuesta por una cinta de longitud infinita. La cinta se encuentra dividida en celdas. En cada celda queda registrado un determinado carácter. Se define un cabezal que se desplaza sobre la cinta; el desplazamiento puede ser hacia la izquierda y hacia la derecha.