雷德算法

對數據進行快速傅裡葉變換後，輸出數據是倒位序的。因此，我們可以在對數據進行快速傅裡葉變換之前，先用雷德算法，把原始數據變為倒位序的。這樣，再對數據進行快速傅裡葉變換，輸出數據就是自然順序的。

雷德算法：自然順序排列的二進制數，其下面一個數總比上面的數大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 ;  
}