16.2: Tablas de búsqueda

Habiendo aprendido sobre los dispositivos de memoria digital en el último capítulo, sabemos que es posible almacenar datos binarios dentro de dispositivos de estado sólido. Esas “celdas” de almacenamiento dentro de los dispositivos de memoria de estado sólido se abordan fácilmente manejando las líneas de “dirección” del dispositivo con los valores binarios adecuados. Supongamos que teníamos un circuito de memoria ROM escrito, o programado, con ciertos datos, de tal manera que las líneas de dirección de la ROM sirvieron como entradas y las líneas de datos de la ROM sirvieron como salidas, generando la respuesta característica de una función lógica particular. Teóricamente, podríamos programar este chip ROM para emular cualquier función lógica que quisiéramos sin tener que alterar ninguna conexión de cables o puertas.

Considere el siguiente ejemplo de una memoria ROM de 4 x 2 bits (¡una memoria muy pequeña!) programado con la funcionalidad de medio sumador:

Si esta ROM se ha escrito con los datos anteriores (que representan una tabla de verdad de medio sumador), la activación de las entradas de dirección A y B provocará que se habiliten las celdas de memoria respectivas en el chip ROM, emitiendo así los datos correspondientes como los bits de _salida σ (Sum) y C. A diferencia del circuito de medio sumador construido con puertas o relés, este dispositivo se puede configurar para realizar cualquier función lógica con dos entradas y dos salidas, no solo la función de medio sumador. Para cambiar la función lógica, todo lo que necesitaríamos hacer es escribir una tabla diferente de datos en otro chip ROM. Incluso podríamos usar un chip EPROM que podría reescribirse a voluntad, dando la máxima flexibilidad en la función.

Es de vital importancia reconocer la importancia de este principio tal como se aplica a los circuitos digitales. Mientras que el medio sumador construido a partir de puertas o relés procesa los bits de entrada para llegar a una salida específica, la ROM simplemente recuerda cuáles deberían ser las salidas para cualquier combinación dada de entradas. Esto no es muy diferente de las “tablas de tiempos” memorizadas en la escuela primaria: en lugar de tener que calcular el producto de 5 veces 6 (5 + 5 + 5 + 5 + 5 + 5 + 5 = 30), a los escolares se les enseña a recordar que 5 x 6 = 30, y luego se espera que recuerden este producto de la memoria según sea necesario. Asimismo, en lugar de la función lógica dependiendo de la disposición funcional de las puertas o relés cableados (hardware), depende únicamente de los datos escritos en la memoria (software).

Una aplicación tan simple, con salidas definidas para cada entrada, se llama tabla de búsqueda, porque el dispositivo de memoria simplemente “busca” cuáles deberían ser las salidas para cualquier combinación dada de estados de entradas.

Esta aplicación de un dispositivo de memoria para realizar funciones lógicas es significativa por varias razones:

• El software es mucho más fácil de cambiar que el hardware.
• El software se puede archivar en varios tipos de medios de memoria (disco, cinta), proporcionando así una manera fácil de documentar y manipular la función en forma “virtual”; el hardware solo puede ser “archivado” abstractamente en forma de algún tipo de dibujo gráfico.
• El software se puede copiar de un dispositivo de memoria (como el chip EPROM) a otro, permitiendo que un dispositivo pueda “aprender” su función desde otro dispositivo.
• Software como el ejemplo de función lógica puede diseñarse para realizar funciones que serían extremadamente difíciles de emular con puertas lógicas discretas (¡o relés!).

La utilidad de una tabla de consulta se hace cada vez más evidente con la creciente complejidad de la función. Supongamos que queríamos construir un circuito sumador de 4 bits usando una ROM. Requeriríamos una ROM con 8 líneas de dirección (dos números de 4 bits para agregar juntos), más 4 líneas de datos (para la salida firmada):

Con 256 ubicaciones de memoria direccionables en este chip ROM, tendríamos una buena cantidad de programación que hacer, diciéndole qué salida binaria generar para todas y cada una de las combinaciones de entradas binarias. También correríamos el riesgo de cometer un error en nuestra programación y hacer que saliera una suma incorrecta, si no tuviéramos cuidado. Sin embargo, la flexibilidad de poder configurar esta función (o cualquier función) solo a través del software generalmente supera esos costos.

Consideremos algunas de las funciones avanzadas que podríamos implementar con el anterior “sumador”. Sabemos que cuando sumamos dos conjuntos de números en la notación firmada del complemento de 2, corremos el riesgo de tener el desbordamiento de la respuesta. Por ejemplo, si intentamos sumar 0111 (decimal 7) a 0110 (decimal 6) con solo un campo numérico de 4 bits, la respuesta que obtendremos es 1001 (decimal -7) en lugar del valor correcto, 13 (7 + 6), que no se puede expresar usando 4 bits firmados. Si quisiéramos, podríamos evitar las extrañas respuestas dadas en condiciones de desbordamiento programando este circuito de tabla de búsqueda para dar salida a otra cosa en condiciones donde sabemos que ocurrirá desbordamiento (es decir, en cualquier caso donde la suma real superaría +7 o -8). Una alternativa podría ser programar la ROM para que emita la cantidad 0111 (el valor positivo máximo que se puede representar con 4 bits firmados), o cualquier otro valor que determinemos que es más apropiado para la aplicación que el típico valor de “error” desbordado que emitiría un circuito sumador regular. Todo depende del programador decidir qué quiere que haga este circuito, porque ya no estamos limitados por las limitaciones de las funciones de puerta lógica.

Las posibilidades tampoco se detienen en funciones lógicas personalizadas. Al agregar más líneas de dirección al chip ROM de 256 x 4, podemos expandir la tabla de consulta para incluir múltiples funciones:

Con dos líneas de dirección más, el chip ROM tendrá 4 veces más direcciones que antes (1024 en lugar de 256). Esta ROM podría programarse para que cuando A8 y A9 fueran ambos bajos, los datos de salida representaran la suma de los dos números binarios de 4 bits introducidos en las líneas de dirección A0 a A7, tal como lo tuvimos con el circuito anterior de 256 x 4 ROM. Para las direcciones A8=1 y A9=0, podría programarse para emitir la diferencia (resta) entre el primer número binario de 4 bits (A0 a A3) y el segundo número binario (A4 a A7). Para las direcciones A8=0 y A9=1, podríamos programar la ROM para emitir la diferencia (resta) de los dos números en orden inverso (segundo - primero en lugar de primero - segundo), y finalmente, para las direcciones A8=1 y A9=1, la ROM podría programarse para comparar las dos entradas y emitir una indicación de igualdad o desigualdad. Lo que tendremos entonces es un dispositivo que puede realizar cuatro operaciones aritméticas diferentes en números binarios de 4 bits, todo “buscando” las respuestas programadas en él.

Si hubiéramos usado un chip ROM con más de dos líneas de dirección adicionales, podríamos programarlo con una variedad más amplia de funciones para realizar en las dos entradas de 4 bits. Hay una serie de operaciones peculiares a los datos binarios (como la comprobación de paridad o la orción exclusiva de bits) que podríamos encontrar útiles para tener programadas en una tabla de consulta de este tipo.

Dispositivos como este, que pueden realizar una variedad de tareas aritméticas según lo dictado por un código de entrada binario, se conocen como Unidades Lógicas Aritméticas (ALU), y comprenden uno de los componentes esenciales de la tecnología informática. Aunque las ALU modernas se construyen más a menudo a partir de circuitos de lógica combinacional (puerta) muy complejos por razones de velocidad, debería ser reconfortante saber que la misma funcionalidad exacta puede duplicarse con un chip ROM “mudo” programado con la (s) tabla (s) de consulta apropiada (s). De hecho, este enfoque exacto fue utilizado por los ingenieros de IBM en 1959 con el desarrollo de las computadoras IBM 1401 y 1620, que utilizaron tablas de consulta para realizar adiciones, en lugar de circuitería sumadora binaria. A la máquina se le conocía con cariño como el “CADET”, que representaba “C an 't A dd, D oesn't E ven T ry”.

Una aplicación muy común para las ROM de tablas de búsqueda es en sistemas de control donde se necesita representar una función matemática personalizada. Tal aplicación se encuentra en sistemas de inyección de combustible controlados por computadora para motores de automóviles, donde la relación adecuada de mezcla aire/combustible para un funcionamiento eficiente y limpio cambia con varias variables ambientales y operativas. Las pruebas realizadas en motores en laboratorios de investigación determinan cuáles son estas relaciones ideales para diferentes condiciones de carga del motor, temperatura ambiente y presión barométrica del aire. Las variables se miden con transductores de sensor, sus salidas analógicas convertidas a señales digitales con circuitos A/D, y aquellas señales digitales paralelas utilizadas como entradas de dirección a un chip ROM de alta capacidad programado para emitir el valor digital óptimo para la relación aire/combustible para cualquiera de estas condiciones dadas.

A veces, las ROM se utilizan para proporcionar funciones de tabla de consulta unidimensionales, para “corregir” valores de señal digitalizados para que representen con mayor precisión su importancia en el mundo real. Un ejemplo de tal dispositivo es un transmisor de termopar, que mide la señal de militensión generada por una unión de metales diferentes y emite una señal que se supone que corresponde directamente a esa temperatura de unión. Desafortunadamente, las uniones de termopar no tienen respuestas de temperatura/voltaje perfectamente lineales, por lo que la señal de voltaje bruto no es perfectamente proporcional a la temperatura. Al digitalizar la señal de voltaje (conversión A/D) y enviar ese valor digital a la dirección de una ROM programada con los valores de corrección necesarios, la programación de la ROM podría eliminar parte de la no linealidad de la relación temperatura-milivoltaje del termopar, de manera que la salida final del dispositivo sería más preciso. El término de instrumentación popular para tal tabla de consulta es un caracterizador digital.

Otra aplicación para tablas de búsqueda es en traducción de código especial. Una ROM de 128 x 8, por ejemplo, podría usarse para traducir código ASCII de 7 bits a código EBCDIC de 8 bits:

Nuevamente, todo lo que se requiere es que el chip ROM esté debidamente programado con los datos necesarios para que cada entrada ASCII válida produzca un código de salida EBCDIC correspondiente.