Improved decoding for a concatenated coding system recommended byCCSDS

The concatenated coding system recommended by CCSDS (Consultative Committee for Space Data Systems) uses an outer (255,233) Reed-Solomon (RS) code based on 8-b symbols, followed by the block interleaver and an inner rate 1/2 convolutional code with memory 6. Viterbi decoding is assumed. Two new decoding procedures based on repeated decoding trials and exchange of information between the two decoders and the deinterleaver are proposed. In the first one, where the improvement is 0.3-0.4 dB, only the RS decoder performs repeated trials. In the second one, where the improvement is 0.5-0.6 dB, both decoders perform repeated decoding trials and decoding information is exchanged between them     

High rate concatenated coding systems using bandwidth efficienttrellis inner 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     

High rate concatenated coding systems using multidimensionalbandwidth-efficient trellis inner codes

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     

Turbo decoding of concatenated channel coding and trellis shaping for peak power controlled single-carrier systems

Trellis shaping (TS) has found its application in the peak power control of band-limited single-carrier signals. Our recent work has demonstrated that a well-designed TS can control the symbol transitions such that the output signal has almost constant envelope, which significantly alleviates the linearity requirement of power amplifiers. Compared to transmission without constellation shaping, however, the TS involves signal constellation expansion exclusively for peak power control. Therefore, unlike trellis coded modulation (TCM) that increases the minimum Euclidean distances (MED), the TS decreases the MED, thus incurring the increase in signal-to-noise power ratio (SNR) required for achieving a certain error rate. In this letter, in order to overcome this drawback, we propose a serial concatenation of coding and shaping together with an effective decoding algorithm that utilizes the memory effect (i.e., error correcting capability) of the shaped symbols. The achievable performance of the proposed system is analyzed in terms of the average mutual information. The simulation results demonstrate that the iterative decoding of the proposed concatenated system with outer convolutional codes and inner trellis shaping offers a significant performance gain.     

On bit-error probability of a concatenated coding scheme

This paper presents a method for evaluating the bit-error probability of a concatenated coding system for BPSK transmission over the AWGN channel. In the concatenated system, a linear binary block code is used as the inner code and is decoded with the soft-decision maximum likelihood decoding, and a maximum distance separable code (or its interleaved code) is used as the outer code and is decoded with a bounded distance decoding. The method is illustrated through a specific example in which the inner code is a binary (64.40.8) Reed-Muller subcode and the outer code is the NASA standard (255, 223, 33) Reed-Solomon code over GF(2⁸) interleaved to a depth of 5. This specific concatenated system is being considered for NASA's high-speed satellite communications. The bit-error performance is evaluated by a combination of simulation and analysis. The split weight enumerators for the maximum distance separable codes are derived and used for the analysis     

Signal editing: A new approach to upgrade concatenated coding communications

Based on the property that correction coding is more sensitive to the number of errors than the number of erased code symbols, results of an analytical investigation to improve the performance of concatenated coding communications are presented. We propose a new tactic, ‘signal editing’, to estimate and erase unreliable data prior to the final outer decoding process. We show that signal editing has a capability to detect and delete individual erroneous digits that has not been achieved by other methods. As a result, system performance can be markedly improved. Specific recommendations for using the procedure are suggested and discussed. We illustrate how signal editing is implemented in the case of a convolutional code with Viterbi decoding. A new concatenated (or hybrid) coding technique is constructed integrating the code with interleaving and signal editing. Performance improvement is evaluated and analysed. In this study, signal editing is derived from the information available in the Viterbi decoding process. Not limited to convolutional code with Viterbi decoding, signal editing can be applied to other linear codes without any restriction.     

A fast maximum likelihood sequence decoding method for multicarrier DS-CDMA using frequency spread coding

This paper focuses on a multicarrier direct-sequence code-division multiple-access system using frequency spread coding, which was proposed by Matsutani and Nakagawa in 1999. Although this system is attractive due to its inherent frequency diversity gain without time or frequency redundancy, it is disadvantaged by its exponential complexity in the maximum likelihood sequence decoding (MLSD). To cope with such a bottleneck, this paper proposes a fast MLSD method which consists of a searching process along the eigenvectors of a symmetric matrix and a refining process. The fast MLSD method is compared with the normal MLSD method via theoretical analysis and simulation results.     

Correction of extrinsic information for iterative decoding in a serially concatenated multiuser DS-CDMA system

The system under study is a coded asynchronous DS-CDMA system with orthogonal modulation in time-varying Rayleigh fading multipath channels. Information bits are convolutionally encoded, block interleaved, and mapped to M-ary orthogonal Walsh codes, where the last step is essentially a process of block coding. This paper aims at tackling the problem of joint iterative decoding of this serially concatenated inner block code and outer convolutional code and estimating frequency-selective fading channels in multiuser environments. The (logarithm) maximum a posteriori probability, (Log)-MAP criterion is used to derive the iterative decoding schemes. In our system, the soft output from inner block decoder is used as a priori information for the outer decoder. The soft output from outer convolutional decoder is used for two purposes. First, it may be fed back to the inner decoder as extrinsic information for the systematic bits of the Walsh codeword. Secondly, it is utilized for channel estimation and multiuser detection (MUD). We also show that the inner decoding can be accomplished without extrinsic information, and in some cases, e.g., when the system is heavily loaded, yields better performance than the decoding with unprocessed extrinsic information. This implies the need for correcting the extrinsic information obtained from outer decoder. Different schemes are examined and compared numerically, and it is shown that iterative decoding with properly corrected extrinsic information or with non-extrinsic/extrinsic adaptation enables the system to operate reliably in the presence of severe multiuser interference, especially when the inner decoding is assisted by decision directed channel estimation and interference cancellation techniques.     

Channel coding and decoding in a relay system operated with physical-layer network coding

This paper investigates link-by-link channel-coded PNC (physical layer network coding), in which a critical process at the relay is to transform the superimposed channel-coded packets received from the two end nodes (plus noise), Y₃ = X₁+ X₂+W₃, to the network-coded combination of the source packets, S₁ oplus S₂. This is in contrast to the traditional multiple-access problem, in which the goal is to obtain both S₁ and S₂ explicitly at the relay node. Trying to obtain S₁ and S₂ explicitly is an overkill if we are only interested in S1oplusS₂. In this paper, we refer to the transformation Y₃ rarr S₁ oplus S₂ as the channel-decoding- network-coding process (CNC) in that it involves both channel decoding and network coding operations. This paper shows that if we adopt the repeat accumulate (RA) channel code at the two end nodes, then there is a compatible decoder at the relay that can perform the transformation Y₃ rarr S₁oplusS₂ efficiently. Specifically, we redesign the belief propagation decoding algorithm of the RA code for traditional point-to-point channel to suit the need of the PNC multiple-access channel. Simulation results show that our new scheme outperforms the previously proposed schemes significantly in terms of BER without added complexity.     

Serial concatenated TCM with an inner accumulate code-part I: maximum-likelihood analysis

We propose a serial concatenated trellis-coded modulation system using one or more inner rate-1 accumulate codes and a mapping to a higher order, Gray-labeled signal constellation. As outer codes, we consider repeat codes, single parity-check codes, and convolutional codes. We show that under maximum-likelihood decoding, there exists a signal-to-noise ratio threshold beyond which the bit-error probability goes to zero as the blocklength goes to infinity. We then evaluate the performance for finite blocklengths using a modified union bound. Computer simulations demonstrate that the proposed system, despite its use of a simple rate-1 inner code, achieves performance in additive white Gaussian noise and Rayleigh fading that is comparable to, or better than, that of more complex systems suggested in the literature.     

Near optimum error correcting coding and decoding: turbo-codes

This paper presents a new family of convolutional codes, nicknamed turbo-codes, built from a particular concatenation of two recursive systematic codes, linked together by nonuniform interleaving. Decoding calls on iterative processing in which each component decoder takes advantage of the work of the other at the previous step, with the aid of the original concept of extrinsic information. For sufficiently large interleaving sizes, the correcting performance of turbo-codes, investigated by simulation, appears to be close to the theoretical limit predicted by Shannon     

Image coding based on a fractal theory of iterated contractiveimage transformations

The author proposes an independent and novel approach to image coding, based on a fractal theory of iterated transformations. The main characteristics of this approach are that (i) it relies on the assumption that image redundancy can be efficiently exploited through self-transformability on a block-wise basis, and (ii) it approximates an original image by a fractal image. The author refers to the approach as fractal block coding. The coding-decoding system is based on the construction, for an original image to encode, of a specific image transformation-a fractal code-which, when iterated on any initial image, produces a sequence of images that converges to a fractal approximation of the original. It is shown how to design such a system for the coding of monochrome digital images at rates in the range of 0.5-1.0 b/pixel. The fractal block coder has performance comparable to state-of-the-art vector quantizers.     

The effect of a precoder on serially concatenated coding systemswith an ISI channel

The performance of a serially concatenated system which includes a channel with memory preceded by a precoder as a rate-1 inner coder is presented. The effect of different precoders on the maximum-likelihood bit-error performance is analyzed. The precoder weight gain, which explains the good bit-error rate (BER) performance, is identified through a union bound analysis. Precoders are divided into two groups based on an analysis of the Euclidean distance and its multiplicity, and each precoder group shows a distinct BER curve behavior. It is shown that the BER curves for two precoder groups cross over each other. Convolutional codes are considered as outer codes in simulations on various intersymbol interference channels. Several important design considerations for the choice of precoders are derived based on the analysis and these are confirmed through simulations with an iterative decoding algorithm     

Serial concatenated TCM with an inner accumulate code - part II: density-evolution analysis

In a companion paper, we showed the existence of decoding thresholds for maximum-likelihood (ML) decoding of a serial concatenated trellis-coded modulation (SCTCM) system with one or more inner accumulate codes. In this paper, we compute the decoding thresholds for an iterative, non-ML decoder by density evolution (DE), assuming infinite blocklengths. We also derive a stability condition for the particular case of an outer parity-check code and a single inner accumulate code. We show that, for equiprobable signaling, the bit-wise log-likelihood ratio densities for higher order constellations are symmetric. Furthermore, when used in DE, these densities can be averaged without significantly affecting the resulting threshold values. For an outer single parity-check code, the lowest decoding thresholds are achieved with two inner accumulate codes. For an outer repeat code, a single inner accumulate code gives the lowest thresholds. At code rates r/sub c/>2/3, the decoding thresholds for the SCTCM system are within 1 dB of the constellation-constrained channel capacity for additive white Gaussian noise channels, and within 1.5 dB for independent, identically distributed Rayleigh channels. Simulation results verify the computed thresholds.     

Joint source-channel coding using combined TCQ/CPM: iterative decoding

An iterative decoding approach to joint source and channel coding (JSCC) using combined trellis-coded quantization (TCQ) and continuous phase modulation (CPM) is proposed. The channel is assumed to be the additive white Gaussian noise channel. This iterative procedure exploits the structure of the TCQ encoder and the continuous phase modulator. The performance in terms of the signal-to-distortion ratio (SDR) is compared with that of a combined TCQ/trellis-coded modulation (TCM) system. It is shown that the combined TCQ/CPM systems are both power- and bandwidth-efficient, compared with the combined TCQ/TCM system. For source encoding rate R=2 b/sample, it is observed that the combined TCQ/CPM systems with iterative decoding working at symbol level converge faster than the systems working at bit level. The novelty of this work is the use of a soft decoder and an iterative decoding algorithm for TCQ-based JSCC systems. The combined TCQ/CPM with iterative decoding is considered for the first time.     

Bounds on a probability for the heavy tailed distribution and the probability of deficient decoding in sequential decoding

Although sequential decoding of convolutional codes gives a very small decoding error probability, the overall reliability is limited by the probability P_G of deficient decoding, the term introduced by Jelinek to refer to decoding failures caused mainly by buffer overflow. The number of computational efforts in sequential decoding has the Pareto distribution and it is this "heavy tailed" distribution that characterizes P_G. The heavy tailed distribution appears in many fields and buffer overflow is a typical example of the behaviors in which the heavy tailed distribution plays an important role. In this paper, we give a new bound on a probability in the tail of the heavy tailed distribution and, using the bound, prove the long-standing conjecture on P_G, that is, P_G ap constanttimes1/(sigma^rhoN^rho-1) for a large speed factor sigma of the decoder and for a large receive buffer size N whenever the coding rate R and rho satisfy E(rho)=rhoR for 0 les rho les 1     

Condensed table of Huffman coding, a new approach to efficient decoding

This letter introduces a new technique for designing and decoding Huffman codes. The key idea is to define a condensed Huffman table (CHT) that is smaller than the ordinary Huffman table and which leads to fast decoding. For example, the new approach has been shown to reduce the memory consumption by a factor of eight, compared with the single-side grown Huffman table.     

Image sequence coding at very low bit rates: a review

This paper presents a review of promising techniques for very low bit-rate, below 64 kb/s, image sequence coding. Image sequence coding at such low rates will be a crucial technique in forthcoming visual services, e.g., visual information transmission and storage. A typical application is to transmit moving videophone scenes through the existing analog telephone lines or via a mobile channel. Two types of potential coding techniques are addressed: waveform-based image sequence coding and model-based image sequence coding.     

On the achievable rate region of sequential decoding for a class ofmultiaccess channels

The achievable-rate region of sequential decoding for the class of pairwise reversible multiaccess channels is determined. This result is obtained by finding tight lower bounds to the average list size for the same class of channels. The average list size is defined as the expected number of incorrect messages that appear, to a maximum-likelihood decoder, to be at least as likely as the correct message. The average list size bounds developed may be of independent interest, with possible applications to list-decoding schemes