CN102810086A - 快速傅立叶变换蝶型运算处理装置及数据处理方法 - Google Patents

Abstract

本发明公开了快速傅里叶变换蝶形运算处理装置及方法，包括：实数加法器模块、延迟及常数乘法器模块、实数乘法器模块、实数加法器及延迟控制模块。本发明实施例公开的快速傅里叶变换蝶形运算处理装置，采用实数乘法器、实数加法器和延迟及常数乘法器的组合，完成快速傅立叶变换蝶型单元的一条分支运算，由于采用了流水线设计结构思想，因此设计出的硬件具有时序紧凑，资源利用率高，速度快、扩展灵活等优点，并且可以应用在基2、基4或基8的运算场合。

Description

快速傅立叶变换蝶型运算处理装置及数据处理方法

技术领域

本发明涉及通信技术领域，尤其涉及快速傅里叶变换蝶形运算处理装置及应用于该装置的数据处理方法。

背景技术

快速傅立叶变换是离散傅立叶变换的一种快速高效的实现形式，并广泛的应用于各种系统中，如宽带多载波通信系统，雷达信号处理系统，信号检测与估计系统等。该技术充分利用了傅立叶变换旋转因子的周期性和对称性，从而大幅度的降低了离散傅立叶变换的计算复杂度和实现成本，因此受到人们的广泛关注。

长期以来，人们对快速傅立叶变换进行了广泛而深入的研究，主要集中在算法和架构设计上。蝶型单元，作为快速傅立叶变换的引擎，其运算速度直接决定快速傅里叶变换的速度，因此，人们对于高效的蝶形单元的需求越来越迫切。

发明内容

有鉴于此，本发明提供一种快速傅里叶变换蝶形运算处理装置及应用于该装置的数据处理方法，其具体方案如下所示：

一种快速傅里叶变换蝶形运算处理装置，包括：

实数加法器模块，用于依据预先设定的处理原则，将待处理数据的实部和虚部相加；

延迟及常数乘法器模块，用于当预先设定的基数为8时，对所述相加的结果进行延迟或加乘处理，当预先设定的基数为2或4时，对所述相加得到的结果不做处理；

实数乘法器模块，用于将所述延迟及常数乘法器模块中得到的结果的实部和虚部分别与旋转因子的实部和虚部相乘；

实数加法器及延迟控制模块，用于根据所述预先设定的处理原则，将与所述旋转因子相乘后得到的乘积进行相加，得到处理结果。

优选的，当所述预先设定的处理原则为在两个周期内完成所述处理过程时，当预先设定的基数为2时，所述实数加法器模块包括至少1个加法器，当预先设定的基数为4时，所述实数加法器模块包括至少3个加法器，当预先设定的基数为8时，所述实数加法器模块包括至少6个加法器；

当所述预先设定的处理原则为在一个周期内完成所述处理过程时，当预先设定的基数为2时，所述实数加法器模块包括至少2个加法器，当预先设定的基数为4时，所述实数加法器模块包括至少6个加法器，当预先设定的基数为8时，所述实数加法器模块包括至少12个加法器。

优选的，当所述预先设定的处理原则为在两个周期内完成所述处理过程时，所述实数加法器及延迟控制模块包括：相加单元和延迟控制单元；

当所述预先设定的处理原则为在一个周期内完成所述处理过程时，所述实数加法器及延迟控制模块包括：相加单元。

一种数据处理方法，包括：

步骤a、依据预先设定的处理原则，将待处理数据的实部和虚部相加；

步骤b、当预先设定的基数为8时，对所述相加的结果进行延迟或加乘处理，当预先设定的基数为2或4时，对所述相加得到的结果不做处理；

步骤c、将步骤b中得到的结果的实部和虚部分别与旋转因子的实部和虚部相乘；

步骤d、根据预先设定的处理原则，将与所述旋转因子相乘后得到的乘积进行相加，得到处理结果。

优选的，所述依据预先设定的处理原则，将待处理数据的实部和虚部相加的过程包括：

当预先设定的处理原则为在两个周期内完成所述处理过程时，当预先设定的基数为2时，利用1个加法器将所述待处理数据的实部和虚部分别进行顺序相加，当预先设定的基数为4时，利用3个加法器将所述待处理数据的实部和虚部分别进行顺序相加，当预先设定的基数为8时，利用6个加法器将所述待处理数据的实部和虚部分别进行顺序相加；

当预先设定的处理原则为在一个周期内完成所述处理过程时，当预先设定的基数为2时，利用2个加法器，分别将所述待处理数据的实部和虚部进行并行相加，当预先设定的基数为4时，利用6个加法器，分别将所述待处理数据的实部和虚部进行并行相加，当预先设定的基数为8时，利用12个加法器，分别将所述待处理数据的实部和虚部进行并行相加。

优选的，当预先设定的基数为8时，对所述相加的结果进行延迟或加乘处理的过程包括：

将所述相加的结果与常数乘法项

相乘，获得其相乘的结果。

优选的，当所述预先设定的处理原则为：在两个周期内完成所述处理过程时，将与所述旋转因子相乘后得到的乘积进行相加的过程包括：

将与所述旋转因子相乘后得到的乘积进行延迟控制后，再相加；

当所述预先设定的处理原则为：在一个周期内完成所述处理过程时，将与所述旋转因子相乘后得到的乘积进行相加的过程包括：

将与所述旋转因子相乘后得到的乘积进行直接相加。

从上述的技术方案可以看出，本发明实施例公开的快速傅里叶变换蝶形运算处理装置，采用实数乘法器、实数加法器和延迟及常数乘法器的组合，完成快速傅立叶变换蝶型单元的一条分支运算，由于采用了流水线设计结构思想，因此设计出的硬件具有时序紧凑，资源利用率高，速度快、扩展灵活等优点，并且可以应用在基2、基4或基8的运算场合。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例公开的快速傅里叶变换蝶形运算处理装置的结构示意图；

图2为本发明实施例公开的快速傅里叶变换蝶形单元的结构示意图；

图3为本发明实施例公开的又一快速傅里叶变换蝶形运算处理装置的结构示意图；

图4为本发明实施例公开的变长快速傅立叶变换单元的框架结构示意图；

图5为本发明实施例公开的数据处理方法的流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明实施例公开了一种快速傅里叶变换蝶形运算处理装置，其结构如图1所示，包括：实数加法器模块11、延迟及常数乘法器模块12、实数乘法器模块13和实数加法器及延迟控制模块14，其中：

实数加法器模块11用于依据预先设定的处理原则，将待处理数据的实部和虚部相加。假设G_r、G_i为输入数据实、虚部相加的结果，N为输入数据的个数，I_nr、I_ni为输入数据的实、虚部，则按照下述公式进行相加：

$G_r=\underset{n=0}{\overset{N-1}{\mathrm{\Σ}}}{I}_{\mathrm{nr}}$ 公式(1)

$G_i=\underset{n=0}{\overset{N-1}{\mathrm{\Σ}}}{I}_{\mathrm{ni}}$ 公式(2)

上述预先设定的处理原则为，在一个周期内完成上述处理过程，或者在两个周期内完成上述处理过程。

假设预先设定的处理原则为在两个周期内完成上述处理过程，当预先设定的基数为2时，所述实数加法器模块11包括至少1个加法器，当预先设定的基数为4时，所述实数加法器模块11包括至少3个加法器，当预先设定的基数为8时，所述实数加法器模块11包括至少6个加法器。假设预先设定的处理原则为在一个周期内完成上述处理过程，当预先设定的基数为2时，所述实数加法器模块11包括至少2个加法器，当预先设定的基数为4时，所述实数加法器模块11包括至少6个加法器，当预先设定的基数为8时，所述实数加法器模块11包括至少12个加法器。

当然，本实施例中的实数加法器模块可以设置至少12个加法器，然后根据不同的处理原则和不同的基数从中选择处理过程中需要用到的加法器，以进行处理。

延迟及常数乘法器模块12用于当预先设定的基数为8时，对所述相加的结果进行延迟或加乘处理，当预先设定的基数为2或4时，对所述相加得到的结果不做处理，本实施例中的常数乘法项为

实数乘法器模块13用于将所述延迟及常数乘法器模块12中得到的结果的实部和虚部分别与旋转因子的实部和虚部相乘。假设旋转因子的实、虚部分别为R_r、R_i，与上述延迟及常数乘法器模块12中得到的结果的实部和虚部分别进行相乘的过程如下所示：

H_rr＝G_r·R_r    公式(3)

H_ri＝G_r·R_i    公式(4)

H_ir＝G_i·R_r    公式(5)

H_ii＝G_i·R_i    公式(6)

其中，H_rr为结果的实部G_r和旋转因子的实部R_r的相乘结果，H_ri为结果的实部G_r与旋转因子的虚部R_i相乘的结果，H_ir为结果的虚部G_i和旋转因子的实部R_r的相乘结果，H_ii结果的实部G_i与旋转因子的虚部R_i相乘的结果。

实数加法器及延迟控制模块14用于根据所述预先设定的处理原则，将与所述旋转因子相乘后得到的乘积进行相加，得到处理结果。实数加法器及延迟控制模块14对实数乘法器模块送至的数据进行处理，得到期望的结果RB_r、RB_i：

RB_r＝H_rr-H_ii    公式(7)

RB_i＝H_ri+H_ir    公式(8)

$\mathrm{RB}={\mathrm{RB}}_r+{\mathrm{jRB}}_i,(j=\sqrt{-1})$ 公式(9)

其中，RB为依据本实施例公开的快速傅里叶变换蝶形运算处理装置进行处理后得到的计算结果。

进一步的，当所述预先设定的处理原则为在两个周期内完成所述处理过程时，所述实数加法器及延迟控制模块14包括：相加单元141和延迟控制单元142，以实现对实数乘法器模块送至的数据进行延迟控制相加。

当所述预先设定的处理原则为在一个周期内完成所述处理过程时，所述实数加法器及延迟控制模块仅包括：相加单元141。或者同时包括上述延迟控制单元142，但是对其做直通处理，不进行任何操作。

本实施例公开的快速傅里叶变换蝶形运算处理装置，采用实数乘法器、实数加法器和延迟及常数乘法器的组合，完成快速傅立叶变换蝶型单元的一条分支运算，由于采用了流水线设计结构思想，因此设计出的硬件具有时序紧凑，资源利用率高，速度快、扩展灵活等优点，并且可以应用在基2、基4或基8的运算场合。

进一步的，本发明实施例公开了当预设基数为8时，快速傅里叶变换蝶形单元的结构，如图2所示，包括：数据缓冲单元21、数据配置单元22及快速傅里叶变换蝶形运算处理装置23，其中：

数据缓冲单元21负责将待处理数据进行缓冲处理，配合数据配置单元22的配置速率；数据配置单元22则负责根据快速傅里叶变换蝶形运算处理装置23的电路形式以及本次运算所需得到的中间数据对缓冲数据进行选择和调整；快速傅里叶变换蝶形运算处理装置23则根据配置单元22送入的数据及选择器控制信息对数据进行计算处理。

进一步的，快速傅里叶变换蝶形运算处理装置23的结构如图3所示，包括：实数加法器模块31、延迟及常数乘法器模块32、实数乘法器模块33和实数加法器及延迟控制模块34。

本实施例中的实数加法器模块31包括12个加法器，其中8个加法器分别实现对数据配置单元22送来的8个复数实部和虚部的相加，具体为x_{1_r}和x_{2_r}，x_{3_r}和x_{4_r}，x_{1_I}和x_{2_i}，x_{3_i}和x_{4_i}，x_{5_r}和x_{6_r}，x_{7_r}和x_{8_r}，x_{5_i}和x_{6_i}，以及x_{7_i}和x_{8_i}相加，然后利用剩余4个加法器对上述相加的结果再进行相加，分别得到前四个复数和后四个复数的实部和虚部的和。在延迟及常数乘法器模块32中，根据基8运算的公式可知，计算前4个处理结果时不需要与旋转因子相乘。其中旋转因子表示为Wnr(k，N)，即基数为N的第k个旋转因子，当N＝8时，旋转因子包括：Wnr(0，8)、Wnr(1，8)、Wnr(2，8)或Wnr(3，8)，而后4个处理结果均需要分别与Wnr(0，8)、Wnr(1，8)、Wnr(2，8)或Wnr(3，8)进行乘法运算。根据旋转因子的特点，Wnr(0，8)和Wnr(2，8)的结果分别是1和sqrt(-1)，无需真正意义的乘法运算，只有Wnr(1，8)和Wnr(3，8)两项需要与常数乘法项

相乘。因此，在计算基8运算的前4个运算结果时，第一选择器MUX1和第二选择器MUX2均选择如图中箭头所指的左边的输入结果，即无加乘运算的延迟结果；在计算基8运算的后4个运算结果时，与Wnr(1，8)和Wnr(3，8)相乘运算时第一选择器MUX1和第二选择器MUX2均选择如图中箭头所指的右边的输入结果，即有加乘运算的处理结果；与Wnr(0，8)和Wnr(2，8)相乘运算时，第一选择器MUX1和第二选择器MUX2仍然选择如图中箭头所指的左边的输入结果，即无加乘运算的延迟结果。第三选择器MUX3和第四选择器MUX4的两个输入数据的差别在于相乘之前进行的是加法运算还是减法运算。减法运算通过反相器实现，其选择需根据基8蝶形运算的具体特点，即在计算第5和第6个结果时选择减法分支，而第7和第8个结果时选择加法分支。

延迟及常数乘法器模块32的处理结果送至实数乘法器模块33中，根据当前FFT运算到第几级来选择与该级对应的旋转因子，然后相乘，相乘结果经实数加法器及延迟控制模块34后得到基8运算的实虚部结果。

本实施例并不限定按照上述流程利用图3中所示电路结构进行蝶形运算，其同样可以采用依据上述结构的其他流程进行数据处理，只要利用本电路结构的实现方式，都是本实施例保护的范围。

本发明同时公开了一种变长快速傅立叶变换单元的框架结构，其结构如图4所示，包括：

主控单元41，用于接收外部的配置信息并对FFT单元进行参数配置，包括FFT的点数、运算采用的基数以及FFT与IFFT之间的选择等。同时还需控制存储器管理单元43和地址产生单元42，地址产生单元42，用于产生存储器管理单元所需的存储器读、写地址，包括外部存储器46和内部存储器45的地址。存储器管理单元43，用于控制和协调变长FFT模块的内部与外部存储器读写秩序、运算状态机运行状态的跳转与选择。蝶形单元组44，其中包含变长FFT所需所有运算基，如基2、基4或基8等，当其为基8时，其结构如图3所示。运算基的分支结构则可以采用本发明的分支设计方法。内部存储器组45，负责保存FFT运算的中间数据，提供旋转因子的存储空间等。根据系统要求，该内部存储器可适应串行、并行、折叠型等不同方式的FFT运算。如蝶形单元组44内的运算基采用并行分支结构，内部存储器还可以成存储器组的形式。外部存储器46，其包含为FFT输入和输出所需的所有存储器。

更进一步的，本发明同时公开了一种应用于上述快速傅里叶变换蝶形运算处理装置的数据处理方法，其流程如图5所示，包括：

步骤S51、依据预先设定的处理原则，将待处理数据的实部和虚部相加；

步骤S52、当预先设定的基数为8时，对所述相加的结果进行延迟或加乘处理，当预先设定的基数为2或4时，对所述相加得到的结果不做处理；

步骤S53、将步骤S52中得到的结果的实部和虚部分别与旋转因子的实部和虚部相乘；

步骤S54、根据预先设定的处理原则，将与所述旋转因子相乘后得到的乘积进行相加，得到处理结果。

进一步的，所述依据预先设定的处理原则，将待处理数据的实部和虚部相加的过程包括：

当预先设定的处理原则为在两个周期内完成所述处理过程时，当预先设定的基数为2时，利用1个加法器将所述待处理数据的实部和虚部分别进行顺序相加，当预先设定的基数为4时，利用3个加法器将所述待处理数据的实部和虚部分别进行顺序相加，当预先设定的基数为8时，利用6个加法器将所述待处理数据的实部和虚部分别进行顺序相加；

当预先设定的处理原则为在一个周期内完成所述处理过程时，当预先设定的基数为2时，利用2个加法器，分别将所述待处理数据的实部和虚部进行并行相加，当预先设定的基数为4时，利用6个加法器，分别将所述待处理数据的实部和虚部进行并行相加，当预先设定的基数为8时，利用12个加法器，分别将所述待处理数据的实部和虚部进行并行相加。

当预先设定的基数为8时，对所述相加的结果进行延迟或加乘处理的过程包括：将所述相加的结果与相乘项

相乘，获得其相乘的结果。

当所述预先设定的处理原则为：在两个周期内完成所述处理过程时，将与所述旋转因子相乘后得到的乘积进行相加的过程包括：

将与所述旋转因子相乘后得到的乘积进行延迟控制后，再相加；

而当所述预先设定的处理原则为：在一个周期内完成所述处理过程时，将与所述旋转因子相乘后得到的乘积进行相加的过程包括：

将与所述旋转因子相乘后得到的乘积进行直接相加。

本实施例公开的数据处理方法，利用实数乘法器、实数加法器和延迟及常数乘法器的组合，完成快速傅立叶变换蝶型单元的一条分支运算，由于上述结构采用了流水线设计结构思想，因此该方法的资源利用率高，速度快、扩展灵活，并且可以应用在基2、基4或基8的运算场合。

本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。

对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。

Claims (7)

1.一种快速傅里叶变换蝶形运算处理装置，其特征在于，包括：

实数加法器模块，用于依据预先设定的处理原则，将待处理数据的实部和虚部相加；

延迟及常数乘法器模块，用于当预先设定的基数为8时，对所述相加的结果进行延迟或加乘处理，当预先设定的基数为2或4时，对所述相加得到的结果不做处理；

实数乘法器模块，用于将所述延迟及常数乘法器模块中得到的结果的实部和虚部分别与旋转因子的实部和虚部相乘；

实数加法器及延迟控制模块，用于根据所述预先设定的处理原则，将与所述旋转因子相乘后得到的乘积进行相加，得到处理结果。

2.根据权利要求1所述的装置，其特征在于，当所述预先设定的处理原则为在两个周期内完成所述处理过程时，当预先设定的基数为2时，所述实数加法器模块包括至少1个加法器，当预先设定的基数为4时，所述实数加法器模块包括至少3个加法器，当预先设定的基数为8时，所述实数加法器模块包括至少6个加法器；

当所述预先设定的处理原则为在一个周期内完成所述处理过程时，当预先设定的基数为2时，所述实数加法器模块包括至少2个加法器，当预先设定的基数为4时，所述实数加法器模块包括至少6个加法器，当预先设定的基数为8时，所述实数加法器模块包括至少12个加法器。

3.根据权利要求2所述的装置，其特征在于，当所述预先设定的处理原则为在两个周期内完成所述处理过程时，所述实数加法器及延迟控制模块包括：相加单元和延迟控制单元；

当所述预先设定的处理原则为在一个周期内完成所述处理过程时，所述实数加法器及延迟控制模块包括：相加单元。

4.一种数据处理方法，其特征在于，包括：

步骤a、依据预先设定的处理原则，将待处理数据的实部和虚部相加；

步骤b、当预先设定的基数为8时，对所述相加的结果进行延迟或加乘处理，当预先设定的基数为2或4时，对所述相加得到的结果不做处理；

步骤c、将步骤b中得到的结果的实部和虚部分别与旋转因子的实部和虚部相乘；

步骤d、根据预先设定的处理原则，将与所述旋转因子相乘后得到的乘积进行相加，得到处理结果。

5.根据权利要求4所述的方法，其特征在于，所述依据预先设定的处理原则，将待处理数据的实部和虚部相加的过程包括：

当预先设定的处理原则为在两个周期内完成所述处理过程时，当预先设定的基数为2时，利用1个加法器将所述待处理数据的实部和虚部分别进行顺序相加，当预先设定的基数为4时，利用3个加法器将所述待处理数据的实部和虚部分别进行顺序相加，当预先设定的基数为8时，利用6个加法器将所述待处理数据的实部和虚部分别进行顺序相加；

当预先设定的处理原则为在一个周期内完成所述处理过程时，当预先设定的基数为2时，利用2个加法器，分别将所述待处理数据的实部和虚部进行并行相加，当预先设定的基数为4时，利用6个加法器，分别将所述待处理数据的实部和虚部进行并行相加，当预先设定的基数为8时，利用12个加法器，分别将所述待处理数据的实部和虚部进行并行相加。

6.根据权利要求5所述的方法，其特征在于，当预先设定的基数为8时，对所述相加的结果进行延迟或加乘处理的过程包括：

将所述相加的结果与常数乘法项

相乘，获得其相乘的结果。

7.根据权利要求5所述的方法，其特征在于，当所述预先设定的处理原则为：在两个周期内完成所述处理过程时，将与所述旋转因子相乘后得到的乘积进行相加的过程包括：

将与所述旋转因子相乘后得到的乘积进行延迟控制后，再相加；

当所述预先设定的处理原则为：在一个周期内完成所述处理过程时，将与所述旋转因子相乘后得到的乘积进行相加的过程包括：

将与所述旋转因子相乘后得到的乘积进行直接相加。

Images