Digital Logic

Sheet 1

Number Systems & Codes

5 formulas

Core concepts

• 2's complement = 1's complement (bitwise NOT) + 1
• Excess/bias representation: stored value = actual value + bias
• IEEE-754 single precision: 1 sign + 8 exponent (bias 127) + 23 mantissa bits

Key formulas

Unsigned Range ☆

\[ 0 \text{ to } 2^n{-}1 \]

n-bit unsigned

2's Complement Range ☆

\[ -2^{n-1} \text{ to } 2^{n-1}{-}1 \]

2's Complement ☆

\[ 1\text{'s complement} + 1 \]

Gray → Binary ☆

\[ b_0{=}g_0,\ b_i = b_{i-1}\oplus g_i \]

Binary → Gray ☆

\[ g_0{=}b_0,\ g_i = b_{i-1}\oplus b_i \]

Test your recall

Can you recall the unsigned range formula?

Reveal formula

\[ 0 \text{ to } 2^n{-}1 \]

GATE traps 4 traps

2's complement has one zero

2's complement has exactly ONE representation of zero (unlike 1's complement's +0/-0) -- this is exactly why its negative range is one number larger than its positive range.

Carry-out ≠ overflow

Overflow in 2's complement addition happens when two numbers of the SAME sign produce a result of the opposite sign -- a carry out of the MSB alone does NOT by itself indicate overflow, a very common misconception.

Fraction-to-binary may never terminate

Converting a fraction to binary by repeated multiplication by 2 can go on forever -- GATE questions specify a fixed number of bits and expect you to truncate/round, not chase exact termination.

Gray code changes exactly one bit

Gray code changes exactly ONE bit between any two consecutive values -- a fast way to spot a wrong option instantly without re-deriving the whole sequence.

Sheet 2

Boolean Algebra & K-Maps

5 formulas

Core concepts

• K-map groupings must be sized in powers of 2: 1, 2, 4, 8...

Key formulas

De Morgan's Laws ☆

\[ (A{+}B)' = A'B' \qquad (AB)' = A'{+}B' \]

Absorption Law ☆

\[ A + AB = A \qquad A(A{+}B) = A \]

Consensus Theorem ☆

\[ AB + A'C + BC = AB + A'C \]

BC term is redundant

Boolean Functions Count ☆

\[ 2^{2^n} \]

functions of n variables

XOR / XNOR ☆

\[ A \oplus B = AB'{+}A'B \qquad A \odot B = AB{+}A'B' \]

Test your recall

Can you recall the de morgan's laws formula?

Reveal formula

\[ (A{+}B)' = A'B' \qquad (AB)' = A'{+}B' \]

GATE traps 4 traps

Exploit don't-cares

A 'don't care' (X) in a K-map can be treated as 0 or 1, whichever gives the simpler grouping -- failing to exploit don't-cares is the most common missed optimization.

Essential PIs are mandatory

Essential prime implicants MUST appear in the minimal SOP; non-essential PIs are optional (pick whichever combination covers the rest with fewest terms) -- GATE frequently asks you to identify which PI is essential.

Groupings must be rectangular powers of 2

K-map groupings must be rectangular (including wraparound) and sized in powers of 2 -- diagonal or non-power-of-2 groupings are invalid, an easy slip under time pressure.

SOP and POS must agree

SOP and POS minimizations of the same function can look structurally very different but must be logically equivalent -- cross-check with a truth table if genuinely unsure.

Sheet 3

Combinational Circuits

3 formulas

Core concepts

• Combinational circuit output depends only on the current inputs, with no memory of past state
• A 2^n:1 MUX can directly implement any n-variable Boolean function (tie each data input to that row's output value)
• Mux: 2^n select lines -> 2^n inputs, 1 output. Decoder: n inputs -> 2^n outputs

Key formulas

Half Adder ☆

\[ \text{Sum} = A \oplus B \qquad \text{Carry} = AB \]

Full Adder ☆

\[ \text{Sum} = A \oplus B \oplus C_{in} \qquad C_{out} = AB{+}BC_{in}{+}AC_{in} \]

MUX / Decoder Sizing ☆

\[ \text{MUX: } 2^n \text{ inputs},\ n \text{ select lines} \qquad \text{Decoder: } n \text{ inputs} \to 2^n \text{ outputs} \]

Test your recall

Can you recall the full adder formula?

Reveal formula

\[ \text{Sum} = A \oplus B \oplus C_{in} \qquad C_{out} = AB{+}BC_{in}{+}AC_{in} \]

GATE traps 4 traps

A 2^n:1 MUX implements any n-variable function

A 2^n:1 MUX can implement ANY n-variable Boolean function directly -- tie each data input to that row of the truth table, no simplification needed. A fast trick when GATE asks for a MUX-based implementation.

Reducing MUX size needs a variable on the inputs

To implement an n-variable function with a MUX that has FEWER than n select lines (e.g. n-1), one variable must be fed to the data inputs themselves (as 0, 1, the variable, or its complement) instead of tied to a fixed constant -- a common 'reduce the MUX size' question.

Half adders don't cascade

A half adder has no carry-in and can't be cascaded for multi-bit addition -- only the FULL adder (with Cin) chains into a ripple-carry adder.

A decoder doubles as a de-multiplexer

A decoder doubles as a de-multiplexer by using its ENABLE line as the data input -- GATE sometimes tests this dual-use directly.

Sheet 4

Sequential Circuits

3 formulas

Core concepts

• Sequential circuit output depends on the current inputs AND the current state (memory via flip-flops)
• Mealy machine: output depends on current state AND input. Moore machine: output depends only on current state

Key formulas

Flip-Flop Next-State ☆

\[ SR{:}\ Q^+{=}S{+}R'Q \quad D{:}\ Q^+{=}D \quad JK{:}\ Q^+{=}JQ'{+}K'Q \quad T{:}\ Q^+{=}T\oplus Q \]

SR: S=R=1 is invalid

Flip-Flops for a mod-N Counter ☆

\[ \lceil \log_2 N \rceil \]

Maximum Clock Frequency ☆

\[ f_{max} = \frac{1}{T_{setup}+T_{propagation}+T_{skew}} \]

Test your recall

Can you recall the flip-flop next-state formula?

Reveal formula

\[ SR{:}\ Q^+{=}S{+}R'Q \quad D{:}\ Q^+{=}D \quad JK{:}\ Q^+{=}JQ'{+}K'Q \quad T{:}\ Q^+{=}T\oplus Q \]

GATE traps 5 traps

SR=1,1 is forbidden

SR flip-flop has a forbidden state at S=R=1 -- GATE tests whether you flag this as undefined rather than computing a next-state value blindly.

Round up for mod-N counters

A mod-N counter needs ceil(log2 N) flip-flops, not floor -- e.g. mod-6 needs 3 flip-flops since 2^2=4 is not enough.

Ripple counters are asynchronous

Ripple counters are ASYNCHRONOUS (each flip-flop is clocked by the previous one's output, not a common clock) -- this is why their propagation delay accumulates across stages, unlike synchronous counters. A frequently tested conceptual contrast.

JK toggles only at J=K=1

JK flip-flop toggles specifically when J=K=1 -- remembering this one case is usually enough to solve most JK sequence-tracing questions.

Moore machines trade a state for glitch-free output

A Moore machine can need one extra state compared to an equivalent Mealy machine, but its output is glitch-free (stable through a clock period) since it doesn't react to the input directly -- GATE often tests converting between the two and comparing state counts.