CN103810146B

CN103810146B - 一种逆序输入顺序输出的fft结构设计方法

Info

Publication number: CN103810146B
Application number: CN201410038950.3A
Authority: CN
Inventors: 陈禾; 杨晨; 谢宜壮; 于文月; 陈亮; 龙腾
Original assignee: Beijing Institute of Technology BIT
Current assignee: Beijing Institute of Technology BIT
Priority date: 2014-01-26
Filing date: 2014-01-26
Publication date: 2017-01-11
Anticipated expiration: 2034-01-26
Also published as: CN103810146A

Abstract

本发明提出一种逆序输入顺序输出的FFT结构设计方法，解决了脉冲压缩系统中传统FFT结构带来的额外存储需求和流水迟滞问题。步骤一、设计FFT结构中的蝶形运算单元,该蝶形运算单元包括两个输入、两个输出、加法器、减法器和实虚部交换单元，两个输出为两个输入数据通过蝶形运算单元中的加法器和减法器运算得到的和结果和差结果，当需要做结果数据乘以虚单位‑j的操作时，通过实虚部交换单元交换结果数据的实虚部实现；步骤二、对输入数据和输出数据的地址重新进行二维分解，推导DIT结构的FFT计算模型，利用二维分解得到的系数组设计信号流图；步骤三、将步骤二中的信号流图进行硬件实现，完成FFT结构设计。

Description

一种逆序输入顺序输出的FFT结构设计方法

技术领域

本发明属于数字信号处理技术领域，涉及一种逆序输入顺序输出的FFT结构设计方法。

背景技术

随着大规模集成电路和数字信号处理技术的发展，FFT算法具有不可替代的作用，广泛应用于雷达、声纳、通信等领域。无论是现在大部分雷达体制中所采用的脉冲压缩体制，还是通信领域中的匹配滤波最大信噪比准则，都涉及到时域信号通过FFT得到频谱，频域进行处理，再通过IFFT（逆快速傅里叶变换）回到时域。这一信号处理过程对FFT的实时性、存储资源消耗、流水迟滞都有较高要求，需要专门设计相应优化的FFT结构。

在脉冲压缩处理过程中，典型的处理过程是时域信号经过FFT处理得到频域信号，在频域与相应的因子相乘，得到的数据再经过IFFT处理得到时域信号，这个过程在雷达系统接收信号脉冲压缩、SAR成像处理算法、通信系统接收信号匹配滤波中都被频繁使用，其中重要的问题是典型的DIF（频域抽取）FFT处理过程数据顺序输入，结果逆序输出，用这种结构进行IFFT时，输入数据之前要对数据进行缓存，调整顺序的处理，这不仅占用大量存储空间（比大部分流水结构FFT处理过程需要的全部的存储还要多），而且加大了流水处理延时，既提高了系统对存储资源的需求，又降低了系统实时性。

发明内容

本发明的目的是为了克服已有技术的缺陷，解决了脉冲压缩系统中传统FFT结构带来的额外存储需求和流水迟滞问题，提出一种逆序输入顺序输出的FFT结构设计方法，同时该结构在实现时对旋转因子数据的存储做了优化，进一步节省了存储资源。

为了解决上述技术问题，其基本实施过程如下：

一种逆序输入顺序输出的FFT结构设计方法，包括如下步骤：

步骤一、设计FFT结构中的蝶形运算单元,该蝶形运算单元包括两个输入、两个输出、加法器、减法器和实虚部交换单元，两个输出为两个输入数据通过蝶形运算单元中的加法器和减法器运算得到的和结果和差结果，当需要做结果数据乘以虚单位-j的操作时，通过实虚部交换单元交换结果数据的实虚部实现；

步骤二、对输入数据和输出数据的地址重新进行二维分解，推导DIT结构的FFT计算模型，利用二维分解得到的系数组设计信号流图；

步骤三、将步骤二中的信号流图进行硬件实现，完成FFT结构设计。

在步骤三之后，利用旋转因子的对称性,仅存储点数的旋转因子到ROM中，然后通过地址控制产生剩余点数的旋转因子，对前的正弦波数据进行关于自身对称轴的翻转、关于横轴的正负翻转得到完整的正弦波波形数据，存储点数的旋转因子到ROM中来进行存储的优化。

步骤三中采用单路延时反馈结构实现信号流图。

本发明的有益效果：

本发明提出的一种逆序输入顺序输出的FFT结构设计方法本身结合了基2蝶形和基4蝶形的优点，采用单路延迟反馈的流水处理结构能够提高处理的实时性，并且逆序输入顺序输出可以省去调整输出顺序的缓存存储以及调整输出顺序所需的流水延迟，从而进一步降低流水迟滞、减少存储需求。在一个脉冲压缩处理过程中，现有的频率抽取FFT结构进行FFT处理，结合本发明的时间抽取FFT结构进行IFFT处理，可以有效降低存储，提高实时性。本发明对比已有技术，无论采取定点实现还是浮点实现，都能够在保持精度下，在实现中降低资源消耗和流水迟滞，从而减少存储资源的占用(本发明中还利用旋转因子对称性进一步降低了对存储资源的需求)，提高处理流程的实时性，在资源和性能两方面同时获得提升。

附图说明

图1为R2²SDF DIT FFT的蝶形单元；

图2为计算某一输出数据的信号流图；

图3为图2的电路结构框图。

图4为旋转因子对称性。

具体实施方式

下面结合附图对本发明方法的实施方式做详细说明。

一种逆序输入顺序输出的FFT结构设计的方法，其具体步骤包括：

步骤一、设计基本运算单元：图1所示为一个R2²SDF DIT结构的四点FFT蝶形单元，它主要由两级2点蝶形单元组成，所谓的蝶形单元包含两个输入、两个输出、加法器、减法器、实虚部交换单元（乘虚单位-j）。两个输入经过加法器运算得到的结果作为一个输出，经过减法器得到的结果作为另一个输出，当结果乘以虚单位-j时，利用简单的数据实虚部交换即可完成。按照图1的结构设计蝶形单元，作为FFT结构中最基本的运算单元。

步骤二、设计信号流图：根据R2²SDF算法的原理，对输入信号的地址n进行二维分解：

n = n_{1} + 2 n_{2} + 4 n_{3}, n_{1} = 0,1, n_{2} = 0,1, n_{3} = 0,1, . . ., \frac{N}{4} - 1,

同时对相应的输出信号地址也进行二维分解：

k = \frac{N}{2} k_{1} + \frac{N}{4} k_{2} + k_{3}, k_{1} = 0,1, k_{2} = 0,1, k_{3} = 0,1, . . ., \frac{N}{4} - 1,

最终得到

X (k) = Σ_{n_{3} = 0}^{\frac{N}{4} - 1} {[x (4 n_{3}) + x ({4 n}_{3} + 2) {(- 1)}^{k_{2}} W_{N}^{{2 k}_{3}}] + {(- 1)}^{k_{1}} {(- j)}^{k_{2}} [x (4 n_{3} + 1) + x ({4 n}_{3} + 3) {(- 1)}^{k_{2}} W_{N}^{{2 k}_{3}}] W_{N}^{k_{3}}} W_{\frac{N}{4}}^{n_{3} k_{3}}

算法的原理就是反复递归进行点数的FFT，其中对于输出地址为k的某个输出数据，它是由输入数据逐级通过蝶形运算和乘法运算得到的。图2所示为1个16点DIT结构FFT，以图中所示的计算X(0)和X(11)两个结果的信号流图为例，通过两级共四列蝶形得到最终输出结果。输出信号的地址k值确定后，可以按照上面的地址分解方法得到一组唯一的系数组（k₁,k₂,k₃），信号的流向就由（k₁,k₂,k₃）这组值决定，由上面公式可以看出每一级的第一列蝶形运算单元进行加法运算还是减法运算是由k₂控制的，每一级的第二列蝶形运算单元进行加法运算还是减法运算是由k₁控制的，是否进行实虚部交换（即乘以-j）由k₂控制，最终每一级计算结果要乘旋转因子旋转因子的数值由点数N和k₃决定，具体数值可以由对存储着旋转因子数值的ROM寻址得到。图2所示的X(0)和X(11)就是由相应的（k₁,k₂,k₃）系数逐级经过加法器、减法器、乘法器等运算最终得到的输出，所以针对每个输出数据，按照地址的二维分解方式，得出其相应的系数（k₁,k₂,k₃）就可以确定为了得到此输出的输入信号流向。按照上述方式进行的地址的二维分解使得运算具有逆序输入顺序输出的特点，按照图2所示的信号流图逐级调用步骤一中的蝶形单元就可以实现DIT结构的FFT运算，得到每一个相应k值对应的输出数据X(k)。

步骤三、设计具体的硬件实现结构：为了保证FFT运算的实时性，应采取流水结构实现，图3所示为一个256点的流水结构DIT FFT，采用单路延迟反馈结构，具体如图所示，从数据输入到数据输出只有一条通路，BFI和BFII分别代表图2中每一级的两列蝶形运算单元，每一列蝶形中的减法器的输出结果暂时缓存到RAM中，加法器的运算结果则传递到下一级继续进行运算，第一级第一列数据流水进入时，只需要缓存1个数据就可以开始运算，并在缓存数据读出后将其参与减法运算得到的差结果存入已经清空的缓存中，参与加法运算的和结果传到下一级；第二列数据流水进入时，需要缓存2个数据才可以开始运算，并在第一个缓存数据读出进行运算后将其参与减法运算得到的差结果存入缓存中的第一个空位，参与加法运算的和结果传到下一级,在第二个缓存数据读出后将其参与减法运算得到的差结果存入缓存中的第二个空位,参与加法运算的和结果传到下一级；以此类推，每一列运算需要的缓存按照1、2、4、8…（2的幂次）递增，这种缓存形成了一种反馈结构，按照这种反馈缓存的方式安排存储节点和运算单元，可以实现全程流水的数据运算。

由于每一级运算结果都要与相应的旋转因子相乘，旋转因子（即正弦波数据）数据存储在ROM中，为了进一步节省存储资源，可以利用如图4所示的旋转因子（即正余弦函数）的对称性，仅存储点数的旋转因子到ROM中，然后通过地址控制产生剩余点数的旋转因子，正弦波对称性如图4中所示，对前的正弦波数据进行关于自身对称轴的翻转、关于横轴的正负翻转可以得到完整的正弦波波形数据，所以存储点数的旋转因子到ROM中来进行存储的优化。

结合步骤一中的基本蝶形运算单元、步骤二中设计的地址映射方式、步骤三设计的电路结构以及对存储进行的优化，实现本发明所述的逆序输入顺序输出的FFT结构。

Claims

1.一种逆序输入顺序输出的FFT结构设计方法，其特征在于，包括如下步骤：

步骤三、将步骤二中的信号流图进行硬件实现，完成FFT结构设计；

2.如权利要求1所述的一种逆序输入顺序输出的FFT结构设计方法，其特征在于，步骤三中采用单路延时反馈结构实现信号流图。