Iterative decoding method, decoding module and decoder therefor

0001The field of the invention is that of the coding of digital data belonging to a source data sequence intended to be transmitted, or broadcast, in particular in the presence of transmission noise, and of the decoding of the coded data thus transmitted.

0002More specifically, the invention relates to a decoding method, allowing the production of modular decoders, with several quality levels according to the number of modules used.

0003The invention finds applications in all cases where it is necessary to transmit digital information with a certain degree of reliability. A preferred field of application of the invention is that of digital transmission over very noisy channels. By way of example, the invention can be implemented for the transmission and reception of signals via satellites. It can also advantageously be used for space transmissions to or between spacecraft and / or space probes, and more generally in all cases where the reliability of decoding is critical. The invention can however be applied in the same way to any type of transmission, over the air or by cable.

0004Any digital signal, whatever its origin, can be coded and decoded according to the invention. It may for example be an image signal, a sound signal, a data signal, or a multiplex of several distinct signals.

0005In known manner, the coding of such signals is generally carried out using one or more convolutional coders. In the decoder, the original data are most often reconstructed using a maximum likelihood algorithm, for example the Viterbi algorithm, whose decisions can possibly be weighted.

0006The convolutional codes are codes associating with each source data to be coded at least one coded data, obtained by summing modulo 2 of this source data with at least one of the preceding source data. Thus, each coded symbol is a linear combination of the source data to be coded and of the previous source data taken into account. The Viterbi algorithm, taking into account a sequence of coded symbols received, provides an estimate of each coded datum on transmission, by determining the source sequence most probably corresponding to the sequence received.

0007It is also known to serialize several coders, whether they are convolutional or not. In this case, the data coded by a first coder feeds a second coder, which "overcodes" this data. Decoding is obviously done symmetrically, starting with the second code.

0008This principle, called code concatenation, has two types of drawbacks. First of all, the overall efficiency of the coders implementing contatted codes is low. For example, in the case of two encoders in series, each having a 1/2 efficiency, the overall efficiency will be 1/4. If more than two encoders are used, this efficiency quickly becomes very low.

0009Furthermore, the technical implementation of these coders is relatively complex, in particular as regards the clocks associated with each code, which must be independent.

0010As regards the decoders, it has already been indicated that generally maximum likelihood algorithms are used, such as the Viterbi algorithm. These algorithms make decisions taking into account a large number of symbols received. Clearly, the decision is all the more reliable the higher the number of symbols taken into account. On the other hand, the higher this number, the more complex the decoder. The memory space required quickly becomes very important, as well as the corresponding calculation times.

0011The integrated circuits implementing such algorithms therefore most often rely on a compromise between cost and performance. These industrial choices do not make it possible to build decoders corresponding optimally to a given application. It is for example not possible to produce decoders at low cost, for applications where the reception quality is not crucial, the integrated circuits having too high a cost. Conversely, these integrated circuits are also not suitable for making receivers with very high decoding quality, for which the cost price is of little importance.

0012The invention particularly aims to overcome these various drawbacks and limits of the state of the art.

0013More specifically, an object of the invention is to provide a coding method and a decoding method of digital data with very good correction power, in comparison with the known methods currently used in digital communications systems.

0014The object of the invention is in particular to provide such methods, which are particularly effective, always compared with known methods, for transmission in very noisy channels.

0015A particular objective of the invention is to provide such methods allowing very reliable decoding of the data received, and for example of data transmitted by satellites, or from probes or spacecraft.

0016Another object of the invention is to provide such methods, making it possible to encode and decode data at very high bit rates.

0017The invention also aims to provide such methods, allowing implementation of the encoders and decoders relatively easy, with regard to their performance.

0018In particular, the invention aims to provide a coding method implementing several convolutional codes, but requiring, both at the coder and at the decoder, only one clock.

0019Another objective of the invention is to provide such a coding method, having a very good overall coding yield.

0020The invention also aims to provide coding and decoding methods, allowing the production of very efficient decoders, but despite everything easily industrially feasible at acceptable costs.

0021Thus, a particular objective of the invention is to provide such methods, allowing the implementation of the decoding method on a silicon surface sufficiently limited for its industrialization to be possible, and for example on a surface less than 50 mm².

0022The invention also aims to provide such coding and decoding methods allowing the production of many types of decoders, with variable performance and cost price according to the needs to which they respond, and implementing one or more integrated circuits of a unique type.

0023In other words, an essential objective of the invention is to provide such methods allowing on the one hand a profitable industrialization, based on the development of a single and relatively simple integrated circuit, and on the other hand the realization of decoders usable for a very wide variety of applications.

0024These objectives, as well as others which will appear subsequently, are achieved according to the invention using a method of decoding digital data received in coded form and corresponding to source data, comprising an iterative decoding procedure. including:<ul id="ul0001" list-style="dash" compact="compact"><li>a step of decoding an intermediate datum representative of a datum received, producing a decoded datum, and</li><li>a step of estimating said received data, using said decoded data, producing an estimated data, said intermediate data being obtained, for the first iteration, by a combination of said received data with a predetermined value, and for the following iterations, by a combination of said data received with at least one of said data estimated during previous iterations.</li></ul>

0025This method makes it possible to produce decoders consisting of a cascade of identical modules, each module corresponding to an iteration. It is clear that the efficiency of the decoding is directly a function of the number of iterations practiced, and therefore of the number of modules used. It is thus possible to define several levels of receiver qualities, simply by varying the number of modules.

0026Each module therefore has the task of calculating, in addition to the decoded data, a new estimate of the transmitted data. This quantity is used from the next module.

0027Advantageously, said estimation step affects said estimated data item with an additive noise decorrelated from the noise assigned to said received item of data.

0028Thus, the data taken into account during the next iteration, combination of the received data and the estimated data, is affected by an overall noise that is less disturbing than in the previous iteration.

0029In a preferred embodiment of the invention, said predetermined value is neutral, or zero, and said combinations are, for iterations other than the first, summations of said received data and of the last estimated data.

0030In the case of a decoding of coded data according to a method ensuring the joint transmission of the source data and of coded redundancy data, for example using the “pseudosystematic” codes already mentioned, it is advantageous for said decoding step to take takes into account all of the data received, source data and coded data, but that said estimation step is applied only to the estimation of said source data.

0031The decoding method of the invention is advantageously associated with a coding method correcting errors of source digital data, implementing in parallel at least two independent steps of systematic convolutional coding, each of said coding steps taking into account the all of said source data, the method comprising at least one step of temporally interleaving said source data, modifying the order of taking into account said source data for each of said coding steps.

0032This method, hereinafter called "parallel concatenation" coding, as opposed to the conventional "serial concatenation" technique described in the preamble, makes it possible to have, when decoding symbols from two distinct coders.

0033The redundant codings used are of the systematic type. Each source datum is therefore also a convolutional coding symbol, and this symbol is shared by the two codes.

0034Sharing coding redundancy in several parallel redundancies thus makes it possible to artificially increase the overall yield of the code. For example, a 1/3 efficiency "parallel concatenation" code may actually contain two 1/2 efficiency codes. If it had been a question of concatenating, in a conventional manner, that is to say by a "series concatenation", two yield codes 1/2, the overall yield would have been 1/4.

0035Another advantage of the codes with "parallel concatenation", compared with the codes "with serial concatenation", is the simplicity of the coding and decoding circuits, relative to the clocks.

0036In a preferred embodiment, the coding method comprises a step of systematic elimination, at predetermined transmission times, of at least one coded datum produced by at least one of said coding steps.

0037The elimination step can for example consist of a periodic switching between said coding steps, ensuring, at each transmission time, the selection of a single coded symbol from the set of symbols coded by each of said coding steps.

0038In this way, a single coded symbol is transmitted at each time of transmission: there is no increase in the overall data rate. On the other hand, the coding method of the invention ensures the systematic transmission of the source data at each time of transmission.

0039In this embodiment, so-called "pseudo-systematic" codes are used, such as those described in French patent application FR 91 05278 entitled "convolutional coding method for pseudo-systematic error correction, decoding method and corresponding devices. ", and deposited on April 23, 1991 in the names of the same applicants. These codes make it possible to obtain very good decoding qualities, in particular in the presence of high transmission noise. They also prove to be very interesting by their systematic characteristic for the implementation of the decoding method described below.

0040Advantageously, each of said time interleaving steps is followed by a delay step, said time interleaving step taking into account the source data in the order in which said source data feeds a first coding step, and the restoring in a different order to feed a second coding step, said delay step affecting each of said source data originating from said time interleaving step by a delay equal to the latency of decoding of data encoded by said first encoding step.

0041These delays prove useful for the implementation of an embodiment of the decoding method of the invention, as will be seen later.

0042Advantageously, said temporal interleaving step implements at least one interleaving matrix in which said source data are written by successive rows (respectively columns) and read by successive columns (respectively rows).

0043This interleaving step allows all the source data to be taken into account and coded, but in different sequences for the two codes. Interlacing can therefore be done in a conventional manner, using an interlacing matrix. However, the invention proposes several possible adaptations of this technique, the aim of which is to improve the efficiency of the interleaving.

0044Thus, preferably, when writing, the increment between two rows (respectively columns) and / or, when reading, the increment between two columns (respectively rows) are strictly greater than 1.

0045By necessity, these increments are of course also prime with the number of columns or rows of this matrix.

0046Advantageously, when writing (respectively reading), said increment between two lines (respectively columns) depends on the location of the column (respectively line) during writing (respectively reading).

0047This technique has the favorable effect, during decoding, of "breaking" the error packets of rectangular arrangement, with respect to which the decoding process is more vulnerable. This interlacing technique will hereinafter be called "dispersion".

0048In the case where such a coding method is implemented, the decoding method advantageously comprises the following consecutive steps:<ul id="ul0002" list-style="dash" compact="compact"><li>first decoding according to said first redundant coding, as a function of at least one of said intermediate data and of at least one coded data produced by said first coding step, producing a first decoded data,</li><li>temporal interleaving identical to said interleaving step of the method of coding said first decoded data,</li><li>second decoding according to said second redundant coding, as a function of at least one of said first decoded and deinterleaved data and of at least one coded data produced by said second coding step, producing a second decoded data,</li><li>estimation of the source data received, as a function of at least one of said first and second decoded data, producing an estimated data,</li><li>symmetrical deinterlacing in said step of interleaving said estimated data.</li></ul>

0049Advantageously, said estimation step consists in determining the magnitude <maths id="math0001"><math display="inline"><mrow><msub><mrow><mtext>(d</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext> × (X</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>) - (X</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>)) / (d</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext>-1)</mtext></mrow></math><img file="EP0735696A2_D0001.tif" /></maths>, or :<ul id="ul0003" list-style="dash" compact="compact"><li>d₂ is the free distance of said second redundant coding;</li><li>X₁ and X₂ are the data decoded by said first and second decoding steps;</li><li>symmetrical deinterlacing (52) in said step (47) of interleaving said estimated data ((Z)_p).</li></ul>

0050This function removes from the result of the decoded data delivered by the second decoding step the contribution linked to the source data. Thus, the additive noise of the source data and the estimated data are practically completely uncorrelated.

0051Preferably, said estimation step is followed, before said deinterleaving step, by a logarithmic compression step.

0052The purpose of this logarithmic compression is to emphasize, in terms of sampling precision, the critical values, that is to say values ​​close to zero, when the values ​​are coded between -n and + n .

0053In an advantageous embodiment of the invention, said first decoding step is followed by a step of multiplying said first decoded datum by a coefficient β strictly greater than 1.

0054This coefficient β has the role of favoring, for the second decoding, the values ​​coming from the first decoder, relative to the coded values ​​received, affected by a higher noise because directly supplied by the transmission channel.

0055Preferably, said coefficient β is variable as a function of the signal to noise ratio of the transmission channel.

0056Advantageously, the said decoding step or steps employ maximum likelihood decoding algorithms, of the type of the Viterbi algorithm, with weighted decisions.

0057One can in particular make use of the decoding method described in the joint application entitled "decoding method of a convolutional code with maximum likelihood and weighting of decisions, and corresponding decoder", filed in the names of the same applicants.

0058Advantageously, the decoding method also comprises a demultiplexing step directing the coded data received towards said suitable decoding steps and transmitting zero values ​​to the decoding steps for which no coded data has been transmitted.

0059This step is useful when coded data is selectively non-transmitted, at certain times of transmission.

0060The invention also relates to a decoding module, performing an iteration of the decoding procedure described above. Such a module comprises at least two inputs, corresponding to at least one data received and at least one estimated data, and at least two outputs, corresponding to at least one decoded data and at least one estimated data. It is likely to be cascaded with at least one other identical module.

0061A module can in particular be produced in the form of an integrated circuit. Such a circuit occupies sufficiently little silicon surface to allow easy, reliable and inexpensive industrialization.

0062The modularity makes it possible to plan, from a single integrated circuit, any type of application. In cases requiring little protection, or when the channel is not very noisy, a single module may suffice. On the other hand, in particular cases where reliability is essential and / or the transmission noise is significant, for example in the case of data transmitted by an interstellar probe, ten or more modules may be cascaded.

0063The invention also relates to decoders implementing one or more of these modules.

0064Other characteristics and advantages of the invention will appear on reading the following description of a preferred embodiment of the invention given by way of illustration and not limitation, and the appended drawings, in which:<ul id="ul0004" list-style="dash" compact="compact"><li>FIG. 1 is a block diagram illustrating the basic principle of the coding method of the invention, known as "with parallel concatenation";</li><li>FIG. 2 shows a particular embodiment of an encoder according to the method illustrated in FIG. 1, ensuring 100% redundancy;</li><li>FIG. 3 is a block diagram of the basic principle of a modular decoder according to the invention, with four modules;</li><li>Figure 4 is a detailed block diagram of a preferred embodiment of a module of Figure 3, in the case where the data is encoded using the encoder of Figure 2;</li><li>Figures 5 and 6 show the results obtained using a decoder using the modules of Figure 4, depending on the number of cascaded modules, in the case of an ideal decoder (Figure 5) and a decoder implantable on integrated circuit (figure 6);</li><li>FIG. 7 presents an example of a "pseudo-systematic" coding module having a constraint length ν = 2 and a yield R = 1/2 which can be used in the coder of FIG. 1.</li></ul>

0065The present invention is based on two new concepts, namely a coding method implementing several codings simultaneously, in parallel, and an iterative decoding method.

0066Taken in combination, these two characteristics have a very strong synergy, making it possible to obtain a particularly low error rate at decoding, and in particular much lower than those obtained with known decoders of equivalent complexity, in particular in the presence of noise. high transmission.

0067FIG. 1 presents a block diagram of an encoder implementing the method of the invention, in the case where two distinct codes are used in parallel.

0068Each source data item d to be coded is directed on the one hand to a first coding module 11, and on the other hand to a time interleaving module 12, which itself feeds a second coding module 13.

0069According to this method, it therefore appears that it is associated with each source datum of at least two coded data Y₁ and Y₂ from separate coders 11 and 13. It is clear that the number of coders, here limited to two, can easily be extended according to the same principle.

0070The modules 11 and 13 can be of any known systematic type. Advantageously, these are convolutional coders taking into account at least one of the preceding source data for the coding of the source data d. The codes used in these modules 11 and 13 can be identical or, preferably, different.

0071An essential characteristic of the invention is that the data coded Y₁ and Y₂ take into account the same source data d, but considered in different sequences, thanks to the interlacing technique. This interleaving can be obtained, in a conventional manner, using an interleaving matrix, in which the source data are introduced row by row, and restored column by column. As will be seen below, the invention nevertheless proposes new improvements to this interleaving process, intended in particular to separate errors well, during decoding.

0072Furthermore, any other technique making it possible to modify the order of the source data can be used in this time interleaving module 12.

0073In the embodiment shown in FIG. 1, a datum X, equal to the source datum d, is systematically transmitted. This is a characteristic necessary for the realization of the decoding modules as described below.

0074In this case, the coding modules 11 and 13 preferentially use codes such as those described in the patent application FR 91 05278 already cited. These codes, called "pseudo-systematic", are characterized by the fact that the source data is systematically transmitted, together with at least one coded data, or redundancy symbol.

0075These redundancy symbols are constructed so that the free distance of the code is maximum. They do not take into account, as is customary in convolutional codes, a series of the preceding source data, but a series of auxiliary data, obtained by mathematical combination of the source data considered with at least one previous auxiliary data.

0076These new codes make it possible to obtain very good performance, in terms of error rate.

0077An example of an encoder (having a constraint length ν = 2 and an efficiency R = 1/2) implementing this technique is illustrated in FIG. 7.

0078This encoder associates with each source data d_k two values ​​coded X_k and Y_k.

0079Data X_k is systematically taken equal to the source value d_k.

0080The data Y_k is calculated, in a conventional manner, using a combination 81 of at least two binary elements contained in a shift register 82. On the other hand, this register 82 does not contain, in these cells 82_AT and 82_B, the previous source values ​​d_k-1, d_k-2, but separate intermediate values ​​a_k-1, at_k-2.

0081The essential characteristic of the invention is in fact to determine the coded value of Y_k from particular values ​​a_k obtained by a mathematical combination, and for example an exclusive OR 83, of the source data d_k with at least one of the above intermediate values ​​a_k-2 (unlike known convolutional coding methods which directly take into account the series of previous source values.

0082This amounts, in a way, to carrying out a feedback on the source values ​​d_k. It appears that this feedback makes it possible to obtain higher performance than that of conventional coders, while requiring only the addition of an exclusive OR 83 to these coders.

0083It seems that this gain can in particular be attributed to the fact that the locations of transmission errors in a sequence of received data are only rarely completely uncorrelated. The application of an exclusive OR combination on this data can then lead to the cancellation of some of these errors.

0084Numerous simulations with codes of constraint lengths and / or of different yields have shown that in all cases, this "pseudo-systematic" coding method exhibits superior performance to equivalent conventional convolutional coders (in terms of yield and constraint length) especially when the signal received is very noisy (E_b/NOT_o less than or equal to 3 dB).

0085The principle of “parallel concatenation” coding according to the invention has two advantages in particular, compared to conventional serial concatenation coding, as already mentioned: on the one hand the overall yield of the code is better, and , on the other hand, the coding and decoding circuits are simpler, as regards their clocks. In fact, in the case of "parallel concatenation", all the circuits operate on a single clock: that of the data rate.

0086FIG. 2 illustrates a particular embodiment of such an encoder, more specifically intended for the coding of decodable data using the modules described below, in relation to FIG. 4.

0087Consider, for example, an overall efficiency coder R greater than or equal to 1/3 (a typical value of R is 1/2) using two respective elementary efficiency codes. <maths id="math0002"><math display="inline"><mrow><msub><mrow><mtext>R</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> and R</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext> = (RR</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>) / (RR</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> + R</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> - R)</mtext></mrow></math><img file="EP0735696A2_D0002.tif" /></maths>, R₁ and R₂ both being greater than 1/2.

0088This encoder transmits, at each transmission instant, two digital symbols, for example binary symbols, X and Y. The symbol X is taken systematically equal to the source data item d, and the symbol Y is a redundancy symbol.

0089This symbol Y is equal to the value Y₁ from the first coding module 11, ie at the value Y₂ from the second coding module 13. A selection module 15 periodically switches between the outputs Y₁ and Y₂. The switching frequency is fixed by the two yields R₁ and R₂, so that the symbols X and Y actually contain two performance codes R₁ and R₂.

0090For example, for R code yields₁ = 3/5 and R₂ = 3/4, the transmitted data sequences can be: <tables id="tabl0001" num="0001"><table frame="all"><tgroup cols="6" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="26.25mm" /><colspec colnum="2" colname="col2" colwidth="26.25mm" /><colspec colnum="3" colname="col3" colwidth="26.25mm" /><colspec colnum="4" colname="col4" colwidth="26.25mm" /><colspec colnum="5" colname="col5" colwidth="26.25mm" /><colspec colnum="6" colname="col6" colwidth="26.25mm" /><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">X_t</entry><entry namest="col2" nameend="col2" align="left">X_{t + 1}</entry><entry namest="col3" nameend="col3" align="left">X_{t + 2}</entry><entry namest="col4" nameend="col4" align="left">X_{t + 3}</entry><entry namest="col5" nameend="col5" align="left">X_{t + 4}</entry><entry namest="col6" nameend="col6" align="left">X_{t + 5}, ...</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">Y_{1, t}</entry><entry namest="col2" nameend="col2" align="left">Y_{1, t + 1}</entry><entry namest="col3" nameend="col3" align="left">Y_{2, t + 2}</entry><entry namest="col4" nameend="col4" align="left">Y_{1, t + 3}</entry><entry namest="col5" nameend="col5" align="left">Y_{1, t + 4}</entry><entry namest="col6" nameend="col6" align="left">Y_{2, t + 5}, ...</entry></row></tbody></tgroup></table></tables>

0091The operation of this selection module 15 can of course be generalized. Thus, in the case where there are more than two coding modules, the selection can be made so as to ensure the transmission of a number m of coded data, selected from among the n coded data produced. Furthermore, this selection module 15 can also ensure punching of the coded data, the data (s) Y not being transmitted at predetermined transmission times.

0092The source data d are applied to the first coding module 11 and to the interleaving module 12. This module 12 provides matrix interleaving. The data is written, by successive lines, in a memory of size n_Exn_E, and restored by successive columns. This technique is for example described in the article "Optimal interleaving scheme for convolutional coding", by Dunscombe E. and Piper FC, published in "Electronic Letters", Vol.25 , n ° 22, October 1989.

0093As this article shows, the efficiency of interleaving, for small values ​​of n_E (a few tens), is improved if the succession of rows and columns is carried out in an increment greater than 1 and, by necessity, first with n_E.

0094The invention proposes a new improvement to this interlacing technique. It indeed appears advantageous that the line break increment, always prime with n_E, or depending on the place of the column considered. This makes it possible to break the error packets with a rectangular layout.

0095Other interleaving techniques can of course be used, and in particular the usual method with writing and reading increments equal to 1, without departing from the scope of the invention. It is also clear that the roles of rows and columns can be reversed.

0096The data from the interleaving module 12 are then delayed by a fixed duration, so as to compensate for the latency L₁ of the decoding module corresponding to the first code 11. For this, delay means 14, such as a shift register of length L₁, acting as a delay line, are arranged at the output of the interleaving module 12.

0097The decoding method according to the invention is now presented, in conjunction with FIG. 3.

0098The essential characteristic of this decoding process is that it is iterative. At each iteration, the decoding of at least one intermediate datum is carried out. Using in particular the decoded data, an estimate of the data to be decoded is then determined. During the next iteration, an identical decoding is performed, on an intermediate datum obtained by combining the received datum with the estimated datum. If the coding method and the estimation method are well chosen, it appears, as will be seen later, that the quality of the decoding is a function of the number of iterations carried out.

0099The essential advantage of this iterative process is that it allows the realization of modular decoders. We can indeed define modules 31₁ to 31₄ decoding, as illustrated in FIG. 3. Each module performs an iteration of the decoding process. By cascading n modules, we therefore carry out n iterations of the process.

0100Module 31_i has at least two inputs: the data X received, to be decoded, and a data Z_p representative of this data X received, estimated by the previous module 31_p-1, and two outputs: the data Z_p estimated, and the decoded value S, taken into account only at the output of the last module. For the first module 31₁, the data Z₁ is set to a predetermined value of zero. Advantageously, the data Z_p is determined so as to be representative of the transmitted symbol X, while being affected by an additive noise decorrelated from that assigned to the data received X. Thus, as iterations occur, the influence of the noise is increasingly lower, and the error rate is therefore increasingly reduced.

0101In other embodiments each module can take into account several data Z_p estimated during the previous steps, or even all of these data. The combination with the data X received can be a simple summation, or a weighted summation. It is for example conceivable to give a variable weight to the different Z values_p estimated. These weights may also vary depending on certain criteria, such as the signal-to-noise ratio.

0102The modular structure of the invention has two advantages in particular. First of all, this makes it possible to define several qualities of decoders, from the same base, simply by varying the number of modules. This also makes it possible to easily increase the efficiency of an existing decoder, by adding one or more modules, if the need arises.

0103The different modules work according to the so-called "pipeline" technique. Each module operates continuously, on different data. The addition of a module does not disturb the functioning of its predecessors. It only slightly lengthens the overall decoding time, by the time necessary for its own operations.

0104Furthermore, this structure requires only the design and industrialization of a single decoding module, for example in the form of a relatively simple integrated circuit and not requiring too large a surface area of ​​silicon. Its cost is therefore not prohibitive, especially since it is capable of being used for a very wide range of applications. Depending on the needs, it is the number of modules that will be variable, and no longer the structure of the modules.

0105It should be noted that the iterative design of the method of the invention in no way prevents the production of more conventional decoders, using only a single module. Indeed, each module has a data input received and a data output S decoded.

0106FIG. 4 presents a particular embodiment of a module according to the invention, the performances of which are very interesting, as shown by the curves of FIGS. 5 and 6, commented on below.

0107This module is intended for decoding coded data and transmitted using the coder of FIG. 2.

0108Such a module of rank p therefore has:<ul id="ul0005" list-style="dash" compact="compact"><li>3 inputs: (X)_p, (Y)_p and (Z)_p,</li><li>4 outputs: (X)_{p + 1}, (Y)_{p + 1}, (Z)_{p + 1} and (S)_p.</li></ul>

0109The quantities (X), (Y) and (Z) are ideally real variables, and in practice samples coded on n bits (typically n = 4). The quantity (S), which represents the output of the module, is binary. The decision of the complete decoder is given by the output (S) of the last module. Regarding the first module, the input quantities (X)₁ and (Y)₁ are provided by the corresponding symbols of the encoder, after transmission and demodulation. Its entry (Z)₁ is set to a neutral value (zero weight).

0110In this module, the input data (X)_p and (Z)_p are added by a summator 41 to provide the intermediate data (X₁)_p, which will be used for decoding instead of the received data (X)_p. As already pointed out, the data (X)_p and (Z)_p may possibly be weighted.

0111The data (Y)_p is transmitted to means 42 for demultiplexing and insertion, the role of which is to separate the redundancy (Y₁) produced by the encoder 11 (Figure 2) and the redundancy (Y₂) produced by the encoder 13, and to insert instead of the unavailable values ​​(Y) neutral values, of zero weight.

0112The data (X₁)_p and (Y₁)_p are transmitted to a first decoder 43, performing the decoding corresponding to the encoder 11. This decoder 43 is constructed in such a way that the scale on its input (X₁) or double that of its input (Y₁), so as to take into account the fact that (X₁) represents the summation of the two values ​​(X) and (Z).

0113The output 45 of the decoder 43 is transmitted to a subtractor 411 which makes the difference 412 between this output 45 and the input (Z) considered at a homogeneous instant, thanks to the shift register 410. (Z) being information produced and used by the second decoder 48 (described below) of the previous module, in the case of a decoder with at least two decoding modules, it is in fact preferable not to reapply it during subsequent iterations.

0114The difference 412 is then transmitted to a multiplier 44, which multiplies this value 412 by a factor β greater than 1. Multiplication by β makes it possible to favor, for the second decoding, the data originating from the first decoder 43, relative to the data ( Y₂)_p, affected by greater noise, since directly from the transmission channel.

0115The factor β can be fixed. However, it is advantageously variable, and dependent on the signal to noise ratio of the transmission channel. It is also clear that this multiplier is not compulsory for the implementation of the invention. However, it does significantly improve performance.

0116The data 46 multiplied by β are then interleaved, using a matrix 47 of size n_E xn_E similar to that used during coding. This matrix 47 outputs the value (X₂)_p which is directed to a second decoder 48, which also takes into account the data (Y₂)_p supplied by the means 42 for demultiplexing and insertion. This second decoder 48 performs the decoding corresponding to the second coder 13 in FIG. 2. It is constructed so that the scale on its input (X₂) or β times greater than that of its input (Y₂).

0117It should be noted that if the coding takes place in parallel, the decoding takes place in series. Thus, the second decoder 48 does not take account of the data received (X)_p, but decoded data, and of course interleaved, (X₂)_p, which is much more reliable. It is for this reason that this data has its importance reinforced, by the multiplier 44.

0118Advantageously, the two decoders 43 and 48 implement a maximum likelihood decoding method, of the type of those using the Viterbi algorithm, with weighted decisions.

0119In a preferred embodiment, decoders are used as described in patent application FR 91 05279, entitled "method for decoding a convolutional code with maximum likelihood and weighting of decisions, and corresponding decoder", filed on 23.04 .91 in the names of the same applicants.

0120These decoders use in particular two separate trellises. The decision is taken, in a conventional manner, by ascending the optimal path in the first trellis. The weighting is then determined, continuing to go up, in the second trellis, the optimal path and its competitor.

0121According to the method of this application, the weighting values ​​are advantageously subjected to logarithmic compression. However, in the case of the module currently described, it appeared preferable that only the first decoder 43 uses this logarithmic compression law. It is somehow postponed, in the case of the second decoder 48, as will be seen below.

0122The data (X₃)_p produced by the second decoder 48 feed a deinterlacing matrix 49 of size n_Exn_E performing the dual function of interleaving 47, and providing the data (S)_p decoded.

0123These data (S)_p decoded are of course only taken into account at the output of the last module, which has the lowest error rate, except in the case of tests, for example to determine the number of modules necessary for a given application.

0124The data (X₃)_p are also directed to block 50 for estimating the value (X)_p entrance. This block 50 also takes into account the corresponding value (X '₂)_p, input of the second decoder 48, and stored in a shift register 51, acting as a delay line. This register 51, of length L₂, L₂ being the latency of the second decoder 48, aims to compensate for the decoding time of this decoder 48, so that the module 50 considers the input data (X '₂)_p and output (X₃)_p of the second decoder at homogeneous times.

0125The role of this estimation block 50 is therefore to determine an estimate (Z)_p of the emitted symbol X. This estimate is made so that the quantity (Z)_p is affected by an additive noise decorrelated from that affecting the symbol (X). (Z)_p is taken into account in the next module (p + 1). Thus, in this module (p + 1), the first decoder processes a virtual code, of yield R₁/ (1 + R₁), R₁ being the output of the first encoder 11.

0126The decorrelation between the additive noises of (X)_p and (Z)_p can for example be ensured by a function g, which removes from the result (X₃)_p from the second decoder 48 the contribution linked to (X)_p. The function g is advantageously the following:<maths id="math0003"><math display="block"><mrow><msub><mrow><mtext>g ((X</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mtext>p</mtext></mrow></msub><msub><mrow><mtext>, (X</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mtext>p</mtext></mrow></msub><msub><mrow><mtext>) = (d</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>x (X</mtext></mrow><mrow><mtext>3</mtext></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mtext>p</mtext></mrow></msub><msub><mrow><mtext>- (X</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>)</mtext></mrow><mrow><mtext>p</mtext></mrow></msub><msub><mrow><mtext>) / (d</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext>-1)</mtext></mrow></math><img file="EP0735696A2_D0003.tif" /></maths> where d₂ is the free distance of the second code.

0127Block 50 then advantageously performs logarithmic compression, precisely that which has been eliminated in the second decoder 48, of the values ​​g ((X₂)_p, (X₃)_p). The values ​​thus obtained are transmitted to a deinterlacing matrix 52, identical to the matrix 49, and providing the output (Z)_{p + 1}.

0128The module of rank p moreover ensures the transmission of the data received (X) and (Y), with delays making it possible to present outputs at homogeneous times, for the module according to rank p + 1. Each module therefore includes two shift registers 53 and 54, respectively for the data (X) and (Y). These shift registers act as delay lines, and have a length of:<maths id="math0004"><math display="inline"><mrow><msub><mrow><mtext>L</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> + L</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext> + 2n</mtext></mrow><mrow><mtext>E</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>2</mtext></mrow></msup></mrow></math><img file="EP0735696A2_D0004.tif" /></maths>, so as to compensate:<ul id="ul0006" list-style="dash" compact="compact"><li>latency L₁ the first decoder 43;</li><li>latency n_E² the interleaving matrix 47;</li><li>latency L₂ the second decoder 48;</li><li>latency n_E² of the deinterlacing matrix 52.</li></ul>

0129Figures 5 and 6 show the results obtained using a decoder equipped with such modules, for a yield code 1/2 of the type 3/5 (ν = 4) // 3/4 (ν = 4) , that is to say a parallel concatenation of two yield codes 3/5 and 3/4, with constraint lengths ν = 4. The abscissa of the curves is the signal to noise ratio E_b/NOT₀ on the transmission channel (E_b : energy received per useful bit, N₀ : monolateral noise spectral density). The ordinate is the bit error rate observed: the curves present the decoding results obtained by simulation of a Gaussian channel, the demodulation being consistent.

0130Figure 5 corresponds to an ideal decoder, working on real variables and with a large interlacing. FIG. 6 presents the case of an "integrable" decoder on an integrated circuit, the main characteristics of which are as follows:<ul id="ul0007" list-style="dash" compact="compact"><li>samples coded on 4 bits,</li><li>lattice length for each decoder: 58 including 25 revision stages for weighting,</li><li>β = 1.5,</li><li>31x31 dispersion interlacing.</li></ul>

0131Curves 61₁ to 61₅ of figure 5 and 71₁ to 71₅ in Figure 6 respectively represent the outputs (S)_p of a chain of five identical modules. For comparison, the curves 62 corresponding to an uncoded transmission were also shown, and the curves 63 and 64 corresponding to the correction curves of the simple standard codes with constraint lengths ν = 4 and ν = 6 respectively.

0132These curves allow several conclusions to be drawn. It is noted first of all that in the presence of a strong transmission noise, the results obtained are exceptionally better than those obtained according to known techniques. So, for example, for an error rate of 10^-5, we see that the gain is greater than 1.5dB, for a two-module decoder, and greater than 2.5dB, for a five-module decoder, compared to a conventional decoder with constraint length ν = 6 (whereas the coders used for simulating the performances of the invention have constraint lengths ν = 4).

0133It also appears that the performance of a decoder of the invention is better than that of known decoders, when we aim for an error rate of the order of 10^-4, even when using only one module (curves 61₁ and 71₁).

0134Finally, it can be noted that each module added makes it possible to improve the quality of the decoding, by approaching the Shannon limit, which is 0 dB for a yield code 1/2. Using this series of curves 61₁ to 61₅, it is possible to select, depending on a particular application, the number of modules required.

0135Performance losses, at high noise, in the "integrable" case (curves 71₁ to 71₅) relative to the ideal case (curves 61₁ to 61₅), are almost entirely related to the very small size of the interleaving matrix. We indeed chose small matrices (31x31) so as to limit the surface area of ​​silicon used. With such matrices, the occupied silicon surface is of the order of 30 mm². However, experience shows that larger arrays, of the order of 100 × 100 (which corresponds to RAM memories of quite conventional sizes), make it possible to greatly improve the performance, while remaining within entirely limits acceptable from the point of view of the industrialization of an integrated circuit.