16.2. Lookup tablesHaving learned about digital memory devices in the last chapter, we know that it is possible to store binary data within solidstate devices. Those storage "cells" within solidstate memory devices are easily addressed by driving the "address" lines of the device with the proper binary value(s). Suppose we had a ROM memory circuit written, or programmed, with certain data, such that the address lines of the ROM served as inputs and the data lines of the ROM served as outputs, generating the characteristic response of a particular logic function. Theoretically, we could program this ROM chip to emulate whatever logic function we wanted without having to alter any wire connections or gates. Consider the following example of a 4 x 2 bit ROM memory (a very small memory!) programmed with the functionality of a half adder:
If this ROM has been written with the above data (representing a halfadder's truth table), driving the A and B address inputs will cause the respective memory cells in the ROM chip to be enabled, thus outputting the corresponding data as the Σ (Sum) and C_{out} bits. Unlike the halfadder circuit built of gates or relays, this device can be set up to perform any logic function at all with two inputs and two outputs, not just the halfadder function. To change the logic function, all we would need to do is write a different table of data to another ROM chip. We could even use an EPROM chip which could be rewritten at will, giving the ultimate flexibility in function. It is vitally important to recognize the significance of this principle as applied to digital circuitry. Whereas the halfadder built from gates or relays processes the input bits to arrive at a specific output, the ROM simply remembers what the outputs should be for any given combination of inputs. This is not much different from the "times tables" memorized in grade school: rather than having to calculate the product of 5 times 6 (5 + 5 + 5 + 5 + 5 + 5 = 30), schoolchildren are taught to remember that 5 x 6 = 30, and then expected to recall this product from memory as needed. Likewise, rather than the logic function depending on the functional arrangement of hardwired gates or relays (hardware), it depends solely on the data written into the memory (software). Such a simple application, with definite outputs for every input, is called a lookup table, because the memory device simply "looks up" what the output(s) should to be for any given combination of inputs states. This application of a memory device to perform logical functions is significant for several reasons:
The usefulness of a lookup table becomes more and more evident with increasing complexity of function. Suppose we wanted to build a 4bit adder circuit using a ROM. We'd require a ROM with 8 address lines (two 4bit numbers to be added together), plus 4 data lines (for the signed output):
With 256 addressable memory locations in this ROM chip, we would have a fair amount of programming to do, telling it what binary output to generate for each and every combination of binary inputs. We would also run the risk of making a mistake in our programming and have it output an incorrect sum, if we weren't careful. However, the flexibility of being able to configure this function (or any function) through software alone generally outweighs that costs. Consider some of the advanced functions we could implement with the above "adder." We know that when we add two sets of numbers in 2's complement signed notation, we risk having the answer overflow. For instance, if we try to add 0111 (decimal 7) to 0110 (decimal 6) with only a 4bit number field, the answer we'll get is 1001 (decimal 7) instead of the correct value, 13 (7 + 6), which cannot be expressed using 4 signed bits. If we wanted to, we could avoid the strange answers given in overflow conditions by programming this lookup table circuit to output something else in conditions where we know overflow will occur (that is, in any case where the real sum would exceed +7 or 8). One alternative might be to program the ROM to output the quantity 0111 (the maximum positive value that can be represented with 4 signed bits), or any other value that we determined to be more appropriate for the application than the typical overflowed "error" value that a regular adder circuit would output. It's all up to the programmer to decide what he or she wants this circuit to do, because we are no longer limited by the constraints of logic gate functions. The possibilities don't stop at customized logic functions, either. By adding more address lines to the 256 x 4 ROM chip, we can expand the lookup table to include multiple functions:
With two more address lines, the ROM chip will have 4 times as many addresses as before (1024 instead of 256). This ROM could be programmed so that when A8 and A9 were both low, the output data represented the sum of the two 4bit binary numbers input on address lines A0 through A7, just as we had with the previous 256 x 4 ROM circuit. For the addresses a8="1" and a9="0", it could be programmed to output the difference (subtraction) between the first 4bit binary number (A0 through A3) and the second binary number (A4 through A7). For the addresses a8="0" and a9="1", we could program the ROM to output the difference (subtraction) of the two numbers in reverse order (second  first rather than first  second), and finally, for the addresses a8="1" and a9="1", the ROM could be programmed to compare the two inputs and output an indication of equality or inequality. What we will have then is a device that can perform four different arithmetical operations on 4bit binary numbers, all by "looking up" the answers programmed into it. If we had used a ROM chip with more than two additional address lines, we could program it with a wider variety of functions to perform on the two 4bit inputs. There are a number of operations peculiar to binary data (such as parity check or ExclusiveORing of bits) that we might find useful to have programmed in such a lookup table. Devices such as this, which can perform a variety of arithmetical tasks as dictated by a binary input code, are known as Arithmetic Logic Units (ALUs), and they comprise one of the essential components of computer technology. Although modern ALUs are more often constructed from very complex combinational logic (gate) circuits for reasons of speed, it should be comforting to know that the exact same functionality may be duplicated with a "dumb" ROM chip programmed with the appropriate lookup table(s). In fact, this exact approach was used by IBM engineers in 1959 with the development of the IBM 1401 and 1620 computers, which used lookup tables to perform addition, rather than binary adder circuitry. The machine was fondly known as the "CADET," which stood for "Can't Add, Doesn't Even Try." A very common application for lookup table ROMs is in control systems where a custom mathematical function needs to be represented. Such an application is found in computercontrolled fuel injection systems for automobile engines, where the proper air/fuel mixture ratio for efficient and clean operation changes with several environmental and operational variables. Tests performed on engines in research laboratories determine what these ideal ratios are for varying conditions of engine load, ambient air temperature, and barometric air pressure. The variables are measured with sensor transducers, their analog outputs converted to digital signals with A/D circuitry, and those parallel digital signals used as address inputs to a highcapacity ROM chip programmed to output the optimum digital value for air/fuel ratio for any of these given conditions. Sometimes, ROMs are used to provide onedimensional lookup table functions, for "correcting" digitized signal values so that they more accurately represent their realworld significance. An example of such a device is a thermocouple transmitter, which measures the millivoltage signal generated by a junction of dissimilar metals and outputs a signal which is supposed to directly correspond to that junction temperature. Unfortunately, thermocouple junctions do not have perfectly linear temperature/voltage responses, and so the raw voltage signal is not perfectly proportional to temperature. By digitizing the voltage signal (A/D conversion) and sending that digital value to the address of a ROM programmed with the necessary correction values, the ROM's programming could eliminate some of the nonlinearity of the thermocouple's temperaturetomillivoltage relationship, so that the final output of the device would be more accurate. The popular instrumentation term for such a lookup table is a digital characterizer.
Another application for lookup tables is in special code translation. A 128 x 8 ROM, for instance, could be used to translate 7bit ASCII code to 8bit EBCDIC code:
Again, all that is required is for the ROM chip to be properly programmed with the necessary data so that each valid ASCII input will produce a corresponding EBCDIC output code.
