US5533065A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Decreasing length tracebacks
Assignee: AT&T Inc
•
Filing: 1993-12-28
•
Granted: 1996-07-02
•
Expires: 2013-12-28
Abstract
Abstract A communication system including a Viterbi decoder for tracing a path through a trellis of individual state information and method of operation are disclosed. The traceback determines a decoded symbol. A matrix of surviving branch data is stored in an array of registers. Operating the system includes initiating a first traceback from a storage register at a first symbol instant. The traceback traces a path back through the trellis a first predetermined number of symbol instants to determine a first decoded symbol. The length of the traceback is changed and another traceback is executed. This process is repeated until all remaining final decoded symbols are decoded. In an alternate embodiment, the traceback length is repreatedly decremented by one less than the constraint length, with each traceback obtaining multiple decoded symbols.
Inventors
- 👤 David M. Blaker
- 👤 Gregory S. Ellard
- 👤 Mohammad S. Mobin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 15:18
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/37; H03M13/39; H03M13/3961; H03M13/41; H03M13/4161; H03M13/4169; H04; H04L; H04L1/00; H04L1/004; H04L1/0045; H04L1/0054
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
212 words
A method of operating a communication system comprising a receiver, the receiver for receiving signals, the method for tracing a path through an array of surviving branch data from various symbol instants to obtain a decoded symbol, the surviving branch data stored in an array of storage registers, the array of storage registers having one dimension determined by a constraint length, the method of comprising the steps of: receiving signals representative of encoded data; providing the received signals to a Viterbi decoder; generating the surviving branch data at a plurality of symbol instants based on the received signals; storing the surviving branch data in storage registers of the array of storage registers; initiating a first traceback of length k from a storage register at a predetermined symbol instant, the first traceback tracing a path back through the surviving branch data in the array of storage registers of the surviving branch data to obtain a first decoded symbol; and initiating another traceback from the storage register at the predetermined symbol instant, said another traceback having a length of k-m, where: k is the length of the first traceback; and 1≦m≦k-1 said another traceback tracing a path back through the array of storage registers of the surviving branch data to obtain another decoded symbol.
Claim 2
Independent Claim
212 words
A method of operating a communication system comprising a receiver, the receiver for receiving signals, the method for tracing a path through an array of surviving branch data from various symbol instants to obtain a decoded symbol, the surviving branch data stored in an array of storage registers, the array of storage registers having one dimension determined by a constraint length, the method of comprising the steps of: receiving signals representative of encoded data; providing the received signals to a Viterbi decoder; generating the surviving branch data at a plurality of symbol instants based on the received signals; storing the surviving branch data in storage registers of the array of storage registers; initiating a first traceback of length k from a storage register at a predetermined symbol instant, the first traceback tracing a path back through the surviving branch data in the array of storage registers of the surviving branch data to obtain a first decoded symbol; and initiating another traceback from the storage register at the predetermined symbol instant, said another traceback having a length of k-m, where: k is the length of the first traceback; and 1≦m≦k-1 said another traceback tracing a path back through the array of storage registers of the surviving branch data to obtain another decoded symbol.
Claim 3
Dependent Claim
27 words
The method as recited in claim 1, wherein the step of initiating another traceback is repeated with m taking on a different value in the range 1≦m≦k-1.
Claim 4
Dependent Claim
18 words
The method as recited in claim 2, wherein m is changed by one less than the constraint length.
Claim 5
Dependent Claim
27 words
The method as recited in claim 2 wherein m is changed by a value selected from the group consisting of 1, 2, 3, 4, 5, and 6.
Claim 6
Independent Claim
161 words
A method of operating a digital communication system comprising a receiver, the receiver for receiving signals, the method for tracing a path through an array of surviving branch data from various symbol instants to determine a decoded symbol, the array stored in an array of storage registers, the method comprising the step of: receiving signals representative of encoded data; providing the received signals to a Viterbi decoder; generating the surviving branch data at a plurality of symbol instants based on the received signals; storing the surviving branch data in the array of storage registers; initiating a series of at least two tracebacks from a predetermined symbol instant, said at least two tracebacks each tracing a path back through the surviving branch data in the array of storage registers of the surviving branch data to obtain a respective decoded symbol, whereby at least two decoded symbols are decoded from the series of at least two tracebacks initiated from the predetermined symbol instant.
Claim 7
Independent Claim
161 words
A method of operating a digital communication system comprising a receiver, the receiver for receiving signals, the method for tracing a path through an array of surviving branch data from various symbol instants to determine a decoded symbol, the array stored in an array of storage registers, the method comprising the step of: receiving signals representative of encoded data; providing the received signals to a Viterbi decoder; generating the surviving branch data at a plurality of symbol instants based on the received signals; storing the surviving branch data in the array of storage registers; initiating a series of at least two tracebacks from a predetermined symbol instant, said at least two tracebacks each tracing a path back through the surviving branch data in the array of storage registers of the surviving branch data to obtain a respective decoded symbol, whereby at least two decoded symbols are decoded from the series of at least two tracebacks initiated from the predetermined symbol instant.
Claim 8
Dependent Claim
25 words
The method of operating a digital communication system as recited in claim 5, wherein at least two tracebacks have traceback lengths that are consecutive numbers.
Claim 9
Dependent Claim
63 words
The method of operating a digital communication system as recited in claim 5, wherein the predetermined symbol instant has a magnitude, and at least one of said series of at least two tracebacks has a traceback length that has a magnitude that is less than the magnitude of the predetermined symbol instant from which said series of at least two tracebacks are initiated.
Claim 10
Dependent Claim
131 words
Apparatus for decoding encoded data, comprising: a Viterbi decoder for receiving the encoded data; means for generating surviving branch data at a plurality of symbol instants based on the encoded data; means for storing the surviving branch data in an array of storage registers; means for initiating a first traceback of length k from a predetermined symbol instant, the first traceback tracing a path back through the array of storage registers of the surviving branch data to obtain a first decoded symbol; and means for initiating from the predetermined symbol instant an additional traceback of length k-m, where: k is the length of the first traceback; and 1≦m≦k-1 the additional traceback tracing a path back through the array of storage registers of the surviving branch data to obtain another decoded symbol.
Claim 11
Dependent Claim
131 words
Apparatus for decoding encoded data, comprising: a Viterbi decoder for receiving the encoded data; means for generating surviving branch data at a plurality of symbol instants based on the encoded data; means for storing the surviving branch data in an array of storage registers; means for initiating a first traceback of length k from a predetermined symbol instant, the first traceback tracing a path back through the array of storage registers of the surviving branch data to obtain a first decoded symbol; and means for initiating from the predetermined symbol instant an additional traceback of length k-m, where: k is the length of the first traceback; and 1≦m≦k-1 the additional traceback tracing a path back through the array of storage registers of the surviving branch data to obtain another decoded symbol.
Claim 12
Dependent Claim
29 words
The apparatus as recited in claim 8, further comprising: means for initiating from the predetermined symbol instant a traceback having a length determined by a different value of m.
Claim 13
Dependent Claim
135 words
An integrated circuit for decoding encoded data comprising: a Viterbi decoder for receiving the encoded data; means for generating surviving branch data at a plurality of symbol instants based on the encoded data; random access memory for storing the surviving branch data in an array of storage registers; means for initiating a first traceback of length k from a predetermined symbol instant, the first traceback tracing a path back through the array of storage registers of the surviving branch data to obtain a first decoded symbol; and means for initiating from the predetermined symbol instant an additional traceback of length k-m, where: k is the length of the first traceback; and 1≦m≦k-1 the additional traceback tracing a path back through the array of storage registers of the surviving branch data to obtain another decoded symbol.
Claim 14
Dependent Claim
135 words
An integrated circuit for decoding encoded data comprising: a Viterbi decoder for receiving the encoded data; means for generating surviving branch data at a plurality of symbol instants based on the encoded data; random access memory for storing the surviving branch data in an array of storage registers; means for initiating a first traceback of length k from a predetermined symbol instant, the first traceback tracing a path back through the array of storage registers of the surviving branch data to obtain a first decoded symbol; and means for initiating from the predetermined symbol instant an additional traceback of length k-m, where: k is the length of the first traceback; and 1≦m≦k-1 the additional traceback tracing a path back through the array of storage registers of the surviving branch data to obtain another decoded symbol.
Claim 15
Dependent Claim
30 words
The integrated circuit as recited in claim 10, further comprising: means for initiating from the predetermined symbol instant a traceback having a length determined by a different value of m.
Claim 16
Independent Claim
164 words
A method of operating a digital communication system comprising a receiver, the receiver for receiving signals, the method for tracing a path through an array of surviving branch data from various symbol instants to determine a decoded symbol, the surviving branch data stored in an array of storage registers, the method comprising the step of: receiving signals representative of encoded data; providing the received signals to a Viterbi decoder; generating the surviving branch data at a plurality of symbol instants based on the received signals; storing the surviving branch data in the array of storage registers; initiating a series of tracebacks from a predetermined symbol instant, the traceback length of each traceback in the series of tracebacks defined by k-m, where: k is the length of an initial traceback; and m=1, 2, 3 . . . k-1 each traceback of the series of tracebacks tracing a path back through the array of storage registers of the surviving branch data to obtain a decoded symbol.
Claim 17
Independent Claim
164 words
A method of operating a digital communication system comprising a receiver, the receiver for receiving signals, the method for tracing a path through an array of surviving branch data from various symbol instants to determine a decoded symbol, the surviving branch data stored in an array of storage registers, the method comprising the step of: receiving signals representative of encoded data; providing the received signals to a Viterbi decoder; generating the surviving branch data at a plurality of symbol instants based on the received signals; storing the surviving branch data in the array of storage registers; initiating a series of tracebacks from a predetermined symbol instant, the traceback length of each traceback in the series of tracebacks defined by k-m, where: k is the length of an initial traceback; and m=1, 2, 3 . . . k-1 each traceback of the series of tracebacks tracing a path back through the array of storage registers of the surviving branch data to obtain a decoded symbol.
References Cited (Backward Citations)
US3789360A
Cited
US4493082A
Cited
EP0127984A2
Cited
US4583078A
Cited
US4868830A
Cited
US4797887A
Cited
US4777636A
Cited
US4905317A
Cited
EP0271984A2
Cited
US4748626A
Cited
US5220570A
Cited
US5159608A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-02 | 2000-01-01 | 2000-07-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-02 | 2004-01-01 | 2004-07-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-02 | 2008-01-01 | 2008-07-02 | $7700.00 | Window Closed / Lapsed |