Generalized IRA Erasure Correcting Codes for Hybrid Iterative/Maximum Likelihood Decoding

The design of low-density parity-check (LDPC) codes under hybrid iterative / maximum likelihood decoding is addressed for the binary erasure channel (BEC). Specifically, we focus on generalized irregular repeat-accumulate (GeIRA) codes, which offer both efficient encoding and design flexibility. We show that properly designed GeIRA codes tightly approach the performance of an ideal maximum distance separable (MDS) code, even for short block sizes. For example, our (2048,1024) code reaches a codeword error rate of 10^-5 at channel erasure probability isin= 0.450, where an ideal (2048,1024) MDS code would reach the same error rate at isin = 0.453.     

The MMD codes are proper for error detection

The undetected error probability of a linear code used to detect errors on a symmetric channel is a function of the symbol error probability /spl epsi/ of the channel and involves the weight distribution of the code. The code is proper, if the undetected error probability increases monotonously in /spl epsi/. Proper codes are generally considered to perform well in error detection. We show in this correspondence that maximum minimum distance (MMD) codes are proper.     

Improved Analysis of List Decoding and Its Application to Convolutional Codes and Turbo Codes

A list decoder generates a list of more than one codeword candidates, and decoding is erroneous if the transmitted codeword is not included in the list. This decoding strategy can be implemented in a system that employs an inner error correcting code and an outer error detecting code that is used to choose the correct codeword from the list. Probability of codeword error analysis for a linear block code with list decoding is typically based on the "worst case" lower bound on the effective weights of codewords for list decoding evaluated from the weight enumerating function of the code. In this paper, the concepts of generalized pairwise error event and effective weight enumerating function are proposed for evaluation of the probability of codeword error of linear block codes with list decoding. Geometrical analysis shows that the effective Euclidean distances are not necessarily as low as those predicted by the lower bound. An approach to evaluate the effective weight enumerating function of a particular code with list decoding is proposed. The effective Euclidean distances for decisions in each pairwise error event are evaluated taking into consideration the actual Hamming distance relationships between codewords, which relaxes the pessimistic assumptions upon which the traditional lower bound analysis is based. Using the effective weight enumerating function, a more accurate approximation is achieved for the probability of codeword error of the code with list decoding. The proposed approach is applied to codes of practical interest, including terminated convolutional codes and turbo codes with the parallel concatenation structure     

Asymptotic optimality of the GMD and Chase decoding algorithms

The generalized minimum distance (GMD) and Chase (1972) decoding algorithms are some of the most important suboptimum bounded distance decoding algorithms for binary linear block codes over an additive white Gaussian noise (AWGN) channel. We compute the limitation of the ratio between the probability of decoding error for the GMD or any one of the Chase decoding algorithms and that of the maximum-likelihood (ML) decoding when the signal-to-noise ratio (SNR) approaches infinity. If the minimum Hamming distance of the code is greater than 2, the limitation is shown to be equal to 1 and thus the GMD and Chase decoding algorithms are asymptotically optimum.     

Undetected error probabilities of binary primitive BCH codes forboth error correction and detection

We investigate the undetected error probabilities for bounded-distance decoding of binary primitive BCH codes when they are used for both error correction and detection on a binary symmetric channel. We show that the undetected error probability of binary linear codes can be simplified and quantified if the weight distribution of the code is binomial-like. We obtain bounds on the undetected error probability of binary primitive BCH codes by applying the result to the code and show that the bounds are quantified by the deviation factor of the true weight distribution from the binomial-like weight distribution     

The duals of MMD codes are proper for error detection

A linear code, when used for error detection on a symmetric channel, is said to be proper if the corresponding undetected error probability increases monotonically in /spl epsiv/, the symbol error probability of the channel. Such codes are generally considered to perform well in error detection. A number of well-known classes of linear codes are proper, e.g., the perfect codes, MDS codes, MacDonald's codes, MMD codes, and some Near-MDS codes. The aim of this work is to show that also the duals of MMD codes are proper.     

Performance of a general decoding technique over the class ofrandomly chosen parity check codes

The paper extends a general decoding technique developed by Metzner and Kapturowski (1990) for concatenated code outer codes and for file disagreement location. That work showed the ability to correct most cases of d-2 or fewer erroneous block symbols, where d is the outer code minimum distance. Any parity check code can be used as the basis for the outer codes, and yet decoding complexity increases at most as the third power of the code length. In this correspondence, it is shown that, with a slight modification and no significant increase in complexity, the general decoding technique can be applied to the correction of many other cases beyond the code minimum distance. By considering average performance over all binary randomly chosen codes, it is seen that most error patterns of t_M or fewer block errors can be corrected, where: 1) t_M in most cases is much greater than the code minimum distance, and 2) asymptotically, the ratio of t_M to the theoretical maximum (the number of parity symbol blocks) approaches 1. Moreover, most cases of noncorrectable error block patterns are detected     

On the design and selection of convolutional codes for anuninterleaved, bursty Rician channel

This article focuses on code design and code selection rules under power and decoding delay constraints for an antipodal (BPSK) modulated and convolutionally encoded communication system. The system operates over a slowly fading AWGN channel, described by the block-fading model. We emphasize perfect coherent detection with maximum likelihood decoding assuming ideal channel information (the instantaneous fading values). The dominant design criterion in this scenario is the code diversity level in terms of blocks while the standard Hamming distance plays a secondary role. A code design procedure, based on maximum distance separable (MDS) cyclic block codes is presented along with a code-search algorithm. The performance results of selected codes are assessed via simulation and compared to those achieved by Reed-Solomon codes with erasure and error decoding     

Estimating the fraction of erasure patterns correctable by linear codes

The conditional probability (fraction) of the successful decoding of erasure patterns of high (greater than the code distance) weights is investigated for linear codes with the partially known or unknown weight spectra of code words. The estimated conditional probabilities and the methods used to calculate them refer to arbitrary binary linear codes and binary Hamming, Panchenko, and Bose–Chaudhuri–Hocquenghem (BCH) codes, including their extended and shortened forms. Error detection probabilities are estimated under erasure-correction conditions. The product-code decoding algorithms involving the correction of high weight erasures by means of component Hamming, Panchenko, and BCH codes are proposed, and the upper estimate of decoding failure probability is presented.     

Weight Distribution of Low-Density Parity-Check Codes

We derive the average weight distribution function and its asymptotic growth rate for low-density parity-check (LDPC) code ensembles. We show that the growth rate of the minimum distance of LDPC codes depends only on the degree distribution pair. It turns out that capacity-achieving sequences of standard (unstructured) LDPC codes under iterative decoding over the binary erasure channel (BEC) known to date have sublinearly growing minimum distance in the block length     

On the weight distribution of linear codes having dual distanced'⩾k

Using only the principle of inclusion and exclusion, the author derives a formula for the weight distribution of an [n,k ] code whose dual code has a minimum distance d'⩾k . The result yields a new condition on the weight distributions of a linear code and its dual which is necessary and sufficient for the code to be a maximum distance separable (MDS) code. Moreover, it shows how the weight distribution for linear MDS codes is obtained in an elementary manner     

Dimension/length profiles and trellis complexity of linear blockcodes

This semi-tutorial paper discusses the connections between the dimension/length profile (DLP) of a linear code, which is essentially the same as its “generalized Hamming weight hierarchy”, and the complexity of its minimal trellis diagram. These connections are close and deep. DLP duality is closely related to trellis duality. The DLP of a code gives tight bounds on its state and branch complexity profiles under any coordinate ordering; these bounds can often be met. A maximum distance separable (MDS) code is characterized by a certain extremal DLP, from which the main properties of MDS codes are easily derived. The simplicity and generality of these interrelationships are emphasized     

A New Upper Bound on the Block Error Probability After Decoding Over the Erasure Channel

Motivated by cryptographic applications, we derive a new upper bound on the block error probability after decoding over the erasure channel. The bound works for all linear codes and is in terms of the generalized Hamming weights. It turns out to be quite useful for Reed-Muller codes for which all the generalized Hamming weights are known whereas the full weight distribution is only partially known. For these codes, the error probability is related to the cryptographic notion of algebraic immunity. We use our bound to show that the algebraic immunity of a random balanced m-variable Boolean function is of order ^m/₂(1-o(1)) with probability tending to 1 as m goes to infinity     

On bit-error probability of a concatenated coding scheme

This paper presents a method for evaluating the bit-error probability of a concatenated coding system for BPSK transmission over the AWGN channel. In the concatenated system, a linear binary block code is used as the inner code and is decoded with the soft-decision maximum likelihood decoding, and a maximum distance separable code (or its interleaved code) is used as the outer code and is decoded with a bounded distance decoding. The method is illustrated through a specific example in which the inner code is a binary (64.40.8) Reed-Muller subcode and the outer code is the NASA standard (255, 223, 33) Reed-Solomon code over GF(2⁸) interleaved to a depth of 5. This specific concatenated system is being considered for NASA's high-speed satellite communications. The bit-error performance is evaluated by a combination of simulation and analysis. The split weight enumerators for the maximum distance separable codes are derived and used for the analysis     

On Decoding Binary Perfect and Quasi-Perfect Codes over Markov Noise Channels

We study the decoding problem when a binary linear perfect or quasi-perfect code is transmitted over a binary channel with additive Markov noise. After examining the properties of the channel block transition distribution, we derive sufficient conditions under which strict maximum-likelihood decoding is equivalent to strict minimum Hamming distance decoding when the code is perfect. Additionally, we show a near equivalence relationship between strict maximum likelihood and strict minimum distance decoding for quasi-perfect codes for a range of channel parameters and the code's minimum distance. As a result, an improved (complete) minimum distance decoder is proposed and simulations illustrating its benefits are provided.     

Improving the generalized likelihood ratio test for unknown linear Gaussian channels

In this work, we consider the decoding problem for unknown Gaussian linear channels. Important examples of linear channels are the intersymbol interference (ISI) channel and the diversity channel with multiple transmit and receive antennas employing space-time codes (STC). An important class of decoders is based on the generalized likelihood ratio test (GLRT). Our work deals primarily with a decoding algorithm that uniformly improves the error probability of the GLRT decoder for these unknown linear channels. The improvement is attained by increasing the minimal distance associated with the decoder. This improvement is uniform, i.e., for all the possible channel parameters, the error probability is either smaller by a factor (that is exponential in the improved distance), or for some, may remain the same. We also present an algorithm that improves the average (over the channel parameters) error probability of the GLRT decoder. We provide simulation results for both decoders.     

Errors and erasures decoding of BCH and Reed-Solomon codes for reduced M-ary orthogonal signaling

The paper presents a comparison of communication systems using different signal constellation sizes and Reed-Solomon or Bose-Chaudhuri-Hocquengem codes with different rates so that the overall required bandwidth is the same for each system. In these comparisons, the channel symbol size is smaller than the code symbol size, so that a code symbol contains parts of multiple channel symbols. Thus, the normal assumption of independent code symbols does not apply. Instead, consideration must be taken to obtain the best arrangement of channel symbols in each code symbol. Analytical expressions are developed to compare the bit error probability performance of comparable systems, based on individual codewords using errors-only decoding and errors and erasures decoding with transmission over a Rayleigh fading channel.     

The capacity of binary channels that use linear codes and decoders

This paper analyzes the performance of concatenated coding systems operating over the binary-symmetric channel (BSC) by examining the loss of capacity resulting from each of the processing steps. The techniques described in this paper allow the separate evaluation of codes and decoders and thus the identification of where loss of capacity occurs. They are, moreover, very useful for the overall design of a communications system, e.g., for evaluating the benefits of inner decoders that produce side information. The first two sections of this paper provide a general technique (based on the coset weight distribution of a binary linear code) for calculating the composite capacity of the code and a BSC in isolation. The later sections examine the composite capacities of binary linear codes, the BSC, and various decoders. The composite capacities of the (8,4) extended Hamming, (24, 12) extended Golay, and (48, 24) quadratic residue codes appear as examples throughout the paper. The calculations in these examples show that, in a concatenated coding system, having an inner decoder provide more information than the maximum-likelihood (ML) estimate to an outer decoder is not a computationally efficient technique, unless generalized minimum-distance decoding of an outer code is extremely easy. Specifically, for the (8,4) extended Hamming and (24, 12) extended Golay inner codes, the gains from using any inner decoder providing side information, instead of a strictly ML inner decoder, are shown to be no greater than 0.77 and 0.34 dB, respectively, for a BSC crossover probability of 0.1 or less, However, if computationally efficient generalized minimum distance decoders for powerful outer codes, e.g., Reed-Solomon codes, become available, they will allow the use of simple inner codes, since both simple and complex inner codes have very similar capacity losses     

Asymptotically Gaussian weight distribution and performance of multicomponent turbo block codes and product codes

It was suggested by Battail that a good long linear code should have a weight distribution close to that of random coding, rather than a large minimum distance, and a turbo code should be also designed using a random-like criterion. In this paper, we first show that the weight distribution of a high-rate linear block code is approximately Gaussian if the code rate is close enough to one, and then proceed to construct a low-rate linear block code with approximately Gaussian weight distribution by using the turbo-coding technique. We give a sufficient condition under which the weight distribution of multicomponent turbo block (MCTB) codes (multicomponent product (MCP) codes, respectively) can approach asymptotically that of random codes, and further develop two classes of MCTB codes (MCP codes) satisfying this condition. Simulation results show that MCTB codes (MCP codes) having asymptotically Gaussian weight distribution can asymptotically approach Shannon's capacity limit. MCTB codes based on single parity-check (SPC) codes have a far poorer minimum distance than MCP codes based on SPC codes, but we show by simulation that when the bit-error rate is in the important range of 10/sup -1/-10/sup -5/, these codes can still offer similar performance for the additive white Gaussian noise channel, as long as the code length of the SPC codes is not very short. These facts confirm in a more precise way Battail's inference about the "nonimportance" of the minimum distance for a long code.     

An algorithm for calculating the exact bit error probability of a binary linear code over the binary symmetric channel

An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2/sup n-k/), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer.