LDPC编码中贪婪算法的改进

A Modified Greedy Algorithm for LDPC Encoder Implementation

基于校验矩阵近似下三角化的RU编码算法,针对分层构造的低密度校验码(Low-DensityParity-Check code,LDPC)码字提出了一种编码实现中贪婪算法的改进方法。首先对低密度校验码的校验矩阵进行列删除尝试,尽量达到最大化下三角子矩阵。若第一层中删除的列数不当,会导致在第一次对角化后,在由未经过对角化的行列构成的剩余矩阵中找不到重量为1的列,使对角化操作提前中止。因此,需要进行列删除尝试,在第一层中删除更多的列向量,直到雪崩效应发生,使剩余矩阵能够达到完全对角化,这实质上也是一种贪婪思想。通过该贪婪方法可以将关键参数g控制得尽量小,从而明显减少相应的分层低密度校验码编码器的硬件资源消耗。

Based on the RU encoding algorithm by bringing the corresponding LDPC（ Low- Density Parity - Ckeck） parity - check matrix into approximate lower triangular form, this paper provides a modified greedy algorithm aiming at efficient triangulation of specialized layered LDPC cedes. To maximize the size of the triangularized sub - matrix, it is necessary to first operate ＂column deletion trial＂ on the LDPC parity - check matrix. It＇s most likely that the triangularization process will be terminated if no enough columns are deleted. Therefore, ＂column deletion trial＂ is introduced in this scheme to evoke the snowslide effect, which is assumed as an extension to the greedy idea embodied in the original algorithm. By this modified greedy algorithm, the key parameter g is much smaller so that the complexity of the LDPC enceder implementation can be further restrained.