Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Information Theory (ISIT)

On the joint decoding of LDPC codes and finite-state channels via linear programming

Byung‐Hak Kim, Henry D. Pfister

Published Jun 1, 2010• 5 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2010.5513614

Related papers

On the Joint Decoding of LDPC Codes and Finite-State Channels via Linear Programming

Byung‐Hak Kim, Henry D. Pfister

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.

arXiv:1005.0052•May 1, 2010•5 citations

Joint Decoding of LDPC Codes and Finite-State Channels Via Linear-Programming

Byung‐Hak Kim, Henry D. Pfister

This paper considers the joint-decoding problem for finite-state channels (FSCs) and low-density parity-check (LDPC) codes. In the first part, the linear-programming (LP) decoder for binary linear codes is extended to perform joint-decoding of binary-input FSCs. 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 in AWGN. This leads naturally to a provable upper bound on decoder failure probability. If the channel is a finite-state intersymbol interference channel, then the joint LP 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. After deriving these results, we discovered some elements were equivalent to earlier work by Flanagan on linear-programming receivers. In the second part, we develop an efficient iterative solver for the joint LP decoder discussed in the first part. In particular, we extend the approach of iterative approximate LP decoding, proposed by Vontobel and Koetter and analyzed by Burshtein, to this problem. By taking advantage of the dual-domain structure of the joint-decoding LP, we obtain a convergent iterative algorithm for joint LP decoding whose structure is similar to BCJR-based turbo equalization (TE). The result is a joint iterative decoder whose per-iteration complexity is similar to that of TE but whose performance is similar to that of joint LP decoding. The main advantage of this decoder is that it appears to provide the predictability and superior performance of joint LP decoding with the computational complexity of TE. One expected application is coding for magnetic storage where the required block-error rate is extremely low and system performance is difficult to verify by simulation.

arXiv:1102.1480•IEEE Journal of Selected Topics in Signal Processing•Aug 25, 2011•18 citations

ML decoding via mixed-integer adaptive linear programming

Stark Christiaan Draper, Jonathan S. Yedidia, Yige Wang

Linear programming (LP) decoding was introduced by Feldman et al. (IEEE Trans. Inform. Theory Mar. 2005) as a novel way to decode binary low-density parity-check codes. Taghavi and Siegel (Proc. ISIT 2006) describe a computationally simplified decoding approach they term "adaptive" LP decoding. Adaptive LP decoding starts with a sub-set of the LP constraints, and iteratively adds violated constraints until an optimum of the original LP is found. Usually only a tiny fraction of the original constraints need to be reinstated, leading to huge efficiency gains compared to ordinary LP decoding. Here we describe a modification of the adaptive LP decoder that results in a maximum likelihood (ML) decoder. Whenever the adaptive LP decoder returns a pseudo-codeword rather than a codeword, we add an integer constraint on the least certain symbol of the pseudo-codeword. For certain codes, and especially in the high-SNR (error floor) regime, only a few integer constraints are required to force the resultant mixed-integer LP to the ML solution. We demonstrate that our approach can efficiently achieve the optimal ML decoding performance on a (155,64) LDPC code introduced by Tanner et al.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•46 citations

A Note on the Linear Programming Decoding of Binary Linear Codes for Multiple-Access Channel

Shunsuke Horii, Toshiyasu Matsushima, Shigeichi Hirasawa

In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2011•0 citations

Using Linear Programming to Decode Linear Codes

Jon Feldman, Martin J. Wainwright, David Ron Karger

Abstract — Given a linear code and observations from a noisy channel, the decoding problem is to determine the most likely (ML) codeword. We describe a method for approximate ML decoding of an arbitrary binary linear code, based on a linear programming (LP) relaxation that is defined by a factor graph or parity check representation of the code. The resulting LP decoder, which generalizes our previous work on turbo-like codes [FK02, FWK02], has the ML certificate property: it either outputs the ML codeword with a guarantee of correctness, or acknowledges an error. We provide a precise characterization of when the LP decoder succeeds, based on the cost of pseudocodewords associated with the factor graph. We introduce the notion of the fractional distance δ of a code, defined with respect to a particular LP relaxation, and prove that the LP decoder will correct up to [δ/2] − 1 errors. For the BEC, we prove that the performance of LP decoding is equivalent to standard iterative decoding. I.

•Jan 1, 2003•34 citations

An Iterative Joint Linear-Programming Decoding of LDPC Codes and Finite-State Channels

Byung‐Hak Kim, Henry D. Pfister

In this paper, we introduce an efficient method for the joint linear-programming (LP) decoding of low-density parity-check (LDPC) codes and finite-state channels (FSCs). In particular, we extend the approach of iterative approximate LP decoding proposed by Vontobel and Koetter and further analyzed by Burshtein. By taking advantage of the dual-domain structure of the joint decoding LP, we obtain a convergent iterative algorithm for joint decoding. Our intent was to find an algorithm very similar to BCJR-based turbo equalization (TE) and it seems that we have succeeded in this respect. The result is an iterative solver for the joint decoding LP whose complexity is similar to TE but whose performance is similar to joint LP decoding. The main advantage of this decoder is that it appears to provide the predictability of joint LP decoding with the computational complexity of TE.

arXiv:1009.4352•International Conference on Communications•Jun 1, 2011•9 citations
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.
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.
This paper considers the joint-decoding problem for finite-state channels (FSCs) and low-density parity-check (LDPC) codes. In the first part, the linear-programming (LP) decoder for binary linear codes is extended to perform joint-decoding of binary-input FSCs. 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 in AWGN. This leads naturally to a provable upper bound on decoder failure probability. If the channel is a finite-state intersymbol interference channel, then the joint LP 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. After deriving these results, we discovered some elements were equivalent to earlier work by Flanagan on linear-programming receivers. In the second part, we develop an efficient iterative solver for the joint LP decoder discussed in the first part. In particular, we extend the approach of iterative approximate LP decoding, proposed by Vontobel and Koetter and analyzed by Burshtein, to this problem. By taking advantage of the dual-domain structure of the joint-decoding LP, we obtain a convergent iterative algorithm for joint LP decoding whose structure is similar to BCJR-based turbo equalization (TE). The result is a joint iterative decoder whose per-iteration complexity is similar to that of TE but whose performance is similar to that of joint LP decoding. The main advantage of this decoder is that it appears to provide the predictability and superior performance of joint LP decoding with the computational complexity of TE. One expected application is coding for magnetic storage where the required block-error rate is extremely low and system performance is difficult to verify by simulation.
Linear programming (LP) decoding was introduced by Feldman et al. (IEEE Trans. Inform. Theory Mar. 2005) as a novel way to decode binary low-density parity-check codes. Taghavi and Siegel (Proc. ISIT 2006) describe a computationally simplified decoding approach they term "adaptive" LP decoding. Adaptive LP decoding starts with a sub-set of the LP constraints, and iteratively adds violated constraints until an optimum of the original LP is found. Usually only a tiny fraction of the original constraints need to be reinstated, leading to huge efficiency gains compared to ordinary LP decoding. Here we describe a modification of the adaptive LP decoder that results in a maximum likelihood (ML) decoder. Whenever the adaptive LP decoder returns a pseudo-codeword rather than a codeword, we add an integer constraint on the least certain symbol of the pseudo-codeword. For certain codes, and especially in the high-SNR (error floor) regime, only a few integer constraints are required to force the resultant mixed-integer LP to the ML solution. We demonstrate that our approach can efficiently achieve the optimal ML decoding performance on a (155,64) LDPC code introduced by Tanner et al.
In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.
Abstract — Given a linear code and observations from a noisy channel, the decoding problem is to determine the most likely (ML) codeword. We describe a method for approximate ML decoding of an arbitrary binary linear code, based on a linear programming (LP) relaxation that is defined by a factor graph or parity check representation of the code. The resulting LP decoder, which generalizes our previous work on turbo-like codes [FK02, FWK02], has the ML certificate property: it either outputs the ML codeword with a guarantee of correctness, or acknowledges an error. We provide a precise characterization of when the LP decoder succeeds, based on the cost of pseudocodewords associated with the factor graph. We introduce the notion of the fractional distance δ of a code, defined with respect to a particular LP relaxation, and prove that the LP decoder will correct up to [δ/2] − 1 errors. For the BEC, we prove that the performance of LP decoding is equivalent to standard iterative decoding. I.
In this paper, we introduce an efficient method for the joint linear-programming (LP) decoding of low-density parity-check (LDPC) codes and finite-state channels (FSCs). In particular, we extend the approach of iterative approximate LP decoding proposed by Vontobel and Koetter and further analyzed by Burshtein. By taking advantage of the dual-domain structure of the joint decoding LP, we obtain a convergent iterative algorithm for joint decoding. Our intent was to find an algorithm very similar to BCJR-based turbo equalization (TE) and it seems that we have succeeded in this respect. The result is an iterative solver for the joint decoding LP whose complexity is similar to TE but whose performance is similar to joint LP decoding. The main advantage of this decoder is that it appears to provide the predictability of joint LP decoding with the computational complexity of TE.