Granted Patent B2

US 7,404,139 · App. 11/040,861 · Granted Jul 22, 2008

Abstract

Claims (44)

1. A method of decoding an encoded sequence of data symbols, comprising the steps of:

computing branch metrics for each state for each trellis stage of the encoded data sequence;

computing path metrics for each state for each trellis stage using the computed branch metrics of a present trellis stage and the path metrics of a previous trellis stage;

identifying a surviving path for each state at each trellis stage based on the computed path metric;

storing a decision bit for each state corresponding to the surviving path, the decision bit being the most significant bit of a previous state of the surviving path; and

performing an M-at-a-time traceback operation using the computed path metrics to generate M decoded data symbols in a single M-at-a-time traceback operation, wherein M ranges from 1 to N, N being a length of the encoded sequence of data symbols;

wherein performing the M-at-a-time traceback operation comprises:

identifying a beginning trellis stage for the M-at-time traceback operation;

reading M decision bits at each trellis stage beyond the identified beginning trellis stage; and

generating M decoded data symbols at each trellis stage based on the read M decision bits, wherein the steps of reading M decision bits and generating M decoded data symbols are repeated at each trellis stage until a predetermined number of data symbols remain to be decoded; and

wherein each of the steps is repeated to obtain the decoded sequence of data symbols.

2. The decoding method of claim 1 , wherein the M-at-a-time traceback operation step further comprises beginning the M-at-a-time trace back operation when decision bits for a predetermined number of trellis stages have been stored.

3. The decoding method of claim 2 , wherein the predetermined number of stored decision bits comprises a maximum number of decisions bits that can be stored.

4. The decoding method of claim 2 , wherein the M-at-a-time traceback operation further comprises the step of flushing out the remaining decoded data symbols.

5. The decoding method of claim 4 , wherein the step of flushing out the remaining decoded data symbols comprises performing an M-at-a-time traceback operation on the remaining encoded data symbols.

6. The decoding method of claim 1 , wherein the sequence of data symbols is encoded with a convolutional code.

7. A method of decoding an encoded sequence of data symbols, comprising the steps of:

computing branch metrics for each state for each trellis stage of the encoded data sequence;

computing path metrics for each state for each trellis stage using the computed branch metrics;

identifying a surviving path for each state at each trellis stage based on the computed path metric;

storing a decision bit corresponding to the surviving path for each state at each trellis stage, the decision bit being the most significant bit of a previous state of the surviving path; and

performing an M-at-a-time traceback operation using the stored decision bits to generate M decoded data symbols in a single M-at-a-time traceback operation, wherein M ranges from 1 to N, N being a length of the encoded sequence of data symbols, and wherein the step of performing the M-at-a-time traceback operation comprises:

identifying a beginning trellis stage for the M-at-a-time traceback operation, the M-at-a-time traceback operation beginning when L+M decision bits have been stored, wherein L is a maximum number of decision bits that can be stored at a time;

reading M decision bits at each trellis stage beyond the identified trellis stage;

generating M decoded data symbols at each trellis stage based on the read M decision bits, wherein the steps of reading M decision bits and generating M decoded data symbols are repeated at each trellis stage until L+M−1 data symbols remain to be decoded; and

flushing out the remaining L+M−1 encoded data symbols by performing a traceback operation on the remaining L+M−1 encoded data symbols.

8. A Maximum Likelihood Sequence Estimation (MLSE) decoder for decoding an encoded sequence of data symbols, the MLSE decoder comprising:

a branch metric unit for computing branch metrics for each stage at each trellis stage of the encoded sequence;

a path metric unit for a computing path metric and decision bit for each state at each trellis stage using the computed branch metrics; and

an M-at-a-time traceback unit for performing an M-at-a-time traceback operation using the computed decision bits to generate M decoded data symbols in a single M-at-a-time traceback operation, wherein M ranges from 1 to N, N being a length of the encoded sequence of data symbols, and

wherein the M-at-a-time traceback unit further comprises:

a traceback memory for storing the decision bit for each trellis stage, the decision bit being extracted from a surviving path at each trellis stage;

a write pointer generation unit for enabling storing of the decision bit at a memory address in the traceback memory;

a read pointer generation unit for computing the memory addresses from which each of the stored decision bits are read from the traceback memory, wherein the computed memory addresses being used for performing the traceback operation; and

a read logic unit for providing the logic to read the stored decision bits from the traceback memory.

9. The MLSE decoder according to claim 8 , wherein the sequence of data symbols is encoded with a convolutional code.

10. The MLSE decoder according to claim 8 , wherein the path metric unit comprises:

a path metric logic unit for computing the path metric for each stage at each trellis stage and identifying a surviving path at each stage; and

a path metric buffer for storing the computed path metrics of the surviving paths.

11. The MLSE decoder according to claim 8 , wherein the M-at-a-time traceback unit further comprises:

a traceback decode unit for initiating reading of M decision bits and decoding of M data symbols; and

a register unit for arranging the generated decoded bits in a predetermined order.

12. The MLSE decoder according to claim 11 , wherein the traceback memory comprises a plurality of dual port memory banks.

13. The MLSE decoder according to claim 11 , wherein the register unit comprises a plurality of shift registers.

Assignments (15)