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)

Statistical approach to ML decoding of linear block codes on symmetric channels

Haris Vikalo, Babak Hassibi

Published Dec 23, 2004• 3 citations
Publisher

Abstract

Maximum-likelihood (ML) decoding of linear block codes on a symmetric channel is studied. Exact ML decoding is known to be computationally difficult. We propose an algorithm that finds the exact solution to the ML decoding problem by performing a depth-first search on a tree. The tree is designed from the code generator matrix and pruned based on the statistics of the channel noise. The complexity of the algorithm is a random variable. We characterize the complexity by means of its first moment, which for binary symmetric channels we find in closed-form. The obtained results indicate that the expected complexity of the algorithm is low over a wide range of system parameters.

DOI
10.1109/isit.2004.1365558

Related papers

On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes: A New Perspective

Weiyu Xu, Babak Hassibi

Abstract — The problem of exact maximum-likelihood (ML) decoding of general linear codes is well-known to be NP-hard. In this paper, we show that exact ML decoding of a class of asymptotically good low density parity check codes—expander codes—over binary symmetric channels (BSCs) is possible with an average-case polynomial complexity. This offers a new way of looking at the complexity issue of exact ML decoding for communication systems where the randomness in channel plays a fundamental central role. More precisely, for any bit-flipping probability p in a nontrivial range, there exists a rate region of non-zero support and a family of asymptotically good codes which achieve error probability exponentially decaying in coding length n while admitting exact ML decoding in average-case polynomial time.As p approaches zero, this rate region approaches the Shannon channel capacity region. Similar results can be extended to AWGN channels, suggesting it may be feasible to eliminate the error floor phenomenon associated with belief-propagation decoding of LDPC codes in the high SNR regime. The derivations are based on a hierarchy of ML certificate decoding algorithms adaptive to the channel realization.In this process, we propose an efficient O(n 2) new ML certificate algorithm based on the maxflow algorithm. Moreover, exact ML decoding of the considered class of codes constructed from LDPC codes with regular left degree, of which the considered expander codes are a special case, remains NP-hard; thus giving an interesting contrast between the worst-case and average-case complexities. I.

•Sep 24, 2007•6 citations

On the Complexity of Exact Maximum-Likelihood Decoding for Asymptotically Good Low Density Parity Check Codes: A New Perspective

Weiyu Xu, Babak Hassibi

The problem of exact maximum-likelihood (ML) decoding of general linear codes is well-known to be NP-hard. In this paper, we show that exact ML decoding of a class of asymptotically good low density parity check codes - expander codes - over binary symmetric channels (BSCs) is possible with an average-case polynomial complexity. This offers a new way of looking at the complexity issue of exact ML decoding for communication systems where the randomness in channel plays a fundamental central role. More precisely, for any bit-flipping probabilitypin a nontrivial range, there exists a rate region of non-zero support and a family of asymptotically good codes which achieve error probability exponentially decaying in coding lengthnwhile admitting exact ML decoding in average-case polynomial time. Aspapproaches zero, this rate region approaches the Shannon channel capacity region. Similar results can be extended to AWGN channels, suggesting it may be feasible to eliminate the error floor phenomenon associated with belief-propagation decoding of LDPC codes in the high SNR regime. The derivations are based on a hierarchy of ML certificate decoding algorithms adaptive to the channel realization.In this process, we propose an efficientO(n2) new ML certificate algorithm based on the max-flow algorithm. Moreover, exact ML decoding of the considered class of codes constructed from LDPC codes with regular left degree, of which the considered expander codes are a special case, remains NP-hard; thus giving an interesting contrast between the worst-case and average-case complexities.

arXiv:cs/0702147•IEEE Information Theory Workshop (ITW)•Sep 1, 2007•6 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

An algorithm for calculating the exact bit error probability of a binary linear code over the binary symmetric channel

T. Wadayama

An efficient algorithm for calculating the i-th bit error probability of a binary linear code over the binary symmetric channel (BSC) are presented. It is proved that the exact i-th bit error probability of maximum likelihood (ML) decoding, bounded distance decoding, symbolwise maximum a posteriori probability (MAP) decoding and symbolwise MAP decoding with erasure can be obtained with time complexity O(n2/sup n-k/), where n, k denote length and dimension of the target code.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•0 citations

An Algorithm for Calculating the Exact Bit Error Probability of a Binary Linear Code Over the Binary Symmetric Channel

Tadashi Wadayama

An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2/sup n-k/), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer.

IEEE Transactions on Information Theory•Feb 1, 2004•4 citations

ML Soft-decision Decoding for Binary Linear Block Codes Based on Trellises of Their Supercodes

Ting-Yi Wu, Yunghsiang Sam Han

Based on the notion of supercodes, we propose a two-phase maximum-likelihood (ML) soft-decision decoding (tpMLSD) algorithm for binary linear block codes in this work. The first phase applies the priority-first search algorithm backwardly to a trellis derived from the parity-check matrix of the supercode of the linear block code. Using the information retained from the first phase, the second phase employs the priority-first search algorithm to the trellis corresponding to the linear block code itself, which guarantees to find the ML decision with a constant complexity per information bit at high signal-to-noise ratios (SNRs). Simulations on the extended BCH code of n = 64 and k = 24 show that the proposed two-phase scheme is an order of magnitude more efficient in average decoding complexity than the recursive ML decoding [1] when the SNR per information bit is 8 dB.

International Conference on Computer Communications and Networks (ICCCN)•Aug 1, 2020•1 citation
Maximum-likelihood (ML) decoding of linear block codes on a symmetric channel is studied. Exact ML decoding is known to be computationally difficult. We propose an algorithm that finds the exact solution to the ML decoding problem by performing a depth-first search on a tree. The tree is designed from the code generator matrix and pruned based on the statistics of the channel noise. The complexity of the algorithm is a random variable. We characterize the complexity by means of its first moment, which for binary symmetric channels we find in closed-form. The obtained results indicate that the expected complexity of the algorithm is low over a wide range of system parameters.
Abstract — The problem of exact maximum-likelihood (ML) decoding of general linear codes is well-known to be NP-hard. In this paper, we show that exact ML decoding of a class of asymptotically good low density parity check codes—expander codes—over binary symmetric channels (BSCs) is possible with an average-case polynomial complexity. This offers a new way of looking at the complexity issue of exact ML decoding for communication systems where the randomness in channel plays a fundamental central role. More precisely, for any bit-flipping probability p in a nontrivial range, there exists a rate region of non-zero support and a family of asymptotically good codes which achieve error probability exponentially decaying in coding length n while admitting exact ML decoding in average-case polynomial time.As p approaches zero, this rate region approaches the Shannon channel capacity region. Similar results can be extended to AWGN channels, suggesting it may be feasible to eliminate the error floor phenomenon associated with belief-propagation decoding of LDPC codes in the high SNR regime. The derivations are based on a hierarchy of ML certificate decoding algorithms adaptive to the channel realization.In this process, we propose an efficient O(n 2) new ML certificate algorithm based on the maxflow algorithm. Moreover, exact ML decoding of the considered class of codes constructed from LDPC codes with regular left degree, of which the considered expander codes are a special case, remains NP-hard; thus giving an interesting contrast between the worst-case and average-case complexities. I.
The problem of exact maximum-likelihood (ML) decoding of general linear codes is well-known to be NP-hard. In this paper, we show that exact ML decoding of a class of asymptotically good low density parity check codes - expander codes - over binary symmetric channels (BSCs) is possible with an average-case polynomial complexity. This offers a new way of looking at the complexity issue of exact ML decoding for communication systems where the randomness in channel plays a fundamental central role. More precisely, for any bit-flipping probabilitypin a nontrivial range, there exists a rate region of non-zero support and a family of asymptotically good codes which achieve error probability exponentially decaying in coding lengthnwhile admitting exact ML decoding in average-case polynomial time. Aspapproaches zero, this rate region approaches the Shannon channel capacity region. Similar results can be extended to AWGN channels, suggesting it may be feasible to eliminate the error floor phenomenon associated with belief-propagation decoding of LDPC codes in the high SNR regime. The derivations are based on a hierarchy of ML certificate decoding algorithms adaptive to the channel realization.In this process, we propose an efficientO(n2) new ML certificate algorithm based on the max-flow algorithm. Moreover, exact ML decoding of the considered class of codes constructed from LDPC codes with regular left degree, of which the considered expander codes are a special case, remains NP-hard; thus giving an interesting contrast between the worst-case and average-case complexities.
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.
An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2/sup n-k/), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer.
Based on the notion of supercodes, we propose a two-phase maximum-likelihood (ML) soft-decision decoding (tpMLSD) algorithm for binary linear block codes in this work. The first phase applies the priority-first search algorithm backwardly to a trellis derived from the parity-check matrix of the supercode of the linear block code. Using the information retained from the first phase, the second phase employs the priority-first search algorithm to the trellis corresponding to the linear block code itself, which guarantees to find the ML decision with a constant complexity per information bit at high signal-to-noise ratios (SNRs). Simulations on the extended BCH code of n = 64 and k = 24 show that the proposed two-phase scheme is an order of magnitude more efficient in average decoding complexity than the recursive ML decoding [1] when the SNR per information bit is 8 dB.