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 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 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.
In this chapter, we continue the discussion on concatenated codes, which was initiated in Section 5.4. The main message to be conveyed in this chapter is that by using concatenation, one can obtain codes with favorable asymptotic performance—in a sense to be quantified more precisely—while the complexity of constructing these codes and decoding them grows polynomially with the code length. We first present a decoding algorithm for concatenated codes, due to Forney. This algorithm, referred to as a generalized minimum distance (in short, GMD) decoder, corrects any error pattern whose Hamming weight is less than half the product of the minimum distances of the inner and outer codes (we recall that this product is a lower bound on the minimum distance of the respective concatenated code). A GMD decoder consists of a nearest-codeword decoder for the inner code, and a combined error–erasure decoder for the outer code. It then enumerates over a threshold value, marking the output of the inner decoder as erasure if that decoder returns an inner codeword whose Hamming distance from the respective received sub-word equals or exceeds that threshold. We show that under our assumption on the overall Hamming weight of the error word, there is at least one threshold for which the outer decoder recovers the correct codeword. If the outer code is taken as a GRS code, then a GMD decoder has an implementation with time complexity that is at most quadratic in the length of the concatenated code.
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.
We study relationships between worst-case and random-noise properties of error correcting codes. More concretely, we consider connections between minimum distance, list decoding radius, and block error probability on noisy channels. A recent result of Pernice, Sprumont, and Wootters established the tight connection between list decoding radius and symmetric channel performance for linear codes. We extend this result to general codes. The proof proceeds by directly bounding the weight distribution rather than by sharp threshold techniques. We then turn to the relation between minimum distance and symmetric channel performance. The results we just described imply that a q-ary code of relative distance δ has vanishing error probability on the symmetric channel up to the Johnson radius Jq(δ). We improve upon this bound in the case of linear codes, for a range δ, for q≥4. In our proof we consider the \emph{erasure} properties of codes, and bound their weight distribution through inequalities introduced by Samorodnitsky. The latter part of the proof gives a more general technique that bounds the symmetric channel performance of a linear code with constant relative distance and good erasure channel performance.
The discovery of turbo codes [5] and the subsequent rediscovery of low-density parity-check (LDPC) codes [9, 18] represent a major milestone in the field of coding theory. These two classes of codes can achieve realistic bit error rates, between 10−5 and 10−12, with signalto- noise ratios that are only slightly above the minimum possible for a given channel and code rate established by Shannon’s original capacity theorems. In this sense, these codes are said to be near-capacity-achieving codes and are sometimes considered to have solved (in the engineering sense, at least) the coding problem for the additive white Gaussian noise (AWGN) channel and its derivative channels. Perhaps the most important commonality between turbo and low-density parity-check codes is that they both utilize iterative message-passing decoding algorithms. For turbo codes, one uses the so-called turbo decoding algorithm, and for LDPC codes, both the sumproduct (SP) and the min-sum (MS) algorithms are used. The success of the various iterative message-passing algorithms is sometimes said to have ushered in a new era of “modern” coding theory in which the design emphasis has shifted from optimizing some code property, such as minimum distance, to optimizing the corresponding decoding structure of the code, such as the degree profile [24, 25], with respect to the behavior of a message-passing decoder. As successful as these codes and decoders have been in terms of application, there are several major questions that must be answered before a complete understanding of them can be achieved. The theoretical research in the area of capacity-achieving codes is focused on two main themes. The first theme is whether different types of capacity-achieving codes have common encoder and structural properties. In [17], it was claimed that turbo codes could be viewed as LDPC codes, but the relationship was not made explicit. More recently, P´erez, his student Jiang, and others [11, 16] developed a construction for the parity-check matrices of arbitrary turbo codes that clearly connects the components of the turbo encoder to the resulting structure of the parity-check matrix. From a more abstract perspective, turbo codes and low-density parity-check codes are examples of codes with long block lengths that exhibit the random structure inherent in Shannon’s original theorems. The second and more active research theme is the determination of the behavior of iterative message-passing decoding and the relationships between the various decoding algorithms. The dominant problem in this area is to understand the non-codeword decoder errors that occur in computer simulations of LDPC codes with iterative message-passing decoders. Motivated by empirical observations of the non-codeword outputs of LDPC decoders, the notion of stopping sets was first introduced by Forney, et al. [8] in 2001. Two years later, a formal definition of stopping sets was given by Changyan, et al. [6]. They demonstrated that the bit and block error probabilities of iteratively decoded LDPC codes on the binary erasure channel (BEC) can be determined exactly from the stopping sets of the parity-check matrix. (Here, a stopping set S is a subset of the set of variable nodes such that all neighboring check nodes of S are connected to S at least twice.)