Pengali biner

Pengali atau Multiplier adalah rangkaian elektronika digital yang berada dalam berbagai perangkat elektronik seperti komputer yang berfungsi untuk mengalikan dua buah bilangan dalam sistem bilangan biner, dwi-an atau basis 2. Jenis rangkaian ini biasanya merupakan bagian dari ALU (Arithmetic Logical Unit) di dalam mikroprosesor atau CPU (Central Processing Unit atau otak dari sebuah komputer) . Namun, rangkaian ini bisa dibuat secara tersendiri untuk keperluan tertentu, dan bisa diprogram secara perangkat keras di dalam FPGA.

Sejarah

Antara tahun 1947 dan 1949, Arthur Alec Robinson bekerja untuk English Electric , sebagai mahasiswa magang, dan kemudian sebagai insinyur pengembangan. Yang terpenting selama periode ini ia belajar untuk gelar PhD di Universitas Manchester, di mana ia bekerja sebagai desainer sirkuit untuk pengali keras komputer Mark 1 lawas . Namun, hingga akhir tahun 1970-an, sebagian besar komputer mini tidak memiliki instruksi perkalian, sehingga programmer menggunakan "perkalian rutin"  yang berulang kali menggeser dan mengumpulkan hasil parsial, sering kali ditulis menggunakan pelepasan loop . Komputer bingkai utama memiliki instruksi perkalian, tetapi mereka melakukan jenis pergeseran dan penambahan yang sama sebagai "perkalian rutin".

Mikroprosesor lawas juga tidak memiliki instruksi perkalian. Meskipun instruksi perkalian menjadi umum dengan generasi 16-bit,  setidaknya dua prosesor 8-bit memiliki instruksi perkalian: Motorola 6809 , diperkenalkan pada tahun 1978,  dan keluarga Intel MCS-51 , dikembangkan pada tahun 1980, dan kemudian mikroprosesor Atmel AVR 8-bit modern yang ada di pengandali mikro ATMega, ATTiny dan ATXMega.

Karena lebih banyak transistor per cip yang tersedia karena integrasi berskala lebih besar, menjadi mungkin untuk menempatkan cukup banyak penjumlah pada satu chip untuk menjumlahkan semua produk parsial sekaligus, daripada menggunakan kembali satu penjumlah untuk menangani setiap produk parsial satu per satu.

Karena beberapa algoritma pemrosesan sinyal digital umum menghabiskan sebagian besar waktunya untuk melakukan perkalian, perancang prosesor sinyal digital mengorbankan area chip yang cukup besar agar perkalian dapat dilakukan secepat mungkin; unit perkalian-akumulasi siklus tunggal sering kali menghabiskan sebagian besar area chip pada DSP awal.

Perkalian biner

Berikut contoh visual dari metode yang diajarkan di sekolah untuk mengalikan angka desimal didasarkan pada perhitungan hasil perkalian parsial, menggesernya ke kiri, lalu menjumlahkannya. Bagian yang paling sulit adalah memperoleh hasil perkalian parsial, karena hal itu melibatkan perkalian angka panjang dengan satu digit (dari 0 hingga 9):

     123 
   × 456 
   ===== 
     738 (ini adalah 123 × 6) 
    615 (ini adalah 123 × 5, digeser satu posisi ke kiri) 
   492 (ini adalah 123 × 4, digeser dua posisi ke kiri) 
   ===== 
   56088

Komputer biner melakukan perkalian yang sama persis seperti yang dilakukan angka desimal, tetapi dengan menggunakan bilangan biner berbasis 2. Dalam pengodean biner, setiap angka panjang dikalikan dengan satu digit (baik 0 atau 1), dan itu jauh lebih mudah daripada dalam desimal, karena hasil perkalian dengan 0 atau 1 hanya menghasilkan 0 atau angka yang sama, 0 atau 1. Oleh karena itu, perkalian dua angka biner menghasilkan perhitungan hasil perkalian parsial (yaitu 0 atau angka pertama), menggesernya ke kiri, lalu menjumlahkannya (tentu dengan penjumlahan biner):

       1011 (ini adalah biner yang setara dengan 11 pada bilangan desimal) 
     × 1110 (ini adalah biner yang setara dengan 14 pada bilangan desimal) 
     ====== 
       0000 (ini adalah 1011 × 0) 
      1011 (ini adalah 1011 × 1, digeser satu posisi ke kiri) 
     1011 (ini adalah 1011 × 1, digeser dua posisi ke kiri) 
    1011 (ini adalah 1011 × 1, digeser tiga posisi ke kiri) 
  ========= 
   10011010 (ini adalah biner untuk desimal 154)

Ini jauh lebih sederhana dibandingkan sistem desimal, karena tidak ada tabel perkalian yang perlu diingat: hanya pergeseran dan penjumlahan.

Metode ini secara matematis benar dan memiliki keuntungan bahwa CPU kecil dapat melakukan perkalian dengan menggunakan fitur shift dan add dari unit logika aritmatikanya daripada sirkuit khusus. Namun, metode ini lambat karena melibatkan banyak penjumlahan antara. Penjumlahan ini memakan waktu. Pengganda yang lebih cepat dapat direkayasa untuk melakukan penjumlahan yang lebih sedikit; prosesor modern dapat mengalikan dua angka 64-bit dengan 6 penjumlahan (daripada 64), dan dapat melakukan beberapa langkah secara paralel.

Masalah kedua adalah bahwa metode sekolah dasar menangani tanda dengan aturan terpisah (" dengan menghasilkan ", " dengan − menghasilkan −", dst.). Komputer modern menyematkan tanda angka di dalam angka itu sendiri, biasanya dalam representasi komplemen dua . Hal itu memaksa proses perkalian untuk disesuaikan guna menangani angka komplemen dua, dan itu sedikit lebih memperumit proses. Demikian pula, prosesor yang menggunakan komplemen satu , tanda dan besaran , IEEE-754 atau representasi biner lainnya memerlukan penyesuaian khusus pada proses perkalian.

Beberapa macam teknik atau cara dapat dipakai untuk merealisasikan operasi perkalian aritmetika ini. Salah satunya adalah dengan mengalikan secara parsiel masing masing bit, kemudian menjumlahkan semua hasil dari perkalian parsiel tersebut. Hal ini mirip dengan proses perkalian bilangan desimal (bilangan basis-10) yang dilakukan oleh murid Sekolah Dasar.

Jika dua buah bilangan biner, a dan b, masing-masing 2 bit (membentuk angka 00, 01, 10, dan 11) dikalikan satu sama lain, maka akan kita peroleh hasil perkalian dalam bentuk bilangan biner 4 bit, seperti tampak pada tabel di bawah ini. Bilangan a ada di kolom paling kiri, dan bilangan b ada di baris paling atas, sementara hasil kalinya ada di dalam masing-masing sel.

Tabel perkalian biner 2-bit:

×	00	01	10	11
00	0000	0000	0000	0000
01	0000	0001	0010	0011
10	0000	0010	0100	0110
11	0000	0011	0110	1001

Cara lain dalam melihat operasi perkalian ini adalah dengan menyatakan bilangan pertama sebagai angka 2 bit a[1] dan a[0], sementara bilangan kedua dinyatakan dengan b[1] dan b[0]. Maka hasil kali parsielnya ada 4 buah: p0[0], p0[1], p1[0], dan p1[1] dengan:

${\begin{array}{c c c c}\\p0[0]&=b[0]\times a[0]\quad &p0[1]&=b[0]\times a[1]\\p1[0]&=b[1]\times a[0]\quad &p1[1]&=b[1]\times a[1]\\\end{array}}$

Hasil kali akhir dari bilangan a dan b akan membentuk bilangan P 4 bit: P[3] P[2] P[1] P[0] dengan penjumlahan parsiel sebagai berikut:

${\begin{array}{c c c c}\\&&p0[1]&p0[0]\\&p1[1]&p1[0]&0\\\hline P[3]&P[2]&P[1]&P[0]\end{array}}$

Untuk bilangan 8 bit: a[7:0] dan b[7:0], banyaknya hasil kali parsiel juga ada 8 buah:

${\begin{array}{c c c c}\\p0[7:0]&=a[0]\times b[7:0]&=\{8\{a[0]\}\}\And &b[7:0]\\p1[7:0]&=a[1]\times b[7:0]&=\{8\{a[1]\}\}\And &b[7:0]\\p2[7:0]&=a[2]\times b[7:0]&=\{8\{a[2]\}\}\And &b[7:0]\\p3[7:0]&=a[3]\times b[7:0]&=\{8\{a[3]\}\}\And &b[7:0]\\p4[7:0]&=a[4]\times b[7:0]&=\{8\{a[4]\}\}\And &b[7:0]\\p5[7:0]&=a[5]\times b[7:0]&=\{8\{a[5]\}\}\And &b[7:0]\\p6[7:0]&=a[6]\times b[7:0]&=\{8\{a[6]\}\}\And &b[7:0]\\p7[7:0]&=a[7]\times b[7:0]&=\{8\{a[7]\}\}\And &b[7:0]\\\end{array}}$

Hasil akhirnya merupakan penjumlahan dari semua hasil kali parsiel:

${\begin{array}{c c c c c c c c c c c c c c c c}\\&&&&&&&&p0[7]&p0[6]&p0[5]&p0[4]&p0[3]&p0[2]&p0[1]&p0[0]\\&&&&&&&p1[7]&p1[6]&p1[5]&p1[4]&p1[3]&p1[2]&p1[1]&p1[0]&\\&&&&&&p2[7]&p2[6]&p2[5]&p2[4]&p2[3]&p2[2]&p2[1]&p2[0]&&\\&&&&&p3[7]&p3[6]&p3[5]&p3[4]&p3[3]&p3[2]&p3[1]&p3[0]&&&\\&&&&p4[7]&p4[6]&p4[5]&p4[4]&p4[3]&p4[2]&p4[1]&p4[0]&&&&\\&&&p5[7]&p5[6]&p5[5]&p5[4]&p5[3]&p5[2]&p5[1]&p5[0]&&&&&\\&&p6[7]&p6[6]&p6[5]&p6[4]&p6[3]&p6[2]&p6[1]&p6[0]&&&&&&\\&p7[7]&p7[6]&p7[5]&p7[4]&p7[3]&p7[2]&p7[1]&p7[0]&&&&&&&\\\hline P[15]&P[14]&P[13]&P[12]&P[11]&P[10]&P[9]&P[8]&P[7]&P[6]&P[5]&P[4]&P[3]&P[2]&P[1]&P[0]\\\end{array}}$