Improved coding techniques for preceded partial-response channels

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_free², 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_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_free ²>d_max(R,N) for rates 1/5⩽R⩽7/9 and (d _free²=d_max(R,N) for R=13/16,29/32,61/64, The tabulated convolutional codes with R⩽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_free² at the channel output. The search was limited by only considering cosets with certain structural properties. The R⩾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     

Minimal tail-biting trellises: the Golay code and more

Tail-biting trellis representations of block codes are investigated. We develop some elementary theory, and present several intriguing examples, which we hope will stimulate further developments in this field. In particular, we construct a 16-state 12-section structurally invariant tail-biting trellis for the (24, 12, 8) binary Golay code. This tail-biting trellis representation is minimal: it simultaneously minimizes all conceivable measures of state complexity. Moreover, it compares favorably with the minimal conventional 12-section trellis for the Golay code, which has 256 states at its midpoint, or with the best quasi-cyclic representation of this code, which leads to a 64-state tail-biting trellis. Unwrapping this tail-biting trellis produces a periodically time-varying 16-state rate-1/2 “convolutional Golay code” with d=8, which has attractive performance/complexity properties. We furthermore show that the (6, 3, 4) quaternary hexacode has a minimal 8-state group tail-biting trellis, even though it has no such linear trellis over F₄. Minimal tail-biting trellises are also constructed for the (8, 4, 4) binary Hamming code, the (4, 2, 3) ternary tetracode, the (4, 2, 3) code over F₄, and the Z₄-linear (8. 4, 4) octacode     

Tailbiting codes obtained via convolutional codes with large active distance-slopes

The slope of the active distances is an important parameter when investigating the error-correcting capability of convolutional codes and the distance behavior of concatenated convolutional codes. The slope of the active distances is equal to the minimum average weight cycle in the state-transition diagram of the encoder. A general upper bound on the slope depending on the free distance of the convolutional code and new upper bounds on the slope of special classes of binary convolutional codes are derived. Moreover, a search technique, resulting in new tables of rate R=1/2 and rate R=1/3 convolutional encoders with high memories and large active distance-slopes is presented. Furthermore, we show that convolutional codes with large slopes can be used to obtain new tailbiting block codes with large minimum distances. Tables of rate R=1/2 and rate R=1/3 tailbiting codes with larger minimum distances than the best previously known quasi-cyclic codes are given. Two new tailbiting codes also have larger minimum distances than the best previously known binary linear block codes with same size and length. One of them is also superior in terms of minimum distance to any previously known binary nonlinear block code with the same set of parameters.     

A note on type II convolutional codes

The result of a search for the world's second type II (doubly-even and self-dual) convolutional code is reported. A rate R=4/8, 16-state, time-invariant, convolutional code with free distance d_free=8 was found to be type II. The initial part of its weight spectrum is better than that of the Golay convolutional code (GCC). Generator matrices and path weight enumerators for some other type II convolutional codes are given. By the “wrap-around” technique tail-biting versions of (32, 18, 8) Type II block codes are constructed     

Bandwidth efficient parallel concatenated coding schemes

The authors propose a solution to the parallel concatenation of trellis codes with multilevel amplitude/phase modulations and a suitable iterative decoding structure. Examples are given for throughputs 2bit/s/Hz with 8PSK and 16QAM signal constellations. For parallel concatenated trellis codes in the examples, rate 2/3 and 4/5, 16-state binary convolutional codes with Gray code mapping are used. The performances of these codes are within 1 dB of the Shannon limit at a bit error probability of 10^-6 for a given throughput. This outperforms all codes reported in the past for the same throughput     

On the structure of rate1/nconvolutional codes

We show what choice there is in assigning output digits to transitions of a binary rate1/ncode trellis so that the latter will correspond to a convolutional code. We then prove that in any ratefrac{1}{2}noncatastrophic code of constraint lengthupsiloneach binary sequence of length2j(1 leq j leq upsilon - 1)is associated with exactly2^{upsilon -j -1}distinct pathsjbranches long. As a consequence of the above properties nondegenerate codes with branch complementarity are fully determined by the topological relationship of the trellis transitions associated with output pairs 00. Finally, we derive a new upper bound on free distance of rate1/nconvolutional codes and use our results to determine the length of the largest input sequence that can conceivably result in an output whose weight is     

Source-channel optimized trellis codes for bitonal imagetransmission over AWGN channels

We consider the design of trellis codes for transmission of binary images over additive white Gaussian noise (AWGN) channels. We first model the image as a binary asymmetric Markov source (BAMS) and then design source-channel optimized (SCO) trellis codes for the BAMS and AWGN channel. The SCO codes are shown to be superior to Ungerboeck's codes by approximately 1.1 dB (64-state code, 10^-5 bit error probability), We also show that a simple “mapping conversion” method can be used to improve the performance of Ungerboeck's codes by approximately 0.4 dB (also 64-state code and 10 ^-5 bit error probability). We compare the proposed SCO system with a traditional tandem system consisting of a Huffman code, a convolutional code, an interleaver, and an Ungerboeck trellis code. The SCO system significantly outperforms the tandem system. Finally, using a facsimile image, we compare the image quality of an SCO code, an Ungerboeck code, and the tandem code, The SCO code yields the best reconstructed image quality at 4-5 dB channel SNR     

An Upper Bound on the Minimum Distance of Serially Concatenated Convolutional Codes

This correspondence presents an upper bound on the minimum distance of serially concatenated codes with interleaver where the inner code is a systematic recursive convolutional encoder and the outer code is any convolutional encoder. The resulting expression shows that the minimum distance of the concatenated code cannot grow more than O(K¹-1/d_f ^(O)), where K is the information word length, and d_f ^(O) is the free distance of the outer code. The obtained upper bound is shown to agree with and, in some cases, improve over previously known results     

An upper bound on the minimum distance of a convolutional code

An upper bound on the minimum distance of a linear convolutional code is given which reduces to the Plotkin bound for the block code case. It is shown that most linear convolutional codes have a minimum distance strictly less than their average distance. A table of the bound for several rates is given for binary codes as well as a comparison with the known optimum values for codes of block length2.     

Woven Graph Codes: Asymptotic Performances and Examples

Constructions of woven graph codes based on constituent block and convolutional codes are studied. It is shown that within the random ensembles of such codes based on s-partite, s-uniform hypergraphs, where s depends only on the code rate, there exist codes satisfying the Gilbert-Varshamov (GV) and the Costello lower bound on the minimum distance and the free distance, respectively. A connection between regular bipartite graphs and tailbiting (TB) codes is shown. Some examples of woven graph codes are presented. Among them, an example of a rate R_wg=1/3 woven graph code with d_free=32 based on Heawood's bipartite graph, containing n=7 constituent rate R^c=2/3 convolutional codes with overall constraint lengths ?^c =5, is given.     

On constructing embedded multilevel trellis codes

A design technique to reduce the search time for trellis codes with multilevel phase modulation is presented. Codes are constructed by connecting trellis diagrams for codes with fewer states in parallel. For example, an N-state code can be constructed by connecting two N/2-state codes. The way in which the embedded codes are connected increases the upper limit on minimum free distance otherwise imposed by parallel transitions between states. In some cases, this technique can reduce the number of codes in a code search by a factor of approximately 2^ν, the number of coder states. A computer search incorporating this technique for eight-level amplitude modulation (8-AM) codes having 2¹¹ and 2¹² states produced codes with greater minimum free distance than reported previously (i.e. greater than 6 dB coding gain). New eight-level phase-shift-keying (8-PSK) codes, which have a different structure from previously reported codes, are also presented     

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.     

A geometric construction procedure for geometrically uniformtrellis codes

The problem of maximizing the minimum free squared Euclidean distance of a trellis code is developed from a geometric point of view. This approach provides a new way of constructing constellations for trellis coding. A decomposition of the trellis topology leads to a systematic construction of signal sets and generators for geometrically uniform trellis codes. An algorithm is proposed to construct geometrically uniform trellis codes, and examples show how to obtain large free distance trellis codes. This approach unifies the construction of convolutional codes over the binary field and trellis codes over the real field     

Group trellis codes over multidimensional unbalanced PSK and theiroptimality

New geometrically uniform trellis codes over multidimensional unbalanced 4-, 8-, and 16-PSK constellations, obtained with the group code approach, are presented. They improve by up to 1.25 dB the asymptotic performance of the best known trellis codes over multidimensional balanced PSK. To check their “optimality”, an upper bound on the free distance of group trellis codes is derived. Some of the new codes achieve the largest obtainable free distance, and several others are close to the bound. Exploiting the symmetry properties of the codes, curves of tight upper bounds to the error probability are also presented     

The free distance of fixed convolutional rate 2/4 codes meets theCostello bound

The long standing question whether the free distance of fixed rate convolutional codes is as good as the Costello bound was almost solved by K.S. Zigangirov and J.L. Massey (1987). They proved that this is indeed the case for codes with long branch length and rates 2/c, c⩾5. It is shown that there exist fixed convolutional codes of rate 2/4 whose free distance d_free meets the Costello bound originally derived for time varying convolutional codes     

Simplified trellis decoder

A new simplified trellis decoder (STD) Viterbi-type algorithm is proposed for fast trellis decoding of rate K/K+1 binary convolutional codes. Viterbi algorithm (VA) computation is dominated by add-compare-select (ACS) operations when k⩾2. The STD can substantially reduce the number of ACS operations and allow for a trade-off between the computational load and the performance of the decoder, The STD is analyzed and simulated for a four-dimensional (4-D) rate 4/5 64-state convolutional encoder specified by the ITU-T V.34 modem recommendation     

Quaternary Convolutional Codes From Linear Block Codes Over Galois Rings

From a linear block code B over the Galois ring GR(4, m) with a k times n generator matrix and minimum Hamming distance d, a rate-k/n convolutional code over the ring Z₄ with squared Euclidean free distance at least 2d and a nonrecursive encoder with memory at most m - 1 is constructed. When the generator matrix of B is systematic, the convolutional encoder is systematic, basic, noncatastrophic and minimal. Long codes constructed in this manner are shown to satisfy a Gilbert-Varshnmov bound.     

Nonhomogeneous Trellis codes for the Quasi-Synchronous Multiple-Access Binary adder channel with Two Users

A trellis code is {em homogeneous} if the number of branches emanating from each node (or state) in the trellis diagram is constant. For example, convolutional codes are linear homogeneous trellis codes. A trellis code is {em nonhomogeneous} if the number of branches emanating from each node in the trellis diagram is not the same. The two-user binary adder channel is a multiple-access channel with two binary inputs,x_{1}andx_{2}, and one ternary output,y = x_{1} + x_{2}, where the addition is done in the real number field. The adder channel is synchronous if both encoders and the decoder maintain block (frame) synchronism. It is quasi-synchronous if the encoders do not start their blocks at the same time, but the decoder knows the position of each block. The difference between the starting times of the blocks is called the slippage. The channel is asynchronous if no block synchronism exists among the encoders and the decoder. Some uniquely decodable code pairs(C_{1}, C_{2})are presented that can be used to transmit information reliably over the quasi-synchronous binary adder channel with two users. One of the codes is a nonhomogeneous trellis code, the other is a common block code. Our code rates are better than Deaett-Wolf codes and are close to or equal to the asymptotic rates of Kasami {em et al}. A method for calculating the rates of nonhomogeneous trellis codes is described. An algorithm for finding more uniquely decodable code pairs for the quasi-synchronous binary adder channel is formulated.     

Binary convolutional codes for a multiple-access channel (Corresp.)

Binary convolutional (linear) code pairs are investigated for use on the two-user adder channel. Maximum likelihood decoding is discussed, and a two-user decoding trellis is defined. The L-free distance of a convolutional code pair is defined and shown to be equal to the free distance of the mod-2 sum of the two single-user codes. It follows that the code pair is uniquely decodable if and only if the mod-2 sum code has an inverse, and that the code pair is subject to catastrophic error propagation if and only if the mod-2 sum code is catastrophic. These results also imply that no uniquely decodable binary convolutional (linear) code pairs exist with a rate sum above time sharing.     

8-PSK trellis codes for a Rayleigh channel

A suboptimal trellis coding approach based on the concept of combining a good convolutional code and bit interleavers is presented. The aim is to improve the reliability of digital radio communication over a fading channel. It is shown that over a Rayleigh channel and for a fixed code complexity the proposed system is superior to the baseline system. Its performance is analyzed using the generalized R_o and the upper bound on the bit error rate. The results suggest that on a Rayleigh channel, the standard trellis codes may not be the correct approach for improving the reliability of the communication channel. The discussion is restricted to a rate 2/3 coded system with 8-PSK modulation