數(shù)字邏輯設(shè)計及應(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ù)邏輯的概念與對偶關(guān)系、反演關(guān)系、香農(nóng)展開定理，以及在邏輯代數(shù)化簡時的作用；掌握:邏輯函數(shù)的表達(dá)形式：積之和與和之積標(biāo)準(zhǔn)型、真值表、卡諾圖、最小邏輯表達(dá)式之間的關(guān)系；掌握:組合電路的分析：窮舉法和代數(shù)法；卡諾圖化簡方法；掌握:組合電路的綜合過程：將功能敘述表達(dá)為組合邏輯函數(shù)的表達(dá)形式、使用與非門、

2、或非門表達(dá)的邏輯函數(shù)表達(dá)式、邏輯函數(shù)的最簡表達(dá)形式及綜合設(shè)計的其他問題：無關(guān)項(dont-care terms)的處理。理解：邏輯函數(shù)表達(dá)式的基本化簡方法函數(shù)化簡方法；多輸出(multiple-output)邏輯化簡的方法和定時冒險（timing hazards）問題。了解：組合邏輯電路和時序邏輯電路的基本概念；邏輯代數(shù)化簡時的幾個概念：蘊含項（implicant）、主蘊含項（prime implicant）、奇異“ 1 ”單元（distinguished 1-cell )、質(zhì)主蘊含項(essential prime implicant);五變量及以上邏輯函數(shù)卡諾圖化簡方法；了解：開集（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 (撇號)為邏輯非操作符;表達(dá)式Y(jié)=x， 表示信號Y與x之

5、間的邏輯關(guān)系;邏輯加操作符“+”，有些地方用“ ”“ or”表示;邏輯乘操作符“”，有些地方用“& ”“ and”表示;優(yōu)先級:邏輯非邏輯乘邏輯加。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(互補律): 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 錯！錯！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 對偶 二、三變量定理 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 的地方都用另一個表達(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門實現(xiàn)NOR功能?邏輯功能的電路實現(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 互補率Example2: Prove (AB + AC) = AB + AC4.1.4 n-Variable Theorems n變量定理 T12T154.1.5 Duality (對偶性)Duality Rule , 0 1 Keep the previous priority 對任意邏輯表達(dá)式，將其中的“或”“與”操作對換，“0”“1”對換，并保持原來的邏輯優(yōu)先級不變，得到新的等式仍然成立。新的等式FD稱為F的對偶式。18 FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ) 回顧公理、定

13、理對偶的性質(zhì)0D=1，1D=0；變量XD=X；對函數(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 (對偶性)Counterexample: 優(yōu)先級的處理 X+XY = XXX+Y = X X+Y = XX(X

14、+Y) = X204.1.5 Duality (對偶性)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 (對偶性)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 (對偶性)Duality: FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , , Xn , , + , ) The relation between the positive-logic convention and the negative-logic convention is duality.正邏輯與負(fù)邏輯之間是對偶的關(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對偶4.1.5 Duality (對偶性)由于正負(fù)邏輯之間的對偶關(guān)系使得：邏輯電路（circuit）有不唯一的描述（解釋）形式邏輯功能（function）有不唯一的實現(xiàn)形式23唯一的電氣特性 (H and L level)唯一的truth Table4.1.5 Duality (對偶性)采用不同的邏輯體制描述同一個數(shù)字電路（circuit）24Example：某個數(shù)字電路電氣特性如下表，用正邏輯描述（解釋），其邏輯表達(dá)式和邏輯電路圖如下所示。請給出用負(fù)邏輯描述的表達(dá)式和電路圖。Positive logicF=AB+CABFCNegative

17、logicF=(A+B)CABFC4.1.5 Duality (對偶性)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采用不同的邏輯體制來實現(xiàn)同一種邏輯功能Use 3 NMOS to build the electric circuitExample：某數(shù)字電路完成的邏輯功能如真值表所示，若分別用正/負(fù)邏輯體制實現(xiàn)，給出其邏輯電路圖和電路圖。4.1.5 Duality (對偶性)采用不同的邏輯體制來實現(xiàn)同一種邏輯功能26Example

18、：某邏輯電路需要完成的邏輯功能如真值表所示，分別用正/負(fù)邏輯體制實現(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 (對偶)and Complement獲得任意函數(shù)的反函數(shù)的方法通過對的對偶函數(shù)求非，且對偶函數(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 (對偶性) and Complement由于對偶關(guān)系的存在，一旦得到積之和的表達(dá)式綜合出二級與-或電路，就可以很方便的得到和之積表達(dá)式并綜合出二級或-與邏輯電路。28Positive logicF=AB+CABFCPositive logic=（F（ A，B）And-OR circuitO

20、R- And circuit4.1.5 Duality (對偶性) 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(乘積項): PQRS

21、um term(求和項): 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)項（normal term）：一個乘積或求和項，每個變量只出現(xiàn)一次；非標(biāo)準(zhǔn)項可以化為標(biāo)準(zhǔn)項。n變量

22、最小項（Miniterm）：具有n個變量的標(biāo)準(zhǔn)乘積項；n變量最大項（Maxterm）：具有n個變量的標(biāo)準(zhǔn)求和項；31F (A,B ) = AB+AF (A,B ) = AB+AB+AB3變量：ABC，A BC，任何非標(biāo)準(zhǔn)項都可以化為最大或最小項。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è)計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、式二級電路實現(xiàn)方式literalproduct term乘積項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求和項P

25、roduct-of-Sums expression“和之積”表達(dá)式“或-與”式二級電路實現(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的乘積項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實際上是挑選取1的Miniterm

27、集合來描述邏輯函數(shù)384.1.6 Standard Representations of Logic FunctionsMinterm (最小項) 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的求和項

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實際上是挑選取0的Maxterm集合來描述邏輯函數(shù)414.1.6 Standard Representations of Logic Functions Maxterms (最大項) 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)項都可以化為最大或最小項，因此可以用最大項之積或最小項之和來表示任意邏輯函數(shù)。邏輯函數(shù)的互斥二值取值；取1的Miniterm之和描述了邏輯函數(shù)取1的所有情況；取0的Maxterm之積描述了邏輯函數(shù)取0的情況；采取哪種描述形式視簡便而定。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