一种蝶形运算FFT处理器

摘要

本发明公开了一种蝶形运算FFT处理器，其中用于实现数据和旋转因子相乘的复数乘法器为CORDIC旋转算法器，旋转因子存储器中存储的为旋转因子对应的旋转角度。本发明采用CORDIC旋转算法实现数据和旋转因子的乘法运算，从而用数据的移位代替了复数乘法运算，降低了计算复杂度。同时，由于采用了CORDIC旋转算法实现复数乘，那么，旋转因子存储器中只需要存储旋转因子对应的旋转角度即可，而不需要存储旋转因子对应角度的正弦、余弦值，从而可以节约旋转因子存储器单元，降低旋转因子读取的复杂度。

主权项

一种蝶形运算FFT处理器，包括：一数据存储器及旋转因子存储器；一存储器地址控制单元，用于控制输入数据和旋转因子在数据存储器及旋转因子存储器中的存放/读取位置；一FFT蝶形运算单元，用于从数据存储器中取出数据，从旋转因子存储器中取出相应的旋转因子，进行蝶形运算，计算结果数据存入数据存储器中；其特征在于，FFT蝶形运算单元中，用于实现数据和旋转因子相乘的复数乘法器为CORDIC旋转算法器，旋转因子存储器中存储的为旋转因子对应的旋转角度θ；CORDIC旋转算法器将旋转角度θ拆开成n+1个旋转角度θi， θ i = d i arctan [ 1 2 i ] , i = 0,1 , . . . . . . , n di为余留旋转角度的符号函数，余留旋转角度是指除去前面旋转的角度和之外，还需要旋转的角度；然后，进行n+1次移位运算，其中的第i+1步移位运算，将输入数据的实部xi右移位i位，然后与符号函数di相乘后到加法器中与输入数据的虚部yi相加得到第i+1步旋转后数据的虚部yi+1，并存回虚部寄存器中；同样，输入数据的虚部yi右移位i位，然后与符号函数di相乘后到加法器中与输入数据的实部xi相加得到第i+1步旋转后数据的实部xi+1，并存回实部寄存器中；经过n+1次移位运算得到数据xi+1、yi+1为数据和旋转因子相乘的结果；FFT蝶形运算单元为基4算法的FFT计算，一次蝶形运算从输入数据中取出四点数据进行FFT蝶形运算；按时间抽取的基4FFT计算推导公式为：A′＝A+BWp+CW2p+DW3pB′＝A+jBWp-CW2p-jDW3pC′＝A-BWp+CW2p-DW3pD′＝A-jBWp-CW2p+jDW3p其中，A、B、C、D为FFT蝶形运算单元的四点输入数据，A′、B′、C′、D′为蝶形运算单元输出的四点FFT计算结果数据，Wp、W2p、W3p为旋转因子，W＝e-j2π/N，N为输入数据的长度；所述的CORDIC旋转算法器将旋转角度θ拆开成12个旋转角度θi，进行12次移位运算。