Siguiente: Códigos lineales: Códigos rectangulares Arriba: Códigos binarios Anterior: Código por mayoría de

Distancia de Hamming

Para $n\in\mathbb{N}$ hay $2^n$ palabras de longitud $n$ con símbolos $0$, $1$. Sea $k\in[\![1,n]\!]$ y sea $K\subset[\![0,n-1]\!]$ un conjunto de índices de cardinalidad $k$. Sea $C\subset\mathbb{F}_2^n$ un conjunto de cardinalidad $2^k$ y sea $\gamma:\mathbb{F}_2^k\to C$ tal que existe $\iota:[\![0,k-1]\!]\to K$ biyectiva, con la condición:

$$\forall \mbox{\boldmath $\varepsilon$}\in\mathbb{F}_2^k\ \for... ...\left(\gamma(\mbox{\boldmath $\varepsilon$})\right)_{\iota(i)}.$$

Se dice que el código $\gamma$ posee $k$ bits de información y utiliza $n-k$ bits de revisión. El cociente $R_C=\frac{k}{n}$ es la razón de información del código $C$.

Por ejemplo, para el código por mayoría de votos visto en la sección anterior 4.1, $n$ es un número impar, $k=1$ y, por ejemplo, $K=\{0\}$. $C=\{0^n,1^n\}$ y $\gamma:\varepsilon\mapsto\varepsilon^n$. Entonces ese código tiene un solo bit de información, utiliza $n-1$ bits de revisión y su razón de información es $\frac{1}{n}$.

Ejemplo 4.1   Sea $C=\{\mbox{\boldmath$\varepsilon$}\in\mathbb{F}_2^n\vert\ \varepsilon_{n-1} = \left(\sum_{i=0}^{n-2}\varepsilon_i\right) \mbox{\rm mod }2\}$ el conjunto de palabras cuyo último símbolo es la paridad del bloque formado por los primeros $n-1$. Para $k=n-1$ y $K=[\![0,n-2]\!]$, las funciones $\gamma$ e $\iota$ quedan determinadas naturalmente: $\gamma:\mbox{\boldmath$\varepsilon$}\mapsto(\mbox{\boldmath$\varepsilon$},\sum_{i=0}^{n-2}\varepsilon_i)$, $\iota:i\mapsto i$. Entonces $\gamma$ es un código con $n-1$ bits de información y $1= n-(n-1)$ bit de revisión. La razón de información de este código es $\frac{n-1}{n}$.

Ejemplo 4.2   Sean $n=6$ y $k=3$. Definamos

$$\gamma: \begin{array}{ccc} 000 &\mapsto& 000000 \\ 001 &\m... ...110 &\mapsto& 110110 \\ 111 &\mapsto& 111000 %\\ \end{array}$$

Sea $K=[\![0,2]\!]\subset[\![0,5]\!]$ e $\iota:[\![0,2]\!]\to K$ la identidad. $\gamma$ es un código con $3$ bits de información y $3= 6-3$ bits de revisión, y su razón de información es $\frac{1}{2}$.

Observemos que en el ejemplo anterior, cualesquiera dos palabras en el código $C$ difieren en por lo menos 3 bits. Así pues, habiendo recibido una palabra $\mbox{\boldmath$\varepsilon$}\in\mathbb{F}_2^6$, si ésta no está en $C$ se reconoce que hay un error.

Las palabras con error pueden ser complementarias de palabras de código o las restantes (éstas son $2^6-2\cdot 8 = 2^6-2^4 = 2^4\cdot 3 = 48$) y para cada una de estas últimas habrá una única palabra $\mbox{\boldmath$\varepsilon$}'\in C$ que difiera de $\mbox{\boldmath$\varepsilon$}$ en tan solo un bit. Se toma entonces a la palabra correspondiente con $\mbox{\boldmath$\varepsilon$}'$ según $\gamma$ y de esta manera se corrige el error. (Para cada palabra complementaria de una palabra de código hay tres palabras de código que difieren de ella en dos bits.)

Definición 4.1 (Distancia de Hamming)   Sea $d_n:\mathbb{F}_2^n\times\mathbb{F}_2^n\to\mathbb{N}$,

$$\left(\mbox{\boldmath $\varepsilon$}_0,\mbox{\boldmath $\vare... ...[\![0,n-1]\!]\vert\ \varepsilon_{0j} \not = \varepsilon_{1j}\},$$

la función que a cada par de palabras le asocia el número de sus discordancias. Naturalmente, $d_n$ es una función distancia en $\mathbb{F}_2^n$, llamada de Hamming.

Definición 4.2   Para cada $\mbox{\boldmath$\varepsilon$}\in\mathbb{F}_2^n$ y $r\in\mathbb{N}$ la esfera de radio $r$ centrada en $\mbox{\boldmath$\varepsilon$}$ es

$$S(\mbox{\boldmath $\varepsilon$},r) = \{\mbox{\boldmath $\del... ...box{\boldmath $\varepsilon$},,\mbox{\boldmath $\delta$}) = r\},$$

y la bola de radio $r$ centrada en $\mbox{\boldmath$\varepsilon$}$ es

$$B(\mbox{\boldmath $\varepsilon$},r) = \{\mbox{\boldmath $\del... ... \bigcup_{s\in[\![0,r]\!]} S(\mbox{\boldmath $\varepsilon$},s).$$

Así, se tiene que $\mbox{\rm card}\,(S(\mbox{\boldmath$\varepsilon$},r))={n\choose r}$ y $\mbox{\rm card}\,(B(\mbox{\boldmath$\varepsilon$},r)) = \sum_{s\in[\![0,r]\!]}{n\choose s}$.

Definición 4.3   Para un punto $\mbox{\boldmath$\varepsilon$}\in\mathbb{F}_2^n$ y un conjunto $G\subset\mathbb{F}_2^n$ se define $d_n(\mbox{\boldmath$\varepsilon$},G) = \min\{d_n(\mbox{\boldmath$\varepsilon$},\mbox{\boldmath$\delta$})\vert\ \mbox{\boldmath$\delta$}\in G\}$. Para dos conjuntos $G_0,G_1\subset\mathbb{F}_2^n$ se define $d_n(G_0,G_1) = \min\{d_n(\mbox{\boldmath$\varepsilon$},G_1)\vert\ \mbox{\boldmath$\varepsilon$}\in G_0\}$.

Definición 4.4   Para un conjunto $G\subset\mathbb{F}_2^n$ su diámetro es

$$d_{n,max}(G) = \max\left\{d_n\left(\mbox{\boldmath $\varepsil... ...$\varepsilon$}_0,\mbox{\boldmath $\varepsilon$}_1\in G\right\}.$$

Su distancia mínima es

$$d_{n,min}(G) = \min\left\{d_n\left(\mbox{\boldmath $\varepsil... ... $\varepsilon$}_0\not=\mbox{\boldmath $\varepsilon$}_1\right\}.$$

Observación 4.1   Para cualquier código $C\subset\mathbb{F}_2^n$ tal que $\left(B(\mbox{\boldmath$\varepsilon$}, d_{n,min}(C)-1)\right)_{\mbox{\scriptsize\boldmath$\varepsilon$}\in C}$ sea un recubrimiento de $\mathbb{F}_2^n$ se tiene

• $C$ reconoce $t$ errores si y sólo si $d_{n,min}(C)>t$
• $C$ corrige $t$ errores si y sólo si $d_{n,min}(C)>2t$

En efecto, para la primera aseveración: Supóngase que se quiere enviar la palabra $\mbox{\boldmath$\varepsilon$}\in C$ y se recibe $\mbox{\boldmath$\delta$}\in\mathbb{F}_2^n$. Entonces pueden ocurrir dos casos. Si $\mbox{\boldmath$\delta$}\not\in C$, se habrá detectado un error y como éste está en una bola de radio $d_{n,min}(C)-1$ con centro en un punto de $C$ se ve que hay menos de $d_{n,min}(C)$ errores. Si, por lo contrario, $\mbox{\boldmath$\delta$}\in C$, entonces bien $\mbox{\boldmath$\delta$}=\mbox{\boldmath$\varepsilon$}$, en cuyo caso no hay error, o bien $d_n(\mbox{\boldmath$\delta$},\mbox{\boldmath$\varepsilon$})\geq d_{n,min}(C)$ y no será posible detectar los más de $t$ errores cometidos.

La segunda aseveración se sigue de lo siguiente: Supóngase que se quiere enviar la palabra $\mbox{\boldmath$\varepsilon$}_0\in C$ y se recibe $\mbox{\boldmath$\delta$}\in\mathbb{F}_2^n$ con a lo sumo $t$ errores. Entonces $d_n(\mbox{\boldmath$\delta$},\mbox{\boldmath$\varepsilon$}_0)\leq t$. Sea $\mbox{\boldmath$\varepsilon$}_1\in C$ una palabra en el código, distinta de la enviada. Entonces $d_n(\mbox{\boldmath$\varepsilon$}_0,\mbox{\boldmath$\varepsilon$}_1)\geq d_{n,min}(C)$. Resulta pues

$$d_n(\mbox{\boldmath $\delta$},\mbox{\boldmath $\varepsilon$}_... ...$\delta$},\mbox{\boldmath $\varepsilon$}_0) > d_{n,min}(C) - t.$$

Por tanto: $d_n(\mbox{\boldmath$\delta$},\mbox{\boldmath$\varepsilon$}_0) >t\ \Leftrightarrow\ d_{n,min}(C)>2t$. $\Box$

Definición 4.5   Un código $C\subset\mathbb{F}_2^n$ con $k$ bits de información y $n-k$ bits de revisión se dice ser un código-$[n,k]$. En este caso se dice también que $k$ es la dimensión de $C$ y que $n$ es su longitud. Todo código-$[n,k]$ de distancia mínima $d$ se dice ser un código-$[n,k,d]$.

La observación 4.1 se reformula como la siguiente:

Observación 4.2   Todo código-$[n,k,d]$ puede corregir menos de $\left\lfloor\frac{d}{2}\right\rfloor$ errores.

Ejemplo 4.3   Sean $n=5$ y $k=2$. Definamos

$$\gamma: \begin{array}{ccc} 00 &\mapsto& 00000 \\ 01 &\maps... ...\ 10 &\mapsto& 11100 \\ 11 &\mapsto& 11011 %\\ \end{array}$$

Sea $K=\{0,3\}\subset[\![0,4]\!]$ e $\iota:[\![0,1]\!]\to K$, $i\mapsto 3 i$. Se tiene que $\gamma$ es un código-$[5,2]$ y su razón de información es $\frac{2}{5}$. Su distancia mínima es $3$, por lo que es un código-$[5,2,3]$

Por la observación 4.2, se tiene que puede corregir un solo bit. Alrededor de cada palabra de código, la bola de radio 1 consiste de ${5\choose 0}+{5\choose 1}=1+5=6$ elementos. Se tiene;

$$\begin{eqnarray*} B(00000,\, 1) &=& \{00000 , 00001 , 00010 , 00100 , 01000 , 10... ...011,\, 1) &=& \{11011 , 11010 , 11001 , 11111 , 10011 , 01011\} \end{eqnarray*}$$

Estas bolas son ajenas a pares y su unión consiste de 24 palabras. Las restantes $8=2^5-24$ equidistan en 2 de dos palabras de código. $\Box$

Siguiente: Códigos lineales: Códigos rectangulares Arriba: Códigos binarios Anterior: Código por mayoría de