（通信与信息系统专业论文）高速viterbi译码器的研究与实现.pdf

啥尔滨工程大学颈士学位论文 摘要 随麓纠错编码理论研究的不断涤入，纠错码的实际应用越来越广泛。卷 积冯作为其中璧要的一种，已被大多数邋信系统所采用，并应雳在各种场合。 ( 2 ，l ，7 ) 卷积码是一种短约柬长度最佳码，编、译码器易于实现，且具有 较强的纠错能力。 本文研究了由( 2 ，1 ，7 ) 卷积码传为母码产生的3 4 删余( p u n c t u r e d ) 卷积码的高速编码及其软判决高速v i t e r b i 译码的理论和实现问题。 首先分绍了v i t e r b i 译码算法的薪逃鼹，在越基础上提出了一秘适合藤速 处理的新结构 然后，用v h d l 语言设计了( 2 ，1 ，7 ) 卷积码的编码器和 v i t e r b i 译码器，在悲基破上设诗了裹遥3 4 测余卷积娼的绽磁器和v i t e r b i 译码器，并下载到x i l i n x 公司的v i r t e x - i i 系列的f p g a ( 型号 x c 2 v 2 0 0 0 6 b 9 5 7 5 ) 器黪上，经避戆枣佬真窝实测，单路3 4 瓣余卷积霹教 v i t e r b i 译码器译码速度接近6 0 m b i t s ，四路并行处理可达到2 2 0 m b i t s ；最后 对( 2 ，l ，7 ) 卷鬏玛豹v i t e r b i 译羁嚣瓣瞧l 遴行了篱攀熬测试，著对涎试 结果作了分析。 关键词：删余卷积码；v i t e r b i 译码；v h d l f p g a 哈尔滨工程大学硕士学位论文 a b s t r a c t a st h er e s e a r c ho fe r r o r c o r r e c t c o d i n gt h e o r yd e v e l o p i n gd e e p l y m o r ea n dm o r e ，t h ea p p l i c a t i o n so fe r r o r c o r r e c t i n gc o d e sh a v eb e e n u s e dm o r ew i d e l y t h ec o n v o l u t i o o a c o d e s ，a st h ei m p o r t a n to n eo f e r r o r c o r r e c t i n gc o d e s ，a r eu s e db ym o s t c o m m u n i c a t i o ns y s t e m si n v a r i o u ss i t u a t i o n s ( 2 ，1 ，7 ) c o n v o l u t i o n a lc o d e si sao p t i m u mc o d ew h i c h h a st h es h o r tc o n s t r a i n tl e n g t h i tc a nb ee n c o d e do rd e c o d e de a s i l y a n dt h i sc o d eh a sag o o de r r o r c o r r e c t i n gp e r f o r m a n c e t h i s p a p e rs t u d y t h e t h e o r ya n di m p l e m e n t a t i o no fh i g h s p e e d e n c o d e ra n ds o f t d e c i s i o nv i t e r b id e c o d e r o f3 4 p u n c t u r e d c o n v o l u t i o n a lc o d e sd e r i v e df r o m ( 2 ，1 ，7 ) c o n v o l u t i o n a lc o d e s f i r s t l y ，t h e n e w d e v e l o p m e n t o f h i g h s p e e d v i t e r b i d e c o d i n g a l g o r i t h m s i s i n t r o d u c e d ，a n d an e wa r c h i t e c t u r ef o r h i g h s p e e d p r o c e s s i n gi sp r o p o s e db a s e do ni t t h e n ，w ed e s i g nt h ee n c o d e ra n d v i t e r b id e c o d e ro f ( 2 ，1 ，7 ) c o n v 0 1 u t i o n a lc e d eb yp r o g r a m m i n gw i t hv h d l a n g u a g e t h ee n c o d e ra n dv i t e r b id e c o d e ro fh i g h s p e e d3 4p u n c t u r e d c o d e sa r ea c h i e v e db a s eo nt h ea b o v ed e s i g n s t h ep r o g r a m sh a v eb e e n c o n f i g u r e di n t ot h e v i r t e x i is e r i e sf p g a ( x c 2 v 2 0 0 0 6 b 9 5 7 5 ) o fx i l i n x i n c t i m i n gs i m u l a t i o na n dp r a c t i c a l t e s ti n d i c a t e st h es p e e do fa s i n g l e d e c o d e ro f3 4 p u n c t u r e d c o n v o l u t i o n a lc o d ec a n a p p r o a c h 6 0 m b i t s ，t h es p e e do ff o u rd e c o d e r sw o r k i n g i np a r a l l e lm o d ec a nr e a c h 2 2 0 m b i t s f i n a ll y ，w et e s tt h ep e r f o r m a n c eo ft h e ( 2 ，l ，7 ) c o n v 0 1 u t i o n a l c o d es i m p l ya n da n a l y s et h et e s tr e s u l t k e y w o r d s ：p u n c t u r e dc o n v o l u t i o n a lc o d e s ，v i t e r b id e c o d i n g ，v h d l ，f p g a 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) 燮 日期：加。牛年2 月j7 日 哙象凑王程大学联士学像论文 第1 章绪论 1 。1 前向纠错编码技术在卫星通信中的应用 纠错编译粥设备是数字卫疆通信卷统的重要组成部分，它可以显著改善 传输信道误码住能。裉据香农编码定理，当且仅当信怠传输速率小于称之为 信道容爨的最大速率时，存在麓种8 达到可纛遽信的编码。卫星信邋可视 为离散焉记忆商斯信道，噪声分布是加性宽频带白高斯噪声，另外，卫星转 发器是功率受隈，丽带宽较不受限。因此，采耀亳增蕊的纠错编码来改善通 信效率是必不可少的。 使孀翦向纠绩编鹞豹卫星数攥逶馈系统一般缝成妻鞋霾1 。1 掰承。 鬻1 。l 翌基数据通信系统组成圈 较理想的卫星信道模型具脊以下两条原理性的特性：噪声分布是加性 宽频带臼商辩磲声。传输延迟较大，同步逮球翌星约是2 7 0 m s 。勇井，卫 星转发器是功率受限、而带宽较不受限，有足够的带宽可用来扩展。因此可 以采用前向纠镄编码按术。采溺纠错编码技术，可以衣特定的镲嗓眈玩o 下，降低误码率，而在规定的谈码率下，能降低所需的信噪比，这对卫星通 信而言，节省了最宝贵的功率资源。因此入们认为在卫星信道利用前向纠错 码技术，是提您通信质爨的一种有效方法，可以取褥明屡的编褥增益，扶丽 充分利用卫星转发器容缀，而系统的设备量相对增加的并不多。 哈尔滨工程大学硕士学蹙论文 卫屡信道可以视为凭记忆信道，因此一般采用纠随机错误的纠错码。目 蔫应蘑予卫星避信麴裁怒纠错磁主要有：醛鹃、卷狡璐、b c h 分组鹈。为了 说明f e c ( f o r w a r de r r o rc o r r e c t i o n ) 技术猩卫星通信系统中的应用，我 们到攀了孬个熬型豹卫星通信系统i n t e 聪艘( 国际电信翌星系统) 和 i n m a r s a t ( 国际海事卫尾系统) 所用的f e c 。 表1 1 瓢举了f e c 在i n t e l s a t 中的应用。在s c p c ( s i n g l ec h a n n e l p e r c a r r i e r ) 系统中采用( 4 ，3 ) 自正交纠两个错误的卷积码，用于传输 4 8 k b i t s 数据。除此之矫，还采用( 1 2 0 ，1 1 2 ) 修正b c h 码，用于4 8 k b i t s 话音基落传输。在t d m a d s i ( 数字语音援空) 中采用修正的( 1 2 8 ，1 1 2 ) b c h 码和( 2 4 ，1 2 ) 扩展g o l a y 码。在i b s ( i n t e l s a tb u s i n e s ss e r v i c e ) 系统 中采用( 2 ，1 ，7 ) 或删余3 4 漆积码帮v i t e r b i 软判决译码。 表1 1f e c 猩i n t e l s a t 系统中的应用 系统应用的f e c 码 s c p c 3 4 鑫正交筠 7 8 自正交码 ( 单路单载波) ( 1 2 0 ，1 1 2 ) 修正b c h 羁 t d 矾d s i ( 1 2 8 ，1 1 2 ) 修正的b c l f 码 ( 时分多娥数字语音插空) ( 2 4 ，1 2 ) 扩展的g o l a y 码 i b s ( 2 ，l ，7 ) 卷积码或剿余3 4 褥 ( 国际商业卫星) 积码和v i t e r b i 软判决译码 表1 2 列举了i n m a r s a t 系统所用的f e c 码。其标准a 采用了( 6 3 ，5 7 ) 帮( 6 3 ，3 9 ) b c i i 码用予检测魄特罐误，两( 2 ，l ，? ) 卷积码及测余3 4 卷 积码和v i t e r b i 软判决译码用于传输5 6 k b i t s 数据。标准b 采用了( 2 ，1 ， 7 ) 卷获褥鬟予9 6 k b i t s 约数攥，艇余3 4 卷积码弱予1 6 k b i t s 话鼹。 哈尔滨工程大学硕士学位论文 表1 2f e c 在i n m a r s a t 系统中的应用 系统应用的f e c 码 请求重传信道高速( 6 3 ，5 7 ) b c h 码 数传( 船一岸)( 6 3 ，3 9 ) b c h 码 标准a( 2 ，1 ，7 ) 卷积码v i t e r b i 软判决译码用于 传输5 6 k b i t s 数据 数字船舰地球站( 2 ，1 ，7 ) 卷积码或删余3 4 卷积码v i t e r b i 软 标准b判决译码用于传输9 6 k b i t s 数据和1 6 k b i t s 语音 随着卫星通信的发展和普及，以及业务量的增长，高速数传的需求日益 迫切。数据速率达1 2 0 m b i t s 的r s 译码器硬件已经实现。发展数据传输速率 高达2 g b i t s 的r s 译码器的计划已在实施中。而v i t e r b i 译码器的数据速率 已达2 5 0 i b i t s ，目前市场中实用的多为2 0 5 0 m b i t s 。 随着国内通信事业的发展，编译码技术也得到了越来越多的重视。高速 数据编译码技术不仅在新一代遥感卫星、星地、星际通信技术中有至关重要 的作用，对加速开发研制我国的高数据速率的卫星通信系统也具有深远的意 义，这项技术的研究也为将来卫星通信在信息高速公路中的应用提供了一项 重要技术手段。为此总装将“高速数据编译码技术”作为一项重要的研究课 题，中国电子科技集团第五十四研究所已将这项课题作为“十五”期间的预 研课题。 1 2 v i t e r b i 译码器的发展概况 卷积码是一种延时小，特别适用于以串行形式传输信息的纠错码。1 9 6 7 年，v i t e r b i 提出了一种译卷积码的最大似然译码算法，称作v i t e r b i 算法。 v i t e r b i 算法在译短约束长度的卷积码时性能最佳，低编码率时实现简单， 特别是对软判决译码器实现容易，能获得较高的编码增益，从而得到了广泛 哈尔滨丁程大学硕士学位论文 的应用，尤其是在卫星通信系统中。 国外从六十年代后期就开始研制卷积编码v i t e r b i 译码器，并在各种 通信系统中得到了广泛的应用。最早研究出卷积码的v i t e r b i 译码器是 l i n k a b i t 公司于1 9 7 1 年研制的l v 7 0 1 5 ，它是1 2 码率，k = 7 ，用了8 2 块集成 块，数据速率为l o o k b i t s ，用于地面与机载终端通信。进入八十年代后， 随着超大规模集成电路技术的发展，在单片芯片上集成低编码率v i t e r b i 译 码器已成为可能。表1 3 列出了国内外各种型号的v i t e r b i 译码器专用芯片 及主要参数。 表1 3 国内外v i t e r b i 译码器专用芯片及主要参数 发表公司编约数据编码工艺参考 日期码束速率增益 蛊 长( m b p s )( d b ) 度 1 9 7 9 2r o k w e l l1 237 0单片 1 9 8 1 1 2r o k w e l l1 253 74 3单片 1 9 8 7 5n i t1 272 05单片 1 9 8 7 3 1 2 785 1c m o sp m 为外部 三菱 3 4 4 1r a m 1 2 71 75 1c m o s 单片 1 9 8 6q u a l c o m m3 44 2 7 8 3 3 1 9 8 7 1h a r r i s 1 2 71 05 1c m o s 单片 1 2 72 05 1单片 1 9 8 9q u a l c o m m3 4 7 8 1 9 9 3 中国西南 1 2 7o 7 55 1c m o s单片 电子电信技 3 4 术研究所 4 哈尔滨工程大学硕士学位论文 从表中可知，这些产品大多限于低编码率低速率的译码器，目前，国外 已有上百兆的单芯片高编码率的v i t e r b i 译码器。而在国内，由于国内集成 电路技术和工艺水平有限，至今研制不出单片的高速高编码率的v i t e r b i 译 码器，这在一定程度上影响了卷积码、v i t e r b i 译码器在国内的应用和发展。 目前，国内外正在积极开展高速率、高编码增益、高编码率等性能更好 和大规模集成化的v i t e r b i 译码器的研究。 1 3 本文研究的主要任务 对卷积码的构成原理、编码原理、v i t e r b i 译码原理、码的性能做一些 探讨，并寻求在高速调制解调中v i t e r b i 译码的解决方法及性能分析。该论 文是针对“十五”预研课题“第二代t d r s s 地面系统及高速数据传输”中的 高速纠错处理提出的，目前国内和国外都没有能达到3 0 0 m b i t s 高速的 v i t e r b i 译码芯片。本文针对这种情况和实际的需要，主要从以下两方面开 展研究： 一方面在对卷积码、v i t e r b i 译码理论研究的基础上，进一步开展对新 的v i t e r b j 译码算法的研究。主要探讨了能提高译码速度的v i t e r b i 译码算 法的新进展，并提出了一种具体实现方案。 另一方面，借鉴国外已采用的将低速率的编译码器并行处理以得到高速 率的编译码器的思想，利用f p g a 实现以( 2 ，i ，7 ) 为母码的删余3 4 卷积 码，信道传输速率为2 2 0 m b i t s 的编译码器。 哈尔滨工程大学硕士学位论文 第2 章卷积编码与v i t e r b i 译码算法 2 1 卷积编码 利用纠错码进行信道编码的基本思想是在被传输的信息中附加一些监督 码元，并在两者之间建立某种相关性，使信息内部具有更强的规律性，当这 种关系由于噪声等影响被破坏时，仍能根据信息原有的内在规律和相关性来 发现错误，甚至纠正错误，恢复原来的信息。这种检错和纠错能力是利用信 息量的冗余度来换取的，这就要求通信信道有足够的带宽资源。按照对信息 元处理方法的不同，纠错码可以分为分组码和卷积码两大类。分组码是把信 源输出的信息序列，以k 个码元划分为一段，通过编码器把这段k 个信息元 按一定规则产生r 个校验( 监督) 元，输出长为n = k + r 的一个码组。因此每 一码组的校验元仅与本组的信息元有关，而与别组无关。 卷积码是1 9 5 5 年由爱里斯( e 1 i a s ) 提出的。它也是把k 个信息比特编 成n 个比特，但k 和n 通常很小，特别适宜于以串行形式传输信息，延时小。 与分组码不同，卷积编码器有记忆性，且在任意给定时间单元处，编码器的 n 个输出不仅与此时间单元的k 个输入信息有关，而且也与前( k 一1 ) 个输入 组有关，编码过程中相互关联的码元为k * n 个。卷积码的纠错能力随着k 的 增加而增大，而差错率随着k 的增加而指数下降。在同样的码率和设备复杂 性条件下，无论从理论上还是从实际上均已证明卷积码的性能优于分组码， 且实现最佳和准最佳译码也比分组码容易。所以，从信道编码定理看，卷积 码是一种非常有前途的，能达到信道编码定理所提出的码类。但由于卷积码 各组之间相互有关，因此至今尚未找到象分析分组码那样有效的数学工具来 分析卷积码，以致性能分析比较困难。目前，大都借助计算机来搜索好码。 卷积码编码器的一般形式如图2 1 所示。在某一时刻i ，输入到编码器的 是由k 个信息元组成的信息组m ；，相应地输出序列是由n 个码元组成的子码 6 哈尔滨工程大学硕士学位论文 c 。若输入的信息序列i n ，i l l 。，i l l ，是一个半无限长序列，则由卷积码 编码器输出的序列，也是一个由各子码c 。，c l ”，c i ，”组成的半无限长序列， 称此序列为卷积码的一个码序列或一个码字。用这种卷积码编码器输出的每 一子码中的校验元，是此时刻输入的信息元与前( k 一1 ) 子码中信息元的模2 和，它们是线性关系。 卷积码 编码器 1 2 图2 1 卷积码编码器 卷积码通常用( n ，k ，k ) 表示。k 为编码约束长度，说明编码过程中互相 约束的码段个数。k n = r 同分组码一样称为卷积码的码率。它们是衡量卷积 码的重要参数。 2 2v i t e r bi 译码 卷积码的译码方式有三种：( 1 ) 1 9 6 3 年由梅西( m a s s e y ) 提出的门限译 码，这是一种码代数结构的代数译码，类似于分组码中的大数逻辑译码；( 2 ) 1 9 6 1 年由沃曾克拉夫特( w o z e n c r a f t ) 提出，1 9 6 3 年由费诺( f a n o ) 改进的 序列译码，这是基于码树图结构上的一种准最佳的概率译码；( 3 ) 1 9 6 7 年由 维特比( v i t e r b i ) 提出的v i t e r b i 算法，这是基于码的网( t r e l l i s ) 图基 础上的一种最大似然译码算法，是一种最佳的概率译码方法。维特比译码具 有最佳性能，但硬件实现复杂；门限译码性能最差，但硬件简单：序列译码 在性能和硬件方面介于维特比译码和门限译码之间。 2 2 1v i t e r b i 译码算法的基本原理 哈尔滨工程大学硕士学位论文 一软判决的概念 接收时是一个模拟量，因此在送入译码器之前应进行量化处理。最简单 的量化是二电平量化( 即量化电平o = 2 ) ，也就是硬判决，当接收信号盖) 0 时，判为“0 ”，否则判为“1 ”。这种量化太粗糙，将丢失许多有用的信息， 以至于造成毛0 大约2 d b 的损失。为了避免二电平量化的这种损失，应当 使量化电平数0 2 ，也就是软判决。q 越大，量化越精细，损失也就越小，但 同时译码器也就会越复杂。当量化电平超过8 时，编码增益也趋于饱和，因 而量化电平通常取o - 8 。 软判决v i t e r b i 译码器的结构并不比硬判决的复杂很多，但可以使性能 提高23 d b 。实现无限电平量化比较困难，而采用8 电平软判决译码较无限 电平软判决译码，编码增益损失只有0 2 d b 。目前，实用中的v i t e r b i 译码 器几乎都是软判决，并且一般都采用8 电平均匀量化，其性能基本达到了最 大似然译码的性能。 二最大似然译码原理 1 9 6 7 年，v i t e r b i 提出了一种译卷积码的最大似然译码算法，称作 v i t e r b i 算法。v i t e r b i 算法可以看作是对有限状态马尔科夫链在无记忆噪声 中的状态序列估计的一种动态规划方法。 由于v i t e r b i 译码是针对卷积码的译码而提出的一种概率译码算法，它 建立在最大似然译码的基础上，因此下面首先讲述最大似然译码的基本原理。 在一个编译码系统中，如图2 2 所示。 c 信 图2 2 编译码系统模型 输入信息序列m 被编码为序列c ，假设c 序列经过有噪声的无记t t k 4 言道_ 传送给译码器。译码器根据一套译码规则，由接收序列r 给出与发送的信息 序列m 最接近的估值序列衍。由于m 与码字c 之间存在一一对应关系，所以 这等价于译码器根据r 产生一个c 的估值序列0 。即当且仅当0 ：c 时， m = m ，这时译码器正确译码。如果译码器输出的0 c ，则译码器产生了 错误译码。 当给定接收序列r 时，译码器的条件译码错误概率定义为： p o v 月) = p 忙c 月) ( 2 1 ) 所以译码器的错误译码概率： 最= 尸( r ) p ( 吲五) ( 2 2 ) 式中p 伍) 是接收r 序列的概率，它与译码算法无关。所以译码错误概率 最小的最佳译码规则是使 i n i n b = m i n e ( r ) e ( s r ) ( 2 3 ) 这等价于对所有的r 使 m i n p ej m j n p ( e r ) = m i n p 忙咖) ( 2 4 ) 或表示成： m i n p ( c 咖) = m a x p p = m ) ( 2 5 ) 因此，如果译码器对输入的r ，能在2 “个码字中选择一个使p b = c 肚) 最大的码序列c m = 1 , 2 ，2 “) ，最大的码字c ，作为c 的估值序列0 ，则 这种译码规则一定使译码器输出错误概率最小，称这种译码规则为最大后验 概率译码。 由贝叶斯公式 p ( c 妒掣 可知，若发端发送每个码字的概率p 瞄) 均相同，且由于p 忸) 与译码方 法无关，所以 m a x p ( c _ | 太) jm a x p ( r c f ) ( 2 6 ) 9 p ( r c ，) ：e “t 0 , 一死n o ) e 吨吲2 慨l = ) e - ”引。“j ：6 面y 。一挣，“( 2 - 7 ) 由最大似然译码可知，译码器选择一个有最大似然函数p ( r c ，) 的码字 c ，作为输出，从上式看这等效于： 定义 月 2 m a x p ( r c ，) jr a i n “一)，= 1 ，2 ，2 “ ( 2 8 ) i = l d 。= 也一) 2 为接收序列r 与码字c ，之间的欧氏距离( e u c l i d e a nd i s t a n c e ) 。若c ，与胄之 间的欧氏距离最小，则译码器把r 译为c 。称这种译码器为欧氏译码器或最 小欧氏译码器。由此可知，最大似然译码也就等价于最小欧氏距离译码。 对于卷积码的最大似然译码，译码的任务是在树状图或网格图中选择一 条路径，使相应的译码序列与接收到的序列之间的距离最小，通常把可能的 译码序列与接收序列之间的距离称为量度。 v i t e r b i 译码分硬判决v i t e r b i 译码和软判决v i t e r b i 译码，它们之间 唯一不同之处在于支路量度的计算方法。硬判决v i t e r b i 译码是以序列之间 的汉明距离作为量度，适用于二进制对称信道( b s c ) ；而软判决v i t e r b i 译 码则是将信道输出的信号进行q ( 2 ) 电平量化，然后再进行v i t e r b i 译码， 这样充分利用了信道输出信号的信息，提高了译码的可靠性，是一种适用于 离散无记忆信道( d m c ) 的译码方法。通常，译码器利用附加的软判决信息进 行软判决v i t e r b i 译码时比硬判决v i t e r b i 译码能得到额外的2 3 d b 软判决 增益，因此目前实用中的v i t e r b i 译码器几乎均采用软判诀v i t e r b i 译码。 三v i t e r b i 译码算法 哈尔滨工程大学硕士学位论文 基于格图搜索的译码是实现最大似然软判决的重要方法和途径。用格图 描述时，由于路径的汇聚消除了树状图中的多余度，译码过程中只需考虑整 个路径集合中那些使似然函数最大的路径。如果在某一点上发现某条路径已 不可能获得最大对数似然函数，就放弃这条路径，然后在剩下的“幸存”路 径中重新选择路径，这样一直进行到最后第l 级( l 为发送序列c 的长度) 。 由于这种方法较早地丢弃了那些不可能的路径，从而减轻了译码的工作量， v i t e r b i 译码正是基于这种想法。 对于( n ，k ，k ) 卷积码，其网格图中共有2 ( k - d 种状态，每个节点( 即 每个状态) 有2 2 条支路引入也有2 条支路引出。为简便起见，讨论k = l 的 情形，从全0 状态为起始点开始讨论。由网格图的前k 一1 条连续支路构成的 路径互不相交，即最初2 “1 条路径各不相同，当接收到第k 条支路时，每条 路径都有2 条支路延伸到第k 级上，而第k 级上的每两条支路又都汇聚在一 个节点上。在v i t e r b i 译码算法中，把汇聚在每个节点上的两条路径的对数 似然函数累加值进行比较，然后把具有较大对数似然函数累加值的路径保存 下来，而丢弃另一条路径，经挑选后第k 级只留下2 “1 条幸存路径，选出的 路径同它们的对数似然函数累加值一起被存储起来。由于每个节点引出两条 支路，因此以后各级中路径的延伸都增大一倍，但比较它们的似然函数累加 值后，丢弃一半，结果留存下来的路径总数保持常数。由此可见，上述译码 过程中的基本操作是“加一比一选”( a d d c o m p a r e s e l e c t ，a c s ) ，即每级求 出对数似然函数的累加值，然后两两比较并作出选择。有时会出现两条路径 的对数似然函数累加值相等的情形，在这种情况下可以任意选择其中一条作 为“幸存”路径。 编码器从全零状态出发，晟后又回到全零状态时所输出的码序列，称为 结尾卷积码。因此，当序列发送完毕后，要在网格图的终结处加上k - 1 个己 知的信息( 即k - 1 个己知支路) 作为结束信息。在结束信息到来时，由于每 一状态中只有与已知发送信息相符的那条支路被延伸，因而在每级比较后， 幸存路径减少一半。因此，在接收到k - 1 个己知信息后，在整个网格图中就 哈尔滨工程大学硕士学位论文 只有唯一的一条幸存路径保留下来，这就是译码所得的路径。也就是说，在 己知接收到的序列的情况下，这条译码路径和发送序列是最相似的。 由上述可见，v i t e r b i 译码过程并不复杂，译码器的运行是前向的、无 反馈的。它接收一段，计算一段，选择一段最可能的码段( 分支) ，从而达到 整个码序列是一个有最大似然函数的序列。v i t e r b i 算法的每一级的计算复 杂度相同，因此它总的计算复杂度和存储量与传输序列长度l 成j 下比，传输 序列很长时，判决需要的长延时和相当大的存储量是我们无法承受的。因些， 实际应用中采用截短v i t e r b i 算法，即不需要接收到所有序列才进行判决， 当译码器接收并处理完固定t ( t d ，则在计算m 步变换 矩阵。时，只要计算其中的一列就够了，无需计算所有仃列。这正是字层 和算法层并行结构相结合以后可以推导出更为有效的并行v i t e r b i 译码器实 现结构的基础所在。 哙尔滨王程大学联士学位论文 3 。4 本章小结 本鬻介绍了实现高速v i t e r b i 译码器的新进展。首先介绍了减少硬件规 模和功率消耗，提高v i t e r b i 译码器速率的s s t 垄v i t e r b i 译粥方案；接下 来针对寻迹速度较高难以实现的问题，介绍了分段寻迹译码法；最后介绍了 在v i t e r b i 译粥算法中弓 入额外并行结构来提高译码速率的方法，描述了在 v i t e r b i 译码算法的不同层次上( 包括比特层、字层和算法层) 引入额外并 行结构，采用这嫂额外并行结构可以使专用v l s i 实现的v i t e r b i 译码器最高 译码速率成倍增搬。 哈尔滨工程大学硕+ 学位论文 第4 章高速卷积码编码器和v i t e r b i 译码器的实现 在国内，由于集成电路工艺水平所限，至今研制不出单片高速卷积码 v i t e r b i 译码器。随着国内卫星通信的发展和普及，以及业务量的增加，人 们更加追求高速率高可靠性数传。这就对编、译码器的速率提出了更高的要 求。目前，已提出了在数传速率为3 0 0 f o i t s 的卫星通信系统中应用卷积码 编、译码器的技术要求。显然，国内的v i t e r b i 译码器研制技术还不能满足 需要。 i n t e li d r 曾采用三个1 5 m b i t s 的3 4 卷积码编码器、软判决的v i t e r b i 译码器并行工作，使译码速率可达4 5 m o i t s 。还有l i n k b i t 公司的l v 7 0 5 7 中的v i t e r b i 译码就是5 个l v 7 0 1 7 ( i 0m b i t s ) v i t e r b i 译码器并行工作构 成5 0m b i t s 的卷积码v i t e r b i 译码器。 本章就是基于这种利用低速率的v i t e r b i 译码器并行联接构成高速率译 码器的思想，来实现信道传输速率为2 2 0 m i o i t s 的卷积码编码器和v i t e r b i 译码器。 4 1 基于v h d l 的卷积码编码器和v i t e r bi 译码器设计 在设计f e c 系统时，最主要的是确定选用何种类型的码，决定码的纠错 能力及交错码的交错度。选择的出发点是依据用户对误码率的要求。对于带 宽有限和功率受限的信道，选择原则相同，方法上有所区别。 在我们的课题中选择了已被国际通信卫星组织( i n t e l s a t ) 制订为i d r 和i b s 业务标准的( 2 ，l ，7 ) 卷积码及其增信删余形成的码率为3 4 的删余 卷积码。这是一个透明码，最小自由距离d ，= 1 0 ，b 。= 1 ，b ，是( 2 ，i ，7 ) 卷积码码字中，所有重量为d ，码字( 路径) 的非零信息位的总数。已经验证， 啥尔滨蔓程大学鞭士学撼论文 这是一个能使v i t e r b i 译码器输出的误码率达剿最小、腹能克服相位误蓑( 带 差分编译码器) 麓最僚羁。 下丽介绍用v h d l 语言实现的( 2 ，i ，7 ) 卷积码编码器和v i t e r b i 译码 器。 4 1 ( 2 ，1 ，7 ) 卷歉码编碣器的实现 ( 2 ，l ，7 ) 卷积码是c s s d s 的一种捧荐标准，霜被各国广泛用于卫星遥测信 道。这种码的约束长度为k = 7 ，码攀为r = ：2 ，一路输入，髓路编码输出， 生成式为：g 1 = 1 7 1 。，g 2 = 1 3 3 8 。因为约束长度为7 ，它的篱笆圈上每到最多 有2 7 一= 6 4 个状态，它的自由距离d ，= 1 0 。糨g ，g 2 写成多项式形式即 为： 媛国 = 1 + d + d 2 + d 3 + d 6 ( 4 - 1 ) g ，佃) = 1 十d 2 + d 3 + d 5 十d 6 ( 4 2 ) 缀码器示爨图如豳4 。1 。 鞫4 1 ( 2 ，1 ，7 ) 卷积礤编码嚣框图 从七位移位寄存器的第一、二、三、四、七位各引出一抽头，然殿进行 模2 帮构成第一路i ( r p g i ) 输出，舅一路q ( & p g 2 ) 为第一、三、隧、六、 七的模2 和，输入数据在时钟的作用下进入移位寄存器，每一节拍一比特输 入、两比特并行输出。 哈尔滨上程大学硕士学位论文 其设计模块框图如图4 2 所示。 ( 2 ，1 ，7 ) 卷积码c o d e ( 1 ：0 ) 编码器模块 图4 2 ( 2 ，1 ，7 ) 卷积码模块框图 卷积编码器包括时钟输入信号c l k ，输入使能信号c e ，异步复位信号c l r ， 数据输入信号d a t ，编码输出信号c o d e ( 1 ：0 ) 。用硬件语言v h d l 设计的( 2 ， 1 ，7 ) 卷积码编码器在m o d e l s i m 仿真环境生成的后仿真波形如图4 3 所示。 图4 3 编码器后仿真波形图 4 1 2 ( 2 1 ，7 ) 卷积码v i t e r b i 译码器的实现 v i t e r b i 译码器由三个基本单元构成，如图4 4 所示。利用接收到的数 据计算分支量度的分支量度单元( b m u ) ；递推地计算幸存路径量度的“加一 比一选”单元( a c s u ) ；利用幸存路径进行判决的幸存路径存储单元( s m u ) 。 图4 4v i t e r b i 译码器框图 耋 哈尔滨_ l 程大学硕士学位论文 一b m u 单元的实现 符号i ，q 输入到b m u ，b m u 产生分支量度送到a c s u 。在我们方案中，采 用3 比特软判决，这样，i ，q 符号用3 比特来表示。使用的分支量度见下表 表4 1 ： 表4 1 量化分支度量表 量化编码 0 0 00 0 10 1 00 1 l1 0 01 0 11 1 01 1 1 符号量度 01234567 分支量度计算公式： ( 1 ) 在非删除比特时，按下式计算： b m o o = r l + r 2b m o i = r l + ( 7 - r 2 ) b m i o = ( 7 - r 1 ) + r 2 b m l1 = ( 7 一r 1 ) + ( 7 - r 2 ) ( 2 ) 在删除比特时，则按下式计算： b m o x = r 1b m x l = 7 一r 2 b m l x = 7 - r 1b m x o = r 2 r 1 ，r 2 分别表示接收到的量化编码，分别用3 位二进制数表示。 分支量度的计算可用r o m 实现，也可用逻辑电路完成。在我们的实现中 采用了r o m 实现b m u 单元。这是因为v i r t e x 一1 1 系列的f p 6 a 具有内部块状 r a m 可以实现r o m ，这样不占用内部的逻辑资源，速度快。r o m 的实现利用了 i pc o r e 技术。 分支量度产生电路图如下图4 5 所示： 图4 5 分支量度计算电路图 哈尔滨工程大学硕士学位论文 二a c s u 单元的实现 对于( 2 ，1 ，7 ) 卷积码，有6 4 个状态，也就意味着，在每一步，要计 算6 4 个路径量度。基于速度要求，采用全并行算法，即在每一步同时计算 6 4 个路径量度，需要6 4 个并行处理的a c s 模块或3 2 个蝶形结构( 每一个蝶 形结构由2 个a c s 模块组成) ，蝶形结构如图4 6 所示。 t - i t s m i s m j s m q 图4 6a c s 蝶形结构 下面说明它们之间的关系： s m x ：状态x 的量度 b m x k ：在源输入为k 时，从状态x 来的分支量度。( k 取o ，1 ) 各状态之间的关系： 对于状态i 来说，j = 2 一+ i p = 2 iq = 2 i + 1 各分支量度之间的关系： b m i 0 2 b m j lb m i l 2 b m j o 对于硬判决来说，b m i l _ n b m i o 状态量度判决( 软) ： s m p = m i n ( s m i + b m i o ) ，( s m j + b m j o ) 】 s m q = m i n ( s m i + b m i l ) ，( s m j + b m j l ) 由上可知，状态p 是偶数，状态q 是奇数，也就是说，如果源输入是一0 ( 1 ) 那么到达的状态就是偶数( 奇数) 。这一特性可以在s m u 单元回索法中利用。 每一个a c s 单元由2 个加法器和1 个比较器构成，这样总共有1 2 8 个加 法器和6 4 个比较器。显然，路径量度单元是整个v i t e r b i 译码器的核心，对 ；。；一；一。；墅鋈蚤娑鍪圭耋堡j 垒2 ：一；。，。一；。一 于提高速度有糟实质的影响。a c s 实现结构如图4 7 所示。 图4 7a c s 电路实璐褥图 已经证明在每一步的量度的最大值与最小值的差值用下砸的公式o “计 算： s m 蝴一s 姒s 选一t 酗m 徽一8 m ， 在本方案中，k = 7 ，协f m w = 1 4 ，黼矿w = o ，最大的路径量度和最小的路 径量度之阀的最大差馕为8 4 。这样要袋用7 比特来表汞路径量度。事实上， 在每步的路径量度的归一化操作保诞了具有最小量度的路径鼯度不受路径 量度的魄特数粒影响。经过验谖，用s 魄特表零路径爨度的y i t e r b i 译码器 的性自仍然很好。为了防止溢出，当每一个路径量度都大于或锌于所逸择的 羲定的数篷辩，在下个周期，瑟毒蛇路径量发邦减去这个固定的数。在本 方案中选择4 为固定的数值，鼹基于比较器简单和快遴，用或非门实现。只 要路经器疫孛簸裹三您蠢一拿必1 裁意味羞藏璧度大予或等予4 。羞黪寿懿 路径量度都大于或等于4 时，进行归化操作，即从所有的路径量度中减去 4 。这样还需要一令6 莲埝入豹泼菲门溆貉，采产生螽一纯褥恚。 在a c s u 的实现中，利用了倍频时钟来处理，这样可以保证译码的连续 送李亍。倍颓辩锋采潮f p g a 蠢的i ) c m ( 数字盼辩楚鬓) 模块。 哈尔滨工程大学硕士学位论文 三s m u 单元的实现 在v i t e r b i 算法中，幸存路径存储的实现有两种传统方法”1 ：寄存器交 换法r e ( r e g i s t e re x c h a n g e ) 和回索法t b ( t r a c eb a c k ) 。 寄存器交换法采用专用寄存器作为存储主体，存储的是路径上的信号信 息，利用数据在寄存器阵列中的不断交换实现信息的译码。优点是存储单元 少，译码延时短，输入输出端固定。缺点是内连关系过于复杂，不适于大状 态译码器的f p g a 实现。 回索法使用通用的r a m 作为存储体，存储的是幸存路径的格状连接关系， 通过读写r a m 来完成数据的写入为回索输出。优点是内连关系简单、规则， 适合用f p g a 实现。缺点是译码延时较长。 v i r t e xi i 是x i l i n x 公司的高性能系列f p g a 。最高规模能达到8 ，0 0 0 ， 0 0 0 门，内部时钟高达4 0 0 m h z 。存贮单元具有高达3 m 容量的真正双端口 b l o c k r a m 。运算单元中包括最多1 6 8 b 的专用乘法器。v i r t e xi i 中的可配置 单元为c l b ( c o n f i g u r a b l el o g i cb l o c c k s ) 。c l b 中的资源可以灵活配置成多 种结构。包括实现查找表，移位寄存器等功能。在存贮资源不够的时候，c l b 也可以配置为分布的r a m “。 双口b l o c k r a m 是v i t e r b i 译码器中实现回索译码的主要模块，其端口如 图4 8 所示。可以看出b l o c k r a m 具有2 套独立的地址和数据输入、输出线， 独立的端口使能、写使能控制线，而且2 个端口各自的时钟输入可以不同。 这些结构保证了b l o c k r m n 是一个完全真正双端口操作的存贮器。v h t e xi i 系列中b l o c k r a m 最多有1 6 8 个，每个容量为1 8 k 。可以配置成不同的数据宽 度和深度。同时b l o c k r a m