Kyungbaek Kim

Terminology • Analog circuits • Digital circuits – Signal values restricted to a few discrete values – Binary logic circuits : two values, 0 and 1 • Why do we use the binary circuit??

– Multi-valued logic • More than two values • Some flash devices use multi-valued data storage – Multi-level cell (MLC) : capable of storing 2 bits of data per cell

• Not covered in this class

Binary Logic

Binary Switch : an example of Binary logic Open

Closed

Input

Binary Logic

Application of a switch • Light • Status of the light – L=1 if the light is on – L=0 if the light is off

• Logic function – L can be described as a function of the input x – L(x) = x

Binary Logic

Basic Logic Function (1/2) : AND • Series Connection • L(x1,x2) = x1•x2 where L=1 if x1=1 and x2=1, L=0 otherwise

Binary Logic

Basic Logic Function (2/2) : OR • Parallel Connection • L(x1,x2)=x1+x2 where L=0 if x1=0 and x2=0, L=1 otherwise

Binary Logic

Series-Parallel Connection

• L(x1,x2,x3)=?

(x1+x2) •x3

Binary Logic

Inversion • Inverse function – If x=0, L=1 – If x=1, L=0

Binary Logic

Complement : NOT • Inversion – Inverse of a value – Complement of a value – NOT operation

• L(x) = x = x’ = !x = NOT x = ~x • Complement (NOT) operation can be applied to more complex operations – f’(x1,x2) = (x1+x2)’

Truth Table

Truth Tables; AND and OR • Alternative description of a logic function for combinational circuits

All Possible combinations of Inputs

Each of Valuation

Truth Table

Three input AND and OR • 2 inputs 4 combinations (2^2) • 3 inputs 8 combinations (2^3) • 4 inputs ??

2^4 = 16

Table Size with n inputs = 2^n

Logic Gate and Network

Logic gates and networks • The Three basic functions (AND, OR, and NOT) can be combined to form logic functions of any complexity • Logic Gates – They can be represented by symbols

• A circuit diagram or a schematic – A combination of logic gate symbols in a drawing – Larger circuit uses a network of gates

Logic Gate and Network

Basic Logic Gate Symbols

Others : NAND, NOR, XOR, Buffer

Logic Gate and Network

Not gate Truth Table A

F

0

1

1

0

Wavelet In A

1

0

Logic Symbol 1

0

A Out F

0

1

0

F

1

Logic Equation F A A'

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

AND gate Truth Table A

B

F

0

0

0

0

1

0

1

0

0

1

1

1

Wavelet

Logic Symbol

A

0

0

1

1

0

B

0

1

0

1

0

F

0

0

0

1

0

A B

F

Logic Equation

F AB A B

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

3 input AND gate Truth Table A

B

C

F

0

0

0

0

0

0

1

0

Wavelet A

0 0 0 0 1 1 1 1 0

B

0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0

0

1

0

0

C

0

1

1

0

F

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

Logic Equation

F ABC A B C Logic Symbol A B C

F

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

OR gate Truth Table A

B

F

0

0

0

0

1

1

1

0

1

1

1

1

Wavelet

Logic Equation

A

0

0

1

1

0

B

0

1

0

1

0

F

0

1

1

1

0

F A B Logic Symbol A B

F

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

3 Input OR gate Truth Table A

B

C

Wavelet

F A

0 0 0 0 1 1 1 1 0

0

0

0

0

0

0

1

1

B

0 0 1 1 0 0 1 1 0

0

1

0

1

C

0 1 0 1 0 1 0 1 0

0

1

1

1

F

0 1 1 1 1 1 1 1 0

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

1

Logic Equation

F A B C

Logic Symbol A B C

F

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

NAND gate • NOT-AND Truth Table A

B

F

0

0

1

0

1

1

1

0

1

1

1

0

Wavelet

Logic Equation

F AB A B A

0

0

1

1

0

B

0

1

0

1

0

F

1

1

1

0

1

Logic Symbol A B A B

F

F

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

3 input NAND gate Truth Table

Wavelet

A

B

C

F

A

0 0 0 0 1 1 1 1 0

0

0

0

1

B

0 0 1 1 0 0 1 1 0

0

0

1

1

C

0 1 0 1 0 1 0 1 0

0

1

0

1

0

1

1

1

F

1 1 1 1 1 1 1 0 1

1

0

0

1

1

0

1

1

1

1

0

1

1

1

1

0

Logic Equation

F ABC A B C

Logic Symbol A B C

F

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

NOR gate • NOT-OR Truth Table A

B

F

0

0

1

0

1

0

1

0

0

1

1

0

Wavelet

Logic Equation

F A B A

0

0

1

1

0

B

0

1

0

1

0

F

1

0

0

0

1

Logic Symbol A B A B

F

F

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

3 Input NOR gate Truth Table

Wavelet

A

B

C

F

A

0 0 0 0 1 1 1 1 0

0

0

0

1

B

0 0 1 1 0 0 1 1 0

0

0

1

0

1

0

0

0 1 0 1 0 1 0 1 0

0

C

0

1

1

0

F

1 0 0 0 0 0 0 0 1

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

0

Logic Equation

F A B C

Logic Symbol A B C

F

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

XOR gate • eXclusive OR Truth Table A

B

F

0

0

0

0

1

1

1

0

1

1

1

0

Wavelet

Logic Equation

F A B AB AB A

0

0

1

1

0

B

0

1

0

1

0

F

0

1

1

0

0

Logic Symbol A B

F

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

3 Input XOR gate Truth Table

Wavelet

A

B

C

F

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

0 1 1 0 1 0 0 1

A

0 0 0 0 1 1 1 1 0

B

0 0 1 1 0 0 1 1 0

C

0 1 0 1 0 1 0 1 0

F

0 1 1 0 1 0 0 1 0

Logic Equation

F A B C

Logic Symbol A B C

F

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

XNOR gate • eXclusive NOR Equivalence Truth Table A

B

F

0

0

1

0

1

1 1

Wavelet

Logic Equation

A

0

0

1

1

0

F AB AB

0

B

0

1

0

1

0

A B

0

0

F

1

0

0

1

1

A

1

1

Logic Symbol

A B

F

A B

B

A B

F

F

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

3 Input XNOR gate 진리표 A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

동작파형 F 1 0 0 1 0 1 1 0

A

0 0 0 0 1 1 1 1 0

B

0 0 1 1 0 0 1 1 0

C

0 1 0 1 0 1 0 1 0

F

1 0 0 1 0 1 1 0 1

논리식

F A B C A

B C

논리기호 A B C

F

Source)디지털 논리회로, 임석구, 홍경호

Logic Gate and Network

Logic network (or logic circuit)

Logic Gate and Network

Example 1

AB'C

Logic Gate and Network

Example 2

[ A(C D)]' BE

Analysis of Logic Network

Synthesis and Analysis • Synthesis – Create a new circuit for an application – Optimization!!

• Analysis – Determine the function of an existing circuit – Rather straightforward and much simpler than synthesis

Analysis of Logic Network

Analysis of a Logic Network

Analysis of Logic Network

Timing Diagram • Graphical form presenting changes in signals of various points in the network

Analysis of Logic Network

Functionally Equivalent Networks

Analysis of Logic Network

Functionally Equivalent Networks (cont’d) • A logic function can be implemented – With different networks – With different costs

• Important Issues – How do we find the best implementation for a given function? – Techniques for synthesizing logic functions? • Truth table • Algebraic (Boolean) manipulations • More techniques

– Why call “Functionally Equivalent”, not just “Equivalent”?? • Physical properties are different

Boolean Algebra

Boolean Algebra • In 1849 George Boole – Defined an algebraic description of processes involved in thought and reasoning

• In the late 1930 Claude Shannon applied this to logic circuits • Boolean algebra developed into a powerful tool to describe logic circuits

Boolean Algebra

Boolean Algebraic structure • A set of element B={ 0, 1 } • Binary operation { + (OR), • (AND) } • Unary operation { ‘ (NOT) }

Axioms of Boolean Algebra

Axioms of Boolean Algebra

Boolean Algebra with Single Variable

Single Variable Theorems • B={0,1,x} • x can be either 0 or 1 – e.g. switch

At least one variable is 0 At least one variable is 1

Boolean Algebra with Single Variable

Equivalent Switch Circuits

Boolean Algebra with Single Variable

Equivalent Switch Circuits (cont’)

Boolean Algebra with Single Variable

Duality • A dual (pair) of a Boolean expression is derived by replacing • by +, + by •, 0 by 1, and 1 by 0, and leaving variables unchanged • You will see more… Replacing And by OR, OR by AND, 0 by 1, and 1 by 0

Boolean Algebra with more Variables

Two and three variable properties

Boolean Algebra with more Variables

Proof of Associate Law for AND X Y Z

XY YZ

(XY)Z

X(YZ)

0 0 0

0

0

0

0

0 0 1

0

0

0

0

0 1 0

0

0

0

0

0 1 1

0

1

0

0

1 0 0

0

0

0

0

1 0 1

0

0

0

0

1 1 0

1

0

0

0

1 1 1

1

1

1

1

Boolean Algebra with more Variables

Associative Laws for AND and OR Associative Law Using AND Gates

A = B C

C

ABC 1 iff A B C 1

(AB)C=ABC

Associative Law Using OR Gates A B C

A =B C (A+B)+C=A+B+C

+

A B C 0 iff A B C 0

Boolean Algebra with more Variables

Proof of Distributive Laws Distributive Laws:

X (Y Z ) XY XZ X YZ ( X Y )( X Z )

Valid only Boolean algebra not for ordinary algebra

Proof

( X Y )( X Z ) X ( X Z ) Y ( X Z ) XX XZ YX YZ X XZ XY YZ X 1 XZ XY YZ X (1 Z Y ) YZ X 1 YZ X YZ

Boolean Algebra with more Variables

Proof of Absorption • 13a. x + x • y = x proof : x + x • y = x • ( 1 + y ) X=X·X =x•1=x

• 13b. x • (x + y) = x proof : x • (x + y) = x • x + x • y =x+x•y=x

Simplification Properties in Boolean Algebra

Two and three variable properties - Simplification Combining

DeMorgan’s theorem

Consensus

Simplification Properties in Boolean Algebra

Proof of Combining • 14a. x • y + x • y ’ = x proof : x • y + x • y ’ = x • ( y + y’ ) =x•1=x • 14b. (x + y) • (x + y’) = x proof : (x + y) • (x + y’) = x + ( y • y’) =x+0=x

Simplification Properties in Boolean Algebra

Proof of DeMorgan’s theorem (15a)

Simplification Properties in Boolean Algebra

Proof of property 16 • 16a. x + x’ • y = x + y proof : x + x’ • y = (x + x’) • ( x + y ) = 1 • (x + y) = x + y • 16b. x • (x’ + y) = x • y proof : x • (x’ + y) = x • x’ + x • y =0+x•y=x•y

Simplification Properties in Boolean Algebra

Proof of consensus • 17a. x • y + y • z + x’ • z = x • y + x’ • z proof : x • y + y • z + x’ • z = x • y + x’ • z + (x + x’) • y • z = x • y + x’ • z + x • y • z + x’ • y • z = x • y + x • y • z + x’ • z + x’ • z • y = x • y • (1 + z) + x’ • z • (1+y) = x • y • 1 + x’ • z • 1 = x • y + x’ • z

Simplification Properties in Boolean Algebra

Examples of Consensus c

Example 1

a' b'ac bc'b' c ab a' b'ac bc' a

Example 2

eliminated

c

(a b c' )(a b d ' )(b c d ' ) (a b c' )(b c d ' ) eliminated

Simplification Properties in Boolean Algebra

Examples of Consensus Either way of Consensus is OK (1)

A' C' D A' BD BCD ABC ACD' A

(2)

A' C' D A' BD BCD ABC ACD' C

D

Simplification of Logic Network

Simplification Application of Simplification Theorem to Functionally Equivalent Gate Circuits

F A( A' B) AB A

F

B A

Simplification of Logic Network

An example

Simplification of Logic Network

An example (cont’d)

Optimization!!!

Simplification of Logic Network

Other examples • Z = A’BC + A’ Z = (A’)(BC) + A’ = A’ ( by 13(a) ) • Z = [A+B’C+D+EF][A+B’C+(D+EF)’] Z=[(A+B’C)+(D+EF)][(A+B’C)+ (D+EF)’] = A+B’C (by 14(b) ) • Z = (AB+C)(B’D + C’E’)+(AB+C)’ Z = B’D+C’E’+(AB+C)’ (by 16(a) )

Simplification of Logic Network

Examples of Consensus Adding Consensus term for simplification Original expression

F ABCD B' CDE A' B' BCE ' A

F ABCD B' CDE A' B' BCE ' ACDE E

Consensus Final expression

F A' B' BCE ' ACDE

term added (ABCD + B’CDE)

Simplification of Logic Network

Example of Exclusive NOR Exclusive-NOR

Example of XOR and Equivalence

F ( A' B C) ( B AC ' )

F [( A' B)C ( A' B)' C ' ] [ B' ( AC ' ) B( AC ' )' ] A' BC ( A B' )C ' AB ' C ' B( A'C ) B( A' C A'C ) C ' ( A B' AB ' ) B( A'C ) C ' ( A B' ) Useful theorem:

( XY'X 'Y )' XY X 'Y '

Venn Diagram

Venn Diagram • Simple visual aid to verify the theorems and properties. • Provide a graphical illustration of various operations and relations in the algebra of sets.

Venn Diagram

Venn Diagram (AND, OR)

Venn Diagram

Verification of Consensus with Venn Diagram

Same

Synthesis of Logic Circuit

Notation and Precedence of Operations • Logical sum and logical product operations – OR “sum” x+y : sum term – AND “product” xy : product term

• Precedence – In the order : NOT, AND, and then OR

implies

Synthesis of Logic Circuit

Synthesis using AND, OR and NOT gates • Synthesis : generate a circuit that implements a function from specifications • Simple process of Synthesis – Specifications can be represented as a truth table – Create the product term for which output has a value 1 – Logical sum of these product terms

Synthesis of Logic Circuit

Example of Simple Synthesis

Synthesis of Logic Circuit

Is it the best? NO! Logic function can be shorten !!

Synthesis of Logic Circuit

So, what is the best realization? • Reduce number of inputs – Fewer inputs implies faster gates – # of gate inputs are limited in some technologies

• Reduce number of literal – Literal : input variables (including complement) of a product term (or a Boolean expression) – Number of literal : sum of number of times each literal appears in logic function expression – Approximate cost of logic gate as 2 transistors per literal – Fewer literals means less transistors

• Reduce number of gates – Reduce the size of circuits

• Reduce number of levels of gates – Reduce propagation delays

Synthesis of Logic Circuit

Comparison of circuits

maximum number of inputs = 2 number of literal = 2 number of gates = 1 number of levels of gates = 1 maximum number of inputs = 3 number of literal = 6 number of gates = 4 number of levels of gates = 2

Not gate is not considered as a gate

Minterm and Maxterm in Canonical forms

Canonical forms • Standard forms for a Boolean expression • A unique algebraic signature • Using Truth table to obtain canonical forms

Minterm and Maxterm in Canonical forms

Minterm and Maxterm • Minterm (mi) – ANDed product of literals – Product term in which each of input variables or its complement appears exactly once – For sum-of-products

• Maxterm (Mi) – ORed sum of literals – Sum term in which each of input variables or its complement appears exactly once – For product-of-sums

Minterm and Maxterm in Canonical forms

Example of minterm and maxterm

N input variables 2^N minterms or maxterms

SOP : Sum-Of-Products

Sum-of-Products Form • SOP : Sum-Of-Products – A function can be represented by an expression that is a logical sum of products

• Canonical SOP – If each product term is a minterm

SOP : Sum-Of-Products

Minimum-cost SOP

SOP : Sum-Of-Products

Cost of network * Cost of a gate = number of input + number of output * Cost of a network = sum of the cost of gates in a network

Canonical SOP

Minimal SOP

1 OR gate with 4 input, 1 output a cost of 5 4 AND gate with 3 input,1 output a cost of 16 3 NOT gate with 1 input,1 output a cost of 6

1 OR gate with 2 input, 1 output a cost of 3 2 AND gate with 2 input,1 output a cost of 6 2 NOT gate with 1 input,1 output a cost of 4

Total : a cost of 27

Total : a cost of 13

Level of network = 2 # of Literals = 12

Level of network = 2 # of Literals = 4

POS : Product-Of-Sums

Product-Of-Sums Form • POS : Product-Of-Sums – A function can be represented by an expression that is a logical product of sums

• Canonical POS – If each sum term is a maxterm

POS : Product-Of-Sums

How to derive POS? • Using DeMorgan’s theorem – Consider f’ = 0 cases, that is, f = 1

POS : Product-Of-Sums

Minimum-cost of POS

SOP vs POS • Which one is better? –Depends on the cases –Choose the one which has minimum cost

NAND/NOR gates

NAND and NOR logic networks • NAND and NOR functions are attractive

NAND

NOR

NAND/NOR gates

DeMorgan’s theorem in terms of logic gates

NAND/NOR gates

NAND gate implementation of SOP

NAND/NOR gates

NOR gate implementation of POS

NAND/NOR gates

NAND or NOR gate implementation of NOT gate

Either

Design Logic Circuit

Design Logic Circuit • Conversion of Verbal Description to Boolean Equations – 1. Find a switching function which specifies the desired behavior of the circuit – 2. Find a simplified algebra expression for the function – 3. Realize the simplified function using available logic elements

Design Logic Circuit

Examples Example Mary watches TV if it is Monday night and she has finished her homework. F = 1 if “Mary watches TV ” is true; otherwise, F = 0; A = 1 if “it is Monday night ” is true; otherwise, A = 0; B = 1 if “she has finished her homework” is true; otherwise, B = 0;

F is ‘true’ if A and B are both ‘true’ F=A·B

Design Logic Circuit

Verbal Description Boolean Expression 1. Verbal Description

The alarm will ring iff the alarm switch is turned on and the door is

not closed, or it is after 6PM and window is not closed. Breaking Down

The alarm will ring iff Z

the alarm switch is turned on

and

the door is not closed, B’

A

or

it is after 6PM C

and

window is not closed. D’

Design Logic Circuit

Verbal Description Boolean Expression 2. Boolean Equation

The alarm will ring iff Z

the alarm switch is turned on

and

the door is not closed, B’

A

or

it is after 6PM

and

C

Z AB'CD'

window is not closed. D’

Design Examples

Design Example : Three-way light controller • A room has three doors, each with a switch to control a light • Design – x1, x2 and x3 denotes each switch – Light on if • Any one of switches is closed • All of switches are closed

– Light off if • All of switches are open • Any two switches are closed

Design Examples

Truth table and realizations

Design Examples

Another example : Multiplexer circuit • Multiplexer – Switches one of multiple sources of data to a single destination, based on one or more selection control input

• Suppose – Two sources (x1, x2) and one output (f) – Control input (s) – If s = 0, f = x1. Otherwise if s = 1, f = x2

Design Examples

Truth table and realization

Functional View