Gold Rader bit reversal algorithm

问题:

I am trying to understand this bit reversal algorithm. I found a lot of sources but it doesn't really explain how the pseudo-code works. For example, I found the pseudo-code below from 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

From looking at this pseudo-code, I don't understand why you would do

swap g(i) and g(j)

when the if statement is true.

Also: what does the while loop do? It would be great if someone can explain this pseudo-code to me.

below is the c++ code that I found online.

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;
    }

Here is the full version of the source code that I found that does 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)

*/

回答1:

A bit-reversal algorithm creates a permutation of a data set by reversing the binary address of each item; so e.g. in a 16-item set the addresses:
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
will be changed into:
1000 0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 0111 1111
and the corresponding items are then moved to their new address.

Or in decimal notation:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
becomes
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

What the while loop in the pseudo-code does, is set variable j to this sequence. (Btw, the initial value of j should be 0).

You'll see that the sequence is made up like this:
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
with each sequence being made by multiplying the previous version by 2, and then repeating it with 1 added. Or looking at it another way: by repeating the previous sequence, interlaced with the values + n/2 (this more closely describes what happens in the algorithm).

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  

Items i and j are then swapped in each iteration of the for loop, but only if i < j; otherwise every item would be swapped to its new place (e.g. when i = 3 and j = 12), and then back again (when i = 12 and 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"]));

The C++ code you found appears to use the symmetry of the sequence to loop through it in double steps. It doesn't produce the correct result though, so either it's a failed attempt, or maybe it's designed to do something different entirely. Here's a version that uses the two-step idea:

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"]));

回答2:

First off, thanks for everyone's help in answering my question. I was talking to the person who is helping me, and I think I understand my C++ code now. Maybe my question is kind unclear, but what I am trying to do is implementing FFT using C++. The C++ code I gave in the question is just the first half of the FFT source code that I found online. Essentially, this part of the C++ code is sorting the inputs into real and imaginary numbers, store the real numbers into the odd index, and imaginary numbers into the even index. (real_0, imag_0, real_1, imag_1, real_2, imag_2,.....) with index starts at 1 because we don't need to swap the zeroth index.

The swap operation below is swapping the real and imaginary numbers.

tempr = data[j];     data[j] = data[i];     data[i] = tempr;
tempr = data[j+1]; data[j+1] = data[i+1]; data[i+1] = tempr;

For example, we have an array length of 8 (nn=8), then 2*nn=16, and we separate our inputs into real and imag numbers and store it into an array of 16. So The first time going through the for loop of the C++ code, my j=1, i=1, it will skip the if and while statements, now in the second for loop, j=9, i=3, so the if statement will be true and data[9], data[3] will be swapped, data[9+1] and data[3+1] will be swapped. This is doing the bit reversal because index 3 and 4 has the real and imag number of the first input, and index 9 and 10 has the real and imag number of the fourth number.

As a result, 001 = 1 (fist input)

         100 = 4  (fourth input)

is swapped, so, this is doing the bit reversal using the indexes.

I don't really understand the while loop yet, but I know from @m69, that it is just a way of setting a sequence, so that it can do bit reversal. Well helpful my explanation on my own question is kind clear to people who has the same questions. Once again, thanks everyone.