2002 · 488 citations · 15 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsCryptographyEdge ComputingChannel CapacityChannel CodingCoding TheoryError Control CodingError-correcting CodesGraph AlgorithmsCode ConstructionsLdpc CodesLow-density Parity-check CodesLower BoundsMinimum DistanceMinimum Distance BoundsParity Check CodesParity-check Matrices
We propose a general method for constructing Tanner (1981) graphs with large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms or parameters of the graphs. Encoding of LDPC codes based on the PEG principle is also investigated. We show how to exploit the PEG graph construction to obtain LDPC codes that allow linear time encoding. The advantages of PEG Tanner graphs over randomly constructed graphs are demonstrated by extensive simulation results on code performance.
15
Low-density parity-check codes
Robert G. Gallager · IEEE Transactions on Information Theory · 1962 · 10.6K citations · Full text