SEARCH · Search NASA
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.
The similarity between the Fast Fourier Transform and the Viterbi algorithm is exploited to develop a Concurrent Viterbi Algorithm suitable for a multiprocessor system interconnected as a hypercube. The proposed algorithm can efficiently decode large constraint length convolutional codes, using different degrees of parallelism, and is attractive for VLSI implementation.
"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.
The Big Viterbi Decoder (BVD), capable of decoding convolutional codes with constraint lengths of up to 15, is under development for the Deep Space Network (DSN). As part of the development, a commercial single-chip (7,1/2) Viterbi decoder is used to enable early start of system integration. Tests of the integrated partial system (including simulator, input systems, output interfaces, and computer controls) were recently completed at the DSN Compatibility Test Area (CTA-21) at JPL. The system elements used for the demonstration and test results are described.
Practical Viterbi decoders often fall significantly short of full maximum likelihood decoding performance because of survivor truncation effects. In the present work the authors study the tradeoff between truncation length and performance loss for the two most common variations of Viterbi's algorithm: best-state decoding (BSD) and fixed-state decoding (FSD). It is found that FSD survivors should be about twice as long as BSD survivors for comparable performance.
A prototype hardware Big Viterbi Decoder (BVD) was completed for an experiment with the Galileo Spacecraft. Searches for new convolutional codes, studies of Viterbi decoder hardware designs and architectures, mathematical formulations, and decompositions of the deBruijn graph into identical and hierarchical subgraphs, and very large scale integration (VLSI) chip design are just a few examples of tasks completed for this project. The BVD bit error rates (BER), measured from hardware and software simulations, are plotted as a function of bit signal to noise ratio E sub b/N sub 0 on the additive white Gaussian noise channel. Using the constraint length 15, rate 1/4, experimental convolutional code for the Galileo mission, the BVD gains 1.5 dB over the NASA standard (7,1/2) Maximum Likelihood Convolution Decoder (MCD) at a BER of 0.005. At this BER, the same gain results when the (255,233) NASA standard Reed-Solomon decoder is used, which yields a word error rate of 2.1 x 10(exp -8) and a BER of 1.4 x 10(exp -9). The (15, 1/6) code to be used by the Cometary Rendezvous Asteroid Flyby (CRAF)/Cassini Missions yields 1.7 dB of coding gain. These gains are measured with respect to symbols input to the BVD and increase with decreasing BER. Also, 8-bit input symbol quantization makes the BVD resistant to demodulated signal-level variations which may cause higher bandwidth than the NASA (7,1/2) code, these gains are offset by about 0.1 dB of expected additional receiver losses. Coding gains of several decibels are possible by compressing all spacecraft data.
The Big Viterbi Decoder (BVD) is a powerful error-correcting hardware device for the Deep Space Network (DSN), in support of the Galileo and Comet Rendezvous Asteroid Flyby (CRAF)/Cassini Missions. Recently, a prototype was completed and run successfully at 400,000 or more decoded bits per second. This prototype is a complex digital system whose core arithmetic unit consists of 256 identical very large scale integration (VLSI) gate-array chips, 16 on each of 16 identical boards which are connected through a 28-layer, printed-circuit backplane using 4416 wires. Special techniques were developed for debugging, testing, and locating faults inside individual chips, on boards, and within the entire decoder. The methods are based upon hierarchical structure in the decoder, and require that chips or boards be wired themselves as Viterbi decoders. The basic procedure consists of sending a small set of known, very noisy channel symbols through a decoder, and matching observables against values computed by a software simulation. Also, tests were devised for finding open and short-circuited wires which connect VLSI chips on the boards and through the backplane.
A new algorithm and hardware implementation of the Viterbi squaring function was developed. The use of an approximation squaring technique preserves the Viterbi performance as is demonstrated by Monte-Carlo simulations. Additionally, the 16-bit approximate squaring implementation is expected to require one-fourth the area and operate at three times the speed of the conventional squaring implementation.
The Galileo low-gain antenna mission will be supported by a coding system that uses a (14,1/4) inner convolutional code concatenated with Reed-Solomon codes of four different redundancies. Decoding for this code is designed to proceed in four distinct stages of Viterbi decoding followed by Reed-Solomon decoding. In each successive stage, the Reed-Solomon decoder only tries to decode the highest redundancy codewords not yet decoded in previous stages, and the Viterbi decoder redecodes its data utilizing the known symbols from previously decoded Reed-Solomon codewords. A previous article analyzed a two-stage decoding option that was not selected by Galileo. The present article analyzes the four-stage decoding scheme and derives the near-optimum set of redundancies selected for use by Galileo. The performance improvements relative to one- and two-stage decoding systems are evaluated.
A simplified Viterbi receiver with a reduced trellis and significanly less complexity is introduced with only a slight BER degradation compared to the full Viterbi receiver.
A method of formulating and packaging decision-making elements into a long constraint length Viterbi decoder which involves formulating the decision-making processors as individual Viterbi butterfly processors that are interconnected in a deBruijn graph configuration. A fully distributed architecture, which achieves high decoding speeds, is made feasible by novel wiring and partitioning of the state diagram. This partitioning defines universal modules, which can be used to build any size decoder, such that a large number of wires is contained inside each module, and a small number of wires is needed to connect modules. The total system is modular and hierarchical, and it implements a large proportion of the required wiring internally within modules and may include some external wiring to fully complete the deBruijn graph. pg,14.
This paper presents a method for separating cochannel FM signals. We show that the Viterbi algorithm, traditionally limited to estimation of digital quantities, can jointly track analog FM signals by quantizing the derivative of their instantaneous frequencies.
This paper describes the design of an ASIC performing the Viterbi decoder function with a constraint length of 15 and at a speed of 4.4 Mb/s. The architecture of the chip is described, as well as the design challenges which were overcome. The author also describes the successful application of the design system.
This paper describes the design of an ASIC performing the Viterbi decoder function with a constraint length of 15 and a speed of 4.4 Mb/s. The architecture of the chip is described, as well as the design challenges which were overcome. The author also describes the successful application of the design system.
Viterbi decoding error probability for convolutional codes using finite Markov chain modeling
Performance predictions for Viterbi decoding algorithm by simulation on UNIVAC 1108
Concepts involved in determining the performance of coded digital communications systems are introduced. The basic concepts of convolutional encoding and decoding are summarized, and hardware implementations of sequential and maximum likelihood decoders are described briefly. Results of parametric studies of the Viterbi decoding algorithm are summarized. Bit error probability is chosen as the measure of performance and is calculated, by using digital computer simulations, for various encoder and decoder parameters. Results are presented for code rates of one-half and one-third, for constraint lengths of 4 to 8, for both hard-decision and soft-decision bit detectors, and for several important systematic and nonsystematic codes. The effect of decoder block length on bit error rate also is considered, so that a more complete estimate of the relationship between performance and decoder complexity can be made.
The design and fabrication of an extremely low-power, constraint-length 7, rate 1/3 Viterbi decoder brassboard capable of operating at information rates of up to 100 kb/s is presented. The brassboard is partitioned to facilitate a later transition to an LSI version requiring even less power. The effect of soft-decision thresholds, path memory lengths, and output selection algorithms on the bit error rate is evaluated. A branch synchronization algorithm is compared with a more conventional approach. The implementation of the decoder and its test set (including all-digital noise source) are described along with the results of various system tests and evaluations. Results and recommendations are presented.
Two interleaving schemes are presented for R-S Viterbi concatenated coding channels and several R-S code array synchronization configurations are investigated. A procedure for obtaining synchronization sequences for the R-S code array under specified conditions is developed and used to identify sequences with desirable properties. The two interleaving schemes are found to be comparable in terms of array synchronization.