We detail a field-programmable gate array (FPGA) based implementation of linearprogramming (LP) decoding. LP decoding frames error correction as an optimization problem. This is in contrast to variants of belief prop...
详细信息
ISBN:
(纸本)9781509041176
We detail a field-programmable gate array (FPGA) based implementation of linearprogramming (LP) decoding. LP decoding frames error correction as an optimization problem. This is in contrast to variants of belief propagation (BP) that view error correction as a problem of graphical inference. LP decoding, when implemented with standard LP solvers, does not easily scale to the block-lengths of modern error-correction codes. This is the main challenge we surmount in this paper. In earlier work we demonstrated how to draw on decomposition methods from optimization theory to build an LP decoding solver competitive with BP, in terms of both performance and speed, but only in double-precision floating point. In this paper we translate the novel computational primitives of our new LP decoding technique into fixed-point. Using our FPGA implementation, we demonstrate that error-rate performance very close to double-precision is possible with 10-bit fixed-point messages.
In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write r...
详细信息
In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write resolutions than read resolutions. The proposed decoding algorithm is based on linearprogramming (LP). For LDPC codes, the proposed algorithm runs in time polynomial in the codeword length. It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance d(fp) of the code, which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to. inverted left perpendiculard(fp)/2inverted right perpendicular - 1 errors.
We detail a field-programmable gate array (FPGA) based implementation of linearprogramming (LP) decoding. LP decoding frames error correction as an optimization problem. This is in contrast to variants of belief prop...
详细信息
ISBN:
(纸本)9781509041183
We detail a field-programmable gate array (FPGA) based implementation of linearprogramming (LP) decoding. LP decoding frames error correction as an optimization problem. This is in contrast to variants of belief propagation (BP) that view error correction as a problem of graphical inference. LP decoding, when implemented with standard LP solvers, does not easily scale to the block-lengths of modern error-correction codes. This is the main challenge we surmount in this paper. In earlier work we demonstrated how to draw on decomposition methods from optimization theory to build an LP decoding solver competitive with BP, in terms of both performance and speed, but only in double-precision floating point. In this paper we translate the novel computational primitives of our new LP decoding technique into fixed-point. Using our FPGA implementation, we demonstrate that error-rate performance very close to double-precision is possible with 10-bit fixed-point messages.
The Euclidean projection onto check polytopes is the most time-consuming operation in the linearprogramming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC...
详细信息
The Euclidean projection onto check polytopes is the most time-consuming operation in the linearprogramming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC) codes. In this letter, instead of reducing the complexity of Euclidean projection itself, we propose a new method to reduce the decoding complexity of ADMM-based LP decoder by decreasing the number of Euclidean projections. In particular, if all absolute values of the element-wise differences between the input vector of Euclidean projection in the current iteration and that in the previous iteration are less than a predefined value, then the Euclidean projection at the current iteration will be no longer performed. Simulation results show that the proposed decoder can still save roughly 20% decoding time even if both the over-relaxation and early termination techniques are used.
While in the past several decades the trend to go towards increasing error-correcting code lengths was predominant to get closer to the Shannon limit, applications that require short block length are developing. There...
详细信息
ISBN:
(纸本)9781728176055
While in the past several decades the trend to go towards increasing error-correcting code lengths was predominant to get closer to the Shannon limit, applications that require short block length are developing. Therefore, decoding techniques that can achieve near-maximum-likelihood (near-ML) are gaining momentum. This overview paper surveys recent progress in this emerging field by reviewing the GRAND algorithm, linear programming decoding, machine-learning aided decoding and the recursive projection-aggregation decoding algorithm. For each of the decoding algorithms, both algorithmic and hardware implementations are considered, and future research directions are outlined.
In this letter, we develop an efficient linearprogramming (LP) decoding algorithm for low-density parity-check (LDPC) codes. The LP relaxation is formulated based on a check-node decomposition approach. Our main cont...
详细信息
In this letter, we develop an efficient linearprogramming (LP) decoding algorithm for low-density parity-check (LDPC) codes. The LP relaxation is formulated based on a check-node decomposition approach. Our main contributions are as follows. First, we propose an algorithm based on the alternating direction method of multipliers (ADMM) technique to solve this LP relaxation. By exploiting the orthogonality structure of the LP model, each ADMM update step can be implemented in parallel. Second, the proposed decoding algorithm under this LP formulation eliminates the Euclidean projection on the check polytope compared with the existing ADMM-based LP decoding algorithms. Third, the feasibility analysis of the proposed algorithm is presented. Moveover, complexity analysis shows that our proposed LP decoder in each iteration has a lower complexity than the state-of-the-art ADMM-based LP decoders. Simulation results demonstrate that the proposed LP decoder achieves better performance than other competing ADMM-based LP decoders in terms of decoding time.
Iterative decoding and linear programming decoding are guaranteed to converge to the maximum-likelihood codeword when the underlying Tanner graph is cycle-free. Therefore, cycles are usually seen as the culprit of low...
详细信息
Iterative decoding and linear programming decoding are guaranteed to converge to the maximum-likelihood codeword when the underlying Tanner graph is cycle-free. Therefore, cycles are usually seen as the culprit of low-density parity-check codes. In this paper, we argue in the context of graph cover pseudocodeword that, for a code that permits a cycle-free Tanner graph, cycles have no effect on error performance as long as they are a part of redundant rows. Specifically, we characterize all parity-check matrices that are pseudocodeword-free for such class of codes.
Random (d(v), d(c))-regular low-density paritycheck (LDPC) codes, where each variable is involved in dv parity checks and each parity check involves dc variables are well-known to achieve the Shannon capacity of the b...
详细信息
Random (d(v), d(c))-regular low-density paritycheck (LDPC) codes, where each variable is involved in dv parity checks and each parity check involves dc variables are well-known to achieve the Shannon capacity of the binary symmetric channel, for sufficiently large dv and dc, under exponential time decoding. However, polynomial time algorithms are only known to correct a much smaller fraction of errors. One of the most powerful polynomial-time algorithms with a formal analysis is the linearprogramming (LP) decoding algorithm of Feldman et al., which is known to correct an Omega(1/d(c)) fraction of errors. In this paper, we show that fairly powerful extensions of LP decoding, based on the Sherali-Adams and Lasserre hierarchies, fail to correct much more errors than the basic LP-decoder. In particular, we show that: 1) for any values of dv and dc, a linear number of rounds of the Sherali-Adams LP hierarchy cannot correct more than an O(1/d(c)) fraction of errors on a random (dv, dc)-regular LDPC code;and 2) for any value of dv and infinitely many values of dc, a linear number of rounds of the Lasserre SDP hierarchy cannot correct more than an O(1/dc) fraction of errors on a random (dv, dc)-regular LDPC code. Our proofs use a new stretching and collapsing technique that allows us to leverage recent progress in the study of the limitations of LP/SDP hierarchies for Maximum Constraint Satisfaction Problems (Max-CSPs). The problem then reduces to the construction of special balanced pairwise independent distributions for Sherali-Adams and special cosets of balanced pairwise independent subgroups for Lasserre. Our (algebraic) construction for the Lasserre hierarchy is based on designing sets of points in F-q(d) (for q any power of 2 and d = 2, 3) with special hyperplane-incidence properties-constructions that may be of independent interest. An intriguing consequence of our work is that expansion seems to be both the strength and the weakness of random regular LDPC codes. S
We examine LDPC codes decoded using linearprogramming (LP). Four contributions to the LP framework are presented. First, a new method of tightening the LP relaxation, and thus improving the LP decoder, is proposed. S...
详细信息
We examine LDPC codes decoded using linearprogramming (LP). Four contributions to the LP framework are presented. First, a new method of tightening the LP relaxation, and thus improving the LP decoder, is proposed. Second, we present an algorithm which calculates a lower bound on the minimum distance of a specific code. This algorithm exhibits complexity which scales quadratically with the block length. Third, we propose a method to obtain a tight lower bound on the fractional distance, also with quadratic complexity, and thus less than previously-existing methods. Finally, we show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained.
Random (d(v), d(c))-regular low-density paritycheck (LDPC) codes, where each variable is involved in dv parity checks and each parity check involves dc variables are well-known to achieve the Shannon capacity of the b...
详细信息
ISBN:
(纸本)9781611973747
Random (d(v), d(c))-regular low-density paritycheck (LDPC) codes, where each variable is involved in dv parity checks and each parity check involves dc variables are well-known to achieve the Shannon capacity of the binary symmetric channel, for sufficiently large dv and dc, under exponential time decoding. However, polynomial time algorithms are only known to correct a much smaller fraction of errors. One of the most powerful polynomial-time algorithms with a formal analysis is the linearprogramming (LP) decoding algorithm of Feldman et al., which is known to correct an Omega(1/d(c)) fraction of errors. In this paper, we show that fairly powerful extensions of LP decoding, based on the Sherali-Adams and Lasserre hierarchies, fail to correct much more errors than the basic LP-decoder. In particular, we show that: 1) for any values of dv and dc, a linear number of rounds of the Sherali-Adams LP hierarchy cannot correct more than an O(1/d(c)) fraction of errors on a random (dv, dc)-regular LDPC code;and 2) for any value of dv and infinitely many values of dc, a linear number of rounds of the Lasserre SDP hierarchy cannot correct more than an O(1/dc) fraction of errors on a random (dv, dc)-regular LDPC code. Our proofs use a new stretching and collapsing technique that allows us to leverage recent progress in the study of the limitations of LP/SDP hierarchies for Maximum Constraint Satisfaction Problems (Max-CSPs). The problem then reduces to the construction of special balanced pairwise independent distributions for Sherali-Adams and special cosets of balanced pairwise independent subgroups for Lasserre. Our (algebraic) construction for the Lasserre hierarchy is based on designing sets of points in F-q(d) (for q any power of 2 and d = 2, 3) with special hyperplane-incidence properties-constructions that may be of independent interest. An intriguing consequence of our work is that expansion seems to be both the strength and the weakness of random regular LDPC codes. S
暂无评论