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

兰州天擘硕士荦位毕业论文 摘要 本文提出了一种高速v i t e r b i 译码器的f p g a 实现方案。这种v i t e r b i 译码器 的设计方案既可以制成高性能的单片差错控制器，也可以集成到大规模a s i c 通 信芯片中，作为全数字接收的一部分。 本文所设计的v i t e r b i 译码器采用了基四算法，与基二算法相比，其译码速 率在理论上约提升一倍。加一比一选单元是v i t e r b i 译码器最主要的瓶颈所在， 本文在加一比一选模块中采用了全并行结构的设计方法，这种方法虽然增加了硬 件的使用面积，却有效的提高了译码器的速率。在幸存路径管理部分采用了两路 并行回溯的设计方法，与寄存器交换法相比，回溯算法更适用于f p g a 开发设计。 为了提高译码性能，减小译码差错，本文采用较大译码深度的回溯算法以保证幸 存路径进行合并。实现了基于f p g a 的误码测试仪，在f p g a 内部完成误码验 证和误码计数的工作。 与基于软件实现译码过程的d s p 芯片不同，f p g a 芯片完全采用硬件平台 对v i t e r b i 译码器加以实现，这使译码速率得到很大的提升。针对于具体的f p g a 硬件实现，本文采用了硬件描述语言v h d l 来完成设计。通过对译码器的综合 仿真和f p g a 实现验证了该方案的可行性。译码器的最高译码输出速率可以达到 6 0 m b p s 。 关键词：v i t e r b i 译码器基四回溯f p g av h d l 兰州大学硕士学位毕业论文 a b s t r a c t t h ef p g a i m p l e m e n t a t i o no fah i g h - s p e e dv i t e r b id e c o d e ri sp r e s e n t e di nt h i s a r t i c l e n o to n l yt h i sd e s i g nc a nb em a d eah i g h - p e r f o r m a n c es i n g l ee r r o rc o n t r o l l e r , b u ta l s oc a nb ei n t e g r a t e di na s i cc o m m u n i c a t i o nc h i pa sd e p a r t m e n to ff l a i ld i g i t a l r e c e i v i n g r a d i x - 4a l g o r i t h mi sa d o p t e di n t h i sa r t i c l e t h es p e e do fv i t e r b id e c o d e ri s p r o m o t e dt w i c et h a nr a d i x - 2a l g o r i t h m a d d - c o m p a r e s e l e c tu n i ti st h em a i n b o t t l e - n e c ko ft h es p e e d f u l lp a r a l l e ls t r u c t u r ei sd e s i g n e d t h em e t h o di se f f i c i e n t l y p r o m o t e dt h es p e e d ，a l t h o u g ht h ea l e ao fh a r d w a r ei si n c r e a s i n g i nt h es u r v i v o r m a n a g e m e n t , t w op a r a l l e lt r a c e b a c km o d u l ei sd e s i g n e d ，t r a c e - b a c ka l g o r i t h mi s b e t t e rt h a nr e g i s t e r - c h a n g ea l g o r i t h mf o rd e s i g n i n go nf p g a i no r d e rt oi m p r o v i n g t h ep e r f o r m a n c eo fd e c o d e ra n dr e d u c i n gd e c o d e i t o r , m o r ed e c o d ed e e pi sa d o p t e d i nt r a c e - b a c ka l g o r i t h mf o re l l s u r et h a tt h es u r v i v o rp a t hc a l lc o m b i n et o g e t h e r f p g a b a s e de r r o r - r a t ed e t e c t o ri si m p l e m e n t e d , a n de l t o rd e t e c t i n ga n de r r o rc o u n t i n ga r e c o m p l e t e do nf p g a d i f f e r e n tf r o md s pc h i pb a s e do ns o f t w a r er e a l i z a t i o no fd e c o d i n gp r o c e s s ， f p g au t i l i z e sh a r d w a r ep l a tt or e a l i z et h e t e r b id e c o d e r , a n dt h es p e e do f d e c o d i n g i si m p r o v e dg r e a t l y t h eb e h a v i o ro f d e s i g ni sd e s c r i b e di nv h d lf o rf p g ah a r d w a r e i m p l e m e n t a t i o n s y n t h e s i z ea n df p g ai m p l e m e n t a t i o ns h o w st h a tt h i sd e s i g ni s f e a s i b l e t h em a x i m a ld a t ao u t p u ts p e e do f t h i sd e c o d e ri s6 0m b p s k e y - w o r d ：v i t e r b id e c o d e r ：r a d i x 4 ：t r a c e - b a c k ：f p g a ：v h d l 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发 表的成果、数据、观点等，均已明确注明出处。除文中已经注明 引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以 明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：皇夺日期： 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：玉z ! 兰导师签名：盘! j 鱼 日期：唑如 兰州大肇硕士擘住毕业论文 引言 信道编码的目的是提高信息传输或通信的可靠性，卷积编码与维特比 ( v i t e r b i ) 译码是信道编码中的一种编译码方式。在c d m a 的i s - 9 5 标准、3 g p p ( 第三代移动通信伙伴关系) 的w c d m a 标准，以及c c s d s ( 空间数据系统咨 询委员会) 的p l a n e t a r y 标准都将卷积码作为实时要求较高业务的信息纠错编码， 使v i t e r b i 译码器成为第三代移动通信系统及卫星通信系统的重要组成部分。高 速v i t e r b i 译码器的设计与实现也成为了当今科技研究的热点。 研究利用现场可编程门阵列( f p g a ) 来实现高速率、大约束度的v i t e r b i 译 码差错控制器具有十分现实的意义。就国内现状来说，在有关工程项目中已经有 3 0 m b p s 的v i t e r b i 译码需求，目前专业a s i c 已经能够实现，但是对v h d l 核 心i p 模块的开发有利于集成译码器的完全国产化。用硬件描述语言编写逻辑， 用f p g a 来实现，同时为a s i c 设计做好实验准备。 随着电子技术的不断发展与进步，现场可编程逻辑门阵列( f p g a ) 作为一 种可编程逻辑器件，其制造工艺日臻完善，超大规模、高速、低功耗的新型f p g a 不断出现。在新一代的f p g a 中甚至集成了中央处理器或数字处理器内核。电子 技术的快速发展使得实现高速译码器成为可能，同时也激发了人们对v i t e r b i 译 码算法研究的热情，拥有上百万逻辑门电路的f p g a 的出现使串行处理逐渐被并 行处理所取代，流水线技术的应用也使得原来需要几个时钟完成的工作合并到一 个时钟完成。新的高效算法不仅提高了译码器的译码速率，同时也使译码准确率 得到提高。 本文第一章在介绍卷积编码和v i t e r b i 译码基本概念的同时，对影响v i t e r b i 译码性能的参数进行了分析，主要的算法将在第二章提出，第三章介绍了具体的 模块划分及f p g a 设计实现后的综合仿真情况，最后在第四章通过实际的测试， 验证了设计性能。 兰州大擘硕士学位毕业论文 1 v i t e r b i 译码原理 卷积编码与维特比( v i t e r b i ) 译码属于信道编码中的一种编译码方式。信道 编码是指在数据发送之前，在信息码元中增加一些码元监督码元，用来供接 收端纠正或检查出信息在信道中传输时为干扰、噪声或衰落所造成的误码。监督 码元如何增加，纠、检错能力及其实现方法就是信道编译码的研究内容。 1 1 卷积编码 1 9 5 5 年e l i a s 发明了卷积码。它是通过异或运算使得信息码之间产生相关性， 增大信息码之间的码距，从而使得编译码具有纠错能力。由于卷积码的编码过程 充分利用了码字间的相关性，因此在码率和复杂性相同的条件下，卷积码的性能 优于分组码【i 】。 1 1 1 卷积码的基本概念 卷积码将k 个信息元编成n 个码元，与分组码不同，卷积码编码后的1 1 个 码元不仅与当前段的k 个信息元有关。还与前面的n l 段信息有关，各码字间 不再是相互独立的，码字中互相关联的码元个数为n x n 个。同样，在译码过程 中不仅从此时刻收到的码元中提取译码信息，而且还利用以后若干时刻收到的码 字提供有关信息。卷积码的纠错性能随n 的增加而增强，而差错率随n 的增加 而指数下降。对于实现复杂性相同的编译码器，在几乎所有的应用中卷积码的性 能胜过分组码。但卷积码没有分组码那样严密的数学结构和数学分析手段，目前 大多是通过计算机进行好码的搜索。 卷积码通常用( n ，k ，n ) 表示，其中n 为输出信息比特，k 为输入信息比 特，n 为约束长度，可见卷积码的编码效率为日r c = k n ，图1 1 为卷积编码器示 意图。 图1 - 1 ( 2 ，1 ，7 ) 卷积编码器示意图 这是一个n = 2 ，k = l ，n = 7 ，生成函数多项式为( 1 7 1 3 ，1 3 3 8 ) 的卷积编码器。 2 兰州大擘硕士学位毕业论文 硬件上可由一个6 比特移位寄存器构成，信息码从左端输入，在同步时钟的驱动 下每一拍右移一位。按照编码生成函数多项式( 1 7 1 8 ，1 3 3 0 ) 分两路模二和连接， 并分别将结果输出。将上一支路连接的d 触发器标为l ，未连接的d 触发器标 为0 ，则从左至右应为“1 1 1 1 0 0 1 * i t 9 转换为八进制数连接关系可表示为( 1 7 1 ) 0 。 同理，下一支路表示为( 1 3 3 ) 8 。按照上述编码算法，每l 比特信息都对应2 比 特输出，即编码效率为1 2 。实际系统通常将编码输出经并串转换后送入信道。 卷积码优异的性能使其在很多方面都得到了广泛的应用，在卫星通信中，采 用前向纠错技术可以将指定差错性能时所需的信噪比降低5 6 d b ，这一编码增 益可以直接转换为所需卫星有效全向辐射功率( e i r p ) 的等量降低。 1 2 卷积码的表示方法 卷积码的表示方法主要有三种：卷积码生成函数多项式、状态转移图和网格 图。生成函数多项式的表示方法最为直观，状态转移图的表示方法可以清楚地表 现出卷积码是一个m o r k o v 的过程，马氏定理是指：当前状态概括了编码器的历 史信息，以前的状态不会影响将来的状态或者将来的输出分支【2 】。网格图则表 现了卷积码的编码路径，在v i t e r b i 译码过程中，实际是通过网格图生成本地码 与接收码比较取最大似然输出，因此网格图对了解v i t e r b i 译码过程最为重要。 以下主要介绍状态转移图和网格图。 为简单起见，以( 2 ，i ，3 ) 卷积编码系统为例，说明卷积码中的状态转移 图和网络图。该系统的编码多项式为( 7 8 ，5 s ) 。与图1 1 比较易见，( 2 ，1 ，3 ) 编码系统共有两个d 触发器。将这两个d 触发器按顺序排列，共可表示4 种状 态，卷积编码的状态如图l - 2 所示。当有新的信息移入移位寄存器，旧的信息移 出时，寄存器内容更新，就称作系统产生了状态转移。 图1 - 2 ( 2 ，1 ，3 ) 卷积编码的状态转移图 3 兰竺苎兰! 主兰苎兰兰堡圭 将每一时刻所有可能的状态用节点表示，并将从某一时刻到下一时刻的状态 转移用连线表示，这样构成的图称作网格图，如图1 - 3 所示a 它可以清楚地表示 编码路径。 输码t 0 l 1lo0 扶态 输出码 1 0 d l 1 1 1 00 i1 0“ 1 1 0 l o o i l1 0 0 ll o0 li l 图卜3 ( 2 ，1 ，3 ) 卷积编码的网格图表示 图1 3 是假设初始状态为“o o ”，即移位寄存器初始值为零。第一个输入的 信息比特为“l ”，则新状态的低位是“l ”，原状态数向高位移动1 比特，舍去高 位后得到新状态为“1 0 ”。同理可以得到以后每一次状态的转移结果。显然，如 果初始状态不为零，对应的输出结果和路径都应与图1 3 不同。这实际上是由于 卷积编码的约束特性使得状态转移不但与当前输入有关，而且与前面的若干信息 有关( 状态转移决定路径，而不同的路径有不同的输出) 。理论与实际都已证明， 当约束长度变大时，纠错能力提高。 1 2 维特比译码 卷积码的译码方法主要有代数译码和概率译码两神。代数译码根据卷积码自 身的代数结构进行译码，计算简单：概率译码则在计算时考虑信道的统计特性， 计算较复杂。但纠错效果好。典型的算法如；v i t e r b i 译码、序列译码等。随着 硬件技术的发展，概率译码已占统制地位。1 9 6 7 年维特比( v i t e r b i ) 提出了基于 网格图( t r e l l i s ) 的最大似然译码算法v i t e r b i 算法。 1 2 1 最大似然译码 在某个卷积编译码系统中，输入信息序列n l 被编码为序列x ，此x 序列可 以用树状图或网格图中某一特定的路径来表示，假设x 序列经过有噪声的无记 忆信道传给译码器，如图1 - 4 所示。译码器得到信道输出的序列y ，并判定约束 4 兰州大擘硕士孝位毕业论文 长度为n 的2 n 个可能发送的序列中究竟是哪一个进入了编码器。设当某一特定 的信息m 进入编码器时，发送序列为x ( m ) ，接收到的序列为y 。若译码器输 出为m m ，说明译码出现了错误。 信息 序列 发送 序列 接收 序列 接收 序列 图i - 4 编译码系统模型 假设所有信息序列是等概出现的，译码器在收到y 序列情况下，若 p y x ( m ) 】珂】，x ( m ) 】对于m m ( 1 - 1 ) 则判定输出为m ，可以证明，这将使序列差错率最小。这种译码器的性能 是最佳的，称为最大似然序列译码器，条件概率p 【y x ( ) 】称为似然函数【l 】。最 大似然译码判定的输出信息是使似然函数为最大时的信息。 另外可以证明，求最大似然函数就相当于求x 和y 两个序列的最小汉明距 离【l 】。由此可知，最大似然译码的任务是在树状图或网格图中选择一条路经， 使相应的译码( 编码) 序列与接收到的序列之间的汉明距最小。卷积码系统中， 通常把这一汉明距称为度量，汉明距是v i t e r b i 译码过程中最常用也是最简单的 一种度量方法。 1 2 2 维特比译码简介 v i t e r b i 译码是接收码和本地生成码作比较，从中选择出最大可能的序列作为 输出，o l t l u r a 在1 9 6 9 年证明了维特比算法实际上就是最大似然译码算法，它的 基本操作是“加比- 选”，在每一级求出对数似然函数累加值，然后两两比较做 出选择，保留对数似然函数较大的路径，该路径称为“幸存路径( s u r v i v i n g p a t h ) ”。 当出现两条路径的对数似然函数累加值相等时，则任选一条保留。对数似然函数 累加值的计算公式如下： 假定噪声是零均值的加性高斯白噪声，而且信道无记忆性，即噪声独立地影 响各个码元。编码效率为i n 的卷积码的似然函数为： p 铆x ( 所) ) = = l o g p ( r ；, l x 。( 删) ) = 职l o g e l s _ 卜，( ，”) j ( 1 - 2 ) 其中，y i 是接收序列y 的第i 个分支，y i i 是y i 的第j 个码元，x i 是x 的第i 个分支，球是x j ( m ) 的第j 个码元。为简化算法，同时基于对数函数的 单调递增性，对( 1 - 2 ) 式取对数即可得对数似然函数累加值以幻) 。 5 兰州走擘硕士学位毕业论文 r a m ) = i 。g p ( i q x ( m ) ) = 耋l 。g p 阢( m ) ) = 茎砉l o g 尸( y ，肛，( 肌) ) ( 1 3 ) 由于在计算过程中，较早的丢弃了那些不可能的路径，从而减轻了译码的工 作量，降低了计算的复杂性。与完全比较译码相比，维特比译码算法使译码器的 复杂性不再是码字序列中所含码元数的函数。 1 3 维特比译码性能分析 影响v i t e r b i 译码纠错性能的主要参数包括码率、约束长度、判决方式和回 溯深度等。为得到具体参数对v i t e r b i 译码性能的影响，可通过m a t l a b 中的 s i m u l i n k 建立系统仿真模型，仿真不同参数条件下编译码性能的改变情况，系统 仿真模型如图i 5 所示。 o e m o d u l a t o r 图1 _ 5 卷积编码及维特比译码系统仿真模型 1 3 1 码卒对误码率的影响 卷积码的码率为r c = k n ，码率是信息码元相对于信息码元与监督码元之和 的比值，码率越小，说明监督码元相对于信息码元的数目越多，监督码元的相对 数目直接影响着译码的纠错能力。当系统码率改变时，随着码率的提高，系统的 误比特率呈现增大的趋势。由此可以说明，较高的码率虽然使传输过程中，冗余 信息减少，信道利用率提高，但系统的纠错性能要下降；而较低的码率则使系统 的纠错性能得到了增强。 如图卜6 所示，在e b n o 相同的情况下，码率为l 3 的译码性能最佳，其误 码率最低，码率为1 2 的译码性能次之。码率为2 1 3 的译码性能相对最差，误码 率最高。 6 兰州大荦硕士学住毕业论文 岔 山 邑 8 1 矗一。鼍 、： ： p 卜、。i ：、l 、k 一、 、 j ，j 鼍孓、： 、r = l = ： 一 薹 j jji i 爻 ：辱二鬻誊曩! _ e 一r c = 1 1 2： 甲 ： | ；一毗r c = ：1 1 3 ； 一一一；一一一一一一一一一； ；一一一一一一；一一一一一一一一j e b n o ( d b ) 图l - 6 码率对v i t e r b i 译码算法的影响 e b n o ( d b ) 图卜7 约束长度对v i t e r b i 译码算法的影响 7 一噬m一60一 兰州大学碰士擘位率业论文 1 3 2 约束长度对误码率的影响 维特比译码器硬件的复杂度随卷积编码器的约束长度的增加以线性方式迅 速递增。在约束长度为n 的情况下，系统的状态数则为2 卜个，进行“加比 选”过程时，需要比较2 n 个状态度量值，同时从中选择并保存2 n - 1 条幸存路径， 这使得存储单元随着约束长度的增加面成倍增长。但是n 的增加在另一方蕊也 增加了输入码元间的关联性，从而增强了系统的纠错性能，降低了差错率。 如图l 一7 所示。随着约束长度的增加，系统的译码性能得到改善。在卫星通 信系统中通常采用的约束长度为7 ，目前随着硬件集成度的不断提高，大约束长 度的译码系统得到了更为广泛的应用，如在空间通信中使用约束长度为2 4 ，甚 至更高。 1 3 。3 判决方式对误码率的影响 v i t e r b i 译码器按信道特性主要分为硬判决译码和软判决译码，其不同之处在 于分支度量的计算方法。硬判决维特比译码以序列之间的汉明距离作为量度，适 用于二进制对称信道( b s c ) ；软判决译码器的输入信息是经软判决量化后的数 据，量化的电平数与码元的可信度有直接的关系，量化电平越多，则越能精确地 接近似然函数，越能准确反映接收码元的可信度，从而使译码器的译码性能更接 近最大似然译码。但随着量化电平数目的增多，译码的复杂性也很快增长，实现 的难度也随之加大。在同一译码算法下，虽然硬判决译码较软判决译码简单而易 于实现，但在性能上要损失2 3 d b 。 由图1 8 中可以看出。由于软判决过程提供更多的中间信息，使译码器能够 更好的恢复信息序列，从而获得更佳的纠错性能。而软判决位大于3 比特后，软 判决增益增加很慢，因此通常采用3 比特量化，即8 级软判决。软判决技术已作 为一种技术标准广泛应用于各种通信系统中。 1 3 4 回溯深度对误码率的影响 随着“加比一选”运算的进行，2 ”1 个状态对应各自的幸存路径l ( l 为 要传送的所有信息长度) 不断加长，不可能用存储嚣保存所有的路径。将原始的 v i t e r b i 译码算法加以修改，每个路径存储器不必存储很大的信息序列，只需存储 t l 段信息序列即可，即译码器只需存贮幸存路径最近的t 段信息元。当接收并 处理完第t 段信息后，找出最小度量对应的幸存路径作为判决输出，这样使得第 t + l 段信息仍然可用这组路径存储器。 8 兰州大擘硕士擘住毕业论文 岔 山 巴 害 瀚i ；i 、 告i 、 丫、 搽 1 、 巍 二二弋二二 ；蕾_ 、 i 一沁 _ 卜- d e c i s i o nb i t = - 2 - - 一d e c i s i o nb i t = 3 叫卜d e c i s i o nb i t = 8 h a r dd e c i s i o n 一iii ： ：一气鼍 m 2 p j e j 2巩j#，、：、杂 寒卷2。 罐kt 一一k ； t=i：t，一置=jk i 担! ! ：n - - - 2 ：风s 葛-；、- ：妊。k 未；。x 嚣蔫 ：； ； l o o 三十t r a c e 蚰c 旧e ，：卜t r a c e b a c k 2 1 4 。乙l 。 ：。 蔓扣traceback=35 i f a c g d a c k - 。o j i 9 回溯深度对v i t e r b i 译码算法的影响 这改后的算法称为v i t c r b i 译码的截尾译码或截短译码。修改后的算法 j j | | j | | 兰州走学硕士学位毕业论文 已不再是最大似然译码，性能比最大似然译码差。然而当t 选取得当时，译码效 果近似于最大似然译码【4 】。 实践和理论分析证明，当t 5 n 时，所有幸存路径在t 段前都有几乎相同的 分支，可以将相同的路径输出。即如果所有状态对应的幸存路径在t 段前有一部 分路径重合，那么即使译码完全结束，该段输出也不会改变，现在就可以先将那 些合并的路径输出，且并不影响译码性能。因此选择5 n t 1 0 n 就可以发挥该 种卷积码在v i t e r b i 译码算法下的全部纠错能力。由于这一运算是从目前运算到 的“加一比一选”位置向前找寻幸存路径并输出，所以称为回溯运算。图1 - 9 所 示为不同回溯深度对译码性能的影响，由图中可以看出当5 n 。 t 1 0 n 时译码性 能变化不大。 1 0 兰州大擘硕士擘住毕业论文 2v i t e r b i 译码算法 v i t e r b i 译码器主要由三个模块组成，分支度量单元( b r a n c hm e t r i cu n i t ) ， 加一比一选单元( a d d c o m p a r e s e l e c tu n i t ) 和幸存路径管理单元( s u r v i v o r m a n a g e u n i t ) 。v i t e r b i 译码算法的基本步骤为：根据接收信息比特，计算出相应 的分支度量值：将进入某一状态的多条分支度量值与其前面的状态度量值累加求 和，比较到达同一状态的多条新的状态度量值的大小，选择最小者作为新的状态 度量值存储，并记录到达当前状态的路径信息值；当存储的路径信息满足译码深 度时( 约为码元约束长度的5 1 0 倍) ，从2 n 。1 个状态中选择状态度量值最小的一 条路径作为译码数据输出。 2 1 分支度量的计算 分支度量单元用于根据输入数据计算出各个可能的分支度量值。在硬判决过 程中通常采用汉明距离的累加和作为分支度量值。与硬判决v i t e r b i 译码不同， 软判决v i t e r b i 译码计算度量值时采用欧氏距离。硬判决与软判决译码的区别如 图2 1 所示。 l ； j r 。 聪 i ! ； ： ： ：以； 0 0 0 0 0 1o l o 们11 0 01 0 11 1 01 1 1软判决 、“、，一 0 ，1 硬判决 图2 - 1 硬判决和软判决译码 欧氏距离可以理解为接收到的码元在度量坐标图上距离( ( 0 0 0 ) 2 ，( 0 0 0 ) 2 ) 、 ( ( 1 1 1 ) 2 ，( 1 1 1 ) 2 ) 、( ( o o o ) 2 ，( 1 l i ) 2 ) 、( ( “i ) 2 ，( 0 0 0 ) 2 ) 的几何距离， 如图2 2 所示。经过3 比特量化后，图中用0 到7 范围内的任一对整数来描述6 4 点集中的任意一点。图中有噪点( 3 ，3 ) 与无噪点( 0 ，0 ) 的距离为 4 ( 0 - 3 ) 2 + ( 0 3 ) 2 = 3 互，与无噪点( 7 ，7 ) 的距离为( 7 3 ) 2 + ( 7 3 ) 2 = 4 互， 所得结果即为欧氏距离。这种计算方法要进行乘方和开方运算，因而降低了整体 的译码速率，并且增加了存储单元的数目。 兰州大擘硕士擘位毕业论文 ，(i 。3 o 图2 - 2 欧氏距离的计算方法 为了简化这一计算，可将量化后的值与( ( 0 0 0 ) 2 ，( 0 0 0 ) 2 ) 、( ( 1 1 1 ) 2 ，( 1 1 1 ) 2 ) 、( ( 0 0 0 ) 2 ，( 1 1 1 ) 2 ) 、( ( 1 1 1 ) 2 ，( 0 0 0 ) 2 ) 四点的矢量和作为分支度量值， 具体表达式如下： b m 0 0 = 障一0 | + l y - q b m i l = 1 x - 7 1 + 陟一7 i 删0 1 = k 一0 | + j j ，一7 | 肼l o = k 一7 | + l y 一0 l 这样可以避免大量的乘方和开方运算，降低硬件复杂度，同时对v i t e r b i 译 码器性能的影响也不大，可以满足设计要求，本文采用上述方法计算分支度量值。 另外也可用相关值作为距离度量，但在进行量化时必须采用二进制补码形式 7 】。 2 2 路径信息的生成 v i t e r b i 译码器通过加一比一选单元实现从所有可能路径中选择出最大似然 路径，加一比一选单元把前一个状态的状态度量值与当前输入信号的分支度量值 相加得到该分支的状态度量值，比较不同分支状态度量值的大小，选择最小度量 值更新该状态的度量值。加一比一选单元又被称为蝶形单元。 2 2 。1 基四( r a d i x - 4 ) 算法 编码状态寄存器每移动一位后转换为新的状态，每一个新状态都对应着两个 前导状态。如图2 3 所示，在进行从第i 步到第i + l 步的译码时，前一级相差 2 ”2 个状态的两个状态经过0 和l 路径，汇合到下一级奇偶相邻的两个状态，即 状态j 和j + 2 n 2 转移得到后一时刻的状态2 j 和2 j + l 。图中，实线为输入为0 时的路径，虚线为输入为1 时的路径。如当前状态为“0 0 1 0 0 1y 9 9 假设数据由右 端进入，那么到达这个新状态的前导状态则包括“0 0 0 1 0 0 ”和“1 0 0 1 0 0 ”。加一 兰州大学硕士学位毕业论文 比一选单元通过累加比较后存储两个前导状态中到达当前状态时状态度量值较 小的一个。 i + l 2 j 2 j + l 图2 - 3 基二算法示意图 由于前导状态只有两个，因此可以用0 和l 作为区分这一节点的标志，这一 节点标志就是幸存路径信息。这种每次状态寄存器仅移动位的算法称为基二算 法。基二算法每次运算仅产生一位幸存路径信息。 n - inn - 2n _ lnn - 2 图2 _ 4 基二算法到基四算法的转换示意图 基四算法是对基二算法的合并。将一个状态数为2 n 的网格图可分解为2 眦 个子网格图，每一个子网格图由k 个状态数为2 0 的网格图组成，通过将每一个 2 k 状态的子网格图应用a c s 循环更新的k 阶预测方法，合并为基2 0 的网格图【5 1 。 当k = - 2 时即为基四算法，如图2 - 4 所示，基四算法将基二算法中的两步合并为一 步，这种算法使前一状态可能到达后一状态的数目比基二算法增加一倍。合并后 的网格图并不影响译码性能，因为在被改变的网格图中的最优路径与原来基二的 网格图之间有着一一对应的关系，由于幸存路径信息的表示方法由原来的一位增 长为两位，在译码过程中每一步将产生两位译码结果，因此理论上基四算法要比 基二算法的译码速率快一倍，但由于在基四算法额外增加的硬件会带来相应的延 时，因此实际速率达不到理论值【6 】。 由基四算法还可推广到基n 算法，其中n 为2 的整数次幂。基二至基十六算 o l 2 3 4 5 6 7嚣鏊塞囊 一 2 m o l 2 3 4 5 6 7 兰州大学硕士擘住率业论文 法的译码速率、复杂度及硬件面积效率对比如表2 - l 所示，可以看出在基n 算法 中，随着1 1 增大，系统的速率得到提高但复杂度增大，占用的硬件资源也随之增 大。基四算法是在同时权衡速率提升与面积使用效率条件下的一种较好选择。 表2 _ 1 基n 算法复杂度及速率 t 较 基 k 理想的速率提升复杂性增长面积效率 2lill 4222l 8 334o 7 5 1 6 4480 5 2 2 2d o u b i e - s t a t e 算法 d o u b l e s t a t e 算法的基本思想在于引入冗余状态( 即将每个状态对应为两个 状态) ，利用蝶形运算的规律使加、比运算并行进行，提高热一比一选模块的工 作速率。常规a c s 模块的结构如图2 5 所示。系统按照加一比一选的顺序进行， 比较器要等待状态度量值和分支度量值累加之后才能够开始比较。 厂r 、 祟筇爪r | 弋u 图2 _ 5 常规 c s 模块结构图 由常规a c s 运算转换为d o u b l e s t a t ea c s 运算时，需要引入冗余状态。以 基二算法为例，如图2 - 6 所示将生成多项式l + d 转换为i + d + 0 x d 2 ，假设当前 状态为“0 1 0 1 0 0 ”，加入l 位冗余比特后变为“0 1 0 1 0 0 0 ”和“0 1 0 1 0 0 1 ”。 i + d 网格图 l + d 旧xd 2 网格图 o l o l 0 0 o l l o l l 0 0 o l l o l l 图2 - 6 两种等效的网格图 由于状态寄存器所产生的本地码只与前6 位状态有关，冗余状态对生成的本 地码并无影响，因此在状态转换过程中并不影响分支度量值的计算，这使得到达 同一状态的两个前导状态的分支度量值b m , 和b m ， 相同，在进行加一比一选 1 4 兰州大肇硕士学位毕业论文 操作时，可以使累加操作与比较操作并行进行。即在计算s m 7 + b m , 。和 s m j + b m ”结果之前，可以先比较s m 7 和s m ? ，选择其中较小的值与分支度 量值累加，并将结果输出寄存。d o u b l e s t a t e a c s 计算一个状态度量值的运算单 元的结构框图如图2 7 所示。 s m 7 b m d , = b m 图2 7d o u bio - s t a t e c s 模块结构图 由于引入了冗余状态，应用d o u b l e - s t a t e 算法将会使v i t e r b i 译码器的加法器、 比较器和选择器成倍增长，在实际应用中采用该算法比常规算法要多占用 2 0 - 3 3 的硬件面积【7 】。 2 2 3 度量溢出的处理 随着时钟的不断前进，加一比一选过程循环进行，旧的状态度量值与分支度 量值不断的累加产生新的状态度量值，这不可避免地会导致状态度量值的溢出。 为防止度量值溢出，通常采用两种方法进行处理，一种是每次找出状态度量值的 最小值，然后将所有状态对应的状态度量值减去这个最小值，这样就使得整体的 状态度量值向零值进行简单的归一化，这种方法使每次产生新的状态度量值时要 进行一系列的减操作；另一种常用的方法则是设定门限值，当所有度量值都超过 溢出门限时，所有值减去这个门限值。 针对v i t e r b i 算法网格图的内在关系，可以证明每一步所计算的状态度量值 的最大值与最小值之间满足以下关系： 醐f 一一踟f ms ( 一1 ) ( 删一一跗n 血) 对于( 2 ，l ，7 ) 的卷积码译码，约束长度n = 7 ，其分支度量值删一= 1 4 ， 删。= 0 ，因此状态度量间的最大差值为8 4 ，存储器需要至少7 比特，可以采 用8 比特存储，将最高位作为溢出标志位，这样满足溢出条件的最小状态度量值 为1 2 8 ( 1 0 0 00 0 0 0 2 ) ，根据差值关系，当某一状态度量值满足溢出条件时，状态 度量寄存器中所寄存的最小状态度量值为4 4 ，可以将所有状态度量值减去4 4 ， 这样可以实现整体的状态度量值向零值进行简单的归一化。 1 5 兰州走学项士学位毕业论文 基于以上方法，可以采用类似方法实现状态度量值的溢出处理。当溢出标志 位未被置为l 时，最大状态度量值为1 2 7 ( 即寄存器数值为0 1 1 1l l l l 2 ) ，该状态 度量对应的下一时刻状态度量值的最大值为1 2 7 + 1 4 = 1 4 1 ，根据差值关系，所有 状态度量值中的最大值为1 4 1 + 8 4 = 2 2 5 ，数值小于2 5 5 ，没有超出8 比特的存储 上限，因此没有数值溢出。当所有溢出标志位均为l 时，通过将该标志位置0 的方法，等同于减去了数值1 2 8 ，这种方法可以省去用于归一化的减法器，节省 了硬件资源。 2 3 幸存路径的管理 在v i t e r b i 译码器中幸存路径存储器用来保存每一级所有节点的幸存路径信 息，这些值被用于回溯单元产生译码器的译码输出。译码数据的生成常用的两种 算法分别是：寄存器交换法和回溯算法。 2 3 1 寄存器交换法 寄存器交换法采用专用寄存器作为存储主体，存储的是路径上的输入信号信 息，这种算法利用数据在寄存器中的不断交换，通过更新幸存路径实现信息译码。 在译码输出时，从一个状态到下一个状态需要把所有寄存器中的内容进行交换， 如图2 8 所示幸存路径由粗线标出，在t - - 4 时刻，寄存器中的内容为1 0 1 1 。 i u r 2 r l r 0 llllj t t k - i 1 1 1 l 1 0 1 1 l l il 毫 i 1 1 0 1 l lil l 乡 - f1 0 卜 、 1 ok ll li 一 髟 一0 1 l 叫l o ly 叫t - o ol l l ifr l i i o f- l 0 0 l- l 0 0 0 ltl t - - 0 t = - lt = 2t = - 3t - - 4 图2 - 8 寄存器交换法示意图 寄存器交换法消除了根据当前状态向前跟踪回溯的必要，并具有存储单元 少，译码延时短的优点，但由于其内连关系过于复杂，不适合大状态v i t e r b i 译 码器的f p g a 实现【8 】。 1 6 兰州走学硕士学位毕业论文 2 3 2 回溯算法 对于f p g a 设计开发，通常采用另外一种方法，即回溯法。回溯法与寄存器 交换法不同，在a c s 运算后，存储的是幸存路径信息，对于基二的算法来说， 幸存路径信息指的是下一状态来源于上支路还是下支路的信息。当输入一个二进 制数据时，到达下一状态的支路共有两条，如果上支路状态度量值小于下支路的 状态度量值，则记录上支路信息0 ；相反，记录下支路信息l 。由此可见，回溯 法可以直接对幸存路径加以更新，这就省去了额外的r a m 开销。只要知道当前 的状态信息和路径信息，就可以按照蝶形单元的关系图，根据当前的状态信息和 路径信息，从回溯起始点开始沿着幸存路径回溯，并输出译码结果。回溯法需要 不断读写存储数据，并需要延时回溯判决。回溯算法的优点是内连关系简单、规 则，缺点是译码延时较长。本文采用回溯算法实现v i t e r b i 译码。 对于回溯起始点的选择有许多方法。最佳的方法是比较所有的状态度量值， 从中选择最小值所对应的状态作为回溯起始状态；为减小运算实现的硬件复杂 性，也可以选择状态度量中的高位序列作为比较数据，选择出最小值的集合，从 中任选一个状态作为回溯起始状态；最简单的方法就是任选一个状态作为起始状 态，这种方法是基于在满足一定的回溯深度时，所有路径已合并的假设，这种方 法省去了最小值比较选择的步骤，节省了硬件开销，在回溯深度设置较大时，对 系统的译码性能影响不大【9 】。 2 4 算法仿真 本文采用c 语言对算法进行了仿真，分别仿真绘制了未编码情况和增加信 道编译码情况的误码率曲线，本算法采用( 2 ，l ，7 ) 卷积编码，3 比特软判决， 回溯深度设为4 0 ，设置采样点个数为1 1 0 8 。 2 4 1 未编码情况 由通信原理可知，误比特率与q 函数的关系为： n = q ) ，其中q 函数为q 如) = 击尹。，”方 对于采用b p s k 调制的通信方式，误比特率计算公式为： p e = t 7 ( 2 ) 兰州走擘硕士学位毕业掂文 当加入高斯白噪声时，由相关器或匹配器输出的高斯白噪声的方差为： 盯：n o ( 3 ) 盯：= 2 3 ) 其中n o 2 为高斯白噪声的双边功率谱密度，由信噪比公式可得： 熹= c 巍= 2 e b = 专j 鲁= 瓦1 由上述误码率公式可计算出在b p s k 调制情况下未经信道编码的理论误码 率值，利用c 语言程序对相应的情况进行仿真，通过设定oi 1 2 的值改变e b n o 。 由图2 - 9 中可以看出仿真结果基本和理论值相符。 2 山 邑 乎 表2 - 2 未编码情况下的误码率 e b n o ( d b ) 一864- 20 o ?3 1 5 4 82 5 0 5 91 2 5 5 90 7 9 2 40 5 理论误码率 0 2 8 5 80 2 6 2 30 2 1 8 30 1 2 9 00 0 7 8 6 仿真误码率0 2 6 7 50 2 4 3 90 1 9 3 6o 1 1 8 60 0 7 1 4 e b n o ( d b )24681 0 o ? 0 3 1 5 50 1 9 9 1 0 1 2 5 60 0 7 9 20 0 5 理论误码率0 0 3 8 5o 0 1 1 80 0 0 2 30 0 0 0 20 仿真误码率 0 0 3 4 00 0 1 1 30 0