Abstract:
Embodiment of the invention is to make the number of interleave sequences and the number of redundant bits as small as possible without increasing the number of bits per symbol so much. By encoding data into an error-correcting code by using an algebraic geometric code consisting of an algebraic curve surface having a genus g over a projective plane P c−1 (GF( 2m )), where m is a positive integer, the code up to a length of 2 m +2 1+m/2  g is constructed. In particular, by using a “Fermat code,” a version of the algebraic geometric code, consisting of a Fermat curve “C (L) : X L +Y L +Z L =0” over the P 2 (GF(2 2m )), where (m, L)=(5, 11), 4-Kbyte data constituting one sector can be encoded into the code made up of 10-bit symbols.

Description:
CROSS-REFERENCES TO RELATED APPLICATIONS  
       [0001]     This application claims priority from Japanese Patent Application No. JP 2004-096512, filed Mar. 29, 2004, the entire disclosure of which is incorporated herein by reference.  
       BACKGROUND OF THE INVENTION  
       [0002]     The present invention relates to information recording/reproducing devices and, more particularly, to an information recording/reproducing device employing a new error correction coding method.  
         [0003]     For information recording/reproducing devices such as magnetic disk devices, magneto-optical disk device, and compact disk devices, Reed-Solomon codes are used. This code consists of 2 8  elements in magnetic disk devices. A Reed-Solomon code over a Galois field GF(2 8 ) that is a set of elements for pairs, of which addition, subtraction, multiplication, and division are defined, but “divide by 0” is not defined in division, is used. This Reed-Solomon coding, in which each symbol consists of eight bits (one byte) as a unit of computing, makes error correction of signals that are recorded and reproduced.  
         [0004]     The Reed-Solomon codes that are capable of correcting up to t symbols are constructed by including 2t redundant (parity) symbols. The length of sectors that are units of data to be recorded and reproduced at a time is 512 symbols (512 bytes). However, because the length of the Reed-Solomon codes that can be constructed over the GF(2 8 ) is not greater than 2 8 −1=255 symbols, data is separated (interleaved) into three or more blocks and each block is constructed by the RS error correction coding.  FIG. 10  shows the order of symbols including Reed-Solomon parity bytes recorded in a sector and associated RS code structures.  
         [0005]     An advantage of the Reed-Solomon codes is that, in polynomial expression of codewords, the positions of the symbols can be arranged from the highest order α n−1 , α n−2 , . . . α 2 , α 1 , α 0  (α: a primitive root of Galois field) and the positions of the symbols can be calculated orderly only by a multiplier during Chien search when the codewords are decoded. The Chien search is a method of evaluating an equation by assigning elements to it in order.  
         [0006]     With a recent trend of using magnetic disk devices in video application, the International Disk Drive Equipment Material Association (IDEMA) and other organizations are discussing the usage of sectors longer than 512 bytes in a magnetic disk device, while maintaining conventional read/write processing in units of 512 bytes on the interface to the host side. One suggestion is a Reed-Solomon code organization with eight interleaving sequences that can preferably be used as an error-correcting code for data separated by a sector length of 4 Kbytes=32768 bits.  
         [0007]     Relevant references include the following: 
    Non-patent Document 1: Shinji Miura, “Algebraic Geometric Codes on a Plane Curve,” the Institute of Electronics, Information and Communication Engineers Transaction (A), Vol. J75-A, No. 1, pp. 1735-1745, 1998;     Non-patent Document 2: T. Shibuya, H. Jinushi and S. Miura, “On the Performance of Algebraic Geometric Codes,” EEICE Transaction on Fundamentals, Vol. E79-A, No. 6, pp. 291-310, June 1996;     Non-patent Document 3: Shojiro Sakata “Algebraic Geometric Codes and Decoding Method Thereof,” Mathematical Sciences, No. 421, pp. 33-40, No. 422, pp. 58-60, 1998;     Non-patent Document 4: S. Sakata, “A Vector Version of the BMS Algorithm for Implementing Fast Erasure-and-Error Decoding of One-Point AG codes,” Proc. AAECC-12, Springer Verlag, pp. 291-310, 1997;     Non-patent Document 5: J. P. Hansen, H. E. Jensen, and R. Koetter, “Determination of Error Values for Algebraic-Geometry Codes and the Forney Formula,” IEEE Transaction on Information Theory, Vol. 44, No. 5, pp. 1881-1886, September 1998; and     Patent Document 1: JP-A No. 118471/2002.    
 
       SUMMARY OF THE INVENTION  
       [0014]     Since the ratio of errors in a sector is proportional to “the probability of interleaved codeword bytes (symbols) becoming biased and uncorrectable” and “the number of interleaving sequences,” that ratio can be lowered when interleaving is not performed from the ratio when interleaving is performed. However, due to the Reed-Solomon code length restriction, for error correction coding of data with a length of a 0  bits without the use of interleaving, it is necessary to construct an RS code with symbols, each consisting of bits corresponding to an integer m that satisfies a 0 /m≦2 m −1. For example, if data with a length of 4 Kbytes (32768 bits) is RS coded without interleaving, it is conditioned that the number of bits per symbol m is equal to or greater than 12 bits. In fact, the number of redundant bits not only increases in proportion to the number of correctable errors, but also increases in proportion to the number of bits per symbol m. This means that the number of redundant bits increases by a factor of 8 or more if the sector length increases by a factor of 8 and the number of correctable errors increases by a factor of 8. This also means that, as the number of bits per symbol m increases, the number of bits needed to correct one error (2m) increases, and, in other words, the efficiency of error correction of redundant bits decreases.  
         [0015]     Even if interleaving is inevitable when decoding delay and other conditions are taken into account, it is desirable not to increase the number of bits per symbol m so much and to make the number of interleaving sequences and the number of redundant bits as small as possible.  
         [0016]     By using algebraic geometric codes (AG codes) over the GF(2 m ), codes that are longer than 2 m −1 are constructed. In this code structure, extra redundant symbols are added, but the number of redundant bits is reduced by decreasing the number of bits per symbol instead.  
         [0017]     An algebraic geometric code consists of an algebraic curve surface “C: f(X 1 :X 2 : . . . :X c )=0” over a projective plane P c−1 (GF(2 m )) (how to construct this code will be described later). The components of the projective plane P c−1 (GF(2 m )) are the ratios of coordinates (GF(2 m )) c /{(0, 0, . . . , 0)}. On this projective plane, (α 1 , α 2 , . . . , α c ) and (χα 1 , χα 2 , . . . , χα c ) (where χ≠0) are regarded as same points and represented as (α 1 , α 2 , . . . , α c ) particularly in consideration of the ratios of the coordinates. The algebraic geometric codes are a general form of the Reed-Solomon codes and, in other words, the Reed-Solomon codes are a particular version of the algebraic geometric codes.  FIG. 1I  is a diagram showing relationship among the Reed-Solomon codes, algebraic geometric codes, elliptic codes, and Fermat codes, the latter two of which will be described later.  
         [0018]     For the algebraic curve surface, a parameter called genus g is defined. The genus is a generalized quantity representing the number of holes of a closed surface in a three-dimensional space. It is known that the genus of a curve remains unchanged after the curve is transformed by (is invariant to) birational mapping and that g=(a−1)(b−1)/2 for a C a   b  curve on a projective plane P 2 (GF(2 m )) (refer to the non-patent documents 1 and 2 above).  
         [0019]     Suppose that E(C, GF(2 m )) represents the following set where F is the number of elements in E(C, GF(2 m )). A point included in E(C, GF(2 m )) is called a GF(2 m ) rational point of C. If the GF(2 m ) field is evident from the context, the point is simply called a rational point of C. 
 
 E ( C,GF (2 m )):={(α 1 :α 2 : . . . :α c )=0}  Equation 1 
 
         [0020]     In E(C, GF(2 m )), one point Q is fixed and points that belong to E(C, GF(2 m ))/{Q} are numbered as P (1) , P (2) , . . . , P (ε−1) . By setting the dimension of a function space L(r 0 Q) over C to be r, an AG codeword consisting of C is defined as a column vector w that satisfies Hw=0 for a matrix H that is expressed in equation 2. Here, the bases of L(r 0 Q) are represented as {v 0 (P), v 1 (P), v 2 (P), . . . , v r−1 (P)}.  
               H   =       (     h     i   ,   j       )           1   ≤   i   ≤   r     ,       1   ≤   j   ≤   n           ,           ⁢       h     i   ,   j       =       υ     i   -   1       ⁡     (     P     (   f   )       )                 Equation   ⁢           ⁢   2             
 
         [0021]     More specifically, code length n up to ε−1 can be given, in which c satisfies equation 3. 
 
ε≦2 2m +1+2 m+1   g   Equation 3 
 
         [0022]     When there is a square matrix M which satisfies equation 4 as a condition of the check matrix H, the AG codeword can be constructed as a systematic code. 
 
 MH=[H   1   |I   r ]  Equation 4 
 
         [0023]     The following are known. In the case of the C a   b  curve and Q=(0:1:0) over the projective plane P 2 (GF(2 m )), r 0 =r+1−g is satisfied when r&gt;2 g; random errors up to (r−g)/2 in number are correctable when r&gt;3 g−1; and a set that is expressed in equation 5 is assigned to the bases of L(r 0 Q). 
 
{ x ( P ) i   y ( P ) j   |ai+bj≦r− 1+ g, 0≦ i, 0≦ j&lt;a},   Equation 5 
 
 where x(X:Y:Z)=X/Z, y(X:Y:Z)=Y/Z 
 
         [0024]     Hence, when 2t+g&gt;3 g−1, a codeword in which up to t symbols are correctable can be constructed by including 2t+g redundant symbols.  
         [0025]     Normally, the bases of equation 2 are numbered in ascending order of ai+bj.  
         [0026]     In the following, the use of a Fermat code that is an AG code consisting of a Fermat curve “C (L) : X L +Y L +Z L =0” over the projective plane p 2  (GF(2 2m )) will be discussed. Given φ(X:Y:Z):=(X:Y:Y+Z), φ(C (L) ) is a C L−1   L  curve (a C a   b  curve where (a, b)=(L□1, L)) and, therefore, g=(L−1)(L−2)/2.  
         [0027]     By assigning C=φ(C (L) ) and Q=(0:1:0), equations 2 and 3 are satisfied. When L is a divisor of 2 m +1 that is greater than 1, it is presumed that equation 3 always has equality. The bases of equation 2 are specifically ordered as in equation 6.  
                   {               υ   0     ⁡     (     X   :     Y   :   Z       )       =   1                                 υ   1     ⁡     (     X   :     Y   :   Z       )       =     X     Y   +   Z         ,         υ   2     ⁡     (     X   :     Y   :   Z       )       =     Y     Y   +   Z                                       υ         1   2     ⁢     s   ⁡     (     s   +   1     )         +   λ       ⁡     (     X   :     Y   :   Z       )       =         (     X     Y   +   Z       )     λ     ⁢       (     Y     Y   +   Z       )       s   -   λ           ⁢                   (       2   ≦   s   ≦     l   -   2       ,     0   ≦   λ   ≦   s       )                     υ   λ     ⁡     (     X   :     Y   :   Z       )       =     X     Y   +   Z         ,     ×       υ     λ   -     (     l   -   1     )         ⁡     (     X   :     Y   :   Z       )                 (         1   2     ⁢     (     l   -   1     )     ⁢   l     ≦   λ   ≦     r   -   1       )                     Equation   ⁢           ⁢   6     ⁢                       
 
         [0028]     Here, {v 0 (φ(P)), v 1 (φ(P)), v 2 (φ(P)), . . . , v r□1 (φ(P))} are the bases of a function space L(r 0 φ −1 (Q)) over C(L).  
         [0029]     Matrix H defined by equation 2 when C=φ(C (L) ) and Q=(0:1:0) agrees with matrix H defined by equation 2 when C=C (L)  and Q=φ −1 (0:1:0). This is generally true when the components φX, φ Y , and φ Z  of φ(X:Y:Z)=(φ X :φ Y :φ Z ) are represented by rational mapping of X, Y, and Z and the components of φ −1 (X:Y:Z) are also represented by rational mapping of X, Y, and Z (that is, φ(X:Y:Z) is birational mapping).  
         [0030]     Data of 4 Kbytes, that is, 4×1024×8 bits is equivalent to 3277 10-bit symbols. The maximum length of a Fermat code with set values of (m, L)=(5, 11) is 3904 symbols and g=45. Thus, the number of redundant symbols is 3904−3277=627. The maximum number of correction symbols is therefore 291 (291×2+45=627). By using this code, it will be possible to construct a 4-Kbyte sector with 10-bit symbols without interleaving.  
         [0031]     In particular, when equation 7 is satisfied, equations 8 and 9 are satisfied and points can be calculated by using the elements in subsets (subfields) and n-th power roots thereof.  
             {               2   ⁢   m     =         2   u     ⁢     (       2   ⁢   e     +   1     )     ⁢           ⁢   where   ⁢             ⁢             ⁢   u     ≧   1       ,     e   ≧   1                   l   =       (       2   m     +   1     )     /     (       2     2     u   -   1         +   1     )         ⁢                           Equation   ⁢           ⁢   7                 E   ⁡     (       C     (   l   )       ,     GF   ⁡     (     2       2   u     ⁢     (       2   ⁢   s     +   1     )         )         )       =     
     ⁢         ⋃     P   ∈   𝒫       ⁢     {           τ     (       j   X     ,     j   Y     ,   0     )       ⁡     (   P   )       ❘     j   X       ,       j   Y     ∈     Z   /   lZ         }       ⁢     
     ⁢           ⋃     {         τ     (       j   X     ,   0   ,   0     )       ⁡     (     1   :     0   :   1       )       ❘       j   X     ∈     Z   /   lZ         }     ⁢     
     ⁢           ⋃     {         τ     (       j   X     ,   0   ,   0     )       ⁡     (     1   :     1   :   0       )       ❘       j   X     ∈     Z   /   lZ         }     ⁢     
     ⁢           ⋃     {         τ     (     0   ,     j   Y     ,   0     )       ⁡     (     0   :     1   :   1       )       ❘       j   Y     ∈     Z   /   lZ         }               Equation   ⁢           ⁢   8               {             τ     (       j   X     ,     j   Y     ,     j   Z       )       (       (       ξ   X     :       ξ   Y     :     ξ   Z         )     :=     (         (     α   s     )       j   X       ⁢       ξ   X     :                             (     α   s     )       j   Y       ⁢       ξ   Y     :         (     α   s     )       j   Z       ⁢     ξ   Z           )               𝒫   =     {       (       ξ     u   0       :         (     ξ   +   1     )       u   0       :   1       )     ❘     ξ   ∈       GF   ⁡     (     2   m     )       ⁢   \   ⁢     GF   ⁡     (   2   )             }                   ⋃     {       (       ξ       u   1     /     u   2         :         (     ξ   +   1     )         u   1     /     u   2         :   1       )     ❘     ξ   ∈       GF   ⁡     (     2     2   ⁢   u       )       ⁢   \   ⁢     GF   ⁡     (     2       2   ⁢   u     -   1       )             }       ,                   u   0     =       2       2   ⁢   u     -   1       +   1       ,       u   2     =     gcd   ⁢     (     l   ,       2     2   ⁢   u       -   1       )         ,         u   1     ⁢   l     ≡       u   2     ⁢           ⁢     (       mod   ⁢           ⁢     2     2   ⁢   u         -   1     )                         Equation   ⁢           ⁢   9             
 
         [0032]     By using the AG codes, the number of bits per symbol in an error-correcting code can be made smaller than when the Reed-Solomon codes are used. As a result, the number of redundant bits can be reduced accordingly. This is because of the following reason. Adding two redundant symbols is always required to enhance a code capable of correcting up to t symbols to the code capable of correcting up to t+1 symbols. The smaller the number of bits per symbol in the error-correcting code, the lower the number of redundant bits to be added is required.  
         [0033]     In the following, the number of redundant bits included in a Reed-Solomon code that can be constructed with 4 Kbytes of one sector and parity bytes for a magnetic disk device will be compared with the number of redundant bits included in the above-described Fermat code example.  
         [0034]     For the Reed-Solomon code, due to its code length restriction, the code entity that is equal to or greater than a GF(2 12 ) must be used. In the case of the code over the GF(2 12 ), it is essential to add 2t 12-bit redundant symbols. Thus, the total number of redundant bits is 2t symbols multiplied by 12 bits, that is, 24t bits.  
         [0035]     On the other hand, for the corresponding data size, the Fermat code that comprises C (11) : X 11 +Y 11 +Z 11 =0 (g=(11−1)(11−2)/2=45) can be used. In this case, it is essential to add 10-bit redundant symbols that are 2t+g=2t+45 in number. Thus, the total number of redundant bits is (2t+45) symbols multiplied by 10 bits, that is, 20t+450 bits. By comparison, it turns out that the 20t+450 redundant bits of the Fermat code are less than the 24t redundant bits of the Reed-Solomon code when t≧113.  
         [0036]     By comparison on the condition that error correction coding is performed to allow for correcting random errors in, for example, up to 240 symbols, 5760 redundant bits are included in the Reed-Solomon code and 5250 redundant bits are included in the Fermat code. The number of redundant bits in the Fermat code can be reduced by 510 bits less than that in the Reed-Solomon code.  
         [0037]     If the number of redundant bits is fixed to, for example, 5760 (so the Reed-Solomon code over the GF(2 12 ) can correct random errors in up to 240 symbols), the Fermat code over the GF(2 10 ) can correct random errors in up to 265 symbols, because 20×265+450&lt;5760&lt;20×266+450. Hence, in this case, by calculation, the number of random errors that are permissible in one sector can be increased by 10% or more.  
         [0038]     The present invention aims to improve the efficiency of error correction with redundant bits and the invention reduces the number of bits per symbol for symbols constituting an error-correcting code and, consequently, can achieve a reduced number of redundant bits in the code less than those bits in conventional Reed-Solomon codes. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0039]      FIG. 1  is a schematic showing an example of a magnetic disk device according to an embodiment of the present invention;  
         [0040]      FIG. 2  is a schematic of a conventional magnetic disk device;  
         [0041]      FIG. 3  is a schematic diagram of a Fermat encoder circuit;  
         [0042]      FIG. 4  is a schematic diagram showing a configuration example of a circuit to generate rational points falling in Group A;  
         [0043]      FIG. 5  is a schematic diagram showing a configuration example of a circuit to generate rational points falling in Group B;  
         [0044]      FIG. 6  is a schematic diagram showing a configuration example of a circuit to generate rational points falling in Group C;  
         [0045]      FIG. 7  is a flowchart describing a procedure of error detection and correction by a Fermat decoder circuit;  
         [0046]      FIG. 8  is a schematic diagram of a syndrome calculation circuit in the Fermat decoder circuit.  
         [0047]      FIG. 9  is a flowchart explaining the details of a polynomial calculation step for locating an error by the Fermat decoder circuit;  
         [0048]      FIG. 10  is a diagram showing the order of symbols including Reed-Solomon parity bytes recorded in a sector and associated RS code structures; and  
         [0049]      FIG. 11  is a diagram showing relationship among the Reed-Solomon codes, algebraic geometric codes, elliptic codes, and Fermat codes.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0050]     An embodiment of the present invention will be described hereinafter with reference to the accompanying drawings. In the following drawings, similar functional parts are assigned the same reference numbers for easily understandable explanation.  
         [0051]      FIG. 2  is a schematic of a conventional magnetic disk device. Input signals per sector  16  are converted into binary data per sector by an interface (I/F)  14 . The binary data per sector  13  is input as is, as a data block, to a hard disk controller (HDC)  9 . The binary data per sector  13  input to the hard disk controller  9  is separated into three data blocks by an interleaver (ITLV-3)  11  and each data block is encoded into an error-correcting code by a Reed-Solomon encoder circuit (RS-ENC)  6 . The error-correcting code corresponding to each data block  8  is converted into analog signals  2  to be recorded on a medium by a signal processing LSI (R/W &amp; SPC)  3  and the analog signals are sent to a head. The signals are recorded on a magnetic disk, the recording medium.  
         [0052]     On the other hand, signals  1  read by the head undergo signal processing such as equalization and Viterbi decoding by the signal processing LSI  3 . After discrimination between 0s and 1s, the signals are converted into binary data. The converted binary data  7  enters the hard disk controller  9  and errors in the binary data are detected and corrected by a Reed-Solomon decoder circuit (RS-DEC)  5  in the controller. Three codeword blocks decoded by the decoder circuit  5  are combined into a codeword block by a deinterleaver (DITLV-3)  10 . The decoded binary data is converted into signals  15  to be output by the I/F  14 .  
         [0053]     Although a Reed-Solomon encoding/decoding LSI into which the RS-DEC  5  and the RS-ENC  6  are integrated on one chip is adopted in this example, these circuits may be provided as separate entities without being integrated on the one chip.  
         [0054]      FIG. 1  is a schematic showing an example of a magnetic disk device according to an embodiment of the present invention. The input signals per sector  16  consisting of 4 Kbytes (corresponding to 3277 10-bit symbols) are analog-to-digital converted into binary data per sector by the interface (I/F)  14  which is a means for analog-to-digital conversion (A/D conversion). The binary data per sector is encoded as is, as a data block, into an error-correcting code by a Fermat encoder circuit  102  which is an encoding means. The error-correcting code of the data block  8  is converted into analog signals  2  to be recorded on a medium by the signal processing LSI (R/W &amp; SPC)  3  and the analog signals are sent to the head. The signals are recorded on a magnetic disk, the recording medium.  
         [0055]     On the other hand, the signals  1  read by the head undergo signal processing such as equalization and Viterbi decoding by the signal processing LSI  3 . After discrimination between 0s and 1s, the signals are converted into binary data. The converted binary data  7  enters the hard disk controller  9  and errors in the binary data encoded in the error-correcting code are detected and corrected by a Fermat decoder circuit  101  in the controller. The decoded binary data is converted into signals  15  to be output by the I/F  14 .  
         [0056]      FIG. 3  is a schematic diagram of the Fermat encoder circuit (AG-ENC)  102 . This encoder configuration is an improved and extended version of an elliptic encoder described in the patent document 1.  
         [0057]     A sequence of input symbols b (1) , b (2) , . . . , b (k)  (k=3277 in this example) is input through an input terminal  304 . A rational point generator  301  outputs a point P (j)  at timing when b (j)  is input. When receiving the input of the point, a vector generator circuit  302  outputs a vector v (j) . When receiving the inputs of the vector v (j)  and the symbol b (j) , a scalar multiplier  303  outputs b (j) v (j)  which is in turn added to and stored into a memory  305  for storing syndrome data and, at the same time, the b (j)  passes through a selector  307 . After completing processing on the k symbols, a matrix arithmetic circuit  306  receives the inputs of addition results and outputs vectors MV. The selector  307  selects and outputs the contents of the vectors MV in order from the top.  
         [0058]     To the inputs P (j) =(α j , β j , 1), the vector generator circuit  302  outputs [v 0 (P (j) ), v 1 (P (j) ), v 2 (P (j) ), . . . , v n−k−1 (P (j) )] which are obtained by equation 10, based on (m, L)=(5, 11) and derived from equation 6.  
                   {               υ   0     ⁡     (     P     (   j   )       )       =   1                                 υ   1     ⁡     (     P     (   j   )       )       =       α   j         β   j     +     γ   j           ,         υ   2     ⁡     (     P     (   j   )       )       =       β   j         β   j     +     γ   j                                       υ         1   2     ⁢     s   ⁡     (     s   +   1     )         +   λ       ⁡     (     P     (   j   )       )       =         (       α   j         β   j     +     γ   j         )     λ     ⁢       (       β   j         β   j     +     γ   j         )       s   -   λ                 (       2   ≦   s   ≦   9     ,     0   ≦   λ   ≦   s       )                     υ   λ     ⁡     (     P     (   j   )       )       =       α   j         β   j     +     γ   j           ,     ×       υ     j   -   10       (   j   )       ⁡     (     P     (   j   )       )                   (     55   ≦   λ   ≦     r   -   1       )     ⁢                             Equation   ⁢           ⁢   10     ⁢                       
 
         [0059]     According to equation 2, a j-th column in a check matrix H from the outputs of the vector generator circuit  302  is located. The matrix arithmetic circuit  306  generates an (n−k)-order square matrix where M satisfies equation 4 when r=n−k.  
         [0060]     In the following, the points corresponding to the symbols in the 1st, 2nd, . . . , 3904th positions relative to the reference position for counting the symbols will be denoted as P (1) , P (2) , . . . , P (3904) .  
         [0061]      FIGS. 4, 5 , and  6  are schematic diagrams of the portions of the rational point generator  301  to generate the points belonging to E(C (L) , GF(2 2m )) which are numbered P (1) , P (2) , . . . , P (3904)  in order as defined in equation 11, whereas τ* (j)  and σ (j)  are defined in equations 12 and 13, respectively.  
             {             P     (   j   )       :=       σ     (       (     j   -   1     )     ⁢   mod   ⁢           ⁢   3     )       ⁡     (         (     α   93     )     j     :     0   :   1       )                     (       j   =   1     ,   2   ,   3   ,   …   ⁢           ,   32     )     ⁢     :     ⁢           ⁢   Group   ⁢           ⁢   A                 P     (     33   +   j     )       :=       τ     (   j   )     *     ⁢       °σ     (     2   ×     (     j   ⁢           ⁢   mod   ⁢           ⁢   2     )       )       ⁡     (       α   341     :       α   682     :   1       )                       (       j   =   0     ,   1   ,   2   ,   …   ⁢           ,       2   ×     11   2       -   1       )     ⁢     :     ⁢           ⁢   Group   ⁢           ⁢   B                 P     (     275   +   j     )       :=       τ     (   j   )     *     ⁡     (         (     α     33   ×     3     j   +   1           )     3     :         (       α     33   ×     3     j   +   1           +   1     )     3     :   1       )                     (       j   =   0     ,   1   ,   2   ,   …   ⁢           ,       30   ×     11   2       -   1       )     ⁢     :     ⁢           ⁢   Group   ⁢           ⁢   C                   Equation   ⁢           ⁢   11                 τ     (   j   )     *     :=     τ     (       ⌊     j   /   l     ⌋     ,     j   ⁢           ⁢   mod1     ,   0     )               Equation   ⁢           ⁢   12               {               σ     (   0   )       :=     Id   .           ⁢     (     identity   ⁢           ⁢   map     )         ⁢                           σ     (   1   )       ⁡     (       ξ   X     :       ξ   Y     :     ξ   Z         )       :=     (       ξ   X     :       ξ   Z     :     ξ   Y         )                     σ     (   2   )       ⁡     (       ξ   X     :       ξ   Y     :     ξ   Z         )       :=     (       ξ   Y     :       ξ   X     :     ξ   Y         )                     Equation   ⁢           ⁢   13               
         [0062]      FIG. 4  is the schematic diagram of a circuit to generate the points P (1) , P (2) , . . . , P (32)  in order, labeled “Group A” in the equation 11. Reference numeral  401  denotes a memory to store one coordinate value of P (j)  and its initial value is α 93 . When calculating the coordinates of P (j) , (α 93 ) j  is output from the memory  401  and goes into two branches. One branch further diverges into branches to the inputs of a selector  402 . The inputs to the selector  402  are ((α 93 ) j , 0, 1)=σ (0) ((α 93 ) j , 0, 1), ((α 93 ) j , 1, 0)=σ (1) ((α 93 ) j , 0, 1), and (0, (α 93 ) j , 1)=σ (2)  ((α 93 ) i , 0, 1) from the top of the drawing. The selector  402  selects σ ((j−1) mod 3) ((α 93 ) j , 0, 1), one of the three inputs, as an output. (α 93 ) j  on the other branch is multiplied by α 93  and stored into the memory  401 .  
         [0063]      FIG. 5  is the schematic diagram of a circuit to generate the points P (33) , P (34) , . . . , P (274)  in order, labeled “Group B” in the equation 11. Reference numerals  501  and  502  denote memories to store P (j)  coordinate components before being multiplied by a constant factor of τ* (j)  and their initial values are α 341  and α 682 , respectively. When calculating the coordinates of P (j+33) , a couple of (α 341 , α 682 ) or a couple of (α 682 , α 341 ) are output from the memories  501  and  502  and go into branches, respectively. The couple of the values on one branch are multiplied by the constant factor of τ* (j)  and, on the other branch, the output of the memory  501  is stored into the memory  502  and the output of the memory  502  is stored into the memory  501 . Reference numerals  504  and  505  are memories to store constants assigned for τ* (j)  by which the coordinate values are to be multiplied. The output of the memory  504  goes into two branches, the value on one branch and the output of the memory  501  are multiplied, and the value on the other branch is multiplied by α 93  and stored into the memory  504 . The output of the memory  505  goes into two branches, the value on one branch and the output of the memory  502  are multiplied, and the value on the other branch is multiplied by a constant (1 or α 93 ) selected by a selector  508  and stored into the memory  505 . An undecimal counter  506  is cleared to 0 once every 11 counts. According to a signal  507  output when the undecimal counter  506  is cleared to 0, the selector  508  selects a constant of α 93  when the counter value is 0; otherwise, it selects a constant of 1.  
         [0064]      FIG. 6  is the schematic diagram of a circuit to generate the points P (275) , P (276) , . . . , P (3904)  in order, labeled “Group C” in the equation 11. Reference numeral  601  denotes a memory t store one of the coordinate components before being multiplied by a constant factor of τ* (j)  and its initial value is α 93 . When calculating the coordinates of P (j+275) , (α 93 ) j  is output from the memory  601  and goes into two branches. The value on one branch is raised to the third power and further goes into branches to be multiplied by the constant factor of τ* (j)  and to be stored into the memory  601 . The value on the other branch, after one is added to it, is raised to the third power and multiplied by the constant factor of τ* (j) . The same arrangement to assign constants to τ* (j)  as described for  FIG. 5  is provided.  
         [0065]     When the numbered points are thus prepared, a matrix M in the matrix arithmetic circuit  306  is a given value, namely, an encoding parameter if the numbered P (1) , P (2) , . . . , P (3904)  have been determined. By calculating the matrix M from the equations 2, 4, and 6 by an arithmetic unit or the like beforehand, the encoder can be configured.  
         [0066]     An example of error detection and correction with the above Fermat code will be described below.  FIG. 7  is a flowchart describing a procedure of error detection and correction with the Fermat code. Through a syndrome calculation step  701  for calculating a syndrome that is a set of checksums that become 0 for error-free bit streams from the inputs, an error syndrome s 0 , s 1 , s 2 , . . . , s n−k−1  is calculated. Next, through a polynomial calculation step  702 , error location polynomials f 1 (P), f 2 (P), . . . , f 10 (P) are calculated from the error syndrome. Next, an error is located through Chien search and the value of the located error is determined. This procedure corresponds to a process block  703  in  FIG. 7 .  
         [0067]      FIG. 8  is a schematic diagram of an error syndrome calculation circuit  701 . A sequence of input symbols z (1) , z (2) , . . . , z (n)  (n=3904 in this example) is input through an input terminal  801 . The rational point generator  301  outputs a point P (j)  at timing when z (j)  is input. When receiving the input of the point P (j) , the vector generator circuit  302  outputs a vector v (j) . When receiving the inputs of the vector v (j) and the symbol z   (j) , the scalar multiplier  303  outputs b (j) v (j)  which is in turn added to and stored into a memory  802  for storing syndrome data. After completing processing on the n symbols, the result is output as the error syndrome s 0 , s 1 , s 2 , . . . , s n−k−1 .  
         [0068]      FIG. 9  is a flowchart explaining the details of the polynomial calculation step  702  for locating an error. This flowchart is an example of application of an algorithm called Berlekamp-Massey-Sakara (refer to the non-patent documents 3 and 4) to the Fermat code.  
         [0069]     Equation 14 represents an example algorithm for calculation of error value e (j) . Error value calculation can be executed by using a generalized Forney formula as well (refer to the non-patent document 5).  
                   e     (   λ   )       =       ∑     i   =   0         2     2   m       -   2       ⁢       ∑     j   =   0         2     2   m       -   2       ⁢       S     i   ,   j       ⁢       x   ⁡     (     P     (   λ   )       )         -   i       ⁢       y   ⁡     (     P     (   λ   )       )         -   j               ,           ⁢   where     ⁢     
     ⁢       S       i   0     ,     j   0         :=       ∑     i   =   1     n     ⁢       e     (   i   )       ⁢       x   ⁡     (     P     (   i   )       )         i   0       ⁢       y   ⁡     (     P     (   i   )       )         j   0                     Equation   ⁢           ⁢   14             
 
         [0070]     It is to be understood that the above description is intended to be illustrative and not restrictive. Many embodiments will be apparent to those of skill in the art upon reviewing the above description. The scope of the invention should, therefore, be determined not with reference to the above description, but instead should be determined with reference to the appended claims alone with their full scope of equivalents.