United States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,446,747
`
`Berrou
`Aug. 29, 1995
`[45] Date of Patent:
`
`USOO5446747A
`
`[54] ERROR-CORRECTION CODING METHOD
`WITH AT LEAST TWO SYSTEMATIC
`CONVOLUTIONAL CODINGS IN
`PARALLEL, CORRESPONDING ITERATIVE
`DECODING METHOD, DECODING
`MODULE AND DECODER
`
`[75]
`
`Inventor:
`
`Claude Berrou, Le Conquet, France
`
`[73] Assignees: France Telecom; Telediffusion de
`France S.A., both of France
`
`[21] Appl. No.: 870,614
`
`[22] Filed:
`
`Apr. 16, 1992
`
`Foreign Application Priority Data
`[30]
`Apr. 23, 1991
`France ................................ 91 05280
`
`Int. (:16 .............................................. cusp 11/10
`[51]
`[52] U.S. Cl. ........................................ 371/45; 371/43;
`375/340
`[52] Field of Search ..................... .. 371/43, 44, 45, 41,
`371/37.1; 375/59, 75, 94
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`.
`3/1972 Fomey, Jr.
`3,652,998
`.......................... .. 371/43
`6/1987 Betts ct a.l.
`4,677,625
`......
`..
`4,677,626 6/1987 Betts et al.
`4,881,241 ll/1989 Pornmier et al.
`
` 5,077,741 12/1991 Kotzrn .....
`
`5,157,671 10/1992 Karplus .... ...
`5,263,051 11/1993 Eyuboglu
`5,287,374 2/1994 Parr .................
`5,289,501
`2/1994 Seshadri et al.
`
`...... 371/30
`. ..... 371/43
`...... 371/43
`.. .. .. 371/43
`...................... 375/17
`
`FOREIGN PATENT DOCUMENTS
`
`I-103M 13/00
`0235477 9/1987 European Pat. Off.
`2616986 12/1988 France ........................ H03M 13/12
`
`OTHER PUBLICATIONS
`
`Dr. G. Lomp et al ‘Projection Codes—A New Class of
`
`22 Claims, 5 Drawing Sheets
`
`FEC Burst Correction and ARQ Codes for Mobile
`Radio’ IEEE 1988 pp. 463—467.
`G. Fettweis ‘Cascaded Feedforward Architectures for
`Parallel Viterbi Decoding’ IEEE 1990 pp. 978-981.
`Iteratively Maximum Likelihood Decodable Spherical
`Codes and a Method for their Construction. Gao et al.
`IEEE 1988 pp. 480-485.
`Dunscombe and Piper, Optimal Interleaving Scheme fiar
`Convolutional Coding, Aug. 1989; Electronics Letters,
`Oct. 26, 1989, vol. 25, No. 22.
`Battail, et al. Decadage Pondere des Codes Concatenes
`Avec Code Interieur Convolutzf; Onzieme Colloque; Jun.
`1987.
`Mackenthun, Block orthogonal convolutional coding for
`the Intelsat TDMA data channel, Comsat Technical
`Review, Fall 1984.
`Nakano, et al. New Decoding Methods of Interleaved
`Burst Error-Correcting Codes, Electronics and Commu-
`nications in Japan, Apr. 1983.
`
`Primary Examiner—Robert W. Beausoliel, Jr.
`Assistant Examiner—-Albert Decady
`Attorney, Agent, or Firm—Locke Reynolds
`
`ABSTRACT
`[57]
`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 tem-
`poral interleaving of the source data elements, modify-
`ing 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 ele-
`ment obtained by the combination of the received data
`element with a data element estimated during the previ-
`ous iteration.
`
`d
`
`12
`
`
`
`
` 1 FIRST
`
`SYSTEMATIC
`
`CODING
`
`13
`
` SECON
`
`
`CODING
`
`SYSTEMATIC
`
`ERICSSON EXHIBIT 1004
`
`
`
`TEMPORAL
`
`INTERLEAVING
`
`

`
`U.S. Patent
`
`Aug. 29, 1995
`
`Sheet 1 of 5
`
`5,446,747
`
`
`
`
`13
`INTERLEAVING ‘
` SECOND
`
`
`
`SYSTEMATIC
`
`CODING
`
`Y2
`
`
`
`
`SYSTEMATIC
`
`CODING
`
`FIRST
`
`
`
`SECOND
`
`
`
`‘I4
`
`SYSTEMATIC
`CODING
`
`
`X,Y
`
`
`
`
`311
`
`312
`
`313
`
`314
`
`DECODING
`
`MODULE
`
`
`
`FIRST
`
`SYSTEMATIC
`
`CODING
`
`12
`
`
`
`TEMPORAL
`
`

`
`U.S. Patent
`
`Aug. 29, 1995
`
`sheet‘ 2 of 5
`
`5,446,747
`
`
` mmmm~m:.m_um=_.E=._wE»3
`
`5.5I28N2.35.“.
`
`Qmm»m_wmmE=._m.
`
`_+CO4goo
`
`
`
`
`
`.03.._o5250zoF<z:m_~m_._.__.S:zEooomo
`
`
`$25ozoomm.Q3
`.!Eooumo.@m¢
`oz_><m.EEz_-mooz_><m._,_m»z_fi\_3
`
`
`
`x_E<2mvx_fi<s_9.3VKim
`om.~m.5_o$_.
`
`
`
`2928oz..2:
`
`
`
`oz_><m._~_m.rz_-m_om¢.4Nu
`,x_E<2uz_xm:.__F._:2m_o
`
`
`Vm,
`
`
`
`1.55mm.8_wm_~_.E_.._m
`
`zoEmmz_oz<
`
`v.3
`
`
`

`
`U.S. Patent
`
`Aug. 29, 1995
`
`Sheet 3 of 5
`
`‘
`
`5,446,747
`
`
`
`
`
`' “————‘:_:::———::
`A \T‘_‘—‘———_—‘“——‘
`l\\‘—:‘——:—_:——:—_—
`::\\x1111111111111111
`nuns:-—111111111111:
`—\_
`\\‘ E“-fl
`- :
`
`I‘NSIIIIIiH!IIIII
`
`.M!NSl§!IIIIlIfliE!
`
`5".‘ EiE“‘:'I—.'EEE=====EE‘
`==:.:::':=_*.‘.=a.-==
`II-uIIn\—’|1In‘u—---
`——|I\—.—CCl‘E———
`IIHIHIENIEII
`
`IKIIZ
`
`
`
`
`
`
`
`9IImnngg§gI:a:IIii
`D ——‘—
`
`
`
`- —I :I_m)“-X——\Xi_———h
`jjjjjljjjj
`ZCT j
`
`
`
`Innflunnnnumunnuun
`IIHIIHIIIIHIIIIII
`!!flflIIIIII!RlIIII
`11-II—|—1nI3m_1'3;u\11
`115-11 54
`11-II-I-1-It
`111111
`11-II-I-111
`---II .--_-—--:‘“-'.-
`
`
`
`\
`
`\
`
`
`
`
`---II l------Ifl'J-
`afillllll
`‘-
`HIIEEIKHII
`Eflflfififinu
`IIIII
`
`
`
`
`‘
`
`1111111111
`
`-F11:--XI‘-K
`
`
`
`

`
`U.S. Patent
`
`Aug. 29, 1995
`
`Sheet 4 of 5
`
`5,446,747
`
`
`
`. xwjjjjjjjjjjjjjjjj
`kxvijjjjjfjjjjjjjjj
`!5_\‘sYIjjjjjj
`—=
`iij
`ham‘:
`1
`S£\\\jK‘—S—_
`‘i:
`fll\\§‘LV-ED
`
`
`IIIIIIIIIIIIIIII/CIIIIIll—
`!!IIIIIufiIIIIIHQIIIIIfillllllilgllll
`
`E
`
`L
`
`
`
`
`Imwnsllii
`IIN&§§
`EEEfiE=EE
`EEE
`jjj
`Tij CI.
`—ZZ SIR‘ XVII
`---m_u.uu-
`
`
`‘K.\IIIE5IIIIIIII
`
`
`
`In:Inl
`
`
`
`2—jjI—ljjj1CI7j1Cjjjjj
`jjjj u — jujj:n:tjj-Ijjjjj
`—_——|Il—|--‘-‘——s_ “-
`T1jiIIIZIZZi&C‘1ZXI 1—1
`:11:|IIL—II1$n‘ 13 1:1
`- --I|“-“:—- ——KI———
`
`- --I|‘II-‘---K‘--‘_--
`‘
`\
`IIIIIIIIIIIIKIIIHII
`
`
`
`1
`
`1II
`
`jilifla
`
`==.:'.-.=-.='.=='..-.=-=5£E
`---I‘-I'll------U ‘-"I
`--—E=ilI|I-xI----DEA
`
`
`
`
`
`I:||\| !I|III
`
`
`
`=====m==
`======‘ul=.=
`CCXIZCIIK
`---I--nu
`IIIIIIII“
`
`umIIIIIINN
`
`
`
`
`9=a
`EE
`KIZ
`n-
`II
`II
`
`
`
`4IIIlMNIi§IEll'
`
`
`

`
`U.S. Patent
`
`Aug. 29, 1995
`
`Sheet 5 of 5
`
`5,446,747
`
`Fig. 7
`
`

`
`ERROR-CORRECTION CODING METHOD WITH
`AT LEAST TWO SYSTEMATIC CONVOLUTIONAL
`CODINGS IN PARALLEL, CORRESPONDING
`ITERATIVE DECODING METHOD, DECODING 5
`MODULE AND DECODER
`
`BACKGROUND OF THE INVENTION
`
`10
`
`5
`
`I
`
`1. Field of the Invention
`The field of the invention is that of the coding of
`digital data belonging to a sequence of source data de-
`signed to be transmitted, or broadcast, notably in the
`presence of transmission noise, and of the decoding of
`coded data thus transmitted.
`More specifically, the invention relates to a method
`of error correction coding that relies notably on a to-
`tally novel approach involving the concatenation of
`several codes, and to a decoding method that enables
`the making of modular decoders, with several levels of 20
`quality depending on the number of modules imple-
`mented.
`The invention can be applied whenever where it is
`necessary to transmit digital information with a certain
`degree of reliability. A preferred field of application of 25
`the invention is that of digital transmission on highly
`noise-ridden channels. For example, the invention may
`be implemented for the transmission and reception of
`signals by satellite. It can also be used advantageously
`for spatial transmission towards or between spaceships 30
`and/or space probes and,niore generally, whenever the
`reliability of the decoding is of vital importance. How-
`ever, the invention can be applied similarly to any type
`of transmission, by r.f. or by cable.
`Any digital signal, whatever may be its origin, can be 35
`coded and decoded according to the invention. It may
`be, for example, an image signal, a sound signal, a data
`signal or a multiplex of several distinct signals.
`2. Description of the Prior Art
`In a known way, signals such as these are generally 40
`coded by means of one or more convolutional coders.
`In the decoder, the original data elements are most
`frequently reconstructed by means of a maximum likeli-
`hood algorithm, for example a Viterbi algorithm, the
`decisions of which may possibly be weighted.
`Convolutional codes are codes that associate at least
`one coded data element with each source data element,
`this coded data element being obtained by the summa-
`tion modulo 2 of this source data element with at least
`one of the preceding source data elements. Thus, each 50
`coded symbol is a linear combination of the source data
`element to be coded and of previous data source ele-
`ments taken into account. The Viterbi algorithm, taking
`account of a sequence of received coded symbols, gives
`an estimation of each data element coded at transmis— 55
`sion,
`in determining the source sequence that most
`probably corresponds to the received sequence.
`There also exists a known way of placing several
`coders in series, whether they are convolutional or not.
`In this case, the data elements coded by a first coder 60
`feed a second coder which “overcodes” these data ele-
`ments. The decoding is obviously done symmetrically,
`in starting with the second code.
`This principle, known as that of the concatenation of
`codes, has two types of drawbacks. Firstly, the overall 65
`efficiency rate of the coders implementing concatenated
`codes is low. For example, in the case of two coders in
`series each having a rate Q, the overall rate will be 3,‘. If
`
`45
`
`1
`
`5,446,747
`
`2
`‘ more than two decoders are used, this rate will soon
`become very low.
`Besides, the technical making of these coders is rela-
`tively complex," notably as regards the clock signals
`associated with each code which have to be indepen-
`dent.
`
`With respect to decoders, it has already been indi-
`cated that the algorithms generally used are maximum
`likelihood algorithms such as the Viterbi algorithm.
`These algorithms take decisions in taking account of a
`large number of received symbols. Clearly, the reliabil-
`ity of the decision increases with the number of symbols
`taken into account. By contrast, the higher the number,
`the more complex is the decoder. The memory space
`needed soon becomes very substantial, as do the corre-
`sponding computation times.
`The integrated circuits that implement such algo-
`rithms therefore most usually rely on a compromise
`between cost and performance characteristics. These
`industrial choices do not enable the construction of
`decoders that correspond optimally to a given applica-
`tion. It is, for example, not possible to make low-cost
`decoders for applications where reception quality is not
`vital, the integrated circuits having an excessively high
`cost. Nor, on the other hand, are these integrated cir-
`cuits adapted to the making of very high quality decod-
`ing receivers, for which the cost price is of little impor-
`tance.
`
`SUMMARY OF THE INVENTION
`
`It is an aim of the invention notably to overcome
`these different drawbacks and limits of the prior art.
`More specifically, an aim of the invention is to pro-
`vide a method for the coding and a method for the
`decoding of digital data with very high corrective ca-
`pacity as compared with the known methods currently
`used in digital communications systems.
`It is an object of the invention, notably, to provide
`methods such as these that are particularly efficient,
`again in comparison with known methods, for transmis-
`sion in highly noise-ridden charmels.
`A particular aim of the invention is to provide meth-
`ods such as these permitting highly reliable decoding of
`the received data, for example data transmitted by satel-
`lites or coming from space probes or spacecraft.
`A further aim of the invention is to provide methods
`such as these, enabling the coding and decoding of data
`at very high bit rates.
`The invention is also aimed at providing methods
`such as these, enabling the relatively easy manufacture
`of coders and decoders as regards their performance
`characteristics.
`Notably, the invention is aimed at providing a coding
`method such as this that implements several convolu-
`tional codes but requires only one clock, in the coder as
`well as the decoder.
`Another aim of the invention is to provide a coding
`method such as this that has very high overall coding
`efficiency rate.
`The invention is further aimed at providing coding
`and decoding methods that enable the making of high-
`performance decoders which, nevertheless, can be eas-
`ily manufactured on an industrial scale at acceptable
`costs.
`
`Thus, a particular aim of the invention is to provide
`methods such as these, enabling the implantation of the
`decoding method on a surface area of silicon that is
`
`

`
`3
`small enough for its industrial-scale manufacture to be
`possible (for example an area smaller than 50 ml).
`The invention is also aimed at providing coding and
`decoding methods such as these that enable the making
`of numerous types of decoders, with performance char-
`acteristics and cost prices that can vary as a function of
`the requirements that they "fulfil, and that use one or
`more integrated circuits of a single type.
`In other words, an essential aim of the invention is to
`provide methods such as these that enable, firstly, prof-
`itable industrial-scale manufacture based on the devel-
`opment of a single, relatively simple integrated circuit
`and, secondly, the making of decoders that can be used
`for a wide variety of applications.
`These aims, as well as others that shall be described
`hereinafter, are achieved according to the invention by
`means of a method for the error-correction coding of
`source digital data elements, implementing in parallel at
`least two independent steps of systematic convolutional
`coding, each of said coding steps taking account of all of
`said source data elements, the method comprising at
`least one step for the temporal interleaving of said
`source data elements, modifying the order in which said
`source data elements are taken into account for each of
`said coding steps.
`This method, hereinafter called method of “parallel
`concatenation” coding, by contrast with the standard
`technique of “series concatenation” described in the
`introduction, makes it possible, during the decoding, to
`have available symbols coming from two distinct de-
`coders.
`
`The redundant codes used are of a systematic type.
`Each source data element is therefore also a convolu-
`tional coding symbol, and this symbol is shared by both
`codes.
`The dividing of the coding redundancy into several
`parallel redundancies thus enables the artificial raising
`of the overall efficiency rate of the code. For example,
`a “parallel concatenation” code with an efficiency rate
`of Q may actually contain codes with an efficiency rate
`of §. In the standard method, namely the method of
`series concatenation, if the operation had involved the
`concatenation of two codes with an efficiency rate of 5,
`then the overall efficiency rate would have been lg.
`Another advantage of parallel concatenation codes as
`compared with series concatenation codes is the sim-
`plicity of the coding and decoding circuits, in relation to
`the clock signals.
`In a preferred embodiment, the coding method com-
`prises a step for the systematic elimination, at predeter-
`mined instants of transmission, of at least one coded data
`element produced by at least one of said coding steps.
`The elimination step may, for example, consist of a
`periodic switching among said coding steps by which,
`at each transmission instant, a single coded symbol is
`selected from among the set of symbols coded by each
`of said coding steps.
`In this way, a single coded symbol is transmitted at
`each instant of transmission: there is no increase in the
`overall data bit rate. By contrast, the coding method of
`the invention provides for the systematic transmission
`of the source data at each instant of transmission.
`This embodiment makes use of so-called pseudo-sys-
`tematic codes such as those described in the French
`patent application No. 91 05278 entitled “Pseudo-Sys-
`tematic Error-Correction Convolutional Coding
`Method, Decoding Method and Corresponding De-
`vices”, filed on 23rd Apr. 1991. These codes can be used
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,446,747
`
`4
`to obtain very good decoding quality, especially in the
`presence of high transmission noise. Besides, their sys-
`tematic characteristic makes them very promissing for
`the implementation of the decoding method described
`further below.
`Advantageously, each of said temporal interleaving
`steps is followed by a delay step, said temporal inter-
`leaving step taking account of the source data elements
`in the order in which said source data elements feed a
`first coding step and restoring them in a different order
`to feed a second coding step, said delay step assigning,
`to each of said source data elements coming from said
`temporal interleaving step, a delay equal to the latency
`of decoding of data elements coded by said first coding
`step.
`These delays prove to be useful for the implementa-
`tion of an embodiment of the decoding method of the
`invention, as shall be seen hereinafter.
`Advantageously, said temporal interleaving step im-
`plements at least one interleaving matrix in which said
`source data elements are recorded in successive rows
`(and columns respectively) and read in successive rows
`(and columns respectively).
`This interleaving step enables all the source data
`elements to be taken into account and coded, but ac-
`cording to different sequences for the two codes. The
`interleaving can therefore be done in a standard way, by
`means of an interleaving‘ matrix. However, the inven-
`tion proposes several possible adaptations of this tech-
`nique, aimed at improving the elfectiveness of the inter-
`leaving.
`Thus preferably, at writing, the increment between
`two rows (and columns respectively) and/or at reading,
`the increment between two columns (and rows respec-
`tively) is strictly greater than 1.
`By necessity, these increments are naturally also rela-
`tively prime with the numbers of columns or rows of
`this matrix.
`
`Advantageously, at writing (and reading respec-
`tively), said increment between two rows (and columns
`respectively) is a function of the position of the column
`(or row respectively) during writing (or reading respec-
`tively).
`This technique has the favorable effect, during the
`decoding, of “breaking” the rectangularly arranged
`error packets with respect to which the decoding
`method is more vulnerable. This interleaving technique
`shall be known hereinafter as the “dispersal technique”.
`Indeed, the invention also relates to a method for the
`decoding of digital data elements received in coded
`form and corresponding to source data elements com-
`prising an iterative decoding procedure comprising:
`a step for the decoding of an intermediate data ele-
`ment representing a received data element, produc-
`ing a decoding data element, and
`a step for the estimation of said received data element,
`by means of said decoded data element, producing
`an estimated data element, said intermediate data
`element being obtained, for the first iteration, by a
`combination of said received data element with a
`pre-determined value, and for the following itera-
`tions, by a combination of said received data ele-
`ment with one of said data elements estimated dur-
`ing the preceding iterations.
`This method can be used to make decoders formed by
`a cascade of identical modules, each module corre-
`sponding to an iteration. It is clear that the efficiency
`rate of the decoding directly depends on the number of
`
`

`
`5
`iterations made and hence on the number of modules
`used. It is thus possible to define several levels of quali-
`ties of receivers, simply by varying the number of mod-
`ules.
`Each module therefore has the task of computing, in
`addition to the decoded data element, a new estimation
`of the data element emitted. This variable is used from
`the next module onwards.
`Advantageously, said estimation step assigns said
`estimated data element an additive noise decorrelated
`from the noise assigned to said received data element.
`Thus, the data element taken into account during the
`following iteration, which is a combination of the re-
`ceived data element and of the estimated data element,
`is affected by an overall noise that is less disturbing than
`in the preceding iteration.
`In a preferred embodiment of the invention, said
`predetermined value is neutral or zero and said combi-
`nations are, for iterations other than the first one, sum-
`mations of said received data element and of the last
`estimated data element.
`In the case of a decoding of data coded according to
`a method that carries out the joint transmission of
`source data elements and redundancy data elements
`coded for example by means of the already mentioned
`“pseudo-systematic” codes, it is advantageous for said
`decoding step to take account of all the received data,
`elements, source data elements and coded data ele-
`ments, but said estimation step is applied solely to the
`estimation of said source data elements.
`
`According to a particular embodiment of the inven-
`tion, of the type carrying out the decoding of 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 their 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, the decoding method comprises the
`following consecutive steps:
`first decoding according to said first redundant cod-
`ing, as a function of at least one of said intermediate
`data elements and of at least one coded data ele-
`ment produced by said first coding step, producing
`a first coded data element;
`temporal interleaving identical to said interleaving
`step of the coding method of said first decoded data
`elements;
`second decoding according to said second redundant
`coding, as a function of at least one of said first
`decoded and de-interleaved data elements and of at
`least one coded data element produced by said
`second coding step, producing a second coded data
`element;
`estimation of the received source data element, as a
`function of at least one of said first and second
`decoded data elements, producing an estimated
`data element;
`de-interleaving, symmetrical to said interleaving step,
`of said estimated data elements.
`
`Advantageously, said estimation step consists in de-
`termining the variable (dz x(X1)—(X2))/d2— 1) where:
`d2 is the free distance of said second redundant cod-
`1118;
`X1 and X2 are the data elements decoded by said first
`and second decoding steps.
`This function removes the contribution related to the
`source data element from the result of the decoded data
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`65
`
`5,446,747
`
`6
`element delivered by the second decoding step. Thus,
`the additive noises of the source data element and of the
`estimated data element are practically completely
`decorrelated.
`"
`Preferably, said estimation step is followed, before
`said de-interleaving step, by a logarithmic compression
`step.
`This logarithmic compression is designed to place
`emphasis, in terms of sampling precision, on the critical
`values, namely on the values close to zero, when the
`values are coded between -—n and +n.
`In an advantageous embodiment of the invention,
`said first decoding step is followed by a step for the
`multiplication of said first decoded data element by a
`coefficient /3 that is strictly greater than 1.
`The role of this coefficient B is to give preference, for
`the second decoding, to the values coming from the first
`decoder, in relation to the coded values received, af-
`fected by a greater noise because they are given directly
`by the transmission channel.
`Preferably, said coefficient B is variable as a function
`of the signal-to-noise ratio of the transmission channel.
`Advantageously, said decoding step or steps imple-
`ment maximum likelihood decoding algorithms of the
`Viterbi algorithm type with weighted decisions.
`It is possible, notably, to use the decoding method
`described in the contemporaneously filed U.S. applica-
`tion Ser. No. 07/870,483, now U.S. Pat. No. 5,406,570,
`entitled “Method For The Decoding Of A Maximum
`Likelihood Convolutional Code With Decision
`Weighting And Corresponding Decoder” claiming the
`Convention priority of the French patent application
`FR 91 05279, filed on Apr. 23, 1991,
`incorporated
`herein by reference.
`Advantageously, the decoding method also includes
`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.
`This step is useful when coded data elements are
`selectively non-emitted at certain instants of transmis-
`sion.
`
`The invention also relates to a decoding module car-
`rying out an iteration of the decoding procedure de-
`scribed here above. A module such as this comprises 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 at least one estimated data
`element. It is capable of being cascaded with at least one
`other identical module.
`A module may notably be made in integrated circuit
`form. Such a circuit takes up a surface area of silicon
`that is small enough to enable easy, reliable and low-
`cost industrial-scale manufacture.
`The feature of modularity makes it possible to pro-
`vide for any type of application on the basis of a a single
`integrated circuit. In cases requiring only a low level of
`protection, or when the channel is little affected by
`noise, only one module may be sufficient. By contrast,
`in special cases where reliability is an essential factor
`and/or the transmission noise is high, for example in the
`case of data transmitted by an interstellar probe, ten or
`more modules may be cascaded.
`The invention also relates to decoders implementing
`one or more of these modules.
`
`

`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Other features and advantages of the invention shall
`appear from the following description of a preferred
`embodiment of the invention, given by way of a non-
`restrictive illustration, and from the appended drawings
`of which:
`
`5
`
`10
`
`FIG. 1 is a block diagram illustating the basic princi-
`ple of the coding method of the invention, called “paral-
`lel concatenation” coding;
`FIG. 2 shows a particular embodiment of a coder
`according to the method illustrated in FIG. 1, providing
`for a redundancy of 100%;
`FIG. 3 is a block diagram of the basic principle of a
`modular decoder according to the invention, with four
`modules;
`FIG. 4 is a detailed block diagram of a preferred
`embodiment of a module of FIG. 3, when the data ele-
`ments are coded by means of the coder of FIG. 2;
`FIGS. 5 and 6 show results obtained by means of a 20
`decoder using the modules of FIG. 4, as a function of
`the number of cascaded modules, in the case of an ideal
`decoder (FIG. 5) and a decoder that can be implanted
`on the integrated circuit (FIG. 6).
`FIG. 7 shows an example of a “pseudo-systematic” 25
`coding module, having a constraint length v=2 and an
`efficiency rate R=é, that can be used in the coder of
`FIG. 1.
`
`15
`
`MORE DETAILED DESCRIPTION
`
`30
`
`40
`
`45
`
`50
`
`The present invention relies on two novel concepts,
`namely a coding method simultaneously carrying out
`several coding operations, in parallel, and a method of
`iterative coding.
`Taken in combination, these two features display a 35
`very high degree of synergy, making it possible to ob-
`tain a particularly low error rate at decoding, notably
`an error rate that is far smaller than those obtained with
`known decoders of equivalent complexity, especially in
`the presence of high transmission noise.
`However, it is clear that these features may be imple-
`mented independently without going beyond the scope
`of the invention. It shall be seen further below that it is
`possible, according to the embodiment described, to
`make decoders with only one module: this would corre-
`spond to a non-iterative decoding.
`FIG. 1 shows a block diagram of a coder implement-
`ing the method of the invention, in an example where
`two distinct codes are used in parallel.
`Each source data element d to be coded is directed,
`firstly, towards a first coding module 11 and, secondly,
`towards an temporal
`interleaving module 12 which
`itself feed a second coding module 13.
`According to this method, it is seen, therefore, that
`there are at least two coded data elements Y1 and Y2, 55
`coming from distinct coders 11 and 13, associated with
`each source data element. It is clear that the number of
`coders, limited herein to two, can easily be increased
`according to the same principle.
`The modules 11 and 13 may be of any known system-
`atic type. They are advantageously convolutional cod-
`ers taking account of at least one of the preceding
`source data elements for the coding of the source data
`element d. The codes implemented in these modules 11
`and 13 may be identical or, preferably, different.
`An essential feature of the invention is that the coded
`data elements Y1 and Y2 take account of the same source
`data elements (1, but these are considered according to
`
`60
`
`65
`
`7
`
`5,446,747 '
`
`8
`different sequences, through of the interleaving tech-
`nique. This interleaving may be obtained in a standard
`way by means of an interleaving matrix in which the
`source data elements are introduced row by row and
`restored column by column. As shall be seen further
`below, the invention nevertheless proposes novel im-
`provements to this interleaving method, designed nota-
`bly to clearly separate the errors, at decoding.
`Besides, any other technique that enables the order of
`the source data elements to be modified may be used in
`this temporal interleaving module 12.
`In the embodiment shown in FIG. 1, a data element
`X, equal to the source data element d, is transmitted
`systematically. This is a feature necessary for the mak-
`ing of the decoding modules as described further below.
`In this case, the coding modules 11 and 13 preferably
`use codes such as those described in the already men-
`tioned French patent application No. FR 91 05278.
`These codes, known as “pseudo-systematic codes” are
`characterized by the fact that the source data element is
`transmitted systematically, jointly with at
`least one
`coded data element or redundancy symbol.
`These redundancy symbols are constructed in such a
`way that the free distance of the code is the maximum.
`They do not take account, as is usually done in the
`convolutional codes, of a series of previous source data
`elements, but of a series of auxiliary data elements ob-
`tained by the mathematical combination of the source
`data element considered with at least one of the previ-
`ous auxiliary data elements.
`These novel codes can be used to obtain excellent
`performance characteristics in terms of error rate.
`An example of a coder (having a constraint length
`v=2 and efficiency rate R: Q) implementing this tech-
`nique is illustrated in FIG. 7.
`This coder associates two coded values Xk and Yk to
`each source data element dk.
`The data element Xk is systematically taken to be
`equal to the source value dk.
`The data element Yk is computed by means of a com-
`bination 81 of at least two binary elements contained in
`a shift register 82. By contrast, in its cells 82,4 and 823,
`the shift register 82 contains not the previous source
`values dk_1, dk_.2, but distinct
`intermediate values
`3k—la 3k—2-
`The essential characteristic of the invention is indeed
`that of determining the coded value of Yk, on the basis
`of particular values ak obtained by a mathematical com-
`bination and, for example, an exclusive OR gate 83, of
`the source data element dk with at least one of the pre-
`ceding intermediate values ak_1 (contrary to the known
`convolutional coding methods which take direct ac-
`count of the series of the preceding source values).
`This, in a way, amounts to performing a feedback on
`the source values dk. It is seen that this feedback makes
`it possible to obtain performance characteristics greater
`than those of classic coders while, at the same time,
`requiring only the addition of an exclusive-OR gate 83
`to these coders.
`It appears that this gain can be attributed notably to
`the fact that it is only very rarely that the positions of
`the tranmission errors in a sequence of received data are
`completely decorrelated. The application of a combina-
`tion by exclusive-OR operations on these data elements
`may then lead to the cancellation of certain of these
`errors.
`
`Numerous simulations with codes having different
`constraint lengths and/or efficiency rates have shown
`
`

`
`9
`that in every possible instance this “pseudo-systematic”
`coding method has performance characteristics supe-
`nor to those of standard convolutional coders, equiva-
`lent in terms of efiiciency rate and constraint length,
`notably when the signal received is highly noise-
`infested (E1,/No smaller than or equal to 3 dB).
`The principle of “parallel concatenation” coding
`according to the invention has notably two advantages
`over the standard coding with serial concatenation, as
`mentioned already: firstly, the overall rate of the code is
`higher and, secondly, the coding and decoding circuits
`are