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)

Low-density parity-check codes with rates very close to the capacity of the q -ary symmetric channel for large q

Amin Shokrollahi, Wei Wang

Published Dec 23, 2004• 17 citations
Publisher

Abstract

Transmission of packets over computer networks is subject to packet-level errors, which appear as "bursts" of bit-level errors and are not well modeled by memoryless binary channels. A standard scrambling technique is used for transmission of packets by the q-ary symmetric channel (q-SC) with alphabet size q and error probability p. Furthermore, significant improvements in computational efficiency can be obtained by codes that operate at the packet-level instead of the bit-level. The capacity of the q-SC is 1+p log/sub q/ (p)+(1-p)log/sub q/ (1-p)-plog/sub q/ (1-q), which is close to 1-p for large q. First designed an efficient decoding algorithm for LDPC codes on the q-SC, and showed that it can afford rates arbitrarily close to 1-2p. We improve the analysis of this decoding algorithm to show that LDPC codes with the Tornado edge distribution, together with an erasure precode, can achieve rates e-close to capacity. We also extend this decoder into a family of decoding algorithms, which become progressively more powerful but also more complex. We show that in the limit, when the decoder is allowed to look infinitely deep into the decoding tree, it can achieve capacity without precoding. However computational requirements make this decoder impractical.

DOI
10.1109/isit.2004.1365310

Related papers

Verification-based decoding for packet-based LDPC codes over binary symmetric channels

Bin Benjamin Zhu

Research on low-density parity-check (LDPC) codes has traditionally been focused on small alphabets. With the development of communication networks and high-speed wireless communication systems, the operation units are normally blocks of bits organized as packets. Packet-based LDPC codes have a great potential to be used in multi-cast and content delivery networks to help achieve reliable communications. To decode packet-based LDPC codes, a verification-based decoding algorithm (VA) has been proposed by Luby and Mitzenmacher for q-ary symmetric channels (q-SC) with large q. However, as a packet-level block code, packet-based LDPC codes are most likely used as outer codes in concatenated coding schemes. Due to the fact that in a typical communication system, an interleaver is employed between the inner encoder and the outer encoder and the output from the inner decoder is normally in a hard-decision form, a binary symmetric channel (BSC) is thereby most proper to model such a scenario. We will show that in contrast to q-SC with large q, when VA is used for BSC, the probability that a packet is falsely verified plays a dominant role in determining system performance. In this dissertation, we propose an enhanced verification-based decoding algorithm (EVA) to improve the verification conditions and significantly reduce the possibility of the false verifications. In contrast to VA, EVA has much better performance over BSC with only moderate computation complexity increase. We also analyze the performance of VA and EVA over BSC. By reformulating VA (EVA) as a message-passing algorithm, a statistical model is proposed to analyze the frame error rate (FER) performance of VA (EVA). Using a recursive method to find the values of the parameters during the iterative process, the proposed model provides a good estimate of FER for the various packet sizes and channel parameters of practical interest.

•Jan 1, 2011•0 citations

Analysis of Verification-Based Decoding on the $q$-ary Symmetric Channel for Large $q$

Fan Zhang, Henry D. Pfister

A new verification-based message-passing decoder for low-density parity-check (LDPC) codes is introduced and analyzed for the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, this decoder passes lists of possible symbols and marks some lists as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list size is unbounded, then one finds that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q -SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list-size constraint. Simulation results are also presented to confirm the DE results. During the simulations, we observed differences between two verification-based decoding algorithms, introduced by Luby and Mitzenmacher, that were implicitly assumed to be identical. In this paper, the node-based algorithms are evaluated via analysis and simulation. The probability of false verification (FV) is also considered and techniques are discussed to mitigate the FV. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.

arXiv:0806.3243•IEEE Transactions on Information Theory•Oct 1, 2011•18 citations

List-Message Passing Achieves Capacity on the q-ary Symmetric Channel for Large q

Fan Zhang, Henry D. Pfister

We discuss and analyze a list-message-passing decoder with verification for low-density parity-check (LDPC) codes on the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, we pass lists of possible symbols and mark very likely symbols as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list-size is unbounded, then we find that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q-SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list-size constraint. The probability of false verification is considered for this case, and techniques are discussed to mitigate the problem. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.

Globecom•Nov 1, 2007•21 citations

Results on Punctured Low-Density Parity-Check Codes and Improved Iterative Decoding Techniques

Hossein Pishro-Nik, Faramarz Fekri

This paper first introduces an improved decoding algorithm for low-density parity-check (LDPC) codes over binary-input-output-symmetric memoryless channels. Then some fundamental properties of punctured LDPC codes are presented. It is proved that for any ensemble of LDPC codes, there exists a puncturing threshold. It is then proved that for any rates R1and R2satisfying 0121to R2resulting in asymptotically good codes for all rates R1lesRlesR2. Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. Bounds on the performance of punctured LDPC codes are also presented. It is also shown that punctured LDPC codes are as good as ordinary LDPC codes. For BEC and arbitrary positive numbers R121lesRlesR2is shown. Based on the above observations, a method is proposed to design good punctured LDPC codes over a broad range of rates. Finally, it is shown that the results of this paper may be used for the proof of the existence of the capacity-achieving LDPC codes over binary-input-output-symmetric memoryless channels

IEEE Transactions on Information Theory•Jan 23, 2007•98 citations

Analysis of decoding error probability for finite length LDPC codes

隆之 野崎

Low-density parity-check (LDPC) codes are linear codes defined by sparse parity check matrices.Due to the sparseness of the parity check matrices, LDPC codes are efficiently decoded by the belief propagation (BP) decoder.It is known that non-binary LDPC codes can outperform binary ones.However, the decoding complexity grows with the size of non-binary alphabets.Hence, there is a trade-off between performance and complexity.In this dissertation, we focus on both binary and non-binary LDPC codes.We analyze the decoding error probability for finite length LDPC codes under BP decoding.The curve of the decoding error probability for finite length LDPC codes, as a function of channel error probability, is divided into two regions called waterfall region and error floor region.We analyze the decoding error probability in the waterfall region for binary LDPC codes and in the error floor region for non-binary LDPC codes.The main results of this dissertation are summarized as follows:• We analyze the decoding erasure probabilities of waterfall regions for binary LDPC codes over binary erasure channels (BECs) without any assumptions by analytically solving the covariance evolution.• We propose a method to lower the decoding error rates in the error floors of non-binary LDPC codes defined over Galois field and general linear group transmitted over the BEC, the memoryless binary-input output-symmetric (MBIOS) channel and q-ary memoryless symmetric (q-MS) channel.Simulation results show that the decoding error rates of the codes designed by the proposed method outperform those of the codes designed by the conventional method proposed by Poulliat et al.• We give lower bounds of decoding error rates in the error floor regions for non-binary LDPC codes over the BEC, MBIOS channel and q-MS channel.Simulation results show that those lower bounds are tight.Moreover, we show that the decoding error rates for non-binary LDPC codes defined over general linear group have same decoding performance in the error floor regions with that for non-binary LDPC codes defined over Galois field.Furthermore, we show that this tight lower bound monotonically decreases, as the order of Galois field of non-binary LDPC code increases in the BEC and binary additive white Gaussian noise channel.iii • We derive the weight distribution of the decoding error patterns in the BP decoder for non-binary LDPC codes defined over general linear group transmitted over the BEC.

•Jan 1, 2012•0 citations

The capacity of low-density parity-check codes under message-passing decoding

Tom Richardson, Rudiger L. Urbanke

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.

IEEE Transactions on Information Theory•Jan 1, 2001•3,034 citations
Transmission of packets over computer networks is subject to packet-level errors, which appear as "bursts" of bit-level errors and are not well modeled by memoryless binary channels. A standard scrambling technique is used for transmission of packets by the q-ary symmetric channel (q-SC) with alphabet size q and error probability p. Furthermore, significant improvements in computational efficiency can be obtained by codes that operate at the packet-level instead of the bit-level. The capacity of the q-SC is 1+p log/sub q/ (p)+(1-p)log/sub q/ (1-p)-plog/sub q/ (1-q), which is close to 1-p for large q. First designed an efficient decoding algorithm for LDPC codes on the q-SC, and showed that it can afford rates arbitrarily close to 1-2p. We improve the analysis of this decoding algorithm to show that LDPC codes with the Tornado edge distribution, together with an erasure precode, can achieve rates e-close to capacity. We also extend this decoder into a family of decoding algorithms, which become progressively more powerful but also more complex. We show that in the limit, when the decoder is allowed to look infinitely deep into the decoding tree, it can achieve capacity without precoding. However computational requirements make this decoder impractical.
Research on low-density parity-check (LDPC) codes has traditionally been focused on small alphabets. With the development of communication networks and high-speed wireless communication systems, the operation units are normally blocks of bits organized as packets. Packet-based LDPC codes have a great potential to be used in multi-cast and content delivery networks to help achieve reliable communications. To decode packet-based LDPC codes, a verification-based decoding algorithm (VA) has been proposed by Luby and Mitzenmacher for q-ary symmetric channels (q-SC) with large q. However, as a packet-level block code, packet-based LDPC codes are most likely used as outer codes in concatenated coding schemes. Due to the fact that in a typical communication system, an interleaver is employed between the inner encoder and the outer encoder and the output from the inner decoder is normally in a hard-decision form, a binary symmetric channel (BSC) is thereby most proper to model such a scenario. We will show that in contrast to q-SC with large q, when VA is used for BSC, the probability that a packet is falsely verified plays a dominant role in determining system performance. In this dissertation, we propose an enhanced verification-based decoding algorithm (EVA) to improve the verification conditions and significantly reduce the possibility of the false verifications. In contrast to VA, EVA has much better performance over BSC with only moderate computation complexity increase. We also analyze the performance of VA and EVA over BSC. By reformulating VA (EVA) as a message-passing algorithm, a statistical model is proposed to analyze the frame error rate (FER) performance of VA (EVA). Using a recursive method to find the values of the parameters during the iterative process, the proposed model provides a good estimate of FER for the various packet sizes and channel parameters of practical interest.
Analysis of Verification-Based Decoding on the qqq-ary Symmetric Channel for Large qqq
A new verification-based message-passing decoder for low-density parity-check (LDPC) codes is introduced and analyzed for the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, this decoder passes lists of possible symbols and marks some lists as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list size is unbounded, then one finds that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q -SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list-size constraint. Simulation results are also presented to confirm the DE results. During the simulations, we observed differences between two verification-based decoding algorithms, introduced by Luby and Mitzenmacher, that were implicitly assumed to be identical. In this paper, the node-based algorithms are evaluated via analysis and simulation. The probability of false verification (FV) is also considered and techniques are discussed to mitigate the FV. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.
We discuss and analyze a list-message-passing decoder with verification for low-density parity-check (LDPC) codes on the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, we pass lists of possible symbols and mark very likely symbols as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list-size is unbounded, then we find that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q-SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list-size constraint. The probability of false verification is considered for this case, and techniques are discussed to mitigate the problem. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.
This paper first introduces an improved decoding algorithm for low-density parity-check (LDPC) codes over binary-input-output-symmetric memoryless channels. Then some fundamental properties of punctured LDPC codes are presented. It is proved that for any ensemble of LDPC codes, there exists a puncturing threshold. It is then proved that for any rates R1and R2satisfying 0121to R2resulting in asymptotically good codes for all rates R1lesRlesR2. Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. Bounds on the performance of punctured LDPC codes are also presented. It is also shown that punctured LDPC codes are as good as ordinary LDPC codes. For BEC and arbitrary positive numbers R121lesRlesR2is shown. Based on the above observations, a method is proposed to design good punctured LDPC codes over a broad range of rates. Finally, it is shown that the results of this paper may be used for the proof of the existence of the capacity-achieving LDPC codes over binary-input-output-symmetric memoryless channels
Low-density parity-check (LDPC) codes are linear codes defined by sparse parity check matrices.Due to the sparseness of the parity check matrices, LDPC codes are efficiently decoded by the belief propagation (BP) decoder.It is known that non-binary LDPC codes can outperform binary ones.However, the decoding complexity grows with the size of non-binary alphabets.Hence, there is a trade-off between performance and complexity.In this dissertation, we focus on both binary and non-binary LDPC codes.We analyze the decoding error probability for finite length LDPC codes under BP decoding.The curve of the decoding error probability for finite length LDPC codes, as a function of channel error probability, is divided into two regions called waterfall region and error floor region.We analyze the decoding error probability in the waterfall region for binary LDPC codes and in the error floor region for non-binary LDPC codes.The main results of this dissertation are summarized as follows:• We analyze the decoding erasure probabilities of waterfall regions for binary LDPC codes over binary erasure channels (BECs) without any assumptions by analytically solving the covariance evolution.• We propose a method to lower the decoding error rates in the error floors of non-binary LDPC codes defined over Galois field and general linear group transmitted over the BEC, the memoryless binary-input output-symmetric (MBIOS) channel and q-ary memoryless symmetric (q-MS) channel.Simulation results show that the decoding error rates of the codes designed by the proposed method outperform those of the codes designed by the conventional method proposed by Poulliat et al.• We give lower bounds of decoding error rates in the error floor regions for non-binary LDPC codes over the BEC, MBIOS channel and q-MS channel.Simulation results show that those lower bounds are tight.Moreover, we show that the decoding error rates for non-binary LDPC codes defined over general linear group have same decoding performance in the error floor regions with that for non-binary LDPC codes defined over Galois field.Furthermore, we show that this tight lower bound monotonically decreases, as the order of Galois field of non-binary LDPC code increases in the BEC and binary additive white Gaussian noise channel.iii • We derive the weight distribution of the decoding error patterns in the BP decoder for non-binary LDPC codes defined over general linear group transmitted over the BEC.
We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.