（通信与信息系统专业论文）基于cmmbstimi标准的ldpc编译码器的设计与实现.pdf

摘要 摘要 l d p c ( 低密度奇偶校验) 码是最接近香农限的信道编码算法，但由子传统的 l d p c 码生成矩阵的随机性使其在硬件上难以实现。随着l d p c 译码算法领域的研 究日趋成熟和越来越易于硬件实现的发展趋势，l d p c 译码器的v l s i 实现才逐渐 成为研究者关注的焦点。嚣前在众多l d p c 译码算法中，b p - b a s e d 译码算法，也 就是常说的“最小和”译码算法及其改进算法是最易于硬件实现的。 多媒体技术和通信技术的共同发展使移动多媒体广播( 俗称“手持电视”) 成为如 今发展的一个热点。2 0 0 6 年l o 月，圈家广电总局芷式颁布了中囤移动多媒体广播 系统f 篱称“c m m b ”) 广播信道行业标准，确定了采用我匡自主研发的移动多媒体广 播传输技术( 简称“s t i m i ”) 。在c m m b s t i m i 标准的信道纠错编码技术采用的是 r s 编码和自主研发的高度结构化低密度奇偶校验码( l d p c ) 技术。 本文燕是基于以上新述的l d p c 码自身的优越的纠错性能，针对c m m b s t i m i 标准的高度结构化的l d p c 码技术特点提出了高速率，性能优越的l d p c 编码器 和译码器的硬件结构和实现。标准要求编、译码器的数据吞吐量达到1 6 m b p s 。在 有限硬件实现资源前提下，本文中编译码器的系统时钟都可达1 0 0 m h z 以上。译 码器运篇了最夺和算法( b p b a s e d ) 的一种改进算法一好一化b p b a s e d 的l d p c 译码算法，采用了符合c m m b s t i m i 标准要求的部分并行正则l d p c 译码器结 构。该设计方法在有限片上资源条件下通过一种独特的数据存储方式降低了控制 逻辑复杂度，用相对其镌l d p c 译码器较少的存储空阆，高效实现了l d p c 译码 过程中大规模数据存储调用，运算速率符合标准耍求，同时其硬件结构提高了硬 件资源的使用效率。本设计的译码器f p g a 实现采用了两套方案，分别使用了 x i l i n x 公司的v i r t e x i ix c 2 v 6 0 0 0 和v i r t e x 4 的x c 4 v l x 8 0 ，硬件开发平台使用了 项霉合作单位n x p 公司东亚研究所提供的g m a p 集成电路扳。性髭测试中，在 a w g n 信道和b p s k 的调制解调方式下，当码率为l 2 时，在信噪比s n r 为1 8 d b 时，误码率已经降至1 0 。以下，在信噪比s n r 为1 9 d b 时，误码率已经降至1 0 - 6 以 下；当码率为3 4 时，在信嗓毙s n r 为3 1 d b 时，误码率已经降至1 0 - 4 以下。与 浮点数仿真结果相比，本设计的l d p c 译码器1 2 码率性能差距只在0 。l d b 左右， 3 4 码率只在0 3 d b 左右。 关键词：l d p c 译码器，l d p c 编码器，c m m b - - s t i m i ，部分并行，b p b a s e d a b s t r a c t a b s t r a c t p c ( l o wd e n s i t yp a d 霹c h e c k ) c o d e i sk i n do fc h a n n e lc o d ea l g o r i t h mw i t ht h e p e r f o r m a n c eo ft h em o s tc l o s et ot h es h a n n o nl i m i t w i t l lt h ed e v e l o p m e n to fl d p c a l g o r i t h mw h i c hh a sah a r d w a r e - f r i e n d l yt r e n d t h ev l s ir e a l i z a t i o no fl d p cd e c o d e r i sb e c o m i n ge v e rt h ef o c u so f r e s e a r c h e r s 。 ，n l ef o r m a lv e r s i o no fm o b i l em u l t i m e d i ab r o a d c a s t i n gs p e c i f i c a t i o no fc h i n aw a s p u b l i s h e di n2 0 0 6 t h i ss p e c i f i c a t i o ni sa p p l i e df o rt h es a t e l l i t e t e r r e s t r i a li n t e r a c t i v e m u l t i s e r v i c ei n f i a s t r u c t u r e i ti sr e f e r r e da ss t i m i s t i m ii sat e c h n i q u es p e c i f i c a t i o n f o rt h em o b i l em u l t i m e d i ab r o a d c a s t i n g i no r d e rt om e e tt h er e q u i r e m e n t sm u l t i m e d i a s e r v i c ei nt h ew i r e l e s se n v i r o n m e n t sl d p cc o d e s ，t h ef e cc o d es c h e m ec l o s et o s h a n n o nl i m i t a t i o n ，i sa d o p t e di ns t i m i b a s e do nt h eh i g h l ys t r u c t u r e df e a t u r eo f 王国p cc o d ei nc 氧稔莲b s 曩轰震s t a n d a r d , w ep r o p o s e dt h eh a r d w a r es t r u c t u r ea n di m p l e m e n to fl d p cd e c o d e ra n de n c o d e rw i t h l l i g hs p e e du pt o10 0m h z t h ed e c o d e re m p l o y st h en o r m a l i z e db p - b a s e dd e c o d e a l g o r i t h m ，a n dp a r t i a l l y - p a r a l l e ls t r u c t u r ef o rr e g u l a rl d p cc o d ei nc m m b s 曩轰蠡 s t a n d a r d w i t ht h es p e c i a la p p r o a c ho fd a t as t o r a g ew h i c hd e c r e a s e st h ec o m p l e x i t yo f c o n t r o ll o g i ca n dr e d u c e st h er e q u i r e m e n tf o rm e m o r y , t h ed e c o d e rc a nr e a l i z e s i m u l t a n e o u st h ew r i t i n ga n dr e a d i n go fh u g ea m o u n to fd a t a 毽u s et w os c h e m e so f t h ef p g ai m p l e m e n to f0 1 1 1 d e s i g nw h i c hu s ev h - t e x - i ix c 2 v 6 0 0 0a n dv i r t e x - 4 x c 4 v l x 8 0f r o mx i l i n x ，a n dg m a pi n t e g r a t e dc i r c u i tb o a r da sh a r d w a r ep l a t f o r m a c c o r d i n gt oo u r t e s to fp e r f o r m a n c e ，u n d e rt h ea w g nc h a n n e la n db p s km o d u l a r , w h e nt h ec o d er a t ei sl 趁。a n dt h es i g n a l - t o - n o i s er a t i oi s1 8d b ，t h ee r r o ro fb i th a s a l r e a d yb e e nb e l o w l o q ：t h es i g n a l t o - n o i s er a t i oi s1 8d b ，t h ee r r o ro f b i ti sb e l o w l o - 6 c o m p a r e dt ot h er e s u l to fs i m u l a t i o nu n d e ri d e a ls i t u a t i o n ，t h ep e r f o r m a n c eo ft h e l d p cd e c o d e rh a s u s t0 1d bd i s t a n c ef o rr a t eo f1 2a n d0 3 d bf o rr a t eo f3 4 k e y w o r d s ：p cd e c o d e r , p ee n c o d e r , c 鹾m b s 氍隧，p a r t i a l l y - p a r a l l e l ，b p - b a s e d 图疆录 图目录 图1 1 数字通信系统基本组成1 图l - 2 数字通信系统简化系统3 图2 一l ( 1 0 ，2 ，4 ) l d p c 码二相图1 6 图2 2 环4 在校验矩阵和相应二相图中的表示1 7 图2 3l d p c 译码器并行结构示例图2 2 图2 4l d p c 译码器的率行结构示例图2 3 图2 5l d p c 译码器的部分并行结构示例图2 4 图3 1c m m b s t i m i 标准移动多媒体系统广播信道物理层功能框图2 6 圈3 2l 趁码率校验矩阵h 划分子矩阵示意图2 8 图3 33 4 码率校验矩阵h 划分子矩阵示意图2 9 图3 4 不同迭代次数( 3 9 4 4 ，2 4 0 4 ) 码的译码性能曲线图3 0 图3 5l d p c 译码器基本结构框图3 l 图3 - 6 根据标准中的校验矩阵h 丽构造的小矩阵坦3 5 图3 7 构造矩阵日，划分信息存储空间方法一。3 6 图3 8 针对构造矩阵h 。第0 到第5 列的初始化软信息存储情况。3 8 图3 - 9 针对构造矩阵砭第6 到第l l 列的初始纯软信息存储情况3 8 图3 1 0 针对构造矩阵髟，第1 2 到第1 7 列的初始化软信息存储情况3 8 图3 1 l 普通存储方法的存储空间划分方式4 0 图3 1 2 构造矩阵的“1 的特殊的顺序排号方法4 1 图3 1 3 根据特殊的顺序排号方法的存储空阉划分4 l 图3 1 4 新存储方法的存储空间划分方式4 2 图3 1 51 2 码率的数据存储示意图4 4 图3 1 6 信息节点存储模块示意图4 5 圈3 1 7 经典算法求最小值示例图。4 6 图3 1 8 “基于指针 的求最小值次小值算法示例图4 7 图3 1 91 2 码率六输入校验节点更新计算子模块4 9 图3 2 0 符号累乘模块5 0 图3 2 l 信息节点更新计算子模块。5 0 图3 2 2f p g a 设计流程5l 图目录 图4 1通用嵌入式系统开发板( m o t h e rb o a r d ) 结构框图5 7 图4 2l d p c 编码器的板上结构图5 8 图4 3 3 4 码率信息比特划分示意图5 8 图4 4 1 2 码率信息比特划分示意图5 8 图4 53 4 码率生成矩阵g 前6 9 1 2 x 2 3 0 4 部分划分示意图5 9 图4 - 61 2 码率生成矩阵g 前6 9 1 2 x 2 3 0 4 部分划分示意图5 9 图4 7l d p c 编码器结构框图6 0 图5 1g m a p 版图局部结构框图6 4 图5 2g m a p 集成电路板6 4 图5 3方案一l d p c 译码器验证架构。6 5 图5 - 4方案一f p g aa 内部结构框图6 6 图5 5 方案二l d p c 译码器验证架构6 6 图5 - 6l d p c 译码时序示意图6 7 图5 7l d p c i 2 码率译码全局功能仿真图6 8 图5 8l d p c i 2 码率一次译码及输出功能仿真图6 8 图5 - 91 2 码率b p s k 调制定点量化仿真结果曲线图6 9 图5 1 03 4 码率b p s k 调制定点量化仿真结果曲线图7 0 表目录 表目录 表3 1l d p c 编码配置2 7 表3 2 经熊算法和“基于指针”算法的结构和资源占用情况比较4 9 表3 - 3 方案一在x c 2 v 6 0 0 0 上的器件资源利用情况总结。5 3 表3 方案二在x c 4 v l x 8 0 上的器件资源剩用情况总结5 4 表4 1v i r t e x i ix c 2 4 0 参数表l 5 7 表4 2 r t c x 。i ix c 2 4 0 参数表2 5 7 表4 3 方案一在x c 2 v p 4 0 上的器件资源利用情况总结6 2 表5 1g m a p 可用的x i l i n xv i r t e x - i i 的几款芯片基本资料6 4 表5 21 2 码率误码率统计7 0 表5 33 4 码率误码率统计7 l 缩略词表 a r q k n g r a s i c b e r b p c m m b c p l d d c m e d a f e c f p g a h d l i o b i p l d p c l u t s t i m i 缩略词表 a u t o m a t i cr e p e a tr e q u e s t a d d i t i v e 朋7 i t eg a u s s i a nn o i s e a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t b i te r r o rr a t e b e l i e fp r o p a g a t i o n c h i n am o b i l em u l t i m e d i ab r o a d c a s t i n g c o m p l e xp r o g r a m m a b l el o g i cd e v i c e d i s t a lc l o c km a n a g e r e l e c t r o n i cd e s i g na u t o m a t i c f o r w a r de r r o rc o r r e c t i o n f i e l dp r o g r a m m a b l eg a t ea r r a y h a r d w a r ed e s c r i p t i o nl a n g u a g e i n p u t o u t p u tb l o c k i n t e l l e c t u a lp r o p e r t y l o w d e n s i t yp m t yc h e c kc o d e s l o o k - u p t a b l e 重传反馈 加性高斯白噪声 专业集成电路 误码率 置信传播 中国移动多媒体广播 复杂可编程逻辑器件 数字时钟管理器 电子设计自动化 前向纠错 现场可编程门阵列 硬件描述语言 输入输出接口模块 知识产权 低密度奇偶校验码 查找表 s a t e l l i t et e r r e s t r i a li n t e r a c t i v em u l t i s e r v i c e卫星和地面交互式多服务 i n f r a s t r u c t u r e 基础设施 v l s i v e r yl a r g es c a l ei c超大规模集成电路 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：匆缓旦导师签名：肆 日期：爰oo 矿年月o r 日 第一章引言 1 1 数字通信系统的结构 第一章引言 通信的目的是通信双方可以把交互信息即时可靠的传送给对方。所有的数字通 信系统如通信、雷达、遥控遥测、数字计算枫存储系统的滤部运算以及数字计算 机之间的数据传输等，都可以归纳成如图1 1 所示的模型【玎。 图1 - 1 数字通信系统基本组成 图1 1 中，信源产生需传输的信息，信息可以是模拟信号，也可以是数字信号。 如果信源是模拟信号，则在送入数字系统传输之前需要进行采样和数字化处理； 如果是数字信号则可瑷是字、码字等符号，一般将这些称为码元。信源的输出根 据给定的码表转化成符号序列，一般情况下常用的是二元符号序列，码字符号中 的码元取自集合f o ，1 ，这时码元又称为比特。如果信源编码器的输出信号为 r bb i t s ，则称最力数据传输速率，篱称为数据率醛l 。 信源编码器的任务是将信源发出的消息如语言、图像、文字等转换成为能够抵 抗信道噪声和失真以及有利于在传输媒质上进行的传输形式，信源输出经过信源 编码器编码后得到的数字序歹l 称为信息序列。 信道编码是在发送器与接收器之间实现信号可靠传输的必要手段之一。传输信 道存在一定的噪声和衰落，必然会对其上传输的信息引入失真和信号判决错误， 因此需要采用差错控制码来检测和纠正这些比特错误。信道编码器的作用是在信 电子科技大学硕士论文 息序列中嵌入冗余码元，提高其纠错能力。从而信道编码的冗余码元的作用是减 小传输中发生的信号和码元错误，提高系统的可靠性。 本文主要考虑二元有限域上的信道编码，因此不再区分码元和比特的概念。信 道编码的基本思想是将每k 个连续的信息比特分为一组，经过适当的编码后得到n 个比特的输出，这n 个比特组成的序列称为一个码字。好的差错控制码所生成的 码字应该是在码字集合中，所有码字之间的区别尽可能大，从而使通信系统中的 无法纠正或检测的信道错误尽可能少，k 个信息比特与1 1 个码字比特的比值称为编 码速率，简称码率r ，即： 尺：一k(1-1) 刀 从而经过信道编码后的数据率为 丑r2 警( 1 - 2 ) 差错控制码的基本目标是在有限的信号功率、系统带宽和硬件复杂性要求下使 通信的可靠性最大，这个目标是通过在信息序列中引入冗余比特来实现的。与未 编码系统相比，信道编码会导致数据传输率的降低或者使对信道带宽的要求增加。 数字调制器的作用是使信息变成能够适应信道传输的信号。如比特形式的信息是 不适合在物理信道上传输的，因此需要利用数字调制器将这些编码比特转化成适 合于在信道上传输的连续波形信号。通过相应方式调制可以在相同的物理信道上 同时传输多个信息比特( 数目与具体的调制方式有关：如8 p s k 调制下可同时传输3 比特信息，16 q a m 调制下可同时传输4 比特信息) ，从而提高信息传输速率。调制 器的基本思想是将编码的数字序列映射成适合在信道上传输的模拟连续信号。具 体地说，m 维调制器可以将1 个二元数字符号映射成一个有m 种不同波形的模拟 连续信号 m = 2 。 ( 1 - 3 ) 如果调制器输出的每个信号的持续时间为t ，则称t 为信号间隔，而称1 厂r 为 符号速率。如果定义信号带宽的最小值为乓( h z ) ，则可以表示为 2 面r b2 菁( 胁) ( 1 - 4 ) 信号经过调制器后送入物理信道进行传输。典型的传输信道包括有线信道、光 纤信道、无线信道、卫星信道、磁记录信道以及水下声音信道等。无论是哪一种 传输媒体，都会引入一定的传输噪声，使传输信号发生一定的失真。而且由于信 道带宽资源有限，通常需要为不同的通信业务分配不同的传输频率和带宽。因此， 2 第一章引言 在实际的信道中存在的两个主要闻题就是信道固有的噪声和有限的带宽限割。此 外，移动信道会受到多径传播的影响，卫星信道会受到信号功率衰减的影响等， 这些在系统设计过程中都应该考剧。 信号到达接收端，在接收机中，数字解调器的作用是通过对接收到的调制信号 序列或传输码字进行最优估计，然后输出数字编码序列到信道译码器。信道译码 器对传输消息进行估计和判决，估计准则是根据编码准则和信道特性而确定的， 目的是使信道噪声所造成的信号判决错误最小化。 最嚣，信源译码器根据信源编码准则将得到的信道译码器输寤的编码信息序列 经过相应的信源译码后，得到对原始信源序列的估计并传递给用户。 图1 1 中的信道编、译码器是本文关注的主要方向。为了便于研究，将图1 1 模型并进一步简化成如图l - 2 所示的模型。在此模型中，信源是指原来的信源和信 源编码器，其输出是二进制( 或多进制) 信息序列。信道是包括发射机、实际信道和 接收机在内的广义信道( 又称编码信道) ，它输入二进制( 或多进制) 数字序列，输出 一般也是二进制( 或多进制) 数字序列【l j 。 图1 2 数字通信系统简化系统 1 2 信道编码技术的发展史 伴随着通信技术的飞速发展以及通信各种传输方式对可靠性要求的不断提高， 差错控制编码技术作为抗干扰技术的一种重要手段，在数字通信领域和数字传输 系统中显示出越来越重要的作用【l 】。由于通信信道固有的噪声和衰落特性，信号经 过信遒传输到达通信接收端的过程中不可避免的会收到干扰丽导致信号失真。通 常需要采用差错控制码来检测和纠正由信道失真引起的信息传输错误。最早的纠 错码主要是用于深空通信和卫星通信，随着数字蜂窝电话、数字电视以及高分辨 率数字存储设备的出现，编码技术已经不仅仅局限于科研和军事领域，露是逐渐 在各种实现信息交流和存储的设备中得到成功应用【l j 。 19 4 8 年c e s h a n n o n 发表的著名的通信的数学理论一文，为信道编码技术 的发展搔明方向。s h a n n o n 在著名的有噪信道编码定理中，给懑了在数字邋信系统 电子科技大学硕士论文 中实现可靠透信的方法以及在特定信道上实现可靠逶傣的信息传输速率上限。 s h a n n o n 在他的证明中引用了三个基本条件： ( 1 ) 采用随机的编译码方法； ( 2 ) 构造码长的濒进好码或s h a n n o n 码： ( 3 ) 译码采用最佳的最大似然译码算法。 5 0 多年来构造好码的思想基本上是按照s h a n n o n 所引用的基本条件的后两条 为主线进行研究的。经过5 0 年的不懈努力，各种差错控制编码方案不断涌现。 在2 q 世纪钧年代，r h a m m i n g 和m g o l a y 提出了第一个实用的差错控利编 码方案，使编码理论这个应用数学分支的发展得到了极大的推动。h a m m i n g 所采 用的方法就是将输入数据每4 比特分为一组，然后通过计算由这些信息比特的线 性组合得到的3 个校验沈特，氍将信息比特加校验比特的总共7 个比特送入计算 机f l 】。计算机按照一定的原则来读取这些码字，通过采用一定的算法，不仅能够检 测到是否有错误发生，同时还可以找到发生错误的单个比特的位置，该码可以纠 正7 个比特中所发生的单个比特错误。这个编码方法就是分组码的基本思想， h a m m i n g 提出的编码方案怎来被命名为汉甓码。 鼠然汉明码的思想在当时是比较先进的，但是它也存在许多技术上难以接受的 缺点：一是它的编码效率比较低，二是在一个码组中只能纠正单个比特错误。 m 。g o l a y 研究了汉明码这些缺点，并提出了两个以他鸯蠢的名字命名的高性能码 字：二元g o l a y 码和三元g o l a y 码，相比汉明码提高了编码效率和可纠正误码数。 1 9 5 4 年r e e d 在m u l l e r 提出的分组码的基础上得到了种新的分组码，称为 r e e d m u l l e t 码( 简称为r m 码) 。r m 码在汉盟码和g o l a y 码的基础上前进了一大步， 在码字长度和纠错能力方面具有更强的适应性，直到今天，r m 码也具有很高的研 究价值，其快速的译码算法非常适合于光纤通信系统。 在r m 码提出之后，人们又提出了循环码的概念。循环码实际上也是一类分组 码，但它的码字具有循环移位特性，即码字比特经过循环移位后仍然是码字集合 中的码字。这种循环结构使码字的设计范围大大增加，同时大大简化了编译码结 构。循环码的另外一个特点就是它可以用一个幂次为n k 的多项式来表示，循环码 也称为循环冗余校验( c r c ，c y c l i cr e d u n d a n c yc h e c k ) 码，并且可以用m e g g i t t 译 码器来实现译码。 h o c q u e n g h e m 在19 5 9 年，b o s e 和r a y - c h a u d h u r i 研究组在19 6 0 年几乎同时提 出了b c h 码( b c h ，b o s ec h a u d h u r ih o c q u e n g h e m ) u 】，b c h 码是循环码的一个非常 重要的子集，b c h 码酶码字长度为n = q ”一l ，其中m 力个正数。二元b c h 码 4 第章弓l 言 鲶鲻错能力限为t 2 ”一1 ) 2 。1 9 6 0 年r e e d 和s o l o m o n 将b c h 码扩震到j 錾= 元 的情况，鳃到了r s ( r e e d s o l o m o n ) 码。烙码的最大优点是其非二元特性可以纠正 突发错误。 1 9 5 5 年e l i a s 等人提出了卷积码。卷积码与分组码的不同在于卷积褥中的n - k 个校验元不仅与本玛字酶k 个信息元有关，还与之蔫码字戆信意元有关。 1 9 6 2 年，由r o b e r tg g a l l a g c r 博士提出的一类具有稀疏校验矩阵的线性分组码， 其特点是使用了迭代译码算法。但由于当时技术条件的限制，再加上人们普遍认 药缀联码更易于实用纯，l d p c 码在恣时著没有褥烈重视。直裂1 9 9 6 年，m a c k a y 和n e a l 证明了l d p c 在与基予可傣度传递( b e l i e f p r o p a g a t i o n ，b p ) 的迭代译码褶结 合的条件下具有逼近香农极限的性能，才使人们重新认识到l d p c 码。l d p c 译码 复杂度较低，结构灵活。 在传统通信系统的最佳接收枫率，解谰器鞠译鹳器是独立的两个部分。硬粼决 译码和软判决译码是信邀编译码技术发展史上出现的两个很重要的思想概念。硬 判决译码的思想就是在处理接收信号的过程中，解调器首先对输入符号做最佳判 决，然螽将硬刿决结栗送入译码器：译鹨器藉对编码器输入信息徽最佳判决，绷 正解调器珂糍发生豹错谖判决。事实上，经过解调器对符号的硬判决，丢失了很 多有利于译码的信息。为了提高编码通信系统的性能，人们从信息论的角度对接 收机中解调器与信道译码器的功能和接蹬重耨进行了审视，提邀了软判决译码方 法，帮解调器对输入不进彳亍判决，送到译码器熬怒粼决符号翡概率值，似然泷信 息或未量化输出，而非嫒判决值，则译码器就可以利用这些信息与编码信怠综合 做出判决，从而提高系统性能。研究表隳，在接收机中解调器采用软输出可以褥 到跑硬输溉高2 d b 左右麴附翔编码增盏l ”。 软判凌译码算法主要分蔻两大类：一类是使符号错误概率最小的逐位软判决译 码算法，如1 9 7 4 年由b a l l l ，c o c k e ，j e l i n e k 和r a v i v 共同提出的前向后向最大后验概 率( m a p ) 译码算法( 也称为b c j r 算法) ；雯外类就是使码字错误概率最小的逐组 软判决译码方法，如1 9 6 7 年v i t e r b i 提出的v i t e r b i 译码算法等。 虽然软判决译码，编码调制技术等对信道码的设计和发展产生了重大影嗡，但 是其增益与s h a n n o n 理论极限始终存在2 3 d b 的差距【l 】。因此，在t u r b o 码提出 之蘸，信遂截止速率豫直被认为是差错控制码键能的实际极限，s h a n n o n 极限 仅仅是理论上的极限，是不可能达到的。 直到1 9 9 3 年t u r b o 鹤的提出以及1 9 9 6 年又重毅被人们所注意的l d c p 码，才 注入蜘看到了差错控制犸性麓逼进s h a n n o n 限的可麓。 电子科技大学硕士论文 1 3 信道编码及相关概念 从信息论的角度来研究编码信道，信道的输入信号，噪声干扰下的输出信号， 差错概率的大小和分布，从输出信号中最佳恢复输入信号的方法等是主要研究的 内容【l 】。信道编、解码器之间的部件作为广义信道，也珏q 编码信道。广义信道中的 调制、均衡、滤波等终端处理一般是可预知的，信道本身的参数大多也是可测试 的，最不确定的因素是噪声干扰【筋。从噪声的发生规律来分，有加性和乘性两种。 加性噪声的影响是做加法( 嗓声+ 信号) ，它是倍道固有噪声，由热噪声，无线电， 电脉冲干扰等造成。乘性噪声( 噪声信号) 的存在与信号有关，由于它的不确定性， 可以用随机信号或随机过程的理论来研究其统计特性。不同的信道加不同类型的 噪声构成了不同类型的信道模型。就噪声引发差错的统计规律而言，分为随机差 错信道和突发差错信道两类。任何种编码信道模型的运信熊力都不是无限的， 其极限值就叫做信道容量。 考虑个q 元入，o 元出的离散无记忆信道，再考虑一个科，k ) 分组码编码器， 该编码器介于信源输出和信道输入之闻，对k 个q 进制符号组成的消息组进行编 码，生成由n 个q 进制符号( 也称为码元) 组成的码字。码字可视为一个n 维矢量， n 维矢量空间共有个点。消息组的k 个q 进制码元总共只有m = 擘个码字，所 有码字的集合称为码集。显然，n 维矢量空间中，码集只是n 维矢量空间的一个 子集。 定义码率( 或传信率) 为r = ( 1 n m ) n ，m = g 是可能的信息组合数，n 是每码字 的码元数，r 表示每码元携带的信息量，单位是每符号奈特( n a t s y m b 0 1 ) 。若以2 为底求( ( 1 0 9 ，m ) n ，码率单位是每符号比特( b s y m b 0 1 ) 吼 令表示码集的差错概率，有扰离散信道的信道的信道编码定理为； 2 时 是q 进制码。多进制q 一般取素数或素数的幂次【2 1 。当q = 2 6 时，每码元可携带b 比特信息，长度为n 的q 元分组码字可以映射成长度n = b n 的二元分组码字。 从空闻的危度来探讨，k 位二进制信息缀有2 。种组会，构成g f ( 2 ) 上酶k 维k 重矢量空间；而n 位二迸制数共有2 ”种组合，构成g f ( 2 ) 上的n 维n 重矢量空间， 通常2 ” 2 。纠错编码的任务是在n 维n 重矢量空间的2 “种可能组合中选择2 。个 构成一个子空闯，或称许用码码集c ，然后设法将k 比特信息组一一对应地映射到 码集c 。不同的编码算法对应不同的码集c 以及不同的映射算法，把这样得到的 码称为( n ，k ) 线性分组码。 二元线性分组码必须满足如下两个条件： ( 1 ) 码字集合中的任意两个码字经过模2 加之后得到的结果仍然是码字集合中 的一个码字。 ( 2 ) 码字集合中包含有全零码字。 l 。4 2 生成矩阵和校验矩阵 令，l 川，m i ，m 。为一组k 个二进制信息码元，它可看成是在k 维k 重空间中的 一个矢量m = ( i n k - l , , m z ，m o ) ，也可看成是一个lx k 的矩阵m = 【m , - l m l m o 】。经 过线性分组码编码后，输出码字码长n ，是k 维n 重码空间c 中的矢量，记为 c = ( q ，c l ，c o ) 。码集c 中任一码字c 的第j 个码元c ，都是信息元m k - i ， 粥，m o 的 线性组合，编码运算可以用由n 个方程构成的线性方程组来表示，即 c ，= m k l 反h ) ，+ + 强& ，+ 醌，歹= 嚣一l ，1 ，0 ( 1 一妨 式中，系数g o 0 ，1 ) ，江后一1 ，1 ，0 表示第i 个信息元砚对第j 个码元的影响【2 1 。 线性方程组如式( 1 6 ) 也可以用矩阵形式表示为： 第一章引言 c = c 。一l ，c 1 ，c o = m g = 一i m l m o 】【g i l g l g o r( 1 - 7 ) 式中，g 称为该码的生成矩阵，是k x n ( k 行n 列) 矩阵： g = g h g l g o r = g c k l n 1 ) 虽i i ) i 反i i ) o g l ( 一1 1 g l ig i o g o ( n n g o lg o o ( 1 - 8 ) 其中& = 瞳沁l 】- g i 。g i 。 ，i = k - 1 ，0 ，是g 中第i 行的行矢量。 按分块矩阵运算法则将式( 1 7 ) 展开，得： c = m k l & i 1 ) + + 蜀+ g o ( 1 - 9 ) 可见，任何码字都是生成矩阵g 的k 个行矢量的线性组合。只要这k 个行矢 量线性无关，就可以作为k 个基底张成一个k 维n 重空间，它是1 1 维n 重空间的 一个子空间，子空间的所有2 个矢量构成码集c 【2 】。不同的生成矩阵产生不同的码， ? 生成矩阵的特点决定了码的特点。另一方面，由于构成同一空间的基底不是唯一 的，所以不同的基底或生成矩阵有可能生成同一码集。此外，由于子空间是k 维 的，因此生成矩阵g 的秩是k 。 基底不是唯一的。将基底线性组合，挑出其中k 个矢量，只要它们满足线性无 关的条件，依然可以作为基底张成一个同样的码空间【2 】。反映到矩阵，等效于允许 通过行运算改变生成矩阵的形式而不改变码集，只要保证矩阵的秩仍是k 。据此， 任何生成矩阵可通过行运算转化成如下的系统形式： g = 阮ip 】= 10 01 ： o 0 p ( k 1 ) ( 月一i 1 ) 毁i 1 ) l 毁t 1 ) o p l ( 月一女一1 ) p 1 1p l o 风( ”一t 1 ) p o lp o o ( 1 - l o ) 这里p 是k ( n - k ) 矩阵，厶是k k 单位矩阵。从而保证矩阵的秩是k 。 信息组1 1 1 乘以系统形式的g 所得的码字，其前k 位由单位矩阵厶决定，则与 信息组各比特相同，而其余的n k 位叫做冗余比特或一致校验位，是k 个信息位的 线性组合。这种把信息组原封不动搬到码字前k 位的( n ，k ) 码o q 做系统码，其码字具 有如下形式： c = ( 巳一l ，巳一i ，c n - k - 1 ，。c o ) = ( m t l ，m l ，m o ，c n - t - l c o ) ( 1 1 1 ) 反之，非系统形式生成矩阵所产生的码叫做非系统码，非系统码的生成矩阵可以 9 电子科技大学硕士论文 通过行运算交为系统码酶生成矩阵，这两个生成矩阵是等效豹。 与任何一个( n ，k ) 线性空间c 相对应，一定存在一个对偶空间d i 羽。事实上，只 要找到n 维1 1 重空间的全部n 个基底除码空间基底k 的另外n - k 个基底，也就找到 了对偶空闻d ，在对偶空闻中的n - k 个基底产生个有2 ”个码矢的( 珏，n k ) 线性码， 称为( n ，k ) 线性码的对偶码。将d 空间n - k 个基底排列起来，可构成一个( n xk ) n 矩阵，称为码空间c 的校验矩阵h ，它是( n ，n 。k ) 对偶码的生成矩阵。 豳于c 的基底和d 的基底惩交，因此( n ，k ) 线性码的任意码字c 一定正交于其 对偶的任意码字，也必定歪交于校验矩阵珏的任意一个衙矢量，即 c h r = o ( 1 1 2 ) 式中，o 代表零阵，它是 1 xn x n x ( n 一露) 】= l x ( n - k ) 全零矢量。式( 1 1 2 ) 可以用来 检验一个1 1 重矢量是否为码字：若等式成立，该n 重矢量毖为码字，否则非码字溺。 相对应式( 1 1 0 ) 所示的生成矩阵的系统形式，则一致校验矩阵h 可取如下形式 日= 卜p 厶一。】( 1 - 1 3 ) 式中，一矿是一个( n - k ) x k 阶矩阵，它是p 矩阵的转置，“一 号表示p r 矩阵中的 每一元素是p 矩阵中对应元素的逆元，在二进制情况下，仍是该元素自己。显然 一p g h 1 - - 1 i , 明【，】_ o ( 1 1 4 ) i n - 蠢 1 4 3 循环码和准循环码 循环码是线性分组码中最重要的一个子类，它的结构完全建立在有限域的基础 上。循环码码字的循环移位仍然是码字，这个特点给循环码的编译码实现带来了 便利，可以利用移位寄存器构造乘法器和除法器来实现。此外，代数结构、纠错