System and methods for low complexity list decoding of turbo codes and convolutional codes

1. A method of decoding a signal, comprising:

receiving a signal to be decoded, where the signal includes at least one symbol;

decoding the signal in stages, where each at least one symbol of the signal is decoded into at least one bit per stage, wherein a Log-Likelihood Ratio (LLR) and a path metric are determined for each possible path for each at least one bit at each stage;

determining magnitudes of the LLRs;

identifying K bits of the signal with smallest corresponding LLR magnitudes;

identifying, for each of the K bits, L possible paths at each decoder stage for a user-definable number of decoder stages;

identifying a set of paths with the highest magnitude from among the L possible paths;

performing forward and backward traces, for each path of the identified set of paths with the highest magnitude, to determine candidate codewords;

performing a Cyclic Redundancy Check (CRC) on the candidate codewords; and

stopping the CRC after a first candidate codeword passes the CRC

wherein performing forward and backward traces comprises:

setting l=1, for l=1, 2, . . . , L;

setting s′=PreState, s=SuccState, and k=TrellisStep;

determining b k l =b(s′, s);

setting j=k+1, for j=k+1, k+2, . . . , N−1;

setting s′=s;

determining s=arg{max s [σ j (s′, s)]};

determining b j l =b(s′, s);

incrementing j and returning to the step of setting j=k+1 if j<N−1; otherwise:

setting s=PreState;

setting j=k−1, for j=k−1, k−2, . . . , 0;

determining s′=arg{max s′ [σ j (s′, s)]};

determining b j l =b(s′, s);

setting s=s′; and

incrementing j and returning to the step of setting j=k−1 if j>0; otherwise:

performing Cyclic Redundancy Check (CRC) on l and stopping if l passes the check, otherwise incrementing l and returning to the step of setting s′=PreState, s=SuccState, and k=TrellisStep.

2. The method of claim 1 , wherein decoding the signal comprises decoding a signal using Maximum-Logarithm Maximum-A-Posteriori decoding.

3. The method of claim 1 , further comprising:

recording paths traced that failed the CRC; and

not regenerating a path that has failed the CRC.

4. The method of claim 1 , further comprising:

stopping a forward or backward trace if a path merges with a Maximum Likelihood (ML) path and considering a rest of the path as the ML path.

5. The method of claim 1 , further comprising:

identifying K bits of the signal with an opposite sign of the K bits with the smallest corresponding LLR magnitudes; and

identifying, for each of the K bits of the signal with the opposite sign of the K bits with the smallest corresponding LLR magnitudes, L possible paths with the largest path metrics at each decoder stage for a user-definable number of decoder stages.

6. The method of claim 1 , further comprising:

identifying K bits of the signal with largest corresponding LLR magnitudes;

identifying, for each of the K bits, (L/2)−1 possible paths with the largest path metrics at each decoder stage for a user-definable number of decoder stages;

identifying K bits of the signal with an opposite sign of the K bits with the largest corresponding LLR magnitudes; and

identifying, for each of the K bits of the signal with the opposite sign of the K bits with the largest corresponding LLR magnitudes, L/2 possible paths with the largest path metrics at each decoder stage for a user-definable number of decoder stages.

7. A method of decoding a signal, comprising:

receiving a signal to be decoded, where the signal includes at least one symbol;

decoding the signal in stages, where each at least one symbol of the signal is decoded into at least one bit per stage, wherein a Log-Likelihood Ratio (LLR) and a path metric are determined for each possible path for each at least one bit at each stage;

determining magnitudes of the LLRs;

identifying K bits of the signal with smallest corresponding LLR magnitudes;

identifying, for each of the K bits, L possible paths with input 0 at each decoder stage for a user-definable number of decoder stages;

identifying a set of input 0 paths with the highest magnitude from among the L possible paths with input 0;

identifying, for each of the K bits, L possible paths with input 1 at each decoder stage for a user-definable number of decoder stages;

identifying a set of input 1 paths with the highest magnitude from among the L possible paths with input 1;

identifying K bits of the signal with largest corresponding LLR magnitudes;

identifying, for each of the K bits, (L/2)−1 possible paths with the largest path metrics at each decoder stage for a user-definable number of decoder stages;

identifying K bits of the signal with an opposite sign of the K bits with the largest corresponding LLR magnitudes; and

identifying, for each of the K bits of the signal with the opposite sign of the K bits with the largest corresponding LLR magnitudes, L/2 possible paths with the largest path metrics at each decoder stage for a user-definable number of decoder stages;

performing forward and backward traces, for each path of the identified set of input 0 paths and set of input 1 paths, to determine candidate codewords;

performing a Cyclic Redundancy Check (CRC) on the candidate codewords; and

stopping the CRC after a first candidate codeword passes the CRC.

8. The method of claim 7 , wherein decoding the signal comprises decoding a signal using Maximum-Logarithm Maximum-A-Posteriori decoding.

9. The method of claim 7 , wherein performing forward and backward traces comprises:

setting l=1, for l=1, 2, . . . , L;

setting s′=PreState, s=SuccState, and k=TrellisStep;

determining b k l =b(s′, s);

setting j=k+1, for j=k+1, k+2, . . . , N−1;

setting s′=s;

determining s=arg{max s [σ j (s′, s)]};

determining b k l =b(s′, s);

incrementing j and returning to the step of setting j=k+1 if j<N−1; otherwise:

setting s=PreState;

setting j=k+1, for j=k+1, k+2, . . . , 0;

determining s′=arg{max s′ [σ j (s′, s)]};

determining b k l =b(s′, s);

setting s=s′; and

incrementing j and returning to the step of setting j=k−1 if j>0; otherwise:

performing a Cyclic Redundancy Check (CRC) on l and stopping if l passes the check, otherwise incrementing l and returning to the step of setting s′=PreState, s=SuccState, and k=TrellisStep.

10. A non-transitory computer-readable recording medium having recorded thereon a program for decoding a signal, the program, when executed by a computer, causes the computer to perform a method, the method comprising:

receiving a signal to be decoded, where the signal includes at least one symbol;

decoding the signal in stages, where each at least one symbol of the signal is decoded into at least one bit per stage, wherein a Log-Likelihood Ratio (LLR) and a path metric are determined for each possible path for each at least one bit at each stage;

determining the magnitudes of the LLRs;

identifying K bits of the signal with the smallest corresponding LLR magnitudes;

identifying, for each of the K bits, L possible paths at each decoder stage for a user-definable number of decoder stages;

identifying a set of paths with the highest magnitude from among the L possible paths;

performing forward and backward traces, for each path of the identified set of paths with the highest magnitude, to determine candidate codewords;

performing a Cyclic Redundancy Check (CRC) on the candidate codewords; and

stopping the CRC after a first candidate codeword passes the CRC,

wherein performing forward and backward traces comprises:

setting 1=1, for 1=1, 2, . . . , L;

setting s′=PreState, s=SuccState, and k=TrellisStep;

determining b k l =b(s′, s);

setting j=k+1, for j=k+1, k+2, . . . , N−1;

setting s′=s;

determining s′=arg{max s [σ j (s′, s)]};

determining b k l =b(s′, s);

incrementing j and returning to the step of setting j=k+1 if j<N−1; otherwise:

setting s=PreState;

setting j=k+1, for j=k+1, k+2, . . . , 0;

determining s′=arg{max s′ [σ j (s′, s)]};

determining b k l =b(s′, s);

setting s=s′; and

incrementing j and returning to the step of setting j=k−1 if j>0; otherwise:

performing Cyclic Redundancy Check (CRC) on l and stopping if l passes the check, otherwise incrementing l and returning to the step of setting s′=PreState, s=SuccState, and k=TrellisStep.

11. The non-transitory computer-readable recording medium of claim 10 , wherein decoding the signal comprises decoding a signal using Maximum-Logarithm Maximum-A-Posteriori decoding.