Fundamentals of Logic Circuit Design

Combinatorial Logic

Logic circuits are electronic circuits processing two-valued signals. Their operations are described by logic functions (Boolean algebra).

Boolean algebra

Laws

$x\wedge y=x\cdot y=xy$
$x\vee y=x+y$

Truth table

Commutative Law

$x\cdot y=y\cdot x$
$x+y=y+x$

Distributive Law

$x\cdot (y+z)=(x\cdot y)+(x\cdot z)$
$x+(y\cdot z)=(x+y)\cdot (x+z)$

Absorptive Law

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

Useful

$x+x=x$
$1=x+\overline{x}$

de Morgan's Laws

$\overline{x}+\overline{y}=\overline{xy}$
$\overline{x}\cdot \overline{y}=\overline{x+y}$

Examples

1

$\overline{A}+\overline{D}+(B+AD)(C+D)$
$=\overline{A}+\overline{D}+BC+BD+AD(C+D)$
$=\overline{A}+\overline{D}+[B+BC]+AD(C+D)$
$=\overline{A}+B+\overline{D}+AD(C+D)$
$=\overline{A}+B+\overline{D}+ADC+AD$
$=[\overline{A}+AD]+B+\overline{D}$
$=\overline{A}+B+D+\overline{D}$
$=\overline{A}+B+1$
$=1$

2

$BC+\overline{B}C\overline{D}+CD$
$=BC+C(\overline{B}\overline{D}+D)$
$=BC+C(\overline{B}+D)$
$=BC+\overline{B}C+CD$
$=C+CD$
$=C$

3

$(B\overline{C}+D)(\overline{B}+C)\overline{D}$
$=B\overline{C}\overline{B}D+B\overline{C}C\overline{D}+D\overline{B}\overline{D}+DC\overline{D}$
$=0+0+0+0$
$=0$

4

$B\overline{C}+D+(\overline{B}+C)\overline{D}$
$=B\overline{C}+D+\overline{B}\overline{D}+C\overline{D}$
$=B\overline{C}+C+\overline{B}\overline{D}+D$
$=B\overline{C}+C+\overline{B}\overline{D}+D$
$=B+C+\overline{B}+D$
$=C+D+1$
$=1$

Basic gates

Typical gates have $2^n$ inputs, so if we want to have 5 inputs, we need to use 8-input gate.
In case of the AND gate, the rest 3 inputs need to be connected to 1

Algebraic manipulation of expressions can lead to the reduction of the circuit size

NOT and OR are the most basic gates
we can create any possible circuit using only NAND gates, or NOR gates.

Useful expressions:
$\overline{\stackrel{―}{a\overline{b}+c}}=\overline{\stackrel{―}{a\overline{b}}\cdot \stackrel{―}{c}}$
$\overline{\stackrel{―}{(a+\stackrel{―}{b})\cdot c}}=\overline{\stackrel{―}{(a+\stackrel{―}{b})}+\stackrel{―}{c}}\leftarrow$ very popular in current designs

Logic function minimalization

Gray's Code

The idea of Gray's code is that the consecutive states differ only by one bit, not the value of the bits

3 bit
000
001
011
010
110
111
101
100

4 bits
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

General idea of absorption law is that it works on pairs only.
But we can technically make it work on bigger sets.

Karnaugh tables

Sum of products

Top row and left column contain inputs, and middle of the table contains every possible output.

How to solve - Sum of Products

We're interested in which inputs give ur output 1
We circle 1's together (groups of 2, 4, 8...)
Those groups can be in line, in a square, or made by 'jumping' from one edge of another (think like snake game)
Then, we check which inputs change on those outputs, and we eliminate them, so we're left only with static inputs for given outputs

So for the top right 'island' - B changes, A, C and D are static.
Now, we write AND of all those inputs, so for our island it will be $\overline{A}C\overline{D}$
For most-left island - $AB\overline{C}$
Bottom island - $A\overline{B}D$
So the whole output function will be $Y=\overline{A}C\overline{D}+AB\overline{C}+A\overline{B}D$

To remember

Sometimes, we don't need all outputs that we have available (explained in the beginning of Basic gates)
In that case, we put '-' instead of a output in the Karnaugh table. This is called a DONTCARE

When solving K-maps, when we circle DONTCARE, it gets turned
into 1, if not - into 0.
Thanks to that, DONTCAREs can be used like 'blanks' in scrabble

Product of sums

Quine McCluskey method

Computer software way of solving boolean algebra

Static hazards

A static hazard it present for two neighboring 1's that aren't in the same minterms

When transitioning from a state 110 into 010

But to correctly show the steps, we need to split the diagram into stages.

When switching from 110 to 010, the top AND gate gets updated at the same time as bottom NOT gates, but because the bottom signal has to travel also through an AND gates, the final OR gets a split moment signal, where the top input is already updated, but the bottom didn't catch up yet. This is called a static hazard.

Fix

To fix the hazard, we can find the edge on the K-map that creates the problem and create a minterm from the 1's. This introduces a new part of the circuit that ensured the proper functioning of the whole circuit.

K-map

Updated circuit