（应用数学专业论文）一类无小环的量子低密度校验码的构造.pdf

摘要 信道噪声是信息处理系统必须克服的一大障碍。纠错码能保护信息免受噪 声影响。其关键思想是，如果要保护一个消息，应当通过对这个消息加入一些 冗余信息来编码消息。这样，即使编码消息受噪声的污染，在编码消息中仍有 足够的冗余度恢复或解码消息，使得原来消息中的信息得以恢复。不论是经典 纠错编码理论还是量子纠错编码理论都是采用这一思想。 在经典纠错码领域中，低密度校验码( l o w - d e n s i t yp a r i t y - c h e c kc o d e s ，简 称为l d p c 码1 以其突出的纠错性能成为人们的研究热点。在众多l d p c 码的 类型中，拟循环l d p 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 码) 能 被简单的移位寄存器以线性时间完成编码，也备受人们的关注。在量子纠错码 领域中，与经典纠错码有紧密联系的是稳定子码( s t a b l i z e rc o d e s ) ，这是一类结 构丰富的量子纠错码。c a l d e r b a n k - s h o r s t e a n e ( c s s ) 码就是其中一类具有特 殊结构的稳定子码。它需要一对满足扭关系( t w i s t e dr e l a t i o n ) 或者一个自对偶 ( d u a l c o n t a i n i n g ) 的二元码。自对偶的l d p c 码必含有长度为4 的环( 小环) 。 当用消息传递译码算法译码时会引起重大错误。 本文首先扼要地介绍了经典纠错编码理论和量子纠错编码理论的发展 历史。接着介绍了经典线性码和量子码的基本知识，其中包含了l d p c 码、 q c l d p c 码、c s s 码的基本概念和基本结论。最后，给出了一种利用子群的 陪集构造一对无小环的，且满足扭关系的q c l d p c 码的构造方法。因此，以这 对q c l d p c 码所得到的c s s 码相比于基于自对偶码构造而得的有较大的优越 性。此外，还提出一种对q c l d p c 码的指数矩阵的复合方法。这种矩阵的复合 方法能继承原先的无小环和扭关系这两个性质，即如果复合前那对q c l d p c 码是无小环，且满足扭关系的，那么复合后所得的那对q c l d p c 码还是无小 环，且满足扭关系的。利用这种复合方法，能得到参数广泛的c s s 码。 关键词：量子码，c s s 码，低密度校验码( l d p c 码) ，拟循环l d p c 码 ( q c l d p c 码) a b s t r a c t c h a n n e ln o i s ei sag r e a to b s t a c l et h a tm u s tt ob eo v e r c o m eo fi n f o r m a t i o n p r o c e s s i n gs y s t e m s 王e r r o r c o r r e c t i n gc o d e sc a np r o t e c ti n f o r m a t i o na g a i n s tn o i s e t h ek e yi d e ai st h a ti fw ew i s ht op r o t e c tam e s s a g ea g a i n s tt h ee f f e c t so fn o i s e ， t h e nw es h o u l de n c o d et h em e s s a g eb ya d d i n gs o m er e d u n d a n ti n f o r m a t i o nt o t h em e s s a g e t h a tw a y , e v e ni fs o m eo ft h ei n f o r m a t i o ni nt h ee n c o d e dm e s s a g e i sc o r r u p t e db yn o i s e ，t h e r ew i l lb ee n o u g hr e d u n d a n c yi nt h ee n c o d e dm e s s a g e t h a ti ti sp o s s i b l et or e c o v e ro rd e c o d et h em e s s a g es ot h a ta l lt h ei n f o r m a t i o ni n t h eo r i g i n a lm e s s a g ei sr e c o v e r e d e i t h e rc l a s s i c a le r r o 卜c o r r e c t i n gc o d i n gt h e o r y o rq u a n t u me r r o r - c o r r e c t i n gc o d i n gt h e o r yi su s i n gt h i si d e a 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 sh a v eb e c o m et h er e s e a r c hf o c u s f o ri t so u t s t a n d i n gp e r f o r m a n c ei nc l a s s i c a le r r o r - c o r r e c t i n gc o d i n gf i e l d s i na l l k i n d so fl d p c c o d e s ，q u a s i c y c h cl d p c ( q c - l d p c ) c o d e sc a nb ee n c o d e di n l i n e a rt i m eu s i n gs i m p l es h i f tr e g i s t e r s ，a n da t t r a c tt h ea t t e n t i o no fp e o p l e i n q u a n t u me r r o r c o r r e c t i n gc o d i n gf i e l d s ，s t a b i l i z e rc o d e si sar i c h l ys t r u c t u r e dc l a s s o fc o d e sw i t hac l o s ec o n n e c t i o nt oc l a s s i c a le r r o r c o r r e c t i n gc o d e s c a l d e r b a n k - s h o r - s t e a n e ( c s s ) c o d e si sa k i n do fs t a b i l i z e rc o d e sw i t hs p e c i a ls t r u c t u r e c s s c o d e sc a nb ec o n s t r u c t e db yap a i ro fb i n a r yl i n e a rc o d e sw i t ht w i s t e d c o n d i t i o n ， o rad u a l - c o n t a i n i n gb i n a r yl i n e a rc o d e ad u a l c o n t a i n i n gl d p cc o d eh a v e c y c l e so fl e n g t h4 ( o r4 - c y c l e s ，f o rs h o r t ) ，w h i c hm a yc a u s ef a t a le r r o r sw h e na m e s s a g e p a s s i n gd e c o d i n ga l g o r i t h mi se m p l o y e d i nt h i sd i s s e r t a t i o n ，w ef i r s t l yb r i e f l yi n t r o d u c et h eh i s t o r yo ft h ed e v e l o p - m e n to fc l a s s i c a le r r o r - c o r r e c t i n gc o d i n gt h e o r ya n dq u a n t u me r r o r - c o r r e c t i n g c o d i n gt h e o r y w et h e ni n t r o d u c et h eb a s i ck n o w l e d g eo fc l a s s i cl i n e a rc o d e sa n d q u a n t u mc o d e s ，w h i c hc o n t a i n st h eb a s i cd e f i n i t i o na n dt h eb a s i cc o n c l u s i o no f l d p cc o d e s ，q c l d p cc o d e sa n dc s sc o d e s w el a s t l ys h o wac o n s t r u c t i o n o fap a i ro fq c l d p cc o d e sw i t hf r e e4 一c y c l e sa n dt w i s t e dr e l a t i o n t h e r e f o r i v扬州大学硕上学位论文 c s sc o d e so b t a i n e db yt h i sp a i ro fq c l d p cc o d e sh a v em o r e a d v a n t a g e st h a n b a s e do nad u a l c o n t a i n i n gl d p cc o d e i na d d i t i o n ，w ea l s os h o wa c o m b i n i n g m e t h o df o re x p o n e n tm a t r i c e so fap a i ro fq c l d p cc o d e s ，w h i c hi n h e r i tf r e e 4 - c y c l e sa n dt w i s t e dr e l a t i o nf r o mo r i g i n a lc o d e s ，t h a ti s ，t h ec o m b i n e dp a i ro f q c l d p cc o d e sa r ef r e e4 - c y c l e sa n ds a t i s f y i n gt w i s t e dr e l a t i o ni ft h eo r i g i n a l p a i ro fq c - l d p cc o d e sa r ef r e e4 - c y c l e sa n ds a t i s f y i n gt w i s t e dr e l a t i o n a p p l y i n gt h ec o m b i n i n gm e t h o d ，w ec a no b t a i nc s sc o d ew i t haw i d er a n g eo f p a r a m e t e r s k e y w o r d s ：q u a n t u me r r o r c o r r e c t i n gc o d e s ，c s sc o d e s ，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 ，q u a s i c y c l i cl d p c ( q c l d p c ) c o d e s 扬州大学学位论文原创性声明和版权使用授权书 作者： 题目： 院系： 学位： 日期：2 0 0 9 年5 月 陈鹏程 一类无小环的量子低密度校验码的构造 数学科学学院 硕士 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工 作所取得的研究成果除文中已经标明引用的内容外，本论文不包含 其他个人或集体已经发表的研究成果对本文的研究做出贡献的个 人和集体，均已在文中以明确方式标明本声明的法律结果由本人承 担 作者签名 签字日期 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交学位论文的复印件和电子文档， 允许论文被查阅和借阅本人授权扬州大学可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文同时授权中国科学技术信息研究所 将本学位论文收录到中国学位论文全文数据库，并通过网络向社 会公众提供信息服务 作者签名：弩! 醚鱼聋 签字日期：二戽小l 1 矽7 1 7 _ r 一 导师签名：桃导师签名：u l 签字日期：3 钥叼坤 ( 本页为学位论文末页如论文为密件可不授权，但论文原创必须声明) 1绪论 1 1研究意义 量子信息学是量子力学、计算机科学和信息论交叉融合产生的新兴学科领 域，是利用量子态编码信息、进行信息处理和传输的学科。量子信息处理能实 现经典信息处理难以有效实现的任务，比如物理模拟、密码分析和安全通信等 方面。近年来在理论和试验上都有重大的突破。量子信息学的发展为未来信息 科学的发展与变革提供了新的原理和方法。 量子计算机是基于量子力学基本规律的计算机，和经典计算机的最大区别 在于，按照态迭加原理，量子计算机可以同时对每个迭加分量进行变换，输出结 果是各个分量变换结果的概率幅迭加，这种计算被称作量子并行计算。正是这 种量子操作的并行性使得许多研究者相信在经典计算机和量子计算机的能力之 间存在着无法跨越的鸿沟。 1 9 8 5 年d d e u t s c h 提出一个简单的问题。对该问题，量子计算机存在 多项式算法，而经典计算机却需要指数算法。由此说明了量子计算机确实可能 从计算机能力上超过那些经典计算机。随后十年内，许多人努力改进d e u t s c h 令人瞩目的初步结果。1 9 9 4 年p s h o r 展示了两个极其重要的问题，即寻找 整数的素因子问题和解决离散对数问题，可以用量子计算机以多项式时间解 决2 1 3 】 4 】。量子计算机功能强大的进一步的证据是，在1 9 9 5 年l g r o v e r 证明 另一个重要问题在没有结构的搜索空间上进行搜索的问题在量子计算 机上可以被加速5 1 。 然而，在量子力学理论中存在退相干( q u a n t u md e c o h e r e n c e ) 问题，即量子 的相干性很难保持。在量子计算机中，量子位不是孤立的，它会与外部环境发 生相互作用，导致量子相干性的衰减。因此要使量子计算成为现实，一个核心 问题就是克服退相干。研究量子纠错码理论的目的就是保护量子状态不受噪声 干扰。所以，从一开始量子纠错编码理论在量子信息理论中就占据了非常重要 的地位。 2扬州大学硕士学位论文 1 2 研究背景 二十世纪四十年代，人们探索计算机科学的同时，通信在进行另一场革命。 c e s h a n n o n 分别在1 9 4 8 年和1 9 4 9 年发表了现代信息和通信理论奠基性的引 人瞩目的两篇论文f 6 1 吲。s h a n n o n 在数学上定义信息的概念，这是他迈出的关 键一步，并关注与信息通过信道传送有关的两个关键问题。第一、通过信道传送 信息需要哪些资源? 第二、在信道上可以保护信息避免噪声的干扰吗? s h a n n o n 分别用信息论的两个基本定理来同答这两个问题，即无噪信道编码定理和有噪 信道编码定理。前者定量给出了用于存储从信源发出信息所需要的物理资源， 后者定量给出了有噪声的信道能可靠传送信息的量。 根据s h a n n o n 的信息理论，一个数字通信系统主要由信源、信道、信道编 码器以及信道译码器四个基本部分组成，如图1 1 所示。为了在有噪声的情况下 传送信息，s h a n n o n 证明纠错码可用来保护要发送的信息，有噪信道编码定理 给出了纠错码提供保护的一个上限。虽然s h a n n o n 定理并没有给出实际能达到 这个上限的一组纠错码，但从s h a n n o n 的论文发表到现在，人们一直在不断推 出更好的纠错码试图逼近s h a n n o n 设定的极限。 图1 1 ：数字通信系统的模型 低密度校验码( l o w d e n s i t yp a r i t y c h e c kc o d e s ，简称为l d p c 码) 8 9 就 是一类能接近s h a n n o n 限的线性分组码，是由r g g a l l a g e r 于1 9 6 2 年提出 的。他证明了它的距离特性，和其性能接近s h a n n o n 限。但是由于运算复杂度 较大和当时计算机模拟能力的限制，以及后来更加实用的卷积码1 0 1 、t u r b o 码 1 1 】的出现，l d p c 码几乎没有受到人们的注意。但随着移动通信系统的发 展，常规的信道编码技术使得接收端进行信道译码的运算量太大。而l d p c 码 陈鹏程类无小环的量子低密度校验码的构造 3 的复杂度主要集中在编码，而译码的运算量较低，而且具有逼近s h a n n o n 极限 的性能。许多学者在g m l a g e r 算法的基础上，对l d p c 码的算法和运算量进行 了改进。 1 9 8 1 年，r m t a n n e r 提出用图论来描述码字的概念，从而将l d p c 码 的校验矩阵对应到被称为t a n n e r 图( 即双向二分图) 上，进一步证明了基于有 限无环( c y c l 曲e e ) 的t a n n e r 图的最小和译码算法( m i n - s u ma l g o r i t h m ) 与和 积译码算法( s u m p r o d u c ta l g o r i t h m ) 的最优性。由于采用随机t a n n e r 图的构 造，其中不可避免短环的存在。这些短环会造成译码信息的重复传递，使译码 过程中的消息不满足独立性假设，影响了迭代译码算法的收敛性，只能保证次 优译码1 2 1 。 上世纪九十年代，d j c m a c k a y 和r m n e m 利用随机构造的t a n n e r 图研究了l d p c 码，发现采用和积译码算法的正则l d p c 码具有突出的纠错 性能，和t u r b o 码有相似的译码性能f 1 3 1 1 4 1 ，并证明了t u r b o 码只是l d p c 码 一个特例【15 】。两者都是基于图构造的低密度码，在基于图的编译码理论中得 到统一。后来，t r i c h a r d s o n 等人设计的非正则l d p c 码，对于非常大的码长 ( n 1 0 5 ) 的纠错性能要强于t u r b o 码，并且达到了与s h a n n o n 限相差0 1d b 的范围f 1 6 1 。 此外，人们还利用因子图( f a c t o rg r a g h ) 模型 1 7 】、线性规划( f i n e a rp r o g r a m m i n gt 0 0 1 ) 【1 8 】、密度进化( d e n s i t ye v o l u t i o n ) 【19 】、e x i t ( e x t r i n s i ci n f o r m a t i o n t r a n s f e rc h a r t ) f 2 0 1 理论等工具做了进一步的研究。 l d p c 码有很多优点：具有较低的差错平层( e r r o rf l o o r ) 特性，可实现完全 的并行操作，译码复杂度低于t u r b o 码，适合硬件实现，吞吐量大，具有高速译 码的潜力。因此，l d p c 码具有巨大的应用潜力，能应用在深空通信、光纤通 信、卫星数字视频和声频广播、存储、移动和固定无线通信等方面。 l d p c 码的校验矩阵的结构是影响其性能的重要因素之一，反映在t a n n e r 图上，对性能有重要影响的就是图中最短环的长度，称为围长( g i r t h ) 。这就 需要采用一定的方法对校验矩阵进行构造，使围长较大，以获得好的性能。 由于l d p c 码的编码复杂度较高，影响码的实际应用。在众多的l d p c 码的 类型中，一类只需采用简单的移位寄存器就能实现编码的拟循环l d p 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 码) 引起人们的广泛注意。r m 4扬州大学硕- 上学位论文 t a n n e r 等人2 1 1 和m p c f o s s o r i e rf 2 2 1 分别对g a l l a g e r 在其博士论文f 9 1 中 提出过的一种准循环的代数结构进行了深入研究，且都利用循环置换矩阵 ( c i r c u l a n tp e r m u t a t i o nm a t r i x ) 的扩张这一技术。前者利用群的乘法结构构造出 q c l d p c 码，并指出了当码长较短或中等时，能达到随机构造的码的性能。这 种码被人们称为s r i d h a r a - f u j a - t a n n e r ( s f t ) 码。后者给出了利用循环置换矩 阵构造的q c l d p c 码的围长等于6 、8 、1 0 、1 2 的一个充分必要条件，并给 出一系列q c l d p c 码的构造方法。此后，人们用各种方法来构造具有较大围 长的q c l d p c 码，比如有限几何【2 3 】，区组设计 2 4 1 2 5 1 2 6 2 7 等方法。 与经典信息论相比，量子信息论也有着类似的发展过程。1 9 9 5 年，b s c h u m a c h e r 证明了与s h a n n o n 无噪信道编码定理类似的结果，并定义了“量 子比特( q u b i t ) ”作为切实的物理资源 2 8 】，但没有提出针对量子信息的对应于 s h a n n o n 有噪信道编码定理的结果。 与经典情形有很大不同，在量子环境下，编码有三个基本困难【2 9 】： 量子态不可克隆：在经典编码理论中，为了引入信息冗余，可以将单个比 特的信息复制到多个比特上。但在量子力学中，根据量子态的不可克隆 ( n o - c l o n i n g ) 定理，这种做法是不允许的。 差错是连续的：在经典编码中的错误只有是0 和1 之间的变化。但对量子 差错并不是这样。对于一个确定的输入态，其输出态可以是复二维向量空 间的任意态。即连续的不同差错可能出现在单量子比特上。 测量会破坏量子信息：在经典编码中，可以观测来自信道的输出，并决定 采用什么样的解码方式。而量子力学中的观测一般会破坏所观测到的量子 态并不可恢复。 幸运的是，这三个问题都不是致命的。p s h o r 3 0 和a s t e a n e 3 1 通过一 些巧妙的措施避免了上面所说的困难，分别于1 9 9 5 年和1 9 9 6 年各自独立地提 出了量子纠错编码方案。自s h o t 和s t e a n e 的工作以后，量子纠错编码理论迅 速发展起来。1 9 9 6 年，两个独立的研究小组，r c a l d e r b a n k 、p s h o r 3 2 和a s t e a n e 3 3 1 ，发现了用他们缩写名字命名的重要的c s s 类量子码，简称为c s s 码。这项工作被包含在由r c a l d e r b a n k 等人3 4 1 和d g o t t e s m a n l 3 5 分别独立 陈鹏程类无小环的量子低密度校验码的构造 5 发现的稳定子码( s t a b i l i z e rc o d e ) 中。稳定子码是建立在经典线性码的基本思想 基础之上的一种特殊的量子纠错码。这些成果大大加快了量子纠错码研究进展。 人们利用r m 码_ 6 】，r s 码3 7 1 ，b c h 码 3 8 】 3 9 】 代数几何码 4 0 4 l 】等经典码 构造出一系列好参数的量子码。 由于l d p c 码突出的纠错性能，l d p c 码对应的量子l d p c 码也被广泛 地研究。t c a m a r a 4 2 基于l d p c 码的图的表示构造出稳定子码。p t a n 和 j l i 4 3 4 4 禾1 j 用循环矩阵、拟循环矩阵、对称矩阵和置换矩阵构造了l d p c 码 的稳定子码。在c s s 码方面，d j c m a c k a y 等人f 4 5 i 利用特殊稀疏序列提出 了几种构造校验矩阵的方法，并在此基础上构造c s s 码。m s p o s t o l 4 6 $ 1 j 用 文献【2 3 】提出过的有限几何构造而得的l d p c 码来构造c s s 码。s a a l y 利 用有限几何中的点和线的关系 4 7 】以及拉丁方( l a t i ns q u a r e ) 4 8 来构造c s s 码。 i b d j o r d j e v i c 利用组合设计中的平衡不完全区组设计( b a l a n c e di n c o m p l e t e b l o c kd e s i g n ，b i b d ) 来构造c s s 码。这些c s s 码的构造方法都是基于自对偶 码( d u a l - c o n t a i n i n gc o d e s ) 的。在文献 4 2 】 4 5 】中指出，由自对偶码构造的c s s 码一定包含小环，这对译码是所采用的迭代译码算法的收敛性有影响。m h a g i w a r a 和h i m a i 4 9 幂t j 用一对满足扭关系( t w i s t e dr e l a t i o n ) 的q c l d p c 码 来构造c s s 码。这种方法避免了小环的出现。m i n h s i uh s i e h 等人 5 0 】进一步将 这种方法推广到另一种具有较好的极小距离的l d p c 码，就是所谓的t y p e - i i q c l d p c 码的情形中去。 在试验方面，量子码【5 ，1 ，3 】已于2 0 0 1 年在实验室成功实现了量子通信的 纠错功能。 1 3本文主要工作及内容安排 本文在文献 4 9 1 1 5 0 的基础上，对l d p c 码和量子码的构造做了研究，得到 了一些好的结果：利用有限域中子群的陪集，构造出无小环的q c l d p c 码，并 由此得到一对满足扭关系的码，构造出无小环的c s s 类量子码。我们修正了文 献 4 9 5 0 1 中的结果。另外还给出一个关于q c l d p c 码指数矩阵的复合方法， 这能继承原先的所具有的无小环和扭关系性质，因此能构造出参数更广泛的 c s s 码。 6扬州大学硕_ 上学位论文 具体内容安排如下：第二章介绍l d p c 码和量子码的基础概念，重点介绍 了q c l d p c 码和c s s 类量子码。在第三章中，我们对l d p c 码和量子码的构 造做了研究，提出一种基于子群的陪集的q c - l d p c 码的构造方法，构造出一 对无小环，且满足扭关系的q c l d p c 码，由此米构造无小环的c s s 码。这比上 面提到的基于自对偶码的c s s 码有一定的优越性。我们也指出这种q c l d p c 码的构造方法在经典纠错码中也具有一定的意义，它是s f t 码构造方法的推广 形式。此外，在这章中还提出一种对q c l d p c 码的指数矩阵的复合方法。这 种方法扩大了码的参数范围。 2l d p c 码和量子码 要发送的原始信息可以有不同的形式，如声音、文字、图像、数据等。利用 各种物理技术手段，把原始信息统一编成离散的脉冲电信号发出，脉冲只有有 限多个状态。在信道传输的过程中，不可避免地会受到噪声的干扰，因此编码 的根本任务之一就是对信息进行有效的处理，来达到检错和纠错的目的。最自 然的方法是在状态集合上引入适当的代数结构。假设脉冲有g 个状态( g 2 ) ， 可以用g 元有限域f 口中的元表示。事实上，数字通信中最常见的脉冲只有两个 状态，即常见的二元域f 2 = 0 ，1 _ ，称为比特( b i t ) 。 区别于经典比特，量子位( q u a n t u mb i t ，q u b i t ) 可以处于0 ，1 两个本征态 的任意叠加态，而且在对量子比特的操作过程中，两态的叠加振幅可以相互干 涉，这就是所谓的量子相干性。已经发现，在量子信息论的各个领域，包括量子 计算机、量子密码术和量子通信等，量子相干性都起着本质性的作用。可以说， 量子信息论的所有优越性均来自于量子相干性。但不幸的是，因为环境的影响， 量子相干性将不可避免地随时间指数衰减，这就是困扰整个量子信息论的退相 干问题。退相干引起量子错误，量子编码的目的就是为了纠正或防止这些量子 错误。虽然量子编码和经典编码的基本想法类似，即要以合适的方式引进信息 冗余，以提高信息的抗干扰能力，但量子码不是经典码的简单推广。 2 1线性码 这一节介绍经典编码理论中线性码的基础知识，具体内容可以参考文 献【5 l 】【5 2 】，先给出纠错码的概念。 定义2 1 1 叼表示f 口上的佗维向量空f - j ，叼的每个非空子集合c 都称为一个 q 元码，该码的码长为n ，c 中向量叫做码字。每个码字中的分量称为码元。 用k 表示c 中码字个数，即k = i c l ，显然1 k q n 。 k ；l o g 。k 称为码c 的信息位数( k 为实数，0 k 钆) 。 r = 等叫做码c 的信息率，简称为码率。 8扬州大学硕士学位论文 如果有意义的信息量与所有可能的码字数相等，这时通信系统并不具有纠 错能力。因此，纠错编码总要令可能的码字数大于信息量。这样，接受到的向量 可以与任何其他码字相比，更象哪个码字。这导致下面的概念。 定义2 1 2 设z = ( z o ，一1 ) 和y = ( y o ，y n 一1 ) 是赡中两个向量，则向 量z 和夕的h a m m i n g 距离d h ( z ，y ) 是指它们各对应分量不同的个数，即 d h ( z ，y ) = 群 i1 0 i 佗一1 ，翰y i 而向量z 的h a m m i n g 重量w h ( z ) ：= d h ( z ，o ) ，这里0 表示零向量。 与h a m m i n g 距离有密切关系的是另一个概念极小距离，能用来衡量 码的纠错能力。 定义2 1 3 码c 的极小距离d ( c ) ( 有时简记为d ) 为不同码字之间的h a m m i n g 距离的最小值，即 d = d ( c ) = m i n d h ( c ，c ，) | c ，c ，c ，c c ，) 定理2 1 4 ( 【5 2 】) 如果纠错码c 的最小距离为d ，则c 可检查d 一1 个错误， 也可纠正l 譬| 为错误。 这个定理虽然简单，却是整个纠错码理论的基础，也反映了极小距离是衡 量纠错码的纠错能力重要参数之一。下面给出线性码的定义。 定义2 1 5 向量空间叼的一个f q 上的线性子空间c 称为q 元线性码。即叼 的一个非空子集合c 叫做q 元线性码，是指若c ，c ，c ，则对任意a ，a 7 f 口， 都有a c + a d c 。 对线性码来说，k = i c i = q 七，其中k ：= d i m f 。c ，所以c 的信息位数就 是c 的维数。常将线性码c 表示成( n ，) 。或i n ，叫。由于极小距离的重要性， 也将c 记为( 佗，k ，d ) 。或h ，七，词口。已知q 的情况下，常省略下标口，即将c 记 为( n ，k ，d ) 或【n ，k ，d 】。 线性码比非线性码的一个主要优点是，线性码更容易定义。可以取c 的一 组f 口一基 g o ，g a ，9 七一1 ) ， g i = ( 仇，0 ，g i ，n 一1 ) ( 0 i k 一1 ) 陈鹏程一类无小环的量子低密度校验码的构造9 其中仇，j f 口( 0 i k 一1 ，0 j n 一1 ) ，则每个码字c 可唯一表示成 c = u o g o + u l g l + + u k 一1 9 詹一1 = ( 咖，牡 = 一1 ) g 其中u t f g ( 0 i k 一1 ) ，g 是f 口上秩为k 的危xn 矩阵 g = ( 三，) = ( 耋i 。三，) j ；三二- ，) 设t 正= ( u o ，u l ，u k 一1 ) 是待编码的消息，则对应的码字是 c = u g = ( u o ，u l ，u o g o + u l g l + + u 七一l g k 一1 显然，矩阵g 的各行生成了h ，纠线性码c 的整个码字空间。由此，称矩阵g 为码c 的生成矩阵。由于线性码c 中的基有不同的选取方式，所以c 的生成矩 阵不是唯一的。另外，任意一个线性码完全由它的生成矩阵确定。 对任一个行向量线性无关的kx 扎矩阵g ，都存在一个行向量也线性无关 的( 礼一k ) xn 矩阵日，使得g 的行向量生成的线性空间正交与日的行向量 所生成的线性空间。由此，我们也可以这样定义由矩阵g 生成的线性码 c = c 叼i c h t = 0 ) ( 2 1 1 ) 其中0 为长为佗一k 的零向量。所以可用日来检查任意长为n 向量是否为c 中 的码字。称矩阵日为线性码c 的一个校验矩阵。校验矩阵还可以确定线性码 的极小距离和用来纠错。 定理2 1 6 ( 【5 2 】) 设c 是参数为hk 】的q 元线性码，h = ( h o ，h 1 ，h n 1 ) 是c 的一个校验矩阵。如果h o ，h i ，h 。一1 当中任意d 一1 个均f q - 线性无 关，并且存在d 个列向量是f q - 线性相关的，则c 的最小距离为d 。 卯吼； 1 0扬州大学硕士学位论文 定理2 1 7 ( 线性码的纠错译码算法 5 2 】) 设c 是参数为h ，尼，d 】的q 元线性码， 其校验矩阵为h = ( h o ，h l j - 一，h n 一1 ) 。如果码字c c 在传送时错位个数 【等j ，即收到向量可= c - 4 - e ，其中叫日( ) 【学j 。则下列算法可以纠错。 f ，砂计算移= h y 丁，这是一个f 口上长为几一k 的列向量，叫做可的校验向 量； 俐如果口= 0 ，则e = 0 ，可= c 佛错) ； 俐如果移0 ，则t ，必可表示称h o ，h l ，h n - 1 当中不超过【学j 个列 向量的线性组合： t ，= a i l 九i 1 + + n “九矗( 0 i i i t n 一1 ) 其中1 t 【孚j ，a i 。，啦。f ；= f g 一 0 】，这时 e = ( e o ，l ，e n 一1 ) 其中旬1 = 吼，= a i 。，而当i i l ，i t 时，毛= 0 。于是口= 可一g 。 换句话说，传送时出现了位错误，错位为i 1 ，i 2 ，i t ，对应的错值分别为 0 n ，啦2 ，a i t 若将线性码c 的校验矩阵日看称另一个码c 上的生成矩阵，显然c 上也是 线性码，其参数为h 几一k 】。由式( 2 1 1 ) ，知c 上是由矩阵g 生成的码c 的 零空间，即对任意的口c 和任意的伽c 上，有t ，硼= 0 。将c 上称为码c 的对偶码。所以，一个线性码的校验矩阵就是它的对偶码的生成矩阵。 2 2l d p c 码 l d p c 码是由g a l l a g e r 于1 9 6 2 年提出的一种能接近s h a n n o n 限的好 码 剐 9 。在这一节中，我们介绍l d p c 码、一类特殊的l d p c 码q c l d p c 码和l d p c 码的译码算法。 2 2 1 l d p c 码的定义和图表示 l d p c 码是一类线性码。正如上一节所述，任何一个线性码可以由一个生 成矩阵或一个校验矩阵定义。g a l l a g e r 提出的l d p c 码就是由一个特定的校验 矩阵来确定的。 陈鹏程一类无小环的量子低密度校验码的构造 1 1 定义2 2 1 二元l d p c 码的校验矩阵日要满足以下四个条件： ( 1 ) 日的每行有p 个“1 ”； ( 2 ) 日的每列有，y 个“1 ”； ( 3 ) 日的任意两行( 或两列) 间共同为“1 ”的个数不超过1 ； ( 4 ) 与码长和日中的行数相比较，p 和- y 很小。 注2 2 2 现在人们所指的l d p c 码是指仅满足条件( 4 ) 的线性码，即校验矩阵 中很少一部分元素非零，其他大部分元素都是零的线性码。为区分起见，将上 述定义的l d p c 码称为g a l l a g rl d p c 码。在下文中，如未特别指出，我们一 般讨论的都是砸2 上的l d p c 码。 定义2 2 1 中的条件( 1 ) 和( 2 ) 是说校验矩阵日的行重和列重分别是p 和7 。 将满足这两个条件的l d p c 码称为( ，y ，j d ) 一正则( r e g u l a r ) l d p c 码，否则称为非 正则( i r r e g u l a r ) l d p c 码。条件( 2 ) 和( 3 ) 保证了校验矩阵中的任意7 个列向量 均线性无关，由定理2 1 6 ，知该码的极小距离至少为7 + 1 。 设一个l d p c 码的码长为n ，信息位为k ，校验位为m = n k ，码率为 r = 皇，贝0 该码的校验矩阵是一个mx 死的矩阵。校验矩阵可用一个t a n n e r 图 表示。图的一边有n 个节点，每个节点表示码字的信息位，称为信息节点( 变量 节点) l j = 0 ，1 ，n 一1 】，对应校验矩阵各列；图的另一边有m 个节点，每 个节点表示码字的一个校验节点 色i i = 0 ，1 ，m 一1 ) ，代表校验方程，对应 于校验矩阵的各行；与校验矩阵中“1 ”元素相对应的左右两节点之间存在连接 边。将这条边两端的节点称为相邻节点，每个节点相连的边数称为该节点的度 数( d e g r e e ) 。显然对( 7 ，p ) 正则l d p c 码而言，每个变量节点的度数为，y ，每个 校验节点的度数为p 。 若一个节点序列中任一节点与它的前一节点和后一节点都是相邻节点( 首 节点的前一节点为末节点，末节点的后一节点为首节点) ，则称该序列为一个环 ( c y c l e ) ，这个环的边数称为环的长度。一个t a n n e r 图中最短环的长度称为该图 ( 码) 的围长( g i r t h ) 。一般地，性能好的l d p c 码的t a n n e r 图中不含短环，特 别是长度为4 的环( 最小环，或小环) 。因为对采用迭代译码算法的l d p c 码来 说，某一个节点发出的信息经过一个环长的传递会被传回本身，从而造成译码 信息的重复叠加，使译码过程中的消息不满足独立性假设，影响译码的准确性。 1 2 扬- i 1 大学硕士学位论文 条件( 3 ) 正是保证了t a n n e r 图中无小环。因此，在设计l d p c 码时，要保证该 码的围长至少为6 。 例1 设一个二元l d p c 码的的校验矩阵 00 01 11 11 01 10 可验证日的零空间定义了一个二元【7 ，4 ，3 】l d p c 码，其对应的t a n n e r 图如 图2 1 所示。 c o c lc 2 v 0 v lv 27 3 3v 4 v 5 图2 1 ：校验矩阵的t a n n e r 图 可以看出变量节点v o $ 1 u 3 的度数分别为1 和2 ，该码是非正则的，而 且t a n n e r 图中含有一个小环v 5 c ov 6c 1 ( 粗线部分) 。可用两种方法验 证c = ( 0 ，1 ，0 ，1 ，0 ，1 ，1 ) 是一个码字：c h t = 0 或者分别令 o ，v 1 ，v 6 为 0 ，l ，1 ，在c o ，c 1 ，c 2 处做模2 加都为0 。 2 2 2 q c l d p c 码 目前l d p c 码的构造方法主要可以分为两大类：( 1 ) 随机或伪随机的构造 方法是根据t a n n e r 图的想要满足的性质( 如围长，度分布等) ，依靠计算机搜 索校验矩阵 1 4 】 1 6 】主要考虑的是码的性能，在码长比较长( 接近或超过1 0 0 0 0 ) 时，性能非常接近s h a n n o n 限。( 2 ) 结构化构造方法是根据代数 2 1 】【2 2 】、有限几 陈鹏程一类无小环的量子低密度校验码的构造 1 3 何 2