배경
마인크래프트에서 가장 재미있다고 생각하던 것 중에 하나는 아무래도 레드스톤과 커맨드 블럭일 것이다. 나는 마인크래프트에서 레드스톤을 통해 뭔가 대단한 것을 만드는 것을 좋아했고, 언젠가 레드스톤으로 키보드를 만들고 싶다고 생각한 적이 있다. 따라서 키보드 모형을 만들고 키보드의 기능을 구현할 때 즈음, 어떻게 하면 글자를 입력할 수 있는 "화면"을 만들 수 있을지 고민하기 시작했다. 쉽게 고민이 끝나지 않자 유튜브에서 다른 사람들이 만든 레드스톤 키보드를 찾아보았고, 키보드만 만든 사람보다는 컴퓨터까지 같이 만든 사람들이 많은 것을 보고, 레드스톤으로 컴퓨터를 만들어보고 싶다고 생각했다.
제로켄
2020년 어느날, 나는 이 영상을 발견했다.
각별은 레드스톤을 이용해서 이진수 가산기를 구현하는 것을 영상으로 찍어 업로드했고, 나는 당시에 하던 마인크래프트 서버에 이 회로를 만들어보고자 했다. 이때 제로켄이 알려준 것이 2-bit Full Adder이다.
방금 검색한 사진. 출처 리서치게이트
2-bit Full Adder를 가로로 연결해서 이전 회로의 이 다음 회로의 으로 연결되도록 하면 한 자리 숫자의 연산을 넘어서 여러 자리 연산까지 확장할 수 있다는 것이었다. 당시에 이것을 마인크래프트 회로로 구현하고, 시간이 지나 업그레이드를 거치면서 다음과 같은 회로를 완성했다.
이 회로는 2개의 8비트 2진수 숫자를 입력받아 두 숫자의 합을 16진수로 표시해주는 장치이다. 나는 분명히 이 숫자를 16진수가 아니라 10진수로 표현할 수 있을 것이라고 생각했고, 유튜브에 관련 정보를 찾아보았다.
조사
유튜브와 구글에서 정보를 검색하던 도중 알아낸 것은 2진수 숫자를 BCD로 바꾼 후에, BCD를 10진수로 바꿔야 한다는 것이다. 사실 당연한 것이, 결국은 2진수로(전기적으로) 숫자를 나타내야 할 것인데 2진수만으로 10진수를 나타낼 수 있는 방법은 없기 때문이다. 따라서 Binary to BCD Converter Circuit 등을 검색해 보았는데, 다음과 같은 사진을 얻을 수 있었다.
출처 English Wikipedia - Double Dabble
이는 알고 보면 상당히 올바른 설명이지만, 당시의 나를 이해시키기에는 충분하지 않았다.
그 다음으로 발견한 영상은 다음이다.
이 영상을 통해서 Double Dabble 알고리즘의 전반적인 이해를 얻을 수 있었지만, 이것을 어떻게 기계적으로 구현하는지는 또 다른 문제였다.
따라서 더 정보를 찾아보다가 마인크래프트로 컴퓨터를 만드는 사람이 찍은 튜토리얼 영상을 발견했다. 56분짜리 영상이고 2개의 영상으로 나누어져 있었기 때문에 보지 말까 싶었지만, 당장 봐보는 것이 좋을 것 같다고 판단하여 영상을 보았다. 결국은 4비트 입력 값이 5 이상이면 그 값에 3을 더해서 출력하는 기계를 회로 중간중간에 끼워넣어야 한다는 것인데, 이해는 되지 않았지만 일단 그대로 해보니 문제 없이 작동하더라.
따라서 이 회로를 사용해 원하는 기계를 만들 수 있었다.
Ben Eater
올해 초반, 유튜브에서 Ben Eater라는 사람의 다음 영상을 발견하게 되었다.
이 영상은 브레드보드 위에서 비디오 카드를 구현하는 내용을 담고 있었다. 실제로 동작하는 것을 보니 신기하기도 했다.
영상의 내용을 이해하지는 못했지만, 모니터에 내용을 띄우고 하는 등의 일이 결국은 정말로 0과 1로 이루어져 있다는 것을 알게 되고 크게 감명받아, 0과 1만을 이용해서 컴퓨터의 모든 것을 구현하는 방법에 대한 탐구를 진행했고, 그것이 2021년 4월에 작성한 2진수의 기계적인 활용이 되겠다.
SchBoard
<2진수의 기계적인 활용> 탐구활동을 진행하고 나서 줄곧 나는 브레드보드에 직접 컴퓨터를 구현해보고 싶다고 생각했다. 나는 이것이 혼자 진행하기에는 상당한 무리가 있다고 판단했고, 다른 사람과 함께 진행하는 프로그래밍 프로젝트를 해보고 싶기도 하여, 입시가 끝나고 시간적인 여유가 생긴다면 다른 사람과 같이 프로그래밍 프로젝트를 진행해보고 싶다고 생각했다. 그래서 만든 것이 바로 <Lofanfashasch>. 내가 알고 있는 모든 지식을 다른 사람에게 알려주고, 내가 원하는 프로젝트를 언제나 진행할 수 있도록 하는 것이 큰 목표이다.
2021년 7월 말부터 Lofanfashasch에서는 굉장히 열심히 수업을 진행했으나, 세상에 태어나서 한 번도 접해본 적이 없는 새로운 정보를 듣자마자 이해해야 하는 어려운 커리큘럼 속에서, 그리고 현생과의 마찰 속에서 이상만큼 큰 진보를 이루지는 못했다. (물론 Lofanfashasch가 망하지는 않았다!!! 열심히 수업을 진행하고 있다.)
그리고 올해 8월 후반, 입시 전쟁 속에서 잠시 동안 여유가 남아 이 시간을 이용해 브레드보드 프로젝트를 진행해보면 좋을 것 같다고 생각하여 OR, NOT만으로 모든 것을 만들어내는 <SchBoard> 프로젝트를 시작했다. SchBoard를 통해서 우경고찬폐문하성 채널에 <0과 1에서 시작하는 컴퓨터 만들기> 시리즈를 진행하는 것도 생각해 보았다.
SchBoard 프로젝트를 시작한 것은 8월 28일, 오늘은 8월 29일이다. 즉, 나는 하루만에 SchBoard의 대부분의 기능을 구현해냈고, 테스트 과정을 남겨놓고 있는 중이다. 이 프로젝트는 유튜브에서 강좌를 찍는 것을 전제하고 개발을 진행했기 때문에 언젠가 Double Dabble 알고리즘에 대해서도 설명해야 할 것이라고 직감적으로 느꼈다.
따라서 Double Dabble 알고리즘에 대해서 이해를 마친 다음, 이를 까먹지 않기 위해 문서로 내용을 남긴다.
Double Dabble 알고리즘
1절: 개요
Double-Dabble은 2진수 수를 BCD로 변환하는 방법에 대한 것이다.
이 문서는 BCD와 비트 시프트에 대해 알고 있는 사람이 Double-Dabble을 이해하고 활용할 수 있도록 작성되었다. 이 문서에는 Double-Dabble 알고리즘의 유도과정과 실제로 전자 회로에서는 어떻게 활용하는지에 대한 정보를 담고 있다.
2절: BCD 정상화
Preset. BCD는 한 숫자가 4개의 비트로 이루어져 있기 때문에 10진수의 16진수 표기라고 하자.
일단 1010이라는 수를 상정하자. 우리는 이것을 1 0000으로 만들 것이다. 10을 16으로 바꾸기 위해서는 6을 더해야 한다. 따라서 이 숫자에 110을 더한다. 그러면 우리는 성공적으로 1 0000을 구해낼 수 있다.
이는 1010 이상인 모든 4비트 수들에 대해서 적용된다. 즉, 값이 1010 미만인 값에 대해서는 적용되지 않는다. 예를 들어, 1001이라는 수는 그 자체로 하나의 BCD 글자인데, 여기에다가 110을 더하면 1111이 나오기 때문에 BCD로 표현할 수도 없을 뿐더러 원하는 결과가 아니다. 따라서 숫자가 10 이상일 때에는 그 숫자에 6을 더한다는 것이 Double-Dabble 방식의 중요한 포인트이다. (이 작업을 ADD6이라고 부르자.)
이러한 방식으로 1111을 변환해 보자. 1111은 1010 이상의 숫자이기 때문에 110을 더한다. 1111 + 0110 = 1 0001 + 0100 = 1 0101. 따라서 1111은 BCD로 1 0101, 즉 15임을 알 수 있다.
3절: 일반화 서두
4자리를 넘어가는 수들에 대해서는 이 방식을 바로 적용하기 곤란하다. 우리는 5자리 이상의 수들에 대해서 이 규칙을 적용하기 위해 BCD와 2진수의 공통적인 특성을 이용할 필요가 있다.
2진수로 표현된 대부분의 표기법(notation)들은 왼쪽으로 한 자리 비트 시프트 연산을 수행했을 때에 그 값이 2배가 되는 경향이 있다. 예를 들어, 0100 0011과 101011은 각각 수 43의 BCD와 2진수 표현이다. 이 수들을 왼쪽으로 1만큼 시프트한 수인 1000 0110과 1010110은 모두 86, 즉 43의 2배인 수를 의미하므로 이 특성이 적용된다.
하지만 BCD의 경우 이것이 적용되지 않는 예가 있다. 예를 들자면, 한 자리수에서 숫자를 시프트한 결과가 1010 이상인 경우, 예를 들자면 0111을 시프트하는 등의 경우이다. 이러한 경우에는 시프트-2배 규칙이 통하지 않고, 추가적인 작업을 해 주어야 한다.
운좋게도, 우리는 이미 이것을 2절에서 해냈다. 0111을 시프트하면 1110을 얻어내는데, 여기에 ADD6 연산을 수행한다. 그러면 1 0100을 얻어낼 수 있고, 이것은 올바른 BCD 구문(syntax)이며, 그 결과도 올바르다.
4절: 일반화 I
5자리 이상의 수, 혹은 그 이상의 길이를 가지고 있는 수에 대해서 2절의 내용을 적용하려면 2절의 내용을 확장성 있는 다른 방향으로 바꿀 필요가 있을 것이다. 수학자들은 2진수의 가장 높은 자리수 숫자부터 하나씩 수를 대입하는 방식으로 이를 해결했다.
이해가 되지 않는다면 다음 예시와 설명을 함께 확인하자.
11111 Initial State.
1 1111 Shift.
11 111 Shift.
111 11 Shift.
1111 1 Shift.
+110 Add 6,
1 0101 1 As 10^0's digit was 15, >= 10.
10 1011 Shift.
+110 Add 6,
11 0001 As 10^0's digit was 11, >= 10. End.수를 왼쪽으로 밀면 2배가 된다는 것은 BCD에서도, 2진수에서도 적용되는 공통적인 특징이다. 이 상태에서 1의 자리에 1을 더하느냐 0을 더하느냐로 모든 숫자를 구현할 수 있다. 모든 자리수를 다 밀 때까지 이 연산을 진행할 수 있기 때문에 얼마나 짧은 자리수의 수를 가져와도, 얼마나 긴 자리수의 수를 가져와도 유한하다면 유한한 시간 안에 계산해낼 수 있다.
하지만 3절 4문단에서 언급했듯이, 일부 상황에 대해서 BCD의 시프트-2배 규칙은 적용되지 않는다. 따라서 시프트를 진행한 Raw-BCD 수의 올바른 자릿수에 맞춰 ADD6을 수행해 주어, 올바른 BCD 구문으로 표현해 준다.
이 작업을 모든 자릿수에 대해 시프트를 할 때마다 진행한다. 즉, 시프트를 할 때마다 시프트로 인해 발생하는 오류로부터 BCD를 알맞게 교정하는 것이다. 그렇게 한다면, 2진수의 모든 자릿수를 BCD로 표현하되, ADD6을 통해서 오류를 보정해 올바른 구문으로 표현되게 해줄 수 있다. 즉, 2진수 숫자를 BCD로 구현해낼 수 있다.
5절: 일반화 II
하지만 위 방식에는 오류가 있다. 2진수 1 0000 = 16을 위 방식을 통해 BCD로 변환하기를 시도해보자.
10000 Initial State.
1 0000 Shift.
10 000 Shift.
100 00 Shift.
1000 0 Shift.
1 0000 End.2진수 1 0000을 BCD로 변환하기를 시도하니 1 0000이라는 결과를 얻을 수 있었다. 이는 10으로, 16이라는 초기 값과는 다른 수이다. 이 문제가 발생한 이유는 2진수의 1의 자리에서 ADD6 연산을 수행하지 않았기 때문이다. 즉, 2절에서 ADD6의 실행 조건으로 무언가를 빠뜨렸다는 말이다.
이 문제는 2진수 수의 가장 큰 자리수부터 아래로 세 자리가 100일 때 발생한다. 즉, 다섯 자리 2진수 수의 경우 16, 17, 18, 19의 경우에 발생한다. ADD6 연산은 네 자리의 2진수 수를 보고 처리를 할지 하지 않을 지 결정하는 것으로 정했는데, 위의 예시에서 볼 수 있듯, 수가 100으로 시작하면 어떤 곳을 잡아서 연속하는 네 자리 숫자를 보아도 1010과 같거나 넘지 않는다. 따라서 그 다음 시프트에서 추가적으로 ADD6을 진행해 주어야 한다는 새로운 실행 조건을 ADD6에 추가해 주어야 한다.
즉, ADD6의 동작은 입력 값에 따라 다음과 표와 같이 주어진다.
| 입력 (4자리 2진수) | 동작 |
|---|---|
1. 100으로 시작 | 다음 시프트에서 6 더하기 |
| 2. 10 미만 | 그대로 출력 |
| 3. 10 이상 | 6 더해 출력 |
2진수와 BCD의 특징을 이용하여 이 규칙을 간단하게 일반화하자.
6절: 일반화 III
위 표에서 1번 입력 조건의 경우, 다음 시프트에서 6을 더하는 연산을 수행하라고 한다. 다음 시프트에서는 현재 입력의 수치가 1 0000 이상이 되고, 이때 6을 더하는 연산을 수행하는 것이다.
이 현상은 ADD6의 입력을 5자리 수로 만드는 것으로 해결이 가능하다. 즉, BCD의 각 자릿수에서 왼쪽으로 5개의 비트를 확인했을 때, 수가 10 이상이라면 6을 더해 출력하라는 것이다. 이러한 방식으로 회로를 구현했을 때에, 정상적인 방법으로 ADD6으로의 입력이 1 0011을 초과하는 경우는 존재하지 않기 때문에 여기서 상정하지 않는 경우는 생각하지 않아도 된다. 즉, 입력되는 비트 수를 5개로 늘려서 2번과 3번의 특징을 1번에 바로 적용하겠다는 것이다. 이렇게 한다면 모든 2진수 수를 BCD로 변환할 수 있다.
10011 Initial State.
1 0011 Shift.
10 011 Shift.
100 11 Shift.
1001 1 Shift.
1 1011 Shift.
+ 110 Add 6,
1 0011 As 5 bits from 10^0's digit showed 19, >= 10. End.즉, 방금은 4개의 비트를 보고 처리를 진행했다면, 이번에는 5개의 비트를 보고 처리를 진행하는 것이다.
7절: 일반화 IV
6은 짝수이기 때문에, 6을 더하는 과정에서는 BCD상에서나 2진수상에서나 1의 자리 수가 변하지 않는다. 따라서 연산의 1의 자리 수는 무시 가능하다. 즉, 지금까지의 ADD6 연산이 5개의 입력을 받고 5개의 출력을 내보냈다면, 그 중 하나의 비트는 무의미한 것이었다는 뜻이 된다. 따라서 그 비트를 하나 무시하고 새로운 연산을 정의한다. 이것을 ADD3이라고 하자.
이름이 ADD3인 이유는, 1의 자리 비트가 없어지면서 마지막 비트가 1의 자리처럼 보이고, 연산의 결과가 5 이상인 경우에 3을 더해 출력하는 연산과 같이 보이기 때문이다.
ADD3의 진리표는 다음과 같이 주어진다.
| 입력 | 출력 |
|---|---|
| 0000 | 0000 |
| 0001 | 0001 |
| 0010 | 0010 |
| 0011 | 0011 |
| 0100 | 0100 |
| 0101 | 1000 |
| 0110 | 1001 |
| 0111 | 1010 |
| 1000 | 1011 |
| 1001 | 1100 |
위 표의 입력 단에 주어지지 않은 입력(1010, 1011 등)에 대해서는 원래 정의하지 않으나, 편의를 위해서 입력이 1100인 경우까지 확장해서 정의하기도 한다. 1101부터는 3을 더하면 오버플로우 현상이 발생하기 때문에 정의하지 않거나 1111, 0000 등의 무의미한 값을 대응하거나 오버플로우가 발생한 후의 연산 결과(0000, 0001, 0010)를 대응하는 등의 설정을 한다.
이 연산을 이용해 32(=100000)을 변환해보자
100000 Initialize.
1 00000 Shift.
10 0000 Shift.
100 000 Shift.
1000 00 Shift.
+ 11 ADD3. (10^0's place = 8 >= 5)
1011 00
1 0110 0 Shift.
+ 11 ADD3. (10^0's place = 6 >= 5)
1 1001 0
11 0010 Shift. End.변환 결과는 11 0010. 정답이다. 이 변환에서는 1000을 변환하는 과정이 있었다. 이는 2절에서 정의한 ADD6 연산으로는 계산 불가능한 것이었다.
또 다른 변환을 진행해보자. 변환하는 수는 63(=111111)이다.
111111 Initialize.
1 11111 Shift.
11 1111 Shift.
111 111 Shift.
+ 11 ADD3. (10^0's place = 7 >= 5)
1010 111
1 0101 11 Shift.
+ 11 Add3. (10^0's place = 5 >= 5)
1 1000 11
11 0001 1 Shift.
110 0011 Shift. End*.변환 결과는 110 0011. 정답이다. 이 변환에서 주의해야 할 점은 어포스트로피로 표현한 부분이다. 끝에서 BCD의 10^1의 자리가 6으로 5 이상임에도 불구하고 추가적인 작업 없이 변환을 종료했다. 이것은 ADD6에서 ADD3으로 바뀐 과정을 살펴보면 이해할 수 있다.
우리는 ADD6에서 6을 더하는 연산이 1의 자리에 아무런 영향을 끼치지 않음을 확인했고, 그 결과로 1의 자리를 버렸다. 따라서 우리가 연산을 할 때에 ADD3라는 이름에 속으면 안 된다. 우리는 3을 더하지만, 보이지 않는 1의 자릿수가 있기 때문에 사실은 6을 더하는 것이다. 우리는 1의 자리까지를 연산하되, 회로를 단순하게 하기 위해서 필요 없는 1의 자리를 무시한 것 뿐이다. 따라서 시프트를 한 후의 값이 한 단계의 종료라고 생각해야 하고, 그 때에 남은 2진수 자릿수가 없다면 연산을 종료해야 하는 것이다.
그러면 아예 ADD3라는 연산에 시프트를 포함시키면 되는 것이 아닌가 싶다. 물론 우리가 눈에 보는 방식으로 ADD3 연산을 진행한다면 연산에 시프트까지를 포함하는 것이 편리하고 좋겠으나, 실제로 계산하는 것은 기계이므로 그 점을 유의해야 한다. 다음 절에서는 회로로 이 알고리즘을 구현하는 방법을 살펴보겠다.
8절: 회로 구현
여기서 회로는 논리 회로, 전자 회로를 의미한다. 컴퓨터 소프트웨어로 구현하는 방법에 대해서는 다루지 않는다.
회로로는 레지스터 상에서 클럭마다 한 번씩 시프트를 하여 이진수 부분에 더 이상 수가 남아있지 않으면 종료하는 방식과, 그냥 ADD3 부품을 여러 개 배치하는 방법이 있다. 그중에 나는 부품을 여러 개 배치하는 방식을 선호하나, 비트의 길이가 정해져있지 않은 경우에는 전자의 방법을 사용해야 한다.
위키페디아에 후자의 구현에 대한 그림을 찾을 수 있었다.
이 그림에서 >4 ? +3으로 표현된 회로가 바로 우리가 만든 ADD3 회로이다. 오른쪽이 1의 자리이고, 왼쪽으로 갈 수록 자릿수가 높아진다.
우리가 위에서 예시를 표현할 때에는 수를 시프트하는 방식으로 표현하여 수가 움직이는 것처럼 느껴졌는데, 이 그림에서는, 그리고 많은 회로에서는 수를 시프트하기보다 부품 자체를 오른쪽으로(1의 자리 수 쪽으로) 시프트해가면서 높은 자릿수부터 연산을 시작해나간다.
높은 자릿수의 입력이 차례대로 00인 경우에는 입력값이 3보다 커질 수 없다. 따라서 가장 상치(上置)한 회로는 가장 높은 자릿수의 세자리를 받는다. 그 다음에는 수를 왼쪽으로 시프트하여 다음 자릿수가 1의 자리에서 ADD3 처리를 받듯이, 회로를 한 칸 오른쪽에 배치하여 시프트를 물리적으로(?) 구현해낸다.
BCD의 일의 자리 숫자는 이렇게 연산해나가고, 진행하다가 10의 자리 숫자 비트가 3개가 되면 1의 자리 숫자에서 했던 것과 같이 또 ADD3회로를 씌우며, 입력의 2의 자리 수까지 ADD3 회로를 연결하면 더 이상 놓지 않는다. 1의 자리 수가 아니라 2의 자리 수인 이유는 1의 자리 숫자가 ADD3 연산에 포함되지 않기 때문이다. (cf. 7절 마지막 문단)
이렇게 만들어진 회로의 출력은 네 글자씩 잘라서 한 10진수 수를 의미하는 BCD의 형태로 나오고, 4 to 7 Segment Converter 등에 연결하여 우리가 쉽게 볼 수 있는 형태로 변환할 수 있다.
마침
이 문서에서는 BCD의 표현 방식 중 한 자리에 10가지의 경우의 수만 사용가능한 것처럼 표현했는데, 사실 BCD에는 부호 표현을 위한 방식같은 추가적인 기능이 있기도 하다. 자세히는 알지 못하지만.
이 문서는 어디까지나 내가 알고 있는 것만을 정리하고 전달하기 위함이기 때문에 내용이 전문적이지 않거나 오류가 있을 수 있다. 그냥 참고용으로만 사용해주기 바란다.
