algorithm
फास्ट फूरियर ट्रांसफॉर्म
खोज…
परिचय
DFT ( D iscrete F ourier T ransforms) के वास्तविक और जटिल रूप का उपयोग किसी भी असतत और आवधिक संकेतों के लिए आवृत्ति विश्लेषण या संश्लेषण करने के लिए किया जा सकता है। FFT ( F ast F ourier T ransform) डीएफटी का एक कार्यान्वयन है जो आधुनिक सीपीयू पर जल्दी से किया जा सकता है।
मूलांक 2 FFT
एफएफटी की गणना के लिए सबसे सरल और शायद सबसे अच्छा ज्ञात तरीका टाइम एल्गोरिथ्म में मूलांक -2 घोषणा है। रेडिक्स -2 एफएफटी एन पॉइंट डोमेन में एन पॉइंट टाइम डोमेन सिग्नल को एक-एक पॉइंट से बनाकर काम करता है। ।
सिग्नल अपघटन, या 'समय में विघटन' समय डोमेन डेटा की सरणी के लिए सूचकांकों को उलट कर प्राप्त किया जाता है। इस प्रकार, एक सोलह सूत्री संकेत के लिए, नमूना 1 (बाइनरी 0001) नमूना 8 (1000) के साथ स्वैप किया जाता है, नमूना 2 (0010) 4 (0100) और इतने पर के साथ स्वैप किया जाता है। बिट रिवर्स तकनीक का उपयोग करके नमूना स्वैपिंग को केवल सॉफ्टवेयर में प्राप्त किया जा सकता है, लेकिन लंबाई N = 2 ^ M के संकेतों के लिए मूलांक 2 FFT के उपयोग को सीमित करता है।
समय डोमेन में 1-पॉइंट सिग्नल का मूल्य आवृत्ति डोमेन में इसके मूल्य के बराबर है, इस प्रकार विघटित एकल टाइम-डोमेन पॉइंट्स के इस सरणी को आवृत्ति डोमेन पॉइंट्स की एक सरणी बनने के लिए कोई परिवर्तन की आवश्यकता नहीं है। एन एकल अंक; हालाँकि, एक एन-पॉइंट फ़्रीक्वेंसी स्पेक्ट्रा में पुनर्निर्माण किया जाना चाहिए। पूर्ण आवृत्ति स्पेक्ट्रम का इष्टतम पुनर्निर्माण तितली गणनाओं का उपयोग करके किया जाता है। रेडिक्स -2 एफएफटी में प्रत्येक पुनर्निर्माण चरण घातीय भार कार्यों के समान सेट का उपयोग करके, दो बिंदु तितलियों का प्रदर्शन करता है।
FFT Wn ^ R की आवधिकता का फायदा उठाकर असतत फूरियर ट्रांसफॉर्म में निरर्थक गणनाओं को हटा देता है। वर्णक्रमीय पुनर्निर्माण एक्स 2 [के] देने वाले तितली गणना के लॉग 2 (एन) चरणों में पूरा हो गया है; आयताकार रूप में वास्तविक और काल्पनिक आवृत्ति डोमेन डेटा। परिमाण और चरण (ध्रुवीय निर्देशांक) में बदलने के लिए पूर्ण मान, Re (Re2 + Im2) और तर्क, tan-1 (Im / Re) की आवश्यकता होती है।
एक आठ बिंदु मूलांक 2 FFT के लिए पूर्ण तितली प्रवाह आरेख नीचे दिखाया गया है। ध्यान दें कि इनपुट संकेतों को पूर्व में उल्लिखित समय प्रक्रिया में परिसीमन के अनुसार पुन: व्यवस्थित किया गया है।
एफएफटी आमतौर पर जटिल इनपुट पर काम करता है और एक जटिल आउटपुट का उत्पादन करता है। वास्तविक संकेतों के लिए, काल्पनिक भाग को शून्य और वास्तविक भाग को इनपुट सिग्नल, x [n] पर सेट किया जा सकता है, हालांकि वास्तविक-केवल डेटा के परिवर्तन में कई अनुकूलन संभव हैं। पुनर्निर्माण के दौरान उपयोग किए गए Wn ^ R का मान घातीय भार समीकरण का उपयोग करके निर्धारित किया जा सकता है।
R का मान (घातीय भार शक्ति) वर्णक्रमीय पुनर्निर्माण में वर्तमान चरण और एक विशेष तितली के भीतर वर्तमान गणना निर्धारित किया जाता है।
कोड उदाहरण (C / C ++)
रेडिक्स 2 एफएफटी की गणना के लिए एसी / सी ++ कोड नमूना नीचे पाया जा सकता है। यह एक सरल कार्यान्वयन है जो किसी भी आकार N के लिए काम करता है जहां N 2 की शक्ति है। यह सबसे तेज़ FFTw कार्यान्वयन की तुलना में लगभग 3x धीमा है, लेकिन फिर भी भविष्य के अनुकूलन के लिए या यह एल्गोरिथ्म कैसे काम करता है, इसके बारे में जानने के लिए एक बहुत अच्छा आधार है।
#include <math.h>
#define PI 3.1415926535897932384626433832795 // PI for sine/cos calculations
#define TWOPI 6.283185307179586476925286766559 // 2*PI for sine/cos calculations
#define Deg2Rad 0.017453292519943295769236907684886 // Degrees to Radians factor
#define Rad2Deg 57.295779513082320876798154814105 // Radians to Degrees factor
#define log10_2 0.30102999566398119521373889472449 // Log10 of 2
#define log10_2_INV 3.3219280948873623478703194294948 // 1/Log10(2)
// complex variable structure (double precision)
struct complex
{
public:
double Re, Im; // Not so complicated after all
};
// Returns true if N is a power of 2
bool isPwrTwo(int N, int *M)
{
*M = (int)ceil(log10((double)N) * log10_2_INV);// M is number of stages to perform. 2^M = N
int NN = (int)pow(2.0, *M);
if ((NN != N) || (NN == 0)) // Check N is a power of 2.
return false;
return true;
}
void rad2FFT(int N, complex *x, complex *DFT)
{
int M = 0;
// Check if power of two. If not, exit
if (!isPwrTwo(N, &M))
throw "Rad2FFT(): N must be a power of 2 for Radix FFT";
// Integer Variables
int BSep; // BSep is memory spacing between butterflies
int BWidth; // BWidth is memory spacing of opposite ends of the butterfly
int P; // P is number of similar Wn's to be used in that stage
int j; // j is used in a loop to perform all calculations in each stage
int stage = 1; // stage is the stage number of the FFT. There are M stages in total (1 to M).
int HiIndex; // HiIndex is the index of the DFT array for the top value of each butterfly calc
unsigned int iaddr; // bitmask for bit reversal
int ii; // Integer bitfield for bit reversal (Decimation in Time)
int MM1 = M - 1;
unsigned int i;
int l;
unsigned int nMax = (unsigned int)N;
// Double Precision Variables
double TwoPi_N = TWOPI / (double)N; // constant to save computational time. = 2*PI / N
double TwoPi_NP;
// complex Variables (See 'struct complex')
complex WN; // Wn is the exponential weighting function in the form a + jb
complex TEMP; // TEMP is used to save computation in the butterfly calc
complex *pDFT = DFT; // Pointer to first elements in DFT array
complex *pLo; // Pointer for lo / hi value of butterfly calcs
complex *pHi;
complex *pX; // Pointer to x[n]
// Decimation In Time - x[n] sample sorting
for (i = 0; i < nMax; i++, DFT++)
{
pX = x + i; // Calculate current x[n] from base address *x and index i.
ii = 0; // Reset new address for DFT[n]
iaddr = i; // Copy i for manipulations
for (l = 0; l < M; l++) // Bit reverse i and store in ii...
{
if (iaddr & 0x01) // Detemine least significant bit
ii += (1 << (MM1 - l)); // Increment ii by 2^(M-1-l) if lsb was 1
iaddr >>= 1; // right shift iaddr to test next bit. Use logical operations for speed increase
if (!iaddr)
break;
}
DFT = pDFT + ii; // Calculate current DFT[n] from base address *pDFT and bit reversed index ii
DFT->Re = pX->Re; // Update the complex array with address sorted time domain signal x[n]
DFT->Im = pX->Im; // NB: Imaginary is always zero
}
// FFT Computation by butterfly calculation
for (stage = 1; stage <= M; stage++) // Loop for M stages, where 2^M = N
{
BSep = (int)(pow(2, stage)); // Separation between butterflies = 2^stage
P = N / BSep; // Similar Wn's in this stage = N/Bsep
BWidth = BSep / 2; // Butterfly width (spacing between opposite points) = Separation / 2.
TwoPi_NP = TwoPi_N*P;
for (j = 0; j < BWidth; j++) // Loop for j calculations per butterfly
{
if (j != 0) // Save on calculation if R = 0, as WN^0 = (1 + j0)
{
//WN.Re = cos(TwoPi_NP*j)
WN.Re = cos(TwoPi_N*P*j); // Calculate Wn (Real and Imaginary)
WN.Im = -sin(TwoPi_N*P*j);
}
for (HiIndex = j; HiIndex < N; HiIndex += BSep) // Loop for HiIndex Step BSep butterflies per stage
{
pHi = pDFT + HiIndex; // Point to higher value
pLo = pHi + BWidth; // Point to lower value (Note VC++ adjusts for spacing between elements)
if (j != 0) // If exponential power is not zero...
{
//CMult(pLo, &WN, &TEMP); // Perform complex multiplication of Lovalue with Wn
TEMP.Re = (pLo->Re * WN.Re) - (pLo->Im * WN.Im);
TEMP.Im = (pLo->Re * WN.Im) + (pLo->Im * WN.Re);
//CSub (pHi, &TEMP, pLo);
pLo->Re = pHi->Re - TEMP.Re; // Find new Lovalue (complex subtraction)
pLo->Im = pHi->Im - TEMP.Im;
//CAdd (pHi, &TEMP, pHi); // Find new Hivalue (complex addition)
pHi->Re = (pHi->Re + TEMP.Re);
pHi->Im = (pHi->Im + TEMP.Im);
}
else
{
TEMP.Re = pLo->Re;
TEMP.Im = pLo->Im;
//CSub (pHi, &TEMP, pLo);
pLo->Re = pHi->Re - TEMP.Re; // Find new Lovalue (complex subtraction)
pLo->Im = pHi->Im - TEMP.Im;
//CAdd (pHi, &TEMP, pHi); // Find new Hivalue (complex addition)
pHi->Re = (pHi->Re + TEMP.Re);
pHi->Im = (pHi->Im + TEMP.Im);
}
}
}
}
pLo = 0; // Null all pointers
pHi = 0;
pDFT = 0;
DFT = 0;
pX = 0;
}
मूलांक 2 उलटा एफएफटी
फूरियर ट्रांसफॉर्म के मजबूत द्वंद्व के कारण, आगे रूपांतरण के आउटपुट को समायोजित करने से उलटा एफएफटी का उत्पादन हो सकता है। निम्न विधि द्वारा फ़्रीक्वेंसी डोमेन में डेटा को टाइम डोमेन में परिवर्तित किया जा सकता है:
- K के सभी उदाहरणों के लिए काल्पनिक घटक को सम्मिलित करके आवृत्ति डोमेन डेटा के जटिल संयुग्म का पता लगाएं।
- संयुग्मित आवृत्ति डोमेन डेटा पर आगे FFT करें।
- सही समय डोमेन मूल्य देने के लिए एन द्वारा इस एफएफटी के परिणाम के प्रत्येक आउटपुट को विभाजित करें।
- N के सभी उदाहरणों के लिए समय डोमेन डेटा के काल्पनिक घटक को सम्मिलित करके आउटपुट के जटिल संयुग्म का पता लगाएं।
नोट : आवृत्ति और समय डोमेन डेटा दोनों जटिल चर हैं। आमतौर पर उलटा एफएफटी के बाद के समय डोमेन सिग्नल का काल्पनिक घटक या तो शून्य होता है, या राउंडिंग त्रुटि के रूप में अनदेखा किया जाता है। 32-बिट फ्लोट से चर की सटीकता को 64-बिट डबल तक बढ़ाना, या 128-बिट लंबा डबल, लगातार कई एफएफटी संचालन द्वारा उत्पादित गोलाई त्रुटियों को कम करता है।
कोड उदाहरण (C / C ++)
#include <math.h>
#define PI 3.1415926535897932384626433832795 // PI for sine/cos calculations
#define TWOPI 6.283185307179586476925286766559 // 2*PI for sine/cos calculations
#define Deg2Rad 0.017453292519943295769236907684886 // Degrees to Radians factor
#define Rad2Deg 57.295779513082320876798154814105 // Radians to Degrees factor
#define log10_2 0.30102999566398119521373889472449 // Log10 of 2
#define log10_2_INV 3.3219280948873623478703194294948 // 1/Log10(2)
// complex variable structure (double precision)
struct complex
{
public:
double Re, Im; // Not so complicated after all
};
void rad2InverseFFT(int N, complex *x, complex *DFT)
{
// M is number of stages to perform. 2^M = N
double Mx = (log10((double)N) / log10((double)2));
int a = (int)(ceil(pow(2.0, Mx)));
int status = 0;
if (a != N) // Check N is a power of 2
{
x = 0;
DFT = 0;
throw "rad2InverseFFT(): N must be a power of 2 for Radix 2 Inverse FFT";
}
complex *pDFT = DFT; // Reset vector for DFT pointers
complex *pX = x; // Reset vector for x[n] pointer
double NN = 1 / (double)N; // Scaling factor for the inverse FFT
for (int i = 0; i < N; i++, DFT++)
DFT->Im *= -1; // Find the complex conjugate of the Frequency Spectrum
DFT = pDFT; // Reset Freq Domain Pointer
rad2FFT(N, DFT, x); // Calculate the forward FFT with variables switched (time & freq)
int i;
complex* x;
for ( i = 0, x = pX; i < N; i++, x++){
x->Re *= NN; // Divide time domain by N for correct amplitude scaling
x->Im *= -1; // Change the sign of ImX
}
}