BAB 2 DASAR TEORI FFT-IFFT

BAB 2 DASAR TEORI FFT-IFFT

Pada Bab ini dibahas tentang hubungan antara Discrete Fourier Transform (DFT) dan algoritma Fast Fourier Transform (FFT), dan hubungan antara algoritma FFT dan IFFT. Dua tipe algoritma FFT dibahas yaitu Decimation in Frequency dan Decimation in Time. Kedua tipe algoritma ini dapat diimplementasikan kedalam beberapa algoritma FFT seperti Cooley-Tukey dan Sande-Tukey. Pembahasan berlanjut mengenai perbandingan algoritma radix yang umum digunakan juga dibahas yaitu algoritma Radix-2, Radix-4, dan Radix-8. Selain itu juga dibahas tetang konstanta twiddle factor dan bagaimana cara membangkitkannya. Pada bagian akhir dibahas tentang penggunaan algoritma FFT dan IFFT dalam sistem OFDM baik dalam sistem pengirim maupun penerima.

2.1 DFT dan FFT FFT adalah algoritma yang efisien untuk melakukan komputasi DFT. DFT sendiri adalah nama untuk transformasi matematis untuk suatu sinyal waktu diskrit, sedangkan FFT lebih merujuk kepada algoritma untuk melakukan komputasi tersebut. Algoritma FFT dan inverse-nya (IFFT), menfasilitasi proses transformasi yang cepat dan efisien antara domain frekuensi dan domain waktu dan sebaliknya. DFT untuk N-point sekuens data

0,1, . . ,

dengan

1 didefinisikan pada

persamaan (2.1).

(2.1) Dengan

0,1, … ,

1 dan

jang transformasi (N-point) dan indeks

. Nilai dan

main frekuensi.

8

sering pula disebut sebagai pan-

adalah indeks domain waktu dan do-

Desain dann Implementassi 2k Pipeline FFT-IFFT F Coore untuk DVB B-T | 9

Kebalikannnya, inversee DFT untuuk sekuens data

dengan

0,1, … ,

1

didefinisikkan pada perrsamaan (2.22). 1 Untuk

0 …, 0,1,

(2.2)

1.

Dari (2.1) dan (2.2) teerlihat bahw wa perbedaan n antara kom mputasi DFT T dan IDFT terle⁄ u hal, yaituu adanya fakktor skala 1⁄ tak pada dua nensial unttuk

pada IDF FT dan tandda pangkat ekspoe

. Karrena kemirippan ini, algo oritma dan arrsitektur darri FFT Core dapat

digunakann pula untuk menghitungg IFFT dengan dua modifikasi kecil sebagai berrikut, 1. Meembalik inpuut dan outpuut FFT Coree antara nilai real dan im majiner. 2. Meembagi outpput dari FFT T Core dengaan 1⁄ . Modifikasii ini ditunjuukkan oleh Gambar G 2-1. Dengan dem mikian sebuuah FFT Corre dapat digunaakan sebagaii FFT Core dan d IFFT Co ore[3].

Gambar 2--1 IFFT Core berbasis b FFT Core C

Persamaann (2.1) dan (2.2) ( merupakan kompu utasi yang sangat komppleks dan memerlukan impllementasi peerangkat kerras yang bessar. Komputtasi DFT dann IDFT mem merlukan

1 penjum mlahan dan

tasi untuk N-point DF FT adalah

mpleksitas ko ompu1 peerkalian. Sehingga kom h karena itu diperlukan algoritma khusus k . Oleh

untuk menngurangi kom mpleksitas perhitungan. p . Coley-Tukkey memberiikan solusi algora tima yang dapat menggurangi kom mpleksitas komputasi k m menjadi

deengan

mengeksplloitasi karakkteristik simeetri dari kom mputasi DFT T[4]. Algorittma Coley-T Tukey dan algorittma komputtasi DFT lainnya kemud dian disebutt dengan Fasst Fourier TransT form (FFT T) dan algooritma kompputasi IDFT T disebut deengan Inverrse Fast Fo ourier Transform m (IFFT).

Desain dan Implementasi 2k Pipeline FFT-IFFT Core untuk DVB-T | 10

Gambar 2-2 Perbandingan kompleksitas komputasi antara DFT dan FFT

2.2 Algoritma FFT Desain prosesor FFT, sangat tergantung kepada komputasi matematis yang digunakan pada algoritma yang dipilih. Pemilihan algoritma tepat akan mempengaruhi kecepatan komputasi, kompleksitas perangkat keras, dan konsumsi daya yang diperlukan.

2.2.1

Algoritma Cooley-Tukey

Algortima FFT didasarkan pada prinsip yang disebut dengan divide-and-conquer untuk mengurangi jumlah komputasi (penjumlahan atau perkalian) untuk mendapatkan hasil yang sama dengan DFT. Teknik ini secara rekursif membagi DFT yang besar menjadi beberapa komputasi DFT yang lebih kecil. Tiap-tiap DFT kemudian dikerjakan secara independen dan hasilnya digabungkan untuk mendapatkan DFT keseluruhan[5]. Cooley dan Tukey mendemonstrasikan keunggulan metode ini dengan menggunakan algoritma yang kemudian disebut dengan algoritma radix-2. Algoritma ini secara efektif membagi komputasi DFT menjadi 2 pada setiap tahap rekursi sehingga pada akhirnya didapatkan 2-point DFT. Karena panjang data harus dibagi menjadi dua pada setiap tahap rekursi, maka DFT awal harus merupakan bilangan pangkat dari dua. DFT dengan panjang bukan bilangan pangkat dua harus dilakukan penambahan dengan nilai nol (zero padding). Tipe algoritma seperti yang digunakan oleh Coley-Tukey disebut sebagai Decimation in Time (DIT). Hal ini karena algoritma ini menghitung setiap blok kecil DFT pada


domain waktu dan pada akhirnya akan didapatkan DFT utuh pada domain frekuensi. Algoritma ini memiliki persyaratan dalam implementasi ke perangkat keras yaitu input dari DIT memiliki indeks bit-reversed. Sebagai contoh untuk 8-point DFT, input data pertama adalah tetap indeks ke-0, tetapi input data kedua adalah indeks ke-4 karena bit-reversed dari indeks “001” adalah “100” dan seterusnya.

Gambar 2-3 Radix-2 butterfly untuk algoritma Cooley-Tukey

2.2.2

Algoritma Sande-Tukey

Input data bit-reversed tidak terlalu disukai untuk implementasi. Oleh karena itu, digunakan tipe algoritma lain yang disebut dengan Decimation in Frequency (DIF). Tipe algoritma ini merupakan kebalikan dari DIT karena ukuran komputasi DFT pada tahap berikutnya selalu lebih kecil dibanding tahapan sebelumnya. DIF mensyaratkan output dari FFT memiliki indeks bit-reversed sedangkan inputnya indeksnya tetap.

Gambar 2-4 Radix-2 butterfly untuk algoritma Sande-Tukey

Algoritma Sande-Tukey memiliki kompleksitas komputasi yang sama dengan ColeyTukey. Namun, algoritma ini dan DIF pada umumnya, lebih disukai daripada DIT untuk diimplementasikan ke perangkat keras. Struktur butterfly dari DIF yang melakukan komputasi perkalian dengan twiddle factor dan pemotongan bit (bit-truncation) setelah penjumlahan butterfly memberikan nilai SNR yang lebih baik dibanding DIT yang melakukan hal sebaliknya[6].


2.3 Algoritma Mode Decimation in Frequency 2.3.1

Algoritma Radix-2

Seperti telah dijelaskan sebelumnya, algoritma Sande-Tukey adalah algoritma FFT Radix-2 bertipe DIF. Algoritma Radix-2 membagi data menjadi dua sama besar. Setiap kombinasi data akan dieksekusi dengan operasi yang disebut dengan butterfly. Butterfly adalah unit terkecil FFT [7]. Gambar 2-3 dan Gambar 2-4 memperlihatkan satu unit butterfly Radix-2 bertipe DIT dan DIF. Seluruh komputasi FFT dapat ditunjukkan/digambarkan dengan menggambar unit radix secara repetitif untuk setiap output radix tahap sebelumnya. Pada algoritma Radix-2, yang terpisah

dan ,

⁄2. Maka apabila

⁄2. Demikian pula dengan

pada Gambar 2-4 merupakan data dengan indeks memiliki indeks dan

maka

memiliki indeks

, mereka juga memiliki indeks dengan

pola yang sama sehingga implementasi pada perangkat keras menjadi lebih sederhana. Pengalamantan data yang sama antara input dan output ini disebut dengan pola inplace addressing karena data output dapat menempati posisi yang sama dengan yang digunakan oleh input. Proses ini diulangi terus menerus hingga tahap terakhir. Gambar 2-5 menunjukkan contoh signal flowgraph dari 8-point DFT yang dikomputasi dengan menggunakan 3 tahap Radix-2 FFT. Tahap pertama membagi data menjadi 2 blok dengan panjang masing-masing 4. Tahap kedua membagi output dari tahap pertama menjadi 2 lagi dengan panjang 2 dan tahap terikhir merupakan satu unit Radix-2 FFT.

Gambar 2-5 Contoh signal flowgraph untuk 8-point DFT


Pada perkembangannya, disadari bahwa proses faktorisasi tidak harus dengan nilai 2, setiap DFT dapat pula difaktorisasi dengan nilai lain asalkan tetap memenuhi syarat bahwa perkalian seluruh nilai faktor adalah besar DFT itu sendiri. Misalnya, 64-point DFT dapat dipecah menjadi 6 tahap 2-point DFT atau 3 tahap 4-point DFT atau 2 tahap 8-point DFT. Bahkan beberapa kombinasi DFT dapat digunakan, misalnya menggunakan radix-2 diteruskan dengan radix-4 dan radix-8 untuk menyusun 64point DFT tersebut. Selain algoritma radix-2, terdapat dua tipe radix yang biasa digunakan yaitu radix-4 dan radix-8.

2.3.2

Algoritma Radix-4

Algoritma Radix-4 membagi data menjadi 4 blok data. Dengan demikian setiap tahap komputasi akan membagi tahap sebelumnya menjadi 4. Pada kenyataannya, Radix-4 merupakan dua tahap Radix-2 FFT untuk 4-point DFT. Oleh karena Radix-4 hanya merupakan generalisasi dari Radix-2, maka seluruh sifat dari Radix-2 juga dimiliki oleh Radix-4 termasuk struktur yang regular, in-place addressing, dan pipelining.

Gambar 2-6 Radix-4 node

Gambar 2-7 Signal flow graph Radix-4 butterfly

Keunggulan Radix-4 dibandingkan dengan Radix-2 adalah adanya trivial twiddle factor yang dapat dikeluarkan dari daftar multiplikasi twiddle factor. Trivial twiddle factor adalah nilai twiddle factor yang tidak memerlukan multiplikasi untuk diimplemen-


tasikan. Algoritma Radix-4 dapat mengeluarkan nilai twiddle untuk masing-masing bernilai – dan . Jika data kompleks maka yang perlu dilakukan hanya menjadikan nilai gai data imajiner sehingga didapatkan

yang

dikalikan dengan – , sebagai data real dan –

seba-

. Demikian pula dengan perkalian

dengan . Maka yang perlu dilakukan hanya menjadikan nilai imajiner dan nilai –

dan

sebagai nilai realnya sehingga didapatkan –

sebagai data . Dengan

demikian salah satu keuntungaan adalah, presisi dapat ditingkatkan dibanding perkalian dengan nilai – dan dengan nilai bit-precission. Radix-4 memerlukan 4 input pada setiap tahapnya, oleh karenanya, panjang FFT yang dikalkulasi haruslah merupakanbilangan pangkat dari 4. Maka terdapat beberapa nilai FFT yang dapat dikerjakan dengan Radix-2 namun tidak dapat dengan Radix-4. Salah satu metode untuk mengatasi hal ini adalah dengan menggabungkan komputasi Radix-4 dengan Radix-2 untuk menghasilkan FFT mixed-radix.

2.3.3

Algoritma Radix-8

Algoritma Radix-8 membagi data menjadi 8 blok data. Dengan demikian setiap tahap perhitungan akan membagi data tahap sebelumnya menjadi 8. Seperti halnya Radix-4, Radix-8 juga merupakan turunan dari Radix-2. Pada kenyatannya, gambar flowgraph Radix-8 merupakan 3 tahap Radix-2 FFT untuk 8-point DFT.

Gambar 2-8 Radix-8 node


Gambar 2-9 Signal flow graph Radix-8 butterfly

Algoritma Radix-8 menambahkan dua buah trivial twiddle factor yang dapat dikeluarkan dari daftar multiplikasi twiddle factor. Nilai trivial twiddle factor tersebut adalah 1

⁄√2 dan

1

⁄√2. Karena terdapat faktor pembagian dengan √2 maka

diperlukan unit scaling. Unit ini dapat diimplementasikan dengan menggunakan sirkuit shift-and-add nilai konstan yang tidak memerlukan kebutuhan perangkat keras yang tinggi. Selain itu nilai presisi untuk kedua twiddle factor ini dapat ditingkatkan dengan menambahkan level sirkuit shift-and-add.

2.4 Twiddle Factor Twiddle factor adalah konstanta trigonometri yang akan dikalikan dengan data pada algoritma FFT. Dari persamaan (2.1) konstanta twiddle factor adalah

, sehingga

2048-point FFT memerlukan 2048 nilai konstanta kompleks twiddle factor. Nilai konstanta ini dapat diperoleh dengan melakukan sampling satu siklus nilai cosinus dan nilai sinus untuk twiddle factor real dan twiddle factor imajiner seperti yang ditunjukkan oleh (2.3).

(2.3) cos

2 2048

sin

2 2048


Untuk menyimpan seluruh nilai twiddle factor ini memerlukan ROM yang besar. Oleh karena itu tidak seluruh nilai twiddle factor disimpan. Gambar 2-10 menunjukkan bahwa hanya 1⁄8 nilai twiddle factor awal saja yang perlu disimpan (dari indeks 0 sampai dengan

256), sedangkan nilai twiddle factor lainnya dapat dihasil-

kan dari nilai ini[8].

Gambar 2-10 Seperdelapan siklus nilai cosinus (kiri) dan sinus (kanan)

2.5 FFT-IFFT dalam OFDM Ortogonal Frequency Division Multiplexing (OFDM) merupakan teknik multiplexing dengan cara membagi sebuah kanal lebar menjadi beberapa kanal sempit, yang dapat mengirimkan informasi secara parallel pada waktu yang bersamaan. Keunggulan OFDM dibandingkan dengan teknik modulasi lainnya adalah kemampuannya untuk mengatasi multipath. Pengiriman data secara parallel memungkinkan tiap bit dikirimkan dengan rate yang lebih kecil. Rate yang lebih kecil berarti perioda simbol yang lebih panjang. Jika delay spread yang terjadi akibat multipath cukup kecil jika dibandingkan dengan perioda simbol, maka efek dari multipath tidak akan terlalu signifikan lagi[9]. Perbedaan antara OFDM dengan FDM (Frequency Division Multiplexing) adalah bentuk spektrumnya yang berupa sin ⁄ diatur sedemikian rupa sehingga sinyalsinyal carrier yang ada secara matematis bersifat ortogonal sehingga spektrumspektrum dari subcarrier dimungkinkan tumpang tindih tanpa saling mengganggu.

Desain dan Implementasi I 2k Pipeline FFT-IFFT F Corre untuk DVB-T - | 17

Gambar 2-11 2 Spektrum m Sinyal OFDM M[9]

Suatu sinyyal disebut orrtogonal jikaa memenuhii persamaann (2.4). , jika p q 0, jika p q Dengan dan

merupakaan komplekss konjugat dari d

,

(2.4)

adalah konstanta bukan n nol,

adallah periode simbol s OFD DM.

DFT memiliki sifat orttogonal. Oleeh karena itu u OFDM meenggunakan IDFT (dalaam hal ma IFFT) unntuk membaangkitkan sin nyal ortogonnal yang akaan ditransmissikan, ini algoritm dan algorittma FFT unttuk mengem mbalikan tran nsformasi kee domain freekuensi, untu uk didemodulassi kembali. Dengan demikian, seccara sederhaana OFDM modulator dapat diimplemeentasikan deengan mengggunakan saatu IFFT corre dan moddulator baseeband. Sedangkann OFDM dem modulator diimplement d tasikan denggan satu FFT T core dan demod dulator basseband.


Gambar 2-12 Sistem OFDM berbasis IFFT dan FFT

Proses pembangkitan sinyal OFDM pada umumnya menggunakan IFFT dengan panjang yang lebih besar dibanding jumlah subcarrier yang digunakan. Sebagai contoh, untuk modulasi OFDM yang digunakan pada DVB-T, dari 2048 subcarrier yang mungkin digunakan hanya 1705 subcarrier yang dipakai, sedangkan sisanya diberi nilai nol (zero padding). Hal ini bermanfaat untuk menghindari terjadinya efek aliasing pada saat sinyal OFDM diubah ke bentuk analog dengan DAC. Selain itu, input 0 juga diberikan pada masukan dari IFFT pada frekuensi 0, yang berguna untuk menghilangkan komponen DC pada sinyal OFDM. Input IFFT berasal dari blok frame adaptation (Gambar 1-1). Blok frame adaptation menerima data dari modulator (QPSK, 16-QAM, atau 64-QAM) dan menambahkan data pilot dan TPS carrier untuk dibentuk menjadi simbol OFDM. Masing-masing modulator memiliki range output yang berbeda-beda yang ditunjukkan pada Tabel 2-1. Dari tabel tersebut, 64-QAM memiliki range yang terbesar. Untuk mengkodekannya dalam format fixed point maka paling tidak diperlukan satu buah sign bit, satu buah integer bit, dan bit sisanya untuk mengkodekan nilai pecahan. Dari persamaan (2.2), diperoleh bahwa range output dari IFFT akan sama dengan range inputnya sehingga sistem pengkodean yang sama dapat diterapkan pada output IFFT.


Tabel 2-1 Nilai output dari tiap tipe modulasi

Modulasi MAX

MIN

Norm.

Range Output

QPSK

1

-1

√2

0.707 s.d -0.707

16-QAM

3

-3

√10

0.949 s.d -0.949

64-QAM

7

-7

√42

1.080 s.d -1.080

Pada kenyatannya, untuk input berupa simbol OFDM, apabila IFFT dilakukan dengan menggunakan faktor normalisasi 1⁄

seperti yang ditunjukkan dengan persamaan

(2.2) maka output akan memiliki amplitudo yang sangat kecil. Sehingga beberapa faktor normalisasi lain diperkenalkan seperti menggunakan faktor normalisasi gain tetap 1⁄√ , automatic data scaling[10][11], dan sebagainya. Implikasinya, IFFT yang terjadi menjadi tidak standar lagi. Untuk mengurangi kompleksitas rancangan dan tetap menjaga standarisasi komputasi, maka 2k FFT-IFFT Core yang dirancang akan menggunakan sistem pengaturan gain manual. Faktor normalisasi dapat diatur secara manual dengan nilai standar adalah gain standar (1⁄ ). Input FFT berasal dari data hasil digitalisasi ADC. Data ini terlebih dahulu harus melalui tahap Automatic Gain Control untuk menghilangkan penguatan yang diperoleh sinyal dari kanal. Dengan demikian sinyal yang diterima oleh FFT dianggap tidak mendapat penguatan oleh kanal. Output dari FFT akan di-demodulasi menggunakan demodulator yang sesuai dengan modulator pengirim. Oleh karena itu sinyal output FFT akan memiliki range yang sama dengan input IFFT. Sehingga, lebar bit dan pengkodean bit yang sama dapat dipergunakan. Pengaturan gain yang sama dengan IFFT juga harus digunakan agar simbol OFDM dapat ditransformasi dengan sempurna. Karena FFT dan IFFT adalah sistem linier, maka penguatan di satu domain dapat dihilangkan dengan membagi output transformasi dengan nilai yang sama. Dengan demikian, apabila pada output IFFT dilakukan penguatan sebesar , maka output dari FFT harus dikalikan dengan 1⁄ .

BAB 2 DASAR TEORI FFT-IFFT

Recommend Documents