Decoding Methods for Linear Codes

Miodrag Živković

A generalization of the Sullivan inequality (1967) on the ratio of the probability of a linear code to that of any of its cosets is proved. Starting from this inequality, a sufficient condition for successful decoding of linear codes by a probabilistic method is derived. A probabilistic decoding algorithm for low-density parity-check codes is also analyzed. This method of analysis enables one to estimate experimentally the probability of successful decoding for any given linear code and for any chosen family of parity-check sets. Using the example of a linear (512,100) code, the author illustrates the dependence of the successful probability on the channel noise level.>

Martin Bossert, F. Hergert

Haiyang LIU, Xiaopeng Jiao, Lianrong Ma

In this letter, we investigate the application of the subgradient method to design efficient algorithm for linear programming (LP) decoding of binary linear codes. A major drawback of the original formulation of LP decoding is that the description complexity of the feasible region is exponential in the check node degrees of the code. In order to tackle the problem, we propose a processing technique for LP decoding with the subgradient method, whose complexity is linear in the check node degrees. Consequently, a message-passing type decoding algorithm can be obtained, whose per-iteration complexity is extremely low. Moreover, if the algorithm converges to a valid codeword, it is guaranteed to be a maximum likelihood codeword. Simulation results on several binary linear codes with short lengths suggest that the performances of LP decoding based on the subgradient method and the state-of-art LP decoding implementation approach are comparable.

Ilya I. Dumer

Miodrag Živković

A generalization of Sullivan inequality on the ratio of the probabi-lity of a linear code to that of any of its cosets is proved. Starting from this inequality, a sufficient condition for successful decoding of linear codes by a probabilistic method is derived. A probabilistic decoding algorithm for “low–density parity–check codes ” is also analyzed. The results obtained allow one to estimate experimentally the probability of successful decoding using these probabilistic algorithms. Index Terms — linear code, inequality, probabilistic decoding, low– density parity–check code

Luigi Paura