Viterbi decoder with reduced number of data move operations

• US 4,748,626 A
• Filed: 01/28/1987
• Issued: 05/31/1988
• Est. Priority Date: 01/28/1987
• Status: Expired due to Term

• Current Assignee: Racal-Datacom, Inc. (Thales SA)
• Original Assignee: Racal Data Communications Incorporated
• Inventors: Wong, Chin-Pan
• Primary Examiner(s): ATKINSON, CHARLES
• Application Number:
  US07/007,860
• Time in Patent Office: 489 Days
• Field of Search: 371/43, 371/44, 371/45, 375/17, 375/34, 375/39
• US Class Current: 714/746
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/41 using the Viterbi algorithm or Viterbi processors
• CPC Class Codes: H04L 27/3438 using an underlying generalised cross constellation

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. In the Viterbi decoder according to claim 4, wherein said time unit comprises a symbol interval.

6. In the Viterbi decoder according to claim 4, wherein said time unit comprises a group interval consisting of a plurality of symbol intervals.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. In the Viterbi decoder according to claim 11, wherein said time unit comprises symbol interval.

14. In the Viterbi decoder according to claim 13, wherein said time unit comprises a group interval consisting of a plurality of symbol intervals.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.