FFT 重新排序阶段

Question

我为你们准备了一些代码。这是快速傅里叶变换分裂算法的第一步。

算法应该做的是重新排序数组，以便输入中的每个元素都将在输出的 "binary mirrored" 位置移位。

例如，元素 X[4] 将位于位置 X[1]，因为 100 的镜像表示是 001。

到这里，一切都清楚了。但是，执行此类重新排序的算法不是。至少我很难理解。

第二个内循环是做什么的？

// N is the length of the array
// p is the number of bits needed to represent the index

for(int n=0; n<N; n++) {

   int j=0; 
   int m=n;
   for(int i=0; i<p; i++) {
     j = 2∗j + m%2; m = m/2;
   }

   if ( j>n) { 
     complex<double> h;
     h = X[j]; 
     X[j] = X[n]; 
     X[n] = h;
   }

}

Answer 1

每次迭代，我们将j乘以2（相当于左移1），然后加上m的奇偶校验。然后我们将 m 除以二（这与右移 1 相同）。 m 以 n 的值开头。所以我们实际上是在反转 n 中的位，并将其存储在 j.

中

Answer 2

将整数想象成一个位序列。

j = 2j 这会弹出左侧的位并将零推入右侧
m % 2这就得到了正确的位
m = m / 2弹出右边的位，把最左边的位压入左边
j + x 将 j 的最右边位设置为 x，假设该位当前为零并且 x 是 0 或 1

所以这一切所做的就是从 m 的右侧弹出位并将它们推到 j 的右侧。

FFT 重新排序阶段

FFT reordering phase

c

algorithm

fft