부스 곱셈 알고리즘(Booth's Multiplication Algorithm)은 2의 보수(2's complement) 표기법으로 표현된 두 개의 부호 있는 이진수를 곱하기 위한 효율적인 알고리즘입니다. 앤드류 도널드 부스(Andrew Donald Booth)는 덧셈보다 시프트 연산이 더 빨랐던 탁상용 계산기의 특성을 활용하여 연산 속도를 향상시키고자 이 알고리즘을 고안했습니다.
알고리즘 핵심 원리
부스 알고리즘은 곱셈기(Multiplier)의 비트 쌍(Qn, Qn+1)을 검사하여 연산을 결정합니다. 피승수(Multiplicand)는 BR 레지스터에, 곱셈기는 QR 레지스터에 저장하며, 누산기(AC)는 0으로 초기화합니다.
알고리즘 단계:
1. 피승수(Multiplicand)를 BR에, 곱셈기(Multiplier)를 QR에 저장한다.
2. Qn(현재 비트)과 Qn+1(이전 비트)을 비교하여 다음을 수행한다:
- 00 또는 11 (동일): 산술 오른쪽 시프트(Arithmetic Right Shift) 1비트 수행.
- 10 (1 → 0 변화): AC = AC - BR (피승수 뺄셈) 후 산술 오른쪽 시프트 수행.
- 01 (0 → 1 변화): AC = AC + BR (피승수 덧셈) 후 산술 오른쪽 시프트 수행.
3. 모든 비트 처리 시까지 반복한다.C++ 구현 예제
다음은 부스 알고리즘을 구현한 완전한 C++ 코드입니다. 사용자로부터 비트 수와 2의 보수 형태의 이진수를 입력받아 단계별 연산 과정과 최종 결과를 출력합니다.
#include <iostream>
using namespace std;
// 함수 선언
void add(int ac[], int x[], int q);
void complement(int a[], int n);
void ashr(int ac[], int qr[], int &qn, int q);
void display(int ac[], int qr[], int qrn);
// 2의 보수 구하기 (1의 보수 + 1)
void complement(int a[], int n) {
int x[10] = {0};
x[0] = 1; // +1을 위한 배열
for (int i = 0; i < n; i++) {
a[i] = (a[i] + 1) % 2; // 1의 보수 (비트 반전)
}
add(a, x, n); // 1 더하기
}
// 이진수 덧셈 (AC = AC + X)
void add(int ac[], int x[], int q) {
int c = 0; // 캐리
for (int i = 0; i < q; i++) {
ac[i] = ac[i] + x[i] + c;
if (ac[i] > 1) {
ac[i] %= 2;
c = 1;
} else {
c = 0;
}
}
}
// 산술 오른쪽 시프트 (ASHR)
void ashr(int ac[], int qr[], int &qn, int q) {
int temp = ac[0]; // AC의 LSB 저장
qn = qr[0]; // QR의 LSB를 Qn+1로 저장
cout << "\t\tashr\t\t";
// AC 시프트
for (int i = 0; i < q - 1; i++) {
ac[i] = ac[i + 1];
}
// QR 시프트
for (int i = 0; i < q - 1; i++) {
qr[i] = qr[i + 1];
}
qr[q - 1] = temp; // AC의 LSB가 QR의 MSB로 이동
}
// 레지스터 상태 출력 (MSB부터 출력)
void display(int ac[], int qr[], int qrn) {
for (int i = qrn - 1; i >= 0; i--) cout << ac[i];
cout << " ";
for (int i = qrn - 1; i >= 0; i--) cout << qr[i];
}
int main() {
int mt[10], br[10], qr[10], sc;
int ac[10] = {0}; // 누산기 초기화
int brn, qrn, i, qn = 0, temp = 0;
cout << "-- 부호 있는 2의 보수 형태로 입력하세요 (음수인 경우) --\n";
cout << "피승수 비트 수: ";
cin >> brn;
cout << "피승수 (LSB부터 입력): ";
for (i = brn - 1; i >= 0; i--) cin >> br[i];
// 피승수의 음수 값(MT) 미리 계산 (뺄셈용)
for (i = brn - 1; i >= 0; i--) mt[i] = br[i];
complement(mt, brn);
cout << "곱셈기 비트 수: ";
cin >> qrn;
sc = qrn; // 시프트 카운터
cout << "곱셈기 (LSB부터 입력): ";
for (i = qrn - 1; i >= 0; i--) cin >> qr[i];
cout << "\nqn\tq[n+1]\t\tBR\t\tAC\tQR\t\tsc\n";
cout << "\t\t\tinitial\t\t";
display(ac, qr, qrn);
cout << "\t\t" << sc << "\n";
// 메인 루프
while (sc != 0) {
cout << qr[0] << "\t" << qn;
// Qn과 Qn+1 비교 (qr[0]이 Qn, qn이 Qn+1)
if ((qn + qr[0]) == 1) { // 01 또는 10인 경우
if (temp == 0) { // 01: 덧셈 (AC + BR) -> 코드상 MT(음수) 더하기 = 뺄셈
add(ac, mt, qrn);
cout << "\t\tsubtracting BR\t";
temp = 1;
} else { // 10: 뺄셈 (AC - BR) -> 코드상 BR(양수) 더하기 = 덧셈
add(ac, br, qrn);
cout << "\t\tadding BR\t";
temp = 0;
}
for (i = qrn - 1; i >= 0; i--) cout << ac[i];
cout << "\n\t";
ashr(ac, qr, qn, qrn);
}
else if (qn - qr[0] == 0) { // 00 또는 11인 경우
ashr(ac, qr, qn, qrn);
}
display(ac, qr, qrn);
cout << "\t";
sc--;
cout << "\t" << sc << "\n";
}
cout << "Result= ";
display(ac, qr, qrn);
cout << endl;
return 0;
}실행 결과 예시
피승수 5비트(01111, +15), 곱셈기 5비트(10111, -9) 입력 시 결과입니다. 최종 결과 11011 11001은 2의 보수 형태의 -135를 나타냅니다.
-- 부호 있는 2의 보수 형태로 입력하세요 (음수인 경우) --
피승수 비트 수: 5
피승수 (LSB부터 입력): 0 1 1 1 1
곱셈기 비트 수: 5
곱셈기 (LSB부터 입력): 1 0 1 1 1
qn q[n+1] BR AC QR sc
initial 00000 10111 5
1 0 subtracting BR 10001
ashr 11000 11011 4
1 1 ashr 11100 01101 3
1 1 ashr 11110 00110 2
0 1 adding BR 01101
ashr 00110 10011 1
1 0 subtracting BR 10111
ashr 11011 11001 0
Result= 11011 11001코드 주요 포인트 정리
- 입력 순서: 코드 편의상 LSB(최하위 비트)부터 입력받아 배열 인덱스 0에 저장합니다.
- MT 배열: 피승수(BR)의 2의 보수(음수 값)를 미리 계산해 두어, 뺄셈이 필요할 때 덧셈 연산으로 대체합니다.
- Temp 변수: 부스 알고리즘의 부호 비트 전환(0→1, 1→0)을 추적하여 덧셈/뺄셈을 번갈아 수행하도록 제어합니다.
- ASHR: 부호 비트(MSB)를 유지하며 오른쪽으로 시프트하는 산술 시프트를 구현했습니다.