GATE CS & IT Engineering Digital Logic Syllabus

Write the sum and carry-out expressions for a full adder with inputs $A$, $B$, and carry-in $C_{in}$.

$S = A \oplus B \oplus C_{in}$ and $C_{out} = A\cdot B + C_{in}\cdot(A \oplus B) = AB + BC_{in} + AC_{in}$.

In an $n$-bit ripple-carry adder, what is the worst-case propagation delay if each full adder has delay $t$ for sum and carry?

The carry must ripple through all stages, so the worst-case delay is proportional to $n$, approximately $n\cdot t_{carry}$ (i.e., $O(n)$). This serial carry propagation is the main speed limitation.

How does a carry-look-ahead adder reduce delay, using generate and propagate terms?

It computes generate $G_{i}=A_{i}B_{i}$ and propagate $P_{i}=A_{i}\oplus B_{i}$, then carries via $C_{i+1}=G_{i}+P_{i}C_{i}$. All carries are computed in parallel from the inputs, reducing delay from $O(n)$ to roughly $O(\log n)$ or constant levels of gate logic.

How is a full subtractor's difference and borrow expressed for inputs $A$, $B$, and borrow-in $B_{in}$?

Difference $D = A \oplus B \oplus B_{in}$ and borrow-out $B_{out} = \overline{A}B + \overline{A}B_{in} + B B_{in} = \overline{A}B + (\overline{A\oplus B})B_{in}$.

How can a single adder/subtractor circuit perform both $A+B$ and $A-B$ using $2$'s complement?

XOR each $B_{i}$ with a control line $M$ and set carry-in $C_{0}=M$. When $M=0$ it adds; when $M=1$ it inverts $B$ and adds $1$, forming $A + \overline{B} + 1 = A - B$ in $2$'s complement.

What is the difference between a latch and a flip-flop?

A latch is level-triggered (transparent while the enable/clock level is active), whereas a flip-flop is edge-triggered (responds only at the clock's rising or falling edge). Flip-flops give better timing control in synchronous design.

Give the characteristic equation of an SR flip-flop and its forbidden input condition.

$Q_{next} = S + \overline{R}\cdot Q$ with the constraint $S\cdot R = 0$. The condition $S=R=1$ is forbidden (invalid/indeterminate output).

What is the characteristic equation of a D flip-flop, and what is its main use?

$Q_{next} = D$. The output simply follows the input at the clock edge. It is used for data storage, registers, and to remove the indeterminate state of the SR flip-flop.

Write the characteristic equation of a JK flip-flop and describe its behavior when $J=K=1$.

$Q_{next} = J\cdot\overline{Q} + \overline{K}\cdot Q$. When $J=K=1$ the output toggles: $Q_{next} = \overline{Q}$. The JK flip-flop removes the forbidden state of the SR type.

What is the characteristic equation of a T flip-flop, and how is it derived from a JK flip-flop?

$Q_{next} = T\oplus Q = T\overline{Q} + \overline{T}Q$. It is formed by tying $J=K=T$ in a JK flip-flop, so $T=1$ toggles and $T=0$ holds the state.

What is the difference between synchronous and asynchronous (preset/clear) inputs on a flip-flop?

Synchronous inputs (e.g., D, J, K) take effect only at the clock edge. Asynchronous inputs (preset/clear) override the clock and set or reset the output immediately, independent of the clock.

State the excitation table of a JK flip-flop (required $J$, $K$ for each $Q \to Q_{next}$ transition).

$0\to0$: $J=0, K=X$. $0\to1$: $J=1, K=X$. $1\to0$: $J=X, K=1$. $1\to1$: $J=X, K=0$. ($X$ denotes don't-care.)

What are setup time and hold time for a flip-flop?

Setup time ($t_{su}$) is the minimum interval the data input must be stable before the clock edge. Hold time ($t_{h}$) is the minimum interval the data must remain stable after the clock edge. Violating either causes metastability.

What is the difference between a synchronous and an asynchronous (ripple) counter?

In a synchronous counter all flip-flops share the same clock and toggle simultaneously, giving low delay. In an asynchronous (ripple) counter the clock of each stage is driven by the previous stage's output, so delays accumulate ($O(n)$) and glitches can occur.

How many flip-flops are needed for a MOD-$N$ counter, and what is the relationship to $N$?

The number of flip-flops is the smallest integer $n$ such that $2^{n} \geq N$, i.e., $n = \lceil \log_{2} N \rceil$. A MOD-$N$ counter has $N$ distinct states ($0$ to $N-1$).

What is the maximum modulus of an $n$-bit ripple counter, and what is its worst-case propagation delay?

Maximum modulus is $2^{n}$. Worst-case delay is the sum of all stage delays, approximately $n\cdot t_{pd}$, because the toggle ripples sequentially through every flip-flop.

What distinguishes a ring counter from a Johnson (twisted-ring) counter, including their number of states for $n$ flip-flops?

A ring counter circulates a single $1$ and has $n$ valid states. A Johnson counter feeds back the complemented output of the last stage, producing $2n$ valid states. Both avoid decoding gates for individual states.

How is a MOD-$10$ (decade) ripple counter created from a $4$-bit binary counter?

Use $4$ flip-flops (max MOD-$16$) and add a feedback gate (e.g., NAND of outputs $Q_{3}$ and $Q_{1}$) that asynchronously clears all flip-flops when the count reaches $1010_{2}=10$, resetting the sequence to $0000$.

What is the purpose of a Karnaugh map (K-map), and how are its cells arranged?

A K-map is a graphical tool for minimizing Boolean functions. Cells are arranged so that physically adjacent cells differ in exactly one variable (Gray-code ordering), allowing visual grouping of $1$s to eliminate variables.

What are the rules for forming groups in a K-map to minimize a function?

Groups must contain $2^{k}$ adjacent $1$s (i.e., $1,2,4,8,\ldots$), be rectangular, be as large as possible, may wrap around edges, and may overlap. Each group eliminates $k$ variables; cover all $1$s with the fewest, largest groups.

Define implicant, prime implicant, and essential prime implicant in K-map minimization.

An implicant is any valid grouping (product term) covering only $1$s. A prime implicant is an implicant not contained in any larger group. An essential prime implicant is a prime implicant that uniquely covers at least one minterm not covered by any other prime implicant.

How are don't-care conditions used in K-map minimization?

Don't-care cells (denoted $X$ or $d$) may be treated as either $0$ or $1$, whichever yields larger groups and a simpler expression. They are included in a group only when doing so helps minimization, never required to be covered.

For a $4$-variable K-map, how many variables are eliminated by groups (octet, quad, pair, single)?

An octet ($8$ cells) leaves $1$ variable (eliminates $3$); a quad ($4$ cells) leaves $2$ variables (eliminates $2$); a pair ($2$ cells) leaves $3$ variables (eliminates $1$); a single cell ($1$) leaves all $4$ variables.

What is the Quine-McCluskey method, and what advantage does it have over the K-map?

It is a tabular, systematic minimization algorithm that groups minterms by the number of $1$s and repeatedly combines terms differing in one bit to find prime implicants. Unlike the K-map, it scales to any number of variables and is fully algorithmic (computer-implementable).

Describe the two main stages of the Quine-McCluskey method.

Stage 1: determine all prime implicants by listing minterms (and don't-cares) grouped by their count of $1$s and iteratively combining pairs differing in a single bit (marking combined terms with a dash). Stage 2: build a prime implicant chart and select essential prime implicants to cover all minterms minimally.

In Quine-McCluskey, when can two terms be combined, and how is the combined term written?

Two minterms can be combined only if they differ in exactly one bit position. The differing bit is replaced by a dash ($-$), representing the eliminated variable. Example: $0100$ and $0110$ combine to $01{-}0$.

How is a fixed-point number represented, and what determines its range and resolution?

A fixed-point number allocates a fixed number of integer bits and fractional bits around an implied binary point. For $i$ integer and $f$ fraction bits the resolution (step) is $2^{-f}$, and the range is fixed; precision is uniform across the whole range.

How do you convert the fractional decimal $0.625$ to binary fixed-point form?

Multiply by $2$ repeatedly, recording integer parts: $0.625\times2=1.25\to1$; $0.25\times2=0.5\to0$; $0.5\times2=1.0\to1$. Reading top-down gives $0.101_{2}$, i.e., $0.625 = 2^{-1}+2^{-3}$.

In the IEEE-754 single-precision (32-bit) floating-point format, how are the bits allocated and what is the value formula for a normalized number?

$1$ sign bit, $8$ exponent bits (bias $127$), and $23$ fraction (mantissa) bits. Value $= (-1)^{S}\times 1.M \times 2^{(E-127)}$, where the leading $1$ of the mantissa is implicit (hidden bit).

In IEEE-754, how are zero, infinity, and NaN encoded using the exponent and mantissa fields?

Zero: exponent all $0$s and mantissa all $0$s (signed $\pm0$). Infinity: exponent all $1$s and mantissa $0$. NaN: exponent all $1$s and mantissa $\neq 0$. Denormalized numbers: exponent all $0$s with nonzero mantissa (no implicit leading $1$).

Compare fixed-point and floating-point representations in terms of range, precision, and hardware.

Fixed-point has limited range but uniform (absolute) precision and simpler, faster, cheaper hardware. Floating-point offers a much wider dynamic range with relative precision (precision varies with magnitude) but needs more complex hardware and has rounding/normalization overhead.