（通信与信息系统专业论文）基于fpga的数据控制与处理系统的研究.pdf

硕 士 论 文基于f p g a的数据控制与处理系统的研究 ab s t r a c t f i e l dp ro gr田 旧 mabl e g 毗 八 们 旧 y ( f p g a ) ， a n ew typ e o f p r o g 旧 m m abl e d e v i ce， h as卜 ” n m ad ea g 以 川p r o g 限 s s inn % 笼 旧 t y e 别 rs . ith as n e 石 b l e p m gr a n 加ab lelo gi cwhi ch can be con 愉 1 印 t 】 y u ， 刃 to如pl e m e n t hi gh . s pe eddi gi 回 si gnai p r 。 以 ” s in g ， for it b 爬 别 ksth rd u ghthe l eve l l 如 i t o f p aral l e l and p ipel in e ， 成 沁 。 n fi gu汕l e l 哈c 花 份onch ipth us阮 n 莞 幻 u 找 冷 姗 bo丽li z e d e 拓 比 t i vely. the ory an d t e c hoo l o gy o f d i gi ta s i gn alp 砂 s s i n g ( d s p ) are w i d e l y l l s e di n m any fi e l ds，翔曲 as c o n ” ” u n i cati 叽voi ce p n x 思 s s i n g， com p u 姗 即d m u l t im edi aw i th th e ad vanon呱 。 f d i gl ta l t ec hn0 1 o gy. f ast f 。 面ert n 趁 凡 而 (f ft) l s the 价 t ec hoiq 此of d s p ， 朗 d i ts两fo rmin g t 加e i s sb o rt r a fe w劝 唱 esth and f 】 ， 5 . f f t h asa 加ad y p l a y edan i m po 沈 an t ro l e inm odem d s p . thi s th e s i s m ain l y stud i e s d a taa q u i s it i 叽 con trol l i n g and f ft b as ed onfi，g a t 七 eint er血ce b 沈 we . thein抚币阴 c 。 ” 往 。 icir c u i tandthep c/ 1 04 b us andallthe co n 七 。 l l in g s i gnal s 眼 m ai n l y r e a 】 1 朋 d b y th e i n t er fa cecon tt l l i n g c i 邝 ui t . t 加 e f p o ai nter fa c e con tr 0 l li n gm odul ec o n s i sts o f 目d r es s d 即ode r andadd r e s sg e n e r 即 泊 r . the add ressd e c o d er d 曰 x d 韶奴 co 能5 卯ndi n g portad d r es s t hr o u gh th el o 一 b 妞 b uswhi l e th e add re s s g en el 钊 泊 r 名 即耽 成 “th e s r a madd 优5 5 . f f t ad 0 p ts th e al god th mo f rad议 礴 ， 5 . s t e p casc ad i n g p roce s s i n g . the who l e s y st 曰 m uses p ipel i n e p a tt e rn ， p r 即 t i c a l ity . the m u l ti p l i 。 时 i o n u n i t i s ch ang edtos h i 丘 and ad d i t i o n uni t 妙 c o r d i cp 咖l in es t r l l c to 佗 wh i ch i s eas i erth an m u lti p l icat i on fo r th eh ard w 毗 . d 明】 . 训d r a m 助 dr o m are b u i l t insi d e th e sy st e m . these m e th 侧 如 】 e ra 扭the 0 pe旧in gan d n 戈 。 。 曲lyre sol veth c m u tl . i l y r e 引 对 ction of邝 sou n 哭 活and s pe曰 t 七 . de si gnad0 p t s q 姗 犷 tu s n 6. 0 so n w ar e provi d ed by a l ter ain c . and alter a 、 c 界l o n e l le pzc 2 0 f25 6 c 8 i s emp i 叮ed inthi s th esi s 二 ke y . ords: fpg a ， d a taa equ l s itio 氏fft，c o r d i c 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知， 在 本学位论文中，除了加以 标注和致谢的部分外， 不包含其他人己经发 表或公布过的研究成果， 也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已 在论文中作了明 确的说明。 。豁-江 业一 叫年 。 月 和 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。 对 于保密论文， 按保密的有关规定和程序处理。 研 究 生 签 名 : 一 恤皿 ， “7 年 月 巧 日 硕 士论 文基于f p g a的致据控制与处理系统的研究 1绪论 l l 课题来派及研究的目的和愈义 基于 护c的工业现场数据采集系统，虽然拥有较好的可靠性、准确性和兼容性等性 能，但是体积大且成本商。基于单片机的系统虽然成本低，但器件较多，系统复杂，开 发时间比较长，系统的可靠性差.p c 1 04 总线系统是一种新型的计算机测控平台，作为 嵌入式 p c的一种，在软件与硬件上与标准的台式 pc 体系结构完全兼容。基于 pc 1 04 总线的数据采集系统采用堆栈式连接、结构紧凑、体积小、功耗小、集成度高、扩展性 强、功能强大，特别适合应用于对体积和功能都有较高要求的工业现场侧控设备。用于 工业现场的嵌入式计算机的数据采集系统，由于工业现场环境的复杂性和多样性，对数 据采集系统的硬件和软件设计提出了更高的要求. 数字信号处理领域中f ft 作为时域和频域转换的基本运算，是数字谱分析的必要前 提，超级的运算能力在雷达处理、观测、跟踪、定时定位处理、高速图像处理、保密无 线通讯和数字通信、匹配滤波等的应用上极为广泛，而实时系统对 f 汀 的运算速度要求 更高。 对于f 盯 而言， 很多领域都提出了其高速实时运算的要求， 目前国际市场专用的f f t 处理器可以达到的速度数量级普遍为 1 024 点 16位字长定点、块浮点、浮点运算在几十 和数百户 : t级， 其中 采用tl公司的d s p62 x系 列达到“产 量级处理 速度， 64 x达到 3 6 脚t级， 但均需要多 片， 且如果 仅用于f f t 处 理则其 它功能 废弃，芯片性价比 就很 低。 而且通用d s p处理器构成的f ft 处理机采用循环编码算法， 程序量小， 但存在大量的冗 余运算，且需要许多跳转操作，处理速度较慢，不能满足现代数字信号处理实时性的要 求。在多处理器构成的并行处理系统中，使用抽取的方法实现对输入数据的分解，达到 并行处理的目的，可显著提高计算的速度，但在进行大点数 f fr 计算时，存在并行算法 与d s p 处 理器的寻址能 力不 相适应， 不能有效 利用数 据传输的 带宽和运算 能力 的问 题， 造成硬件资源的浪费。虽然通用的d s p处理器在结构上己考虑了 对各种算法的优化，同 时具有很大的灵活性，但对 f f t这种高度结构化的算法， 其效率仍然不是很高。 由 于fp以 ( f i el d pro g 旧 j l l m a b l e g 也a 厅 a y 现场可 编程门阵 列) 能够并 行处理， 容易实 现流 水线结构， 且升级简 便， 非常 适合实 现f f t 算法. f p g a厂商入 口 飞 r a 公司和x i l 仆 戊 公司都研制了f f t ip核，但是价格昂贵. 因此，自主研发基于fl，g a芯片的f 盯 ，把 f ft 实时化的要求和 f p g a芯片设计的 灵活 性结合 起来， 实现并 行算 法与硬 件结构的 优化配 置， 提高fft 处理 速度， 满 足现 代 硕 士 论文 基于fpo 人的数据控制与处理系统的研究 信号处理的高速度、高可靠性要求，成为了现今我国数字信号处理的一个研究点。 鉴于此种趋势，我将基于 fpg a的数据控制与处理作为自己的课题。根据工业现场 环境的数据采集需求，设计了墓于p c 1 04 总线的数据采集接口 控制电路， 及一个f 盯 处 理模块。 l z 国内 外研究现 状 1 2 .l 数据采集技术的发展 数据采集系统起始于 20 世纪50 年代，1956年美国首先研究了用在军事上的测试系 统，目标是测试中不依靠相关的测试文件，由非熟练人员进行操作，并且测试任务是由 测试设备高速自 动控制完成的。 由于该种数据采集测试系统具有高速性和一定的灵活性， 可以满足众多传统方法不能完成的数据采集和侧试任务，因而得到了初步的认可。大约 在6 0 年代后期，国外就有成套的数据采集设备产品进入市场， 此阶段的数据采集设备和 系统多属于专用的系统。 2 0世纪 7 0年代中后期，随着微型机的发展，诞生了采集器、仪表同计算机融为一 体的 数据 采集系统。由于这 种数据采集系 统的性能 优良， 超过了 传统的自 动检测仪表和 专用数据采集系统，因此获得了 惊人的发展。从 70年代起，数据采集系统在发展过程中 逐渐分为两 类，一类是实验 室数据采 集系 统，另一 类是工业 现场数据采集系 统。 就使用 的总线而言，实验室数据采集系统多采用并行数据总线，工业现场数据采集系统多采用 串行数据总线. 20世纪 80年代随着计算机的普及应用，数据采集系统得到了极大的发展，开始出现 了通用的数据采集与自动测试系统。该阶段的数据采集系统主要有两类，一类以仪器仪 表和采集 器、 通用接口 总线 和计算机等 构成。 例如:国 际标 准ice 62 5( g p 份 赚 口 总 线系 统就是一个典型的代表。这类系统主要用于实验室，在工业生产现场也有一定的应用。 第二 类以 数据 采集卡、标准总 线和计算 机构成。 例如: s t d总线 系统是这 一类的典型 代 表.这种接口系统采用积木式结构，把相应的接口卡装在专用的机箱内，然后由一台计 算机控制。第二类系统在工业现场应用较多.20 世纪 80 年代后期，数据采集系统发生 了极大的变化，工业计算机、单片机和大规模集成电路的组合，用软件管理，使系统的 成本降低，体积减小，功能成倍增加，数据处理能力大大加强。 加 世 纪 90 年 代至 今， 在国 际上 技术先 进的国 家， 数据 采集技术已 经在军事、 航空 电子设备及宇航技术、工业等领域被广泛应用。由于集成电路制造技术的不断提高，出 现了 高 性能、 高 可靠性的单片 数据采集系 统 ( d a s)。 数据采 集技术己 经成为 一 种专门的 技 硕 士 论文基于f f o人的教据控制与处理系统的研究 术，在工业领域得到了广泛的应用。该阶段数据采集系统采用更先进的模块式结构，根 据不同的应用要求，通过简单的增加和更改模块，并结合系统编程，就可扩展或修改系 统，迅速地组成一个新的系统。该阶段并行总线数据采集系统向高速、模块化、即插即 用的方向发展，典型系统有 v x i 总线系统，pc l 、p 力 总线系统等，数据位数已达到 32 位总 线宽度， 采样频率可以 达到 l oo ms ps .由于 采用了高 密度， 屏蔽型， 针孔式的 连接 器和卡式模块，可以充分保证其稳定性及可靠性，但其昂贵的价格是阻碍它在自 动化领 域普及的一个重要因素。但是，并行总线系统在军事等领域取得了成功的应用。串行总 线数据采集系统向分布式系统结构和智能化方向发展，可靠性不断提高。数据采集系统 物理层通信，由于采用 8 5485、双绞线、电力载波、无线和光纤，所以其技术得到了不 断发展和完善。其在工业现场数据采集和控制等众多领域得到了广泛的应用。 l 1 2 f f t的发展 随着f p g a技术的普及，以及 f ft 算法在各个领域的广泛应用，使用fpg a芯片设 计 f f t正在世界范围内兴起。国内外己积极地开展了有关应用与研究，并取得了良 好的 效益。 目前在国际上，以f p g a芯片生产厂商为主的公司在基于 fpg a设计f ft 的综合研 究方面处于领先地位.而且由于 f p g a芯片生产厂商对本厂生产芯片性能上的了 解，设 计的f ft 处理器可以最大限度的发挥芯片的性能。fpg a厂商 a l t e r a公司和 xil inx 公司 都研 制了f f t ip核， 性能非常 优越。 例如a li 飞 r a公司2 0 0 4 年最 新推出的f f t ip 核全面支持a li阳r a公司的最新器件，使用此f ft ip核计算 16位 1 024 点 f f t 仅需要 6. 63脚 . 然而这些公 司研 制的f ft 处理器 价格十分昂 贵， 因此还难以 在我国基层 应用领 域普及。 我国的fpg a技术起步较晚， 但是进入21 世纪后， 发展非常迅速。目前不少大学及 研究所都使用 f p g a芯片设计开发具有自主知识产权的fft ，但是由于起步较晚，基础 薄弱， 所设计的f ft 无论是速度， 还是可扩展性上都与国外有一定差距。 2 0 02 年罗雪苟、 詹阳详细的分析了f ft 使用即c a实现的几种方法， 并对于各种方法的优劣进行了讨论， 2 0 0 3 年连冰在论文里也对此作了详细的阐述。 1 999年徐公权等把 f ft 蝶形设计和c o r d i c算法联系起来，在 c o r d i c算法的基 础上完成单个蝶形单元，对于固定 n，都可预先设计制造好印刷电路板，只要把一批 c o r d i c蝶形芯片安装上即可，建立在 c o r d i c算法基础上的蝶形运算器，并在此基础 上构成的 f f t阵列式计算，实现了 fft算法的潜在并行性。2004 年李成诗等也利用 c o r d lc 算法实现实时定点的fft ， 设计了基 4 按时抽取算法， 采用双端口内置 r a m和 硕 士 论 文 基于f p g a的教据控制与处理系统的研究 流水线串 行工作方式。 设 计针对2 56点24位长数据 进行运算， 完成 一次运算约 为12声 。 1 999年刘朝晖、韩月秋以及 2 002 年党向东、孙阳、韩泽耀等也对使用 f p g a实现 f f t进行了研究。他们都是使用按时间抽取的基 4算法，部分单元或者全部单元采用流 水方式保证系统的速度，使存取数据、计算旋转因子和蝶形运算等操作协调一致。其中 党向 东设 计的f f t 处理 器完成2 56点f fr 计算需要26声 ， 孙阳以 及韩泽 耀设计 的f f t 处理 器完成1 0 2 4 点f fr 计算均 需要12 .8 脚. 2 003 年韩颖等采用力i nx 公司的fpg a设计了f f t处理器。采用流水方式对复数数 据实现了加窗、f ft 、 求模平方三种运算. 整个设计使用双基 2 蝶形运算单元，采用流水 线方式尽量避免瓶颈的出现，提高了系统时钟频率。 2 以 娜年刘国栋等使用基 2 算法设计了f 盯 单元， 他使用了a 口 王r a高性能的s tr 鱿 i x 器件对 5 12 点、1 0 2 4 点、2 048 点、 40% 点和 8192 点都进行了分析。 2 0 04 年督欣等通过 对1 0 2 4 点的f fr ip核进行扩展， 设计了40%点f 盯， 如果 系统输入 时钟为50 n 任 1 2 ， 计 算时 间约为0. 5 7 7 ms 。 2 005 年 刘晓明 等实现了 基于c p l d的点 数可灵活变换的 (i)f 盯 处理器。 输入 数据为 z o n 任 往时 ，10 24 点fft 运算 时间约为50脚 . i j本 论文主要 研究内 容 课题研究的具体内容如下: ( 1) 对f 盯 算法进行比 较， 选择一 种适 合于f p g a的算法。 (2 ) 分 析设计f f t 整体结构。 使用流 水线结构的c o r d i c 算法优化f ft 蝶型单 元， 并 根据f 盯 的寻址特点设计地址发生器. (3 ) 将算 法用veril o g h d l 实现. (4)达到 实时处理的 要求。 (5 ) 分析p c l 04 总 线拍 读写时 序， 并 根据各芯片要 求合理 设计接口 电 路. 硕士论文 基于f p g a的数据控制与处理系统的 研究 z fpg a技术概述 2. 1 可编程逻辑器件的发展史 可编程器件经历了比 较长的发展过程，它一直在数字硬件电路设计中扮演着重要的 角色。第一个得到广泛应用的可编程芯片是 p r o m，以 后发展到 epr o m， eepro m。 可编程器件的迅速发展也是具有戏剧性的，初期设想是根据任何组合逻辑电 路都可以最 终化简成与、非、加、或的形式，它们构成了数字电路设计的一个完备集。基于此早期 的p l d器件主要形式为a d d阵列后 接o r阵列， 中间的连接就是通过可编程点来进行 选择，以乘积和的形式实现所有的任意逻辑功能， 输出再接存储原件可构成时序电 路。 早期 的p a l (p r o 乡 盆 m m ab 把 a 巾y logi c) ， 其结 构为 可 编 程的a d d平面跟 一个固 定 的o r 平面， 输出 再经过一些触发 器。 还有p l a (p r o gr 别 m m 曲 le 切g ic a rray ) ， 其a d d与or 平 面都是可编程的，其他都大致一样.这些可编程逻辑器件在早期的小规模数字电路设计 时显示出了较大的优点，这些优点可以说是可编程逻辑本身的一些基本特点，最突出的 优点就是一块片子能完成不同的逻辑功能，而且延时模型简单固定，布局布线基本不用 使用者考虑， 输入输出 也较固定。 它们主要是用于一些基本的数字逻辑电路， 如译码器、 编码器、计数器、多路器等等，适合完成输入信号较多但功能较简单的数字电路.但它 们的其缺点也是明显的.首先是规模较小，等效门数在千门左右，完成复杂逻辑时需要 设计人员将表达式化为与或式， 不利于大规模的eda设计。 后来又出 现了一种g a 以 g 滋 e 为 ，y logi c) 器件， 它在结构上有了 新的 变化，出 现了 宏单 元的 概念， 输入的信号仍然要 经过一个可编程的与阵列， 通过编程连到宏单元内部固定的或阵列.或阵列输出再送入 相应的后级选择电路从而输出到片外，而宏单元内部结构与现代cpl d的输出宏单元、 fpga 中i o b ( 压 p u t o u tp utb i oc k ) 结 构 很 相 似. fpg 的 出 现， 则 是大 规 模可编程 逻 辑 器 件发展的又一大进步。 fpg a拥有完全崭新的一种硬件体系结构， 硬件资源更丰富， 灵 活性更大，设计更灵活。 198 5 年 x i l 仆 仪公司最先推出了第一块f p g a产品芯片， 其f p o 人产品芯片十几年 来一直居于领先地位。从此各种各样的 fpg a芯片相继问世，影响较大的厂家有: xil in x ， a li 飞 r a等。 经过十几年的发展， fpg a的 硬件体系结构和软件开发工具都在 不断的完善，日 趋成熟，发展到今天可以说f p g a是微电子技术，电路技术，e d a设计 技术的完美结合，设计者的主要精力只要放在电 路设计所完成的功能本身上，而不必在 一些基本逻辑模块产生上再耗费时间。 随着f p g a硬件体系结构的不断完善， 配套的e d a 开发工具的不断发展，可以毫不夸张的说。现代数字系统设计只局限于设计者的想象力 硕士论文基于f p g a的数据控制与处理系统的 研究 和创造力了。 z j及ra血 f p g a系列器件概述 s t rati x f p g a在2 0 0 2 年初推向市场 s tr at ix器件在结构和工艺上较前一代的 的特性，如d s p 块、三重的r a m 结构， 速存储器接口。 ，以突出的性价比迅速占领了高端 fpg a市场。 apex系列有了较大的提高， 增加了许多业界领先 内嵌lvd s 高速电路以及 dqs/dq 移项电路实现高 s tr at 议 f p g a采 用成熟的1 .s v 、 9 层 金属走 线、 0 . 13产 m 全铜工 艺 制 造. 本设计将采用s tr at i x 系列的epl s20b6 72c 6 实现f 盯及数据采集板的接口控制电路。 e p i s 2 0 b 6 7 2 c 6的特性见表 2 . 1 。 表2.i ep i s 20助72c6 的特性及管脚封装 逻辑单元 l el 8 4 6() ms l z r am1 94 m4 kram8 2 m一 r am2 d s p块l 0 锁相环 ( p l l ) 6 2 3 veriiogl 刃 d l 语言简介 早期的硬件描述语言是以一种高级语言为基础，加上一些特殊的约定而产生的，目 的是为了实现即1级仿真， 用以验证设计的正确性，而不必像在传统的手工设计过程中 那样， 必须等 到完成样机后才能进行实 测和调试。 决r i l ogh d l 就是在用途最广泛的c 语 言的基础上发展起来的一种硬件描述语言，它最初是于 1 9 83 年由 g a 比 叨 a yd es i gn auto m ation 公司为其模拟器产品开发的硬件建模语言。那时它只是一种专用语言。由于 他们的 模拟、 仿 真器产品的广泛使用， 珑行 l ogh i l 作为一种 便于使用且实用的 语言逐渐 为众多 设 计者所接受， 于19 90年被推向 公 众领域. openveri 且 ogln te m atio na l (ovi) 是促 进垅“ l ogh d l 发展的国际性组织， 19 92年o vl开始推广珑d l ogo v l 标准成为i eee 标 准， 这一努力最后获得成功. veril ogh d l 语言于1 995 年成为ie e e 标准， 称为ie e e s td 13 64一 1 995 . 完 整的 标准 在珑的 l oghdl 硬件描 述语 言 参 考手 册中 有详 细 描 述。 2 . 4 q “ a rtus ll 简介 q u ar tu s n 软件是alte ra的综合开发工具，它集成了alt e ra的fpg 户 以 c p l d开发流程 硕士 论文 墓于即6 人的数据控制与处理系统的研究 中所涉及的所有工具和第三方软件接口。通过使用综合开发工具，设计者可以创建，组 织和管理自己的设计。 q uartus n具有以下特点: 支持多时 钟定时分 析， logl c 兀 k t m基 于块的 设计， s 0 p c ( 单芯片可 编程系统)， 内 嵌si gnat tap n 逻辑分析 器， 功率估计 器等高 级工具; 易于管脚分配和时序约束: 强大的h d l综合能力; 支持的器件种类众多; 支 持铂 n d o w s ，s ol ari s 脚 us ，ll n ux等多 种 操 作 系 统 : 拥有第三方工具如综合，仿真等的接口。 2 3流 水线设计 简介 流水线处理是高 速设计中的一 个常用设计手 段.如果 某个设计的处理 流程分为若 干 步骤，而且整个数据处理是 “ 单流向，的，即没有反馈或者迭代运算，前一个步骤的输 出 是下 一个步 骤的 输入，则可以 考虑采 用流水线 设计方 法提高系统的 工作频率。 其 基本结 构是将适当 划分的 n 个操 作步骤单 流向串 联起来。 流水线操 作的 最大特点 是数据流在各个步骤的处理从时间上看是连续的.如果将每个操作步骤简化为通过一个 d触发器，那么流水线操作就类似一个移位寄存器组，数据流依次流经 d触发器，完成 每个步骤的操作。 流水线设计的一个关键在于整个设计时序的合理安排、前后级接口间数据流速的匹 配。 这 就要求每个操作 步骤地划分必 须合理，要统 筹考虑各 个操作步 骤间的 数据流量。 如果 前级操 作时间恰好等于 后级的操作时间， 设计 最为简单， 前级的愉出 直接汇入后级 的输入即可。如果前级操作时间小于后级的操作时间，则需要对前级的输出数据适当缓 存， 才能 汇入 后级， 还必 须注意数据 速率的 匹配， 防止后级 数据的溢出。 如果前级操作 时间大于后级的操作时间，则必须通过逻辑复制，串井转换等手段将数据分流，或者在 前级对数 据采用存储、 后处理 方式，否则 会造成与 后级的 处理节拍不 匹配 sj. 流水线处 理方式之 所以 频率较高， 是因为复 制了 处理 模块，它是 面积换取速度思 想 的 体现。 通过这种方 式设计的 芯片， 如今在f p g a的 设计中 使用相当 普遍。 硕 士 论文 基于f p g 冉的数据控制与处理系统的研究 3 f f t 整体方案选择 3. i f f t数学理论及算法 离散傅立 叶变换 口f 】 ， 开辟了 频域 离散化的 道路， 使数字信号 处理也可以 在频域上 采 用数 字运算方法 进行， 它可以 作为 一种 数学工具来描述离 散信号的时域与 频域的关系， 大大增加了数字信号处理的灵活性，特别是它的多种快速算法，使信号的实时处理和设 备的简化得以实现，所以离散傅立叶变换不仅在理论上有重要意义，而且在各种数字信 号处理中起着核心的作用。 1 %5 年c ool ey和知k e y 发表的关 于d 叮 的著名论 文， 使计算n点的d 叮 运算 量从 矿降 为 n lo g z n ， 引 起了 各 国 学 者 的 广 泛 关 注。 三 十 多 年 来， d fr各 种 快 速 算 法 相 继出 现， 成为数值数学方面最活跃的一个领域。 f fr 是 近代数 值数学最重要的 成果 之一， 在众多领域中发 挥了 很大的 作用， 它的 意 义远远超过一个算法的范围，它使某些数据的事后处理及系统的模拟研究进入到数据的 实时处理阶段，在数字信号处理和图像处理等方面为广泛采用数字方法打开了一个崭新 的局面。 i l i 快速傅里叶变换原理 有 限 长n 点 复 序列 减 月 的d 盯定 义 为 : xlm 】 = 艺 二 【 月 吟 恤k: 。 ， 1 ， 一 n 一 ) ( 31 ) 通过式 (3 . 1 ) 计算n点d f t ， 对每 一个 频率分量xlm l 需要 计 算n次复 数乘法伽 1 ) 次 复 数 加 法. 因 此 计 算n 个 不 同 的 频 率 分 量x lm 共 需矿次 乘 法 和 件 1 )n次 复 数 加 法 。 当 n较大时运算量是很大的。 其中还不包括计算平k 所需的运算量. 为此寻求其快速算法是 非常重要的。 目 前己 有的 计算离散 傅里叶 变换的算 法大 致可以 分为两 类， 一 类是将o f t 转 变为卷 积， 利用计算 卷积的方 法计算， 其代表是w i n o ad 快速傅立叶 变换算法 ( w r r) 和素因 子伊 fa: p m e f 咖 r alg o ri th nl ) ，另 一 类是递归 型算法， 是将一维的d f t 化为容易 计算 的二维或多维 d fr ，且这个过程可以重复，其代表算法是 c o o l ey-tukey算法、 r ader-b 嘟n er算法和分裂基算法等。 相比较而言，w曰队 和p fa 在运算量上占优，用的 乘法 器比c oo l ey一 ke y 算法少， 但控 制复杂 ，控制单 元相对实现 起来复杂. 在硬件实现 中，需要考虑的不仅仅是算法运算量，更重要的是算法的复杂性、规整性和模块化。控 制简单、实现规整的算法在硬件系统实现中要优于仅仅是在运算t上占优的算法。分裂 硕 士 论 文 基于f p o a的数据控制与处理系统的研究 基算法也具有一定的优势，综合了基 4 和基2的运算特点，但其l型蝶式运算结构在控 制上要复杂一些。 1 1 )墓4 算法讨论 f 盯 算法基本原理就是将长序列的d f t分解为短序列的d ft ， 然后再根据这些短序 列的 d 盯 表达长序列对应的d 盯 。这种算法充分利用旋转因子甲k 的特性，从而形成结 构简单的d f t 快速算法f f t . 基4 按时域抽 取旧1 刀是 在时域x 你 ) 上 将k 分 为4 个 短序列，即 .2)习.4) (3(3(3 xl 【 k 】 = x 【 4 k ， k = 0， 1， n 1 4 一 1 气 【 k 】 = x 【 4 k + 1 】 ， k 二 0， 丸 n 1 4 一 1 石 【 k 】 = x 【 4 k + 2 】 ， k = 0 ，1 ， n / 4 一 1 凡 【 k 】 = x 【 4k+ 3 】 ， k = 0， 1， n 1 4 一 1 x 【 m 】 = z x 【 k 】 吟 = 艺x 【4 k 】 叫细 + zx 【 4 k 川畔 + ，冲 + zx 【 4 k + 2 】 畔“ ，冲 + ， ，4立 -o 艺x 【 4 k + 3 】 畔， + ，冲 轰 戒月 叫加 + 畔艺x:月 叫加 + 衅 艺气 【 月 叫 + 心 艺、 【 kl 叫加 扮 -0 . _ ， 竺 j 姿 二 翻 由于畔 ，=e 一 份 ， e川 弓= 环 侃故 上 式 可 表 示 为 : x 【m 】 = zxl 【 k 晓 + 畔艺毛 【 k 】 味 + 岭 艺从月 咪+ 叫 艺x.月 环 侃 用戈 m l 、 凡m l 、 凡二 、 x. 二 分 别 表 示 序 列 xt lk 、 毛 k 、 毛 i k l 、 x k 对 应 的 n /4点d 盯 ，进一步整理得: 硕 士 论文 荃于即c 人的数据控制与处理系统的研究 x m 】 一 戈 【 m l + 畔凡【 m 】 + 吟凡【 ， 1 + 叫 戈【 m 】( 3 .5 频率 变量m的取值为厉 = 0 ， 1 ， ， ( n / 4)一 1 。 由 于 序列xl k l 、 毛 k l 、 xa k 、 礼 k l 的 长度都是n /4 ， 因而对 应的d f t : 戈脚 、 戈1 ， 1 、 戈 ， 、 x.l m 的长度也是n / 4 ， 而x i 脚 1 的 长度为n ， 因此需 要利用x : 【 ， 、 x : 1 ， 、 戈l m 、 x.m 的 周期 性以 及旋转因子w的 特性才能 够表达全部的x lm . 序列的d fr 都 蕴涵着周期性， 即戈m1 、凡i m、 戈i m、 x.i ml都是周期为n /4的 序列，它们满足: 戈【 ， + n / 4 1 = x.【m 】 戈【m + 万 1 4 】 = 戈【 ， 】 戈【m + n 1 4 】 = 凡【 m 】 x.【 ， + 万 1 4 1 = 戈【 m l 二= 0 ， 1 ， ， ( n/ 4 ) 一 1 用= 0 ， 1 ， 一， ( n1 4 ) 一 1 功二 0， 1 ， ， ( n/ 4 ) 一 1 m二 0 ， l ， ( n/ 4)一 1 ( 3 .6 ) 旋转因子满足: 开 罗 ， 用 = e 一 加 + 2 万 1 = 忍 一 j 畔 畔 = 一 畔 = 一 卜 畔 刁 脚 4 = 。 ， 瓜 衅 = j. 畔 +414 = 畔 = 1. 畔 ( 3乃 畔畔畔 利用上述特性可得: x 【 m 】 = 戈【 。 】 + 畔凡【m 】 + 畔 凡【m 】 + 叫 x.【m 】 x 【 m + n 1 4 】 ， 戈【 ， 1 一 j 衅戈【 m 】 一 叫“ 戈【 ， 】 + j 吟x.【m x 【 m + z n 1 4 】 = 戈【， 】 一 畔戈 【 m 】 + 畔 凡 【 m 一 砂x.【 m 】 x 【 m + 3 n / 4 】 = 戈 【 ， + 了 衅x z 【 m 】 一 叫 凡 【 m 】 一 少 叫 戈【 ， 】 ( 3 . 8 ) 1.j-1-j 1-1- 1.勺-l少 rwewesese 也可用矩阵表达为: rx 【 ， + 万 】 x 【 二 + n 1 4 1 x 【 m + z n 1 4 x 【 m + 3n1 4 】 l r 】!叫 衅 月叫 嵘 塑叫 些 二 j l x 。 1 功 叮- ( 3 .9 ) 式(3 .8) 和(3 .9 ) 是按基4 分 解的四 个子 序列 对应的d ft 合成xt k的d f t 的计算公式， 其实现过程可用信号流图表示，如图3 . 1 所示，该信号流图是基4按时间抽取 f ft 运算 的基本单元。图3 .2为其简化形式。 硕 士 论文 墓于f p ga的效据控制与处理系统的研究 xi间 附创+3n xlnxlmxlm ，.j钾.jl.jl.月 m口口口 xxxx 图3 . 1墓四的信号流图 图3 二简化信号 流图 这 里还需要 特别分析的 是第一级的4 点d 盯。 根据d ft 定 义， 4点 序列 a， b， c， d 的 d ft 可由下列矩阵表示: 一; 洲 =一洲训 l 戈15 【 i j 一 1一 jjl 列 (3. 1 0) 比较式 3 .9与式 3. 8 ， 两者矩阵运算相同。 以1 024点d ft 为例，首先将这个序列按倒序排列;第一级迭代输入为 2 56 个 4点 时间 序列， 输出为 对应的d ft: 第二级迭 代， 输入 为2 56个4 点短序列d 盯， 将它们4 个一组合成为 16点d f t ，输出为 64 个 16 点短序列d ft;第三级迭代，输入为64 个 16 点d 盯， 再 将它们4 个一 组合成为64点d ft， 输出 为16个64点d ft; 第四级 迭代， 输入为 16个 64 点d ft， 再将它们 4 个一组合成为2 56 点d ft ， 输出为4 个 2 56 点 d 盯 ; 第五级迭代，输入为4 个2 56 点 d ft ，最终将它们合成为 1 024点的长序列d 盯 。 硕 士 论文基于f p o a的致据控制与处理系统的研究 3. 2 f r y 设计方案选择 3. 2. i f f t整体结构选择 f fr 整体结构形式有四种:顺序处理、并行迭代、阵列处理和级联处理。 顺序处理:顺序处理机只使用一个 f f t 蝶型运算单元。 输入t、 中间结果及输出 量都使用同一个存储装里。这种顺序处理机所使用的硬件设备量最少。它的运算顺序是 根据蝶型图按照 自 左向右，自上向下的顺序先算第一列的所有蝶型，然后依次再算第二 列、第三列的所有蝶型，直到算完所有蝶型为止。这样就完成了f f t的全部运算.这种 处理方法的优点是只使用一个蝶型运算单元，节省硬件资源。由于不是并行运算，所以 缺点是速度缓慢，而且由于只使用一个运算单元，控制复杂。 并行迭代和阵列处理: 假若对一列中的n12只蝶型用n12个蝶型运算单元并行运 算. 如用4 个 运算单元一起算 第一列的4 只蝶型， 然后再依次算 第二列、 第三列的4 只 蝶型，即每列的运算是并行的，而各列相继的迭代是连续的，这就是并行迭代运算。它 的特点是: 有n12个运算单元， 并行执行n/2个蝶形运算。 也可以考虑在一个处理机中 并行 实现 全部蝶形 运算， 它是把顺 序和 级联的方式组 合起来 进行， 如在n= 5 时， 它可以 并行运算 12只媒型。 并行迭代和阵列处理这两种方式计算速度最快， 但是它们耗费的资 源也是最多的， 以基2的 1 024 点f 盯 运算为例， 使用并行迭代方法需要 512个蝶型运算 单元; 而使用阵列处理方式资源的使用更是惊人，孺要5120 个蝶型运算单元，实际中实 现是有很大困难的。 级联处理:假若每一级都使用一个独立的蝶型运算单元来加以运算，即用第一个 蝶 型 运 算 单 元 计 算 第 一 列， 第 二 个 单 元 计 算 第 二 列. 基2 的n 点f ft运 算 需 要logz n 个 蝶 型 运 算 单 元 . 级 联 处 理 的 特 点 是 : 使 用!og z n个 运 算 单 元 并 行 运 算 ， 每 个 单 元 执 行n /2 次蝶形运算;每个运算单元含有时延用的缓冲存储。通过对这四种结构的分析，级联处 理最适合本设计，所以选用级联结构。 3 j jrad 吐蝶型算法选择 在基 4和基 2算法硬件实现的比较中，1 个基 2蝶形运算由 1 个复乘和 2 个复加组 成， 而 1 个基4 蝶形运算包含 3 个复乘和5 个复加， 在硬件上实现基 4 虽然会占用f p g a 中更 多的 资源， 但是随着芯片 集成度的 不断 提高，用 这种并行 结构实 现的f 盯 运算 其优 越性将越来越明显。荃 2算法虽相对墓 4 算法占用的资源较少，但为满足系统运算的速 度，要求 f ft 有更小的流水周期。当对fl，g a内部资源占用较少时，这一速度要求不难 满足;但由于 fpg a的内部连线资源有限，故当设计中对于fpg a的资源利用率相当高 硕 士论 文 墓于f p g a的数据控制与处理系统的研究 时，各信号间连线延时加大， 这一要求往往不容易满足。 若采用高基数结构的基4 算法， 降低了运算量，同时提高了速度，在系统时钟频率相同时，基 4处理器运算速度是基 2 处理器的 2 倍，所以基4算法更便于对f p g a的布局、布线和调试。 表31 几种 r adi x 的运算次数 f f t算法实数乘法实数加法 基 2 ( 2 10 9 : n一 4 ) n+ 4( 3 1 0 9 : n一 2 ) n+ 2 基4( 1 . 5 1 0 9 : n 一 4 ) n+ 4( 2 .7 5 1 09: n一 2 ) n+ 2 基 8 ( 1 . 3 3 3 l o g z n一 4 ) n+ 4 ( 2 .7 5 1 09: n一 4) n+ 4 基 1 6( 1 . 3 1 2 5 1 0 9 : n一 4 ) n+ 4( 2 7 1 8 1 0 9 : n一 2 ) n+ 4 几种 r a d 认的运算次数见表 3 . 1 ，由表可知:从基 2 到基 4 ，乘法和加法的运算次数 发生了比较大的跳变，而从基 4 到基 8 以及基 16运算次数变化的幅度就不是很明显了。 而基2的算法，控制操作起来最简单，基 4 算法的控制性复杂些，但仍然具有和基 2 算 法的可类比性。 而基 9 与基 16算法的控制复杂度与基 4 相比就很明显了。 对运算速度和 控制性进行折中考虑，基4算法在 f f t处理实现中具有最高的性价比，所以选择使用基 4算法。 3 j jr a m 的选择 利用 f ft 同址运算的特点可以节省 r a m容量， 基 4运算时其结果可以返回原址来 替换原有输入数据，通过这个同址运算的特点，可以 将输出 r a m 省去，而在每次蝶型 运算结束后通过输出选择器重新回到输入 r a m的原址。 尽管 这样可以 减少了r a m 的容 量， 但是 其缺点 也相当明显: 首先在 控制上要在 每 次蝶型运算结 束后回存 数据，比 较浪费时间 ，而 且再产生 相同的地址 使地址发生器的 控 制变的更 复杂:其次要 涉及到 大节拍的 数据搬移， 即每 一级运 算完成后 进行 r a m之间 的 “ 拷贝” ，这个时间开销也相当巨大。由于存储和运算可以同时进行，故 r a m采用乒 乓型的 分时 共享模式， 在本设计中 每一级 都使用了2 048 x 3 2 bits 的双端口r a m， 此r a m 分为两部分，当第一部分用于当前级输入运算数据即读数据时，另一部分用于前一级结 果的存储即写数据，当该级 1 024点运算结束后，r a m的两部分功能交换。尽管增加了 r a m的开销，但是简化了地址发生器，提高了速度。 硕士论文荃于f p c a的 数据控制与处理系统的研究 4f 卜 一 1 ， 4.if f t 具体模块设计 整体结构设计 根据第三章的讨论，综合fpg a的性能。采用了级联结构，设计了一个使用基4 算 法10 24点3 2 位( 16位实数，16位虚数 ) 的f f t 处理单 元。 整体结构框图 如图4 . 1 所示: 控制单元 日粳 第五级拱形运算单元 一 一 一 第-级蛛形运算单元 愉入地址 发生器 轴入地址 发生器 整序单元 溉恶 输出地址 发生器 物出地址 发生签 图4 . i f f t 整 体结 构框图 如图4 . 1 所示， 此f 盯 处理器采用6 级流水线结构， r a m采用乒乓操作， 每组r a m 都使用地址发生器进行控制。 4. 2 蝶形单元设计 f