Canon Kabushiki Kaisha

Frédéric Lehobey

Philippe Piret

Philippe Le Bars

Frédérique Ehrmann-Patin

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 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.

Growing community of inventors

Rennes, France

Frédéric Lehobey