기본 연산
수학적 연산의 공리
- 닫혀있음(연산을 해도 같은 집합에 들어 있음)
- 결합 법칙 : 연산을 하는 순서에 상관 없이 같은 결과가 나옴. (x y) z == x (y z)
- 교환 법칙 : 연산되는 것의 순서에 상관 없이 같은 결과가 나옴.
- 항등원 : 어떤 연산을 했을 때 연산을 하지 않은 것과 같다면 연산자의 항등원이라고 함. 예를 들어 e x = x e = x면 e 는 * 의 항등원임
- 역원 : 어떤 연산을 반대로 해서 항등원이 나오는 것을 역원이라고 함. 예를 들어 x * y = e면 y는 x의 항등원임.
- 분배 법칙 : 괄호로 감싸져있을 때 분배가 가능함. x (y z) = (x y)(x z)
불 대수(boolean algebra)
영국의 수학자 George Boole이 1854년에 제안했으며, 0과 1 두 숫자에 대해서 다루는 대수학이다. 디지털 시스템의 논리 연산에 적합했기 때문에 많이 연구되었다.
Huntington Postulates(헌팅턴의 공리)
-
(a) 논리합(+)은 2진수 체계에 닫혀있다. (b) 논리곱(⋅)은 2진수 체계에 닫혀있다. -
(a) 논리합의 항등원은 0이다. 0 + 𝑥 = 𝑥 + 0 = 𝑥 (b) 논리곱의 항등원은 1이다. 1⋅𝑥 = 𝑥⋅1 = 𝑥 -
(a) 논리합은 곱셈 법칙이 성립한다. 𝑥 + 𝑦 = 𝑦 + 𝑥 (b) 논리곱은 곱셈 법칙이 성립한다. 𝑥⋅𝑦 = 𝑦⋅𝑥 -
(a) 논리곱은 논리합에 대해서 분배법칙이 성립한다. 𝑥⋅(𝑦 + 𝑧) = (𝑥⋅𝑦) + (𝑥⋅𝑧) (b) 논리합은 논리곱에 대해서 분배법칙이 성립한다. 𝑥 + (𝑦⋅𝑧) = (𝑥 + 𝑦)⋅(𝑥 + 𝑧) -
모든 𝑥 ∈ 𝐵에 대해서 𝑥’ ∈ 𝐵가 존재한다. (a) 𝑥 + 𝑥’ = 1 / (b) 𝑥⋅𝑥’ = 0 -
𝐵에는 적어도 동일하지 않은 𝑥,𝑦 ∈ 𝐵가 존재한다. 𝑥 ≠ 𝑦
불 대수와 기본 대수의 차이
- 불 대수의 결합 법칙은 기본 대수의 결합 법칙과 같은 원리이다.
- 논리합은 논리곱에 대해서 분배법칙이 성립하며, 기본 대수에서는 성립하지 않는 규칙이다.
- 불 대수는 곱셈에 대한 역원이 존재하지 않는다.
- 반대(Complement)는 기본 대수에선 존재하지 않는 개념이다.
- 기본 대수는 실수에 대해서 적용되는 반면, 불 대수는 {0,1}에 대해서 적용된다.
불 대수의 연산자 정리
- AND, OR, NOT연산자와 동일하다.
- 2개의 매개 변수를 가지는 연산자 : AND, OR
- 1개의 매개 변수를 가지는 연산자 : NOT
- Huntington Postulates는 {0,1}에서 유효하다.
- Postulate 1 : 닫혀있음
- Postulate 2 : 위 그림 참조
- Postulate 3 : 교환 법칙 성립함
- Postulate 4 : AND에 대한 OR가 성립하고, OR에 대한 AND가 성립함.
- Postulate 5 : 위 그림 참조
- Postulate 6 : 두 가지 값 {0,1}밖에 없기 때문에 성립함
불 대수의 정리와 성질
불 대수는 성질이 있는데, 참이 되는 식에서 AND와 OR를 바꾸고, 0과 1을 바꾸면 정확히 식이 성립한다. 이것은 불 대수에서만 성립하는 성질로, 쌍대성(Duality)이라고 한다.
아래는 계산할 때 유용한 정리들이다.
논리 연산을 할 때 증명을 해야 할 때, 가장 쉬운 방법은 진리표를 이용하는 거다. x + x'
𝑥 + 𝑥’𝑦 = 𝑥 + 𝑦
| x | y | x' | x'y | x+x'y | x | y | x+y | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
이진 식의 간략화
이진 식이 복잡하게 나열되어 있으면, 간략화를 통해 간단히 나타낼 수 있다. 간략화는 같은 부분을 찾아내어 묶거나 없앨수 있으면 없애는 과정으로, 복잡성을 줄이고 이해하기 쉽게 해준다.
𝑥'𝑦'𝑧 + 𝑥'𝑦𝑧 +𝑥𝑦'
= 𝑥'𝑧(𝑦'+𝑦) + 𝑥𝑦'
= 𝑥'𝑧 + 𝑥𝑦'
이러한 간략화 과정이 필요한 이유는 논리 회로를 만들 때 최소한의 회로들이 들어가야 하는데(성능이나 자원 등등의 이유), 같은 결과를 내는 논리 회로는 간단할수록 좋기 때문이다.
간략화를 통해서 회로가 하나 줄은 모습이다. 이처럼 나오는 값이 똑같은 회로들을 등가회로라고 한다.
함수의 반대값
함수 자체에 대해서 NOT연산을 할 수 있을까? 물론 가능하다. 함수의 반대값에 대한 계산은 드모르간 법칙을 사용하거나, 쌍대성을 이용하면 된다.
드모르간 법칙을 이용하는 법
𝑓(𝑥,𝑦,𝑧) = 𝑥(𝑦’𝑧’ + 𝑦𝑧)라는 식이 있을 때
𝑓’(𝑥,𝑦,𝑧) = (𝑥(𝑦’𝑧’ + 𝑦𝑧))’
= 𝑥’ + (𝑦’𝑧’ + 𝑦𝑧)’
= 𝑥’ + (𝑦’𝑧’)’ (𝑦𝑧)’
= 𝒙’ + (𝒚 + 𝒛)(𝒚’ + 𝒛’)
쌍대성을 이용하는 법
𝑓(𝑥,𝑦,𝑧) = 𝑥(𝑦’𝑧’ + 𝑦𝑧)라는 식이 있을 때 쌍대성을 이용하면
𝑥 + (𝑦’ + 𝑧’)(𝑦 + 𝑧)라는 식이 나옴.
여기서 각각의 요소에 NOT연산을 하면
𝑓’(𝑥,𝑦,𝑧) = 𝑥’ + (𝑦 + 𝑧)(𝑦’ + 𝑧’)
Minterms(최소항)
minterm은 그 회로가 가지고 있는 모든 변수가 정확히 한 개씩 나오도록 AND Term을 구성한 거다. 변수가 n개가 있으면, minterm은 2^n개가 나온다. 예를 들어, 𝑓(𝑥,𝑦,𝑧)는 2^3 = 8개의 minterm을 가진다.
𝑥’𝑦’𝑧’ 𝑥’𝑦’𝑧 𝑥’𝑦𝑧’ 𝑥’𝑦𝑧
𝑥𝑦’𝑧’ 𝑥𝑦’𝑧 𝑥𝑦𝑧’ 𝑥𝑦𝑧
Sum of Minterms Form
어떤 함수는 Minterm들의 Sum(OR 연산)으로 표현할 수 있다. 아래 예시를 보자.
𝑓(𝑥,𝑦,𝑧)는 = 𝑥’𝑦’𝑧’,𝑥’𝑦’𝑧, 𝑥’𝑦𝑧’, 𝑥’𝑦𝑧, 𝑥𝑦𝑧’중 하나만 1이어도 1이 될 수 있다. 그러므로 𝑓(𝑥,𝑦,𝑧) = 𝑥’𝑦’𝑧’ + 𝑥’𝑦’𝑧 + 𝑥’𝑦𝑧’ + 𝑥’𝑦𝑧 + 𝑥𝑦𝑧’로 표현할 수 있다. 다시 말하면 𝑚0 + 𝑚1 + 𝑚2 + 𝑚3 + 𝑚6 = Σ(0,1,2,3,6)로 표현할 수 있다.
반대로 𝑓’(𝑥,𝑦,𝑧)는 남은 minterm들의 sum으로 표현하면 된다. 𝑚4 + 𝑚5 + 𝑚7 = Σ(4,5,7)
products of sum
products of sum은 AND들의 OR연산으로, 회로가 쉽게 구현된다는 장점이 있다. 모든 회로들은 SOP 혹은 POS로 구현 가능한데, POS가 구현이 쉬우므로 자주 사양된다.
Maxterms(최소항)
maxterm은 그 회로가 가지고 있는 모든 변수가 정확히 한 개씩 나오도록 OR Term을 구성한 거다. 변수가 n개가 있으면, maxterm은 2^n개가 나온다. 예를 들어, 𝑓(𝑥,𝑦,𝑧)는 2^3 = 8개의 maxterm을 가진다.
𝑥’+𝑦’+𝑧’ 𝑥’+𝑦’+𝑧 𝑥’+𝑦+𝑧’ 𝑥’+𝑦+𝑧
𝑥+𝑦’+𝑧’ 𝑥+𝑦’+𝑧 𝑥+𝑦+𝑧’ 𝑥+𝑦+𝑧
Product of Maxterms Form
어떤 함수는 Maxterm들의 Product(AND 연산)으로 표현할 수 있다. 아래 예시를 보자.
𝑓(𝑥,𝑦,𝑧)는 = 𝑥’ + 𝑦 + 𝑧, 𝑥’ + 𝑦 + 𝑧’, 𝑥’ + 𝑦’ + 𝑧’ 모두 0이 되어야만 0이 될 수 있다. 그러므로 𝑓(𝑥,𝑦,𝑧) = (𝑥’ + 𝑦 + 𝑧)(𝑥’ + 𝑦 + 𝑧’)(𝑥’ + 𝑦’ + 𝑧’)로 표현할 수 있다. 다시 말하면 𝑀4 𝑀5 𝑀7 = ∏(4,5,7)
로 표현할 수 있다.
반대로 𝑓’(𝑥,𝑦,𝑧)는 남은 maxterm들의 sum으로 표현하면 된다. 𝑀0 𝑀1 𝑀2 𝑀3 𝑀6 = ∏(0,1,2,3,6)
Minterm과 Maxterm의 연관성
아래 사진과 같이, Minterm과 Maxterm은 complement의 관계에 있다.
이를 통해, 𝒇 = 𝚺(𝟎,𝟏,𝟐,𝟑,𝟔) = ∏(𝟒,𝟓,𝟕)가 성립하는 걸 알 수 있고, 회로를 SOP나 POS로 나타낸 것을 Standard Form이라고 부른다.
Standard Form
Standard Form은 회로를 나타내는 데 도움을 준다.
-
SOP
- 위 그림에서 입력 신호 다음에 있는 회로는 level 1, 그 뒤에 있는 회로를 level 2(outermost level)이라고 부른다. level 1에는 AND(Product)연산만 존재하고, level 2에는 OR(sum)연산만 존재한다.
-
POS
- POS는 반대로, level 1에는 OR(sum)연산만 존재하고, level 2에는 AND(Product)연산만 존재한다.
왼쪽은 3단계를 거쳐야 하고, AND와 OR연산이 혼재해있어 표현하거나 이해하기 쉽지 않다. 그러나 분배법칙을 이용하여 Standard Form을 만들면, 1단계에서는 AND연산, 2단계에서는 OR연산만 하면 되므로 회로 설계가 편해진다. 이는 회로의 성능과도 연결되어 있는데, 존재하는 level에 따라서 성능이 좌지우지되는 경우가 많기 때문에 level이 적을수록 성능이 좋아지는 경우가 많다. Standard Form은 level을 많이 줄일 수 있으므로 성능이 좋아진다.
여러가지 논리 연산
위는 논리 연산들을 모두 모아둔 것이다. 우리가 배운 AND연산자는 F1과 동일하고, OR연산자는 F7과 동일하다. F12는 NOT x와 동일하다. 이처럼 연산들 중에는 계산의 편리나 유용성 등으로 인해 자주 쓰이는 연산들이 있다.
많이 쓰이는 연산들에 대해 애기하기 전에여기를 참고하는 것도 좋을 것 같다.
게이트들의 표현 방식
Exclusive-OR
일반적으로는 2-input gate를 사용한다. 그 이유는 3-input gate가 성능 자체는 뛰어나지만, 회로적인 복잡함이 단점이 될 수 있기 때문에 많은 성능을 기대하지 않는 이상 2-input gate를 사용하는 경우가 많다.
또한 exclusive-OR는 연관된 변수들 중 1의 개수가 짝수(even)일때 0이 되고, 홀수(odd)일때 1이 되는 특성을 가지고 있다.
양수 / 음수 논리
컴퓨터에서 0과 1은 논리 연산에서 참과 거짓을 뜻한다. 여기서 0을 true로 할지, false로 할지를 시스템에 따라 정할 수 있다.
- Positive logic : 실제 시스템에서 나오는 출력이 High value일 때를 1로 놓고, Low value일 때를 0으로 놓는 방식이다. 우리가 흔히 생각하는 0 == false / 1 == true라고 생각할 수 있다.
- Negative logic : 위와는 반대로 시스템에서 나오는 출력이 Low value일때를 1로 놓는 방식이다. 자주 쓰이지는 앟는다.
그림과 같이 High value가 되려면, 입력 둘 다 High value여야 한다. 다시 말해 AND연산이 수행된다. 그러므로 Positive logic을 사용하면 AND게이트를 사용하는 것과 똑같은 방식을 취한다. 이와는 반대로 Negative logic을 사용하면 OR게이트를 사용하는 것과 똑같은 방식을 취한다. 기본적으로 Positive logic게이트가 많이 사용되므로 알아두기만 하자.
IC(Integrated Circuits)에 대한 용어 정리
- Levels
- SSI : Small Scail Integrated Circuits
- MSI : 10~1,000개
- LSI : 천개 이상
- VLSI : 수십만개 이상
- Digital Logic Families(제조 방법)
- TTL
- ECL
- MOS
- CMOS
- References
- Fan-out : 어떤 칩의 출력단에 몇 개의 회로를 붙힐 수 있는가?
- Fan-in : 어떤 칩의 입력단에 몇 개의 회로를 붙힐 수 있는가?
- Power dissipation : 전력 소비량이 얼마나 되는가?
- Propagation delay : 입력이 들어와서 출력까지 걸리는 시간이 얼마나 되는가?
- Noise margin : 입출력이나 회로 내부에서 얼마나 많은 전류가 들어와야 바뀌는가?(예상치 못한 Noise가 들어왔을때, 예를 들면 스파크같은, 얼마나 많은 전류가 들어오면 값이 바뀌는가?)
