（基础数学专业论文）基于完备循环差集ldpc码的构造.pdf

宋德银基于完备循环差集l d p c 码的构造三 中文摘要 1962 年格拉哥( g a l l a g e r ) 首次提出低密度奇偶校验码，几类 低密度奇偶校验码己被构造，通过和积迭代译码算法进行仿真得到码 的表现可知，它们都是近s h a n n o n 限码。在过去的几年里，研究组要 目标是构造伪随机低密度奇偶校验码，使其既有好的误差表现，而且 也要接近s h a n n o n 限。尽管一些知道的伪随机低密度奇偶校验码具有 极好的的纠错性能，但复杂度问题对码构造与设计的好坏也起着决定 一 性作用。伪随机低密度奇偶校验码具有高的复杂度的一个重要原因是 由于这个码对应生成矩阵并不是个稀疏矩阵。伪随机低密度奇偶校验 码这个问题可以通过构造具有一定结构的低密度奇偶校验码来解决。 已经有几类具有一定结构低密度奇偶校验码被构造出来，其中比较好 的有基于组合设计构造的低密度奇偶校验码，基于有限几何构造的低 密度奇偶校验码和基于正交拉丁方阵构造的低密度奇偶校验码。这些 具有结构低密度奇偶校验码都具有准循环这一性质，而准循环低密度 奇偶校验码在编码上要优于伪随机低密度奇偶校验码，它们可以使用 简单的线性反馈移位寄存器进行编码，最重要的是其复杂度与码长成 线性关系。 在迭代译码条件下，低密度奇偶校验码的表现有这个码的众多指 标决定。这些指标中一个重要的就是码的围长，其定义为码对应二部 图中最短环的长度。一个码在迭代译码下表现良好，则它对应二部图 扬州大学硕士学位论文 不能含有太多长度为4 的短环，因此在码的构造中必须阻止长度为4 的环出现。许多实验结果表明：在迭代译码条件下低密度奇偶校验码 错误盆地效应很大程度上依赖码的最小汉明距离，而对非正规低密度 奇偶校验码的错误盆地效应依赖它二部图变量结点和校验结点的度数 分布。 本文基于组合数学中完备循环差集提出了两类低密度奇偶校验码 的构造方法。一类是通过分解完备循环差集的关联矩阵q 来构造低密 度奇偶校验码的校验矩阵日( f ) ，这种分解方法可以降低码的校验矩阵 中非零分量的密度，因而可以大大减少影响低密度奇偶校验码性能的 短环数量。另一类低密度奇偶校验码和我们熟知的阵码( a r r a yc o d e s ) 一样，其校验矩阵是由一些小的循环置换矩阵组成，且覆盖一大类不 同码率和不同列重的低密度奇偶校验码码。根据这类的结构，采用大 规模集成电路来设计并行译码器极其有效。由于两类码所对应二部图 图的围长( g i r t h ) 至少为6 ，因而大大减少图上迭代时外信息之间的相关 性，进而提高译码性能。根据比特误码率和帧误码率标准，在加性高 斯白噪声信道下，用和积迭代译码算法进行译码仿真表现良好，并且所 构造的码具有准循环结构，因此它们可以使用简单线性移位寄存器在 线性时间内完成编码。值得注意的是，这一优点一般不被其它随机低 密度奇偶校验码所分享。 关键词低密度奇偶校验码，循环差集，迭代译码。 宋德银基于完备循环差集l d p c 码的构造 a b s t r a c t l o w - d e n s i t yp a r i t y - c h e c k ( l d p c ) c o d e s ，w h i c hw b 田 ei n 扛o d u c e db yg a l l a g e ri n 1 9 6 2 s e v e r a ll o w d e r t s i t yp a r i t y - c h e c k ( l d p c ) c o d e sh a v eb e e nd e s i g n e da c h i e v i n g p e r f o r m a n c er e s u l t sv e r yc l o s et ot h es h a n n o nl i m i tw h e ni t e r a t i v e l yd e c o d e du s i n gt h e s u m - p r o d u c ta l g o r i t h mw i t hl i n e a rc o m p l e x i t y d u d n gt h ep a s tf e wy e a r s ， i n t e n s e r e s e a r c hh a sb e e nf o c u s e do np s e u d o r a n d o ml d p cc o d e sw i t ht h ea i mo fc l o s i n g t h eg a pb e t w e e nt h es h a n n o nl i m i ta n de r y o rc o r r e c t i o np e r f o r m a n c e so f l d p cc o d e s d e s p i t et h ee x c e l l e n te r r o r - c o r r e c t i n gp r o p e r t i e so fs o m ek n o w np s e u d o - r a n d o ml d p c c o d e s , c o m p l e x i t y i s s u e st r e n dt od o m i n a t e s y s t e m a r c h i t e c t u r ea n dd e s i g n c o n s i d e r a t i o n t h eh i 【曲c o m p l e x i t yo fp s e u d o r a n d o ml d p cc o d e si sad i r e c t c o n s e q u e n c eo f t h ef a c tt h a tf o rt h e s ec o d e sal a r g ea m o u n to f i n f o r m a t i o ni sn e c e s s a r y t os p e c i f yp o s i t i o n so ft h en o n - z e r oe l e m e n t si nt h ep a r i t y - c h e c km a t r i x t h e c o m p l e x i t yd r a w b a c k so fp s e u d o - r a n d o ml d p cc o d e sc a nb eo v e r c o m eb y u s i n g s t r n e t u r e dl d p cc o d e s s e v e r a lc l a s s e so fs t r u c t u r e dl d p cc o d e sa r ek n o w n , i n c l u d i n gt h o s eb a s e do n c o m b i n a t o r i a ld e s i g n ，f i n i t eg e o m e t r i e sa n dm u t u a l l y o r t h o g o n a ll a t i ns q u a r e s s o m eo ft h es t r u c t u r e dl d p cc o d e sh a v et h ep r o p e r t yo f b e i n gq u a s i c y c l i c q u a s i - c y c l i cl d p cc o d e s ( q c l d p c ) h a v ee n c o d i n ga d v a n t a g e s o v e rp s e u d o - r a n d o ml d p cc o d e sa st h e yc 勰b ee n c o d e du s i a gs i m p l es h i f t - r e g i s t e r s w i t hc o m p l e x i t yl i n e a r l yp r o p o r t i o n a lt h e i rc o d el e n g t h t h ep e r f o r m a n c eo f a nl d p cc o d e sw i t hi t e r a t i v ed e c o d i n gd e p e n d so l lan u m b e r o f c o d es t r u c t u r ep r o p e r t i e s o n es u c hs t r u c t u r a lp r o p e r t yi st h eg i m lo f t h e c o d et h a ti s d e f i n e da st h el e n g t ho ft h es h o r t e s tc y c l ei nt h ec o d e st a n n e rg r a p h f o rac o d et o p e r f o r mw e l lw i t hi t e r a t i v ed e c o d i n g , i t st a n n e rg r a p hm u s tn o tc o n t a i nt o om a n y s h o r t c y c l e so f l e n g t h4 ，t h e r e f o r ei nc o d ec o n s t r u c t i o n ，c y c l e so f l e n g t h4m u s tb ep r e v e n t e d m a n ye x p e r i m e n t a lr e s u l t ss h o wt h a tt h ee r r o r - f l o o ro f a l ll d p cc o d e sw i t l li t e r a t i v e d e c o d i n gv e r ym u c hd e p e n d so nt h em i n i m u m d i s t a n c eo fa nl d p cc o d ea n dh e n c ei t i sn e c e s s a l vt ok e e dt h em i n i m u md i s t a n c eo fa l ll d p cc o d er e a s o n a b l y1 a r g e f o ra n 3 扬州大学硕士学位论文 i r r e g u l a rc o d ew i t hi t e r a t i v ed e c o d i n g , i t se r r o rp e r f o r m a n c ea l s od e p e n d so nt h ed e 伊e e d i s t r i b u t i o n so f t h ev a r i a b l ea n dc h e c kn o d e so f i mt a n n e rg r a p h t h i sp a p e rp r e s e n t san e wa p p r o a c ht oc o n s t r u c tl o w - d e n s i t yp a l i t y - c h e c k ( l d p c ) c o d e s t w oc l a s s e so fl d p cc o d e sa r ec o n s t r u c t e db a s e do np r e f e c tc y c l i c d i f f e r e n c es e t s t h ef i r s tc l a s si sc o n s t r u c t e db yd e c o m p o s f f i o no fi n c i d e n c em a t r i c e so f t h ep r e f e c tc y c l ed i f f e r e n c es e t s t h ed e c o m p o s i t i o nt e c h n i q u er e d u c e st h ed e n s i t yo f t h ep a r i t yc h e c km a t r i xa n dh e n c er e d u c e st h en u m b e ro fs h o r tc y c l e s ，w h i c hu s u a l l y i m p l i e sb e t t e rp e r f o r m a n c e t h ep a r i t y - c h e c km a t r i xo f t h e s e c o n dc l a s so f l d p cc o d e s a r em a t r i c e sc o m p o s e do fs o m es m a l lc i r c u l a n tp e r m u t a t i o nm a t r i c e sa n dc o v e ral a r g e s e to fc o d e sw i t hd i f f e r e n tr a t e sa n dc o l u m nw e i g h t s a st h ec l a s so f c o d e sw h i c hi s k n o w na sa r r a yc o d e s s ot h el d p cc o d e sc o n s t r u c t e da l eq u i t es u i t a b l ef o rp a r a l l e l v l s ld e c o d e ri m p l e m e n t a t i o n s s i n c et h e r ea l en oc y c l e so fl e n g t h4i nt h et a n n e r g r a p h s ，d e p e n d e n c ea m o n ge x t r i n s i ci n f o r m a t i o ni sg r e a t l yr e d u c e dd u r i n gi t e r a t i o na n d d e c o d i n gp e r f o r m a n c ei sa l s oi m p r o v e d e x p e r i m e n t a ls i m u l a t i o n si nt e r m so f b i te r r o r r a t ea n d f r a m ee r r o rr a t eo nt h ea d d i t i v ew h i l eg a n s s i a nn o i s e ( a w g n ) c h a n n e l s s h o wt h a to u rm e t h o dh a sr e m a r k a b l ec o d i n gg a i n s f u r t h e r m o r e ，t h e ya r eq u a s i - c y c l i c a n dt h e i re n c o d i n gc a nb ea c h i e v e di nl i n e a rt i m ea n di m p l e m e n t e dw i t hs i m p l e f e e d b a c ks h i f tr e g i s t e r s w en o t et h a tt h i sa d v a n t a g ei sn o ts h a r e db yr a n d o ml d p c c o d e si ng e n e r a l k e y w o r d sc y c l i cd i f f e r e n c es e t s ， i t e r a t i v ed e c o d i n g ， l o w d e n s i t yp a r i t y c h e c k ( l d p c ) c o d e s 4 宋德银基于完备循环差集l d p c 码的构造 1 引言 1 1 数字通信系统的组成 信息传输的可靠性与有效性是通信系统与储存系统的重要指标。尤其近几十 年来大规模集成电路技术的高速发展极大地促进了对这方面的需求。工程师们大 部分关注信息传输的差错控制，使得信息可靠传输得以实现。1 9 4 8 年s h a n o n 发 表一篇论文，给出通过适当的信息编码，由噪声所产生的错误在保证一定的传输 速率的前提下，错误率可以任意小。自从s h a n o n 的工作后，有效的编译码方法的 研究已成为差错控制工作的一个十分重要的方面。 图( 1 ：1 ，1 ) 是数字通信系统的功能框图和基本组成部分。其中信源编码器是把信 源发出的消怠转换成二进制形式的信息序列并且为了便传输有效，还去掉了一些 与传输信息无关的冗余度。为了抗击传输的各种干扰，人为地增加一些冗余度， 使其具有检错和自动纠错能力，这种能力由图中信道编码器提供。调制器的功用 是把纠错码送出的信息序列通过调制器变换成适合予信道传输的信号。数字信号 在传输过程中，总会遇到各种干扰而使信号失真，这种失真信号传输到接收端的 接收机，进行解调变成二进制信息序列。由于信道干扰的影响该信息序列中可能 已有错误，经过信道译码器对其中的错误进行纠正，再信源译码器恢复成原来的 消息送给用户。 图1 1 1 扬州大学硕士学位论文 由于我们仅关心图中的信息序列信道编译码器两个方框，为研究方便可将 图( 1 1 1 ) 简化成下面的模型( 图1 1 2 ) ： 4 图1 1 2 1 2 低密度奇偶校验码研究进展 低密度奇偶校验码( l o w - d e n s i t y c h e n k - p a r i t y c o d e s ) 是一类可以用非常稀疏的 校验矩阵日或二部图来描述的线性分组码，最初由g a l l a g e r 于1 9 6 2 年首次提出， 故亦称g a l l a g e r 码 1 ，g a l l a g e r 证明u ) p c 码的最小汉明距离随码长的增加而线性 增加，且满足g v 限的渐进好码，但鉴于当时的计算能力，l d p c 码被认为是不 实用的好码。经过几十年的沉寂，m a c k a y 和n e a l 【2 】重新发现了它，并证明它在 b p ( b e l i e f - p r o p a g a t i o n ) 算法与迭代译码相结合的条件下具有近s h a n n o n 限的性能。 1 9 8 1 年，t a n n e r 3 首次提出用图的模型描述线性分组码，将线性分组码的校 验矩阵用二部图( t a n n e r 图) 来表示。好的l d p c 码应具有良好的纠错性能和低 的编译码复杂度。c 孙l a g e l 和m a c k a y 所构造的l d p c 码是正规的或近正规的。 l u b y 4 ，5 的研究表明，好的非正规l d p c 码性能要优于正规l d p c ，他还提 出了一类基于非正规t a n n e r 图的l d p c 码，称为t o r m a d o 码，用于纠删信道，具 有线性编译码时间。由于采用了非正规的t a n n e r 图，t o r m a d o 码具有更大的扩展 性和更好的收敛性，纠删性能更强。m a c k a y 6 等指出：能进行快速编码的l d p c 码校验矩阵通常具有下三角的结构。l d p c 码译码采用迭代算法，其推导和证明 宋德银基于完备循环羞集l d p c 码的构造 是基于信息独立的假设。实际构造的大都数l d p c 码，其对应的t a n n e r 图都存在 小的短环，这些短环是造成译码性能降低的重要原因。构造好的l d p c 码的研究 可分为两个方面：一是寻找构造码的分析方法，二是具体构造综合性能更好的码。 y m a o 和b a i h 锄h e 【7 】基于码的性能，提出利用围长( g i r t h ) 分布来设计l d p c 码的 方法。x - y h u 【8 】提出渐进边增长( p r o 咿s i v e e d g 争f f o w t h ) 算法，这种算法适 于随机构造正规和非正规的l d p c 码，通过对围长的优化，可以消除短环。 t a r m e r ，f u ja ，g m a i a n g f e n g 9 】等以循环矩阵构造的l d p c 码具有大围长。y u k o u 和s h u l m 1 0 】等人利用有限几何方法构造l d p c 码，给出了4 种基于e u d d e a n 空 间的点和线设计出的码。w e b c r g 【1 l 】通过对因子图的研究发现，对任意给定系统， 无环图的状态复杂度是最大的，有环图的状态复杂度则会大大降低，这说明有环 t a n n e r 图的l d p c 码可以具有较低的译码复杂度。m a c k a y 【1 2 等还指出，消除长 度为4 的环对码的性能有很大提高，但继续消环对于提高码性能的作用则越来越 不明显。 近十年来，构造性能优良的l d p c 码一直是l d p c 码的研究热点之一。一般构 造l d p c 码的方法主要分两类：( 1 ) 随机码f 1 】， 1 6 】 】9 】，( 2 ) 结构码f 2 0 】- 【2 5 】。随机 u ) p c 码一般是通过计算机搜索来得到，它是基于某种确定的设计或图结构，如 围长( g i r t h ) 或结点的度数分配。而结构l d p c 码的构造是基于代数或组合设计的 方法。一般长的随机码要比同等条件下构造码的表现更接近s h a n n o n 限，然而一 般随机码的编码复杂度较高，这归结于缺少一定的代数结构。相比而言，结构码 的编码要优于随机码，尤其是循环或准循环码 1 0 】。它们可用简单的线性反馈移 位寄存器来实现，且编码复杂度与码长成线性关系【2 6 】。事实上，在实际中结构 良好的l d p c 码与随机码在误码率和盆地效应等方面有一样好的表现 3 4 】，【3 6 】。 本文基于组合数学中完备循环差集提出了两类l d p c 码构造的方法。一类是 通过分解完备循环差集的关联矩阵来构造l d p c 码的校验矩阵，这种分解方法可 以降低码的校验矩阵中非零分量的密度，医面可以减少影响l d p c 码性能的短环 扬州大学硕士学位论文 数量，并且使得到的码具有准循环结构。另一类l d p c 码和我们熟知的阵码一样， 其校验矩阵是由一些小的循环置换矩阵组成，且覆盖一大类不同码率、不同列重 的l d p c 码。根据这类的构造，不但编码简单，而且译码器的设计非常有效的， 可采用大规模集成电路来设计并行译码器 3 1 。由于这两类码所对应t a n n e r 图的 固长( g i r t h ) 至少为6 ，因而大大减少图上迭代时外信息之间的相关性，进而提高 译码性能。根据比特误码率和帧误码率标准，在加性高斯臼噪声信道下，用和积 迭代译码算法进行译码仿真表现良好，并且所构造的码都具有准循环结构，因此 它们可以使用简单线性移位寄存器在线性时间内完成编码，这一优点一般不被其 它随机l d p c 码所分享。 6 1 3 本文内容安排 本文将分成一下几个部分：第二部分简略介绍线性码和图的基本知识，以及它 们之间的关系，并介绍低密度奇偶校验码的一种迭代译码方法( 和积算法) 。第三 部分介绍一些本文所使用的数学工具循环差集。第四部分给出两类基于完备循 环差集l d p c 码的构造方法，并给出在加性高斯白噪声信道下进行仿真的效果。最后 对全文内容进行总结。 宋德银基于完备循环差集l d p c 码的构造 2 图和码 2 1 线性码 一个信息是个长度为k 的0 - 1 序列，【万，明线性码c 是一个在域g f ( 2 ) 上的 n 维线性空间的一个| j 维子空间，每个信息“= ( “。，q ，“。) 对应唯一一个码字 c = ( c o ，q ，q 。) 。由于c 是一个七维线性子空间，其中存在后个线性独立的向量 g o ，g l ，g k 。，使得c 可以由它们线性生成。因此，每个码字能够被它们线性表示 c = u g ，其中g = 【爵，矸，吐。r 是一个七n 阶矩阵，称g 为码c 的生成矩阵a 码c 的正交补空间c “是一个m = ，1 | j 维线性子空间，它们可以被埘个线性独立的 向量，啊，吒。生成。对每个码字c 都有c 岛= o ( o j y i p 。 7 扬州大学硕士学位论文 2 _ 3t a n n e r 图 、j 对于l d p c 码，我们可以用图来表示其校验矩阵，称此图为t a n n e r 图。为了方 便叙述，我们先回顾图论的基本定义。设g = ( 矿，e ) ) 是一个图，其中矿是结点集 e 是边集。y 中一个结点的度数是连接该结点边的总数。在无向图中，一系列依 次首尾相连的边，称为一个链。起点和终点相同且没有使用同一边超过一次的链 称为一个环。环的长度是其中边的数目。图g 的围长( g i m i ) 是g 中最短环的长度。 如果结点集矿能被分成两个不相交的子集巧和k ，并且使得k 和k 内部结点之间 没有边相连，贝q 称g 为二部图( 如图2 3 1 ) 。由图论知识可知，g 是二部图当且 仅当它的环长是偶数。 t a n n e r 图是二部图，其中两个不相交的结点集k 和砭分别称为比特结点和校 验结点。一个码字的每个比特皆对应一个比特结点，而每个校验方程对应一个校 验结点。我们用图( 2 3 2 ) 来解释码的校验矩阵日与t a n n e r 图之间的对应关系。 h = l0 11 oo ol 1o 0l l0 ol l0 o0 11 ol 宋德银基于完备循环差集l d p c 码的构造 图( 2 3 2 ) 是一个4 x 6 阶矩阵h 对应的t a n n e r 图，日的行对应校验结点，日的 列对应t 锄e r 图的比特结点：若= 1 表示在g 中有一个边连接墨。和0 ，两个结 点。例如k = 1 对应图中带箭头的线表示的边。在t a n n e r 图中 瓴，也) ，( 屹，s ：) ，( s ：，h ) ，( v 4 ，s o ) 形成一个长度为4 的环，它是这个图中最短的环因 此其围长g = 4 。 2 。4l d p c 码的译码 目前l d p c 码的译码广泛采用和积算法 2 9 。它是基于t a n n e r 图的并行且有 利于硬件实现的一种迭代译码算法。为了简单地描述它，我们先定义一些量。 三( m ) = f ：k = 1 ) 表示校验矩阵第m 行中非零分量的列标所形成的集合。 m u ) = 却：k = 1 表示校验矩阵第，列中非零分量的行标所形成的集合。g 二表示 除第，个校验结点外其他校验结点提供外信息的情况下，第m 个信息结点c 。= x 的概率。蠕表示在码字中第，个比特是e i = 石且其他比特服从分布 钿：，三( 掰) f ) ) 的情况下，第州个校验方程满足的条件概率，其中后面两个量 与校验矩阵日的非零元素的位置相对应且在译码中被不断更新。译码过程如下： 9 扬州大学硕士学位论文 1 、初始化：d - - 1 ( 1 + e x p ( 一2 z t c r 2 ) ) ，钟= l d ，z 是接收向量，0 2 是高斯 白噪声的方差。令g “0 = p o , 叮二= p 1 ； 2 、水平迭代： 名= o 5 0 + 兀( 1 2 q ：瑚 t c l ( m ) q l 砖= 1 - 喝； 3 、垂直迭代：q o = a 耐钟兀匕，如= a 耐一兀如，其中口。，被 m w ( ，) 、枷m 蛳f f ”t m 选择使得如+ 如= 1 ； 4 、尝试译码； q 是为保证钟+ g ；_ 1 ，计算完后对码字中每一位进行硬判定。 如果卵 0 5 ，则c f = o ，否则判为1 ，然后计算c 是否为零， 1 0 如果是零，则本次译码结束，否则转到2 进行下一次迭代，直 到译出码字或达到最大迭代次数时停止。 2 5 环及围长( g i r t h ) 我们知道在无环t a n n e r 图中，和积算法经过有限步计算是最优译码，然而计 算复杂度较高。当t a n n e r 图有环时，和积译码算法是一个次最优算法。环影响译 码算法性能，主要表现译码收敛速度减缓且不是最优译码，尤其是长度为4 的短 环 2 7 。所以在码的构造要适当的引进一些环，但不能引进长度为4 的环。这主 要由围长来控制。对增大围长避免短环，校验矩阵应该足够稀疏，这意味着码长 必须足够大。事实上，g a l l a g e l 给出围长为g 正规l i ) p c 码的长度的一个下界 1 。 若校验矩阵日的列重为，行重为p ，则码长，z 满足： m + l ( 1 ) 对g = 4 m + 2 ， 墨其中焉= l ，量= y ( y 1 ) “2 ( p 一1 ) i - 1i 2 ； 末德银基于完备循环差集l d p c 码的构造 + l ( 2 ) 对g = 4 m ， 2 乏：厶其中厶= p ( y 一1 ) “( p 1 ) “， f = 1 ，2 ，m + l 例如构造一个仉3 ，1 2 ) ，g = 1 2 的u ) p c 码n 应满足力6 0 8 4 。当然，对给定的个g ， n 即使满足上面的界，也可能不存在长度为刀的正规l d p c 码，使得其围长为g 。 扬州大学硕士学位论文 3 循环差集 3 1 差集的基本概念 定义3 i 称以正整数v 为模的k 个互不同余的整数所组成的集合 d ；如l ，a 2 ，a k ( m o d v ) 为一个| 】 ，且) 差集，并记为d ( v ，k ，如果对每个d 0 ( m o d v ) 恰好在d 中有兄个 有序对 ，巳) 使得式下式成立 d = - - a i a j ( r o o d v ) 由定义立刻得到差集参数满足： k ( k 一1 1 = , t ( v - 1 ) 当旯= 1 时， l = k 2 k + 1 我们称此循环差集为完备差集。 例：d 1 = o ，1 ，3 ( r o o d 7 ) ； b = o ，3 ，5 ，6 ) ( r o o d 7 ) ； 功= o ，l ，3 ，9 ( m o d l 3 ) ； d 4 = o ，3 ，4 ，5 ，6 ，8 ，1 0 ，1 5 ，1 6 ( m o d l 9 ) 。 它们参数分别为( 7 ，3 ，1 ) 差集，( 7 ，4 ，2 ) 差集，( 1 3 ，4 ，1 ) 差集，( 1 9 ，9 ，4 ) 差集，其中d l 和d 3 是完备差集。 为了验证d 是否为差集，我们可以构造一个表。 013 9013 9 ( m o d l 3 ) o 等 1 3 9 表中第f 行第列元素是乃- a t ( m o d v ) ，如上表中第3 行第2 列元素是1 3 ( m o d l 3 ) 。 1 2 宗德银基于完备循环差集l d p c 码的构造旦 称这个表为差集表，显然，如果d 为完备差集，则表中除了零外每个元素只出一 次所以对完备差集，我们有下面性质： 性质3 2 完备差集表中非零元素互不相同。 设d = “，口2 ，吼 ( m o d v ) 是一个差集，则对任意整数，集合 d 十s = 如+ s ，a 2 + f ，q + s ( m o d v ) 也是一个差集，它称为d 的一个循环平 移。由定义可知，差集的循环平移最多产生s 1 个不同的差集，但它们的差集表 都相同的。从差集表角度，我们可以把一个差集和它们的所有平移看成一个差集。 3 。2 差集的构造 差集的构造有很多方法，主要分成两类： 一是通过计算机随机搜索；二是代数、组合设 计等方法。下面我们给出一种通过计算机搜索 来找差集的方法。首先给出一些相关概念 定义3 3 和为v 的1 个正整数 v ) 作为圆周 上循环排列，如能通过邻加恰好生成l ，2 ， v 。l 诸数各五次，则称它是一个完备距离循环排 列，简记为c p p d ( v , k ，。 例如不论是( a ) 图，或是( b ) 图四个数字之和为 1 3 ，另外，沿着圆周f 个数字相加一= ，z 丑硼可 以得到1 ，2 ，1 3 各数字有且仅有一次 ( a ) l ，2 ，i + 2 = 3 ，4 ，4 + i = 5 ，6 ，4 + i + 2 = 7 ，2 + 6 = 8 1 + 2 + 6 - - 9 ，6 + 4 = 1 0 ，6 + 4 + 1 = 1 l ，2 + 6 + 4 = 1 2 ，1 + 2 + 6 + 4 - - 1 3 ： ( b ) l ，2 ，3 ，1 + 3 = 4 ，3 + 2 = 5 ，6 ，4 + l + 2 = 7 ，7 + 1 = 8 ， 扬州大学硕士学位论文 所以( a ) ( b ) 就是c p p d ( v ，k ，t ) = c p p d ( 1 3 ，4 ，1 ) 的两个不同的构造方式。循环差集 与完备距离循环排列之间的关系用下面定理来说明： 定理3 4 2 8 3 ( 1 ，k ，a ) 差集存在的充要条件总存在一组有序循环排列 l l ，乞，) 通过邻加生成c p p d ( v , k ，a ) 。 证明：“j ” 设d = 4 l ，a 2 ，吗，a k ( m o d v ) ；1 芑- - 个“| | ，a ) 差集，并且0 - a l a i v 。 令4 = 1 ，+ q - a k ，= a t 一口2 f s 晃，则为正整数， 并且对1 i j k ， 口，一口，= 杰， li 口f - a j = + 卜v 于是“，毛，) 是一个c p p d ( v ，k ，a ) 。 = y 。 f l l 设媛，乏，& ) 是一个c p p d ( v , k ，力，则对任意整数口，令 t - i a i = 口+ ，i = 1 ，2 ，k ( 2 ) 1 4 t 则由= v 易知有( 1 ) 和( 2 ) 成立。从而d = “，4 ：，呜，a k ( m o d v ) 是一个 ( v ，k ，兄) 差集。 下面我们给出c p p d ( v ，k ，a ) 一些性质 性质3 5 2 8 在一个c p p d ( v ，k ，a ) 中，数1 出现a 次，数2 至少要出现一次。 来德银基于完备循环差集l d p c 码的构造 性质3 6 2 8 如果和为v 的k 个正整数有序排列辑，厶，厶) 能通过邻加生成 1 ，2 ， 刍各a 次，则它构成c 料