雷德（Rader）算法

科技前沿 • 2025-03-07 16:40 • 阅读 52

大家好，我是讯享网，很高兴认识大家。

记录一个菜逼的成长。。

解释与图转自：http://m.blog.csdn.net/article/details?id=
在实现FFT(快速Fourier变换)计算的时候，第一步要做的就是实现码位(二进制码)倒序，这里有一种算法，叫做雷德（Rader）算法。
废话少说，请看下面0-7的顺序排列与倒序排列：
这里写图片描述
讯享网
由上面的表可以看出，按自然顺序排列的二进制数，其下面一个数总是比其上面一个数大1，即下面一个数是上面一个数在最低位加1并向高位进位而得到的。而倒位序二进制数的下面一个数是上面一个数在最高位加1并由高位向低位进位而得到。
若已知某个倒位序J(0是已知的嘛)，要求下一个倒位序数：
首先判断J的最高位是否为0，这可与k=N/2相比较，因为N/2总是等于100..的。

 如果k>J，则J的最高位为0，只要把该位变为1（J与k=N/2相加即可），就得到下一个倒位序数； 如果K<=J，则J的最高位为1，可将最高位变为0（J与k=N/2相减即可）。 然后(k<=J时)还需判断次高位，这可与k=N\4相比较，若次高位为0，则需将它变为1（加N\4即可）其他位不变，既得到下一个倒位序数；若次高位是1，则需将它也变为0。然后再判断下一位。。。。(以此循环)

讯享网

讯享网///求num的下一个二进制码倒序数 ///len必须是2^n形式 int Rader(int num,int len) { int k = len >> 1; while(num >= k){ num -= k; k >>= 1; } if(num < k)num += k; return num; }

如果要把一个数组按二进制的倒序排列
即把一个数组
a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7]
变成
a[0],a[4],a[2],a[6],a[1],a[5],a[3],a[7]
运用在FFT中的就是以下形式

void Rader(type F[],int len) { for( int i = 1,j = len >> 1; i < len-1; i++ ){ if(i < j)swap(F[i],F[j]); int k = len >> 1; while(j >= k){ j -= k; k >>= 1; } if(j < k)j += k; } }

雷德（Rader）算法

相关推荐