（微电子学与固体电子学专业论文）一种用于无线通信的dsp结构设计与实现.pdf

中文摘要 摘要：随着数字信号处理技术和半导体技术的迅速发展，数字信号处理系统越来 越趋向以数字信号处理器( d s p ) 为核心，各种数字信号处理系统已经可以采用单片 系统实现，基于d s p 内核的专用数字信号处理系统芯片开发模式成为这类系统开 发的主流方式，通过采用合适的d s p 内核可以简化设计并缩短产品上市时间，快 速实现不断发展地数字信号处理算法。 本文分析了无线通信领域的常用算法，如维特比算法，基于分析对d s p 提出 了要求，并对现有d s p 器件进行了分析，指出了其不足之处。相比于现有d s p 通 过多处理单元，大总线宽度和并行性来提高d s p 的运算速度，提出了基于算法的 d s p 结构，通过提高算法符合度来提高d s p 的运算速度。针对特定算法，还设计 了相应的指令、适合算法的总线结构和运算单元结构。 对于所设计的d s p 结构，做了i p 核开发的尝试。用v e r i l o g 对整体结构作了 行为级描述和仿真。各个运算单元结构进行了r t l 级描述和门级综合，门级仿真。 仿真结果表明，和现有d s p 相比，虽然本文设计的d s p 运算单元较少，结构简单， 但是由于算法符合度高，处理特定算法( 如维特比算法) 的速度上并不输给复杂d s p 器件。 关键词：d s p i p 核；无线通信；维特比；a l u ；乘累加单元 分类号：t n 4 3 1 2 a b s t r a c t ： w i i ht h er a p i dd e v e l o p m e n to fd i g i t a ls i g n a lp r o c e s s i n gt e c h n o l o g ya n ds e m i c o n d u c t o r t e c h n o l o g y , m o r ea n dm o r ed i g i t a ls i g n a lp r o c e s s i n gs y s t e m sa r eu s i n gd i g i t a ls i g n a l p r o c e s s o r ( d s p ) a ti t sc o r e a l lk i n d so fm g i t a ls i g n a lp r o c e s s i n gs y s t e m sc a n b eu s e dt o a c h i e v es i n g l e - c h i ps y s t e mb a s e do nd s pc o r 0 $ d e d i c a t e dd i g i t a ls i g n a lp r o c e s s i n g s y s t e m - o n c h i pd e v e l o p m e n tm o d e li n t ot h em a i n s t i e e mo ft h ed e v e l o p m e n to fs u c h s y s t e m s t h r o u g ht h el 啪o fa p p r o p r i a t ed s p c o r ec a l ls a m # i f yt h ed e s i g na n dt i m et o m a r k e t , a c h i e v i n gt h ed i 百t a ls i g a a lp r o c e s s i n ga l g o r i t h m sr a p i d l y t h i sp a p e ra n a l y z e st h ef i e l do fw i r e l e s sc o m m u n i c a t i o n sa l g o r i t h mc o m m o n l yu s e d , s u c ha st h ev i t e r b ia l g o r i t h m , b a s e do nt h ea n a l y s i ss e tr e q u i r e m e n t sf o r t h ed s ea l s o t h ee x i s t i n gd s pd e v i c ew a sa n a l y z e d ，p a i n t i n go u ti t ss h o r t c o m i n g s c o m p a r e dt o e x i s t i n gd s pt h a tm e r e a s ot h en u m b e ro fp r o c e s s i n gu n i t s ，t h eb u sw i d t ha n dt h e p a r a l l e l i s mt oi n c r e a s ec o m p u t a t i o n a ls p e e d , t h i sp a p e re n h a n c et h ed e g r e eo fd s p c o m p u t a t i o n a ls p e e db a s e do nt h ep r o p o s e ds t r u c t u r ef o rs p e c i f i ca l g o r i t h m s ，a l s o d e s i g n e dt h ec o r r e s p o n d i n gi n s t r u c t i o m ，t h eb u sa r c h i t e c t u r ea n dc o m p u t i n gu n i t s t r u c t u r es u i t a b l ea l g o r i t h m t i l i sp a p e rd e s i g n e di pe o r ef o rt h ed s pa r c h i t e c t u r eh a sp r o p o s e du s i n gv e r i l o gh d l 1 1 1 ep r o c e s s i n gu n i t sh a v eb e e nd e s c r i b e di nr t lc o d e a l s o 。g a t e - l e v e ls y n t h e s i sa n d g a t e - l e v e ls i m u l a t i o nh a v eb e e nd o n e 1 1 把s i m u l a t i o nr e s u l t ss h o wt h a t , c o m p a r e dt o e x i s t i n gd s p , t h ed e s i g n e dd s ph a sl e s sc o m p u t i n gu n i t , s i m p l e rs 饥i c t u r e , b u td u e t o t h ea r c h i t e c t u r es u i t i n gt os p e c i f i ca l g o r i t h m s ( s u c ha sv i t e r b ia l g o r i t h m ) i sn o tl o s to n t h es p e e d k e y w o r d s ：d s p ；i p c o r e ；w i r e l e s sc o m m u n i c a t i o n ；v i t e r b i ；a l u ；m a c c l a s s n o ：t n 4 3 1 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：翻翱导师签名：肱 签字日期：0 7 年j 月猡日t t 字bj l i i ：刁年阻月落日 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：南翔日 签字日期： 0 7 年f ) ，月修日 致谢 本论文的工作是在我的导师李哲英教授的悉心指导下完成的，李哲英教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来 李哲英老师对我的关心和指导。 周小龙老师悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向周小龙老师表示衷心的谢意。 赵俊良老师和韩玺老师对于我的科研工作和论文都提出了许多的宝贵意见， 在此表示衷心的感谢。 在实验室工作及撰写论文期间，李争、李博都对我论文撰写和研究工作给予 了热情帮助，在此向他们表达我的感激之情。 另外也感谢我的母亲和王春蕾，她们的理解和支持使我能够在学校专心完成 我的学业。 序 当前，数字信号处理技术已被广泛应用在国民经济和国防的所有领域，因此 作为其核心部件的数字信号处理器( d s p ) 随着v l s i 技术的发展，性能不断提高， 价格不断降低，而且市场规模不断扩大，应用前景非常广阔。因此对于d s p 器件 结构和实现的研究意义重大。 d s p 器件越来越多地应用于无线通信领域，移动终端设备朝着体积小、重量 轻、性能好的方向发展，要求d s p 芯片具有低功耗、高性能、通用性好等特性， 能够在成本较低的情况下实时地完成复杂的运算。与此同时由于无线通信中不同 的算法有不同的标准，这又要求d s p 器件具有一定的通用性。 本文基于d s p 应用领域算法特点，对d s p 的结构进行了相关的研究。 分析了无线通信领域的常用算法，如维特比算法，基于分析对d s p 提出了要 求；并对现有d s p 器件执行维特比算法进行了分析，发现了不足。针对这些不足 本文提出了基于算法的d s p 结构，提高结构对算法的支持度，同时设计易于算法 的指令系统和处理单元结构，使得在简单的结构下，能够尽量提高d s p 对算法的 运算速度，可在相同的速度甚至更快地速度下，减少了芯片冗余度，缩小芯片面 积。 对于所设计的d s p 结构，做了口核开发的尝试。用v e r i l o g 对整体结构作了 行为级描述和仿真。各个运算单元结构进行了r t l 级描述和门级综合，门级仿真。 仿真结果表明，和现有d s p 相比，虽然本文设计的d s p 运算单元较少，结构简单， 但是由于算法符合度高，处理特定算法( 如维特比算法) 的速度上并不输给复杂d s p 器件 本文分五部分，第一部分是引言，介绍数字信号处理器技术、课题的现状、 研究意义以及本文研究的主要问题和文章组织；第二部分简单介绍了无线通信系 统，并对无线通信系统中的典型算法进行了分析；第三部分在第二部分对无线通 信典型算法分析的基础上，提出了应用于无线通信领域的d s p 的需求，并对现有 的几种d s p 在无限领域应用傲了分析和比较，提出了不足，根据此需求和分析提 出了基于算法的d s p 的结构设计。第四部分是内核的实现，主要介绍了基于算法 的处理器内部结构设计，各个功能单元的设计和实现：第五部分介绍了内核的设 计流程、验证和仿真，以及仿真结果；第六部分为结论和后续工作。 由于作者水平有限，本文中一定存在不少缺陷和不足，真诚地希望请读者指 正。 引言 1 引言 1 1数字信号处理器技术 d s p 有别于普通的科学计算与分析，强调运算处理的实时性，因此除了具备 通用处理器所强调的高速运算和控制功能外，针对实时数字信号处理，在处理器 结构、指令系统、指令流程上都作了很大的改动，其结构特点如下i l 】： 1 ) d s p 属于哈佛架构 具有两条内部总线：数据总线、程序总线。程序与数据存储空间分开，各有独 立的地址总线和数据总线，取指和读数可以同时进行。 2 ) 大多采用流水作业 每条指令的执行划分为取指令、译码、取数、执行等若十步骤，由片内多个 功能单元分别完成。相当于多条指令并行执行，从而大大提高了运算速度。 3 ) 独立的硬件乘法器 乘法指令在单周期内完成，优化卷积、数字滤波、f f t 、相关、矩阵运算等算 法中的大量重复乘法。独特的乘累加指令。 舢循环寻址( c i r c u l a ra d d r e s s i n g ) ，位倒序( b i t - r e v e r s e d ) 寻址 循环寻址和位倒序使f f t 、卷积等运算中的寻址、捧序及计算速度大大提高。 1 0 2 4 点f f t 的时问已小于i p s 。 5 1 独立的d m a 和总线控制器 有一组或多组独立的d m a 总线，与( p l 的程序、数据总线并行工作，在不影 响c i u 工作的条件下，d m a 速度己达8 0 0 m b y t e s 以上。 6 ) 多处理器接口 使多个处理器可以很方便的并行或串行工作以提高处理速度。j t a g ( j o i n t t e s t a c t i o ng r o u p ) 标准测试接i ( i e e e11 4 9 标准接口) ，便于对d s p 作片上的在线仿真 和多d s p 条件下的调试。 7 ) 片内片外两级存储体系 采用片内片外两级存储体系，是d s p 芯片结构的又一特色。片内存储器的特 点是速度快，可以多个存储器块并行访问，但是容量不可能太大。片外存储器的 容量大，由于要通过总线与处理器交换数据，因此速度不能太快。 8 ) 零开销循环控制 大部分d s p 处理器具有零开销循环控制的专门硬件。零开销循环是指处理器 北京交通大学硕士学位论文 不用花时问测试循环计数器的值就能执行一组指令的循环。硬件完成循环跳转和 循环计数器的增减。有些d s p 还通过一条指令的超高速缓存实现高速的单指令循 环。 数字信号处理器( d s p ) 、通用微处理器( m p l 9 和微控器( m c u ) 三者的区别在于： d s p 面向高性能、重复性、数值运算密集型的实时处理；m p u 大量应用于计算机； m c u 则适用于以控制为主的处理过程【2 】。 虽然先进v l s i 技术不断地被采用，使得时钟频率不断提高，片内总线以及存 储器的容量不断增加，d s p 的峰值运算能力己经可以达到每秒1 0 亿次【3 】，但是相 对于人们要求的每秒几百亿、上千亿次的运算来说仍远远不够。而且v l s i 技术的 发展己经受到其开关速度极限的限制，进一步提高d s p 主频所遇到的难度和付出 的成本越来越大，单处理器性能的提高空间受到限制，为此，在d s p 研制中引入 了并行处理技术。 考虑到在许多专用和高速的场合的应用，d s p 在结构上也不断推陈出新，使 其能非常有效地实时处理一些特殊算法，而这些特殊算法用通用d s p 结构和编程 方法来实现时的效率低且程序很长，不能满足实时处理的要求。例如在d s p 核中 加入专用的处理单元，如d c t ，维特比，r e e d s o l o m o n ，w a v l e e t 编码解 码器，增加向量、矩阵运算所需的寻址功能和向量流水功能，同时增加片内r a m 的容量等都能够大大提高d s p 的性能。 目前，d s p 器件技术的发展十分迅速，应用范围广阔，市场规模巨大，如表 1 1 所示【4 】，已成为i c 业中最活跃、发展潜力最大的一部分因此，开发拥有自主 产权的d s p 器件和系统，就显得格外重要。 表1 1 可编程d s p 的市场发展( 单位：百万美元) t a b l e1 i t h e p r o g r a m m a b l e d s p m a r k e t d e v e l o p m e n t 产品规格标准产品 特殊应用产品可定制产品合计 1 9 9 1 58 5 05 9 52 5 5 1 7 0 0 2 0 0 02 3 9 04 3 0 4 2 4 4 2 9 1 3 5 2 0 0 56 7 0 0 3 1 0 8 52 3 2 9 34 9 1 3 0 年均增长率2 3 0 5 4 8 5 0 5 7 1 0 4 0 0 0 1 2课题的现状及研究意义 当前系统芯片己成为i c 发展的必然趋势，口设计方法被广泛采用，基于口 2 引言 核的集成电路设计已经成为i c 设计的主流方法，现在国家已经把i c 产业作为国 家重点支柱产业来发展。然而目前国内在m 核的开发方面还没有开发出自己的产 品能提供给用户使用，因此，开发一个产品往往需要从头开始一个一个模块的设 计，这样的设计开发周期通常很长，成本高，大量的时间花在许多重复的工作中， 而且可靠性一般难以保证，产品缺乏竞争力。购买国外的m 产品价格往往非常的 高，很不利于终端产品参与市场的竞争，这些都极大地制约了我国在i c 领域的发 展嘲。 由于目前数字信号处理技术应用广泛，d s p 发展迅速、市场庞大，因此，对 在i c 设计中对d s p 的i p 芯核的需求必然是越来越大。但是国内的i c 设计和生产 都还比较落后，基本上还没有自己的d s p 产品，更谈不上可供用户选择的口芯核， 国内的市场基本上是给国外公司的产品占据，这与国内巨大的市场需求和国际上 d s p 的飞速发展是很不相衬的。 因此，研制和开发拥有自主产权的d s p 产品，不仅可获得可观的经济效益， 而且，由于在d s p 中集合了最先进的工艺技术和i c 设计方法，所以研制和开发 d s p 产品还可用促进国内i c 设计技术和生产工艺技术水平的提高，紧跟世界先进 水平，从而推动我国民族微电子行业以及与之相关的信息产业的发展。另外由于 数字信号处理技术在国防军事领域中已被广泛应用，因此开发出国内自主产权的 高性能d s p 将有力地促进国防现代化的发展。 1 3论文主要工作及内容安排 本文分析了无线通信领域的常用算法，如维特比算法，基于分析对d s p 提出 了要求，并对现有d s p 器件进行了分析，指出了其不足之处。相比于现有d s p 通 过多处理单元，大总线宽度和并行性来提高d s p 的运算速度，提出了基于算法的 d s p 结构，通过提高算法符合度来提高d s p 的运算速度。针对特定算法，还设计 了相应的指令、适合算法的总线结构和运算单元结构。 采用自顶向下的设计方法，完成了用于无线通信的d s p 体系结构的设计和部 分高性能运算部件的设计。用v e r i l o g 对整体结构作了行为级描述和仿真。各个运 算单元结构进行了r t l 级描述和门级综合，门级仿真。本文对d s p 的结构进行了 分析和研究，重点研究了如何建立适合特殊计算的口核结构。 本文分五部分，第一部分是引言，介绍数字信号处理器技术、课题的现状、 研究意义以及本文研究的主要问题和文章组织；第二部分简单介绍了无线通信系 统，并对无线通信系统中的典型算法进行了分析；第三部分在第二部分对无线通 北京交通大学硕士学位论文 信典型算法分析的基础上，提出了应用于无线通信领域的d s p 的需求，并对现有 的几种d s p 在无限领域应用做了分析和比较，提出了不足，根据此需求和分析提 出了基于算法的d s p 的结构设计。第四部分是内核的实现，主要介绍了基于算法 的处理器内部结构设计，各个功能单元的设计和实现；第五部分介绍了内核的设 计流程、验证和仿真，以及仿真结果；第六部分为结论和后续工作。 4 无线通信介绍及典型算法分析 2 无线通信介绍及典型算法分析 2 1无线通信系统概述 所有的无线通信系统如通信、雷达、遥控遥测、数字计算机的存储系统和内 部运算以及数字计算机之间的数据传输等，都可以归结为如图1 1 所示的模型6 】。 i 一- 图2 1 无线通信系统模型 f i g u r e2 1w i r e l e s sc o m m u n i c a t i o ns y s t e mm o d e l 在图2 1 中，信源编码器是把信源发出的消息如语言、文字、图像等转换成为 二进制形式的信息序列，并且为了使传输有效，还去掉了一些与传输信息无关的 多余度。为了抗击传输过程中的各种干扰，往往要人为地增加一些冗余度，把不 带规律性或规律性不强的原始数字信号变换成为带上规律性或加强了规律性的数 字信号，使其具有自动检错和纠错能力，这种功能由图2 1 中的信道编码器即纠错 编码器完成。信道译码则利用这些规律性来鉴别是否发生错误，进而纠正错误。 所以，纠错编码在通信系统中起着保护信号传输的完整性和正确性的积极作用。 纠错编码经过几十年的发展已比较成熟，各种纠错码如循环码、b c h 码、r s 码、卷积码、t t u b o 码、l d p c 码以及调制与纠错码相结合的t c m 码等都得到了 研究和发展，其中近代代数理论的应用，为代数编码提供了理论基础。随着大规 模集成数字电路的发展，实际中采用纠错编码技术解决问题也将日益广泛，各种 纠错编码技术已经深入到通信、数据传输与存储等诸多领域，成为众多的业界标 准。 卷积码是一类重要的前向纠错编码，编码简单，易于实现最佳译码，是当今 无线数字通信系统的一个十分重要的组成部分，目前无线数字通信系统都采用某 一形式的卷积编码，如在在i s - 9 5 、w - c d m a 、d v b s 、d v b - t 、i e e e 8 0 2 1 l 系统 5 北京交通大学硕士学位论文 中都使用了卷积编码【刀。由于卷积编码出色的纠错性能，一般在级联码中作为内码 使用，为外码的有效工作而服务，以大大提高整个系统的纠错能力。 2 2卷积码的基本原理 卷积码是1 9 5 5 年由e l i a s 提出的。在卷积编码中，本组的校验单元不仅与本 组的信息源有关，而且还与以前各时刻输入至编码器的信息有关。 图2 2 ( 3 ，1 ，2 ) 卷积码示意 f i g u r e2 2 ( 3 ，1 , 2 ) c o n v o l u t i o n a lc 0 d 酋 图2 2 给出了一个二进制卷积码的编码器。若在每一个时间单位内向编码器输 入一个新的信息源m i ，且存储内的数据往右移一位，则1 1 1 i 一方面直接输出至信道， 另一方面与前两个单位时间送入的信息元m l j ，m i - 2 按途中路线所确定的规则进行 运算，得到此时刻两个检验元阳和p 啦，跟随在m i 后面组成一个子码c i = ( 1 n i ，p i i ， p i t 2 ) 送出信道。由图可知： p i 1 = m ，+ 肼，- l ( 1 ) ，j 2 = m i + 研f - 2 ( 2 ) 下一个时间单位输入的信息元为m h i ，与其相应的两个检验元： p ，+ = 坍i + l + 舶j ( 3 ) p j + 1 25 坍i + 镌一l ( 4 ) 组成第二个子码e i + l 和，阻i ，l ，阳。2 ) 送至信号，如此等等。在每一时间单 位，送至编码器】( o 个信息元，编码器就送出相应的1 1 0 个码元组成的一个子码c i 送 入信道，这n o 个码元组成的子码c i 有时也成为卷积码的一个码段或子码。 以上讨论的卷积码编码器输出的每一个字码中的校验单元，使此时刻输入的 信息元与前m 个字码中信息元的模2 和，是线性关系，所以这类编码器编出的卷 积码是线性码，称为线性卷积码，并且称m 为编码存贮，表示输入信息组在编码 6 无线通信介绍及典型算法分析 器中需存贮的单位时间。称m + l = n 为编码约束度，说明编码过程中互相约束的码 段的个数。称n - - m + l 为编码约束长度，说明码段过程中互相约束的码元个数。所 以，卷积码通常用( 1 1 0 ，k o ，m 0 ) 表示。r = k o n o 称为卷积码的码率。 ( 2 ，1 2 ) 卷积码的编码示意图如图2 3 所示。 图2 , 3 ( 2 ，1 ，2 ) 卷积编码 f i g u r e2 3 ( 2 ，1 ，2 ) c o n v o l u t i o n a lc o d e s 0 0 0 1 1 0 图2 a ( 2 ，l ，2 ) 卷积码状态图 f i g u r e2 4 ( 2 ，1 力c o n v o l u t i o n a lc o d e ss t a t em a p 卷积码有两种描述方式：状态图描述和网格图描述。 状态图如图2 4 所示。若电路处于s o 状态，当输入为0 时，输出为o o ，电路 仍处于s 0 状态，输入为l 时，输出为1 1 ，电路进入s l 状态；在电路处于s l 状态 下，输入为0 和1 时，输出分别为1 0 和0 1 ，电路分别进入s 2 和s 3 状态；电路处 于s 2 状态下，输入为0 和1 时，输出为l l 和0 0 ，电路分别转移到s o 和s l 状态： 7 北京交通大学硕士学位论文 电路处于s 3 状态下，输入为0 和1 时，输出为0 1 和1 0 ，电路状态非分别转移到 s 2 和自身s 3 。 0 0 o i 图2 5 卷积码的网格图 f i g u r e2 5c o n v o l u t i o n a lc o d e sg r i dm a p 用图2 5 所示的篱笆图可以表示数组的字码序列与状态图和时间的关系。该图 是( 2 ，1 ，2 ) 卷积码在l = 5 时的状态转移时间关系图。由节点和分支构成，共有l + m 个时间单位( l = 5 ，m r 2 ，l + m + 1 = 8 ) 。编码器从s 0 状态开始最后结束仍回到s 0 状态。开始的第0 和第1 时间单位，相应于编码器由s o 状态出发往各个状态进行， 最后两个时间单位，编码器的输入为两个0 ，最终使编码器由各个状态返回到最初 的s o 状态。 篱笆图的第一行各个节点都代表处于s o 状态，第二行各个节点代表s l 状态， 第三行和第四行的各个节点分别代表s 2 和s 3 状态。途中每个状态都有两个输入 和两个输出分支，在某一时间单位，离开某一状态的实线分支( 上面分支) 表示该时 间单位输入编码器的信息m = o ，而虚线分支表示输入信息m = l 。 若输入序列m 爿1 0 1 1 1 0 0 ) ，s o 状态接受信息l ，由状态图2 4 所示，输出码序 列1 1 ，进入状态s 1 ，接受信息0 ，输出码序列1 0 ，进入状态s 2 ，依次类推，最后 得出的输出码序列为c = ( 1 1 1 0 0 0 0 1 1 0 0 1 1 1 ) 。 2 3 维特比译码算法 维特比译码算法是一种针对卷积码而提出的最大似然译码算法。维特比译码 算法是基于卷积编码器的状态转移与时间的关系，求出码集所有码字中与接受序 列有最小度量的码字。在译码器中有一个与发送端相同的本地编码器，只不过这 个编码器能遍历所有可能的编码路径，而译码就是在每一时刻都将这些路径与接 收序列进行距离度量，并去掉那些度量值小的编码路径。所以，整个译码过程可 m 叭 无线通信介绍及典型算法分析 以用篱笆或网格图来表示，如图2 5 所示。篱笆图中每一状态都有两个输入和两个 输出分支。在某一个时间单位i ，离开每一状态的虚线分支( 下面分支) ，表示输入 接收段编码器中的信息子组m i - - - 1 ；而实线分支( 上面分支) 表示此时可输入至编码 器的信息子组m i = 0 。 发送端编码器送出的码序列c ，经过离散无记忆信道( d m c ) 传输后送入译码其 的是序列r = c + e ，e 是信道错误序列。译码器根据接受序列r ，按最大似然译码 准则力图找出编码器在篱笆图上所走过的路径，这个过程就是译码计算、寻找最 大似然函数 m a x l 0 9 6 尸( rc ，) j = 1 , 2 ，2 v ( 5 ) 的过程。对于b s c 信道而言，计算和寻找有最大度量的路径 m a x m ( rlc ，)，= 1 , 2 ，2 上一( 6 ) 汉明距离是指两个等长字符串之间的汉明距离是两个字符串对应位置的不同 字符的个数。例如，1 0 1 1 1 0 1 与1 0 0 1 0 0 1 之间的汉明距离是2 ，2 1 4 3 8 9 6 与2 2 3 3 7 9 6 之间的汉明距离是3 。 等价于寻找与r 有最小汉明距离的路径，即寻找 m i n d c r ，c j ) ，= 1 , 2 ，2 v( 7 ) 但是，如果不对路径进行适当取舍的话，上述译码方法是难以实现的。 维特比算法正式在解决上述困难中所引入的一种最大似然译码算法。并不是 在篱笆图上一次比较所有可能路径，而是接收一段，计算、比较一段，选择一段 最有可能的码段，从而达到整个码序列是一个有最大似然函数的序列。 下面以一个具体的译码过程为例，说明这种译码算法。以最简单的( 2 ，1 ，2 ) 卷积码为例，维特比译码步骤如下： 从1 - - m 开始，计算进入每一状态的所有长度为l 段分支的部分路径，计算部分 度量，对每一状态，挑选并存贮一条有最大度量的部分路径及其部分度量值，称 此路径为幸存保留路径。 l - - m + l ，计算分支度量值并于前一段幸存度量值相加，再进行累加比较选择 运算，产生新的近一条幸存保留路径，并将幸存路径及其度量值分别用两个存储 器存储下来，同时删除其他所有路径。 若i a o ) 0 c m p g t l 2 b i i ，b 1 0 ，b 0；t 8 = 0 , 8 a s ) m p y m 1 xl ，b 5 , a 4；c o p ym j 【a 2 】s u b s 1a 2 ，l ，a 2 ；d e c r e m e n tp r i m i n g i l ir a 2 】s t h d ia 1 2 ，+ a 6 + + ；s t o r en e w j 1 = a 0 j i a 1 】a d d s 2 2 ，b 0 , b 0；t 8 产( t o 1 ) i i a 0 】m p y m 21 , b 1 1 ，b 1 2；i f ( t s ) a 8 = b 8 0m p y m ii , a 1 0 ，a 1 2 ；c o p ya 0 s u b l 2 x a 7 ，b 5 ，b 1 0；a 8 = o l d 0 - m j 0l d h d 2 + 。卜m 9 ，b 5；l o a dm j = m 硼 s h l s 2a 4 , 2 ，b 1 4 ；仃 a ( 1 5 ：o ) ，则a ( 3 1 ：1 6 ) 放到* a r i 中，t r n 左移一位，放入0 ； 反之a 0 5 ：0 ) 放到* a r i 中，t r n 左移一位，放入1 。 3 4 指令系统 包括算术运算指令、逻辑运算指令、控制指令和l o a d s t o r e 指令。在算术运算 指令中，设计了专门的适用于无线通信算法的比较指令和双1 6 位配置指令等。 指令系统支持5 种寻址方式，依次为立即数寻址、绝对地址寻址、累加器寻 址，直接寻址、间接寻址。 在立即数寻址中，指令中包含特定的操作数，立即数按长度可以分为两类短 立即数和长立即数，前者的长度可以为3 ，5 ，8 ，9 位，后者长度固定为1 6 位， 立即数的长度同时也影响指令长度，前者是单字指令而后者是双字指令。 绝对地址寻址就是在指令中包含有所要寻址的存储单元的1 6 位地址，在绝对 地址寻址指令句法中，存储单元的1 6 位地址可以用其所在单元的地址标号或者1 6 位常数来表示。 2 0 基于算法的d s p 结构设计 累加器寻址就是利用累加器中的数值作为地址去访问程序存储器，只有两条 指令可以使用累加器寻址，用来进行程序存储器和数据存储器中的数据块转移。 间接寻址是将辅助寄存器数值作为数据存储器地址的一种寻址方式，内核包 含8 个辅助寄存器a r 0 - a r 7 ，通过辅助寄存器a r x 可访问数据存储空间中任何一 个数据存储单元，这种寻址方式相当于使用指针，而且在指针寻址的同时可以对 指针值进行灵活的更新。 3 5流水线及其控制 流水线( p i p l i n e ) 是一种能将多条指令重叠操作的处理机实现技术，其是当前高 性能处理机设计中的最为差键的技术，流水线处理机将一条指令的指令分成若干 个步骤，或称为级( s t a g e s ) ，每一级在一个时钟周期内完成，通过流水线，每一条 指令的执行都可以分散在各级的不同时钟周期完成，而且每一个时钟周期都可以 取得一条指令，大大提高了处理器得性能，如果处理机得流水线是m 级，那么处 理级在性能上会提高到非流水处理时的m 倍，当然m 不可能无限制地增加，因为 流水线处理机性能提高的代价是处理机结构复杂度地增加【1 9 1 。 本设计有6 级流水，基本上是从取指、译码、取操作数和执行这样的架构演 化而来，由于内核操作的对象是大块的数据，这些操作数不可放入寄存器堆栈才 进行处理。为了支配庞大的数据寻址空间和程序寻址空间以及多数据总线访问， 内核在对存储器访问的两个流水线的级进行了扩展，以免处理器性能会被对存储 器的带宽和复杂的访问限制，其中取指级被扩展成预取指和取指两级，取操作数 扩展成寻址和读数两级，这样内核的流水线是6 级，依次为预取指p r e f e t c h ，取指 f e t c h 、寻址a c c e s s 、读数r e a d 、执行e x e c u t e 。 3 5 1 流水线的操作 在任何一个时钟周期内，可以有1 到6 条不同的指令在同时工作，每条指令 工作在不同级的流水线上。流水线的前两级是预取指和取指，通过这两级流水可 以从程序存储器取得指令，其中预取指是将程序计数器p c 值写入程序存储器地址 总线寄存器，取指令是将从程序存储器中指令写入程序存储器数据总线寄存器第 三级是译码，就是将程序存储器数据总线寄存器中的数据写入指令寄存器并进行 译码。第四级是寻址，就是根据指令译码结果，如果有需要就所需操作数的地址 写入数据存储器地址总线寄存器。第五级是读数，就是从数据总线寄存器取得操 作数，如果有需要将需要写回的地址写e 地址总线寄存器。第六级是执行，就是 2 i 北京交通大学硕士学位论文 对取得的操作数计算，计算的结果可以送到累加器或写入e 数据总线寄存器后传 到数据存储器。如下所示： 取指令 预取指取指 译码访问读数执行 执行读单操作数指令处理 预取指取指 译码 访问 读数执行 执行读双操作数指令 预取指取指 译码访问读数执行 i 写d a b 读d b 和d a b 和c b 执行写卑保作藏瑁令 预取指取指 译码 访问 读数执行 执行写双操作数指令 预取指取指 译码访问读数执行 预取指取指 译码 访问 读数执行 单操作数读和单操作数写指令 3 5 2 流水冲突 在流水线处理机的设计中存在三个著名的问题，其们是结构相关问题( s t r u c t u r e h a z a r d ) 、数据相关问题( d d t ah 犯a r d ) 和转移相关问题( b m n c hh a z a r d ) 2 0 ，结构相关问 题是指由于硬件资源不充足而导致流水线不通畅，数据相关问题是指一条指令的 操作数跟前面的指令相关，也就是说由于流水的原因，单元指令的操作在需要用 基于算法的d s p 结构设计 来处理是还没有被上一条指令更新。转移相关的问题是指由于是流水操作，在转 移发生前，若千条在转移指令后的指令已经被取到流水线处理机中，因此转移相 关有时也被称为控制相关问题( c o n t r o lh a z a r d ) 。 以上的问题在内核的设计中都必须考虑，首先内核是一种超级h a r v a r d 结构， 有4 条数据总线( 其中一条是程序数据总线) 和4 条地址总线，也就是s i m d 结构， 因此就意味这在单个时钟周期可能同时有4 个存储器访问，当这四个访问中有若 干个访问发生的同一个物理存储器b l o c k ，而且该b l o c k 不能同时相应这些访问就 回产生冲突，t ic 5 4 x 系列d s p 是通过一个片上的外设来解决这个问题的，这个 外设可以进行软件编程产生等待状态，一旦发生冲突，会将这个流水停下来等待 存储器访问结束。因此在这个问题可以转化为如何在外部信号的控制下如何将流 水线停下来怔“。 在结构上的相关问题表现在两方面，一个是存储器的访问冲突，一个是存储 器地址映像寄存器的访问冲突。首先内核是一种超级h a r v a r d 结构，有4 条数据总 线( 其中一条是程序数据总线) 和4 条地址总线，也就是s i m d 结构，因此就意味这 在单个时钟周期可能同时有4 个存储器访问，当这四个访问中有若干个访问发生 的同一个物理存储器b l o c k ，而且该b l o c k 不能同时相应这些访问就回产生冲突。 内核使用的数据存储器有两种，一种是双寻址存储器器d a r a m ，一种是单寻址 存储器。对前者来说d a r a m 允许处理器在单个时钟周期对其访问两次，在单周 期内允许同时访问d a r a m 不同的块，不会带来时序上的冲突，允许处在流水线 不同级的2 条指令同时访问一个d a r a m 块也不会造成时序上的冲突，同一条指 令可以同时访问不同的两个存储器块也不会产生时序冲突。对后者来数处理机在 当时钟周期指令访问一个存储器块一次，这些存储器包括单口存储器可只读存储 器。这里可以参考t i 的t m s 3 2 0 c 5 4 x 系列d s e 通过一个片上的外设来解决这个问 题的，这个外设可以进行软件编程产生等待状态，一旦发生冲突，会将这个流水 停下来等待存储器访问结束。因此在这个问题上执行考虑如何在外部上如何将流 水线停下来。 其次，存储器地址映像寄存器m m r 在访问是也有一些限制，例如在数据地 址产生单元的m m r 中【1 9 1 ，a r x 、b k 和s p 的更新时，连续的两条指令前一条同 过存储类型指令、后一条通过r e a ds t a g e 同时访问地址产生单元寄存器时会产生 冲突。 在内核的流水线结构中，数据相关问题体现在两个部分，一个是存储器操作 数的读写相关问题，一个是存储器地址映像寄存器w a r 的访问问题，对前者来说， 由于是流水处理，如果后一条指令所需的存储器操作数是由前一条更新，那么就 会出现读后写的问题，这就是数据相关问题，这个问题通过编译器处理或者在手 北京交通大学硕士学位论文 工编程是解决这个问题，w a r 的访问冲突跟流水线结构相关，下表列出了m m r 访问的流水冲突 表3 3m m r 访问的流水线冲突 t a b l e3 3m m rv i s i tp i p e l i n ec o n f l i c t m m r 产生流水冲突的条件 f x 和b k前一条这里对a r x 或b k 进行写攮作。下一条指寺同十i l 助寄 存量进行同接寻址或采用b k 进行循环寻址 堆拽指针s p当一豢指令写卵下蠡指令采用s p 作为直接寻址的位移量赭 下一条是堆栈量作指令 簟时寄存一豢指令写t 下一条指令使用1 做移位囊位捡 帆杏寄存量访盯曹一条指令对s t 中的某一字姓行更新下一条指令麓蔓使用该 字段用作寻址和运算控制 块循环寄存量条描专写b r c 寄存鼍，下一条指令是i l t , r l g d 覃加量当一条撸专直接政壹了个膏存量下一矧盼试田将箕作为地址 快寄存曩读出 对转移相关问题的处理有三种技术，一种是暂停流水线，一种是假定转移不 发生最后是延迟转移，在内核的设计中，通过对转移指令添加延迟选项是流水线 的控制自动进行，也就是第三种延迟转移技术，在转移指令后的两条指令会被完 整执行，根据转移指令将转移指令后的时钟周期设置成f l u s hc y c l e 或d u m m y c y c l e 可以继续取指但不译码或按需要停止取指，通过对上述3 中技术解决了转移 相关的问题，同时也有效底提高了转移操作底效率。 3 6所设d s p 计结构的维特比算法实现 本文设计的d s p 结构实现维特比算法的数据流图如图3 6 所示。执行过程如 表3 4 所示，此结构能在4 个指令周期内完成一次维特比译码算法蝶型运算，与表 3 2 对比可知，相对于t ic 6 x 、l u c e n td s p l 6 2 1 0 和f r e e s c a l es t a r c o r es c l 4 0 三种 d s p ，尽管结构简单，运算单元少，但是由于采用了易于实现算法的结构，维特比 算法执行速度并不慢。 基于算法的d s p 结构设计 图3 6 执行维特比算法的数据通路 f i g u r e3 6d a t ap a t ho f v i t e r b ia l g o r i t h mi m p l e m e n t a t i o n 表3 4 维特比算法执行过程 t a b l e3 5 t h e i m p l e m e n t a t i o no f t h e v i t e r b i a l g o r i t h m 指令备注 d a d s t a r 5 a d s a d t * a r 5 b c o m s a ，* a r c + c o m sb a r 3 + ； a l u 执行( 2 胪m 和( 2 j + 1 ) - m ，结果存入累加器a a l u 执行( 2 * j ) - m 和( 2 j + l 卜m t 结果存入累加器b c s s u 比较累加器a 的高1 6 位和低1 6 位数据，并将 较大的数存入t r n c s s u 比较累加器b 的高1 6 位和低1 6 位数据，并将 较大的数存入t r n 北京交通大学硕士学位论文 4d s p 功能模块的设计 4 1