CONSTRUCCIÓN Y
USO DE UN CÓDIGO HAMMING DE PALABRAS CON CUATRO DÍGITOS NO REDUNDANTES
1.- Tareas
en el sistema emisor
Cada palabra consta inicialmente de 4 bits. Se trata
de añadir a cada palabra un número p
de bits y formar palabras de 4+p
bits. La transmisión se realiza después
de esta ampliación. Se supone que durante la transmisión se puede alterar
alguno de los 4+p bits. Pero sólo uno, es decir, que la
probabilidad de error en más de un bit es despreciable. Utilizaremos una de las
2p combinaciones binarias de los bits añadidos para indicar la
ausencia de error; y el resto de las 2p combinaciones para indicar
cuál de los bits es el alterado durante
la transmisión (puede ser uno cualquiera de los 4+ p). Por esto, el mínimo p
debe cumplir:
2p – 1 ³ 4 + p (Ec. 1)
El menor p que verifica esta condición es p=4.
Inicialmente, las palabras tienen este formato:
Numeramos los bits de esta manera (más adelante se
verá por qué esta forma tan rara de numerarlos):
El emisor añade los bits p1, p2 y p3 teniendo en cuenta estas dos normas:
1ª.- Los
bits de paridad pi se
intercalan en las posiciones cuyo número es potencia de 2, es decir, tienen un
único 1 en el código binario puro de dicho número.
Nº |
valores |
Bits de la nueva palabra |
||
01 |
001 |
p1 |
||
02 |
010 |
p2 |
||
03 |
011 |
D3 |
||
04 |
100 |
P4 |
||
05 |
101 |
D5 |
||
06 |
110 |
D6 |
||
07 |
111 |
(Tabla 1) |
2ª.- Cada
uno de los nuevos bits pi se construye con una operación EXOR en cascada
de los bits iniciales (Di) cuyo número de posición tiene un 1 en el mismo sitio
del pi en cuestión:
p1 = D3 Å D5 Å D7
p2
= D3 Å D6 Å D7 (Ec. 2)
p4
= D5 Å D6 Å D7
Las palabras, ya preparadas para ser enviadas,
tienen este formato:
Debido al ruido presente en el canal, puede ser
alterado uno de los bits (suponemos que sólo uno). Este es también el formato
en el que le llegan al sistema receptor. A continuación vamos a explicar el mecanismo
hardware que utiliza el sistema receptor para detectar si hubo error; y en tal
caso, averiguar cuál es el bit erróneo para efectuar la corrección.
2.- Tareas
en el sistema receptor
En primer lugar, a partir de los 7 bits, construye
tres nuevas variables ci que llevarán a cabo funciones de señales de
control. Las define así:
c1 = p1 Å D3 Å D5 Å D7
c2
= p2 Å D3 Å D6 Å D7 (Ec. 3)
c3
= p3 Å D5 Å D6 Å D7
Recordamos que las definiciones no hay que demostrarlas.
Son objetos cuya aceptación dependerá de su utilidad para conseguir algún
objetivo, como la demostración de algún teorema posterior; o en este caso, la
implementación de un mecanismo hardware.
En segundo lugar, a partir de las señales de control
ci , construye (define) 8
funciones de error, de esta manera:
Señales de control |
Funciones de error |
|||||||
c3 c2 c1 |
OK |
ep1 |
ep2 |
ED3 |
ep4 |
ED5 |
ED6 |
ED7 |
0 0 0 0 0
1 0 1
0 0 1
1 1 0
0 1 0
1 1 1
0 1 1
1 |
1 0 0 0 0 0 0 0 |
0 1 0 0 0 0 0 0 |
0 0 1 0 0 0 0 0 |
0 0 0 1 0 0 0 0 |
0 0 0 0 1 0 0 0 |
0 0 0 0 0 1 0 0 |
0 0 0 0 0 0 1 0 |
0 0 0 0 0 0 0 1 |
(Tabla 2)
(Ec. 4)
2.1.- Detección
Como puede verse de (3) y de la tabla 2:
Un error
en Di provoca un 1 en EDi.
Un error
en pi provoca un 1 en epi.
Para saber cuál es el bit erróneo, basta con sondear
cuál de las funciones de error está a
1. Vemos ahora la utilidad de los dos conjuntos de definiciones.
2.2.- Corrección
Ya sabemos cómo detectar el error. Pero hay que ir
más lejos. El sistema de recepción debe estar diseñado de forma que su usuario
no tenga que saber si hubo error; y en tal caso, saber dónde está para
corregirlo manualmente. Es el sistema
receptor quien debe hacer una corrección automática.
Para ello se hacen estas asociaciones :
ei Di
de entrada |
Di de salida |
0 0 0 1 1 0 1 1 |
0 1 1 0 |
ei |
Di de salida |
0 |
|
1 |
|
(Tabla 3) (Fig. 1) (Tabla 4)
Como vemos:
Si no
había error en Di (ei =0),
Di no se ve cambiada en la salida.
Si había
error en Di (ei =1), Di se
cambia (se corrige automáticamente en la salida).
El usuario no necesita saber si el bit Di presente en la entrada de la puerta EXOR es correcto o no, pero puede estar seguro de que el que hay a la salida es el correcto.