제이시스의 게으른 블로그...

컴퓨터 구조 수업을 듣다가 ALU 부분에서 곱셈에 대해 배울때 조사했던 Booth's algorithm에 대한 정리입니다.

기본적인 곱셈의 경우 multiflier의 해당 자리수가 multiflicant를 product에 더해주고 0일 경우 0을 더해준뒤 1bit left shift를 해주고 난뒤 multiflier의 다음 자리수를 0,1인지 비교하여 product에 더해주게 된다
1010 * 1001 일 경우(부호비트 생략)

     0110  (6)
  * 1001  (9)
     0110
    0000
   0000
  0110
  0110110
이런식으로 구하게 되며 자리수 만큼의 반복을 거쳐야 계산이 완료하게 된다 지금의 경우는 양의 정수끼리의 곱셈이며 음의 정수일 경우 부호비트에 대한 처리를 따로 해줘야한다.

이것을 좀더 빠르게 하기위해 나온 것이 Booth's algorithm이다. Booth's algorithm은 음수와의 곱셈을 지원하며 한번에 2bit씩 left shift를 하며 반복 횟수를 줄여주게 된다. Booth's algorithm은 multiflier의 맨오른쪽 bit 오른쪽에 0이 하나 더 붙이고 1자리씩 겹치게 3자리로 끈어서 Booth's Table에 대입한다

Booth's Table
011      2     multiflicant를 1bit left shift 시킨다음 product에 더해준다
010      1     multiflicant를 product에 더해준다
001      1     multiflicant를 product에 더해준다
000      0     0을 product에 더해준다
111      0     0을 product에 더해준다
110     -1    multiflicant를 2의보수로 변경한 다음 product에 더해준다
101     -1    multiflicant를 2의보수로 변경한 다음 product에 더해준다
100     -2    multiflicant를 2의보수로 변경한 다음1bit left shift 시킨다음 product에 더해준다

위의 문제를 여기에 맞춰서 풀어준다면
0110*1001(첫자리를 부호비트로 생각)      (6)*(-7)

multiflier를 끈어주어야한다
1001에 0을 하나더 붙여서 10010으로 만들고 1자리씩 겹치게 3자리로 끈는다.
1 0|0|1 0
100 010 2개가 나오게 된다

이것을 booth's table에 대입하게 되면
100 010
-2   1
이며 연산은 오른쪽에서 왼쪽으로 간다

처음은 1이므로 multiflicant를 product에 더해주면 된다
0000+0110
product:0110

2bit left shift를 한다.

다음은 -2이므로 multiflicant를 2의보수로 변경한 다음1bit left shift 시킨다음 product에 더해준다
0000110+1010000
product:1010110 (-42)
6*(-7)=-42
위와 같은 결과가 나오게 된다
위쪽에선 4번의 반복으로 나왔던 결과가  2번의 반복으로 가능하며, 부호비트가 있는 데이터의 연산이 가능하게 됩니다