3장. 디지털 회로 Lecture #3

3.1 디지털 논리 게이트 (1) 디지털 : 0과 1만 이용하여 표현하는 방법 논리 게이트 : 0과 1을 이용하여 2진 논리 연산을 수행하는 게이트 양의 논리와 음의 논리 컴퓨터 구조론

3.1 디지털 논리 게이트 (2) 인버터와 버퍼의 배치 드라이브 버퍼 게이트 인버터 게이트(NOT 게이트) x F 1 x F F = NOT x x F 1 (a) 진리표 (b) 버퍼 게이트의 기호 (c) 사각 기호 x F 1 (a) 진리표 (b) NOT 게이트의 기호 (c) 사각 기호 컴퓨터 구조론

3.1 디지털 논리 게이트 (3) 인버터 게이트(NOT 게이트) 버퍼와 인버터 및 배치 드라이브 IC 펄스 연산 입력펄스 x 1 출력펄스 F (a) C-MOS : MC14050B(버퍼) 컴퓨터 구조론

3.1 디지털 논리 게이트 (4) 버퍼와 인버터 및 배치 드라이브 IC (b) TTL : SN74LS04(인버터) (c) TTL 버퍼/드라이브의 예(SN74LS365A) 컴퓨터 구조론

3.1 디지털 논리 게이트 (5) AND 게이트와 NAND 게이트 AND 게이트 F = x AND y = x × y = x · y = xy x y F 1 x x & F F y y (a) 진리표 (b) AND 게이트의 기호 (c) 사각 기호 컴퓨터 구조론

3.1 디지털 논리 게이트 (6) AND 게이트 펄스 연산 1 입력펄스 x 1 입력펄스 y 1 출력펄스 F 컴퓨터 구조론

3.1 디지털 논리 게이트 (7) NAND 게이트 F = x · y = x + y x y F 1 x x F F y y & 1 x x & F F y y (a) 진리표 (b) NAND 게이트의 기호 (c) 사각 기호 컴퓨터 구조론

3.1 디지털 논리 게이트 (8) NAND 게이트 펄스 연산 1 입력펄스 x 1 입력펄스 y 1 출력펄스 F 컴퓨터 구조론

3.1 디지털 논리 게이트 (9) AND 게이트와 NAND 게이트 IC (a) TTL : SN74LS21 (4-입력 AND 게이트 ) (b) TTL : SN74LS002 (2-입력 NAND 게이트) (c) C-MOS : MC74HC11 (3-입력 AND 게이트) (d) C-MOS : MC14011B (2-입력 NAND게이트) 컴퓨터 구조론

3.1 디지털 논리 게이트 (10) OR 게이트와 NOR 게이트 OR 게이트 F = x + y x y F 1 x x F F y 1 x x ≥1 F F y y (a) 진리표 (b) OR 게이트의 기호 (c) 사각 기호 컴퓨터 구조론

3.1 디지털 논리 게이트 (11) OR 게이트 펄스 연산 1 입력펄스 x 1 입력펄스 y 1 출력펄스 F 컴퓨터 구조론

3.1 디지털 논리 게이트 (12) OR 게이트와 NOR 게이트 NOR 게이트 F = x + y = x · y x y F 1 1 x x ≥ 1 F F y y (a) 진리표 (b) NOR 게이트의 기호 (c) 사각 기호 컴퓨터 구조론

3.1 디지털 논리 게이트 (13) NOR 게이트 펄스 연산 1 입력펄스 x 1 입력펄스 y 1 출력펄스 F 컴퓨터 구조론

3.1 디지털 논리 게이트 (14) OR 게이트와 NOR 게이트 IC (a) TTL : SN74LS32 (2-입력 OR 게이트) (b) TTL : SN74LS02 (2-입력 NOR 게이트) (c) C-MOS : MC14071B (2-입력 OR 게이트) (d) C-MOS : MC74C4078 (8-입력 OR/NOR 게이트) 컴퓨터 구조론

3.1 디지털 논리 게이트 (15) XOR 게이트와 XNOR 게이트 XOR 게이트 F = xy + xy = x y x y F 1 x x =1 F F y y (a) 진리표 (b) XOR 게이트의 기호 (c) 사각 기호 컴퓨터 구조론

3.1 디지털 논리 게이트 (16) XOR 게이트 펄스 연산 1 입력펄스 x 1 입력펄스 y 1 출력펄스 F 컴퓨터 구조론

3.1 디지털 논리 게이트 (17) XOR 게이트와 XNOR 게이트 XNOR 게이트 F = x y + x y = x ⊙ y x 1 x x =1 F F y y (a) 진리표 (b) XNOR 게이트의 기호 (c) 사각 기호 컴퓨터 구조론

3.1 디지털 논리 게이트 (18) XNOR 게이트 펄스 연산 1 입력펄스 x 1 입력펄스 y 1 출력펄스 F 컴퓨터 구조론

3.1 디지털 논리 게이트 (19) XOR 게이트와 XNOR 게이트 IC XOR 게이트와 XNOR 게이트의 응용 (a) TTL : SN74LS86 (2-입력 X OR 게이트) (b) C-MOS : MC74HC266 (2-입력XNOR 게이트) NAND로 구성된 XOR 게이트 XNOR 게이트에 의한 일치 검출 회로 컴퓨터 구조론

3.1 디지털 논리 게이트 (20) 3-상태 버퍼 출력이 3가지 상태인 특수 기호의 게이트 3-상 버퍼회로 S=0일 경우 3-상태 버퍼 회로는 high impedance가 되어 회로는 off 상태가 된다. S=1일 경우 3-상태 버퍼 회로는 on 상태가 되어 x=0이면 0이 출력되고, x=1이면 1이 출력된다. x S F High impedance 1 컴퓨터 구조론 [ 기호 및 진리표 ]

3.1 디지털 논리 게이트 (21) 3-상 인버터회로 S=0일 경우 3-상태 버퍼 회로는 on 상태가 되어 x=1이면 0이 출력되고, x=0이면 1이 출력된다. S=1일 경우 3-상태 버퍼 회로는 고임피던스가 되어 회로는 off 상태가 된다. x S F 1 High impedance [ 기호 및 진리표 ] 컴퓨터 구조론

3.1 디지털 논리 게이트 (22) 결선형 AND와 결선형 OR 결선형 AND 일부분의 NAND와 NOR게이트의 두 게이트의 출력을 직접 연결함으로써 논리 기능을 할 수 있게 한 것 회로의 비용 절감과 하나의 보드(board) 또는 카드(card)에 보다 많은 논리 기능을 포함시킬 수 있다. [ AND 결합 ] [ 직접 결합 ] [ F = wx · yz = wx+yz ] 컴퓨터 구조론 [ open-collector TTL 게이트 결선형 AND ]

3.1 디지털 논리 게이트 (23) 결선형 AND와 결선형 OR 결선형 OR ECL(Emitter Coupled Logic) 게이트의 NOR 게이트의 출력을 함께 결선 [ OR 결합 ] [ 직접 결합 ] [ F = w+x + y+z = w+x · y+z ] [ ECL 결합 NOR 게이트 결선형 OR ] 컴퓨터 구조론

3.1 디지털 논리 게이트 (24) 논리 게이트의 요약 각 게이트 기호와 사각기호 그리고 진리표 정리 명 칭 기 호 사각 기호 기 호 사각 기호 대 수 식 진 리 표 Buffer 1 F = x x F x F x F 명 칭 기 호 사각 기호 대 수 식 진 리 표 NOT 1 F = x x F x F x F 컴퓨터 구조론

3.1 디지털 논리 게이트 (25) 명 칭 기 호 사각 기호 대 수 식 진 리 표 OR  1 F = x + y x x F F 기 호 사각 기호 대 수 식 진 리 표 OR  1 F = x + y x y F 0 0 0 1 1 0 1 1 1 x x F F y y 명 칭 기 호 사각 기호 대 수 식 진 리 표 AND & F = x y x y F 0 0 0 1 1 0 1 1 1 x x F F y y 명 칭 기 호 사각 기호 대 수 식 진 리 표 NOR 1 F = x + y x y F 0 0 0 1 1 0 1 1 1 x x F F y y 컴퓨터 구조론

3.1 디지털 논리 게이트 (26) 명 칭 기 호 사각 기호 대 수 식 진 리 표 NAND & F = x · y x x F F 기 호 사각 기호 대 수 식 진 리 표 NAND & F = x · y x y F 0 0 0 1 1 0 1 1 1 x x F F y y 명 칭 기 호 사각 기호 대 수 식 진 리 표 XOR =1 F = x y + x y = x  y x y F 0 0 0 1 1 0 1 1 1 x x F F y y 명 칭 기 호 사각 기호 대 수 식 진 리 표 XNOR =1 F = x y + x y = x  y x y F 0 0 0 1 1 0 1 1 1 x x F F y y 컴퓨터 구조론

3.2 부울대수 (1) 부울대수(boolean algebra)를 근거로 한 스위칭 이론(switching theory)은 논리설계에 있어서 이론적인 근거가 되는 수학적 체계이다. 부울대수의 가설 : 헌팅턴이 제시한 가설에 의하여 두 개의 2진 연산자 +, · 와 집합 B로 정의된 대수 체계이다. 닫힘(closure) : 모든 a,b∈B에 대하여 a + b ∈ B a · b ∈ B 교환법칙(commutative law) : 모든 a,bB에 대하여 a + b = b + a a · b = b · a 컴퓨터 구조론

3.2 부울대수 (2) 결합법칙(associative law) : 모든 a,b ∈ B 에 대하여 (a + b)+c=a+(b+c) (a · b) · c=a · (b · c) 분배법칙(distributive law) : 모든 a,b ∈ B 에 대하여 a · (b+c) = (a · b)+(a · c) a+(b · c) = (a+b) · (a+c) 보수(complement) : 모든 a ∈ B에 대하여 a가 a의 보수라 하면 a + a = 1 a · a = 0 a≠b를 만족하는 적어도 두개의 원소 a,b ∈ B가 존재. 컴퓨터 구조론

3.2 부울대수 (3) 부울대수의 기본 규칙 x+y · z = (x+y)(x+z) 공리 2. 항등원 존재 : x + 0 = x x · 1= x 공리 3. 교환법칙 : x + y = y + x x · y = y · x 공리 4. 분배법칙 : x ·(y+z) = x · y + x · z x+y · z = (x+y)(x+z) 공리 5. 역의 존재 : x + x = 1 x · x = 0 정리 1. 멱등법칙 : x + x = x x · x = x 정리 2. 한계법칙 : x + 1 = 1 x · 0 = 0 정리 3. 대합성 : x = x 정리 4. 결합법칙 : x+(y+z) = (x+y)+z x ·(y · z)=(x · y) · z 컴퓨터 구조론

3.2 부울대수 (4) 정리 5. 드모르강 법칙 정리 6. 흡수 법칙 정리 7. 합치법칙 정리 8. 인접법칙 x + y = x · y x · y = x + y 정리 6. 흡수 법칙 x + x · y =x x ·(x + y)=x 정리 7. 합치법칙 x · y + x · z + y · z = x · y + x · z (x+y)(x+z)(y+z) =(x+y)(x+z) 정리 8. 인접법칙 x + x · y = x + y x + x · y = x + y 컴퓨터 구조론

3.2 부울대수 (5) 쌍대성 부울대수 가설에 의하여 연산자와 항등원을 대치하더라도 성립한다. AND ⇔ OR, 0 ⇔ 1 (x · y ) + z = (x + z) · (y + z) ↕ ↕ ↕ ↕ ↕ (x + y ) · z = (x · z) + (y · z) 컴퓨터 구조론

3.3 부울 함수 (1) 부울함수 표현 F1 = xyz, F2 = xy + xz x y z F1 F2 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 컴퓨터 구조론

3.3 부울 함수 (2) 부울함수 표현 F3 = xy + xz + yz의 진리표와 논리회로 x y z F3 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 컴퓨터 구조론

3.3 부울 함수 (3) 부울 함수의 간소화 간소화 간소화 방법 게이트의 수와 게이트의 입력이 되는 변수를 줄이는 것 부울함수로 표현 부울 대수의 항등식 규칙 등으로 간소화 회로 구성 간소화 방법 항 결합 : 두 개의 항을 결합하여 하나의 항으로 정리. x y + x y = ( x + x ) y = 1 · y = y 항 제거 : 항들을 제거하기 위하여 사용되는 정리 x y + y = y · 1 = y 컴퓨터 구조론

3.3 부울 함수 (4) 부울 함수의 간소화 간소화 방법 문자 제거 : 문자들을 제거하기 위하여 사용되는 정리를 말한다. x + x y = x ( y + y ) + x y = x y + x y + x y = x ( y + y ) + y ( x + x ) = x + y 함수식의 의미가 변하지 않도록 주의해야 하며, 적절한 항들을 함수식에 첨가. x y z + x y z + x y z = x y z + x y z + x y z + x y z = x z ( y + y ) + x y ( z + z ) = x z + x y 컴퓨터 구조론

3.3 부울 함수 (5) 콘센서스 정리 부울 대수식에서 콘센서스 항을 더해도 부울 대수식은 변하지 않음을 말한다. 공리와 정리 이용하여 간소화 부울 표현식을 최소화 하는데 유리 예) F = x y + y z + x z x z와 y z 항의 콘센서스 항은 x y 항이므로 이를 제거한다. F = x y + x z + y z = x z + y z 컴퓨터 구조론

3.3 부울 함수 (6) 함수의 보수 방법1.부울함수 F에서 1은 0로, 0은 1으로 바꾼다. 방법2. 드모르강 정리를 이용해 AND를 OR로, OR를 AND로 서로 바꾸고, 각 변수의 값도 1을 0로, 0을 1로 바꾼다. 방법3.연산자들의 쌍대를 구한 후 각 변수의 값에 보수를 취한다. 예) F = x y z + x y z + x z  F = ( x + y + z )( x + y + z )( x + z ) 컴퓨터 구조론

3.4 부울 함수의 정형과 표준화 (1) 최대항과 최소항 논리회로를 부울함수로 나타내는 경우 AND게이트는 논리곱, OR게이트는 논리합으로 나타냄. 최소항 또는 표준곱(standard product) : 2개의 변수 x와 y에 대해서는 4가지 조합( x·y, x·y, x·y, x·y)이 가능하며, AND연산의 항으로 표시되는 것을 말함. 최대항 또는 표준합(standard sum) : 2개의 변수 x와 y에 대해서는 4개의 조합(x+y, x+y,x+y,x+y)이 가능하며, OR연산의 항으로 표시되는 것을 말함. N개의 변수는 2n개의 최소항, 최대항으로 구성되고 0부터 2n-1까지가 n개의 변수가 된다. 변수의 값이 0일때는 ( : bar) 기호로 하고 1일 때는 붙이지 않는다. 컴퓨터 구조론

3.4 부울 함수의 정형과 표준화 (2) 3변수에 대한 최소항과 최대항의 진리표 변 수 최 소 항 최 대 항 함 수 x y z 변 수 최 소 항 최 대 항 함 수 x y z 항 표시 F1 F2 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 z m0 m1 m2 m3 m4 m5 m6 m7 x + y + z M0 M1 M2 M3 M4 M5 M6 M7 1 컴퓨터 구조론

3.4 부울 함수의 정형과 표준화 (3) 곱의 합형 합의 곱형 표현 F(x,y,z) = ∑m(1,3,5) = x y z + x y z + x y z ∑(시그마) 기호는 각각의 AND 항들을 OR 결합한 것. 괄호 속의 숫자는 함수 값이 1인 최소항을 나타낸다. 합의 곱형 표현 F(x,y,z) = ∏M(0,3,7) = (x+y+z) (x+y+z) (x+y+z) ∏ (파이) 기호는 각각의 OR 항들을 AND 결합하는 것 괄호 속의 숫자는 함수의 값이 0인 최대항을 나타낸다. 컴퓨터 구조론

3.4 부울 함수의 정형과 표준화 (4) 최소항과 최대항의 관계 곱의 합형은 부울 대수식의 보수 곱의 합형과 합의 곱형의 변환 함수 값이 1인 최소항을 구하는 것 곱의 합형으로 표시된 부울 함수를 보수화한다. 함수 값이 0인 최소항을 곱의 합형인 부울 대수식 표현 mj = Mj 곱의 합형과 합의 곱형의 변환 곱의 합형으로 된 부울 함수를 보수화 한 후, 그 결과를 드모르강 정리에 의해 보수를 취하면 합의 곱형인 부울함수가 된다. F(x,y,z) = ∏M(0,2,4,5)를 곱의 합형으로 바꾸면 F(x,y,z) = ∑m(1,3,6,7) F(x,y,z) = ∑m(1,2,4,6)를 합의 곱형으로 바꾸면 F(x,y,z) = ∏M(0,3,5,7) 컴퓨터 구조론

3.4 부울 함수의 정형과 표준화 (5) 합의 곱형과 곱의 합형의 관계 곱의 합형으로 표시된 함수를 두번 보수화하면 합의 곱형이 되므로, 곱의 합형인 부울 함수와 동등한 합의 곱형인 부울함수는 같은 부울 함수가 된다. 예) F(x, y, z) = ∑m(1,4,5,6,7)을 보수화 F(x, y, z) = ∑m(0,2,3)=m0+m2+m3 F = F = m0+m2+m3 = m0 · m2 · m3 = M0 · M2 · M3 = ∏M(0,2,3) 컴퓨터 구조론

3.5 논리 회로의 간소화 (1) x x 카르노맵(karnaugh map) 진리표를 그림모양으로 나타낸 것이며, 여러 형태의 사각형으로 된 그림으로 각각의 최소항 또는 최대항으로 나타낸다. 2변수의 기본 카르노 맵 : 4개의 최소항 구성 F = x y + x y + x y y y 1 m0 m1 m2 m3 x x y x y x 1 x y F 1 y x 1 F = x + y   컴퓨터 구조론

3.5 논리 회로의 간소화 (2) 3변수의 카르노맵 : 3개의 2진 변수에 대한 8개의 최소항을 구성. 3변수의 카르노맵 : 3개의 2진 변수에 대한 8개의 최소항을 구성. F(x, y, z) = ∑m(0,2,3,4,6) y z y z y z y z 00 01 11 10 x m0 m1 m3 m2 m4 m5 m7 m6 x y z x 1 x y z F 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 Z xy 1 0 0 0 1 1 1 1 0   F = z + x y 컴퓨터 구조론

3.5 논리 회로의 간소화 (3) 4변수의 카르노 맵 : 16개의 최소항을 구성한다. 카르노 맵의 묶음 4변수의 카르노 맵 : 16개의 최소항을 구성한다. 카르노 맵의 묶음 반드시 2n(2,4,8,16…) 단위로 묶는다. 수직 혹은 수평 방향으로 인접한 원소들끼리 묶는다. y z y z y z y z 00 01 11 10 w x m0 m1 m3 m2 m4 m5 m7 m6 m12 m13 m15 m14 m8 m9 m11 m10 00 w x y z w x 01 w x 11 w x 10 컴퓨터 구조론

3.5 논리 회로의 간소화 (4) 무관조건(don’t-care condition) 입력변수에 따라 출력값에 영향을 미치지 않고, 함수를 더 간단하게 하는데 사용. 무관 조건이 있는 논리함수의 표현 F(w,x,y,z) =  m(1,3,5,7) +  d(0,4) 또는 F(w,x,y,z) =  M(1,4,6) ·  d(0,4) 이 식은 함수 F는 최소항 4개와 무관항 2개, 또는 최대항 3개와 무관항 2개로 표현. 무관 조건을 갖는 함수를 설계하면, 각 무관조건에 대하여 0또는 1의 값을 부여해 주어야 한다. (어떠한 값이라도 상관없다.) 컴퓨터 구조론

3.5 논리 회로의 간소화 (5) 논리 함수 구현 NAND 게이트 구현 [ 함수 구성 ] [ NAND 게이트 구현 ] 컴퓨터 구조론

3.5 논리 회로의 간소화 (6) 논리 함수 구현 NOR 게이트 구현 [ 함수 구성 ] [ NAND 게이트 구현 ] 컴퓨터 구조론 [ NAND 게이트 구현 ]

3.5 논리 회로의 간소화 (7) XOR와 XNOR 게이트 관계 비교 연산을 수행. 결합법칙과 교환법칙이 성립되며, 3개 이상의 변수들로 확장가능. [ AND, OR, NOT로 구성한 XOR 게이트 ] 컴퓨터 구조론 [ NAND게이트로 구성된 XOR게이트 ] [ XNOR게이트로 구성된 XOR게이트 ]