（信号与信息处理专业论文）ldpc编解码技术及其在信息隐藏领域中的应用.pdf

中文摘要 捕要： 近年来，随着h t 伽c t 和通信技术的迅速发展，越来越多的信息需要通过 h t 锄e t 来传输。通常我们认为加密的通信就很安全了，但在现实中却远远不够。 因此，对于通信网络安全的学习，不仅包括密码学，还包括以信息隐藏为主的传 输安全。信息隐藏已经运用到知识产权的保护，数字水印等多种领域，从这种意 义上讲，信息隐藏已经成为一个非常重要的领域。 根据隐藏信息的嵌入方法不同，信息隐藏算法分为空域信息隐藏算法和变换 域信息隐藏算法。若使用上面两种算法之一进行信息隐藏时，尤其是信道中有比 特攻击，我们进行信息提取恢复时就会遇到困难，从而使诸如版权保护之类的目 的难以实现。 为了解决上述问题，我们提出一种基于u ) p c 码的数字图像信息隐藏算法。 由于u ) p c 码具有很强的错误纠错能力，所以本算法克服了传统的空域信息隐藏 算法和变换域信息隐藏算法的缺点，尤其是在遇到比特攻击的时候，该优点很明 显。在信噪比很低的情况下，我们可以几乎完整地恢复出隐藏信息。 传统的信息隐藏不具备抗比特攻击能力，本文提出一种基于u ) p c 码的数字 图像信息隐藏算法，对隐藏信息图像编码，可抵御比特攻击。隐藏信息在进入高 斯噪声信道前需要进行l i p c 编码本文给出了u ) p c 码的编码结构，可传播置 信解码算法以及信息隐藏技术的相关知识。本文提出的算法不仅具有空域信息隐 藏算法的特点：算法简单，运行速度快，容易实现；而且还具有变换域信息隐藏 算法的特点：较强的抗比特干扰能力，仅对隐藏信息编码，确保隐藏信息的不可 见性。通过仿真结果表明，该算法降低了隐藏信息在传输中的误码率，具有较强 的鲁棒性。 关键词：u ) p c 码；1 、l r b o 码；b p 算法 a b s t ra c t a b s r i r a c b r c c 睫ty c 躺w ch a v cw i t i l e s s c dt h cr a p i dd c v c l 叩m 髓t0 ft h ei n t e m c t 卸d t e l c c 0 蚴u n i c a t i o nt 池i q u 髓m o 锄dm o r c 撕a t i i st f a 璐m i t t c dt h ：u g ht h c i n t c m c t ni s 曲锄t h 伽g h tt h a t 锄m u n i 叫i o 璐m a yb cs 鲫- c db y 眦聊陆gt h c n 砌c ，b u tt h i sh 鹤r a l yb e c na d e q u a t ci np r a d i ，t h cs t i l d yo ft h e 锄u n i c a t i o n s c 删r i t y 血c l u d c sn o tj u 吼锄c r y p t i o nb u ta l 仃a f f i cs 咖r ! i t y w h o c s s 锄c cu 龉i n h i d 迦i n f b n n a t i o n ht h i sc 獬，幽姗a t i h i d i n gh 弱b c 伽c 蛆锄e f g i n g 毋嗽觚c h 撇t h a t0 0 删璐a p p h c a t i 0 鹏辄c h 路c o p y r i g h tp m t c ( a i f o i 。d i g i t a lm c d i a w 砒e 曲盯k i n 舀痂l g e r p r i n t i n g ，a n ds oo 也 a c o o r d i n gt o t h cd i 丘c t6 c l d sw h i c ht h cs c c tm 髂s 鸭cw o r bi n ，t h c i n f 0 助a t i h i d i i l gm c t h o d sa d i v i d c d 蛔t ot h cs p a 6 e l dm c t h o d 柚dt f 柚s f 0 1 m a t i 丘e l dm c l h 毗u 血gm c 钾mm c t h o d sa b o v es e p 删c l y ，t h c f cc x i s bd i f f i c i l l t yw i n l s t o r i l l gt h es h o r c m i n g ，w h 吼m e e t i l i gt l i cb i ta t t a c l 【，w h i c hw i l lc a u t h ec o p y r i g h t p t c c t i o no f m u l t i m c d i ad i g i t a ip f o d u di n t 0aq u c s t i 蚰 h o r d 盯t 0 l v c t h i sp r o b l c m ，t h i sa n i d c p r 0 p 0 s 鹤a l 【i n do f m c t h o db a d o t h e l d p cc o d c dd i g i t a li m a g ei l l f o 哪a t i h i d i n ga l g o r i t h m ，t 0 铡c r y 衄t h cl d p cc o d c d f o ft l l es e c r c tm c s 鼢g cw l l i c hi si n s c n c di nt h cc o v c rm 瞄s a g cj n l a g c 王i c c a u t h cu ”c c o d eh 鹤t h cv c r ys 咖g 咖c 0 删t i o na b i n t y ，t h i sa l g o r i t h i no v c r o o m t h cd e f b c b o ft h ct r a d i t i a ls p a c ef i c l d 卸dt h ct m s f b 姗a t i o nf i e l dm c t h o d sw h e nt h e ym e c tt h c b “a t t a c i 【s ，髓p c c i a l l y 吼d c rt l i cs t 枷gb “a t t a c ks i n l a t i ，t h cs c a r c tm e 娼a g ce 仃o rm t c i ss t i l li l lp a n 妣l a r1 0 w ，卸dc o u l d 脚妇弓t h cs c c r e tm e s s a g ci m a g c 州t h 印p m x i m a t c 肿d a i l l a g e 皿i sp a p c rp r o p o s e san e wi n f o 曲a l i o nh i d i n gs c h 锄ci ni l i l a g c sv i au ) p c d i n 吕 g e n 盯a l l y ，r 鼯i s t i l l g t h eb i t s a t t a c k i n g i s n e a r l yi m p o 豁i b l c f b ft h ec o n v e n t i 蛐a l i n f o 咖a t i 咖h i d i n gs y s t e m ht h i sa n i c l eh r d e n s i t yp 捌t yc h c c kc o d 龉a r ci n t _ o d u c c d i n t 0t h ei n f 0 加1 a t j o nh i d i n gs y s t c mb c c a u o ft h cb c l t c rp c r f b 加柚n c co ft l l e i fo w n w b p r o v i d em ei n f o 加a t i 伽h i d i n gs y s t 锄b 嬲c d t h eu ) p c d i n g 勰w c l l 弱t h cb d i c f p r o p a g a t i d c 0 0 d i n ga 1 9 0 r i t l l i n ，蛐d 柚a l y z ct h cp c 胁a n o ft h c 此s u l t s t h c p r o p o da l 鲥t h mh 勰t h cs p a c c 丘e l dm c t l l o d a d v 柚t a g c s ：s i i i l p l c 蛐dq u i c k t h c p r o p o s e dm e t h o di sc 醛yt ob e ”a i i z e d f u n h c rm o r c ，i ta l h a st h cv i r t u e0 f t 砌s f o 皿a t i o nd o m a i nm e t h o dt h a to n i yc a i 鹤o nt h ec o d i n gt ot h c c r e tm e s s a g e 卸d g 哪【r a n t c 髂t h e 蝴tm c s 髓g c ，sj n v i s i b i l i t y t h es i m u l a t i 彻r 璐u l t ss h o wt h a tt h c p r o p 懈c di n f 0 皿a t i o nh i d i n gs y s t c mb 撇d 加l d p c d 骼锄a 出e v ct h cg o o dc 珊叫 m t ep c i f b 助a n 卸dt h ca p p 田锄tm b u s 衄c 豁c 勰b ct a l ( 姐佃 暇w o i m s ；k l w d c 邶i 咿p a r i t y - c h c c k d e s ；1 、l f b oc o d 髂；b e l i e fp r o p a g a t i 蛐 致谢 本论文的工作是在我的导师肖扬教授的悉心指导下完成的，肖扬教授严谨的 治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来肖扬 老师对我的关心和指导。 肖扬教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给予 了我很大的关心和帮助，在此向肖扬老师表示衷心的谢意。 肖扬教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心 的感谢。 在实验室工作及撰写论文期间，赵莹、杜海峰等同学对我论文中的信道编码 研究工作给予了热情帮助，在此向他们表达我的感激之情 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业 序 在数字通信中，我们所要传输的数据往往在信道中要受到比特攻击，从而在 接收端出现错误，无法完全恢复数据，产生失真。在数字通信系统以及计算机存 储和运算系统中这种错误往往是致命的。因此如何在信道中特别是有扰信道进行 抗干扰通信，一直是困扰我们的一大难题。还有一大难题就是通信信息的安全问 题，开放网络的通信信息安全尤为重要。因此本文为了解决上述两大问题，进行 了如下工作： 提出用u ) p c 码对隐藏信息进行编码，降低系统的误码率。 提出基于u ) p c 码的数字图像信息隐藏系统，将编码后的数据隐藏在数字图 像中，在有扰信道进行传输，为解决开放网络的通信信息安全提供了一种有效可 靠的解决方案。 同时我们也需要加大在通信安全和传输有效性等方面的研究力度，尽早解决 这些问题。 1 1 课题研究背景及其意义 1 绪论 近些年来，我们目睹了计算机网络和数字通信的飞速发展。越来越多的信息 都是通过i n t 咖c t 进行传递。过去那种认为将信息加密就可以很安全的传递的观念 在现实中已经很难实现了【。信息安全已经被提到了战略高度。因此，对于通信安 全的研究，不仅包括密码学技术，更应该包括传输安全技术，而它的实质就是信 息隐藏技术。 信息隐藏可以追溯到公元1 4 9 9 年，它的历史久远。但是直到2 0 世纪9 0 年代， 在r r 界，人们才赋予了它新的内容，使之成为继加密技术之后，保护信息的又一 强有力的工具信息隐藏与传统的信息加密的明显区别在于，传统的加密技术以 隐藏信息的内容为目的，使加密后的文件变得难以理解，而信息隐藏是以隐藏秘 密信息的存在为目标，所以科学技术的发展使信息隐藏技术在信息时代又成为新 的研究热点它既发扬了传统隐藏技术的优势，又具有了现代的独有特性。 对于图像和视频数据，根据信息嵌入的工作域不同，信息隐藏算法分为空间 域信息隐藏算法和变换域信息隐藏算法。空间域信息隐藏算法，是通过改变某些 象素的灰度将要隐蔽的信息嵌入其中，将数字信息直接加载在数据上。传统的空 域信息隐藏算法，加入的信息很容易受到压缩，量化，比特攻击信道传输的影响 而失真。基于变换域的技术可以隐藏大量比特的数据而不会导致不可察觉的缺陷， 往往通过改变频域的一些系数的值，采用类似扩频图像的技术来隐藏数字信息。 频域方法具有如下优点：( 1 ) 在频域中隐藏的信号能量可以分布到所有的象素上， 有利于保证隐藏信息的不可见性；( 2 ) 在频域中可以利用人类视觉系统的某些特 性，可以更方便、更有效的进行隐藏信息的编码。不过，频域变换和反变换过程 中是有损的，同时其运算量也很大，对一些精确或者快速应用的场合不太适合。 在有扰信道进行通信时，不管是传统的信息隐藏算法，还是变换域信息隐藏 算法，都不具备纠错能力。因此仅仅用上述的算法进行信息通信时，必然存在信 息的丢失，无法完全恢复隐藏信息。 在信噪比为3 的a w g n 信道，隐藏信息嵌入载体图像后，直接进入信道后， 在接收端经过提取得到隐藏信息。图1 1 ，1 2 ，1 3 ，1 4 分别为原始载体图像，还 原后的原始载体图像，隐藏信息图像，还原后的隐藏信息图像。 图1 1 载体图像 f i g m1 1 n c i m a g c 图1 2 还原后载体图像 f i g u 阳1 2 n c v e r ，s i l i l a g eo f r e s 们n n 2 图1 3 隐藏信息图像 f i g i l m1 31 ks c c m c s s a 萨 图l4 提取后隐藏信息图像 k g m e1 4 n c 咖d n gs 删血l t 鲈 通过对比上面四幅图像我们可以看出，在经过有扰信道时，由于受到比特攻 击，发生了比特翻转，不仅载体图像发生了失真，而且隐藏信息图像也发生了严 重的失真。 在经过信道时候，发生比特翻转，用二进制表示的信息0 变成1 ，1 变成0 ， 所以隐藏信息大量丢失，其根本原因就是在于传统的隐藏信息算法不具备纠错能 力。 为了解决上面的问题，我们试着将纠错码引入到信息隐藏领域中，从而使隐 藏信息在经过有扰信道发生比特翻转后，在接受端仍能纠错过来。在纠错码领域， 在一定条件下，u ) p c 码是目前已知最接近香农限的好码，目前是编码领域研究的 热点之一。由于其具有优越的纠错性能，因此我们将u ) p c 码与信息隐藏技术相 结合。 将u ) p c 码引入到信息隐藏技术中具有巨大的现实意义。 在网络飞速发展的今天，信息隐藏技术的研究更具有现实意义。但由于信息 隐藏技术本身的缺点约束，仅仅靠信息隐藏本身的技术已经不能实现真正意义上 的绝对安全，将l d p c 码引入信息隐藏技术中，对隐藏信息进行u p c 编码，如 果接收端不知道校验矩阵以及相关解码条件，就无法提取隐藏信息，所以u ) p c 码与信息隐藏技术结合，为通信安全提供了一种有效的方案。 3 在有扰信道中通信时，由于受到比特攻击，大量信息丢失，所以无法完全恢 复出隐藏信息，从而失去了信息隐藏技术的价值。为此，将u ) p c 码引入信息隐 藏技术中，充分发挥u ) p c 码优越的纠错性能，使两种技术充分发挥各自的优点， 达到完美的结合，在信息通信中，特别是有扰信道中仍达到安全通信的目的。 u ，p c ( k 脯d e 璐i t yp a r i t yq 眦k ) 码是g a l i a g 盱最早于1 9 6 2 年提出的一种具有 稀疏校验矩阵的分组纠错码，亦称g a l l a g 盱码。之后，在1 r u r b 0 码的研究的巨大成 功的带动下，m a c k a y 等人重新研究了u ) p c 码，并发现其具有非常好的优点：逼 近香农限的性能，且描述和实现简单，易于进行理论分析和研究，译码简单且可 实行并行操作，适合硬件实现。近年来u ) p c 码凭借其优异的性能、简洁的形式 及良好的应用前景日益备受青睐，已经引起世界各国学术界和r r 业界的高度重视， 成为当今信道编码领域的研究热点之一 好的u ) p c 码关键在于要有好的码性能和较短的编码时间。迄今为止尚没有 提出构造u p c 码的系统方法，都是借助于实验和统计分析构造l d p c 码。 m c d a v e 俨】提出，在非二元有限域中定义码和采用具有非均匀行、列重量的非规 则奇偶校验矩阵均可以改善u ) p c 码的性能。d j c m a c l 【a y 等【3 】提出对非规则 u ) p c 码采用先选择轮廓再选择结构的两部选择方法，验证了蛐p c 协血结构均 有较好性能，并指出：能快速编码的u ) p c 矩阵通常具有下三角形结构。 i j 硒c h a r d n 等【4 】通过优化非规则图的次数结构来寻找逼近容量的非规则 u ) p c 码。t j r i c h 羽s o n 和r l u r b a i i k c 阁探讨了要获得高效编码器如何确定校验 矩阵稀疏度的问题，以及如何构造码，使得编码时间与码块长度实际上符合线性 关系，而非通常认为的平方关系。m g 【曲y 等1 6 j 也提出了一类基于级联二分图的 u ) p c 码，用于可擦信道，称为e r 弱u r c 咖t i n g 码，它不仅是线性时间编码，还 可以实现线性时间译码。 d a s p i e l m 柚门开发了一种试探法来寻找非规则l d p c 码参数的分布，据此构 造了在低信噪比下比码率为l 2 的n r b o 码的b e r 还低的u p c 码。j c a m p e l l o 等1 8 l 提出采用扩展的b i t f i l l i n g 算法来设计具有高码率高g i n h 的性能良好的u ) p c 码。y m 和a h b a n i h a s h 锄i 1 9 】则基于性能准则，提出根据g i n h 的分布来设计好 的l d c p 码的方法。s j j 0 h n s 0 n 掣1 0 1 人构造和在其n e r 图中不出现环长为4 ， g i n h 至少为6 的规则u ) p c 码，该u ) p c 码具有高码率，码长短等性能。 n v a n i c a 等f 1 1 l 对文献【4 j 中的优化方法进行了改进，用于有符号间干扰的部分响 应信道中的u ) p c 码的优化。目前一些学者探讨了基于有限几何学的u ) p c 码的 4 结构，并构造出了性能优于随即构造的( 3 ，6 ) 规则u ) p c 码i 捌k 肌等人提 出了一种基于有限几何点和线的几何构造方法，作为这种方法的推广【切，进一步 提出了基于部分几何点和线的几何构造方法，还有一些研究学者将s t c i l l 盯三连系、 循环差族和循环差集也被引进u ) p c 码的构造中，这些组合方法中的大部分都能 得到编码复杂度较低的准循环码。 在现代通信系统中，纠错码的设计是保证数据可靠传输的一个重要组成部分， 因为它可以检测并纠正信号传输过程引入的错误。1 9 4 8 年，s h 枷提出并证明 了一个理论：对于一个信道容量为c 的有扰信道，消息源产生信息的速率为r ， 只要rs c ，则总可以找到一种信道编码和译码方式，使编码错误率随着码长的增 加，按照指数下降到任意小的值；若r ) c ，则不存在能够实现无误码率传输的编 译码方式。但是s h 蝴定理并没有指出相应的实现方式若干年来，随着通信 技术的高速发展和实际应用的不断提高，人们一致的努力寻找能够更加逼近 s h 锄衄理论极限的优秀编译码方法，从早期的分组码、代数码、到r s 码、卷积 码，知道今天的1 i l r b o 码、u ) p c 码，系统性能与s h 锄极限的差距越来越小 虽然u ) c p 码的理论以及应用研究已取得了不少进展，但仍有存在许多问题 需要解决，如码字结构的优化，编码的复杂度，译码算法的简化以及实现。 1 3 信息隐藏技术发展概况 目前，随着i n t 锄c t 的高速发展、信息处理技术和通信手段的迅猛发展，使得 图像、音频、视频等多媒体信息可以在各种通信网络中高速及时的传输，从而给 信息的压缩、存储、复制处理等应用提供了更大的方便。与此同时，也给信息资 源的共享提供了条件，目前如t c m c t 是当今社会的主要通讯方式之一。各种机密信 息，包括国家安全信息、军事信息、个人信息( 如身份证件号等) 等都需要通过 互联网络进行传输，但h t c m e t 是一个开放的环境，在其上传输的秘密关系着国家 安全、经济发展和个人稳私等方方面面的安全，所以信息安全在当今变得越来越 重要信息隐藏的出现为信息安全提供了有力的保障。 信息隐藏技术主要性能指标： 1 ) 不可觉察性：将隐藏信息隐含于载体信号后，载体信号的变化应当满足于 人的视觉和计算机数据处理的不可觉察性的要求。 2 ) 保真性：嵌有隐藏信息的数字媒体出现一定的失真时，隐藏信息能够在保 证较低错误率的条件下加以恢复，或者在多种无意或故意的攻击性操作后，仍能 保持原有的信息完整性、可靠性和秘密信息的可检测性。 3 ) 隐藏容量：即载体信号中隐藏信息的最大比特数。 5 目前信息隐藏技术在信息安全的各个领域中所发挥的作用系统地总结为五个 方面： 1 ) 数据保密 在网络上传输数据要防止非授权用户截获并使用，这是网络安全的一个重要 内容。随着经济的发展，世界联系日益密切，这一点不仅涉及政治、军事，还涉 及到商业、金融和个人隐私等多个方面。而我们可以通过使用信息隐藏技术来保 护在网上交流的信息，如网上银行交易中的客户密码等数据信息、重要文件的数 字签名和个人隐私等。另外，还可以对一些保密内容使用信息隐藏的方式进行隐 藏存储。 2 ) 数据的不可抵赖性 交易中重要的一个环节就是交易的双方不能抵赖自己曾经做出的行为，也不 能否认曾经接收到对方的信息。然而现实中经常出现交易中的一方否认自己行为 的现象。水印技术为解决上述问题提供了解决办法。在交易体系的任何一方发送 或接收信息时，将各自的特征标记以水印的形式加入到传递的信息中，这种水印 应是不能被去除的，以达到确认其行为的目的。 3 ) 数字作品的版权保护 敝权保护是信息隐藏技术中的水印技术所解决的一个重要问题。随着网络和 数字技术的快速发展，通过网络向人们提供的数字服务也会越来越多，如数字图 书馆、数字图书出版、数字电视、数字新闻等数字信息。数字信息具有易修改、 易复制的特点，从而出现了非法盗版等现象，如今已经成为迫切需要解决的实际 问题。数字水印技术为解决此难题提供了一种有效的方案。 4 ) 防伪 商务活动中的各种票据的防伪也是信息隐藏技术应用的一个方面。在数字票 据中隐藏的水印经过打印后仍然存在，可以通过一定的处理，提取防伪水印，证 实票据的真实性。 5 ) 数据的完整性 数据完整性的验证就是要确认数据在传输或存储过程中是否被窜改。通过使 用水印技术保护的媒体一旦被窜改就会破坏水印，从而很容易被识别。 科学的发展、新技术和新工艺的应用，为信息隐藏技术的进一步发展奠定了 重要基础。信息隐藏、多媒体技术、密码学、语音处理等技术体系密切相关。隐 藏技术作为一门跨多个领域、多个学科( 数字信号处理、图像处理、模式识别、 数字通信) 的学科，因此这也决定了信息隐藏技术研究成果的多样性以及信息隐 藏技术研究的不完善性，所以仍有许多技术问题需要解决。但可以相信，随着科 学技术的飞速发展，信息隐藏技术将有更多的新创意、新方法和新理论，不断完 6 善和更新 1 4 本课题研究内容 采用空间域和变换域信息隐藏方法时，信息隐藏在遇到比特攻击时，存在难 以恢复隐藏信息的缺点，这使得信息的隐藏成为问题。为解决这一问题，类似【摊1 司 的1 u f b 0 隐藏和水印技术，本文提出一种基于u ) p c 码的数字图像信息隐藏算法， 对要隐藏的信息进行u ) p c 编码，编码后的数据隐藏到载体图像中，然后通过信 道传输，在接受端提取出隐藏信息，再进行u ) p c 解码，从而恢复出隐藏信息。 由于u ) p c 码具有很强的纠错能力，所以本算法克服了传统空间域信息隐藏算法 和变换域隐藏算法的抗比特攻击能力差的缺点，尤其是在强比特攻击情况下，隐 藏信息的误码率仍很低，能近似无损的恢复隐藏信息所提算法具有空间域算法 优点：简单、速度快、易于实现；同时又具有变换域算法的优点：仅对隐藏信息 进行编码，确保信息的不可见性。 本文结构如下： 第2 章u p c 码。简单介绍了纠错码的基本概念，包括数字通信系统的组成， 信道模型分类，最大似然译码，信道编码定理，线性分组码的一些相关知识，规 则l d p c 码的编码算法，校验矩阵h 的构造 第3 章l d p c 码解码介绍了硬判决和软判决译码概念，以及两种u ) p c 译 码算法。 第4 章基于u ) p c 码的数字信息隐藏系统本章对信息隐藏技术进行了概括 的介绍并对本文提出的隐藏系统各部分进行了介绍。最后进行系统仿真，并给出 实验结果。 第5 章总结。简单阐述一下本课题所做的工作，并提出下一步工作目标。 7 2l 】9 p c 码 近年来，信道编码领域的研究热点就是关于u ) p c 码的研究。由于其具有比 1 _ i i r b o 码f 1 7 】更接近s h 仰蛆限的原因，所以对它的研究具有很大意义。在本章中， 我们先介绍一些纠锗码的基本概念以及线性分组码的相关原理，然后再介绍u ) p c 码的相关技术。 2 1 纠错码的基本概念 所谓纠错码，就是指在译码器端不仅能发现错误，还能自动纠正错误的码字 在通信中使用纠错码进行编码，可以大大的降低误码率，提高通信质量。如今， 纠错码受到了越来越多的通信和数学工作者，特别是代数学家的重视，使纠错码 无论是在理论还是实际中都得到了飞速发展。 通常按以下方式对纠错码进行分类： 1 ) 按照对信息元处理方法的不同，纠错码分为分组码与卷积码两大类。 分组码是把信源输出的信息序列，以k 个码元划分为一段，通过编码器把这 段k 个信息元按一定规则产生r 个校验元，输出长为n - k + r 的一个码组。因此每一 码组的校验元仅与本组的信息元有关，而与别组无关。分组码用( n ，k ) 表示，n 表示 码长，k 表示信息位 卷积码是把信源输出的信息序列，以个七0 码元分为一段，通过编码器输出长 为( 之) 一段码段。但是该码段的雄。一个校验元不仅与本组的信息元有 关，而且也与其前m 段的信息元有关，称m 为编码存贮。因此卷积码用( 开。，m ) 表示。 2 ) 根据校验元与信息元之间的关系，纠错码分为线性码和非线性码。若校 验元与信息元之间的关系是线性关系( 满足线性叠加原理) ，则称为线性码；否则， 称为非线性码 3 ) 按照纠正错误的类型，纠错码可分为纠正随机( 独立) 错误的码、纠正突发 错误的码和纠正同步错误的码，以及既能纠正随机错误又能纠正突发错误的码。 4 ) 按照每个码元取值来分，纠错码可分为二进制码与q 进制码( q = p m ，p 为素 数，m 为正整数1 。 5 ) 按照对每个信息元保护能力是否相等，纠错码可分为等保护纠错码与不等 保护e p ) 纠错码。此外，在分组码中按照码的结构特点，又可分为循环码与非循 环码。纠错码分类用图2 1 表示。 9 在本节里，我们将简单的介绍一下有关纠错码的基本知识包括数字通信系 统的组成，以及信道模型的分类，最大似然译码和信道编码定理。 图2 1 纠错码的分类 脚卵2 1 n c a 瓣i 置j 髓6 o f m c 脚c o m c t 咄c o d e 2 1 1 数字通信系统的组成及信道模型分类 数字通信系统的组成 通信的目的是要把对方不知道的消息及时可靠地( 有时还须秘密地) 传送给对 方，因此，要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠 与快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占的时间缩短、 波形变窄、能量减少，从而在受到干扰后产生错误的可能性增加，传送消息的可 靠性减低。若要求可靠，则使得传送消息的速率变慢。因此，如何较合理地解决 可靠性与速度这一对矛盾，是正确设计一个通信系统关键问题之一。通信理论本 身( 包括纠错码) 也正是在解决这对矛盾中不断发展起来的。 所有数字通信系统都可以用图2 2 表示。如通信系统，雷达系统，遥控系统， 数字计算机存贮系统等等都可以归结成图2 2 的模型。 图2 2 数字通信系统模型 f 置g 呲2 2n cd i g i i a ic o 咖桃l 妇硒ns y s 咖lm o d e l 在此模型中，信源是指信息的信源和信源编码器，其输出是二进制或多进制 信息序列。编码器是指信道编码器。信道是包括发射机、实际信道( 或称传输媒质) 和接收机在内的广义信道( 又称编码信道) ，它的输入是二进制或多进制数字序列， 输出一般也是二进制或多进制数字序列，解码器是指信道解码器，而图中的信宿 可以是人或计算机。 信道模型 现在以图2 2 的模型来讨论二进制数字序列通过该系统时所发生的情况。设从 信源送出二进制序列，以基带信号传送，经发射机调制后，送往信道的已调信号。 由于信道的干扰，从信道输出端的信号产生了失真，这些失真信号送入接收机进 行判决时，由于失真严重而难于判决。这时有以下三种判决方法：一是勉强作出 是o 还是1 的判决，即所谓硬判决；另一种是对该码元暂且不作判决，而输出一 个未知或待定的信号“x ”，称其为删除符号；第三种方法是输出一种有关该码元的 信息，例如关于o 和1 的后验概率或似然函数，这种作法称为软判决。当然软判 决的性能较好，但实现起来较复杂。 在二进制硬判决情况下，信道可用图2 3 所示的简单模型表示。图中，。和a 。 分别是o 错成l 和1 错成o 的概率，称信道转移概率。该信道的信道转移概率矩 阵可用 p 。匕坩= ，：。】 描述。如果p m = 见。= 见，则称这种信道为二进制对称信道，简称b s c 。否则，称 为不对称信道。若p 0 1 或p l 。等于零，则称为z 信道。通常b s c 是一种无记忆信道， 所以也称随机信道，它说明数据序列中出现的错误彼此无关。 l l i 图2 3 二进制信道模型 f i g u 2 3 砸地b 缸a r y c h 蛐n e l m o d d 如果信道的输入是二进制符号，而输出是离散的鼋( g p 。王2 ) 进制符号，如图 2 4 所示，且p g 协一p ( 口一1 一f 眇，f - o 工，口一l ，则这种信道称为离散无记忆信道 p m q ，显然b s c 是d m c 的一种特殊情况。d m c 的信道转移概率矩阵为： o l p p ( 0 l o ) p ( 1 1 0 ) p ( q 一1 i o ) 1 l p ( 0 1 1 ) p ( 1 1 1 ) p ( g 一1 1 1 ) i 图2 4 离散无记忆信道 f i g i i 托2 4n e d i s m t em 咖r y l e 站c h a 皿d o j 口一2 一l 在作删除判决情况下，信道可用图2 5 所示的模型表示，称为二进制删除信道， 简称b e c ，一般它也是对称信道图中，p 。为信道的转移概率，q 为删除概率， 在有删除处理情况下，信道的转移概率见一般很小，可忽略，因此把图2 5 所示 的模型用图2 6 代替，称为二进制纯删除信道。应当指出，当码元作删除处理时， 它在序列中的位置是己知的，仅不知其值是0 还是1 ，故对这种髓c 信道的纠错 要比b s c 信道容易 o o 图2 5 二进制删除信道 f i g i l 2 - 5t h eb i 帕r yd c l e t ca 啪d 图2 6 二进制纯删除信道 f i g i l ”2 6 n e 晌a i y p 峨d c l e t e c h m e l o 0 上述三种信道模型只是简化的理想情况，它们表达了某些实际信道传送信号 的主要特征。例如，卫星信道或深空信道，可近似看成是b s c 。但有很多实际信 道如高频、散射、有线等信道，由于各种干扰所造成的错误，往往不是单个地而 是成群成串地出现的，也就是一个错误的出现，往往引起其前后码元的错误( 突发 错误) ，表现为错误之间的相关性。产生这种错误的信道称有记忆信道或突发信道。 在计算机存贮系统中，磁带的缺陷或读写头接触不良所引起的错误，也属于这种 类型。但由于实际信道干扰的复杂性，所引起的错误往往不是单纯的一种，而是 两种错误形式并存，只不过有的信道以某种错误形式为主罢了 像这种随机错误与突发错误并存的信道，称为组合信道或复合信道。作为检 错与纠错用的抗干扰码，必须针对这几类信道，设计能纠正随机错误或纠正突发 错误的码，或者设计既能纠正随机错误又能纠正突发错误的码。 2 1 2 最大似然译码和信道编码定理 最大似然译码 由图2 2 可知，信道输出的r 是一个二进制或多进制序列，而译码器的输出是 一个信息序列m 的估值序列m 译码器的基本任务就是根据一套译码规则，由接收序列r 给出与发送的信息 序列m 最接近( 最好是相同) 的估值序列l f 。由于信息序列m 与编码器输出码字c 之间存在一一对应关系，所以这等价于译码器根据r 产生一个c 的估值序列c 。 显然，当且仅当c = c 时，肼= m ，这时译码器正确译码。 如果译码器输出的c c ，则译码器产生了错误译码。之所以产生错误译码是 由于：信道干扰很严重，超过了码本身的纠错能力；其次，由于译码设备的故障。 当给定接收序列r 时，译码器的条件译码错误概率定义为 p 但i r ) 尸( c c i r ) 所以译码器错误译码的概率： 最一雌l r 妒僻) p ( 鼬是接收r 的概率，与译码方法无关，所以译码错误概率最小的最佳译码规则 是使： m i n 最一n 唾n p ( e i r ) 一啪曲p ( c ，c i r ) m i n p ( c - c i 露) 辛m a 】【p ( ct c i r ) 因此，如果译码器对输入的r ，能在矿个码字中选择一个使p ( c 产c l 尺) ( i = 1 ，2 ，2 ) 最大的码字c 作为c 的估值序列c ，则这种译码规则一定使译码 器输出错误概率最小，称这种译码规则为最大后验概率译码。由贝叶斯公式 粥- 警 可知，若发端发送每个码字的概率p ( g ) 均相同，且由于p ( r ) 与译码方法无关，所 1 4 以可以得出； m a 】【p ( qir ) 一m 缸p 僻i c ) f 吐2 一僖j - 1 ，2 ，r ，2 i 对d m c 而言 ( 2 1 ) 即ic j ) - 兀盹i 勺) ，- t 这里码字c f 一( c j l ，c 。，气) ，i = 1 ，2 ，矿 一个译码器的译码规则若能在2 1 个码字c 中选择某一个c 使( 2 1 ) 式成为最 大，则这种译码规则称为最大似然译码( m l d ) ，p 俾i c ) 称为似然函数，相应的译 码器称为最大似然译码器。由于h d g 。z 与z 是单调关系，因此推出： ；- 玎筹1 。p ( 刚c 1 ) 。，三筹善1 。岛p 瓴l 勺) 称l o g 。袱l c ) 为对数似然函数或似然函数。对于d m c 信道，m l d 是使译码错误 概率最小的一种最佳译码准则或方法，但此时要求发端发送每一码字的概率尸 ( i ：1 ，2 ，) 均相等，否则m l d 不是最佳的。 信道编码定理 信道编码定理规定，每个信道具有确定的信道容量c ，对任何小于c 的码率r ， 存在有速率为r 码长为n 的分组码，若用最大似然译码，则随着码长的增加其译 码错误的概率p 可任意小，即 p 爿，一“忸) ( 2 2 ) 式中，a 为大于o 的系数，e 俾) 是正实函数，称为误差指数，它与r 、c 的关系 如图2 7 所示。 图2 7e ( r ) 与r 的关系 f i 伊陀2 7 ，r k 馆h t i o n s h i po f e ) a n dr 图中，c l ，c 2 为信道容量，且c 1 巴由信息论的基本知识可知，在高斯自噪声 信道时，信道容量： “形l o g ：1 1 + 蒜p 加) lj 式中，w 是信道所能提供的带宽，只层。仃是信号功率，e ，是信号能量，r 是分 组码信号的持续时间即信号宽度，只彤是单位频带的信号功率，j ，o 是单位频带 的噪声功率，( i j ) 是信噪比。 由公式( 2 2 ) 和图2 7 可看出，信道容量c 、码长n 和错误概率p 之问的转换 关系。为了满足一定误码率p 的要求，可用以下两类方法实现。 一是增加信道容量c ，从而使e 僻) 增加。由c 的表示式可知，增加c 的方法 可以采用如加大系统带宽或增加信噪比的方法来达到。例如，采用调频、调相等 宽带调制方法；增加发射机的功率；应用高增益天线；采用分集接收及低噪声器 件等方法。这些措施是从根本上改善信道、增加信道容量、减少误码率的方法， 是通信设计工作者经常采用的传统方法 另一种方法是在r 一定下，增加分组码长n ( 也就是增加分组信号持续时间d ， 可使p 随n 的增加而呈指数下降。但由于码长n 的增加，当r 保持一定时，可能 发送的码字数2 指数增加，从而增加了译码设备的复杂性。这种方法就是信道编 码定理所指出减少误码率的另一方向，它为通信设计工作者提供了一条新的途径。 2 2 线性分组码 分组码是把信源编码器输出的信息序列，以k 个码元划分为一段，通过编码 器把这段k 个信息元按一定规则产生r 个校验元，输出长为n - k + r 的一个码组。因 此每一个码组的校验元仅与本组的信息元有关，与别组无关。分组码用【n ，k 1 表示， 其中，n 表示码长，k 表示信息位。如果校验元与信息元之间是线性关系，即满足 线性叠加原理，则称该分组码为线性分组码；否则，称为非线性分组码。本文如 无特殊说明，分组码均指线性分组码。 一个i n ，k 】线性分组码，也可以也用【n k d 】表示，其中d 为线性码的最小距离。 线形分组码的最小距离等于非零码字的最小重量。r 一| 力，r 为分组码的码率。 r 和d 是分组码的两个最重要的参数。 2 2 1 码的校验矩阵与生成矩阵 1 6 【n ，k ，d 】分组码的编码问题就是在n 维线性空间k 中，如何找到满足一定要求 的，有个矢量组成的k 维线性子空间k 。或者说，在满足给定条件下，如何 从已知的k 个信息元求得r = n - k 个校验元。这相当于建立一组线性方程组，已知k 个系数，要求n - k 个未知数，使得到的码字恰好满足给定的条件。如在分组码【 4 】 中用c 6 ，c 5 ，c 4 表示3 个信息元，用c 3 ，c 2 ，c l ，c o 表示4 个校验元，可从以 下方程组求得： c 6 + c + c ，- 0 c 6 + 岛+ c 4 + c 3 + c 2 1 0 c 6 + c ，+ c l o c 5 + c + c o o ( 2 3 ) 上述运算为模2 运算，因此当3 个信息元确定以后，就可以由方程组( 2 3 ) 求出4 个检验元。通过检验【7 ，3 ，4 】码的8 个码子我们知道，它们均满足方程组( 2 3 ) 若用矩阵形式表示这些线性方程组，则( 2 3 ) 式可表示成： 或 1o1 1o0o 11 1010o 1 1oool0 0110oo1 【c - c ，c c ，cz c - c 。】 c 岛 c c 3 c 2 c l c o = 0 r ( 2 4 ) = o o o o = o ( 2 5 ) 称( 2 3 ) 中4 行7 列矩阵为【7 ，3 ，4 】码的一致校验矩阵，通常用h 表示，该 码字的校验矩阵为： 1 7 o 1 l o o 0 1 l 1 o 0 o 1 0 1 l l o l o o 1 o 1 1 o 0 o 日一 101 10o0 11101oo 11ooo10 0110 o o1 一般情况下，任何一个【n ，k d 】码的一致校验矩阵h 可表示为： h - k 。 也。- l 一4 。- l k i 以4 o 它是一个o 一七) x 刀阶矩阵。由h 矩阵可以很快建立码的线性方程组： i 1 1 。- 1 红。4 吃。- 1 或 k 2 吃。： - 七。一2 巳一2c o 简写为： h c 7 0 7 或c 日7 - 0 i l l o k o ： o k 4 啊j ，一2 ： q - 1 q 一2 ： 2 j i 一、 2 鼻一2 。矿 吃一t 。- 1 玩- 七。一2 吸，oj l z 2 ，o 。4 ，o 一0 可知h 矩阵的每一行代表一个线性方程组的系数，它表示求一个校验元的线 性方程。因此任何一个【n ，l 【d 】码的h 矩阵必须有n k 行，且每行必须线性独立。若 把h 的每一行看成一个矢量，则这( n - k ) 个矢量必然张成了n 维线性空间中的一 个n - k 维子空间k 。 由【n ，l 【，d 】码的每一个码字必须满足式日c 7 0 7 或c h 7 0 ，即它的每一个 鬈；一 码字必然在由h 矩阵的行所张成的k 。空间中的零空间中。所以k ，。的零空间必 然是一个k 维子空间屹j ，而这正是【n ，l 【，d 】码的码字集合全体所以k ，。和【n l 【