Algoritma Perkalian Booth

Posted on Updated on



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

Iklan

One thought on “Algoritma Perkalian Booth

    aryo said:
    4 Oktober, 2014 pukul 11:22 am

    gan, ane mau nanya. yang proses 2 dan 3 bit paling kanan kan 1, trus klo di shift kanan kok jadinya bit paling kiri 0 ? sedangkan proses yang ke-4 bit baling kanan 1, kemudian di shift kanan bit paling kiri jadi 1. Mohon penjelasannya. thanks

Apa komentarmu?

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s