부스 알고리즘

부스 알고리즘 또는 부스 곱셈 알고리즘(Booth's multiplication algorithm)은 2의 보수 표기법으로 표현된 부호 있는 이진수 두 개를 곱하는 곱셈 알고리즘이다. 이 알고리즘은 1950년 앤드루 도널드 부스가 런던 블룸즈버리의 버크벡 칼리지에서 결정학을 연구하던 중 발명했다.^[1] 부스 알고리즘은 컴퓨터 구조 연구에서 중요한 관심사이다.

알고리즘

부스 알고리즘은 'N' 비트 승수 Y의 인접한 비트 쌍을 부호 있는 2의 보수 표현으로 검사하며, 이에는 최하위 비트 아래의 암시적 비트, y₋₁ = 0이 포함된다. i가 0부터 N − 1까지 실행되는 각 비트 y_i에 대해 비트 y_i와 y_i−1이 고려된다. 이 두 비트가 같을 경우, 곱 누산기 P는 변경되지 않는다. y_i = 0이고 y_i−1 = 1일 경우, 피승수 곱하기 2ⁱ가 P에 더해진다. 그리고 y_i = 1이고 y_i−1 = 0일 경우, 피승수 곱하기 2ⁱ가 P에서 빼진다. P의 최종 값은 부호 있는 곱이다.

피승수와 곱의 표현은 지정되지 않는다. 일반적으로 이들은 승수와 마찬가지로 2의 보수 표현이지만, 덧셈과 뺄셈을 지원하는 모든 숫자 시스템도 잘 작동한다. 여기서 언급된 대로 단계의 순서는 결정되지 않는다. 일반적으로 최하위 비트에서 최상위 비트로 진행되며, i = 0에서 시작한다. 2ⁱ를 곱하는 것은 일반적으로 단계 사이에 P 누산기를 오른쪽으로 점진적으로 이동하는 것으로 대체된다. 낮은 비트는 시프트될 수 있으며, 이후의 덧셈과 뺄셈은 P의 최상위 N 비트에서만 수행될 수 있다.^[2] 이러한 세부 사항에는 많은 변형과 최적화가 있다.

이 알고리즘은 종종 승수의 1의 문자열을 문자열 끝에 고위 +1과 저위 -1로 변환하는 것으로 설명된다. 문자열이 MSB를 통과할 때 고위 +1은 없으며, 순 효과는 적절한 값의 음수로 해석된다.

일반적인 구현

1960년의 발터 WSR160 계산기. 크랭크 손잡이를 한 번 돌릴 때마다 위쪽 레지스터에 설정된 피연산자가 아래쪽 누산기 레지스터의 값에 더해지거나(위) 빼진다(아래). 산술 시프트를 왼쪽이나 오른쪽으로 하면 효과가 10배가 된다.

부스 알고리즘은 두 개의 미리 정해진 값 A와 S 중 하나를 곱 P에 반복적으로 더한(일반적인 부호 없는 이진 덧셈으로) 다음 P에 오른쪽으로 산술 시프트를 수행하여 구현할 수 있다. m과 r을 각각 피승수와 승수라고 하고, x와 y를 m과 r의 비트 수라고 하자.

1. A와 S의 값, 그리고 P의 초기 값을 결정한다. 이 모든 숫자는 (x + y + 1)과 같은 길이를 가져야 한다.
   1. A: 최상위(가장 왼쪽) 비트를 m의 값으로 채운다. 나머지 (y + 1) 비트는 0으로 채운다.
   2. S: 최상위 비트를 2의 보수 표기법의 (−m) 값으로 채운다. 나머지 (y + 1) 비트는 0으로 채운다.
   3. P: 최상위 x 비트를 0으로 채운다. 이 오른쪽에는 r의 값을 추가한다. 최하위(가장 오른쪽) 비트를 0으로 채운다.
2. P의 최하위(가장 오른쪽) 두 비트를 결정한다.
   1. 01이면 P + A 값을 찾는다. 오버플로는 무시한다.
   2. 10이면 P + S 값을 찾는다. 오버플로는 무시한다.
   3. 00이면 아무것도 하지 않는다. 다음 단계에서 P를 직접 사용한다.
   4. 11이면 아무것도 하지 않는다. 다음 단계에서 P를 직접 사용한다.
3. 두 번째 단계에서 얻은 값을 오른쪽으로 한 자리 산술 시프트한다. P는 이제 이 새로운 값과 같다고 하자.
4. 2단계와 3단계를 y번 반복한다.
5. P에서 최하위(가장 오른쪽) 비트를 버린다. 이것이 m과 r의 곱이다.

예시

m = 3, r = -4, x = 4, y = 4일 때, 3 × (-4)를 구한다.

• m = 0011, -m = 1101, r = 1100
• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0
• 루프를 네 번 수행한다.
  1. P = 0000 1100 0. 마지막 두 비트는 00이다.
     • P = 0000 0110 0. 산술 오른쪽 시프트.
  2. P = 0000 0110 0. 마지막 두 비트는 00이다.
     • P = 0000 0011 0. 산술 오른쪽 시프트.
  3. P = 0000 0011 0. 마지막 두 비트는 10이다.
     • P = 1101 0011 0. P = P + S.
     • P = 1110 1001 1. 산술 오른쪽 시프트.
  4. P = 1110 1001 1. 마지막 두 비트는 11이다.
     • P = 1111 0100 1. 산술 오른쪽 시프트.
• 곱은 1111 0100이며, 이는 -12이다.

위에서 언급된 기술은 피승수가 표현할 수 있는 가장 음수적인 숫자일 때 부적절하다(예: 피승수가 4비트이면 이 값은 -8이다). 이는 S를 설정하는 데 필요한 피승수의 음수 -m을 계산할 때 오버플로가 발생하기 때문이다. 이 문제에 대한 가능한 해결책 중 하나는 A, S, P를 각각 한 비트씩 확장하면서도 동일한 숫자를 나타내도록 하는 것이다. 즉, -8이 이전에는 4비트로 1000으로 표현되었지만, 이제는 5비트로 1 1000으로 표현된다. 이는 A와 S의 비트를 결정하는 데 약간의 수정이 가해지지만, 위에서 설명된 구현을 따른다. 예를 들어, 원래 A의 첫 x 비트에 할당된 m의 값은 이제 x+1 비트로 확장되어 A의 첫 x+1 비트에 할당된다. 아래에서는 피승수와 승수에 4비트를 사용하여 -8을 2로 곱함으로써 개선된 기술이 시연된다.

• A = 1 1000 0000 0
• S = 0 1000 0000 0
• P = 0 0000 0010 0
• 루프를 네 번 수행한다.
  1. P = 0 0000 0010 0. 마지막 두 비트는 00이다.
     • P = 0 0000 0001 0. 오른쪽 시프트.
  2. P = 0 0000 0001 0. 마지막 두 비트는 10이다.
     • P = 0 1000 0001 0. P = P + S.
     • P = 0 0100 0000 1. 오른쪽 시프트.
  3. P = 0 0100 0000 1. 마지막 두 비트는 01이다.
     • P = 1 1100 0000 1. P = P + A.
     • P = 1 1110 0000 0. 오른쪽 시프트.
  4. P = 1 1110 0000 0. 마지막 두 비트는 00이다.
     • P = 1 1111 0000 0. 오른쪽 시프트.
• 곱은 11110000 (첫 비트와 마지막 비트를 버린 후)이며, 이는 -16이다.

작동 방식

0으로 둘러싸인 1의 블록으로 구성된 양수 승수를 생각해 보자. 예를 들어, 00111110이다. 곱은 다음과 같이 주어진다. $${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&0&1&1&1&1&1&0\\\hline \end{array}}=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62}$$ 여기서 M은 피승수이다. 같은 식을 다음과 같이 다시 작성하여 연산 수를 두 개로 줄일 수 있다. $${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&1&0&0&0&0&-1&0\\\hline \end{array}}=M\times (2^{6}-2^{1})=M\times 62.}$$

실제로 이진수에서 1의 모든 시퀀스는 두 이진수의 차이로 분해될 수 있음을 보일 수 있다.

$${\displaystyle (\ldots 0\overbrace {1\ldots 1} ^{n}0\ldots )_{2}\equiv (\ldots 1\overbrace {0\ldots 0} ^{n}0\ldots )_{2}-(\ldots 0\overbrace {0\ldots 1} ^{n}0\ldots )_{2}.}$$

따라서 곱셈은 실제로는 원래 숫자의 1의 문자열을 더 간단한 연산으로 대체할 수 있다. 즉, 피승수를 더하고, 이렇게 형성된 부분 곱을 적절한 위치로 시프트한 다음, 마지막으로 피승수를 빼는 것이다. 이는 이진 승수에서 0을 다룰 때 시프트 외에는 아무것도 할 필요가 없다는 사실을 활용하며, 99를 곱할 때 99 = 100 - 1이라는 수학적 속성을 사용하는 것과 유사하다.

이 방식은 승수의 1의 블록 수에 관계없이 확장될 수 있다(블록에 1이 하나만 있는 경우 포함). 따라서,

$${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&0&1&1&1&0&1&0\\\hline \end{array}}\ =M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58}$$ $${\displaystyle M\times {\begin{array}{|r|r|r|r|r|r|r|r|}\hline 0&1&0&0&-1&1&-1&0\\\hline \end{array}}=M\times (2^{6}-2^{3}+2^{2}-2^{1})=M\times 58.}$$

부스 알고리즘은 1의 블록의 첫 번째 숫자를 만나면 (0 1) 덧셈을 수행하고, 블록의 끝을 만나면 (1 0) 뺄셈을 수행하여 이 오래된 방식을 따른다. 이것은 음수 승수에도 작동한다. 승수의 1이 긴 블록으로 그룹화될 때, 부스 알고리즘은 일반적인 곱셈 알고리즘보다 더 적은 덧셈과 뺄셈을 수행한다.

펜티엄 곱셈기 구현

인텔의 펜티엄 마이크로프로세서는 64비트 하드웨어 곱셈기에서 부스 알고리즘의 8진수 변형을 사용한다. 8진수 곱셈을 구현하는 방식 때문에, 대기 시간을 최소화하는 방식으로 3을 곱하는 특수 사례를 수행하기 위해 복잡한 보조 회로가 필요하며, 자리올림수 예측 가산기, 자리올림수 선택 가산기, 코지-스톤 가산기의 사용을 결합한다.^[3]

같이 보기

• 곱셈기
• 비인접 형태
• 잉여 이진 표현
• 월레스 트리
• 다다 곱셈기