Turbo decoder using parallel processing

• US 20040111659A1
• Filed: 12/06/2002
• Published: 06/10/2004
• Est. Priority Date: 12/06/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Sandbridge Technologies Incorporated (Qualcomm, Inc.)
• Inventors: Lu, Jin, Moudgill, Mayan, Hokenek, Erdem, Chun, Joon-Hwa
• Granted Patent: US 7,055,102 B2
• Time in Patent Office: Days
• US Class Current: 714/755
• CPC Class Codes: H03M 13/296 Particular turbo code structure
• CPC Class Codes: H03M 13/3927 Log-Likelihood Ratio [LLR] computation by combination of forward and backward metrics into LLRs
• CPC Class Codes: H03M 13/6561 Parallelized implementations
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes

Abstract

A method of decoding using a log posterior probability ratio L(u_k), which is a function of forward variable α (.) and backward variable β (.). The method comprises dividing the forward variable α (.) and the backward variable β (.) into, for example, two segments p and q, where p plus q equal the length of the code word U. The forward segments α (.) are parallel calculated, and the backward segments β (.) are parallel calculated. The ratio L(u_k) is calculated using the parallel calculated segments of α (.) and β (.).

Claims

1. A method of a turbo decoder using log A Posteriori Probability L(u_k), where L(u_k)=f(α

_k(s), β

_k(S)), the method comprising;

dividing a forward variable α

(.) and a backward variable β

(.) into a plurality M of parallel segments of size p, q . . . w, where p+q, . . . +w equals the length of a coded word U;

parallel calculating the segments of forward variable α

(.) and backward variable β

(.); and

calculating L(u_k) using the parallel calculated segments of α

(.) and β

(.).

2. The method according to claim 1, wherein

the forward variable segments are calculated as follows:

$\begin{array}{c}{\mathrm{\alpha <br><br>}}_1<br><br>(.),\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\mathrm{\alpha <br><br>}}_p<br><br>(.)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{starting}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{from}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_0<br><br>(.)\\ {\mathrm{\alpha <br><br>}}_{p+1}<br><br>(.),\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\mathrm{\alpha <br><br>}}_q<br><br>(.)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{starting}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{from}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_p<br><br>(.)\\ \text{\hspace{1em}<br><br>}<br><br>\mathrm{⋮<br><br>}\\ {\mathrm{\alpha <br><br>}}_{w+1}<br><br>(.),\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\mathrm{\alpha <br><br>}}_K<br><br>(.)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{starting}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{from}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_w<br><br>(.);<br><br>\end{array}$

and the reverse variable segments are calculated as follows;

$\begin{array}{c}{\mathrm{\beta <br><br>}}_K<br><br>(.),\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\mathrm{\beta <br><br>}}_{w+1}<br><br>(.)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{starting}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{from}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\beta <br><br>}}_K<br><br>(.)\\ {\mathrm{\beta <br><br>}}_w<br><br>(.),\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\mathrm{\beta <br><br>}}_{v+1}<br><br>(.)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{starting}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{from}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\beta <br><br>}}_{w+1}<br><br>(.)\\ \text{\hspace{1em}<br><br>}<br><br>\mathrm{⋮<br><br>}\\ {\mathrm{\beta <br><br>}}_q<br><br>(.),\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},{\mathrm{\beta <br><br>}}_1<br><br>(.)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{starting}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{from}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\beta <br><br>}}_{q+1}<br><br>(.).\end{array}$

3. The method according to claim 2, wherein the starting points α

_p(.), . . . , α

_w(.) are estimated, and the starting points β

_w(.), . . . , β

_q+1(.) are estimated.

4. The method according to claim 3, wherein the starting points for the forward variable are estimated from:

5. The method according to claim 4, wherein d is in the range of 1 to 20.

6. The method according to claim 4, wherein d is in the range of 15 to 20.

7. The method according to claim 4, wherein the starting points for the estimated states are uniform random variables.

8. The method according to claim 4, wherein the starting points for the estimated states are a predetermined state.

9. The method according to claim 4, wherein the starting point for the estimated states is one divided by the number of possible states.

10. The method according to claim 1, wherein the segment sizes are set equal.

11. The method according to claim 1, wherein the variables are divided only into two segments p and q.

19. A signal receiver including a decoder performing the method according to claim 1.

20. A signal receiver including a decoder performing the method according to claim 11.

12. A method of decoding using a log A Posteriori Probability ratio L(u_k) where L(u_k)=f(α

_k(s), β

_k(s) ), the method comprising;

dividing a forward variable α

(.) and a backward variable β

(.) into two segments p and q where p+q equals the length of the code word U;

parallel calculating the forward segments;

α

₁(.), . . . ,α

_p(.) starting from a known α

₀(.) and

α

_p+1(.), . . . ,α

_k(.) starting from an estimated α

_p(.);

parallel calculating the backward segments;

β

_K(.), . . . , β

_q+1(.) starting from a known β

_K(.) and

β

_q(.), . . . , β

₁(.) staring from an estimated β

_q+1(.); and

calculating L(u_k) using the parallel calculated segments of α

(.) and β

(.).

13. A method according to claim 12, wherein the estimated starting point α

_p(.) for α

_p+1(.) is estimated from prior probabilities α

<sub>p−

d+</sub>(.), . . . , α

_p(.), and the estimated starting point β

_q+(.) for β

_q(.) is estimated from prior probabilities β

_q+d(.), . . . , β

_q+1(.).

14. A method according to claim 13, wherein d is in the range of 1 to 20.

15. A method according to claim 13, wherein d is in the range of 15 to 20.

16. A method according to claim 13, wherein the starting points for the estimated states are uniform random variables.

17. A method according to claim 13, wherein the starting points for the estimated states are a predetermined state.

18. A method according to claim 13, wherein the starting point for the estimated states is one divided by the number of possible states.