轉載文章，文字說明部分修改文字錯誤、補充一些文字以及在程序中加一些注釋，原文網址：

http://www.xuebuyuan.com/2117668.html

程序部分是借鑒介紹FFT算法程序的文章《網上找的純C實現的FFT,與matlab計算結果完全一樣》，網址：

https://blog.csdn.net/cp1300/article/details/28850309

在實現FFT計算的時候，第一步要做的就是實現倒位序的實現，這里有一種算法，叫做雷德（Rader）算法。

自然序排列的二進制數，其下面一個數總比上面的數大1，而倒序二進制數的下面一個數是上面一個數在最高位加1并由高位向低位進位而得到的。?若已知某數的倒序數是J，求下一個倒序數，應先判斷J的最高位是否為0，與k=N/2進行比較即可得到結果：

i)如果J<k，說明最高位為0，應把其變成1，即J+N/2，這樣就得到倒序數了。

ii)如果J>=k，即J的最高位為1，將最高位化為0，即J-N/2；此時，需要再判斷次高位（即與k=N/4進行比較），若為0，將其變位1（即J+N/4），即得到倒序數；如果次高位為1，將其化為0（即J-N/4），再判斷下一位為0還是1，為0則變為1，得到倒序數；如果為1則變為0后繼續判斷下一位......直到判斷到某位為0或者判斷完全部的位數都為1才會結束判斷。

若倒序數大于順序數，進行換位，否則不變，防止重復交換，變回原數。

C代碼如下：

/*----以int型數據為例,假設數據長度N為2的整數次冪*----/
void Rader(int *f, int N)
{
int i,j,t,k;
/*----按照倒位序重新排列原信號----*/
for(i=1,j=N/2;i<=N-2;i++) ?// 第一個和最后一個數據是位置不變的，因此i=0和i=N-1不處理
{
if(i<j) ?// 原始下標小于變換下標才交換
{
t=f[j];
f[j]=f[i];
f[i]=t;
}
k=N/2; // 用于比較最高位
while(k<=j) ?// 位判斷為1
{
j=j-k; ?// 該位變為0
k=k/2; ?// 用于比較下一高位
}
j=j+k; ?// 判斷為0的位變為1
}
}

總結

以上是生活随笔為你收集整理的[转]FFT倒序算法—雷德算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。