On Pseudocodewords and Decision Regions of Linear Programming Decoding of HDPC Codes

Author

Lifshitz, Asi ; Be´ery, Yair

Author_Institution

Sch. of Electr. Eng., Tel Aviv Univ., Ramat Aviv, Israel

Volume

60

Issue

4

fYear

2012

fDate

4/1/2012 12:00:00 AM

Firstpage

963

Lastpage

971

Abstract

In this paper we explore the decision regions of Linear Programming (LP) decoding. We compare the decision regions of an LP decoder, a Belief Propagation (BP) decoder and the optimal Maximum Likelihood (ML) decoder. We study the effect of minimal-weight pseudocodewords on LP decoding. We present global optimization as a method for finding the minimal pseudoweight of a given code as well as the number of minimal-weight generators. We present a complete pseudoweight distribution for the [24, 12, 8] extended Golay code, and provide justifications of why the pseudoweight distribution alone cannot be used for obtaining a tight upper bound on the error probability.

Keywords

Golay codes; error statistics; linear codes; linear programming; maximum likelihood decoding; HDPC codes; LP decoder; ML decoder; belief propagation decoder; decision regions; error probability; extended Golay code; global optimization; linear programming decoding; maximum likelihood decoder; minimal-weight generators; minimal-weight pseudocodewords; pseudoweight distribution; Euclidean distance; Generators; Iterative decoding; Linear programming; Maximum likelihood decoding; Vectors; Belief propagation; LP relaxation; bounded distance decoding; generators; global optimization; linear programming; pseudocodewords; pseudoweight;

fLanguage

English

Journal_Title

Communications, IEEE Transactions on

Publisher

ieee

ISSN

0090-6778

Type

jour

DOI

10.1109/TCOMM.2012.020912.110428

Filename

6152076