Canon Kabushiki Kaisha

Canon Research Centre France S.a.

Philippe Piret

Claude Le Dantec

Philippe Le Bars

Frédéric Lehobey

Pascal Rousseau

Patrice Nezou

Laurent Frouin

Pascal Coudray

Arnaud Closset

Mohamed Braneci

Julien Sevin-Renault

Frédérique Ehrmann-Patin

Francedillaois Delumeau

A transmitting apparatus transmits a plurality of data packets to a receiver in a communication system, by transmitting one or more data packets from a list of data packets to be transmitted, and determining whether an acknowledgment is received for each transmitted data packet. When it is determined that an acknowledgement has not been received for at least one data packet, referred to as an unacknowledged data packet, the apparatus selects one or more additional data packets from the list of data packets to be transmitted, generates one or more parity packets by encoding a block of data containing a combination of the selected one or more additional data packets and at least one unacknowledged data packet using a forward error correction scheme, and transmits at least one of the generated parity packets.

Method, device and software application for transmitting data packets in a communication system

A method of decoding a one-point algebraic geometric code defined on an algebraic curve of type C(a,b) represented by an equation F(X,Y) =0 of degree b in X and of degree a in Y over F, includes calculating extended error syndromes (&#x3c3;(i)) associated with a received word (r) and determining the values of errors in each component r(x,y,(x)) of the received word r, on the basis of the extended error syndromes calculated.

Decoding method for algebraic geometric codes and associated device

The present invention concerns a method of coding information symbols according to a code defined on a Galois field F, where q is an integer greater than 2 and equal to a power of a prime number, and of length n=p(q&#x2212;1), where p&#x3e;1. This coding is designed so that there exists a corresponding decoding method, also disclosed by the invention, in which the correction of transmission errors essentially comes down to the correction of errors in p words of length (q&#x2212;1) coded according to Reed-Solomon. The invention is particularly advantageous when, through a suitable choice of parameters, the code according to the invention is an algebraic geometric code: in this case, it is possible to correct the transmission errors by the method already mentioned and/or by a conventional method which is less economical but has a higher performance.

Information coding by algebraic geometric code offering two decoding options

A method of decoding a one-point algebraic geometric code defined on an algebraic curve of the kind C(a,b), represented by an equation of degree b in X and of degree a in Y. For any received word, transmission errors affecting the received word are located. The correction of errors in the word, which belongs to an algebraic geometric code, is then reduced to the correction of errors in a certain number, at most equal to a, of words belonging to a Reed-Solomon code. Devices and apparatuses adapted to implement this method are also described.

Decoding and error correction for algebraic geometric codes

The present invention concerns channel codes particularly well adapted to transmission in channels in which errors tend to occur in bursts. Moreover, the codes according to one embodiment of the invention using an algebraic geometric curve are easy to decode and have a relatively high minimum distance. The invention also relates to the corresponding encoding and decoding methods, as well as the devices and apparatuses adapted to implement those methods. Application is in particular to mass storage, and to systems of communication by OFDM.

Algebraic geometric code adapted to error bursts

A method of encoding information symbols comprises a step in which a word, orthogonal to a matrix H, the element Hof which is equal to the value taken by some monomial h=YXat the point Pof some locating set, is associated with every block of k information symbols belonging to a Galois field F. The method chooses the set of monomials hso as to define codes which can be decoded with an algorithm by aggregates of low complexity, and which provides a very good error correction capability, in particular for channels in which the errors tend to occur in bursts. Devices and apparatuses adapted to implement this method are also disclosed.

Channel encoding adapted to error bursts

A method of decoding a one-point algebraic geometric code of dimension k and length n, in which, in order to identify the position of the errors in a received word, the syndromes matrix S, of size (n&#x2212;k)&#xd7;(n&#x2212;k), is defined, of which the elements Sof each line i are calculated, for j between 1 and w(i), where the boundary w is a decreasing function, using the syndromeof the received word. Matrices Sare constructed for the successive values of u starting with S=S, and, for u&#x3e;1, each matrix Sis obtained by performing on the matrix S, column permutations where appropriate, then linear manipulations involving the line of index u. These steps are performed in such a manner as to find a matrix Swhich has a line of index less than or equal to &#x3bb; of which the elements are zero in the first w(&#x3bb;) columns. The invention also relates to devices and apparatuses adapted to implement this method.

Methods and devices for decoding one-point algebraic geometric codes

The present invention concerns a device () for the encoding of information symbols to transmit or to record, and for the correction of errors among the symbols received or read, according to codes defined over a Galois field F, where q is an integer greater than 2 and equal to a power of a prime number, and in which a set of elements of Fare considered which are denoted y(j), where j=1, . . . , R with 1&#x2266;R&#x2266;q&#x2212;1 and l=0, . . . , p&#x2212;1 with p&#x3e;1. Said device () comprises a Reed-Solomon encoder (), a Reed-Solomon decoder () and a unit () serving to calculate the inverse of a Vandermonde matrix as well as:

Encoding/decoding device using a reed-solomon encoder/decoder

The present invention concerns an encoding method in which encoding is performed of any information word a of length k in the form of a word &#x3bd; belonging to a Reed-Solomon code C of dimension k' and length n&#x2032; (with n&#x2032;&#x2212;k&#x2032;=n&#x2212;k) such that the components of &#x3bd;&#x2032; situated in (n&#x2032;&#x2212;n) arbitrary predetermined positions be systematically equal to respective predetermined constants (for example, all zero). The possibility then exists of deleting those components of fixed value to obtain a word &#x3bd; of length n belonging to a code C, which thus constitutes a code that is shortened with respect to code C. The invention also relates to devices and apparatuses adapted to implement the encoding method. The invention may be used for encoding by means of an algebraic geometric code, when such encoding may be implemented by encoding by means of a plurality of shortened Reed-Solomon codes.

Information encoding by shortened Reed-Solomon codes

The present invention concerns a method and apparatus of decoding a one-point algebraic geometric code defined on an algebraic curve represented by an equation in X and Z of degree 2in Z, where &#x3c6; is a strictly positive integer and &#x3bc; an integer greater than 1, obtained by taking the fiber product of &#x3bc; component algebraic equations, each of said component equations governing the unknown X and an unknown Y, where i=0, . . . , &#x3bc;&#x2212;1, and being of degree 2in Y. This method comprises the decoding of 2'clustered' codes, all defined on the same algebraic curve represented by one of said component equations.

Decoding for algebraic geometric code associated with a fiber product

Method and apparatus for decoding a one-point algebraic geometric code of dimension k and length n, in order to identify the position of the errors in a received word, the syndromes matrix S, of dimension (n&#x2212;k)&#xd7;(n&#x2212;k) is defined, of which the elements Sof each line i are calculated, for j between 1 and w(i), where the boundary w is a decreasing function, using the syndromeof the received word, as well as the matrix S* obtained by 'extending' the matrix S, that is to say by calculating the value of certain elements S*where j is greater than w(i). This method makes it possible in certain favorable cases to find the erroneous positions of the received word when the number of errors is greater than (n&#x2212;k+1&#x2212;g)/2, even if it is not possible to calculate all the elements of S* conventionally required by a two-stage algorithm to perform that correction.

Error locating methods and devices for algebraic geometric codes

A method for encoding and decoding a sequence of words, corresponding signal, encoder, decoder, computer programs and storage means. A method for encoding a sequence of source words includes a step of selecting an encoding function to be applied to a source word to be encoded as a function of the content of the word to be encoded and of at least one preceding source word in the sequence so that the concatenation of two consecutive encoded words has no binary element, called an isolated binary element, sandwiched between two binary elements with a value different from that of the isolated binary element. The method further includes a step of encoding the word to be encoded implementing the selected encoding function.

Method for the encoding and decoding of a sequence of words, corresponding signal, encoder, decoder, computer programs and storage means

A method of decoding product codes is disclosed, in which the symbols of each codeword may be placed in a table comprising nrows and ncolumns, such that the symbols constituting each row form a permitted word of length naccording to a first component code able to be decoded by means of an algorithm Afor correction with erasures, and the symbols constituting each column form a permitted word of length naccording to a second component code able to be decoded by means of an algorithm Afor correction with erasures. According to the method, a correction of a row or column is only accepted when the result of the correction is deemed reliable, otherwise all the symbols of that row or column are erased. Devices and apparatus adapted to implement this method are also disclosed. The method is preferably applied to algebraic geometric codes.

Low-cost methods and devices for the decoding of product cases

To interleave a binary sequencerepresented by the polynomial where n=R.M with R&#x2267;M, i being an integer which may be written i=r.M+c, r and c being integers, r&#x2267;0 and c &#x3b5; [0, M&#x2212;1], there is obtained, from the sequence, an interleaved binary sequence*. The interleaved binary data sequence* represented by the polynomial where i*=[r&#x2212;h(c)].M+c mod n, the h(c) being obtained by the choice of an M-tuple=[h(0), . . . , h(M&#x2212;1)] of non-negative integers less than R&#x2212;1 such that, given a predetermined set &#x3a0; of circulating matrices P of dimension M&#xd7;M, for any matrix P of &#x3a0;, the residues modulo R of the components of the vector.P are not nil; and the corresponding choice of an M-tupleobtained fromby the application of a permutation moving h(c) to position L&#xd7;c mod M, the integer L being relatively prime with M. (It is noted that the above underlining of the variables, and the above single bracketing, is in the original and is meant to be permanent.)

Method of interleaving a binary sequence

Turbocoding methods use a first RSC coder operating on sequences of binary data, and a second RSC coder operating on binary sequences* each obtained fromby means of a predetermined permutation. These permutations are designed so that, for any sequencerepresented by a polynomial divisible by the recursion polynomial, the associated sequence* is also represented by a polynomial divisible by the recursion polynomial. These permutations are relatively simple to implement, and are applicable to all the data sequenceswhich have a length which is a multiple of the period of the recursion polynomial. In addition, once the transfer functions of the coders and the sequence length have been chosen, it is possible to select, amongst the corresponding permutations, the one which will probably offer the highest minimum distance of the code. Application to devices and apparatus implementing these methods.

Growing community of inventors

Cesson-Sevigne, France

Philippe Piret