matlab实现混合基fft算法,一种基于实时性处理的混合基fft方法

一种基于实时性处理的混合基fft方法

【专利摘要】本发明公开了一种基于实时性处理的混合基FFT方法，适用于FFT点数满足级数为s=s1+s2的情况。第一步根据实时性的要求，将输入数据分配到r2个存储器中，每个存储器深度为第二步，采用流水方法读取多个存储器，对r2个N′点进行DFT运算；在读取过程中，第n+1个存储器读取时序延后第n个存储器；第三步，采用并行方法对多个存储器读取，对N′个r2点进行DFT运算。本发明基于原位存储、输入数据顺序、单蝶形单元，且保证实时性的条件下，消除额外运算，针对多存储器采用流水和并行的访问方式，达到了实时性的设计要求。

【专利说明】一种基于实时性处理的混合基FFT方法

【技术领域】

[0001]本发明属于数字信号处理【技术领域】，涉及一种基于实时性处理的混合基FFT方法。

【背景技术】

[0002]随着数字信号处理技术和大规模集成电路的发展，FFT (快速傅里叶变换)算法的重要性不言而喻，广泛应用于各种科学工程领域，如雷达、声纳、通信等，同时对小型化和实时性等的要求越来越高。

[0003]计算FFT时，常用的算法是基-2FFT和基-4FFT，点数限制在2的幂次方或4的幂次方，这样限制了其点数的可选择范围。对于某些应用，比如SAR (合成孔径雷达)信号处理中，尤其是在聚束模式下，由于处理时间和面积的限制，不能将每个处理的点数都扩展至满足基-2或基-4FFT算法，尤其对于大点数的FFT，否则会延长计算时间以及消耗更多的存储空间。[0004]在各种各样的FFT处理器中，一般采用两种结构:流水结构和基于存储的结构。当对大点数进行处理时，流水结构比基于存储结构会占用更多的资源，导致面积和功耗增加。因此近些年来，针对大点数FFT的实现，基于存储结构得到越来越广泛的需求。而为了占用最少的存储资源，通常采用原位存储算法，该方法是将FFT蝶形单元的输出存储到与输入数据读取的地址一致的存储空间内。不过，原位存储结构处理时间长，实时性不高。为满足实时性的要求，通常会将输入数据分配到多个存储器中，这样可以同时对进入蝶形单元的数据进行读取/存储。

[0005]目前关于多存储器分配数据的方法常用的有以下三种:(I)采用多个取模操作对数据进行分配，该方法针对固定基FFT ; (2)采用一个取模操作对数据进行分配，该方法可用于混合基中；(3)采用异或门实现多存储的分配，该方法主要应用于基-2和基-4FFT中。这三种方法中都存在额外的运算，即取模或异或操作，都会消耗额外的资源，因此解决这一问题是必要的。

【发明内容】

[0006]本发明的目的是为了克服已有技术的缺陷，在基于原位存储、输入数据顺序、单蝶形单元(在本发明中由于是基-1Vr2FFT的形式，虽然有两个蝶形处理单元，即基I1和基_r2，但是可以将两个合并称为单碟形单元，是与多蝶形相对，多蝶形是指多个基I1和基_r2单元)，且保证实时性的条件下，提出一种混合基FFT方法，不需要限定FFT点数必须满足2或4的幂指数要求，无需取模/异或操作运算，达到实时处理的目的。

[0007]本发明是通过下述技术方案实现的:

[0008]该方法适用于FFT点数满足N = η'' X 、级数为s=s1+s2的情况；其中，1ι，r2分

别为两个不同的基，S1, S2为两个基分别对应的幂指数；设定；

[0009]步骤一、根据实时性的要求，将输入数据分配到多个存储器中；[0010]选定存储器的个数为m=r2，则每个存储器的存储深度为

【权利要求】

1.一种基于实时性处理的混合基FFT方法，其特征在于，该方法适用于FFT点数满足N = /f X if、级数为S=S1+S2的情况；其中，r1； r2分别为两个不同的基，S1, S2为两个基分别对应的幂指数；设定； 该方法包括如下步骤: 步骤一、对输入的数据序列x(n)进行存储器的分配:选定存储器的个数为m=r2，则每个存储器的存储深度为= r；1 x/f 4 ；将数据序列 的序号η分解为n = T2Xi^n2, ^n2表示存储器的编号,Ii1表示存储器的深度,然后对η个数据序列X (η)进行分配； 步骤二、采用流水方法读取多个存储器，对r2个N'点进行DFT运算:设r2个存储器依次用Mtl, M1,...M7..!来表示；按存储器编号依次从各存储器中按照原位计算的地址规律读出r'个操作数；其中，r' e (r1； r2);当前级做基_r2蝶形运算时，r' =r2,做基-!T1蝶形运算时，r' =A ;具体操作如下:(1)首先按照时钟周期，在每个时钟周期从Mtl读取一个操作数，共读取r'个；在从Mtl读取操作数的同时，在M0延迟一个时钟的情况下从M1开始读操作数，在M1延迟一个时钟的情况下从虬开始读操作数，以此类推，在延迟一个时钟的情况下从My1开始读操作数； (2)每当从同一个存储器读取的操作数凑齐r'个后，这r'个操作数后经第一缓存单元并行进入蝶形单元进行运算，得出r'个并行输出数据，再经第二缓存单元串行写入对应存储器的相应地址，从而完成每个存储器的第一级的第一个蝶形运算； (3)重复步骤(1)~(2)(N' /r' )_1次，每个存储器的N'点数据完成第一级剩下的(N' Ix' )-1次蝶形运算；在此过程中，Mtl的第二次蝶形处理的r'个操作数是在延迟一个时钟情况下获得的； (4)重复步骤(1)~(3)s-2次，则得到每个存储器的N'点FFT运算； 步骤三、采用并行方法对多个存储器读取，对N'个1*2点进行DFT运算: 每个时钟周期从r2个存储器的同一个地址读取一个操作数，共r2个，并行进入蝶形单元中进行基_r2的蝶形运算，共N,次；蝶形单元的并行输出数据按照原位存储方法并行存储到相应的存储器的相应地址中； 至此，整个N点FFT运算完成。

【文档编号】G06F12/02GK103544111SQ201310465130

【公开日】2014年1月29日 申请日期:2013年10月8日 优先权日:2013年10月8日

【发明者】陈禾, 马翠梅, 于文月, 谢宜壮, 龙腾 申请人:北京理工大学