NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Collections About News Help Login
Back to Results
A VLSI decomposition of the deBruijn graphA new Viterbi decoder for convolutional codes with constraint lengths up to 15, called the Big Viterbi Decoder, is under development for the Deep Space Network. It will be demonstrated by decoding data from the Galileo spacecraft, which has a rate 1/4, constraint-length 15 convolutional encoder on board. Here, the mathematical theory underlying the design of the very-large-scale-integrated (VLSI) chips that are being used to build this decoder is explained. The deBruijn graph B sub n describes the topology of a fully parallel, rate 1/v, constraint length n+2 Viterbi decoder, and it is shown that B sub n can be built by appropriately wiring together (i.e., connecting together with extra edges) many isomorphic copies of a fixed graph called a B sub n building block. The efficiency of such a building block is defined as the fraction of the edges in B sub n that are present in the copies of the building block. It is shown, among other things, that for any alpha less than 1, there exists a graph G which is a B sub n building block of efficiency greater than alpha for all sufficiently large n. These results are illustrated by describing a special hierarchical family of deBruijn building blocks, which has led to the design of the gate-array chips being used in the Big Viterbi Decoder.
Document ID
19900012579
Acquisition Source
Legacy CDMS
Document Type
Reprint (Version printed in journal)
Authors
Collins, O. (Johns Hopkins Univ. Baltimore, MD., United States)
Dolinar, S. (Jet Propulsion Lab., California Inst. of Tech. Pasadena, CA, United States)
Mceliece, R. (Jet Propulsion Lab., California Inst. of Tech. Pasadena, CA, United States)
Pollara, F. (Jet Propulsion Lab., California Inst. of Tech. Pasadena, CA, United States)
Date Acquired
September 6, 2013
Publication Date
February 15, 1990
Publication Information
Publication: The Telecommunications and Data Acquisition Report
Subject Category
Communications And Radar
Accession Number
90N21895
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.

Related Records

There are no records associated with this record.
No Preview Available