2012/12/12 by Nathan Axvig, Axvig, Nathan
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Coding theory and cryptography #Combinatorics (math.CO) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1212.2953
openalex publication_date 2012/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In his Ph.D. disseration, Feldman and his collaborators define the linear programming decoder for binary linear codes, which is a linear programming relaxation of the maximum-likelihood decoding problem. This decoder does not, in general, attain maximum-likelihood performance; however, the source of this discrepancy is known to be the presence of non-integral extreme points (vertices) within the fundamental polytope, vectors which are also called nontrivial linear programming pseudocodewords. Restricting to the class of cycle codes, we provide necessary conditions for a vector to be a linear programming pseudocodeword. In particular, the components of any such pseudocodeword can only assume values of zero, one-half, or one.