（电路与系统专业论文）基于CSP理论的Viterbi模块在FPGA上的实现[电路与系统专业优秀论文].pdf

摘要 摘要 s o e 技术已经成为电路设计中主要方法。整个系统功能的实现是在一个大规模 的集成电路上。这个集成电路可能包含了数字、射频、模拟以及其它的功能。s o c 技术的优点在于它能将电路的设计从底层电路级推向系统级，使设计者可以将更 多的精力放在对口模块的选择以及内部连接结构上。而一个系统级的i p c o l e 可以 看作是由多个模块i p c o r e 通过内部的总线连接而成。 一个i p c o r e 网络可能遭遇稳定性的问题，比如死锁和活锁。只有从设计初期 入手才能解决这些问题。其中一个方法是同步原则，即：使得基本上每一个数字 设计都是用同步。运用同步的原则会使得抽象的模型很容易理解以及改进。c s p 理论正是基于同步这一点，它强调执行的有序性；同时c s p 设计方法还可以针对 不同的层次进行描述，比如：系统级和芯片级等。这有助于设计者对模块的分析 和设计。 v i t c r b i 算法是目前通信领域中最常用的卷积码译码算法之一。本文在大量阅 读前人研究文献的基础上，深入理解其算法，提出针对d a b 卷积码译码算法的合 理结构，应用c s p 理论分别对其每一个模块进行描述、验证，最后采用x i l i n x 公 司的i s e 开发工具为系统开发平台，在这个平台上完成模块的v h d l 语言设计、 综合、功能仿真和时序仿真。 关键词：c s p ，v i t c r b i 译码器，f p g a ，d a b a b s t r a c t a b s t r a c t s o c ( s y s t e mo nc h i p ) t e c h n o l o g yh a se v o l v e di l l st h ep r ed o m i n a n tc i r c u i td e s i g n m e t h o d o l o g y t h ee n t i r es y s t e m sf u n c t i o n a l i t yi si m p l e m e n t e d0 1 1as i n g l ei c t h i si c m a yi n t e g r a t ed i g i t a l ，r f , a n a l o g u ea n do t h e rf u n c t i o n s t h ea d v a n t a g ei st h a ts o c t e c h n o l o g ym o v e sd e s i g nf r o mt h ec i r c u i tl e v e lt ot h es y s t e ml e v e l ，c o n c e n t r a t i n go nt h e s e l e c t i o no fa p p r o p r i a t ei pb l o c k sa n dt h e i ri n t e r c o n n e c t i o ni n t oac o m p l e t es y s t e m a n i pc g ) r eb a s e ds y s t e mc a nb ev i e w e da sac o l l e c t i o no fv a r i o u si pc o r e sw i ma n i n t e r c o n n e c t i o nb u sn m n i n ga m o n gt h e m t h en e t w o r ko fs e l f - c o n t a i n e di pc o r e sm a ys u f f e rf r o ms t a b l ef a i l u r e ss u c ha s d e a d l o c ka n dl i v e l o c k o n l yaf u n d a m e n t a l l yc o r r e c td e s i g nm e t h o dp r o v i d e sar e l i a b l e w a yt oa v o i dd e a d l o c ka n dl i v e l o c kp r o b l e m s o n eo ft h e s em e t h o d si s a s y n c h r o n i z a t i o nm e t h o dw h i c hi sr o b u s ta n ds i m p l ee n o u g ht ob ea p p l i c a b l et oa l m o s t e v e r yd i g i t a ld e s i g n t h es y n c h r o n i z a t i o ns c h e m ec a nl e a d st oa b s t r a c tm o d e l sw h i c h a r ec o m p r e h e n s i b l ee n o u g ht ob eu n d e r s t o o da n dp r o v e d t h ec s p ( c o m m u n i c a t i n g s e q u e n t i a lp r o c e s s e s ) t h e o r yi s b a s e do nt h es y n c h r o n i z a t i o n i te m p h a s i z e st h e s e q u e n t i a lp e r f o r m a n c e a n dt h ec s pd e s i g nm e t h o dc a np r o v i d et h ea b s t r a c to ft h e d i f f e r e n tl e v e l s u c h 硒：s y s t e ml e v e l ，c h i pl e v e la n ds oo n i ti sv e r yh e l p f u lf o r d e s i g n e rt oa n a l y z ea n dd e s i g nt h ep r o c e s s v i t e r b ia l g o r i t h mi so n eo f m o s tf a m o u sd e c o d i n ga l g o r i t h mf o rc o n v o l u t i o n a lc o d e i nc o m m u n i c a t i o nf i e l d b yr e a d i n ga b u n d a n c eo t h e rp e o p l e sr e s e a r c hl i t e r a t u r e ，t h i s p a p e rc o m p r e h e n d sv i t e r b id e c o d i n ga l g o r i t h md e e p l y a n di tp r o v i d e st h ea p p r o p r i a t e s t r u c t u r ef o rt h ed e c o d e ro ft h ed a bc o n v o l u t i o n a lc o d e t h e l li td e s c r i b e st h ed e c o d e r b a s e do nt h ec s pt h e o r y f o ri m p l e m e n t a t i o n ，t h ev i t e r b id e c o d e ri si m p l e m e n t e do n f p g ab yu s i n gi s ed e s i g np l a t f o r mo fx i l i n xt od e s i g nv h d lp r o g r a m ，s y n t h e s i s ， s i m u l a t ef u n c t i o nl o g i ca n ds i m u l a t et i m el o g i c k e yw o r d ：c s p , v i t e r b id e c o d e r , f p g a ，d a b i i 图目录 图目录 图3 - 1 卷积码编码器1 l 图5 - 1d a b 中卷积码编码器2 2 图5 2d a b 中卷积码外部端口2 5 图5 3 编码器仿真图2 6 图5 - 4 编码器网格图2 6 图5 - 5 ( 4 ，1 ，7 ) 1 时刻p m 更新图2 7 图5 6 ( 4 ，1 ，7 ) 2 时刻网格图2 8 图5 - 7 ( 4 ，l ，7 ) 3 时刻的网格图2 9 图5 8( 4 ，1 ，7 ) 4 时刻的网格图2 9 图5 - 9v i t e r b i 译码器内部功能结构图3 l 图5 1 0c s p 到v h d l 转换图3 1 图5 1 1c s p 理论模块通信图3 2 图5 - 1 2v h d l 环境中的模块通信图3 2 图5 1 3v i t e r b i 译码器外部框图3 3 图5 一1 4 分支度量模块3 7 图5 一1 5 状态转移图3 8 图5 一1 6 路径分支度量模块的仿真图3 9 图5 1 7 十进制碟形图3 9 图5 1 8 碟形单元图4 l 图5 一1 9 加比选单元的外部模块图4 2 图5 - 2 0 加比选单元部分仿真图4 3 图5 2 1 路径度量存储以及溢出控制模块图4 4 图5 2 2 路径度量存储以及溢出控制模块仿真图4 5 图5 2 3 最小状态选择器模块图4 6 图5 2 4 最小状态管理模块部分仿真图4 6 图5 2 5 幸存路径存储器模块4 7 图5 2 6v i t e r b i 译码器内部结构4 8 图5 2 7v i t e r b i 译码器仿真图4 9 v 图目录 图5 2 8 测试方法图4 9 图5 2 9f p g a 上得到的信号图5 0 v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 关于论文使用授权的说明 钞月勿日 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：沙7 年严月弦日 第一章引言 1 1 研究背景以及开发意义 第一章引言 软件无线电的概念是由j e om i t o l a 在1 9 9 2 提出，它突破了传统的无线电平台 以功能单一、可扩展性差的硬件为核心的设计局限性，强调以开放性的最简单硬 件设计平台，尽可能地用可升级、可重配置的应用软件来实现各种无线电功能的 设计思路。使设计者在同一硬件平台上可以通过配置不同的应用软件来满足不同 时期、不同使用环境的不同功能需求【l 】。软件无线电在可编程的通用硬件平台上， 利用软件来定义和实现无线设备的各部分功能，使得硬件工程师从原来耗时、繁 琐的底层电路设计中解放出来，拥有更多的时间来专注于系统算法以及结构。 随着软件无线电技术的日趋成熟，它被广泛的应用于无线电通信领域。d a b ( d i # t ma u d i ob r o a d c a s t i n g ) 是继a m 、f m 传统模拟广播之后的第三代广播一 数字音频广播，它的出现是广播技术的一场革命。因为数字广播具有抗噪声、抗 干扰、抗电波传播衰落等特点，它能提供c d 级的立体声音质量。其中很重要的原 因是，在数字广播通信中可以引入前向纠错模块，即f e c ( f o r w a r de r r o r c o r r e c t i o n ) 。在实际通信中，由于信道传输特性的不理想，数据在传输过程中不可 避免会产生畸变和非等时延迟，对数字信号来说就意味着产生误码和抖动，而抖 动的最终效果也反映在系统的误码上。如果在发射端通过某种算法对待发的信息 编码，在接收端通过相应的算法解码，使得发生误码最大程度的得到纠正。f e c 正是接收端译码模块。 纠错码分为分组码和卷积码两大类。由于卷积码在编码过程中充分利用了各 组之间的相关性，卷积码具有优异的性能。因此在通信纠错中，以卷积码为主分 组码为辅。卷积码的译码方案有很多，如序列译码算法、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 译码算法是基于码的代数结构和 信道的统计特性的一种译码技术，是卷积码的一种最大似然译码算法，它充分发 挥了卷积码的特点，使译码性能得到很大的提高。特别是在约束度较小时，v i t e r b i 译码算法效率较高、速度较快、译码器简单。因此，自1 9 6 7 年提出以后，无论在 理论还是实践中，都得到了极其迅速的发展，并广泛的应用于各种数据传输系统 中。 电子科技大学硕士学位论文 软件技术的优点是在于它能将电路的设计从底层电路级推向与系统级，将更 多的精力放在对m 模块的选择以及内部连接结构上。而一个系统级的i p c o r e 可以 看作是由多个模块i p c o r e 通过内部的总线连接而成。一个完备的i p c o r e 网络可能 遭遇稳定性的问题，比如死锁和活锁1 2 】。 只有从根本上的设计入手才能解决这些问题。其中一个方法是同步原则，即 使得基本上每一个数字设计都是用同步。运用同步的原则会使得抽象的模型很容 易理解以及改进。报告显示由c a r h o a r e 提出了c s p ( c o m m u n i c a t i n gs e q u e n t i a l p r o c e s s ) 设计方法可以提供所需要的抽象，同时也会考虑到安全性以及稳定性。 c s p 是一门用于描述和分析并行系统的符号理论，它主要的关注点是在于可以通 过不同的抽象程度对不同模块间通信的进行描述与分析。然后通过专用软件来判 断设计中是否出现死锁等现象，为硬件工程师解决了很多问题。 目前，c s p 理论在与硬件的结合应用还处于起步阶段，但是随着软件无线电 的发展，c s p 的会得到越来越多的应用。因此本文结合当前背景，将v i t e r b i 译码 器通过c s p 语言验证后，然后转成硬件语句，最后在f p g a 实现。 1 2 本文工作 本课题来源于d a b 系统设计中的一块，o f d m 算法的实现是由两位德国博士 完成，而本文的工作是设计前向纠错模块，用c s p 理论中的符号来描述验证，最 后在x i l i n x 的v i r t e x l i 系列中x c v 3 0 0 0 f p g a 上实现。大致规划如下： 第二章介绍c s p 语言的基本概念；第三章着重讨论卷积码编码以及v i t e r b i 译 码算法；第四章介绍本文需要用的软件，硬件以及总结在f p g a 设计过程中应该 考虑的问题；第五章为d a b 编码器的实现、以及所对应的v i t e r b i 算法的理论验证， 用c s p 描述以及用专用工具检查是否存在死锁，然后再f p g a 上的实现。 第二章c s p 基本理论 第二章c s p 基本理论 c s p ( c o m m u n i c a t i n gs e q u e n t i a lp r o c e s s e s ) 是一门符号理论，用于描述并行系 统中模块与模块之间相互通信；同时，c s p 也具有许多数学模型以及推理的方法， 有助于更好的理解和使用该理论中的符号。在本章中，我将介绍c s p 理论的一些 基本概念以及运用。 2 1 进程( p r o c e s s e s ) 我们用进程代表具有特定接口的独立实体，并规定实体的行为是能用由字母 组成的事件的有限集合来说明。 我们定义： 1 约定的字符串表示不同的事件，比如：c o i n ，c h o c 等；有时候也可以用字 母来表示事件，如：a , b ，c ，等。 2 大写的有意义字符串表示具体的某一进程，如：a t m 就可以表示为自动取 款机。有时也用单个的大写字母表示任意进程，如：p ，q ，r 等。 3 小写字母x ，y ，z 是表示事件的变量；大写的字母a ，b ，c 则表示事件的 集合；大写的x ，y 表示进程的变量。 4 最简单的进程是用s t o p 表示，该进程从来没有准备执行它端口上的事件， 永远处于同一状态。 5 进程之间的通信建立在参与通信的进程必须同时同意某一事件时该事件才 能被执行，类似于握手原则。 2 2 符号以及语法 符号的应用是c s p 核心。通过应用这些符号我们可以在比较高的抽象层次上 去描述完备实体之间复杂的关系。c s p 中的符号通过序列进程以及这些进程之间 的通信来达到描述完备实体母体。接下来将介绍在c s p 中比较常用的符号的含义 以及用法。 电子科技大学硕士学位论文 2 2 1 顺序进程 2 2 1 1 前缀算子( p r e f i x i n g ) 【3 】 给定一个进程p 事件4 ，a ，其中表示的是所有可能发生事件的全 集。那么a - - + p 表示该进程开始的行为是先和a 通信，然后行为和进程p 一样。举 个例子：用用钥匙开门这个过程安全的进程，用c s p 描述为 s a f e = p i n _ o p e n s t o p ( 2 1 ) 含义就是s a f e 这个进程首先需要等待p i n 事件的发生，然后才会有o p e n 事 件的发生，两个事件发生完了之后进入s t o p 进程，即门已经被安全的打开。这样 一个执行过程的以及符号就被称为前缀算子。 前缀算子以及s t o p 进程连接在一起使用时，我们可以描述连续有限的序列通 信，直到停止为止。 2 2 1 2 循环算子( r e c u r s i o n ) 3 1 如前一节所讲，前缀算子只能描述有限的通信，但是对于描述能够无限次通 信的进程时我们应该怎么办呢? 这里我们便引入了循环算子。 举一个例子，一个灯在它使用寿命内的开关情况我们用c s p 描述如下： l i g h t = o nj 够寸l i g h t ( 2 2 ) 等式的左边我们叫做循环算子中的进程名，而等式的右边我们叫做循环式子 的进程体。由此便定义了循环算子，即一个等式的左边所表示的进程名必须出现 在等式右边里。 此外，我们可以定义多个等式来取代一个等式所描述的循环算子，我们称为 相互循环算子。比如我们可以将等式2 1 等效的改为： l i g h t = o n p ( 2 3 ) p = o f f - - l i g h t( 2 4 ) 2 2 1 3 输入输出算子【4 】 我们定义c 是一个传输通道的名字，通道的类型位z ，而该传输通道中传输的 数据值为 ，数据类型为z 。那么我们定义输出算子为： e v 寸尸 ( 2 5 ) 4 第二章c s p 基本理论 它的含义是进程沿着传输通道c 输出值为y 的数据，接着进程的行为与进程p 相同。同理我们也可以定义输入算子，如下所示： e ? x ? r - - - y p ( x ) ( 2 6 ) 该算子描述了，进城准备从传输通道c 接收任何属于类型r 的数据，然后进程 的行为和p ( x ) 相同。 举一个例子，具有计算自然数平方功能的模块在c s p 中的描述如下： s q u a ；i n ? x ? 一0 1 4 f f ( x 21 寸s q 已_ ( 2 7 ) 、， 2 2 1 4 事件选择算子( g u a r d e dc h o i c e ) 【5 】 很多实体在所处的环境中与环境是相互作用的。这就导致实体的行为会受到 外部环境的影响。因此我们定义选择算子，如式2 5 所示： t = x 专，i y o q( 2 - 8 ) 它的含义是进程r 一开始时既可以执行事件x 也可以执行事件j ，。如果是先 执行的事件是x 则进程丁之后便按照p 进行动作；相反则按照q 进行动作。 我们继续讨论前面所讲的开门的例子。如果把一个进程定义为开门，则它就 有两种途径完成，一种是在安全模式下用钥匙进入，另外一种则是不用钥匙强行 的闯入。这便出现了一个选择： o p e n = 廊- - yo p e n - - s t o pn o t p m 专o p e n s t o p( 2 9 ) 2 2 1 5 外部选择算子( e x t e r n a lc h o i c e ) 【5 】 外部选择算子是用来描述两个或者多个进程都准备好执行他们所能执行的事 件，至于选择哪一个进程可以执行就取决于这些进程从外部所得到的第一个事件。 在c s p 我们用如下的符号来描述进程间的选择： p 口q( 2 1 0 ) 其实外部选择算子是可以和事件选择算子换的，式子2 5 就可以描述成： p 1 = x 寸p ，p 2 = y _ q( 2 1 1 ) t = p 1 口p 2 = x 专p l y q( 2 1 2 ) 之所以要描述成这样，一个比较重要的原因是要与非决定性算子相对应，因 此外部选择算子也称为决定性算子。二者的区别是决定性算子发生可以由外部的 电子科技大学硕士学位论文 输入来决定，而非决定性算子则只能由它内部决定，从外部来看它就是随机的， 不可控的。 2 2 1 6 非决定性选择算子( n o n d e t e r m i n i s t i cc h o i c e ) 【5 】 非决定性算子又称内部选择算子，它是用来描述外部环境对进程的选择是没 有影响的，完全是靠进程内部决定。定义如下： p 门q( 2 - 1 3 ) 我们在详尽的描述外部选择式子与非决定性算子的区别。对于进程 ( 口专s t o p ) 口( 6 专s t o p ) 来说，当外部环境提供事件a 或者b 的时候它都会执 行，而对于进程( 口一s t o p ) n ( 6 一s t o p ) 来说，则又可能拒绝执行。因为只有 当环境同时提供事件a 和b 的时候，它才会执行。所以前者的选择权是在于环境， 而后者的选择权则在于进程本身。 举一个例子，我们要坐车从车站回到学校，现在有两路公交车可以乘坐，分 别是3 路和4 路。当3 路或者4 路中的一辆来到面前，我们上车这个行为就叫做 外部选择，而当3 路和4 路同时到达时，我们选择其中一辆上车的行为就叫做非 决定选择，因为不是由环境来做出的选择而是我们本身。 2 2 2 进程并发【3 。6 】 前一节所定义的进程沿着一个方向执行事件，而并行进程是指用来描述由独 立进程所构成的一个系统，它们之间的通信是根据该系统的功能来定。一个进程 可以通过描述它所有潜在的行为来定义。通常，在几个不同的行为之间要进行选 择，而这种选择可以被该进程所处的环境控制。我们可以把环境也看作一个进程 从而得到包括进程和环境在内的整个系统的行为描述。系统本身也被看作了一个 进程，其行为有它的各个组成部分进程定义。这样做的好处是我们可以用简单统 一的方法来描述，分析进程，无论它是个单一进程，环境，或者整个系统。本节 将介绍用什么样的符号来表述这种并行的通信。 2 2 2 1 同步并行算子( a l p h a b e t i z e dp a r a l l e l ) 之前已经定义进程之间的通信发生的前提，即参与通信的进程必须同时同意 某一事件时，通信才能发生。而在c s p 的符号语言中，我们是通过定义进程的事 件集来描述一个进程，因此在进程之间的通信中我们也通过这样的事件集来定义， 描述如下： 6 第二章c s p 基本理论 假设x 和i r 是所有事件集的子集，进程p 允许的集合x 中的事件被执行， 而进程q 允许集合y 中的事件被执行。我们定义p 和q 的通信如下： p x i 眵q ( 2 _ 1 4 ) 它们之间要发生通信必须是两个进程同时同意事件4 ，而口x n y 。下面举 个例子： p = ( 4 争西争6 - - s t o p ) ( 2 - 1 5 ) q = ( b 斗c o b 专s t o p ) ( 2 1 6 ) x = a , b ( 2 1 7 ) l ，= b , c ) ( 2 1 8 ) 因此我们可以得到： p x i 瞳q 2 ( 口寸西一6 哼s m p ) p ，b l l b ，c ) ( 西c 专6 专s m p ) ( 2 - 1 9 ) 两个进程的事件集合的交集只有b ，因此两个进程要实现相互的通信那么就必 须同时同意事件b ，否则就是各自执行自己本身的事件。我们可以得到 p x l l rq = 口专( ( 6 专6 专s 冗炉) 口，6 池6 ，c p c 一6 专s m p ) ) = 4 专易专( p 专s 兀垆) 4 ，西) i 6 ，c p 一西斗s 冗胪) ) ( 2 - 2 0 ) = 口专6 一c 一( p 专s 冗胪) 口，6 ) ( 6 ，c ( b - - - s t o p ) ) = 口j b o c 专b 专s 阳p 最开始的时候该进程p 不同意执行事件b ，因此只有执行事件口，然后两个进 程同时同意执行事件b ；接着进程q 又阻止了事件b 的执行，这时只能执行事件c ； 最后两个进程有同意执行事件b ，因此两个进程又可以通信。 2 2 2 2 交叉并行算子( i n t e r l e a v i n g ) 前一节所介绍的并行算子的特点是，所有的进程只有同时同意某一个事件时 该事件才能被执行。那么相反，进程之间并没有这样约束就通过本节所介绍的交 叉算子来描述，定义为： 尸川q( 2 - 2 1 ) 这里进程p 和q 是相互独立的，进程可以独立的执行两个进程事件集交集之 7 电子科技大学硕士学位论文 外的事件，但是如果两个进程需要执行两个进程事件集交集以内的事件时，这时 便由两个进程随机执行。举个例子，假设口p 且口萑q ，即p = a p ，则： a 专p 川q = p 川q( 2 - 2 2 ) 假设a p 且a q ，即p - a p ，q = a 寸q 则： a - + p l l iq ：p 7i l iq i 1p l l iq ( 2 2 3 ) 2 2 2 3 顺序进程 如果p 和q 都是顺序进程，那么它们的顺序组合则用算子： p ；q( 2 2 4 ) 表示，其含义是，整个进程最开始的行为是和p 相同，当进程p 成功结束后， 那么接着的进行进程q 的行为，如果p 没有成功结束，那么q 是不会开始执行其 行为。举一个例子：当我们要去商店买东西的时候，我们把行为分为两个步骤， 第一是选择需要的商品，第二是付钱。则有： c h o o s e = s e l e c t 专( 缸印- - ) s k i p ) 口r e t u r n - - hc h o o s e ( 2 - 2 5 ) p a y = c a s ho r e c e i p t s k i p( 2 - 2 6 ) 在这里进程s k i p 表示的成功结束。因此到商店买东西这个进程用c s p 语言 描述出来便是： p u r c h a s e = c h o o s e ；p a y ( 2 - 2 7 ) 2 2 - 2 4 迹( t r a c e ) 一个进程行为的迹是由事件组成的一个序列，它描述了进程的所有可能的行 为。事件中间由逗号隔开，并且由括在一对角括号内。比如： 表示的是该迹 由两个事件组成，事件b 是发生在事件b 之后。需要强调的是任何一个进程的迹 都必须包括空集，即。 我们继续讨论前面关于开门的例子。由式2 - 6 可以得到进程o p e n 的迹为： ， ， ，) 。 前面所介绍到的算子都有相应的运算法则，这里的需要间要的介绍一部份 t r a c e 的一些运算法则，这有助于我们更好的分析进程的行为。 ( 1 ) 连接 第二章c s p 基本理论 连接是指当两个迹需要连接到一块时所用的符号： s 广、t 例如： 2 ( 2 ) 局限 局限是指将一个迹局限于一个事件集和，把该迹中不属于集合的事件去 掉而留下的迹。用符号表示如下： tf a 其中t 表示的是迹，而彳表示的是事件集和。 例如： l c o i n ) = ( 3 ) 首部和尾部 分别用函数j i l p 耐( f ) 与绷( f ) 来描述迹中的第一个事件以及除了第一个 事件所剩下的迹。 例如：h e a d ( ) = c o i n 蒯 = ( 4 ) 长度 用来计算一个迹的长度的符号：群 例如：挣 - - 4 ( 5 ) 集合中事件在迹中出现的次数 用来计算某一事件集中的事件在在一个迹中所出现的次数我们用符号 l 表示。例如： j c o i n ) - - 2 9 电子科技大学硕士学位论文 第三章v i t e r bi 译码算法原理 v i t e r b i 算法是针对卷积码的译码而提出的一种最大似然译码算法，同时它还 是一种估计一个有限状态过程中状态序列的最优算法。被广泛应用于各种数据传 输系统，特别是深空通信、卫星通信系统中。要了解v i t e r b i 译码算法原理就必须 要对卷积码有一个清晰的了解。 3 1 卷积编码【7 】 卷积码分的利用了前后各组之间的相关性，是与分组码完全不同的编码方式。 在分组码中，把k 个信息比特的序列编成n 个比特的码组，每个码组的n k 个校 验位仅与本码组的k 个信息位有关，而与其它码组无关。为了达到一定的纠错能 力和编码效率，分组码的长度一般都比较大。编译码时必须把整个信息码组存储 起来，由此产生的译码延迟随n 的增加而增加【7 】。 卷积码中，也是将k 个信息比特编成以个比特，但通常k 和刀通常很小，可以 以串行和并行的方式进行传输，延迟小。与分组码不同的是，卷积码编码后的以个 码元不仅与当前段的k 个信息有关，还与前面的一1 ( 为编码约束度，稍后会 介绍) 段信息有关，编码过程中互相关联的码源个数为n n 。 正由于在卷积码的编码过程中，充分利用了各组之间的相关性，且刀和k 比较 小，因此，在分组码同样的码率和设备复杂性条件下，无论从理论还是从实际均 已证明卷积码的性能至少不比分组码差，且实现最佳和准最佳也较分组码容易。 在编码器复杂性相同的情况下，卷积码的性能优于分组码r 7 1 。 3 1 1 卷积码的基本原理 卷积码编码器的形式如下图3 1 所示，它包括：一个由上段组成的输入一位寄 存器，每段有k 个，共l k 个寄存器，一组n 个模2 加法器，一个由力级组成的输 入移位寄存器( 串行形式) 。对应于每段k 个比特的输入序列，输出n 个比特。称工 为编码约束度，说明编码过程中互相约束的码段个数。令l = m + 1 ，称m 为编码 存储，它表示输入信息组在编码器中需要存储的单位时间。称l 4 = 工n 编码约束 长度，说明编码过程中互相约束的码元个数。所以m 或三、4 是卷积码编码器复 1 0 第三章v i t e r b i 译码算法 杂性的一重要参数。 输入 输出 12l 图3 - 1 卷积码编码器 同样在卷积码译码过程中，不仅要根据此时可输入到译码器的码元，而且还 要根据以后很长一段时间如m d 段时间内收到的码元，才能译出一个信息元，通常 m d 肌。我们称脚d + 1 = 为一码约束度，称n l d 为译码约束长度，它们分别表 示译码过程中相互约束的码段或码元个数。总之，在卷积码的各段之间，不论是 编码还是译码都不是每段各自处理，而是与前朋或者m d 有关。所以卷积码通常用 ( n , k ，) 表示，因此在本文中就是( 4 ，1 ，7 ) 。令置= k n ，称之为卷积码的码率， 它是衡量卷积码传输信息有效性的一个重要参数。 3 2v i t e r b i 译码算法原理 卷积码的译码方法可分为两大类：即代数译码和概率译码。代数译码是以卷 积码的代数表示法为基础，从码子本身的代数结构出发，通过计算伴随式，确定 错误图样后得到结果。目前用的较多的事由m a s s e y 提出的门限译码。概率译码不 仅考虑码字的代数结构，还利用了信道的统计特性，充分发挥了卷积码的特点， 使译码错误概率大大降低【s 】。 卷积码译码的概率译码最早始于1 9 6 1 年由w o z e n c r a f t 提出的序列译码，1 9 6 3 年由f a n o 进行改进，提出f a n o 算法。1 9 6 7 年由v i t e r b i 提出了另外i y i z h o n g 概率 译码算法一v i t e r b i 译码算法，它是一种最大似然译码算法，在码的约束度较小时， 它比序列译码算法效率更高、速度更快，译码器也较简单。因此，自v i t e r b i 译码 算法提出以来，无论在理论上还是实践上都得到了快速发展。下面将简要介绍 v i t e r b i 译码算法p j 。 电子科技大学硕士学位论文 3 2 1 最大似然译码【7 】 假设发送端发送码字序列c ：f c o ，c l ，c z ，1 ，接收端接收到的码字序列是 皿：f r o ，r 1 ，r 1 1 。信道的噪声丰扰导致足c ! 这给译码( 胄由推断c ) 带来 了不确定性。最好的办法是拿序列r 去和所有可能的候选码字序列 q = ( 四，弓，q ，) ( ，= l ，2 ，c q ) ) 一一对比，选出其中“最佳”的那个序列作为 译码话值序列e 。所以可能的候选码字序列定有连续的轨迹，且编码序列在q 之 中；而接收序列r 的轨迹由于存在差错，在网格图上的轨迹是连续的。这里所谓 的“最佳 ，是指具有最大后验条件概率，如式3 - 1 所示： p ( c r ) = 哗旷( 勺砷】 ， ( 3 - i ) 一般来说，信道模型并不使用后验条件概率，而只表明转移概率，因此必须 通过贝叶斯公式找到这两种概率间的关系，如式2 - 2 所示： p ( c 斛掣 隆2 ， 这里，p ( r c j ) 是发送码字序列0 而得到接收序列足的概率，也称似然度。 当各可能序列等概发送时，只9 是常数；当信道对称时尸( r ) 也是常数。在这种 情况下，m a x p ( r c j ) 与胁盯( 勺詹) 等价。此时，最大似然译码也就是“最佳 译 码。再对朋觥p ( 足c 一) 取对数： 砌g m 口x 尸c r ，c 歹，= ，垂，z o g p ( r ，c 歹1 ) c 3 3 ， ，蛔并虽非线性，但确是x 的单调增函数，因此m a x p ( r c ，) 与臌妞田7 q ) 对 q 肜q i 一致的，称后者为对数似然函数。如果说序列的似然函数是各码字似然 函数之积，那么序列的对数似然函数等于组成该序列的各码字对数似然函数之和 三是组成序列的码字的个数，p 心弓) 】是第1 个发送码字与接收码字的对数似然 度，又等于组成第1 码字的n 各码元的对数似然度之和 州。讣兰叫哆) 最大似然译码就是把似然度最大的这个序列选为译码估值序列e 输出： 1 2 ( 3 4 ) 第三章v i t e r b i 译码算法 e = 7 i 州1 = li 刀 ( 3 5 ) 显然，序列的似然度与序列长度有关。如果把码组的似然度称作分支量( b m ， b r a n c hm e t r i c ) ，把序列累计似然度蛔沪( 刚勺) 】称为路进量度( p m ，p a t hm e t r i c ) ， 那么在相同序列长度下( 长度工应足够大) ，具有最大路径量度的那个序列应选作 译码估值序列亡输出。 3 2 2v i t e r b i 算法的基本原理【刀 如前面所述，卷积码的状态图可以很好地表示在不同输入序列下编码器各状 态之间的转移关系，但并不能表示出状态转移与时间的关系。为此，便提出了卷 积码的篱笆图或网格图( t r e l l i s ) ，用来描述状态与时间之间的关系。举一个例子， 卷积编码器为( 2 ，1 ，2 ) ，其结构图如3 _ 2 1 0 所示。 输入 图3 - 2 ( 2 ，1 ，2 ) 卷积码编码器 画出该卷积码的网格图，如图3 3 所示： 出 电子科技大学硕士学位论文 图3 3 ( 2 ，1 ，2 ) 码段三= 5 时的网格图 该图由节点和分支构成，共有三+ 肘+ 1 ( 这里为8 ) 个节点，每一节点为一时 间单位，分支为输入的信息源( 图中实线表示输入为0 ，虚线表示输入为1 ) ，分 支上的数字表示为此书编码器输出的码字。如图中粗线所示为输入信息序列肘= ( 1 01 110 o ) 时的编码路径。而对一般情况下的卷积码( n n ，k o ，臃) ，便码器以 共有2 k o 朋个状态，进入和离开每一状态各有2 o 条分支，网格图上共有k o 二条 不同的路径，相应于编码器输出的z 旷各码序列。 最大似然译码过程就是根据接收到的序列，按最大似然译码准则力图找出编 码器在网格上所走过的路径，这个过程也就是译码器计算、寻找最大似然函数 h g c j ) ，j = 1 ，2 ，2 “o 。的过程，也就是说计算、寻找有最大“度量 的路径的 过程。对二进制对称信道) 而言，计算、寻找有最大度量的路径，等价于寻找与置 有最小汉明距离的路径，即寻找 m i n d ( r ，c i ， j = 1 ，2 ，2 “o 而对二进制输入o 进制输出的离散无记忆信道而言，就是寻找与足有最小软 距离的路径，此时的度量就是软判决距离 m i n d s l b ，c 凼j ， j = 1 ，2 ，2 o l 式中，气与c 商是接收序列r 与c ，序列的q 进制表示。 但是，用这种方法译码是非常难以实现的。例如l = 5 0 ，坳= 3 , k o = 2 ，则网格 图上共有2 k o = 2 1 0 0 1 0 3 0 条不同路径；如果要在一秒钟内送出这1 0 0 个信息 元，则信息传输率只有1 0 0 比特秒，这是很低的。但即使在如此低的信息速率 下，也要求译码器在一秒钟计算、比较l u 一个似然函数，这相当于要求译码器计 1 4 第三章v i t e r b i 译码算法 算每一似然函数的时间小于1 0 圳s ，这根本无法实现 7 】。 v i t e r b i 译码算法正是在解决上述困难时所引入的一种最大似然译码算法。它 并不是在网格图上一次比较所有可能的路径，而是接收一段，计算、比较一段， 选择一段最大可能的码段，从而达到整个码序列是一个有最大似然函数的序列。 其步骤简述如下【8 】： 设在实现某一步( 如第j 步) 译码时，已知如下数据： 1 卷积码的状态转移网格图 2 第l 步的接收码字是r 3 截止第，一l 步，到达各状态的候选序列与接收序列相比的最大似然度、即最 小汉明距离删( 7 1 ) ( j f ) ( ，：1 ，2 ，) 。p m ( 1 - 1 ) ( j ) 是，一1 时刻第j 个状态的路径量度 p m ( p a t hm e t r i c ) 。 4 截止第，一1 步，到达j j 、状态的最大似然序列的码元序列s ( t - 1 j ( j 1 ，也叫 做第_ ，个状态的幸存路径( s u r v i v o r ) 。这是一个能存储三个码组的移位寄存器，存 放到达该状态的具有最大似然度的路径的码字序列。 在完成一步译码时，根据已知数据需要计算如下数据： 1 根据接收码字，计算它和状态转移网格图中所有的编码输出码字的汉明 距离，即分支量度b m 。 2 从状态转移图可知，每一个状态可能由两个状态转移而来。计算这两个状态 路径量度p m l 叫，f 门分别加上各自转移的分支量度b m ，两者中最小者作为该状 态在该时刻的p m ( o j ( j ) 值。所有状态都以此更新各自的p m ( 仇j f ) 值。拥有 删，( ，) 值中最小的状态，表示该时刻到达该状态的路径是最大可能路径，即最 优路径。 3 更新p m 的过程中，已经确定了每个状态由那一个状态转移而来。根据这种 转移更新留存路径。没个状态新的留存路径为转移到该状态的前一状态的低三一1 个码字和这一步转移的编码码字组成新的上个码组，构成新的留存路径。前一状 态的最高位码字被移出，肼，f ，) 最小的状态( 此刻的p m 最小表示汉明距离最 小，等价与可能性最大) 移出的码字作为该时刻的译码输出。 以上是维特比译码算法的一步，每一步都依次计算，直至最后一位接收码字 的三个延时之后，工移位寄存器中的