2010/05/01 by Byung‐Hak Kim, Byung-Hak Kim, Henry D. Pfister +2
Computer Science · Engineering · Mathematics · #Advanced Wireless Communication Techniques #Cooperative Communication and Network Coding #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1005.0052
To appear in Proc. 2010 IEEE Int. Symp. Information Theory, Ausin, TX, June 12-18, 2010 (a small error in the reference corrected)
openalex publication_date 2010/05/01 · arxiv created 2010/06/07 · arxiv updated 2010/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, the linear programming (LP) decoder for binary linear codes, introduced by Feldman, et al. is extended to joint-decoding of binary-input finite-state channels. In particular, we provide a rigorous definition of LP joint-decoding pseudo-codewords (JD-PCWs) that enables evaluation of the pairwise error probability between codewords and JD-PCWs. This leads naturally to a provable upper bound on decoder failure probability. If the channel is a finite-state intersymbol interference channel, then the LP joint decoder also has the maximum-likelihood (ML) certificate property and all integer valued solutions are codewords. In this case, the performance loss relative to ML decoding can be explained completely by fractional valued JD-PCWs.