本文针对LDPC译码算法进行总结，附带详细的推导过程。由于笔者不是这方面的专家，充其量略知一二，许多不懂的地方，还请读者们多多指教。
LDPC码在IEEE802.16e、IEEE802.11n、IEEE802.11ac、IEEE802.11ad以及5G等高吞吐量系统中得到了广泛的应用。
信道编解码作为整个通信系统中最难实现的一部分，众多高校、研究院所、企业，投入了大量的人力资源进行研究与实现。
在信道编解码技术中，译码主要分为硬判决译码和软判决译码。
LDPC硬判决译码算法主要分为：消息传递（Message-Passing，MP）算法、比特翻转（Bit Flipping, BF）算法和Gallager A、B算法。比特翻转算法中，先求取HCT，如果为0则停止译码，否则翻转参与校验失败校验方程最多的变量节点对应的比特，再计算HCT，如此迭代直到HCT=0或达到设定迭代次数。Gallager A、B算法算法过程参考其博士论文。硬判决译码性能较差，使用软判决可显著提高译码性能。
LDPC软判决译码基于置信度传播（BP）算法（或叫做和积SP算法），通过在变量节点VN和校验节点CN之间传播和更新置信度信息来达到译码收敛的效果。通过BP算法，又衍生出最小和算法，以及归一化最小和算法，偏置最小和算法。
一切算法研究，需要从脑海理论到落地实践，通过仿真验证，再到工程应用，才能将知识转变为财富。
01
MP译码算法
消息传递(MP)算法是迭代解码算法，在VN和CN之间来回传递消息，直到进程停止。消息标记的Mi表示已知bit值为0或1,e表示已删除位。
在LDPC译码中，用Bj符号表示H的奇偶校验方程中的bit集合(每一行中1的位置集合)，用Ai符号表示码的第i位的奇偶校验方程（每一列中1的位置集合）。
考虑下面的奇偶校验矩阵:
对于上面的奇偶校验矩阵，我们得到:
基于(Binary Erasure Channel,BEC)的LDPC译码处理过程如下：
02
BF译码算法
收到符号硬解码成1和0组成一个二进制向量y。在每个迭代中,计算所有检查和,以及涉及每一个n bit向量y不满足奇偶检验的数量。接下来，如果y的比特包含最大数量的未满足奇偶校验，则将其翻转。该过程将重复进行，直到所有校验和都满足或达到预定的迭代次数。
比特翻转译码算法的步骤如下：
03
BP(SP)算法
和积算法类似于前一节中描述的比特翻转算法，但表示每个判决(无论位值是1还是0)的消息现在都是概率。比特翻转译码接受接收比特的初始硬判定作为输入，和积算法是接受接收位的概率作为输入的软判定消息传递算法。在LDPC译码器操作之前，输入信道或接收比特的概率是已知的，因此它们也被称为接收比特的先验概率。在和积解码器中，节点之间传递的外部信息也是概率。校验节点j与比特节点i之间的外部信息用Eji表示; Eji给出了bit ci为1时使奇偶校验方程j满足的概率。如果第i位不包含在j中，则无法定义Eji，因为在检查节点j和第i bit之间没有外部信息。
奇偶校验方程中奇数个bit 是1的概率是：
也就是bit ci为1时奇偶校验方程满足的概率。bit ci为0时满足奇偶校验方程的概率为
二元变量的度量用以下对数似然比(LLR)表示：
其中，log就是loge，L(x)符号提供了x的硬判决，并且模|L(x)|决定了判决的可靠性。将LLR转化为概率：
当需要将概率相乘时，只需要加LLR，从而降低和积译码器的复杂性。这使得概率的对数表示有了好处。从校验节点j
到比特节点i的外部信息表示为LLR：
从而有：
其中：
运用关系式
于是得到：
或者，运用关系式
则有
由于存在tanh和tanh-1函数的乘积，上述方程在数值上具有挑战性。
考虑Mj,i'其符号和大小(或bit值和bit可靠性):
于是有
然后我们可以得到：
上式产生了一种新的形式：
每个比特节点都可以连接输入LLR，Li，以及每个连接的检查节点的LLR。第i位的总LLR就是这些LLR的和：
对于所有的j,i，有Hj,i=1。因此，yi代表实际接收到的信道值，即不是有效值。对于不同的信道，Li可以计算：
BEC：
BSE：
BI-AWGNC:
瑞利信道：
对数域和积译码算法总结如下：
04
Min-Sum算法
Min-Sum算法是对数域和积译码算法的简化，主要考虑到和积译码算法在硬件实现上的复杂性，进而采用了一种近似算法。
归一化最小和译码算法的实现采用分层置信传播算法，是对上式（4-26）的修正，乘一个取值范围0~1的缩放因子。
偏置最小和译码算法，则是在归一化最小和译码算法的基础上，减去一个偏置因子。
本次关于LDPC译码算法的推导和总结，到此结束。
放眼全球，能把LDPC编解码器做好的，没有几家。
（声明：本文来源于笔者的学习笔记，文中打框部分的公式带有序号，可能与全文不对应，若有阅读困难，请联系上下文。鉴于劳动成果保护，算法示例与MATLAB算法实现，不在本文显示。）
往期精选
FPGA技术江湖广发江湖帖
无广告纯净模式，给技术交流一片净土，从初学小白到行业精英业界大佬等，从军工领域到民用企业等，从通信、图像处理到人工智能等各个方向应有尽有，QQ微信双选，FPGA技术江湖打造最纯净最专业的技术交流学习平台。
FPGA技术江湖微信交流群
加群主微信，备注姓名+公司/学校+岗位/专业进群
FPGA技术江湖QQ交流群
备注姓名+公司/学校+岗位/专业进群
