Method for a maximum likelihood decoding of a convolutional code with decision weighting, and corresponding decoder

• US 5,406,570 A
• Filed: 04/16/1992
• Issued: 04/11/1995
• Est. Priority Date: 04/23/1991
• Status: Expired due to Term

• Current Assignee: Orange S.A., Telediffusion De France SA
• Original Assignee: France Telecom Telediffusion de France SA
• Inventors: Berrou, Claude, Adde, Patrick
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Decady, Albert
• Application Number:
  US07/870,483
• Time in Patent Office: 1,090 Days
• Field of Search: 371/43, 371/44, 371/45, 371/37.1, 371/46, 375/94, 375/75
• US Class Current: 714/792
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/4153 two-step SOVA decoding, i.e. the soft-output is determined by a second traceback operation after the determination of the hard decision like in the Berrou decoder

Abstract

A method for the decoding of digital data obtained according to a convolutional coding and transmitted on a noise-ridden channel aimed at improving the methods of maximum likelihood decoding such as the Viterbi algorithm consisting in associating, with each estimation s(t) of the corresponding source digital element a(t), a weighting coefficient m(t) representing the reliability of the estimation s(t), the estimation s(t) taking account of the values of a first series of L received samples, and the weighting m(t) taking account of the values of a second series of N samples received, N being strictly greater than L. In a preferred embodiment, a second trellis is associated with the standard first decoding trellis, a trace-back being done in the second trellis on two concurrent paths, used to revise the weighting coefficients obtained at output of the first trellis.

Claims

1. A method for maximum likelihood decoding of a digital signal transmitted in the presence of noise using reduced storage and processing means providing for improved weighting, the method comprising the steps of

receiving at a receiver a sequence of received samples R(t) corresponding to a convolutional coding of a source digital elements a(t) of a signal transmitted in the presence of noise,

estimating an estimation value s(t) of each of said source digital elements a(t) taking account of a first series of L received samples, including said received sample R(t) corresponding to said source digital element a(t) and the following L-1 received samples R(t+1), . . . ,R(t+L-1), L being an integer strictly greater than 1,

computing a weighting coefficient m(t) representing reliability of said estimation value s(t), taking account of a second series of N received samples, comprising said received sample R(t) corresponding to said source digital element a(t) and the following N-1 received samples R(t+1), . . . , R(t+L-1), . . . , R(t+N-1), N being an integer strictly greater than L, and

associating with each of said received Sample R(t) said estimation value s(t) along with said weighting coefficient m(t) to identify at the receiver the most likely coding of the source digital elements a (t).

2. A method according to claim 1, further comprising a step of revising, at each instant of reception t, each of the weighting coefficients m(t-N) to m(t-L-1), corresponding to the N-L last estimation values s(t-N) to s(t-L-1), as a function of the received sample R(t).

3. A method according to claim 2, comprising the step of

using a decision algorithm of the Viterbi algorithm type to arrive at the estimation value s(t), said decision algorithm defining a first trellis T(2.sup.ν

,L) of the possible states of the coding, including a set of nodes, organized in L depth levels, of 2.sup.ν

nodes, L being the number of received samples R(t-L-1), . . . , R(t) taken into account for the estimation value s(t), and 2.sup.ν

being the number of possible states of the convolutional code at a given instant, ν

being the constraint length of the code used for the coding, each of said nodes of a given depth level i corresponding to a given instant of reception and being connected to two nodes of the preceding depth level i-1, corresponding to the preceding instant of reception, by means of two paths, each path corresponding to a possible transition according to said convolutional code, wherein said estimating step comprises the steps of;

determining, for each node of said first trellis, two cumulated distances M⁰ and M¹ respectively corresponding to each of said two paths corresponding to a possible transition;

selecting, for each node of said first trellis, the path having the smaller of the cumulated distances M⁰ and M¹, called the survivor path;

eliminating, from said first trellis, the path having the greater of the cumulated distances M⁰ and M¹, called the concurrent path;

tracing back in said first trellis, starting from the node having the smallest cumulated distance on the first depth level, corresponding to the last received sample R(t), following, at each level, the survivor path associated with the node reached;

thereby defining the optimal path; and

associating, with the estimation value s(t-L) corresponding to the decoding of the received sample R(t-n), the value of a terminal node of said optimal path;

wherein said computing step comprises a step of

associating, with estimation value s(t-L), a weighting coefficient m(t-L), representing the reliability of said estimation value s(t-L), said weighting coefficient being obtained by analyzing the cumulated distances M⁰ and M¹ associated with each of the nodes of said optimal path;

and wherein said step of revising, at each instant of reception t, said weighting coefficients comprises the steps of;

storing the weighting coefficient m(t-L) associated with said estimation S(t-L);

defining a second trellis T'"'"'(2.sup.ν

,L'"'"') of the possible states of the coding, where L'"'"'=N-L, consecutive to said first trellis T(2.sup.ν

,L), corresponding to the instants of reception between t-L-1 and t-L-L'"'"';

tracing back, in said second trellis, the two concurrent paths corresponding to the two paths coming from said terminal node of the optimal path of the first trellis to obtain two values s^k and s'"'"'^k respectively corresponding to the digital samples received on the two concurrent paths.; and

resetting the values of each of the weighting coefficients re(t-L-1) to re(t-N) associated respectively with each of the estimations s(t-L-1) to s(t-N) of the values of the digital samples received between the instants t-L-1 and t-N as a function of a level-to-level comparison of the values s_k and s'"'"'_k.

4. A method according to claim 3, wherein the depth L'"'"' of said second trellis is substantially equal to half the depth L of said first trellis.

5. A method according to claim 3, further comprising the steps of associating a provisional weighting coefficient m(t) with each of said nodes of said first trellis, and updating each of said provisional weighting coefficients m(t) at each instant of reception t as a function of the received sample R(t).

6. A method according to claim 3, wherein said weighting coefficient m(t-L), determined during said computing step, is equal to the absolute value Δ

M_t-L of the difference between the two metrics M⁰_t-L and M¹_t-L associated with said terminal node of said optimal path, also called a concurrence index, said metrics M⁰_t-L and M¹_t-L being, respectively, the total of the distances L⁰ and L¹ computed for each node of said optimal path, said distances L⁰ and L¹ representing the difference between the received symbol and the symbols corresponding to one of the two transitions possible in order to reach each node.

7. A method according to claim 6, wherein said resetting step comprises a step of logarithmically compressing said concurrence index Δ

M_t-L, thus forming a logarithmically compressed concurrence index equal to the weighting coefficient m_t-L, before said storing step.

8. A method according to claim 6 wherein, at each reception instant t and for each of the levels k of said second trellis, said reseting step comprises the steps of comparing the values s_k and s'"'"'_k corresponding to the received sample R(t-L-k) on each of the two concurrent paths, and reducing said concurrence index Δ

M_k downwards if these values s_k and s'"'"'_k are different.

9. A method according to claim 8 wherein said reseting set comprises the step of equating, when said values s_k and s'"'"'_k corresponding to the sample received R(t-L-k) on each of the two concurrent paths are different, said concurrence index Δ

M_k to the smaller of the values Δ

M_k and Δ

M_L, Δ

M_L being the concurrence index associated with the estimation value s(t-L), at the starting point of said concurrent paths, determined during said weighting step.

10. A method according to claim 9, further comprising the step of recomputing said concurrence index Δ

M_L, at each instant of reception t, as a function of the received samples R(t-L) to R(t).

11. A method according to any of the claims 1 to 4, wherein the received samples R(t) comprise, at least at certain instants t, two distinct coded data elements X(t) and Y(t) corresponding to said source digital element a(t).

12. A decoder of a sequence of received samples R(t), corresponding to a convolutional coding of a sequence of source digital elements a(t), said decoder comprising:

first and second storing means operating as level-by-level shift registers;

said first storing means being designed for storing a first trellis T(2.sup.ν

,L) of the possible states of the coding, comprising a set of nodes, organized in L depth levels of 2.sup.ν

nodes, L being an integer strictly greater than 1, and

said second storing means being designed for storing a second trellis T'"'"'(2.sup.ν

,L'"'"') of the possible states of the coding, comprising a set of nodes, organized in L'"'"' depth levels, of 2.sup.ν

nodes, L'"'"' being an integer strictly greater than 1,

said second storing means being connected consecutively to said first means for storing, so that said first storing means stores data corresponding to instants of reception between t and t-L and said second storing means stores data corresponding to instants of reception between t-L-1 and t-L-L'"'"';

means for tracing back of an optimal path ending with a final node, in said first trellis stored in said first means storing;

means for tracing back of two concurrent paths in said second trellis stored in said second means storing;

means for computing concurrence indices for each node of said first trellis;

third storing means of all concurrence indices associated with each node of said first trellis, with a size L×

2.sup.ν

×

μ

, where μ

is the number of bits used for the coding of each concurrence index;

a shift register, for storing weighting coefficients m(t-L-1) to m(t-N); and

means for revision of said weighting coefficients, as a function of said two concurrent paths traced back to said second trellis.

13. A decoder according to claim 12 wherein said shift register for storing the weighting coefficients is supplied by the concurrence index Δ

M_t-L of said final node of said optimal path, converted according to a logarithmic relationship to form m_t-L.