US4748626A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Viterbi decoder with reduced number of data move operations
Assignee: Racal Data Communications Inc
•
Filing: 1987-01-28
•
Granted: 1988-05-31
•
Expires: 2007-01-28
Abstract
Abstract Disclosed is a modem including a transmitter having a convolutional encoder for transforming each time unit digital data into an expanded bit sequence having symbol-selecting bits and subset-selecting bits, the transmitter further providing modulation of a carrier signal and a receiver wherein a Viterbi decoder determines the maximum likelihood path through a trellis from a plurality of surviving paths using a wraparound memory wherein in each addressable location indexed to a current state of a surviving path there is stored a previous state of that surviving path.
Inventors
- 👤 Chin-Pan Wong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 22:39
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/37; H03M13/39; H03M13/41; H04; H04L; H04L27/00; H04L27/32; H04L27/34; H04L27/3405; H04L27/3416; H04L27/3427; H04L27/3438
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
230 words
In a Viterbi decoder for determining a maximum likelihood path from a plurality of surviving paths through a trellis, said trellis having a plurality of states repeated for each one of a plurality of time units, with the number of said surviving paths being equal to the number of states in said trellis, said Viterbi decoder having means for storing and retrieving said plurality of surviving paths, the improvement in said means for storing and retrieving said plurality of surviving paths comprising: memory means having a plurality of groups of addressable locations, the number of said groups being equal to the number of said states in said trellis and each one of said groups being associated with a unique one of said states; said memory means further having each one of said addressable locations of each said group associated with a unique one of said plurality of time units; means for storing in each said addressable location, associated with one of said states of one of said surviving paths, the previous state of said one of said surviving paths; and means for retrieval of said maximum likelihood path by repeatedly reading one of said addressable locations associated with said maximum likelihood path to obtain said previous state of said maximum likelihood path and thereby to determine for the previous time unit which of said addressable locations is to be read.
Claim 2
Dependent Claim
230 words
In a Viterbi decoder for determining a maximum likelihood path from a plurality of surviving paths through a trellis, said trellis having a plurality of states repeated for each one of a plurality of time units, with the number of said surviving paths being equal to the number of states in said trellis, said Viterbi decoder having means for storing and retrieving said plurality of surviving paths, the improvement in said means for storing and retrieving said plurality of surviving paths comprising: memory means having a plurality of groups of addressable locations, the number of said groups being equal to the number of said states in said trellis and each one of said groups being associated with a unique one of said states; said memory means further having each one of said addressable locations of each said group associated with a unique one of said plurality of time units; means for storing in each said addressable location, associated with one of said states of one of said surviving paths, the previous state of said one of said surviving paths; and means for retrieval of said maximum likelihood path by repeatedly reading one of said addressable locations associated with said maximum likelihood path to obtain said previous state of said maximum likelihood path and thereby to determine for the previous time unit which of said addressable locations is to be read.
Claim 3
Dependent Claim
54 words
In the Viterbi decoder according to claim 1, wherein said means for retrieval of said maximum likelihood path comprises means for using, after a predetermined number of said readings of said addressable locations, a last pair of adjacent, retrieved said states of said maximum likelihood path to determine a best estimated subset-defining bit group.
Claim 4
Dependent Claim
76 words
In the Viterbi decoder according to claim 2, wherein in said memory means said addressable locations of each said group are correlated with at least a sequence of L said time units, where L is defined as the truncation length of said Viterbi decoder, whereby each said addressable location is read from said memory means as a function of a given said time unit in conjunction with a given said state to provide said previous state.
Claim 5
Dependent Claim
30 words
In the Viterbi decoder according to claim 3, wherein said means for determining said estimated subset-defining bit group uses said states retrieved after L said readings of said addressable locations.
Claim 6
Dependent Claim
16 words
In the Viterbi decoder according to claim 4, wherein said time unit comprises a symbol interval.
Claim 7
Dependent Claim
23 words
In the Viterbi decoder according to claim 4, wherein said time unit comprises a group interval consisting of a plurality of symbol intervals.
Claim 8
Dependent Claim
81 words
In the Viterbi decoder according to claim 2, wherein said memory means includes a wrap around memory, said means for storing in each said addressable location includes a means for storing in said wraparound memory a plurality of newest said states associated with a newest said time unit in said addressable locations associated with an oldest said time unit and offset pointer means for identifying a position in said wraparound memory of said addressable locations associated with said newest time unit.
Claim 9
Dependent Claim
66 words
In the Viterbi decoder according to claim 7, wherein in said memory means the number of said addressable locations for each said group is equal to depth max, L is defined as the number of addressable locations of each said group having said states which are retrieved by said means for retrieval, where depth max≦L and wherein said means for retrieval includes means for changing L.
Claim 10
Dependent Claim
146 words
In a Viterbi decoder for determining a minimum cost path from a plurality of surviving paths through a trellis which has a plurality of states repeated in each of a plurality of time units, the improvement comprising: memory means having an addressable location indexed to each combination of one of said time units with one of said states; means for storing in each said addressable location, indexed to a current said state of one of said surviving paths, a previous said state of said one of said surviving paths; and means for retrieving said minimum cost path by repeatedly reading one of said addressable locations associated with one of said current states of said minimum cost path to provide said previous state of said minimum cost path which in turn becomes a new said current state of said minimum cost path for a subsequent said reading.
Claim 11
Dependent Claim
146 words
In a Viterbi decoder for determining a minimum cost path from a plurality of surviving paths through a trellis which has a plurality of states repeated in each of a plurality of time units, the improvement comprising: memory means having an addressable location indexed to each combination of one of said time units with one of said states; means for storing in each said addressable location, indexed to a current said state of one of said surviving paths, a previous said state of said one of said surviving paths; and means for retrieving said minimum cost path by repeatedly reading one of said addressable locations associated with one of said current states of said minimum cost path to provide said previous state of said minimum cost path which in turn becomes a new said current state of said minimum cost path for a subsequent said reading.
Claim 12
Dependent Claim
50 words
In the Viterbi decoder according to claim 9, wherein said means for retrieving further comprises means for using, after a predetermined number of said readings of said addressable locations, a last pair of adjacent, retrieved said states of said minimum cost path to determine a best estimated subset-defining bit group.
Claim 13
Dependent Claim
41 words
In the Viterbi decoder according to claim 10, wherein said addressable locations indexed to one said state are indexed to at least a sequence of L said time units, where L is defined as the truncation length of said Viterbi decoder.
Claim 14
Dependent Claim
30 words
In the Viterbi decoder according to claim 11, wherein said means for determining said estimated subset-defining bit group uses said states retrieved after L said readings of said addressable locations.
Claim 15
Dependent Claim
15 words
In the Viterbi decoder according to claim 11, wherein said time unit comprises symbol interval.
Claim 16
Dependent Claim
23 words
In the Viterbi decoder according to claim 13, wherein said time unit comprises a group interval consisting of a plurality of symbol intervals.
Claim 17
Dependent Claim
76 words
In the Viterbi decoder according to claim 10, wherein said memory means includes a wraparound memory, said means for storing includes means for storing in said wraparound memory a plurality of newest said states indexed to a newest said time unit in said addressable locations indexed to an oldest said time unit and offset pointer means for identifying a position in said wraparound memory of said group of addressable locations indexed to said newest time unit.
Claim 18
Dependent Claim
65 words
In the Viterbi decoder according to claim 15, wherein said memory means the number of said addressable locations for each said group is equal to depth max, L is defined as the number of addressable locations of each said group having said states which are retrieved by said means for retrieval, where depth max≦L and wherein said means for retrieval includes means for changing L.
Claim 19
Dependent Claim
159 words
In a method for determining a minimum cost path from a plurality of surviving paths through a trellis which has a plurality of states repeated in each of a plurality of time units, the improvement comprising the steps of: indexing an addressable location in a memory to each unique combination of one of said time units with one of said states; storing in each said addressable location, indexed to one of said states of one of said surviving paths, a previous said state of said one of said surviving paths; and starting with said addressable locations indexed to the newest said time unit, retrieving said minimum cost path by repeatedly reading one of said addressable locations associated with one of said states of said minimum cost path to provide said previous state of said minimum cost path which in turn defines which one of said addressable locations indexed to the next prior time unit is to be read next.
Claim 20
Dependent Claim
159 words
In a method for determining a minimum cost path from a plurality of surviving paths through a trellis which has a plurality of states repeated in each of a plurality of time units, the improvement comprising the steps of: indexing an addressable location in a memory to each unique combination of one of said time units with one of said states; storing in each said addressable location, indexed to one of said states of one of said surviving paths, a previous said state of said one of said surviving paths; and starting with said addressable locations indexed to the newest said time unit, retrieving said minimum cost path by repeatedly reading one of said addressable locations associated with one of said states of said minimum cost path to provide said previous state of said minimum cost path which in turn defines which one of said addressable locations indexed to the next prior time unit is to be read next.
Claim 21
Dependent Claim
47 words
In the method according to claim 17, wherein said step of retrieving further comprises using, after a predetermined number of said readings of said addressable locations, a last pair of adjacent, retrieved said states of said minimum cost path to determine a best estimated subset-defining bit group.
Claim 22
Dependent Claim
43 words
In the method according to claim 18, wherein said step of indexing includes correlating said addressable locations of each said group with at least a sequence of L said time units, where L is defined as the truncation length of said Viterbi decoder.
Claim 23
Dependent Claim
30 words
In the method according to claim 19, wherein said step of determining said estimated subset-defining bit group includes using said states retrieved after L said readings of said addressable locations.
Claim 24
Dependent Claim
68 words
In the method according to claim 18, wherein said step of storing includes storing in a wraparound memory a plurality of newest said states associated with a newest said time unit in said addressable locations associated with an oldest said time unit and identifying a position in said wraparound memory of said group of addressable locations associated with said newest time unit by use of an offset pointer.
Claim 25
Dependent Claim
52 words
In the method according to claim 21, wherein said addressable locations indexed to a given said state is equal to depth max, L is defined as the number of addressable locations of indexed to said given state which are retrieved, where the depth max≦L and further including the step of changing L.
References Cited (Backward Citations)
US4240156A
Cited
US4630032A
Cited
US4606027A
Cited
US4583236A
Cited
US4601044A
Cited
EP0154415A1
Cited
US4586182A
Cited
US4581601A
Cited
US4631735A
Cited
US4710746A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1991-05-31 | 1991-11-30 | 1992-05-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-05-31 | 1995-11-30 | 1996-05-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-05-31 | 1999-11-30 | 2000-05-31 | $7700.00 | Window Closed / Lapsed |