Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

Sistem Digital : Algoritma dalam Perkalian, Algoritma Perkalian Booth, dan Pembagian

Perkalian

Pengali (Multiplier) dan yang dikalikan (Multiplicand) diload ke dalam 2 register (Q and M). Register ke-3, register A juga diperlukan dan di-inisialisasi 0. Ada juga sebuah 1-bit, register C yang di-inisialisasi 0, yang menyimpan carry bit yang dihasilkan dari penambahan.

Algoritma

Operasi perkalian sbb ( lihat algoritmanya di gambar )

• Control logic membaca bit dari multiplier, satu setiap saat. 
• Jika Q0 = 1, maka multiplicand ditambahkan ke register A dan hasilnya disimpan di register A, dengan C bit digunakan untuk overflow.
• Kemudian, semua bit dari register C, A dan Q digeser ke kanan 1 bit sehingga C bit ke An-1, A0 ke Qn-1 dan Q0 hilang.
• Jika Q0 = 0, maka tidak ada penambahan, hanya pergeseran yang dilakukan.
• Proses ini diulang untuk setiap bit dari multiplier (original)
• Hasil dari perkalian 2n bit diperoleh di dalam register A dan Q.

Contoh

Perkalian dengan Algoritma Booth

Perkalian twos complement dapat dilakukan dengan algoritma Booth. Multiplier dan multiplicand ditempatkan pada register Q dan M. Ada sebuah register 1 bit yang secara logik ditempatkan pada LSB dari Q (Q0) darn register Q dan diberikan label Q-1. Hasil dari perkalian akan muncul di register A dan Q.

Algoritma Booth

• A dan Q-1 diinisialisasi 0. 
• Control logic akan meng-scan bit dari multiplier satu bit setiap saat. Jika setiap bit diperiksa, bit di kirinya juga diperiksa 
• Jika keduanya sama (1-1 atua 0- 0), semua bit dari register A, Q dan Q-1 digeser ke kanan 1 bit. 
• Jika kedua bit berbeda, 1-0, A dikurangi dengan M. Jika 0-1, A ditambahkan dengan M. 
• Kemudian, register A, Q dan Q-1 digeser ke kanan. 
• Pergeseran ke kanan, LSB dari A, yaitu An-1 tidak hanya digeser ke kanan (An-2) tetapi juga tinggal tetap di An-1. Ini yang disebut dengan arithmetic shift, karena mempertahankan bit tanda.

Contoh 7x3 : Algoritma Booth

Pembagian ( of unsigned binary integers )

Perhatikan gambar, menunjukkan sebuah contoh pembagian bilangan binary integer unsigned ( tidak bertanda ).

Pertama, bit dari dividend (yang dibagi) diperiksa dari kiri ke kanan, sampai himpunan dari bit-bit menunjukkan sebuah bilangan yang lebih besar atau sama dengan divisor (pembagi); ini menyatakan bahwa divisor dapat membagi bilangan.

Sampai tahapan tersebut, 0 ditempatkan di quetiont (hasil bagi) dari kiri ke kanan. Ketika bit-bit tersebut >= divisor, sebuah bit 1 ditempatkan pada hasil bagi dan divisor dikurangkan dari partial dividend. Hasil diacu sebagai partial remainder.

Pembagian terus dilakukan sebagai siklus, dimana pada setiap siklus bit tambahan dari dividend ditambahkan ke partial remainders sampai hasil lebih besar atau sama dengan divisor. Kemudian divisor dikurangkan dari bilangan untuk menghasilkan partial remainder baru.

Proses dilanjutkan terus sampai semua bit dari dividend habis.

Algoritma Pembagian

Gambar berikut, menunjukkan algoritma yang berkaitan dengan proses pembagian yang panjang tersebut.

• Divisor (pembagi) ditempatkan di register M, Dividend (yang dibagi) ditempatkan di register Q. Count = n (jumlah bit divisor)
• Setiap langkah, register A dan Q di-shift ke kiri 1 bit.
• M dikurangkan dari A untuk menentukan apakah A membagi partial remainder (A < 0).
• Jika (A < 0?), Q0 memperoleh sebuah bit 0 dan M harus ditambahakan ke A (untuk restore) nilai sebelumnya. Jika sebaliknya (A > = 0), Q0 mendapatkan bit 1
• Count = count – 1 dan proses dilanjutkan sebanyak n langkah
• Pada akhirnya, quotient (hasil bagi) berada di register Q dan sisa bagi berada di register A

Proses jalannya algoritma pembagian

Jalannya algoritma

Algoritma mengasumsikan bahwa divisor V dan dividend D adalah positif dan |V| < |D|. Jika |V| = |D|, maka quotient Q = 1 dan sisa baginya (remainder) R = 0. Jika |V| > |D|, maka Q = 0 dan R = D. 

Algoritma berjalan sebagai berikut :

• Load bentuk twos complement dari divisor ke register M; yaitu register M yang berisi negatif dari divisor. Load dividend ke register A dan Q. Dividend harus diekspresikan sebagai 2n-bit bilangan positif. Contohnya: 4 bit 0111 menjadi 00000111 
• Shift A, Q ke kiri 1 posisi bit 
• Lakukan A = A – M. 
• Jika hasilnya adalah nonnegatif (MSB dari A = 0) maka Q0 ß 1; Jika hasilnya negatif (MSB dari A = 1), maka Q0 ß 0 dan kemudian nilai A dikembalikan ke semula (A = A + M) 
• Ulangi langkah 2 sampai 4 sebanyak posisi bit di Q 
• Sisa bagi di A dan hasil bagi di Q