數(shù)字邏輯設(shè)計(jì)及應(yīng)用教學(xué)英文課件：Lec06-Chap 4

1、1Digital Logic Design and Application Lecture #6UESTC, Spring 2011Chapter 4 Combinational Logic Design PrinciplesBasic Logic Algebra學(xué)習(xí)要求掌握:邏輯代數(shù)的公理、定理，正負(fù)邏輯的概念與對(duì)偶關(guān)系、反演關(guān)系、香農(nóng)展開定理，以及在邏輯代數(shù)化簡(jiǎn)時(shí)的作用；掌握:邏輯函數(shù)的表達(dá)形式：積之和與和之積標(biāo)準(zhǔn)型、真值表、卡諾圖、最小邏輯表達(dá)式之間的關(guān)系；掌握:組合電路的分析：窮舉法和代數(shù)法；卡諾圖化簡(jiǎn)方法；掌握:組合電路的綜合過程：將功能敘述表達(dá)為組合邏輯函數(shù)的表達(dá)形式、使用與非門、

2、或非門表達(dá)的邏輯函數(shù)表達(dá)式、邏輯函數(shù)的最簡(jiǎn)表達(dá)形式及綜合設(shè)計(jì)的其他問題：無關(guān)項(xiàng)(dont-care terms)的處理。理解：邏輯函數(shù)表達(dá)式的基本化簡(jiǎn)方法函數(shù)化簡(jiǎn)方法；多輸出(multiple-output)邏輯化簡(jiǎn)的方法和定時(shí)冒險(xiǎn)（timing hazards）問題。了解：組合邏輯電路和時(shí)序邏輯電路的基本概念；邏輯代數(shù)化簡(jiǎn)時(shí)的幾個(gè)概念：蘊(yùn)含項(xiàng)（implicant）、主蘊(yùn)含項(xiàng)（prime implicant）、奇異“ 1 ”單元（distinguished 1-cell )、質(zhì)主蘊(yùn)含項(xiàng)(essential prime implicant);五變量及以上邏輯函數(shù)卡諾圖化簡(jiǎn)方法；了解：開集（on-

3、set）、閉集(off-set)的概念；23Basic ConceptsTwo types of logic circuits:combinational logic circuitsequential logic circuitOutputs depend only on its current inputs.Outputs depends not only on the current inputs but also on the past sequence of inputs.A combinational circuit dont contain feedback loops whic

4、h generally create sequential circuit behavior.4.1 Switching Algebra454.1 Switching Algebra4.1.1 Axioms (公理)A1: X = 0, if X 1X = 1, if X 0A2: 0 = 11 = 0A3: 00 = 01+1 = 1A4: 11 = 10+0 = 0A5: 01 = 10 = 01+0 = 0+1 = 1a.k.a. “Boolean algebra”數(shù)字抽象基本邏輯門的輸出4.1 Switching Algebra (撇號(hào))為邏輯非操作符;表達(dá)式Y(jié)=x， 表示信號(hào)Y與x之

5、間的邏輯關(guān)系;邏輯加操作符“+”，有些地方用“ ”“ or”表示;邏輯乘操作符“”，有些地方用“& ”“ and”表示;優(yōu)先級(jí):邏輯非邏輯乘邏輯加。6F = 0 + 1 ( 0 + 1 0 ) = 0 + 1 1= 074.1.2 Single-Variable TheoremsIdentities(自等律): X+0=XX1=XNull Elements(0-1律): X+1=1X0=0Involution(還原律): ( X ) = XIdempotency(同一律): X+X=XXX=XComplements(互補(bǔ)律): X+X=1XX=0The relationship between

6、 variable and constantThe relationship between variable and itself單變量定理 T1T5所有定理都可以通過完全歸納法來證明!84.1.3 Two- and Three-Variable TheoremsSimilar relationships with general algebraCommutativity (交換律) AB = BAA+B = B+AAssociativity (結(jié)合律) A(BC) = (AB)CA+(B+C) = (A+B)+CDistributivity (分配律) AB+BC=A(B+C) A+BC

7、= (A+B)(A+C)These theorems can be proved by truth table.二、三變量定理 T6T89Notices不存在變量的指數(shù) AAA A3沒有定義除法 if AB=BC A=C ? 沒有定義減法 if A+B=A+C B=C ?A=1, B=0, C=0AB=AC=0, ACA=1, B=0, C=1 A+B=A+C, BC 錯(cuò)！錯(cuò)！104.1.3 Two- and Three-Variable TheoremsCovering (吸收律)X + XY = X X(X+Y) = XCombining (組合律)XY + XY = X (X+Y)(X+

8、Y) = XConsensus (添加律/一致性定理)XY + XZ + YZ = XY + XZ(X+Y)(X+Z)(Y+Z) = (X+Y)(X+Z)Some Special Relationships 對(duì)偶 二、三變量定理 T9T1111(X+Y) + (X+Y) = 1A + A = 1XY + XY = X(A+B)(A(B+C) + (A+B)(A(B+C) = (A+B)代入定理： 在含有變量 X 的邏輯等式中，如果將式中所有出現(xiàn) X 的地方都用另一個(gè)表達(dá)式 F 來代替，則等式仍然成立。124.1.4 n-Variable Theorems n變量定理 T12T15General

9、ized idempotency theorem 廣義同一律X + X + + X = X X X X = XShannons expansion theorem 香農(nóng)展開定理F(X1, X2, , Xn)= X1 F(1,X2,Xn) + X1 F(0,X2,Xn)= X1 + F(0,X2,Xn) X1 + F(1,X2,Xn) N變量定理能夠使用有限歸納法來證明!How to prove?13To prove: AD + AC + CD + ABCD = AD + AC= A ( 1D + 1C + CD + 1BCD ) + A ( 0D + 0C + CD + 0BCD )= A (

10、 D + CD + BCD ) + A ( C + CD )= AD+ AC144.1.4 n-Variable TheoremsDeMorgans Theorem 摩根定理 T13 Complement Theorem 反演定理 (A B) = A + B(A + B) = A Bn變量定理 T12T15Xi可以是任意表達(dá)式15DeMorgan SymbolsQuiz: 如何用NAND門實(shí)現(xiàn)NOR功能?邏輯功能的電路實(shí)現(xiàn)的多樣性164.1.4 n-Variable Theorems n變量定理 T12T15Complement of a logic expression: , 0 1, Co

11、mplementing all VariablesKeep the previous priorityNotice the out of parenthesesExample1: Write the complement function for each of the following logic functions.F1 = A(B+C)+CDF2 = (AB)+CDEExample2: Prove that (AB + AC) = AB + ACF1 = (A+BC)(C+D)F2 = AB(C+D+E)17(A+B)(A+C) 反演定理AA +AC + AB + BC 結(jié)合律AC +

12、 AB 一致律 AC + AB + BC 互補(bǔ)率Example2: Prove (AB + AC) = AB + AC4.1.4 n-Variable Theorems n變量定理 T12T154.1.5 Duality (對(duì)偶性)Duality Rule , 0 1 Keep the previous priority 對(duì)任意邏輯表達(dá)式，將其中的“或”“與”操作對(duì)換，“0”“1”對(duì)換，并保持原來的邏輯優(yōu)先級(jí)不變，得到新的等式仍然成立。新的等式FD稱為F的對(duì)偶式。18 FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ) 回顧公理、定

13、理對(duì)偶的性質(zhì)0D=1，1D=0；變量XD=X；對(duì)函數(shù)F，G有：（F+G）D= FDGD；（F G）D= FD+ GD（F D ）D=F若F=G，則FD =GD 19Example: Write the Duality function for each of the following Logic functions. F1 = A+B(C+D)F2 = ( A(B+C) + (C+D) )F1D = A(B+CD)F2D = ( (A+BC) (CD) )4.1.5 Duality (對(duì)偶性)Counterexample: 優(yōu)先級(jí)的處理 X+XY = XXX+Y = X X+Y = XX(X

14、+Y) = X204.1.5 Duality (對(duì)偶性)Principle of Duality Any logic equation remains true if the duals of it is true. 證明公式：A+BC = (A+B)(A+C)A(B+C)AB+AC214.1.5 Duality (對(duì)偶性)Write the duality and complement function for each of the following logic functions. F1 = A(B+C) + CD F2 = ( A(B+C) + (C+D) )224.1.5 Dual

15、ity (對(duì)偶性)Duality: FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ) The relation between the positive-logic convention and the negative-logic convention is duality.正邏輯與負(fù)邏輯之間是對(duì)偶的關(guān)系G1ABFA B FL L LL H LH L LH H Helectrical functionA B F0 0 00 1 01 0 01 1 1positive logicA B F1 1 11 0 10 1 10 0 0n

16、egative logicF = ABF = A+B對(duì)偶4.1.5 Duality (對(duì)偶性)由于正負(fù)邏輯之間的對(duì)偶關(guān)系使得：邏輯電路（circuit）有不唯一的描述（解釋）形式邏輯功能（function）有不唯一的實(shí)現(xiàn)形式23唯一的電氣特性 (H and L level)唯一的truth Table4.1.5 Duality (對(duì)偶性)采用不同的邏輯體制描述同一個(gè)數(shù)字電路（circuit）24Example：某個(gè)數(shù)字電路電氣特性如下表，用正邏輯描述（解釋），其邏輯表達(dá)式和邏輯電路圖如下所示。請(qǐng)給出用負(fù)邏輯描述的表達(dá)式和電路圖。Positive logicF=AB+CABFCNegative

17、logicF=(A+B)CABFC4.1.5 Duality (對(duì)偶性)25A B F0 0 00 1 01 0 01 1 1Truth TableA B FL L LL H LH L LH H HPositive logicelectrical functionF=A BABF采用不同的邏輯體制來實(shí)現(xiàn)同一種邏輯功能Use 3 NMOS to build the electric circuitExample：某數(shù)字電路完成的邏輯功能如真值表所示，若分別用正/負(fù)邏輯體制實(shí)現(xiàn)，給出其邏輯電路圖和電路圖。4.1.5 Duality (對(duì)偶性)采用不同的邏輯體制來實(shí)現(xiàn)同一種邏輯功能26Example

18、：某邏輯電路需要完成的邏輯功能如真值表所示，分別用正/負(fù)邏輯體制實(shí)現(xiàn)，給出其邏輯電路圖和電路圖。A B F0 0 00 1 01 0 01 1 1Truth TableA B FH H HH L HL H HL L LNegative logicelectrical functionF=A + BABFUse 3 PMOS to build the electric circuitF=A B4.1.5 Duality (對(duì)偶)and Complement獲得任意函數(shù)的反函數(shù)的方法通過對(duì)的對(duì)偶函數(shù)求非，且對(duì)偶函數(shù)自變量為的反變量；27Complement: F(X1 , X2 , , Xn) =

19、 FD(X1 , X2, , Xn ) F(X1 , X2 , , Xn) = FD(X1 , X2, , Xn ) A B F0 0 00 1 01 0 01 1 1positive logicF = ABF = ABF = AB =F （ A，B） =（F （ A，B）ABFC4.1.5 Duality (對(duì)偶性) and Complement由于對(duì)偶關(guān)系的存在，一旦得到積之和的表達(dá)式綜合出二級(jí)與-或電路，就可以很方便的得到和之積表達(dá)式并綜合出二級(jí)或-與邏輯電路。28Positive logicF=AB+CABFCPositive logic=（F（ A，B）And-OR circuitO

20、R- And circuit4.1.5 Duality (對(duì)偶性) and Complement29304.1.6 Logic Function and its RepresentationsSome definitionsLiteral(文字): a variable or its complement such as X, X, CS_LExpression(表達(dá)式): literals combined by AND, OR, parentheses, complementation( FREDZ + CS_LABC + Q5 )RESET Product term(乘積項(xiàng)): PQRS

21、um term(求和項(xiàng)): X+Y+ZSum-of-products expression(積之和表達(dá)式): A + BC + ABC Product-of-sums expression (和之積表達(dá)式): (B+C) (A+B+C)Equation(方程/函數(shù)): Variable = expressionP = ( FREDZ + CS_LABC + Q5)RESET 4.1.6 Logic Function and its RepresentationsSome definitions標(biāo)準(zhǔn)項(xiàng)（normal term）：一個(gè)乘積或求和項(xiàng)，每個(gè)變量只出現(xiàn)一次；非標(biāo)準(zhǔn)項(xiàng)可以化為標(biāo)準(zhǔn)項(xiàng)。n變量

22、最小項(xiàng)（Miniterm）：具有n個(gè)變量的標(biāo)準(zhǔn)乘積項(xiàng)；n變量最大項(xiàng)（Maxterm）：具有n個(gè)變量的標(biāo)準(zhǔn)求和項(xiàng)；31F (A,B ) = AB+AF (A,B ) = AB+AB+AB3變量：ABC，A BC，任何非標(biāo)準(zhǔn)項(xiàng)都可以化為最大或最小項(xiàng)。3變量：A+B+C，A+ B+C，324.1.6 Logic Function and its Representations舉重裁判電路Y = F (A,B,C ) = A(B+C)ABYC&1ABCYLogic Circuit開關(guān)ABC:1-閉合指示燈Y:1-亮000001110 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1

23、1 1 0 1 1 1 ABCYTruth TableLogic Equation 4.1.6 Logic Function and its Representations邏輯函數(shù)的描述方式真值表(Truth table)邏輯代數(shù)表達(dá)式(Logic Function/ Equation)邏輯電路圖(Logic circuit)33分析設(shè)計(jì)34Y = A + BC + ABC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ABCBCABCY110000000111111000000100Sum-of-Products expression“積之和”表達(dá)式“與-或”

24、式二級(jí)電路實(shí)現(xiàn)方式literalproduct term乘積項(xiàng)11114.1.6 Logic Function and its RepresentationsLogic Expression Truth Table邏輯函數(shù)真值表4.1.6 Logic Function and its RepresentationsLogic Expression Truth Table邏輯函數(shù)真值表35Y = (B+C) (A+B+C)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ABCB+CA+B+CY001111111111111111110000sum term求和項(xiàng)P

25、roduct-of-Sums expression“和之積”表達(dá)式“或-與”式二級(jí)電路實(shí)現(xiàn)方式4.1.6 Standard Representations of Logic FunctionsTruth table logic function真值表邏輯函數(shù)36ABC1 variable0 (variable)product terms: 0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 01 1 0 01 1 1 0ABCFTruth TableA product term that is 1 in exactly one row of the truth t

26、able真值表中使某行為1的乘積項(xiàng)minterm*F = ABC37Canonical Sum（標(biāo)準(zhǔn)和）: a sum of mintermsOn-Set開集0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0ABCF00010000F1= + +00000100F200000010F3F = ABC + ABC + ABC= A,B,C(3,5,6)MintermListm0m1m2m3m4m5m6m74.1.6 Standard Representations of Logic Functions實(shí)際上是挑選取1的Miniterm

27、集合來描述邏輯函數(shù)384.1.6 Standard Representations of Logic FunctionsMinterm (最小項(xiàng)) An n-variable minterm is a normal product term with n literals.There are 2n such product terms.The sum of all minterms is 1.The product of any two different product-terms is 0.ABCABCABCABCABCABCABCABC0 0 00 0 10 1 00 1 11 0 01

28、 0 11 1 01 1 1ABCMinitermTruth table logic function真值表邏輯函數(shù)Truth Table394.1.6 Standard Representations of Logic Functions11101111G(ABC) = A+B+CF = ABCG = A+B+C0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 01 1 0 01 1 1 0ABCFTruth TableA sum term that is 0 in exactly one row of the truth table真值表中使某行為0的求和項(xiàng)

29、maxterm *0 variable1 (variable)sum terms: 40Canonical Product （標(biāo)準(zhǔn)積） : a product of maxterms0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 11 0 1 11 1 0 11 1 1 0ABCF01111111F1= 11101111F211111110F3F = (A+B+C)(A+B+C)(A+B+C)= A,B,C(0,3,7)Off-Set閉集MaxtermListM0M1M2M3M4M5M6M74.1.6 Standard Representations of Logic Fu

30、nctions實(shí)際上是挑選取0的Maxterm集合來描述邏輯函數(shù)414.1.6 Standard Representations of Logic Functions Maxterms (最大項(xiàng)) An n-variable maxterm is a normal sum term with n literals. There are 2n such sum terms.The product of all maxterms is 0.The sum of any two different sum-terms is 1.A+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA

31、+B+C0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ABCMaxtermTruth table logic function真值表邏輯函數(shù)42ABCABCABCABCABCABCABCABCmintermm0m1m2m3m4m5m6m70 0 0 00 0 1 10 1 0 20 1 1 31 0 0 41 0 1 51 1 0 61 1 1 7ABCrowA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CA+B+CM0M1M2M3M4M5M6M7maxtermProduct term:0 (variable)1 variableSum

32、term:1 (variable)0 variable Mi = mi ； mi = Mi ；Why does every logic function can be written as a canonical sum or a canonical product?為什么任何邏輯函數(shù)都可以表示為標(biāo)準(zhǔn)積或者標(biāo)準(zhǔn)和的形式？任何非標(biāo)準(zhǔn)項(xiàng)都可以化為最大或最小項(xiàng)，因此可以用最大項(xiàng)之積或最小項(xiàng)之和來表示任意邏輯函數(shù)。邏輯函數(shù)的互斥二值取值；取1的Miniterm之和描述了邏輯函數(shù)取1的所有情況；取0的Maxterm之積描述了邏輯函數(shù)取0的情況；采取哪種描述形式視簡(jiǎn)便而定。4.1.6 Standard Representations of Logic FunctionsAny logic function can be written as a canonical sum.44Example: Write the canonical sum for the following function: F(A,B,C) = AB +ACUsing theorem: X + X = 1F(A,B,C) = AB + AC = AB(C+C) + AC(B+B) = ABC + ABC + ABC + ABC1 1 11 1 00 1 10 0 1= A,B,C