Method and system for initializing a training period in a turbo decoding device

This application claims the benefit of provisional U.S. Patent Application No. 60/258,974 filed Dec. 29, 2000, to inventors Blankenship et al., herein incorporated by reference in its entirety.

The present invention relates generally to the field of communication systems. In particular, the present invention provides a method of initializing training recursions for iterative decoding.

In a communication system, channel coding schemes may typically be employed for error correction. For instance, turbo codes may be used for reliable communications over a wireless channel. A variety of methods may be employed to decode these channel coding schemes. For example, turbo codes are generally decoded using an iterative decoding technique.

Some iterative decoding techniques process results from an underlying algorithm. For instance, a maximum a posteriori (MAP) algorithm, a variant such as the max-log-MAP or log-MAP, or a similar type of algorithm is generally used to decode a constituent code within a turbo code. The MAP algorithm may be referred to as a decoder. The results from the MAP algorithm, such as output log-likelihood ratios (LLRs), can then be used or modified for further decoding iterations. The MAP algorithm uses forward and backward recursions to update probability metrics and subsequently decode the constituent code. However, the MAP algorithm requires memory proportional to the frame size. In some standards, the frame sizes may reach up to 20,728 bits. Because the memory requirements of the MAP algorithm are proportional to the frame size, the amount of memory necessary to implement the MAP algorithm is a serious concern. For example, for a frame size of 20,728 bits and an eight-state constituent code, 2.65 Mbits of memory is required.

To alleviate these memory requirements, windowing techniques are frequently employed. In conventional windowing techniques, a frame is divided into windows. The MAP algorithm is performed one window at a time and thus only requires an amount of memory proportional to the window size.

However, while memory requirements are reduced, these conventional windowing techniques may not produce results that are as reliable as those produced without windowing. The results are not as reliable because the initial conditions for the forward recursion at the beginning of the window or the backward recursion at the end of the window are unknown, and must be estimated through a training procedure. Training recursions are run forward from a time before the beginning of the window or backward from a time after the end of the window to obtain reliable metric values for the initial conditions at the beginning and end of the window. The training period is often set to 32 or more, which may provide acceptable performance degradation from the un-windowed MAP algorithm.

Because the training is required for each window and the training period is the same for each window, an increase in the complexity of the windowing technique results. In some instances, the training period is equal to the window size. This doubles the complexity of a forward or backward recursion.

Moreover, because the training period is fixed over all signal-to-noise ratios (SNRs) and over all iterations, the training cost remains the same for all decoding iterations, even if the complexity of the iteration differs from that of the previous or subsequent iteration.

It would be desirable therefore to provide a method of initialization that allows near-optimal performance and that reduces the complexity associated with training.

FIG. 1 is a schematic representation of an information burst decoded in accordance with the present invention;

FIG. 2 is a schematic diagram of a frame-length-N trellis in accordance with the present invention;

FIG. 3 is a flow diagram of one embodiment of a method for processing a window in an information burst in accordance with the present invention;

FIG. 4 is a flow diagram of one embodiment of a subroutine of the method shown in FIG. 3 ;

FIG. 5 is a flow diagram of another embodiment of a subroutine of the method shown in FIG. 3 ;

FIG. 6 is a flow diagram of one embodiment of the internal workings of an α recursion block for the k-th window in accordance with the present invention;

FIG. 7 is a flow diagram of one embodiment of the internal workings of a β recursion block for the k-th window in accordance with the present invention; and

FIG. 8 shows a schematic representation of one embodiment of a turbo decoding system in accordance with the present invention.

FIG. 1 shows a schematic representation of an information burst that may be decoded in accordance with one embodiment of the present invention at 100 . The term “burst” appearing herein may refer to a short or isolated transmission, a portion of a longer transmission, a portion of a continuous transmission, a portion of a semi-continuous transmission, a time-limited transmission, a bandwidth-limited transmission, or any combination thereof.

Information burst 100 may include coded or uncoded source information. Information burst 100 may comprise any suitable number of information symbols. Information burst 100 may be transmitted from any suitable transmitting device to any suitable receiving device. For example, information burst 100 may be transmitted from a base station to a wireless cellular device. Alternatively, a cellular device may transmit information burst 100 to a base station.

As seen in FIG. 1 , information burst 100 may be processed with one embodiment of the present invention. In the embodiment of FIG. 1 , information burst 100 has a size of N. Information burst 100 may be divided into two or more windows 110 , 120 , 130 . These windows may be of differing length. Alternatively, as seen in FIG. 1 , the windows 110 , 120 , 130 may have the same length.

Each window 110 , 120 , 130 of information burst 100 may be processed. For example, a window management function may control the processing of each window. In general, the windows may be processed in any order. In one embodiment, all windows are processed simultaneously in parallel. In another embodiment, the windows are processed from the front of information burst 100 to the back of the information burst 100 in sequential order. In yet another embodiment, the windows are processed from the back of information burst 100 to the front of information burst 100 in reverse sequential order.

FIG. 2 is a schematic diagram of a frame-length-N code trellis in accordance with the present invention. Such a diagram may be used, for example, by a decoder to denote the possible states through which the encoder may have passed. One possible decoder may be the MAP algorithm. Alternatively, similar variants of the MAP algorithm may be used. In the diagram of FIG. 2 , there are eight possible states at each step. Alternatively, there may be more or less states for each step. To generate the output of the decoder (such as output LLRs from the MAP algorithm), a typical decoder may compute α probabilities for all states between steps 0 and N−1, inclusive. Alternatively, a typical decoder may compute β probabilities metrics for all states between steps 1 and N, inclusive. When windowing is used, the frame is generally divided into n windows, k=1, . . . ,n, which may have differing lengths. FIG. 2 calls out the k-th window in the frame. In the embodiment of FIG. 2 , the symbols s 0 (k) and s e (k) are used to label the starting and ending steps, respectively, of the k-th window. These labels are referenced to the frame step numbers. From this definition, s 0 (1) may equal zero (0) and s e (n) may equal N, where N is the frame length. Furthermore, by definition s 0 (k+1)=s e (k) and the size of the k-th window, W(k), may be W(k)=s e (k)−s 0 (k). In the following description, the symbol α j (k), j=O, . . . ,W(k), may denote an ordered set of α's at step j of the k-th window. The elements of the set α j (k) are referenced by α j l (k), where l runs from 1 to the cardinality of the set. Also in the following description, the symbol β j (k), j=0, . . . ,W(k), may denote an ordered set of β's at step j of the k-th window. The elements of the set β j (k) are referenced by β j l (k), where l runs from 1 to the cardinality of the set. For example, in the embodiment of FIG. 2 the code has 8 states and the cardinality of the sets α j (k) and β j (k) is 8.

FIG. 3 shows a flow diagram of one embodiment of a method of processing a window in an information burst in accordance with the present invention at 300 . A indicates a period before the processing of a window such as, for example, window k described above. During period A, a window adjacent to window k, such as, for example, window k−1 or window k+1 may be processed. Alternatively, during period A, an information burst 100 may be divided into windows as described above where window k is processed at the same time or before windows k−1 and k+1.

At block 310 , a window is selected for processing. This window may be one of the windows 110 , 120 , 130 in information burst 100 or window k as described above. In one embodiment of the invention, the window may be processed using the algorithm shown below:

L j = ln ⁢ P ⁢ ( u j = + 1 | y ) P ⁢ ( u j = - 1 | y ) = ∑ ( s ′ , s ) u j = + 1 ⁢ p ⁢ ( s ′ , s , y ) ∑ ( s ′ , s ) u j = - 1 ⁢ p ⁢ ( s ′ , s , y ) = ∑ ( s ′ , s ) u j = + 1 ⁢ α j - 1 ⁢ ( s ′ ) ⁢ γ j ⁢ ( s ′ , s ) ⁢ β j ⁢ ( s ) ∑ ( s ′ , s ) u j = - 1 ⁢ α j - 1 ⁢ ( s ′ ) ⁢ γ j ⁢ ( s ′ , s ) ⁢ β j ⁢ ( s ) .

where the quantity p(s′,s,y) may represent a joint probability that a branch of the trellis goes from state s′ to state s during the j-th section of the code trellis and the entire received sequence y (e.g., information burst); L j may represent the output likelihood value at section j of the trellis, and u j may be the j-th information symbol. Because of the underlying Markov nature of the code, this probability may be broken up into a product of three probabilities: past α j−1 (s′)=p(s′,y m<j ), present γ j (s′,s)=p(s,y j |s′), and future β j (s)=p(y m>j |s). The notation y m<j may represent the sequence of symbols whose position within the sequence is less than j. Similarly, the notation Y m>j may represent the sequence of symbols whose position within the sequence is greater than j. The α and β probabilities may be calculated through generalized forward and backward recursions, respectively, on the code trellis.

After selecting a window, metric determinations are made for the α probabilities (α's) for the beginning state α 0 (k) and the β probabilities (β's) for the final state β W(k) (k) of the window as seen at blocks 315 , 320 . Depending upon how the windows are processed, this may be done by copying metrics from adjacent windows or by training.

In one embodiment of the invention, α 0 (k) may be determined through training for windows k=2, . . . ,n for block 315 . Meanwhile, β W(k) (k) may be determined through training for windows k=1, . . . ,n−1 for block 320 . This embodiment may be used, for example, when the windows 110 , 120 , 130 are processed simultaneously in parallel.

In another embodiment of the invention, α 0 (k) may be set to equal to α W(k−1) (k−1) for windows k=2, . . . ,n for block 315 . Meanwhile, β W(k) (k) may be determined through training for windows k=1, . . . ,n−1 for block 320 . This embodiment may be used, for example, when windows 110 , 120 , 130 are processed sequentially from the front to the back of the information burst 100 .

In another embodiment of the invention, α 0 (k) may through training for windows k=2, . . . ,n at block 315 . Meanwhile, β W(k) (k) may be set to equal β 0 (k+1) for windows k=1, . . . ,n−1 at block 320 . This embodiment may be used, for example, when the windows 110 , 120 , 130 are processed reverse sequentially from the back to the front of information burst 100 .

In one embodiment of the invention, determination may occur as shown in FIG. 3 (i.e., α 0 (k) determination followed by β W(k) (k) determination). Alternatively, determination may occur at block 320 followed by determination at block 315 (i.e., β W(k) (k) determination followed by α 0 (k) determination). In another embodiment of the invention, block 315 and block 320 may occur at the same time.

Each metric determination block 315 , 320 may accept inputs. These inputs may be accepted, for example, from a window management function such as described above. For example, metric determination block 315 , 320 may accept F α and/or F β . F α is a flag that may equal 0 when α 0 (k) is determined from the adjacent window and may equal 1 for determination through training. Alternatively, F β is a flag that may equal 0 when β W(k) (k) is determined from the adjacent window and may equal 1 for determination through training.

Metric determination block 315 , 320 may also accept α init (k,i) and/or β init (k,i). α init (k,i) may be an ordered set of metrics that initializes the α training recursion for the k-th window on iteration i. Alternatively, β init (k,i) may be an ordered set of metrics that initializes the β training recursion for the k-th window on iteration i. Note that the elements of the set α init (k,i) (β init (k,i)) may be referenced by α l init (k,i) (β l init (k,i)), for example, where the index l runs from 1 to the cardinality of the set.

Metric determination block 315 , 320 may also accept T α (k) and/or T β (k). T α (k) may be the a training period for the k-th window. T β (k) may be the β training period for the k-th window.

At block 325 , the α's may be computed over the k-th window. During the α recursion over the k-th window, α metrics may be computed that may be used to initialize the α training recursions of windows k′>k on the following iteration. This use of the α metrics computed over a window on the i-th iteration to initialize the training recursions on the (i+1)-st iteration is in accordance with the present invention.

At block 330 , the β's may be computed over the k-th window. During the β recursion over the k-th window, β metrics may be computed that may be used to initialize the β training recursions of windows k′<k on the following iteration. This use of the β metrics computed over a window on the i-th iteration to initialize the training recursions on the (i+1)-st iteration is in accordance with the present invention.

In the embodiment of FIG. 3 , block 325 precedes block 330 . Alternatively, in another embodiment of the invention, block 330 can precede block 325 . In yet another embodiment of the invention, block 325 and block 330 may occur at the same time.

At block 335 , the decoder output, such as LLRs, may be computed over the window. This may accomplished using any suitable method known in the art. Alternatively, the decoder output may be computed within block 330 when block 325 precedes block 330 . In another embodiment, the decoder output may be computed within block 325 when block 330 precedes block 325 .

The procedure for using stored metrics from a previous iteration to initialize a training period that determines the starting recursion state for the window during the current iteration (blocks 315 or 320 ), and storing metrics in a current iteration to initialize a training period in a future iteration (blocks 325 and 330 ) may be described quantitatively. One such embodiment is presented below.

Let the α and β training periods of the k-th window be T α (k) and T β (k), respectively. In general, the α j (k) from iteration i can determine the α init (k′,i+1) when the equation

∑ m = 1 k - 1 ⁢ ⁢ W ⁡ ( m ) + j = s 0 ⁡ ( k ′ ) - T α ⁡ ( k ′ ) Eq . ⁢ ( 1 )

is satisfied, where k′ may represent the index of a window. Similarly, the β j (k) from iteration i may determine the β init (k′,i+1) when the equation

∑ m = 1 k - 1 ⁢ ⁢ W ⁡ ( m ) + j = s e ⁡ ( k ′ ) + T β ⁡ ( k ′ ) Eq . ⁢ ( 2 )

is satisfied. In one embodiment of the invention, since metrics on the i-th iteration may influence the initialization of the training recursions on the (i+1)-st iteration, the quantities s 0 (k′), s e (k′), T α (k′), and T β (k′) are all measured on the (i+1)-st iteration.

In general, the α init (k′,i+1) (β init (k′,i+1)) may be functions of α j (k) (β j ( Previously, the conventional windowing technique uses an equiprobable initialization

α init l ( k,i )=β init l ( k,i )= C, ∀l,k,i,

where C is an arbitrary constant that may be independent of α j (k) (β j (k)).

In one embodiment, one function is a direct assignment, or

α init ( k′,i+ 1)=α j ( k ),  Eq. (3)

for all combinations of j, k, and k′ satisfying Eq. (1) and

β init ( k′,i+ 1)=β j ( k )  Eq. (4)

for all combinations of j, k, and k′ satisfying Eq. (2).

In another embodiment,

α init l ⁡ ( k ′ , i + 1 ) = { Δα min , l = arg ⁢ ⁢ max l ′ ⁢ ⁢ α J l ′ ⁡ ( k ) 0 , l ≠ arg ⁢ ⁢ max l ′ ⁢ ⁢ α J l ′ ⁡ ( k ) , Eq . ⁢ ( 5 )

for all combinations of j, k, and k′ satisfying Eq. (1) and

Δα min = min q ≠ l ⁢  α J l ⁡ ( k ) - α J q ⁡ ( k )  , l = arg ⁢ ⁢ max l ′ ⁢ ⁢ α J l ′ ⁡ ( k ) , and ⁢

⁢ β init l ⁡ ( k ′ , i + 1 ) = { Δβ min , l = arg ⁢ ⁢ ⁢ max l ′ ⁢ ⁢ β J l ′ ⁡ ( k ) 0 , l ≠ arg ⁢ ⁢ ⁢ max l ′ ⁢ ⁢ β J l ′ ⁡ ( k ) , Eq . ⁢ ( 6 )

for all combinations of j, k, and k′ satisfying Eq. (2) and

Δβ min = min q ≠ l ⁢  β J l ⁡ ( k ) - β J q ⁡ ( k )  , l = arg ⁢ ⁢ max l ′ ⁢ ⁢ β J l ′ ⁡ ( k ) ,

where q runs from 1 to the cardinality of the set and l′ runs from 1 to the cardinality of the set.

In yet another embodiment, one function may be used for initializing α init (k′,i+1) while another function initializes β init (k′,i+1). In another embodiment, an initialization function that can be based on α j (k) may be used. In another embodiment, an initialization function that can be based on β j (k) may be used.

One of the benefits of the present invention is that near-optimal performance may be obtained with smaller training periods than required by the conventional windowing technique. This invention may require a modest increase in memory. However, in comparison, this increase may be significantly less than the memory required by the MAP algorithm. Additionally, for some embodiments, there may be a small increase in complexity for computing α init (k′,i+1) and β init (k′,i+1) in comparison to the equiprobable initialization. However, this increase is offset by the savings due to reducing the training period.

FIG. 4 shows a flow diagram of one embodiment of a subroutine in accordance with the present invention at 400 . Routine 400 may be for example a subroutine corresponding to the metric determination block 315 for the k-th window described in FIG. 3 . The subroutine of FIG. 4 may begin, for example, at B in FIG. 4 .

At block 405 , it may be determined whether F α is equal to 1. If F α ≠1, then the metric determination may occur by copying. In one embodiment, α 0 (k) may be set to equal to α W(k−1) (k−1) as seen at block 410 .

If F α =1, then subroutine 400 (e.g., metric determination block 315 ) may also indicate that determination will occur by training. In one embodiment of the invention, the α's at step s 0 (k)-T α (k) are initialized to α init (k,i) as seen at block 415 . This may occur at a point T α (k) steps from the beginning of the window. Then at block 425 , an α recursion may be performed over the T α (k) steps before the initial step of the window up to the initial step of the window.

FIG. 5 shows a flow diagram of one embodiment of a subroutine in accordance with the present invention at 500 . Routine 500 may be, for example, the metric determination block 320 for the k-th window described in FIG. 3 . The subroutine of FIG. 5 may begin, for example, at D in FIG. 5 .

At block 505 , it may be determined whether F β is equal to 1. If F β ≠1, then the metric determination may occur by copying. In one embodiment, β W(k) (k) may be set to equal to β 0 (k+1) as seen at block 510 .

If F β =1, then subroutine 500 (e.g., metric determination block 320 ) may also indicate that determination will occur by training. In one embodiment of the invention, the β's at step s e (k)+T β (k) are initialized to β init (k,i) as seen at block 515 . This may occur at a point T β (k) steps from the end of the window. Then at block 525 , a β recursion may be performed over the T β (k) steps after the final step of the window up to the final step of the window.

FIG. 6 shows a flow diagram of one embodiment of the internal workings of the α recursion block for the k-th window in accordance with the present invention at 600 . In the embodiment shown in FIG. 6 , the α j+1 (k) may be computed recursively from the α j (k) for j=0,1, . . . ,W(k)−1. However, if α 0 (k) determination by training is specified (i.e., F α =1), then whenever Eq. (1) is satisfied, the α j (k) may be used to compute initial values of α training recursions of windows k′>k for the following iteration.

Thus, at block 610 , j may be set to 0 (i.e., j= 0 ). Then at block 615 , it may be determined whether F α is equal to 1 and whether Eq. (1) is satisfied for j. If F α =1 and Eq. (1) is satisfied for j, then as seen at block 620 , α init (k′,i+1) may be computed from α j (k). In one embodiment, block 620 may implement Eq. (3) described above. In another embodiment, block 620 may implement Eq. (5) described above. In yet another embodiment, block 620 may implement a function for α init (k′,i+1) from α j (k). Alternatively, α init (k′,i+1) may be computed using any suitable method known in the art.

At block 625 , α j+1 (k) may be computed from α j (k). This may be accomplished using any suitable method known in the art. The information computed at block 625 may be handled in any suitable manner known in the art. In one embodiment of 625 , the results of block 625 may be stored. In another embodiment, the results of block 625 may be available for computing. For example, the results of block 625 may be used to compute LLRs.

At block 630 , j may be set to j+1 (i.e., j=j+1). Then at block 635 , it may be determined whether j=W(k). If j is equal to W(k), the routine may end. Otherwise, the routine may return to block 615 .

FIG. 7 , shows a flow diagram of one embodiment of the internal workings of the β recursion block for the k-th window in accordance with the present invention at 700 . In the embodiment of FIG. 7 , the β j−1 (k) are computed recursively from the β j (k) for j=W(k),W(k)−1, . . . ,1. However, if β W(k) (k) determination by training is specified (i.e., F β =1), then whenever Eq. (2) is satisfied, the β j (k) may be used to compute initial values of β training recursions of windows k′<k for the following iteration.

Thus, at block 710 , j may be set to W(k) (i.e., j=W(k)). Then at block 715 , it may be determined whether F β is equal to 1 and whether Eq. (2) is satisfied for j.

If F β =1 and Eq. (2) are satisfied for j, then as seen at block 720 , β init (k′,i+1) may be computed from β j (k). In one embodiment, block 720 may implement Eq. (4). In another embodiment, block 720 may implement Eq. (6). In yet another embodiment, block 720 can implement a function for β init (k′,i+1) from β j (k). Alternatively, β init (k′,i+1) may be computed using any suitable method known in the art.

At block 725 , β j−1 (k) may be computed from β j (k). This may be accomplished using any suitable method known in the art. The information computed at block 725 may be handled in any suitable manner known in the art. In one embodiment of 725 , the results of block 725 may be stored. In another embodiment, the results of block 725 may be available for computing. For example, the results of block 725 may be used to compute LLRs.

Next, j may be set to j−1 (i.e., j=j−1) as seen at block 730 . Then at block 735 , it may be determined whether j=0. If j is equal to 0, the routine may end. Otherwise, the routine may return to block 715 .

FIG. 8 shows a schematic representation of a turbo decoding system in accordance with the present invention at 800 . Turbo decoding system 800 may include at least one log-MAP decoder 810 . In the embodiment of FIG. 8 , turbo decoding system 800 also includes a second log-MAP decoder 840 . Alternatively, MAP or MAP variants may be used instead of log-MAP decoders. Turbo decoding system 800 may also include an interleaver 830 and a de-interleaver 850 .

While specific embodiments of the present invention have been shown and described, it will be apparent to those skilled in the art that the disclosed invention may be modified in numerous ways and may assume many embodiments other than those specifically set out and described above. Accordingly, the scope of the invention is indicated in the appended claims, and all changes that come within the meaning and range of equivalents are intended to be embraced therein.