Siguiente: Decodificación única Arriba: Codificación Anterior: Codificación

Funciones de codificación

Sea $A$ un alfabeto finito y sea $C$ un alfabeto llamado de código. $C^+$ denota al conjunto de palabras no-vacías con símbolos en $C$. Una codificación es una función $\gamma:A\to C^+$. La imagen de $\gamma$ se dice ser el conjunto de palabras de código (codewords). $\gamma$ se extiende, mediante la mera concatenación de valores, a una función $\gamma^*:A^*\to C^+$, donde $A^*=\bigcup_{n\geq 0}A^n=A^+\cup\{\mbox{\rm nil}\}$, haciendo:

$$\gamma^*(\mbox{\rm nil}) = \mbox{\rm nil}\hspace{2em}, \hspac... ... A^*,a\in A:\ \gamma^*(\sigma a) = \gamma^*(\sigma)\,\gamma(a).$$

La codificación se dice ser de una decodificación única si $\gamma^*$ es una función inyectiva.

Ejemplo 2.1 (4-en-8)   Codifiquemos un alfabeto de 70 símbolos mediante un alfabeto consistente de tiras de 8 bits, 4 de los cuales están prendidos y los otros 4 apagados.

Sea $A$ un alfabeto de 70 símbolos, por ejemplo, $A$ podría ser el alfabeto que consta de las 26 letras minúsculas, las 26 mayúsculas, los 10 dígitos decimales y 8 símbolos de puntuación (entre los cuales está el ``blanco''). Sea $C=\{0,1\}$ el alfabeto de sólo dos símbolos y sea $C^8_e$ el conjunto de palabras de 8 bits en las que exactamente hay 4 bits con valor 1. Es claro que $\mbox{\rm card}\,(C^8_e) = {8\choose 4} = 70$ y que el conjunto $C^8_e$ está ordenado con el orden usual de los enteros cuando cada palabra se lee como la representación en base-2 de un entero: El primer elemento es pues $'00001111'$ y el último $'11110000'$. Sea $\gamma:A\to C^8_e$ la función que asocia el $i$-ésimo elemento de $A$ con el $i$-ésimo elemento de $C^8_e$. Una palabra de longitud $k$ en $A$ quedará entonces codificada por $8k$ bits. Cada bloque de 8 bits contiguos, de la forma $\varepsilon_{8\ell -7}\varepsilon_{8\ell -6}\cdots \varepsilon_{8\ell -1}\varepsilon_{8\ell}$, con $1\leq \ell\leq k$, contiene exactamente 4 1's. Naturalmente, de las $2^8=256$ palabras de 8 bits, hay $2^8-{8\choose 4} = 186$ que no son palabras de código. La decodificación es natural. Cada uno de los bloques de 8 bits contiguos determina un símbolo de $A$. $\Box$

Observación 2.1 (Terminología)   En la literatura técnica es común nombrar a una función de codificación como un código, e incluso, a su imagen, o sea al conjunto de palabras de código, se le llama también código. Así pues la palabra código tiene prácticamente cuatro connotaciones: el esquema $(\gamma, A, C)$, la función $\gamma$, el valor $\gamma(a)$ asociado a cada símbolo $a\in A$, y la propia imagen $\gamma(A)$. De estas cuatro, la mayormente supuesta en la Teoría de Códigos es la cuarta.

Si existe una $k\in\mathbb{N}$, $k>0$, tal que $\gamma(A)\subset C^k$, entonces el código se dice ser de bloques: cada símbolo se codifica mediante un bloque de $k$ símbolos.

Ejemplo 2.2 (ASCII)   El código ASCII (American Standard Code for Information Interchange) es un código por bloques de 8 bits (con una connotación inicial de 7 bits más 1 de paridad).

Por otro lado, el código se dice ser instantáneo si no ocurre que el código de un símbolo sea un prefijo del código de otro símbolo:

$$\forall a_1,a_2\in A:\ \left[\left[\exists \tau\in C^*: \gamma(a_2) = \gamma(a_1) \tau\right]\ \Rightarrow\ a_1 = a_2\right].$$

Ejemplo 2.3 (Código Morse)   Sea $\mbox{\it Latino}$ el alfabeto de las 26 letras mayúsculas y sea $\mbox{\it Cd}=\{\mbox{\tt p,r,e}\}$ el afabeto consistente de tres símbolos: punto, raya, espacio. El código es instantáneo y se muestra en la tabla 1

Recuadro 1: Código Morse. (a) En orden alfabético. (b) En orden de frecuencias en el idioma inglés.

A	pre	N	rpe
B	rpppe	O	rrre
C	rprpe	P	prrpe
D	rppe	Q	rrpre
E	pe	R	prpe
F	pprpe	S	pppe
G	rrpe	T	re
H	ppppe	U	ppre
I	ppe	V	pppre
J	prrre	W	prre
K	rpre	X	rppre
L	prppe	Y	rprre
M	rre	Z	rrppe

E	pe	O	rrre
T	re	H	ppppe
I	ppe	V	pppre
A	pre	F	pprpe
N	rpe	L	prppe
M	rre	P	prrpe
S	pppe	J	prrre
U	ppre	B	rpppe
R	prpe	X	rppre
W	prre	C	rprpe
D	rppe	Y	rprre
K	rpre	Z	rrppe
G	rrpe	Q	rrpre

(a)

(b)

El Código Morse es de decodificación única: ya que la codificación de cada símbolo termina con ``e'' (espacio), entre dos espacios contiguos cualesquiera se decodifica un único símbolo. También, al asignar códigos más cortos a símbolos más frecuentes, podrá esperarse que en el Código Morse los códigos de palabras serán de longitudes ``cortas''. $\Box$

Los códigos instantáneos deben su nombre a un procedimiento ``natural'' para decodificarlos: Leyéndolos de izquierda a derecha, cada vez que se reconoce el código de un símbolo se escribe ese símbolo y se reinicia el proceso de reconocimiento.

Siguiente: Decodificación única Arriba: Codificación Anterior: Codificación