Teknik Digital: Algoritma Booth Untuk Perkalian Dua Bilangan Biner Integer Bertanda

jati.itda.ac.id

8 Oct, 2015

Pendahuluan:

Asumsinya pertama kita sudah mengetahui operasi aritmatika dasar (tambah, kurang, kali dan bagi) untuk bilangan biner integer. Sebagai contoh :

Operasi penjumlahan:

Operasi pengurangan

Operasi perkalian

Operasi pembagian

Asumsi kedua kita juga sudah mengetahui representasi bilangan negatif biner dengan komplemen 2. Sebagai contoh:

-10 (desimal) = 10110 (biner 5 bit)

Saat ini kita akan menggunakan Algoritma Booth untuk perkalian bilangan biner bertanda (signed binary multiplication) karena perkalian bilangan biner bertanda tidak semudah biasanya. :)

Sebelum kita masuk ke algoritma, ada baiknya kita samakan terlebih dulu istilah yang nanti saya gunakan. Jika saya ingin melakukan operasi aritmatika: 6 * -7 maka:

Multiplikan = 6

Multiplier = -7

Algoritma

Algoritma booth adalah sebuah proses iterasi dimana jumlah iterasinya sama dengan jumlah bit yang kita gunakan dalam representasi bilangan biner. Sebagai contoh jika kita memiliki angka -7 dalam desimal dan kita menggunakan 11001 sebagai bilangan binernya, berarti kita menggunakan 5 bit sehingga jumlah iterasi nantinya adalah 5x.

Algoritma Booth ini menggunakan 4 variabel yaitu

Produk
Bit terakhir produk (product's last bit)
Bit terakhir produk sebelumnya (product's previous last bit)
Action

Keterangan:

Variabel produk terdiri dari 2 bagian yaitu nilai kiri (left side) dan nilai kanan (right side). Nilai kiri produk nantinya berisi nilai yang akan di "operasi" dengan penjumlahan atau pengurangan dengan multiplikan sedangkan nilai kanan berisi multiplier. Jumlah bit antara left side dan right side harus sama.
Product's last bit (untuk selanjutnya disingat Last Bit) adalah nilai least significant bit (LSB) atau nilai bit paling kanan dari product. Misalnya nanti product memiliki nilai 11010 11001, maka nilai Last bit sama dengan 1.
Product's previous last bit (selanjutnya disingkat Previous Bit) adalah nilai last bit pada iterasi sebelumnya.
Setiap kenaikan proses iterasi, nilai bit produk akan digeser (shifted) ke kanan.
Action: Nilai aksi ini tergantung pada susunan last bit dan previous bit di masing-masing iterasi sebagai berikut:
00 : Tidak ada aksi apa-apa
01 : tambahkan bit pada left side product dengan multiplikan
10 : kurangi bit pada left side product dengan multiplikan
11 : Tidak ada aksi apa-apa

Studi Kasus

Setelah kita memahami langkah-langkah pada algoritma booth, saatnya kita coba implementasi Algoritma Booth pada perkalian bilangan biner bertanda.

Kasus I
Kasus yang akan kita gunakan adalah 6 * -7 (dalam desimal).

Multiplikan : 6 (desimal) = 00110 (biner)

Multiplier : -7 (desimal) = 11001 (biner)

Bantu : -6 (desimal) = 11010 (biner)

Contoh di atas menggunakan representasi 5 bit yang berarti ada 5 iterasi algoritma booth. Angka bantu di sini digunakan untuk membantu aksi saat susunan last bit dan previous bit adalah 1 dan 0.

Perhatikan gambar di bawah ini:

Penjelasan proses penambahan dan pengurangan left side produk dengan multiplikan di Step 1 ke Step 1a dan dari Step 3 ke Step 3a

Penjumlahan produk dengan multiplikan:

Pengurangan produk dengan multiplikan (saya menggunakan teknik penjumlahan dengan angka bantu):

Kasus II:
9 * -7 dengan 6 bit bilangan biner. Karena menggunakan 6 bit, maka ada 6 step iterasi Algoritma Booth.

Multiplikan : 9 (desimal) = 001001 (biner)

Multiplier : -7 (desimal) = 111001 (biner)

Bantu : -9 (desimal) = 110111 (biner)

Perhatikan tabel berikut:

Semoga Bermanfaat

Booth Digital Negatif