cryptography - 随着奇偶校验矩阵密度增加的 LDPC 行为

Question

我的任务是为低密度奇偶校验码实现循环信念传播算法。这段代码使用了一个相当稀疏的奇偶校验矩阵 H（比如 750×1000 二进制矩阵，每列平均大约有 3 个“1”）。生成奇偶校验矩阵的代码取自这里

无论如何，子任务之一是在矩阵 H 的密度增加时检查 LDPC 码的可靠性。因此，我将通道容量固定为 0.5，将代码速度固定为 0.35，并开始增加矩阵的密度。随着列中“1”的平均数量以 1 为步长从 3 变为 7，灾难就会发生。使用 3 或 4，代码可以很好地应对。随着更高的密度，它开始失败：它不仅有时无法收敛，而且经常收敛到错误的码字并产生错误。

所以我的问题是：随着稀疏奇偶校验矩阵变得更密集，LDPC 码的预期行为类型是什么？对于熟练的读心者来说，一个额外的问题：在我的情况下（随着代码性能下降），更可能是因为 Loopy Belief Propagation 算法无法保证收敛，还是因为我在实现它时犯了错误？

Answer 1

在与我的助教和其他学生交谈后，我了解到以下内容：

1. 根据香农定理，代码的可靠性应该随着奇偶校验矩阵的密度而增加。这仅仅是因为进行了更多检查。
2. 然而，由于我们使用 Loopy Belief Propagation，当图中的边越来越多形成越来越多的循环时，它会变得非常困难。因此，实际性能下降。
3. 无法确定我是否仅基于此行为在代码中犯了错误。但是，由于我的代码确实适用于稀疏矩阵，因此实现很可能是好的。