（材料物理与化学专业论文）用于gps接收端的viterbi译码器的asic设计.pdf

学科专业：材料物理与化学 论文题目：用于g p s 接收端的v i t e r b i 译码器的a s i c 设计 硕士生：关红波导师：陈伟元 副教授 摘要 卷积码被运用于卫星通信和无线通信系统中，它提供了种不同于分 组码的在噪声信道下传输信息的一种编码方案。运用卷积码的优点之一是 它可以对连续的数据流进行处理。c d m a ( c o d ed i v i s i o nm u l t i p l ea c c e s s ) 数字蜂窝标准i s 9 5 采用卷积码作为其纠错方案，现在已经通过的第三代数 字蜂窝无线通信标准( 3 g ) 建议采用t u r b o 码作为纠错方案，该码也是属 于卷积码。 卷积码的译码算法方案有很多，如序列译码算法、f a n o 算法、v i t e r b i 算法，但是真正大规模应用的还是v i t e r b i 算法。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 译码器进行a s l c 前端设计，本次设计是以s y n o p s y s 公司的d e s i g n c o m p i l e r 作为综合工具、以c a d e n c e 公司的v e r i l o g x l 作为仿真验证工具进行的。行为仿真结果、综合布线后的门级仿真结果以 及f p g a 验证结果均表明了设计的正确性。 关键字：v i t e r b i 译码器，a s l c 前端设计，仿真 m a j o r ：m a t e r i a lp h y s i c s & c h e m i s t r y t i t l e ：t h ea s i cd e s i g no f v i t e r b id e c o d e r a p p l i e d t or e c e i v e ro fg p s m a s t e rc a n d i d a t e ：g u a nh u n g b o s u p e r v i s o r ：a s s o c i a t ep r o f , c h e nw e i y u a n a b s t r a c t c o n v o i n t i o n a lc o d i n gi sac o d i n gs c h e m eo f t e ne m p l o y e di nd e e ps p a c e c o m m u n i c a t i o n sa n d r e c e n t l yi nd i g i t a lw i r e l e s sc o m m u n i c a t i o n s i to f f e r sa l l a l t e r n a t i v et ob l o c kc o d e sf o rt r a n s m i s s i o no v e ran o i s yc h a n n e l a na d v a n t a g e o f c o n v o j u t i o n a lc o d i n gi st h a ti tc a nb ea p p l i e dt oac o n t i n u o u sd a t as t r e a ma s w e l la st ob l o c k so f d a t a i s 一9 5 ，aw i r e l e s s d i g i t a lc e l l u l a rs t a n d a r df o rc d m a ( c o d ed i v i s i o nm u l t i p l ea c c e s s ) ，e m p l o y sc o n v o l u t i o n a lc o d i n g a t h i r d g e n e r a t i o nw i r e l e s s c e l l u l a rs t a n d a r da d o p tt u r b o c o d i n g ，w h i c h s t e m sf r o m c o n v o l u t i o n a lc o d i n g t h e r ea r em a n y d e c o d i n g s c h e m e sf o rc o n v o l u t i o n a lc o d e ，s u c ha s s e q u e n c ed e c o d i n ga l g o r i t h m ，f a n oa l g o r i t h m ，v i t e r b ia l g o r i t h m b u t i n f a c t ，w h a t su s e dw i d e l y i sv i t e r b id e c o d i n g a l g o r i t h m t h e v i t e r b id e c o d i n g a l g o r i t h m ，p r o p o s e d i n1 9 6 7b yv i t e r b i ，i sad e c o d i n g p r o c e s sf o r c o n v o l u t i o n a l c o d e si nm e m o r y l e s sc h a n n e l ，w h i c ht a k e sf u l la d v a n t a g eo fc o n v o l u f i o n a l c o d e s s i n c ev i t e r b ia l g o r i t h mi sp r o p o s e d ，i th a so b t a i n e d r a p i dd e v e l o p m e n t w h e t h e ri nt h e o r e t i c so ri np r a c t i c ea n db e e na p p l i e dt oa l lk i n d so f d a t a t r a n s m i s s i o ns y s t e m s ，e s p e c i a l l yt od i g i t a lw i r e l e s sc o m m u n i c a t i o n sa n dd e e p s p a c ec o m m u n i c a t i o n s i nt h i st h e s i s ，w es t u d yv i t e r b id e c o d i n g a l g o r i t h mf i r s t ，a n da n a l y z et h e s t r u c t u r eo f v i t e r b id e c o d e i , t h e nb a s e do nt h e m ，p r e s e n tt h ef r o n t e n da s i c d e s i g no f v i t e r b i d e c o d e nd u r i n gt h ec o u r s eo f d e s i g n ，d e s i g n c o m p i l e ro f s y n o p s y si sa p p l i e da ss y n t h e s i st o o to f t h e d e s i g n ，v e r i l o g x l o f c a d e n c e i sa p p l i e da st h es i m u l a t i o nt o o l ，t h ee f f e c t so f t h et i m es e q u e n c e n e t l i s ts i m u l a t i o no ft h ec i r c u i ta n df p g av e r i f i c a t i o ni n d i c a t et h ec o r r e c t n e s s o f t h ec i r c u i td e s i g n k e y w o r d s ：v i t e r b id e c o d e r ，a s i cf r o n t e n dd e s i g n ，s i m u l a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 日期：哆年口膨日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 导师签名：j 登! 堑型 日期：哆年l 月哆日 电子科技大学硕士学位论文 第一章引言 1 1 研究背景及开发意义 提高信息传输的可靠性和有效性，始终是通信工作所追求的目标。纠 错码是提高信息传输可靠性的一种重要手段。 1 9 4 8 年香农( s h a n n o n ) 在他的开创性论文“通信的数学理论”中，首 次阐明了在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码 定理，奠定了纠错码的基石。自此以后汉明( h a m m i n g ) 、斯列宾( s l e p i a n ) 、 普兰奇( p r a n g e ) 等人在5 0 年代初，根据香农的思想，给出了一系列设计 好码和有效码的方法。以后，纠错码受到了越来越多的通信和数学工作者， 特别是代数学家的重视，使纠错码无论在理论上还是实际中都得到了飞速 发展。迄今，纠错码已有4 0 年的历熨”。 纠错码又可分为分组码和卷积码。分组码编码时，本组中的n k 个信 息元仅与本组的k 个信息元有关，而与其他各组码元无关。分组码译码时， 也仅从本码组中的码元内提取有关译码信息，而与其他各组无关。但是在 卷积码编码中，n o k o 个校验元不仅与本组的k o 个信息元有关，而且还与以 前各时刻输入至编码器的信息组有关。同样在卷积码译码过程中，不仅从 此时刻收到的码组中提取译码信息，而且还要利用以前或以后各时刻收到 的码组中提取有关信息。此外，卷积码中每组的信息位k o 和码长n o ，通常 也比分组码的k 和n 要小。 正是由于在卷积码的编码过程中，充分利用了各组之间的相关性，且 k o 和1 3 0 也较小，因此在与分组码同样的码率和设备复杂性条件下，无论从 理论上还是从实践上均己证明卷积码的性能至少不比分组码差，且实现最 佳和准最佳译码也较分组码容易1 2 j 。所以，从信道编码定理看，卷积码是 一种非常有前途的，能达到信道编码定理所提出的码类。但由于卷积码各 组之间相互有关，因此在卷积码的分析过程中，至今仍未找到象分组码那 样有效的数学工具，以致性能分析比较困难，从分析上得到的成果也不像 分组码那样多，而往往还要借助计算机的搜索来寻找好码。 电子科技大学硕士学位论文 但由于卷积码各组的n o 、k o 均比分组码小，译码似乎比分组码要容易， 卷积码有许多分组码所没有的特点和优势，它被广泛的运用于卫星通信和 无线通信系统中。c d m a ( c o d e d i v i s i o n m u l t i p l e a c c e s s ) 数字蜂窝标准 i s 一9 5 采用卷积码作为其纠错方案，现在已经通过的第三代数字蜂窝无线通 信标准( 3 g ) 建议采用t u r b o 码作为纠错方案，该码也是属于卷积码。 卷积码的译码方案有很多，如序列译码算法、f a n o 算法、v i t e r b i 算法， 但是真正大规模应用的还是v i t e r b i 算法。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 译码器的研究已成为一个热点问题，目前a l t e r a 公 司及x i l i n x 公司都己推出了符合i e e e 标准的v i t e r b i 译码器内核，t i 公司 推出了基于d s p 处理的v i t e r b i 译码器，i n t e i 公司也推出了功能强大的 通用v i t e r b j 译码器芯片。虽然这些芯片都能满足用户的需求，但是芯片 的价格一直居高不下。比如a l t e r a 公司和x ii lr l x 公司，用户买了内核以 后就必须买它们公司可编程芯片，而可编程芯片的价格是比较高的，而运 用t i 公司的产品就必须买该公司的d s p 处理芯片，而d s p 芯片由于功能强 大，所以价格是非常高的，而i n t e i 公司的产品是通用的芯片，可能有很 多功能都不会用到。 通过以上对一些国外公司产品的分析，可以看出，这些产品虽然功能 强大，能够满足大部分用户，特别是高端用户的需求，但是价格却是非常 高，一般的用户是很难承受的。 由于通讯、电子技术的飞速发展，特别是近年来通讯技术的发展，现 在的通讯企业的销售对象已经在逐步向个人用户靠拢，即出现了不同级别 的用户群。由于市场的扩大和用户的变化，很多企业为了降低成本就需要 专用的处理芯片，而不是价格高的通用芯片。 2 电子科技大学硕士学位论文 但由于设计这种通讯领域的专用芯片需要有较高的理论要求，设计周 期比较长，在国内研究v i t e r b j 译码器的主要还是各个大学和科研院所， 而专门设计这种芯片的设计公司更少，所需产品大多依靠进口，所以设计 开发该芯片具有十分重要的意义。 1 2 本文工作 本文所述v i t c r b i 译码芯片是专门为国腾集团下属国星公司卫星通信系 统设计、开发的，主要用于g p s ( 全球定位系统) 接收端，所以具有一定 的针对性，该设计的特点及主要技术参数如下： 1 、接口简单，去除一些额外的功能端口： 2 、运用灵活，采样频率可灵活调整； 3 、约束长度为l = 7 ； 4 、码率r = i 2 ； 5 、生成多项式g 1 = 1 7 1 g 2 = 1 3 3 ： 6 、3 位软判决译码输入； 7 、编码增益5 2 d b ( 1 旷b e r ，r a t e1 2 ) ； 8 、时钟1 5 m h z ： 9 、回溯深度4 2 ： 本次设计的第一部分工作就是研究v i t e r b i 译码算法及其译码器结 构，第二部分工作就是在此基础之上，对v i t e r b i 译码器进行a s i c 前端设 计。 电子科技大学硕士学位论文 第二章v i t e r b i 译码器基本理论 2 1 数字通信系统的组成 通信的目的是要把对方不知道的消息及时可靠的( 有时还需秘密的) 传送给对方，因此，要求一个通信系统传输消息必须可靠与快速，在数字 通信系统中可靠与快速往往是一对矛盾。若要求快速，则必然使得每个数 据码元所占的时间缩短，波形变窄，能量减少，从而在受到干扰后产生错 误的可能性增加，传送消息的可靠性降低。若要求可靠，则使得传送消息 的速率变慢。因此，如何较合理的解决可靠性与速度这一对矛盾，是正确 设计一个通信系统关键问题之一。通信理论本身( 包括纠错码) 也正是在 解决这对矛盾中不断发展起来的。 所有数字通信系统如通信、雷达、遥控遥测、数字计算机的存贮系统 和内部运算以及数字计算机之间的数据传输等，都可归结成如图2 1 所示 的模型h 。 图2 1 数字通信系统模型 图中，信源编码器是把信源发出的信息如语言、图象、文字等转换成 为二进制( 也可转换成为多进制) 形式的信息序列，并且为了使传输有效， 还去掉了一些与传输信息无关的多余度( 有时为了保密，信源编码器后还 可接上加密器) 。为了抗击传输过程中的各种干扰，往往要人为的增加一些 电子科技大学硕士学位论文 多余度，使其具有自动检错或纠错能力，这种功能由图中的信道编码器即 纠错编码器完成。发射机( 调制器) 的功用是把纠错码送出的信息序列通 过调制器变换成适合于信道传输的信号。数字信号在信道传输过程中，总 会遇到各种干扰而使信号失真，这种失真信号传输到接收端的接收机，进 行解调，变成二进制( 或多进制) 信号序列。由于信道干扰的影响，该信 息序列中可能已有错误，经过信道译码器即纠错码译码器，对其中的错误 进行纠正，再通过信源译码器( 及解密器) 恢复成原来的消息送给用户。 我们关心的是图中的信道编、译码器即纠错编、译码器两个方框，为 了研究方便，将上述模型再进一步简化成图2 2 所示的模型。在此模型中， 信源是指原来的信源和信源编码器，其输出是二( 多) 进制信息序列。信 道是包括发射机、实际信道( 或称传输媒质) 和接收机在内的广义信道( 又 称编码信道) ，它的输入是二( 多) 进制数字序列，输出一般也是二( 多) 进制数字序列，而图中的信宿可以是人或计算机。 图2 - - 2 数字通信系统简化模型 2 2 差错控制系统和纠错码分类 2 2 1 差错控制系统分类 在数字通信系统中，利用纠错码或检错码进行差错控制的方式大致有 以下几类： ( 】) 重传反馈方式( a r q ) 。发送端发出能够发现( 检测) 错误的码， 接收端收到通过信道传来的码后，在译码器根据该码的编码规则，判决收 到的码序列中有无错误产生，并通过反馈信道把判决结果用判决信号告诉 电子科技大学硕士学位论文 发端。发端根据这些判决信号，把接收端认为有错的信息再次传送，直到 接收端认为正确接收为止。由此可知，应用a r q 方式必须有一反馈通道， 一般较适用于一个用户对一个用户( 点对点) 的通信，且要求信源能够控 制，系统收发两端必须互相配合、密切合作，因此这种方式的控制电路比 较复杂。由于反馈重发的次数与信道干扰情况有关，若信道干扰很频繁， 则系统经常处于重发消息的状态，因此这种方式传送消息的连贯性和实时 性较差。该方式的优点是：编译码设备比较简单：在一定的多余度码元下， 检错码的检错能力比纠错码的纠错能力要高得多，因而整个系统的纠错能 力极强，能获得极低的误码率；由于检错码的检错能力与信道干扰的变化 基本无关，因此这种系统的适应性很强，特别适应于短波、散射、有线等 干扰情况特别复杂的信道中【3 j 。 ( 2 ) 前向纠错方式( f e c ) 。利用前向纠错方式进行差错控制的数字 通信系统如图2 2 所示。发送端发送能够被纠错的码，接收端收到这些码 后，通过纠错译码器不仅能自动的发现错误，而且能自动的纠正接收码字 传输中的错误。这种方式的优点是不需要反馈信道，能进行一个用户对多 个用户的同播通信，译码实时性较好，控制电路比a r q 的简单。其缺点是 译码设备比较复杂，所选用的纠错码必须与信道的干扰情况相匹配，因而 对信道的适应性较差。为了要获得比较低的误码率，往往必须以最坏的信 道条件来设计纠错码，故所需的多余度码元比检错码要多得多，从而使编 码效率很低。但由于这种方式能同播，特别适用于军用通信，并且随着编 码理论的发展和编译码设备所需的大规模集成电路成本的不断降低，译码 设备有可能做得越来越简单，成本越来越低，因而在实际的数字通信中逐 渐得到广泛应用。 ( 3 ) 混合纠错方式( h e c ) 。这种方式是发送端发送的码不仅能够被 检测出错误，而且还具有一定的纠错能力。接收端收到码序列以后，首先 检验错误的情况，如果在纠错码的纠错能力以内，则自动进行纠错。如果 错误很多，超过了码的纠错能力，但能检测出来，则接收端通过反馈信道， 要求发端重新传送有错的消息。这种方式在一定程度上避免了f e c 方式要 求用复杂的译码设备和a r q 方式信息连贯性差的缺点，并能达到较低的误 码率，因此在实际中的应用越来越广。 电子科技大学硕士学位论文 f e c h e e 廿可以纠正错误的鹅 江篓竺釜粪饕霉竺竺二二二莲卜 器群= 廿 b 翌竺燃孥塑瑾翳一1 甥罂竺二氆么卜一 图2 3 差错控制的基本方式 除了上述三种主要方式以外，还有所谓狭义信息反馈系统( i r q ) 。这 种方式是接收端把收到的信息原封不动地通过反馈信道送回发送端，发送 端比较发送的与反馈回来的消息，从而发现错误，并且把传错的消息再次 传送，最后达到使对方正确接收消息的目的。 为了便于比较，我们把上述几种方式用图2 3 所示的框图表示。图中， 有斜线的方框表示在该端检出错误。在实际系统设计中，如何根据实际情 况选择哪种差错控制方式是一个比较复杂的问题，由于篇幅所限，这里不 再讨论。 2 2 2 纠错码的分类 上述各种差错控制系统中所用到的码，不外乎是能在译码器自动发现 错误的检错码，或者不仅能发现错误而且能自动纠正错误的纠错码，或者 能纠正删除错误的纠删码。但这三类码之间没有明显区分，实际上，任何 一类码，按照译码方法不同，均可作为检错码、纠错码或纠删码来使用。 除了上述的划分方法以外，通常还按以下方式对纠错码进行分类【i ： ( 1 ) 按照对信息元处理方法的不同，分为分组码与卷积码两大类。 分组码是把信源输出的信息序列，以k 个码元划分为一段，通过编码 器把这段k 个信息元按一定规则产生r 个校验( 监督) 元，输出长为n = k + r 的一个码组。因此每一码组的校验元仅与本组的信息元有关，而与别组无 电子科技大学硕士学位论文 关。分组码用( n ，k ) 表示，n 表示码长，k 表示信息位。 卷积码是把信源输出的信息序列，以k o 个( k o 通常小于k ) 码元分为 一段，通过编码器输出长为n o ( = k o ) 一段的码段。但是该码段的n o k 。个校验元不仅与本组的信息元有关，而且也与其前m 段的信息元有关， 称m 为编码存贮。因此卷积码用( n o ，k o ，m ) 表示。 ( 23根据校验元与信息元之间的关系分为线性码与非线性码。若校 验元与信息元之间的关系是线性关系( 满足线性叠加原理) ，则称为线性码： 否则，称为非线性码。 ( 3 )按照纠正错误的类型可分为纠正随机( 独立) 错误的码、纠正 突发错误的码和纠正同步错误的码，以及既能纠正随机错误又能纠正突发 错误的码。 ( 4 ) 按照每个码元取值来分，可分为二进制码与q 进制码。 ( 5 )按照对每个信息元保护能力是否相等可分为等保护纠错码与 不等保护( u e p ) 纠错码。 此外，在分组码中按照码的结构特点，又可分为循环码与非循环码。 为了清楚起见，我们把上述分类用图2 4 表示。 图2 4 纠错码分类 电子科技大学硕士学位论文 2 3 卷积码及其表示方法 2 3 1 卷积码编码原理 v i t e r b i 译码算法是1 9 6 7 年由维特比( v i t e r b i ) 提出的一种对卷积码译 码的最大似然译码算法，卷积码有许多分组码所没有的特点和优势，被广 泛的运用于卫星通信和无线通信系统中。 卷积码的概念在前文已有所描述，其编码原理可直观的由卷积码编码 器阐述。卷积码编码器的构造很简单。一个最简单( 2 ，i ，2 ) 卷积码，如果 其子生成元为7 ，5 ，则编码器如图2 5 所示t 7 输m 2 图2 5 ( 2 ，1 ，2 ) 卷积码编码器 图2 5 的方框表示移位寄存器，o 表示模2 和相加器，也可以看作是 一个异或门，箭头方向表示数据的流向。 图2 5 的卷积码编码器中，每一时刻，当输入1 个信息比特，则同时 输出2 个信息比特，所以该卷积码编码器的码率r = t 2 。 卷积码编码器一般用( n ，k ，m ) 表示，其中： 1 1表示编码器的输出个数； k表示编码器的输入个数： m 表示编码器中存储单元个数。 卷积码( n ，k ，m ) 的码率r = k n 。 9 电子科技大学硕士学位论文 卷积码编码器可以看作是一个m e a l y 机，编码器的输出是当前状态和 当前输入的一个函数。它包括一个或多个移位寄存器和多个异或门。输入 的信息数据流入移位寄存器的输入端并且随后移入输出端。异或门与移位 寄存器和当前的输入相连，产生数据输出。这儿没有移位寄存器与异或门 相互连接最佳位置的理论，它是完全凭经验得到的。上述位置是由互连函 数所决定的，这如同存储器单元数量决定了最小汉明距离，最小汉明距离 决定了一次能够纠正错误数据的个数。在参考文献 4 j o e 介绍了不同码率、 不同存储单元个数和它们的最小汉明距离的互连函数。 下面我们详细说明图2 5 卷积码编码器的编码过程： 首先，卷积码编码的初始状态为0 ，即移位寄存器1 、2 内的数据都为 0 。当输入一个数据时，输入数据、寄存器l 和寄存器2 同时作用于模2 和 相加器产生2 个数据，并输出这两个数据。当下一个数据到来时，寄存器 2 的数据移出编码器，寄存器1 的数据移入寄存器2 中，上一时刻的输入 数据移入寄存器1 ，此时2 个寄存器中的数据与此时刻输入的数据又同时 作用于模2 和相加器产生2 个数据，并输出这两个数据。当下一时刻输入 数据到来时，处理过程同上。如果输入的数据序列是：( 】0 1 1 1 0 0 ) 则我们 可以得到编码输出的数据为：( 1 1 ，1 0 ，0 0 ，o l ，1 0 ，0 1 ，1 1 ，) 。 本文所讨论的码是( 2 ，l ，6 ) 码，编码器存储单元有六个，子生成元 为1 7 1 ，1 3 3 ，如下图2 6 所示： 数捌输i 啪1 图2 6 ( 2 ，1 ，6 ) 卷积码编码器 o 电子科技大学硕士学位论文 ( 2 ，】，6 ) 码的编码过程与( 2 ，1 ，2 ) 码相同，在此就不再赘述。 2 3 2 卷积码的表示 正如前文所述，卷积码编码器其实可以当作一个有限状态机( f s m ) ， 所处的状态由该时刻的寄存器决定，状态的转移由输入的数据所驱动。 如果我们假定当前时刻j 的状态为s i os i i ，其中s i o 为寄存器l 内的 数据，s i l 为寄存器2 内的数据，输入的数据用d 表示，则我们将得到2 个表格，一个是状态转移表( 见表2 1 ) ，一个是编码器输出表( 见表2 - - 2 ) ，其中s ( i + l l o s i ) 1 表示下一时刻即i + l 时刻编码器寄存器的状态，o u 如 o u t l 2 表示当前时刻编码器的输出数据。 表2 1 状态转移表 d = 0d = i s i os i 】= 0 0 s f i + o os o + o i = 0 0s ( i + 1 ) 0s ( i + 0 1 = 1 0 s i os i = 0 1 s ( i h ) os ( i + o l = 0 0s ( i + i ) 0s ( i + i 、i = 1 0 s i os i l = 1 0 s ( i + 1 ) os ( i * j ) l = 0 1s ( i + o os o + 】1 1 = 1 1 s i os i l = 1 1 s ( i + 1 ) os ( i + i ) l = 0 1s o + o os ( i + 1 ) i = 1 1 表2 2 输出表 d = od = l s i os i l = 0 0o u l i lo a t i 2 = 0 0o u t i jo u t 2 = 1 1 s i os i l = 0 1 o u t i io u t i 2 = l1o u t i l0 u t i 2 = 0 0 s i os = 1 00 u t i l0 u t i 2 = 1 0o m i lo u t i 2 = 0 1 s i os n = 1 1 o u t i lo u t i 2 = 0 1o u t i l0 l l t i 2 = l0 以上的表示是通过表格的形式，其实卷积码的表示方法有很多，下面 就以后可能会用到的一些表示方法进行简单的介绍： ( 1 ) 有限状态机( f s m ) 表示法： 电子科技大学硕士学位论文 圜 r i 1 0 0 l l 下j o o悫 图2 7 有限状态机表示法 上图2 7 中方格表示当前状态，箭头所指的状态为下一状态，其中实 线表示当前输入的数据是1 ，虚线表示当前输入的数据是0 ，实线或虚线上 的数据表示当前的输出。前文所描述的卷积码编码器编码过程其实就是在 以上的各个状态之间转移的过程。 ( 2 ) 网格( t r e l l ) 表示法： n 驴网 l 实线：1l j垒垡! !| 图2 8 网格表示法 t r e l l 表示法与f s m 表示法大部分相似，只是它表示出了编码与时间 的关系，所以我们就不用另外说明了。 电子科技大学硕士学位论文 2 4v i t e r b i 译码算法 2 4 1v i t e r b i 译码算法的历史 卷积码的译码算法方案有很多，最早的是1 9 6 1 年由乌曾格来夫提出的 序列译码，这是第一个提出的实用的卷积码的概率译码方法。在此之后， 1 9 6 3 年费诺对序列译码进行改进，提出了f a n o 算法，并推动了序列译码 的实际应用。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 算法提出以来，无 论在理论上还是实践上都得到了极其迅速的发展，并广泛地应用于各种数 字传输系统中，特别是无线通信系统和卫星通信系统中。 2 4 2v i t e r b j 译码算法的基本原理 下图2 9 描述了一个通过有噪声信道的一般的信息流的传输情况。为 了能够纠正错误，编码器在原始信息i 上增加了冗余信息，编码输出的数 据t 在信道中传输。进入译码器的是带有冗余和噪声的信息( r ) 。接收端 尽可能通过译码算法从接收到的信息中找出原始信息，并产生个估计的 数据( e ) 。最大概率p ( r e ) 的译码算法叫做最大似然算法( m l ) 。最大概率 p ( e r ) 的译码算法叫做最大后验算法( m a p ) 。当输入的信号源i 有统一的 概率分布时，这两个算法的结果是相同的1 2 】。在本设计中，我们采用最大 似然译码算法。 图2 - 9 卷积译码 由于我们所要讨论的( 2 ，1 ，6 ) 码，有2 6 = 6 4 个状态，不便说明。 所以下面我们仍然以在编码过程中用到的( 2 ，1 ，2 ) 卷积码为例，来说明 电子科技大学硕士学位论文 v i t e r b i 译码算法的基本原理。 如前所述，虽然状态图能表示卷积编码器在不同输入的信息序列下， 编码器各状态之间的转移关系，但并不能表示出编码器状态转移与时间的 关系。为了表示这种状态与时间的关系，我们用t r e l l 方式来表示卷积码 编码的过程，如下图2 1 0 所示： 67 移一 ， ， j j 蜀 图2 1 0 ( 2 ，1 ，2 ) 码的t r e l l 图 图2 一1 0 是l = 5 ( 输入五个信息元) ，( 2 ，1 ，2 ) 卷积码的状态转移时 间关系图，它由节点和分支组成，共有l + m + 1 个时间单位( 节点) ，我们以 0 至l + m 予以标号。若编码器从s o ( 0 0 ) 状态开始，并且结束于s o 状态， 则最先的m = 2 个时间单位( o ，1 ) ，相应于编码器由s o 状态出发往各个状 态进行，而最后m = 2 个时间( 6 ，7 ) ，相应于编码器由各状态返回到s o 状 态。因此，在开始和最后m 个时间单位，编码器不可能处于任意状态，而 只能处在某些特定状态，仅仅从第m ( 2 ) 至第l ( 5 ) 时间单位，编码器可以处 于任何状态之中( 即4 个状态s o ，s i ，s 2 ，s 3 中之任一个) 。 t r e l l 表示法中，每一状态有两个输入分支和两个输出分支。在某一 时间单位i ，离开每一状态的虚线分支，表示输入编码器的信息元m ；= o ， 即输入为0 ；而实线分支表示此时刻输入至编码器的信息元m i = 1 ，即输入 为1 。每一分支上的2 位数字，表示i 时刻编码器输出的子组c i ( c i ( ”，c 。( 2 ) ， 因而t r e l l 中的每一条路径都对应于不同输入的信息序列。 例如，输入至图中编码器的信息序列m = ( 1 0 1 l1 0 0 ) ，则由编码器输 电子科技大学硕士学位论文 出的码序列c = ( 1 l ，1 0 ，0 0 ，0 1 ，1 0 ，0 1 ，1 1 ) ，它相应于t r e l l 图中的 一条路径。如下图2 一l l ： 0 s o 表示0 0 s 1 表示1 0 s 2 寝示0 l s 3 袭示1 1 图2 1 1 ( 2 ，1 ，2 ) 编码器输出路径 一般情况下，( n ，k ，m ) 卷积码编码器共有2 啪个状态，若输入的信 息序列长度是l k + m k ( 后m k 个码元全为零) ，则进入和离开每一状态的各 有2 。条分支，在篱笆图上有2 k l 条不同的路径，相应于编码器输出的2 k l 个码序列。 编码器送出的码序列c ，经过离散无记忆信道( d m c ) 传输后送入译 码器的是序列r = c + e ，e 是信道错误序列。译码器根据接收序列r ，按最 大似然译码准则力图找出编码器在网格图上走过的路径，这个过程就是译 码计算、寻找最大似然函数 m a x 】0 9b p ( ri q )j = 1 ，2 ，2 “ 的过程，或者说译码器计算、寻找有最大“度量”的路径的过程，即寻找 m a x m 限iq )j = 1 ，2 ，2 “ 的过程。式中，m ( riq ) = l o gbp ( rlc j ) 是q 的自然函数也称c j 的路径 度量。 对b s c ( 二进制对称信道) 信道而言，计算和寻找有最大度量的路径， 等价于寻找与r 有最小汉明距离的路径，即寻找 m i n d ( r ，c j )j 2 1 ，2 ，2 “ 对二进制输入q 进制输出的d m c 信道而言，就是寻找与r 有最小软 ，9、 。 电子科技大学硕士学位论文 距离的路径，此时的度量就是软判决距离， m i n d 。( r s ，c i s )j _ l ，2 ，2 “ 式中，r ；与c 。是接收序列r 与q 序列的q 进制表示。 但是用上述这些方法译码是难以实现的。例如l = 5 0 ，n = 3 ，k = 2 ，则共 有2 k l = 2 m o 1 0 3 0 个码序列( 或网格图上的路径) ；若m = 5 ，则f l + m ) = 5 5 。 如果在一秒钟内送出这k l = 1 0 0 个信息元，则信息传输率只有1 0 0 b i “s ，这 是很低的。但即使是在如此低的信息速率下，也要求译码器在一秒钟内计 算、比较1 0 3 0 个似然函数( 或汉明距离、软距离) ，这相当于要求译码器计 算每一似然函数的时间小于1 0 - 3 咯，这是根本无法实现的。更何况通常情 况下l 不是几十，而是成百上千，因此，必须寻找新的最大似然译码算法。 v i t e r b i 算法正是在解决上述困难中所引入的一种最大似然译码算法。 它并不是在网格图上一次比较所有可能的2 “条路径( 序列) ，而是接收一 段，计算、比较一段，选择一段最可能的码段( 分支) ，从而达到整个码序 列是一个有最大似然函数的序列。现在把v i t e r b i 译码算法的步骤简述如下： ( 1 ) 从某一时间单位j = 玎l 开始，对进入每一状态的所有长为i 段分支 的部分路径，计算部分路径度量。对每一状态，挑选并存储一条有最大度 量的部分路径及其部分度量值，称此部分路径为留选路径。 ( 2 ) i 增加l ，把此时刻进入每状态的所有分支度量，和同这些分 支相连的前时刻的留选路径的度量相加，得到了此时刻进入每一状态的 留选路径，加以存储并删去其它所有路径，因此留选路径延长了一个分支。 ( 3 ) 若j l + m ，则重复以上各步，否则停止，译码器得到了有最大路 径度量的路径。 下面我们举一个简单的例子来说明v i t e r b i 译码算法的过程： 输入至( 2 ，l ，2 ) 编码器的信息序列m = ( 1 0 1 1 1 0 0 ) ，编码器输出的码序 列c = ( 1 1 ，1 0 ，0 0 ，0 1 ，1 0 ，0 1 ，1 1 ) ，通过b s c 送入译码器的序列r = ( 1 0 ， 1 0 ，0 0 ，0 1 ，1 1 ，o l ，1 1 ) 有两个错误，下面我们利用v i t e r b i 译码算法输出 估计信息序列m 和码序列c 。基于图2 1 0 的网格图，v i m r b i 译码器接收 序列r 的过程示于下图2 1 2 中。 电子科技大学硕士学位论文 j 。第1 时刻接收f 6 弥。一j l 】2 托：| i - 】刻接收f l i 弓r , = l o 列刻01d 3 第三时刻接收，码r ：卸o 时刻0 1 4 第| ! ! 】州刻接收子码免i = 0 1 时刻0 j dh 4 1 7 州翔0 dm 3q 0 0 0 dm 2( 0 0 ) ( 0 1 ) ( 1 0 ) 电子科技大学硕士学位论文 i 莉舢1 划接收h 一弧1 j 时刻0 】 6 鼐六时亥9 接收予“q 时 别 7 时 刻 3 4 ， ， 翁 之瓢詈”三毒 园翱7 以 飞商 心， b 上 7 1 i 5 七时刘接收予鹎 7 ， 图2 1 2 用v i t e r b i 译码算法在网格图上的译码过程 ( 】 f 1 0 1 0 0 ) 3 ( 0 0 0 0 ” 2( 1 0 1 1 0 ) 2( 1 0 1 1 1 ) d 3 ( 1 0 l 1 0 0 ) 2 ( 10 1 1 l0 ) d强 2 ( 1 0 l l 】0 0 ) 上图中画出了各时刻进入每一状态的留选路径及其度量值d ( 最小汉 明距离) ，以及与此相应的译码器估计的信息序列m 。当l + m = 7 个时刻以 8 09， 电子科技大学硕士学位论文 后，4 条留选路径只剩一条，它就是译码器输出的估值序列c = ( 1 1 ，1 0 ， o o ，o l ，1 0 ，0 1 ，1 】) ，相应的估值信息序列m = ( 1 0 1 】0 0 ) ，r 中的两个 错误得到了纠正。 由图看出，在某一时刻，如j = 3 时，进入s 。状态的留选路径的确定过 程可叙述如下。进入s o 状态的有两条路径：一条是由( 0 0 ) 分支加上与此 分支相连的前一时刻( 第2 时刻) 的留选路径c o 广( 0 0 ，0 0 ) 连接组成的 路径( c o l0 0 ) = ( 0 0 ，0 0 ，0 0 ) ，d ( r 2 ，0 0 ) = d ( 0 0 ，0 0 ) = 0 ，因而 d ( c o l0 0 ，r o r l r 2 ) = d ( c o l ，岛r t ) + d ( r 2 ，0 0 ) = 2 + 0 = 2 ，所以 该路径的度量值d 是2 ；另一条路径是由( 11 ) 分支加上与此分支相连的 前一时刻( 第2 时刻) 的留选路径c o j = ( 1 l ，1 0 ) 连接组成的路径( c o l ， 1 1 ) = ( “，1 0 ，1 1 ) ，它的度量值d = d ( c o l 1 1 ，硒r l r 2 ) = d ( c o l ，r o r l ) + d ( r 2 ，1 】) = l + 2 = 3 。根据最小汉明距离准则可季寻在第3 时刻s o 的留 选路径是c o l 2 = ( 0 0 ，0 0 ，0 0 ) ，它的度量值d = 2 。 在其他时刻及进入其余状态的留选路径的选择与此完全相同。若某一 时刻进入某一状态的两条路径有相同的度量，如第4 时刻，进入s 2 状态的 两条路径( 1 1 ，l o ，o o ，l o ) 和( 0 0 ，1 1 ，o l ，0 1 ) ，它们的度量值d 都为3 ， 故可任选一条作为s 2 状态的留选路径，在图中选择( 1 l ，1 0 ，0 0 ，1 0 ) 。 这种任意选的结果，并不会影响最后结果的正确性。 由前面所述的译码过程不难明白，v i t c r b i 译码器应有以下特点： ( 1 1 ( n ，k ，m ) 卷积码编码器共有2 个状态，因而v i t c r b i 译码器必 须有同样的2 h n 个状态发生器。并且对每一状态必须有一个路径寄存器以 存储路径或其信息序列m ，以及一个存储路径度量值的存储器。所以v i t c r b i 译码器的复杂性随2 指数增加。为了不致使译码器太复杂、成本太高， 一般要求选用码的编码存储m 1 0 。 f 2 、每个路径( 或信息序列) 存储器存储路径的长度是n l 或k l ) 。 这里，l 是需