（信号与信息处理专业论文）纠错码及其在数字水印技术中的应用研究.pdf

五邑大学硕士学位论文 摘要 数字水印技术( d i g i t a lw a t e r m a r k i n gt e c h n o l o g y ) 是新兴的信息隐藏技术。在 互联网等信息产业高速发展的带动下，其应用已日益广阔，并已引起学术界、工业 界和军方的广泛关注。近年来，随着纠错编码技术的发展，结合纠错编码的数字水 印系统已成为提高数字水印鲁棒性的关键技术。本文针对图像数字水印应用的特点， 提高图像数字水印系统的鲁棒性，研究了新型的纠错编码，并将其应用于图像数字 水印系统中。 本文主要完成如下工作： 1 研究了各类纠错编码的理论，着重研究了准循环l d p c 码，基于二部图， 介绍了l d p c 码的的概念与构造方法后，详细地介绍了准循环l d p c 码的 构造及其编码算法，得出了准循环l d p c 码的编码复杂度较低，在中短码 具有具有优越的译码性能。 2 研究了l d p c 码的迭代译码原理，从和积算法的数学基础出发，推导了和 积算法全过程，并研究了其k - m i n 简化算法，最后结合串行和积译码算法提 出了译码改进算法，研究表明，简化前后的译码性能相差不大，但由于处理 的边数量大大减少，提高了数据的传输速度从而译码速度也得到了提高；改 进译码算法由于结合了串行和积译码算法的特点：在本次迭代计算更新节点 时，前面已经更新过的外信息可被用于本次的计算，因此减少了译码的迭代 次数，进一步的提高了译码的速度。 3 研究了数字水印技术原理，着重介绍了数字水印算法中的空域算法和频域算 法等的几种典型算法，为后续建立纠错编码的数字水印系统方案提供参考。 4 介绍了小波变换基本理论，研究了基于q c l d p c 码的数字水印系统的模型， 并对模型在m a t l a b 环境下进行仿真，仿真结果表明水印图像在经j p e g 压缩后或经加性高斯信道传输后，水印图像具有很强的鲁棒性和不可见性。 结合纠错编码的数字水印系统已成为信息安全领域研究的热点，随着技术的成 熟，越来越多这样的数字水印系统将在实际中得到应用。 关键词：低密度校验码，前向纠错码，和一积算法，a , - m i n 简化算法，准循环l d p c 码，数字水印技术 五邑人学硕+ 学位论文 a b s t r a c t d i g i t a lw a t e r m a r k i n gt e c h n o l o g yi san e wt e c h n o l o g yo fi n f o r m a t i o nh i d d e n a l o n gw i t ht h ef a s t d e v e l o p m e n to fi n t e m e ta n do t h e ri n f o r m a t i o ni n d u s t r y , i th a sb e e nw i d e l yu s e da n dh a sa r r e s t e dg r e a t a t t e n t i o n sf r o mt h ea c a d e m i a , i n d u s t r ya n da r r a yb c c a u s eo fi t se x c e l l e n tp c t - f o n a l a n c ei ni n f o r m a t i o nh i d d e n r e c e n t l y , w i t ht h ed e v e l o p m e n to ft h ec o d i n gt e c h n o l o g y , d i g i t a lw a t e r m a r k i n gs y s t e mb a s e d0 1 1c o d i n g t e c h n o l o g yh a sb e c o m em o r ea n dn l o r ei m p o r t a n t s i n c em b u s m e s si so t l co ft h ei m p o r t a n tr e q u i r e m e n t so f d i g i t a lw a t e r m a r k i n gs y s t e m , i tc a nb ei m p r o v e db yc o d i n gt e c h n o l o g y i no r d e rt oi m p r o v er o b u s m e s so f w a t e r m a r ka n dp r o t e c tt h ec o p y r i g h to fd i g i t a lw o r k s ，f o r w a r de r r o rc o r r e c t i o nc o d e sa n dw a t e r m a r k i n gs y s t e m a r er e s e a r c h e di nt h i sp a p e f o 1 r i 埒m a i nc o n t e n t sa n dr e s u l t sa r ca sf o l l o w s 1 b a s e d0 1 1t h eb i p a r t i t eg r a p h , t h ed e f i n i t i o na n dc o n s t r u c t i o n so fl d p cc o d e sw e 他a d d r e s s e d e s p 。地t h ec o n s t r u c t i o nm e t h o d so fq u a s i - c y c l i cl d p cc o d e s w e r es t u d i e d , a n dt h ed e c o d i n g p e r f o r m a n c ew a sa l s oi n v e s t i g a t e db yc o m p u t e rs i m u l a t i o n i tw 鹬s h o w nt h a tq c l d p cc o d e sh a v ep o w e r e t t o rc o r r e c t i n ga b i l i t ya tm o d e r a t eo rs h o r tl e n g t h t h eb i te l r o tr a t ei sv e r yc l o s et ot h a to ft h eb e s tl d p c c o d e so na w g nc h a n n e l s oi tc a nb ee x p e c t e dt h a tt h eq c - l d p cc o d e sw i l lh a v ew i d ea p p l i c a t i o ni nf u t u r e 2 t h ep r i n c i p l e so fs o f td e c o d i n ga n dm e s s a g ep a s s i n gw e l ed i s c u s s e d b a s e do i lt h eb i p a r t i t eg r a p ha n d t h er e l a t i n gm a t h e m a t i ct h e o r y , t h es u m - p r o d u c ta l g o r i t h ma n di t sr e d u c e dc o m p l e x i t ya l g o r i t h m sw e r e p r e s e n t e df o rd e c o d i n g a tt h ee n d , a ni m p r o v e dd e c o d i n ga l g o r i t h m , b a s e do nr a i n - s u m - p r o d u c t ( m s p ) a n d s e q u e n t i a l - s u m - p r o d u c t ( s - s p ) ，i sp r e s e n t e d t h es i m u l a t i o nr e s u l t sh a v es h o w nt h a t7 , - m i na l g o r i t h m sw i t h r e d u c e dc o m p l e x i t yw o r k 8a sw e l la st h es t a n d a r ds u m p r o d u c ta l g o r i t h m so n l yw i t hal i t t l ep e r f o r m a n c el o s s a n dt h ei m p r o v e dd e c o d i n ga l g o r i t h mi sb e t t e rt h a n m i na l g o r i t h m s t h e r e f o r e , i tc a nb ee x p e c t e dt ob e u s e di nh i g hd a t ar a t ec o m m u n i c a t i o n 3 t h ed i g i t a lw a t e r m a r k i n gt e c h n o l o g yw a sr e s e a r c h e d i no r d e rt ob u i l da # o c t d i g i t a lw a t e r m a r k i n g s y s t e ml a t e r , s o m ec l a s s i c a la l g o r i t h m so f d i g i t a lw a t e r m a r k i n gs y s t e mw e 佗s t u d i e da tf i r s t 4 a f t e rs t u d y i n gt h et h e o r yo fw a v e l e tt r a n s f o r m , ad i g i t a lw a t e rm a r k i n gs y s t e mb a s e do t lq c - l d p c c o d em o d e li sp r e s e n t e d b ya p p l y i n gt h eq c - l d p cc o d e sa n d m i na l g o r i t h mi nt h em o d e ls i m u l a t i o n , i t s h o w st h a tt h i ss c h e m ec a ng r e a t l yi m p r o v et h er o b u s t n e s sa n dw a n s l m e t 酵c l a r i t yo f w a t e r m a r k i n g r e c e n t l y , d i 西t a lw a t e r m a r k i n gs y s t e mb a s e do ne l r o l c o n c g t i o nc o d eh a sa t t r a c t e dm u c ha t t e n t i o n p a r t i c u l a r l yi nt h ef i e l do fi n f o r m a t i o ns a f e t yf i e l d w i t ht h em a t u r i t yo ft e c h n o l o g y , l n o a n dm o r ed i g i t a l n 五邑人学硕十学位论文 w a t e r m m l d n gs y s t e m sl i k et h i s 、加1 1b ew i d e l yu s e di nt h ef u t u r e k e yw o r d s ：l o w - d e n s i t yp a r i t y - c h e c kc o d e s ，f o r w a r de r r o rc o r r e c t i o n ；s u m p r o d u c ta l g o r i t h m ， 他n i i lr e d u c e dc o m p l e x i t ya l g o r i t h m ，q u a s i - c y c l i cl d p cc o d e s ，d i g i t a lw a t e r m a r k i n gt e c h n o l o g y i i i 五邑大学硕士学位论文 本人声明 我声明，本论文及其研究工作由本人在导师指导下独立完成。在 完成论文时所利用的一切资料均己在参考文献中列出。 五邑人学硕士学位论文 第一章绪论弟一早三否。t 匕 1 1 课题的提出与现实意义 近年来，由于计算机网络和多媒体技术的迅速发展，越来越多的数字作品开始 在网络上传播，i n t e r n e t 的发展为数字作品的广泛传播创造了条件，但由于网络多 媒体作品极易被高速、低成本地复制，这就容易被盗版者所利用，因此研究保护网 络多媒体作品版权的各种技术和方法已迫在眉睫n 1 。其中纠错码对数字水印的鲁棒 性更是起到着决定性的作用。因此针对水印的特点结合纠错码的研究是至关重要的。 数字水印技术的应用前景和领域更是显而易见! 它主要包括以下几种应用领域 【2 一1 2 】 ( 1 ) 用于版权保护的水印。版权保护是水印最主要的应用。其目的是嵌入数据的 来源信息以及比较代表性的版权所有者的信息，从而防止其他团体对该数据宣称拥 有版权。这样水印就可以用来公正地解决所有权问题，这要求水印必须有较好的鲁 棒性、安全性、透明性和水印的嵌入的不可逆性。 ( 2 ) 图像认证。认证的目的是检测对图像数据的修改。可用易碎水印( f r a g i l e w a t e r m a r k ) 来实现图像认证。为了便于检测，易碎水印对某些变换( 如压缩) ，具有 较低的稳健性( 鲁棒性) ，而对其他变换的稳健性更低。因而在所有的数字水印应用 中，认证水印具有最低级别的稳健性要求。 ( 3 ) 标题与注释。将作品的标题、注释等内容以水印形式嵌入该作品中。这种隐 蔽式注释不需要额外的带宽，且不易丢失。 ( 4 ) 拷贝保护。在多媒体发行体系中，希望存在这样的一个拷贝保护机制，即它 不允许未经授权的媒体拷贝。在开放系统中很难实现拷贝保护，然而在封闭或私有 系统中，拷贝保护是可行的。在这样的系统中，可用水印来说明数据的拷贝状况。 ( 5 ) 篡改提示。当数字作品被用于法庭、医学、新闻及商业时，常常需要确定它 们的内容是否被修改、伪造或特殊处理过。为实现该目的，通常将原始图像分成多 个独立块，每个块中加入不同的水印。为确定其完整性，可通过检测每个数据块中 的水印信号来确定作品的完整性。与其他的水印不同的是，这类水印必须是脆弱的， 并且检测水印信号时，不需要原始数据。 第章绪论 ( 6 ) 盗版跟踪。数字水印还有一些其他的应用，它们的目的是传输合法接收者的 信息而不是数据来源者的信息，主要用来识别数据的单个发行拷贝。这一类应用在 发行的每个拷贝中嵌入不同的水印，通常称之为“数字指纹 。对每个拷贝各自嵌 入水印的情况，因为它们的发行要面临共谋攻击的危险，所以嵌入的水印应该设计 成对共谋攻击而言是安全的。同样，对于某些数字指纹应用来说，它们要求水印易 于提取，且有很低的复杂度。数字指纹应用中的水印也需要很高的鲁棒性，不仅要 能抵抗恶意的攻击，还要能抵抗一些标准数据处理。水印系统可以由一些特性来描 述其特征，每一个特性的重要性取决于实际应用的需要和水印的作用。在不同的应 用环境中水印应具有不同的特性，一般有以下几点： 不可感知性；鲁棒性：密钥唯一性；嵌入有效性；不可逆性；产品依赖性： 多重水印：检测可靠性：计算有效性：安全性。 1 2 当前国内外的研究动态 数字水印的概念虽然是在2 0 世纪9 0 年代提出的，但是，对它的研究可以追溯到 2 0 世纪5 0 年代。美国m u z a c 公司的e m a i lh e m b r o o k e 在1 9 5 4 年申请了一项名为 “i d e n t i f i c a t i o no fs o u n da n dl i k es i g n a l s ”的专利。该专利描述了一种将标识码不可感 知地嵌入到音乐中而证明所有权的方法。这是迄今为止所知道的最早的电子 ( e l e c t r o n i cw a t e r m a r k i n g ) 技术。 之后，人们对数字水印的研究兴趣日益增长。自从第一届国际信息隐藏学术研 讨会于1 9 9 6 年5 月3 0 日6 月1 日，在英国剑桥牛顿研究所召开，及s p i e 和i e e e 的一 些重要国际会议也开辟了相关的专题以来，随着数字水印技术研究的不断深入，数 字水印从研究对象上来已经涉及到图像水印、音频水印、文本水印、视频水印和三 维网格数据水印等几个方面。 目前数字水印领域研究主要集中在水印嵌入策略和鲁棒性强的水印算法，到目 前为止水印领域己经取得了一定的理论成果，包括数字水印的信息理论和通信理论， 提出了利用扩频技术的数字水印算法和边信息数字水印算法等好的水印算法n 3 q 引， 总结了水印评价理论和测试基准，同时研究新的水印攻击方法以提高水印的抗攻击 能力，近来抗几何攻击水印技术也是一个研究热点，也有不少研究者研究在相关的 图像和视频压缩标准j p e g 2 0 0 0 ，m p e g 2 ，m p e g 4 等嵌入水印。虽然数字水印技术取 2 五邑大学硕士学位论文 得了这么多的研究成果，但仍有一些方面被研究者忽略了。如针对数字水印技术的 特点用信道编码的概念设计出较为实用的编、译码算法应用于水印应用系统中研究 的人还较少。尽管在利用信道编码技术上，p 6 r e z ，g o n z f i l e z 1 9 1 等人研究了分组码、卷 积码和正交码在水印技术方案中的作用，但他们的工作结果只建立在扩频水印方案 上，且在对如何进步简化编译码及提高编码的纠错能力方面并没有做太多的考虑。 再如，b a u d r ys e v e r i n e 2 0 】等人也只讨论了b c h 和卷积码的情况；谷利刚2 等人也分 析了数字水印信道中的分组码编码的策略。目前对于分析数字水印信道中的l d p c 码编码策略的人也很少，以及对如何进一步的研究将l d p c 码运用于数字水印系统 中并简化其编码算法提高译码效率等的人就更少了。 1 3 本论文的内容安排 第一章绪论。先介绍了题目来源和研究背景，接着介绍了数字水印的特征并对 国内外的研究状况进行了简单的介绍，最后是关于本论文的内容安排。 第二章纠错码原理与方法。先简要介绍数字通信系统的基本模型，然后回顾四 种典型纠错编码的原理与方法，最后概述了逼近仙农限的两种纠错码一t u r b o 码和 l d p c 码。 第三章q c l d p c 码的编译码算法。先简单的介绍l d p c 码的基本概念及一些 常用的编码算法，接着着重介绍q c l d p c 码的编译码算法，最后提出改进译码算 法，并进行了计算机仿真与性能分析。 第四章数字水印技术。先介绍数字水印原理、攻击以及性能与容量等基本理论， 最后再分析数字水印的几种典型算法，为第五章建立的数字水印系统提供参考。 第五章纠错码在数字水印技术中的应用。从小波变换的基本理论出发，分析了 在小波域数字水印算法的透明性，最后结合纠错编码研究了基于纠错编码的数字水 印系统，并进行实验仿真与分析。 第二章纠错码原理与方法 第二章纠错码原理与方法 1 9 4 8 年，香农( s h a n n o n ) 在他的开创性论文通信的数学理论中，首次阐明了在 有扰信道中实现可靠通信的方法【2 2 1 ，提出了著名的有扰信道通信编码定理，奠定了 纠错码的基石。自此以后汉明( h a m m i n g ) 、斯列宾( s l e p i a n ) 、普兰奇( p r a n g e ) 等人在 5 0 年代初，根据香农的思想，给出了一系列设计好码和有效译码的方法。以后，纠 错码受到了越来越多的通信和数学工作者，特别是代数学家的重视，使纠错码无论 在理论还是在实际中都得到飞速发展。本章先简要介绍数字通信系统的基本模型， 然后回顾四种典型纠错编码的原理与方法，最后概述了逼近仙农限的两种纠错码。 2 1 数字通信系统概述 信道中传输数字信号的系统，称为数字通信系统。数字通信系统的模型【2 3 】如图 2 1 所示。图中信源编码器的作用是把信源发出的消息如语言、图像、文字等转换为 数字序列，并且为了使传输有效还可以去掉一些与传输信息无关的多余度( 有时为 了保密，信源编码器后还可接上加密器) 。信道编码器的作用是将信源编码器输出的 数字序列人为地按一定的规则加入多余码元，使得在接收端能发现错码或纠正错码， 以提高通信的可靠性。信道译码器的作用是发现或纠正传输过程中引入的差错，解 除信道编码器所加入的多余码元。调制器和解调器只是对用模拟传输方式的数字通 信系统才是必须的，信源译码器的作用是把数字信号还原为模拟信号。 图2 1 数字通信系统模型 4 五邑大学硕士学位论文 2 2 纠错码的分类 纠错编码【2 4 2 7 】是用来改善数字信道通信可靠性的一种信号处理技术，它所以能 够检错和纠错，是因为在信息码元之外加入了多余码元，这种多余的码元不载任何 信息，只是用来校验信息码元在传输中是否出现差错。多余码元的引入，降低了信 道的传输效率。一般地说，多余码元引入越多；纠检错能力越强，但信道的传输效 率下降也越多。所以纠错编码实际上是牺牲了信息传输的有效性来获得传输的可靠 性。 从不同的角度出发，纠错编码可有不同的分类方法： 1 按码的功能分，有检错码和纠错码。 2 按监督码与信息码元之间的关系分，有线性码和非线性码。 3 按照对信息码元处理方法的不同分，分组码、卷积码和量子纠错码。 2 2 1 线性码 线性码是分组码中最重要的一类码，它是讨论各类码的基础。由于线性码具有 便于运算分析的叠加性质，因此在目前可供使用的绝大部分差错控制码均属于线性 码。如完全线性码：h a m m i n g 码和g o l a y 码、m d s 线性码：多项式码和二元 r e e d m u l l e r 码等。它们主要是通过有关码的生成矩阵g 都消息进行编码和校验矩阵 日对其进行译码。 下面首先来阐明线性码以及其生成矩阵和校验矩阵。 定义2 2 1 1 向量空间的片一个上f 。的线性子空间c 作q 元线性码。 取c 的一组f q 基 l ，l ，玖) ， ，f _ ( a j l ，a f 一) ( 1 j 句其中a f f 。 尽力，1 j 。则每个码字可唯一表示成 c = b l v l + + 反 = ( b ，历) g( b ，良f 。)( 2 1 ) 其中g 是f 。上秩为k 的k x n ( k 行刀列) 矩阵 第二章纠错码原理与方法 g 舟髓i i g 叫作线性码c 的一个生成阵。 另一方面，瑶的一个k 维向量子空间c 必是某个齐次方程组 ( 2 - 2 ) “l + 6 1 2 毛+ + 6 l 。矗= 0 ， 6 2 i 而+ 6 2 2 毛+ - - + b 2 一毛2o，(2-3) ： 屯一i 1 五十吃一2 x 2 + + “一i ，。矗= 0 的全部解，其中 而r = ( 6 盯) l ，一七， l j 一( 2 4 ) 是f q 上0 k ) x n ( 一k 行根列) 矩阵，并且秩为理k 。h 叫作线性码c 的一个校验阵。 由定义可知，对每个v e 写， v c 俏7 = 0 ( 长为，l k 的零向量) ， 所以可用h 来检查向量l ，是否为c 中的码字( 日7 1 为矩阵h 的转置矩阵) 。 线性码的纠错译码算法： 设c 是参数 毛明的q 元线性码，= 等 ，并且c 有校验矩阵 h = ( u l ，”，叻， ( 2 - 5 ) 其中嚣；( 1 i 9 ) 均是f q 上长为栉k 的列向量。如果码字c c 在传送时错位个数 ，即收到向量y = c + 6 ，其中w ( z ) ，。则纠错算法如下： ( 1 ) 计算 ，= 协t ，这是f q 上长为拧竞的列向量，叫作的校验向量。 ( 2 ) 如是l ，0 ( 零向量) ，则占= 0 ，y = c ( 无错) 。 ( 3 ) 如果v = = 0 ，则 ，必可表示成留l ，o a j , 以。当中不超过z 个列向量的线性组合： l ，= a f l u f i + + a f f u f f( 1 i x i 2 n - m ， 其纠错能力也随之下降。 了一 即矗 而 五邑大学硕士学位论文 l d p c 码的校验矩阵日可以用二部图来表示，假设二部图g 中有个左节点( 称 为信息节点) 和m 个右节点( 称为校验节点) ，则一个二部图就可以定义了一个长 为，维数至少为- 肘的线性分组码如下： 该码字中的个码字分别表示个信息节点的数值( 0 或1 ) ，则一个码组向量 c = ( c l ，c 2 , c 3 ，厶) 满足这样一个条件：任一校验节点的相邻信息节点的数值和为o ( 如图3 1 所示) 。 基鬈莲 = 警圉上的停止集铡子 图3 2 二部图上的停止集 二部图中的信息节点与校验节点之间的连线称 为边( e d g e ) 。若第，个信息节点与第f 个校验节点 有边相连接，则校验矩阵中的h ( i j ) = i ，否则为0 。 在二部图g 中，存在几个重要的概念，节点的 度、围长、周长、直径、半径、停止集，节点的度 就是与该节点相连的边的数量；围长是在二部图中，最短的环的长度，节点v 的围 长毋定义为以，为节点的环中最短的环长；而二部图中最长的环的长度则称之二部 图g 的周长；若记节点v ；到屹的最短路径为吠，矗v f ) ，在二部图g 的任意两个变量节 点的以，b 1 = ，) 中，我们称m a x ( 硪v b 吁) ) 为二部图g 的直径，而m i n ( 政v 厶哆) ) 为二部图g 的半径；至于停止集，它是一个包含有若干个信息节点的集合，集合中任意一个信 息节点的邻居校验节点的度都大于l ，且集合中任意两个信息节点都有路径相连，如 图3 2 所示为一些停止集的例子。引入二部图及其相关概念，为分析l d p c 码的结 构、深入研究译码方法提供了度量参数，为构造性能优良的校验矩阵的研究提供了 直观方法。 3 2l d p c 码的编码原理 把一个m n 校验矩阵日分成两个子矩阵c l ，c 2 ，即舻【c i ，c 2 】，其中c l 是一 个k 的矩阵( 槲m ) ，c 2 是一个m m 的矩阵，又设生成的码组为c = 【甜，c p 】， 扎为信息位，c d 为校验位，由朋1 = o 有 h c t = c l ，c 2 】【“，c p 】t = c l “t + c 2 c o t = 0 。 ( 3 1 ) 从而有：c p t = c 2 c l 列t = p u t 。 上式中p = c 2 。1 c l ，当且仅当c 2 可逆时，p 存在；若日不满秩，g 不可逆，此 时可删除日矩阵中线性相关的行来得到一个具有更高码率的l d p c 码。 第三章q c l d p c 码的编译算法 由c = u g 及g 日r - o 得到对应系统码的生成矩阵：g = 厶，p 1 】。 上面是l d p c 码的最基本的编码方法，其关键是对特定的h 求得c p t 。但选用 长码时通常校验矩阵日的维数比较大，编码运算中含有大量的乘法运算和加法运算， 同时还要分配大量的存储空间用于存贮数据与变量，这使得l d p c 码的基本编码方 法具有较高的编码复杂度，其复杂度跟分组码长成二次方的关系，。不适用于硬件实 现。为此，人们利用校验矩阵稀疏的特点，提出了行( 列) 压缩的方法，变矩阵相 乘为向量点乘，从而有效地降低了编码的复杂度与存储空间。近年来，不少专家学 者把l d p c 码的编码与构造方法结合起来进行编码。为提高编码效率，n e a l 讨论了 一种利用校验矩阵稀疏的特性来降低复杂度的混合编码方法与矩阵分解的编码方法 【3 们，随后r i c h a r d s o n 研究了一类近似下三角变换的编码方法【3 1 1 ，m a c k a y 和y a n g 也 相继提出了下三角构造和完全下三角构造校验矩阵的编码方法，这些编码方法都大 大降低的编码的复杂度与存储空间，但是当g 比较大时，编复杂度与长度聆的近似 线性关系将被破坏。化相似三角形形式进行编码的方法主要针对随机构造的l d p c 码，为降低编码的复杂度，不少专家也借助了有限几何方法进行编码，如文【3 2 】提 出用有限几何中的点线来构造l d p c 码，并使其编码时间与长度聆成线性的关系。 欧氏几何法与射影几何法就是其中两种有限几何中的l d p c 码的构造与编码方法。 欧氏几何与射影几何构造l d p c 码是以几何代数理论为依据的，其特别是编译码速 度快，但此类方法构造出来的l p d c 码属于循环正则l d p c 码，其性能与相当长度 的l d p c 码的性能还有一定的差距，主要是此类码的最小距离还有待提高。于是后 来，又有人提出了在有限域中构造q c l d p c 码的方法1 3 3 1 ，该类方法不仅利用了有 限几何方法编码的优点而且提高了码字的最小距离，更进一步的增强了纠错能力。 3 3q c l d p c 码的编码算法 在构造l d p c 码校验矩阵时，随机构造方法不利于硬件实现，于是人们想到的 是用几何代数方法来构造l d p c 码的校验矩阵，而基于有限域的循环码的构造是目 前线性分组码研究中最为成熟的一类码，目前大多数实用的纠错码都属于循环码的 范畴。而即将介绍的q c l d p c 码就是在循环码基础上进行构造的【3 4 1 。 一个常见的【七 】q c 码的生成矩阵如下所示： 1 6 五邑大学硕士学位论文 岛铂踟 鼬岛鼬踟 ，1 l u = i 鼬铂蹁鼬岛 岛岛鼬岛 ( 3 - 2 ) 很明显，该码完全由生成矩阵g 的第- - ? g o , g , , 9 2 g n 1 】确定，其循环移位的 步长为= 2 ，第一行也称为分组码c 的生成器。在代数学中，循环行列式i n n 矩阵与 多项式商环f 2 x l ( x “+ 1 ) 在r 上同构，即可以把系数矢量【勘，g i ，匏，勘i 】映射到多项 式彳o ) = g o + g l x + 9 2 x 2 - i - g n 1 ，。( 3 6 ) 式中，生成矩阵g 同时又可以写成为两个循环 方阵的形式为： g = i 季：三蓍ii ：主詈 ( 3 - 3 ) 即g = g 1 ( x ) i g 2 ( x ) ，g l o ) ，g 2 ( x ) 为商环f 2 x ( x o + 1 ) 上的循环多项式。因此，准 循环矩阵可以用多个循环矩阵来定义。( 3 3 ) 式所示的准循环矩阵是两个循环矩阵水 平级联构成，还可由同时再添加多个循环矩阵水平或垂直级联构成的，下面介绍由 多个重为2 的循环矩阵构成的准循环码校验矩阵日的构造。 3 3 1q c l d p c 对偶码 由前面分析可知，l d p c 码的校验矩阵可以由1 个p x p 循环子矩阵水平级联而 成。若要构造一个码率为，的( 巩以) 正则l d p c 校验矩阵，只要知道任一子循环矩 阵的列重巩就可以确定以= 州( 1 ，) 。而用多项式表示的校验矩阵日可以写成多个子 矩阵级联形式：胙【日1 0 ) ，飓( x ) ，飓o ) 胁o ) 】。显然，日中的行数与循环子矩阵 的行数是一致的。则若生成矩阵g 由j 个生成器构成，则对应的【坍刀】校验矩阵h 中，n = l p ，聊= ( ，- s ) p 印，所以( ，s ) 印，1 = 1 + s ，由此得码率，= ( 门胁) 励= s ，= j ( 1 + s ) 。例如 ( s ，) = ( 1 ，2 ) ，( 2 ，3 ) ，( 3 ，4 ) 。这样构造出来的码c 也可以简单地用由一个生 1 7 第三章q c l d p c 码的编译算法 成器确定的并与之正交的对偶码c 上来定义，因此c 与c 上互为校验矩阵与生成矩阵， 它们又称为对偶码。 给定一个校验矩阵日，我们还要求其生成矩阵g ，使g 日1 = o 。等同于高斯消元 法，我们把原来的校验矩阵日的多项式除以胁0 ) ，得到一个用多项式定义的新的校 验矩阵为： 。 h = 盯i ( x ) 【h 1 0 ) ，飓o ) ，飓( x ) h i ( x ) 】 = 【p 1 0 ) ，岛o ) 只 ) ，1 】( 3 4 ) 式中尸，o ) = - q l ( x ) ( x ) 。于是我们得到了其系统形式的生成矩阵为： g = 10 01 ： 0 ( 3 - 5 ) g 存在的必要条件是胁o ) 可逆，凰( x ) 可逆的充要条件是t t t ( x ) 与x p + l 互质。即 g c d ( h i ( x ) ，+ 1 ) = l ，蜀o ) 与，+ 1 的最大公约数为l 。 h = a 环长为4 o1 1oo 1 0 固0