CN113378108A - 音频处理装置的快速傅立叶变换电路 - Google Patents

Abstract

本发明提出一种音频处理装置的快速傅立叶变换电路，用以进行N点快速傅立叶变换并包括存储器电路以及蝴蝶运算单元电路。蝴蝶运算单元电路自存储器电路读取2点输入数据，依据旋转因子对2点输入数据进行蝴蝶运算以产生2点输出数据，并将2点输出数据写入存储器电路。蝴蝶运算单元电路包括乘法器与多个加减法器。乘法器依序于多个时钟周期将2点输入数据其中之一者的实部系数或虚部系数乘上旋转因子的实部系数或虚部系数。乘法器分别于时钟周期其中之每一者内执行一次乘法运算。多个加减法器执行加减法运算，致使蝴蝶运算单元电路产生2点输出数据。

Description

音频处理装置的快速傅立叶变换电路

技术领域

本发明是有关于一种指音频处理电路，且特别是有关于一种用于音频处理装置的快速傅立叶变换电路。

背景技术

随着科技的进步，越来越多的电子装置开始使用语音控制，语音控制今后将成为大多数电子装置常用的用户界面。由此可知，语音识别(Speech Recognition)的辨识率将直接影响用户使用电子装置的用户体验。在语音识别的实现中，快速傅立叶变换(FastFourier Transform，FFT)已经被广泛应用，其功能为把时域数据转换为频域数据，以依据语音信号的频谱特性来进行语音识别。更进一步而言，进行语音识别的音频处理装置大都具有一个由硬件实现的快速傅立叶变换电路。

此外，快速傅立叶变换电路的硬件架构设计将根据不同领域的需求而有不同的设计，像是适合高速应用的流水线(Pipeline)架构以及具有较低硬件成本的存储器复用(Memory-based)架构等等皆已经被广泛使用。其中，流水线架构可以让输入数据与输出数据源源不断地进出，在处理效能与数据吞吐量上领先存储器复用架构，但流水线架构比存储器复用架构需要更多的硬件消耗。相较之下，存储器复用架构的优点与特色则是电路面积较小且所需的存储空间也较少，但其处理效能较慢。

图1是说明8点快速傅立叶变换的信号流程图。图2是说明流水线架构的快速傅立叶变换电路。请同时参照图1至图2，流水线架构的快速傅立叶变换电路20所执行的8点快速傅立叶变换是以2点为基底。流水线架构的快速傅立叶变换电路20可包括多个存储器电路M1～M4，以及三阶段的蝴蝶运算模块B1～B3。于此，蝴蝶运算模块B1～B3可各自包括4个基2蝴蝶运算单元。存储器电路M1～M4分别设置在每两级蝴蝶运算模块B1～B3之间与数据输入与输出的地方。

蝴蝶运算模块B1可自存储器电路M1读取输入数据x[0]～x[7]来进行第一阶段蝴蝶运算(即4组基2蝴蝶运算)，并将蝴蝶运算模块B1的运算结果写入存储器电路M2。接着，蝴蝶运算模块B2可自存储器电路M2读取蝴蝶运算模块B1的运算结果来进行第二阶段蝴蝶运算(即4组基2蝴蝶运算)，并将蝴蝶运算模块B2的运算结果写入存储器电路M3。依此类推。第三阶段的蝴蝶运算模块B3可在执行第三阶段蝴蝶运算之后将输出数据X[0]～X[7]写入存储器电路M4。

图3是说明流水线架构的8点基2快速傅立叶变换运算的时序示意图。请参照图2与图3，于时钟周期CC1，第一笔输入数据写入存储器电路M1。于时钟周期CC2，蝴蝶运算模块B1可自存储器电路M1读取第一笔输入数据来进行第一阶段蝴蝶运算，并将运算结果写入存储器电路M2。于时钟周期CC3，蝴蝶运算模块B2可针对第一笔输入数据进行第二阶段蝴蝶运算，并将运算结果写入存储器电路M3。于时钟周期CC4，蝴蝶运算模块B2可针对第一笔输入数据进行第三阶段蝴蝶运算，并将运算结果写入存储器电路M3。于时钟周期CC5，存储器电路M3提供输出数据给其他后续电路。需注意的是，藉由将每一阶段的蝴蝶运算结果皆存入对应的存储器，形成流水线架构的各个硬件模块可不间断地操作于多个时钟周期。因此，如图3所示，快速傅立叶变换电路10需要5个时钟周期来完成一笔输入数据的FFT运算，并需要6个时钟周期来完成两笔输入数据的FFT运算。

另一方面，图4是说明存储器复用架构的快速傅立叶变换电路。请同时参照图1与图4，存储器复用架构的快速傅立叶变换电路40所执行的8点快速傅立叶变换是以2点为基底。存储器复用架构的快速傅立叶变换电路40可包括相互耦接的存储器电路M5以及蝴蝶运算模块B4。于此，蝴蝶运算模块B4可包括4个基2蝴蝶运算单元。相较于图2的快速傅立叶变换电路10包括12个蝴蝶运算单元，快速傅立叶变换电路40仅需包含4个蝴蝶运算单元。蝴蝶运算模块B4可自存储器电路M5读取输入数据x[0]～x[7]来进行4组基2蝴蝶运算，并将运算结果写回存储器电路M5。接着，蝴蝶运算模块B4可自存储器电路M5读取第一阶段蝴蝶运算的运算结果来进行第二阶段蝴蝶运算，并将运算结果写回存储器电路M5。依此类推。蝴蝶运算模块B4可在依据第二阶段蝴蝶运算的运算结果执行第三阶段蝴蝶运算之后，将输出数据X[0]～X[7]写回存储器电路M5。需注意的是，当蝴蝶运算模块B4每次执行完蝴蝶运算之后，会将运算结果写回存储器电路M5并覆盖掉先前的储存数据。

图5是说明存储器复用架构的8点基2快速傅立叶变换运算的时序示意图。请参照图4与图5，于时钟周期CC1，第一笔输入数据写入存储器电路M5。于时钟周期CC2，蝴蝶运算模块B4可自存储器电路M5读取第一笔输入数据来进行第一阶段蝴蝶运算，并将运算结果写入存储器电路M5。于时钟周期CC3，蝴蝶运算模块B4可针对第一笔输入数据进行第二阶段蝴蝶运算，并将运算结果写入存储器电路M5。于时钟周期CC4，蝴蝶运算模块B4可针对第一笔输入数据进行第三阶段蝴蝶运算，并将运算结果写入存储器电路M5。于时钟周期CC5，存储器电路M5提供输出数据给其他后续电路。如图5所示，快速傅立叶变换电路40需要5个时钟周期来完成一笔输入数据的FFT运算，但因为快速傅立叶变换电路40于每一阶段蝴蝶运算重复使用存储器电路M5，因此需要9个时钟周期来完成两笔输入数据的FFT运算。比较图3与图5可知，流水线架构的快速傅立叶变换电路10需要5个时钟周期来完成两笔输入数据的FFT运算，存储器复用架构的快速傅立叶变换电路40需更长时间(即9个时钟周期)来完成两笔输入数据的FFT运算。

可知的，用以实现快速傅立叶变换的硬件电路将直接影响硬件成本、电路面积与处理效能等等。因而，随着语音识别的应用越来越广，如何设计符合语音识别需求的快速傅立叶变换电路为本领域技术人员关心的重要议题之一。

发明内容

有鉴于此，本发明提出一种音频处理装置的快速傅立叶变换电路，其可有效降低硬件成本并节省电路面积。

本发明提供一种音频处理装置的快速傅立叶变换电路，其用以进行N点快速傅立叶变换，且N为2的幂。快速傅立叶变换电路包括存储器电路以及蝴蝶运算单元电路，蝴蝶运算单元电路耦接存储器电路。蝴蝶运算单元电路自存储器电路读取2点输入数据，依据旋转因子对2点输入数据进行蝴蝶运算以产生2点输出数据，并将2点输出数据写入存储器电路。蝴蝶运算单元电路包括乘法器与多个加减法器。乘法器依序于多个时钟周期将2点输入数据其中之一者的实部系数或虚部系数乘上旋转因子的实部系数或虚部系数。乘法器分别于时钟周期其中之每一者内执行一次乘法运算。多个加减法器耦接乘法器，依据乘法器的输出或2点输入数据其中之另一者的实部系数或虚部系数执行加减法运算，致使蝴蝶运算单元电路产生2点输出数据。

本发明提供一种音频处理装置的快速傅立叶变换电路，其用以进行N点快速傅立叶变换，且N为2的幂。快速傅立叶变换电路包括多个基2(radix-2)蝴蝶运算电路。每个基2蝴蝶运算电路执行包括：接收输入数据，并依据M个旋转因子其中之一对输入数据进行蝴蝶运算以产生输出数据。蝴蝶运算包括基于复数运算而分解出的多个加减法运算及多个乘法运算，且M为小于N/2的正整数。每个基2蝴蝶运算电路依序于多个时钟周期执行加减法运算及乘法运算，且在每个时钟周期内最多执行一次乘法运算。

基于上述，于本发明的实施例中，可通过重复使用乘法器的方式来实现FFT的蝴蝶运算，从而大幅减少乘法器的个数。并且，透过优化记录有旋转因子的查找表，可有效减少只读存储器的使用量。藉此，本发明实施例的快速傅立叶变换电路可大幅减少硬件消耗并使电路面积下降。

为让本发明的上述特征和优点能更明显易懂，下文特举具体实施方式，并配合附图作详细说明如下。

附图说明

包含附图以便进一步理解本发明，且附图并入本说明书中并构成本说明书的一部分。附图说明本发明的实施例，并与描述一起用于解释本发明的原理。

图1是说明8点快速傅立叶变换的信号流程图。

图2是说明流水线架构的快速傅立叶变换电路。

图3是说明流水线架构的8点基2快速傅立叶变换运算的时序示意图。

图4是说明存储器复用架构的快速傅立叶变换电路。

图5是说明存储器复用架构的8点基2快速傅立叶变换运算的时序示意图。

图6是依照本发明一实施例的用于语音识别的音频处理装置的示意图。

图7是依照本发明一实施例的快速傅立叶变换电路的示意图。

图8是依照本发明一实施例的基2蝴蝶运算的示意图。

图9是依照本发明一实施例的快速傅立叶变换电路的操作示意图。

图10依照本发明一实施例的基2蝴蝶运算的时序示意图。

图11是依照本发明一实施例的快速傅立叶变换电路进行基2蝴蝶运算的流程示意图。

附图标记说明

10：音频处理装置；

M1～M5：存储器电路；

B1～B4：蝴蝶运算模块；

CC1～CC10、CC91～CC96：时钟周期；

20、40：快速傅立叶变换电路；

61：预处理电路；

62：快速傅立叶变换电路；

63：功率谱转换电路；

s1：时域取样数据；

d1：经预处理数据；

d2：频谱系数；

621：存储器电路；

622：蝴蝶运算单元电路；

623：旋转因子存储器电路；

6221：乘法器；

6222、6222_1、6222_2：加减法器。

具体实施方式

现将详细地参考本发明的示范性实施例，示范性实施例的实例说明于附图中。只要有可能，相同组件符号在图式和描述中用来表示相同或相似部分。

图6是依照本发明一实施例的用于语音识别的音频处理装置的示意图。请参照图6，用于语音识别的音频处理装置10可包括预处理电路61、快速傅立叶变换电路62，以及功率谱转换电路63。预处理电路61对时域取样数据s1进行音频预处理而产生经预处理数据d1。音频预处理可包括预加重(Pre-emphasis)处理、音框化(Frame blocking)处理，以及加窗处理等等。快速傅立叶变换电路62可对经预处理数据d1进行FFT运算而产生包括实部系数与虚部系数的频谱系数d2。详细而言，时域取样数据s1是对模拟音频信号进行取样而产生，而取样频率例如是8K赫兹或16K赫兹等等。频谱系数d2是透过对一取样时段(亦即一音框)内的经预处理数据d1进行FFT运算而产生。功率谱转换电路63可对这些频谱系数d2进行功率谱转换取得频谱特征，亦即计算频谱系数d1的实部系数平方与频谱系数d1的虚部系数平方的总和。接着，音频处理装置10可依据功率谱转换的结果进行后续语音识别处理。

图7是依照本发明一实施例的快速傅立叶变换电路的示意图。请参照图7，音频处理装置10的快速傅立叶变换电路62用以进行N点快速傅立叶变换，其中N为2的幂。N可以等于256、512或1024等等，其可依据一个音框里的取样数目而决定。举例而言，假设预处理电路61所提供的一个音框包括512个取样点，则音频处理装置10的快速傅立叶变换电路62用以进行512点快速傅立叶变换。假设预处理电路61所提供的一个音框少于N个取样点，则音频处理装置10的快速傅立叶变换电路62可对经处理后得到的N点数据进行N点快速傅立叶变换。例如，当预处理电路61所提供的一个音框包括400个取样点时，可将数据补足至N点(例如，补入112个‘0’)后，由快速傅立叶变换电路62进行512点快速傅立叶变换。

于一实施例中，快速傅立叶变换电路62包括存储器电路621、蝴蝶运算单元电路622，以及旋转因子存储器电路623。存储器电路621用以缓存FFT运算时的数据，可以是静态随机存取存储器(static random-access memory，SRAM)，但不以此为限制。存储器电路621可经由内部总线耦接蝴蝶运算单元电路622。此外，旋转因子存储器电路63耦接快速傅立叶变换电路62，并用以储存旋转因子，可以为只读存储器(read-only memory，ROM)或其他非瞬时存储器。

于一实施例中，快速傅立叶变换电路62所执行的N点快速傅立叶变换是以R点为基底，亦即N点快速傅立叶变换包括log_RN级的阶段运算。R为大于1的整数。然而，为了清楚说明本发明，以下将先以R＝2为范例继续说明。亦即，蝴蝶运算单元电路622是执行基2蝴蝶运算。蝴蝶运算单元电路622自存储器电路621读取2点输入数据，并依据旋转因子对2点输入数据进行基2蝴蝶运算以产生2点输出数据。于此，快速傅立叶变换电路62可自旋转因子存储器电路63读取旋转因子。之后，蝴蝶运算单元电路622再将2点输出数据写入存储器电路621。于一实施例中，蝴蝶运算单元电路622自存储器电路621的多个存储地址读取2点输入数据，并将蝴蝶运算所产生的2点输出数据覆写回相同的存储地址，以重复使用存储器电路621的存储空间。

需说明的是，上述的蝴蝶运算包括基于复数运算而分解出的多个加减法运算及多个乘法运算。图8是依照本发明一实施例的基2蝴蝶运算的示意图。蝴蝶运算单元电路622自存储器电路621读取2点输入数据，其分别为x₁[k]与x₂[k]。蝴蝶运算单元电路622进行基2蝴蝶运算而产生2点输出数据，其分别为x₁[k]+W_N ^k·x₂[k]与x₁[k]-W_N ^k·x₂[k]。由此可知，基2蝴蝶运算需要2次的加减法运算以及1次的复数乘法运算。此外，复数乘法运算可等效为4次乘法运算以及3次加减法运算。所以，蝴蝶运算单元电路622进行一次基2蝴蝶运算需要执行4次乘法运算与5次加减法运算。举例而言，假设x₁[k]＝e+fi，x₂[k]＝a+bi且旋转因子W_N ^k＝c+di，则x₁[k]+W_N ^k·x₂[k]＝e+ac-bd+i(f+ad+bc)且x₁[k]-W_N ^k·x₂[k]＝e-ac+bd-i(f-ad-bc)，其需要4次乘法运算与5次加减法运算来产生2点输出数据的两个实部系数与两个虚部系数。

于一实施例中，蝴蝶运算单元电路622可依序于多个时钟周期执行加减法运算及乘法运算，且在每个时钟周期内最多执行一次乘法运算。换言之，蝴蝶运算单元电路622可使用单一乘法器来执行多个乘法运算。更详细而言，蝴蝶运算单元电路622可包括乘法器6221与耦接乘法器6221的多个加减法器6222。乘法器6221可依序于多个时钟周期将2点输入数据其中之一者(例如前述范例的x₂[k])的实部系数或虚部系数乘上旋转因子的实部系数或虚部系数。需注意的是，乘法器6221分别于时钟周期其中之每一者内执行最多一次乘法运算。多个加减法器6222依据乘法器6221的输出或2点输入数据其中之另一者(例如前述范例的x₁[k])的实部系数或虚部系数执行加减法运算，致使蝴蝶运算单元电路622可据以产生2点输出数据。

于一实施例中，蝴蝶运算单元电路622可依序于多个时钟周期执行加减法运算及乘法运算，而这些时钟周期包括第一时钟周期、第二时钟周期以及第三时钟周期。乘法器6221于第一时钟周期将2点输入数据其中之一者的实部系数乘上旋转因子的实部系数与虚部系数其中之一而产生第一乘法输出，并且乘法器6221于第二时钟周期将2点输入数据其中之一者的虚部系数乘上旋转因子的实部系数与虚部系数其中之另一而产生第二乘法输出。

详细而言，于一实施例中，乘法器6221可于第一时钟周期先将2点输入数据其中之一者的实部系数乘上旋转因子的实部系数而产生第一乘法输出，然后乘法器6221可于第二时钟周期将2点输入数据其中之一者的虚部系数乘上旋转因子的虚部系数而产生第二乘法输出。或者，于一实施例中，乘法器6221可于第一时钟周期先将2点输入数据其中之一者的虚部系数乘上旋转因子的虚部系数而产生第一乘法输出，然后乘法器6221可于第二时钟周期将2点输入数据其中之一者的实部系数乘上旋转因子的实部系数旋转因子的实部系数而产生第二乘法输出。需注意的是，上述两种配置的第一乘法输出与第二乘法输出可用以产生2点输出数据的实部系数。

于一实施例中，加减法器6222包括第一加减法器与第二加减法器。在已经产生用以产生2点输出数据的实部系数的第一乘法输出与第二乘法输出的情况下，第一加减法器于第二时钟周期依据第一乘法输出与第二乘法输出进行加减法操作而获取第一加减法输出。并且，第二加减法器于第二时钟周期依据第一加减法输出与2点输入数据其中之另一者的实部系数进行加减法操作而获取2点输出数据其中之一者的实部系数。接着，第二加减法器可于第三时钟周期依据第一加减法输出与2点输入数据其中之另一者的实部系数进行加减法操作而获取2点输出数据其中之另一者的实部系数。

另一方面，于一实施例中，乘法器6221可于第一时钟周期先将2点输入数据其中之一者的实部系数乘上旋转因子的虚部系数而产生第一乘法输出，然后乘法器6221可于第二时钟周期将2点输入数据其中之一者的虚部系数乘上旋转因子的实部系数而产生第二乘法输出。或者，于一实施例中，乘法器6221可于第一时钟周期先将2点输入数据其中之一者的虚部系数乘上旋转因子的实部系数而产生第一乘法输出，然后乘法器6221可于第二时钟周期将2点输入数据其中之一者的实部系数乘上旋转因子的虚部系数而产生第二乘法输出。需注意的是，上述两种配置的第一乘法输出与第二乘法输出可用以产生2点输出数据的虚部系数。

于一实施例中，加减法器6222包括第一加减法器与第二加减法器。在已经产生用以产生2点输出数据的虚部系数的第一乘法输出与第二乘法输出的情况下，第一加减法器于第二时钟周期依据第一乘法输出与第二乘法输出进行加减法操作而获取第一加减法输出。并且，第二加减法器于第二时钟周期依据第一加减法输出与2点输入数据其中之另一者的虚部系数进行加减法操作而获述2点输出数据其中之一者的虚部系数。然后，第二加减法器可于第三时钟周期依据第一加减法输出与2点输入数据其中之另一者的虚部系数进行加减法操作而获取2点输出数据其中之另一者的虚部系数。

为了清楚说明，图9是依照本发明一实施例的快速傅立叶变换电路的操作示意图。图10依照本发明一实施例的基2蝴蝶运算的时序示意图。于此，假设2点输入数据其中之一者为x₂[k]＝a+bi，2点输入数据其中之另一者为x₁[k]＝e+fi且旋转因子W_N ^k＝c+di，以方便说明。此外，加减法器6222可包括第一加减法器6222_1与第二加减法器6222_2。请同时参照图9与图10，于时钟周期CC91，蝴蝶运算单元电路622自存储器电路621以及旋转因子存储器电路623分别读取输入数据x₂[k]的实部系数a以及旋转因子W_N ^k的实部系数c，并将其记录于缓存器电路中。

于时钟周期CC92，蝴蝶运算单元电路622自存储器电路621以及旋转因子存储器电路623分别读取输入数据x₂[k]的虚部系数b以及旋转因子W_N ^k的虚部系数d，并将其记录于缓存器电路中。乘法器6221可于时钟周期CC92先将输入数据x₂[k]的实部系数a乘上旋转因子W_N ^k的实部系数c而产生乘法输出a*c，并将其记录于缓存器电路中。

于时钟周期CC93，蝴蝶运算单元电路622自存储器电路621读取输入数据x₁[k]的实部系数e，并将其记录于缓存器电路中。乘法器6221可于时钟周期CC93将输入数据x₂[k]的虚部系数b乘上旋转因子W_N ^k的虚部系数d而产生乘法输出b*d，并将其记录于缓存器电路中。并且，第一加减法器6222_1于时钟周期CC93依据乘法输出a*c与乘法输出b*d进行减法操作而获取减法输出a*c-b*d，并将其记录于缓存器电路中。并且，第二加减法器6222_2于时钟周期CC93依据减法输出a*c-b*d与输入数据x₁[k]的实部系数e进行加法操作而获取输出数据的实部系数e+(a*c-b*d)。

于时钟周期CC94，蝴蝶运算单元电路622自存储器电路621读取输入数据x₁[k]的虚部系数f，并将其记录于缓存器电路中。乘法器6221可于时钟周期CC94将输入数据x₂[k]的实部系数a乘上旋转因子W_N ^k的虚部系数d而产生乘法输出a*d并将其记录于缓存器电路中。并且，第二加减法器6222_2于时钟周期CC94依据减法输出a*c-b*d与输入数据x₁[k]的实部系数e进行减法操作而获取另一输出数据的实部系数e-(a*c-b*d)。

于时钟周期CC95，乘法器6221可于时钟周期CC95将输入数据x₂[k]的虚部系数b乘上旋转因子W_N ^k的实部系数c而产生乘法输出b*c，并将其记录于缓存器电路中。并且，第一加减法器6222_1于时钟周期CC95依据乘法输出a*d与乘法输出b*c进行加法操作而获取加法输出a*d+b*c，并将其记录于缓存器电路中。并且，第二加减法器6222_2于时钟周期CC95依据加法输出a*d+b*c与输入数据x₁[k]的虚部系数f进行加法操作而获取输出数据的虚部系数f+(a*d+b*c)。最后，于时钟周期CC96，第二加减法器6222_2依据加法输出a*c+b*d与输入数据x₁[k]的虚部系数f进行减法操作而获取另一输出数据的虚部系数f-(a*d+b*c)

基于图9与图10的说明可知，每一次的基2蝴蝶运算可分成6个时钟周期来执行。乘法器6221分别于时钟周期CC92～时钟周期CC95执行一次乘法操作。2点输出数据的实部系数与虚部系数将分时输出。需说明的是，图9与图10的实施例是以先产生2点输出数据的实部系数接着再产生2点输出数据的虚部系数为例进行说明，但本发明不限制于此。此外，于另一实施例中，可先产生2点输出数据的虚部系数接着再产生2点输出数据的实部系数。藉此，蝴蝶运算单元电路622可透过重复使用一个乘法器6221来完成一次基2蝴蝶运算，从而大幅降低硬件消耗。

于一实施例中，快速傅立叶变换电路62可包括一个蝴蝶运算单元电路622，以藉由重复使用蝴蝶运算单元电路622来完成FFT运算。于一实施例中，快速傅立叶变换电路62可包括与蝴蝶运算单元电路622结构相似的多个基2(radix-2)蝴蝶运算电路。于一实施中，这些基2(radix-2)蝴蝶运算电路可组成一或多个基数大于2的蝴蝶运算电路，例如基4蝴蝶运算电路或基8蝴蝶运算电路等等。或者，于一实施中，快速傅立叶变换电路62内的这些基2(radix-2)蝴蝶运算电路可并行执行某一阶段的所有蝴蝶运算。举例而言，快速傅立叶变换电路62可包括与蝴蝶运算单元电路622结构相似的4个基2蝴蝶运算电路，以并行执行FFT运算里的某一阶段运算的4次蝴蝶运算。

以下将以快速傅立叶变换电路62重复使用单一个蝴蝶运算单元电路622来完成FFT运算为例进行说明。图11是依照本发明一实施例的快速傅立叶变换电路进行基2蝴蝶运算的流程示意图。蝴蝶运算单元电路622可完成基R的N点FFT运算，且N点快速傅立叶变换包括log_RN级的阶段运算，其中R为大于1的整数。于本实施例中，以蝴蝶运算单元电路622来完成基2的512点FFT运算且512点FFT运算包括9级的阶段运算为例进行说明。

请参照图11，于本实施例中，基于FFT运算的运算结果会包含共轭对称的复数结果，因此蝴蝶运算单元电路622可于第i级阶段运算中取N/2个取样点来执行N/4次的蝴蝶运算(图示简称BU运算)，i为大于等于1且小于等于log_RN的整数。并且，蝴蝶运算单元电路622将于第i级阶段运算所产生的N/2点输出数据依序写入存储器电路621。此外，基于FFT运算的最终运算结果会包含2个实数结果与多个互为共轭对称的复数结果，因此存储器电路621需要记录2个实数结果以及(N/2-1)个复数结果。对应的，被重复使用的存储器电路621至少需要提供(N/2+1)*2个储存地址来暂存FFT运算数据。

详细而言，快速傅立叶变换电路62可先对512点输入数据x[0]～x[511]进行奇偶分组排列，并取256个输入数据(例如：{x[0],x[1]}、{x[256],x[257]}、{x[128],x[129]}……{x[510],x[511]})来进行后续的蝴蝶运算。也就是说，通过上述动作可先将512个输入数据拆分成256个数组，并使得各个数组从地址的角度来说皆是奇偶配对。于第1级阶段运算(即i＝1)，蝴蝶运算单元电路622依序取256个输入数据且运用单一个乘法器6221而分时执行第1次至第128次的蝴蝶运算(共128次)，以产生256笔运算结果。每次蝴蝶运算的2笔运算结果可包括实部系数与虚部系数并且将储存于存储器电路621中。于第2级阶段运算(即i＝2)，蝴蝶运算单元电路622自存储器电路621依序取第1级阶段运算的256笔运算结果且运用单一个乘法器6221而再次分时执行第129次至第256次的蝴蝶运算(共128次)的蝴蝶运算，以产生256笔运算结果。

依此类推，于第8级阶段运算(即i＝8)，蝴蝶运算单元电路622自存储器电路621依序取第7级阶段运算的256笔运算结果且运用单一个乘法器6221而再次分时执行第897次至第1024次的蝴蝶运算(共128次)的蝴蝶运算，以产生256笔运算结果。需注意的是，于第9级阶段运算(即i＝9)，蝴蝶运算单元电路622自存储器电路621取第8级阶段运算的256笔运算结果并执行128次共轭对称变化操作，以获取完整的512点输出数据X[0]～X[511]。基于上述，以本实施例的512实数点FFT来说，在第1～8级阶段的蝴蝶运算中，每阶段会产生256个复数结果，且这256个复数结果彼此不共轭对称。而在第9级阶段的蝴蝶运算中，则根据共轭对称性而推导出另外的256个复数结果，因此共得到512个复数结果。

可知的，每当蝴蝶运算单元电路622执行某一阶段运算(即第1阶段运算至第9阶段运算)之后，蝴蝶运算单元电路622可将运算结果记录于存储器电路621。于此，基于前述的对称性质，本实施例只需要记录峰值(第256个复数结果)以及对称值(X[0]～X[255])共257个复数结果，又每个复数结果包括实部系数和虚部系数，故存储器电路621需要257*2个存储地址来完成一次512点FFT运算。每一个存储地址用以记录复数结果的实部系数或虚部系数。

此外，于一实施例中，当快速傅立叶变换电路62包括与蝴蝶运算单元电路622结构相似的多个基2蝴蝶运算电路时，每个所述基2蝴蝶运算电路执行以下操作。接收输入数据，并依据M个旋转因子其中之一旋转因子对输入数据进行蝴蝶运算以产生输出数据。上述蝴蝶运算包括基于复数运算而分解出的多个加减法运算及多个乘法运算，以及M为小于N/2的正整数。每个基2蝴蝶运算电路依序于多个时钟周期执行加减法运算及乘法运算，且在每个时钟周期内最多执行一次乘法运算。于一实施例中，作为旋转因子存储器电路623的只读存储器可耦接这些基2蝴蝶运算电路，并用以储存M个旋转因子，且M等于N/4。

详细而言，基于图9的范例可知，每次蝴蝶运算皆需要从只读存储器读取旋转因子的实部系数与虚部系数。旋转因子可表示为cosθ-j*sinθ，而旋转因子的实部系数为cosθ且旋转因子的虚部系数为sinθ。对于第i阶段的蝴蝶运算，θ将等于2π*0/2ⁱ、2π*1/2ⁱ、2π*2/2ⁱ、….、2π*(2^(i-1)-1)/2ⁱ。由此可知，随着i增加，快速傅立叶变换电路62需要更多对应至不同旋转角度的旋转因子。于传统的设计中，每一阶段的蝴蝶运算所需的旋转因子皆记录于只读存储器中，然而相同的旋转因子是有重复被记录的现象。因此，于一实施例中，可取蝴蝶运算的总阶段数而决定产生N/4个旋转因子，且只读存储器记录这N/4个旋转因子。举例而言，当N＝512，蝴蝶运算单元电路622需执行8阶段的蝴蝶运算(如图11所示)。因此，只读存储器记录这128个旋转因子，其分别对应至旋转角度2π*0/2⁸、2π*1/2⁸、2π*2/2⁸、….、2π*(2^(8-1)-1)/2⁸，以避免有相同的旋转因子被重复记录于只读存储器。蝴蝶运算单元电路622可透过选择逻辑电路而获取适当的旋转因子进行基2蝴蝶运算。藉此，本发明实施例可透过优化的旋转因子查找表来节约只读存储器的使用量。

综上所述，于本发明的实施例中，可通过重复使用乘法器的方式来实现FFT的蝴蝶运算，从而大幅减少乘法器的个数。并且，透过优化记录有旋转因子的查找表，可有效减少只读存储器的使用量。藉此，本发明实施例的快速傅立叶变换电路可大幅减少硬件消耗并使电路面积下降。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。

Claims (12)

1.一种音频处理装置的快速傅立叶变换电路，用以进行N点快速傅立叶变换，N为2的幂，其特征在于，包括：

存储器电路；以及

蝴蝶运算单元电路，耦接所述存储器电路，自所述存储器电路读取2点输入数据，依据旋转因子对所述2点输入数据进行蝴蝶运算以产生2点输出数据，并将所述2点输出数据写入所述存储器电路，其中所述蝴蝶运算单元电路包括：

乘法器，依序于多个时钟周期将所述2点输入数据其中之一者的实部系数或虚部系数乘上所述旋转因子的实部系数或虚部系数，其中所述乘法器分别于所述时钟周期其中之每一者内执行一次乘法运算；以及

多个加减法器，耦接所述乘法器，依据所述乘法器的输出或所述2点输入数据其中之另一者的实部系数或虚部系数执行加减法运算，致使所述蝴蝶运算单元电路产生所述2点输出数据。

2.根据权利要求1所述的音频处理装置的快速傅立叶变换电路，其特征在于，更包括：

旋转因子存储器电路，耦接所述蝴蝶运算单元电路，储存所述旋转因子。

3.根据权利要求1所述的音频处理装置的快速傅立叶变换电路，其特征在于，所述N点快速傅立叶变换是以R点为基底，所述N点快速傅立叶变换包括log_RN级的阶段运算，所述蝴蝶运算单元电路于第i级阶段运算中执行N/4次的蝴蝶运算，并将于第i级阶段运算所产生的N/2点输出数据依序写入所述存储器电路，其中R为大于1的整数，i为大于等于1且小于等于log_RN的整数，

其中所述蝴蝶运算单元电路于第i级阶段运算所产生的N/2点输出数据彼此不共轭对称，而存储器电路具有(N/2+1)*2个存储地址，每一所述存储地址用以记录N/2点输出数据其中一者的实部系数或虚部系数。

4.根据权利要求3所述的音频处理装置的快速傅立叶变换电路，其特征在于，于第i级阶段运算中，所述蝴蝶运算单元电路自所述存储器电路的2个存储地址读取所述2点输入数据，并将所述2点输出数据覆写回所述2个存储地址。

5.根据权利要求1所述的音频处理装置的快速傅立叶变换电路，其特征在于，所述时钟周期包括第一时钟周期以及第二时钟周期，所述乘法器于所述第一时钟周期将所述2点输入数据其中之一者的实部系数乘上所述旋转因子的实部系数与虚部系数其中之一而产生第一乘法输出，所述乘法器于所述第二时钟周期将所述2点输入数据其中之一者的虚部系数乘上所述旋转因子的实部系数与虚部系数其中之另一而产生第二乘法输出。

6.根据权利要求5所述的音频处理装置的快速傅立叶变换电路，其特征在于，所述加减法器包括第一加减法器与第二加减法器，所述第一加减法器于所述第二时钟周期依据所述第一乘法输出与所述第二乘法输出进行加减法操作而获取第一加减法输出，所述第二加减法器于所述第二时钟周期依据所述第一加减法输出与所述2点输入数据其中之另一者的实部系数进行加减法操作而获取所述2点输出数据其中之一者的实部系数，

其中所述时钟周期包括第三时钟周期，所述第二加减法器于所述第三时钟周期依据所述第一加减法输出与所述2点输入数据其中之另一者的实部系数进行加减法操作而获取所述2点输出数据其中之另一者的实部系数。

7.根据权利要求5所述的音频处理装置的快速傅立叶变换电路，其特征在于，所述加减法器包括第一加减法器与第二加减法器，所述第一加减法器于所述第二时钟周期依据所述第一乘法输出与所述第二乘法输出进行加减法操作而获取第一加减法输出，所述第二加减法器于所述第二时钟周期依据所述第一加减法输出与所述2点输入数据其中之另一者的虚部系数进行加减法操作而获取所述2点输出数据其中之一者的虚部系数，

其中所述时钟周期包括第三时钟周期，所述第二加减法器于所述第三时钟周期依据所述第一加减法输出与所述2点输入数据其中之另一者的虚部系数进行加减法操作而获取所述2点输出数据其中之另一者的虚部系数。

8.一种音频处理装置的快速傅立叶变换电路，用以进行N点快速傅立叶变换，N为2的幂，其特征在于，包括：

多个基2蝴蝶运算电路，其中每个所述基2蝴蝶运算电路执行包括：接收输入数据，并依据M个旋转因子其中之一旋转因子对所述输入数据进行蝴蝶运算以产生输出数据，其中所述蝴蝶运算包括基于复数运算而分解出的多个加减法运算及多个乘法运算，以及M为小于N/2的正整数，

其中每个所述基2蝴蝶运算电路依序于多个时钟周期执行所述加减法运算及所述乘法运算，且在每个所述时钟周期内最多执行一次所述乘法运算。

9.根据权利要求8所述的音频处理装置的快速傅立叶变换电路，其特征在于，每个所述基2蝴蝶运算电路中均使用单一乘法器来执行所述多个乘法运算，

其中每个所述基2蝴蝶运算电路更包括：

存储器电路，耦接所述基2蝴蝶运算电路，用以储存所述输入数据与所述输出数据，具有(N/2+1)*2个存储地址，其中每一所述存储地址用以记录N/2点输出数据其中一者的实部系数或虚部系数。

10.根据权利要求9所述的音频处理装置的快速傅立叶变换电路，其特征在于，每个所述基2蝴蝶运算电路包括：

多个加减法，耦接所述乘法器，依据所述乘法器的输出或所述输入数据的实部系数或虚部系数执行加减法运算，致使所述蝴蝶运算单元电路产生所述输出数据。

11.根据权利要求8所述的音频处理装置的快速傅立叶变换电路，其特征在于，更包括：

只读存储器，耦接所述多个基2蝴蝶运算电路，储存所述M个旋转因子，且M等于N/4。

12.根据权利要求8所述的音频处理装置的快速傅立叶变换电路，其特征在于，至少部分的所述基2蝴蝶运算电路组成一或多个基数大于2的蝴蝶运算电路。

Images