Algoritma Perkalian Booth

Algoritma Perkalian Booth adalah algoritma perkalian yang mengalikan dua signed binary number dalam notasi two’s complement. Algoritma ini ditemukan oleh Andrew Donald Booth pada tahun 1951 ketika melakukan penelitian dalam kristalografi di Birbeck College di Bloombury, London. Algoritma Booth banyak digunakan dalam dunia computer.

Prosedur

Algoritma Booth bekerja dengan berulang kali menambahkan satu dari dua nilai  ditentukan A dan S untuk produk P, kemudian melakukan shift kanan aritmatik pada P. Misalnya m dan r menjadi multiplicand dan multiplier, dan x dan y merupakan jumlah bit di m dan r.

1.  Tentukan nilai A dan S, dan nilai awal P. Semua angka-angka harus memiliki panjang sama dengan (x + y + 1).

• A : Isi yang paling signifikan (paling kiri) bit dengan nilai m. Isi sisa (y + 1) bit dengan nol.
• S : Isi bit yang paling signifikan dengan nilai (-m) di notasi two’s complement. Isi sisa (y + 1) bit dengan nol.
• P : Isi bit paling signifikan x dengan nol. Di sebelah kanan ini, tambahkan nilai r. Isi bit  paling signifikan (paling kanan) dengan nol.

2.  Tentukan dua paling signifikan (paling kanan) bit dari P.

• Jika mereka adalah 01, tentukanlah nilai dari P + A. Abaikan overflow apapun.
• Jika mereka adalah 10, tentukanlah nilai dari P + S. Abaikan overflow apapun.
• Jika mereka 00, tidak perlu melakukan apa-apa. Gunakan P langsung pada langkah berikutnya.
• Jika mereka 11, tidak perlu melakukan apa-apa. Gunakan P langsung pada langkah berikutnya.

3.  Lakukan sekali shift kanan aritmatik terhadap nilai yang diperoleh dari langkah 2.

4.  Ulangi langkah 2 dan 3 sebanyak y kali.

5.  Buang LSB dari nilai P (bit paling kanan). Nilai yang diperoleh adalah hasil perkalian m dan r.

Contoh

Tentukan nilai dari -5 x 7, dengan m = -5 dan r = 7, dimana x = 4 dan y = 4

• A = 1011 0000 0
• S = 0101 0000 0
• P = 0000 0111 0

Kita akan melakukan 4 kali looping :

1.  P = 0000 0111 0. Dua bit terakhir adalah 10.

→ P = 0101 0111 0. P = P + S.

→ P = 0010 1011 1. Shift kanan aritmatik.

2.  P = 0010 1011 1. Dua bit terakhir adalah 11.

→ P = 0001 0101 1. Shift kanan aritmatik.

3.  P = 0001 0101 1. Dua bit terakhir adalah 11.

→ P = 0000 1010 1. Shift kanan aritmatik.

4.  P = 0000 1010 1. Dua bit terakhir adalah 01

→ P = 1011 1010 1. P = P + A.

→ P = 1101 1101 0. Shift kanan aritmatik.

 

Hasil perkalian adalah 1101 1101 = -35

Artikel ini saya copy dari http://bilt4blog.wordpress.com/.

Credits all to http://bilt4blog.wordpress.com/.

Salam dari http://echowhiterabbit.blogspot.com/