Digital Logic (old course)

A MOD-12 counter counts 0 to 11 and then returns to 0. The number of flip-flops needed is $n$ with $2^n \ge 12$, so $n = 4$ ($2^3 = 8 < 12 \le 16$).

Design: Use four negative-edge triggered J-K flip-flops with $J = K = 1$ (toggle mode). Connect them as an asynchronous (ripple) counter: the external clock drives FF0, and each $Q$ drives the clock of the next flip-flop.

The counter would run 0 to 15, so it is forced back to 0 when the count 12 ($1100$, $Q_3 = Q_2 = 1$) appears. A NAND gate with inputs $Q_3$ and $Q_2$ drives the active-low asynchronous CLEAR inputs of all flip-flops.

CLK --> [FF0] Q0 --> [FF1] Q1 --> [FF2] Q2 --> [FF3] Q3
         J=K=1        J=K=1        J=K=1        J=K=1
          ^CLR          ^CLR         ^CLR         ^CLR
          |             |            |            |
          +-------------+------+-----+------------+
                                |
                         NAND(Q3, Q2)
                           ^      ^
                           Q3     Q2

Count sequence:

The state 1100 lasts only for a very short time, so the counter effectively goes through 12 states. The output frequency at $Q_3$ is $f/12$ (not exactly 50% duty cycle).

Number of flip-flops $n$: $2^n \ge 88$. Since $2^6 = 64 < 88 \le 128 = 2^7$, $n = 7$.

Design: Use seven negative-edge triggered J-K flip-flops with $J = K = 1$, connected as a ripple counter: the clock drives FF0, and each $Q_i$ drives the clock of the next flip-flop. The counter would count 0 to 127, so it must be cleared when the count reaches 88.

Decimal 88 in binary:

$88 = 64 + 16 + 8 = 1011000_2 \quad (Q_6Q_5Q_4Q_3Q_2Q_1Q_0)$

The flip-flops at 1 are $Q_6, Q_4, Q_3$. A 3-input NAND gate with inputs $Q_6, Q_4, Q_3$ drives the active-low CLEAR of all seven flip-flops. No smaller count has all three of these outputs at 1 (the first such count is 88 itself), so the counter is cleared exactly at 88.

CLK --> [FF0]-->[FF1]-->[FF2]-->[FF3]-->[FF4]-->[FF5]-->[FF6]
         J=K=1 each                Q3          Q4            Q6
                                    \           |           /
                                     +-- NAND(Q6, Q4, Q3) --+---> to CLR of all FFs

The counter counts 0 to 87 (88 states) and 88 appears only momentarily before the reset. The output frequency is $f/88$.

A MOD-3 counter counts $0,1,2$ and then returns to $0$.

Number of flip-flops: $2^n \ge 3$ gives $n = 2$. Use two JK (or T) flip-flops with $J=K=1$ so each toggles.

Connections (asynchronous / ripple):

• The external clock drives FF0 (output $Q_0$).
• $Q_0$ drives the clock of FF1 (output $Q_1$).
• A 2-input NAND gate takes $Q_1$ and $Q_0$ and its output goes to the active-low CLEAR inputs of both flip-flops.

Operation:

When the count reaches $11$ (decimal 3), the NAND output goes low and clears both flip-flops almost immediately. The state $11$ lasts only for a very short time, so the stable states are $00 \to 01 \to 10 \to 00$, i.e. MOD-3. The output frequency is $f/3$.

Number of flip-flops: $2^8 = 256 < 440 \le 2^9 = 512$, so 9 flip-flops ($Q_8$ to $Q_0$) are needed.

Design: use 9 JK flip-flops with $J=K=1$ (toggle mode), connected as a ripple counter. The clock goes to FF0, and each $Q_n$ clocks the next flip-flop.

Reset decoding: the counter must return to 0 when the count reaches $440$.

$440 = 256+128+32+16+8 = 110111000_2$

so $Q_8=1, Q_7=1, Q_6=0, Q_5=1, Q_4=1, Q_3=1, Q_2=Q_1=Q_0=0$.

Only the 1s are decoded. The first time all of $Q_8, Q_7, Q_5, Q_4, Q_3$ are 1 is exactly at count 440 (smaller counts do not set all of these bits). Feed these five outputs to a 5-input NAND gate. Its output goes to the active-low CLEAR (reset) inputs of all nine flip-flops.

Operation: the counter counts $0$ to $439$. At count 440 the NAND output goes low and resets all flip-flops, so 440 is a very brief transient state and the stable cycle has 440 states ($0$ to $439$): MOD-440. The output frequency is $f/440$.

Number of flip-flops: $2^7 = 128 < 156 \le 2^8 = 256$, so 8 flip-flops ($Q_7$ to $Q_0$) are needed.

Design: 8 JK flip-flops with $J=K=1$ (toggle) connected as a ripple counter: the external clock feeds FF0 and each $Q_n$ clocks the next flip-flop.

Reset decoding:

$156 = 128+16+8+4 = 10011100_2$

So $Q_7=1, Q_4=1, Q_3=1, Q_2=1$, and the others are 0. The first count that makes $Q_7, Q_4, Q_3, Q_2$ all 1 is exactly 156. Connect these four outputs to a 4-input NAND gate. The NAND output goes to the active-low CLEAR inputs of all eight flip-flops.

Operation: the counter counts $0,1,\dots,155$. When it reaches 156, the NAND output goes low and clears all flip-flops to 00000000 immediately, so 156 appears only momentarily. The counter therefore has 156 stable states: MOD-156, and the output frequency is $f/156$.

A MOD-33 counter counts $0$ to $32$ and then resets, giving 33 states. The number of flip-flops $n$ must satisfy $2^n\ge33$, so $n=6$ ($2^5=32<33<64$).

Design.

1. Use six negative-edge triggered JK flip-flops (or T flip-flops) with $J=K=1$, so each toggles on every falling clock edge at its clock input.
2. Connect the external clock to FF0, and $Q_0\to$ clock of FF1, $Q_1\to$ clock of FF2, and so on up to FF5. This is a ripple (asynchronous) counter, counting up in binary.
3. The natural count goes $0,1,\dots,32$ ($100000_2$). The counter must reset on the next state, 33 = $100001_2$. This is the first state in which $Q_5=1$ and $Q_0=1$ at the same time, so the decode is unique.
4. Connect a 2-input NAND gate to $Q_5$ and $Q_0$. Its output goes to the active-low asynchronous CLEAR inputs of all six flip-flops.

Operation. When the count reaches 33 the NAND output goes low and immediately clears all flip-flops to 000000. The state 33 therefore lasts only a very short time (a glitch), and the stable states are $0$ to $32$, which is exactly 33 states.

The output frequency at $Q_5$ is not exactly $f/33$ because the state 33 is only a transient, but the counter has modulus 33.

A MOD-33 counter has 33 states ($0$ to $32$), so $n$ flip-flops with $2^n\ge33$ are needed: $n=6$.

Design

1. Six negative-edge triggered JK flip-flops with $J=K=1$ (toggle mode). The clock drives FF0 and each $Q_{k}$ drives the clock of the next flip-flop (ripple counter).
2. The counter counts up in binary: $000000$ to $100000$ (32). The next count, 33 = $100001$, is the first state with $Q_5=1$ and $Q_0=1$ together.
3. A 2-input NAND gate with inputs $Q_5$ and $Q_0$ drives the active-low CLEAR inputs of all six flip-flops. As soon as the count reaches 33 the NAND output goes low and clears the counter to $000000$.

Count sequence

The stable states are $0$ to $32$, so the counter has modulus 33.

3 inverters.

To find the 2's complement, copy all bits up to and including the first (least significant) 1 and invert only the bits to its left.

$10110000 \rightarrow 01010000$

The lowest 1 is at bit 4, so the bits $0000$ and that 1 are copied unchanged, and only the 3 higher bits $(101)$ are inverted, which needs 3 inverters. (The usual method, 1's complement followed by adding 1, needs 8 inverters and an adder.)

A serial-in parallel-out (SIPO) register is used. The 4 bits are entered serially, one per clock pulse, and then read together at the parallel outputs.

Circuit (4 D flip-flops):

Serial in --> [D FF0 Q0] --> [D FF1 Q1] --> [D FF2 Q2] --> [D FF3 Q3]
                  |              |              |              |
                 Q0             Q1             Q2             Q3   (parallel outputs)
CLK -------------- common to all four flip-flops ----------------
CLR -------------- common clear

Storing 1101 (the first bit, 1, is entered first):

After 4 clock pulses, $Q_3Q_2Q_1Q_0 = 1101$, so the whole word is stored with the first bit in $Q_3$.

Retrieving: all four bits are available at the same time at $Q_3Q_2Q_1Q_0$ after the 4th pulse and can be read in parallel. Retrieval needs no further clock pulses. Applying CLR resets the register for the next word.

This is an overlapping 101 detector, a Mealy machine (the example shows overlap: the 1 ending one pattern starts the next).

States: S0 = no useful bits, S1 = last bit "1", S2 = last two bits "10". Encode with $Q_1Q_0$: S0 = 00, S1 = 01, S2 = 10 (11 unused, don't care).

State diagram (input A / output B):

S0 --0/0--> S0        S1 --0/0--> S2
S0 --1/0--> S1        S1 --1/0--> S1
S2 --0/0--> S0        S2 --1/1--> S1

State table with T excitations ($T = Q \oplus Q_{next}$):

K-map simplification (using the don't cares):

$T_1 = Q_1 + Q_0A'$ $T_0 = Q_0 \oplus A$ $B = Q_1A$

Circuit: Two T flip-flops with a common clock. $T_1$ is an OR of $Q_1$ and the AND of $Q_0$ and $A'$; $T_0$ is an XOR of $Q_0$ and $A$; the output $B$ is an AND of $Q_1$ and $A$.

Check with input 0101011101: the states go S0, S1, S2, S1(out 1), S2, S1(out 1), S1, S1, S2, S0... which gives the output 0001010001, as required.

The 1's complement is obtained by inverting every bit. The number $(101011100)_2$ has 9 bits, so 9 inverters are required.

Detector for the pattern $000$ in a serial stream (overlapping allowed), Mealy type. Output is called $Z$ here to avoid confusion with flip-flop outputs.

States:

• $S_0$: no trailing 0 seen
• $S_1$: one trailing 0 seen
• $S_2$: two or more trailing 0s seen

State table (state $AB$, input $P$):

State $11$ is unused (don't care).

D inputs ($D =$ next state):

$D_A = P'(A+B), \qquad D_B = A'B'P', \qquad Z = AP'$

Circuit: two D flip-flops with a common clock, an OR gate (A+B) followed by an AND with $P'$ for $D_A$, a 3-input AND of $A', B', P'$ for $D_B$, and an AND of $A$ and $P'$ for the output.

Check: the stream $1\,0\,0\,0\,0$ moves $S_0\to S_0\to S_1\to S_2$, and the third 0 produces $Z=1$, and the fourth 0 gives $Z=1$ again (overlap).

Gray code changes only one bit between adjacent values. Labelling the K-map rows and columns in Gray order ($00,01,11,10$) makes physically adjacent cells differ in exactly one variable, so they can be grouped and the differing variable eliminated. Binary order ($00,01,10,11$) would put cells such as $01$ and $10$ next to each other although they differ in two variables, so grouping would give wrong results.

Sequence $010$ recogniser, Mealy machine with overlapping allowed, using T flip-flops.

States:

• $S_0$: start / no useful bits
• $S_1$: last bit was 0
• $S_2$: last two bits were 01

Encoding: $S_0=00,\ S_1=01,\ S_2=10$ ($AB$); $11$ unused (don't care).

State table ($X$ = input, $Z$ = output):

Next-state functions (from K-maps with the don't care):

$A^+ = BX, \qquad B^+ = X', \qquad Z = AX'$

T inputs ($T = Q \oplus Q^+$):

$T_A = A \oplus BX, \qquad T_B = B \oplus X'$

Excitation check: for $AB=01, X=1$: $A^+=1$, $T_A = 0\oplus1 = 1$ (A toggles to 1) and $B^+=0$, $T_B = 1$ (B toggles to 0), giving $10$ ✓.

Circuit: two T flip-flops with a common clock; an AND gate ($B\cdot X$) followed by an XOR with $A$ for $T_A$; a NOT on $X$ and an XOR with $B$ for $T_B$; and an AND of $A$ and $X'$ for the output $Z$.

Serial In Serial Out (SISO) register storing 101

Circuit: three D flip-flops $FF_2, FF_1, FF_0$ in cascade with a common clock. The serial data input $D_{in}$ goes to the D input of $FF_2$; $Q_2$ drives $D$ of $FF_1$; $Q_1$ drives $D$ of $FF_0$; and the serial output is taken from $Q_0$.

Din ─►[D FF2]─Q2─►[D FF1]─Q1─►[D FF0]─Q0─► Dout
          ▲            ▲            ▲
          └────────── Clock ────────┘

Store operation: the bits are entered one per clock pulse, so entering $1,0,1$ one bit per clock:

After 3 clock pulses, $Q_2Q_1Q_0 = 101$ is stored.

Retrieve operation: with no further input ($D_{in}=0$), three more clock pulses shift the bits out at $Q_0$:

The output sequence seen at $Q_0$ is $1,0,1$ (the first bit in the first out). The first stored bit is already at $Q_0$ after pulse 3, and the remaining bits appear after pulses 4 and 5.

Timing diagram: each stage's waveform is the input waveform delayed by one clock period per stage; $Q_2$ follows $D_{in}$ after clock 1, $Q_1$ after clock 2, $Q_0$ after clock 3. Storing and reading 3 bits therefore takes 3 clocks each.

0011 (taking the counter to shift right, with the inverted last output fed back to the first flip-flop):

$1100 \to 1110 \to 1111 \to 0111 \to 0011$

The 5 bits are loaded all at once (in parallel) and taken out one bit at a time (serially), so a Parallel-In Serial-Out (PISO) shift register is suitable.

Circuit: five D flip-flops $FF_0\ldots FF_4$ share a common clock. The D input of each flip-flop (except the first) is fed from a 2-to-1 selector (two ANDs and an OR) controlled by a $SHIFT/\overline{LOAD}$ line. With $SHIFT/\overline{LOAD}=0$ the parallel data $D_0\ldots D_4$ enter the flip-flop inputs; with $SHIFT/\overline{LOAD}=1$ each flip-flop takes the output of its neighbour, i.e. $D_i=Q_{i+1}$. The serial output is taken from the last flip-flop's $Q$.

D4  D3  D2  D1  D0   (parallel inputs)
 |   |   |   |   |
[MUX][MUX][MUX][MUX]--  (SHIFT/LOAD selects)
 |   |   |   |   |
[FF4]->[FF3]->[FF2]->[FF1]->[FF0]--> Serial out
 ^------------- common clock ------------^

Operation:

1. Set $SHIFT/\overline{LOAD}=0$ and apply one clock pulse. All 5 data bits are loaded into the flip-flops at the same time.
2. Set $SHIFT/\overline{LOAD}=1$. On each following clock pulse the data move one place towards the output.
3. After 5 clock pulses all 5 bits have appeared one by one at the serial output.

0011 (taking the ring counter to shift right, with the last bit fed back to the first). A 4-bit ring counter repeats every 4 pulses, so 7 pulses equal $7 \bmod 4=3$ pulses:

$1001\to1100\to0110\to0011$

The data enter one bit at a time (serial) and are read out all at once (parallel), so a Serial-In Parallel-Out (SIPO) shift register is used.

Circuit: four D flip-flops $FF_3,FF_2,FF_1,FF_0$ are connected in cascade: the serial input goes to the D input of the first flip-flop, and $Q$ of each flip-flop feeds the D input of the next. All flip-flops share one clock. The outputs $Q_3Q_2Q_1Q_0$ of the four flip-flops are the parallel outputs.

Serial in -> [D FF3 Q]->[D FF2 Q]->[D FF1 Q]->[D FF0 Q]
                |           |          |          |
               Q3          Q2         Q1         Q0   (parallel out)
              (common clock to all)

Operation: on each clock pulse, every bit moves one flip-flop to the right and a new bit enters the first flip-flop. After 4 clock pulses the 4 bits are present in the register and are read together at $Q_3Q_2Q_1Q_0$.

Timing diagram for the serial input 1, 0, 1, 1 (the first bit entered ends in the last flip-flop):

After the 4th pulse, $Q_3Q_2Q_1Q_0=1101$ is available in parallel.

Design a Mealy sequence detector for $11101$ that allows overlapping, with input $X$ and output $Z$.

States (by the progress made so far): $S_0$ = nothing matched, $S_1$ = "1", $S_2$ = "11", $S_3$ = "111", $S_4$ = "1110".

State table (next state / output $Z$):

After "1110" a 1 completes the sequence, and the final 1 can start a new match, so the next state is $S_1$.

State assignment ($Q_2Q_1Q_0$): $S_0 = 000$, $S_1 = 001$, $S_2 = 010$, $S_3 = 011$, $S_4 = 100$. The states 101, 110 and 111 are don't cares. For D flip-flops $D = Q^+$.

K-map results

$D_2 = Q_1 Q_0 X'$

$D_1 = X(Q_1 + Q_0)$

$D_0 = X(Q_0' + Q_1)$

$Z = Q_2 X$

Check. Sequence 1,1,1,0,1 from $S_0$: $S_0 \to S_1 \to S_2 \to S_3 \to S_4$ (input 0), then input 1 gives $Z = 1$ and the state returns to $S_1$.

Circuit. Three D flip-flops with a common clock, the gates above for $D_2, D_1, D_0$, and one AND gate ($Q_2 \cdot X$) for the output.

Gray code changes only one bit between successive values, so adjacent cells in the K-map differ in exactly one variable. This lets terms in neighbouring cells combine by $X + X' = 1$ and be grouped to eliminate variables. With binary ordering adjacent cells could differ in several bits, and the grouping would not work.

Taking the usual 4-bit right-shifting Johnson counter, the new MSB is the complement of the old LSB: $Q_3^+ = Q_0'$ and the other bits shift right.

The state after the 7th clock pulse is 1010. (1101 is not in the normal 8-state Johnson sequence, so the counter is in an unused cycle.)

A twisted ring (Johnson) counter shifts right and feeds the complement of the last bit back to the first bit. Starting at $1001001$:

The state after the 4th clock pulse is 0110100.

Sequence 1001 (overlapping), Mealy machine with D flip-flops.

States: $S_0$ = start, $S_1$ = "1", $S_2$ = "10", $S_3$ = "100".

State diagram (edges input/output):

S0 --1/0--> S1     S0 --0/0--> S0
S1 --0/0--> S2     S1 --1/0--> S1
S2 --0/0--> S3     S2 --1/0--> S1
S3 --1/1--> S1     S3 --0/0--> S0

State table

State assignment: $S_0=00,\ S_1=01,\ S_2=10,\ S_3=11$ for $AB$.

Flip-flop inputs ($D=Q^+$):

• $D_A=1$ for $ABX=010$ and $100$, so $D_A=A'BX'+AB'X'=X'(A\oplus B)$.
• $D_B=1$ for every row with $X=1$ and for $ABX=100$, so $D_B=X+AB'$.
• $Y=1$ only for $ABX=111$, so $Y=ABX$.

Circuit: two D flip-flops with a common clock, an XOR gate and AND gate for $D_A$, an AND and OR gate for $D_B$, and a 3-input AND gate for the output $Y$.

0101 sequence recognizer (overlapping, Mealy machine)

States (each remembers the longest suffix of the input that matches a prefix of 0101):

• $S_0$: nothing matched yet
• $S_1$: "0" seen
• $S_2$: "01" seen
• $S_3$: "010" seen

State table (next state / output $Z$):

In $S_3$ with input 1 the sequence 0101 is complete, so $Z=1$. The last "01" can start a new match, so the machine goes to $S_2$ (overlap allowed).

State assignment: $S_0=00,\ S_1=01,\ S_2=10,\ S_3=11$ for $Q_1Q_0$, using D flip-flops.

Simplified equations:

$D_1 = Q_0X + Q_1Q_0'X'$ $D_0 = X'$ $Z = Q_1Q_0X$

Circuit: two D flip-flops with a common clock. $D_0$ is just an inverter on $X$. $D_1$ uses two AND gates and one OR gate. The output $Z$ is a 3-input AND of $Q_1, Q_0, X$.

A clock pulse is a periodic rectangular (square) waveform that alternates between logic 1 (high) and logic 0 (low). It is used to synchronise the operation of sequential circuits such as flip-flops, registers and counters. Each pulse has a rising edge, a high level, a falling edge and a low level.

Error detection codes add extra (redundant) bits to data so that the receiver can detect errors introduced during transmission or storage.

Example: the parity bit. In even parity, a bit is added so that the total number of 1s is even. The data 1011001 has four 1s, so the parity bit is 0 and the transmitted word is 10110010. If a single bit flips, the receiver sees an odd number of 1s and detects the error. Other examples are checksum and CRC.

In 10111 the bit positions from the right are $2^0,2^1,2^2,2^3,2^4$. The 0 is in the fourth position, so its weight is $2^3=8$.

Adding two 4-bit words needs a 4-bit ripple adder:

• 1 half adder for the least significant bit (there is no carry-in).
• 3 full adders for the remaining three bits, each taking the carry from the previous stage.

(If a full adder is also used for the LSB, 4 full adders and no half adder are needed.)

A Programmable Logic Array (PLA) is a combinational device with a programmable AND array followed by a programmable OR array. Inputs and their complements feed the AND array, which forms product terms. The OR array sums chosen product terms to give the outputs. Any set of sum-of-products functions can be implemented by programming the fuse connections.

Example: implement

$F_1=AB+A'C,\qquad F_2=AB+BC$

Product terms: $P_1=AB$, $P_2=A'C$, $P_3=BC$.

The AND array is programmed with the A, B, C columns (1 means true input, 0 means complemented, - means not connected). The OR array connects $P_1,P_2$ to $F_1$ and $P_1,P_3$ to $F_2$. The shared term $P_1$ is generated once and used for both outputs.

A 1 Hz pulse is obtained from 16 Hz by dividing the frequency by 16. A MOD-16 binary (ripple) counter made of $\log_2 16 = 4$ flip-flops does this, because each flip-flop (J = K = 1, or T = 1) halves the frequency of its input.

16 Hz --> [FF0] --8 Hz--> [FF1] --4 Hz--> [FF2] --2 Hz--> [FF3] --> 1 Hz
 CLK      T=1             T=1             T=1             T=1      (output Q3)

The output of each stage is the clock of the next stage; the output of the last flip-flop (Q3) is the 1 Hz pulse.

Timing diagram (one output cycle spans 16 input clock pulses):

CLK(16Hz) : _|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_|‾|
Q0 (8 Hz) : ‾‾|__|‾‾|__|‾‾|__|‾‾|__|‾‾|__|‾‾|__|‾‾|__|‾‾|__|   (toggles every clock)
Q1 (4 Hz) : toggles every 2 clocks
Q2 (2 Hz) : toggles every 4 clocks
Q3 (1 Hz) : high for 8 clocks, low for 8 clocks  -> period = 16 clocks = 1 s

Check: $f_{out} = \dfrac{16}{2^4} = 1\ \text{Hz}$.

Number of address lines $n$ must satisfy $2^n \ge 500$.

$2^8 = 256 < 500$ and $2^9 = 512 \ge 500$.

So 9 address lines are required.

Properties of TTL (Transistor-Transistor Logic):

• Built from bipolar junction transistors (multi-emitter input transistor and a totem-pole output).
• Single +5 V supply.
• Logic levels: LOW is 0 to 0.8 V, HIGH is 2 to 5 V.
• Propagation delay about 10 ns per gate (fast).
• Power dissipation about 10 mW per gate.
• Fan-out of about 10.
• Noise margin about 0.4 V.
• Wide range of available functions (the 74xx series).

(a) Using 8 bits:

$A = 61 = 00111101,\qquad B = 32 = 00100000$

2's complement of $A$: invert to $11000010$ and add 1 to get $11000011$.

$B - A = B + (-A)$:

$\begin{array}{r} 00100000 \\ +\;11000011 \\ \hline 11100011 \end{array}$

There is no carry out of the MSB, so the result is negative and is in 2's complement form. Its magnitude is the 2's complement of $11100011$: $00011100 + 1 = 00011101 = 29$.

So $B - A = -29$, which matches $32 - 61 = -29$.

(b) Analog to digital conversion has these steps:

1. Sampling: the analog signal is measured at regular intervals. The sampling rate must be at least twice the highest signal frequency (Nyquist criterion).
2. Holding: a sample-and-hold circuit keeps each sampled value constant while it is converted.
3. Quantization: each held value is approximated to the nearest of a finite set of $2^n$ levels. The difference is the quantization error.
4. Encoding: each quantized level is given an $n$-bit binary code, producing the digital output.

Select lines $n$ must satisfy $2^n \ge 99$. Since $2^6 = 64 < 99 \le 128 = 2^7$, 7 select lines are required.

8-to-1 MUX from 4-to-1 MUXes: Use three 4-to-1 MUXes in two levels. Select lines are $S_2 S_1 S_0$.

I0..I3 --> [4:1 MUX A] --\
            S1 S0         \
                           [4:1 MUX C] --> Y
I4..I7 --> [4:1 MUX B] --/  (inputs: A, B; other two unused)
            S1 S0            select = S2 (on its S0), S1 = 0

• MUX A selects one of $I_0$ to $I_3$ and MUX B selects one of $I_4$ to $I_7$, both using $S_1S_0$.
• MUX C passes A when $S_2 = 0$ and B when $S_2 = 1$ (a 2-to-1 selection, so only two of its inputs are used).

$Y = S_2'\,(\text{MUX A output}) + S_2\,(\text{MUX B output})$

This gives the full 8-to-1 function.

Circuit diagram (clocked J-K flip-flop using NAND gates):

        +-----------+
J ------| NAND  G1  |--+--------+
Q' -----|  (3 in)   |  |        |
CLK ----|           |  |    +---------+
        +-----------+  +----| NAND G3 |---- Q
                            |         |<----- Q'
        +-----------+  +----|         |
K ------| NAND  G2  |--+    +---------+
Q ------|  (3 in)   |       +---------+
CLK ----|           |-------| NAND G4 |---- Q'
        +-----------+       |         |<---- Q
                            +---------+

G1 has inputs J, CLK and Q'; G2 has inputs K, CLK and Q. G3 and G4 are the cross-coupled NAND latch, with outputs Q and Q'. The feedback from Q and Q' removes the invalid state of the S-R flip-flop.

Truth table (at the active clock edge):

Characteristic equation:

$Q_{n+1} = J\,Q_n' + K'\,Q_n$

A serial-in serial-out (SISO) right-shift register is used. The bits are loaded one per clock pulse at the serial input, and shift right on every pulse until they leave at the serial output. The sequence has 3 bits, so a 3-bit register (3 D flip-flops) is needed.

Din --> [D FF0 Q0] --> [D FF1 Q1] --> [D FF2 Q2] --> Dout
           ^              ^              ^
CLK -------+--------------+--------------+

Input bits in order: 1, 0, 1.

Timing diagram:

CLK  : _|‾|_|‾|_|‾|_|‾|_|‾|_
Din  : 1   0   1   0   0
Q0   : 1   0   1   0   0
Q1   : 0   1   0   1   0
Q2   : 0   0   1   0   1   <- Dout

Clock pulses needed: 3 pulses to load the 3 bits (the first bit then appears at the output), plus 2 more to shift out the remaining bits. The total is $2n - 1 = 5$ clock pulses.

$Y = ABCD' + A'B'CD + ABC + A'B'CD' + ACD + AB'C'D$

Expand to minterms (order $ABCD$):

• $ABCD' = 1110 = 14$
• $A'B'CD = 0011 = 3$
• $ABC = 1110, 1111 = 14, 15$
• $A'B'CD' = 0010 = 2$
• $ACD = 1011, 1111 = 11, 15$
• $AB'C'D = 1001 = 9$

$Y = \sum m(2, 3, 9, 11, 14, 15)$

K-map:

Groups:

• $m_2, m_3$ gives $A'B'C$
• $m_9, m_{11}$ gives $AB'D$
• $m_{14}, m_{15}$ gives $ABC$

All three are essential (each covers a minterm no other prime implicant covers).

$Y = A'B'C + AB'D + ABC$

(a) AND-OR circuit: Three AND gates (3-input) produce $A'B'C$, $AB'D$ and $ABC$ (using NOT gates for $A'$ and $B'$). Their outputs feed one 3-input OR gate that gives $Y$.

(b) NAND-only circuit: Apply double complement and De Morgan:

$Y = \left[(A'B'C)'\cdot(AB'D)'\cdot(ABC)'\right]'$

Three 3-input NAND gates form the first level and a 3-input NAND gate is the second level. NOT gates for $A'$ and $B'$ are used as allowed.

(a) Digital clock: A digital clock counts pulses of a stable 1 Hz signal and displays the time in hours, minutes and seconds.

Crystal      Divider chain       1 Hz    Seconds      Minutes      Hours
oscillator --> (divide by 2^15 --------> counter ---> counter ---> counter
32.768 kHz     = 15 flip-flops)          MOD-60       MOD-60       MOD-12/24
(or 50 Hz mains                          (MOD-10 +    (MOD-10 +
 + MOD-50 counter)                        MOD-6)       MOD-6)
                                           |             |            |
                                       BCD-to-7seg   BCD-to-7seg  BCD-to-7seg
                                        decoders      decoders     decoders
                                           |             |            |
                                       7-seg displays (SS)  (MM)     (HH)

• The oscillator gives a stable frequency, divided down to 1 Hz.
• The units-of-seconds counter is MOD-10 and the tens counter is MOD-6, giving MOD-60. The carry from it clocks the minutes counter, whose carry clocks the hours counter (MOD-12 or MOD-24).
• Each BCD digit goes through a BCD-to-seven-segment decoder to a seven-segment display.
• Set switches allow hours and minutes to be adjusted.

(b) Sequence detector for 011 (Mealy machine, output Z = 1 when 011 has just been received).

States:

• S0: initial / no useful bits received
• S1: last bit received was 0 (so far "0")
• S2: last two bits received were "01"

State diagram (arrows labelled input/output):

          1/0                 0/0
        +-----+            +-----+
        v     |            v     |
      (S0) ---0/0---> (S1) ---1/0---> (S2)
        ^                ^              |  |
        |                +------0/0-----+  |
        +----------------1/1---------------+

State table:

The output 1 occurs only from S2 on input 1, which is the completion of 0-1-1.

Convert each octal digit to 3 bits:

$(67.51)_8 = (110\ 111.\ 101\ 001)_2 = 110111.101001_2$

Regroup into 4 bits from the radix point:

• Integer part: $0011\ 0111 = 37$
• Fraction part: $1010\ 01\mathbf{00} = A4$

$(67.51)_8 = (37.A4)_{16}$

An alphanumeric code (such as ASCII or EBCDIC) can represent letters, decimal digits, punctuation and control characters, so text as well as numbers can be stored and communicated. Other codes such as BCD or Gray code represent only numbers.

A K-map has $2^n$ cells for $n$ variables, so its size doubles with each variable. Beyond 5 or 6 variables the map becomes too large and needs many dimensions, so adjacent cells are hard to see and grouping becomes error-prone. Hence it is practical only for a limited number of variables (up to about 4-6).

A Johnson (twisted-ring) counter with $n$ flip-flops has $2n$ states, so 6 states need $n = 3$ D flip-flops. The inverted output $Q_2'$ of the last flip-flop is fed back to the first D input.

   +----------------------------------------+
   |                                        |
   +--> [D FF0 Q0] --> [D FF1 Q1] --> [D FF2 Q2]--+
        D0=Q2'          D1=Q0         D2=Q1  (Q2' from here)
         ^                ^              ^
CLK -----+----------------+--------------+

Count sequence:

Six different states are counted.

$AB + A'B' + ABC'D' + A'B$

Using absorption, $AB + ABC'D' = AB$. Also $A'B' + A'B = A'(B' + B) = A'$.

$= AB + A' = A' + B$

Final answer: $A' + B$.

• ECL: high-speed applications such as supercomputers, high-speed communication and test equipment, because it is the fastest logic family.
• CMOS: low-power battery-operated devices such as digital watches, calculators and portable equipment (it is also used in microprocessors and memory chips).

Each read or write accesses 32 bits at once, so the memory is organised in words of 32 bits.

$\text{Number of words} = \frac{1696}{32} = 53$

The address decoder selects one of 53 words:

• Input: $n$ address lines with $2^n \ge 53$, so $n = 6$ (since $2^5 = 32 < 53 \le 64$).
• Output: 53 word-select lines (a 6-to-64 decoder with only 53 outputs used).

In a PLA both the AND array and the OR array are programmable, while in a PAL only the AND array is programmable and the OR array is fixed. The PLA is therefore more flexible: product terms can be shared between several outputs and any product term can be connected to any output, so Boolean functions are implemented with fewer product terms and less area.

Division ratio $= 56/7 = 8 = 2^3$.

Each flip-flop divides the frequency by 2, so 3 flip-flops (a MOD-8 counter) are required.

(a) Use 8 bits.

$A = 37 = 00100101,\qquad B = -18$

$18 = 00010010$, so $B = -18 = 11101110$ (2's complement).

$B - A = B + (-A)$. The 2's complement of $A$: invert $00100101$ to $11011010$ and add 1 to get $11011011$.

$\begin{array}{r} 11101110 \\ +\;11011011 \\ \hline 1\,11001001 \end{array}$

Discard the carry out: result $= 11001001$. The MSB is 1, so the result is negative. Its magnitude is $00110110 + 1 = 00110111 = 55$.

So $B - A = -55$, which matches $-18 - 37 = -55$.

(b) Advantages:

Analog technology:

1. It represents real-world quantities continuously, with theoretically infinite resolution.
2. It needs less bandwidth and often simpler circuitry for simple signals.