LAPORAN TAHUNAN PENELITIAN HIBAH BERSAING
METODE EFISIENSI AREA INTEGRATED CIRCUIT (IC) DENGAN REDUKSI WORDLENGTHS UNTUK MENINGKATKAN KINERJA PERANGKAT KOMPUTASI ELEKTRONIK
Tahun ke 2 dari rencana 3 tahun Zulfikar, S.T., M.Sc.
NIDN. 0020077507
Hubbul Walidainy, S.T., M.T.
NIDN. 0026087301
Dibiayai oleh Direktorat Penelitian Pengabdian kepada Masyarakat, Direktorat Jenderal Pendidikan Tinggi, Kementerian Pendidikan dan Kebudayaan, sesuai dengan Surat Perjanjian Penugasan Pelaksanaan Hibah Penelitian bagi Dosen Perguruan Tinggi Batch I Universitas Syiah Kuala Tahun Anggaran 2015 Nomor: 035/SP2H/PL/Dit.Litabmas/II/2015 tanggal 5 Pebruari 2015 UNIVERSITAS SYIAH KUALA NOVEMBER 2015
RINGKASAN Perkembangan teknologi integrated circuit (IC) yang kian pesat dan kebutuhan akan bertambahnya informasi yang dapat disajikan dalam sebuah perangkat komputasi elektronik dewasa ini telah mendorong para peneliti untuk menemukan cara menghemat area yang terpakai oleh rangkaian komputasi dalam sebuah IC. Penelitian ini bertujuan menerapkan metode baru dengan cara reduksi wordlengths untuk menghemat area dari suatu IC guna meningkatkan kinerja dari perangkat komputasi elektronik. Dengan berkurangnya wordlengths, maka area yang dibutuhkan dalam sebuah IC untuk rangkaian komputasi akan semakin kecil. Pada penelitian ini, untuk tahun kedua dipilih rangkaian transformasi Fourier jenis Discrete Fourier Transform (DFT) sebagai target untuk diefisiensikan. Rangkaian tersebut dirancang dengan menggunakan blok-blok dasar operasi aritmatika seperti penambah dan pengali. Tahapan awal dari teknik reduksi wordlength yang diajukan telah berhasil diaplikasikan pada rangkaian tersebut. Rangkaian 4-point DFT dan teknik perancangannya disajikan secara detail. Hasil simulasi behavior, synthesis dan simulasi waktu terhadap beberapa chip FPGA dari Xilinx dipaparkan pada bab 5. Desain lanjutan untuk 8-point DFT telah berhasil dilaksanakan dan diefisiensikan juga. Hasil awal dari penelitian ini telah dipublikasikan pada seminar internasional ICEEI 2015 tanggal 10-11 Agustus 2015. Dan hasil lanjutan telah submit pada jurnal internasional bereputasi IJECE. Hasil lanjutan ini (8-point DFT) lebih efisien dari rancangan konvensional. Dengan demikian penelitian ini telah mencapai tujuan keseluruhan.
Keywords: Integrated Circuit, Penghematan Area, Reduksi Wordlengths, FPGA, 4-point DFT, 8-point DFT
i
PRAKATA Penelitian ini bermaksud untuk menghemat area suatu IC dari perangkat komputasi elektronik dengan harapan kinerja perangkat tersebut semakin meningkat. Penelitian ini memakai menerapkan teknik reduksi/ pengurangan wordlength dari rangkaian pembangkitan bilangan random. Diharapakan area yang dibutuhkan dalam sebuah IC untuk rangkaian bilangan random semakin kecil. Adapun Metode dan tahapan penelitian yang digunakan adalah sebagai berikut: •
Studi Literatur, mempelajari beberapa rangkaian aritmatika kompleks yang akan dijadikan sasaran penelitian.
•
Implementasi Software, pemodelan rangkaian-rangkaian target ke dalam hardware melalui program VHDL akan dilakukan. Beberapa program simulasi telah dipilih, antara lain Xilinx ISE dan Quartus Altera.
•
Perbandingan, bersama dengan rancangan metode baru, akan disimulasikan juga rangkaian-rangkaian aritmatika konvensional yang telah dipakai saat ini. Jika area dari rangkaian dengan metode baru tidak lebih hemat, maka akan dilakukan pemrograman ulang. Perbandingan akan dilakukan melalui software dari Xilinx dan Altera.
•
Pengembangan Lanjut, setelah diimplementasikan ke FPGA, akan dikaji kemungkinan penghematan lebih lanjut terhadap rangkaian yang dipilih. Jika memungkinkan akan dilakukan dan dimulai pemrograman ulang. Penulis mengucapkan terima kasih yang sebesar-besarnya kepada pihak-pihak yang
telah membantu terlaksananya penelitian ini.
ii
DAFTAR ISI RINGKASAN
i
PRAKATA
ii
DAFTAR ISI
iii
DAFTAR TABEL
iv
DAFTAR GAMBAR
v
DAFTAR LAMPIRAN
vi
BAB I. PENDAHULUAN
1
BAB II. TINJAUAN PUSTAKA
4
2.1 Discrete Fourier Transforms
4
BAB III. TUJUAN DAN MANFAAT PENELITIAN
8
3.1 Tujuan Penelitian
8
3.2 Mamfaat Penelitian
8
BAB IV. METODE PENELITIAN
9
BAB V. HASIL YANG DICAPAI
11
5.1 Desain Rangkaian DFT 4 point
11
5.2. Implementasi Rangkaian DFT 4 point
14
5.3. Desain Rangkaian DFT 8 point
15
BAB VI. RENCANA TAHAPAN BERIKUTNYA
20
BAB VII. KESIMPULAN DAN SARAN
21
DAFTAR PUSTAKA
22
LAMPIRAN
25
iii
DAFTAR TABEL Tabel I. Jumlah dari nontrivial perkalian real dan penambahan untuk menghitung N titik komplek DFT
7
Tabel II. Daftar perintah konversi bilangan antara standard logic vector, signed dan unsigned
4
Tabel III. Perbandingan frekuensi maksimum diantara chip-chip Xilinx
13
Tabel IV. Perbandingan kecepatan diantara chip Xilinx
15
Tabel V. Area yang diperlukan diantara chip Xilinx
15
Tabel VI. Jenis bilangan berdasarkan perhitungan twiddle factor
16
iv
DAFTAR GAMBAR Gambar 1. Array data dua dimensi untuk penyimpanan urutan x(n), 0<=n<= N-1
5
Gambar 2. Dua pengaturan untuk array-array data; (a) Row wise; (b) Column wise
6
Gambar 3. Fishbone diagram metode penelitian
9
Gambar 4. Blok dan aliran data dari rancangan rangkaian DFT 4-point
12
Gambar 5. Algoritma dari DFT 4-point berdasarkan perkalian dari fungsi Rademacher
13
Gambar 6. Rangkaian kontrol berdasarkan fungsi Rademacher
14
Gambar 7. Hasil simulasi dari desain rangkaian DFT
14
Gambar 8. Skema bagan 8-point DFT
16
Gambar 9 Hasil-hasil komplek konjugate
17
Gambar 10. Desain 8-point DFT ysng efisien
18
Gambar 11. Rangkaian dari 2-point DFT
18
Gambar 12. Rangkaian 4-point DFT yang telah di modifikasi
19
v
DAFTAR LAMPIRAN LAMPIRAN I: BIODATA KETUA PENELITI
25
LAMPIRAN II: BIODATA ANGGOTA PENELITI
28
LAMPIRAN III: Publikasi Artikel pada ICEEI 2015
30
LAMPIRAN IV: Publikasi pada Jurnal Internasional
31
vi
BAB 1 PENDAHULUAN
Sekarang ini banyak rangkaian elektronika diimplementasikan kedalam sebuah Integrated Circuit (IC). Kecendrungan untuk masa yang akan datang semakin banyak rangkaian elektronika diimplementasikan kedalam IC, hal ini dikarenakan faktor biaya produksi yang murah jika diproduksi dalam jumlah yang banyak. Seiring dengan itu, tuntutan akan semakin besarnya rangkaian elektronika untuk suatu aplikasi tertentu mendorong para peneliti untuk menemukan cara yang lebih efisien untuk merealisasikan suatu rangkaian elektronika kedalam sebuah IC. Salah satu faktor efisiensi yang sangat penting dalam merealisasikan suatu rangkaian elektronika kedalam sebuah IC adalah area (besarnya ukuran IC). Sebagai contoh, sebuah telepon genggam produksi sekarang ini mempunyai kemampuan berlipat ganda jika dibandingkan dengan telepon genggam produksi 10 tahun yang lalu dengan ukuran yang sama tentunya, hal ini salah satunya dikarenakan efisiensi area pada IC. Kapasitas IC didalam telepon genggam produksi sekarang ini jauh lebih besar walaupun dengan ukuran (dimensi) yang sama dengan sebelumnya. Hal ini bergantung dari teknologi terbaru pembuatan rangkaian terintegrasi. Penghematan area dari suatu IC lebih lanjut juga bisa dicapai dengan menyederhanakan rangkaian komputasi elektronik. Rangkaian tersebut digunakan untuk perhitungan-perhitungan seperti penjumlahan, pengurangan, pembagian, perkalian dan lainlain. Penghematan rangkaian ini akan lebih terasa jika diterapakan pada perhitungan lebih dari satu tingkatan (komplek). Metode yang akan digunakan adalah reduksi wordlengths (lebar kata). Dengan diterapkannya metode ini, diharapkan area yang terpakai didalam suatu IC menjadi lebih kecil. Sehingga suatu IC dengan ukuran yang sama bisa menampung lebih banyak rangkaian untuk aplikasi lain. Pada tahun 2014, peneliti telah memilih rangkaian pembangkit bilangan randon uniform dengan metode Linear Congruential Generator (LCG). Desain rangkaian LCG yang efisien dibandingkan dengan metode biasa telah dihasilkan dan diseminasikan pada jurnal internasional. Tahapan lanjutan untuk menghemat area dari LCG juga telah dilakukan. Pada tahap lanjut ini, desain rangkaian lebih cepat dari yang sebelumnya.
1
Metode reduksi wordlengths akan diuji juga terhadap rangkaian-rangkaian lain untuk mendapatkan suatu generalisasi. Tahun 2015, peneliti berencana akan menerapkan metode reduksi wordlengths terhadap rangkaian Discrete Fourier Transform (DFT). Digital signal processing (DSP) digunakan di hampir semua piranti elektronik. Kebutuhan untuk memproses suatu signal di dalam perangkat elektronik adalah keharusan sekarang ini. Data atau sinyal dari luar atau di dalam perangkat harus diproses untuk tujuan tertentu menggunakan aplikasi khusus. Sering kali data harus ditransformasikan ke domain yang lain untuk mempermudah pemrosesan. Transformasi yang paling banyak digunakan adalah jenis Fourier transform. Dalam hal discrete, Discrete Fourier Transforms (DFT) sering digunakan untuk merubah sinyal atau data ke domain frekuensi. Ini adalah suatu transformasi yang sangat hebat dan telah digunakan sejak dulu. DFT tidak efisien jika diimplementasikan secara langsung. Banyak ilmuan memperkenalkan
konsep
penyederhanaan
proses
perubahan
data
dengan
DFT.
penyederhanaan tersebut membawa ke perkembangan algoritma Fast Fourier Transforms (FFT). Selama beberapa dekade terakhir, peneliti telah mengembangkan algoritma FFT seperti Radix-2, Radix-4, Split Radix, Prime Factor Algorithm (FPA) dan Winograd Fourier Transforms (WFTA). Algoritma-algoritma tersebut telah dikembangkan untuk tujuan tertentu dan masing-asing punya kelebihan dan kekurangan. Algoritma Walsh transforms lebih sederhana dari pada Fourier transforms, tetapi trnsformasi ini jarang digunakan dan hampir dilupakan. Walsh transforms punya sedikit kesamaan dengan Fourier transforms. Berdasarkan kesamaan tersebut, beberpa peneliti telah mengadopsi algoritma Walsh untuk mengembangkan Fourier transforms yang lebih efisien. Suatu algoritma untuk menghitung DFT dengan menggunakan Walsh transforms di kembangkan melalui faktorisasi matrik intermediate T. Monir T dkk telah mengusulkan suatu kombinasi perhitungan yang efisien dari Walsh dan DFT. teknik ini berdasarkan penggunaan Radix-4 Walsh Hadamard transforms (FWHT). Teknik lain yang juga efisien adalah perhitungan keduanya (DFT dan Walsh transfors) dengan menggunakan algoritma Radix-2 juga telah dipublikasikan. Algoritma-algoritma kombinasi sebelumnya dirancang untuk input dan output data secara paralel. Hal ini menyebabkan penggunaan memori dalam jumlah besar sehingga tidak sesuai untuk aplikasi rangkaian-rangkaian kecil. Oleh karena itu, kami mengenalkan suatu algoritma untuk meminimalkan penggunaan memori dengan memberikan input secara serial dan output didapat secara paralel. Model algoritma ini bisa di dapatkan dengan menggunakan 2
perkalian dari fungsi Rademacher. Desain telah dilakukan untuk DFT 4-point, detail rancangan akan disajikan kemudian. Pada tahapan lanjut telah didesain rangkaian untuk menjalankan fungsi 8-point DFT. rangkaian tersebut merupakan gabungan dari rangkaian DFT yang lebih kecil seperti 4-point dan 2-point DFT sesuai dengan konsep decimatin in time (DIT). Desain awal telah dibuat dengan mengkoneksikan DFT yang lebih kecil. Analisa terhadap wordlengths dan kebiasaan data juga telah dilaksanakan. Hasilnya adalah rangkaian 8-point DFT yang efisien.
3
BAB 2 TINJAUAN PUSTAKA
2.1
Discrete Fourier Transform Pada dasarnya, permasalahan perhitungan untuk DFT adalah untuk menghitung
urutan {X(k)} dari N bilangan nilai komplek yang diberikan urutan data yang lain {x(n)} dengan panjang N, sesuai dengan persamaan (1) N −1
X ( k ) = ∑ x(n)W Nkn
(1)
0 ≤ k ≤ N −1
n =0
dimana W N = e − j 2π / N
(2)
Secara umum, urutan x(n) juga diasumsikan adalah nilai komplek. Begitu juga dengan Inverse Discrete Transform (IDFT) menjadi x(n) =
1 N −1 ∑ X (k )WN−nk N k =0
(3)
0 ≤ n ≤ N −1
Perhitungan langsung dari DFT untuk urutan nilai komplek x(n) dari N titik dapat dinyatakan oleh: N −1 2πkn 2πkn X R (k ) = ∑ x R ( n) cos + x I (n) sin N N n =0
(4)
N −1 2πkn 2πkn − x I (n) sin X I ( k ) = − ∑ x R (n) sin N N n=0
(5)
Perhitungan langsung dari persamaan-persamaan (4) dan (5) membutuhkan: •
2N2 evaluasi dari fungsi-fungsi trigonometri
•
4N2 perkalian real
•
4N(N-1) penambahan real
•
Sebuah bilangan untuk indeks dan pengalamatan operasi Perhitungan langsung dari DFT pada dasarnya tidak efisien, hal ini karena perhitungan
tersebut tidak memperlihatkan properti-properti symetri dan perulangan dari faktor WN. Kedua property tersebut adalah: •
Properti Symetri: WNk + N / 2 = −W Nk 4
•
Properti Perulangan: WNk + N = WNk Fast Fourier Transform (FFT) adalah suatu metode cepat untuk perhitungan Discrete
Fourier Transform (DFT). Ada beberapa metode yang dapat digunakan untuk melakukan DFT berdasarkan pendekatan divide dan conquer yang mana lebih cepat dari perhitungan DFT secara langsung. Metode-metode tersebut adalah: •
Radix-2 FFT
•
Radix-4 FFT
•
Split-Radix FFT Pendekatannya berdasarkan kepada dekomposisi dari N titik DFT kedalam successive
DFT yang lebih kecil. Untuk mengilustrasikan notasi dasar, mari kita lihat perhitungan dari N titik DFT, dimana N dapat difaktorkan sebagai perkalian dari dua bilangan integer, yaitu N = LM
(6)
Urutan x(n), 0 <= n <= N-1, dapat disimpan pada array terindeks satu dimensi oleh n atau sebagai array terindeks dua dimensi oleh l dan m, dimana 0 <= l <= L-1 dan 0 <= m <= M-1 sebagai ilustrasi yang ditunjukkan pada Gambar 1. n
0
1
x(0)
x(1)
x(2)
…
N-1
…
x(N-1)
… … … …
M-1
(a) M row index L
0 1 2 . . . L-1
column index 0 1 x(0,0) x(0,1) x(1,0) x(1,1) x(2,0) x(2,1) . . . . . .
…
. . .
… (b)
Gambar 1. Array data dua dimensi untuk penyimpanan urutan x(n), 0<=n<= N-1
5
Row wise
n=Ml + m
M 0 x(0) x(M) x(2M) . . . x((L-1)M)
L 0 1 2 . . . L-1
1 x(1) x(M+1) x(2M+1) . . . x((L-1)(M+1))
2 x(2) x(M+2) x(2M+2) . . . x((L-1)(M+2))
… … … … … …
M-1 x(M-1) x(2M-1) x(3M-1) . . . x(LM-1)
(a) Column wise
n=l + mL
M L 0 1 2 . . . L-1
0 x(0) x(1) x(2) . . . x(L-1)
1 x(L) x(L+1) x(L+2) . . . x(2L-1)
2 x(2L) x(2L+1) x(2L+2) . . . x(3L-1)
… … … … … …
M-1 x((M-1)L) x((M-1)L+1) x((M-1)L+2) . . . x(LM-1)
(b) Gambar 2. Dua pengaturan untuk array-array data; (a) Row wise; (b) Column wise Algoritma 1 (row wise): •
Simpan sinyal secara column-wise
•
Hitung M titik DFT dari setiap row
•
Kalikan hasil array dengan faktor phase W Nlq
•
Hitung M titk DFT dari setiap column
•
Baca array yang dihasilkan secara row-wise
Algoritma 2 (column wise): •
Simpan sinyal secara row-wise
•
Hitung L titik DFT dari setiap column
•
Kalikan hasil array dengan faktor phase W Npm
•
Hitung M titik DFT dari setiap row
•
Baca array yang dihasilkan secara column-wise
Perkembangan penggunaan FFT dengan pendekatan divide and conquer adalah: 6
•
N2 perkalian telah berkurang menjadi N(M+L+1)
•
N(N-1) penambahan telah berkurang menjadi N(M+L-2)
Tabel 1: Jumlah dari nontrivial perkalian real dan penambahan untuk menghitung N titik komplek DFT Perkalian Real N 16
Radix 2 24
32 64 128 256 512 1,024
88 264 712 1,800 4,360 10,248
Radix 4 20
Radix 8
208
204
1,392 3,204 7,856
Penambahan Real Split Radix 20
Radix 2 152
68 196 516 1,284 3,076 7,172
408 388 1,032 976 972 964 2,504 2,308 5,896 5,488 5,380 13,566 12,420 12,292 30,728 28,336 27,652
Sumbe: diambil dari Duhamel (1986)
7
Radix 4 148
Radix 8
Split Radix 148
BAB 3 TUJUAN DAN MANFAAT PENELITIAN
3.1 Tujuan Penelitian Penelitian ini secara umum bertujuan untuk menghemat area dari suatu IC dari perangkat komputasi elektronik. Diharapkan kinerja perangkat komputasi elektronik tersebut semakin meningkat. Penelitian ini akan menggunakan teknik reduksi wordlengths dari rangkaian komputasi aritmatika. Dengan berkurangnya wordlengths, maka area yang dibutuhkan dalam sebuah IC untuk fungsi yang sama akan semakin kecil. Pada tahap awal, penelitian ini bertujuan khusus untuk: 1. Melakukan analisis statistik terhadap semua wordlengths yang digunakan dari rangkaian komputasi elektronik (DFT 4 point). 2. Mereduksi wordlengths dari rangkaian komputasi elektronik tersebut. 3. Membandingkan desain rangkaian komputasi elektronik yang telah dengan area dari rangkaian komputasi elektronik lain. Pada tahap lanjutan, penelitian ini bertujuan khusus untuk: 1. Melakukan analisis statistik secara mendalam terhadap semua sinyal-sinyal (data) yang mungkin digunakan untuk masukan ke rangkaian komputasi elektronik (DFT 8 point). 2. Mereduksi wordlengths rangkaian tersebut, sehingga dicapai hasil yang lebih optimal dari desain lain. 3. Mendokumentasikan dan mendiseminasikan hasil penelitian tersebut kepada pihak terkait baik di tingkat nasional maupun internasional. 3.2 Mamfaat Penelitian Suatu perangkat elektronik akan lebih bernilai jual jika dilengkapi dengan berbagai macam aplikasi atau fungsi tambahan. Hal ini senada dengan perkembangan teknologi perangkat elektronik selama ini, dimana makin banyak (beragam) aplikasi tambahan yang dimasukkan kedalam suatu perangkat elektronik dengan ukuran atau dimensi yang sama dengan sebelumnya. IC merupakan komponen utama tempat aplikasi-aplikasi disematkan. Jadi kebutuhan untuk menghemat area IC menjadi keharusan. Dengan penghematan area IC maka akan ada ruang untuk menambahkan rangkaian untuk aplikasi yang lain.
8
BAB 4 METODE PENELITIAN
Penulis telah menginisialisasi penelitian ini dengan mempublikasikan konsep dasar reduksi wordlengths dari rangkaian aritmatika. Hasil implementasi konsep desain kedalam FPGA menunjukkan bahwa area yang dibutuhkan lebih sedikit dibandingkan dengan metode konvensional. Penulis juga telah menerapkan metode yang diajukan pada rangkaian LCG, sehingga area yang diperlukan lebih sedikit. Metode penelitian yang digunakan untuk penghematan area dari IC dengan metode reduksi wordlengths tertuang dalam fishbone diagram (diagram tulang ikan) seperti terlihat pada Gambar 3.
Gambar 3 Fishbone diagram metode penelitian Berikut adalah penjelasan metode penelitian yang tersusun seperti pada gambar 3: •
Studi Literatur, pada tahap awal, penulis akan mendalami beberapa rangkaian aritmatika komplek yang akan dijadikan sasaran penelitian. Setiap tahun akan dipilih 1 (satu) buah rangkaian. Studi statistik terhadap aplikasi rangkaian tersebut akan dilakukan secara mendalam.
•
Implementasi Software, pemodelan rangkaian-rangkaian target kedalam hardware melalui program VHDL akan dilakukan. Beberapa program simulasi telah dipilih,
9
antara lain: Xilinx ISE dan Quartus Altera. Konsep konversi bilangan sangat membantu dalam penerapan. •
Perbandingan, bersama dengan rancangan metode baru, akan disimulasikan juga rangkaian-rangkaian aritmatika konvensional yang telah dipakai saat ini. Jika area dari rangkaian dengan metode baru tidak lebih hemat, maka akan dilakukan pemrograman ulang. Perbandingan akan dilakukan melalui software dari Xilinx dan Altera.
•
Implementasi Hardware, urutan proses untuk mengimplementasikan rangkaian yang dirancang kedalam hardware FPGA adalah: Translation, Mapping, Place & Route, Program Generation, dan Downloading.
•
Pengujian Hardware, untuk pengujian ini akan dilakukan beberapa tahapan seperti: pengujian visual, pengujian dengan alat ukur dan pengujian akan dilakukan untuk berbagai macam kemungkinan.
•
Pengembangan Lanjut, setelah diimplementasikan ke FPGA, akan dikaji kemungkinan penghematan lebih lanjut terhadap rangkaian yang dipilih. Jika memungkinkan akan dilakukan dan dimulai pemrograman ulang. Metode penelitian yang telah dijelaskan diatas adalah untuk satu tahapan proses dari
suatu rangkaian komputasi elektronik. Hal ini ditargetkan akan selesai selama 1 (satu) tahun. Untuk tahun ke 2 dan ke 3, proses seperti pada fishbone diagram tersebut akan diulang dari awal. Pada tahun ke 2 dan ke 3, implementasi dan pengujian juga akan dilakukan pada software. Hal ini dilakukan untuk menjustifikasi metode yang telah dirancang dengan berbagai kemungkinan yang tidak didapatkan pada implementasi rangkaian di tahun pertama. Jumlah publikasi setiap tahunnya adalah 2 (dua). Publikasi pertama sekitar bulan Agustus – September, publikasi kedua pada akhir tahun. Publikasi pertama baru bisa dilakukan setelah tahapan Pengujian Hardware. Setelah dilakukan pengembangan untuk penghematan lanjutan, diharapkan hasil penelitian akan lebih baik, sehingga publikasi kedua akan layak untuk dimuat pada jurnal baik ditingkat nasional maupun internasional. Indikator capaian penelitian ini berdasarkan perbandingan dengan metode konvensional atau dengan rangkaian yang diajukan oleh peneliti lain. Jika area yang diperlukan lebih sedikit dari area yang dibutuhkan oleh metode konvensional atau rangkaian yang dipublikasikan peneliti lain, maka penelitian ini dinilai berhasil. Indikator capaian kedua adalah diterimanya hasil penelitian ini pada seminar dan jurnal ilmiah.
10
BAB 5 HASIL DAN PEMBAHASAN
Penelitian ini dimulai sekitar pertengahan bulan februari. Sampai saat laporan ini dibuat, penelitian ini sudah selesai 100%. Tujuan tahap awal dari penelitian ini telah tercapai. Hal ini diperkuat dengan diterima dan hasil awal penelitian ini pada seminar internasional. Tujuan lanjut dari penelitian ini juga telah tercapai dengan submisi artikel pada jurnal internasional. Berikut akan dipaparkan beberapa rancangan desain rangkaian DFT dan efisiensi yang dicapai terhadap desain tersebut. 5.1 Desain Rangkaian DFT 4 point Walsh transforms merubah suatu sinyal pada domain waktu ke domain frekuensi dengan cara yang sangat sederhana. Matrik Walsh berisi bilangan +1 atau -1. Dari itu, pada proses perubahan tidak ada perkalian. Mari kita lihat Walsh matrik berikut untuk transform length N=4:
1 1 1 1
1 1 1 1 −1 −1 −1 1 −1 −1 −1 1
Pada saat perubahan hanya dibutuhkan penambahan dan pengurangan saja. Dan ini telah di demonstrasikan oleh banyak peneliti. Walaupun demikian, jenis transformasi ini jarang digunakan dalam aplikasi. Berbeda halnya dengan DFT, dia membutuhkan algoritma yang sangat rumit dalam melakukan proses transformasi. Namun DFT memberikan lebih banyak informasi tentang suatu sinyal di domain frekuensi. Matrik DFT bisa berisi bilangan bukan integer dan komplek. Sehingga, DFT membutuhkan rangkaian lebih dalam transformasi. Cara DFT melakukan proses transformasi dapat ditiru dari kebiasaan Walsh transforms, terutama untuk N=4. Berikut adalah matrik DFT (N=4):
1 1 1 1 1 − −1 1 −1 1 −1 1 −1 −
Matrik tersebut punya kesamaan dengan matrik Walsh. Matrik DFT berisi biangan positif atau negative kecuali untuk baris pertama. Kami telah mengembangkan algoritma yang menghubungkan kedua jenis transformasi tersebut. Kami memilih menggunakan perkalian dari fungsi Rademacher dalam pentransferan sinyal dari domain waktu ke domain frekuensi. Metode ini telah dikembangkan lebih untuk membedakan dan men treat bilangan komplek 11
(dalam kasus ini j dan –j). Gambar 4 menunjukkan blok diagram dan aliran data dari DFT 4-
Control Circuits
Output Buffers
Real Accumulators
Xr0 Xr1 Xr2 Xr3 Xi0
Output Buffers
Enter
Imaginer Accumulators
Negative Circuits
Multiplexers
x
Data Buffers
point yang dirancang.
Xi1 Xi2 Xi3
Gambar 4. Blok dan aliran data dari rancangan rangkaian DFT 4-point Blok diagram yang ditunjukkan pada gambar 4 terdiri dari:
-
Rangkaian Negatif Multiplexers Data buffers and Output buffers Real accumulators Imaginary accumulators Rangkaian Kontrol. Data input x dihubungkan ke rangkaian negative, multiplekser dan buffer data secara
parallel. Rangkaian negative digunakan untuk menyediakan nilai negative dari input data x. multiplekser digunaan untuk memilih apakah positif atau negative dari nilai x yang akan dilewatkan. Hubungan langsung antara input data x dengan buffer untuk menghindari pemilihan oleh multiplekser karena baris pertama dari matrik DFT hanya berisi nilai positif. Nilai yang terpilih akan dilewatkan ke real akumulator atau imaginer akumulaor melalui buffer-buffer juga di control oleh sinyal dari rangkaian control. Akhirnya, semua nilai yang tersimpan pada buffer output akan dilewatkan ke luar dan dianggap sebagai hasil DFT. buffer data dikontrol oleh rangkaian control, tetapi buffer output tidak. Buffer-buffer ini digunakan untuk menyimpan sementara nilai-nilai sebelum di keluarkan. Gambar 5 menampilkan algoritma dari blok yang telah dirancang pada gambar 4. Data input x dilewatkan ke system secara serial dan hasil DFT diambil secara parallel. Setiap kali sinyal Enter naik, sebuah data x dimasukkan ke system dan fungsi Rademacher dibangkitkan. Buffer (F0, F1, F2, F3) digunakan untuk menyimpan sementara input data. Buffer F1, F2, dan F3 akan menahan nilai sementara berdasarkan perkalian dari fungsi Rademacher. Jika R(1) tidak nol, buffer F3 akan menyimpan nilai negative dari x. jika R(0) adalh nol, buffer F2 akan meyimpa nilai positif dari x, nilai-nilai yang disimpan pada buffer F1 dan F3 akan dianggap 12
imaginer. Selain itu, jika R(0) tidak nol, buffer F2 akan menyimpan nilai negative dari x, nilai pada buffer F1 dan F3 akan diakumukasika pada real akumulator Real1 dan Real 3. Nilainilai baik pada real akumulator atau imaginer akumulator akan dianggap sebagai hasil DFT dan akan dilewatkan keluar dari system ketika Clock naik.
Gambar 5. Algoritma dari DFT 4-point berdasarkan perkalian dari fungsi Rademacher Gambar 6 menunjukkan rangkaia control yang digunakan untuk mengatur aliran data dari DFT 4-point yang di rancang. Rangkaian control dibangun berdasarkan fungsi Rademacher. Dalam prakteknya, fungsi Rademacher dapat dengan mudah dibangkitkan menggunakan sebuah counter. Sinyal-sinyal dibangkitan berdasarkan perkalian dari fungsi Rademacher. Sinyal R(0) dan R(1) diambil dari bit LSB dan MSB dari counter naik. Sementara sinyal Rxor adalah perkalian dari R(0) dan R(1). Sinyal-sinyal ini kemudian digunakan untuk mengontrol multiplekser dan akumulator.
13
R(0 ) Q(0) Q(1)
Counter up
Enter
Rxor R(1)
C
Gambar 6. Rangkaian kontrol berdasarkan fungsi Rademacher
5.2 Implementasi Rangkaian DFT 4 point Desain DFT 4-point yang diajukan telah diimplementasikan ke dalam FPGA. Berbagai jenis chip Xilinx telah dipilih dengan software Xilinx ISE 13.4. Desain di realisasikan dengan program VHDL. Gambar 7 menunjukkan hasil simulasi behavior dari rangkaian yang didesain. Data input x=[5,6,1,3] di lewatkan ke dalam rangkaian secara seri. Hasil dari DFT muncul secepatnya, tetapi ini bukan nilai akhir karena pada saat tersebut, tidak semua nilai input telah masuk. Hasil DFT yang betul dating setelah semua data telah dilewatkan. Disini keluaran DFT adalah Xr=[15,4,-3,4] dan Xi=[0,-3,0,3] mewakili bagian real dan imaginer. Data input x direpresentatsikan dalam mode 4 bit sign, sementara data output direpresentasikan dengan 6 bit sign. Hal tersebut untuk mengakomodir kemungkinan hasil penjumlahan.
Gambar 7. Hasil simulasi dari desain rangkaian DFT Tabel 4 memperlihatkan perbandingan kecepatan dari rangkaia yang didesain dalam berbgai chip Xilinx. Teknik DFT yang diajukan akan optimal kecepatannya jika di implementasikan dengan Artix 7. Beberapa parameter kecepatan disini adalah: frekuensi maksimum, waktu antar kedatangan dan waktu yang dibutuhkan output. Kintex 7 hampir
14
secepat Artix 7. Chip Spartan 3E dan Spartan 6 adalah yang paling lambat dibandingkan dengan yang lain, hal ini karena teknologi yang lama. Dalam hal area yang diperlukan, chip lama (Spartan 3E dan Spartan 6) membutuhkan lebih sedikit area dibandingkan dengan yang lain. Mereka hanya memerlukan 26 slice register dan 48 slice LUT. Sementara itu, chip dengan teknologi baru memerlukan area yang lebih. Hal tersebut dikarenakan chip-chip baru dilengkapi dengan LUT 6 input. Ini akan tidak terlalu efisien untuk rangkaian kecil. Perbandingan area yang diperlukan terpapar dengan jelas pada table 5. Table 4. Perbandingan kecepatan diantara chip Xilinx Speed Variables Chips Max Frequency Input arrival times Output require time MHz ns ns 555 0.820 0.737 Virtex 7 2.631 3.597 Spartan 6 352 631 0.758 0.681 Kintex 7 635 0.704 0.640 Artix 7 3.920 4.040 Spartan 3E 296 Tabel 5. Area yang diperlukan diantara chip Xilinx Chips Virtex 7 Spartan 6 Kintex 7 Artix 7 Spartan 3E
Area Variables Slice Registers Slice LUTs 43 56 26 48 43 56 43 56 26 48
5.3 Desain Rangkaian DFT 8 point Desain 8-point DFT diturunkan dari hasil penelitian sebelumnya yaitu desain rangkaian 4-point DFT yang digabungkan dengan teknik decimation in time (DIT). Gambar 8 memperlihatkan bagan 8-point DFT yang terkenal. Desain tersebut terdiri dari: • • • •
Dua buah 4-point DFT Empat buah 2-point DFT Tiga buah proses real multiplication Tiga buah proses imaginary multiplication Proses perkalian digunakan untuk menjalankan twiddle factor. Seperti yang telah
didemonstrasikan sebelumny pada, disana tidak membutuhkan proses perkalian untuk
15
rangkaian 4-point DFT. Namun demikian, untuk 8-point DFT harus dilengkapi dengan beberapa rangkaian proses perkalian.
Gambar 8. Skema bagan 8-point DFT Skema rangkaian pada gambar 8 menunjukkan blok-blok dan komponen secara umum. Dalam rangka menghubungkan blok-bok dengan komponen, dibutuhkan teknik khusus yang dapat melibatkan baik rangkaian real maupun imaginer. Jenis-jenis bilangan ini bisa diturunkan dari twiddle factor dari setiap blok atau komponen. Misalkan blok 4-point DFT, tabel 6 memperlihatkan semua kemungkinan jenis bilangan dari jika diasumsikan semua data input adalah real. Tabel 6. Jenis bilangan berdasarkan perhitungan twiddle factor k
Twiddle Factor
0
W40
Cos (0) – j Sin (0)
1
W4
1
W4
2
W4
3
2 3
Jenis Input
Jenis Output
1
x(0) : Real
X(0) : Real
Cos (2π/4) – j Sin (2π/4)
-j
x(1) : Real
X(1) : Real + Imaginary
Cos (4π/4) – j Sin (4π/4)
-1
x(2) : Real
X(2) : Real
Cos (6π/4) – j Sin (6π/4)
j
x(3) : Real
X(3) : Real + Imaginary
Beberapa hasil dari 4-point DFT dikalikan dengan twiddle factor (W81, W82 and W83). Perkalian ini dapat di analisa sebagai berikut, (R + I) x W81 = (R + I) x (Cos (2π/8) – j Sin (2π/8)) = (R + I) x (R + I) = R + I (R) x W82 = (R) x (Cos (4π/8) – j Sin (4π/8)) = (R) x ( I) = I (R + I) x W83 = (R + I) x (Cos (6π/8) – j Sin (6π/8)) = (R + I) x (R + I) = R + I Hasilnya adalah bahwa output dari 8-point DFT berisi bilanagn real dan imaginer kecuali untuk X(0) dan X(4) yang hanya berisi bilangan rela saja. Desain ini akan dianalisa kemudian
16
untuk menentukan kebutuhan buffer. Koneksi yang mengandung bilangan real dan imaginer membutuhkan dua kali lebih banyak buffer untuk penyimpanan data sementara. Jumlah ragkaian yang dibutuhkan untuk desain 8-point DFT sangat banyak. Namun dalam perspektif rangkaian, disana ada peluang untuk dihemat. Analisa yang mendalam untuk menentukan bagian mana saja yang bisa dioptimalkan. Pada desain sebelumnya, jenis bilangan yang digunakan untuk menghubungkan antar blok telah ditentukan. Disini, disediakan analisis dari bilangan-bilangan tersebut. Fenomena yang unik dari hasil DFT adalah ketika beberapa hasinya adalah komplek conjugate dari hasil yang lainnya. Sebagai contoh diberikan x={1,2,3,4,5,6,7,8}, kemudian hasil DFT adalah X={36, -4+9.66i, -4+4i, -4+1.66i, -4, -4-1.66i, -4-4i, -4-9.66i}. Dimana X1 ber komplek konjugate dengan X7, X2 ber komplek konjugate dengan X6 dan X3 ber komplek konjugate dengan X5, yang secara umum dapat diformulasikan sebagai berikut: −
∗
,
1,2, … , − 1
Dimana N=4,8,16, ….. hal ini sama dengan hasil-hasil 4-point DFT, D1=D3* (catatan: D adalah hasil 4-point DFT untuk membedakannya dengan hasil 8-point DFT). Gambar 9 menunjukkan mapping dari semua kemungkinan komplek conjugate dari rangkaian DFT yang dirancang.
Gambar 9. Hasil-hasil komplek konjugate Dengan didapatkannya komplek conjugate dari beberapa hasil DFT, rangkaian dapat dioptimalkan.
17
Dari gambar 9, dapat dilihat bahwa hasil-hasil dari 2-point DFT nomor 2 dan 4 adalah komplek conjugate satu sama lain. Dari itu, salah satu blok (DFT) ini dapat dihilangkan. Konsekuensinya, dibutuhkan sebuah rangkaian negative. Keuntungan lain dari penghilangan blok tersebut adalah salah satu komponen twiddle factor W81 atau W83 tidak dibutuhkan lagi. Hal tersebut juga akan mengurangi rangkaian dari kedua buah 4-point DFT. Proses perkalian pada W82 juga bisa dihilangkan karena besaran dari W82 adalah 1. Hasil dari 4-point DFT D2 sekarag dapat dihubungkan langsung dengan input dari 2-point DFT yang ketiga dan diasumsikan sebagai bilanga imaginer. Penghematan lain didapatkan pada kedua buah blok 4-point DFT karena ketidakterhubungan dari hasil D3. Gambar 10 menunjukkan desain rangkaian 8-point DFT yang efisien.
Gambar 10. Desain 8-point DFT ysng efisien Gambar 11 menunjukkan rangkaian dari 2-point DFT. rangkaian tersebut dikembangkan berdasarkan kesederhanaan dari twiddle factor W20 = 1 dan W21 = -1. Oleh karena itu, untuk mendapatkan hasil dari DFT tersebut dapat dilakukan hanya dengan menambahkan dan mengurangkan kedua input yang diberikan. Gambar 12 memperlihatkan 4-point DFT yang telah dimodifikasi. x(0) Adder
X(0)
Adder
X(1)
x(1)
Gambar 11. Rangkaian dari 2-point DFT 18
Real Accumulators
Output Buffers Output Buffer
Control Circuits
Imaginary Acc
Enter
Data Buffers
Negative Circuits
Multiplexers
x
Xr0 Xr1 Xr2
Xi1
Gambar 12. Rangkaian 4-point DFT yang telah di modifikasi Rangkaian 4-point DFT yang telah dimodifikasi lebih efisien, rangkaian tersebut hanya menggunakan lebih sedikit akumulator dan buffer. Dapat dilihat bahwa disana hanya ada emapat buah akumulator dan empat buah buffer. Desain sebelumnya membutuhkan delapan buah akumulator dan delapa buah buffer. Walaupun demikian, rangkaian ini tidak bisa digunakan sendiri, melainkan harus diintegrasikan dengan rangkaian lain untuk membentuk rangkaian 8-point DFT.
19
BAB 6 RENCANA TAHAPAN BERIKUTNYA
Penelitian penghematan area dari rangkaian komputasi elektronik direncanakan akan selesai setelah 3 tahun. Pada tahun pertama (2014), penelitian ini mempunyai dua tahapan tujuan yaitu tahap awal dan tahap lanjutan. Kedua tahapan tersebut telah tercapai dengan baik. Tahun kedua (2015) yang sedang berjalan, peneliti juga telah mendapatkan kedua tahapan tujuan. Tujuan tahap awal untuk mendesain 4-point DFT telah berhasil, begitu juga dengan tujuan tahap lanjutan yang telah berhasil menghemat rangkaian 8-point DFT. Sebagaimana pada tahun pertama dan kedua yang telah berjalan, penelitian penghematan area terhadap rangkaian transformasi fourier juga akan dijabarkan kedalam dua tahapan dalam masa satu tahun terakhir (2016). Tahapan awal terdiri dari langkah-langkah sebagai berikut: 1. Melakukan analisis statistik terhadap semua wordlengths yang digunakan dari rangkaian transformasi Fourier jenis Discrete Fourier Transform (DFT) khusus untuk yang lebih besar dari 8-point. 2. Mereduksi wordlengths dari rangkaian tersebut. 3. Membandingkan area dari rangkaian DFT yang telah direduksi wordlengths nya dengan area dari rangkaian DFT konvensional dan yang diajukan orang lain. Tahapan lanjutan terdiri dari langkah-langkah sebagai berikut: 1. Melakukan analisis secara statistik secara mendalam terhadap semua data-data yang mungkin digunakan untuk masukan ke rangkaian DFT. 2. Dari analisa tersebut, akan dirancang rangkaian DFT modifikasi. Hal ini bertujuan untuk mencapai hasil yang lebih optimal. 3. Mendokumentasikan dalam bentuk laporan penelitian dan mendiseminasikan hasil rancangan lanjutan tersebut pada jurnal internasional. 4. Memfinalisasi teknik/ metode efisiensi area dari rangkaian komputasi numerik.
20
BAB 7 KESIMPULAN DAN SARAN Rangkaian yang dipilih pada tahun kedua adalah transformasi Fourier. Tujuan awal dan lanjutan dari penelitian ini pada tahun 2015 telah tercapai. Rancangan dan implementasi dari 4-point DFT kedalam FPGA telah berhasil dilakukan. Hasil awal dari penelitian ini telah dipublikasikan pada seminar internasional ICEEI 10-11 agustus 2015. Rancangan yang lebih efisien untuk 8-point DFT telah berhasil dirancang. Rangkaian modifikasi jauh lebih efisien dalam hal jumlah komponen dan proses aritmatika dibandingkan dengan rangkaian secara umum. Hasil penelitian dari desain yang terakhir telah di submit pada jurnal internasional terindex Scopus (IJECE).
21
DAFTAR PUSTAKA
A. Amira, A. Bouridane, and P. Milligan, and P. Sage, “A High Throughput, FPGA Implementation of A Bit Level Matrix Product,” Proceeding of IEEE Workshop on Signal Processing Systems Design and Implementation (SIPS), LA, USA, pp: 356364, 2000. A. Amira, A. Bouridane, P. Milligan, and M. Roula, “An FPGA Implementation of WalshHadamard Transforms for Signal Processing,” Proceeding of IEEE International Conference on Acoustic, Speech and Signal Processing, Vol. 2, pp: 1105-1108, 2001. A note on random number generation. September 2009. Christophe Dutang dan Diethelm Wuertz. B. J. Falkowski, and T. Sasao, “Unified Algorithm to Generate Walsh Functions in Four Different Orderings and Its Programmable Hardware Implementations,” Proceeding of IEE on Vision, Image and Signal Processing, Vol. 152, Issue: 6, pp: 819-826, 2005. B. J. Fino and V. R. Algazi, “Unified Matrix Treatment of the Fast Walsh-Hadamard Transform,” IEEE Transactions on Computers, Vol. 42, pp: 1142-1146, 1976 D E Knuth. 2002. The Art of Computer Programming: seminumerical algorithms. Vol. 2, Edisi Ketiga. Massachusetts: Addison-Wesley. D H Lehmer. 1954. Random number generation on the BRL high speed computing machines. Oleh M L Juncosa. Math. Rev. 15, 559 http://www.letech.jpn.com. 2014. Genuine Random Number Generator (GRANG). 10 Maret. http://en.wikipedia.org. 2014. Comparison of hardware random number generators. 10 Maret http://en.wikipedia.org. 2014 - Linear congruential generator, 10th March http://en.wikipedia.org. 2014. List of random number generators, 11 Maret “Hadamard Transform.” en.wikipedia.org. Wikipedia, 6 Feb. 2011. Web. 27 Apr. 2011.
J.W. Cooley and J.W. Tukey. An Algorithm for the Machine Calculation of Complex Fourier Series. Math. Comp., Vol. 19, pp. 297-301, April 1965. John. G. Proakis, and Dimitris G. Manolakis, Digital signal processing: principles, algorithms, and applications, 4th ed., Pearson Prentice Hall, New Jersey, 2007. M Anis dkk. 2009. Low-Power Design of Nanometer FPGAs: Architecture and EDA. Morgan Kaufmann. M. Y. Zulfikar, S. A. Abbasi, and A. R. M. Alamoud, “FPGA Based Processing of Digital Signals using Walsh Analysis,” Proceeding of IEEE International Conference on Electrical, Control and Computer Engineering (INECCE 2011), pp: 440-444, 21-22 June, Pahang, Malaysia, 2011. Monir T. Hamood and, Said Boussakta, “Fast Walsh–Hadamard–Fourier transform algorithm,” Trans. Signal Processing, vol. 59, no. 11, pp. 5627-5631, November 2011 22
M. G. Karpovsky, R. S. Stankovic and J. T. Astola, Spectral Logic and Its Applications for The Design of Digital Devices, John Wiley & Sons Inc. Publication, New Jersey, 2008 N Harald. 1992. Random Number Generation and Quasi-Monte Carlo Methods. Society for lndustrial and Applied Mathematics. Philadelphia. Numerical Computing with MATLAB. 2008. By Cleve B. Moler, SIAM. P P Chu. 2006. RTL Hardware Design Using VHDL: Coding for Efficiency, Portability, and Scalability. Jhon Wiley and Sons. P. Duhamel, and M. Vetterli, “Fast Fourier Transforms: a tutorial, review and a state of the art,” Trans. Signal Processing, vol. 19, no. 4, pp. 259-299, April 1990. P. K. Meher, and J. C. Patra, “Fully-Pipelined Efficient Architectures for FPGA Realization of Discrete Hadamard Transform,” Proceeding of International Conference on Application Specific Systems, Architectures and Processors (ASAP 2008), pp: 43-48, 2008 S Hauck dkk. 2007. Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation. Morgan Kaufmann. S. K. Bahl, “Design and Prototyping a Fast Hadamard Transformer for WCDMA,” Proceeding of 14th IEEE International Workshop on Rapid Systems Prototyping, pp: 134-140, 2003 S K Park dan K W Miller (1988). Random number generators: good ones are hard to find. Association for Computing Machinery. 31(10). pp: 1192-2001. S Kilts. 2007. Advanced FPGA Design: Architecture, Implementation, and Optimization. Wiley-IEEE Press. S. Salivahanan, A. Vallavaraj, and C. Gnanapriya, Digital Signal Processing, McGraw Hill, New Delhi, 2000. S. Boussakta, and A. G. J. Holt, “Fast algorithm for calculation of both Walsh-Hadamard and Fourier transforms (FWFTs),” Electron. Letter, vol. 25, no. 20, pp. 1352-1354, 1989. Teng Su, and Feng. Yu, “A Family of Fast Hadamard–Fourier Transform Algorithms,” Signal Processing Letters, vol. 19, no. 9, pp. 583-586, September 2012. Wolfram Mathematica ® Tutorial Collection. 2008. Random Number Generation. www.doulos.com. 2013. VHDL Vector Arithmetic using Numeric_std. 8th March. Zulfikar. 2009. Generating Non Uniform Random Numbers Using Residue and Rejection Methods. Jurnal Rekayasa Elektrika. Vol. 8 No. 2. Zulfikar. 2014. FPGA Implementations of Uniform Random Number based on Residue Method. Jurnal Rekayasa Elektrika. Vol. 11 No. 1. Zulfikar. 2012. Novel Area Optimization in FPGA Implementation Using Efficient VHDL Code. Jurnal Rekayasa Elektrika. Vol. 10 No. 2.
23
Zulfikar dkk. 2012. FPGA Based Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing. Jurnal Electronics and Electrical Engineering. Vol.18. No. 8. Pp: 3-8. Zulfikar dan H Walidainy. 2014. Design and Implementations of Linear Congruential Generator into FPGA. International Journal of Electronics Communication and Computer Engineering. Vol. 5, Issue 4. Pp: 809-813. Zulfikar and H. Walidainy, "A Novel 4-Point Discrete Fourier Transforms Circuit based on Product of Rademacher Functions," IEEE Proceeding of International Conference of Electrical Engineering and Informatics (ICEEI), pp:142-147, Bali, Indonesia, August 10-11, 2015 Zulfikar, S. A. Abbasi, and A. R. M. Alamoud, “A Novel Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing,” Proceeding of IEEE International Conference on Communication Systems and Network Technologies (CSNT 2011), pp: 504-509, Katra, Jammu, 3-5 June, 2011. Zulfikar, S. A. Abbasi, and A. R. M. Alamoud, “FPGA Based Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing,” Transaction of Electronics and Electrical Engineering, vol. 18, no. 8, pp. 3-8, October 2012
24
LAMPIRAN I. BIODATA KETUA PENELITI A. Identitas Diri 1 2 3 4 5 6 7 8 9 10 11
Nama Lengkap (dengan gelar) Jenis Kelamin Jabatan Fungsional NIP NIDN Tempat dan Tanggal Lahir E-mail Nomor Telepon/HP Alamat Kantor Nomor Telepon/Faks Lulusan yang Telah Dihasilkan
Zulfikar, S.T., M.Sc. L Lektor 197507202006041003 0020077507 Kampung Sentosa, 20 Juli 1975 [email protected] 081280239034 Jl Syech Abdurrauf, Darussalam 0651-7554336 S-1= 5 orang; S-2= - orang; S-3= - orang 1. Elektronika Digital 2. Perancangan VLSI 3. Elektronika Industri 4. Teknik Digital 5. Elektronika Telekomunikasi 6. Sistem Kendali Terprogram
12. Mata Kuliah yang diampu
B. Riwayat Pendidikan Nama Perguruan Tinggi Bidang Ilmu Tahun Masuk-Lulus Judul Skripsi/Thesis
Nama Pembimbing/Promotor
S-1 Universitas Sumatera Utara Teknik Elektro 1994-1999 Pengalokasian pita suara dan data ke dalam jaringan B-ISDN
Ir. Zulfin, M.T.
S-2 King Saud University Teknik Elektro 2008-2011 An Intellectual Property Core for Spectrum Analysis, Synthesis and Processing of Periodic Multiple Digital Signals Prof. Shuja A Abbasi
C. Pengalaman Penelitian Dalam 5 Tahun Terakhir No. Tahun
Pendanaan Sumber Jml (Juta Rp)
Judul Penelitian
Metode Efisiensi Area Integrated Circuit (IC) 1 2015 dengan Reduksi Wordlengths untuk Meningkat kan Kinerja Perangkat Komputasi Elektronik Metode Efisiensi Area Integrated Circuit (IC) 2 2014 dengan Reduksi Wordlengths untuk Meningkat kan Kinerja Perangkat Komputasi Elektronik 3 2010 An Advanced Application Specific IC Research KSU : King Saud University 25
DIPA
67,5
DIPA
46
NPST
4.800
NPST: National Plant for Sciences Technology, Saudi Arabia D. Pengalaman Pengabdian Kepada Masyarakat dalam 5 Tahun Terakhir No. Tahun
Judul Pengabdian Kepada Masyarakat
1
Pengenalan Aplikasi Komputer untuk Guru SD Gugus Lambada Klieng Kecamatan Baitussalam Kabupaten Aceh Besar Pembinaan kelistrikan untuk keamanan dan penghematan energi kepada masyarakat Gampong Mon Mata Kecamatan Lhong Aceh Besar
2
2015
2012
Pendanaan Sumber Jml (Juta Rp) Mandiri
10,8
Mandiri
5,8
E. Publikasi Artikel Ilmiah Dalam Jurnal Dalam 5 Tahun Terakhir No. Judul Artikel Ilmiah 1
2
3
4
Desain Sistem Kontrol Traffic Light Adaptif pada Persimpangan Empat Berbasis PLC Siemens An Improved Design of Linear Congruential Generator based on Wordlengths Reduction Technique into FPGA FPGA Implementation of Uniform Random Number Using Residue and Rejection Method Design of Linear Congruential Generator based on Wordlengths Reduction Technique into FPGA
5
Processing of Multiple Digital Signals Based on Real-time Walsh Transform
6
FPGA Based Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing Novel Area Optimization in FPGA Implementation Using Efficient VHDL Code Design and Implementation of an Improved Arbitrary Waveform Generator Based on Walsh Functions Perancangan Pengontrolan Traffic Light Otomatis
7
8
9
26
Nama Jurnal
Volume/Nomor/ Tahun
Jurnal Nasional Teknik Elektro
Volume 4/ Nomor 1 Maret 2015
International Journal of Volume 5/ Nomor 1 Eletrical and Computer Feb 2015 Engineering Jurnal Rekayasa Elektrika International Journal of Electronics Communication Computer Engineering International Journal of Electrical and Computer Engineering Electronics and Electrical Engineering
Volume 11 / Nomor 1 / Tahun 2014 Volume 5 / Nomor 4 / Tahun 2014 Volume 3 / Nomor 2 / Tahun 2013
Volume 18 / Nomor 8 / Tahun 2012
Rekayasa Elektrika
Volume 10 / Nomor 2 / Tahun 2012
International Journal of Physical Sciences
Volume 7 / Nomor 10 / Tahun 2012
Rekayasa Elektrika
Volume 9 / Nomor 3 / Tahun 2011
LAMPIRAN II. ANGGOTA PENELITI A. Identitas Diri 1 2 3 4 5 6 7 8 9 10 11
Nama lengkap (dengan gelar) Jenis Kelamin Jabatan Fungsional NIP NIDN Tempat dan Tanggal Lahir E-mail Nomor Telepon/HP Alamat Kantor Nomor Telepon/Faks Lulusan yang Telah Dihasilkan
12 Mata Kuliah yang Diampu
Hubbul Walidainy, ST, MT L Lektor 197308262000121001 0026087301 Banda Aceh, 26 agustus 1973 [email protected] 0651 22905 Jl Syech Abdurrauf no 7, Darussalam S-1 = 32 orang; S-2 = … orang; S-3 = … orang 1. Dasar Telekomunikasi 2. Kalkulus 1 3. Elektronika Telekomunikasi 4. Analisis Numerik
B. Riwayat Pendidikan Nama Perguruan Tinggi Bidang Ilmu Tahun Masuk-Lulus Judul Skripsi/Tesis/Disertasi Nama Pembimbing/Promotor
S1 Univ. Gadjah Mada Teknik Elektro 1992-1998 Studi Kelayakan UMTS Adhi Soesanto, MSc, PhD
S2 Univ. Gadjah Mada Teknik Elektro 1999-2003 Proses Adaptif untuk Menghapus Gema Prof. Adhi Soesanto, MSc, PhD
C. Pengalaman Penelitian Dalam 5 Tahun Terakhir No Tahun
Judul Sumber
1
2
3
2015
2014
2012
Metode Efisiensi Area Integrated Circuit (IC) dengan Reduksi Wordlengths untuk Meningkat kan Kinerja Perangkat Komputasi Elektronik Metode Efisiensi Area Integrated Circuit (IC) dengan Reduksi Wordlengths untuk Meningkat kan Kinerja Perangkat Komputasi Elektronik Laboratorium Eksperimen: Pengaturan Tinggi Permukaan Cairan pada Tangki Secara Otomatis Menggunakan UniTrain Berbasis PID 28
Pendanaan Jml (Juta Rp)
DIPA
67,5
DIPA
46
DIPA
15
LAMPIRAN III. Publikasi artikel pada ICEEI 2015 Berikut adalah bukti publikasi artikel pada International Conference on Electrical Engineering and Information 2015 (ICEEI 2015).
30
The 5th International Conference on Electrical Engineering and Informatics 2015 August 10-11, 2015, Bali, Indonesia
A Novel 4-Point Discrete Fourier Transforms Circuit based on Product of Rademacher Functions Zulfikar1, Hubbul Walidainy2 Department of Electrical Engineering Syiah Kuala University Banda Aceh 23111, Indonesia. E-mail: [email protected], [email protected]
Abstract—This paper presents a new circuit design for implementing 4-point DFT algorithm based on product of Rademacher functions. The circuit has been derived from the similarity of how Fourier transforms and Walsh transforms are implemented. Walsh matrices contain numbers either +1 or -1 except for first row. Similarly, the 4-point DFT matrix contain numbers either positive or negative except for first row. This similarity has been taken into the case of how to implement the DFT circuit based on how Walsh transforms is generated. Since Walsh transforms is derived based on product of Rademacher functions, the proposed 4-point DFT circuit is designed according to product Rademacher functions. The circuit consist of negative circuit, multiplexers, accumulator (real and imaginary), buffers, and control circuit. The control circuit is designed to produce Rademacher functions for controlling and managing data flow. The 4-point DFT circuit has been successfully designed and implemented to FPGA platform. Among the selected chips, Artix 7 is the fastest one.
Keywords—DFT; Walsh transforms; Rademacher functions; DFT matrix; Walsh matrix
I. INTRODUCTION Digital signal processing is used in almost all electronics devices. The need for processing a signal is a must nowadays. Data or signal either from outside or internal have to process for specific purposes using specific application or processing. Often, data have to be transformed to other domains for easier processing. The most widely used transformation type is Fourier transforms. In terms of discrete model, Discrete Fourier Transforms (DFT) often used to converts signal or data to frequency domain. In domain frequency, it is easier to process and extract information of the data. This is a powerful transformation model that has been used since long time ago. The DFT is inefficient when it is implementing directly. Many scientist proposed simplification of the process of data transformation of DFT. Those simplifications lead to the development of Fast Fourier Transforms (FFT) algorithm. During previous several decades, researchers have been developed the algorithm of the FFT implementation such as Radix-2, Radix-4, Split Radix, Prime Factor Algorithm (FPA), and Winograd Fourier Transform (WFTA) [1]. Those
The authors gratefully acknowledge the financial support from Syiah Kuala University, Ministry of Education and Culture, Indonesia under project Hibah Bersaing, No. 035/SP2H/PL/Dit.Litabmas/II/2015, Feb 5, 2015. 142
algorithms have been developed for certain purposes and each of them comes with advantages and drawbacks. Walsh transforms algorithm is simpler than Fourier transform, but this transformation model is rarely used in application and almost forgotten. Walsh transforms has a few similarity to the Fourier transforms [2]-[5]. Based on this, some researchers have adopted this algorithm for developing the more efficient Fourier transforms [6]-[8]. An algorithm for calculating DFT using Walsh transforms is developed through the factorization of intermediate transform T [6]. Monir T et al proposed an efficient combination of Walsh and DFT calculation. The technique is based on the utilize Radix-4 fast Walsh Hadamard Transforms (FWHT) [7]. Another efficient technique of calculating both DFT and Walsh transforms by utilizing Radix-2 algorithm was also published [8]. The previous combination algorithms are designed for parallel input and output data. This leads to huge number of memory resources which is not suitable for small circuit applications. Therefore, we proposed an algorithm to minimize the use of memory by taking input serially and the output is gathered in parallel. This such algorithm may be achieved using product of Rademacher. The design has been done for 4point DFT, details of the design is covered in section III. In this paper, some basic theory of Walsh transforms, and Fourier transforms are covered in the next section. Section III provide the detail design of both algorithm and circuit for 4point DFT. Section IV views the implementation and discussion of the proposed algorithm into FPGA. Finally, the conclusion and some suggestions for future works are presented in the section V II. BACKGROUND THEORY A. Fourier Transforms The Fourier transforms is a tool that converts a waveform (a function or signal) into an alternate representation, characterized by cosine and sine. The Fourier Transforms indicates that any waveform may be re-written as the sum of sinusoidal functions [9]. Usually, Fourier transform is used to analyze the frequency content of a signal, design a system/ filter with particular properties, and solve differential equations in the frequency domain using algebraic operators. It is possible to develop an
Hadamard transforms for transform lengths N (N-point) can be performed by multiplying the input values (numbers) X with Hadamard matrix H to produce the output as the transformed coefficients matrix, Y as follows:
alternative Fourier representation for finite duration sequences that is referred to the Discrete Fourier Transforms (DFT) [9],[10]. DFT contains signal which is discrete and periodic, as can be expressed in the following expression (x(n) represents N point discrete signal in time domain).
Y=
1 (H N X ) N
(7)
N −1
X (k ) =
∑ x(n)WN nk
(1)
Hadamard matrix is a square matrix whose entries are either +1 or -1 and whose rows are mutually orthogonal. This matrix is another name of Walsh functions based on Hadamard ordering [12].
(2)
A direct implementation of eq. (7) in case input transform length N will require N2–N additions and subtractions. This huge area consumption, challenges many scientists to develop the more efficient computation algorithms. One such method to reduce number of additions and subtractions has been introduced in terms of unified matrix by Fino and Algazi [13]. The implementation of this idea require N(log2N) additions and subtractions. Many workers adopted Fino et al idea in order to realize the Walsh transform; Fast Hadamard Transform (FHT) is the popular one.
n=0
where
WN = e − j 2π / N , therefore N −1
N −1
X ( k ) = ∑ x ( n )e
− j 2πkn / N
= ∑ x ( n) e
(
)
− j 2π / N nk
n =0
n=0
Direct computation of the above equations is inefficient since they do not extract the symmetry and periodicity property as follows: (1)
Symmetry property:
WNk + N / 2 = −WNk (2)
(3)
Periodicity property k +N
Another way to perform Walsh transforms is by evaluating it in terms product of Rademacher functions [12]. It has attracted many scientists to develop effective and efficient structures. In general, Walsh transforms may be evaluated as follows
k
WN = WN (4) Direct computation of DFT of a complex value sequence x(n) can be expressed further as N −1 2πkn 2πkn ⎤ ⎡ + xI (n) sin X R (k ) = ∑ ⎢ xR (n) cos N ⎥⎦ N n =0 ⎣
(5)
N −1 2πkn 2πkn ⎤ ⎡ − xI (n) cos X I (k ) = −∑ ⎢ xR (n) sin N ⎥⎦ N n =0 ⎣
(6)
Yn =
1 N
N −1
∑ X ψ (n, t )
(8)
k
k =0
where ψ (n, t ) refers to any ordering of Walsh functions. III. CIRCUIT DESIGN
The DFT requires N2 (NxN) complex multiplications, which is each X(k) requires N complex multiplications. Therefore to determine the values of the DFT (from X(0) to X(N-1)) N2 multiplications are required. The DFT also requires (N-1)*N complex additions that is each X(k) requires N-1 additions. Therefore to evaluate all the values of the DFT (N1)*N additions are required [1],[9]
Walsh transforms converts a signal in time domain into frequency domain in very simple way. Walsh matrix contains number either +1 or -1. Therefore, in the transformation process, there will be no multiplication task. Let consider Walsh matrix for transform lengths N=4 as follow:
After Cooley and Tukey developed the divide-and-conquer method, many scientists proposed the algorithm for simplifying the calculation of DFT. All of them aim to reduce number of memory usage and arithmetic functions [1].
In performing the transformation, it requires addition or subtraction only. This has been performed in many works for certain signals [2],[3],[14]-[16]. In spite of this, this transformation method is rarely used in applications.
B. Walsh Transforms Walsh transforms performs a symmetric, orthogonal, and linear operation on 2m real numbers (or complex numbers). In terms of discrete one, Walsh transform is used to transform numbers (information) from time domain to frequency domain. A method of transforming information from time domain, represented in real numbers, is known as Hadamard transforms or Walsh Hadamard transforms. This method is also known as Walsh-Fourier transforms, since it is an example of a generalized class of Fourier transforms [11].
In contrast, DFT requires very complicated algorithm and circuit in performing transformation process. However, DFT provide more useful information about a signal in frequency domain. DFT matrix may contains non integer and complex numbers. Obviously, it would require more circuit in transformation process. The way of DFT performing transformation may be imitated the behavior of Walsh transforms performed, especially for N=4. Let’s consider DFT matrix (N=4) as follows.
143
condition. If R(1) is not zero, buffer F3 will store negative value of x. If R(0) is zero, buffer F2 store positive value of input data x, values stored in buffers F1 and F3 will consider as imaginary. Otherwise, if R(0) is not zero, buffer F2 will store negative value of x, the values in buffers F1 and F3 will be accumulated in real accumulators Real1 and Real3, respectively. The values either in real accumulators or in imaginer accumulators will consider as the DFT results and will be passing out the system when Clock is goes high.
Control Circuits
Real Accumulators
Output Buffers Output Buffers
Enter
Imaginer Accumulators
Negative Circuits
Multiplexers
x
Data Buffers
The matrix is quite similar to Walsh matrix. The 4-point DFT matrix contain numbers either positive or negative except for first row. We have developed the algorithm that connect both transforms method. We consider method of using product of Rademacher functions in transforming signal from time domain to frequency domain. The method has been develop more for distinguish and treats the complex numbers (in this case j and –j). Fig. 1 shows block diagram and data flow of the proposed 4-point DFT. Xr0 Xr1 Xr2 Xr3 Xi0 Xi1 Xi2 Xi3
Fig. 1. Blocks and data flow of the design 4-point DFT circuit
The design block diagram shown in the fig. 1 consist of: -
-
Negative circuit Multiplexers Data buffers and Output buffers Real accumulators Imaginary accumulators Control circuit.
Input data x is connected to negative circuit, multiplexers and data buffers in parallel. Negative circuit is used to provide negative value of input data x. multiplexers is used to selects either positive or negative value of input data x. The connection of data input x directly to the buffers in order to avoid selection of multiplexers since the first row of DFT matrix contain only positive value.
Fig. 2. Algorithm of 4-point DFT based on product of Rademacher functions
Fig. 3 shows design control circuit that is used to manage the data flow of the designed 4-point DFT circuit. The control circuit is developed based on Rademacher functions. In practice, Rademacher functions can be easily generated using a counter. The signals are generated based on product of Rademacher functions. Signal R(0) and R(1) are taken from the Least Significant Bit (LSB) and Most Significant Bit (MSB) of the counter up, respectively. Meanwhile, signal Rxor is product of R(0) and R(1). These signals are then used to control multiplexers and accumulators.
The selected values will be passed to either real accumulators or imaginary accumulators through buffers also controlled by the signal from control circuit. Finally all values stored in output buffers will be passing out and consider as the DFT results. Data buffers is controlled by the control circuit, but the output buffers is not. These buffers is used to stored temporary values before passing out. Fig. 2 views algorithm for the designed block of the fig. 1. Input data x is passing to the system in serial and the results of DFT are taking out in parallel. Every times signal Enter goes high, one data x is passing into the system and Rademacher functions is generated. Buffers (F0, F1, F2, F3) are used to stored input data temporary. Buffers F1, F2 and F3 will hold values temporary based on product of Rademacher functions
144
(b) Fig. 5. Configuration of control signal for: (a) Accumulator Real1 and Im1; (b) Accumulator Real3 and Im3
Fig. 3. Control circuits based on Rademacher functions
Fig. 4 shown the connections configuration of the control signals for multiplexers. The input data through Mux2 is control by signal R(0). If the signal is high, then positive x will be passed to buffer F2. Otherwise, negative x will be selected. The input data through mux1 is controlled by signal Rxor. When the signal is high, positive x will be pass to buffer F1. Similarly, when the signal control R(1) is high, the positive value of input data will be selected and passed to buffer F3.
IV. FPGA IMPLEMENTATION The proposed 4-point DFT design has been implemented into FPGA. Various Xilinx chips has been selected using Xilinx ISE 13.4 software. The proposed design is realized using VHDL codes. Fig. 6 shows the behavior simulation results of the design. Input data x=[5,6,1,3] is passing into the circuit serially. The resulting DFT comes immediately, but this is not the final values since at that time, not all input values has been passing in. The right DFT values comes up after all input data has been passed. Here the output DFT is Xr=[15,4,-3,4] and Xi=[0,-3,0,3] represent real and imaginary part, respectively. Input data x is represented in 4-bit sign number, meanwhile the output data are represented in 6-bit sign number. This is to accommodate the possibility of summation results [5],[17].
Fig. 4. Configuration of control signal for multiplexers
Fig. 5 shown the connection configuration of the control signals for accumulators. Initially, all accumulators is zero. Fig. 5(a) shows the configuration connection of control signal R(0) for enabling accumulator Real1 or Im1. If R(0) is equal to ‘1’, data in buffer F1 will be accumulated in accumulator Im1 (accumulator Real1 is disable). Otherwise, data in buffer F1 will be accumulated in accumulator Real1. The value stored in buffer F3 will be accumulated in accumulator Im3 (accumulator Real3 is disable) if signal control R(0) is high. The value will be accumulate in accumulator Real3 if R(0) is being low when the signal Enter goes high. This behavior is shown in the Fig. 5(b). Fig. 6. Simulation results of the design DFT circuit
Table I views speed comparison of the proposed circuit into various Xilinx chips. The proposed DFT circuit is best implement into Artix 7 in terms of speed parameters: maximum frequency, input arrival time and output require time. Kintex 7 chip almost as fast as Artix 7. Spartan 3E and Spartan 6 are very slow compare to other chips, this is due to old technology. In terms of occupies area, the old chips (Spartan 3E and Spartan 6) utilized less area than others. They require only 26 slice registers and 48 slice Look up Table (LUTs). Meanwhile the new technology chips utilized more area. This is might be because the new chips equipped with 6 input LUTs technology.
(a)
145
Clock to Setup on destination clock Enter ---------------+---------+---------+---------+---------+ | Src:Rise| Src:Fall| Src:Rise| Src:Fall| Source Clock |Dest:Rise|Dest:Rise|Dest:Fall|Dest:Fall| ---------------+---------+---------+---------+---------+ Enter | 1.608| | | | ---------------+---------+---------+---------+---------+
It would be not too efficient for small circuit implementation. The comparison of area occupies are listed in the Table II. TABLE I.
SPEED COMPARISON AMONG XILINX CHIPS Speed Variables
Chips
Max Frequency
Virtex 7 Spartan 6 Kintex 7 Artix 7 Spartan 3E
TABLE II.
Input arrival times
Output require time
MHz
ns
ns
555 352 631 635 296
0.820 2.631 0.758 0.704 3.920
0.737 3.597 0.681 0.640 4.040
Clock to Setup on destination clock clk ---------------+---------+---------+---------+---------+ | Src:Rise| Src:Fall| Src:Rise| Src:Fall| Source Clock |Dest:Rise|Dest:Rise|Dest:Fall|Dest:Fall| ---------------+---------+---------+---------+---------+ Enter | 2.519| | | | ---------------+---------+---------+---------+---------+
V. CONCLUSIONS The circuit and algorithm of 4-point DFT circuit based on product of Rademacher functions has been designed and implemented into FPGA successfully. Data comes into the circuit in serial, meanwhile the output data are provided in parallel. Among the targeted chips, Artix 7 is the fastest one and Spartan 3E and Spartan 6 occupies less area. There is no multiplication process in this design. However, in application, it is required circuit that is higher than 4-point DFT. In the future work, it is possible to develop the 8-point DFT or higher using this method. Higher point DFT is implemented efficiently using FFT method such as Radix-2. Therefore, this design is suitable for FFT algorithms. There is no comparison can be made to other methods since the FPGA implementation designed only for 4-point.
CCUPIES AREA COMPARISON AMONG XILINX CHIPS
Chips Virtex 7 Spartan 6 Kintex 7 Artix 7 Spartan 3E
Area Variables Slice Registers
Slice LUTs
43 26 43 43 26
56 48 56 56 48
The following data are concerning about static timing report of the design circuit that has been implemented into Artix 7 chip. It can be seen that maximum setup and hold to clock edge vary from 0.333 to 0.558 ns and 1.403 to 1.693 ns. Some clock to pad data are shown there, node XR1(2) (6.558 ns) is the slowest and node XR2(1) is the fastest (2.759 ns). Clock to setup on destination clock Enter is about 1.608 ns (rise) and clock to setup on destination clock clk is about 2.519 ns (rise). Device,package,speed:
REFERENCES [1]
[2]
xc7a100t,csg324,C,-3
[3]
Data Sheet report: All values displayed in nanoseconds (ns) Setup/Hold to clock Enter -------+------------+------------+--------+ |Max Setup to|Max Hold to | Clock | Source | clk (edge) | clk (edge) | Phase | -------+------------+------------+--------+ X<0> | 0.558(R)| 1.403(R)| 0.000| X<1> | 0.475(R)| 1.597(R)| 0.000| X<2> | 0.333(R)| 1.590(R)| 0.000| X<3> | 0.413(R)| 1.693(R)| 0.000| -------+------------+------------+--------+
[4]
[5]
Clock clk to Pad -----------+-----------------+------------------+------+ |Max (slowest) clk |Min (fastest) clk| Clock| Destination| (edge) to PAD | (edge) to PAD | Phase| -----------+-----------------+------------------+------+ XR1<2> | 6.558(R) | 2.912(R) | 0.000| XR1<3> | 6.396(R) | 2.816(R) | 0.000| XR2<0> | 6.359(R) | 2.780(R) | 0.000| XR2<1> | 6.335(R) | 2.759(R) | 0.000| XR3<2> | 6.554(R) | 2.908(R) | 0.000| -----------+-----------------+------------------+------+
[6]
[7]
[8]
146
P. Duhamel, and M. Vetterli, “Fast Fourier Transforms: a tutorial, review and a state of the art,” Trans. Signal Processing, vol. 19, no. 4, pp. 259-299, April 1990. A. Amira, A. Bouridane, and P. Milligan, and P. Sage, “A High Throughput, FPGA Implementation of A Bit Level Matrix Product,” Proceeding of IEEE Workshop on Signal Processing Systems Design and Implementation (SIPS), LA, USA, pp: 356-364, 2000. A. Amira, A. Bouridane, P. Milligan, and M. Roula, “An FPGA Implementation of Walsh-Hadamard Transforms for Signal Processing,” Proceeding of IEEE International Conference on Acoustic, Speech and Signal Processing, Vol. 2, pp: 1105-1108, 2001. M. Y. Zulfikar, S. A. Abbasi, and A. R. M. Alamoud, “FPGA Based Processing of Digital Signals using Walsh Analysis,” Proceeding of IEEE International Conference on Electrical, Control and Computer Engineering (INECCE 2011), pp: 440-444, 21-22 June, Pahang, Malaysia, 2011. Zulfikar, S. A. Abbasi, and A. R. M. Alamoud, “A Novel Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing,” Proceeding of IEEE International Conference on Communication Systems and Network Technologies (CSNT 2011), pp: 504-509, Katra, Jammu, 3-5 June, 2011. S. Boussakta, and A. G. J. Holt, “Fast algorithm for calculation of both Walsh-Hadamard and Fourier transforms (FWFTs),” Electron. Letter, vol. 25, no. 20, pp. 1352-1354, 1989. Monir T. Hamood and, Said Boussakta, “Fast Walsh–Hadamard–Fourier transform algorithm,” Trans. Signal Processing, vol. 59, no. 11, pp. 5627-5631, November 2011 Teng Su, and Feng. Yu, “A Family of Fast Hadamard–Fourier Transform Algorithms,” Signal Processing Letters, vol. 19, no. 9, pp. 583-586, September 2012.
[9]
[10] [11] [12]
[13]
[14]
[15] B. J. Falkowski, and T. Sasao, “Unified Algorithm to Generate Walsh Functions in Four Different Orderings and Its Programmable Hardware Implementations,” Proceeding of IEE on Vision, Image and Signal Processing, Vol. 152, Issue: 6, pp: 819-826, 2005. [16] P. K. Meher, and J. C. Patra, “Fully-Pipelined Efficient Architectures for FPGA Realization of Discrete Hadamard Transform,” Proceeding of International Conference on Application Specific Systems, Architectures and Processors (ASAP 2008), pp: 43-48, 2008 [17] Zulfikar, S. A. Abbasi, and A. R. M. Alamoud, “FPGA Based Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing,” Transaction of Electronics and Electrical Engineering, vol. 18, no. 8, pp. 3-8, October 2012.
John. G. Proakis, and Dimitris G. Manolakis, Digital signal processing: principles, algorithms, and applications, 4th ed., Pearson Prentice Hall, New Jersey, 2007. S. Salivahanan, A. Vallavaraj, and C. Gnanapriya, Digital Signal Processing, McGraw Hill, New Delhi, 2000. “Hadamard Transform.” en.wikipedia.org. Wikipedia, 6 Feb. 2011. Web. 27 Apr. 2011. M. G. Karpovsky, R. S. Stankovic and J. T. Astola, Spectral Logic and Its Applications for The Design of Digital Devices, John Wiley & Sons Inc. Publication, New Jersey, 2008 B. J. Fino and V. R. Algazi, “Unified Matrix Treatment of the Fast Walsh-Hadamard Transform,” IEEE Transactions on Computers, Vol. 42, pp: 1142-1146, 1976 S. K. Bahl, “Design and Prototyping a Fast Hadamard Transformer for WCDMA,” Proceeding of 14th IEEE International Workshop on Rapid Systems Prototyping, pp: 134-140, 2003
147
LAMPIRAN IV. Publikasi pada Jurnal Internasional Berikut adalah artikel dan bukti submisi pada pada International Journal of Electrical and Computer Engineering (IJECE)..
31
International Journal of Electrical and Computer Engineering (IJECE) Vol.x, No.x, September 201x, pp. xx~xx ISSN: 2088-8708
31
Design of 8-point DFT based on Rademacher Functions Zulfikar, Hubbul Walidainy Department of Electrical Engineering, Syiah Kuala University
Article Info
ABSTRACT
Article history:
This paper presents a new circuit design for 8-point DFT algorithm based on product of Rademacher functions. The design has been adopted from the famous 8-point DFT decimation in time which is mainly constructs of two 4point and four 2-point DFTs. However, the operation of the design circuit is different. It utilized the advantage of Rademacher functions simplicity. Therefore, the proposed design is constructed form the previous design 4-point DFT which is based on product of Rademacher functions [6]. Some analysis upon number types and internal connections to achieve a more efficient circuit have been conducted. As a result, instead of four, the proposed design requires only three 2-point DFT. Several output results of the design DFT have been removed since they are equal in terms of magnitude, two negative circuit are required as a compensation. Moreover, the previous 4-point DFT has been replaced to the efficient one. This circuit is special designed for non stand alone used, the circuit must be integrated inside the proposed 8-point DFT.
Keyword: 4-point DFT 8-point DFT Walsh transforms Rademacher functions Twiddle Factor FFT
Copyright © 201x Institute of Advanced Engineering and Science. All rights reserved.
Corresponding Author: Department of Electrical Engineering, Syiah Kuala University, Jl Syech Abdur Rauf, Darussalam, Banda Aceh, Indonesia. Email: [email protected]
1.
INTRODUCTION
No doubt that Fourier transforms is used ubiquitous. The Fourier algorithms is available in terms of both continues and discrete models. Discrete model of Fourier which is often called Discrete Fourier Transforms (DFT) is more suitable for application since the development of computing machines that limits the ability of calculation. Unlike discrete, the continues model is very difficult to implement. The development of Fourier transforms has been done since about a century ago. However, because of the huge number of applications of this, it is still attracted scientists to develop a more and more efficient and fast algorithms for implementing the transforms in the applications. Duhamel and Veterli summarized, analyzed and provided some suggestions of those development in 1990 [1]. The most significant improvement of Fourier is when Cooley and Tukey introduced a method for factorization it [2]. After that, thousands number of paper appears for implementing Fourier in applications. Scientists have been developed the algorithms of Fourier transforms that combines Walsh and Fourier transforms [3]-[5]. The developments are based on the simplicity calculation of Walsh transforms that often ignored by researchers before. Those algorithms such as Walsh transforms is adopted through factorization of intermediate transforms T for calculation of DFT coefficients [3]. Monir T et al then proposed the efficient combination of DFT and Walsh calculations. This technique is used to perform Fast Walsh Hadamard Transforms (FWHT) by utilizing Radix-4 [4]. Later then, the efficient algorithm of calculating both Walsh transforms and DFT transforms using the famous Radix-2 was also published [5]. The previous combination algorithms are designed for parallel input and output data. This leads to huge number of memory resources which is not suitable for small circuit applications. A method for reducing circuit resources has been proposed in [6]. The circuit is designed by taking input serially and the output is gathered in
Journal homepage: http://iaesjournal.com/online/index.php/IJECE
ISSN: 2088-8708
32
parallel. The proposed method used to design 4-point DFT that adopts behavior of how Walsh transforms is generated. The previous DFT has been done only for 4-point, which is very simple and rarely used in the application. The higher circuit point is required. Therefore, in this paper, we propose a design of 8-point DFT that is build up using the previous 4-point DFT design. Two 4-point DFT and four 2-point DFT are required for the proposed design. Some basic theory of DFTs are covered in the theory section. Next section provides the detail step by step circuit design for area efficiency of 8-point DFT. Section 4 views the analysis results and a few discussions of the proposed design. Finally, the conclusions and some suggestions for future works are presented in the section 5. 2.
THEORY
2.1. 2-Point and 4-Point Discrete Fourier Transforms DFT plays a very important role in almost all digital applications such as signal processing, spectrum analysis and filtering process. Many scientists proposed the theory and implementation of how DFT efficiently used. The basic calculation of DFT is using equation (1) as follow [7]-[9], = Where =
,
0≤
≤
−1
/
Small point number (N) of DFT is very simple and may be often ignored in discussion. However higher N-point DFTs are constructed from smaller ones. For instance, 8-point DFT based on FFT algorithm is developed using 2-point and 4-point DFTs. The 2-point DFT may be calculated easily according to eqs (1) and (2). For instance, given x(n) = {2, 5}, let us compute twiddle factors for the DFT. W20 = cos (0) – j sin (0) = 1 W21 = cos (π) – j sin (π) = -1 Therefore, X(0) = x(0)W20 + x(1)W20 = 2(1) + 5(1) = 2 + 5 = 7 X(1) = x(0)W20 + x(1)W21 = 2(1) + (-1)(5) = 2 – 5 = -3 The circuit for 2-point DFT is very easy to be created since it contains only addition and subtraction. Let s consider higher N such as 4-point DFT. Given x(n) = {2,4,3,5}, the twiddle factors can be evaluated as follows: W40 = cos (0) – j sin (0) = 1 W41 = cos (π/2) – j sin (π/2) = -j W42 = cos (π) – j sin (π) = -1 W43 = cos (3π/2) – j sin (3π/2) = j Therefore, X(0) = x(0)W40 + x(1)W40 + x(2)W40 + x(3)W40 = 2 + 4 + 3 + 5 = 14 X(1) = x(0)W40 + x(1)W41 + x(2)W42 + x(3)W43 = 2 - 4j – 3 + 5j = -1 + j X(2) = x(0)W40 + x(1)W42 + x(2)W40 + x(3)W42 = 2 - 4 + 3 - 5 = -4 X(3) = x(0)W40 + x(1)W43 + x(2)W42 + x(3)W41 = 2 + 4j – 3 - 5j = -1 - j The computation of 4-point DFT demonstrated here would not require multiplication process, it similar to the 2point DFT’s. However, because it is contain imaginary part, we separate the results into different buffers. This has been demonstrated before [6]. 2.2. Rademacher Functions Some works preferred to perform Walsh transform based upon product of Rademacher functions. This is found to be more appropriate for circuit realization [9]-[13]. The Rademacher functions itself are defined as follows. ∅ + 1, = | ! sin2π2 , = 0,1,2, … 0 ≤ < 1 0 Where ϕ(0,x)=1 and the signum function Sgn(y) is determined as follows, +1, ) ≥ 0, ! ) =* −1, ) < 0, In practice, the Rademacher functions can be easily generated by simply using a counter.
IJECE Vol. x, No. x, September 201x : xx – xx
IJECE 3.
ISSN: 2088-8708
33
Design of 8-Point Discrete Fourier Transforms
3.1. General Circuit Design This paper propose the circuit design of 8-point DFT based on product of Rademacher functions. The design has been derived from the previous work of 4-point DFT [6] combined with the common 8-point DFT decimation in time design. Figure 1 shows the famous 8-point DFT based on decimation in time. The design consist of several smaller DFT and may involve some arithmetic process as follow: • Two 4-point DFTs • Four 2-point DFTs • Three real multiplication process • Three imaginary multiplication process The multiplication process is used to handle the twiddle factors. As demonstrated in [6], there is no multiplication process required for 4-point DFT. However, in the case of 8-point DFT, the circuit have to be equipped with some multiplier circuits.
Figure 1. Scheme of 8-point DFT [1]
3.2. Type of Number The circuit scheme of Figure 1 shows blocks and component in general view. In order to integrate blocks and components, it requires specific handling that may involve real and imaginary numbers. The connections between blocks or components that involve both real and imaginary numbers requires more circuit. Figure 2 shows all possible of real (noted “R”) and imaginary (noted “I”) numbers.
Title of manuscript is short and clear, implies research results (First Author)
ISSN: 2088-8708
34
Figure 2. Type of numbers for connections Those type of numbers have been derived from the twiddle factor of each block or component. Let us consider the both 4-point DFT blocks, table 1 shows all possible number type of the result for all input real numbers. k 0 1 2 3
Twiddle Factor W4 0 Cos (0) – j Sin (0) W4 1 Cos (2π/4) – j Sin (2π/4) W4 2 Cos (4π/4) – j Sin (4π/4) W4 3 Cos (6π/4) – j Sin (6π/4)
1 -j -1 j
Type of Input x(0) : Real x(1) : Real x(2) : Real x(3) : Real
Type of Output X(0) : Real X(1) : Real + Imaginary X(2) : Real X(3) : Real + Imaginary
Some results of the second 4-point DFT are multiplied with twiddle factors (W81, W82 and W83). These multiplication can be examined as follow, (R + I) x W81 = (R + I) x (Cos (2π/8) – j Sin (2π/8)) = (R + I) x (R + I) = R + I (R) x W82 = (R) x (Cos (4π/8) – j Sin (4π/8)) = (R) x ( I) = I (R + I) x W83 = (R + I) x (Cos (6π/8) – j Sin (6π/8)) = (R + I) x (R + I) = R + I As the results, the output of 8-point DFT contains real and imaginary number except for X(0) and X(4) which is contains only real numbers. This is because both inputs of the 2-point DFT is real numbers only. This design will be further analyzed for determining the amount of buffer required. The connections that involve both real and imaginary requires twice number of buffer for storing data temporarily.
3.3. Interconnect Configuration The designed 8-point DFT mainly requires two 4-point DFTs and four 2-point DFTs. These amount of DFTs will requires huge numbers of circuit. However, in terms of circuit perspective, there is a space to reduce the circuit. A deep analysis is required for determining in which part of the whole circuit can be optimized. In the previous section, the type of numbers used for connecting blocks has been determined. Here, we provide deep analysis of those numbers. The results of DFT shows the unique phenomena, since some of them complex conjugate to the other result [7],[8]. For example given x={1,2,3,4,5,6,7,8}, the DFT results are X={36, -4+9.66i, -4+4i, -4+1.66i, -4, 4-1.66i, -4-4i, -4-9.66i}. Where, X1 complex conjugate with X7, X2 complex conjugate with X6 and X3 complex conjugate with X5. In general formula, , − -=
∗
, + - ,
/01
= 1,2, … , − 1
IJECE Vol. x, No. x, September 201x : xx – xx
IJECE
ISSN: 2088-8708
35
Where N=4,8,16, ….. This behavior similar to the 4-point DFT results, D1=D3* (note: D refers to the DFT result of 4-point DFT in order to differentiate it to the 8-point DFT result). Figure 3 shows mapping of all possible complex conjugate results of the designed 8-point DFT.
Figure 3. Complex conjugate results By determining complex conjugate of some DFT results, the circuit can be optimized. 4.
CIRCUIT COMPLEXITY In the previous, analysis of number’s type and complex conjugate of the results has been made. Therefore, the designed circuit may now to be optimized by reducing unneeded component or block. However, there is a cost for doing this. From the figure 3, it can be seen that the results of 2nd and 4th 2-point DFT are complex conjugate to each other. Therefore, one of these blocks can be removed. As a consequence of removing the block, it is required a negative circuit. Another advantage of removing the DFT block, either component of twiddle factor W81 or W83 is not required anymore. This also will reduce the 4-poit DFT circuit due to disconnected of either D1 or D3. The multiplication process in the W82 also can be removed because the magnitude of W82 is -1. The result 4-point DFT D2 may now connected directly to the input of the third 2-point DFT and assumed it as an imaginary number. Another efficiency can be applied in the both blocks of 4-point DFT due to the unconnected of result D3. Figure 4 the efficient circuit design of 8-point DFT.
Title of manuscript is short and clear, implies research results (First Author)
ISSN: 2088-8708
36
Figure 4. Efficient 8-point DFT Figure 5 shows the circuit of 2-point DFT. The circuit has been developed based on the simplicity of twiddle factors W20 = 1 and W21 = -1. Therefore, for determining the results just simply add and subtract both given inputs. Figure 6 shows the modified 4-point DFT that has been proposed before in [6]. x(0) Adder
X(0)
Adder
X(1)
x(1)
Real Accumulators
Output Buffers Output Buffer
Enter
Control Circuits
Imaginary Acc
Negative Circuits
Multiplexers
x
Data Buffers
Figure 5. Circuit of 2-point DFT Xr 0 Xr 1 Xr2
Xi1
Figure 6. Proposed modified 4-point DFT The modified circuit of 4-point DFT is more efficient, it utilized less accumulator and buffer. It can be seen there are four accumulators and four output buffers. The previous design required eight accumulators and eight output buffers [6]. However this circuit cannot used as a single application, it must be integrated I order to form the 8-point DFT. IJECE Vol. x, No. x, September 201x : xx – xx
IJECE
ISSN: 2088-8708
37
5.
CONCLUSIONS The design of 8-point DFT circuit based on product of Rademacher functions has been done. It consists of smaller DFT blocks which are two 4-point DFT and four 2-point DFT. The analysis of type number used and internal connections has been accomplished. Based on these, the efficient 8-point DFT has been achieved. The efficient circuit involved two modified 4-poit DFT and three 2-point DFT. Moreover, the design of modified 4point DFT and the simple 2-point DFT also has been designed. Several output results of the design DFT have been removed since they are equal in terms of magnitude, two negative circuit are required as a compensation.
ACKNOWLEDGEMENTS The authors gratefully acknowledge the financial support from Syiah Kuala University, Ministry of Education and Culture, Indonesia under project Hibah Bersaing, No. 035/SP2H/PL/Dit.Litabmas/II/2015, Feb 5, 2015. REFERENCES [1] [2] [3] [4] [5] [6]
[7] [8] [9] [10]
[11]
[12]
[13]
P. Duhamel, and M. Vetterli, “Fast Fourier Transforms: a tutorial, review and a state of the art,” Trans. Signal Processing, vol. 19, no. 4, pp. 259-299, April 1990. J.W. Cooley and J.W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series," Math. Comp., Vol. 19, pp. 297-301, April 1965. S. Boussakta, and A. G. J. Holt, “Fast algorithm for calculation of both Walsh-Hadamard and Fourier transforms (FWFTs),” Electron. Letter, vol. 25, no. 20, pp. 1352-1354, 1989. Monir T. Hamood and, Said Boussakta, “Fast Walsh–Hadamard–Fourier transform algorithm,” Trans. Signal Processing, vol. 59, no. 11, pp. 5627-5631, November 2011 Teng Su, and Feng. Yu, “A Family of Fast Hadamard–Fourier Transform Algorithms,” Signal Processing Letters, vol. 19, no. 9, pp. 583-586, September 2012. Zulfikar and H. Walidainy, "A Novel 4-Point Discrete Fourier Transforms Circuit based on Product of Rademacher Functions," IEEE Proceeding of International Conference of Electrical Engineering and Informatics (ICEEI), pp:142-147, Bali, Indonesia, August 10-11, 2015 John. G. Proakis, and Dimitris G. Manolakis, Digital signal processing: principles, algorithms, and applications, 4th ed., Pearson Prentice Hall, New Jersey, 2007. S. Salivahanan, A. Vallavaraj, and C. Gnanapriya, Digital Signal Processing, McGraw Hill, New Delhi, 2000. M. G. Karpovsky, R. S. Stankovic and J. T. Astola, Spectral Logic and Its Applications for The Design of Digital Devices, John Wiley & Sons Inc. Publication, New Jersey, 2008 M. Y. Zulfikar, S. A. Abbasi, and A. R. M. Alamoud, “FPGA Based Analysis and Multiplication of Digital Signals,” Proceeding of IEEE Second International Conference on Advances in Computing, Control, and Telecommunication Technologies (ACT 2010), pp: 32-36, Jakarta, Indonesia, 2010. M. Y. Zulfikar, S. A. Abbasi, and A. R. M. Alamoud, “FPGA Based Processing of Digital Signals using Walsh Analysis,” Proceeding of IEEE International Conference on Electrical, Control and Computer Engineering (INECCE 2011), pp: 440-444, 2122 June, Pahang, Malaysia, 2011. Zulfikar, S. A. Abbasi, and A. R. M. Alamoud, “A Novel Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing,” Proceeding of IEEE International Conference on Communication Systems and Network Technologies (CSNT 2011), pp: 504-509, Katra, Jammu, 3-5 June, 2011. Zulfikar, S. A. Abbasi, and A. R. M. Alamoud, “FPGA Based Complete Set of Walsh and Inverse Walsh Transforms for Signal Processing,” Transaction of Electronics and Electrical Engineering, vol. 18, no. 8, pp. 3-8, October 2012.
BIBLIOGRAPHY OF AUTHORS Zulfikar He was born in Beureunuen, Aceh, Indonesia, in 1975. He received his B.Sc. degree in Electrical Engineering from North Sumatera University, Medan, Indonesia, the M. Sc. Degree in Electrical Engineering from King Saud University, Riyadh, Saudi Arabia, in 1999 and 2011, respectively. He joined as teaching staff in the Department of Electronics at Politeknik Caltex Riau, Pekanbaru, Indonesia in 2003. He served as head of Industrial Control Laboratory, Politeknik Caltex Riau from 2003 to 2006. In 2006, he joined the Electrical Engineering Department, Syiah Kuala University. He has been appointed as head of Digital Laboratory for two successive years. His current research interests include VLSI design and System on Chips (SoC).
Title of manuscript is short and clear, implies research results (First Author)
ISSN: 2088-8708
38
Hubbul Walidainy He was born in Banda Aceh, Aceh, Indonesia, in 1973. He graduated from Electrical Engineering Department at Gadjah Mada University, Yogyakarta, Indonesia, in 1998. The Master Degree in Electrical Engineering from Gadjah Mada University, Yogyakarta, Indonesia, in 2003. He joined in the Department of Electrical Engineering, Syiah Kuala University, Aceh, Indonesia in 2000, as a teaching staff. His current position is the head of Telecommunication Laboratory. His current research interests include all issues in Digital Signal Processing (DSP).
IJECE Vol. x, No. x, September 201x : xx – xx
Zulfikar Yahoo From: Sent: To: Subject:
Tole Sutikno Monday, October 19, 2015 5:19 PM Zulfikar Zulfikar [IJECE] Submission Acknowledgement
Dear Zulfikar Zulfikar: Thank you for submitting the manuscript, "Design of 8-point DFT based on Rademacher Functions" to International Journal of Electrical and Computer Engineering (IJECE). With the online journal management system that we are using, you will be able to track its progress through the editorial process by logging in to the journal web site: Manuscript URL: http://iaesjournal.com/online/index.php/IJECE/author/submission/9218 Username: zulfikarsafrina If you have any questions, please contact us. Please refer to your paper ID whenever you communicate with our Editorial Office in the future. Your paper ID is latest number at Manuscript URL. Thank you for considering this journal as a venue for your work. Best Regards, Tole Sutikno International Journal of Electrical and Computer Engineering (IJECE) ________________________________________________________________________ International Journal of Electrical and Computer Engineering http://iaesjournal.com/online/index.php/IJECE
1
