FFT至简设计法实现法-FFT算法-蝶形运算.doc

DIT-FFT至简设计实现法
1、 DIT-FFT算法的基本原理
有限长序列xn的N点DFT定义为：Xk=n=0N-1xnWNKn,式中WN=e-j2πN。
DFT在实际应用中很重要，但是如果直接按DFT变换进行计算，当序列长度N很大时，计算量会非常大，所需时间也很长，因此常用的是DFT的一种快速计算算法，简称FFT。
最常用的FFT算法是基于时间抽取的基2-FFT算法和基于频率抽取的基2-FFT算法，这种算法的特点在于FFT会把一次大的DFT分割成几个小的DFT，这样递归式地细分下去，例如有8个采样点的FFT，首先会把最外层的8点运算分成两个4点FFT的奇偶组合，第二层FFT又分成四个两点FFT的奇偶组合，并且由此计算出的频谱中很有趣的一点在于对于实数输出的数组，后面一半和前面一半正好对称相同，对于虚数输出的数组，后面一半是前面数组对称后乘上负1，因此，我们只需要算出FFT的一半即可求出全部。
本设计讨论的是基于至简设计法实现按时间抽选的基2-FFT算法（即DIF-FFT）实现过程，支持N由8到1024。

图 1按时间抽取的基2-FFT算法蝶形运算流图（N=8）

2、 蝶形运算至简实现过程
2、1 模块划分

图 2蝶形运算模块框图
本模块包括三个RAM模块（RAM1，RAM2，RAM3）与一个DFT模块，各模块功能如下：
1） RAM1模块：在开始进行蝶形运算前，全部采样点（如图1所示的x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、x(7)）已经按照倒位序二进制的地址依次存储在RAM1模块中，即地址0保存了采样点x(0)，地址1保存了采样点x(4)。选用双端口RAM1可以同时对两点采样数据(如图1的x（0）、x(4))进行读、写操作。
2） RAM2模块：RAM2模块也是采用双端口输入输出，可同时对两点数据进行读、写操作。
3） DFT模块：DFT模块用于对RAM1、RAM2输出的两点采样数据（如图1的x（0）、x(4)）进行蝶形运算，它将运算结果输出至RAM1、RAM2模块进行保存。
4） RAM3模块：RAM3模块是单输出模块，理论是应保存N（N为采样点个数）个运算参数WNr，但由于每一次蝶形运算结果（如 x1k+WNkX2(k), x1k-WNkX2(k)）具有对称性，因此RAM3只需要保存N/2个WNr即可。

2、1、1 奇数轮蝶形运算
图3 第奇数轮蝶形运算流图
如图3所示，RAM1首先根据计数器给出的两个点的地址（如地址0，地址1）进行数据读操作，然后将数据（如x1(k)和x2(k)）送进DFT模块进行运算，最后RAM2将DFT模块输出的数据（如x1k+WNkX2(k), x1k-WNkX2(k)）按照原来的地址顺序进行写操作,直到RAM1全部读完N个数据，并且RAM2全部写完N个数据后，则第一轮蝶形运算计算完毕。
2、1、2 偶数轮蝶形运算
图4 第偶数轮蝶形运算流图
偶数轮运算跟奇数轮运算相似，唯一的不同就是：读取RAM由RAM1改为RAM2，写RAM由RAM2改为RAM1。
RAM1与RAM2按照这样的读写交替顺序，直至历遍完n轮蝶形运算（n为蝶形运算一共要计算的轮数）。
2、2 计数器架构设计
由于需要依次读取和写入RAM1和RAM2，并且还要经过N轮的运算，很明显需要运用到计数器。
计数器架构，关乎到整个设计的可靠性和至简性，因此是重中之中的设计。按照至简设计法的建议，需要用到N轮运算，这需要一个计数器但每轮的计数器如何设计呢？
由于这些计数器主要是用于产生读写地址的，所以我们需要仔细分析地址的规律。我们以8点的FFT为例进行分析。

观察上图，每一轮取址如表1所示:
蝶形运算第几轮
运算节点
第一次蝶形运算
第二次蝶形运算
第三次蝶形运算
第四次蝶形运算
1
X1(k)的地址
0
2
4
6
X2(k)的地址
1
3
5
7
2
X1k的地址
0
1
4
5
X2k的地址
2
3
6
7
3
X1(k)的地址
0
1
2
3
X2(k)的地址
4
5
6
7
表1 N为8的蝶形运算每一轮取址
蝶形运算每一轮每一次的取地址满足什么关系呢，如何才能在FPGA设计中实现如表1的取地址运算，观察上表，我们可以发现如下规律:
第几级蝶形运算
X1(k)的地址
第一次
第二次
第三次
第四次
第一级
0=0+0*21
2=0+1*21
4=0+2*21
6=0+3*21
第二级
0=0+0*22
1=1+0*22
4=0+1*22
5=1+1*22
第三级
0=0+0*23
1=1+0*23
2=2+0*23
3=3+0*23
第几级蝶形运算
X2(k)的地址
第一次
第二次
第三次
第四次
第一级
1=20 +0+0*21
3=20 +0+1*21
5=20 +0+2*21
7=20 +0+3*21
第二级
2=21 +0+0*22
3=21 +1+0*22
6=21 +0+1*22
7=21 +1+1*22
第三级
4=22 +0+0*23
5=22 +1+0*23
6=22 +2+0*23
7=22 3+0*23
表2 X1(k)的取址
表3 X2(k)的取址
根据表2、表3，可得到X1k地址与X2k地址与数组[a],[b],[c]有关的表达式
X1k地址=a+[b]*2[c];
X2k地址=X1k地址+2[c]-1； （式1）
通过上面的观察，按照明德扬的计数器架构建议，可设计三个计数器cnt0,cnt1,cnt2分别表示数组[a],[b],[c]，因此可将式1变为：
X1k地址=cnt0+cnt1*2cnt2+1；
X2k地址=X1k地址+2cnt2； （式2）
各个计数器每一轮的结束条件为：

cnt0=2cnt2-1;
cnt1=2n-1-cnt2-1;
cnt2=n-1; (式3)
其中n为蝶形运算一共要计算的轮数，如采样点数N为8时，则一共要进行三轮运算。通过这三个简易的计数器设计，就能实现复杂的DIT-FFT蝶形运算取址操作。
终上所述，无论是模块划分、计数器设计、还是乒乓操作的读写处理，都始终基于“至简设计”的原则，用简易的代码结构就能实现复杂的DIT-FFT蝶形运算，代码设计风格极其简洁，详细可参考附录代码。
本案例是FFT的串行实现，但根据同样的思路和资源换速度的思想，可以很方便地实现多个并行或者全并行的设计。

3、至简设计代码实现（附录部分代码）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
parameter N = 512;
parameter LOGN = 9;

/****************************************
/计数器架构，下面三个计数器用于产生读地址
****************************************/
always @(posedge clk or negedge rst_n)begin
if(!rst_n)begin
cnt0 <= 0;
end
else if(add_cnt0)begin
if(end_cnt0)
cnt0 <= 0;
else
cnt0 <= cnt0 + 1;
end
end

assign add_cnt0 = flag;
assign end_cnt0 = add_cnt0 && cnt0== (1<st_n)begin
if(!rst_n)begin
cnt1 <= 0;
end
else if(add_cnt1)begin
if(end_cnt1)
cnt1 <= 0;
else
cnt1 <= cnt1 + 1;
end
end

assign add_cnt1 = end_cnt0;
assign end_cnt1 = add_cnt1 && cnt1==(N>>(cnt2+1))-1 ;

always @(posedge clk or negedge rst_n)begin
if(!rst_n)begin
cnt2 <= 0;
end
else if(add_cnt2)begin
if(end_cnt2)
cnt2 <= 0;
else
cnt2 <= cnt2 + 1;
end
end

assign add_cnt2 = end_cnt1;
assign end_cnt2 = add_cnt2 && cnt2==LOGN-1 ;

/********
/计数器架构，下面三个计数器用于产生写地址
****************************************/
always @(posedge clk or negedge rst_n)begin
if(!rst_n)begin
wr_cnt0 <= 0;
end
else if(add_wr_cnt0)begin
if(end_wr_cnt0)
wr_cnt0 <= 0;
else
wr_cnt0 <= wr_cnt0 + 1;
end
end

assign add_wr_cnt0 = fft_dout_vld;
assign end_wr_cnt0 = add_wr_cnt0 && wr_cnt0==(1<1)
wr_cnt1 <= 0;
else
wr_cnt1 <= wr_cnt1 + 1;
end
end

assign add_wr_cnt1 = end_wr_cnt0;
assign end_wr_cnt1 = add_wr_cnt1 && wr_cnt1==(N>>(wr_cnt2+1))-1 ;

always @(posedge clk or negedge rst_n)begin
if(!rst_n)begin
wr_cnt2 <= 0;
end
else if(add_wr_cnt2)begin
if(end_wr_cnt2)
wr_cnt2 <= 0;
else
wr_cnt2 <= wr_cnt2 + 1;
end
end

assign add_wr_cnt2 = end_wr_cnt1;
assign end_wr_cnt2 = add_wr_cnt2 && wr_cnt2==LOGN-1 ;

/************************************************
RAM1地址0的设计
************************************************/

always @(posedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
addr_0 <= 0;
end
else if(wr_cnt2[0]==0) begin
addr_0 <= cnt0 + cnt1*(1<<(cnt2+1));
end
else begin
addr_0 <= wr_cnt0 + wr_cnt1*(1<<(wr_cnt2+1));
end
end
/************************************************
RAM1写数据0的设计
************************************************/
always @(posedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
wdata_0 <= 0;
end
else begin
wdata_0 <= fft_dout0
end
end

/************************************************
RAM1写请求0的设计
************************************************/
always @(posedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
wrreq_0 <= 0;
end
else if(wr_cnt2[0]==1) begin
wrreq_0 <= fft_dout_vld;
end
else begin
wrreq_0 <= 0;
end
end

/************************************************
RAM1地址1的设计
************************************************/
always @(posedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
addr_1 <= 0;
end
else if(wr_cnt2[0]==0) begin
addr_1 <= cnt0 + cnt1*(1<<(cnt2+1)) + (1</
always @(posedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
wdata_1 <= 0;
end
else begin
wdata_1 <= fft_dout1;
end
end

/************************************************
RAM1写请求1的设计
************************************************/
always @(posedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
wrreq_1 <= 0;
end
else if(wr_cnt2[0]==1)begin
wrreq_1 <= fft_dout_vld;
end
else begin
wrreq_1 <= 0;
end
end

/************************************************
RAM2地址0的设计
**********/
always @(posedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
addr_2 <= 0;
end
else if(wr_cnt2[0]==1) begin
addr_2 <= cnt0 + cnt1*(1<<(cnt2+1));
end
else begin
addr_2 <= wr_cnt0 + wr_cnt1*(1<<(wr_cnt2+1));
end
end

/************************************************
RAM2写数据0的设计
************************************************/
always @(posedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
wdata_2 <= 0;
end
else begin
wdata_2 <= fft_dout0;
end
end

/************************************************
RAM2写请求0的设计
************************************************/
always @(posedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
wrreq_2 <= 0;
end
else if(wr_cnt2[0]==0) begin
wrreq_2 <= fft_dout_vld;
end
else begin
wrreq_2 <= 0;
end
end

/************************************************
RAM2地址1的设计
************************************************/
always @(posedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
addr_3 <= 0;
end
else if(wr_cnt2[0]==1) begin
addr_3 <= cnt0 + cnt1*(1<<(cnt2+1)) + (1<sedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
wdata_3 <= 0;
end
else begin
wdata_3 <= fft_dout1;
end
end

/************************************************
RAM2写请求1的设计
************************************************/
always @(posedge clk or negedge rst_n)begin
if(rst_n==1'b0)begin
wrreq_3 <= 0;
end
else if(wr_cnt2[0]==0)begin
wrreq_3 <= fft_dout_vld;
end
else begin
wrreq_3 <= 0;
end
end