Teorema De Hamming

´
CAP´ITULO 3. CODIFICACION

67

{Y1 } = {f (Xk , Xkc )}
{Y2 } = {f (Xk , Xkc )}
..
..
.
.
{YL } = {f (Xk , Xkc )}

3.5.

Teorema de Hamming

3.5.1.

Peso y distancia Hamming

(3.5)

La idea desimilaridad es m´as consistente debido a la definici´on de la distancia Hamming. Sean
{Xi } y {Xj } dos secuencias binarias de la misma longitud i, j = 1, ..., K, la distancia Hamming
entre ellas es el n´umero de s´ımbolos en que difieren. Siendo W ({Xi }) el peso de Hamming de una
secuencia y {Xi } el n´
umero de unos de la secuencia, la distancia Hamming dij = d ({Xi } , {Xj })
est´a dada por:
dij =W ({Xi } ⊕ {Xj })

(3.6)

Donde ⊕ es la operaci´on suma m´odulo 2 entre las secuencias.
Ejemplo 3.1 Halle la distancia Hamming para las secuencias
{X}0 = 000

{X}1 = 111

Usando 3.6:
d01 = W (000 ⊕111) = 3
Para la detecci´on de errores, considere un sistema de transmisi´on que al codificar, genera un
alfabeto con un n´
umero N de secuencias {Xi }n , n = 1 · · · N , y una de esas secuencias setransmite
sobre el canal. Debido a los errores, se recibe {Yj }. El decodificador entonces determina que la
secuencia enviada es aquella del alfabeto generado, cuya distancia Hamming entre {Yj } y {Xi}n
sea minima.
Ejemplo 3.2 Un codificador contiene el siguiente alfabeto generado:
a. 10000
b. 01100
c. 10011

(3.7)

Se env´ıa una secuencia, pero hay un error de bit simple y se recibe 10001, se notaque la
secuencia “m´
as cercana” es, en efecto, 10000 y que se ha encontrado la secuencia correcta.
Para dise˜
nar un buen c´odigo, se trata de asegurar que la distancia Hamming entre posiblesc´odigos {Xi } sea m´as larga que la distancia Hamming proveniente del error. Por lo que el decodificar puede describirse como: “Elegir la palabra de c´odigo con la m´ınima distancia Hamming de la
palabrarecibida”. Un c´odigo con todas las palabras distintas debe tener al menos una distancia de
Hamming m´ınima. Las prestaciones de un c´odigo continuo no s´olo dependen de un buen algoritmo
de...