It has been widely observed that there exists a fundamental tradeoff between the minimum (Hamming) distance properties and the iterative decoding convergence behavior of turbo-like codes. While capacity-achieving code ensembles typically are asymptotically bad in the sense that their minimum distance does not grow linearly with block length, and they therefore exhibit an error floor at moderate-to-high signal-to-noise ratios, asymptotically good codes usually converge further away from channel capacity. In this paper, we introduce the concept of tuned turbo codes, a family of asymptotically good hybrid concatenated code ensembles, where asymptotic minimum distance growth rates, convergence thresholds, and code rates can be tradedoff using two tuning parameters:$\lambda $and$\mu $. By decreasing$\lambda $, the asymptotic minimum distance growth rate is reduced in exchange for improved iterative decoding convergence behavior, while increasing$\lambda $raises the asymptotic minimum distance growth rate at the expense of worse convergence behavior, and thus, the code performance can be tuned to fit the desired application. By decreasing$\mu $, a similar tuning behavior can be achieved for higher rate code ensembles.

We consider an ensemble of systematic low-density parity-check (LDPC) codes of length N with linear encoding complexity, i.e., with complexity O(N). We call these codes partially-regular, since they can be considered as modifications of regular LDPC codes. Further, their iterative decoding thresholds on the binary erasure channel (BEC) are found to be significantly better than the thresholds of the corresponding regular LDPC codes.

An iterative decoding threshold analysis for terminated regular LDPC convolutional (LDPCC) codes is presented. Using density evolution techniques, the convergence behavior of an iterative belief propagation decoder is analyzed for the binary erasure channel and the AWGN channel with binary inputs. It is shown that for a terminated LDPCC code ensemble, the thresholds are better than for corresponding regular and irregular LDPC block codes.

Existence type lower bounds on the free distance of periodically time-varying LDPC convolutional codes and on the minimum distance of tail-biting LDPC convolutional codes are derived. It is demonstrated that the bound on free distance of periodically time-varying LDPC convolutional codes approaches the bound on free distance of general (nonperiodic) time-varying LDPC convolutional codes as the period increases. The proof of the bound is based on lower bounding the minimum distance of corresponding tail-biting LDPC convolutional codes, which is of interest in its own right.

We present a new class of iteratively decodable turbo-like codes, called braided convolutional codes. Constructions and encoding procedures for tightly and sparsely braided convolutional codes are introduced. Sparsely braided codes exhibit good convergence behavior with iterative decoding, and a statistical analysis using Markov permutors shows that the free distance of these codes grows linearly with constraint length, i.e., they are asymptotically good.

A new class of binary iteratively decodable codes with good decoding performance is presented. These codes, called braided block codes (BBCs), operate on continuous data streams and are constructed by interconnection of two component block codes. BBCs can be considered as convolutional (or sliding) version of either Elias' product codes or expander codes. In this paper, we define BBCs, describe methods of their construction, analyze code properties, and study asymptotic iterative decoding performance.

It has recently been shown that the minimum distance of the ensemble of repeat multiple accumulate codes grows linearly with block length. In this paper, we present a method to obtain the distance growth rate coefficient of multiple-serially concatenated code ensembles and determine the growth rate coefficient of the rate 1/2 double-serially concatenated code consisting of an outer memory one convolutional code followed by two accumulators. We compare both the growth rate of the minimum distance, as well as the convergence behavior, of this code with rate 1/2 repeat multiple accumulate codes, and we show that repeat multiple accumulate codes have better minimum distance growth but worse performance in terms of convergence.

LDPC convolutional codes have been shown to be capable of achieving the same capacity-approaching performance as LDPC block codes with iterative message-passing decoding. In this paper, asymptotic methods are used to calculate a lower bound on the free distance for several ensembles of asymptotically good protograph-based LDPC convolutional codes. Further, we show that the free distance to constraint length ratio of the LDPC convolutional codes exceeds the minimum distance to block length ratio of corresponding LDPC block codes.

We introduce and analyze new constructions of LDPC convolutional codes and their tail-biting versions which are obtained from braided convolutional codes. The basic ideas behind the encoding and decoding architectures for these codes are presented. Additionally, asymptotic results concerning the iterative thresholds are shown for different ensembles. Finally, we evaluate the bit error rate performances of several codes by means of computer simulations.

Potentially large storage requirements and long initial decoding delays are two practical issues related to the decoding of low-density parity-check (LDPC) convolutional codes using a continuous pipeline decoder architecture. In this paper, we propose several reduced complexity decoding strategies to lessen the storage requirements and the initial decoding delay without significant loss in performance. We also provide bit error rate comparisons of LDPC block and LDPC convolutional codes under equal processor (hardware) complexity and equal decoding delay assumptions. A partial syndrome encoder realization for LDPC convolutional codes is also proposed and analyzed. We construct terminated LDPC convolutional codes that are suitable for block transmission over a wide range of frame lengths. Simulation results show that, for terminated LDPC convolutional codes of sufficiently large memory, performance can be improved by increasing the density of the syndrome former matrix.

A new class of codes is presented that features a block-convolutional structure—namely, laminated turbo codes. It allows combining the advantages of both a convolutional encoder memory and a block permutor, thus allowing a block-oriented decoding method. Structural properties of laminated turbo codes are analyzed and upper and lower bounds on free distance are obtained. It is then shown that the performance of laminated turbo codes compares favorably with that of turbo codes. Finally, we show that laminated turbo codes provide high rate flexibility without suffering any significant performance degradation.

In this paper, the tail-biting version of the low-density parity-check convolutional codes (LDPCCCs) is introduced and investigated. The definition of the tail-biting LDPCCCs (TB-LDPCCCs) is given through their parity-check matrices and the basic ideas behind the architectures of the encoders and decoders for these codes are also presented. In addition, the asymptotical lower bound for the minimum distance of these codes and simulation results are shown.

In this paper, we introduce and investigate the tail- biting low-density parity-check convolutional codes (LDPCCCs) based on protographs. We show a construction algorithm for these codes, which is based on a modified version of the PEG algorithm [1] and on the unwrapping [2] technique. The basic ideas behind the decoder architecture for these codes are also discussed. Finally, the performances of the tail-biting LDPCCCs based on protographs are evaluated through computer simulations, where we also examine a family of rate-compatible codes.

An ensemble of$(J,K)$-regular low-density parity- check (LDPC) convolutional codes is introduced and existence-type lower bounds on the minimum distance$d _ {\rm L}$of code segments of finite length$L$and on the free distance$d _{\rm free}$are derived. For sufficiently large constraint lengths$\nu$, the distances are shown to grow linearly with$\nu$and the ratio$d_ {\rm L}/\nu$approaches the ratio$d _{ {\rm free}}/\nu$for large$L$. Moreover, the ratio of free distance to constraint length is several times larger than the ratio of minimum distance to block length for Gallager's ensemble of (J,K)-regular LDPC block codes.

We propose a novel code design technique for irregular LDPC convolutional codes. The constructed codes can be encoded continuously in real time with the help of a shift-register based encoder. For moderate values of the syndrome former memory, simulation results show that the constructed codes outperform LDPC block codes with comparable hardware (processor) complexity.

Low-density parity-check convolutional codes offer the same good error-correcting performance as low-density parity-check block codes while having the ability to encode and decode arbitrary lengths of data. This makes these codes well suited to certain applications, such as forward error control on packet switching networks. In this paper we propose a decoder architecture for low-density parity-check convolutional codes with very large memories. These codes have very good error correcting properties and as such may be applicable in wireless sensor networks and space communication systems. We discuss a realization of this architecture for a (2048,3,6) code implemented on a field-programmable gate-array.

The free distance of convolutional codes is the most important parameter determining their performance under good channel conditions. In this paper, we investigate the free distance properties of turbo-like codes generated by non-terminated convolutional encoders and convolutional permutors. In particular, we prove the existence of such codes whose free distance exhibits the same asymptotic growth rate in the permuter memory as block turbo codes in the permuter size

Irregular low-density parity-check (LDPC) codes constructed from small protographs are one of the most powerful LDPC block codes. In this paper, we introduce the convolutional version of these codes. LDPC convolutional codes constructed from protographs have some advantages in comparison to LDPC block codes constructed from protographs, e.g., an effective pipeline decoding. We show that LDPC convolutional codes constructed from protographs have much lower error rates than analogous LDPC block codes with the same complexity and that they operate with low error rates near the Shannon limits even for a relatively small memory size

We consider construction and realization aspects of encoders and decoders for braided block codes (BBCs), which are a powerful class of iteratively decodable codes. An efficient encoder is proposed as well as a pipeline decoder realization. Also, upper and lower bounds on the free distance of BBCs are derived

The erasure correcting capability of LDPC codes with parity-check matrices composed of permutation matrices is considered. A new lower bound for number of the iteratively correcting erasures for the Zyablov-Pinsker algorithm is given

In this letter, a permutor design parameter, called the weight of a cycle through J-1 permutation matrices, for multiple turbo codes is introduced. Analogously to the single-permutor case of conventional turbo codes, we show the connection of the new parameter to the minimum distance of special classes of multiple turbo codes. In addition, simulation results are presented for multiple turbo codes based on the new design

In this paper, we study the problem of joint permutor analysis and design for J-dimensional multiple turbo codes with J constituent encoders, J>2. The concept of summary distance is extended to multiple permutors of size N and used as the design metric. Using the sphere-packing concept, we prove that the minimum length-2 summary distance (spread) Dmin,2is asymptoticly upper-bounded by O(NJ-1/J). We also show that the asymptotic minimum length-2L summary distance Dmin,2Lfor the class of random permutors is lower-bounded by O(NJ-2J-epsi/), where epsi>0 can be arbitrarily small. Then, using the technique of expurgating "bad" symbols, we show that the spread of random permutors can achieve the optimum growth rate, i.e., O(NJ-1/J), and that the asymptotic growth rate of Dmin,2Lcan also be improved. The minimum length-2 and length-4 summary distances are studied for an important practical class of permutors-linear permutors. We prove that there exist J-dimensional multiple linear permutors with optimal spread Dmin,2=O(NJ-1J/). Finally, we present several joint permutor construction algorithms applicable to multiple turbo codes of short and medium lengths

We present a new class of iteratively decodable turbo-like codes, called braided convolutional codes. Constructions and encoding procedures for tightly and sparsely braided codes are introduced. Sparsely braided codes exhibit good convergence behavior with iterative decoding, and a statistical analysis using Markov permutors shows that the free distance of these codes grows linearly with constraint length.

In this paper we introduce a new coding scheme - so-called laminated turbo codes. It is characterized by a block-convolutional structure that enables us to combine the advantages of a convolutional encoder memory and a block-oriented decoding method. We show that this block-convolutional structure is superior in terms of its error correction capability compared to the pure block structure of the corresponding self-concatenated code. Comparisons to turbo codes and multiple turbo codes are also included. Finally, the impact of the inter-block memory is investigated.

An ensemble of LDPC convolutional codes with parity-check matrices composed of permutation matrices is considered. The convergence of the iterative belief propagation based decoder for terminated convolutional codes in the ensemble is analyzed for binary-input output-symmetric memoryless channels using density evolution techniques. We observe that the structured irregularity in the Tanner graph of the codes leads to significantly better thresholds when compared to corresponding LDPC block codes

Asymptotic iterative decoding performance is analyzed for several classes of iteratively decodable codes when the block length of the codes N and the number of iterations I go to infinity. Three classes of codes are considered. These are Gallager's regular low-density parity-check (LDPC) codes, Tanner's generalized LDPC (GLDPC) codes, and the turbo codes due to Berrou et al. It is proved that there exist codes in these classes and iterative decoding algorithms for these codes for which not only the bit error probability P/sub b/, but also the block (frame) error probability P/sub B/, goes to zero as N and I go to infinity.

Block transmission over noisy communication channels is characterized by two performance criteria: the bit error probability P/sub b/ and the block error probability P/sub B/. If P/sub B/ goes to zero when N/spl rarr//spl infin/ (where N denotes the length of the permutors), P/sub b/ also must go to zero for all symbols in the block but, in general, the reverse is not true. Therefore we formulate the Shannon's condition for reliable communication over noisy channels. In this paper, we address the problem of reliable communication for iterative decoding of turbo codes.

While low-density parity-check (LDPC) convolutional codes tend to significantly outperform LDPC block codes with the same processor complexity, large storage requirements and a long initial decoding delay are two issues related to their continuous pipeline decoding architecture [A. Jimenez Feltstrom et al., (1999)]. In this paper, we propose reduced complexity decoding strategies to lessen the storage requirements and the initial decoding delay without significant loss in performance.

A lower bound on the free distance of LDPC convolutional codes defined by syndrome former matrices comprised of MtimesM permutation matrices is derived. We show that asymptotically, i.e., as Mrarrinfin, for almost all codes in the ensemble the free distance grows linearly with constraint length

A new permutor design for serially concatenated convolutional codes is presented. It is based on the construction of a permutation matrix without short cycles of special types. For such a permutor, we give a lower bound on the minimum distance of the overall code that is significantly larger than that achievable with first-order separation (spreading factors). Additionally, the minimum distance can be attuned to the permutation length. This property may be useful for the construction of codes with moderate block lengths.

Analytic expressions for the exact bit error probabilities of rate R=1/2, memory m=2 convolutional encoders are derived for a maximum-likelihood (ML) decoder and transmission over the binary-symmetric channel (BSC). The resulting expressions are rational functions of the crossover probability of the BSC. In addition to classical nonsystematic encoders without feedback, we consider also recursive systematic encoders, which became especially important as component encoders in concatenated coding schemes. To attest the validity of the results, they are compared to computer simulations. Based on the presented technique also the bit error probability and the probability distribution of the output log-likelihood ratios of the Max-Log-MAP algorithm are derived in analytic form.

We examine a low-rate turbo coding scheme based on superorthogonal convolutional encoders (SOCEs). The low-rate coding is suitable for code-division multiple-access (CDMA) applications. We use the property that the component encoders are equivalent to conventional convolutional encoders to analyze the asymptotic performance. We analyze the iterative decoding performance that can be achieved when both the code length and the number of iterations tend to infinity and present a bound on the iterative limit of the code construction. It is shown by asymptotic analysis, that the rate 1/7,1/15, and 1/31 codes with component encoders of memory 3,4, and 5 have iterative limits below -0.65, -0.88, and -0.95 dB, respectively. Simulations for codes with large permutors (interleavers) confirm these asymptotic results. The construction is general and can be done for codes of lower rates as well.

An asymptotical analysis and comparison of two coded modulation systems using phase-shift keying (PSK) signaling with the transmission taking place over the additive white Gaussian noise (AWGN) channel is provided. In this paper, bounds for the decoding error probability of conventional coded modulation are derived. Both block and trellis coding are considered. The state-complexity error exponent is introduced.

For pt.I see ibid., vol.47, no.7, p.2782-92 (2001). In this paper we analyze a multilevel coded modulation system using phase-shift keying (PSK) signaling and transmitting over the additive white Gaussian noise (AWGN) channel. We reduce the analysis of the overall system to the analysis of each decoding level, considering them as a set of related channels. The concept of a "genie-aided communication system" is introduced to simplify the analysis. A comparison with the conventional coded modulation system, studied in part I of this work, and some results concerning the synthesis and analysis of practical multilevel modulation schemes concludes the paper.

We introduce new upper bounds for the bit and burst error probabilities, when a convolutional code is used for transmission over a binary input, additive white Gaussian noise (AWGN) channel, and the decoder performs maximum-likelihood decoding. The bounds are tighter than existing bounds, and nontrivial also for signal-to-noise ratios below the computational cutoff rate.

Pulse-position-hopped (PPH) code division multiple access (CDMA) is a new promising multiple-access technique which is very well suited for short-range multipath communications and has several benefits, such as coherent reception and low transmit power density. We analyze the error-correcting capability of a system employing PPH-CDMA. The results show that the system capacity is proportional to the bandwidth, in a similar fashion as for carrier-based transmission techniques.

We present a class of convolutional codes defined by a low-density parity-check matrix and an iterative algorithm for decoding these codes. The performance of this decoding is close to the performance of turbo decoding. Our simulation shows that for the rate R=1/2 binary codes, the performance is substantially better than for ordinary convolutional codes with the same decoding complexity per information bit. As an example, we constructed convolutional codes with memory M=1025, 2049, and 4097 showing that we are about 1 dB from the capacity limit at a bit-error rate (BER) of 10/sup -5/ and a decoding complexity of the same magnitude as a Viterbi decoder for codes having memory M=10.

Coherent reception of quadrature phase-shift keying (QPSK) modulated signals in an uplink channel of a direct-sequence code-division multiple access (DS-CDMA) system is considered. The receivers, commonly referred as the conventional matched-filter receiver and the RAKE receiver, are analyzed when the transmission of data is performed over the additive white Gaussian noise (AWGN) channel and the multipath slow Rayleigh fading channel, respectively. Both analyses take into account inaccuracies in the carrier phase estimations resulting from a carrier phase estimator.

A family of active distance measures for general convolutional codes is defined. These distances are generalizations of the extended distances introduced by Thommesen and Justesen (1983) for unit memory convolutional codes. It is shown that the error correcting capability of a convolutional code is determined by the active distances. The ensemble of periodically time-varying convolutional codes is defined and lower bounds on the active distances are derived for this ensemble. The active distances are very useful in the analysis of concatenated convolutional encoders.

An explicit expression for the symbol error probability for a system using frequency-hopped spread-spectrum multiple-access with M-ary frequency shift keying (M-ary FSK) is given when the channel is undergoing Rayleigh fading. Using this expression, the performance of binary BCH codes, nonbinary BCH codes and RS codes are compared, and the best choices of code and modulation format are determined for different channel conditions. Depending on the required codeword error probability, different choices of code and modulation format are found to give the best result. Some attention is also paid to the sometimes used assumption of a noiseless channel, which in many cases is found to give inaccurate results.

We analyze the quadrature amplitude modulation (QAM) version of multilevel modulation with multistage decoding using a suboptimal metric, when transmission takes place over a memoryless Gaussian channel. The upper bounds for decoding error probabilities are functions of the Chernoff bounding parameter Z. We argue that the conventional approximation of Z is not adequate; new values of Z that tightens the error bounds without causing them to lose their validity are given. The capacity for this system is also calculated, and we conclude that the use of a suboptimal metric in multistage decoding causes very little degradation in capacity compared to when the optimal metric is used in each decoding stage.

Soft-input/soft-output symbol decoding plays a significant role in iterative decoding. We propose a simple optimal soft-input/soft-output symbol decoding algorithm for linear block codes which requires one forward recursion using a trellis. For many codes the decoding complexity is lower than previous methods, such as the algorithm by Bahl et al. (1974), and the decrease is shown at its most when decoding Hamming codes.

A coding-decoding strategy for the noiseless T-user q-ary multiple-access channel is presented where no cooperation between the users is needed, neither in the code construction nor in the decoding process. Statistics for the received symbols as a function of q and T are given, and the cutoff rate for the channel is defined and evaluated. Finally, computer simulations are presented to support the results found.

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>or=5. It is shown that there exist fixed convolutional codes of rate 2/4 whose free distance d/sub free/ meets the Costello bound originally derived for time varying convolutional codes.>

It is well known that the computational performance of sequential decoding deteriorates greatly when channel errors occur in clusters, as in Gilbert channels. A way of using sequential decoding to exploit the memory of a Gilbert channel that alleviates this problem is presented. A Fano-like metric matched to this channel is used. The method is investigated by simulating sequential decoding utilizing the stack algorithm. The simulations confirm the feasibility of the technique.< >

Multitype branching processes have been employed to determine the stack algorithm computational distribution for one subtree. These results are extended here to the distribution of the number of computations in any finite number of subtrees. Starting from the computational distribution forK-1subsequent subtrees, a recurrent equation for the distribution forKsubsequent subtrees is determined.

An upper bound on the first-event error probability for maximum-likelihood decoding of fixed binary convolutional codes on the binary symmetric channel is derived. The bound is evaluated for rate1/2codes, and comparisons are made with simulations and with the bounds of Viterbi, Van de Meeberg, and Post. In particular, the new bound is significantly better than Van de Meeberg's bound for rates aboveR_{\comp}.

Upper bounds are derived on the error probability that can be achieved by using the maximum-likelihood algorithm of sequential decoding for the binary symmetric channel. The bounds are functions of constraint length and backsearch limit.