ফাস্ট ফুরিয়ে ট্রান্সফরম (FFT) হলো ডিসক্রিট ফুরিয়ে ট্রান্সফরম (DFT) এবং এর ইনভার্স কম্পিউট করার একটি অ্যালগরিদম। বেসিক্যালি ফুরিয়ে অ্যানালিসিস টাইম (অথবা স্পেস) কে ফ্রিকোয়েন্সিতে এবং তার বিপরীতে কনভার্ট করে। একটি FFT র্যাপিডলি ট্রান্সফরমেশন কম্পিউট করে DFT ম্যাট্রিক্সকে স্পার্স (প্রায়শই জিরো) ফ্যাক্টরগুলোর প্রোডাক্টে ফ্যাক্টরাইজ করে।
অ্যালগরিদম
শুরু অ্যারের সাইজ ডিক্লেয়ার করুন অ্যারের এলিমেন্টগুলো নিন তিনটি অ্যারে ডিক্লেয়ার করুন height = অ্যারের সাইজ এবং width = অ্যারের সাইজ ইনিশিয়ালাইজ করুন আউটপুট ডেটায় ইটারেট করার জন্য দুটি আউটার লুপ তৈরি করুন ইনপুট ডেটায় ইটারেট করার জন্য দুটি আউটার লুপ তৈরি করুন real, img এবং amp কম্পিউট করুন। শেষ
উদাহরণ কোড
#include <iostream>
#include <math.h>
using namespace std;
#define PI 3.14159265
int n;
int main(int argc, char **argv) {
cout << "Enter the size: ";
cin >> n;
double Data[n][n];
cout << "Enter the 2D elements ";
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> Data[i][j];
double realOut[n][n];
double imgOut[n][n];
double ampOut[n][n];
int height = n;
int width = n;
for (int yWave = 0; yWave < height; yWave++) {
for (int xWave = 0; xWave < width; xWave++) {
for (int ySpace = 0; ySpace < height; ySpace++) {
for (int xSpace = 0; xSpace < width; xSpace++) {
realOut[yWave][xWave] += (Data[ySpace][xSpace] * cos(2 *
PI * ((1.0 * xWave * xSpace / width) + (1.0 * yWave * ySpace /
height)))) / sqrt(width * height);
imgOut[yWave][xWave] -= (Data[ySpace][xSpace] * sin(2 * PI
* ((1.0 * xWave * xSpace / width) + (1.0 * yWave * ySpace / height)))) /
sqrt(width * height);
ampOut[yWave][xWave] = sqrt(
realOut[yWave][xWave] * realOut[yWave][xWave] +
imgOut[yWave][xWave] * imgOut[yWave][xWave]);
}
}
cout << realOut[yWave][xWave] << " + " <<
imgOut[yWave][xWave] << " i (" << ampOut[yWave][xWave] << ")\n";
}
}
}
আউটপুট
Enter the size: 2 Enter the 2D elements 4 5 6 7 4.5 + 6.60611e-310 i (4.5) 11 + 6.60611e-310 i (11) -0.5 + -8.97448e-09 i (0.5) -1 + -2.15388e-08 i (1) 4.5 + 6.60611e-310 i (4.5) -2 + -2.33337e-08 i (2) -0.5 + -8.97448e-09 i (0.5) 0 + 5.38469e-09 i (5.38469e-09)
