Resume BAB 3 Transformasi Diskrit
3. Transformasi Diskrit
3.1 Pendahuluan
Transformasi
data diskrit antara waktu dan frekuensi domain dijelaskan dalam bab ini.
Tegangan terhadap representasi waktu menjadi magnet versus frekuensi dan
representasi fase versus frekuensi, dan viceversa. Kedua domain memberikan
informasi pelengkap tentang data yang sama. Dengan demikian kadang-kadang
mungkin lebih bermakna dalam aplikasi untuk memeriksa magnitudo versus
frekuensi plot untuk perubahan dalam amplitudo tegangan pada frekuensi
tertentu. Transformasi diskrit memiliki keuntungan dalam mereduksi data karena
data yang tidak penting diabaikan sehingga meningkatkan penafsiran.
Transformasi diskrit digunakan dalam kompresi data sinyal suara dan video untuk
mengurangi bandwidth saat transmisi. Transformasi diskrit juga digunakan dalam
pengolahan gambar agar mengurangi set fitur untuk pengenalan pola, juga
digunakan sebagai alat matematika untuk mempercepat perhitungan dalam aplikasi
pemrosesan sinyal. Discrete Fourier Transform (DFT) dan Fast Fourier Transform
(FFT) adalah yang paling terkenal dan paling penting. Alasannya adalah DFT dan
FFT mengizinkan representasi yang memadai dalam domain frekuensi untuk semua
tetapi panjang datanya terpendek (1<s).
3.43
Dalam mengeksploitasi redundansi komputasi yang
diungkapkan oleh Persamaan 2.46 urutan data dibagi menjadi dua urutan yang
sama, salah satu data bernomor genap, dan salah satu data bernomor ganjil.
Untuk urutan yang sama panjangnya, semuanya harus berisi data genap. Jika
urutan awal terdiri dari jumlah data ganjil, maka nol tambahan harus
ditambahkan untuk merender jumlah data. Hal ini memungkinkan DFT, X1 (k),
ditulis dalam dua DFT, X11 (k) dan Xu (k), yang merupakan DFfs dari data yang
bernilai tinggi dan data ganjil bernilai masing-masing (lihat Tabel). 2.1).
Jadi titik-N DFT diubah menjadi dua DFTs masing-masing N / 2 poin. Proses ini
kemudian diulang sampai X 1 (k) didekomposisi menjadi N / 2 DFfs, masing-masing
dua poin, keduanya merupakan data awal. Dengan demikian, dalam prakteknya, data
awal diurutkan ulang dan N / 2 DFT dua titik dihitung dengan mengambil data
secara berpasangan. Output DFT ini cocok digabungkan dalam empat untuk menyediakan
N / 4 DFT empat titik yang dihitung dan digabungkan secara tepat untuk
menghasilkan N / 8 DFT delapan titik yang dihitung, dan seterusnya sampai titik
N titik terakhir DFT, X1 (k ), diperoleh. Pada setiap tahap faktor-faktor umum
yang merupakan kekuatan dari W N dimasukkan untuk mengurangi jumlah perhitungan
yang rumit. Prosedur ini dibenarkan sebagai berikut. Sufiks, n, dalam Persamaan
2.43 memanjang dari n = 0 ke n = N - 1, sesuai dengan nilai data x0, x1, x2,
x3, ..., xN-l · Urutan bernomor genap adalah x0 , x2, x4, ..., xN_2, dan urutan
bernomor ganjil adalah Xi. x3, ..., XN-l · Kedua urutan mengandung N / 2 poin.
Istilah dalam urutan genap dapat ditetapkan Xzn dengan n = 0 hingga n = N / 2 -
1 sementara yang dalam urutan ganjil menjadi x2n + l · Kemudian Persamaan 3.43
dapat ditulis ulang
Tabel
3.1 Structure of an 8-point FFT.
Using
Equation 3.46b gives W~k = W:Z,)2 so Equation 3.47 becomes
Equation
3.48 may be written
Pada perbandingan Persamaan 3.49 dengan Persamaan
3.43, terlihat bahwa X 11 (k) memang DFT dari urutan genap, sedangkan X n (k)
adalah dari urutan yang aneh. Oleh karena itu, sebagaimana dinyatakan
sebelumnya, DFT, X 1 (k), dapat dinyatakan dalam dua D F'Is: X 11 (k) dan X iz
(k). Faktor Wt; 2 terjadi di kedua X 11 (k) dan X 12 (k) dan hanya perlu sekali
perhitungan. Tabel 2.1 mengilustrasikan proses untuk DFT 8 titik. Baris 1
memberikan data sementara garis 2 memberikan ekspresi untuk DFT data dalam hal DFfs
dari genap dan ganjil, X11 (k) dan X12 (k) masing-masing. Baris 3 menunjukkan
data yang dipesan ulang dari mana X11 (k) dan Xu (k) berasal. Baris 4
memberikan DFfs dari urutan data baris 3 dalam hal DFfs dari urutan genap dan
ganjil, X21 (k), X22 (k), X23 (k) dan X24 (k). Urutan ini ditunjukkan pada
baris 5, dan terlihat sebagai urutan 2-titik tertinggi, yang DFfsnya adalah X21
(k), X22 (k), X23 (k) dan X24 (k) dan dinyatakan dalam bentuk data sejalan 6.
Dengan demikian, DFT 8-titik tunggal telah diuraikan menjadi empat DFf 2-titik,
yang masing-masing menghasilkan dua nilai, misalnya X21 (0) dan X21 (1) dalam
kasus X21 (k). Proses ini melibatkan dua dekomposisi, dan bobotnya dikuadratkan
pada setiap langkah. Mempertimbangkan garis
6
terlihat bahwa :
dari mana kita amati bahwa nilai-nilai dengan k = 1
hanya berbeda dengan tanda dari mereka dengan k = 0. Titik ini ditekankan jika
X 11 (k) (k = 0, 1, 2, 3) dianggap. Sekarang,
Pemeriksaan persamaan ini menunjukkan bagaimana DFTs X
11 (k) terkait dengan DFTs dari data bernomor genap dan bernomor ganjil, dan
bahwa X 11 (0) dan X11 (2) diberikan oleh ekspresi dengan istilah umum yang
berbeda hanya dalam satu tandanya. Hal yang sama berlaku untuk X11 (1) dan X11
(3). Persamaan seperti ini dikenal sebagai persamaan rekomposisi karena dimulai
dari pasangan data dan membentuk X21 (k), X22 (k), X23 (k) dan X24 (k)
memungkinkan X11 (k) dan Xn (k) dapat ditemukan, dan karenanya X 1 (k). Jumlah
penambahan kompleks dan perkalian yang terlibat dikurangi dengan cara ini karena
(i)
Persamaan recomposition dinyatakan dalam hal kekuatan
dari faktor WN berulang, (ii) penggunaan juga terbuat dari hubungan dari tipe
X21 (2) = X21 (0) dan X21 (3) = X21 (1), dan (iii) ) Kehadiran hanya tanda
perbedaan dalam pasangan ekspresi dieksploitasi. Algoritma ini dikenal sebagai
algoritma Cooley-Tukey.
3.5.1 The Butterfly
Persamaan 3.58 dapat
direpresentasikan secara diagram dengan mengeksploitasi symmetry yang berpusat
pada perbedaan tanda dan mengambil persamaan secara berpasangan. Jadi dari
Persamaan 3.58a dan 3.58b output dari rekomposisi adalah X 11 (0) dan X 11 (2)
terbentuk dari input X 21 (0) dan X 22 (0). Ini diilustrasikan pada Gambar 3.4
(a). Input berada di sisi kiri dari salib, output ke kanan. Gambar 3.4 (b)
menunjukkan bagaimana output X 11 (1) dan X 11 (3) diperoleh secara diagram.
Dengan tumpang tindih Angka 3,4 (a) dan 3,4 (b), sebuah komposit dialog
diperoleh di mana output DFTs diatur dalam urutan peningkatan k. Ini
ditunjukkan pada Gambar 3.4 (c). Struktur Gambar 3.4 (a) atau 3.4 (b) disebut
sebagai 'kupu-kupu', yang mengingatkan pada representasi simbolis serangga.
Seluruh 8-titik FFT dapat digambarkan dengan cara ini seperti pada Gambar 3.5
Gambar 3.5 kupu-kupu FFf untuk 8-point
DFf: BW3, pemisahan memori antara titik-titik yang berkontribusi terhadap
kupu-kupu paling atas dari tahap 3; BS, pemisahan memori antara titik-titik
bawah kupu-kupu di tahap 2 dengan faktor pembobotan yang sama
Contoh 3.5
menjadi instruktif untuk mendapatkan DFT dari
urutan {1, 0, 0, 1}, sebelumnya dievaluasi dalam Bagian 3.2, dengan menggunakan
algoritma FFT desimidasi-in-time. Ini adalah DFT empat titik dengan x0 = 1, x1
= 0, x2 = 0, x3 = l, dan X1 (k) = X11 (k) + W ~ X12 (k), k = 0, 1, 2, 3. Urutan
urutan ulang adalah x0, X1, X2. X3.
Kita sekarang dapat memanfaatkan sudut
kiri atas Gambar 2.5 untuk menyusun DFT. Poin x0, x4, x2, x6 diganti dengan x0,
x2, xi, x3, dan nilai DFT yang diperlukan adalah X 11 (0), X 11 (1), X 11 (2)
dan X 11 (3). Karena itu,
Nilai-nilai ini sama dengan yang diperoleh pada Bagian
3.2, tetapi lebih mudah diperoleh dengan menggunakan algoritma FFT. Kesimpulannya
penghitungan penghematan meningkat seiring dengan meningkatnya jumlah data.
3.5.2 Pengembangan Algoritma
Untuk menjalankan FFT,
program harus mengatur ulang data input dan melakukan perhitungan kupu-kupu.
3.5.2.1 Memesan ulang data input
Meskipun pada awalnya
mungkin tampak bahwa tidak ada cara yang jelas untuk memprogram pemesanan ulang
data input. Rahasianya dalam istilah biner. Tabel 3.2 menunjukkan di kolom
pertama urutan yang diperlukan dari data untuk input ke jaringan kupu-kupu
seperti yang diberikan oleh Gambar 2.5. Setiap nilai diasumsikan disimpan dalam
alamat memori biner. Alamat-alamat ini diberikan di kolom kedua. Kolom ketiga
menunjukkan alamat-alamat memori ini sedikit terbalik. Jika alamat-alamat yang
dibalik-bit ini diambil agar sesuai dengan alamat-alamat biner dari urutan data
asli, dimulai dengan x (O) pada 000, maka nilai-nilai data yang bersangkutan
diberikan dalam kolom keempat, yang terlihat mengandung urutan data asli . Jadi
alamat dari data yang dipesan ulang terlihat menjadi alamat bit-terbalik dari
urutan data asli. Programnya adalah
Table
3.2 Sequencer e-orderingb y bit reversal.
Diperlukan untuk mengkonversi nomor titik data (0 ke N
- 1) ke biner, untuk menggandakan nomor-nomor biner ini dan untuk
mengkonversikannya kembali ke nomor-nomor penyangkalan yang merupakan alamat
dari data yang dipesan ulang. Konversi ke biner dapat dicapai dengan membagi
secara berulang oleh dua ketika sisanya memberikan digit urutan terbalik dari
bilangan biner yang sesuai yang merupakan syarat biner yang diperlukan dari
urutan re-ordered. Residu ini dapat diperoleh dengan menggunakan fungsi MOD
yang dapat diperoleh dalam bahasa tingkat tinggi, misalnya MOD (K, 2)
memberikan sisanya pada membagi nilai denary K oleh 2. Bagian bilangan bulat
dari K / 2 ditemukan dengan melakukan pembagian bilangan bulat . Sisa digit
ditemukan dengan mengulangi proses ini sampai log, N divisi telah dibuat. Hal
ini karena data terdiri dari zm = N titik data sehingga setiap alamat
membutuhkan digit m dan dapat dibagi dengan dua kali m, di mana m = log, N. Bit
ke-I dari alamat baru adalah koefisien biner 2m-lI sehingga alamat baru (NADDR)
dapat ditemukan menggunakan loop DO untuk nilai tertentu K (K = IADDR) yang
berjalan dari 1 = 0 ke l = m-1 dan yang mengambil sisa (RMNDR) dari bilangan
bulat berturut-turut yang diperoleh setelah membagi K = IADDR dengan dua. Kode
pseudo yang diperlukan untuk ini adalah
DO
FOR 1=0 TO m-1
RMNDR:=
MOD(IADDR,2)
NADDR:=NADDR+RMNDRx2m-1-1
IADDR:=IADDR/2
END
DO
Loop DO ini harus bersarang di dalam loop
DO lain, yang berfungsi untuk mengekstrak data asli dari array kompleks DATA
(K), K = O ke N-1 sebagai nomor titik datum yang juga merupakan nomor elemen
kompleks dalam array dan sesuai dengan alamat awal datum, dan untuk memasukkan
data yang diurutkan ulang ke dalam array NEWDATA (NADDR). Data dalam NEWDATA
sekarang dalam urutan yang benar untuk perhitungan kupu-kupu. Pseudo-code
lengkap adalah
DO
FOR K=O TO N-1
NADDR:=O
IADDR:=K
DO FOR 1=0 TO m-1
RMNDR:=
MOD(IADDR,2)
NADDR:=NADDR+RMNDx2m-1-1
IADDR:=IADDR/2
END
DO
NEWDATA
(NADDR): =DAT A(K)
END
DO
3.5.2.2 Perhitungan kupu-kupu
Tiga tahap perhitungan :
(1) menghitung faktor pembobotan, Wrn = e-i (2rr
/ N) R;
(2) mengevaluasi kupu-kupu dalam satu tahap (lihat
Gambar 3.5 untuk definisi tahap);
(3) menghitung semua tahapan.
Prosedur yang efektif adalah menghitung faktor
pembobotan yang terlibat dalam suatu tahap, dan untuk masing-masing
mengevaluasi semua kupu-kupu di atas panggung dengan faktor itu. Setelah
mengevaluasi semua kupu-kupu di tahap itu, prosedur ini diulang untuk semua
tahap. Jadi, mengacu pada tahap 2 pada Gambar 2.5, W ~ dan dua kupu-kupu yang
melibatkan W ~ dihitung. Kemudian W ~ dan dua kupu-kupu yang terlibat dihitung.
Prosedur ini dilakukan untuk masing-masing dari tiga tahap pada gilirannya
dimulai dengan tahap 1 dan data yang dipesan ulang. Untuk mencapai perhitungan
FFT menggunakan program yang relatif singkat, sejumlah properti dari algoritma
diperlukan. Biarkan lebar kupu-kupu BWIDTH mewakili pemisahan dalam memori poin
yang berkontribusi pada kupu-kupu. Untuk kupu-kupu teratas pada tahap 3 pada
Gambar 2.5 ini adalah BW3. Jaraknya empat titik. Pertimbangan kupu-kupu di
tahap lain mengarah pada kesimpulan bahwa secara umum
BWIDTH=2s-1 ( 3.59)
dimana S adalah nomor panggung. Biarkan BSEP,
pemisahan kupu-kupu, menjadi perpisahan dalam memori titik-titik seperti di
antara kupu-kupu terdekat dalam tahap kupu-kupu yang memiliki faktor pembobotan
yang sama. Untuk tahap 2 pada Gambar 2.5, BS2 mewakili BSEP untuk kupu-kupu
dengan faktor pembobot W ~. Inspeksi gambar menunjukkan bahwa untuk tahap Sth
BSEP=S2 (3.60)
Akhirnya
untuk N-point FFT, eksponen faktor pembobot berubah
p = N/2s (3.61)
di
tahap Sth. Ini dapat dilihat pada Gambar 3.5. Misalnya, dalam tahap 2, S = 2, P
= 8/22 = 2 dan faktor pembobot adalah W08 dan W28 Setiap kupu-kupu dapat
dihitung sebagai
XNEW(TOP)
= XOLD(TOP) + W~ x XOLD(BOTTOM) XNEW(BOTTOM)=XOLD(TOP)-W~xXOLD(BOTTOM) (3.62)
TEMP=WRNxX(BOTTOM)
di
mana X (BOTTOM) mengacu pada output kupu-kupu pada tahap sebelumnya, X(BOTTOM)=X(TOP)-
TEMP
di
mana X (BAWAH) sekarang mengacu pada output kupu-kupu yang diperlukan, X (TOP)
mengacu pada nilai sebelumnya, dan
X(TOP)
=X(TOP)+ TEMP
di
mana nilai sisi kiri baru X (TOP) adalah output kupu-kupu yang diperlukan.
Dengan semua pengetahuan ini tersedia sekarang mungkin untuk menulis kode
pseudo-untuk FFT seperti yang ditunjukkan di bawah ini:
Tabel 3.3 Penghematan dalam perkalian dan penambahan
yang rumit ketika FFr digunakan selain dari DFT.
3.5.3 Keuntungan komputasional dari FFT
Keuntungan komputasional dari FFT dapat diilustrasikan
dengan mempertimbangkan terlebih dahulu algoritma FFT pada Gambar 3.5. Gambar
ini menunjukkan bahwa titik N-FFT berisi N / 2 kupu-kupu per tahap dan tahap
log2 N, yang berisi total (N / 2) log-N kupu-kupu. Gambar 3.4 (a) menunjukkan
bahwa setiap kupu-kupu melibatkan satu perkalian rumit dari bentuk W ~ X; j
(k). Oleh karena itu FFT melibatkan (N / 2) log2 N perkalian rumit dibandingkan
dengan N2 dalam kasus DFT, seperti yang ditunjukkan pada Bagian 3.4. Dengan
demikian penghematan komputasi dalam perkalian rumit adalah N2 - (N / 2) log,
N. Setiap kupu-kupu mengandung dua kondisi kompleks sehingga FFT membutuhkan
penambahan N log2 N kompleks dibandingkan dengan N (N-1) untuk OFT. Jadi
penghematan dalam penambahan kompleks adalah N (N - 1) -Nlog2 N. Penghematan
ini diilustrasikan pada Tabel 3.3. Untuk DFT 1024 titik yang khas, terlihat
bahwa waktu komputasi akan berkurang dua kali lipat jika algoritma FFT
digunakan.
3,6 Inverse Fast Fourier Transform
Algoritma FFT untuk menentukan inverse fast Fourier
transform (IFFT) dapat diperoleh dari algoritma FFT. Penggunaannya terletak
pada transformasi spektra ke bentuk gelombang yang sesuai dan dalam memeriksa
bahwa FFT telah dihitung dengan benar dengan menggunakan algoritma yang pada
dasarnya sama untuk mendapatkan data asli. Untuk melihat bagaimana IFFT
diturunkan, lakukan pergantian berikut dalam Persamaan 3.20. Jumlahkan variabel
A. daripada n, biarkan variabel k menjadi µ, atur Q = 21T / NT sehingga
eksponen e menjadi -jk (21T / N) A .. Sekali lagi menggunakan notasi x (AT) = x
(A.) dan seterusnya, Persamaan 3.20 kemudian menjadi
(3.64)
Sekarang buat substitusi serupa dalam Persamaan 3.23,
yaitu letakkan k = A., dan n = µ sehingga Persamaan 3.23 menjadi
(3.65)
Dalam dua persamaan terakhir X (µ), X (A.), X (A.) Dan
x (µ) adalah semua elemen dari array ekidimensi X dan x, dan sehingga dapat
dilihat bahwa IFFT, x (µ ), berbeda dari FFT, X (µ), hanya dalam faktor l / N
dan tanda eksponen. Jadi dengan modifikasi kecil, FFT dapat digunakan untuk
menghitung IFFT. Kedua transformasi dapat dimasukkan dalam algoritma yang sama
dengan membuat modifikasi berikut pada pseudo-code sebelumnya;
line
5 K:=1 FOR FFT,
K:=-1 FOR IFFT
line
80 THETA:=Kx2xPlxR/N
line
145 IF K=-1 DO
line
146 X(BOTVAL):=X(BOTVAL)/N
line
147 X(TOPVAL): =
X(TOPVAL)/N
line
148 END DO
PENYUSUN :
 |
| Murni Sri (3C/12) |
 |
| Ainun Nisyah(3C/02) |
 |
| Tony Agung W (3C//21) |