JP2725551B2 - Error correction code decoding method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for decoding an error correcting code for improving the reliability of digital communication and a memory.

[0002]

2. Description of the Related Art A decoding method related to an error correction coding method based on an algebraic curve having a code length n, the number of information symbols k, and a design distance d includes a basic decoding method / correction decoding method (document: Scolobogatob, Bradyu [On the Coding of Algebraic Geometric Cause], IEE, Information Theory, No. 5, September, 1
990, A.M. N. Skorobogatov and
Vladut: "On the decoding o
f algebraic geometric cod
es, "IEEE Trans on Information
Tion Theory, no. 5, Septembe
r, 1990), and for a modified decoding method in which an algebraic curve to be a target of code construction is restricted, a two-dimensional Berlekamp-Massie algorithm (Literature: Sakata [Finding Aminimal Set of Linear Recurring Relations Capable of Generation] Rating Aggressive Two-Dimensional Array] Journal of Symbolic Computation, No. 5, 198
8, S.M. Sakata: "Finding a min
imal set of linear recurr
ing relations capable of
generating a given finete
two-dimensional array, "J
ownal of Symbolic Computing
ation, no. 5, 1988) (Literature: Sakata, [On Application of the 2 Diver Recamp Massy Algorithm Toe Decoding Sam Causes Defined on Algebraic Curves], 13th Information Theory and Its Application Symposium, 19
91, S.M. Sakata: "On applicati
on of the 2DBerlekamp-Mas
sey algorithm to decoding
some codes defined on al
Gebraic curves, "), which is a high-speed decoding method (Filing No. 4-46813,
Inventor: Kamiya). The above decoding method cannot generally correct a number of errors up to the error correction capability ((d-1) / 2) that the code originally has. On the other hand, a decoding method using a majority decision procedure as a decoding method capable of correcting errors up to the error correction capability of the code (Fen, Rao [Decoding Algebraic Geometric Cause Up Toe Design Dominant Distance], AI EE, Information Theory, No. 1,
January, 1993, G.A. -L. Feng and T.S.
R. N. Rao: "Decoding algebra
ic geometric codes up to
designedminimum distance
e, “IEEE Trans on Information
ion Theory, no. 1, January, 1
993). FIG. 1 shows a decoding method using the majority decision procedure. It consists of the following steps: First n
A received word consisting of symbols is used as an input symbol sequence.
The corresponding syndrome is derived (step 1-
1). Here, when all the syndromes are zero, the following operation is omitted. A solution of a simultaneous linear equation having a coefficient matrix composed of the syndrome and unknown syndromes described below and a matrix having the results of these linear operations as components is derived (step 1-2). Of the values obtained by the product-sum operation of the solution and the components of the coefficient matrix, the one with the largest number is selected by majority decision and output as an unknown syndrome (step 1-4). This is fed back to the input of the linear equation deriving means (step 1-5). When the number of repetitions exceeds a set value (step 1-3), an error position is determined using the solution of the simultaneous linear equation (step 1-6), and an error pattern is determined based on the determined error position. And performs correction (step 1-7).

[0003]

In the prior art, when an algebraic curve used for error correction coding (code length = n, number of information symbols = k, design distance = d) is limited, decoding is not possible. Although the error position can be derived at high speed, the error cannot be corrected to the error correction capability (t = [(d-1) / 2]) inherent in the code. On the other hand, for a code configured using a general algebraic curve, there is a decoding method using the majority decision procedure as a decoding method capable of performing error correction of the code. There is a problem that calculation of is required. An object of the present invention is to solve such a problem of the prior art when the algebraic curve used in encoding is limited, to derive an error position at high speed, and to correct errors up to the correction capability of the code. An object of the present invention is to provide a high-speed decoding method capable of performing correction.

[0004]

An error correction code decoding method according to the present invention comprises a code length n (n is a positive integer), the number of information symbols k
(K is a positive integer), a decoding method of an error correction code based on an algebraic curve, wherein a received word consisting of n symbols is input, at least nk syndromes are derived, and the syndrome and the unknown syndrome are input. Deriving a feedback coefficient of the shift register by a method of obtaining a shift register of the minimum number of stages that generates a part of a predetermined partial two-dimensional array having the input or a result of a linear operation of the input as a component, Among the values obtained by the product-sum operation of the partial two-dimensional array and the feedback coefficient, the one with the largest number is output as the unknown syndrome.

[0005]

DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the error correction code decoding method according to the present invention will be described with reference to FIGS. FIG. 2 is a flowchart showing the whole method of the present invention, which comprises the following steps. First, a received word consisting of n symbols is used as an input symbol sequence, and a corresponding syndrome is derived (step 2-1). This is the same as step 1-1 described above. Here, when all the syndromes are zero, the following operation is omitted. The feedback coefficient of the shift register is calculated by a method of obtaining a shift register of the minimum number of stages that generates a part of a predetermined partial two-dimensional array having the syndrome and an unknown syndrome described later and a result of these linear operations as components. It leads (step 2-2). Among the values obtained by the product-sum operation of the feedback coefficient and the components of the two-dimensional array, the one having the largest number is selected by majority decision and output as an unknown syndrome (step 2-4). Is fed back to the input of the simultaneous linear equation (step 2-5). When the number of repetitions exceeds a set value (step 2-3), an error position is determined using the feedback coefficient (step 2-6), and an error pattern is derived and corrected based on the determined error position. (Step 2-
7). Steps 2-6 and 2-7 are the same as steps 1-6 and 1-7 described above.

Hereinafter, step 2-2 which is a feature of the present invention will be described in detail with reference to FIG. First, a point n and initial values of tables S, N, L, D described later, a feedback coefficient table, and an auxiliary coefficient table are set (step 3-1).
At this time, the feedback coefficient table stores the feedback coefficients of a predetermined two-dimensional shift registers, and the table S stores the coordinates of points corresponding to the number of stages of the register. Next, the above-mentioned syndrome and unknown syndrome are input, and a syndrome array described below is generated (step 3-2). It is determined whether or not a number of two-dimensional shift registers having data stored in the feedback coefficient table as a feedback coefficient generate an array at point n (step 3).
-3) Based on the determination information, it is determined whether or not to update the table S for each two-dimensional shift register (step 3-4). Based on the determination information, the table S and the feedback coefficient table are updated using the property 1 described below and the data in the tables N, L, and D (step 3-5) (step 3-7). Based on the newly updated table S and the feedback coefficient table, the contents of the tables N, L, and D are updated or added according to the means described below. If the point n is not the predetermined operation end point, the next point of the n is designated, and the control returns to the step 3-3 (step 3-8). If it is the operation end point, the contents of the feedback coefficient table and the table S are output,
Input to the above-mentioned step 2-4. At this time, the contents of each table and the operating point n are kept stored.

Step 2-4 will be described in detail with reference to FIG. First, input the output of step 2-2,
Initialization such as initializing the table M is performed (step 4-1), the number m when storing the data u described later in the table M is determined, and when the number is not zero, the data u is derived (step 4-1). 4-2). Data u is stored in step 3-2.
, The feedback coefficient which is the input of step 2-4, and the data i representing the number of repetitions of the present means. Next, m data u are stored in the table M (step 4-3). If the end condition set in the initial setting in step 4-1 is not satisfied, the data i is updated (step 4-6). (Step 4-5).

Hereinafter, matters omitted in the above description will be described in detail.

[0009]

(Equation 1)

[0010]

(Equation 2)

[0011]

(Equation 3)

[0012]

(Equation 4)

[0013]

(Equation 5)

[0014]

(Equation 6)

[0015]

(Equation 7)

[0016]

(Equation 8)

[0017]

(Equation 9)

[0018]

(Equation 10)

[0019]

[Equation 11]

G ⁿ of property 1 is called an auxiliary rational function system at point n. The original coefficient data of G ⁿ is the data of the auxiliary coefficient table.

[0021]

(Equation 12)

[0022]

(Equation 13)

[0023]

[Equation 14]

The unknown syndrome deriving means in step 2-4 will be described.

[0025]

(Equation 15)

[0026]

(Equation 16)

[0027]

[Equation 17]

[0028]

According to the conventional decoding method, for example, ya ⁺ y = x
Based on the algebraic curve defined by ^b , errors up to the correction capability [(d-1) / 2] of the error correction code coded at the code length n, the number of information symbols k, and the design distance d are corrected. In such a case, there is a problem in that the number of calculations in proportion to the cube of n is required to derive the error position, or when the derivation of the error position is accelerated, error correction up to the correction capability cannot be performed. However, this problem is solved by using the decoding method of the present invention. In this case, when correcting an error up to the correction capability of the code, the error position is equal to the code length of 2 bits.
The calculation can be performed at high speed with the number of calculations in proportion to the product of the power and a.

[Brief description of the drawings]

FIG. 1 is a flowchart showing one embodiment according to a conventional method.

FIG. 2 is a flowchart showing an embodiment (whole) of an error correction code decoding method according to the present invention;

FIG. 3 is a flowchart showing an embodiment (part) of an error correction code decoding method according to the present invention;

FIG. 4 is a flowchart showing an embodiment (part) of an error correction code decoding method according to the present invention;

Continuation of the front page (56) References JP-A-61-237521 (JP, A) JP-A-5-284404 (JP, A) -L. FENG, T .; R. N. RAO, "DECODING ALGE BRAIC-GEOMETRIC CO DES UP TO THE DESI NGED MINIMUM DISTA NCE," IEEE TRANSACTION ON INFORMATION VOL. IT-39, NO. 1, P. 37-45 A. N. SKOROBOGATOV, ET. AL, "ON THE DECO DING OF ALGEBRAIC-GEOMETRIC CODES," "IEEE TRANSACTIONS ON INFORMATION THEO RY, VOL. IT-36, NO. 5, p. 1051-1060. SAKATA, "FINDING A MINIMAL SET OF LINEAR RECURRING R ELATIONS CAPABLE OF GENERATING A GIV EN FINITE TWO-DIME NATIONAL ARRAY," 321-337 Sakata, "Extension of BERLEKAMP-MAS SSEY algorithm and its significance in coding theory and linear system theory", IEICE Technical Report, July 11, 1992, Vol. 92, NO. 133, IT92-34, P.E. 63-70 Kamiya and Miura, "Application of SAK ATA ALGORITHM to MODIFIED DECODE ING ALGOLITHM on Certain Algebraic Curve Codes", IEICE Technical Report, January 23, 1992, Vol. 91, NO. 435, IT91-96, P.E. 47-55 Kamiya and Miura, "Decoding Algorithm for Codes on ARTIN-SCHR EIER Curve", IEICE Technical Report, March 17, 1993, Vol. 92, NO. 504, IT92-145, P.67-72

Claims (1)

(57) [Claims] 1. A decoding method for an error correction code based on an algebraic curve having a code length n (n is a positive integer) and a number of information symbols k (k is a positive integer), wherein a received word including n symbols is input. Lead at least nk syndromes,
The syndrome and the unknown syndrome are input, and the input or the result of the linear operation of the input is used as a component to determine a shift register of the minimum number of stages that generates a part of a predetermined partial two-dimensional array. Error correction code decoding for deriving a feedback coefficient of a shift register and outputting, as the unknown syndrome, the largest number of values obtained by the product-sum operation of the partial two-dimensional array and the feedback coefficient. Method.