Methods and Apparatuses for Parallel Decoding and Data Processing of Turbo Codes
Methods and apparatuses for parallel decoding and data processing of Turbo codes are provided. The method includes: a codeword dividing step for dividing a whole codeword into Q sub-blocks to form a plurality of boundaries between adjacent sub-blocks of the Q sub-blocks so as to decode the Q sub-blocks, wherein the decoding process comprises P times of decoding iterations, and wherein Q is a positive integer and Q>1 and P is a positive integer and P>1; and a boundary moving step for moving at least one position of the boundaries formed in a pth decoding iteration by an offset Δ before performing a (p+n)th decoding iteration, wherein p is a positive integer and 1≦p<P, n is a positive integer and 1≦n<P−p, and the offset Δ is set as a fixed step size.
1 . A method for parallel decoding and data processing of Turbo codes, comprising:
a codeword dividing step for dividing a whole codeword into Q sub-blocks to form a plurality of boundaries between adjacent sub-blocks of the Q sub-blocks so as to decode the Q sub-blocks, wherein the decoding process comprises P times of decoding iterations, and wherein Q is a positive integer and Q>1 and P is a positive integer and P>1; and
a boundary moving step for moving at least one position of the boundaries formed in a pth decoding iteration by an offset Δ before performing a (p+n)th decoding iteration, wherein p is a positive integer and 1≦p<P, n is a positive integer and 1≦n<P−p, and the offset Δ is set as a fixed step size.
2 . The parallel decoding and data processing method as claimed in claim 1 , wherein the codeword dividing step further comprises:
an overlapping step for overlapping adjacent sub-blocks of the Q sub-blocks so that an effective data length M of the qth sub-block is kept unchanged, and overlap lengths of the qth sub-block with the (q−1)th sub-block and the (q+1)th sub-block are respectively equal to L, wherein L≧0, 2≦q≦Q−1, and q is a positive integer.
3 . The parallel decoding and data processing method as claimed in claim 2 , wherein a start point of a forward processing procedure of the qth sub-block during the pth decoding iteration relates to a product of M and q and a product of L and q, and a start point of a backward processing procedure of the qth sub-block during the pth decoding iteration relates to a product of q and a sum of M and L, and wherein when all of the boundaries are moved in the (p+n)th decoding iteration, the start point of the forward processing procedure of the qth sub-block by the offset Δ is moved during the (p+n)th decoding iteration, and the start point of the backward processing procedure of the qth sub-block by the offset Δ is moved during the (p+n)th decoding iteration.
4 . The parallel decoding and data processing method as claimed in claim 3 , wherein a start point of a forward or backward processing procedure of a q′th sub-block is k where 1≦q′≦Q, and q′ is an integer, further comprising:
a storing step for storing an index of a state (s*) of a maximum probability of the calculation results of the forward processing procedure or backward processing procedure of a p′th decoding iteration for the q′th sub-block during the p′th decoding iteration, wherein when an initial condition (s) is with the state of the maximum probability in the forward processing or backward processing procedure of a (p′+1)th decoding iteration for the q′th sub-block, a reliability of the initial condition (s) is 0, wherein p′ is a positive integer and 1≦p′<P.
5 . The parallel decoding and data processing method as claimed in claim 4 , wherein the storing step further comprises:
when the initial condition (s) is not compliant with the state of the maximum probability (s*), that is s≠s*, the initial condition relates to a difference between a reliability of the state (s*) of the maximum probability and a reliability of a state (s′) of a second highest probability.
6 . A method for parallel decoding and data processing of Turbo codes, comprising:
a codeword dividing step for dividing a whole codeword into Q sub-blocks to form a plurality of boundaries between adjacent sub-blocks of the Q sub-blocks so as to decode the Q sub-blocks, wherein the decoding process comprises P times of decoding iterations, and wherein Q is a positive integer and Q>1 and P is a positive integer and P>1; and
a storing step for storing an index of a state (s*) of a maximum probability of the calculation results of a forward processing or a backward processing procedure of a pth decoding iteration for the qth sub-block during the pth decoding iteration, wherein when an initial condition (s) is with the state of the maximum probability in the forward processing or backward processing procedure of a (p+1)th decoding iteration for the qth sub-block, a reliability of the initial condition (s) is 0, wherein a start point of the forward or the backward processing procedure of the qth sub-block is k, where 1≦q≦Q, and q′ is an integer, and p is a positive integer and 1≦p<P.
7 . A method for parallel decoding and data processing of Turbo codes, comprising:
a codeword dividing step for dividing a whole codeword into Q sub-blocks to form a plurality of boundaries between adjacent sub-blocks of the Q sub-blocks so as to decode the Q sub-blocks, wherein the decoding process comprises P times of decoding iterations, and wherein Q is a positive integer and Q>1 and P is a positive integer and P>1; and
a storing step for storing an index of a state (s*) of a maximum probability of the calculation results of a forward processing or a backward processing procedure of a pth decoding iteration for the qth sub-block during the pth decoding iteration, wherein when an initial condition (s) in a forward processing or a backward processing procedure of a (p+1)th decoding iteration for the qth sub-block is not compliant with the state of the maximum probability (s*), that is s≠s*, the initial condition relates to a difference between a reliability of the state (s*) of the maximum probability and a reliability of a state (s′) of a second highest probability.
8 . The parallel decoding and data processing method as claimed in claim 6 or 7 , wherein the codeword dividing step further comprises:
an overlapping step for overlapping adjacent sub-blocks of the Q sub-blocks so that an effective data length M of the qth sub-block is kept unchanged, and overlap lengths of the qth sub-block with the (q−1)th sub-block and the (q+1)th sub-block are respectively equal to L, wherein L≧0, 2≦q≦Q−1, and q is a positive integer.
9 . An apparatus for parallel decoding and data processing of Turbo codes, comprising:
a codeword dividing device dividing a whole codeword into Q sub-blocks to form a plurality of boundaries between adjacent sub-blocks of the Q sub-blocks so as to decode the Q sub-blocks, wherein the decoding process comprises P times of decoding iterations, and wherein Q is a positive integer and Q>1 and P is a positive integer and P>1; and
a boundary moving device moving at least one position of the boundaries formed in a pth decoding iteration by an offset Δ before performing a (p+n)th decoding iteration, wherein p is a positive integer and 1≦p<P, n is a positive integer and 1≦n<P−p, and the offset Δ is set as a fixed step size.
10 . The parallel decoding and data processing apparatus as claimed in claim 9 , wherein the codeword dividing device further comprises:
an overlapping device overlapping adjacent sub-blocks of the Q sub-blocks so that an effective data length M of the qth sub-block is kept unchanged, and overlap lengths of the qth sub-block with the (q−1)th sub-block and the (q+1 )th sub-block are respectively equal to L, wherein L≧0, 2≦q≦Q−1, and q is a positive integer.
11 . The parallel decoding and data processing apparatus as claimed in claim 10 , wherein a start point of a forward processing procedure of the qth sub-block during the pth decoding iteration relates to a product of M and q and a product of L and q, and a start point of a backward processing procedure of the qth sub-block during the pth decoding iteration relates to a product of q and a sum of M and L, and wherein when all of the boundaries are moved in the (p+n)th decoding iteration, the start point of the forward processing procedure of the qth sub-block by the offset Δ is moved during the (p+n)th decoding iteration, and the start point of the backward processing procedure of the qth sub-block by the offset Δ is moved during the (p+n)th decoding iteration.
12 . The parallel decoding and data processing apparatus as claimed in claim 11 , wherein a start point of a forward or backward processing procedure of a q′th sub-block is k, where 1≦q′≦Q, and q′ is an integer, further comprising:
a storing device for storing an index of a state (s*) of a maximum probability of the calculation results of the forward processing or backward processing procedure of a p′th decoding iteration for the q′th sub-block during the p′th decoding iteration, wherein when an initial condition (s) is with the state of the maximum probability in the forward processing or backward processing procedure of a (p′+1)th decoding iteration for the q′th sub-block, a reliability of the initial condition (s) is 0, wherein p′ is a positive integer and 1≦p′<P.
13 . The parallel decoding and data processing apparatus as claimed in claim 12 , wherein the storing device further comprises:
when the initial condition (s) is not compliant with the state of the maximum probability (s*), that is s≠s*, the initial condition relates to a difference between a reliability of the state (s*) of the maximum probability and a reliability of a state (s′) of a second highest probability.
14 . An apparatus for parallel decoding and data processing of Turbo codes, comprising:
a parallel decoding and data processing device for receiving input data, comprising:
a codeword dividing device dividing a whole codeword into Q sub-blocks to form a plurality of boundaries between adjacent sub-blocks of the Q sub-blocks so as to decode the Q sub-blocks, wherein the decoding process comprises P times of decoding iterations, and wherein Q is a positive integer and Q>1 and P is a positive integer and P>1; and
a boundary moving device moving at least one position of the boundaries formed in a pth decoding iteration by an offset Δ before performing a (p+n)th decoding iteration, wherein p is a positive integer and 1≦p<P, n is a positive integer and 1≦n<P−p, and the offset Δ is set as a fixed step size;
a Turbo code decoding device coupled to the parallel decoding and data processing device and receiving decoded data of the sub-blocks, wherein the Turbo code decoding device comprises a plurality of interleavers and a plurality of de-interleavers to Turbo decode the decoded data of the sub-blocks generated by the parallel decoding and data processing device; and
a storing device coupled to the parallel decoding and data processing device and the Turbo code decoding device for storing the input data and decoded results.