一种码位倒置算法

最近在复习FT（Fourier Transform）相关的知识，当然是要好好复习一下FFT（Fast Fourier Transform）算法啦。FFT这个伟大的算法是JW Cooley & JW Tukey在1965年提出的。 他们的论文“机器计算Fourier series的一种算法”发表在<<Mathematics of computation>> ，成为DSP发展史上的里程碑。关于FT和FFT算法相关的理论资料是很容易找到的，这里就不在复述啦。这里我想提一提“码位倒置”算法。码为倒置算法作为FFT算法的一部分，它的出现为FFT这个本来就很巧妙的算法更添一份神奇，是的冥冥之中码为倒置算法就应该出现在FFT中，这或许就是所谓的真理！

先简单的描述一下码位倒置算法：

尽管有很多高效简单的码位倒置算法，但它们理解起来都比较困难，针对这种情况，提出一种“循环移位”的码为倒置算法，该算法直观容易理解，而且也同样高效。算法代码如下：

/*void bitreverse(int a[],int N)

a[]为要改变位置的数字，N为数组a的长度，N = 2^L

*/

void bitreverse(int a[],int N){

//计算数组长度N的二进制站位数，即L，保存到bitsn中

int n = N-1;

int bitsn = 0;

while(n != 0){

n = n>>1;

bitsn++;

}

//码位倒置，最多交换N/2次

for(int i = 0; i < N/2; i++{

int num = bitsn; /*循环位移次数，bitsn次

int pos = i; /*当前待交换位置*/

int des = 0; /*目的交换位置*/

//循环移位

while(num > 0){

int temp = pos;

pos = pos>>1; /*当前待交换位置向右移出一位*/

des = des<<1; /*目的位置左移一位，虚以待位*/

des += temp - (pos<<1); /*将pos移出的位加到pos上*/

num--;

}

//如果des和i相等则交换

if(des != i){

int t = a[i];

a[i] = a[des];

a[des] = t;

}

}

}

下面是另一种方法的流程图：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!