WO2018185402A1 - Methods for encoding and decoding data packets in a galois field - Google Patents

Abstract

The present invention relates to a method for encoding data packets, comprising the following steps: receiving r ≥1 l useful data packets Y _i <sb /> each made up of a linear combination in which the coefficients of the linear combination are taken in an extension field GF(2 ^m ) defined by means of a chosen primitive polynomial, from the same k ≥1 information packets {P ₁, P ₂,..., P _k} referred to as initial packets, each information packet containing L ≥ 1 symbols each made up of a series of m > 1 bits; calculating an outgoing useful data packet Y' made up of a linear combination of useful data packets Y _i ; in which the coefficients α _i are taken from the extension field GF(2 ^m ); and transmitting the outgoing useful data packet Y'. The encoding method is characterized in that the step of calculating the outgoing useful data packet Y' comprises at least one sub-step of multiplying Q = a ⋅ P all the symbols in a data packet P= (x ₁,..., x _L ), wherein x _j for j = 1,..., L, is a symbol made up of a series of m bits x _ij , in which i = 0,..., m- 1, by a same number α belonging to GF(2 ^m ), and in that the multiplication is carried out by means of binary operations performed in a vector manner at the level of the symbols of the data packet P. The invention applies to the transmission of binary data packets on erasing channels.

Description

 CODING AND DECODING METHODS

 PACKET DATA IN A BODY OF GALOIS

The present invention relates to communication or data recording systems in which, in order to improve the fidelity of transmission or storage, the data is subjected to a so-called "network coding" ("Network Coding"). .

 The invention relates more particularly to the transmission of data packets on a channel affected by packet losses. On such a channel, some packets are received perfectly (thanks to properly defined modulation and coding at the physical layer); however, other packets are not received, either because these packets are deleted due to congestion in a router, or because they are received in bad conditions (noise, interference) and can not be decoded correctly. Such a transmission channel is called "erasing channel", and lost packets are said to be "erased". Systems for transmitting packets on channels causing erasures include, for example:

 - mass storage, as well as distributed storage, systems in which data loss is due to failures of hard disks or servers;

 - broadcast or multicast broadcast eMBMS (evolved Multimedia

Broadcast Multicast Services) in LTE (Long Term Evolution), for the transmission of files or audiovisual programs streaming; and

 - Real-time transmission of voice or video over lossy channels, such as VoLTE (Voice over LTE) or WebRTC (Web Real-Time Communication).

 It should be noted that in some of these systems the packets are called "blocks", but the term "packets" will be used uniformly below.

It is recalled that the network coding (see for example the article by R. Koetter and M. Medard entitled "/ An algebraic approach to network coding", IEEE / ACM Transactions on Networking, Volume 1 1, No. 5, Oct. 2003, pages 782-795) consists in transmitting information in data packets of such that this information follows several paths in a distributed infrastructure including nodes that serve as relays (or routers).

 The present invention relates more particularly to the case in which the relays can store and retransmit ("store and forward" in English) the useful data packets entering these relays, but can also, as illustrated in FIG. 1, retransmit packets of useful data that result from processing on these input packets, i.e., which constitute a certain function f of these input packets.

pour une valeur correspondante de j , où j = 1,..., q - 1 , et où α est une racineIt will be assumed that the useful data packets contained in all these data packets all have the same number of bits. If this number is a multiple of an integer m greater than 1, it can be considered that each payload packet consists of L symbols of m bits belonging to a binary extension body GF (2 ^m ). We recall in this respect that we call Galois body (denoted GF (q)) a set of q elements whose non-zero elements can be identified as being each equal to

for a corresponding value of j, where j = 1, ..., q - 1, and where α is a root

primitive de l'unité dans GF(q) ; lorsque, en particulier, q = 2^m , où m > 1 , le corps de Galois est également appelé « corps d'extension binaire ».

primitive unity in GF (q); when, in particular, q = 2 ^m , where m> 1, the Galois body is also called "binary extension body".

 Each relay can transfer the payload packets it receives without modification, or transmit on the output link a linear combination of packets received on the input links, it being understood that, as explained above (erase channel) , some packets sent by other nodes of the network may not have been received (in which case the relay does not try to find the deleted packets).

Une règle de calcul plus complexe du paquet de sortie Y met en œuvre des combinaisons linéaires des paquets d'entrée avec des coefficients

When the input packets X ₁ , ..., X _n all consist of L elements of GF (2 ^m ), a very simple operation on these input packets consists in performing a bitwise addition (it should be remembered that bitwise addition is also referred to as "exclusive OR", and denoted "XOR") as input packets:

A more complex calculation rule of output packet Y implements linear combinations of input packets with coefficients

 that is to say :

This input-output relationship now involves multiplications in the GF body (2 ^m ). For convenience of notation, we will now represent the operation XOR by the usual symbol (+) of the addition, so that the preceding relation is written:

 The transmission of information packets from a source S to a recipient (or receiver) D via an N network can be described by a graph (see FIG. 2) whose nodes represent relays such as that illustrated in FIG. and branches represent existing links between:

 - the source and one or more relays,

 - the recipient and one or more relays, and

 between the relays themselves.

The source S emits a series of information packets said

initial packages. One and the same packet P _t may travel on several paths of the network N originating from S. The recipient D may therefore receive a number n≥k of useful data packets R _t , each of which may be:

- a copy of one of the packets if it has been transmitted by nodes

 retransmitting without modification the packets they receive, or

- a linear combination of form

if it has passed through relays performing linear combinations, the coefficients c _Uj being taken in an extension body GF (2 ^m ); the N network relays perform linear combinations on the packets of the same stream (from the same source S to the same recipient D) with coefficients that can be determined once and for all, or be drawn at each application in the case of the so-called "random" network coding.

It should be noted that since the different paths between the source S and the recipient D have potentially different lengths (in number of branches) and different delays, the packets received are in an order which may be different from that of the transmitted packets. On the other hand the topology of the network is not necessarily known to the recipient and / or the issuer. This means that the recipient receives a number n of packets which are each a linear combination of the packets P _i emitted by the source S, which can be written as follows:

In order to find these packets P _} from the received packets R _t , the matrix K must be known to the recipient, and, when it is known, it must be of rank k. In particular, the recipient must have a number n≥k of received packets R _t , otherwise the matrix would be of rank lower than k and the packets P _j could not be traced back.

 This technique of network coding thus consists of coding / decoding by means of a code with no predefined efficiency ("rateless code" in English) because of the constraint n≥ k, n being (theoretically) infinite. In fact it is an instance of the codes called "fountain codes" ("fountain codes" in English), with the following differences:

 • There is more than one path between source and recipient, and packets received by the same recipient may have followed different paths;

• Linear combinations of information packets P _j are not performed by the source but by the elements of the network (distributed coding);

• the coefficients of these linear combinations can be predetermined and fixed in time, or be drawn by the nodes of the network; the latter case (described in the article by T. Ho, M. Medard, R. Koetter, DR Karger, M. Effros, J. Shi, and B. Leong entitled "A random linear Network Coding approach to multicast ", IEEE Trans. Information Theory, vol. 52, No. 10, Oct. 2006, pages 4413-4430) is referred to as "Random Linear Network Coding" (or RLNC).

 It will be noted that the use of codes without predefined performance to recover the packets lost during congestion phenomena makes it possible to envisage the possibility of implementing packet data transmission protocols without resorting to the contention mechanism conventionally used to avoid the collisions, resulting in a gain in terms of simplicity of implementation and speed of execution.

However, simple linear algebra considerations show that the resolution of a system of equations in GF (2 ^m ) involving data packets can be reduced to packet additions and multiplications of one. packet by the same element of GF (2 ^m ), ie linear combinations of packets with coefficients taken in GF (2 ^m ). In the context of these calculations, the bitwise addition is simple to implement, but the multiplication in GF (2 ^m ) relies conventionally on a multiplication table software mechanism.

 However, when it is necessary to multiply all the elements of a given vector

X = (x _1; ..., x _n ) composed of elements of GF {2 ^m ) by the same element a of GF {2 ^m ), it is not possible to consult said multiplication table in vectorial manner; in other words, it is necessary to consult the table for each element x _i of the vector, which is even slower than the vector is longer.

 The present invention thus relates, in a first aspect, to a method of coding data packets in a network (N), comprising the following steps:

receiving r≥ 1 packets of useful data Y _i each consisting of a linear combination

où les coefficients sont pris dans un corps d'extension GF (2^m ) défini au

where the coefficients are taken in a GF extension body (2 ^m ) defined in

L≥ 1 symboles constitués chacun d'une suite de m > l bits ; a selected primitive polynomial, the same k≥1 information packets said initial packets, each packet of information containing

L≥ 1 symbols each consisting of a sequence of m> 1 bits;

computing a outgoing payload packet Y 'consisting of a linear combination

said user data packets Y _n where the coefficients ", are taken in said extension body GF (2 ^m ); and

 sending said outgoing user data packet Y '.

 Said coding method is remarkable in that said step of computing the outgoing payload packet includes at least one substep of multiplication Q = a-P of all the symbols of a data packet.

P = (x _1; ..., x _L ) in which Xj, for; = 1, ..., L, is a symbol composed of a sequence of m bits x _y , where i = 0, ..., m - 1, by the same number a belonging to

GF (2 ^m ), and in that said multiplication is performed as follows: a) filling of a binary matrix X of dimension mx L by placing the bits x _y constituting each symbol Xj along the jth column said matrix X;

 b) calculation of the binary matrix

 Y = M (a) x X,

of dimension mx L, where M {a) is the binary matrix of dimensions mx m whose respective columns contain the binary coordinates of the respective elements where a is a root of said primitive polynomial, in

obtaining the rows of said matrix Y by means of binary additions of rows of the matrix X in patterns determined by the rows of the matrix M {a); and c) obtaining the data packet in which

i = 0, ... , m - 1, situés sur la j -ième colonne de ladite matrice Y . each symbol y _p for j = 1,2, ..., L, is composed of m bits where

i = 0, ..., m - 1, located on the jth column of said matrix Y.

 Thanks to these provisions, the conventional multiplication table consultation mechanism can be replaced by a set of binary operations carried out in a vectorial manner at the level of the symbols of said data packet P. The present invention is therefore particularly advantageous because, if it allows a software implementation of encoding or decoding as state-of-the-art techniques, it also makes it possible to efficiently use an electronic circuit simultaneously with software means, or in their place.

It will be noted in particular that the method according to the invention lends itself well to virtualization. It can indeed be supposed that certain functions will require the use of hardware coprocessors such as a programmable logic circuit ("Field Programmable Gate Array" or FPGA), a graphics processor unit ("Graphics Processing Unit" or GPU , in English), or a digital signal processor ("DSP"), to speed up some processing requiring high computing power, such as encryption processes, but also those introduced by coding channel and network coding. The present invention is therefore particularly advantageous in the context of a virtualized network function (VNF), mainly written in software form and using a hardware accelerator implementing the multiplication in GF. (2 ^m ) in packet mode.

sont extraites d'une matrice de référence T de dimensionAccording to particular features, said matrices M (a), for

are extracted from a reference matrix T of dimension

 Thanks to these provisions, one can easily obtain matrices M (a) without any calculation, by simple reading in a single matrix T built and stored prior to the implementation of said coding method.

où, pour i = 1, ... , n, chaque paquet de données codé

Correlatively, the invention relates to a method for decoding data packets, comprising the following steps: receiving n> 1 packets of coded data

where, for i = 1, ..., n, each coded data packet

is a linear combination of the same k≥1 information packets P _j each containing L≥1 symbols consisting of a sequence of m> 1 bits, and where the coefficients c _tj are taken in a GF extension body (2 ^m ) defined by means of a primitive polynomial chosen, and

resolution of the system formed by said linear combinations, so as to obtain said information packets P _j .

 Said decoding method is remarkable in that said step of solving a system of linear combinations comprises at least one substep of multiplication Q = a - P of all the symbols of a data packet

P = (x _1; ..., x _L ) in which Xj, for j = 1, ..., L, is a symbol composed of a sequence of m bits x _y , where i = 0, ... , m - 1, by the same number a belonging to

GF (2 ^m ), and in that said multiplication is performed as follows: a) filling of the binary matrix X of dimension mx L by placing the bits x _y constituting each symbol along the jth column

said matrix X;

 b) calculation of the binary matrix

 Y = M (a) x X,

of dimension mxL, where the matrix M (a) is the binary matrix of dimensions mxffl whose respective columns contain the binary coordinates of the respective elements where a is a root of said polynomial

i = 0, ... , m - 1, situés sur la j -ième colonne de ladite matrice Y . primitive, by obtaining the rows of said matrix Y by means of binary additions of rows of the matrix X in patterns determined by the rows of the matrix M (a); and c) obtaining the data packet Q = (y _1; ..., y _L ), in which each symbol y _p for j = 1,2, ..., L, is composed of the m bits where

i = 0, ..., m - 1, located on the jth column of said matrix Y.

 The advantages offered by this decoding method are essentially the same as those offered by the correlative coding method succinctly set forth above.

sont extraites d'une matrice de référence T de dimensionAccording to particular features, said matrices M (a), for

are extracted from a reference matrix T of dimension

 Thanks to these provisions, one can easily obtain matrices M (a) without any calculation, simply by reading in a single matrix T built and stored prior to the implementation of said decoding method.

 According to a second aspect, the invention relates to various devices.

 It thus relates, firstly, to a device for coding data packets, comprising means for:

; i - receive r≥l useful data packets Y _i each constituted by a linear combination

; i

where the coefficients are taken in a GF extension body (2 ^m ) defined in

a selected primitive polynomial, the same k≥1 information packets said initial packets, each packet of information containing

 L≥ 1 symbols each consisting of a sequence of m> 1 bits;

calculate a outgoing payload packet consisting of a linear combination

useful data packets Z, where the coefficients ", are taken in said extension body GF (2 ^m ); and

- send said packet of user data out y. Said coding device is remarkable in that it further comprises, for the purpose of performing at least one multiplication Q = a P, required for computing the outgoing user data packet Y \ of all the symbols of a packet of data P = (x _1; ..., x _L ) in which x _jt for j = l, ..., L, is a symbol composed of a sequence of m bits where i = 0, ..., m - 1, by the same number a

belonging to GF (2 ^m ), means for:

filling a binary matrix X of dimension mx L by placing the bits x _y constituting each symbol Xj along the jth column of said matrix x;

 - calculate the binary matrix

 Y = M (a) x X,

of dimension mxL, where M (a) is the binary matrix of dimensions mxm whose respective columns contain the binary coordinates of the respective elements {a, yy, ..., a ^m_1 a}, where a is a root of said primitive polynomial, obtaining the rows of said matrix Y by means of binary additions of rows of the matrix X in patterns determined by the rows of the matrix M (a); and

- obtain the data packet, in which each

_jt symbol y for j = 1,2, ..., L, is composed of m bits y _y, where i = 0, ..., m - 1, located on the j ^'th column of said matrix Y.

According to particular features, said coding device further comprises means for extracting said matrices M (a), for a reference matrix T of dimension

 The invention also relates, secondly, to a device for decoding data packets, comprising means for:

- receive n> \ coded data packets where, for

i = 1, ..., n, each coded data packet

is a linear combination of the same k≥1 information packets P _j each containing L≥1 symbols consisting of a sequence of m> 1 bits, and where the coefficients are taken in an extension body defined by means

a primitive polynomial chosen; and

solving the system formed by said linear combinations, so as to obtain said information packets P _j .

symbole composé d'une suite de m bits x_y , où i = 0, ... , m - 1, par un même nombre a appartenant à GF (2^m ) , des moyens pour : Said decoding device is remarkable in that it further comprises, for the purpose of performing at least one multiplication Q = a P, required for the resolution of said system of linear combinations, of all the symbols of a data packet. in which for is a

symbol consisting of a sequence of m bits x _y , where i = 0, ..., m - 1, by the same number a belonging to GF (2 ^m ), means for:

- Fill a binary matrix X of dimension mx L by placing the bits x _y each component Xj along the jth column of said matrix X;

- calculate the binary matrix

où a est une racine dudit polynôme primitif, en obtenant les lignes de ladite matrice Y au moyen d'additions binaires de lignes de la matrice X selon des motifs déterminés par les lignes de la matrice M {a) ; et of dimension mx L, where M (a) is the binary matrix of dimensions mxm whose respective columns contain the binary coordinates of the respective elements

where a is a root of said primitive polynomial, obtaining the rows of said matrix Y by means of binary additions of rows of the matrix X in patterns determined by the rows of the matrix M {a); and

- obtain the data packet in which each

symbol for j = 1,2, ..., L, is composed of m bits where

i = 0, ... , m - 1, situés sur la j -ième colonne de ladite matrice Y . Selon des caractéristiques particulières, ledit dispositif de codage comprend en outre des moyens pour extraire lesdites matrices M (a) , pour d'une matrice de référence T de dimension

i = 0, ..., m - 1, located on the jth column of said matrix Y. According to particular features, said coding device further comprises means for extracting said matrices M (a), for a reference matrix T of dimension

mx (2 ^m + m - 2).

 According to a third aspect, the invention relates to:

 a node, referred to as a relay node, of a communication network, comprising a coding device as briefly described above, and

 a node, said destination node, of a communication network comprising a decoding device as briefly described above.

 Naturally, a node of a communication network may comprise both a coding device and a decoding device as briefly described above.

 The advantages offered by these devices and these nodes are essentially the same as those offered by the correlative methods briefly described above.

 Note that it is possible to realize these devices in the context of software instructions and / or in the context of electronic circuits.

 According to a fourth aspect, the invention relates to a communication network, comprising at least one relay node as briefly described above and at least one destination node as briefly described above.

Note that in such a communication network, said relay node and said destination node must, in order to be mutually compatible, use not only the same binary extension body GF (2 ^m ), ie the same value of m, but in addition the same representation of this body, that is to say, the same primitive polynomial.

The invention also relates to a computer program downloadable from a communication network and / or stored on a computer readable medium and / or executable by a microprocessor. This computer program is notable in that it includes instructions for performing the steps of the data packet coding method succinctly set forth above. above, or the method of decoding data packets succinctly set forth above, when executed on a computer.

 The advantages offered by this computer program are essentially the same as those offered by said methods.

 Other aspects and advantages of the invention will appear on reading the detailed description below of particular embodiments, given by way of non-limiting examples. The description refers to the figures that accompany it, in which:

 FIG. 1, described above, represents the operation carried out by a relay node in the network coding,

 FIG. 2, described above, schematically represents a transmission system T according to the invention,

 FIG. 3 schematically represents the structure of a data packet according to one embodiment of the invention,

 FIG. 4 represents the relationship between the operation carried out by a relay node R in the network coding, and the structure of the data packet transmitted by this relay node R,

 FIG. 5 represents, at a relay node R, the relationship between the incoming data packets and the transmitted data packet,

 FIG. 6 represents, at a relay node R, the relationship between the incoming data packets and the data packet transmitted when an incoming data packet is erased,

 FIG. 7 schematically represents a relay node R according to one embodiment of the invention,

 FIG. 8 schematically represents a destination node D according to one embodiment of the invention, and

FIG. 9 represents the representation of a vector of L symbols belonging to GF (2 ^m ) in the form of a binary matrix ^m × L.

We will first explain how one can, according to one embodiment of the invention, carry in each data packet transmitted information on how this transmitted data packet was built from initial information packets P _i (emitted by the source S). For this, as illustrated in Figure 3, is inserted, for example between the header (designated "header" in Figures 3, 4, 5 and 6), and the useful part (referred to as "payload" on these same figures) of the data packet, a sequence C of k symbols of m bits equal to the coefficients in GF (2 ^m ) of the decomposition of the payload data packet transmitted over k information packets P _i .

Consequently, the identifiers of the initial packets P _i are respectively equal to C = (0, ..., 0,1,0, ..., 0), where 1 is the i-th symbol of m bits, the others symbols being null.

When a relay R of the network N transmits an information packet without modifying it, the identifier is unchanged. When this relay performs a linear combination of information packets P _i , the identifier contains the list of coefficients used, some of the coefficients being null, as illustrated.

 in Figure 4.

When a relay R performs a linear combination:

le vecteur d'identifiants C du paquet de données sortant contient les combinaisons linéaires des identifiants des paquets d'entrée, comme illustré sur la figure 5. useful data packets Y _i already coded by other nodes of the network, each packet of useful data Y _i being characterized by a vector of identifiers

the identifier vector C of the outgoing data packet contains the linear combinations of the identifiers of the input packets, as illustrated in FIG. 5.

Thus, the operation done on the identifiers during the coefficient linear combination in GF (2 ^m ) is exactly the same as that performed on the payload packets; the relay R can therefore advantageously perform these two operations in one go.

Note that this method works even in case of packet loss. For example, if a relay R had to combine three payload data packets but did not receive it for any reason,

figure 6. Autrement dit, l'en-tête d'un paquet de données utiles R_i reçu par le destinataire D indique toujours correctement la manière dont ce paquet de données utiles R_t a été obtenu à partir de paquets d'information P_i initiaux. Par conséquent, suite à la réception des paquets de données utilesit calculates the combination of the useful data packets Y ₁ and Y ₂ , and indicates in the header the coefficients resulting from this combination, as illustrated in FIG.

FIG. 6. In other words, the header of a payload packet R _i received by the recipient D always correctly indicates the manner in which this payload packet R _t was obtained from information packets P _i initial. Therefore, after receiving the relevant data packets

the matrix K mentioned above will be known to the recipient, as required.

 It should also be noted that the implementation of this method does not require knowing the topology of the network, since the information on the way in which the packets have been coded is carried in the packets themselves. It is said to be non-coherent in the technical literature.

To retrieve information packages from

received packets, the recipient D proceeds as follows:

 the source S does not wait for acknowledgment for each packet that it transmits;

 the recipient D does not send an acknowledgment when he receives an encoded packet;

reçu, le destinataire D extrait l'identifiant on dispose ainsi d'une équation

- for each packet of useful data

received, the recipient D extracts the identifier and has an equation

linear:

 as soon as the recipient D has n≥k such equations, it checks whether the rank of the matrix of the system is equal to k, using any conventional method (for example the Gauss method); the article by C. Studholme and I. Blake entitled "Random matrices and codes for the erasure channel", Algorithmica, vol. 56, No. 4, pages 605 to 620 (2010), demonstrates that, in the case of a randomly filled matrix, the matrix is of rank equal to k with a high probability;

if the rank is less than k, the recipient D waits for the reception of new packets until the condition of rank equal to k is checked; preferably, a limit n _{max is set} to the number of packets transmitted by the source S, and the recipient D sends a negative acknowledgment (NACK) if he fails to obtain an invertible matrix after the end of the transmission of the n _max packets; in this case, the source sends additional coded packets until decoding is possible;

once this condition is verified, the following linear system is solved:

which involves adding / subtracting operations, and multiplying the symbols of a packet by the same scalar ae GF (2 ^M ), operations that we can, thanks to the invention, perform in packets, c that is to say in a parallel manner.

 FIG. 7 schematically represents a relay node R according to one embodiment of the invention.

 The relay R comprises a reception module 10, an extraction module 11, a module 12 for computing the outgoing user data packet, a memory module 13, a building module 14 and a transmission module 15.

The input module 10 is adapted to receive incoming data packets from other nodes of the network N, and to transmit these incoming data packets to the extraction module 11. The extraction module 11 is adapted to extract from each incoming packet its header (designated "H" in FIG. 7), and to transmit to the calculation module 12 the remainder of the incoming packet, ie say the set formed by a identifier vector C ^(,) and a payload data packet Y _i (referred to as "payload" in FIG. 7). The calculation module

12 is adapted to draw the coefficients a _i in the memory module 13 to calculate, in parallel:

 - the outgoing data packet

 - the outgoing identifier vector whose components are

by implementing the multiplication method in GF (2 ^m ) according to the invention.

It will be noted, concerning the memory module 13, that: this module can be integrated in the relay R as shown in FIG. 7, or constitute an external source that can be accessed by the relay R, and

the coefficients can be constant for a given relay R, or

 vary with each new packet entering the relay R (for example by means of a draw).

 The building module 14 is adapted to receive, on the one hand, the packet header H mentioned above, and on the other hand the set formed by the outgoing identifier vector C and the outgoing user data packet F ', and to build from these elements an outgoing data packet.

 Finally, the transmission module 15 is adapted to receive the outgoing data packet from the building module 14, and to transmit this outgoing data packet on the network N.

 FIG. 8 schematically represents a destination node D according to one embodiment of the invention.

 The recipient D comprises a reception module 20, an extraction module 21, a building module 22, a second member module 23, a test module 27, an inversion module 26, a resolution module 24 and a transmission module 25.

The extraction module 21 is adapted to separate, in each packet received, its header (denoted by "H" in FIG. 8), its identifier vector and its payload packet R _i .

et à ajouter des lignes égales à ces paquets de données utiles R_i au vecteur de second membre The second member module 23 is adapted to receive from the extraction module 21, as and when receiving packets by the receiving module 20, the useful data packets

and to add equal rows to these payload packets R _i to the second member vector

ajouter des lignes constituées de ces identifiants à une matrice servant à construire la matrice K . Similarly, the building module 22 is adapted to receive from the extraction module 21, as and when receiving packets by the receiving module 20, the identifier vectors and to

add lines consisting of these identifiers to a matrix used to construct the matrix K.

 Similarly, the test module 27 is adapted to receive, as packets are received by the receiving module 20, said matrix being constructed by the building module 22, and to determine whether the determinant of this module matrix is different from zero, that is to say if this matrix is regular (rank equal to k).

When this is not the case, the operation described above continues. When this is the case, the reception module 20 is adapted to stop receiving packets, and the inversion module 26 is adapted to calculate the inverse of the matrix K obtained. The resolution module 24 is adapted to receive said second member vector from the second member module 23, as well as the inverse of the matrix K from the inversion module 26, and to calculate the product of these elements. two magnitudes by implementing the multiplication method in GF (2 ^m ) according to the invention, so as to retrieve the initial information packets.

initiaux de la part du module de résolution 24, et à transmettre ces paquets d'information à l'utilisateur du nœud destinataire D. Finally, the transmission module 25 is adapted to receive the information packets

initials from the resolution module 24, and to transmit these information packets to the user of the destination node D.

As explained above, the coding and decoding considered in the present invention are realized in a binary extension body GF (2 ^m ), where m> 1. By this we mean that any given symbol composed of m bits x _y , where we associate the element of GF (2 ^m ), noted whose

choisie sont précisément lesdits bits x_y ; autrement dit :

binary coordinates on a canonical basis

chosen are precisely said bits x _y ; in other words :

 where a is a root of a predetermined primitive polynomial.

Le

We will now explain how we can perform the multiplication in GF (2 ^m ) only by means of binary additions (XOR). Let's take an example in the GF (2 ⁴ ) body constructed from the primitive polynomial to verify the equation:

The

result of the multiplication of the element of

binary coordinates by the element of

est l'élément

dont les coordonnées binaires sont obtenues comme suit :binary coordinates

is the element

whose binary coordinates are obtained as follows:

by definition of the matrix M (a), whose successive columns are constituted by the binary coordinates of the elements a, aa, a ² a and a ³ a of

GF (2 ⁴ ) successively. To calculate these columns, it will be noted, for example, that

The same procedure is followed for a ² a and a ³ a. The final result is:

In the general case of a GF body (2 ^m ) for any m, we calculate:

 or :

• X is the column vector containing the m binary coordinates

 • Y is the column vector containing the m binary coordinates of y, and

• la matrice est la matrice binaire mx m dont les

• the matrix is the binary matrix mx m whose

 columns contain the binary coordinates of the elements

GF (2 ^m ), either

We will say that the matrix M (a) is the "binary equivalent" of the element a for the multiplication in GF (2 ^m ).

pour un certain entier 0 < k≤ 2^m - 2 , on peut se contenter de considérer les matrices

As all the non-zero elements of GF (2 ^m ) can be written in the form

for a certain integer 0 <k≤ 2 ^m - 2, we can content ourselves with considering the matrices

 associated with the consecutive powers of a.

Note that all these matrices can be obtained by consulting a "large" binary matrix

where n = 2 ^m - 1, of dimension mx (2 ^m + m - 2), previously constructed, whose columns contain the coordinates of a ^k for k≥ 0. In this matrix T, which will be called "reference matrix", the last (m - 1) columns are a simple copy of the first (m -1) columns. M {a ^k ) is then the sub-matrix obtained by extracting the columns n (k + 1) to (k + m) from the reference matrix T, which will be noted as follows:

By definition, the product of two elements is equal to

so that the matrix associated with the

référence T ; on peut ainsi obtenir très simplement le produit des matrices par :product, which can be read directly into the matrix of

reference T; it is thus possible to obtain very simply the product of the matrices by:

est

puisque

qui est la matrice identité. In the same way, the matrix associated with the inverse of an element

is

since

which is the identity matrix.

If we take the same example on GF (2 ⁴ ) (constructed from the primitive polynomial, the reference matrix T is given

 by :

 so that, for example:

 It is easy to check, for example, that the product of the bit matrices is equal to as expected.

 Following the same example, we find:

 so that, or

dans GF (2⁴ ) est donnée par le produit matriciel : As another example, multiplication by

in GF (2 ⁴ ) is given by the matrix product:

de l'élément x . Note that this expression only uses XORs of the binary coordinates

of the element x.

It is thus convenient to perform the multiplication of any element x of GF (2 ^m ) by any element ae GF (2 ^m ) on the basis of equation (1) above and sub-matrices of the reference matrix T , which only involves XORs of the coordinates of x.

We will now explain how this method can be used to perform multiplication by any GF (2 ^M ) element at the packet level.

The matrix product of equation (1) can easily be parallelized when each x _i is a binary vector of length L. For example, the multiplication by an element a in GF (2 ⁴ ) becomes:

 where, advantageously, all operations are performed in GF {2).

We will use the following notation to denote

the line n ° i of a matrix x of dimension mx L; the matrix product above can then be conveniently seen as implementing XORs of these lines x (i, -). For example, the multiplication by presented above

 can be conveniently written in the form:

The above considerations explain how one can, during coding or decoding in a Galois body GF (2 ^m ), where m> l, defined in using a predetermined primitive polynomial, calculate a packet Q = a P, where the number a belongs to GF (2 ^m ), and P is a data packet P = (x _1; ..., x _L ), in where Xj, for j = 1,2, ..., L "with L≥ 1, is a symbol composed of a sequence of m bits x _tj , where i = 0, ..., m - 1.

 According to the present embodiment, the following substeps are implemented.

la i -ème ligne, où i = 0, ... , m - 1, de cette matrice X . Autrement dit, si l'on regarde le paquet P comme une ligne de bits numérotés de 1 à mx L , la ligne est définie

a) We fill a binary matrix X of dimension mx L by placing the bits x _tj composing each symbol Xj along the jth column, as illustrated schematically in FIG.

the i-th line, where i = 0, ..., m - 1, of this matrix X. In other words, if we look at the packet P as a line of bits numbered from 1 to mx L, the line is defined

by :

 b) The binary matrix Y, of dimension mx L, is calculated using the matrix product:

where the matrix M (a) is the binary equivalent, defined above, of the element a. As explained above, performing this matrix product amounts to calculating the rows of the matrix Y by XORs of rows of the matrix X, in binary patterns determined by the rows of the matrix M (a). This is advantageously done in vector manner on the L symbols of the packet P. c) Finally we get the package in which

each symbol y _p for j = 1,2, ..., L, is composed of the m bits y _tj , where i = 0, ..., m - 1, located on the jth column of the matrix Y obtained previously. In other words, it is sufficient to read the matrix Y column by column.

We will, finally, explain how we can use this method to perform, always at the level of the packets, the multiplication by any matrix A whose elements has _Uj belong to

En effet, une telle matrice peut être aisément transformée en une matrice binaire, que l'on appellera « image binaire » de la matrice A , en remplaçant tous ses éléments par leurs équivalents binaires mxm définis ci-

Indeed, such a matrix can be easily transformed into a binary matrix, which will be called "binary image" of the matrix A, replacing all its elements by their binary equivalents mxm defined below.

above.

 The invention may be implemented within the nodes, for example a relay node or a destination node of a communication network, by means of software and / or hardware components.

 The software components can be integrated into a typical network node management computer program. Therefore, as indicated above, the present invention also relates to a computer system. This computer system conventionally comprises a central processing unit controlling signals by a memory, as well as an input unit and an output unit. In addition, this computer system may be used to execute a computer program comprising instructions for implementing any of the methods of encoding, or decoding, data packets according to the invention.

 Indeed, the invention also relates to a downloadable computer program from a communication network comprising instructions for executing the steps of a method of encoding, or decoding, data packets according to the invention, when it is run on a computer. This computer program may be stored on a computer readable medium and may be executable by a microprocessor.

 This program can use any programming language, and be in the form of source code, object code, or intermediate code between source code and object code, such as in a partially compiled form, or in any another desirable form.

 The invention also relates to an information carrier, irremovable, or partially or completely removable, readable by a computer, and comprising instructions of a computer program as mentioned above.

The information carrier may be any entity or device capable of storing the program. For example, the medium may comprise storage means, such as a ROM, for example a CD ROM or a ROM of microelectronic circuit, or a magnetic recording means, such as a hard disk, or a USB flash drive ("USB flash drive").

 On the other hand, the information medium may be a transmissible medium such as an electrical or optical signal, which may be conveyed via an electrical or optical cable, by radio or by other means. The computer program according to the invention can in particular be downloaded to an Internet type network.

 Alternatively, the information carrier may be an integrated circuit in which the program is embedded, the circuit being adapted to execute or to be used in performing any of the methods of encoding, or decoding, packets data according to the invention.

Claims

1. A method of coding data packets in a network (N), comprising the steps of: receiving r≥1 useful data packets Y _i each consisting of a linear combination

where the coefficients are taken in a GF extension body (2 ^m ) defined in

by means of a chosen primitive polynomial, of the same k≥1 information packets said initial packets, each information packet containing L≥ 1

 symbols each consisting of a sequence of m> l bits; computing a outgoing payload packet Y 'consisting of a linear combination

said user data packets Y where the coefficients α _i are taken in said extension body GF (2 ^m ); and  transmitting said outgoing user data packet Y '; characterized in that said step of computing the outgoing payload packet Y 'comprises at least one substep of multiplication

of all the symbols of a data packet in which for

is a symbol consisting of a sequence of m bits

where by the same number a belonging to GF (2 ^m ), and in this

 that said multiplication is performed as follows: a) filling a binary matrix X of dimension mx L by placing the bits constituting each symbol X _j along the -th column

 said matrix X; b) calculation of the binary matrix

of dimension mx L, where M (a) is the binary matrix of dimensions mx m whose respective columns contain the binary coordinates of the respective elements is a root of said primitive polynomial, in

obtaining the rows of said matrix Y by means of binary additions of rows of the matrix X in patterns determined by the rows of the matrix M (a); and c) obtaining the data packet in which

each symbol y _p for j = 1,2, ..., L, is composed of m bits y _tj , where i = 0, ..., m - 1, located on the jth column of said matrix Y. 2. Encoding method according to claim 1, characterized in that said matrices are extracted from a reference matrix T of dimension mx (2 ^m + m - 2). The coding method according to claim 1 or claim 2, wherein each of said payload packets Y _i is contained in a data packet further containing an identifier vector.

comprising said coefficients and wherein said payload packet F 'is contained in a data packet containing in addition a vector of iden ifiants outgoing

characterized in that the calculation of said outgoing identifiers vector C is performed by means of the same operations and simultaneously with computing said outgoing user data packet F '. A method of decoding data packets, comprising the steps of: reception of n> 1 coded data packets where, for

i = 1, ..., n, each coded data packet

is a linear combination of the same k≥ \ information packets P _j each containing L≥1 symbols consisting of a sequence of m> 1 bits, and where the coefficients c _tj are taken in an extension body GF (2 ^m ) defined by means of a primitive polynomial chosen, and resolution of the system formed by said linear combinations, so as to obtain said information packets P _j , characterized in that said step of resolving a system of linear combinations comprises at least one sub-step of multiplying all

the symbols of a data packet in which x _r for

j = l, ..., L, is a symbol composed of a sequence of m bits where

i = 0, ..., m - 1, by the same number a belonging to GF (2 ^m ), and in that said multiplication is performed as follows: a) filling a binary matrix X of dimension mx L by placing the bits x _tj composing each symbol Xj along the jth column of said matrix X;  b) calculation of the binary matrix

of dimension mx L, where the matrix M {a) is the binary matrix of lux dimensions! whose respective columns contain the binary coordinates of the respective elements where a is a root of said polynomial

primitive, by obtaining the rows of said matrix Y by means of binary additions of rows of the matrix X in patterns determined by the rows of the matrix M {a); and c) obtaining the data packet in which

each symbol y _p for j = 1,2, ..., L, is composed of m bits where

i = 0, ..., m - 1, located on the jth column of said matrix Y. 5. Decoding method according to claim 4, characterized in that said matrices are extracted from a

 reference matrix T of dimension

 Data packet coding device comprising means for: - receive r≥l useful data packets Y _i each constituted by a linear combination

where the coefficients cf are taken in an extension body GF (2 ^m ) defined by means of a chosen primitive polynomial, of the same k≥1 information packets called initial packets, each information packet containing

 L≥1 symbols each consisting of a sequence of m> l bits; calculating an outgoing useful data packet F 'consisting of a linear combination

useful data packets Y _n where the coefficients ", are taken in said extension body GF (2 ^m ); and  transmitting said outgoing user data packet F '; characterized in that it further comprises, for the purpose of performing at least one multiplication required for computing the payload packet

outgoing F ', of all the symbols of a data packet

in which for j = 1, ..., L, is a symbol composed of a sequence of m bits

or

by the same number belonging to GF (2 ^m ), means for: - fill a binary matrix X of dimension mx L by placing the bits

composing each symbol X _j along the jth column of said matrix X;  - calculate the binary matrix

of dimension mx L, where M (a) is the binary matrix of dimensions mxm whose respective columns contain the binary coordinates of the respective elements a is a root of said primitive polynomial, in

 obtaining the rows of said matrix Y by means of binary additions of rows of the matrix X in patterns determined by the rows of the matrix M (a); and - obtain the data packet), in which each

symbol

for

is composed of the m bits where

located on the jth column of said matrix Y. 7. Encoding device according to claim 6, characterized in that it further comprises means for extracting said matrices M (a), for a reference matrix T dimension

Coding device according to claim 6 or claim 7, characterized in that each of said useful data packets Y _i being contained in a data packet further containing a identifier vector

comprising said coefficients and said payload packet F 'being

contained in a data packet also containing an outgoing identifier vector

 it further comprises means for performing the calculation of said identifier vector outgoing C by means of the same operations and simultaneously calculating said outgoing user data packet F '. 9. Device for decoding data packets, comprising means for: - receive n> \ coded data packets where, for

i = 1, ..., n, each coded data packet

is a linear combination of the same k> \ information packets P _j each containing L≥1 symbols consisting of a sequence of m> 1 bits, and where the coefficients c _tj are taken in a GF extension body (2 ^m ) defined by means of a chosen primitive polynomial; and solving the system formed by said linear combinations, so as to obtain said information packets P _j ; characterized in that it further comprises, for the purpose of performing at least one multiplication Q = a P, required for the resolution of said system of linear combinations, of all the symbols of a data packet in which is a symbol composed of

following of m bits by the same number a belonging to

GF (2 ^m ), ways to: - Fill a binary matrix X of dimension mx L by placing the bits x _tj component each symbol Xj along the jth column of said matrix X; - calculate the binary matrix

of dimension mx L, where M (a) is the binary matrix of dimensions mxm whose respective columns contain the binary coordinates of the respective elements is a root of said primitive polynomial, in

 obtaining the rows of said matrix Y by means of binary additions of rows of the matrix X in patterns determined by the rows of the matrix M (a); and - obtain the data packet in which each

symbol y _p for j = l, 2, ..., L "is composed of m bits where

located on the jth column of said matrix Y.

10. Decoding device according to claim 9, characterized in that it further comprises means for extracting said matrices M (a) for a reference matrix T of dimension

1 1. Node, said relay node (R), of a communication network (N), characterized in that it comprises a coding device according to any one of claims 6 to 8. 12. Node, said destination node (D), of a communication network (N), characterized in that it comprises a decoding device according to claim 9 or claim 10. 13. Communication network (N), comprising at least one relay node (R) according to claim 1 1 and at least one destination node (D) according to claim 12. A non-removable, or partially or fully removable data storage medium, comprising computer program code instructions for performing the steps of a data packet encoding method according to any one of claims 1 to 3, or a method of decoding data packets according to claim 4 or claim 5. 15. 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 the execution of the steps of a method of encoding data packets according to any one of claims 1 to 3, or a method of decoding data packets according to claim 4 or claim 5 when executed on a computer.