Un nuevo enfoque para introducir codigos de hamming

UN NUEVO ENFOQUE PARA INTRODUCIR LOS CÓDIGOS DE HAMMING EN LA INGENIERÍA ELECTRÓNICA
E. ALDABAS1, M. CORBALÁN2, A. ARIAS2, I. PLAZA3, C. MEDRANO3 y F. ARCEGA4 1 Dto. Ing. Eléctrica, 2Dto. Ing. Electrónica, EUETIT Terrassa, UPC 3 Dto. Ing. Electrónica y Comunicaciones, EUPT Teruel, Unizar 4 Dto. Ing. Eléctrica, EUITIZ Zaragoza, Unizar www.unizar.es/eduqtech/ En el presente trabajo se presenta unaintroducción al algoritmo publicado por el profesor Richard Wesley Hamming en 1950 para detectar y corregir un bit erróneo dentro de una palabra binaria de datos. En primer lugar se definen los conceptos previos necesarios para comprender el alcance del problema, a continuación se describe paso a paso la forma en que trabajan los ya denominados códigos de Hamming. Para finalizar se comentan unosejemplos prácticos y se propone un circuito de Hamming (11,7) desarrollado en GNU Octave.

1. Introducción
En el año 1950, el profesor Richard W. Hamming [1] publicó un artículo sobre detección y corrección de errores [2]. Este trabajo supuso el comienzo de una nueva área de investigación dentro de la teoría de la información. Actualmente, los códigos de Hamming son fundamentales en la teoríade la codificación y tienen una gran cantidad de aplicaciones prácticas. En concreto, los códigos correctores de errores tienen un papel esencial en la vida cotidiana y son usados en modems, memorias, TDT e incluso en comunicaciones vía satélite. La teoría de los códigos de Hamming es madura, difícil y con una orientación matemática. Sin embargo, hay multitud de artículos y libros que tratan estetema [3-8]. En cualquier caso, en los cursos de electrónica digital básica es difícil encontrar los códigos de Hamming [5] por falta de tiempo y porque es necesario introducir al alumno en conceptos más elementales que son ineludibles. Con el uso generalizado de internet, los alumnos tienen una importante fuente de información, y los códigos de Hamming no son una excepción. En cualquier caso, elpresente trabajo pretende animar a los estudiantes de electrónica digital a que se introduzcan en este fascinante tema, y si ya lo conocen, a que vean en él alguna nueva faceta que les pasó desapercibida cuando lo estudiaron por primera vez. Antes de comenzar el razonamiento para describir los códigos de Hamming es necesario tener presente las siguientes definiciones: Código binario: Es unarepresentación unívoca de las cantidades, de tal forma que a cada una de éstas se le asigna una combinación de símbolos binarios. Distancia entre dos combinaciones binarias: Viene dada por el número de bits que hay que cambiar en una de ellas para obtener la otra. Distancia mínima de un código: Es la menor de las distancias entre dos combinaciones binarias cualesquiera pertenecientes a dicho código. Enbase a estas definiciones se concluye que un código binario debe tener al menos la distancia mínima igual a 1 para garantizar que una combinación no represente a varias cantidades o valores. Los códigos son continuos cuando las combinaciones correspondientes a números decimales consecutivos difieren solamente en un bit. En el caso de que también se cumpla que la última combinación sea adyacente a alprimera se está ante los códigos cíclicos. Los códigos ponderados asignan a cada bit un valor o peso en función del lugar que ocupan.

A 0 0 1 1

B 0 1 0 1

BPP 0 1 1 0 .

Control 0 0 1 1

Dato 0 1 0 1

Salida . 0 (dato) 1 (dato) 1 (no dato) 0 (no dato) .

dpp = 0 -> no hay error dpp = 1 -> hay error

BPP

Dato

Salida

A B Control

BPP A B

dpp

Figura 1. Utilizaciónde la función XOR en los códigos de Hamming.
1 A Sistema Emisor 0 B 0 C 0 D
Ruido

1 a 0 0 1 c Receptor d b Sistema

Figura 2. Planteamiento del problema de la transmisión de una palabra binaria.

A 0 1 1 1 0 0 1 0 0 0

B 1 1 0 0 1 0 0 1 0 0

C 1 0 1 0 0 1 0 0 1 0

D 0 0 0 1 1 1 0 0 0 1

E 0 0 0 0 0 0 1 1 1 1

Cantidad 0 1 2 3 4 5 6 7 8 9

BPP 0 1 1 0 1 0 0 1 1 0

A 0 0 0...