ফাস্ট ফুরিয়ার ট্রান্সফর্ম (এফএফটি) হল বিযুক্ত ফুরিয়ার ট্রান্সফর্ম (ডিএফটি) এবং এর বিপরীত গণনা করার জন্য একটি অ্যালগরিদম। মূলত ফুরিয়ার বিশ্লেষণ সময়কে (বা স্থান) ফ্রিকোয়েন্সিতে রূপান্তর করে এবং এর বিপরীতে। একটি এফএফটি দ্রুত রূপান্তর গণনা করে ডিএফটি ম্যাট্রিক্সকে স্পার্স (বেশিরভাগই শূন্য) ফ্যাক্টরগুলির গুণিতক হিসাবে।
অ্যালগরিদম
Begin Declare the size of the array Take the elements of the array Declare three arrays Initialize height =size of array and width=size of array Create two outer loops to iterate on output data Create two outer loops to iterate on input data Compute real, img and amp. End
উদাহরণ কোড
#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)