Algoritma Booth: Kalkulator Cerdas Perkalian Biner

Di era digital, operasi matematika yang efisien menjadi tulang punggung berbagai teknologi, mulai dari komputasi sains, grafis komputer, hingga sistem keamanan. Salah satu operasi mendasar yang sering ditemui adalah perkalian. Untuk bilangan desimal, kita sudah sangat familiar dengan metode perkalian susun. Namun, dalam dunia komputer yang bekerja dengan sistem biner, perkalian memerlukan pendekatan yang berbeda. Salah satu algoritma perkalian biner yang sangat efisien dan banyak digunakan adalah **Algoritma Booth**. Algoritma ini dirancang untuk mempercepat proses perkalian, terutama ketika mengalikan bilangan bertanda (positif dan negatif).

Apa Itu Algoritma Booth?

Algoritma Booth, yang dikembangkan oleh William Stallings Booth pada tahun 1951, adalah sebuah algoritma perkalian biner yang memiliki keunggulan dalam menangani bilangan bertanda. Berbeda dengan metode perkalian biner "naif" yang melakukan banyak penambahan, Algoritma Booth berusaha mengurangi jumlah langkah penambahan yang diperlukan. Keunggulan utamanya terletak pada kemampuannya untuk mengenali pola berurutan dari angka 1 dalam bilangan pengali (multiplier) dan menggantinya dengan operasi yang lebih efisien. Ini sangat signifikan dalam mengurangi total operasi yang harus dilakukan oleh prosesor.

Bagaimana Cara Kerja Algoritma Booth?

Prinsip dasar Algoritma Booth adalah melakukan scan terhadap bit-bit bilangan pengali dari kanan ke kiri, sambil membandingkan bit saat ini dengan bit sebelumnya. Berdasarkan perbandingan ini, beberapa aksi dilakukan: penambahan, pengurangan, atau tidak melakukan apa-apa (geser).

Untuk memahami cara kerjanya, kita perlu mendefinisikan beberapa elemen:

• Multiplicand (A): Bilangan yang akan dikalikan.
• Multiplier (B): Bilangan yang digunakan untuk mengalikan.
• Accumulator (Q): Menyimpan hasil sementara. Awalnya berisi Multiplier (B).
• Register Awal (A'): Register tambahan yang berukuran sama dengan Accumulator, digunakan untuk menyimpan bit sebelumnya dari Accumulator. Awalnya berisi 0.
• Product (P): Hasil akhir perkalian, biasanya berukuran 2 kali lebar Multiplicand.

Langkah-langkah umum Algoritma Booth adalah sebagai berikut:

1. Inisialisasi: Inisialisasi Accumulator (Q) dengan Multiplier (B), Register Awal (A') dengan 0, dan Product (P) dengan 0.
2. Proses Perulangan: Lakukan perulangan sebanyak jumlah bit dalam Multiplier. Dalam setiap iterasi:
   • Lihat dua bit terakhir: bit paling kanan dari Accumulator (Q) dan bit dari Register Awal (A').
   • Berdasarkan kombinasi kedua bit ini, lakukan salah satu dari tiga operasi berikut:
     • 10 (bit Q = 0, bit A' = 1): Lakukan pengurangan Multiplicand (A) dari Product (P). Operasi ini mengindikasikan dimulainya blok angka 1.
     • 01 (bit Q = 1, bit A' = 0): Lakukan penambahan Multiplicand (A) ke Product (P). Operasi ini mengindikasikan berakhirnya blok angka 1.
     • 00 atau 11: Tidak ada penambahan atau pengurangan yang dilakukan.
   • Geser secara aritmatika ke kanan: Geser Product (P), Accumulator (Q), dan Register Awal (A') satu bit ke kanan. Bit paling kanan dari Q menjadi bit paling kiri dari A', dan bit paling kanan dari P menjadi bit paling kiri dari Q. Bit tanda (sign bit) dipertahankan untuk geseran aritmatika.
3. Hasil Akhir: Setelah semua iterasi selesai, hasil perkalian adalah gabungan dari bit-bit pada Product (P) dan Accumulator (Q).

Keunggulan Algoritma Booth

Mengapa Algoritma Booth begitu penting dalam komputasi? Jawabannya terletak pada efisiensinya:

• Perkalian Bilangan Bertanda: Ini adalah keuntungan utamanya. Algoritma ini bekerja dengan baik untuk bilangan positif maupun negatif, menggunakan representasi komplemen dua tanpa memerlukan konversi terpisah.
• Mengurangi Jumlah Penambahan: Dibandingkan dengan algoritma perkalian biner standar, Algoritma Booth dapat secara signifikan mengurangi jumlah operasi penambahan dan pengurangan yang diperlukan, terutama jika bilangan pengali memiliki blok angka 1 yang panjang.
• Kecepatan: Dengan mengurangi jumlah operasi, Algoritma Booth secara inheren lebih cepat. Ini penting dalam sistem yang membutuhkan pemrosesan berkecepatan tinggi.
• Implementasi Hardware yang Efisien: Algoritma ini mudah diimplementasikan dalam desain sirkuit digital, menjadikannya pilihan populer untuk Unit Aritmatika dan Logika (ALU) pada CPU.

Contoh Sederhana (Konseptual)

Misalkan kita ingin mengalikan A = 5 (0101) dengan B = 3 (0011) menggunakan algoritma Booth dengan representasi 4-bit.

Multiplicand (A) = 0101

Multiplier (B) = 0011

Inisialisasi:

A' = 0000

Q = 0011 (Multiplier)

P = 0000 (Bagian Product)

Kita akan melakukan 4 iterasi (sesuai jumlah bit).

Iterasi 1:

Bit terakhir Q=1, Bit A'=0. Kombinasi "01". Lakukan penambahan A ke P.

P = P + A = 0000 + 0101 = 0101

Geser kanan: A'=0, Q=0010, P=0010.

Kondisi setelah geser: A'=0, Q=0010, P=0010 (Bit paling kanan Q masuk ke A', bit paling kanan P masuk ke Q)

Iterasi 2:

Bit terakhir Q=0, Bit A'=0. Kombinasi "00". Tidak ada operasi penambahan/pengurangan.

Geser kanan: A'=0, Q=0001, P=0001.

Kondisi setelah geser: A'=0, Q=0001, P=0001.

Iterasi 3:

Bit terakhir Q=1, Bit A'=0. Kombinasi "01". Lakukan penambahan A ke P.

P = P + A = 0001 + 0101 = 0110

Geser kanan: A'=0, Q=0011, P=0011.

Kondisi setelah geser: A'=0, Q=0011, P=0011.

Iterasi 4:

Bit terakhir Q=1, Bit A'=0. Kombinasi "01". Lakukan penambahan A ke P.

P = P + A = 0011 + 0101 = 1000

Geser kanan: A'=0, Q=0100, P=0100.

Kondisi setelah geser: A'=0, Q=0100, P=0100.

Hasil Akhir: Gabungan P dan Q (dengan mempertimbangkan bit tanda): 0100 0100 (ini adalah representasi 8-bit hasil perkalian 5 * 3 = 15, yaitu 00001111). Jika kita hanya melihat P dan Q sebagai satu kesatuan dari kiri ke kanan: 01000100, ini merepresentasikan 68 dalam desimal (terlalu besar karena penanganan bit tanda perlu lebih hati-hati dalam contoh sederhana ini).

Catatan Penting: Contoh di atas adalah penyederhanaan konseptual. Implementasi yang sebenarnya, terutama untuk bilangan negatif menggunakan komplemen dua, memerlukan perhatian lebih pada bit tanda dan bagaimana geseran aritmatika memengaruhinya. Namun, ilustrasi ini memberikan gambaran dasar tentang proses perbandingan bit dan operasi yang mengikuti.

Aplikasi Algoritma Booth

Algoritma Booth banyak diterapkan dalam berbagai konteks:

• Unit Aritmatika dan Logika (ALU): Di dalam setiap CPU komputer modern, ALU menggunakan algoritma seperti Booth untuk melakukan operasi perkalian yang cepat.
• Sistem Digital: Digunakan dalam desain chip yang memerlukan perkalian biner efisien, seperti dalam pemrosesan sinyal digital (DSP) atau sistem embedded.
• Kriptografi: Operasi perkalian merupakan elemen kunci dalam banyak algoritma kriptografi.
• Grafika Komputer: Transformasi matriks dan operasi lain dalam grafika seringkali melibatkan perkalian biner.

Kesimpulan

Algoritma Booth adalah metode perkalian biner yang cerdas dan efisien, terutama dalam menangani bilangan bertanda. Dengan meminimalkan jumlah operasi penambahan dan pengurangan, algoritma ini memberikan peningkatan kinerja yang signifikan. Kemampuannya untuk beradaptasi dengan pola bit pengali menjadikannya fondasi penting dalam komputasi digital, memastikan bahwa operasi perkalian dapat dilakukan dengan cepat dan akurat di berbagai aplikasi teknologi yang kita gunakan sehari-hari.