18
CÓDIGO GRAY El código Gray es uno de los tipos más comunes de códigos cíclicos y tiene la característica de que las palabras de código para dos números consecutivos difieren sólo en un bit. Es decir, la distancia entre las dos palabras de código es 1. En general la distancia entre dos palabras de código binario es igual al número de bits en que difieren las dos palabras. Se trata de un código no ponderado, también conocido como código binario reflejado, el cual fue diseñado originalmente por Frank Gray para prevenir la salida espuria de los interruptores electromecánicos. Hoy en día, los códigos de Gray son ampliamente utilizados para facilitar la corrección de errores en las comunicaciones digitales, tales como la televisión digital terrestre y algunos sistemas de televisión por cable. Muchos dispositivos indican la posición mediante el cierre y la apertura de interruptores. Si el dispositivo utiliza códigos binarios naturales, estas dos posiciones serían uno al lado del otro: ... 011 100 ... El problema con los códigos binarios naturales es que, con los interruptores reales, es muy poco probable que los interruptores cambiarán estados exactamente en sincronía. En la transición entre los dos estados mostrados anteriormente, los tres interruptores de cambio de estado. En el breve período en que todos están cambiando, los detectores se lee

Código Gray

Embed Size (px)

DESCRIPTION

a

Citation preview

Page 1: Código Gray

CÓDIGO GRAY

El código Gray es uno de los tipos más comunes de códigos cíclicos y tiene

la característica de que las palabras de código para dos números consecutivos

difieren sólo en un bit. Es decir, la distancia entre las dos palabras de código es 1.

En general la distancia entre dos palabras de código binario es igual al número de

bits en que difieren las dos palabras.

Se trata de un código no ponderado, también conocido como código binario

reflejado, el cual fue diseñado originalmente por Frank Gray para prevenir la salida

espuria de los interruptores electromecánicos. Hoy en día, los códigos de Gray

son ampliamente utilizados para facilitar la corrección de errores en las

comunicaciones digitales, tales como la televisión digital terrestre y algunos

sistemas de televisión por cable. Muchos dispositivos indican la posición mediante

el cierre y la apertura de interruptores. Si el dispositivo utiliza códigos binarios

naturales, estas dos posiciones serían uno al lado del otro: ... 011 100 ...

El problema con los códigos binarios naturales es que, con los interruptores

reales, es muy poco probable que los interruptores cambiarán estados

exactamente en sincronía. En la transición entre los dos estados mostrados

anteriormente, los tres interruptores de cambio de estado. En el breve período en

que todos están cambiando, los detectores se lee una posición falsa. La transición

podría ser como 011-001 - 101 - 100. Cuando los interruptores parecen estar en la

posición 001, el observador no puede decir si esa es la posición "real" 001, o un

estado de transición entre dos posiciones. Si la salida se alimenta en un sistema

secuencial a continuación, el sistema secuencial puede almacenar un valor falso.

El código binario reflejado resuelve este problema mediante el cambio de

un solo interruptor a la vez, así que nunca hay ninguna ambigüedad de la posición.

El código gray es ampliamente utilizado en la solución de:

Codificadores de posición Torres de Hanoi Los algoritmos genéticos Mapas de Karnaugh

Page 2: Código Gray

Corrección de errores en las comunicaciones digitales

La comunicación entre los dominios de reloj

Conversión de binario a gray y viceversa:

Para la conversión de código binario a código gray se siguen los siguientes

pasos:

1. El bit más significativo en el código gray, es el mismo de código binario.

2. Yendo de izquierda a derecha, sumar cada par adyacente de los bits en

código binario para obtener el siguiente bit en código gray. Se descartan los

acarreos.

Para convertir de código gray a binario, se siguen los pasos siguientes:

1. El bit más significativo en código binario, es el mismo que el

correspondiente bit en código gray.

2. A cada bit del código binario generado, se le suma el bit en código gray de

la siguiente posición adyacente. Se descartan los acarreos.

Ejemplo: Defina un código Gray para codificar los números decimales del

0 al 15.

Se necesitan cuatro bits para representar todos los números, y podemos

construir el código necesario asignando al bit i de la palabra de código el

valor 0 sí los bits i e i 1 del número binario correspondientes son

iguales, y 1 en caso contrario.

El bit más significativo del número siempre se debe comparar con 0 al

utilizar esta técnica. El código resultante es:

Page 3: Código Gray

Tipos especiales de códigos Gray:

En la práctica, un "código Gray" casi siempre se refiere a un código binario

reflejado. Sin embargo, los matemáticos han descubierto otros tipos de códigos de

Gray. Cada uno consiste en una lista de palabras, donde cada palabra es diferente

a la siguiente en un solo dígito.

código Gray n-ario: También conocido como un código Gray no booleano. Como

su nombre lo indica, este tipo de código Gray utiliza valores no booleanos en sus

codificaciones.

Código Gray Balanceado: Aunque el binario reflejado es útil en muchos

escenarios, no es óptimo en ciertos casos debido a la falta de "uniformidad". En

los códigos Gray equilibrados, el número de cambios en las diferentes posiciones

de coordenadas están lo más cerca posible.

Page 4: Código Gray

Código Beckett - Gray: Otro tipo de código Gray, el código de Beckett-Gray, y se

llama así por el dramaturgo irlandés Samuel Beckett, quien se interesó por la

simetría. Su obra "Quad", cuenta con cuatro actores y se divide en dieciséis

periodos de tiempo. Cada periodo termina con uno de los cuatro actores entran o

salen de la etapa. El juego comienza con un escenario vacío, y Beckett quería que

cada subconjunto de actores que aparezca en el escenario exactamente una vez.

Es evidente que el conjunto de los agentes actualmente en el escenario puede ser

representado por un código de Gray binario de 4 bits.

Código Gray de una sola pista: Desarrollado por NB Spedding y refinado por

Hiltgen, Paterson y Brandestini es conocido como STGC, el cual es una lista

cíclica de P codificaciones binarias únicas de longitud n de tal manera que dos

palabras consecutivas difieren en exactamente una posición, y cuando la lista se

examina como una matriz xn P, cada columna es un desplazamiento cíclico de la

primera columna.

CÓDIGO HAMMING

Es un código detector y corrector de errores que lleva el nombre de su

inventor, Richard Hamming. En los datos codificados en Hamming se pueden

detectar errores en un bit y corregirlos, sin embargo no se distingue entre errores

de dos bits y de un bit (para lo que se usa Hamming extendido). Esto representa

una mejora respecto a los códigos con bit de paridad, que pueden detectar errores

en un solo bit, pero no pueden corregirlo.

Hamming estudió los esquemas de codificación existentes, incluido el de

dos entre cinco, y generalizó sus conclusiones. Para empezar, desarrolló una

nomenclatura para describir el sistema, incluyendo el número de los bits de datos

y el de los bits detectores-correctores de error en un bloque. Por ejemplo, la

paridad incluye un solo bit para cualquier palabra de datos, así que las palabras

del Código ASCII que son de siete bits, Hamming las describía como un código

Page 5: Código Gray

(8.7), esto es, un total de 8 bits de los cuales 7 son datos. En el ejemplo anterior

de la repetición, sería un código (3.1), siguiendo la misma lógica. La relación de la

información es el segundo número dividido por el primero, por nuestro ejemplo de

la repetición, 1/3.

Cuando se van a transmitir los datos: se realiza el cálculo, representado por

una función f, para producir un código. Se transmiten los datos y también el

código: así, si se va a enviar una palabra de datos de M bits, y el código tiene una

longitud de K bits, el tamaño real de la palabra a transmitir es de M + K bits.

Cuando la secuencia de bits llega a destino, se utiliza el código para detectar

código de K bits a partir de los M bits de código que se han recibido.

Ejemplo: Supongamos que deseamos transmitir los números decimales del 0 al 9

mediante el código BCD natural; puesto que empleamos 4 bits de datos (n=4),

para confeccionar el código de Hamming se deberán agregar 3 bits de paridad

(p=3), ya que 23=8 4+3+1.

Para plantear las ecuaciones que permiten calcular el valor de los bits de

paridad, cada bit de paridad es asociado a los bits de datos cuya posición,

expresada en binario, tiene un 1 en la potencia de 2 en la que esta ubicada el bit

de paridad, de acuerdo a la siguiente representación:

Page 6: Código Gray

Para cada palabra del código de datos se debe calcular el valor de cada

uno de los bits de paridad, el cual es 0 si la cantidad de unos de los bits asociados

es par, y es 1 si la cantidad de unos de los bits asociados es impar. De lo anterior

se deduce que el bit de paridad B0 esta asociado a los bits de datos D0, D1 y D3,

el bit de paridad B1 esta asociado a los bits de datos D0, D2 y D3, y el bit de

paridad B2 esta asociado a los bits de datos D1, D2 y D3, por medio de las

siguientes ecuaciones:

De esta manera, el código de Hamming para los dígitos decimales

expresados en BCD natural es:

Por la forma en que están elegidos los bits de paridad, es obvio que en la

medida de que no ocurra un error en la transmisión de cada palabra de código de

Hamming, las siguientes ecuaciones serán siempre iguales a cero:

Page 7: Código Gray

De producirse un error en la transmisión de cualquier bit de una palabra de

código de Hamming, en las ecuaciones en las que aparece dicho bit el resultado

será uno. El resultado de todas las ecuaciones va a formar un número binario que

nos indicara la posición del bit con error.

Para mostrarlo, supongamos que trasmitimos el número (7) decimal

codificado en código de Hamming (0110100), pero recibimos la palabra de código

con error (0010100); de esta forma, tenemos que:

Planteando las ecuaciones para el código recibido, tenemos que:

Y de aquí podemos observar que el error se encuentra en el bit que ocupa

la posición 1102, que corresponde efectivamente al bit D2. La corrección se

realiza invirtiendo el bit erróneo (si es un 1, cambiarlo por un 0, y si es un 0,

cambiarlo por un 1).

Page 8: Código Gray

CÓDIGO ASCII

El código ASCII viene de las siglas en ingles American Standard Code for

Information Interchange, es decir, es un código Americano Estándar para el

intercambio de información. El código ASCII fue creado en el año 1963 por el

comité Estadounidense “ASA”, este organismo cambio su nombre en el año 1969

por “Instituto Estadounidense de Estándares Nacionales”. Este código nació a

partir de reordenar y expandir el conjunto de símbolos utilizados desde ese

entonces por telégrafos en la Compañía BELL.

En un inicio, el código ASCII incluía únicamente las mayúsculas y los

números, pero a partir del año 1967 se comenzaron a agregar las minúsculas y

algunos caracteres de control, desde ese entonces formaron los caracteres,

variaban desde el 0 al 127, a la vez se le conocía como US ASCII. Este código

utiliza 7 bits para representar los caracteres, aunque inicialmente emplea un bit

adicional que se usa para detectar errores en la transmisión. Hoy en día define

códigos para 32 caracteres no imprimibles, de los cuales la mayoría son

caracteres de control obsoletos que tiene efecto sobre cómo se procesa el texto.

Cabe resaltar, que el código ASCII reserva los primeros 32 códigos para

caracteres de control, esto originalmente se da para representar información

imprimible o sino para controlar dispositivos que usen ASCII. Un ejemplo de

información imprimible son los códigos del 33 al 126, ya que se conocen como

caracteres imprimibles y tienden a representar letras, dígitos, signos de puntuación

y varios símbolos.

Page 9: Código Gray

Conversión de binario a ASCII:

CÓDIGO AIKEN

Al igual que el código BCD el código Aiken es ponderado y utiliza una

notación posicional. Este código tiene la ventaja de que puede obtener fácilmente

el complemento de un dígito sin más que cambiar "ceros" por "unos y "unos"

por"ceros", lo que será muy útil en ciertas operaciones aritméticas. La diferencia

con el BCD natural, es que los pesos para cada bit equivalen a 2-4-2-1. Cabe

señalar que es posible codificar algunos dígitos de dos formas en este código.

La razón del código Aiken es conseguir simetría entre algunos números, de

manera que entre los números "simétricos" o "complementarios" la diferencia sea

Page 10: Código Gray

la variación entre 0 y 1 de sus posiciones. Por ejemplo, el 1 y el 8 tienen simetría

ya que basta con intercambiar el 0 por el 1 y se logra obtener el número al que es

simétrico.

Conversión decimal a código Aiken:

Los computadores o calculadoras que realizan operaciones aritméticas

utilizan el código BCD-AIKEN para facilitar las operaciones de resta y división y así

obtener un rápido y optimo desempeño.

CÓDIGO DE EXCESO 3

A pesar de ser un código binario sin peso, el código de exceso 3 guarda

una estrecha relación con el código BCD 8421 por el hecho de que cada grupo de

4 bits solo pueden representar a un único dígito decimal (del 0 al 9), y deriva su

nombre de exceso 3 debido a que cada grupo de 4 bits equivale al número BCD

8421 más 3.

Conversión de decimal a exceso 3

Page 11: Código Gray

1. Se separa al número decimal en cada uno de sus dígitos.

2. Sumarle tres (3) a cada dígito decimal.

3. Convertir a BCD el número decimal obtenido.

4. El número obtenido es el equivalente en XS3 del número decimal.

Ejemplo: convertir el número decimal 463 a su equivalente XS3.

Primero le sumamos 3 a cada dígito:

4+3, 6+3, 3+3

Luego cada resultado se transforma a BCD = 0110 1001 0110

Conversión exceso 3 a decimal:

Page 12: Código Gray

REPÚBLICA BOLIVARIANA DE VENEZUELA

MINISTERIO DEL PODER POPULAR PARA LA EDUCACIÓN SUPERIOR

INSTITUTO UNIVERSITARIO DE TECNOLOGÍA AGRO-INDUSTRIAL

PNF INGENIERÍA ELÉCTRICA

SISTEMAS DIGITALES

SISTEMAS DE CODIFICACIÓN

Estudiante:

Henry Jhoann Ramírez R. CI: V-19.033.080

Profesor: Alberto Aguilera

Sección: EN2A

San Cristóbal, Marzo de 2015

Page 13: Código Gray

INTRODUCCIÓN

En la informática se usaron muchos sistemas de numeración como lo fue el

sistema binario, decimal, octal y hexadecimal ya que fueron muy útil para la

realización de varios programas pero la tecnología ha avanzado tanto que ya

estos sistemas están si se puede decir obsoleto.

Para la realización de estos programas se tenía que realizar algunas

conversiones, como lo sonlas conversiones a códigos hamming, Gray, Aiken y

Exceso 3.