הנדסת חשמל - סמינר - אלכס יופיט
~~Electrical Engineering-Systems Department
*** SEMINAR ***
Alex Yufit
M.Sc. student under the supervision of Prof. Yair Be’ery
on the subject:
On Efficient Linear Programming Decoding of HDPC codes
In our work we propose improved LP decoding techniques for HDPC codes. Our enhanced LP decoder generates several variants of the fundamental polytope for eliminating pseudocodewords and improving decoding performance. On top of the enhanced performance, our decoder reduces the complexity by removing all inactive LP constraints at each iteration. We compare the performance and the complexity of our enhanced decoded to the New Separation Algorithm (NSA) for several BCH codes using AWGN channel. From simulation results we observe that our enhanced LP decoder achieves significant performance gain over the NSA with similar decoding complexity.
Inspired by the above results we propose three enhanced ADMM message passing decoders and discuss the tradeoffs between them. Our enhancements make the ADMM decoder suitable for HDPC codes. In simulation results our decoders show near-ML performance for BCH and Hamming codes that we’ve tested. Analysis of the decoding complexity implies that in high SNR regime our decoders have negligible overhead of the average complexity relative to the original ADMM decoder.
Decoding complexity is a very important factor for any practical use. We propose a framework for detailed analysis of the complexity of ADMM message passing decoder. Computational complexity of ADMM decoding algorithm is expressed by the number of arithmetic operations. First, we derive an upper bound on the complexity of a single ADMM message passing iteration. Our upper bound depends linearly on the number of edges in the Tanner graph of a code. Then, relying on simulation results we count the average number of required message passing iterations to get an estimate of the computational complexity of decoding one codeword. We observe that in high SNR regime the most dominant factor affecting total decoder complexity is the complexity of a single ADMM message passing iteration. We extend the analysis to our enhanced ADMM decoders.
