An application-specific integrated circuit (ASIC) serves as a building block for a digital system that effects maximum-likelihood decoding of a Viterbi code (a binary convolutional error-correcting code) with a constraint length (K) in the range of 2 through 15 and a rate (r) in the range of 1/2 through 1/6. This ASIC is based on the same architecture as that of two older prototype K = 15, r = 1/6 Viterbi decoders, the first of which was reported in literature in 1988. These prototypes have functioned successfully in experiments, and their capabilities exceed those of state-of-the-art (K up to 7 andr at 1/2) commercial decoders as of the time of reporting the information for this article, but they have not been put into commercial production, partly because their complexities have given rise to reliability problems. Moreover, these prototypes have been limited to decoding speeds ≤ 750 kb/s.

Figure 1
This Simplified Diagram illustrates the major functional blocks of the ASIC. A complete decoder for a K = 15, r = 1/6 Viterbi code contains 64 such ASICs.

A decoder built from multiple units of the present ASIC is capable of decoding at a speed up to 4.4 Mb/s. Other notable aspects of the decoder and its ASIC building blocks include (1) implementation of a "pipeline" scheme for traceback (reconstruction of the most likely sequence of recent code states); (2) a novel CMOS (complementary metal oxide/ semiconductor) current-logic (CMCL) input/output scheme that affords low switching currents, high immunity to noise, and fast signaling among ASICs; and (3) timing-error-detection circuitry that helps to ensure synchronization of each ASIC with an externally generated clock signal.

In global terms, decoding is performed by a traceback processor that reads a traceback random-access memory (RAM). The decoder contains 64 identical ASICs, each of which (see figure) contains 1/64 of the traceback RAM and 1/64 of other circuits that are called "butterfly processors" because a graphical representation of the arithmetic logic at each node pair has a butterfly-like shape. However each ASIC contains a complete traceback processor, so that there is no problem of transferring traceback addresses among ASICs.

Code symbols enter each ASIC at the symbol-input circuit, where they are buffered and preprocessed. The preprocessed code symbols are fed to the butterfly processors, which produce metrics (measures of the likelihoods of candidate paths through sequences of code states). The metrics are fed, variously, back to the butterfly processors in the ASIC or to the butterfly processors in other ASICs. On the basis of comparisons between the metrics of the two alternative path branches that lead into each code state, the butterfly processors generate decision bits, which are transferred to the RAM. Pointers in the RAM-address controller keep track of the reading and writing locations. The traceback controller implements the traceback logic, which reads the RAM and puts out traceback bits to connect to the other ASICs. Data from the traceback controller are transferred to the output controller, which contains last-in/first-out (LIFO) memories. The output controller puts out the decoded data bit.

All registers in the ASIC are loaded initially from a 16-bit bus. The bus controller serves as the interface between the rest of the ASIC and the bus. All ASIC configurations are programmable and are set through this interface.

The ASIC includes metric accumulators (in the butterfly processors), which keep incrementing until they roll over. The metric growth block keeps track of the rate of growth in the metric accumulators to give a measure of how well the decoder is performing. A large metric-growth rate would indicate poor performance; this could occur because of a very low signal-to-noise ratio, or because of lack of synchronization of the decoder operation with the incoming code symbols.

This work was done by Gary R. Burke and William D. Whitaker of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at under the Electronic Systems category, or circle no. 103on the TSP Order card in this issue to receive a copy by mail ($5 charge).

In accordance with Public Law 96-517, the contractor has elected to retain title to this invention. Inquiries concerning rights for its commercial use should be addressed to

Technology Reporting Office
Mail Stop 122-116
4800 Oak Grove Drive
Pasadena, CA 91109
(818) 354-2240

Refer to NPO-19999, volume and number of this NASA Tech Briefs issue, and the page number.