Microsoft PowerPoint - Appendix_SNU_Combinational Digital Logic Circuits.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - Appendix_SNU_Combinational Digital Logic Circuits.ppt"

수인 장
5 years ago
Views:

1 CHAPTER 2 COMBINATIONAL LOGIC CIRCUITS What to study? - Binary Logic (Boolean Algebra) : 논리회로의기본수학 -Gates: 디지털시스템의기본구성소자 - How to design cost-effective circuits? Logic Circuits: - Combinational Logic Circuits ( 組合論理回路 ) - Sequential Logic Circuits ( 順次論理回路 ) 2- Binary Logic and Gates 2-6 NAND and NOR Gates 2-2 Boolean Algebra 2-7 Exclusive-OR Gates 2-3 Standard Forms 2-8 Integrated Circuits 2-4 Map Simplification 2-9 Chapter Summary 2-5 Map Manipulation

2 2- BINARY LOGIC & GATES. Binary Logic (2 進論理 ) - Binary Logic Boolean Algebra Switching algebra, Two-valued Boolean Algebra 2 値부울代數 { 참, 거짓 } n { 참, 거짓 } {HIGH, LOW} n 2진디지털시스템 {HIGH, LOW} {ON, OFF} n {ON, OFF} 논리학 : 접속사 and, or, not Switch 회로 : 직렬연결, 병렬연결, NC/NO switch {??,??} n 수학적모델 {??,??}????,????

3 2- BINARY LOGIC & GATES 2. Three Basic Logical Operations 2 진디지털시스템기술에필요, 충분한연산 ( 동작 ) 의수와종류는? 2진논리 2진시스템 -bit 2진수연산 (Binary Logic) (Binary Digital System) (-bit Binary Arithmetic), 0 and 거짓참 거짓거짓거짓 참거짓참 0,+ 0 or 거짓참 거짓거짓참 0 0 참참참 0 X X not 0 거짓 참 0 참 거짓

4 2- BINARY LOGIC & GATES 3. (Basic) Logic Gates = 2 진논리를수행하는단위전자회로 X Y Z X Y Z L L L L H L 0 0 H L L 0 0 H H H X Y Z X Y Z L L L L H H 0 H L H 0 H H H X Z X Z L H 0 H L 0

5 2- BINARY LOGIC & GATES 4. Timing Diagram ( 타이밍도 ) 회로의논리동작을표현하는또다른방법주로순차논리회로의동작을규정하거나해석하는데사용

6 2- BINARY LOGIC & GATES 5. 多入力 (Multiple-Input) Gate 시스템구성의편이를위하여 2입력 AND, 2입력 OR, NOT 이외에도다양한 gate를제공함. (more at 2-6, 2-7) AND, OR gate의입력확장은and, OR 연산의결합법칙에의해정의됨. F = A B C = ((A B) C) F = A+B+C+D+E+F = (((((A+B)+C)+D)+E)+F)

7 논리소자 : IC 패키지의종류 Dual-in-line package (DIP) Small-outline IC (SOIC) SOIC with "gull-wing" leads PLCC with J-type leads LCCC with no leads Flat package with straight leads

8 논리소자 : IC Marking Manufacturer, Logic Family, Function, Package

9 논리소자 : Pin Numbering & Diagram

10 Logic Families ( 논리군 ) 용이한상호연결을위해비슷한전기적성질을갖도록만들어진논리게이트집합. ( 같은회로구조, 소자치, 같은공정 ) 서로다른논리군의 IC의연결은주의를요함.

11 CHAPTER 2 COMBINATIONAL LOGIC CIRCUITS What to study? - Binary Logic (Boolean Algebra) : 논리회로의기본수학 -Gates: 디지탈시스템의기본구성소자 - How to design cost-effective circuits? Logic Circuits: - Combinational Logic Circuits ( 組合論理回路 ) - Sequential Logic Circuits ( 順次論理回路 ) 2- Binary Logic and Gates 2-6 NAND and NOR Gates 2-2 Boolean Algebra 2-7 Exclusive-OR Gates 2-3 Standard Forms 2-8 Integrated Circuits 2-4 Map Simplification 2-9 Chapter Summary 2-5 Map Manipulation

12 2-2 BOOLEAN ALGEBRA ( 부울代數 ) Key Points:. Boolean Function X Y Z F F(X,Y,Z) = Boolean Expression = X + Y Z * 眞理表 (Truth Table) 0 0 * 論理圖, 論理回路圖 (Logic Diagram) 0 0 (Figure 2-3) 0 0 * algebraic expression logic diagram * 좋은표현식 좋은회로도 * 하나의함수에대해진리표표현은하나, 대수표현 ( 회로도 ) 는여럿. * 설계의일반적과정 Informal Spec. Formal Spec. 대수표현식 논리회로도

13 2-2 BOOLEAN ALGEBRA ( 부울代數 ) 부울代數의公理적定義 (Axiomatic Definition of Boolean Algebra) 代數體系 (algebraic system) 의정의 V: 값들의集合 (a set of elements or values) O: 演算의種類 (a set of operations) A: 값또는演算들에대한公理또는假說 (axioms or postulates) 유한집합 S의멱집합 ( Power Set, 즉 S의모든부분집합을원소로갖는집합 ) P에대하여 < V = P, O = {, }> 는부울대수임을 증명하라.

14 2-2 BOOLEAN ALGEBRA ( 부울代數 ) Huntington의부울代數의假說 : < V={ }, O={+,.} >. (a) V is closed with respect to the operation p. (b) V is closed with respect to the operation p2. 2. (a) V has an identity element w.r.t the operation p. (b) V has an identity element w.r.t the operation p2. 3. (a) V is commutative w.r.t the operation p. (b) V is commutative w.r.t the operation p2. 4. (a) p is distributive over p2. (b) p2 is distributive over p. 5. For each x in V, there exists an element y in V such that (a) x + y = (b) x. y = 0 6. V 2

15 2-2 BOOLEAN ALGEBRA ( 부울代數 ) 2. Basic Identities of Boolean Algebra ) X + 0 = X 2) X = X 恒等元 (identity) ( 公理 ) 3) X + = 4) X 0 = 0 Identity Theorem 恒等元定理 5) X + X = X 6) X X = X Idempotence Th. 冪等의定理 7) X + X = 8) X X = 0 補元 (Complement ) 9) (X ) = X Involution Th. 累乘定理 0) X + Y = Y + X ) X Y = Y X Commutative Law 2) X+(Y+Z) = (X+Y)+Z 3) X (Y Z) = (X Y) Z Associative Law 4) X (Y + Z) = X Y+ X Z 5) X + Y Z = (X+Y) (X+Z) Distributive Law 6) (X + Y) = X Y 7) (X Y) = X + Y De Morgan s Th. * 일반대수와의차이? 역원 (inverse)? * 雙對性原理 (Principles of Duality): AND OR, 0

16 2-2 BOOLEAN ALGEBRA ( 부울代數 ) 3. Algebraic Manipulation ( 代數的操作, 代數式操作 ) - 표현식의간소화 디지털회로의간소화 F = X YZ + X YZ + XZ = X Y(Z+Z ) + XZ = X Y + XZ

17 2-2 BOOLEAN ALGEBRA ( 부울代數 ) 4. Other Useful Identities () 흡수정리 (Absorption Theorem) X + X Y = X + X Y = X ( + Y) = X X (X + Y) = (X + 0) (X + Y) = X + 0 Y = X (2) X Y + X Y = X (Y + Y ) = X = X (X + Y) (X + Y ) = X + Y Y = X + 0 = X (3) 간소화정리 (Simplification Theorem) X + X Y = (X + X ) (X + Y) = (X + Y) = X + Y X (X + Y) = X X + X Y = 0 + X Y = X Y (4) 合意의정리 (Consensus Theorem) X Y + X Z + Y Z = X Y + X Z (X + Y) (X + Z) (Y + Z) = (X + Y) (X + Z) * 정리의증명방법 : 진리표, 대수식조작

18 2-2 BOOLEAN ALGEBRA ( 부울代數 ) 5. Complement of a Function ( 補函數 ) () 보함수의정의 (2) How to get the expression? - DeMorgan s Theorem F = X YZ + X Y Z F = X(Y Z + YZ) F = (X YZ + X Y Z) F = {X(Y Z + YZ)} = (X+Y +Z)(X+Y+Z ) = X + (Y+Z)(Y +Z ) - Using dual expression (i) take the dual expression (ii) complement each literal F = X YZ + X Y Z F = X(Y Z + YZ) F D = (X +Y+Z )(X +Y +Z) F D = X + (Y +Z )(Y+Z) F = (X+Y +Z)(X+Y+Z ) F = X + (Y+Z)(Y +Z )

19 CHAPTER 2 COMBINATIONAL LOGIC CIRCUITS What to study? - Binary Logic (Boolean Algebra) : 논리회로의기본수학 -Gates: 디지탈시스템의기본구성소자 - How to design cost-effective circuits? Logic Circuits: - Combinational Logic Circuits ( 組合論理回路 ) - Sequential Logic Circuits ( 順次論理回路 ) 2- Binary Logic and Gates 2-6 NAND and NOR Gates 2-2 Boolean Algebra 2-7 Exclusive-OR Gates 2-3 Standard Forms 2-8 Integrated Circuits 2-4 Map Simplification 2-9 Chapter Summary 2-5 Map Manipulation

20 2-3 STANDARD FORM ( 標準型 ) Key Points: 부울표현식의형태분류, 관련용어, 형태사이의변환. 부울표현식의형태 - 標準型 (Standard Form): 곱의합형 (Sum-of-Products, SOP, or Disjunctive Form) F(X,Y,Z) = XY + X Z + YZ 합의곱형 (Product-of-Sums, POS, or Conjunctive Form) F(X,Y,Z) = (X + Y)(X + Z)(Y + Z) - 非標準型 (Non-standard, Factored, or Parenthesized Form) F(X,Y,Z) = X + (Y + Z)(Y + Z ) - 正型 (Canonical Form): 표준형의특별한경우곱의합정형 (Canonical SOP, or Canonical Disjunctive Form) F(X,Y,Z) = XYZ + XYZ + X YZ [sum-of-minterms form] 합의곱정형 (Canonical POS, or Canonical Conjunctive Form) F(X,Y,Z) = (X+Y+Z)(X+Y+Z ) [product-of-maxterms form] * 한함수에대한정형표현식은唯一함.

21 2-3 STANDARD FORM ( 標準型 ) * 곱항 (product term) = ANDing of literals * 합항 (sum term) = ORing of literals * 표준형 = 2 段階표현식 (Two-Level Form) * 비표준형 = 多段階표현식 (Multi-Level Form) 2. Minterms and Maxterms -minterm( 最小項, 最小積項, 標準積 standard product) = a product term in which all the variables appear exactly once, either complemented or uncomplemented. -maxterm( 最大項, 最大合項, 標準合 standard sum) = a sum term in which all the variables appear exactly once, either complemented or uncomplemented. * The order of the variables should be assumed for the symbolic representation of minterms/maxterms.

22 2-3 STANDARD FORM ( 標準型 ) Table 2-6 Minterms for Three Variables X Y Z product terms symbol m 0 m m 2 m 3 m 4 m 5 m 6 m X Y Z m X Y Z m X YZ m X YZ m XY Z m XY Z m XYZ m XYZ m

23 X Y Z 2-3 STANDARD FORM ( 標準型 ) Table 2-7 Maxterms for Three Variables sum terms symbol M 0 M M 2 M 3 M 4 M 5 M 6 M X+Y+Z M X+Y+Z M X+Y +Z M X+Y +Z M X +Y+Z M X +Y+Z M X +Y +Z M 6 0 X +Y +Z M 7 0

24 2-3 STANDARD FORM ( 標準型 ) 3. Canonical Expressions - sum-of-minterms of F and F F(X,Y,Z) = [ ] + [ ] + [ ] + = X Y Z + X YZ + XY Z + XYZ = m 0 + m 2 + m 5 + m 7 = Σ m (0, 2, 5, 7), or Σ(0, 2, 5, 7) F (X,Y,Z) = [ ] + [ ] + [ ] + = X Y Z + X YZ + XY Z + XYZ X Y Z F F = m + m 3 + m 4 + m 6 = Σ m (, 3, 4, 6), or Σ(, 3, 4, 6)

25 2-3 STANDARD FORM ( 標準型 ) - product-of-maxterms of F and F F(X,Y,Z) = ( ) ( ) ( ) = (X+Y+Z )(X+Y +Z )(X +Y+Z)(X +Y +Z) = M M 3 M 4 M 6 = Π M (, 3, 4, 6), or Π(, 3, 4, 6) Similarly, F (X,Y,Z) = M 0 M 2 M 5 M 7 = Π(0, 2, 5, 7) Another method: F (X,Y,Z) = [F(X,Y,Z)] = (m 0 + m 2 + m 5 + m 7 ) = (m 0 ) (m 2 ) (m 5 ) (m 7 ) = M 0 M 2 M 5 M 7 = Π(0, 2, 5, 7) X Y Z F F F( ) = Σ(0, 2, 5, 7) = Π(, 3, 4, 6) F ( ) = Σ(, 3, 4, 6) = Π(0, 2, 5, 7)

26 2-3 STANDARD FORM ( 標準型 ) 4. Non-Canonical to Canonical E = Y + X Z = (X+X )Y (Z+Z ) + X (Y+Y )Z = (XY +X Y )(Z+Z ) + X YZ + X Y Z = XY Z + XY Z + X Y Z + X Y Z + X YZ + X Y Z = X Y Z + X Y Z + X YZ + XY Z + XY Z = Σ(0,, 2, 4, 5) E = Y + X Z = (Y + X )(Y + Z ) = (X X+Y +Z )(X +Y +Z Z) = (X+Y +Z )(X +Y +Z )(X +Y +Z)(X +Y +Z ) = Π(3, 6, 7) X Y Z E

27 2-3 STANDARD FORM ( 標準型 ) 5. Sum of Products - sum-of-minterms. obtained directly from a truth table. the most complex sum-of-products form. but, a starting point to a simplified s-o-p form - logic diagram of a s-o-p form?. two-level, AND-OR, implementation. (complements of input variables are assumed to be available) - Non-standard form to SOP form?. by means of the distributive law - SOP to simplified SOP?. many ways. Simplification Th., Consensus Th., Identity Th.,. - Figure 2-5, Figure 2-6

28 2-3 STANDARD FORM ( 標準型 ) - 다단계회로와 2 단계회로 (Figure 2-6) 6. Product of Sums - Two-level, OR-AND Implementation - Figure 2-7

29 CHAPTER 2 COMBINATIONAL LOGIC CIRCUITS What to study? - Binary Logic (Boolean Algebra) : 논리회로의기본수학 -Gates: 디지탈시스템의기본구성소자 - How to design cost-effective circuits? Logic Circuits: - Combinational Logic Circuits ( 組合論理回路 ) - Sequential Logic Circuits ( 順次論理回路 ) 2- Binary Logic and Gates 2-6 NAND and NOR Gates 2-2 Boolean Algebra 2-7 Exclusive-OR Gates 2-3 Standard Forms 2-8 Integrated Circuits 2-4 Map Simplification 2-9 Chapter Summary 2-5 Map Manipulation

30 2-4 MAP SIMPLIFICATION What to Study: Map method for logic simplification 맵방법에의한논리 ( 표현식 ) 최소화 / 간소화. Simplification Criterion: 최소화 / 간소화된곱의합표현이란? F = ( ) + ( ) + ( ) + + ( ) (i) with a minimum number of terms (ii) with the fewest possible number of literals * There may be many, equally good expressions! 2. 대수적간소화 (Algebraic Simplification) 과정의예 f(a, b, c) = a b c + a b c + a bc + a bc + abc = a b + a b + abc = a + abc = a + bc

31 2-4 MAP SIMPLIFICATION f(a, b, c) = a b c + a b c + a bc + a bc + abc = a b + a bc + bc = a (b + bc ) + bc = a (b + c ) + bc = a b + a c + bc = a (bc) + bc = a + bc f(a, b, c) = a b c + a b c + a bc + a bc + abc = a b c + a b c + a bc + a bc + a bc + abc = a b + a b + bc = a + bc =??? * With proper duplication of product terms, only the distributive law would do the job.

32 2-4 MAP SIMPLIFICATION 3. Algebraic Simplification: Use any boolean axioms and theorems, or () two adjacent product terms into one bigger product term (2) a term may be used more than once during combination (3) a term may be partitioned into smaller ones But, still we have some difficulties: () no specific rules to predict each succeeding step (2) difficult to determine whether the simplest expression has been achieved - Simplify the following expression: f(a,b,c,d) = A BC D + A BCD + ABC + ABCD + A BCD = A BD + ABC + ABCD + A BCD =?????? = ABC + A BC + BD

33 2-4 MAP SIMPLIFICATION 4. Karnaugh Map, (K-map, Veitch Diagram) () 진리표의 2차원적그림표현 ( 인접관계를시각적으로판단가능 ) (2) 인접한최소항또는곱항끼리물리적으로도가까이있도록배치 (3) 수작업에의한간소화에사용 (not for computer-aided design) (4) 곱의합또는합의곱형태간소화에사용 (not apply directly to simplification in non-standard forms) (5) up to 4 variables? ==> depends on YOU! Glue logic * possible to find two or more simplified expressions.

34 2-4 MAP SIMPLIFICATION 5. 2-, 3-, 4-Variable K-Maps * Gray Code Y X Y Z Y X Y X Y X XY XY 0 0 X Y 0 X X m 0 m 2 3 m m 3 Y 0 X Y Z X Y Note the adjacency of minterms Z = X Y+ X Y+ X Y = X + Y

35 2-4 MAP SIMPLIFICATION Y Y Y X 0 00 XYZ XYZ 0 XYZ XYZ 0 XYZ XYZ XYZ XYZ X m 0 m m 4 m 2 m 5 m 3 m 7 m 6 X Z [EXAMPLE 2-3] F(X,Y,Z) = Σ(2,3,4,5) * rectangles of, 2, 4, 8, cells or squares Y X Z Z Z

36 2-4 MAP SIMPLIFICATION [Examples] F(X,Y,Z) = Σ(0,2,4,6) F(X,Y,Z) = Σ(0,,2,3,6,7) Y Y X X Z Z [EXAMPLE 2-4] F(X,Y,Z) = Σ(3,4,6,7) F(X,Y,Z) = Σ(0,2,4,5,6) Y Y X X Z Z

37 2-4 MAP SIMPLIFICATION [Example] F(X,Y,Z) = Σ(,3,4,5,6) Y X Z [Example] F(X,Y,Z) = X Z+ XY + XYZ+ YZ => Z+ XY Y X Z

38 2-4 MAP SIMPLIFICATION W [EXAMPLE 2-5] Four-Variable Map F(W,X,Y,Z) = Σ(0,,2,4,5,6,8,9,2,3,4) Y Y X X W 0 Z Z

39 2-4 MAP SIMPLIFICATION [EXAMPLE 2-6] F = ABC+ BCD + ABC+ ABCD C 0 A 0 0 B D

40 CHAPTER 2 COMBINATIONAL LOGIC CIRCUITS What to study? - Binary Logic (Boolean Algebra) : 논리회로의기본수학 -Gates: 디지탈시스템의기본구성소자 - How to design cost-effective circuits? Logic Circuits: - Combinational Logic Circuits ( 組合論理回路 ) - Sequential Logic Circuits ( 順次論理回路 ) 2- Binary Logic and Gates 2-6 NAND and NOR Gates 2-2 Boolean Algebra 2-7 Exclusive-OR Gates 2-3 Standard Forms 2-8 Integrated Circuits 2-4 Map Simplification 2-9 Chapter Summary 2-5 Map Manipulation

41 2-4 MAP SIMPLIFICATION What to Study: Map method for logic simplification 맵방법에의한논리 ( 표현식 ) 최소화 / 간소화. Simplification Criterion: 최소화 / 간소화된곱의합표현이란? F = ( ) + ( ) + ( ) + + ( ) (i) with a minimum number of terms (ii) with the fewest possible number of literals * There may be many, equally good expressions! 2. 대수적간소화 (Algebraic Simplification) 과정의예 f(a, b, c) = a b c + a b c + a bc + a bc + abc = a b + a b + abc = a + abc = a + bc

42 2-4 MAP SIMPLIFICATION f(a, b, c) = a b c + a b c + a bc + a bc + abc = a b + a bc + bc = a (b + bc ) + bc = a (b + c ) + bc = a b + a c + bc = a (bc) + bc = a + bc f(a, b, c) = a b c + a b c + a bc + a bc + abc = a b c + a b c + a bc + a bc + a bc + abc = a b + a b + bc = a + bc =??? * With proper duplication of product terms, only the distributive law would do the job.

43 2-4 MAP SIMPLIFICATION 3. Algebraic Simplification: Use any boolean axioms and theorems, or () two adjacent product terms into one bigger product term (2) a term may be used more than once during combination (3) a term may be partitioned into smaller ones But, still we have some difficulties: () no specific rules to predict each succeeding step (2) difficult to determine whether the simplest expression has been achieved - Simplify the following expression: f(a,b,c,d) = A BC D + A BCD + ABC + ABCD + A BCD = A BD + ABC + ABCD + A BCD =?????? = ABC + A BC + BD

44 2-4 MAP SIMPLIFICATION 4. Karnaugh Map, (K-map, Veitch Diagram) () 진리표의 2차원적그림표현 ( 인접관계를시각적으로판단가능 ) (2) 인접한최소항또는곱항끼리물리적으로도가까이있도록배치 (3) 수작업에의한간소화에사용 (not for computer-aided design) (4) 곱의합또는합의곱형태간소화에사용 (not apply directly to simplification in non-standard forms) (5) up to 4 variables? ==> depends on YOU! Glue logic * possible to find two or more simplified expressions.

45 2-4 MAP SIMPLIFICATION 5. 2-, 3-, 4-Variable K-Maps * Gray Code Y X Y Z Y X Y X Y X XY XY 0 0 X Y 0 X X m 0 m 2 3 m m 3 Y 0 X Y Z X Y Note the adjacency of minterms Z = X Y+ X Y+ X Y = X + Y

46 2-4 MAP SIMPLIFICATION Y Y Y X 0 00 XYZ XYZ 0 XYZ XYZ 0 XYZ XYZ XYZ XYZ X m 0 m m 4 m 2 m 5 m 3 m 7 m 6 X Z [EXAMPLE 2-3] F(X,Y,Z) = Σ(2,3,4,5) * rectangles of, 2, 4, 8, cells or squares Y X Z Z Z

47 2-4 MAP SIMPLIFICATION [Examples] F(X,Y,Z) = Σ(0,2,4,6) F(X,Y,Z) = Σ(0,,2,3,6,7) Y Y X X Z Z [EXAMPLE 2-4] F(X,Y,Z) = Σ(3,4,6,7) F(X,Y,Z) = Σ(0,2,4,5,6) Y Y X X Z Z

48 2-4 MAP SIMPLIFICATION [Example] F(X,Y,Z) = Σ(,3,4,5,6) Y X Z [Example] F(X,Y,Z) = X Z+ XY + XYZ+ YZ => Z+ XY Y X Z

49 2-4 MAP SIMPLIFICATION W [EXAMPLE 2-5] Four-Variable Map F(W,X,Y,Z) = Σ(0,,2,4,5,6,8,9,2,3,4) Y Y X X W 0 Z Z

50 2-4 MAP SIMPLIFICATION [EXAMPLE 2-6] F = ABC+ BCD + ABC+ ABCD C 0 A 0 0 B D

51 CHAPTER 2 COMBINATIONAL LOGIC CIRCUITS What to study? - Binary Logic (Boolean Algebra) : 논리회로의기본수학 -Gates: 디지탈시스템의기본구성소자 - How to design cost-effective circuits? Logic Circuits: - Combinational Logic Circuits ( 組合論理回路 ) - Sequential Logic Circuits ( 順次論理回路 ) 2- Binary Logic and Gates 2-6 NAND and NOR Gates 2-2 Boolean Algebra 2-7 Exclusive-OR Gates 2-3 Standard Forms 2-8 Integrated Circuits 2-4 Map Simplification 2-9 Chapter Summary 2-5 Map Manipulation

52 2-5 MAP MANIPULATION What to Study: 맵방법에의한논리최소화 ( 체계적방법 ) 합의곱표현의최소화無關條件 (Don t-care Conditions) 이있는경우. Implicant, Prime Implecant, Essential Prime Implicant F = ( ) + ( ) + ( ) + ( ) - Implicant = a product term if the function has the value for all minterms of the product term, 즉, 주어진함수의곱의합표현에나타날수있는곱항. - Prime Implicant(PI) 主積項 = 문자를더이상줄일수없는implicant, 다른 implicant에포함되지않는 implicant. - Essential Prime Implicant (EPI) 必須主積項 = 어떤최소표현식에도항상포함되어야하는주적항.

53 2-5 MAP MANIPULATION 2. 곱의합표현식에서의곱항 F = ( ) + ( ) + + ( ) (i) 곱의합표현식에서의각곱항은그함수의 implicant 이어야함. (ii) 곱의합최소표현식에서의각곱항은그함수의 PI 이다. 3. K-map 에서의 Implicant, PI, EPI Implicant = -cell 만을포함하는묶음. PI 主積項 = 더이상크게할수없는묶음. EPI 必須主積項 = 곱의합최소표현식에꼭포함시켜야할묶음. 4. K-map에서의간소화과정오직 PI 묶음만을고려하여, 모든 -cell이어떤묶음에속할때까지, () EPI 묶음을모두선택한다. (2) 덜바람직한 PI 묶음을고려대상에서제외한다. (3) 이상태에서다시필수적인 PI 묶음 [Secondary EPI] 들을선택한후, (2) 로되돌아간다. (4) 선택할것도, 제외할것도없을때에는임의로 (?) 하나를선택한후, 위 (2) 와 (3) 을반복한다.

54 2-5 MAP MANIPULATION [Examples] C C C A 0 0 B A 0 0 B A 0 0 B D D D

55 2-5 MAP MANIPULATION 5. Product-of-Sums Simplification ( 합의곱형간소화 ) () F 의 s-o-p를구하여양변의 complement를취함. (2) F의 K-map에서 0-cell을 grouping함. [Grouping한조건들을합항으로표현할때, 문자의극성에주의 ] [Example 2-8] F(A, B, C, D) = Σ(0,, 2, 5, 8, 9, 0) C B A 0 0 D

56 2-5 MAP MANIPULATION 6. Don t-care Conditions ( 無關條件 ) = 함수의출력이정의되지않은입력조건들. (i) the input combinations never occur. (ex) BCD code (ii) the input combinations would occur, but we do not care about the outputs in response to these combinations. => We simply do not care what value is assumed by the function for the unspecified conditions. * imcompletely specified functions ( 불완전하게정의된함수 ) - What shall we do with DC conditions? DC 조건에대한함수의출력은설계자가임의로설정가능. But, somebody will get better designs!! How many complete specifications are possible for a 4-input -output function with 6 DC conditions? ==>

57 2-5 MAP MANIPULATION - 무관조건의표현진리표, K-map: -, x, X, d, D, D Equation : F = [ ] [ ] + dc([ ] [ ]) = [ ] [ ] + ([ ] [ ])dc = Σ(, 2, ) + Σdc(7, 8, ) = Π(0, 3, ) + Πdc(7, 8, ) - 무관조건이있는경우의표현식간소화유관조건을중심으로 grouping을하여나아가되, 무관조건을포함하는경우에 group의크기가커질수있으면그무관조건을 group 에포함시킴. (I) 유관조건 : grouping의개수와크기를결정. (ii) 무관조건 : grouping의크기에만영향을줌.

58 2-5 MAP MANIPULATION [Example] F(A,B,C,D) = Σ(, 3, 7,, 5) + Σdc(0, 2, 5) C x x 0 0 x 0 B A D

59 B MAP MANIPULATION 7. 5-변수 K-Map: two 4-variable K-maps into a -variable K-map A=0 A= [Example: f(a, B, C, D, E) = Σ( ) D D C B E E C A=0 A= D D 0 B C B 0 C E E

60 7. 6-변수 K-Map: C A=0 A= C 2-5 MAP MANIPULATION E F E F B=0 B= 00 0 D C 0 00 D 0 C 0 E F E F D D

61 CHAPTER 2 COMBINATIONAL LOGIC CIRCUITS What to study? - Binary Logic (Boolean Algebra) : 논리회로의기본수학 -Gates: 디지탈시스템의기본구성소자 - How to design cost-effective circuits? Logic Circuits: - Combinational Logic Circuits ( 組合論理回路 ) - Sequential Logic Circuits ( 順次論理回路 ) 2- Binary Logic and Gates 2-6 NAND and NOR Gates 2-2 Boolean Algebra 2-7 Exclusive-OR Gates 2-3 Standard Forms 2-8 Integrated Circuits 2-4 Map Simplification 2-9 Chapter Summary 2-5 Map Manipulation

62 2-6 NAND AND NOR GATES What to study: NAND 와 NOR gate 를이용한부울함수具現. AND, OR, NOT 이외에다른 type의 gate들이제공됨. Gate type을결정할때의고려사항 : - feasibility & economy of the gates in the implementation tech. - possibility of fan-in extension - ability to implement Boolean functions 2. Simple Gate Types in Bipolar and CMOS Technology: names( 이름 ), graphic symbols( 회로기호 ), functions( 기능 ) [Figure 2-26] in next slide * negation indicator, bubble

63 Digital Logic Gates

64 Digital Logic Gates

65 2-6 NAND AND NOR GATES 3. Functional(Logical) Completeness 函數的 ( 論理的 ) 完全性 A set of gates are functionally, or logically complete if any Boolean function can be implemented or expressed using only the gate types in the set: {AND, OR, NOT} is functionally complete. {NAND} and {NOR} are functionally complete. [PROVE? => Figure 2-27, Figure 2-33 below] *Universal Gates

66 2-6 NAND AND NOR GATES 4. How to implement a Boolean function with NAND gates? () Obtain the simplified expression and/or circuit in terms of AND, OR, and NOT. (2) Convert AND, OR, NOT gates to NAND gates. [bubble insertion] more on later slides Alternative NAND and NOT Symbols for Conversion [Fig. 2-28]

67 2-6 NAND AND NOR GATES 5. Two-Level NAND Circuits - NAND-NAND Two-Level Implementation - S-O-P expression can be realized by NAND-NAND circuits F = A B + C D = A B CD Figure 2-29 for the circuits and also for the conversion from AND-OR using bubble insetion. [Example 2-9 & Fig. 2-30] F(x, y, z) = Σ(, 2, 3, 4, 5, 7) 을 NAND gates로구현하라. () Simplify in sum-of-products form (2) Draw AND-OR network (Use buffer for terms with single literal) (3) Convert it into NAND-NAND network

68 2-6 NAND AND NOR GATES 6. Multilevel NAND Circuits [ 多段階 NAND 回路 ] Fig. 2-3, Fig. 2-32, Procedure at page 72.

69 2-6 NAND AND NOR GATES 7. NOR Circuits Can repeat the disscussion with NAND circuits. Alternative Symbols for NOR [Fig. 2-34] NOR-NOR form = P-O-S expression [Fig. 2-35] Converting AND/OR Circuits into NOR Circuits [Fig. 2-36]

70 Demonstration of Positive and Negative Logic

71 2-7 EXCLUSIVE-OR GATES. Exclusive-OR 함수 : XOR, EXOR, EOR -X Y = X Y + X Y [difference ftn.] 2. Exclusive-NOR 함수 : XNOR, EXNOR, ENOR - complement of exclusive-or -(X Y) = X Y + X Y [equivanlece ftn]

72 2-7 EXCLUSIVE-OR GATES 3. XOR와관련된항등식들 X 0 = X X = X X X = 0 X X = X Y = (X Y) X Y = (X Y) A B = B A (A B) C = A (B C) = A B C

73 2-7 EXCLUSIVE-OR GATES 4. XOR Gate 의 NAND 구현 : [Fig. 2-37] 5. 다변수 XOR -A B C =??? - Odd function ( 홀수함수 ) : F = when - K-map for XORs: check board : [Fig. 2-38] - Multiple-Input XOR with 2-Input XOR: [Fig. 2-39] - 응용예 : Parity 생성과검출

74 CHAPTER 2 COMBINATIONAL LOGIC CIRCUITS What to study? - Binary Logic (Boolean Algebra) : 논리회로의기본수학 -Gates: 디지탈시스템의기본구성소자 - How to design cost-effective circuits? Logic Circuits: - Combinational Logic Circuits ( 組合論理回路 ) - Sequential Logic Circuits ( 順次論理回路 ) 2- Binary Logic and Gates 2-6 NAND and NOR Gates 2-2 Boolean Algebra 2-7 Exclusive-OR Gates 2-3 Standard Forms 2-8 Integrated Circuits 2-4 Map Simplification 2-9 Chapter Summary 2-5 Map Manipulation

75 2-8 INTEGRATED CIRCUITS Levels of Integration( 집적도 ): SSI, MSI, LSI, VLSI Digital Logic Families ( 論理群 ): 회로기술 ( 소자, 회로도 ), 전기적성질 전기적성질 : Logic Level( 전압, 전류 ), Fan-in, Fan-out, Noise Margin( 잡음여유 ), Power Dissipation( 소비전력 ), Propagation Delay( 전달지연시간 ) transport delay, inertial delay

76 Gates as Control Elements Gate as Operators Gate as Control Elements

77 Fully Complementary CMOS Gate Structure and Examples

78 Networks and Circuit for Example 2-0

79 Transmission Gate (TG)

80 Selector and Exclusive- OR Constructed with Transmission Gates

歯02-BooleanFunction.PDF

歯02-BooleanFunction.PDF 2Boolean Algebra and Logic Gates 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 IC Chapter 2 Boolean Algebra & Logic Gates 1 Boolean Algebra 1854 George Boole Chapter 2 Boolean Algebra & Logic Gates 2 Duality Principle