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

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.

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 bkl=b(s′, s);
• setting j=k+1, for j=k+1, k+2, . . . , N−1;
• setting s′=s;
• determining s′=arg{maxs[σj(s′, s)]};
• determining bkl=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{maxs′[σj(s′, s)]};
• determining bkl=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.