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

Optimal encoding, trellis structure, and normalized weight of linear block codes.

Houshou Chen

Published Jan 1, 1999• 3 citations
OpenAlex

Abstract

This thesis concentrates on studying three problems in error-correcting codes: optimal encoding, trellis structure, and normalized weight of linear block codes. In general, the research in error-correcting codes can be roughly classified into coding practice and coding theory. The problems in coding practice focus on codes and decoders with more attention on the subject of the tradeoffs between performance and complexity, e.g., soft-decision decoding, bit error probability, or trellis of the codes. On the other hand, coding theory concentrates on the structure of codes based on sophisticated mathematical techniques, with little concern for the decoding complexity, e.g., coset weight distribution, algebraic constructions, or bounds on possible parameters of the codes. In this dissertation, we will present three fundamental topics in coding practice: optimal encoding of linear block codes for bit error probability, trellis structure of linear block codes for trellis-based decoding, and normalized weight of block coded modulation for bandwidth efficient communication systems. The central theme of the thesis is to transform the problems of the above three topics in coding practice into problems in coding theory and to develop the theory associated with the problems. Much of this thesis is devoted to studying what 'optimal' means in different contexts. In summary, we investigated the optimal information bit encoding of a given linear block code for minimizing the probability of an information bit error, with the goal of determining an optimal generator matrix by using the structure of the code. We showed that many natural codes have systematic optimal generator matrices in the quiet region. We analyzed the trellis structure of a self-dual code C to minimize the trellis complexity of the code by considering all equivalent codes of C, with the goal of reducing the soft-decision decoding complexity via permutations on the codeword coordinates. We determined the length/dimension profile of all eight [32, 16, 8] self-dual codes, and find their corresponding optimum permutations. We examined the performance gains achievable by adding interblock memory to block coded modulation systems, with the goal of finding the best codes for normalized distance rather than Hamming distance. We found a large number of best codes for normalized distance for the cases of practical interest.

Related papers

On Optimal Codes for Additive Noise Channels

Al Moufid

One of the fundamental goals of coding theory is to find optimal codes, in terms of achieving the largest probability of correct decoding. Most of the foundational works on optimal codes use three assumptions. First, optimality is defined relative to a code’s rate and minimum Hamming distance, and not its probability of correct decoding. The problem is that the former conditions are not always good indicators for the latter. Second, for practicality only optimal codes with some kind of algebraic structure are considered, the most common being linearity. While linear codes have practical advantages, it is known that often the best codes are not linear. Thirdly, codes are usually proven optimal only for memoryless channels. However, there are many real-life channels which exhibit memory. Attempts to extend these results often make use of interleaving. This technique renders some of these channels with memory equivalent to a memoryless one with respect to the decoder. However, this comes with two disadvantages namely: we fail to exploit the channel’s memory and we add latency to the communication system. In this thesis, we seek optimal codes which require milder conditions than those aforementioned. Specifically, we describe a class of optimal q-ary block codes over additive noise channels, which are a generalization of a class of optimal codes from Hamada. We prove these codes are optimal using our novel method of analyzing the probability of correct decoding of block codes based on so-called error indexed decoder regions. Our method allows us to prove that these codes must be either a linear code or a coset of one.

•Sep 22, 2020•0 citations

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

A low-weight trellis-based iterative soft-decision decoding algorithm for binary linear block codes

Takuya Koumoto, T. Takata, Tadao Kasami +1 more

This paper presents a new low-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. The algorithm is devised based on a set of optimality conditions and the generation of a sequence of candidate codewords for an optimality test. The initial candidate codeword is generated by a simple decoding method. The subsequent candidate codewords, if needed, are generated by a chain of low-weight trellis searches, one at a time. Each search is conducted through a low-weight trellis diagram centered around the latest candidate codeword and results in an improvement over the previous candidate codewords that have been already tested. This improvement is then used as the next candidate codeword for a test of optimality. The decoding iteration stops whenever a candidate codeword is found to satisfy a sufficient condition on optimality or the latest low-weight trellis search results in a repetition of a previously generated candidate codeword. A divide-and-conquer technique is also presented for codes that are not spanned by their minimum-weight codewords. The proposed decoding algorithm has been applied to some well-known codes of lengths 48, 64, and 128. Simulation results show that the proposed algorithm achieves either practically optimal error performance for the example codes of length 48 and 64 or near optimal error performance for the (128, 29, 32) RM code with a significant reduction in computational decoding complexity.

IEEE Transactions on Information Theory•Mar 1, 1999•13 citations

Optimal information bit decoding of linear block codes

Aaron B. Kiely, J.T. Coffey, Mark R. Bell

We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>

IEEE Transactions on Information Theory•Jan 1, 1995•11 citations

On decoding algorithms for binary linear block codes

Bruce L. Montgomery

This dissertation investigates the complexity of minimum-distance decoding (MDD) algorithms for general binary linear block codes, and also investigates the use of such codes in constructing error correcting/detecting codes that are effective against both random and unidirectional errors. A new MDD algorithm is proposed, and its complexity is analyzed and compared to that of other such algorithms. The question of whether all good codes satisfy certain properties required for efficient implementation of the algorithm is also considered. The performance of decoding algorithms, with the information bit error rate as the criterion instead of the block error rate, is also studied. New decoding rules which can yield lower information bit error rates than the MDD rule are proposed and evaluated. A new class of binary codes is developed which corrects random errors and detects all unidirectional errors. These codes are obtained by appending a suffix to each codeword of a linear block code. To evaluate the efficiency of the new codes, a thorough comparison with the best previously obtained codes is made.

•Jan 1, 1987•0 citations

Decoding of linear block codes based on ordered statistics

M.P.C. Fossorier

This dissertation presents a novel approach to soft decision decoding for binary linear block codes. The basic idea of this approach is to achieve a desired error performance progressively in a number of stages. For each decoding stage, the error performance is highly bounded and the decoding is terminated at the stage where either near-optimum error performance or a desired level of error performance is achieved. As a result, more flexibility in the trade-off between performance and decoding complexity is provided. The proposed decoding is based on the reordering of the received symbols according to their reliability measure. In the dissertation, we evaluate the statistics of the noise after ordering. Based on these statistics, we derive two monotonic properties which dictate the reprocessing strategy. Each codeword is decoded in two steps: (1) hard-decision decoding based on reliability information and (2) reprocessing of the hard-decision decoded codeword in successive stages until the desired performance is achieved. The reprocessing is based on the monotonic properties of the ordering and is carried out using a cost function. A new resource test highly related to the reprocessing strategy is introduced to reduce the number of computations for each reprocessing stage. For short codes of lengths N ≤ 32 or medium codes with 32 < N ≤ 64 with rate R ≥ 0.6, near-optimum bit error performance is achieved in two stages of reprocessing with at most a computation complexity of o(K2) constructed code-words, where K is the dimension of the code. For longer codes, three or more reprocessing stages are required to achieve near-optimum decoding. However, most of the coding gain is obtained within the first two reprocessing stages for error performances of practical interest. The proposed decoding algorithm applies to any binary linear code, does not require any data storage and is well suitable for parallel processing. Furthermore, the maximum number of computations required at each reprocessing stage is fixed, which prevents buffer overflow at low SNR. Further reductions of the number of computations based on probabilistic or decomposable properties of the code considered are also investigated. The generalization of the algorithm to other channels is discussed. Finally, the discrete time channel associated with the AWGN model after ordering is greatly simplified. This simplification allows an important reduction of the number of computations required to evaluate the theoretical error performance of any algorithm based on a partial or total ordering.

•Jan 1, 1994•0 citations
This thesis concentrates on studying three problems in error-correcting codes: optimal encoding, trellis structure, and normalized weight of linear block codes. In general, the research in error-correcting codes can be roughly classified into coding practice and coding theory. The problems in coding practice focus on codes and decoders with more attention on the subject of the tradeoffs between performance and complexity, e.g., soft-decision decoding, bit error probability, or trellis of the codes. On the other hand, coding theory concentrates on the structure of codes based on sophisticated mathematical techniques, with little concern for the decoding complexity, e.g., coset weight distribution, algebraic constructions, or bounds on possible parameters of the codes. In this dissertation, we will present three fundamental topics in coding practice: optimal encoding of linear block codes for bit error probability, trellis structure of linear block codes for trellis-based decoding, and normalized weight of block coded modulation for bandwidth efficient communication systems. The central theme of the thesis is to transform the problems of the above three topics in coding practice into problems in coding theory and to develop the theory associated with the problems. Much of this thesis is devoted to studying what 'optimal' means in different contexts. In summary, we investigated the optimal information bit encoding of a given linear block code for minimizing the probability of an information bit error, with the goal of determining an optimal generator matrix by using the structure of the code. We showed that many natural codes have systematic optimal generator matrices in the quiet region. We analyzed the trellis structure of a self-dual code C to minimize the trellis complexity of the code by considering all equivalent codes of C, with the goal of reducing the soft-decision decoding complexity via permutations on the codeword coordinates. We determined the length/dimension profile of all eight [32, 16, 8] self-dual codes, and find their corresponding optimum permutations. We examined the performance gains achievable by adding interblock memory to block coded modulation systems, with the goal of finding the best codes for normalized distance rather than Hamming distance. We found a large number of best codes for normalized distance for the cases of practical interest.
One of the fundamental goals of coding theory is to find optimal codes, in terms of achieving the largest probability of correct decoding. Most of the foundational works on optimal codes use three assumptions. First, optimality is defined relative to a code’s rate and minimum Hamming distance, and not its probability of correct decoding. The problem is that the former conditions are not always good indicators for the latter. Second, for practicality only optimal codes with some kind of algebraic structure are considered, the most common being linearity. While linear codes have practical advantages, it is known that often the best codes are not linear. Thirdly, codes are usually proven optimal only for memoryless channels. However, there are many real-life channels which exhibit memory. Attempts to extend these results often make use of interleaving. This technique renders some of these channels with memory equivalent to a memoryless one with respect to the decoder. However, this comes with two disadvantages namely: we fail to exploit the channel’s memory and we add latency to the communication system. In this thesis, we seek optimal codes which require milder conditions than those aforementioned. Specifically, we describe a class of optimal q-ary block codes over additive noise channels, which are a generalization of a class of optimal codes from Hamada. We prove these codes are optimal using our novel method of analyzing the probability of correct decoding of block codes based on so-called error indexed decoder regions. Our method allows us to prove that these codes must be either a linear code or a coset of one.
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.
This paper presents a new low-weight trellis-based soft-decision iterative decoding algorithm for binary linear block codes. The algorithm is devised based on a set of optimality conditions and the generation of a sequence of candidate codewords for an optimality test. The initial candidate codeword is generated by a simple decoding method. The subsequent candidate codewords, if needed, are generated by a chain of low-weight trellis searches, one at a time. Each search is conducted through a low-weight trellis diagram centered around the latest candidate codeword and results in an improvement over the previous candidate codewords that have been already tested. This improvement is then used as the next candidate codeword for a test of optimality. The decoding iteration stops whenever a candidate codeword is found to satisfy a sufficient condition on optimality or the latest low-weight trellis search results in a repetition of a previously generated candidate codeword. A divide-and-conquer technique is also presented for codes that are not spanned by their minimum-weight codewords. The proposed decoding algorithm has been applied to some well-known codes of lengths 48, 64, and 128. Simulation results show that the proposed algorithm achieves either practically optimal error performance for the example codes of length 48 and 64 or near optimal error performance for the (128, 29, 32) RM code with a significant reduction in computational decoding complexity.
We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>
This dissertation investigates the complexity of minimum-distance decoding (MDD) algorithms for general binary linear block codes, and also investigates the use of such codes in constructing error correcting/detecting codes that are effective against both random and unidirectional errors. A new MDD algorithm is proposed, and its complexity is analyzed and compared to that of other such algorithms. The question of whether all good codes satisfy certain properties required for efficient implementation of the algorithm is also considered. The performance of decoding algorithms, with the information bit error rate as the criterion instead of the block error rate, is also studied. New decoding rules which can yield lower information bit error rates than the MDD rule are proposed and evaluated. A new class of binary codes is developed which corrects random errors and detects all unidirectional errors. These codes are obtained by appending a suffix to each codeword of a linear block code. To evaluate the efficiency of the new codes, a thorough comparison with the best previously obtained codes is made.
This dissertation presents a novel approach to soft decision decoding for binary linear block codes. The basic idea of this approach is to achieve a desired error performance progressively in a number of stages. For each decoding stage, the error performance is highly bounded and the decoding is terminated at the stage where either near-optimum error performance or a desired level of error performance is achieved. As a result, more flexibility in the trade-off between performance and decoding complexity is provided. The proposed decoding is based on the reordering of the received symbols according to their reliability measure. In the dissertation, we evaluate the statistics of the noise after ordering. Based on these statistics, we derive two monotonic properties which dictate the reprocessing strategy. Each codeword is decoded in two steps: (1) hard-decision decoding based on reliability information and (2) reprocessing of the hard-decision decoded codeword in successive stages until the desired performance is achieved. The reprocessing is based on the monotonic properties of the ordering and is carried out using a cost function. A new resource test highly related to the reprocessing strategy is introduced to reduce the number of computations for each reprocessing stage. For short codes of lengths N ≤ 32 or medium codes with 32 < N ≤ 64 with rate R ≥ 0.6, near-optimum bit error performance is achieved in two stages of reprocessing with at most a computation complexity of o(K2) constructed code-words, where K is the dimension of the code. For longer codes, three or more reprocessing stages are required to achieve near-optimum decoding. However, most of the coding gain is obtained within the first two reprocessing stages for error performances of practical interest. The proposed decoding algorithm applies to any binary linear code, does not require any data storage and is well suitable for parallel processing. Furthermore, the maximum number of computations required at each reprocessing stage is fixed, which prevents buffer overflow at low SNR. Further reductions of the number of computations based on probabilistic or decomposable properties of the code considered are also investigated. The generalization of the algorithm to other channels is discussed. Finally, the discrete time channel associated with the AWGN model after ordering is greatly simplified. This simplification allows an important reduction of the number of computations required to evaluate the theoretical error performance of any algorithm based on a partial or total ordering.