algorithm - Gold Rader 位反转算法

Question

我正在尝试理解这种位反转算法。我找到了很多资源，但并没有真正解释伪代码的工作原理。例如，我从 http://www.briangough.com/fftalgorithms.pdf 中找到了下面的伪代码

for i = 0 ... n − 2 do
  k = n/2
  if i < j then
    swap g(i) and g(j)
  end if
  while k ≤ j do
    j ⇐ j − k
    k ⇐ k/2
  end while
  j ⇐ j + k
end for

看了这段伪代码，我不明白你为什么要这样做

交换 g(i) 和 g(j)

当 if 语句为 true 时。

另外:while 循环有什么作用？如果有人能向我解释这个伪代码，那就太好了。

下面是我在网上找到的c++代码。

void four1(double data[], int nn, int isign)
{
    int n, mmax, m, j, istep, i;
    double wtemp, wr, wpr, wpi, wi, theta;
    double tempr, tempi;

    n = nn << 1;
    j = 1;
    for (i = 1; i < n; i += 2) {
        if (j > i) {
            tempr = data[j];     data[j] = data[i];     data[i] = tempr;
            tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;
        }
        m = n >> 1;
        while (m >= 2 && j > m) {
            j -= m;
            m >>= 1;
        }
        j += m;
    }

这是我找到的执行 FFT 的源代码的完整版本

/************************************************
* FFT code from the book Numerical Recipes in C *
* Visit www.nr.com for the licence.             *
************************************************/

// The following line must be defined before including math.h to correctly define M_PI
#define _USE_MATH_DEFINES
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define PI  M_PI    /* pi to machine precision, defined in math.h */
#define TWOPI   (2.0*PI)

/*
 FFT/IFFT routine. (see pages 507-508 of Numerical Recipes in C)

 Inputs:
    data[] : array of complex* data points of size 2*NFFT+1.
        data[0] is unused,
        * the n'th complex number x(n), for 0 <= n <= length(x)-1, is stored as:
            data[2*n+1] = real(x(n))
            data[2*n+2] = imag(x(n))
        if length(Nx) < NFFT, the remainder of the array must be padded with zeros

    nn : FFT order NFFT. This MUST be a power of 2 and >= length(x).
    isign:  if set to 1, 
                computes the forward FFT
            if set to -1, 
                computes Inverse FFT - in this case the output values have
                to be manually normalized by multiplying with 1/NFFT.
 Outputs:
    data[] : The FFT or IFFT results are stored in data, overwriting the input.
*/

void four1(double data[], int nn, int isign)
{
    int n, mmax, m, j, istep, i;
    double wtemp, wr, wpr, wpi, wi, theta;
    double tempr, tempi;

    n = nn << 1;
    j = 1;
    for (i = 1; i < n; i += 2) {
        if (j > i) {
            //swap the real part
            tempr = data[j];     data[j] = data[i];     data[i] = tempr;
            //swap the complex part
            tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;
        }
        m = n >> 1;
        while (m >= 2 && j > m) {
            j -= m;
            m >>= 1;
        }
        j += m;
    }
    mmax = 2;
    while (n > mmax) {
    istep = 2*mmax;
    theta = TWOPI/(isign*mmax);
    wtemp = sin(0.5*theta);
    wpr = -2.0*wtemp*wtemp;
    wpi = sin(theta);
    wr = 1.0;
    wi = 0.0;
    for (m = 1; m < mmax; m += 2) {
        for (i = m; i <= n; i += istep) {
        j =i + mmax;
        tempr = wr*data[j]   - wi*data[j+1];
        tempi = wr*data[j+1] + wi*data[j];
        data[j]   = data[i]   - tempr;
        data[j+1] = data[i+1] - tempi;
        data[i] += tempr;
        data[i+1] += tempi;
        }
        wr = (wtemp = wr)*wpr - wi*wpi + wr;
        wi = wi*wpr + wtemp*wpi + wi;
    }
    mmax = istep;
    }
}

/********************************************************
* The following is a test routine that generates a ramp *
* with 10 elements, finds their FFT, and then finds the *
* original sequence using inverse FFT                   *
********************************************************/

int main(int argc, char * argv[])
{
    int i;
    int Nx;
    int NFFT;
    double *x;
    double *X;

    /* generate a ramp with 10 numbers */
    Nx = 10;
    printf("Nx = %d\n", Nx);
    x = (double *) malloc(Nx * sizeof(double));
    for(i=0; i<Nx; i++)
    {
        x[i] = i;
    }

    /* calculate NFFT as the next higher power of 2 >= Nx */
    NFFT = (int)pow(2.0, ceil(log((double)Nx)/log(2.0)));
    printf("NFFT = %d\n", NFFT);

    /* allocate memory for NFFT complex numbers (note the +1) */
    X = (double *) malloc((2*NFFT+1) * sizeof(double));

    /* Storing x(n) in a complex array to make it work with four1. 
    This is needed even though x(n) is purely real in this case. */
    for(i=0; i<Nx; i++)
    {
        X[2*i+1] = x[i];
        X[2*i+2] = 0.0;
    }
    /* pad the remainder of the array with zeros (0 + 0 j) */
    for(i=Nx; i<NFFT; i++)
    {
        X[2*i+1] = 0.0;
        X[2*i+2] = 0.0;
    }

    printf("\nInput complex sequence (padded to next highest power of 2):\n");
    for(i=0; i<NFFT; i++)
    {
        printf("x[%d] = (%.2f + j %.2f)\n", i, X[2*i+1], X[2*i+2]);
    }

    /* calculate FFT */
    four1(X, NFFT, 1);

    printf("\nFFT:\n");
    for(i=0; i<NFFT; i++)
    {
        printf("X[%d] = (%.2f + j %.2f)\n", i, X[2*i+1], X[2*i+2]);
    }

    /* calculate IFFT */
    four1(X, NFFT, -1);

    /* normalize the IFFT */
    for(i=0; i<NFFT; i++)
    {
        X[2*i+1] /= NFFT;
        X[2*i+2] /= NFFT;
    }

    printf("\nComplex sequence reconstructed by IFFT:\n");
    for(i=0; i<NFFT; i++)
    {
        printf("x[%d] = (%.2f + j %.2f)\n", i, X[2*i+1], X[2*i+2]);
    }

    getchar();
}

/*

Nx = 10
NFFT = 16

Input complex sequence (padded to next highest power of 2):
x[0] = (0.00 + j 0.00)
x[1] = (1.00 + j 0.00)
x[2] = (2.00 + j 0.00)
x[3] = (3.00 + j 0.00)
x[4] = (4.00 + j 0.00)
x[5] = (5.00 + j 0.00)
x[6] = (6.00 + j 0.00)
x[7] = (7.00 + j 0.00)
x[8] = (8.00 + j 0.00)
x[9] = (9.00 + j 0.00)
x[10] = (0.00 + j 0.00)
x[11] = (0.00 + j 0.00)
x[12] = (0.00 + j 0.00)
x[13] = (0.00 + j 0.00)
x[14] = (0.00 + j 0.00)
x[15] = (0.00 + j 0.00)

FFT:
X[0] = (45.00 + j 0.00)
X[1] = (-25.45 + j 16.67)
X[2] = (10.36 + j -3.29)
X[3] = (-9.06 + j -2.33)
X[4] = (4.00 + j 5.00)
X[5] = (-1.28 + j -5.64)
X[6] = (-2.36 + j 4.71)
X[7] = (3.80 + j -2.65)
X[8] = (-5.00 + j 0.00)
X[9] = (3.80 + j 2.65)
X[10] = (-2.36 + j -4.71)
X[11] = (-1.28 + j 5.64)
X[12] = (4.00 + j -5.00)
X[13] = (-9.06 + j 2.33)
X[14] = (10.36 + j 3.29)
X[15] = (-25.45 + j -16.67)

Complex sequence reconstructed by IFFT:
x[0] = (0.00 + j -0.00)
x[1] = (1.00 + j -0.00)
x[2] = (2.00 + j 0.00)
x[3] = (3.00 + j -0.00)
x[4] = (4.00 + j -0.00)
x[5] = (5.00 + j 0.00)
x[6] = (6.00 + j -0.00)
x[7] = (7.00 + j -0.00)
x[8] = (8.00 + j 0.00)
x[9] = (9.00 + j 0.00)
x[10] = (0.00 + j -0.00)
x[11] = (0.00 + j -0.00)
x[12] = (0.00 + j 0.00)
x[13] = (-0.00 + j -0.00)
x[14] = (0.00 + j 0.00)
x[15] = (0.00 + j 0.00)

*/

Answer 1

位反转算法通过反转每个项目的二进制地址来创建数据集的排列；所以例如在 16 项集合中地址:
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
将更改为:
1000 0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 0111 1111
然后相应的项目被移动到他们的新地址。

或者用十进制表示:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
成为
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

伪代码中 while 循环的作用是将变量 j 设置为该序列。 (顺便说一下，j 的初始值应该是 0)。

你会看到序列是这样组成的:
0
0 1
0 2 1 3
0 4 2 6 1 5 3 7
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
每个序列都是通过将前一个版本乘以 2，然后重复添加 1 来制作的。或者换一种方式看:通过重复前面的序列，与值 + n/2 交错(这更准确地描述了算法中发生的事情)。

0                                               
0                       1                       
0           2           1           3           
0     4     2     6     1     5     3     7     
0  8  4 12  2 10  6 14  1  9  5 13  3 11  7 15  

然后在 for 循环的每次迭代中交换项目 i 和 j，但前提是 i < j；否则每个项目都会被交换到它的新位置(例如，当 i = 3 和 j = 12 时)，然后再返回(当 i = 12 和 j = 3 时)。

function bitReversal(data) {
    var n = data.length;
    var j = 0;
    for (i = 0; i < n - 1; i++) {
        var k = n / 2;
        if (i < j) {
            var temp = data[i]; data[i] = data[j]; data[j] = temp;
        }
        while (k <= j) {
            j -= k;
            k /= 2;
        }
        j += k;
    }
    return(data);
}

console.log(bitReversal([0,1]));
console.log(bitReversal([0,1,2,3]));
console.log(bitReversal([0,1,2,3,4,5,6,7]));
console.log(bitReversal([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]));
console.log(bitReversal(["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p"]));

您发现的 C++ 代码似乎使用序列的对称性以双步循环遍历它。但是它并没有产生正确的结果，所以它要么是一次失败的尝试，要么可能是为了做一些完全不同的事情而设计的。这是一个使用两步想法的版本:

function bitReversal2(data) {
    var n = data.length;
    var j = 0;
    for (i = 0; i < n; i += 2) {
        if (i < j) {
            var temp = data[i]; data[i] = data[j]; data[j] = temp;
        }
        else {
            var temp = data[n-1 - i]; data[n-1 - i] = data[n-1 - j]; data[n-1 - j] = temp;
        }
        var k = n / 4;
        while (k <= j) {
            j -= k;
            k /= 2;
        }
        j += k;
    }
    return(data);
}

console.log(bitReversal2([0,1]));
console.log(bitReversal2([0,1,2,3]));
console.log(bitReversal2([0,1,2,3,4,5,6,7]));
console.log(bitReversal2([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]));
console.log(bitReversal2(["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p"]));