Background

Cooley dan Tukey

Cooley dan Tukey
Abstrak — Transformasi Fourier Cepat, dalam bahasa Inggris dikenal dengan Fast Fourier Transform, adalah suatu algoritma yang banyak digunakan untuk menghitung Transformasi Fourier Diskrit atau Discrete Fourier Transform dalam bahasa Inggris. Adapun kelebihan dari Transformasi Fourier Cepat adalah tingkat kompleksitas yang lebih rendah sehingga lebih cepat dan mangkus. Nilai tambah ini sangat berguna karena Transformasi Fourier Diskrit banyak diaplikasikan pada berbagai bidang khususnya pengolahan sinyal. 
Kata Kunci — Transformasi Fourier Cepat, Transformasi Fourier Diskrit, kompleksitas, pengolahan sinyal.   
Transformasi Fourier Diskrit merupakan bagian dari Transformasi Fourier yang digunakan dalam analisis Fourier. Dalam analisis Fourier dipelajari bagaimana cara merepresentasikan sevuah fungsi dengan penjumlahan beberapa fungsi trionometri yang lebih sederhana.  Analisis Fourier dinamakan sesuai dengan penemunya yaitu Joseph Fourier (1768-1830), seorang matematikawan dan fisikawan berkebangsaan Prancis. Beliau menunjukkan bahwa dengan mengubah sebuah fungsi menjadi deret trigonometri akan mempermudah pembelajaran tentang propagasi panas. 
Dalam bidang matematika, Transformasi Fourier digunakan untuk menguraikan sebuah sinyal menjadi frekuensinya. Dengan kata lain, Transformasi Fourier mengubah suatu fungsi ke daam bentuk lain. Pada Transformasi Fourier Diskrit, masukan fungsi harus dalam bentuk diskrit. Masukan Transformasi Fourier Diskrit adalah urutan terbatas bilangan riil ataupun bilangan kompleks. Hal ini menyebabkan Transformasi Fourier Diskrit ideal untuk memproses informasi di dalam komputer.  
Dalam perkembangannya, para peneliti terus berupaya mengembangkan suatu algoritma yang lebih cepat dan mangkus. Pada tahun 1965, J. W. Cooley dan John Tukey mengenalkan sebuah metode baru yang lebih cepat dan mangkus dalam memproses Transformasi Fourier Diskrit.

Algoritma yang diberi nama algoritma Cooley-Tukey ini sebenarnya telah ditemukan oleh Carl Friedrich Gauss pada sekitar tahun 1805. Karena lebih cepat dalam proses perhitungan, metode ini disebut dengan nama Transformasi Fourier Cepat.  
Dalam penggunaan sehari-hari, istilah Transformasi Fourier Cepat dan Transformasi Fourier Diskrit sering dipertukarkan. Padahal keduanya memiliki perbedaan yang jelas, yakni Transformasi Fourier Diskrit merujuk pada transformasi matematik bebas sedangkan Transformasi Fourier Cepat merujuk pada algoritma mangkus yang digunakan untuk menghitung Transformasi Fourier Diskrit. Hal demikian terjadi karena pada umumnya Transformasi Fourier Cepat digunakan untuk menghitung Transformasi Fourier Diskrit. 
Selain algoritma Cooley-Tukey, ada beberapa algoritma lain yang juga ditujukan untuk menghitung Transformasi Fourier Diskrit dengan lebih cepat dan mangkus. Beberapa diantaranya yaitu algoritma faktor prima, algoritma Radix terpisah, algoritma Bruun, algoritma Rader, dan algoritma Bluestein. Sampai dengan waktu pada saat makalah ini dibuat, algoritma Cooley- Tukey merupakan bentuk Transformasi Fourier Cepat yang paling populer digunakan. 
Penemuan Transformasi Fourier Cepat membawa dampak besar pada sejarah ilmu pengetahuan. Transformasi dapat menghitung deret Fourier dengan kecepatan  dibandingkan dengan Transformasi Fourier Diskrit biasa. Untuk data dengan jumlah ribuan atau bahkan jutaan, penggunaan Transformasi Fourier Cepat dapat mengurangi waktu komputasi hingga beberapa kali lipat. Peningkatan besar ini berperan penting pada berbagai macam aplikasi, contohnya pemrosesan sinyal digital, penyelesaian persamaan diferensial, dan perkalian bilangan bulat besar.

            TRANSFORMASI FOURIER DISKRIT 
Menurut Buku “Understanding Digital Signal Processing, Second Edition” karangan Richard G. Lyons. Transformasi Fourier Diskrit adalah prosedur yang kuat yang digunakan dalam pemrosesan sinyal digital dan filterisasi digital.  Transformasi Fourier Diskrit menungkinkan seseorang untuk menganalisa, memanipulasi dan mensintesis sinyal yang tidak mungkin dapat dilakukan dalam pemrosesan sinyal analog. Sedangkan menurut buku “Handbook of Digital Signal Processing Engineering Applications”, Transformasi Fourier Diskrit  merupakan gambaran karakteristik spektrum periodik dari suatu sampel data.  Transformasi Fourier Diskrit  memiliki spectrum garis yang mewakili periode sekuensial N.  Adanya istilah “discrete fourier transform” karena Transformasi Fourier Diskrit  memberikan gambaran deret fourier untuk sekuens terbatas. 

TRANSFORMASI FOURIER CEPAT 
Ada beberapa macam algoritma yang tergolong ke dalam Transformasi Fourier Cepat. Namun dalam makalah ini hanya akan membahas tiga algoritma saja. 
a. Algoritma Cooley-Tukey 
Algoritma Cooley Tukey adalah salah satu dari sekian algoritma yang digunakan untuk menghitung Transformasi Fourier Diskrit. Algoritma ini dipopulerkan oleh J. W. Cooley dan John Tukey pada tahun 1965. Sebenarnya algoritma ini pertama kali ditemukan oleh Carl Friedrich Gauss pada tahun 1805. Hanya saja ia tidak sampai pada pembahasan waktu perhitungan asimptotik. Sampai dengan waktu saat makalah ini dibuat, algoritma ini merupakan algoritma yang paling umum digunakan.  
Ide dari Transformasi Fourier Cepat adalah mengubah suatu bentuk Transformasi Fourier Diskrit dengan panjang N  menjadi bentuk penjumlahan dari dua buah bentuk Transformasi Fourier Diskrit dengan panjang masing-masing N/2, satu bagian terdiri dari elemen bernomor ganjil sementara yang lain genap.
b.  Algoritma Rader 
Algoritma Rader, ditemukan pada tahun 1968, adalah salah satu jenis Transformasi Fourier Cepat untuk menghitung transformasi Fourier Diskrit berukuran bilangan prima dengan mengekspresikan kembali Transformasi Fourier Diskrit sebagai sebuah siklus konvolusi. Untuk suatu kasus yang sama, algoritma Cooley-Tukey jauh lebih sederhana dan lebih praktis dalam memecahkan suatu masalah. Oleh karena itu, algoritma Rader biasanya hanya digunakan untuk kasus dasar dari dekomposisi rekursif Cooley-Tukey  dari Transformasi Fourier Diskrit.

c. Algoritma Bluestein 
Algoritma Bluestein, ditemukan pada tahun 1968, adalah salah satu bentuk Transformasi Fourier Cepat untuk menghitung Transformasi Fourier Diskrit dengan ukuran bebas dengan cara mengubah bentuk Transformasi Fourier Diskrit ke dalam bentuk konvolusi.
Read More 0 komentar