"Combinational Circuits" — Practice

Question 1

The sum output of a full adder is

Accepted Answer

B

Question 2

How many outputs does a 5-to-32 decoder assert simultaneously for a valid input?

Accepted Answer

A

Question 3

In which device are both the AND plane and the OR plane programmable?

Accepted Answer

A

Question 4

Implement F(A,B,C) as the sum of minterms 1, 3, 5, 6 using an 4-to-1 multiplexer with A and B on the select lines.

Accepted Answer

A 4-to-1 multiplexer has two select lines, so with A and B selecting, C becomes the residue variable and each data input must be 0, 1, C or not-C.

Take each select combination and examine the two minterms sharing it.

AB = 00 covers minterms 0 and 1. Minterm 1 is present and 0 is not. Minterm 1 has C = 1, so the output equals C. Data input 0 is wired to C.

AB = 01 covers minterms 2 and 3. Minterm 3 is present and 2 is not. Minterm 3 has C = 1, so the output equals C. Data input 1 is wired to C.

AB = 10 covers minterms 4 and 5. Minterm 5 is present and 4 is not, and 5 has C = 1, so again the output equals C. Data input 2 is wired to C.

AB = 11 covers minterms 6 and 7. Minterm 6 is present and 7 is not. Minterm 6 has C = 0, so the output equals not-C. Data input 3 is wired to not-C.

The wiring is C, C, C, not-C.

As a check, three of the four inputs being C means the function is C except when AB = 11, which is consistent with the minterm list containing all the odd minterms except 7, plus the even minterm 6.

Question 5

Derive the expression for C_3 in a carry-lookahead adder in terms of generate and propagate signals and the input carry.

Accepted Answer

Start from the recurrence C_(i+1) = G_i + P_i times C_i and unroll it.

C_1 = G_0 + P_0 C_0.

C_2 = G_1 + P_1 C_1 = G_1 + P_1 (G_0 + P_0 C_0) = G_1 + P_1 G_0 + P_1 P_0 C_0.

C_3 = G_2 + P_2 C_2 = G_2 + P_2 (G_1 + P_1 G_0 + P_1 P_0 C_0).

Expanding gives C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0.

The expression reads naturally: a carry emerges from position 3 either because position 2 generated one, or because position 2 propagated a carry that position 1 generated, or because positions 2 and 1 both propagated one that position 0 generated, or because all three propagated the incoming carry.

Every term is a product of signals available after one gate delay, so C_3 needs one AND level and one OR level, giving three gate delays in total including the G and P computation.

Note the fan-in cost: the OR gate needs four inputs and the largest AND gate needs four. By C_8 those counts reach nine, which is why lookahead is applied in blocks of four in practice.

Question 6

How many 3-to-8 decoders with enable are required to construct a 6-to-64 decoder?

Accepted Answer

A 6-to-64 decoder has 64 outputs. Each 3-to-8 decoder supplies 8 outputs, so 64 divided by 8 gives 8 decoders for the output stage.

Those eight must be selected between, exactly one active at a time. That selection is driven by the three high-order address bits, and it requires a decoder with 8 outputs to drive the eight enable inputs.

One more 3-to-8 decoder serves as that enable driver.

The three low-order address bits go in parallel to the data inputs of all eight output decoders.

The total is 9 decoders.

The general rule extracted from this: building a 2n-to-2^(2n) decoder from n-to-2^n decoders needs 2^n output decoders plus 1 enable driver. The same recursive structure appears in memory address decoding, where the high-order bits select a chip and the low-order bits select a location within it.

Question 7

The function F = AC + not-A times B is implemented directly. Identify any static hazard and give the hazard-free expression.

Accepted Answer

A static-1 hazard occurs when two adjacent minterms both give output 1 but are covered by different product terms, so that during the transition one term falls before the other rises.

Look for an input change of a single variable that moves between the two terms while keeping the output at 1.

Set B = 1 and C = 1, and let A change from 1 to 0.

Before: A = 1 makes AC = 1, so F = 1.
After: A = 0 makes not-A times B = 1, so F = 1.

The output should hold at 1 throughout. But the second term depends on A through an inverter while the first depends on A directly, so AC falls before not-A times B rises, and F dips to 0 for the inverter delay.

This is a static-1 hazard.

The fix is the consensus term of AC and not-A times B, obtained by removing the complementary variable A and multiplying the remainders: BC.

The hazard-free expression is F = AC + not-A times B + BC.

With B = C = 1 the added term is 1 throughout the transition, holding the output steady. The function itself is unchanged, since the consensus term is logically redundant, which is exactly why minimisation had removed it.

Question 8

Three functions of four variables are to be implemented: F1 needs product terms {AB, CD, A not-C}, F2 needs {AB, B not-D}, F3 needs {CD, A not-C, B not-D, AD}. Size a PLA and decide whether a PAL with 3 terms per output suffices.

Accepted Answer

For the PLA, count distinct product terms across all three functions, since the programmable OR plane allows any term to feed any output.

List them: AB appears in F1 and F2. CD appears in F1 and F3. A not-C appears in F1 and F3. B not-D appears in F2 and F3. AD appears only in F3.

The distinct terms are AB, CD, A not-C, B not-D and AD, which is 5.

So a PLA with 4 inputs, 5 product lines and 3 outputs suffices. Note the saving: the naive total of 3 plus 2 plus 4 is 9 term-slots, but only 5 physical product lines are needed because four of the terms are shared.

For the PAL, the OR plane is fixed and each output has its own allocation, so nothing can be shared and the sizing is decided by the worst single output.

F1 needs 3 terms, F2 needs 2, and F3 needs 4.

F3 exceeds the 3 terms per output that the part provides, so a PAL with 3 terms per output does not suffice. F3 would have to be split across two outputs and recombined with an external OR gate, or a PAL with at least 4 terms per output selected instead.

The contrast is the point of the device family: a PLA sizes on distinct terms in total, a PAL on the worst output.

Question 9

A 16-bit adder is built from four 4-bit carry-lookahead blocks connected by ripple carry between blocks. Estimate its worst-case delay in gate delays and compare with a pure 16-bit ripple-carry adder.

Accepted Answer

Work out the delay of one 4-bit lookahead block first.

Computing all G and P signals takes 1 gate delay, since each is a single AND or XOR of the two input bits.

The block's carry-out is a two-level sum-of-products in those signals plus the incoming carry, adding 2 more gate delays. So a block produces its carry-out 3 gate delays after its inputs and carry-in are stable.

However, only the first block starts at time zero. The G and P signals of all four blocks are computed in parallel during the first gate delay, so each subsequent block needs only the 2-delay carry logic once its carry-in arrives.

Block 0 carry-out at delay 3. Block 1 at delay 5. Block 2 at delay 7. Block 3 at delay 9.

The top sum bit needs one further XOR after the final carry, giving about 10 gate delays.

A pure 16-bit ripple-carry adder takes 2 gate delays per stage on the carry path, so 32 delays for the carry plus 1 for the final XOR, about 33.

The hybrid is roughly three times faster while using far less fan-in than a flat 16-bit lookahead, which would need 17-input gates. This block-and-ripple structure is exactly why real adders are hierarchical.

Practice — "Combinational Circuits"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities