Two 16-state, rate R=2/4 trellis codes whose free distances meetthe Heller bound

For rate R=1/2 convolutional codes with 16 states there exists a gap between Heller's (1968) upper bound on the free distance and its optimal value. This article reports on the construction of 16-state, binary, rate R=2/4 nonlinear trellis and convolutional codes having d _free=8; a free distance that meets the Heller upper bound. The nonlinear trellis code is constructed from a 16-state, rate R=1/2 convolutional code over Z₄ using the Gray map to obtain a binary code. Both convolutional codes are obtained by computer search. Systematic feedback encoders for both codes are potential candidates for use in combination with iterative decoding. Regarded as modulation codes for 4-PSK, these codes have free squared Euclidean distance d_{E, free}²=16     

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.     

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     

New short constraint length convolutional code constructions for selected rational rates (Corresp.)

New short constraint length convolutional code constructions are tabulated for ratesR=(n-k)/n, k=1,2, cdots ,n-1withn=2, 3,cdots ,8, and for constraint lengthsK=3,4, cdots,8. These codes have been determined by iterative search based upon a criterion of optimizing the free distance profile. Specifically, these codes maximize the free distanced_{f}while minimizing the number of adversaries in the distance, or weight, spectrum. In several instances we demonstrate the superiority of these codes over previously published code constructions at the same rate and constraint length. These codes are expected to have a number of applications, including combined source-channel coding schemes as well as coding for burst or impulsive noise channels.     

A convolutional single-parity-check concatenated coding scheme forhigh-data-rate applications

The coding scheme uses a set of n convolutional codes multiplexed into an inner code and a (n,n-1) single-parity-check code serving as the outer code. Each of the inner convolutional codes is decoded independently, with maximum-likelihood decoding being achieved using n parallel implementations of the Viterbi algorithm. The Viterbi decoding is followed by additional outer soft-decision single-parity-check decoding. Considering n=12 and the set of short constraint length K=3, rate 1/2 convolutional codes, it is shown that the performance of the concatenated scheme is comparable to the performance of the constraint length K=7, rate 1/2 convolutional code with standard soft-decision Viterbi decoding. Simulation results are presented for the K=3, rate 1/2 as well as for the punctured K=3, rate 2/3 and rate 3/4 inner convolutional codes. The performance of the proposed concatenated scheme using a set of K=7, rate 1/2 inner convolutional codes is given     

Complementary punctured convolutional (CPC) codes and theirapplications

Presents a new class of punctured convolutional codes that are complementary (CPC codes). A set of punctured convolutional codes derived from the same original low rate code are said to be complementary if they are equivalent (in terms of their distance properties) and if when combined yield at least the original low rate code. Based on these CPC codes the author proposes and analyzes a variation of the type II hybrid ARQ scheme which is called a type III hybrid ARQ scheme. With the type III hybrid ARQ scheme, the starting code rate can be chosen to match the channel noise requirements, and as with the type II scheme, packets that are detected in error are not discarded, but are combined with complementary transmissions provided by the transmitter to help recover the transmitted message. The main advantage is that any complementary sequence sent for a packet that is detected with errors is self decodable. That is the decoder does not have to rely on previously received sequences for the same data packet for decoding, as is generally the case with incremental redundancy ARQ schemes. This feature is desirable especially in situations where a transmitted packet can be lost or severely damaged as a result of interference. CPC codes can find applications in diversity transmission systems. A novel complementary diversity scheme which makes use of CPC codes is briefly discussed     

On (n, n-1) convolutional codes with low trellis complexity

We show that the state complexity profile of a convolutional code C is the same as that of the reciprocal of the dual code of C in case that minimal encoders for both codes are used. Then, we propose an optimum permutation for any given (n, n-1) binary convolutional code that will yield an equivalent code with the lowest state complexity. With this permutation, we are able to find many (n, n-1) binary convolutional codes which are better than punctured convolutional codes of the same code rate and memory size by either lower decoding complexity or better weight spectra     

Asymptotic performance comparison of concatenated (turbo) codes over GF(4)

In this paper, we investigate and compare the asymptotic performance of concatenated convolutional coding schemes over GF(4) over additive white Gaussian noise (AWGN) channels. Both parallel concatenated codes (PCC) and serial concatenated codes (SCC) are considered. We construct such codes using optimal non‐binary convolutional codes where optimality is in the sense of achieving the largest minimum distance for a fixed number of encoder states. Code rates of the form k₀/(k₀ + 1) for k₀=1, 8, and 64 are considered, which suite a wide spectrum of communications applications. For all of these code rates, we find the minimum distance and the corresponding multiplicity for both concatenated code systems. This is accomplished by feeding the encoder with all possible weight‐two and weight‐three input information patterns and monitoring, at the output of the encoder, the weight of the corresponding codewords and their multiplicity. Our analytical results indicate that the SCC codes considerably outperform their counterpart PCC codes at a much lower complexity. Inspired by the superiority of SCC codes, we also discuss a mathematical approach for analysing such codes, leading to a more comprehensive analysis and allowing for further improvement in performance by giving insights on designing a proper interleaver that is capable of eliminating the dominant error patterns. Copyright © 2004 John Wiley & Sons, Ltd.     

Comparative study of turbo equalization schemes usingconvolutional, convolutional turbo, and block-turbo codes

Turbo equalizers have been shown to be successful in mitigating the effects of inter-symbol interference introduced by partial response modems and by dispersive channels for code rates of R⩽ 1/2. We comparatively studied the performance of a range of binary phase-shift keying turbo equalizers employing block-turbo codes, namely Bose-Chaudhuri-Hocquenghen (1960, 1959) turbo codes, convolutional codes, and convolutional turbo codes having high code rates, such as R=3/4 and R=5/6, over a dispersive five-path Gaussian channel and an equally weighted symbol-spaced five-path Rayleigh fading channel. These turbo equalization schemes were combined with an iterative channel estimation scheme in order to characterize a realistic scenario. The simulation results demonstrated that the turbo-equalized system using convolutional turbo codes was the most robust system for all code rates investigated     

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     

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.     

A fast algorithm for computing distance spectrum of convolutionalcodes

A fast algorithm for searching a tree (FAST) is presented for computing the distance spectrum of convolutional codes. The distance profile of a code is used to limit substantially the error patterns that have to be searched. The algorithm can easily be modified to determine the number of nonzero information bits of an incorrect path as well as the length of an error event. For testing systematic codes, a faster version of the algorithm is given. FAST is much faster than the standard bidirectional search. On a microVAX, d_∞=27 was verified for a rate R=1/2, memory M=25 code in 37 s of CPU time. Extensive tables of rate R=1/2 encoders are given. Several of the listed encoders have distance spectra superior to those of any previously known codes of the same rate and memory. A conjecture than an R=1/2 systematic convolutional code of memory 2M will perform as well as a nonsystematic convolutional code of memory M is given strong support     

A new high rate code scheme with highly parallel and low complexity decoding algorithm

A new high rate code scheme is proposed in this paper. It consists of serial concatenated recursive systematic ordinary (nonpunctured) convolutional codes with only 8 states in the trellis of the corresponding reciprocal dual codes. With a low complexity and highly parallel decoding algorithm, over additive white Gaussian noise channels, the proposed codes can achieve good bit error rate (BER) performance comparable to that of turbo codes and low density parity check (LDPC) codes. At code rate R=16/17, the overall decoding complexity of the proposed code scheme is almost half that of the LDPC codes.     

Coded continuous phase modulation using ring convolutional codes

Rate 1/2 convolutional codes over the ring of integers modulo M are combined with M-ary continuous phase modulation (CPM) schemes whose modulation indices are of the form h=1/M. An M-ary CPM scheme with h=1/M can be modeled by a continuous-phase encoder (CPE) followed by a memoryless modulator (MM), where the CPE is linear over the ring of integers modulo M. The fact that the convolutional code and the CPE are over the same algebra allows the state of the CPE to be fed back and used by the convolutional encoder. A modified Euclidean distance function that substantially simplifies the search for good codes has been derived and used to find new codes. Numerical results show that this approach consistently improves the performance as compared to coded schemes using binary convolutional codes with the same decoding complexity     

On the computation of weight enumerators for convolutional codes

Performance bounds for maximum-likelihood decoding of convolutional codes over memoryless channels are commonly measured using the distance weight enumerator T(x,y), also referred to as the transfer function, of the code. This paper presents an efficient iterative method to obtain T(x,y) called the state reduction algorithm. The algorithm is a systematic technique to simplify signal flow graphs that algebraically manipulate the symbolic adjacency matrix associated with the convolutional code. Next, the algorithm is modified to compute the first few terms of the series expansion of T(1,y) and {/spl part/T(x,y)//spl part/x}/sub x=1/ (the distance spectra) without first computing the complete T(x,y).     

Rate-compatible convolutional codes for multirate DS-CDMA systems

New rate-compatible convolutional (RCC) codes with high constraint lengths and a wide range of code rates are presented. These new codes originate from rate 1/4 optimum distance spectrum (ODS) convolutional parent encoders with constraint lengths 7-10. Low rate encoders (rates 115 down to 1/10) are found by a nested search, and high rate encoders (rates above 1/4) are found by rate-compatible puncturing. The new codes form rate-compatible code families more powerful and flexible than those previously presented. It is shown that these codes are almost as good as the existing optimum convolutional codes of the same fates. The effects of varying the design parameters of the rate-compatible punctured convolutional (RCPC) codes, i.e., the parent encoder rate, the puncturing period, and the constraint length, are also examined. The new codes are then applied to a multicode direct-sequence code-division multiple-access (DS-CDMA) system and are shown to provide good performance and rate-matching capabilities. The results, which are evaluated in terms of the efficiency for Gaussian and Rayleigh fading channels, show that the system efficiency increases with decreasing code rate     

A pragmatic approach to trellis-coded modulation

Since the early 1970s, for power-limited applications, the convolutional code constraint length K=7 and rate 1/2, optimum in the sense of maximum free distance and minimum number of bit errors caused by remerging paths at the free distance, has become the de facto standard for coded digital communication. This was reinforced when punctured versions of this code became the standard for rate 3/4 and 7/8 codes for moderately bandlimited channels. Methods are described for using the same K=7, rate 1/2 convolutional code with signal phase constellations of 8-PSK and 160PSK and quadrature amplitude constellations of 16-QASK, 64-QASK, and 256-QASK to achieve, respectively, 2 and 3, and 2, 4, and 6 b/s/Hz bandwidth efficiencies while providing power efficiency that in most cases is virtually equivalent to that of the best Ungerboeck codes for constraint length 7 or 64 states. This pragmatic approach to all coding applications permits the use of a single basic coder and decoder to achieve respectable coding (power) gains for bandwidth efficiencies from 1 b/s/Hz to 6 b/s/Hz     

On Convolutional Coupled Codes

The error correcting performance of the parallel concatenation of two convolutional codes is very promising. Inspired from this construction which is near the Shannon limit error correction performance, we consider a further development of concatenated codes. In this construction systematic convolutional codes and rate 1/2 systematic block codes are linked together such that only the systematic part of the convolutional codes is encoded with the block encoders. The bits of each information vector of the convolutional codes are scrambled by a given interleaving before entering to the block encoders. Then, differently from the Turbo codes, in which information symbols and the redundancy from the constituent codes are transmitted [1], we transmit only the redundancy from the convolutional and block codes. We call this construction convolutional coupled codes and code coupling is the new scheme of code concatenation. The structural properties of the generator matrix of the convolutional coupled code is investigated. It's minimum distance is lower and upper bounded and we introduce the term of the effective free distance. Simulation results will show, that convolutional coupled codes have the potential of being a realistic alternative to Turbo codes.     

Adaptive type II hybrid ARQ scheme using zigzag code

The authors propose a new hybrid type II ARQ scheme based on the simple multidimensional concatenated zigzag code. Owing to the fact that the error-correcting capability of zigzag codes is far better than that of conventional convolutional codes, the throughput of our scheme is better than existing hybrid ARQ schemes     

Robust modem and coding techniques for FM hybrid ICOC DAB

The design of robust modem and FEC (forward error correction) code techniques with application to the transmission of an FM hybrid analog/digital in-band on-channel (IBOC) digital audio broadcast (DAB) signal is presented here. The FEC codes are derived from an original lower rate convolutional code (R=1/3). The original code is segmented into a pair of “complementary” components, which form independent codes, each with a higher rate (less redundancy) than the base code. The exploitation of channel state information (CSI) and special interleaving techniques are described for application to FM hybrid IBOC DAB with its unique interference environment and selective fading due to multipath. Simulation results confirm the robustness of the design