2025年mt19937（mt19937伪随机数）

科技前沿 • 2025-05-21 18:18 • 阅读 52

大家好，我是讯享网，很高兴认识大家。

LDPC低密度奇偶校验码的比特翻转译码浅析

LDPC 低密度奇偶校验码的软判决译码算法浅析(一)

LDPC 低密度奇偶校验码的软判决译码算法浅析(二)–降低运算量

LDPC 软判决算法之似然比形式 (一)

LDPC 软判决算法之似然比形式 (二)–算法和代码

LDPC 软判决算法之似然比形式 (三) tanh-lambda 规则

LDPC码（low-density parity-check）实际上就是一种线性分组码，但是，由于LDPC码的 low-density 特性，可以用比较高效的算法来实现译码。这篇小文不是探讨 LDPC 码的方方面面，而是在读者已经了解线性分组码的基本概念，以及校验矩阵的基础上，试图对 LDPC码中一个简单的译码算法进行一个描述。在 Gallager 博士论文 [1] 中非常简要描述了一种称之为 Bit-Flipping 的 hard decoder 方法来译码。下面这段英文摘自 Gallager 博士论文 [1] :

（在哔站本人录制了一个小视频，做简单讲解：

https://www.bilibili.com/video/BV1C24y1Z7Uf/ ）

下面举个例子来具体说明这个过程。

假设校验矩阵是：

把接收到的码字表示为一个向量：

则根据收到的码字，可以计算出伴随式 syndrome（这个词在医学里面是症状的意思，在这里，可以理解为用来“诊断”接收到的码字是否有错误，以及诊断哪些校验方程是没有被满足的）：

计算后的结果，是一个含有5个元素的向量，记为：

为了易于理解，我们把上面这个矩阵形式的方程，展开成 5 个校验方程：

讯享网

现在，我们举一个具体的例子，发送一个码子，接收到的码字有一个错误，用 bit-flipping 算法做一个译码。

发送的码字为：

接收到的码字有错误：

可以看到是有错误的。下面，用 bit-flipping 算法，尝试做一个译码：

第一步，计算出伴随式：

                 注：上面是模 2 加法， 1+1=0

第二步，看伴随式是否都为 0 ，若都为 0 ，则结束译码，此时的就是正确的码字；如果伴随式不为0，跳到第三步。

第三步，看到分别在哪几个校验方程中出现，在出现的校验方程中，有几个校验方程是不满足的，即不等于0.

       出现在中，其中，因此，出现的校验方程中有 1 个方程不满足；

      出现在中，其中，因此，出现的校验方程中有 1 个方程不满足；

   以此类推，可以列出如下这个表格：

在 “不满足的校验方程的个数” 中选择最大的，上表中最大的是 3 ，对应的是所在的那一列，因此，把从 1 翻转（Flipping）成 0，接收到的码字被翻转后，记为新的 . 跳转到第一步继续执行。

此时的为：

译码结束。

正确的码字为：

可见，与最初的发送码字相同：

通俗来理解，这种迭代算法，就是考虑收到的码字中的比特，如果参与的校验方程中，越多的方程不满足，则越说明这个比特出错的可能性比较大，优先对这个比特进行翻转来尝试。

以前一直不太理解的 sum-product 方法的思想，现在似乎有所领悟。上面是一种硬判决，如果换成软判决，则考虑的是每个校验方程不满足的 “概率”，从绝对的满足与不满足，换成了满足或不满足的概率。进而来计算每个参与的比特，在各个校验方程中，不满足的概率，找出概率最大的那个进行某种修改。

[1] R.G.Gallager, Low-Density Parity-Check Codes, *IRE Trans.Info.Theory* IT-8:21-28. 1962.

2025年mt19937（mt19937伪随机数）

相关推荐