（电路与系统专业论文）全并行viterbi译码器的fpga实现.pdf

南京理工大学硕士学位论文 垒并行v i t e r b i 译码器的f p g a 实现 摘要 对于全并行v i t e r b i 译码器的设计及其f p g a 实现方案进行了研究，并最终将用 f p g a 实现的译码器嵌入到某数字通信系统之中。 首先介绍了卷积码及v i t e r b i 译码算法的基本原理，并对卷积码的纠错性能进行 了理论分析。接着介绍了v i t e r b i 译码器各个模块实现的一些经典算法，对这些算法 的硬件结构设计进行优化并利用f p g a 实现，而后在q u a l - t l l s1 平台上对各模块的 实现进行仿真以及在m a t l a b 平台上对结果进行验证。最后给出v i t e r b i 译码模块应 用在实际系统上的误码率测试性能结果。 测试结果表明，系统的误码率达到了工程标准的要求，从而验证了译码器设计 的可靠性，同时所设计的基于f p g a 实现的全并行v i t e r b i 译码器适用于高速数据传 输的应用场合。 关键词：数字通信，卷积码，维特比算法，现场可编程门阵列 塑室堡三查兰堡主兰垡兰奎 全茎堡曼型堡里堡塑婴旦垒壅塾 a b s t r a c t t h i st h e s i sm a i n l yf o c u s e so nt h ed e s i g no fp a r a l l e lv i t e r b id e c o d e ra n di t s f p g a b a s e di m p l e m e n t a t i o n t h ed e c o d e ri sa p p l i e dt oad i g i t a lc o m m u n i c a t i o nm o d e r m o fap r o j e c t a tf i r s t ，t h eb a s i cp r i i l c i p l ea b o u tc o n v o l u t i o n a lc o d ea n dv i t e r b id e c o d i n ga l g o r i t h m a r ei n t r o d u c e d ，a n dt h ea n a l y s i so ft h ee r r o rc o r r e c t i n gp e r f o r m a n c ei sg i v e l l a f t e rt h a t ， w ei n t r o d u c es o m ec l a s s i ca l g o r i t h m sa b o u tt h er e a l i z a t i o no fa p a r a l l e lv i t e r b id e c o d e r f o rt h e s ea l g o r i t h m s r e a l i z a t i o n s ，w ea l s od i s c u s sa b o u tt h eh a r d w a r eo p t i m i z a t i o n t h e n ， at e s tm o d u l et ov e r i f yt h er e s i l k so ft h eq u a r t u s ss i m u l a t i o nw i t hm a f l a bl a n g u a g e si s b u i l t h lt h ee n d ，t h eb i te r r o rr a t e ( b e r ) p e r f o r m a n c eo ft h ea c t u a ls y s t e mi sl i s t e d a c c o r d i n g t ot h er e s u l t ，t h eb e r p e r f o r m a n c em e e t st h er e q u i r e m e n t so ft h ep r o j e c t ， a n di ta l s ot e s t i f i e st h ev a l i d i t yo ft h ep a r a l l e ld e s i g n a n dt h ed e c o d e rd e s i g n e dh e r ec a r l a l s ob eu s e di nah i g h r a t ec o m m u n i c a t i o ns y s t e m k e yw o r d s ：d i g i t a lc o m m u n i c a t i o n s ，c o n v o l u t i o i l a lc o d e ，v i t e r b id e c o d i n g ，f p g a 苌7 6 3 4 8 7 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其僳存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：彩月埚 南京理工大学硕士学位论文全并行v i t e r b i 译码器的f p g a 实现 1 引言 1 1 课题背景及意义 随着现代通信技术和计算机技术的迅速发展，每天都在不断涌现新的通信业务 和信息业务，同时用户对通信质量和数据传输速率的要求也在不断提高。由于通信 信道固有的噪声和衰落特性，信号在经过信道传输过程中，不可避免的会受到干扰 而出现信号失真。通常我们需要采用信道纠错编码来检测和纠正由信道失真引起的 信息传输错误。 现代信息和编码理论的奠基人c e s h a n n o n 在1 9 4 8 年提出了著名的有噪信道编 码定理，在定理中s h a n n o n 给出了在数字通信系统中实现可靠通信的方法以及在特 定信道上实现可靠通信的信息传输速率上限。同时，该定理还给出了有效差错控制 编码的存在性证明，从而促进了信道编码领域研究的快速发展。 卷积码是e l i a s 等人在1 9 5 5 年提出的f 2 l ，是一种非常有前途的编码方法，尤其 是在其最大似然译码算法v i t c r b 译码算法提出之后【l0 1 ，卷积码在通信系统中得 到了极为广泛的应用。其中约束长度i ( - - 7 ，码率为l 2 和l ，3 的o d e n w a l d e r 卷积码 已经成为商业卫星通信系统中的标准编码方法。在“航海家”以及“先驱者”等太空探 测器上也都采用了卷积码作为其差错控制编码方法。在移动通信领域，g s m 采用 约束长度k = 5 ，码率为1 2 的卷积码；在i s 9 5 中，上行链路中采用的是约束长度 k = 9 ，码率为l 3 的卷积码，在下行链路中采用的是约束长度k = 9 ，码率为1 2 的 卷积码。特别在第三代移动通信标准中也是以卷积码以及与卷积码相关的编码方法 作为差错控制编码方案的【8 】口 本课题来源于某卫星通信系统的前向纠错编码系统，该卫星通信系统在实现语 音通信业务中，采用约束长度k = 7 ，码率l 2 卷积编码，来提高系统的通信质量， 并保证了语音通信的实时性要求。本课题的研究不仅包括卷积编码的性能理论分 析，而且重点的介绍了v , t e r b i 译码器的硬件设计与实现的方法。在v i t e r b i 译码器 设计中我们采用了全并行的结构，使得译码器在码率吞吐量上有很大的提高，区j 此 本课题中设计的v i t e r b i 译码嚣适用于高速率的通信系统中去。 1 2 课题研究主要内容 本课题围绕某卫星通信系统的前向纠错编码系统的f p g a 实现而展开，首先对 卷积码的基本原理进行分析，并对全并行v i t e r b i 译码器的f p g a 实现方法进行详细 南京理工大学硕士学位论文全并行v i t e r b i 译码器的f p g a 实现 阐述，本文主要完成以下工作： 1 介绍卷积编码及其最大似然译码算法t e r b i 译码算法的基本原理，并理论 分析卷积编码的性能。 2 介绍v i t e r b i 算法的硬件实现方法，并以a l t e r a 公司的c y c l o n e 系列的f p g a 为 硬件平台设计并实现全并行v i t e r b i 译码器。 3 验证设计的译码器功能的正确性，并利用m a t l a b 仿真和实际系统验证所设计译 码器的性能可靠性。 1 3 论文组织结构 第一章引言。 第二章主要介绍卷积码的基本原理，其中引用较简单的( 2 ，l ，3 ) 卷积编码 为例，介绍卷积码的基本概念、基本表示方法、转移函数和卷积码的距离特性等相 关内容。 第三章我们主要介绍了v i t e r b i 译码算法的基本原理，仍然以( 2 ，l ，3 ) 卷积 编码为例，介绍了v i t e r b i 译码算法中各个操作的方法和原理，介绍了硬判决和软判 决的基本概念并推导了在b p s k ( 或q p s k ) 相干解调系统中软判决译码的差错概 率上限。 第四章我们介绍了本课题中译码器实现的硬件平台a l t e r a 公司的c y c l o n e 系列的f p g a ，我们重点介绍了该器件的嵌入式存储资源的应用。 第五章我们详细的介绍了全并行v i t e r b i 译码器的f p g a 实现，其中包括译码器 各个模块的设计和时序仿真。 第六章是本论文的结论篇，我们首先利用q u a r t u si i 软件自带的时序仿真器验 证我们所设计的v i t e r b i 译码器的功能正确性，然后利用m a t l a b 仿真和实际系统验 证我们所设计的译码器在性能上的可靠性。 2 2 卷积码基本原理 卷积码是1 9 5 5 年由e 1 i a s 等人提出的。我们在一些资料上可以找到关于分组 码的一些介绍，分组码的实现是将编码信息分组单独进行编码，因此无论是在编码 还是译码的过程中不同码组之间的码元无关。而卷积码则与分组码不同，在编码时， 本组中的n k 个校验元不仅与本组中的k 个信息元有关，而且还与以前各时刻输入 至编码器的信息有关。同样，在卷积码译码的过程中，不仅从此时刻收到的码组中 提取译码信息，而且还要利用以前或以后各时刻收到的码组中提取相关信息。 正由于在卷积编码过程中，充分利用了各码组之间的相关性，且k 和n 也较小， 因此，在与分组码同样的码率r 和设备条件下，无论从理论上还是从实际上均证明 了卷积码的性能至少不比分组码差。所以，从信道编码定理来看，卷积码是一种非 常有前途的，能达到信道编码定理而提出的码类。 2 。1 卷积码的基本概念 我们用简单的( 2 ，l ，3 ) 卷积编码为例，其编码器如图2 1 所示。 一拶 1 图毒量 g o ( n ) g 1 ) 图2 1( 2 ，1 ，3 ) 卷积编码器 可用两个多项式表示例( 2 ，l ，3 ) 编码器的输出： 6 k ( ，z ) = 工( ”) o x ( n 1 ) o x ( n - 2 ) ( 2 1 ) g ；( n ) = 工( n ) o x ( n 一2 ) ( 2 ，2 ) 根据式( 2 1 ) 和式( 2 2 ) 我们可以对一组信息码元进行卷积运算，得出编码 信息，我们注意到在每一时间单位内输入编码器一个新的待编码信息元x ( n ) ，存储 器内的数据往右移一位，同时将两个生成的编码信息元瓯( n ) 和g 1 ( ，z ) 送入信道。并 且我们还可以发现输出的编码信息元不仅和当前输入的待编码信息元x ( n ) 有关，而 且还与前两个时刻的待编码信息元x ( n 1 ) 和x ( n 一2 ) 有关，即每一时刻的输出的编 码信息元与三个时刻的待编码信息元有关。 将上述分析推广至一般的情况下，我们知道对于( n ，k ，k ) 标准的卷积编码 南京理工大学硕士学位论文 全并行v i t e r b i 译码器的f p g a 实现 来说，每一时刻输入待编码的码元个数为k ，编码后输出的编码码元个数为n ，而 当前的编码输出与当前和前k 一1 = m 个时刻的待编码信息元有关，我们称k 为约 束长度，m 为编码器中存储器的个数，并且我们称k = = r 为卷积编码的码率。 我们还应注意到编码的码元单位并不一定是单比特信息，有可能为多个比特二 进制信息组成的信息字，这是更一般的卷积编码的表示，可以在很多文献中找到相 关的介绍，我们在这里不再赘述。 2 2 卷积码的表示 卷积码的表示方法主要有多项式矩阵表示法、状态图表示法和网格图表示法三 种，多项式矩阵表示的方法多用于介绍卷积码的代数译码方式，而在介绍v i t e r b i 译码算法时我们习惯于采用后两种表示方法，因为它们比较直观的表现了编译码过 程中各状态的转移关系。 2 2 1 状态图法 我们仍然用( 2 ，1 ，3 ) 卷积编码为例，根据两个编码多项式公式可计算并绘 制出该编码系统的状态图，如图2 2 所示。 图2 2( 2 ，l ，3 ) 卷积码状态图表示 在图2 2 中，各状态点表示为x ( n 一1 ) x ( n 一2 ) ，并且状态之间的转移被定义为 g o ( ，1 ) ，g l ( 月) n ) 。所谓状态就是指在编码器中d 触发器所存储的内容，而状态转 移贝u 指出了状态转移的路径和根据编码输入而得到的编码输出。因此我们知道编码 的输出是与输入相联系的，输入的变化决定了输出的变化，假定有k 个输入，则应 4 南京理工大学硕士学位论文全并行v i t e f b i 译码器的f p g a 实现 该对应2 个状态转移路径。 状态图表示的方法提供了一个比较直观的完整的编码系统描述，但是它的缺点 是不能描述随着时间变化系统状态转移的轨迹，因此我们引入了下面的网格图表示 法。 2 2 2 网格图法 在网格图中，一个结点代表着在某个时间点上的状态，而结点之间的连线则代 表着状态之间的转移，在图2 3 中，我们注意到输入信息并没有出现在连线的标签 上，但是我们却可以在状态转移的结点状态x ( n ) ，x ( n - d 中找到前一输入x 。 在图2 t 3 中，我们表示出了两个不同的网格图，它们的不同之处仅仅在于目标 状态的顺序的不同，这样重新制定目标状态顺序的原因在于可以提高计算效率。第 二种网格图表示方法被称为“蝶形图”，这种方法将状态进行了分组，从而为特定 的硬件实现译码算法提供了方便。 图2 3 下面我们给出( 2 ， o ( 2 ，i ，3 ) 卷积编码网格图的蝶形表示 l ，3 ) 卷积编码的网格图表示，如图2 4 所示。 234 图2 4 ( 2 ，i ，3 ) 卷积编码网格图表示 南京理工大学硕士学位论文 全并行v i t e r b i 译码嚣的f p g a 实现 2 3 卷积码的转移函数 卷积码是一种线性码，根据线性码的特性我们知道，在网格图中截止到某级长 度的所有码字序列与全零码字序列的汉明距离集合，同所有码字序列与其他任何一 个码字序列的距离集合相同。因而，不失一般性，我们假设输入到编码器的是全零 码字序列。 我们利用状态图2 2 来说明获得卷积码码距特性的方法。首先，将该状态图 的每个分支注上d o = 1 ，d 1 或d 2 的标记，其中d 的指数表示对应于每个分支的输 出比特序列与零分支的输出比特序列之间的汉明距离。在状态a 处的自环可以删除， 因为它在计算码字序列与全零码序列的距离特性上不起作用。另外，我们将状态h 分成两个结点a 和e ，其中之一表示状态图的输入，另一个代表状态图的输出。图 2 5 是经过以上处理后的状态图。 图2 5 根据图2 5 中的五个节点， ( 2 ，1 ，3 ) 卷积编码状态图 我们可以列出4 个状态方程 x 。= d 2 x a + x 6 x 6 = d x 。4 - d x d 以= d x 。+ d 舅d ( 2 3 ) x = d 。瓦 卷积码的转移函数定义为丁( d ) = x 。x 。解上述状态方程，可得 r ( d ) = 焉= 舛2 d 6 + 4 d 7 + 8 d 8 + 一薹 ( 2 4 ) 这个卷积码转移函数表明：存在唯一一条汉明距离d = 5 的路径，该路径从全零路径 分叉出去后又在某给定节点与全零路径汇合。从图2 , 4 我们可以看到：这条d = 5 的 路径是a - c b e 。并且d = 5 的路径只有条。式2 4 的第二项表明：从a 节点到e 节 点有两条距离d = 6 的路径，从网格图中可看到，这两条路径是a - c d b e 和 a - c - b c _ b - e 日式2 4 的第三项表明存在4 条距离d = 7 的路径，依此类推。转移函数 给出了卷积码的距离特性。卷积码的最小距离叫做最小自由距离，用d 。表示，在 6 南京理工大学硕士学位论文 全并行v i i 既 b i 译码器的p p g a 实现 上例中，= 5 。 除了不同路径的距离特性之外，转移函数还可以给出更详细的信息。假定在由 输入t e 特为1 而引发的所有转移分支上引入一个因子n ，那么当横越每个分支时， 只有由输入比特为l 引发的转移才能使n 指数的累积值增加l 。可再引入一个因子 j 到状态图的每个分支，用它的指数来表示由节点a 到节点e 的任何给定路径所经 过的分支的数目。在上例中，我们引入j 和n 后的状态图如图2 6 所示。 ( ，。、) 彻 吧苍? j n d 2 7 迪咽 图2 6 所示状态图中的状态方程为 x 。= j n d 2 x 。+ j n x 6 x 6 = j d x 。+ j d x d x d = j n d x 。+ j n d x d x 。= j d 2 x 6 对上述方程求解x 。x 。，可得转移函数 r ( 。，) = r i i 篆；! ；巧面= ，n d 5 + j 4 n z d 6 + j 5 2 。6 ( 2 5 ) + 2 j 5 n 3 d 7 + j 6 n 3 d 7 + j 7 n 3 d 7 + ( 2 6 ) 转移函数的这种形式给出了卷积码中所有路径的特征。t ( d ，n ，j ) 展开式的第 一项表明距离d = 5 的路径长度( 分支数) 为3 ，有三个输入信息比特，其中有一个 比特是1 。t ( d ，n ，j ) 展开式的第二项和第三项表明有两个d = 6 的路径，其中一条 的长度为4 ，另外一条长度为5 。在长度为4 的路径中，4 个输入信息比特中有两个 为1 ；在长度为5 的路径中，5 个输入信息比特中也有两个是l 。由此可见，因子j 的指数表明与全零路径分叉后首次合并的路径长度，因子n 的指数表明该路径的输 入信息序列中“1 ”的个数，d 的指数表明该路径的编码比特序列与全零序列的距 离。 假设发送一个有限长度( 如l 比特) 的序列，因子j 特别重要。在这种情况下， 卷积码在l 个节点之后就截断了。这意味着截短码的转移函数可以通过把 7 查堕丝! 叁兰堡! ! 兰焦鲨兰 全茎堡兰塑堕堡塑壁堕! 竖坠兰塑l 一 t ( d ，n ，j ) e f 一处截断而获得。另一方面，如果发送一个非常长的序列，实质上是 一个无限长序列，希望抑制丁( d ，n ，j ) 对参数j 的依赖关系，令j = 1 即可。这时， 上例变为 ，( d ，j v ，1 ) = r ( d ，) = r = n d 5 + 2 j v 2 d 6 + 4 d 7 + ( 2 7 ) 我们在上面讲述求二进制卷积码转移函数的步骤很容易推广到非二进制码的 情况，我们在这里不再赘述。 2 4 二进制卷积码的距离特性 本节我们将给出码率r = 1 2 、短约束长度的二进制卷积码生成多项式及最小自 由距离。这些二进制码在下述意义上是最佳的，即当码率和约束长度给定时，它们 具有能够得到的最大的d 。表中列出的生成多项式和d 撕值是由奥登沃尔德 ( o d e n w a l d e r ，1 9 7 0 年) 、拉森( l a r s e n ，1 9 7 3 年) 尾计算机搜索方法得到的【l j 。 海勒( h e l l e r ) 为码率1 n 的卷积码推导了一种简单的自由距离的上边界，即 l ，一il d 肥s 呼f 五( n ，- 1 ) f - 8 ) 其中，l x j 表示对x 进行下取整。 生成多项式 d p 。 d ， 。的上边界约束长度k ( 八进制表示) 5755 1 51 766 2 33 578 5 37 58 8 t 3 3 1 7 11 0 1 0 2 4 7 3 7 11 0 1 1 5 6 17 5 31 21 2 1 1 6 71 5 4 51 21 3 表2 1 码率l 2 的最大自由距离码 我们在本课题中，所采用的是表中约束长度为7 的二进制卷积码，我们从表2 1 可以看到该标准的卷积码的自由距离d 。= 1 0 ，并且上限同为1 0 。 南京理丁大学硕f ：学位论文全并行v i t e r b i 译码器的f p g a 实现 3v i t e r b i 译码算法基本原理 卷积码的译码算法可分为两类：( 1 ) 代数译码，这是利用编码本身的代数结构 进行译码的，类似于分组码中的大数逻辑译码，它未考虑信道的统计特性，属于硬 判决译码，比如由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 ) 对序列 译码进行改进，提出了f a n o 算法，从而推动了序列译码的实际应用。1 9 6 7 年维特 比( v i t e r b i ) 提出了另一种概率译码算法v i t e r b i 算法，它是一种最大似然译 码算法“0 3 。在码的约束度较小时，它比序列译码算法效率更高、速度更快，译码器 也较简单。因而v i t e r b i 算法提出以来，无论在理论上还是在实践上都得到了极其 迅速的发展，并广泛的应用于各种数字通信系统，特别是卫星通信系统中。 结合前面介绍的卷积码的网格图表示法，下面我们仍然以( 2 ，l ，7 ) 卷积编 码的例子来介绍一下v i t e r b i 译码算法的基本原理。 3 1v i t e r b i 译码算法的引入 我们以( 2 ，1 ，3 ) 卷积编码为例，假定要传输的数据为：1 0 1 1 0 1 0 1 0 0 ，卷积 编码器的起始状态为最( 0 0 ) 。假定送入l ( 本例中为1 0 ) 个待编码信息元。我们 下面给出网格图所表示的该序列的编码过程，如图3 1 所示，从图中可以发现，编 码器从全为0 的& 状态出发，最后又回到瓯状态，有这样规律的码序列，我们称为 结尾卷积码序列。因此，在实际数据组帧中，在送完信息序列后，我们一般还要向 编码器再送入至少m 个全0 码，以迫使编码器回到品状态，m 为编码器中存储器 的个数。 图3 1编码过程的网格图表示 在这罩我们通过利用网格图，可以很清楚的了解卷积编码过程中各个状态之间 的相互转移的路径，及编码输出。编码输出的信息在实际传输中通过相应的调制方 9 南京理工大学硕士学位论文 全并行v i t e r b i 译码器的f p g a 实现 式送入信道上传输，在解调系统的接收端我们通常利用未经过判决的软判决值进行 译码，相关的软判决内容我们将在后面介绍，请注意在对于不同的映射和量化方式 中我们将得到不同的软判决值，在本例中我们采用3 比特二进制补码量化，在信息 未被噪声污染的理想解调情况下，编码信息0 在接收端将被映射为3 ，而编码信息 l 在接收端将被映射为_ 4 。 我们设编码器送出的码序列c ，经过离散无记忆信道( d m c ) 传输后送入译码 器的是序列r = c + e ，e 是信道的错误序列。译码器根据接收序列r ，按最大似然 译码准则力图找出编码器在网格图上所走过的路径，这个过程就是译码器计算、寻 找最大似然函数 m a x l 0 9 6p ( rc ，) j = l 2 ，s ( 3 1 ) ， 的过程，或者说译码器计算、寻找有最大“度量”路径的过程，即寻找 m a x m ( r i c ，) j = l ，2 ，s ( 3 2 ) j 的过程。式中m ( r i q ) = m a x l o g 。p ( r i q ) 是q 的路径度量，s 表示该码状态数， 且有s = 2 “。 对于二元对称信道( b s c ) 信道而言，计算和寻找有最大路径度量的路径，等 价于寻找与r 有最小欧凡里德距离的路径，即寻找 m i n d ( r ，c ，)j = l 2 ，s( 3 3 ) 但是，用上述这些办法译码是难以实现的。例如l = 1 0 0 ，n = 2 ，k = 1 ，则共有 2 “= 2 “ 1 0 ”个码序列( 或网格图上的路径) ：如果在一秒种内送出这k l = 1 0 0 个 信息元，则信息传输率只有1 0 0 b i f f s ，这是很低的。但即使是在如此低的信息传输 速率下，也要求译码器在一秒钟内计算、比较1 0 3 0 个似然函数( 或欧几里德距离) ， 这相当于要求译码器计算每一个似然函数的时间小于1 0 。os ，这是根本无法实现的。 更何况通常情况下l 不是几十，而是成百上千，因此，必须寻找新的最大似然译码 算法。 3 2v i t e r b i 译码算法简述 v i t e r b i 算法正是解决上述困难而引入的一种最大似然译码算法。它并不是在网 格图上一次比较所有可能的2 “条路径( 序列) ，而是接收一段，计算、比较一段， 选择一段最可能的码段( 分支) ，从而达到整个码序列是个最大似然函数的序列， 下面把v i t e r b i 译码算法的步骤简述如下【2 】： ( 1 ) 从某一时间单位j = m 开始，对进入每一状态的所有长为j 段分支的部分路径， 1 0 南京理工大学硕士学位论文全并行v i t c r b i 译码器的f p g a 实现 计算部分路径度量。对每一状态，挑选并存储一条具有最大度量的部分路径及 其部分度量值，称此部分路径为幸存路径。 ( 2 ) j 增加l ，把此时刻进入每一状态的所有分支度量，和同这些分支相连的前一 时刻的幸存路径的度量相加，得到了此时刻进入每状态的幸存路径，加以存 储并列去其它所有的路径，因此幸存路径延长一个分支。 ( 3 ) 若就j l + m ，则重复以上各步，否则停止，v i t e r b i 译码器得到了有最大路径度 量的路径。 由时间单位m 直至u - m ，网格图中2 “个状态中的每一个状态有一条幸存路径， 共有2 “条。但在l 时间单位( 结点) 后，网格图上的状态数目减少，幸存路径也 相应减少。最后到第l + m 单位时间，网格图归到全为0 的状态& ，因此仅剩下一 条幸存路径，也就是译码器输出的估值码序列。由此可知，在网格图上用v i t e r b i 算法得到的路径一定是一条最大似然路径，因此这种译码方法是最佳的。下面我们 将来结合实例来说明v i t e r b i 译码算法的原理和译码过程。 3 2 1 分支度量计算 我们首先来介绍分支度爨的定义，v i t e r b i 译码器接收到来自信道的经过量化后 的软判决信息，并利用该软判决信息来计算网格中各个分支的度量，分支度量的计 算就是计算接收到的软判决信息与编码输出码字的欧几里德距离。 计算欧几里得距离的公式为 l o c a ld i s t a n c e ( n ，i ) = ：i s ，( n ) 一g ，( n ) 】： ( 3 4 ) 磊。 。 其中s ，( n ) 表示解调器输出的软判决信息。我们将上式展开得到 l o c a ld i s t a n c e ( n , i ) = s ( n ) - 2 s ，( ，z ) q ( n ) + q 2 ( n ) 】 ( 3 5 ) 删j 我们又注意到s ；( ，1 ) 和g ；( ，1 ) 都为常量，因此这些项在算法中用于寻找幸存路 径的过程中可以忽略，因此上式又可以简化为 l o c a ld i s r a n c e l ( n ，i ) = 乏：s f ( ，1 ) g ，( ，1 ) ( 3 6 ) 丽4 下面举个例子说明如何使用上式来计鳟分支度量：假设某一时刻v i t e r b i 译码器 接收软判决量化数据( 3 ，- 4 ) ，则其对应的分支度量分别为： ( g o ( 行) ，g i ( ) ) = ( o ，0 ) 其分支度量为一3 1 + ( _ 4 ) 1 _ 7 ； ( g 0 ( ，1 ) ，g l 唧”= ( o 1 ) 其分支度量为3 l + ( - 4 ) ( 一1 ) = 1 ； ( g o ( 妨，g l ( 功) ；( 1 ，o ) 其分支度量为- 3 ( 1 ) + ( 4 ) l - 一l ； ( g 0 ( n ) ，g l ( h ) ) = ( 1 1 ) 其分支度量为一3 ( 一1 ) + ( - 4 ) ( 1 ) = 7 ； 南京理t 大学顾。 j 学位论文 全并行v i t e r b i 译码群的f p g a 实现 通过分支度量计算的举例可以发现q ( m 在计算过程中用单元向量+ 1 和- 1 代替 + 3 和一4 参加运算。一是因为单元向量可使度量计算变的更简单，只需要做加法和 减法运算即可，省掉乘法运算。二是因为3 和4 可以近似归一化成1 和一1 ，由分析 可知归一化对于度量相对大小没有任何影响。 3 2 2 路径度量操作 我们在这里仍然使用3 1 小节中所给出的例子，假定编码序列经过有噪信道传 输，在解调器输出端送出被噪声污染过的软判决信息，我们将这些软判决信息送给 v i t e r b i 译码器进行译码操作，下面我们首先给出表示译码过程的网格图，该网格图 清楚的表示出了译码过程中各状态的幸存路径，及其路径度量，如图3 2 所示。 渊：- 3 4 1 3 8 3 矗2 7 2 9 未52 z 362 1 - 2 石 26 1 13 - 25 卫827 14 3 2 1- 3 1 4 翟端 州引3 ，33 _2 33 1 - 3 t 3 3 1础 3 f - 4 0 0 k 争一骱t 鬟，葺弘o 0 1 慷铲i 砖k 唆儡 0 x 1 0 7 篱9 4 弑1 2 0 舟，1 0 9 谆矿1 t 2 01 3 6 弦1 2 8 、1 4 6 1 3 9 、1 4 4 1 0 崦、一。蝣k 畸yo j 螨k 、嘶 ，、二r 墨。i l l 1 r1 、。 图3 2 译码过程的网格图表示 由上面的v i t e r b i 译码算法简述我们知道，v i t e r b i 译码算法可分为两个主要的步 骤，路径度量值的更新和译码回溯。在路径度量更新步骤中，主要完成每一状态路 径度量的累加，和幸存路径的选择和存储，例如在图3 2 所示的网格图中在时刻3 的s 状态，进入状态岛前一时刻可能的状态只有氐和s ，因此我们可以计算两条 待选路径的度量 p a t h m e t r i c 0 = 9 2 + 6 = 9 8( 3 7 ) p a t h m e t r i c l = 1 1 4 6 = 1 0 8( 3 馏) 且有p a t hm e t r i c 0 p a t hm e t r i c l ，因此路径1 作为状态鼠的幸存路径，相应的路径 度量值也被存储下来，而路径0 则被删除。上述过程在实现v i t e r b i 译码算法中称之 为加比选( a d d - c o m p a r e s e l e c t a c s ) 操作。 最后，我们在图3 2 所示的网格图中，用实线标出了我们从状态晶回溯所得到 的译码路径。 南京理工人学硕：1 学位论文 全并行v i t e r b l 译码鞴的f p g a 实现 3 2 3 译码回溯操作 我们首先应该注意到，v i t e r b i 译码算法在实际应用中，为了保证一定的纠错能 力，输入的码字长度一般不应小于1 0 k ，k 为码的约束长度。因此在本例中，至 少需要接收到1 0 3 = 3 0 个码字，才能保证该卷积码的纠错能力，在这里我们假设 在时刻0 之前已经接收了至少2 0 个码字。 下面我们首先给出上面例子中表示回溯过程的网格图，如图3 3 所示。 0 0 0 1 1 0 + 1 1 译码输帆 ，? ：7 月 人。、l 火。k 。、 1 厂1 ，1 、，1 1 1 1i 1 人+ 、y 。 图3 3 回溯过程的网格图表示 从图3 3 所示的网格图中，我们可以清楚的了解回溯译码的过程，我们从瓯状 态开始回溯，按照鼠状态的幸存路径向前回溯，例如在开始的时间点上，我们由鼠 状态的幸存路径知道状态是从s 状态而来，即从状态( x ( n 1 ) ，x ( n - 2 ) ) = ( 0 1 ) 到( x ( n ) ，x ( n 1 ) ) = ( 0 0 ) ，因此得到的译码输出x ( n ) = 0 。并重复进行这个过程，最 终得到全部的回溯结果，并将此结果倒序输出，就得到了最终的译码结果如图3 3 所示。 我们从上面简单例子所介绍的译码过程可以看到该译码器完成了译码的功 能，并达到了纠错的目的。 3 3 硬判决与软判决 3 3 1 硬判决与软鼎决的基本概念 在前面v i t e r b i 译码算法基本原理的介绍中，我们用到了软判决的概念，下面我 们来介绍有关硬判决和软判决的基本原理。 设在数字通信系统中我们用b p s k 的调制方式，即用： 置( r ) = 4 2 e , rc o s ( 2 n f o t + 州2 ) ( 3 9 ) s o ( t ) = 2 点。rc o s ( 2 ，r f o t 一州2 ) ( 3 1 0 ) 来传送0 、1 两个码元，式中e 。为信号能量，t 为发送信号周期，信号通过均值为0 、 方差为仃2 = n 2 的加性高斯白噪声( a w g n ) 信道后到达接收端解调器的输入端。 利用相干解调，则解调器匹配滤波器输出的抽样电压是一均值为瓦、方差为 = n o 2 的高斯随机变量。所以，输出电压i 的概率密度函数为 尸( 茸1 1 ) = p ( 1 io)=oxpc_-(+r4e,；-noj ( 3 1 1 ) ( 3 + 1 2 ) 在硬判决解调器中，最佳判决门限为0 。当匹配滤波嚣输出的电压为负，则输出为 一1 ( 相当于0 或1 码元) ；若为正，则输出为+ 1 ( 相当于1 或0 码元) 。在数字通 信系统中与硬判决解调器相应的译码器是硬判决译码器，即硬判决译码器利用解调 器送来的已经过硬判决后的0 、1 信息来进行译码，这样的判决方式我们称之为硬 判决译码，这种判决方式结果显然会损失掉接收信号中所包含的有用的信息。 为了充分利用接收信号波形中的信息，使译码器能够以更大的正确概率判决所 发的码字，就把解调器输出的抽样电压进行量化。因而由解调器输出的供给译码器 的值就不止两个，而有q ( 通常q = 2 “) 个。另一方面若译码器直接利用解调器的 未量化的模拟电压进行译码，称为模拟译码。无论译码器利用q 进制量化值译码， 还是利用模拟量的模拟译码，统称为软判决译码。 通常，译码器利用附加的软判决信息进行软译码时比硬判决译码能得到额外的 2 3 d b 的增益。一般，若利用q = 8 或q = 1 6 电平量化，所得到的性能约与最大似 然译码的性能差不多，但其译码的复杂度却比最大似然译码要低得多。 众所周知，应用纠错码进行差错控制时，对信道的质量有一定的要求。信道质 量越好，则利用纠错码所获得的效果就越明显；反之，若信道原始误码率很高如为 1 0 - 2 ，则利用纠错码后不但没有好处，有时反而变得更坏。但软判决译码不同，在 误码率为1 0 2 l 旷范围内，能提供几乎最佳的性能。 3 3 2 软判决译码的差错概率 我们在上一节介绍了软判决与硬判决的基本原理，并且我们知道软判决译码方 式相比硬判决译码甫式可以得到2 3 d b 的增益，因此，实际中在实现v i t e r b i 译码 器时大多采用软判决译码的方式，下面我们引用参考文献【1 】中关于卷积码在软判决 译码条件下误码率的理论推导，来给出卷积码在软判决条件下的理论纠错性能。 我们首先观察图2 4 的网格图中的两条路径，它们从初始状态a 经过三次状态 转移( 3 个分支) 又回到状态a ，与这两条路径对应的信息序列分别为0 0 0 和0 1 1 ， 对应的发送序列分剐是0 0 0 0 0 0 和1 11 0 1 1 。我们用 c 。，= 1 ，2 ，3 ；m = 1 ，2 表示发送 1 4 絮 南京理工大学硕士学位论文全并行v i t e r b i 译码器的p p g a 实现 比特，其中下标j 表示第、i 个分支，下标1 1 1 表示该分支的第m 个比特。同样，我们 用 ，。，j = 1 ，2 ，3 ；m = l ，2 ) 表示解调器的输出。我们采用软判决译码，且编码序列如果 用二进制相干p s k 传输，则解调器的输出为 = t ( 2 一1 ) + 7 ( 3 1 3 ) 式中7 k 表示加性噪声，t 是发送每个编码比特所用的信号能量。 穿过网格图的第i 条路径之第j 分支的量度定义为在第i 条路径上发送序列为 嘏，m = 1 ，2 ) 而接收序列是( ，m = 1 ，2 的联合条件概率的对数，即 心= l o g p ( r ji c ：f ) ) ( = 1 ，2 ，3 ，)( 3 1 4 ) 把穿过网格图由b 个分支组成的第i 条路径的度量定义为 p m “= ( 3 1 5 ) 对于软判决译码来说，解调器的输出从统计角度可以用概率密度函数表示为 嘶旧= 志唧卜坠学j ( 3 1 6 ) 式中，口2 = n o z 是加性高斯噪声的方差。如果忽略各分支量度同等拥有的项，第i 条路径的第i 分支量度可以表示为 膨1 = ( z c j m 、一1 ) ( 3 1 7 ) m i 在此例中n = 3 。这两个路径的相对度量为 32 c m 。= ( 2 c 譬一1 ) ( 3 1 8 ) j = lm = l 32 c m 1 ) - 2 螺- 1 ) ( 3 1 9 ) 卢im = l 下面我们从理论上来分析卷积码软判决译码时的差错概率。在推导卷积码的差 错概率时，利用这类编码的线性特性可使推导简化，也就是假定发送的是全零序列， 求误判成另一序列的差错概率。 我们将上例中的式3 1 7 、3 1 8 和3 。1 9 推广至一般的情况，我们得n t 路径量度 公式3 2 0 b日 c m “= = ( 2 c ；：- i ) ( 3 2 0 ) 卢lj = tm = l 在这里，i 表示各节点的任意一条待选路径，b 是一条路径上的分支( 信息符号) 数。例如，全零路径用i = o 表示，具有路径量度 妻室堡三奎兰堡圭兰垒丝奎全蒸重型! 堡里竖塑壁垒墼 d 4 一 c m o = ( 一t + 7 ) ( 一1 ) _ f ：lm = l = 厄b 玎+ ( 3 2 1 ) j = tm = t 由于卷积码没有固定长度，可以利用网格图某给定节点上第一次与全零序列汇 合的序列的差错概率推导其性能。把在节点b 上与全零路径汇合的路径的量度首次 超过全零路径量度的概率定义为首次差错事件概率。假设和全零路径汇合的编号为 i = 1 的不正确路径与全零路径有d 比特差别，即编号i = 1 的路径上有d 个“1 ”而 其余全为“0 ”。两条路径为一对，成对比较量度c m 和c m o ，得差错概率 只( d ) = p ( c m o c m ! o ) = p ( c m ”一c m 嘶0 ) 口4 p 2 ( d ) = p 2 e f ，( 、d ，l 。) 一c 嚣) o l ( 3 2 2 ) j = zm = t 由于两条路径得编码比特除了在d 个位置上不同外，其他都相同 简化为 d 只( d ) = e ( t , n o ) _ l 所以式3 2 2 可以 ( 3 2 3 ) 式中下标? 代表两条路径中不同的d 个比特，集合 表示和该d 比特对应的译码 器输入。( 是独立的等概率的高斯随机变量，均值为一，方差为o 2 。因此， 两条相差d 比特的路径成对比较时的差错概率为 炒q c 脬瑚c 厕， ( 3 2 4 ) 式中，托= 毛“是接收端的每比特信噪比，疋是码率。 尽管我们推出了与全零路径距离为d 的错误路径的首次差错概率，但在给定节 点b 上可能有很多路径以不同的路径和全零路径汇合。实际上，转移函数t ( d ) 为 所有以不同距离与全零路径汇合于b 节点的路径提供了最完整的描述。于是，我们 通过将所有可能距离的路径的差错概率通通加起来，