Logic gates Logic gates and truth tables

Logic gates
! Last lecture
" Boolean algebra # Axioms # Useful laws and theorems # Simplifying Boolean expressions
! Today’s lecture
" Logic gates and truth tables " Implementing logic functions " CMOS switches
CSE370, Lecture 4

Logic gates and truth tables

! AND X•Y XY XY

XYZ Z 00 01 00
100 111

! OR X+Y

XYZ

X

Z

000

Y

011

101

111

! NOT X

X’

X

Y

XY 01 10

! Buffer X

X

Y

XY 00 11

1

CSE370, Lecture 4

2

Logic gates and truth tables (con’t)

! NAND X • Y XY XY

! NOR X + Y

X

Y

! XOR X ⊕ Y

X

Y

! XNOR X ⊕ Y

X

Y

CSE370, Lecture 4

XYZ Z 00 01 11
101 110

XYZ

001

Z

010

100

110

XYZ

Z

000

011

101

110

XYZ

001

Z

010

100

111

3

Definitions
! Schematic: A drawing of interconnected gates ! Net: Wires at the same voltage (electrically connected) ! Netlist: A list of all the devices and connections in a
schematic ! Fan-in: The # of inputs to a gate ! Fan-out: The # of loads the gate drives

CSE370, Lecture 4

4

Mapping Boolean expressions to logic gates

! Example: F = (A•B)’ + C•D

NAND2
A B 19
AND2
C D 16

OR2
F
17

! Example: F = C•(A+B)’

NOR2
A B 21
C

AND2
F
22

CSE370, Lecture 4

5

Example: A binary full adder

! 1-bit binary adder
" Inputs: A, B, Carry-in

A

B

Adder

Sum

" Outputs: Sum, Carry-out Cin

Cout

A B Cin S Cout 000 00 001 10 010 10 011 01 100 10 101 01 110 01 111 11

Sum = A'B'Cin + A'BCin' + AB'Cin' + ABCin Cout = A'BCin + AB'Cin + ABCin' + ABCin

CSE370, Lecture 4

6

Full adder: Sum

Before Boolean minimization Sum = A'B'Cin + A'BCin'
+ AB'Cin' + ABCin

AND3 A' B' C in 28
AND3 A' B C in' 30
AND3 A B' C in' 29
AND3 A B C in 31

OR4
Sum
27

CSE370, Lecture 4

After Boolean minimization Sum = (A⊕B) ⊕ Cin

XOR
A B 32
Cin

XOR
Sum
33

7

Full adder: Carry-out

Before Boolean minimization Cout = A'BCin + AB'Cin + ABCin' + ABCin

AND3 A' B C in 1
AND3 A B' C in 2
AND3 A B C in' 3
AND3 A B C in 4

OR4
Cout
5

CSE370, Lecture 4

After Boolean minimization Cout = BCin + ACin + AB

AND2
B Cin 11
AND2
A Cin 12
AND2
A B 13

OR3
Cout
14
8

Preview: A 2-bit ripple-carry adder

AB

XOR A B 32
Cin

Cin

AND2 B Cin 11
AND2 A Cin 12
AND2 A B 13

1-Bit Adder

XOR

Sum 33

0

C OR3

out

Cout 14

A1 B1 Cin Cout
Sum1

A2 B2 Cin Cout
Sum2

Sum
CSE370, Lecture 4

Overflow
9

Mapping truth tables to logic gates

! Given a truth table

" Write the Boolean expression

" Minimize the Boolean expression

" Draw as gates

AB C F 0000 0010

F = A’BC’+A’BC+AB’C+ABC = A’B(C’+C)+AC(B’+B) = A’B+AC

0101

0111 1000 1011 1100 1111

AND2
A' B 26
AND2
A C 25

OR2
F
24

CSE370, Lecture 4

10

Many possible mappings
! Many ways to map expressions to gates " Example: Z = A • B • (C + D) = A • B • (C + D)

A A ZZ

B

ZB

C

C

D

D

CSE370, Lecture 4

11

What is the optimal gate realization?
! We use the axioms and theorems of Boolean algebra to “optimize” our designs
! Design goals vary
" Reduce the number of inputs? " Reduce the number of gates? " Reduce number of gate levels?
! How do we explore the tradeoffs?
" CAD tools " Logic minimization: Reduce number of gates and complexity " Logic optimization: Maximize speed and/or minimize power

CSE370, Lecture 4

12

Minimal set

! We can implement any logic function from NOT, NOR, and NAND
" Example: (X and Y) = not (X nand Y)
! In fact, we can do it with only NOR or only NAND
" NOT is just NAND or NOR with two identical inputs

X Y X nor Y

00

1

11

0

X Y X nand Y

00

1

11

0

" NAND and NOR are duals: Can implement one from the other # X nand Y = not ((not X) nor (not Y)) # X nor Y = not ((not X) nand (not Y))

CSE370, Lecture 4

13

Most digital logic is CMOS

! CMOS technology

" Complementary Metal-

Oxide Semiconductor

X

Y

" Transistors act as voltage-

controlled switches

1.8V

0V ≡ Logic 0 1.8V ≡ Logic 1
XY 0V 1.8V 1.8V 0V
1.8V

0.13µm

X

YX

Y

CSE370, Lecture 4

Mark Bohr

0V

Intel

0V
14

Multi-input logic gates

! CMOS logic gates are inverting
" Get NAND, NOR, NOT
" Don’t get AND, OR, Buffer

1.8V

1.8V

XY Z X Y

XYZ 001 011 101 110
CSE370, Lecture 4

Z X
Y 0V

1.8V

1.8V

X

Y

Z X

Y 0V 15