（微电子学与固体电子学专业论文）dsp算法不同平台上的实现、性能研究与优化.pdf

中文摘要 摘要：速度与功耗是数字处理技术中关键的两个因素。因为需要处理与传输的信 息量激增，所以速度尤为重要。同时，能源的短缺、便携产品以及特殊应用领域 对信息处理设备的要求，促使人们开始重视数字处理系统的功耗问题。由于数字 信息处理都是通过算法来实现，因此，研究如何从速度与功耗这两个方面优化数 字信号处理算法的实现系统是非常重要的。 从算法到实现的映射包含两个层次：较高的控制流与数据流层次即算法层，与 较低的实现层次，每个层次的映射对算法最终实现的性能都有着极大的影响。此 外，每个数字信号处理算法的数据流与控制机制有着很大不同，导致实现结构的 不同。因而，本论文从优化速度与功耗的角度出发，研究不同平台实现算法时不 同的性能优化方法，针对三个不同的数字信号处理算法，在不同的平台上完成它 们的实现，并作速度与功耗的比较。 本论文研究并实现的三个d s p 算法是：f f t 、f 取、v i t e r b i 解码的实现，这三 个算法在数字领域如无线通信、音频视频处理、互联网等领域应用得非常普遍。 论文利用软件、f p g a 和a s i c 三种不同的平台技术，分别实现了这三种算法，并 对实现结果的技术性能进行了分析研究。在此基础上，对一种新的针对速度和功 耗优化的平台d 砌认( d y n 锄i c a l i yr e c o n f i g u f a b l cr e s o u r c e sa 册y ，由k m 开发) 进行了前沿性应用研究，并对d s p 算法在d 认上的实现做出了总结。此外，论 文还研究了f p g a 的功耗测试方法，构建了两种f p g a 功耗测试平台，并从数学 理论上对两种平台的测试结果和测量误差进行了推导。 关键词：d s p 算法；软件；f p g a ；a s i c ；d r r a ；算法实现；速度功耗优化 分类号：t n 4 3 1 2 a bs t r a c t a b s t r a c t s p e e d 锄dp o w e ra r et w oc m c i a l 雒p e c t sf o rd i g i t a ip r o c e s s i n g ，b e c a l l s e m e 锄o l i n to fi n f 0 册a t i o nn e e d e dt 0b e 她l s f l 0 册e d 锄dp m c e s s e di s 伊o w i n gf 瓠t ，锄d a tt h es 锄et i m ep o w e rc o n s 岫p t i o ni sd r a w i n gm o r ea t t e n t i o nw i m 廿l e 粤0 w 山o f d e v i c ed e n s i 够a sar e s u l t ，d i 百t a ls i 印a lp r o c e s s i n g( d s p ) a l g o r i 岫n s 锄dt l l e i r i m p l e m e n t a t i o na r ew o r 血s t u d y i n g 锄d 叩t i m i z i l l g ，i no r d e rt 0m a k e 吐l e mm o r c e f n c i e n t 锄da t t r a c t i v e r h e 的n s f 0 加打o m 缸a l g o r i m mt 00 p e r a t i o nc o 璐i s t so f 铆oi e v e l s ：廿l eh i 曲e r c o n 缸d l 锄dd a t an o wl e v e l 、7 l ，h i c hc 趾b ec o n s i d e r e d 勰t l l ea l g o t l l ml e v e l 锄dt 1 1 el o w e r 妇p l e m 伽o nl e v e l b o t l lo fm et 、ol e v e l sc 锄i i l f l u 锄c et 1 1 ep e r f 0 m 蛆c eo f 觚 a l g o r i 岫b e s i d e s ，m ed a t an o w 觚dc o n t r o lm e c h 锄i s mo fo n ed s pa l g o r i t l l mm a yb e t o t a l l yd i 仃e r e n tf r o mn l o s eo f 锄o m e r l e a d i n gt 0n l es 仉l c t u 他o f 也e i ri m p l e m 曲t a t i o 璐 a r ef 打d i 行c r e n t 舶me a c ho m e r f o rt 1 1 ep u 印o s eo f s p e e d 锄dp o w e r 叩t i m i z a t i o n ，廿l i s 廿1 e s i sw o r k so nd i f j f e r e n to p t i m i z a t i o nm e t l l o d sf o rd i h e r e n tp l a t f 0 咖i l l l p l e m c n t a t i o n ， 雒w e l l 勰t l l ei m p l e m e n t a t i o no fn l r e ed s p a l g o r i t h m s 觚dn l e i rc o m p 枷s o no fs p e e d a n dp o w e r t h e t ) ，p i c a ld s pa 1 9 0 甜i m s f f t ，f m 勰dv i t 拍id e c o d i n gw h i c ha r cv 吖 c o m m o n l y 璐e di np r a c t i c a l l ya p p l i c a t i o 璐s u c h 觞w i r e l e s sc 0 舢叭m i c a t i o n ，肌d i o & v i d e os y s t e m s ，i n t e m c t 趾ds oo n ，眦s t u d i e di nt 1 1 i sm e s i s t h et h r c ea l g o r i t l l i n sa r c m a p p e dt 0t h r e ec o m m o np l a t f 0 r n l s s o 胁a r e ，f p g a 觚da s i c ，r e s p e c t i v e l y b 雒e d t 1 1 ea b o v ew o r k ，an o v e lp l a 怕册c a j l e dd r r a ( d ) n 锄i c a l l yr e c o n f j 毋珊b l e r e s o u r c e s 岫)弧p l o i t e di nk t h i sd e 印i ys t u d i e d i i la d d i t i o n ，s o m ec o n c l u s i o 璐o n d s pa l g o r i 廿l m si m p l e m e n t a t i o na r ed r a 、n 勰w e l l b e s i d e s ，廿l ef p g am e 邪1 l r e m t m e t l l o di s i n v e s t i g a t e di nt l l i s w o r k t w ok i n d so ft e s t b e n c ha r ed e s i 印e d ，锄dt 1 1 e m e 私u r e m e n tr e s u i t s 锄dt l l e i re r r 0 体盯ed e r i v e d 仔o mm a 也e m a t i c sr e s p e c t i v e l y k e y w o r d s ：d s pa l g o r i t l l m s ； s o r w a 托；f p g a ；a s i c ；d r r a ； a l g o r i t h m i m p l e m e n t a t i o n ；s p e e 彬p o w c r0 p t i m i z a t i o n c l 。a s s n o ：r n 4 3 】2 致谢 本论文的工作是在我的导师李哲英教授和s u p e r v i s o r 李硕的悉心指导下完成 的，他们对于我的论文的完成给予了很大的帮助，并提出了许多的宝贵意见，在 此表示衷心的感谢! 李哲英教授悉心指导我完成了实验室的科研工作，在学习和生活上都给予了 我很大的关心和帮助，他严谨的治学态度和科学的工作方法给了我极大的影响。 在此衷心感谢两年半来李老师对我的关心和指导。 再次感谢李老师为我提供了去瑞典皇家工学院( k t h ) 完成论文的机会! 在实验室工作及撰写论文期间，束晨同学、李宁师兄、刘佳师姐、周旋同学、 卫光辉同学、杨雅雯同学等对我论文中的研究工作给予了热情帮助，在此向他们 表达我的感激之情。 另外也感谢我的家人，。他们的理解和支持使我能够在学校专心完成我的学业。 1 引言 1 1 课题研究背景与现状 近年来，数字技术一直迅猛发展，在信息处理中担任着越来越多的任务，引 领着当代信息技术的前进。每时每刻，海量的信息产生后被源源不断地转换成原 始数据，然后经过重要的数据处理步骤如信源编码、信道编码、帧封装等，在巨 大的数字网络中如因特网、移动通信网络被传输到世界各地，进入到人们的生活 与工作中。可以毫无争议地说，人们无不享受着数字技术创造的产物，如移动电 话、数字视频、因特网等等，人们的日常生活正在为数字所支配。数字技术的最 新成果改变了世界，创造了更美好的生活：高清电视，正在被越来越多的家庭与 电视台采用；在高质量图片、视频传输与通讯的要求下，第三代移动通信网络的 进步日新月异；数字基带通信、无线网络如蓝牙、超宽带通信系统的发展也令人 瞩目。 数字技术的发展产生巨大的待处理数据量，所以高速的数字处理技术越来越 具有吸引力。同时，能源的短缺促使人们更加重视数字系统的功耗，不断地追求 低功耗数字处理系统。因此，速度与功耗，是数字处理系统最关键的因素。另一 方面，数字技术的核心是各种协议与数字信号处理算法，这些算法的实现多种多 样，每种实现方法的速度与功耗都有着较大的差异。因此，如何从实现的角度优 化每种数字信号处理算法的速度与功耗，是一个非常值得研究的课题【l 】【2 】【3 】。 算法到实际功能单元的映射包含多个层次，其中的两个主要层次是：较高的 控制流与数据流层次与较低的实现层次。每个层次都需要认真地对待。较高层次 的优化主要由系统工程师完成，而较低层次则需要硬件与软件工程师的努力。算 法实现后的速度与功耗受到很多因素的影响，最重要的是设计技巧与实现平台。 因为每一种数字信号处理算法都具有独特的数据流与控制机制，所以它们彼此的 实现结构也有着根本性的差异，同时，不同平台的优化方案也存在很大差别。一 个统一的优化策略是不存在的。 1 2 论文目标 本文的目标是，从速度与功耗这两个最受关注的角度出发，研究了如何在不 同的实现平台上优化几种典型且重要的某种数字信号处理算法。这几种典型的算 法分别是f f t 、f 瓜和v i t e r b i 解码。这三个算法在数字系统，如无线通信、音频 处理、数据接口、数据通信网络中应用得极其普遍，所以针对如何优化这几种算 法实现的研究，对于提高大多数数字系统的性能与功耗，有着非常重要的意义 【4 】【5 】【6 】。其中，f f t 算法大大提高了离散f o u r i e r 变换d f t 的效率，使得离散信号 频谱分析具备了极大的工程应用价值，并被广泛得使用在音频与视频处理、移动 通信等系统中；f 瓜算法用于设计线性相位的有限脉冲响应( f 取) 滤波器，具 有线性的相位响应，解决了i r 滤波器相位响应失真导致非线性群延迟的问题，在 数字信号处理任务里占据着非常重要的地位，应用于需要滤波的数字系统中； t e r b i 解码算法则是一种高效率的卷积解码算法，具有误码率低，解码速度快等 优点，近年来被越来越多地使用于数字通信系统的信道编码与解码单元中来解决 传输误码的问题。图1 1 是一个典型的数字音频觎频通信系统，说明了这三种算 法在数字系统中的普遍性。 图像 视频 音频 制 输 调 图1 1一个典型的数字音频视频通信系统框图 f i 目旺e1 1 ：a 帅i c a la u d i o i d e oc o m m u n i c 撕o ns y s t c m 在这个系统中，自然界的模拟信号，如图像、声音、视频等，首先被采样转 换成原始数据，其中包含了大量的噪声，所以原始数据要经过数字滤波器以滤除 噪声；再经过压缩减少冗余数据量，以减轻数据传输与存储的压力；经过压缩后， 数据需要进行信源编码以产生冗余位用于纠错，在这个过程中，卷积编码因为其 较强的纠错能力而被广泛地应用；信源编码后的数据再经过帧封装，组合成一片 片连续的帧；这些帧数据经过信道编码后形成通信协议规定格式的码流，然后经 过调制，开始了传输与后续的接收、解码、恢复与播放与存储的过程。在整个数 字处理与通信系统中，f i r 算法被广泛应用于数字滤波器中；很多常用的图像或视 频数据压缩如j p e g 、h 2 6 4 ，也以f f t 算法为基础；同时，很多系统的信源编码 采用卷积编码，因此对应的接收端多采用v i t e r b i 译码算法。 这三种算法将被分别映射至四种不同的实现平台：软件、f p g a 、a s i c 与 d 认。在这四种平台中，前三种是最普遍的实现策略，d r r a 则是一种新颖的平 台，由瑞典k t h 开发，其结构针对多数d s p 算法进行了专门的设计，可以实现很 高的资源利用率的算法映射。 2 软件平台上的实现采用c 语言完成，f p g a 与a s i c 平台上的实现采用v e r i l o g h d l 完成。在这三种d s p 算法实现的设计中，为了更好地优化算法，针对不同的 平台，仔细研究了每种平台上的实现结构对算法速度与功耗的影响。在验证与测 试阶段，做出了详细的不同平台上各个算法实现速度与功耗的对比，根据对比结 果，仔细评价了不同平台实现d s p 算法的优劣。 1 3 论文结构 论文的组织结构如下： 第二章介绍了背景知识，包括论文实现的三种d s p 算法：f f t 、f m 和v i t e r b i 译码算法的概念，以及它们的基本数据流与处理机制。三种实现平台：软件( c 语言) 、f p g a 和a s i c 也在本章详细讨论。 第三章研究了三种d s p 算法在软件平台上的实现，着眼于如何控制软件实现 中的数据流，以优化算法的性能，并验证分析了每种算法实现后的结果。 第四章研究了三种d s p 算法在硬件平台上的实现，以及硬件结构对算法性能 的影响；并验证了三种算法的硬件电路的功能：同时给出了d c 综合f p g a 下载 后的速度信息及结果分析。 第五章对d 砌认平台做了的前沿性研究，重点分析了d r r a 的资源结构、数 据通路单元及针对典型算法时的配置情况。 第六章研究了f p g a 的功耗测试方法，构建了两种测试平台，通过数学理论 推导出其测试结果并分析误差。 第七章是结论及展望。 2d s p 算法原理及实现平台介绍 2 1 f i r 算法 根据单位脉冲响应的长度，d s p 系统可以分为i m ( 无限脉冲响应) 系统与 f 瓜( 有限脉冲响应) 系统。其中，f m 数字滤波器广泛用于数字信号处理领域。 本章首先介绍了f m 的定义、基本操作与数据流，然后揭示了f m 滤波器的重要 特征。 2 1 1f i r 的定义 对f 瓜的定义如下【7 】： y 【n 】= 6 埘n 一，1 ( 2 1 ) ，= 旬 公式2 1 中： n 为滤波器阶数：对于n 阶滤波器，式子的右边有n + 1 项； y n 】为当前输出量： x n - i 】为输入量； b i 为滤波器系数。 公式2 1 表明了f 瓜滤波器的基本操作：当前输出为当前输入与之前n 个输 入的加权和。图2 1 说明了f 瓜滤波器输出与输入之间的关系。 【o 】【n n 】( i = n )【n 】( i = o ) o u t y 【n 】 图2 1n 限滤波器输出与输入之间的关系 f i g u 他2 1 ：t l i er e l a t i o nb e 铆e 锄i n p u t 柚do u t p u to f f 瓜：f i b r 展开公式2 1 ，可以看到f 爪滤波器可以用一个线性的方程来表示： y 【行】= 6 0 x 【玎】+ 6 l 虹九一1 】+ + 6 x 行一】 ( 2 2 ) 4 这里： n ，y n 】，x n i b i ( i - 0 ，1 ，n ) 的含义与前面所述一致。 从定义中可以看出，如果滤波器系数b i 已经设计好，那么滤波器也就确定了。 因此，f m 滤波器的设计任务就是设计出一组系数，使滤波器能够滤除某个频段的 信号。实际上，滤波器系数b i 序列是滤波器的单位脉冲响应h n 】。公式2 1 中， 令缸聆】- 研刀】，得到如下关系式： m 圪】= 善6 j 况川】 ( 2 3 ) = 以 2 1 2 实现f i r 滤波器的基本操作与数据流 f m 滤波器的基本操作是求得当前输入与之前有限个输入的加权和，所以实现 f 瓜滤波器需要两个基本结构：输入延迟线，用来存储之前的有限个输入值；系数 存储单元，计算延迟线中采样数据的加权和。实现滤波器的基本步骤如下： ( 1 ) 将一系列输入信号送入延迟线中； ( 2 ) 送入延迟线的每个输入信号乘以对应的系数实现加权，并累加所有的加 权值； ( 3 ) 将输入序列整体前移一个样本，为下一个输入信号样本留出空间。 图2 2 说明了f m 滤波器的数据流与核心操作。 通n l - - l 一 b 【n 2 】 - l 一 图2 2f 瓜滤波器的数据流 f i g u 托2 2 ：d a t a 玎o 、o ff n t 矗l t e r 图2 2 中，z - 1 表示单位延迟【羽。 2 1 3f i r 滤波器的性质 y 【n 】 f m 滤波器具有很多优势，因此被广泛地使用在d s p 系统中，这些优点包括： ( 1 ) 固有的稳定性 对于一个f 爪滤波器，输出为有限项输入的线性叠加，因而只要输入有界， 输出一定有界，所以f i r 系统一定是b i b o 稳定的，这是内在的稳定性。 ( 2 ) 线性相位响应 f m 滤波器容易实现线性相位响应，这意味着f 瓜滤波器的相位响应是关于频 率的线性函数，因此不同频率的时域信号经过滤波器后的延迟也完全相等，线性 相位f m 滤波器没有相位失真与群延迟失真。可以证明，如果f 瓜滤波器的系数 是关于其中心样本左右对称的( 即第一个系数等于最后一个，第二个系数等于倒 数第二个，以此类推) ，那么它一定是线性相位的f m 滤波器【9 】。如果滤波器的系 数为奇数，那么除了中间的系数，其他的系数全部成对。 ( 3 ) 无反馈结构 f m 滤波器的数据流表明，它只存在前馈通路，不存在反馈回路。因此，它的 结构比较简单，实现容易；并且因为系统中没有环路，由有限精度导致的极限环 振荡现象便不存在。 2 2f f t 算法 2 2 1f f t 定义 f f t 表示快速f o u r i e r 变换，是离散f o u r i e r 变换( d f t ) 的快速算法。d f t 将时域序列分解成一系列不同频率分量的线性叠加，揭示了信号的内在本质，其 定义如下： 研m - 虹尼聘， 聊= o ，1 ，一1 七= o ( 2 4 ) 公式2 4 中： x k 】为输入时域信号； x m 】为输出频域分量； 时为旋转因子e 0 2 删被。 从d f t 的定义式里可以看出，直接计算d f t 的计算量为n ( n 1 ) 次复数加 法( n 个输出，每个输出需要求n 个复数加权和，也就是n 1 次加法，总共需要 n ( n 1 ) 次复数加法) 与n 2 次复数乘法( n 个输出，每个输出需要n 个复数加 权，每个复数加权结果需要做一次复数乘法) 。随着输入序列长度n 的增加，总运 算量将变得十分惊人，使得d f t 的应用受到极大的限制。c 0 0 l e y 与t u l ( e y 提出的 快速算法即f f t 算法利用旋转因子的对称性质，大幅度减小了d f t 的运算量，提 高了d f t 的运算效率。直接的f f t 算法推导需要利用群理论与数论的知识，这里 6 仅以基2 按时间抽取( d i t ) 算法为例，介绍其基本原理，并得出算法复杂度与运 算量的评估【1 0 1 。 2 2 2 基2 按时间抽取f f t 算法原理 ( 1 ) 旋转因子的性质 1 ) 周期性 蚶= 咿训 = 咐似删 2 ) 对称性 盯气= 一吲 ( 咿) = 峨础 ( 2 5 ) ( 2 6 ) 3 ) 可约性 蚶= 州 蚶= 嵫加 ( 2 7 ) 其中，n n 为整数。 ( 2 ) 算法推导 假设输入序列长度n 为以2 为底的幂( 如果长度不够，通过补零来满足要求) ， 抽取序列x n 是指将长度为n 的序列拆分成2 个n 2 长度的序列，拆分如公式2 8 所示。 墨【丘】= x 【2 k 】 x 【七】= x 【2 k + 1 】， 七= 0 ，1 ，2 1 ( 2 8 ) 公式2 8 中，x l k 】为原序列中偶数样本的集合，x 2 眯】为原序列中奇数样本的集 合。根据旋转因子的性质，d f t 的计算过程如公式2 9 所示。注意到，应用公式 2 9 ，一次只能计算出结果x 【m 】的前n 2 个点，注意到x l m 】和x 2 m 】分别是关于 n 2 的周期函数，再一次使用旋转因子的周期性，可以得到x m 】的后n 2 个点， 如公式2 1 0 所示。 一1 仂】_ d f 7 - 埘良】) = x 【k 肿 鼻i o 一1一1 = x 【七肿+ 埘七肿 = 0k = 0 ；o v 鲫k ；o d d = 埘2 厂】忻册+ x 【2 厂+ 1 肾h 1 细 ，；0 r = 0 ，2 1 ，2 1 = x 1 【r 川册+ w 屯【厂蛾册 ，罩0r 暑o ，2 1，2 1 = x 1 【r 懈+ w x ：【r 懈 ( 2 9 ) = x 【m 】+ w 恐【m 】 m = o ，1 ，2 1 x 【m + ，2 】= x 【m 】一咐x 2 【m 】 m = o ，1 ，2 1 ( 2 1 0 ) 这样，一个n 点的d f t 计算就被转化成了两个n 2 点的d f t 计算，反复利 用上面的抽取与推导结果，直到最终只计算2 点的d f t ，就是基2f f t 算法最后 的表达式，此时总共需要计算n 2 个2 点d f t 。 将f f t 算法使用到8 点序列的d f t 计算中，其数据流图如图2 3 所示【1 1 】。可 以看出，整个f f t 算法呈现多级运算，且由一系列基本的蝶形单元组成，图2 4 为f f t 计算的蝶形单元。 ( o ) x ( 4 ) ( 2 ) x ( 6 ) ( 1 ) ( 5 ) ( 3 ) x ( 7 ) 图2 38 点h 叮的数据流图 f i g u r e2 3 ：s i g n a ln o wd i a g 衄f 0 r8p o i n t s ) ( o x 1 ) ( o 1 图2 4 蝶形运算单元 f i g u r c2 4 ：ab u t t e 棚y 8 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) 一般来说，对于一个n 点序列，假设n - 2 m ，其基2f f t 算法有m 级，每级 有n 2 个蝶形单元完成2 点f f t 运算。因此，蝶形单元的总数量为 州2 m = m 2 i o g ，j 。每个蝶形单元完成一次复数乘法与两次复数加法。这样，n 点序列的d f t 的运算量就是( 叫2 ) l 0 9 2 次复数乘法与1 0 9 2 次复数加法，与之 前的n 2 数量级相比，f f t 算法无疑大大减小了d f t 的运算量，而且这种优势随着 输入序列长度n 的增大而越发显著，这使得d f t 具备了实际的工程意义，被广泛 地应用于信息技术领域。 论文选取“点基2 按时间抽取f f t 算法作为实现对象，原因有两点：( 1 ) d 认平台内部每个小处理器对应的存储单元深度是6 4 ，因此选取“点f f t 算法 便于测试激励的添加；( 2 ) 基2f f t 算法是最基本的f f t 算法，其他一切的f f t 算法，如，基4 、基8 、混合基、分离基算法的原理都是从基2 算法中推演而来， 基2f f t 算法与其他升级版本的算法的核心是：循环递归，即把原始序列抽取成 一系列子序列，反复抽取子序列形成很多更短的子序列，对最终的子序列做f f t 并叠加、排序形成最终结果，通过减小做f f t 运算的子序列长度来大幅度减小整 体的运算量。 2 3v i t e r b i 译码算法 2 3 1v i t e r b i 译码算法的重要性 通信系统中，数据在传输过程中总会存在一定的误码，如果这些误码不能被 纠正，很有可能导致接收端恢复的数据资料不正确，造成通信的失败。因此，人 们设计出多种误差校验算法，在发送端产生一些数据冗余位，在接收端检测冗余 位与目标数据，按照算法修正目标数据在传输过程中产生的误码，降低误码率， 提高通信质量。在各种校验算法中，卷积码以其较高的误码校验能力而受到广泛 的青睐【1 2 】。而v i t e r b i 译码算法正是一种用于卷积码译码的高效率算法。据gd a v i d f o m e y j r 的“t h ev i t e r b ia i g o r i t l l i n ：ap e r s o n a ih i s t o 珂 一书中报道，当今世界， 有至少十亿的移动电话采用t e r b i 译码器；此外，数字视频与广播中，v i t e r b i 译 码算法的应用更加广泛。 2 3 2v i t e r b i 译码算法的概念 v i t e r b i 译码算法用于解码经过误差校验卷积编码的码流，是卷积编码的逆运 算，因此，这里先介绍有关卷积编码的基础知识。 9 卷积码用两个重要的参数来描述：码率与约束长度。码率m n 表示每个编码 周期输入比特数m 与输出码元的比特数n 的比；约束长度k 表示每个编码周期计 算输出码元所需的比特数。卷积码通常用以上两个参数表示成( n ，m ，k ) 。其中， 约束长度k 越大，纠错能力就越强。通信质量也就越高。 v i t e r b i 算法是最有吸引力的卷积码译码算法，它根据接收的一定深度的码流， 通过回溯来寻找最有可能的原始序列。它的优点是准确度高，译码时间固定不变， 适合硬件实现。不过随着约束长度的增加，其算法的运算量也激增。因而，一般 来说，在实际应用中，t e r b i 算法适用于约束长度小于9 的卷积码的译码【1 3 】【1 4 】。 2 3 3 算法描述 ( 1 ) 卷积编码 卷积编码的过程就如它的名字一样，用输入序列与一个己知的多项式( 生成 多项式) 计算卷积得到输出码流，如公式2 1 1 所示： y ( 门) = x ( 仃) g ( 门) ( 2 1 1 ) 公式2 1 1 中： y ( n ) 为卷积编码器的输出码元； x ( n ) 为输入比特流； g ( n ) 为生成多项式，对于一个给定约束条件的编码器，都存在一个最优多 项式。 根据上述定义，卷积编码运算可以由移位寄存器组及模2 和( 异或) 运算的 组合逻辑来完成。移位单元组完成输入序列的暂存与移位，每个编码周期将输入 序列整体移位l b i t ，并引入新的输入比特，在硬件中可以由寄存器链实现，软件中 可由指针实现。异或运算单元组则执行卷积操作。 值得注意的是，进行卷积编码，将输入序列传送至移位寄存器链的过程中， 在输入序列的末尾需要补上k 1 个零( m 为约束长度) ，并计算出k 1 个冗余码元， 以保证输出码流最后k 1 个码元具有与之前码元相同的纠错能力。 ( 2 ) v i t e r b i 译码 理解v i t c r b i 译码算法的关键是网格图，图2 5 ( 摘自1 1 1 t e m e t ： h t c p ：胁o m e n e t c o m c o m 一c h i p 伽i t e r b i a l g m 曲s 2 h 臼n 1 ) 是一个( 2 ，1 ，3 ) 卷积码的网 格图，包含了1 5 b i t 的信息。 l o 9 瞰 9 瞰们 筑t 1 0 9 i t 1 1 t - t 1 6 1 7 一，一 ：! l 图2 5v i t e 而i 译码网格图 f i g u 陀2 5 ：v i t e r b id c c o d c 骶l l i sd i a 鲈锄 卷积编码器中，实现移位的寄存器里的数据代表了整个电路的状态。在图2 5 中，卷积码的约束长度是3 ，需要两个寄存器来暂存前两个输入比特，因此可以形 成一个两位的二进制数，即4 个状态。编码1 5 b i t 的原始比特数据，为使最后两位 具有跟前面数据相同的约束，在原始比特流后补2 个零，产生1 7 个输出码元。图 中实线表示输入为电路状态的跳转，虚线表示输入为0 时状态的跳转。由于每个 移位寄存器中初始值为0 ，因此初始状态为0 0 ，且由于在原始输入序列末尾补了2 个零，因此最后一个状态也是0 0 。从初始状态0 0 开始，每个周期开始，如果输入 1 ，状态则按照实线箭头跳转；如果输入o ，状态则按照虚线箭头跳转。也就是说， 下一个状态完全取决于上一个状态以及输入比特，状态转换关系如表2 1 所示。 表2 1 状态转换表 1 a b l e2 1 ：s t a t et ：m n s i t i o nt a b l e 0 0 0 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 对于译码器来说，每接收一个码元( 一个码元包含的比特数由编码器的输出 决定，在( 2 ，l ，3 ) 卷积编码器中，一个码元包括2 个比特) ，就计算该码元与能 形成当前状态与前一状态之间跳转的所有可能接收到的码元之间的“度量 。计算 完度量之后，译码器还需要完成三件事情：将当前的度量值与之前的累加度量值 累加，得到新的累加度量值；比较到达当前状态的所有累加度量值的大小：选出 使得累计度量最小的前一个状态，并存储这个状态。这个过程称为“加比选操 作( a c s ) 。图2 6 详细说明了a c s 操作( 图中所有元素的意义与图2 5 相同) 。 前一状态 ( 存储有路径度量值) 状态o o 状态0 l 状态1 0 状态1 l 当前状态 ( 当前路径度量值) 图2 6 加比选操作 f i g u r e2 6 ：a c so p e r a t i o n 本文采用汉明距离计算度量，即两个码元里不同的比特数，而前一状态与当 前状态之间跳转的路径称作“分支”，因此该汉明距离在t e r b i 译码器中称作“分 支度量。 以上信息建立以后，v i t e 而i 译码器就可以恢复输入到卷积编码器被编码传输 的原始信息了。译码步骤可以概括如下： ( 1 ) 选取具有最小累加分支度量值的状态作为回溯的起点。 ( 2 ) 回溯。迭代执行以下步骤直到图2 5 所示网格图的起点：从历史状态列 表中选出当前状态对应的先前状态，得到整个回溯深度内的所有幸存状态。该过 程是逆向执行的。 ( 3 ) 沿着步骤( 2 ) 得到的幸存状态列表正向执行，依据状态转换表找出每 两个状态之间对应的输入。 2 4d s p 算法的实现平台简介 一般来说，数字信号处理算法的两种传统实现平台分别为软件和硬件。软件 实现通过计算机语言如c 语言、汇编语言等编写工程文件即程序，由通用c p u 或 专用d s p 芯片编译成一系列串行的指令，指令中包含要执行的操作与操作数，当 指令序列全部执行完毕后，输出最终结果。硬件实现是将某种特定的d s p 算法映 射成为电路，由外部模块输入待处理数据，算法的硬件电路经过计算后输出处理 数据。硬件实现主要分为a s i c 与f p g a 。上述的所有实现平台都有特定的优劣， 如何选择取决于应用环境与要求。 总的来说，软件实现成本较低，其中包括：开发周期短、更新与升级简单、 移植性强；但是由于软件实现的本质是由处理器将工程文件编译成指令序列，并 串行执行( 尽管当代通用c p u 与d s p 芯片采用多核结构，但指令仍然需要在每个 1 2 内核里串行执行) ，而专用的硬件电路则针对特定的d s p 算法优化电路结构，且其 内部信号随输入改变而迅速改变，因此软件实现的速度比硬件慢得多。在软件实 现的两种方案：通用c p u 与专用d s p 芯片中，因为当代的通用c p u 架构均为x 8 6 ， 而专用d s p 芯片则没有统一架构，因此通用c p u 实现策略的移植性更强；但是因 为专用d s p 芯片内部的运算单元为d s p 算法中的特殊操作所专门优化，如乘加器、 复数运算单元、环形f i f o 等，而通用c p u 则没有对d s p 算法进行专门优化，内 部的a l u 只是为绝大部分的应用软件操作所需，因此专用d s p 芯片的运行效率更 高、运算速度更快。 在硬件实现的两种策略中，f p g a 与a s i c 也各有优劣。f p g a 由于其相对于 软件实现的高速、与相对于a s l c 的灵活性，近些年对于实现d s p 算法的吸引力 越来越强。它通过编译r t l 级的h d l 硬件描述文件，同时考虑其内部资源如查找 表、寄存器、洲等，综合生成电路网表；通过专用的数据接口，配置其内部资 源生成源h 】) l 文件描述的功能电路模块。因为它的内部资源丰富且可配置可重构， 每次设计与升级只需更新源h d l 与配置文件即可，且硼d l 语言标准统一，因此 它具备软件实现的很多优点如开发灵活、升级简单、移植性强：并且由于它本质 上是硬件电路，因此相对软件实现又具备硬件的高速优势。 a s i c 则是通过编写r 1 l 级的h d l 硬件描述文件，经过综合、静态时序分析、 布局布线、后端验证等一系列严格的流程，产生针对某d s p 算法的专门优化的硬 件电路版图，交给半导体加工厂商进行流片生产。由于它所有的电路与结构都是 针对该d s p 算法专门优化，因此其速度与功耗最为理想，但是它的开发成本最高、 周期最长、难以升级。 综上所述。硬件电路映射d s p 算法能够实现高速、高数据吞吐率和低功耗的 目标，因此近年来硬件实现d s p 算法的研究非常热门。人们不断发明和改进新结 构提高性能、降低功耗与面积【1 5 】【1 6 】【1 7 1 。 1 3 3 软件平台上的算法实现与分析 软件实现算法的速度主要取决于算法的复杂度、待处理的数据量及数据存储 位置。一般情况下，待处理的数据量及算法的复杂度是由设计要求及算法本身决 定的，本论文主要研究在规定算法及要求的前提下算法实现时对速度的优化，因 而主要从数据存储位置方面优化。数据放在内存中的处理速度是最快的，反之， 如果待处理的数据存储在硬盘上，那么读取数据就需要很长时间。当然，数据存 放位置会受到内存的限制，当内存有限时，可以通过优化算法的空间复杂度，让 程序一次处理的数据多一些。而当内存空间相对于要实现的算法足够大时，可以 把数据放在内存中。 本文研究的三种算法的复杂度不高，需要的存储空间不大，因而通过将待处 理的数据放在内存中来提高速度。具体做法是在程序中读取待处理数据，放在程 序可用的数据结构( 如数组) 中，这样可以减少读取硬盘的次数，节省处理时间。 算法实现的功耗与速度相关，在相同面积条件下，速度低则功耗低。也就是 说功耗与速度及面积之间存在如下关系式： p = f ( y ，s ) ( 3 1 ) 公式3 1 的给出，目的是在给定处理实时性要求条件下，根据算法概念降低功 耗。这里，p 是电路消耗的功耗。s 是器件的面积，软件实现时可以看成是常数， 硬件实现时与计算结构相关。v 是时钟速度，由处理速度要求所决定，处理速度 由实时性要求所决定，而处理速度与处理过程有关，即与算法的计算结构直接相 关。 可见，速度与功耗是一对矛盾，在实际算法实现的时候，应根据应用需求， 得出算法的实时性要求，实现速度与功耗的折中。 3 1f f t 算法实现 3 1 1 基2f f t 算法 分析图2 3 所示的基2 按时间抽取f f t 算法的数据流图，可以得到关于实现 该算法的三个重要特点： ( 1 ) 输出序列按频率由直流分量到最高频率分量( 即为兀) 的顺序排列，输 入序列则需要经过二进制倒序进行重排列。二进制倒序是指：写出从0 0 o 到1 1 l 1 4 的自然二进制数顺序，再将每个二进制数按比特从右到左反向排列，因此原来的 最低位变成了最高位，次低位变成了次高位，以此类推，新形成的二进制数序列 即为原来序列的二进制倒序。以8 点序列为例，其位取反方法如图3 1 所示。 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 斗1 1 1 图3 18 点序列为例的二进制倒序排列示意图 f i g u 陀3 1 ：吐i cb i t r c v e 巧a ld i a g m mf o r8 p o i n ts e q u c n ( 2 ) 在该算法的第一级中，只需要1 ( 2 0 ) 个旋转因子，即为w n o ，同一个 蝶形单元里，两个输入的操作数之间在重排序后的输入序列内位置上的距离也是1 ( 2 0 ) ；在第二级中，需要2 ( 2 1 ) 个旋转因子，分别是w n o 和w n 2 ，同一个蝶形 单元里，两个输入的操作数之间的距离则是2 ( 2 1 ) 。一般地，在第m 级中，需要 2 m 个旋转因子，分别是w n o ，w n n 忍m w n 洲胁，且同一个蝶形单元的两个操作 数之间距离为2 m ，即为所需旋转因子的数量。 ( 3 ) 每级运算所需的蝶形运算单元数量相同，且数据流向只有前馈、没有反 馈，因此可以重复利用一组蝶形运算单元，进行同址运算。具体来说，就是在时 序的控制下，使用一组( n 2 个) 蝶形运算单元，将每级运算的输出结果覆盖输入 端，重复利用这组蝶形运算单元直到运算结束。每级的运算需要改变的仅仅是旋 转因子【1 8 】【1 9 】【2 们。 3 1 2 程序流程图 在3 1 1 节分析的基础上，输入序列需要经过二进制倒序，再参与运算。有两 种方法可以实现输入整序：( 1 ) 将输入序列直接按照二进制倒序存储并按地址顺 序读取；( 2 ) 将输入序列按照地址顺序存储并按二进制倒序读取，论文采用第一 种方法。对于“点基2f f t 运算来说，共需要6 ( 1 0 9 2 “) 级运算，在第m 级有 2 6 哪组，一级里的每一组共享相同的2 m 个旋转因子。观察旋转因子随运算级数的 变化规律可知，第m 级所需的相邻2 个旋转因子序数之间相差2 佃，这用来确定 每级所需的旋转因子在事先准备计算好的旋转因子存储器里的地址。“点基2f f t 算法的具体程序流程图如图3 2 所示。 图3 2 “点基2f f r 算法的程序流程图 f i g u r e3 2 ：6 4 - p o i n tr a d b c - 2f f t 算法实现的验证步骤如下：( 1 ) f f t 的软件实现程序从源文件里读取输入数 据，经过程序运算后将结果存入目标数据文件；( 2 ) m a t l a b 标准f f t 函数读入 相同的源文件作为输入信号，经过标准函数运算后的结果作为正确结果，与目标 数据文件的结果进行比对。图3 3 说明了算法实现验证的流程。在这里，由于输入 1 6 序列长度超过了6 4 点即程序实现的f f t 运算长度，因此，将输入序列截成6 4 点 的子序列，分别做f f t 运算并叠加子序列的运算结果。稍后会证明此做法的合理 性。 图3 3f f t 软件实现验证方案 f i g u 他3 3 ：v c f i c a 嘶o nd a t a f l o wf 0 r6 4 _ p o i n tr a d i x 一2f f r 这里将证明上述将长序列截成一系列子序列分别做f f t 并将子序列的f f t 结 果叠加的合理性，叠加后的结果完全能反映原长序列的频谱。 假设，长序列埘仃】补零后的长度为2 。，其2 。点f f t 结果为： 2 l 一1 f f t m = 州仃】哗 ( 3 2 ) n 柏 该序列被截断成多个连续的2 n 点的较短子序列，运用d f t 的定义式，这些较 短子序列的f f t 分别可以表示成： 1 7 【卅= x 【川嶝 2 n 1 1 x 1 【卅2 x m 咄 n = z m 扩卜1 x 【卅= x 【n 】皑 ( 3 3 ) 所有较短子序列的f f t 结果累加合成2 。点原序列的2 n 点f f t 的最终结果，将 公式3 3 里的式子全部叠加： 2 l 刺1 b 阿渊