Design of parallel concatenated convolutional codes

A parallel concatenated convolutional coding scheme consists of two constituent systematic: convolutional encoders linked by an interleaver. The information bits at the input of the first encoder are scrambled by the interleaver before entering the second encoder. The codewords of the parallel concatenated code consist of the information bits followed by the parity check bits of both encoders. Parallel concatenated codes (turbo codes), decoded through an iterative decoding algorithm of relatively low complexity, have been shown to yield remarkable coding gains close to theoretical limits. We characterize the separate contributions that the interleaver length and constituent codes give to the overall performance of the parallel concatenated code, and present some guidelines for the optimal design of the constituent convolutional codes     

On dualizing trellis-based APP decoding algorithms

The trellis of a finite Abelian group code is locally (i.e., trellis section by trellis section) related to the trellis of the corresponding dual group code which allows one to express the basic operations of the a posteriori probability (APP) decoding algorithm (defined on a single trellis section of the primal trellis) in terms of the corresponding dual trellis section. Using this local approach, any algorithm employing the same type of operations as the APP algorithm can, thus, be dualized, even if the global dual code does not exist (e.g., nongroup codes represented by a group trellis). Given this, the complexity advantage of the dual approach for high-rate codes can be generalized to a broader class of APP decoding algorithms, including suboptimum algorithms approximating the true APP, which may be more attractive in practical applications due to their reduced complexity. Moreover, the local approach opens the way for mixed approaches where the operations of the APP algorithm are not exclusively performed on the primal or dual trellis. This is inevitable if the code does not possess a trellis consisting solely of group trellis sections as, e.g., for certain terminated group or ring codes. The complexity reduction offered by applying dualization is evaluated. As examples, we give a dual implementation of a suboptimum APP decoding algorithm for tailbiting convolutional codes, as well as dual implementations of APP algorithms of the sliding-window type. Moreover, we evaluate their performance for decoding usual tailbiting codes or convolutional codes, respectively, as well as their performance as component decoders in iteratively decoded parallel concatenated schemes.     

Assembled space-time turbo trellis codes

A novel full rate space-time turbo trellis code, referred to as an assembled space-time turbo trellis code (ASTTTC), is presented in this paper. For this scheme, input information binary sequences are first encoded using two parallel concatenated convolutional encoders. The encoder outputs are split into four parallel streams and each of them is modulated by a QPSK modulator. The modulated symbols are assembled by a predefined linear function rather than punctured as in the standard schemes. This results in a lower code rate and a higher coding gain over time-varying fading channels. An extended two-dimensional (2-D) log-MAP (maximum a posteriori probability) decoding algorithm, which simultaneously calculates two a posteriori probabilities (APP), is developed to decode the proposed scheme. Simulation results show that, under the same conditions, the proposed code considerably outperforms the conventional space-time turbo codes over time-varying fading channels.     

Unveiling turbo codes: some results on parallel concatenated codingschemes

A parallel concatenated coding scheme consists of two simple constituent systematic encoders linked by an interleaver. The input bits to the first encoder are scrambled by the interleaver before entering the second encoder. The codeword of the parallel concatenated code consists of the input bits to the first encoder followed by the parity check bits of both encoders. This construction can be generalized to any number of constituent codes. Parallel concatenated schemes employing two convolutional codes as constituent codes, in connection with an iterative decoding algorithm of complexity comparable to that of the constituent codes, have been previously shown to yield remarkable coding gains close to theoretical limits. They have been named, and are known as, “turbo codes”. We propose a method to evaluate an upper bound to the bit error probability of a parallel concatenated coding scheme averaged over all interleavers of a given length. The analytical bounding technique is then used to shed some light on some crucial questions, which have been floating around in the communications community since the proposal of turbo codes     

An extensive search for good punctured rate-k/(k+1) recursive convolutional codes for serially concatenated convolutional codes

In many practical applications requiring variable-rate coding and/or high-rate coding for spectral efficiency, there is a need to employ high-rate convolutional codes (CC), either by themselves or in a parallel or serially concatenated scheme. For such applications, in order to keep the trellis complexity of the code constant and to permit the use of a simplified decoder that can accommodate multiple rates, a mother CC is punctured to obtain codes with a variety of rates. This correspondence presents the results of extensive search for optimal puncturing patterns for recursive convolutional codes leading to codes of rate k/(k+1) (k an integer) to be used in serially concatenated convolutional codes (SCCC). The code optimization is in the sense of minimizing the required signal-to-noise ratio (SNR) for two target bit-error rate (BER) and two target frame-error rate (FER) values. We provide extensive sample simulation results for rate-k/(k+1) SCCC codes employing our optimized punctured CC.     

Analysis, design, and iterative decoding of double seriallyconcatenated codes with interleavers

A double serially concatenated code with two interleavers consists of the cascade of an outer encoder, an interleaver permuting the outer codeword bits, a middle encoder, another interleaver permuting the middle codeword bits, and an inner encoder whose input words are the permuted middle codewords. The construction can be generalized to h cascaded encoders separated by h-1 interleavers, where h>3. We obtain upper bounds to the average maximum likelihood bit-error probability of double serially concatenated block and convolutional coding schemes. Then, we derive design guidelines for the outer, middle, and inner codes that maximize the interleaver gain and the asymptotic slope of the error probability curves. Finally, we propose a low-complexity iterative decoding algorithm. Comparisons with parallel concatenated convolutional codes, known as “turbo codes”, and with the proposed serially concatenated convolutional codes are also presented, showing that in some cases, the new schemes offer better performance     

Symbol-by-symbol MAP decoding algorithm for high-rate convolutionalcodes that use reciprocal dual codes

A symbol-by-symbol maximum a posteriori (MAP) decoding algorithm for high-rate convolutional codes applying reciprocal dual convolutional codes is presented. The advantage of this approach is a reduction of the computational complexity since the number of codewords to consider is decreased. All requirements for iterative decoding schemes are fulfilled. Since tail-biting convolutional codes are equivalent to quasi-cyclic block codes, the decoding algorithm for truncated or terminated convolutional codes is modified to obtain a soft-in/soft-out decoder for high-rate quasi-cyclic block codes which also uses the dual code because of complexity reasons. Additionally, quasi-cyclic block codes are investigated as component codes for parallel concatenation. Simulation results obtained by iterative decoding are compared with union bounds for maximum likelihood decoding. The results of a search for high-rate quasi-cyclic block codes are given in the appendix     

MAP decoding of convolutional codes using reciprocal dual codes

A new symbol-by-symbol maximum a posteriori (MAP) decoding algorithm for high-rate convolutional codes using reciprocal dual convolutional codes is presented. The advantage of this approach is a reduction of the computational complexity since the number of codewords to consider is decreased for codes of rate greater than 1/2. The discussed algorithms fulfil all requirements for iterative (“turbo”) decoding schemes. Simulation results are presented for high-rate parallel concatenated convolutional codes (“turbo” codes) using an AWGN channel or a perfectly interleaved Rayleigh fading channel. It is shown that iterative decoding of high-rate codes results in high-gain, moderate-complexity coding     

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.     

Serial concatenation of interleaved codes: performance analysis,design, and iterative decoding

A serially concatenated code with interleaver consists of the cascade of an outer encoder, an interleaver permuting the outer codewords bits, and an inner encoder whose input words are the permuted outer codewords. The construction can be generalized to h cascaded encoders separated by h-1 interleavers. We obtain upper bounds to the average maximum-likelihood bit error probability of serially concatenated block and convolutional coding schemes. Then, we derive design guidelines for the outer and inner encoders that maximize the interleaver gain and the asymptotic slope of the error probability curves. Finally, we propose a new, low-complexity iterative decoding algorithm. Throughout the paper, extensive comparisons with parallel concatenated convolutional codes known as “turbo codes” are performed, showing that the new scheme can offer superior performance     

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     

Simultaneous zero-tailing of parallel concatenated codes

In a parallel concatenated convolutional code, an information sequence is encoded by a convolutional encoder, and an interleaved version of the information sequence is encoded by another convolutional encoder. We discuss the situation in which we require both convolutional encoders to end in the all-zero state. To do so, we have to split an information word in two parts. One part contains the true information bits, and the second part contains the so-called tail bits, which are special bits with values computed such that both encoders end in the all-zero state. Depending on the interleaver, a different number of tail bits are needed. By using a constructive method, we give a characterization of all interleavers for a prescribed number of tail bits. We explain the method of encoding. In addition, simulations have been carried out to investigate the performance of codes resulting from simultaneous zero-tailing. This shows that simultaneous zero-tailing is similar in performance as compared to previously known zero-tailing methods (but with fewer trellis termination bits) and that it is better than zero-tailing just one of the encoders.     

Relation between encoder and syndrome former variables and symbol reliability estimation using a syndrome trellis

We derive a linear correspondence between the variables of an encoder and those of a corresponding syndrome former. Using the derived correspondence, we show that the log-likelihood ratio of an information bit conditioned on a received sequence can be equally calculated using the syndrome trellis. It is shown that the proposed method also applies to recursive systematic convolutional codes which are typical constituent codes for turbo codes. Moreover, we show that soft-in syndrome decoding considering a priori probabilities of information bits is possible in the same way as for Viterbi decoding based on the code trellis. Hence, the proposed method can be applied to iterative decoding such as turbo decoding. We also show that the proposed method is effective for high-rate codes by making use of trellis modification.     

Scarce-state-transition syndrome-former error-trellis decoding of(n,n-1) convolutional codes

A novel scarce-state-transition (SST) type trellis decoding system for (n,n-1) convolutional codes with coherent BPSK signals is proposed. The new system retains the same number of binary comparisons as the syndrome-former trellis decoding technique. Like the original SST-type encoder trellis technique, the proposed system is also suitable for CMOS VLSI implementation. A combination of the two techniques results in a less complex and low power consumption decoding system     

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     

On turbo decoding of nonbinary codes

Symbol-by-symbol maximum a posteriori (MAP) decoding algorithms for nonbinary block and convolutional codes over an extension field GF(p ^a) are presented. Equivalent MAP decoding rules employing the dual code are given which are computationally more efficient for high-rate codes. It is shown that these algorithms meet all requirements needed for iterative decoding as the output of the decoder can be split into three independent estimates: soft channel value, a priori term and extrinsic value. The discussed algorithms are then applied to a parallel concatenated coding scheme with nonbinary component codes in conjunction with orthogonal signaling     

Design of ring convolutional trellis codes for MAP decoding of MPEG-4 images

We propose a trellis-coded modulation system using continuous-phase frequency-shift keying (CPFSK) and ring convolutional codes for transmitting the bits generated by an embedded zerotree wavelet encoder. Improved performance is achieved by using maximum a posteriori decoding of the zerotree symbols, and ring convolutional trellis codes are determined for this decoding method. The CPFSK transmitter is decomposed into a memoryless modulator and a continuous phase encoder over the ring of integers modulo 4; the latter is combined with a polynomial convolutional encoder over the same ring. In the code design process, a search is made of the combined trellis, where the branch metrics are modified to include the source transition matrix. Simulation results of image transmission are provided using the optimized system, including mismatched channel cases.     

Coset codes viewed as terminated convolutional codes

Coset codes are considered as terminated convolutional codes. Based on this approach, three new general results are presented. First, it is shown that the iterative squaring construction can equivalently be defined from a convolutional code whose trellis terminates. This convolutional code determines a simple encoder for the coset code considered, and the state and branch labelings of the associated trellis diagram become straightforward. Also, from the generator matrix of the code in its convolutional code form, much information about the trade-off between the state connectivity and complexity at each section, and the parallel structure of the trellis, is directly available. Based on this generator matrix, it is shown that the parallel branches in the trellis diagram of the convolutional code represent the same coset code C₁ of smaller dimension and shorter length. Utilizing this fact, a two-stage optimum trellis decoding method is devised. The first stage decodes C₁ while the second stage decodes the associated convolutional code, using the branch metrics delivered by stage 1. Finally, a bidirectional decoding of each received block starting at both ends is presented. If about the same number of computations is required, this approach remains very attractive from a practical point of view as it roughly doubles the decoding speed. This fact is particularly interesting whenever the second half of the trellis is the mirror image of the first half, since the same decoder can be implemented for both parts     

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.     

Convolutional Codes Under a Minimal Trellis Complexity Measure

We conduct a code search, restricted to the recently introduced class of generalized punctured convolutional codes, under the minimal trellis complexity measure defined by McEliece and Lin. For the same decoding complexity and the same code rate, new codes are compared to well-known existing classes of convolutional codes. Some of the best convolutional codes (in a distance spectrum sense) of existing and new trellis complexities are tabulated.