fft变址算法实现

作者在 2010-05-28 21:17:50 发布以下内容
#include <iostream>
#include <bitset>
using namespace std;

#define  M  4
#define  N (1<<M)


/*基2变址运算*/
void switchadr2(int x[],int len)
{
    int temp;
    int i,j,k;
    for(j=0,i=0;i<len-1;i++)
    {
        if(i<j)
        {
            temp=x[j]; x[j]=x[i]; x[i]=temp ; // printf("%d<-->%d\n",i,j);
        }
        k=len/2 ;
        while(k<(j+1)&&(j>0))
        {
            j=j-k ; k=k/2 ;
        }
        j=j+k ;
    }
}

/*基4变址运算*/
void switchadr4(int x[],int len)
{
    int temp;
    int i,j,k;
    for(j=0,i=0;i<len-1;i++)
    {
        if(i<j&&j<len)
        {
            temp=x[j]; x[j]=x[i]; x[i]=temp ; // printf("%d<-->%d\n",i,j);
        }
        k=len/2 ;
        while( (len/2-1)*k<(j+1)&&(j>0))
        {
            j=j-(len/2-1)*k ; k=1 ;
        }
        j=j+k ;
    }
}

int main()
{
    int a[N],b[N];
    int i ;

    for (i=0;i<N;i++) a[i] = i;
    for (i=0;i<N/2;i++) { b[i] = 2*i;b[N/2+i] = 2*i+1;}
    

    for (i=0;i<N;i++) cout<<bitset<M>(b[i])<<"\t";
    
    cout<<"\n";
    switchadr4(a,N);
    for (i=0;i<N;i++) cout<<bitset<M>(a[i])<<"\t";

    getchar();
    return 0;
}
算法 | 阅读 2178 次
文章评论,共0条
游客请输入验证码
浏览1936645次