We propose a new class of high-rate spatially coupled LDPC (SC-LDPC) codes based on the convolutional selforthogonal codes (CSOCs) first introduced by Massey. The SCLDPC codes are constructed by treating the irregular graph corresponding to the parity-check matrix of a systematic rate$R=(n-1) / n$CSOC as a convolutional protograph. The protograph can then be lifted using permutation matrices to generate a high-rate SC-LDPC code whose strength depends on the lifting factor. The SC-LDPC codes constructed in this fashion can be decoded using iterative belief propagation based sliding window decoding. To improve performance, a non-systematic version of a C SOC parity-check matrix is then proposed by making a slight modification to the systematic construction. Even though the parity-check matrix is in non-systematic form, we show how systematic encoding can still be performed. We also show that the non-systematic convolutional protograph has a guaranteed girth and free distance and that these properties carry over to the lifted versions. Numerical results are included demonstrating that CSOC-based SC-LDPC codes (i) have performance at least as good as that of SC-LDPC codes commonly found in the literature, and (ii) have iterative decoding thresholds comparable to those of existing SC-LDPC code designs.

In this paper, we examine variable node (VN) doping to mitigate the error propagation problem in sliding window decoding (SWD) of spatially coupled LDPC (SC-LDPC) codes from the point of view of the encoding process. More specifically, in order to simplify the process of generating an encoded sequence with some number of doped code bits, we propose to employ systematic encoding and to limit doping to systematic bits only. Numerical results show that doping of systematic bits only achieves comparable performance to employing general (nonsystematic) encoding and full doping of all the code bits at each doping position, while benefiting from a much simpler encoding process. We then show that the inherent rate loss due to doping can be reduced by doping only a fraction of the variable nodes at each doping position with only a minor impact on performance.

Generalized low-density parity-check (GLDPC) codes are a class of LDPC codes in which the standard single parity check (SPC) constraints are replaced by constraints defined by a linear block code. These stronger constraints typically result in improved error floor performance, due to better minimum distance and trapping set properties, at a cost of some increased decoding complexity. In this paper, we study spatially coupled generalized low-density parity-check (SC-GLDPC) codes and present a comprehensive analysis of these codes, including: (1) an iterative decoding threshold analysis of SC-GLDPC code ensembles demonstrating capacity approaching thresholds via the threshold saturation effect; (2) an asymptotic analysis of the minimum distance and free distance properties of SC-GLDPC code ensembles, demonstrating that the ensembles are asymptotically good; and (3) an analysis of the finite-length scaling behavior of both GLDPC block codes and SC-GLDPC codes based on a peeling decoder (PD) operating on a binary erasure channel (BEC). Results are compared to GLDPC block codes, and the advantages and disadvantages of SC-GLDPC codes are discussed.

We introduce a novel design of spatially coupled low density parity check codes in order to reduce the effects of error propagation in low-latency sliding window decoding for large frame lengths or streaming applications. Specifically, we employ reduced-degree check nodes spaced throughout the coupling chain, which have the effect of allowing the decoder to recover from error bursts. A simplified analysis of the block error rate (BLER) of the proposed codes is presented that allows us to predict the effect of different placements of reduced-degree checks in the coupling chain. Simulation results supporting the beneficial effect of the new code design on the overall BLER performance are included.

In this paper, we study the problem of error propagation in sliding window decoding (SWD) of spatially coupled LDPC (SC-LDPC) codes. A general decoder model that accounts for error propagation is proposed and analyzed, and the decoded block error rate (BLER) is calculated using the model. In order to improve the BLER performance under decoder error propagation conditions, adaptive variable node (VN) doping is proposed, assuming a noiseless binary feedback channel is available. Example calculations using the proposed model, as well as numerical simulation results, are used to show that adaptive VN doping improves the BLER performance compared to the periodic VN doping and to the undoped case.

The performance of low-density parity-check (LDPC) codes at high signal-to-noise ratios (SNRs) is known to be limited by the presence of certain sub-graphs that exist in the Tanner graph representation of the code, for example trapping sets and absorbing sets. This paper derives a lower bound on the frame error rate (FER) of any LDPC code containing a given problematic sub-graph, assuming a particular message passing decoder and decoder quantization. A crucial aspect of the lower bound is that it is code-independent, in the sense that it can be derived based only on a problematic sub-graph and then applied to any code containing it. Due to the complexity of evaluating the exact bound, assumptions are proposed to approximate it, from which we can estimate decoder performance. Simulated results obtained for both the quantized sum-product algorithm (SPA) and the quantized min-sum algorithm (MSA) are shown to be consistent with the approximate bound and the corresponding performance estimates. Different classes of LDPC codes, including both structured and randomly constructed codes, are used to demonstrate the robustness of the approach.

For decoding low-density parity-check (LDPC) codes, the attenuated min-sum algorithm (AMSA) and the offset min-sum algorithm (OMSA) can outperform the conventional min-sum algorithm (MSA) at low signal-to-noise-ratios (SNRs), i.e., in the “waterfall region” of the bit error rate curve. This paper demonstrates that, for quantized decoders, MSA actually outperforms AMSA and OMSA in the “error floor” region, and that all three algorithms suffer from a relatively high error floor. This motivates the introduction of a modified MSA that is designed to outperform MSA, AMSA, and OMSA across all SNRs. The new algorithm is based on the assumption that trapping sets are the major cause of the error floor for quantized LDPC decoders. A performance estimation tool based on trapping sets is used to verify the effectiveness of the new algorithm and also to guide parameter selection. We also show that the implementation complexity of the new algorithm is only slightly higher than that of AMSA or OMSA. Finally, the simulated performance of the new algorithm, using several classes of LDPC codes (including spatially coupled LDPC codes), is shown to outperform MSA, AMSA, and OMSA across all SNRs.

Spatially coupled (SC) low-density parity-check (LDPC) codes can achieve capacity approaching performance with low message recovery latency when using sliding window (SW) decoding. An SC-LDPC code constructed from a protograph can be generated by first coupling a chain of block protographs and then lifting the coupled protograph using permutation matrices. In this paper, we introduce a systematic design to eliminate 4-cycles in a coupled protograph. Further using a quasi-cyclic (QC) lifting, we introduce a procedure for constructing QC-SC-LDPC codes of girth at least eight. This can be interpreted as a multi-stage graph lifting process that yields a greater flexibility in designing QC-SC-LDPC codes with a large girth than previous approaches. Simulation results show the design leads to improved decoding performance, particularly in the error floor, compared to random constructions. Finally, we determine the minimum coupling width required to eliminate 4-cycles in a coupled protograph.

We investigate error propagation in sliding window decoding of braided convolutional codes (BCCs). Previous studies of BCCs have focused on iterative decoding thresholds, minimum distance properties, and their bit error rate (BER) performance at small to moderate frame length. Here, we consider a sliding window decoder in the context of large frame length or one that continuously outputs blocks in a streaming fashion. In this case, decoder error propagation, due to the feedback inherent in BCCs, can be a serious problem. To mitigate the effects of error propagation, we propose several schemes: a window extension algorithm where the decoder window size can be extended adaptively, a resynchronization mechanism where we reset the encoder to the initial state, and a retransmission strategy where erroneously decoded blocks are retransmitted. In addition, we introduce a soft BER stopping rule to reduce computational complexity, and the tradeoff between performance and complexity is examined. Simulation results show that, using the proposed window extension algorithm, resynchronization mechanism, and retransmission strategy, the BER performance of BCCs can be improved by up to four orders of magnitude in the signal-to-noise ratio operating range of interest, and the soft BER stopping rule can be employed to reduce computational complexity.

It is well known that for decoding low-density parity-check (LDPC) codes, the attenuated min-sum algorithm (AMSA) and the offset min-sum algorithm (OMSA) can outperform the conventional min-sum algorithm (MSA) at low signal-to-noise-ratios (SNRs). In this paper, we demonstrate that, for quantized LDPC decoders, although the MSA achieves better high SNR performance than the AMSA and OMSA, each of the MSA, AMSA, and OMSA all suffer from a relatively high error floor. Therefore, we propose a novel modification of the MSA for decoding quantized LDPC codes with the aim of lowering the error floor. Compared to the quantized MSA, the proposed modification is also helpful at low SNRs, where it matches the waterfall performance of the quantized AMSA and OMSA. The new algorithm is designed based on the assumption that trapping/absorbing sets (or other problematic graphical objects) are the major cause of the error floor for quantized LDPC decoders, and it aims to reduce the probability that these problematic objects lead to decoding errors.

A novel code construction based on spatially coupled low-density parity-check (SC-LDPC) codes is presented. The proposed code ensembles are comprised of several protograph-based chains characterizing individual SC-LDPC codes. We demonstrate that the code ensembles obtained by connecting appropriately chosen individual SC-LDPC code chains at specific points have improved iterative decoding thresholds. In addition, the connected chain ensembles have a smaller decoding complexity required to achieve a specific bit error probability compared to the individual code chains. Moreover, we demonstrate that, like the individual component chains, the proposed constructions have a typical minimum distance that grows linearly with block length. Finally, we show that the improved asymptotic properties of the connected chain ensembles also translate into improved finite length performance.

In this paper, we study sliding window decoding of braided convolutional codes (BCCs) in the context of a streaming application, where decoder error propagation can be a serious problem. A window extension algorithm and a resynchronization mechanism are introduced to mitigate the effect of error propagation. In addition, we introduce a soft bit-error-rate stopping rule to reduce computational complexity, and the tradeoff between performance and complexity is examined. Simulation results show that, using the proposed window extension algorithm and resynchronization mechanism, the error performance of BCCs can be improved by up to three orders of magnitude with reduced computational complexity.

Absorbing sets are known to be the primary factor in the error-floor performance of low-density parity-check (LDPC) codes with message passing decoders over the additive white Gaussian noise (AWGN) channel. Besides showing excellent waterfall performance, spatially coupled LDPC (SC-LDPC) codes that are constructed by an edge spreading technique are known to have fewer cycles and absorbing sets than their block code counterparts, and therefore to exhibit better error-floor performance. Based on our previously obtained results for quantized LDPC block decoders, we derive lower bounds on the performance of quantized SC-LDPC decoders, including both a flooding schedule decoder and a sliding window decoder. Numerical simulation results confirm the accuracy of the obtained bounds and show that, for quantized decoders, properly designed SC-LDPC codes have better error-floor performance than their underlying LDPC block codes.

It has been shown that a class of spatially coupled low-density generator-matrix (SC-LDGM) code ensembles displays distortion saturation for the lossy binary symmetric source coding problem with the belief propagation guided decimation (BPGD) algorithm, i.e., the BPGD distortion approaches the optimal expected distortion of the underlying ensemble asymptotically in code length. We investigate the distortion performance of a practical class of protograph-based SC-LDGM code ensembles and demonstrate distortion saturation numerically. Moreover, taking advantage of the convolutional structure of the SC-LDGM codes, we propose an efficient windowed encoding (WE) algorithm with two decimation techniques for lowering the WE complexity that maintain distortion performance close to the rate-distortion bound.

Spatially coupled (SC) low-density parity-check (LDPC) codes can achieve capacity approaching performance with low message recovery latency when using sliding window (SW) decoding. An SC-LDPC code constructed from a protograph can be generated by first coupling a chain of block protographs and then lifting the coupled protograph using permutation matrices. This paper introduces a systematic design of SC-LDPC codes to eliminate 4-cycles in the coupled photograph. Using a quasi-cyclic (QC) lifting, we obtain QC-SC-LDPC codes of girth at least eight. Coupling a chain of block protographs implies spreading edges from one protograph to the others. Our protograph-based design can be viewed as guiding the edge spreading and also the graph-lifting process. Simulation results show the design leads to improved decoding performance, particularly in the error floor, compared to random designs.

Spatially coupled low-density parity-check codes can be decoded using a graph-based message passing algorithm applied across the total length of the coupled graph. However, considering practical constraints on decoding latency and complexity, a sliding window decoding approach is normally preferred. In order to reduce decoding complexity compared with standard parallel decoding schedules, serial schedules can be applied within a decoding window. However, uniform serial schedules within a window do not provide the expected reduction in complexity. Hence, we propose non-uniform schedules (parallel and serial) based on measured improvements in the estimated bit error rate (BER). We show that these non-uniform schedules result in a significant reduction in complexity without any loss in performance. Furthermore, based on observations made using density evolution, we propose a non-uniform pragmatic decoding schedule (parallel and serial) that does not require any additional calculations (e.g., BER estimates) within the decoding process.

We propose a novel encoding/transmission scheme called continuous chain (CC) transmission that is able to improve the finite-length performance of a system using spatially coupled low-density parity-check (SC-LDPC) codes. In CC transmission, instead of transmitting a sequence of independent code words from a terminated SC-LDPC code chain, we connect multiple chains in a layered format, where encoding, transmission, and decoding are performed in a continuous fashion. The connections between chains are created at specific points, chosen to improve the finite-length performance of the code structure under iterative decoding. We describe the design of CC schemes for different SC-LDPC code ensembles constructed from protographs: a (J,K) -regular SC-LDPC code chain, a spatially coupled repeat-accumulate (SC-RA) code, and a spatially coupled accumulate-repeat-jagged-accumulate (SC-ARJA) code. In all cases, significant performance improvements are reported and it is shown that using CC transmission only requires a small increase in decoding complexity and decoding delay with respect to a system employing a single SC-LDPC code chain for transmission.

In this paper, we present a novel sliding window decoding scheme based on iterative Bahl-Cocke-Jelinek-Raviv decoding for braided convolutional codes, a class of turbo-like codes with short constraint length component convolutional codes. The tradeoff between performance and decoding latency is examined and, to reduce decoding complexity, both uniform and nonuniform message passing schedules within the decoding window, along with early stopping rules, are proposed. We also perform a density evolution analysis of sliding window decoding to guide the selection of the window size and message passing schedule. Periodic puncturing is employed to obtain rate-compatible code rates of 1/2 and 2/3 starting from a rate 1/3 mother code and a code rate of 3/4 starting from a rate 1/2 mother code. Simulation results show that, with nonuniform message passing and periodic puncturing, near capacity performance can be maintained throughout a wide range of rates with reasonable decoding complexity and no visible error floors.

Recently, it has been shown that a class of spatially coupled low-density generator-matrix (SC-LDGM) code ensembles displays distortion saturation for the lossy binary symmetric source coding problem with the belief propagation guided decimation (BPGD) algorithm, i.e., the BPGD distortion approaches the optimal expected distortion of the underlying ensemble asymptotically in code length. Here, we investigate the distortion performance of a practical class of protograph-based SC-LDGM code ensembles and demonstrate distortion saturation numerically. Moreover, we propose an efficient windowed encoding (WE) algorithm that takes advantage of the convolutional structure of the SC-LDGM codes. By using the WE algorithm, a distortion very close to the rate-distortion limit can be achieved for a fixed compression rate with low-to-moderate encoding latency.

A code-independent performance bound for a given absorbing set is derived for quantized low-density parity-check (LDPC) decoders. The analysis demonstrates that each absorbing set in the Tanner graph imposes a specific lower bound on the frame error rate (FER) of any code containing that absorbing set under a given quantization scheme. This approach is applicable to any message-passing (MP) decoding algorithm and any uniform or non-uniform quantization scheme for LDPC codes. Simulation results using the sum-product algorithm (SPA) provide FERs that are consistent with the obtained bounds. In addition, the bounds demonstrate that the conventional quantized SPA is not capable of achieving very low FERs if the LDPC codes contain certain absorbing sets.

In this paper, we study the block error rate (BLER) performance of spatially coupled low-density parity-check (SC-LDPC) codes using a sliding window decoder suited for streaming applications. Previous studies of SC-LDPC have focused on the bit error rate (BER) performance or the frame error rate (FER) performance over the entire length of the code. Here, we consider protograph-based constructions of SC-LDPC codes in which a window decoder continuously outputs blocks in a streaming fashion, and we examine the BLER associated with these blocks. We begin by examining the effect of protograph design on the streaming BLER by varying the block size and the coupling width in such a way that the overall constraint length of the SC-LDPC code remains constant. Next, we investigate the BLER scaling behavior with block size and coupling width. Lastly, we consider the effect of employing an outer code to protect blocks, so that small numbers of residual errors can be corrected by the outer code. Simulation results for the additive white Gaussian noise channel (AWGNC) are included and comparisons are made to LDPC block codes (LDPC-BCs).

The papers in this special issue address the topic of capacity approaching codes. This issue reflects a further shift of interest in coding theory research, this time toward polar codes, a new class of capacity achieving codes introduced in 2008. Of the 17 papers appearing in this issue, 9 are devoted to various aspects of polar codes, with 6 papers devoted to LDPC codes, including 3 on spatially coupled (convolutional) LDPC codes, and 2 on other coding topics.

In this paper, we present a random puncturing analysis of low-density parity-check (LDPC) code ensembles. We derive a simple analytic expression for the iterative belief propagation (BP) decoding threshold of a randomly punctured LDPC code ensemble on the binary erasure channel (BEC) and show that, with respect to the BP threshold, the strength and suitability of an LDPC code ensemble for random puncturing is completely determined by a single constant that depends only on the rate and the BP threshold of the mother code ensemble. We then provide an efficient way to accurately predict BP thresholds of randomly punctured LDPC code ensembles on the binary-input additive white Gaussian noise channel (BI-AWGNC), given only the BP threshold of the mother code ensemble on the BEC and the design rate, and we show how the prediction can be improved with knowledge of the BI-AWGNC threshold. We also perform an asymptotic minimum distance analysis of randomly punctured code ensembles and present simulation results that confirm the robust decoding performance promised by the asymptotic results. Protograph-based LDPC block code and spatially coupled LDPC code ensembles are used throughout as examples to demonstrate the results.

In this paper, we study spatially coupled lowdensity parity-check (SC-LDPC) codes over finite fields GF(q), q ≥ 2, and develop design rules for q-ary SC-LDPC code ensembles based on their iterative belief propagation decoding thresholds, with particular emphasis on low-latency windowed decoding (WD). We consider transmission over both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise channel (BIAWGNC) and present results for a variety of (J, K)-regular SC-LDPC code ensembles constructed over GF(q) using protographs. Thresholds are calculated using the protograph versions of q-ary density evolution (for the BEC) and the q-ary extrinsic information transfer analysis (for the BIAWGNC). We show that the WD of q-ary SC-LDPC codes provides significant threshold gains compared with corresponding (uncoupled) q-ary LDPC block code (LDPC-BC) ensembles when the window size W is large enough and that these gains increase as the finite-field size q = 2m increases. Moreover, we demonstrate that the new design rules provide WD thresholds that are close to capacity, even when both m and W are relatively small (thereby reducing decoding complexity and latency). The analysis further shows that, compared with standard flooding-schedule decoding, the WD of q-ary SC-LDPC code ensembles results in significant reductions in both the decoding complexity and the decoding latency and that these reductions increase as m increases. For the applications with a near-threshold performance requirement and a constraint on decoding latency, we show that using q-ary SC-LDPC code ensembles, with moderate q > 2, instead of their binary counterparts results in reduced decoding complexity.

In this paper, a modified extrinsic information transfer (EXIT) chart analysis that takes into account the relation between mutual information (MI) and bit-error-rate (BER) is presented to study the convergence behavior of block Markov superposition transmission (BMST) of short codes (referred to as basic codes). We show that the threshold curve of BMST codes using an iterative sliding window decoding algorithm with a fixed decoding delay achieves a lower bound in the high signal-to-noise ratio (SNR) region, while in the low SNR region, due to error propagation, the thresholds of BMST codes become slightly worse as the encoding memory increases. We also demonstrate that the threshold results are consistent with finite-length performance simulations.

In this paper, we provide an efficient way to predict iterative belief propagation (BP) decoding thresholds of randomly punctured low-density parity-check (LDPC) code ensembles on the binary-input additive white Gaussian noise channel (AWGNC), given only the BP threshold of the mother code ensemble on the binary erasure channel (BEC) and the code design rate. We show that the predictions are accurate by comparing them with values calculated by discretized density evolution for a variety of puncturing fractions. We find that the strength and suitability of an LDPC code ensemble for random puncturing over the AWGNC with respect to iterative decoding threshold is completely determined by a single constant θ, and this behavior is demonstrated using both LDPC block code and spatially coupled LDPC code ensembles. Finally, we present simulation results that confirm the excellent decoding performance promised by the asymptotic results.

In this paper, we analyze the performance of finite-length generalized LDPC (GLDPC) block codes constructed from protographs when transmission takes place over the binary erasure channel (BEC). A generalized peeling decoder is proposed and we derive a system of differential equations that gives the expected evolution of the graph degree distribution during decoding. We then show that the finite-length performance of a GLDPC code can be estimated by means of a simple scaling law, where a single scaling parameter represents the finite-length properties of the code. We also show that, as we consider stronger component codes, both the asymptotic threshold and the finite-length scaling parameter are improved.

In this paper, asymptotic methods are used to form lower and upper bounds on the typical free distance growth rate of ensembles of periodically time-varying protograph-based spatially coupled low-density parity-check (SC-LDPC) codes over GF(q). By evaluating and comparing these bounds, we find that the typical free distance of q-ary SC-LDPC codes increases linearly with constraint length and that the bounds coincide for a sufficiently large period. In particular, we show that the free distance to constraint length ratio of (3, 6)-regular q-ary SC-LDPC code ensembles exceeds the minimum distance to block length ratio of an underlying q-ary LDPC block code (LDPC-BC) ensemble. We also show that, similar to the minimum distance growth rate of the (3, 6)-regular q-ary LDPC-BC ensemble, the free distance growth rate of (3, 6)-regular q-ary SC-LDPC code ensembles increases with the field size q up to a certain point, and then it decreases as q increases further.

In this paper, we compare the finite-length performance of protograph-based spatially coupled low-density paritycheck (SC-LDPC) codes and LDPC block codes (LDPC-BCs) over GF(q). To reduce computational complexity and latency, a sliding window decoder with a stopping rule based on a soft belief propagation (BP) estimate is used for the q-ary SC-LDPC codes. Two regimes are considered: one when the constraint length of q-ary SC-LDPC codes is equal to the block length of q-ary LDPC-BCs and the other when the two decoding latencies are equal. Simulation results confirm that, in both regimes, (3,6)-, (3,9)-, and (3,12)-regular non-binary SC-LDPC codes can significantly outperform both binary and non-binary LDPC-BCs and binary SC-LDPC codes. Finally, we present a computational complexity comparison of q-ary SC-LDPC codes and q-ary LDPC-BCs under equal decoding latency and equal decoding performance assumptions.

In this paper, we construct protograph-based spatially coupled low-density parity-check (LDPC) codes by coupling together a series of L disjoint, or uncoupled, LDPC code Tanner graphs into a single coupled chain. By varying L , we obtain a flexible family of code ensembles with varying rates and frame lengths that can share the same encoding and decoding architecture for arbitrary L . We demonstrate that the resulting codes combine the best features of optimized irregular and regular codes in one design: capacity approaching iterative belief propagation (BP) decoding thresholds and linear growth of minimum distance with block length. In particular, we show that, for sufficiently large L , the BP thresholds on both the binary erasure channel and the binary-input additive white Gaussian noise channel saturate to a particular value significantly better than the BP decoding threshold and numerically indistinguishable from the optimal maximum a posteriori decoding threshold of the uncoupled LDPC code. When all variable nodes in the coupled chain have degree greater than two, asymptotically the error probability converges at least doubly exponentially with decoding iterations and we obtain sequences of asymptotically good LDPC codes with fast convergence rates and BP thresholds close to the Shannon limit. Further, the gap to capacity decreases as the density of the graph increases, opening up a new way to construct capacity achieving codes on memoryless binary-input symmetric-output channels with low-complexity BP decoding.

In this paper, we compare the finite-length performance of non-binary spatially coupled low-density parity-check (NB SC-LDPC) codes constructed from protographs to non-binary LDPC block codes (NB LDPC-BCs). A sliding window decoding architecture with a stopping rule based on a soft bit-error-rate (BER) estimate for the NB SC-LDPC codes is considered. It is demonstrated that NB SC-LDPC codes with sliding window decoding outperform NB LDPC-BCs with no increase in decoding complexity when the decoding latency of the SC-LDPC codes equals the block length of the LDPC-BCs. We also investigate the relationship between the protograph lifting factor, the decoding window size, and the decoding performance of NB SC-LDPC codes when the decoding latency is fixed. Simulation results for several (3,6)-regular NB code examples confirm that NB SC-LDPC codes can significantly outperform both binary LDPC-BCs and binary SC-LDPC codes with the same decoding latency.

Absorbing sets are combinatorially defined objects existing in the Tanner graph of a low-density parity-check (LDPC) code that have been shown to cause failures in the iterative message-passing decoder when transmission occurs over the additive white Gaussian noise channel. In this paper, we study the absorbing set properties of a class of high-rate array-based spatially coupled LDPC (SC-LDPC) codes that are constructed by coupling together L array-based LDPC block codes. We prove that the smallest absorbing sets existing in the Tanner graph of the SC-LDPC code have the same size as those in the corresponding uncoupled LDPC codes, and the number of such sets grow linearly with L. We show that spatial coupling greatly reduces the average number (per symbol) of minimal sets compared to the uncoupled codes, and we explain that this reduction is due to many absorbing sets and small cycles being `broken' by the coupling process. The large reduction in the number of minimal absorbing sets suggests that array-based SC-LDPC codes will have significantly improved decoding performance in the high signal-to-noise ratio regime compared to the corresponding uncoupled LDPC codes.

We study the iterative decoding threshold performance of non-binary spatially-coupled low-density parity-check (NB-SC-LDPC) code ensembles for both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise channel (BIAWGNC), with particular emphasis on windowed decoding (WD). We consider both (2, 4)-regular and (3, 6)-regular NB-SC-LDPC code ensembles constructed using protographs and compute their thresholds using protograph versions of NB density evolution and NB extrinsic information transfer analysis. For these code ensembles, we show that WD of NB-SC-LDPC codes, which provides a significant decrease in latency and complexity compared to decoding across the entire parity-check matrix, results in a negligible decrease in the near-capacity performance for a sufficiently large window size W on both the BEC and the BIAWGNC. Also, we show that NBSC-LDPC code ensembles exhibit gains in the WD threshold compared to the corresponding block code ensembles decoded across the entire parity-check matrix, and that the gains increase as the finite field size q increases. Moreover, from the viewpoint of decoding complexity, we see that (3, 6)-regular NB-SC-LDPC codes are particularly attractive due to the fact that they achieve near-capacity thresholds even for small q and W.

In a network application, channel coding alone is not sufficient to reliably transmit a message of finite length K from a source to one or more destinations as in, e.g., file transfer. To ensure that no data is lost, it must be combined with rateless erasure correcting schemes on a higher layer, such as a time-division multiple access (TDMA) system paired with automatic repeat request (ARQ) or random linear network coding (RLNC). We consider binary channel coding on a binary symmetric channel (BSC) and q-ary RLNC for erasure correction in a star network, where Y sources send messages to each other with the help of a central relay. In this scenario RLNC has been shown to have a throughput advantage over TDMA schemes as K→∞ and q→∞. In this paper we focus on finite block lengths and compare the expected throughputs of RLNC and TDMA. For a total message length of K bits, which can be subdivided into blocks of smaller size prior to channel coding, we obtain the channel code rate and the number of blocks that maximize the expected throughput of both RLNC and TDMA, and we find that TDMA is more throughput-efficient for small message lengths K and small q.

Quasi-cyclic low-density parity-check (QC-LDPC) codes based on protographs are of great interest to code designers because analysis and implementation are facilitated by the protograph structure and the use of circulant permutation matrices for protograph lifting. However, these restrictions impose undesirable fixed upper limits on important code parameters, such as minimum distance and girth. In this paper, we consider an approach to constructing QC-LDPC codes that uses a two-step lifting procedure based on a protograph, and, by following this method instead of the usual one-step procedure, we obtain improved minimum distance and girth properties. We also present two new design rules for constructing good QC-LDPC codes using this two-step lifting procedure, and in each case, we obtain a significant increase in minimum distance and achieve a certain guaranteed girth compared with one-step circulant-based liftings. The expected performance improvement is verified by simulation results.

Low-density parity-check convolutional (LDPCC) codes, also known as spatially coupled LDPC codes, can be decoded using a message passing algorithm. In order to limit decoding latency and complexity, windowed decoding can be applied. Updates within the window can be performed either in parallel or serially. However, simulation results show that uniform updating schedules do not provide the expected reduction in complexity when applied within the window. Hence we propose non-uniform schedules for updating the nodes based on measured improvements in the bit error rate. Nodes within the window that stop showing any improvement are excluded from the update list for the next iteration. This results in a reduction of up to 50% in complexity compared to uniform window schedules.

Channel coding alone is not sufficient to reliably transmit a message of finite length from a source to one or more destinations as in, e.g., file transfer. To ensure that no data is lost, it must be combined with rateless erasure correcting schemes on a higher layer, such as a time-division multiple access (TDMA) system paired with automatic repeat request (ARQ) or random linear network coding (RLNC). We consider binary channel coding on a binary symmetric channel (BSC) and q-ary RLNC for erasure correction in a star network, where Y sources send messages to each other with the help of a central relay. We focus on finite block lengths and compare the expected throughputs of RLNC and TDMA. For a total message length of K bits, which can be subdivided into blocks of smaller size prior to channel coding, we obtain the channel coding rate and the number of blocks that maximize the expected throughput of both RLNC and TDMA, and we find that TDMA is more throughput-efficient for small K and small q.

Families of generalized spatially-coupled low-density parity-check (GSC-LDPC) code ensembles can be formed by terminating protograph-based generalized LDPC convolutional (GLDPCC) codes. It has previously been shown that ensembles of GSC-LDPC codes constructed from a protograph have better iterative decoding thresholds than their block code counterparts, and that, for large termination lengths, their thresholds coincide with the maximum a-posteriori (MAP) decoding threshold of the underlying generalized LDPC block code ensemble. Here we show that, in addition to their excellent iterative decoding thresholds, ensembles of GSC-LDPC codes are asymptotically good and have large minimum distance growth rates.

This paper investigates the use of rate-compatible spatially-coupled codes for coded cooperation. Transmitting to the same destination, two source nodes cooperate to combat block fading; using rate-compatible spatially-coupled codes, one source node relays additional parity-check bits for its partner's latest transmission to provide cooperative diversity at the destination. Different families of spatially-coupled codes are generated by applying the edge spreading technique to several rate-compatible protograph-based block LDPC codes from the literature. Simulation of the outage behavior shows that, using spatially-coupled codes, system performance approaches the theoretical limit, regardless of whether the original underlying block LDPC codes were designed specifically for coded cooperation or not. The same result holds when windowed decoding, instead of decoding across the entire graph, is used to reduce decoding latency.

The finite length performance of codes on graphs constructed by connecting spatially coupled low-density parity-check (SC-LDPC) code chains is analyzed. Successive (peeling) decoding is considered for the binary erasure channel (BEC). The evolution of the undecoded portion of the bipartite graph remaining after each iteration is analyzed as a dynamical system. It is shown that, in addition to superior iterative decoding thresholds, connected chain ensembles have better performance than single chain ensembles of the same rate and length.

In this paper we provide necessary and sufficient conditions for constituent codes in (multiple) concatenated and graph-based coding schemes to achieve an asymptotically error-free iterative decoding fixed-point if the maximum possible a priori information is available. At least one constituent code in an iterative decoding scheme must satisfy these conditions in order to ensure an asymptotically vanishing bit error probability at the convergence point of the decoder. Our results are proved for arbitrary binary-input symmetric memoryless channels (BISMCs) and thus can be universally applied to many transmission scenarios. Specifically, using a factor graph framework, it is shown that non-inner codes in a serial concatenation or check nodes in generalized LDPC codes achieve perfect extrinsic information if and only if the minimum Hamming distance between codewords is two or greater. For inner codes in a serial concatenation, constituent codes in a parallel concatenation, or variable nodes in doubly-generalized LDPC codes the corresponding encoder condition for acquiring perfect extrinsic information is an infinite codeword weight for a weight-one input sequence. For this case we provide a general proof which holds for all linear encoders and BISMCs. We also show that these results can improve the performance of concatenated coding schemes.

A family of robust rate-compatible (RC) punctured low-density parity-check convolutional codes (LDPC-CCs) is derived from a time-invariant LDPC-CC mother code by periodically puncturing encoded bits (variable nodes) with respect to several criteria: (1) ensuring the recoverability of punctured variable nodes, (2) minimizing the number of completely punctured cycle trapping sets (CPCTSs), and (3) minimizing the number of punctured variable nodes involved in short cycles. The influence of (1) and (3) on iterative decoding performance is felt most strongly in the waterfall region of the bit-error-rate (BER) curve, while (2) has a larger effect in the error floor, or high signal-to-noise ratio (SNR), region. We show that the length of the puncturing period is an important parameter when designing high rate punctured codes and, moreover, that extending the puncturing period can improve the decoding performance and extend the range of compatible rates. As examples, we obtain families of RC LDPC-CCs from several time-invariant LDPC-CC mother codes with monomial and binomial entries in their polynomial syndrome former matrices.

Low-density parity-check (LDPC) convolutional codes have been shown to be capable of achieving capacity-approaching performance with iterative message-passing decoding. In the first part of this paper, using asymptotic methods to obtain lower bounds on the free distance to constraint length ratio, we show that several ensembles of regular and irregular LDPC convolutional codes derived from protograph-based LDPC block codes have the property that the free distance grows linearly with respect to the constraint length, i.e., the ensembles are asymptotically good. In particular, we show that the free distance to constraint length ratio of the LDPC convolutional code ensembles exceeds the minimum distance to block length ratio of the corresponding LDPC block code ensembles. A large free distance growth rate indicates that codes drawn from the ensemble should perform well at high signal-to-noise ratios under maximum-likelihood decoding. When suboptimal decoding methods are employed, there are many factors that affect the performance of a code. Recently, it has been shown that so-called trapping sets are a significant factor affecting decoding failures of LDPC codes over the additive white Gaussian noise channel with iterative message-passing decoding. In the second part of this paper, we study the trapping sets of the asymptotically good protograph-based LDPC convolutional codes considered earlier. By extending the theory presented in part one and using similar bounding techniques, we show that the size of the smallest non-empty trapping set grows linearly with the constraint length for these ensembles.

Codes constructed from connected spatially coupled low-density parity-check code (SC-LDPCC) chains are proposed and analyzed. It is demonstrated that connecting coupled chains results in improved iterative decoding performance. The constructed protograph ensembles have better iterative decoding thresholds compared to an individual SC-LDPCC chain and require less computational complexity per bit when operating in the near-threshold region. In addition, it is shown that the proposed constructions are asymptotically good in terms of minimum distance.

In this paper, we study ensembles of connected spatially coupled low-density parity-check codes (SC-LDPCCs), i.e., ensembles described by graphs in which regular SC-LDPCC chains of various lengths serve as edges. We show that, by carefully connecting individual SC-LDPCC chains, we obtain LDPC code ensembles with improved iterative decoding thresholds compared to those of a single coupled chain, in addition to reducing the decoding complexity required to achieve a specific bit error probability. Moreover, we show that, like the component SC-LDPCC chains, the proposed constructions have a typical minimum distance that grows linearly with block length.

Time-invariant low-density parity-check convolutional codes (LDPC-CCs) derived from corresponding quasi-cyclic (QC) LDPC block codes (LDPC-BCs) can be described by a polynomial syndrome former matrix (polynomial-domain transposed parity-check matrix). In this paper, an estimation of the distance spectrum of time-invariant LDPC-CCs is obtained by splitting the polynomial syndrome former matrix into submatrices representing “super codes” and then evaluating the linear dependence between codewords of the corresponding super codes. This estimation results in an upper bound on the minimum free distance of the original code and, additionally, a lower bound on the number of codewords Awwith Hamming weight w.

Window decoding schedules are very attractive for message passing decoding of spatially coupled LDPC codes. They take advantage of the inherent convolutional code structure and allow continuous transmission with low decoding latency and complexity. In this paper we show that the decoding complexity can be further reduced if suitable message passing schedules are applied within the decoding window. An improvement based schedule is presented that easily adapts to different ensemble structures, window sizes, and channel parameters. Its combination with a serial (on-demand) schedule is also considered. Results from a computer search based schedule are shown for comparison.

Quasi-cyclic (QC) low-density parity-check (LDPC) codes are of great interest to code designers because of their implementation advantages and algebraic properties that facilitate their analysis. In this paper, we present some new results on QC-LDPC codes that are constructed using a two-step lifting procedure based on a protograph, and, by implementing this method instead of the usual one-step procedure, we are able to show improved minimum distance and girth properties. We also present two design rules to construct QC-LDPC codes: one uses only circulant permutation matrices at the first (pre-lifting) stage and the other uses a selection of non-commuting permutation matrices. For both techniques, we obtain a demonstrable increase in the minimum distance compared to a one-step circulant-based lifting. The expected performance improvement is verified by simulation results.

This paper compares the performance of convolutional codes to that of LDPC block codes with identical decoding latencies. The decoding algorithms considered are the Viterbi algorithm and stack sequential decoding for convolutional codes and iterative message passing for LDPC codes. It is shown that, at very low latencies, convolutional codes with Viterbi decoding offer the best performance, whereas for high latencies LDPC codes dominate - and sequential decoding of convolutional codes offers the best performance over a range of intermediate latency values. The "crossover latencies" - i.e., the latency values at which the best code/decoding selection changes - are identified for a variety of code rates (1/2, 2/3, 3/4, and 5/6) and target bit/frame error rates. For sequential decoding, both blockwise and continuous resynchronization procedures are used to allow the decoder to recover the correct path. The results indicate that sequential decoding substantially extends (beyond what is possible with Viterbi decoding) the range of latency values over which convolutional codes prove advantageous compared to LDPC block codes.

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.

A significant amount of the analysis of protograph-based low-density parity-check (LDPC) codes has been devoted to the subclass of quasi-cyclic (QC) LDPC codes. Despite their implementation advantages and algebraic properties that make them easy to analyze, protograph-based QC-LDPC codes have undesirable fixed upper limits on important code parameters. This implies that picking a QC code from an asymptotically good or capacity approaching ensemble is suboptimal, since long QC codes will not perform close to the ensemble asymptotic limits. Indeed, these limits can only be achieved by codes that are not QC. In this paper we present an overview together with some new results on partially-QC protograph-based LDPC codes, i.e., LDPC codes whose parity-check matrix is partially composed of circulant submatrices. We perform both a minimum Hamming distance and girth analysis of these codes. Moreover, we present explicit partially-QC LDPC code constructions with parameters that exceed the restricted QC upper bounds.

Ensembles of (J,K)-regular low-density parity-check convolutional (LDPCC) codes are known to be asymptotically good, in the sense that the minimum free distance grows linearly with the constraint length. In this paper, we use a protograph-based analysis of terminated LDPCC codes to obtain an upper bound on the free distance growth rate of ensembles of periodically time-varying LDPCC codes. This bound is compared to a lower bound and evaluated numerically. It is found that, for a sufficiently large period, the bounds coincide. This approach is then extended to obtain bounds on the trapping set numbers, which define the size of the smallest, non-empty trapping sets, for these asymptotically good, periodically time-varying LDPCC 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.

Channel coding alone is not sufficient to reliably transmit a message of finite length from a source to one or more destinations. To ensure that no data is lost, channel coding on the physical layer needs to be combined with rateless erasure correcting schemes such as automatic repeat request (ARQ) or random linear network coding (RLNC) on a higher layer. In this paper we consider channel coding on a binary symmetric channel and random linear network coding for erasure correction. Given a message of length K and network coding over a finite Galois field of size q, we obtain the optimal number of blocks for network coding that minimizes the expected number of transmissions. We consider both a single link and broadcast to n destinations. As the field size of network coding gets large and the expected coding overhead in blocks becomes small, we show that, given our assumptions, the benefit of using a larger channel coded block outweighs the advantage of employing network coding over many blocks and the optimal number of number of blocks tends to one, making RLNC equivalent to simple ARQ.

Quasi-cyclic Low-Density Parity-Check (QC-LDPC) codes based on protographs are of great interest to code designers because of their implementation advantages and algebraic properties that make them easy to analyze. However, the protograph structure imposes undesirable fixed upper limits on important code parameters. In this paper, we show that the upper bound on the minimum Hamming distance of protograph-based QC codes can be improved by the careful application of a two-step lifting procedure applied to the protograph. The promised improvement is validated by constructing codes with minimum distance exceeding the upper bound for QC codes based on a particular protograph.

Low-density parity-check (LDPC) convolutional codes are capable of achieving excellent performance with low encoding and decoding complexity. In this paper, we discuss several graph-cover-based methods for deriving families of time-invariant and time-varying LDPC convolutional codes from LDPC block codes and show how earlier proposed LDPC convolutional code constructions can be presented within this framework. Some of the constructed convolutional codes significantly outperform the underlying LDPC block codes. We investigate some possible reasons for this “convolutional gain,” and we also discuss the-mostly moderate-decoder cost increase that is incurred by going from LDPC block to LDPC convolutional codes.

In this paper, we present a method of constructing new families of LDPC block code ensembles formed by terminating irregular protograph-based LDPC convolutional codes. Using the accumulate-repeat-by-4-jagged-accumulate (AR4JA) protograph as an example, a density evolution analysis for the binary erasure channel shows that this flexible design technique gives rise to a large selection of LDPC block code ensembles with varying code rates and thresholds close to capacity. Further, by means of an asymptotic weight enumerator analysis, we show that all the ensembles in this family also have minimum distance that grows linearly with block length, i.e., they are asymptotically good.

Families of asymptotically regular LDPC block code ensembles can be formed by terminating (J, K)-regular protograph-based LDPC convolutional codes. By varying the termination length, we obtain a large selection of LDPC block code ensembles with varying code rates, minimum distance that grows linearly with block length, and capacity approaching iterative decoding thresholds, despite the fact that the terminated ensembles are almost regular. In this paper, we investigate the properties of the quasi-cyclic (QC) members of such an ensemble. We show that an upper bound on the minimum Hamming distance of members of the QC sub-ensemble can be improved by careful choice of the component protographs used in the code construction. Further, we show that the upper bound on the minimum distance can be improved by using arrays of circulants in a graph cover of the protograph.

This paper presents a quantitative study of the benefits that mobile relays can provide to the wireless infrastructure namely, extension of base station coverage and enhancement of wireless connection throughput. The end user can choose to connect directly to a base station, or, as an alternative, to establish a two-hop link using a relay. Relay locations are modelled as realizations of a two-dimensional Poisson process with random motion, and as such their availability to forward messages received from a base station or from an end user is analyzed. Two important performance metrics are derived for out-of-coverage end users: the probability of establishing a route and the expected duration that a route or connection can be sustained. For an end user within the coverage area, the maximum and average throughput gains that can be achieved using mobile relays are derived. These results provide insight into the benefits mobile relays can offer in terms of improving connectivity or throughput.

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.

This paper analyzes a cooperative diversity scheme in which multiple (i.e., more than two) source nodes cooperate to deliver their packets to a common destination. To obtain spatial diversity, the source nodes form a partnership that enables each source node to transmit its own packets while relaying those of its partners. Instead of time-multiplexing the codewords for local packets and relay packets (as in conventionally done), we adopt a network coded approach wherein the local and relay packets are first channel encoded and then XORed together. The resulting scheme generalizes the design in [1], which considered only two source nodes. We are able to show that the network coded approach delivers a significant performance advantage over conventional time multiplexing even when more than two source nodes are present.

The serial concatenation of a repetition code with two or more accumulators has the advantage of a simple encoder structure. Furthermore, the resulting ensemble is asymptotically good and exhibits minimum distance growing linearly with block length. However, in practice these codes cannot be decoded by a maximum likelihood decoder, and iterative decoding schemes must be employed. For low-density parity-check codes, the notion of trapping sets has been introduced to estimate the performance of these codes under iterative message passing decoding. In this paper, we present a closed form finite length ensemble trapping set enumerator for repeat multiple accumulate codes by creating a trellis representation of trapping sets. We also obtain the asymptotic expressions when the block length tends to infinity and evaluate them numerically.

It has been suggested that ¿near-codewords¿ may be a significant factor affecting decoding failures of LDPC codes over the AWGN channel. A near-codeword is a sequence that satisfies almost all of the check equations. These near-codewords can be associated with so-called `trapping sets' that exist in the Tanner graph of a code. In this paper, we analyse the trapping sets of protograph-based LDPC convolutional codes. 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. Further, it has been shown that some ensembles of LDPC convolutional codes are asymptotically good, in the sense that the average free distance grows linearly with constraint length. Here, asymptotic methods are used to calculate a lower bound on the trapping set growth rates for two ensembles of asymptotically good protograph-based LDPC convolutional codes. This can be used to predict where the error floor will occur for these codes under iterative message-passing decoding.

This paper analyzes the error performance of a coded cooperative diversity system employing the Euclidean superposition of two BPSK-modulated signals. For an example using a convolutional code on block fading channels, the results show excellent agreement with computer simulations. The analysis makes it possible to optimize the power allocation between the local and relay signals numerically, circumventing the need for time consuming Monte Carlo simulations. Similarly, the analysis demonstrates how the power allocation can be "tuned" to compensate for unbalanced uplink channels and/or to provide unequal error protection to the data from the two cooperating nodes.

The design of double serially concatenated convolutional codes with S-type permutors, i.e., permutors that provide a nontrivial separation, is considered. Based on a newly introduced parameter, namely, the so-called symbol span, a joint design of the outer and inner permutor is presented and its impact on the minimum distance of the overall code is analyzed. It is shown that a lower bound on the minimum distance that is given by the product of the free distances of all three component codes can be guaranteed. Design tables and simulation results are presented that include comparisons with single serially concatenated convolutional codes. In addition, a comparison with double/generalized repeat accumulate codes is briefly sketched.

Message-passing iterative decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudocodewords. These failures can cause the large signal-to-noise ratio (SNR) performance of message-passing iterative decoding to be worse than that predicted by the maximum-likelihood (ML) decoding union bound.

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.

The invention of turbo coding demonstrated that interleaved concatenation of weak codes can achieve excellent performance in the waterfall region of the bit error rate curve when decoded iteratively. The performance curve of turbo codes, however, typically exhibits an error floor due to poor minimum distance. The minimum distance can be increased by introducing a stronger component code into the concatenation, but this can lead to unacceptably large decoding effort if full BCJR decoding is used. In this paper we consider reduced complexity soft input soft output decoding of convolutional codes with long constraint lengths. In particular, we consider the M*-BCJR algorithm, which uses the M-algorithm principle to preserve only the M most promising trellis states at each step of the forward recursion. We demonstrate that the forward state metrics, typically used in M-type algorithms, are insufficient to reliably identify the best M states. In contrast, very small M suffices to achieve very good decoding performance if the state selection is based on both the forward metric and an estimate of the backward metric. We present how a heuristic based on a supercode, a higher rate code containing all the codewords of the original code but having a simpler trellis representation, can serve as an efficient estimate for the backward state metrics, enabling practical decoding of turbo codes with a strong component code.

This paper considers the coverage extension that mobile relays offer to an isolated base station. The relays are modelled as realizations of a two dimensional Poisson process with random motion, and as such their availability to forward messages received from a base station or from out-of-range mobiles is open to analysis. Two important performance metrics are derived: the probability of establishing a route and the expected duration that a route or connection can be sustained via a two hop coverage extension. The results provide insights into the benefits mobile relays can offer in terms of assisting users far away from the base station.

Viterbi decoding and sequential decoding are the standard approaches to decoding convolutional codes (and linear codes with trellis representations in general). However, when reliable communication at low signal-to-noise ratios (SNR) is desired, both techniques are impractical: the Viterbi algorithm requires large amounts of memory and numbers of computations to decode powerful codes, while sequential decoding at low SNR requires exploring large portions of the code tree. In this paper we present a novel two-pass decoder which incorporates features of both these techniques but can achieve decoding complexities lower than either of them. The decoder initially performs a backward pass that resembles the add-compare-select stage of the Viterbi decoder or the backward stage of the BCJR decoder. However, it is performed not on the trellis representing the actual code used for transmission, but on a higher rate supercode (a linear code containing all codewords of the original code) with a simpler trellis representation. The supercode state metrics obtained in the backward pass are preserved and subsequently used in the forward pass. The forward pass involves the actual tree search for the most likely transmitted codeword (of the original code), and the supercode state metrics serve as heuristics, speeding up the search process. We demonstrate that such a decoder, with a proper choice of parameters, can be made equivalent to a sequential decoder with the Fano metric, a sequential decoder with an ML metric, or a Viterbi decoder (run backwards). However, the decoder operates most effectively in between these modes, when the computational load is distributed evenly between the backward and forward stages.

This paper presents a low-complexity interleaver design that facilitates the high throughput turbo decoding required for next generation wireless systems. Specifically, it addresses the interleaver design issues that arise when several Log-MAP processors are used in parallel to improve turbo decoding throughput. In such a parallel decoder, memory access contentions occur when more than one extrinsic value is to be written to or read from the same memory block at the same time. These contentions may be avoided by designing contention- free (CF) interleavers that incorporate hardware constraints into the interleaver description. The paper first derives bounds on the number of CF interleavers, demonstrating that the fraction of interleavers of a given size that are contention-free is quite small. In spite of this, a class of contention-free "inter-window shuffle" (IWS) interleavers are shown via simulation to achieve near-WCDMA performance. Further, the paper shows that the memory requirement of CF IWS interleavers is small compared to an alternate contention-resolving method that uses a modified memory addressing scheme. Finally, we note that the advantages of contention-free interleavers have led to the adoption of a CF quadratic permutation polynomial (QPP) interleaver in the 3 GPP long term evolution (LTE) standard.

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 we study the iterative decoding behavior of time-invariant and time-varying LDPC convolutional codes derived by unwrapping QC LDPC block codes. In particular, for a time-varying LDPC convolutional code, we show that the minimum pseudo-weight of the convolutional code is at least as large as the minimum pseudo-weight of the underlying QC code. We also prove that the unwrapped convolutional codes have fewer short cycles than the QC codes. These results taken together lead to improved BER performance in the low-to-moderate SNR region, where the decoding behavior is influenced by the complete pseudo-codeword spectra and by the Tanner graph cycle histogram, with the time-varying convolutional codes outperforming both the underlying QC block codes and their time-invariant convolutional counterparts.

Convolutional codes are an efficient means of achieving reliable communication with low latency and complexity constraints. Since optimal Viterbi decoding of long (say, above 8) constraint length codes can be prohibitively complex, sequential decoders, such as the Zigangirov-Jelinek (ZJ) stack algorithm or the Fano algorithm can be applied. However, the performance of sequential algorithms is limited by a steep increase in the average number of steps per information bit that takes place close to the cutoff rate, more than by the error correcting capabilities of the code itself. In this paper we examine the problem of improving the performance of sequential decoders by designing more sophisticated path metrics. In particular, we propose a look-ahead (LA) path metric, which equals the Fano metric of the best path stemming from the current path for a fixed number of time steps. We demonstrate that in the limit of a large number of look-ahead time steps, sequential decoding becomes equivalent to the backtracking step of the Viterbi algorithm. Direct computation of the LA metric requires searching an exponential number of partial paths at each state and is infeasible, since the extra cost of computing the metric outweighs the savings in the number of time steps. However, in some scenarios of interest, the LA metric can be computed by other means. In the particular case of a covolutional code transmitted over a binary symmetric channel (BSC), this metric can be obtained from a modified syndrome decoder that stores for each partial syndrome the weight of the minimum weight error event. We demonstrate through simulations that this structure leads to an efficient and computationally inexpensive sequential decoding algorithm.

This paper presents a technique for achieving cooperative spatial diversity using serially concatenated low density generator matrix (LDGM) codes. Specifically, we consider a scenario in which a pair of transceivers employ algebraic superposition of error control codes to effect spatial diversity at their common destination. The construction of LDGM codes from a sparse generator matrix makes them a natural fit for such a cooperative diversity scheme. The simple decoder structure for graph based codes reduces the complexity at the destination compared with previously-proposed schemes using algebraic superposition of convolutional codes and turbo-like decoding. The result is a system with low encoding and decoding complexity and improved error performance.

Starting from Shannon's celebrated 1948 channel coding theorem, we trace the evolution of channel coding from Hamming codes to capacity-approaching codes. We focus on the contributions that have led to the most significant improvements in performance versus complexity for practical applications, particularly on the additive white Gaussian noise channel. We discuss algebraic block codes, and why they did not prove to be the way to get to the Shannon limit. We trace the antecedents of today's capacity-approaching codes: convolutional codes, concatenated codes, and other probabilistic coding schemes. Finally, we sketch some of the practical applications of these 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.

This paper proposes a network coding approach to cooperative diversity featuring the algebraic superposition of channel codes over a finite field. The scenario under consideration is one in which two ldquopartnersrdquo - node A and node B - cooperate in transmitting information to a single destination; each partner transmits both locally generated information and relayed information that originated at the other partner. A key observation is that node B already knows node A's relayed information (because it originated at node B) and can exploit that knowledge when decoding node A's local information. This leads to an encoding scheme in which each partner transmits the algebraic superposition of its local and relayed information, and the superimposed codeword is interpreted differently at the two receivers i.e., at the other partner and at the destination node, based on their different a priori knowledge. Decoding at the destination is then carried out by iterating between the codewords from the two partners. It is shown via simulation that the proposed scheme provides substantial coding gain over other cooperative diversity techniques, including those based on time multiplexing and signal (Euclidean space) superposition.

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.

Multiple turbo codes (MTC's) have been shown to be capable of achieving better performance than conventional turbo codes. Most previous research on MTC's, however, has been focused on low rate schemes. In this paper, we present a systematic approach to designing high rate MTC's. Several MTC's with low complexity constituent encoders are considered as examples. First, a simple method is presented to jointly design multiple dithered relative prime interleavers. Then, based on the extrinsic information transfer characteristics of the constituent encoders, good periodic puncturing patterns are obtained using a sequential search algorithm. We compare the resulting high rate MTC's with those obtained using an alternative optimized random puncturing pattern. Simulation results show that the new codes designs, for rates up to 3/4, exhibit good performance in the waterfall region of the frame error rate (FER) curve, without any sign of an error floor down to FER's as low as 10-5

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

In this paper we address the extrinsic information transfer functions of inner decoders for a serially concatenated coding scheme. For the case of an AWGN channel, we give a universal proof for the fact that only inner encoders yielding an infinite output weight for a weight-one input sequence, such as recursive convolutional encoders, lead to perfect extrinsic information at the output of the corresponding SISO decoder. As an example we consider bit-interleaved coded modulation with iterative demapping (BICM-ID) and insert an additional recursive precoder prior to the mapping operation. Simulation results show that the proposed system does not suffer from an error floor and thus significantly outperforms BICM-ID systems that solely use mappings as inner encodings, even when they are optimized

When designing communication systems based on serially concatenated codes and iterative decoding, it is common practice to use recursive convolutional codes as inner codes. In this paper we show that very good performance can also be obtained by using simple block codes as inner codes. In particular, we propose a simple extension of a single parity check encoder that produces large Hamming weight output sequences for weight one input sequences. We also present a soft decoding algorithm and use a uniform interleaver analysis and EXIT charts to design efficient schemes that perform well in both the waterfall and error floor regions of the bit error rate curve

Iterative message-passing decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudo-codewords. These failures can cause the large signal-to-noise ratio performance of message-passing decoding to be worse than that predicted by the maximum-likelihood decoding union bound. In this paper we study the pseudo-codeword problem for the class of LDPC convolutional codes decoded continuously using an iterative, sliding window, message-passing decoder. In particular, for an LDPC convolutional code derived by unwrapping a quasi-cyclic LDPC block code, we show that the free pseudo-weight of the convolutional code is at least as large as the minimum pseudo-weight of the underlying quasi-cyclic code. This result parallels the well-known relationship between the free Hamming distance of convolutional codes and the minimum Hamming distance of their quasi-cyclic counterparts. Finally, simulation results are included that show improved performance for unwrapped LDPC convolutional codes compared to their underlying quasi-cyclic codes

This paper proposes a new approach to cooperative diversity based on the algebraic superposition of channel codes over a finite field. The scenario under consideration is one in which two "partners" - Node A and Node B cooperate in transmitting information to a single destination; each partner transmits both locally-generated information and relayed information that originated at the other partner. A key observation is that Node B already knows Node A's relayed information (previously sent from Node B) and can exploit that knowledge when decoding Node A's local information. This leads to an encoding scheme in which each partner transmits the algebraic superposition of its local and relayed information, and the superimposed codeword is interpreted differently at the two receivers - i.e., at the other partner and at the destination node - based on their different a priori knowledge. It is shown via simulation that the proposed scheme provides substantial coding gain over other cooperative diversity techniques, including those based on time sharing and signal (Euclidean space) superposition

An iterative estimation and decoding technique for memoryless additive white Gaussian noise (AWGN) channels with several abrupt changes in noise variance during transmission of a codeword is introduced. A technique developed for source coding of piecewise-stationary memoryless sources is adapted to estimate the unknown channel transition points. Then, maximum-likelihood (ML) estimation is used to estimate the unknown noise variance in each segment This process is carried out on an estimated noise sequence of the currently hypothesized codeword. Simulations using turbo codes show performance almost as good as that of a receiver with perfect knowledge of the channel

In this paper the impact of S-type permutors, i.e., permutors that provide a non-trivial separation, on the minimum distance of double serially concatenated convolutional codes is considered. A joint design of the outer and inner permutor is presented on the basis of a newly introduced permutor parameter - the so-called symbol span. This design guarantees that the minimum distance of the overall code is lower bounded by the product of the free distances of all three component codes. Simulation results are presented and comparisons with single serially concatenated and double/generalized repeat accumulate codes are briefly sketched.

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

The goal of this paper is to establish which practical routing schemes for wireless networks are most suitable for power-limited and bandwidth-limited communication regimes. We regard channel state information (CSI) at the receiver and point-to-point capacity-achieving codes for the additive white Gaussian noise (AWGN) channel as practical features, interference cancellation (IC) as possible, but less practical, and synchronous cooperation (CSI at the transmitters) as impractical. We consider a communication network with a single source node, a single destination node, and N-1 intermediate nodes placed equidistantly on a line between them. We analyze the minimum total transmit power needed to achieve a desired end-to-end rate for several schemes and demonstrate that multihop communication with spatial reuse performs very well in the power-limited regime, even without IC. However, within a class of schemes not performing IC, single-hop transmission (directly from source to destination) is more suitable for the bandwidth-limited regime, especially when higher spectral efficiencies are required. At such higher spectral efficiencies, the gap between single-hop and multihop can be closed by employing IC, and we present a scheme based upon backward decoding that can remove all interference from the multihop system with an arbitrarily small rate loss. This new scheme is also used to demonstrate that rates of O(logN) are achievable over linear wireless networks even without synchronous cooperation.

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

In this paper we propose a new soft-input soft-output equalization algorithm, offering very good performance/complexity tradeoffs. It follows the structure of the BCJR algorithm, but dynamically constructs a simplified trellis during the forward recursion. In each trellis section, only the M states with the strongest forward metric are preserved, similar to the M-BCJR algorithm. Unlike the M-BCJR, however, the remaining states are not deleted, but rather merged into the surviving states. The new algorithm compares favorably with the reduced-state BCJR algorithm, offering better performance and more flexibility, particularly for systems with higher order modulations

This paper proposes iterative estimation and decoding techniques for memoryless channels with a bounded number of abrupt changes in channel statistics. Specifically, the channel under consideration is a binary symmetric channel with a crossover probability that changes a bounded number of times during the transmission of a codeword; the channel state information to be estimated consists of the crossover probabilities of the different segments and the location(s) of the transition point(s). To estimate the transition points, a technique developed for source coding of piecewise-stationary memoryless sources is adapted; then the expectation-maximization algorithm is used to estimate the crossover probabilities. This segmentation/estimation is carried out on the error sequence of the currently hypothesized frame. Simulation results using turbo codes indicate that the proposed receiver performs almost as well as a receiver that has perfect knowledge of the channel.

In this paper, we introduce the concept of nonsystematic turbo codes and compare them with classical systematic turbo codes. Nonsystematic turbo codes can achieve lower error floors than systematic turbo codes because of their superior effective free distance properties. Moreover, they can achieve comparable performance in the waterfall region if the nonsystematic constituent encoder has a low-weight feedforward inverse. A uniform interleaver analysis is used to show that rate R=1/3 turbo codes using nonsystematic constituent encoders have larger effective free distances than when systematic constituent encoders are used. Also, mutual information-based transfer characteristics and extrinsic information transfer charts are used to show that rate R=1/3 turbo codes with nonsystematic constituent encoders having low-weight feedforward inverses achieve convergence thresholds comparable to those achieved with systematic constituent encoders. Catastrophic encoders, which do not possess a feedforward inverse, are shown to be capable of achieving low convergence thresholds by doping the code with a small fraction of systematic bits. Finally, we give tables of good nonsystematic turbo codes and present simulation results comparing the performance of systematic and nonsystematic turbo 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.

An efficient method for calculating some of the first coefficients of the distance spectrum of turbo codes is presented. It is based on the evaluation of cycles in the permutation matrix that are of a special type. For S-type permutors, the calculated coefficients in the distance spectrum include the minimum distance and other low weight terms. Therefore, by applying the union bound, this method is capable of giving a very tight approximation to the error floor behavior of the corresponding turbo code - even for large permutor sizes.

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.

Interleavers that avoid memory contentions in parallelized log-MAP decoding are analyzed and designed. Bounds are derived demonstrating that the fraction of interleavers that are contention-free is small. Nevertheless, contention-free "inter-window shuffle" interleavers with a simple implementation and reasonable memory requirements are shown to surpass 3GPP performance.

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

In this paper, we address the design of high rate turbo codes using high rate nonsystematic constituent encoders and compare their distance and iterative decoding convergence properties with systematic turbo coding schemes.

We consider a wireless communication system with a single source node, a single destination node, and multiple relay nodes placed equidistantly between them. We limit our analysis to the case of coded TDMA multihop transmission, i.e., the nodes do not cooperate and do not try to access the channel simultaneously. Given a global constraint on bandwidth, we determine the number of hops that achieves a desired end-to-end rate with the least total transmission power. Furthermore, we examine how the optimum number of hops changes when an end-to-end delay constraint is introduced using the sphere-packing bound and computer simulations. The analysis demonstrates that the optimum number of hops depends on the end-to-end rate and the path-loss exponent. Specifically, we show the existence of an asymptotic per-link spectral efficiency, which is the preferred spectral efficiency in TDMA multihop transmission.

A lower bound is derived on the achievable redundancy for universal lossless coding of parametric sources with piecewise stationary, abruptly changing, occasionally repeating statistics. In particular, it is shown that if the number of repeating statistical parameter vectors (or states) is not too large, for any uniquely decipherable code, for almost every set of states that govern all the different segments in the data sequence, for almost every arrangement of these states in the different segments, and for almost every vector of transition times, the minimum achievable redundancy is composed of 0.5 log d extra code bits for each unknown component of each state, log m extra code bits for each unknown transition time, and log s extra code bits for each repetition of a state, where d is the average duration of each state in the input string, TO is the average length of a segment, and s is the total number of states. If s is essentially large compared to TO, it is shown that the minimum redundancy is composed of 0.5 log 77i bits for each unknown component in each segment and log TO bits for each unknown transition time, which is the same lower bound as that of general piecewise stationary sources (PSSs). These results are true also in the minimax and maximin senses. The lower bound is shown to be achievable through construction of mixture and estimation based codes. Different special cases are reviewed, and it is shown that unless s is essentially large compared to m, optimal codes that are designed particularly for sources with repeating statistics outperform codes designed for PSSs when coding sources with repeating statistics. In particular, the bound for general PSSs is shown to be a special case of the new bound.

A class of algebraically structured quasi-cyclic (QC) low-density parity-check (LDPC) codes and their convolutional counterparts is presented. The QC codes are described by sparse parity-check matrices comprised of blocks of circulant matrices. The sparse parity-check representation allows for practical graph-based iterative message-passing decoding. Based on the algebraic structure, bounds on the girth and minimum distance of the codes are found, and several possible encoding techniques are described. The performance of the QC LDPC block codes compares favorably with that of randomly constructed LDPC codes for short to moderate block lengths. The performance of the LDPC convolutional codes is superior to that of the QC codes on which they are based; this performance is the limiting performance obtained by increasing the circulant size of the base QC code. Finally, a continuous decoding procedure for the LDPC convolutional codes is described.

We present an analog rotating ring decoder for decoding an LDPC convolutional code. The decoder architecture uses a window of soft received L-values, K time units in the past and K time units in the future, to decode a given bit. The window of 2K+1 time units is arranged in a ring structure, and decoding proceeds in a continuous fashion by rotating around the ring. Simulation results indicate performance almost identical to that achieved with digital decoding.

Low density parity check (LDPC) block codes have been shown to achieve near capacity performance for binary transmission over noisy channels. Block codes, however, require splitting the data to be transmitted into frames, which can be a disadvantage in some applications. Convolutional codes, on the other hand, have no such requirement, and are well suited for continuous transmission. Felstrom and Zigangirov (1999) proposed the construction of periodic time-varying convolutional codes with LDPC matrices. A set of time-invariant LDPC convolutional codes was described by Sridharan et al. (2002). The codes of Felstrom and Zigangirov were obtained by random construction techniques whereas those of Sridharan et al. were essentially algebraic constructions. The new LDPC convolutional codes described here are obtained by introducing a degree of randomness into the latter construction.

Universal lossless compression of parametric piecewise stationary sources with slow changes in the statistics between stationary segments that take place in unknown time intervals is investigated. The minimum description length (MDL) principle is derived for two different settings of this problem under the assumption that the parameter changes are linear over the change interval. In the first setting, it is assumed that all changes are of equal known in advance duration d, and in the second setting all statistics changes are of unknown durations. While in both cases the redundancy for most sources for each unknown statistical parameter in each segment remains lower bounded, as in the case of abruptly changing statistics, by 0.5 log m extra code bits, where m is the mean segment length, the minimum extra code-length required for each unknown transition interval decreases to log m-0.5 log d in the first setting, but surprisingly remains log m, as in the case of abruptly changing statistics, in the second. Schemes that achieve the lower bounds in both settings are demonstrated.

We discuss the design of new low-complexity turbo-like codes based on a multiple parallel concatenation of 4-state and 2-state constituent codes. The new code designs take advantage of the big-numerator/little-denominator principle along with specially designed interleavers to outperform previously designed turbo codes over the entire range of signal-to-noise ratios. Puncturing at the encoder is used to produce low-complexity codes with excellent performance at code rates of 1/2 and 1/3. The multiple parallel concatenation and puncturing results in turbo-like encoders which are either partially systematic or completely nonsystematic. Comparisons with the proposed 8-state turbo coding standard and with other low-complexity alternative code designs are included.

Turbo codes with long frame lengths are usually constructed using a randomly chosen interleaver. Statistically, this guarantees excellent bit-error rate (BER) performance but also generates a certain number of low weight codewords, resulting in the appearance of an error floor in the BER curve. Several methods, including using an outer code, have been proposed to improve the error floor region of the BER curve. We study the effect of an outer BCH code on the frame-error rate (FER) of turbo codes. We show that additional coding gain is possible not only in the error floor region but also in the waterfall region. Also, the outer code improves the iterative APP decoder by providing a stopping criterion and alleviating convergence problems. With this method, we obtain codes whose performance is within 0.6 dB of the sphere packing bound at an FER of 10/sup -6/.

In this paper, bandwidth efficient Type-I and Type-II hybrid-ARQ (HARQ) schemes using turbo trellis coded modulation (TTCM) are proposed. These schemes combine the power efficiency of turbo codes with the bandwidth efficiency of trellis coded modulation (TCM) to create an effective hybrid FEC/ARQ system. Several packet combining schemes are presented for use in conjunction with iterative turbo decoding over wireless time-varying Rayleigh fading channels. The packet combining schemes provide improved throughput and reliability compared to a standard Type I hybrid ARQ system without combining with only a small increase in transmitter and receiver complexity. Simulation results show that, for high throughput values, HARQ schemes based on TTCM give substantial improvement over conventional TCM schemes with the same throughput over wireless channels.

This paper studies an application of turbo codes to compressed image/video transmission and presents an approach to improving error control performance through joint channel and source decoding (JCSD). The proposed approach to JCSD includes error-free source information feedback, error-detected source information feedback, and the use of channel soft values (CSV) for source signal postprocessing. These feedback schemes are based on a modification of the extrinsic information passed between the constituent maximum a posteriori probability (MAP) decoders in a turbo decoder. The modification is made according to the source information obtained from the source signal processor. The CSVs are considered as reliability information on the hard decisions and are further used for error recovery in the reconstructed signals. Applications of this joint decoding technique to different visual source coding schemes, such as spatial vector quantization, JPEG coding, and MPEG coding, are examined. Experimental results show that up to 0.6 dB of channel SNR reduction can be achieved by the joint decoder without increasing computational cost for various channel coding rates.

This book provides a comprehensive coverage of almost all the major research results in convolutional coding since their introduction by Elias 45 years ago. The authors are well respected senior researchers who have spent almost their entire career in this field. The book was developed over a period of more than ten years and has been thoroughly tested in the doctoral program at Lund University, Sweden. The result of this painstaking effort is a first-class graduate textbook and research resource that sets very high standards for depth and breadth of coverge, attention to detail, and clarity. As a graduate textbook, it is ideal for an advanced, doctoral level course on convolutional coding. It would best be preceded by a course in the basics of block coding theory, but the brief coverage of block codes included in Chapter 1 would be sufficient for highly motivated students. The book is too long to be covered in one semester, because much of the material is heavy in detail and not easy to comprehend. Despite my obvious like and appreciation for this book, there are, in my opinion, a few shortcomings. Most unfortunate, perhaps, is the lack of any coverage of so-called turbo codes. I also was somewhat disappointed in the relatively brief coverage given to trellis-coded modulation. These practically important codes deserve more attention than they received here. Finally, I would have liked to see the authors develop the concept of punctured convolutional codes, also very important in practice, to the same depth that they covered, say, tail biting codes. All in all, though, these shortcomings should not detract from what is on the whole an excellent book.

The lower bound on the redundancy for lossless universal coding of regular memoryless sources with a bounded number of abrupt changes in the statistics is shown to be asymptotically achievable using a fixed per-letter computational complexity sequential compression scheme with fixed storage complexity. The scheme which outperforms any other known fixed-complexity scheme when regularity conditions hold is presented, and its redundancy is upper-bounded. Although the upper bounds are merely asymptotic, simulation results show that even for relatively short sequences, the redundancy obtained by asymptotically optimal schemes of higher complexity can still be achieved with fixed per-letter complexity. Furthermore, in practice, a fixed-complexity scheme based on the proposed scheme can in most cases achieve optimal redundancy even when the regularity conditions do not hold.

It is well known that an interleaver with random properties, quite often generated by pseudo-random algorithms, is one of the essential building blocks of turbo codes. However, randomly generated interleavers have two major drawbacks: lack of an adequate analysis that guarantees their performance and lack of a compact representation that leads to a simple implementation. We present several new classes of deterministic interleavers of length N, with construction complexity O(N), that permute a sequence of bits with nearly the same statistical distribution as a random interleaver and perform as well as or better than the average of a set of random interleavers. The new classes of deterministic interleavers have a very simple representation based on quadratic congruences and hence have a structure that allows the possibility of analysis as well as a straightforward implementation. Using the new interleavers, a turbo code of length 16384 that is only 0.7 dB away from capacy at a bit-error rate (BER) of 10/sup -5/ is constructed. We also generalize the theory of previously known deterministic interleavers that are based on block interleavers, and we apply this theory to the construction of a nonrandom turbo code of length 16384 with a very regular structure whose performance is only 1.1 dB away from capacity at a BER of 10/sup -5/.

This paper presents a lossy image compression scheme that employs a generalized rank-ordered prediction filter for pyramidal image coding. The proposed prediction method renders significantly reduced variance of the quantizer input. Consequently, the quality of the decompressed image is much enhanced due to the greatly reduced quantization distortion. Both analytical and simulation results show that the proposed scheme yields high-quality performance.

The multilevel coding approach of Imai and Hirakawa (1977) is used to construct trellis-matched codes for binary-input partial-response channels. For the codes to be trellis matched, the signal constellations are selected according to certain constraints, but no conditions are imposed on the component codes. New codes for the (1-D)(1+D)/sup n/ channel compare favorably to existing codes.

In this correspondence, the low-weight terms of the weight distribution of the block code obtained by terminating a convolutional code after x information blocks are expressed as a function of x. It is shown that this function is linear in x for codes with noncatastrophic encoders, but quadratic in x for codes with catastrophic encoders. These results are useful to explain the poor performance of convolutional codes with a catastrophic encoder at low-to-medium signal-to-noise ratios.

The joint channel-source decoding scheme for using turbo codes to protect compressed image data proposed by Peng, Huang, Costello and Stevenson (see, Proc. 1998 IEEE International Symposium on Circuits and Systems, Monterey, California, 1998) is modified for subband coded images. Two different modifications are presented and compared. The factors affecting the performance of the schemes are studied. Both modified schemes show superiority over a separate decoding system.

This paper is intended to investigate the bit rate allocation between source coding and channel coding rates when turbo codes are used to protect vector quantized images. The experimental results show that an appropriate bit rate allocation can lead to significant gains in the quality of the reconstructed images compared to an arbitrary bit rate allocation scheme.

An overview of the many practical applications of channel coding theory in the past 50 years is presented. The following application areas are included: deep space communication, satellite communication, data transmission, data storage, mobile communication, file transfer, and digital audio/video transmission. Examples, both historical and current, are given that typify the different approaches used in each application area. Although no attempt is made to be comprehensive in the coverage, the examples chosen clearly illustrate the richness, variety, and importance of error-control coding methods in modern digital applications.

Compressed images transmitted over noisy channels are extremely sensitive to bit errors. This necessitates the application of error control channel coding to the compressed representation before transmission. This paper presents an image transmission system which takes advantage of the superior performance of turbo codes, an important new class of parallel concatenated codes. Several aspects of the application of turbo codes to image transmission are studied, including comparison to a previous image transmission system using convolutional codes. Experimental results for several channel signal-to-noise ratios show that, in the same SNR range, turbo codes achieve much better performance with less decoding complexity than convolutional codes and that similar performance can be achieved at much lower channel SNRs. Studies also show that the use of feedback from an outer Reed-Solomon code to aid turbo decoding results in further improvement.

This paper presents a lossy image compression scheme which employs a pyramidal coding technique with segmentation based on the local activity levels. A novel prediction method is introduced, rendering significantly reduced variance of the quantizer input. Consequently, the coding efficiency is much enhanced due to the greatly reduced quantization distortion. Both theoretical analysis and simulation results show that the proposed scheme yields high quality performance. A reconstruction PSNR of 30.5 dB is achieved at a bit rate of 0.181 bpp for a 512×512 image "Lenna" before entropy coding.

A probabilistic algorithm is used to construct large constraint length trellis codes at high spectral efficiencies for use with sequential decoding. Linear trellis codes for two- and four-dimensional constellations with constraint lengths up to 19 are obtained. These codes can achieve 180/spl deg/ rotational invariance. To achieve full 90/spl deg/ rotational invariance, nonlinear trellis codes for four-dimensional constellations with constraint lengths up to 19 are obtained. In both cases it is shown that the channel cutoff rate bound can be achieved using constraint lengths between 16 and 19 with sequential decoding at a bit-error rate of 10/sup -5/-10/sup -6/ and that 4.9-5.8 dB real coding gains can be achieved over uncoded systems with the same spectral efficiency.

The relationship between the distance properties of trellis codes and the computational effort and error performance of sequential decoding is studied and optimum distance profile (ODP) and optimum free distance (OFD) trellis codes are constructed for 8-PSK and 16 QAM modulation. A comparison of the performance of both the ODP and the OFD trellis codes reveals that neither class of codes results in the best trade-off between error performance and computational effort when sequential decoding is used. A new algorithm is then proposed to construct robustly good trellis codes for use with sequential decoding. New trellis codes with asymptotic coding gains up to 6.66 dB are obtained using this algorithm, and the new codes achieve nearly the same free distances as the OFD codes and nearly the same distance profiles as the ODP 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.

The performance of turbo codes is addressed by examining the code's distance spectrum. The "error floor" that occurs at moderate signal-to-noise ratios is shown to be a consequence of the relatively low free distance of the code. It is also shown that the "error floor" can be lowered by increasing the size of the interleaver without changing the free distance of the code. Alternatively, the free distance of the code may be increased by using primitive feedback polynomials. The excellent performance of turbo codes at low signal-to-noise ratios is explained in terms of the distance spectrum. The interleaver in the turbo encoder is shown to reduce the number of low-weight codewords through a process called "spectral thinning." This thinned distance spectrum results in the free distance asymptote being the dominant performance parameter for low and moderate signal-to-noise ratios.

Two new classes of rotationally invariant trellis codes are constructed. A simple method is used to check the rotational invariance of a given code in the process of searching for optimum trellis codes. A class of linear trellis codes with constraint lengths 2-9 using four-dimensional constellations is presented. Simulation results show that a 180/spl deg/ rotationally invariant, constraint length 8, linear trellis code achieves about 0.4-dB real coding gain compared to the best constraint length 6 code, while the trellis complexity is only four times that of the constraint length 6 code. On the other hand, the constraint length 6 code that has been adopted for use in the V.34 28.8-kbit/s modem standard has the same 0.4-dB real coding gain compared to a constraint length 4 code which has also been adopted for the standard, but it requires sixteen times the trellis complexity. A class of fully rotationally invariant nonlinear trellis codes with constraint lengths 6-11 is also presented. Simulation results show that a 90/spl deg/ rotationally invariant, constraint length 8, nonlinear trellis code performs almost as well as the best linear code.

The sensitivity of the compressed image representation to bit errors requires application of a channel code before transmission over noisy channels. To prevent the uncontrolled degradation caused by a channel error, an error controlling channel code is applied to the compressed representation before transmission. Many image communication systems have constraints on bandwidth, power and time which prohibit transmission of uncompressed raw image data. Compressed image formats, however, are extremely sensitive to bit errors which can seriously degrade the quality of the image at the receiver. A new list-based iterative trellis decoder is proposed which accepts feedback from a post-processor which can detect channel errors in the reconstructed image. Experimental results are shown which indicate the new decoder provides significant improvement over the standard Viterbi decoder.

This paper presents an image communication system with improved decoding of compressed image information. A convolutional code protects the compressed image information from channel noise while a Reed-Solomon outer code gives additional protection to the critical image header information. A post-processor detects uncorrected channel errors in the reconstructed image and feeds error location information to a list-based iterative trellis decoder. This list-based decoder provides significant improvement in image quality. Experimental results are given for varying channel SNR and for varying bit rate.

Probabilistic algorithms are given for constructing good large constraint length trellis codes for use with sequential decoding that can achieve the channel cutoff rate bound at a bit error rate (BER) of 10/sup -5/-10/sup -6/. The algorithms are motivated by the random coding principle that an arbitrary selection of code symbols will produce a good code with high probability. One algorithm begins by choosing a relatively small set of codes randomly. The error performance of each of these codes is evaluated using sequential decoding and the code with the best performance among the chosen set is retained. Another algorithm treats the code construction as a combinatorial optimization problem and uses simulated annealing to direct the code search. Trellis codes for 8 PSK and 16 QAM constellations with constraint lengths v up to 20 are obtained. Simulation results with sequential decoding show that these codes reach the channel cutoff rate bound at a BER of 10/sup -5/-10/sup -6/ and achieve 5.0-6.35 dB real coding gains over uncoded systems with the same spectral efficiency and up to 2.0 dB real coding gains over 64 state trellis codes using Viterbi decoding.>

A Markovian technique is described to calculate the exact performance of the Viterbi algorithm used as either a channel decoder or a source encoder for a convolutional code. The probability of information bit error and the expected Hamming distortion are computed for codes of various rates and constraint lengths. The concept of tie-breaking rules is introduced and its influence on decoder performance is examined. Computer simulation is used to verify the accuracy of the results. Finally, we discuss the issue of when a coded system outperforms an uncoded system in light of the new results.>

Sequential decoding of the channel code in a trellis-coded modulation system with trellis shaping can be used to reduce the system complexity and to achieve high coding gain with large constraint-length codes. It is shown that almost all the shaping gain that can be achieved when Viterbi decoding is used for the channel code can also be achieved when sequential decoding is used for the channel code. It is also shown that the real shaping gain is a function of both the SNR and the spectral efficiency.

Systematic feedforward trellis codes for 8-PSK and 16-QAM modulation are constructed using a nested step by step algorithm which guarantees a good distance profile. This makes the codes suitable for use with sequential decoding, where a rapidly growing distance profile is needed to reduce the average number of computations. In addition to having a good distance profile, the new codes achieve asymptotic coding gains of up to 6.53 dB. A procedure based upon the Fano (1963) algorithm (FA) is used to calculate the free distance of the new codes. This procedure is very effective for finding the free distances of long trellis codes because of the computational and storage efficiency of the FA. From a comparison of the new systematic feedforward codes with Ungerboeck's (1982, 1987) systematic feedback codes, the authors conjecture that a systematic feedforward code of constraint length 2/spl nu/ can achieve the same free distance as a systematic feedback code of constraint length /spl nu/.>

A general parity-check equation is presented that defines rotationally invariant trellis codes of rate k/(k+1) for two-dimensional signal sets. This parity-check equation is used to find rate k/(k+1) codes for 4PSK, 8PSK, 16PSK, and QAM signal sets by systematic code searches. The MPSK codes exhibit smaller free Euclidean distances than nonrotationally invariant linear codes with the same number of states. However, since the nonlinear codes have a smaller number of nearest neighbors, their performance at moderate signal to noise ratios is close to that of the best linear codes. The rotationally invariant QAM codes with 8, 32, 64, and 256 states achieve the same free Euclidean distance as the best linear codes. Transparency of user information under phase rotations is accomplished either by conventional differential encoding and decoding, or by integrating this function directly into the code trellis.>

An erasure-free sequential decoding algorithm for trellis codes, called the buffer looking algorithm (BLA), is introduced. Several versions of the algorithm can be obtained by choosing certain parameters and selecting a resynchronization scheme. These can be categorized as block decoding or continuous decoding, depending on the resynchronization scheme. Block decoding is guaranteed to resynchronize at the beginning of each block, but suffers some rate loss when the block length is relatively short. The performance of a typical block decoding scheme is analyzed, and we show that significant coding gains over Viterbi decoding can be achieved with much less computational effort. A resynchronization scheme is proposed for continuous sequential decoding. It is shown by analysis and simulation that continuous sequential decoding using this scheme has a high probability of resynchronizing successfully. This new resynchronization scheme solves the rate loss problem resulting from block decoding. The channel cutoff rate, demodulator quantization, and the tail's influence on performance are also discussed. Although this paper considers only the decoding of trellis codes, the algorithm can also be applied to the decoding of convolutional codes.>

Trellis coding using multidimensional quadrature amplitude modulation (QAM) signal sets is investigated. Finite-size 2D signal sets are presented that have minimum average energy, are 90 degrees rotationally symmetric, and have from 16 to 1024 points. The best trellis codes using the finite 16-QAM signal set with two, four, six, and eight dimensions are found by computer search (the multidimensional (multi-D) signal set is constructed from the 2-D signal set). The best moderate complexity trellis codes for infinite lattices with two, four six, and eight dimensions are also found. The minimum free squared Euclidean distance and number of nearest neighbors for these codes were used as the selection criteria. Many of the multi-D codes are fully rotationally invariant and give asymptotic coding gains up to 6.0 dB. From the infinite lattice codes, the best codes for transmitting J, J+1/4, J+1/3, J+1/2, J+2/3, and J+3/4 b/sym (J an integer) are presented.>

Set partitioning is applied to multidimensional signal spaces over GF(q), i.e., GF/sup n1/(q) (n1or=d are presented. These codes use Reed-Solomon codes as component codes. Longer multilevel block codes are also constructed using q-ary block codes with block length longer than q+1 as component codes. Some quaternary multilevel block codes are presented with the same length and number of information symbols as, but larger distance than, the best previously known quaternary one-level block codes. It is proved that if all the component block codes are linear. the multilevel block code is also linear. Low-rate q-ary convolutional codes, word-error-correcting convolutional codes, and binary-to-q-ary convolutional codes can also be used to construct multilevel trellis codes over GF(q) or binary-to-q-ary trellis codes.>

A 2L-dimensional multiple phase-shift keyed (L*MPSK) signal set is obtained by forming the Cartesian product of L two-dimensional MPSK signal sets. A systematic approach to partitioning L*MPSK signal sets that is based on block coding is used. An encoder system approach is developed. It incorporates the design of a differential precoder, a systematic convolutional encoder, and a signal set mapper. Trellis-coded L*4PSK, L*8PSK, and L*16PSK modulation schemes are found for 1>

A class of quasiregular codesis defined for which the distance spectrum can be calculated from the codeword corresponding to the all-zero information sequence. Convolutional codes and regular codes are both quasiregular, as well as most of the best known trellis codes. An algorithm to compute the distance spectrum of linear, regular, and quasiregular trellis codes is presented. In particular, it can calculate the weight spectrum of convolutional (linear trellis) codes and the distance spectrum of most of the best known trellis codes. The codes do not have to be linear or regular, and the signals do not have to be used with equal probabilities. The algorithm is derived from a bidirectional stack algorithm, although it could also be based on the Viterbi algorithm. The algorithm is used to calculate the beginning of the distance spectrum of some of the best known trellis codes and to compute tight estimates on the first-event-error probability and on the bit-error probability.>

The authors apply a general method of bounding the event error probability of TCM (trellis-coded modulation) schemes to fading channels and use the effective length and the minimum-squared-product distance to replace the minimum-free-squared-Euclidean distance as code design parameters for Rayleigh and Rician fading channels with a substantial multipath component. They present 8-PSK (phase-shift-keying) trellis codes specifically constructed for fading channels that outperform equivalent codes designed for the AWGN (additive white Gaussian noise) channel when v>or=5. For quasiregular trellis codes there exists an efficient algorithm for evaluating event error probability, and numerical results which demonstrate the importance of the effective length as a code design parameter for fading channels with or without side information have been obtained. This is consistent with the case for binary signaling, where the Hamming distance remains the best code design parameter for fading channels. The authors show that the use of Reed-Solomon block codes with expanded signal sets becomes interesting only for large value of E/sub s//N/sub 0/, where they begin to outperform trellis codes.>

High-rate concatenated coding systems with bandwidth-efficient trellis inner codes and Reed-Solomon (RS) outer codes are investigated for application in high-speed satellite communication systems. Two concatenated coding schemes are proposed. In one the inner code is decoded with soft-decision Viterbi decoding, and the outer RS code performs error-correction-only decoding (decoding without side information). In the other the inner code is decoded with a modified Viterbi algorithm, which produces reliability information along with the decoded output. In this algorithm, path metrics are used to estimate the entire information sequence, whereas branch metrics are used to provide reliability information on the decoded sequence. This information is used to erase unreliable bits in the decoded output. An errors-and-erasures RS decoder is then used for the outer code. The two schemes have been proposed for high-speed data communication on NASA satellite channels. The rates considered are at least double those used in current NASA systems, and the results indicate that high system reliability can still be achieved.>

A concatenated coding system using two-dimensional trellis-coded MPSK inner codes and Reed-Solomon outer codes for application in high-speed satellite communication systems was proposed previously by the authors (ibid., vol.37, no.5, p.420-7, May 1989). The authors extend their results to systems using symbol-oriented, multidimensional, trellis-coded MPSK inner codes. The concatenated coding systems are divided into two classes according to their achievable effective information rates. The first class uses multidimensional trellis-coded 8-PSK inner codes and achieves effective information rates around 1 b/dimension (spectral efficiency 2 b/s/Hz). The second class employs multidimensional trellis-coded 16-PSK inner codes and provides effective information rates around 1.5 b/dimension (spectral efficiency 3 b/s/Hz). Both classes provide significant coding gains over an uncoded reference system with the same effective information rate as the coded system. The results show that the symbol-oriented nature of multidimensional inner codes can provide an improvement of up to 1 dB in the overall performance of a concatenated coding system when these codes replace bit-oriented two-dimensional codes.>

A parity retransmission hybrid automatic repeat request (ARQ) scheme is proposed which uses rate 1/2 convolutional codes and Viterbi decoding. A protocol is described which is capable of achieving higher throughputs than previously proposed parity retransmission schemes. The performance analysis is based on a two-state Markov model of a nonstationary channel. This model constitutes a first approximation to a nonstationary channel. The two-state channel model is used to analyze the throughput and undetected error probability of the protocol presented when the receiver has both an infinite and a finite buffer size. It is shown that the throughput improves as the channel becomes more bursty.>

A model is developed for a concatenated coding system, and from it the overall channel cutoff rate and capacity is found using random coding arguments. The effects of interleaving between the inner and outer codes and of the availability of side information to the outer decoder are considered. The performance of several specific concatenated coding systems is calculated and used for comparison with the random coding result. From the analysis, a number of general conclusions regarding the design of concatenated coding systems are presented. All the results are derived assuming a block inner code.>

A lower bound on the minimum free Euclidean distance of trellis-coded modulation (TCM) is derived that guarantees the existence of good TCM codes of any complexity. The bound is used to compare trellis codes combined with phase-shift keying, pulse amplitude modulation, and quadratic amplitude-shift keying modulation. This random coding bound is the first lower bound on the free distance of trellis codes, is tighter than any upper bound for large constraint lengths, and predicts the asymptotic performance of TCM when the complexity of the code becomes large. The bound can be used with any code rate and any modulation scheme and shows that the free distance increases linearly with the constraint length for large values of the constraint length.>

A problem in designing semiconductor memories is to provide some measure of error control without requiring excessive coding overhead or decoding time. In LSI and VLSI technology, memories are often organized on a multiple bit (or byte) per chip basis. For example, some 256K bit DRAM's are organized in 32K × 8 bit-bytes. Byte-oriented codes such as Reed-Solomon (RS) codes can provide efficient low overhead error control for such memories. However, the standard iterative algorithm for decoding RS codes is too slow for these applications. In this correspondence we present a special decoding technique for double-byte-error-correcting (DBEC), triple-byte-error-detecting (TBED) RS codes which is capable of high-speed operation. This technique is designed to find the error locations and the error values directly from the syndrome without having to use the iterative algorithm to find the error locator polynomial.

The performance of a concatenated coding scheme for error control in ARQ systems is analyzed for both randomerror and burst-error channels. In particular, the probability of undetected error and the system throughput are calculated. In this scheme, the inner code is used for both error correction and error detection, and the outer code is used for error detection only. Interleaving/deinterleaving of the outer code is assumed. A retransmission is requested if either the inner code or the outer code detects the Presence of errors. Various coding examples are considered. The results show that concatenated coding can provide extremely high system reliability (i.e., low probability of undetected error) and high system throughput.

An important problem in land mobile radio communications is how to provide reliable data communications to the largest number of users. To explore this problem, several existing ARQ protocols are examined which have application to the land mobile radio channel, as well as some new protocol combinations. All protocols are analyzed for several key system performance measures which are verified by experimental means for static as well as fading channels. Finally, a conclusion is reached regarding a new Protocol combination which is found to offer significant advantages over all other protocols explored.

An important feature of ARQ sequential decoding is that a very low undetected error probability can be achieved without increasing significantly the complexity of decoding. Several ARQ sequential decoding algorithms based on the stack algorithm are considered. Analysis is done for a memoryless channel with noiseless feedback, and the emphasis is on evaluating the undetected error probability and the maximum throughput attainable with each algorithm. A time-out algorithm is analyzed and the parameters optimizing the performance of this algorithm are found. A new algorithm called the slope control algorithm, capable of achieving a better throughput than the time-out algorithm, is proposed. The algorithm is analyzed using random coding arguments, and the parameters maximizing the throughput for various conditions are found. All theoretical results are verified by computer simulation for a binary symmetric channel.

ARQ methods of error control can considerably improve the reliablity of data transmission in such areas as satellite communications, computer networks, etc. A number of ARQ schemes using both block and convolutional codes have appeared in the literature. In this paper, the following problem is addressed. Given two different implementations of an ARQ scheme, one using a block code and the other using a convolutional code, such that the bit error probability of both implementations does not exceed some specific value, which implementation has the higher throughput and under what conditions will it be attained? The comparison is made for three basic retransmission schemes using both hybrid and pure ARQ: stop-and-wait, go-back-N, and selective repeat. Numerical estimates of the throughput were obtained using approximate theoretical expressions for BCH codes and simulation results for sequential decoding of rate 1/2 convolutional codes. Parameters optimizing the performance of both block and convolutional codes for different channel conditions and round trip delays were found and were used to obtain these numerical estimates. Comparison of the quantitative results indicates a trend toward preferring convolutional codes as delay and/or block length increases. A binary symmetric channel with noiseless feedback was assumed. Possible implications for the Gaussian channel are also discussed.

This paper examines three new digital modulation binary codes developed by Hedeman and denoted as the H-1, H-2, and H-3 codes. It contains a complete description of the Hedeman codes and analyzes several of their important properties. The bit error probability is displayed as a function of signal-to-noise ratio, and detector implementation is discussed. It is shown that with a maximum likelihood sequence estimator using soft decisions, the H-2 and H-3 codes can achieve the same bit error rate as the nonreturn-to-zero (NRZ) or Manchester codes. Autocorrelation functions and power spectral densities of the Hedeman codes are presented. These results indicate that they possess the favorable quality of no dc component. Finally, symbol synchronization is considered. Here, phase synchronizing template patterns are identified and the probability of resynchronization is given as a function of time after loss of synchronization.

The minimum distance growth rate of unmerged codewords in a convolutional code is shown to depend upon the minimum average weight per branchw_{0}in the encoder state diagram. An upper bound onw_{0}is obtained for a large class of rate1/2codes which includes many of the best known classes of rate1/2codes. The hound is shown to be tight for short constraint length codes. A class of codes is defined to be asymptotically catastrophic ifw_{0}approaches zero for large constraint lengths. Several classes of rate1/2codes are shown to be asymptotically catastrophic. These include classes containing codes known to have large free distance. It is argued that the free distance alone is not a sufficient criterion to determine a codes performance with either Viterbi or sequential decoding. A code with a low distance growth rate will yield a high bit error probability and will not perform well with truncated Viterbi decoding.

Two-user tree codes are considered for use on an arbitrary two-user discrete memoryless multiple-access channel (MAC). A two-user tree Is employed to achieve true maximum likelihood (ML) decoding of two-user tree codes on MAC's. Each decoding error event has associated with it a configuration indicating the specific time slots in which a decoding error has occurred for the first user alone, for the second user alone, or for both users simultaneously. Even though there are many possible configurations, it is shown that there are five fundamental configuration types. An upper bound on decoding error probability, similar to Liao's result for two-user block codes, is derived for sets of error events having a particular configuration. The total ML decoding error probability is bounded using a union bound first over all configurations of a given type and then over the five configuration types. A two-user tree coding error exponent is defined and compared with the corresponding block coding result for a specific MAC. It is seen that the tree coding error exponent is larger than the block coding error exponent at all rate pairs within the two-user capacity region. Finally, a new lower bound on free distance for two-user codes is derived using the same general technique used to bound the error probability.

A new condition for a generalized minimum distance decoder to guarantee correct decoding is developed. Based on this condition, decoding algorithms for block codes, product codes, and completely orthogonalizable codes onQary output channels are presented. The results of computer simulations comparing the performance of these decoding algorithms with several other soft-decision decoding algorithma are also presented.

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.

Using the Euclidean Algorithm for polynomials over GF(q), an algebraic technique for the generation of q-ary shift register sequences of arbitrary length l, 1 ≤ l ≤ qm, is obtained, where q is a power of a prime number, q = pn, and m is the number of shift register stages.

A new analysis of the computational effort and the error probability of sequential decoding is presented, which is based entirely on the distance properties of a particular convolutional code and employs no random-coding arguments. An upper bound on the computational distributionP(C_{t}>N_{t})for a specific time-invariant code is derived, which decreases exponentially with the column distance of the code. It is proved that rapid column-distance growth minimizes the decoding effort and therefore also the probability of decoding failure or erasure. In an analogous way, the undetected error probability of sequential decoding with a particular fixed code is proved to decrease exponentially with the free distance and to increase linearly with the number of minimum free-weight codewords. This analysis proves that code construction for sequential decoding should maximize column-distance growth and free distance in order to guarantee fast decoding, a minimum erasure probability, and a low undetected error probability.

A new algorithm for erasurefree sequential decoding of convolutional codes is introduced which achieves low error probabilities at substantially higher decoding speeds than the Viterbi decoding algorithm. The algorithmic properties of the Multiple Stack Algorithm (MSA) are investigated and it is demonstrated that the MSA reaches a decision with an exponentially rather than Pareto distributed computational effort. The MSA's error probability on the binary symmetric channel is studied as a function of its parameters and its performance and complexity compared to that of the Viterbi algorithm. The MSA is seen to achieve equal and lower error probabilities with a significantly lower average decoding effort. The new algorithm can thus be considered an attractive alternative to the Viterbi algorithm where low error probabilities and high decoding speeds are required simultaneously.

An upper bound on the bit error probability due to truncation of the path length in Viterbi decoding is obtained for any given convolutional code. This bound is then used to determine the path length at which the additional error probability due to truncation becomes negligible compared to the maximum likelihood decoding error probability. These results are tested by simulation using several short constraint length codes.

The relationship between the column distance function and the computational effort of sequential decoding is studied and the results of computer simulations are reported. A table ofR = 1/2codes having good free distance and optimum average column distance function (CDF) is presented.

The best asymptotic bounds presently known on free distance for convolutional codes are presented from a unified point of view. Upper and lower bounds for both time-varying and fixed codes are obtained. A comparison is made between bounds for nonsystematic and systematic codes which shows that more free distance is available with nonsystematic codes. This result is important when selecting codes for use with sequential or maximum-likelihood (Viterbi) decoding since the probability of decoding error is closely related to the free distance of the code. An ancillary result, used in proving the lower bound on free distance for time-varying nonsystematic codes, furnishes a generalization of two earlier bounds on the definite decoding minimum distance of convolutional codes.

For any nonzero elementcof a general finite fieldGF(q), it is shown that the polynomials(x - c)^i, i = 0,1,2,\cdots, have the "weight-retaining" property that any linear combination of these polynomials with coefficients inGF(q)has Hamming weight at least as great as that of the minimum degree polynomial included. This fundamental property is then used as the key to a variety of code constructions including 1) a simplified derivation of the binary Reed-Muller codes and, for any primepgreater than 2, a new extensive class ofp-ary "Reed-Muller codes," 2) a new class of "repeated-root" cyclic codes that are subcodes of the binary Reed-Muller codes and can be very simply instrumented, 3) a new class of constacyclic codes that are subcodes of thep-ary "Reed-Muller codes," 4) two new classes of binary convolutional codes with large "free distance" derived from known binary cyclic codes, 5) two new classes of long constraint length binary convolutional codes derived from2^r-ary Reed-Solomon codes, and 6) a new class ofq-ary "repeated-root" constacyclic codes with an algebraic decoding algorithm.

A new lower bound on definite decoding minimum distance for the class of systematic binary periodic convolutional codes is presented. The bound is everywhere stronger than Wagner's bound and has the same form as the bound obtained by Massey for the class of systematic binary fixed convolutional codes. The bound is also shown to apply to a specific subclass of simply implemented periodic codes for which Wagner's bound also holds.

A simple algorithm is presented for finding rate 1/n random-error-correcting convolutional codes. Good codes considerably longer than any now known are obtained. A discussion of a new distance measure for convolutional codes, called the free distance, is included. Free distance is particularly useful when considering decoding schemes, such as sequential decoding, which are not restricted to a fixed constraint length. It is shown how the above algorithm can be modified slightly to produce codes with known free distance. A comparison of probability of error with sequential decoding is made among the best known constructive codes of constraint length 36.