DESIGN OF THE INTERLEAVER FOR TURBO CODES AS A FUNCTION OF THE PUNCTURING PATTERN

Abstract

A method is provided for encoding an input digital message bearing K information symbols using a turbo-encoder forming a turbocode, the turbo-encoder including an interleaver and first and second encoders for encoding according to at least one elementary code and delivering the information symbols and redundancy symbols. With a puncturing of the symbols delivered by the turbo-encoder being done according to at least one periodic puncturing pattern of a length N, defining the puncturing period N, the interleaver distributes the information symbols of the input message into Q layers of the interleaved input message in complying with an interleaving function defined from the at least one puncturing pattern, according to the relationship: (i)=Pi+S(i mod Q) mod K=Pi+(T.sub.l+A.sub.lQ) mod K.

Claims

1. A method comprising: encoding an input digital message bearing K information symbols using a turbo-encoder forming a turbocode, the turbo-encoder comprising an interleaver and first and second encoders for encoding according to at least one elementary code and delivering said information symbols and redundancy symbols, wherein, with a puncturing of the symbols delivered by the turbo-encoder being done according to at least one periodic puncturing pattern of a length N, defining the puncturing period, said interleaver distributes the information symbols of said input message into Q layers of the interleaved input message in complying with an interleaving function defined from said at least one puncturing pattern, according to the relationship:
(i)=Pi+S(i mod Q)mod K=Pi+(T.sub.l+A.sub.lQ)mod K with: i=0, . . . , K1 being the position of an information symbol in said interleaved input message, in the interleaved order and (i) the position of said information symbol in said input message, in the natural order; P an integer value co-prime with the length K of said input message, called an interleaver period; S(i mod Q)=S(l)=T.sub.l+A.sub.1Q are the parameters of adjustment of the interleaving function, with 1=0, . . . , Q1 the layer number; Q a degree of disorder inserted into the interleaver, corresponding to the number of layers, such that Q=qN, with q1 being an integer and Q being a divider of K; T.sub.l a value of inter-layer adjustment defined from said at least one puncturing pattern; and A.sub.l a value of intra-layer adjustment.

2. The method according to claim 1, wherein, said puncturing implementing a puncturing of the information symbols delivered by said turbo-encoder, the value of inter-layer adjustment T.sub.l makes the punctured information symbols correspond with one another between their position in the natural order and their position in the interleaved order.

3. The method according to claim 1, wherein the inter-layer adjustment values T.sub.l makes the positions of the most fragile non-punctured information symbols correspond with the positions of the least fragile non-punctured information symbols, the degree of fragility of the positions being determined by comparing the distance spectra of the elementary codes obtained in puncturing each of the non-punctured information symbols one by one, the least fragile position corresponding to the spectrum having the greatest minimum Hamming distance and the lowest multiplicity and the most fragile position corresponding to the spectrum having the smallest minimum Hamming distance and the greatest multiplicity, the multiplicity corresponding to the number of words of an elementary code at a distance d.

4. The method according to claim 1, wherein the inter-layer adjustment values T.sub.l makes the positions of the most fragile punctured information symbols correspond with the positions of the least fragile punctured information symbols, the degree of fragility of the positions being determined as a function of the number of punctured redundancy symbols, the least fragile positions being those for which no redundancy symbol is punctured and the most fragile positions being those for which all the redundancy symbols are punctured.

5. The method according to claim 3, wherein the degrees of fragility of the positions having the same number of punctured redundancy symbols are determined on the basis of at least one comparison of the distance spectra of the elementary codes obtained by puncturing non-punctured redundancy symbols one by one, the least fragile position corresponding to the spectrum having the greatest minimum Hamming distance and the lowest multiplicity, and the most fragile position corresponding to the spectrum having the lowest minimum Hamming distance and the greatest multiplicity.

6. The method according to claim 1, wherein the adjustment parameters of the interleaving function are determined as a function of predefined values of the minimum cumulative spatial distance S.sub.min and of the length of the minimum correlation cycle G.sub.min of the interleaver for at least one interleaver period P, the length of the minimum correlation cycle G.sub.min of the interleaver corresponding to the length of the shortest correlation cycle of the graph of correlation between the input message, in the natural order, and the interleaved input message in the interleaved order.

7. The method according to claim 6, wherein the predefined value of the minimum cumulative spatial distance S.sub.min of the interleaver is smaller than or equal to the greatest integer smaller than the square root of twice the length K of the input digital message S.sub.min={square root over (2K)}, and the predefined value of the length of the minimum correlation cycle G.sub.min of the interleaver is smaller than or equal to Moore's theoretical limit 2 log.sub.3(K).

8. The method according to claim 1, wherein the period P of the interleaver is chosen to ensure a minimum cumulative spatial distance value S.sub.min of the interleaver greater than or equal to the minimum cumulative spatial distance of a regular interleaver whose interleaving function is (i)=Pi mod K.

9. The method according to claim 1, wherein the two elementary codes of the first and second encoders of the turbo-encoder are identical.

10. The method according to claim 1, wherein the elementary codes of the first and second encoders of the turbo-encoder are circular.

11. The method according to claim 1 wherein the puncturing period is a divider of the length of the input digital message.

12. A non-transitory computer-readable medium comprising a computer program stored thereon and comprising instructions for implementing a method of encoding when this the instructions are executed by a processor of a turbo-encoder, the method comprising: encoding an input digital message bearing K information symbols using the turbo-encoder, the turbo-encoder forming a turbocode and comprising an interleaver and first and second encoders for encoding according to at least one elementary code and delivering said information symbols and redundancy symbols, wherein, with a puncturing of the symbols delivered by the turbo-encoder being done according to at least one periodic puncturing pattern of a length N, defining the puncturing period, said interleaver distributes the information symbols of said input message into Q layers of the interleaved input message in complying with an interleaving function defined from said at least one puncturing pattern, according to the relationship:
(i)=Pi+S(i mod Q)mod K=Pi+(T.sub.l+A.sub.lQ)mod K with: i=0, . . . , K1 being the position of an information symbol in said interleaved input message, in the interleaved order and (i) the position of said information symbol in said input message, in the natural order; P an integer value co-prime with the length K of said input message, called an interleaver period; S(i mod Q)=S(l)=T.sub.l+A.sub.lQ are the parameters of adjustment of the interleaving function, with l=0, . . . , Q1 the layer number; Q a degree of disorder inserted into the interleaver, corresponding to the number of layers, such that Q=qN, with q1 being an integer and Q being a divider of K; T.sub.l a value of inter-layer adjustment defined from said at least one puncturing pattern; and A.sub.l a value of intra-layer adjustment.

13. A turbo-encoder device comprising: a processor; and a non-transitory computer-readable medium comprising instructions stored thereon, which when executed by the processor configure the turbo-encoder device to: encode an input digital message bearing K information symbols using an interleaver and first and second encoders for encoding according to at least one elementary code, and delivering said information symbols and redundancy symbols, wherein a puncturing of the symbols delivered by said turbo-encoder being done according to at least one periodic puncturing pattern of a length N, defining the puncturing period, said interleaver distributes the information symbols of said input message in Q layers of the interleaved input message in complying with an interleaving function defined from said at least one puncturing pattern, according to the relationship:
(i)=Pi+S(i mod Q)mod K=Pi+S(l)mod K=Pi+(T.sub.l+A.sub.lQ)mod K with: i=0, . . . , K1 being the position of an information symbol in said interleaved input message, in the interleaved order and (i) the position of said information symbol in said input message, in the natural order; P an integer value co-prime with the length K of said input message, called an interleaver period; S(i mod Q)=S(l)=T.sub.l+A.sub.1Q the parameters of adjustment of the interleaving function, with 1=0, . . . , Q1 the layer number; Q a degree of disorder inserted into the interleaver, corresponding to the number of layers, such that Q=qN, with q1 being an integer and Q being a divider of K; T.sub.l is a value of inter-layer adjustment defined from said at least one puncturing pattern; and A.sub.l a value of intra-layer adjustment.

14. The method according to claim 4, wherein the degrees of fragility of the positions having the same number of punctured redundancy symbols are determined on the basis of at least one comparison of the distance spectra of the elementary codes obtained by puncturing non-punctured redundancy symbols one by one, the least fragile position corresponding to the spectrum having the greatest minimum Hamming distance and the lowest multiplicity, and the most fragile position corresponding to the spectrum having the lowest minimum Hamming distance and the greatest multiplicity.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0148] The invention can be understood more clearly from the following detailed description of non-exhaustive examples of implementation of the invention and from the appended drawings, of which:

[0149] FIG. 1A, described here above, represents the structure of a turbo-encoder according to the prior art, and FIGS. 1B and 1C represent the structure of a turbo-encoder according to different embodiments of the invention,

[0150] FIG. 2, described here above, illustrates the iterative decoding of a turbocode according to the prior art,

[0151] FIG. 3, described here above, represents the curves of error rates of a turbocode decoded iteratively according to the prior art,

[0152] FIG. 4, described here above, represents an interleaver of a turbocode with elementary circular codes according to the prior art,

[0153] FIG. 5 is a graph illustrating different steps of implementation of a method for building an interleaver,

[0154] FIG. 6 represents curves for measuring mutual information exchanged between the decoders corresponding to the turbo-encoder according to an exemplary embodiment, used for the selection of the puncturing pattern,

[0155] FIG. 7 represents the curves of error rates of the turbo-decoder corresponding to a uniform interleaver for different selected puncturing patterns,

[0156] FIG. 8, described here above, represents an example of a connection rule of an interleaving function according to the prior art,

[0157] FIG. 9, described here above, represents a ranking of positions according to their degree of fragility for which the information symbol is not punctured,

[0158] FIGS. 10A and 10B, described here above, illustrate the determining of the degree of fragility of the positions for which the information symbol is punctured,

[0159] FIGS. 11 and 12, described here above, illustrate the rules of connection of the interleaving function according to the invention,

[0160] FIGS. 13A and 13B, described here above, are examples of graphic representations used for the building of the interleaver,

[0161] FIG. 14, described here above, illustrates the sub-division of the interleaver into Q layers,

[0162] FIG. 15, described here above, illustrates an example of possible inter-layer adjustment,

[0163] FIG. 16, described here above, illustrates an example of possible intra-layer adjustment,

[0164] FIG. 17, described here above, represents the link between the connected positions and the adjustment value T.sub.l,

[0165] FIG. 18 represents the permissible connections of the interleaver for the punctured information symbols according to the exemplary embodiment of FIGS. 6 and 7,

[0166] FIGS. 19 and 20 represent examples of connections imposed for the interleaving of the non-punctured information symbols according to the first rule of connection of the interleaving function according to the invention,

[0167] FIG. 21 represents the example of a connection mask for the punctured information symbols as a function of their degree of fragility,

[0168] FIG. 22 shows the values of minimum cumulative spatial distance corresponding to the permissible values of the regular interleaver period,

[0169] FIG. 23 represents the curves of measurement of mutual information exchanged between the decoders corresponding to the turbo-encoder according to another exemplary embodiment, used for the selection of the puncturing pattern,

[0170] FIG. 24 represents the error rate curves of the turbo-decoder corresponding to a uniform interleaver for different selected puncturing patterns,

[0171] FIG. 25 shows the values of minimum spatial cumulated distance corresponding to permissible values of the regular interleaver period,

[0172] FIG. 26 represents curves of measurement of mutual information exchanged between the decoders corresponding to the turbo-encoder according to another exemplary embodiment, used for the selection of the puncturing pattern,

[0173] FIG. 27 represents error rate curves of the turbo-decoder corresponding to a uniform interleaver for different selected puncturing patterns,

[0174] FIG. 28 represents permissible connections of the interleaver for the punctured information symbols according to the exemplary embodiment of FIGS. 26 and 27,

[0175] FIGS. 29 and 30 represent other examples of connection dictated for the interleaving of the non-punctured information symbols according to the first rule of connection of the interleaving function according to the invention,

[0176] FIG. 31 represents another example of a connection mask for the punctured information symbols as a function of their degree of fragility,

[0177] FIG. 32 represents curves of measurement of the mutual information exchanged between the decoders corresponding to the turbo-encoder according to another exemplary embodiment, used for the selection of the puncturing pattern,

[0178] FIG. 33 represents error rate curves of the turbo-decoder corresponding to a uniform interleaver for different puncturing patterns selected according to another exemplary embodiment,

[0179] FIG. 34 represents error rate curves of the turbo-decoder corresponding to a uniform interleaver for different puncturing patterns selected,

[0180] FIG. 35 represents permissible conditions of the interleaver for punctured information symbols according to the exemplary embodiment of FIG. 34,

[0181] FIG. 36 represents another example of connections dictated for the interleaving of non-punctured information symbols according to the first rule of connections of the interleaving function according to the invention, according to the exemplary embodiment of FIG. 34,

[0182] FIG. 37 represents another example of a connection mask for the punctured information symbols as a function of their degree of fragility according to the exemplary embodiment of FIG. 34,

[0183] FIG. 38 represents bit error rate curves on a Gaussian channel of the turbocode for different configurations of interleaving, for an input digital message length K=1504,

[0184] FIG. 39 represents frame error rate curves on a Gaussian channel of the turbocode for different interleaving configurations, for an input digital message length K=1504,

[0185] FIG. 40 represents bit error rate curves on a Gaussian channel of the turbocode for different interleaving configurations, for a length of the input digital message K=6144, and

[0186] FIG. 41 represents frame error rate curves on a Gaussian channel of the turbocode for different interleaving configurations, for a length of an input digital message K=6144.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

[0187] FIGS. 1B and 1C show the structure of a turbo-encoder according to the invention, outputting information symbols (interleaved or non interleaved) and redundancy symbols, and a puncturing of the information and/or redundancy symbols, for an encoding rate of R1/3 and 1/3>R1/5 respectively.

[0188] The turbo-encoder illustrated in FIG. 1B comprises an interleaver 20 and two encoders, for example of the recursive systematic convolutive type (C1, C2), each producing a systematic output (information symbols X in the natural order for the first encoder C1 or information symbols X in the interleaved order for the second encoder C2) and a redundancy output (redundancy symbols Y1 for the first encoder C1, and redundancy symbols Y2 for the second encoder C2). The input digital message, comprising K information symbols is encoded in its order of arrival, called a natural order, by the encoder C1, and in the interleaved order or permutated order by the encoder C2.

[0189] The output digital message comprising the systematic output (information symbols X or else information symbols X) and the redundancy output (redundancy symbols Y1 and Y2) can be punctured according to at least one periodic puncturing pattern of a length N. For example, for each encoding rate greater than 1/3, three puncturing patterns of a length N are used, each expressed for example in the form of a binary vector: a first puncturing pattern used for the puncturing of the information symbols X or X, a second puncturing pattern used for the puncturing of the redundancy symbols Y1 and a third puncturing pattern used for the puncturing of the redundancy symbols Y2. If the elementary codes of the first and second encoders (C1, C2) of the turbo-encoder are identical, the same puncturing pattern can be applied to the redundancy symbols Y1 and to the redundancy symbols Y2.

[0190] The turbo-encoder illustrated in FIG. 1C comprises an interleaver 20 and two encoders, for example of the recursive systematic convolutive type (C1, C2) each producing a systematic output (information symbols X in the natural order for the first encoder C1, or information symbols X in the interleaved order for the second encoder C2) and two redundancy outputs (redundancy symbols Y1 and W1 for the first encoder C1, and redundancy symbols Y2 and W2 for the second encoder C2).The input digital signal comprising K information symbols is encoded in its order of arrival, called a natural order, by the encoder C1 and, in the interleaved or permutated order by the encoder C2.

[0191] The output digital message comprising the systematic output (information symbols X or else information symbols X) and the two redundancy outputs (redundancy symbols Y1 and W1 obtained from the first encoder and redundancy symbols Y2 and W2 obtained from the second encoder), can be punctured according to at least one periodic puncturing pattern of a length N. For example, for each encoding rate of 1/5 to 1/3, five puncturing patterns of a length N are used, expressed for example in the form of a binary vector: a first puncturing pattern used for the puncturing of the information symbols X and X, a second puncturing pattern used for the puncturing of the redundancy symbols Y1, a third puncturing pattern used for the puncturing of the redundancy symbols Y2, a fourth puncturing pattern used for the puncturing of the redundancy symbols W1, and a fifth puncturing pattern used for the puncturing of the redundancy symbols W2. If the elementary codes of the first and second encoders (C1, C2) of the turbo-encoder are identical, the same puncturing pattern can be applied to the redundancy symbols Y1 and the redundancy symbols Y2. In the same way, the same puncturing pattern can be applied to the redundancy symbols W1 and to the redundancy symbols W2.

[0192] Other encoding rates can of course be obtained with a turbo-encoder according to the invention, by modifying the number of redundancy outputs.

[0193] FIG. 5 represents different steps of implementation of a method for building an interleaver 20 for a turbo-encoder according to FIGS. 1B and 1C. In a step 11, a puncturing pattern is preliminarily selected from among a plurality of puncturing patterns, on the basis of at least a comparison between the distance spectra of the corresponding punctured elementary codes and measurements of mutual information. In a step 12, the degree of fragility of the different positions within the puncturing patterns selected at the step 11 is determined. In a step 13, an interleaving function of the interleaver is established by connecting the positions according to at least one connection rule of said interleaving function, dependent on the degree of fragility of the positions. In a step 14, a restricted set of candidates is determined for the adjustment parameters S(l) of the interleaving function determined in the step 13. During a step 15, at least one interleaver 20 is selected from among the restricted set of candidates of the step 14, on the basis of at least the distance spectra of the turbocodes obtained in using the corresponding interleavers.

[0194] A first example of building of an interleaver 20 shall be described with reference to FIGS. 6, 7 and 18 to 22. In this example, the elementary codes of the first and second encoders C1, C2 of the turbo-encoder are the code CSR (13,15).sub.8, the resulting turbocode of which has an encoding rate R=2/3, and the length of the input digital message is equal to K=1504. The puncturing period N, a divider of K, is equal to 16.

[0195] The table below lists the best puncturing patterns in terms of distance spectra of the elementary code that have been obtained with N=16. The values A.sub.d represents the multiplicity A.sub.d at the distance d=0, 1, 2, 3, 4. The value 1 corresponds to a non-punctured symbol, the value 0 to a punctured symbol. The case corresponding to R.sub.pd=4/16 can be represented more simply by means of N=8, giving R.sub.pd=2/8, the resulting information/redundancy symbols being 01111110/11000001. The case R.sub.pd=0/16 and 8/16 can more simply be represented by means of N=4, giving R.sub.pd=0/4 and 2/4, the resulting information/redundancy symbols being 1111/1000 for R.sub.pd=0/4 and 1100/1001 for R.sub.pd=2/4.

TABLE-US-00001 R.sub.pd R.sub.c A.sub.0 A.sub.1 A.sub.2 A.sub.3 A.sub.4 Puncturing pattern: information/redundancy symbols 0/16 0.8 0 0 0 9 48 1111111111111111/1000100010001000 2/16 0.84 0 0 2 49 344 1111111110111011/0100000101001100 4/16 0.88 0 0 3 62 566 0111111001111110/1100000111000001 6/16 0.94 0 0 21 424 7490 1110101110101010/0001010001110101 8/16 1.0 0 4 38 358 3310 1100110011001100/1001100110011001 10/16 1.06 1 25 342 4804 66643 1110000010010100/1110100110110010

[0196] The pattern corresponding to the ratio R.sub.pd=10/16 and the higher values are not permissible because they lead to catastrophic puncturing patterns where the rate R.sub.c of the elementary code, depending on the number punctured information symbols, and thus on the ratio R.sub.pd, is greater than 1.

[0197] In a second stage, the mutual information exchanged between the decoders in a uniform interleaving turbo-decoding structure for the permissible puncturing patterns of the above table is measured.

[0198] FIG. 6 shows the mean mutual information exchanged between the extrinsic input and output information of each elementary decoder, for E.sub.b/N.sub.0=1.6 dB, with 16 turbo-decoding iterations and a Gaussian channel. The quantity of mutual information exchanged is all the greater as the junction point is close to the coordinates point (1,1). In the example considered, the two puncturing patterns corresponding to the ratios R.sub.pd of punctured information symbols equal to 2/16 and 2/8 are selected, because the junction points of the curves are closer to the point (1,1) than the junction point of the curves corresponding to R.sub.pd=0.

[0199] In the example of FIG. 7, the uniform interleaver turbocodes built from the two puncturing patterns selected previously are compared in terms of performance in the waterfall and flare regions, using BPSK (binary phase-shift keying) modulation. If the performance criterion chosen is the error rate with a high signal-to-noise ratio, in the flare region, rather than with a low and average signal-to-noise ratio in the waterfall region, preference is given to the puncturing pattern corresponding to R.sub.pd=2/8, with resultant information/redundancy symbols=01111110/11000001. If not, the puncturing pattern corresponding to R.sub.pd=2/16 will be selected.

[0200] Connection rules of the interlacing function are then chosen as a function of the puncturing pattern. As described here above, according to a known rule, the interleaving function must convert a punctured position for an information symbol in the natural order into a punctured position for the corresponding interleaved information symbol. The permissible connections of the interleaver for the punctured information symbols linked to this rule are illustrated in FIG. 18, for a selected puncturing pattern corresponding to R.sub.pd=2/8.

[0201] As described here above, the positions of the non-punctured information symbols are ranked by degree of fragility, in puncturing each of these symbols one by one, and the distance spectrum of the elementary code resulting in each of the cases is determined. The following table gives the first terms of the associated distant spectra and the ranking of the positions as a function of their degree of fragility, for the puncturing pattern of the redundancies 11000001 corresponding to R.sub.pd=2/8.

TABLE-US-00002 Puncturing Ranking by pattern degree of fragility A.sub.0 A.sub.1 A.sub.2 A.sub.3 A.sub.4 considered in rising order 0 0 1880 1060320 465121494 00111110 1 (least fragile position) 0 0 4000 2003510 671273377 01011110 2 0 4 3015 1151175 294778989 01101110 4 0 8 140 2229 35176 01110110 6 (most fragile position) 0 2 2256 1275364 320347391 01111010 3 0 4 3019 1152688 148963135 01111100 5

[0202] The first connection rule consisting in connecting the most fragile positions to the least fragile positions, for the non-punctured information symbols, by means of the interleaver can then be applied to all the positions considered or to a part of them only. For example, two cases are considered here.

[0203] In the first case, the most fragile position is connected to the least fragile position. No additional constraint on the positions of the non-punctured information symbols is dictated for the building of the interleaver. This rule leads to a connection mask for the non-punctured information symbols shown in FIG. 19.

[0204] In the second case, a complete cross connection between the positions is made: the most fragile position is connected to the least fragile position, the second most fragile position is connected to the second least fragile position, and so on and so forth. This rule leads to a connection mask for the non-punctured information symbols shown in FIG. 20.

[0205] The second connection rule in which the positions of punctured information symbols are connected as a function of their degree of fragility is then applied. In the example considered, there are only two positions for the punctured information symbols, and the connection mask resulting therefrom is shown in FIG. 21.

[0206] A search is then made for a restricted set of candidates for the adjustment parameters of the previously defined interleaving function. The maximum theoretical value of the minimum spatial cumulated distance of the interleaver for an input message of length K=1504 being equal to 54, the predefined value of the minimum spatial cumulated distance S.sub.min can be fixed at 80% of this value, giving 44. The predefined value of the length of the minimum correlation cycle G.sub.min is fixed in this example at 8. The permissible values for the interleaving period P are the integer values comprised between 1 and 1503 and co-prime with 1504. FIG. 22 shows the values of the minimum spatial cumulated distance S.sub.m, corresponding to these permissible values for a regular interleaver, of which the maximum value of the minimum spatial cumulated distance is equal to 52.

[0207] To determine the restricted set of candidates for the adjustment parameters S(l) for each value of P chosen, four cases were considered. The first is the reference case where no information symbol is punctured, corresponding to R.sub.pd=0, called NDP or No Data Punctured. The puncturing pattern of the first row of the first table here above, where only the redundancies are punctured, is used. In this case, no interleaver giving the turbocode a minimum Hamming distance greater than 15 was found.

[0208] The second case corresponds to the case where only the interleaver connection rule according to which the interleaving function converts the punctured position of an information symbol in the natural order into a punctured position for the corresponding interleaved information symbol, the case known as DPC (for data puncturing constraint) was taken into account. In this case, seven candidate interleavers at the distance 19 were found.

[0209] The third case corresponds to the case where the above-mentioned rule, the first case of the first rule and the second connection rule were taken into account, this case being called DPPC1 (Data and Parity Puncturing Constraint 1). In this case, 14 candidate interleavers at the distance 19 were found.

[0210] The fourth case corresponds to the case where the above-mentioned rule, the second case of the first rule and the second connection rule were taken into account. This case is called DPPC2 (Data and Parity Puncturing Constraint 2). In this case, 40 candidate interleavers at the distance 19, and one additional interleaver at the distance 20, were found with search times of the same order of magnitude for the four cases described.

[0211] The table below gives the four best interleavers determined for each case as well as the values obtained for the minimum spatial cumulated distance S.sub.min and the length of the minimum correlation cycle G.sub.min.

TABLE-US-00003 Case S.sub.min G.sub.min P S(0) S(1) S(2) S(3) S(4) S(5) S(6) S(7) NDP 45 8 399 0 792 630 829 1010 90 1471 658 DPC 45 8 227 0 495 998 280 1090 734 361 362 DPPC1 45 8 699 0 289 1452 1292 1349 391 417 874 DPPC2 45 8 651 0 89 528 852 1501 1396 688 490

[0212] The first three terms of the distance spectrum of the corresponding turbocodes are given in the following table. The value w.sub.free corresponds to the cumulated input weight of the code words at the minimum Hamming distance d.sub.0.

TABLE-US-00004 Case w.sub.free d.sub.0 d.sub.1 d.sub.2 A.sub.d.sub.0 A.sub.d.sub.1 A.sub.d.sub.2 NDP 5640 15 16 17 1128 4512 7708 DPC 4324 19 20 21 752 1880 5264 DPPC1 2444 19 20 21 376 2444 3572 DPPC2 10716 20 21 22 1504 3008 6016

[0213] In this example, the puncturing of the information symbols increases the minimum Hamming distance of the turbocode. The application of the first connection rule in partial form and of the second rule, corresponding to the DPPC1 case, does not in this case enable an increase in distance as compared with the known DPC codes, even if the number of code words at the minimum distance d.sub.0 is lower. However, the application of the first connection rule in complete form and of the second rule corresponding to the DPPC2 case makes it possible to gain one distance point as compared with the known DPC codes for which the only rule taken into account is the rule according to which the interleaving function converts the punctured position of an information symbol in the natural order into a punctured position for the corresponding interleaved information symbol.

[0214] A second example of the building of an interleaver 20 is described with reference to FIGS. 23 to 25. This example differs from the previous example in that the length of the input digital message is equal to K=6144.

[0215] Since the distance spectrum of the elementary code does not depend on the value of the length K of the input digital message, the puncturing patterns selected for the previous example are also valid.

[0216] FIG. 23 shows the mutual mean information exchanged between the extrinsic input and output information of each elementary decoder. The conclusions are similar to those obtained for K=1504: the patterns selected according to this criterion correspond to the ratios R.sub.pd of punctured information symbols equal to 2/16 and 2/8.

[0217] FIG. 24 shows the error rate curves of the turbocodes with uniform interleaving built from three puncturing patterns selected at the previous step. The conclusion is also identical with that of the previous example: should low error rates be sought, especially for FER<10.sup.6, preference is given to the puncturing pattern corresponding to R.sub.pd=2/8, the resulting information/redundancy symbols being 01111110/11000001.

[0218] Since the selected puncturing pattern is the same as in the previous example, the choice of the connection rules of the interleaving function related to the puncturing can directly re-utilize the previously obtained results.

[0219] A search is then made for a restricted set of candidates for the adjustment parameters of the previously defined interleaving function. The maximum theoretical value of the minimum spatial cumulated distance of the interleaver for an input message of length K=6144 being equal to 110, the predefined value of the minimum spatial cumulated distance S.sub.min can be fixed at 65% of this value, i.e. 75. The predefined value of the length of the minimum correlation cycle G.sub.min is fixed in this example at 8. The permissible values for the interleaver period P are the integer values comprised between 1 and 6143 and co-prime with 6144. FIG. 25 shows the values of the minimum spatial cumulated distance S.sub.min corresponding to permissible values for a regular interleaver.

[0220] To determine the restricted set of candidates for the adjustment parameters S(l) for each value of P chosen, only the three first cases described here above were considered, namely the cases NDP, DPC and DPPC1.

[0221] In the NDP case, no interleaver giving the turbocode a minimum Hamming distance greater than 16 was found. In the DPC case, six candidate interleavers at the distance 22 were found and in the DPPC1 case 78 candidates interleavers at the distance 22 were found for search times of the same order of magnitude.

[0222] The following table gives the four best interleavers determined for each case, as well as the values obtained for the minimum spatial cumulated distance S.sub.min and the length of the minimum correlation cycle G.sub.min.

TABLE-US-00005 Case S.sub.min G.sub.min P S(0) S(1) S(2) S(3) S(4) S(5) S(6) S(7) NDP 75 9 83 0 3340 732 2196 2877 391 481 4095 DPC 77 8 1045 0 727 3195 2775 4053 361 4517 1652 DPPC1 75 8 3773 0 4647 691 511 3541 6009 1773 900

[0223] The first three terms of the distance spectrum of the corresponding turbocodes are given in the following table.

TABLE-US-00006 Case w.sub.free d.sub.0 d.sub.1 d.sub.2 A.sub.d.sub.0 A.sub.d.sub.1 A.sub.d.sub.2 NDP 30720 16 17 18 4608 6912 16128 DPC 77568 22 23 24 12288 7680 24756 DPPC1 67584 22 23 24 10752 6144 19968

[0224] In this example too, the puncturing of the information symbols increases the minimum Hamming distance of the turbocode. The application of the first connection rule in partial form and the second rule corresponding to the case DPPC1 does not, in this instance, enable an increase in distance as compared with the known DPC codes, even if the number of code words at the minimum distance d.sub.0 is smaller, but it enables the search process to be more efficient and to produce a greater number of the right sets of parameters.

[0225] A third example of the building of an interleaver 20 is described with reference to FIGS. 26 to 31. This example differs from the previous example in that the encoding rate is equal to R=4/5 and the length of the input digital message is equal to K=1504.

[0226] The table below lists the best puncturing patterns in terms of distance spectrum of the elementary codes that have been obtained for N=16. The case corresponding to R.sub.pd=0/16 can be more simply represented by means of N=8, i.e. R.sub.pd=0/8, the resultant information/redundancy symbols being 11111111/01000000. The case R.sub.pd=4/16 can more simply be represented by means of N=4, giving R.sub.pd=1/4, the resultant information/redundancy symbols being 1110/1000.

TABLE-US-00007 R.sub.pd R.sub.c A.sub.0 A.sub.1 A.sub.2 A.sub.3 A.sub.4 Puncturing pattern: information/redundancy symbols 0/16 0.88 0 0 4 72 645 1111111111111111/0100000001000000 2/16 0.94 0 0 24 525 8732 0111111111111101/1100000000000010 4/16 1.0 0 4 42 424 4204 1110111011101110/1000100010001000 6/16 1.06 1 25 379 5412 77412 1111001110110001/0001011100100000

[0227] The patterns corresponding to the ratio R.sub.pd=6/16 and to the higher values are not permissible because they lead to catastrophic puncturing patterns where the rate R.sub.c of the elementary code is greater than 1.

[0228] In a second stage, the mutual information exchanged between the decoders in a turbo-decoding structure with uniform interleaving for the permissible puncturing patterns of the above table is measured. FIG. 26 shows the mean mutual information exchanged between the extrinsic input and output information of each elementary decoder, for E.sub.b/N.sub.0=2.55 dB, with 16 turbo-decoding iterations and a Gaussian channel. In the example considered, the only puncturing pattern corresponding to the ratio R.sub.pd of the punctured information symbols equal to 2/16 is selected because the junction points of the curves are closer to the point (1,1) than the junction point of the curves corresponding to R.sub.pd=0.

[0229] The uniform interleaver turbocodes built from the puncturing patterns envisaged previously are compared in terms of performance in the waterfall and flare regions, as shown in FIG. 27. These results confirm the choice of the puncturing pattern corresponding to R.sub.pd=2/16, with resultant information/redundancy symbols=0111111111111101/1100000000000010.

[0230] For the example considered, the permissible connections of the interleaver for the punctured information symbols linked to the rule according to which the interleaving function must convert a punctured position for an information symbol in the natural order into a punctured position for the corresponding interleaved information symbol are illustrated in FIG. 28.

[0231] As described here above, the positions of the non-punctured information symbols are then ranked by degree of fragility, and the distance spectrum of the elementary code resulting in each of the cases is determined. The following table gives the first terms of the associated distance spectra and the ranking of the positions as a function of their degree of fragility for the selected puncturing pattern corresponding to R.sub.pd=2/16.

TABLE-US-00008 Ranking by Order Puncturing pattern degree of Number of selected fragility in of the information rising Simplified position A.sub.0 A.sub.1 A.sub.2 A.sub.3 A.sub.4 symbols order ranking 1 0 0 3503 2200764 946127360 0011111111111101 1 (least 1 fragile position) 2 0 2 6371 3140138 1138244658 0101111111111101 4 2 3 0 16 491 13686 376258 0110111111111101 12 4 4 0 8 6047 2331934 606872251 0111011111111101 9 3 5 0 8 6032 2327999 527349550 0111101111111101 6 3 6 0 2 6125 3274279 996842927 0111110111111101 3 2 7 0 16 536 16292 359330 0011111011111101 13 5 8 0 16 489 13457 113075 0111111101111101 11 4 9 0 2 6376 3144441 735019476 0111111110111101 5 2 10 0 16 536 16307 68224 0111111111011101 14 (most 5 fragile position) 11 0 8 6038 2332485 160321914 0111111111101101 7 3 12 0 8 6042 2328199 377642859 0111111111110101 8 3 13 0 2 6123 3272599 750308910 0111111111111001 2 2 15 0 8 6047 2334859 381315178 0111111111111100 10 3

[0232] In this example, the position No. 10 is considered to be the most fragile. The position No. 7 presents a similar level of fragility and could also be chosen. Similarly, in this example, several groups of positions have very close degrees of fragility: this is the case for example of the positions No. 2, No. 6, No. 9 and No. 13 on the one hand and No. 4, No. 5, No. 11, No. 12 and No. 14, on the other hand. When the positions No. 2, No. 6, No. 9 or No. 13 are punctured, the first term of multiplicity is identical and equal to 2 while the second terms are close, ranging from 6123 to 6176. Similarly, when the positions No. 4, No. 5, No. 11, No. 12 or No. 14 are punctured, the first multiplicity term is identical and equal to 8, while the second terms are close, ranging from 6032 to 6047. The choice of either of these positions within the same group during the ranking process therefore has only a low impact on the performance of the resultant interleavers. It is thus possible to assign them the same degree of reliability as represented in the simplified ranking column of the table here above.

[0233] As above, the first case of the first connection rule is applied, the most fragile position being connected to the least fragile position, leading to a connection mask for the non-punctured information symbols represented in FIG. 29.

[0234] The second case described here above is also applied: a complete cross connection between the positions is performed, leading to a connection mask for the non-punctured information symbols represented in FIG. 30.

[0235] The second connection rule consisting of the connection of the punctured information symbols as a function of their degree of fragility is then applied. In the example considered, there are only two positions for the punctured information symbols, the connection mask resulting therefrom is represented in FIG. 31.

[0236] A search is then made for a restricted set of candidates for the adjustment parameters of the previously defined interleaving function. In the example considered, the predefined value of the minimum spatial cumulated distance S.sub.min is fixed at 70% of its maximum theoretical value for K=1504, giving 39. The predefined value of the length of the minimum correlation cycle G.sub.min is fixed in this example at 8.

[0237] To determine the restricted set of candidates for the adjustment parameters S(l) for each value of P chosen, the four cases NDP, DPC, DPPC1 and DPPC2 described here above were considered.

[0238] In the NDP case, no interleaver conferring a minimum Hamming distance greater than 9 on the turbocode was found. In the DPC case, two candidate interleavers at the distance 11 were found, in the DPPC1 case, six candidate interleavers at the distance 11 were found, and in the DPPC2 case, 23 candidate interleavers at the distance 11 were found.

[0239] The table here below gives the four best interleavers determined for each case, as well as the values obtained for the minimum spatial cumulated distance S.sub.min and the length of the minimum correlation cycle G.sub.min.

TABLE-US-00009 Case S.sub.min G.sub.min P (S(0) . . . S(15)) NDP 39 8 725 (0, 250, 1224, 239, 981, 48, 236, 449, 30, 856, 1487, 1228, 1440, 1372, 293, 93) DPC 39 8 267 (0, 1436, 521, 1492, 1048, 1142, 1337, 957, 57, 1125, 740, 189, 56, 650, 852, 158) DPPC1 39 8 583 (0, 1107, 1412, 1038, 909, 1250, 546, 1366, 958, 1445, 299, 178, 1273, 96, 1212, 1487) DPPC2 39 8 365 (0, 1261, 1374, 1279, 417, 867, 549, 514, 730, 474, 1359, 285, 927, 670, 11786, 1078)

[0240] The first three terms of the distance spectrum of the corresponding turbocodes are given in the following table.

TABLE-US-00010 Case w.sub.free d.sub.0 d.sub.1 d.sub.2 A.sub.d.sub.0 A.sub.d.sub.1 A.sub.d.sub.2 NDP 12220 9 10 11 2350 8554 29516 DPC 10434 11 12 13 1880 5358 16732 DPPC1 4888 11 12 13 940 4606 12878 DPPC2 4324 11 12 13 752 4794 15134

[0241] A fourth example of the building of an interleaver 20 is described with reference to FIGS. 32 and 33. This example differs from the previous example in that the length of the input digital message is equal to K=6144.

[0242] Since the distance spectrum of the elementary code does not depend on the value of the length K of the input digital message, the puncturing patterns selected for the previous example are also valid.

[0243] FIG. 32 shows the mean mutual information exchanged between the extrinsic input and output information of each elementary decoder. The pattern selected according to this criterion corresponds to the ratio R.sub.pd of punctured information symbols equal to 2/16.

[0244] The uniform interleaver turbocodes built from the puncturing patterns envisaged previously are compared in terms of performance in the waterfall and flare regions as shown in FIG. 33. These results confirm the choice of the puncturing pattern corresponding to R.sub.pd=2/16, with the resultant information/redundancy symbols=0111111111111101/1100000000000010.

[0245] Since the selected puncturing pattern is the same as in the previous example, the choice of the connection rules of the interleaving function linked to the puncturing can directly re-utilize the previously obtained results.

[0246] A search is then made for a restricted set of candidates for the adjustment parameters of the previously defined interleaving function. In the example considered, the predefined value of the minimum spatial cumulated distance S.sub.min is fixed at 70% of its maximum theoretical value for K=6144, i.e. 80. The predefined value of the length of the minimum correlation cycle G.sub.min is fixed in this example at 8.

[0247] To determine the restricted set of candidates for the adjustment parameters S(l) for each value of P chosen, only the first three cases described here above were considered, namely the cases NDP, DPC and DPPC1.

[0248] In the NDP case, no interleaver conferring minimum Hamming distance greater than 10 on the turbocode was found. In the DPC case, 249 candidate interleavers at the distance 12 were found, and in the DPPC1 case 499 candidate interleavers at the distance 12 were found, and eight candidate interleavers at the distance 13.

[0249] The table here below gives the four best interleavers determined for each case, as well as the values obtained for the minimum spatial cumulated distance S.sub.min and the length of the minimum correlation cycle G.sub.min.

TABLE-US-00011 Case S.sub.min G.sub.min P (S(0) . . . S(15)) NDP 80 8 4741 (0, 3987, 2144, 4792, 5501, 3772, 3569, 5513, 1966, 4855, 3369, 3527, 349, 6130, 2295, 807) DPC 80 8 3607 (0, 5579, 1681, 1714, 12, 3337, 140, 586, 1353, 3509, 879, 774, 4117, 850, 876, 5393) DPPC1 80 8 953 (0, 801, 3826, 5118, 210, 1698, 6065, 684, 5076, 2695, 4119, 5250, 775, 3768, 624, 11)

[0250] The first three terms of the distance spectrum of the corresponding turbocodes are given in the following table.

TABLE-US-00012 Case w.sub.free d.sub.0 d.sub.1 d.sub.2 A.sub.d.sub.0 A.sub.d.sub.1 A.sub.d.sub.2 NDP 1536 10 11 12 384 3840 25728 DPC 5376 12 13 14 768 7680 15360 DPPC1 14208 13 14 15 2304 5760 28032

[0251] A fifth example of the building of an interleaver 20 is described with reference to FIGS. 34 to 37. This example differs from the previous examples in that the elementary codes of the first and second encoders C1, C2 of the turbo-encoders are the code CSR (13,15,17).sub.8, the encoding rate being equal to R=1/3 and the length of the input digital message being equal to K=1504.

[0252] The table here below lists the best puncturing patterns in terms of distance spectrum of the elementary codes that were obtained for the puncturing period N=8.

TABLE-US-00013 Puncturing pattern: R.sub.pd R.sub.c A.sub.4 A.sub.5 A.sub.6 A.sub.7 A.sub.8 A.sub.9 A.sub.10 information/redundancy 1/redundancy 2 symbols 0/8 0.5 0 0 2 0 10 0 49 11111111/11111111/00000000 2/8 0.53 0 3 20 33 83 202 311 11101110/10110000/01011111 4/8 0.57 0 6 12 35 90 223 479 10101010/11111111/01000100 6/8 0.62 2 26 66 165 500 1526 2845 10100000/11101111/01011010 8/8 0.66 3 11 35 114 378 1253 4147 00000000/11111111/10101010

[0253] All the values of the ratio R.sub.pd are permissible because they lead to rate values R.sub.c of the elementary code lower than 1.

[0254] Performance of the uniform interleaver turbocodes built from the puncturing patterns of the table here above are compared in the waterfall and flare regions as represented in FIG. 34. The puncturing pattern corresponding to R.sub.pd=6/8 with resultant information/redundancy symbols=10100000/11101111/01011010 is chosen.

[0255] For the example considered, the permissible connections of the interleaver for the punctured information symbols linked to the rule according to which the interleaving function must convert a punctured position for an information symbol in the natural order into a punctured position for the corresponding interleaved information symbol are illustrated in FIG. 35.

[0256] As described here above, the first connection rule in which positions of non-punctured information symbols are connected as a function of their degree of fragility is then applied. In the example considered, there are only two positions for the non-punctured information symbols, the connection mask resulting therefrom is shown in FIG. 36.

[0257] The second connection rule consisting in connecting positions of punctured information symbols as a function of their degree of fragility is then applied. In the example considered, FIG. 37 illustrates the determining of two degrees of fragility of the positions as a function of the number of punctured redundancy symbols: the positions identified by dashes, corresponding to a punctured redundancy symbol, are more fragile than the positions identified in unbroken lines, corresponding to no punctured redundancy symbols. According to this rule, each of these positions No. 1, 4 and 6 are connected to one of the positions Nos. 3, 5 and 7.

[0258] As search is then made for a restricted set of candidates for the adjustment parameters of the previously defined interleaving function. In the example considered, the predefined value of the minimum spatial cumulated distance S.sub.min is fixed at 80% of its maximum theoretical value for K=1504, giving 44. The predefined value of the length of the minimum correlation cycle G.sub.min is fixed in this example at 8.

[0259] To determine the restricted set of candidates for the adjustment parameters S(l) for each value of P chosen, the three cases NDP, DPC and DPPC1 described here above were considered. The DPPC1 case corresponds to the case where the first connection rule and the second connection rule as described here above have been applied.

[0260] In the NDP case, no interleaver conferring a minimum Hamming distance greater than 49 on the turbocode was found. In the DPC case, two candidate interleavers at the distance 59 were found, and in the DPPC1 case one candidate interleaver at the distance 61 was found.

[0261] The table here below gives the best interleavers determined for each case, as well as the values obtained for the minimum spatial cumulated distance S.sub.min and the length of the minimum correlation cycle G.sub.min.

TABLE-US-00014 Case S.sub.min G.sub.min P S(0) S(1) S(2) S(3) S(4) S(5) S(6) S(7) NDP 47 8 59 0 619 1198 1496 1209 1260 917 973 DPC 45 8 1219 0 938 732 1427 739 378 449 1297 DPPC1 45 8 487 2 462 106 191 131 342 601 1197

[0262] The first three terms of the distance spectrum of the corresponding turbocodes are given in the table here below.

TABLE-US-00015 Case w.sub.free d.sub.0 d.sub.1 d.sub.2 A.sub.d.sub.0 A.sub.d.sub.1 A.sub.d.sub.2 NDP 2632 49 50 51 376 564 940 DPC 752 59 60 61 188 376 376 DPPC1 3196 61 62 63 376 376 564

[0263] An interleaver thus built can then be used in a turbo-encoder according to the invention. In particular, as already indicated, an interleaver of this kind distributes the information symbols of the input message in Q layers of the interleaved input message in complying with the interleaving function defined from the puncturing pattern or patterns according to the relationship:

(i)=Pi+S(i mod Q)mod K=Pi+S(l)mod K=Pi+(T.sub.l+A.sub.lQ)mod K

[0264] FIGS. 38 to 41 show the performance in terms of binary error rate or bit error rate BER and the frame error rate FER of the punctured turbocodes using the different interleaving configurations proposed. Significant gains are obtained relative to the LTE turbocode which uses a QPP interleaving and the puncturing technique known as rate matching.

[0265] FIG. 38 represents the bit error rate curves of the turbocode for different interleaving configurations for different encoding rates R, with a Gaussian channel, a BPSK modulation, a length of the input digital message equal to K=1504, and 16 decoding iterations using the BCJR (Bahl-Cocke-Jelinek-Raviv) algorithm. The TUB indication designates the truncated union bound corresponding to the first terms of the union bound applied to the error probability per pair. The union bound also called Boole's inequality defines the probability of occurrence of any unspecified event taken in a set of discrete events, and is smaller than or equal to the sum of the probabilities of each of the events taken separately. The probability of error per pair P(x,x) corresponds to the probability that the decoder will decode the code word x while the code word x has been transmitted. The union bound makes it possible to obtain the lower bound for the probability that the decoder will make a mistake when the code word x has been transmitted: Pe (x)x P(x, x). To obtain the TUB, we consider only the terms of the sum corresponding to the code words x closest to x instead of all the code words x possible.

[0266] FIG. 39 represents the frame error rate curves on the Gaussian channel of the turbocode for different interleaving configurations for different encoding rates R, with a Gaussian channel, a BPSK modulation, an input digital message length equal to K=1504 and 16 BCJR decoding iterations.

[0267] FIG. 40 represents the bit error rate curves of the turbocode for different interleaving configurations, for different encoding rates R, with a Gaussian channel, a BPSK modulation, an input digital message length equal to K=6144 and 16 BCJR decoding iterations.

[0268] FIG. 41 represents the frame error rate curves on a Gaussian channel of the turbocode for different interleaving configurations, for different encoding rates R, with a Gaussian channel, a BPSK modulation, an input digital message length equal to K=6144 and 16 BCJR decoding iterations.

[0269] The invention is not limited to the examples that have just been described.

[0270] Possible applications of the invention include transmission systems under the future fifth-generation or 5G mobile telephony standard. These systems will in fact have to respond to new cases of use requiring very reliable connections and/or very efficient connections from the viewpoint of spectral use. The corresponding transmission modes should also make use of error correction codes that have better performance at low error rates than the current codes under the 3G and 4G standards.

[0271] The invention can be used in applications for which security is of prime importance in the context of what is known as mission critical communications, applications such as those related to the coordination of vehicles, control of electrical networks, or broadcasting applications where the return channel cannot be used for the retransmission of data, or in all applications requiring low latency and for which the use of the return channel must be avoided as much as possible, for example in interactive online gaming applications.

[0272] The expression comprising one must be understood to mean comprising at least one unless otherwise specified.

[0273] Although the present disclosure has been described with reference to one or more examples, workers skilled in the art will recognize that changes may be made in form and detail without departing from the scope of the disclosure and/or the appended claims.