Categories
FPGA

Algoritma Aritmatika Terdistribusi (Implementasi FPGA)

Aritmatika terdistribusi merupakan algoritma komputasi yang dapat melakukan perkalian dengan menggunakan bantuan tabel look-up. Aritmatika terdistribusi sering digunakan pada komputasi penjumlahan-perkalian atau sum-of-products yang banyak dijumpai pada algoritma penapis PSD dan fungsi-fungsi transformasi frekuensi. Ironisnya, pada saat ini belum banyak perancang komputasi PSD menggunakan (bahkan mendengar) algoritma ini (Mintzer, 1992). Jika perancangan fungsi-fungsi PSD dalam deskripsi VHDL dilakukan pada tingkat RTL, justru algoritma ini perlu diperhitungkan dan digunakan karena dapat mengefisiensikan algoritma fungsi PSD yang akan diimplementasikan.

Misalnya, pada kasus tapis digital, jumlah perkalian aritmatika yang menyatakan tanggap dari suatu sistem linear serta invarian terhadap waktu dapat dinyatakan dalam bentuk:

(1)

dengan:

  • y(n) = tanggap sistem;
  • xk(n) = peubah masukan ke-k pada waktu-n;
  • Bk = faktor bobot atau koefisien masukan ke-k yang konstan untuk semua n.

Pada aplikasi tapis digital, konstanta Bk merupakan koefisien penapis sedangkan peubah xk adalah sumber masukan data tunggal. Proses penjumlahan-perkalian menggunakan Aritmatika Terdistribusi digantikan dengan langkah-langkah atau prosedur tabel look-up yang dapat diimplementasikan dengan mudah menggunakan CLB (ROM) dari FPGA.

Dimulai dengan mendefinisikan format angka dari peubah masukan menjadi 2’s complement, dengan demikian peubah xk dapat dituliskan

(2)

dengan B adalah lebar bit data dan xkb adalah sebuah peubah biner dan dapat diasumsikan sebagai angka 0 dan 1. Sebuah bit tunggal yang menyatakan tanda bilangan dinyatakan oleh xk0. Persamaan (1) disubstitusikan ke dalam persamaan (2), sehingga menghasilkan

(3)

atau dapat dituliskan secara keseluruhan

Masing-masing bentuk yang terdapat di dalam tanda kurung menyatakan suatu operasi biner AND yang melibatkan sebuah bit dari peubah masukan dan semua bit konstanta dan tanda “+” menyatakan operasi aritmatika penjumlahan. Faktor eksponensial menyatakan faktor skala kontribusi dari masing-masing total penjumlahan. Tabel look-up dibuat berdasarkan bit skala yang sama untuk semua peubah masukan, hal ini sekaligus menyatakan cara pengalamatan-nya (gambar 1), yang dapat diakses jumlah total masing-masing persamaan di dalam tanda kurung, sebagaimana terlihat pada gambar 2, yang dinamakan sebagai DALUT (Distributed Arithmetic Look-Up Table).

DALUT yang sama dapat dikonfigurasikan secara time-shared (penggunaan-waktu bersama) dalam struktur komputasi serial atau dapat direplikasikan sebanyak B kali untuk komputasi paralel.

Gambar 1. Pengalamatan DALUT, AK dimasukkan ke dalam penjumlahan untuk xkb = 1

Gambar 2. Isi DALUT, angka 0 s/d 8 dan seterusnya menunjukkan alamat DALUT

Operasi aritmatika sekarang telah berkurang menjadi operasi penjumlahan, pengurangan dan penyekalaan biner. Skala dengan 2 pangkat N dapat diimplementasikan dengan melakukan pergeseran kode biner ke kanan sebanyak N bit, sedangkan penjumlah penuh (Full Adder) hanya memerlukan dua operan, yaitu penambah dan yang ditambah, untuk menghasilkan jumlah dan sisa (sum and carry). Sedangkan implementasi ROM dapat dilakukan dengan CLB (Mintzer, 1993).

Daftar Pustaka

  • Mintzer, L., 1993, “The Role of Distributed Arithmetic in FPGA-based Signal Processing”, Xilinx Inc., San Jose, California, USA.