Digital Logic

Logic Operations

The three fundamental logic operations are AND, OR, NOT

OR can be built using AND and NOT

NAND and NOR are universal gates

Operation	Logic Equation
AND	$C=A\cdot B$
OR	$C=A+B$
NOT	$B=\bar{A}$
NAND	$C=\overline{A\cdot B}$
NOR	$C=\overline{A+B}$
XOR	$C=A\oplus B=\bar{A}\cdot B+A\cdot \bar{B}$

Combinational logic circuits

• No memory
• Can be fully specified with truth table or logic equation
• Output depends only on current inputs

Multiplexor/De-multiplexor

Multiplexor (or selector, MUX) selects one of the data inputs as output by a control input value

• $2^n$-to-1 multiplexor
  • $2^n$ data inputs
  • n selection inputs
  • a single output

Decoder/Encoder

Decoder (n-to-$2^n$ decoder) has n-bit input and $2^n$ 1-bit outputs, where the output maps the input to a binary form

• n-to-$2^n$ decoder
  • n inputs
  • $2^n$ 1-bit outputs

The output corresponds to the input bit pattern is true while all other outputs are false

• $2^n$-to-n encoder
  • $2^n$ 1-bit inputs
  • n outputs

Adder

• 1-bit half adder
  • $S=A\oplus B$
  • $C=A\cdot B$

2-bit Comparator

Example

Canonical Form

Any Boolean function can be expressed in its two-level representation

• Sum-of-products (SoP) of its 1-minterms
• Product-of-sums (PoS) of its 0-maxterms

Programmable Logic Array (PLA)

A gate-level implementation of the two-level representation

Laws of Boolean Algebra

Exercises

$$\begin{array}{rl}C+\overline{BC}& =C+\bar{B}+\bar{C}\\ & =\bar{B}+1\\ & =1\end{array}$$ $$\begin{array}{rl}\overline{AB}(\bar{A}+B)(\bar{B}+B)& =\overline{AB}(\overline{A}+B)\\ & =(\bar{A}+\bar{B})(\bar{A}+B)\\ & =\bar{A}\bar{A}+\bar{A}B+\bar{B}\bar{A}+\bar{B}B\\ & =\bar{A}+\bar{A}B+\bar{A}\bar{B}\\ & =\bar{A}(1+\bar{B}+\bar{B})\\ & =\bar{A}(1+1)\\ & =\bar{A}\end{array}$$

K-map

• $2^n$ adjacent cells in each group
• Toroid (leftmost adjacent to rightmost, topmost adjacent to bottom cells)
• Larger groups $\to$ fewer inputs to the AND gates
• Fewer groups $\to$ fewer AND gates and fewer inputs to OR gates
• Best group might not be unique

1. Draw the K-map according to the gray code
2. Group adjacent cells with 1

Gray code

Two adjacent cells’ corresponding minterms differ in only one variable

1. 0, 1 (start with 1-bit gray code)
2. 0, 1, 1, 0 (mirror)
3. 00, 01, 11, 10 (add 0/1 to the front of left/right part)
4. 00, 01, 11, 10, 10, 11, 01, 00
5. 000, 001, 011, 010, 110, 111, 101, 100

Sequential Logic Circuits

• Memory
• Output depends on current inputs and value stored in memory (state)

S-R Latches (set-reset latches)

NOR Gates Implementation

Inputs	Inputs	Outputs	Outputs
$S$	$R$	$Q$	$\bar{Q}$
0	0	Latch	Latch
0	1	0	1
1	0	1	0
1	1	Invalid	Invalid

NAND Gates Implementation

Inputs	Inputs	Outputs	Outputs
$\bar{S}$	$\bar{R}$	$Q$	$\bar{Q}$
0	0	Invalid	Invalid
0	1	1	0
1	0	0	1
1	1	Latch	Latch

Gated D-Latch

Clock Implementation

$C$	$D$	$Q$
0	0	Unchanged
0	1	Unchanged
1	0	0
1	1	1

Master-Slave D Flip-Flop

Clock

• Free-running signal with a fixed cycle time
• All state changes occur on a clock edge (rising/falling)

$$f=\frac{1}{T}$$

Register