Prediction device and method applied in a Viterbi decoder

• US 7,434,149 B2
• Filed: 04/29/2005
• Issued: 10/07/2008
• Est. Priority Date: 12/09/2004
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Huang, Chun-Hao, Shih, Yun-I, Ting, Hung-Jua, Hsu, Hsien-Yuan
• Primary Examiner(s): Louis-Jacques; Jacques
• Assistant Examiner(s): Alphonse; Fritz
• Application Number:
  US11/118,175
• Publication Number:
  US 20060129903A1
• Time in Patent Office: 1,257 Days
• Field of Search: 714/795, 714/794, 714/796, 714/798, 714/799, 714/819, 714/822
• US Class Current: 714/795
• CPC Class Codes: H03M 13/3738 with judging correct decoding
• CPC Class Codes: H03M 13/4176 using a plurality of RAMs, e.g. for carrying out a plurality of traceback implementations simultaneously
• CPC Class Codes: H03M 13/4192 using combined traceback and register-exchange
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing

Abstract

A prediction device and method for use in a Viterbi decoder is provided. The prediction device is applicable to a communication system with low bit error rate for reducing the count of accessing path memories, thereby lowering the power consumption of the system. The prediction device needs not activate the traceback modules when making a successful prediction. In other words, no access to the path memories is required. The predicted bits decoded and outputted by the decoded bit registers are the decoded bits from the Viterbi decoder. Therefore, the prediction device saves much traceback and power consumption for decoding.

Claims

1. A prediction device applicable to a Viterbi decoder, said Viterbi decoder at least comprising a path computing module, a path metric comparison module, a plurality of path memories, a traceback module and a storage control module, said prediction device comprising:

a prediction module receiving a path source of all states in a current stage from said path computing module and the state of the minimum path metric of the current stage from said path metric comparison module to determine whether the state of the minimum path metric of a previous stage is connected to the state of the minimum path metric of the current stage based on a prediction activation signal from said storage control module and the state of the minimum path metric of the previous stage stored in said prediction module, and outputting a prediction success signal to said storage control module; and

a plurality of decoded bit storages, each of said decoded bit storages corresponding to one of said path memories, and storing at least a decoded bit outputted by said prediction module or by said traceback module sequentially.

2. The prediction device as claimed in claim 1, wherein said storage control module comprises a plurality of counters, with each counter corresponding to one of said decoded bit storages, and each counter being increased by 1 when it receives a prediction success signal.

3. The prediction device as claimed in claim 1, wherein said storage control module sends a signal to said decoded bit storages at a preset output time for outputting all decoded bits stored in one of said plurality of decoded bit storages.

4. The prediction device as claimed in claim 3, wherein said preset output time is the time of finishing traceback.

5. A prediction method applicable to a Viterbi decoder, said Viterbi decoder at least comprising a path computing module, a path metric comparison module, a plurality of path memories each corresponding to one decoded bit storage, a traceback module and a storage control module, said storage control module at least comprising a plurality of counters with each counter corresponding to one decoded bit storage, said prediction method comprising the following steps of:

(a) using a prediction module to determine whether the state of the minimum path metric of a current stage is connected to the state of the minimum path metric of a previous stage based on a prediction activation signal from said storage control module and the state of the minimum path metric of the previous stage stored in said prediction module, said prediction module receiving a path source of all states in the current stage from said path computing module and the state of the minimum path metric of the current stage from said path metric comparison module;

(b) waiting until a preset condition is met to return to step (a) for activating prediction if the state of the minimum path metric of the current stage is not connected to the state of the minimum path metric of the previous state; and

(c) generating at least a decoded bit of the current stage, storing sequentially the decoded bit to one of said decoded bit storages, and adjusting the counter corresponding to the decoded bit storage currently used.

6. The prediction method as claimed in claim 5, further comprising the steps of:

(d) using a traceback mechanism to determine whether to directly output all the decoded bits in one of said decoded bit storages at a preset output time; and

(e) transmitting a decoded bit signal from said storage control module to the decoded bit storage corresponding to a last path memory being already traced-back, and outputting all decoded bits stored in the corresponding decoded bit storage.

7. The prediction method as claimed in claim 6, wherein said traceback mechanism of step (d) further comprising the following steps of:

(d1) determining whether the number of said path memories that are full is equal to a preset traceback number, and repeating step (d1) if the number is not equal;

(d2) going to step (d5) if a current path memory being traced back meets a criteria to waive traceback;

(d3) using said traceback module to store the decoded bits generated in each stage to the decoded bit storage of the current path memory during traceback, and going to step (d5) if the state of the current stage is equal to a combination of the decoded bits of previous several stages;

(d4) returning to step (d3) if the current path memory is not completely traced back yet; and

(d5) returning to step (e) if the number of path memories that have been traced back is equal to said preset traceback number;

otherwise, going to step (d2).

8. The prediction method as claimed in claim 7, wherein said criteria to waive traceback in said step (d2) is that the value in the counter corresponding to the decoded bit storage of the current path memory equals to total stages recorded by the current path memory.

9. The prediction method as claimed in claim 8, wherein the total recorded stages is 16.

10. The prediction method as claimed in claim 9, wherein the total number of decoded bits stored in said step (d3) equals to 32.

11. The prediction method as claimed in claim 7, wherein said preset traceback number is 3.

12. The prediction method as claimed in claim 6, wherein said preset output time is the time of finishing traceback.

13. The prediction method as claimed in claim 5, wherein said preset condition for activating prediction is that a current path memory is full and the processing of a next path memory is about to start.