TAG:
|
共同讨论，期待并绝对接受您的批评和意见。 typedef struct COMPLEX // 复数结构体 { double Real; double Imag; } Complex; // 一维 FFT 变换 void FFT1D(Complex* pTD, Complex* pFD, unsigned int nGrade); // 一维 IFFT 变换 void IFFT1D(Complex* pFD, Complex* pTD, unsigned int nGrade); // 一维 FFT 变换 void FFT1D(Complex* pTD, Complex* pFD, unsigned int nGrade) { Complex *W, *X1, *X2, *X; Complex TempComplex; unsigned int i, j, k; unsigned int bfsize, p; unsigned int nCount = 1 << nGrade; double dAngle; // 分配内存空间 W = new Complex[nCount >> 1]; X1 = new Complex[nCount]; X2 = new Complex[nCount]; // 计算加权系数 for(i = 0; i < (nCount >> 1); i++) { dAngle = PI * 2.0 * i / nCount; W[i].Real = cos(dAngle); W[i].Imag = - sin(dAngle); } // 内存拷贝 memcpy(X1, pTD, sizeof(Complex) * nCount); // 采用蝶形算法进行快速傅立叶变换 for(k = 0; k < nGrade; k++) { for(j = 0; j < (unsigned int) (1 << k); j++) { bfsize = 1 << (nGrade - k); for(i = 0; i < bfsize / 2; i++) { p = j * bfsize; X2[i + p].Real = X1[i + p].Real + X1[i + p + bfsize / 2].Real; X2[i + p].Imag = X1[i + p].Imag + X1[i + p + bfsize / 2].Imag; TempComplex.Real = X1[i + p].Real - X1[i + p + bfsize / 2].Real; TempComplex.Imag = X1[i + p].Imag - X1[i + p + bfsize / 2].Imag; X2[i + p + bfsize / 2].Real = TempComplex.Real * W[i * (1 << k)].Real - TempComplex.Imag * W[i * (1 << k)].Imag; X2[i + p + bfsize / 2].Imag = TempComplex.Real * W[i * (1 << k)].Imag + TempComplex.Imag * W[i * (1 << k)].Real; } } X = X1; X1 = X2; X2 = X; } // 重新排序 for(j = 0; j < nCount; j++) { p = 0; for(i = 0; i < nGrade; i++) { if (j & (1 << i)) { p += 1 << (nGrade - i - 1); } } pFD[j].Real = X1[p].Real; pFD[j].Imag = X1[p].Imag; } delete[] W; delete[] X1; delete[] X2; } // 一维 IFFT 变换 void IFFT1D(Complex* pFD, Complex* pTD, unsigned int nGrade) { Complex *W, *X1, *X2, *X; Complex TempComplex; unsigned int i, j, k; unsigned int bfsize, p; unsigned int nCount = 1 << nGrade; double dAngle; // 分配内存空间 W = new Complex[nCount >> 1]; X1 = new Complex[nCount]; X2 = new Complex[nCount]; // 计算加权系数 for(i = 0; i < (nCount >> 1); i++) { dAngle = PI * 2.0 * i / nCount; W[i].Real = cos(dAngle); W[i].Imag = sin(dAngle); } // 内存拷贝 memcpy(X1, pFD, sizeof(Complex) * nCount); // 采用蝶形算法进行快速傅立叶变换 for(k = 0; k < nGrade; k++) { for(j = 0; j < (unsigned int) (1 << k); j++) { bfsize = 1 << (nGrade - k); for(i = 0; i < bfsize / 2; i++) { p = j * bfsize; X2[i + p].Real = X1[i + p].Real + X1[i + p + bfsize / 2].Real; X2[i + p].Imag = X1[i + p].Imag + X1[i + p + bfsize / 2].Imag; TempComplex.Real = X1[i + p].Real - X1[i + p + bfsize / 2].Real; TempComplex.Imag = X1[i + p].Imag - X1[i + p + bfsize / 2].Imag; X2[i + p + bfsize / 2].Real = TempComplex.Real * W[i * (1 << k)].Real - TempComplex.Imag * W[i * (1 << k)].Imag; X2[i + p + bfsize / 2].Imag = TempComplex.Real * W[i * (1 << k)].Imag + TempComplex.Imag * W[i * (1 << k)].Real; } } X = X1; X1 = X2; X2 = X; } // 重新排序 for(j = 0; j < nCount; j++) { p = 0; for(i = 0; i < nGrade; i++) { if (j & (1 << i)) { p += 1 << (nGrade - i - 1); } } pTD[j].Real = X1[p].Real / (double) nCount; pTD[j].Imag = X1[p].Imag / (double) nCount; } delete[] W; delete[] X1; delete[] X2; } (iwgh) |