Adder

Penjumlahan adalah operasi aritmetika yang paling sering dikerjakan prosesor, dan rangkaiannya dibangun dari gerbang logika sederhana. Topik ini merakit perangkat penjumlah biner dari komponen terkecilnya, mulai dari half adder untuk satu bit, full adder yang menyertakan carry masuk, hingga ripple carry adder untuk bilangan n bit. Carry adalah bit sisa yang dibawa ke kolom berikutnya, dan perilakunya menentukan bentuk maupun kecepatan seluruh rangkaian. Setiap tahap diimplementasikan dalam Python dengan bit sebagai daftar 0/1, dan bagian penutup menghitung biaya kecepatannya beserta alternatif carry-lookahead yang menghitung carry lebih awal.

Half adder: menjumlahkan dua bit#

Half adder (penjumlah setengah) adalah rangkaian yang menjumlahkan dua bit dan menerbitkan dua keluaran, yaitu bit jumlah dan bit carry. Penjumlahan biner satu digit mengikuti aturan yang sama dengan penjumlahan bersusun pada desimal. Hasil 0 + 0 dan 0 + 1 muat dalam satu digit, sedangkan 1 + 1 bernilai 10, sehingga digitnya 0 dengan carry 1. Dua gerbang dasar sudah cukup untuk menangkap aturan itu. Gerbang XOR menghasilkan 1 hanya bila tepat satu masukannya bernilai 1, sehingga cocok menjadi bit jumlah, sedangkan gerbang AND menghasilkan 1 hanya bila kedua masukannya bernilai 1, sehingga cocok menjadi bit carry.

Tabel kebenaran di atas memperlihatkan keempat kemungkinan masukannya, dan kedua kolom keluaran persis mengikuti perilaku XOR dan AND. Implementasinya pun sesederhana itu, sebagaimana terlihat pada fungsi berikut.

def half_adder(a, b):
    jumlah = a ^ b        # XOR: 1 bila tepat satu masukan bernilai 1
    carry = a & b         # AND: 1 bila kedua masukan bernilai 1
    return jumlah, carry

Half adder menyimpan keterbatasan yang langsung terlihat pada penjumlahan sesungguhnya, yaitu tidak adanya jalur carry masuk. Penjumlahan bilangan multi-bit menghasilkan carry dari kolom yang lebih rendah yang juga wajib dijumlahkan, sehingga half adder tidak dapat dirangkai begitu saja menjadi penjumlah dengan lebar berapa pun. Kebutuhan itulah yang melahirkan full adder.

Full adder: carry masuk ikut dijumlahkan#

Full adder (penjumlah penuh) menjumlahkan tiga bit sekaligus, yaitu a, b, dan carry masuk dari kolom yang lebih rendah. Keluarannya tetap dua, yaitu bit jumlah dan carry keluar. Rangkaian ini dapat dibangun dari dua half adder dan satu gerbang OR. Half adder pertama menjumlahkan a dan b, half adder kedua menjumlahkan hasilnya dengan carry masuk, sedangkan gerbang OR menggabungkan kedua carry menengah menjadi carry keluar.

def full_adder(a, b, carry_masuk):
    j1, c1 = half_adder(a, b)
    j2, c2 = half_adder(j1, carry_masuk)
    return j2, c1 | c2    # carry keluar menyala bila salah satu carry menengah menyala

Gerbang OR cukup dipakai tanpa perhitungan tambahan karena kedua carry menengah tidak pernah menyala bersamaan. Apabila a dan b keduanya bernilai 1, jumlah menengahnya 0, sehingga half adder kedua tidak mungkin melahirkan carry. Salah satu carry menyala, atau tidak sama sekali, dan OR meneruskannya apa adanya.

Perilakunya dapat diperiksa dari satu contoh dengan a = 1, b = 1, dan carry masuk = 1. Half adder pertama menghasilkan jumlah 0 dengan carry 1. Half adder kedua menjumlahkan 0 dengan carry masuk 1 sehingga menghasilkan jumlah 1 tanpa carry. Carry keluarnya 1 dan jumlah akhirnya 1, sesuai 1 + 1 + 1 = 11 dalam biner. Dengan tiga masukan ini, rantai penjumlah multi-bit menjadi mungkin.

Ripple carry adder: merangkai n bit#

Ripple carry adder (penjumlah carry berambat) menjumlahkan dua bilangan n bit dengan merangkai n full adder secara berurutan. Carry keluar dari setiap tingkat menjadi carry masuk bagi tingkat yang lebih tinggi, dan bit terendah dijumlahkan lebih dahulu. Nama ripple, yang berarti berambat, menggambarkan cara kerjanya, karena carry bergerak dari bit paling kanan menuju bit paling kiri seperti riak air.

Diagram berikut menggambarkan rantai empat full adder untuk bilangan 4 bit. Jalur carry menyambung dari keluaran satu tingkat ke masukan tingkat berikutnya, mulai dari carry masuk di bit terendah hingga carry keluar di bit tertinggi.

Implementasi Python berikut menempatkan bit paling rendah pada indeks 0. Fungsi ripple_carry menerima dua daftar bit berpanjang sama, menjalankan full adder untuk setiap pasangan bit, lalu mengembalikan hasil dan carry akhir. Konversi bilangan menjadi bit dan sebaliknya hanya menyiapkan masukan serta menampilkan keluaran, sedangkan penjumlahannya sendiri murni operasi bit.

"""Perangkat penjumlah biner: half adder, full adder, dan ripple carry.

Bit disimpan sebagai daftar 0/1 dengan bit paling rendah di indeks 0.
Seluruh mekanisme penjumlahan memakai operasi bit, bukan operator +.
"""


def half_adder(a, b):
    """Menjumlahkan dua bit, mengembalikan pasangan (jumlah, carry)."""
    jumlah = a ^ b        # XOR: 1 bila tepat satu masukan bernilai 1
    carry = a & b         # AND: 1 bila kedua masukan bernilai 1
    return jumlah, carry


def full_adder(a, b, carry_masuk):
    """Menjumlahkan dua bit dan carry masuk, mengembalikan (jumlah, carry keluar)."""
    j1, c1 = half_adder(a, b)
    j2, c2 = half_adder(j1, carry_masuk)
    return j2, c1 | c2    # carry keluar menyala bila salah satu carry menengah menyala


def ripple_carry(a_bits, b_bits):
    """Menjumlahkan dua bilangan n bit dari bit terendah ke bit tertinggi."""
    hasil = []
    carry = 0
    for i in range(len(a_bits)):
        s, carry = full_adder(a_bits[i], b_bits[i], carry)
        hasil.append(s)
    return hasil, carry


def ke_bit(n, lebar):
    """Mengubah bilangan non-negatif menjadi daftar bit (untuk menyiapkan masukan)."""
    return [(n >> i) & 1 for i in range(lebar)]


def tampil(bits):
    """Menampilkan daftar bit dalam urutan baca, bit tertinggi di kiri."""
    return "".join(str(b) for b in reversed(bits))


if __name__ == "__main__":
    contoh = [(0b0101, 0b0011), (0b1001, 0b1000), (0b1111, 0b0001), (0b0110, 0b0010)]
    for a, b in contoh:
        abits, bbits = ke_bit(a, 4), ke_bit(b, 4)
        hasil, carry = ripple_carry(abits, bbits)
        print(f"0b{tampil(abits)} + 0b{tampil(bbits)} = 0b{tampil(hasil)} (carry keluar {carry})")

0b0101 + 0b0011 = 0b1000 (carry keluar 0)
0b1001 + 0b1000 = 0b0001 (carry keluar 1)
0b1111 + 0b0001 = 0b0000 (carry keluar 1)
0b0110 + 0b0010 = 0b1000 (carry keluar 0)

Baris 0b1111 + 0b0001 pada keluaran di atas memperlihatkan kasus yang penting. Carry yang lahir di bit paling kanan harus melewati keempat tingkat sebelum operasi selesai, dan hasil akhirnya 0b0000 dengan carry keluar 1. Carry akhir itu adalah bit kelima dari 16, yaitu nilai yang tidak muat lagi dalam lebar 4 bit. Membuangnya berarti membaca 15 + 1 sebagai 0, sehingga carry keluar tingkat terakhir wajib dijaga.

Biaya kecepatan: carry yang merambat#

Rangkaian kombinasional dinyatakan selesai bekerja begitu semua sinyal keluarannya stabil, dan pada ripple carry adder sinyal yang paling lambat adalah carry itu sendiri. Tingkat pertama menerbitkan carry keluarnya setelah satu jeda gerbang, tingkat kedua menunggu tingkat pertama, dan seterusnya hingga carry mencapai bit tertinggi. Jeda totalnya kira-kira n kali jeda satu tingkat, sehingga bertumbuh linear terhadap lebar bit dan dapat ditulis $O(n)$. Pada bilangan 64 bit, carry pada kasus terburuk harus melewati 64 tingkat sebelum hasilnya sah dibaca.

Carry-lookahead memotong perambatan itu dengan cara menghitung carry lebih awal. Setiap tingkat menerbitkan dua sinyal bantu, yaitu generate bila pasangan bitnya pasti melahirkan carry sendiri, dan propagate bila pasangan bitnya meneruskan carry yang datang dari bawah. Dengan kedua sinyal tersebut, carry setiap tingkat dihitung langsung dari a dan b melalui beberapa lapis gerbang, tanpa menunggu carry dari bit terendah tiba satu per satu. Kedalaman gerbangnya bertumbuh jauh lebih lambat daripada ripple carry, tetapi jumlah gerbangnya jauh lebih banyak, sehingga pilihannya adalah menukar area dan daya dengan kecepatan.

Kesalahan umum#

Rancangan adder yang baru pertama kali ditulis biasanya gagal pada tiga tempat yang sama. Ketiganya terdeteksi dengan pengujian yang disiplin sejak lebar bit masih kecil.

• Urutan bit terbalik. Konvensi bit paling rendah di indeks 0 berlawanan dengan urutan baca manusia, sehingga hasil yang tercetak terlihat mundur. Tetapkan konvensinya sekali di awal, lalu uji dengan contoh kecil seperti 01 + 10 sebelum menaikkan lebar bitnya.
• Carry akhir dibuang. Penjumlahan n bit dapat menghasilkan n + 1 bit, seperti 1111 + 0001. Apabila carry keluar tingkat terakhir tidak diambil, 15 + 1 terbaca sebagai 0 dan hasilnya terlihat keliru padahal rangkaiannya benar. Kesalahan ini mudah lolos pada contoh kecil karena banyak pasangan masukan tidak melahirkan carry akhir sama sekali.
• Sambungan carry yang salah tingkat. Carry keluar tingkat i wajib menjadi carry masuk tingkat i + 1, bukan tingkat i sendiri. Kesalahan kabel semacam ini tidak memunculkan error apa pun pada simulasi tanpa pemeriksaan, sehingga pengujian dengan banyak pasangan masukan menjadi cara utama mendeteksinya.

Ringkasan#

• Half adder menjumlahkan dua bit dengan gerbang XOR untuk bit jumlah dan gerbang AND untuk bit carry.
• Full adder menjumlahkan dua operand beserta carry masuk dan dibangun dari dua half adder dengan satu gerbang OR.
• Ripple carry adder merangkai full adder dari bit terendah ke bit tertinggi, dengan carry keluar setiap tingkat menjadi carry masuk tingkat berikutnya.
• Jeda merambat tumbuh linear terhadap lebar bit karena carry melewati seluruh rantai, sedangkan carry-lookahead menghitung carry lebih awal dengan biaya gerbang lebih banyak.

Referensi#

• Nand2Tetris — Nisan dan Schocken — Proyek pendidikan yang membangun adder dan ALU dari gerbang dasar hingga komputer lengkap, sejalan dengan pendekatan topik ini.
• Computer Systems: A Programmer’s Perspective — Carnegie Mellon — Buku teks yang membahas aritmetika bilangan bulat biner beserta representasinya dari sudut pandang pemrogram.