ejemplo codigo hamming.pdf
TRANSCRIPT
Código Hamming
Detección y corrección de errores
08/02/2014 I.M. Luis Angel Martinez Cabrera 1
Información
Publicado en 1950 por Richard Hamming.
Se puede detectar error en un bit y corregirlo.
Para errores en dos bits se utiliza Hamming extendido (pero no corrige).
Se utiliza para reparar errores en la trasmisión de datos, donde puede haber perdidas.
08/02/2014 I.M. Luis Angel Martinez Cabrera 2
Bits paridad/Bits datos
Agrega tres bits adicionales de
comprobación por cada cuatro bits de
datos del mensaje.
Bits de paridad: Bits cuya posición es
potencia de 2 (1,2,4,8,16,32,64,…)
Bits de datos: Bits del resto de posiciones
(3,5,6,7,9,10,11,12,13,14,15,17…)
08/02/2014 I.M. Luis Angel Martinez Cabrera 3
Algoritmo
Cada bit de paridad se obtiene con la
paridad de algunos de los bits de datos:
Posición 1 : Salta 0, Comp 1, Salta 1, Comp 1…
Posición 2 : Salta 1, Comp 2, Salta 2, Comp 2…
Posición 4 : Salta 3, Comp 4, Salta 4, Comp 4…
Posición n : Salta n-1, Comp n, Salta n, Comp n..
08/02/2014 I.M. Luis Angel Martinez Cabrera 4
Ejemplo: 0110101
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7
Palabra s/p 0 1 1 0 1 0 1
P1
P2
P3
p4
Palabra c/p
08/02/2014 I.M. Luis Angel Martinez Cabrera 5
Ejemplo: 0110101
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7
Palabra s/p 0 1 1 0 1 0 1
P1 1 0 1 0 1 1
P2
P3
p4
Palabra c/p
08/02/2014 I.M. Luis Angel Martinez Cabrera 6
Ejemplo: 0110101
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7
Palabra s/p 0 1 1 0 1 0 1
P1 1 0 1 0 1 1
P2 0 0 1 0 0 1
P3
p4
Palabra c/p
08/02/2014 I.M. Luis Angel Martinez Cabrera 7
Ejemplo: 0110101
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7
Palabra s/p 0 1 1 0 1 0 1
P1 1 0 1 0 1 1
P2 0 0 1 0 0 1
P3 0 1 1 0
p4
Palabra c/p
08/02/2014 I.M. Luis Angel Martinez Cabrera 8
Ejemplo: 0110101
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7
Palabra s/p 0 1 1 0 1 0 1
P1 1 0 1 0 1 1
P2 0 0 1 0 0 1
P3 0 1 1 0
P4 0 1 0 1
Palabra c/p
08/02/2014 I.M. Luis Angel Martinez Cabrera 9
Ejemplo: 0110101
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7
Palabra s/p 0 1 1 0 1 0 1
P1 1 0 1 0 1 1
P2 0 0 1 0 0 1
P3 0 1 1 0
P4 0 1 0 1
Palabra c/p 1 0 0 0 1 1 0 0 1 0 1
08/02/2014 I.M. Luis Angel Martinez Cabrera 10
Comprobando Error
Ahora supongamos que el 3° bit de
derecha a izquierda cambia de 1 a 0, la
nueva palabra seria:
10001100101 => 10001100001
08/02/2014 I.M. Luis Angel Martinez Cabrera 11
Comprobando Error
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7 Bit paridad
Palabra s/p 0 1 1 0 0 0 1
P1 1 0 1 0 0 1
P2 0 0 1 0 0 1
P3 0 1 1 0
P4 0 0 0 1
Palabra c/p 1 0 0 0 1 1 0 0 0 0 1
08/02/2014 I.M. Luis Angel Martinez Cabrera 12
Comprobando Error
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7 Bit paridad
Palabra s/p 0 1 1 0 0 0 1
P1 1 0 1 0 0 1 1
P2 0 0 1 0 0 1
P3 0 1 1 0
P4 0 0 0 1
Palabra c/p 1 0 0 0 1 1 0 0 0 0 1
08/02/2014 I.M. Luis Angel Martinez Cabrera 13
Comprobando Error
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7 Bit paridad
Palabra s/p 0 1 1 0 0 0 1
P1 1 0 1 0 0 1 1
P2 0 0 1 0 0 1 0
P3 0 1 1 0
P4 0 0 0 1
Palabra c/p 1 0 0 0 1 1 0 0 0 0 1
08/02/2014 I.M. Luis Angel Martinez Cabrera 14
Comprobando Error
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7 Bit paridad
Palabra s/p 0 1 1 0 0 0 1
P1 1 0 1 0 0 1 1
P2 0 0 1 0 0 1 0
P3 0 1 1 0 0
P4 0 0 0 1
Palabra c/p 1 0 0 0 1 1 0 0 0 0 1
08/02/2014 I.M. Luis Angel Martinez Cabrera 15
Comprobando Error
p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7 Bit paridad
Palabra s/p 0 1 1 0 0 0 1
P1 1 0 1 0 0 1 1
P2 0 0 1 0 0 1 0
P3 0 1 1 0 0
P4 0 0 0 1 1
Palabra c/p 1 0 0 0 1 1 0 0 0 0 1
08/02/2014 I.M. Luis Angel Martinez Cabrera 16
Corrigiendo error
Los bits de paridad nos dicen que el error esta en
la posición:
1001 = 9
El error está en el 9° bit:
10001100001
El número original era: 10001100101 = 0110101
08/02/2014 I.M. Luis Angel Martinez Cabrera 17