Title :
Decoding Binary Linear Block Codes Using Local Search
Author :
Esmaeili, M. ; Alampour, A. ; Gulliver, T.A.
Author_Institution :
Dept. of Math. Sci., Isfahan Univ. of Technol., Isfahan, Iran
Abstract :
This paper presents a novel iterative hard decision decoding algorithm for binary linear block codes over a binary symmetric channel (BSC). The problem is formulated as a 0-1 integer programming problem which is known to be NP-hard. When the crossover probability c of the channel is known, the solution space of the decoding problem can be decreased to a sphere whose radius is related to c. Using the penalty function method, the problem is reformulated on this reduced solution space. Then an iterative multi-flip local search algorithm is designed to find the global solution of this decoding problem. For a code with minimum distance d, when the radius of the sphere is not greater than d-1/2, this algorithm has the maximum likelihood (ML) certificate property, i.e., if the decoder outputs a codeword, it is guaranteed to be the ML codeword. Compared to the probabilistic suboptimal iterative belief propagation (BP) decoder, this approach has lower complexity and better performance. Numerical results show that in terms of speed and performance the proposed decoding method outperforms BP decoding in the error floor region.
Keywords :
block codes; channel coding; decoding; integer programming; iterative decoding; maximum likelihood decoding; probability; search problems; BP decoder; BSC; ML certificate property; ML codeword; NP-hard problem; binary symmetric channel; crossover probability; decoding binary linear block codes; decoding problem; integer programming problem; iterative multiflip local search algorithm; local search; maximum likelihood certificate property; novel iterative hard decision decoding algorithm; penalty function method; probabilistic suboptimal iterative belief propagation; Algorithm design and analysis; Indexes; Iterative decoding; Linear programming; Maximum likelihood decoding; Search problems; Integer programming decoding; iterative decoding; maximum likelihood hard decision decoding; multi-flip local search decoding;
Journal_Title :
Communications, IEEE Transactions on
DOI :
10.1109/TCOMM.2013.041113.120057