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

Cambridge University Press eBooks

Beyond BCH Codes

Richard E. Blahut

Published Feb 6, 2003• 0 citations
Publisher

Abstract

A digital communication system may transmit messages consisting of thousands or even millions of bits. While one can always break a long message into short blocks for encoding, in principle, a single, long block code will give better performance because it will protect against both error patterns in which the errors are clustered and error patterns in which the errors are scattered throughout the message. Therefore, there are many occasions where good codes of very long blocklength can be used. Although short binary cyclic codes can be quite good, the known long binary cyclic codes have a small minimum distance. Codes of large blocklength with a much larger minimum distance do in principle exist, though we know very little about these more powerful codes, nor do we know how to find them. Despite more than fifty years of intense effort, codes of large blocklength and large minimum distance, both binary and nonbinary, still elude us. Even if such codes were found, it may be that their decoding would be too complex. Accordingly, the most successful constructions for codes of large blocklength for many applications combine codes of small blocklength into more elaborate structures. We call such structures composite codes . The elementary codes from which composite codes are formed can then be called basic codes .

DOI
10.1017/cbo9780511800467.012

Related papers

Performance of Error-Control Codes

Richard E. Blahut

In any engineering discipline, one looks for methods of solving a given class of problems and then for methods of quantifying the performance and complexity of those solutions. Accordingly, in this chapter, we shall study performance in terms of the composition structure of block codes, and the probabilities of decoding error and of decoding failure. Later, after satisfactory methods are in hand, one turns to questions of optimality. Are these methods the best methods, and if not, in what ways and by how much are they inferior? To answer such questions, one needs to know how good are the known codes and how good are the best possible codes. Generally, we cannot answer either of these questions satisfactorily. Although for any given rate and blocklength, not too small, the best possible code is not known, a number of bounds are known – bounds beyond which no codes can exist, and bounds within which codes are sure to exist. We shall give some such bounds on the best possible codes later in this chapter. Knowledge of these bounds can deepen our understanding of the subject. Weight distributions of block codes If a linear block code has a minimum distance d min , then we know that at least one codeword of weight d min exists. Sometimes, we are not content with this single piece of information; we wish to know how many codewords have weight d min , and what are the weights of the other codewords.

Cambridge University Press eBooks•Feb 6, 2003•0 citations

The dual-containing primitive BCH codes with the maximum designed distance and their applications to quantum codes

Xueying Shi, Qin Yue, Yansheng Wu

Designs Codes and Cryptography•Feb 1, 2019•32 citations

Decoder Error Probability of Binary Linear Block Codes and Its Application to Binary Primitive BCH Codes

Mingoo Kim, Jae Hong Lee

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Apr 25, 1996•4 citations

Algebraic Constructions of Nonbinary Quasi-Cyclic LDPC Codes

Shu Hwa Lin, Shumei Song, Ying Tai +2 more

In the late 1950's and early 1960's, finite fields were successfully used to construct linear block codes, especially cyclic codes, with large minimum distances for correcting random errors with algebraic decoding, such as Bose-Chaudhuri-Hocqenghem (BCH) and Reed-Solomon (RS) codes. Recently it has been shown that finite fields can also be used successfully to construct binary quasi-cyclic (QC)-LDPC codes that perform very well not only over the AWGN channel but also over the binary erasure channel with iterative decoding, besides being efficiently encodable. This paper is concerned with constructions of nonbinary QC-LDPC codes based on finite fields

International Conference on Communications, Circuits and Systems•Jun 1, 2006•19 citations

Quantum BCH codes with maximum designed distance

Xinmei Huang, Qin Yue, Xiaoping Shi +1 more

Applicable Algebra in Engineering Communication and Computing•Jun 27, 2020•0 citations

Short-length Low-density Parity-check Codes: Construction and Decoding Algorithms

Cornelius T. Healy

Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.

•Jul 1, 2014•4 citations
A digital communication system may transmit messages consisting of thousands or even millions of bits. While one can always break a long message into short blocks for encoding, in principle, a single, long block code will give better performance because it will protect against both error patterns in which the errors are clustered and error patterns in which the errors are scattered throughout the message. Therefore, there are many occasions where good codes of very long blocklength can be used. Although short binary cyclic codes can be quite good, the known long binary cyclic codes have a small minimum distance. Codes of large blocklength with a much larger minimum distance do in principle exist, though we know very little about these more powerful codes, nor do we know how to find them. Despite more than fifty years of intense effort, codes of large blocklength and large minimum distance, both binary and nonbinary, still elude us. Even if such codes were found, it may be that their decoding would be too complex. Accordingly, the most successful constructions for codes of large blocklength for many applications combine codes of small blocklength into more elaborate structures. We call such structures composite codes . The elementary codes from which composite codes are formed can then be called basic codes .
In any engineering discipline, one looks for methods of solving a given class of problems and then for methods of quantifying the performance and complexity of those solutions. Accordingly, in this chapter, we shall study performance in terms of the composition structure of block codes, and the probabilities of decoding error and of decoding failure. Later, after satisfactory methods are in hand, one turns to questions of optimality. Are these methods the best methods, and if not, in what ways and by how much are they inferior? To answer such questions, one needs to know how good are the known codes and how good are the best possible codes. Generally, we cannot answer either of these questions satisfactorily. Although for any given rate and blocklength, not too small, the best possible code is not known, a number of bounds are known – bounds beyond which no codes can exist, and bounds within which codes are sure to exist. We shall give some such bounds on the best possible codes later in this chapter. Knowledge of these bounds can deepen our understanding of the subject. Weight distributions of block codes If a linear block code has a minimum distance d min , then we know that at least one codeword of weight d min exists. Sometimes, we are not content with this single piece of information; we wish to know how many codewords have weight d min , and what are the weights of the other codewords.
In the late 1950's and early 1960's, finite fields were successfully used to construct linear block codes, especially cyclic codes, with large minimum distances for correcting random errors with algebraic decoding, such as Bose-Chaudhuri-Hocqenghem (BCH) and Reed-Solomon (RS) codes. Recently it has been shown that finite fields can also be used successfully to construct binary quasi-cyclic (QC)-LDPC codes that perform very well not only over the AWGN channel but also over the binary erasure channel with iterative decoding, besides being efficiently encodable. This paper is concerned with constructions of nonbinary QC-LDPC codes based on finite fields
Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.