Codigo Hamming y sus aplicaciones PDF

Preview

Summary

Código Hamming que es, sus usos, conversión a binario, aplicaciones y ejercicios...

Description

DEPARTAMENTO DE ELÉCTRICA Y ELECTRÓNICA

CARRERA DE INGENIERIA MECATRÓNICA

SISTEMAS DIGITALES

CÓDIGO HAMMING

Nombres: Campos David Coronado Joel Parra Joel NRC: 4520

Sangolquí, 11 de abril del 2019

1. Tema: Código Hamming 2. Objetivos •

Investigar y presentar información relacionada con el código de Hamming en el sistema binario. o Determinar en qué consiste el código de Hamming. o Determinar el proceso de codificación y decodificación en Hamming. o Determinar el proceso para detección y corrección de errores en 1 bit. o Determinar el proceso para codificación y detección de errores en 2 bits

3. Desarrollo Richard W. Hamming en 1950 creó un método que permite construir códigos, este código permite la detección y corrección de errores, al principio puede parecer complicado y difícil de entender, pero con la práctica y la ayuda de trucos aritméticos a nivel de bits se puede lograr entender el método de manera más rápida. El código de Hamming tiene ciertas peculiaridades en donde tenemos que: 2฀ ฀ − 1 Este el número de bits que tendrá el código de Hamming y 2฀ ฀ − 1 − ฀฀ será el número de datos a enviar. •

Ejemplo:

Con un valor de ฀ ฀ = 3 se tiene que: 23 − 1 = 7 23 − 1 − 3 = 4 7−4=3 (AprendeenLinea, 2015) Que se representa como Hamming (7,4), en el cual podremos determinar que se transmitirán 7 bits en los cuales 4 serán de datos y 3 de redundancia. En el código de Hamming se maneja lo que son los bits de paridad y los de datos: •

Bits de paridad: son aquellos que son potencia de 2, es decir, las posiciones 1, 2, 4, 8, 16, 32…

•

Bits de datos: son el resto de las posiciones que no son potencia de 2, es decir, 3, 5, 6, 7, 9, 10… (KairoZ, 2009)

3.1 Distancia Hamming La distancia de Hamming vendría a ser el número de bits en los cuales dos palabras de igual longitud se diferencian. Lo que la distancia de hamming expresa es que la distancia d a la cual se encuentran dichas palabras, sería el número de bits que se necesitara cambiar para que una de estas palabras se convierta en la otra, y se puede interpretar como el número de errores necesarios para que una palabra salte a otra. Dicho de manera sencilla la distancia de Hamming es el número de bits diferentes que hallamos en 2 palabras, y se considera en número de errores mínimos que provocarían que una palabra del código se convierta en otra palabra valida, interpretando esto podemos darnos cuenta que mientras mayor sea la distancia hamming más complicado será que el paso de una palabra a otra ocurra. A continuación, un ejemplo: Palabra 1 1011001 236641 Lámpara

Palabra 2 1001011 256123 Campana

Distancia de Hamming 2 4 3

3.2 Codificación a Hamming Para hacer el cambio de binario a Hamming se debe tener en cuenta cuales son los numero de datos y los de paridad. Para ello se debe realizar una tabla y en los números de datos poner el binario a transformar y luego realizar la suma en los que son los de paridad, si la suma da un número par se debe colocar el 0 y si es impar el 1. Ejemplo: 0110 Posición

0001 (1) p1

0010 (2) p2

Datos p1

1 1

p2

0011 (3) d1

1

1

p3

0101 (5)

0110 (6)

0111 (7)

d2

d3

d4

0

1

1

0

0

1

0

p3 H(7,4)

0100 (4)

0

0 1

0

0

1

1

0

0

1

1

0

3.3 Cambiar de Hamming a binario Para hacer esto solo se debe tomar en cuenta el valor que no son exponenciales de 2 y empezando desde el más significativo 1

1

0

0

1

1

0

0001

0010

0011

0100

0101

0110

0111

x

x

0

x

1

1

0

Los casilleros marcados con ฀฀ son los exponenciales de 2 por lo tanto el numero binario es 0110

3.4 Detección y corrección de errores Retomando el ejemplo anterior se tiene que el mensaje a enviar es 0110 en binario y codificado en H(7,4) se envía 1100110, supongamos que se recibe este valor 1110110 que en binario resultaría 1110 El proceso para la decodificación y detección de errores es el siguiente: Se crea una tabla o matriz, similar a la usada en la codificación, llamada Matriz de comprobación de paridad o Matriz Síndrome Paridad Codificada

Error XOR

p3

Paridad Decodificada

Posición p2

0

1

1

1

0

0

1

1

1

0

0

0

0

0010 (2)

0011 (3)

0100 (4)

0101 (5)

0110 (6)

0111 (7)

p1

p2

d1

p3

d2

d3

d4

1

1

1

0

1

1

Datos p1

0

0001 (1)

0 0

1 0

1

Los valores obtenidos en la columna de Error se toman de abajo hacia arriba y se calcula su valor decimal

p3p2p1 → 0112 → 3 El valor en decimal representa la posición del bit con error, entonces se procede a corregir el error cambiando el valor de dicho bit, en este caso de 1 a 0. Este método sólo funciona cuando existe error en un solo bit. 3.4.1 Hamming extendido En este método se utiliza un bit de paridad global y pueden darse únicamente tres casos: 1. Sin Error: La decodificación de Hamming resulta correcta y el bit de paridad global es correcto. 2. Error en 1 bit a. La decodificación de Hamming resulta correcta y el bit de paridad global es incorrecto. Esto sucede únicamente cuando el error se encuentra en el bit de paridad global. b. La decodificación de Hamming resulta incorrecta y el bit de paridad global resulta incorrecto también. Esto se corrige por el método de Hamming. 3. Error en 2 bits: La decodificación de Hamming resulta incorrecta y el bit de paridad global resulta correcto. Este error no puede ser corregido.

4. Aplicaciones del código de Hamming El código de Hamming es un muy importante en la actualidad, ya que nos permite encontrar errores en palabras codificadas en binarios y sus variantes han encontrado aplicación tanto en las comunicaciones como en el almacenamiento de datos. Esta clase de códigos fueron los primeros pensados para corrección de errores. Han sido muy usados para control y detección de errores en sistemas de comunicación digital y en el almacenaje de información. El código haming es utilizado en la detección de errores principalmente en lo que es el campo de la comunicación, su manera de funcionamiento es la de enviar la misma palabra por 2 canales y al momento de su recepción comprobar si cada uno de los bits de la palabra sigue siendo igual de darse el caso de no serlo se identifica la cadena errónea y se puede corregir.

5. Conclusiones • • •

El método de Hamming sirve para detectar y corregir errores al transmitir una cadena de bits de un lugar a otro. El método de Hamming puede corregir errores en un solo bit. El método de Hamming obtiene una ventaja respecto a otros tipos de códigos de paridad ya que estos pueden encontrar el error, pero no corregirlo

Referencias  Wakerly, J. F. (2001). Diseño digital: principios y prácticas. Pearson educación.  Meinadier J. (1996). Estructura y Funcionamiento de Computadoras  Anasagasti M. (1988). Fundamentos de los computadores...