（信号与信息处理专业论文）自适应滤波器的vlsi实现.pdf

摘要 随着现代通信、多媒体和高速网络互联技术的融合与发展，引发了宽带革 命的到来。宽度技术需要处理的模拟和数字数据量呈指数型增长。虽然摩尔定 律仍适用于目前最快的d s p ，但需要的性能水平与实际d s p 器件所提供性能水 平间的差距仍在不断增大。因此，为满足宽带技术带来的挑战，必须寻求新的 数据处理方法。 在数据吞吐量大，并行度高，算法比较简单，状态较少，流程比较简单和 对时延要求较高的场合，应用f p g a 非常适合。 本文在深入研究各类硬件有效算法的基础上，以f p g a 为平台完成了，自适 应滤波器的设计。主要完成的工作如下： ( 1j 使用不同方法，在f p g a 上实现了多种乘法器结构的硬件描述，并给 出了这些方法的优缺点和适用范围。在此基础之上，提出一些优化、改 进措施。 ( 2 ) 对d a 算法进行了较为深入的研究。在阐述算法原理基础上，用硬件形 式对d a 算法进行描述。针对以性能为最终目标和以系统资源利用率为 最终目标这两种情况，提出相应的优化方案并给出了这些优化方案的 硬件描述。 ( 3 j 对c o r d i c 算法以及两种工作模式进行了较为深入和系统的研究。 基于f p g a ，实现了高资源利用率的迭代结构c o r d i c 处理器和高性 能的在线式c o r d c 处理嚣。对于c o r d i c 旋转带来的增益问题，提 出了自己的改进方法。 ( 4 ) 对自适应数字滤波器进行了较为系统的研究，归纳了各类自适应算法在 具体实现过程中的共同点a 在此基础上，完成了自适应滤波器( 基本模 型) 的设计，并给出了该设计的硬件描述。 关键词：超大规模集成电路，现场可编程门阵列，分布式算法，自适应滤波器 坐标旋转数字计算 a b s t r a c t w i t ht h ei n o s c u l a t i o na n dd e v e l o p m e n to fm o d e r nc o m m u n i c a t i o n ，m u l t i m e d i a a n dh i g hs p e e dc o n n e c t e dn e t w o r kt e c h n i q u e s ，b r i n g st h eb r o a d b a n dr e v o l u t i o n s y s t e mp e r f o r m a n c er e q u i r e m e n t s c o n t i n u et oi n c r e a s e s e x p o n e n t i a l l yb y b r o a d b a n dt e c h n i q u e a l t h o u g hm o o r el a wi st h es a m ew i t ht h ef a s t e s td s pd e v i c e a tp r e s e n t b u tt h ea d v a n c e m e n ti np e r f o r m a n c ef o rd s pd e v i c e si s l a g g i n gb e h i n d t h ep e r f o r m a n c er e q u i r e m e n t sg r o w t h s o ，i tm u s tt of i n dan e ws 0 1 i o no fd a t a p r o c e s s i n g t om e e tt h ec h a l l e n g eo fb r o a d b a n dt e c h n i q u e a tt h es i t u a t i o n o f h i g h d a t a - r a t e ，h i g h - p a r a l m ，s i m p l ea l g o r i t h m ，l e s ss t a t e s ， s i m p l ed a t af l o wa n d c r i t i c a ld e l a y ，t h ef p g ac a no f f e ra v e r yg o o d s o l u t i o n t h i sp a p e rh a sa c h i e v e dt h ed e s i g no f a d a p t i v ef i l t e ro n t h ep l a t f o r mo f f p g a ， i t sa l lb a s e d0 1 3 t h er e s e a r c ht ot h ea l g o r i t h mo fh a r d w a r ee f f e c t i v et h ew o r k m a i n l ya sf o l l o w ： ( 1 ) u s e d i f f e r e n tm e t h o dt oi m p l e m e n tm a n yk i n d so f m u l t i p l i c a t i o ni nf p g a ， a n dl i s tt h e i ra d v a n t a g e s ，d i s a d v a n t a g e sa n ds u i t a b l es i t u a t i o n u p o nt h e s e ， a d v a n c e ss o m eo p t i m i z e dm o d i f i c a t i o n ( 2 ) r e s e a r c h e st h ed a m o r ed e e p l y h a st h ed e s c r i p t i o no fd ai nt h es t y l eo f h a r d w a r e a d v a n c e st h e o p t i m i z e d s o l u t i o n so fu l t i m a t ei n s p e e d a n d u l t i m a t ei ng a t ee f f i c i e n c y , a n di m p l e m e n t st h e mi nf p g a ( 3 ) r e s e a r c h e st h ec o r d i ca l g o r i t h ma n di t st w ow o r km o d e sd e e p l ya n di n s y s t e m ，i m p l e m e n t si t e r a t e d ( g a t ee f f i c i e n t l y ) c o r d i cp r o c e s s o r a n d o n l i n e ( h i g hp e r f o r m a n c e ) c o r d i cp r o c e s s o ea d v a n c e sam o d i f i c a t i o n m e t h o dt oc o r d i c g a i n ( 4 ) r e s e a r c h e st h ed i g i t a la d a p t i v ef i l t e r s i n s y s t e m ，c o n c l u d e dt h ec o m m o n c o n s t r u c t i o no fv a r i a b l e a d a p t i v e a r i t h m e t i ca c h i e v e dt h e d e s i g n o f a d a p t i v ef i l t e r ( b a s i cm o d e l ) b y h a r d w a r ed e s c r i p t i o n k e y w o r d s ：v l s i ，f p g a ，d a ，c o r d i c ，a d a p t i v ef i l t e r 致谢 首先，作者要感谢导师殷福亮教授，本文的研究工作是在导师的悉心指导 下完成的。殷老师严谨的治学态度、渊博的专业知识、求实的科研作风都给作 者以很大的影响。导师的谆谆教诲将使作者受益终生，并将指导作者今后的工 作和学习。 作者还要感谢信号处理教研室的马晓红老师、陈拮老师、孔祥维老师、李 建华老师和郭成安老师，在这些老师的教导下，作者学到了信号处理领域的专 、l k 知识。 作者还要感谢本科时的所有授课教师及硕士阶段的公共课教师，是他们为 作者在专业领域的研究打下了坚实的基础。 作者还要感谢本科时曾为作者提供过宝贵的学习和实验环境的毛德祥指导 老师，他指导作者的学习，关心作者的生活，使作者的理论和实际动手能力都 有了很大的提高。 马晓红老师、陈拮老师、师弟魏建强、师妹朱健华和作者曾一起参与实际 项目的研究开发，并绘予作者许多的帮助。在此一并致以深深的谢意。陈拮老 师刻苦钻研的精神、实事求是的作风将成为作者今后工作和学习的楷模。 在硕士阶段的学习和生活中，研究生周浩阳、刘雨、杨永胜、罗荣阁等同 学为作者创造了良好的学习和生活环境，并给予作者许多的帮助，在此特向他 们表示感谢。 自适应滤波器的v l s i 实现 第一章前言 1 1 d s p 器件的发展 第一章前言 2 0 世纪6 0 年代和7 0 年代，数字信号处理理论迅猛发展，理论体系和框 架逐渐趋于成熟。典型的代表作是美国a v o p p e n h e i m 的( d i g i t a ls i g n a l p r o c e s s i n g ) ) 。但由于当时受器件水平的限制，信号处理算法仅能在通用计算 机上进行模拟和仿真，难以达到实时处理。这样。尽管数字信号处理应用范 围很广，但在实际中应用的却很少。 8 0 年代，随着微电子技术的发展而出现了d s p 器件。这些器件的出现使 得数字信号处理算法得以实时实现。通用d s p 器件是专为数字信号处理而设 计的。它的m a c ( 乘累加) 单元能够在一个机器周期内完成一次乘累加运算， 并具备独特的循环寻址和倒序寻址能力。这些特点都非常适合数字信号处理 中的滤波器设计、卷积以及正交变换等的有效实现。最典型的d s p 器件是美 国t i 公司的t m $ 3 2 0 c 2 x 产品。 然而d s p 器件的哈佛结构本质上还是串行的，这使得它必须顺序执行某 个功能模块。只有在数据缺乏关联特性时，才具备一定的并行执行能力，因 此性能受到一定限制。传统d s p 器件中的m a c 单元通常是被共享使用的( 数 量一般只有1 个) ，因此d s p 器件的并行处理能力和数据吞吐能力是比较弱的。 为满足更高性能的特殊用途需要，a s i c ( 专用集成电路) 技术应运而生。 近年来，a s i c 技术的发展取得了长足进步。可是a s i c 的开发周期比较长， 而且成型以后无法再行更改，这无形中也增加了系统开发成本。 f p g a ( 现场可编程门阵y u ) 像a s i c 一样拥有高并行处理能力的优势，而 且其产品化后的设计可根据实际情况进行修改( a s i c 则不具备这种特性) 。另 外f p g a 无论是在节省线路板空间还是在节省系统功耗上，都可以通过优 化工具来提供最优化的设计方案，d s p 芯片则通常不具备这样的能力。 1 2 f p g a 的发展历史 自7 0 年代以来可编程逻辑器件，经历了p a l ( n - i 编程阵列逻辑) 、g a l ( 通 用阵列逻辑) 、c p l d ( 复杂可编程逻辑器件) 和f p g a 几个发展阶段。最初的 p a l 和g a l 芯片是由美国国家半导体公司在7 0 年代中期先后推出的，其结 自适应滤波器的v l s i 实现 第一章前言 构相对比较简单，片内资源也相当有限。 c p l d 是由p a l 或g a l 发展而来的，基本上是扩充原始的可编程逻辑器 件。它通常是由可编程逻辑的功能块围绕一个位于中心和固定延时的可编程 互联矩阵构成。 c p l d 又延伸出两大分支，即e p l d ( 可擦除、可编程的逻辑器件) 和 f p g a 。f p g a 器件通常是由布线资源围绕的可编程单元( 或宏单元) 构成阵列， 再由可编程i o 单元围绕阵列构成整个芯片。 f p g a 是由可编程掩膜门阵列和可编程逻辑器件演变而来的。这样，f p g a 既有门阵列的高逻辑密度和通用性，又有可编程逻辑器件的用户可编程特性。 c p l d 和f p g a 都属于高密度可编程逻辑器件，目前集成度已达8 0 0 万 门片以上。 1 3 数字信号处理的硬件实现算法发展 在过去将近2 0 多年的时间里，软件可编程的d s p 器件几乎统治了商用 可重构信号处理硬件的市场。然而在这些d s p 器件的发展和应用过程中，它 的某些弊端和不足之处也逐渐体现出来。最显著地，宽带革命将给d s p 器件 带来最大的挑战。宽带革命是由传统上分别属于不同领域的许多技术的融合 所引发的，其中包括计算、电信无线、视频、图像和网络等。宽度技术需要 处理的模拟和数字数据量呈指数型增长，这又进一步加大了对更快的d s p 器 件的需求。虽然摩尔定律仍适用于目前最快的d s p ，但在所需要的性能水平 与实际d s p 器件所提供性能水平问的差距仍在不断增大。因此，d s p 器件要 满足宽带技术所提出的挑战，必须寻求新的数据处理方法。 近1 0 年来，一个新的选择出现了：f p g a ( 现场可编程门阵列) ，它可被 用来构造可编程的高性能计算数据平台。过去人们总是认为f p g a 适合实现 逻辑密集型的功能，而缺乏完成计算密集型任务的能力。事实上，多年前人 们已经研究出了很多有效的硬件算法。充分地利用这些算法，使得f p g a 也 可以有效地实现许多线性时不变系统的信号处理算法，比如滤波器( f i r 和 i i r ) 、正交变换( 快速傅立叶变换f f t 、离散余弦变换d c t 、离散小波变换 d w t ) 、梳状滤波器( c o m bf i l t e r ) 、自适应滤波器( a d a p t i v ef i l t e r ) 等。由于 f p g a 的并行特性和许多硬件有效算法在其上的成功实现，商用数字信号处 理硬件领域市场的天平开始向f p g a 慢慢倾斜。 在f p g a 上构建d s p 系统时，设计能够从并行结构和数学算法中获得优 势，使得系统资源最小化，性能上超过通用d s p 芯片。利用分布式算法在 自适应滤波器的v l s i 实现第一章前言 f p g a 上实现阵列乘法，是增加数据带宽和吞吐能力的有效方法，也可以此 来提供非定制的d s p 解决方案。 在数据吞吐量大，并行度高，算法比较简单，状态较少，流程比较简单 和对时延要求较高的场合，应用f p g a 非常适合。 在最新的f p g a 器件中，已经内嵌了硬件乘法器阵列和内置的大容量随 机存储器( r a m ) 。这些增强结构使其在实现包含数学计算的算法时具有独特 的优势，例如，应用这些增强结构，实现一个2 5 6 阶f i r 滤波器，每个样本 可以在一个时钟周期内完成，这极大地改善了数字信号处理的性能和效率。 在传统d s p 芯片上，目前尚达不到这样的速度。 分布式计算技术( d i s t r i b u t e d a r i t h m e t i c t e c h n i q u e ) 分布式计算( d a ) 是专门针对乘累加运算的一种计算技术。1 9 7 4 年， a b r a h a mp e l e d 和b e d el i u 首先采用d a 算法设计了f i r 和i i r 数字滤波器 邮1 ，并将其成果发表在1 e e et r a n s a c t i o n sa s s p 上。此后，d a 技术得到越来 越广泛的应用。 d a 设计可实现门级高效率的位串行算法和高性能的位并行运算，它是经 典的串并综合方案。d a 技术可应用于很多重要的线性时不变数字信号处理 算法，如滤波器( f i r 和i i r ) 、快速傅立叶变换及矩阵向量乘积等。 尽管d a 技术不适用于可编程d s p 器件的定点指令集结构，但却适用于 f p g a 实现，尤其是在具备l u t ( 查找表) 逻辑模块结构的f p g a 器件中( 如 x i l i n x ) 。 坐标旋转数字计算( c o o r d i n a t er o t a t i o nd i g i t a lc o m p u t e r ) 坐标旋转数字计算( c o r d i c ) 是jd v o i d e r 于1 9 5 9 年提出的】，它是一 种能有效计算超越函数的迭代算术算法，常用于三角函数、双曲函数、指数 和对数的运算。该算法使得矢量的旋转和矢量化运算不需要三角函数表、乘 法、开方和反三角函数等复杂的运算，从广义上讲它提供了一种数值计算的 逼近方法。自该算法提出后，人们就对它不断的进行改进和完善。1 9 7 1 年， j s w a l t e r 提出统一的c o r d i c 算法【l ”，使它展示出更为广泛的应用前景。尤 其是近几年，在f p g a 上通过移位、相加计算实现平面内的矢量旋转，从而 使c o r d i c 算法走向实用。c o r d i c 旋转体使用一系列特殊的固定旋转角度 完成一次矢量旋转，每一步的旋转都是由移位和相加操作完成的。应用 c o r d i c 算法，使得f p g a 可以完成一些更加复杂的工作，比如d c t 、d w t 变换等。 自适应滤波器的v l s i 实现 第一章前言 1 4 硬件描述语言 硬件描述语言( h d l - - h a r d w a r ed e s c r 证) t i o nl a n g u a g e ) 是一种用于设计硬 件电子系统的计算机语言，它用软件编程的方式来描述电子系统的逻辑功能、 电路结构和连接形式。与传统的门级描述方式相比，它更适合大规模系统的 设计。例如一个3 2 位的加法器，利用图形输入软件需要输入5 0 0 至1 0 0 0 个 门，而利用v h d l 语言只需要书写一行a = b + c 即可。v h d l 语言可读性强， 易于修改和发现错误。早期的硬件描述语言，如( a b e l h d l 和a h d l ) ，由 不周的e d a 厂商开发，互不兼容，而且不支持多层次设计，层次间翻译工作 要由人工完成。为了克服以上不足，1 9 8 5 年美国国防部正式推出了v h d l ( v e r y h i g hs p e e d i ch a r d w a r e d e s c r i p t i o nl a n g u a g e ) 语言，1 9 8 7 年i e e e 采纳v h d l 为硬件描述语言标准( i e e es t d 一1 0 7 6 ) 。 v h d l 是一种全方位的硬件描述语言，包括系统行为级、寄存器传输级 和逻辑门级多个设计层次。它支持结构、数据流、行为三种描述形式的混合 描述，因此v h d l 几乎覆盖了以往各种硬件描述语言的功能。通常整个自顶 向下或自底向上的电路设计过程都可以用v h d l 来完成。v h d l 还具有以下 优点： ( 1 1v h d l 的宽范围描述能力，使它成为高层次设计的核心，这样可使设 计人员的工作重点主要放在系统功能的实现与调试，而花较少的精力 用于物理实现。 f 2 1v h d l 可以用简洁明确的代码描述来进行复杂控制逻辑的设计。这样 既灵活、方便，又便于设计结果的交流、保存和重用。 ( 3 1v h d l 的设计不依赖于特定的器件，从而方便了工艺的转换。 f 4 ) v h d l 是一种标准语言，为众多的e d a 厂商支持，因此移植性好。 1 5 本文的主要工作 本文主要工作如下： ( 1 ) 使用不同方法，在f p g a 上实现了多种乘法器结构的硬件描述，并给 出了这些方法的优缺点和适用范围。在此基础之上，提出一些优化、 改进措施。 ( 2 ) 对d a 算法进行了较为深入的研究。在阐述算法原理基础上，用硬件 自适应滤波器的v l s i 实现第一章前言 形式对d a 算法进行描述。针对以性能为最终目标和以系统资源利用 率为最终目标这两种情况，提出相应的优化方案，并给出了这些优化 方案的硬件描述。 ( 3 ) 对c o r d i c 算法以及两种工作模式，进行了较为深入和系统的研究。 基于f p g a ，实现了高资源利用率的迭代结构c o r d i c 处理器和高性 能的在线式c o r d i c 处理器。对于c o r d i c 旋转带来的增益问题， 提出了自己的改进方法。 ( 4 ) 对自适应数字滤波器进行了较为系统的研究，归纳了各类自适应算法 在具体实现过程中的共同点。在此基础上，完成了自适应滤波器f 基 本模型) 的设计，并给出了该设计的硬件描述。 自适应滤波器的v l s i 实现第二章乘法器的实现及优化 第二章乘法器的实现及优化 从运算量的角度考虑，各种数字信号处理算法的核心往往会归结到乘累 加运算上。用硬件的方法来实现数字信号处理算法，乘法器设计的优劣将直 接影响整个设计的效率和性能。 乘法器的本质是基本的移位加操作，但是实现方法多种多样，其中有一 些是比较适合在f p g a 上通过硬件来实现的。本文对这些实现乘法器的方法 进行了分析和优化实现。 2 1 修正累加乘法器 修正累加乘法器使用一个递归的移位加操作来实现乘法。本乘法器中一 个输入是通过位并行方式给出，另外一个输入通过位串行方式给出。串行输 入的每一位( 0 或1 ) 都和并行输入项相乘。当串行输入项逐位输入时，并行输 入项是作为常数项保持。值得注意的是每次比特乘法是根据比特位f 1 或o ) 将 并行输入项不加改变或者替换为0 后输出。每个比特乘积项都将参加求和运 算。在下一个比特乘积项到来之前，累加器的输入左移一位后，再参加求和 运算。 这种方法的特点是： ( 1 ) 串行算法实现并行； ( 2 ) 递归移位加程序； ( 3 ) n 个时钟周期完成计算； ( 4 ) 非常小型的设计： ( 5 ) 根据累加器的移位方向确定串行输入是m s b 或l s b 在先 ( 6 ) 并行输出。 图2 - 1 修正累加乘法器原理示意 竹。 毗如叽。一 吡一 。儿u一如。署 1 0 l 1 自适应滤波器的v l s i 实现 第二章乘法器的实现及优化 2 2 串并混合乘法器 由于除了串行输入路径在器件物理布线时是广播模式，别的所有路径都 是最近邻布线，因此简单的串并混合乘法器，特别适合在不带快速进位逻辑 的f p g a 芯片上，实现串行比特处理机。串行输入必须进行符号位扩展，扩 展宽度到串行输入和并行输入的宽度和，以防止溢出。这就意味着此类乘法 器要比修正累加乘法器花费更多的时钟周期。下面这种结构在早期的t 1 l 串 并混合乘法器中被广泛使用。 这种方法的特点是： ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) 省略了进位链的比特串行加法器： 非常适用于不带快速进位逻辑的f p g a 芯片 最低有效位在先串行输入； 串行输出； 除了串行输入路径是广播模式，别的路径都是最近邻 延迟时间为1 比特时间。 并行犄 n 一1) ( 。一21o 比特串行加j 去嚣 图2 2 串并混合乘法器逻辑示意 2 3 波纹进位阵列乘法器 波纹进位阵列乘法器( 也称为行波纹结构) 是一个典型的移位加乘法算法 在展开后的化身。图( 2 3 ) 显示了用来综合4 4 乘法器阵列所有比特乘积项的 加法器结构。比特乘积项是布尔值，乘积的输入来自乘法器输入的各比特位。 比特乘积的输入项用x , y 的形式在下图中表示。最大的延迟是从任意一个输 入项的最低有效位到乘积项的最高有效位的路径( 不考虑路径选择延迟和路 径延迟) 。延迟大致是2 * n 。 这种方法的特点是： 自适应滤波器的v l s i 实现第二章乘法器的实现及优化 ( 1 ) 行波纹结构； ( 2 ) 展开的移位加算法 ( 3 ) 延迟和n 成比例。 图2 3 波纹进位阵列乘法器逻辑结构 p il ，0 这种基本结构非常易于在f p g a 上实现。但是，在大部分的f p g a 上都 不能很有效的利用逻辑资源，因此这种实现方法相对别的方法更占用资源， 速度也更慢。 2 4 行加法树乘法器 行加法树乘法器重新排列了行波纹乘法器的加法器，使得加法器的数目 和为产生部分乘积项结果所必须通过的加法器个数相同。使用相同数目的加 法器，在最坏情况下从输入到输出的数据路径是遍历1 0 0 2 ( n ) 个加法器而不 是n 个加法器。此类乘法器如果经过严格的逻辑组合，会减少延迟。如果是 采用管道技术，则可以减少时钟周期。路径选择的树形结构意味着某些单条 连线会比行波纹结构要长。这样，采用管道技术的行波纹乘法器可以在 v e g a ( 更短的时钟周期) 上具备更高的吞吐能力，但等待时间会延长。 这神方法的特点是： ( 1 ) 优化的行波纹结构； ( 2 ) 和行波纹结构的门数目基本相同： ( 3 ) 树形排列的行加法器可以减少时延 自适应滤波器的v l s i 实现第= 章乘法器的实现及优化 ( 4 ) 路径选择更加困难，但在大多数f p g a 上是可行的 ( 5 ) 延迟和i 0 9 2 ( n ) 成比例。 图2 - 4 行加法树乘法器逻辑 2 5 进位保存阵列乘法器 进位保存阵列乘法器，其结构同波纹进位阵列乘法器( 行波纹结构乘法器) 是类似的，也被称为列波纹结构乘法器。 这种方法的特点是： ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) 列波纹结构； 与行波纹结构的时延和门数目基本相同 针对a s i c 电路，门级速度可以提升； 波纹加法器可以被速度更快的进位树加法器代替 常规的路径选择模式。 图2 - 5 进位保存阵列乘法器逻辑 自适应滤波器的v l s i 实现 第= 章乘法嚣的实现及优化 2 6 查找表乘法器 查找表乘法器其实就是一大块存储器，它保存着完整的所有可能乘法输 入的组合。这样，即使普通的乘法输入宽度，也会需要庞大的查找表，这对 于f p g a 来讲是不切实际的。 这种方法的特点是： ( 1 ) 所有可能输入的组合形成完整的查找表； ( 2 ) 每一个查表地址的比特位对应每个输入数据的比特位 ( 3 ) 表的体积按指数规律增大： ( 4 ) 非常有限的应用； ( 5 ) 快速仅仅是存储器的存取方式； 表2 - i 3 * 3 乘法的6 输入查找表所包含的内容 0 0 00 0 1 0 1 00 1 11 0 0 1 0 11 1 01 1 1 0 0 00 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 00 0 0 0 0 1 0 0 0 0 1 00 0 0 0 1 10 0 0 1 0 0 0 0 0 1 0 10 0 0 1 1 00 0 0 1 1 1 0 1 00 0 0 0 0 00 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 00 0 1 1 1 0 0 1 10 0 0 0 0 00 0 0 0 1 1 0 0 0 1 1 00 0 1 0 0 10 0 1 1 0 00 0 1 1 1 1 0 1 0 0 1 00 1 0 1 0 1 1 0 00 0 0 0 0 00 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 00 1 0 1 0 00 1 1 0 0 00 1 1 1 0 0 1 0 10 0 0 0 0 00 0 0 1 0 1 0 0 1 0 1 00 0 1 1 1 10 1 0 1 0 0 0 1 1 0 0 10 1 1 1 1 01 0 0 0 1 1 1 1 00 0 0 0 0 00 0 0 1 1 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 1 1 01 0 0 1 0 01 0 1 0 1 0 1 1 10 0 0 0 0 00 0 0 1 1 1 0 0 1 1 1 00 1 0 1 0 10 1 1 1 0 0 1 0 0 0 1 11 0 1 0 1 01 1 0 0 0 1 2 7 部分乘积项查找表乘法器 部分乘积项查找表乘法器，使用了部分乘积项的技术，这种技术和常用 的普通手写乘法非常类似，由此延伸了查找表乘法的有效性。 设想下面的手写乘法： 6 76 76 76 7 x5 4 x 5 4 x5 4 生丝 2 82 82 8 2 8 。一2 4 0 _ 渺2 4 0 静2 4 0 3 5 03 5 0 。t+ 3 0 0 0 一 ： 3 6 1 8 自适应滤波器的v l s i 实现第二章乘法器的实现及优化 该方法次完成一个数字的乘法，然后移位并累加单独的部分乘积项， 因此保存查找表的存储器体积能极大的减小。虽然这个例子是十进制的，但 这种技术对任何进制都有效。部分乘积项的产生顺序以及这些乘积项的累加 顺序都不重要，无论以何种顺序来处理，都必须提供固定的移位操作。 接下去的例子说明了这种技术是如何应用在硬件上的。剥用上面提到的 3 x 3 乘法的6 输入l u t ，可以进行6 x 6 的乘法运算。如图( 2 - 6 ) 所示，4 个同 样的6 输入l u t ( 完成一对8 进制数的乘法) ，并行响应查表请求，因此所有 的部分乘积项是同时获得的。各个部分乘积项被移位修正以后，一起参加累 加运算。一个加法树被用来以最小的时延获得累加和。 a ( 2 ：0 】 1 3 1 2 ：0 】 a 1 2 ：0 b 5 ：3 1 a 5 ：3 1 b 1 2 ：o j a 【53j b 1 5 ：3 】 图2 - 6 部分乘积项查找表乘法器逻辑( 6 x 6 ) 当l u t 被作为乘法器使用时，它可以被任何别的乘法器应用所代替。这 种方法使我们能够了解，如何使用l u t 去组合并实现一个较大的乘法器。 l u t 乘法器的表示是和根基数相匹配的( 本例中，输入项都是八进制的) 。 部分乘积项也允许在输入端有混合根基数，不过需要注意，部分乘积项在参 加累加运算前须进行正确的移位操作。如果部分乘积项是由小型l u t 提供的， 那么当l u t 相互一致( 也就是所有输入的基数相吻合) 时，实现的性能是最有 效的。在a l t e r a1 0 kf p g a 中就有8 比特的l u t ，这就意味着这个l u t 的基 数是十六进制的。在大部分的f p g a 逻辑单元中，都可以找到4 比特的l u t 。 最理想的根基数是2 比特( 这是4 查找表真正的唯一选择：一个l 比特输入使 l u t 简化为一个与门，每个l u t 单元有一个输出，在另外的输入端仅能使用 l 比特) 。 通过串行的使用同一个l u t ，并且通过一个修正累加器将所有部分乘积 项移位累加，则可以实现一个尺寸更加紧凑但是速度更慢的版本。在这种情 况下需要注意一件事情，就是移位寄存器必须有一个专门的控制，以便为所 有的部分乘积项提供正确的移位操作。 这种方法的特点是： 自适应滤波器的v l s i 实现第二章乘法器的实现及优化 ( 1 ) 像普通的手写乘法方式来工作： ( 2 ) l u t 用于获得阿拉伯数字的乘积 ( 3 ) 部分乘积项用加法树组合起来。 2 8 部分乘积项计算乘法器 由4 查找表结构构造而来的部分乘积项乘法器，在大多数的f p g a 上不 是非常有效，这是因为有大量的部分乘积项需要进行求和运算( 同时也需要有 大量的查找表) 。我们把其中一个输入项为2 比特的乘法器，看成为一个根据 此输入项来产生另一输入项的0 、1 、2 或者3 倍输出的乘法器，以此来构造 一个更加有效的乘法器。仅需使用一个加法器和移位寄存器，就可以很容易 的在一步内产生所有这4 个乘积项。如图( 2 7 ) 所示，一个由2 比特乘法器输 入项来控制的多路选择器用来选择合适的乘积项输出。与查找表的解决方案 不同，这种方法对于乘法器的a 输入项字长没有限制。同样的规模，采用这 种结构设计的乘法器，相对于部分乘积项查找表乘法器，可以很大程度上地 缩减部分乘积项的数量和加法树的深度。因为所有a 输入项的0 、1 、2 和3 倍值输入到多路选择器都是相同的，因此一个加法器可以被所有部分乘积项 生成器共享使用。这种结构可以很好的工作于粗粒度( c o a r s e r g r a i n e d ) 类型的 f p g a ，比如x i l i n x 的x c 4 0 0 0 系列。 图2 7 采用加法器和多路选择器来产生2xnb i t 的部分乘积项 这种方法的特点是： ( 1 ) 为f p g a 作了优化的部分乘积项可以有更小的l u t ； ( 2 ) 更少的部分乘积项，减少了加法树的深度： ( 3 ) 通过逻辑而不是通过l u t 来产生2 xn 比特的部分乘积项 ( 4 ) 比4 查找表部分乘积项乘法器尺寸更小、速度更快。 在x i l i n x 的v i r t e x 器件中，进位链逻辑包含一个“扩展门”，它允许使 用一个4 输入的查找表加上进位链来实现一个2 ) ( n 的部分乘积项，因此可以 自适应滤波器的v l s i 实现第二章乘法器的实现及优化 获得2 倍密度。在这种情况下，加法器( 由进位链中的异或门和多路选择器组 成) 将一对q x n 的部分乘积项相加来实现“与门”。进位逻辑中的扩展“与门” 允许将与门同时置于加法器的两个输入上，以提供4 输入功能。 图2 - 8 使用x i l i n xv i r t e x 器件进位链逻辑中的 特殊多与门来产生2xnb i t 的部分乘积项 自适应滤波器的v l s ! 实现第三章d a 算法的硬件实现止优化 第三章d a 算法的硬件实现及优化 3 1d a 算法概述 线性时不变系统的输出可表示为 f y ( 月) = d k x 。( n ) 1 = 1 ( 3 1 ) 这里y ( n ) 是在时间九时的系统输出，x k ( n ) 是第k 个输入数据彳i 是针对 第k 个输入数据的加权系数。 在滤波器应用中，式( 3 1 ) 内的常数爿是滤波器的系数，变量x k 是单一 数据源中得到的采样数据。在频域变换中，无论是d f t 还是f f t ，式( 3 1 ) 内 的常数彳 是基本的正弦余弦函数，变量瓢是单一数据源的采样数据。显 然，系统输出需要k 次乘积项的累加。 定义变量的数据格式为2 的补码及小数形式，这在定点微处理器中为防 止进行乘法运算时数据长度溢出而使用的标准惯例。常系数爿t 可以有整数， 也可以有小数形式。变量靴可以写成小数形式如下 f 3 - 2 ) 这晕x 是二值变量，其值只可能是“l ”或者0 。符号位的值由。枷来单 独表示的。将式( 3 2 ) 代入( 3 1 ) 可得 将上式展开，则有 kk # 一l f , d k x k 。十x k ，, a k 2 “ ( 33 ) = i= i = l l i 1j 2 嘞 + 。l 一 。h = y 自适m 滤波器的v l s l 实现第三章d a 算法的硬件实现及优化 y = 一k o a i + x 2 0 一2 + + x k o a k + k 1 1 a i + x 2 l a 2 + + 1 4 】2 “ + k 2 爿l + z 2 2 a 2 + - - - + x 女2 4 】2 2 + k l ( ) a l + x 2 ) a 2 + + x k ( b - 2 ) 副2 一“2 + b 。 。一。) 4 。+ 而( 。) a ：+ + 坼( 。一) a k 2 。8 1 ( 3 4 ) 在中括号内的每一项均是二进制的多个与操作，包括了所有的输入变量 比特位和所有的常量比特位。中括号内的加法符号表示算术和操作。指数部 分的系数表示中括号内的和，被修正以后参加累加运算。现在我们可以产生 一张查找表，以输入变量为地址对l u t ( 查找表) 进行寻址操作，得出每一对 括号内的各项之和。图( 3 1 ) 显示了这样的l u t ，并且今后作为d a 算法的查 找表d a l u t 来引用。同一个d a l u t 可以被串行组织的计算分时复用，或 者被复制b 份在并行运算模式下( 这在接下去的描述中会具体展开) 。 d a l u t 的寻址 a 0 a l a 2 a k k 2 丰空间( 字长为a ) d a l u i - 的内容 地址 x o d 为最旺有效位 k 可以是双极牲帕 图3 - 1 d a 算法查找表 在d a 算法中，数学运算被简化成了加法、减法和二进制成比例的缩放。 - 1 5 m 肿一 舳 帅 自适应滤波器的v l s i 实现第三章d a 算法的硬件实现及优化 以2 的负幂次进行修正，实际应用的时候需要进行二进制的移位操作，移位 方向为最低有效位的方向，并且需要进行符号位扩展，以保持数据的正负特 性。二进制全加器的硬件实现在c l b ( 可配置逻辑模块) 中已经完成，全加器 需要2 个操作数加数和被加数，并产生和与进位输出。公式3 4 中表达的 d a l u t 的多个位并行加法输出可以由一个并行加法器来完成( 如果这个加法 器是时分复用的话) 。另外，如果所有d a l u t 的输出必须同时参加加法运算， 则会需要一个并行加法阵列。 3 2 以速度为最终目标的d a 算法 使用完全的并行设计将使数据采样速度达到系统时钟频率。这种情况下， 式( 3 4 ) 中，所有中括号内的值( d a l u t 的输出) 的累加操作，都是以并行方式 来完成的。为了容易阐述这个过程，我们将式( 3 4 ) 中括号内的内容用更简易 的符号来代替，即k ：a + x ：a ：十十扎：a 。 缩写为s u m 2 】，同样的， ( ) a 1 + x 2 ( ) a 2 + + h ( ) a j 缩写为 s u m ( b 一1 ) 。例如b = 1 6 ，则式( 3 4 ) 变成 y = 一s u m 0 + s u m l 2 1 + s u m 2 2 2 + s u m l 4 2 一。4 + s u m l 5 1 2 一5 ( 3 5 ) 将式( 3 ，5 ) 分解成2 输入加法器的阵列后，则有 y = 一 s u m o + s u m l 2 1 + s u m 2 + s u m 3 2 1 2 2 ( 3 6 ) + b “肌4 】+ b “m 5 1 2 。+ b “m 6 卜b “m 7 2 。1 2 2 2 。 f s u m s + s u m 9 2 1 + s u m t o + s u m i1 p 一1 2 2 j1 。一。 。h 妇m 1 2 + s u m l 3 2 “+ b m l 4 + b m l 5 1 2 - t 2 。 2 “j 自适应滤波器的v l s i 实现 第三章d a 算法的硬件宴现及优化 式( 3 5 ) 和式( 3 6 ) 在计算上是等价的，但是式( 3 6 ) 可以直接映射成一个二进 制树型的带进位功能的加法节点阵列，见图( 3 2 ) 。1 5 个节点中的每一个都代 表一个并行加法器。计算中可以包括双精度( b + c 比特) 乘法结果和附加的增 益处理后得到的系统输出。 x o o 图3 2 全并行的d a 模型( k = 1 6 ，b = 1 6 ) 例子 所有k 个数据的所有b 比特需要能对b 个d a l u t 进行寻址。这就需要 一个b k 的寄存器阵列，每个b 都对应d a l u t 提供的字长为c 的2 个字 节，c 的值是对应的系数累加和。从寄存器阵列之后的数据流可以被逻辑组 合。对于b = 1 6 的情况，严格的延迟会经过5 个c l b 和2 c 个进位链。如时 钟频率在1 0 0 m h z 范围内，系统将能正常工作，这里的延迟是可接受的。 3 3 以资源利用率为最终目标的d a 算法 若以资源利用率为最终目标来实现d a 算法，会用到一个单独的d a l u t 、 自适应滤波器的v l s i 实现第三章d a 算法的硬件实现及优化 一个并行加法器和更少的寄存器( 用来接收输入数据) 。以变量字长b = 1 6 为例 式( 3 4 ) 改写为 “ s u m l 5 1 2 “+ s u m l 4 2 。1 + s u m l 3 2 1 + s u m l 2 2 。( 3 7 ) + s u m ll 】 2 1 + s u m l 0 2 一+ s u m 9 2 1 + s u m s 2 1 + s u m 7 2 一 + s u m 6 2 1 + s u m 5 2 1 + s u m 4 2 1 + s u m 3 2