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.     

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.     

Distance spectra and performance bounds of space-time trellis codes over quasistatic fading channels

This correspondence presents a general approach to upper bounding coded system performance over quasistatic fading channels (QSFC). This approach has the advantage of yielding a closed-form upper bound that converge for all signal-to-noise ratios (SNRs). The proposed approach is used to upper-bound the performance of space-time trellis codes (STTC) over QSFCs. The resulting upper bounds for STTCs are better adapted to the QSFC and present an improvement over worst case pairwise error probability (PEP) analysis used so far. In its second part, this correspondence investigates several ways to reduce the complexity of computing the distance spectrum of STTCs. The combined result obtained from using the new upper bounds and the computed distance spectra are shown to be close to simulated performance for all SNRs.     

On performance bounds for space-time codes on fading channels

We evaluate truncated union bounds on the frame-error rate (FER) performance of space-time (ST) codes operating over the quasi-static fading channel and compare them with computer simulation results. We consider both ST trellis and block codes. We make the following contributions. For the case of ST trellis codes, we develop a general method, which we denote as measure spectrum analysis, that characterizes ST codeword differences and accommodates the combined influences of the ST code and channel scenario. We propose a numerical bounding method that converges in the measure spectrum to within a very small fraction of a decibel to the simulated FER over the full range of signal-to-noise ratio. In addition, we demonstrate the existence of dominant quasi-static fading error events and detail a method for predicting them. Using only this set of dominant measure spectrum elements, very rapid and tight numerical estimation of FER performance is attained.     

Repeated convolutional codes for high-error-rate channels

An error-correction scheme for an M-ary symmetric channel (MSC) characterized by a large error probability p_e is considered. The value of p_e can be near, but smaller than, 1-1/M, for which the channel capacity is zero, such as may occur in a jamming environment. The coding scheme consists of an outer convolutional code and an inner repetition code of length m that is used for each convolutional code symbol. At the receiving end, the m inner code symbols are used to form a soft-decision metric, which is passed to a soft-decision decoder for the convolutional code. The effect of finite quantization and methods to generate binary metrics for M>2 are investigated. Monte Carlo simulation results are presented. For the binary symmetric channel (BSC), it is shown that the overall code rate is larger than 0.6R₀, where R₀ is the cutoff rate of the channel. New union bounds on the bit error probability for systems with a binary convolutional code on 4-ary and 8-ary orthogonal channels are presented. For a BSC and a large m, a method is presented for BER approximation based on the central limit theorem     

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.     

Evaluating the performance of convolutional codes over block fadingchannels

This correspondence considers union upper bound techniques for error control codes with limited interleaving over block fading Rician channels. A modified bounding technique is presented that relies on limiting the conditional union bound before averaging over the fading process. This technique, although analytically not very attractive, provides tight and hence useful numerical results     

New performance bounds for turbo codes

We derive a new upper bound on the word- and bit-error probabilities of turbo codes with maximum-likelihood decoding by using the Gallager bound. Since the derivation of the bound for a given interleaver is intractable, we assume uniform interleaving as in the derivation of the standard union bound for turbo codes. The result is a generalization of the transfer function bound and remains useful for a wider range of signal-to-noise ratios, particularly for some range below the channel cutoff rate. The new bound is also applicable to other linear codes     

Asymptotic performance of space-frequency codes over broadband channels

We show that when the number of receive antennas is large, the Euclidean distance among codewords dominates the performance of space-frequency codes, the same result as for space-time codes. Therefore, in the presence of a large number of receive antennas, space-frequency codes can be optimized by using the Euclidean-distance criterion valid for additive white Gaussian noise channels. Simulation results show that this conclusion is also valid when the number of antennas is small.     

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.     

Optimum shortened cyclic codes for burst-error correction

This paper is concerned with the construction of the most efficient shortened cyclic (pseudo-cyclic) codes that can correct every burst-error of lengthbor less. These codes have the maximum number of information digitskamong all shortened cyclic burst-bcodes with a given number of check digitsr. The search procedure described is readily programmable for computer execution and efficient particularly for the case whereris close to the theoretical minimum of2bcheck digits. For2 leq b leq 10, several optimum shortened cyclic codes in the above-mentioned sense have been found. Their code-lengths and generators are tabulated in this paper.     

Analytical upper bounds for convolutional coded CPM over rings

Analytical upper bounds on symbol error probability for ring convolutional coded Continuous Phase Modulation (CPM) with Maximum Likelihood Sequence Detection (MLSD) are presented. The constructed bounds for the investigated systems are shown to be asymptotically tight for increasing channel Signal-to-Noise Ratio (SNR) values. This work provides an analysis tool for the investigated systems. The analysis method is very general. It may be applied to any trellis based coding schemes.     

提高检突发错误能力的LDPC码的构造方法

当前LDPC码的构造方法都是偏重于提高码的性能、降低编码复杂度2个方面，没有考虑码组之间的汉明距离和汉明距离分布，从而漏检部分突发错误。给出了一种次优的考虑码组汉明距离分布的构造方法，和已有的方法相比，这种方法构造的LDPC码不仅可以检突发长度小于校验矩阵秩的突发错误，并且保持纠随机错误性能不变。     

Algebraic lower bounds on the free distance of convolutional codes

A new module structure for convolutional codes is introduced and used to establish further links with quasi-cyclic and cyclic codes. The set of finite weight codewords of an (n,k) convolutional code over F_q is shown to be isomorphic to an F_q[x]-submodule of F_q ⁿ[x], where F_q ⁿ[x] is the ring of polynomials in indeterminate x over F_q ⁿ, an extension field of F_q. Such a module can then be associated with a quasi-cyclic code of index n and block length nL viewed as an F_q[x]-submodule of F_q ⁿ[x]/langx^L-1rang, for any positive integer L. Using this new module approach algebraic lower bounds on the free distance of a convolutional code are derived which can be read directly from the choice of polynomial generators. Links between convolutional codes and cyclic codes over the field extension F_q ⁿ are also developed and Bose-Chaudhuri-Hocquenghem (BCH)-type results are easily established in this setting. Techniques to find the optimal choice of the parameter L are outlined     

System-theoretic properties of convolutional codes over rings

Convolutional codes over rings are particularly suitable for representing codes over phase-modulation signals. In order to develop a complete structural analysis of this class of codes, it is necessary to study rational matrices over rings, which constitutes the generator matrices (encoders) for such convolutional codes. Noncatastrophic, minimal, systematic, and basic generator matrices are introduced and characterized by using a canonical form for polynomial matrices over rings. Finally, some classes of convolutional codes, defined according to the generator matrix they admit, are introduced and analyzed from a system-theoretic point of view     

Comments on `Evaluating distance spectra and performance bounds oftrellis codes on channels with intersymbol interference'

It is shown that the method presented by C. Schlegel (see ibid., vol.37, no.3, p.627-34, May 1991) for evaluating the distance spectra of trellis codes on channels with intersymbol interference is incorrect. A counterexample is presented along with comments on the feasibility of correcting the method     

Binary intersymbol interference channels: Gallager codes, density evolution, and code performance bounds

We study the limits of performance of Gallager codes (low-density parity-check (LDPC) codes) over binary linear intersymbol interference (ISI) channels with additive white Gaussian noise (AWGN). Using the graph representations of the channel, the code, and the sum-product message-passing detector/decoder, we prove two error concentration theorems. Our proofs expand on previous work by handling complications introduced by the channel memory. We circumvent these problems by considering not just linear Gallager codes but also their cosets and by distinguishing between different types of message flow neighborhoods depending on the actual transmitted symbols. We compute the noise tolerance threshold using a suitably developed density evolution algorithm and verify, by simulation, that the thresholds represent accurate predictions of the performance of the iterative sum-product algorithm for finite (but large) block lengths. We also demonstrate that for high rates, the thresholds are very close to the theoretical limit of performance for Gallager codes over ISI channels. If C denotes the capacity of a binary ISI channel and if C/sub i.i.d./ denotes the maximal achievable mutual information rate when the channel inputs are independent and identically distributed (i.i.d.) binary random variables (C/sub i.i.d.//spl les/C), we prove that the maximum information rate achievable by the sum-product decoder of a Gallager (coset) code is upper-bounded by C/sub i.i.d./. The last topic investigated is the performance limit of the decoder if the trellis portion of the sum-product algorithm is executed only once; this demonstrates the potential for trading off the computational requirements and the performance of the decoder.     

Source fidelity over fading channels: performance of erasure and scalable codes

We consider the transmission of a Gaussian source through a block fading channel. Assuming each block is decoded independently, the received distortion depends on the tradeoff between quantization accuracy and probability of outage. Namely, higher quantization accuracy requires a higher channel code rate, which increases the probability of outage. We first treat an outage as an erasure, and evaluate the received mean distortion with erasure coding across blocks as a function of the code length. We then evaluate the performance of scalable, or multi-resolution coding in which coded layers are superimposed within a coherence block, and the layers are sequentially decoded. Both the rate and power allocated to each layer are optimized. In addition to analyzing the performance with a finite number of layers, we evaluate the mean distortion at high signal-to-noise ratios as the number of layers becomes infinite. As the block length of the erasure code increases to infinity, the received distortion converges to a deterministic limit, which is less than the mean distortion with an infinite-layer scalable coding scheme. However, for the same standard deviation in received distortion, infinite layer scalable coding performs slightly better than erasure coding, and with much less decoding delay.     

An upper bound on turbo codes performance over quasi-static fading channels

This letter proposes an upper bound on the performance of turbo-codes over quasi-static fading channels. First an upper bound is derived for the case of a single-input single-output channel. The result is then extended to the case of a serial concatenation of a turbo-code and a space-time block code. Unlike a simple extension of the union bound, the derived upper bounds are shown to converge for all signal-to-noise ratios. Additionally the closed form upper bounds obtained confirm analytically that, unlike over additive white Gaussian noise channels, turbo-code performance does not improve by increasing frame length over quasi-static fading channels.     

Packet-length adaptive CLSP/DS-CDMA: performance in burst-error correlated fading channels

The authors analyze throughput-delay performance of an unslotted channel load sensing protocol (CLSP)/direct sequence (DS)-code division multiple access (CDMA) packet radio network (PRN) with adaptive packet length over burst-error correlated fading channels. CLSP controls the packet access in uplink of unslotted ALOHA/DS-CDMA systems so that contention is avoided and throughput is maximized. However, due to high uncertainty of radio channels, the performance of CLSP/DS-CDMA PRN may suffer from notable degradations. Using theoretical analysis and simulation, the authors show that in highly correlated fading environments adapting the length of radio packets to fading conditions significantly improves system performance and energy efficiency of mobile terminals. In their modeling, they study the relation between the fade statistics and the packet length in correlated Rayleigh fading channels. The effects of reception diversity, imperfect transmit power control (TPC), and user mobility are considered. The results are used to develop simple, energy-efficient, and robust adaptation mechanisms.