一种实现快速傅立叶变换/离散傅立叶变换的装置及方法

摘要

本发明公开了一种实现快速傅立叶变换/离散傅立叶变换的装置及方法，该装置包括：第一乘法器、第二乘法器、第一加法器、第二加法器、第一复用器、第二复用器、第一累加寄存器、第二累加寄存器和取反控制器，其中：第一加法器用于将第一复用器、第一乘法器、第二乘法器的输出信号累加后输入到第一累加寄存器；第二加法器用于将第二复用器、第一乘法器、第二乘法器的输出信号累加后输入到第二累加寄存器；第一累加寄存器用于将第一加法器的输出信号输出或将其反馈到第一复用器；第二累加寄存器用于将第二加法器的输出信号输出或将其反馈到第二复用器。利用本发明所述装置，可以一次得到高阶蝶形运算的两路信号输出，提高了高阶蝶形运算的运算速度。

说明书

技术领域

本发明涉及通信技术领域，尤其涉及一种实现快速傅立叶变换/离散傅立叶 变换（Fast Fourier Transformation/Discrete Fourier Transformation，FFT/DFT） 的装置及方法。

背景技术

FFT/DFT广泛应用于进行信号处理的通信系统中，尤其是涉及正交频分复 用技术（Orthogonal Frequency Division Multiplexing，OFDM）的LTE（Long Term  Evolution，长期演进）、全球微波互联接入（Worldwide Interoperability for  Microwave Access，Wimax）、中国移动多媒体广播（China Mobile Multimedia  Broadcasting，CMMB）、数字电视广播（Digital Video Broadcasting，DVB）、 数字音频广播（Digital Audio Broadcast，DAB）、数字用户线路（Digital Subscriber  Line，DSL）等通信系统中。

对于DFT来说，长度为N的有限长序列x(n)的DFT的计算公式为： $X\left(k\right)=\mathrm{DFT}\left[x\left(n\right)\right]=\underset{n=0}{\overset{N-1}{\Sigma }}x\left(n\right)W_N^{\mathrm{nk}}(k=\mathrm{0,1},...N-1),$一般情况下，x(n)为复数序列，对某 一个k值，直接按上式计算x(k)值需要N次复数乘法、(N-1)次复数加法，因 此直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计 算量太大，导致计算时间过长，并且会造成软硬件资源的浪费，因此，为了避 免直接使用DFT进行信号实时处理时难度过大的问题，FFT应运而生。

FFT是DFT的快速算法，可以简化DFT的运算量，提高运算速度,因 为系数是一个周期函数，具备周期性和对称性，根据的对称性 可以得到：${\left(W_N^{\mathrm{nk}}\right)}^{*}=W_N^{-\mathrm{nk}},$$W_N^{k+n/2}=-W_N^k,$$W_N^{n(N+k)}=W_N^{k(N+n)}=W_N^{\mathrm{nk}}$以及 $W_N^{n(N-k)}=W_N^{k(N-n)}=W_N^{-\mathrm{nk}},$通过巧妙利用的周期性和对称性，可以使DFT的运 算尽量分解为更少点数的DFT运算。

目前，传统的FFT/DFT计算可以采用通用运算单元或者某种形式的专用 蝶形运算单元进行计算，其中，传统的通用运算单元可以实现实数乘、实数加、 实数乘加、实数乘累加、复数乘、复数加、复数乘加、复数乘累加以及基2蝶 形运算，但是无法实现N点高阶蝶形运算（所述N为大于2的正整数）；在进 行N点高阶蝶形运算时，通常采用更为复杂的专用蝶形运算单元，如采用可以 同时支持基3，基4，基5蝶形的专用蝶形计算单元，但是，此种类型的专用 蝶形运算单元在设计完成之后只能实现某几个固定点数的FFT/DFT处理，在 具体的应用环境中可能需要计算多种点数的FFT/DFT，所以现有技术中的专用 蝶形运算单元存在灵活性低的问题，同时，此种类型的专用蝶形运算单元通常 需要消耗较多的硬件资源，复杂度和功耗均较高，因而导致进行实时信号处理 时的运算速度并不高，并不利于在移动终端的应用。

发明内容

本发明实施例提供了一种实现FFT/DFT的装置及方法，用以解决现有技 术中存在的通用运算单元无法实现高阶蝶形运算以及专用蝶形运算单元运算 速度以及灵活性并不高的问题。

一种实现FFT/DFT的装置，包括：第一乘法器、第二乘法器、第一加法 器、第二加法器、第一复用器、第二复用器、第一累加寄存器、第二累加寄存 器以及用于对第一乘法器和/或第二乘法器的输出信号进行取反操作的取反控 制器，其中：

所述第一加法器的输入端与第一复用器的输出端、第一乘法器的输出端以 及第二乘法器的输出端相连，输出端与第一累加寄存器的输入端相连，用于将 第一复用器的输出信号、第一乘法器的输出信号以及第二乘法器的输出信号进 行累加，并将得到的累加信号输入到第一累加寄存器；

所述第二加法器的输入端与第一乘法器的输出端、第二乘法器的输出端以 及第二复用器的输出端相连，且输出端与第二累加寄存器输入端相连，用于将 第二复用器的输出信号、第一乘法器的输出信号以及第二乘法器的输出信号进 行累加，并将得到的累加信号输入到第二累加寄存器；

所述第一累加寄存器用于将第一加法器的输出信号进行输出或将其反馈 到第一复用器的输入端；所述第二累加寄存器用于将第二加法器的输出信号进 行输出或将其反馈到第二复用器的输入端。

一种利用上述实现FFT/DFT的装置进行N点蝶形运算的方法，所述方法 包括：

针对第一个实现FFT/DFT的装置，执行以下操作：

向第一乘法器的两个输入端分别输入第一信号的同相（In-phase，I）信号、 第二信号的I信号，向第二乘法器的两个输入端分别输入第一信号的正交 （Quadrature，Q）信号、第二信号的Q信号，以及向第一复用器和第二复用 器输入第三信号的I信号；

利用第一加法器对第一复用器的输出信号、第一乘法器的输出信号以及经 过取反控制器处理后的第二乘法器的输出信号进行累加运算，并将得到的累加 信号经由第一累加寄存器反馈至第一复用器，由第一复用器将所述第一累加寄 存器反馈的累加信号作为更新后的第一复用器的输出信号，并对更新后的第一 复用器的输出信号、第一乘法器的输出信号以及经过取反控制器处理后的第二 乘法器的输出信号继续执行上述累加运算，直至进行累加运算时利用的第一复 用器的输出信号为第一累加寄存器第N-2次反馈的累加信号，所述N为大于2 的正整数；

将第一加法器最后一次累加运算所得到的累加信号作为N点蝶形运算的 第一路I信号；以及，

利用第二加法器对第二复用器的输出信号、第一乘法器的输出信号以及第 二乘法器的输出信号进行累加运算，并将得到的累加信号经由第二累加寄存器 反馈至第二复用器，由第二复用器将所述第二累加寄存器反馈的累加信号作为 更新后的第二复用器的输出信号，并对更新后的第二复用器的输出信号、第一 乘法器的输出信号以及第二乘法器的输出信号继续执行上述累加运算，直至进 行累加运算时利用的第二复用器的输出信号为第二累加寄存器第N-2次反馈的 累加信号；

将第二加法器最后一次累加运算所得到的累加信号作为N点蝶形运算的 第二路I信号；

以及，针对第二个实现FFT/DFT的装置，执行以下操作：

向第一乘法器的两个输入端分别输入第一信号的I信号、第二信号的Q信 号，向第二乘法器的两个输入端分别输入第二信号的I信号、第一信号Q信号， 以及向第一复用器和第二复用器输入第三信号的Q信号；

利用第一加法器对第一复用器的输出信号、第一乘法器的输出信号以及第 二乘法器的输出信号进行累加运算，并将得到的累加信号经由第一累加寄存器 反馈至第一复用器，由第一复用器将所述第一累加寄存器反馈的累加信号作为 更新后的第一复用器的输出信号，并对更新后的第一复用器的输出信号、第一 乘法器的输出信号以及第二乘法器的输出信号继续执行上述累加运算，直至进 行累加运算时利用的第一复用器的输出信号为第一累加寄存器第N-2次反馈的 累加信号；

将第一加法器最后一次累加运算所得到的累加信号作为N点蝶形运算的 第一路Q信号；

利用第二加法器对第二复用器的输出信号、第一乘法器的输出信号以及经 过取反控制器处理后的第二乘法器的输出信号进行累加运算，并将得到的累加 信号经由第二累加寄存器反馈至第二复用器，由第二复用器将所述第二累加寄 存器反馈的累加信号作为更新后的第二复用器的输出信号，并对更新后的第二 复用器的输出信号、第一乘法器的输出信号以及经过取反控制器处理后的第二 乘法器的输出信号继续执行上述累加运算，直至进行累加运算时利用的第二复 用器的输出信号为第二累加寄存器第N-2次反馈的累加信号；

将第二加法器最后一次累加运算所得到的累加信号作为N点蝶形运算的 第二路Q信号；

将第一个实现FFT/DFT的装置的第一加法器得到的I信号和第二个实现 FFT/DFT的装置的第一加法器得到的Q信号进行合并，得到N点蝶形运算的 第一路输出信号，以及，将第一个实现FFT/DFT的装置的第二加法器得到的I 信号和第二个实现FFT/DFT的装置的第二加法器得到的Q信号进行合并，得 到N点蝶形运算的第二路输出信号。

本发明有益效果如下：

本发明实施例提供了一种实现FFT/DFT的装置及方法，所述装置包括： 第一乘法器、第二乘法器、第一加法器、第二加法器、第一复用器、第二复用 器、第一累加寄存器、第二累加寄存器以及用于对第一乘法器和/或第二乘法器 的输出信号进行取反操作的取反控制器，其中：第一加法器用于将第一复用器、 第一乘法器、第二乘法器的三路输出信号进行累加后输入到第一累加寄存器； 第二加法器用于将第二复用器、第一乘法器、第二乘法器的三路输出信号进行 累加后输入到第二累加寄存器；第一累加寄存器用于将第一加法器的输出信号 进行输出或将其反馈到第一复用器；第二累加寄存器用于将第二加法器的输出 信号进行输出或将其反馈到第二复用器。利用本发明所述装置，在实现通用运 算的基础上，可以一次得到高阶蝶形运算的两路信号输出，提高了高阶蝶形运 算的运算速度。

附图说明

图1所示为本发明实施例一中所述实现FFT/DFT的装置的结构示意图；

图2所示为本发明实施例一中所述利用实施例一中的装置进行复数乘加运 算时的结构示意图一；

图3所示为本发明实施例一中所述利用实施例一中的装置进行复数乘加运 算时的结构示意图二；

图4所示为本发明实施例一中所述利用实施例一中的装置进行基2蝶形运 算时的结构示意图一；

图5所示为本发明实施例一中所述利用实施例一中的装置进行基2蝶形运 算时的结构示意图二；

图6所示为本发明实施例一中所述利用实施例一中的装置进行N点蝶形运 算时的结构示意图一；

图7所示为本发明实施例一中所述利用实施例一中的装置进行N点蝶形运 算时的结构示意图二。

具体实施方式

下面结合说明书附图对本发明实施例作进一步说明，但本发明不局限于下 面的实施例。

实施例一：

如图1所示，为本发明实施例一中所述实现FFT/DFT的装置的结构示意 图，所述装置包括：第一乘法器11、第二乘法器12、第一加法器13、第二加 法器14、第一复用器15（如图1所示的mux1）、第二复用器16（如图1所示 的mux2）、第一累加寄存器17、第二累加寄存器18以及用于对第一乘法器11 和/或第二乘法器12的输出信号进行取反操作的取反控制器19，其中：

所述第一加法器13的输入端与第一复用器15的输出端、第一乘法器11 的输出端以及第二乘法器12的输出端相连，输出端与第一累加寄存器17的输 入端相连，用于将第一复用器15的输出信号、第一乘法器11的输出信号以及 第二乘法器12的输出信号进行累加，并将得到的累加信号输入到第一累加寄 存器17；

所述第二加法器14的输入端与第一乘法器11的输出端、第二乘法器12 的输出端以及第二复用器16的输出端相连，且输出端与第二累加寄存器18输 入端相连，用于将第二复用器16的输出信号、第一乘法器11的输出信号以及 第二乘法器12的输出信号进行累加，并将得到的累加信号输入到第二累加寄 存器18；

所述第一累加寄存器17的输入端与第一加法器13的输出端相连，输出端 与第一信号输出端以及第一复用器15的两个输入端中的一个输入端相连，用 于将第一加法器13的输出信号进行输出或将其反馈到第一复用器15的输入 端；所述第二累加寄存器18的输入端与第二加法器14的输出端相连，输出端 与第二信号输出端以及第二复用器16的两个输入端中的一个输入端相连，用 于将第二加法器14的输出信号进行输出或将其反馈到第二复用器16的输入 端。

进一步地，所述第一复用器15的两个输入端分别与第一信号输入端（如 图1所示的Z0所在位置）以及第一累加寄存器17的输出端相连，用于接收来 自第一信号输入端的输入信号或来自第一累加寄存器17反馈的输出信号；所 述第二复用器16的两个输入端分别与第二信号输入端（如图1所示的Z1所在 位置）以及第二累加寄存器18的输出端相连，用于接收来自第二信号输入端 的输入信号或来自第二累加寄存器18反馈的输出信号；另外，第一乘法器11 的两个输入端分别与第三信号输入端（如图1所示的X0所在位置）以及第四 信号输入端（如图1所示的Y0所在位置）相连，用于接收来自第三信号输入 端以及第四信号输入端的输入信号，并对接收到的来自第三信号输入端以及第 四信号输入端的输入信号进行相乘运算；第二乘法器12的两个输入端分别与 第五信号输入端（如图1所示的X1所在位置）以及第六信号输入端（如图1 所示的Y1所在位置）相连，用于接收来自第五信号输入端以及第六信号输入 端的输入信号，并对接收到的来自第五信号输入端以及第六信号输入端的输入 信号进行相乘运算。

具体地，所述取反控制器19包括第一取反控制器191（如图1所示的neg1）、 第二取反控制器192（如图1所示的neg2）以及第三取反控制器193（如图1 所示的neg3）：

所述第一取反控制器191一端与第一乘法器11的输出端相连，另一端与 第二加法器14的输入端相连，用于在接收到触发条件时对第一乘法器11向第 二加法器14输入的信号进行取反操作；

所述第二取反控制器192一端与第二乘法器12的输出端相连，另一端与 第一加法器13的输入端相连，用于在接收到触发条件时对第二乘法器12向第 一加法器13输入的信号进行取反操作；

所述第三取反控制器193一端与第二乘法器12的输出端相连，另一端与 第二加法器14的输入端相连，用于在接收到触发条件时对第二乘法器12向第 二加法器14输入的信号进行取反操作。

进一步地，所述装置还包括第三复用器20（如图1所示的mux3）以及第 四复用器21（如图1所示的mux4）：

所述第三复用器20的两个输入端分别与零信号输出端（如图1所示的信 号“0”）以及第二乘法器12的输出端相连，用于向第一加法器13输入零信号 或第二乘法器12的输出信号；

所述第四复用器21的两个输入端分别与零信号输出端（如图1所示的信 号“0”）以及第一乘法器11的输出端相连，用于向第二加法器14输入零信号 或第一乘法器11的输出信号。

进一步地，所述装置还包括指令译码单元22：

所述指令译码单元22用于控制第一复用器15、第二复用器16、第三复用 器20、第四复用器21的输出信号（例如，控制第一复用器15向第一加法器 13输入第一复用器15两个输入端输入信号中的一个输入信号，控制第三复用 器20向第一加法器13输入第三复用器20两个输入端输入信号中的一个输入 信号，如零信号或第一乘法器12的输出信号等），以及在需要对第一乘法器11 以及第二乘法器12的输出信号进行取反操作时触发取反控制器19（具体地， 在需要对第一乘法器11向第二加法器14输入的信号进行取反操作时，触发第 一取反控制器191，在需要对第二乘法器12向第一加法器13输入的信号进行 取反操作时，触发第二取反控制器192以及在需要对第二乘法器12向第二加 法器14输入的信号进行取反操作时，触发第三取反控制器193）。

具体地，利用本发明实施例一中所述装置，能够同时完成2个并行的实数 乘、实数加、实数乘加、实数乘累加等通用运算，例如：指令译码单元22控 制第三复用器20、第四复用器21分别向第一加法器13以及第二加法器14输 入全0数据，并控制第一复用器15、第二复用器16分别向第一加法器13、第 二加法器14输入全0数据，则可以得到第一乘法器11两个输入端输入数据的 乘积和第二乘法器12两个输入端输入数据的乘积；或者，若分别将第一乘法 器11和第二乘法器12一个输入端输入的数据置为1，且控制第三复用器20、 第四复用器21分别向第一加法器13以及第二加法器14输入全0数据，则可 以得到第一乘法器11输入端输入的非1数据与第一信号输入端输入数据的和， 以及第二乘法器12输入端输入的非1数据与第二信号输入端输入数据的和； 再者，若仅控制第三复用器20、第四复用器21分别向第一加法器13以及第二 加法器14输入全0数据，则可以实现第一乘法器11两个输入端输入数据的乘 积与第一信号输入端输入数据的和，以及第二乘法器12两个输入端输入数据 的乘积与第二信号输入端输入数据的和，即可以实现两个实数的乘加；进一步 地，若控制第一复用器15以及第二复用器16分别向第一加法器13以及第二 加法器14输入第一累加寄存器17、第二累加寄存器18反馈的累加信号，则可 以实现两个实数的乘累加。

进一步地，同时利用两个本发明实施例一中所述实现FFT/DFT的装置能 够实现1次复数乘、复数加、复数乘加、复数乘累加等通用运算，具体地，图 2所示即为本发明实施例一中所述利用实施例一中的装置进行复数乘加运算时 的结构示意图一（具体地，图2所示为进行复数乘加时的实部计算结构示意图）。

具体地，在利用所述实现FFT/DFT的装置进行复数乘加时所依据的复数 乘加计算公式可以如下所示：

V=Vr+j*Vi=X*Y+Z=(Xr+j*Xi)*(Yr+j*Yi)+(Zr+j*Zi)

Vr=Xr*Yr-Xi*Yi+Zr

Vi=Xr*Yi+Xi*Yr+Zi

具体地，按照上述公式，在进行复数乘加时的实部计算时，如图2所示， 需要向第一乘法器11的两个输入端输入第一信号的I信号（Xr）以及第二信 号的I信号（Yr）、向第二乘法器12的两个输入端输入第一信号的Q信号（Xi） 以及第二信号的Q信号（Yi），并向第一信号输入端以及第二信号输入端输入 第三信号的I信号（Zr），指令译码单元22控制第三复用器20、第四复用器21 分别向第一加法器13、第二加法器14输入交叉数据（向第一加法器13输入第 一乘法器12的输出信号，向第二加法器14输入第一乘法器11的输出信号）， 同时触发取反控制器19（第一取反控制器191）将第二乘法器12的输出信号 进行取反操作，则可以得到将输入的第一信号、第二信号以及第三信号进行复 数乘加运算后实部信号（I信号），具体地，所得到的I信号为第一累加寄存器 17输出的信号；

进一步地，如图3所示（利用实施例一中的装置进行复数乘加运算时的结 构示意图二），在进行复数乘加时的虚部计算时，需要向第一乘法器11的两个 输入端输入第一信号的I信号（Xr）以及第二信号的Q信号（Yi）、向第二乘 法器12的两个输入端输入第一信号的Q信号（Xi）以及第二信号的I信号（Yr）， 并向第一信号输入端以及第二信号输入端输入第三信号的Q信号（Zi），指令 译码单元22控制第三复用器20、第四复用器21分别向第一加法器13、第二 加法器14输入交叉数据（向第一加法器13输入第一乘法器12的输出信号， 向第二加法器14输入第一乘法器11的输出信号），则可以得到将输入的第一 信号、第二信号以及第三信号进行复数乘加运算后虚部信号（Q信号），具体 地，所得到的Q信号为第一累加寄存器17输出的信号。

进一步地，同时利用两个本发明实施例一中所述实现FFT/DFT的装置还 能够实现1次基2蝶形运算，具体地，在利用所述实现FFT/DFT的装置进行 基2蝶形运算时所依据的基2蝶形运算的计算公式可以如下所示：

V=Z+X*Y

U=Z-X*Y

进一步地，对上述V，U进行实部虚部展开，可以得到：

Vr=Xr*Yr-Xi*Yi+Zr

Vi=Xr*Yi+Xi*Yr+Zi

Ur=-Xr*Yr+Xi*Yi+Zr

Ui=-Xr*Yi-Xi*Yr+Zi

具体地，按照上述公式，在进行基2蝶形运算时的实部计算时，如图4所 示，需要向第一乘法器11的两个输入端输入第一信号的I信号（Xr）以及第 二信号的I信号（Yr）、向第二乘法器12的两个输入端输入第一信号的Q信号 （Xi）以及第二信号的Q信号（Yi），并向第一信号输入端以及第二信号输入 端输入第三信号的I信号（Zr），指令译码单元22控制第三复用器20、第四复 用器21分别向第一加法器13、第二加法器14输入交叉数据（向第一加法器 13输入第一乘法器12的输出信号，向第二加法器14输入第一乘法器11的输 出信号），同时触发取反控制器19（第一取反控制器191）将第二乘法器12的 输出信号进行取反操作以及触发取反控制器19（第二取反控制器192）将第一 乘法器11的输出信号进行取反操作，则可以得到将输入的第一信号、第二信 号以及第三信号进行基2叠加运算后的两路实部信号（I信号），具体地，所得 到的两路实部信号分别为第一累加寄存器17输出的信号（如图4所示的Vr） 和第二累加寄存器18输出的信号（如图4所示的Ur）；

进一步地，如图5所示（利用实施例一中的装置进行基2蝶形运算时的结 构示意图二），在进行基2蝶形运算时的虚部计算时，需要向第一乘法器11的 两个输入端输入第一信号的I信号（Xr）以及第二信号的Q信号（Yi）、向第 二乘法器12的两个输入端输入第一信号的Q信号（Xi）以及第二信号的I信 号（Yr），并向第一信号输入端以及第二信号输入端输入第三信号的Q信号 （Zi），指令译码单元22控制第三复用器20、第四复用器21分别向第一加法 器13、第二加法器14输入交叉数据（向第一加法器13输入第一乘法器12的 输出信号，向第二加法器14输入第一乘法器11的输出信号），同时触发取反 控制器19（第二取反控制器192）将第一乘法器11的输出信号进行取反操作 以及触发取反控制器19（第三取反控制器193）将第二乘法器12的输出信号 进行取反操作，则可以得到将输入的第一信号、第二信号以及第三信号进行复 数乘加运算后两路虚部信号（Q信号），具体地，所得到的两路虚部信号分别 为第一累加寄存器17输出的信号（如图5所示的Vi）和第二累加寄存器18 输出的信号（如图5所示的Ui）；

进一步地，将第一累加寄存器17的输出信号Vr与第一累加寄存器17的 输出信号Vi进行合并，即可得到基2蝶形运算中的V信号；类似地，将第二 累加寄存器18的输出信号Ur与第二累加寄存器18的输出信号Ui进行合并， 即可得到基2蝶形运算中的U信号。

进一步地，同时利用两个本发明实施例一中所述实现FFT/DFT的装置还 能够实现1次N点蝶形运算，具体地，在利用所述实现FFT/DFT的装置进行 N点蝶形运算时所依据的N点蝶形运算的计算公式可以如下所示：

$\left(\begin{array}{c}{y}_0\\ y_1\\ y_2\\ ...\\ y_{N-2}\\ y_{N-1}\end{array}\right)=\left(\begin{array}{cccccc}{W}^0& W^0& W^0& ...& W^0& W^0\\ W^0& W^1& W^2& ...& W^{N-2}& W^{N-1}\\ W^0& W^2& W^4& ...& W^{2*(N-2)}& W^{2*(N-1)}\\ ...& ...& ...& ...& ...& ...\\ W^0& W^{N-2}& W^{(N-2)*2}& ...& W^{(N-2)*(N-2)}& W^{(N-2)*(N-1)}\\ W^0& W^{N-1}& W^{(N-1)*2}& ...& W^{(N-1)*(N-2)}& W^{(N-1)*(N-1)}\end{array}\right)\left(\begin{array}{c}{x}_0\\ w_1{x}_1\\ w_2{x}_2\\ ...\\ w_{N-2}{x}_{N-2}\\ w_{N-1}{x}_{N-1}\end{array}\right)$

$=\left(\begin{array}{cccccc}{W}^0& W^0& W^0& ...& W^0& W^0\\ W^0& W^1& W^2& ...& W^{N-2}& W^{N-1}\\ W^0& W^2& W^4& ...& W^{2*(N-2)}& W^{2*(N-1)}\\ ...& ...& ...& ...& ...& ...\\ W^0& {\bar{W}}^2& {\bar{W}}^4& ...& {\bar{W}}^{2*(N-2)}& {\bar{W}}^{2*(N-1)}\\ W^0& {\bar{W}}^1& {\bar{W}}^2& ...& {\bar{W}}^{N-2}& {\bar{W}}^{N-1}\end{array}\right)\left(\begin{array}{c}{z}_0\\ z_1\\ z_2\\ ...\\ z_{N-2}\\ z_{N-1}\end{array}\right)$

进一步地，对上述公式进行化简，可以得到：

y₁＝W⁰Z₀+W¹Z₁+W²Z₂+...+W^N-2Z_N-2+W^N-1Z_N-1

$y_{N-1}=W^0{z}_0+{\bar{W}}^1{z}_1+{\bar{W}}^2{z}_2+...+{\bar{W}}^{N-2}{z}_{N-2}+{\bar{W}}^{N-1}{z}_{N-1}$

y₂＝W⁰Z₀+W²Z₁+W⁴Z₂+...+W^2*(N-2)Z_N-2+W^2*(N-1)Z_N-1

$y_{N-2}=W^0{z}_0+{\bar{W}}^2{z}_1+{\bar{W}}^4{z}_2+...+{\bar{W}}^{2*(N-2)}{z}_{N-2}+{\bar{W}}^{2*(N-1)}{z}_{N-1}$

进一步地，依据上述公式可以得到如下所示的ditn，ditn_acc公式，并通 过一次ditn和多次（N-2次）ditn_acc累加同时计算出N点蝶形运算的两路输 出信号，所述ditn以及ditn_acc可以表示为：

ditn：V=Z+X*Y

$U=Z+\bar{X}*Y$

ditn_acc：V=acc+X*Y

$U=\mathrm{acc}+\bar{X}*Y$

将ditn、ditn_acc的实部虚部展开，可以得到：

ditn：Vr=Xr*Yr-Xi*Yi+Zr

Vi=Xr*Yi+Xi*Yr+Zi

Ur=Xr*Yr+Xi*Yi+Zr

Ui=Xr*Yi-Xi*Yr+Zi

ditn_acc：Vr=Xr*Yr-Xi*Yi+accr

Vi=Xr*Yi+Xi*Yr+acci

Ur=Xr*Yr+Xi*Yi+accr

Ui=Xr*Yi-Xi*Yr+acci

具体地，上述ditn公式的实现方式可以为：如图6所示，向第一乘法器 11的两个输入端输入第一信号的I信号（Xr）以及第二信号的I信号（Yr）、 向第二乘法器12的两个输入端输入第一信号的Q信号（Xi）以及第二信号的 Q信号（Yi），并向第一信号输入端以及第二信号输入端输入第三信号的I信号 （Zr），指令译码单元22控制第三复用器20、第四复用器21分别向第一加法 器13、第二加法器14输入交叉数据（向第一加法器13输入第一乘法器12的 输出信号，向第二加法器14输入第一乘法器11的输出信号），同时触发取反 控制器19（第一取反控制器191）将第二乘法器12的输出信号进行取反操作， 则可以得到ditn的两路实部信号（I信号），具体地，所得到的两路实部信号分 别为第一累加寄存器17输出的信号（如图6所示的Vr）和第二累加寄存器18 输出的信号（如图6所示的Ur）；

进一步地，如图7所示，向第一乘法器11的两个输入端输入第一信号的I 信号（Xr）以及第二信号的Q信号（Yi）、向第二乘法器12的两个输入端输入 第一信号的Q信号（Xi）以及第二信号的I信号（Yr），并向第一信号输入端 以及第二信号输入端输入第三信号的Q信号（Zi），指令译码单元22控制第三 复用器20、第四复用器21分别向第一加法器13、第二加法器14输入交叉数 据（向第一加法器13输入第一乘法器12的输出信号，向第二加法器14输入 第一乘法器11的输出信号），同时触发取反控制器19（第三取反控制器193） 将第二乘法器12的输出信号进行取反操作，则可以得到ditn的两路虚部信号 （Q信号），具体地，所得到的两路虚部信号分别为第一累加寄存器17输出的 信号（如图7所示的Vi）和第二累加寄存器18输出的信号（如图7所示的Ui）；

进一步地，上述ditn_acc公式的实现方式可以为：如图6所示，向第一乘 法器11的两个输入端输入第一信号的I信号（Xr）以及第二信号的I信号（Yr）、 向第二乘法器12的两个输入端输入第一信号的Q信号（Xi）以及第二信号的 Q信号（Yi），并向第一信号输入端以及第二信号输入端输入第三信号的I信号 （Zr），指令译码单元22控制第三复用器20、第四复用器21分别向第一加法 器13、第二加法器14输入交叉数据（向第一加法器13输入第一乘法器12的 输出信号，向第二加法器14输入第一乘法器11的输出信号），以及控制第一 复用器15、第一复用器16分别向第一加法器13、第二加法器14输入第一累 加寄存器17、第二累加寄存器18反馈的累加信号，同时触发取反控制器19（第 一取反控制器191）将第二乘法器12的输出信号进行取反操作，则可以得到 ditn_acc的两路实部信号（I信号），具体地，所得到的两路实部信号分别为第 一累加寄存器17输出的信号（如图6所示的Vr）和第二累加寄存器18输出的 信号（如图6所示的Ur）；

进一步地，如图7所示，向第一乘法器11的两个输入端输入第一信号的I 信号（Xr）以及第二信号的Q信号（Yi）、向第二乘法器12的两个输入端输入 第一信号的Q信号（Xi）以及第二信号的I信号（Yr），并向第一信号输入端 以及第二信号输入端输入第三信号的Q信号（Zi），指令译码单元22控制第三 复用器20、第四复用器21分别向第一加法器13、第二加法器14输入交叉数 据（向第一加法器13输入第一乘法器12的输出信号，向第二加法器14输入 第一乘法器11的输出信号），以及控制第一复用器15、第一复用器16分别向 第一加法器13、第二加法器14输入第一累加寄存器17、第二累加寄存器18 反馈的累加信号，同时触发取反控制器19（第三取反控制器193）将第二乘法 器12的输出信号进行取反操作，则可以得到ditn_acc的两路虚部信号（Q信 号），具体地，所得到的两路虚部信号分别为第一累加寄存器17输出的信号（如 图7所示的Vi）和第二累加寄存器18输出的信号（如图7所示的Ui）。

进一步地，所述y1，yN-1可以由一次ditn，N-2次ditn_acc同时计算出结 果，y2，yN-2以及y3，yN-3可以同样组对算出。

本发明实施例一提供了一种实现FFT/DFT的装置，所述装置包括：第一 乘法器、第二乘法器、第一加法器、第二加法器、第一复用器、第二复用器、 第一累加寄存器、第二累加寄存器以及用于对第一乘法器和/或第二乘法器的输 出信号进行取反操作的取反控制器，其中：第一加法器用于将第一复用器的输 出信号、第一乘法器的输出信号、第二乘法器的输出信号进行累加后输入到第 一累加寄存器；第二加法器用于将第二复用器的输出信号、第一乘法器的输出 信号、第二乘法器输出信号进行累加后输入到第二累加寄存器；第一累加寄存 器用于将第一加法器的输出信号进行输出或将其反馈到第一复用器；第二累加 寄存器用于将第二加法器的输出信号进行输出或将其反馈到第二复用器。利用 本发明所述装置，能够同时完成2个并行的实数乘、实数加、实数乘加、实数 乘累加等通用运算，或者同时利用两个本发明实施例一中所述实现FFT/DFT 的装置能够实现1次复数乘、复数加、复数乘加、复数乘累加等通用运算，以 及利用本发明实施例一中所述实现FFT/DFT的装置能够一次同时计算出基2 蝶形运算的两路输出或N点蝶形运算的两路输出等，在满足通用运算的基础 上，大大提高了基2蝶形运算或N点高阶蝶形运算的运算速度（所述N为大 于2的正整数），可以适用于DSP、矢量处理器等计算单元中。

实施例二：

本发明实施例二提供了一种利用实施例一中所述实现FFT/DFT的装置进 行N点蝶形运算的方法（所述方法需要利用两个实施例一中所述的实现 FFT/DFT的装置），所述方法包括：

步骤一：针对第一个实现FFT/DFT的装置（第一装置），向该第一装置的 第一乘法器的两个输入端分别输入第一信号的I信号、第二信号的I信号，向 该第一装置的第二乘法器的两个输入端分别输入第一信号的Q信号、第二信号 的Q信号，以及向该第一装置的第一复用器和第二复用器输入第三信号的I信 号。

具体地，以图6为例，在本步骤一中需要向第一乘法器11的两个输入端 输入第一信号的I信号（Xr）以及第二信号的I信号（Yr）、向第二乘法器12 的两个输入端输入第一信号的Q信号（Xi）以及第二信号的Q信号（Yi），并 向第一信号输入端以及第二信号输入端输入第三信号的I信号（Zr）。

步骤二：针对第一装置，执行以下操作：利用第一加法器对第一复用器的 输出信号、第一乘法器的输出信号以及经过取反控制器处理后的第二乘法器的 输出信号进行累加运算，并将得到的累加信号经由第一累加寄存器反馈至第一 复用器，由第一复用器将所述第一累加寄存器反馈的累加信号作为更新后的第 一复用器的输出信号，并对更新后的第一复用器的输出信号、第一乘法器的输 出信号以及经过取反控制器处理后的第二乘法器的输出信号继续执行上述累 加运算，直至进行累加运算时利用的第一复用器的输出信号为第一累加寄存器 第N-2次反馈的累加信号，所述N为大于2的正整数；以及，

利用第二加法器对第二复用器的输出信号、第一乘法器的输出信号以及第 二乘法器的输出信号进行累加运算，并将得到的累加信号经由第二累加寄存器 反馈至第二复用器，由第二复用器将所述第二累加寄存器反馈的累加信号作为 更新后的第二复用器的输出信号，并对更新后的第二复用器的输出信号、第一 乘法器的输出信号以及第二乘法器的输出信号继续执行上述累加运算，直至进 行累加运算时利用的第二复用器的输出信号为第二累加寄存器第N-2次反馈的 累加信号。

具体地，以图6为例，在本步骤二中，指令译码单元22需要控制第三复 用器20、第四复用器21分别向第一加法器13、第二加法器14输入交叉数据 （向第一加法器13输入第一乘法器12的输出信号，向第二加法器14输入第 一乘法器11的输出信号），以及控制第一复用器15、第一复用器16分别向第 一加法器13、第二加法器14输入第一累加寄存器17、第二累加寄存器18反 馈的累加信号，同时触发取反控制器19（第一取反控制器191）将第二乘法器 12的输出信号进行取反操作。

步骤三：将第一装置的第一加法器最后一次累加运算所得到的累加信号作 为N点蝶形运算的第一路I信号，以及，将第一装置的第二加法器最后一次累 加运算所得到的累加信号作为N点蝶形运算的第二路I信号。

具体地，以图6为例，本步骤三中所得到的第一路I信号为第一累加寄存 器17输出的信号（如图6所示的Vr），所得到的第二路I信号为第二累加寄存 器18输出的信号（如图6所示的Ur）。

步骤四：针对第二个实现FFT/DFT的装置（第二装置），向该第二装置的 第一乘法器的两个输入端分别输入第一信号的I信号、第二信号的Q信号，向 该第二装置的第二乘法器的两个输入端分别输入第二信号的I信号、第一信号 Q信号，以及向该第二装置的第一复用器和第二复用器输入第三信号的Q信 号。

具体地，以图7为例，在本步骤四中需要向第一乘法器11的两个输入端 输入第一信号的I信号（Xr）以及第二信号的Q信号（Yi）、向第二乘法器12 的两个输入端输入第一信号的Q信号（Xi）以及第二信号的I信号（Yr），并 向第一信号输入端以及第二信号输入端输入第三信号的Q信号（Zi）。

步骤五：针对第二装置，执行以下操作：利用第一加法器对第一复用器的 输出信号、第一乘法器的输出信号以及第二乘法器的输出信号进行累加运算， 并将得到的累加信号经由第一累加寄存器反馈至第一复用器，由第一复用器将 所述第一累加寄存器反馈的累加信号作为更新后的第一复用器的输出信号，并 对更新后的第一复用器的输出信号、第一乘法器的输出信号以及第二乘法器的 输出信号继续执行上述累加运算，直至进行累加运算时利用的第一复用器的输 出信号为第一累加寄存器第N-2次反馈的累加信号；以及，

利用第二加法器对第二复用器的输出信号、第一乘法器的输出信号以及经 过取反控制器处理后的第二乘法器的输出信号进行累加运算，并将得到的累加 信号经由第二累加寄存器反馈至第二复用器，由第二复用器将所述第二累加寄 存器反馈的累加信号作为更新后的第二复用器的输出信号，并对更新后的第二 复用器的输出信号、第一乘法器的输出信号以及经过取反控制器处理后的第二 乘法器的输出信号继续执行上述累加运算，直至进行累加运算时利用的第二复 用器的输出信号为第二累加寄存器第N-2次反馈的累加信号。

具体地，以图7为例，在本步骤五中，指令译码单元22需要控制第三复 用器20、第四复用器21分别向第一加法器13、第二加法器14输入交叉数据 （向第一加法器13输入第一乘法器12的输出信号，向第二加法器14输入第 一乘法器11的输出信号），以及控制第一复用器15、第一复用器16分别向第 一加法器13、第二加法器14输入第一累加寄存器17、第二累加寄存器18反 馈的累加信号，同时触发取反控制器19（第三取反控制器193）将第二乘法器 12的输出信号进行取反操作。

步骤六：将第二装置的第一加法器最后一次累加运算所得到的累加信号作 为N点蝶形运算的第一路Q信号；以及，将第二装置的第二加法器最后一次 累加运算所得到的累加信号作为N点蝶形运算的第二路Q信号。

具体地，所得到的第一路Q信号为第一累加寄存器17输出的信号（如图 7所示的Vi），所得到的第二路Q信号为第二累加寄存器18输出的信号（如图 7所示的Ui）。

步骤七：将第一装置的第一加法器得到的I信号和第二装置的第一加法器 得到的Q信号进行合并，得到N点蝶形运算的第一路输出信号，以及，将第 一装置的第二加法器得到的I信号和第二装置的第二加法器得到的Q信号进行 合并，得到N点蝶形运算的第二路输出信号。

需要说明的是，步骤一~步骤三与步骤四~步骤六可以为同时进行的操作， 当所述步骤一~步骤三与步骤四~步骤六同时进行时，需要同时利用两个本发明 实施例一中所述的实现FFT/DFT的装置，如本发明实施例二中所述的第一装 置和第二装置。

进一步地，本发明实施例二还提供了一种利用实施例一中所述实现 FFT/DFT的装置进行基2蝶形运算的方法（所述方法同样需要利用两个实施例 一中所述的实现FFT/DFT的装置），所述方法包括：

步骤一：针对第一个实现FFT/DFT的装置，向该装置的第一乘法器的两 个输入端分别输入第一信号的I信号、第二信号的I信号，向该装置的第二乘 法器的两个输入端分别输入第一信号的Q信号、第二信号的Q信号，以及向 该装置的第一复用器和第二复用器输入第三信号的I信号。

具体地，以图4为例，在本步骤一中需要向第一乘法器11的两个输入端 输入第一信号的I信号（Xr）以及第二信号的I信号（Yr）、向第二乘法器12 的两个输入端输入第一信号的Q信号（Xi）以及第二信号的Q信号（Yi），并 向第一信号输入端以及第二信号输入端输入第三信号的I信号（Zr）。

步骤二：针对第一个实现FFT/DFT的装置，执行以下操作：利用第一加 法器对第一复用器的输出信号、第一乘法器的输出信号以及经过取反控制器处 理后的第二乘法器的输出信号进行累加运算，并将得到的累加信号作为将输入 的第一信号、第二信号以及第三信号进行基2叠加运算后的第一路实部信号； 以及，

利用第二加法器对第二复用器的输出信号、经过取反控制器处理后的第一 乘法器的输出信号以及第二乘法器的输出信号进行累加运算，并将得到的累加 信号作为将输入的第一信号、第二信号以及第三信号进行基2叠加运算后的第 二路实部信号。

具体地，以图4为例，在本步骤二中，指令译码单元22需要控制第三复 用器20、第四复用器21分别向第一加法器13、第二加法器14输入交叉数据 （向第一加法器13输入第一乘法器12的输出信号，向第二加法器14输入第 一乘法器11的输出信号），同时触发取反控制器19（第一取反控制器191）将 第二乘法器12的输出信号进行取反操作以及触发取反控制器19（第二取反控 制器192）将第一乘法器11的输出信号进行取反操作。

具体地，所得到的第一路实部信号为第一累加寄存器17输出的信号（如 图4所示的Vr），所得到的第二路实部信号为第二累加寄存器18输出的信号（如 图4所示的Ur）。

步骤三：针对第二个实现FFT/DFT的装置，向该装置的第一乘法器的两 个输入端分别输入第一信号的I信号、第二信号的Q信号，向该装置的第二乘 法器的两个输入端分别输入第二信号的I信号、第一信号Q信号，以及向该装 置的第一复用器和第二复用器输入第三信号的Q信号。

具体地，以图5为例，在本步骤三中需要向第一乘法器11的两个输入端 输入第一信号的I信号（Xr）以及第二信号的Q信号（Yi）、向第二乘法器12 的两个输入端输入第一信号的Q信号（Xi）以及第二信号的I信号（Yr），并 向第一信号输入端以及第二信号输入端输入第三信号的Q信号（Zi）。

步骤四：针对第二个实现FFT/DFT的装置，执行以下操作：利用第一加 法器对第一复用器的输出信号、第一乘法器的输出信号以及第二乘法器的输出 信号进行累加运算，并将得到的累加信号作为将输入的第一信号、第二信号以 及第三信号进行复数乘加运算后第一路虚部信号；以及，

利用第二加法器对第二复用器的输出信号、经过取反控制器处理后的第一 乘法器的输出信号以及经过取反控制器处理后的第二乘法器的输出信号进行 累加运算，并将得到的累加信号作为将输入的第一信号、第二信号以及第三信 号进行复数乘加运算后的第二路虚部信号。

具体地，以图5为例，在本步骤四中，指令译码单元22需要控制第三复 用器20、第四复用器21分别向第一加法器13、第二加法器14输入交叉数据 （向第一加法器13输入第一乘法器12的输出信号，向第二加法器14输入第 一乘法器11的输出信号），同时触发取反控制器19（第二取反控制器192）将 第一乘法器11的输出信号进行取反操作以及触发取反控制器19（第三取反控 制器193）将第二乘法器12的输出信号进行取反操作。

具体地，所得到的第一路虚部信号为第一累加寄存器17输出的信号（如 图5所示的Vi），所得到的第二路虚部信号为第二累加寄存器18输出的信号（如 图5所示的Ui）。

步骤五：将第一个实现FFT/DFT的装置的第一加法器得到的I信号和第二 个实现FFT/DFT的装置的第一加法器得到的Q信号进行合并，得到基2蝶形 运算的第一路输出信号，以及，将第一个实现FFT/DFT的装置的第二加法器 得到的I信号和第二个实现FFT/DFT的装置的第二加法器得到的Q信号进行 合并，得到基2蝶形运算的第二路输出信号。

需要说明的是，步骤一~步骤二与步骤三~步骤四可以为同时进行的操作， 当所述步骤一~步骤二与步骤三~步骤四同时进行时，需要同时利用两个本发明 实施例一中所述的实现FFT/DFT的装置，如本发明实施例二中所述的第一个 实现FFT/DFT的装置和第二个实现FFT/DFT的装置。

进一步地，本发明实施例二还提供了一种利用实施例一中所述实现 FFT/DFT的装置进行复数乘、复数加、复数乘加、复数乘累加等通用运算的方 法，以及利用所述实现FFT/DFT的装置进行实数乘、实数加、实数乘加、实 数乘累加等通用运算的方法（具体可参见本发明实施例一中的详细描述），本 发明实施例二对此不再赘述。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发 明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及 其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。