低密度校验码的蚕食算法线性编码

Linear Encoding Greedy Algorithm of Low Density Parity Check Codes

首先论证了通过执行行列置换,将稀疏奇偶校验矩阵H变成近似下三角矩阵HT,同时应用以对角扩展处理为核心算法的蚕食算法使编码的复杂度可控制为线性的。接着论述了蚕食算法的3个阶段:启动阶段、主要三角矩阵变化阶段、清除阶段,当算法结束时校验节点将以O(n)的高概率剩余,即g将以极高的概率小于O(n)。

This text demonstrates that by performing row and column permutations we can bring paritycheck matrix into approximate lower triangular form  T,the complexity of encoding can be controlled to be linear when apply greedy algorithm.The algorithm has three phases: startup phase,main triangulation process,cleanup phase,with high probability at most O(n) check nodes will be left when the algorithm terminates.