¿Cómo funciona una LUT, por qué se usa?

Una tabla de búsqueda (LUT) es una forma rápida de realizar una función compleja en lógica digital. La dirección es la entrada de la función, y el valor en esa dirección es la salida de la función. La ventaja es que el cálculo de la función solo requiere una búsqueda de memoria independientemente de la complejidad de la función, por lo que es muy rápido. La desventaja es que requiere memoria, especialmente si necesita una alta resolución para la entrada de la función.

Por ejemplo, la función seno a menudo se implementa como una búsqueda de tabla. Si los ángulos de 10 bits tienen una resolución lo suficientemente buena, entonces toda la función se puede implementar como una tabla de búsqueda con 1024 entradas. (En realidad, en el caso del seno, solo se almacena 1/4 de ciclo, luego se anula o se indexa hacia atrás según el cuadrante real, pero eso es algo específico para el seno).

La entrada de la función también puede ser una combinación de diferentes variables de entrada con el resultado expresado como un solo entero. Por ejemplo, una multiplicación de 4 x 4 bits se puede implementar como una tabla de búsqueda de 256 valores. La dirección de la tabla de 8 bits puede ser los dos valores de entrada de 4 bits concatenados.

La tabla de búsqueda a menudo se implementa con RAM o celdas ROM en una matriz. Las entradas lógicas son las líneas de dirección a la matriz. Las salidas de datos de la matriz se convierten en las salidas lógicas de la LUT. Uno determina la lógica realizada por la LUT en función del lugar en el que se escriben 1 y 0. Los bits de contenido para cada columna de salida de la matriz se pueden determinar utilizando técnicas de síntesis lógica estándar para las diversas combinaciones de los bits de entrada. Tenga en cuenta que la minimización lógica real normalmente no es necesaria para una LUT porque hay bits en las columnas de salida de la matriz para cada combinación de los bits de entrada.

Puede obtener más buena información acerca de las LUT y sus usos refiriéndose a las diversas Hojas de datos de la familia de lógicas de FPGA de personas como Altera y Xilinx. Sus FPGA hacen un uso intensivo de LUT para la generación de lógica aleatoria. Normalmente, las LUT de FPGA son pequeños arreglos de RAM que se cargan desde una memoria de configuración no volátil en el momento del encendido.

Quizás la mejor manera de entender una LUT es considerar cómo se podrían enumerar todos los circuitos combinatorios que toman dos entradas y producen una salida. Si se supone que las entradas están cableadas a otras cosas, por ejemplo, "A y no B" es diferente de "B y no A", y las funciones que ignoran una o ambas entradas pueden ser útiles [por ejemplo, algo se conectará a la entrada B, pero puede que a uno no le importe lo que está generando], hay dieciséis circuitos de este tipo:

0000 Always output zero
0001 Output (not A) and (not B)
0010 Output A and (not B)
0011 Output (not B)
0100 Output (not A) and B
0101 Output (not A)
0110 Output A xor B
0111 Output A or (not B)
1000 Output (A and B)
1001 Output not (A xor B)
1010 Output A
1011 Output A or (not B)
1100 Output B
1101 Output (not A) or B
1110 Output A or B
1111 Always output 1

Cada uno de los circuitos anteriores puede ser descrito por el valor binario de cuatro dígitos a su izquierda: el primer dígito indica qué se debe emitir cuando ambas entradas están altas. El segundo dice qué debería salir si B es alto y A es bajo. El tercero dice qué hacer si A es alto y B es bajo. El cuarto dice qué hacer cuando ambas entradas están bajas.

En lugar de intentar inventar algún esquema complicado para permitir que un programador de dispositivos cambie entre varios tipos de compuertas, los fabricantes de FPGA a menudo tienen como circuito dominante un circuito similar al anterior (aunque a menudo utilizan ocho bits para describir un trío). función de entrada, o dieciséis bits para describir una función de cuatro entradas). El circuito se denomina LUT porque los N bits de entrada se utilizan para "buscar" uno de los bits de selección de modo 2 ^ N ".

Una cosa importante a tener en cuenta cuando se utilizan LUT en comparación con otros tipos de circuitos lógicos es que incluso si uno tiene un dispositivo lógico como el anterior configurado para generar "A", realmente computará "(A y B) o (A y no B) ". Como consecuencia, si un dispositivo tiene, por ejemplo, un tiempo de propagación mínimo de 2 ns y un tiempo de propagación máximo de 5 ns, luego, incluso si la entrada A permanece constante, el comportamiento de la salida se volverá no especificado 2ns después de que la entrada B cambie y permanecerá sin especificar hasta 5ns después de que la entrada B sea estable. Si la salida B está alimentando un flip flop que está cronometrado por la misma fuente que sus entradas, este problema técnico será intrascendente. Sin embargo, si la entrada B está impulsando una lógica secuencial asíncrona, estos fallos pueden provocar un comportamiento inesperado e indeseable.

Un ejemplo que viene a la mente es la tabla de búsqueda de onda sinusoidal. Si tiene un DAC y desea emitir una onda sinusoidal, puede almacenar varios valores que representan una onda sinusoidal en los primeros 90º de su forma de onda. Estos valores se pueden almacenar en la memoria contigua, desde el valor 0 hasta el valor 90.

Para producir los primeros 90º de la onda sinusoidal, lee los valores de 0 a 90 de manera incremental, luego, de 91 a 180, trabaja hacia atrás en la tabla, luego, para los siguientes 2 cuadrantes, comienza de nuevo pero niega los valores. Esto te lleva de nuevo al inicio.

Los chips DDS de los dispositivos analógicos utilizan esta técnica y si la definición de la onda sinusoidal es lo suficientemente amplia, puede omitir valores para producir frecuencias más altas.