algoritma booth

Download Algoritma Booth

Post on 18-Oct-2015

295 views

Category:

Documents

14 download

Embed Size (px)

DESCRIPTION

Algoritma yang di gunakan untuk menghitung perkalian atau pembagian pada bilangan biner, karena pada bilangan biner akan lebih mudah jika kita gunakan ini

TRANSCRIPT

  • *PERKALIANOperasi Aritmatika

  • *PENGALIANOperasi pengalian lebih rumit dibandingkan operasi penjumlahan atau pengurangan, baik dalam hardware maupun softwareAda beberapa jenis algoritma yang digunakan dalam bermacam-macam komputer

  • *PENGALIAN UNSIGNED INTEGER

    1011Multiplicand (11)x1101Mutiplier (13)10110000Partial1011Product101110001111Product (143)

  • *PENGALIAN UNSIGNED INTEGERPengalian meliputi pembentukan beberapa perkalian parsial untuk setiap digit dalam multiplier. Perkalian parsial ini kemudian dijumlahkan untuk mendapatkan hasil pengalian akhirBila bit multiplier sama dengan 0, maka hasil pengaliannya 0. Bila bit multiplier 1, maka hasil pengaliannya sama dengan mutiplierHasil pengalian akhir diperoleh dengan menjumlahkan perkalian parsial tersebut. Setiap hasil perkalian parsial yang berurutan digeser satu posisi ke kiri relatif terhadap hasil perkalian sebelumnya.Pengalian dua buah integer biner n-bit menghasilkan hasil perkalian sampai 2n-bit

  • *PENGALIAN UNSIGNED INTEGERControl Logic membaca bit-bit multiplier satu persatuBila Q0 = 1, multiplicand ditambahkan ke register A; hasilnya disimpan ke register A; setelah itu seluruh bit di register C, A dan Q digeser ke kanan 1 bit.Bila Q0 = 0, tidak terjadi penambahan; seluruh bit di register C, A dan Q digeser ke kanan 1 bit.Proses tersebut dilakukan secara berulang untuk setiap bit multiplierHasil perkalian akhir tersimpan di register A dan Q.

  • *PENGALIAN UNSIGNED INTEGER

  • *PENGALIAN UNSIGNED INTEGER

  • *PENGALIAN KOMPLEMEN-2Dengan algoritma pengalian di atas1011 * 1101 = 1000 1111Perkalian unsigned integer : 11 * 13 = 143Perkalian komplemen-2 : -5 * -3 = -113perkalian tidak berfungsi jika multiplicand dan/atau multiplier-nya negatif

  • *PERKALIAN UNSIGN & KOMPLEMEN-2Ada beberapa cara untuk menangani hal tersebut:konversi multiplier dan multicand jadi positif, dikalikan; cari komplemen-2 dari hasilnya jika tanda multiplier dan multiplicand berbedaMenggunakan algoritma lain yang tidak memerlukan transformasi, misalnya Algoritma Booth

  • *ALGORITMA BOOTHmemiliki kelebihan kecepatan proses perkaliannya, relatif terhadap pendekatan langsungterdapat register Q(multiplier), M(multiplicand), A(accumulator), dan register 1-bit di kanan Q yg ditandai dengan Q-1hasil perkalian tersimpan di A dan Q

  • *ALGORITMA BOOTHA dan Q-1 diinisialisasi 0control logic memeriksa bit-bit multiplier satu-persatu beserta bit di kanannyaJika kedua bit sama (1-1 atau 0-0), maka seluruh bit di A, Q dan Q-1 digeser 1-bit ke kananjika kedua bit berbeda, multiplicand ditambahkan (0-1) atau dikurangkan (1-0) ke register A, kemudian digeser ke kananpergeseran menggunakan Arithmetic Shiftcontoh : 1011 0101 1101 1010

  • *ALGORITMA BOOTH

  • *ALGORITMA BOOTHcontoh : 0111 * 0011 = 0001 0101

  • *ALGORITMA BOOTH

  • *PEMBAGIANOperasi Aritmatika

  • T.Informatika UAD*PEMBAGIAN-UNSIGNED BINARY

    13111471137334

  • *PEMBAGIAN-UNSIGNED BINARY

  • *PEMBAGIAN-UNSIGNED BINARY1001 0011 : 1011 = 000 1101 + 0100

    E A Q0 1 0 0 1 0 0 1 1 Initial1 0 0 1 0 0 1 1 0 Shift Left 0 1 0 11 0 1 1 1 A A - M1 0 1 1 1 0 1 1 1 Set Q00 1 1 1 0 1 1 1 0 Shift Left 0 1 0 11 0 0 1 1 A A - M1 0 0 1 1 1 1 1 1 Set Q00 0 1 1 1 1 1 1 0 Shift Left 0 1 0 10 1 1 0 0 A A - M 1 0 1 11 0 1 1 1 1 1 1 0 A A + M (restore A)0 1 1 1 1 1 1 0 0 Shift Left 0 1 0 11 0 1 0 0 A A - M1 0 1 0 0 1 1 0 1 Set Q0M = 1011M = 0101 (2nd-c)remainderquotient

  • *PEMBAGIAN KOMPLEMEN-2Muatkan divisor ke M, dividend ke A dan Q. dividend diekspresikan sbg komplemen-2 2n-bit.Geser A dan Q 1-bit ke kiriBila M dan A memiliki tanda yg sama, lakukan A A M; bila tandanya beda, A A + MOperasi tsb akan berhasil bila tanda A sesudah dan sebelum operasi samabila berhasil (A dan Q = 0), set Q0 1bila gagal (A dan Q 0), reset Q0 0 dan simpan A sebelumnyaUlangi langkah 2 sampai 4 utk setiap posisi bit di QBila tanda divisor dan dividend sama maka quotient ada di Q, jika tidak quotient adalah komplemen-2 dari Q.Remainder ada di A.

  • *PEMBAGIAN KOMPLEMEN-2

  • *PEMBAGIAN KOMPLEMEN-2

  • *PEMBAGIAN KOMPLEMEN-2

  • *PEMBAGIAN KOMPLEMEN-2(-7)/(3) dan (7)/(-3) akan menghasilkan remainder yang berbeda. Hal ini disebabkan operasi pembagian didefinisikan sebagaiD = Q * V + RdenganD = dividendQ = quotientV = divisorR = remainder

  • Daftar Pustaka:William Stallings, Computer and ArchitectureE. Haodudin Nurkifli, Universitas Ahmad Dahlan

Recommended

View more >