Noisy gradient descent bit flip decoding of low density parity check codes: Algorithm and implementation

A modified Gradient Descent Bit Flipping (GDBF) algorithm is proposed for decoding Low Density Parity Check (LDPC) codes on the binary-input Additive White Gaussian Noise (AWGN) channel. The new algorithm, called Noisy Gradient Descent Bit Flipping (NGDBF), introduces a random perturbation into each symbol metric at each iteration. The noise perturbation allows the algorithm to escape from undesirable local maxima, resulting in improved performance. A combination of heuristic improvements to the algorithm are proposed and evaluated. When the proposed heuristics are applied, NGDBF performs better than any previously reported GDBF variant, and comes within 0:5 dB of the Belief Propagation (BP) algorithm for several tested codes. Unlike other previous GDBF algorithms that provide an escape from local maxima, the proposed algorithm uses only local, fully parallel operations and does not require computing a global objective function or a sort over symbol metrics, making it highly ecient in comparison. The proposed NGDBF algorithm requires channel state information which must be obtained from a Signal to Noise Ratio (SNR) estimator. Architectural details are presented for implementing the NGDBF algorithm. Complexity analysis and optimizations are also discussed. The proposed algorithm is implemented on a code that is deployed in the Ethernet standard. The design employs a fully parallel architecture and a ooding schedule. The design employs a two phase decoding approach. In the rst phase, noise samples are processed and stored. In the second phase, the stored noise samples are read and are used in decoding. The design is implemented in a 65nm Complementary Metal Oxide Semiconductor (CMOS) process. The implemented design is compared to other decoder designs and all the necessary performance parameters are measured. The comparisons show that the NGDBF design is more ecient in terms of area consumption compared to other designs. The design is also more energy ecient and has a better error performance compared to other designs that are not based on the Min-Sum (MS) algorithm.