Digital Logic

$F = B'C'D' + BCD' + ABCD'$ with $d = B'CD' + A'BC'D$ (variables $A,B,C,D$).

Minterms of $F$ (ABCD):

• $B'C'D' = 0000, 1000$, so $m_0, m_8$
• $BCD' = 0110, 1110$, so $m_6, m_{14}$
• $ABCD' = 1110$, so $m_{14}$

$F = \Sigma(0, 6, 8, 14)$

Don't cares:

• $B'CD' = 0010, 1010$, so $m_2, m_{10}$
• $A'BC'D = 0101$, so $m_5$

$d = \Sigma(2, 5, 10)$

K-map (rows $AB$, columns $CD$; X = don't care)

SOP:

• Quad $m_0, m_2, m_8, m_{10}$ gives $B'D'$
• Quad $m_2, m_6, m_{10}, m_{14}$ gives $CD'$

$F = B'D' + CD'$

POS: group the 0s (using the X in $m_5$ and $m_{10}$ where useful):

• $m_1, m_3, m_5, m_7, m_9, m_{11}, m_{13}, m_{15}$ (all $D=1$ cells) gives $D$
• $m_4, m_5, m_{12}, m_{13}$ gives $BC'$

$F' = D + BC' \;\Rightarrow\; F = D'(B' + C)$

Both forms are equal: $D'(B' + C) = B'D' + CD'$.

$F(A,B,C,D)=\prod M(2,3,4,5,7,9,10)$ with don't cares at 0, 6, 11. So the 0s are 2, 3, 4, 5, 7, 9, 10; the don't cares are 0, 6, 11; and the 1s are 1, 8, 12, 13, 14, 15.

K-map (rows $AB$, columns $CD$; X = don't care):

SOP form (group the 1s, using don't cares where useful)

• Cells 12, 13, 15, 14 (row $AB=11$): $AB$
• Cells 8, 12: $A\bar C\bar D$
• Cells 0 (X), 1: $\bar A\bar B\bar C$

$F = AB + A\bar C\bar D + \bar A\bar B\bar C$

POS form (group the 0s, using don't cares where useful)

• Cells 2, 3, 10, 11 (X): $\bar BC$, so the sum term is $(B+\bar C)$
• Cells 4, 5, 7, 6 (X): $\bar AB$, so the sum term is $(A+\bar B)$
• Cells 9, 11 (X): $A\bar BD$, so the sum term is $(\bar A+B+\bar D)$

$F = (B+\bar C)(A+\bar B)(\bar A+B+\bar D)$

Check: for minterm 9 ($ABCD=1001$) the last factor is $0+0+0=0$, so $F=0$ as required; for minterm 8 ($1000$) all three factors are 1, so $F=1$ as required.

$f(A,B,C,D) = \Pi M(0,1,3,7,8,12)\cdot d(5,10,13,14)$

So $f = 0$ at 0, 1, 3, 7, 8, 12; don't care at 5, 10, 13, 14; and $f = 1$ at the remaining minterms 2, 4, 6, 9, 11, 15.

K-map (rows $AB$, columns $CD$)

        CD: 00   01   11   10
AB=00        0    0    0    1
AB=01        1    X    0    1
AB=11        0    X    1    X
AB=10        0    1    1    X

SOP (group the 1s)

• $m_2, m_6, m_{10}, m_{14}$ gives $CD'$ (uses X at 10, 14).
• $m_9, m_{11}, m_{13}, m_{15}$ gives $AD$ (uses X at 13).
• $m_4, m_5$ gives $A'BC'$ (uses X at 5), covering $m_4$.

$f_{SOP} = CD' + AD + A'BC'$

POS (group the 0s)

• $m_8, m_{10}, m_{12}, m_{14}$ gives $AD'$ (uses X at 10, 14), covering 8 and 12.
• $m_1, m_3, m_5, m_7$ gives $A'D$ (uses X at 5), covering 1, 3, 7.
• $m_0, m_8$ gives $B'C'D'$, covering 0.

$f' = AD' + A'D + B'C'D'$

Complementing:

$f_{POS} = (A' + D)(A + D')(B + C + D)$

Check: at $m_0$: $(A'+D)=1$, $(A+D')=1$, $(B+C+D)=0$, so $f=0$. At $m_1$: $(A+D') = 0$, so $f=0$. At $m_4$: all three factors are 1, so $f=1$. At $m_8$: $(A'+D)=0$, so $f=0$. At $m_{15}$: all 1, so $f=1$.

Clocked JK flip-flop

A JK flip-flop is a clocked bistable element with two data inputs $J$ and $K$ and outputs $Q$ and $\bar Q$. It removes the invalid state of the SR flip-flop: when $J=K=1$ the output toggles. The state changes only when the clock pulse (or edge) arrives.

Logic diagram: it is built from a clocked SR flip-flop (two cross-coupled NAND gates) with two extra 3-input NAND gates at the input.

• Upper gate: inputs $J$, $CLK$ and $\bar Q$; its output is $S$.
• Lower gate: inputs $K$, $CLK$ and $Q$; its output is $R$.
• These feed the cross-coupled NAND latch whose outputs are $Q$ and $\bar Q$.

The feedback of $Q$ and $\bar Q$ to the input gates is what makes $J=K=1$ toggle the output.

Truth table (at an active clock pulse)

Characteristic table

Characteristic equation: $Q_{n+1}=J\bar Q_n+\bar K Q_n$.

Excitation table (what inputs are needed for a required transition)

D flip-flop: a flip-flop with a single data input $D$. On the active clock edge the output takes the value of $D$, so $Q(t+1) = D$. It is also called a delay or data flip-flop. It is made from an SR flip-flop by connecting $S = D$ and $R = D'$, so the invalid state cannot occur.

Clocked RS flip-flop

Logic diagram: the basic cross-coupled NAND (or NOR) latch is preceded by two gates. Input $S$ is ANDed with the clock to give the set input of the latch, and $R$ is ANDed with the clock to give the reset input. When CP = 0 both gates output inactive values, so the latch holds its state. When CP = 1 the inputs $S$ and $R$ reach the latch.

Operation:

• $S=0, R=0$: no change.
• $S=0, R=1$: reset, $Q=0$.
• $S=1, R=0$: set, $Q=1$.
• $S=1, R=1$: invalid, since both outputs go to the same level and the final state is unpredictable.

Truth table

Characteristic equation: $Q(t+1) = S + R'Q$, with $SR = 0$.

MOD-5 counter: counts 0, 1, 2, 3, 4 and returns to 0. It needs $\lceil\log_2 5\rceil = 3$ flip-flops. A synchronous design with JK flip-flops follows. States are $ABC$.

State table and excitation (J, K entries from the JK excitation table: 0→0 is 0X, 0→1 is 1X, 1→0 is X1, 1→1 is X0)

K-map simplification (states 101, 110, 111 as don't cares)

$J_A = BC,\quad K_A = 1$ $J_B = K_B = C$ $J_C = A',\quad K_C = 1$

If the counter powers up in an unused state, it returns to the valid sequence: 101 goes to 010, 110 goes to 010 and 111 goes to 000.

State diagram: $000 \to 001 \to 010 \to 011 \to 100 \to 000$

Timing diagram (outputs change on the falling edge of the clock)

CLK : _|‾|_|‾|_|‾|_|‾|_|‾|_|‾|_
A   : ______________|‾‾‾‾|_____    (high only in state 4)
B   : ______|‾‾‾‾‾‾‾‾‾‾|_________    (high in states 2,3)
C   : __|‾‾|____|‾‾|_______________  (high in states 1,3)
count:  0   1   2   3   4   0

The pattern repeats every 5 clock pulses, and the output of A has frequency $f/5$.

We need $1010.110 - 101.101$, that is $10.75 - 5.625 = 5.125 = 101.001_2$.

Write the subtrahend with 4 integer bits: $0101.101$.

Using 2's complement

1's complement of $0101.101$ is $1010.010$. Add 1 at the last bit: 2's complement $= 1010.011$.

$1010.110 + 1010.011 = 1\,0101.001$

The carry out is discarded (it indicates a positive result), so the answer is $+0101.001 = +101.001$.

Using 1's complement

1's complement of $101.101$ is $1010.010$.

$1010.110 + 1010.010 = 1\,0101.000$

There is an end-around carry: remove the carry and add it to the last bit.

$0101.000 + 0000.001 = 0101.001$

Answer: $+101.001_2$ ($= 5.125_{10}$) by both methods.

Equations (reading $x/B$ as $x'B$):

$A(t+1) = x'y + xA$ $B(t+1) = x'B + xA$ $z = B$

For D flip-flops $D_A = x'y + xA$ and $D_B = x'B + xA$.

1. Logic diagram

x --[NOT]--> x'
x' , y     --[AND]--+
x  , A     --[AND]--+--[OR]--> D_A --[D FF A]--> A  (fed back)
x' , B     --[AND]--+
x  , A     --[AND]--+--[OR]--> D_B --[D FF B]--> B  (fed back)
B ---------------------------------------------> z
CLK -> both flip-flops

Components: one inverter, four 2-input AND gates (the $xA$ term is shared and can use a single gate), two 2-input OR gates and two D flip-flops. The output $z$ is taken directly from $B$.

2. State table (present state $AB$, inputs $xy$)

For example, with $AB=01$, $xy=10$: $A^+ = 0 + 1\cdot0 = 0$, $B^+ = 0\cdot1 + 1\cdot0 = 0$.

3. State diagram

The states are $00, 01, 10, 11$ (labelled $AB$). The output depends only on the state: $z = 1$ in states 01 and 11, $z=0$ in states 00 and 10. Transitions are labelled $xy$:

State 00 (z=0): xy=00,10,11 -> 00 ;  xy=01 -> 10
State 01 (z=1): xy=00 -> 01 ;  xy=01 -> 11 ;  xy=10,11 -> 00
State 10 (z=0): xy=00 -> 00 ;  xy=01 -> 10 ;  xy=10,11 -> 11
State 11 (z=1): xy=00 -> 01 ;  xy=01,10,11 -> 11

Summary of the behaviour: when $x = 0$, $A$ loads $y$ and $B$ holds its value; when $x = 1$, $A$ holds its value and $B$ loads $A$. State 11 is reached and held while $x = 1$ and $A = 1$; from 11 the circuit leaves only through $x=0,y=0$ (to 01).

The zeros of $F$ are the maxterms 0, 2, 4, 6, 8, 10, 12, 14, so $F=1$ for the odd minterms 5, 7, 13, 15, and the don't-care conditions are the cells 1, 3, 9, 11.

K-map (rows $wx$, columns $yz$; X = don't care):

SOP form. The cells with $z=1$ (the whole column $yz=01$ and $yz=11$: cells 1, 3, 5, 7, 9, 11, 13, 15) form one octet, using the don't cares as 1. The octet is independent of $w$, $x$ and $y$:

$F = z$

POS form. Group the 0s (cells 0, 2, 4, 6, 8, 10, 12, 14), which form the octet $z=0$. Writing the group as the product $\bar z$ and complementing it (De Morgan) gives the sum term $z$, with no other variable involved:

$F = z$

Both forms give the same result, $F=z$, so the function needs no gate at all, only a wire from input $z$.

Combinational logic circuit

A combinational logic circuit is a circuit whose output at any instant depends only on the present combination of its inputs, and not on past inputs. It has no memory or feedback. It is built from logic gates; examples are adders, decoders, multiplexers and comparators.

Full adder

A full adder adds three 1-bit inputs: the two bits $A$ and $B$ and the carry-in $C_{in}$, giving a sum $S$ and a carry-out $C_{out}$.

Truth table:

From the truth table, $S=\sum m(1,2,4,7)$ and $C_{out}=\sum m(3,5,6,7)$.

$S=\bar A\bar B C_{in}+\bar A B\bar C_{in}+A\bar B\bar C_{in}+ABC_{in}=A\oplus B\oplus C_{in}$

K-map simplification of $C_{out}$ gives

$C_{out}=AB+BC_{in}+AC_{in}=AB+C_{in}(A\oplus B)$

Logic diagram: two half adders and an OR gate. The first half adder takes $A$ and $B$ (XOR gives $A\oplus B$, AND gives $AB$). The second half adder takes $A\oplus B$ and $C_{in}$ (XOR gives the sum $S$, AND gives $C_{in}(A\oplus B)$). An OR gate combines the two AND outputs to give $C_{out}$.

Combinational circuit

A combinational circuit is a logic circuit whose output at any instant depends only on the present combination of inputs, not on past inputs. It has no memory or feedback. Examples: adders, multiplexers, decoders, encoders.

Design procedure

1. State the problem and decide the number of inputs and outputs.
2. Assign letter symbols to the inputs and outputs.
3. Derive the truth table that defines the relation between inputs and outputs.
4. Obtain the simplified Boolean expression for each output (K-map or Boolean algebra).
5. Draw the logic diagram with the simplified expressions and verify it.

Half adder

A half adder adds two single bits $A$ and $B$ and gives a sum $S$ and a carry $C$.

Boolean expressions: $S=\bar AB+A\bar B=A\oplus B,\qquad C=AB$

Logic diagram: an XOR gate with inputs $A,B$ gives the sum, and an AND gate with the same inputs gives the carry.

State diagram

A state diagram is a graphical representation of a sequential circuit. Each state is a circle, and each directed arrow between circles is a transition labelled with "input/output" (Mealy) or just the input (Moore, with the output written inside the state circle). It shows how the circuit moves from state to state for each input.

Given circuit: D flip-flops $A$, $B$; input $x$; output $z$. $D_A=A'+B,\qquad D_B=B'x,\qquad z=A+B'$

(i) Logic diagram

• $D_A$: a NOT gate on $A$ and an OR gate with $B$ give $D_A=A'+B$, connected to flip-flop $A$.
• $D_B$: a NOT gate on $B$ and an AND gate with $x$ give $D_B=B'x$, connected to flip-flop $B$.
• Output: a NOT gate on $B$ and an OR gate with $A$ give $z=A+B'$.
• Both flip-flops share one clock.

(ii) State table

(iii) State diagram (Moore type, because $z$ depends only on the present state: $z=1$ in states $00,10,11$ and $z=0$ in state $01$)

• State $00/z{=}1$: on $x=0$ go to $10$; on $x=1$ go to $11$.
• State $01/z{=}0$: on $x=0$ or $1$ go to $10$.
• State $10/z{=}1$: on $x=0$ go to $00$; on $x=1$ go to $01$.
• State $11/z{=}1$: on $x=0$ or $1$ go to $10$.

Flip-flop versus latch

Clocked SR flip-flop

It is an SR latch with two extra NAND gates that gate the inputs $S$ and $R$ with the clock $CLK$. When $CLK = 0$ the flip-flop holds its state; when $CLK = 1$ the inputs act on it.

Logic diagram:

S ──┐
    NAND ──┐
CLK─┤      │
    └──────┼── NAND (Q) ──── Q
           │      ╳ cross-coupled
    ┌──────┼── NAND (Q') ─── Q'
CLK─┤      │
    NAND ──┘
R ──┘

Truth table (with $CLK = 1$)

Characteristic table

Characteristic equation: $Q(t+1) = S + R'Q$ with the constraint $SR = 0$.

Excitation table

Subtract $675.6 - 456.4$.

Using 10's complement

10's complement of $456.4$ (3 integer digits): $10^3 - 456.4 = 543.6$

$675.6 + 543.6 = 1219.2$

The carry (leftmost 1) is discarded, so the result is 219.2.

Using 9's complement

9's complement of $456.4$: $999.9 - 456.4 = 543.5$

$675.6 + 543.5 = 1219.1$

The end-around carry is added to the result:

$219.1 + 1 \text{ (at the last digit)} = 219.2$

The answer is 219.2 by both methods. Check: $675.6 - 456.4 = 219.2$.

Universal gate: a gate from which every other basic gate (NOT, AND, OR) and hence any logic function can be built. NAND and NOR are universal gates.

NAND as a universal gate

• NOT: tie the inputs together: $Y = (A\cdot A)' = A'$
• AND: NAND followed by a NAND used as NOT: $Y = ((AB)')' = AB$
• OR: invert each input with a NAND, then NAND them: $Y = (A'\cdot B')' = A + B$ (De Morgan)

NOR as a universal gate

• NOT: tie the inputs together: $Y = (A + A)' = A'$
• OR: NOR followed by a NOR used as NOT: $Y = ((A+B)')' = A + B$
• AND: invert each input with a NOR, then NOR them: $Y = (A' + B')' = AB$ (De Morgan)

Gate counts: NOT = 1, AND = 2, OR = 3, using either gate type.

Encoder: a combinational circuit with $2^n$ (or fewer) input lines and $n$ output lines. Exactly one input is active at a time, and the output is the binary code of that input.

Octal-to-binary encoder (8 inputs $D_0$ to $D_7$, 3 outputs $A_2A_1A_0$)

Boolean equations

$A_0 = D_1 + D_3 + D_5 + D_7$ $A_1 = D_2 + D_3 + D_6 + D_7$ $A_2 = D_4 + D_5 + D_6 + D_7$

Logic diagram: three 4-input OR gates.

• OR gate 1 takes $D_1, D_3, D_5, D_7$ and gives $A_0$.
• OR gate 2 takes $D_2, D_3, D_6, D_7$ and gives $A_1$.
• OR gate 3 takes $D_4, D_5, D_6, D_7$ and gives $A_2$.

$D_0$ is not connected to any gate, because the all-zero output already represents $D_0$.

4-bit serial-in parallel-out (SIPO) shift register

Design: four D flip-flops $FF_A$, $FF_B$, $FF_C$, $FF_D$ share one clock.

• The serial input goes to $D$ of $FF_A$.
• $Q_A$ feeds $D$ of $FF_B$, $Q_B$ feeds $D$ of $FF_C$, and $Q_C$ feeds $D$ of $FF_D$.
• The four outputs $Q_A, Q_B, Q_C, Q_D$ are available together as the parallel output.

On each rising clock edge every bit moves one place to the right and a new bit enters $FF_A$. After four clock pulses the four serial bits are available in parallel. The first bit entered is in $Q_D$.

Operation example: serial input 1, 0, 1, 1 (register initially 0000)

Timing diagram

CLK : _|‾|_|‾|_|‾|_|‾|_
Din : ‾‾‾|___|‾‾‾‾‾‾‾‾‾   (1 0 1 1)
QA  : __|‾‾|___|‾‾‾‾‾‾‾
QB  : _____|‾‾‾|___|‾‾‾‾
QC  : _________|‾‾‾|____
QD  : _____________|‾‾‾‾

Each output is the previous stage's output delayed by one clock period. After the 4th pulse the parallel data $Q_AQ_BQ_CQ_D = 1101$ can be read.

Difference between PLA and PAL

PLA design

$F_1(A,B,C) = \Sigma(2,3,5)$, $F_2(A,B,C) = \Sigma(0,4,5,7)$

K-map simplification

$F_1$: minterms 2 (010) and 3 (011) combine to $A'B$; minterm 5 (101) is alone, $AB'C$.

$F_1 = A'B + AB'C$

$F_2$: minterms 0 and 4 combine to $B'C'$; minterms 5 and 7 combine to $AC$.

$F_2 = B'C' + AC$

The PLA needs four distinct product terms:

$P_1 = A'B$, $P_2 = AB'C$, $P_3 = B'C'$, $P_4 = AC$.

PLA program table

In the inputs column, 1 means the variable is used true, 0 means complemented, and - means the variable is absent. In the outputs, 1 means the product term goes to that OR gate. (Outputs: $F_1 = P_1 + P_2$, $F_2 = P_3 + P_4$.)

PLA structure

Inputs A,B,C (with complements) --> AND array --> P1,P2,P3,P4
   P1 ,P2 --> OR gate --> F1
   P3 ,P4 --> OR gate --> F2

Each programmable connection (cross) in the AND array corresponds to a 1/0 entry in the table, and in the OR array to a 1 in the output columns.

D flip-flop: A D (Data) flip-flop is a one-input flip-flop whose output follows the input at the clock edge: $Q(t+1) = D$. It stores one bit and delays the data by one clock period, so it is also called a delay flip-flop.

Master-slave flip-flop using JK flip-flops

An ordinary level-triggered JK flip-flop suffers from the race-around condition: when $J = K = 1$ and CLK stays high longer than the propagation delay, the output toggles repeatedly. A master-slave arrangement avoids this.

Construction: two JK flip-flops are cascaded. The first (master) receives the external $J$, $K$ and the clock CLK. The second (slave) receives the master's outputs $Q_m$ and $Q_m'$ as its $J$ and $K$, and the inverted clock CLK'. The final outputs $Q$ and $Q'$ are taken from the slave.

J --\                          Qm              Q
     [ MASTER JK ]-----------> J [ SLAVE JK ] ----> Q
K --/   (CLK)       Qm' ---->  K   (CLK')    ----> Q'
          ^                          ^
          |                          |
         CLK ---------[NOT]----------+

Operation

• CLK = 1: the master is enabled and responds to $J$, $K$ (and its own feedback), while the slave is disabled (its clock CLK' = 0), so the output $Q$ cannot change.
• CLK = 0: the master is disabled and holds its value; the slave is enabled and copies the master's state to the outputs.

So the output changes only once per clock, at the falling edge, and no race-around occurs, because the master's change is not fed back to the inputs while it is enabled.

Truth table (state change at the falling edge of the clock)

Characteristic equation: $Q(t+1) = JQ' + K'Q$. Connecting $J=D$ and $K=D'$ through an inverter turns the master-slave JK into a master-slave D flip-flop.

Difference between asynchronous and synchronous counters

4-bit binary ripple (up) counter

It counts 0 to 15 (16 states, MOD-16) using four JK (or T) flip-flops with $J = K = 1$ so that each toggles on a clock edge. Outputs $Q_3 Q_2 Q_1 Q_0$ with $Q_0$ the LSB. The flip-flops are negative-edge triggered, the clock goes to FF0 and the output $Q$ of each stage is the clock of the next.

Circuit

        J=K=1        J=K=1        J=K=1        J=K=1
CLK --> [FF0] Q0 --> [FF1] Q1 --> [FF2] Q2 --> [FF3] Q3

Each flip-flop toggles when the preceding output goes from 1 to 0 (a falling edge), so each stage divides the frequency by 2: $f_{Q_3} = f_{CLK}/16$.

State table

State diagram: $0 \to 1 \to 2 \to \dots \to 15 \to 0$ (one loop of 16 states).

Timing diagram

CLK: _|~|_|~|_|~|_|~|_|~|_|~|_|~|_|~|_|~|_ ...
Q0 : __/~\__/~\__/~\__/~\__/~\ ...            toggles every clock
Q1 : ____/~~~\___/~~~\___/~~~\ ...            toggles every 2 clocks
Q2 : ________/~~~~~~~\_______ ...             toggles every 4 clocks
Q3 : ________________/~~~~~~~~~~~~~~~\ ...    toggles every 8 clocks

$Q_0$ has half the clock frequency, $Q_1$ a quarter, $Q_2$ an eighth and $Q_3$ one-sixteenth.

Decoder: A decoder is a combinational circuit that converts an $n$-bit binary code on its inputs into a maximum of $2^n$ unique output lines, activating exactly one output for each input combination. It is the opposite of an encoder.

3-to-8 line decoder

Inputs $A, B, C$ ($A$ MSB), outputs $D_0$ to $D_7$. Each output is a minterm of the inputs. Optionally an enable input $E$ is ANDed with each output.

Truth table

Output equations

$D_0 = A'B'C',\; D_1 = A'B'C,\; D_2 = A'BC',\; D_3 = A'BC$ $D_4 = AB'C',\; D_5 = AB'C,\; D_6 = ABC',\; D_7 = ABC$

Logic diagram

A --+------[NOT]--- A'
B --+------[NOT]--- B'
C --+------[NOT]--- C'

A' B' C' --[AND3]-- D0        A  B' C' --[AND3]-- D4
A' B' C  --[AND3]-- D1        A  B' C  --[AND3]-- D5
A' B  C' --[AND3]-- D2        A  B  C' --[AND3]-- D6
A' B  C  --[AND3]-- D3        A  B  C  --[AND3]-- D7

Three inverters and eight 3-input AND gates are needed. It can be used for memory address decoding, code conversion and implementing Boolean functions (OR the required outputs).

ROM (Read-Only Memory): ROM is a non-volatile memory whose contents are fixed (written during manufacture or programmed once) and which can only be read in normal operation. A ROM with $n$ address inputs and $m$ outputs has $2^n$ words of $m$ bits. Internally it is a fixed AND array (an $n$-to-$2^n$ decoder) followed by a programmable OR array, so it can realise any combinational function: the inputs are the address and the outputs are the stored data bits.

Implementation

The table has 2 inputs ($A_1, A_0$) and 2 outputs ($F_1, F_2$), so a $4 \times 2$ ROM is required (4 words of 2 bits).

From the table:

$F_1 = \Sigma(0, 2, 3), \quad F_2 = \Sigma(1, 2)$

ROM structure: a 2-to-4 decoder produces the word lines $W_0$ to $W_3$ (the minterms); the OR array connections (fuses left intact) are:

• $F_1 = W_0 + W_2 + W_3$
• $F_2 = W_1 + W_2$

A1 -->[ 2-to-4 ]--> W0 --------+-------> OR --> F1
A0 -->[ decoder ]--> W1 -----+--|-------> OR --> F2
                     W2 -----+--+--(to both ORs)
                     W3 ---------+-------> F1 OR

That is, $W_0, W_2, W_3$ feed the OR gate of $F_1$ and $W_1, W_2$ feed the OR gate of $F_2$. Programming the ROM means keeping exactly these connections and blowing the rest.

Drawbacks of the clocked RS flip-flop

1. Invalid state: when $S = R = 1$ with CLK = 1, both outputs become 1 (or both 0 in a NOR version), violating the condition $Q' = \overline{Q}$. When the clock then falls, the next state is unpredictable.
2. Forbidden input condition: the user must make sure $S$ and $R$ are never 1 together, which restricts its use.
3. No toggle operation: there is no input combination that complements the output, so counters and similar circuits cannot be built directly.
4. Race/indeterminate behaviour: if $S$ and $R$ go from 1,1 to 0,0 at slightly different times the final state is uncertain.

The JK flip-flop removes these problems.

JK flip-flop

A JK flip-flop is a clocked RS flip-flop with feedback: the outputs $Q$ and $Q'$ are fed back to the input gates so that $S = J\cdot Q'$ and $R = K\cdot Q$. The input condition $J = K = 1$ is now allowed and causes the output to toggle.

Circuit diagram

J --[AND3: J, CLK, Q']--- S \
CLK                           [Clocked SR latch] -- Q
K --[AND3: K, CLK, Q ]--- R /                    -- Q'
          ^         ^
          |_________|  Q and Q' fed back

Operation

• $J = 0, K = 0$: no change, $Q(t+1) = Q(t)$.
• $J = 0, K = 1$: reset, $Q(t+1) = 0$.
• $J = 1, K = 0$: set, $Q(t+1) = 1$.
• $J = 1, K = 1$: toggle, $Q(t+1) = Q'(t)$. Because of the feedback the invalid state never occurs.

Characteristic table

Characteristic equation: $Q(t+1) = JQ' + K'Q$.

If the clock pulse is wider than the propagation delay, toggling repeats within one pulse (race-around). It is cured by edge triggering or the master-slave arrangement.

PLA (Programmable Logic Array): A PLA is a programmable logic device with a programmable AND array that generates product terms of the inputs and a programmable OR array that sums selected product terms to form the outputs. Because both arrays are programmable, product terms can be shared between several functions. Its size is given by the number of inputs, product terms and outputs.

Design

$F_1(A,B,C) = \Sigma(3,5,6,7)$, $F_2(A,B,C) = \Sigma(0,2,4,7)$

Simplification

$F_1$: pairs $(3,7) = BC$, $(5,7) = AC$, $(6,7) = AB$.

$F_1 = AB + AC + BC$

$F_2$: pairs $(0,2) = A'C'$, $(0,4) = B'C'$, and minterm 7 $= ABC$.

$F_2 = A'C' + B'C' + ABC$

To reduce the number of product terms, also simplify the complement of $F_1$. $F_1' = \Sigma(0,1,2,4)$:

$F_1' = A'B' + A'C' + B'C'$

Now $F_1'$ and $F_2$ share $A'C'$ and $B'C'$, so only four distinct product terms are needed ($A'B'$, $A'C'$, $B'C'$, $ABC$) instead of six. Output $F_1$ is taken as the complement of this sum (PLA outputs have an XOR gate to select true or complemented form).

PLA program table

In the inputs, 1 = true, 0 = complemented, - = not used. In the output columns, 1 means the product term is connected to that OR gate; (C) means the output is complemented (XOR fuse intact) and (T) means true output.

Thus $F_1 = (P_1 + P_2 + P_3)'$ and $F_2 = P_2 + P_3 + P_4$.

Verification: $P_1+P_2+P_3$ covers $\{0,1\}\cup\{0,2\}\cup\{0,4\} = \{0,1,2,4\}$, whose complement is $\{3,5,6,7\}$, which is $F_1$. $P_2 + P_3 + P_4$ covers $\{0,2\}\cup\{0,4\}\cup\{7\} = \{0,2,4,7\}$, which is $F_2$.

Block structure

A,B,C (true and complement) -> AND array (4 product terms)
-> OR array: F1 gets P1,P2,P3 then XOR(1) -> F1 ; F2 gets P2,P3,P4 then XOR(0) -> F2