（通信与信息系统专业论文）基于循环置换矩阵构造的ldpc码.pdf

中文摘要 低密度奇偶校验 l o w d e n s 时p 撕t y c h e c k l d p c 码是一种接近香农限的 码 其译码复杂度仅随码长成线性增加 u p c 码是由其奇偶校验矩阵确定的 奇 偶校验矩阵的结构直接影响着l d p c 码的性能 根据构造方法的不同 可将l d p c 码分为随机构造型和结构构造型 而后者已然成为近年来的研究热点 本文以循 环置换矩阵 c i r 砌咖p 黜u t a t i o nm a t r i x c p m 为基础 提出了两种结构型u p c 码的构造方法 首先 基于欧氏几何 e u c l i d e 觚g e o m e h y e g 中相交于同一点的两条直线 及其交点构造出一个矩阵 然后用c p m 替换该矩阵中的域元素 可以得到一类规 则准循环 q u 嬲i c y c l i c q c l d p c 码 与周长为6 的e g l d p c 码相比 此类码 的周长至少为8 这对l d p c 码的性能提高大有裨益 同时 此类码还保留了 e g l d p c 码的准循环特性 从而可以实现较低复杂度的编码 其次 通过选择不同大小的c p m 进行适当排列 可以获得一个较大的矩阵 然后按照列重不小于3 的规则从该矩阵中提取子矩阵 作为l d p c 码的奇偶校验 矩阵 这种方法异常简单 也容易满足奇偶校验矩阵的行列约束条件 可获得行 重不同或者行重和列重都不同的非规则l d p c 码 由于c p m 的大小可以任意选择 因此得到的l d p c 码的码率和码长具有较大的选择空间 由于c p m 中1 的比例非 常小 所以通过这种方法可以构造出极其稀疏的奇偶校验矩阵 这两种方法构造出的l d p c 码的码长可以从数十到几千 甚至更长 而码率 的取值范围大约为o 2 至0 9 在a w g n 信道下的仿真结果表明 与随机构造型 的g a l l a 孵码和m a c k a y 码相比 这些码均有相当的甚至更好的误码性能 相似的 译码收敛速度和更低的的错误平台 关键词 非规则l d p c 码 循环置换矩阵 准循环l d p c 码 欧氏几何 错误平 厶 口 分类号 t n 9 1 1 a bs t r a c t l 0 w d e 璐埘p 撕妒c h e c k l d p c c o d e sa r eac l 嬲so fs h 黜0 nl i m i ta p p r o a c t l i n g c o d e s 咖rd e c o d 迦c o m p l e x i t i e sl i n e a l l y 舯ww i m 1 e i r1 饥g d l s l d p cc o d 髑躺 d e f i n e db yt i l e i rp a r i t y c h e c km 删c e s t h es t l l 比懈o ft t l e i rp a r i 妒c h e c km 痂c 豁 曲优t l ya 侬脱m e i rp e r f o m 孤c e s a c c o r d i n gt om ec o n s 仃u c t i o nm e t l l o d s u p cc o d 懿 c 趾b er o u g i l l yd i v i d e di n t ot 7 l ot y p e s r 锄d o m 锄ds m l c t i l r e d t h el a t t e rh 嬲b e c o m ea 代s e a r e hh o t s p o ti i lr e c e n ty e a r s h lt l l i sm e s i s 鲰r on e wd e s i g n 印p r o a c h 伪f 0 r c o n 咖c t i n gs 仃u 咖r e dl d p cc o d e sb a s e do nc i r c u l 锄p 锄眦l t i o nm 拥懈 c p m s h a v eb e 饥p r o p o s c d f i r 瓯am 撕xc 强b ec o n s 饥l c t e db 嬲e do n t l o i n t e r s 硎n gl i n 器锄d 蛾 m e r s e c t i n gp o i n to fe u c l i d e 觚g e o m e 时 e g n 饥ad 嬲so fr e 则盯q u 戚 c y c l i c q c l d p cc o d 锱c 距b eo b t a i n e db yr 印l a c i n ge a c h 丘e l de l 伽 l e n ti nm em a 乜奴w i ma r e l e v 锄tc p m c o m p a r e dw i m 垂m l 6e g l d p cc o d e s m e s ec o d e sh a v ea 西m lo fa t l e 嬲t8 w i l i 6 hi so f 舶a tb e n e f i tt om ei n l p r 0 v e m e n to ft l l e i rp e r f o 衄a 1 1 c 懿 f l l m l e n n o r e m e s ec o d e sp o s s e s st l l eq u 峪i c y c l i cs 协j c t l l r e s 龇1 dh e n c em e i re n c o d i i l gc o r i l p l e x i t i 铭 c a nb er e 1 u c e d s e c 0 n d l y ma r r a yc 觚b e0 b t a i n e db yp r o p 甜ya r r 趾百n gc p m so fd i 删s i z 鼯 t h e nas u b m a t r i xc 锄b ee x n a c t e d 丘o mm ea r r a ys uc ht l l a ti t sc 0 i u i i l i lw e i g h t sa r en 0 l 懿sm 觚3 t l l i ss u b m a t r i xi st a l 器t l l ep 撕妒c h e c km 撕x 啦sc o 删o nm e m o d i sv 巧s i i l l p l e 砒l di se 嬲yt 0s a 廿s 矽m er o w c o l u m nc o n s 删mo f l ep a d 妒c h e c k m 纳r i x ad 嬲so fm g u l a rl d p cc o d e s 谢n ld i 行 r c n tr o ww e i 西她o rv a r i o l l sr 0 觚d c 0 1 u i 1 nw c i g h t sc 趾b e0 b t a i l l e d 廿啪u g l l 血i sm e 1 0 d s i n c en l es i z 锱o fc p m sc 锄b e n e x i b l yc h o s e i l m e s ec o d 懿h a v eaw i d e 啪g e o fr a t 懿锄d1 c n g 吐塔 s i n c ct l l ep r o p 硎0 n o f1i i l 1 ec p mi sv e 巧s m a l l s o m ep 撕妒c h e c km a t r i c 锱c o n s 咖c t e db 嬲e do n l i s m e t h o dc 锄b ev e r ys p a r s e t h el c i l g t h so fm el d p cc o d e sc o l l s t r i l c t c db 雒c do nt l l e s et l on e wm e m o d sc 觚b e 丘o mt 吼st ot h o u s a n d s 觚d l ec o d er a t e sc a nb e 丘o mo 2t oo 9 s i 加 u l a t i o nr e s u l t s s h o wm a tm 器ec o d e sh a v es i m i l a ro re v e nb e t t e rp 耐b n n a i l c s i m i l a rf 嬲td c c o d i l l g c o n v 删es p e e d s 觚d1 0 w 盯e 仃0 rn o o f st 1 1 弛捌n d o mg a l l a g 阿觚dm a c k a y c o d 懿 k e y w o r d s m g u l a r l d p cc o d e 删a n t p 踟m n a t i o nm a 臼奴 q u 鹊i c y c l i cl d p c c o d e e u c l i d e 肌g e o m e 时 e n 0 rf 1 0 0 r c i a s s n o t n 9 1 1 致谢 本论文的工作是在我的导师张立军老师的悉心指导下完成的 张立军老师严 谨的治学态度和科学的工作方法给了我极大的帮助和影响 在此衷心感谢两年来 张立军老师对我的关心和指导 在研究工作期间 我参考了大量林舒老师曾经发表过的论文 这对我的研究 工作给予了很大的帮助 在此向林舒老师表达我的感激之情 另外也感谢我的父母 他们的理解和支持使我能够在学校专心完成我的学业 1引言 纠错编码技术是提高数字通信可靠性的主要手段之一 而低密度奇偶校验 l o w d 饥s i t yp 撕t y c h e c k l d p c 码是一种性能非常接近香农限的好码 在移 动通信 卫星通信以及信息存储等领域得到越来越广泛的应用 l o 本章首先简单地介绍了l d p c 码的概念 然后对l d p c 码的基本构造方法进 行了简要的概述 包括随机构造法和几种著名的结构性构造法 最后给出了本文 的创新内容及整体结构 1 1l d p c 码的简介 近年来 随着对高效且可靠的数据传输和存储系统需求的日益增长 纠错编 码作为设计并实现此类系统的关键技术 已成为通信领域的研究热点 l 香农在 1 9 4 8 年发表了一篇题为 a m 拙黜a t i c a lt h c o r yo f c o m m u i l i c a t i o n 的经典论文1 4 j 文章中指出 只要信息的传输速率低于信道的容量 那么通过对信息进行编码 就可以在不牺牲信息的传输或存储速率的情况下 将有噪信道或存储媒介中引入 的错误减到任意少的程度 自此 如何设计有效的编译码方法来实现纠错就成为 了设计数字通信系统和数字存储系统的核心问题之一 1 1 1l d p c 码的概念 l d p c 码由g a l l a g e r 于1 9 世纪6 0 年代首次提出 是迄今为止最接近香农限的 纠错码 5 基于置信传播迭代译码的长l d p c 码距离香农限只有o 0 0 4 5d b 2 o l d p c 码具有描述简单 易于进行理论分析 便于硬件实现等优点 在信道条件较差的 无线移动通信系统中展现出了巨大的应用前景 非常适用于未来的移动通信系统 6 因此 l d p c 码的研究 实现和应用是纠错编码领域中的一个热点课题 受到 学术界和工程界的高度重视 第四代 4 g 移动通信系统与技术是目前移动通信领域的研究热点 n 曲 码 是c b 翎 0 u 于1 9 9 3 年提出的一种并行级联码 性能非常接近香农限 已成为第三 代 3 g 移动通信系统的信道编码方案 7 1 而l d p c 码在许多场合下性能优于t i r b o 码 因此 u p c 码极有可能取代t u 曲 码而成为4 g 移动通信系统的编码方案 s 正交频分复用 o n l l o g o i l a lf r e q u 吼c yd i v i s i o nm u l t i p l 懿i n g o f d m 和多输入 多输出 m u l t i p l e h l p u t 觚dm u l t i p l e o u t p u t m i m o 技术被认为是下一代移动通信 系统的关键技术 将l d p c 码编码方案应用到o f d m m i m o 系统 能够有效地提高 编码效率和降低译码的复杂度 从而提高o f d m m m i o 系统的整体性能 l d p c 码 与o f d m m i m 0 技术相结合 能够满足下一代移动通信高速率数据大容量可靠传 输的迫切需求 6 j 目前已有很多通信标准采用了l d p c 码信道编码方案 例如 宽带无线接入协 议i e e e 8 0 2 1 6 e 无线局域网8 0 2 1 1 n 中国国家地面数字电视传输标准 以及卫星 通信标准d s 2 等都采纳了l d p c 码 另外 l d p c 码还可以广泛地应用于光通信 卫星通信 深空通信 以及光和磁记录系统等 3 由于l d p c 码具有如此良好的应用前景 所以吸引了广大学者进行深入的研 究 而如何构造出性能更好 编码实现更加容易的l d p c 码便成为了通信领域的 研究热点 1 1 2l d p c 码的表示 分组码是一种纠错码 其基本原理是将冗余符号加在信息符号后面获得码字 从而纠正信息在信道传输或媒介存储过程中可能发生的错误 在分组码中 由信 源输出的信息序列被看作是由后个信息比特组成的消息u 编码器 按照一定的规则将消息u 转换为由力个比特组成的序列v v 0 v 1 k 一 这里 刀 七 这个序列v 被称为消息u 的码字 对应于2 种不同的消息 有2 个码字组 成了一个 后 分组码 分组码的结构如下 图1 1 分组码的结构 对于一个二进制分组码来说 如果其中的任意两个码字的模2 和仍然是该分组码 中的一个码字 则这个分组码就是线性分组码p j l d p c 码是一种 刀 妫线性分组码 码长为疗 信息序列的长度为后 它被定义 为奇偶校验矩阵h 的零空间 是由h 唯一确定的 l o 1 1 这个零空间中的每一个向 量都是一个码字 且与h 的内积为o 即码字序列v 满足v h 1 0 所以被称为h 的零空间 h 是一个 刀一七 刀的矩阵 其每一行对应一个校验方程 每一列对应 码字的一个比特位 h 具有如下的结构特性 1 每一行含有p 个1 即h 的行重为p 2 每一 列含有y 个1 即h 的列重为 3 任两行或任两列位置相同的l 的个数不大于 2 1 4 与列数刀和行数所相比 列重和行重都较小 因此h 中1 的密度很小 而 h 的低密度意味着h 是一个稀疏矩阵 h 的密度 被定义为h 中1 的总数与h 中元素的总数的比值 表示如下 夕 刀 7 研 1 1 由h 的特性 1 和 2 可知 h 具有相同的行重p 和列重y 由h 的零空 间给出的l d p c 码被称为规则l d p c 码 由于h 的行不一定是线性独立的 所以要确定码字中信息位的个数 i 首先要 确定h 的秩 l d p c 码的码率r 被定义为其码字中信息位的个数七与码长刀的比值 r 后 刀 1 2 l d p c 码另有一种图形化的表示方式 被称为t a 衄e r 图表示 1 2 假设有一个长 度为刀的l d p c 码 其奇偶校验矩阵h 是由 行和栉列组成的 它的t a n n e r 图包含两 个顶点集 其中一个顶点集v 批 m 屹一 包含刀个顶点 对应着h 的刀列 代表 l d p c 码的刀个码字比特 其中每个顶点m 被称为变量节点 另一个顶点集 c c l c 一1 包含 个顶点 对应着h 的 行 代表l d p c 码的 个奇偶校验方程 其中每个顶点c 被称为校验节点 如果两个顶点被一条边所连 则称这两个顶点 相邻 在 n e r 图中 任意两个变量节点不相邻 同时任意两个校验节点也不相邻 因此 t a n n c r 图是一个二分图 其构造规则如下 当且仅当奇偶校验矩阵h 中的 办 1 时 t a n n e r 图中的变量节点m 与校验节点c 相连接 与一个顶点相连接的边的数目称为该顶点的度 对于规则l d p c 码而言 所 有变量节点的度都相同 且等于其奇偶校验矩阵的列重y 同时 所有校验节点的 度也都相同 且等于其奇偶校验矩阵的行重p 在t 锄1 e r 图中 由一组顶点和边交替组成的有限序列被称为路径 该序列中 的每一条边与其前一个顶点和后一个顶点相关联 且该序列起始和终止于同一顶 点 除此顶点外 其它任意一个顶点在序列中至多出现一次 像这样的闭合路径 被称为环 路径中边的数量被称为环的长度 环的长度一定是偶数 这是因为一 个环从变量节点 校验节点 出发 再回到变量节点 校验节点 需要经过两条 边 因此环的长度必然是2 的倍数 而最小的环的长度为4 t a l l i l e r 图中最短环的 长度被称为t a i m e r 图的周长 百n 1 1 如果奇偶校验矩阵h 中的某两行或两列包含两组位置相同的l 那么其t a m 盯 图中将形成一个长度为4 的环 因此 可以得到这样一个结论 若h 中的任意两 行或两列相同位置是l 的数目不大于l 那么其t a 皿盯图中就不包含长度为4 的 环 换句话说 就是t a 珊旧图的周长至少为6 这种对h 的行和列的限制被称为 行列约束条件 1 1 3非规则l d p c 码 非规则l d p c 码是由具有不同行重或不同列重 或同时具有不同行重和列重 的奇偶校验矩阵所确定的 其t a n n e r 图中的变量节点具有不同的度 或者校验节 点具有不同的度 或者变量节点和校验节点同时具有不同的度 非规则l d p c 码 的误码性能取决于其t a 衄盯图中变量节点和校验节点的度分布 令兄 x 为变量节 点的度分布 表示如下 以 五 x 丑矿1 1 3 其中丑代表与度为f 的变量节点相连接的边占总边数的比例 或代表变量节点的度 的最大值 令p x 为校验节点的度分布 表示如下 p x 壹岛x 卜 1 4 其中肛代表与度为f 的校验节点相连接的边占总边数的比例 以代表校验节点的度 的最大值 1 3 通过优化这两类度分布可以得到非常接近香农限的非规则l d p c 码 优化度分布的方法主要有三种 包括密度演进算法 1 4 高斯近似算法 1 5 以及外 信息转移 e x t r i n s i ch f o m a t i o nt r a i l s 向 e x i t 图 1 6 砒c h a r d s o n 等人给出了一系列非规则l d p c 码的最优度分布 但这些度分布都 是在码无限长 译码迭代次数取无限次 以及t a n n e r 图中不包含环的情况下得到 的 而且其中存在大量度为2 的变量节点 1 3 1 对于有限长度的非规则u p c 码来 说 其t a l u l e r 图中一定存在环 而且 若其t a i l i l e r 图中含有大量度为l 或2 的变 量节点 将会导致较高的错误平台 锄rf 1 0 0 r 1 7 1 引 因此 基于这些最优的度 分布构造出来的有限长非规则l d p c 码的性能往往不好 要想提高有限长非规则u p c 码的性能 并降低错误平台 可以减少度为2 的变量节点的数目或者完全去掉它们 一种办法就是把部分或者全部度为2 的变 量节点的数量转化为度为3 的变量节点的数量 若度为3 的变量节点存在的话 另一种方法就是把度分布中变量节点的每一种度都加l 也就是度2 变成度3 度 3 变成度4 依此类推 但系数保持不变 若调整了变量节点的度 也要相应地调 整校验节点的度 从而使得校验节点的度的总和与变量节点的度的总和相等 虽 然目前没有理论依据 但仿真结果表明 基于改进的度分布构造出的有限长度的 非规则u p c 码性能很好 h j 根据度分布可以求得非规则l d p c 码的码率r 若奇偶校验矩阵是满秩矩阵 即它的每一行校验方程都是线性无关的 则码率r 可以表示为如下的形式 4 跗川上竖 攀 1 掣 1 5 nn 艺t 幻艺九 f j 其中行代表码长 同时也是变量节点的数目 c 代表校验位的数目 同时也是校验 节点的数目 后代表信息位的数目 p 代表度为j 的校验节点数目占总边数的 比例 然后对校验节点的所有度进行求和 从而得到总的校验节点数目占总边数 的比例 旯 代表度为 的变量节点数目占总边数的比例 然后对变量节点的所 有度进行求和 从而得到总的变量节点数目占总边数的比例 在它们的比值中 约去了总边数 于是该式可以被理解为变量节点的数目减去校验节点的数目再除 以变量节点的数目 该式给出了非规则l d p c 码的码率r 的下界 若奇偶校验矩 阵的秩小于校验方程的数目 则码率尺大于这个式子 1 3 1 2l d p c 码的基本构造方法 由于l d p c 码是由稀疏的奇偶校验矩阵h 唯一确定的 因此码的构造就是指对 其奇偶校验矩阵h 的构造 目前为止 l d p c 码的构造方法可以分为两类 随机构造法 1 9 2 3 和结构性构造 法 2 4 1 3 引 随机l d p c 码是基于它们的t a 加e f 图的性质以及特定的设计规则通过计 算机搜索构造出来的 其中最典型的随机码包括g a l l a g e r 码和m a c k a y 码 虽然这 类码在足够长的情况下可以接近香农限 但由于缺少结构特性 它们的编码过程 十分复杂 并且很难确定其最小距离 为解决该问题 许多学者提出了结构型l d p c 码 它们通常是基于几何构造 法 2 牝刀和代数构造澍2 8 8 1 构造出来的 通常结构型u p c 码在高码率和长码长时 能够表现出优越的误码性能 某些结构型u p c 码还具有准循环结构 从而使编 码更加容易实现 但其码长和码率的设计不够灵活 只能根据自己的设计规则首 先构造出奇偶校验矩阵 然后由奇偶校验矩阵来确定l d p c 码的码长和码率 而 不能首先给出码长和码率 然后根据这些参数来设计奇偶校验矩阵 1 2 1 随机构造法 最著名的随机码主要有两种 g a l l a g c r 码 5 和m a c k a y 码 1 9 御1 它们分别是由 g a l l a g 钉和m a c k a y 提出的随机法构造出来的 g a l l a g e r 随机构造法的基本思想如下 首先按照一定的规则构造出一个 舻 5 维的子矩阵h l 其中p l 且 1 其行重为p 列重为l 对于f 0 1 一l h 的第f 行包含p 个1 且分别位于和列至g 1 p l 列的位置上 其它的子矩阵 h h h 都是通过对h 进行随机的列变换而获得的 这些子矩阵组成了具有如 下形式的奇偶校验矩阵h h h l h 2 h 1 6 h 是一个 伊维的规则奇偶校验矩阵 其行重为p 列重为厂 当7 3 且p 厂 时 此类码具有良好的距离特性 但由于其子列的变换是随机的 因此不能保证 其t 锄n e r 图中不包含长度为4 的环 m a c k a y 通过计算机仿真展示了u p c 码接近香农限的特性 并在自己的主页 上发布了大量由自己的构造方法设计出的u p c 码 2 1 1 m 咖随机构造法的基本 思想如下 在保证行重固定为p 的前提下 随机生成列重为y 的列 并且满足列重 y 尽可能地接近行重p 同时 为了保证其t a 衄e r 图中不包含长度为4 的环 任 意两列最多只包含一个共同的1 分量 由满足以上条件的若干列组成了奇偶校验 矩阵h m 栅构造法既可以用来构造规则l d p c 码 也可以用来构造非规则 l d p c 码 比较典型的随机构造法还包括逐步边增长 p r o g r e s s i v e e d g 争g r o w t l l p e g 算 法 捌和比特填充 b i t f i l l i n g b f 算法 2 3 1 通常采用这两种方法来构造非规则l d p c 码 p e g 算法的基本思想如下 根据t a n n e r 图中变量节点和校验节点的数目及其 度分布 逐步地将校验节点和变量节点用边连接起来 从而构造出l d p c 码的 m e r 图 在构造t a i l l l e r 图的过程中 由于边的选择不是唯一的 因此要通过计 算机搜索随机地选择边 在每添加一条新边时 要满足当前的t a n n e r 图具有尽可 能大的周长 构造出t 觚n e r 图以后 就可以得到对应的奇偶校验矩阵 p e g 算法 是一种尽可能增大t a 衄盯图的周长的方法 采用比特填充算法来构造奇偶校验矩阵h 是分步进行的 在每一步向已经构 造了的部分奇偶校验矩阵h 中添加一列 而且每次增加的列要满足一定的限制条 件 首先该列没有被h 选用过或被拒绝选用过 然后检查它是否与h 中的列有超 过一个的共同的1 分量 若没有 则继续进行下一步 否则不要使用该列 而重 新选择一个候选列 这是为了使t 觚n e r 图中不出现长度为4 的环 若以上两个条 件都满足 则把该列加入到h 中得到临时的部分奇偶校验矩阵 然后检查它的行 重 若行重满足规定的数量 则永久地将该列加入到h 中来 从而构造出新的部 6 分奇偶校验矩阵h 然后转到第一步继续构造过程 若行重不满足规定的数量 则拒绝使用该列 重新选择一个候选列 这个分步构造过程持续进行 直到最终 构造出具有规定数目的列的h 由于候选列是随机选取的 因此构造出的h 是不 唯一的 这种方法对于列重比较小的h 比较有效 而对于具有很大列重的h 要 使候选列满足限制条件将需要很大的计算开销 随机码的共同缺陷是编码过程较复杂 而且不利于硬件实现 1 2 2 结构性构造法 结构性构造法主要包括几何构造法 2 铊7 1 和代数构造法 2 8 0 引 其中有限域几何 是一种很强大的用来构造l d p c 码的工具 k o u l i i l 和f o s s o r i e r 第一次系统地提出了采用有限域几何构造l d p c 码的方 法 2 4 1 此类码是基于有限域几何中的点和线来进行构造的 它们具有相对较好的 最小距剐3 9 1 具有循环或准循环结构 柏l 而且其t 雒n e r 图的周长为6 4 1 1 有限域 几何l d p c 码可采用多种算法进行译码 包括大数逻辑译码 m 勾o r i t y 1 0 百c m l g 4 2 4 3 1 比特翻转译码 b i t j e i i p p i n g b f 5 1 加权比特翻转译码 w e i 出e db fd e c o d i n g w b f m 后验概率译码 ap o s t 嘶o rp r o b a b i l i 坝a p p 4 5 1 以及和积译码算法 跚m 伽d u c ta l g o r i 1 l i l s p a 2 0 巩缸4 扪 在这五种译码算法之中 和积译码算法 的误码性能最好 仿真结果表明 在a w g n 信道下采用和积译码算法进行译码 有限域几何u p c 码在高码率时能显示出优越的误码性能 但在低码率时性能恶 化 有限域几何l d p c 码可以分为两类 欧氏几何 e u c l i d e 姐g c o m e 时 e g l d p c 码与投影几何 p r o j e c t i v eg c o m e 时 p g l d p c 码 其中e g l d p c 码可以通过将 其矩阵中的每一个元素替换为循环置换矩阵 c i r 饥l 觚tp e n n u t a t i o nm a t r i x c p m 来进行扩展 从而得到一类具有良好性能和准循环结构的l d p c 码 c p m 的每一 行都是其上一行向右移一位的结果 而其首行是最后一行向右移一位的结果 而 且每一行只有一个1 分量 这种方法是一种代数构造法 被称为循环阵列扩展法 2 8 2 9 1 许多其它代数构造法都是基于它的思想演变出来的 包括基于具有2 个信 息符号的缩短r s 码构造l d p c 码 3 3 基于r s 码的最小重量码构造l d p c 码 3 4 1 基于有限域的本原元素构造u p c 码 3 5 基于有限域的加法域和乘法域构造l d p c 码 3 6 等 比较典型的代数构造法还包括基于均衡不完全区组设计构造法 3 刀 叠加 构造法 驯等 上述构造方法主要用来构造规则l d p c 码 对于非规则l d p c 码 可以采用 原模图构造法1 4 9 掩码构造法 剽 打孔构造法 2 4 行分裂和列分裂构造法阱 等来 7 进行构造 原模图 p r o t o 群l p h 构造法也是一种结构性的构造方法 可以用来构造非规 则l d p c 码p 引 原模图是一个较小的t 觚n e r 图 即具有少数个变量节点和校验节 点的t a 衄e r 图 首先对原模图复制q 次 并把同类型的节点放在一起 所谓同类 型的节点是指具有相同度的节点 然后对同类型节点的边进行置换 从而使q 个 原模图相互连接 形成一个较大的t a l l i l e r 图 该图就是原模图l d p c 码的t a 衄e r 图 假设原模图的奇偶校验矩阵用p 来表示 那么把p 中的1 元素替换为 的 置换矩阵 其中置换矩阵是相互独立的 再把0 元素替换为 的零矩阵 就可 以得到原模图l d p c 码的奇偶校验矩阵 此方法通过计算机搜索来选择原模图的 边 由于原模图的规模一般较小 所以可以降低搜索的复杂度 而且此类码的编 码过程简单 便于硬件实现 掩码构造法的基本思想如下 删 首先通过循环阵列扩展法构造出一个k g 的 c p m 阵列h 由h 的零空间给出了一类规则l d p c 码 并且可以求得它的码长和 码率 并将其作为最终要设计的l d p c 码的码长和码率 根据码率可以找到相应 的度分布 根据这个度分布通过随机法构造出一个k g 的二元域上的矩阵z 被 称为掩码矩阵 然后定义一种乘法运算 满足 m z 木h 毛 l a l l乙 2 a l 2 毛 g a l g 乞 l a 2 lz 2 2 a 2 2 乞 g a 2 叮 l a 石 i缸 2 a 置 2 讼 g a 量 g 1 7 fa 佑 z 1 锄a f 2 试 荔 z 名o 1 i n i n l c m 瓴 x 3 8 这与条件 3 7 矛盾 因此 h 的t a n n e r 图中不包含长度为4 的环 即h 满足行 列约束条件 由于x m 和 z 的值是可以任意选取的 所以能得到具有不同大小 行重和 列重的奇偶校验矩阵h 根据上述限制条件 可以构造出如下的目标奇偶校验矩阵h h a 脚a 埘 a 3 9 它是在b 的基础上取出若干连续的列而得到的 其行数 为 j 付 y 蕾 3 1 0 冒 其列数即可以在由 3 7 给出的范围内进行选择 由于a 1 朋 的列重都 是l 所以h 的列重恒定为埘 又因为h 的每行中a 的个数不同 所以它具有不 同的行重 由h 的零空间给出了一类具有不同码长和码率 且t a l l l l 盯图的周长至少为6 的非规则l d p c 码 其校验节点有多种度 而变量节点的度只有一种 由于此类 码的奇偶校验矩阵仅仅是由c p m 组成的 所以被称为非规则c p m l d p c 码 3 2 2 构造方法2 首先构造出一个基矩阵b 表示如下 b 3 1 1 它是由朋个子矩阵组成的 每个子矩阵用 来表示 h i o 而 而 而 恐 o 而 抽a i a i a j l f 肌 3 1 2 在h 中 o 代表一个零矩阵 它的角标分别为其行数和列数 a 代表一个五 而 的c p m h 中包含多少个a 是根据目标奇偶校验矩阵h 的列数进行选择的 为 了使h h h 用具有相同数目的列 h 的最后一个c p m 可能会被截去一部分 3 3 l 2 3 a a a 2 3 所 a 硝 l 2 3 啊a 加加 知 l 2 3 靠a 庶加 知 一 l 2 3 如 槲 o l 2 3 a a a 一 l 2 k a a k k o o 嘶 吨 啊a以以 以 i i f 2 3 卅 h f 日 口 列 a 代表的就是被截去某些列的不完整的c p m 另外 b 中每个c p m 的第一 行的唯一一个1 分量必须在相同位置上 从而便于满足协m e r 图中不包含长度为 4 的环 在b 中 第一个子矩阵h 包含多个完全相同的c p ma 第二个子矩阵h 中的第一个c p m 与h j 中的第二个c p m 的首列对齐 前面的部分用零矩阵 来填 充 同理 第三个子矩阵h 中的第一个c p m 与h 中的第二个c p m 的首列对齐 前面的部分用零矩阵 来填充 依此类推 最终得到b 目标奇偶校验矩阵h 的列数仍然满足限制条件 3 7 值得注意的是 b 的 前而列的列重为l 从五 1 到而列的列重为2 由于h 中存在列重为1 或2 的列 会影响非规则l d p c 码的性能 因此要除去b 中的前而 而列 同时 为了满足h 的列数疗的限制条件 需要从如下的范围内选择b 中连续的列来构造h 毛 砭 c 毋坦l c m 而 x 五 屯 3 1 3 芎 其中c 代表h 中的列序号 根据上述限制条件 可以构造出如下的奇偶校验矩阵h a ja la l a 2a 2a 2 a 3 a 3 o 而a 4 a 4 ji o 而 o k 3 1 4 它是在b 的基础上取出若干连续的列并去掉了前五 而列而得到的 其行数 为 j 行 而 3 1 5 f 皇l 其列数以可以在由 3 7 给出的范围内进行选择 由于h 的前几列c p m 中包含 不同数目和不同大小的零矩阵o 所以h 具有不同的列重 又因为h 的每行中a 的个数不同 所以它也具有不同的行重 由h 的零空间也给出了一类具有不同码长和码率 且t a l l l l e r 图的周长至少为 6 的非规则c p m l d p c 码 但是其变量节点和校验节点同时具有不同的度 3 3码族列表 表格3 1 给出了一系列通过上述两种构造方法构造出的具有不同码长 码率和 度分布的非规则c p m l d p c 码 6 0 0 3 0 2 码的奇偶校验矩阵是基于三行c p m 构造出来的 其中每行c p m 的 大小从上到下依次为 5 1 5 1 7 5 7 5 2 0 0 2 0 0 它们可以对齐排列 也可以错 l 2 3 4 n从 毒乱 a 觑加 位排列 当三行c p m 进行错位排列时 前面列重为1 或2 的列均被删除 只保留 了后面列重为3 的列 因此 无论采用何种排列方式 其奇偶校验矩阵的列重恒 定为3 且同时具有四种行重 分别为3 8 1 1 和1 2 密度为o 0 0 9 2 4 5 9 2 8 2 码是将四行c p m 进行错位排列而构造出来的 而 4 5 9 2 8 3 码是将同 一组c p m 进行对齐排列而构造出来的 9 9 9 2 9 1 1 2 0 0 4 9 2 1 5 0 0 7 9 2 和 1 8 3 6 1 1 2 8 码的奇偶校验矩阵都是基于同 一组c p m 并采用错位排列方式构造出来的 但是由于截取的列数不同 所以码长 和码率不同 剩下几个非规则c p m l d p c 码的奇偶校验矩阵都是通过错位排列方式来进行 构造的 但采用了不同组的c p m 当每组中不同c p m 的大小取互质数或其倍数 时 可以构造出相对较长的非规则c p m l d p c 码 当每组中不同c p m 的大小取 连续的互质数或其倍数时 构造出的非规则c p m l d p c 码的码率相对较高 另外 当c p m 的大小取值较大时 此类码的奇偶校验矩阵的密度较低 表格3 1一系列具有不同码长 码率和度分布的非规则c p m l d p c 码 x码参数行重列重码率密度 5 l 7 5 2 0 0 6 0 0 3 0 2 3 8 l l 1 2 3o 5 0 30 0 0 9 2 0 2 7 5 0 5 1 5 3 4 5 9 2 8 2 7 8 9 1 0 1 7 3 4o 6 1 4o 0 2 1 4 8 2 7 5 0 5 1 5 3 4 5 9 2 8 3 8 9 l o 1 7 4 0 6 1 6o 0 2 2 l o 1 0 8 2 0 0 2 0 4 2 1 2 9 9 9 2 91 3 4 5 9 1 0 3 4 0 2 9 l0 0 0 5 2 4 1 0 8 2 0 0 2 0 4 2 1 2 1 2 0 0 4 9 2 4 5 6 1 1 1 23 4 0 4 l o0 0 0 5 2 9 1 0 8 2 0 0 2 0 4 2 1 2 1 5 0 0 7 9 2 6 7 8 1 3 1 43 4 0 5 2 8o 0 0 5 3 4 1 0 8 2 0 0 2 0 4 2 1 2 1 8 3 6 1 1 2 8 7 8 9 1 0 1 73 4 0 6 1 40 0 0 5 3 7 1 2 6 3 0 0 3 0 6 3 1 8 2 1 4 2 1 1 1 6 5 6 7 8 1 73 4 0 5 2 1o 0 0 3 6 7 2 7 5 0 5l 5 3 5 7 5 9 4 5 9 1 6 2 5 6 7 8 93 4 5 6 o 3 5 3o 0 1 5 8 7 1 0 8 2 0 0 2 0 4 2 1 2 2 2 8 2 3 6 18 3 6 6 6 4 5 6 7 8 9 l o 1 73 4 5 6 0 3 6 2o 0 0 4 4 7 1 0 4 1 0 8 l1 6 2 1 2 6 7 8 9 1 0 1 7 2 2 8 2 3 6 2 0 5 2 1 0 5 2 1 8 1 9 3 4 5 6 0 5 1 30 0 0 5 4 0 5 1 5 2 5 3 5 5 5 9 9 1 0 1 l 1 2 1 3 6 l 6 7 7 l 1 0 0 0 5 3 1 1 4 1 5 3 4 5 6 7 8 o 5 3 lo o l l 5 8 5 1 5 3 6 l 1 0 4 1 0 8 1 1 1 5 0 0 5 4 3 3 4 5 1 0 1 1 1 2 1 3 6 2 2 8 2 3 6 1 4 1 7 1 8 1 9 2 0 3 4 5 6 7 8 0 3 6 20 0 0 6 3 7 3 5 3 4仿真结果与分析 本节将通过仿真结果对非规则c p m l d p c 码的误码性能进行分析 所有的仿 真结果都是在a w g n 信道下经过b p s k 调制 并采用s p a 进行译码而得到的 其 最大迭代次数设为1 0 0 在不同信噪比下 每次仿真至少统计到1 0 0 个错误比特 下面给出了四个例子 分别对高码率短码 低码率短码 高码率长码和低码率长 码进行性能分析 例3 1 令朋 4 x 2 7 5 0 5 1 5 3 那么使t a n n e r 图中不包含长度为4 的环的条件是刀 4 5 9 和7 7 c 5 3 6 在这里取刀 4 5 9 从形式如 3 5 的基矩阵b 中取出1 到4 5 9 列 从而构造出一个1 8 l 4 5 9 的奇偶校验矩阵h 形式如 3 9 由 h 的零空间给出了一个码长为4 5 9 码率为o 6 1 6 的 4 5 9 2 8 3 非规则c p m u p c 码 其度分布为 名 x 石3 厦幻 0 0 9 呀7 o 7 0 蚜8 0 0 5 仉矿 0 1 4 蚜1 6 其变量节点的度为4 而校验节点有4 种度 分别是8 9 l o 和1 7 将它的性能 与一个具有相同码长但码率为o 6 0 6 的 4 5 9 2 7 8 m a c k a y 码做比较 2 1 1 m a c k a y 码的 奇偶校验矩阵的平均行重和列重分别为9 和3 5 通常对于码长相同的两个码来说 码率较低的码性能较好 虽然图3 1 显示在b e r 达到1 0 西以前 c p m l d p c 码的 性能比m a c k a y 码略差 但是c p m u p c 码的码率却比m a c k a y 码略高 因此可 以认为这两个码在b e r 达到1 0 币以前具有相似的误码性能 同时 m a c k a y 码在 b e r 达到1 旷左右开始出现错误平台 而c p m l i p c 码直到b e r 达到1 0 7 仍然 没有出现错误平台 因此 c p m l d p c 码具有比m a c k a y 码更低的错误平台 从形式如 3 1 1 的基矩阵b 中取出7 7 到5 3 6 列 从而构造出一个1 8 1 4 5 9 的 奇偶校验矩阵h 形式如 3 1 4 由h 的零空间给出了一个码长为4 5 9 码率为o 6 1 4 的 4 5 9 2 8 2 非规则c p m l d p c 码 其度分布为 五 x o 1 儿l j 2 0 8 8 8 9 x 3 厦z o 0 8 8 4 x 6 o 2 0 4 4 r 7 o 5 0 8 3 矿 0 0 4 9 7 j 矿 o 1 4 9 2 x 1 6 其变量节点有两种度 分别是3 和4 校验节点有5 种度 分别是7 8 9 l o 和 1 7 该码与 4 5 9 2 7 8 m a c k a y 码相比 码长相同 码率略高 而图3 1 显示出该码 的性能比m a c k a y 码略好 而且 m a c k a y 码在b e r 达到1 0 6 左右开始出现错误平 台 而 4 5 9 2 8 2 码直到b e r 达到1 7 仍然没有出现错误平台 因此 4 5 9 2 8 2 码 具有比m a c k a y 码更低的错误平台 叱 山 图3 1 4 5 9 2 8 2 非规则c p m u p c 码 4 5 9 2 8 3 非规则c p m l d p c 码 和 4 5 9 2 7 8 m a c k a y 码的误码性能 下面将这两个非规则c p m u p c 码做比较 虽然它们具有相同的码长和近似 的码率 但是 4 5 9 2 8 2 码的性能略优于 4 5 9 2 8 3 码 因此 当变量节点和校 验节点同时具有多种度时 非规则c p m l i p c 码的误码性能更好 例3 2 令m 6 x 2 7 5 0 5 1 5 3 5 7 5 9 那么使t a l l l l e r 图中不包 含长度为4 的环的条件是刀 4 5 9 和7 7 c 5 3 6 在这里取刀 4 5 9 从形式如 3 5 的基矩阵b 中取出1 到4 5 9 列 从而构造出一个2 9 7 4 5 9 的奇偶校验矩阵h 形 式如 3 9 由h 的零空间给出了一个长为4 5 9 码率为o 3 7 3 的 4 5 9 1 7 1 非规则 c p m u p c 码 其度分布为 名 z z 5 反柳 o 0 0 4 4 x 6 o