基于FPGA的快速傅立叶变换

Ｄ′＝[ｒ０－(ｉ１×ｃ１＋ｒ１×ｓ１)－(ｒ２×ｃ２－ｉ２×ｓ２)＋(ｉ３×ｃ３＋ｒ３×ｓ３)]＋ｊ[ｉ０＋(ｒ１×ｃ１－ｉ１×ｓ１)－(ｉ２×ｃ２＋ｒ２×ｓ２)－(ｒ３×ｃ３－ｉ３×ｓ３)]? （７）

而在基２蝶形中，Ｗｋ０和Ｗｋ２的值均为１，这样，将Ａ，Ｂ，Ｃ和Ｄ的表达式代入图２中的基２运算的四个等式中，则有：

Ａ′＝ｒ０＋(ｒ１×ｃ１－ｉ１×ｓ１)＋ｊ[ｉ０＋(ｉ１×ｃ１＋ｒ１×ｓ１)]? （８）

Ｂ′＝ｒ０－ (ｒ１×ｃ１－ｉ１×ｓ１)＋ｊ[ｉ０－(ｉ１×ｃ１＋ｒ１×ｓ１)] 　（９）

Ｃ′＝ｒ２＋(ｒ３×ｃ３－ｉ３×ｓ３)＋ｊ[ｉ０＋(ｉ３×ｃ３＋ｒ３×ｓ３)]? （１０）

Ｄ′＝ｒ２－(ｒ３×ｃ３－ｉ３×ｓ３)＋ｊ[ｉ０－(ｉ３×ｃ３＋ｒ３×ｓ３)]? （１１）

在上述式（４）～（１１）中有很多类同项，如ｉ１×ｃ１＋ｒ１×ｓ１和ｒ１×ｃ１－ｉ１×ｓ１等，它们仅仅是加减号的不同，其结构和运算均类似，这就为简化电路提供了可能。同时，在蝶形运算中，复数乘法可以由实数乘法以一定的格式来表示，这也为设计复数乘法器提供了一种实现的途径。

以基４为例，在其运算单元中，实际上只需做三个复数乘法运算，即只须计算ＢＷｋ１、ＣＷｋ２和ＤＷｋ３的值即可，这样在一个基４蝶形单元里面，最多只需要３个复数乘法器就可以了。在实际过程中，在不提高时钟频率下，只要将时序控制好?便可利用流水线（Ｐｉｐｅｌｉｎｅ）技术并只用一个复数乘法器就可完成这三个复数乘法，大大节省了硬件资源。

图2 基2和基4蝶形算法的信号流图

３　ＦＦＴ的地址

ＦＦＴ变换后输出的结果通常为一特定的倒序,因此，几级变换后对地址的控制必须准确无误。

倒序的规律是和分解的方式密切相关的，以基８为例，其基本倒序规则如下：

基８可以用２×２×２三级基２变换来表示，则其输入顺序则可用二进制序列（ｎ１ ｎ２ ｎ３）来表示，变换结束后，其顺序将变为（ｎ３ ｎ２ ｎ１），如：Ｘ?０１１?→ ｘ?１１０?，即输入顺序为３，输出时顺序变为６。

更进一步，对于基１６的变换，可由２×２×２×２，４×４，４×２×２等形式来构成，相对于不同的分解形式，往往会有不同的倒序方式。以４×４为例，其输入顺序可以用二进制序列（ｎ１ ｎ２ ｎ３ ｎ４）来表示变换结束后，其顺序可变为（（ｎ３ ｎ４）（ｎ１ ｎ２）），如： Ｘ?０１１１?→ ｘ?１１０１?。即输入顺序为７，输出时顺序变为１３。

在２ｋ／４ｋ／８ｋ的傅立叶变换中，由于要经过多次的基４和基２运算，因此，从每次运算完成后到进入下一次运算前，应对运算的结果进行倒序，以保证运算的正确性。

４　旋转因子

Ｎ点傅立叶变换的旋转因子有着明显的周期性和对称性。其周期性表现为：

FFT之所以可使运算效率得到提高，就是利用

ＦＦＴ之所以可使运算效率得到提高，就是利用了对称性和周期性把长序列的ＤＦＴ逐级分解成几个序列的ＤＦＴ，并最终以短点数变换来实现长点数变换。

根据旋转因子的对称性和周期性，在利用ＲＯＭ存储旋转因子时，可以只存储旋转因子表的一部分，而在读出时增加读出地址及符号的控制，这样可以正确实现ＦＦＴ。因此,充分利用旋转因子的性质，可节省７０％以上存储单元。

实际上，由于旋转因子可分解为正、余弦函数的组合，故ＲＯＭ中存的值为正、余弦函数值的组合。对２ｋ／４ｋ／８ｋ的傅立叶变换来说，只是对一个周期进行不同的分割。由于８ｋ变换的旋转因子包括了２ｋ／４ｋ的所有因子，因此，实现时只要对读ＲＯＭ的地址进行控制，即可实现２ｋ／４ｋ／８ｋ变换的通用。

５　存储器的控制

《基于FPGA的快速傅立叶变换(第2页)》