Laporan Praktikum Algoritma FFT Cooley-Tukey
Artikel berikut ini adalah percobaan menerapkan Algoritma Cooley-Tukey untuk menampilkan amplitudo dan frekuensi pada data accelerometer MPU6050 yang terpasang pada mikrokontroler Wemos D1 Mini.
Algoritma Cooley-Tukey adalah algoritma yang paling terkenal dan banyak digunakan untuk menghitung Fast Fourier Transform (FFT). FFT adalah yang dianggap paling efisien untuk menghitung Discrete Fourier Transform (DFT).
DFT adalah alat fundamental dalam pemrosesan sinyal dan analisis frekuensi, memungkinkan transformasi sinyal dari ranah waktu ke frekuensi.
Perhitungan langsung DFT memerlukan waktu komputasi yang sangat panjang, terutama untuk jumlah data yang besar, karena memiliki kompleksitas algoritmik sebesar (O(N^2)), di mana (N) adalah jumlah sampel data.
Sejarah dan Pengembangan
Konsep dasar FFT telah diperkenalkan oleh Carl Friedrich Gauss pada 1805. Adapun komputasinya baru dikembangkan awal dasawarsa 1960-an. Gauss mengembangkan metode serupa untuk menghitung orbit asteroid dan interpolasi numerik.
Pada 1965 James W. Cooley dan John W. Tukey menerbitkan algoritma komputasi FFT berjudul "An Algorithm for the Machine Calculation of Complex Fourier Series" untuk perhitungan DFT. Algoritma ini memungkinkan perhitungan selesai lebih cepat dan murah. Cooley adalah matematikawan yang bekerja untuk IBM, dan Tukey adalah seorang statistikawan yang bekerja di Bell Labs.
Algoritma Cooley-Tukey memanfaatkan simetri dan periodicity DFT, serta fakta bahwa banyak operasi dapat dilakukan secara rekursif dan dalam parallel. Saran mereka mengurangi kompleksitas komputasi dari (O(N^2)) menjadi (O(N \log N)). Ini membuat perhitungan DFT praktis untuk aplikasi nyata dalam sains, teknik, dan terutama pemrosesan sinyal digital, di mana transformasi Fourier cepat menjadi alat yang sangat penting.
Sejak Algoritma Cooley-Tukey, lahir turunan seperti algoritma radix-2, radix-4, dan algoritma yang dioptimalkan untuk perangkat keras tertentu. FFT telah menjadi salah satu algoritma paling penting dalam pemrosesan sinyal digital, memungkinkan aplikasi seperti kompresi data, analisis spektral, dan banyak lagi.
Algoritma Cooley-Tukey didapuk sebagai salah satu pencapaian besar dalam komputasi numerik abad ke-20. Algoritma ini tidak hanya membuka jalan bagi pengembangan lanjutan dalam pemrosesan sinyal dan analisis frekuensi tetapi juga menginspirasi inovasi dalam algoritma numerik lainnya yang memanfaatkan pendekatan serupa untuk efisiensi komputasi.
Algoritma
Berikut adalah penjelasan langkah demi langkah untuk membuat kode progam yang akan diterapkan dalam bahasa pemrograman C:
Cek Basis Rekursi
Cek kondisi dasar rekursi. Jika panjang array N kurang dari atau sama dengan 1, tidak ada yang perlu dihitung, dan fungsi kembali.
Pembagian
Array input X dibagi menjadi dua bagian, even dan odd, berdasarkan indeks genap atau ganjil elemen. Ini memecah masalah DFT menjadi dua bagian yang lebih kecil.
Rekursi FFT
Fungsi FFT dipanggil secara rekursif pada kedua array even dan odd, memungkinkan algoritma untuk memecah masalah lebih lanjut menjadi sub-masalah yang lebih kecil.
Kombinasi
Hasil dari sub-masalah even dan odd digabungkan menggunakan formula:
X[k] = E[k] + e^{-2\pi i k/N} O[k] X[k + N/2] = E[k] - e^{-2\pi i k/N} O[k]di mana E[k] adalah elemen k-th dari hasil FFT pada array even, O[k] adalah elemen k-th dari hasil FFT pada array odd, N adalah ukuran array saat ini, dan e^{-2\pi i k/N} adalah faktor twiddle.
Hasil
Setelah proses rekursi dan kombinasi selesai, array X mengandung hasil FFT dari data input, yang mewakili representasi frekuensi dari sinyal waktu asli.
kode
#include < stdio.h >
#include < stdlib.h >
#include < math.h >
#include < complex.h >
#include < string.h >
#include < time.h >
#define PI 3.14159265358979323846
void fft(complex double *X, int N)
{
if (N < = 1)
return;
complex double even[N / 2];
complex double odd[N / 2];
for (int i = 0; i < N / 2; i++)
{
even[i] = X[2 * i];
odd[i] = X[2 * i + 1];
}
fft(even, N / 2);
fft(odd, N / 2);
for (int k = 0; k < N / 2; k++)
{
complex double t = cexp(-2.0 * I * PI * k / N) * odd[k];
X[k] = even[k] + t;
X[k + N / 2] = even[k] - t;
}
}
double parseDateTimeToSeconds(const char *datetime)
{
struct tm tm = {0};
int year, month, day, hour, minute, second;
sscanf(datetime, "%d-%d-%d %d:%d:%d", &year, &month, &day, &hour, &minute, &second);
tm.tm_year = year - 1900; // Year since 1900
tm.tm_mon = month - 1; // Month, where 0 = january
tm.tm_mday = day; // Day of the month
tm.tm_hour = hour;
tm.tm_min = minute;
tm.tm_sec = second;
return (double)mktime(&tm);
}
int main(int argc, char *argv[])
{
char *filename = NULL;
for (int i = 1; i < argc; i++)
{
if (strncmp(argv[i], "--file=", 7) == 0)
{
filename = argv[i] + 7;
}
}
if (filename == NULL)
{
printf("Usage: program --file=\"filename.csv\"\n");
return 1;
}
FILE *file = fopen(filename, "r");
if (file == NULL)
{
printf("Error opening file\n");
return 1;
}
complex double X[512]; // Asumsikan maksimum 512 data points
double timestamps[512];
int N = 0;
char line[512];
fgets(line, sizeof(line), file); // Skip header
while (fgets(line, sizeof(line), file) && N < 512)
{
char datetime[20];
double x;
if (sscanf(line, "%[^,],%lf", datetime, &x) == 2)
{
timestamps[N] = parseDateTimeToSeconds(datetime);
X[N++] = x;
}
}
fclose(file);
// Hitung sample rate
double totalInterval = timestamps[N - 1] - timestamps[0];
double sampleRate = (N - 1) / totalInterval;
// Pastikan jumlah data genap dan lebih dari 1
if (N < 2)
{
printf("Data insufficient for FFT processing.\n");
return 1;
}
// Jika jumlah data ganjil, abaikan data terakhir
if (N % 2 != 0)
{
N--;
}
fft(X, N);
printf("\"Amplitude\",\"Frequency\"\n");
for (int i = 1; i < N / 2; i++)
{ // Mulai dari 1 untuk menghindari frekuensi 0 Hz
double freq = i * sampleRate / N; // Frekuensi dalam Hz
double amplitude = cabs(X[i]) / N; // Hitung amplitudo
printf("%f,%f\n", amplitude, freq);
}
return 0;
}
praktikum
Contoh data
| DateTime | acl_z (m/s^2) |
|---|---|
| 2024-02-02 17:21:00 | -0.16 |
| 2024-02-02 17:21:00 | -0.16 |
| 2024-02-02 17:21:00 | -0.17 |
| 2024-02-02 17:21:00 | -0.17 |
| 2024-02-02 17:21:01 | -0.17 |
| 2024-02-02 17:21:01 | -0.17 |
| 2024-02-02 17:21:01 | -0.17 |
| 2024-02-02 17:21:01 | -0.17 |
| 2024-02-02 17:21:03 | -0.18 |
| 2024-02-02 17:21:03 | -0.18 |
| 2024-02-02 17:21:03 | -0.16 |
| 2024-02-02 17:21:03 | -0.16 |
| 2024-02-02 17:21:03 | -0.17 |
| 2024-02-02 17:21:03 | -0.17 |
| 2024-02-02 17:21:03 | -0.18 |
| 2024-02-02 17:21:03 | -0.18 |
| 2024-02-02 17:21:04 | -0.16 |
| 2024-02-02 17:21:04 | -0.16 |
| 2024-02-02 17:21:04 | -0.16 |
| 2024-02-02 17:21:04 | -0.16 |
| 2024-02-02 17:21:04 | -0.16 |
| 2024-02-02 17:21:04 | -0.16 |
Hasil Algoritma FFT Cooley-Tukey
| Amplitude | Frequency |
|---|---|
| 0.000900 | 0.238636 |
| 0.001745 | 0.477273 |
| 0.002759 | 0.715909 |
| 0.010166 | 0.954545 |
| 0.000000 | 1.193182 |
| 0.001860 | 1.431818 |
| 0.000983 | 1.670455 |
| 0.000548 | 1.909091 |
| 0.007455 | 2.147727 |
| 0.002070 | 2.386364 |
Perdebatan
Data mentah berasal dari sensor gerak tiga-sumbu MPU6050 pada sisi Z. Semata melirik data mentah tidak memberi informasi yang menarik perhatian.
Setelah dihitung dengan FFT, tampil lah frekuensi dan kekuatan masing-masing. Dari data terlihat frekuensi paling dominan selama 5 detik pengukuran ada di dekat 1Hz. Artinya, sensor menangkap ada gerakan yang berulang (hampir) 1 kali per detik selama 5 detik pengamatan.
Puncak Resonansi (Resonance Peaks)
Saat melihat puncak yang tinggi pada grafik, seperti yang ada di frekuensi sekitar 0.95, itu artinya di frekuensi tersebut, sistem atau sinyal bergetar kuat. Puncak-puncak ini penting karena menunjukkan pada frekuensi mana sistem bergetar paling kuat.
Tanggapan Frekuensi (Frequency Response)
Grafik ini menunjukkan bagaimana sistem atau sinyal bereaksi terhadap frekuensi yang berbeda. Misalnya, jika amplitudo meningkat tajam pada frekuensi tertentu, itu berarti sistem atau sinyal tersebut lebih sensitif terhadap frekuensi tersebut.
Lebar Band (bandwidth)
Dengan melihat seberapa lebar rentang frekuensi dimana amplitudo cukup besar, kita bisa mengerti lebar band sistem atau sinyal tersebut. Lebar band ini penting untuk mengetahui frekuensi mana saja yang bisa ditanggapi atau diolah sistem dengan baik.
Peredaman (Damping)
Perubahan amplitudo, seperti bagaimana sinyal naik atau turun di berbagai frekuensi, bisa memberi informasi seberapa cepat sistem kehilangan energinya. Ini bisa menunjukkan seberapa baik sistem mengurangi getaran atau suara yang tidak diinginkan seiring waktu.
Ciri Khas Sistem atau Sinyal (System or Signal Characteristics)
Dari bentuk grafik dan bagaimana amplitudo berubah terhadap frekuensi, kita bisa belajar tentang ciri khas dari sistem atau sinyal tersebut. Ini termasuk mengetahui pada frekuensi rendah atau tinggi mana sistem lebih mudah bergetar atau bereaksi.
Kemungkinan Noise atau Kesalahan Pengukuran (Potential Noise or Artifacts)
Jika ada lonjakan tiba-tiba atau perubahan yang tidak diharapkan dalam grafik, itu mungkin menunjukkan adanya gangguan atau kesalahan dalam data atau sistem yang dianalisis. Ini bisa jadi area yang perlu diteliti lebih lanjut atau diperbaiki.
Karena gerakan terbilang sangat lemah dan lambat, bisa jadi itu adalah getaran yang disebabkan oleh aliran angin/air. Untuk memastikan penyebab, perlu ada pemeriksaan lokasi sensor MPU6050.
Apabila pada interval pengukuran 5 detik berikutnya selama, katakanlah 1 jam, grafik itu tetap sama atau nyaris identik, kita sangat yakin sumber getaran terjadi konsisten selama 1 jam, dan seterusnya.
Tinggal cari saja apa yang bergerak lambat dan konsisten di sekitar sensor. Apabila grafik pengukuran berikutnya tidak menghasilkan pola yang identik, dugaan awal dianggap keliru.
Ini lah salah satu contoh pemakaian algoritma Cooley-Tukey untuk masalah pratidina. Dengan melihat grafik amplitudo dan frekuensi, kita bisa mengerti banyak hal tentang bagaimana sistem atau sinyal bekerja, seperti pada frekuensi mana ia bergetar kuat, bagaimana ia bereaksi terhadap frekuensi yang berbeda, dan seberapa baik ia mengurangi getaran yang tidak diinginkan. Ini sangat penting untuk membuat sistem yang bekerja dengan baik dan mengerti bagaimana sesuatu bergetar atau berbunyi.
