논리회로 설계 기초 (1) Lecture #1

전자 시스템 (1) 원하는 입력/출력 변환을 수행하는 블랙박스 전자시스템 분류 입력/출력 : 전기 신호 정보는 전기신호로 시스템 내에 입력되어, 시스템 안에서 처리 및 변환되고, 전기신호로 출력된다 전자시스템 분류 아날로그 시스템 전기신호의 크기가 시간에 따라 연속적(continuous) 형태로 변하는 전자 시스템 자연의 대부분의 사건은 시간에 대해 연속적인 형태로 변한다 디지털 시스템 전기신호의 크기가 시간에 따라 이산적(discrete) 형태로 변하는 전자 시스템 모바일특강

전자 시스템 (2) 모바일특강

디지털 시스템 디지털 시스템의 기본 형태 모바일특강

디지털 시스템 분류 디지털 시스템 분류 모바일특강

조합 논리 회로 조합 논리 회로(Combinational Logic Circuit) 회로의 출력이 현재 입력의 조합에 의해 정해지는 논리 회로 이전의 회로 상태가 출력에 영향을 미치지 않음  메모리 소자를 갖지 않는다 예: 이진 전가산기 등 모바일특강

(Minimized Logic Expression) 조합 논리 회로 설계 (1) 조합 논리 회로 설계 과정 회로 기능 명세 서술문 합성(Synthesis) 논리식 (Logic Expression) 최소화된 논리식 (Minimized Logic Expression) 구현(Implementation) 하드웨어 논리회로 모바일특강

조합 논리 회로 설계 (2) 조합 논리 회로에 대한 논리식 작성 조합 논리회로의 기능 명세 : 어떤 입력 조건에 대하여 원하는 출력을 서술적으로 묘사 논리식 : 조합 논리회의 동작인 입력/출력 변환 함수를 수학적으로 정의 서술문-논리식 변환: 단계 1: 논리회로의 입력과 출력을 식별하고, 각 입력과 출력에 대하여 논리 변수를 정의한다 단계 2: 모든 가능한 입력에 대하여 출력을 열거하는 진리표를 작성한다 단계 3: 진리표로부터 정준형(Canonical Form)의 논리식을 유도한다 모바일특강

조합 논리 회로 설계 (3) 조합 논리 회로 설계 예: 서술문-논리식 변환 두 개의 이진수와 올림수를 더해 합과 올림수를 계산하는 이진 전가산기(Full Adder)을 설계한다. 서술문-논리식 변환 단계 1: 입력 - 이진수 X, Y / 올림수 Cin 출력 - 합 Sum / 올림수 Cout 단계 2 : 회로 기호 및 진리표 모바일특강

조합 논리 회로 설계 (4) 서술문-논리식 변환 (계속) 단계 3: 정준형 논리식 작성 정준합형(Canonical sum form) – Sum of Product Sum = X’•Y’ •Cin + X’•Y•Cin’ + X•Y’•Cin’ + X•Y•Cin Cout = X’•Y•Cin + X•Y’•Cin + X•Y•Cin’ + X•Y•Cin  Sum = m1 + m2 + m4 + m7 = ∑m(1, 2, 4, 7) Cout = m3 + m5 + m6 + m7 = ∑m(3, 5, 5, 7) 최소항 (Minterm) 최소항 전개식 (Minterm List) 모바일특강

조합 논리 회로 설계 (5) 서술문-논리식 변환 (계속) 단계 3: 정준형 논리식 작성 정준곱형(Canonical product form) – Product of Sum Sum = (X’+Y’+Cin’)•(X’+Y+Cin)•(X+Y’+Cin)•(X+Y+Cin’) Cout = (X’+Y’+Cin’)•(X’+Y’+Cin)•(X’+Y+Cin’)•(X+Y’+Cin’)  Sum = M0 + M3 + M5 + M6 = ∏M(0, 3, 5, 6) Cout = M0 + M1 + M2 + M4 = ∏M(0, 1, 2, 4) 최대항 (Maxterm) 최대항 전개식 (Maxterm List) 모바일특강

조합 논리 회로 설계 (6) 논리식의 최소화 대수적 간소화 카르노우 도표(Karnaugh Maps) 콰인-맥클러스키 표 논리회로의 복잡성과 비용은 일반적으로 논리 다이어그램의 복잡성에 직접적으로 비례 논리식에서 논리연산자의 수와 연산자에 대한 입력의 개수를 최소화하는 과정이 요구됨 논리식 최소화 기법 대수적 간소화 카르노우 도표(Karnaugh Maps) 콰인-맥클러스키 표 모바일특강

조합 논리 회로 설계 (7) 논리식의 최소화 : 대수적 간소화 부울대수(Boolean Algebra)의 법칙과 정리를 이용하여 논리식을 간소화 모바일특강

조합 논리 회로 설계 (8) 논리식의 최소화 : 대수적 간소화 (계속) 대수적 논리식 간소화의 4가지 방법 항 결합 : [X•Y+X•Y’=X] 정리를 이용하여 두 항을 결합한다 항 제거 : [X+X•Y=X] 정리를 이용하여 가능한 불필요한 항을 제거한 후, [X•Y+X’•Z+Y•Z=X•Y+Y•Z] 정리를 적용하여 일치하는 항들을 제거한다 변수 제거 : [X+X’•Y=X+Y] 정리를 이용하여 중복되는 변수들을 제거한다 중복 항의 첨가 : 중복되는 항은 X•X’를 더하거나, (X+X’)를 곱하거나, X’Z를 X•Y+Y•Z에 더하거나, X•Y를 X에 더하는 등의 다양한 방법으로 첨가함으로써 중복된 항이 다른 항과 결합하거나 다른 항을 제거하도록 한다 모바일특강

조합 논리 회로 설계 (9) 논리식의 최소화 : 대수적 간소화 (계속) 전가산기의 논리식 최소화 Sum = X’•Y’ •Cin + X’•Y•Cin’ + X•Y’•Cin’ + X•Y•Cin = X’•(Y’•Cin+Y•Cin’) + X•(Y’•Cin’+Y•Cin) = X’•(Y Cin) + X•(Y Cin)’ = X Y Cin Cout = X’•Y•Cin + X•Y’•Cin + X•Y•Cin’ + X•Y•Cin = (X’•Y•Cin + X•Y•Cin ) + (X•Y’•Cin + X•Y•Cin ) + (X•Y•Cin’ + X•Y•Cin) = Y•Cin + X•Cin + X•Y + + + + 모바일특강

조합 논리 회로 설계 (8) 논리식의 최소화 : Karnaugh Maps 3~5개의 논리변수를 갖는 논리식의 최소화에 편리한 방법을 제공 4변수 Karnaugh map 예: 모바일특강

조합 논리 회로 설계 (9) 논리식의 최소화 : Karnaugh Maps (계속) 4변수 Karnaugh map에서 각 칸은 4개의 변수에 의한 16개의 minterm들 중에 하나를 나타냄 ‘1’ – 해당 minterm에서 논리식의 값이 ‘1’임 ‘0’ – 해당 minterm에서 논리식의 값이 ‘0’임 ‘X’ – 해당 minterm이 무상관(Don’t-care) 조건임 (1) Don’t-care에 해당하는 입력 조합이 발생하기 않거나 (2) 입력 조합이 발생할 수 있으나 논리회로의 출력이 입력 상태와 무관한 경우 Karnaugh Map 작성 진리표  정준형 논리식(or minterm 전개식)  Karnaugh map 모바일특강

조합 논리 회로 설계 (10) 논리식의 최소화 : Karnaugh Maps (계속) 기본 원리 예: Karnaugh map에서 이웃하는 칸들에 해당하는 minterm사이에는 하나의 변수 값만 다른 규칙성을 갖는다 첫 번째와 마지막 행, 그리고 첫 번째 열과 마지막 열은 이웃한다 이웃한 칸의 두 개의 1은 xy+xy’=x 정리를 이용하여 한 개의 변수를 제거할 수 있다 예: 앞의 카르노우 도표에서 5번과 7번 칸이 이웃하면서 1의 값을 갖는다 Minterm A’BC’D와 A’BCD가 주어진 논리식을 1로 만드는 조건이므로 xy+xy’=x 정리에 의해 두 개의 minterm은 A’BD로 간소화 할 수 있다 모바일특강

조합 논리 회로 설계 (11) 논리식의 최소화 : Karnaugh Maps (계속) 단계 1 : 아직 커버되지 않은 minterm(1)을 선택한다 단계 2 : 선택된 minterm에 이웃하는 모든 1과 X를 찾는다 단계 3 : 단일 항이 그 minterm을 커버하고 이웃한 모든 1과 X를 커버한다면 그 항은 essential prime implicant(필수 주함축소)이므로 그 항을 선택한다 주함축소: 이웃하는 1에 대해 1, 2, 4, 8(2의 승수)의 개수의 그룹 필수 주함축소 : 다른 주함축소에 포함되지 않는 이웃하는 1들의 그룹 단계 4 : 모든 essential prime implicant가 선택될 때가지 1, 2, 3 단계를 반복한다 단계 5 : map에 남아 있는 1을 커버하는 prime implicant의 최소 집합을 찾는다 모바일특강

조합 논리 회로 설계 (12) 논리식의 최소화 : Karnaugh Maps (계속) 필수 주함축소 두 개의 함축소 중에서 하나를 선택 부 주함축소 최소화 논리식 : F=A’C’+A’B’D’+ACD+A’BD or F=A’C’+A’B’D’+ACD+BCD 모바일특강

조합 논리 회로 설계 (13) 논리식의 최소화 : Karnaugh Maps (계속) 최소의 정준합형 논리식을 구하는 방법과 동일하나 1 대신에 0을 묶어 주함축소를 구한다 구해진 주함축소를 이용하여 F’에 대한 정준합형의 논리식을 구한다 F’에 대해 드모르강의 정리를 적용하여 F의 정준곱형의 논리식을 구한다 예: 앞에서 제시된 4 변수 Karnaugh map에서 이웃하는 0을 묶어 F’의 정준합형 논리식을 구하면 F’ = BC’D’ + B’C’D + AB  F = (B’+C+D)(B+C+D’)(A’+B’) 모바일특강

조합 논리 회로 설계 (14) 조합 논리회로 구현 2 단계 회로망(Two-level gate network) 정준형 논리식이 2-단계 논리식으로 구성되기 때문에 직접적인 매핑을 통해 구현 A-O-I(And-Or-Invert) gate network Nand-nand gate network Nor-nor gate network Exclusive OR-Equivalence gate network 다단계 회로망(Multi-level gate network) Multiplexer Decoder Memory PLD(Programmable Logic Device) 모바일특강

조합 논리 회로 설계 (15) 조합 논리회로 구현 사례 : 모바일특강

조합 논리 회로 설계 (16) 기본 논리 게이트 논리 연산자(Logic Operator) / 논리 게이트(Logic Gate) 기본 논리 게이트 : 모바일특강

조합 논리 회로 설계 (17) NAND & NOR Gate를 이용한 논리회로 구현 많은 회로제조기술에서 NAND gate나 NOR gate를 구현하는 것이 AND 또는 OR gate를 구현하는 것보다 쉽다 또한, NAND 또는 NOR gate의 처리 속도가 더 빠르다 AND-OR 회로망의 NAND(또는 NOR) 회로망으로의 변환 단계 1 : 모든 AND 게이트의 출력에 반전 버블을 추가하여 NAND 게이트로 전환한다. 모든 OR 게이트의 입력에 반전 버블을 추가하여 NAND 게이트로 전환한다(NOR 회로망으로 전환하기 위해서는 모든 OR 게이트의 출력과 모든 AND 게이트의 입력에 반전 버블을 추가한다) 단계 2 : 반전 출력이 반전 입력에 연결될 때에는 두 번의 반전은 반전이 되지 않은 것과 같기 때문에 그대로 둔다 단계 3 : 반전되지 않은 게이트 출력을 반전된 입력이나 또는 반대의 경우 버블의 취소를 위하여 인버터를 넣어주어야 한다 단계 4 : 어떤 변수가 반전된 입력에 연결 할 때마다 변수에 보수를 취하는 것은 입력에서 반전을 취소하기 위해서이다 모바일특강

조합 논리 회로 설계 (18) AND-OR 회로망의 NAND 회로망으로의 변환 예: (a) AND-OR 회로망 (b) NAND 변화의 첫번째 단계 (b) 변환 완료된 NAND 회로망 모바일특강

반전된 입력은 반전 버블과 같이 쓰이면 반전되지 않는 것과 같다 조합 논리 회로 설계 (19) AND-OR 회로망의 NOR 회로망으로의 변환 예: Z = G(E+F)(A+B’+D)(C+D) = G(E+F)[(A+B’)C+D] (a) AND-OR 회로망 (b) 변환된 NOR 회로망 이중 반정은 반전되지 않은 것과 같다 반전된 입력은 반전 버블과 같이 쓰이면 반전되지 않는 것과 같다 모바일특강

조합 논리 회로 설계 (20) 조합 논리회로의 해저드(Hazard) 입력에서 출력으로 가는 경로가 다른 때에 전파 지연의 차이  입력이 조합회로를 변화시킬 때에 출력에 원치 않는 스위칭 과도현상 발생 정적 1-해저드(static 1-hazard) 회로의 출력이 일정한 값 1로 남아 있어야 하는데 순간적으로 0이 되는 경우 정적 0-해저드(static 1-hazard) 회로의 출력이 일정한 값 0로 남아 있어야 하는데 순간적으로 1이 되는 경우 동적 해저드(dynamic hazard) 출력이 3번 이상 변화하는 경우 모바일특강

조합 논리 회로 설계 (21) 조합 논리회로의 해저드(Hazard) 사례: (a) 1-해저드를 갖는 회로망 (b) 타이밍 챠트 모바일특강 (b) 타이밍 챠트

조합 논리 회로 설계 (22) 조합 논리회로의 해저드 제거 절차 단계 1 : Karnaugh map에서 ‘1’로 표시된 인접한 항들을 반드시 1개의 항으로 모두 커버되게 루프로 묶어서 곱의 합 표현식(Ft)으로 나타낸다. 이러한 Ft 에 바탕을 둔 2-레벨 AND-OR 회로망은 1-동적 해저드와 0-동적 해저가 존재하지 않는다 단계 2 : 간단한 인수화 드모르간의 법칙 등에 의해 원하는 형태로 회로를 수정하는데, 이 과정에서 해저드를 막기 위해 각 X와 X’는 독립변수로 취급하여야 한다. 모바일특강 해저드가 제거된 회로망