JPH0353818B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an error correction method that has a high error correction ability for both burst errors and random errors, and can simplify the configuration of an error correction device.

The applicant of the present application has previously proposed a method called cross interleaving as a data transmission method effective against burst errors. This generates a first check word sequence by supplying one word included in each of the PCM data sequences of multiple channels in a first alignment state to a first error correction encoder; The first check word series and the PCM data series of multiple channels are
array state, and one word included in each is the second
the second error correction encoder by feeding
It generates a check word sequence, and performs double interleaving (arrangement rearrangement) on a word-by-word basis. Interleaving distributes and transmits check words and PCM data included in a common error correction block.
This is intended to reduce the number of error words among a plurality of words included in a common error correction block when the original arrangement is restored on the receiving side. In other words, when a burst error occurs during transmission, this burst error can be dispersed. If such interleaving is performed twice,
Since each of the first and second check words constitutes a separate error correction block, even if one of the check words cannot correct an error, the other can be used to correct the error. , Therefore, the error correction ability can be further improved. By the way, if even one bit in one word is erroneous, the entire word is treated as erroneous, so when handling received data with relatively many random errors, it is not always necessary to have sufficient error correction ability. I can't say that.

Therefore, it is possible to detect and correct up to a 2-word error in a predetermined word within one block (maximum number of errors that can be detected and corrected is 2 words), and when the error location is known, it is possible to correct, for example, a 4-word error (the maximum number of errors that can be corrected is 2 words). error correction code (adjacent (b-
(adjacent) code) is combined with the above-mentioned multiple interleaving. Also, this error correction code is
When only one word error is to be corrected, the structure of the decoder can be greatly simplified.

In order to effectively utilize the high correction ability of such an error correction code, the present invention adds a pointer indicating the presence or absence of an error to each word when decoding the first stage, and decoding the next stage. The state of this pointer is determined during decoding, and error correction is performed using the determination result. Along with this, when performing the next stage of decoding, errors are detected depending on whether the pointer is in a specific state or not, and errors are corrected using the error location indicated by this pointer. . In other words,
In the above proposal, data arrangement rearrangement such as interleaving and deinterleaving disperses burst errors occurring in the transmission system and prevents the number of error words in one error correction block from becoming so large that it cannot be corrected. However, if the duration of the burst error becomes long, the error correction block obtained by deinterleaving and restoring the data array to its original state will reduce the number of adjacent words containing errors. A condition arises. In this application, only when such a specific error can be known from the state of the pointer, error correction is performed on these multiple error words, and error correction is performed using the error location indicated only by the pointer. The risk of erroneous error correction can be reduced compared to performing erroneous error correction.

First, the error correction code used in the present invention will be explained. When describing an error correction code, a vector representation or a cyclic group representation is used. First, consider an irreducible m-th degree polynomial F(x) on GF(2). A body GF that only has elements of “0” and “1”
On (2), the irreducible polynomial F(x) has no roots. Therefore, consider a virtual root α that satisfies (F(x)=0). At this time, 2 ^m different elements 0, α, α ² , α ³ . . . are expressed as powers of α including zero elements.
α ^2m-1 constitutes the extended field GF(2 ^m ). GF (2 ^m )
is a polynomial ring modulo the m-th order irreducible polynomial F(x) over GF(2). The element of GF (2 ^m ) is 1, α=
It can be expressed as a linear combination of {x}, α ² ={x ² }, ... α ^m-1 = {x ^m-1 }. That is, a ₀ +a ₁ {x}+a ₂ {x ² }+...+a _n-1 {x ^m-1 } = a ₀ +a ₁ α+a ₂ α ² +...+a _n-1 α ^m-1 or (a _{n- 1} , a _n-2 , ..., a ₂ , a ₁ , a ₀ ) Here, a ₀ , a ₁ , ..., a _n-1 ∈GF(2).

As an example, considering GF(2 ⁸ ), (mod, F
(x) = x ⁸ + x ⁴ + x ³ + x ² + 1), and all 8-bit data is a ₇ x ⁷ + a ₆ x ⁶ + a ₅ x ⁵ + a ₄ x ⁴ + a ₃ x ³ + a ₂ x ² + a ₁ x + a ₀ Or it can be written as (a ₇ , a ₆ , a ₅ , a ₄ , a ₃ , a ₂ , a ₁ , a ₀ ), so for example a ₇ is on the MSB side and a ₀ is on the LSB side.
Assign to the side. a _o belongs to GF(2), so 0
Or 1.

Further, the following (m×m) matrix T is derived from the polynomial F(x).

T=0 0 ... 0 a ₀ 1 0 ... 0 a ₁ 0 1 ... 0 a ₂ 〓 〓 〓 〓 0 0 ... 1 a _n-1 Another expression uses a cyclic group. This takes advantage of the fact that the 0 element is removed from GF(2 ^m ) and the remaining elements form a multiplicative group of order 2 ^m -1. When the elements of GF (2 ^m ) are expressed using a cyclic group, they become 0, 1 (= α ^2m-1 ), α, α ² , α ³ , ..., α ^2m-2 .

Now, in one example of the present invention, when m bits are one word and n words constitute one block, k check words are generated based on the parity check matrix H below.

H= 1 α ^n-1 α ^2(n-1) 〓 α ^(k-1)(n-1) 1 α ^n-2 α ^2(n-2) 〓 α ^(k-1)(n-2) … … … … 1 α α ² 〓 α ^k-1 1 1 1 〓 1 Furthermore, the parity check matrix H can be similarly expressed using the matrix T.

H= T ^n-1 T ^2(n-1) 〓 T ^(k-1)(n-1) I T ^n-2 T ^2(n-2) 〓 T ^(k-1)(n-2) I T ¹ T ² 〓 T ^k-1 I I I 〓 I However, is a (m×m) unit matrix.

As mentioned above, the expression using the root α and the generation matrix T
Expressions using are similar to each other.

For example, if we use four (k=4) check words, the parity check matrix H is H=1 α ^n-1 α ^2(n-1) α ^3(n-1) 1 α ^{n- 2 2(n-2)} α ^3(n-2) … … … … 1 α α ² α ³ 1 1 1 1 . One block of received data is expressed as a column vector V
= (W^ _o-1 , W^ _o-2 , ..., W^ ₁ , W^ ₀ ) (where W^ _i = W _i +
e _i , e _i : error pattern), the four syndromes S ₀ , S ₁ , S ₂ , S ₃ that occur on the receiving side become S ₀ S ₁ S ₂ S ₃ =H· ^VT . This error correction code has the ability to correct errors up to 4 words. In other words, it is possible to detect and correct errors up to 2-word errors in one error correction block, and when the error location is known, it is possible to detect and correct errors up to 3-word errors or 4-word errors.
Word errors can be corrected.

4 check words in 1 block (p=
W ₃ , q=W ₂ , r=W ₁ , s=W ₀ ).
This check word is obtained as follows. However, Σ means _o-1 〓 ⁱ⁼⁴ .

p+q+r+s=ΣW _i =a α ³ p+α ² q+αr+s=Σα ⁱ W _i =b α ⁶ p+α ⁴ q+α ² r+s=Σα ²ⁱ W _i =c α ⁹ p+α ⁶ p+α ³ r+s=Σα ³ⁱ W _i =d Skip the calculation process However, if only the results are shown, p q r s=α ²¹² α ¹⁵³ α ¹⁵² α ²⁰⁹ α ¹⁵⁶ α ² α ¹³⁵ α ¹⁵² α ¹⁵⁸ α ¹³⁸ α ² α ¹⁵³ α ²¹⁸ α ^{158 α 156 α 212 a} b c d . In this way, check words p, q,
The role of the encoder provided on the transmitting side is to form r and s.

Next, a basic algorithm for error correction when data containing check words formed as described above is transmitted and received will be described.

[1] When there is no error: S ₀ = S ₁ = S ₂ = S ₃ = 0 [2] When there is a 1-word error (error pattern is e _i ): S ₀ = e _i S ₁ = α ⁱ e _i S ₂ = α ²ⁱ e _i S ₃
= α ³ⁱ e _i Therefore, α ⁱ S ₀ = S ₁ α ⁱ S ₁ = S ₂ α ⁱ S ₂ = S ₃ , and when i is changed sequentially, one word depends on whether the above relationship holds. It is possible to determine whether there is an error. Alternatively, S ₁ /S ₀ =S ₂ /S ₁ =S ₃ /S ₂ =α ⁱ , and the error location i can be found by referring to the conversion table previously stored in the ROM for the pattern of α ⁱ . The syndrome S ₀ at that time becomes the error pattern e _i itself.

[3] In the case of two-word error (e _i , e _j ) S ₀ = e _i + e _j S ₁ = α ⁱ e _i + α ^j e _j S ₂ = α ²ⁱ e _i + α ^2j e _j S ₃ = α ³ⁱ e _i +α ^3j e _{jTransforming} the above equation, α ^j S ₀ +S ₁ = (α ⁱ + α ^j )e _i α ^j S ₁ +S ₂ = α ⁱ (α ⁱ +α ^j )e _i α ^j S ₂ +S ₃ = α ²ⁱ (α ⁱ + α ^j ) e _i Therefore, if α ⁱ (α ^j S ₀ + S ₁ ) = α ^j S ₁ + S ₂ α ⁱ (α ^j S ₁ + S ₂ ) = α ^j S ₂ + S ₃ holds. , it is determined that there is a 2-word error, and the error locations i and j are known. In other words, i
By changing the combination of and j, check whether the relationship in the above equation holds true. The error pattern at that time is e _i =S ₀ +α ^-j S ₁ /1+α ^ij e _j =S ₀ +α ^-i S ₁ /1+
α ^ji [4] In case of 3-word error (e _i , e _j , e _k ) S ₀ = e _i + e _j + e _k S ₁ = α ⁱ e _i + α ^j e _j + α ^k e _k S ₂ = α ²ⁱ e _i + α ^2j e _j + α ^2k e _k S ₃ = α ³ⁱ e _i + α ^3j e _j + α ^3k e _k Transforming the above equation, α ^k S ₀ + S ₁ = (α ⁱ + α ^k ) e _i + (α ^j + α ^k )e _j α ^k S ₁ +S ₂ =α ⁱ (α ⁱ +α ^k )e _i +α ^j (α ^j +α ^k )e _j α ^k S ₂ +S ₃ = α ²ⁱ (α ⁱ +α ^k )e _i + α ^2j ( α ^j + α ^k )e _j Therefore α ^j (α ^k S ₀ + S ₁ ) + (α ^k S ₁ + S ₂ ) = (α ⁱ + α ^j ) (α ^j + α ^k ) e _i α ^j (α ^k S ₁ + S ₂ ) + (α ^k S ₂ + S ₃ ) = α ⁱ (α ⁱ + α ^j ) (α ⁱ + α ^k )e _i From the above equation, α ⁱ (α ^j (α ^k S ₀ + S ₁ ) + (α ^k If S ₁ +S ₂ ))=α ^j (α ^k S ₁ +S ₂ )+(α ^k S ₂ +S ₃ ) holds true, it can be determined that a 3-word error has occurred.
However, the condition is that (S ₀ ≠0, S ₁ ≠0, S ₂ ≠0). At that time, each error pattern is e _i = S ₀ + (α ^-j + α ^-k ) S ₁ + α ^-jk S ₂ / (1 + α ^ij
)(1+α ^ik ) e _j =S ₀ +(α ^-k +α ^-i )S ₁ +α ^-ki S ₂ /(1+α ^ji
) (1 + α ^jk ) e _k = S ₀ + (α ^-i + α ^-j ) S ₁ + α ^-ij S ₂ / (1 + α ^ki
)(1+α ^kj ). In reality, the configuration for correcting 3-word errors becomes complicated, and the time required for the correction operation becomes longer. Therefore, it is practical to perform an error correction operation by combining the case where the error locations of i, j, k, and l are known by a pointer and using the above equation for checking at that time.

[5] In case of 4-word error (e _i , e _j , e _k , e _l ): S ₀ = e _i + e _j + e _k + e _l S ₁ = α ⁱ e _i + α ^j e _j + α ^k e _k + α ^l e _l S ₂ = α ²ⁱ e _i + α ^2j e _j + α ^2k e _k + α ^2l e _l S ₃ = α ³ⁱ e _i + α ^3j e _j + α ^3k e _k + α ^3l e lTransforming _the above equation gives e _i = S ₀ +(α ^-j +α ^-k +α ^-l )S ₁ +(α ^-jk +
α ^-kl +α ^-lj )S ₂ +α ^-jkl S ₃ /(1+α ^ij )(1
+ α ^ik ) (1 + α ^il ) e _j = S ₀ + (α ^-k + α ^-l + α ^-i ) S ₁ + (α ^-kl +
α ^-li + α ^-ik ) S ₂ + α ^-kli S ₃ / (1 + α ^ji ) (1
+ α ^jk ) (1 + α ^jl ) e _k = S ₀ + (α ^-l + α ^-i + α ^-j ) S ₁ + (α ^-li +
α ^-ij + α ^-il ) S ₂ + α ^-lij S ₃ / (1 + α ^ki ) (1
+ α ^kj ) (1 + α ^kl ) e _l = S ₀ + (α ^-i + α ^-j + α ^-k ) S ₁ + (α ^-ij +
α ^-jk + α ^-ki ) S ₂ + α ^-ijk S ₃ / (1 + α ^li ) (1
+α ^lj ) (1+α ^lk ) pointer to error location (i,
j, k, l) is known, error correction can be performed by the above-mentioned calculation.

The basic error correction algorithm described above uses syndromes S ₀ to _{S 3} to check for errors in the first step, check to see if there is a 1-word error in the second step, and check to see if there is a 2-word error in the third step. When trying to correct even a 2-word error, it takes a long time to complete all the steps, and this problem especially occurs when determining the error location of a 2-word error. arise. Therefore, a modified algorithm that does not cause such a problem and is effective when correcting a two-word error will be described below.

The formulas for the syndromes S ₀ , S ₁ , S ₂ , S ₃ in the case of two-word errors (e _i , e _j ) are as before: S ₀ = e _i +e _j S ₁ = α ⁱ e _i + α ^j e _j S ₂ = α ²ⁱ e _i + α ^2j e _j S ₃ = α ³ⁱ e _i + α ^3j e _jIf we transform this equation, (α ⁱ S ₀ + S ₁ ) (α ⁱ S ₂ + S ₃ ) = (α ⁱ S ₁ +S ₂ ) ² Further transform to find the error location polynomial below.

(S ₀ S ₂ + S ₁ ² ) α ²ⁱ + (S ₁ S ₂ + S ₀ S ₃ ) α ⁱ + (S ₁ S ₃ + S ₂ ² )=0 Here, the coefficient of each equation is S ₀ S ₂ + S ₁ ² = A S ₁ S ₂ + S ₀ S ₃ = B S ₁ S ₃ + S ₂ ² = C. By using the coefficients A, B, and C in the above equation, the error location in the case of a two-word error can be determined.

[1] When there is no error: A=B=C=0, S ₀ =
0, S ₃ =0 [2] In the case of a 1-word error: A 1-word error is determined when A=B=C=0, S ₀ ≠0, and S ₃ ≠0. (α ⁱ =
The error location i is found from S ₁ /S ₀ ), and error correction is performed using (e _i =S ₀ ).

[3] In the case of a 2-word error: In the case of an error of 2 or more words, (A≠0,
B≠0, C≠0) holds, and the determination becomes extremely simple. Also, at this time, Aα ²ⁱ +Bα ⁱ +C=0 (however, i=0 to (n−
1)) is established. Here, if (B/A=D, C/A=E), then D=α ⁱ +α ^j and E=α ⁱ ·α ^j and α ²ⁱ +Dα ⁱ +E=0. Here, if the difference between the two error locations is t, that is, (i=i+t), then it is transformed as D=α ⁱ (1+α ^t ) and E=α ^2i+t . Therefore, D ² /E=(1+α ^t ) ² /α ^t =α ^−t +α ^t . The value of (α ^{- t} + α ^t ) for each of (t = 1 to (n-1)) is written in advance in the ROM, and the value of (D ² /E) calculated from the ROM output and the received word is written in advance. t is found by detecting a match with the value. If this matching relationship does not hold, there is an error of three or more words. Therefore, by setting X=1+α ^t Y=1+α ^−t =D ² /E+X, α ⁱ =D/X, α ^j =D/Y, and error locations i and j can be found. The error patterns e _i and e _j are e _i =(α ^j S ₀ +S ₁ )/D=S ₀ /Y+S ₁ /D e _j =(α ^j S ₀ +S ₁ )/D=S ₀ /X+S ₁ /D This allows error correction to be performed.

The modified correction algorithm described above can significantly reduce the time required to determine the error location when correcting a two-word error, compared to the basic algorithm.

Incidentally, if the number k of check words is further increased, the error correction ability is further improved. For example, if (k=6), it has error correction capability of up to 6 words. That is, up to 3 word errors can be detected and corrected, and when the error location is known, up to 6 word errors can be corrected.

Hereinafter, a specific example in which the present invention is applied to recording and reproducing audio PCM signals will be described with reference to the drawings. FIG. 1 shows the entirety of an error correction encoder provided in a recording system, and an audio PCM signal is supplied to its input side. audio
The PCM signal is formed by sampling each of the left and right stereo signals at a sampling frequency f _s (for example, 44.1 [KHz]) and converting one sample into one word (16 bits in two's complement code). ing. Therefore, for the left channel audio signal, PCM data with consecutive words (L ₀ , L ₁ , L ₂ ...) is obtained, and for the right channel audio signal, (R ₀ , R ₁ , R _{2 ...} ) is obtained. …)
PCM data in which each word is consecutive is obtained.
This left and right channel PCM data is divided into 6 channels each, for a total of 12 channels.
A PCM data series is input. At a given timing, (L _6o , R _6o , L _6o+1 , R _6o+1 , L _6o+2 ,
R _6o+2 , L _6o+3 , R _6o+3 , L _6o+4 , R _6o+4 , L _6o+5 ,
12 words of R _6o+5 ) are input. In this example,
One word is divided into upper 8 bits and lower 8 bits, and 12 channels are further processed as 24 channels. For simplicity, one word of PCM data is expressed as W _i , and for the upper 8 bits,
W _i , A and A suffixes are added, and the lower 8 bits are distinguished by adding W _i , B and B suffixes. For example, L _6o is divided into two parts, W _12o ,A and W _12o ,B.

These 24 channels of PCM data series are first supplied to the even-odd interleaver 1. (n=
0, 1, 2...), then L _6o (W _12o , A, W _12o ,
B), R _6o (=W _12o+1 , A, W _12o+1 , B), L _6o+2 (=
W _12o+4 , A, W _12o+4 , B), R _6o+2 (=W _12o+5 , A,
W _12o+5 , B), L _6o+4 (=W _12o+8 , A, W _12o+8 ,
B), R _6o+4 (W _12o+9 , A, W _12o+9 , B) are even-numbered words, and the others are odd-numbered words. PCM consisting of even words
1-word delay circuit (2A) (2B) (3A) (3B) (4A) where each data series has an even-odd interleaver 1
It is delayed by one word by (4B) (5A) (5B) (6A) (6B) (7A) (7B). Of course, more than one word, for example eight words, may be delayed. In addition, in the even-odd interleaver 1, 12 data sequences consisting of even-numbered words are
The 12 data sequences consisting of odd-numbered words are converted so as to occupy the 13th to 24th transmission channels.

The even-odd interleaver 1 is provided to prevent errors in two or more consecutive words of each of the left and right stereo signals, and to prevent these errors from becoming uncorrectable. For example, considering three consecutive words (L _i-1 , L _i , L _i+1 ), L _i is incorrect,
However, if this error is uncorrectable, L _i-1 or
It is desired that L _i+1 is correct. When correcting erroneous data L _i , it is possible to interpolate L _i using the previous correct word L _i-1 (previous value hold), or use the average value of L _i-1 and L _i+1 . This is to interpolate L _i . The delay circuits (2A) (2B) to (7A) (7B) of the even-odd interleaver 1 are provided to ensure that adjacent words are included in different error correction blocks. Furthermore, the reason why transmission channels are grouped into data sequences consisting of even-numbered words and data sequences consisting of odd-numbered words is that when interleaving is performed, the records of adjacent even-numbered words and odd-numbered words are This is to make the distance between the positions as large as possible.

At the output of the even-odd interleaver 1, a PCM data sequence of 24 channels in the first arrangement state appears, one word is taken out from each of them and supplied to the encoder 8, and the first check word Q _12o ,
Q _12o+1 , Q _12o+2 , Q _12o+3 are formed. The first error correction block including the first check word is (W _12o-12 , A, W _12o-12 , B, W _12o+1-12 , A,
W _12o+1-12 , B, W _12o+4-12 , A, W _12o+4-12 , B,
W _12o+5-12 , A, W _12o+5-12 , B, W _12o+8-12 , A,
W _12o+8-12 , B, W _12o+9-12 , A, W _12o+9-12 , B,
W _12o+2 , A, W _12o+2 , B, W _12o+3 , A, W _12o+3 ,
B, W _12o+6 , A, W _12o+6 , B, W _12o+7 , A,
W _12o+7 , B, W _12o+10 , A, W _12o+10 , B,
W _12o+11 , A, W _12o+11 , B, Q _12o , Q _12o+1 ,
Q _12o+2 , Q _12o+3 ). In the first encoder 8,
Number of words in 1 block: (n=28), Number of bits in 1 word: (n=8), Number of check words: (k=4)
is encoded.

These 24 PCM data sequences and 4 check word sequences are supplied to the interleaver 9. In the interleaver 9, the position of the transmission channel is changed so that a check word sequence is interposed between the PCM data sequence consisting of even-numbered words and the PCM data sequence consisting of odd-numbered words, and then a delay for interleaving is performed. Processing is in progress. This delay processing is performed for each of the other 27 transmission channels excluding the first transmission channel, 1D, 2D, 3D, 4D, ..., 26D, 27D (where D is the unit delay amount, for example 4 This is done by inserting a delay circuit with a delay amount of (word).

At the output of the interleaver 9, 28 data sequences in the second arrangement state appear, and one word is extracted from each data sequence and sent to the encoder 1.
0 and the second check word P _12o ,
P _12o+1 , P _12o+2 , P _12o+3 are formed. The second error correction block consisting of 32 words including the second check word is as follows.

(W _12o-12 , A, W _12o-12(D+1) , B,
W _{12o+1-12(2D+1)} , A, W _{12o+1-12(3D+1)} , B,
W _{12o+4-12(4D+1)} , A, W _{12o+4-12(5D+1)} , B,
W _{12o+5-12(6D+1)} , A, W _{12o+5-12(7D+1)} , B,...
Q _12o-12(12D) , Q _{12o+1-12(13D)} , Q _{12o+2-12(14D)} ,
Q _{12o+3-12(15D)} ,...W _{12o+10-12(24D)} ,A,
W _{12o+10-12(25D)} , B, W _{12o+11-12(26D)} , A,
W _{12o+11-12(27D)} , B, P _12o , P _12o+1 , P _12o+2 ,
_P12o+3 ) Among the 32 data sequences including the first and second check words, an interleaver 11 in which a 1-word delay circuit is inserted is provided for even-numbered transmission channels. , and inverters 12, 13, 14, and 15 are inserted for the second check word series. The interleaver 11 takes care of the fact that an error that straddles the boundary between blocks is likely to result in an uncorrectable word count error. Further, inverters 12 to 15 are provided to prevent a malfunction in which all data in one block becomes "0" due to dropout during transmission, and this is determined to be correct in the reproduction system. For the same purpose, an inverter may also be inserted for the first check word series.

Then, each of the 32 words extracted from each of the 24 PCM data sequences and 8 check word sequences that are finally obtained is serialized, and as shown in Figure 2, 16-bit synchronization is placed at the beginning. A signal is added to form one transmission block and transmitted. In FIG. 2, one word extracted from the i-th transmission channel is shown as u _i for simplicity of illustration. Specific examples of transmission systems include magnetic recording and reproducing devices, rotating disk devices, and the like.

The encoder 8 described above is related to the error correction code as described above, (n=28, m=8, k=4)
and a similar encoder 10 has (n=32, m=8,
k=4).

In this transmission form, the words contained in the same first error correction block (i.e. the 24 words supplied to the encoder 8) when the synchronization signal is ignored.
Consider the distance in the transmission path between For example, if we consider words W _12o-12 ,A and W _12o-12 ,B, the distance between adjacent words included in the first error correction block is 12(D+1)(words).
becomes. However, since the check words Q _12o , Q _12o+1 , Q _12o+2 , Q _12o+3 formed by the encoder 8 are inserted between the 24 data words, the words W _12o+9-12 , The distance between B and W _12o+2 , A is 12 (D
+1). Therefore, if a burst error with a length exceeding 12 (D+1) occurs in the transmission path, (W _12o-12 , A, W _12o-12 , B...
12 words of W _12o+9-12 , B) and (W _12o+2 , A,
In each of the 12 words W _12o+2 , B...W _12o+11 , B), two or more adjacent words become error words. Two or more such adjacent words, e.g. 4
When it is detected that a word is an error word, error correction is performed for this four-word error when the error location is known. In general, when detecting and correcting errors for each block consisting of multiple words, if information indicating an error is not added to the word, there will be more than a predetermined number of error words in the same error correction block, and the error will be corrected. When this is not possible, it is unclear which words contain errors. In addition, if the error location is known and correction is performed on a given word that is considered an error word even though it does not contain an error, the corrected word may become an incorrect word. be. However, in the present invention, even when transmitting using interleaving, for example, random errors in the transmission path often cause errors in adjacent words as a result of interleaving. Since the above correction is performed only on error words, the possibility of erroneous error correction can be reduced. However, if the error location is (i, i+1, i+
2, i+3), using the fact that they are adjacent to each other,
The configuration of error correction can be simplified.

In further detailing one embodiment of the present invention, the reproduced data is applied to the input of the error correction decoder shown in FIG. 3 every 32 words of one transmission block. Since this is playback data, it may contain errors. In the absence of errors, the 32 words applied to the input of this decoder will match the 32 words that appear at the output of the error correction encoder. The error correction decoder performs deinterleaving processing corresponding to the interleaving processing in the encoder to restore the data order and then perform error correction.

First, a deinterleaver 1 in which a 1-word delay circuit is inserted for odd-numbered transmission channels.
Further, inverters 17, 18, 19, and 20 are inserted for the check word sequence, and the check word sequence is supplied to the first stage decoder 21. Decoder 21
Now, as shown in Figure 4, the parity check matrix
Syndromes S ₁₀ , S ₁₁ , S ₁₂ , and S ₁₃ are generated from H _c1 and the input 32 words (V ^T ), and error correction is performed based on these syndromes. α is (F(x)=x ⁸
+x ⁴ +x ³ +x ² +1) is the element of GF(2 ⁸ ). From the decoder 21, 24 PCM data sequences and 4 check word sequences appear, and for each word of this data sequence, at least a 1-bit pointer indicating the presence or absence of an error (if there is an error, " 1”,
Otherwise, "0") is added.
In FIGS. 4 and 5, and in the following description, one received word W^ _i is simply referred to as W _i .

The output data sequence of this decoder 21 is supplied to a deinterleaver 22. Deinterleaver 22
are for canceling the delay processing performed by the interleaver 9 in the error correction encoder, and are applied to each of the channels from the first transmission channel to the 27th transmission channel (27D, 26D, 25D,
...2D, 1D) and delay circuits with different delay amounts are inserted. The output of the deinterleaver 22 is supplied to a decoder 23 at the next stage. In the decoder 23, as shown in _FIG.
and from the input 28 words, the syndrome S ₂₀ ,
S ₂₁ , S ₂₂ , and S ₂₃ are generated, and error correction is performed based on them.

The data sequence appearing at the output of the next-stage decoder 23 is supplied to an even-odd interleaver 24. In the even-odd deinterleaver 24, the PCM data series consisting of even-numbered words and the PCM data series consisting of odd-numbered words are returned so that they are located on different transmission channels, and the PCM data series consisting of odd-numbered words is A 1-word delay circuit is inserted for each series. At the output of this even-odd deinterleaver 24, a PCM data sequence is obtained having exactly the same arrangement and predetermined transmission channel as that supplied to the input of the error correction encoder. Although not shown in FIG. 3, a correction circuit is provided next to the even-odd deinterleaver 24, and performs correction such as average value interpolation to make errors that cannot be corrected by the decoders 21 and 23 less noticeable. will be carried out.

In one example of the present invention, the first stage decoder 21 corrects up to one word error. Then, within one error correction block, 2
If it is detected that there is an error in more than one word, add at least a 1-bit pointer indicating that there is an error to all 32 words in this error correction block or 28 words excluding the check word. . This pointer is "1" when there is an error, otherwise
This is set to “0”. Note that a pointer indicating that an error exists may be added even when the above-mentioned predetermined number of words is corrected during first-stage decoding. When one word is 8 bits, a pointer is added as one bit above the most significant bit, making one word 9 bits, processed by the deinterleaver 22, and supplied to the next stage decoder 23. Ru.

The next stage decoder 23 performs error correction using the number of error words or error location in the first error correction block indicated by this pointer. FIG. 6 shows an example of error correction in the next-stage decoder 23. In FIG. 6 and the following explanation, the number of error words caused by the pointer is expressed as Np, and the error location caused by the pointer is expressed as Ei. represent. Also,
In FIG. 6, Y represents affirmation and N represents negation. Since the next-stage decoder 23 corrects up to 2-word errors, a modified algorithm is preferable as the error correction algorithm. That is, at the beginning of the flowchart shown in FIG. 6, the error location polynomial (Aα ²ⁱ +
Bα ⁱ +C=0) is calculated, and each coefficient A, B,
Error correction is performed using C and syndromes S ₂₀ to S ₂₃ . At the same time, the total number Np of pointers indicating errors included in one block is counted. Of course, as shown by the broken line in FIG. 6 using the syndrome, detection of the absence of errors, 1
A basic algorithm that detects word errors and detects two-word errors in stages may be used.

(1) Check for errors. (A=B=
C=0, S ₂₀ =0, S ₂₃ =0), it is assumed that there is no error. In that case, check whether (Np≦z ₁ ). If (Np≦z ₁ ), it is determined that there is no error, and the pointer in the error correction block is cleared (“0”). If (Np>Z ₁ ), it is determined that the syndrome detection is incorrect and the pointer is left as is or the pointers of all words in that block are set to “1”.
Make it. As z ₁ , it is quite large, for example, 14.

(2) Check whether there is a one-word error. (A=B
= C = 0, S ₂₀ ≠ 0, S ₂₃ ≠ 0), it is tentatively determined to be a one-word error, and the error location i is determined from (S ₂₁ /S ₂₀ =α ⁱ ). It is detected whether this error location i corresponds to that by the pointer. If there are multiple error locations by pointers, it is checked to see if they match any of them. If (i=Ei), then it is checked whether (Np≦z ₂ ).
z ₂ is, for example, 10. If (Np≦z ₂ ), then
It is determined that it is a one-word error, and error correction is performed using (e _i =S ₂₀ ). (i=Ei) but
If (Np>z ₂ ), the number of pointers is too large for a one-word error, so it is judged that it is dangerous to judge it as a one-word error.
Either leave the pointers as they are, or treat all words as errors and set each word's pointer to "1".

If (i≠Ei), it is checked whether (Np≦z ₃ ). z ₃ is a fairly small number, for example 3
It is. When (Np≦z ₃ ) holds, the one-word error at error location i is corrected in the syndrome calculation.

In the case of (Np<z ₃ ), it is further checked whether (Np≦z ₄ ). In other words, (z ₃ <Np≦z ₄ )
When , it means that Np is too small considering that the one-word error due to the syndrome is incorrectly determined, so the pointers for all words in that block are set to "1". On the contrary (Np＞z ₄ )
If so, leave the pointer as is.

(3) Check whether there is a 2-word error. If it is a two-word error, the error location (i, j) is detected by calculation. (A≠0,
B≠0, C≠0) and (D ² /E=α ^-t +α ^t , where t=1 to 27), it is determined that there is a 2-word error, and (α ⁱ =D/X, α The error location (i, j) is determined by ^j = D/Y). A match between the error locations i, j and the error locations Ei, Ej by pointers is detected. When (i=Ei, j=Ej), the number of pointers indicating an error is compared with a predetermined value _z5 .
If (Np≦z ₅ ), the error location i,
The two word error for j is corrected. This correction is performed by finding the error patterns e _i and e _j as described above. When (Np>z ₅ ),
For example, since there is a high possibility that an error of three or more words is mistakenly detected as a two-word error, no correction is made and the pointer is left as is, or all words in the block are marked as errors.

When checking the error location, (i=Ei, j≠Ej) or (i≠Ei, j=Ej)
When any of the relationships holds true, (Np≦z ₆ )
It can be checked whether When (Np≦z ₆ ),
A two-word error regarding error locations i and j is corrected. When (Np>z ₆ ),
It can be checked whether (Np≦z ₇ ). This is to check the number of pointers indicating an error when the above relationship of error location is partially satisfied, and if (Np≦z ₇ )
When this happens, it is determined that the number of pointers indicating an error is too small, and the pointers of all words in that block are set to "1". When (Np>z ₇ ), the reliability of the pointer is considered to be high, so the pointer is left as is.

When (i≠Ei, j≠Ej), it is checked whether (Np≦z ₈ ). When Np is quite small, the two-word error in i and j is corrected by giving more weight to the result obtained using the error location polynomial than to the pointer. (Np>
z ₈ ), it is further checked whether (Np≦z ₉ ). As in the case of (Np≦z ₇ ), this is a check to see whether to leave the block pointer as it is or to set all word pointers to "1".

(4) If none of the above cases (1), (2), or (3) apply, that is, if there is an error exceeding 2 words, (Np
= 3) or (Np = 4) and whether these 3 or 4 words are adjacent in each of the 12 words of the 24 data words of the first error correction block. Only when this holds true, the 4-word error is corrected for the error location using the pointer. In this case, the error location is (i,
i+1, i+2, i+3), and the error locations as described above are independent of each other4.
In addition to word error correction calculations, error patterns can be determined by considerably simplified calculations. It is shown below.

e _i = α ²¹⁸ S ₂₀ + α ¹⁵⁸ α ^-i S ₂₁ + α ¹⁵⁶ α ^-2i S ₂₂ + α ²¹² α ^-3i S ₂₃ e _i+1 = α ¹⁵⁸ S ₂₀ + α ¹³⁸ α ^-i S ₂₁ + α ² α ^-2i S ₂₂ +α ¹⁵³ α ^-3i S ₂₃ e _i+2 = α ¹⁵⁶ S ₂₀ +α ² α ^-i S ₂₁ +α ¹³⁵ α ^-2i S ₂₂ +α ¹⁵² α ^-3i S ₂₃ e _i+3 = α ²¹² S ₂₀ +α ¹⁵³ α ^-i S ₂₁ +α ¹⁵² α ^-2i S ₂₂ +α ²⁰⁹ α ^-3i S _23Also , in the case of (Np=3), (i, i+1, i
+2) 3 word error, (i+3)
It is also possible to process a 4-word error by adding a dummy error to the word at the location and using it as an error word.

(5) If none of the above cases (1), (2), (3), and (4) apply, error correction is not performed. Then, it is checked whether (Np≦z ₁₀ ). (Np≦ _z10 )
If so, it is determined that the pointer is unreliable, and
Set all word pointers to "1". (Np
> z ₁₀ ), leave the pointer as is.

Note that the value z _i compared with the total number Np of pointers indicating errors in one block is the probability of incorrect detection of the error correction code (in the above example, if there are 5 or more word errors, this is determined as no error). Errors involving 4 words or more may be judged as 1-word errors, and errors involving 3 or more words may be judged as 2-word errors. It can be a value of

In the error correction decoder shown in FIG. 3 described above, the first check words Q _12o , Q _12o+1 , Q _12o+2 ,
Error correction using Q _12o+3 and error correction using second check words P _12o , P _12o+1 , P _12o+2 , P _12o+3 are performed once for each husband and wife. If each error correction is performed at least twice (actually, about twice), the error reduction resulting from the correction can be utilized to further increase the error correction ability. can. In this way, when a decoder is provided at a later stage, the decoders 21 and 2
It is also necessary to correct the check word in step 3.

Note that in the above example, the delay processing in the interleaver 9 is performed by varying the delay amount by D, but unlike such regular changes in the delay amount, it may be irregular. Also, the second
The check word Pi not only checks PCM data, but also
This is an error correction code that also includes the first check word Qi. Similarly, it is also possible for the first check word Qi to also include the second check word Pi. Specifically, the second check word Pi may be fed back and supplied to the encoder that forms the first check word. Such a feedback type configuration is effective when the number of times of decoding is three or more as described above.

As can be understood from the above description, according to the present invention, in the first stage decoding, the maximum number of detectable and correctable errors determined corresponding to the second check word (error detection and correction is possible without using a pointer). In addition to correcting errors up to a first predetermined number that does not reach the first predetermined number (the maximum number that can be performed), if it is detected that there are at least more errors than the predetermined number, errors are corrected for all words in the block to be corrected. In the next stage of decoding, errors up to a second predetermined number that can be corrected using the error location obtained from the error syndrome are determined by checking the number of pointers. When correction is performed and there are errors exceeding the second predetermined number, the number of pointers is less than or equal to the maximum number of correctable errors (the maximum number of errors that can be corrected using pointers),
In addition, erasure correction is performed using pointers only when the error locations of the pointers are adjacent, which improves the reliability of the pointer in the first stage and minimizes missed errors and erroneous corrections in the later stages. It can be prevented.

Furthermore, in the first stage decoding, errors up to a predetermined number that does not reach the maximum number of detectable and correctable errors are corrected, so that error correction can be performed using a very simple circuit.

Even if a one-word error is corrected in the first stage decoding, if the pointer of each word in the block that includes this corrected word is set to "1", there is a further risk of incorrect error detection and incorrect correction. can be reduced.

[Brief explanation of drawings]

FIG. 1 is a block diagram of an example of an error correction encoder to which the present invention is applied, FIG. 2 is a block diagram showing an arrangement during transmission, FIG. 3 is a block diagram of an example of an error correction decoder, and FIGS. 5 and 6 are diagrams used to explain the operation of the decoder of the error correction decoder. 1, 9, 11 are interleavers, 8, 10 are encoders, 16, 22, 24 are deinterleavers, 2
1 and 23 are decoders.

Claims (1)

[Claims] 1. A plurality of channels in a first arrangement state
A first check word consisting of one word included in each PCM data series and a first check word for this word.
An error correction block is formed, and the PCM data sequences of the plurality of channels and the first check word sequence are brought into a second arrangement state by delaying each channel by a different time.
Receive data transmitted as a second error correction block consisting of one word included in each of the PCM data series of the plurality of channels and the first check word series in the arrangement state, and a second check word corresponding thereto. Then, the second check word is used to decode the first stage of the second error correction block, and then the PCM data series of multiple channels in the second arrangement state and the first check word series are channel-coded. a first arrangement state by delaying each time for a different time;
This is an error correction method in which the first check word is then used to decode the first error correction block in the second stage, and in the first stage decoding, the maximum detection correction determined corresponding to the second check word is performed. In addition to correcting errors up to a first predetermined number that does not reach the number of possible errors, at least when it is detected that there are errors exceeding the first predetermined number, all words of the block to be corrected are corrected. A pointer indicating the existence of an error is set, and in the latter stage of decoding, the first check word is used to detect and correct errors up to a second predetermined number. If the number of pointers set during the previous stage decoding in the block to be corrected is less than or equal to a preset third value, the error is corrected using the error location obtained from the error syndrome; If there are errors exceeding the second predetermined number, the number of pointers set during the previous stage decoding in the error correction target block has previously corresponded to the first check word. When the error location indicated by the above pointer is within the fourth value set below the predetermined maximum correctable error number and the error location indicated by the above pointer is adjacent, the error location indicated by the above pointer is used. An error correction method characterized in that the error is corrected by