Bài giảng Thuật toán Booth

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