Landasan Teori Hukum, Manajemen Keuangan, Kesehatan, Internasional, Ekonomi

Friday, 2 October 2015

Pengertian Transformasi Fourier Diskrit Perbandingan Fast Fourier Transform

Pengertian Transformasi Fourier - Proses penting dalam pemrosesan sinyal digital adalah menganalisis suatu sinyal input maupun output untuk mengetahui karakteristik sistem fisis tertentu dari sinyal. Proses analisis dan sintesis dalam domain waktu memerlukan analisis cukup panjang dengan melibatkan turunan dari fungsi, yang dapat menimbulkan ketidaktelitian hasil analisis. Analisis dan sintesis sinyal akan lebih mudah dilakukan pada domain frekuensi, karena besaran yang paling menentukan suatu sinyal adalah frekuensi. Oleh karena  itu, untuk dapat bekerja pada domain frekuensi dibutuhkan suatu formulasi yang tepat sehingga proses manipulasi sinyal sesuai dengan kenyataan. Salah satu teknik untuk menganalisis sinyal adalah mentransformasikan (alih bentuk) sinyal yang semula analog menjadi diskrit dalam domain waktu, dan kemudian diubah ke dalam domain frekuensi.


Transformasi Fourier adalah suatu model transformasi yang memindahkan sinyal domain spasial atau sinyal domain waktu menjadi sinyal domain frekuensi. Di dalam pengolahan suara, transformasi fourier banyak digunakan untuk mengubah domain spasial pada suara menjadi domain frekuensi. Analisa-analisa dalam domain frekuensi banyak digunakan seperti filtering. Dengan menggunakan transformasi fourier, sinyal atau suara dapat dilihat sebagai suatu objek dalam domain frekuensi.


Transformasi Fourier Diskrit

Transformasi Fourier Diskrit (Discrete Fourier Transform - DFT) adalah prosedur yang paling umum dan kuat pada bidang pemrosesan sinyal digital. DFT memungkinkan untuk menganalisis, memanipulasi, dan mensintesis sinyal  dengan cara yang tidak mungkin dilakukan dalam pemrosesan sinyal analog Lyons, Richard G. 1997. Understanding Digital Signal Processing. Prentice Hall PTR... Meskipun sekarang digunakan dalam hampir setiap bidang teknik. Aplikasi yang menggunakan DFT terus berkembang sebagai utilitas yang menjadikan DFT lebih mudah untuk dimengerti. Karena itu, pemahaman yang kuat tentang DFT adalah wajib bagi siapa saja yang bekerja di bidang pemrosesan sinyal digital.

DFT merupakan prosedur matematika yang digunakan untuk menentukan harmonik atau frekuensi yang merupakan isi dari urutan sinyal diskrit. Urutan sinyal diskrit adalah urutan nilai yang diperoleh dari sampling periodik sinyal kontinu dalam domain waktu. DFT berasal dari fungsi Transformasi Fourier X(f) yang didefinisikan:



Dalam bidang pemrosesan sinyal kontinu, Persamaan 2.1 digunakan untuk mengubah fungsi domain waktu kontinu x(t) menjadi fungsi domain frekuensi kontinu X(f). Fungsi X(f) memungkinkan untuk menentukan kandungan isi frekuensi dari beberapa sinyal dan menjadikan beragam analisis sinyal dan pengolahan yang dipakai di bidang teknik dan fisika. Dengan munculnya komputer digital, ilmuwan di bidang pengolahan digital berhasil mendefenisikan DFT sebagai urutan sinyal diskrit domain frekuensi X(m), dimana:



Meski lebih rumit daripada Persamaan 2.2, Persamaan 2.3 lebih mudah untuk dipahami. Konstanta j = √−1 hanya membantu membandingkan hubungan fase di dalam  berbagai  komponen  sinusoidal  dari  sinyal.  Nilai  N  merupakan    parameter penting karena menentukan berapa banyak sampel masukan yang diperlukan, hasil domain frekuensi dan jumlah waktu proses yang diperlukan untuk menghitung N-titik DFT. Diperlukan N-perkalian kompleks dan N-1 sebagai tambahan. Kemudian, setiap perkalian membutuhkan N-perkalian riil, sehingga untuk menghitung seluruh nilai N (X(0), X(1), …, X(N-1)) memerlukan N2 perkalian. Hal ini menyebabkan perhitungan DFT memakan waktu yang lama jika jumlah sampel yang akan diproses dalam jumlah besar.

Fast Fourier Transform

Meskipun DFT memainkan peranan yang penting sebagai prosedur matematis untuk menentukan isi frekuensi dari urutan domain waktu, namun sangat tidak efisien. Jumlah titik dalam DFT meningkat menjadi ratusan atau ribuan, sehingga jumlah- jumlah yang dihitung menjadi tidak dapat ditentukan. Pada tahun 1965 sebuah makalah diterbitkan oleh Cooley dan Tukey menjelaskan algoritma yang sangat  efisien untuk menerapkan DFT Cooley, J. & Tukey, J. 1965. An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation. pp. 297-301.. Algoritma yang sekarang dikenal sebagai Fast Fourier Transform (FFT). Sebelum munculnya FFT, seribu titik DFT membutuhkan waktu begitu lama untuk melakukan perhitungan yang pada saat itu masih terbatas pada komputer-komputer berspesifikasi rendah. Gagasan Cooley dan Tukey, dan perkembangan industri semikonduktor menjadikan jumlah N-titik DFT semisal 1024- titik, dapat dilakukan dalam beberapa detik saja pada komputer berspesifikasi rendah Lyons, Richard G. 1997. Understanding Digital Signal Processing. Prentice Hall PTR..

Meskipun telah banyak bermacam-macam algoritma FFT yang dikembangkan, algoritma FFT radix-2 merupakan proses yang sangat efisien untuk melakukan DFT yang memiliki kendala pada ukuran jumlah titik dipangkatkan dua. FFT radix-2 menghilangkan redundansi dan mengurangi jumlah operasi aritmatika yang  diperlukan. Sebuah DFT 8-titik, harus melakukan N2 atau 64 perkalian kompleks. Sedangkan FFT melakukan (N/2)log2N yang memberikan penurunan yang signifikan dari N2 perkalian kompleks. Ketika N = 512 maka DFT memerlukan 200 kali perkalian kompleks dari yang diperlukan oleh FFT.


Gambar Perbandingan jumlah perkalian kompleks DFT dengan FFT Lyons, Richard G. 1997. Understanding Digital Signal Processing. Prentice Hall PTR.

FFT beroperasi dimulai dengan menguraikan (dekomposisi) sinyal domain waktu titik N ke N sinyal domain waktu hingga masing-masing terdiri dari satu titik. Selanjutnya menghitung N frekuensi spektrum yang berkorespondensi dengan N sinyal domain waktu. Terakhir, spektrum N disintesis menjadi spektrum frekuensi tunggal.



Gambar Diagram Alir FFT Smith, Steven W. 1997. The Scientist and Engineer's Guide to Digital Signal Processing. (Online) http://www.dspguide.com (20 Februari 2013).


Dalam proses dekomposisi diperlukan tahapan Log2N. Sebagai contoh, sinyal 16 titik (24) memerlukan 4 tahapan, sinyal 512 titik (29) membutuhkan 9 tahap,  sinyal 4096 titik (212) membutuhkan 12 tahapan. Dalam Gambar1, sinyal 16 titik terurai melalui empat tahap yang terpisah. Tahap pertama memisahkan sinyal 16 titik menjadi dua sinyal masing-masing terdiri dari 8 titik. Tahap kedua menguraikan data menjadi empat sinyal terdiri dari 4 titik. Pola ini berlanjut sampai sinyal N terdiri dari satu   titik. Dekomposisi digunakan setiap kali sinyal dipecah menjadi dua, yaitu sinyal dipisahkan menjadi sampel genap dan sample ganjil.





Gambar1 Contoh dekomposisi sinyal domain waktu yang digunakan di FFT Smith, Steven W. 1997. The Scientist and Engineer's Guide to Digital Signal Processing. (Online) http://www.dspguide.com (20 Februari 2013).


Setelah dekomposisi, dilakukan Pengurutan Pembalikan Bit (Bit Reversal Sorting), yaitu menata ulang urutan sampel sinyal domain waktu N dengan menghitung dalam biner dengan bit membalik dari kiri ke kanan. Asumsi N adalah kelipatan dari 2, yaitu N = 2r untuk beberapa bilangan bulat r=1, 2, dst. Algoritma FFT memecah sampel menjadi dua bagian yaitu bagian genap dan bagian ganjil.

Tabel Pengurutan Pembalikan Bit


Persamaan 2.2 dibagi menjadi bagian ganjil dan bagian genap sebagai berikut:


Karena rumusan yang didapat panjang, sehingga digunakan notasi standar untuk menyederhanakannya. Didefenisikan W𝑒−𝑗2𝜋/𝑁  yang merepresentasikan nth root of unity. Persamaan 2.4 dapat ditulis:


Sintesis domain frekuensi membutuhkan tiga perulangan. Perulangan luar menjalankan tahapan Log2N (setiap tingkat mulai dari bawah dan bergerak ke atas).

Perulangan bagian tengah bergerak melalui masing-masing spektrum frekuensi individu dalam tahap sedang dikerjakan (masing-masing kotak pada setiap tingkat). Dalam pemrosesan sinyal digital dikenal istilah butterfly. Butterfly digunakan untuk menggambarkan peruraian (decimation) yang terjadi. Karena tampilannya yang bersayap maka disebut butterfly. Butterfly adalah elemen komputasi dasar FFT, mengubah dua poin kompleks menjadi dua poin kompleks lainnya. Ada dua jenis peruraian, peruraian dalam waktu (decimation in time-DIT) dan peruraian dalam frekuensi (decimation in frekuensi-DIF). Gambar dari butterfly dasar untuk kedua jenis peruraian tersebut dapat dilihat pada Gambar 3 dan Gambar 4



Gambar 3 FFT butterfly dasar untuk peruraian dalam waktu Lyons, Richard G. 1997. Understanding Digital Signal Processing. Prentice Hall PTR.





Gambar 4 FFT butterfly dasar untuk peruraian dalam frekuensi sintesis butterfly Lyons, Richard G. 1997. Understanding Digital Signal Processing. Prentice Hall PTR.



Perulangan paling dalam menggunakan butterfly untuk menghitung poin dalam setiap spektrum frekuensi (perulangan melalui sampel dalam setiap kotak). Gambar 5 menunjukkan implemetasi FFT dari empat spektrum dua titik dan dua spektrum empat titik. Gambar 5 terbentuk dari pola dasar pada Gambar 3 berulang-ulang.




Gambar 5 FFT sintesis butterfly Lyons, Richard G. 1997. Understanding Digital Signal Processing. Prentice Hall PTR.

Daftar Pustaka Makalah Transformasi Fourier 

Pengertian Transformasi Fourier Diskrit Perbandingan Fast Fourier Transform Rating: 4.5 Posted By: Rarang Tengah

0 comments:

Post a Comment