Menulis Program Fast Fourier Transform
FFT atau adalah sebuah teknik untuk memecah sinyal menjadi bagian-bagian kecil untuk dipelajari dengan lebih mudah. Sama seperti kita memecah masalah matematika yang sulit menjadi bagian yang lebih kecil dan mudah dikerjakan.
FFT digunakan untuk menganalisis sinyal suara, video, dan gambar. Contohnya, kita dapat menggunakan FFT untuk melihat gelombang suara yang kita dengar, dan memisahkan suara dari instrumen yang berbeda dalam musik. Dalam ilmu komputer, FFT membantu kita mempercepat pengolahan data pada sistem komunikasi nirkabel, pemrosesan gambar, dan pemrosesan sinyal medis.
Algoritma
- Tentukan panjang sinyal yang akan diproses (N). N harus merupakan bilangan pangkat dua (2^n) untuk FFT.
- Hitung nilai kompleks dari akar persamaan x^N = 1. Ini akan membentuk tabel akar yang akan digunakan untuk perhitungan FFT.
- Lakukan pengurutan ulang terhadap sinyal dengan algoritma bit reversal. Pengurutan ini akan memastikan bahwa sinyal diproses dalam urutan yang benar untuk FFT.
- Lakukan FFT dengan melakukan perhitungan untuk setiap level transformasi. FFT dilakukan dalam bentuk iteratif dengan menghitung nilai transformasi pada setiap level secara terpisah.
Pada setiap level transformasi, ulangi langkah-langkah berikut: a. Pisahkan sinyal menjadi dua bagian, bagian atas dan bawah. b. Hitung nilai transformasi pada setiap bagian dengan menggunakan rumus FFT. c. Gabungkan hasil transformasi dari kedua bagian untuk mendapatkan hasil transformasi keseluruhan.
Setelah semua level transformasi selesai, sinyal telah tertransformasi menjadi domain frekuensi dengan menggunakan FFT.
pseudocode
function fft(signal):
N = length(signal)
if N == 1:
return signal
else:
even = fft(signal[0::2])
odd = fft(signal[1::2])
T = [exp(-2jpik/N)*odd[k] for k in range(N//2)]
return [even[k] + T[k] for k in range(N//2)] + [even[k] - T[k] for k in range(N//2)]C Sharp
using System;
namespace FFT
{
class Program
{
static void BitReversal(int n, Complex[] x)
{
int i, j, k;
Complex temp;
for (i = 0, j = 0; i < n; i++)
{
if (j > i)
{
temp = x[j];
x[j] = x[i];
x[i] = temp;
}
k = n / 2;
while (k < = j)
{
j -= k;
k /= 2;
}
j += k;
}
}
static void FFT(int n, Complex[] x)
{
if (n == 1)
{
return;
}
int i;
Complex w, wn;
Complex[] xeven, xodd;
xeven = new Complex[n / 2];
xodd = new Complex[n / 2];
wn = Complex.Exp(-2 * Math.PI * Complex.ImaginaryOne / n);
w = 1;
for (i = 0; i < n / 2; i++)
{
xeven[i] = x[2 * i];
xodd[i] = x[2 * i + 1];
}
FFT(n / 2, xeven);
FFT(n / 2, xodd);
for (i = 0; i < n / 2; i++)
{
x[i] = xeven[i] + w * xodd[i];
x[i + n / 2] = xeven[i] - w * xodd[i];
w *= wn;
}
}
static void Main(string[] args)
{
int n, i;
double[] signal;
Complex[] x;
Console.Write("Masukkan jumlah sampel: ");
n = Convert.ToInt32(Console.ReadLine());
signal = new double[n];
x = new Complex[n];
Console.Write("Masukkan sinyal: ");
for (i = 0; i < n; i++)
{
signal[i] = Convert.ToDouble(Console.ReadLine());
x[i] = new Complex(signal[i], 0);
}
BitReversal(n, x);
FFT(n, x);
Console.Write("Hasil transformasi: ");
for (i = 0; i < n; i++)
{
Console.Write("{0:F2} + {1:F2}i ", x[i].Real, x[i].Imaginary);
}
Console.WriteLine();
}
}
}
C
#include < stdio.h >
#include < stdlib.h >
#include < math.h >
#include < complex.h >
void bit_reversal(int n, double complex *x) {
int i, j, k;
double complex temp;
for (i = 0, j = 0; i < n; i++) {
if (j > i) {
temp = x[j];
x[j] = x[i];
x[i] = temp;
}
k = n / 2;
while (k < = j) {
j -= k;
k /= 2;
}
j += k;
}
}
void fft(int n, double complex *x) {
if (n == 1) {
return;
}
int i;
double complex w, wn, *xeven, *xodd, *xrecon;
xeven = (double complex *) malloc(n/2 * sizeof(double complex));
xodd = (double complex *) malloc(n/2 * sizeof(double complex));
xrecon = (double complex *) malloc(n * sizeof(double complex));
wn = cexp(-2 * M_PI * I / n);
w = 1;
for (i = 0; i < n/2; i++) {
xeven[i] = x[2*i];
xodd[i] = x[2*i+1];
}
fft(n/2, xeven);
fft(n/2, xodd);
for (i = 0; i < n/2; i++) {
x[i] = xeven[i] + w * xodd[i];
x[i + n/2] = xeven[i] - w * xodd[i];
w *= wn;
}
free(xeven);
free(xodd);
}
int main() {
int n, i;
double *signal;
double complex *x;
printf("Masukkan jumlah sampel: ");
scanf("%d", &n);
signal = (double *) malloc(n * sizeof(double));
x = (double complex *) malloc(n * sizeof(double complex));
printf("Masukkan sinyal: ");
for (i = 0; i < n; i++) {
scanf("%lf", &signal[i]);
x[i] = signal[i] + 0 * I;
}
bit_reversal(n, x);
fft(n, x);
printf("Hasil transformasi: ");
for (i = 0; i < n; i++) {
printf("%.2lf + %.2lfi ", creal(x[i]), cimag(x[i]));
}
printf("\n");
free(signal);
free(x);
return 0;
}
Dart
import 'dart:math';
List FFT(int n, List x) {
if (n == 1) {
return x;
}
List even = [];
List odd = [];
for (int i = 0; i < n / 2; i++) {
even.add(x[2 * i]);
odd.add(x[2 * i + 1]);
}
even = FFT(n / 2, even);
odd = FFT(n / 2, odd);
List y = List.filled(n, Complex(real: 0.0, imaginary: 0.0));
for (int k = 0; k < n / 2; k++) {
double kth = -2 * pi * k / n;
Complex wk = Complex(real: cos(kth), imaginary: sin(kth));
y[k] = even[k] + (wk * odd[k]);
y[k + n / 2] = even[k] - (wk * odd[k]);
}
return y;
}
void main() {
List x = [
Complex(real: 1.0, imaginary: 0.0),
Complex(real: 2.0, imaginary: 0.0),
Complex(real: 3.0, imaginary: 0.0),
Complex(real: 4.0, imaginary: 0.0)
];
int n = x.length;
List result = FFT(n, x);
for (int i = 0; i < n; i++) {
print("X[$i] = ${result[i].real} + ${result[i].imaginary}i");
}
}
class Complex {
final double real;
final double imaginary;
const Complex({required this.real, required this.imaginary});
Complex operator +(Complex other) {
return Complex(real: real + other.real, imaginary: imaginary + other.imaginary);
}
Complex operator -(Complex other) {
return Complex(real: real - other.real, imaginary: imaginary - other.imaginary);
}
Complex operator *(Complex other) {
return Complex(
real: (real * other.real) - (imaginary * other.imaginary),
imaginary: (real * other.imaginary) + (imaginary * other.real));
}
}
