Entwurf kombinatorischer Schaltungen - ti.uni-due.de · Grundlagen der Technische Informatik Wintersemester 2018/19 Vorlesender: Dr. Ing. Frank Sill Torres 2. Review - Karnaugh-Veich

Grundlagen der Technische InformatikWintersemester 2018/19

Vorlesender:Dr. Ing. Frank Sill Torres

1

Entwurf kombinatorischer SchaltungenGrundlagen der technischen InformatikWintersemester 2018/19

Folien basierend auf Material von F. Vahid und S. Werner



2Grundlagen der Technische InformatikWintersemester 2018/19


Review - Karnaugh-Veich Maps (KV-Maps)• Graphical method for finding terms that can be combined to eliminate

variables in order to obtain the minimum• Minterms differing from one variable are adjacent (neighbors) on the

map• We can clearly visualize the possible cases of combination of terms

00 01 11 10

0

1

Fyz

x

Note that it is not sorted binary

Consider left and right neighbors too

KV-map

z = 1

y = 1

x’y’z’ x’y’z x’yz x’yz’

xy’z’ xy’z xyz xyz’

0

00 01 11 10

0

1

1 3 2

4 5 7 6

yzx

z = 1

y = 1

F = xyz

Reminder:

` 0, 1` 0, 1` 0, 1

x xy yz z





Review - KV-maps

• Four adjacent cells can be in shapeof a square

• OK to cover a 1 twice– Just like duplicating a term▪ Remember, c + d = c + d + d

• No need to cover 1s more than once– Yields extra terms – not

minimized

0 1 1 0

00 01 11 10

0 1

0

1 1 0

H yzx

z

H = x’y’z + x’yz + xy’z + xyz(xy appears in all combinations)

0 1 0 0

00 01 11 10

1 1

0

1 1 1

I yzx

x

y’z

The two circles are shorthand for:I = x’y’z + xy’z’ + xy’z + xyz + xyz’I = x’y’z + xy’z + xy’z’ + xy’z + xyz + xyz’I = (x’y’z + xy’z) + (xy’z’ + xy’z + xyz + xyz’)I = (y’z) + (x)

1 1 0 0

00 01 11 10

0 1

0

1 1 0

J yzx

xz

y’zx’y’





Review - Don’t Care Input Combinations

• What if particular input combinations can never occur?– e.g., Minimize F = xy’z’, given that x’y’z’

(xyz=000) can never be true, and that xy’z (xyz=101) can never be true

– So it doesn’t matter what F outputs when x’y’z’ or xy’z is true, because those cases will never occur

– Thus, make F be 1 or 0 for those cases in a way that best minimizes the equation

• On KV-map– Draw Xs for don’t care combinations▪ Include X in circle ONLY if minimizes

equation▪ Don’t include other Xs

X 0 0 0

00 01 11 10

1 X

0

1 0 0

F yz y’z’x

Good use of don’t cares

Unnecessary use of don’t cares; results in extra term

X 0 0 0

00 01 11 10

1 X

0

1 0 0

F yz y’z’ unneeded

xy’

xunneeded





Review - Example of Automated Two-Level Minimization

1. Determine all prime implicants

2. Add essential PIs to cover

– Italicized 1s are thus already covered

– Only one uncovered 1 remains

3. Cover remaining mintermswith non-essential PIs

– Pick among the two possible PIs 1 1 1 0

00 01 11 10

1 0

0

1 0 1

I yzx

y’z’

x’z

xz’

(c)

1 1 0

00 01 11 10

1 0

0

1 0 1

I yzx

1 1 1 0

00 01 11 10

1 0

0

1 0 1

I yzx

x’y’y’z’

x’z

xz’

(b)

x’y’y’z’

x’z

xz’

(a)1

1

1





• Many circuits have more than one output• Can give each a separate circuit, or can share gates• Ex: F = ab + c’, G = ab + bc

a

b

c

F

G

(b)

a

b

c

F

G

(a)

Option 1: Separate circuits Option 2: Shared gates

Multiple-Output Circuits





abcdefg = 1111110 0110000 1101101

afb

d

gec

(b)(a)

afb

d

gec

wxyz Converter

Multiple-Output Example: BCD to 7-Segment Converter





a = w’x’y’z’ + w’x’yz’ + w’x’yz + w’xy’z + w’xyz’ + w’xyz + wx’y’z’ + wx’y’z

b = w’x’y’z’ + w’x’y’z + w’x’yz’ + w’x’yz + w’xy’z’ + w’xyz + wx’y’z’ + wx’y’z

afb

d

gec

...

Multiple-Output Example: BCD to 7-Segment Converter





Step Description

Step 1:Capturebehavior

Capture the function

Create a truth table or equations, whichever is most natural for the given problem, to describe the desired behavior of each output of the combinational logic.

2A: Createequations

This substep is only necessary if you captured the function using a truth table instead of equations. Create an equation for each output by ORing all the minterms for that output. Simplify the equations if desired.

2B: Implementas a gate-based circuit

For each output, create a circuit corresponding to the output’s equation. (Sharing gates among multiple outputs is OK optionally.)

Step 2:Convertto circuit

Combinational Logic Design Process





• Problem: Detect three consecutive 1sin 8-bit input: abcdefgh• 00011101 → 1 • 10101011 → 0 • 11110000 → 1– Step 1: Capture the function• Truth table or equation?

– Truth table too big: 2^8=256 rows

– Equation: create terms for eachpossible case of three consecutive 1s

• y = abc + bcd + cde + def + efg + fgh– Step 2a: Create equation -- already done– Step 2b: Implement as a gate-based circuit

bcd

def

fgh

abc

cde

efg

y

abc

d

e

f

g

h

Example: Three 1s Pattern Detector





• Problem: Output in binary on twooutputs yz the amount of 1s on threeinputs

• 010 01 • 101 10 • 000 00

– Step 1: Capture the function• Truth table or equation?

–Truth table is straightforward

– Step 2a: Create equations• y = a’bc + ab’c + abc’ + abc• z = a’b’c + a’bc’ + ab’c’ + abc• Optional: Let's simplify y:

–y = a'bc + ab'c + ab(c' + c) = a'bc + ab'c + ab

– Step 2b: Implement as a gate-based circuit

abc

abc

abc

abc

z

abc

abc

a

b

y

Example: Number of 1s Counter





• Keypad has 7 outputs– One per row– One per column

• Key press sets one row and one column output to 1– Press "5" r2=1, c2=1

• Goal: Convert keypad outputs into 4-bit binary number– 0-9 0000 to 1001– * 1010, # 1011– nothing pressed: 1111

1

*

3

#

2

4 65

7 98

0

r2

r3

r4

c1 c2 c3

r1

Converter

wxyz

Example: Keypad Converter





• Step 1: Capture behavior– Truth table too big (2^7 rows); equations not clear either– Informal table can help

w = r3c2 + r3c3 + r4c1 + r4c3 + r1'r2'r3'r4'c1'c2'c3'x = r2c1 + r2c2 + r2c3 + r3c1 + r1'r2'r3'r4’c1'c2'c3'y = r1c2 + r1c3 + r2c3 + r3c1 + r4c1 + r4c3 + r1'r2'r3'r4'c1'c2'c3'z = r1c1 + r1c3 + r2c2 + r3c1 + r3c3 + r4c3 + r1'r2'r3'r4'c1'c2'c3'

Step 2b: Implement as circuit (note sharable gates) ...

Example: Keypad Converter





• Microprocessor outputs which zone to water (e.g., cba=110 means zone 6) and enables watering (e=1)

• Decoder should set appropriate valve to 1

d0d1d2d3d4d5d6d7e

c

decoder

Micro-processor

b

a

zone 0 zone 1

24

3

56

7

d0 = a'b'c'ed1 = a'b'ce

d2 = a'bc'ed3 = a'bced4 = ab'c'ed5 = ab'ced6 = abc'ed7 = abce

Step 1: Capture behavior

Equations seem like a natural fit

Example: Sprinkler Controller





• Step 2b: Implement as circuitd0d1d2d3d4d5d6d7e

c

decoder

Micro-processor

b

a

zone 0 zone 1

24

3

56

7

d0 = a'b'c'ed1 = a'b'ce

d2 = a'bc'ed3 = a'bced4 = ab'c'ed5 = ab'ced6 = abc'ed7 = abce

abc

e

d0

d1

d2

d3

d4

d5

d6

d7

Example: Sprinkler Controller





• NAND: Opposite of AND (“NOT AND”)• NOR: Opposite of OR (“NOT OR”)• XOR: Exactly 1 input is 1, for 2-input XOR. (For more inputs -- odd

number of 1s)• XNOR: Opposite of XOR (“NOT XOR”)

x0011

y0101

F1000

xy F

NOR

x0011

y0101

F1110

xy F

NAND

x0011

y0101

F0110

XOR

x0011

y0101

F1001

XNOR

More Gates





• Aircraft lavatory signexample– S = (abc)’

• Detecting all 0s– Use NOR

• Detecting equality – Use XNOR

• Detecting odd # of 1s– Use XOR– Useful for generating “parity”

bit common for detecting errors

S

Circuit

abc

000

1 a0

b0

a1

b1

a2

b2

A=B

More Gates: Example Uses





•Likewise for NOR

• Any Boolean function can be implemented using just NAND gates. Why?– Need AND, OR, and NOT– NOT: 1-input NAND (or 2-input NAND with inputs tied

together)– AND: NAND followed by NOT– OR: NAND preceded by NOTs*

→Thus, NAND is a universal gate• Can implement any circuit using just NAND gates

• Likewise for NOR

Completeness of NAND

*A B A B A B+ = + =*Proof via DeMorgan:





• How many possible functions of 2 variables?– 22 rows in truth table, 2 choices for each– 2(22) = 24 = 16 possible functions

• N variables– 2N rows– 2(2N) possible functions

a0011

b0101

0 or 1 2 choices0 or 1 2 choices0 or 1 2 choices0 or 1 2 choices

F

24 = 16possible functions

f00000

b0101

a0011

f10001

f20010

f30011

f40100

f50101

f60110

f70111

f81000

f91001

f101010

f111011

f121100

f131101

f141110

f151111

0

a A

ND

b a ba

XO

R b

a O

R b

a N

OR

b

a X

NO

R b b’ a’

a N

AN

D b 1

Number of Possible Boolean Functions





• Decoder: Popular combinational logic building block, in addition to logic gates– Converts input binary number

to one high output• 2-input decoder: four possible

input binary numbers– So has four outputs, one for

each possible input binary number

• Internal design– AND gate for each output to

detect input combination• Decoder with enable e

– Outputs all 0 if e=0– Regular behavior if e=1

• n-input decoder: 2n outputs

i0

i1

d0

d1

d2d3 1

1

10

0

0

i0

i1

d0

d1

d2d3 0

0

00

0

1

i0

i1

d0

d1

d2d3

i0

i1

d0

d1

d2d30

0

10

1

0

0

1

01

0

0

i0i1

d0d1

d2d3e 1

1

11

000

e

i0i1

d0d1

d2d3 0

11

000

0i0

d0

d1

d2

d3

i1

i1’i0’

i1’i0

i1i0’

i1i0

Decoders and Muxes





• New Year’s Eve Countdown Display

– Microprocessor counts from 59 down to 0 in binary on 6-bit output

– Want illuminate one of 60 lights for each binary number

– Use 6x64 decoder

• 4 outputs unused

d0d1d2d3

i0i1i2i3i4i5

e

6x64dcd

d58d59d60d61d62d63

0HappyNew Year

123

5859

010000

0010

00

2 2 1100000

0100

00

1000000

1000

00

0 0

Proc

esso

r

Decoder Example





• Mux: Another popular combinational building block– Routes one of its N data inputs to its one output, based on binary

value of select inputs• 4 input mux needs 2 select inputs to indicate which input to

route through• 8 input mux 3 select inputs • N inputs log2(N) selects

– Like a rail yard switch

Multiplexor (Mux)





s0

di0

i1

2×1

i1i0

s01

d

2×1

i1i0

s00

d

2×1

i1i0

s0

d

0

i0 (1*i0=i0)

i0 (0+i0=i0)1

0

2x1 mux

i04⋅ 1

i2i1

i3s1 s0

d

s0

d

i0

i1

i2

i3

s1

4x1 mux

0

Mux Internal Design





• City mayor can set four switches up or down, representing his/her vote on each of four proposals, numbered 0, 1, 2, 3

• City manager can display any such vote on large green/redLED (light) by setting two switches to represent binary 0, 1, 2, or 3

• Use 4x1 mux

i0

4x1

i2

i1

i3

s1 s0

d

1

2

3

4

Mayor’s switches

manager'sswitches

Green/RedLED

on/off

Proposal

Mux Example





• Ex: Two 4-bit inputs, A (a3 a2 a1 a0), and B (b3 b2 b1 b0)– 4-bit 2x1 mux (just four 2x1 muxes sharing a select line) can select

between A or B

i0

s0i1

2x 1d

i0

s0i1

2x 1d

i0

s0i1

2x 1d

i0

s0i1

2x 1d

a3b3

I0

s0

s0

I1

4-bit2x1

D CA

B

a2b2

a1b1

a0b0

s0

4C

44

4

c3

c2

c1

c0

is short for

Simplifyingnotation:

Muxes Commonly Together –N-bit Mux





• Four possible display items– Temperature (T), Average km-per-liter (A), Instantaneous km-per-

liter (I), and Km remaining (M) – each is 8-bits wide– Choose which to display on D using two inputs x and y

• Pushing button sequences to the next item– Use 8-bit 4x1 mux

I08-bit

4x1

I2

I1

I3s1 s0

D

x y

8

8 D

T

AI

M

8

8

8

button

We`ll design This later

To the above-mirror display

From the car's central computer

N-bit Mux Example





• N-bit equality comparator: Outputs 1 if two N-bit numbers are equal• Example: 4-bit equality comparator with inputs A and B

• a3 must equal b3, a2 = b2, a1 = b1, a0 = b0• Two bits are equal if both 1, or both 0• eq = (a3b3 + a3’b3’) * (a2b2 + a2’b2’) * (a1b1 + a1’b1’) * (a0b0 + a0’b0’)

• Note that function inside parentheses is XNOR• eq = (a3 xnor b3) * (a2 xnor b2) * (a1 xnor b1) * (a0 xnor b0)

a3 b3 a2 b2 a1 b1 a0 b0

eq

a3 a2 a1 a0 b3

eq

b2 b1 b0

4-bit equality comparator

0110 = 0111 ? 0 1 1 00 1 1 1

01 1 1

0

=

Comparators





• N-bit magnitude comparator: Two N-bit inputs A and B, outputs whether A>B, A=B, or A B

Magnitude Comparator





• By-hand example leads to idea for design– Start at left, compare each bit pair, pass results to the right– Each bit pair called a stage– Each stage has 3 inputs taking results of higher stage, outputs new

results to lower stage

in_gtin_eqin_lt

out_gtout_eqout_lt

IgtIeqIlt

Stage 3

a3 b3

a bin_gtin_eqin_lt

out_gtout_eqout_lt

Stage 2

a2 b2

a bin_gtin_eqin_lt

out_gtout_eqout_lt

Stage 1

a1 b1

a bin_gtin_eqin_lt

out_gtout_eqout_lt

AgtBAeqBAltB

Stage 0

a0 b0

a b

IgtIeqIlt

a3 a2 a1 a0 b3b2b1b0 AgtBAeqBAltB

0

01 4-bit magnitude comparator > = <

How design each stage?


gt – greater thaneq – equallt – lower than





• Each stage:– out_gt = in_gt + (in_eq * a * b’)

• A>B if already determined in higher stage, or if higher stages equal but in this stage a=1 and b=0

– out_lt = in_lt + (in_eq * a’ * b)• A





• How does it work?

in_gtin_eqin_lt

out_gtout_eqout_lt

IgtIeq

Ilt

Stage3

a3 b3

a b

in_gtin_eqin_lt

out_gtout_eqout_lt

Stage2

a2 b2

a b

in_gtin_eqin_lt

out_gtout_eqout_lt

Stage1

a1 b1

a b

in_gtin_eqin_lt

out_gtout_eqout_lt

AgtBAeqBA ltB

Stage0

a0 b01 1 0 0 1 0 1 1

a b

(a)

=

010

in_gtin_eqin_lt

out_gtout_eqout_lt

IgtIeq

Ilt

S tage3

a3 b3

a b

in_gtin_eqin_lt

out_gtout_eqout_lt

S tage2

a2 b2

a b

in_gtin_eqin_lt

out_gtout_eqout_lt

S tage1

a1 b1

a b

in_gtin_eqin_lt

out_gtout_eqout_lt

AgtBAeqBAltB

S tage0

a0 b01 1 0 0 1 0 1 1

a b

(b)

010

=

010

1011 = 1001 ?

010

Ieq=1 causes this stage to compare

010






• Final answer appears on the right

• Takes time for answer to “ripple” from left to right

• Thus called “carry-ripple style”

1011 = 1001 ?

in_gt

in_eqin_lt

out_gt

out_eqout_lt

IgtIeq

Ilt

S tage3

a3 b3

a b

in_gt

in_eqin_lt

out_gt

out_eqout_lt

S tage2

a2 b2

a b

in_gt

in_eqin_lt

out_gt

out_eqout_lt

S tage1

a1 b1

a b

in_gt

in_eqin_lt

out_gt

out_eqout_lt

AgtB

AeqBAltB

S tage0

a0 b01 1 0 0 1 0 1 1

a b

(c)

0

1

0

1

0

0

>

in_gtin_eq

in_lt

out_gtout_eq

out_lt

IgtIeq

Ilt

Stage3

a3 b3

a b

in_gtin_eq

in_lt

out_gtout_eq

out_lt

Stage2

a2 b2

a b

in_gtin_eq

in_lt

out_gtout_eq

out_lt

Stage1

a1 b1

a b

in_gtin_eq

in_lt

out_gtout_eq

out_lt

AgtBAeqB

AltB

Stage0

a0 b01 1 0 0 1 0 1 1

a b

(d)

0

1

0

0

1

0

010

100






• Design a combinational component that computes the minimum of two 8-bit numbers– Solution: Use 8-bit magnitude comparator and 8-bit 2x1 mux

• If A





• Data inputs: flow through component (e.g., mux data input)• Control input: influence component behavior

– Normally active high – 1 causes input to carry out its purpose– Active low – Instead, 0 causes input to carry out its purpose

• Example: 2x4 decoder with active low enable• 1 disables decoder, 0 enables

• Drawn using inversion bubble

i0

i1

d0

d1

d2

d3e e 1

1

1

1

0

0

0

i0

i1

d0

d1

d2

d30

1

1

0

0

0

(a) (b)0

Active Low Inputs





• Entwurfsmethodik für kombinatorische Schaltungen

• Typische Schaltungen und deren Anwendung

– De- und Multiplexer– Decoder– Vergleicher (auch Komparator)– Größen-Vergleicher

Was haben Sie heute gelernt?

Slide Number 1Review - Karnaugh-Veich Maps (KV-Maps)Review - KV-mapsReview - Don’t Care Input CombinationsReview - Example of Automated Two-Level MinimizationMultiple-Output CircuitsMultiple-Output Example: �BCD to 7-Segment ConverterMultiple-Output Example: �BCD to 7-Segment ConverterCombinational Logic Design ProcessExample: Three 1s Pattern DetectorExample: Number of 1s CounterExample: Keypad ConverterExample: Keypad ConverterExample: Sprinkler ControllerExample: Sprinkler ControllerMore GatesMore Gates: Example UsesCompleteness of NANDNumber of Possible Boolean FunctionsDecoders and MuxesDecoder ExampleMultiplexor (Mux)Mux Internal DesignMux ExampleMuxes Commonly Together – �N-bit MuxN-bit Mux ExampleComparatorsMagnitude ComparatorMagnitude ComparatorMagnitude ComparatorMagnitude ComparatorMagnitude ComparatorMagnitude Comparator Example: �Minimum of Two NumbersActive Low InputsWas haben Sie heute gelernt?

Documents

Entwurf kombinatorischer Schaltungen - ti.uni-due.de · Grundlagen der Technische Informatik Wintersemester 2018/19 Vorlesender: Dr. Ing. Frank Sill Torres 2. Review - Karnaugh-Veich