基于Q矩阵的LDPC码编码设计方法

基于Q矩阵的LDPC码编码设计方法 基于 Q 矩阵的 LDPC 码编码设计方法 王哲 ,栾英姿 () 西安电子科技大学 ,陕西 西安 710071 摘 要 :给出了 Q 矩阵的定义 , 在此基础上提出了一种基于 Q 矩阵的 LDPC 码编码器设计方法 。此设计 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 将奇偶校验矩p d p d 阵 H 分解成两个子矩阵 H和 H, 通过对这两个子矩阵分别设计 , 构造出 H 矩阵 。其中 H 是上三角双对角矩阵 , H矩阵 由 Q 矩阵按照一定的行重列重 , 根据某种排列规则构造而成 。着重研究了 Q 排列规则 ,并找到了一种较好方法 ,使得这种 编码方案得到了很好的性能 。采用的这种编码方案的编码器算法具有较低的实现复杂度 ,为 LDPC 码编码器设计提供了 很好的选择方案 。 关键词 :LDPC 码 ;奇偶校验矩阵 ; Q 矩阵 ( ) 中图分类号 : TP301文献标识码 :A文章编号 :1673 - 629 X201006 - 0201 - 04 Design of LD PC Code Ba sed on Q - Matrix WAN G Zhe ,L UAN Ying2zi ( )Xidian U niversity , Xi’an 710071 ,China Abstract :In t his paper , t he definitio n of Q mat rix is int ro duced first , and t he designatio n of L D PC co des based o n Q mat rix is p ropo sed , p d p which is based o n Q - Mat rix . In t his met ho d , t he parit y check mat rix H is co nst ructed by t wo mat rixes : H and H , His an upper t d riangular dual diago nal mat rix , H is fo r med by Q mat rix based o n a certain p rinciple which is t he focus of t his paper , a goo d co nst ructio n d p rinciple of H is p ropo sed , which imp roves t he perfo r mances of L D PC co des. The enco der algo rit hm is easier to implement and it p ro2 vides a goo d suggestio n fo r t he enco der of L D PC co des. Key words :L D PC co de ; parit y - check mat rix ; Q - Mat rix [ 1 ] 了编码器的复杂度。 0 引言 () LDPC 码 low densit y parit y check codes是 Gallager 于 1962 提出的一种性能接近香农极限而且可以实现 1 Q - 矩阵的定义及性质1 的编码方案。在许多需要高可靠性的通信和数字存 ( 定义 :若 n × n 阶非对角单位方阵 n 为任意正整 储系统中 ,有着极其广阔的应用前景 。 ) ( 数的每行每列及每条对角线 包括斜率为正负的两 LDPC 码是 一 种 具 有 稀 疏 校 验 矩 阵 的 线 性 纠 错 [ 3 ] ) 种情况上均只有一个“1”, 则称该矩阵为 Q 矩阵。 码 。其校验矩阵的元素除了一小部分为一以外 , 其他 Q 矩阵的这种特殊结构对 LDPC 码的校验矩阵的 构成绝大多数均为零 。LDPC 码可以由其校验矩阵 H 来定 具有特殊意义 , 如果可以找到多个 n 值相同但布 [ 2 ] 义。对 LDPC 码编码器的研究主要分为两步 : 首先 , 研究校验矩阵的构造算法 , 其次 , 根据校验矩阵的结构 局不同的 Q 矩阵 , 并将它们按照一定的规则排列 , 这样来研究编码器算法 。 就可以构成准规则 LDPC 码的校验矩阵 H 。因而怎样下文介绍的基于 Q 矩阵的准规则 LDPC 码由一组 寻找 n 值一定的 Q 矩阵的布局就成为这种编码方法的 循环正交 Q 矩阵构成 , 能根据给定的码长和码率设计 重要环节 。这个问题可以由“皇后算法”解决 。 校验矩阵 H , 从而使码长和码率的取值具有更大的灵 “皇后问题”是这样描述的 :由 n ×n 个方块排成 n 活性 , 并且该类码字可以直接利用 H 矩阵编码 , 降低 行 n 列的正方形称为“n”元棋盘 。若任意两个皇后位 于 n 元棋盘上同一行 , 同一列或同一对角线 , 则称它们 互相攻击 。要求找出使 n 元棋盘上的 n 个皇后互不攻 收稿日期 :2009 - 09 - 09 ;修回日期 :2009 - 12 - 30[ 4 ] ( ) 作者简介 : 王 哲 1983 - , 女 , 硕士研究生 , 研究方向为 L D PC 码 击的布局 。由此可见 , 它与寻找 Q 矩阵的布局是等 的编译码原理 ;栾英姿 ,副教授 ,研究方向为多载波码分多址中的关 效的 。 键技术 。 下面是 n = 8 时 Q 矩阵的一种布局 。 d 0 0 0 0 1 0 0 0 ( H是由 j ×k 个 n 维 Q 矩阵按一定规则构成的其0 0 0 0 0 0 0 1 ) 中 j 是对应 LDPC 码 H 矩阵的列重 , k 为行重, 故它的 0 0 0 1 0 0 0 0 ( 维数 是 j n × k n 。对 应 LDPC 码 的 码 长 为 N = j + 1 0 0 0 0 0 0 0 ) ( ) kn , 信息位 K = k ×n , 码率为 k/ j + k。这样就可0 0 1 0 0 0 0 0 以根据码长和码率设计需要的 LDPC 码 , 具有更大的 0 0 0 0 0 1 0 0 灵活性 。 p d d p 0 1 0 0 0 0 0 0 HH由 H和 H, 构造出校验矩阵 H , H = | [ 3 , 8 ] 0 0 0 0 0 0 1 0 | , 这样 , 就由 Q 矩阵构成了 LDPC 码。将 H 矩阵对 p ( ) 4 , 7 , 5 , 3 , 1 , 6 , 8 , 2, 它所 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示的其对应的矢量为 应的码矢量 c 分解为两部分 , 分别为校验位 c和信息 p d d 是 :该列的皇后位于哪一行 , 矢量中第一个元素 4 的意 cc, 码字 c = |c| , H 与 c 的关系为 :位 p 思就是第一列的皇后位于该列的第 4 行 。 cT p d p p d d Hc = H H ] H c = 0 = H c + d 可见 , Q 矩阵的每行每列是彼此正交的 。并且可以c( ) 看出 , 由一个 Q 矩阵 , 循环左 或右移位一次 , 就可以 ppdd p p- 1 dd ( ) 二进制情况下 , Hc= Hc, c= HHc得到一种新的布局 , 从而可以得出这样的结论 :如果已 ( ) 知 n 维 Q 矩阵的一种布局 , 将其循环左移 或右移n 次 , 就可以得到皇后矩阵的 n 种布局 。并且通过证明可 3 Q 矩阵的排列方法 d 知 , 这 n 种布局彼此之间是正交的 。 H是有若干相互正交的 Q 矩阵按照一定规则排 Q 矩阵的这两种性质对于文中这种编码方案有着 列而成的 , 那么如何排列这些 Q 矩阵才能得到好的性 d 极其重要的作用 。首先 , 由于循环移位性 , 因而只需搜 能 ?规则如下 :第一 , 为了避免出现四环 , 构成 H的这 索到一种布局 , 就可以得到 n 个布局 , 当 n 达到一定大些 Q 矩阵最好是由同一个 Q 矩阵循环移位得到的 。第 小时 , 只需找到一种布局 , 就能够得到构造校验矩阵所 [ 4 ] 二 , 为了避免出现四环 , 四角的 Q 矩阵不能相同。满需的 Q 矩阵 。其次 , 这 n 个布局对应的 Q 矩阵彼此正 ( 足这两个要求的可能的排列方法有以下几种 均已行 交 , 若将这些由一种布局循环移位所得到的布局构成 ) 列重等于 6 为列 , 码长均为 576: 一个集合 , 那么由这个集合中的元素按照某种规则排 ) 1顺序排列法 :6 ×6 个 n 维 Q 矩阵按下标顺序排 列构成校验矩阵 , 可以避免出现四环 , 从而提高迭代译 列 。 码的性能 。 QQQQQQ 1 2 3 4 5 6Q 矩阵的获取可以由经典的皇后回溯算法实现 , QQQQQQ但是效率很低 , 难以满足编码的要求 。文中采用一种有 7 8 9 10 11 12 效的快速搜索算法实现 Q 矩阵布局的搜索 , 可以很好 QQQQQQ13 14 15 16 17 18 [ 5,7 ] 地满足码长的要求 , 并且具有很高的灵活性。QQQQQQ19 20 21 22 23 24 QQQQQQ25 26 27 28 29 30 QQQQQQ31 32 33 34 35 36 2 Q 矩阵构成 LD PC 码的方法按照上述方法排列 Q 矩阵得到 H 矩阵 , 仿真结果 如图 1 所示 , 可见这种排列方法性能很差 , 分析原因 , H 矩阵的结构对 LDPC 码的 性 能 具 有 极 大 的 影 可能是由于所有的 Q 矩阵都是由同一个原始的 Q 矩响 :迭代解码的性能 , 若奇偶校验矩阵中存在四环 , 迭 代解码的性能会下降 。 由 Q 矩阵构成 LDPC 码 H 矩阵的思想是将 H 矩阵 p d p HH| , 其中 H是一个 分解为两个子矩阵 : H = |d ( ) ( ) N - K×N - K的方阵 , 称为校验位矩阵 , H是 ( ) ( 一个 N - K× K 的 矩 阵 , 称 为 信 息 位 矩 阵 N 为 [ 4 ] ) LDPC 码的码长 , K 为信息位长度。p H是双对角线形式的下三角矩阵 , 具有如下形式 : 1000000 1100000 p H= 0000 110 00000 11 图 1码长 576 时四种排列方法性能对比图 阵循环移位得到的 , 相邻编号的 Q 矩阵是彼此循环一Q 矩阵得到 H 矩阵 , 性能很理按照上述方法排列 想 。这种排列方法规律性强 , 同时具备很好的性能 , 故 位得到的 , 这导致性能很差 , 应该尽量让这些 Q 矩阵 文中采用这种排列方法来生成 H 矩阵 , 实现编码器 。 分散开来 , 因而考虑到下面的第二种排列方法 。 图 1 是上文研究的四种排列方法得到的仿真图 , ) 2随机排列法 :6 ×6 个 n 维 Q 矩阵根据下标顺序由图可见 , 改进方法的性能最好 。 随机排列 。图 2 是码长分别为 576 , 1056 , 1536 和 2304 四种情 ( 这种方法用到 36 个 Q 用到 Q 的个数根据行重和 况下 , 采用改进排列方法构造 Q 矩阵 LDPC 码得到的 仿真图 , 可见码长为 2304 时 , 信噪比约为 2 . 2dB 时 , 误 ) 列重得到, 它们是在 N 一定时 , 由同一个 Q 矩阵循环 - 6 码率已达 10 。 移位产生的 。 QQQQQQ10 29 9 11 27 30 QQQQQQ17 33 24 40 46 14 QQQQQQ21 42 7 1 12 19 QQQQQQ36 38 32 43 2 6 QQQQQQ15 20 8 41 25 44 QQQQQQ35 31 26 18 3 48 按照上述方法排列 Q 矩阵得到 H 矩阵 , 性能有很 大的提高 , 可以作为一种方案 , 但是这种排列方法缺少 规律性 , 实际操作的过程中难以实现 。最好能找到一种 排列方法 , 既能保证 Q 矩阵分散开来 , 又使排列方案 有规律可循 , 因而想到下面的排列方案 。 ) 3变换公差的等差数列排列法 :6 ×6 个 n 维 Q 矩 改进法四种码长性能对比图 2图 阵根据下标顺序按等差数列排列 , 但每行的公差都不 d 综上所述 , 可得出构造 H矩阵的最佳方案 , 即先相同 。每列都以 Q开始 , 第一行的公差是 0 , 所以第一 1 找到 N 维 Q 矩阵的一种布局 , 通过循环移位 , 得到 N 行都是 Q, 第二行公差是 2 , 第三行公差是 3 , 以此类 1 [ 4 ] 种不同的布局 , 把这些 Q 矩阵按照改进的构造法就得 推 , 公差之间必须满足互为素数。 d 到信息位矩阵 H。 接下来的问题是 : 当 Q 矩阵的维数较大时 , 通过 QQQQQQ 1 1 1 1 1 1 快速搜索算法 , 可以得到多种原始 Q 矩阵 , 只需将其 QQQQQQ1 2 4 6 8 10 中的一种布局循环移位若干次 , 当维数 N 足够大时 , d QQQQQQ1 3 6 9 12 15 就可以得到构成 H所需的 Q 矩阵 。那么 , 选择哪种布 局作为原始 QQQQQQQ 矩阵进行循环移位 , 得到若干个相互正 1 5 10 15 20 25 d 交的 Q 矩阵构造 H矩阵 ?在所有 Q 矩阵中一定存在 QQQQQQ1 7 14 21 28 35 最优的原始 Q 矩阵 , 选择最优原始 Q 矩阵与否对性能 QQQQQQ1 11 22 33 44 55 影响是否会很大 ?如果是 , 那就有必要找到最优的原始 按照上述方法排列 Q 矩阵得到 H 矩阵 , 性能不是Q 矩阵 ; 如果不是 , 那么就可以使用 Q 矩阵的快速搜 特别理想 , 没有随机排列性能好 , 但是规律性比较强 。 索算法随机地找到一种布局作为原始 Q 矩阵的布局来 构成 H 矩阵 。 分析原因 , 从 尽 量 让 相 邻 的 Q 矩 阵 分 散 这 个 规 律 入 首先通过快速搜索算法 , 随机地得到四种原始 Q 手 , 上述排列法中的 Q过多 , 可能影响性能 。因此得到1 矩阵 , 分别对它们进行循环移位 , 构成 H 矩阵 , 仿真结 下面第四种排列法 。果如图 3 和图 4 所示 , 码长为 576 和 1056 。 ) 4在第三种排列方法的基础上 , 提出一种改进的 由图 3 和图 4 可见 , 当信噪比较小时 , 原始 Q 矩阵 排列方法 , 即去掉第一行和第一列元素完全相同的矩 不同的情况下 , 误码率差别很小 , 随着信噪比的增加 , 阵 Q, 排列方法如下 : 1 ( 误码率出现抖动 码长为 576 时 , 信噪比超过 2 . 5dB 时 出现 抖 动 ; 码 长 1056 时 , 信 噪 比 超 过 2dB 就 出 现 抖 QQQQQQ 2 4 6 8 10 12 ) 动。说明原始 Q 矩阵不同 , 对编码器性能有一定的影 QQQQQQ3 6 9 12 15 18 响 。码长越长 , 对抖动越敏感 。多种原始 Q 矩阵中一定 QQQQQQ5 10 15 20 25 30 QQQQQQ7 14 21 27 35 42 QQQQQQ11 22 33 44 55 66 QQQQQQ13 26 39 52 65 78 存在最优 , 如何找到最优的布局 , 还需要进一步研究 。要生成 G 矩阵 , 只需由 H 矩阵就可以进行编码 。其中d H矩阵的构成 , 即 Q 矩阵的排列规则对整个 LDPC 码 的性能有重要的影响 。通过顺序排列 、随机排列 、变换 公差的等差数列排列法 , 以及其改进排列法这四种排 列方法的对比 , 总结出了一定的排列规律并得到了较 好的性能 。文中只给出了一种相对较好的排列方案 , 如 何排列这些正交的 Q 矩阵得到最优的布局并且分析 是否最优布局对编码器性能的影响 , 是未来一个很好 的研究方向 。 参考文献 : 1 Gallager R. Low Densit y Parit y Check CodesD . Cambrid ge , MA : Massachuset t s Instit ute of Technolo gy ,1960 . 孙韶辉 , 慕建君 , 王新梅. 低密度校验码研究及其新进展 图 3 码长 576 时不同原始 Q 矩阵性能对比2 ( ) J . 西安电子科技大学学报 ,2001 ,28 3:393 - 397 . 彭 立 ,朱光喜. Q - 矩阵准规则 LDPC 码编器计方案的 3 ( ) 研究J . 计算机工程与科学 ,2005 ,27 6:81 - 82 . 彭 立 ,朱光喜. 基于 Q - 矩阵的 LDPC 码编器设计J . ( ) 4 电子学报 , 2005 ,33 10:1734 - 1739 . Sosic R , Gu J un . Fast Search Al gorit hms for t he Q - queens 5 ProblemJ . I EEE Transactions S ystem , Man , and Cybernet2 ( ) ics , 1991 ,21 6:1572 - 1576 . Sosic R , Gu J un . Efficient Local Search Conflict Mini miza 2 6 tion : A case St udy of t he n - Queens Problem J . I EEE Transactions on Knowledge and Data Engineering , 1994 , 6 ( ) 5:661 - 668 . 王 哲 ,栾英姿. N 皇后问题的快速搜索算法J . 计算机 ( ) 技术与发展 ,2009 ,19 6:72 - 75 . 7 彭 立 ,朱光喜. 不同置换矩阵对基于分块 H 矩阵的 LD2 图 4 码长 1056 时不同原始 Q 矩阵性能对比PC 码性能的影响 J . Chinese Journal of Co m p uters , 2008 , 8 ( ) 31 5:783 - 954 . 4 结束语 文中介绍的由 Q 矩阵构成 LDPC 码的方法 , 不需 () 上接第 195 页( ) 处理框架J . 计算机技术与发展 ,2009 ,19 8:74 - 79 . 7 蒋邵岗 , 谭 杰. RF ID 中间件数据处理与过滤方法的研 ( ) 究J . 计算机应用 ,2008 ,28 10:2613 - 2615 . 5 萧荣兴 , 苏伟仁 , 许育嘉. RF ID 技术运作的神经中枢 ———饶运涛 ,邹继军 , 郑勇芸. 现场总线 CAN 原理与应用技术 ( ) RF ID 中间件J . 信息与电脑 ,2005 ,19 9:35 - 37 . 8 M . 北京 :北京航空航天大学出版社 ,2007 :18 - 20 . Hoag J E , Tho mpson C W. Architectin g RF ID middleware 6 ( ) J . Internet Co m p uting ,2006 ,10 5:88 - 92 . () 上接第 200 页 ( ) 应 用 研 讨 会 SPCA06 . 中 国 新 疆 乌 鲁 木 齐 : 出 版 者 不 王 伟 , 张正兰. 基于 J 2 M E 平台的手机实时监视系统的7 详 ,2006 :306 - 310 . ( ) 设计J . 计算机技术与发展 ,2007 ,17 12:182 - 186 . 任晓 尘 ,孙 涌. 基于 J 2 M E/ J 2 EE 移动预约挂号系统的设 计与4 8 贾 雯 ,贺 栋. 面向服务的开发方式在普适计算领域中( ) 实现J . 计算机技术与发展 ,2006 ,16 12:187 - 189 . 张俊( ) 的应用J . 计算机应用与软件 ,2008 ,25 8:123 - 125 . 郭妍 ,陈启买. SOAP 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 性能与安全的研究进展J . 计 算机朝珍 ,林志虹 ,郭 昆. 协同综合预报 I GDSS 通用模型的 研5 9 ( ) 技术与发展 ,2009 ,19 6:163 - 166 . ( ) 究与应用J . 通信学报 ,2006 ,27 11:42 - 47 . 赵 阳. 基 于 Web Service 的 群 体 决 策 支 持 系 统 的 研 究 刘少林. 台风综合预报群决策支持系统的研究与实现D . D . 南京 :南京理工大学 ,2008 . 6 10 福州 :福州大学 ,2009 .