2
\$\begingroup\$

I am a student in an introductory Digital Logic and Computer Systems course. We have been learning about ROMS, but often we just use them to basically just map truth tables onto them. We have been briefly exposed to more complex ROMS such as EEPROMS that come in 32k X 8 dimensions, and are told to ground unused address lines and just use the ones we need. I see that ROMS always have much, much less available possible outputs than possible inputs. In the EEPROM example, what is the purpose of having a 2^15 possible states as inputs that can only map onto a maximum of 8 unique words. If I were to use this in one of our assignments, about 99% of the addresses would be unused. In the "real world" what is done with all of those extra states if they are all limited to outputting the same set of 8 possible words?

edit: Thank you guys for the in-depth responses! Learned a lot

\$\endgroup\$
6
  • 3
    \$\begingroup\$ Why do you assume your method is the only way ROMs are used? Maybe your instructor is using it as a look up table to teach something. More a kludge than a legitimate use for a ROM. \$\endgroup\$ Mar 29 at 8:22
  • 8
    \$\begingroup\$ I assume your question is about parallel EEPROMs. In the "real world" these E(E)PROMs are not usually used as a substitute for real programmable logic. These types of ROMs are designed to be a (semi) permanent program or configuration memory for computers or microcontroller systems connected to an address and data bus and therefore have different requirements. \$\endgroup\$
    – StarCat
    Mar 29 at 9:55
  • 5
    \$\begingroup\$ I now see that you are also misunderstanding what a parallel E(E)PROM does. In the case of a 32kx8 E(E)PROM, it has 15 address inputs and 8 data outputs (plus some control lines), so it can map 2^15 possible input states to 2^8 possible output states (and not just 8). \$\endgroup\$
    – StarCat
    Mar 29 at 15:34
  • 19
    \$\begingroup\$ This is a little like saying "We only have 26 letters in the alphabet. Why are books so long?!?" ... ;) \$\endgroup\$
    – brhans
    Mar 29 at 18:17
  • 2
    \$\begingroup\$ If you want more output lines that's easy. Just add more ROMs, all decoding the same set of input lines. \$\endgroup\$ Mar 30 at 19:44

6 Answers 6

14
\$\begingroup\$

The other answer covers very well a real world usage, but I feel that I understand the specific OP confusion a bit better.

You seem to think that a 32k x 8 memory only has 8 output words, but that is not correct. A 32k x 8 memory has 32k words, each 8 bit wide. With such a chip you can implement any 15 bits-to-up-to-eight-bits function.

If you need to implement a 8x4 function, you will only use 8 bits for the address, and only 4 bits from the output. You should ground the unused address lines both for electrical and logical reasons; floating pins can go up and down and be erratically read by the chip.

If you need to implement a 15x8 function, you can do that easily as well.

To clarify even more, you have to imagine a 32k x 8 ROM as an excel table with 8 columns and 32k rows. You are free to write 0 or 1 in each cell, and on the output you will get the particular row (8 bits) that is selected depending on the status of the address (15 bits).

\$\endgroup\$
1
  • 4
    \$\begingroup\$ The Excel analogy is excellent \$\endgroup\$ Mar 29 at 18:37
8
\$\begingroup\$

Using a ROM as a "lookup table" may seem like a waste of space, but as an example of how you can take advantage of a lot of address space for lookups, I am reminded of a project from decades ago, in which I used an 8 bit CPU (6502) to operate upon sinusoids, of varying amplitudes.

On-the-fly calculation of \$sin(x)\$, and the subsequent scaling by multiplication (the 6502 has no multiplication instruction), is computationally expensive and slow. I used an 8 kilobyte ROM (2764) containing many copies of a single sinusoid cycle, arranged into "banks", addressable with 5 of the 13 available address lines.

Each bank contained pre-calculated sin data, pre-multiplied for a specific amplitude. I was able to select one of the 32 possible banks, to "select" the amplitude, and have immediate access to a complete cycle of appropriate sinusoid data addressable using the remaining 8 address lines (a contiguous block of 256 bytes of sin data), already scaled to the appropriate amplitude. No arithmetic necessary.

The main use for ROM has always been to store programs to be executed by a CPU. If you have software, sequences of bytes of executable machine code and associated data, that requires 32 kilobytes to contain all of the program's features and behaviour, then you can't say that a 32 kilobyte ROM (such as a 27C256 with 15 address lines) is wasted space, with far more address space than data that can occupy it.

If your program is only 8 kilobytes in size, then use a ROM that has only 8k of address space, 13 address lines (such as a 27C64), instead.

\$\endgroup\$
5
\$\begingroup\$

The main purpose of a ROM (read-only memory; PROM being a programmable ROM, EPROM an erasable programmable ROM, EEPROM an electrically erasable programmable ROM) is not to implement a truth table. This is one possible solution you learned about now.

The by far most common usage is program (and constant data) memory.

As you experienced for sure, memory is the key, the more, the better. Therefore memory devices have many "inputs" (address lines, note the name) to address the content. The "output" (data lines) are as wide as contemporary common.

The largest EPROM I came across in my career was the 27C4001 (there are bigger ones). It has 19 address lines and 8 data lines. Used as program memory it can hold up to 512 kiB.

But even if you use an EPROM just as a neat device to implement a truth table, many combinatorial circuits have more inputs than outputs.

\$\endgroup\$
3
\$\begingroup\$

The short answers:

  • (1) The 'unused' inputs can be used for added inputs in the future.
  • (2) EPROMs/ROMs are intended to support program storage using fixed width data, not logic. Therefore they're "deep", not "wide".

What is a ROM/EPROM, anyway? Think of it a group of of fixed-width (e.g., 8-bit) words, with a great big multiplexer to select one of them. The multiplexer is controlled by the address bus.

Is having such a big mux skinnying down all those available words to just a few bits wasteful? Depends how you use it.

For program storage it's just the ticket. It's possible to use 100% of the capability of this thing: in a 32KB EPROM you can store 32K bytes of code. You change the code (almost) at will, without ripping everything to pieces. No surprises here.

What if you were to do the reverse, use random logic to store code? This is much more awkward since you have to re-synthesize the entire logic array if even one code word changes. Nevertheless I've seen this approach used on security processors as a means to thwart attempts at altering critical code.

As logic, a 32K ROM/EPROM can make an arbitrary lookup table (LUT) function of 15 inputs x 8 outputs. So for each input state you have up to 256 possible (2^8) possible output states, or 8.4 million states for a 32KB device. In theory that's pretty useful.

Is it efficient though? Depends on the logic. For example, if one ROM-based LUT input is 'enable', you'd use 50% of the address space just for that one variable. That's kind of wasteful: it would make more sense to apply a gate the ROM outputs.

In fact, each unused zero-tied input wastes 50% of the remaining LUT space. So if you have a function that's, say, 6 inputs, you only need 64 entries out of the entire 32KB, so you're wasting 8.3 million states out of 8.4 million. It would make sense to use a smaller LUT device (we'll come back to this.)

What if you need more output signals than your ROM width? Then you'd need either more ROMs, or do some kind of additional logic layer on the output. As you could imagine, for anything fairly complex things get out of hand pretty quickly.

There's another problem lurking as well. ROMs-as-logic (or for that matter, any logic based on LUT) has a pitfall: the outputs can glitch because ROM/EPROMs don't guarantee stable output until the device access time is met. Even just one address line changing state could cause multiple states on the output until things settle.

Implementers using ROMs for logic need to qualify and / or synchronize the ROM outputs to avoid the glitch issue, or use them only for cases that don't care about glitches.

Despite these drawbacks, it might surprise you to learn that one of the largest applications of LUT based logic is FPGAs. FPGAs kind of split the difference: they're composed of smaller SRAM-based LUTs (6 bits in x 4 out is common now) with a flexible interconnect. These RAM-based LUTs can be connected together to make bigger functions, or they can be used as memory. But, being LUTs just like ROM/EPROMs, they too can glitch, so they must be used with care. (The FPGA EDA tools will warn about this.)

More about FPGA LUTs here: https://www.allaboutcircuits.com/technical-articles/purpose-and-internal-functionality-of-fpga-look-up-tables/

There's another type of logic that splits the difference between PROM and random gates, called a Programmable Logic Array, or PLA. PLAs provide PROM-like regularity, but unlike PROMs PLAs are organized using a sum-of-products structure, making them much more efficient than using LUTs for logic. Even better, unlike LUTs they don't suffer glitch issues.

You'll find PLAs today as the logic elements within smaller CPLDs. PLAs have been available as standalone devices since the mid 1970s. The first types were bipolar PROM fuse-blown devices from Signetics (PLA) in 1975, followed later in 1978 by Monolithic Memories (PAL).

Famously, PALs played a key role in the Data General MV/8000, as documented in Tracy Kidder's The Soul Of a New Machine.

Reprogrammable PLA- and PAL-type devices came soon after from Lattice (GAL), Altera (EP3xx) and others. Today there are several Flash-based PAL types available from Microchip (Atmel).

PLA structures are also found in ASICs as standard cells, used in place of random logic in cases where minimizing change cost and schedule are more important than minimum die area. A common example would be instruction decoding in a CPU. A mask-programmed PLA, like a ROM, can be updated by changing just one or two mask layers, compared to an all-layer tape-out for random logic. This saves considerable cost and schedule.

More about PLAs here: https://www.electrically4u.com/programmable-logic-array-pla/

\$\endgroup\$
2
  • \$\begingroup\$ For PLAs remember working on boards which were originally designed using multiple GAL22V10 24-pin DIP packages to contain logic. Sometimes a design change (or bug fix) required more complex logic, and switched to using an ATV750 which had the same pin out but increased logic terms. The datasheets linked contain diagrams showing the internal array of product terms and sum terms. \$\endgroup\$ Mar 29 at 19:02
  • \$\begingroup\$ I've used both, going all the way back to MMI PALs and Signetics PLAs. That said, those standalone PAL/PLA/GALs have largely been superseded by bigger CPLDs. But the concept of the PLA lives on in those devices. \$\endgroup\$ Mar 29 at 19:29
2
\$\begingroup\$

To take a specific example, a 24LC256 is a 32k x 8 EEPROM, but is in a 8-pin the package with 3 address lines, A0 - A2, so might appear to have only 8 addressable locations, as you describe.

The answer is that the device is accessed using a clocked serial protocol called i2c, whereby the address or data is conveyed one bit at a time. Each transfer starts by the CPU sending a bus address; this is necessary because there might be multiple devices attached to the i2c bus, and the CPU needs to indicate which it is talking to. Part of the bus address is fixed in the chip, and part is determined by those A0 - A2 lines; this allows you to connect multiple 24LC256 devices to the bus, each with a (slightly) different address, the first having A0 - A2 set to zero, the second with only A0 set to 1, the third with just A1 set to 1, and so on.

So you can see that the A0 - A2 lines are purely to allow one device to be distinguished from another, and have nothing to do with the 32k memory space. That is set using another address field that is sent to the chip after the device address - I think this is the source of your confusion.

\$\endgroup\$
2
\$\begingroup\$

In the "real world" what is done with all of those extra states if they are all limited to outputting the same set of 8 possible words?

Before flash was available, have worked on embedded computer systems where the non-volatile storage for programs used multiple EPROMs. E.g. the following shows a processor with a 32-bit data bus to which four 32Kx8 EPROMs are connected, with each EPROM providing 8-bits of data:

schematic

simulate this circuit – Schematic created using CircuitLab

Where:

  • D[0:31] is the 32-bit processor data bus, with 8-bits of the data bus connected to a different 8-bit wide output EPROM.
  • A[0:14] is the 15 processor address bus, connected in parallel to all EPROMs.
  • /RD is the processor read strobe, connected in parallel to all EPROMs. The above is a simplified schematic with no address decoding and only EPROMs shown for program storage. In most systems there could also be peripherals or SRAM/DRAM connected the processor as well.

So, the external four EPROMs provided 32K 32-bits words of non-volatile program storage for the processor.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.