（应用数学专业论文）准循环低密度校验码的理论研究及构造.pdf

棼涛；准循环低密凌校验玛静壤论礴究及梅造 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标翡弓| 用的内容外，本论文不包含其德令入或集体已经发表 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。 本声明靛法律结果由本人承担。 学位论文作者签名：孑i 谤 签字日期：? 硝年么月，2 日 学位论文版权使用授权书 本入完全了解学校有关保留、使用学位论文的规定，帮：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。 本人授权扬蹦大学霹以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学 技术信息研究所将本学位论文收录到中国学位论文全文数据库，并透过网络向 社会公众提供信息服务。 学位论文作者签名：石l 麝导师签名：硝艺 签字目瓣：夕弼年多月口目 签字日期：硝年6 月渺 圈 孙涛：准循环低密度校验码的理论研究及构造 中文摘要 低密度校验( l o w d e n s 时p a r i t y c h e c k ，l d p c ) 码是目前信息领域和通信界最 热门的研究方向之一。它是一种基于图和迭代译码，性能逼近s h 锄o n 限，而且 易于实现的信道编码方案。其性能甚至可以超过t u r b o 码。本文对准循环低密度校 验码的理论和构造进行了研究，创新性地提出了利用组合设计中的差集类来构造 准循环低密度校验( q u a s i - c y c l i cl d p c ) 码。这种方法构造的q c l d p c 码，最小 环长至少为6 ，码率的选择具有很大的灵活性。由于其特殊的准循环结构，这种码 与用随机方法构造的码相比较具有很大优越性：一是可以用简单线性移位寄存器 实现编码；二是只需存储校验矩阵的指数矩阵，可节约很多存储空间，易于硬件 实现。计算机仿真结果表明在加性高斯白噪声信道中b p s k 调制下用和积迭代译 码性能良好。本文主要由以下几个部分组成： 1 、介绍l d p c 码的定义及其独特优点、l d p c 码校验矩阵的t a i l l l e r 图表示和 最小环长、准循环l d p c 码的研究进展。 2 、介绍完备循环差集，循环差集以及不相交差集的定义及构造方法。 3 、研究准循环l d p c 码的结构，介绍基于循环置换矩阵的扩张构造q c l d p c 码的代数方法。 4 、利用计算机仿真基于差集类构造的q c l d p c 码的误比特率性能。 关键词：低密度校验码，完备循环差集，循环差集类，不相交差集，准循环低 密度校验码，t a n n e r 图，最小环长，和积迭代译码 孙涛：准循环低密度校验码的理论研究及构造 a b s t r a c t 2 一 l o w d e n s i t yp 撕够一c h e c kc o d e sh a v eb e e no n eo fm em 匈o rr e s e a r c ht o p i c si nt h e i n f b m a r t i o na n dc o i n n l u i l i c a t i o nf i e l d ni sac l a s so f c h a n n e lc o d e s b a s e do ng r a p h sa n d c a i la c l l i e v eg o o dp e r ：f o m a i l c ec l o s et ot h es h 锄o n - l i m i t 、) j r h e ni t e r a t i v e l yd e c o d e d ， w h i c hp e 怕mb e t t e rt h a nm et u r b oc o d e s i nt h i sd i s s e 似i o n ，t h et h e o d e s i g no f q c - l d p cc o d e si ss t u d i e da n dan e wm e m o do fc o n s t i u c t i n gq u a s i - c y c l i cl d p cc o d e s b a s e do nc i r c u l a n tp e r i l l u t a t i o nm a t r i c e sf r o mt h ed i 虢r e n c ef 锄i l yi sp r o p o s e d t h e c o n s t m c t e dc o d e sa r ew i t l ln os h o r tc y c l eo fl e n 舀h4o ri no m e rw o r d ，t h e i rg i r t hi sa t l e a s t6 ；w i t hl a r g en e x i b i l i t yi nc h o o s eo fc o d er a t e b e c a u s eo ft h es p e c i a lq u a s i c y c l i c 蛐n j c t u r e ，t h i sa 1 1 0 w ss i m p l ee n c o d i n ga n ds m a l ls i z eo fr e q u i r e dm e m o r y ，w m l e m a i m a i l l i n gg o o dp e r f o m a n c e s i m u l a t i o n ss h o wt h a tt h ec o n s t r u c t e dq c - l d p cc o d e s w i t hs 啪- p r o d u c ti t e r a t i v ed e c o d i n gp e 墒n i lw e l lu n d e rb p s km o d u l a t i o no v e ra i l a d d i t i v ew h i t eg a u s s i a nn o i s e ( a w g n ) c h 籼e 1 t h em a i n 、o r k sa r ea u sf o l l o w s ： 1 i n 们d u c i n gt h ed e f i l l i t i o na 1 1 du i l i q u ea d v a n t a g e so fl d p cc o d e s 、 t a n i l e rg r a p h r e p r e s e n t a t i o na n dg i r t ho ft h ep 碰t ) ，- c h e c km a t r i x 、t h ep r e s e n tr e s e a r c hs i t u a t i o no f q c - l d p cc o d e s 2 i n t r o d u c i n gt h ed e f i i l i t i o n sa sw e l la st 1 1 es t m c t u r em e t h o do ft h ep e r f e c tc y c l i c d i 虢r e n c es e t s ，c y c l i cd i 位r e n c es e t sa j l dd i s j o i n td i 腑r e n c es e t s 3 t h es t m c t u r eo fq c l d p cc o d e sa n dt h es t r u c t u r ec o n s t m c t i o n so fp 撕t y - c h e c k m a _ t r i xb a s e do nc i r c l u a n tp e m u t a t i o nm a t r i c e sa r er e s e a r c h e d 4 t h eb i t - e r r o rr a t ep e r f o m a n c eo ft h ec o n s t m c t e dq c - l d p cc o d e si sd e m o n s t r a t e d b yc o m p u t e rs i m u l a t i o n s k e y w o r d s ：l o w - d e n s i 够p a r i 锣一c h e c kc o d e s ， p e r f e c tc y c l i cd i f 托r e n c es e t s ， c y c l i cd i f f e r e n c es e t s ，d i s j o i n td i f f e r e n c es e t s ，q u a s i c y c h cl d p cc o d e s ，t a n n e r g r a p h ，g i n h ，s u m - p r o d u c t i t e r a t i v ed e c o d i n g 孙涛：准循环低密度校验弼的理论研究及构造 o引言 移动通信技术的发展对于通信的质量和速率的要求越来越高。纠错编码技术是 移动通信、卫星通信、光纤通信和磁盘存储等数字信息系统中的关键技术之一， 以美国a t & t ( 贝尔) 、l u c e n t ( 朗讯) 、q u a l c o m ( 高通) 等大的电信公司为代表 的一批公司及国外一批大学的研究机构，都相继投入了大量的入力物力在诸如 h b o 码技术、l d p c 码技术、o f d m 技术、m l m o ( 多输入多输出技术) 、s p a c e t i m e c o d i n g ( 时空编码技术) 等第四代移动通信关键技术的研发上，目标是通过采用更先 进的技术，实现第四代宽带、高速、高可靠的移动通信，以满足市场的需求。 l d p c 码是一种近年来引起国内外学者注意的具有极强纠错能力的好码，它可 以在加性高斯白噪声( a w g n ) 信道中达到香农限，其优良的译码性能吸引了整 个编码界的关注。由于l d p c 码可以采用和积迭代译码算法，易于未来高速并行 处理；l d p c 码在高码率情况下仍其有相当高的纠错能力，具备多业务、高速数据 传输等鲜明特色，这使其在光纤通信、深空通信和磁记录信道等方面具有广泛的 应用翦景。美国国家航空和宇宙航行局已经将己d p c 码的编译码方案应用到了深空 数据传输中，实现了高精度的数据传输。 1低密度校验码的研究进展 1 1l d p c 码的定义及独特优点 l d p c 码是由美国麻省理工学院的r g g a l l a g e r 于1 9 6 2 年发明的，p c 码可 以由它的校验矩阵来定义，它的校验矩阵是稀疏矩阵，也就是说矩阵中除了很少 部分元素非零外，其他大部分的元素都怒零。 定义1 1 ( g a l l a g e r ，1 9 6 2 年) n 1 ：一个l d p c 码被定义为校验矩阵日的零 空间，且h 具有下列结构特征： ( 1 ) 每一行有意个“l ”； ( 2 ) 每一列有，个“1 ； ( 3 ) 往意两列( 行) 具有共同“王的位置个数不大于圭； 孙涛：准循环低密度校验码的理论研究及构造 4 一 ( 4 )七和，与日的列数、行数相比是很小的。 l d p c 码之所以引起人们关注，主要归结于自身的许多独特优点： ( 1 )当码长趋近于很大的时候，l d p c 码的最小码距和码长的比趋于一个常数而 不是零。 ( 2 ) m a c k a y 和n e a l 的研究表明，采用优化设计的l d p c 长码可以达到n 曲。 码的性能。最近的研究表明在非规则图上构造的l d p c 长码的性能已非常 地接近香农限 2 ，这也是引起理论界极大关注的主要原因。 ( 3 ) l d p c 码的译码算法是一种基于稀疏矩阵的并行迭代译码算法，并且由于结 构并行的特点，在硬件实现上比较容易。 ( 4 ) l d p c 码的码率可以任意构造，也可以打孔得到，有很大的灵活性。 1 2 校验矩阵的结构特征 1 2 1t a n n e r 图表示 校验矩阵日可以对应到称为t a n n e r 图的双向二部图。如图1 2 1 所示，上面 的节点是变量节点可以认为是一个码字中的一个比特或者是校验矩阵中的一列； 下边的节点是校验节点，每个节点表示一个校验方程或者是校验矩阵中的一行。 当码字中某一比特包含在某一校验方程中即校验矩阵相应的位为l 时，图1 2 1 中的上下节点之间存在连线，对于每个节点与之相连的边数称为这个节点的度数。 l d p c 码有两类，一类是正则l d p c 码，其校验矩阵中具有相同的行重和列重；另 一类是非正则l d p c 码，其校验矩阵中的行重和列重不相同。正则码与非正则码同 样可以通过上下节点度数是否分别相同来定义。 h 4 。5 = 11 01 0l lo 图1 2 1 校验矩阵的t a n n e r 图表示 0 1 l 1 o 0 1 l 0 l 0 1 孙涛：准循环低密度校验码的理论研究及构造 1 2 2 环及最小环长 一个码的好坏完全由它的校验矩阵来确定，也就是说校验矩阵的结构对于码 的性能有着决定性的作用。l d p c 码是用一个稀疏校验矩阵来定义的，要设计一个 l d p c 码，最直接有效的方法就是按照指定标准构造一个低密度校验矩阵日。 一个“环”被定义为校验矩阵对应的t a n n e r 图中由一个顶点出发，最后又回 到同一个顶点的一些“边”组成的回路。在环中同层节点不允许互连，而且除了 起点和终点，中间顶点出现的次数只有一次。 环中边的个数被称为环的“长度”。一个t a n n e r 图中最小的环长被称为“g i n h ，。 对线性分组码而言，协m e r 图中不存在长度为2 或者奇数的环，所以t a n n e r 图的 最小环长至少是4 ，即g i m l 4 。如图1 2 2 ( 1 ) 所示： 巧一弓一哆一白号巧 构成一个长度为4 的环。它可以表示为两个码字比特屹，v 5 同时被校验节点巳，q 进行校验。映射回日矩阵即是第巳，q 行上的第屹，个码字比特位都为“l ”， 此时这两行“1 的重叠度五= 2 ； 如图1 2 2 ( 2 ) 所示： m q 专心jc 3 一吩jq h 构成一个长度为6 的环。 吩 v lv 2吃 图1 2 2 长度为4 和6 的环 q ( 2 ) 孙涛：准循环低密度校验码的理论研究及构造 6 1 2 3l d p c 码代数构造方法的优点 l d p c 码越来越多地受到人们的重视，各种好的代数构造方法不断推出，主要 是为了实现以下几个目标： ( 1 ) 优化码结构； ( 2 ) 增大二部图中的最小环长； ( 3 ) 减少编码复杂度。 代数方法构造的l d p c 码和随机构造的l d p c 码相比较，尽管性能上有一定 的损失，但是以下几个方面的优点使得这一类l d p c 码受到额外的关注： ( 1 ) 具有严谨的数学结构，构造和分析更加精确，甚至最小汉明距离的准确计 算都是可能的； ( 2 )和随机构造的l d p c 码相比，具有更低的错误平层( e 1 1 r o rf l o o r ) ，它可以 应用于有线通信、深空通信以及磁盘存储工业等对误码率要求更加苛刻的 场合； ( 3 ) 可以具有循环( c y c l i c ) 或者准循环( q u a s i c y c l i c ) 的结构，可以很大程度的 降低编码复杂度，也为译码提供了更加方便的选择。 1 3 准循环l d p c 码的研究现状 早在1 9 6 2 年，l d p c 码便由g a l l a g e r 提出，但之后3 0 余年几乎被遗忘。直到1 9 9 5 年，m a c k a y 和n e a l 等人的重新发现才引起了l d p c 码的新一轮研究热潮。l d p c 码 的优势来源于它的校验矩阵的稀疏性，也就是校验矩阵中非零元素占校验矩阵中 元素总数目的比例很小。但是，这些码的校验矩阵还主要是由计算机随机生成的 2 ，依靠计算机随机生成的校验矩阵有两个主要缺点：一是难以避免短长度环的 存在；二是接收端对随机生成的矩阵需要很大的存储空间。因而，如何构造具有 良好稀疏性的校验矩阵成为l d p c 码的一个研究热点。准循环l d p c 码，由于其特 殊的结构，可以用简单线性移位寄存器在线性复杂度的条件下完成编码，并且与 用随机搜索方法构造的l d p c 码相比，可以节约很多存储空间，易于硬件实现。目 前在准循环l d p c 码的构造方面，y uk o u 和l i ns h u 等人 3 ，4 对基于有限仿射几 孙涛：准循环低密度校验码的理论研究及构造 7 一 何和射影几何的l d p c 码进行了研究，b v 如i c 和b h o n a r y ，a m o i n i a i l 等人 5 ，6 ， 7 则利用组合数学中的均衡不完全区组设计，拉丁方阵等构造出了具有准循环结 构的l d p c 码；另一种主要的代数构造方法则是利用循环置换矩阵构造准循环l d p c 码，它首先由j l f a n 8 提出，后来r m 吼m e r 9 ，1 0 和m p c f o s s o r i e r 等人 1 1 ， 1 2 对其构造方法进行了研究并在此基础上各自提出了新的构造方法。基于循环置 换矩阵的构造方法，可以得到各种码长和码率的l d p c 码，并且在码长较短时其译 码性能优于随机构造的码，可适应不同领域的需求。 2 差集类 2 1 差集类的定义n 3 1 设马= 6 1 ，岛 2 ，6 ，。) ，o ，一1 ，是以正整数v 为模的f 个c 一元素子集。 定义2 1 1 ( 不相交差集，d d s ) ：如果对任意口o ( m o d v ) ，至多存在1 个有序对 ( 岛 f ，2 j 7 ，) ，使得口三6 f ，一6 f ，( r n o d v ) ，0 ，f 一1 ，1 f ，c ，贝0 称为o ，c ，1 ，) 一d d s 。 局= 6 f ，l ，6 2 ，4 ，。) ，o ，f 一1 ，称为( ，c ，v ) 一d d s 的基区组，显然各参数满足 关系式v 纪 一1 ) + 1 。 定义2 1 2 ( 循环差集，c d s ) ：如果对任意口0 ( m o d v ) ，恰好有允个有序对 ( 岛 ，岛，) ，使得口兰6 ，一岛，j ( m o d l ，) ，o ，r 一1 ，l f ，c ，则称为( v ，c ，z ) 循环差 集，记为f d ( v ，c ，兄) 。 局= 6 l ，6 ， 2 ，4 ，。) ，0 ，卜l ，称为f d ( v ，c ，兄) 的基区组，显然各参数满足 关系式兄( v 一1 ) = 纪 一1 ) 。因此r d ( 1 ，c ，1 ) 是( f ，c ，v ) 一d d s 的一种特殊情形。 定义2 1 3 ( 完备循环差集，p e r f e c tc d s ) ：当t = 1 ，九= 1 时，则称循环差集 l d ( v ，c ，1 ) 为完备循环差集( p e r f e c tc d s ) ，此时v 称为完备循环差集的模，c 称 孙涛：准循环低密度校验码的理论研究及构造 8 定义2 1 4 ( 差集表) ：设马= 6 ， l ，岛 2 ，一白，。 为( f ，c ，v ) 一d d s 基区组中的一个元 素，则它对应的差集表d 7 ，定义为一个c c 阵列d 7 = 磋l ，= 6 ，一6 f ，( m o d l ，) ) ， 由不相交差集的定义，基区组马= 岛 l ，岛 2 ，4 ，。 ，o ，卜1 ，对应的差集表 由差集表的定义，我们可以得到( f ，c ，v ) 一d d s 的基区组马= 岛 1 ，6 f 2 ，4 ，。) ， 性质2 1 1 ：马+ q 三 6 ，l + 口，岛，2 + q ，岛。+ q ) ( m o d v ) ，q 磊，o ，r 一1 为 性质2 1 2 ：骂口兰 ，o f 七一1 ，称f 为集合s 的 下标，用之表示包含口幽一l 的集合下标，1 e 刀。若在模，2 运算下，乙互不相 同，则集合品，瓯，& h ) 。构成f d ( v ，c ，1 ) 循环差集的f 个基区组。 例2 2 1 ：我们用方法1 构造一个3 一d ( 6 l ，5 ，1 ) 循环差集。 构造：令刀= 2 ，= 3 ，c = 2 刀+ 1 = 5 ，七= f ( c 1 ) = 1 2 ，v = f c ( c 一1 ) + 1 = 6 1 。 孙涛：准循环低密度校验码的理论研究及构造 经验证口= 2 为舒( 6 1 ) 的本原元，由s = 口h 弦io 歹c 一1 ) ，我们计算得到下面的 集合： & = l ，9 ，2 0 ，3 4 ，5 8 ) ，s = 2 ，7 ，1 8 ，4 0 ，5 5 ) ，疋= 4 ，1 4 ，1 9 ，3 6 ，4 9 ，s = 8 ，l l ，2 8 ，3 7 ，3 8 ) ， 墨= 1 3 ，1 5 ，1 6 ，2 2 ，5 6 ) ，墨= 2 6 ，3 0 ，3 2 ，4 4 ，5 1 ) ，瓯= 3 ，2 3 ，4 1 ，5 2 ，6 0 ) ，s = 6 ，2 1 ，4 3 ，4 6 ，5 9 ) ， = 1 2 ，2 5 ，3 1 ，4 2 ，5 7 ) ，岛= 1 ，2 3 ，2 4 ，5 0 ，5 3 ) ，s o = 2 ，3 9 ，4 5 ，4 6 ，4 8 ) ，s l = 4 ，1 7 ，2 9 ，3 1 ，3 5 ) ； 显然s 包含8 ，是包含1 9 ；即= 3 ，f 2 = 2 ，因此在模2 运算下互不相同，则集合 氐= l ，9 ，2 0 ，3 4 ，5 8 ) ，是= 4 ，1 4 ，1 9 ，3 6 ，4 9 ) ，墨= 1 3 ，1 5 ，1 6 ，2 2 ，5 6 ，构成3 一d ( 6 1 ，5 ，1 ) 循环差集的基区组，可以看到z 6 。中每个非零元素在模6 l 的差集表中恰好出现一 次。 o 81 9 3 3 5 7 5 3o1 12 54 9 4 25 0 o1 43 8 2 83 64 7o2 4 41 22 3 3 7 o ( m o d 6 1 ) ， 01 0 1 53 2 4 5 5 1o52 2 3 5 4 65 6 o1 7 2 93 94 40 1 6 2 63 14 8 3 0 i ( m o d 6 1 ) ， 1 3 o o 2394 3 5 9 0174 1 5 8 6 0o6 4 0 5 25 45 5 0 3 4 1 82 02 12 7 o ( m o d 6 1 ) 。 构造方法2 ：令c = 2 行，尼= 纪，v = 纪( c 一1 ) + 1 ，且v 为素数。令夕为舒( v ) 的 本原元，用z ，o f 七一1 ，表示集合z = 件业lo c 一2 u o ) ，用f o ，一，分 别表示含有1 ，一1 ，”1 弦一1 的集合的下标。若在模，z 运算下，乇，一。互不相同， 则集合磊，乙，夏h ) 。构成f d ( v ，c ，1 ) 循环差集的f 个基区组。 例2 2 2 ：我们用方法2 构造1 一( 1 3 ，4 ，1 ) 循环差集的基区组。 构造：令刀= 2 ，f = 1 ，c = 2 刀= 4 ，七= 纪= 4 ，v = 纪( c 一1 ) + 1 = 1 3 。经验证= 7 为卯( 1 3 ) 的本原元，由z = 件肚lo 歹c 一2 ) u o ) ，计算得到下面的集合： 瓦= 0 ，1 ，3 ，9 ) ，墨= o ，7 ，8 ，1 1 ，t = 0 ，4 ，1 0 ，1 2 ) ，五= o ，2 ，5 ，6 ) ； 孙涛：准循环低密度校验码的理论研究及构造 显然瓦包含l ，互包含8 ，所以f 0 = o ，= 1 ，因此在模2 运算下互不相同，则集合 瓦= 0 ，1 ，3 ，9 ) 构成l 一( 1 3 ，4 ，1 ) 循环差集的基区组，可以看到z l ，中每个非零元素在模 1 3 的差集表中恰好出现一次。 2 2 3 完备循环差集的构造方法 目前利用纯数学的方法只能确定很少一部分参数v 的完备循环差集，在大多数 情况下完备循环差集的构造主要是借助计算机搜索的方法来实现 1 3 ，在附录中 我们给出了存在的一些完备循环差集1 一d ( v ，c ，1 ) ，3 c 3 0 。 2 3 不相交差集的构造 2 3 1d d s 的递归构造 令马，岛，忍为( f ，c ，v ) 一d d s 的，个基区组。若( 聊，( c 1 ) ! ) = 1 ，则对于每个 哆= o ，屯1 ，p 1 ) 生成聊个差集基区组 o ，屯，。+ f v ，屯，2 + 2 f v ，嘭p 。+ ( c 一1 ) 如) ， o f m ，1 f 。若存在( 口，c ，m ) 一d d s ，则对于其每一个基区组t = o ，乞一。) ， 1 r ，生成单个差集基区组 0 ，嵋，v 乞一1 ) 。这些新生成的基区组构成 ( 聊f + 口，c ，加) 一d d s 的基区组，其中所有运算为模聊v 运算。 例2 3 1 ：我们用d d s 的递归方法构造( 8 ，3 ，6 3 ) 一d d s 。 构造：昼= 0 ，1 ，4 ) 为( 1 ，3 ，9 ) 一d d s 的一个基区组，由( 7 ，21 ) = 1 ，我们计算得到 下面的集合： 置= o ，1 ，4 ) ，段= o ，l o ，2 2 ) ，马= o ，1 9 ，4 0 ) ，蜀= o ，2 8 ，5 8 ) ，b = o ，3 7 ，1 3 ) ， o 、， 3t ld0m ，i 、 9 8 6 o 3 2 0 7 1 0 5 0 2 o 4 孙涛：准循环低密度校验码的理论研究及构造 成= o ，4 6 ，3 1 ) ，马= o ，5 5 ，4 9 ) ； d l = 0 ，1 ，3 ) 为( 1 ，3 ，7 ) 一d d s 的基区组，计算得到一个区组最= 0 ，9 ，2 7 ) ，因此蜀， 岛，最为新生成的( 8 ，3 ，6 3 ) 一d d s 的基区组。 2 3 2 一类( 1 ，g ，9 2 1 ) 一d d s 的构造 利用下面提到的构造方法，可以得到周期v = 9 2 1 ，大小c = g 的不相交循环 差集，其中g 为素数。考虑以0 ，1 开始的序列，其中的每个元素都是它前面第一个 元素与两倍的前面第二个元素的差。 o11 1 3 157 3 1 7 1l2 34 5 1 9 1 8 99 32 7 18 5 4 5 7 6 2 72 8 71 5 4 19 6 7 2 l1 5 4 0 4 9 对该序列取模5 ，得到周期为2 4 的下列序列，给每个1 的位置作如下标志，并从o 开始计数： 序列：01 14 24 02 2343o4 413103 32l 2 ( o1 标志： 撑撑群拌拌 计数：0l2345 678 91 011 1 21 31 41 51 61 71 81 92 02 12 22 3 ( o1 我们已经构造了一个模9 2 一l = 2 4 的不相交循环差集 1 ，2 ，1 5 ，1 7 ，2 2 ) ( m o d 2 4 ) ， 差集表如下： 011 41 62 1 1o1 3 1 52 0 1 4 1 3027 1 6 1 5 - 2o 5 2 1 2 0 75o 011 4 1 62 1 2 3 01 3 1 52 0 ( m o d 2 4 ) jl l o 1 lo 2 7 89 2 2 o5 34 1 7 1 9 0 这个仅符合模g 为素数的情况，且g 为其它素数时，需要的序列也不相同。我们 用来产生不相交差集的序列由有序二元组( 彳，b ) 来决定，该二元组亦称为次数为2 的线性递归。 因为序列中的每一个数总等于彳倍的它前面第一个数、b 倍的前面第二个数， 孙涛：准循环低密度校验码的理论研究及构造 两者之和，并且序列总以0 ，1 开头。上面的例子就是彳= 1 ，b = 一2 模为5 的情况。下 面再举例一些( 么，b ) 取值不同的情况下所得到的序列： ( 彳，b ) is e q u e n c e ( 1 ，2 ) 011351 12 14 38 51 7 1 ( 2 ，1 )i o 1251 22 97 01 6 94 0 89 8 5 ( - 2 ，1 ) 1 0 1- 25 - 1 22 97 01 6 9- 4 0 89 8 5 ( 2 ，一3 ) 1 0 1 21 - 4 - 1 1 1 01 35 67 3 对上面的序列( 彳，b ) = ( 2 ，一3 ) 时取模7 后可得到周期为4 8 的不相交循环差集 1 ，3 ，2 2 ，3 1 ，3 4 ，4 4 ，4 5 ) ( m o d 4 8 ) ，注意序列取的模g 和不相交循环差集的模( 9 2 一1 ) 是 不一样的。一般情况下，对于任意素数g 都可以找到( 么，b ) 序列使得第二个o 发生 在位置g + 1 处。当我们对这样的序列取模g 时总能产生模为9 2 1 大小为g 的不相 交循环差集。对于任意素数g 存在许多( 彳，b ) 序列，我们可以采用下面的规则进行 计算机搜索： ( 1 ) 改变彳，b 的值使得到的序列周期为v = 9 2 1 ，g 为素数，让彳，b 在1 ，g 一1 范围内变化。 ( 2 ) 如果存在一个数z 满足z 2 = 止+ b ( i n o d g ) ，那么这样的( 彳，b ) 序列不是我们 所需要的。 在参考文献 1 4 ，何善宝等人介绍了一种与上面方法类似的由三元组( 彳，b ，c ) 决定的序列，序列中的每一个数总等于彳倍的它前面第一个数、b 倍的前面第二 个数和c 倍前面第三个数，三者之和，并且序列总以0 ，o ，1 开始。对于任意素数g 都 可以找到( 么，b ，c ) 序列使得第二对连o 发生在位置9 2 + g + 1 处。当我们对这样的序 列取模g 时总能产生模为9 2 + g + l ，大小为g + 1 的完备循环差集。 孙涛：准循环低密度校验码的理论研究及构造 1 4 3 准循环低密度校验码 3 1 准循环低密度校验码的基本概念 准循环低密度校验码与用随机方法构造的码相比具有很大优越性：一是可用 简单线性移位寄存器完成编码；二是只需存储校验矩阵的指数矩阵，可节约很多 存储空间。我们将要构造的准循环l d p c 码的校验矩阵h 是由循环置换矩阵尸扩张 构造的，令c 为一长度为础的q c l d p c 码，且它的校验矩阵何具有下面的形式 h = p p 嘞l 尸唧h 尸嘞1 ) 尸口1 0p 口1 l p 口1 神p q h ) 尸q 川) 。尸叼一l 尸q 川x h 尸町一l 川) 尸= o1oo o o1o o o 0l 1o o0 o ，1 ，p 一1 ) ，o i j 一1 ，o 歹l 一1 。 尸为p p 阶循环置换矩阵 叫：) 篇善却 为了叙述方便，我们引入下面一些记号： ( 1 ) 指数矩阵 e ( 日) = ol 口o ( l 一2 )( 一1 ) q oq 1 q ( l 一2 )q ( l 1 ) q j 1 ) oq j 1 ) 1 q j 一1 x l 一2 ) 口( ，一1 x l 一1 ) ( 3 1 1 ) 为( 3 1 1 ) 式中给出的校验矩阵h 对应的指数矩阵。 ( 2 ) 循环置换矩阵 尸7 = p p 7 ，l f p l 为( 3 1 1 ) 式中f 个循环置换矩阵尸相乘后得到的矩阵，其中p o 为p p 阶单位矩 阵。 孙涛：准循环低密度校验码的理论研究及构造 1 5 ( 3 ) 矩阵的复合 ( 3 1 1 ) 中的校验矩阵日表示为： 日= e ( 日) o 尸 下面是本文将要用到的几个定理： 定理3 1 1 n 1 ：校验矩阵h 对应的t a n n e r 图中存在长度为4 的环当且仅当在 指数矩阵e ( ) 中存在至少一个子矩阵 ：降 l 气气止j 满足气 一气止+ 口2 止一 三0 ( m o d p ) 即 ( 气 一口f 2 ) 三( 气止一止) ( m o d p ) ，f 1 f 2 ，五左 定理3 1 2 n ：由循环置换矩阵尸扩张构造的( ，三) 一正则准循环l d p c 码的最 小环长大于等于6 的一个必要条件是循环置换矩阵的阶数p 三，上为奇数； p 三+ 1 ，三为偶数。最小环长大于等于8 的一个必要条件是循环置换矩阵的阶数 p ( ，一1 ) ( 三一1 ) + 1 ，且气 口2 止，0 之，一1 ，o 石 ，2 。 e = z l如z 3 屯 屯 z 1 2 2 屯一l l l j + 21 1 一j + 3l l j + 4 “3 l j + 、 引理3 2 2 1 ：( ，三) 一q c l d p c 码，令= 6 7 口7 ，o 6 ( 一1 ) “ ( 。0 d 。) = 6 ( 一1 ) f + 止( 。o d 。) 1 9 j ( 一1 ) f + _ = ( 一1 ) ，+ 五= ( i i 】【o d c ) j ( 一1 ) ( f 一，) + 一左= o ( 埘【o d c ) 吃 三气止( m o dp ) = 6 ( ，：一1 ) ，+ ( 。0 d 。) = 反j 2 一1 ) ，+ 如( 。o d 。) = ，( f 2 1 ) f + 工= ( f 2 1 ) ，+ 以= ( m o d c ) ( 之一1 ) ( f 一，) + 一五= o ( m o d c ) j ( f l 一1 ) ( f 一，) + 五一左= ( 之一1 ) ( f 一，) + 一五= o ( n l o d c ) j ( f 1 1 ) ( f 一，) = ( f 2 一1 ) ( f 一，) = o ( m o d c ) j ( f 2 一f 1 ) ( f 一，) = o ( m o d c ) 又因为1 f 2 c ，1 f ，c 一1 ，c 为素数，( 之一f 1 ) ( f 一，) = 0 ( m o d c ) 不成立， 这与所设矛盾，故g 4 。 ( 2 ) g ( c 1 ) ( c 2 一c 1 ) ，而由上面的构造只需 p = v = c 2 一c + l ( c 一1 ) ( c 2 一c 一1 ) ，因此g ，o ，一1 ； ( 2 ) 构造指数矩阵e = 【巨易巨】； 棼涛：礁獯强低密度校验褥麓壤论臻究及构造 局= 骂。局：局。一， = e i i 。 岛，l 参，：。也# 一，岛，。 岛，：岛3 岛，。岛。l 岛，。磊，1 。磊，卜：岛，。一， 岛，岛，：岛# 一，岛，c 魏，f + l 岛”2 岛f - l岛，f 岛，。h 岛。甜2 r 磊，。一捌魏，。一， 岛，t 魏，：磊，。一t 岛，。 岛，。岛1 4 ，c _ z6 ，。一。 岛，t 岛4 ，。一3 岛，p 2 岛，：绣一岛，。岛。l ，l 篷f c l ，为c c 阶拉丁方阵，它的第l 行为 岛 l ，岛，2 ，岛，。 依次排列，第2 行是第1 行循环左移f 位后所得，下面的各行由其 上面一行循环左移f 位后得到。显然指数矩阵e 为c r ( c 2 一c ) 阶矩阵。 ( 3 ) 矩阵的复合 日= e 。p 一【簋。p 易。p e 。p 】 得到p c ( # 2 一c ) 除校验矩阵拦。 例3 2 2 ：利用例2 1 1 给出的循环差集2 一d ( 1 3 ，3 ，1 ) 的基区组来构造一个 3 p 1 2 p 阶校验矩阵科。 尸op 1j p 4p op 2p 7尸op 2p 7 户4p o 夕尹2 尹7p 。尹7 夕。尹2 p 1 尸4p o 尸7 尸op 2 尸2p 7p o 利用f p ( v ，e ，1 ) 循环差集的基区组，构造的q c l d p c 码具有下面的性质： 性质3 2 4 ：构造的( 工d = ( c ，纪2 一纪 一正则准循环l d p c 码的最小环长g = 6 。 由f d ( v ，c ，1 ) 构造的指数矩阵e 的每一个子矩阵局，1 z ，不存在长度为4 # 2 魏所缸 绣勃岛所 、j 3idom l 1， 7 2 o 2 o 7 e 7 2 7 0 2 2 7 o 0 2 7 4 l o l 0 4 o 4 l 4 o l l 4 o 0 1 4 ，。，。，。，。l | | e m 秘p 胁趣耻 p 尹p 。，。，。l = 嚣 孙涛：准循环低密度校验码的理论研究及构造 的块环且任意两行之间的差在模p 运算下对应到差集表d 7 中的非零元素，g 4 。 又由定理3 1 2 知，p = v = 纪2 一纪+ 1 2 1 ； ( 3 ) 由引理3 2 2 知：，= 5 ，三= 2 l ，在乏。中不存在元素口满足o ( 口) = 2 1 ； ( 4 )由引理3 2 3 知：j = 5 ，三= 2 l ， 2 g ，一1jg = 2 ，3 ，4 ，因为32 1 ， 所以p 三= 2 1 ； ( 5 ) 利用d ( 2 1 ，5 ，1 ) 的基区组b 三 0 ，5 ，6 ，9 ，1 9 ) ，构造指数矩阵e 2 0 ，然后有 e = e s 趔= 【o 易2 0 】可以得到( ，三) = ( 5 ，2 1 ) 一q c l d p c 码， 0o5691 9o56 9 1 9o5 691 9 0 5691 90 6 9 1 9o591 9o56 o691 9o51 9o5695 691 90 091 9o5 656 91 90 1 9o56 9 o1 9o56 991 9o5 6691 9o 5 p = v = 2 1 。 o56 9 1 9 1 9o569 91 9o56 691 9 05 569 1 9 o 孙涛：准