Combination logic

1. Basic Logic

n개의 input이 있을 때, $2^{2^n}$개의 함수가 만들어질 수 있다.

 

이산수학과 겹치는 axioms 들은 따로 정리하지 않고 패스...

Boolean function은 Boolean algebra로 모두 표현 가능하다.

 

1-1. transistor

전기 신호를 0과 1로 바꾸어주는 것 : 트랜지스터

 

이러한 트랜지스터는 두 가지 종류가 있다.

1) nMOS transistor : 1일 때 닫힌다. ground와 연결되어 0을 전달하는 역할

2) pMOS transistor : 0일 때 닫힌다. Voltage와 연결되어 1을 전달하는 역할

 

Pull-up network : 1의 값을 전달하는 pMOS와 Voltage로 이루어진 net

Pull-down network : 0의 값을 전달하는 nMOS와 Ground로 이루어진 net

 

pMOS는 전선 연결부에 동그라미로 표현한다.

이러한 특성 때문에 NAND와 NOR을 구성하는게 더 적은 트렌지스터(4개)가 든다!

 

1-2. Cost of different logic functions

inverter : 2개

nor, nand : 4개

or, and : 6개

equal, xor : 16개 -> 제일 많은 트렌지스터가 필요

 

2. Minimal set of functions

2-1. Boolean Expression

axioms들과 duality를 이용해서 boolean algebra의 크기를 줄일 수 있다.

2-2. Boolean Expression to logic gates

하나의 function을 실제 하드웨어로 구현하는 것은 여러가지로 나타낼 수 있다.

 

1. two-level implementation 

=> 거쳐야하는 단계가 적기 때문에 제일 빠르다.

=> not deep 하지만 wide한 circuit을 만들어야 하기 때문에, number of inputs이 높은 게이트를 써야 한다.

=> 기술적인 한계(# of inputs의 제한, fan-ins)으로 2-level로 구현하지 못할 수도 있음.

 

2. multi-level implementation

=> 최대로 거치는 level의 수를 level로 기록한다.

=> input단에 걸리는 inverter는 레벨로 간주하지 않는다.

 

2-3. Best Realization

(1) fewer literals

(2) fewer inputs

(3) fan-ins

3. Implementing Boolean Function

Boolean Function을 최소로 나타내기 위한 알고리즘은 아직 밝혀지지 않음.

 

하지만 적당히 괜찮은(Heuristic algorithm)은 존재한다.

 

3-1. Canonical Forms

: Boolean expression의 표준화된 형태

 

(1) Sum-of-products canonical forms(minterm expansion)

=> AND 연산을 활용하여 1(True)이 되는 조합들을 만들고 그를 모두 OR 연산자들로 합쳐준다.

 

(2) Product-of-sums canonical form(maxterm expansion)

=> OR 연산을 활용하여 0(False)이 되는 조합들을 만들고 그를 모두 AND 연산자들로 곱해준다.

 

(1)과 (2)는 DeMorgan equivalnce를 통해 구해줄 수 있다.

 

=> 하지만 canonical form이 최소의 개수를 가진 Boolean function(minimum realization)을 뜻하지는 않는다!

 

각각의 방법을 통해 나온 Boolean Function들은 논리적으로 동일하다.

 

3-2. Incompletely specified functions

=> "Don't care" set이 존재하는 functions => 답에 영향을 주지 않는 set이다.

 

Don't care set을 이용해서 더 편하게 canonical form을 만들 수 있다.

 

Simplication of two-level combinational logic

=> Hand methods still relevant 

 

3-3. Simplication of two-level combinational logic 

A Minimal Sum of Products

- 항의 개수가 가장 적은 것

- 항의 개수가 가장 적다면 각 항이 가장 적은 원소들을 포함하고 있는 것!

 

The uniting theorem => simplication의 Key!

ex) A(B + B') = A

 

1) Boolean cubes

- 3개의 input 이하의 시스템의 simplication에서 유용.

- n-dimension cube를 그려서 항을 줄여나간다.

- m-subcube가 모두 onset 혹은 don't care라면 (n-m) literals를 가진 항이 나온다.

 

2) Karnaugh maps(K-maps)

- 큐브를 2차원 형태로 편 것

- Gray-code(옆의 bits가 바로 옆의 bits에서 하나의 항만 바뀐 bits)를 이용해서 인접한 항을 빠르게 찾는다.

- minterm numbering 잘 체크할 것!(0~15)

- 6-variable K-Maps 까지 시각화 가능하다.