본문으로 건너뛰기

Boolean Logic

1.1 Background​

1) Boolean Value​

Boolean Value: 두 가지 상태만 가지는 값.

일반적으로 다음과 같이 표현한다.

0, 10,\ 1

Meaning: 디지털 컴퓨터는 정보를 두 개의 이진 상태로 표현하고 처리한다.

2) Boolean Function​

Boolean Function: 하나 이상의 이진 입력을 받아 이진 출력을 만드는 함수.

f:{0,1}n→{0,1}f:\{0,1\}^n \rightarrow \{0,1\}

Meaning: 논리 게이트가 수행해야 하는 동작을 수학적으로 표현한 것이다.

3) Truth Table​

Truth Table: 가능한 모든 입력 조합과 그에 대응하는 출력을 나타낸 표.

입력이 nn개이면 가능한 입력 조합은

2n2^n

개이다.

예를 들어 입력이 두 개인 경우 가능한 조합은 다음과 같다.

ab
00
01
10
11

Meaning: Boolean function의 동작을 가장 명확하게 정의하는 방법이다.

1.2 Basic Boolean Operations​

1) Not​

Not: 입력 값을 반전하는 연산.

inout
01
10
out=Not⁡(in)out=\operatorname{Not}(in)

Meaning: 0은 1로, 1은 0으로 바꾼다.

2) And​

And: 두 입력이 모두 1일 때만 1을 출력하는 연산.

about
000
010
100
111
out=aAnd⁡bout=a\operatorname{And}b

Meaning: 두 조건이 모두 참일 때만 참이다.

3) Or​

Or: 두 입력 중 하나 이상이 1이면 1을 출력하는 연산.

about
000
011
101
111
out=aOr⁡bout=a\operatorname{Or}b

Meaning: 두 조건 중 하나라도 참이면 참이다.

4) Xor​

Xor (Exclusive Or): 두 입력이 서로 다를 때 1을 출력하는 연산.

about
000
011
101
110

Meaning: 두 입력이 정확히 하나만 1일 때 참이다.

5) Nand​

Nand: And 결과를 반전한 연산.

about
001
011
101
110
Nand⁡(a,b)=Not⁡(And⁡(a,b))\operatorname{Nand}(a,b) = \operatorname{Not}(\operatorname{And}(a,b))

Meaning: 두 입력이 모두 1인 경우에만 0을 출력한다.

1.3 Universal Gate​

1) Nand Universality​

Universal Gate: 하나의 종류만으로 모든 Boolean function을 구성할 수 있는 게이트.

Nand는 universal gate이다.

Not, And, Or를 모두 Nand만으로 만들 수 있고, 모든 Boolean function은 Not, And, Or의 조합으로 표현할 수 있다.

따라서

Nand→all Boolean functions\text{Nand} \rightarrow \text{all Boolean functions}

이 가능하다.

Meaning: 하나의 기본 게이트만 있어도 임의의 디지털 논리 회로를 만들 수 있다.

2) Number of Boolean Functions​

입력 변수가 nn개이면 입력 조합은

2n2^n

개이다.

각 입력 조합마다 출력은 0 또는 1이 될 수 있으므로 가능한 Boolean function의 수는

22n2^{2^n}

이다.

예를 들어 두 입력 Boolean function의 수는

222=162^{2^2}=16

개이다.

Meaning: 입력 수가 증가하면 가능한 논리 함수의 수가 매우 빠르게 증가한다.

1.4 Canonical Representation​

Canonical Representation: truth table에서 출력이 1인 행들을 이용해 Boolean expression을 만드는 방법.

각 행에서 입력값을 고정하는 항을 만들고 이들을 Or로 연결한다.

예를 들어 어떤 행이

x=0,y=1,z=0x=0,\quad y=1,\quad z=0

이고 출력이 1이라면 해당 항은

Not⁡(x)And⁡yAnd⁡Not⁡(z)\operatorname{Not}(x) \operatorname{And} y \operatorname{And} \operatorname{Not}(z)

형태가 된다.

출력이 1인 모든 행의 항을 Or로 연결하면 전체 Boolean function을 표현할 수 있다.

Meaning: 모든 Boolean function은 Not, And, Or의 조합으로 나타낼 수 있다.

1.5 Gate Logic

1) Logic Gate​

Logic Gate: Boolean function을 물리적으로 구현한 장치.

입력이 주어지면 정의된 Boolean function에 따라 출력을 생성한다.

out=f(inputs)out=f(inputs)

Meaning: Boolean algebra를 실제 하드웨어 동작으로 구현한 것이다.

2) Primitive Gate​

Primitive Gate: 내부 구현을 더 이상 다루지 않고 기본 구성 요소로 사용하는 게이트.

이 책에서는

  • Nand
  • DFF

등을 특정 단계에서 primitive component로 사용한다.

Boolean Logic에서는 Nand를 기본 게이트로 사용한다.

Meaning: 하위 구현을 숨기고 바로 사용할 수 있는 가장 기본적인 building block이다.

3) Composite Gate​

Composite Gate: 여러 개의 기존 게이트를 연결하여 만든 새로운 게이트.

예를 들어 3-input And는 다음과 같이 만들 수 있다.

And⁡(a,b,c)=And⁡(And⁡(a,b),c)\operatorname{And}(a,b,c) = \operatorname{And}(\operatorname{And}(a,b),c)

Meaning: 단순한 게이트를 조합하여 더 복잡한 기능을 만든다.

4) Interface and Implementation​

모든 게이트는 두 가지 관점에서 볼 수 있다.

Interface: 입력, 출력, 기능을 정의한다.

Implementation: 내부에서 어떤 게이트를 어떻게 연결했는지를 나타낸다.

예를 들어 Xor의 interface는

a≠b⇒out=1a\neq b \Rightarrow out=1

이라고 정의할 수 있다.

그러나 내부 구현 방법은 여러 가지가 가능하다.

Meaning: 사용하는 쪽은 무엇을 하는지만 알면 되고, 내부 구현 방법은 알 필요가 없다.

이 원리는 이후 컴퓨터 시스템 전체에서 반복되는 핵심 추상화 원리이다.

1.6 Multiplexor and Demultiplexor

1) Multiplexor​

Multiplexor (Mux): selector 입력에 따라 여러 입력 중 하나를 선택하여 출력하는 게이트.

2-way Mux는

  • a
  • b
  • sel

을 입력으로 받는다.

sel=0⇒out=asel=0 \Rightarrow out=a sel=1⇒out=bsel=1 \Rightarrow out=b
selout
0a
1b

Meaning: 여러 데이터 중 하나를 선택하는 하드웨어 selector이다.

Mux는 CPU, ALU, register, memory 등의 데이터 경로를 구성하는 핵심 요소이다.

2) Demultiplexor​

Demultiplexor (DMux): 하나의 입력을 selector에 따라 여러 출력 중 하나로 전달하는 게이트.

sel=0⇒(a,b)=(in,0)sel=0 \Rightarrow (a,b)=(in,0) sel=1⇒(a,b)=(0,in)sel=1 \Rightarrow (a,b)=(0,in)

Meaning: 하나의 입력 신호를 선택된 경로로 분배한다.

3) Mux and DMux​

두 게이트의 기본 역할은 반대이다.

Mux:many inputs→one output\text{Mux} : \text{many inputs} \rightarrow \text{one output} DMux:one input→many outputs\text{DMux} : \text{one input} \rightarrow \text{many outputs}

Meaning: Mux는 선택하고, DMux는 분배한다.

1.7 Multi-Bit Gates

1) Bus​

Bus: 여러 개의 bit를 하나의 묶음으로 전달하는 신호선 집합.

예를 들어

in[16]

은 16-bit bus를 의미한다.

각 bit는 다음과 같이 접근한다.

in[0]
in[1]
...
in[15]

Meaning: 컴퓨터는 하나의 bit보다 여러 bit로 이루어진 word를 주로 처리한다.

2) Not16​

Not16: 16-bit 입력의 모든 bit에 Not을 적용한다.

out[i]=Not⁡(in[i])out[i]=\operatorname{Not}(in[i])

for

i=0,…,15i=0,\ldots,15

Meaning: 16개의 Not gate를 병렬로 배치한 것과 같다.

3) And16​

And16: 두 16-bit bus의 같은 위치에 있는 bit끼리 And 연산을 수행한다.

out[i]=And⁡(a[i],b[i])out[i] = \operatorname{And}(a[i],b[i])

Meaning: word 전체에 bit-wise And 연산을 수행한다.

4) Or16​

Or16: 두 16-bit bus의 같은 위치의 bit끼리 Or 연산을 수행한다.

out[i]=Or⁡(a[i],b[i])out[i] = \operatorname{Or}(a[i],b[i])

Meaning: word 전체에 bit-wise Or 연산을 수행한다.

5) Mux16​

Mux16: selector 값에 따라 두 16-bit bus 중 하나를 선택한다.

sel=0⇒out=asel=0 \Rightarrow out=a sel=1⇒out=bsel=1 \Rightarrow out=b

Meaning: 여러 bit를 하나의 word 단위로 선택한다.

1.8 Multi-Way Gates

1) Multi-Way Or​

Or8Way: 8개의 입력 중 하나라도 1이면 1을 출력한다.

out=Or⁡(in[0],in[1],…,in[7])out = \operatorname{Or} ( in[0], in[1], \ldots, in[7] )

Meaning: 여러 조건 중 하나라도 참인지 검사한다.

2) Multi-Way Multiplexor​

Multi-Way Mux: 여러 입력 bus 중 하나를 selector로 선택한다.

mm개의 입력을 선택하려면 필요한 selector bit 수는

k=log⁡2mk=\log_2 m

이다.

예를 들어 4개의 입력을 선택하려면

log⁡24=2\log_2 4=2

개의 selector bit가 필요하다.

Mux4Way16​

4개의 16-bit 입력 중 하나를 선택한다.

selout
00a
01b
10c
11d

Meaning: selector를 이용해 여러 데이터 경로 중 하나를 선택한다.

Mux8Way16​

8개의 16-bit 입력 중 하나를 선택한다.

필요한 selector bit 수는

log⁡28=3\log_2 8=3

이다.

Meaning: Mux를 계층적으로 조합하면 더 많은 입력 중 하나를 선택할 수 있다.

3) Multi-Way Demultiplexor​

Multi-Way DMux: 하나의 입력을 여러 출력 중 하나로 전달한다.

4-way DMux에서는

sel=00,01,10,11sel=00,01,10,11

중 하나를 이용하여 a, b, c, d 중 하나의 출력만 선택한다.

Meaning: 주소나 제어 신호를 이용해 특정 회로나 장치를 선택하는 데 사용할 수 있다.

1.9 Hardware Description Language

1) HDL​

Hardware Description Language (HDL): 하드웨어의 구조와 연결 관계를 텍스트로 기술하는 언어.

이 책에서는 실제 트랜지스터를 직접 연결하지 않고 HDL을 이용하여 논리 회로를 구성한다.

예를 들어 Xor gate는 내부에서

  • Not
  • And
  • Or

gate를 연결하여 표현할 수 있다.

Meaning: 회로를 실제 제작하기 전에 소프트웨어로 설계하고 검증할 수 있다.

2) Chip Interface​

HDL에서 chip의 interface는 주로 다음 정보를 정의한다.

  • Chip name
  • Input pins
  • Output pins

예:

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    ...
}

Meaning: 외부에서 이 chip을 어떻게 사용할 수 있는지를 정의한다.

3) Parts​

PARTS: chip 내부에서 사용하는 하위 chip들과 연결 관계를 기술하는 영역.

예:

Not(in=a, out=nota);

이 코드는 입력 a를 Not gate에 전달하고 결과를 내부 신호 nota에 저장한다.

Meaning: 복잡한 chip을 이미 만들어진 작은 chip들의 연결로 구현한다.

4) Internal Pin​

Internal Pin: chip 내부의 다른 gate들을 연결하는 중간 신호.

예:

Not(in=a, out=nota);
And(a=nota, b=b, out=w);

여기서 nota와 w가 내부 연결에 사용된다.

Meaning: 한 gate의 출력을 다른 gate의 입력으로 연결하는 wire 역할을 한다.

1.10 Hardware Simulation

1) Hardware Simulator​

Hardware Simulator: HDL로 작성된 가상 하드웨어의 동작을 실행하고 검증하는 프로그램.

기본 과정은 다음과 같다.

HDL→Simulation→Output\text{HDL} \rightarrow \text{Simulation} \rightarrow \text{Output}

Meaning: 실제 chip을 제작하지 않고 논리 회로의 동작을 확인할 수 있다.

2) Test Script​

Test Script: chip에 입력값을 넣고 출력을 기록하도록 simulator에 지시하는 테스트 프로그램.

예를 들어 Xor는 가능한 네 입력 조합을 모두 검사할 수 있다.

(0,0)(0,0) (0,1)(0,1) (1,0)(1,0) (1,1)(1,1)

Meaning: 같은 테스트를 반복 가능하고 체계적으로 수행할 수 있다.

3) Compare File​

Compare File: 올바른 예상 출력값을 저장한 파일.

Simulator가 실제 출력과 compare file을 비교하여 구현의 정확성을 검사한다.

actual output=expected output\text{actual output} = \text{expected output}

이면 테스트가 성공한다.

Meaning: chip의 interface specification이 실제 구현에서 지켜지는지 검증한다.

1.11 Logic Design Principle

Logic Design: 주어진 gate specification을 이미 존재하는 더 단순한 gate들의 조합으로 구현하는 과정.

핵심 과정은 다음과 같다.

Specification→Boolean Logic→Gate Composition→Implementation→Testing\text{Specification} \rightarrow \text{Boolean Logic} \rightarrow \text{Gate Composition} \rightarrow \text{Implementation} \rightarrow \text{Testing}

좋은 구현은 같은 기능을 더 단순한 구조로 만든다.

Meaning: 하드웨어 설계의 핵심은 복잡한 기능을 작은 검증된 구성 요소의 조합으로 만드는 것이다.

Essential Study Checklist

반드시 이해하고 기억해야 하는 내용:

  1. Boolean value는 0과 1의 두 상태를 가진다.

  2. Boolean function은 binary input을 받아 binary output을 만든다.

  3. Truth table은 모든 입력 조합과 출력을 정의한다.

  4. 기본 Boolean 연산은 Not, And, Or, Xor, Nand이다.

  5. Nand 하나만으로 모든 Boolean function을 구현할 수 있다.

  6. 입력 변수가 nn개인 Boolean function의 입력 조합은 2n2^n개이다.

  7. 가능한 Boolean function의 수는

22n2^{2^n}

이다.

  1. Logic gate는 Boolean function의 하드웨어 구현이다.

  2. Composite gate는 작은 gate들을 연결하여 만든다.

  3. Interface는 무엇을 하는지, implementation은 어떻게 하는지를 나타낸다.

  4. Mux는 여러 입력 중 하나를 선택한다.

many inputs→one output\text{many inputs} \rightarrow \text{one output}
  1. DMux는 하나의 입력을 여러 출력 중 하나로 분배한다.
one input→many outputs\text{one input} \rightarrow \text{many outputs}

  1. Bus는 여러 bit를 하나의 단위로 전달한다.

  2. Multi-bit gate는 같은 Boolean 연산을 여러 bit에 병렬 적용한다.

  3. mm개의 입력 중 하나를 선택하려면

log⁡2m\log_2 m

개의 selector bit가 필요하다.

  1. HDL은 gate의 interface와 내부 연결 구조를 기술한다.

  2. Hardware simulator를 이용하면 실제 chip 제작 전에 HDL 회로를 검증할 수 있다.

  3. 디지털 하드웨어 설계의 기본 원리는

simple gates→composite gates→complex hardware\boxed{ \text{simple gates} \rightarrow \text{composite gates} \rightarrow \text{complex hardware} }

이다.