디 지 털 공 학디 지 털 공 학 한국폴리텍 V 대학

1 강의내용 및 구성  논리함수의 간략화 1) 논리게이트와 IC 2) map 에 의한 간소화 3) 다변수 입력함수의 간소화  Implicant, Prime implicant, Essential prime implicant  Quine-McClusky 방법에 의한 간소화

2 논리 게이트의 종류  TTL 1)Transistor-Transistor Logic 2) 바이폴라 (bipolar) transistor 에 기초한 논리 게이트 3) 전류 구동 능력 우수하나 CMOS 보다 전력소모가 많음 4)TTL subfamilies 예 ① 74LS : low-power Schottky TTL  CMOS 1)Complementary Metal-Oxide Semiconductor 2)MOSFET 에 기반한 논리 게이트 3) 매우 적은 전력소모 4) 사용할 수 있는 전압의 폭이 넓고 noise 에 강하다. 5)CMOS subfamilies 예 ① 74HC : high-speed CMOS 예 ) 74HC00 : 2-input NAND, 74HC20 : 4-input NAND

3 게이트의 입 출력 전압과 전류 제조회사에서 입 출력의 L 상태와 H 상태를 정해 놓음 Data Sheets 를 참고하여 논리회로 설계 시 유의사항 1)Max 값과 Min 값을 상황에 따라 고려하여 설계 2)Typical 값은 참고만 함  입출력 전압 1)V OL : 논리 LOW 일 때의 출력 전압 2)V OH : 논리 HIGH 일 때의 출력 전압 3)V IL : 논리 LOW 일 때의 입력 전압 4)V IH : 논리 HIIGH 일 때의 입력 전압

4 게이트의 입 출력 전압과 전류 ( 계속 )  입출력 전류 1)I OL : 논리 LOW 일 때의 출력 전류 2)I OH : 논리 HIGH 일 때의 출력 전류 3)I IL : 논리 LOW 일 때의 입력 전류 4)I IH : 논리 HIIGH 일 때의 입력 전류

5 전파 지연  전파지연 (Propagation delay, PD) 1) 입력의 변화와 이에 따른 출력의 변화가 일어날 때까지의 시간 2)tp HL : 출력이 High 에서 Low 로 바뀔 때의 전파지연 3)tp LH : 출력이 Low 에서 High 로 바뀔 때의 전파지연 t pHL t pLH a) NAND b) AND

6 전파 지연 ( 게속 )  전파지연에 영향을 주는 요소 1) 온도 2) 전원 전압 3) 부하, 특히 용량성 (capacitance) 부하  논리회로에서의 전파지연 1)input-to-output path 에서의 모든 delay 의 합 2) 출력에 영향을 주지 않는 delay 는 무시 다음의 논리회로에서 t p = ? tp HL1 tp HL2 tp LH 출력에 영향을 주지 않는다 tp HL1 + tp HL2

7 fan-in, fan-out  fanout 1) 논리 게이트의 출력이 에러없이 구동할 수 있는 게이트의 수 2) 필요로 하는 전류 (load gate) 와 공급할 수 있는 최대 전류 (driving gate) 에 의해서 결정됨 3)fan-out 을 초과하면 정상적인 동작을 하지 못하므로 설계 시 중요하게 고려되어야 한다  Driving gate ( 구동 게이트 ) 1) 다른 게이트의 입력에 전류를 공급하는 게이트  Load gate ( 부하 게이트 ) 1) 다른 게이트로 부터 전류를 공급 받는 게이트

8 디지털 IC 의 잡음대책 ( 교재 p.101) 전자기기 회로와 잡음은 불가분의 관계가 있으며, 시스템의 설계 시에는 중요시된다 1. 정전 유도에 의한 잡음의 방지대책 1) 배선의 선간 거리를 떼어 놓는다 2) 배선의 지름과 길이를 될 수 있는 한 작게한다 3) 배선간 상호 전위차를 작게한다 2. 전자 유도에 의한 잡음의 방지 대책 1) 교류 회로가 흐르는 두 가닥의 선은 왕로 ( 往路 ) 와 복로 ( 復路 ) 의 선을 서로 모아서 상호 방향이 다른 자력선 끼리를 상쇄시킨다 2) 잡음 발생 회로와 신호 회로는 될 수 있는 한 거리를 뗀다 3) 잡음 발생원의 리드선 및 간섭을 받기 쉬운 선은 되도록 짧게한다 4) 잡음을 포함한 선과 갑섭을 받기 쉬운 선은 될 수 있는 한 교차시켜서 평행으로 배선하지 말아야한다  라인의 공통 임피던스에 의한 잡음의 대책  신호와 혼입해 있는 외부 잡음의 제거 대책

9 IC( 집적회로 ) 디지털 논리회로 소자는 보통 집적 회로화 (IC, Integrated Circuit) 하여 사용한다  IC 1) 디지털 게이트를 이루는 전자소자를 모아 실리콘 반도체 위에 만들어 놓은 것 2) 세라믹이나 플라스틱 패키지 3) IC 핀을 통해 외부와 연결 2. 집적의 규모 1)SSI : 20 개 정도의 논리 게이트로서 NAND, OR, 플립플롭 등 2)MSI : 10~1,000 gates 로서 ALU, 시프트 레지스터, 멀티플렉서 등 3)LSI : 수천 gates 로서 ROM, RAM, 시계, 계산기의 칩 4)VLSI : 수십만 gates 이상

10 논리함수의 표준형 전개 ( 교재 p.136) 1. 최소항과 최대항 1) 일반적으로 논리함수는 그 속에 포함되어 있는 모든 변수의 다항식으로 표시 최소항 (minterm) 2) 그 변수와 변수의 부정 (complement) 을 포함하여 논리곱 (AND) 으로 표시되는 모든 항을 최소항 (minterm) 최대항 (maxterm) 3) 그 변수와 변수의 부정 (complement) 을 포함하여 논리합 (OR) 으로 표시되는 모든 항을 최대항 (maxterm)  최소항 또는 최대항은 2 n 개 나타난다 (n 은 변수의 수 ) 예 ) 2 개의 변수를 a, b 라 할 때 최소항은 ab, a’b, ab’, a’b’  최대항의 부정은 최소항, 최소항의 부정은 최대항이다 - 드모르간의 법칙  모든 최소항 또는 최대항의 논리합은 1 이다  이웃 최소항을 서로 논리곱하면 0 이되고, 최대항을 서로 논리합하면 1 이된다

11 논리함수의 표준형 전개 ( 계속 ) 4) 3 개의 2 진 변수에 대한 최소항과 최대항의 예 최 소 항최 소 항최 대 항최 대 항 a b c 항명칭항 000a’b’c’m0m0 a+b+cM0M0 001a’b’cm1m1 a+b+c’M1M1 010a’bc’m2m2 a+b’+cM2M2 011a’bcm3m3 a+b’+c’M3M3 100ab’c’m4m4 a’+b+cM4M4 101ab’cm5m5 a’+b+c’M5M5 110abc’m6m6 a’+b’+cM6M6 111abcm7m7 a’+b’+c’M7M7

12 논리함수의 표준형 전개 ( 계속 ) 2. 논리함수의 표준형 전개 1) 논리함수를 간략화할 때는 우선 진리표로 부터 최소항과 최대항을 결정한 후 2) 논리함수의 표준형 (canonical form) 으로 표시  SOP(Sum of Product) a. 출력 변수가 “1” 인 때는 최소항의 논리합으로 표시  POS(Product of Sum) a. 출력변수가 “0” 일 때는 최대항의 논리곱으로 표시 3) n 개의 변수로 이루어진 어떤 논리함수이건 OR, AND 및 NOT 의 기본 논리동작 외 및 몇 항으로 표현될 수 있으므로 굳이 특수한 다른 논리동작을 이용하여 표현할 필요는 없다 표준형으로 전개된 표준식 예 SOP : F = m 0 + m 3 + m 4 + m 5 = ∑(0,3,4,5) POS : F = M 1 M 2 M 6 M 7 = ∏(1,2,6,7)

13 논리함수의 표준형 전개 ( 계속 ) 예 제 ) Boole 함수 F=A+B'C 를 최소항의 합으로 나타내어라. 4 개의 최소항의 합으로 표현 2 개의 최소항의 합으로 표현 중복된 항은 한 번만 표현 함수의 진리표를 얻고, 거기에서 최소항들을 구하여도 됨

14 논리함수의 표준형 전개 ( 계속 ) 예 제 ) Boole 함수 F = xy + x'z 를 최대항의 곱 형태로 나타내라

15 논리함수의 표준형 전개 ( 계속 ) 예 제 ) F = ABC + DE 의 불 함수를 NAND 게이트만으로 구성하라 F = ABC + DE = [(ABC)’ (DE)’]’ SOP 는 NAND 게이트로, POS 는 NOR 게이트로 변환이 용이하다

16 MAP 에 의한 간소화  함수의 간략화 1) 대수적 방법  규칙성 없음 2) Karnaugh Map(K-MAP)  간단하고 직접적인 간략화 방법  SOP, POS 의 표준 형태로 만들어 줌  각 입력 상태의 조합을 K-MAP 에 표시함에 있어서 인접한 항과의 관계가 1 비트의 변수만 변화하도록 구성

17 MAP 에 의한 간소화 ( 계속 )  2 변수 맵 2 변수 맵에서의 a) minterm 항과 b) 불 함수 m1+m2+m3 를 불 함수로 표현하면 ?

18 MAP 에 의한 간소화 ( 계속 )  3 변수 맵 1) 3 변수의 논리함수에서는 입력 조합이 8 가지이므로 8 개의 인접항이 존재한다 2) 8 개의 각 항에 0 과 1 의 조합을 할당하는데 각 항 사이에는 1 비트만 변화해야 하므로 배열 순서에 주의해야 한다  불 대수식을 K-MAP 으로 간소화 하는 순서  표준 SOP 형식으로 나타낸 후 K-MAP 의 해당 칸에 1 을 기입  인접한 1 의 항을 루프 (loop) 로 둘러싼다. 이때 항의 수는 짝수이어야 하며, 묶음은 최대가 되도록 한다  항의 1 은 반복 사용가능하며, 반드시 한번은 사용해야 한다 배열 순서에 주의

19 MAP 에 의한 간소화 ( 계속 )  각각의 루프로부터 SOP 형식의 논리식을 구한다  항의 0 이 매우 적을 때는 POS 의 형식을 이용하면 더욱 간단해진다 예 제 ) Boole 함수 F(x, y, z) =Σ(2, 3, 4, 5) 를 간략화하라 x’y xy’ F = x’y + xy’

20 MAP 에 의한 간소화 ( 계속 ) 예 제 ) 에 대한 K-MAP 을 그리고 간략화 하라 F = yz + xz’ F = z’ + xy’

21 MAP 에 의한 간소화 ( 계속 ) 예 제 ) 다음 Boole 함수 F = A'C + A'B +AB‘C +BC 에 대하여 최소화된 SOP 와 POS 를 나타내라 minterm 의 합으로 표현 최소화된 SOP 는 F=C+A’B 주어진 함수를 maxterm 의 곱으로 표현하면 F(A,B,C) = ∏(0,4,6) ① K-MAP 의 해당하는 항에 0 을 기입 B+C ② 0 이 최대한 많이 포함 되도록 묶는다 A’+C 최소화된 POS 는 F=(A’+C)(B+C)

22 MAP 에 의한 간소화 ( 계속 )  4 변수 맵 ( 교재 p.143) 1) 변수의 논리함수 F(A,B,C,D) 인 경우는 2 4 =16 개의 항을 가진 K-MAP 이 필요하다  디지털 시스템에서는 4 비트 단위의 데이터를 취급하는 경우가 많으므로 입력 변수에 의한 논리식이 많이 사용된다 F(w,x,y,z) 에 대한 4 변수 맵에서의 최소항

23 MAP 에 의한 간소화 ( 계속 ) 예 제 ) 다음 Boole 함수를 간략화 하라. F(w, x, y, z) =Σ(0, 1, 2, 4, 5, 6, 8,9, 12, 13, 14) y′y′ xz′ w’z′ F = y′+ w’z’ + xz’

24 MAP 에 의한 간소화 ( 계속 )  5 변수 맵 ( 교재 p.144) 1) 5 변수의 경우는 32 개의 항을 가진 K-MAP 이 필요하다 2) F(A,B,C,D,E) 가 5 변수를 가질 경우는 2 개의 4 변수 맵으로 구성할 수 있다  A=0 인 경우의 16 개 셀 : 최소항 0~15 를 표현  A=1 인 경우의 16 개 셀 : 최소항 16~31 을 표현

25 MAP 에 의한 간소화 ( 계속 ) 예 제 ) 다음 Boole 함수를 간략화하라. F(A,B,C,D,E)=Σ(0,2,4,6,9,13,21,23,25,29,31) A’B’E’ ACE A’BD’E + ABD’E = BD’E(A+A’) = BD’E 서로 포개어지는 위치에 있는 두 셀은 인접항으로 간주가능 = A’B’E + BD’E + ACE

26 MAP 에 의한 간소화 ( 계속 )  무관조건 (don’t care condition) ( 교재 p.146) 1) 입력 변수들의 조합에 대해 함수 출력이 무엇이든 (1 이든 0 이든 ) 무관 2) 무관 조건을 1 이나 0 과 구별하기 위해서 x(don’t care) 기호사용 예 제 ) don`t care 조건 d(w,x,y,z) = Σ(0,2,5) 을 갖는 Boole 함수를 간략화 하라, F(w,x,y,z) = Σ(1,3,7,11,15) w’x’ yz F = w’x’ + yz w’z F = w’z + yz

27 Implicant, prime implicant, essential prime implicant Implicant 는 1 또는 x 만을 포함하는 그룹을 의미한다 Prime implicant 는 다른 implicant 에 포함되지 않는 implicant 를 의미 Essential prime implicant 는 다른 implicant 가 포함하지 않는 1 을 적어도 하나이상 갖고 있는 prime implicant 를 의미 예 제 ) F(A,B,C,D) =Σ(0,2,3,5,7,8,9,10,11,13,15) 에서 prime implicant, essential prime implicant 를 구하라. Implicant 이지만 prime implicant 는 될 수 없다 AB’ AD BD CD B’C B’D’ Prime implicants 다른 implicant 가 포함하지 않는 1 을 갖는 Prime implicant BD, B’D’ 를 Essential prime implicant 라 한다

Implicant, prime implicant, essential prime implicant PI(Prime Implicant) table 을 작성하면 EPI(Essential Prime Implicant) 와 PI 만으로 구성되는 최소화된 표현식을 쉽게 구할 수 있다 F(A,B,C,D) =Σ(0,2,3,5,7,8,9,10,11,13,15) 주어진 함수에 대한 K-MAP 으로 부터 작성된 PI table √ √ √ √√ √√√ √ √ √ √ √ √ √ √ √√√ √ √ √ √ √ M 0 와 m 5 를 포함하는 PI 가 EPI 가 되며, 최소화된 F 는 반드시 EPI 를 포함하고 있어야 한다 F = BD+B’D’+CD+AD = BD+B’D’+CD+AB’ = BD+B’D’+B’C+AD = BD+B’D’+B’C+AB’

29 Implicant, prime implicant, essential prime implicant 예 제 ) F(A,B,C,D) =Σ(2,3,5,7,10,11,13,14,15) 에서 PI, EPI 를 구하고 함수를 간소화하라 K-MAP PI table PI = BD, CD, AC, B’C EPI = BD, AC, B’C F = BD + AC + B’C √ √√√√ √√√ √√√√ √ √ √√

30 Quine-McClusky 방법 AB+AB’=A 다수의 입력변수를 갖는 불 함수를 간소화하는 방법으로서 AB+AB’=A 의 관계식에 기초를 둔다  최소화하려는 불 함수를 표준형 SOP 형식으로 표시한다 예 ) F(A,B,C,D) =Σ(m 0, m 1, …, m 15 )  표현된 불 함수의 진리표로부터 a. 첫째줄에는 1 이 전혀 포함되지 않는 항 b. 두 번째 줄에는 1 이 1 개 포함되어 있는 항 c. 세 번째 줄에는 1 이 2 개 포함되어 있는 항 d. 마지막에는 모든 변수가 1 인 항들로 나열된 표를 구한다  불 함수를 구성하는 모든 최소항에 대해서 인접 최소항 사이에 AB+AB’=A 의 관계를 적용시켜 변수를 간소화한다  간소화된 변수의 자리는 “-” 를 기입한다 예 ) A’B’C’D’ 와 A’BC’D’ 의 2 개 항은 A’-C’D’ 로 간소화  새로 얻어진, 즉 1 개의 변수가 “-” 로 바뀐 최소항에 대해 ③과정을 반복 수행한다 …

31 Quine-McClusky 방법 ( 계속 ) 예 제 ) F(w,x,y,z) =Σ(1,4,6,7,8,9,10,11,15) 에 대해서 Quine-McClusky 방법을 이용하여 PI, EPI 를 구하고 SOP 형식으로 간소화 하라 1) 주어진 함수에 대한 진리표를 작성한다 YZ WX a) F 의 K-MAP w x y zF m1m m4m m6m m7m m8m m9m9 10 m m m 15 b) F 의 진리표 m 4 항에대한 인접항은 m 0, m 5, m 6, m 12 “1” 이 2 개 포함 “1” 이 1 개 포함

32 Quine-McClusky 방법 ( 계속 ) w x y z ) 진리표로부터 “1” 의 갯수별로 그룹화 한다 AB+AB’=A 3) 인접 최소항 사이에 AB+AB’=A 의 관계를 적용시켜 변수를 간소화 연결 w x y z 1, 인접안함 인접함 4, , , , , , , , ) 새로 얻어진 최소항에 대해 3) 과정을 반복 1 단계 연결 w x y z 8,9,10, ※ 더 이상 인접항과 간소화 되지 않으므로 PI ※ ※ ※ ※ 2 단계 ※

33 Quine-McClusky 방법 ( 계속 ) 5) 이상의 결과로부터 PI table 을 작성한다 ,9x’y’z 4,6w’xz’ 6,7w’xy 7,15xyz 11,15wyz 8,9,10,11wx’ √ √√ √√ √ √ √ √√ √√√√ 다른 implicant 에 속하지 않는 1 을 포함하므로 EPI 가 된다 PI = x’y’z, w’xz’, w’xy, xyz, wyz, wx’ EPI = x’y’z, w’xz’, wx’ F = x’y’z + w’xz’ + xyz + wx’

34 Quine-McClusky 방법 ( 계속 ) 예 제 ) F(w,x,y,z) =Σ(0,1,2,8,10,11,14,15) 를 Quine-McClusky 방법으로 간략화하라 1 단계 간소화 2 단계 간소화

35 Quine-McClusky 방법 ( 계속 ) PI table PI = EPI = w’x’y’, x’z’, wy F = w’x’y’ + x’z’ + wy