Bài giảng Kiến trúc máy tính - Thuật toán Booth - ĐHCN TP.HCM

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