mdykj33

FFT至简设计法实现法_FFT算法_蝶形运算_fpga

0
阅读(112) 评论(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=+0+0*

3=+0+1*

5=+0+2*

7=+0+3*

第二级

2=+0+0*

3=+1+0*

6=+0+1*

7=+1+1*

第三级

4=+0+0*

5=+1+0*

6=+2+0*

7=+3+0*

表2  的取址

                          表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

 

 

 

 

 

 

设计案例-FFT至简设计实现法.docx