关键词: 低密度校验码, 渐进边增长算法, 平衡搜索树

Abstract:

A fast implementation of the Progressive Edge-Growth (PEG) algorithm for constructing low density parity check (LDPC) codes is presented. A balanced search tree is used to sort the check nodes and the variety of the Tanner graph is tracked during the edge growth process. The balanced search tree makes the search for a specified check node have the logarithmic complexity, and the number of times of the tree-expanding of the Tanner graph is significantly reduced by tracing the variety of the Tanner graph. Compared with the indicator-based implementation, the method presented here reduces the complexity effectively. Taking the construction of an LDPC code with length 10⁴ as an example, the time used by the balanced-search-tree based implementation is only about 20 percent of that used by the indicator-based approach.

Key words: low density parity check (LDPC) codes, progressive-edge-growth (PEG) algorithm, balanced search trees