İkili çarpan - Binary multiplier

Bir ikili çarpan bir bir elektronik devre kullanılan dijital elektronik bir şekilde, bilgisayar için, çarpma iki ikili sayılar .

Sayısal bir çarpanı uygulamak için çeşitli bilgisayar aritmetik teknikleri kullanılabilir. Çoğu teknik, daha sonra ikili toplayıcılar kullanılarak bir araya getirilen kısmi ürün kümesinin hesaplanmasını içerir . Bu işlem, 2 tabanlı ( ikili ) bir sayı sistemi kullanması dışında uzun çarpma işlemine benzer .

Tarih

1947 ve 1949 yılları arasında Arthur Alec Robinson English Electric Ltd'de öğrenci çırak ve ardından geliştirme mühendisi olarak çalıştı. Bu dönemde çok önemli olan, Manchester Üniversitesi'nde doktora derecesi için çalıştı ve burada Mark 1 bilgisayarı için donanım çarpanının tasarımı üzerinde çalıştı. [3] Bununla birlikte, 1970'lerin sonlarına kadar, çoğu minibilgisayarda çarpma talimatı yoktu ve bu nedenle programcılar, tekrar tekrar değişen ve kısmi sonuçları biriktiren , genellikle döngü çözme kullanılarak yazılan bir "çarpma rutini" kullandılar . Anabilgisayarların çoklu yönergeleri vardı, ancak aynı tür kaymaları yaptılar ve "çarpma rutini" olarak eklediler.

Erken mikroişlemcilerde ayrıca çarpma talimatı yoktu. Çarpma talimatı 16 bit nesil ile yaygın hale gelse de, en az iki 8 bit işlemcide çarpma talimatı vardır: 1978'de tanıtılan Motorola 6809 ve 1980'de geliştirilen Intel MCS-51 ailesi ve daha sonra modern Atmel AVR ATMega, ATTiny ve ATXMega mikro denetleyicilerinde bulunan 8 bit mikroişlemciler.

Daha büyük ölçekli entegrasyon nedeniyle çip başına daha fazla transistör kullanılabilir hale geldikçe, her bir kısmi ürünü tek tek işlemek için tek bir toplayıcıyı yeniden kullanmak yerine, tüm kısmi ürünleri bir kerede toplamak için tek bir yongaya yeterli sayıda toplayıcı koymak mümkün hale geldi.

Bazı yaygın dijital sinyal işleme algoritmaları zamanlarının çoğunu çarpma işlemine harcadıkları için, dijital sinyal işlemcisi tasarımcıları çarpma işlemini olabildiğince hızlı yapmak için önemli miktarda çip alanından fedakarlık eder; Tek çevrimli çoğalma-birikme birimi, genellikle erken DSP'lerin çip alanının çoğunu kullanır.

ikili uzun çarpma

Okulda ondalık sayıları çarpmak için öğretilen yöntem, kısmi çarpımları hesaplamaya, bunları sola kaydırmaya ve ardından toplamaya dayanır. En zor kısım, kısmi ürünleri elde etmektir, çünkü bu, uzun bir sayıyı bir basamakla (0'dan 9'a kadar) çarpmayı içerir:

     123
   x 456
   =====
     738  (this is 123 x 6)
    615   (this is 123 x 5, shifted one position to the left)
 + 492    (this is 123 x 4, shifted two positions to the left)
   =====
   56088

İkili bir bilgisayar, ondalık sayılarla tam olarak aynı çarpma işlemini yapar, ancak ikili sayılarla. İkili kodlamada, her uzun sayı bir basamakla (0 veya 1) çarpılır ve bu, 0 veya 1'in çarpımı yalnızca 0 veya aynı sayı olduğundan, ondalık sayıdan çok daha kolaydır. Bu nedenle, iki ikili sayının çarpımı, kısmi çarpımların (0 veya ilk sayı olan) hesaplanmasına, bunları sola kaydırmaya ve sonra bunları bir araya toplamaya (elbette ikili bir toplama) gelir:

       1011   (this is binary for decimal 11)
     x 1110   (this is binary for decimal 14)
     ======
       0000   (this is 1011 x 0)
      1011    (this is 1011 x 1, shifted one position to the left)
     1011     (this is 1011 x 1, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   10011010   (this is binary for decimal 154)

Bu, ondalık sistemdekinden çok daha basittir, çünkü hatırlanacak bir çarpma tablosu yoktur: sadece kaydırır ve ekler.

Bu yöntem matematiksel olarak doğrudur ve küçük bir CPU'nun özel bir devre yerine aritmetik mantık biriminin kaydırma ve ekleme özelliklerini kullanarak çarpma işlemini gerçekleştirebilmesi avantajına sahiptir. Ancak, birçok ara ekleme içerdiğinden yöntem yavaştır. Bu eklemeler zaman alıcıdır. Daha az ekleme yapmak için daha hızlı çarpanlar tasarlanabilir; modern bir işlemci 64 bitlik iki sayıyı 6 eklemeyle (64 yerine) çarpabilir ve birkaç adımı paralel olarak yapabilir.

İkinci sorun, temel okul yönteminin işareti ayrı bir kuralla ele almasıdır ("+ ile + verir +", "+ ile - verir -" vb.). Modern bilgisayarlar, sayının işaretini, genellikle ikisinin tümleyen gösteriminde , sayının kendisine yerleştirir . Bu, çarpma işlemini ikinin tümleyen sayılarını işlemek için uyarlamaya zorlar ve bu da işlemi biraz daha karmaşık hale getirir. Benzer şekilde, tümleyen , işaret ve büyüklük , IEEE-754 veya diğer ikili gösterimleri kullanan işlemciler , çarpma işleminde özel ayarlamalar gerektirir.

işaretsiz tamsayılar

Örneğin, iki işaretsiz sekiz bit tamsayıyı birlikte çarpmak istediğimizi varsayalım : a [7:0] ve b [7:0]. Biz çarpılan her bit için sekiz bir bitlik çarpımı tek gerçekleştirerek sekiz kısmi ürünler üretebilir bir :

 p0[7:0] = a[0] × b[7:0] = {8{a[0]}} & b[7:0]
 p1[7:0] = a[1] × b[7:0] = {8{a[1]}} & b[7:0]
 p2[7:0] = a[2] × b[7:0] = {8{a[2]}} & b[7:0]
 p3[7:0] = a[3] × b[7:0] = {8{a[3]}} & b[7:0]
 p4[7:0] = a[4] × b[7:0] = {8{a[4]}} & b[7:0] 
 p5[7:0] = a[5] × b[7:0] = {8{a[5]}} & b[7:0]
 p6[7:0] = a[6] × b[7:0] = {8{a[6]}} & b[7:0]
 p7[7:0] = a[7] × b[7:0] = {8{a[7]}} & b[7:0]

burada {8{a[0]}}, a[0] (a'nın 0. biti) 8 kez tekrar etmek anlamına gelir ( Verilog gösterimi).

Ürünümüzü elde etmek için, burada gösterildiği gibi sekiz kısmi ürünümüzün tümünü toplamamız gerekir:

                                                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] 0
                                  + p2[7] p2[6] p2[5] p2[4] p2[3] p2[2] p2[1] p2[0] 0     0
                            + p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0     0     0
                      + p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0     0     0     0
                + p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0     0     0     0     0
          + p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0     0     0     0     0     0
    + p7[7] p7[6] p7[5] p7[4] p7[3] p7[2] p7[1] p7[0] 0     0     0     0     0     0     0
-------------------------------------------------------------------------------------------
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]

Başka bir deyişle, P [15:0], son işaretsiz 16 bitlik ürünümüzü üretmek için p 0, p 1 << 1, p 2 << 2 ve benzerlerinin toplanmasıyla üretilir .

işaretli tamsayılar

Eğer b bir olmuştu imzalı bir tamsayı yerine işaretsiz tamsayı, daha sonra kısmi ürünleri toplayarak önce ürünün genişliğine kadar işareti uzatıldı olması gerekir. Eğer bir imzalı tamsayı olmuştu, o zaman kısmi ürün p7 nihai toplamından çıkarılır, yerine kendisine eklenmesi gerekir olacaktır.

Yukarıdaki dizi çarpanı , çarpım terimlerinin birkaçını ters çevirerek ve ilk kısmi çarpım teriminin soluna bir tane ekleyerek ikinin tümleyen gösterim işaretli sayılarını desteklemek için değiştirilebilir :

                                                    1  ~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]   0
                                         ~p2[7] +p2[6] +p2[5] +p2[4] +p2[3] +p2[2] +p2[1] +p2[0]   0      0
                                  ~p3[7] +p3[6] +p3[5] +p3[4] +p3[3] +p3[2] +p3[1] +p3[0]   0      0      0
                           ~p4[7] +p4[6] +p4[5] +p4[4] +p4[3] +p4[2] +p4[1] +p4[0]   0      0      0      0
                    ~p5[7] +p5[6] +p5[5] +p5[4] +p5[3] +p5[2] +p5[1] +p5[0]   0      0      0      0      0
             ~p6[7] +p6[6] +p6[5] +p6[4] +p6[3] +p6[2] +p6[1] +p6[0]   0      0      0      0      0      0
   1  +p7[7] ~p7[6] ~p7[5] ~p7[4] ~p7[3] ~p7[2] ~p7[1] ~p7[0]   0      0      0      0      0      0      0
 ------------------------------------------------------------------------------------------------------------
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]

Burada ~p, p'nin tamamlayıcısını (zıt değer) temsil eder.

Yukarıdaki bit dizisinde gösterilmeyen ve açık olmayan birçok basitleştirme vardır. Tamamlanan bir bitin ardından tamamlanmayan bitlerin dizileri, işaret uzantısından kaçınmak için ikinin tamamlayıcı hilesini uygular. p7 dizisi (tamamlanmayan bitin ardından tüm tamamlanan bitler), bu terimi çıkarmamızdır, bu nedenle başlangıçta hepsi reddedilmiştir (ve en az anlamlı konuma 1 eklenmiştir). Her iki dizi türü için de son bit çevrilir ve doğrudan MSB'nin altına örtük bir -1 eklenmelidir. 0 bit konumunda (LSB) p7 için ikisinin tümleyen olumsuzlamasından ve 7 ila 14 arasındaki bit sütunlarındaki tüm -1'ler (her bir MSB'nin bulunduğu yerde) birlikte eklendiğinde, bunlar tek 1'e basitleştirilebilir. "sihirli bir şekilde" sola doğru yüzüyor. MSB'yi çevirmenin neden bize işaret uzantısından tasarruf ettiğinin bir açıklaması ve kanıtı için bir bilgisayar aritmetiği kitabına bakın.

Kayan nokta sayıları

İkili bir kayan sayı, bir işaret biti, önemli bitler (anlamlı olarak bilinir) ve üs bitleri (basitlik için taban ve kombinasyon alanını dikkate almayız) içerir. Her işlenenin işaret bitleri, cevabın işaretini almak için XOR'lanır. Ardından, sonucun üssünü elde etmek için iki üs eklenir. Son olarak, her işlenenin anlamlısının çarpımı sonucun anlamlısını döndürür. Ancak, ikili çarpmanın sonucu belirli bir kesinlik için toplam bit sayısından yüksekse (örneğin 32, 64, 128), yuvarlama gereklidir ve üs uygun şekilde değiştirilir.

Donanım uygulaması

Çarpma işlemi 3 adıma ayrılabilir:

kısmi ürün üreten
kısmi ürünü azaltmak
bilgisayar nihai ürünü

Daha eski çarpan mimarileri, her bir kısmi ürünü, genellikle döngü başına bir kısmi ürünü toplamak için bir kaydırıcı ve akümülatör kullandı ve kalıp alanı için değiş tokuş hızı. Modern çarpan mimarileri , kısmi ürünleri tek bir döngüde toplamak için (Modified) Baugh-Wooley algoritmasını , Wallace ağaçlarını veya Dadda çarpanlarını kullanır. Wallace ağaç uygulamasının performansı bazen iki çarpandan birini kodlayan değiştirilmiş Booth ile iyileştirilir , bu da toplanması gereken kısmi ürünlerin sayısını azaltır.

Hız için, kaydırma ve toplama çarpanları hızlı bir toplayıcı gerektirir (dalgalanma taşımadan daha hızlı bir şey).

Bir "tek döngü" çarpanı (veya "hızlı çarpan") saf kombinasyonel mantıktır .

Hızlı bir çarpanda, kısmi ürün indirgeme süreci genellikle çarpanın gecikmesine, gücüne ve alanına en fazla katkıda bulunur. Hız için, "kısmi ürünü azalt" aşamaları tipik olarak kompresörlerden oluşan bir taşıma-koruyucu toplayıcı olarak uygulanır ve "son ürünü hesapla" adımı hızlı bir toplayıcı olarak uygulanır (dalgalanma-taşıma işleminden daha hızlı bir şey).

Birçok hızlı çarpan, statik CMOS'ta uygulanan kompresörler ("3:2 kompresörler") olarak tam toplayıcılar kullanır . Aynı alanda daha iyi performans elde etmek veya daha küçük bir alanda aynı performansı elde etmek için, çarpan tasarımları 7:3 kompresörler gibi daha yüksek dereceli kompresörler kullanabilir; kompresörleri daha hızlı mantıkta uygulamak (örneğin iletim kapısı mantığı, geçiş transistör mantığı, domino mantığı ); kompresörleri farklı bir düzende bağlayın; veya bazı kombinasyonlar.

Örnek devreler

2 bitlik 2 bitlik ikili çarpan

Ayrıca bakınız

Booth'un çarpma algoritması
Sigortalı çarpma-ekleme
Wallace ağacı
Karmaşık logaritmalar ve üsteller için BKM algoritması
KOCHANSKI çarpma için modüler çarpma
Mantıksal kaydırma sola

Referanslar

Hennessy, John L.; Patterson, David A. (1990). "Kısım A.2, Kısım A.9". Bilgisayar Mimarisi: Nicel Bir Yaklaşım . Morgan Kaufmann Publishers, Inc. s. A–3..A–6, A–39..A–49. ISBN'si 978-0-12383872-8.

Languages

In other projects