JPH0636286B2 - Error correction method and apparatus - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to error correction in a digital signal reproducing apparatus, and more particularly to an error correcting apparatus suitable when the number of check words is large.

[Background of the Invention]

When transmitting or recording a digital signal, the occurrence of data error in the transmission system poses a problem. Therefore,
A check word is added during transmission or recording, and error correction is performed using the check word during reception or reproduction. A BCH code or the like, which is efficient and easy to decode, is used as the check word. In particular, in the block code, a Reed-Solomon code, which is a kind of BCH code, is often used. Further, there is a cross interleave code as a method in which the correction capability is increased by performing double coding with these codes.

1 and 2 show a coding circuit and a decoding circuit of a cross interleaved Reed-Solomon code (hereinafter abbreviated as CIRC code). In FIG. 1, 1, 2 are encoders, 3,
4,5 are interleave circuits, and 6 is a data inverting circuit. In FIG. 2, 7 and 8 are decoders and 9 and 10 and 11 are deinterleave circuits.

The CIRC code uses the Reed-Solomon code for double coding. In the encoding circuit shown in FIG. 1, the interleaving circuit 3 performs the first interleaving circuit on the information words of 24 words, and then the encoder 1 checks the check words Q ₁ , Q ₂ , Q ₃ , Q _{4 of} 4 words. Is added. Further, the 28-word code block consisting of 24 information words and 4 check words is subjected to the second interleaving by the interleaving circuit 4, and then the encoder 2 is used to check the check words P ₁ , P of 4 words. ₂ , P ₃ , P ₄ are added. The 32 word code block consisting of 24 information words and 8 check words is further transmitted or recorded after the third interleaving is performed by the interleaving circuit 5. The inspection word is inverted by the data inverting circuit 6 in order to prevent erroneous detection or erroneous correction when continuous data is lost.

In the decoding circuit of FIG. 2, the deinterleave circuit 9
After the deinterleaving corresponding to the above 3 interleaving and the inversion of the check word by the data inverting circuit 6 are performed, the first decoding is performed by the decoder 7. In this first decoding, error detection and correction are performed using the check words P _{1 to} P ₄ . 24 information words and 4 which have been subjected to error detection and correction in the decoder 7
The check word of the word is secondly decoded by the decoder 8 after being deinterleaved by the deinterleave circuit 10 corresponding to the second interleave. In this second decoding, the check words Q _{1 to} Q ₄
Error detection and correction are performed. The 24-word information word subjected to error detection and correction by the decoder 8 is output after being deinterleaved corresponding to the first interleave by the deinterleave circuit 11.

In the method of performing double encoding such as the CIRC code, the correction capability can be increased by performing decoding twice or more with two different code blocks. However, in the conventional decoding method, the first decoding and the second decoding are performed.
Since only one word or two words are corrected in the decoding of, it cannot be said that the correction capability of the code is fully utilized.

[Object of the Invention] It is an object of the present invention to provide an error correction system and apparatus which can maximize the error correction capability of a code.

[Outline of Invention]

The present invention uses a decoding method such that 2p + q = d−1 when correcting an error of a p word whose error position is unknown and an error of a q word whose error position is known in a code whose minimum distance is d. By doing so, the error correction capability of the code is maximized.

Example of Invention

Hereinafter, a case where one embodiment of the present invention is applied to the CIRC code described above will be described.

In the decoding of the CIRC code, a Galois field GF (2 with a code length of 32 words and a check word number of 4 words in the first decoding and a code length of 28 words and a check word number of 4 words in the second decoding is used.
⁸ ) It is necessary to decode the above Reed-Solomon code.

First, the Reed-Solomon code defined on the Galois field GF (2 ⁸ ) and its decoding method will be described.

Letting α be one of the roots of the eighth-order irreducible polynomial F (x) on GF (2), it is expressed by the power of α in the element of GF (2) (2 ⁸
-2) A set {0, 1, α, α ² , ..., α
²⁵⁴ } constitutes GF (2 ⁸ ). In GF (2 ⁸ ), when a certain positive integer is t, g (x) = (x + 1) (x + α) (x + α ² ) ... (x +
α ^2t−1 ) or (x + α) (x + α ² ) (x + α ³ ) ... (x + α
A code having a code length n = (2 ⁸ −1), a number of information words (n−2t), and a check word number of 2t with ^2t ) (1) as a generator polynomial is a Reed-Solomon code. That is, the read code word in Solomon code _{C = {C 0, C 1} , ..., C n-1} polynomial representation C of _{(x) = C 0 + C} 1 x + C 2 x 2 + ... + C n-1 x
^n-1 (2) is divisible by g (x). This is expressed as the following equation.

C (x) ≡0 (mod g (x)) (3) The code length n can be shortened within the range of 2 ⁸ −1n> 2t. In this Reed-Solomon code, the minimum distance is (2t + 1).

Here, the received signal for the code word C (x) expressed by the equation (2) is R (x) = γ ₀ + γ ₁ x + ... + γ _n-1 x ^n-1 (4), and the received signal has ν Error of If R occurs, R (x) = C (x) + E (x) ≡ E (x) (mod g (x)) (6) The error E (x) is expressed by the syndrome S _k expressed by the following equation. You can ask.

As the decoding procedure, first, the error position polynomial is calculated from the syndrome S _t. Error position i ₁ ,
i ₂ , ..., i _ν are known. From equation (8), σ (α ^ij ) = 0
_Therefore , e _ij α ^{ij · k} σ (α ^ij ) = 0 When the above equation is added for 0 ≦ k ≦ 2t−1 (or 1 ≦ k ≦ 2t), Siσ _ν + S _{i + 1} σ _{ν − 1} + ... + S _{i + ν −1} σ ₁ + S _{i + ν} = 0 (0 ≦ i ≦ 2t-1-ν or 1 ≦ i ≦ 2t-ν) (9) holds. Σi can be obtained by solving equation (9).
Further, from this error position and the equation (7), the error values ei ₁ , e
If i ₂ , ... E i _ν are calculated and E (x) is calculated, error correction can be performed by C (x) = R (x), E (x) (10).

In the code with the minimum distance d, it is possible to correct p errors whose error positions are unknown and q errors whose error positions are known within the range of 2 _p + q ≦ d−1. In the Reed-Solomon code, since the minimum distance is (2t + 1), error correction can be performed within the range of 2 _p + q ≦ 2t.

Next, at t = 2, the number of information words (n−4), the number of check words, and the generator polynomial are g (x) = (x + 1) (x + α) (x + α ² ) x + α ³ ).
A specific decoding method for the Reed-Solomon code that is (11) is described.

In this case, the syndromes S ₀ , S ₁ , S ₂ and S ₃ are given by the following equations.

If there is no error, obviously S ₀ = S ₁ = S ₂ = S ₃ = 0.

If the error is one word (assuming the error position is i),
From equation (9), Therefore, σ ₁ = S ₁ / S ₀ = S ₂ / S ₁ = S ₃ / S ₂ Also, σ (x) = x + α ⁱ = x + σ ₁ Therefore, α ⁱ = S ₁ / S ₀ (14) i is required.

The error value in this case is ei = S ₀ (15) from the equation (7).

If the error is 2 words (the error positions are i ₁ and i ₂ ), from equation (9) Solving the above equation, Becomes Therefore, the error locator polynomial is Becomes By solving σ (x) = 0 And the error positions i ₁ and i ₂ can be obtained.
Also, from equation (7), Therefore, More incorrect value Can be asked.

Error is 3 words (Error position is i ₁ , i ₂ , i ₃ )
In this case, S ₀ σ ₃ + S ₁ σ ₂ + S ₂ σ ₁ + S ₃ = 0 (20) Than Therefore, if the error positions i ₁ and i ₂ are known,
From equations (20) and (22) However, The third error position i ₃ can be obtained by
Also, from equation (7) Therefore, However, More incorrect value Can be asked.

If the error is 4 words (error positions are i ₁ , i ₂ , i ₃ , and i ₄ ), from equation (7) Therefore, if the error positions i _{1 to} i ₄ are known, However, As described above, as a method of decoding a Reed-Solomon code having four check words, an error of not more than two unknown error positions is corrected. Corrects an unknown error position,
3 to correct less than 4 known errors
There are different ways. By combining and using these decoding methods, efficient error correction can be performed.

In the CIRC code, the number of check words is 4 and the minimum distance is 5. Therefore, as described above, it is possible to correct the error of the p word whose error position is unknown and the error of the q word whose error position is known within the range of 2p + q ≦ 4.

In the first decoding, the error position is unknown. Therefore, q = 0, p = 1 or 2, and an error of up to 2 words can be corrected. That is, in the first decoding, there are four types of cases, that is, it is determined that there is no error, that one-word correction is performed, that two-word correction is performed, and that there is an error of three words or more and it is uncorrectable. Conceivable. Therefore, consider the following as a flag indicating the first decoding state.

In the first decoding, such a flag is added to each word simultaneously with error correction. The reason for adding a plurality of flags in this way is that the probability of erroneous detection and erroneous correction that occurs when decoding is different in each case. The probability of false detection and correction increases as the correction capability increases. If this probability is p (Fi), then P (F ₀ ) <P (F ₁ ) <(F ₂ ). Therefore, by adding flags indicating a plurality of states in the first decoding, it is possible to perform error correction in the second decoding, which is excellent in both correction capability and detection capability.

In the second decoding, the error position can be detected by the flag added in the first decoding. Therefore, There are three possible correction methods.

If p = 0 and q ≦ 4, the flag is added to 4
Errors up to a word can be corrected. Although the method has the highest correction capability, if there is an error in the correction block in which a flag is not added due to erroneous detection or erroneous correction in the first decoding, erroneous correction results. Therefore, it is necessary to use a flag such as F ₀ or F ₁ that has a low probability of false detection and correction as an error flag. If the number of corrected words is less than 3, the detection capability can be improved by the syndrome check.

When p = 1 and q ≦ 2, 2 with a flag added
It is possible to correct an error of up to 3 words and an error of up to 3 words of any one word. In this case, it is possible to correct an error of one word to which no flag is added. Further, when there are 3 words (or 3 words or less) to which the flag is added, 2 words (or 1 word) of them are regarded as an erroneous error whose error position is known, and the error position of the remaining 1 word is determined. If a method of detecting and checking whether the result matches the position of the flag is used, the detection capability can be enhanced.

In the case of p = 2 and q = 0, it is possible to correct an error of up to two arbitrary words. In this case, up to 2 words can be corrected even if there is an error in which no flag is added. Further, if it is checked whether or not the detected error position matches the position of the flag, the detection capability can be improved.

Specific application examples of the three types of decoding methods in the second decoding C ₂ will be described with reference to the flowchart shown in FIG.

(1) When the number of F ₀ flags is 4 or less, the word to which the flag is added is regarded as an error word and error correction of 4 words or less is performed. (2) If the number of F ₀ flags is 5 or more, F
_When the number of ₁ flags is 3 or less, the error position of 1 word is detected with 2 words (or 1 word) added with the F ₁ flag as an error word, and the detected error position is regarded as the flag position. When they match or when there is no error, error correction of 3 words or less is performed. The word to which the F ₂ flag is added is prioritized as the error word to be determined first.

(3) When the number of F ₁ flags is 5 or more and the number of F ₁ flags is 4 or more, the error position detection up to 2 words is performed, and the F ₁ flag is added to the detected error position. In this case, error correction of 2 words or less is performed.

In the cases of (4) and (3), the error detection capability can be enhanced by making a more detailed judgment depending on the state of the F ₂ flag.

As described above, according to the decoding method of the present invention, it is possible to correct an error of up to 3 words or 4 words, and to improve the correction capability as compared with the conventional method of correcting an error of up to 2 words. You can In addition, the error detection capability can be enhanced by using the optimum decoding method according to the state of the flag.

In addition, the error correction method of the present invention is applicable to decoding other than CIRC code, for example, when a cyclic code (CRC code) is used to generate the second check word and only error detection is performed in the first decoding. Applicable.

Next, an embodiment applied to the CIRC code of the error correction device of the present invention will be described.

FIG. 4 is a block diagram of the error correction device. In the figure, 17 to 19 are bus lines, 20 is a syndrome generation circuit, 21, 22 ROM, 25, 27 and 29 are RAMs, 24 is an arithmetic circuit, 26 is a counter, 28 is a comparison circuit, 30 is a condition judgment circuit, 31 Is a program ROM, and 32 is an address counter.

This circuit is composed of three bus lines, a circuit connected to the bus lines, and a control circuit for controlling the operation of each circuit by a program.
The bus line 17 is a data bus for exchanging data such as a received signal and an error pattern, the bus line 18 is a location bus for exchanging data such as a data position, and the bus line 19 is data for a flag added to the data. It is a flag bus that exchanges. A data input / output terminal 12, a location input / output terminal 13, and a flag input / output terminal 14 are connected to each bus.

The syndrome generation circuit 20 generates syndromes S _{0 to} S _{3 according} to the received signal input from the data input / output terminal 12. The syndrome generation circuit 20 is composed of a circuit as shown in FIG. In FIG. 5, 42 is an EOR circuit, 44
Is an 8-bit latch. Further, 43 is a matrix operation circuit, "1" in _{S 0} generation circuit, the _{S 1} generation circuit "alpha", _{S 2} in generation circuit "alpha ^2", _{S 3} at generating circuit "alpha ^3" and the input signal Output the product of and. FIG. 4 shows an example of the S ₁ generation circuit. Input terminal to this circuit
Input the received signal to 38 and clock input terminal 40 of latch 44.
By inputting the clock signal synchronized with the received signal, the syndrome is output to the output terminal 39 when the input of the received signal is completed. The clear signal input terminal 41
Is for clearing the latch before performing the syndrome generation.

The arithmetic circuit 24 performs an arithmetic operation for obtaining an error position and an error pattern by the syndromes S _{0 to} S ₃ generated by the syndrome generating circuit. The arithmetic circuit performs multiplication, division and addition on GF (2 ⁸ ).
The multiplication and division of X (= α ^x ) and Y (= α ^y ) on GF (2 ⁸ ) are as follows.

FIG. 6 shows a multiplication / division circuit. Reference numerals 48 and 49 are ROMs which respectively output x and y for X and Y input to the input terminals 45 and 46. Reference numeral 50 is an addition / subtraction circuit, which performs addition in the case of multiplication and subtraction in the case of division. 51 is RO
M, and for the output x ± y of the adder / subtractor circuit 50, α
^It outputs ^{x ± y} to the output terminal 47. For addition in GF (2 ⁸ ), as shown in FIG. 7, mod 2 may be added in each bit.

The RAM 25 is for storing the syndromes S _{0 to} S ₃ and the calculation results of the calculation circuit 25. Reference numeral 23 is an 8-input OR circuit for determining whether or not the data on the data bus 17 is "0".

The ROMs 21 and 22 are ROMs for converting i and α ⁱ . When exchanging with an external circuit, the data position is i = 0 to 31, but as described above, when the decoding operation is performed, it is handled in the form of α ⁱ . Therefore, the ROMs 21 and 22 perform conversion between i and α ⁱ . R
The OM21 is a ROM for converting i → α ⁱ , and the ROM 22 is a ROM for converting α ⁱ → i.

The counter 26 counts the number of flags in one block. In the second decoding, the counter 26 uses F ₀ , F ₁ ,
The number of F ₂ is counted, and the number is compared with a predetermined number by the comparison circuit 28 to determine how many words are to be corrected, or whether correction is performed or uncorrectable without correction. .

The ROM 27 is for storing the number of flags, the error position, etc. counted by the counter 26. Also, the comparison circuit
28 is used for comparing the number of flags described above with a predetermined number, and for comparing data with a constant during the decoding process.

The ROM 29 stores flags F _{0 to} F ₂ indicating the result of the first decoding added to the data in the second decoding. The status of the flag stored in the ROM 29 is used to check the presence or absence of the flag at the error position obtained by decoding.

The condition judging circuit 30 judges whether or not to branch the program based on the result judged by the OR circuit 23 or the comparison circuit 28 and the state of the flag stored in the ROM 29.

The program ROM 31 stores a program for controlling each circuit described above to perform decoding. The structure of the program is shown in FIG. 1 word is 32
It consists of bits. 52 selects a register for storing data among the registers in the input section of each circuit. 53
Selects the buffer that outputs data from the buffers in the output section of each circuit. 52 and 53 allow data to be transferred from any circuit to any circuit through a bus line. Reference numeral 54 is for writing data to the ROM 25 or RAM 27. Since the data writing to the RAM 29 is performed only when the reception signal is input, it is not necessary to control it by the program. Reference numeral 55 is for selecting multiplication and division in the arithmetic circuit 24. 33 is RAM
Address and the constants to be input to each bus line and the comparison circuit. 34 is for determining the condition for branching the program.
The contents of 34 are compared with the conditions of the OR circuit 23, the comparison circuit 28, the RAM 29, etc. to decide whether or not to branch. Reference numeral 35 determines the branch destination when branching. In the circuit of the present invention, 40
A CIRC code can be decoded with a program of about 0 words.

The counter 32 controls the address of the program. This counter is the master clock input
The address of the program ROM 31 is advanced by the clock input from 15 to execute the program. When branching the program, the branch instruction 37 loads the branch destination address 35 into the counter to branch the program. The input terminal 16 is for inputting a signal for resetting the counter 32 when the program is started.

As a procedure for error correction, first, the received signal is input, the syndromes S _{0 to} S ₃ are generated, and in the second decoding, the number of flags is counted and the flag state is stored in the RAM 29. Next, decoding is performed by the program, the error position and the error pattern are obtained, and the error data is corrected by the equation (10). Further, when correction is impossible in the first decoding and the second decoding, the flag input / output 14 outputs a flag to be added to the data.

As described above, the error correction device of the present invention uses the method of controlling each circuit by a program, the circuit scale is small, and different decoding methods can be dealt with only by changing the program.

〔The invention's effect〕

According to the present invention, the capacity of a code used for error detection and correction can be maximized, and the error detection capacity and correction capacity can be improved.

[Brief description of drawings]

FIG. 1 is an encoding circuit diagram of a CIRC code, FIG. 2 is a decoding circuit diagram of a CIRC code, FIG. 3 is a schematic flowchart diagram of a second decoding procedure of a CIRC code according to the present invention, and FIG. Block diagram, Fig. 5 is the syndrome generation circuit diagram, and Fig. 6 is the GF.
A multiplication / division circuit diagram on (2 ⁸ ), FIG. 7 is an addition circuit diagram on GF (2 ⁸ ), and FIG. 8 is a configuration diagram of a program. 20 …… Syndrome generation circuit 21, 22 …… ROM 23 …… OR circuit 24 …… Operation circuit 25,27,29 …… RAM 26 …… Counter 28 …… Comparison circuit 30 …… Condition judgment circuit 31 …… Program ROM 32 …… Address counter

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Keiji Noguchi 292 Yoshida-cho, Totsuka-ku, Yokohama-shi, Kanagawa Inside the Home Appliance Research Laboratory, Hitachi, Ltd. (72) Inventor Takao Arai 292 Yoshida-cho, Totsuka-ku, Yokohama-shi, Kanagawa Inside the Hitachi Electric Appliances Research Laboratory (72) Inventor Toshifumi Shibuya 292 Yoshida-cho, Totsuka-ku, Yokohama-shi, Kanagawa Inside the Hitachi Electric Appliances Research Laboratory (56) Reference JP-A-58-29237 (JP, A) Electronic communication Technical Report of the Society, 82 [18]

Claims (4)

[Claims] 1. A first check word composed of a plurality of information words and a first check word having a minimum distance d ₁ (d ₁ is an integer of 2 or more) added to the plurality of information words. For a data block composed of a large number of code blocks, a data series consisting of words selected from each of the first code blocks and a minimum distance added to this data series are d ₂ (d ₂ is 2 or more). An error correction method for decoding a codeword that is doubly encoded so that a plurality of second code blocks are formed by a second check word that is Error check / correction of the second code block is performed by using the check word of the second check word, and a flag indicating an error detection state is generated for each of the data sequences to which the second check word is added. 1 inspection word and above Above using the lugs first
When the error detection / correction of the code block is performed, it is determined that the word to which the flag is added among the words to which the flag is added of the first code block is erroneous. The number of words to be corrected and the number of words to be subjected to error position detection and correction by the first check word in the first code block other than the words to be corrected An error correction method, characterized in that a combination is set to any one of the combinations determined by the minimum distance d ₁ of the first check word according to the state of the flag, and error correction is performed. 2. In the error detection / correction of the second code block using the second check word, p ₁ word error corrections of 2p ₁ ≦ d ₂ −1 are performed, and the first check error correction is performed. the error detection and correction of a plurality of information words first check word using a test word and the flag is added, that detects the p ₂ pieces of error location is _{2p 2 + q 2 ≦ d 1} -1 The error correction is performed by the combination of the word for correcting the error and the word to which the q ₂ flag is added as an error, and the number of corrected words p ₂ and d ₂ is The error correction method according to claim 1, wherein the error correction method changes depending on the state of the generated flag. 3. The error correction method according to claim _2, wherein the correction word numbers p ₂ and q ₂ change depending on the number of generated flags. 4. An information word, a check word, and a first code added to the information word and the check word of one code block.
In the error correction device that performs the second correction using the flag indicating the correction state of the above, the syndrome generation circuit that generates the syndrome from the information word and the check word, and the number of flags added to the information word and the check word. A counter that counts, a storage circuit that stores the position of the flag that is added to the information word and the inspection word, the value of the syndrome that is generated by the syndrome generation circuit, and the addition of the flag that is stored in the storage circuit. An arithmetic circuit that performs an operation on the Galois field using the position of the word that is set, and the arithmetic circuit that controls the above-mentioned flag in the word to which the above-mentioned flag is added in the above-mentioned code block. Assuming that there is an error, the number of words to be subjected to the second correction by the check word and the correction pair The combination of the error position detection by the check word in the code block other than the determined word and the number of words to be subjected to the second correction among the combinations determined by the minimum distance of the check word. An error correction device comprising a control circuit for performing error correction by setting one of the flags according to the number of flags counted by the counter.