Conceptos de distancia de hamming

Problema de distancia de Hamming : en general, se supone que es más probable que haya menos errores que más errores . Esteenfoque de codificación del » peor de los casos » es intuitivamente atractivo en sí mismo. Sin embargo, está estrechamente relacionado con un modelo probabilístico simple donde los errores se introducen en el mensaje de forma independiente para cada símbolo y con una probabilidad fija p < 1/2 . Para hablar del “ número de errores ”se introduce la distancia de Hamming .

Definición : La distancia de Hamming entre dos enteros es el número de posiciones en las que los bits correspondientes son diferentes. No depende de los valores reales de xi y yi , sino solo si son iguales o no.

Proposición : La función d es una métrica. Es decir, para todo x, y, z ∈ A _N :

• 0 ≤ d(x, y) ≤ norte
• d(x, y) = 0 si y solo si x = y
• d(x, y) = d(y, x)
• d(x, z) ≤ d(x, y) + d(y, z) (desigualdad triangular)

Regla para decodificar : A continuación se muestran las reglas:

• Sea C un código de longitud N sobre un alfabeto A .
• La regla de decodificación del vecino más cercano establece que todo x ∈ A _N se decodifica en cx ∈ C que está más cerca de x .
• Es decir, D(x) = cx donde cx es tal que d(x, cx) = minc ∈ C{d(x, c)} .
• Si existe más de un c a esta distancia mínima, entonces D devuelve ⊥ .
• Distancia de código y detección y corrección de errores.
• Intuitivamente, un código es mejor si todas las palabras clave están separadas.

Noción formalizada :
Sea C un código. La distancia del código, indicada como d(C), está definida por:
 d(C) = min{d(c1, c2) | c1, c2 ∈ C, c1 6= c2}

Un código (N, M) de distancia d se denomina código (N, M, d) . Los valores N, M, d se denominan parámetros del código.