ENCODING METHOD FOR QUASI-PERIODIC FADING CHANNEL

The present invention relates to a method of error correction coding for a channel with quasi-periodic fade, such as the RSC (railroad satellite channel). According to an embodiment, it uses a block code (N, K) in which the parity check matrix comprises a sub-matrix obtained by horizontal concatenation of a plurality of identity matrices. The coding applies preferably to the level of the link layer, on data packets of the physical layer, without prior interleaving of said packets.

DETAILED DESCRIPTION OF PARTICULAR EMBODIMENTS

We will consider hereafter a channel with quasi-periodic fade in the sense defined above, such as for example the RSC presented above.

FIG. 1represents an application context of the present invention.

The information symbols (bits for example) to be transmitted are grouped together in the form of packets, known as source packets, from an applicative layer. In the case of a DVB-S2 broadcast, for example, these packets are MPEG-TS (MPEG transport stream) packets.

These packets are preferably subject to an error correction coding at the level of the link layer (2ndlayer of the OSI model) in the encoder C2. More precisely, the encoder C1codes a plurality K of incident packets P1, . . . , PKas source packets into a plurality N>K of coded packets. When the coding is systematic, this plurality of coded packets is constituted of source packets P1, . . . , PK, followed by M=N−K parity packets PK+1, . . . , PN(of same size as the source packets) representing the redundancy of the code. A parity packet is obtained as a sum, bit by bit, of several source packets, formalised by a parity check.

The packets P1, . . . , PNmay then undergo a second error correction coding at the level of the physical layer (1stlayer of the OSI model) in the encoder C1. More precisely, each packet Pk, k=1, . . . , K, of size q (q bits) is then coded in a packet P′kof size q′>q. Here again, if the coding is systematic, the packet P′kwill be constituted of q initial bits and q′-q parity bits representing the redundancy of the code. It is also possible to group together several packets Pi, . . . , Pjinto a super-packet, Pi-jand to apply the error correction coding to this super-packet. One then obtains a new packet, P′i-jwhich, in the case of a systematic code, contains the bits of the super-packet, in other words all of the initial packets, Pi, . . . , Pj, as well as the parity bits corresponding to the redundancy of the code.

If needs be, an interleaving (not represented) may be provided at the packet level before the encoder C2and within each packet (or super-packet) before the encoder C1.

In all cases, after transmission on the channel with periodic fade, the packets P′kthereby coded are treated by the receiver as indicated hereafter.

At the level of the physical layer, each of the packets P′kis decoded by the decoder D1. If the decoding is successful, the packet Pkis transmitted to the link layer. On the other hand, if the decoding fails (for example, when the channel undergoes a fade) the packet Pkcannot be recovered and is considered as erased. The information of the erased packet is then transmitted to the link layer.

At the level of the link layer, each of the packets Pkis either correctly received, or considered as erased. The decoder D2then performs a decoding of the sequence of packets P1, . . . , PNin which one or more packets can be erased, to recover the initial packets P1, . . . , PK.

One will speak more specifically of channel with quasi-periodic erasure when, at the level of the link layer (or of an upper layer), the packets of this layer are periodically erased on account of periodic fades intervening at the level of the underlying physical layer. The term channel with periodic erasure will thus be consequently understood as a particular case of a channel with periodic fade.

The coding method according to the present invention is preferably implemented by the encoder C2and then applies to the aforementioned packets.

Alternatively, the coding method according to the present invention may be implemented by the encoder C1and then applies to the data of the physical layer (if needs be after interleaving).

Hereafter, in order to conserve a unitary presentation, we will designate by information symbols either data of the physical layer (bits for example) or packets of such data from the link layer (or instead of an upper layer). In all cases, the block of information symbols is noted s1, . . . , sKand the block of coded symbols is noted c1, . . . , cN. It will be understood that according to the envisaged level (physical, link or upper) the coded symbols are themselves data of the physical layer or packets of the link layer (or the upper layer).

Nevertheless it will be understood that, when the present invention is implemented at the level of the link layer, the decoding has simply to correct erasures of symbols (packets). One then speaks of an erasure decoding. In fact, the input of the decoder is constituted of the packets correctly decoded at the level of the physical layer. The fact that the packets have been correctly decoded may be verified for example by using a CRC code. The other packets (of which the decoding has failed) are considered as being erased.

When the coding method is implemented at the level of the physical layer, the receiver will use a conventional decoding of errors. The input of such a decoder is constituted of log likelihood ratios (LLRs), calculated from the signal observed at the output of the channel. When the channel goes through a fade, these LLRs have values very close to zero and may be considered as erasures, a LLR equal to zero signifying that one does not have any information on the value of the corresponding bit.

Whatever the level of implementation of the coding method, the size N of the code is chosen so that at the most one periodic fade (or bad state) of the channel intervenes during the transmission of a block of N coded symbols c1, . . . , cN. In other words, if one notes T the period of recurrence of the first state (bad state) of the channel, and ρ the output of the coded symbols, the size N will be chosen such that N<ρT.

One notes moreover τ the maximum duration of the fade of the channel, or in an equivalent manner the maximum duration of the first state. The maximum number of symbols erased, during the duration of this fade, is thus m=pτ.

The size N is chosen as a multiple of m, N=nm wherenis a whole number greater than or equal to 2, and satisfying N<ρT.

The coding method according to the invention uses a code per block (N, K) which may be conventionally defined by its generator matrix G of size K×N or by its parity check matrix H of size (N−K)×N.

It will be recalled that if s=(s1, . . . , sK) is the vector constituted of the information symbols, the associated code word c is given by the vector:

The words c of the code (N, K) satisfy:

where .Tsignifies the matrix transposition, the generator and parity check matrices being linked by the relation:

Moreover, if the code is systematic, its generator matrix has the form:

where IKis the identity matrix of size K×K and P is the parity matrix of size K×(N−K). In this case, the parity check matrix is expressed as:

where IN-Kis the identity matrix of size (N−K)×(N−K).

According to a first embodiment of the invention, one considers that the second state of the channel (good state) does not introduce errors (physical layer) or erasures (physical layer or link layer) in the information symbols. This situation intervenes in particular when the coding method applies to the link layer (the information symbols are then packets) and when the error correction coding (C1) at the level of the physical layer is sufficiently efficient to correct the errors/erasures intervening in the second state of the channel.

FIG. 2Arepresents in a schematic manner the structure of a parity check matrix used by the coding method according to the first embodiment of the invention.

It may be noted that this matrix is constituted of the concatenation ofn=N/m identity matrices Imof size m×m, i.e.:

The code is here systematic with N−m information symbols and m parity symbols since the parity matrix has the form of the expression (5). It will be assumed that the m parity symbols correspond to the final matrix Im(the furthest on the right inFIG. 2).

Each line of the parity check matrix corresponds to a check and involvesnsymbols (n−1 information symbols and a parity symbol), the check being expressed as a XOR sum of thesensymbols. Given the particular structure of the parity check matrix, the different symbols intervening in a check i (line i) occupy the positions i, i+m, i+2, . . . , i+(n−1)m in the code word (in other words the columns having these indices in the matrix H).

When an erasure of length m (symbolised by a dotted line above the matrix) takes place, it only affects at the most m consecutive symbols of the code word. Thus, for a given parity check, i, the erasure will only affect at the most one symbol (in position j in the code word) since any preceding symbols (in positions j−m, j−2m, . . . ) and any following symbols (in positions j+m, j+2m, . . . ) intervening in this check are situated outside of the erasure zone. It is thus always possible to restore the erased symbol by means of the check in question.

According to a more general version represented inFIG. 2B, each identity matrix Imappearing in (6) may be replaced by a triangular matrix (lower or upper), of size m×m i.e.:

where the matrices Tm(n), n=1, . . . ,nare triangular matrices (all lower or instead all upper) in which the diagonal elements are non-zero, in other words equal to 1. It will be recalled that an upper triangular matrix is a matrix in which the elements situated below the diagonal are all zero and that a lower triangular matrix is a matrix in which the elements situated above the diagonal are all zero.

According to this version, the parity matrix appears as a horizontal concatenation of matrices either all upper triangular or instead all lower triangular, and in which the diagonal elements are non-zero. It will be understood that this version is more general than the preceding version in so far as the identity matrix may be considered as a particular case of matrix Tm(n).

In a particular example of embodiment, the triangular matrices Tm(n), n=1, . . . ,nmay all be identical, in other words: Tm(n)=Tm, ∀n.

It is also possible with the parity matrix structure given by the expression (7) to restore the erased symbols, thanks to the parity check, beginning with the first line containing an erased symbol and continuing by lines of increasing indices, if the triangular matrix is lower, or instead by beginning with the final line containing an erased symbol and by continuing with lines of decreasing indices, if the triangular matrix is upper. In fact, by proceeding in this way, each new line in the direction indicated by the arrows only contains one unknown symbol (erased), since the other symbols are situated either in the erasure zone but have already been restored by means of a preceding parity check (preceding line), or outside of the erasure zone.

The first variant (parity matrix given by the expression (6)) will be favoured when the coding method is implemented at the level of the link layer (or instead of an upper layer), whereas the second variant (parity matrix given by the expression (7)) will be favoured when the coding method is implemented at the level of the physical layer.

In fact, in the first case, the packets in the erasure zone are purely and simply absent (the CRC check at the level of the physical layer having declared them as erroneous), it is thus pointless to envisage a complex parity check. On the other hand, in the second case, certain bits of the erasure zone (bad state of the channel) may contain a useful information (non-zero LLR).

Finally, it will be understood that any permutation of the lines of the parity check matrix (7) conserves the preceding property, such a permutation only corresponding to a change of the order of the parity checks. In other words, the parity check matrix of the code could more generally result from the (horizontal) concatenation ofnmatrices QmTm(n), where Qmis a permutation matrix of size m×m and where Tm(n)has the same definition as previously.

According to a second embodiment of the invention, one considers that errors and/or erasures of short duration may intervene on the channel when it is in its second state (good state).

Thus a code word may be affected either by a long erasure (of at the most m symbols) when the channel is in its first state during the transmission of the word, or by a short erasure and/or errors if the channel is in its second state during this transmission.

FIG. 3represents in a schematic manner the structure of a parity check matrix used by the coding method according to the second embodiment of the invention.

It will be noted that the parity check matrix of the code (N, K) ofFIG. 3is constituted of the (vertical) concatenation of an upper matrix HUof size m×N and of a lower matrix HLof size l×N with l=M−m where M is the number of parity checks.

The upper matrix HUis identical to the matrix H of the first embodiment. For example, the matrix HUmay be constituted of the (horizontal) concatenation ofnidentity matrices Imor ofnmatrices QmTm(n).

The matrix HLis a sparse matrix, in other words a matrix having for elements 0 values and several 1 values.

FIG. 3(dotted lines) represents erasures that have taken place during the transmission of the code on the channel, namely a long erasure when the channel was in its first state and several short erasures (Rice fade) when the channel was in its second state.

The function of the upper matrix HUis to enable the restitution of the symbols erased during a long erasure (first state). The function of the lower matrix HLis to restore the symbols erased during short erasures and/or to correct the errors of the channel in the second state.

It will be understood that, as in the first embodiment, the parity check matrix is defined to within one permutation of its M=N−K lines.

The parity check matrix H represented inFIG. 3nevertheless does not correspond to a systematic code. When a systematic coding is desired, the coding method described hereafter is advantageously implemented.

FIG. 4represents in a schematic manner the structure of a parity check matrix of a code used by the coding method according to a third embodiment of the invention.

It may be noted that the parity check matrix H of the code (N, K) ofFIG. 4is constituted of the (vertical) concatenation of a first upper matrix HUof size m×N and of a lower matrix HLof size l×N with l=M−m where M=N−K is the number of parity checks.

The upper matrix HUis constituted here of the (horizontal) concatenation ofnidentity matrices Imof size m×m.

The lower matrix HLof size l×N is constituted of the (horizontal) concatenation of four elementary matrices, represented from left to right inFIG. 4:a first sparse elementary matrix HL1of size l×K;a second elementary matrix HL2equal to the identity matrix Ilof size l×l;a third sparse elementary matrix HL3of size l×(m−l);a fourth elementary matrix HL4, sub-diagonal, of size l×l. Sub-diagonal matrix designates a matrix in which only the elements of the sub-diagonal are non-zero (in the present instance equal to 1).

The M last columns (on the right ofFIG. 4) correspond to the parity symbols. These M parity symbols may be divided into three groups, noted p1, p2, p3of respective sizes l, m−l, l.

The code (N, K) is systematic since the K information symbols, s1, . . . , sK, are transmitted as such, the M=N−K parity symbols being calculated as follows:a) the m/parity symbols of the group p2are firstly calculated from (XOR sum) information symbols intervening in the m−l first lines of the parity check matrix. More precisely, for the check i, the (l+i)thparity symbol cK+l+i, belonging to the group p2, is obtained by the sum of the Ti information symbols:

One returns to the step (i) by estimating the second parity symbol cK+2, belonging to the group p1, as XOR sum of the information symbols appearing in the second line of the matrix HL1and parity symbols appearing in the second line of the matrix HL3and of the parity symbol cK+m+1that has just been calculated.

FIG. 5illustrates in a schematic manner the different steps of calculating (a), (b)(i), (b)(ii) parity symbols during the coding of the parity symbols.

In the same way, the decoding is relatively simple since one can always come down to the restitution of an erasure/correction of an error by check line. Thus, the complexity of the decoding is linear as a function of the size N of the code.

According to a variant (not represented) of the third embodiment, one may use a code (N, K) defined by the parity check matrix H constituted of the (vertical) concatenation of an upper matrix HUof size m×N and of a lower matrix HLof size l×N, the upper matrix HUbeing obtained by horizontal concatenation ofnmatrices QmTm(n)as in the expression (8), Qmbeing a permutation matrix and the matrices Tm(n)being triangular matrices (all lower or instead all upper, and non-zero diagonal elements), the lower matrix HLbeing constituted of the horizontal concatenation of four elementary matrices, HL1, HL2, HL3, HL4, the first and third elementary matrices HL1and HL3being identical to those described previously, the second elementary matrix HL2being triangular and of same nature as Tm(lower or upper) and the fourth elementary matrix HL4only having non-zero elements below or above its diagonal (and thus zero elements on its diagonal), depending on whether Tmis lower or upper triangular.

It is also possible, according to this variant, to calculate firstly the parity symbols of the group p2, then by successive iterations those of the groups p1and p3.

As in the preceding embodiments, the matrix of the parity code is defined to within one permutation of its lines, a permutation of the lines equivalent to a permutation of the parity checks.

Whatever the embodiment envisaged, the code (N, K) defined by the parity matrices given above is well adapted to a channel with erasure periodic and has a minimum redundancy.

When the coding method of the invention is applied at the link level, a prior interleaving of the packets is not necessary, and the latency is not affected, which is particularly important for services in streaming mode.

It also ensues that the corresponding coding circuit does not require important memory resources.

FIGS. 6A and 6Brepresent the symbol error rate at the level of the link layer, in other words the packet error rate when the coding method is implemented within the context of a transmission on RSC.

The distance between the power arches, on which depends the period of the erasure of the RSC in the first state, has been taken equal to 50 m. The width of the power arch in the axis of movement of the train, on which depends the duration of the periodic erasure, has been taken equal to 87 cm. The probability that a symbol undergoes an erasure at the level of the physical layer (due to a deep fade) is none other than the ratio between the width of the power arch and the distance between power arches, namely 1.54 10−2.

It is assumed that the communication between the satellite and the terminal obeys the DVB-S2 standard with a QPSK modulation, a modulation speed of 27.5 Mbaud, an FEC code (at the level of the physical layer) of length 16200 bits and output 4/9.

In the examples illustrated, the coding method according to the present invention has been applied to the level of the link layer, the information symbols being MPEG-TS packets of 188 octets. The dimensions of the code were N=9064; m=824; l=626 (and thus M=1450).

FIGS. 6A and 6Bcorrespond to a train speed of 60 km/h and 300 km/h, respectively.

In the two figures, the solid curve in solid line600represents the packet error rate as a function of the signal to noise ratio (SNR) of the RSC (periodic deep fade and random fade of Rice type). The curve in broken line601represents the packet error rate in the absence of periodic fades (random fade of Rice type only, in other words channel constantly in the second state).

The curve603represents the packet error rate on the RSC after the coding according to the first embodiment, thus with an output of (N−m)/N=0.91.

It may be noted that the application of the coding method makes it possible to eliminate completely the deterioration of the packet error rate (more precisely to delete the lower limit of the packet error rate) due to periodic erasure (even at low speed, cf.FIG. 6A) since, in the two figures, curve603has the same slope as curve601.

Curve602represents the packet error rate on this same RSC, after coding according to the third embodiment, thus with an output if (N−m−l)/N=0.84. It will be noted that the l parity symbols/parity checks added make it possible to reduce in a significant manner the residual errors/erasures appearing in the second state of the channel.