Improved space-time convolutional codes for quasi-static slow fading channels

Space-time convolutional codes, that provide maximum diversity and coding gain, are produced for cases with PSK modulation and various numbers of states and antennas. The codes are found using a new approach introduced previously in a companion paper. The new approach provides an efficient method that allows a search for optimum codes for many practical problems. The new approach also provides a simple method for augmenting the criteria of maximum diversity and coding gain with a new measure which is shown to be extremely useful for evaluating code performance without extensive simulations. To validate the approach, an extensive set of simulation results are presented comparing the codes designed here to many other previously proposed space-time convolutional codes. The comparisons, given in terms of frame error rate (FER), indicate that our new method provides codes which yield excellent performance. The approach is especially useful for finding a handful of good codes. Selection among these codes can be made with a limited number of simulations for FER.     

Generating series and performance bounds for convolutional codes over burst-error channels

We present an analytical method for evaluating performance bounds for a communication system that employs a convolutional code, a block interleaving with finite interleaving depth, a binary channel that exhibits statistical dependence in the occurrence of errors, and a decoder that implements the Viterbi (1979) algorithm with Hamming metric. The main idea is to apply combinatorial methods to derive a formula for bounds to first-event and bit error probabilities in terms of coefficients of a generating series. The method is used to investigate the tradeoff between coding parameters and interleaving depth to achieve a required performance.     

Evaluation of the gallager adaptive convolutional codes on real channels

In the letter the performances of Gallager codes, and hybrid systems based on these codes, are evaluated on real channels using the Monte Carlo simulation method. The new criteria are proposed for diffuse bursts as well as for hybrid systems. Test results demonstrate that these codes, if properly used, offer a significant reduction in the error rate.     

Sphere-packing bounds for convolutional codes

We introduce general sphere-packing bounds for convolutional codes. These improve upon the Heller (1968) bound for high-rate convolutional codes. For example, based on the Heller bound, McEliece (1998) suggested that for a rate (n - 1)/n convolutional code of free distance 5 with /spl nu/ memory elements in its minimal encoder it holds that n /spl les/ 2/sup (/spl nu/+1)/2/. A simple corollary of our bounds shows that in this case, n < 2/sup /spl nu//2/, an improvement by a factor of /spl radic/2. The bound can be further strengthened. Note that the resulting bounds are also highly useful for codes of limited bit-oriented trellis complexity. Moreover, the results can be used in a constructive way in the sense that they can be used to facilitate efficient computer search for codes.     

Active distances for convolutional codes

A family of active distance measures for general convolutional codes is defined. These distances are generalizations of the extended distances introduced by Thommesen and Justesen (1983) for unit memory convolutional codes. It is shown that the error correcting capability of a convolutional code is determined by the active distances. The ensemble of periodically time-varying convolutional codes is defined and lower bounds on the active distances are derived for this ensemble. The active distances are very useful in the analysis of concatenated convolutional encoders     

High-rate recursive convolutional codes for concatenated channel codes

This letter presents the results of the search for optimum punctured recursive convolutional codes (RCCs) of rate k/k+1, for k=2,...,8, suitable for concatenated channel codes whose constituent encoders are recursive, systematic convolutional codes. The mother codes that are punctured are rate-1/2 RCCs proposed for use in parallel and/or serial concatenation schemes. Extensive tables of systematic and nonsystematic puncturing patterns, optimized relative to various objective functions suitable for concatenated channel codes, are presented for several mother codes.     

Strongly-MDS convolutional codes

Maximum-distance separable (MDS) convolutional codes have the property that their free distance is maximal among all codes of the same rate and the same degree. In this paper, a class of MDS convolutional codes is introduced whose column distances reach the generalized Singleton bound at the earliest possible instant. Such codes are called strongly-MDS convolutional codes. They also have a maximum or near-maximum distance profile. The extended row distances of these codes will also be discussed briefly.     

BCH convolutional codes

Using a new parity-check matrix, a class of convolutional codes with a designed free distance is introduced. This new class of codes has many characteristics of BCH block codes, therefore, we call these codes BCH convolutional codes     

MDS convolutional codes

Maximum distance separable (MDS) convolutional codes are defined as the row space overF(D)of totally nonsingular polynomial matrices in the indeterminateD. These codes may be used to transmit information onnparallel channels when a temporary or even an infinite break can occur in some of these channels. Their algebraic properties are emphasized, and the relevant parameters are introduced. On this basis two decoding procedures are described. Both procedures correct arbitrarily long error sequences that may occur at the same time in some of thenchannels. Some specific constructions of MDS convolutional codes are presented.     

Bit error probability calculations for convolutional codes withshort constraint lengths on very noisy channels

A technique for estimating convolutional code performance on very noisy channels is considered. Specifically, the performance of short constraint length codes operating near the channel cutoff rate is estimated. Decoding convolutional codes with a sliding window decoder (SWD) are considered. This decoder is an optimal (maximum likelihood) symbol decoder as the window size grows toward infinity, while the Viterbi decoder is the maximum-likelihood sequence estimator. The difference in the decoded BERs (bit error rates) between the two decoders is very small and approaches zero asymptotically as the channel BER decreases. Therefore, an estimate on the decoded BER for the SWD can also be used as an estimate of the decoded BER for Viterbi decoding     

Basic encoders for Abelian convolutional codes

A specific criterion is presented to check the noncatastrophic property of encoders for a convolutional code with a certain type of automorphism. In most cases to which the criterion is applicable, only a very small amount of computation is required.     

Free distance bounds for convolutional codes

The best asymptotic bounds presently known on free distance for convolutional codes are presented from a unified point of view. Upper and lower bounds for both time-varying and fixed codes are obtained. A comparison is made between bounds for nonsystematic and systematic codes which shows that more free distance is available with nonsystematic codes. This result is important when selecting codes for use with sequential or maximum-likelihood (Viterbi) decoding since the probability of decoding error is closely related to the free distance of the code. An ancillary result, used in proving the lower bound on free distance for time-varying nonsystematic codes, furnishes a generalization of two earlier bounds on the definite decoding minimum distance of convolutional codes.     

Unequal error protection for convolutional codes

In this correspondence, unequal error-correcting capabilities of convolutional codes are studied. For errors in the information symbols and code symbols, the free input- and output-distances, respectively, serve as "unequal" counterparts to the free distance. When communication takes place close to or above the channel capacity the error bursts tend to be long and the free distance is not any longer useful as the measure of the error correcting capability. Thus, the active burst distance for a given output and the active burst distance for a given input are introduced as "unequal" counterparts to the active burst distance and improved estimates of the unequal error-correcting capabilities of convolutional codes are obtained and illustrated by examples. Finally, it is shown how to obtain unequal error protection for both information and code symbols using woven convolutional codes.     

Lower bounds on reliability functions of variable-length nonsystematic convolutional codes for channels with noiseless feedback

A variable-length, nonsystematic, convolutional encoding, and successive-decoding scheme is devised to establish significant improvements in the reliability functions of memoryless channels with noiseless decision feedback. It is shown that, for any but pathological discrete memoryless channels with noiseless feedback, there exists a variable-length convolutional code such that the reliability function of the channel can be bounded below by the channel capacityCfor all transmission rates less thanC. By employing a modified version of this scheme, it is also constructively shown that, for an additive-white-Gaussian-noise (AWGN) channel with noiseless feedback it is possible to find a variable-length convolutional code such that the channel reliability function can be bounded below byalpha_0 c_{infty}for all rates less than the channel capacityC_{infty}, wherealpha_0 = max (1, gamma/2)andgammais the maximum allowable expected-peak-to-expected-average-power ratio at the transmitter.     

Joint source-channel decoding of variable-length codes for convolutional codes and turbo codes

Several recent publications have shown that joint source-channel decoding could be a powerful technique to take advantage of residual source redundancy for fixed- and variable-length source codes. This letter gives an in-depth analysis of a low-complexity method recently proposed by Guivarch et al., where the redundancy left by a Huffman encoder is used at a bit level in the channel decoder to improve its performance. Several simulation results are presented, showing for two first-order Markov sources of different sizes that using a priori knowledge of the source statistics yields a significant improvement, either with a Viterbi channel decoder or with a turbo decoder.     

Generalized punctured convolutional codes

This letter introduces the class of generalized punctured convolutional codes (GPCCs), which is broader than and encompasses the class of the standard punctured convolutional codes (PCCs). A code in this class can be represented by a trellis module, the GPCC trellis module, whose topology resembles that of the minimal trellis module. he GPCC trellis module for a PCC is isomorphic to the minimal trellis module. A list containing GPCCs with better distance spectrum than the best known PCCs with same code rate and trellis complexity is presented.     

DC-free error-correcting codes based on convolutional codes

A new construction of direct current (DC)-free error-correcting codes based on convolutional codes is proposed. The new code is constructed by selecting a proper subcode from a convolutional code composed of two different component codes. The encoder employs a Viterbi algorithm as the codeword selector so that the selected code sequences satisfy the DC constraint. A lower bound on the free distance of such codes is proposed, and a procedure for obtaining this bound is presented. A sufficient condition for these codes to have a bounded running digital sum (RDS) is proposed. Under the assumption of a simplified codeword selection algorithm, we present an upper bound on the maximum absolute value of the RDS and derive the sum variance for a given code. A new construction of standard DC-free codes, i.e., DC-free codes without error-correcting capability, is also proposed. These codes have the property that the decoder can be implemented by simple symbol-by-symbol hard decisions. Finally, under the new construction, we propose several codes that are suitable for the systems that require small sum variance and good error-correction capability     

Multiple-word correcting convolutional codes

Two classes of multiple-word correcting convolutional encoders are defined and analyzed. We obtain some conditions for these encoders to be noncatastrophic, and we describe ways to check the (word) minimum distance of the generated codes. The first class can easily be analyzed by algebraic means, but the redundancy of the corresponding codes is not arbitrarily iow. The codes generated by the second class of encoders may have a lower redundancy, but their analysis requires the use of a computer program.     

Partially concatenated convolutional codes

We present a new concatenated code construction. The resulting codes can be viewed as intermediate between parallel and serially concatenated convolutional codes. Proper partitioning of the outer code sequence provides a new degree of freedom for code design. Various methods are considered to analyze code properties.     

Near-optimal limited-search detection on ISI/CDMA channels anddecoding of long convolutional codes

We derive an upper bound on the bit-error probability (BEP) in limited-search detection over a finite interference channel. A unified channel model is presented; this includes finite-length intersymbol interference channels and multiuser CDMA channels as two special cases. We show that the BEP of the M-algorithm (MA) is bounded from above by the sum of three terms: an upper bound on the error probability of the Viterbi (1967) algorithm (VA) detection given by Forney Jr. (1972), and upper bounds on the error probabilities of two types of erroneous decision caused by the correct path loss event. We prove that error propagation (in terms of the mean recovery step number) is finite for all finite interference channels. The convergence and asymptotic behavior of the upper bounds are studied. The results show that, if a channel satisfies certain mild conditions, all series in the bounds are convergent. One of the key results is that, for any finite interference channel satisfying certain mild conditions. the asymptotic BEP of the MA is bounded by the same upper and lower bounds (which have the same asymptotical behavior) as those for the VA if the correct path loss probability is smaller than that of the VA. Furthermore, we extend the above results to near optimally decode long convolutional codes in a short packet format (about 200-300 bits). We present a nonsorting combined M/T algorithm and showed that the M/T algorithm with M>2( ^dfree/ⁿ) and T>(d_freeE_b)/n can near-optimally decode the code. We also propose a hierarchical decoding algorithm (HDA) to further cut down the average decoding complexity. Numerical results show that the bounds are reasonably tight. The HDA can achieve a performance within about 0.8 dB of the sphere-packing lower bound for a packet error rate of 10^-4 and a packet length below 200 bits, which is the best reported decoding performance so far for block sizes from 100 to 200 bits