2007/07/30 by Mark F. Flanagan, Flanagan, Mark F., Vitaly Skachek +5
Computer Science · Mathematics · #Coding theory and cryptography #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.0707.4360
6 pages, 1 figure, 7-th International ITG Conference on Source and Channel Coding (SCC'08)
openalex publication_date 2007/07/30 · arxiv created 2007/10/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We develop a framework for linear-programming (LP) decoding of non-binary linear codes over rings. We prove that the resulting LP decoder has the `maximum likelihood certificate' property, and we show that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. LP decoding performance is illustrated for the (11,6,5) ternary Golay code with ternary PSK modulation over AWGN, and in this case it is shown that the LP decoder performance is comparable to codeword-error-rate-optimum hard-decision based decoding.