（应用数学专业论文）基于循环差集的量子ldpc码的构造.pdf

沈洁基于循环差集的量了l d p c 码的构造 摘要 1 9 9 6 年以来，量子编码已成为量子信息学领域最热门的课题之一。量子纠错编码作为 其中的一种量子编码方案，是量子通信和量子计算实用化的基础。目前量子纠错编码理论 已日趋完善，许多经典的编码技术在量子领域中都可以找到相应的编码方法。 在经典纠错码领域，低密度奇偶校验码( l d p c 码) 是目前最受关注的编码之一。它的 校验矩阵具有稀疏性，其性能接近s h a n n o n 限，而且l d p c 码的译码简单，可进行并行操 作。其中，准循环l d p c ( q c l d p c ) 码是一类具有线性编码复杂度且所需存储空间较小的 l d p c 码，也是当前的研究热点。在量子纠错码领域，稳定子码是一类结构丰富的量子纠 错码。c s s 码作为其中一类具有特殊结构的稳定子码，可以由一个自对偶或一对满足扭关 系的经典二元线性码构造。那么在c s s 码的基础上，利用不含四环的经典l d p c 码构造量 子l d p c 码，这些量子l d p c 码将遗传相应的经典l d p c 码优越的性能。但通过自对偶码 构造的c s s 码一定含有长度为4 的块环，这对译码具有消极影响。所以构造一对满足扭关 系且无四环的经典l d p c 码成为研究量子l d p c 码的关键问题。 本文的主要工作是基于一种q c l d p c 码的构造方法，给出了构造一对满足扭关 系且无四环的q c l d p c 码的方法，获得了基于c s s 码的量子l d p c 码。 本文主要由以下三章内容组成： 第一章，简单地介绍了经典纠错编码理论和量子纠错编码理论的发展及研究意义。 第二章，介绍了l d p c 码和量子码的一些基本知识，主要包含l d p c 码、t a m m e r 图 表示、稳定子码及c s s 码的基本概念和基本结论。 第三章，给出了基于组合数学中完备循环差集与循环差集的一对满足扭关系且无四环 的准循环l d p c 码校验矩阵的构造方法，进而得到不含四环的量子l d p c 码。通过这种方 法构造的c s s 码比通过自对偶码构造的c s s 码具有更大的优越性。 关键词：l d p c 码，准循环l d p c 码，量子码，c s s 码，完备循环差集，循环差集 扬州大学硕：b 学位论文 a b s t r a c t s i n c e19 9 6 ，q u a n t u mc o d i n gh a sb e e no n eo ft h em o s tp o p u l a rt o p i c si nt h ef i e l do f q u a n t u mi n f o r m a t i o n a sak i n do fq u a n t u mc o d i n gs c h e m e , q u a n t u me r r o r - c o r r e c t i o nc o d i n gi s t h ef o u n d a t i o no fr e a l i z a t i o no fq u a n t u mc o m m u n i c a t i o na n dq u a n t u mc o m p u t a t i o n s of a r , t h e t h e o r yo fq u a n t u me r r o r - c o r r e c t i o nc o d i n gh a sb e c o m em o r ea n dm o r ep e r f 碱m a n y c o r r e s p o n d i n gm e t h o d so f c l a s s i c a lc o d i n gt e c h n i q u e sh a v eb e e nf o u n di nq u a n t u mf i e l d i nt h ef i e l do 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 e 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 ( l d p cc o d e s ) a r eo n ec l a s so ft h ec o d i n g sw h i c ha t t r a c tt h em o s ta r e n t i o nc u r r e n t l y t h ep a r i t yc h e c km a t r i xo f a nl d p cc o d ei ss p a r s ea n dt h es h a n n o nl i m i tc a nb ec l o s e l ya p p r o a c h e db yl d p cc o d e s t h e d e c o d i n ga l g o r i t h mo fl d p cc o d e sa l es i m p l e ，a n dc a nb eo p e r a t e di np a r a l l e l o fa l ll 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 sh a v el i n e a re n c o d i n gc o m p l e x i t ya n dn e e dl e s s s t o r a g es p a c e , w h i c ha r ea l s ot h ec u r r e n tr e s e a r c hf o c u si nt h ef i e l do fc l a s s i c a le r r o r - c o r r e c t i n g c o d e s i nt h ef i e l do fq u a n t u me r r o r - c o r r e c t i n gc o d e s ，s t a b i l i z e rc o d e sa l ear i c h l ys t r u c t u r e dc l a s s o fq u a n t u me r r o r - c o r r e c t i n gc o d e s a sac l a s so fs t a b i l i z e rc o d e s1 ) l ，i ms p e c i a ls t r u c t u r e s ，c s s c o d e sc a nb ec o n s t r u c t e db yad 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 eo rap a i ro fc l a s s i c a lb i n a r y l i n e a rc o d e s 谢lt w i s t e dr e l a t i o n b a s e do nc s sc o d e s ，w ec o n s t r u c tq u a n t u ml d p cc o d e sf r o m c l a s s i c a ll d p cc o d e sw i t h o u tf o u r - c y c l e s ，a n dt h o s eq u a n t u ml d p cc o d e sw i l li n h e r i tt h eb e r e r p e r f o r m a n c eo f t h e i rc l a s s i c a lc o u n t e r p a r t s b u tc s sc o d e sc o n s t r u c t e db yd u a l c o n t a i n i n gc o d e s m u s tc o n t a i nc y c l e so fl e n g t h4 w h i c hh a san e g a t i v ei m p a c to nt h ed e c o d i n g s ot h ek e y q u e s t i o no fq u a n t u ml d p cc o d e sr e s e a r c hi s t oc o n s t r u c tap a r i t yc h e c km a t r i xo fc l a s s i c a l l d p cc o d e sw i t ht w i s t e dr e l a t i o na n dw i t h o u tf o u r - c y c l e s i nt h i sp a p e r , b a s e do nam e t h o do fc o n s t r u c t i n gq c - l d p cc o d e s ，w ep r o p o s eam e t h o dt o c o n s t r u c tap a i ro fq c - l d p cc o d e s 、) i r i lt w i s t e dr e l a t i o na n dw i t h o u tf o u r - c y c l e s ，a n dt h u s o b t a i nq u a n t u ml d p cc o d e sv i ac s sc o d e s t h i sp a p e rc o n s i s t so ft h ef o l l o w i n gt h r e ec h a p t e r s t h ef i r s tc h a p t e rb r i e f l y 州e 、st h ed e v e l o p m e n ta n dr e s e a r c hs i g n i f i c a n c eo fc l a s s i c a l e 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 gc o d i n gt h e o r y t h es e c o n dc h a p t e rp r o v i d e ss o m eb a s i ck n o w l e d g eo fl d p cc o d e sa n dq u a n t u mc o d e s ， w h i c hc o n t a i nt h eb a s i cc o n c e p t sa n dr e s u l t so fl d p cc o d e s ，t a n n e rg r a p h ，s t a b i l i z e rc o d e sa n d 沈洁基于循环差集的量子l d p c 码的构造 c s sc o d e s i nt h et h i r dc h a p t e r , b a s e do np e r f e c tc y c l i cd i f f e r e n c es e t sa n dc y c l i cd i f f e r e n c es e t si n c o m b i n a t o r i a lm a t h e m a t i c s ，w ep r o p o s eam e t h o dt oc o n s t r u c tt h ep a r i t yc h e c km a t r i xo fa p a i r o fq c - l d p cc o d e sw i t ht w i s t e dr e l a t i o na n dw i t h o u tf o u r - c y c l e s ，a n dt h u so b t a i nq u a n t u m l d p cc o d e sw i t h o u tf o u r - c y c l e s c s sc o d e sc o n s t r u c t e db yt h ea b o v em e t h o da l e p r i o rt ot h o s e c o n s t r u c t e db yd u a l c o n t a i n i n gc o d e s k e y w o r d s ：l d p cc o d e s ，q c l d p cc o d e s ，q u a n t u mc o d e s ，c s sc o d e s ，p e r f e c tc y c l i cd i f f e r e n c e s e t s ，c y c l i cd i f f e r e n c es e t s 扬州人学硕：i ：学位论文 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研究成果。 除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表的研究成果。对本 文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人 承担。 学位论文作者签名：i 忆i 吃 签字日期：加i o 年f 月f7b 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关 部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。本人授权扬州大 学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文：同时授权中国科学技术信息研究所将本学位论文收录 到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 学位论文作者签名：i 协1 勺 导师签名： 前怠 签字日期： 加l 。年 月f 7e t 签字日期： 如年厂月【、e t ( 本页为学位论文末页。如论文为密件可不授权，但论文原l l j , g , 须声明。) 沈洁基于循环差集的量子l d p c 码的构造 1绪论 1 1研究意义 量子信息学是将量子力学与信息论和计算机科学相结合，以量子力学的态叠加原理及 量子子系统间量子态的纠缠性为基础，研究信息处理和计算机运算的一门新兴前沿科学。 由于量子特性在信息领域中的独特功能，使量子信息学在增大信息容量、提高运算速度、 确保信息安全等方面突破了现有传统信息系统的极限。量子信息学诞生以来已经取得举世 瞩目的成果，并显示出了十分广阔的应用前景。 量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息 的物理装置。当某个装置处理和计算的是量子信息，运行的是量子算法，并且遵循量子力 学基本规律时，它就是量子计算机。 与经典计算机不同，量子计算机可以做任意的幺正变换，在得到输出态后，进行测量 得出计算结果。因此，量子计算对经典计算作了极大的扩充，在数学形式上，经典计算可 看作是一类特殊的量子计算。量子计算机对每一个叠加分量进行变换，所有这些变换同时 完成，并按一定的概率幅叠加起来，给出结果，这种计算称作量子并行计算。因为量子并 行处理，一些利用经典计算机仅存在指数算法的问题，利用量子计算机却存在量子多项式 算法，这方面最著名的一个例子是：1 9 9 4 年s h o r 给出的关于大数因子分解的量子多项式 算法 1 2 3 。除了并行计算外，量子计算机的另一个重要用途是模拟量子系统，这项 工作是经典计算机无法胜任的。 无论是量子并行计算还是量子模拟计算，本质上都是利用了量子相干性。遗憾的是， 在实际系统中量子相干性很难保持。在量子计算机中，量子比特不是一个孤立的系统，它 会与外部环境发生相互作用，导致量子相干性的衰减，即消相干。因此，要使量子计算成 为现实，一个核心问题就是克服消相干。而量子编码是迄今发现的克服消相干最有效的方 法。主要的几种量子编码方案有：量子纠错码、量子避错码和量子防错码。量子纠错码是 经典纠错码的类比，是目前研究的最多的一类编码，在量子信息理论中占据着非常重要的 地位。 扬州大学硕：i ：学位论文 2 一 1 2研究背景 1 2 1 数字通信系统 1 9 4 8 年，在s h a n n o n 发表的著名论文通信的数学原理 4 中，他从研究通信系统的 实质出发，对信息作出了科学的定义，并进行了定性和定量的分析，在论文中给出一个统 一的通信系统模型。他的模型分为五个部分： 1 信源 信源是通信过程中产生和发送信息的设备或计算机。信源的输出是消息，消息是具体 的，但它不是信息本身，消息携带着信息，消息是信息的表达者。 2 编码器 编码器是将信号或数据进行编制，转换为可用来通讯、传输和存储的信号形式的设备。 3 信道 信道是信号的传输媒质，可分为有线信道和无线信道两类。有线信道包括明线、对称 电缆、同轴电缆及光缆等。无线信道有地波传播、短波电离层反射、超短波或微波视 距中继、人造卫星中继以及各种散射信道等。 4 译码器 译码器是一种具有“翻译”功能的逻辑电路，这种电路能将输入的二进制代码的各种状 态，按照其原意翻译成对应的输出信号。 5 信宿 信宿就是通信过程中接收和处理信息的设备或计算机。相对于信源而言的，信宿是信 息动态运行一个周期的最终环节。 上述的通信系统可以用图1 1 来表示。在本文中，我们仅考虑编码器到译码器的这两个 过程，即信道编码部分。 图1 1 ：数字通信系统的模型 为了能在有噪声的情况下传送信息，s h a n n o n i i e 明纠错码可用来保护要发送的信息， 带噪声信道编码定理给出7 g q 错码提供保护的一个上限，不幸的是，s h a n n o n 定理并没有 给出实际能够达到这个极限的一组纠错码，研究人员一直在不断推出更好类型的纠错码试 沈洁基于循环差集的量了l d p c 码的构造 3 一 图逼近s h a n n o n 定理设定的极限。复杂的纠错码理论为使用者提供了多种选择，这些码用 途广泛，可以应用在光盘播放器、计算机调制解调器、卫星通信系统等方面。 1 2 2l d p c 码 低密度奇偶校验码( l o w d e n s i t yp a r i t y - c h e c kc o d e s ) 5 6 是一类具有稀疏校验矩阵 的线性分组码，不仅有逼近s h a n n o n 限的良好性能，而且译码复杂度较低，结构灵活，是近 年信道编码领域的研究热点。 l d p c 码最早是在1 9 6 2 年由g a l l a g e r 在他的博士论文( ( l o w d e n s i t yp a r i t y - c h e c k c o d e s ) ) 5 中提出，但限于当时的技术条件，缺乏可行的译码算法，此后的3 5 年间基 本上被人们忽略。其间，t a n n e r 7 在1 9 8 1 年推广了l d p c 码并给出了l d p c 码的图表 示，即后来所称的t a n n e r 图。1 9 9 3 年b e r r o u 等人 8 发现了t u r b o 码，在此基础上，1 9 9 6 年m a c k a y 和n e a l 等人 9 儿1 0 利用随机构造的t r a i n e r 图来研究线性分组码的性能的时候 重新发现了l d p c 码，并提出了可行的译码算法，从而进一步发现了l d p c 码所具有的 良好性能，迅速引起了人们的强烈反响和极大关注。 经过十几年来的研究和发展，研究人员在各方面都取得了突破性的进展，l d p c 码的相关技术也日趋成熟，目前已广泛应用于深空通信、光纤通信、卫星数字视频和 音频广播等领域。l d p c 码已成为第四代通信系统( 4 g ) 强有力的竞争者，而基于l d p c 码的编码方案已经被下一代卫星数字视频广播标准d v b s 2 采纳。 1 2 3 量子信息 量子信息论中，信息的载体不再是经典比特，而是一个一般的二态量子体系。这二态 量子体系，可以是一个二能级的原子或离子，也可以是一自旋为1 2 的粒子或具有两个偏 振方向的光子，所有这些体系均称为量子比特。区别于经典比特，量子比特可以处于0 ，l 两个本征态的任意叠加态，而且在对量子比特的操作过程中，两态的叠加振幅可以相互干 涉，这就是所谓的量子相干性 1 1 1 2 1 3 。已经发现，在量子信息论的各个领域，包括 量子计算机、量子密码术和量子通信等，量子相干性都起着本质性的作用。可以说，量子 信息论的所有优越性都来自于量子相干性。但不幸的是，因为环境的影响，量子相干性将 不可避免地随时间指数衰减，这就是困扰整个量子信息论的消相干问题。消相干引起量子 错误，而量子编码的目的就是为了纠正或防止这些量子错误。虽然量子编码和经典编码的 基本想法类似，即要以合适的方式引进信息冗余，以提高信息的抗干扰能力，但量子码并 扬州人学顾上学位论文 4 不是经典码的简单推广。 在量子情况下，编码存在着一些基本困难 1 4 ，主要表现在如下3 个方面： ( 1 ) 经典编码中，为引入信息冗余，需要将单比特态复制到多比特上。但在量子力学 中，有个著名的量子态不可克隆定理，禁止态的复制。 ( 2 ) 经典编码在纠错时，需要进行测量，以确定错误图样。但在量子情况下，测量会 引起态坍缩，从而破坏量子相干性。 ( 3 ) 经典码中的错误只有一种，即0 ，l 之间的跃迁。而量子错误的自由度要大得多。 对于一个确定的输入态，其输出态可以是二维空间中的任意态。因此，量子错误的种类为 连续统。 由于这些原因，量子纠错要比经典纠错困难得多。事实上，直至0 1 9 9 5 年底至1 9 9 6 年， s h o r 1 5 和s t e a n e 1 6 才独立地提出了最初的两个量子纠错编码方案。量子纠错码通过一 些巧妙的措施，克服了上面提到的3 个困难，具体为： ( 1 ) 为了不违背量子态不可克隆定理，量子编码时，单比特态不是被复制为多比特的 直积态，而是编码为一个较复杂的纠缠态。对于纯态而言，纠缠态是指不能表示为直积形 式的态。通过编码为纠缠态，既引进了信息冗余，又没有违背量子力学的原理。 ( 2 ) 量子纠错在确定错误图样时，只进行部分测量。通过编码，可以使得不同的量子 错误对应于不同的正交空间，部分的量子测量( 即只对一些附加量子比特，而不是对全部比 特进行测量) 使得态投影到某一正交空间。在此正交空间中，信息位之间的量子相干性仍 被保持，同时测量的结果又给出了量子错误图样。 ( 3 ) 量子错误的种类虽然为连续统，但却可以表示为3 种基本量子错误( 对应于3 个 p a u l i 矩阵) 的线性组合。只要纠正了这3 种基本量子错误，所有的量子错误都将得到纠正。 自从发现了最初的两个量子编码方案，各种更高效的量子码就被相继地提出。 s h o r 的第一个纠错方案 i s 为量子重复码，它利用9 比特来编码l 比特信息，可以纠1 位错。s h o t 的方案简单，而且与经典重复码有较直接的类比，但它的效率不高。s t e a n t 的 编码方案 1 6 对后来的量子纠错码影响较大。在该方案中，s t e a n e 提出了互补基的概念， 给出了量子纠错一些般性的描述，并具体构造了一个利用7 比特来编码1 比特信息，纠1 位错的量子码。紧接着，c a l d c r b a n k 和s h o r 以及s t e a n e 提出了一个从经典纠错码构造量子纠 错码 1 7 1 8 的方法，该方法建立在群论语言之上，即为我们所称的c s s 码。纠1 位错的最 佳( 效率最高) 量子码也由两个小组独立地发现，该纠错方案利用5 比特来编码1 比特信息。 现有的各种量子纠错码，都可以被统一在群论框架之下，该描述已f l 习g o t t e s m a n 和c a l d e r b a n k 沈洁基于循环差集的量子l d p c 码的构造 5 一 等 1 9 2 0 给出。但利用现有的理论去构造新的量子纠错码，仍然是一件非常艰巨的工作。 由于l d p c 码突出的纠错性能，l d p c 码对应的量子l d p c 码也被广泛的研究。2 0 0 1 年 m s p o s t o l 2 1 在c s s 码基础上，利用有限几何的方法构造了量子l d p c 码。m a c k a y 等人 2 2 在2 0 0 4 年利用特殊稀疏序列提出了几种构造校验矩阵的方法，并在此基础上构造了量子 l d p c 码。t c a m a r a 等人 2 3 提出了基于l d p c 码的图的表示构造出稳定子码的方法，并且 数字仿真了码率为0 5 条件下这种量子l d p c 码在退极化信道中的性能。p t a n 和j l i 2 4 2 5 利用循环矩阵，准循环矩阵，对称矩阵和置换矩阵构造了l d p c 码的稳定子码。s a a l y 2 6 利用有限几何中的点线关系构造c s s 码。i b d j o r d j 州c 2 7 利用组合设计中的平衡不完全 区组设计( b i b d ) 来构造c s s 码。这些c s s 码的构造方法都是基于自对偶码的。而自对偶码 构造的c s s 码一定含有四环，这对采用迭代译码算法的译码收敛性是有影响的 2 2 2 3 。 m h a g i w a r a 和h i m a ie 2 8 利用一对满足扭关系的o c l d p c 码来构造c s s 码，这一构造方法 避免了四环的出现。 1 3 本文内容安排 本文对l d p c 码和量子码的构造作了研究，得到了一些结果：利用组合方法中的循环 差集，构造出不含四环且满足扭关系的一对q c l d p c 码校验矩阵，进而获得了基于c s s 码的量子l d p c 码。 本文具体内容安排如下：第二章介绍l d p c 码和量子码的概念，以及一些重要的定理。 第三章介绍了准循环l d p c 码与循环差集的定义，接着对l d p c 码和量子码的构造作了研 究，在一种基于循环差集的正则准循环l d p c 码构造方法的基础上，给出了构造一对满足 扭关系的q c l d p c 码的方法，得到基于c s s 码的量子l d p c 码。最后对全文的内容进行 总结。 扬州大学硕士学位论文 2l d p c 码和量子码 6 2 1l d p c 码 l d p c 码是一类具有稀疏校验矩阵的线性分组码，不仅有逼近s h a n n o n 限的良好性能， 而且译码复杂度较低，结构灵活 5 【6 。l d p c 码比t u r b o 码在技术上更具有优势 z 9 ，更 能适应未来系统高速速率数据传输和高性能的要求。在这一节中，将介绍l d p c 码及其 t a n n e r 图表示，围长，l d p c 码的编译码方法。 2 1 1l d p c 码的定义 l d p c 码是一类特殊的线性分组码，可以用_ 个特定的校验矩阵来定义。 定义2 1 i 二元l d p c 码的校验矩阵日要满足以下条件： ( 1 ) 日的每行有p 个“1 ； ( 2 ) 日的每列有y 个“l 一； ( 3 ) - 的任意两行( 或两列) 间共同为“1 ”的个数不超过l ； ( 4 )与码长和日中的行数相比，p 和y 很小。 定义2 1 1 中满足条件( 4 ) 的线性码就是我们所指的l d p c 码，即校验矩阵中1 的个 数远小于0 的个数。条件( 1 ) 和( 2 ) 是指校验矩阵日的行重和列重分别是p 和7 。将满足 这两个条件的l d p c 码称为( 厂，p ) 一正则l d p c 码，否则称为非正则l d p c 码。满足条件 ( 3 ) 的l d p c 码不含长度为四的块环，是一类好码。 2 1 2t a n n e r 图的表示 校验矩阵日可以对应到称为t a n n e r 图的双向二部图。如图2 1 所示，上边的节点是校 验节点，每个节点表示一个校验方程或者是校验矩阵中的一行；下边的节点是变量节点( 比 特节点) ，认为是一个码字中的一个比特或者是校验矩阵中的一列。当码字中某一比特包 含在某一校验方程中即校验矩阵相应的位为1 时，图2 1 中的上下节点之间存在连线，每 个节点相连的边数称为这个节点的度数( d e g r e e ) 。而l d p c 码有两类，一类是正则l d p c 码，其校验矩阵中具有相同的行重和列重；另一类是非正则l d p c 码，其校验矩阵中的行 沈洁基于循环差集的量予l d p c 码的构造 7 一 重和列重不相同。正则l d p c 码与非正则l d p c 码同样可以通过上下节点度数是否分别相 同来定义。 例1 设一个二元l d p c 码的校验矩阵 h = olo o1 lo ol1 10lol 1l110 可验证日的零空间定义了一个二元【5 ，1 ，4 l d p c 码，其对应的t a n n e r 图如图2 1 所示。 v 3 图2 1 u ，5 2 1 3 环及围长 一个码的好坏由其校验矩阵来确定，也就是说校验矩阵的结构对于码的性能起着决定 性的作用。而l d p c 码是用一个非常稀疏的校验矩阵来定义的，那么要设计一个好的l d p c 码，关键问题就是如何构造一个低密度校验矩阵日。 t a n n e r 图中，“环 的定义为从一个顶点出发，最后又回到同一个顶点的一些“边” 组成的回路。在环中同一边的节点不允许互连，而且除了起点和终点外，中间节点仅能出 现一次。环中边的个数称为环的“长度”，即环长。一个t a n n e r 图中最小的环长称为围长 ( g i r t h ) 。 对线性分组码而言，t a n n e r 图中不存在长度为2 或者奇数的环，所以t a n n e r 图的围长 至少是4 ，即时h 4 。 在图2 1 ( 1 ) 中h 专缸一屹专白一u 构成一个长度为4 的环。它可以表示为两个码字 比特v l ，屹同时被校验节点c 3 ，c 。进行校验。映射回校验矩阵h 即是第3 ，4 行上的第1 ，3 个 码字比特位都为“l ”，此时这两行“1 ”的重叠度为2 。而在图2 1 ( 2 ) 中屹_ c 4 专琢j c 2 扬州大学硕：i j 学位论文 y 5 一c i 一屹构成一个长度为6 的环。 c 3 c 4 v l 1 ，3 图2 1 ( 1 )图2 1 ( 2 ) v 4 y j 2 1 4l d p c 码的编译码方法 l 、l d p c 码的常用构造方法 在l d p c 码的构造中，校验矩阵日不仅决定了l d p c 编码的复杂性而且决定了l d p c 码译码的复杂性。校验矩阵的构造可以分成两个大类：随机构造和代数构造。随机构造主 要有g a l l a g e r 的最初方法，m a c k a y 的随机方法 1 0 ，p e g 算法 3 0 ，b i t - f i l l i n g 和e x t e n d e d b i t f i l l i n g 算法。虽然纠错性能好，但由于校验矩阵的随机性，编码的复杂度较高，而且需 要存储大量的数据。代数构造主要有，l i n s 3 1 提出的有限几何的方法，b v a s i e 3 2 和 b a m m a r 3 3 等人利用组合数学的均衡不完全区组设计( b i b d ) 构造了l d p c 码。由 g a l l a g e r 提出，后被t a n n n e r 3 4 和f o s s o r i e r 3 5 等人进行深入研究的具有准循环结构的 l d p c 码。 2 、l d p c 码的译码 g a l l a g e r 曾给出两种l d p c 码的迭代译码算法：硬判决和软判决算法。后者虽有好的 性能，但太复杂；消息传递算法( m p ) 可以认为是二者的折衷。在m p 译码算法中，节点到 节点的消息是通过t a n n e r 图传递的。置信传播算法( b e l i e fp r o p a g a t i o na 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 ) ，是一种迭代的概率译码方法，是逐符号软判决 译码方法。g a l l a g e r 硬判决的译码算法 6 ，也称为比特翻转算法( b i tf l i p p i n ga l g o r i t h m ) 。 这是一种基于置信传播的硬判决位翻转译码算法，仅适用于二元对称信道( b s c ) ，可以看 成置信传播算法的简化形式。 译码算法的改进和优化离不开译码性能的分析。在译码性能分析的研究方面， t j r i c h a r d s o n 等 3 6 开发了一种在码块无限长假设条件下跟踪l d p c 码t a n n e r 图中消息 概率的技术来近似估计噪声门限，提出了一种通用的方法来确定具有离散或连续输出字符 集的任何二元输入无记忆信道中采用m p 译码的l d p c 码的性能。特别对于b p 译码算法， 该方法可提供任何所需精度的性能估计。近年来，l d p c 码的很多研究成果表明l d p c 码 沈洁基于循环差集的量子l d p c 码的构造 9 一 是一种性能优异的好码。 2 2量子码 量子编码自1 9 9 6 年以来，已成为量子信息学领域最热门的课题之一，其发展速度令 人惊叹，已取得了激动人心的进展。一方面，通过量子纠错编码理论的研究成果，人们看 到了克服消相干的希望，从而使得量子计算机和量子传输可以从梦想变为现实。另一方面， 量子编码定理是s h a n n o n 定理的量子推广，具有重要的理论意义。量子编码理论的研究将 大大促进人们对量子力学和量子信息论这两门学科的理解。我们相信在2 1 世纪必将引起 一场以量子信息学为基础的信息和通信技术的革命。量子纠错编码作为量子信息学的一个 方面，其中遗留下来的问题有待进一步研究。 在这一节中，我们介绍量子码的基本知识，稳定子码和c s s 码。具体内容可以参考文 献 1 4 1 9 3 7 。 2 2 1 量子码的基本概念 量子计算机操纵的是量子位( 量子比特) 。一个量子比特说明一个单粒子能存在于0 或 1 的状态，或者同时存在于0 和1 的状态，这说明量子比特比经典比特可以表示的状态多。 而且量子叠加态允许同时进行许多运算，这就是已知的量子并行，可以很大地减少计算时 间。 与经典比特存在一个状态0 或1 一样，量子比特也有一个状态，量子比特的可能状态 是i o ) 和1 1 ) 。i g - g - i ) 是量子力学里经常用到的狄拉克( d i r a c ) 符号，表示一个状态。比特和 量子比特的区别就在于，量子比特的状态可以落在l o ) 和1 1 ) 之外，即量子比特可以是状态 的线性组合，称为叠加态( s u p e r p o s i 廿。曲。例如i 伊) = 口l o ) + 纠1 ) ，其中口和是复数，且满 足p 1 2 + 例2 = l 。换句话说，量子比特的状态是二维复向量空间c 2 中的单位向量。这里特 殊的l o ) 和1 1 ) 状态称为计算基态( c 0 m p 咖i o n a lb a s i ss t a t e ) ，是构成这个向量空间的一组正 交基。 下文中的符号c 矿指的是2 ”维复向量空间( c 2 ) 锄= c 2 p 。c 2 = c r 。 定义2 2 1 一个咒位量子态( n q u b i t ) 是指c r 中的单位向量。 取c r 的一组基 a ) 。l a i ) o i a n - i ) h f 2 = o ，1 ) ，0 5f 甩- 1 ) ，这里可以将 扬州大学硕士学位论文 l o i a o ) o l a 。) o p l a 州) 简记成l 口。口，口) 或i 口) ，其中口= ( 口o ，口i ，口纠) e 。那么任一万 位量子态眵) 都可以表示成这组基的复线性组合，即 i 缈) =c 4 。口。4 一。i a o 口口一一，) = ：c - l 口) ( 4 0 ，4 i 。口一1 ) e f f4 e f ； 其中c 叩。= c 4 c ，且满足l c 。1 2 = 1 。 定义2 2 2 一个量子码q 是指c 矽中的一个非零子空间，这里n 称为q 的码长。记k 为子 空问q 的维数( k = d i m cq ) ，k = l o g ：k ( o k ，1 ) 。 在经典情形下，码字c 和错误s 均是：；，中的向量，错误g 对码字c 的作用是相加g + c ； 而量子情形下，量子错误是作用在c 2 “上的酉线性算子( 一组标准正交基) 。s h o r 已经把问 题简化成对每个量子比特作用的情形，对于任一量子态i 罗) = 口l o ) + 1 1 ) ，量子错误算子 对于基i o ) 和1 1 ) 可表示成二阶复酉矩阵，共有四个基本的错误算子( p a u l i 矩阵) ： ，= ( 三? ) ，x = ( ：三) ，l ，= ( ；i f ) ，z = ( 三二) 。 它们对i 伊) 的作用分别是： 卅矽) = j 仁l o ) + 纠1 ) ) = 口l o ) + 纠1 ) 未发生翻转 x l 妒) = x ( 口i o ) + 1 1 ) ) = 口1 1 ) + i o ) 位翻转( b i tf l i p ) l ，1 9 ) = l ，( 口i o ) + 1 1 ) ) = f ( 口1 1 ) 一i o ) ) 位翻转加相翻转 z l 缈) = z ( 口l o ) + 1 1 ) ) = 口l o ) 一1 1 ) 相翻转( p h a s en i p ) 这些二阶酉矩阵之间的基本关系是： x 2 = i ，2 = z 2 = j ： 姗7 = i z ，l x = 一泫： 弦= i x ，z l ，= 一： z x = i y ，x z = - i 】，。 定义2 2 3 作用在c 2 4 上的量子错误算子形为e = l 五s oo8 lo os 川，其中力 0 ，l ，2 ，3 ) ， 沈洁基于循环差集的量了l d p c 码的构造 已 i , x , y , z k o j n 1 ) 。 量子错误算子e 对c 2 。的基元1 4 ) - - i 口。) 圆k ) o o l 口州) 的作用为逐位作用： e l 口) = f 五g 。a 。) ) 。g 。i 口1 ) ) 。g 。a 。一。) ) 继而作用到c 2 。的所有元素上。 定义2 2 4 设e = 童2 。q 。圆君p o ，1 ，2 ，3 , r j 口，x ，y ，z 刀一1 ) ，对于e 中的任意两个元素e = f s o 固qo 圆s 川，e = f s ：o8 ：o os ：一。，定义乘法如下： e e = f “g 。s ：) o g ，占：) 圆o g 川8 ：一。) ( 2 2 1 ) 可以得到e 是一个非交换的有限乘法群，且l e 。l = 4 肿1 。我们称e 为量子错误算子群。 由式( 2 2 1 ) 可知，对于e 中的任意两个元素e ，f ，均有e e = e e 或e e = 一e e 成立。 这里若e e = e 留成立，称e 与e 对易；若e e = 一e e 成立，称e 与e 反对易。也就是说 量子错误算子群中的任意两个元素，要么对易，要么反对易。 c a l d c r b a n k 等 1 9 给出了色的另一表示方式。将e 中的元素e = f 五s 0 _ 固8 io o 暑川 表示成e = f “。z 以) z ( 6 ) ，这里口= ( ，a l ，一。) 叼，b = 愉，1 5 i ，吃一。) 醪， ，= 撑 ，i s ，= i ，o s s ，l 一1 。即对于o ，l 一1 ，有 ( a j , 屯) = ( 0 ，0 ) 若勺= ， ( 1 ，0 ) 若s ，= x ( 1 ，1 ) 若8 = l ，。 ( 0 ，1 ) 若勺= z 引理2 2 5 ( e 3 7 ) ( 1 ) x ( 口) 和z ( 砷( 口，6 骘) 对c 2 ”的基元j d = j ) o l h ) o p i 匕q ) ( ，酵) 的作用为： x ( 口) i y ) = 1 4 + 哆，z ( 6 ) i y ) = ( - d 扣i ，) 。 ( 2 ) 对于e 中的任意两个元素e = f 名彳 ) z ( 6 ) 和e = f x ( 口7 ) z ( 6 ) ，有 e e = ( 一1 ) 和西e e 即e 和e 对易当且仅当口b 7 + 口6 = 0 。这里为孵中通常的内积。 扬州火学颂：i ：学位论文 1 2 令瓦= e 。 l ，f ) ，可验证其是一个4 ”= 2 2 n 阶群，用虿表示巨的代表元。对于瓦中 的任意两个元素豆和酽，均有历= 一e e 一，即巨中元素是相互对易的。另外，e 中的任 意一个元素豆，均有吾2 = l 。从而巨为2 ，1 个二阶循环群的直和。 定理2 2 6 ( 3 7 ) e 兰蟛” 根据定理2 2 6 可知，巨同构于嘭”的