Question

基于FPGA的并行迭代法实现FFT...请问哪位大虾能给个指导，有程序最好了

Answer 1

我曾做过语音分析的实验，不知你是否一样，不会写 C, 只能给你个 VB 的参考，不知有没有帮助，写 FPGA 的话，参考过别人的资料，为了节省内存，加快计算速度，要考虑把蝶形因子固化在静态储存器中。

Option Explicit

'复数
Public Type COMPLEX
re As Double '实部
im As Double '虚部
End Type

'############################################################'
'FFT 算法
'############################################################'
'nFFTn 样本数列的长度。
'aFFT 储存 FFT 变换的数组，由于使用同址变换，结果保存回此数组。
Public Sub m_DIT_FFT(nFFTn As Long, aFFT() As COMPLEX)
Dim i As Long, j As Long, k As Long, k2 As Long
Dim m As Long, n As Long
Dim Numerator As Double, Pn As Long
Dim Iterations As Long, Block As Long, Level As Long

Dim XX As COMPLEX, WP As COMPLEX, BC As COMPLEX

'----------------------------------------'
' 确定 N = 2^M 有效样本长度
'----------------------------------------'
m = m_Log2(nFFTn) '有效样本长度指数
n = 2 ^ m '有效样本长度

'----------------------------------------'
' FFT 输入序列预排序
'----------------------------------------'
j = n / 2
For i = 1 To n - 2
If i < j Then
XX.re = aFFT(i).re
XX.im = aFFT(i).im
aFFT(i).re = aFFT(j).re
aFFT(i).im = aFFT(j).im
aFFT(j).re = XX.re
aFFT(j).im = XX.im
End If
k = n / 2
If j >= k Then
Do While (j >= k)
j = j - k
k = k / 2
Loop
End If
j = j + k
Next

'----------------------------------------'
' 时域抽取 FFT 同址变换
'----------------------------------------'
Numerator = 2 * PI / n '采样角分子

For Iterations = 1 To m '迭代次数
Level = 2 ^ Iterations
Block = Level / 2
For j = 0 To Block - 1 '蝶形级数
Pn = j * 2 ^ (m - Iterations)
WP.re = Cos(Pn * Numerator)
WP.im = -Sin(Pn * Numerator)
For k = j To n - 1 Step Level '蝶形单元
k2 = k + Block

XX.re = aFFT(k).re
XX.im = aFFT(k).im

BC.re = aFFT(k2).re * WP.re - aFFT(k2).im * WP.im
BC.im = aFFT(k2).re * WP.im + aFFT(k2).im * WP.re

aFFT(k).re = XX.re + BC.re
aFFT(k).im = XX.im + BC.im

aFFT(k2).re = XX.re - BC.re
aFFT(k2).im = XX.im - BC.im
Next
Next
Next
End Sub

' 计算以 2 为底的对数值 log2(N)
Public Function m_Log2(nNumber As Long) As Double
m_Log2 = Log(nNumber) / Log(2#)
End Function