ROM, PLA and PAL questions look like three device families to memorise. In an exam, however, they reduce to one picture with two stages: an AND array forms minterms or product terms, and an OR array combines them into outputs.
Once you know which stage is fixed and which is programmable, ROM sizing and minimum-product-term questions become mechanical. The same two functions show how implementation differs across all three devices.
1. The AND array / OR array picture
In sum-of-products form, each output is an OR of product terms. The AND stage forms those terms. The OR stage selects which terms feed each function.
ROM: The AND array is a fixed decoder that generates all
2^nminterms. The OR array is programmable.PLA: Both the AND array and the OR array are programmable.
PAL: The AND array is programmable, but the OR array is fixed. Each output has its assigned product-term slots.
This gives the exam's key distinction. A PLA can form one product term and route that line to more than one output. A PAL cannot freely route a neighbour's product line through its fixed OR arrangement, so a common term may need to be generated separately for each output.
ROM takes a different route. It generates every minterm whether the simplified functions use those minterms conveniently or not. That is why ROM size depends on input and output counts, not on K-map minimisation.
2. Two functions and their truth table
Take three inputs A, B, C and two outputs:
F1 = C + A'B
F2 = C' + A'B
The product A'B is shared. In minterm notation:
F1 = Sum m(1, 2, 3, 5, 7)
F2 = Sum m(0, 2, 3, 4, 6)
Verify that expansion instead of trusting it. When A = 0 and B = 1, A'B = 1 for addresses 010 and 011, so both functions are 1 at minterms 2 and 3. Outside those addresses, F1 follows C, giving odd minterms 1, 5 and 7 in addition. F2 follows C', giving even minterms 0, 4 and 6 in addition.
The complete truth table is:
A | B | C | F1 | F2 | Stored word F1F2 |
|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 1 | 01 |
0 | 0 | 1 | 1 | 0 | 10 |
0 | 1 | 0 | 1 | 1 | 11 |
0 | 1 | 1 | 1 | 1 | 11 |
1 | 0 | 0 | 0 | 1 | 01 |
1 | 0 | 1 | 1 | 0 | 10 |
1 | 1 | 0 | 0 | 1 | 01 |
1 | 1 | 1 | 1 | 0 | 10 |
If deriving these expressions is the hard step, revise Boolean algebra and K-map minimisation before counting hardware.
3. ROM implementation and its size
Three inputs provide 2^3 = 8 addresses. Two outputs mean that every address stores a 2-bit word. Therefore:
ROM size = 2^n words x m bits per word
= 2^3 x 2
= 8 words x 2 bits
= 16 bits
Reading the truth table from address 000 through 111, the eight stored words are:
01, 10, 11, 11, 01, 10, 01, 10
Notice what did not enter the size calculation: the number of product terms in the simplified functions. Whether the functions are one literal or a long expression, a ROM with n address inputs and m outputs still requires 2^n x m stored bits in this model.
For this example, the fixed decoder forms all eight minterms. The programmable OR connections select minterms 1, 2, 3, 5 and 7 for F1, and minterms 0, 2, 3, 4 and 6 for F2.
4. PLA implementation and minimum product terms
A PLA does use minimisation because its programmable AND array forms only the selected product terms. Across both functions, list distinct products:
A'B, used byF1andF2.C, used byF1.C', used byF2.
There are three distinct terms, not four. The AND array forms A'B once, and the programmable OR array connects that same line to both outputs. Thus the implementation is a 3-input, 3-product-term, 2-output PLA, commonly written 3 x 3 x 2.
The count must be taken across the whole PLA, not separately per output. If two outputs use an identical product term, count that physical AND line once. A similar-looking term with one literal changed is a different product and needs its own line.
5. PAL implementation: why it costs more here
In a PAL, the programmable AND stage can create the required products, but the fixed OR arrangement assigns product-term slots to particular outputs. The A'B line used for F1 cannot simply be shared with F2 as it was in the PLA.
Count by output:
F1needs its ownA'BandC, so it uses 2 terms.F2needs its ownA'BandC', so it uses 2 terms.Total PAL AND terms used here:
2 + 2 = 4.
The PLA used three physical product terms. The PAL uses four because A'B is generated once in each output's assigned group. This does not make PAL universally inferior. Its fixed OR stage can favour simpler, faster hardware. The question here asks about term sharing, and on that measure the PLA wins.
The wider combinational picture is covered in combinational circuits, multiplexers, decoders and adders. A ROM's fixed decoder is much easier to remember when you connect it to decoder behaviour.
6. The traps GATE builds these on
Minimising before sizing a ROM. Wrong approach. Use the number of input address lines and outputs.
Writing
n x mfor ROM capacity. The number of words is2^n, so capacity is2^n x mbits.Counting PLA terms output by output. Shared products count once across the PLA.
Letting a PAL share like a PLA. Its fixed OR arrangement prevents that free sharing.
Counting literals instead of product terms.
A'Bhas two literals but is one product term.Treating
CandC'as one term. They are distinct products and require separate AND lines.
When a question supplies functions, minimise them first for PLA or PAL, then build a set of distinct products and inspect routing. For ROM, go directly to 2^n x m and, if asked for contents, create the truth table.
7. How GATE tests this and the official pointer
Typical questions ask for the ROM size needed to implement m functions of n variables, the minimum number of PLA product terms, or the device that allows a product to feed multiple outputs. The arithmetic is short, which means the device model usually decides the mark.
Digital Electronics is part of the official GATE scope. Check the official GATE portal for your cycle for the current syllabus and any mark-share information. KnowledgeGate's practice bank has about 1,600 Digital Electronics questions across combinational and programmable logic, so you can practise the distinction in several forms. The GATE category gives the broader preparation context.
8. Key differences and practice
ROM uses a fixed decoder and programmable OR, so n inputs and m outputs need 2^n x m bits. PLA programs both arrays and counts distinct shared products, which gives three terms here. PAL programs the AND array but fixes the OR arrangement, so the shared A'B is duplicated and the count becomes four.
Rebuild the truth table and term list once without looking. Then use GATE Guidance by Sanchit Sir for the connected Digital Electronics sequence and the GATE test series for timed sizing and implementation questions.
