Search NASA⌕ Search

SEARCH · Search NASA

Results for “trellis decoding”

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 91 records · Page 5
All sourcesNASA NTRSDOE OSTI
NASA NTRS1974

Convolutional codes. II - Maximum-likelihood decoding. III - Sequential decoding

Maximum-likelihood decoding is characterized as the determination of the shortest path through a topological structure called a trellis. Aspects of code structure are discussed along with questions regarding maximum-likelihood decoding on memoryless channels. A general bounding technique is introduced. The technique is used to obtain asymptotic bounds on the probability of error for maximum-likelihood decoding and list-of-2 decoding. The basic features of sequential algorithms are discussed along with a stack algorithm, questions of computational distribution, and the martingale approach to computational bounds.

Forney, G. D., Jr.↗
NASA NTRS1996

Soft-output decoding algorithms in iterative decoding of turbo codes

In this article, we present two versions of a simplified maximum a posteriori decoding algorithm. The algorithms work in a sliding window form, like the Viterbi algorithm, and can thus be used to decode continuously transmitted sequences obtained by parallel concatenated codes, without requiring code trellis termination. A heuristic explanation is also given of how to embed the maximum a posteriori algorithms into the iterative decoding of parallel concatenated codes (turbo codes). The performances of the two algorithms are compared on the basis of a powerful rate 1/3 parallel concatenated code. Basic circuits to implement the simplified a posteriori decoding algorithm using lookup tables, and two further approximations (linear and threshold), with a very small penalty, to eliminate the need for lookup tables are proposed.

Benedetto, S.↗
NASA NTRS1996

Soft-Output Decoding Algorithms in Iterative Decoding of Turbo Codes

In this article, we present two versions of a simplified maximum a posteriori decoding algorithm. The algorithms work in a sliding window form, like the Viterbi algorithm, and can thus be used to decode continuously transmitted sequences obtained by parallel concatenated codes, without requiring code trellis termination. A heuristic explanation is also given of how to embed the maximum a posteriori algorithms into the iterative decoding of parallel concatenated codes (turbo codes). The performances of the two algorithms are compared on the basis of a powerful rate 1/3 parallel concatenated code. Basic circuits to implement the simplified a posteriori decoding algorithm using lookup tables, and two further approximations (linear and threshold), with a very small penalty, to eliminate the need for lookup tables are proposed.

Benedetto, S.↗
NASA NTRS2007

Optimizations of a Hardware Decoder for Deep-Space Optical Communications

The National Aeronautics and Space Administration has developed a capacity approaching modulation and coding scheme that comprises a serial concatenation of an inner accumulate pulse-position modulation (PPM) and an outer convolutional code [or serially concatenated PPM (SCPPM)] for deep-space optical communications. Decoding of this code uses the turbo principle. However, due to the nonbinary property of SCPPM, a straightforward application of classical turbo decoding is very inefficient. Here, we present various optimizations applicable in hardware implementation of the SCPPM decoder. More specifically, we feature a Super Gamma computation to efficiently handle parallel trellis edges, a pipeline-friendly 'maxstar top-2' circuit that reduces the max-only approximation penalty, a low-latency cyclic redundancy check circuit for window-based decoders, and a high-speed algorithmic polynomial interleaver that leads to memory savings. Using the featured optimizations, we implement a 6.72 megabits-per-second (Mbps) SCPPM decoder on a single field-programmable gate array (FPGA). Compared to the current data rate of 256 kilobits per second from Mars, the SCPPM coded scheme represents a throughput increase of more than twenty-six fold. Extension to a 50-Mbps decoder on a board with multiple FPGAs follows naturally. We show through hardware simulations that the SCPPM coded system can operate within 1 dB of the Shannon capacity at nominal operating conditions.

quadratic polynomial interleaver↗
NASA NTRS1986

Simplified Decoding of Convolutional Codes

Some complicated intermediate steps shortened or eliminated. Decoding of convolutional error-correcting digital codes simplified by new errortrellis syndrome technique. In new technique, syndrome vector not computed. Instead, advantage taken of newly-derived mathematical identities simplify decision tree, folding it back on itself into form called "error trellis." This trellis graph of all path solutions of syndrome equations. Each path through trellis corresponds to specific set of decisions as to received digits. Existing decoding algorithms combined with new mathematical identities reduce number of combinations of errors considered and enable computation of correction vector directly from data and check bits as received.

Truong, T. K.↗
NASA NTRS1980

Joint map data/phase sequence estimation for trellis phase codes

A unified estimation procedure is formulated for the coherent detection of trellis phase codes, including partial response FM codes and multi-h codes. The unknown carrier phase is imbedded in the system state vector, and by simple augmentation of the decoder's state space, joint data and carrier estimation may be accomplished. The procedure is general to all trellis phase codes analyzed thus far. The effect of a static phase error on detection performance is also treated.

Wilson, S. G.↗
NASA NTRS1997

Soft-Decision Decoding of Binary Linear Block Codes Based on an Iterative Search Algorithm

This correspondence presents a suboptimum soft-decision decoding scheme for binary linear block codes based on an iterative search algorithm. The scheme uses an algebraic decoder to iteratively generate a sequence of candidate codewords one at a time using a set of test error patterns that are constructed based on the reliability information of the received symbols. When a candidate codeword is generated, it is tested based on an optimality condition. If it satisfies the optimality condition, then it is the most likely (ML) codeword and the decoding stops. If it fails the optimality test, a search for the ML codeword is conducted in a region which contains the ML codeword. The search region is determined by the current candidate codeword and the reliability of the received symbols. The search is conducted through a purged trellis diagram for the given code using the Viterbi algorithm. If the search fails to find the ML codeword, a new candidate is generated using a new test error pattern, and the optimality test and search are renewed. The process of testing and search continues until either the MEL codeword is found or all the test error patterns are exhausted and the decoding process is terminated. Numerical results show that the proposed decoding scheme achieves either practically optimal performance or a performance only a fraction of a decibel away from the optimal maximum-likelihood decoding with a significant reduction in decoding complexity compared with the Viterbi decoding based on the full trellis diagram of the codes.

Lin, Shu↗
NASA NTRS2010

Serial turbo trellis coded modulation using a serially concatenated coder

Serial concatenated trellis coded modulation (SCTCM) includes an outer coder, an interleaver, a recursive inner coder and a mapping element. The outer coder receives data to be coded and produces outer coded data. The interleaver permutes the outer coded data to produce interleaved data. The recursive inner coder codes the interleaved data to produce inner coded data. The mapping element maps the inner coded data to a symbol. The recursive inner coder has a structure which facilitates iterative decoding of the symbols at a decoder system. The recursive inner coder and the mapping element are selected to maximize the effective free Euclidean distance of a trellis coded modulator formed from the recursive inner coder and the mapping element. The decoder system includes a demodulation unit, an inner SISO (soft-input soft-output) decoder, a deinterleaver, an outer SISO decoder, and an interleaver.

Divsalar, Dariush↗
NASA NTRS2011

Serial turbo trellis coded modulation using a serially concatenated coder

Serial concatenated trellis coded modulation (SCTCM) includes an outer coder, an interleaver, a recursive inner coder and a mapping element. The outer coder receives data to be coded and produces outer coded data. The interleaver permutes the outer coded data to produce interleaved data. The recursive inner coder codes the interleaved data to produce inner coded data. The mapping element maps the inner coded data to a symbol. The recursive inner coder has a structure which facilitates iterative decoding of the symbols at a decoder system. The recursive inner coder and the mapping element are selected to maximize the effective free Euclidean distance of a trellis coded modulator formed from the recursive inner coder and the mapping element. The decoder system includes a demodulation unit, an inner SISO (soft-input soft-output) decoder, a deinterleaver, an outer SISO decoder, and an interleaver.

Divsalar, Dariush↗
NASA NTRS1990

VLSI Architecture For Viterbi Decoder

"Pipeline" architecture developed for very-large-scale integrated (VLSI) Viterbi decoding circuits for binary convolutional codes of large constraint lengths. In scheme, single sequential processor computes path metrics in trellis diagram (diagram in which paths and nodes represent possible sequences of code states and in which metrics indicate relative likelihoods of sequences). Systolic-array method used to store path information as well as to choose path with best metric. VLSI Viterbi-decoder architecture is compromise between speed and complexity. Size of decoding circuit increases approximately linearly with constraint length of code, and additional circuit chips added with moderate numbers of interconnections.

Hsu, In-Shek↗
NASA NTRS1988

Method for Veterbi decoding of large constraint length convolutional codes

A new method of Viterbi decoding of convolutional codes lends itself to a pipline VLSI architecture using a single sequential processor to compute the path metrics in the Viterbi trellis. An array method is used to store the path information for NK intervals where N is a number, and K is constraint length. The selected path at the end of each NK interval is then selected from the last entry in the array. A trace-back method is used for returning to the beginning of the selected path back, i.e., to the first time unit of the interval NK to read out the stored branch metrics of the selected path which correspond to the message bits. The decoding decision made in this way is no longer maximum likelihood, but can be almost as good, provided that constraint length K in not too small. The advantage is that for a long message, it is not necessary to provide a large memory to store the trellis derived information until the end of the message to select the path that is to be decoded; the selection is made at the end of every NK time unit, thus decoding a long message in successive blocks.

Hsu, In-Shek↗
NASA NTRS2004

Serial-Turbo-Trellis-Coded Modulation with Rate-1 Inner Code

Serially concatenated turbo codes have been proposed to satisfy requirements for low bit- and word-error rates and for low (in comparison with related previous codes) complexity of coding and decoding algorithms and thus low complexity of coding and decoding circuitry. These codes are applicable to such high-level modulations as octonary phase-shift keying (8PSK) and 16-state quadrature amplitude modulation (16QAM); the signal product obtained by applying one of these codes to one of these modulations is denoted, generally, as serially concatenated trellis-coded modulation (SCTCM). These codes could be particularly beneficial for communication systems that must be designed and operated subject to limitations on bandwidth and power. Some background information is prerequisite to a meaningful summary of this development. Trellis-coded modulation (TCM) is now a well-established technique in digital communications. A turbo code combines binary component codes (which typically include trellis codes) with interleaving. A turbo code of the type that has been studied prior to this development is composed of parallel concatenated convolutional codes (PCCCs) implemented by two or more constituent systematic encoders joined through one or more interleavers. The input information bits feed the first encoder and, after having been scrambled by the interleaver, enter the second encoder. A code word of a parallel concatenated code consists of the input bits to the first encoder followed by the parity check bits of both encoders. The suboptimal iterative decoding structure for such a code is modular, and consists of a set of concatenated decoding modules one for each constituent code connected through an interleaver identical to the one in the encoder side. Each decoder performs weighted soft decoding of the input sequence. PCCCs yield very large coding gains at the cost of a reduction in the data rate and/or an increase in bandwidth.

Divsalar, Dariush↗
NASA NTRS1996

Architecture and implementation considerations of a high-speed Viterbi decoder for a Reed-Muller subcode

The (64, 40, 8) subcode of the third-order Reed-Muller (RM) code for high-speed satellite communications is proposed. The RM subcode can be used either alone or as an inner code of a concatenated coding system with the NASA standard (255, 233, 33) Reed-Solomon (RS) code as the outer code to achieve high performance (or low bit-error rate) with reduced decoding complexity. It can also be used as a component code in a multilevel bandwidth efficient coded modulation system to achieve reliable bandwidth efficient data transmission. The progress made toward achieving the goal of implementing a decoder system based upon this code is summarized. The development of the integrated circuit prototype sub-trellis IC, particularly focusing on the design methodology, is addressed.

Lin, Shu↗
NASA NTRS1990

New multi-level codes over GF(q)

Set partitioning to multi-dimensional signal spaces over GF(q), particularly GF sup q-1(q) and GF sup q (q), and show how to construct both multi-level block codes and multi-level trellis codes over GF(q). Two classes of multi-level (n, k, d) block codes over GF(q) with block length n, number of information symbols k, and minimum distance d sub min greater than or = d, are presented. These two classes of codes use Reed-Solomon codes as component codes. They can be easily decoded as block length q-1 Reed-Solomon codes or block length q or q + 1 extended Reed-Solomon codes using multi-stage decoding. Many of these codes have larger distances than comparable q-ary block codes, as component codes. Low rate q-ary convolutional codes, work error correcting convolutional codes, and binary-to-q-ary convolutional codes can also be used to construct multi-level trellis codes over GF(q) or binary-to-q-ary trellis codes, some of which have better performance than the above block codes. All of the new codes have simple decoding algorithms based on hard decision multi-stage decoding.

Wu, Jiantian↗
NASA NTRS1992

New multilevel codes over GF(q)

Set partitioning to multi-dimensional signal spaces over GF(q), particularly GF sup q-1(q) and GF sup q (q), and show how to construct both multi-level block codes and multi-level trellis codes over GF(q). Two classes of multi-level (n, k, d) block codes over GF(q) with block length n, number of information symbols k, and minimum distance d sub min greater than or = d, are presented. These two classes of codes use Reed-Solomon codes as component codes. They can be easily decoded as block length q-1 Reed-Solomon codes or block length q or q + 1 extended Reed-Solomon codes using multi-stage decoding. Many of these codes have larger distances than comparable q-ary block codes, as component codes. Low rate q-ary convolutional codes, work error correcting convolutional codes, and binary-to-q-ary convolutional codes can also be used to construct multi-level trellis codes over GF(q) or binary-to-q-ary trellis codes, some of which have better performance than the above block codes. All of the new codes have simple decoding algorithms based on hard decision multi-stage decoding.

Wu, Jiantian↗
NASA NTRS1987

Soft-decision decoding of some block codes

The performance of certain binary block codes with soft-decision decoding is evaluated by simulation. A construction is proposed to introduce memory on block codes, and simulation results are shown for a trellis code derived from the Nordstrom-Robinson code.

Pollara, F.↗
NASA NTRS1989

Error control techniques for satellite and space communications

Two aspects of the work for NASA are examined: the construction of multi-dimensional phase modulation trellis codes and a performance analysis of these codes. A complete list is contained of all the best trellis codes for use with phase modulation. LxMPSK signal constellations are included for M = 4, 8, and 16 and L = 1, 2, 3, and 4. Spectral efficiencies range from 1 bit/channel symbol (equivalent to rate 1/2 coded QPSK) to 3.75 bits/channel symbol (equivalent to 15/16 coded 16-PSK). The parity check polynomials, rotational invariance properties, free distance, path multiplicities, and coding gains are given for all codes. These codes are considered to be the best candidates for implementation of a high speed decoder for satellite transmission. The design of a hardware decoder for one of these codes, viz., the 16-state 3x8-PSK code with free distance 4.0 and coding gain 3.75 dB is discussed. An exhaustive simulation study of the multi-dimensional phase modulation trellis codes is contained. This study was motivated by the fact that coding gains quoted for almost all codes found in literature are in fact only asymptotic coding gains, i.e., the coding gain at very high signal to noise ratios (SNRs) or very low BER. These asymptotic coding gains can be obtained directly from a knowledge of the free distance of the code. On the other hand, real coding gains at BERs in the range of 10(exp -2) to 10(exp -6), where these codes are most likely to operate in a concatenated system, must be done by simulation.

Costello, Daniel J., Jr.↗
NASA NTRS1990

Trellis-coded multidimensional phase modulation

A 2L-dimensional multiple phase-shift keyed (MPSK) (L x MPSK) signal set is obtained by forming the Cartesian product of L two-dimensional MPSK signal sets. A systematic approach to partitioning L x 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 x 4PSK, L x 8PSK, and L x 16PSK modulation schemes are found for L = 1-4 and a variety of code rates and decoder complexities, many of which are fully transparent to discrete phase rotations of the signal set. The new codes achieve asymptotic coding gains up to 5.85 dB.

Pietrobon, Steven S.↗