Booth Algorithm이란?
partial sum algorith보다 적은 HW 자원과 적은 operation을 사용하여 multiplication을 구현하는 방법이다.
Andrew Donald Booth 씨가 1950년에 고안한 방법
두 개의 signed binary number를 곱하는 알고리즘이다. (2's complement notation)
Booth's multiplication algorithm - Wikipedia
Binary Multiplication을 구현하는 알고리즘 중에서 우리에게 가장 친숙한 것은 Partial Sum Approach이다.
따라서 Partial Sum Approach를 먼저 살펴본다.
그 전에, 이진 곱셈을 위한 용어를 먼저 정리해보자!!
M x Q = U 라고 할때,
M은 Multiplicand
Q는 Multiplier
U는 output이 되겠다.
보통 곱셈은 교환법칙이 성립하여 M과 Q의 구분을 하지 않지만
영어권에서는 이를 구분한다.
피승수를 M Multiplicand라고하고
승수를 Q, Multiplier라고 한다.
Partial Sum Approach
Partial Sum Approach는 말그대로 Multiplicand를 Multiplier에서 값이 1인 비트 수 만큼 더하는 방식이다.
예를 들어 01011 x 01110 을 한다고 하면
01011 (Multiplicand)를 자릿수에 맞춰 3 번 더하게된다.
0 1 0 1 1
x 0 1 1 1 0
-----------------------
0 0 0 0 0
0 1 0 1 1
0 1 0 1 1
0 1 0 1 1
0 0 0 0 0
------------------------ 이렇게 3 개의 덧셈을 하게 된다.
0 1 0 0 1 1 0 1 0
그러므로 Partial Sum Approach에서는 최대 Multiplier의 bit 수만큼 덧셈을 하게된다.
Booth Algorithm
Booth Algorithm의 핵심은 연속된 1을 2의 승수만으로 표현할 수 있다는 것이다.
예를 들어 111은 1000 - 1 이다
01110은 10000 - 10이다
11011은 100000- 10000 + 100 - 1
위 표현 방식을 일반화 해볼까?
01110은
2^3 + 2^2 + 2^1 이다
이는 2^4 - 2^1 이다
이는 2^j+1 - 2 ^ i이다.
j 는 연속된 1이 시작되는 가장 높은 자리수
i 는 연속된 1이 끝나는 가장 낮은 자리수이다.
그리고 Booth Algorith에선 Multiplier를 위처럼 2의 승수만으로 표현한다.
예시를 보면 더 이해하기 쉽다.
예시로 보는 Booth's Multiplication Algorithm
M : 01011
Q : 01110
Q의 새로운 표현 10000 - 10
좀더 일반화를 하자면 2^4 - 2^1 이다.
따라서 M x Q는
2^4(M) - 2^1(M)이다.
2's complement에서 -M을 M'라고 해보자. M' = 10101이 된다.
따라서 MxQ = 2^4(M) + 2^1(M')가 된다.
자 어떤가?! Partial Sum에서는 3번의 덧셈 연산이 있었는데,
Booth's Algorithm에서는 단 2번의 덧셈 연산(한번은 2's complement 변환시 1 덧셈)과 arithmetic shift 연산만 있으면 된다. 복잡도가 훨씬 낮다.
다시 표현해보자면
MxQ = M <<4 + M' <<1 이 된다.
Booth's Algorithm의 구현
Booth Algorithm 구현을 위해서는
- Multiplier를 위한 5 bit register
- Multiplicand를 위한 5 bit register
- 누적 sum을 저장하기 위한 Accum이란 5 bit register
- Multiplier의 마지막 bit를 delay시켜 저장할 1 bit flipflop
register 설명
아래처럼 5bit + 5bit + 1bit 짜리 register 안에서 모든 연산을 수행할 것이다.
최종 결과는 Accum 5bit과 Multiplier 5bit을 이어붙인 것이 된다.
Q_-1는 Multiplier Q의 마지막 bit가 right shift 될 때마다 hold되는 플립플롭이다.
| Accumulator | Multiplier | Q_-1 | ||||||||
| Q_4 | Q_3 | Q_2 | Q_1 | Q_0 | ||||||
operation 설명
Booth's Algorithm 구현에서는 총 Multiplier의 bit 수 만큼 Arithmetic Right Shift를 해가며 연산을 수행할 것이다.
각 round에는 ARS가 꼭 있다.
각 round마다 수행할 operation은 Q의 0번bit와 -1번 비트가 결정한다.
{Q_0, Q_-1 } 이 00이거나 11인 경우는 위에 예제에서 봤을 때처럼 0이 연속이거나 1이 연속인 부분이다.
따라서 조용히 right shift만 하고 넘긴다
{Q_0, Q_-1 } 이 10 일 때는 2^i 를 빼주는 구간이다.
따라서 Accum = Accum + M'를 하고 ARS를 해준다.
{Q_0, Q_-1 } 이 01 일 때는 2^j+1 를 더해주는 구간이다.
따라서 Accum = Accum + M를 하고 ARS를 해준다.
| Q_0 | Q_-1 | Operation |
| 0 | 0 | Arithmetic Right Shift |
| 0 | 1 | Accum = Accum + M , ARS |
| 1 | 0 | Accum = Accum + M' , ARS |
| 1 | 1 | Arithmetic Right Shift |
step by step 설명
step1 초기화
| Accumulator | Multiplier | Q_-1 | ||||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
Accum 과 Q_-1은 0으로 초기화 해준다.
step 2 연산
round1)
Q_0 , Q_-1이 00 이므로 ARS
| Accumulator | Multiplier | Q_-1 | ||||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
round2)
Q_0 , Q_-1이 10 이므로 Accum = Accum + M' , ARS
M' = 10101
i) Accum = Accum + M'
| Accumulator | Multiplier | Q_-1 | ||||||||
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
ii) ARS
| Accumulator | Multiplier | Q_-1 | ||||||||
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
주의할 점은 Arithmetic Right Shift에서는 sign bit가 유지된다는 점이다.
round3)
Q_0 , Q_-1이 11 이므로 ARS
| Accumulator | Multiplier | Q_-1 | ||||||||
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
round4)
Q_0 , Q_-1이 11 이므로 ARS
| Accumulator | Multiplier | Q_-1 | ||||||||
| 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
round5) Multiplier가 5bit 이므로 마지막 round이다.
Q_0 , Q_-1이 01 이므로 Accum = Accum + M, ARS
i) Accum = Accum + M
| Accumulator | Multiplier | Q_-1 | ||||||||
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
ii) ARS
| Accumulator | Multiplier | Q_-1 | ||||||||
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
최종 연산 결과는 Accumulator와 Multiplier 두 개의 연속 레지스터가 된다.
따라서 0010011010
Partial Sum의 결과와 똑같다