De bruijn graph based VLSI viterbi decoder
AssigneeThe United States of America as represented by the Secretary of the Air Force
InventorsDhiraj K. Pradhan, Nitin H. Vaidya
Life of this patent
Estimating the term…
Abstract
The disclosed system uses a binary tree which is embedded in a De Bruijn graph to sort the survivor paths based on their path metrics. The system includes a sorting algorithm which is implemented in a pipelined fashion. The same communication structure underlining the De Bruijn graph is used, so that no additional communication overhead is required for sorting. The system implementation is parallel resulting in a high throughput.
Claims1
A system for decoding a convolutional code (n, k, m), where k is the input, n is the output and m is the input memory, said code being supplied to a generator matrix G(D)=(1+D, 1+D.sup.2, +D+D.sub.2) where D and D2 are delay elements equal in number to m, comprising:
- a DeBruijn graph having 2.sup.m nodes, each of said nodes corresponding to one of four states 00, 01, 10, and 11 of a Viterbi decoder, each of said nodes having one input and two outputs, wherein k=1, m=2 and n=3.0;
- a plurality of Viterbi trellis decoders for decoding said convolutional code, one trellis decoder being embedded in each of said nodes, each trellis decoder having a plurality of arcs, every arc in the trellis of each Viterbi decoder providing a connection corresponding to each of said nodes.
Dependencies are inferred from the claim text.