Formula sheet
Every formula from every topic. Type to filter.
🔢 Number Systems & Binary Arithmetic
Value in base r
N = Σ dᵢ · rⁱ (i negative for fraction digits)
Range of n bits (unsigned)
0 … 2ⁿ − 1
Range of n bits (2's complement)
−2ⁿ⁻¹ … +2ⁿ⁻¹ − 1
Range (sign-magnitude, 1's complement)
−(2ⁿ⁻¹ − 1) … +(2ⁿ⁻¹ − 1), two zeros
Negation in 2's complement
−x = (bitwise NOT x) + 1
Signed overflow
V = C_in(MSB) ⊕ C_out(MSB)
Gray code
g = b ⊕ (b >> 1); b = g ⊕ (g >> 1) ⊕ (g >> 2) ⊕ …
Bits for N values
⌈log₂ N⌉
🧮 Boolean Algebra, Canonical Forms & K-Maps
De Morgan
(A + B)′ = A′B′, (AB)′ = A′ + B′
Absorption / redundancy
A + AB = A; A + A′B = A + B; A(A′ + B) = AB
Consensus
AB + A′C + BC = AB + A′C
XOR identities
A⊕0 = A; A⊕1 = A′; A⊕A = 0; A⊕A′ = 1; A⊕B = AB′ + A′B
Minterms / maxterms
mᵢ′ = Mᵢ; Σm = 1; F = Σm(1-rows) = ΠM(0-rows)
Number of Boolean functions
2^(2ⁿ) (n variables)
Self-dual functions
2^(2ⁿ⁻¹)
K-map group of 2ᵏ cells
removes k variables, leaves a product of n − k literals
🔌 Combinational Circuits
Full adder
S = A⊕B⊕Cin; Cout = AB + Cin(A⊕B)
Half adder
S = A⊕B; C = AB
Half / full subtractor
D = A⊕B (⊕Bin); Bout = A′B (+ (A⊕B)′Bin)
Look-ahead carries
Gᵢ = AᵢBᵢ; Pᵢ = Aᵢ⊕Bᵢ; Cᵢ₊₁ = Gᵢ + PᵢCᵢ
MUX
F = Σ mᵢ·Iᵢ; 2ⁿ:1 MUX has n selects and handles n + 1 variables with data inputs 0, 1, X, X′
MUXes in a tree
2ⁿ:1 from 2:1 MUXes: 2ⁿ − 1
ROM size
2^(address bits) × (data bits)
Decoder
n inputs → 2ⁿ outputs; function of n variables = OR of its minterm outputs
🔁 Latches & Flip-Flops
SR
Q⁺ = S + R′Q (SR = 0)
JK
Q⁺ = JQ′ + K′Q
D
Q⁺ = D
T
Q⁺ = T⊕Q = TQ′ + T′Q
T from JK
J = K = T
D from JK
J = D, K = D′
JK from T
T = JQ′ + KQ
T from D
D = T ⊕ Q
⏱️ Counters, Registers & State Machines
Ripple counter modulus
n flip-flops → 2ⁿ states; Qᵢ has frequency f / 2ⁱ⁺¹
Flip-flops for N states
⌈log₂ N⌉
Ring counter
n flip-flops, n states (one-hot)
Johnson counter
n flip-flops, 2n states
T flip-flop binary up counter
T₀ = 1, T₁ = Q₀, T₂ = Q₁Q₀, Tᵢ = Q₀Q₁…Qᵢ₋₁
Ripple counter max clock
f_max ≈ 1 / (n · t_pd + t_decode)
Moore vs Mealy
Moore: output = f(state); Mealy: output = f(state, input)
⏳ Timing, Delay & Clock Frequency
Minimum clock period
T_min = t_clk→Q + t_comb(max) + t_setup (+ t_skew)
Maximum frequency
f_max = 1 / T_min
Hold condition
t_clk→Q + t_comb(min) ≥ t_hold (+ t_skew)
Ripple counter delay
n · t_pd (outputs settle only after all n stages)
Pipeline speed-up (k stages, balanced)
throughput up to k×, latency ≈ k · T