分享程序员开发的那些事...
更新时间：2023-12-02 15:57:16
一个位反转算法创建一个数据通过反转每个项目的二进制地址设置的一个排列;所以如在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 3 13 11 7 15
在什么伪code 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 3 13 11 7 15 结果
与每个序列由2 previous版本相乘，然后用1重复它使加入。或者看它的另一种方式：通过重复previous序列，值+ 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 3 13 11 7 15
项i和j然后在for循环的每次迭代交换，但只有当I＆下;焦耳;否则每个项目将被交换到了新的地方（例如，当i = 3和j = 12），然后再回来（当i = 12和J = 3）。
函数bitReversal（数据）{\r
变种N = data.length;\r
变种J = 0;\r
对于（i = 0; I＆LT; N - 1;我++）{\r
VAR K = N / 2;\r
如果（ⅰ＆所述; j）条{\r
变种临时=数据[I]数据[I] =数据[J]。数据[J] =温度;\r
}\r
而（K＆LT; = j）条{\r
的J - = K;\r
K / = 2;\r
}\r
J + = K;\r
}\r
返回（数据）;\r
}\r
\r
的console.log（bitReversal（[0,1]））;\r
的console.log（bitReversal（[0,1,2,3]））;\r
的console.log（bitReversal（[0,1,2,3,4,5,6,7]））;\r
的console.log（bitReversal（[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]））;\r
console.log(bitReversal([\"a\",\"b\",\"c\",\"d\",\"e\",\"f\",\"g\",\"h\",\"i\",\"j\",\"k\",\"l\",\"m\",\"n\",\"o\",\"p\"]));$c$c>$p$p>\r
C ++的code你发现出现过它的双步骤使用序列的对称性循环。它不会产生虽然正确的结果，所以无论它是一个失败的尝试，或者它的设计做不同的事情完全。下面是一个使用两步想法版本：
函数bitReversal2（数据）{\r
变种N = data.length;\r
变种J = 0;\r
对于（i = 0; I＆LT; N，I + = 2）{\r
如果（ⅰ＆所述; j）条{\r
变种临时=数据[I]数据[I] =数据[J]。数据[J] =温度;\r
}\r
其他{\r
变种临时=数据[N-1 - 我]数据[N-1 - 我] =数据[N-1 - J]。数据[N-1 - J] =温度;\r
}\r
VAR K = N / 4;\r
而（K＆LT; = j）条{\r
的J - = K;\r
K / = 2;\r
}\r
J + = K;\r
}\r
返回（数据）;\r
}\r
\r
的console.log（bitReversal2（[0,1]））;\r
的console.log（bitReversal2（[0,1,2,3]））;\r
的console.log（bitReversal2（[0,1,2,3,4,5,6,7]））;\r
的console.log（bitReversal2（[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]））;\r
console.log(bitReversal2([\"a\",\"b\",\"c\",\"d\",\"e\",\"f\",\"g\",\"h\",\"i\",\"j\",\"k\",\"l\",\"m\",\"n\",\"o\",\"p\"]));$c$c>$p$p>\r
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)
*/
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
becomes0 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:00 10 2 1 30 4 2 6 1 5 3 70 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"]));