Optimal soft-output decoder for tail-biting trellis codes

Claim 2

A decoder for a tall-biting trellis code generated by an encoder, which decoder decodes by determining the joint probability that the state of the encoder at time t, S t , is m and that a sequence of L channel outputs having values Y 1 L ={y 1 , . . . , y L } is received, as represented by λ t (m)=P{S t =m; Y 1 L }, said trellis code having M encoder states, said decoder determining L probability matrices γ t , one at each of L trellis levels, the elements of said probability matrices being defined by: γ.sub.t (ij)=P{state j at time t-1; y.sub.t /state i at time t.sub.1 }; by determining row vectors α t having M joint probability elements defined by: α.sub.t (j)=P{state j at time t; y.sub.1, . . . , y.sub.t }; and by determining column vectors β t having M conditional probability elements defined by: β.sub.t (j)=P{y.sub.t+1, . . . y.sub.L /state j at time t} for j=0, 1, . . . , (M-1), said decoder comprising: a γ t calculator for receiving said channel outputs, the channel transition probability R(Y t , X), the probability p t (m/m') that the encoder makes a transition from state m' to m at time t, and the probability q t (X/m', m) that the encoder's output symbol is X given that the previous encoder state is m' and the present encoder state is m, and for determining the scalar elements of said probability matrices γ t therefrom; a γ t matrix product calculator for receiving said scalar elements from said γ t calculator and computing a matrix product γ 1 γ 2 . . . γ L therefrom; a normalized eigenvector computer for receiving said matrix product γ 1 γ 2 . . . γ L and computing a normalized eigenvector α 0 corresponding to the largest eigenvalue P{Y 1 L } of said matrix product; a α t matrix product calculator for receiving said normalized eigenvector α 0 and forming the succeeding α t by a forward recursion as follows: α.sub.t =α.sub.t-1 γ.sub.t, t=1, . . . , L; memory for storing said probability matrices γ t and said row vectors α t ; a β t matrix product calculator for providing said column vectors by initializing β L =(1, 1, 1, . . . , 1) T and forming the preceding β t by a backward recursion as follows: β.sub.t =γ.sub.t+1 β.sub.t+1, t=L-1, . . . , 1; an element-by-element product calculator for forming the joint probability vectors λt, the elements of which are said joint probabilities λ t (ij), by multiplying the elements of said row vectors by the elements of said column vectors as follows: λ.sub.t (i)=α.sub.t (i) β.sub.t (i), all i, t=1, . . . , L; and a decoded bit value probability calculator for determining from λ t the probability that a given data bit inputted to the encoder at time=t is equal to zero, the data bit being the m th of k data bits, and providing a soft output as a function of said probability.

Claim 3

The decoder of claim 1, further comprising a threshold decision device for receiving the probability that the data bit inputted to the encoder at time=t is equal to zero and for implementing a decision rule to provide decoded output bits therefrom.

Claim 4

The decoder of claim 1 wherein said tail-biting trellis code comprises a convolutional code.

Claim 5

The decoder of claim 1 comprising a bounded distance decoder.

Claim 6

A decoder for a tail-biting trellis code generated by an encoder, which decoder decodes by determining the joint probability that the state of the encoder at time t, S t , is m and that a sequence of L channel outputs having values Y 1 L ={y 1 , . . . , y 1 } is received, as represented by λ t (m)=P{S t =m, Y 1 L }, said trellis code having M encoder states, said decoder determining L conditional probability matrices γ t , one at each of L trellis levels, the elements of said probability matrices being defined by: γ.sub.t (ij)=P{state j at time t; y.sub.t /state i at time t-1}; by determining row vectors α t having M joint probability elements defined by: α.sub.t (j)=P{state j at time t; y.sub.1, . . . , y.sub.t }; and by determining column vectors β t having M conditional probability elements defined by: β.sub.t (j)=P{y.sub.t+1, . . . y.sub.L /state j at time t} for j=0, 1, . . . , (M-1), said decoder comprising: a γ t calculator for receiving said channel outputs, the channel transition probability R(Y t , X), the probability p t (m/m') that the encoder makes a transition from state m' to m at time t, and the probability q t (X/m', m) that the encoder's output symbol is X given that the previous encoder state is m' and the present encoder state is m, and for determining the scalar elements of said probability matrices γ t therefrom; a α t matrix product calculator for receiving said scalar elements of γ t from said γ t calculator and providing said row vectors α t ; a β t matrix product calculator for providing said column vectors β t ; an element-by-element product calculator for forming the joint probability vectors λ t , the elements of which are said joint probabilities λ t (i,j); said α t matrix product calculator, said β t matrix product calculator, and said element-by-element product calculator forming said vectors α t , β t , and λ t , respectively, by: (i.a) starting with an initial α 0 equal to (1/M, . . . , 1/M), calculating L times the forward recursion: α.sub.t =α.sub.t-1 γ.sub.t, t=1, . . . , L; and normalizing the results so that the elements of each α t sum to unity, retaining all L α t vectors; (i.b) letting α 0 equal α L from step (i.a) and, starting at t =1, calculating α.sub.t =α.sub.t-1 γ.sub.t, t=1, . . . , L.sub.w.sbsb.min ; where L w .sbsb.min is a predetermined minimum number of trellis stages; normalizing the results so that the elements of each α t sum to unity, retaining only the most recent set of α t 's found by the recursion in steps (i.a) and (i.b) and the ##EQU15## found in step (i.a); (i.c) comparing ##EQU16## from step (i.b) to the ##EQU17## found in step (i.a) and proceeding to step (ii) if within a tolerance range; otherwise, continuing to step (i.d); (i.d) letting t=t+1 and calculating α t =α t-1 β t , normalizing the results of the recursion so that the elements of each α t sum to unity, retaining only the most recent set of L α t 's calculated and this α t found previously in step (i.a). (i.e) comparing the α t to the most recent, previously-calculated α t from steps (i.a), (i.b) and (i.d) and proceeding to step (ii) if within a tolerance range, continuing with step (i.d) if the two most recent vectors do not agree to within said tolerance range and if the number of recursions does not exceed a predetermined maximum; proceeding to step (ii) otherwise; (ii) initializing β L =(1, 1, 1, . . . , 1) T and forming the preceding β t by a backward recursion as follows: β.sub.t =γ.sub.t+1 β.sub.t+1, t=L-1, . . . , 1; and normalizing the results of the recursion so that the elements of each β t sum to unity, retaining all L β t vectors; (iii) forming the joint probability vectors λ t , the elements of which are said joint probabilities λ t , by multiplying the elements of said row vectors by the elements of said column vectors as follows: λ.sub.t (i)=α.sub.t (i)β.sub.t (i), all i, t=1, . . . , L; memory for storing said probability matrices and said row vectors; and a decoded bit value probability calculator for determining from λ t the probability that a given data bit inputted to the encoder at time=t is equal to zero, the data bit being the m th of k data bits, and providing a soft output as a function of said probability.

Claim 7

A decoder for a tail-biting trellis code generated by an encoder, which decoder decodes by determining the joint probability that the state of the encoder at time t, S t , is m and that a sequence of L channel outputs having values Y 1 L ={y 1 , . . . , y 1 } is received, as represented by λ t (m)=P{S t =m, Y 1 L }, said trellis code having M encoder states, said decoder determining L conditional probability matrices γ t , one at each of L trellis levels, the elements of said probability matrices being defined by: γ.sub.t (ij)=P{state j at time t; y.sub.t /state i at time t-1}; by determining row vectors α t having M joint probability elements defined by: α.sub.t (j)=P{state j at time t; y.sub.1, . . . , y.sub.t }; and by determining column vectors β t having M conditional probability elements defined by: β.sub.t (j)=P{y.sub.t+1, . . . y.sub.L /state j at time t} for j=0, 1, . . . , (M-1), said decoder comprising: a γ t calculator for receiving said channel outputs, the channel transition probability R(Y t , X), the probability p t (m/m') that the encoder makes a transition from state m' to m at time t, and the probability q t (X/m', m) that the encoder's output symbol is X given that the previous encoder state is m' and the present encoder state is m, and for determining the scalar elements of said probability matrices γ t therefrom; a α t matrix product calculator for receiving said scalar elements of γ t from said γ t calculator and providing said row vectors α t ; a β t matrix product calculator for providing said column vectors β t ; an element-by-element product calculator for forming the joint probability vectors λ t , the elements of which are said joint probabilities λ t (i,j); said α t matrix product calculator, said β t matrix product calculator, and said element-by-element product calculator forming said vectors α t , β t , and λ t , respectively, by: (i.a) starting with an initial α 0 equal to (1/M, . . . , 1/M), calculating L times the forward recursion: α.sub.t =α.sub.t-1 γ.sub.t, t=1, . . . , L; and normalizing the results so that the elements of each α t sum to unity, retaining all L α t vectors; (i.b) letting α 0 equal α L from step (i.a) and, starting at t =1, calculating α.sub.t =α.sub.t-1 γ.sub.t, t=1, . . . , L.sub.w.sbsb.min ; where L w .sbsb.min is a predetermined minimum number of trellis stages; normalizing the results so that the elements of each α t sum to unity, retaining only the most recent set of α t 's found by the recursion in steps (i.a) and (i.b) and the ##EQU15## found in step (i.a); (i.c) comparing ##EQU16## from step (i.b) to the ##EQU17## found in step (i.a) and proceeding to step (ii) if within a tolerance range; otherwise, continuing to step (i.d); (i.d) letting t=t+1 and calculating α t =α t-1 β t , normalizing the results of the recursion so that the elements of each α t sum to unity, retaining only the most recent set of L α t 's calculated and this α t found previously in step (i.a). (i.e) comparing the α t to the most recent, previously-calculated α t from steps (i.a), (i.b) and (i.d) and proceeding to step (ii) if within a tolerance range, continuing with step (i.d) if the two most recent vectors do not agree to within said tolerance range and if the number of recursions does not exceed a predetermined maximum; proceeding to step (ii) otherwise; (ii) initializing β L =(1, 1, 1, . . . , 1) T and forming the preceding β t by a backward recursion as follows: β.sub.t =γ.sub.t+1 β.sub.t+1, t=L-1, . . . , 1; and normalizing the results of the recursion so that the elements of each β t sum to unity, retaining all L β t vectors; (iii) forming the joint probability vectors λ t , the elements of which are said joint probabilities λ t , by multiplying the elements of said row vectors by the elements of said column vectors as follows: λ.sub.t (i)=α.sub.t (i)β.sub.t (i), all i, t=1, . . . , L; memory for storing said probability matrices and said row vectors; and a decoded bit value probability calculator for determining from λ t the probability that a given data bit inputted to the encoder at time=t is equal to zero, the data bit being the m th of k data bits, and providing a soft output as a function of said probability.

Claim 8

The decoder of claim 5, further comprising a threshold decision device for receiving the probability that the data bit inputted to the encoder at time=t is equal to zero and for implementing a decision rule to provide decoded output bits therefrom.

Claim 9

The decoder of claim 5 wherein said tail-biting trellis code comprises a convolutional code.

Claim 10

The decoder of claim 5 comprising a bounded distance decoder.

Claim 11

The decoder of claim 5 wherein the encoder encodes a block of data bits, said data bits being grouped into k-bit symbols for encoding, the predetermined maximum number of recursions comprising two times the number of k-bit input symbols in a block of data bits.

Claim 12

A decoder for a tail-biting trellis code generated by an encoder, which decoder decodes by determining the joint probability that the state of the encoder at time t, S t , is m and that a sequence of L channel outputs having values Y 1 L ={y 1 , . . . , y L } is received, as represented by λ t (m)=P{S t =m; Y 1 L }, said trellis code having M encoder states, said decoder determining L conditional probability matrices γ t , one at each of L trellis levels, the elements of said probability matrices being defined by: γ.sub.t (ij)=P{state j at time t; y.sub.t /state i at time t-1}; by determining row vectors α t having M joint probability elements defined by: α.sub.t (j)=P{state j at time t; y.sub.1, . . . , y.sub.t }; and by determining column vectors β t having M conditional probability elements defined by: β.sub.t (j)=P{y.sub.t+1, . . . y.sub.L /state j at time t} for j=0, 1, . . . , (M-1), said decoder comprising: a γ t calculator for receiving said channel outputs, the channel transition probability R(Y t , X), the probability p t (m/m') that the encoder makes a transition from state m' to m at time t, and the probability q t (X/m', m) that the encoder's output symbol is X given that the previous encoder state is m' and the present encode state is m, and for determining the scalar elements of said probability matrices γ t therefrom; a α t matrix product calculator for receiving said scalar elements of γ t from said γ t calculator and providing said row vectors α t ; a α t matrix product calculator for providing said column vectors β t ; an element-by-element product calculator for forming the joint probability λ t ; said α t matrix product calculator, said β t matrix product calculator, and said element-by-element product calculator forming said vectors α t , β t , and λ t , respectively, by: (i.a) starting with an initial α 0 equal to (1/M, . . . , 1/M), calculating L times the forward recursion: α.sub.t =α.sub.t-1 γ.sub.t, t=1, . . . , L; and normalizing the results so that the elements of each α t sum to unity, retaining all α t vectors; (i.b) letting α 0 equal α L from step (i.a) and, starting at t =1, calculating α.sub.t =α.sub.t-1 γ.sub.t, for t=1, 2, . . . L.sub.w ; where the wrap depth L w is a predetermined number of trellis stages; normalizing the results so that the elements of each α t sum to unity, replacing the α t calculated in step (i.a) with the α t calculated in step (i.b) for t=1, 2, . . . , L w ; (ii.a) initializing β L =(1, 1, 1, . . . , 1) T and forming the preceding β t by a backward recursion as follows: β.sub.t =γ.sub.t+1 β.sub.t+1, t=L-1, . . . , 1; and normalizing the results of the recursion so that the elements of each β t sum to unity, retaining all L β t vectors; (ii.b) letting β L+1 equal β 1 from step (ii.a) and letting γ L+1 , =γ 1 , starting at t=L, and calculating β.sub.t =γ.sub.t+1 β.sub.t+1 for t=L, (L-1), . . . (L-L.sub.w) where the wrap depth L w is a predetermined number of trellis stages; normalizing the results of the recursions so that the elements of each β t sum to unity, replacing the β t calculated in step (ii.a) with the β t calculated in step (ii.b) for t=L, (L-1), . . . , L-(L w +1); (iii) forming the joint probability vectors λ t , the elements of which are said joint probabilities λ t (ij), by multiplying the elements of said row vectors by the elements of said column vectors as follows: λ.sub.t (i)=α.sub.t (i) β.sub.t (i), all i, t=1, . . . , L; memory for storing said probability matrices and said row vectors; and a decoded bit value probability calculator for determining from λ t the probability that a given data bit inputted to the encoder at time=t is equal to zero, the data bit being the m th of k data bits, and providing a soft output as a function of said probability.

Claim 13

A decoder for a tail-biting trellis code generated by an encoder, which decoder decodes by determining the joint probability that the state of the encoder at time t, S t , is m and that a sequence of L channel outputs having values Y 1 L ={y 1 , . . . , y L } is received, as represented by λ t (m)=P{S t =m; Y 1 L }, said trellis code having M encoder states, said decoder determining L conditional probability matrices γ t , one at each of L trellis levels, the elements of said probability matrices being defined by: γ.sub.t (ij)=P{state j at time t; y.sub.t /state i at time t-1}; by determining row vectors α t having M joint probability elements defined by: α.sub.t (j)=P{state j at time t; y.sub.1, . . . , y.sub.t }; and by determining column vectors β t having M conditional probability elements defined by: β.sub.t (j)=P{y.sub.t+1, . . . y.sub.L /state j at time t} for j=0, 1, . . . , (M-1), said decoder comprising: a γ t calculator for receiving said channel outputs, the channel transition probability R(Y t , X), the probability p t (m/m') that the encoder makes a transition from state m' to m at time t, and the probability q t (X/m', m) that the encoder's output symbol is X given that the previous encoder state is m' and the present encode state is m, and for determining the scalar elements of said probability matrices γ t therefrom; a α t matrix product calculator for receiving said scalar elements of γ t from said γ t calculator and providing said row vectors α t ; a α t matrix product calculator for providing said column vectors β t ; an element-by-element product calculator for forming the joint probability λ t ; said α t matrix product calculator, said β t matrix product calculator, and said element-by-element product calculator forming said vectors α t , β t , and λ t , respectively, by: (i.a) starting with an initial α 0 equal to (1/M, . . . , 1/M), calculating L times the forward recursion: α.sub.t =α.sub.t-1 γ.sub.t, t=1, . . . , L; and normalizing the results so that the elements of each α t sum to unity, retaining all α t vectors; (i.b) letting α 0 equal α L from step (i.a) and, starting at t =1, calculating α.sub.t =α.sub.t-1 γ.sub.t, for t=1, 2, . . . L.sub.w ; where the wrap depth L w is a predetermined number of trellis stages; normalizing the results so that the elements of each α t sum to unity, replacing the α t calculated in step (i.a) with the α t calculated in step (i.b) for t=1, 2, . . . , L w ; (ii.a) initializing β L =(1, 1, 1, . . . , 1) T and forming the preceding β t by a backward recursion as follows: β.sub.t =γ.sub.t+1 β.sub.t+1, t=L-1, . . . , 1; and normalizing the results of the recursion so that the elements of each β t sum to unity, retaining all L β t vectors; (ii.b) letting β L+1 equal β 1 from step (ii.a) and letting γ L+1 , =γ 1 , starting at t=L, and calculating β.sub.t =γ.sub.t+1 β.sub.t+1 for t=L, (L-1), . . . (L-L.sub.w) where the wrap depth L w is a predetermined number of trellis stages; normalizing the results of the recursions so that the elements of each β t sum to unity, replacing the β t calculated in step (ii.a) with the β t calculated in step (ii.b) for t=L, (L-1), . . . , L-(L w +1); (iii) forming the joint probability vectors λ t , the elements of which are said joint probabilities λ t (ij), by multiplying the elements of said row vectors by the elements of said column vectors as follows: λ.sub.t (i)=α.sub.t (i) β.sub.t (i), all i, t=1, . . . , L; memory for storing said probability matrices and said row vectors; and a decoded bit value probability calculator for determining from λ t the probability that a given data bit inputted to the encoder at time=t is equal to zero, the data bit being the m th of k data bits, and providing a soft output as a function of said probability.

Claim 14

The decoder of claim 10, further comprising a threshold decision device for receiving the probability that the data bit inputted to the encoder at time=t is equal to zero and for implementing a decision rule to provide decoded output bits therefrom.

Claim 15

The decoder of claim 10 wherein said tail-biting trellis code comprises a convolutional code.

Claim 16

The decoder of claim 10 comprising a bounded distance decoder.

Claim 17

The decoder of claim 10 wherein the encoder encodes a block of data bits, said data bits being grouped into k-bit symbols for encoding, the predetermined maximum number of recursions comprising two times the number of k-bit input symbols in a block of data bits.

Claim 20

The method of claim 15, further comprising the step of implementing a decision role to provide decoded output bits from the probability that the dam bit inputted to the encoder at time=t is equal to zero.

Claim 21

The method of claim 15 wherein said tail-biting trellis code comprises a convolutional code.

Claim 24

The method of claim 18 further comprising the step of implementing a decision rule to provide decoded output bits from the probability that the dam bit inputted to the encoder at time=t is equal to zero.

Claim 25

The method of claim 18 wherein said tail-biting trellis code comprises a convolutional code.

Claim 26

The method of claim 18 wherein the encoder encodes a block of data bits, said dam bits being grouped into k-bit symbols for encoding, the predetermined maximum number of recursions comprising two times the number of k-bit input symbols in a block of data bits.

Claim 29

The method of claim 22, further comprising the step of implementing a decision rule to provide decoded output bits from the probability that the data bit inputted to the encoder at time =t is equal to zero.

Claim 30

The method of claim 22 wherein said tail-biting trellis code comprises a convolutional code.

Claim 31

The method of claim 22 wherein the encoder encodes a block of data bits, said data bits being grouped into k-bit symbols for encoding, the predetermined maximum number of recursions comprising two times the number of k-bit input symbols in a block of data bits.