Optimal soft-output decoder for tail-biting trellis codes

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.sub.t, is m and that a sequence of L channel outputs having values Y.sub.1.sup.L ={y.sub.1, . . . , y.sub.1 } is received, as represented by .lambda..sub.t (m)=P{S.sub.t =m, Y.sub.1.sup.L }, said trellis code having M encoder states, said decoder determining L conditional probability matrices .gamma..sub.t, one at each of L trellis levels, the elements of said probability matrices being defined by:

• .gamma..sub.t (ij)=P{state j at time t;
• y.sub.t /state i at time t-1};
• by determining row vectors .alpha..sub.t having M joint probability elements defined by:
• .alpha..sub.t (j)=P{state j at time t;
• y.sub.1, . . . , y.sub.t };
• and by determining column vectors .beta..sub.t having M conditional probability elements defined by:
• .beta..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 .gamma..sub.t calculator for receiving said channel outputs, the channel transition probability R(Y.sub.t, X), the probability p.sub.t (m/m') that the encoder makes a transition from state m' to m at time t, and the probability q.sub.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 .gamma..sub.t therefrom;
• a .alpha..sub.t matrix product calculator for receiving said scalar elements of .gamma..sub.t from said .gamma..sub.t calculator and providing said row vectors .alpha..sub.t ;
• a .beta..sub.t matrix product calculator for providing said column vectors .beta..sub.t ;
• an element-by-element product calculator for forming the joint probability vectors .lambda..sub.t, the elements of which are said joint probabilities .lambda..sub.t (i,j);
• said .alpha..sub.t matrix product calculator, said .beta..sub.t matrix product calculator, and said element-by-element product calculator forming said vectors .alpha..sub.t, .beta..sub.t, and .lambda..sub.t, respectively, by:
• (i.a) starting with an initial .alpha..sub.0 equal to (1/M, . . . , 1/M), calculating L times the forward recursion:
• .alpha..sub.t =.alpha..sub.t-1 .gamma..sub.t, t=1, . . . , L;
• and normalizing the results so that the elements of each .alpha..sub.t sum to unity, retaining all L .alpha..sub.t vectors;
• (i.b) letting .alpha..sub.0 equal .alpha..sub.L from step (i.a) and, starting at t =1, calculating
• .alpha..sub.t =.alpha..sub.t-1 .gamma..sub.t, t=1, . . . , L.sub.w.sbsb.min ;
• where L.sub.w.sbsb.min is a predetermined minimum number of trellis stages;
• normalizing the results so that the elements of each .alpha..sub.t sum to unity, retaining only the most recent set of .alpha..sub.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 .alpha..sub.t =.alpha..sub.t-1 .beta..sub.t, normalizing the results of the recursion so that the elements of each .alpha..sub.t sum to unity, retaining only the most recent set of L .alpha..sub.t 's calculated and this .alpha..sub.t found previously in step (i.a).
• (i.e) comparing the .alpha..sub.t to the most recent, previously-calculated .alpha..sub.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 .beta..sub.L =(1, 1, 1, . . . , 1).sup.T and forming the preceding .beta..sub.t by a backward recursion as follows:
• .beta..sub.t =.gamma..sub.t+1 .beta..sub.t+1, t=L-1, . . . , 1;
• and normalizing the results of the recursion so that the elements of each .beta..sub.t sum to unity, retaining all L .beta..sub.t vectors;
• (iii) forming the joint probability vectors .lambda..sub.t, the elements of which are said joint probabilities .lambda..sub.t, by multiplying the elements of said row vectors by the elements of said column vectors as follows:
• .lambda..sub.t (i)=.alpha..sub.t (i).beta..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 .lambda..sub.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.sup.th of k data bits, and providing a soft output as a function of said probability.

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.sub.t, is m and that a sequence of L channel outputs having values Y.sub.1.sup.L ={y.sub.1, . . . , y.sub.L } is received, as represented by .lambda..sub.t (m)=P{S.sub.t =m;

• Y.sub.1.sup.L }, said trellis code having M encoder states, said decoder determining L conditional probability matrices .gamma..sub.t, one at each of L trellis levels, the elements of said probability matrices being defined by:
• .gamma..sub.t (ij)=P{state j at time t;
• y.sub.t /state i at time t-1};
• by determining row vectors .alpha..sub.t having M joint probability elements defined by:
• .alpha..sub.t (j)=P{state j at time t;
• y.sub.1, . . . , y.sub.t };
• and by determining column vectors .beta..sub.t having M conditional probability elements defined by:
• .beta..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 .gamma..sub.t calculator for receiving said channel outputs, the channel transition probability R(Y.sub.t, X), the probability p.sub.t (m/m') that the encoder makes a transition from state m' to m at time t, and the probability q.sub.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 .gamma..sub.t therefrom;
• a .alpha..sub.t matrix product calculator for receiving said scalar elements of .gamma..sub.t from said .gamma..sub.t calculator and providing said row vectors .alpha..sub.t ;
• a .alpha..sub.t matrix product calculator for providing said column vectors .beta..sub.t ;
• an element-by-element product calculator for forming the joint probability .lambda..sub.t ;
• said .alpha..sub.t matrix product calculator, said .beta..sub.t matrix product calculator, and said element-by-element product calculator forming said vectors .alpha..sub.t, .beta..sub.t, and .lambda..sub.t, respectively, by:
• (i.a) starting with an initial .alpha..sub.0 equal to (1/M, . . . , 1/M), calculating L times the forward recursion:
• .alpha..sub.t =.alpha..sub.t-1 .gamma..sub.t, t=1, . . . , L;
• and normalizing the results so that the elements of each .alpha..sub.t sum to unity, retaining all .alpha..sub.t vectors;
• (i.b) letting .alpha..sub.0 equal .alpha..sub.L from step (i.a) and, starting at t =1, calculating
• .alpha..sub.t =.alpha..sub.t-1 .gamma..sub.t, for t=1, 2, . . . L.sub.w ;
• where the wrap depth L.sub.w is a predetermined number of trellis stages;
• normalizing the results so that the elements of each .alpha..sub.t sum to unity, replacing the .alpha..sub.t calculated in step (i.a) with the .alpha..sub.t calculated in step (i.b) for t=1, 2, . . . , L.sub.w ;
• (ii.a) initializing .beta..sub.L =(1, 1, 1, . . . , 1).sup.T and forming the preceding .beta..sub.t by a backward recursion as follows:
• .beta..sub.t =.gamma..sub.t+1 .beta..sub.t+1, t=L-1, . . . , 1;
• and normalizing the results of the recursion so that the elements of each .beta..sub.t sum to unity, retaining all L .beta..sub.t vectors;
• (ii.b) letting .beta..sub.L+1 equal .beta..sub.1 from step (ii.a) and letting .gamma..sub.L+1, =.gamma..sub.1, starting at t=L, and calculating
• .beta..sub.t =.gamma..sub.t+1 .beta..sub.t+1 for t=L, (L-1), . . . (L-L.sub.w)
• where the wrap depth L.sub.w is a predetermined number of trellis stages;
• normalizing the results of the recursions so that the elements of each .beta..sub.t sum to unity, replacing the .beta..sub.t calculated in step (ii.a) with the .beta..sub.t calculated in step (ii.b) for t=L, (L-1), . . . , L-(L.sub.w +1);
• (iii) forming the joint probability vectors .lambda..sub.t, the elements of which are said joint probabilities .lambda..sub.t (ij), by multiplying the elements of said row vectors by the elements of said column vectors as follows:
• .lambda..sub.t (i)=.alpha..sub.t (i) .beta..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 .lambda..sub.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.sup.th of k data bits, and providing a soft output as a function of said probability.

A method for decoding a tail-biting trellis code generated by an encoder by determining the joint probability that the state of the encoder at time t, S.sub.t, is m and that a sequence of L channel outputs having values Y.sub.1.sup.L ={y.sub.1, . . . , y.sub.L } is received, as represented by .lambda..sub.t (m)=P{S.sub.t =m;

• Y.sub.1.sup.L }, said trellis code having M encoder states, said method comprising steps for determining L probability matrices .gamma..sub.t, one at each of L trellis levels, the elements of said probability matrices being defined by:
• .gamma..sub.t (ij)=P{state j at time t;
• y.sub.t /state i at time t-1};
• and for determining row vectors .alpha..sub.t having M joint probability elements defined by:
• .alpha..sub.t (j)=P{state j at time t;
• y.sub.1, . . . , y.sub.t };
• and for determining column vectors .beta..sub.t having M conditional probability elements defined by:
• .beta..sub.t (j)=P{y.sub.t+1, . . . y.sub.L /state j at time t}
• for j=0, 1, . . . , (M-1), the steps of said method comprising:
• determining the scalar elements of said probability matrices .gamma..sub.t from said channel outputs, the channel transition probability R(Y.sub.t, X), the probability p.sub.t (m/m') that the encoder makes a transition from state m' to m at time t, and the probability q.sub.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;
• computing a matrix product .gamma..sub.1 .gamma..sub.2 . . . .gamma..sub.L from said scalar elements of .gamma..sub.t ;
• computing a normalized eigenvector .alpha..sub.0 corresponding to the largest eigenvalue P{Y.sub.1.sup.L } of said matrix product .gamma..sub.1 .gamma..sub.2 . . . .gamma..sub.L ;
• forming the succeeding .alpha..sub.t by a forward recursion as follows:
• .alpha..sub.t =.alpha..sub.t-1 .gamma..sub.t, t=1, . . . , L;
• providing said column vectors by initializing .beta..sub.L =(1, 1, 1, . . . , 1).sup.T and forming the preceding .beta..sub.t by a backward recursion as follows:
• .beta..sub.t =.gamma..sub.t+1 .beta..sub.t+1, t=L-1, . . . , 1;
• forming the joint probability vectors .lambda..sub.t, the elements of which are said joint probabilities .lambda..sub.t (ij), by multiplying the elements of said row vectors by the elements of said column vectors as follows:
• .lambda..sub.t (i)=.alpha..sub.t (i) .beta..sub.t (i), all i, t=1, . . . , L;
• and
• determining from .lambda.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.sup.th of k data bits, and providing a soft output as a function of said probability.

A method for decoding a tail-biting trellis code generated by an encoder by determining the joint probability that the state of the encoder at time t, S.sub.t, is m and that a sequence of L channel outputs having values Y.sub.1.sup.L ={y.sub.1, . . . , y.sub.L } is received, as represented by .lambda..sub.t (m)=P{S.sub.t =m;

• Y.sub.1.sup.L }, said trellis code having M encoder states, said method comprising steps for determining L probability matrices .gamma..sub.t one at each of L trellis levels, the elements of said probability matrices being defined by:
• .gamma..sub.t (ij)=P{state j at time t-1;
• y.sub.t /state i at time t-1};
• and for determining row vectors .alpha..sub.t having M joint probability elements defined by:
• .alpha..sub.t (j)=P{state j at time t;
• y.sub.1, . . . , y.sub.t };
• and for determining column vectors .beta..sub.t having M conditional probability elements defined by:
• .beta..sub.t (j)=P{y.sub.t+1, . . . y.sub.L /state j at time t}
• for j=0, 1, . . . , (M-1), the steps of said method comprising:
• determining the scalar elements of said probability matrices .gamma..sub.t from said channel outputs, the channel transition probability R(Y.sub.t, X), the probability p.sub.t (m/m') that the encoder makes a transition from state m' to m at time t, and the probability q.sub.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;
• forming said vectors .alpha..sub.t, .beta..sub.t, and .lambda..sub.t, respectively, by:
• (i.a) starting with an initial .alpha..sub.0 equal to (1/M, . . . , 1/M), calculating L times the forward recursion:
• .alpha..sub.t =.alpha..sub.t-1 .gamma..sub.t, t=1, . . . , L;
• and normalizing the results so that the elements of each .alpha..sub.t sum to unity, retaining all L .alpha..sub.t vectors;
• (i.b) letting .alpha..sub.0 equal .alpha..sub.L from step (i.a) and, starting at t =1, calculating
• .alpha..sub.t =.alpha..sub.t-1 .gamma..sub.t, for t=1, 2, . . . , L.sub.w.sbsb.min
• where L.sub.w.sbsb.min is a predetermined minimum number of trellis stages;
• normalizing the results so that the elements of each .alpha..sub.t sum to unity, retaining only the most recent set of L .alpha..sub.t 's found by the recursion in steps (i.a) and (i.b) and the ##EQU18## found in step (i.a);
• (i.c) comparing ##EQU19## from step (i.b) to the ##EQU20## 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 .alpha..sub.t =.alpha..sub.t-1 .gamma..sub.t, normalizing the results of the iteration so that the elements of each .alpha..sub.t sum to unity, retaining only the most recent set of L .alpha.'s calculated and this .alpha..sub.t found previously in step (i.a).
• (i.e) comparing the .alpha..sub.t to the most recent, previously-calculated .alpha..sub.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 .beta..sub.L =(1, 1, 1, . . . , 1).sup.T and forming the preceding .beta..sub.t by a backward recursion as follows:
• .beta..sub.t =.gamma..sub.t+1 .beta..sub.t+1, t=L-1, . . . , 1;
• and normalizing the results of the recursion so that the elements of each .beta..sub.t sum to unity, retaining all L .beta..sub.t vectors;
• (iii) forming the joint probability .lambda..sub.t vectors, the elements of which are said joint probabilities .lambda..sub.t (i, j) by multiplying the elements of said row vectors by the elements of said column vectors as follows:
• .lambda..sub.t (i)=.alpha..sub.t (i) .beta..sub.t (i), all i, t=1, . . . , L;
• and
• determining from .lambda..sub.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.sup.th of k data bits, and providing a soft output as a function of said probability.

A method for decoding a tail-biting trellis code generated by an encoder by determining the joint probability that the state of the encoder at time t, S.sub.t, is m and that a sequence of L channel outputs having values Y.sub.1.sup.L ={y.sub.1, . . . , y.sub.L } is observed, as represented by .lambda..sub.t (m)=P{S.sub.t =m;

• Y.sub.1.sup.L }, said trellis code having M encoder states, said method comprising steps for determining L conditional probability matrices .gamma..sub.t, one at each of L trellis levels, the elements of said probability matrices being defined by:
• .gamma..sub.t (ij)=P{state j at time t;
• y.sub.t /state i at time t-1};
• and for determining row vectors .alpha..sub.t having M joint probability elements defined by:
• .alpha..sub.t (j)=P{state j at time t;
• y.sub.1, . . . , y.sub.t};
• and for determining column vectors .beta..sub.t having M conditional probability elements defined by:
• .beta..sub.t (j)=P{y.sub.t+1, . . . y.sub.L /state j at time t}
• for j=0, 1, . . . , (M-1), the steps of said method comprising:
• determining the scalar elements of said probability matrices .gamma..sub.t from said channel outputs, the channel transition probability R(Y.sub.t, X), the probability p.sub.t (m/m') that the encoder makes a transition from state m' to m at time t, and the probability q.sub.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;
• forming said vectors .alpha..sub.t, .beta..sub.t, and .lambda..sub.t, respectively, by:
• (i.a) starting with an initial .alpha..sub.0 equal to (1/M, . . . , 1/M), calculating L times the forward recursion:
• .alpha..sub.t =.alpha..sub.t-1 .gamma..sub.t, t=1, . . . , L;
• and normalizing the results so that the elements of each .alpha..sub.t sum to unity, retaining all L .alpha..sub.t vectors;
• (i.b) letting .alpha..sub.0 equal .alpha..sub.L from step (i.a) and, starting at t =1, calculating
• .alpha..sub.t =.alpha..sub.t-1 .gamma..sub.t, for t=1, . . . L.sub.w,
• where the wrap depth L.sub.w is a predetermined number of trellis stages;
• normalizing the results so that the elements of each .alpha..sub.t sum to unity, replacing the .alpha..sub.t calculated in step (i.a) with the .alpha..sub.t calculated in step (i.b) for t=1, 2, . . . L.sub.w ;
• (ii.a) initializing .beta..sub.L =(1, 1, 1, . . . , 1).sup.T and forming the preceding .beta..sub.t by a backward recursion as follows:
• .beta..sub.t =.gamma..sub.t+1 .beta..sub.t+1, t=L-1, . . . , 1;
• and normalizing the results of the recursion so that the elements of each .beta..sub.t sum to unity, retaining all L .beta..sub.t vectors;
• (ii.b) letting .beta..sub.L+1 equal .beta..sub.1 from step (ii.a) and letting .gamma..sub.L+1 =.gamma..sub.1, starting at t=L, and calculating
• .beta..sub.t =.gamma..sub.t+1 .beta..sub.t+1, for t=L, (L-1), . . . (L-L.sub.w);
• where the wrap depth L.sub.w is a predetermined number of trellis stages;
• normalizing the results so that the elements of each .beta..sub.t sum to unity, replacing the .beta..sub.t calculated in step (ii.a) with the .beta..sub.t calculated in step (ii.b) for t=L, (L-1), . . . , L-(L.sub.w +1);
• (iii) forming the joint probability .lambda..sub.t vectors, the elements of which are said joint probabilities y.sub.t, by multiplying the elements of said row vectors by the elements of said column vectors as follows:
• .lambda..sub.(i)=.alpha..sub.t (i) .beta..sub.t (i), all i, t=1, . . . , L;
• and
• determining from .lambda..sub.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.sup.th of k data bits, and providing a soft output as a function of said probability.