Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “trellis”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1998

Trellises and Trellis-Based Decoding Algorithms for Linear Block Codes: An Iterative Decoding Algorithm for Linear Block Codes Based on a Low-Weight Trellis Search - Part 3

For long linear block codes, maximum likelihood decoding based on full code trellises would be very hard to implement if not impossible. In this case, we may wish to trade error performance for the reduction in decoding complexity. Sub-optimum soft-decision decoding of a linear block code based on a low-weight sub-trellis can be devised to provide an effective trade-off between error performance and decoding complexity. This chapter presents such a suboptimal decoding algorithm for linear block codes. This decoding algorithm is iterative in nature and based on an optimality test. It has the following important features: (1) a simple method to generate a sequence of candidate code-words, one at a time, for test; (2) a sufficient condition for testing a candidate code-word for optimality; and (3) a low-weight sub-trellis search for finding the most likely (ML) code-word.

Lin, Shu↗
NASA NTRS1998

Trellises and Trellis-Based Decoding Algorithms for Linear Block Codes

A code trellis is a graphical representation of a code, block or convolutional, in which every path represents a codeword (or a code sequence for a convolutional code). This representation makes it possible to implement Maximum Likelihood Decoding (MLD) of a code with reduced decoding complexity. The most well known trellis-based MLD algorithm is the Viterbi algorithm. The trellis representation was first introduced and used for convolutional codes [23]. This representation, together with the Viterbi decoding algorithm, has resulted in a wide range of applications of convolutional codes for error control in digital communications over the last two decades. There are two major reasons for this inactive period of research in this area. First, most coding theorists at that time believed that block codes did not have simple trellis structure like convolutional codes and maximum likelihood decoding of linear block codes using the Viterbi algorithm was practically impossible, except for very short block codes. Second, since almost all of the linear block codes are constructed algebraically or based on finite geometries, it was the belief of many coding theorists that algebraic decoding was the only way to decode these codes. These two reasons seriously hindered the development of efficient soft-decision decoding methods for linear block codes and their applications to error control in digital communications. This led to a general belief that block codes are inferior to convolutional codes and hence, that they were not useful. Chapter 2 gives a brief review of linear block codes. The goal is to provide the essential background material for the development of trellis structure and trellis-based decoding algorithms for linear block codes in the later chapters. Chapters 3 through 6 present the fundamental concepts, finite-state machine model, state space formulation, basic structural properties, state labeling, construction procedures, complexity, minimality, and sectionalization of trellises. Chapter 7 discusses trellis decomposition and subtrellises for low-weight codewords. Chapter 8 first presents well known methods for constructing long powerful codes from short component codes or component codes of smaller dimensions, and then provides methods for constructing their trellises which include Shannon and Cartesian product techniques. Chapter 9 deals with convolutional codes, puncturing, zero-tail termination and tail-biting.Chapters 10 through 13 present various trellis-based decoding algorithms, old and new. Chapter 10 first discusses the application of the well known Viterbi decoding algorithm to linear block codes, optimum sectionalization of a code trellis to minimize computation complexity, and design issues for IC (integrated circuit) implementation of a Viterbi decoder. Then it presents a new decoding algorithm for convolutional codes, named Differential Trellis Decoding (DTD) algorithm. Chapter 12 presents a suboptimum reliability-based iterative decoding algorithm with a low-weight trellis search for the most likely codeword. This decoding algorithm provides a good trade-off between error performance and decoding complexity. All the decoding algorithms presented in Chapters 10 through 12 are devised to minimize word error probability. Chapter 13 presents decoding algorithms that minimize bit error probability and provide the corresponding soft (reliability) information at the output of the decoder. Decoding algorithms presented are the MAP (maximum a posteriori probability) decoding algorithm and the Soft-Output Viterbi Algorithm (SOVA) algorithm. Finally, the minimization of bit error probability in trellis-based MLD is discussed.

Lin, Shu↗
NASA NTRS1995

The trellis complexity of convolutional codes

It has long been known that convolutional codes have a natural, regular trellis structure that facilitates the implementation of Viterbi's algorithm. It has gradually become apparent that linear block codes also have a natural, though not in general a regular, 'minimal' trellis structure, which allows them to be decoded with a Viterbi-like algorithm. In both cases, the complexity of the Viterbi decoding algorithm can be accurately estimated by the number of trellis edges per encoded bit. It would, therefore, appear that we are in a good position to make a fair comparison of the Viterbi decoding complexity of block and convolutional codes. Unfortunately, however, this comparison is somewhat muddled by the fact that some convolutional codes, the punctured convolutional codes, are known to have trellis representations that are significantly less complex than the conventional trellis. In other words, the conventional trellis representation for a convolutional code may not be the minimal trellis representation. Thus, ironically, at present we seem to know more about the minimal trellis representation for block than for convolutional codes. In this article, we provide a remedy, by developing a theory of minimal trellises for convolutional codes. (A similar theory has recently been given by Sidorenko and Zyablov). This allows us to make a direct performance-complexity comparison for block and convolutional codes. A by-product of our work is an algorithm for choosing, from among all generator matrices for a given convolutional code, what we call a trellis-minimal generator matrix, from which the minimal trellis for the code can be directly constructed. Another by-product is that, in the new theory, punctured convolutional codes no longer appear as a special class, but simply as high-rate convolutional codes whose trellis complexity is unexpectedly small.

Mceliece, R. J.↗
NASA NTRS1986

Multiple Trellis Coded Modulation (MTCM): An MSAT-X report

Conventional trellis coding outputs one channel symbol per trellis branch. The notion of multiple trellis coding is introduced wherein more than one channel symbol per trellis branch is transmitted. It is shown that the combination of multiple trellis coding with M-ary modulation yields a performance gain with symmetric signal set comparable to that previously achieved only with signal constellation asymmetry. The advantage of multiple trellis coding over the conventional trellis coded asymmetric modulation technique is that the potential for code catastrophe associated with the latter has been eliminated with no additional cost in complexity (as measured by the number of states in the trellis diagram).

Divsalar, D.↗
NASA NTRS1986

Multiple trellis coded modulation (MTCM)

A new trellis coded modulation technique, referred to as multiple trellis coded modulation wherein more than one channel symbol per trellis branch is transmitted and demonstrated. Simple two state trellis codes for symmetric MPSK and AM modulations, which can achieve 3 dB gain over uncoded modulation at very high signal-to-noise ratios without bandwidth expansion and without reduction in information bit rate have been found. The gain of the new trellis codes with respect to previously reported two state trellis codes is between 1 to 2 dB at very high signal-to-noise ratios, depending on the number of bits per hertz transmitted. These gains are achieved with no additional cost in complexity; while indeed additional computations per branch are needed for the multiple trellis coding scheme. This concept can be extended to higher number of states and other type of modulations; i.e., quadrature amplitude modulation.

Divsalar, D.↗
NASA NTRS1991

Trellis coded multilevel DPSK system with doppler correction for mobile satellite channels

A trellis coded multilevel differential phase shift keyed mobile communication system. The system of the present invention includes a trellis encoder for translating input signals into trellis codes; a differential encoder for differentially encoding the trellis coded signals; a transmitter for transmitting the differentially encoded trellis coded signals; a receiver for receiving the transmitted signals; a differential demodulator for demodulating the received differentially encoded trellis coded signals; and a trellis decoder for decoding the differentially demodulated signals.

Divsalar, Dariush↗
NASA NTRS1985

A new description of combined trellis coding with asymmetric modulation

The combination of rate k/(k+t) trellis codes with digital modulations described by an asymmetric 2 sup k+1-point signal constellation has been recently shown to yield performance improvement over the traditional symmetric constellation combined with the same trellis code. The approach taken is to specify an underlying trellis code and then map the output code symbols into the fixed signal constellation based on a rule called mapping by set partitioning. The latter process is tantamount to assigning signals from the constellation to the trellis code transitions so as to maximize the free Euclidean distance of the code. Recently, a new description of trellis codes has been given that combines the above two steps into one. The ideas introduced are further explored, placing particular emphasis on the optimization of the signal constellation asymmetry. It can be concluded that the trellis-coded amplitude modulation (AM) designs given are very close to being optimum.

Simon, M. K.↗
NASA NTRS1987

The design of trellis codes for fading channels

The appropriate criterion for optimum trellis coded modulation design on the additive white Gaussian noise channel is maximization of the free Euclidean distance. When trellis coded modulation is used on a Rician fading channel with interleaving/deinterleaving, the design of the code for optimum performance is guided by other factors, in particular the length of the shortest error event path, and the product of branch distances (possibly normalized by the Euclidean distance of the path) along that path. Although maximum free distance (d sub free) is still an important consideration, it plays a less significant role the more severe the fading is on the channel. These considerations lead to the definition of a new distance measure for optimization of trellis codes transmitted over Rician fading channels. If no interleaving/deinterleaving is used, then once again the design of the trellis code is guided by maximizing d sub free. It is also shown that allowing for multiple symbols per trellis branch, i.e., multiple trellis coded modulation (MTCM), provides an additional degree of freedom for designing a code to meet the above optimization criteria on the fading channel. It is here where the MTCM technique exploits its full potential.

Divsalar, Dariush↗
NASA NTRS1985

Combined trellis coding with asymmetric modulations

The use of asymmetric signal constellations combined with optimized trellis coding to improve the performance of coded systems without increasing the average or peak power, or changing the bandwidth constraints of a system is discussed. The trellis code, asymmetric signal set, and Viterbi decoder of the system model are examined. The procedures for assigning signals to state transitions of the trellis code are described; the performance of the trellis coding system is evaluated. Examples of AM, QAM, and MPSK modulations with short memory trellis codes are presented.

Divsalar, D.↗
NASA NTRS1987

Multiple trellis coded modulation (MTCM) performance on a fading mobile satellite channel

The author recently introduced the notion of multiple trellis coding, in which more than one channel symbol per trellis branch is transmitted. He showed that on the ideal additive white Gaussian noise (AWGN) channel, the combination of multiple trellis coding with M-ary modulation yields a performance gain with symmetric signal sets comparable to and in some cases better than that previously achieved only with signal constellation asymmetry. The combination of conventional trellis coding with multiple phase-shift-keyed (MPSK) signaling has recently been shown by the author to be a well-suited modulation/coding scheme for transmission over the fading mobile satellite channel. In particular, a rate 2/3 coded 8-PSK scheme operating at 4800 b/s is currently under development for use in NASA's Mobile Satellite Experiment (MSAT-X). The author applies the multiple trellis-coded modulation technique in the same fading mobile satellite environment, extending the analysis results previously found for its performance over the AWGN channel to the MSAT-X channel.

Simon, Marvin K.↗
NASA NTRS1988

The design of trellis coded MPSK for fading channels: Set partitioning for optimum code design

A previous work on criteria for designing trellis-coded MPSK modulation to achieve minimum error probability performance on the Rician fading channel is extended. It is demonstrated that allowing for multiple symbols per trellis branch, i.e., multiple trellis-coded modulation (MTCM), provides an additional degree of freedom for designing a code to meet the optimization on the fading channel. Diversities larger than those achievable with conventional trellis codes having the same number of trellis states are now attainable, it is under these conditions that MTCM achieves its full potential.

Divsalar, Dariush↗
NASA NTRS1989

Generalized Multiple-Trellis-Coded Modulation

Generalized multiple-trellis-coded modulation technique combines multiple trellis coding (more than one channel symbol per trellis branch transmitted) with symmetrical M-ary phase-shift keying. Transmitter puts out k M-ary code symbols for every b input binary symbols. Throughout performances, b/k, of trellis-coded multiple-phase-shift-keying channels compared with computational cutoff rates, R0, of multiple-phase-shift keying. Performs better than conventional trellis-coded modulation technique, with no increase in complexity.

Divsalar, D.↗
NASA NTRS1988

Trellis coding techniques for mobile communications

A criterion for designing optimum trellis codes to be used over fading channels is given. A technique is shown for reducing certain multiple trellis codes, optimally designed for the fading channel, to conventional (i.e., multiplicity one) trellis codes. The computational cutoff rate R0 is evaluated for MPSK transmitted over fading channels. Examples of trellis codes optimally designed for the Rayleigh fading channel are given and compared with respect to R0. Two types of modulation/demodulation techniques are considered, namely coherent (using pilot tone-aided carrier recovery) and differentially coherent with Doppler frequency correction. Simulation results are given for end-to-end performance of two trellis-coded systems.

Divsalar, D.↗
NASA NTRS1989

An algorithm for computing the distance spectrum of trellis codes

A class of quasiregular codes is 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.

Rouanne, Marc↗
NASA NTRS1990

A hybrid M-algorithm/sequential decoder for convolutional and trellis codes

The Viterbi Algorithm (VA) is optimum in the sense of being maximum likelihood for decoding codes with a trellis structure. However, since the VA is in fact an exhaustive search of the code trellis, the complexity of the VA grows exponentially with the constraint length upsilon. This limits its application to codes with small values of upsilon and relatively modest coding gains. The M-Algorithm (MA) is a limited search scheme which carries forward M paths in the trellis, all of the same length. All successors of the M paths are extended at the next trellis depth, and all but the best M of these are dropped. Since a limited search convolutional decoder will flounder indefinitely if one of the paths in storage is not the correct one, the data are usually transmitted in blocks. It has been shown that the performance of the MA approaches the VA at high signal to noise ratios (SNR's) with an M which is far less than the 2 sup upsilon states in the full trellis. Thus the MA can be used with larger values of upsilon, making larger coding gains possible at high SNR's. However, it still requires a relatively large fixed computational effort to achieve good performance.

Wang, Fu-Quan↗
NASA NTRS1990

The performance of trellis-coded MDPSK with multiple symbol detection

The idea of using a multiple (more than two) symbol observation interval to improve error probability performance is applied to differential detection of trellis-coded multiple phase-shift keying (MPSK) over an additive white Gaussian noise (AWGN) channel. An equivalent Euclidean distance measure per trellis branch is determined for this detection scheme. This is used to define an augmented (larger multiplicity) trellis code whose distance measure is the conventional squared Euclidean distance typical of conventional trellis-coded modulation on the AWGN. Such an augmented multiple trellis code is a convenient mathematical tool for simplifying the analysis. Results are obtained by a combination of analysis (upper Chernoff bounds and asymptotic large-SNR approximations) and computer simulation. It is shown that only a slight increase (e.g., one symbol) in the length of the observation interval will provide a significant improvement in bit error probability performance.

Divsalar, Dariush↗
NASA NTRS1995

Trellis Decoding Complexity of Linear Block Codes

We consider the problem of finding a trellis for a linear block code that minimizes one or more measures of trellis complexity. The domain of optimization may be different permutations of the same code, or different codes with the same parameters. Constraints on trellises, including relationships between the minimal trellis of a code and that of the dual code, are used to derive bounds on complexity. We define a partial ordering on trellises: if a trellis is optimum with respect to this partial ordering, it has the desirable property that it simultaneously minimizes all of the complexity measures examined. We examine properties of such optimal trellises and give examples of optimal permutations of codes, most notably the (48,24,12) quadratic residue code.

trellis decoding↗
NASA NTRS1986

Trellis coded modulation for 4800-9600 bps transmission over a fading mobile satellite channel

The combination of trellis coding and multiple phase-shift-keyed (MPSK) signalling with the addition of asymmetry to the signal set is discussed with regard to its suitability as a modulation/coding scheme for the fading mobile satellite channel. For MPSK, introducing nonuniformity (asymmetry) into the spacing between signal points in the constellation buys a further improvement in performance over that achievable with trellis coded symmetric MPSK, all this without increasing average or peak power, or changing the bandwidth constraints imposed on the system. Whereas previous contributions have considered the performance of trellis coded modulation transmitted over an additive white Gaussian noise (AWGN) channel, the emphasis in the paper is on the performance of trellis coded MPSK in the fading environment. The results will be obtained by using a combination of analysis and simulation. It will be assumed that the effect of the fading on the phase of the received signal is fully compensated for either by tracking it with some form of phase-locked loop or with pilot tone calibration techniques. Thus, results will reflect only the degradation due to the effect of the fading on the amplitude of the received signal. Also, we shall consider only the case where interleaving/deinterleaving is employed to further combat the fading. This allows for considerable simplification of the analysis and is of great practical interest. Finally, the impact of the availability of channel state information on average bit error probability performance is assessed.

Divsalar, D.↗