Booth's algorithm

High Speed Multiplication

곱셈 알고리즘을 더욱 빨리 수행하고 더욱 적은 자원을 사용해서 연산하는 방법에 대해 알아보자.

 multiplicand(피승수/A) x multiplier(승수/X) = product(결과물/U)를 연산할 때 parital product는 X에 존재하는 1의 개수만큼 반복된다.

이 과정에서 많은 시간이 소비되며 중간의 partial product를 구성하기 위해 많은 register가 사용된다.

따라서 위의 단점을 극복하기 위해 나온 연산방법이 Booth's algorithm이다.

만약 X가 15인 경우 1111로 표기되며 덧셈 연산을 4번 반복해야한다.

하지만 다음과 같이 표기하게 되면 어떻게 될까

1111 = 1_0000 - 0_0001

15 = 16 - 1로 표현하게 되면서 한 번의 뺄셈 연산으로 표기할 수 있게 되었다.

즉, 두 번의 partial product만이 생성된다.

이렇게 표기하는 방법을 SD code라고 하며 아래의 방식으로 SD code(Y)를 생성할 수 있다.

 

$x_{i}$	$x_{i-1}$	Operation	Comments	$y_{i}$
0	0	shift only	string of zeros	0
1	1	shift only	string of ones	0
1	0	subtract and shift	beginning of a string of ones	$\overline{1}$
0	1	add and shift	end of a string of ones	1

 

만약 X가 부호화 된 수라면 아래의 법칙에 따라 $y_{n-1}$가 정해지게 된다.

$x_{n-1}$	$x_{n-2}$	$y_{n-1}$
1	0	$\overline{1}$
1	1	0

 

위의 방식으로 -5 x 3을 연산해보자.

SD code 법칙에 따라 Y = 010$\overline{1}$이 된다.