Digital Logic synthesis and cumulative review

Use this after the teaching sequence

This is a bounded synthesis lesson with six original diagnostic MCQs, not a full GATE mock, a score predictor or a replacement for the preceding lessons. It combines representation, minimization, circuit realization, state behavior and timing. A correct number obtained under the wrong representation or sampling assumption is still the wrong solution.

Prerequisites are the completed Digital Logic teaching sequence: integer/fixed/floating representation and arithmetic; Boolean/K-map/tabular methods; combinational components and timing; flip-flops, registers, counters and FSM design/reduction. Carry lookahead, Booth, decimal codes and alternate counters are selected implementations of those broader areas, not separately named official syllabus clauses. Revisit a prerequisite when the method below is unfamiliar rather than trying to memorize the answer key.

A five-stage reasoning routine

1. Write the contract. Identify bit width, signedness, scale, code, bit order, valid inputs, clock edge and rounding rule. “Four bits” alone is not a complete number representation; “a counter” alone does not define its sequence.
2. Build an exact reference. Decode operands into mathematical values, enumerate the small truth/state table, or write the required transfer equation. Keep this reference separate from truncated or rounded storage.
3. Choose the mechanism. Select an arithmetic algorithm, cover, MUX/decoder realization or flip-flop excitation method that actually implements the reference.
4. Check boundaries. Test zero, most-negative values, invalid codes, unused states, tie rounding and input transitions. A don't-care is permission from the specification, not permission from convenience.
5. Check implementation constraints separately. Verify resource/width limits, old-state updates, propagation deadlines and earliest-change/hold constraints. Functional equivalence is necessary but does not prove identical timing or hazard behavior.

For a wrong answer, classify the failure before repeating calculations: representation, arithmetic width, Boolean specification, state/update order, or timing assumption. That diagnosis tells you which earlier lesson to revisit.

Worked synthesis 1: fixed-point addition and widening

Use signed six-bit two's-complement storage with two fractional bits. If the stored signed integer is I, value=I/4; resolution is1/4 and range is−8…7.75. This scale is explicit, so no ambiguous Q-format naming convention is needed.

Let x=5.5 and y=3. Their stored integers are22=010110 and12=001100. Exact sum is8.5. Adding patterns gives100010, whose six-bit signed integer is34−64=−30, so the retained numerical value is−7.5. The exact result exceeds7.75: this is signed overflow, not a rounding issue. Both inputs and their exact sum are multiples of the scale step.

Widen both operands to seven signed bits while keeping two fractional bits. Their stored integers remain22 and12; the new range is−16…15.75. Sum34 is seven-bit0100010 and decodes to8.5 exactly. Widening the original operands fixes the range problem. Widening the already-overflowed result100010 by sign extension would preserve−7.5, not reconstruct the lost sum. This distinguishes prevention from repair after information was discarded.

Worked synthesis 2: a floating midpoint

Reuse a fully specified seven-bit toy format: sign1,exponent3,fraction3, bias3. For exponent field e=1…6, value=(−1)^s(1+f/8)2^(e−3). For e=0,value=(−1)^s(f/8)2^(1−3), including signed zero when f=0. Exponent e=7 is reserved for infinity when f=0 and NaN when f≠0. Round finite results to nearest, ties to even. This is a teaching format, not IEEE binary32.

Consider1.75+1/16. The first operand is normal1.110₂×2^0,fields0|011|110. The second is subnormal f=2 because2/32=1/16,fields0|000|010. Exact sum is29/16=1.8125. Nearby representable numbers are1.75 and1.875, each1/16 away. Their retained fraction integers are6 and7, so ties-to-even chooses6: stored result1.75 again.

Nothing “failed to add”: the exact sum changed, but rounding chose the same stored value. Do not call this integer overflow, and do not assume an arithmetic identity guarantees exact stored equality after rounding. Keep the exact rational result, adjacent grid points and tie decision visible.

Worked synthesis 3: one function, multiple realizations

Take F(A,B,C)=Σm(0,2,5,7),with index4A+2B+C and no don't-cares. The pairs(0,2) and(5,7) differ only in B. Their implicants are A′C′ and AC, giving F=A′C′+AC. These are the only maximal valid cubes, and both are essential. No four-cell cube avoids the off-set, so two terms with four literals are minimum under the stated lexicographic cost: first terms, then literals.

The result is A XNOR C; B is irrelevant to the settled function. With A as a2:1 MUX select, choose I0=C′ and I1=C. For A=0 the required restriction is C′; for A=1 it is C. This is a cofactor check, not a guess from a pattern of ones.

Every adjacent on-set pair is covered by one of the two implicants, so the two-level SOP satisfies the single-input static-1 bridging criterion. That does not guarantee glitch-free behavior when A and C change together. For example endpoints A,C=00 and11 both give1, but an intermediate01 or10 gives0. Boolean minimization, implementation selection and transition assumptions answer different questions.

Worked synthesis 4: a saturating state machine

Use two rising-edge D flip-flops Q_1Q_0 as an unsigned count0…3. A synchronous reset r=1 loads00 with highest priority. Otherwise enable e=1 increments unless already at3; e=0 holds. The Moore output full=Q_1Q_0 indicates the current saturated state. All four patterns are legal; there are no unused-state don't-cares.

For r=0, the eight(Q,e) rows imply

D_1=Q_1 OR(e AND Q_0); D_0=(Q_0 XOR e) OR(Q_1 AND Q_0).

When Q=11 these equations keep11 even for e=1; ordinary modulo-four increment would wrap to00 and violate the specification. Apply reset by selecting00 instead of these D inputs whenever r=1. Starting at00 with reset inactive, e sequence1,1,0,1,1 produces states01,10,10,11,11 after successive edges. Use old Q in both equations; do not update one bit and feed it into the other at the same edge.

Now specify zero clock skew, maximum clock-to-Q0.5ns,maximum next-state logic delay4ns,and setup0.7ns. Setup requires period at least5.2ns. If minimum clock-to-Q0.2ns,minimum logic delay0.3ns,and hold0.6ns,then0.2+0.3=0.5ns fails hold by0.1ns. Merely slowing the clock does not fix that same-edge condition. Adding sufficient minimum data-path delay is one possible remedy, but its maximum delay must also be included when rechecking setup. The state equations can be correct while the physical timing budget is not.

Consolidation checklist

• For number questions, decode, compute exactly, check range, then round or retain bits under the stated rule. Carry and signed overflow are different checks.
• For minimization, write on-set,off-set and allowed don't-cares; verify coverage, cost and any hazard requirement separately. Prime does not mean essential.
• For components, state select/enable polarity and invalid-input behavior. A priority code, parity code, Gray code and BCD digit have different meanings.
• For state machines, check every allowed state/input pair, reset priority, source snapshots and output observation time. Equivalent current outputs alone do not prove equivalent states.
• For timing, compare maximum-path setup and minimum-path hold independently. Counter ripple transients and single-input hazard guarantees require their stated models.

The practice below samples several of these connections. Six correct choices are not evidence that every Digital Logic skill is mastered. Re-derive each explanation, then test a nearby boundary case yourself.

Original practice

These six single-correct MCQs are original learning questions, not previous-year questions. Choose exactly one option.

C01. Signed six-bit fixed-point has value I/4. Add patterns 010010 and 001110, retaining six bits. Which result is correct?

A. Exact8; retained100000 means−8; signed overflow occurs. B. Exact8; retained100000 means+8; no overflow. C. Exact4; retained010000; no overflow. D. Exact8; retained100000 means−8 solely because of rounding.

Answer: A

A is correct: stored integers18+14=32 represent4.5+3.5=8; six-bit32 decodes−32, the retained value is−8, while exact+8 is outside−8…7.75.

B is incorrect: top-bit-one100000 is signed−32, not+32, before scaling.

C is incorrect: the scale is fixed; the exact sum is8, not4.

D is incorrect: all values lie on the1/4 grid; the failure is range overflow, not quantization.

C02. In the stated s1/e3/f3,bias3 toy float, round1.75+1/16 to nearest,ties-to-even. What value is stored?

A. 1.875 B. 1.75 C. 1.8125 exactly D. 2.0

Answer: B

A is incorrect: both neighbors tie, but this one has odd retained fraction7.

B is correct: the exact midpoint1.8125 rounds to the neighbor with even retained fraction6.

C is incorrect: it needs more fraction precision than the format provides at this exponent.

D is incorrect:2.0 is farther away than either adjacent grid point.

C03. For F(A,B,C)=Σm(1,3,4,6),index4A+2B+C,no don't-cares, implement F with a2:1 MUX selected by A. What are(I0,I1)?

A. (C′,C) B. (B,B′) C. (C,C′) D. (0,1)

Answer: C

A is incorrect: that gives the complement,XNOR,whose on-set is0,2,5,7.

B is incorrect: the required function is independent of B.

C is correct: A=0 requires C,while A=1 requires C′; F=A′C+AC′.

D is incorrect: those constant inputs produce A alone,not A XOR C.

C04. The stated two-bit saturating counter starts00 with reset inactive. For e=1,0,1,1,1 at successive edges, which post-edge sequence is correct?

A. 01,10,11,00,01 B. 01,01,10,11,00 C. 00,00,01,10,11 D. 01,01,10,11,11

Answer: D

A is incorrect: e=0 must hold and saturation must prevent wraparound.

B is incorrect: the last step wrongly wraps from saturated11 to00.

C is incorrect: the first enabled edge must already increment00 to01.

D is correct: increment,hold,increment,increment,then hold at the maximum.

C05. Zero-skew timing has t_cq,max=0.5ns,t_pd=4ns,setup=0.7ns,t_cq,min=0.2ns,t_cd=0.3ns,hold=0.6ns. Which assessment is correct?

A. Period≥5.2ns meets setup,but hold still fails by0.1ns. B. Period≥5.2ns automatically fixes every hold violation. C. Period≥4ns suffices and hold passes. D. Period≤0.5ns fixes both constraints.

Answer: A

A is correct: maximum path0.5+4+0.7=5.2; minimum path0.2+0.3=0.5<0.6.

B is incorrect: hold is a same-edge earliest-arrival condition,not repaired by a longer period.

C is incorrect: it omits register/setup delays and mischecks the minimum path.

D is incorrect: a shorter period worsens setup and does not change the hold inequality.

C06. Multiply signed four-bit−8 by+3 exactly into eight bits,then retain only four bits. Which conclusion is correct?

A. Full00011000; low1000 is exact+8. B. Full11101000; low1000 means−8,so signed narrowing loses the exact−24. C. Full11101000; low1000 still means−24. D. Full11111000; no width change is needed.

Answer: B

A is incorrect: the mathematical product is negative,and four-bit1000 means−8.

B is correct:256−24=232=11101000;−24 does not fit−8…7,so the retained signed value differs.

C is incorrect: four-bit two's complement cannot represent−24.

D is incorrect:11111000 encodes−8,the original multiplicand rather than its product.

Scope and sources

This is one bounded Digital Logic lesson, not complete GATE CS coverage. The official syllabus establishes relevance only; the derivations, examples and practice are original. Technical references were used to check representation and circuit conventions, not to reproduce their exercises.

• Official GATE 2027 CS syllabus Section 2
• MIT combinational synthesis conventions
• MIT sequential timing and old-state conventions
• Oracle floating-point format and rounding conventions

Sources checked 14 October 2026.