首页资源分类FPGA/CPLDAltera > 2k-8kFFT处理器ROM面积的优化

2k-8kFFT处理器ROM面积的优化

已有 445506个资源

下载专区

上传者其他资源

    FPGA/CPLD热门资源

    本周本月全部

    文档信息举报收藏

    标    签:FFT旋转因子ROMradix-4

    分    享:

    文档简介

    结合FFT的实际需要,对ROM规模进行了最佳化处理

    文档预览

    http://www.paper.edu.cn 2k-8k FFT 处理器 ROM 面积的优化 雷艳敏 武汉理工大学信息工程学院,武汉(430070) E-mail:lymyoujian2@126.com 摘 要:结合实时高速 FFT 的实际需求,硬件设计采用多级串联的同步流水线结构、基于 SRAM、SDF(single-path delay feedback)、DIF 等结构和方法。2k/8k 分解为 5/6 级 radix-4 蝶形单元与一级 radix 2 蝶形单元级联,设计对存储旋转因子的 ROM 规模进行了最佳优化 处理。整体划分为多个模块,均采用 Verilog HDL 语言描述,并进行了功能一致性仿真验 证。 关键词:FFT,旋转因子,ROM,radix-4 1. FFT 理论 FFT 算法按时间抽取(DIT)和按频率抽取(DIF)的区别在于:DIT 中蝶形运算的输入数据 和旋转因子是先乘后加;DIF 中则是先加后乘。两者并没有实质区别。本文采用 DIF 的 radix-4 FFT 算法。FFT radix-4 算法比 radix-2 算法少约 20 %的运算量[1]。 N 点DFT变换对定义为: ⎧ ⎪⎪ DFT : ⎨ ⎪ ⎪⎩ I D F T : X (k ) = x(n) = ∑ , 1 N N −1 x ( n )W nk N n=0 ∑ 1 N N −1 x ( k )W − N nk k =0 n, k = 0,1, 2...N −1 这里WNnk = e− j2π nk / N 是旋转因子。radix-4蝶形计算公式可表示为: (1) N /4L −1 ∑ X(4r + p) = {x(n) + x(n + N 4L )W4p + x(n + 2N 4L )W42 p + x(n + 3N 4L )W }W W 3p np nr 4 N / 4(L−1) N / 4L n=0 (2) 其中 r=0 ~ (N/4L) -1,p = 0,1,2,3,L=1~log4N 且 n = 0 ~ (N/4) -1。 式 2 中当 L=1 时,Radix-4 DIF butterfly 如图 1,实际动作过程信号流图如图 2 所示。 x[n] x[n+N/4] x[n+N/2] x[n+3N/4] WN0 -j -1 j WN1 -1 -1 WN2 j -1 -j WN3 X[4r] X[4r+1] X[4r+2] X[4r+3] 图 1 Radix-4 DIF butterfly -1- x[n] x[n+N/4] x’[4r] X[4r] WN0 -1 x’[4r+2] X[4r+2] WN2 http://www.paper.edu.cn x[n+N/2] -1 x’[4r+1] X[4r+1] WN1 x[n+3N/4] x’[4r+3] -1 -j -1 X[4r+3] WN3 图 2 Signal flow in the DIF Radix-4 butterfly 2. FFT 结构 FFT 硬件设计采用 pipeline 流水线结构,有利于减小面积、最大化 throughput。radix-2 和 radix-4 处理采用 SDF butterfly unit,有利于节省功耗、方便 Place and route;采用 SRAM 存储中间数据,SRAM 比 DRAM 节省功耗及面积[2]。 Din Stage 1 Radix-4 Stage 2 Radix-4 Stage 7 Dout … Radix-2 ROM ROM 图 3 Pipeline 结构示意图 本设计最大符号速率是 8MHz,系统时钟为 16MHz,因此采用单口 SRAM。图 3 为 Pipeline 结构示意图。 x[0] x[512] x[0] x[1024] x[512] x[1536] x[256] x[1280] x[768] x[1792] x[1024] x[1536] … … … … … … … … . … … … … … … … … . … … … … … … … … . … … … … … … … … . Radix-4 stage Radix-4 stage Radix-4 R-4 R-4 R-2 stage stage stage stage 图 4 2k mode pipeline-structured FFT 如图 4 所示,2k mode 由 5 个 radix-4 stage 和 1 个 radix-2 stage 组成;8k mode 由 6 个 radix-4 stage 和 1 个 radix-2 stage 组成。2k mode 是用表示 8K 模式或 2K 模式的电平信号旁 -2- http://www.paper.edu.cn 路 8k mode 最左边一级 radix-4 结构来实现的。这样可以最大限度的复用公有电路。 3. ROM 优化过程 每级 ROM 存储该级运算的旋转因子,同一个旋转因子的 sin、cos(即 I、Q)两项拼 接在 ROM 同一个地址。Radix-4 蝶形有一个点对应旋转因子为 1,所以 ROM 中只存储 3/4 的旋转因子。如第一级 8192 点 FFT ROM 中存储 8192×3/4 个旋转因子。 以 8K 模式第一级旋转因子和第二级旋转因子为例来说明。本设计第一级为 8192 点 FFT,其旋转因子依次为 W0 8192 、W81192 、W82192 、W83192 、W84192 、W85192 、W86192 、W87192 、W88192 、 W9 8192 W 、 10 8192 W 、 11 8192 W 、 12 8192 …;第二级为 2048 点 FFT,其旋转因子依次为 W0 2048 、W21048 、 W2 2048 、 W3 2048 …。由旋转因子 WNnk 的可约性: WNnk = W mnk mN ,WNnk = W nk / m N/m 可得: W0 2048 = W0 8192 、 W1 2048 = W4 8192 、 W2 2048 = W8 8192 W … 2047 2048 W = 8188 8192 。可见第二级所有旋转因子的值均 可由第一级旋转因子中得到。第 3~6 级的旋转因子也可以根据同样道理得到。 采用 pipeline 结构,所有旋转因子的值虽然都可以由第一级 ROM 得到,但不能将第 2~ 6 级的 ROM 去掉。而是第一级与第二级共用 ROM,第三级与第四级共用 ROM。为保持 功率平衡第六级旋转因子的值都是除以 2 后的结果,因此第五、六级分别采用各自的 ROM。 3.1 同级 ROM 结构优化 第 1~6 级为顺序输入、倒位序输出的 radix-4 DIF FFT 处理,以第 1 级为例来说明。旋 转因子具有WN2i 、WNi 、WN3i 的形式, i = 0,1, 2...2047 ,分别对应 8192 个数据中第 2N/4、 N/4、3N/4 的数据。令 I = WNi 、 II = WN2i 、 III = WN3i ,则: I = W i N = cos( 2π N i) − j sin( 2π N i) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ cos( cos( cos( 2π 8192 2π 8192 2π 8192 * 0) − *1) − * 2) − j sin( 2π * 0) 8192 j sin( 2π *1) 8192 j sin( 2π * 2) 8192 ⎪... ⎪ ⎪⎩ cos( 2π 8192 * 2047) − j sin( 2π 8192 * 2047) (3) ⎧ ⎪ ⎪ ⎪ ⎪ cos( cos( 2π 8192 2π 8192 * * 0) 2) − − j sin( 2π 8192 j sin( 2π 8192 * 0) * 2) ⎪⎪... II = W 2 N i = cos( 2π N * 2i) − j sin( 2π N * 2i) = ⎪ ⎨cos( 2π * 2046) − ⎪ 8192 j sin( 2π * 2046) 8192 ⎪ ⎪ ⎪ cos( 2π 8192 * 2048) − j sin( 2π 8192 * 2048) ⎪... ⎪ ⎪cos( 2π * 4094) − j sin( 2π * 4094) ⎩ 8192 8192 (4) -3- http://www.paper.edu.cn ⎧⎪⎪⎪⎪ccooss(( 882211ππ9922 *0) − *3) − j sin( 2π 8192 j sin( 2π 8192 * 0) * 3) ⎪⎪... ⎪ ⎪cos( ⎪ 2π 8192 * 2046) − j sin( 2π 8192 * 2046) III = WN3i = cos( 2π N * 3i) − j sin( 2π N * 3i ) = ⎪⎪cos( 2π * 2049) − ⎨ 8192 ⎪... j sin( 2π * 2049) 8192 ⎪ ⎪⎪cos( ⎪ ⎪cos( 2π 8192 2π * 4095) − * 4098) − j sin( 2π 8192 j sin( 2π * 4095) * 4098) ⎪ 8192 8192 ⎪⎪... ⎪⎪⎩ cos( 2π 8192 * 6141) − j sin( 2π 8192 * 6141) (5) 当 i < 1024 时 II 的值可直接由 I 得到,下面来看 i ≥ 1024 时的情况。当 i ≥ 1024 时, II = ⎧⎪⎪⎪⎪ccooss((8221ππ92 ⎨ 8192 * * 2048) 2050) − − j j sin( 2π 8192 sin( 2π 8192 *2048) *2050) = ⎧⎪⎪⎪⎪−−ssiinn((8221ππ92 ⎨ 8192 *0) *2) − − j j cos( 2π 8192 cos( 2π 8192 *0) *2) ⎪... ⎪... ⎪ ⎪ ⎪⎪⎩cos(821π92 * 4094) − j sin( 2π 8192 * 4094) ⎪⎪⎩−sin(821π92 * 2046) − j cos( 2π 8192 * 2046) (6) 当 i < 683 时 III 的值可由 I 直接得到,下面来看 i ≥ 683 时的情况。 (1) 当 683 ≤ i < 1366 时, III = ⎧⎪cos( ⎪ ⎪⎪cos( 2π 8192 2π * * 2049) 2052) − − ⎨ 8192 j sin( 2π 8192 j sin( 2π 8192 * 2049) * 2052) = ⎧⎪ − ⎪ ⎪⎪ − sin( sin( 2π 8192 2π ⎨ 8192 *1) − * 4) − j cos( 2π *1) 8192 j cos( 2π * 4) 8192 ⎪⎪... ⎪⎪... ⎪⎪⎩cos( 2π 8192 * 4095) − j sin( 2π * 4095) 8192 ⎪⎪⎩ − sin( 2π 8192 * 2047) − j cos( 2π 8192 * 2047) (7) (2) 当 i ≥ 1366 时, III = ⎧⎪cos( ⎪ ⎪⎪cos( 2π 8192 2π ⎨ 8192 * 4098) * 4101) − − j sin( 2π 8192 j sin( 2π 8192 * 4098) * 4101) = ⎧⎪− ⎪ ⎪⎪− cos( 2π 8192 cos( 2π ⎨ 8192 * 2) + *5) + j sin( 2π 8192 j sin( 2π 8192 * 2) * 5) ⎪⎪... ⎪⎪... ⎪⎪⎩cos( 2π 8192 * 6141) − j sin( 2π * 6141) 8192 ⎪⎪⎩ − cos( 2π 8192 * 2045) + j sin( 2π 8192 * 2045) (8) 通过交换实部和虚部和简单的正负号改变,旋转因子 II 和 III 都可以由旋转因子 I 派 生出来。这样只需要通过存取旋转因子 I 就可以达到存取所有旋转因子的目的。同理第 3、 5 级也只需要存储对应的旋转因子 I 。这样大大减少了旋转因子存储器的大小。 -4- http://www.paper.edu.cn 3.2 最终优化 以 8K 模 式 为 例 , 如 上 节 所 述 , 第 一 级 ROM 中 存 储 内 容 为 {− sin( 2π *i), cos( 2π *i)} , i = 0,1, 2...2047 ,即在 ROM 中存储了[0, π ) 的 sin 值 8192 8192 2 和 cos 值。 由三角函数公式 sin(θ ) = cos(π −θ ) 可知,在[0, π ) 范围内只需根据 sin 值就可以得 2 2 到相应角度的 cos 值。因此 ROM 面积仍可减少一半。 这里 ROM 中存储了 (0, π ] 的 sin 值和 cos 值。 4 3.3 ROM 优化结果 从 表 1 可以看出最终优化结果比原始设计的 ROM 面积减少了将近 7/8。有效的减小了 FFT 处理器的面积。 Stage No. In (bit) 1 10 2 12 3 12 4 12 5 12 6 12 7 12 Sum 表 1 ROM 优化结果 Out 原始 各级 同级 (bit) 设计 共用 优化 12 4096*24 2048*24 4096*24, 2048*24 2048*24 12 1024*24 512*24 12 256*24 128*24 256*24 128*24 128*24 12 128*24 12 32*24 32*24 8*24 12 8*24 8*24 2*24 12 None None None 197,568 157,632 52,464 最终 优化 1024 *24 64 *24 4*24 2*24 None 26,256 4. 结语 根据三角函数公式 sin2 θ + cos2 θ = 1还可将 ROM 面积减小一半,但控制、计算都非 常复杂,不符号实时 FFT 处理要求。因此本文旋转因子 ROM 的优化已是最佳方案。 -5- http://www.paper.edu.cn 参考文献 [1] Chua-Chin Wang, Jian-Ming Huang, Hsian-Chang Cheng.A 2K/8K mode small-area FFT processor for OFDM demodulation of DVB-T receivers[J]. IEEE Transactions on Consumer Electronics, Vol.51.No.1, feb 2005. [2] 周海斌,刘刚.基于FPGA的高速实时FFT处理器设计[J].电子工程师. 2005-1. Vol.31 No.1. 54-56 Optimization of 2K-8K FFT ROM Lei Yanmin WuHan University of technology, Wuhan (430070) Abstract With the really need of high-speeding real-time Fast Fourier Transform (FFT), hardware structure uses a multi-stage pipeline synchronous structure, based on the structures and methods of SRAM、 SDF (single-path delay feedback)、DIF (decimation in frequency) and so on. The structure are divided into a serial connection of 5/6 level of radix-4 and one level of radix-2 butterfly units. Optimization is done in minimize the ROM , where the twiddle factors are stored, area. The whole structure are divided into several modules and all of them are described in Verlog HDL language, then have done the functional consistency simulation. Keywords: FFT,twiddle factor,ROM,radix-4 作者简介:雷艳敏,女,1980 年生,硕士研究生,主要研究方向是计算机网络通信技术。 -6-

    Top_arrow
    回到顶部
    EEWORLD下载中心所有资源均来自网友分享,如有侵权,请发送举报邮件到客服邮箱bbs_service@eeworld.com.cn 或通过站内短信息或QQ:273568022联系管理员 高进,我们会尽快处理。