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.

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)

 
D7

 

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.