Distancia de Hamming


Definición


Dados dos elementos x,y ∈ An, llamamos distancia de Hamming entre x e y al numero de coordenadas distintas que poseen


In [41]:
# Vamos a definir la distancia de Hamming
# Para ello definimos primero lo que significa distancia entre dos palabras o elementos
def dv(x,y):
    distancia = 0
    for i in range(len(x)):
        if x[i] != y[i]:
            distancia = distancia + 1
    return distancia

In [42]:
# También podemos definir la distancia entre los elementos de un código C.
# Esta versión no aprovecha que la distancia es simétrica
def dc(C):
    distancias = set([dv(x,y) for x in C for y in C if x!=y])
    return min(distancias)

In [43]:
# La siguiente versión aprovecha que la distancia es simétrica
def dc_simetrica(C):
    distancia_minima = oo
    for i in range(len(C)):
        for j in range(i+1,len(C)):
            distancia = dv(C[i],C[j])
            if dv(C[i],C[j])<distancia_minima:
                distancia_minima=distancia
    return(distancia_minima)

Ejemplo 3.3 Códigos correctores. Distancia mínima de Hamming


In [44]:
a = vector([0,0,0])
b = vector([1,1,1])
C3 = (a,b)

In [45]:
print(dv(a,b))


3

Ejemplo 3.4 Códigos correctores. Distancia mínima de Hamming


In [46]:
dv(vector([0,0,0]),vector([0,1,1]))


Out[46]:
2

In [47]:
# Definimos el código C
C0 = (vector([0,0,0]),vector([0,1,1]),vector([1,0,1]),vector([1,1,0]))
print(dc_simetrica(C0))


2

No tengo claro que dc calcule la distancia mínima


In [48]:
C1 = (vector([0,0,0]),vector([0,1,1]),vector([1,0,1]),vector([1,1,0]),vector([1,1,1]),vector([0,0,1]))
print(dc_simetrica(C1))


1

In [49]:
C2 = (vector([0,0,0]),vector([0,1,1]),vector([1,0,1]),vector([1,1,0]),vector([1,1,1]))
print(dc_simetrica(C2))


1

Ejemplo 3.5 Códigos correctores. Distancia mínima de Hamming

Proposición 3.2

In [50]:
# Numero de errores (k) capaz de detectar nuestro código
k3 = dc(C3)-1
k0 = dc(C0)-1
print("El código C3 definido podrá detectar un máximo de " + str(k3) + " errores.")
print("El código C0 definido podrá detectar un máximo de " + str(k0) + " errores.")


El código C3 definido podrá detectar un máximo de 2 errores.
El código C0 definido podrá detectar un máximo de 1 errores.

In [0]: