Exponsor

CURSO TÉCNICO INSTALADOR DE ENERGÍA SOLAR TÉRMICA

Visita el siguiente enlace: http://enersolartermica.blogspot.com.es/ ¡No pierdas esta magnifica oportunidad de poder formarte en esta profesión con gran demanda de empleo! Ahora por oferta de lanzamiento y por tiempo limitado puedes adquirir este curso por solo 9,95€, cuando su valor de mercado es de 49€.

martes, 31 de marzo de 2009

OTRAS APLICACIONES DE LA LÓGICA DIGITAL EN LA ELECTRÓNICA MODERNA ( I ).

Este capítulo está dedicado tanto al estudio de ciertos temas selectos que ocurren con bastante frecuencia en las aplicaciones cotidianas de los circuitos lógicos como a ciertos temas cuya discusión había sido postpuesta mientras el lector se familiarizaba con el contenido de los capítulos anteriores.

Dada la gran variedad de aplicaciones que encuentra la lógica digital en la práctica, es imposible cubrir todas ellas en una obra limitada como la presente. Posiblemente la aplicación más importante de esta rama de la electrónica sea la computadora digital. Un estudio a fondo sobre este tema queda fuera del alcance de este libro, aunque de cualquier manera se ha incluído información introductoria en los Suplementos puestos al final de esta obra. Se hace hincapié, sin embargo, en el hecho de que podemos construír una computadora digital usando los elementos estudiados en los capítulos anteriores. De cualquier manera, se deja el estudio de dicho tema a obras más especializadas.

Idealmente, en lógica positiva, un "0" lógico equivale exactamente a cero volts, y un "1" lógico equivale exactamente al máximo nivel de voltaje proporcionado por la fuente de poder, y la transición de "0" a "1" ó de "1" a "0" se lleva a cabo de una manera instantánea.

En la práctica, sin embargo, esto no es posible. Conforme las señales digitales van siendo procesadas y van pasando de un circuito a otro, ni el "0" lógico se puede mantener exactamente en cero volts, ni el "1" lógico alcanza a llegar hasta el máximo nivel de volta dado por la fuente de poder que alimenta al sistema. Esto se hace más notorio conforme la velocidad de las señales va aumentando y estas tienen que salir inclusive fuera de la computadora hacia un mundo hostil en donde las interferencias eléctricas y los ruidos generados por motores pesados o aparatos electrodomésticos degradan a la señal agregándole un componente de "ruido" que antes no tenía. Para que las señales digitales del mundo real puedan ser de utilidad, es necesario establecer límites arriba de los cuales un "0" lógico no puede ser considerado ya como tal y debajo de los cuales tampoco un "1" lógico puede ser considerado así. En la siguiente figura en donde podemos distinguir pulso digital, vemos definidas dos bandas amarillas dentro de las cuales el "0" se puede considerar como una señal útil y el "1" también puede ser considerado como una señal útil:



La región intermedia entre estas dos bandas, determinada por el tipo de electrónica que se esté utilizando, es considerada como la "tierra de nadie", y para evitar indefiniciones es necesario incorporar dentro del arsenal de funciones lógicas básicas componentes que sean capaces de "limpiar" una señal ruidosa extrayendo los verdaderos "unos" y los verdaderos "ceros" de todo el ruido circundante, componentes tales como el gatillo Schmitt que será explorado más a fondo en los problemas resueltos.

Frecuentemente, quizá con demasiada frecuencia, al transmitir señales digitales de un punto a otro la señal de cualquier modo pese a los mecanismos compensadores usados para intentar distinguir claramente entre un "0" y un "1" fallan, y en vez de recibirse lo que debería ser un "0" se recibe erróneamente un "1", o en vez de recibirse lo que debería ser un "1" se recibe erróneamente un "0". Es por ello que, además de la electrónica correctora implementada por medio del hardware para tratar de reafirmar un "0" como un "0" y un "1" como un "1", se llevan a cabo procedimientos de detección de errores agregando información adicional a la señal digital.

El mecanismo más frecuentemente utilizado para la detección de errores quizá lo sea la adición del bit de paridad. Esta técnica empezó a tener aplicaciones amplias al utilizarse el código ASCII para transmitir caracteres alfanuméricos de byte en byte. Como el código ASCII no utiliza más de 7 bits para la transmisión de cada caracter ASCII, se puede utilizar como bit adicional el octavo bit de cada byte que normalmente no se utilizaría, una información extra que se considera una redundancia pero que nos permite determinar si ocurrió un error durante el proceso de transmisión. Existen dos variantes del bit de paridad: el bit de paridad par y el bit de paridad impar. El bit de paridad par es puesto como "1" si la cantidad de "unos" en un conjunto dado de bits es impar, haciendo de este modo a la cantidad total de "unos" par. Y el bit de paridad impar es puesto en "1" si la cantidad de "unos" en un subconjunto dado de bits es par, haciendo de este modo al total de "unos" impar. Usando el bit de paridad par, si un caracter ASCII de siete bits que está siendo transmitido tiene un número impar de "unos" como en la palabra 1100001 que contiene tres "unos", entonces se le añade un bit de "1" adicional tranformando a la palabra en 11100001 para que el total de los "unos" en la palabra binaria sea par:



y si la palabra tiene un número par de "unos" entonces se le agrega un "0" para que el total de "unos" de la palabra siga siendo par, como en el caso de la palabra 01100011. De este modo, todos los bytes que están siendo enviados contendrán un número par de bits. Esta adición del "bit de paridad" se hace desde el punto de la transmisión de la señal (que puede ser de una computadora a otra a través de una red o inclusive dentro de la misma electrónica de cada computadora, como cuando se está enviando información del disco duro a la memoria RAM). Al ir llegando cada byte, lo primero que hace el sistema es checar la paridad del byte. Si el número de bits es par, entonces se sabe que la información llegó correctamente, pero si el número de bits es impar, entonces se sabe que ocurrió un error durante el proceso de transmisión del byte, y en tal caso el receptor le pidiría al transmisor envíar de nuevo esa palabra binaria o el paquete completo de palabras binarias dentro del cual está incluído el caracter que llegó erróneo.

La detección de la paridad en el punto receptor se puede llevar a cabo de una manera extremadamente sencilla con un circuito construído a base de un bloque con el cual ya debemos estar familiarizados: el bloque OR-EXCLUSIVO. Por su Tabla de Verdad, sabemos que un OR-EXCLUSIVO de dos entradas A y B dá un "1" cuando ambas entradas son iguales, y dá un "0" cuando ambas entradas son diferentes. Pero ahora veremos al OR-EXCLUSIVO desde otra perspectiva. Cuando ambas dos entradas A y B son iguales, la salida del OR-EXCLUSIVO es "1", o sea cuando las dos entradas son ambas "0" ó cuando las dos entradas son ambas "1", o sea cuando la paridad de la palaba de entrada AB es par. El OR-EXCLUSIVO es capaz de detectar la paridad en una palabra de dos bits, o sea un número par de "unos" cuando hay "unos" en la palabra. ¿Podemos extender este concepto a una palabra binaria de tres bits? La respuesta es afirmativa, y para ello podemos seguir utilizando el mismo OR-EXCLUSIVO de la siguiente manera:



La construcción de la Tabla de Verdad para este circuito, que es la siguiente:



es extremadamente sencilla. Tomamos las entradas combinadas A y B cuando ambas solo están produciendo un "1" a la salida del OR-EXCLUSIVO del cual son entradas (o sea, cuando ambas A y B son iguales). Esta salida de "1" del OR-EXCLUSIVO de arriba es la entrada al OR-EXCLUSIVO de abajo. Y cuando ambas entradas al OR-EXCLUSIVO inferior son iguales, la salida del OR-EXCLUSIVO que es a su vez la salida del circuito será "1", y en caso contrario la salida será "0". Un efecto curioso es que este circuito, el cual tiene una cantidad impar de entradas (tres entradas: A, B y C), produce un "1" a su salida cuando la palabra binaria de entrada ABC es impar (o sea, cuando hay un número impar de "unos" a la entrada), y produce un "0" cuando la palabra binaria de entrada ABC es par. Contrástese esto con el funcionamiento del OR-EXCLUSIVO de dos entradas, cuyo comportamiento es el reverso de esto. Si queremos que se produzca un "1" cuando la paridad de la palabra de entrada sea par (como ocurre con el OR-EXCLUSIVO de dos entradas), todo lo que tenemos que hacer es agregar un inversor lógico NOT a la salida del circuito.

Así como construímos el circuito anterior usando tres bloques OR-EXCLUSIVO, podemos construír otro circuito que incorpore cuatro bloques OR-EXCLUSIVO:



Empleando el mismo razonamiento que el que utilizamos arriba para construír la Tabla de Verdad para el circuito de 3 bits, encontramos que la Tabla de Verdad para el circuito con cuatro bloques OR-EXCLUSIVO es la siguiente:



En este caso, con una cantidad par de entradas, encontramos que el circuito produce un "1" cuando la palabra binaria de entrada ABC es impar, y produce un "0" cuando la palabra binaria de entrada ABC es par.

Este circuito recibe el nombre de árbol de paridad. Podemos extender el mismo concepto con toda facilidad para construír un árbol de paridad de seis bits, o de ocho bits como el árbol de paridad que se muestra a continuación, al cual le hemos dado una salida convencional X y el inverso de la salida, X, con el fin de utilizar la salida "par" como productora de una señal que podemos interpretar y usar en un diseño simplemente como PAR y la salida impar como productora de una señal que podamos interpretar y usar en un diseño simplemente como IMPAR:



Como una cortesía de la Universidad de Hamburgo en Alemania, se encuentra disponible en Internet en el siguiente domicilio un árbol de paridad de ocho bits completamente interactivo, en el que haciendo "clic" con el mouse podemos ir "encendiendo" o "apagando" cada una de las entradas en los puntos marcados como d0, d1, d2, d3, etc.:

http://tams-www.informatik.uni-hamburg.de/applets/hades
_______/webdemos/10-gates/12-parity/parity8.html

Para que la demostración intercativa pueda funcionar, es necesario que la computadora en la cual se corra la simulación tenga instalada la plataforma Java (la cual se puede descargar sin costo alguno de Internet). En esta simulación, podemos comprobar cómo al ir encendiendo alternadamente una cantidad par o impar de "unos" en las entradas la salida del árbol en la terminal "o" se va "apagando" (esto lo tomamos como indicativo de un "0") o se va "encendiendo" (esto lo tomamos como indicativo de un "1") dependiendo en que el total de las entradas "encendidas" sea una cantidad impar o par (podemos invertir el sentido de la paridad en este árbol de paridad simulado con sólo "activar" la entrada en el extremo inferior izquierdo que dice "odd").

Con la misma facilidad con la cual se construye un árbol de paridad de ocho bits podemos, si queremos, construír un árbol de paridad de doce bits. Pero en este último caso, podemos ahorrarnos una buena cantidad de tiempo y esfuerzo adquiriendo comercialmente algún circuito integrado cuya función sea precisamente la misma que la de un árbol de paridad, un circuito integrado como el 4531, el cual es un árbol de paridad de 12 bits:



Este circuito integrado trabaja de la manera siguiente: Las entradas al circuito son puestas desde la terminal identificada como Input 0 hasta la terminal identificada como Input 11. En operación normal, la terminal "pin" 10 (Odd/Even Select) tiene puesto un "0". Si una cantidad par de entradas está en el estado de paridad "cero" el circuito pone un "0" en la terminal de salida identificada como Output (terminal "pin" 9), y si un número impar de entradas están en el estado de paridad "cero" entonces el circuito pone un "1" en la terminal de salida Output. Poniendo un "1" en la terminal 10 invierte el sentido de la salida Output.

En general, el árbol de paridad puede ser utilizado de dos maneras: para generar el "bit" de paridad en la palabra que será transmitida, y para detectar la paridad de la palabra recibida.

Otra técnica que ha sido ampliamente utilizada para la detección de errores es la técnica del chequeo-de-suma (sumcheck). Esta consiste en generar un número checksum, que es enviado junto con un "paquete" de datos, a partir de los mismos datos. Al recibirse el "paquete" de datos, el número checksum puede ser generado nuevamente por el receptor sumando los números que corresponden al paquete recibido, y comparado con el número checksum enviado. Si los dos checksum resultan ser diferentes, entonces se sabrá que hubo un error. Con una ligera variante, podemos hacer un poco más eficiente el proceso en la forma que se describirá a continuación.

Supóngase que vamos a enviar cuatro palabras: la palabra 00100101 (equivalente al número hexadecimal 25h), la palabra 01100010 (equivalente al número 62h), la palabra 00111111 (equivalente al número 3Fh) y la palabra 01010010 (equivalente al número 52h), junto con su checksum.

El primer paso consiste en sumar (en suma binaria) las cuatro palabras como si fueran números (pueden serlo, pero también podrían ser caracteres alfabéticos ASCII). Esto dará como resultado una palabra de nueve bits en vez de ocho, la palabra 100011000 (cuyo equivalente hexadecimal es 118h).

El siguiente paso consiste en ignorar el bit excedente resultante de la operación aritmética de "llevar", lo cual nos deja con la palabra 00011000 (cuyo equivalente hexadecimal es 18h).

El tercer paso consiste en obtener el 2-complemento (véase el Capítulo 3: El álgebra Boleana) de la palabra obtenida, el cual resulta ser 11101000 (cuyo equivalente hexadecimal es E8). Este es el byte del chequeo-de-suma que es enviado hacia afuera junto con los datos.

El receptor todo lo que tiene que hacer de su lado es sumar el checksum recibido a la suma total que obtenga del grupo recibido de cuatro bytes, sabiendo que el resultado debe ser siempre cero (recuérdese que la suma de un número al número 2-complemento derivado de ella es cero). En este caso, si sumamos 11101000 a 100011000 (la palabra de nueve bits resultante de la suma de los cuatro bytes), obtenemos 1000000000, o sea el número hexadecimal 200h, y como en el procedimiento ignoramos los bits generados por la operación aritmética de "llevar", ignoramos los dos bits "10", lo cual nos deja con la palabra 00000000, lo cual nos indica que hubo una generación de cero errores.

Otra técnica potente muy utilizada para la detección de errores es el chequeo de redundancia cíclica (Cyclic Redundancy Check ó CRC). Su modo de empleo se muestra a continuación (ampliar imagen):



Como lo muestra el diagrama, el proceso comienza con la palabra binaria a3a2a1a0 que va a ser transmitida. Se toma la palabra binaria que en este caso es de cuatro bits y se le añaden tres ceros. Hecho esto, se lleva a cabo un proceso de división binaria entre esta palabra y un divisor de cuatro bits identificado como d3d2d1d0 (tanto el transmisor como el receptor deben tener disponible en todo momento el mismo valor binario para el divisor d3d2d1d0). El resultado de este proceso aritmético se lleva a cabo en un "generador" (el cual puede ser un circuito lógico especializado o un secuenciador programable capaz de poder llevar a cabo el proceso de división), en el cual después de haberse llevado a cabo la división binaria se produce el residuo resultante de la división, identificado como r3r2r1r0, el cual es frecuentemente conocido como el CRC. Este residuo (CRC) es anexado a la palabra-dato original a3a2a1a0 formando la palabra-código a3a2a1a0r3r2r1r0. Esta palabra de siete bits es la palabra que es enviada por el "transmisor" mediante un canal de comunicaciones poco fiable, el cual puede ser una línea telefónica ruidosa. La palabra que llega al "receptor" es la palabra código de siete bits b3b2b1b0q2q1q0. Si el canal de comunicaciones fuera altamente confiable y no hubiera ocurrido ningún error durante el proceso de transmisión, la palabra código recibida b3b2b1b0q2q1q0 sería idéntica en todo respecto a la palabra código enviada a3a2a1a0r3r2r1r0. Una vez recibida la palabra código, el receptor utilizando como punto de referencia el mismo divisor d3d2d1d0 lleva a cabo el mismo proceso aritmético de división (dividiendo el mensaje entre el divisor d3d2d1d0) en un bloque "checador" obteniendo una palabra "síndrome" de tres bits s2s1s0. Si la palabra síndrome resulta estar constituída de puros "ceros", ello significa que no hubo error alguno durante el proceso de transmisión de la palabra, con lo cual se abre una compuerta dejando pasar los bits b3b2b1b0 aceptándolos como la palabra-dato original a3a2a1a0. Pero si la palabra síndrome tiene un valor diferente de cero binario, entonces la compuerta no se abrirá y por el contrario será descartada como defectuosa. Como ya se dijo, esta técnica se puede implementar con electrónica digital, con circuitos usando funciones lógicas básicas y flip-flops, como lo muestra la siguiente "tabla de secuencias" representativa del comportamiento de una "máquina CRC":





En esta "máquina" que esencialmente está hecha a base de un registro de desplazamiento del tipo entrada serial y salida serial de 5 bits (usando cinco flip-flops) con los bits desplazándose dentro de ella de derecha a izquierda en cada "pulso de reloj", se utiliza como generador del CRC la palabra binaria "1011" para obtener el CRC a partir de la palabra-dato o "mensaje" a ser transmitido que en este caso es "01100111". En la implementación de la máquina, puesto que se van a estar llevando a cabo operaciones aritméticas en el sistema binario (base-2), será inevitable en cualquier diseño de este tipo de máquina la inclusión de una función lógica que encontramos previamente tanto en la construcción del Medio-Sumador como del Medio-Substractor: el bloque OR-EXCLUSIVO o XOR.

Desde el punto de vista de la máquina (del lado del transmisor), el procesamiento se lleva a cabo bit por bit, resultando en una serie de dígitos binarios (los bits del CRC) que serán anexados posteriormente al mensaje original. El proceso comienza con todos los flip-flops de la máquina puestos en "ceros", tras lo cual el mensaje va siendo desplazado hacia la izquierda siendo introducido bit por bit dentro del registro de desplazamiento (esto está simbolizado con una letra "M" que tiene anexada una flecha a la misma apuntando hacia la izquierda) seguido de cuatro ceros (simbolizado cada uno de ellos con un número "0" también con una flecha anexada apuntando hacia la izquierda), de modo tal que entra el mensaje seguido de cuatro ceros. Obsérvese que cuando el bit más significativo (el bit más a la izquierda) es "1" (esta es la situación que tenemos en el séptimo renglón de la tabla de secuencias, con el "1" de color rojo sobre un fondo negro) se lleva a cabo entonces la operación de OR-EXCLUSIVO con el "generador" que en este ejemplo es la palabra "10011". Esto se repite cada vez que el bit más significativo es "1", lo cual ocurre tres veces (en el séptimo, en el noveno y en el 13avo renglón). Los cuatro bits de orden más bajo, resultado final del proceso de división aritmética en el sistema binario (base-2), son entonces el CRC que será anexado a la palabra-dato original justo antes de llevarse a cabo la transmisión del mensaje, el cual en este caso es "0110" (en el renglón inferior de la tabla de secuencias) descartando el "0" que está en la posición del bit más significativo. Para este proceso hemos supuesto que el generador es una palabra no de cuatro bits sino de cinco; sin embargo el bit más significativo en el generador no es realmente de interés y por lo tanto no se le toma en cuenta, porque en primer lugar el bit más significativo en el generador siempre es "1", y cuando el bit más significativo (más a la izquierda) dentro del registro se vuelve "1", el generador es sometido a una operación de OR-EXCLUSIVO contra los contenidos del registro, "limpiando" el bit más significativo. Por lo tanto, el bit más significativo no necesita ser transmitido.

También la palabra código resultante (la palabra-dato más la secuencia CRC), al pasar por el "hardware" CRC, deja "limpio" el registro. Esto se puede visualizar mejor alimentando la secuencia "01101110110" (consistente en la palabra-dato "0110111" con el CRC "0110" anexado) adentro del registro de transferencia siguiendo las reglas indicadas. El contenido del registro terminará siendo "cero" al final.

Puesto que a las velocidades actuales de procesamiento que actualmente andan arriba del orden de 1 Gigabit por segundo es muy difícil diseñar circuitos lógicos CRC que puedan hacer todas sus operaciones a esta velocidad, los ingenieros frecuentemente diseñan los circuitos CRC para procesar varios bits a la vez.

Para que el chequeo de redundancia cíclica pueda trabajar, matemáticamente hablando, es necesario que la palabra que va a ser transmitida sea considerada en nuestros análisis como un polinomio. A modo de ejemplo, para el siguiente dato binario de 16 bits a ser transmitido:

0010 0110 1111 0000 (26F0h, hexadecimal)

el polinomio formado directamente a partir de cada uno de los bits es el siguiente (obsérvese la correspondencia entre cada uno de los bits de la palabra y cada uno de los coeficientes "unos" y "ceros" del polinomio):
M(X) = 0 + 0X1 + 1X2 + 0X3 + 0X4 + 1X5 + 1X6 + 0X7 + 1X8 + 1X9 + 1X10 + 1X11 + 0X12 + 0X13 + 0X14 + 0X15
lo cual, ignorando los términos en los que los coeficientes son "ceros", se reduce a:

M(X) = 1X2 + 1X5 + 1X6 + 1X8 + 1X9 + 1X10 + 1X11

Tras esto, y tomando n como la cantidad de bits de que está formada la palabra que será transmitida (n=16 en este ejemplo) se lleva a cabo un proceso de división entre este polinomio M(X) y un polinomio generador G(X) que tiene propiedades especiales:

M(X)Xn/G(X) = Q(X) + R(X)

en donde Q(X) es el cociente de la división y R(X) es el residuo resultante de la misma. Es precisamente este residuo binario R(X) lo que es anexado a la palabra-dato que será transmitida. A continuación tenemos detallado el proceso de división para el ejemplo que estamos utilizando, en donde nuestro polinomio generador G(X) es un polinomio utilizado con mucha frecuencia, el polinomio G(X)=X16+X15+X2+1 (ampliar imagen):



En el receptor,después del cálculo CRC de su lado, el residuo R(X) debe ser cero para que la palabra pueda ser considerada como transmitida sin error alguno.

Una cosa que hay que tener presente es que, al nivel de la máquina digital, la cual trabaja en el sistema binario, no es necesario proporcionarle a la máquina una "calculadora" para que pueda llevar a cabo el proceso de división binaria; ya al igual que en el caso de la multiplicación binaria, la cual se puede llevar a cabo con un registro de transferencia serial y simples adiciones, la división binaria se puede llevar a cabo también con un registro de transferencia serial y simples substracciones. No hay que olvidar que este proceso, que a nosotros nos puede parecer muy laborioso, al final del día no será llevado a cabo por nosotros sino por la misma máquina en donde esté instalado ya sea el productor (en el transmisor) o el verificador (en el receptor) de la redundancia cíclica. Sin embargo, considerando que en un proceso de transmisión de datos de un archivo sumamente grande (con un tamaño en el orden de los megabytes) estos procesos aritméticos repetidos una y otra vez miles y miles de veces invariablemente tendrán un impacto en la disminución de la velocidad de la transmisión de los datos, esto ciertamente tiene que ser considerado como un factor en cualquier diseño que tenga que ver con las áreas de aplicación de la técnica CRC.

A continuación se muestra un cálculo simplificado, muy a la manera de como los matemáticos efectúan el proceso algebraico de división sintética, prescindiendo de las "equis" (que en realidad sólo están haciendo "bulto" aquí), en donde el polinomio M(X) es obtenido de la palabra 11100110 y en donde el polinomio generador G(X) es el que está dado por la palabra 11001, obteniéndose el residuo 0110 que es lo que será anexado a la palabra-dato original a ser enviada (ampliar imagen):



Además de la capacidad para poder detectar errores (error detection), es posible darle a los circuitos lógicos también la capacidad para poder corregir errores (error correction). Esto requiere, desde luego, agregar información redundante adicional a una palabra que permita localizar la posición exacta del bit que está produciendo un error de paridad, ya que el error de paridad por sí solo en una palabra no nos indica cuál de todos los bits es el bit incorrecto. Un esquema utilizado en algunos diseños consiste en tomar varias palabras binarias "en bloque", digamos unas ocho palabras, de modo tal de que además de que cada palabra (representada por un renglón) tenga un bit de paridad, al final de cada bloque de ocho palabras haya una palabra completa "extra" redundante, la cual consistirá de ocho bits de paridad, uno para cada columna. De esta manera, si en lugar de un "1" tenemos un "0" en una palabra, además de la paridad incorrecta que nos permite identificar cuál de las ocho palabras viene con un error tenemos la paridad incorrecta del bloque que nos permite identificar cuál bit de esas ocho palabras es el que está en el error.

Seleccionando una paridad impar como denotando una palabra correcta sin errores y también como denotando una bloque completo de palabras correcto sin errores, a continuación tenemos un bloque que carece errores en la transmisión y en la recepción (cada renglón representa una palabra binaria diferente):


Puesto que todas las palabras binarias del bloque tienen la paridad correcta (impar), no hay errores en la transmisión de este bloque. En cambio, en el siguiente bloque, tenemos una palabra con tres errores:



En este caso, la penúltima palabra (en el penúltimo renglón) viene con tres errores. Su paridad par nos dice que tiene por lo menos un error. Además, la paridad en las columnas nos permite detectar la presencia de tres errores en la palabra e identificar la localización precisa de los tres bits erróneos: están en el cuarto, el quinto, y el séptimo bit de la penúltima palabra binaria.

La localización exacta de un bit erróneo nos permite diseñar una máquina que sea capaz no sólo de detectar estos tres errores sino también corregirlos. Y aunque a nosotros como humanos el proceso nos pueda parecer dificultoso, es relativamente fácil enseñarle a una máquina a corregir este tipo de errores, lo cual haría con rapidez electrónica. Existen procedimientos matemáticos muy específicos para agregar bits redundantes que permitan no sólo la detección de errores sino la corrección de los mismos, conocidos como códigos correctores de errores (error correcting codes ó ECC). Uno de ellos es el código Hamming. Considérese una palabra binaria consistente de únicamente cuatro bits de datos que será transmitida como una palabra-código (codeword) con la adición de tres bits de control de error. Esto sería llamado un código (7,4). Los tres bits agregados son tres bits de paridad par, en donde la paridad de cada uno es calculada en distintos subconjuntos del mensaje de la manera que se muestra abajo:



La razón teórica para este tipo de arreglo es que los tres bits de paridad (1,2,4) están relacionados con los cuatro bits de datos (3,5,6,7) de la manera que se muestra a continuación:



En este diagrama cada círculo corresponde a un bit de paridad, y define los cuatro bits que contribuyen al cálculo del bit de paridad. Por ejemplo, el bit de datos 3 contribuye a los bits de paridad 1 y 2. Cada círculo (bit de paridad) abarca un total de cuatro bits (tres bits de datos y un bit de paridad), y cada círculo por lo tanto debe tener una paridad par. Dados cuatro bits de datos cualesquiera en cualquier combinación de "unos" y "ceros", los tres bits de paridad pueden ser seleccionados fácilmente para cumplir con esta condición, y como de costumbre le dejaremos la carga de este trabajo a la máquina.

Se puede observar en el diagrama que cambiando cualesquier bit numerado del 1 al 7 afecta de modo único los tres bits de paridad. Alterando el bit 7 afecta todos los tres bits de paridad, mientras que un error en el bit 6 afecta únicamente a los bits de paridad 2 y4, mientras que un error en un bit de paridad (lo cual también puede ocurrir durante el proceso de transmisión) afecta únicamente a ese bit de paridad. La localización de cualquier error individual en un bit está determinada unívocamente después de checarse los tres círculos de paridad.

Con este esquema de detección y corrección de errores, la palabra binaria (datos) "1101" sería enviada como la palabra-código "1100110" con la adición de los tres bits de paridad, puesto que:



Cuando estos siete "unos" y "ceros" son introducidos en los círculos de paridad, se puede confirmar que la selección de los tres bits de paridad asegurará que la paridad dentro de cada círculo será par, como se muestra aquí:



Se puede observar aquí que si ocurre un error en cualesquiera de los siete bits, ese error afectará distintas combinaciones de los tres bits de paridad dependiendo de la posición del bit que llega con error. Supóngase por ejemplo que se envía el mensaje "1100110" y que ocurre un error en un solo bit tal que se recibe la palabra-código "1110110":



El error en el mensaje, en el bit 5, puede ser corregido examinando cuáles de los tres bits de paridad fueron afectados por el bit defectuoso:



En el segundo renglón en el cual se utiliza el bit de paridad 1 y el cual tiene un valor de un "0", la cantidad total de "unos" es un número impar, 3, lo cual indica que ha ocurrido un error de acuerdo con el criterio de que bajo la paridad par si se produce un "1" en lugar de un "0" ello apunta hacia la presencia de un error. En el tercer renglón, en el cual se utiliza el bit de paridad 2 y el cual tiene un valor de un "1", la cantidad total de "unos" es un número par, 4, lo cual indica que aquí no hay indicación de error alguno según el criterio de que bajo la paridad par se debe producir un "0" como consecuencia de un número par de "unos". Y en el cuarto renglón, en el cual se utiliza el bit de paridad 4 y el cual tiene un valor de "0", la cantidad total de "unos" es un número impar, 3, lo cual indica que ha ocurrido un error. Los bits de paridad así como la palabra código original permiten determinar la posición del "bit" que llegó defectuoso, o sea el bit 5 que llegó como un "1" en vez de haber llegado como el "0" que debía haber sido. El examen de los círculos de paridad confirma que cualquier bit defectuoso puede ser corregido de esta manera. El código Hamming tiene pues las siguientes características (1) La capacidad para detectar en una palabra transmitida dos bits en el error, lo cual supone que no se intentará llevar a cabo una corrección del error, (2) La corrección de bits individuales de error, o sea un error de un bit en una palabra transmitida, y (3) Un costo de tres bits que se tienen que añadir a un mensaje de 4 bits. Esto último puede parecer oneroso. Sin embargo, la capacidad para poder corregir errores viene a un costo que es menor que el tener que enviar de nuevo el mensaje completo, y tómese en cuenta que el envío del mensaje por partida doble no logra ninguna corrección de error.

Al hablar sobre el tema de la detección y corrección de errores, es frecuente manejar el concepto de la distancia entre dos palabras binarias. Aunque a este concepto casi siempre se le dá en los libros de texto una definición formal que también casi siempre resulta críptica, aquí daremos una definición naïve del concepto: es simplemente la cantidad de bits que tienen que ser cambiados para igualar una palabra binaria con otra. Así, la distancia entre las palabras 10011000 y 00011000 es 1 porque basta con cambiar el primer bit de cualquiera de las dos palabras para igualar una con otra. Entre más "alejada" esté una palabra binaria de la otra, tanto mayor será la cantidad de bits que tengamos que cambiar para igualar una de ellas con la otra. El código Hamming permite la corrección de errores porque la distancia mínima entre dos palabras código es 3. En la figura de abajo, dos palabras código en ocho posibles palabras código de tres bits están acomodadas para tener una distancia de 3 entre ellas. Se requieren tres cambios de bits (errores) para moverse de una palabra código 000 válida a los siguientes 111. Si la palabra código 000 es transmitida y ocurre un error en un bit, la palabra recibida necesariamente será una del conjunto {001, 010, 100}, cualquiera de las cuales puede ser identificada fácilmente como una palabra código inválida, y la cual podría haber sido únicamente la palabra código 000 antes de la transmisión.



El código Hamming define esencialmente 16 palabras código válidas dentro de todas las 128 palabras código posibles de 7 bits. Estas 16 palabras están acomodadas de modo tal que la distancia mínima entre dos palabras cualesquiera sea 3. Estas palabras código son mostradas en la siguiente tabla:



Se puede verificar que la distancia de cualquier palabra código M={0,1,2,...,E,F} de esta tabla a cualquier otra palabra código N es de por lo menos 3. A continuación tenemos unos ejemplos en donde medimos la distancia de la palabra código 3 hacia otras palabras código para confirmar esta aseveración:
La distancia es 4 entre 3 = 0011110 y 0 = 0000000
La distancia es 3 entre 3 = 0011110 y 1 = 0000111
La distancia es 3 entre 3 = 0011110 y 2 = 0011001
La distancia es 4 entre 3 = 0011110 y D = 1100110
La distancia es 4 entre 3 = 0011110 y E = 1111000
La distancia es 3 entre 3 = 0011110 y F = 1111111
Continuando con el chequeo de la distancia entre la palabra código 3 y todas las demás palabras código restantes, podemos concluír que la palabra código 3 está situada a una distancia de por lo menos 3 de todas las demás palabras código.

Con la misma facilidad con la que construímos el código (7,4) podemos construír otros códigos Hamming, por ejemplo el código (8,4).

Con un poco de análisis matemático podemos obtener una fórmula que nos indica en forma precisa cuántos bits redundantes adicionales se requieren para garantizar la detección y corrección de un error con el código Hamming. La fórmula es Ham(2n, 2n-n-1). Por ejemplo, si n=7, tenemos entonces Ham(128,120), lo cual nos dice que para cada 120 bits de datos únicamente se requieren ocho bits extra redundantes para protegernos en contra de un error dándonos la capacidad no sólo para poder detectarlo sino también para poder corregirlo. Y cuando n=20, entonces obtenemos Ham(1048576,1048555), lo cual nos dice que se requieren únicamente 21 bits para codificar más de un millón de bits y aún garantizarnos una protección en contra de un error.

Como una cortesía de la Universidad de Hamburgo en Alemania, se encuentra disponible en Internet en el siguiente domicilio un programa interactivo que permite al estudiante el poder "experimentar" con un envío y recepción de un mensaje binario utilizando la adición de bits de paridad y el código Hamming para poder detectar la presencia de errores así como la determinación del bit defectuoso. El programa interactivo puede ser accesado en el siguiente domicilio:

http://tams-www.informatik.uni-hamburg.de/applets/hades
_______/webdemos/10-gates/50-hamming/hamming.html

Esta simulación trabaja con un circuito que utiliza un código Hamming de 4 bits para detección y corrección de errores. Los cuatro interruptores a la izquierda se utilizan para fijar el valor de 4 bits para el codificador, el cual calcula el valor requerido por cada uno de los tres bits de paridad que serán transmitidos junto con los cuatro bits de datos como una palabra código. Los siete interruptores (Set channel faults) y las compuertas OR-EXCLUSIVO en la parte media del circuito permiten introducir manualmente "fallas" en el mensaje transmitido. Si todos los interruptores están "apagados", el mensaje es transmitido en forma normal, pero si se "enciende" uno de los interruptores entonces la compuerta OR-EXCLUSIVO asociada al interruptor invierte el bit del dato correspondiente (conviertiendo un "0" en un "1" ó un "1" en un "0"), lo cual equivale a que ese bit haya sido transmitido como error. El bloque decodificador a la derecha del circuito toma los siete bits del mensaje e intenta reconstruír con los siete bits la información original, o sea los cuatro bits del mensaje original. Los creadores del programa interactivo recomiendan tener todos los siete interruptores "apagados" experimentando con el envío de algunos mensajes; seleccionando algunos valores de entrada para el codificador con los interruptores a la izquierda para así poder observar los bits de paridad que se generan así como el modo de funcionamiento del decodificador. Tras esto, recomiendan "jugar" con algunos de los interruptores para introducir manualmente "fallas" individuales en el mensaje transmitido, observando la operación del decodificador. Y finalmente, invitan al experimentador a descubrir qué es lo que ocurre cuando se activa más de un "interruptor generador de error".

Ámsterdam únicamente con circulación de coches eléctricos para el 2040


Ámsterdam no podía ser una ciudad más respetuosa del medio ambiente, hoy en día es una ciudad que tiene una increíble proporción en el uso de la bicicleta en Europa.

Ahora esta ciudad quiere dar un paso más allá y planea tener solo coches eléctricos en circulación en el 2040, sin ningún vehículo de combustión interna en funcionamiento. Para esto ya se está trabajando en una red de recarga que contempla 200 estaciones donde podrán enchufar sus vehículos.

Sería interesante que también implementaran estacionamientos provistos de paneles solares para las bicicletas eléctricas como en Japón.

lunes, 30 de marzo de 2009

Sin Palabras: Estación Espacial Internacional vs La Tierra

PROBLEMAS RESUELTOS SOBRE CONTADORES , FLIP-FLOP (J-K): PARTE 5ª

PROBLEMA: Sin hacer uso de ninguna de las fórmulas derivadas en los problemas anteriores y sin hacer uso del mapa de Karnaugh, diseñar un contador binario BCD síncrono (ascendente) utilizando para ello el flip-flop más versátil de todos, el flip-flop J-K.

En este problema, llevaremos a cabo el diseño de un circuito secuencial partiendo de cero (en los países de habla inglesa a esto se le llama trabajar from the ground up) y demostraremos con ello que con un poco de ingenio podemos prescindir de fórmulas, álgebra, mapas y demás artificios utilizados para trabajar metódicamente.

La tabla de secuencias para un contador binario BCD, síncrono o asíncrono, debe recorrer los siguientes estados desde el principio hasta el regreso a su estado original:



Obsérvese que se han listado los estados de cada flip-flop en el orden Q4Q3Q2Q1 en el cual nosotros estamos acostumbrandos a contar, con cada número sucesivo creciendo de la derecha hacia la izquierda. Pero en los diagramas esquemáticos, con la señal de entrada (los pulsos del reloj) puesta del lado izquierdo del circuito, y con el flujo de señales del circuito yendo en su mayor parte de la izquierda hacia la derecha (la manera en la cual se leen los diagramas esquemáticos de los circuitos lógicos), para el diseño que llevaremos a cabo será más apropiado utilizar la tabla de secuencias en el orden Q1Q2Q3Q4:



Viendo esta tabla, resulta obvio que el primer flip-flop J-K cuyo estado es Q1 estará alternando siempre en cada transición entre los estados "0" y "1", actuando como un flip-flop "T". El primer bloque será entonces un flip-flop J-K con sus entradas J y K puestas permanentemente en el estado "0" (estamos utilizando en nuestro diseño flip-flops activados por una transición negativa en la terminal de entrada C, de "1" a "0").

A continuación, agregamos un segundo flip-flop cuyas entradas J y K están por determinadas, cuya terminal C derivará de la misma entrada que alimenta a la terminal C del primer flip-flop para que el diseño sea síncrono. Quizás el diseño síncrono más sencillo posible de un contador binario ascendente de dos bits es el que se muestra a continuación:



La secuencia natural de este contador binario síncrono de dos bits será la siguiente:



Para que el contador sea un contador BCD (contando del 0 al 9 en el sistema binario), requerimos que el contador vuelva al estado Q1Q2Q3Q4=0000 en la transición que sigue al estado Q1Q2Q3Q4=1001. Para lograrlo, revisamos los cuatro últimos estados del contador binario BCD para ver cómo se pueden usar para condicionar los flip-flops puestos a la entrada:



Podemos ver en la secuencia que el primer flip-flop no requiere ninguna modificación. Sin embargo, después del estado Q1Q2Q3Q4=1110, el segundo flip-flop deja de contar (permanece en el estado Q2=0) hasta que empiece de nuevo la secuencia. Notamos que esto ocurre al mismo tiempo que Q4 toma el valor de "1". Esto nos sugiere que podemos usar Q4 para desactivar a Q2 en los últimos estados del contador, lo cual se logra fácilmente añadiendo un OR como se muestra a continuación (el OR se encargará de poner el "1" proveniente de Q4 en ambas entradas J y K del segundo flip-flop, con lo cual no ocurrirá nada en dicho flip-flop en cada transición):



(Para simplificar los diagramas, en este circuito y en los que siguen ya no se mostrarán las entradas J y K del primer flip-flop puestas a "0", lo cual se dará por sobreentendido, y lo cual dicho sea de paso es una práctica frecuente en diagramas complejos de circuitos lógicos en lugares en donde se supone que el flip-flop J-K tiene ambas entradas J y K puestas a un mismo valor, el valor con el cual cambiará de estado en cada pulso de reloj, ya que el otro valor no servirá de nada para hacer que cambie o que haga algo.)

Añadimos ahora a la configuración de dos bits el tercer flip-flop manteniendo por conveniencia la simetría del diseño original, con la mente abierta para modificarlo según sea necesario:



La secuencia natural de este contador síncrono de tres bits será la siguiente, en base a las propiedades del flip-flop J-K:



Con excepción de los dos primeros flip-flops, este contador no sigue una secuencia binaria. Debemos buscar ahora la manera de condicionar al tercer flip-flop con los flip-flops anteriores en la cadena para que se produzca una secuencia binaria. En particular, deseamos que el tercer flip-flop sea condicionado para una transición cuando Q1Q2=11 y desactivado para otros valores Q1Q2. Tomando en cuenta que lo más probable es que la entrada del tercer flip-flop dependa de Q1 y Q2, podemos construír una Tabla de Verdad indicando la acción deseada (¡esta no es una tabla de secuencias!):



En esta Tabla de Verdad, puesto que hay únicamente un maxterm y en cambio hay tres minterms, resulta más conveniente diseñar alrededor de los "ceros" que de los "unos". Podemos ver que la entrada al tercer flip-flop en sus terminales J y K tiene que estar dada por el maxterm Q1+Q2. Esto se logra fácilmente usando un OR y tomando la salida Q del primer flip-flop (Q2 ya estaba alimentando al tercer flip-flop). La configuración toma ahora el siguiente aspecto:



A continuación, añadimos el cuarto flip-flop a la cadena, haciendo primero una Tabla de Verdad para ver cómo deben condicionar los tres primeros flip-flops al cuarto:



Nuevemante, resalta la conveniencia de utilizar maxterms en lugar de minterms. La entrada al cuarto flip-flop en sus terminales J y K debe ser el maxterm Q1+Q2+Q3, para lo cual debemos usar un OR de tres entradas. Sin embargo, debemos tener presente que después del estado Q1Q2Q3Q4=1001, el contador debe regresar al estado Q1Q2Q3Q4=0000. La única forma en la cual se puede mandar al cuarto flip-flop al estado Q4=0 después de Q1Q2Q3Q4=1001 es haciendo J4=0 en este estado, independientemente del valor de K4. Esto sugiere que dejemos la entrada K4 como Q1+Q2+Q3 y que tratemos a la entrada J4 por separado.

Para que después del estado Q1Q2Q3Q4=1110 el cuarto flip-flop tome el estado Q4=1 se requiere que antes de la transición J4=1 ó J4=0, ya que K4=0. De cualesquier manera, hay únicamente dos cambios de estado en el cuarto flip-flop durante toda la secuencia natural de estados del contador. Notamos también que durante la mayor parte de la secuencia natural de estados se tiene Q4=0. Hay dos formas de mantener al flip-flop J-K en el estado Q4=0:

a) J4=1 y K4=10

b) J4=0 y K4=0

Todo lo anterior indica que, exceptuando al estado Q1Q2Q3Q4=1001 en el cual se requiere J4=0, podemos asignar el valor que queramos a J4. Lo más ventajoso es asignar a J4 una secuencia alternada de "unos" y "ceros", lo cual es relativamente fácil de obtener. La Tabla de Verdad para el cuarto flip-flop a través de la secuencia natural de estados del contador toma entonces el siguiente aspecto:



Estudiando la Tabla de Verdad vemos que los valores asignados a J4 y K4 están de acuerdo con el comportamiento requerido del cuarto flip-flop a través de la secuencia de estados. Notamos también que podemos obtener J4 del complemento de Q1, o sea de Q1. El diseño terminado se muestra a continuación:



Este tipo de contador binario BCD es el más rápido posible en teoría, por el hecho de ser síncrono. En la práctica, la máxima velocidad que se pueda lograr en este contador dependerá de la tecnología empleada por los elementos usados para construír el contador.


PROBLEMA: Sin consultar ninguno de los problemas anteriores, y usando flip-flops tipo D, diseñar haciendo recurso del mapa de Karnaugh un contador síncrono cuya tabla de secuencias sea la siguiente:



Si se requiere que el contador sea síncrono, entonces todas las entradas a la terminal de "reloj" C de cada uno de los tres flip-flops deben ser activadas al mismo tiempo por la misma señal. De la tabla de secuencias dada, podemos elaborar dos tablas que nos indiquen el valor previo Qn que debe tener cada flip-flop en cierto estado, y el valor Qn+1 que debe tener en el estado siguiente:



A continuación, separamos las tres columnas correspondientes a cada uno de los estados Qn+1 en preparación para la operación sutil de convertir la tabla de secuencias en Tablas de Verdad para cada uno de los flip-flops usados:



Un momento de reflexión nos dirá que precisamente aquí tenemos toda la información que requerimos para poder "condicionar" cada uno de los tres flip-flops D para el estado Qi que deberá tomar al llevarse a cabo una transición:



De este modo, si el estado actual del contador es Q0nQ1nQ2n=000, entonces para que el primer flip-flop independientemente de lo que ocurra con los otros dos flip-flops pase del estado Q0n=0 al estado Q0n+1=1 dicho flip-flop tiene que tener condicionada su entrada D1 previamente con un "1" producido por esta combinación de todos los valores que tengan los tres flip-flops antes de la transición, o sea Q0n=0, Q1n=0 y Q2n=0. Del mismo modo, si el estado actual del contador es Q0nQ1nQ2n=010, entonces para que el segundo flip-flop independientemente de lo que ocurra con los otros dos flip-flops pase del estado Q1n=1 al estado Q1n+1=1 dicho flip-flop tiene que tener condicionada su entrada D1 previamente con un "1" producido por esta combinación de todos los valores que tengan los tres flip-flops antes de la transición, o sea Q0n=0, Q1n=1 y Q2n=0. Y si el estado actual del contador es Q0nQ1nQ2n=101, entonces para que el tercer flip-flop independientemente de lo que ocurra con los otros dos flip-flops pase del estado Q2n=1 al estado Q2n+1=0 dicho flip-flop tiene que tener condicionada su entrada D2 previamente con un "0" producido por esta combinación de todos los valores que tengan los tres flip-flops antes de la transición, o sea Q0n=1, Q1n=0 y Q2n=1.

Puesto que hay tres flip-flops D, se requerirán tres mapas de Karnaugh, un mapa de Karnaugh para cada uno de ellos. La construcción de cada mapa de Karnaugh puede utilizar ventajosamente la existencia de dos estados redundantes. Estos son los estados que no aparecen en la tabla de secuencias normal del contador, y que por lo tanto son irrelevantes para los estados que deberán ir tomando cada uno de los flip-flops en cada transición; se trata de los estados Q0Q1Q2=011 y Q0Q1Q2=111. Normalmente, en una tabla de secuencias se les identifica simplemente como una "X" que significa que tanto el "0" como el "1" son valores igualmente válidos (en circuitos de lógica combinatoria también en las Tablas de Verdad se les representa a estas condiciones con el símbolo "X"). Sin embargo, aunque sean redundantes, se pueden utilizar para "agrupar" los términos dentro de expresiones más sencillas, y en base a esto tenemos la entera libertad de asignarle a cada valor redundante un "0" para no tomarlo en cuenta para nada o un "1" para utilizar la redundancia ventajosamente para la simplificación del circuito. Tomando esto como base, a continuación construímos el mapa de Karnaugh para el primer flip-flop D, diseñando alrededor de los minterms:



En este mapa se ha utilizado ventajosamente una redundancia, Q0Q1Q2=011, identificada con un "1" de color rojo, con el fin de abarcar dos celdas contiguas reduciendo el término Q0Q1Q2 a Q0Q1 Q'0Q1. Del primer mapa de Karnaugh vemos pues que el primer flip-flop debe estar condicionado por la relación:

D0 = Q0Q1 + Q0Q1

Esto se puede simplificar aún más con álgebra Boleana:

D0 = Q0(Q1 + Q1) D0 = Q0

A continuación, construímos el mapa de Karnaugh para el segundo flip-flop D:



Del segundo mapa de Karnaugh, vemos que el segundo flip-flop debe estar condicionado por la relación:

D1 = Q0Q1Q2 + Q0Q1

Por último, construímos el mapa de Karnaugh para el tercer flip-flop D:



Del tercer mapa de Karnaugh, vemos que el tercer flip-flop debe estar condicionado por la relación:

D2 = Q0Q1 + Q0Q2

En este último mapa, hemos usado las dos redundancias disponibles para llevar a cabo dos simplificaciones de modo distinto. La primera simplificación por la vía visual con la ayuda del mapa de Karnaugh, resaltada con las celdas de color ciano, consistió en "enrollar" los "unos" colocados en la última columna, obteniendo el término simplificado Q0Q1. La segunda simplificación se logró metiendo la otra redundancia, resaltada con las celdas de color verde, con el fin de lograr el objetivo de reducir el término de tres variables Q0Q1Q2 al término de dos variables Q0Q2 mediante el recurso del álgebra Boleana al hacer:

Q0Q1Q2 + Q0Q1Q2 = Q0Q2(Q1 + Q1) = Q0Q2

Podemos ver en este último ejemplo cómo ambas técnicas, el mapa de Karnaugh y el álgebra Boleana, se pueden complementar ventajosamente.

Resumiendo los resultados obtenidos, el circuito toma entonces la siguiente configuración final: