We introduce a general adaptive coding scheme for Nakagami multipath fading channels. An instance of the coding scheme utilizes a set of 2L-dimensional (2L-D) trellis codes originally designed for additive white Gaussian noise (AWGN) channels. Any set of 2L-D trellis codes for AWGN channels can be used, Sets for which all codes can be generated by the same encoder and decoded by the same decoder are of particular interest. A feedback channel between the transmitter and receiver makes it possible to transmit at high spectral efficiencies under favorable channel conditions and respond to channel degradation through a smooth reduction of the spectral efficiency. We develop a general technique to determine the average spectral efficiency of the coding scheme for any set of 2L-D trellis codes. As an illustrative example, we calculate the average spectral efficiency of an adaptive codec utilizing eight 4-D trellis codes. The example codec is based on the International Telecommunications Union's ITU-T V.34 modem standard.

The author denotes by w/sub 0/ the minimum average weight per edge over all nonzero cycles in the state diagram for a convolutional code, and assumes that a technique is available for generating canonical parity-check matrices for codes with increasing degree m. The obtained class of codes is asymptotically catastrophic if w/sub 0/ approaches zero for large m. We prove the existence of convolutional code classes that are not asymptotically catastrophic by providing explicit constructions of codes with nonzero w/sub 0/ for all m.

A convolutional code can be represented by the conventional trellis module or the "minimal" trellis module based on the BCJR trellis for block codes. For many convolutional codes, the trellis complexity (TC) of the minimal module is significantly less than the TC of the conventional module. An alternative representation, consisting of an extended BCJR trellis module and a pruned version of the conventional module, was previously introduced. We prove that the overall TC of the two new modules is less than the TC of the conventional module for infinitely many codes. Furthermore, we show that the overall TC of the new modules is smaller than the TC of the minimal module for many codes considered in the literature.

A communication or storage system may use a coset of a binary convolutional code for both symbol synchronization and error control. To facilitate symbol synchronization, the coset must have a short maximum zero-run length L/sub max/. General upper and lower bounds on L/sub max/ were given previously by Hole. In this correspondence we use these bounds to identify which convolutional codes have cosets with short L/sub max/. For such a code, we then show how to determine a coset with the least possible L/sub max/ among all cosets of the code. Exact expressions for the least possible L/sub max/ of convolutional code cosets are given, and examples of such cosets with large free distances are tabulated. Bounds on L/sub max/ for cosets of block codes are also provided. It is indicated how to tighten the bounds for block codes satisfying the one-way chain condition. We show that the cosets obtained from traditional high-rate block code constructions have larger L/sub max/ than cosets of convolutional codes with approximately the same rates. In some systems the convolutional code cosets must have short maximum one-run lengths as well as short maximum zero-run lengths to avoid loss of symbol synchronization. It is shown how to determine convolutional codes whose cosets with least possible maximum zero-run lengths also have least possible maximum one-run lengths.

Convolutional codes with rate R=(n-1)/n,n/spl ges/2, are defined in terms of their minimal parity check matrices. The matrices are represented by a binary vector notation introduced by Ytrehus (1992). The upper bounds on /spl omega/0 (minimum average weight per branch) are presented. Many classes of rate (n-1)/n convolutional codes are shown to be asymptotically catastrophic.

Cosets of convolutional codes can be used to obtain large free Euclidean distances and short maximum zero-run lengths at the output of the 1-D partial-response channel (PRC). We present a new soft-decision decoding technique for cosets of convolutional codes on the preceded 1-D PRC. The decoding technique is especially well suited for cosets of partial unit memory (PUM) convolutional codes. A connection between the decoder trellises for cosets of block codes and PUM codes on the 1-D PRC is exploited to obtain a small number of operations per decoded information bit. We prove that the new decoding technique needs fewer operations than the Viterbi algorithm for any (n,n-r), r/spl ges/1, PUM code coset with n/spl les/2/sup v-r/ where v is the constraint length. It is also indicated how to prove the same result for other classes of codes. For many of the best known PUM code cosets, the new decoding technique requires both fewer operations per decoded information bit and smaller path memories than the Viterbi algorithm needs for comparable cosets of punctured convolutional codes.

Consider a cycle in the state diagram of a convolutional code. The average weight per branch of the cycle is equal to the total Hamming weight of all labels on the branches divided by the number of branches. Let w/sub 0/ be the minimum average weight per branch over all cycles in the state diagram, except the zero state self-loop of weight zero. Codes with low w/sub 0/ result in high bit error probabilities when they are used with either Viterbi or sequential decoding. Hemmati and Costello (1980) showed that w/sub 0/ is upper-bounded by 2/sup /spl nu/-2//(3/spl middot/2/sup /spl nu/-2/-1) for a class of (2,1) codes where /spl nu/ denotes the constraint length. In the present correspondence it is shown that the bound is valid for a large class of (n,n-1) codes, n/spl ges/2. Examples of high-rate codes with w/sub 0/ equal to the upper bound are also given. Hemmati and Costello defined a class of codes to be asymptotically catastrophic if w/sub 0/ approaches zero for large /spl nu/. The class of (n,n-1) codes constructed by Wyner and Ash (1963) is shown to be asymptotically catastrophic. All codes in the class have minimum possible w/sub 0/ equal to 1//spl nu/.

Communication systems and storage systems derive symbol synchronization from the received symbol stream. To facilitate symbol synchronization, the channel sequences must have a short maximum zero-run length. One way to achieve this is to use a coset of an (n, k) convolutional code to generate the channel inputs. For k/spl les/n-2, it is shown that there exist cosets with short maximum zero-run length for any constraint length. Any coset of an (n, n-1) code with high rate and/or large constraint length is shown to have a large maximum zero-run length. A systematic procedure for obtaining cosets with short maximum zero-run length from (n, k) codes is presented, and new cosets with short maximum zero-run length and large minimum Hamming distance are tabulated.>

A coset of a convolutional code may be used to generate a zero-run length limited trellis code for a 1-D partial-response channel. The free squared Euclidean distance, d/sub free//sup 2/, at the channel output is lower bounded by the free Hamming distance of the convolutional code. The lower bound suggests the use of a convolutional code with maximal free Hamming distance, d/sub max/(R,N), for given rate R and number of decoder states N. In this paper we present cosets of convolutional codes that generate trellis codes with d/sub free//sup 2/>d/sub max/(R,N) for rates 1/5/spl les/R/spl les/7/9 and (d/sub free//sup 2/=d/sub max/(R,N) for R=13/16,29/32,61/64, The tabulated convolutional codes with R/spl les/7/9 were not optimized for Hamming distance. Instead, a computer search was used to determine cosets of convolutional codes that exploit the memory of the 1-D channel to increase d/sub free//sup 2/ at the channel output. The search was limited by only considering cosets with certain structural properties. The R/spl ges/13/16 codes were obtained using a new construction technique for convolutional codes with free Hamming distance 4. Newly developed bounds on the maximum zero-run lengths of cosets were used to ensure a short maximum run length at the 1-D channel output.>

The algorithm determines whether or not the punctured state diagram contains a zero-weight cycle. The punctured encoder is assumed to be obtained from a rate 1/b, b>

G.D. Forney (1970, 1975) defined a minimal encoder as a polynomial matrix G such that G generates the code and G has the least constraint length among all generators for the code. Any convolutional code can be generated by a minimal encoder. High-rate k(k+1) punctured convolutional codes were introduced to simplify Viterbi decoding. An ordinary convolutional encoder G can be obtained from any punctured encoder. A punctured encoder is minimal if the corresponding ordinary encoder G is minimal and the punctured and ordinary encoders have the same constraint length. It is shown that any rate k/(k+1), noncatastrophic, antipodal punctured encoder is a minimal encoder.>

A coded (1-D) system containing a punctured convolutional encoder is analyzed. In general, a punctured encoder with 2/sup v/ states results in a decoder trellis with 2/sup v+1/ states and a periodically time-varying branch structure. A class C of punctured convolutional encoders for which the decoder trellis has a fixed branch structure with 2/sup v/ states is described. An encoder in this class can be combined with a precoder to form a new punctured convolutional encoder that generates the output from the precoder. The author determines the set of good variable-rate trellis codes for selectable rate encoding and Viterbi decoding. A set of variable-rate trellis codes is generated by a variable-rate punctured convolutional encoder in C. The author also determines punctured convolutional encoders in C that generate a single good high-rate trellis code.>

Punctured convolutional codes with good performance are reported for rates (n-1)/n with n=5, 6, 7, 8 and constraint lengths k=2, 3, . . ., 6. The tabulated codes are nonsystematic binary convolutional codes with maximum free distance and minimum information weight, for use with soft-decision Viterbi decoding.>