JPH01264316A - Encoder/decoder and encoding method for reed-solomon code - Google Patents

Abstract

PURPOSE:To make software unnecessary and to improve error correction capacity and reliability without increasing a quantity of hardware by using a serial feedback shift register (division circuit) of (m) bits whose generating function is specified. CONSTITUTION:In the title device, the serial feedback shift register (division circuit) of (m) bits whose generating function is expressed in equation is used. The output of an exclusive OR gate group 12 is inputted also to a feedback factor generation circuit 13, and feedback patterns to terms (2nd-order and 4th-order terms) whose factor of G(x) are (beta) are generated at the circuit, and become the input of exclusive OR gate groups 8 and 10. A feedback shift register shifted by one stage when a clock signal is sent to all of the flip-flops in flip-flop groups (1-6) simultaneously as receiving feedback by the pattern of the flip-flop group at each stage is constituted. A detection circuit to detect the fact that the output of all of the flip-flops are 0s, and a zero detection circuit to detect the fact that the output of all of the flip-flops in the flip-flop group at a high-order(m-b) stage are 0s at the time of setting the length of an error correctable by the division circuit as (b) symbol are provided.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention relates to an error correction device for a disk, and in particular to a read/write error correction device.
The present invention relates to a decoding method and encoding/decoding device suitable for single burst error correction processing using Solomon codes.

[Conventional technology]

The conventional Read/Nromon code single burst error correction system for magnetic disks is described in "Essentials of Error Correction Coding Technology," edited by Japan Industrial Technology Center, published in March 1986, pp. 151-163, "Error correction method of F6425. ”
and 1F6d20 error correction methods are known. IF
The ``F6425 error correction scheme'' has a shorter applied theta length and lower reliability (false detection rate, error correction rate) than the ``F6425 error correction scheme''. Also, the "F6420 error correction method" handles data in 8-bit units, but "
If you try to expand this to 16-bit units in order to achieve the same performance as the F6425 error correction method, it will require 60 bits.
Performance 11# for KX2 bytes or more: 1-L for table (JM
Is required. Even if the operation 1s- were to be performed by shifting the feedback shift register without using H, U M i , it would be impractical in terms of time.

According to the "F6425 error correction method", to put it simply, encoding and syndrome calculation are performed by using six 16-bit serial feedback shift registers each independently and dividing all of the data interleaved twice. Let's do it. A total of 7 error positions FM and erroneous Shibataan are processed to some extent using the feedback shift register described above to obtain the error pattern and relative positions rtμ1, J+l, and then the absolute position Q of the error is determined using the Chinese remainder theorem. was.

This calculation of the absolute position Q=-326R9a@+326AOti1 is performed by software, or if it is ζC, separate hardware dedicated to the calculation is required.

[The problem that the invention seeks to solve]

The above-mentioned conventional technology is based on error conditions (one symbol error or two symbol errors).
I felt safe using the algorithmic or complex software 9-air, which was able to differentiate between cases (symbol errors or uncorrectable cries) and branch processing in each case.

The purpose of the present invention is to eliminate the complexity of υ correction processing by using a simple algorithm, thereby eliminating the need for shiftware, and without increasing the amount of hardware. It is an object of the present invention to realize an error correction method and apparatus having error correction ability and reliability.

[Means for solving the problem J The above purpose is to convert the generator polynomial into GIXI--rr <X+@'k)
(19)-s 1 ikell, 2, 3, -. This is achieved by using an m-bit serial feedback seat register (divider circuit) on the 1n-11 aik: up (2'').

[Effect]

The primitive light α of the primitive polynomial P+x+ on the Galois field CjFlql has the following properties.

xQ+x-x(xQ-+1) Sound(X-0)(X-a')(X-ga)...(X-αq
-' ) (20) Take one or more of the q factors on the right side of equation (19) to form a polynomial % expression % (21) 10,000, 0 (xl Initial pattern in the division circuit by K,
F, tx+-aJm-'xm-'+ajm-2Xm
-2+-+a 31x+a l, and shifting the division circuit once with the input as 0 corresponds to calculating F, 1xl-x ・F'alx1mod GIx+, so from the initial pattern (q-1
) times.

Fq-11xl-xq-'F, Ix1mod Glxl
= (xq-1-1)・F'slx1mod G(xl+
F, [xl'J@lxl (
22) and returns to the initial pattern.

Therefore, any polynomial Glxl that satisfies equation (21)? The division circuit used as a divisor is a feedback shift register having a period (q-1). Due to the cyclic nature of this feedback shift register, it is possible to extract error patterns and positions of data within (q-1) symbols.

[Example] An example of the present invention is shown in Fig. 1, Fig. 2, and 8g below.
This will be explained with reference to Figure 3.

Figure 1 shows the following Q F < 211! 1 is a block diagram of a Reed-Solomon code encoding/decoding device configured based on the above primitive polynomial P lxl and generator polynomial G(xlK).

PIXI-X"+X"+X"+X+1 (Jlxl-(x+a"3)(xla")(xla-6
)(xl, 376)x(xla)(x+α
] "X'+X'+/X'+X"+7FX"+X+1However,
- is PIX) (D primitive light., , I! 47961 In the figure, 1 to 6 are flip-flop groups of the 1st stage to 6th stage, respectively. 4,5
) A group of exclusive OR gates whose inputs are the outputs of the flip-flops and the feedback pattern, whose output becomes the input of the first stage flip-flop. Reference numeral 12 denotes a group of exclusive OR gates which receives input data such as the output of the fifth stage flip-flop group. The output of the exclusive OR gate 12 is directly converted into a term (with a coefficient of 1) of the generator polynomial GIXI (
This becomes a feedback pattern for the zero-order, first-order, third-order, and fifth-order terms) and is input to the first stage flip-flop group and the exclusive OR gate group 7.9.11. - the output of the exclusive OR gate group 12 is also. Enter the feedback coefficient generation circuit 13 7+% soCte (J lxl O coefficient is 70
A feedback pattern to the term (2'X, j!rK term) is generated and becomes the power of exclusive OR gate group 8.10.

The flip-flop group, the 7-lip 7cr 7#2.3 and the exclusive-OR gate 8ft which are part of the altruistic OR gate group are shown in detail in FIG.

Flip-flop group 2 and flip-flop group 3 each consist of 16 flip-flops throughout the diagram;
The 16 flip-flops are α0, all, 2, respectively.
, . . . , Oh for all 5th place. Thread count pattern of x2 and X term t-, &was for all 16 bits. The exclusive OR gate group 8 consists of 16 exclusive OR gates, and the first position of flip-flop #2 (term of txl:
i-0,1,2,-...,15) output b'i and 71-
The first place of the dopuck coefficient generation circuit 13 (term of ai: i-0
%1.2, . . . , 15) and the output y'+a% is taken and becomes the first input (term of ai) of the flip-flop e3.

Therefore, when a clock signal is sent to each flip-flop in flip-flop group 2 and clip 7a block nt3, an exclusive logic between the 16-bit pattern of the flip-flop group 20 and the 16-bit output pattern of the feedback coefficient generation circuit is applied. The sum is taken, resulting in a new pattern for flip-flop group 3.

Flip-flop groups 1 to 6 and exclusive OR gate groups 7 to 12 in FIG. 1 are all repeats of such 16-bit flip-flops and 16 exclusive OR gates, and are exclusive OR gates. Group 7. q, 11 are the output of the first place (ai term) of the flip-flop group 1.3.5 and the first place (el
Exclusive OR with the output of (iO term) is performed. The exclusive OR gate group 12 performs exclusive OR of the 16-bit output of the flip-flop group 6 and the 712-byte data inputted from the input terminal 16.

As described above, in order to send a clock signal to all the flip-flops in flip-flop groups 1 to 6 at the same time, a feedback shift register is created in which the pattern of the flip-flop group in each stage is shifted one stage higher while receiving feedback. bottomed out. The clock counter 17 increases by +1 every time the feedback shift register shifts once.
Count all.

Next, the feedback coefficient generation circuit 13 will be explained.

When configuring a division circuit using the primitive polynomial (11) and the generator polynomial (21), α of the feedback thread number generation circuit
'(ig=o, 1.2,..., 15) input sound α
4 (i-0゜1.2,..., 15:α1-10ru0)
, the output is 411, then 41 must satisfy the formula 16@ for withdrawal.

(1, -ad,,+d,,+d 1゜+d4+d,
10d, +d0-(3)d: d, 4+d, +d
, 1+d 1゜+d, +d, +d2-(1)d↓-d
,,+d,,+d,-)d,,+d,+d,10d,
-(5)';"ta"
t. +d, +d, +d3+d, +d,
−(6)dS”d,, +d11+d, +d, +d,
+d, +d1+d0 -(7)d; -d,,
+d, +d, +d, +d, +d, +d,
−(8) dλ−d, 10d,. +d, +d, +
d, +d, +d, +d. -(9) rl;
-d, 4+d,, +cl, +d, +d, +d, +d,
+d, -(10)(17,"d,, +
dX, +d,. +d, +d, +d, %+d, +d2+d
0(11)d6 subd ,, +d 11+d , 10d ,
+d 6+d , +d , +d , +d 0-(12)
d, :o”d, 4+d1□+d, o+d8+d, +d,
+d4+d2+d, -(1M)d,',-d
,s+d ,,+d 1□+d ,+d ,10d 7+
d , +d , +d , +d o-(1) dll, Marod
14+d1. +d, +d, +d6+d.
-(15)dI'3-d11S+d14"I
. +d, +cl, +d1+d0
(16) d 14 d11s-f-d 11 +
d 1゜+d a+d 2 +a 1
o 7) d; swmd
l, +a,, +d, +d, +d 2+d o-
<18) However, in equations (3) to (18), + represents the entire exclusive OR.

dll"Is to di(i-0,1,2,...,15
) is the circuit 1. ? 'I! It is realized in a simple manner using XOR gates. For example, dlo (α10 term), d, μ
A circuit for calculating the term α) is shown in FIG.

The data encoding/decoding procedure will be explained below with reference to FIG. and set the correction burst length to 2 symbols.

(The patterns of 11 encoding flip-flop groups 1 to 6 are all initialized to zero, the feedback shift register is shifted once by one clock signal, and data is transferred from input terminal 16 in 2-byte units (-1 symbol). input.

The shift is repeated until the count value of the clock counter reaches the data length [symbol], and then the pattern of 6 symbols (M12 bytes) remaining in the feedback shift register is added to the end of the data as a check symbol.

Till Error Detection (Syndrome Calculation) Similar to the encoding, the feedback shift register is shifted while inputting data from the data input terminal 16. If the error detection circuit detects zero at the end of data input, that is,
If all the contents of the 6-stage flip-flop group are zero, it is determined that there is no error, and the decoding ends. Error detection circuit 1
If 4 does not detect zero, it is determined that the syndrome is non-zero and an error has occurred in the data, and the process moves on to extracting the error position and pattern of tllll+.

11111 If the error position/pattern extraction syndrome is non-zero, first invert the syndrome. That is,
The contents of flip-flop group 1 and flip-flop group 6 are exchanged, the contents of flip-flop group 2 and flip-flop group 5 are exchanged, and the contents of flip-flop group 3 and flip-flop group 4 are exchanged. means not shown). In this case, the first place (i-0, 1, 2,
..., swap the contents of 15). Thereafter, while the input data from the data input terminal 16 is set to zero, the clock counter 17 continues until the zero detection circuit 15 detects zero, that is, until the contents of the upper four stages of flip-flops become all zero. The feedback shift register is repeatedly shifted while counting the number of shifts.

If the zero detection circuit 15 detects zero after the number of shifts equal to or less than the data length [symbol], it is determined that there is a single burst error within 2 symbols in the data, and in this case, the flip-flop group of the lower two stages An error pattern is obtained by reversing the contents of (the contents of flip-flop group 1 and flip-flop group 2 are swapped),
The counted number of shifts is taken as the position of the first symbol of the error pattern counted from the end of the data, that is, the error position.

If the zero detection circuit 15 does not detect zero even after shifting by more than the data length [symbol], it is determined that an uncorrectable error exists.

According to this embodiment, the same effect (reliability and correction ability) as the conventional error correction effect can be achieved without using software for algebraic calculations or a 几01VI table for calculations, while almost increasing the hardware f. Any single burst error of 17 bits or less can be corrected.

When extracting the v4 position/pattern, the syndrome pattern is inverted and then shifted, so there is no need to search for errors from the end of the data, and the number of shifts required for extraction is at most the data length (symbol).

In addition, since a symmetric expression is used as the generator polynomial, there is no need to change the feedback position and coefficients when proceeding to error extraction after syndrome calculation, and x, x%x, x, x
Since the coefficient of the term x is 1, and the coefficient of the term x is β, only one type of feedback coefficient generation circuit is required, which saves the amount of hardware.

〔Effect of the invention〕

According to the invention, an encoding/decoding device having the following features and effects is realized.

In other words, the same effect (reliability/correction ability) as the conventional error correction effect can be achieved without using software or ROM table for counting W (error position/pattern calculation).
Any single burst error of less than b symbols can be corrected without increasing the amount of hardware. Furthermore, conventional decoding methods generally require data interleaving b times to correct errors in b symbols, but this processing is not necessary.

Further, since the number of types of feedback coefficient generation circuits is generally less than one type, the amount of noise can be reduced.

Furthermore, when extracting the error position/pattern, the syndrome pattern is inverted and then shifted, so the number of shifts required for extraction can be up to the data length (symbol), and the shift is performed in units of n bits. Therefore, the time required to perform error detection is less than one time required to calculate the syndrome of one sector data.

Furthermore, when moving on to error extraction after syndrome calculation,
There is no need to change the feedback position and coefficient.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of an encoding/decoding device according to an embodiment of the present invention, and FIG. 2g2 is a partially detailed diagram of a group of flip-flops and a group of exclusive OR gates in FIG. Figure 8g3 is a partially detailed diagram of the feedback coefficient generation circuit in Figure @1. 1-6... Flip-flop group, 7-12... Exclusive OR gate group, 13... Feedback coefficient generation circuit, 14... Error detection circuit, 15... Zero detection circuit, 16. ...Data input terminal, 17...Clock counter.

Claims (1)

[Claims] 1, 1, primitive elements α and α^ of Galois field GF(2^n)
2, n representing each position of α^3, ..., α^n^-^1
Flip-flop group (
(referred to as one symbol) and m or less feedback coefficient generation circuits that generate feedback patterns to each flip-flop group based on the output values of the n flip-flops of the m-th stage flip-flop group; xn exclusive OR means and a clock count means for counting inputs of flip-flops, and the kth stage (k=
1, 2, ..., m) the jth position (j
=1, 2, . . . , n) and the output of the corresponding feedback coefficient generation circuit are input to one of the exclusive OR means, and the output of the exclusive OR means is j-th flip-flop group of k+1 stage
The output of the exclusive OR means, which inputs the output of each flip-flop of the m-th stage flip-flop group and n-bit input data, is input to each of the feedback coefficient generation circuits. , all of the flip-flops input and output using the same clock signal, and in a division circuit that divides by an m-th degree polynomial ▲ mathematical formulas, chemical formulas, tables, etc. ▼ or an encoding circuit that uses a generator polynomial, an error detection circuit that detects that the output is zero, and all flip-flops of the flip-flop group in the upper (m-b) stage when the length of the error that can be corrected by the division circuit is set to b symbols. A lead/lead device characterized in that it is equipped with a zero detection circuit that detects that the output of the lead is zero.
Solomon code encoding/decoding device. 2.i) If the degree of the generator polynomial is an even number, ▲There are mathematical formulas, chemical formulas, tables, etc.▼-(1) ii) If the degree of the generator polynomial is an odd number, ▲There are mathematical formulas, chemical formulas, tables, etc.▼ -(2) By using a generating polynomial of the form, the output pattern of one feedback coefficient circuit contributes to the input of the flip-flop group in the i-th stage from the top and the flip-flop group in the i-th stage from the bottom. Claim 1 characterized by
The Reed-Solomon code encoding/decoding device described above. 3. When C_m=C_o with respect to the generator polynomial G(x), the contents of the j-th flip-flop of the k-th flip-flop group from the lowest and the contents of the j-th flip-flop of the k-th flip-flop group from the high means for exchanging the contents of the j-th flip-flop and the output of the feedback coefficient generation circuit that corresponded to the k-th flip-flop group at the time of encoding and syndrome calculation
3. The Reed-Solomon code encoding/decoding apparatus according to claim 2, further comprising means for switching to correspond to the group of flip-flops in the -k+1)th stage. 4. When C_m≠C_o with respect to the generator polynomial G(x), the content of the j-th flip-flop of the k-th flip-flop group from the lowest and the content of the flip-flop of the k-th flip-flop group from the high-order A means for exchanging the contents of the j-th flip-flop, an inverse polynomial of the generator polynomial ▲ There are mathematical formulas, chemical formulas, tables, etc. 2. The Reed-Solomon system according to claim 1, further comprising means for separating the feedback coefficient generation circuit based on the inverse polynomial G'(x) and connecting the feedback coefficient generation circuit based on the inverse polynomial G'(x) instead. Code encoding/decoding device. 5. The j-th flip-flop group of the k-th stage from the bottom
3. The Reed-Solomon code encoding system according to claim 2, further comprising means for exchanging the contents of the first flip-flop and the contents of the jth flip-flop of the kth flip-flop group from the top. decoding device. 6. As a result of inputting the data and calculating the syndrome, the error detection circuit (i) determines that there is no error if it detects zero; (ii) if it does not detect it, resets the clock counting means and While counting the clock count means until the detection circuit detects zero, the encoding and
By repeating the shifting of the decoding circuit, the contents of the flip-flops of the first stage to the mth stage when the zero detection circuit detects zero are set as an error pattern, and for the count l of the clock counting means at this time. The error position is the l+1st symbol (~l+m symbol) counting from the beginning of the data, and (iii) when the error detection circuit does not detect zero even after shifting by the number of cycles of the encoding/decoding device. 3. The decoding method of the Reed-Solomon code encoding/decoding apparatus according to claim 2, wherein it is determined that an uncorrectable error exists. 7. As a result of inputting the data and calculating the syndrome, the error detection circuit (i) determines that there is no error if it detects zero; (ii) if it does not detect zero, the error detection circuit determines that there is no error; The contents of the j-th flip-flop of the flip-flop group and the j-th flip-flop of the k-th flip-flop group from the top are exchanged, and the feedback corresponding to the k-th flip-flop group is changed. After switching the output of the coefficient generation circuit to correspond to the m-k+1 flip-flop group, the clock counting means is reset, and the clock counting means counts until the zero detection circuit detects zero. while repeating the shift of the encoding/decoding device, and when the zero detection circuit detects zero, the contents of the result of changing the order of the flip-flop groups from the first stage to the b-th stage are used as an error pattern, and at this time, The count of the clock counting means is the position of the first symbol of the error pattern counted from the end of the data, and (iii) if the error detection circuit does not detect zero even after shifting by the number of symbols of the data, 4. The decoding method of a Reed-Solomon code encoding/decoding apparatus according to claim 3, wherein it is determined that an uncorrectable error exists. 8. As a result of inputting the data and calculating the syndrome, the error detection circuit determines that (i) if zero is detected, there is no error, (ii) if zero is not detected, the kth stage from the lowest swapping the contents of the j-th flip-flop of the flip-flop group with the contents of the j-th flip-flop of the k-th flip-flop group from the top, and disconnecting the feedback coefficient generation circuit based on the generator polynomial G(x). , Instead, after connecting the feedback coefficient generation circuit based on the inverse polynomial G'(x), the clock counting means is reset, and the clock counting means is counted until the zero detection circuit detects zero. The encoder/decoder repeats the shift, and when the zero detection circuit detects zero, the order of the flip-flop groups from the first stage to the b stage is changed, and the result is defined as an error pattern, and the count l is used as the data. (iii) If the error detection circuit does not detect zero even after shifting by the number of data symbols, it is determined that an uncorrectable error exists. 5. A decoding method using a Reed-Solomon code encoding/decoding apparatus according to claim 4. 9. As a result of inputting the data and calculating the syndrome, the error detection circuit determines that (i) if zero is detected, there is no error, (ii) if zero is not detected, the kth stage from the lowest After exchanging the contents of the j-th flip-flop of the flip-flop group with the contents of the j-th flip-flop of the k-th flip-flop group from the top, the clock counting means is reset, and the zero detection The circuit repeats shifting of the encoding/decoding device while counting the clock count means until the circuit detects zero, and when the zero detecting circuit detects zero, the flip-flop groups from the first stage to the bth stage are The content of the result of rearranging the order is an error pattern, the count l is the position of the first symbol of the error pattern counted from the end of the data, and (iii) even if the shift is performed by the number of symbols in the data, the error detection circuit is zero. 6. The decoding method of a Reed-Solomon code encoding/decoding apparatus according to claim 5, further comprising determining that an uncorrectable error exists if the error is not detected.