Ledian

Hamming
Características Principales

Generalidades.
• Este código fue inventado por Richard Hamming en 1949.
• Es un código binario capaz de corregir errores de un bit por símbolo y de
detectar hasta dos errores de bit por símbolo, pero no de corregirlos.
• Es un código que se ha utilizado extensamente en las memorias RAM de
computadoras y resulta una buena elección cuando los errores sonaleatorios.
• Si los errores ocurren en ráfagas, como suele ocurrir en la transmisión
terrestre de televisión digital, es necesario utilizar otros códigos más
complejos como los códigos no binarios de bloque, o los códigos
convolucionales.

Generalidades.
• Código de bloque
• Usado en comunicaciones digitales
• Propiedades:

(n, k , d min) (2 m  1 , 2 m  1  m, m)

• ‘m’: Bits de paridad.
• Detecta‘e’ errores.

e d min 1
t

• Corrige ‘t’ errores.

d min 1
2

Generalidades.
• Cantidad de bits de Hamming debe cumplir la siguiente ecuación:
H

2

k  H  1

• H: cantidad de bits Hamming
• k: cantidad de bits en el carácter de datos

Ejemplo.
Ejemplo:
• Para la cadena de bits
101100010010
calcular la cantidad de bits Hamming necesarios para que el Código
Hamming pueda detectar el error.

k12
n  k ?

Ejemplo.
• Buscamos un n que satisfaga la condición…
n

2 k  n  1
n 4
n 5

2 4 16 12  4  1 17
5

2 32 12  5  1 18

• Se verifica que, 5 bits Hamming son suficientes para corregir
algún eventual error.
n 5
n  k 5

Ejemplo.
• La ubicación de los bits Hamming, se realiza de forma arbitraria…

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

H1 0 1 H1 0 0HH0 1 0 H0 1 0

Ejemplo.
• Para determinar la condición lógica de los bits de Hamming, se
expresan todas las posiciones del bit que contiene un “1” como
número binario:
Posición

Binario

2

00010

6

00110

12

01100

14

01110

16

10000

Ejemplo.
Posición

Binario

2

00010

6

00110

XOR1

00100

12

01100

XOR2

01000

14

01110

XOR3

00110

16

10000

XOR4

10110

Ejemplo.
• CódigoHamming:
B17

B13

B9

B8

B4

1 0 1 1 0
• Corriente de datos codificada en 17 bits
se transforma en:
H

H

H

H

H

11010100110100010

Ejemplo.
Probando el código…
Asumamos que durante la transmisión se presenta un
error en bit 14. Entonces, el stream sería:

1 1000100110100010
En el receptor, se determina la posición del
bit erróneo extrayendo los bits de Hamming
y haciendo XOR con el código binariopara
cada bit que contenga un “1”

Ejemplo.
Posición

Binario

Código
Hamming
2

10110

XOR1

10100

6

00110

XOR2

10010

12

01100

XOR3

11110

16

10000

XOR4

01110

00010

Codificación.
• Matriz Generadora ‘G’:
• Ik, matriz identidad.
• Q, matriz de m columnas :

G  I k Q 

• Columnas de peso 2 o superior
• Columnas linealmente independientes
• Mensaje enviado:

bˆ

• b : mensajeoriginal

bˆ b G

Decodificación.
• Matriz en el Rx, ‘H’
T
H  Q In  k



• In-k, matriz identidad

• Verificación:

T
ˆ
b H



Decodificación.
• Si el resultado es 0, recepción correcta
T
ˆ
b H 0

• Si no, el resultado corresponderá a una fila de HT, la posición de esa
fila, indica la posición del bit errado.
T
ˆ
b H 0

Ejemplo:
• Para la siguiente Matriz:
1
0
G 
0

0

• Y para lasecuencia de entrada:

0
1
0
0

b 0100

0
0
1
0

0
0
0
1

1
0
1
1

1
1
1
0

0
1
1

1

Ejemplo:
• Obtenemos:

bˆ b G 0100011
• Además la matriz H (en el receptor)
será:

 1 0 1 1 1 0 0
H 1 1 1 0 0 1 0
0 1 1 1 0 0 1

Ejemplo:
• Paralelamente:
1
0

1

T
H  1
1

0
0


1 0
1 1
1 1

0 1
0 0

1 0
0 1

Ejemplo:
• Finalmente si recepcionamos:

bˆ 0100011
•Obtendremos:
T
ˆ
b H 0

Ejemplo:
• Pero si recepcionamos con error:

bˆ 0100010
• Obtendremos:

T
ˆ
b H 001

Ejemplo:
• Revisando:

• Ultimo bit errado

1
0

1

H T  1
1

0
0


1 0
1 1
1 1

0 1
0 0

1 0
0 1

Modificaciones:
• Intercalar bits de redundancia
• Robustez
• Chequeo de paridad

Ejemplo:
• Los bits de paridad en las posiciones:

2 , x   0,..., (m ...