快速傅立叶转换器与反快速傅立叶转换器及其方法

摘要

一种快速傅立叶转换器与反快速傅立叶转换器及其方法。所述的快速傅立叶转换器，适用于3,780点的傅立叶转换运算，其包括插序装置、第一转换模块、重新排序模块、乘法单元与第二转换模块。插序装置，接收输入串行值并依据快速傅立叶转换运算的需要提供多点数值给第一、第二转换模块。第一转换模块进行63点快速傅立叶转换运算，输出至插序装置以暂存结果，重新排序模块对插序装置所暂存的结果进行重新排序，而乘法单元对重新排序后的每一点数值乘以适当的旋转因子。第二转换模块对相乘的结果进行60点快速傅立叶转换运算并产生输出串行值。

说明书

技术领域

本发明是有关于快速傅立叶转换器，且特别是有关于一种使用于3,780点的快速傅立叶转换运算的快速傅立叶转换器与反快速傅立叶转换器及其方法。

背景技术

地面数字多媒体及电视广播系统(Digital Television Multimedia Broadcasting，以下简称为DTMB)规范在传送广播信号中，一个正交分频多工(OFDM)符号须使用3,780个子载波。因此，在DTMB系统的调制(Modulation)过程或解调(Demodulation)过程中，需要使用具有3,780点的快速傅立叶转换(Fast Fourier Transform，简称为FFT)模块与反快速傅立叶转换(Inverse Fast Fourier Transform，简称为IFFT)模块。

传统上，3,780点的FFT模块可以间接利用基2(Radix-2)或基4(Radix-4)的算法来实现，例如图1所示的内插至4,096点的3,780点FFT模块。图1是一种内插至4,096点的3,780点快速傅立叶转换处理器100的系统结构图。此快速傅立叶转换处理器100具有内插器102、122，而除了内插器102、122之外，其他主要构件(即标号110的区域所示的各元件)皆为传统的基4的4,096点FFT模块。虽然快速傅立叶转换处理器100通过将3,780点输入值映射至4,096点，再使用技术成熟的4,096点FFT计算，接着将4,096点FFT的计算结果插值回到3,780点后再输出。然而，快速傅立叶转换处理器100会引入较大的相位误差，进而影响DTMB接收器的整体系统性能。另外，使用内插法的快速傅立叶转换处理器100需要图1所示的乒乓结构随机存取存储器(RAM)112、114，导致硬件开销较大。

另外，3,780点的FFT模块还可以利用混合基算法来实现，例如图2所示的混合基(Mixed-radix)的3,780点FFT模块。图2一种混合基的3,780点快速傅立叶转换处理器200的系统结构图。此混合基的3,780点快速傅立叶转换处理器200虽可避免引入较大的相位误差，但须使用5级FFT计算，且需要在各级FFT计算之前后使用如图2所示的串行转并行装置104与并行转串行装置206。再者，此混合基的3780点快速傅立叶转换处理器200还需要在各级FFT计算后(除了最后一级的FFT计算)，进行混序与相位旋转操作。因此，此混合基算法的3,780点快速傅立叶转换处理器200需要至少4个如图2所示的五级混序随机存取存储器(RAM)208、4个五级相位旋转装置210(相位旋转装置通常由乘法器与系数储存单元所构成的)，以及乒乓结构随机存取存储器(RAM)202、212。据此，初步估计，混合基的3,780点快速傅立叶转换处理器200至少需要3,780×4＝15,120储存空间用以处理乒乓结构的输入与输出。所以，混合基算法的3,780点快速傅立叶转换处理器200在实现上，整体硬件开销较大。

发明内容

承上所述，根据本发明的示范实施例，本发明提供使用于3,780点的快速傅立叶转换运算的快速傅立叶转换器与反快速傅立叶转换器及其方法。快速傅立叶转换器将3,780点的快速傅立叶转换运算分解为依序执行多组较少点的快速傅立叶转换运算，并于转换运算流程中的适当位置重新排序运算结果以及将排序的结果乘以适当的旋转因子，以有效率地完成3,780点的快速傅立叶转换运算。

根据本发明的示范实施例，本发明提出一种快速傅立叶转换器，适用于3,780点的快速傅立叶转换运算。所述的快速傅立叶转换器接收一个具有多组3,780点数值的输入串行值，且所述的快速傅立叶转换器包括插序装置、第一转换模块、重新排序模块、旋转因子模块、相位旋转乘法单元与第二转换模块。插序装置具有多个多工器、解多工器与多个储存单元。第一转换模块，耦接于插序装置，用以进行63点的快速傅立叶转换运算。第二转换模块，耦接于插序装置，用以进行60点的快速傅立叶转换运算，以产生输出串行值。重新排序模块，耦接于插序装置，暂存自插序装置接收的每一点数值，并将其所暂存的多点数值进行重新排序后输出。旋转因子模块，储存多个变动性旋转因子，并提供变动性旋转因子的其中的一给相位旋转乘法单元。相位旋转乘法单元，耦接于插序装置、重新排序模块与旋转因子模块，用以将重新排序模块所输出的每一点数值与所接收到的变动性旋转因子相乘，并输出每一点相乘后的数值。其中，插序装置用以接收输入串行值、第一转换模块进行该63点的快速傅立叶转换运算的结果、第二转换模块进行60点的快速傅立叶转换运算的结果与相位旋转乘法单元所输出的此些相乘后的数值，而插序装置用以提供该第一转换单元进行63点的快速傅立叶转换运算所需的多点数值与第二转换单元进行60点的快速傅立叶转换运算所需的多点数值。

根据本发明的示范实施例，本发明所提出的快速傅立叶转换器利用库利-图基算法(Cooley-Tukey method)将快速傅立叶转换运算的过程为分解为第一转换模块与第二转换模块依序计算完成。所述的第一转换模块包括第一转换单元与第二转换单元。第一转换模块利用互质因子算法将63点的快速傅立叶转换运算分解为7点的快速傅立叶转换运算与9点的快速傅立叶转换运算。再者，第一转换单元与第二转换单元还利用威诺格拉德算法(Winograd Small-N algorithm)分别进行7点的快速傅立叶转换运算与9点的快速傅立叶转换运算。另外，第二转换模块包括第三转换单元、第四转换单元与第五转换单元。第二转换模块利用互质因子算法将60点的快速傅立叶转换运算分解为5点的快速傅立叶转换运算、4点的快速傅立叶转换运算与3点的快速傅立叶转换运算。然后，第三转换单元、第四转换单元与第五转换单元利用威诺格拉德算法分别进行5点的快速傅立叶转换运算、4点的快速傅立叶转换运算与3点的快速傅立叶转换运算。

根据本发明的示范实施例，本发明所提出的快速傅立叶转换器进行一种全流水式傅立叶转换运算。所述的全流水式傅立叶转换运算于每一时钟脉冲内接收输入串行值中的一个数值，并且连续性进行多个3,780点的快速傅立叶转换运算。

根据本发明的示范实施例，本发明提出一种反快速傅立叶转换器，适用于3,780点的反快速傅立叶转换运算。所述的反快速傅立叶转换器包括如上述的快速傅立叶转换器的所有元件，并且更包括共轭处理单元。共轭处理单元将反快速傅立叶转换器的输入串行值进行一次共轭运算，以产生输入串行值的共轭，将输入串行值的共轭输入快速傅立叶转换器以进行3,780点的快速傅立叶转换运算以产生输出串行值，并将输出串行值再求一次共轭运算以产生反快速傅立叶输出串行值。其中，共轭处理单元对输入串行值的虚部取反，对输入串行值的实部不变化，或对串行输出值的虚部取反，对串行输出值的实部不变化。

根据本发明的示范实施例，本发明提出一种快速傅立叶转换方法，适用于3,780点的快速傅立叶转换运算。所述的快速傅立叶转换方法包括以下步骤。首先，依序接收输入串行值，其中，输入串行值包括多组3,780点数值。接着，依据7点的快速傅立叶转换运算的需要，对输入串行值进行第一数值选择动作，并对第一数值选择动作的结果进行7点的快速傅立叶转换运算，以产生一第一转换结果。依据9点的快速傅立叶转换运算的需要，对第一转换结果进行第二数值选择动作，并对第二数值选择动作的结果进行9点的快速傅立叶转换运算，以产生第二转换结果。然后，暂存第二转换结果的每一点数值，并对所暂存的多点数值进行重新排序后输出。再者，依序对重新排序后输出的每一点数值进行一相位旋转乘积动作，其中，该相位旋转乘积动作包括依据重新排序后输出的每一点数值选择一适当变动性旋转因子，以及将重新排序后输出的每一点数值乘以适当变动性旋转因子，以输出每一点相乘后的数值。另外，依据5点的快速傅立叶转换运算的需要，对相位旋转乘积动作所输出的每一点相乘后的数值进行第三数值选择动作，并对第三数值选择动作的结果进行5点的快速傅立叶转换运算，以产生第三转换结果。依据4点的快速傅立叶转换运算的需要，对第三转换结果进行第四数值选择动作，并对第四数值选择动作的结果进行4点的快速傅立叶转换运算，以产生第四转换结果。此外，依据3点的快速傅立叶转换运算的需要，对第四转换结果进行第五数值选择动作，并对第五数值选择动作的结果进行3点的快速傅立叶转换运算，以产生输出串行值。

根据本发明的示范实施例，本发明所提出的快速傅立叶转换方法为利用快速傅立叶转换方法利用库利-图基算法将快速傅立叶转换运算分解为由63点的快速傅立叶转换运算与60点的快速傅立叶转换运算依序完成。快速傅立叶转换方法利用互质因子算法分解63点的快速傅立叶转换运算为第一转换子动作与第二转换子动作，其中，第一转换子动作包括利用威诺格拉德算法进行7点的快速傅立叶转换运算，而第二转换子动作包括利用威诺格拉德算法进行9点的快速傅立叶转换运算。另外，快速傅立叶转换方法利用互质因子算法分解60点的快速傅立叶转换运算为第三转换子动作、第四转换子动作与第五转换子动作，其中，该第三转换子动作包括利用威诺格拉德算法进行5点的快速傅立叶转换运算，第四转换子动作包括利用威诺格拉德算法进行4点的快速傅立叶转换运算，而第五转换子动作包括利用威诺格拉德算法进行3点的快速傅立叶转换运算。

根据本发明的示范实施例，本发明所提出的快速傅立叶转换方法为一种全流水式傅立叶转换运算。所述的全流水式傅立叶转换运算于每一时钟脉冲内接收输入串行值中的一个数值，并且连续性进行多个3,780点的快速傅立叶转换运算。

根据本发明的示范实施例，本发明提出一种反快速傅立叶转换方法，适用于3,780点的反傅立叶转换运算。所述的反快速傅立叶转换方法包括如上述的快速傅立叶转换方法的所有特征，并且更包括以下步骤。将反傅立叶转换运算的输入串行值进行一次共轭运算，以产生输入串行值的共轭，将输入串行值的共轭进行3,780点的快速傅立叶转换运算以产生输出串行值，并将输出串行值再求一次共轭运算以产生反快速傅立叶输出串行值。其中，共轭运算对输入串行值的虚部取反，对输入串行值的实部不变化，或对输出串行值的虚部取反，对输出串行值的实部不变化。

基于上述，本发明的示范实施例提供使用于3,780点的快速傅立叶转换运算的快速傅立叶转换器与反快速傅立叶转换器及其方法。快速傅立叶转换器将3,780点的快速傅立叶转换运算分解为依序执行多组较少点的快速傅立叶转换运算，并于转换运算流程中的适当位置重新排序转换运算的结果与乘以适当的旋转因子，以有效率地完成3,780点的快速傅立叶转换运算。据此，所提供的3,780点的快速傅立叶转换运算的快速傅立叶转换器具有全流水线结构，可以实现全流水式傅立叶转换运算，因此具有较高计算效率、较少处理时间延迟与较少硬件资源开销。

附图说明

为让本发明的上述目的、特征和优点能更明显易懂，以下结合附图对本发明的具体实施方式作详细说明，其中：

图1是一种内插至4,096点的3,780点快速傅立叶转换处理器的系统结构图。

图2一种混合基的3,780点快速傅立叶转换处理器的系统结构图。

图3是根据本发明的第一示范实施例所绘示一种快速傅立叶转换器的系统方块图。

图4是根据本发明的第二示范实施例所绘示一种快速傅立叶转换器的系统方块图。

图5是根据本发明的第三示范实施例所绘示一种快速傅立叶转换方法的流程图。

图6是根据本发明的第二示范实施例所绘示一种快速傅立叶转换方法的流程图。

主要元件符号说明：

102、122：内插器                  411：第二转换电路模块

110：传统的基4的4,096点FFT        412：第二解多工器

模块                              414：第二储存单元

112、114、202、212：乒乓结构      418：第二多工器

随机存取存储器                    420：重新排序与相位旋转乘积

204：串行转并行装置          模块

206：并行转串行装置               430：第三转换电路模块

208：五级混讯随机存取存储器       432：第三解多工器

210：五级相位旋转装置             434：第三储存单元

302：插序装置                     438：第三多工器

310：第一转换模块                 440：第四转换电路模块

312、406：第一转换单元            442：第四解多工器

314、416：第二转换单元            444：第四储存单元

322、422：重新排序模块            448：第四多工器

324、424：旋转因子模块            450：第五转换电路模块

326、426：相位旋转乘法单元        452：第五解多工器

330：第二转换模块                 454：第五储存单元

332、436：第三转换单元        458：第五多工器

334、446：第四转换单元        S502～S516：根据本发明的第三

336、456：第五转换单元    示范实施例所绘示一种快速傅立叶

351：选择模块             转换方法的各步骤

352：储存模块                 S602～S620：根据本发明的第二

401：第一转换电路模块     示范实施例所绘示一种快速傅立叶

402：第一解多工器         转换方法的各步骤

404：第一储存单元

408：第一多工器

具体实施方式

现在将详细参照所揭露的示范实施例，所述的示范实施例多绘示于附图中，附带一提的是，整个附图中相同的参考标记用于表示相同或相似的元件。

根据本发明的示范实施例，本发明提供一种使用于3,780点的快速傅立叶转换运算的快速傅立叶转换器与反快速傅立叶转换器及其方法。快速傅立叶转换器将3,780点的快速傅立叶转换运算分解为较少点的快速傅立叶转换运算，并于转换计算流程中的适当位置重新排序转换计算的结果与乘以适当的旋转因子，以有效率地完成3,780点的快速傅立叶转换运算。据此，所提供的3,780点的快速傅立叶转换运算的快速傅立叶转换器具有全流水线结构，可以实现全流水处理，因此具有较高计算效率、较少处理时间延迟与较少硬件资源开销。除此之外，下列所述的所有示范实施例仅是用以说明，并非用以限定本发明。

首先请参照图3，图3是根据本发明的第一示范实施例所绘示一种快速傅立叶转换器300的系统方块图。快速傅立叶转换器300接收一个输入串行值，而输入串行值包括多组3,780点数值。输入串行值的多组3,780点数值是由通讯接收器(未绘示)所接收的多个OFDM符号中所获得的，例如在地面数字多媒体及电视广播系统(DTMB)系统中，各OFDM符号包括3,780个子载波，而输入串行值中的一组3,780点数值则分别代表一个OFDM符号中的3,780个子载波。快速傅立叶转换器300包括插序装置302、第一转换模块310、重新排序模块322、旋转因子模块324、相位旋转乘法单元326、第二转换模块330。其中，插序装置302更包括了选择模块351与储存模块352。以下将以图3继续介绍快速傅立叶转换器300的各元件的运作方式与细部构成元件。

请继续参照图3，快速傅立叶转换器300的插序装置302插序装置，具有多个多工器、解多工器与多个储存单元。第一转换模块310，耦接于插序装置302，用以进行63点的快速傅立叶转换运算。第二转换模块330，耦接于插序装置302，用以进行60点的快速傅立叶转换运算，以产生一输出串行值。第一转换模块310更包括第一转换单元312与第二转换单元314。

重新排序模块322，耦接于插序装置302，暂存自插序装置302接收的每一点数值，并将其所暂存的多点数值进行重新排序后输出。旋转因子模块324，储存多个变动性旋转因子，并提供此些变动性旋转因子的其中的一给相位旋转乘法单元326。相位旋转乘法单元326，耦接于插序装置302、重新排序模块322与旋转因子模块324，用以将重新排序模块322所输出的每一点数值与所接收到的变动性旋转因子相乘，并输出每一点相乘后的数值。其中，插序装置302用以接收输入串行值、第一转换模块310进行63点的快速傅立叶转换运算的结果、第二转换模块330进行60点的快速傅立叶转换运算的结果与相位旋转乘法单元326所输出的此些相乘后的数值，插序装置302用以提供第一转换单元312进行63点的快速傅立叶转换运算所需的多点数值与第二转换单元314进行60点的快速傅立叶转换运算所需的多点数值。

在本示范实施例中，重新排序模块322包括2个乒乓结构的存储器装置(未绘示)，用以提供重新排序动作所须的存储器空间，其中，每一乒乓结构的存储器装置具有至少60个存储器空间以储存60点数值，且采取先进先出的存取运作方式。

在本示范实施例中，快速傅立叶转换器300利用一种库利-图基算法(Cooley-Tukey method)将傅立叶转换运算的流程分解为第一转换模块310与第二转换模块330依序计算完成。更详细地说明，快速傅立叶转换器300利用库利-图基算法将3,780点数值的FFT运算的流程分解为依序执行63点的FFT运算以及60点的FFT运算，其中，第一转换模块310进行63点的FFT运算，而第二转换模块330进行60点的FFT运算算。第一转换模块310包括第一转换单元312与第二转换单元314。另外，第一转换模块310利用一种互质因子算法(Prime Factor Algorithm)将63点的FFT运算进一步分解为一个7点的FFT运算与一个9点的FFT运算，而第一转换单元312与第二转换单元314利用威诺格拉德算法(Winograd Small-N algorithm)分别进行上述的7点的FFT运算与9点的FFT运算。至于第二转换模块330则包括第三转换单元332、第四转换单元334与第五转换单元336。第二转换模块330利用互质因子算法将60点的FFT运算进一步分解为一个5点的FFT运算、一个4点的FFT运算与一个3点的FFT运算。此外，第三转换单元332、第四转换单元334与第五转换单元336利用威诺格拉德算法分别进行5点的FFT运算、4点的FFT运算与3点的FFT运算。

插序装置302用以接收上述的输入串行值、第一转换模块310与第二转换模块330所计算的结果。更进一步地说，插序装置302接收输入串行值并储存输入串行值中部份数点数值，同理，插序装置302接收第一转换模块310与第二转换模块330所计算的结果，并储存第一转换模块310与第二转换模块330所计算的结果中部份数点数值。同时，插序装置302会输出第一转换模块310与第二转换模块330进行FFT运算所需要的数点数值给第一转换模块310与第二转换模块330使用。除此之外，插序装置302接收第一转换单元310的计算结果，并将计算结果的每一点数值输出给重新排序模块322。另外，插序装置302更接收相位旋转乘法单元324所输出的相乘结果，并且储存相乘结果的部分数点数值。

更详细的说明，插序装置302的选择模块351将其接收到的每一点数值选择输出至储存模块352储存或输出给第一转换模块310使用。储存模块352与选择模块351会提供第一转换模块310与第二转换模块330进行计算时所需要的数点数值，其中储存模块352会一次提供多点数值，而选择模块351则会一次提供一点数值。除此之外，选择模块302还会选择第一转换模块310的计算结果与储存模块352所储存的内容的部份数点数值给重新排序模块302，更进一步地说，选择模块302是一次提供一点数值给重新排序模块302，其用以将储存模块352所储存的内容(此内容为第一转换模块310的计算结果中的部份数点数值)中的一点数值或第一转换模块310的计算结果中的一点数值的其中的一提供给重新排序模块302。选择模块351更用以将相位旋转乘法单元326所输出的部份数点数值输出给储存模块352储存，或者将相位旋转乘法单元326所输出的部份数点数值的其中之一提供给第二转换模块330。

上述的选择模块351包括多个选择器，此些选择器的部份连接于第一转换模块310与第二转换模块330。上述的储存模块352具有多个储存单元，每一个储存单元分别被划分给第一转换模块310与第二转换模块330的第一至第四转换单元312、314、332、334，且此些选择器的又一部份连接于上述的储存单元，另外，尚有两个选择器分别与重新排序模块332与相位旋转乘法单元324连接。

简单地说，本示范实施例是将3780点的FFT运算拆解成63点与60点的FFT运算，其中63点的FFT运算又可以利用7点与9点的FFT运算来实现，60点的FFT运算又可以利用5点、4点与3点的FFT运算来完成。选择模块351与储存模块352会提供7点、9点、5点、4点与3点的FFT运算时所需的数点数值给第一至第五转换单元312、314、332、334、346，同时储存模块352会分别储存第一至第四转换单元312、314、332、334的计算结果的部份数点数值。

要注意的是，在处理完63点FFT运算后，选择模块351与储存模块352会提供第二转换单元314的计算结果的数点数值给重新排序模块322来重新排序，接着，相位旋转乘法单元324会将重新排序后的每一点数值与旋转因子模块324所储存的对应的变动性旋转因子相乘，并将相乘后的结果的数点数值传送给选择模块351，以接着进行5点的FFT运算。最后，在第五转换单元进行完3点的FFT运算后，其计算结果即为输出串行值。

以下将以图4对本发明所提供的快速傅立叶转换器的细部构成元件与运作方式作进一步的说明。请参照图4，图4是根据本发明的第二示范实施例所绘示一种快速傅立叶转换器400的系统方块图。在本示范实施例中，快速傅立叶转换器400包括第一转换电路模块401、第二转换电路模块411、第三转换电路模块430、第四转换电路模块440、第四转换电路模块450以及重新排序与相位旋转乘积模块420。重新排序与相位旋转乘积模块420包括重新排序模块422、相位旋转乘法单元424与旋转因子模块426，且重新排序模块422、相位旋转乘法单元424与旋转因子模块426分别与快速傅立叶转换器400中的重新排序模块322、旋转因子模块324以及相位旋转乘法单元326大致上相同。

请继续参照图4，第一转换电路模块401的第一解多工器402于每一时钟脉冲内接收输入串行值的一点数值，并选择性地将所接收的此点数值输出至第一转换电路模块401的第一储存单元储存404或输出给第一转换电路模块401的第一转换单元406使用。第一转换单元406自第一储存单元404所储存的内容接收进行7点的快速傅立叶转换运算所需的6点数值与自第一解多工器401接收其输出的此点数值，以进行7点的快速傅立叶转换运算。第一转换单元进行7点的快速傅立叶转换运算的结果的其中6点数值被储存至第一储存单元404中，其另一点数值则传送至第一转换电路模块401的第一多工器408，而第一多工器408用以接收第一储存单元所储存的7点的快速傅立叶转换运算的结果的其中一点数值与第一转换单元406进行7点的快速傅立叶转换运算的结果的一点数值，并选择性输出所接收的两点数值的其中之一。另外，第一储存单元404包括6个存储器电路，而每一个存储器电路用以储存540点数值。

请继续参照图4，第二转换电路模块411的第二解多工器412于每一时钟脉冲内接收第一多工器408所输出的一点数值，并选择性地将所接收的此点数值输出至第二转换电路模块411的第二储存单元储存414或输出给第二转换电路模块411的第二转换单元416使用。第二转换单元416自第二储存单元414储存所储存的内容接收进行9点的快速傅立叶转换运算所需的8点数值与自第二解多工器412接收其输出的此点数值，以进行9点的快速傅立叶转换运算。第二转换单元416进行9点的快速傅立叶转换运算的结果的其中8点数值被储存至第二储存单元414中，其另一点数值则传送至第二转换电路模块411的第二多工器418，而第二多工器418用以接收第二储存单元414所储存的9点的快速傅立叶转换运算的结果的其中一点数值与第二储存单元414进行9点的快速傅立叶转换运算的结果的一点数值，并选择性输出所接收的两点数值的其中之一至重新排序与相位旋转乘积模块420以进一步进行重新排序以及相位旋转因子乘积等处理。另外，第二储存单元414包括8个存储器电路，而每一个存储器电路用以储存60点数值。

重新排序模块422、相位旋转乘法单元424与旋转因子模块426之间的耦接关系以及信号沟通的方式也与重新排序模块322、旋转因子模块324以及相位旋转乘法单元326大致上相同，在此不重述其细节。重新排序与相位旋转乘积模块420的相位旋转乘法单元426，用以将重新排序模块422所输出的每一点数值与所接收到的变动性旋转因子相乘，并输出每一点相乘后的数值。

请继续参照图4，第三转换电路模块430的第三解多工器432于每一时钟脉冲内接收相位旋转乘法单元426所输出的一点数值，并选择性地将所接收的此点数值输出至第三转换电路模块430的第三储存单元434储存或输出给第三转换电路模块430的第三转换单元436使用。第三转换单元436自第三储存单元434储存所储存的内容接收进行5点的快速傅立叶转换运算所需的4点数值与自第三解多工器432接收其输出的此点数值，以进行5点的快速傅立叶转换运算。第三转换单元436进行5点的快速傅立叶转换运算的结果的其中4点数值被储存至第三储存单元434中，其另一点数值则传送至第三转换电路模块430的第三多工器438，而第三多工器438用以接收第三储存单元434所储存的5点的快速傅立叶转换运算的结果的其中一点数值与第三储存单元434进行5点的快速傅立叶转换运算的结果的一点数值，并选择性输出所接收的两点数值的其中之一。另外，第三储存单元434包括4个存储器电路，而每一个存储器电路用以储存12点数值。

请继续参照图4，第四转换电路模块440的第四解多工器442于每一时钟脉冲内接收第三多工器438所输出的一点数值，并选择性地将所接收的此点数值输出至第四转换电路模块440的第四储存单元444储存或输出给第四转换电路模块440的第四转换单元446使用。第四转换单元446自第四储存单元444储存所储存的内容接收进行4点的快速傅立叶转换运算所需的3点数值与自第四解多工器442接收其输出的此点数值，以进行4点的快速傅立叶转换运算。第四转换单元446进行4点的快速傅立叶转换运算的结果的其中3点数值被储存至第四储存单元444中，其另一点数值则传送至第四转换电路模块440的第四多工器448，而第四多工器448用以接收第四储存单元444所储存的4点的快速傅立叶转换运算的结果的其中一点数值与第四储存单元444进行4点的快速傅立叶转换运算的结果的一点数值，并选择性输出所接收的两点数值的其中之一。另外，第四储存单元444包括3个存储器电路，而每一个存储器电路用以储存3点数值。

请继续参照图4，第五转换电路模块450的第五解多工器452于每一时钟脉冲内接收第四多工器448所输出的一点数值，并选择性地将所接收的此点数值输出至第五转换电路模块430的第五储存单元454储存或输出给第五转换电路模块450的第五转换单元456使用。第五转换单元456自第五储存单元454储存所储存的内容接收进行3点的快速傅立叶转换运算所需的4点数值与自第五解多工器452接收其输出的此点数值，以进行3点的快速傅立叶转换运算。第五转换单元456进行3点的快速傅立叶转换运算的结果的其中2点数值被储存至第五储存单元454中，其另一点数值则传送至第五转换电路模块450的第五多工器458，而第五多工器458用以接收第五储存单元454所储存的3点的快速傅立叶转换运算的结果的其中一点数值与第五储存单元454进行3点的快速傅立叶转换运算的结果的一点数值，并选择性输出所接收的两点数值的其中之一为输出串行值。

值得注意的是，第一储存单元404、第二储存单元414、第三储存单元434、第四储存单元444与第五储存单元454皆包括同步存储器装置，且此些同步存储器装置具有正缘时钟脉冲触发读出与负缘时钟脉冲触发写入的功能。据此，第一储存单元404、第二储存单元414、第三储存单元434、第四储存单元444与第五储存单元454可以于一个时钟脉冲内读出与写入一个数值。另外，第一示范实施例的储存模块352具有类似本示范实施例的第一储存单元404、第二储存单元414、第三储存单元434、第四储存单元444与第五储存单元454的功能。此外，第一示范实施例的选择模块352具有类似本示范实施例的第一解多工器402、第一多工器408、第二解多工器412、第二多工器418、第三解多工器的功能432、第三多工器436、第四解多工器442、第四多工器448、第五解多工器452与第五多工器458的功能。

请继续参照图4，在本示范实施例中，快速傅立叶转换器400可以进行一种全流水式傅立叶转换运算。所述的全流水式傅立叶转换运算于每一时钟脉冲内接收输入串行值中的一个数值，并且连续性计算多个3,780点FFT运算。另外，初步估计，根据本示范实施例，本发明所提供的快速傅立叶转换器仅需要一个相位旋转装置与大约3,880个记忆空间，因此以硬件实现时，可节省硬件开销与电路面积。

根据本发明的其他示范实施例，本发明还提供一种反快速傅立叶转换器(未绘示)包括如上述的快速傅立叶转换器400的所有元件。请参见以下代表FFT运算过程的等式(1)与代表(反快速傅立叶转换)IFFT运算过程的等式(2)。

$Y\left(k\right)=\underset{n=0}{\overset{N-1}{\Sigma }}x\left(n\right)·W_N^{\mathrm{nk}},$0≤k≤N-1等式(1)

其中，Y(k)为通过FFT运算过程后的系数结果，x(n)为FFT运算过程的输入值，为旋转因子，N为采样点的数目并且N等于3,780。

$x\left(n\right)=\frac{1}{N}\underset{n=0}{\overset{N-1}{\Sigma }}Y\left(k\right)·W_N^{-\mathrm{nk}},$0≤k≤N-1等式(2)

其中，x(n)为通过IFFT运算过程后的系数结果，Y(k)为FFT运算过程的输入值，为旋转因子，N为采样点的数目并且N等于3,780。当将等式(1)与等式(2)两者进行比较时可以发现，IFFT运算过程与FFT运算过程的差异仅在于，等式(2)中被相加的每一个频域信号值(即IFFT运算的输入值)所乘以的变动性旋转因子的相位与相应的等式(1)的变动性旋转因子相差180度。另外，等式(2)相加完成后的时域信号值需要进行一调节动作，亦即将输出串行值中的各数值除以3,780。因此，反快速傅立叶转换器除了具有快速傅立叶转换器400的所有元件，反快速傅立叶转换器还包括一个共轭处理单元。此共轭处理单元将反快速傅立叶转换器的输入串行值进行一次共轭运算，以产生输入串行值的共轭。接着，反快速傅立叶转换器将输入串行值的共轭输入快速傅立叶转换器来进行3,780点的快速傅立叶转换运算，以产生输出串行值。然后，共轭处理单元将输出串行值再求一次共轭运算以产生一个反快速傅立叶输出串行值。其中，共轭处理单元对输入串行值的虚部取反，对输入串行值的实部不变化，或对输出串行值的虚部取反，对输出串行值的实部不变化。因此快速傅立叶转换器400可以动态性地设置以进行3,780点的快速傅立叶转换运算或其对应的3,780点的反快速傅立叶转换运算。

介绍完依据本发明的示范实施例所提供的快速傅立叶转换器与反快速傅立叶转换器之后，以下将以图5至图8介绍应用本发明的精神的快速傅立叶转换方法与反快速傅立叶转换方法。

图5是根据本发明的第三示范实施例所绘示一种快速傅立叶转换方法500的流程图。请参照图5，在本示范实施例中，快速傅立叶转换方法500从步骤S502开始，在步骤S502之后进行步骤S504。在步骤S504中，快速傅立叶转换方法500依序接收3,780点FFT运算的串行输入值。另外，在步骤S504中，快速傅立叶转换方法500还利用库利-图基算法将3,780点FFT运算分解为第一转换动作与第二转换动作。第一转换动作为进行一种63点FFT运算，而第二转换动作为进行一种60点FFT运算。请参照前述的等式(1)，上述3,780点FFT运算可被分解为依序进行63点FFT运算与60点FFT运算的状况可以用以下等式(3)至等式(7)来表示。当以下等式(3)、等式(4)与等式(5)成立时，则N1、N2、n1、n2、k1与k2之间的关系可以用以下等式(6)与等式(7)来代表。

N1＝63等式(3)，

N2＝60等式(4)，

N＝N1×N2等式(5)，

n＝N2×n1+n2等式(6)，

k＝k1×N1+k2等式(7)

，其中，N等于3,780，n为等式(1)的加法运算中的索引值，k为等式(1)的加法运算中每一输入参数所须乘以变动性因子的索引值，而n1、n2、k1与k2为库利-图基算法的参数。而上述的等式(1)还可以利用n1、n2、k1与k2改变为以下等式(8)：

$Y(k1,k2)=\underset{n2=0}{\overset{N2-1}{\Sigma }}{W}_{N2}^{n2k2}·(W_N^{n2k1}·\underset{n=0}{\overset{N1-1}{\Sigma }}x(n1,n2)·W_{N1}^{n1k1})$等式(8)。

在步骤S S504之后，进行步骤S506。在步骤S506中，快速傅立叶转换方法500依据63点的FFT运算的需要，对所接收的串行输入值依序进行数值选择动作。在步骤S506之后，进行步骤S508。在步骤S508中，快速傅立叶转换方法500对上述的数值选择动作的结果进行63点的FFT运算(此即第一转换动作)，并产生第一阶段计算结果。上述的63点FFT运算可以用以下等式(9)来表示，而等式(8)可以利用下等式(10)来表示：

$Y_1(k1,n2)=\underset{n=0}{\overset{N1-1}{\Sigma }}x(n1,n2)·W_{N1}^{n1k1}$等式(9)，

$Y(k1,k2)=\underset{n2=0}{\overset{N2-1}{\Sigma }}{W}_{N2}^{n2k2}·(W_N^{n2k1}·Y_1(k1,n2))$等式(10)。

在步骤S508之后，进行步骤S510。在步骤S510中，快速傅立叶转换方法500对第一阶段计算结果的多个数值进行重新排序动作后输出重新排序的结果。在步骤S510之后，进行步骤S512。

在步骤S512中，快速傅立叶转换方法500依序对重新排序动作所输出的每一数值进行相位乘积动作，亦即将每一数值乘以适当的变动性旋转因子，并输出相乘后的各数值。上述的相位乘积动作与所产生的相乘后的各数值可以进一步用以下等式(11)来表示：

${Y_1}^{*}(k1,n2)=W_{N1}^{n1k1}·Y_1(k1,n2)$等式(11)。

在步骤S512之后，进行步骤S514。在步骤S514中，快速傅立叶转换方法500依据60点的快速傅立叶转换运算的需要，对相位乘积动作所产生的相乘后的各数值进行数值选择动作。

在步骤S516中，快速傅立叶转换方法5002对数值选动作的结果进行一种60点FFT运算(此即第二转换动作)，并产生输出串行值。上述的60点FFT运算可以用以下等式(12)来表示：

$Y_1(k1,k2)=\underset{n2=0}{\overset{N2-1}{\Sigma }}{W}_{N2}^{n2k2}·\left({Y_1}^{*}(k1,n2)\right)$等式(12)。

在步骤S516之后，进行步骤S518，到此快速傅立叶转换方法500结束。然而本发明并不限定于上述，除了以上所述的快速傅立叶转换方法500的外，依据本发明的其他示范实施例，本发明所提供的快速傅立叶转换方法还可以于流程中进行一种重新排序动作，以提高快速傅立叶转换流程的执行效率。

在本示范实施例中，以上所述将3,780点的FFT运算分解为一种63点的FFT运算与一种60点的FFT运算，而在分解后的状况可以用以下等式(13)来表示：

$Y\left(k\right)=\underset{n=0}{\overset{N-1}{\Sigma }}x\left(n\right)·W_N^{\mathrm{nk}},$等式(13)。

0≤n1≤N1，0≤n2≤N2，0≤k1≤N1，0≤k2≤N2，N＝N1×N2

快速傅立叶转换方法500的步骤S506中的60点FFT运算利用互质因子算法可以被进一步分解为第一转换子动作(包括利用威诺格拉德算法进行7点FFT运算)与第二转换子动作(包括利用威诺格拉德算法进行9点FFT运算)。为了计算出7点FFT运算与9点FFT运算的结果，可以利用上述的等式(5)中N1与N2互质的条件，并应用以下等式(14)至等式(19)来求得n1、n2、k1与k2的数值：

n＝MOD((A×n1+B×n2)，N)等式(14)，

k＝MOD((C×k1+D×k2)，N)等式(15)，

AD≡0mod N等式(16)，

BC≡0mod N等式(17)，

AC≡N2mod N等式(18)，

BD≡N1mod N等式(19)

其中，MOD(U，V)为一余数函数可以获得U被V除以所得到的余数，N等于3,780，n为上述的等式(1)的加法运算中的索引值，k为等式(1)的加法运算中每一输入参数所须乘以变动性因子的索引值，n1、n2、k1与k2为库利-图基算法的参数，N1为63，N2为60，而A、B、C与D为求取等式(14)或等式(15)中n或k的必要参数。举例说明，等式(18)所表达的含义是：A和C的乘积对N取模的结果等于N2，也就是(A*C)除以N的余数为N2。其余的等式(16)、(17)、(19)可以依据等式(18)的原理来分别求取A和D的乘积、B和C的乘积以及B和D的乘积。将这些A和D的乘积、B和C的乘积、A和C的乘积以及B和D的乘积整体比较后，可以分别求得A、B、C与D的数值。

利用以上等式(14)至等式(19)的条件，当N1为63时，N1可以分解为9与7两个互质因子的乘积，因此可以获得A为14、B为18、C为14以及D为18的结果。将A为14、B为18、C为14以及D为18的结果输入以上所述的等式(14)与等式(15)即可获得n1、n2、k1与k2的数值，并可进一步利用n1、n2、k1与k2的数值，在等式(8)中分别获得7点FFT运算与9点FFT运算的结果。

快速傅立叶转换方法500的步骤S514中的60点FFT运算利用互质因子算法可以被进一步分解为第三转换子动作(包括进行5点的FFT运算)、第四转换子动作(包括进行4点的FFT运算)与第五转换子动作(包括进行3点的FFT运算)。为了计算出5点FFT运算、4点FFT运算与3点FFT运算的结果，可以利用以上等式(14)至等式(19)的条件。据此，当N2为60时，N2可以分解为3与20两个互质因子的乘积，因此可以获得A为20、B为3、C为40以及D为21的结果。若再进一步将20分解为4与5两个互质因子的乘积时，则可以获得A为4、B为5、C为16以及D为25的结果。另外，将A为4、B为5、C为16以及D为25的结果输入以上所述的等式(14)与等式(15)即可获得n1、n2、k1与k2的数值，并可进一步利用n1、n2、k1与k2的数值，在等式(8)中分别获得5点FFT运算与4点FFT运算的结果。

图6是根据本发明的第二示范实施例所绘示另一种快速傅立叶转换方法600的流程图。请参照图6，在本示范实施例中，快速傅立叶转换方法600的步骤S602、S604与上述的步骤S502、S504相类似，在此不重述其细节。在步骤S604之后，进行步骤S606。在步骤S606中，快速傅立叶转换方法600依据7点FFT的运算的需要对输入串行值进行第一数值选择动作，并产生第一转换结果。步骤S602与步骤S604的运作细节，可以参照上述的快速傅立叶转换器400的第一转换电路模块401的内部运作原理。在步骤S606之后，进行步骤S608。

在步骤S608中，快速傅立叶转换方法600依据9点的FFT运算的需要，对第一转换结果的多个数值进行第二数值选择动作，并产生第二转换结果。步骤S608的运作细节，可以参照上述的快速傅立叶转换器400的第二转换电路模块411的内部运作原理。在步骤S608之后，进行步骤S610。

在步骤S610中，快速傅立叶转换方法600对第二转换结果的多个数值进行重新排序动作后输出以进行相位旋转乘积处理。步骤S610的运作细节，可以参照上述的快速傅立叶转换器400的重新排序模块422的内部运作原理。在步骤S610之后，进行步骤S612。

在步骤S612中，快速傅立叶转换方法600依序对重新排序所输出的各数值乘以适当的变动性旋转因子后，输出相乘后的各数值。步骤S612的运作细节，可以参照上述的快速傅立叶转换器400的旋转因子模块424与相位旋转乘法单元426的内部运作原理。在步骤S612之后，进行步骤S614。

在步骤S614中，快速傅立叶转换方法600依据5点的FFT运算的需要，对上述的相乘后的各数值进行第三数值选择动作，并产生第三转换结果。步骤S614的运作细节，可以参照上述的快速傅立叶转换器400的第三转换电路模块430的内部运作原理。在步骤S614之后，进行步骤S616。

在步骤S616中，快速傅立叶转换方法600依据4点的FFT运算的需要，对上述的第三转换结果进行第四数值选择动作，并产生第四转换结果。步骤S616的运作细节，可以参照上述的快速傅立叶转换器400的第四转换电路模块440的内部运作原理。在步骤S616之后，进行步骤S618。

在步骤S618中，快速傅立叶转换方法600依据3点的FFT运算的需要，对上述的第三转换结果进行第五数值选择动作，并产生第五转换结果。步骤S618的运作细节，可以参照上述的快速傅立叶转换器400的第五转换电路模块450的内部运作原理。在步骤S618之后，进行步骤S620，到此快速傅立叶转换方法600结束。此外，如前所述，快速傅立叶转换方法500、600为一种全流水式傅立叶转换运算。全流水式傅立叶转换运算于每一时钟脉冲内接收输入串行值中的一个数值，并且连续性进行多个3,780点的FFT运算。

根据本发明的其他示范实施例，本发明还提供一种反快速傅立叶转换方法包括如上述的快速傅立叶转换方法600的所有步骤。另外，反快速傅立叶转换方法还包括一个共轭运算。更精确的说明为，将反快速傅立叶转换器的输入串行值进行一次共轭运算，以产生输入串行值的共轭。接着，将输入串行值的共轭利用快速傅立叶转换方法600来进行3,780点的快速傅立叶转换运算，以产生输出串行值。然后，将输出串行值再求一次共轭运算以产生一个反快速傅立叶输出串行值。其中，上述的共轭运算对输入串行值的虚部取反，对输入串行值的实部不变化，或对输出串行值的虚部取反，对输出串行值的实部不变化。因此快速傅立叶转换方法600可以动态性地被设置以进行3,780点的快速傅立叶转换运算或其对应的3,780点的反快速傅立叶转换运算。

综上所述，根据本发明的多个示范实施例，本发明提供使用于3,780点的FFT运算的快速傅立叶转换器与反快速傅立叶转换器及其方法。快速傅立叶转换器将3,780点的FFT运算分解为依序执行多组较少点的FFT运算，并于转换计算流程中的适当位置重新排序转换计算的结果并且乘以适当的旋转因子，以有效率地完成3,780点的FFT运算。此外，快速傅立叶转换器具有全流水线结构，可以实现全流水处理，可以减少存取存储器的数量，减少相位旋转的次数，并进而减少整体硬件所须的面积。据此，所提供的3,780点的FFT运算的快速傅立叶转换器具有较高计算效率、较少处理时间延迟与较少硬件资源开销的优点。

虽然本发明已以较佳实施例揭示如上，然其并非用以限定本发明，任何本领域技术人员，在不脱离本发明的精神和范围内，当可作些许的修改和完善，因此本发明的保护范围当以权利要求书所界定的为准。