Booth 곱셈기 설명(예제 포함)

기수 2 및 기수 4 Booth 재부호화를 배우고 -3 × 5를 단계별로 추적하며 반복형 하드웨어 곱셈기에서 발생하는 부호 있는 비트 폭 오류를 피하세요.

Denny

2026년 5월 7일약 7분 소요

Chalkboard feature illustration for “Booth 곱셈기 설명(예제 포함)”

요약: Booth 재부호화는 승수의 연속된 1 비트를 부호 있는 자릿값으로 다시 씁니다. 기수 2 Booth는 매 반복에서 $(Q_0,Q_{-1})$ 쌍을 봅니다. 01이면 피승수를 더하고, 10이면 피승수를 빼며, 00 또는 11이면 아무것도 하지 않은 뒤 산술 오른쪽 시프트를 합니다. 비트 폭이 안전한 $n$ 비트 구현은 피승수를 부호 확장하고 $(n+1)$ 비트 누산기를 사용하므로 최솟값에서 생기는 특수한 실패를 피합니다. 기수 4 수정 Booth는 $0,\pm M,\pm2M$ 가운데 하나를 선택해 부분곱 수를 약 절반으로 줄입니다.

이진 곱셈은 시프트와 덧셈으로 구성할 수 있습니다. 문제는 2의 보수 피연산자를 Booth 없이 곱할 수 없다는 데 있지 않습니다. 실제로는 가능합니다. 부호 처리와 부분곱 생성을 올바르게 설계해야 한다는 점이 핵심입니다.

Booth 방식은 균일한 부호 있는 재부호화를 제공하고 연속된 1을 압축합니다. 이는 서로 다른 두 아키텍처에서 유용합니다.

여러 사이클에 걸쳐 하나의 가산기를 재사용하는 반복형 곱셈기
재부호화된 부분곱을 만들고 가산기/압축기 트리로 줄이는 병렬 곱셈기

두 아키텍처는 재부호화라는 발상을 공유하지만, 지연 시간, 면적, 타이밍은 다릅니다.

연속된 1의 항등식

비트 $j$ 부터 비트 $k$ 까지( $k\ge j$ ) 이진수 1이 연속되어 있다고 합시다.

2^j + 2^{j+1} + \cdots + 2^k = 2^{k+1} - 2^j

예를 들면 다음과 같습니다.

001111_2 = 010000_2 - 000001_2

일반적인 부호 없는 시프트-가산 방식은 1111에 대해 피승수의 시프트된 복사본 네 개를 더합니다. Booth 재부호화는 연속 구간의 하위 경계에서 뺄셈을 하고 상위 경계 바로 위 위치에서 덧셈을 하여 이 연속 구간을 나타냅니다.

이 방법이 모든 비트 패턴에서 0이 아닌 연산 수를 줄인다는 보장은 없습니다. 긴 연속 구간에는 이롭지만, 고립된 1이나 1과 0이 번갈아 나오는 패턴에서는 줄어들지 않으며 가감산 결정 수가 늘 수도 있습니다. 고정 지연 시간의 기수 2 반복형 곱셈기는 여전히 $n$ 번 반복합니다. 재부호화는 각 반복 안의 산술 동작을 바꾸는 것이지, 사이클 수를 자동으로 줄이는 것은 아닙니다.

기수 2 Booth 재부호화

승수 아래에 묵시적인 0을 하나 붙입니다.

Q_{-1}=0

반복 $i$ 에서 현재 최하위 승수 비트 $Q_0$ 와 저장된 이전 비트 $Q_{-1}$ 를 살펴봅니다.

$Q_0$	$Q_{-1}$	누산기 동작
0	0	변화 없음
0	1	$M$ 더하기
1	0	$M$ 빼기
1	1	변화 없음

그런 다음 누산기, 승수, 저장 비트를 이어 붙인 전체를 한 비트만큼 산술 오른쪽 시프트합니다.

이 쌍은 경계를 검출합니다.

10은 연속된 1의 하위 끝을 표시하므로 뺍니다.
01은 연속 구간을 지나 시프트한 뒤의 상위 끝을 표시하므로 더합니다.
인접한 두 비트가 같으면 일정한 구간 내부이므로 산술 동작이 필요 없습니다.

표의 비트 순서는 중요합니다. 어떤 문헌은 $(Q_{-1},Q_0)$ 로 인쇄하므로 행 레이블이 반대가 됩니다. 항상 사용하는 규약을 명시하세요.

비트 폭이 안전한 반복형 데이터패스

두 입력 피연산자가 모두 부호 있는 $n$ 비트 2의 보수 값이라고 합시다.

$M$ : 피승수
$Q$ : 승수

다음을 사용합니다.

$M_e$ : $M$ 을 $n+1$ 비트로 부호 확장한 값
$A$ : 초깃값이 0인 $n+1$ 비트 누산기
$Q$ : $n$ 비트 승수 레지스터
$Q_{-1}$ : 초깃값이 0인 저장 비트 하나
0부터 $n-1$ 까지 세는 반복 카운터

$n$ 번의 각 반복에서 다음을 수행합니다.

$(Q_0,Q_{-1})$ 를 확인합니다.
01이면 $A \leftarrow A+M_e$ 로 설정합니다.
10이면 $A \leftarrow A-M_e$ 로 설정합니다.
00 또는 11이면 $A$ 를 그대로 둡니다.
연결한 $\{A,Q,Q_{-1}\}$ 를 한 비트만큼 산술 오른쪽 시프트합니다.

$n$ 번 반복한 뒤 $A$ 의 중복된 최상위 부호 확장 비트를 버립니다. 남은 $A$ 의 $n$ 비트와 $Q$ 를 이어 붙이면 부호 있는 $2n$ 비트 곱이 됩니다.

누산기에 추가 비트가 중요한 이유

$n$ 비트 2의 보수 수가 표현할 수 있는 범위는 다음과 같습니다.

-2^{n-1} \le x \le 2^{n-1}-1

$-2^{n-1}$ 의 양의 크기는 $n$ 비트에 들어가지 않습니다. 따라서 $n$ 비트만으로 -M을 미리 계산하는 설계는 $M$ 이 가장 작은 음수일 때 실패할 수 있습니다. $M$ 을 부호 확장하고 $(n+1)$ 비트 누산기를 사용하면 알고리즘 진행 중 $M_e$ 와 $-M_e$ 모두 표현할 수 있습니다.

예제: $-3 \times 5$

4비트 피연산자를 사용합니다.

M=-3=1101_2,\qquad Q=5=0101_2

피승수를 5비트로 부호 확장합니다.

M_e=11101_2

초기화합니다.

A=00000,\quad Q=0101,\quad Q_{-1}=0

표는 쌍과 시프트 전 산술 동작을 보여 준 뒤, 연결된 산술 오른쪽 시프트를 수행한 뒤의 상태를 나타냅니다.

반복	쌍 $(Q_0,Q_{-1})$	시프트 전 동작	시프트 후 $A$	시프트 후 $Q$	$Q_{-1}$
초기	—	—	`00000`	`0101`	`0`
1	`10`	$A-M_e=00011$	`00001`	`1010`	`1`
2	`01`	$A+M_e=11110$	`11111`	`0101`	`0`
3	`10`	$A-M_e=00010$	`00001`	`0010`	`1`
4	`01`	$A+M_e=11110$	`11111`	`0001`	`0`

네 번 반복한 뒤 $A$ 의 중복된 상위 부호 비트를 버립니다.

A[3:0]\;||\;Q = 1111\;0001_2

이를 8비트 2의 보수 값으로 해석하면 다음과 같습니다.

11110001_2=-15

이는 $-3\times5$ 와 일치합니다.

연결된 시프트 하나 추적하기

첫 번째 뺄셈 뒤에는 다음과 같습니다.

\{A,Q,Q_{-1}\} = \{00011,\ 0101,\ 0\}

산술 오른쪽 시프트는 누산기 부호 비트를 새 최상위 위치로 복사하고 나머지 모든 비트를 한 자리씩 옮깁니다.

\{00001,\ 1010,\ 1\}

시프트는 연결된 전체 레지스터에 작용해야 합니다. $A$ 와 $Q$ 를 따로 시프트하면 경계를 가로지르는 비트 전달이 사라집니다.

하드웨어 블록

재사용 가능한 반복형 Booth 곱셈기는 다음으로 구성됩니다.

$(n+1)$ 비트 피승수 레지스터 또는 입력 경로
$(n+1)$ 비트 누산기
$Q_{-1}$ 을 포함하는 $n$ 비트 승수 레지스터
$(n+1)$ 비트 가산기/감산기
add, subtract, hold를 위한 쌍 디코드 제어
연결된 산술 시프터
반복 카운터와 busy/done 제어

가산기는 모든 반복에서 재사용되므로 완전 병렬 곱셈기보다 면적을 절약하는 대신 지연 시간이 듭니다. 반복 하나가 한 클록에 끝나는지 여러 마이크로스텝이 필요한지는 제어기와 데이터패스에 따라 달라집니다.

ALU 구성 요소는 교육용 회로에 가감산 동작을 제공할 수 있지만, 비트 폭과 부호 있는 오버플로 동작을 확인해야 합니다. 시프트 레지스터는 직렬 이동을 보여 주지만, Booth 데이터패스에는 상위 비트를 부호로 채우는 더 넓은 연결 레지스터가 필요합니다.

기수 4 수정 Booth

기수 4 수정 Booth는 겹치는 3비트 윈도를 살펴 두 승수 비트를 자릿값 하나로 재부호화합니다. 하위 끝에는 0을 붙이고, 필요에 따라 상위 끝에서는 승수를 부호 확장합니다.

윈도 $(Q_{2i+1},Q_{2i},Q_{2i-1})$ 에 대해 다음과 같습니다.

윈도	재부호화된 배수
`000`	$0$
`001`	$+M$
`010`	$+M$
`011`	$+2M$
`100`	$-2M$
`101`	$-M$
`110`	$-M$
`111`	$0$

사용 가능한 배수는 다음과 같습니다.

\{0,\ +M,\ -M,\ +2M,\ -2M\}

$2M$ 은 왼쪽 시프트이므로 이 부분곱들은 비교적 경제적으로 만들 수 있습니다. $n$ 비트 승수에서 기수 4는 $n$ 개의 기수 2 자릿값 대신 약 $\lceil n/2\rceil$ 개의 재부호화 자릿값을 만듭니다.

이 감소는 다음을 가능하게 합니다.

반복형 기수 4 설계에서 반복 횟수를 절반으로 줄이기
병렬 설계에서 부분곱 행 수 줄이기

그렇다고 전체 곱셈기가 자동으로 두 배 빨라지는 것은 아닙니다. 재부호화, 부호 보정, 부분곱 생성, 축소, 배선, 최종 덧셈, 파이프라이닝이 모두 타이밍에 기여합니다.

병렬 축소: Wallace, Dadda 및 최종 가산기

고처리량 곱셈기는 부분곱을 병렬로 만들고, 캐리 세이브 압축기로 각 열을 줄인 뒤, 캐리 전파 가산기로 마무리할 수 있습니다.

Wallace 트리와 Dadda 트리는 대표적인 두 가지 축소 일정입니다. 수정 Booth 재부호화를 이런 트리 앞에 배치해 행 수를 줄일 수 있습니다. 최종 가산기는 목표 기술에 맞춰 캐리 예측, 병렬 접두사, 캐리 선택 또는 다른 구조를 선택할 수 있습니다.

‘조합 회로’가 반드시 ‘프로세서 한 사이클’을 뜻하는 것은 아닙니다. 넓은 곱셈기는 목표 클록 주기를 맞추기 위해 여러 단계로 파이프라이닝될 수 있으며, 일부 프로세서는 면적이나 전력 때문에 반복형 유닛을 사용합니다. 아키텍처는 구현 선택입니다.

Booth와 다른 곱셈기 구조 비교

접근 방식	부호 있는 연산	부분곱 또는 사이클 수	일반적인 트레이드오프
기본 반복형 시프트/가산	올바른 부호 처리 시 가능	보통 $n$ 회 반복	작은 데이터패스, 단순한 제어
기수 2 반복형 Booth	기본 제공되는 2의 보수 재부호화	$n$ 회 반복	균일한 부호 알고리즘, 가산/감산/건너뜀
기수 4 반복형 Booth	기본 제공되는 2의 보수 재부호화	약 $\lceil n/2\rceil$ 회 반복	더 복잡한 디코드/배수 선택
병렬 부분곱 배열/트리	부호 있음 또는 없음 변형	행을 동시에 처리	더 많은 하드웨어, 파이프라이닝 가능
기수 4 Booth와 축소 트리	기본 제공되는 부호 재부호화	초기 행 수가 약 절반	일반적인 고성능 설계 선택지

보편적으로 우세한 방식은 없습니다. 피연산자 비트 폭, 목표 셀 또는 FPGA 자원, 처리량, 지연 시간, 면적, 전력, 검증 노력이 적절한 구조를 결정합니다.

DigiSim에서 만들기

4비트 교육용 구현에서는 다음을 수행합니다.

눈에 보이는 저장 소자로 5비트 누산기를 만듭니다.
4비트 피승수를 5비트로 부호 확장합니다.
5비트 가감산 경로를 사용합니다.
4비트 승수와 별도의 $Q_{-1}$ 비트를 저장합니다.
(Q0, Q−1)을 add, subtract, hold로 디코드합니다.
전체 {A,Q,Q−1} 상태에 걸쳐 산술 시프트를 구현합니다.
정확히 네 번 반복을 셉니다.
busy, done, 최종 8비트 곱을 노출합니다.

$-3\times5$ 표를 한 단계씩 따라가며 모든 시프트 후 상태를 비교하세요. 첫 반복에서 불일치하면 대개 쌍 순서를 뒤집었거나 뺄셈 극성을 잘못 정한 것입니다. 음수 누산기를 시프트한 뒤 불일치하면 대개 산술 시프트 대신 논리 시프트를 쓴 것입니다.

검증 점검표

작은 $n$ 비트 곱셈기를 완전 검증하려면 다음 모든 경우를 검사합니다.

2^n \times 2^n = 2^{2n}

입력 쌍을 $2n$ 비트로 표현한 부호 있는 기준 곱과 대조합니다.

최소한 다음을 포함하세요.

$0\times x$ 및 $1\times x$
양수 × 양수
양수 × 음수
음수 × 양수
음수 × 음수
최댓값 양수
가장 작은 음수 $-2^{n-1}$
$-2^{n-1}\times -1$
승수 패턴 0000, 1111, 0101, 1010
busy 상태에서 리셋 또는 재시작

또한 다음을 단언하세요.

정확히 $n$ 회의 기수 2 반복이 발생합니다.
수락된 연산 하나마다 done이 한 번만 발생합니다.
입력은 래치되거나 계약상 안정적으로 유지되어야 합니다.
결과가 유효해지기 전에 소비되지 않습니다.
연결된 시프트가 누산기 부호를 보존합니다.

이상적인 기능 시뮬레이션은 산술 순서를 증명할 뿐, 최대 하드웨어 클록 속도를 증명하지는 않습니다. 설계를 목표에 매핑한 뒤 정적 타이밍 분석을 사용하세요.

계속 학습하기

부호 확장과 범위는 2의 보수 산술에서 복습한 뒤, 리플 캐리 덧셈과 캐리 예측 구조를 비교해 보세요.

Andrew D. Booth는 1951년 논문 “부호 있는 이진 곱셈 기법”에서 이 균일한 부호 방식을 소개했습니다. 핵심 재부호화는 지금도 유효하지만, 전문적인 구현에는 여전히 명시적인 비트 폭, 정의된 지연 시간 계약, 완전한 부호 검증, 목표별 타이밍 분석이 필요합니다.