數(shù)字邏輯設計及應用教學英文課件：Lec08-Chap4

1、1,Digital Logic Design and ApplicationLecture #08,Combinational-Circuit Synthesis,UESTC, Spring 2011,2,4.3 Combinational-Circuit Synthesis,Design（設計）: from informal description to logic diagram 從非正式描述（如文字描述）到邏輯電路圖 Synthesis（綜合）: from formal description to logic diagram 從正式描述（標準表達）到邏輯電路圖,Synthesis,Mi

2、nimization or transformation Circuit Manipulations, obtain the logic circuit select devices,4.3 Combinational-Circuit Synthesis,定義輸入輸出信號 標準表達 Truth table Logic function/expression 文字描述,3,如，4.3.1 警報電路的描述,4.3.1 Circuit Description and design,4,1. Circuit Description: Inputs: Red, Yellow, Green corresp

3、ond to the state of three lights light1, dark0 Output: Fault normal state0, abnormal state1,Example: Design a circuit to check the state of traffic lights.,5,Example: Design a circuit to check the state of traffic lights.,1 1 1 1 1,1. Circuit Description: Inputs: Red, Yellow, Green correspond to the

4、 state of three lights light1, dark0 Output: Fault normal state0, abnormal state1,6,1. Circuit Description,2. Write logic expression and minimization,= RYG + RY + RG + YG,F =A,B,C(1,2,4 ) = (R+Y+G)(R+Y+G)(R+Y+G),( ),= (RYG) (RY) (RG) (YG),3. Circuit Manipulation four AND gates A+A=1,Y = AB + AB + BC

5、 + BC,= AB + AB(C+C) + BC +BC(A+A),= AB + ABC + ABC + BC + ABC + ABC,= AB,+ AC,+ BC,Y = AB + AB + BC + BC,= AB + AB + AC + BC + BC + AC,= AB + AC + BC,可以添加 AC,結果不唯一，但代價相同,16,4.3.4 Karnaugh Maps,a graphical representation of a logic functions truth table,卡諾圖是變形的真值表 每一個單元都對應于一個最小項（最大項）,Gray Code,17,4.

6、3.4 Karnaugh Maps,F = (A,B,C)(0,3,5,6),1-cell minterm 0-cell maxterm,18,F1 = (A,B,C) (1,3,4,7) F2(A,B,C) = AC + BCD + B,Example: Draw the K-maps for the following functions,Plot 1s corresponding to miniterms of function Plot 0s corresponding to maxterms of function,19,4.3.5 Minimizing Sum of Product

7、s,Adjacent（邏輯相鄰） A cell and its immediately adjacent neighbors differ only in one variable. Combining adjacent cells,i literals can be eliminated from 2i adjacent cells 合并2i 個單元可消去i個變量。,T10 組合律 項X + 項X = 項,用Gray Code保證卡諾圖相鄰單元的邏輯相鄰性,XYZ+XYZ=YZ,XY,20,one literal can be eliminated from two adjacent 1-c

8、ells,XYZ + XYZ = YZ,21,ABCD,= ABD,+ ABCD,+ ABCD,+ ABCD,+ ABD,= BD,Two literals can be eliminated from four adjacent cells.,22,A,D,消掉既能為 0 也能為 1 的變量 保留始終為0或始終為1的變量,Three literals can be eliminated from eight adjacent cells.,T10 組合律 項X + 項X = 項,23,Example: F = A,B,C,D ( 0, 2, 3, 5, 7, 8, 10, 11, 13 ),

9、1. Drawing map,2. Circling adjacent cells area of circle: as large as possible number of circle: as few as possible cells can be reused,3. Write terms,F(A,B,C,D) = BD + BC + BCD + ABD,BD,BC,4.3.5 Minimizing Sum of Products,24,問題：圈組時是否需要考慮順序？ 先圈大的還是小的？,4.3.5 Minimizing Sum of Products,25,4.3.5 Minimi

10、zing Sum of Products Terminologies for 2-level simplification,P implies F(P隱含F(xiàn)), F includes P ( F covers P F覆蓋P),prime implicant (主蘊涵項) circled sets and corresponding product terms A minimal sum is a sum of prime implicants. ( Prime-Implicant Theorem )最小和是主蘊涵項 之和。 The sum of all the prime implicants

11、 of a logic functions is called the complete sum. 所有主主蘊涵項 之和稱為完全和。,P1(A,B,C) = ABC P2(A,B,C) = BC F1(A,B,C) = AB + BC,P = A,B,C (1,3,6) F = A,B,C (1,3,5,6,7),26,Terminologies,Distinguished 1-cell （奇異“1”單元） An input combination that is covered by only one prime implicant.,Essential prime implicant 質主

12、蘊涵項 A prime implicant that covers one or more distinguished 1-cell.,無法被重復“圈”的1,27,Terminologies,Distinguished 1-cell （奇異“1”單元）,Begin with distinguished 1-cell,Essential prime implicant 質主蘊涵項,28,Example: F = A,B,C,D ( 0, 1, 2, 3, 4, 5, 7, 14, 15 ),1. Drawing map,2. Circling adjacent cells,circling es

13、sential prime implicant,circling other 1-cells,3. Write terms, one per circled set,F(A,B,C,D) = AB + AC + AD + ABC,marking distinguished 1-cell,Eliminating the variable which is 0 as well as 1 Keeping the variable which is always 0 or 1,29,For some logic functions, the minimal expressions may be dif

14、ferent, but the minimal forms are equally costly. 最小和可能不唯一，但代價相同,30,No distinguished 1-cell and essential prime implicant,Dont repeat circle!,In each circle, there is at least ONE NEW 1-cell. 每個圈至少含有一個未被圈過的“1”單元。,31,Approach for K-map algorithm,Draw map Combine adjacent cells Mark distinguished 1-ce

15、lls Circle essential prime implicant, then circle other cell Cells can be reused, but each circle must have new cell. Ensure the areas of circle as large as possible Ensure the number of circle as few as possible Write the minimal sum Eliminating the variable which is 0 as well as 1 Keeping the vari

16、able which is always 0 or 1 Sum-of-Product: 1variable; 0(variable),How to minimize product of sums,Minimizing Products of Sums,32,0 variable 1 (variable),A+B,A+C,F = (A+B+C+D)(A+C)(A+B),4.3.6 Other minimization problems,33,4.3.6 Other minimization problems,“Dont-Care” Input Combinations（無關項處理） Outpu

17、t doesnt matter for certain inputs combinations Dont care about behavior under these inputs (out-of-range) F = A,B,C,D(1,2,3,5,7) + d(10,11,12,13,14,15),F = AD + BC,AD,BC,34,4.3.6 Other minimization problems,F1 = A,B,C (0,1,3) F2 = A,B,C (3,6,7),F1 = AB + AC,F2 = AB + BC,Multiple-Output Minimization

18、（多輸出最小化）,35,Multiple-Output Minimization,F1 = AB + ABC,F2 = AB + ABC,36,A 5-variable Karnaugh Map,16 17 19 18,20 21 23 22,28 29 31 30,24 25 27 26,How to minimize?,37,F = A,B,C,D,E(0,1,2,3,4,5,10,11,14,20,21,24,25,26,27,28,29,30),F = + + + +,ABD,ACD,ACD,ABC,BDE,Task: 4.59 (b),38,A 6-variable K-Map,39,Real-World Logic Design,Lots more than 6 inputs - cant use Karnaugh maps Design co