GATE Digital Electronics formula sheet

185 formulas in 7 topics, each with when to use it. Each is explained in the topic notes.

VALUE OF A POSITIONAL NUMBER

N = i = - m \sum n - 1 d_{i} r^{i}, 0 \leq d_{i} \leq r - 1

Here $n$ is the number of integer digits $d_{n - 1} \dots d_{0}$ and $m$ the number of fraction digits $d_{- 1} \dots d_{- m}$ . Every digit must be smaller than the base.

RANGE OF AN N-DIGIT UNSIGNED INTEGER; DIGITS NEEDED

0 \leq N \leq r^{n} - 1, n_{m i n} = ⌈ lo g_{r} (N + 1) ⌉ (N \geq 1)

An $n$ -digit base- $r$ integer takes $r^{n}$ distinct values. In bits, $n_{m i n} = ⌈ lo g_{2} (N + 1)⌉$ . For example, 256 needs 9 bits because $2^{8} - 1 = 255$ . The formula needs $N \geq 1$ ; the value 0 still takes one digit.

Boolean algebra, logic gates and minimisation

All 20 formulas

BASIC LAWS

A + 0 A + 1 A + A A + \overline{A} \overline{\overline{A}} = A, = 1, = A, = 1, = A A \cdot 1 A \cdot 0 A \cdot A A \cdot \overline{A} = A = 0 = A = 0

Identity, null (dominance), idempotent, complement and involution laws; each left-hand law is the dual of the one beside it.

DISTRIBUTIVE LAWS

A (B + C) = A B + A C, A + B C = (A + B) (A + C)

The second one (OR over AND) has no counterpart in ordinary algebra; it is the step that turns an SOP into a POS.

Logic families and CMOS logic gates

All 15 formulas

HIGH-LEVEL NOISE MARGIN

N M_{H} = V_{O H} - V_{I H}

Uses worst-case values: the minimum $V_{O H}$ and the minimum $V_{I H}$ .

LOW-LEVEL NOISE MARGIN

N M_{L} = V_{I L} - V_{O L}

Uses worst-case values: the maximum $V_{I L}$ and the maximum $V_{O L}$ . The family's noise margin is the smaller of $N M_{H}$ and $N M_{L}$ .

Combinational circuits: arithmetic circuits, multiplexers, decoders, code converters

All 32 formulas

HALF ADDER

S = A \oplus B, C = A B

Adds two 1-bit inputs and has no carry-in. A full adder with $C_{in} = 0$ reduces to this.

FULL ADDER

S = A \oplus B \oplus C_{in}, C_{o u t} = A B + B C_{in} + A C_{in} = A B + C_{in} (A \oplus B)

$S$ is 1 when an odd number of the three inputs are 1. $C_{o u t}$ is the 3-input majority function. Use the second form of $C_{o u t}$ when the adder is built from two half adders.

Sequential circuits: flip-flops, counters, shift registers, state machines and timing

All 18 formulas

CONDITION TO AVOID RACE-AROUND

t_{p} < t_{p d} < T

$t_{p}$ = width of the HIGH clock pulse, $t_{p d}$ = flip-flop propagation delay, $T$ = clock period. Applies to a level-triggered JK flip-flop in toggle mode ( $J = K = 1$ ).

SR FLIP-FLOP

Q_{n + 1} = S + \overline{R} Q_{n}, S R = 0

The constraint $S R = 0$ is part of the equation, because $S = R = 1$ is not allowed. $S R = 00$ holds, $10$ sets, $01$ resets.

Sample-and-hold, ADCs and DACs

All 43 formulas

DECIMAL VALUE OF A CODE

D = k = 0 \sum n - 1 b_{k} 2^{k}, 0 \leq D \leq 2^{n} - 1

Straight binary. The MSB $b_{n - 1}$ has weight $2^{n - 1}$ and the LSB $b_{0}$ has weight 1.

STEP SIZE (RESOLUTION IN VOLTS)

Δ = \frac{V _{F S}}{2 ^{n}}

Convention used in these notes: $V_{F S}$ is the full-scale range, i.e. the reference span. For a bipolar range $- V_{R}$ to $+ V_{R}$ , $V_{F S} = 2 V_{R}$ .

Memories, computer organisation, microprocessors and embedded systems

All 38 formulas

ROM AS A COMBINATIONAL CIRCUIT

ROM size = 2^{n} \times m bits

A ROM with n address inputs and m data outputs stores a complete truth table, so it implements any m Boolean functions of the same n variables: each address is one input combination and each word holds the m outputs for it. Example: a squarer for a 4-bit unsigned input (largest output $1 5^{2} = 225$ , which needs 8 bits) needs a $16 \times 8$ ROM, 128 bits.

DRAM DISTRIBUTED-REFRESH INTERVAL

t_{row} = \frac{T _{ref}}{R}

R = number of rows (one refresh operation per row); $T_{ref}$ = period within which every row must be refreshed. Spread evenly, one row is refreshed every $t_{row}$ .