2015下数字逻辑设计第三章

1、Digital DesignDigital Design Pinciples and Practices Pinciples and PracticesDigital DesignDigital Design Pinciples and Practices Pinciples and PracticesCombinational Logic CircuitIts outputs depend only on its current inputs.Its outputs depend not only on the current inputs, but also on the past seq

2、uence of inputs.Logic CircuitSequential Logic CircuitQ: How to design better ? Q: How to design better ? A: Theory can guide practice.A: Theory can guide practice.Switching AlgebraGeorge Boole (1815 1864) Boolean Algebra1854 True FalseClaude Elwood Shannon(1916 2001) Switching Algebra1938 OnOffFor R

3、elay LogicSwitching AlgebraBasic Value Basic OperationAND ( ) , OR ( + ), NOT ( )1 / 0Switching Algebra Axioms(A1) If X 1, then X = 0 (A1) If X 0, then X = 1(A2) If X = 0, then X = 1 (A2) If X = 1, then X = 0(A3) 00 = 0 (A3) 1+1 = 1(A4) 11 = 1 (A4) 0+0 = 0(A5) 01 = 10 = 0 (A5) 1+0 = 0+1 = 1PairNote:

4、 They are not Arithmetic, but Logic.Switching Algebra Single-Variable Theorems (T1) X+0 = 0+X = X (T1) X1 = 1.X = X (Identities, 自等律自等律)(T2) X+1 = 1+X = 1 (T2) X0 = 0.X = 0 (Null Elements, 0-1律律) (T3) X+X = X (T3) XX = X (Idempotency, 同一律同一律) (T4) (X) = X (Involution, 还原律还原律) (T5) X+X = 1 (T5) XX =0

5、 (Complements, 互补律互补律) 变量和常量变量和常量的关系的关系变量和自身变量和自身的关系的关系Theorems are derived from AxiomsThey can be proved by Perfect Induction.(Such as Truth Table)Switching Algebra Two-and-Variable Theorems (T6) X+Y = Y+X (T6) XY= YX (Commutativity, 交换律交换律) Prove T6: If X = 0, according to T1 . If X = 1, according

6、 to T2 . The same proving way to T6.(T7) (X+Y)+Z = X+(Y+Z) (T7) (XY)Z = X (YZ) (Associativity, 结合律结合律) Prove T7: If X = 0, according to T1 . If X = 1, according to T2 . The same proving way to T7.They can also be proved by Perfect Induction.(Such as Truth Table)Switching Algebra Two-and-Variable The

7、orems (T8) XY+XZ = X(Y+Z) (T8) (X+Y)(X+Z) = X+YZ (Distributivity, 分配律分配律) Prove T8, T8: If X = 0, . If X = 1, . (T9) X+XY = X (T9) X(X+Y) = X (Covering, 吸收律吸收律) Prove T9, T9: If Y = 0, . If Y = 1, . Another way to T9: X+XY = X1+XY (According to T1) = X(1+Y) = X (According to T8, T2, T1) Another way

8、to T9: X(X+Y) = XX+XY (According to T8) = X+XY = X (According to T3, T9)They can also be proved by Perfect Induction.(Such as Truth Table)Switching Algebra Two-and-Variable Theorems (T10) XY + XY = X (T10) (X+Y)(X+Y) = X (Combining, 组合律组合律) Prove T10, T10: If X = 0, . If X = 1, . Another way to T10:

9、 XY + XY = X(Y+Y) (According to T8) = X1 = X (According to T5, T1) Another way to T10: (X+Y)(X+Y) = X+YY (According to T8) = X+0 = X (According to T5, T1)They can also be proved by Perfect Induction.(Such as Truth Table)Switching Algebra Two-and-Variable Theorems (T11) XY + XZ + YZ = XY + XZ (T11) (

10、X+Y)(X+Z)(Y+Z) = (X+Y)(X+Z) (Consensus,一致律一致律添加律添加律) Prove T11, T11: If X = 0, . If X = 1, . Another way to T11: If YZ = 0, YZ is redundant. (According to T1) If YZ = 1, then Y=Z=1 (According to A4) Left = XY+XZ+1=1 (According to T2) Right = X1+X1=X+X=1 (According to T1, T5) One more way to T11: Lef

11、t = XY + XZ + 1YZ (According to T1) = XY + XZ + (X+X)YZ (According to T5) = XY + XZ + XYZ + XYZ (According to T8) = XY(1+Z) + XZ(1+Y) (According to T8) = XY + XZ (According to T2, T1) Consensus(一致项一致项)How to prove T11 by the theorems?Switching Algebra Two-and-Variable Theorems Sum of Products (积之和积之

12、和)Example: V(W+X)(Y+Z) = (VW+VX)(Y+Z) (According to T8) = VWY+VXY+VWZ+VXZ (According to T8)Multiply out (乘开乘开)Product of Sums (和之积和之积)Example: VWX + YZ = (VWX+Y)(VWX+Z) (According to T8) = (VW+Y)(X+Y)(VW+Z)(X+Z) (According to T8) = (V+Y)(W+Y)(X+Y)(V+Z)(W+Z)(X+Z) (According to T8)Add out (加开加开)Switch

13、ing Algebra Two-and-Variable Theorems ExampleProve: X+XZ = X+Z = (X+X)(X+Z) (According to T8) = 1(X+Z) = X+Z (According to T5, T1)(A+B)(A(B+C) + (A+B)(A(B+C) = ?= A+B (According to T10) Switching Algebra Two-and-Variable Theorems Notes 开关代数中没有变量的指数开关代数中没有变量的指数 AAA A3 允许提取公因子允许提取公因子 AB+AC = A(B+C) 没有

14、定义除法没有定义除法 If AB = BC A=C ? e.g. If A=1, B=0, C=0 then AB=AC=0, but A C 没有定义减法没有定义减法 If A+B = A+C B=C ? e.g. If A=1, B=0, C=1 then A+B=A+C=1, but B C错！错！错！错！Switching Algebra n-Variable Theorems (T12) X+X+.+X = X(T12) XX . X = X (Generalized idempotency, 广义同一律广义同一律) Can be proved by Finite Induction

15、.(T13) (X1X2. Xn) = X1+X2+.+Xn(T13) (X1+X2+ .+Xn) = X1X2.Xn (DeMorgans theorems, 德德.摩根定理摩根定理) Can be proved by Finite Induction.(T14) F(X1, X2, . , Xn, +, ) = F(X1, X2, . , Xn, , +) (Generalized DeMorgans theorems, 广义德广义德.摩根定理摩根定理) Can be proved by DeMorgans theorems.DeMorgans theorems is also calle

16、d Complement Theorems (反演定理反演定理)Switching Algebra n-Variable Theorems Complement Rules (反演规则反演规则)Swapping + and (与或交换与或交换)Complementing all variables (变量取反变量取反)遵循原来的运算优先（遵循原来的运算优先（Priority）次序）次序不属于单个变量上的反号应保留不变不属于单个变量上的反号应保留不变 Switching Algebra n-Variable Theorems Example 1：Write the Complement func

17、tion for each of the following logic functions. (写出下面函数的反函数写出下面函数的反函数) F1 = A (B + C) + C D F1 = ? = (A + B C) (C + D) F2 = (A B) + C D E F2 = ? = (A + B) (C + D + E) = A B (C + D + E)Switching Algebra n-Variable Theorems Example 2：Prove (AB + AC) = AB + AC(AB + AC) = (A+B) (A + C) (According to T14

18、) = AA + AB + AC + BC (According to T8) = AB + AC + BC (According to T5, T1) = AB + AC (According to T11) Switching Algebra n-Variable Theorems Application of DeMorgans theorems(A B) = A + B(A + B) = A BNAND NOT-ORNOR NOT-ANDSwitching Algebra n-Variable Theorems (T15) F(X1, X2, . , Xn) = X1F(1, X2,

19、. , Xn) + X1F(0, X2, . , Xn) (T15) F(X1, X2, . , Xn) = X1+F(0, X2, . , Xn) X1+F(1, X2, . , Xn) (Shannons expansion theorems, 香农展开定理香农展开定理)香农展开定理主要用于证明等式或展开函数香农展开定理主要用于证明等式或展开函数,将函数展开一次将函数展开一次可以使函数内部的变量数从可以使函数内部的变量数从 n 个减少到个减少到 n-1 个。个。How to prove Shannons expansion theorems?Switching Algebra n-Vari

20、able Theorems Application of Shannons theoremsProve: AD + AC + CD + ABCD = AD + AC= A(1D+1C+CD+1BCD) + A(0D+0C+CD+0BCD) (According to T15)= A(D+CD+BCD)+A(C+CD) (According to A2, A2, T1, T2)= AD(1+C+BC)+AC(1+D) (According to T8)= AD + AC (According to T2, T1)Switching Algebra Duality Any theorem or i

21、dentity in Switching Algebra remains trueif 0 and 1 are swapped and . and + are swapped throughout. Principle of DualityLogic expression F(X1, X2, , Xn) = FD(X1, X2, , Xn) FD(X1 , X2 , , Xn , + , , ) = F(X1 , X2 , ,Xn , , + , ) Switching Algebra Duality 对偶规则对偶规则 + 0 1变换时不能破坏原来的运算顺序（优先级）变换时不能破坏原来的运算顺

22、序（优先级）对偶原理对偶原理 (Principle of Duality)若两逻辑式相等，则它们的对偶式也相等若两逻辑式相等，则它们的对偶式也相等.Switching Algebra Duality Example例：例： 写出下面函数的对偶函数写出下面函数的对偶函数 F = A + B (C + D) G = (A (B+C) + (C+D) X + X Y = X X X + Y = X (错错)X ( X + Y ) = X (正确正确) Switching Algebra Duality ExampleProve T8：A+BC = (A+B)(A+C)A(B+C)AB+AC定理定理

23、Tx 和和 Tx 为对偶关系为对偶关系对偶式对偶式对偶式对偶式=T8Switching Algebra Duality Tpye1ABFElectrical FunctionTable (电气功能表电气功能表)A B FL L LL H LH L LH H HPositive-LogicConventionA B F0 0 00 1 01 0 01 1 1Negative-LogicConventionA B F1 1 11 0 10 1 10 0 0L: Low LevelH: High LevelThe relationship of Positive-Logic Convention a

24、nd Negative-Logic Convention are Duality. ( (正逻辑约定和负逻辑约定互为对偶关系正逻辑约定和负逻辑约定互为对偶关系) )ABFTpye1Tpye1ABFF = A BF = A + BFABVDDHigh: 1, Low: 0 High: 0, Low: 1 Switching Algebra Duality Tpye2ABFElectrical FunctionTable (电气功能表电气功能表)A B FL L LL H HH L HH H HPositive-LogicConventionA B F0 0 00 1 11 0 11 1 1Neg

25、ative-LogicConventionA B F1 1 11 0 00 1 00 0 0L: Low LevelH: High LevelF = A BF = A + BThe relationship of Positive-Logic Convention and Negative-Logic Convention are Duality. ( (正逻辑约定和负逻辑约定互为对偶关系正逻辑约定和负逻辑约定互为对偶关系) )ABFTpye2Tpye2ABFVDDABFHigh: 1, Low: 0 High: 0, Low: 1 Switching Algebra Duality F =

26、(A+B) (C+D)CDABFNegative-LogicTpye1Tpye2Tpye1Tpye1Tpye1F = (AB) + (CD)CDABFPositive-LogicTpye2This is just DeMorgans theorems (T14) ! VDDVDDOutTpye1Tpye2In1VDDTpye1In2In3In4Define Logic Variables:A, B, C, D, FSwitching Algebra Duality F(X1, X2 , , Xn )F = FD(X1, X2 , , Xn)F FPositive-LogicNegative-L

27、ogicSwitching Algebra Duality ExerciseWrite the Duality and Complement function for each of the following logic functions. (分别写出下面函数的对偶函数和反函数分别写出下面函数的对偶函数和反函数) F = A(B+C) + CD F =? FD =? G = (A+B)C(C+D) G =? GD =? Switching Algebra Standard Representations of Logic FunctionsLogic Function: F = A(B+C

28、)ABFC&1ABCF0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 A B CFTruth table 00000111Logic Circuits:举重裁判电路举重裁判电路A为主裁判，为主裁判，B、C为为副裁判，副裁判，F亮表示成功。亮表示成功。1为闭合，为闭合，0为断开为断开Switching Algebra Standard Representations of Logic Functions举重裁判电路举重裁判电路将输入和输出信号变化的时间关系用波形的形式描述，就得到了波形图。将输入和输出信号变化的时间关系用波形的形式描述，就得

29、到了波形图。 00000010010001101000101111011111ABCFSwitching Algebra Standard Representations of Logic Functionstruth table 真值表真值表product term 乘积项乘积项 sum term 求和项求和项 sum-of-products expression “积之和积之和”表达式表达式product-of-sums expression “和之积和之积”表达式表达式normal terms 标准项标准项n-variable minterm n变量最小项变量最小项n-variable

30、maxterm n变量最大项变量最大项Some DefinitionsSwitching Algebra Standard Representations of Logic Functions What is the Output for the given Inputs If you are a boss,? what you need to think is Functional RequirementXYZTruth table 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 X Y ZF0/10/10/10/10/10/10/10/1Sw

31、itching Algebra Standard Representations of Logic Functions Try to get the Logic Expression first If you are an engineer,F you need to design the Logic CircuitXYZ?Truth table 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 X Y ZF0/10/10/10/10/10/10/10/1Switching Algebra Standard Representations of L

32、ogic Functions Use Minterms or Maxterms How to get a Logic Expression from the True Table ?XYZ?FTruth table 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 X Y ZF0/10/10/10/10/10/10/10/1Switching Algebra Standard Representations of Logic FunctionsXYZFLogicCircuitsHow to define the Minterms (最小项最小项)?

33、A Minterm can be defined as a product term that is 1 in exactly one row. Why?Easy to get the sum-of-products There are 2n such product terms ( n变量函数具有变量函数具有2n个最小项个最小项 ) The product of any two different minterms is 0 ( 任意两个不同最小项的乘积为任意两个不同最小项的乘积为0 ) Sum of all minterms is 1 ( 全体最小项之和为全体最小项之和为1 )How to

34、 prove?0 反变量反变量 1 原变量原变量F is either 0 or 1Switching Algebra Standard Representations of Logic FunctionsA Maxterm can be defined as a sum term that is 0 in exactly one row. Why?Easy to get the product-of-sums There are 2n such sum terms ( n变量函数具有变量函数具有2n个最大项个最大项 ) The sum of any two different maxterm

35、s is 1 ( 任意两个不同最大项的和为任意两个不同最大项的和为1 ) Product of all maxterms is 0 ( 全体最大项之积为全体最大项之积为0 )How to define the Maxterms (最大项最大项)?How to prove?0 原变量原变量 1 反变量反变量XYZFLogicCircuitsF is either 0 or 1Switching Algebra Standard Representations of Logic FunctionsHow to obtian the logic expression from True Table?

36、True Table F= XYZ+ XYZ+ XYZ+ XYZ+ XYZ = X,Y,Z (0, 3, 4, 6, 7) Canonical Sum (标准和标准和) :A sum of the minterms corresponding totruth-table rows (input combinations) for which the function produces a 1 output.It is also known as the on-set (开集开集)XYZFLogicCircuitsSwitching Algebra Standard Representation

37、s of Logic FunctionsXYZFLogicCircuitsHow to obtian the logic expression from True Table?True Table F= X,Y,Z (1, 2, 5) = (X+Y+Z) (X+Y+Z) (X+Y+Z)Canonical Product (标准积标准积) :A product of the maxterms corresponding to truth-table rows (input combinations) for which the function produces a 0 output.It is

38、 also known as the off-set (闭集闭集)Switching Algebra Standard Representations of Logic FunctionsRelationship of Minterm and Maxtermmi = Mim: mintermM: maxterm(mi )D = Mjj = (2n -1) - ij = iOnesWhy?= A,B,C (0,3,5,6,7)FD = (m3+m5+m6)D= m3D m5D m6D= M4 M2 M1= A,B,C (1, 2, 4)Switching Algebra Standard Rep

39、resentations of Logic FunctionsRelationship of Minterm and Maxterm(ABC) = A+B+C(ABC) = A+B+C(ABC) = A+B+C11101001F0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0A B CF01234567RowF= A,B,C (3, 5, 6) F = A,B,C (3, 5, 6)F = A,B,C (0, 1, 2, 4, 7)标号一致标号一致 标号互缺标号互缺 标号互反标号互反 Switching Algebra Stand

40、ard Representations of Logic FunctionsRelationship of Minterm and Maxterm Mi = mi ； mi = Mi ；一个一个 n 变量函数，既可用最小项之和表示，也可用最变量函数，既可用最小项之和表示，也可用最大项之积表示，两者标号互缺。大项之积表示，两者标号互缺。 某逻辑函数某逻辑函数 F，若用，若用 m 个最小项之和表示，则其反函个最小项之和表示，则其反函数数 F 可用可用 m 个最大项之积表示，两者标号完全一致。个最大项之积表示，两者标号完全一致。一个一个 n 变量函数的最小项变量函数的最小项 mi , 其对偶其对偶

41、(Duality) 为：为：( mi )D = M (2n-1) - i 两者标号互反。两者标号互反。Switching Algebra Standard Representations of Logic FunctionsFive representations for the combinational logic function1. True Table2. Canonical Sum F= X,Y,Z (0, 3, 4, 6, 7)3. Minterm ListF= XYZ+ XYZ+ XYZ+ XYZ+ XYZ4. Canonical Product F= X,Y,Z (1, 2,

42、 5)F= (X+Y+Z) (X+Y+Z) (X+Y+Z)5. Maxterm ListSwitching Algebra Standard Representations of Logic FunctionsExercise1. F = (A,B,C) (1, 5, 7)FD = (A,B,C) (?) F = (A,B,C) (?) 2. Write the Canonical Sum of the following function: F(A,B,C) = AB +AC (Use T5, T8)3. Write the Canonical Product of the following function: G(A,B,C) = (A+B) (A+C) (