基于MATLAB的仿真与研究

目目 录录 摘 要 1 1 绪论 3 1 1 无线通信发展状况 3 1 2 LDPC 发展动态 5 1 3 本论文的主要工作 5 2 LDPC 码的原理 5 3 LDPC 码校验矩阵构造 6 3 1 校验矩阵的随机构造 7 3 2 校验矩阵的结构化构造 9 4 LDPC 码的编码 11 4 1 密集编码 11 4 2 LU 分解 11 4 3 高斯消去 12 4 4 LDPC 码的有效编码 12 5 LDPC 码的译码 14 5 1 BP 译码 14 5 2 降低复杂度的 BP 译码 16 6 运用 MATLAB 对 LDPC 码仿真 20 6 1 不同码长对 LDPC 码的影响 20 6 2 不同迭代次数对 LDPC 码的影响 20 6 3 不同列重对 LDPC 码的影响 21 6 4 本章小结 22 结论 22 参考文献 23 致谢 24 淮南师范学院 2012 届本科毕业论文1 基于基于 MATLABMATLAB 的的 LDPCLDPC 码的仿真与研究码的仿真与研究 学生 陈诚 指导教师 王千春 淮南师范学院电气信息工程学院 摘摘 要要 随着无线通信技术的发展和各种传输方式对可靠性要求的不断提高 信道编码作为抗干扰技 术的重要手段之一 在数字通信技术领域和数字传输领域显示出越来越重要的作用 目前 3G 和 4G 无线通信系统的信道编码的主流技术是 Turbo 码 其具有接近香农极限的优异性能 但是在码长较 长的情况下 其误码性能还有待于提高 LDPC 码是一种线性分组码 和 Turbo 码同属于复合码类 两者的性能相近 且两者的译码延迟都很长 其适用一些实时性要求不是很高的通信 但是在码长 较长的情况下 LDPC 码比 Turbo 码的译码性能更高而且在误码率上 在硬件应用和应用方面 LDPC 具有更大的优点 本课题主要研究 LDPC 码在不同条件下的误码率 译码算法和应用上相比其他编 解码技术的优点 为 B3G 和 4G 无线通信系统的信道编码提供理论依据 本论文所做工作如下 本文 阐述了 LDPC 码的基本原理和分析 LDPC 码关键技术及影响性能的因素 对 LDPC 码进行编码在 MATLAB 软件的环境下进行仿真 在仿真的图像上进行性能的分析 运用仿真的图像对 LDPC 和 Turbo 在误码率上进行分析比较 在研究 LDPC 码基本理论的基础上 利用 MATLAB 仿真比较不同码长 列重 和迭代次数对 LDPC 码性能的影响 为 B3G 和 4G 移动通信提供了有利的参考价值 关键词关键词 LDPC 码 MATLAB 仿真 Research and Simulation of LDPC code Based on MATLAB Student Chen cheng Teacher Wang qian chun Electronic And Information Engineering Department Of Huainan Normal University Abstract Along with the wireless communication technology development and all kinds of transmission 基于 MATLAB 的 LDPC 码的仿真与研究2 way to improve the reliability requirements channel coding as one of the important methods anti interference technology in digital communication technology field and digital transmission field shows that more and more important role Current 3 G and 4 G wireless communication system of channel coding technology is the mainstream of Turbo yards it has the close to shannon the excellent properties of the limit but in yards long long its error performance needs improving LDPC code is a linear space time block codes and Turbo yards with belong to the compound of code Both similar performance and both decoding delay are very long it is some real time requirement of communication is not very high But in the code length is longer LDPC code than Turbo decoding yards in the ber performance and higher application and application in the hardware has more advantages of LDPC This topic research LDPC code in different conditions ber decoding algorithm and application compared with the other decoding technology advantages for three G3G and 4 G wireless communication system provides the theory basis for the channel coding This paper work are as follows this paper expounds the basic principle and LDPC code analysis LDPC code key technology and influence factors of performance the LDPC code in the MATLAB software code under the environment of the simulation the simulation of the image in the performance analysis In the study of the basic theory of LDPC code based on the use of computer simulation code length and all heavy and iteration Number of B3G LDPC code affect performance and 4G mobile communication provides favorable reference value Key words LDPC code MATLAB simulati 淮南师范学院 2012 届本科毕业论文3 1 绪论 21 世纪是一个信息化的时代 信息的传输即通信起着支撑的作用 随着科学技术的 发展 人们对通信的要求与日俱增 世界各国都在致力于现代通信技术的研究与开发 无线通信是现代通信系统的重要组成部分 经过专家和学者的努力 在过去几十 年中 无线通信已经取得了很大程度上的进步 但是现代社会的发展是更加迅速的 这就对无线通信提出了进一步的要求 不仅要高速率的传输数据 而且要高质量的传 输数据 为了满足这种高速率和高质量的传输需求 本文提出了一种新的编码调制技 术 1 1 无线通信发展状况 古时 千里眼 顺风耳 表达了人们对通信特别是远距离通信的向往 19 世纪末 马可尼无线通信实验的电报声宣布了一个新时代的到来 二十世纪是无线通信发展的 黄金时期 40 年代无线通信理论得到了长远的发展 可捷尔尼可夫和香农为无线通信 理论的发展做出了卓越的贡献 近 20 年 无线通信的发展经过了三代 1978 年底 美国贝尔实验室研发了高级移动电话系统 AMPS Advanced Mobile Phone Service 建成了模拟蜂窝语音通信系统 诞生了第一代无线通信系统 同时 其他国家也研发出采用频分多址 FDMA Frequency Division Multiple Access 方式的 模拟蜂窝无线通信系统 包括以美国 AMPS 英国 TACS Total Access Communication System 北欧 NMT450 900 等 二十世纪八十年代 进入了数字通信的时代 欧洲率先研发出了全球移动通信系 统 GSM Global System for Mobile Communication 日本和美国也研发了自己的标 准 二十世纪九十年代 美国推出了窄带码分多址 CDMA Code Division Multiple Access 数字蜂窝无线通信系统 这也就是目前正普遍使用的无线通信系统 即第二 1 代无线通信系统 第二代无线通信系统主要支持语音和低速率的数据业务 当今世界 的第二代数字无线标准 包括 GSM D AMPS JDC Japan Digital Cellular 和 IS 95CDMA 等 仍然是窄带系统 现有的无线通信网络主要以 GSM 和 CDMA 为主 采 用 GSM GPRS CDMA 的 IS 95B 技术 速率可达 115 2kbit s 全球移动通信系统 GSM 采用增强型数据速率 EDGE 技术 速率可达 384kbit s 随着人们的物质和文化水平的提高 对无线通信业务的需求日益增多 这种现存 基于 MATLAB 的 LDPC 码的仿真与研究4 的无线通信网难以满足新的需求 为适应新的需求 第三代 3G 3rd Generation 无 线通信系统成为技术发展的必然 3G 于 1985 年由国际电信联盟 ITU International Telecommunication Union 提出 目前 被世界公认的主流标准为 欧洲和日本提出的 WCDMA 北美的 CDMA2000 和中国的 TD SCDMA 方案 虽然 3G 在通信容量和质 量上较 2G 有了较大的提高 但是其核心技术没有发生革命性的变化 所以 3G 可看作 是 2G 向未来无限通信系统发展的一个过渡 随着时代的发展 人们已经提出了 B3G 乃至 4G 无线通信系统 该系统有着不可 替代的优点 不仅进一步提高了系统的容量和数据的传输质量 而且可实现数据的高 速率和高质量传输 B3G 和 4G 系统涵盖了现有的 3G 和 3G 增强型技术以及新的移动 接入和本地接入系统 在各种技术中 正交频分复用 OFDM 技术受到了极大的关 注 B3G 蜂窝移动通信系统需要具备以下能力 1 支持全 IP 高速分组数据传输 数据速率可高达数百 Mbit s 2 支持高传输质量 传输数据的误码率低于 6 10 3 提供高的频谱利用率和功率效率 发射功率降低 10dB 以上 4 支持高终端移动性 移动速度高达几百 km h 5 能够支持在用户数据速率 用户容量 服务质量和移动速度等方面大范围的 动态变化 为满足这些技术上的需求 B3G 移动通信系统必须在系统理论 网络结构和关键 技术等方面具有突破性的改变 具体为 1 在网络结构方面 将采用全 IP 分布式 自组织和多层的无线广带个人通信 新体制和新模式 以对抗 2G 以上电波传输特性的挑战 并适应未来移动通信以数据业 务为主的需求 2 2 在传输体制方面 传统的单载波时分多址技术和码分多址技术很难直接推广 到广带传输 必须采用多载波并行传输体制 而设计高度灵活的多载波传输方案是设 计 B3G 移动通信系统的一个关键 3 在编码与调制技术方面 将采用新型的自适应编码调制技术 而包括其在内 的 高效的自适应链路技术则是 B3G 移动通信的另一个关键技术 4 在空中接口方面 将采用分布式的接入方式 多天线环境下多输入多输出 淮南师范学院 2012 届本科毕业论文5 MIMO 无线通信系统的理论将突破传统的无线通信系统理论 成为未来移动与无 线通信系统理论的核心 5 在天线与射频技术方面 将采用新型的多天线和阵列天线技术以及宽高线性 度射频技术 1 2 LDPC 发展动态 在 20 世纪 60 年代 Gallager在他的博士论文中提出了低密度分组校验码 3 LDPC Low Density Parity Check Code 也称为 Gallager 码 是校验矩阵稀疏的线性 分组纠错码 经数十年的沉寂 随着计算机能力的增强和相关理论的发展 Mackay 和 Neal 重新发现了它 并证明它在与基于 BP Belief Propagation 的迭代译码相结合的 条件下具有逼近 Shannon 极限的性能 LDPC 的重新发现是继 Turbo 码后纠错编码领域 又一重大进展 LDPC 码的特点是 性能优于 Turbo 码 灵活性大 译码复杂度低于 Turbo 码 可以完全并行操作 硬件复杂度较低 所以硬件易于实现 描述简单 对严 格的理论分析具有可验证性 吞吐量很大 能够高速译码 经过大量实验表明 AWGN 信道下 码长足够长时码率为 1 2 的非正则 LDPC 码可达到距离香农限 0 13dB LDPC 码在数据可靠传输中的良好应用前景引起了学术界和 IT 业界的高度重视 4 成为现今信道编码领域最受瞩目的研究热点之一 下一代数字卫星视频广播标准 DVB S2 已经采纳了基于 LDPC 码的编码方案 在第四代通信系统 LDPC 码将得到广泛的应 用 1 3 本论文的主要工作 本论文做了如下工作 对数字通信与差错控制编码的基本理论进行了概述 介绍 了 LDPC 码的历史与发展 并对 LDPC 码的编译码算法的研究现状进行阐述了其在各 个方面的应用 介绍了 LDPC 码的编解码的设计和译码的算法 重点运用 matlab 软件 对其 LDPC 码码长 列重和迭代次数进行仿真 1 应用matlab软件针对规则LDPC码码长分别为300 500和1000 列重选择 2 应用matlab软件针对码长为500 译码的最大迭代次数为20 校验矩阵每列的 列重分别为2 3和4情况下进行了仿真实验 3 应用matlab 软件针对码长500 的规则LDPC码 列重为2 译码迭代次数分别为 10 20和40的情况下进行了仿真实验 4 对LDPC码和Turbo码在误码的性能上进行仿真并且进行系统的分析 基于 MATLAB 的 LDPC 码的仿真与研究6 2 LDPC 码的原理 LDPC 码是一种非常特殊的线性分组纠错码 通过生成矩阵 G 可以将线性分组纠 5 错码要发送的信息 s 转换成被传输的码字 t 与 G 对应的是校验矩阵 H 满足 H t 0 LDPC 码校验矩阵中非 0 元素的个数远远小于 0 元素的个数 是稀疏矩阵 LDPC 码可以分为规则 Regular 码和非规则 Irregular 码两种 二者的主要区 别在于它们的校验矩阵的行和列权重是否变化 假设 LDPC 码的校验矩阵 H 是 M N 维 而且满秩 则 LDPC 码长为 N 校验位为 M 信息位则为 k M N 码率 r k N H 矩阵中每行 1 的个数为行权重 每列中 1 的个数为列权重 H 矩阵可 以用二部图 Tanner 图 来表示 如图 1 所示 下边的 N 个节点代表 N 个码字 称为 信息节点 Message Node 或比特节点 Bit Node 上边的 M 个节点代表 M 个校验 式 称为校验节点 Check Node 当矩阵中元素时 信息节点 n 和校验节点1 mn H m 就可以通过对应的边 Edge 连接起来 连接两个节点的边称为这两个节点的相邻 边 相互连接的两个节点称为相邻节点 和每个节点连接的边的数量称为该节点的度 Degree 对于规则 LDPC 码 校验矩阵 H 中行权重和列权重都是固定不变的 6 在二部图上 信息节点和校验节点的度都分别为固定值 我们用 N j k 来表示 其中 N 为码长 j 为校验矩阵的列权重 k 为行权重 对于非规则 LDPC 码 其 Tanner 图中上 下任一个节点的度数都不是固定值 分别占上 下总度数的一定比例 i 规则码是非规则码的一个特例 i n个比特节点 m个校验节点 图图 1 1 校验矩阵对应的校验矩阵对应的 TannerTanner 图图 3 LDPC 码校验矩阵构造 在介绍 LDPC 码校验矩阵的构造之前 首先阐述一下什么是 girth 图 2 中 粗线部 分构成了长度为 6 的环 二部图中最短环的环长称为该图的 girth girth 是构造校验矩 淮南师范学院 2012 届本科毕业论文7 阵的非常重要的指标 二部图中 girth 的值越大 校验矩阵的性能就越好 一般要求 girth 最小为 6 v1 c1 v3v2v4v5v6 c3c4c2 图图 2 2 二部图中的二部图中的 girthgirth 3 1 校验矩阵的随机构造 1 Gallager 构造法 Gallager 基于 GF 2 域上定义的 n j k LDPC 码 其校验矩阵 H 的构造 7 如下 1 将 Gallager 码的监督矩阵按行划分成 j 个部分 每部分包含相同的行数 每 一部分的每一列中只包含一个 1 2 第一部分构造的矩阵中 1 比特在行中按降幂排列 在第一行中 第 1 到 k 个元素为 1 其余为 0 在第 2 行中 从第 k 1 到 2k 个元素为 1 其余为 0 如此安排 第 i 行中 从第 i 1 k 1 到第 ik 个元素为 1 其余为 0 3 其余 j 1 部分的构造是对第一部分进行列的随机重排 该构造法可以保证每列有 j 个 1 每行有 k 个 1 图 3 给出了由 Gallager 构造 法构造的 20 3 4 的 LDPC 码校验矩阵 码长为 20 j 3 k 4 11110000000000000000 00001111000000000000 00000000111100000000 00000000000011110000 00000000000000001111 10001000100010000000 01000100010000001000 00100010000001000100 00010000001000100010 00000001000100010001 10000100000100000100 01000010001000010000 00100001000010000010 00010000100001001000 00001000010000100001 基于 MATLAB 的 LDPC 码的仿真与研究8 图图 3 3 GallagerGallager 构造的 构造的 2020 3 3 4 4 的 的 LDPCLDPC 码校验矩阵码校验矩阵 2 Mackay 构造法 Mackay 提出了 3 种校验矩阵的构造方法 使其二部图中循环的数目最少 得到 8 的矩阵去掉了长度为 4 的短环 分别如下 1 构造 1A 这是一种最基本的构造方法 保证矩阵列重 t 通常取 t 3 保证 行重在每行中均匀分布 而且任意列间不存在长度为 4 的短环 如图 4 所示 33 图图 4 4 1A1A 构造构造 2 构造 2A 矩阵中有 M 2 列列重为 2 用 2 个 M 2 M 2 的单位矩阵上下摆放 其余的 N M 2 列按照 1A 法构造 任意列间的重叠不超过 1 如图 5 所示 3 图图 5 5 2A2A 构造构造 3 构造 1B 2B 从 1A 2A 中特意删去二部图中一些出现短环的列 再插入 随机产生的列 使二部图中不再存在小于某个长度的 girth 如 girth 为 6 3 Davey 构造法 Davey 构造法把每个节点按照它们的度 d 变成 d 个节点 然后构造二部图 设 9 H 中所有非 0 元素的个数为 T 则有 下半部和上半部分别有 T 个 ii ii Tnimi 节点 和 把列重为 i 的列用 i 个下节点表示 用其列 12 T D DD 12 T U UU 号表示这些节点 同样把行重为 j 的行用 j 个上节点表示 接下来对上节点进行随机排 列构造校验式 为确保不出现双边 即一个上节点的两条边参与同一个校验式 在排 列时要保证同名的上 下节点不相互对应 4 比特填充及扩展的比特填充方法 淮南师范学院 2012 届本科毕业论文9 比特填充 Bit filling 算法可以解决以下三个问题 一是给定正整数 10 a b g m 其中 g 是偶数 构造一个 m n 维校验矩阵 H 每列有 a 个 1 每行最多 有 b 个 1 girth 为 g 码率尽量大 二是给定变量节点数 n 度为 a 校验节点数 m 度为 b 满足 n a m b 使得 g 较大 三是给定 n a g 使得 m 较小 也就是使码 率较大 比特填充算法的实现 假设我们已得到一个校验矩阵 H n 列 列重 a 行重未超 过 b girth 大于等于 g 现在在 H 上添加第 n 1 列 用一个初值为空的集合表示第 1 U n 1 列 该集合长度为 a 元素为各校验节点 是 l 2 m 的子集之一 再假设 已添加 j 个元素到 0 j a 按条件再添加第 j 1 个元素到 这样循环往复下去 1 U 1 U 就会得到整个校验矩阵 H 扩展的比特填充 Extended Bit filling 算法是比特填充算法的扩展 该算法通 11 过减少 girth 到 g 2 这种方式 在列不能增加时 保证列可以继续增加下去 5 PEG 方法 PEG Progressive Edge Growth 方法是 Xiao Yu Hu 等提出的 是一种在二部图上 以增加 girth 长度为目的的方法 具体操作如下 对于给定的信息节点数 n 校验节 12 点数 m 和比特节点的分布序列 首先选取新的边 选取时要保证尽量对 Tanner 图的 girth 没有较大影响 然后选择程序放置 接着继续搜索下一边放置 直至结束 具体算法如下 For i 0 to n 1 For k 0 to d 1 i b If k 0 edge 是比特节点的第 1 条入射边 是校验节点在当 0 i ijb b cE 0 i b E i b j c 前图集合中度数最低的 011i bbb EEE Else 在当前图中从比特节点开始采用树形结构扩大到深度为 l 直到 i b i l b N Then 是比特节点的第 k 条入射边 是集合中度 1 i l b N i k ijb b cE i k b E i b j c i l b N 数最低的校验节点 3 2 校验矩阵的结构化构造 1 有限几何构造法 基于 MATLAB 的 LDPC 码的仿真与研究10 有限几何构造法是基于有限几何中的线和点来进行的 包括欧式几何 Euclidean Geometry EG 和投影几何 Projective Geometry PG EG 和 PG 具有 n 个点和 J 条 线 满足以下条件 每条线有 p 个点 任意两点间有且只有一条线 每个点只能落 13 在 q 条线上 两条线平行或者只有一个交点 与有限几何 G 对应的 GF 2 上的 J n 维矩阵为 H 矩阵的行和列分别对应 G 的线和点 若第 i 条线包含第 j 个点 ij h 则 1 否则 0 矩阵的某一行表示这条线包含的所有点 重量为 q 某一列表示 ij h ij h 穿过这个点的所有线 重量为 q 矩阵的行称为 G 中线的入射矢量 H 矩阵为 G 中行 的入射矩阵 矩阵的行对应信息比特 列对应校验方程 可产生 LDPC 码 2 BIBD 组合法 平衡不完全区组设计 Balanced Incomplete Block Design BIBD 方法 给定 23 一个 v 元素的集合 V 1 2 v B 为 v 的子集的集合 r 为 k 的 12 b B BB 子集数 则 V B 构成区组设计 而且对任意一对元素 i j l 2 v ij 有个区组同时包括它们 称为平衡不完全区组设计 记为 v k BIBD 1 时的 BIBD 称为 Steiner 系统 在 LDPC 码中 关联矩阵和校验矩阵有对应关 系 如 假设 X 1 2 3 4 5 6 7 8 9 A 是 12 个 3 元素块的集合 各区 组为 1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9 1 5 9 2 6 7 3 4 8 1 6 8 2 4 9 3 5 7 X A 就是一个 9 3 1 BIBD 它的关联矩阵如下 100100100100 100010010010 100001001001 010100001010 010010100001 010001010100 001100010001 001010001100 001001100010 在 BIBD 中 任两个元素相遇的次数都是 1 构造的校验矩阵可以确保不存在 girth 为 4 的环 淮南师范学院 2012 届本科毕业论文11 4 LDPC 码的编码 本小节主要讨论 LDPC 码随机构造的几种通用的编码方法 包括密集编码方法 LU 分 解法 高斯消去法和 LDPC 码的有效编码方法 并对它们的编码复杂度进行了比较 4 1 密集编码 设校验矩阵 H 的所有行都是线性无关的 根据分组码定义 编码后的码字 x 必须 满足 Hx 0 为了在接收区易于区分信息位和校验位 一般采用系统码 但对于随机构造的校 验矩阵 H 具有非系统码的形式 因此首先将 H 进行列变换 将 H 分割成 M M 的左方 阵 I 和 M N M 的右矩阵 P 同样将 x 分成 M 个校验比特 C 和 N M 个系统比特 S 有 1 0 C I P S 得到 AC BS 0 2 因此 得到校验位 1 CI BP 该方法的计算复杂度表现在计算 约为 但实际中如果采用相同的校验 1 I P 3 O M 矩阵 其计算复杂度为 M N M 4 2 LU 分解 LU 分解法的思想是 若 I 是非奇异矩阵 则可将 I 分解为一个上三角矩阵 U 和下 三角矩阵 L 的乘积 其中 L 和 U 也是 M N 维稀疏矩阵 基本步骤如下 1 对 H 矩阵进行 LU 分解 得到重排后的 H B L U 2 计算 Z BS 3 通过前向消元法解方程 LY Z 得到 Y 其中 Y 是 M 维列向量 4 通过后向消元法解方程 UC Y 得到 C LU 分解的一个基本算法如下所示 1 设 U 和 L 为全零矩阵 2 设 F H 3 for i 1 to m 基于 MATLAB 的 LDPC 码的仿真与研究12 找一个 F 矩阵中第 i 行第 i 列的非零元素 或在其后行 或列 的非零元素 重新排列 F 和 H 的行和列 使得这个非零元素放入第 i 行第 i 列 把 F 矩阵第 i 列中的从顶到第 i 行的元素拷贝到 U 矩阵的第 i 列 把 F 矩阵第 i 列中的从第 i 行到底的元素拷贝到 L 矩阵的第 i 列 把 F 矩阵第 i 行元素模 2 加到第 i 列的后行元素中 End 4 把 B 矩阵设置为重排后的 H 矩阵最后 N M 列 4 3 高斯消去 高斯消去法把校验矩阵化简为图 6 所示的等价下三角矩阵 图图 6 6 下三角校验矩阵下三角校验矩阵 构造出系统码 c u p 使用式 3 计算校验比特 3 1 1 11 p n ml ll jjj n mj jj H uHp 4 4 LDPC 码的有效编码 前面介绍的 LDPC 编码方法都没有办法使校验矩阵始终保持它的稀疏性 为了能 够充分保证和利用校验矩阵的稀疏性 提出了一种有效的编码方法 该编码方法复杂 度较低 近似线性复杂度 具体步骤如下 1 三角化 为不改变校验矩阵 H 的稀疏性 仅对 H 的行和列进行重组 得到近似下三角稀疏 矩阵 H 如图 7 所示 淮南师范学院 2012 届本科毕业论文13 图图 7 7 近似下三角的校验矩阵近似下三角的校验矩阵 表示如下 4 ABT H FDE 其中 A 的维数为 M g N M B 为 M g g T 为 M g M g F 为 g M g D 为 g g E 为 g M g T 是对角线元素为 1 的下三角矩阵 三角化 过程中 使矩阵的间隔 g 尽量小 2 秩验算 对 H 左乘矩阵 1 0I ETI 使其成为右下角为 0 的矩阵 11 0 ABT ETAFET BD 检验是否是非奇异 如果是奇异 则与前面列重排 直至为非奇 1 ET BD 异 3 编码 设码字 x 其中 s 为信息符号 为校验符号 据方程可得 1 2 s p p 12 p p0Hx 5 12 0AsBpTp 6 11 1 0ETAF sET BD p 得到 7 11 1 pETAF s 基于 MATLAB 的 LDPC 码的仿真与研究14 8 1 21 pTAsBp 表表 1 1 的计算复杂度的计算复杂度 11 1 pETAF s 矩阵运算计算复杂度 AsO N 1 s TA O N 1 s ETA O N FsO N Fs 1 s ETA O N 11 ss ETAF 2 gO 表表 2 2 的计算复杂度的计算复杂度 1 21 pTAsBp 矩阵运算计算复杂度 AsO N 1 pBO N As 1 pBO N 1 1 TAsBp O N 该算法总的计算复杂度为 优于前几种算法 2 O Ng 5 LDPC 码的译码 LDPC 码的迭代译码方法是 LDPC 码能够得以迅速发展的主要原因 该译码方法使 得 LDPC 码不仅描述简单 译码复杂度低 而且可以并行操作 便于硬件实现 具有 接近 Shannon 极限的优异性能 Gallager 提出的译码方法可以被当作是 Tanner 图上 14 的置信传播算法 BP Belief Propagation Algorithm 亦可以叫作和积算法 Sum Product Algorithm 本小节阐述了概率域的 BP 算法和对数域的 LLR BP 算法 然后介 绍并分析了几种简化的 BP 译码算法 并对它们的复杂度和性能进行比较 5 1 BP 译码 1 概率 BP 算法 淮南师范学院 2012 届本科毕业论文15 和积 BP 算法是由多变量函数通过因子图中的比特节点和校验节点 以及比 15 特节点和校验节点间的更新规则来得到以某个变量为参数的边缘函数 函数值消息沿 边传输 在节点更新 定义如下符号 为比特节点的概率 L m b nn pP xb n xb n 1 为参与校验集所有比特节点的集合 L m n 为除了外的 L m mn H m z n x 是在 M n m 已知的条件下 信息比特的概率 是在给定和所有 b mn q n xb b mn r n xb L m n 条件下满足校验 0 的概率 l x m z 译码采用基于 Tanner 图的概率迭代算法 译码过程中 比特节点向与其相连的 n x 所有校验节点发送消息 通知节点处于状态 b 的概率 用于更新节点上 m z b mn q m z n x m z 的消息 然后校验节点向父节点发送己更新的消息 通知它满足校验时节 b mn r m z n x b mn r 点应处于的状态 一轮更新后 产生一个估计码字 若满足 H 0 则译码成功 n x X X 否则再迭代上述过程 如果达到迭代的最大值后仍没有满足校验 则译码失败 可以 表述如下 1 初始化 2 00 2 1 2 2 1 1 exp 2 2 n mnn r qP 2 11 2 1 2 2 1 1 exp 2 2 n mnn r qP 2 校验节点更新 令 则 1 1 mn q 0 mn q 1 mn q mn r 0 mn r 1 mn r mn mrow nm q 1 mn r 1 2 mn r 0 mn r 1 2 mn r 3 比特节点更新 选择合适的 使 111 mnmnm mn ncol mn qpr 000 mnmnm mn ncol mn qpr mn 1 0 mn q 1 mn q 4 更新伪后验概率 选择合适的 使 1 111 nnnmn m M n qpr 000 nmnnmn m M n qpr n 0 n q 1 n q 5 译码判决 若 0 5 判定 1 否则 0 如果使或到达最大迭代次数 1 n q 0 n q nx nx 0 T H X 基于 MATLAB 的 LDPC 码的仿真与研究16 则结束 否则迭代次数加 1 转到步骤 2 2 LLR BP 算法 LLR BP 算法是将概率消息用对数似然比来表示 由此就可以用计算量较小的加法 运算来代替计算量较大的乘法运算 这样计算时间就可以大大减少 定义 16 9 0 ln 1 i i i P L P P LLR BP 算法计算过程如下 1 初始化 首先算出初始概率似然比消息 该消息是由信道传向信息节 i L P 点的 接着对所有信息节点 i 和与其相邻的校验节点 j 给出信息节点传递给校验节点 的初始消息 10 0 iji LqL P 2 校验节点更新 计算所有的校验节点 j 第 l 次迭代时变量节点传递给校验节 点的消息 11 1 1 1 2tanh tanh 2 j ll ji i j iRi LrLq 3 信息节点更新 计算所有的信息节点 i 第 l 次迭代时校验节点传递给变量节 点的消息 12 i ll iji ji jCj LqL PLr 4 译码判决 对所有的变量节点计算硬判决消息 若 i ll iiji j C LqL PLr 则 否则 如果使或达到最大迭代次数 则结束 否 0 l i Lq 0 i c 1 i c 0 T i Hc 则转到步骤 1 5 2 降低复杂度的 BP 译码 BP 算法能够得以普遍应用 不仅因为其具有优异的译码性能 而且因为其具有较 低的复杂度 如何能得到译码性能和复杂度的折衷 是一个有待于研究的问题 Fossorier 等人提出了几种简易算法 这些简易算法都是基于 LLR BP 算法的 仅仅采 用加法运算就可以成功地译码 在很大程度上降低了译码的复杂度 下面加以介绍 17 并进行分析比较 1 迭代 APP 算法 淮南师范学院 2012 届本科毕业论文17 迭代 APP A Posteriori Probability 算法 在变量节点的处理中 只采用加法 18 运算 但算法的实现复杂度还可进一步降低 如果在要传递的变量节点之间引入相关 性 这样传递的就是内部消息而不再是外部消息 需要计算和存储的就仅仅是一个变 量消息值 从而可以降低算法的复杂度 迭代 APP 用 LLR BP 算法中的代替 i L q 参与校验消息的迭代 这样就通过传递内部消息而大大降低了系统的复杂度 ij L q 2 UMP BP Based 算法 最小和或最大积 LLR BP 算法中校验节点的处理可以进一步推导为 13 1 1 1 1 2tanh tanh 2 1 2tanh sgn tanh 2 1 2sgn tanh tanh 2 j jj jj ji i j iRi i ji j iRiiRi i ji j iRiiRi L rL q L qL q L qL q 由于 14 111 tanh mintanh tanh min 222 jj j i jiRii jiRii j iRi L qL qL q 所以 15 sgn min j j ji i jiRii j iRi L rL qL q UMP Uniformly Most Powerful BP Based 算法又称为最小和 Min Sum 算 19 法或最大积 Max Product 算法 该算法是用式来处理 LLR BP 算法中校验节点的消 息 此时校验节点的迭代只有比较算法和加法运算 计算的复杂度就大大降低了 对 于加性高斯白噪声信道 该算法不需要信道估计 3 APP Based 算法 迭代 APP 算法仅对变量消息的计算进行简化 而 UMP BP Based 算法仅对校验消 息的计算进行简化 如果对校验消息和变量消息的计算都进行简化 运算的复杂度将 会进一步降低 UMP Uniformly Most Powerful APP Based 算法就将 BP Based 算法 与迭代 APP 算法结合在一起 译码步骤如下 1 初始化 首先算出初始概率似然比消息 该消息是由信道传向信息节 i L P 基于 MATLAB 的 LDPC 码的仿真与研究18 点的 接着对每一变量节点 i 设定变量节点传递给校验节点的初始消息 16 0 ii LqL P 2 校验节点更新 计算所有的校验节点 j 第 l 次迭代时变量节点传递给校验节 点的消息 17 1 1 sgn min j j lll jiii Ri i R LrLqLq 3 变量节点更新 计算所有的信息节点 i 第 l 次迭代时校验节点传递给变量节 点的消息 18 i ll iiji j C LqL PLr 4 译码判决 对所有变量节点计算硬判决消息 若 则 l i Lq 0 l i Lq 0 i c 否则 如果使或达到最大迭代次数 则结束 否则转到步骤 1 1 i c 0 T i Hc 该算法同样也不需要信道估计 4 与标准 BP 算法的比较 为了比较 LLR BP 算法 UMP BP Based 算法和 UMP APP Based 算法的复杂度 对于码率 1 2 的 LDPC 码 n p 2p 对以上三种算法进行了比较 每一次迭代计算 量如表 3 所示 20 表表 3 3 译码算法计算量比较译码算法计算量比较 译码算法加法运算乘法运算除法运算 LLR BP 31 np 11np 9n 1 n p UMP BP Based 2 4n 1 2 log 2 pnp UMP APP Based 2 2np 2 log 2 npn 由表 3 可知 UMP BP Based 算法和 UMP APP Based 算法只有加法运算 跟 BP 算法比较 计算量大大减小了 同时 为了比较了三种译码算法的误码性能 本论文 对三种算法进行了仿真比较 仿真采用的是 1532 3 6 LDPC 码 QPSK 调制 AWGN 信道 仿真结果如图 8 所示 从仿真结果可以看出 采用两种简化算法 虽然 计算复杂度有所降低 但误码性能同时也有一定程度的降低 BP Based 算法只有加法 淮南师范学院 2012 届本科毕业论文19 运算 SNR 在误码率为时比 LLR BP 算法多损失约 0 5dB 而 APP Based 算法的计 4 10 算量约为 BP Based 算法的 1 2 在误码率为时又多损失了约 0 5dB 相比较而言 4 10 BP Based 算法更实用些 图图 8 8 三种译码算法性能比较三种译码算法性能比较 基于 MATLAB 的 LDPC 码的仿真与研究20 6 运用 MATLAB 对 LDPC 码仿真 Matlab是一个大家常用的通信仿真平台 本章利用Matlab软件在其平台上通过仿真得 出图形来理论分析说明码长 列重和迭代次数对LDPC码性能的影响从而更好的在通信 中运用LDPC码 21 6 1 不同码长对 LDPC 码的影响 应用Matlab软件在列重和迭代次数选择一定值时选取三种不同的码长进行仿真比 较对上所述选取LDPC码码长分别为300 500和1000 列重选择2 最大迭代次数设置 为20 仿真结果如图9所示 图图 9 9 不同码长对不同码长对 LDPCLDPC 码性能的影响码性能的影响 从图9的仿真图像可以清楚地看出 在信噪比相同的条件下 LDPC码的性能随着 码长的增加而不断提高但是在小信噪比区域 码长的增加对误码率的改进不大 但随 着信噪比的增大 LDPC码的误码率得到明显的提高 在误码率为很小时 码长为1000 的LDPC码比码长为500和300的LDPC码 信噪比分别降低了约0 3 dB和0 6 dB 但随着 码长的增加 LDPC码性能的提高是相对的 当达到一定码长后 性能将会有很小的提 高 这是因为一定码长下编码性能有一定的极限 随着码长的增大 编码和译码的复 杂度也增加 编码性能就会更接近极限 性能随码长增加改善的就更少 6 2 不同迭代次数对 LDPC 码的影响 应用Matlab软件在列重和码长选择一定值时选取三个不同的迭代次数进行仿真比 较对上所述选取的迭代次数分别为10 20 40 列重选择2 码长选择为500 仿真结果如下 图10所示 淮南师范学院 2012 届本科毕业论文21 图图 1010 不同迭代次数对不同迭代次数对 LDPCLDPC 性能的影响性能的影响 从图10所示的仿真结果可以看出 在相同的信噪比下 LDPC码的性能随着迭代次 数的增加而逐渐提高 在误码率为l0 时 译码迭代次数为40的LDPC码比迭代次数为 20和l0的LDPC码 信噪比分别降低了约0 16 dB和0 5 dB 但是LDPC码的误码率并 不能随着迭代次数的增加无限地减小 当迭代次数足够大的时候 再增加LDPC码的迭 代次数 只能增加系统的时延和复杂度 而LDPC码的性能不会再有提高 6 3 不同列重对 LDPC 码的影响 应用Matlab软件在迭代次数和码长选择一定值时选取三个不同的列重进行仿真比 较 对上所述选取的列重分别为2 3和4迭代次数选择20 码长选择为500 仿真结果如 下图11所示 图图 1111 不同列重对不同列重对 LDPCLDPC 性能的影响性能的影响 从图11的仿真结果可以看出 在相同的信噪比下 随着列重的增加 LDPC码的误 基于 MATLAB 的 LDPC 码的仿真与研究22 码率增大 分析其原因 因为仿真过程中所用的码长不够大 校验矩阵不是足够稀疏 增加列重 会在一定程度上降低检验矩阵的稀疏性 在校验矩阵不是足够稀疏的情况 下 稀疏性的一定提高会给编码对应的Tanner图带来大量短长度的环 而短长度的环 尤其是长度为4的环的增加将会使BP算法的性能恶化 导致LDPC码的性能的下降 因 此随着列重的增加 LDPC码的性能有所下降 这种LDPC码性能上的下降将会随着码 长的增加而逐渐减少 当码长足够长 列重的增加对校验矩阵的稀疏性的影响相对较 少 且在译码时 列重大的LDPC码比列重小的LDPC码得到更多的校验信息 从而得 到更可靠的译码 所以此时 随着列重的增加 LDPC码的性能将会得到改善 但是当 列重增加到较大时 因为校验矩阵不具有稀疏性 性能会随着列重的增加严重下降 6 4 本章小结 本文对LDPC码做了深入的研究 然后应用MATLAB软件对码长 列重和迭代次数 对LDPC码性能的影响进行了仿真实验 通过仿真和理论分析得到如下结论 LDPC码 长码的误码性能优于短码的误码