fft中的码位倒置

zhaopeng161

在fft中有一个重要的环节：码位倒置。不知道有没有好的算法，请大家多多指教。

VibrationMaster

用汇编，可是现在不提倡了。

rockzone

C语言，VB都有FFT的程序。在网上下载一个就可以了。不复杂

zhaopeng161

我想在matlab中实现码位倒置，但是没有思路。要是按照原理那样先转化成二进制然后倒置，再转化为十进制的话就太麻烦点，有没有更好的算法。

花如月

只要肯找，方法总是会有:lol

VibrationMaster

1.MATLAB不支持位(bit)操作,因此纯用MATLAB比较难.
2.如果不是专门做这个工作的,现在没有必要深入研究这个问题.
3.在遥远的1990年,我在BASIC中结合汇编实现位操作的倒序,速度相差不大. 因为主要工作量还是在蝶型算法环节

[ 本帖最后由 eight 于 2007-11-4 10:03 编辑 ]

smartcho

matlab中有专门的码位倒读命令bitrevorder
例如：
A=[0 1 2 3]
[y,i]=bitrevorder(A)
y=0   2    1    3
i=1   2    3    4

VibrationMaster

bitrevorder这个函数最终是通过/2 /2 。。。来完成的。并非机器码意义上的倒置。

songzy41

我曾看到过一个码位倒置的函数，列于下面，楼主不妨试试。在MATLAB中关键数组下标从1开始，这给用MATLAB编写码位倒置增加了一点麻烦，像FORTRAN中，数组下标可从0开始，有很简单的码位倒置的方法。
function bit_reversal(x,N)
%倒序子程序
%
%变址运算
%
NV2=N/2;                      %  输入倒位序处理
NM1=N-1;
I=0;
J=0;
while I<NM1
    if I<J
        T=x(J+1);
        x(J+1)=x(I+1);
        x(I+1)=T;
    end
    K=NV2;
    while K<=J
        J=J-K;
        K=K/2;
    end
    J=J+K;
    I=I+1;
end

zhaopeng161

谢谢各位的回答，我自己编了一个倒读的程序如下
[m,n]=size(x);
clear x1

%=======================码位倒置==============
for j=1:(log2(n)-1)
    for k=1:2^(j-1)
        for g=1:n/(2^j)
            x1(g+(k-1)*n/(2^(j-1)))=x(2*g-1+(k-1)*n/2^(j-1));
            x1(g+(k-1)*n/(2^(j-1))+n/(2^j))=x(2*g+(k-1)*n/2^(j-1));
        end
    end
    x=x1;
end
x=x1;
clear x1
其中是输入量，但是我编制的时候只是考虑fft变换，x中的数据个数只能是2^n个。

zhaopeng161

原帖由 songzy41 于 2007-11-4 13:37 发表

                               
登录/注册后可看大图

我曾看到过一个码位倒置的函数，列于下面，楼主不妨试试。在MATLAB中关键数组下标从1开始，这给用MATLAB编写码位倒置增加了一点麻烦，像FORTRAN中，数组下标可从0开始，有很简单的码位倒置的方法。
function b ...

再次谢谢，我试了一下，有点不明白，N是什么参数？
比如我输入x=[1,2,3,4,5,6,7,8],经过‘码位倒置’我要求的输出应该是x=[1,5,3,7,2,6,4,8]
可是分别取参数N=1，2，4，8。输出都是x=[1,2,3,4,5,6,7,8]

smartcho

bitrevorder这个命令对于实现fft已经足够用了，还用得着自己编程序吗！在fft中只是用来颠倒输入向量的元素的位置，别的作用它一点都不起，你甭管这个函数是用什么编出来的，你想得越多就越容易钻牛角尖，把问题简单化最好，用不着舍近求远

zhaopeng161

原帖由 smartcho 于 2007-11-6 20:51 发表

                               
登录/注册后可看大图

bitrevorder这个命令对于实现fft已经足够用了，还用得着自己编程序吗！在fft中只是用来颠倒输入向量的元素的位置，别的作用它一点都不起，你甭管这个函数是用什么编出来的，你想得越多就越容易钻牛角尖，把问题 ...

谢谢，呵呵。你的观点我也同意，对于一些现成的东西我们拿来用就可以了。我就是想自己找一下规律，个人行为，见笑了。

zhaopeng161

有个问题，根据fft的原理（码位倒置，蝶形算法），它处理的数据个数应该是2*n个吧。可是matlab中的fft函数可以求取的数据个数是任意个，不明白为什么，望大虾们指教。

VibrationMaster

这个相当的复杂, MATLAB实际上对不同长度采用不同策略,基本上就是组合小质数.   
搜索网上FFTW算法,你就会停止考虑这个问题了.