一种快速的渐进边增长算法

Abstract

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

CLC Number:

TN911.22

CHEN Lin;FENG Da-zheng. Fast progressive edge-growth algorithm[J].J4, 2009, 36(3): 406-409.

[1]	MA Yanping;YANG Hongyong;MA Zhangchao;WANG Zengfeng. Proportional fair resource allocation in the relay enhanced cellular system [J]. J4, 2015, 42(3): 179-185.
[2]	SUN Jinhua;WANG Xuemei;WU Xiaojun. Joint pilot and iterative decoding carrier synchronization for the short burst transmission system [J]. J4, 2014, 41(1): 23-28+63.
[3]	LI Xiaotian;ZHANG Runsheng;LI Yanbin. Research on the recognition algorithm of Turbo codes on trellis termination [J]. J4, 2013, 40(4): 161-166.
[4]	ZHANG Chengchang;PENG Wanquan;WU Xiaobing. Construction and decoding of second-order magic square convolutional codes [J]. J4, 2013, 40(1): 155-161.
[5]	MA Tianming;LI Fengrong;SHI Yusong;WANG Yingguan. Novel design for the quasi orthogonal space-time block code [J]. J4, 2012, 39(4): 172-177.
[6]	LI Xiaofeng;FENG Dazheng;HU Shukai. Low power Turbo decoder based on the state metric decimation and interpolation strategy [J]. J4, 2012, 39(3): 58-62+71.
[7]	LIN Wei;BAI Baoming;WANG Xuepeng. Dynamic extended mim-sum decoding algorithm for Q-ary LDPC codes [J]. J4, 2012, 39(2): 59-65.
[8]	LIU You-yao;HAN Jun-gang. Star-cluster double-loop topology for the network-on-chip [J]. J4, 2009, 36(6): 1063-1069.
[9]	LIU Ying-ting;CAI Jue-ping;LI Zan;ZHANG Hai-lin;LIU Quan-yang. Dynamic spectrum allocation based on continuous double auctions in cognitive radio networks [J]. J4, 2009, 36(6): 996-1002.
[10]	GUO Kai;CHEN Yan-hui;LI Jian-dong. Rate-compatible codes based on puncturing parity check bits in group [J]. J4, 2009, 36(5): 782-787.
[11]	LIU Yuan-hua;WANG Xin-mei;HU Shu-kai;CHEN Ru-wei. Improved belief propagation algorithm for decoding of convolutional LDPC codes [J]. J4, 2009, 36(3): 424-447.
[12]	XIE Wu1;CAO Jia-nian1;WANG Li-ying2. Design and performance analysis of quasi-orthogonal space-time block codes for four antennas [J]. J4, 2009, 36(3): 563-572.
[13]	ZHANG Wei-dong;WANG Bao-cang;HU Yu-pu. New knapsack-type public-key cryptographic algorithm [J]. J4, 2009, 36(3): 506-511.

Fast progressive edge-growth algorithm

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 13

Metrics

Comments

Recommended 0