Hardware-based Linear Program Decoding with the Alternating Direction Method of Multipliers

This thesis is concerned with the hardware implementation of Linear Program (LP) decoding for Low-Density Parity-Check (LDPC) codes. Until recently, LDPC codes have been decoded exclusively by means of graphical inference using belief propagation (BP). LP decoding frames the decoding problem in the language of convex optimization, resulting in several advantages over graphical inference techniques: better performance in certain applications, convergence guarantees, and an ability to incorporate advances in optimization theory. However, LP decoding is not currently used in practice as it is unclear whether or not a hardware-based implementation is possible. Recent LP decoding decomposition efforts, using the alternating direction method of multipliers (ADMM), make such an implementation possible. This work expands upon the ADMM decomposition of LP decoding, and a hardware-based LP decoder is implemented. This implementation shows that hardware-based LP decoding with error-rate performance within 0.5dB of double-precision BP and LP decoding is possible using 10-bit messages.M.A.S