Error-correction coding method with at least two systematic convolutional codings in parallel, corresponding iterative decoding method, decoding module and decoder

• US 5,446,747 A
• Filed: 04/16/1992
• Issued: 08/29/1995
• Est. Priority Date: 04/23/1991
• Status: Expired due to Term

• Current Assignee: France Telecom SA (Orange S.A.), Telediffusion De France SA
• Original Assignee: Orange S.A., Telediffusion De France SA
• Inventors: Berrou, Claude
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Decady, Albert
• Application Number:
  US07/870,614
• Time in Patent Office: 1,230 Days
• Field of Search: 371/43, 371/44, 371/45, 371/41, 371/37.1, 375/59, 375/75, 375/94
• US Class Current: 714/788
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/27 using interleaving techniques
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/2987 using more component decoders than component codes, e.g. pipelined turbo iterations
• CPC Class Codes: H03M 13/39 Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
• CPC Class Codes: H03M 13/6362 by puncturing
• CPC Class Codes: H03M 13/658 Scaling by multiplication or division
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes
• CPC Class Codes: H04L 1/0068 by puncturing
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

An error-correction method for the coding of source digital data elements to be transmitted or broadcast, notably in the presence of high transmission noise, the method comprising at least two independent steps of systematic convolutional coding, each of the coding steps taking account of all of the source data elements, the method comprising at least one step for the temporal interleaving of the source data elements, modifying the order in which the source data elements are taken into account for each of the coding steps, and a corresponding iterative decoding method using, for the decoding, at each iteration, an intermediate data element obtained by the combination of the received data element with a data element estimated during the previous iteration.

Claims

1. A method for error-correction coding of source digital data elements, comprising the steps of:

implementing at least two independent and parallel steps of systematic convolutional coding, each of said coding steps taking account of all of said source data elements and providing parallel outputs of distinct series of coded data elements;

and temporally interleaving said source data elements to modify the order in which said source data elements are taken into account for at least one of said coding steps.

2. A method according to claim 1, comprising a step of systematically eliminating, at predetermined instants of transmission, at least one coded data element of at least one of said series of coded data elements.

3. A method according to claim 2, wherein said elimination step consists of periodically switching among said parallel outputs by which, at each transmission instant, a single coded data element is selected from among the distinct series of coded data elements.

4. A method according to claim 1, wherein each of said temporal interleaving steps is followed by a delaying step,

said delaying step assigning, to each of said source data elements coming from said temporal interleaving step, a delay equal to a time of latency for coding the data elements coded by said first coding step.

5. A method according to claim 1, wherein said temporal interleaving step implements at least one interleaving matrix in which said source data elements are recorded in successive rows and read in successive rows.

6. A method according to claim 5 wherein, at writing, two successive source data are written in between two rows selected according to an increment which is strictly greater than 1.

7. A method according to claim 6, wherein said increment between two rows is a function of the position of the column during writing.

8. A method according to claim 5 wherein, at reading, two successive source data are read in two columns selected according to an increment which is strictly greater than 1.

9. A method according to claim 8, wherein said increment between two columns is a function of the position of the row during reading.

10. A method for decoding received digital data elements representing source data elements coded according to the coding method of claim 1, wherein said decoding method comprises an iterative decoding procedure comprising the steps of:

in a first iteration, combining each of said received digital data elements with a predetermined value to form an intermediate data element,

decoding the intermediate data element representing each received data element to produce a decoded data element,

estimating said source data element, by means of said decoded data element, to produce an estimated data element,

and for all subsequent iterations, combining each of said received data elements with one of said estimated data elements estimated during a preceding iteration.

11. A method according to claim 10, wherein said estimating step assigns to said estimated data element an additive noise decorrelated from noise assigned to said received data element.

12. A method according to claim 10, wherein said predetermined value has a zero weight, having no effect on said decoding, and said combinations are, for iterations other than the first one, summations of said received data element and of the estimated data element estimated in the immediately preceding iteration.

13. A method according to claim 10, applied to decoding of data coded according to a method carrying out a joint transmission of source data elements and coded redundancy data elements, wherein said decoding step takes account of all the received data elements, source data elements and coded data elements, and wherein said estimation step is applied solely to the estimation of said source data elements.

14. A method according to claim 10, wherein said decoding step or steps implement maximum likelihood decoding algorithms of the Viterbi algorithm type with weighted decisions.

15. A method according to claim 10, including a demultiplexing step directing the received coded data elements towards said appropriate decoding steps and transmitting zero values at the decoding steps for which no data element has been transmitted.

16. A method according to claim 10, of the type carrying out the decoding of a first and a second series of received data elements representing source data coded according to a coding method implementing two redundant coding steps in parallel, the first coding step carrying out a first redundant coding on all the source data taken in natural order and the second coding step carrying out a second redundant coding on all the source data taken in an order modified by a temporal interleaving step to produce two distinct series of coded data elements, wherein said decoding method comprises the consecutive steps of:

first decoding according to said first redundant coding the first series of received data elements taken together with at least one of said intermediate data elements to produce a series of first decoded data elements;

temporally interleaving, identical to said interleaving step of the coding method, said first decoded data elements to form a series of decoded de-interleaved data elements;

second decoding according to said second redundant coding said decoded de-interleaved data elements and the second series of received data elements to produce a series of second decoded data elements;

estimating the source data from at least one of said series of first and second decoded data elements to produce a series of estimated data elements; and

de-interleaving, symmetrical to said interleaving step, said estimated data elements.

17. A method according to claim 16, wherein said estimating step consists in determining the variable (d₂ ·

(X₁)-(X₂))/(d₂ -1) where;

d₂ is the free distance of said second redundant coding;

X₁ and X₂ are the data elements decoded by said first and second decoding steps.

18. A method according to claims 16, wherein said estimation step is followed, before said de-interleaving step, by a logarithmic compression step.

19. A method according to claim 16, wherein said first decoding step is followed by a step of subtracting, from said first decoded data element, said estimated data element.

20. A method according to claim 16, wherein said first decoding step is followed by a step for the multiplication of said first decoded data element by a coefficient β

that is strictly greater than 1.

21. A method according to claim 20, wherein said coefficient β

varies as a function of a signal-to-noise ratio of a transmission channel.

22. A decoding module for carrying out an iteration of a decoding procedure comprising at least two inputs, corresponding to at least one received data element and to at least one estimated data element, and at least two outputs corresponding to at least one decoded data element and to at least one estimated data element,

wherein said module is capable of being cascaded with at least one other identical module, each module comprising:

means for summation of the inputs corresponding to said received data element and to said estimated data element;

first decoding means for decoding of data elements coded according to a first redundant coding, taking account of the data elements coming from said summation means;

first interleaving means for interleaving the data elements coming from said first decoding means;

second decoding means for decoding data coded according to a second redundant coding;

means for estimating said received data element or elements;

first de-interleaving means for de-interleaving the data elements coming from said estimation means;

second de-interleaving means for de-interleaving the data elements coming from said second decoding means, delivering the data elements decoded in their original order; and

delay means designed to compensate for latencies of the decoding means, interlacing means and de-interlacing means so that all the data elements coming from said module correspond to one and the same instant of reception.