SEARCH · Search NASA

Results for “Viterbi”

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.

SourceResearch connectionFrom yearThrough year

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

At least 19 records

All sources NASA NTRS DOE OSTI

NASA NTRS1979

Performance of mismatched Viterbi receiver on satellite channels

This paper presents an analysis of a satellite communication system using a Viterbi receiver. Here we have a bandlimited nonlinear channel where both uplink and downlink are taken into account as well as the effect of Intersymbol Interference, phase and time synchronization errors. In order that ISI can be combatted effectively, we use a Viterbi demodulator which is designed for the satellite channel when there is no uplink noise. The Viterbi demodulator for the channels with large memory is too complex to be implemented. To reduce the complexity, a Viterbi demodulator with memory shorter than the true channel memory is used. The objective of this paper is to analyze the performance degradation of this 'Mismatched Viterbi Receiver' due to the uplink noise and memory truncation, and to understand how the time and phase synchronization errors influence the performance.

Divsalar, D.↗

NASA NTRS1996

Good trellises for IC implementation of viterbi decoders for linear block codes

This paper investigates trellis structures of linear block codes for the IC (integrated circuit) implementation of Viterbi decoders capable of achieving high decoding speed while satisfying a constraint on the structural complexity of the trellis in terms of the maximum number of states at any particular depth. Only uniform sectionalizations of the code trellis diagram are considered. An upper bound on the number of parallel and structurally identical (or isomorphic) subtrellises in a proper trellis for a code without exceeding the maximum state complexity of the minimal trellis of the code is first derived. Parallel structures of trellises with various section lengths for binary BCH and Reed-Muller (RM) codes of lengths 32 and 64 are analyzed. Next, the complexity of IC implementation of a Viterbi decoder based on an L-section trellis diagram for a code is investigated. A structural property of a Viterbi decoder called ACS-connectivity which is related to state connectivity is introduced. This parameter affects the complexity of wire-routing (interconnections within the IC). The effect of five parameters namely: (1) effective computational complexity; (2) complexity of the ACS-circuit; (3) traceback complexity; (4) ACS-connectivity; and (5) branch complexity of a trellis diagram on the VLSI complexity of a Viterbi decoder is investigated. It is shown that an IC implementation of a Viterbi decoder based on a non-minimal trellis requires less area and is capable of operation at higher speed than one based on the minimal trellis when the commonly used ACS-array architecture is considered.

Moorthy, H. T.↗

NASA NTRS1996

Good trellises for IC implementation of viterbi decoders for linear block codes

Lin, Shu↗

NASA NTRS1997

Good Trellises for IC Implementation of Viterbi Decoders for Linear Block Codes

This paper investigates trellis structures of linear block codes for the integrated circuit (IC) implementation of Viterbi decoders capable of achieving high decoding speed while satisfying a constraint on the structural complexity of the trellis in terms of the maximum number of states at any particular depth. Only uniform sectionalizations of the code trellis diagram are considered. An upper-bound on the number of parallel and structurally identical (or isomorphic) subtrellises in a proper trellis for a code without exceeding the maximum state complexity of the minimal trellis of the code is first derived. Parallel structures of trellises with various section lengths for binary BCH and Reed-Muller (RM) codes of lengths 32 and 64 are analyzed. Next, the complexity of IC implementation of a Viterbi decoder based on an L-section trellis diagram for a code is investigated. A structural property of a Viterbi decoder called add-compare-select (ACS)-connectivity which is related to state connectivity is introduced. This parameter affects the complexity of wire-routing (interconnections within the IC). The effect of five parameters namely: (1) effective computational complexity; (2) complexity of the ACS-circuit; (3) traceback complexity; (4) ACS-connectivity; and (5) branch complexity of a trellis diagram on the very large scale integration (VISI) complexity of a Viterbi decoder is investigated. It is shown that an IC implementation of a Viterbi decoder based on a nonminimal trellis requires less area and is capable of operation at higher speed than one based on the minimal trellis when the commonly used ACS-array architecture is considered.

Moorthy, Hari T.↗

NASA NTRS1996

(abstract) MCD3 - A Constraint Length 15 Viterbi Decoder

JPL is responsible for many space missions, as part of NASA's continuing unmanned exploration of the solar system. Signals from spacecraft at planetary distances arrive at Earth with poor S/N ratio. To reduce errors, the signals are encoded with an inner code of Viterbi encoding. One of the key parameters of Viterbi encoding is the constraint length. Previous space missions have used a constraint length of 7. Newer missions use 15, to give a considerably improved error correction ability. However, the complexity of the Viterbi decoder is increased so as to be 256 times more complex.

communications↗

NASA NTRS1971

Viterbi decoding for satellite and space communication.

Convolutional coding and Viterbi decoding, along with binary phase-shift keyed modulation, is presented as an efficient system for reliable communication on power limited satellite and space channels. Performance results, obtained theoretically and through computer simulation, are given for optimum short constraint length codes for a range of code constraint lengths and code rates. System efficiency is compared for hard receiver quantization and 4 and 8 level soft quantization. The effects on performance of varying of certain parameters relevant to decoder complexity and cost are examined. Quantitative performance degradation due to imperfect carrier phase coherence is evaluated and compared to that of an uncoded system. As an example of decoder performance versus complexity, a recently implemented 2-Mbit/sec constraint length 7 Viterbi decoder is discussed. Finally a comparison is made between Viterbi and sequential decoding in terms of suitability to various system requirements.

Heller, J. A.↗

NASA NTRS1972

Performance versus complexity of Viterbi and sequential decoding.

Performance versus complexity is compared for the Viterbi maximum likelihood decoder and the sequential decoder of convolutional codes for the additive white Gaussian noise memoryless channel. It is found that sequential decoders outperform Viterbi decoders at low data rates (less than 100 kbps) for the same complexity. However, Viterbi decoders are less complex than sequential decoders at high data rates (10 Mbps and greater) for the same performance.

Huth, G. K.↗

NASA NTRS1989

Wiring Viterbi decoders (splitting deBruijn graphs)

A new Viterbi decoder, capable of decoding convolutional codes with constraint lengths up to 15, is under development for the Deep Space Network (DSN). A key feature of this decoder is a two-level partitioning of the Viterbi state diagram into identical subgraphs. The larger subgraphs correspond to circuit boards, while the smaller subgraphs correspond to Very Large Scale Integration (VLSI) chips. The full decoder is built from identical boards, which in turn are built from identical chips. The resulting system is modular and hierarchical. The decoder is easy to implement, test, and repair because it uses a single VLSI chip design and a single board design. The partitioning is completely general in the sense that an appropriate number of boards or chips may be wired together to implement a Viterbi decoder of any size greater than or equal to the size of the module.

Collins, O.↗

NASA NTRS1989

Systolic array processing of the Viterbi algorithm

Results on efficient forms of decoding convolutional codes based on the Viterbi algorithm by using systolic arrays are presented. Various properties of convolutional codes are discussed. A technique called strongly connected trellis decoding is introduced to increase the efficient utilization of all the systolic array processors. Issues dealing with the composite branch metric generation, survivor updating, overall system architecture, throughput rate, and computational overhead ratio also investigated. The scheme is applicable to both hard and soft decoding of any rate b/n convolutional code. It is shown that as the length of the code becomes large, the systolic Viterbi decoder maintains a regular and general interconnection structure as well as moderate throughput rate gain over the sequential Viterbi decoder.

Chang, Chi-Yung↗

NASA NTRS1989

Quantization effects in Viterbi decoding rate 1/n convolutional codes

A Viterbi decoder's performance loss due to quantizing data from the additive white Gaussian noise (AWGN) channel is studied. An optimal quantization scheme and branch metric calculation method are presented. The uniformly quantized channel capacity C(sub u)(q) is used to determine the smallest number of quantization bits q that does not cause a significant loss. The quantizer stepsize which maximizes C(sub u)(q) almost minimizes the decoder bit error rate (BER). However, a slightly larger stepsize is better, like the value that minimizes the Bhattacharyya bound. The range and renormalization of state metrics is analyzed, in particular for K = 15 decoders such as the Big Viterbi Decoder (BVD) for the Galileo mission. These results are required to design reduced hardware complexity Viterbi decoders with a negligible quantization loss.

Onyszchuk, I. M.↗

NASA NTRS1990

Validity of the two-level model for Viterbi decoder gap-cycle performance

A two-level model has previously been proposed for approximating the performance of a Viterbi decoder which encounters data received with periodically varying signal-to-noise ratio. Such cyclically gapped data is obtained from the Very Large Array (VLA), either operating as a stand-alone system or arrayed with Goldstone. This approximate model predicts that the decoder error rate will vary periodically between two discrete levels with the same period as the gap cycle. It further predicts that the length of the gapped portion of the decoder error cycle for a constraint length K decoder will be about K-1 bits shorter than the actual duration of the gap. The two-level model for Viterbi decoder performance with gapped data is subjected to detailed validation tests. Curves showing the cyclical behavior of the decoder error burst statistics are compared with the simple square-wave cycles predicted by the model. The validity of the model depends on a parameter often considered irrelevant in the analysis of Viterbi decoder performance, the overall scaling of the received signal or the decoder's branch-metrics. Three scaling alternatives are examined: optimum branch-metric scaling and constant branch-metric scaling combined with either constant noise-level scaling or constant signal-level scaling. The simulated decoder error cycle curves roughly verify the accuracy of the two-level model for both the case of optimum branch-metric scaling and the case of constant branch-metric scaling combined with constant noise-level scaling. However, the model is not accurate for the case of constant branch-metric scaling combined with constant signal-level scaling.

Dolinar, S.↗

NASA NTRS1990

Soft-decision Viterbi decoding with diversity combining

Diversity combining methods for convolutional coded and soft-decision Viterbi decoded channels in mobile satellite communications systems are evaluated and it is clarified that the pre-Viterbi-decoding maximal ratio combining shows better performance than other methods in Rician fading channels by computer simulation. A novel practical technique for maximal ratio combining is proposed, in which the coefficients for weighting are derived from soft-decision demodulated signals only. The proposed diversity combining method with soft-decision Viterbi decoding requires simple hardware and shows satisfactory performance with slight degradation of 0.3 dB in Rician fading channels compared with an ideal weighting scheme. Furthermore, this diversity method is applied to trellis coded modulation and significant Pe performance improvement is achieved.

Sakai, T.↗

NASA NTRS1990

A simple implementation of the Viterbi algorithm on the Motorola DSP56001

As systems designers design communication systems with digital rather than analog components to reduce noise and increase channel capacity, they must have the ability to perform traditional communication algorithms digitally. The use of trellis coded modulation as well as the extensive use of convolutional encoding for error detection and correction requires an efficient digital implementation of the Viterbi Algorithm for real time demodulation and decoding. Digital signal processors are now fast enough to implement Viterbi decoding in conjunction with the normal receiver/transmitter functions for lower speed channels on a single chip as well as performing fast decoding for higher speed channels, if the algorithm is implemented efficiently. The purpose of this paper is to identify a good way to implement the Viterbi Algorithm (VA) on the Motorola DSP56001, balancing performance considerations with speed and memory efficiency.

Messer, Dion D.↗

NASA NTRS1976

Space communication system for compressed data with a concatenated Reed-Solomon-Viterbi coding channel

A space communication system incorporating a concatenated Reed Solomon Viterbi coding channel is discussed for transmitting compressed and uncompressed data from a spacecraft to a data processing center on Earth. Imaging (and other) data are first compressed into source blocks which are then coded by a Reed Solomon coder and interleaver, followed by a convolutional encoder. The received data is first decoded by a Viterbi decoder, followed by a Reed Solomon decoder and deinterleaver. The output of the latter is then decompressed, based on the compression criteria used in compressing the data in the spacecraft. The decompressed data is processed to reconstruct an approximation of the original data-producing condition or images.

Rice, R. F.↗

NASA NTRS1978

Bursty channel errors and the Viterbi decoder

Recent applications have developed for spread spectrum communications, hardware data transfer, high rate digital systems, etc. that use channels for which errors tend to occur in short bursts in addition to those at random, i.e., compound channels. Viterbi decoding algorithms are generally very good for random error channels but are not as efficient for burst errors or for compound channels. This paper presents the results of a computer simulation study of the performance of various Viterbi decoders when receiving data corrupted with burst and random errors on the same channel. Simulations were performed using hard-decision CPSK.

Ingels, F.↗

NASA NTRS1981

Burst statistics of Viterbi decoding

A mathematical model of Viterbi decoder burst error performance is presented. This model allows for computer generation of Viterbi-like error sequences quickly and inexpensively for applications where large amounts of data are required. The model is corroborated through comparisons with actual software decoder simulations.

Deutsch, L. J.↗

NASA NTRS1980

The effects of receiver tracking phase error on the performance of the concatenated Reed-Solomon Viterbi channel coding system

In connection with attempts to achieve very low error probabilities, Odenwalder (1970) proposed a concatenated coding system using the Viterbi-decoded convolutional codes as the inner code and Reed-Solomon (RS) codes as the outer code. Analytical and experimental results are presented concerning the effects of the receiver tracking phase error on the performance of the concatenated RS/Viterbi channel coding system. On the basis of these results it is concluded that certain problems regarding communication operations on deep-space missions can be alleviated by employing the RS/Viterbi coding system. In one-way communication, an employment of RS/Viterbi coding will also provide greater data protection than the Viterbi-decoded convolutional-only coding system.

Liu, K. Y.↗

NASA NTRS1986

Fast VLSI Viterbi Decoder

Fast Viterbi decoder with fully parallel, pipeline architecture implemented on two VLSI NMOS chips. Decoder used with constraint-length-7, rate-1/2, convolutional error-correcting code widely used by NASA for deepspace telemetry data. With this (7,1/2) code, bit stream contains 2 bits per original data bit, and information about 1 data bit distributed over 7 pairs of bits. Design principles of decoder also applicable to Viterbi codes of other lengths and rates.

Wang, C. C.↗