LTE物理上行共享信道中FFT算法分析与FPGA实现

2010 年 4 月 第 4期 电 子 测 试 ELECTRONIC  TEST Apr.2010 No.4 43 LTE物理上行共享信道中FFT算法 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 与FPGA实现★ 陈发堂，郑向波 (重庆邮电大学通信与信息工程学院，重庆 400065) 摘要：快速傅里叶变换FFT作为数字信号处理的核心技术之一，使离散傅里叶变换的运算时间缩短了几个数 量级，并在LTE中有重要的应用。 现场可编程门阵列FPGA是近年来迅速发展起来的新型可编程器件。本文 主要研究如何利用FPGA实现FFT算法，包括算法选取、算法验证、系统结构设计、FPGA实现和测试整个流 程。设计采用Good-Thomas算法，利用Verilog HDL描述的方式实现了不定点FFT系统，并以FPGA芯片virtex4 为硬件平台，进行了仿真、综合、板级验证等工作。仿真结果表明其计算结果达到了一定的精度，运算速度 可以满足一般实时信号处理的要求。 关键字：LTE；非基2；verilog HDL；Good-Thomas FFT；FPGA实现； 中图分类号：TN929.5 文献标识码：A Algorithm analysis of FFT in PUSCH and FPGA implementation for LTE Cheng Fatang，Zheng Xiangbo (School of Communication and Information Engineering, ChongQing University of Posts and Telecommunications, ChongQing, 400065, China) Abstract:Fast Fourier Transform is the core technique of DSP, and its performing time is shorter a few stages than DFTs,and in the LTE system FFT has important applications.Field Programmable Gate Array is a new type of programmable device at high speed development in recent years. This paper studies the implementation of FFT processor based on FPGA. It includes selection and validation of the arithmetic, design of the whole architecture, implementation and test of the system. This design adopts the algorithm of Good-Thomas, and realizes a variable points FFT system by using Verilog HDL. Then it finishes simulation,synthesis and verification of the system on Virtex4. The simulation indicates that the result of calculation can reach equivalent precision and the operation speed of FFT can satisfy the request of commonly real-time signal processing. Keywords:LTE；Non-radix-2；verilog HDL；Good-Thomas FFT；FPGA implementation； ★基金项目：“新一代宽带无线移动通信网”国家科技重大专项 TD-LTE无线综合测试仪表开发(2009ZX03002-009) 资助 Application of MCU & PLD 44 2010.4 0  引言  为了快速计算 DFT, 常见的算法有基 -2，基 -4 算法，分裂基算法，Good-Thomas 算法，Cooley- Tukey 算法。然而在硬件实现的过程中，需要考虑 的不仅仅是算法运算量，更重要的是算法的复杂性， 模块化。而 Good-Thomas 算法可将变换长度 M 分 解成互质因子的乘积，在变换的过程中合理的选取 互质因子，可以减少旋转因子的乘积，使运算部件 和存储部件之间的操作减少。通过综合考虑，本文 采用 Good-Thomas 算法，并以满足不定点 12 及 15 点的 FFT 硬件设计为切入点，对这种算法进行了硬 件实现与验证，以满足 LTE 系统中对于不定点 FFT 变换的要求。 1  FFT算法分析 Good-Thomas 算法分析 离散傅里叶变换 (DFT) 将时域信息转换成频域 信息。长度为 M 的序列 x(n) 的离散傅里叶变换可 写成 ： 公式中， ，M 为 DFT 变换区间长度。 M 点 DFT 的复乘次数等于 , 通过把 M 点的 DFT 分解成几个较短的 DFT，可使运算量大大减少。 而 FFT 算法就是不断的把长序列的 DFT 分解成几 个短序列的 DFT，并利用旋转因子的周期性和对称 性来减少 DFT 的运算次数。 Good-Thomas 算法可将变换长度 M 分解成两 个互质因子的乘积即 ： , 将长度为 M 的 DFT 变换为二维的 DFT，更高的维数可以通过 反复迭代替换其中的一个因子就能实现。 将时域输入信号索引 n 表示成 ： 　 进行变换。利用这种索引变换就可以将输入序 列变换成一个二维序列。 将输出序列索引 k 表示成 ： 进 行变换。 由 于 G o o d - T h o m a s 算 法 需 将 M 分 解 成 两 个 互 质 因 子 的 乘 积， 因 此 A,B,C,D 的 选 取 应 满 足 下 面 公 式 ： ， 从而得到 Good-Thomas 算法的索引映射公式 ： (1) (2) 式 中 : , 为欧拉函数 , 是 0 到 中与 互素的个 数，如 =4。 2  Good-Thomas算法描述 利用 Good-Thomas 算法进行 DFT 运算，主要 分为以下几个步骤 ： （1） 根据公式（1）对输入序列进行索引变换。 （2） 进行 次长度为 的 DFT 的计算。 （3） 进行 次长度为 的 DFT 的计算。 （4） 根据公式（2）对输出序列进行索引变换。 下面以 12 点为例具体说明相关的映射关系 微处理器与可编程器件应用 45 2010.4 12 点的 Good-Thomas 算法 FFT 分成两级，其 中第一级有 3 个变换长度为 4 点的 DFT，第二级有 4 个变换长度为 3 的 DFT，并且两级之间没有旋转 因子 。此时的输入映射关系为 ： （3） 输出映射关系为 ： （4） 3  FFT处理器的硬件实现 3.1  FFT处理器 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 分析 以 12 点 FFT 为例，其他点数的 FFT 变换都有 相同的流程。如图 1 所示。 图1  12Good-Thomas算法的FFT流程框图 图 1 中的模块 1 是对输入序列按照输入索引进 行重新排序并分成 4 组，每组 3 个输入序列，第 2 个模块是对各组数据进行 4 点的 FFT 变换并进行暂 存，第 3 个模块对第一级 FFT 的计算结果进行重新 排序使得进入第二级 FFT 变换输入端口得到正确的 数据，第 4 个模块进行第二级 3 点 FFT 变换，第 5 个模块是对第二级的输出以输出映射关系正确的输 出。 3.2  FFT处理器系统结构 以 12 点 FFT 为例，其他点数的 FFT 变换都有 相同的处理器系统结构。如图 2 所示。 为了达到高效率的要求，整个 FFT 处理器的 系统结构如图 2 所示，包括一个控制器，控制整个 电路的时序工作，保证系统各部分之间的协调工作， 一个地址产生器，在控制器的控制下产生旋转因子 所需的各个地址，保证运算器按照时序要求处理数 据，一个 4 点处理单元，一个输入寄存器，一个输 出寄存器，两个存储旋转因子的 ROM，其中一个 ROM 存储 4 点的旋转因子，另一个 ROM 存储 3 点 的旋转因子，两个 RAM，其中一个 RAM 与外部的 输入输出接口相连，另一个则用来处理内部数据。 图2  FFT处理器系统结构图 4  非基2FFT多种模式下处理器实现 过程 由于在 LTE 物理上行信道中存在有多种点数的 FFT 变换，因此在硬件实现的时候必须对于寄存器 及相关的旋转因子的存储方式作出必要的改变，以 简化相应的寻址操作，适应不同点数的 FFT 变换的 需要。 首先，根据不同点数，由该算法可以得到 3 个 参数，分别是 2 个分解的质数和数据本身的长度， 这里分别表示为 first_prime，second_prime，length。 其 次， 由 于 Good-Thomas 算 法 中 第 一 步 数 据需要变换顺序，为了便于取数据的方便，这里 设置一个寄存器大小，其等于 2 倍的输入数据的 长 度， 输 入 数 据 按 照 以 下 方 式 存 放， 即（0，1， 2.……,length-2，length-1，0，1，2.……length-2， 索引变 换之后 的序列 进行第 一级FFT 变换：3 个4点的 DFT 对第一 级的FFT 变换结 果进行 重新排 序 进行第 二级的 FFT变 换：4个 3点的 DFT 对计算 结果按 照输出 索引进 行重新 排序 输入 序列 x(n) 输出 序列 x[K] 时序控制器 RAM 存储器 地址产生器 输入寄存器 输出寄存器 ROM2 4点FFT 处理单元 3点FFT处理单元 计数器 ROM1 Application of MCU & PLD 46 2010.4 length-1，0，0.……，0，0），这里 0，1，2 指的是 输入数据的顺序，以这种方式存放数据可以简化存 入数据的地址操作。这里的 length 只是指里面的有 效数据长度，该寄存器的实际长度应该是最大寄存 器为 Max 位的 2 倍，以便保证最大的时候依然够用， 并且超出的部分全部为 0。 以 15 点 FFT 第 一 步 为 例 来 说 明 简 化 的 过 程， 其规律如图 3 所示。 由图可见，抽取共计 3 次等于分解的第二个质 因子，每一次抽取的数为分解的第一个质因子，且 相邻抽取数之间的间隔也等于分解的第二个质因子。 由于寄存器的长度要满足最大系数的要求，当输入 系数个数不是最大的时候在寄存器多出的位置，即： 图 3 的省略号的位置应该补零。 利用以上规律可以简化寻址过程，使算法更具 模块化。 下面描述使用固定的乘积项数来计算不同点的 乘累加计算。 首先 ：初始化的时候，系数寄存器已经清零， 数据输入时的顺序已经可以满足算法的输入要求。 系数寄存器的大小要以满足最大系数的点数为准。 当使用的系数不满足最大的时候，在放置完使用系 数以后，要将该寄存器剩余的部分补零。 其次 ：由于要实现不同点数的 FFT 变换，在 做乘累加的时候必须以最大的乘累加项数为准。如 要实现 12 点和 15 点的 FFT（12 点可以分解为 4*3， 15 点可以分解为 5*3），那么乘累加的项数应该取 最大的项数 5。则第一步计算可以统一可以写成如 下表达式 ： Result ＝ A1*B1+A2*B2+A3*B3+A4*B4+A5*B5; 其中 A 代表输入的数据，B 代表系数乘积项。 为了要满足使用这个表达式来计算不同项数的 乘累加计算，需要对于不同点 FFT 乘积系数的存储 顺序作出一定的变化。即 ：系数存储的时候要先先 列后行的顺序存放。 这样存放以后，在取数进行计算的时候只要每 隔一定的间隔位取数相乘即可，不但简化了程序的 设计，还可以保证正确计算对应点的乘累加。 如 ：以 4 点计算为例，第一次使用的系数地址 为 0，4，8，12，16， 而 系 数 只 有 16 个（0 到 15， 多于的全为 0），故第 5 项 A5*B5 始终为 0，可以满 足计算要求。 那么现在就可以直接利用表达式 ： Result ＝ A1*B1+A2*B2+A3*B3+A4*B4+A5*B5 来计算不同点的 FFT 变换了。这是也就完成了 第一步计算 FFT 的处理。 5  综合和仿真 平台 ：Xilinx ISE 10.1 和 ModelSim SE 6.1d 硬件 ：virtex4 实现算法 ：基于 Good-Thomas 的 FFT 算法 系统输出频率如图 4 ～图 6 所示。  图4  实现频率仿真结果 图3 微处理器与可编程器件应用 47 2010.4 输入及输出分析 ： 图5  15点FFT部分仿真结果 图6  12点FFT部分仿真结果 结果以流水线的方式连续输出，保证数据输出 的连贯性。可以根据不同系统需要对于数据采用不 同的精度表示，当然这也会消耗更多的额外资源。 6  结束语 Good-Thomas 算法的 verilog 程序已通过 Xilinx ISE 10.1 的编译，仿真验证及板级验证，仿真结果 与理论值一致，可以精确到 LTE 系统要求。该算法 满足了硬件对算法的模块化、 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf 化的要求，因此 它可以充分发挥硬件的优势，利用硬件的资源，从 而实现硬件与算法相结合的一种优化 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。本文采 用了完全串行，并以资源优先的方式实现了不定点 FFT 算法，在实际的系统中，如果对于输入输出时 间有特殊的要求而资源相对宽裕的情况下，其结构 还可以改为并行或部分并行的方式实现，具有很大 的灵活性。 参考文献 [1] 夏宇闻 .Verilog 数字系统设计教程 [M]. 2 版 . 北京 ： 北京航空航天大学出版社，2008. [2] 3GPP TS 36.211 V8.8.0 “Evolved Universal Terrestrial Radio Access(E-UTRA);Physcial Channel and Modulation”[S]. [3] ( 美 ) 贝斯 . 数字信号处理的 FPGA 实现 [M]. 北京 ： 清华大学出版社，2002. [4] S. C. Chan and K. L. Ho, "On indexing the prime-factor fast Fourier transform algorithm," [C], IEEE Trans. Circuits and Systems 38 (8), 951-953 (1991). [5] Yun-Nan Chang; Parhi, K.K. “An efficient pipelined FFT architecture"[C], IEEE Transactions on Volume 50, Issue 6, June 2003 Page(s): 322-325. [6] Xilinx Inc. Foundation Series User Guide.http://china. xilinx.com/support/documentation/user_guides/ug071. pdf 2010-01-03. [7] 王晓明 , 韩晓军 . 快速傅里叶变换的 FPGA 实现 [J]. 天津工业大学学报，2005，(24)2. [8] 满峰 基于 FPGA 的高速 FFT 处理器的设计与实现 [J]. 科学技术与工程，2006(6):17. 作者简介：陈发堂，副教授，硕士 生导师。长期从事移动通信系统终端开 发项目的物理层算法及系统仿真工作， 目前从事LTE-TDD综合测试仪表项目的 开发。 E-mail:chenfatang@cqcyit.com LTE物理上行共享信道中FFT算法分析与FPGA实现 作者： 陈发堂， 郑向波， Cheng Fatang， Zheng Xiangbo 作者单位： 重庆邮电大学通信与信息工程学院,重庆,400065 刊名： 电子测试 英文刊名： ELECTRONIC TEST 年，卷(期)： 2010，""(4) 被引用次数： 0次 参考文献(8条) 1.夏宇闻 Verilog数字系统设计教程 2008 2.3GPP TS 36.211 V8.8.0 "Evolved Universal Terrestrial Radio Access(E-UTRA);Physcial Channel and Modulation" 3.贝斯 数字信号处理的FPGA实现 2002 4.S C Chart.K L Ho Onindexing the prime-factor fast Fourier transform algorithm 1991(8) 5.Yun-Nan Chang.Parhi K K An efficient pipelined FFT architecture 2003(6) 6.Xilinx Inc Foundation Series User Guide 2010 7.王晓明.韩晓军 快速傅里叶变换的FPGA实现[期刊论文]-天津工业大学学报 2005(2) 8.满峰.汶德胜.朱家佳 基于FPGA的高速FFT处理器的设计与实现[期刊论文]-科学技术与工程 2006(17) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_dzcs201004011.aspx 授权使用：陕西理工学院(sxlgxy)，授权号：c00fe0a9-7eb4-4f9b-b4d4-9df20100ccf0 下载时间：2010年9月15日