부스의 곱셈 알고리즘

부스의 곱셈 알고리즘은 2의 보완 표기법으로 서명된 2진수 2개를 곱한 곱셈 알고리즘이다.이 알고리즘은 1950년 앤드류 도널드 부스가 런던 블룸즈버리의 버크벡 대학에서 결정학에 대한 연구를 하던 중 발명했다.^[1]부스의 알고리즘은 컴퓨터 건축학 연구에 관심이 있다.

알고리즘

부스의 알고리즘은 서명된 두 개의 보완 표현에서 'N'비트 곱셈기 Y의 인접 비트 쌍을 검사하며, 여기에는 최소 중요 비트인 y₋₁ = 0 미만의 암묵적 비트가 포함된다.각 비트 y에_i 대해, 0에서 N - 1까지 실행되는 i의 경우, 비트_i y와_i−1 y가 고려된다.이 두 비트가 동일한 경우, 제품 축전지 P는 변경되지 않은 상태로 남는다.여기서 y_i = 0, y_i−1 = 1이면 곱셈 2가 P에 추가되고ⁱ, y_i = 1과 y_i−1 = 0이면 곱셈 2는ⁱ P에서 뺀다.P의 최종 가치는 서명된 제품이다.

곱셈드와 제품의 표현은 명시되지 않는다. 전형적으로, 이것들은 둘 다 곱셈과 같이 두 개의 보완적 표현에도 있다. 그러나 덧셈과 뺄셈을 지원하는 모든 숫자 시스템도 또한 작동할 것이다.여기에 기술한 바와 같이, 스텝의 순서는 정해지지 않았다.일반적으로, 그것은 LSB에서 MSB로 진행되며, i = 0에서 시작한다. 그리고 나서 곱하기 2는ⁱ 일반적으로 P 축전지의 단계 사이의 우측으로 증분 이동으로 대체된다. 낮은 비트는 이동할 수 있으며, 이후 추가와 소급은 P의 가장 높은 N비트에서만 수행될 수 있다.^[2]이 세부사항에는 많은 변수와 최적화가 있다.

알고리즘은 흔히 승수에서 1초의 문자열을 고차 +1과 저차 -1로 변환하는 것으로 설명된다.문자열이 MSB를 통과하면 고차 +1이 없고, 순효과는 적절한 값의 음수로 해석된다.

일반적인 구현

1960년의 월터 WSR160 아리스미터.크랭크 핸들의 각 회전은 하단에 있는 축전지 레지스터의 값에서 상단 레지스터에 설정된 피연산자를 추가(상향)하거나 빼(하향)한다.덧셈을 왼쪽이나 오른쪽으로 돌리면 효과가 10배 증가한다.

부스의 알고리즘은 제품 P에 미리 결정된 두 가지 값 중 하나를 (일반적으로 부호 없는 이항 첨가로) 반복적으로 추가한 다음, P에 우향 산술 시프트를 수행하면 구현할 수 있다.m과 r을 각각 승수와 승수가 되게 하고 x와 y는 m과 r의 비트 수를 나타내도록 한다.

A와 S의 값과 P의 초기 값을 결정한다.이 모든 숫자는 길이가 (x + y + 1)이어야 한다.
1. A: 가장 유의한(맨 왼쪽) 비트를 m 값으로 채운다.나머지(y + 1) 비트를 0으로 채우십시오.
2. S: 두 개의 보완 표기법으로 가장 유의한 비트를 (-m) 값으로 채운다.나머지(y + 1) 비트를 0으로 채우십시오.
3. P: 가장 유의한 x 비트를 0으로 채우십시오.이 오른쪽에 r 값을 추가한다.중요도가 가장 낮은(가장 오른쪽) 비트를 0으로 채우십시오.
P의 최소(가장 오른쪽) 비트 두 개를 결정한다.
1. 01일 경우 P + A 값을 구하십시오.오버플로를 무시하십시오.
2. 10이면 P + S 값을 찾으십시오. 오버플로는 무시하십시오.
3. 그들이 00이라면 아무것도 하지 마라.다음 단계에서 P를 직접 사용하십시오.
4. 그들이 11살이라면 아무것도 하지 마라.다음 단계에서 P를 직접 사용하십시오.
산술적으로 두 번째 단계에서 얻은 값을 오른쪽으로 한 자리 이동시킨다.이제 P가 이 새로운 값과 같도록 하자.
2단계와 3단계를 y번까지 반복하십시오.
P에서 최하위(가장 오른쪽) 비트를 떨어뜨린다.이것은 m과 r의 산물이다.

예

3 × (-4), m = 3 및 r = -4, x = 4 및 y = 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) 불충분하다.이 문제에 대한 가능한 한 가지 수정은 A, S, P의 왼쪽에 한 비트를 더하는 것이다.그 다음, A와 S의 비트를 결정하는 수정과 함께 위에서 설명한 구현을 따른다. 예를 들어, 원래 A의 첫 번째 x 비트에 할당된 m 값은 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.오른쪽 교대.
제품은 1111000000(첫 번째와 마지막 비트를 폐기한 후)으로 -16이다.

작동 방식

0으로 둘러싸인 1초 블록으로 구성된 양의 승수를 고려한다.예: 001110.본 제품은 다음과 같이 제공된다.

M\time \,^{\premy \}0\;0\;1\;1\;1\;1\,^{\premy \premy }}=M\time (2^{5}+2^{4}+2^{3}+2^{2^{1}=}}}}}+2^{1}M\time 62

여기서 M은 승수다.같은 내용을 다시 작성하면 운영 횟수를 2회로 줄일 수 있다.

M\time \,^{\premy \premy \}0\;0\;0\{\mbox{-1}\;0\;^\premy \primy \primy \}=M\time (2^{6}-2^{1}=}}}}=)M\time 62.

사실, 이진수에서 1의 순서는 두 이진수의 차이로 나눌 수 있다는 것을 알 수 있다.

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

따라서, 곱셈은 실제로 원래 숫자의 곱셈의 끈으로 대체될 수 있다. 더 간단한 연산, 곱셈을 더하고, 적절한 위치에 의해 형성된 부분적인 곱셈을 이동시키고, 마지막으로 곱셈을 빼는 것이다.0을 2진법으로 처리하면서 교대하는 것 외에 아무것도 할 필요가 없다는 점을 활용하고 있으며 99 = 100 - 1을 곱하면서 99 = 100 - 1을 곱하는 수학적 특성을 사용하는 것과 유사하다.

이 계획은 승수(블록의 단일 1의 경우 포함)에서 1s의 임의 수의 블록으로 확장할 수 있다.그러므로,

M\time \,^{\premy \}0\;0\;1\;1\;1\;0\,^{\premy \premy \}=M\time (2^{5}+2^{4}+2^{3}+2^{1}=}}}}}{1}M\times 58

M\time \,^{\premy \premy \premy \}{-1\mbox{-1:1}}\\\1\1}\mbox{1}\1}\premy \premy \times (2^{6}-2^{3}+2^}-2^{1}={1}^{1}^{1}^{1}^{1}^{1}^{1}^{1}^{1}{1}{1}^{1^{1^{1}^{1}^{1}^}}}}}M\time 58.

부스의 알고리즘은 한 블록의 첫 번째 자리(0 1)와 블록의 끝자락(1 0)을 만났을 때 뺄셈을 만나면 덧셈을 수행함으로써 이 낡은 체계를 따른다.이것은 음의 승수에게도 효과가 있다.곱셈기에 있는 것을 긴 블록으로 묶을 때, 부스의 알고리즘은 일반적인 곱셈 알고리즘보다 더 적은 추가와 소축을 수행한다.

참고 항목

참조

^ 부스, 앤드류 도널드(1951년)[1950-08-01]."ASigned 이진 곱하기 기법"(PDF).그 계간 역학 및 응용 수학의.IV(2):236–240.그 2018-07-16에 원래에서Archived(PDF).2018-07-16 Retrieved.부스, 앤드류 도날드에 Reprinted.ASigned 이진 곱하기 기법.옥스포드 대학 출판부.를 대신하여 서명함. 100–104.
^ Chen, Chi-hau (1992). Signal processing handbook. CRC Press. p. 234. ISBN 978-0-8247-7956-6.

추가 읽기

Collin, Andrew (Spring 1993). "Andrew Booth's Computers at Birkbeck College". Resurrection. London: Computer Conservation Society (5).
Patterson, David Andrew; Hennessy, John Leroy (1998). Computer Organization and Design: The Hardware/Software Interface (Second ed.). San Francisco, California, USA: Morgan Kaufmann Publishers. ISBN 1-55860-428-6.
Stallings, William (2000). Computer Organization and Architecture: Designing for performance (Fifth ed.). New Jersey: Prentice-Hall, Inc. ISBN 0-13-081294-3.
Savard, John J. G. (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.

외부 링크

[Booth_1951-1] 부스, 앤드류 도널드(1951년)[1950-08-01]."ASigned 이진 곱하기 기법"(PDF).그 계간 역학 및 응용 수학의.IV(2):236–240.그 2018-07-16에 원래에서Archived(PDF).2018-07-16 Retrieved.부스, 앤드류 도날드에 Reprinted.ASigned 이진 곱하기 기법.옥스포드 대학 출판부.를 대신하여 서명함. 100–104.

[Chen_1992-2] Chen, Chi-hau (1992). Signal processing handbook. CRC Press. p. 234. ISBN 978-0-8247-7956-6.

[1]

[2]

Search