Thuật toán Booth
Thực hiện phép toán nhân lưu đồ theo thuật
toán Booth.
• Các số hạng trong phép nhân phải có dấu. Vậy
nếu là Số dương bit lớn nhất = 0; Số âm bit lớn
nhất = 1
• Các số hạng có độ dài bit giống nhau.
• Khởi tạo Q
-1 =0
• Khi Q0Q-1 = 00 hay 11 dời bit sang phải giảm số
hạng nhân là 1
Khi Q0Q-1 = 01 thì A = A+M dời bit sang phải
giảm số hạng nhân là 1
• Khi Q0Q-1 = 10 thì A = A-M dời bit sang phải
giảm số hạng nhân là 1
• Khi dời bit giữ dấu của A
• Khi nhân hết số hạng kết quả là giá trị được
nối giữa hai giá trị A & Q
6 trang |
Chia sẻ: candy98 | Lượt xem: 4803 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Bài giảng Kiến trúc máy tính - Thuật toán Booth - ĐHCN TP.HCM, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Thuật toán Booth
Thực hiện phép toán nhân lưu đồ theo thuật
toán Booth.
• Các số hạng trong phép nhân phải có dấu. Vậy
nếu là Số dương bit lớn nhất = 0; Số âm bit lớn
nhất = 1
• Các số hạng có độ dài bit giống nhau.
• Khởi tạo Q-1 =0
• Khi Q0Q-1 = 00 hay 11 dời bit sang phải giảm số
hạng nhân là 1
21/05/13 Kiến Trúc Máy Tính 1
21/05/13 Kiến Trúc Máy Tính 2
• Khi Q0Q-1 = 01 thì A = A+M dời bit sang phải
giảm số hạng nhân là 1
• Khi Q0Q-1 = 10 thì A = A-M dời bit sang phải
giảm số hạng nhân là 1
• Khi dời bit giữ dấu của A
• Khi nhân hết số hạng kết quả là giá trị được
nối giữa hai giá trị A & Q
Ví dụ : 12 x -5
Chuyển số thập phân sang nhị phân có dấu:
M = 12 M = 011002 ; -M = 101002
Q = -5 Q = 110112
A = 00000 , Count = 5
Thông thường trong máy tính các số hạng có dạng 4, 8, 16, 32,
64 bits nhưng để đơn giản và không ảnh hưởng thuật toán ta
có thể chuyển sang số nhị phân có số bit 2 số hạng bằng nhau
và có dấu
21/05/13 Kiến Trúc Máy Tính 3
A Q0 Q-1 Thực hiện
00000 11011 0 Q0Q-1 =10, Count = 5
10100 11011 0 A= A-M
11010 01101 1 Shift R, Count = 4, Q0Q-1 =11
11101 00110 1 Shift R, Count = 3, Q0Q-1 =01
1 01001 00110 1 A= A+M
00100 10011 0 Shift R, Count = 2, Q0Q-1 =10
11000 10011 0 A= A-M
11100 01001 1 Shift R, Count = 1, Q0Q-1 =11
11110 00100 1 Shift R, Count = 0 Kết thúc
Kết quả : 1111000100
21/05/13 Kiến Trúc Máy Tính 4
Ví dụ : -5 x 12
Chuyển số thập phân sang nhị phân có dấu:
M = -5 M = 110112 - M = 00101
Q = 12 M = 011002
A = 00000 , Count = 5
Thông thường trong máy tính các số hạng có dạng 4, 8, 16, 32,
64 bits nhưng để đơn giản và không ảnh hưởng thuật toán ta
có thể chuyển sang số nhị phân có số bit 2 số hạng bằng nhau
và có dấu
21/05/13 Kiến Trúc Máy Tính 5
A Q0 Q-1 Thực hiện
00000 01100 0 Q0Q-1 =00, Count = 5
00000 00110 0 Shift R, Q0Q-1 = 00, Count = 4
00000 00011 0 Shift R, Count = 3, Q0Q-1 =10
00101 00011 0 A= A-M
00010 10001 1 Shift R, Count = 2, Q0Q-1 =11
00001 01000 1 Shift R, Count = 1, Q0Q-1 =01
11100 01000 1 A= A+M
11110 00100 1 Shift R, Count = 0, Q0Q-1 =11, Kết thúc
Kết quả : 1111000100
21/05/13 Kiến Trúc Máy Tính 6