Digital Logic

Convert $(257)_8$.

To hexadecimal: convert each octal digit to 3 bits, regroup into 4 bits.

$2 = 010,\quad 5 = 101,\quad 7 = 111$

$(257)_8 = (010\,101\,111)_2 = (0\,1010\,1111)_2$

Grouping in fours from the right: $0000\ 1010\ 1111 = (0AF)_{16}$.

$(257)_8 = (AF)_{16}$

To decimal

$2 \times 8^2 + 5 \times 8^1 + 7 \times 8^0 = 128 + 40 + 7 = 175$

$(257)_8 = (175)_{10}$

Check: $(AF)_{16} = 10 \times 16 + 15 = 175$.

Half-subtractor

A half-subtractor is a combinational circuit that subtracts two single bits, $A - B$, and produces two outputs: the difference $D$ and the borrow $B_o$ (borrow needed from the next higher bit). It has no borrow input, which is why it is "half".

Truth table

(For $0-1$: the result is 1 with a borrow of 1.)

Boolean expressions

$D = A'B + AB' = A\oplus B$

$B_o = A'B$

Logic diagram

A ---+-------------[XOR]------------> D = A xor B
     |               ^
B ---|---+-----------+
     |   |
     +-[NOT]--+
         |    +--[AND]-------------> Bo = A'.B
B -------+----------^

That is: one XOR gate gives $D$; $A$ is inverted by a NOT gate and ANDed with $B$ to give $B_o$.

Convert $(51966.57)_{10}$ to octal and hexadecimal.

Integer part 51966

Hexadecimal (divide by 16):

Reading upward: $CAFE_{16}$.

Octal (divide by 8):

Reading upward: $145376_8$.

Fraction part 0.57

Multiply by 16 repeatedly:

• $0.57\times16 = 9.12 \to 9$
• $0.12\times16 = 1.92 \to 1$
• $0.92\times16 = 14.72 \to E$
• $0.72\times16 = 11.52 \to B$
• $0.52\times16 = 8.32 \to 8$

Hex fraction $\approx .91EB8$ (it does not terminate).

Multiply by 8 repeatedly:

• $0.57\times8 = 4.56 \to 4$
• $0.56\times8 = 4.48 \to 4$
• $0.48\times8 = 3.84 \to 3$
• $0.84\times8 = 6.72 \to 6$
• $0.72\times8 = 5.76 \to 5$
• $0.76\times8 = 6.08 \to 6$

Octal fraction $\approx .443656$.

Result

$(51966.57)_{10} \approx (145376.443656)_8 \approx (CAFE.91EB8)_{16}$

Check: $CAFE_{16}$ in binary is $1100\,1010\,1111\,1110$; regrouping in threes gives $1\,100\,101\,011\,111\,110 = 145376_8$.

Convert $(110.101)_8$.

To binary (each octal digit becomes 3 bits)

• Integer: $1 = 001,\ 1 = 001,\ 0 = 000$ giving $001\,001\,000 = 1001000$.
• Fraction: $1 = 001,\ 0 = 000,\ 1 = 001$ giving $.001\,000\,001$.

$(110.101)_8 = (1001000.001000001)_2$

To decimal

Integer part: $1\cdot8^2 + 1\cdot8^1 + 0\cdot8^0 = 64+8+0 = 72$.

Fraction part: $1\cdot8^{-1} + 0\cdot8^{-2} + 1\cdot8^{-3} = 0.125 + 0 + 0.001953125 = 0.126953125$.

$(110.101)_8 = (72.126953125)_{10}$

Check from binary: $1001000_2 = 64+8 = 72$ and $.001000001_2 = 2^{-3}+2^{-9} = 0.125+0.001953125$, which agrees.

Magnitude comparator

A magnitude comparator is a combinational circuit that compares two binary numbers $A$ and $B$ and gives three outputs: $A>B$, $A=B$ and $A<B$, exactly one of which is 1.

2-bit comparator design

Let $A=A_1A_0$ and $B=B_1B_0$. There are 4 inputs, so 16 rows in the truth table:

Equations

$A=B$ when both bit pairs are equal. Let $x_i = A_i\odot B_i = A_iB_i + A_i'B_i'$ (XNOR).

$(A=B) = x_1 x_0$

$A>B$ when the MSB of $A$ is larger, or the MSBs are equal and the LSB of $A$ is larger:

$(A>B) = A_1B_1' + x_1 A_0B_0'$

$A<B$ similarly:

$(A<B) = A_1'B_1 + x_1 A_0'B_0$

Circuit. Two XNOR gates give $x_1,x_0$; a 2-input AND gives $A=B$. For $A>B$: AND gates $A_1B_1'$ and $x_1A_0B_0'$ feed an OR gate. For $A<B$: AND gates $A_1'B_1$ and $x_1A_0'B_0$ feed an OR gate. NOT gates provide the complements of the inputs.

Check: $A=10,B=01$: $A_1B_1'=1$, so $A>B=1$; $x_1=0$ so $A=B=0$; $A_1'B_1=0$ and $x_1\cdot(\ldots)=0$ so $A<B=0$. Correct.

A 4-bit PIPO shift register consists of four D flip-flops with a common clock. Each flip-flop has its own data input ($A, B, C, D$) and its own output ($Q_A, Q_B, Q_C, Q_D$).

 A=1   B=0   C=1   D=0     (data input 1010)
  |     |     |     |
[FF_A][FF_B][FF_C][FF_D] <- common CLK
  |     |     |     |
 Q_A   Q_B   Q_C   Q_D

Operation with data 1010

1. Before the clock pulse, the register holds an old value (say 0000) and the parallel inputs are set to $A=1, B=0, C=1, D=0$.
2. At the active clock edge, each flip-flop copies its input: $Q_A = 1$, $Q_B = 0$, $Q_C = 1$, $Q_D = 0$.
3. The register now holds 1010 and all four bits appear at the outputs at the same time, in a single clock pulse. The data stays stored until the next clock edge or until it is cleared.

No shifting is involved between the stages. A clear input can reset all flip-flops to 0.

Magnitude comparator: a combinational circuit that compares two binary numbers $A$ and $B$ and indicates whether $A > B$, $A = B$ or $A < B$ using three outputs.

4-bit comparator design: let $A = A_3A_2A_1A_0$ and $B = B_3B_2B_1B_0$.

Step 1: bit equality (XNOR gates)

$x_i = A_i \odot B_i = A_iB_i + A_i'B_i' \quad (i = 0,1,2,3)$

Step 2: outputs

$(A = B) = x_3x_2x_1x_0$

$(A > B) = A_3B_3' + x_3A_2B_2' + x_3x_2A_1B_1' + x_3x_2x_1A_0B_0'$

$(A < B) = A_3'B_3 + x_3A_2'B_2 + x_3x_2A_1'B_1 + x_3x_2x_1A_0'B_0$

Reasoning: comparison starts at the MSB. If $A_3 > B_3$ then $A > B$. If the MSBs are equal ($x_3 = 1$), the next bits are compared, and so on. The numbers are equal only if all four bit pairs are equal.

Logic diagram

A3 B3 -> XNOR -> x3 --+
A2 B2 -> XNOR -> x2 --+--> AND4 ---------------------> A = B
A1 B1 -> XNOR -> x1 --+
A0 B0 -> XNOR -> x0 --+

A>B : 4 AND terms (with NOT on B_i) -> OR4 -> A > B
A<B : 4 AND terms (with NOT on A_i) -> OR4 -> A < B

The circuit needs 4 XNOR gates, a few NOT gates, AND gates (of 2, 3, 4, 5 inputs) and two 4-input OR gates. (The IC 7485 is a standard 4-bit comparator.) For example, $A = 1011$, $B = 1001$: $x_3 = 1$, $x_2 = 1$, $x_1 = 0$, so $A > B$ through the term $x_3x_2A_1B_1' = 1$.

Shift register: a sequential circuit made of a group of cascaded flip-flops, sharing a common clock, used to store binary data and shift it left or right by one position on each clock pulse.

4-bit SISO shift register (four D flip-flops)

Serial   +----+   +----+   +----+   +----+
 in ---->| FF3|-->| FF2|-->| FF1|-->| FF0|----> Serial out
         +----+   +----+   +----+   +----+
CLK common to all

Operation with input 1011 (the bits are entered LSB first: 1, 1, 0, 1; the register initially holds 0000, outputs shown as $Q_3Q_2Q_1Q_0$)

After 4 clock pulses the register holds 1011 (the word is loaded). For serial output, four more pulses (with 0 input) shift the data out at $Q_0$ in the order 1, 1, 0, 1 (first bit entered, first out).

At each pulse every flip-flop takes the value of the one before it, so data moves one position per pulse.

Decoder

A decoder is a combinational circuit that converts an $n$-bit binary input code into up to $2^n$ unique output lines, activating exactly one output for each input combination.

BCD to decimal decoder (4-line to 10-line)

Inputs are the BCD digits $A, B, C, D$ ($A$ = MSB); outputs are $D_0$ to $D_9$. Input combinations 1010 to 1111 are invalid and produce no output (don't-care).

Truth table:

Boolean expressions (using don't-cares to simplify):

$D_0 = A'B'C'D',\quad D_1 = A'B'C'D,\quad D_2 = B'CD',\quad D_3 = B'CD,\quad D_4 = BC'D'$ $D_5 = BC'D,\quad D_6 = BCD',\quad D_7 = BCD,\quad D_8 = AD',\quad D_9 = AD$

(Without don't-cares, each output is the full 4-input AND of the minterm, e.g. $D_8 = AB'C'D'$.)

Logic diagram: four inputs $A,B,C,D$ and their complements $A',B',C',D'$ feed ten AND gates, one per output. Each AND gate takes the literals shown in its expression above (4-input AND gates for $D_0, D_1$, 3-input for $D_2$ to $D_7$, 2-input for $D_8, D_9$); the output of the gate matching the input code goes to 1 and all others stay 0.

Let the input be $A_3A_2A_1A_0$ and the output $Y_3Y_2Y_1Y_0$, where $Y$ is the 2's complement of $A$ (invert all bits and add 1).

Truth table:

Simplifying with K-maps (or by the rule "copy bits up to and including the first 1 from the right, then invert the rest"):

$Y_0 = A_0$ $Y_1 = A_1 \oplus A_0$ $Y_2 = A_2 \oplus (A_1 + A_0)$ $Y_3 = A_3 \oplus (A_2 + A_1 + A_0)$

Check: $A = 0110$: $Y_0=0$, $Y_1 = 1\oplus 0 = 1$, $Y_2 = 1 \oplus 1 = 0$, $Y_3 = 0 \oplus 1 = 1$, so $Y = 1010$. Correct.

Logic diagram: $Y_0$ is a direct wire from $A_0$; one XOR gate gives $Y_1$; one OR gate plus one XOR gives $Y_2$; a 3-input OR (or two 2-input ORs) plus one XOR gives $Y_3$.

Ring counter

A ring counter is a circular shift register in which the output of the last flip-flop is fed back to the input of the first. It is initialised so that a single 1 (the others 0) circulates around the register with each clock pulse. An $n$-bit ring counter has $n$ states (modulus $n$) and uses $n$ flip-flops.

Diagram (4-bit, using D flip-flops)

 +-----------------------------------------------+
 |                                               |
 +--> D Q0 --> D Q1 --> D Q2 --> D Q3 ----------+
      FF0       FF1       FF2       FF3
       ^         ^         ^         ^
 CLK --+---------+---------+---------+

All four flip-flops share the same clock. The $Q$ output of each flip-flop feeds the $D$ input of the next, and $Q_3$ feeds back to $D_0$. A preset pulse sets $Q_0=1$ and clears the others, giving the initial state 1000.

Timing (state) sequence

After 4 pulses the sequence repeats.

Timing diagram

CLK : _|-|_|-|_|-|_|-|_|-|_
Q0  : ---|_______|-------|__
Q1  : ___|-------|_______|--
Q2  : _______|-------|_______
Q3  : ___________|-------|___

Each output is high for exactly one clock period, and the high level moves from $Q_0$ to $Q_3$ in turn, so the outputs act as sequential timing pulses. Uses: sequence generators, control timing signals, and frequency division by $n$.

Binary to decimal

$(1011.110)_2 = 1\times2^3 + 0\times2^2 + 1\times2^1 + 1\times2^0 + 1\times2^{-1} + 1\times2^{-2} + 0\times2^{-3}$ $= 8 + 0 + 2 + 1 + 0.5 + 0.25 + 0 = 11.75$

So $(1011.110)_2 = (11.75)_{10}$.

Binary to hexadecimal

Group in fours from the binary point: integer part $1011$, fractional part $1100$ (pad with a zero on the right).

$1011 = B,\qquad 1100 = C$

So $(1011.110)_2 = (B.C)_{16}$.

Compute $1010.10 - 1011.11$ (that is $10.5 - 11.75 = -1.25$).

Using 1's complement

1's complement of the subtrahend $1011.11$ is $0100.00$.

$1010.10 + 0100.00 = 1110.10$

There is no end-around carry, so the result is negative and is the 1's complement of the sum:

$-(0001.01) = -1.25$

Using 2's complement

2's complement of $1011.11$ = $0100.00 + 0000.01 = 0100.01$.

$1010.10 + 0100.01 = 1110.11$

There is no carry out, so the result is negative; take the 2's complement of the sum: $0001.00 + 0000.01 = 0001.01$.

Result: $-(0001.01)_2 = -1.25_{10}$.

A minterm is a product (AND) term containing every variable of the function once, in complemented or uncomplemented form. A function in sum-of-minterms form is the OR of the minterms for which the function equals 1, written as $\Sigma m(\ldots)$.

Method: make a truth table (or expand each product term by ANDing the missing variables with $(x + x')$) and list the rows where $F = 1$.

Example: Express $F(A,B,C) = A + B'C$ as a sum of minterms.

Expand the first term: $A = A(B + B')(C + C') = ABC + ABC' + AB'C + AB'C'$.

Expand the second term: $B'C = B'C(A + A') = AB'C + A'B'C$.

Combining and removing the duplicate $AB'C$:

$F = A'B'C + AB'C' + AB'C + ABC' + ABC$ $F = m_1 + m_4 + m_5 + m_6 + m_7 = \Sigma m(1,4,5,6,7)$

Check using the truth table: $F=1$ for $ABC$ = 001, 100, 101, 110, 111, which are exactly these minterms.

Example: $F(A,B,C,D) = \Sigma m(1,3,7,11,15)$ with don't-care conditions $d(0,2,5)$.

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

SOP (group the 1s, using X where useful)

• Quad $m_0, m_1, m_3, m_2$ (top row) gives $A'B'$.
• Quad $m_3, m_7, m_{15}, m_{11}$ (column $CD=11$) gives $CD$.

$F = A'B' + CD$

POS (group the 0s, using X where useful)

Zeros are $m_4, m_6, m_8, m_9, m_{10}, m_{12}, m_{13}, m_{14}$.

• $m_4, m_6, m_{12}, m_{14}$ gives $BD'$.
• $m_8, m_9, m_{12}, m_{13}$ gives $AC'$.
• $m_8, m_{10}, m_{12}, m_{14}$ gives $AD'$.

$F' = BD' + AC' + AD'$

Complementing with De Morgan's theorem:

$F = (B' + D)(A' + C)(A' + D)$

Both forms realise the same function on the required minterms (they may differ only on the don't-care entries).

Half subtractor (HS)

Inputs $x, y$; outputs Difference $D = x \oplus y$ and Borrow $B = x'y$.

Full subtractor

Inputs $x$, $y$ and borrow-in $B_{in}$:

$D = x \oplus y \oplus B_{in}$ $B_{out} = x'y + (x \oplus y)'B_{in}$

Implementation using two half subtractors and an OR gate

• HS1 takes $x$ and $y$: gives $D_1 = x \oplus y$ and $B_1 = x'y$.
• HS2 takes $D_1$ and $B_{in}$: gives $D = D_1 \oplus B_{in}$ (final difference) and $B_2 = D_1' B_{in}$.
• An OR gate combines the two borrows: $B_{out} = B_1 + B_2$.

x --+--[ HS1 ]-- D1 --[ HS2 ]-- D (difference)
y --+      |            |  ^
           B1           B2 |
Bin ----------------------+
           \             /
            +-- OR ----+--> Bout

Verification: $B_{out} = x'y + (x\oplus y)'B_{in}$, which is the full-subtractor borrow expression, so the circuit is correct.

Truth table check (x y Bin -> D Bout): 000->00, 001->11, 010->11, 011->10, 100->10, 101->01, 110->00, 111->11.

SR latch

An SR (Set-Reset) latch is a basic 1-bit memory element with two inputs, S (set) and R (reset), and two complementary outputs $Q$ and $Q'$. It can be built from two cross-coupled NOR gates (active-high inputs) or two cross-coupled NAND gates (active-low inputs).

Logic diagram (NOR latch)

R ----+----------|\\
      |    NOR1  | )o---- Q
      |      +---|//
      |      |
      |      +-------+
      |              |
      |      +-------+
      |      |
S ----+---------|\\
           NOR2 | )o---- Q'
         Q ----|//

The output of each NOR gate is fed back to an input of the other: $Q = (R + Q')'$ and $Q' = (S + Q)'$.

Truth table (NOR latch)

With S = R = 1 both outputs are 0 and the final state is unpredictable when both inputs return to 0, so this input is avoided. For the NAND latch the inputs are active-low, so S = R = 0 is the invalid case.

Both are binary counters built from flip-flops, but they differ in how the clock reaches the flip-flops.

Ripple (asynchronous) counter

Only the first flip-flop receives the external clock. The output of each flip-flop drives the clock input of the next one, so the change ripples through the chain. For a 3-bit up counter with T (or JK with $J=K=1$) flip-flops:

CLK --> [FF0] Q0 --> [FF1] Q1 --> [FF2] Q2

Synchronous counter

All flip-flops receive the same clock at the same instant. Each flip-flop's J/K (or T) input is driven by combinational logic on the present outputs, so a flip-flop toggles only when the logic enables it. For a 3-bit up counter:

$T_0 = 1,\qquad T_1 = Q_0,\qquad T_2 = Q_1 Q_0$

CLK --+----------+----------+
      v          v          v
    [FF0]      [FF1]      [FF2]
   T0=1      T1=Q0     T2=Q1.Q0

Comparison

Shift register

A shift register is a sequential circuit made of a cascade of flip-flops, usually D flip-flops, sharing a common clock. Each flip-flop output is connected to the input of the next, so on every clock pulse the stored binary word moves one position left or right. An $n$-bit register stores $n$ bits. It is used for temporary storage, serial-to-parallel and parallel-to-serial conversion, delay, and in counters and arithmetic circuits (multiplication by 2 and division by 2).

Types (by the way data enters and leaves)

1. Serial-In Serial-Out (SISO): Data enters one bit at a time at the first flip-flop and leaves one bit at a time from the last. A 4-bit word needs 4 clock pulses to load and 4 more to read. It acts as a delay line.

Din --> [D FF0] --> [D FF1] --> [D FF2] --> [D FF3] --> Dout
           ^           ^           ^           ^
           +-----------+-----CLK---+-----------+

2. Serial-In Parallel-Out (SIPO): Data is loaded serially, and after $n$ clock pulses all flip-flop outputs $Q_0\ldots Q_{n-1}$ are available together. Used for serial-to-parallel conversion.

3. Parallel-In Serial-Out (PISO): All $n$ bits are loaded at once through a SHIFT/LOAD control (a 2-to-1 selector in front of each flip-flop), then shifted out serially. Used for parallel-to-serial conversion (transmitters).

4. Parallel-In Parallel-Out (PIPO): All bits are loaded together and all are available together after one clock pulse. It is a simple storage register and is the fastest type.

Other types by direction and function

• Unidirectional: shifts only left or only right.
• Bidirectional: shifts left or right under a mode control.
• Universal shift register: has parallel load, shift left, shift right and hold modes (for example the IC 74194).
• Ring counter: the last output is fed back to the first input; a single 1 circulates, giving $n$ states.
• Johnson (twisted-ring) counter: the complement of the last output is fed back, giving $2n$ states.

(a) Parity generator

A parity generator is a combinational circuit that adds one extra bit (the parity bit) to a data word so that the total number of 1s becomes even (even parity) or odd (odd parity). The receiver uses a parity checker to detect any single-bit error during transmission.

For a 3-bit message $A\,B\,C$ with even parity bit $P$, $P$ must make the number of 1s even, so $P = 1$ when the message has an odd number of 1s:

$P = A \oplus B \oplus C$

It is implemented with two XOR gates: $(A\oplus B)\oplus C$. For odd parity the output is inverted, $P = (A\oplus B\oplus C)'$. The 4-bit even-parity checker at the receiver computes $E = A\oplus B\oplus C\oplus P$; $E=1$ indicates an error.

(b) State diagram

A state diagram is a graphical description of a sequential circuit. Each state (the contents of the flip-flops) is drawn as a circle labelled with its binary code. A directed arrow from one circle to another shows a transition on a clock pulse and is labelled with the input that causes it (and, for a Mealy machine, the output as input/output; for a Moore machine the output is written inside the circle).

Example: a 2-bit up counter with one enable input $x$:

         x=1               x=1               x=1               x=1
  (00) -------> (01) -------> (10) -------> (11) -------> (00)
   ^ |x=0        ^ |x=0        ^ |x=0        ^ |x=0
   +-+           +-+           +-+           +-+

State diagrams are first converted to a state table, then to excitation tables for the chosen flip-flops, and finally simplified with K-maps to obtain the circuit.

Step 1: Truth table. Let the inputs be $A, B, C, D$ and the output $F$.

• (i) all inputs 1: minterm 15 (1111)
• (ii) no input is 1: minterm 0 (0000)
• (iii) odd number of 1s: minterms 1, 2, 4, 7, 8, 11, 13, 14

$F(A,B,C,D)=\Sigma(0,1,2,4,7,8,11,13,14,15)$

Step 2: Simplification. The ten minterms contain the eight odd-parity minterms, which form a checkerboard pattern on the K-map. No two of them are adjacent, so they cannot be grouped into larger SOP terms. The function is therefore best expressed using the XOR (parity) function plus the two extra minterms:

$F = (A\oplus B\oplus C\oplus D) + ABCD + A'B'C'D'$

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

Step 3: Circuit.

• Three 2-input XOR gates: $X_1=A\oplus B$, $X_2=C\oplus D$, $X_3=X_1\oplus X_2$ (odd parity detector).
• One 4-input AND gate for $ABCD$ (all inputs 1).
• One 4-input NOR gate for $A'B'C'D'$ (no input is 1).
• One 3-input OR gate combining $X_3$, the AND output and the NOR output to give $F$.

A --+--[XOR]--+
B --+         +--[XOR]--------+
C --+--[XOR]--+                |
D --+                          +--[OR]--> F
A,B,C,D ---[AND4]--------------+
A,B,C,D ---[NOR4]--------------+

Check: $0000$ gives NOR $=1$; $1111$ gives AND $=1$; $0111$ has three 1s so XOR $=1$; $0011$ has two 1s, XOR $=0$, AND $=0$, NOR $=0$ so $F=0$. All agree with the table.

$F(A,B,C,D)=\Sigma(0,1,3,4,5,8,9,10,15)$

(i) Using a decoder

Use a $4\times16$ decoder with $A$ as MSB and $D$ as LSB. Its outputs $m_0\ldots m_{15}$ are the minterms. Connect the outputs $m_0,m_1,m_3,m_4,m_5,m_8,m_9,m_{10},m_{15}$ to a 9-input OR gate:

$F = m_0+m_1+m_3+m_4+m_5+m_8+m_9+m_{10}+m_{15}$

(If the decoder has active-low outputs, use a 9-input NAND gate instead.)

A B C D --> [4x16 DECODER] --> m0,m1,m3,m4,m5,m8,m9,m10,m15 --> [OR] --> F

(ii) Using a multiplexer

Use an $8\times1$ MUX with $A,B,C$ as select lines ($S_2S_1S_0$) and $D$ as the data variable. For each $ABC$, look at the pair of minterms $(2k, 2k+1)$:

Connections: $I_0=I_2=I_4=1$, $I_3=I_6=0$, $I_1=I_7=D$, $I_5=D'$ (through a NOT gate); select lines $S_2=A,\ S_1=B,\ S_0=C$; output $=F$.

(iii) Using a PLA

First minimise with a K-map (rows $AB$, columns $CD$):

Groups: $B'C'$ (0,1,8,9), $A'C'$ (0,1,4,5), $A'B'D$ (1,3), $AB'D'$ (8,10), $ABCD$ (15).

$F = B'C' + A'C' + A'B'D + AB'D' + ABCD$

PLA program table (4 inputs, 5 product terms, 1 output; the AND plane is programmed with 1 = true input, 0 = complemented input, - = not connected):

The AND plane generates the five product terms from the inputs and their complements; the OR plane connects all five products to the single output $F$.

Race condition in a JK flip-flop

In a level-triggered JK flip-flop with $J=K=1$, the output toggles while the clock is high. If the clock pulse width $t_p$ is longer than the propagation delay $t_{pd}$ of the gates, the toggled output is fed back to the inputs and the flip-flop toggles again and again during the same pulse. At the end of the pulse the output is unpredictable. This uncontrolled oscillation is the race-around condition.

Methods to overcome it

1. Use edge triggering, so the flip-flop responds only at the rising or falling edge and the output changes once per clock.
2. Use a master-slave configuration (described below).
3. Make the clock pulse narrower than the propagation delay ($t_p < t_{pd}$), which is difficult to guarantee in practice.

Master-slave JK flip-flop

It consists of two JK (or SR) latches in cascade: the master and the slave. The master is clocked by CLK and the slave by the inverted clock $\overline{CLK}$. The outputs of the slave $Q, Q'$ are fed back to the master's gates.

J --+                                      +-------------------+
    |   +---------+  Qm      +---------+   |                   |
    +-->|  MASTER |--------->|  SLAVE  |---+--> Q              |
K --+-->| (CLK)   |--Qm'---->| (CLK')  |------> Q'             |
    |   +----^----+          +----^----+                       |
    |        |                    |                            |
    |       CLK                [NOT]<--CLK                     |
    +-- feedback of Q and Q' to the master input gates --------+

Operation

• CLK = 1: the master is enabled and takes the values of $J$, $K$ (using $Q$, $Q'$); the slave is disabled, so $Q$ does not change.
• CLK goes 1 to 0: the master is disabled (its inputs are locked), and the slave is enabled and copies the master's output. $Q$ changes only now.
• CLK = 0: the master is disabled, so new $J,K$ values have no effect.

Because the feedback to the master is blocked whenever the slave is open, the output changes only once per clock cycle and there is no race.

Truth table (output after the falling edge of CLK)

Timing diagram (for $J=K=1$, so the flip-flop toggles)

CLK   __|""|__|""|__|""|__|""|__
Qm    __|"""""|_____|"""""|_____   (master follows while CLK=1)
Q     ____|"""""""""|_________|    (changes only at falling edge of CLK)

The output $Q$ toggles once at each falling clock edge, giving a frequency of half the clock.

Convert $(1011.110)_2$.

To decimal

Integer part: $1011_2 = 1\cdot 8 + 0\cdot 4 + 1\cdot 2 + 1\cdot 1 = 11$.

Fraction part: $.110_2 = 1\cdot 2^{-1} + 1\cdot 2^{-2} + 0\cdot 2^{-3} = 0.5 + 0.25 = 0.75$.

$(1011.110)_2 = (11.75)_{10}$

To hexadecimal

Group the bits in fours outward from the binary point, padding with zeros: integer $1011$; fraction $.1100$ (a 0 is added on the right).

• $1011 = B$
• $1100 = C$

$(1011.110)_2 = (B.C)_{16}$

Check: $B.C_{16} = 11 + 12/16 = 11.75$.

Subtract $(111000.110)_2 - (110100.101)_2$.

Check in decimal: $56.75 - 52.625 = 4.125$, which is $100.001_2$.

Let $M = 111000.110$ and $N = 110100.101$.

(a) Using 2's complement

1's complement of $N$: $001011.010$.

2's complement of $N$: add 1 at the last place: $001011.010 + 000000.001 = 001011.011$.

Add to $M$:

  111000.110
+ 001011.011
------------
 1000100.001

There is a carry out of the MSB, so the result is positive; discard the carry.

$M - N = 000100.001 = (100.001)_2$

(b) Using 1's complement

1's complement of $N$: $001011.010$.

Add to $M$:

  111000.110
+ 001011.010
------------
 1000100.000

There is a carry out of the MSB (end-around carry). Add it to the least significant bit:

  000100.000
+ 000000.001
------------
  000100.001

$M - N = (100.001)_2$

Both methods give $(100.001)_2 = 4.125_{10}$, which matches the decimal check.

De Morgan's theorems

Theorem 1: The complement of a sum equals the product of the complements.

$\overline{A+B} = \overline{A}\cdot\overline{B}$

Theorem 2: The complement of a product equals the sum of the complements.

$\overline{A\cdot B} = \overline{A}+\overline{B}$

(They extend to any number of variables: $\overline{A+B+C+\cdots}=\overline A\,\overline B\,\overline C\cdots$ and $\overline{ABC\cdots}=\overline A+\overline B+\overline C+\cdots$.)

Proof by truth table

The columns $\overline{A+B}$ and $\overline A\,\overline B$ are identical, and the columns $\overline{AB}$ and $\overline A+\overline B$ are identical, so both theorems hold for all input combinations.

Algebraic proof (Theorem 1)

The complement $X'$ of $X$ is the unique element satisfying $X+X'=1$ and $X\cdot X'=0$. Show that $\overline A\,\overline B$ is the complement of $A+B$.

$(A+B)+\overline A\,\overline B = (A+B+\overline A)(A+B+\overline B) = (1+B)(1+A) = 1$

$(A+B)\cdot\overline A\,\overline B = A\overline A\,\overline B + B\overline A\,\overline B = 0 + 0 = 0$

Both conditions are satisfied, so $\overline{A+B}=\overline A\,\overline B$.

Algebraic proof (Theorem 2)

$AB+(\overline A+\overline B) = (A+\overline A+\overline B)(B+\overline A+\overline B) = 1\cdot1 = 1$

$AB\cdot(\overline A+\overline B) = AB\overline A + AB\overline B = 0+0=0$

Hence $\overline A+\overline B$ is the complement of $AB$, i.e. $\overline{AB}=\overline A+\overline B$.

Applying the theorems turns an AND into an OR (and vice versa) with complemented inputs, so NAND and NOR gates can implement any logic function.

Decoder

A decoder is a combinational circuit that converts an $n$-bit binary code on its inputs into a unique active output among $2^n$ output lines. Exactly one output is 1 (active-high) for each input combination, so each output is a minterm of the inputs. Examples: $2\times4$, $3\times8$ and $4\times16$ decoders; each usually has an enable input. A $3\times8$ decoder has outputs $D_i =$ minterm $m_i$ of $A_2A_1A_0$. Uses: address decoding, memory chip selection, code conversion, and implementing Boolean functions.

$8\times1$ MUX using $4\times1$ MUX

An $8\times1$ MUX has 8 data inputs $I_0\ldots I_7$, three select lines $S_2S_1S_0$ and one output $Y$. Three $4\times1$ MUXes are used in two stages:

• MUX1 takes $I_0,I_1,I_2,I_3$ with selects $S_1,S_0$. Output $Y_1$.
• MUX2 takes $I_4,I_5,I_6,I_7$ with selects $S_1,S_0$. Output $Y_2$.
• MUX3 takes $Y_1$ on input 0 and $Y_2$ on input 1 (inputs 2 and 3 are unused, connected to 0), with select lines $S_0 = S_2$ and $S_1 = 0$. Its output is $Y$.

I0..I3 --> [4x1 MUX1] --Y1--> in0 +------------+
            S1 S0                   | 4x1 MUX3   |--> Y
I4..I7 --> [4x1 MUX2] --Y2--> in1  | S0=S2,S1=0 |
            S1 S0                   +------------+

When $S_2=0$ MUX3 passes $Y_1$ (one of $I_0$-$I_3$); when $S_2=1$ it passes $Y_2$ (one of $I_4$-$I_7$). So $Y=I_{S_2S_1S_0}$ as required.