WO2015079168A1

WO2015079168A1 - Data packet encoding by means of convolutional codes and deleted packet recovery

Info

Publication number: WO2015079168A1
Application number: PCT/FR2014/053051
Authority: WO
Inventors: Patrick Tortelier
Original assignee: Orange
Priority date: 2013-11-28
Filing date: 2014-11-26
Publication date: 2015-06-04
Also published as: FR3013924A1

Abstract

The invention relates to a method for encoding digital data packets. Said method includes, for N input packets, generating (N+K_-1) first encoded packets and (N+K₂) second encoded packets, the first encoded packets being obtained by a first convolution associated with a first generating polynomial G₁ other than 1, and of degree K_-1, and the second encoded packets being obtained by a second convolution associated with a second generating polynomial G₂ other than 1, and of degree K₂, said generating polynomials being mutually prime. The invention also relates to a method for correcting deletions, including a first phase of recovering deleted encoded packets, and a second phase of decoding non-deleted or recovered encoded packets.

Description

CODING OF DATA PACKETS BY CONVOLUTIVE CODES AND RECOVERY OF ERASED PACKETS

GENERAL AREA

The invention relates to the field of erase correcting codes.

The invention more particularly relates to a method and a device for coding digital data packets, and a method and a device for correcting any erasures affecting coded packets following their transmission in a channel.

STATE OF THE ART

Numerous methods of transmitting identical digital data to a large number of receivers in a channel subject to losses or "erasure" of packets are known from the state of the art. In the case of "broadcast" or "multicast" broadcast over the Internet, packet losses are often caused by congestions at routers. In the case of broadcast or multicast broadcasting on radio channels (MBMS, eMBMS), packet losses may be due to poor quality of some radio links, causing transmission errors that Physical layer corrector coding can not correct: the corresponding data is then marked as erased. In both cases, the different transmission routes between one transmitter and several recipients have different link qualities and suffer different packet losses after data transmission by the transmitter.

A conventional scheme for retransmission of non-received data, made recipient by recipient, would be inefficient because it would imply on the one hand as many return channels in the channel as there are receivers, and on the other hand the retransmission of the same packets to different users, causing significant overflow in the channel, and longer transmission delays.

In order to avoid the introduction of such return channels, it has been proposed to introduce redundancy in the transmitted data so that any user can reconstruct the packets they did not receive thanks to those that he received, without return way or retransmission.

This introduction of redundancy is typically implemented by means of an erasure correction code.

Correction codes for correcting erasures have been known for a long time, for example the "Reed-Solomon" codes, which nevertheless have constraints: indeed, these codes have lengths that are not very flexible, of the form n = 2 ^m -1, m≥ 2, and involve an arithmetic in GF extension bodies (2 ^m ), arithmetic which becomes difficult to implement (at least in software form) for values of m exceeding 10, that is to say say code lengths "> 1023.

To avoid the constraints of Reed-Solomon codes, a class of packet coding methods (hereinafter referred to as "Arai-based methods") has been proposed based on convolutional codes operating on digital data packets (cf. Arai, A. Yamamoto, A. Yamaguchi, S. Fukumoto, and K. Iwasak, "Proceedings of the 2001 Pacific Rim International Symposium on Dependable Computing (PRDC '01). ) ", Pages 258-265, and M. Arai, S. Fukumoto and K. Iwasaki," Expanding coefficients for (n, k, m) convolutional-code-based packet loss recovery, "Computers and Mathematics with Applications, vol. 51, 2006, pp. 247-256).

In the methods according to Arai, data is transmitted in the form of groups of n packets, each group \ (= 1 ', 2''''' ^ in) containing, on the one hand, k packets of information (so we have a systematic coding), and secondly (nk) redundant packets, which is written in the form

^V i = ( ^U i ^P i) = l> ^u i, 2 ^" · · · ^" ; ^"Pi ^2" · · · ^"Pi - *). where the Uf's are the information packets and the Pi's are redundant packets, obtained in the following way:

Pi =! Ϊ́ ^Η ί ⁺ * 2 Nl, l + · ^" + # 1 + 1,1 ^M * -m, l +

S 2 ^u i, + 82.2 ^u i- 2 + - + # 1 + 1.2 ^M / -m, 2 +

This form shows the components of the vectors U, (first column), Uj-i (second column), and so on until Ui _-m . If we write these equations for j = 1, 2, nk, the above equation takes the following matrix form

P. = G ⁾ U. + G ⁽²⁾ U., + - - - + G ^{(m + 1)} U.

where G ^(t) are binary matrices of dimensions (nk) by k.

However, these methods according to Arai have several disadvantages.

A first disadvantage is that it requires the erasures to be in the form of a grouped salvo that must imperatively be preceded and followed by what the authors call a guard space ("guard space" in English), ie say a succession of packets that have not been erased over a length greater than the memory m of the encoder. This constraint on the guard interval is made necessary in particular by the use of generator generatrices sized to correct bursts of predetermined length.

Moreover, in these processes according to Arai, the recovery of the erased packets is done by solving a linear system of equations whose unknowns are the erased packets. Such a resolution is, however, complex to implement.

Finally, these methods according to Arai implement a systematic coding, which has the advantage of obtaining directly (that is to say, without decoding operation) the information packets following the recovery of the erased packets. But as the systematic coding is by definition to transmit clear input packets in the channel, the methods according to Arai have the disadvantage of being unsuited to the transmission of confidential information.

PRESENTATION OF THE INVENTION

An object of the invention is to implement packet coding and erase correction in a channel subject to packet loss or erasure, each of which is simple to implement.

Another object of the invention is to be able to recover erased coded packets without first having to decode any coded packet.

According to a first aspect, it is therefore proposed a method of encoding digital data packets, comprising the following steps:

storing N input packets (P _1; ..., P _N ),

the production of (N + first coded packets (A ^ ..., A _{N + K} defined, for = 1, ..., N + K, by

Gij m-i>

where G ₁ is a first generator polynomial different from 1, and of degree K _lt G is the coefficient of the power term ί of said first generator polynomial G _lt and the input packets of index less than 1 or greater than N are identically zero,

- the production of (N + K ₂₎ first packets encoded [B _1} ..., B _{N + K2)} defined, for n = 1, ..., N + K _2, by

B _N

G _2i iP _n -j, where G ₂ is a second generator polynomial different from 1, and of degree K ₂ , G ₂ is the coefficient of the power term; said second generator polynomial G ₂ , and the input packets of index less than 1 or greater than N are identically zero,

and where the generating polynomials G _i and G ₂ are prime between them.

It is understood that the steps of said coding method do not necessarily take place in the order in which they are presented above.

It should be noted that the present invention does not impose any constraints on the nature of the digital data composing the packets. It may be, for example, bits ("bits"), or elements of an extension body GF 2 ^m ), with m greater than or equal to 2.

It will also be noted that, contrary to the methods according to Arai, the coding method according to the invention in no way imposes the use of systematic coding, and therefore does not require the transmission of clear-text input packets in the channel when the context does not lend itself to it.

As explained in detail below, the fact that the two generator polynomials G ₁ and G ₂ used for coding are prime between them makes it possible to very simply decode the coded packets (following the recovery of the erased coded packets).

According to a second aspect, there is also provided a method of erasure correction, said method comprising the steps of:

storing (N + K) first packets to be processed {A _1} ..., A _{N + K} ) and (N + K) second packets to be processed (B _i ..., B _{N + K} ), each packet to be processed being a non-erased packet or a null packet representative of an erased packet,

calculating (N + 2K) syndromes ..., S _{N + 2K} ) defined, for n = 1, ..., N + 2K, by

where G _{1 <£} are K first predetermined coefficients defining a first polynomial

K j = o

different from 1, and the G _{2 i} are K second predetermined coefficients defining a second polynomial

K

G ₂ (D) = G _2J Di different from 1, and where the packets A _m and B _m are identically zero for m <1 or m> N + K,

- Possible recovery of packets deleted from the syndromes, so that when the calculation of a syndrome involves a single zero packet representative of an erased packet, then the recovered packet corresponding to this erased packet is equal to this syndrome .

The erasure correction method according to the second aspect comprises a step of recovering erased coded packets, which can be implemented independently of the decoding of the received data. In fact, no input packet has to be generated to reconstruct any coded packet that has been erased as a result of its transmission in the channel.

The erasure correction method according to the second aspect also operates without any particular algorithmic constraint on the number of coded packets received. It therefore allows great flexibility on the number N of collectively encoded input packets.

It can therefore be seen that the coding method according to the first aspect and the method of erasure correction according to the second aspect are very flexible in that they can adapt to a large number of different implementation contexts.

According to a third aspect, there is also provided a device for encoding digital data packets comprising: a memory module adapted to memorize N input packets (P _1; ..., P _N ), and

an input packet processing module,

said packet processing module comprising first and second convolutional coding units such as:

- the first convolutional coding unit is configured to produce (N + first packets encoded [A _1} ..., A _{N + K} defined for m = Ι,,, Ν + K _lt pa..

Gij m-i>

where G ₁ is a first generator polynomial different from 1, and of degree K _lt G is the coefficient of the power term ί of said first generator polynomial G _lt and input packets of index less than 1 or greater than N are zero ,

the second convolutional coding unit is configured to produce (N + K ₂ ) first coded packets [B _1} ..., B _{N +} K ₂ ) defined, for n = Ι,.,. , Ν + K ₂ , by

Bn ⁼ Σy = o ^ 2, iPn-j>

where G ₂ is a second generator polynomial different from 1, and of degree K ₂ , G ₂ is the coefficient of the power term; said second generator polynomial G ₂ , and the input packets of index less than 1 or greater than N are zero,

and the generating polynomials G ₁ and G ₂ are prime between them.

According to a fourth aspect, there is also provided an erasure correction device comprising:

a memory module adapted to store (N + K) first packets to be processed (A ^ ..., A _{N + K} ) and (N + K) second packets to be processed (B ₁ ..., B _{N + K} ) each packet to be processed being an undeleted packet or a null packet representative of an erased packet,

a memorized packet processing module adapted to: o calculate (N + 2K) defined syndromes ..., S _{N + 2K} ), for n = 1, ..., N + 2K, by

where G _li are K first predetermined coefficients defining a first polynomial

G ^ D) = G ₁ D)> J

j = 0

G ₂ (D) = G ₂ D ^J j different from 1, and where the packets A _m and B _m are identically zero for m <1 or m> N + K, and

when the calculation of a syndrome involves a single null packet representative of an erased packet, defining a recovered packet corresponding to this erased packet as being equal to this syndrome.

According to a fifth aspect, there is also provided a digital data transmission system comprising at least one transmitting node and at least one receiving node mutually connected by a channel subject to packet erasures, said transmitting node comprising a coding device according to the third aspect, and said receiving node comprising an erasure correction device according to the fourth aspect.

According to a sixth aspect, there is also provided a computer program downloadable from a communication network and / or stored on a computer readable medium and / or executable by a microprocessor, characterized in that it comprises instructions for performing the steps of a method according to the first and / or second aspect, when executed on a computer

According to a seventh aspect, there is also provided an immovable, partially or totally removable data storage means comprising computer program code instructions for executing the steps of a method according to the first and / or second aspect. .

DESCRIPTION OF THE FIGURES

Other features, objects and advantages of the invention will emerge from the description which follows, which is purely illustrative and nonlimiting, and which should be read with reference to the appended drawings in which:

FIG. 1 schematically represents a transmission system according to the invention,

FIG. 2 diagrammatically represents an emitter node included in the transmission system of FIG. 1, according to one embodiment of the invention,

FIG. 3 diagrammatically represents a receiving node included in the transmission system of FIG. 1, according to one embodiment of the invention,

FIG. 4 is a flowchart comprising the steps of a packet coding method according to one embodiment of the invention,

FIG. 5 is a flowchart comprising the steps of a method for processing packets received from a channel according to one embodiment of the invention,

FIG. 6 is a flowchart comprising the steps of an erased packet recovery method according to one embodiment of the invention,

FIG. 7 represents a functional diagram of a convolutional coding of packets according to one embodiment of the invention, FIG. 8 is a Tanner graph associated with the convolutional code of FIG. 7,

FIG. 9 represents a diagram of a decoding of the convolutional code of FIG. 7, and

each of FIGS. 10 to 12 respectively represents performance curves associated with an erased packet recovery method, according to a respective variant of the invention. In all the figures, similar elements bear identical references.

DETAILED DESCRIPTION OF THE INVENTION

With reference to FIG. 1, a digital data transmission system R comprises a transmitter node 1, a packet-erase transmission channel T and at least one receiver node 2.

The T-channel is adapted to transmit data packets transmitted from the sending node 1 to each receiving node 2. The receiving node 2 comprises means (not shown) for clearing packets presenting errors introduced during the transmission, and means for generating erasure information identifying the packets erased by the channel. These means, known in themselves, will not be detailed later.

With reference to FIG. 2, the transmitter node 1 comprises a packet coding device 10 and a transmission module 16 arranged at the output of the device 10.

In the present embodiment, the device 10 is configured to implement a convolutional coding according to the invention. It comprises an input memory module 1 1, two convolution units 12 and 13, and a multiplexing module 14.

The memory module 1 1 is connected to an input of the transmitter node 1 through which data packets are received. Both convolution units 12, 13 are configured to encode stored packet data in the memory 11 and output coded packets to the multiplexing module 14.

The multiplexing module 14 is furthermore configured to deliver coded data to the transmission module 16, which is configured to generate a signal conveying the coded data and transmit this signal on the channel T. Optionally, the multiplexing module can also interleaving these coded data, in order to remedy the transmission errors occurring in puffs, because this type of transmission errors causes puffs of packets erased at the receiver.

With reference to FIG. 3, the receiving node 2 comprises a reception module 21, an erased packet recovery device 20 and a decoder 26 at the output of the covering device 20.

The erased packet recovery device 20 comprises a memory unit 22, a memory unit 23, and a packet correction module 24.

The memory unit 22 is configured to receive from the reception module 21 received packets corresponding to packets transmitted by the sending node.

The memory unit 23, also connected to the receiver module 21, is configured to receive therefrom the erasing information generated by the T channel.

The correction module 24 comprises a syndromes calculation unit 240, a counter 241, and a reconstruction unit 244.

The syndromes calculating unit 240 is configured to identify, in the packets received and from the erasure information stored in the second memory unit, a group of non-erased packets involved in parity equations, each parity equation involving coded packets stored in the memory unit 22. The counter 241 is configured to count, from the erasure information stored in the memory unit 23, a number of erased packets involved in a parity equation associated with a pair of coded packets stored in the memory unit 22.

The reconstruction unit 244 is configured to reconstruct an erased packet by a convolution performed on the identified non-erased coded packets involved in the parity equation associated with a pair stored in the memory unit 22, if the number of packets erased counted by the counter 241 for said pair is equal to one.

The reconstruction unit 244 is furthermore configured to write access to the memory units 22 and 23.

The decoder 26 is adapted to receive packets processed by the covering device 20. The decoder 26 may form a module independent of the device 20 or be an integral part of the device 20 covering.

Coding and transmission

With reference to FIG. 4, an erasure correction coding method comprises the following steps.

In a step 101, data are stored by the memory module 1 1 in the form of a sequence of N input packets P = (P _1; ..., P _W ) to be processed, all having the same length, that is to say the same number of data (bits or other) of the packet. From this sequence P, we produce (N + K- first coded packets A _m and (N + K ₂ ) second coded packets B _n .

In a step 102, the first coded packets A _m are produced by the module 12 by the implementation of a first convolution operated on a first set of input packets present in the following.

In a step 103, the second coded packets B _n are produced by the module 13 by the implementation of a second convolution operated on a second set of input packets present in the suite.

Each first coded packet A _m and each second coded packet B _n are therefore of equal length to that of the input packets.

The convolution implemented by the coding unit 1 2 is defined by a first generating polynomial G ₁ of degree K ₁ . Similarly, the second convolution implemented by the coding unit 13 is defined by a second generator polynomial G ₂ of degree K ₂ .

K denotes the maximum of the respective degrees K and K ₂ of the first and second generator polynomials G ₁ and G ₂ .

In the embodiment described below, it will be assumed that the degrees K and K ₂ are equal (although G ₁ and G ₂ polynomials of different degrees can be used, as will be discussed later).

In a step 104, (N + K) first coded packets and (N + K) second coded packets are stored by the multiplexing module 14 so as to generate a sequence C of pairs (A _n , B _n ) of first and second coded packets, so as to be able to transmit all the coded packets on a single communication route included in the channel T. The multiplexing module 14 may, for example, control the execution of the convolution units 1 2 and 13 so as to receiving from these two convolution units first and second alternatively coded packets. Optionally, as explained above, the multiplexing module 14 may further interleave the encoded data.

The sequence C of coded pairs thus obtained comprises, for example, the following packets Ci:

C _l = A ₁ , C ₂ = B _X , C 1 = A ₂ , C ₄

= B · · · C = A C

= R i · ^"· · ^'' C ^ 2 N + K) -l = A N + K 'C ^ 2 (N + K) = F N + K

In a step 106, the sequence C of coded pairs is transmitted by the transmission module of the transmitter node 1 in the transmission channel T. During their transmission in the T-channel, possible errors can corrupt the contents of certain coded packets of the series C of pairs emitted by the sending node 1. When the decoder of the physical layer (responsible for correcting the errors due to the transmission) can not completely correct these errors, it gives information that makes it possible to mark the packet as erased.

The "erase information" thus makes it possible to identify all the packets erased as a result of their passage in the T-channel. Reception, recovery of erased coded packets, and decoding

With reference to FIG. 5, the reception module 21 of the receiving node 2 receives data from the channel T during a step 201.

The received data comprises received packets corresponding to the sequence C of 2 (N + K) coded packets transmitted by the sending node 1, and the erasing information described above. Then, during this step 201, the reception module 21 implements a demultiplexing of the received data (and optionally deinterleaves these data if they have been interleaved before being transmitted by the transmitter node 1), and marks each of the 2 (N + K) encoded packets sent as present in received packets, or missing in received packets.

It will be admitted in the following that each of the (N + K) pairs of the sequence transmitted by the sending node 1 is referenced in the erasure information received by the receiving node 2.

In a step 202, the packets received in the memory unit 21, and in a step 202, the erasure information is stored in the memory unit 23. These two storing steps 202, 203 can be executed sequentially, or else simultaneously to shorten the processing time of these data.

The erasure information and the received packets are then processed by the device 24 by means of a recovery method of erased packets represented by a step 204 in FIG. 5. Finally, in a step 206, the correctly transmitted coded packets in the T-channel and the recovered packets can be decoded by the decoder 26 (thus, independently of the recovery of erased packets operated in step 204).

With reference to FIG. 6, the erased packet recovery method 204 comprises the following steps implemented for the first 2 (N + K) coded packets stored in step 203.

In a step 2040, the syndromes calculation unit 240 calculates

(N + 2K) syndromes from the stored packets. Each syndrome S _n of index n is the result of the following parity equation:

In a step 2041, the counter 241 counts, from the erase information, a number of erased packets involved in each parity equation; in what follows, this counted number will be called "index" of the parity equation, or index of the syndrome resulting from this parity equation.

In a step 2042, the value of each of the (N + 2K) indexes is examined.

If the index l _n is equal to 0, this means that no erased packet intervenes in the parity equation resulting in the syndrome S _n ; no recovery is necessary.

If the index I _n is equal to 1, then a single null packet representative of an erased coded packet intervenes in the parity equation. In this case, in a step 2044, the value of the syndrome S _n is identified as being the value of the erased packet.

If the index I _n is different from 1, the next index I _{n + 1} is examined. The steps for calculating the 2040 syndromes, calculating the index 2041 and the covering 2044 can be repeated so as to correct a maximum of deletions in the received packets corresponding to the series of transmitted pairs.

Embodiment based on XOR operation

In one embodiment, each convolution performed during steps 103 and 104 is a bit-to-bit addition modulo 2 (XOR) performed on the corresponding input packets, and each convolution operated by the during the reconstruction step. 2044 is also a bit-to-bit addition modulo 2 (XOR) performed on the corresponding coded packets.

In the general case of a generator polynomial code

G _i (p) = Σ ₀ G _ii jDJ, i = 1.2,

whose coefficients G _{ij is} 0 or 1, the first coded packet and the corresponding second coded packet are computed by the following convolution operations in convolution units 12 and 13:

so that :

Therefore, for any value of n, the coded packets are associated with a syndrome S _n and obey the following parity equation:

KK

Thus, the group of undeleted coded packets involved in the parity equation associated with the index n comprises a first set comprising at least a first coded packet Ai delayed or not with respect to the packet An and a second set comprising at least a second coded packet Bi delayed (s) or not with respect to the packet Bn. Said first set of coded packets is associated with the second generator polynomial G ₂ , while said second set of coded packets is associated with the first generator polynomial

By convention, in the equation above relating to the syndrome S _n of index n, the packets A _m , B _m whose indices satisfy m <1 or m> (N + K) are null.

As an example, we will take the following generative polynomials G ₁ () = 1 + + ² and G ₂ (D) = \ + D ² . The first packet and the second index packet n coded according to these polynomials are then defined as follows:

A n = P n Θ P n-, l Θ P n-, 2

B n = P n ® P n-, 2

where the symbol ® denotes the modulo 2 addition of bits of the same position of the packets involved in the expressions of the packets An, Bn. The coding scheme corresponding to this example is illustrated in FIG.

The index parity equation n is then the following:

for any value of n. Indeed, considering the following successive terms:

B n = P n ® P n -2

we easily check that © -2 © _η θ Β _η _ _χ θ Β _η _ ₂ = 0. Each input packet Ρ _η ι appears an even number of times in the sum ® Ai-2 ® B _n

® B _n -2 which is therefore zero (a packet whose all bits are equal to 0).

In what follows, the symbol © is replaced by the classic symbol of addition (+), it being understood that it is the addition of the body with two elements GF (2).

This sequence of parity equations can be represented graphically in the form of a Tanner graph, which is a bipartite graph with two categories of vertices: nodes representing coded packets, and nodes representing syndromes (parity equations) , as illustrated in FIG. 8.

In this graph, all the nodes Sn have the same degree, that is to say the same number of incident branches, equal to:

^ = Σfo, + G ₂ ,)

i≥0

which is none other than the sum of the numbers of non-zero coefficients of the two generating polynomials Gi (D) and G ₂ (D).

The nodes of the Tanner graph which correspond to the coded packets A _n are of degree d _b G _{and those} corresponding to the packets

B _n are of degree d _b =, the two sums being calculated in i≥0

natural integers (these are simply the numbers of non-zero coefficients of each of the two generating polynomials).

Each packet An intervenes in the syndromes S _{n + i} , z ^' | G ₂ , ≠ 0 and in the same way each packet Bn is connected to the syndromes S _{n + i} , i G _u ≠ Parity equations are used to recover deleted packets; indeed, if a single packet intervening in a given parity equation is erased, it can be recalculated as the sum (XOR) of the other undeleted packets involved in the same parity equation.

The process of recovering erased packets operates on the Tanner graph introduced above. The index of a parity equation is introduced as being equal to the number of deleted packets involved in this parity equation. The interesting case is of course that of an index parity equation equal to 1 because the erased packet is then computable as the sum (XOR) of the other (undeleted) packets that are involved in this parity equation.

If, in the above example, the packet An is the only packet erased in the parity equation S "= ® _ ₂ ® B _n ® B _n _ _x ® B _n _ ₂ = 0, we can reconstruct it according to = - ₂ ® B _n ® ¾-i ® ¾-2 ■ Once a packet is recovered, the index of the parity equations in which it was involved is decremented by one unit (the packet is no longer considered as erased), and we search for a new index parity equation equal to 1.

It will be shown below that it is possible to avoid decoding the bits contained in the packets An, Bn, to go back to the input packets Pn.

In the present embodiment, the generating polynomials G ₁ and G ₂ are prime between them and thus verify the Bezout equation, that is, there are two polynomials U (D), V (D) such as

U (D) G ₁ (D) + V (D) G ₂ (D) = 1 (the arithmetic being, in the present embodiment, that of the two-element body, that is to say modulo 2 ). For example, the two polynomials G ^ D) = Ï + D + D ² and G ₂ (D) = 1 + D ² already taken as an example respect the Bezout equation well, since D xG _l (D) + (1 + D) xG ₂ (D) = 1, i. _e . U (D) = D and V (D) = 1 + D.

Recovery of erased packets based on XOR operation

In the embodiment illustrated in FIG. 6, the recovery of erased packets can be implemented in two phases: an initialization phase, and a loopback phase, which will now be detailed in the non-limiting case where the XOR operator is chosen to generate the first coded packets and the second convolutionally encoded packets.

As a preliminary, it is assumed that the following 2 (N + K) packets have memorized during the storage step 203:

C ₁ = A ₁ , C ₂ = B ₁ , C ₃ = A ₂ , C ₄

- B _{2 ''} _'' ^ 2i-i ~ A _{_'2i} C -B, · · ·, C _{2 (N + K)} ~ _1.

= A N + K 'C 2 (^ + ^) = E N + K

Ci packets are assumed to be received without error or not received (erased).

The erasure information is a vector E = (E1, E2, ...) such that:

ί 1, if the package i is cleared

With these notations, the sequence of the packets stored in the memory unit 23 is

The memory unit 23 thus contains undeleted packets and null packets each representative of an erased packet. We also define the two sets I i ⁼ _M = lj and ¹ 2 = {^ 2 ,; = l}. For the generative polynomials G ₁ and G ₂ taken as an example above, we have I i = {θ, 1,2}, I ₂ = {0,2}. Initialization phase

During a preliminary step, the received packets and the erasure information can be demultiplexed by the module 21, so as to separate the received packets relating to the first coded packets and the packets received. relating to the second coded packets. This step can be implemented by a serial / parallel pass of the packets Ri to form the two suites of (N + K) packets A

^" and

B _l = R ₂ , B ₂ = R ₄ , ^{■ ■} , B _i = R _2. , - -. In the same way, the vector

Ε = (Ε _ι , Ε ₂ , · · ·) erasures is converted into two vectors respectively storing the erase information on the first coded aquet A, and the second coded packet Bi, that is to say:

= E _2i _ _x and £ «'= ¾.

By "erasure information", we mean that all transmitted packets are numbered (or have an identifier), which allows to know which packets have been lost or erased (their number is missing at the reception level). ).

The step of calculating the syndromes 2040 is then implemented for the (N + 2K) syndromes by the unit for calculating syndromes 240. During this step, a vector of the syndromes ¾ (* Sj, S 2) is initialized. ·, '"S N + 2K), each syndrome being obtained according to the formula: κ κ

S _n = ΣG ₂ A _n _ _{i +} ΣG ₁ . B _n _i , n = 1.2, ...

i = 0 i = 0

Each first packet of the first set of coded packets involved in this parity equation is multiplied by a non-zero coefficient of the second generator polynomial G ₂ , and each second packet of the second set of coded packets involved in this parity equation is multiplied by one. non-zero coefficient of the first generator polynomial G ₁ .

If all the packets R, were received, each syndrome S _n would consist of null bits (by definition of the syndrome); the presence of erasures makes some S _n non-zero.

The step of calculating the indexes 2041 is implemented by the counter 241 for the same (N + 2K) syndromes, so as to initialize an index vector I ⁼ ('^ 2'^"' ^ V + 2 ^) , each index counting the number of deleted packets involved in the parity equation associated with the Sn syndrome.

The indexes .., N + 2K, by:

where is the erase information associated with the first stored packet of index i and E ^ _t is the erase information associated with the stored second packet of index i.

Iterative phase

The iterative phase comprises a succession of iterations, each iteration being performed after verification of a loopback condition 2042 evaluating whether there remain erased packets that can be reconstructed.

The condition of loopback is verified by the reconstruction unit

244, or the counter 241. This loop condition 2042 is true if there exists an index j such that the index / _, - = 1, which means that there exists a unique index i which indicates which was the erased packet intervening in the equation parity index j. In other words, this loop condition 2042 is true if at least one of the calculated (N + 2K) indexes is 1. The loopback condition 2042 can therefore be verified in two cases:

there exists, in the index parity equation j, an index i of the first packet Ai intervening in the parity equation such that = 1 (in this case, the erased packet is a first coded packet), or else

there exists, in the index parity equation j, an index i of second packet Bi intervening in the parity equation of index j, such that

En¾ = 1 (in this case, the deleted packet is a second encoded packet).

As long as this condition is true, a new iteration of the loop is executed, taking as input data to process the packets stored in the memory unit 23. Each iteration comprises the following steps.

In the reconstruction step 2044, the reconstruction unit 244 replaces, in the packets stored in the memory unit 23, a zero packet of index i representative of an erased packet, involved in the index syndrome j, by the value 5} of this syndrome. More precisely, the single erased packet of index i involved in the index parity equation j is then reconstructed by A _{i =} Sj in the first case described above, or else by Bj = Sj respectively.

The reconstruction step therefore performs a simple write in the memory unit 23, the syndrome Sj having already been calculated during the step 2040 implemented previously, without consuming additional memory in the correction device 20. In a step 2046, the erase information is updated by the reconstruction unit 244 to mark the reconstructed packet as non-erased. Thus, the corresponding erasure indication E. ^a) = 0 or E- ^b) = 0 respectively is set to zero.

The unit for calculating syndromes 240 then implements the step of calculating the syndromes S = {S ₁ , S ₂ , - - - S _{N + 2K} ) on the (N + 2K) updated packets contained in the memory unit 203.

The index calculation step 2041 is also executed in order to update the index vector Ι = {ΐ Ι ₂ , · · · Ι _{Ν + 2} κ) ■ All indexes associated with syndromes whose value has have been modified during the previous update are then decremented by 1.

Loop condition 2042 is then re-examined. Thus, the iterative phase makes it possible to reconstruct deleted packets intervening in index parity equations greater than 1 at the end of the initialization phase.

As soon as the loopback condition 2042 is false, no more erased packet can be reconstructed: the iterative phase then ends.

Two cases of exit from the iterative phase can occur. In a first output case, the (N + 2K) indexes are zero, which means that all the erased packets have been reconstructed, and the decoding step 206 can then be implemented by the decoder 26. In a second output case (referred to as "end" in FIG. 6), only indexes strictly greater than 1 remain; correction of all erasures is then not possible and residual erasures remain.

Case of polynomials generating different degrees

The overlay is operated from 2 (N + K) packets stored in the memory unit 23, each stored packet being a non-erased coded packet (successfully transmitted in the channel), or an erased packet represented by a null packet representative of a coded packet erased by the channel.

In the foregoing, the case of an encoding by means of two generating polynomials G ₁ and G ₂ having the same degree K has been considered. These two polynomials may however have different degrees (one may in particular have a zero degree; the packets at the output of the convolution unit implementing a polynomial of zero degree are then in the clear).

If the respective degrees K and K ₂ for G ₁ and G ₂ are different generator polynomials (K then being defined as the maximum of K and K _2), then only (N + K first encoded packet and (N + K ₂₎ Coded packets are produced by convolution steps 102 and 103. Blank packets of stuffing can then be generated by the sending node, or the receiving node, in a stuffing step.

This stuffing step produces:

if K> K ₂ , second identically zero packets B _n , where N + K ₂ <n ≤ N + K _lt completing the second non-erased packets and the null packets representative of second erased packets, to form the (N + K) second packets processed during the overlay 204, and

if KL <K ₂ , first null packets A _N , where N + K ₁ <n ≤ N + K ₂ , completing the first non-erased packets and the null packets representative of first erased packets, to form the (N + K) first packets processed during recovery 204. The stuffing step can be implemented by the sending node

1 after the coding steps 102 and 1 03.

As a variant, only (N + K) first packets and (N + K ₂ ) are transmitted by the sending node and the null packets are generated by the receiving node 2 during the reception step 201. the advantage of reducing the number of packets transmitted in the T channel. Decoding XOR-based input packets

Step 206 of decoding packets can be implemented once the iterative phase is completed.

In the first case of loop output, the decoding can be performed without error. Since, in the present embodiment, the two polynomials G1 and G2 are chosen first among themselves, the decoding can be done very simply on the basis of the Bezout equation, as follows:

P _jD i,

=> U (D) A (D) + V (D) B (D) = [U (D) G ₁ (D) + V (D) G ₂ (D)] x P (D) = P (D) ) The decoding scheme associated with polynomials

^ (£ = 1 + D + D ² and G ₂ (D) = 1 + D ² is illustrated in Figure 9. In this example, input packets are decoded by calculating A ^ + B _n + B ^ = P _n

In a particular embodiment variant, one or the other of the two generating polynomials has only one non-zero term, for example G1. In this case, the realized code is systematic: each first coded packet is actually an input packet transmitted in clear, and the next step implementing the Bezout equation is useless since there are already packets of information.

In the second case of loop output, some input packets can not be decoded because some coded packets are missing as a result of being erased by the T channel.

The decoding performance criteria are the residual rate of packets erased after decoding (in English PER, "Packet Erasure Rate"), and the rate of failure of decoding the code word (WER, Word Erasure Rate). Are illustrated in each of Figures 10 to 12 two curves of theoretical decoding performances (in terms of WER and PER respectively), as a function of a probability p of independent erasures in a T channel.

The curves of Figure 10 correspond to the following parameters:

G _l {D) = \ + D ³ + D + D ⁵ + D ¹ + ⁸ + D ⁹

G ₂ (D) = 1 + D + D ³ + D ⁴ + D ¹ + D ⁹

N = 100

The curves of FIG. 11 correspond to the following parameters:

⁽ ¾ (D) = D

G ₂ (D) = 1 + D ² + D ³ + D ⁶ + ⁸ + D ⁹

N = 100

The curves of Figure 12 correspond to the following parameters:

⁽ ¾ (D) = D

G ₂ (D) = 1 + D ² + D ³ + D ⁶ + ⁸ + D ⁹

N = 500

The packet coding and the corresponding erase correction described above can be used for many applications, such as:

- file delivery ("delivery delivery" in English) in "multicast / broadcast" mode on fading channels, with retransmission of coded packets that could not be decoded: we use the property that the probability of non-correction of a code word (WER) can be of the order of 10 ^{~ 3} , while the probability of erasure of a packet is 10%, so that the failure rate of the decoding is almost equal to 1 for large values of K, such as those proposed as examples; - the distribution of multimedia files ("streaming" in English); using the property that the residual erasure rate (in the order of i ⁽⁾⁾ is much lower than that after decoding in the channel (20%).

Moreover, the correction method previously described for 2 (N + K) coded packets can be generalized to a continuous mode of operation, that is to say to an unlimited series of packets, by means of the definition of a window decoding algorithm which restricts the Tanner graph to the syndromes S _t -w ^'" $ t + w where (2 * W + 1) is the width of the window.

It is also possible to take into account the quality of the T channel: when the erasure rate in the channel is low, it is possible to introduce voluntary erasures by the conventional punching technique ("puncturing" in English). which has the effect of advantageously increasing the efficiency of the code.

Packet coding and erase correction according to the invention may furthermore be implemented in the form of a computer program product comprising code instructions for the execution of the corresponding steps.

Claims

1. A method of encoding digital data packets, said method comprising the steps of:

storing (1 00) N input packets (P _1; ..., P _N ),

- production (101) of (N + first coded packets [A _1] ..., A _{N + K} defined for m = 1, ..., N + K _lt by

Gij m-i>

where G ₁ is a first generator polynomial different from 1, and of degree K _lt G is the coefficient of the power term i of said first generator polynomial G _lt and the input packets of index less than 1 or greater than N are identically zero,

- production (1 02) of (N + K ₂ ) second encoded packets (#i, defined, for = 1, ..., N + K ₂ , by

where G ₂ is a second generator polynomial different from 1, and of degree K ₂ , G ₂ is the coefficient of the power term; said second generator polynomial G ₂ , and the input packets of index less than 1 or greater than N are identically zero,

and where the generating polynomials G ₁ and G ₂ are prime between them.

2. Erasure correction method, said method comprising the steps of:

storing (203) (N + K) first packets to be processed (L, ..., A _{N + K} ) and (N + K) second packets to be processed (B ₁ ..., B _{N + K} ) each packet to be processed being a non-erased packet or a null packet representative of an erased packet,

- calculation (2040) of (N + 2K) syndromes ..., S _{N + 2K} ) defined, for n = 1, ..., N + 2K, by

where G _li are K first predetermined coefficients defining a first polynomial

different from 1, and where the packets A _m and B _m are identically zero for m <1 or m> N + K,

- recovery (2044) possible packets deleted from the syndromes, so that when the calculation of a syndrome involves a single zero packet representative of an erased packet, then the recovered packet corresponding to this erased packet is equal to this syndrome.

The method of claim 2, further comprising the steps of:

storing (202) 2 (N + K) erase information, each erase information indicating whether a respective stored packet is a non-erased packet or a null packet representative of an erased packet,

calculating (2041) (N + 2K) index ..., l _{N + 2K} ) from the erasure information, the index I _n counting the number of erased packets representing the erased packet involved in the calculation of the syndrome S _n, said step of covering an erased packet that can be achieved when the index _n is equal to 1.

4. Method according to claim 3, comprising several successive iterations, each iteration comprising:

updating (2044) the stored packets, in which each recovered packet replaces the corresponding null packet in the stored packets, and

calculating the syndromes (2040) from the updated stored packets,

updating (2046) the erasure information associated with the replaced stored packets, so that each covered packet is marked as non-erased in the stored data,

the computation (2041) of the indexes from the erasure information, a new iteration being implemented as long as at least one of the indexes calculated during the preceding iteration is equal to 1.

5. Method according to one of claims 2 to 4, wherein said polynomials G ₁ and G ₂ are prime between them.

The method of claim 5, further comprising a decoding step (206) implementing the following calculation to obtain P _n packets of decoded data:

OR

- A (D) is a polynomial representative of the first non-erased or recovered packets, such that A (D) = ⁺ ΣJL ^(AJD},

B (D) is a representative polynomial of second undeleted or recovered packets, such that BD) = BjD ^j , and

U (D) and V (D) are two polynomials such that U (D) G ₁ (D) + V (D) G ₂ (D) = 1.

7. Method according to one of claims 2 to 6, wherein the integer K is the maximum of two integers K and K ₂ , and wherein the first coefficients G are identically zero for i> K _lt and the second coefficients G _{2 i} are identically zero for i> K ₂ , and further comprising the following steps implemented before the storage step:

- receiving (N + K ^) first transmitted packets [A _1} ..., A _{N + K} and (N + K ₂ ) second transmitted packets [B _1} ..., B _{N + K} ,

if K- _L > K ₂ , producing identically zero second packets B _N , where N + K ₂ <n ≤ N + K _lt completing the first packets transmitted to form the (N + K) second packets to be processed, and

if K- _L <K ₂ , producing first identically null packets A _N , where N + K- _L <n <N + K ₂ , completing the second transmitted packets to form the (N + K) first packets to be processed.

8. Device (10) for encoding digital data packets comprising:

a memory module (1 1) adapted to store N input packets and

an input packet processing module,

said packet processing module comprising first and second convolutional coding units (12, 13) such as:

the first convolutional encoding unit (12) is configured to produce (N + K- first coded packets (A ^ ..., A _{N + K} defined, for m = 1, ..., N +

Gij m-i>

where G ₁ is a first generator polynomial different from 1, and of degree K _lt G is the coefficient of the power term ί of said first generator polynomial G _1; and input packets of index less than 1 or greater than N are zero,

the second convolutional coding unit (13) is configured to produce (N + K ₂ ) first coded packets [B _1} ..., B _{N +} K ₂ ) defined, for n = Ι,.,. , Ν + K ₂ , by

Bn -Σj = o G ₂ iP _n -j,

and the generating polynomials G ₁ and G ₂ are prime between them.

An erasure correction device (20) comprising:

- a memory module (22) adapted to store (N + K) first packets to be processed (A ^ ..., A _{N + K} ) and (N + K) second packets to be processed (B ₁ ..., B _{N + K} ), each packet to be processed being an undeleted packet or a null packet representative of an erased packet,

a module (24) for processing stored packets adapted to:

o calculate (N + 2K) defined syndromes ..., S _{N + 2K} ), for n = 1, ..., N + 2K, by

where G _LI are K first predetermined coefficients defining a first polynomial

different from 1, and the G _{2 I} are K second predetermined coefficients defining a second polynomial κ

G ₂ (D) = G 2 _J Di

j = o

different from 1, and where the packets A _m and B _m are identically zero for m <1 or m> N + K, and

An erasure correction device (20) according to claim 9, wherein said G ₁ and G ₂ polynomials are first to each other.

1 1. An erase correcting device (20) according to claim 10, further comprising a decoder (26) adapted to implement the computation according to obtaining packets P _n of decoded data:

N + K

P (D) = P _n D ⁿ = U (D) A (D) + V (D) B (D)

n = 0

OR

A (D) is a representative polynomial of first non-erased or recovered packets, such that Αφ) = ΣJL ⁺ _< AjD ^} ,

B (D) is a representative polynomial of second non-erased or recovered packets, such that Βφ)

BjD ^j , and

- U (D) and V (D) are two predetermined polynomials such that υφ) α ₁ φ) + νφ) α ₂ φ) = 1.

12. Digital data transmission system (R) comprising at least one transmitting node (1) and at least one receiving node (2) mutually connected by a channel (T) subject to packet erasures, said transmitting node (1) comprising a packet coding device (10) according to claim 8, and said receiving node (2) comprising an erase correction device (20) according to any of claims 9 to 11.

13. Computer program downloadable from a communication network and / or stored on a computer readable medium and / or executable by a microprocessor, characterized in that it comprises instructions for carrying out the steps of a method according to any of claims 1 to 7 when executed on a computer.

A non-removable, or partially or fully removable data storage medium comprising computer program code instructions for performing the steps of a method according to any one of claims 1 to 7.