（通信与信息系统专业论文）tcm技术与ldpc码的研究.pdf

摘要 信道编码技术能够带来编码增益，节省宝贵的功率资源，已经成为现代通信 系统必不可少的关键技术。本文首先介绍了v 3 4 协议中发端结构图中的各个组成 部分，对其所采用的关键技术进行了详细分析。重点研究了协议中四维网格编码 及对应的维特比译码；其次，介绍了u ) p c 码的编译码方法，用m a t u 出仿真工 具对( 1 0 0 8 ，3 ，6 ) 规则码的软判决和硬判决译码算法进行了性能仿真，分析了 g b 2 0 6 0 0 一2 0 0 6 标准中的准循环l d p c 码基于对数似然比的置信传播译码算法、最 小和译码算法和补偿最小和译码算法性能；再次，分析了密度进化的对称性条件， 进化方程和阈值现象，由于对数似然比的置信传播译码消息的概率密度在演进过 程中保持了近似高斯分布的特点，因此可以用高斯估计思想简化密度进化过程。 结合概率论知识简化门限确定过程，在确定了门限的基础上运用提前判决思想减 少译码运算量。最后对改进算法的性能及算法运算量减少情况作了仔细分析。 关键词：网格编码 置信传播算法 维特比译码器低密度奇偶校验码 高斯估计 a b s 仃a c t c h a n n e lc o d i n gt 池0 1 0 9 yw h i c hc 眦b 血gc o d i n gg a i na ds a v ev a l u a b l ep o w 盯 r 嚣o u r c eb e c 锄髓ak e yt c c h n o l o g yi nm o d e mc 0 衄1 1 1 1 i c a t i o ns y s t e i l l f i r s t l y e v c r y b l o c kd i a g r a mo fm e 仃妣s m i n 盯i nt r e c o m m e n d a t i o nv 3 4i sd i s c u s s 。di nd e t a i l t l h ev i t 盯b id e c o d e ro ft l l e4 d t c mi nt r e c o m m e n d a t l 0 nv 3 4i sr e s e a r c h e d ： s e c o n d l mt h i sp a p e fi i 咖d u c e st h ec o d i n ga n dd c c o d i n gn l e t h o d so fl d p co o d e ， p r c s 跖t 8 也ep 曲皿韶c eo f b o t hs o na n dh a r dd e c i s i o n so f ( 1 0 0 8 ，3 6 ) r c g u l a rl d p c c o d e 锄a l y z 嚣t h el l r b p ，m i n s u m 姐d0 凡c tb p b 嬲e dd e c o d i n ga l g o 五t 1 1 n l p e 响m 蛆c 铝o f t l l r e eq c u ) p cc o d c si ng b 2 0 6 0 0 一2 0 0 6s t a n d a r d n i r d l 弘t h ed e n s 时 e v o l u t i o nt h c 0 巧i sd 器c r i b 。d ，t 1 1 ep r o c so fd e l l s 时e v o l 埘o ni ss i m p l i f i e db yu s i n g g a u s s i a l la p p r o x i i n a t i o n t h i sp a p 盯1 l s e sas i m p l em e m o d t og e tt h ed e t e c t i o nt h 】r e s h o l d w 主t hm ek n o w i c d g eo fp r 曲a b i l i 碳w h i c hc a nd 。d u c cc o n s i d e r a b l e 咖p u t a t i a m o u n t o fd e c o d i n g n ep e r f b 肋a n c eo fi m p r o v e da l g 耐t l 皿a n dt h e 嘶g i n a la l g o r i t l l li s c o m p 删，a n dm e 螂o no f c o m p i l t a t i o n 锄o l l i l tr c d u c i n gi sa n a l y z e d k e y w o r d s ：t c m v i t e r b id e c o d e r l o w - d e n s n yp a r i t y _ c h e c k ( l d p c ) c o d e s b e e f p r o p a g a t i 帆p ) 柚g o d t h m g a u s s i a na p p r o x i m a 勘n 西安电子科技大学 学位论文创新性声明 本人声明所呈交的论文是我个入在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 辑 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于，在年解密后适用本授权书。 本人签名： 导师签名； 日期驰i ：! 三 日期型璺! ：坦 绪论 第一章绪论 在现代数字通信系统中，由于噪声的存在，必然导致数据传输错误，为保证 各种数据能够可靠、有效地传输，往往要利用纠错编码技术，它是提高信息传输 可靠性的一种重要手段。近年来，随着无线数字通信的发展及各种高速率、强突 发性的新业务的出现，研究并利用好纠错编码技术就显得越来越必要。 1 1 数字通信系统的结构 随着对高效、高可靠性数字通信系统的需求迅猛增长，大规模高速宽带网络 的发展使语音、图像和其他多媒体信息的传输成为可能。我们最关心的是如何在 数据源功率和传输带宽有限，系统复杂性和设备造价尽可能小的条件下实现尽可 能准确的信息传输，使信息传输的误码率最小化。 信道编码是降低信息传输错误概率的有效手段之一。为了更好地理解信道编 码在数字通信系统中的地位和作用，本文先介绍一下通用数字通信系统的基本组 成结构【i 】，如图1 1 所示。 图l 。l 数字通信系统基本组成结构 下面对图1 1 中的各个组成模块作简单介绍： 信源编码，信道编码和数字调制器组成数字通信系统的发送器，它的任务是 将信源生成的信息转换为能够抵抗信道噪声和失真以及有和于在传输媒介上进行 传输的形式。图1 1 中信源用于生成需要传输的信息，信源编码就是用二进制( 或 多进制1 序列来表示信源输出的过程，其目的是除去信源的冗余以减少通信负担， 2 t c m 技术和u ) p c 码的研究 因而也称为数据压缩。任何信源都有一个被称为信源熵的量，它表征了信源的平 均不确定程度。信源编码定理口指出信源熵是数据压缩的下界。 信道编码器的作用是在信息序列中嵌入冗余码元，提高其纠错能力。与原始 信息序列中的冗余码元不同，经过信道编码添加冗余码元的作用是减少传输中发 生的信号和码元错误，提高系统的可靠性。信道编码的基本思想是将每七个连续的 信息比特分为一组，经过适当的数学运算( 编码) 后得到 个比特的输出，这栉个比 特组成的序列称为一个码字。好的差错控制码所生成的码字应该是在码字集合中， 所有码字之间的区别尽可能大，从而使通信系统中无法纠正或检测的信道错误尽 可能少。 比特形式的信息是不适合在物理信道上传输的，数字调制器就是将这些编码 信息比特转换成适合在信道上传输的连续波形信号，调制器的基本思想是将编码 的数字序列映射成适合在信道上传输的模拟连续信号，调制器主要采取的调制方 式包括调幅、调频和调相等及其变形。 信号经过信道传输后到达接收端。在接收端中，数字解调器的作用是通过对 接收到的调制信号序列或传输码字进行最优估计，然后输出数字序列到信道译码 器。信道译码器对传输消息进行估计和判决，估计准则是根据编码准则和信道特 性而确定的，目的是使信道噪声所造成的信号判决错误最小化。 信源译码器根据信源编码准则将得到的信道译码器输出的编码信息序列经过 相应的信源译码后，得到对原始信源序列的估计并传输给用户。 1 2 信道模型和信道容量 1 2 1 信道容量的定义 在数字通信系统中，常用的信道模型主要有二元对称信道( b s c ，b i n a r y s y i n m e m cc h 锄e i ) 、a w g n 信道和衰落信道。 s h a n l l o n 定义信道容量为 c = m ”，( ，】，) ( 1 - 1 ) ，l j j 其中变量j 和r 分别代表信道的输入和输出。p ( 工) 为变量x 的概率密度函数 ( p d f ，p r o b a b i l 时d e n s i 哆f u n c t i o n ) ，( ，即为变量x 和y 的互消息。 1 2 2 信道容量与纠错码的关系 对于带宽为形，信号功率为p 的带限a w g n 信道，其信道容量为 绪论 3 。眦g z 0 + 秽 o 2 ) 其中华是噪声的双边功率谱密度。从概念上理解，信道容量c 是在误码率极低的 条件下理论上每秒能够在信道上传输的信息比特数。当信道带宽矿趋于无穷大时， 信道容量达到渐进极限值 q 2 志 ( 1 3 ) 由s h 锄o n 有噪信道编码定理的证明可知，码字的随机性越强，得到好码的 可能性越大。 信道编码定理m 每个信道具有确定的信道容量c ，对于任何小于c 的码率 矗，存在有速率为矗码长为疗的分组码及( ，掰) 卷积码。若用最大似然译码， 则随着码长的增加其译码错误概率p 可任意小，即 p s 以p 一嘛。( 1 4 ) 和 p 4 p 勘+ 1 如乓脚= 4 e 幔肿( 1 5 ) 式( 1 - 4 ) 和( 1 5 ) 中r 以和4 为大于o 的系数，岛( r ) 和匪( r ) 为正实函数，称 为误差指数，它与r 、c 的关系如图1 2 所示。图1 2 中，c 1 、c ：为信道容量， 且c 1 c 2 。 e 俾) o c 2 c l r 图1 2e ( r ) 与r 的关系 由式( 1 啕和( 1 5 ) 可以看出，信道容量c 、码长疗和错误概率p 之间的转换关系。 为了满足一定误码率p 的要求，可以用以下两类方法实现。 1 增加信道容量c ，从而使舌( r ) 增加。由c 的表达式( 1 2 ) 可知，增加c 的方 法可以采用如加大系统带宽或增加信噪比的方法来达到。例如，采用调频、调相 等宽带调制方法；增加发射机的功率；应用高增益天线；采用分集接收及低噪声 4 1 m 技术和l d p c 码的研究 器件等方法。 2 在r 定的条件下，增加分组码长以，可使p 随，l 的增加呈指数下降。但是 由于码长n 的增加，当r 保持一定时，可能发送的码字数随2 “指数增加，从而增 加了译码设备的复杂性。这种方法就是信道编码理论所指出减少误码率的另一方 向。 1 2 3b s c 和a w g n 信道的信道容量 信道就是信息传输的媒质，按照功能不同，信道可以分为调制信道和编码信 道( 这里只考虑编码信道) 。对于编译码器来说，调制器输出为连续值时的信道容 量大于输出为离散值时的信道容量，如果译码器充分利用调制器输出的软信息， 可以提高编码信道的信息速率。下面以二元对称信道( b s c ) 和二元输入加性高斯 白噪声( b 队w c n ) 信道的信道容量为例来分析软判决和硬判决的性能，深刻理 解软判决可以提高系统性能的机理。 i 二元对称信道 令图1 1 中的信道为a w g n 信道，服从( o ，盯2 ) 分布，调制器和解调器看作 信道的一部分。如果调制器使用二元波形，解调器做硬判决，则组合信道等价于 b s c 信道。信道的特性由输入集合z = o ，1 ) 、输出集合】，= o ，1 ) 和输出关于输入的 条件概率确定： 烈y = o z = 1 ) = 烈】，= l z = o ) = p( 1 6 ) 尸( r = 1 r = 1 ) = 以】，= o x = o ) = 1 一p( 1 7 ) 由a w g n 信道的性质可知，转移概率p = q ( 2 巨o ) ，巨是信号的平均能量( 对 于二元输入，平均每个信息比特的能量e = e ) ，0 = 2 盯2 是单边功率谱密度， q ( 工) = 1 2 石广e 一27 2 出，工o 输入等概时，可达到信道容量为： 。i ：= l + p l 0 9 2 ( p ) + ( 1 一p ) 1 0 9 2 ( 1 一p ) 比特符号 ( 1 8 ) 2 二元输入a w g n 信道 若a w g n 信道输入为z = ( o ，1 ) ，解调器做理想相干解调，输出】r = ( ，+ _ o 。) ( 输 出值连续，为软判决) 的条件概率密度函数为： ，0 ，x = 以) = 7 ：i p 由1 r ”一 ( 1 9 ) 当信道输入等概时，可达到信道容量为： c 。聊( 盯) = 一f 九( 石) l 。g ：( 九( x ) ) 出一三l 。g ：( 2 钟盯2 ) 比特符号( 1 1 。) 绪论 5 其中输出密度九( z ) = ( ( 1 ，a 2 ) + ( 一1 ，盯2 ) ) 2 是信道特征参量盯的函数，即 丸( 功= 志( 一2 ，删2 ，2 ，) ( 1 - 1 1 ) 根据以上两个信道容量表达式，画出容量曲线，如图1 _ 3 所示； 三i 滁羚i ，； j ?： s h a n n o n 限 ， ： 蒡弋。 形 么 圣 0246日 e m 岫卅日) 图1 3 软判决和硬判决译码的信道容量图 图1 3 可以看出，b s c 限和b p s k 软判决限之间最大的距离约有2 d b ，也就是 解调器采用软输出可以得到比硬判决高2 d b 左右的附加编码增益。在只使用一个 纠错码的情况下，软判决译码是最好的解决方案。 1 3 纠错编码的发展历史 纠错编码是数字通信系统和计算机系统的重要组成部分，1 9 4 8 年，现代信息 理论的奠基人c e ，s h 锄o n 在他的开创性论文【3 l “am 砒e m a t i c a lt h e o r yo f c o m m u n i c a t i o n ”中首先阐明了在有噪信道中实现可靠通信的方法，提出了著名的 有噪信道编码理论，奠定了差错控制码的基石。 香农定理是一个编码的存在性定理，指明了纠错码研究的方向，在那以后， 寻找能够实际应用的逼近香农极限的编码方案就成了纠错编码理论的最终目标。 纠错码口】从构造方法上可分为分组码和卷积码两大部分。 第一个实用的差错控制编码方案是r h 啪m i n g 提出的，称为汉明码，他采用的 方法是将输入数据每4 个比特分为一组，然后通过计算这些信息比特的线性组合来 得到3 个检验比特，收端通过一定的算法，不仅能够检测到是否有错误发生，同时 还能找到发生单个错误的比特位置。但这种码也存在难以接受的缺点：1 编码效 6 1 m 技术和l d p c 码的研究 率比较低，2 在一个码组中只能纠正单个比特错误。 其后m g 0 1 a y 研究汉明码的缺点，提出了高性能码字：二元g 0 1 a y 码和三元 g o l a y 码。这两种码字分别可以纠正三个错误和两个错误。在g 0 1 a y 码提出后最主要 的一类分组码是r e e d m u l l c r 码。它是m u l le r _ 在1 9 5 4 年提出，此后r e e d 在m u l l e r 提出 的分组码的基础上得到了一种新的分组码，称为r e e d m u i l c r 码，简称蹦码。r m 码与汉明码和g o l a y 码相比在码字长度和纠错能力方面具有更强的适应性。循环码 是蹦码提出之后的又一类码字，它实际上也是分组码，但它的码字具有循环移位 特性，这种循环结构使码字设计范围大大增加，同时也大大简化了编译码结构。 循环码的一个非常重要的子集就是分别由h o c q u e n 曲e m 在1 9 5 9 年、b o s e 和 r a v c h a i i d h 晡研究组在1 9 6 0 年几乎同时提出的b c h 码( b o c h 卸d h u i i h o c q u c n g l l e m ) ，b c h 码的码字长度为咒= g ”一1 ，二元b c h 码( g = 2 ) 的纠错能力为 f 2 ) 的情况，得 到了r s 限e e d s o l o m o n ) 码，此码的最大优点是其非二元特性可以纠正突发错误。 1 9 6 7 年b c d c k a n l p 给出了有效的译码算法，r s 码缛到了广泛地应用， 虽然分组码取得了很多的研究成果，但它固有的缺陷也大大限制了它的进一 步发展。首先，由于分组码是面向数据块的，因此在译码过程中必须等待整个码 字全部接受到后才能译码，导致系统时延较大；其次，分组码要求精确的帧同步， 即需要对接收码字或帧的起始符号时间和相位精确同步；另外，大多数基于代数 的分组码的译码算法都是硬判决算法，造成增益损失，若要实现分组码的软判决 译码，往往复杂性较大，基本上是随码字长度的增加而呈指数形式的增长。 e l i 豁等人在1 9 5 5 年提出了卷积码编码方法，卷积码与分组码的不同在于分组 码在编码之前先将信息序列按照一定的数据块长度分组，然后对每一组信息进行 独立编码，即对于( 月，七) 分组码来说，码字中的咒一七个校验元仅与本码字的七个信 息元有关，而与其他码字的信息源无关。卷积码中的拜一_ j 个校验元不仅与本码字 的露个信息元有关。还与之前码字的信息元有关。由于在满足一定性能要求的前提 下，卷积码的码组长度要比分组码的码组长度小一些，因此卷积码的译码相对容 易些。 卷积码的译码通常有如下几个比较流行的译码算法：1 由w j z e i l c r 血和r e i 脆n 在1 9 6 1 年提出，f a n o 和j e l i n e k 分别在1 9 6 3 年和1 9 6 9 年进行改进的序列译码算法：2 由m 笛s e y 在1 9 6 3 年提出的门限译码算法；3 由t e r b i 在1 9 6 7 年提出的t e r b i 算法， 该算法是基于码字格图结构的一种最大似然译码算法，是一种最优译码算法。 多年来，传统的信道编码思想是采用给传输的信息位增加冗余的办法来抗干 扰，因此在提高了系统可靠性的同时，也降低了系统传输的有效性，即系统的频 带有效性下降。为了解决这一矛盾，j m a s s e y 于1 9 7 4 年提出了将编码与调制作为一 个整体看待可能会提高系统性能的设想。1 9 8 2 年u n g e r b o e c k 提出的t c m 概念是解 绪论 7 决带宽和纠错这对矛盾的一个理想方案，它将纠错编码与调制技术有机结合，在 不增加系统带宽要求的条件下通过扩展符号映射空间来达到提高编码增益的目 的。t c m 技术奠定了限带信道上编码调制技术的研究基础，这在信道编码发展中 具有划时代的意义。 自2 0 世纪9 0 年代开始的十年对信道编码的发展来讲，是一个具有里程碑意义 的十年，其中最具历史意义的是t u 曲。码的提出。1 9 9 3 年在世界著名的i e e e 国际通 信会议上，缅甸籍的来自法国的博士生c b a r r o u 发表了著名的、具有深远意义的 1 i l i b o 码的论文【4 1 。论文中给出的t u i b o 码能够在长码长时逼近香农的理论极限，同 时译码复杂度也是可以接受的，t u r b o 码采用并行级联递归的编码器结构，是一种 系统的卷积码。其译码算法主要有m a p 算法、l o g m a p 算法、s o v a 算法等。但是 t 1 l i b o 码也有其缺点，它的译码复杂性仍然较大，且在码长较长时，由于交织器的 存在具有较大的时延。 随着人们对t u r b o 码的深入研究发现它其实就是一种l d p c ( l o wd s i t yp 耐t y c h e c k 码f 3 q 。u ) p c 的译码性能同样可以逼近s h a n n o n 信道容量限韬t 9 埘。已经证 明，当分组长度很大时，l d p c 码远远超出了卷积编码的性能。目前，u ) p c 码的 研究和实现是编码领域中的一个热点课题。u ) p c 码之所以引起人们极大的兴趣， 主要归结于自身的许多独特的优点。 首先，l d p c 码被证明是好码，当码长趋近于很大的时候，l d p c 码的最小码 距和码长的比趋近一个常数而不是零【1 1 】。目前看来，这个特点是l d p c 码独有的； 其次。m a c k a y 和n e a j 的研究表明，采用优化设计的l d p c 长码可以达到t u r b o 码的性能。最近的研究表明在非规则图上构造的u ) p c 长码的性能已经非常接近香 农限，这也是引起理论界极大关注的主要原因1 1 0 j 2 】： 第三，l d p c 码的译码算法是一种基于稀疏矩阵的并行迭代译码算法，并且由 于结构并行的特点，在硬件实现上比较容易； 第四，l d p c 码的码率可以任意构造，也可以由打孔得到，有更大的灵活性； 第五，在采用了新的编码算法之后f 1 3 】，u ) p c 码的码长和码距还可以进步增 加，使得性能也可以有很大的提高。同时由于不可检测错误很少，所以对实现混 合a r q 技术系统的无错误传输有很大的优势； 第六，根据计算机仿真分析。u ) p c 码具有极低的错误平层，在低误码率传输 要求下，u ) p c 码具有巨大的优势 1 4 】。 1 4 论文结构及内容安排 本文作者所完成的工作主要分以下三大部分：1 对v 3 4 协议进行详细描述， 对其中四维网格编码与收端相应的v i t e r b i 译码算法性能进行仿真；2 掌握u ) p c 码 8 t c m 技术和u ) p c 码的研究 的编码方法，结合g b 2 0 6 0 0 2 0 0 6 标准，对标准中给出的q c l d p c 码的结构和对应 的译码算法做详细的介绍，在加性高斯白噪声信道下对其进行仿真；3 研究 l l r b p 算法的密度演进及其高斯估计分析，设定判决门限，对每次迭代输出的位 信息进行提前判决，以此减少迭代次数降低译码运算量，定性的与未使用该准则 的情况进行比较和分析。 论文分五章，第一章为绪论部分，介绍了信道编码的基础理论和纠错编码的 发展状况： 第二章系统地介绍了基于v 3 4 协议的m o d 锄的关键技术，同时简要给出了卷 积编码，网格编码和v i t e r b i 译码的基本原理，并针对协议中信道编码部分一四维网 格编码及其维特比译码进行深入的研究，给出实际性能的仿真结果； 第三章简要介绍u ) p c 码的编译码的基本原理。对数字电视地面广播传输系统 中的q c l d p c 码和码率为0 5 的( 1 0 0 8 ，3 ，6 ) 规则码的各种译码算法进行仿真； 第四章着重研究了密度进化原理和高斯估计，运用位信息的高斯特性和概率 论知识计算每次迭代时节点的判决门限，用及早判决思想减少译码运算量，加快 译码速度： 第五章对全文工作进行总结，并展望了未来的研究工作。 第二章v 3 4 协议中t c m 技术和v i t 目伽译码 第二章v 3 4 协议中t c m 技术和v i t e r b i 译码 2 1 卷积码和维特比译码基本原理 2 1 1卷积编码的基本原理简介 卷积码是1 9 5 5 年由爱丽斯( e l i 勰) 提出的，与分组码不同，卷积码的个 校验码不仅与本组的k 个信息元相关，而且还与以前各时刻输入至编码器的信息 组相关。正由于这些相关性，再加上和较小，在与分组码相同的码率和设备 复杂皮下，卷积码的性能至少不比分组码差。 卷积码除了像分组码一样利用多项式或者生成矩阵等形式来表示外，也可以 结合自身的特点，利用状态图，树图及网格图等形式来描述。 以( 2 ，1 ，2 ) 卷积码编码器为例，图2 1 ，2 2 分别为此编码器的结构图和网格图。 输 列y o ，m 图2 i ( 2 ，1 ，2 ) 卷积码编码器 对图2 1 ，( 2 ，1 ，2 ) 卷积编码器由两个移位寄存器和两个模2 加运算单元组成。 每次当1 个新的信息比特到来。就把移位寄存器右移i 位，将新比特位移入，这 时两个异或运算单元重新计算新的编码比特作为编码输出。两个编码比特乩，) ，与 d 1 ，d 2 ，u 之间的关系是： y 0 = d 1 0 d 2 0 u( 2 1 ) 儿= d 2 0 u( 2 - 2 ) 移位寄存器d 1 和d 2 的更新情况为： 一 d 2 = d 1 ( 2 3 ) d 1 = u ( 2 _ 4 ) 图2 2 中，实线表示输入为0 时所走的分支，虚线表示输入为1 时所走的分 支。任给定一个信息序列在网格图中就存在一条特定的路径，举例说明，如 u = ( 1 叭l l o o ) ，其输出编码为c 1 11 0o o0 11 00 l1 1 ) ，它即为上述网格图中粗黑线 所表示的路径。两个不同的信息序列将由网格图上不相重合路径段来区分。网格 1 0 t c m 技术和u ) p c 码的研究 图是研究维特比译码算法的重要工具。 口= 0 0 6 = 1 0 c = 0 1 疗= 1 l ，印i2 图2 2 ( 2 ，l 。2 ) 卷积码网格图表示法 2 1 2维特比译码原理介绍 卷积码的译码基本上可分为两大类型：代数译码和概率译码，概率译码是实 际中最常用的卷积码译码方法。而1 9 6 7 年维特比( t 砷i ) 引入的维特比译码算法 被小村( o m l l r a ) 证明等价于求通过一个加权图的最短路径问题的动态规划解，后来 福尼( f o m e y ) 又指出维特比算法实际上就是卷积码的最大似然译码算法。 维特比译码算法是建立在网格图上的一种算法，它的基本思想是依次在不同 时刻，= 埘+ l ，m + 2 ，所+ 3 ，研+ 三( 册为卷积码寄存器个数，为输入信息组长度) ， 对网格图中相应列的每个点( 它对应于编码器中该时刻的一个状态) ，按照最大似然 准则比较所有以它为终点的路径，只保留一条具有最大似然值的路径，称它为幸 存路径，而将其它路径弃之不用。故到下一个时刻只要对幸存路径延伸出来的路 径继续比较即可。在时刻，= 三+ 胧所留下的一条路径就是所要求的最大似然译码 的解。具体步骤如下： ( 1 )从f = 历时刻开始，对进入每一状态的所有分支的部分路径，计算部分路径度 量。对每一状态的所有部分路径进行比较，挑选出具有最大度量的分支，存 储其分支度量，将此部分路径称为幸存路径。 ( 2 )，；，+ 1 ，计算此时刻进入每一状态的所有分支的分支度量，并与和这些分支 相连的前一时刻的幸存路径的度量相加，对每一状态，选取并存贮具有最大 度量值的路径作为幸存路径，删去其它路径，因此幸存路径又增加了一个分 支。 ( 3 ) 若， 三+ 肌，则重复步骤( 2 ) ，直至= l + 小为止。 第二章v 3 4 协议中t c m 技术和t e r b i 译码 维特比算法有两方面的优越性：1 路径度量的可加性，网格图的格子结构， 使得每次局部判决等效于全局整体最优化的一部分；2 局部判决及时去掉了大量 非最优路径，去掉重复部分不计算，从而大大的减少了运算量。 2 1 3t c m 技术原理及译码流程 u n g e r b o e c k 于1 9 8 2 年提出的网格编码调制( t c m ) 技术【“，1 7 1 是将纠错编码和调 制信号结合起来进行设计，这样能够克服一般纠错编码在提高功率利用率时使频 谱利用率下降的缺点。在t c m 中用扩展信号集来提供编码冗余度，并通过集分割 增加信号点间的欧氏距离以获得编码增益。但其中部分增益将用于补偿因信号集 扩展带来的信号点间距离减少所降低的功率利用率。 2 1 3 1t c m 编码基本结构 t c m 系统一般由卷积码器和符号映射器两部分组成，其一般结构为图2 3 所 示： x ：4 x z ? x ， ，： 工： 信号映射 选择子 集中的 信号点 一 选择 子集 图2 3t c m 的一般编码结构 编码器在每个调制间隔传送m 个比特，选取其中朋m 个比特进行码率为 m ( m + 1 ) 的二进制卷积编码，得到的_ ，l + 1 个比特用于选择子集，剩余的m 一所个 比特用于选择相应子集中的信号点。 2 1 3 2t c m 编码的集分割原理 t c m 技术的基础是信号空间的“集分割映射”( m a p p i n g b ys c t p a r t i t i o n ) 方法， 以1 6 q a m 为例说明，图2 4 为其集分割示意图： ( 1 ) 首先将星座图划分为两个子集( s u b s 哪曰o 和b 1 ，并分配比特位y 0 作为它 们的映射，此时子集中星座点的最小距离为，= 2 。； ( 2 ) 继续进行，将两个b 类子集分别划分成两个c 类子集，并用比特位y l 来 t c m 技术和l i ) p c 码的研究 映射，此时c 类子集中星座点的最小距离为：= 一，子集的数字编号用比特位 y l y o 的表示。 ( 3 ) 依此类推，我们得到的d 类子集有，= - ：，此时每个子集中只有两 个星座点，把它们分别用y 3 等于o 或l 来表示，集分割映射过程结束。 此时每个星座点( 即调制波形) 都分配到一个唯一的码字y = y 3 y 2 y l y o 。 y o = o b o o o 一 o o o o y l = o 1 c o c 2 ，- ：j 。o b 1 ：z 一， c 弋sa c s o o ooo o oo o oo i o j o z o o oobo 。影。s 。s 影- 。， oo o o 0 ooooo o ooo o oo o oo o o ooa 、ooo 。 y 3 = 0 1 o1olo1o1o1ol o 1 瞬圈豳暇豳豳蠲圃圈豳圆圈豳豳匿隧 坤d 【l l l ol o l oo l l ou i oo 呻l lo l o li i o l拟ll o l l o l l l u u 图2 41 6 。a m 信号的集分割映射 总之，集分割映射过程就是根据信号星座的对称性不断地把一个较大的信号 集分割成两个较小