LDPC码论文个人简单整理编写

LDPC 码作业 通信与信息系统 LDPCLDPC 编码编码译码方法研究及误码率实现译码方法研究及误码率实现 摘摘 要要 低密度奇偶校验低密度奇偶校验 LDPCLDPC 码 码 Low DensityLow Density Parity CheckParity Check codescodes 是继 是继 TurboTurbo 码之后又一种逼近香农极限的信道编码 相码之后又一种逼近香农极限的信道编码 相 对于对于 TurboTurbo LDPCLDPC 码有着诸多的优势 以及更加广阔的应用前码有着诸多的优势 以及更加广阔的应用前 景 因此它已经成为编码界当前最热门的研究课题 本文主要研景 因此它已经成为编码界当前最热门的研究课题 本文主要研 究了低密度校验码究了低密度校验码 LDPCLDPC 码码 的编译码方法及不同信噪比下所得的编译码方法及不同信噪比下所得 到的误码率 编码通常有高斯消元法 基于近似下三角化的到的误码率 编码通常有高斯消元法 基于近似下三角化的 LDPCLDPC 编码方法和特殊码字编码方法和特殊码字 LDPCLDPC 编码方法 译码通常有消息传编码方法 译码通常有消息传 递算法 最小和译码算法 比特翻转译码算法等 递算法 最小和译码算法 比特翻转译码算法等 AbstractAbstract TheThe Low densityLow density parityparity checkcheck LDPCLDPC codescodes Low Density Low Density Parity Parity CheckCheck codescodes to to is is yetyet anotheranother afterafter thethe TurboTurbo codescodes approachingapproaching thethe ShannonShannon limitlimit ofof channelchannel coding coding RelativeRelative toto thethe TurboTurbo andand LDPCLDPC codescodes havehave manymany advantages advantages asas wellwell asas moremore broadbroad applicationapplication prospects prospects soso it it hashas becomebecome thethe codingcoding communitycommunity is is thethe mostmost popularpopular researchresearch topics topics InIn thisthis paper paper thethe BERBER encodingencoding andand decodingdecoding methodsmethods andand differentdifferent signalsignal toto noisenoise ratioratio ofof lowlow densitydensity parityparity checkcheck codecode LDPC LDPC code code CodingCoding usuallyusually GaussianGaussian eliminationelimination method method basedbased onon thethe approximateapproximate lowerlower triangulartriangular LDPCLDPC encodingencoding methodmethod andand specialspecial codeword codeword LDPCLDPC encodingencoding method method DecodingDecoding typicallytypically messagemessage passingpassing algorithms algorithms beliefbelief propagationpropagation algorithm algorithm thethe smallestsmallest andand decoding decoding bitbit flippingflipping decodingdecoding algorithm algorithm 第一章第一章 引言引言 1 11 1 LDPCLDPC 码介绍码介绍 低密度校验码低密度校验码 LDPC LDPC 码码 是一种前向纠错码 它最初在是一种前向纠错码 它最初在 19621962 年由麻省理工学院的年由麻省理工学院的 GalfagerGalfager 在其博士论文中提出 那时候 世在其博士论文中提出 那时候 世 界才刚刚脱离真空管 进入第一代晶体管时代 实验仿真所要求界才刚刚脱离真空管 进入第一代晶体管时代 实验仿真所要求 的的计算能力并不发达 所以的的计算能力并不发达 所以 LDPCLDPC 码无与伦比的潜能没能引起码无与伦比的潜能没能引起 人们的重视 而被长久地忽视了人们的重视 而被长久地忽视了 3535 年 同一时期 主流的前向纠年 同一时期 主流的前向纠 错技错技 术是高度结构化的代数分组码和卷积码 尽管上述这些纠错码技术是高度结构化的代数分组码和卷积码 尽管上述这些纠错码技 术在实际中获得了巨大的成功 但是它们的性能却远没有达到术在实际中获得了巨大的成功 但是它们的性能却远没有达到 ShalmonShalmon 在其在其 19481948 年发表的开创性论文中所指出的理论可达限 年发表的开创性论文中所指出的理论可达限 到了到了 2020 实际实际 8080 年代末 经过几十年的尝试 学者们已经接受了年代末 经过几十年的尝试 学者们已经接受了 这个理论与实际之间无法逾越的鸿沟 这个理论与实际之间无法逾越的鸿沟 编码学研究经过了相当的一段沉寂之后 被编码学研究经过了相当的一段沉寂之后 被 turbo turbo 码码 的出现的出现 彻底唤醒 彻底唤醒 turboturbo 码由码由 B uB u GlavieuxGlavieux 和和 ThitimajshimaThitimajshima 在在 19931993 年提出 它彻底颠覆了所有人们认为成功的纠错码所要具备的因年提出 它彻底颠覆了所有人们认为成功的纠错码所要具备的因 素素 turbo turbo 码涉及非常少的代数 运用迭代 分布的算法 专注于码涉及非常少的代数 运用迭代 分布的算法 专注于 平均平均 而非最差而非最差 性能 同时仰赖从信道中获取的软性能 同时仰赖从信道中获取的软 或者似然或者似然 信信 息 一夜之间 在复杂度可控的译码器的协助下 达到息 一夜之间 在复杂度可控的译码器的协助下 达到 ShannonShannon 限所要越过的鸿沟已不复存在 限所要越过的鸿沟已不复存在 LDPCLDPC 码不仅蕴含有很高的理论价值 而且已经为卫星数字码不仅蕴含有很高的理论价值 而且已经为卫星数字 视频广播标准和长途光通信标准所采纳 还极有可能被吸收入视频广播标准和长途光通信标准所采纳 还极有可能被吸收入 IEEEIEEE 无线局域网标准中 人们还正在考虑把无线局域网标准中 人们还正在考虑把 LDPCLDPC 码应用到第四码应用到第四 代移动电话系统的长期发展规划中 代移动电话系统的长期发展规划中 1 21 2 LDPCLDPC 码的特点码的特点 LDPCLDPC 码是一种分组码 其校验矩阵只含有很少量非零元素 码是一种分组码 其校验矩阵只含有很少量非零元素 正是校验矩阵正是校验矩阵 H H 的这种稀疏性 保证了译码复杂度和最小码距都的这种稀疏性 保证了译码复杂度和最小码距都 只随码长呈现线性增加 只随码长呈现线性增加 除了校验矩阵除了校验矩阵 H H 是稀疏矩阵外 是稀疏矩阵外 LDPCLDPC 码本身与任何其它的码本身与任何其它的 分组码并无二致 其实如果现有的分组码可以被稀疏矩阵所表达 分组码并无二致 其实如果现有的分组码可以被稀疏矩阵所表达 那么用于那么用于 LDPCLDPC 码的迭代译码算法也可以成功的移植到它身上 码的迭代译码算法也可以成功的移植到它身上 然而 一般来说 为现有的分组码找到一个稀疏矩阵并不实际 然而 一般来说 为现有的分组码找到一个稀疏矩阵并不实际 不同的是 不同的是 LDPCLDPC 码的设计是以构造一个校验矩阵开始的 然后码的设计是以构造一个校验矩阵开始的 然后 才通过它确定一个生成矩阵进行后续编码 而才通过它确定一个生成矩阵进行后续编码 而 LDPCLDPC 的编码就是的编码就是 本论文所要讨论的主体内容 本论文所要讨论的主体内容 译码方法是译码方法是 LDPCLDPC 码与经典的分组码之间的最大区别 经典码与经典的分组码之间的最大区别 经典 的分组码一般是用的分组码一般是用 MLML 类的译码算法进行译码的 所以它们一般类的译码算法进行译码的 所以它们一般 码长较小 并通过代数设计以减低译码工作的复杂度 但是码长较小 并通过代数设计以减低译码工作的复杂度 但是 LDPCLDPC 码码长较长 并通过其校验矩阵码码长较长 并通过其校验矩阵 H H 的图像表达而进行迭代的图像表达而进行迭代 译码 所以它的设计以校验矩阵译码 所以它的设计以校验矩阵 H H 的特性为核心考虑之一 的特性为核心考虑之一 目前的研究均表明目前的研究均表明 LDPCLDPC 码是信道编码中纠错能力最强的一种码 码是信道编码中纠错能力最强的一种码 而且由于其译码器结构简单 可以用较少的资源消耗获得极高的而且由于其译码器结构简单 可以用较少的资源消耗获得极高的 吞吐量 因此应用前景相当广泛 吞吐量 因此应用前景相当广泛 1 31 3 LDPCLDPC 码的历史和现状码的历史和现状 LDPCLDPC 码于码于 19621962 年由年由 GallagerGallager 提出 因此它也被称为提出 因此它也被称为 GallagerGallager 码 它是码 它是 TurboTurbo 码之外的另一种逼近香农极限的码字 码之外的另一种逼近香农极限的码字 虽然虽然 GallagerGallager 证明了证明了 LDPCLDPC 码是渐进好码 但是受限于当时的码是渐进好码 但是受限于当时的 计算能力 计算能力 LDPCLDPC 码一度被认为是一种无法实现的信道编码方式 码一度被认为是一种无法实现的信道编码方式 在很长一段时间内没有得到人们的重视 在很长一段时间内没有得到人们的重视 19811981 年随着年随着 TannerTanner 著作的出现 著作的出现 LDPCLDPC 码可以用图论的角度进行新的理解和诠释 码可以用图论的角度进行新的理解和诠释 然而不幸的是这一理论成果依然没有得到人们的重视 知道然而不幸的是这一理论成果依然没有得到人们的重视 知道 9090 年代初 随着年代初 随着 TurboTurbo 码的出现 这才引发了学者们对于码的出现 这才引发了学者们对于 LDPCLDPC 码研究的热情 码研究的热情 MackayMackay 和和 NealNeal 在上世纪九十年代利用随机构造在上世纪九十年代利用随机构造 的的 TannerTanner 图研究了图研究了 LDPCLDPC 码的性能 采用码的性能 采用 BeliefBelief PropagationPropagation BPBP 算法 译码算法的算法 译码算法的 LDPCLDPC 码字具有与码字具有与 TurboTurbo 码相似的译码性能 长的码相似的译码性能 长的 LDPCLDPC 码在码在 BPBP 译码算法下性能甚至译码算法下性能甚至 超过了超过了 TurboTurbo 码 它可以达到距离香农限只有码 它可以达到距离香农限只有 0 1dB0 1dB 的距离 的距离 这个发现是的这个发现是的 LDPCLDPC 码比码比 TurboTurbo 码在需要高度可靠性的通信和码在需要高度可靠性的通信和 存储系统纠错中更具有竞争力 从此以后 有关存储系统纠错中更具有竞争力 从此以后 有关 LDPCLDPC 码的文献码的文献 大量涌现 大量涌现 第二章第二章 LDPCLDPC 码的编码和译码分析码的编码和译码分析 2 12 1 LDPCLDPC 码的编码方法码的编码方法 2 1 12 1 1 LDPCLDPC 码的标准编码方法码的标准编码方法 设设 LDPCLDPC 码的码长为码的码长为 n n 信息码长度为 信息码长度为 k k 校验码长度为 校验码长度为 m nm n 一一 k k 已经讨论过 校验矩阵已经讨论过 校验矩阵 H H 经过高斯消元可以化为经过高斯消元可以化为 H H H H Im m Im m 其中其中 H H 是尺寸为是尺寸为 mxkmxk 的二进制矩阵 可以得到的二进制矩阵 可以得到 Imxm Imxm 是尺寸是尺寸 为为 mm mm 的单位矩阵 于是可以得到 的单位矩阵 于是可以得到 G Ik kG Ik k H1 H1 通过生成矩阵通过生成矩阵 G G 就可以进行编码 以下用一个例子说明如何就可以进行编码 以下用一个例子说明如何 由校验矩阵由校验矩阵 H H 得到生成矩阵得到生成矩阵 G G 2 1 22 1 2 L L 分解编码算法 分解编码算法 首先推导出根据校验矩阵直接编码的等式 将尺寸为首先推导出根据校验矩阵直接编码的等式 将尺寸为 mxnmxn 校校 验矩阵验矩阵 H H 写成如下形式写成如下形式 H H H H 其中其中 H H 的尺寸为 的尺寸为 的尺寸为 的尺寸为 m m 设编码后的码字 设编码后的码字 行向量为行向量为 x x 它的长度为 把它写成如下形式 它的长度为 把它写成如下形式 c c p p 其中其中 s s 是信息码行向量 长度为是信息码行向量 长度为 k k p p 为校验码行向量 长度为为校验码行向量 长度为 m m 根根 据校验等式有据校验等式有 H cT OH cT O 上式展开得上式展开得 展开该矩阵方程 并考虑到运算是在展开该矩阵方程 并考虑到运算是在 GF 2 GF 2 中进行 得到中进行 得到 p Hp H T s HTT s HT 2 1 2 1 如果校验矩阵如果校验矩阵 H H 是非奇异 则是非奇异 则 HZHZ 满秩 所以有满秩 所以有 p s HT Hp s HT H T T 2 2 2 2 式式 2 1 2 1 和式和式 2 2 2 2 就是不通过生成矩阵而直接由校验矩阵进就是不通过生成矩阵而直接由校验矩阵进 行编码的等式 一切只依赖校验矩阵的编码都是通过这两个式子行编码的等式 一切只依赖校验矩阵的编码都是通过这两个式子 实现的 实现的 从式从式 2 1 2 1 可以看出 一般来说 只要校验矩阵具有下三角结可以看出 一般来说 只要校验矩阵具有下三角结 构 它总是能够通过迭代方法进行编码的 引入了迭代 就大大构 它总是能够通过迭代方法进行编码的 引入了迭代 就大大 降低了编码的复杂度 降低了编码的复杂度 LULU 分解编码算法就是以这个思想为基础的 分解编码算法就是以这个思想为基础的 LDPCLDPC 译码算法译码算法 2 2 消息传递算法 消息传递算法 在消息传递在消息传递 MessagePassing MessagePassing MP MP 算法中 概率信息依据算法中 概率信息依据 二分图在变量节点和校验节点之间传递 逐步进行迭代译码 节二分图在变量节点和校验节点之间传递 逐步进行迭代译码 节 点沿边发送的信息与上次从接收到的信息无关 而取决于和相连点沿边发送的信息与上次从接收到的信息无关 而取决于和相连 的其它边上接收的信息 目的在于使得任一条边上 只有外来信的其它边上接收的信息 目的在于使得任一条边上 只有外来信 息传递 从而保证译码性能 如果息传递 从而保证译码性能 如果 1DPC1DPC 码对应的二分图中不存码对应的二分图中不存 在环 则任一节点接受的信息都与从该节点发出的信息无关 从在环 则任一节点接受的信息都与从该节点发出的信息无关 从 而保证了迭代译码的性能 如果二分图中存在环 经过一定次数而保证了迭代译码的性能 如果二分图中存在环 经过一定次数 的迭代之后 节点收到的信息将将与其发出的信息存在相关性 的迭代之后 节点收到的信息将将与其发出的信息存在相关性 这将影响译码算法的性能 这将影响译码算法的性能 2 2 2 2 最小和译码算法最小和译码算法 最小和最小和 Min Min 一一 sum sum 译码算法是根据对数域译码算法是根据对数域 BPBP 译码算法提出译码算法提出 的一种近似简化算法 它利用求最小值的运算简化了函数运算 的一种近似简化算法 它利用求最小值的运算简化了函数运算 大大降低了运算复杂度且不需要对信道噪声进行估计 但其性能大大降低了运算复杂度且不需要对信道噪声进行估计 但其性能 也有一定程度的降低 也有一定程度的降低 2 2 比特翻转译码算法 比特翻转译码算法 比特翻转比特翻转 Bit Bit 一一 FlippingFlipping BF BF 译码算法首先将输入译码器的译码算法首先将输入译码器的 数据进行硬判决 然后将得到的数据进行硬判决 然后将得到的 O O 1 1 序列代入所有的校验方程 序列代入所有的校验方程 找出使校验方程不成立数目最多的变量节点 最后将该变量节点找出使校验方程不成立数目最多的变量节点 最后将该变量节点 所对应的比特位翻转 至此完成一次迭代 整个译码过程不断地所对应的比特位翻转 至此完成一次迭代 整个译码过程不断地 进行迭代 直到所有的校验方程都成立或者达到了设定的最大迭进行迭代 直到所有的校验方程都成立或者达到了设定的最大迭 代次数 比特翻转译码算法只进行比特位的翻转等儿种简单的运代次数 比特翻转译码算法只进行比特位的翻转等儿种简单的运 算 没有复杂的操作 因此非常适合硬件实现 但其性能相对于算 没有复杂的操作 因此非常适合硬件实现 但其性能相对于 BPBP 译码算法有所降低 适用于硬件条件受限而性能要求较低的场译码算法有所降低 适用于硬件条件受限而性能要求较低的场 合 合 附一部分关于比特翻转译码仿真程序 附一部分关于比特翻转译码仿真程序 function vHat decodeBitFlipping rx H iteration rx Received signal vector column vector H LDPC matrix iteration Number of iteration vHat Decoded vector 0 1 M N size H Prior hard decision ci 0 5 sign rx 1 Initialization rji zeros M N Asscociate the ci matrix with non zero elements of H qij H repmat ci M 1 for n 1 iteration Horizontal step for i 1 M c1 find H i for k 1 length c1 rji i c1 k mod sum qij i c1 qij i c1 k 2 end end Vertical step for j 1 N r1 find H j numOfOnes length find rji r1 j for k 1 length r1 Update qij set 1 for majority of 1s else 0 excluding r1 k if numOfOnes ci j length r1 numOfOnes rji r1 k j qij r1 k j 1 else qij r1 k j 0 end end if numOfOnes ci j length r1 numOfOnes vHat j 1 else vHat j 0 end end end 附一部分编码程序 附一部分编码程序 function c newH makeParityChk dSource H strategy Generate parity check vector bases on LDPC matrix H using sparse LU decomposition dSource Binary source 0 1 H LDPC matrix strategy Strategy for finding the next non zero diagonal elements 0 First First non zero found by column search 1 Mincol Minimum number of non zeros in later columns 2 Minprod Minimum product of Number of non zeros its column minus 1 Number of non zeros its row minus 1 c Check bits newH Rearrange H Get the matric dimension M N size H Set a new matrix F for LU decomposition F H LU matrices L zeros M N M U zeros M N M Re order the M x N M submatrix for i 1 M strategy 0 First 1 Mincol 2 Minprod switch strategy Create diagonally structured matrix using First strategy case 0 Find non zero elements 1s for the diagonal r c find F i end Find non zero diagonal element candidates rowIndex find r i Find the first non zero column chosenCol c rowIndex 1 i 1 Create diagonally structured matrix using Mincol strategy case 1 Find non zero elements 1s for the diagonal r c find F i end colWeight sum F i end 1 Find non zero diagonal element candidates rowIndex find r i Find the minimum column weight x ix min colWeight c rowIndex Add offset to the chosen row index to match the dimension of the original matrix F chosenCol c rowIndex ix i 1 Create diagonally structured matrix using Minprod strategy case 2 Find non zero elements 1s for the diagonal r c find F i end colWeig