Homework: Exercise 5

Theory: How to Approach These

Decoder / mux sizes (4.4): decoder $n$ inputs → $2^n$ outputs; mux with $2^s$ data inputs needs $s$ select lines.
Analysing a sequential circuit (4.5): write an input equation for every flip-flop input from the wiring, then evaluate it row by row using present values only.
Flip-flop rules: JK: 00 hold, 01 reset, 10 set, 11 toggle. D: $Q^+ = D$ .
Converting a flip-flop: new characteristic table → old flip-flop’s excitation table → K-maps → gates.

Jump to: Q1 · Q2 · Q3 · Q4 · Q5

Homework Solutions

Exercise Q1

How many inputs does a decoder have if it has 64 outputs?

Part	Detail
Asks	Find the number of inputs $n$ of a decoder with 64 outputs.
Needs	$n$ inputs give $2^n$ outputs, so $n = \log_2(\text{outputs})$ .
Look at	64 is a power of 2, so no rounding is needed.
If it changes	Not a power of 2 (e.g. 10 outputs): round up, $2^4 = 16 \ge 10$ so 4 inputs.

Show solution ↓

Solution

How to solve

A decoder activates one output per input pattern, so outputs $= 2^n$ .
Solve $2^n = 64$ with a logarithm.

Known	Rule	$n = \log_2(\ldots)$	Check

Sample answer

2^n = 64 \;\Rightarrow\; n = \log_2 64 = 6.

The decoder has 6 inputs (a 6-to-64 decoder). Check: $2^6 = 64$ ✓.

Watch out: the count is the number of inputs, not outputs, and a non-power of 2 must be rounded up.

Exercise Q2

How many control lines does a multiplexer have if it has 32 inputs?

Part	Detail
Asks	Find the number of select (control) lines for 32 data inputs.
Needs	$s$ select lines choose one of $2^s$ inputs, so $s = \log_2(\text{inputs})$ .
Look at	“Inputs” means the data inputs; select lines are not counted.
If it changes	Only the number changes; non-powers of 2 round up.

Show solution ↓

Solution

How to solve

Each select-line pattern picks one data input, so inputs $= 2^s$ .
Solve $2^s = 32$ .

Sample answer

s = \log_2 32 = 5.

The multiplexer has 5 control lines. Check: $2^5 = 32$ ✓.

Watch out: do not count the select lines among the 32 inputs.

Exercise Q3

Analyze the following sequential circuit by determining the truth table.

Present State		Input	Next State
A	B	X	A	B
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Part	Detail
Asks	For each of the 8 rows $(A, B, X)$ , find $A^+$ and $B^+$ after the next clock pulse.
Needs	JK: 00 hold, 01 reset, 10 set, 11 toggle. D: $Q^+ = D$ . Use present values.
Look at	NOR gets $X$ and $A$ and drives both $J$ and $K$ ; AND gets $A$ and $Q'$ of the D flip-flop ( $B'$ ).
If it changes	Only the input equations change; the row-by-row method stays.

Show solution ↓

Solution

How to solve

Name the parts: $A$ is the JK flip-flop, $B$ the D flip-flop, $X$ the input.
Write the input equations from the wires (below).
Since $J_A = K_A$ , $A$ toggles when $(A+X)' = 1$ and holds otherwise.
Per row: compute $A + X$ , then $J = K$ , then the JK action gives next $A$ ; compute $B'$ , then $D_B$ , which is next $B$ .
Fill the two Next State columns; the working goes in the extra columns on the right.

Sample answer

From the wiring:

J_A = K_A = (A + X)', \qquad D_B = A \cdot B'

Present State		Input	Next State		Working
A	B	X	A	B	$A + X$	$J_A = K_A$	JK action	$B'$	$D_B = AB'$
0	0	0	1	0	0	1	toggle	1	0
0	0	1	0	0	1	0	hold	1	0
0	1	0	1	0	0	1	toggle	0	0
0	1	1	0	0	1	0	hold	0	0
1	0	0	1	1	1	0	hold	1	1
1	0	1	1	1	1	0	hold	1	1
1	1	0	1	0	1	0	hold	0	0
1	1	1	1	0	1	0	hold	0	0

Final table (rows $ABX$ = 000 → 111): Next $A$ = 1, 0, 1, 0, 1, 1, 1, 1 and Next $B$ = 0, 0, 0, 0, 1, 1, 0, 0.

Behaviour: once $A = 1$ it stays 1 and $B$ alternates ( $B^+ = B'$ when $A=1$ ). From $A = 0$ , $X = 0$ sets $A$ to 1 and $X = 1$ keeps it 0.

Watch out: never use the new $A$ to compute $B^+$ ; every right-hand side uses present values. Take $B'$ from the D flip-flop’s $Q'$ output.

Exercise Q4

Complete the truth table for the following sequential circuit:

Input		Present	Next state
X	Y	A	A	B
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Part	Detail
Asks	Find $A^+$ and $B^+$ for every $(X, Y, A)$ .
Needs	JK rule, D rule, XOR (1 when inputs differ).
Look at	$X \to J$ , $Y \to K$ ; $Y$ also goes through an inverter into the XOR with $A$ ; XOR drives $D$ . Present $B$ is unused.
If it changes	Column order here is $X, Y, A$ ; copy the order of the table you are given.

Show solution ↓

Solution

How to solve

Write the equations: $J_A = X$ , $K_A = Y$ , $D_B = A \oplus Y'$ .
$A^+$ : read $XY$ as $JK$ (00 hold, 01 reset, 10 set, 11 toggle).
$B^+$ : compute $Y'$ , then $A \oplus Y'$ using the present $A$ .
Fill the two Next state columns; the working goes in the extra columns on the right.

Sample answer

From the wiring:

J_A = X, \qquad K_A = Y, \qquad D_B = A \oplus Y'

Input		Present	Next state		Working
X	Y	A	A	B	JK action	$Y'$	$D_B = A \oplus Y'$
0	0	0	0	1	00 hold	1	$0 \oplus 1 = 1$
0	0	1	1	0	00 hold	1	$1 \oplus 1 = 0$
0	1	0	0	0	01 reset	0	$0 \oplus 0 = 0$
0	1	1	0	1	01 reset	0	$1 \oplus 0 = 1$
1	0	0	1	1	10 set	1	$0 \oplus 1 = 1$
1	0	1	1	0	10 set	1	$1 \oplus 1 = 0$
1	1	0	1	0	11 toggle	0	$0 \oplus 0 = 0$
1	1	1	0	1	11 toggle	0	$1 \oplus 0 = 1$

Result (rows $XYA$ = 000 → 111): Next $A$ = 0, 1, 0, 0, 1, 1, 1, 0 and Next $B$ = 1, 0, 0, 1, 1, 0, 0, 1.

Check: $B^+ = A'$ when $Y = 0$ and $B^+ = A$ when $Y = 1$ ✓.

Watch out: the XOR uses $Y'$ , not $Y$ , and the old $A$ , not $A^+$ .

Exercise Q5

A Mux-Not flip-flop (MN flip-flop) behaves as follows: If M = 1, the flip-flop complements the current state. If M = 0, the next state of the flip-flop is equal to the value of N.

a) Derive the characteristic table for the flip-flop.

b) Show how a JK flip-flop can be converted to a MN flip-flop by adding gate(s) and inverter(s).

Part	Detail
Asks	(a) Table of $Q(t+1)$ for every $M, N$ . (b) The $J$ , $K$ logic that makes a JK flip-flop act like it.
Needs	JK excitation table (change → $J,K$ ) and K-maps with don’t-cares.
Look at	$M = 1$ : toggle ( $Q'$ ). $M = 0$ : copy $N$ .
If it changes	Any conversion: new table → old excitation table → K-map per input → gates.

Show solution ↓

Solution

How to solve

Build the table of the new flip-flop with $Q$ and $Q^+$ (8 rows).
For each row, write the $J, K$ that cause $Q \to Q^+$ : 0→0: $J=0, K=d$ ; 0→1: $J=1, K=d$ ; 1→0: $J=d, K=1$ ; 1→1: $J=d, K=0$ .
K-map each of $J$ and $K$ (rows $M$ , columns $NQ$ ) and use the $d$ ‘s to enlarge groups.
Draw the gates in front of the JK flip-flop and verify with $Q^+ = JQ' + K'Q$ .

$M$	$N$	$Q$
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Sample answer

(a) Characteristic table

$M$	$N$	$Q(t+1)$
0	0	0
0	1	1
1	0	$Q(t)'$
1	1	$Q(t)'$

Equation: $Q^+ = M'N + MQ'$ .

(b) Conversion

$M$	$N$	$Q$	$Q^+$	$J$	$K$
0	0	0	0	0	d
0	0	1	0	d	1
0	1	0	1	1	d
0	1	1	1	d	0
1	0	0	1	1	d
1	0	1	0	d	1
1	1	0	1	1	d
1	1	1	0	d	1

$J$ (rows $M$ , columns $NQ$ ):

$M \backslash NQ$	00	01	11	10
0	0	d	d	1
1	1	d	d	1

Bottom row gives $M$ , columns 11–10 give $N$ : $J = M + N$ .

$K$ :

$M \backslash NQ$	00	01	11	10
0	d	1	0	d
1	d	1	1	d

Bottom row gives $M$ , columns 00–01 give $N'$ : $K = M + N'$ .

J = M + N, \qquad K = M + N'

Verify: $Q^+ = (M+N)Q' + M'NQ$ . For $M = 1$ : $Q^+ = Q'$ (toggle) ✓. For $M = 0$ : $Q^+ = N(Q' + Q) = N$ ✓.

Watch out: use the excitation table (change → inputs), not the characteristic table, and use a $d$ only when it enlarges a group.