Algoritma Booth: Perkalian Bilangan Biner yang Efisien

Dalam dunia komputasi, operasi perkalian seringkali menjadi salah satu operasi aritmatika fundamental. Kecepatan dan efisiensi dalam melakukan perkalian dapat sangat memengaruhi kinerja keseluruhan sebuah sistem. Salah satu algoritma yang dirancang untuk mencapai efisiensi ini, terutama dalam perkalian bilangan biner, adalah Algoritma Booth.

Apa itu Algoritma Booth?

Algoritma Booth adalah sebuah algoritma yang digunakan untuk mengalikan dua bilangan bertanda (signed numbers) dalam representasi pelengkap dua (two's complement). Algoritma ini dikembangkan oleh Andrew Donald Booth pada tahun 1951. Keunggulan utama Algoritma Booth terletak pada kemampuannya untuk mengurangi jumlah langkah perkalian jika terdapat urutan bit nol atau satu yang berulang dalam pengali (multiplier), sehingga menjadikannya lebih efisien dibandingkan metode perkalian biner langsung yang sederhana.

Cara Kerja Algoritma Booth

Algoritma Booth bekerja dengan memproses bit-bit pengali dari kanan ke kiri. Algoritma ini menggunakan empat nilai utama yang dipertahankan selama proses iterasi:

• A (Accumulator): Register yang menyimpan sebagian dari hasil perkalian sementara.
• Q: Register yang menyimpan bit-bit pengali.
• Q_-1: Bit tambahan di sebelah kanan bit terendah dari Q, digunakan untuk menyimpan bit sebelumnya.
• M: Multiplicand (bilangan yang akan dikalikan).

Setiap iterasi melibatkan pemeriksaan dua bit terakhir dari pengali (bit terendah Q dan Q_-1). Berdasarkan kombinasi kedua bit ini, operasi berikut akan dilakukan:

1. Jika Q = 0 dan Q_-1 = 0: Tidak ada operasi aritmatika yang dilakukan.
2. Jika Q = 0 dan Q_-1 = 1: Operasi Aritmetik Shift Kiri (Arithmetic Left Shift) dilakukan pada A dan Q. Ini setara dengan menambahkan M ke A.
3. Jika Q = 1 dan Q_-1 = 0: Operasi Aritmetik Shift Kanan (Arithmetic Right Shift) dilakukan pada A dan Q. Ini setara dengan mengurangkan M dari A (atau menambahkan komplemen dua M).
4. Jika Q = 1 dan Q_-1 = 1: Tidak ada operasi aritmatika yang dilakukan.

Setelah operasi yang sesuai dilakukan, nilai Q_-1 diperbarui dengan bit terendah Q, dan kemudian Q digeser ke kanan (Arithmetic Right Shift) bersama dengan A. Proses ini diulang sebanyak jumlah bit pada pengali.

Ilustrasi Sederhana

Misalkan kita ingin mengalikan $5 \times 3$ dalam representasi 4-bit:

• Multiplicand (M) = $0101$ (5)
• Multiplier (Q) = $0011$ (3)

Inisialisasi:

• A = $0000$
• Q = $0011$
• Q_-1 = $0$

Iterasi 1:

• Bit yang diperiksa: Q=1, Q_-1=0.
• Operasi: A = A - M. A = $0000 - 0101 = 1011$ (pelengkap dua dari -5).
• Arithmetic Right Shift: A menjadi $1101$, Q menjadi $0001$, Q_-1 menjadi $1$.

Iterasi 2:

• Bit yang diperiksa: Q=1, Q_-1=1.
• Operasi: Tidak ada aritmatika.
• Arithmetic Right Shift: A menjadi $1110$, Q menjadi $0000$, Q_-1 menjadi $0$.

Iterasi 3:

• Bit yang diperiksa: Q=0, Q_-1=0.
• Operasi: Tidak ada aritmatika.
• Arithmetic Right Shift: A menjadi $1111$, Q menjadi $0000$, Q_-1 menjadi $0$.

Iterasi 4:

• Bit yang diperiksa: Q=0, Q_-1=0.
• Operasi: Tidak ada aritmatika.
• Arithmetic Right Shift: A menjadi $1111$, Q menjadi $0000$, Q_-1 menjadi $0$.

Hasil akhir: A = $1111$, Q = $0000$. Hasil perkaliannya adalah $11110000$. Namun, dalam representasi 4-bit, hasil yang relevan adalah 8 bit teratas, yaitu $00001111$, yang merupakan $15$ dalam desimal. Perlu diingat bahwa hasil sebenarnya dari $5 \times 3$ adalah $15$. Algoritma ini bekerja dengan benar untuk bilangan bertanda.

Keuntungan dan Kerugian

Keuntungan:

• Efisiensi: Mengurangi jumlah operasi penjumlahan/pengurangan jika terdapat urutan bit yang sama yang berdekatan.
• Menangani Bilangan Bertanda: Cocok untuk perkalian bilangan dalam format pelengkap dua.
• Performa: Cenderung lebih cepat daripada algoritma perkalian biner langsung pada beberapa kasus.

Kerugian:

• Kompleksitas: Lebih kompleks untuk diimplementasikan dibandingkan algoritma perkalian biner sederhana.
• Performa pada Kasus Tertentu: Pada kasus di mana tidak ada urutan bit yang panjang, efisiensinya mungkin tidak jauh berbeda dari metode langsung.

Aplikasi

Algoritma Booth telah banyak digunakan dalam desain sirkuit digital, terutama pada Unit Aritmatika dan Logika (ALU) mikroprosesor dan unit pemrosesan digital sinyal (DSP) yang membutuhkan operasi perkalian cepat. Implementasinya memungkinkan perangkat keras untuk melakukan perhitungan matematika yang kompleks dengan lebih efisien.

Secara keseluruhan, Algoritma Booth adalah metode yang cerdas dan efisien untuk melakukan perkalian bilangan biner bertanda, menawarkan peningkatan performa dalam banyak skenario komputasi.