Skip to content

[ From Nand to Tetris ] 불 함수와 게이트 로직

참고

Coursera 강의 From Nand to Tetris밑바닥부터 만드는 컴퓨팅 시스템을 참고로 공부한 내용입니다.

불 게이트 (Boolean gate)

불 게이트(Boolean gate)불 함수(Boolean function)를 물리적으로 구현한 것이므로, 먼저 불 대수(Boolean algebra)부터 간략하게 살펴봐야 한다.

불 대수 (Boolean algebra)

불 함수는 2진수를 입력받아 2진수를 출력하는 함수다. 컴퓨터는 2진수를 표현하고 처리하는 하드웨어이므로, 불 함수는 하드웨어 아키텍처의 명세, 구성, 최적화에 중심적인 역할을 한다.
따라서 불 함수를 정의하고 분석하는 것이 컴퓨터 아키텍처를 구축하는 첫 단계가 된다.

진리표 표현 (Truth table)

어떤 불 함수를 정의하는 가장 쉬운 방법은 함수의 입력값들과 결괏값을 나란히 쓰는 방법이다. 이 방식을 함수의 진리표(Truth table)표현이라 한다.
예를 들어 아래 표와 같다.

x y z f(x, y, z)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0

불 표현식

불 함수는 진리표 말고도 입력값에 대한 불 연산으로도 표현 가능하다. 위 예시를 연산으로 표현하면 \(f(x, y, z) = (x+y)\cdot\bar{z}\) 와 같다.

정준 표현

또한 이러한 모든 불 함수는 정준 표현(Canonical representation)이라 불리는 불 표현식으로 표현 가능하다. 예를 들어 함수 값이 1인 세 번째 행의 변수를 묶으면 \(\bar{x}y\bar{z}\) 라는 항을 만들 수 있다. 이러한 1인 행들을 OR 연산으로 묶을 경우 결국 \(f(x, y, z) = \bar{x}y\bar{z}+x\bar{y}\bar{z}+xy\bar{z}\) 와 같다.

이처럼 모든 불 함수에 대해서 AND, OR, NOT 연산만 활용하여 표현 가능한 것이다.

정보

기본적인 연산의 종류는 NAND, AND, OR, NOT, NOR 등이 있는데 가장 주목해야 할 것은 바로 NAND 연산이다.

NANA 연산의 경우 다른 모든 연산들의 기초가 되고, 또한 다른 모든 연산들을 전부 NAND 연산만을 사용하여 표현 가능하기 때문에 NADN 연산을 범용 게이트(Universal gate)라 부른다.

이러한 정준 표현이 가능한 이유는 불 함수에 아래와 같은 법칙(Law)이 적용되기 때문이다.

  • 교환 법칙(Commutative Laws)
    • \((x AND y) = (y and x)\)
  • 결합 법칙(Associative Laws)
    • \((x AND (y AND z)) = ((x AND y) AND z)\)
  • 분배 법칙(Distributive Laws)
    • \((x AND (y OR z)) = (x AND y) OR (x AND z)\)
  • 드 모르간 법칙(De Morgan Laws)
    • \(NOT(x AND y) = NOT(x) or NOT(y)\)

게이트 논리

게이트(Gate)는 불 함수를 구현한 물리적 장치를 의미한다. 예를 들어 n개의 변수를 받아 m개의 2진 결괏값을 반환하는 불 함수 \(f\) 가 있을 경우, 이를 구현하는 게이트에는 n개의 입력 핀과 m개의 출력 핀이 있게 된다.

복잡한 불 함수를 더 단순한 함수로 표현했던 것처럼, 복잡한 게이트 또한 더 기초적인 게이트로 구성할 수 있다. 가장 단순한 형태의 게이트는 트랜지스터(Transistor)라 불리는 아주 작은 스위치 장치들을 특정한 구조로 연결해서 특정 기능을 하도록 만든 것이다.

이러한 스위치는 여러 기술로 구현할 수 있지만, 가장 중요한 사실은 그 기능들을 모두 불 대수로 추상화할 수 있다는 것이다. 이는 곧 컴퓨터 과학자들이 물리적인 영역에 신경 쓸 필요가 없다는 것을 뜻한다.

결국 하드웨어 설계자는 AND 게이트와 같은 기본 게이트(Primitive gate)를 만들고 이를 서로 연결하여 조합 게이트(Composite gate)를 만들어 복잡한 기능을 구현할 수 있게 되며 이때 사용한 게이트에 대해서는 상세한 구현 방식을 알 필요가 없게 되는 것이다.

결국 게이트의 종류는 아래와 같이 두 가지로 분류할 수 있다.

  • 기본(Elementary)
    • 예를 들어 NAND, AND, OR, NOT 게이트 등이 있다.
  • 조합(Composite)
    • 예를 들어 MUX, ADDER 게이트 등이 있다.

주의

책에서는 기본 게이트의 기본Primitive라 적혀 있지만 강의에서는 Elementary라 적혀 있다. 두 단어 모두 동일한 기본을 의미하므로 혼동하지 않도록 주의해야 한다.

그리고 이렇게 게이트를 서로 연결해서 조합 게이트를 만드는 기술을 논리 설계(Logic design)라 한다. 예를 들어 아래 이미지를 한 번 살펴보자.

논리 게이트는 위 이미지와 같이 내부와 외부, 두 가지 관점으로 바라볼 수 있는데 이때 외부를 의미하는 왼쪽을 게이트 인터페이스(Gate interface)라 하며 내부의 아키텍처를 의미하는 오른쪽을 게이트 구현(Gate implementation)이라 한다.

결국 내부 아키텍처, 즉 구현(Implementation) 부분은 오로지 게이트를 설계하는 사람만 신경 써도 되며 이를 부품으로 활용하는 사람은 인터페이스(Interface) 단계만으로 충분하다.

참고

이때 인터페이스는 유일하다. 그 표현하는 방법은 단 한 가지로 진리표, 불 표현식 등으로 표현하지만 구현하는 방식은 여러 가지다.

다시 말해 하나의 인터페이스는 여러 가지 방법으로 구현될 수 있는데 그중 비용, 속도, 단순성 등의 여러 측면을 고려하여 더 나은 구현 방법을 채택하는 것이다.

따라서 기능적 관점에서는 어떤 방식으로든 정해진 인터페이스를 따르는 게이트를 구현하는 것이 요구되는 사항이고, 효율성 관점에서는 최소 비용 최대 효과가 요구되는 사항이다.

결국 논리 설계는 주어진 게이트 인터페이스를 구현하는 효율적인 방법을 찾는 과정을 뜻한다.

하드웨어 기술 언어

하드웨어 설계자들은 더 이상 예전처럼 부품을 손으로 직접 만들지 않는다. 대신 하드웨어 기술 언어(HDL_Hardware Description Language)를 사용하여 칩 아키텍처를 설계하고 최적화한다.

이때 해당 HDL 프로그램을 테스트할 수 있는 하드웨어 시뮬레이터(Hardware simulator)를 사용하는데 이를 통해 몇 가지 불 연산을 수행하는 게이트를 만들어 볼 것이다.

규칙

그 전에 하드웨어 기술 언어의 몇 가지 규칙을 먼저 살펴보고자 한다.

  • 칩 구조: 정의는 헤더(Header)본문(Body)으로 되어 있다.
    • 헤더(Header)
      • 칩의 인터페이스(Interface)를 정의한다.
    • 본문(Body)
      • 구현(Implementation)을 담당한다.
  • 구문 규칙
    • 대소문자를 구문하며 키워드들은 대문자다.
  • 식별자 명명 규칙
    • 칩과 핀 이름들은 맨 앞에 글자가 숫자가 아닌, 어떤 문자나 숫자로 이루어진 문자열이다.
    • 관례상 칩 이름은 대문자, 핀 이름은 소문자로 시작한다.
    • 가독성을 위해 이름에는 대문자가 포함될 수 있다.
  • 공백
    • 공백 문자, 개행 문자, 주석은 무시된다.
  • 주석
    • // 라인 끝까지 주석
    • /* 닫을 때까지 주석 */
    • /** API 문서 주석 */
  • 닫기
    • 세미콜론(;)을 통해 닫는다.

헤더는 앞서 설명한 것처럼 인터페이스(Interface)를 정의한다. 예시 코드는 아래와 같다. 각 라인에 삽입된 주석을 통해 해당 문법이 무엇을 의미하는 지 확인할 수 있다.

CHIP Chip {      // (1)

    IN a, b;     // (2)

    OUT out;     // (3)

    BUILTIN And; // (4)
}
  1. 칩의 이름을 기술한다. 예시에서는 Chip이다. 보통 대문자로 시작한다.
  2. 입력 핀을 기술한다. 예시에서는 ab이다.
  3. 출력 핀을 기술한다. 예시에서는 out이다.
  4. 내장형 칩을 기술한다. 예시에서는 다른 파일에서 칩으로 구현된 And 칩이다.

본문(Body)

System Architect decides which chips are needed and for each chip, the architect creates chip API, test script, compare file and then by the given these resources, the developers can build the chips, by usign HDL.