Toplayıcı

Toplayıcı (İngilizce: adder), iki ikili sayıyı toplayan sayısal bir birleşik devredir. İşlemcilerde aritmetik mantık biriminin temel parçasıdır; toplamanın yanı sıra çıkarma, çarpma ve adres hesabında da kullanılır.

En yalın toplayıcı olan yarım toplayıcı iki biti toplar, tam toplayıcı bunlara alttan gelen eldeyi de ekler. Çok bitlik sayılar tam toplayıcıların birleştirilmesiyle toplanır. En basit düzenleme olan dalga eldeli toplayıcıda elde basamaktan basamağa geçtiği için gecikme bit sayısıyla doğrusal artar. Elde atlamalı, eldeyi önceden üreten, elde ile seçmeli ve koşut önek toplayıcılar bu gecikmeyi daha çok donanım karşılığında kısaltır.

Toplayıcı, ikinci sayının ikiye tümleyeni alınarak çıkarma da yapar; hızlı çarpıcılar ise çok sayıda sayıyı 3:2 sıkıştırıcılarla toplar. İkili toplayıcının ilk örneklerinden biri 1937'de rölelerle kurulmuştur; hızlı elde yöntemleri 1950'lerden başlayarak geliştirilmiştir.

Yarım toplayıcı (İngilizce: half adder), iki bir bitlik sayıyı (A ve B) toplayarak bir toplam biti (T) ve bir elde biti (e) üreten en basit toplayıcıdır. Alttan gelen bir elde girişini hesaba katmadığından tek başına yalnızca en düşük basamağın toplanmasında işe yarar.

İki bit elle toplanırken dört durum ortaya çıkar: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 ve 1 + 1 = 10. Son durumda sonuç tek basamağa sığmaz; toplam basamağına 0 yazılır ve bir üst basamağa 1 elde aktarılır. Bu durumlardan toplam bitinin yalnız iki girişten biri 1 olduğunda 1 olduğu görülür; bu, iki girişin birbirinden farklı olup olmadığını sınayan Dışlayan VEYA işlemidir. Elde biti ise yalnız iki giriş birden 1 olduğunda 1 olur ve VE işlemine karşılık gelir. Yarım toplayıcı bu yüzden bir Dışlayan VEYA kapısı ile bir VE kapısından kurulur; toplam biti yalnız VE, VEYA ve DEĞİL kapılarıyla T = A′B + AB′ biçiminde de yazılabilir.

• Toplam: T = A ⊕ B
• Elde: e = A · B

Yarım toplayıcının doğruluk tablosu

Girişler	Çıkışlar
A	B	T	e
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Tam toplayıcı (İngilizce: full adder), iki toplanan bitin (A, B) yanı sıra bir önceki basamaktan gelen elde girişini (e_g) de toplayarak bir toplam biti (T) ve bir elde çıkışı (e_ç) üretir. Elde girişini de işleyebilmesi onu çok bitlik toplamanın yapı taşı yapar.

Tam toplayıcının iki çıkışı üç girişe bakılarak tanımlanır. Toplam biti, girişlerden yalnız biri ya da üçü birden 1 olduğunda 1 olur; başka bir deyişle 1 olan girişlerin sayısı tek olduğunda. Elde çıkışı ise girişlerden en az ikisi 1 olduğunda 1 olur. Örneğin üç giriş de 1 iken toplam 1 + 1 + 1 = 11 olur; toplam biti de elde çıkışı da 1'dir. Elde çıkışı girişlerin çoğunluğuna baktığı için bu devreye çoğunluk kapısı da denir.

Elde çıkışı iki eşdeğer biçimde yazılabilir. Doğrudan tanımdan e_ç = A·B + A·e_g + B·e_g elde edilir. Üretme sinyali g = A·B ve geçirme sinyali p = A ⊕ B tanımlandığında ise e_ç = g + p·e_g olur: iki toplanan bitin ikisi de 1 ise elde kendiliğinden üretilir, yalnız biri 1 ise alttan gelen elde bir üst basamağa geçirilir.

• Toplam: T = A ⊕ B ⊕ e_g
• Elde çıkışı: e_ç = (A · B) + (e_g · (A ⊕ B))

Tam toplayıcının doğruluk tablosu

Girişler	Çıkışlar
A	B	eg	T	eç
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Bu ikinci yazılış, bir tam toplayıcının iki yarım toplayıcı ve bir VEYA kapısıyla neden kurulabildiğini de gösterir. Birinci yarım toplayıcı A ile Byi toplayarak p ve g sinyallerini üretir. İkinci yarım toplayıcı p ile e_gyi toplar; toplam çıkışı tam toplayıcının toplam biti olur, elde çıkışı ise p·e_g terimini verir. İki yarım toplayıcının eldeleri bir VEYA kapısında birleştirilerek elde çıkışı bulunur.

Tam toplayıcı doğrudan mantık kapılarıyla kurulduğunda CMOS teknolojisinde 32 transistör gerekir. Toplam çıkışı elde çıkışının teriminden yararlanılarak yeniden düzenlendiğinde ve pMOS ağı nMOS ağının tümleyeni yerine onun aynısı olarak kurulduğunda devre 28 transistöre iner. Bu, toplama işlevinin simetrik olmasıyla mümkündür; bir tam toplayıcının bütün girişleri tersine çevrildiğinde bütün çıkışları da tersine döner. Aynı özellik sayesinde dalga eldeli bir toplayıcıda basamakların yarısı tersine çevrilmiş verilerle çalıştırılarak elde yolundaki DEĞİL kapıları azaltılabilir. Bu devrelerde en uzun yol elde girişinden elde çıkışına uzandığı için o yoldaki transistörler büyütülür, toplam devresi ise en küçük boyda tutulur.

n bitlik iki sayıyı toplamak için n tane tam toplayıcı birleştirilir. Bu birleştirmenin farklı düzenlemeleri, hız ile devre karmaşıklığı arasında değişik dengeler sunar.

Dalga eldeli toplayıcı (İngilizce: ripple-carry adder), tam toplayıcıların art arda bağlanmasıyla oluşur: her tam toplayıcının elde çıkışı bir üst basamağın elde girişine verilir. Adını, eldenin en düşük basamaktan en yükseğe doğru basamak basamak "dalga" gibi yayılmasından alır. En yalın düzenlemedir ama yavaştır: her basamak alttan gelen eldeyi beklediğinden toplam gecikme bit sayısı n ile doğru orantılı (O(n)) büyür.

Manchester elde zinciri, dalga eldeli toplayıcının elde yolunu mantık kapıları yerine anahtar gibi çalışan transistörlerle kuran bir düzenlemedir. Her basamakta eldenin üretildiği, geçirildiği ya da sıfırlandığı durumlara karşılık gelen üç anahtar bulunur ve bunlardan her an yalnız biri kapalıdır. Anahtarların hepsi toplamanın başında aynı anda kurulduğu için elde her basamakta yalnızca bir anahtar gecikmesi görür. Yöntemi T. Kilburn, D. B. G. Edwards ve D. Aspinall 1959 ve 1960'ta yayımlamıştır; ilk kez Manchester Üniversitesi'nde geliştirilen Atlas bilgisayarında kullanılmıştır. 1960 tarihli çalışmada 24 basamaklı bir toplamanın 200 nanosaniyede tamamlandığı bildirilmiştir.

Zincirin direnci ve sığası uzunlukla birlikte arttığından gecikme zincir uzunluğunun karesiyle büyür. Bu yüzden uzun zincirler bölünür ve araya DEĞİL kapıları konarak gecikme yeniden doğrusal hâle getirilir.

Elde atlamalı toplayıcı (İngilizce: carry-skip adder ya da carry-bypass adder), eldeyi art arda gelen basamak öbeklerinin üzerinden atlatarak dalga eldeli toplayıcının gecikmesini kısaltır. Bir basamakta toplanan iki bitten yalnız biri 1 ise geçirme sinyali p 1 olur ve basamağın elde çıkışı elde girişine eşit olur. Toplayıcı bloklara bölünür ve her blok kendi içinde dalga eldeli olarak çalışır. Bloktaki bütün geçirme sinyallerinin VE işlemiyle bir blok geçirme sinyali üretilir; bu sinyal ancak bloğun bütün basamaklarında p = 1 iken 1 olur. Bloğun çıkışındaki bir çoklayıcı, blok geçirme sinyali 1 ise bloğa giren eldeyi, değilse bloğun kendi içinde hesapladığı eldeyi bir sonraki bloğa verir. Blok geçirme sinyalleri doğrudan toplanan sayılardan hesaplandığı için toplamanın başında hazırdır.

En kötü durumda elde ilk basamakta üretilir, ilk bloğun içinde dalgalanır, aradaki blokları atlar ve son bloğun içinde yeniden dalgalanarak en yüksek basamağa ulaşır. Blok boyları eşit tutulduğunda gecikme bit sayısıyla yine doğrusal artar ama artışın eğimi küçülür. Birkaç bitlik toplayıcılarda dalga eldeli yapı daha hızlıdır; iki yapının gecikmelerinin eşitlendiği nokta çoğunlukla dört ile sekiz bit arasındadır. I. Koren'in kapı gecikmesi (ΔG) birimiyle yaptığı hesapta 32 bitlik dalga eldeli toplayıcının en uzun elde yolu 62 ΔG, sekiz tane dört bitlik blokla kurulan elde atlamalı toplayıcınınki 24 ΔG'dir. İlk ve son bloklar küçük, ortadakiler büyük seçildiğinde bu süre kısalır; 1, 2, 3, 4, 5, 6, 5, 3, 2 ve 1 bitlik on blokla 18 ΔG'ye iner. Atlama yollarının üzerine ikinci bir atlama düzeyi eklenerek gecikme daha da azaltılabilir.

Atlama yolu, dalga eldeli toplayıcıya blok başına bir çoklayıcı ve bir VE kapısı ekler. Manchester elde zinciriyle kurulan bir gerçeklemede alan artışı çoğunlukla yüzde 10 ile 20 arasındadır. Yapı, yaygın sözcük uzunluklarında eldeyi önceden üreten toplayıcılara yakın hızda çalışırken daha az alan ve güç harcar. Uzun toplayıcılarda ise koşut önek toplayıcılar yeğlenir.

Weste ve Harris, yöntemin ikili toplayıcılardaki kullanımını C. Morgan ile D. Jarvis'in 1959 ve M. Lehman ile N. Burla'nın 1961 tarihli çalışmalarına dayandırır. Lehman ile Burla'nın makalesi, mekanik hesap makinelerinde ondalık biçimde kullanılan bu yöntemi ikili aritmetik birimleri için geliştirir.

Eldeyi önceden üreten toplayıcı (İngilizce: carry-lookahead adder), eldelerin basamak basamak yayılmasını beklemek yerine her basamağın eldesini doğrudan girişlerden hesaplayarak dalga eldeli toplayıcıdan çok daha hızlı çalışır. Yöntem her basamak için iki yardımcı sinyale dayanır: üretme (generate; g_i = A_i · B_i) ve geçirme (propagate; p_i = A_i ⊕ B_i). Her elde, e_i+1 = g_i + p_i · e_i bağıntısından bulunur; bu bağıntı açıldığında bütün eldeler koşut olarak az sayıda mantık düzeyinde hesaplanabilir. Karşılığında devre daha karmaşık ve maliyetlidir; çok geniş sözcüklerde bloklar sıradüzensel biçimde birleştirilir. Bazı kaynaklar geçirme sinyalini p_i = A_i + B_i biçiminde, VEYA işlemiyle tanımlar.

Elde ile seçmeli toplayıcı (İngilizce: carry-select adder), 1962'de O. J. Bedrij tarafından tanımlanmıştır. Toplayıcı bloklara bölünür ve en alttaki blok dışında her blok iki kez kurulur; biri elde girişini 0, öteki 1 varsayarak toplamı önceden hesaplar. Bir alt bloğun eldesi hazır olunca bir çoklayıcı iki sonuçtan doğru olanı geçirir; böylece üst bloklar alt blokların eldesini beklemez.

Blokların hepsi aynı boyda olursa gecikme bit sayısıyla doğrusal olarak artmayı sürdürür, yalnızca eğimi küçülür. Blok boyları alttan üste doğru büyütülürse gecikme bit sayısının kareköküyle orantılı (O(√n)) büyür. Karşılığında her üst bloğun toplayıcısı iki kez kurulduğu için devre alanı artar.

Eldeyi önceden üretme fikri çok düzeyli bir ağaç biçiminde kurulduğunda gecikme bit sayısının logaritmasıyla büyür. Bu yapılara ağaç toplayıcı, logaritmik toplayıcı ya da koşut önek toplayıcı (İngilizce: parallel prefix adder) denir. Her basamağın üretme ve geçirme sinyalleri bir önek hesabıyla birleştirilir; yan yana iki bit aralığının sinyalleri tek bir aralığın sinyallerine indirgenir ve ağacın sonunda her basamağın eldesi bilinir. Toplam bitleri bu eldelerden ve geçirme sinyallerinden bulunur. Önek hesabı için koşut devreleri R. E. Ladner ile M. J. Fischer 1980'de incelemiştir.

Ağaçlar düzey sayısı, birim sayısı ve tel uzunluğu arasında farklı dengeler kurar.

• Sklansky ağacı log₂n düzeyle çalışır, ancak bazı birimlerin çıkışı her düzeyde iki katına çıkan sayıda birime bağlanır.
• Kogge-Stone ağacı log₂n düzeyle çalışır ve her birim yalnız iki birime bağlanır; karşılığında çok sayıda uzun tel gerektirir. Ağaç, P. M. Kogge ile H. S. Stone'un 1973'te yineleme denklemleri için önerdikleri koşut algoritmaya dayanır.
• Brent-Kung ağacı 2log₂n − 1 düzey kullanır ama daha az birim ve daha kısa tellerle kurulur. R. P. Brent ile H. T. Kung, 1982'de toplamanın düzenli bir yerleşimle, bit sayısının logaritmasıyla orantılı sürede ve bit sayısıyla orantılı alanda yapılabileceğini göstermiştir.

Önek toplayıcıların kazancı özellikle 32 ve daha çok bitlik toplayıcılarda belirgindir; karşılığında tek düzeyli bir eldeyi önceden üreten toplayıcıdan daha çok donanım gerektirirler.

D. M. Harris ile S. L. Harris, iki girişli bir kapının 100 ps, bir tam toplayıcının 300 ps gecikmeli olduğu varsayımıyla 32 bitlik toplayıcıların gecikmelerini hesaplamıştır.

32 bitlik toplayıcıların gecikmesi

Yapı	Gecikme
Dalga eldeli toplayıcı	9,6 ns
Dört bitlik bloklarla eldeyi önceden üreten toplayıcı	3,3 ns
Koşut önek toplayıcı	1,2 ns

Aynı kaynak, gerçek devrelerde kazancın bu kadar büyük olmadığını, önek toplayıcıların yine de öteki yapılardan belirgin biçimde hızlı kaldığını belirtir. Kapı gecikmelerini sayan daha kaba bir hesapta 16 bitlik iki düzeyli eldeyi önceden üreten toplayıcı, dalga eldeli toplayıcıdan altı kat hızlı çıkar. Toplayıcı çoğu zaman işlemcinin kritik yolu üzerinde bulunduğundan seçilen yapı saat sıklığını doğrudan etkiler.

A − B işlemi için ayrı bir çıkarıcı devresi gerekmez; A ile Bnin ikiye tümleyeni toplanır. İkiye tümleyen, Bnin bitleri tersine çevrilip sonuca 1 eklenerek bulunduğu için toplayıcıya Bnin tersi verilir ve en düşük basamağın elde girişi 1 yapılır.

Toplama ile çıkarmayı aynı devrede yapan toplayıcı-çıkarıcıda tek bir denetim sinyali hem B bitlerini Dışlayan VEYA kapılarından geçirir hem de en düşük basamağın elde girişine verilir. Sinyal 0 iken B değişmeden geçer ve devre toplar; 1 iken B tersine çevrilir, elde girişi 1 olur ve devre çıkarır.

İşaretli sayılarla yapılan toplamada sonuç ayrılan bit sayısına sığmayabilir (aritmetik taşma). Bu durum, en anlamlı bite giren elde ile o bitten çıkan eldenin karşılaştırılmasıyla anlaşılır; iki elde farklıysa taşma olmuştur ve iki elde bir Dışlayan VEYA kapısına verilerek taşma sinyali elde edilir. İşaretsiz sayılarda ise taşmayı en anlamlı bitten çıkan elde gösterir.

İkili kodlanmış ondalık (BCD) gösterimde her ondalık basamak dört bitle tutulur. İki BCD basamağını toplayan devre, iki dört bitlik basamak ile bir elde girişi alır; toplam en çok 9 + 9 + 1 = 19 olabilir. Dört bitlik ikili toplamın sonucu 1001'i (9) aşarsa geçerli bir BCD basamağı değildir; sonuca 0110 (6) eklenerek doğru basamak bulunur ve bir elde çıkışı üretilir. Düzeltme, ikili toplamın elde çıkışı 1 olduğunda ya da toplam 1010 ile 1111 arasında kaldığında gerekir. 0110 eklemek, dört bitte 1010'un (on) çıkarılmasına denktir.

Devre iki dört bitlik toplayıcıdan oluşur; birincisi ikili toplamı bulur, ikincisi düzeltme gerekiyorsa 0110'u ekler. n basamaklı ondalık sayıları toplamak için n tane BCD toplayıcı art arda bağlanır; daha hızlı toplama için basamak toplayıcıları eldeyi önceden üreten yapıda da kurulabilir.

Çok sayıda sayı toplanacağında her ara toplamda eldenin bütün basamaklardan geçmesini beklemek yavaştır. 3:2 sıkıştırıcı (İngilizce: carry-save adder) üç n bitlik sayıyı alıp iki n bitlik sayıya indirir; bunlardan biri toplam bitlerinden, öteki elde bitlerinden oluşur. Devre, birbirine bağlanmamış n tam toplayıcıdan oluşur; her tam toplayıcı yalnız kendi sütunundaki üç biti toplar ve eldesini bir üst sütuna ayrı bir sayı olarak bırakır. Üç girişi iki çıkışa indirdiği için tam toplayıcıya (3,2) toplayıcı da denir.

Hızlı çarpıcılar kısmi çarpımları bu sıkıştırıcılarla toplar. C. S. Wallace'ın 1964'te önerdiği ağaçta kısmi çarpımlar sırayla değil koşut olarak sıkıştırılır ve her düzeyde toplanacak sayıların sayısı yaklaşık üçte ikisine iner.

Bir işlemcide toplayıcılar aritmetik mantık biriminin dışında da kullanılır. Buyrukların sırayla yürütülmesi için program sayacı bir toplayıcıyla bir sonraki buyruğun adresine ilerletilir; 32 bitlik buyruklar kullanan bir işlemcide bu adres PC + 4'tür. Koşullu dallanmada hedef adres, buyruktaki işaret genişletilmiş sabitin program sayacına eklenmesiyle bulunur; bu yüzden işlemcide ayrı bir dallanma hedefi toplayıcısı yer alır. Bellekten okuyan ve belleğe yazan buyruklarda erişilecek adres, taban yazmacındaki değere buyruktaki sabit eklenerek hesaplanır.

Karşılaştırmalar da çıkarmayla yapılır; A < B sınaması için A − B hesaplanır ve sonucun işaret bitine bakılır. Sıralı çarpma donanımı çarpılanı her adımda ara çarpıma ekler, bölme donanımı ise böleni kalandan çıkarır; ikisi de toplayan ya da çıkaran tek bir aritmetik birim üzerine kurulabilir.

Birçok işlemci toplamanın sonucuna ilişkin bilgileri bir bayrak yazmacında tutar. ARM mimarisinde elde bayrağı (C) işaretsiz toplamadaki taşmayı, taşma bayrağı (V) işaretli toplamadaki taşmayı gösterir; N ve Z bayrakları da sonucun eksi ya da sıfır olup olmadığını bildirir. x86 mimarisinde aynı bilgiler EFLAGS yazmacındaki CF ve OF bayraklarında tutulur; elde bayrağı ayrıca birden çok sözcüğe yayılan aritmetikte sözcükler arasında eldeyi aktarmak için kullanılır. Koşullu dallanma buyrukları bu bayraklara bakar; karşılaştırma buyruğu iki işleneni birbirinden çıkarır ve yalnız bayrakları kurar. MIPS mimarisi gibi bayrak yazmacı kullanmayan mimarilerde ise koşullu dallanma doğrudan yazmaç içeriklerine bakar.

Tam toplayıcı, Verilog ya da VHDL gibi bir donanım tanımlama dilinde üretme ve geçirme sinyallerini iç değişken olarak kullanan birkaç atamayla tanımlanabilir. Çok bitlik bir toplayıcı ise ya tam toplayıcı modülünün birçok kez örneklenmesiyle sıradüzensel olarak kurulur ya da dilin toplama işleciyle tek bir atamada yazılır. İkinci yolda toplayıcının hangi yapıyla gerçekleneceğine sentez aracı karar verir; araç, hız gereksinimini karşılayan en küçük tasarımı seçer.

Eldeyi bir üst basamağa aktarmak, mekanik hesap makinelerinin de temel sorunuydu. 17. yüzyılda Wilhelm Schickard ve Blaise Pascal'ın hesap makinelerinde eldeyi aktaran düzenekler vardı; Schickard'ın makinesinde eldenin birçok basamaktan birden geçmesi dişlilere zarar verebiliyordu. Eldenin birden çok basamağı atlayarak aktarılması fikri Charles Babbage'a kadar gider ve mekanik hesap makinelerinde uzun süre kullanılmıştır.

İkili toplayıcının ilk örneklerinden biri, Bell Laboratuvarları'nda çalışan George Stibitz'in 1937'de iki röle ile evinde kurduğu bir bitlik toplayıcıdır; mutfak masasında kurulduğu için Model K adıyla anılır. Atanasoff-Berry bilgisayarında, her biri iki basamağı ve alttan gelen eldeyi toplayan otuz vakum tüplü ikili toplayıcı birimi vardı.

Hızlı toplama yöntemleri 1950'lerde gelişti. A. Weinberger ile J. L. Smith, 1956'da bir eldenin kendinden önceki eldeyi beklemeden, doğrudan toplanan bitlerden hesaplanabileceğini göstererek eldeyi önceden üretme yöntemini yayımladı. Bunu 1960'ta Sklansky'nin toplayıcısı, 1962'de Bedrij'in elde ile seçmeli toplayıcısı ve 1964'te Wallace'ın hızlı çarpıcı önerisi izledi. Brent ile Kung'un 1982 tarihli çalışması, logaritmik gecikmeli bir toplayıcının düzenli bir yerleşimle yonga üzerinde kurulabileceğini gösterdi.