下-自动化数字逻辑设计课件-第三章

Chapter

3Combinational

LogicDesign

PrinciplesDDiiggiittaall

DDeessiiggnn——

PPiinncciipplleess

aanndd

PPrraaccttiicceessCombinational-CircuitysisExhausting

Way

(穷举法)将全部输入组合加到输入端；根据基本逻辑关系，从输入端到输出端，根据最后输出结果列出真值表。Combinational-CircuitysisAlgebra

Way

(代数法)由输入到输出逐级写出逻辑函数表达式；对输出逻辑函数表达式进行化简；判断逻辑功能。Refer

to

Figure

4-11,

4-12,

4-13Combinational-CircuitysisAlgebra

Way

(代数法)应用广义德·摩根定理来减少非运算Refer

to

Figure

4-14,

4-15,

4-16,

4-17(A

·

B)’

=

A’

+

B’ (A

+

B)’

=

A’

·

B’NAND

<=>

NOT-OR NOR

<=>

NOT-ANDCombinational-Circuitysis并项法：吸收法：消项法：利用A·B+A·B’=A·(B+B’)=A利用A+A·B=A·(1+B)=A利用A·B+A’·C+B·C=A·B+A’·C消因子法：利用A+A’·B=A+B配项法： 利用A

=

A+A 1

=

A+A’Formula

Minimization (公式法化简)Minimizing

Logic

Function(化简逻辑函数)Combinational-CircuitysisMinimizing

Logic

Function(化简逻辑函数)ExerciseMinimize

theLogic

Function

with

Formula

MathodY

=

A·C+B’·C+B·D’+C·D’+A·(B+C’)+A’·B·C·D’+A·B’·D·E=

A+B’·C+B·D’Combinational-Circuit

SynthesisIn

real

circuits,

AND

gates

are

slower

and

more

complex

than

NANDgates.

OR

gates

are

slower

and

more

complex

than

NOR

gates.A

sum-of-products

expression

can

be

realized

as

an

AND-OR

circuit.An

AND-OR

circuit

should

be

replaced

by

a

NAND-NAND

circuit

.Combinational-Circuit

SynthesisA

product-of-sums

expression

can

be

realized

as

an

OR-AND

circuit.AnOR-AND

circuit

should

be

replaced

by

a

NOR-NOR

circuit

.Combinational-Circuit

SynthesisPractice

1Design

a

logic

circuit

to plishthe

function

below:There

are

tow

switches

A

and

B.When

you

go

upstairs,

push

B

to

turn

on

the

light,

and

push

A

to

turn

offthe

light.When

you

go

downstairs,

push

A

to

turn

on

the

light,

and

push

B

to

turnoff

the

light.BALCombinational-Circuit

SynthesisPractice

1ABL000011101110BALTruth

TableL

=

∑A,B

(1,

2)=

A’·B

+

A·B’ABLABLXORGate!Combinational-Circuit

SynthesisPractice

2Design

a

three-variablevoter.If

two

or

three

ofthem

agree，pass

the

proposal.Otherwise,

deny.Combinational-Circuit

SynthesisPractice

2F

=

∑A,B,C

(3,

5,

6,7)=

A’·B·C

+

A·B’·C

+

A·B·C’

+

A·B·C=

A’·B·C

+

A·B·C

+

A·B’·C

+

A·B·C

+

A·B·C’

+

A·B·CABCF00000010010001111000101111011111=

B·C

+

A·C

+

A·BTruth

TableABCABCCombinational-Circuit

SynthesisPractice

3Design

a

4-bit

Pri mber

Detector

(素数检测器).Given

a

4-bit

input

combination

N

=

N3N2N1N0,this

function

produces

a

1

outputfor

N

=

1,

2,

3,

5,

7,

11,

13,

and

0

otherwise.So,

it

can

berepresented

as

a

Canonical

Sum(标准和)F

=

∑N3,N2,N1,N0

(1,

2,

3,

5,

7,

11,

13)Combinational-Circuit

SynthesisPractice

3Standard

Design

of

a

4-bitPri mber

DetectorCombinational-Circuit

SynthesisPractice

3It

can

be

simplified

by

T10.F

=

∑N3,N2,N1,N0

(1,

2,

3,

5,

7,

11,

13)=

N3’·N2’·N1’·N0

+

N3’·N2’·N1·N0’

+

N3’·N2’·N1·N0

+N3’·N2·N1’·N0

+

N3’·N2·N1·N0

+

N3·N2’·N1·N0

+

N3·N2·N1’·N0=

N3’·N2’·N0

+

N3’·N2’·N1·N0’

+

N3’·N2·N0

+

N3·N2’·N1·N0

+N3·N2·N1’·N0=

N3’·N0

+

N3’·N2’·N1·N0’

+

N3·N2’·N1·N0

+

N3·N2·N1’·N0Combinational-Circuit

SynthesisPractice

3Realization

of

Logic

CircuitsCombinational-Circuit

SynthesisPractice

3Logic

function

of

the

4-bit

Pri mber

Detector:F

=

N3’·N0

+

N3’·N2’·N1·N0’

+

N3·N2’·N1·N0

+

N3·N2·N1’·N0Please

simplify

it

further

...Is

there

a

better

way——Karnaugh

Maps(卡诺图)Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)便于采用定理T10、T10’来进行相关项的合并！Why?最小项

/最大项的序号相邻两方格只有一个变量发生改变，符合格雷码规则。将最小项或最大项以二维表格形式排列Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)ExampleX’·Y·Z’X’·Y’·Z+X·Y’·Z=Y’·Z

(According

to

T10)

X·Y·Z+X·Y’·Z=X·ZF

=

∑X,Y,Z

(1,2,5,7)

=

X’·Y’·Z+X’·Y·Z’+X·Y’·Z+X·Y·Z=

X·Z

+

Y’·Z

+

X’·Y·Z’Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)卡诺图化简步骤填写卡诺图可由真值表、标准和或标准积等来填写圈组：找出相邻的1或0每组(圈)内为全1或全0，且个数为2的幂组(圈)内1或0的个数尽量多，组(圈)数尽量少，确保所有1或0都被圈过如果需要，1或0可被圈多次（根据T3、T3’）读图：若圈1，写出合并后的乘积项；若圈0，写出合并后的求和项消掉有变化的变量；保留无变化的变量写出化简后的积之和表达式（圈1）或和之积（圈0）表达式可以圈6个吗Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)两个相邻项，可消去一个变量AB00

01

11

10CD000111101011101111110001A·B·DB’·D’C四个相邻项，可消去两个变量八个相邻项，可消去三个变量2n个相邻项，可消去n个变量蕴含项(Implicant)：只包含1的一个矩形圈主蕴含项(Prime

Implicant)

：扩展到最大的蕴含项完全和：所有主蕴含项之和最小和：即化简结果，部分主蕴含项之和

奇异“1”单元：只能被一个主蕴含项覆盖质主蕴含项(Essential

PrimeImplicant)：含有奇异1单元的主蕴含项ABCD00

01

11

100001111011

111

11

1

1

1Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)几个概念Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)Example

1CD0001111000

01

11

101

1

11

1

11

11

1

1哪些是奇异1单元？找出所有的主蕴含项AB哪些是质主蕴含项？Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)Example

1CDAB00

01

11

10000111101

1

11

1

1CDAB00

01

11

100001111111

11

1

1

10

1

11

1

11

1

1化简结果不一定唯一，但代价相同Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)Example

2CD0001111011

1

11

1没有奇异1单元没有质主蕴含项AB

找出所有的主蕴含项00

01

11

10Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)Example

3CDAB00

01

11

10000001001101000A’+C→原变量→反变量A’+BF=

(A+B’+C’+D)·(A’+C)·(A’+B)CDAB00

01

11

10000111

1

1

1

10

0

1

00

0

1

010

0

0

1

0Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)Example

4圈0和圈1的代价相同吗？圈1得最小和：F=A·B+C·D圈0得最小积：F=(A+C)·(A+D)·(B+C)·(B+D)∴圈1代价最小Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)Practice

3Let’s

optimize

the

foregoing

4-bit

Pri mber

Detector

.N1N0N3N200011110F

=

∑N3,N2,N1,N0

(1,

2,

3,

5,

7,

11,

13)00

01

11

100

0

0

01

1

1

01

1

0

11

0

0

0N3’·N0N

’·N

’·N3

2

1N2·N1’·N0N2’·N1·N0F=

N

’·N +

N

’·N

’·N3

0

3

2

1+

N2’·N1·N0

+

N2·N1’·N0Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)Practice

3F

=

N3’·N0

+

N3’·N2’·N1+

N2’·N1·N0

+

N2·N1’·N0Let’s

optimize

the

foregoing

4-bit

Pri mber

Detector

.F

=

∑N3,N2,N1,N0

(1,

2,

3,

5,

7,

11,

13)Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)五变量卡诺图之化简010

110

111

101

100ABCDE符合格雷码排列00只能消掉一项！011110前面提到的卡诺图的化简方法不再适用！对于四个以上变量的情况，可拆分为多个四变量卡诺图来化简！041121812412820211737151127312319261410263022Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)五变量卡诺图之化简For

example:

F=

A,B,C,D,E(0,1,2,3,4,5,10,11,14,20,21,24,25,26,27,28,29,30)ABC

DE00011110010110

111

101

10001411282412812011111211173171511127131231921614110126130122A

=

0A

=

1Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)五变量卡诺图之化简011110DE000001111001411281511391121611A

=

0A

=

1011110DE0010

11

01

0024128120116251291211172713123192613012218A

=

1011110For

example:

F=

A,B,C,D,E(0,1,2,3,4,5,10,11,14,20,21,24,25,26,27,28,29,30)BC

BC

BCDE0000

01

11

1016201281241172112912511923312711822301261Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)五变量卡诺图之化简A

=

0BCDE

00

01

11

1000

101

111

110

11111

1BCDE

00

0111

10111000

101

11

11

111

1A

=

1F

= A’·B’·D’

+

A’·C’·D

+ A·C·D’

+

A·B·C’

+

B·D·E’Combinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)多输出函数的最小化ABCF1F2ABC

00

01

11

1001111ABC

00

01

11

1001111F1=

A’·B’

+

A’·CF2=

A·B

+

B·CCombinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)多输出函数的最小化ABCF1F2ABC

00

01

11

1001111ABC

00

01

11

1001111F1=

A’·B’

+A’·B·CF2=

A·B

+

A’·B·CCombinational-Circuit

SynthesisKarnaugh

Maps

(卡诺图)“Don’t-Care”

Input

Combinations(“无关”输入组合)有时组合电路的输出和某些输入组合无关F

=

A,B,C,D(1,2,3,5,7)

+

d(10,11,12,13,14,15)CDAB00

01

11

10000111ddd

dd

d10

11

11

1F=

A’·D

+

B’·CA’·DB’·Cd

集（d-set）Combinational-Circuit

SynthesisRepresentations

of

Combinational

Logic

CircuitsTruthTableLogicExpressionMinterm

ListMaxterm

ListKarnaugh

MapLogic

DiagarmWaveform

DiagramCanonical

SumCanonical

ProductMinimal

ExpressionOtherFormsTimingHazardsTerms竞争（Race）：在组合电路中，信号经由不同的途径达到某一会合点的时间有先有后，这种现象称为竞争。（Hazard）：由于竞争而引起电路输出发生瞬间错误现象称为 。表现为输出端出现了原设计中没有的窄脉冲，常称其为毛刺。竞争与

的关系：有竞争不一定会产生

，但有就一定有竞争。TimingHazardsStatic

HazardsGlitch(尖峰)AA’FAFA’Static-1

Hazards

(静态1型

)Logic

DiagramTiming

Diagram主要存在于“与－或”电路中当在某输入条件下，输出端能简化成：F

=

(A·A’)’

=

A+A’，则存在静态1型

.一级延迟TimingHazardsStatic

HazardsLogic

DiagramTiming

DiagramStatic-1

Hazards

(静态1型

)Example=1=1存在静态1型

！TimingHazardsStatic

Hazards当在某输入条件下，输出端能简化成：F

=

(A+A’)’

=

A·A’

，则存在静态0型

.Static-0

Hazards

(静态0型

)Logic

DiagramTiming

DiagramAFA’Glitch(尖峰)AA’F一级延迟主要存在于“或－与”电路中TimingHazardsStatic

Hazards=0=0=0Static-0