https://gall.dcinside.com/mgallery/board/view/?id=factorio&no=29319
원래 팩토리오라는 게임 하려고 쓴 건데 여기 사람들도 좋아할 거 같아서 한번 올려봄
논리회로란?
하나 이상의 입력값에 대해 연산을 해서 하나의 출력값을 얻는 전자 회로를 말한다.
이놈은 OR게이트라 하는데, A, B중 하나만 1이어도 Y가 1이 되도록 만든다.
진리표로 나타내면
A | B | Y |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 1 | 1 |
이게 되겠다.
그럼 입력을 2개 받는 논리회로는 모두 몇 종류가 있을까?
물론 두 입력값이 대칭적이라는 가정 하에
입력값이 0, 0 일때 0이나 1
입력값이 0, 1 일때 0이나 1
입력값이 1, 1 일때 0이나 1
이렇게 8종류라고 생각할 수 있지만 아니다
A | B | Y |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 1 | 0 |
A | B | Y |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 1 |
이 두 경우를 제외하고 6개다
위에꺼는 입력이 무엇인지에 관계없이 그냥 0을 출력하고
아래꺼는 입력에 무엇인지에 관계없이 그냥 1을 출력한다.
논리연산을 하는 것이 아니라 그냥 선이 끊어진 것이나 다름없기 때문에 논리회로로 치지 않는 것이다.
그래서 AND, OR, XOR, NAND, NOR, XNOR 이 6개로 끝이다.
가산기란?
두 수의 덧셈을 연산하는 회로이다.
가산기는 어떻게 작동해야 하는가?
컴퓨터는 이진수를 사용하기 때문에 이제 이진수를 이용해서 설명할 거임.
1자리수+1자리수를 계산하려고 하면 결과값은
00 01 10
이 3가지가 나올 수 있겠지
진리표를 작성하면?
A | B | C | S |
0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
이렇게 되겠지.
이때 C는 Carry(받아올림)의 약자고 S는 Sum(합)의 약자임
그냥 이렇게 쓰더라
이걸 잘 보면 C는 AND 논리회로랑 진리표가 똑같고 S는 XOR 논리회로랑 진리표가 똑같은 거를 볼 수 있음.
그럼 간단한 가산기는 그냥 이렇게 구현이 가능하다.
이를 반가산기 라고 한다.
복수 자리수 가산기
이거는 1비트+1비트를 계산한 결과다.
이제 0+0, 0+1, 1+1의 결과값이 무엇인지 계산할 수 있다는 뜻이다
그러면 더 큰 숫자, 예를 들어 13+3이 무엇인지 계산하고 싶다면 어떻게 해야 될까?
그러기 위해서는 A와 B뿐만 아니라 Carry-in(받아올림 된 숫자)도 인풋으로 받는 가산기를 만들면 된다.
A | B | Cin | Cout | S |
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 0 |
1 | 1 | 1 | 1 | 1 |
입력 3개가 모두 대칭적이라는 가정 하에 썼다
솔직히 디씨 서식 내에서 표쓰는거 너무 노가다임
아무튼 이런 진리표를 갖는 가산기는 이렇게 구현함.
이거를 전가산기 라고 한다.
그럼 전가산기를 이렇게 줄줄이 이으면?
입력으로 A0, A1, A2, A3, B0, B1, B2, B3 을 받고 출력으로 S0, S1, S2, S3, C4 를 내놓는 가산기가 완성된다
이거를 RCA;Ripple Carry Adder(물결 자리올림수 가산기) 라고 부르더라
자리올림수가 왼쪽으로 이동하는게 호수에 퍼지는 물결을 보는 것 같아서 그렇대나 아무튼 그런 식으로 이름이 붙었다
RCA의 문제
RCA를 만들었다고 계산이 한 번에 해결되는게 아니다
RCA로 가산기를 만들면 nbit 덧셈을 하는데 n개의 전가산기를 통과하게 된다(위의 회로도를 다시 보자)
이를 Linear Time 이라고 한다.
덧셈은 연산의 기본 중의 기본이기 때문에 RCA만 쓴다면 고속 정보처리가 불가능하게 되겠지
여기서 더 생각해보면 자리올림이 이전 자릿수의 결괏값에 의존적이기 때문에 병목이 되고,
이 자리올림 문제를 효율적으로 처리해야겠다는 생각까지 도달할 수 있겠지.
자리올림수 예측 가산기
방금 전에 봤던 RCA랑 비슷하게 생겼지만 Cn을 CLA;Carry Look Ahead Adder(자리올림수 예측 가산기)가 공급해 준다는 점이 다르다
이게 무슨 원리인지 알아보기 전에 두 함수를 지정하겠다
G(A,B) = A AND B
P(A,B) = A XOR B
G는 Generate(생성) 의 약자다.
G가 1이면 C에 관계 없이 무조건 자리올림수가 생성되겠지
P는 Propagate(전달) 의 약자다.
P가 1이면 C값에 따라 자리올림수가 생성되는지 안 되는지가 달라지겠지
아무튼 여기서 중요한 거는 C를 계산하지 않아도 G와 P를 알 수 있다는 점이다
이제 G와 P를 이용해서 임의의 C와 S를 계산해보자
S = P XOR C
Cout = G OR (P AND Cin)
이해 잘 안되면 위에부터 다시 읽으면서 생각해보자
이제 아래첨자를 좀 써서 설명해야 하는데 어떻게 쓰는지 모르겠으니 그냥 숫자를 뒤에 붙이겠음.
C0 = C0 이다 (이거는 그냥 입력값 중의 하나기 때문임).
C1 = G0 OR (P0 AND C0)
C2 = G1 OR (P1 AND C1)
C3 = G2 OR (P2 AND C2)
C4 = G3 OR (P3 AND C3)
이 되겠지
그럼 이거를 재귀적으로 풀어내면?
C0 = C0
C1 = (G0) OR (P0 AND C0)
C2 = G1 OR (P1 AND (G0 OR (P0 AND C0)))
= (G1) OR (P1 AND G0) OR (P1 AND P0 AND C0)
C3 = G2 OR (P2 AND (G1 OR (P1 AND (G0 OR (P0 AND C0)))))
= (G2) OR (P2 AND G1) OR (P2 AND P1 AND G0) OR (P2 AND P1 AND P0 AND C0)
C4 = G3 OR (P3 AND (G2 OR (P2 AND (G1 OR (P1 AND (G0 OR (P0 AND C0)))))))
= (G3) OR (P3 AND G2) OR (P3 AND P2 AND G1) OR (P3 AND P2 AND P1 AND G0) OR (P3 AND P2 AND P1 AND P0 AND C0)
이제 좀 보이는가?
우리는 이제 논리 신호를 이용해서 4비트 덧셈을 실행할 수 있다
회로가 좀 복잡해지긴 하겠지만 상수시간 안에 덧셈을 할 수 있는 것이다
하지만 건물만한 컴퓨터를 짓고 싶은게 아니라면 공간과 시간 사이에서 적당히 합의를 봐야 한다
Log Time Adder
로그시간 안에 덧셈을 하는 회로를 짜 보도록 하겠다.
로그시간이란?
선형 | 로그 | 상수 | |
1 | 1 | 1 | 1 |
2 | 2 | 2 | 1 |
3 | 3 | 2 | 1 |
4 | 4 | 3 | 1 |
5 | 5 | 3 | 1 |
10 | 10 | 5 | 1 |
100 | 100 | 8 | 1 |
1000 | 1000 | 11 | 1 |
10000 | 10000 | 15 | 1 |
선형보다 빠르고 상수보다 느린 거를 로그시간이라고 한다
보통 O(log n) 이런 식으로 표기함
이진 트리
이를 해결하기 위해서는 BIT;Binary Index Tree(이진 트리) 를 심어야 한다.
여기서 새로운 함수를 하나 더 도입하는데,
Gm;n = (Gm) OR (Pm AND Gm-1) OR (Pm AND Pm-1 AND Gm-2) OR ... OR (Pm AND Pm-1 AND ... AND Pn+1 AND Gn)
Pm;n = Pm AND Pm-1 AND ... Pn+1 AND Pn
으로 정의된다.
각각 G집합, P집합이라고 읽음.
예를 들면
G3;0 = (G3) OR (P3 AND G2) OR (P3 AND P2 AND G1) OR (P3 AND P2 AND P1 AND G0)
P3;0 = P3 AND P2 AND P1 AND P0
이런 식으로 정의되는 함수임.
위의 C4와 G3;0 이 다르다는 점과 Gm;n/Pm;n 의 출력값은 여전히 1비트라는 점에 유의할 것.
이렇게 집합 두 개를 합칠 수도 있다.
Gi;j = Gi;k OR (Pi;k AND Gk-1;j)
Pi;j = Pi;k AND Pk-1;j
아까 C4의 정의를 다시 한번 가져와 보자.
C4 = G3 OR (P3 AND (G2 OR (P2 AND (G1 OR (P1 AND (G0 OR (P0 AND C0)))))))
= (G3) OR (P3 AND G2) OR (P3 AND P2 AND G1) OR (P3 AND P2 AND P1 AND G0) OR (P3 AND P2 AND P1 AND P0 AND C0)
= G3;0 OR (P3;0 AND C0)
C4를 재귀적으로 계산하고자 할 때는 RCA처럼 C0에서 C1, C2, C3, C4 이렇게 순서대로 올라와도 되겠지만
G
1틱 - G0 + G1 = G1;0
1틱 - G2 + G3 = G3;2
2틱 - G1;0 + G3;2 = G3;0
P
1틱 - P0 + P1 = P1;0
1틱 - P2 + P3 = P3;2
2틱 - P1;0 + P3;2 = P3;0
C
3틱 - G3;0 + P3;0 + C0 = C4
이렇게 계산할 수도 있다.
이를 회로도로 나타내면 나무 모양이 되기 때문에 BIT;Binary Index Tree(이진 트리) 라고 부른다더라
아무튼 이렇게 하면 O(log2 n)의 시간만으로 모든 G값과 P값의 합을 구할 수 있다!
마찬가지 방법으로(순서만 바꿔서 하면) 각각의 C값도 구할 수 있다.
출처-
ㅋㅋ 이거 정보처리기능사에서 본건데
로그타임애더는 첨보네
개쩌네... 신기하다