雷德算法
程序员文章站
2022-10-19 22:03:09
对数据进行快速傅里叶变换后,输出数据是倒位序的。因此,我们可以在对数据进行快速傅里叶变换之前,先用雷德算法,把原始数据变为倒位序的。这样,再对数据进行快速傅里叶变换,输出数据就是自...
对数据进行快速傅里叶变换后,输出数据是倒位序的。因此,我们可以在对数据进行快速傅里叶变换之前,先用雷德算法,把原始数据变为倒位序的。这样,再对数据进行快速傅里叶变换,输出数据就是自然顺序的。
雷德算法:自然顺序排列的二进制数,其下面一个数总比上面的数大1,而倒序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位进位而得到的。
J都是从0开始,若已知某个倒位序数J,要求下一个倒位序数,则应先判断J的最高位是否为0,这可与k=N/2相比较,因为N/2总是等于1000……的。如果K>J,则J的最高位为0,只要把该位变为1(J与K=N/2相加即可),就得到下一个倒位序数;如果K<=J,则J的最高位为1,可将最高位变为0(J与K=N/2相减即可)。然后还需判断次高位,这可与K=N/4相比较,若次高位为0,则需将它变为1(加K=N/4即可),其他位不变,即得到下一个倒位序数;若次高位是1,则需将它也变为0。然后再判断下一位。
举例说明,当N= 8时:
倒位序 ——————–顺序
0(000)———– 0(000)
4(100)———– 1(001)
2(010)———– 2(010)
6(110)———– 3(011)
1(001)———– 4(100)
5(101)———– 5(101)
3(011)———– 6(110)
7(111)————7(111)
代码如下:
#include <iostream> #include <cstdio> using namespace std; int x[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; int y[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; int N = 8; int main() { int i,j,k; int temp; for(j=0,i=0;i<N-1;i++) //这里实现了奇偶前后分开排序 { if(i<j) //如果i<j,即进行变址 { temp = x[j]; x[j] = x[i]; x[i] = temp; } k = N/2; //求j的下一个倒位序 while(j >= k) //如果k<=j,表示j的最高位为1 { j = j-k; //把最高位变成0 k = k/2; //k/2,比较次高位,依次类推,逐个比较,直到某个位为0 } j = j+k; //更新j } for(i = 0 ; i < N ; ++ i) { printf("%2d %2d\n" , i , x[i]) ; } return 0 ; }
上一篇: 三国中诸葛瑾有哪些经历?他是个怎样的人?
下一篇: 朱武的绰号是怎么来的?为何叫神机军师?