[전산기조직] 논리 디자인의 기초 - Combinational Logic 편

 이 글은 Computer Organization And Design: The Hardware/Software Interface, David A. Patterson and John L Hennessy 6th edition 중, Appdendix C: The Basics of Logic Design의 C.2~C.3를 읽고 재구성한 글입니다. 이 글 속의 이미지들도 이 책의 이미지를 사용했습니다.

 

이 글은 LateX 수식이 포함되어 있습니다. $ \sum $ <- 이 시그마 기호가 제대로 보이지 않으면 새로고침 해주세요.

 

---

 컴퓨터 세상의 신호는 디지털(Digital)로 통한다. 디지털은 모든 신호를 두 가지로 표현한다. True, 1, asserted 등으로 표현하는 신호와 false, 0, deasserted 등으로 표현하는 신호이다. 이 신호는 회로 위에서 고전압(High voltage)과 저전압(Low voltage)로 구현된다.

 

 우리는 지금부터 다양한 논리 블럭(Logic Block)들을 알아 볼 것이다. 논리 블럭은 크게 두 종류로 나눌 수 있다. 메모리(Memory)가 있는 것과 없는 것이다. 논리 블럭에서 나오는 출력(Output)이 입력(Input)에만 의존한다면, 그 블럭은 메모리가 없는 블럭이라고 할 수 있다. 우리는 이것을 Combinational Logic 이라고 한다. 반면, 논리 블럭의 상태(State)에 따라 같은 입력에도 다른 출력을 반환할 수도 있다. 이 상태가 저장되는 곳을 우리는 메모리라고 부르고, 입력과 상태 모두에 출력이 의존하는 회로를 sequential logic 이라고 부른다. 이번 글에서는 Combinational Block들의 예시를 소개한다.

 

Boolean Algebra

 다양한 logic block들을 알기 이전에 Boolean Algebra에 대한 기호 약속이 필요하다. 먼저 3가지 가장 기본적인 연산을 정의한다. 우리가 다룰 모든 logic block들은 이 연산들만을 가지고 모두 표현할 수 있다.

 

AND: $ out = A \cdot B = AB $
OR: $ out = A + B $
NOT: $ out = \overline{A} $

 

 위 3가지 연산은 이렇게 gate 기호로 표현된다.

AND, OR, NOT gate

 

그리고 아래의 기본적인 law들을 따른다. 다른 law들은 익숙하나 distributative law에서 or 연산을 분배하는 규칙이 낯설 수 있다.

 

Identity law: $A + 0 = A$ and $A \cdot 1 = A$.
Zero and One laws: $A + 1 = 1$ and $A \cdot 0 = 0$.
Inverse laws: $A + \overline{A} = 1$ and $A \cdot \overline{A} = 1$.
Commutative laws: $A + B = B + A$ and $A \cdot B = B \cdot A$.
Associative laws: $A + (B + C) = (A + B) + C$ and $A \cdot (B \cdot C) = (A \cdot B) \cdot C$.
Distributive laws: $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$ and $A + (B \cdot C) = (A + B) \cdot (A + C)$.
DeMorgans' laws: $\overline{A + B} = \overline{A} \cdot \overline{B}$ and $ \overline{AB} = \overline{A} + \overline{B}$.

 

 두 가지 신기한 연산을 추가한다. NAND 와 NOR 이다. 신기하게도, NAND 와 NOR 둘 중 하나의 연산만 가지고도 위의 기본적인 AND, OR, NOT 3가지 연산을 모두 구현할 수 있다. 즉, NAND나 NOR gate 둘 중 하나만 있으면 우리가 앞으로 다룰 모든 logic block들을 모두 구현할 수 있다. 그래서 우리는 NAND와 NOR 연산을 universal 하다고 표현한다.

 

$ \mathbin{\text{nand}} $: $ A \mathbin{\text{nand}} B = \overline{A \mathbin{\text{and}} B} $
$ \mathbin{\text{nor}} $: $ A \mathbin{\text{nor}} B = \overline{A \mathbin{\text{or}} B} $

$ \mathop{\text{not}} A = A \mathbin{\text{nand}} A = A \mathbin{\text{nor}} A $
$ A \mathbin{\text{and}} B = \overline{A \mathbin{\text{nand}} B} = \overline{A} \mathbin{\text{nor}} \overline{B} $
$ A \mathbin{\text{or}} B = \overline{A} \mathbin{\text{nand}} \overline{B} = \overline{A \mathbin{\text{nor}} B} $

 

기본적인 연산 정의도 끝났으니, 이제 combination logic block들을 하나씩 알아본다.

Decoder

디코더는 n개의 입력과 2ⁿ개의 출력을 가지고 있다. 디코더는 이 입력 값에 따라 2ⁿ개의 출력 중 하나만을 true 로 반환한다.

예를 들어, 3개의 입력과 8개의 출력을 갖는 아래의 디코더는 입력을 마치 3bit의 2진수처럼 해독하여, 원하는 Out Port 에만 신호를 보낼 수 있다.

디코더(Decoder)

 

Multiplexor

멀티플렉서(Mux)는 여러개의 입력 중에서 하나의 입력 값만을 출력으로 반환한다. 아래 그림에서 A와 B 입력에는 각각 0과 1이 input으로 들어오고 있다. 그리고 S(Selector)의 값이 0인지 1인지에 따라서, 출력인 C의 값은 A와 같은 0이 될수도, B와 같은 1이 될수도 있다. 아래의 회로를 논리식으로 표현하면 아래와 같다. 또, 아래의 예시에서는 셀렉터가 S 하나였기에 두 개의 입력만 다룰 수 있었지만, 셀렉터가 n개로 확장된다면, 그만큼 입력 또한, 2ⁿ개로 늘려서 확장할 수 있다. 디코더를 이용하여 n개의 셀렉터 값들을 2ⁿ개의 출력으로 반환한후, 멀티플렉서의 입력과 1대1로 AND 연산 하면 된다.

 

$$ C = A \cdot S + B \cdot \overline{S} $$

멀티플렉서(Multiplexor, Mux)

 

Progammable Logic Array(PLA)

앞서, 거의 모든 logic function은 AND, OR, NOT 3가지 기본 연산으로 구현가능하다고 했다. 실은, 더 일반적으로 모든 logic function들은 합의 곱(Product of Sums)이나 곱의 합(Sum of Products) 같은 정규식(Canonical Form)으로 표현가능하다. 예를 들어, A, B, C 3개의 입력 중 정확히 2개의 입력이 true일 때 true를 반환하는 출력 E를 생각해보자. 아래 식처럼 표현 할 수 있다. 아래의 등식이 성립하는 것은 앞서 언급했던 boolean algebra의 law들을 이용하여 확인가능하다.

 

$$ E = ((A \cdot B) + (A \cdot C) + (B \cdot A)) \cdot (\overline{A \cdot B \cdot C}) \\ = (A \cdot B \cdot \overline{C}) + (A \cdot C \cdot \overline{B}) + (B \cdot C \cdot \overline{A}) \\ = \overline{(\overline{A} + \overline{B} + C)\cdot(\overline{A} + B + \overline{C})\cdot(A + \overline{B} + \overline{C})} $$

 

두번째 줄의 식이 곱의 합(Sum of Products), 세번째 줄의 식이 합의 곱(Product of Sums)이다. 보통의 우리가 다루는 다항식과 가까운 모양인 곱의 합이 major한 정규식으로 널리 쓰인다. 이런 정규식으로 표현했을 때 큰 이점이 있는데, 아래 그림의 회로처럼 일반적으로 모든 회로를 그려낼 수 있다는 것이다. 이 회로를 우리는 PLA(Programmable Logic Array)라고 부른다.

일반적인 PLA 모식도와 실제 구현예시, 오른쪽 그림에서 E가 앞서 예시로 든 E와 같다.