A number system is a way to write numbers. Each system has a base (also called radix). The base tells how many symbols the system uses.

• Decimal — base 10. Symbols: 0–9. This is our normal system.
• Binary — base 2. Symbols: 0 and 1. Computers use this.
• Octal — base 8. Symbols: 0–7.
• Hexadecimal (hex) — base 16. Symbols: 0–9 and A–F (A=10, B=11, C=12, D=13, E=14, F=15).

Each digit has a place value. In base r, the place values are powers of r: ... r³, r², r¹, r⁰ before the point, and r⁻¹, r⁻² after the point.

For the whole part: divide by 2 again and again. Keep the remainders. Read the remainders from bottom to top.

For the fraction part: multiply by 2 again and again. Keep the whole-number digit each time. Read from top to bottom.

Octal and hex are just "packed" binary. This makes conversion very fast:

• Binary → octal: group bits in 3s from the point. Each group is one octal digit.
• Binary → hex: group bits in 4s from the point. Each group is one hex digit.
• Going the other way, expand each digit into 3 or 4 bits.

Addition rules: 0+0=0, 0+1=1, 1+0=1, 1+1=10 (write 0, carry 1), 1+1+1=11 (write 1, carry 1).

Subtraction rules: 0−0=0, 1−0=1, 1−1=0, 0−1=1 with a borrow of 1 from the next column.

Complements let us do subtraction using only addition. That is why hardware loves them.

• 1's complement: flip every bit. Example: 1's complement of 0101 is 1010.
• 2's complement: 1's complement + 1. Example: 2's complement of 0101 is 1011.

Subtraction rule (A − B): take the 2's complement of B and add it to A.

• If there is a final carry, discard it. The answer is positive.
• If there is no carry, the answer is negative. Take the 2's complement of the result to get the magnitude.

With n bits, we can represent signed numbers in three ways. 2's complement is the winner because it has one zero and simple hardware.

BCD (Binary Coded Decimal, 8421 code): each decimal digit is written as its own 4-bit binary. Example: 59 = 0101 1001 in BCD. Note: this is different from pure binary (59 = 111011). Codes 1010–1111 are invalid in BCD. In BCD addition, if a digit sum is more than 9, add 6 (0110) to correct it.

Gray code: only one bit changes between two consecutive numbers. This avoids glitches in position sensors and helps in K-maps.

• Binary → Gray: keep the MSB. Then each Gray bit = current binary bit XOR previous binary bit.
• Gray → Binary: keep the MSB. Then each binary bit = previous binary bit XOR current Gray bit.

ASCII: a 7-bit code for characters. 'A' = 65 (41 in hex), 'a' = 97 (61 in hex), '0' = 48 (30 in hex).

Boolean algebra works with only two values: 0 (false) and 1 (true). A logic gate is a small circuit that does one Boolean operation. We write NOT A as A′ (or \(\overline{A}\)), A AND B as A·B (or just AB), and A OR B as A+B.

Quick memory helpers: AND = 1 only when all inputs are 1. OR = 1 when any input is 1. XOR = 1 when the inputs are different. XNOR = 1 when the inputs are equal. NOT A means the opposite of A.

De Morgan's theorems: (A·B)′ = A′ + B′ and (A+B)′ = A′·B′. In words: break the bar, change the operator. The truth table below proves both — matching columns are shaded.

The yellow pair matches row by row, and the green pair matches row by row. So both theorems are proved. ✓

NAND and NOR are called universal gates because any Boolean function can be built using only NAND (or only NOR). This is a BUET favorite. Here is how to build the basic gates from NAND:

• NOT from NAND: join both inputs. NAND(A, A) = (A·A)′ = A′.
• AND from NAND: NAND, then NOT. ((AB)′)′ = AB. Needs 2 NAND gates.
• OR from NAND: invert both inputs first, then NAND. (A′·B′)′ = A + B (De Morgan). Needs 3 NAND gates.
• NOR from NAND: OR then NOT → 4 NAND gates.
• XOR from NAND: needs 4 NAND gates (a classic exam question).

A minterm (mᵢ) is an AND term that uses every variable once. It is 1 for exactly one input row. A maxterm (Mᵢ) is an OR term that uses every variable once. It is 0 for exactly one row.

• SOP (Sum of Products): OR of AND terms. Example: F = A′BC + AB′.
• POS (Product of Sums): AND of OR terms. Example: F = (A+B)(A′+C).
• Canonical SOP: F = Σm(list of rows where F = 1). Canonical POS: F = ΠM(rows where F = 0).
• Same function: the minterm list and maxterm list together cover all 2ⁿ rows. Example (3 variables): F = Σm(1,3,5,7) = ΠM(0,2,4,6).

A K-map is a grid form of a truth table. Cells that are next to each other differ in only one variable (Gray code order). So when two neighboring cells are both 1, that variable can be dropped. This makes simplification visual and fast.

Grouping rules:

• Groups must be rectangles of size 1, 2, 4, 8, or 16 — always a power of 2.
• The map wraps around: the left edge touches the right edge, and the top touches the bottom. Corners are neighbors too.
• Make groups as large as possible, and use as few groups as possible.
• Every 1 must be inside at least one group. Groups may overlap.
• A group of 2 removes 1 variable, a group of 4 removes 2, a group of 8 removes 3.

A group that cannot be made bigger is a prime implicant. If some 1 is covered by only one prime implicant, that group is an essential prime implicant — it must appear in the answer.

A don't-care (written X or d) is an input that never happens, or whose output we do not care about. We may count an X as 1 if it helps make a bigger group, otherwise we treat it as 0.

A combinational circuit has no memory. Its output depends only on the current inputs. Adders, multiplexers, decoders, encoders and comparators are all combinational.

A half adder adds two 1-bit numbers A and B. It gives a Sum and a Carry.

A full adder adds three bits: A, B, and a carry-in (Cin). It is the building block of real adders.

A full adder = two half adders + one OR gate. The first half adder adds A and B. The second adds that sum with Cin. The OR combines the two carries.

To add two 4-bit numbers, chain four full adders. The carry-out of each stage goes to the carry-in of the next stage. The carry "ripples" from right to left — so the last sum bit must wait for all earlier carries. This makes the ripple carry adder simple but slow. (Faster designs use carry look-ahead.)

A half subtractor computes A − B: a Difference and a Borrow. A full subtractor also takes a borrow-in (Bin).

A multiplexer is a data selector. A 4:1 MUX has 4 data inputs (I₀–I₃), 2 select lines (S₁S₀), and 1 output. The select lines choose which input reaches the output.

A 2ⁿ:1 MUX needs n select lines. General rule: a function of n variables can be built with a 2ⁿ⁻¹:1 MUX — put n−1 variables on the select lines, and feed each input with 0, 1, the last variable, or its complement.

A demultiplexer is the opposite of a MUX: 1 data input, n select lines, 2ⁿ outputs. The select lines choose which output receives the input. A 1:4 DEMUX: Y₀ = S₁′S₀′D, Y₁ = S₁′S₀D, Y₂ = S₁S₀′D, Y₃ = S₁S₀D. A DEMUX is really a decoder with an enable input used as the data line.

An n-to-2ⁿ decoder turns on exactly one of its 2ⁿ outputs — the one whose number matches the input. A 3:8 decoder gives all 8 minterms of the 3 inputs: output Dᵢ = mᵢ.

Implementing functions: since a decoder produces every minterm, any function = OR of the right decoder outputs. One decoder + a few OR gates can build several functions at once.

An encoder is the opposite of a decoder: 2ⁿ inputs, n outputs. It outputs the binary number of the active input. Problem: what if two inputs are active at once? A priority encoder fixes this — the highest-numbered active input wins. It also has a valid bit (V) that is 1 when at least one input is active.

A comparator compares two numbers. For 1-bit inputs A and B:

• A > B when A=1, B=0 → output AB′
• A = B when bits match → output XNOR: (A⊕B)′
• A < B when A=0, B=1 → output A′B

Multi-bit comparators compare from the MSB down: the first different bit decides.

Sometimes the exam gives you only a truth table and asks: "which circuit is this?" Do not panic — run this simple checklist:

• Count inputs and outputs first. This alone removes most wrong guesses. n inputs and 2ⁿ outputs → think decoder. Many data inputs plus select lines and 1 output → think MUX. 2 or 3 inputs with 2 outputs → think adder family.
• Two outputs, one looks like XOR and one looks like "majority"? That pair is Sum + Carry → it is an adder (half adder for 2 inputs, full adder for 3).
• Exactly one output is 1 in every row (one-hot)? → decoder (or demultiplexer).
• The output just copies one chosen input, picked by the select lines? → multiplexer.
• One output that is 1 when the count of 1s is odd (a pure XOR column)? → parity generator/checker. Output 1 only when the inputs are equal → comparator (XNOR).

A sequential circuit has memory. Its output depends on the inputs and the current state. The basic memory elements are latches and flip-flops — each stores 1 bit.

• Latch: level-sensitive. While the enable/clock is high, the output follows the inputs the whole time.
• Flip-flop: edge-triggered. The output can change only at a clock edge (rising ↑ or falling ↓). The rest of the time it holds its value.

Notation: Q = present state, Q⁺ (or Q(t+1)) = next state.

Two cross-coupled NOR gates make an SR latch. S = set (make Q = 1), R = reset (make Q = 0).

S = R = 1 is forbidden: both outputs go 0 (they should be complements), and when S, R return to 0 the final state is unpredictable — it becomes a race.

A clocked SR flip-flop adds a clock: S and R work only when the clock allows. It still has the invalid S=R=1 problem.

A D flip-flop fixes the invalid state: it has one input D, and R is just D′ inside. At the clock edge, Q simply copies D. Characteristic equation: Q⁺ = D. It is the standard 1-bit storage cell.

A JK flip-flop is an SR where J=K=1 is allowed and means toggle (Q flips). Characteristic equation: Q⁺ = JQ′ + K′Q.

A T flip-flop has one input T: T=0 holds, T=1 toggles. Characteristic equation: Q⁺ = T ⊕ Q. Make one by tying J = K = T. Toggling divides the clock frequency by 2, so T flip-flops build counters.

A characteristic table answers: "given the inputs, what is Q⁺?" An excitation table answers the reverse design question: "I want to go from Q to Q⁺ — what inputs do I need?"

Race-around: in a level-triggered JK flip-flop with J = K = 1, the output toggles once, but the clock is still high — so it toggles again, and again, many times in one clock pulse. The final value is unpredictable.

It happens when the clock pulse width is much longer than the propagation delay of the flip-flop.

Fixes:

• Master-slave JK: two latches in series. The master reads the inputs while the clock is high; the slave copies the master when the clock goes low. The output changes only once per clock pulse.
• Edge-triggered JK: respond only to the narrow moment of the clock edge (the modern fix).

Other useful conversions (same method): JK → T: tie J = K = T. D → T: D = T ⊕ Q. T → D: T = D ⊕ Q.

Here is a trick every D flip-flop hides: connect D = Q′ (feed the inverted output back to the input). Now at every active clock edge, Q copies its own opposite — so Q toggles on every edge.

Think about what toggling means for frequency. The input clock makes one full cycle per period. But Q needs two clock edges (one to go high, one to go low) to finish one of its own cycles. So:

The October 2017 question: convert a 100 MHz clock to 50 MHz and 25 MHz using only D flip-flops.

1. FF1: clock it with the 100 MHz input, tie D₁ = Q₁′. Q₁ toggles every edge → Q₁ is a clean 50 MHz square wave.
2. FF2: use Q₁ as the clock of FF2, tie D₂ = Q₂′. Q₂ toggles on every edge of Q₁ → Q₂ is 25 MHz.

That is the whole answer: two D flip-flops in series, each with its own Q′ wired back to its D. Take 50 MHz from Q₁ and 25 MHz from Q₂. Each stage also outputs a perfect 50% duty cycle — a bonus you can mention.

Follow the toggles edge by edge (FF1 clocked by CLK rising edges, FF2 clocked by Q₁ rising edges):

Read the table: Q₁ completes one cycle every 2 CLK periods (half frequency), and Q₂ toggles only when Q₁ rises (edges 1, 3, 5, 7) — one cycle every 4 CLK periods, a quarter of the frequency. ✓

A ripple counter uses T (or JK with J=K=1) flip-flops in a chain. Only the first flip-flop gets the clock. Each next flip-flop is clocked by the output of the previous one. Each stage divides the frequency by 2.

Look at the waveform below for a 3-bit ripple counter (negative-edge triggered):

• Q₀ toggles on every falling edge of CLK → half the frequency.
• Q₁ toggles on every falling edge of Q₀ → one quarter.
• Q₂ toggles on every falling edge of Q₁ → one eighth.
• Reading Q₂Q₁Q₀ gives 000, 001, 010, … 111, 000 — it counts 0 to 7 (mod-8).

Mod-N with reset: to make a mod-6 counter from a mod-8 ripple counter, detect the count 6 (110) with a NAND on Q₂ and Q₁, and use its output to clear all flip-flops. The counter then runs 0–5.

Drawback: the clock ripples through the chain, so delays add up: total delay = n × t_pd. At high speed, the outputs can be read while still changing — glitches.

In a synchronous counter every flip-flop gets the same clock. Logic gates decide which ones toggle. No ripple delay.

Design a mod-8 (3-bit) up counter with JK flip-flops.

Step 1: write the state sequence: 000 → 001 → 010 → 011 → 100 → 101 → 110 → 111 → 000.

Step 2: build the excitation table. For each bit, compare Q with Q⁺ and use the JK excitation table (0→0: J=0,K=X; 0→1: J=1,K=X; 1→0: J=X,K=1; 1→1: J=X,K=0):

Step 3: simplify each input with a K-map (variables Q₂, Q₁, Q₀):

• J₀ and K₀ are 1 or X in every row → J₀ = K₀ = 1 (bit 0 always toggles).
• J₁ is 1 exactly when Q₀ = 1 (rows 001, 101), X elsewhere possible → J₁ = K₁ = Q₀.
• J₂ is 1 at 011, X at 1xx → group gives J₂ = K₂ = Q₁Q₀.

Step 4: circuit — three JK flip-flops on one clock; J₀=K₀=1; J₁=K₁=Q₀; J₂=K₂ = AND of Q₁, Q₀.

Pattern to remember: for a binary up counter, each bit toggles when all lower bits are 1. So Jₙ = Kₙ = Q₀Q₁…Qₙ₋₁.

A down counter counts 111 → 110 → … → 000. Rule: a bit toggles when all lower bits are 0 (use Q′ outputs: Jₙ = Kₙ = Q₀′Q₁′…). An up/down counter has a mode input M: M=0 count up (use Q's), M=1 count down (use Q′'s), mixed with AND-OR logic.

A register is a row of flip-flops that stores an n-bit word. A shift register moves its bits one place on every clock. Four types, named by how data goes in and out:

Uses: serial data transfer (UART), multiplication/division by 2 (shift left/right), delay lines.

Ring counter: a shift register whose last output feeds back to the first input. Load one 1, and it circulates: 1000 → 0100 → 0010 → 0001 → 1000. With n flip-flops it has n states (mod-n).

Johnson (twisted ring) counter: feed back the complement of the last output. With n flip-flops it has 2n states. For n = 4: 0000 → 1000 → 1100 → 1110 → 1111 → 0111 → 0011 → 0001 → 0000 (8 states).

Design steps (same every time — memorize the flow):

1. Understand the problem → draw the state diagram.
2. Write the state table (present state, input → next state, output).
3. State assignment: give each state a binary code. n states need ⌈log₂n⌉ flip-flops.
4. Pick a flip-flop type; use its excitation table to find each flip-flop input.
5. Simplify the input and output equations with K-maps (unused states = don't-cares).
6. Draw the circuit.

Problem: a circuit reads one bit x per clock. Output y = 1 when the last three bits seen are 1, 0, 1. Overlap allowed (in 10101, "101" appears twice).

Step 1 — states (each state remembers useful progress):

• S0: no useful progress yet.
• S1: last bit was 1 (we have "1").
• S2: we have "10".

Transitions: from S2, input 1 completes "101" → output 1, and that final 1 can start a new pattern, so go to S1.

Step 2 — state table, and Step 3 — assignment: S0 = 00, S1 = 01, S2 = 10 (two D flip-flops A, B; state = AB). The combination 11 is unused → don't-care.

(For D flip-flops, D = next state bit, so the last two columns just copy A⁺ and B⁺.)

Step 4 & 5 — equations by K-map (variables A, B, x; cells 110 and 111 are don't-cares):

• D_A = 1 only at A′Bx′ (row 010). Grouping with don't-care 110 → D_A = Bx′.
• D_B = 1 at 001, 011, 101. Grouping with don't-care 111 → all cells with x = 1 → D_B = x.
• y = 1 at 101. Grouping with don't-care 111 → y = Ax.

Step 6 — circuit: D_A needs one AND (B, x′), D_B is just the input x, and y needs one AND (A, x). Two D flip-flops + two AND gates + one NOT. Done!

Sanity check with input 1, 0, 1: start 00 →(x=1) 01 →(x=0) 10 →(x=1) y = A·x = 1 ✓ and next state 01, ready for overlap. ✓