JPS5939779B2 - Double error correction device using error pointers of adjacent codes - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a double error correction device using error pointers of adjacent codes. To provide a device capable of correcting errors in two information vectors among a plurality of information vectors (information words) in one process using a small number of each element of a correction matrix (correction matrix data) during correction. The purpose is to

Devices that transmit and receive digital signal information, or that record and play back at high density such as magnetic recording and reproducing devices (magnetic tapes, magnetic disks) and optical recording and reproducing devices, are subject to disturbances and distortions in transmission paths and recording media. A major problem is that digital signal information may be missing or have errors due to such factors.

To solve this problem, many error correction codes have been put into practical use. Among these, the double error correction method (a method that corrects errors of 2 words or less) using error pointers of adjacent codes requires complex matrix calculations to correct double errors, so the elements of the inverse matrix are prepared in advance. A method is used in which the data is calculated and stored in a read-only memory (ROM) or the like, and read out and used when necessary. However, when using ROM in this way,
An address counter for selectively reading information from the ROM is required, which complicates the circuit configuration. Moreover, if the number of elements in one vector (the number of bits in one word) is large,
For example, if the number of bits in one word is 14 bits and the number of words in the digital signal in one block is 6 words, the capacity of the ROM will be 980 bits (-14 x 14 x 5
) The actual ROM capacity is often 2N (N is a natural number), so a ROM with an even larger capacity is required.
, which is expensive. The present invention relates to an apparatus for performing adjacent code correction that corrects vector errors in two of a plurality of vectors constituting one block using an error pointer indicating which vector (word) has made an error. , First, an outline of adjacent code correction will be explained.

Now, each m-bit information vector (also called an information word) W1, W2, . . . is expressed as an element O,1.
Wn and two error correction vectors (error correction words) P, . Q (these are column vectors) is taken as one block, and a digital signal is transmitted in each block unit. It has an error pointer that indicates which vector is erroneous at the time of reception. In the correction of double errors in adjacent codes that are corrected when detected, the error correction vector P. Q is expressed as.

Here, in formulas (1) and (2), Σo represents the sum of vectors on GF2 (a finite field consisting of two elements), 1 represents the sum of vectors on GF2, and T is the unit matrix. This is a regular linear transformation matrix that is linearly independent of I, and represents, for example, an auxiliary matrix of the polynomial 1+GlX+G2X2+...+Xm. That is, the above auxiliary matrix T is defined as follows.

The m-th polynomial on GF2 is G(X)=Xm+Gm-1X
When m-1+...+GlX+GO, the auxiliary matrix T becomes.

This is defined from the following. That is, let m-element column vectors A and B on GF2 (t indicates a transposed matrix) be as follows, and these A, . Let B correspond to a polynomial, and let the remainder of x-A(x):G(x) be B(x).

Therefore, from the above formula, B, -Am-GO, . b2=Allam
gl,..., Bm-Anl-11an1gm-, so this can be expressed as a matrix.

Therefore, it is expressed as B-T-A. Note that since T must be regular, GO must be 1. Because G. This is because if is O, the first row of the auxiliary matrix T will be all 0 and will not be regular. Therefore, the polynomial G(X)=Xm-l-Gm-,Xm-"10...+Gl
It becomes x+1.

Also, as will be explained later, when making corrections, (I4T-k) must be regular because it is a condition that 珀π-k'1 exists, and therefore I and Tk must be linearly independent matrices. Therefore, I and Tk must also be linearly independent.From this, the conditions for G(x) are that at least one of its coefficients Gm-1 to gl is not 0, and ,T,.T2,...,Tn-1
\*I (N* indicates linear independence).
Now, if we rewrite the above formulas (1 and (2), we get that formula (3) holds true if there is no error.

However, Φ indicates a column vector in which all m elements are O. However, for example, the i-th information vector Wi and the j-th information vector Wj mistakenly become the following equation, and these two equations are calculated, and the above Ei. The i-th information vector Wi. j-th emotion Chang Wi
、． When Wj is assumed to be Wj, (where Ei, and E· in equation (3) is an error vector).

Therefore, the above error vector Ei. Using the partial syndromes S1 and S2 of equation (5), Ej can be calculated as follows: (I is m
By calculating these and substituting them into equation (4), it is possible to calculate and restore the correct i-th information vector Wi and 1j-th information vector Wj, respectively. By the way, when calculating the partial syndromes S1 and S2 in equation (5), the erroneous information vectors were added, but the erroneous information vectors are added as zero vectors (the result is the same as not adding them). and the partial syndromes S'1 and S'2 at that time
When W. knows from the error pointer that W. has made an error, he defines the partial syndromes S1 and S2 as follows.

S1 and S2 are information vectors W1 to Wn and P. Wi.Q pointed to by the error pointer. Except for Wj, W1 to P or W, to Q are TOk. It can be obtained by multiplying by THk etc. and adding them.

Here, Φ in the above formula is Wi, . Wj part, and Wi. Wj can be corrected and restored.

Substituting (self) expression into (substitute) expression, (TOj− in (self) expression
011T1Ij-11i)-1 as matrix M.

．． -0. and the vector G- J1 1-H・ (T1 1・SleTl−S2).

It is defined as Wj is M from (self) formula. It is obtained by multiplying j-Gi by the column vector SO, and Wi is calculated using equation (substitution). However, in this specification, for convenience of explanation, the case where the error correction vector P-Q is generated by equation (3) will be mainly explained.

The above is an outline of adjacent code correction, but an error pointer is generated as follows.

The first generation method is W1 to Wn. P. While receiving each vector of Q, the signal corresponding to each vector (for example, NRZ, MF
An error pointer is obtained by observing the envelope of the vector (M, etc.) and determining the vector as an error if it deviates from a predetermined level. The second generation method is w1 to Wn. P
The vectors of and Q are distributed among (n+2) different block signals, and an error check vector (CRC, etc.) for each block is added and transmitted for each block, and error checking is performed for each block at the time of reception. In this method, all vectors in the block signal that are erroneous are assumed to be erroneous and an error pointer is obtained. The above-mentioned adjacent code correction using the error pointer has conventionally been carried out by a circuit as shown in FIG. 1 or 2. In Figure 1,
The information vectors w1 to Wn and the error correction vector PlQ are sequentially received at the input terminal 1, and applied to the generation circuit 2 of the partial syndrome S1 and the multiplication circuit 4 for multiplying by Tn-1. This S1 generation circuit 2 is S″1 in equation (7).
Here, an example of parallel calculation is shown, and it is configured as shown in Figure 3 with m exclusive OR circuits and m registers. If you want to perform a correction operation for the next block before the operation ends, use its parallel output (WiCf) Wj)
may be temporarily stored in the register 3 before the calculation of S'1 of the next block is started. On the other hand, the input signal is transmitted to T
It is applied to a circuit (hereinafter referred to as "S2 generation circuit") 5 that generates S2 that has been transformed after being multiplied by -n-1.

As shown in FIG. 4, the S2 generation circuit 5 is composed of m registers (edge trigger type flip-flops) and (m+1) or more exclusive OR circuits (indicated by 1 in the figure). If the flip-flop (register) is initially in a clear state, the parallel input is output as is when the first clock pulse CK is received, and at the next clock pulse CK, the first vector is multiplied by T and the vector of the parallel input is added. As a result, the relationship among the input terminal 1, the output of the multiplication circuit 4, and the output of the S2 generation circuit 5 is as follows. Incidentally, since the clock pulse CK shown in FIG. 4 is not applied at the time of P input, the output of the S2 generation circuit 5 does not change.

Next, Wi. If i clock pulses are applied to the S2 generation circuit 5 of FIG. 1 in response to an error in Wj, and the input terminal 1 is set to 0 at this time, the output of the S2 generation circuit 5 is as follows.

This output is applied to the adder circuit 6, where it is added to the output S'1 from the S1 generating circuit 2 and SO-S'11si-
n-1·s'2 is calculated. The output S of this adder circuit 6
. is temporarily stored in the &ζ register 7 and then applied to the AND circuit 9, in order to generate the matrix (1( +)Ti-j)
-1 and S. Multiplication is performed. On the other hand, each data in the matrix (I[Tk)-1Mk(k-j-1) with m rows and m columns is calculated in advance and the results are stored in a storage device (for example, a read-only memory (ROM)). )) 8, and the control circuit 8a controls the matrix M1~
One Mk of MO- is selected, and the rows from the first row to the mth row of the matrix Mk are sequentially selected by the control circuit 8b.

In this way, the output (11Ti-j)-1 of the ROM 8 controlled by the control circuits 8a and 8b and the output (S'14Ti-n-1・s''2) of the register 7 are AN
After each bit is multiplied by the D circuit 9, the addition circuit 10 adds GF2. As a result, the information vector W calculated by the addition circuit 10 according to equation (9)
Each element of j is sequentially output as a serial signal in accordance with the selection of a row of matrix Mk. This serial signal is serial-parallel converted by a shift register 11 and then applied to one terminal of an adder circuit 12. At this time, the data (Wi4Wj) stored in the register 3 is input to the other terminal of the adder circuit 120, and therefore the output of the adder circuit 12 is the information vector Wi calculated according to Wi4Wj4Wj-Wi. be done. Furthermore, after completing the specified transmission of Wi, by clearing register 3 (or registers 3 and 7 are unnecessary if the next block is to be corrected after one block has been corrected, in that case, S1 generation circuit 2). , a zero vector is applied to the Sl input of the adder circuit 12, and therefore the adder circuit 12
The corrected and restored W·j applied to the other input terminal is output as is.

Next, to explain the conventional circuit for obtaining the serial output shown in the second figure, compared to the circuit shown in the first figure, a shift register 13 is provided instead of the register 3, and an AND circuit 14 is added. 11 is not necessary, and the adder circuit 12'' need only be for one element instead of m-parallel.

The shift register 13 is a register that stores the S'1 output from the S1 generation circuit 2 and also operates as a serial/parallel converter, and has a configuration as shown in FIG. Now, the adder circuit 10 sequentially outputs each element Wjl, .
Wj2), .
inl is obtained.

At this time, by applying Wj, ~Wjnl passed through the AND circuit 14 to the serial input terminal of the shift register 13, when the shift register 13 has finished outputting all m elements of S″1, Wj is suppressed. There will be
Therefore, if the AND circuit 14 is opened and the output of the shift register 13 is performed continuously, each element Wjl to Wjm of Wj is obtained at the output terminal of the adder circuit 12'. As described above, according to the conventional double error correction device, the matrix Mk-(1(1
11) All data (elements) of T-k)-1 are stored in ROM8
I remembered that the matrix Mk has m rows and m columns,
Furthermore, since k is j-1, the vectors W1 to WO
．． P. If Q is 14 bits and n is 6, then k is 5 at maximum, so the minimum storage capacity of storage device 8 using ROM is 980 (-14 x 14 x 5
) bits are also required, and the actual ROM capacity is 2N (N
is a natural number), so even more capacity RO
M had to be used, which was uneconomical. Also ROM
is expensive compared to other logic elements, and the torpedo circuit is also the first
8a and 8b in FIG. 2, and the cost of the ROM and its peripheral circuits among the correction circuits has a great influence, so the above-mentioned conventional device had the disadvantage of being expensive. The present invention eliminates the above-mentioned drawbacks, and each embodiment thereof will be described with reference to the drawings from FIG. 6 onwards.

First, a method of correction calculation performed by the apparatus of the present invention will be explained.

Calculations are performed during correction, but i does not necessarily have to be <j; in that case, i-j is a total of (2n-2) types of 1 (n-1) to -1 and 1 to (n-1). (14Ti-j
)-1 matrix.

Therefore, when we set (14Ti-j)-1-(18)T-k)-1, k-1~(n-1), k=-1~(n-1
), the present invention can be implemented.

There is a relationship expressed by equation (8)' between the vector Wj to be sought and the intermediate calculated vector SO.

Then, by multiplying both sides by (14T-k)-1, equation (9) is obtained.

Now consider a matrix (11T-k)-1 with m rows and m columns as shown in the following equation. That is, the matrix Mk of M8m columns is decomposed into m matrices of m elements and rows of each of Mkl to Mkrrl.

Now Wj-(a1, A2,...-, Am)t (however, t
indicates transposition), then for Mkl in the l row, the l-th element al is calculated as Wj(7). In the first embodiment of the present invention, a row matrix of a linear combination of Mkl to Mkrrl is generated using the same e1 to Em (e1 to En
At least one of l is not O) (n-1) types,
That is, Mld. The correction operation is performed by selectively using one row matrix of M2d,..., Mn-1, d depending on the value of i-j-1k. Only one Mkl will be explained.

The correction calculation using Mkd is performed using each Mkl of this I (-1 to m).
It is a linear combination of each correction operation. Furthermore, Mk
is a regular matrix with m rows and m columns, and Mkl to Mknl are linearly independent. Therefore, an arbitrarily created m-element row matrix (excluding the zero matrix) is a linear combination of Mkl to Mkm, that is, expressed by the (company) formula. Therefore, (n-1) Mk
One of d can be any m-element row matrix except the zero matrix. Note that Q trials e1 to Enl are elements of GF2, that is, 1 or 0. In the present invention, if m integers are L1, L2J..., Lm, TLlSO. T
We show that correction operations can be performed from L2SO, . . . , TLmsO and Mkl, and will later extend this to Mkd.

Therefore, first, if both sides of equation (5) are multiplied by TL (where L is an arbitrary integer), then equation (5) becomes as follows.

Now let the row matrix LTl of the l-th row (TLf) be,
Multiplying TL-SO by Mkl gives the formula (to) Wi's l
TL−Wjf instead of the th element al) the 1st element LTl
-Wj is calculated.

That is, Wi-(a1, A2, . . . Am)T, .
If expressed as TL-Wj(Lal, La2, . . . , Lanl)t (where t indicates a transposed matrix), then) TLlO(LlTl)L2T2,''''.

LlTm)t,...,TLm-(Lrr]T1,Lm
T2,...LmTm)t, TLl SO-T
L2・SO,..., TLm-SOVC. The vector W-/ that can be served by multiplying by Mkl is Wj″-(a1″, A2(
...A. ″) t, then it becomes.

Here, if we rewrite equation (24-1), we get the following (25
) formula is obtained.

(to) Displaying the expression as a matrix Therefore, to obtain Wj All you have to do is calculate.

In this case, lτ must be regular in order to find 1rff-1, but TLI, TL2, . ．． ．． , TLm are linearly independent, IT' is regular. Next, as mentioned above, instead of one arbitrarily selected Mkl, Mk, -e1・Mk
Let Wj″ be the vector found when using ll...4em-Mkm, and Wj″ = (a so AJJ..., AM)
When t is assumed, the following formula is obtained as a linear combination of l-1 to m in the formula.

Also, from the (funding) formula, 1T''-(LlTl.L2Tl,...
, LmTl)t, the following equation holds from these. Therefore,.

τ−1・Wj''.).The information sequence vector Wj can be found. The regularity of 'r' is also the same as that of 1T'.
τ-1 or f-1 is a matrix independent of k,
A control circuit is not required and it can be configured relatively easily using only an exclusive OR circuit, but it is also possible to select Mlcd and adopt a simple configuration (n-1 Mkd and 0
What is necessary is to select a structure that, when combined with τ-1, provides a simple configuration as a whole. ). FIG. 6 shows a block system diagram of the first embodiment of the device of the present invention.

In the figure, the same components as in FIG. 1 are denoted by the same numbers, and their explanations will be omitted. The column vector SO output taken out from the adder circuit 6 is supplied to a multiplier circuit 15 which multiplies it by TL.
Hereby or TL-SO. T2L-SOJ...,T
The output of the mL-SO is applied to an AND circuit 9''.The multiplication circuit 15 described above generally has the same number of registers 201 to 20rr1 as the number m of elements of the information vector and a plurality of exclusive registers, as shown in FIG. The vector stored in the registers 201 to 20m is multiplied by TL every time one clock pulse is received from the terminal 22. On the other hand, 16 is ij ( = -k), which selectively outputs a linear combination row matrix Mkd of an m-row matrix (11Ti-j)-1 of an m-row m-column matrix (11Ti-j)-1, depending on the value of As described above, the row matrix Mkdl, which is an arbitrary linear combination (excluding the 0 matrix) of Mkl to Mkm in the formula (self), is stored.

One row matrix Mkd corresponding to i-j-1k is selected under the control of the control circuit 17 and outputted to the inner product calculation circuit 23 consisting of the M1 circuit 9 and the addition circuit 10, where it is outputted from the multiplication circuit 15. SO. TL-SO. T2L-SO...
, T(m-1).The inner product is calculated with the parallel output of SO. As shown in FIG. 8, the inner product calculation circuit 23 has the AN of FIG.
It is composed of a group of AND gates corresponding to the D circuit 9 and a group of exclusive OR circuits corresponding to the adder circuit 10, and each element of the linear transformation vector Wj'' of the information vector Wj is serially transferred to the shift register 18. is output and the terminal 22
The data is stored in the shift register 18 in synchronization with the next clock pulse.

Here, the reason why two-word errors are corrected in series instead of in parallel in adjacent codes is as follows. Mk-SO-W
For the operation of j, Wj can be calculated in parallel instead of serially if there are exclusive OR circuits equal to the number of elements that are not O (i.e. 1) out of M2 elements of Mk minus m elements. , Mk, and in order to perform calculations on all Mk, the contents of Mk must be switched. For this purpose, the circuit consists of m (m-1) exclusive OR circuits, M2 AND circuits, and M2 AND circuits for control.
A 2-bit memory is required, and M2 bits must be output in parallel, increasing the circuit scale. Also M2
When 9 or more, the RO can output M2 bits in parallel.
M does not currently exist, so M2 bits of memory are M2×(n
-1) The dual structure of a bit ROM and a register that outputs M2 bits in parallel requires a large amount of control circuit power. For example, when m is 14, the originally required RO
In addition to M, a register for M2 bits, that is, 196 bits, a ROM, a control circuit for the register, 182 exclusive OR circuits, and 196 AND circuits are required.
Not practical. Therefore, double error correction using error pointers of adjacent codes is generally performed serially rather than in parallel. j
Wj' or Wj'' is supplied to a linear conversion circuit (circuit for multiplying 1T'-1 or oτ-1) 19, where
Column linear transformation is performed, and each element of the information vector Wj is corrected and restored, and output in parallel.

Here, the above-mentioned linear conversion circuit 19 is constituted by an exclusive OR circuit and can be easily constituted. That is,
The parallel output Wj″ of the shift register 18 is (Ar, .aJ
l...AJ)t, so when trying to obtain a predetermined information string vector Wj-(a1, A2,..., Am)t, the matrix operation of the linear conversion circuit 19 is performed by matrix f-1. = [Z1, Z2J..., Zm]t, Z1~Z
An operation is performed to treat each m as a row matrix. At that time, if there are K elements that are not O (1) among the m elements of a row matrix Zlf), then a1-zl-
In order to calculate Wj7, Zli-1 (i is 1
It is sufficient to calculate only the term ˜m), and let i, which is Zll-1, be i1, I2, . . . Ik.

Therefore, al can be calculated using (K-1) exclusive OR circuits. Similarly, for a1 to Am, each 1 of Z1 to Zm
It can be calculated using an exclusive OR circuit that subtracts 1 from the original number. Therefore,. Since τ-1 is regular, there is at least one element each of Z and ~Zm that is 1, and if KM is the number of 1 elements among the elements of Z(f) m rows and m columns, then the number required for the above matrix operation is The number of exclusive OR circuits may be (KM - m). FIG. 9 shows a block diagram of a second embodiment of the apparatus of the present invention.

This embodiment is an example in which m-14 and n=6, and the linear transformation matrix T is an auxiliary matrix of X14+X8+1.

5( is each n-1 ) type inverse matrix It is becoming.

The multiplication circuit 4'' is a circuit that multiplies T-7 and is composed of seven exclusive OR circuits.The S2 generation circuit 5 multiplies Ti-7.S'
2 is generated and output, and added to the output S''1 of the S1 generating circuit 2 in the adder circuit 6, SO-S''11T-7.S'. is obtained and input to the multiplication circuit 24. 24 has the circuit configuration shown in FIG. 10. First, each register (14 bits) is cleared, and the terminal 25 is closed.

When CK is input and one clock CK is applied to terminal 26, S. is stored. Next, open terminal 25 and select S.

If the input of the clock CK is blocked and the clock CK is sequentially input to the terminal 26, T will be repeatedly multiplied in sequence, and therefore the clock will be multiplied sequentially by S in accordance with the number of clocks CK. ．． T-SO,. T2・
SOl..., Tl3.SO are output from the output terminal 24. On the other hand, W.J. T-Wj, . . . , Tl3·Wj are as follows. Therefore, Mkl as Mkd, that is, the first row of M1 to M5 1M11)M2llM3l)M4
l) Using M5l, these are , so select the row matrices Mll to M5l corresponding to k and use 1 in FIG.
6' and sequentially output from the multiplication circuit 24.

The vector W-7 obtained by matrix calculation with -Tl3.SO becomes a vector that takes each first row of W.~JjTl3.Wj, and then Wj'' and T' are expressed as follows. Therefore, the calculation 'r'-1 of the linear conversion circuit 19 for determining Wj from Wj'' is as follows.
The operation of this matrix, T'-1 is performed by the exclusive OR circuit 7
This can be achieved by individuals. Further, when Mk8 is selected as Mkd, that is, when the row matrix of the eighth row Ml8 to M58 of M1 to M5 is selected corresponding to k and outputted from the storage device 16', the obtained vector Wj'' is Wj - Tl3.・
The following vectors are obtained by taking each of the 8th rows of Wj.

Therefore, matrix operation to obtain Wj from this Wj''.'
r'-1 is determined by the linear conversion circuit 19 as follows.

this.

The T'-1 arithmetic circuit can be realized simply by replacing the wiring, and an exclusive OR circuit is not required. Also Ml8~M58
The memory does not necessarily require a ROM, but can be constructed by a decoder circuit using several gates. Ml8 to M58, 1 tear on each 1st night, 1st tear on 14th night are unchanged, 1st tear on 2nd night and 1st tear on 4th night.
The 7th column is the same as the 3rd and 1st tears, the 5th and 1st tears, and therefore, for example, if a code consisting of 3 or more bits representing k-1 to 5 is assigned to the same column as the unchanged column of M18 to M58, This can be realized by a decoder circuit that converts the codes of the remaining nine columns after each removal. By the way, in this example, the conversion relationship between Wj7 and Wj is regular and relatively simple, and the conversion to Wj can also be performed as follows. For example, if the 14th row matrix of M1 to M5 is used, the circuit shown in FIG. 11 is inserted between the adder circuit 1σ and the shift register 11 shown in FIG. The output of the adder circuit 10' is applied.

Initially, the 6-bit shift register 27 is kept in a clear state, and when the outputs Ar, a;, . Al4, Al3, Al2, . . . , a1 are sequentially obtained from the output terminal. FIG. 12 shows a block system diagram of a third embodiment of the apparatus of the present invention.

In the figure, the same components as those in FIG. 9 are given the same numbers, and their explanations will be omitted. In FIG. 12, 30 is a data selector, which selects the S1 output from the S1 generation circuit 2, each word output obtained by multiplying T-7 from the multiplication circuit 4'', and the Φ vector. One of the outputs is passed through and applied to the multiplication circuit 24''. This multiplication circuit 24'
has a configuration in which 14 AND circuits are removed from the multiplier circuit 24 shown in FIG. applied. Assuming that the data selector 30 selectively passes the output of the multiplier circuit 1, at this time the multiplier circuit 24'' calculates Ti-8·S!, and then the data selector 30 selects the S/S of the S1 generation circuit 2. When the output is switched to pass through the selection, the multiplier circuit 2
4', s/1Ti-7·S25, that is, SO is calculated.

Thereafter, the data selector 30 is switched to output a zero vector (in general data selector ICs, it outputs 2, 4,
It has a strobe function as well as a function to select one of eight types, and when the strobe is turned off, a zero vector is output. ), thereby the multiplier circuit 24'
S in order. , T-SOl..., Tl3.SO are output. That is, according to the present embodiment, by providing the data selector 30, a circuit for multiplying T used for S2 calculation can be used to repeatedly multiply SO by T. ,
This means that it can be shared with the circuit that sequentially calculates T-SO, . . . , Tl3·SO. The output of the multiplier circuit 24'' is subsequently subjected to signal processing similar to that shown in FIG. 9, and correction calculations are performed.
Next, a fourth embodiment of the apparatus of the present invention for obtaining serial output will be described with reference to FIG. 13. In the figure, the same components as those in FIG. 12 are designated by the same numbers and their explanations will be omitted.

In FIG. 13, M18 to M58 are used as the row matrix, and the output of the multiplier circuit 2L is stored in the register 7'' when the next block is to be corrected before the correction of one block is completed.
is memorized. On the other hand, 31 is a register that stores the S1 output from the S1 generation circuit 2, and also receives and stores the serial output of the adder circuit 10'. As a result, Wi is serially outputted from the register 31 first, and W. is serially outputted from the register 31 by storing Wj calculated at that time.

However, in this case, it is necessary to set the line 10a to O. Also, in both WilWj, the original array is swapped (
Arrangements of A8 to a1 and Al4 to A9) will be output. Next, using the AI formula and l formula, the error correction vector P
．． Q has been generated, and the error correction vector P.Q has been generated.
A fifth embodiment of the present invention apparatus for receiving Q will be described with reference to FIG.

Information vectors W1 to Wn that have entered the data bus 32.
P. ．． Q generated by the l formula is supplied to multiplication circuits 33 and 35, respectively, and the multiplication circuit 3
3 from W1 to WO, P, . According to the input of Q, Wi, . By excluding the integration of Wj, the multiplier circuits 33 and 35 calculate each of G1 to Gn. Hl～Hn
The maximum among them is Gmax. Each G as Hnlax
-HTma-X,. Each TO, T1,...
TOmax or TO,. This can be realized by a circuit as shown in FIG. 10 which can multiply Tl, . . . , THmax.

Further, the circuits 34 and 36 can be realized by a circuit as shown in FIG. 1G.

G・−H・(TlSllTlS2) is calculated, and this SO is supplied to a multiplication circuit 38 which multiplies by TN (N is an integer other than O) having a circuit configuration as shown in FIGS. 4 and 10, where Sequential S.

By repeatedly multiplying TN by TN, these m-element column vectors are processed into an inner product calculation circuit (matrix calculation circuit) consisting of an AND circuit and an exclusive OR circuit.
39, where the I. In accordance with the combination of j, an inner product operation is performed between the m-row row matrix of the matrix (Tjl4THj-Hi)-1 selected by the control circuit G.-G.path 41 and the linear/combined m-element row matrix. .

Here, each of 1, . Store all combinations of I. It is controlled by a control circuit 49 that selects a matrix according to j, and a control circuit 50 that sequentially selects and outputs each matrix of m rows (matrix Mkf). , 3 is performed.

Therefore, the storage capacity of the storage device 48 is larger than that of the storage device 40, and moreover, there are many peripheral circuits. 1st again
To explain the embodiment of the present invention shown in FIG. 4, the inner product calculation circuit 3
Vector Wj″ (Wj″−Y−Wj
shall be.

(Y is a matrix with m rows and m columns) for each element Ar.
The serial outputs of aJ, . . . , AM are serial-parallel converted by the shift register 42 shown in FIG.
Wj is obtained. This Wj is subjected to matrix multiplication of TGj-01 by controlling the number of clock pulses by a multiplication circuit 44 as shown in FIG. 4 or FIG.
TlSl(=WiC+)T from G・-G・Road 34
jlWj) to calculate Wi.

The output Wi of the adder circuit 45 and Wj from the linear conversion circuit 43 are applied to a data selector 46, where they are switched and output Wi. Wj are sequentially output. This WilWj is an information vector that is known to be incorrect due to an error pointer, and the W
i,. Wj is obtained. The correction calculation method of the apparatus shown in FIG. 14 is based on the unit matrix 1. TN. T2N, ..., T(m-
1) N is linearly independent, or TN, . T2Nl..., Tm
This is possible if N is linearly independent, but it is also possible in the following case. The multiplication circuit 38 is S. In order to only multiply TN by TN, first S. (or TN-SO
(memory)), the parallel input is turned off and the Φ vector is input, but if you input the Φ vector as it is to the parallel input. is applied, the output of the multiplier circuit 38 becomes.

At this time, the above 1. TN. Similar to the independence conditions such as T2N, etc., if the m matrices of 1C are linearly independent, the correction calculation of the present invention is possible, and in that case, the linear conversion circuit 43 may be changed according to these matrices.

As described above, the double error correction device using error pointers of adjacent codes according to the present invention calculates TLl, TL2, . , m rows m of TLm
When the column matrices are linearly independent of each other, an m-by-m-column matrix (1(1E)Ti-j)-1 used during correction.
Or, define (TOj-014THj-Hi)-1 as Mk (where k-f(1,.j), k takes multiple integer values depending on the combination of I, .j), and the matrix Let Mk be composed of m row matrices of m elements each from Mkl to Mkm, and a plurality of row matrices Mk corresponding to each k generated from Mkl to Mkm according to the same dependency rule.
A storage device that stores d in advance and selectively reads it corresponding to k, and an error vector EjMk (SleT
i-n-1・S2) or EjMk・(T?Gi-S
, lT-Hi-S2), or by the syndromes S1 and S2 obtained by deleting Wi* and Wj* indicated as incorrect by the error pointer, Wj=Mk・(S
l4Ti-n-1-S2) or Wj=Mk・(T-
Gi. SllT2Hi-S2) to correct the column vector S.

(-SllTi-n-1 ・S2 or T-01-Sll
T-HiS2) is supplied, to which TLl, TL2
..., column vector TLl・transformed by multiplying by TLm
SOlTL2・SO,..., TLm-SO, or T
NO・SO, (1(+)TN)・TNO・SO,...
, (11TNeT2Ne-)・TNO・SO, and the row matrix selectively read from the storage device and the output of the multiplication circuit, Mkd-TLl・S
O, LMkd-TL2・SOl..., Mkd-Tm-
SOl or Mkd-TNO・SO,. Mkd・(1(1
T) TN)・TNO・SOl..., Mkd・(IeT
An arithmetic circuit that sequentially performs the operations NeT2Ne-), TNO, and SO to serially output an m-element vector, and an arithmetic circuit that temporarily stores the m-element vector obtained from this arithmetic circuit and stores m rows m.
Since it is configured with a circuit that performs column linear conversion and outputs the result, the data in the above 1. Since it is only necessary to selectively read one row out of a plurality of row matrices formed by combinations of j, the readout control circuit section of this storage device can have a simpler configuration than the conventional one, and the storage device can be Since the number of signals to be read (matrix elements) can be reduced to 1/m, the storage capacity of the storage device can be reduced compared to the conventional method. S by supplying.

Since multiplying by T is repeated (m-1) times, a circuit for multiplying by T and S used for S2 calculation. The circuit that multiplies KT can be shared, and furthermore, with m-14 and n=6, T
is used as the auxiliary matrix of the polynomial 1+X8+Xl4, so when the 8th row of Mk is used, the linear transformation can be performed without using an exclusive OR circuit, which has the advantage of simplifying the circuit configuration. be.

[Brief explanation of the drawing]

1 and 2 are block system diagrams showing examples of conventional devices, respectively. Figure 6, Figure 9, Figure 12
13 and 14 are block system diagrams showing the first to fifth embodiments of the device of the present invention, and FIGS. 7, 8, and 10 show the main parts of the device of the present invention, respectively. A specific circuit diagram showing an embodiment, FIG. 11 is a circuit diagram showing each embodiment of a circuit that can be used in place of the linear conversion circuit of the device of the present invention, and FIG. 15 is a fifth embodiment of the device of the present invention shown in FIG. 14. FIG. 2 is a block system diagram showing an example of a main part of a conventional device corresponding to the example. 1, 32... Input terminal (input data bus), 2
・・・・・・S1 generation circuit, 4, 4″, 24, 24″,
24'', 33, 35, 38, 44... Multiplication circuit, 5... S2 generation circuit, 8, 16, 165, 4
0,48...Storage device, 19,43...
-Linear conversion circuit, 23, arithmetic circuit, 39... inner product arithmetic circuit, 30, 46... data selector.

Claims (1)

[Claims] 1. n information string vectors W_1 to W_n each having m elements on GF2 (a finite field consisting of two elements), and 2 generated from the information vectors W_1 to W_n according to the following equation. Two error correction column vectors {▲ Contains mathematical formulas, chemical formulas, tables, etc. ▼ {▲ Contains mathematical formulas, chemical formulas, tables, etc. ▼ Or ▲ Contains mathematical formulas, chemical formulas, tables, etc. ▼ Or {▲ Contains mathematical formulas, chemical formulas, tables, etc. ▼ {▲There are mathematical formulas, chemical formulas, tables, etc.▼ (However, T is a regular linear transformation matrix with m rows and m columns that is linearly independent of the unit matrix I, ■ is the addition of vectors on GF2) A calculation consisting of P and Q (n+2) vectors as 1
It is transmitted as a block for each block, and has an error pointer that indicates which vector is incorrect at the time of reception.
In an adjacent code correction device that performs correction when errors are detected in two vectors W_i and W_j in a block, regarding the transformation matrix T and the m integers L_1, L_2, ..., L_m constituting the arithmetic progression. T^L^1,
When m matrixes of m rows and m columns of T^L^2, ..., T^(L_m) are linearly independent of each other, the m rows and m columns matrix used for correction ▲ mathematical formulas, chemical formulas, tables, etc. There are ▼ or ▲ there are mathematical formulas, chemical formulas, tables, etc. ▼ is M_k (however, k
= f(i, j), where k takes multiple integer values depending on the combination of i and j), and the matrix M_
Let k be composed of m m-element row matrices M_k_1 to M_k_m, and the row matrices M_k_1 to M_k
a storage device that stores in advance a plurality of row matrices M_k_d corresponding to each k generated from _m according to the same dependency rule and selectively reads out the row matrices M_k_d corresponding to k;
~ Reception vector W_1^ corresponding to W_n, P, and Q respectively
Partial syndrome S_1, S_2 calculated as [▲There are mathematical formulas, chemical formulas, tables, etc.▼] or [▲There are mathematical formulas, chemical formulas, tables, etc.▼] depending on ＊〜W_n^*, P^*, Q^* The error vector E_j=M_k・(S_1■T^i^-^
n^-^1・S_2) or E_j=M_k・(T^
-^G^i・S_1■T^−^H^i・S_2) or W_ that is indicated as incorrect by the error pointer.
By deleting i^* and Wj^* and calculating [▲There are mathematical formulas, chemical formulas, tables, etc.▼] or [▲There are mathematical formulas, chemical formulas, tables, etc.▼] and the partial syndromes S_1 and S_2, W_j=M_k・(S_1■T^i^-^n^-^1・
S_2) or W_j=M_k・(T−＾G＾i・S
_1■T^-^H^i・S_2), the column vector S_0(=S_1■T^i^-^n^-^
1・S_2 or T^-^G^i・S_1■T^-^H^
i・S_2) is supplied, to which T^L^1, T^
Column vectors T^L^1S_0, T^L^2S_0, T^LmS_0 multiplied by L^2, ..., T^L^m
M_k_d・T^L^1・S
_0・M_k_d・T^L^2・S_0,...,M_k_
An arithmetic circuit that sequentially performs operations d・T^L^m・S_0 and serially outputs an m-element vector, and an m-element vector obtained from the arithmetic circuit is temporarily stored and linear conversion of m rows and m columns is performed. 1. A double error correction device using an error pointer of adjacent codes, characterized in that it is composed of an output circuit. 2. n information column vectors W_1 to W_n each having m elements on GF2 (finite field consisting of two elements) and two error correction column vectors [▲ There are mathematical formulas, chemical formulas, tables, etc. ▼ or T・W_1■T^2・W_2■…■T^n・W_n
Or [▲There are mathematical formulas, chemical formulas, tables, etc.▼ (However, T is the polynomial 1+g_1x+g_2x^2+...+g_m_-_1
Auxiliary matrix of X^m^-^1+X^m, ■ is GF2
Addition of the above vectors) A total of (n+2) vectors consisting of P and Q are transmitted in each block as one block, and an error pointer is provided to indicate which vector is incorrect at the time of reception. Vector W_i, W_
In the adjacent code correction device that performs correction when an error in j is detected, the above auxiliary matrices T, T^2, T^3
,..., T^m or m of I, T, T^2, T^m^-^1
When the m-row, m-column matrices are linearly independent of each other, the m-row, m-column matrix (IT^i^
-^j)^-^1 or (T^G^j^-^G^i■T^
H^j^-^H^i)^-^1 is M_k (however, k=f
(i, j), where k takes multiple integer values depending on the combination of i, j), and the matrix M_k is defined as M
The row matrices M_k_1 to M_k_m are composed of m row matrices with m elements each, and a plurality of row matrices M_k_d corresponding to each k generated from the row matrices M_k_1 to M_k_m according to the same dependency rule are stored in advance and are made to correspond to k. and a storage device that is selectively read by W_1 to W_
Reception vectors W_1^*~W corresponding to n, P, and Q, respectively
By ＿n^*, P^*, Q^* [▲mathematical formula, chemical formula,
There are tables, etc.▼] or [▲There are mathematical formulas, chemical formulas, tables, etc.▼] According to the partial syndromes S_1 and S_2 calculated, the error vector E_j=M_k・(S_1■T＾i＾−＾
n^-^1・S_2) or E_j=M_k・(T^
-^G^i・S_1■T^−^H^i・S_2) or W_ that is indicated as incorrect by the error pointer.
W_j= by deleting i^* and W_j^* and calculating [▲There are mathematical formulas, chemical formulas, tables, etc.▼] or [▲There are mathematical formulas, chemical formulas, tables, etc.▼] and the partial syndromes S_1 and S_2. M_k・(S_1■T^i^-^n^-^1・
S2) or ▲There are mathematical formulas, chemical formulas, tables, etc.▼ In order to correct the column vector S_0(=S_1■
T^i^-^n^-^1・S_2 or ▲mathematical formula, chemical formula,
A column vector T・S_0 is supplied which is converted by repeatedly multiplying it by T.
, T^2・S_0, ..., T^m・S_0, or S_
A circuit that sequentially calculates and outputs 0, T・S_0, ..., T^m^-^1・S_0, a row matrix selectively read from the storage device, and the output (column vector) of the circuit.
Toyo M_k_d・T・S_0, M_k_d・T^2・
S_0,..., M_k_d・T^m・S_0, or M
＿k_d・S_0, M_k_d・T・S_0,...
an arithmetic circuit that sequentially performs operations M_k_d, T^m^-^1, and S_0 and serially outputs an m-element vector;
A double error correction device using an error pointer of adjacent codes, comprising a circuit that temporarily stores an m-element vector obtained from the arithmetic circuit, performs m-row, m-column linear transformation, and outputs the result. 3 The information vectors W_1 to W_n each have 14 elements (=
m) is composed of 6 pieces (=n), and the auxiliary matrix T is an auxiliary matrix of the polynomial 1+x^8+x^1^4 of adjacent codes according to claim 2. Double error correction device using error pointer.