High-rate punctured convolutional self-doubly orthogonal codes for iterative threshold decoding

The puncturing technique allows obtaining high-rate convolutional codes from low-rate convolutional codes used as mother codes. This technique has been successfully applied to generate good high-rate convolutional codes which are suitable for Viterbi and sequential decoding. In this paper, we investigate the puncturing technique for convolutional self-doubly orthogonal codes (CSO/sup 2/C) which are decoded using an iterative threshold-decoding algorithm. Based on an analysis of iterative threshold decoding of the rate-R=b/(b+1) punctured systematic CSO/sup 2/C, the required properties of the rate-R=1/2 systematic convolutional codes (SCCs) used as mother codes are derived. From this analysis, it is shown that there is no need for the punctured mother codes to respect all the required conditions, in order to maintain the double orthogonality at the second iteration step of the iterative threshold-decoding algorithm. The results of the search for the appropriate rate-R=1/2 SCCs used as mother codes to yield a large number of punctured codes of rates 2/3/spl les/R/spl les/6/7 are presented, and some of their error performances evaluated.     

Iterative threshold decoding without interleaving for convolutional self-doubly orthogonal codes

A novel iterative error control technique based on the threshold decoding algorithm and new convolutional self-doubly orthogonal codes is proposed. It differs from parallel concatenated turbo decoding as it uses a single convolutional encoder, a single decoder and hence no interleaver, neither at encoding nor at decoding. Decoding is performed iteratively using a single threshold decoder at each iteration, thereby providing good tradeoff between complexity, latency and error performance.     

Generalized threshold decoding of convolutional codes

A one-step threshold decoding method previously presented for cyclic block codes is shown to apply generally to linear convolutional codes. It is further shown that this method generalizes in a natural way to allow decoding of the received sequence in its unquantized analog form.     

Nonlinear analysis of the iterative decoding of parallel concatenated convolutional codes

In this correspondence, we introduce a simple one-dimensional (1-D) nonlinear map to describe the iterates of the bit-error rate (BER) of parallel-concatenated convolutional codes (PCCC) on the binary-input Gaussian channel. A lower bound on this map is derived based upon the weight enumerator of the constituent codes, thus enabling the characterization of the dynamics of the decoder in terms of fixed points, along with the associated stability analysis.     

Joint source-channel decoding of variable-length codes for convolutional codes and turbo codes

Several recent publications have shown that joint source-channel decoding could be a powerful technique to take advantage of residual source redundancy for fixed- and variable-length source codes. This letter gives an in-depth analysis of a low-complexity method recently proposed by Guivarch et al., where the redundancy left by a Huffman encoder is used at a bit level in the channel decoder to improve its performance. Several simulation results are presented, showing for two first-order Markov sources of different sizes that using a priori knowledge of the source statistics yields a significant improvement, either with a Viterbi channel decoder or with a turbo decoder.     

A robust decoding for long convolutional codes

Sequential decoding is an attractive technique to achieve the reliability of communication promised by the channel coding theory. But, because it utilizes the Fano metric, its performance is sensitive to channel parameter variations and it cannot simultaneously minimize both decoding effort and probability of decoding error. Based on the distance properties of the codes, we have derived a new set of metric which not only can overcome the two drawbacks caused by the Fano metric but also can significantly reduce the decoding effort required by sequential decoding.     

Low-complexity ML decoding for convolutional tail-biting codes

Recently, a maximum-likelihood (ML) decoding algorithm with two phases has been proposed for convolutional tailbiting codes [1]. The first phase applies the Viterbi algorithm to obtain the trellis information, and then the second phase employs the algorithm A* to find the ML solution. In this work, we improve the complexity of the algorithm A* by using a new evaluation function. Simulations showed that the improved A* algorithm has over 5 times less average decoding complexity in the second phase when E_b/N₀? 4 dB.     

卷积码的通用编译码

介绍了实现各种不同码型卷积码的编、译码的通用算法.在考虑程序代码效率、执行效率和程序的可读性的情况下,给出它的程序实现,只需要给定不同的生成多项式,就可以实现各种不同码率和不同约束长度的卷积码编码和译码,能简化通信系统中的软件实现.     

A low-complexity SISO multiuser detector for iterative decoding of asynchronous CDMA systems with convolutional codes

The optimal decoding scheme for asynchronous code-division multiple-access (CDMA) systems that employ convolutional codes results in a prohibitive computational complexity. To reduce the computational complexity, an iterative receiver structure was proposed for decoding multiuser data in a convolutional coded CDMA system. At each iteration, extrinsic information is exchanged between a soft-input soft-output (SISO) multiuser detector and a bank of single-user SISO channel decoders. A direct implementation of the optimal SISO multiuser detector, however, has exponential computational complexity in terms of the number of users which is still prohibitive for channels with a medium to large number of users. This paper presents a low-complexity SISO multiuser detector using the decision-feedback scheme, of which tentative hard decisions are made and fed back to the SISO multiuser from the previous decoding output. In the proposed scheme, the log-likelihood ratios (LLR) as well as the tentative hard decisions of code bits are fed back from the SISO decoders. The hard decisions are used to constrain the trellis of the SISO multiuser detector and the LLRs are used to provide a priori information on the code bits. The detector provides good performance/complexity tradeoffs. The computational complexity of the detector can be set to be as low as linear in the number of users. Simulations show that the performance of the low-complexity SISO multiuser detector approaches that of the single-user system for moderate to high signal-to-noise ratios even for a large number of users.     

Differential trellis decoding of convolutional codes

This paper investigates the principle of metric differences for trellis decoding of convolutional codes. Based on this differential method, a new algorithm, referred to as differential trellis decoding (DTD), is proposed. DTD offers an alternative to the conventional “add-compare-select” (ACS) method for implementing the Viterbi algorithm     

截尾卷积码的译码算法分析

介绍了截尾卷积码的循环维特比译码算法和BCJR译码算法，以及在循环维特比算法基础上改进的环绕维特比译码算法和双向维特比算法，最后对各种译码算法的性能进行了仿真分析。     

Bidirectional decoding of convolutional codes for indoor cellularradio

Bidirectional suboptimal breadth-first decoding of convolutional codes is an attractive technique for slowly varying and quasi-static fading channels as it restricts the extent of decoding errors due to correct path loss to very heavy noise or interference regions. This paper compares the performance of such a decoding scheme to the Viterbi algorithm over wideband TDMA indoor radio links where equalization and space diversity are also used to combat dispersive fading and cochannel interference. On the basis of equal computational complexity and equal decoding delay, suboptimal, breadth-first, bidirectional decoding of a long constraint length convolutional code is shown to be superior to Viterbi decoding of a shorter constraint length code. Furthermore, this advantage increases as the outage criterion (in terms of bit error rate) becomes more stringent which makes bidirectional decoding particularly attractive for data applications and makes channel coding a more attractive alternative to increasing the space diversity order at the receiver     

基于OCDMA的新型卷积码译码方案

对光码分多址(OCDMA)的误码特性和卷积码进行研究,根据两者的特点提出了一种新的基于OCDMA多址干扰信道模型的卷积码译码方法.针对这种新型卷积码译码方法的抗误码性和译码速度,将它与原有的维特比(Viterbi)判决译码法进行了横向比较分析.分析结果表明,采用新型译码法可以有效提高卷积码的抗误码性能,同时也可以简化译码时的路径判决程序,降低译码复杂性并提高译码速度.     

Computational moments for sequential decoding of convolutional codes

The long standing conjecture is established that, for a discrete memoryless channel, there exists a linear convolutional code with infinite constraint length such that therhoth(rho geq 1)moment of the number ofF-hypotheses in the Fano sequential decoding algorithm is bounded, provided that the transmission rateRis less thanE_{0}( rho,r)/ rho, wherer(x)is a distribution over the channel input alphabet. A new concept of independence for a finite set of message sequences plays an essential role in averaging a product of likelihood ratios over an ensemble of code sequences in a code tree. A simpler version of the method can be applied to the proof of the conjecture for general tree codes.     

Graph-based iterative decoding algorithms for parity-concatenatedtrellis codes

We construct parity-concatenated trellis codes in which a trellis code is used as the inner code and a simple parity-check code is used as the outer code. From the Tanner-Wiberg-Loeliger (1981, 1996) graph representation, several iterative decoding algorithms can be derived. However, since the graph of the parity-concatenated code contains many short cycles, the conventional min-sum and sum-product algorithms cannot achieve near-optimal decoding. After some simple modifications, we obtain near-optimal iterative decoders. The modifications include either (a) introducing a normalization operation in the min-sum and sum-product algorithms or (b) cutting the short cycles which arise in the iterative Viterbi algorithm (IVA). After modification, all three algorithms can achieve near-optimal performance, but the IVA has the least average complexity. We also show that asymptotically maximum-likelihood (ML) decoding and a posteriori probability (APP) decoding can be achieved using iterative decoders with only two iterations. Unfortunately, this asymptotic behavior is only exhibited when the bit-energy-to-noise ratio is above the cutoff rate. Simulation results show that with trellis shaping, iterative decoding can perform within 1.2 dB of the Shannon limit at a bit error rate (BER) of 4×10^-5 for a block size of 20000 symbols. For a block size of 200 symbols, iterative decoding can perform within 2.1 dB of the Shannon limit     

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     

BEAST decoding of block codes obtained via convolutional codes

BEAST is a bidirectional efficient algorithm for searching trees. In this correspondence, BEAST is extended to maximum-likelihood (ML) decoding of block codes obtained via convolutional codes. First it is shown by simulations that the decoding complexity of BEAST is significantly less than that of the Viterbi algorithm. Then asymptotic upper bounds on the BEAST decoding complexity for three important ensembles of codes are derived. They verify BEAST's high efficiency compared to other algorithms. For high rates, the new asymptotic bound for the best ensemble is in fact better than previously known bounds.     

Variable-complexity trellis decoding of binary convolutional codes

Considers trellis decoding of convolutional codes with selectable effort, as measured by decoder complexity. Decoding is described for single parent codes with a variety of complexities, with performance “near” that of the optimal fixed receiver complexity coding system. Effective free distance is examined. Criteria are proposed for ranking parent codes, and some codes found to be best according to the criteria are tabulated, Several codes with effective free distance better than the best code of comparable complexity were found. Asymptotic (high SNR) performance analysis and error propagation are discussed. Simulation results are also provided     

Design of repeat-accumulate codes for iterative detection and decoding

Extrinsic information transfer (EXIT) charts are used to design systematic and nonsystematic repeat-accumulate (RA) codes for iterative detection and decoding. The convergence problems of nonsystematic RA codes are solved by introducing a biregular, or doped, layer of check nodes. As examples, such nonsystematic codes are designed for multi-input/multi-output (MIMO) fading channels and are shown to operate close to capacity.