US5491705A
Expired / Lapsed
US
⏱️ 0.0 years remaining
De bruijn graph based VLSI viterbi decoder
Assignee: United States Department of the Air Force
•
Filing: 1992-06-18
•
Granted: 1996-02-13
•
Expires: 2012-06-18
Abstract
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.
Inventors
- 👤 Dhiraj K. Pradhan
- 👤 Nitin H. Vaidya
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 07:59
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/65; H03M13/6502; H03M13/37; H03M13/39; H03M13/41
Claims Analysis
Total Claims: 2
Claim 1
Independent Claim
141 words
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 2 , +D+D 2 ) where D and D2 are delay elements equal in number to m, comprising: a DeBruijn graph having 2 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.
Claim 2
Independent Claim
141 words
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 2 , +D+D 2 ) where D and D2 are delay elements equal in number to m, comprising: a DeBruijn graph having 2 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.
References Cited (Backward Citations)
US3789360A
Cited
US4015238A
Cited
US4240156A
Cited
US4354269A
Cited
US4493082A
Cited
US4486882A
Cited
US4500994A
Cited
US4630032A
Cited
US4545054A
Cited
US4606027A
Cited
US4715037A
Cited
US4581601A
Cited
US4730322A
Cited
US4710746A
Cited
US4748626A
Cited
US4888775A
Cited
US5150381A
Cited
US5068859A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-02-12 | 1999-08-14 | 2000-02-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-02-12 | 2003-08-14 | 2004-02-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-02-12 | 2007-08-14 | 2008-02-13 | $7700.00 | Window Closed / Lapsed |