（通信与信息系统专业论文）qcldpc码的编码构造.pdf

中国科学技术大学硕士论文摘要 摘要 低密度奇偶校验( l o w d e n s i t yp a r i t y c h e c k ，l d p c ) 码是一种先进的信道 编码技术，它具有逼近香农限的纠错性能。准循环低密度奇偶校验码( q u a s i 。 c y c l i cl o w d e n s i t yp a r i t y c h e c k ，q c l d p c ) 码是l d p c 码的一个重要子类，它 的校验矩阵具有准循环形式，这种结构特征决定了其较低的编解码复杂度。 q c l d p c 码的主要构造方法包括有限几何法，均衡不完全区组设计法和三 维立方体网格图法：其中，三维立方体网格图法作为一种特殊的均衡不完全区 组设计方法，可以使构造出的码字达到g i r t h 值为1 0 。q c l d p c 码的g i r t h 值和 环分布是影响码字性能的重要因素。q c l d p c 码的生成矩阵也具有准循环形 式，这决定了它可以利用移位寄存器进行编码。双对角线结构的q c l d p c 码 可以由校验矩阵直接生成码字，因此能实现简单快速编码。 自适应调制编码要求可变码长、码率的q c l d p c 码，这也是本文的重点 研究内容。通过分析q c l d p c 码校验矩阵中的环，作者推导了一个定理和一 个推论，并基于此设计了两种q c l d p c 码的压缩构造算法，包括递推压缩算 法和单步压缩算法，这两种方法可以生成码长连续变化、码率可选的码字。为 了使双对角线结构的q c - l d p c 码能够实现码率灵活变化，作者对一穿刺算法 进行了改进，改进后的算法实时性更高、运算复杂度更低且性能损失很小。除 了压缩算法和穿刺算法以外，作者讲述了一种行合并算法，该方法在实现码率 变化的同时保持码长不变。 l d p c 码的应用领域主要包括现代通信系统和存储系统，除此以外，作者 重点介绍了l d p c 码在量子通信系统中的应用，包括两种可行的构造方法：均 衡不完全区组设计法和有限几何法，以及在应用中存在的问题和可能的解决方 案。 作者最后提出了l d p c 码方面一些有意义的研究点，包括高阶域、与其它 编码技术的联合、系统实现和跨学科应用。 第1 页共6 2 页 中国科学技术大学硕士论文摘要 关键词：低密度奇偶校验码，准循环，双对角线结构，环，最短环长，压缩， 穿刺，码长可变，码率可变，量子低密度码 第页共6 2 页 中国科学技术大学硕士论文a b s t r a c t 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 sa r eo n ek i n do fe r r o rc o n t r o lc o d e s ， w h o s ep e r f o r m a n c ec a nb en e a rs h a n n o nl i m i t q u a s i - c y c l i cl o w - d e n s i t yp a r i t y - c h e c k ( q c l d p c ) c o d e sa r eo n ek i n do fl d p cc o d e s ，w h o s ep a r i t y c h e c km a t r i c e s a r ew i t hq u a s i - c y c l i cs t y l e ，s ot h e i re n c o d i n gc o m p l e x i t ya n dd e c o d i n gc o m p l e x i t ya r e l o w m a j o rm e t h o d sf o r t h ec o n s t r u c t i o no fq c l d p cc o d e si n c l u d ef i n i t eg e o m e t r y ， b a l a n c e di n c o m p l e t eb l o c kd e s i g na n d3 dl a t t i c e 3 dl a t t i c ei so n ek i n do fb a l a n c e d i n c o m p l e t eb l o c kd e s i g n s ，w h i c hc a ng e tc o d e s w i t hg i r t h10 g i r t ha n dc y c l e so fq c l d p cc o d e sa r ei m p o r t a n tf a c t o r s ，w h i c hc a na f f e c tp e r f o r m a n c eg r e a t l y g e n e r a t o r m a t r i c e so fq c - l d p cc o d e sa r ew i t hq u a s i c y c l i cs t y l et o o ，w h i c hm e a n st h ec o d e s c a nb ee n c o d e dw i t hs h i f tr e g i s t e r q c l d p cc o d e sw i t hd u a l d i a g o n a l p a r i t y s t r u c t u r ed on o th a v et og e tg e n e r a t o rm a t r i c e s ，s ot h e yc a np e r f o r mf a s te n c o d i n g a d a p t i v em o d u l a t i o na n de n c o d i n gn e e dl e n g t h - - c o m p a t i b l ea n dr a t e - c o m p a t i b l e q c l d p cc o d e s b ya n a l y z i n gc y c l e so fq c l d p cc o d e s ，t h ew r i t e rd e d u c e sa t h e o r e ma n dad e d u c t i o n ，a n dd e s i g n st w oc o m p r e s s i n gm e t h o d sb a s e do l lt h e m 1 1 1 e m e t h o d si n c l u d er e c u r s i v e - c o m p r e s s i n ga n ds i n g l e - c o m p r e s s i n g ，w h i c hc a ng e n e r a t e c o d e sw i t hc o n t i n u o u sl e n g t h f o rt h er e a l i z a t i o no fs t r u c t u r e dp u n c t u r i n gf o rr a t e - c o m p a t i b l eq c - l d p c c o d e s 、】 r i t hd u a l d i a g o n a lp a r i t ys t r u c t u r e ，t h ew r i t e ra m e l i o r a t e s am e t h o d ，t h ea d v a n c e dm e t h o dc a nb em o r er e a l - t i m ew i t hl o w e ro p e r a t i o n c o m p l e x i t yt h a nt h eo r i g i n a lm e t h o d b e s i d e st h em e t h o d sa b o v e ，t h ew r i t e ri n t r o d u c e s ar o w - c o m b i n i n gm e t h o d ，w h i c hc a ng e n e r a t ec o d e sw i t hc o m p a t i b l er a t ea n dc o n s t a n t l e n g t h l d p cc o d e sc a nb eu s e di nt h ea r e ao fm o d e mc o m m u n i c a t i o ns y s t e m sa n d m e m o r ys y s t e m s a n da l s o ，t h ew r i t e ri n t r o d u c e st h ea p p l i c a t i o no fl d p cc o d e si n q u a n t u mc o m m u n i c a t i o ns y s t e m s ，i n c l u d i n gt w om e t h o d st od e s i g nc o d e s ，b a l a n c e d i n c o m p l e t eb l o c kd e s i g na n df i n i t eg e o m e t r y t h e nt h ew r i t e rd i s c u s s e st h ep r o b l e m s a n dp r o b a b l es o l u t i o n sf o rl d p cc o d e su s e di nq u a n t u mc o m m u n i c a t i o ns y s t e m s a tl a s t ，t h ew r i t e ri n t r o d u c e ss o m ei m p o r t a n tp o i n t so fl d p cc o d e st h a ta r ew o r t h s t u d y i n gi nt h ef u t u r e ，i n c l u d i n gn o n b i n a r yl d p cc o d e s ，c o m b i n i n gw i t ho t h e re r r o r c o n t r o lc o d e s ，t h er e a l i z a t i o ni nas y s t e ma n dt h ea p p l i c a t i o ni no t h e rs u b je c t s 第1 i i 页共6 2 页 中国科学技术大学硕士论文a b s t r a c t k e yw o r d s ：l d p cc o d e s ，q u a s i c y c l i c ，d u a l - d i a g o n a lp a r i t ys t r u c t u r e ，c y c l e s ，g i r t h ， c o m p r e s s i n g ，p u n c t u r i n g ，l e n g t h c o m p a t i b l e ，r a t e c o m p a t i b l e ，q u a n t u ml d p cc o d e s 第1 v 页共6 2 页 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含 任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本 研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名：到：壶堕 2 0 0 7 年6 月了日 中国科学技术大学硕士论文第1 章绪论 第1 章绪论 1 1信道编码技术及其应用 近年来，信道编码技术在移动通信系统和存储系统中得到了广泛的应用。 典型的移动通信系统或存储系统如图1 1 所示。 图1 1 典型的移动通信系统或存储系统框图 为了消除信道中的噪声影响，实现信息的高效可靠传输，需要引入信道编 码技术。1 9 4 8 年，香农在文献【1 】中证明，只要信息传输数率低于信道容量，通 过对信息进行适当编码，就可以在不降低信息传输速率的情况下，将由噪声引 入的差错减到任意少。具体的结论是，每个信道都有一个信道容量c ，对任意 满足r 2 时，我们可以得到m 维第一类循环e g l d p c 码，其校验矩阵为 场 日2 ： h r ( 2 - 6 ) 其中k = 卅疗= ( 2 ( 川b 一1 ) ( 2 5 1 ) 。 有限几何法构造的准循环码具有较大的最小码距，可以消除误码平台：由 于校验矩阵具有较大的列重和行重( 每个比特参与较多的校验方程，每个校验 方程包含较多比特) ，在和积译码算法的每次迭代中，存在较多其它码比特对 该比特的信息计算提供帮助，所阶i 1 鲁厅匕h 获得很好的误码性能。 2 2 2均衡不完全区组设计法 均衡不完全区组设计( b i b d ) 是组合设计的一个子类，它可以用来构造 q c l d p c 码。本文简要介绍一下b o s e 构造的一类特殊的b i b d 3 7 。 令t 是满足2 0 t + i = p m 的一个正整数，其中p 是一个素数：对于具有 q ：2 0 t + 1 个元素的集合x ，存在一个b i b d ，它有，z = t ( 2 0 t + 1 ) 个区组，每个区组 由y ：5 个元素组成，每两个元素恰好在a = 1 个区组中出现；用g f ( p m ) 的元素 o ，1 ，口，口z ，口，一z 来表示集合x 的q 个元素；x 的b i b d 由f 个基础区组完全确定 届= 口甜，o f 2 1 + 4 o f 2 j + g t ) 口2 1 + 1 2 ts 口甜+ 1 研l ( 2 - 7 ) 其中0 i f ；b i b d 的所有区组可以通过将g f ( p m ) 中的每个元素逐个加到这f 个 基础区组上得到。事实上，我们利用这些区组可以得到循环形式的校验矩阵 风啪；对于0 i f ，令形为基础区组尽的关联向量，它是一个p m 维向量，在 第1 2 页共6 2 页 中国科学技术大学硕士论文第2 章l d p c 码的基本原理 2 f ，2 f + 4 f ，2 f + 8 t ，2 i + 1 2 f ，2 f + 1 6 f 位置上的元素为l ，其余位置上的元素为0 ；令g 为 将形循环移位2 0 r 次得到的( 2 0 t + 1 ) x ( 2 0 t + 1 ) 矩阵，g 的所有列是2 0 f + 1 个不同区 组的关联向量，即有h b t s o = 【g og 1 g f 1 1 。这样，我们就得到了一个准循环 b i b d l d p c 码，码长为刀= t ( 2 0 t + 1 ) ，列重为5 ，行重为5 ，。 均衡不完全区组设计容易构造出高码率的码字，这可以有效提高系统的频 谱效率和信息传输速率。 2 2 3三维立方体网格图法 当我们把均衡不完全区组设计的一个条件放宽时，即改为任意两个元素至 多在1 个区组中出现，可以构造出一类特殊的准循环b i b d l d p c 码，它们往 往具有较大的g i r t h 值；在利用和积算法译码时，可以保证交互信息的有效性； 三维立方体网格图法( 3 dl a t t i c e ) 就是通过这一思路引申出来的。结合文献 【1 9 】，本文对此做下简单介绍。 在笛卡尔坐标系内，沿x 轴方向取c 个点、沿y 轴方向取r 个点、沿z 轴 方向取q 个点，构造一个含有q r x c 个点的三维立方体网格图；对网格图内 的所有点进行编号：沿y 轴的方向对c q 平面编号，在一个c q 平面内沿x 轴 的方向对平行于z 轴的直线编号，在每一条直线上沿z 轴的方向对点编号；在 顶面即c r 平面上构造循环的直线，使得每条直线都经过c r 平面上的c 个 点：分别以y 轴上的r 个点为起点，依次选取斜率为o ，l ，r - 1 ，构造尺z 条 直线；构造r ：个平行于z 轴的平面，使得每个平面与顶面的交线分别是顶面上 的一条直线；在每个平面内分别构造q 条循环平行线，对于其中的任一平面， 把平行线的斜率记为如，平行线的起点的z 坐标分别是o ，l ，q 1 ，起点的 x 坐标为0 ，酩按照如下方法确定：如果该平面沿z 轴在顶面上的投影所得到 的直线的起点的y 坐标为y ，斜率为s t ，那么有 = ( y + 尺) ( y + c ) + ( 墨+ r ) ( 岛+ c ) ；r ：个平面上一共有鲫z 条循环平行线；然 后，构造一个q r c 行，鲫：列的全零矩阵，把构造出来的鲫2 条循环平行线和矩 阵的列对应起来，然后根据每一条直线经过的点的编号把矩阵每- - y u 中对应位 置的元素置为1 ，生成的矩阵被称为均衡不完全区组设计的点块矩阵，将它作 为l d p c 码的校验矩阵。 第1 3 页共6 2 页 中国科学技术大学硕士论文 第2 章l d p c 码的基本原理 三维立方体网格图法构造的q c l d p c 码的g i r t h 值可以达到1 0 ，并且具有 较好的环分布，我们知道l d p c 码的最小码距与g i r t h 值之间的关系为 靠i 。 + 矗 u 1 m ，+ 矗卜m t 卜，降j 其中g 表示g i r t h 值，表示列重。综合考虑上述因素，我们知道三维立方体网 格图法构造的o c - l d p c 码具有优越的纠错性能。 2 3 o c l d p c 码的编码过程 q c l d p c 码相比早期的l d p c 码，一个很重要的优势就在于它的准循环结 构特性，这决定了它具有更低的编解码复杂度，也就更利于硬件实现。结合文 献【1 5 】，本文对q c l d p c 码的编码过程做下简单介绍。 我们将一个q c l d p c 码的校验矩阵表示为 h q c = 4 ，t4 ，z 4 。t4 ，z 4 。4 。2 ( 2 9 ) 其中的每个循环子矩阵4 ，都是b 阶的，假定该矩阵的秩为6 c ，并且假定由其得 到的矩阵d 的秩也是施，矩阵d 为 d = 然后我们可以得到生成矩阵 g 口c = g l g 2 ： g k a 1 r f + l 4 + l 4 ，m 4 f _ m 第1 4 页共6 2 页 ( 2 1 0 ) ( 2 1 1 ) 趵 d 玎 甜 嘲 甜 吖 远 b 2 2 胆 俚 研 w 订 行 j j j 4 4 ；4 j j j 4 4 ；4 ， ， 叩 q q ；q o o 。f 西西；“i j ，p q q ；q d d ；， d ，；d，d ；d 中国科学技术大学硕士论文第2 章l d p c 码的基本原理 其中i 是b 阶单位阵，o 是全零矩阵，g ! f 是循环子矩阵：令彰，表示g ：f 的第 ( 疗+ 1 ) 行，0 ，z _ b - 1 ，a = ( a t ，a 2 9 0 1 1 口( 心砧) 表示待编码的信息序列，我们可以 把信息序列表示成口= ( 彳，正，石k ) ) 的形式，其中z = ( 口( 一灿，q m 2 ，) ； 这样我们可以生成码字 ，= a g q c ，由于q 是系统循环形式，所以 v = ( 口，p i ，p 2 ，见) ，其中p j 可以表示为 乃= 彳g l ，+ 石g 2 ，j + + z 一。g f 嵋 ( 2 - 1 2 ) 其中有 z g f = q j - 1 ) 6 + l 或+ 口( h ) 6 + 2 础+ + a 1 6 9 ( ，b ，- ( 2 13 ) 即p ，可由移位寄存器和加法器构成的循环移位累加器生成。 综上所述，q c l d p c 码可以利用简单的移位寄存器进行编码，即可以实现 基于生成器的线性编码。 2 4 q c l d p c 码的性能影响因素 度数分布、环分布以及列重、行重都是影响q c l d p c 码性能的重要因 素，在此我们重点分析环分布。通过对文献 3 8 】的总结，我们可以了解到q c l d p c 码的校验矩阵中环的形成原因，并以此为依据，优化其中的环分布，从 而提升q c l d p c 码的性能。 为了方便讲述，我们首先引入几个概念。我们将一个q c l d p c 码的校验 矩阵表示为h ，不失一般性，假定h 中的非零循环子矩阵均由单位阵移位得 到；将日中的全零矩阵用0 取代，其它循环子矩阵用1 取代，得到一个小矩阵 m ( ) ，我们称之为日的母矩阵；对于各个非零循环子矩阵，用其相比单位阵 的移位位数来取代，全零矩阵用o o 来取代，这样我们得到一个小矩阵s ( ) ，称 之为日的位移矩阵。如果在母矩阵m ( ) 中存在一个长2 ，的环，根据该环经过l 元素的位置，可以提取位移矩阵s ( ) 中相同位置的元素，按提取顺序将这些元 素组成一个有序集合( 轧，翰) 。 定理2 1 1 3 8 ：由m ( h ) 中一长2 l 的环可确定有序集合( 民，s ：，s ：，) ，如果，是 满足 第1 5 页共6 2 页 中国科学技术大学硕士论文第2 章l d p c 码的基本原理 2 ， ，( 一1 ) 7 s ，- 0 m o dt ( 2 1 4 ) j = l 的最小正整数，那么日中存在长2 ，的环，其中r 表示日中循环子矩阵的大小。 该定理表明，日中的各个环是由其母矩阵m ( ) 中的环决定的。根据该定 理，我们可以通过优化母矩阵和位移矩阵中的元素取值来提高校验矩阵的g i r t h 值并减少短环数目，从而提升码字性能。 第1 6 页共6 2 页 中国科学技术大学硕十论文 第3 章q c l d p c 码的简单快速编码方法 第3 章q c l d p c 码的简单快速编码方法 一般的q c l d p c 码的编码复杂度比普通的l d p c 码要小很多，但我们仍然 需要由校验矩阵得到生成矩阵，进而生成码字；因此，我们需要在系统中同时 存储校验矩阵和生成矩阵，这无疑增加了存储负担，并且编码复杂度也较大。 通过优化q c l d p c 码的结构，我们可以在不损失性能或损失很小的情况下， 实现线性编码复杂度，即复杂度与码长成正比，并减少存储量；利用优化后的 结构可以通过递推运算生成码字，运算复杂度很低且不需要生成矩阵。 h e 和w i m a x 协议均给出了优化结构，结合文献 2 1 ，2 3 ，本文对这两种结构 分别做下简要介绍与分析。 3 1双对角线矩阵重构技术 h e 利用了双对角线矩阵重构技术来构造q c l d p c 码的校验矩阵，该方法 可以实现简单快速编码，且码字具有非常优越的纠错性能。 3 1 1基本原理 我们最初采用的校验矩阵为 = 只怫 ( 3 1 ) l ，jj 其中有 和 4 , = h p = h i ，1 凰“t h j 。i h 、。l j 。h j - l j h j 。l j dd ： ： h j 一1 。l - j 。i h j 一1 ，l 2 ii ( q 一1 、) h j ? l j 。l hj ? 2 i i 第1 7 页共6 2 页 ( 3 - 2 ) ( 3 - 3 ) 中国科学技术人学硕十论文 第3 章q c l d p c 码的简单快速编码方法 且h j 暑，( c j ，) 表示将单位阵，循环移c j f 位，校验矩阵中各个循环子矩阵的大 小为g ；值得注意的是，日，中i ( q - 1 ) 的第一行中没有l 元素，这对下面将要进 行的矩阵重构非常重要。下面我们以一个简单的例子介绍一下矩阵重构技术， 一个简单的校验矩阵h 为 h = i 二7l p 4 ， 其中的循环子矩阵为4 阶，( 3 ) 的第一行中没有1 元素。通过将h 的前4 行置 于新矩阵风的奇数行，将后4 行置于风的偶数行；将风的前4 列置于新矩阵 凰的奇数列，将后4 列置于吼的偶数列，这样我们可以将凰重构为 - 2 = ( 3 - 5 ) 同理，对h 采取如下操作：针对日p 中最后两行的循环子矩阵，将前q 行置 于奇数行，将后g 行置于偶数行；针对h p 中最后两列的循环子矩阵，将前g 列 置于奇数列，将后g 列置于偶数列：这样我们可以得到新矩阵比，它右边是双 对角线结构，这是实现简单快速编码的关键。 3 1 2编码过程 我们利用巩进行编码，定义y 为生成的码字，那么有 玩y 7 = 0 r ( 3 - 6 ) 将码字j ，分为( 1 ) 个部分，即少= ( “，p i ，一，p j ) ，其中u 表示系统部分，易 包含q 比特。通过公式( 3 6 ) 并且结合巩和日的关系，可以计算出 f 一，一l 所( f ) = 毋，i u ( a j 3 d ) + 白，i 仇( 以卜，叱，) ( 3 7 ) k = lk = l 其中，1 j q ，l j f j 一2 ；并且有 第1 8 页共6 2 页 中国科学技术大学硕十论文 第3 章q c l d p c 码的简单快速编码方法 和 ：诋n訾“蚂，)(3-8)gj,k 2 1ow h e n 乩产o a j ，= ”q ，】。+ q ( k - 1 ) b j 小_ 【f + q , l - j + k 】。+ q ( k - 1 ) 其中【x 】。表示x 对q 求模。另外有 力1 ( f ) = v ( i ) + 加一l ( f 1 ) 乃( f ) = v ( i + q ) + p j ( i - 1 ) 其中有p s 一。( 0 ) = 0 和矽，( 0 ) = p j 一1 ( q ) ，并且有 v ( 2 f 一1 ) = g j - l t 甜( 乃一眠。) + g s l 七仇( 幻- l 一，叱。) 七= l七= l l jj - 2 v ( 2 0 = g 似u ( a j f ) + g 肌p , ( b j 卜m ) 3 1 3结构分析 ( 3 9 ) ( 3 一l o ) ( 3 - 1 1 ) ( 3 1 2 ) ( 3 1 3 ) ( 3 1 4 ) 双对角线矩阵重构方法能够得到双对角线形式的校验矩阵，显然可以实现 简单快速编码；同时，通过优化重构前矩阵的度数分布和循环子矩阵的移位位 数，可以得到非常优越的纠错性能。但是，由于要进行矩阵重构，破坏了整个 矩阵的准循环形式，在计算最后两部分的校验比特时，除了简单利用移位寄存 器与累加器以外，还需要引入行交换机制，这势必会引入运算复杂度与延迟。 并且由于重构后的矩阵不具备完全准循环形式，解码复杂度会相应提高。 3 2双对角线结构 w i m a x 协议中给出了一种含双对角线结构的q c - l d p c 码，可以实现简单 快速编码。 第1 9 页共6 2 页 中国科学技术大学硕士论文 第3 章q c l d p c 码的简单快速编码方法 3 2 1 基本原理 由于w i m a x 协议中给出的校验矩阵为文献【3 8 】中情形的特例，所以我们先 简单介绍一下文献 3 8 】中的码字，其校验矩阵为 并且有 和 = ( 以) 巩。砘i ( h ，) 巩。地 j p q 。p 2 尸吒1 胪， p p h j j p i ，o oo 0l 胪，oo ；i oj p oo ，= 【0 ih 门= ip i ； ； ；i ；，d oi oo 尸， p qi oo o 矿” ( 3 一1 5 ) ( 3 - 1 6 ) ( 3 - 1 7 ) 其中除了第一列和双对角线上的位置以外，其余位置上都是全零阵，循环子矩 阵大小为z ，p p 位于第，行、通常是第m b 2 行，为了实现简单快速编码，需要 有口= ( 芝6 j ) r o o dz 和p = ( 一芝包) m o dz 成立。在w i m a x 协议中，将其简化为b l = g 、 p = o 和6 2 = 岛= = k 一。= 0 。我们以一个码率为1 2 的码字为例，其校验矩阵为日， 相应的位移矩阵为 19 47 3 17o 1 12 7 - l 1 2 - l0 0 00 o 4 37 ( 3 - 1 8 ) 其中1 代表全零子矩阵，其他元素表示该循环子矩阵的移位位数，矩阵大小为 第2 0 页共6 2 页 “ “ 汕 肌眠；队 中国科学技术大学硕士论文 第3 章q c l d p c 码的简单快速编码方法 3 2 2编码过程 对于公式( 3 1 8 ) 对应的校验矩阵日，将其划分为公式( 3 1 5 ) 的形式，即 h - 以i d ，利用它，并且通过递推运算，我们可以将信息序列生成码字。把 生成码字y 的系统部分和校验部分以子矩阵大小为单位分组，并将其分别称为 而和g ，根据1 4 y7 1 = 0 7 1 ，有 以i h ，屯，x t 2 】7 + 尸7x 0 + c ；= 0 7 且2 x x j ，z 2 ， 2 】7 + + = o r ； 只，【西，屯，而2 】r + + = 0 7 皿。h ，x 2 ，2 】r + 0 + + 西= o r( 3 1 9 ) 以7 h ，x 2 ，j 1 2 】7 + 西+ i = 0 7 i 以i lx t x , ，而，x 1 2 】7 + + c 五= 0 7 且1 2x x i ，x 2 ，而2 1 7 + p 7x 0 + = 0 7 其中玑，表示几的第f 行循环子矩阵，将各个公式相加可得c 。，通过递推运算 可以得到其余的校验部分，这样就完成了编码过程。 3 2 3结构分析 w i m a x 协议给出的校验矩阵中的双对角线形式是实现简单、快速编码的关 键，相比h e 的方法，它不需要进行矩阵重构；在性能方面，由于该校验矩阵的 最d , n 重为2 ，有效避免了列重为l 的情况，并且由于矩阵风的度数分布是经 优化过的，所以构造出的不规则码具有非常优越的纠错性能。但该双对角线结 构也决定了三种环的存在，这在一定程度上会影响码字的性能，具体请参考文 献【3 8 】。 第2 l 页共6 2 页 中国科学技术大学硕士论文 第4 章可变码长、码率的q c l d p c 码 第4 章可变码长、码率的q c l d p c 码 对q c l d p c 码的研究已经开展了很长时间，无论在纠错性能还是在编解 码复杂度方面，均取得了突破性的进展，可以说我们已经掌握了构造优秀q c l d p c 码的方法：但是，在实际的通信系统和存储系统中，通常需要可变码 长、码率的q c l d p c 码序列，以自适应系统的需求，这要求我们统筹考虑码 序列的纠错性能、编解码复杂度和存储等因素。如何设计可变码长、码率的优 秀q c l d p c 码是本文的一个重点研究方向。 4 1自适应调制编码技术对编码的要求 自适应调制编码可以增强数据传输的可靠性并提高频带利用率，其基本思 想是：在接收端估计信道，然后将估计结果反馈到发送端，发送端根据信道的 特性进行适当的调整：发送端可以调整的参数很多，主要包括数据速率、功 率、编码、误码率以及它们的组合，本文主要从编码角度进行讲述。出于复杂 度或峰均功率比等方面的考虑，有时我们必须要固定调制方式，自适应编码技 术非常适合于这种情况。 自适应编码利用不同的码字对传输比特提供不同的编码增益，当信道增益 较小时，使用纠错能力强的编码，而当信道增益较大时，使用纠错能力较弱的 编码或者不进行编码。 自适应编码的一种实现方式是设计并存储多个不同纠错能力的编码，不同 信道条件时连接到不同的编码器，这种方法需要在码字长度内信道状况大致不 变。 实现自适应编码的另一种方法是采用码率兼容的码字，它们是基于同一套 编码器和译码器的一族不同码率的码字；通过对低码率的码字进行穿刺，可以 得到可变码长、码率的码序列，穿刺的意思就是不发送编码结果中的某些比 特：通过穿刺可以控制码的纠错能力。该方法的优势是不同码率的码字都使用 同一套编码器和译码器，只要在发送端执行适当的穿刺操作就可以达到所需要 的差错保护能力。 第2 3 页共6 2 页 中国科学技术大学硕十论文 第4 章可变码长、码率的q c l d p c 码 4 2具体可行的方法 在使用q c l d p c 码的通信系统中，为了实现自适应编码，需要设计可变 码长、码率的码字。具体可行的方法主要有两种，一种是采用校验矩阵变换的 方式，另一种是采用穿刺的方式。 校验矩阵变换的方法：早期是在一些相互没有关联的校验矩阵之间变换； 这样的好处是每一个校验矩阵都分别通过精心设计得到，在满足码长、码率的 条件下，能获得优越的纠错性能和较低的编解码复杂度；但缺点也是显而易见 的，每一个校验矩阵都要单独进行存储，大大加重了系统的存储负担，这样整 个系统中并不能提供很多备选矩阵。目前常用的方法是，提供一个基础矩阵， 其余的校验矩阵都可以通过基础矩阵简单生成，这样大大减轻了存储负担。如 何简单生成，并使各个校验矩阵得到的码字性能优越，成为了一个值得研究的 课题；作者基于这些方面的考虑，提出了两个压缩算法。这些方法既保证了系 统中存在大量备选码字，又保持了码字的良好性能。 穿刺的方法：该方法只需要一套编码器和解码器，对编码后的码字穿刺掉 若干比特，即可实现码长、码率可变的目的，简单灵活；通过合理设计穿刺图 案，可以使生成的码字具有优越的性能。在统筹考虑减小系统延时和运算复杂 度的基础上，作者提出了一种改进穿刺算法。穿刺方法也存在一个缺点，由于 穿刺不可避免使码长变短，这样势必影响纠错性能，本文简要介绍一种码率可 变、码长不变的方法作为对比。 4 3q c l d p c 码的压缩构造 如果l d p c 码具有较高的g i r t h 值和较少的短环数，我们称它具有良好的环 路特性。通过对码字结构进行分析，作者提出了一类压缩算法来构造环路特性 优异的q c l d p c 码，即首先选定一个g i r t h 值较大的码字作为基准码，然后对 它进行压缩，最后对生成码字的环路特性进行优化。这类算法只需要存储若干 个基准码的信息和其它很少量的算法信息，即可在较大的码长变化范围内，连 续生成一些码字，从而大大节省了存储空间。 我们简要介绍一下将要用到的符号，h 表示基准码的校验矩阵，旭劢表示 日的母矩阵，义肋表示日的位移矩阵，即其元素蜀为各循环子矩阵的移位位 第2 4 页共6 2 页 中国科学技术大学硕士论文 第4 章可变码长、码率的q c l d p c 码 数，各个循环子矩阵的大小为，；h 表示将要生成码字( 我们称其为子码) 的 校验矩阵，m ( h ) 表示h 的母矩阵，并且有m ( ) = 肘( 日) ，s ( h ) 表示的 位移矩阵，其中的元素可表示为，q 表示压缩比，日中各个循环子矩阵的大 小为。 通过推导，我们可以得到一个定理和一个推论。 定理4 1 ：假设位移矩阵。义奶( 对应于g i r t h 值为2 l 的基准码日) 中任一有 限元素品，有鹕为整数，并且s ( h ) = q s ( h ) ，则有日的g i r t h 值也为2 l ，且 对于各种长度的环，日中的数目皆为日中的q 倍。 证明：假设中有一长2 1 r 的环，它是由有序集合( _ ，s ：，) 确定的，由 定理2 1 可知 2 ， ，( 一1 ) 。q s , - 0 m o dq t ( 4 - 1 ) i = 1 有序集合( s 1 , 5 2 ，s ：，) 确定了日中t 个长2 1 r 的环，并且由该集合可确定母矩阵 撇功中一个长2 f 的环，因为m ( h ) = m ( ) ，所以可确定有序集合 ( s ：，s ；，) ，由它确定h7 中的若干个环；假设环的起点位于循环子矩阵的第 _ ，行，( 1 ，2 ，q t ) 。由于= q s j ，所以有 2 ， j f 三- + r ( 一1 ) q s m o dq t ( 4 - 2 ) t = l 成立，即 2 j 暑+ ，( 一1 ) r o o dq t ( 4 - 3 ) j = l 成立。根据的取值范围，( 1 ，2 ，q t ) ，可知共有砂个长2 肛的环。 推论4 1 ：q c l d p c 码的校验矩阵中各种长度环的数目都是循环子矩阵大 小的整数倍。 证明：由定理2 1 可知，日中任一长2 r 的环可确定其对应的有序集合，该 有序集合可以确定中的f 个长2 r 的环，推论得证。 推论4 1 可以作为检验矩阵中环数目检测结果对错的基本条件。当定理4 1 的条件得到满足时，通过压缩，我们可以产生与基准码g i r t h 值相同且环更少的 第2 5 页共6 2 页 中国科学技术大学硕士论文 第4 章可变码长、码率的q c l d p c 码 子码；基于此，我们设计了两个有效的压缩算法来构造可变码长的q c l d p c 码。 4 3 1两个压缩算法 两个压缩算法分别是递推压缩算法和单步压缩算法，下面我们分别讲述它 们的步骤。 递推压缩算法： 1 ) 定义凰为基准码的校验矩阵，选择一个压缩比( g ) ，利用日7 表示将要生 成子码的校验矩阵，并且有m ( h ) = m ( h o ) 。 2 ) 定义一个q c l d p c 码的校验矩阵为h ，且有m ( q ) = m ( 风) ，胃和h 大 小相同；定义彤为s ( q ) 中的元素，对于s ( 凰) 中的元素而，令= f g 而 ， 这样我们可以得到h i ；当帆为非整数时，记录该下标( j ，j ) ；检测并记 录h 的g i r t h 值和最短环数目。 3 ) 定义另一个q c l d p c 码的校验矩阵为h e ，面为s ( 心) 中的元素，并且 m ( h ：) = m ( h o ) ，凰与片大小相同；对于s ( h o ) 中的元素勘，令 = iq s 盯l ，这样我们可以得到h 2 ；检测并记录h z 的g i r t h 值和最短环数 目。 4 ) 比较h 和日：的环路特性( g i r t h 值和最短环数目) ，如果凰表现更好 ( g i r t h 值大或最短环数目少) ，转到第5 步，反之，转到第6 步。 5 ) 根据第2 步中记录的一个下标( i ，j ) ，将减1 ，这样我们可以根据 s ( h ) 得到相应的校验矩阵日“检测h i 的坏路特性，将其与h 。的结果进行 比较，如果叫更优，则利用该环路特性将目的结果更新，否则，将s ：恢 复原状；继续根据下一个下标重复这一过程，直到记录的所有下标都被用 过，转到第7 步。 6 ) 根据第2 步中记录的一个下标( f ，歹) ，将s ；加1 ，这样我们可以根据 s ( 以) 得到相应的校验矩阵成；检测删的环路特性，将其与吼的结果进 行比较，如果叫更优，则利用该环路特性将皿的结果更新，否则，将 恢复原状；继续根据下一个下标重复这一过程，直到记录的所有下标都被 用过，转到第7 步。 第2 6 页共6 2 页 中国科学技术大学硕士论文 第4 章可变码艮、码率的o c l d p c 码 7 ) 生成的s ( q ) 或s ( 以) 作为s ( h ) ，这样我们就得到了日，即产生了一个子 码。 8 ) 利用第7 步中产生的子码作为基准码，选择一个压缩比，重复整个的过程 作为下一步递推，这样我们可以得到新的子码。 单步压缩算法： 1 ) 7 ) 与递推压缩算法中的1 ) 7 ) 相同。 8 ) 仍然使用相同的基准码，更新压缩比，重复整个过程，这样我们可以得到 新的子码。 4 3 2压缩算法的性能与存储分析 根据公式( 2 8 ) ，我们了解到码字的最小距离与g i r t h 值的关系，即g i r t h 值越 大，最小码距越大；并且环，特别是短环的存在，会降低迭代解码的性能。由 于压缩算法可以确保产生的码字具有较高的g i r t h 值，并能有效控制短环的数 目，所以具有优异的纠错性能。 如果我们在系统中需要利用一系列的码字，按照一般的方法，通常会存储 所有码字的校验矩阵，这无疑加重了存储负担；采用压缩算法，我们可以大大 减小存储空间。对于递推压缩算法，我们需要存储以下信息：基准码的母矩阵 和位移矩阵，每一步递推中的压缩比、相应的压缩类型( 采用s ( h ) 或 s ( 皿) ) ；另外，在每一步递推中，若或需要更新，则存储相应的下标信 息。对于单步压缩算法，需要存储的信息与递推压缩算法类似，我们不再进行 详细描述。 我们可以利用一个基准码和这两个压缩算法来产生一系列可变码长的q c l d p c 码，并且不需要单独存储每个码字。当产生的码字数目很多时，可以很 明显的减小存储空间。 我们采用两种不同码率的o c l d p c 码作为基准码，并结合压缩算法，可 以实现码长、码率可变；这两种基准码分别是码率0 4 的3 dl a t t i c e 码和码率0 5 的w i m a x 协议码。我们对产生的码字进行了性能仿真。 第2 7 页共6 2 页 中国科学技术大学硕十论文 第4 章可变码长、码率的q