부스 알고리즘은 2의 보수로 부호 있는 두 이진 정수를 각각 곱할 수 있는 곱셈 알고리즘입니다. 또한 곱셈 과정의 성능을 높이는 데에도 사용됩니다. 매우 효율적이기도 합니다. 추가 비트가 필요하지 않은 승수의 문자열 비트 0에서 작동하며 승수 비트 가중치 2에서 가장 오른쪽 문자열 비트와 1의 문자열만 이동합니다.케이무게 2로중그것은 다음과 같이 간주될 수 있다. 2k+ 1- 2중 .
다음은 부스 알고리즘을 그림으로 표현한 것입니다.
위의 순서도에서 처음에는 교류 그리고 큐엔 + 1 비트는 0으로 설정되고 SC 총 비트 세트를 나타내는 시퀀스 카운터입니다. N, 이는 승수의 비트 수와 같습니다. 있다 BR 을 대표하는 피승수 비트, QR은 승수 비트 . 그 후, 우리는 Q로 곱셈기의 두 비트를 만났습니다.N그리고 Q엔 + 1여기서 Qn은 QR의 마지막 비트를 나타내고 Q는엔 + 1는 1만큼 증가된 Qn 비트를 나타냅니다. 곱셈기의 두 비트가 10과 같다고 가정합니다. 이는 누산기 AC의 부분 곱에서 승수를 뺀 다음 산술 시프트 연산(ashr)을 수행해야 함을 의미합니다. 승수 중 두 개가 01이면 누산기 AC의 부분 곱에 피승수를 더한 다음 산술 이동 연산을 수행해야 함을 의미합니다( 아쉬르 ), 포함 큐엔 + 1 . 산술 시프트 연산은 Booth 알고리즘에서 AC 및 QR 비트를 오른쪽으로 하나씩 이동하고 AC의 부호 비트를 변경하지 않고 유지하는 데 사용됩니다. 그리고 시퀀스 카운터는 계산 루프가 반복될 때까지 비트 수(n)와 동일하게 계속 감소합니다.
부스 알고리즘 작업
- 피승수 및 승수 이진 비트를 각각 M 및 Q로 설정합니다.
- 처음에는 AC와 Q를 설정했습니다.엔 + 1값을 0으로 등록합니다.
- SC는 승수 비트(Q)의 수를 나타내며, 비트 수(n)와 같거나 0이 될 때까지 계속 감소하는 시퀀스 카운터입니다.
- Qn은 Q의 마지막 비트를 나타내며, Q는n+1Qn의 비트가 1만큼 증가한 것을 보여줍니다.
- 부스 알고리즘의 각 주기에서 QN그리고 Q엔 + 1비트는 다음 매개변수에 대해 다음과 같이 확인됩니다.
- 2비트 Q일 때N그리고 Q엔 + 100 또는 11인 경우 부분 곱 AC에 대해 산술 오른쪽 시프트 연산(ashr)을 수행하기만 하면 됩니다. 그리고 Qn과 Q의 비트엔 + 11비트씩 증가합니다.
- Q의 비트라면N그리고 Q엔 + 101에 표시되면 피승수 비트(M)가 AC(누산기 레지스터)에 추가됩니다. 그 후, AC와 QR 비트를 1만큼 오른쪽으로 이동하는 연산을 수행합니다.
- Q의 비트라면N그리고 Q엔 + 110에 표시된 것처럼 피승수 비트(M)는 AC(누산기 레지스터)에서 뺍니다. 그 후, AC와 QR 비트에 대해 1만큼 오른쪽 시프트 연산을 수행합니다.
- 부스 알고리즘에서 n - 1 비트에 도달할 때까지 작업이 계속 작동합니다.
- 곱셈 이진 비트의 결과는 AC 및 QR 레지스터에 저장됩니다.
부스 알고리즘에는 두 가지 방법이 사용됩니다.
소수 자바
1. RSC(오른쪽 시프트 원형)
이진수의 가장 오른쪽 비트를 이동한 다음 이진수 비트의 시작 부분에 추가합니다.
2. RSA(오른쪽 시프트 연산)
두 개의 이진 비트를 더한 다음 결과를 1비트 위치만큼 오른쪽으로 이동합니다.
파워셸과 배쉬
예 : 0100 + 0110 => 1010, 이진수를 더한 후 각 비트를 오른쪽으로 1씩 이동하고 결과의 첫 번째 비트를 새 비트의 시작 부분에 넣습니다.
예: 부스의 곱셈 알고리즘을 사용하여 두 숫자 7과 3을 곱합니다.
연령 . 여기에는 7과 3이라는 두 개의 숫자가 있습니다. 먼저 7과 3을 7 = (0111) 및 3 = (0011)과 같은 이진수로 변환해야 합니다. 이제 7(이진수 0111)을 피승수(M)로 설정하고 3(이진수 0011)을 승수(Q)로 설정합니다. 그리고 SC(Sequence Count)는 비트 수를 나타내며 여기서는 4비트이므로 SC = 4로 설정합니다. 또한 부스 알고리즘의 반복 주기 수를 나타내며 그 주기는 SC = SC - 1회 실행됩니다.
| 큐N | 큐엔 + 1 | 남 = (0111) M' + 1 = (1001) & 연산 | 교류 | 큐 | 큐엔 + 1 | SC |
|---|---|---|---|---|---|---|
| 1 | 0 | 초기의 | 0000 | 0011 | 0 | 4 |
| 덜다 (M' + 1) | 1001 | |||||
| 1001 | ||||||
| 산술 오른쪽 시프트 연산 수행(ashr) | 1100 | 1001 | 1 | 삼 | ||
| 1 | 1 | 산술 오른쪽 시프트 연산 수행(ashr) | 1110 | 0100 | 1 | 2 |
| 0 | 1 | 덧셈(A+M) | 0111 | |||
| 0101 | 0100 | |||||
| 산술 오른쪽 시프트 연산 수행 | 0010 | 1010 | 0 | 1 | ||
| 0 | 0 | 산술 오른쪽 시프트 연산 수행 | 0001 | 0101 | 0 | 0 |
부스 곱셈 알고리즘의 수치적 예는 7 x 3 = 21이고 21의 이진수 표현은 10101입니다. 여기서 결과는 이진수 00010101로 표시됩니다. 이제 이를 (000010101)과 같이 십진수로 변환합니다.10= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.
100만개
예: 부스의 곱셈 알고리즘을 사용하여 두 숫자 23과 -9를 곱합니다.
여기서 M = 23 = (010111), Q = -9 = (110111)
| 큐N큐엔 + 1 | 남 = 0 1 0 1 1 1 M' + 1 = 1 0 1 0 0 1 | 교류 | 큐 | 큐엔 + 1SC |
|---|---|---|---|---|
| 처음에는 | 000000 | 110111 | 0 6 | |
| 1 0 | M 빼기 | 101001 | ||
| 101001 | ||||
| 산술 오른쪽 시프트 연산 수행 | 110100 | 111011 | 열 다섯 | |
| 열하나 | 산술 오른쪽 시프트 연산 수행 | 111010 | 011101 | 1 4 |
| 열하나 | 산술 오른쪽 시프트 연산 수행 | 111101 | 001110 | 1 3 |
| 0 1 | 덧셈(A+M) | 010111 | ||
| 010100 | ||||
| 산술 오른쪽 시프트 연산 수행 | 001010 | 000111 | 0 2 | |
| 1 0 | M 빼기 | 101001 | ||
| 110011 | ||||
| 산술 오른쪽 시프트 연산 수행 | 111001 | 100011 | 열하나 | |
| 열하나 | 산술 오른쪽 시프트 연산 수행 | 111100 | 110001 | 1 0 |
큐엔 + 1 = 1이면 출력이 음수임을 의미합니다.
따라서 23 * -9 = 111100110001의 2의 보수 => (00001100111)