Chapter 01 디지털 논리회로

디지털 논리회로 논리 회로(2진 논리 전자 회로) – P14 논리 게이트(논리 소자) 컴퓨터 내부에서 정보를 처리하기 위한 회로 0과 1의 전기적 신호를 사용해서 표현하고 동작하는 전자 회로 논리 게이트(논리 소자) 논리 회로의 기본적인 구성 요소(처리 요소) 0과 1의 2가지 상태의 값을 사용 입출력 값 표현을 위해 논리 변수 A, B 등의 사용이 가능 기능을 불 함수식 또는 진리표로 나타낼 수 있음

디지털 논리회로 0과 1의 전압 표현 0과 1의 펄스 표현 논리 1은 높은 전압(양 논리: positive logic) 논리 0은 낮은 전압(음 논리: negative logic) 0과 1의 펄스 표현 양 논리에서는 펄스가 있으면 1, 없으면 0 음 논리에서는 펄스가 있으면 0, 없으면 1

논리회로 논리곱(AND) – P15 2개의 2진 변수 입력 A,B가 모두 1(ON)인 경우만 결과가 1(ON)이고, 나머지 경우는 모두 0(OFF) 두 입력 A, B 중에서 하나라도 0(OFF)이면 결과는 0(OFF) 연산 기호는 X 또는  을 사용하거나 생략할 수 있음(AXB, AB, AB) 동시 만족 조건 , 교집합

논리회로 논리합(OR) – P16 2개의 2진 변수 입력 A,B가 모두 0(OFF)인 경우만 결과가 0(OFF)이고, 나머지 경우는 모두 1(ON) 두 입력 A, B 중에서 하나라도 1(ON)이면 결과는 1(ON) 연산 기호는 +를 사용

논리회로 논리 부정(NOT) – P16 2진 변수입력 A가 0(OFF)이면 결과가 1(ON), 1(ON)이면 결과가 0(OFF) NOT의 논리식 표현은 A 또는 A’

논리회로 배타적 논리합 (XOR) – P17 2개의 2진 변수 입력 A,B의 내용이 서로 다르면 결과가 1(ON), 내용이 같으면 결과가 0(OFF) 연산기호:  AB’ + A’B와 같은 논리 관계를 갖고 AB, A XOR B와 같이 표현 비교

논리회로 전압 입력에 대한 각 논리회로의 출력 전압 입력 전압 출력 전압

논리회로 그 밖의 논리회로 - P18 기본적인 논리 게이트인 AND, OR, NOT, XOR 외에 데이터를 저장하는 버퍼와 NOT 게이트가 다른 게이트와 결합된 것을 독립적인 게이트로 취급할 수 있음

논리회로 NAND 게이트 디지털 시스템에서 보편적으로 사용 NOT 연산은 1-입력 NAND 게이트로 구현 AND 연산은 2개의 NAND 게이트로 구현 OR 연산은 3개의 NAND 게이트로 구현

논리회로 NOR 게이트 NOT 연산은 1-입력 NOR 게이트로 구현 AND 연산은 3개의 NOR 게이트로 구현 OR 연산은 2개의 NOR 게이트로 구현

불 대수 불 대수(Boolean algebra) – P21 불 대수에서 사용되는 변수 기본 연산 불 대수의 사용 목적 1854년 조지 불이 논리학을 체계적으로 표현하기 위해 제안 논리수학의 대표적인 형태 논리회로의 설계에 이용되며 논리를 2진 변수의 식으로 표현하고 간소화함 불 대수에서 사용되는 변수 0과 1의 2치 변수(2-valued variable) 기본 연산 논리곱(AND), 논리합(OR), 논리 부정(NOT), 배타적 논리합(XOR) 불 대수의 사용 목적 진리표 및 논리 회로의 입출력 관계를 함수 형태로 표현 논리 회로를 같은 기능의 간단한 회로로 단순화

논리 회로의 간소화 A A AB B B X = AB + AB’ A X = A*B + A*B’ X = A*(B+B’)

불 대수의 기본 공식 기본 공식 – P22 논리곱(AND)의 법칙 논리합(OR)의 법칙 논리 변수를 사용하는 경우 0  1 = 0 , 1  1 = 1 => A  1 = A 논리합(OR)의 법칙 0 + 0 = 0 , 1 + 0 = 1 => A + 0 = A 0 + 1 = 1 , 1 + 1 = 1 => A + 1 = 1

불 대수의 기본 공식 부정의 법칙 (A’)’ = A 0 + 1 = 1 + 0 = 1 , A + A’ = 1

불 대수의 기본 공식 교환 법칙 결합 법칙 논리 변수의 순서를 변경하여 연산을 수행해도 동일한 결과를 가짐 A + B = B + A A  B = B  A 결합 법칙 괄호의 순서를 변경하여 연산을 수행해도 동일한 결과를 가짐 A + (B + C) = (A + B) + C A  (B  C) = (A  B)  C

불 대수의 기본 공식 분배 법칙 중복의 법칙 공통의 논리 변수를 괄호 내부의 논리 변수들에 할당해도 결과는 동일함 A  (B + C) = (A  B) + (A  C) A + (B  C) = (A + B)  (A + C) 중복의 법칙 자기를 복제하고 그것을 중복해서 논리곱 또는 논리합 해도 결과는 동일함 A = A  A , A = A  A  A  A A = A + A , A = A + A + A + A

불 대수의 기본 공식 드 모르간의 법칙 – P23 전체 부정의 논리식에 대한 간소화 작업에 이용 논리식의 전체 부정을 각 변수의 부분 부정으로 바꾸고, 각 변수에 사용된 연산자를 변경(ANDOR)할 경우 두 결과는 동일 [아래의 표를 참조]

불 대수의 기본 공식 드 모르간의 법칙 – P23 A B · A B + 1) 전체 부정을 부분 부정으로 변환 = A B A B 1) 전체 부정을 부분 부정으로 변환 = A B A B = 2) 연산자 변환 ( AND OR ) A B + A B ·

불 대수의 기본 공식 드 모르간의 법칙 예 [교재 24~26] 예제 참조

불 대수의 기본 공식 논리식 X = AB + AB’ + A’B 를 간소화하시오 * 각 항의 변수 개수를 통일 ▶ 2개항을 선택해서 공통부분을 활용 * 풀이 방법-1 X = AB + AB’ + A’B (분배) X = A(B + B’) + A’B (부정) X = A·1 + A’B (논리곱) X = A + A’B (분배) X = (A + A’) (A + B) (부정) X = 1·(A + B) (논리곱) X = A + B

불 대수의 기본 공식 논리식 X = AB + AB’ + A’B 를 간소화하시오 * 각 항의 변수 개수를 통일 ▶ 중복의 법칙을 활용 * 풀이 방법-2 X = AB + AB’ + A’B + AB (중복) X = AB + AB’ + A’B +AB (분배) X = A(B+B’) + B(A+A’) (부정) X = A·1 + B·1 (논리곱) X = A + B 23

카르노 도표 불 대수 vs. 카르노 도표 F(X,Y)=X’Y’ + X’Y + XY’ - 도표 안에 있는 1을 묶는다 - 상하좌우에 위치한 ‘1’을 가능한 크게 2n으로 묶는다 F(X,Y)=X’Y’ + X’Y + XY’ X Y 0 0 0 1 F(X,Y) = X’Y’ + X’Y + XY’ + X’Y’ X’ F(X,Y) = X’(Y’ + Y) + Y’(X + X’) (1)도표 그리기 , (2)논리식 구하기 X Y F(X,Y) = X’(1) + Y’(1) 0 1 0 0 Y’ F(X, Y) = X’ + Y’ F(X, Y) = X’ + Y’

카르노 도표 F(X,Y) = X’Y’ + X’Y + XY’ F(X,Y) = X’ + Y’ X Y X’ Y’ X Y’ 간소화 과정은 비용 절감 및 성능 향상의 장점으로 논리 회로 구현에 필수적 과정

카르노 도표 민텀(minterm) - P26 n개 입력변수의 불 함수에서 입력변수의 논리곱으로 만들어진 항 n개의 변수에 대해서는 2n개의 민텀을 가짐 카르노 도표를 이용한 간소화 작업에 이용 X Y F 1 X Y Z F 1

카르노 도표 민텀(minterm) 2개 변수 => x, y => x와 y의 경우의 수 x=0=x’ , x=1=x y=0=y’ , y=1=y => x, y의 민텀은 22개(4개) => x’y’, x’y, xy’, xy => 00 , 01 , 10 , 11 3개 변수 => x, y, z => x와 y, z의 경우의 수 z=0=z’ , z=1=z => x, y, z의 민텀은 23개(8개) => x’y’z’ , x’y’z , x’yz’ , x’yz , xy’z’ , xy’z , xyz’ , xyz => 000 , 001 , 010 , 011 , 100 , 101 , 110 , 111

카르노 도표 카르노 도표 – P26 2변수 카르노 도표_1 복잡한 논리식을 간단히 하기 위해 사용되는 진리표의 n차원적 도표 일반적으로 2 변수 카르노 도표, 3 변수 카르노 도표, 4 변수 카르노 도표가 사용됨 2변수 카르노 도표_1 2개의 논리변수는 조합 가능한 수가 4개이므로, 4칸의 카르노 도표를 사용하고 상하좌우 이웃한 칸을 인접한 것으로 처리해 간소화시킴 간소화 과정 진리표에서 출력이 1 값인 입력 변수의 민텀항을 카르노 도표에 1로 표시 인접한 1끼리 묶은 후 아래의 과정에 따라 간소화 작업을 진행 인접한 것이란 대각선을 제외한 상하좌우에 위치한 것을 의미함 인접한 것을 묶을 때 가능한 크게 2n으로 묶어야 함 인접한 것의 묶음은 1개의 변수로 대체되며, 이들 모두의 논리합이 최종 결과가 됨

카르노 도표 2변수 카르노 도표_2 (논리식= 진리표= 카르노도표= 입출력관계) X=0 이고 Y=0 인 상태 F 1 X Y F 1 X=0 이고 Y=0 인 상태 X=0 이고 Y=1 인 상태 X=1 이고 Y=0 인 상태 X=1 이고 Y=1 인 상태 위치정보 : minterm=경우의 수 , 결과

카르노 도표 2변수 카르노 도표_3 (카르노 도표 그리기) 출력 F는 X,Y가 1,1인 경우에만 1(참) 값을 표시 AND : F(X,Y) = XY X Y F 1 1 출력 F는 X,Y가 0,1 또는 1,0 또는 1,1 인 경우 1(참) 값을 표시 OR : F(X,Y) = X’Y + XY’ + XY X Y F 1 1

카르노 도표 2변수 카르노 도표_4 (카르노 도표 그리기) - P27 논리식 F(X,Y)= X’Y’+ X’Y+ XY’= (0,1,2)를 카르노 도표로 간소화하시오. 2변수 카르노 도표 그리기 논리식의 3개 민텀 항 X’Y’, X’Y, XY’을 카르노 도표의 해당 위치에 표시 00 , 01 , 10 X Y F 1

카르노 도표 2변수 카르노 도표_5 (카르노 도표의 간소화) 논리식 F(X,Y)= X’Y’+ X’Y+ XY’ 를 카르노 도표를 이용하여 간소화하시오. - 도표 안의 상하좌우에 위치한 1을 가능한 크게 2n으로 묶는다 X Y 0 0 0 1 X’ X Y 0 1 0 0 F(X, Y) = X’Y’ + X’Y + XY F(X, Y) = X’ + Y’ Y’

카르노 도표 3변수 카르노 도표_1 - P28 논리식의 입력 변수가 3개인 경우로 이들 세 변수로 결합되는 조합의 수는 8가지이므로 8칸의 카르노 도표를 이용 카르노 도표에 민텀의 결과가 1인 것만을 표시 변수가 3개인 경우 양끝의 내용들은 인접한 것으로 처리 1인 것을 묶을 때, 2의 배수(2n)이면서 최대한 큰 것으로 묶음 1칸(20)은 3개의 변수로 표현 인접한 2칸(21)의 묶음은 2개의 변수로 표현 인접한 4칸(22)의 묶음은 1개의 변수로 표현

카르노 도표 3변수 카르노 도표 - 입력 변수 값의 순서 XY 00 01 10 11 XY 00 01 11 10 XY X’Y’ X’Y XY’ XY XY X’Y’ X’Y XY XY’ XY X’Y’ X’Y XY XY’

카르노 도표 3변수 카르노 도표- 2n묶임 형태 X’Y’ X’Z X’Y X’Z’ Y’ Z’

카르노 도표 3변수 카르노 도표_2 – P29 논리식 F(X, Y, Z) = XY’Z’ + XY’Z + XYZ + XYZ’를 간략화하는 예 3개의 변수로 XY’Z’, XY’Z, XYZ, XYZ’가 각각 표현되기 때문에 4개의 항이 다음과 같이 표시됨 1로 표시된 인접 부분을 묶어 주면 다음과 같이 표시할 수 있으며, 인접한 4칸은 1개의 변수로 표현되므로 F(X, Y, Z) = X로 다음과 같이 간소화

카르노 도표 3변수 카르노 도표_3 – P29 논리식 F(X,Y,Z)= X’Y’Z’+XY’Z’+X’YZ’+XYZ’를 간략화하는 예 3개 변수로 X’Y’Z’, XY’Z, X’YZ’, XYZ’가 각각 표현되므로 4개의 항에 다음과 같이 표시 1로 표시된 인접 부분을 묶어 주면 아래 그림과 같이 표현할 수 있으며, 인접한 4칸은 1개의 변수로 표현되므로 F(X, Y, Z) = Z’로 간소화됨 F(X,Y,Z) = (0,1,2,4,5,6)

카르노 도표 4변수 카르노 도표_1 - P30 논리식 입력 변수가 4개이면 이들이 결합되는 조합의 수가 16개이므로 카르노 도표의 모양은 16개 칸의 민텀 항으로 표현됨 카르노 도표에 민텀의 결과가 1인 것만을 표시 변수가 4개인 경우 양끝의 내용은 인접한 것으로 처리 인접한 1을 묶을 때, 2의 배수(2n=2,4,8,16) 형태로 최대한 크게 묶음 1칸은 4개의 변수로 표현 인접한 묶음이 2칸, 4칸, 8칸은 3개,2개,1개의 변수로 표현

카르노 도표 4변수 카르노 도표_2 – P31 논리식 F(W, X, Y, Z) = W’X’Y’Z’ + W’X’Y’Z + W’XY’Z’ + W’XY’Z + WXYZ + WXYZ’ + WX’YZ + WX’YZ’를 카르노 도표로 간략화하는 예 4개의 변수로 W’X’Y’Z’, W’X’Y’Z, W’XY’Z’, W’XY’Z, WXYZ, WXYZ’, WX’YZ, WX’YZ’가 각각 표현되므로 8개의 항에 아래와 같이 표현 F(W,X,Y,Z) = (0,1,2,3,4,5,9,10,11,14,15)

카르노 도표 1로 표시된 인접 부분을 묶어 주면 아래 그림과 같이 표현할 수 있으며, 인접한 4칸은 2개의 변수로 표현되므로 F(W, X, Y, Z) = W’Y’ + WY로 간소화 됨 간소화된 논리식을 논리곱의 논리합 (sum of products) 형태로 아래그림과 같은 논리 게이트 회로로 표현

카르노 도표 논리합의 논리곱 – P33 카르노 도표에서 민텀 항이 1이 아닌 0인 항을 가지고 간소화하는 방법 0인 항의 인접 부분을 묶어서 간소화한 내용은 논리식 F의 F’이 되고, 이 F’에 다시 부정을 취하면 원래의 F를 구할 수 있음 F(X, Y, Z) = X’Y’Z + XY’Z’ + XY’Z + XYZ’에 대한 논리합의 논리곱 형식으로 간소화하는 과정 불 정리를 이용한 간소화

카르노 도표 카르노 도표를 이용한 간소화 논리곱의 논리합 형태로 간소화하기 위해 해당되는 민텀에 1을 표시 위의 그림을 간소화하면, F(X, Y, Z) = Y’Z + XZ’가 됨

카르노 도표 논리합의 논리곱 형태로 나타내기 위해서는 1이 아닌 0의 항을 아래 그림과 같이 묶어 간소화 하면 F(X, Y, Z)’ = YZ + X’Z’가 됨 F = (F’)’으로 AND와 OR로 표현하면 아래 그림과 같이 나타남 (F(X, Y, Z)’)’=(YZ + X’Z’)’ => F(X, Y, Z)=(Y’+Z’)(X+Z)

카르노 도표 3 변수 X, Y, Z에 대한 아래의 표를 통해서 논리곱의 논리합 또는 논리합의 논리곱 두 방식의 결과가 모두 동일한 값임이 증명됨 F = (F’)’를 NAND와 NOR로 표현하면 아래 그림과 같이 나타남

카르노 도표 Don’t care 조건 – P36 카르노 도표의 민텀 항의 값은 보통 1 또는 0 값을 가지지만 민텀 항의 값이 0 또는 1의 아무 값을 가져도 상관없는 조건을 Don’t care라 함 도표에서는 X로 표시하고 논리식은 d(X, Y)로 표현함 함수의 간소화에 사용되며, 간소화하는 과정에 따라서 X를 포함할 수도 있고 포함하지 않을 수도 있음 Don’t care 조건을 이용하여 아래의 불 함수 F를 간소화하는 예 카르노 도표로 간소화하면 F(X, Y, Z) = X’ + Z가 됨

카르노 도표 Don’t care 조건을 이용하여 아래의 불 함수 F를 논리곱의 논리합의 형식으로 간소화 하는 예 카르노 도표를 이용하여 간소화

카르노 도표 Don’t care 조건을 이용하여 아래의 불 함수 F를 논리합의 논리곱 형식으로 간소화 하는 예 F’=W’X+YZ이므로 이를 보수 취하면 (F’)’=(W’X+YZ)’=(W+X’)(Y’+Z’)가 됨

주요 학습 내용 논리회로와 논리 게이트 기본 논리 (AND, OR, NOT, XOR)와 회로 구성 불 대수와 논리식의 간소화 카르노 도표 Don’t care 조건