FFT至简设计法实现法_FFT算法_蝶形运算_fpga
0赞DIT-FFT至简设计实现法
1、 DIT-FFT算法的基本原理
有限长序列
的N点DFT定义为：,式中。
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为采样点个数）个运算参数，但由于每一次蝶形运算结果,）具有对称性，因此RAM3只需要保存N/2个即可。
2、1、1 奇数轮蝶形运算
图3 第奇数轮蝶形运算流图
如图3所示，RAM1首先根据计数器给出的两个点的地址（如地址0，地址1）进行数据读操作，然后将数据（如和）送进DFT模块进行运算，最后RAM2将DFT模块输出的数据（如,）按照原来的地址顺序进行写操作,直到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 |
| 0 | 2 | 4 | 6 |
| 1 | 3 | 5 | 7 | |
2 |
| 0 | 1 | 4 | 5 |
| 2 | 3 | 6 | 7 | |
3 |
| 0 | 1 | 2 | 3 |
| 4 | 5 | 6 | 7 |
表1 N为8的蝶形运算每一轮取址
蝶形运算每一轮每一次的取地址满足什么关系呢，如何才能在FPGA设计中实现如表1的取地址运算，观察上表，我们可以发现如下规律:
第几级蝶形运算 |
| |||
第一次 | 第二次 | 第三次 | 第四次 | |
第一级 | 0=0+0* | 2=0+1* | 4=0+2* | 6=0+3* |
第二级 | 0=0+0* | 1=1+0* | 4=0+1* | 5=1+1* |
第三级 | 0=0+0* | 1=1+0* | 2=2+0* | 3=3+0* |
第几级蝶形运算 |
| |||
第一次 | 第二次 | 第三次 | 第四次 | |
第一级 | 1= | 3= | 5= | 7= |
第二级 | 2= | 3= | 6= | 7= |
第三级 | 4= | 5= | 6= | 7= |
表3 的取址
根据表2、表3，可得到与与数组[a],[b],[c]有关的表达式
;
； （式1）
通过上面的观察，按照明德扬的计数器架构建议，可设计三个计数器cnt0,cnt1,cnt2分别表示数组[a],[b],[c]，因此可将式1变为：
；
； （式2）
各个计数器每一轮的结束条件为：
(式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<<cnt2)-1 ;
always @(posedge clk or negedge rst_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<<wr_cnt2)-1 ;
always @(posedge clk or negedge rst_n)begin if(!rst_n)begin wr_cnt1 <= 0; end else if(add_wr_cnt1)begin if(end_wr_cnt1) 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<<cnt2); end else begin addr_1 <= wr_cnt0 + wr_cnt1*(1<<(wr_cnt2+1)) + (1<<wr_cnt2); end end /************************************************ RAM1写数据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<<cnt2); end else begin addr_3 <= wr_cnt0 + wr_cnt1*(1<<(wr_cnt2+1)) + (1<<wr_cnt2); end end
/************************************************ RAM2写数据1的设计 ************************************************/ always @(posedge 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
|
