[밑바닥부터 만드는 컴퓨팅 시스템] 1장 불 논리 구현

공부/밑바닥부터 만드는 컴퓨팅 시스템

[밑바닥부터 만드는 컴퓨팅 시스템] 1장 불 논리 구현

다위 2022. 11. 1. 09:41

1.1 배경

1.1.1 불 대수

불대수는 true/false, 1/0 같은 불(또는 2진수)값을 다루는 대수학이다.
불함수는 2진수를 입력 받아 2진수를 출력하는 함수이다.

· 진리표 표현

진리표 (trueth table) 표현은 불 함수를 정의하는 가장 쉬운 방법으로
함수의 입력값들과 결과값을 나란히 쓰는 방법이다.

· 불 표현식

기본적으로 자주 사용되는 불 연산은 "And", "Or", "Not"이 있으며
각각 x·y, x+y, x'로 표현된다.

· 정준 표현

모든 불 함수는 정준 표현 (canonical representation)이라 불리는 불 표현식으로 표현 가능하다. 예를 들어 정준표현식 f(x,y,z)=x'yz'+xy'z'+xyz'로 표현되며 아무리 복잡한 불 함수라도 And, Or, Not의 세가지 불 연산만으로 표현 가능하다. 재밌는 점은 Nand 함수(Nor 함수 또한)를 이용하여 And, Or, Not 연산을 만들 수 있다. 결국 모든 불 함수는 Nand 연산만으로 표현 가능하다.

1.1.2 게이트 논리

게이트는 불함수를 구현한 물리적 장치다. 복잡한 불 함수를 더 단순한 함수로 표현할 수 있는 것처럼, 복잡한 게이트는 더 기초적인 게이트로 구성할 수 있다. 가장 단순한 형태의 게이트들은 트랜지스터라는 작은 스위치 장치들을 연결하여 만든 것이고, 스위치의 기능들은 모두 불 대수로 추상화 할 수 있다.

· 기본 게이트와 조합 게이트

모든 논리 게이트는 입력 및 출력 신호 형태가 같으므로(0또는 1), 서로 연달아 이으면 더 복잡한 조합 게이트를 만들어 낼 수 있다. 논리 설계(logic design)란 게이트를 서로 연결해서 더 복잡한 기능을 하는 조합 게이트를 만드는 기술이다. 논리 게이트들은 내부와 외부, 두가지 관점으로 바라볼 수 있다. 내부는 게이트의 내부 아키텍처, 즉 구현 implementation을 의미하며, 외부는 게이트의 인터페이스, 즉 바깥에 노출된 입력 핀과 출력 핀들을 의미한다. 논리설계의 목적은 기존에 구현된 게이트들을 이용해서, 주어진 게이트 명세(인터페이스)를 구현하는 효율적인 방법을 찾는 것이라고 할 수 있다.

1.1.3 하드웨어 기술 언어

오늘날 하드웨어 설계자들은 컴퓨터 워크스테이션에서 하드웨어 기술 언어 도구를 사용해서 칩 아키텍처를 설계하고 최적화한다. 설계자는 하드웨어 시뮬레이터라는 특별한 소프트웨어 도구를 이용하는데, 이 도구는 HDL 프로그램을 입력으로 받아 메모리 위에 모델링된 칩 이미지를 만든다. 그 후 동작 테스트와 여려 변수들을 고려하며 칩의 요구 성능 대비 비용 수준을 맞출 때까지 설계를 최적화 한다.

· 예제: XOR 게이트 제작

Xor(a,b)=Or(And(a, Not(b)), And(Not(a),b))는 베타적 논리합 (exclusive or)울 정의하는 하나의 방법이다.

1.2 명세

1.2.1 Nand 게이트

다른 모든 게이트들의 기초가 되는 게이트로, 따로 구현할 필요가 없다.

If a=b=1 then out=0 else out 1.

1.2.2 기본 논리 게이트

· Not

단일 입력 Not 게이트는 컨버터라고 불리며,
입력값을 0에서 1, 또는 1에서 0으로 변화한다.

If in=0 then out=1 else out=0.

· And

입력값 중 하나가 1일 때는 1을, 그 외에는 0을 반환한다.

If a=b=0 then out=0 else out=1.

· XOR

두 입력값이 다를 경우 1을, 그 외에는 0을 반환한다.

If a≠b then out=1 else out=0.

· 멀티플렉서

멀티플렉서는 3-입력 게이트로 '선택 비트' 입력을 이용해 나머지 두 개의 '데이터 비트' 입력 중 하나를 선택한다.

If sel=0 then out=a else out=b

· 디멀티플렉서

디멀티플렉서는 멀티플렉서와 정반대 기능을 한다. 선택 비트에 따라 두 출력선 중 하나를 선택해 입력 신호를 내보낸다.

If sel=0 then {a=in, b=0} else {a=0, b= in}.

1.2.3 기본 게이트의 멀티비트 버전

컴퓨터 하드웨어는 일반적으로 '버스'라고 불리는 멀티비트 배열에 대한 연산을 수행한다. 버스 내의 개별 비트들을 가리킬 때는 보통 배열 문법을 활용한다. 예를 들어 data라는 16비트 버스가 있다면, data[0], data[1], ··· data[15]와 같이 개별 비트를 표기한다.

·멀티비트 Not
n비트 Not게이트는 n비트 입력 버스의 모든 비트에 대해 Not 연산을 수행한다.

For i=0..15 out [i]=not(in[i]).

·멀티비트 And
n비트 And게이트는 두 개의 n비트 입력 버스로 들어오는 모든 n비트 쌍에 대해 And연산을 수행한다.

For i=0..15 out [i]=And(a[i],b[i]).

·멀티비트 Or
n비트 Or 게이트는 두 개의 n비트 입력 버스로 들어오는 모든 n비트 쌍에 대해 Or연산을 수행한다.

For i=0..15 out [i]=Or(a[i],b[i]).

·멀티비트 멀티 플렉서
n비트 멀티플렉서는 입력이 n비트라는 점을 제외하면 기존 멀티플렉서와 같다.
단, 선택 비트는 여전히 1비트이다.

If sel=0 then for i=0..15 out [i]=a[i]
else for i=0..15 out[i]=b[i]

1.2.4 기본 게이트의 다입력 버전

2-입력 논리 게이트들은 입력이 여러개인 다입력 게이트들로 자연스럽게 일반화 할 수 있다.

· 다입력 Or

n-입력 Or 게이트는 n비트 입력 중 적어도 하나가 1이면 1을 출력하고, 그 외에는 0을 출력한다. 아래는 8-입력 게이트의 예이다.

out=Or(in[0],in[1],...,in[7])

· 다입력/멀티비트 멀티플렉서

m-입력 n비트 멀티플렉서는 m개의 n비트 입력 버스 중에 하나를 골라서 n비트 출력 버스에 출력한다. 선택 입력은 k개의 제어 비트로 되어 있으며 k=log₂m 이다. 여기서 개발할 컴퓨터 플랫폼에는 이런 칩이 두 종류(4-입력 16비트 멀티 플렉서와 8-입력 16비트 멀티플렉서)가 필요하다.

If sel = 00 then out = a else if sel = 01 then out = b
else if sel = 10 then out = c else if sel =11 then out = d

If sel = 000 then out = a else if sel = 001 then out = b
else if sel = 010 then out = c ... else if sel =111 then out = h

· 다입력/멀티비트 디멀티플렉서

m-입력 n비트 디멀티플렉서는 n비트 입력을 하나 받아 m개의 n비트 출력 중 하나로 내보낸다. 선택 입력은 k개의 제어 비트로 되어 있고, k=log₂m 이다, 여기서 개발할 컴퓨터 플랫폼에는 이런 칩이 두 종류(4-입력 1비트 디 멀티플렉서와 8-입력 1비트 디 멀티플렉서)가 필요하다.

If sel = 00 then {a=in, b=c=d=0}
else if sel = 01 then {b=in, a=c=d=0}
else if sel = 10 then {c=in, a=b=d=0}
else if sel = 11 then {d=in, a=b=c=0}.

If sel = 000 then {a=in, b=c=d=e=f=g=h=0}
else if sel = 001 then {b=in, a=c=d=e=f=g=h=0}
else if sel = 010 ...
...
else if sel = 111 then {h=in, a=b=c=d=e=f=g=0}

1.3 구현

· Not

CHIP Not {
    IN in;
    OUT out;

    PARTS:
    Nand(a=in, b=in, out=out);
}

· And

CHIP And {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a,b=b,out=nandab);
    Nand(a=nandab,b=nandab,out=out);
}

· Or

CHIP Or {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a, b=a, out=nota);
    Nand(a=b, b=b, out=notb);
    Nand(a=nota, b=notb, out=out);

}

· XOR

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a=a, b=a, out=nota);
    Nand(a=b, b=b, out=notb);
    Nand(a=a, b=notb, out=nandanb);
    Nand(a=nota, b=b, out=nandnab);
    Nand(a=nandanb, b=nandnab, out=out);

}

· MUX

CHIP Mux {
    IN a, b, sel;
    OUT out;

    PARTS:
    Not(in=sel, out=notsel);
    And(a=sel, b=b, out=selA);
    And(a=notsel, b=a, out=selB);
    Or(a=selA, b=selB, out=out);
}

· DMUX

CHIP DMux {
    IN in, sel;
    OUT a, b;

    PARTS:
    Not(in=sel, out=notSel);
    And(a=sel, b=in, out=b);
    And(a=notSel, b=in, out=a);
}