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

arXiv:1102.1480 · IEEE Journal of Selected Topics in Signal Processing

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

Byung‐Hak Kim, Henry D. Pfister

Published Aug 25, 2011• 18 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/jstsp.2011.2165525

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

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

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.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•5 citations

Iterative Approximate Linear Programming Decoding of LDPC Codes With Linear Complexity

David Burshtein

The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes.

IEEE Transactions on Information Theory•Oct 27, 2009•67 citations

Iterative Linear Programming Decoding of Nonbinary LDPC Codes With Linear Complexity

Dina Goldin, David Burshtein

The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.

IEEE Transactions on Information Theory•Aug 6, 2012•17 citations

Low Complexity Linear Programming Decoding of Nonbinary Linear Codes

Mayur Punekar, Mark F. Flanagan

Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. The aim of LP decoding is to develop an algorithm which has error-correcting performance similar to that of the Sum-Product (SP) decoding algorithm, while at the same time it should be amenable to mathematical analysis. The LP decoding algorithm has also been extended to nonbinary linear codes by Flanagan et al. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remain prohibitively large for codes of moderate to large block length. To address this problem, Vontobel et al. proposed a low complexity LP decoding algorithm for binary linear codes which has complexity linear in the block length. In this paper, we extend the latter work and propose a low-complexity LP decoding algorithm for nonbinary linear codes. We use the LP formulation proposed by Flanagan et al. as a basis and derive a pair of primal-dual LP formulations. The dual LP is then used to develop the low-complexity LP decoding algorithm for nonbinary linear codes. In contrast to the binary low-complexity LP decoding algorithm, our proposed algorithm is not directly related to the nonbinary SP algorithm. Nevertheless, the complexity of the proposed algorithm is linear in the block length and is limited mainly by the maximum check node degree. As a proof of concept, we also present a simulation result for a $[80,48]$ LDPC code defined over $\mathbb{Z}_4$ using quaternary phase-shift keying over the AWGN channel, and we show that the error-correcting performance of the proposed LP decoding algorithm is similar to that of the standard LP decoding using the simplex solver.

arXiv:1007.1368•Jul 8, 2010•0 citations
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.
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, 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.
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.
The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes.
The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.
Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. The aim of LP decoding is to develop an algorithm which has error-correcting performance similar to that of the Sum-Product (SP) decoding algorithm, while at the same time it should be amenable to mathematical analysis. The LP decoding algorithm has also been extended to nonbinary linear codes by Flanagan et al. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remain prohibitively large for codes of moderate to large block length. To address this problem, Vontobel et al. proposed a low complexity LP decoding algorithm for binary linear codes which has complexity linear in the block length. In this paper, we extend the latter work and propose a low-complexity LP decoding algorithm for nonbinary linear codes. We use the LP formulation proposed by Flanagan et al. as a basis and derive a pair of primal-dual LP formulations. The dual LP is then used to develop the low-complexity LP decoding algorithm for nonbinary linear codes. In contrast to the binary low-complexity LP decoding algorithm, our proposed algorithm is not directly related to the nonbinary SP algorithm. Nevertheless, the complexity of the proposed algorithm is linear in the block length and is limited mainly by the maximum check node degree. As a proof of concept, we also present a simulation result for a [80,48][80,48][80,48] LDPC code defined over Z4\mathbb{Z}_4Z4​ using quaternary phase-shift keying over the AWGN channel, and we show that the error-correcting performance of the proposed LP decoding algorithm is similar to that of the standard LP decoding using the simplex solver.