[C++知识库]C语言实现 IFFT 运算

参考 《C》C语言实现FFT算法_杨贵安的博客-CSDN博客_c语言 fft 实现了 fft 运算；

如果要实现 ifft 运算，只需要在输入和输出时取共轭就好了，故 ifft 的 C 语言实现如下（已经通过matlab 验证）。

// n 为信号长度， n=2^k
// pr 为输入信号实部，pi 为输入信号虚部
// fr 为输出信号实部，fi 为输出信号虚部
// 函数执行后，pr 变为输出信号的模
void ifft(int n, int k,
	long double pr[], long double pi[], long double fr[], long double fi[])
{
	int it, m, is, i, j, nv, l0;
	long double p, q, s, vr, vi, poddr, poddi;

	for (i = 0; i < n; i++)	// 取共轭
	{
		pi[i] = -pi[i];
	}

	for (it = 0; it <= n - 1; it++)  //将pr[0]和pi[0]循环赋值给fr[]和fi[]
	{
		m = it;
		is = 0;
		for (i = 0; i <= k - 1; i++)
		{
			j = m / 2;
			is = 2 * is + (m - 2 * j);
			m = j;
		}
		fr[it] = pr[is];
		fi[it] = pi[is];
	}
	pr[0] = 1.0;
	pi[0] = 0.0;
	p = 6.283185306 / (1.0 * n);
	pr[1] = cos(p); //将w=e^-j2pi/n用欧拉公式表示
	pi[1] = -sin(p);

	for (i = 2; i <= n - 1; i++)  //计算pr[]
	{
		p = pr[i - 1] * pr[1];
		q = pi[i - 1] * pi[1];
		s = (pr[i - 1] + pi[i - 1]) * (pr[1] + pi[1]);
		pr[i] = p - q; pi[i] = s - p - q;
	}
	for (it = 0; it <= n - 2; it = it + 2)
	{
		vr = fr[it];
		vi = fi[it];
		fr[it] = vr + fr[it + 1];
		fi[it] = vi + fi[it + 1];
		fr[it + 1] = vr - fr[it + 1];
		fi[it + 1] = vi - fi[it + 1];
	}
	m = n / 2;
	nv = 2;
	for (l0 = k - 2; l0 >= 0; l0--) //蝴蝶操作
	{
		m = m / 2;
		nv = 2 * nv;
		for (it = 0; it <= (m - 1) * nv; it = it + nv)
			for (j = 0; j <= (nv / 2) - 1; j++)
			{
				p = pr[m * j] * fr[it + j + nv / 2];
				q = pi[m * j] * fi[it + j + nv / 2];
				s = pr[m * j] + pi[m * j];
				s = s * (fr[it + j + nv / 2] + fi[it + j + nv / 2]);
				poddr = p - q;
				poddi = s - p - q;
				fr[it + j + nv / 2] = fr[it + j] - poddr;
				fi[it + j + nv / 2] = fi[it + j] - poddi;
				fr[it + j] = fr[it + j] + poddr;
				fi[it + j] = fi[it + j] + poddi;
			}
	}

	for (i = 0; i < n; i++)	// 取共轭
	{
		fr[i] = fr[i] / n;
		fi[i] = -fi[i] / n;
	}

	for (i = 0; i <= n - 1; i++)
	{
		pr[i] = sqrt(fr[i] * fr[i] + fi[i] * fi[i]);  //幅值计算
	}
	return;
}