JPS638650B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Technical Field of the Invention] The present invention relates to an improvement in an error correction circuit suitable for, for example, an optical digital audio disk (DAD) playback device.

[Technical background of the invention]

As is well known, the recently developed optical method
Cross-interleaved Reed-Solomon code (CIRC) is used as an error correction code for DAD playback devices (particularly CD (compact disk type)).
is adopted.

In other words, it is broadly defined as having the highest error correction ability among the typical random error correction codes known to date.
It uses a Reed-Solomon code, which is a type of BCH code, but it is also accompanied by signal processing called cross-interleaving in order to have a high correction ability even for burst errors.

By the way, decoding, that is, error correction of the Reed-Solomon code can be performed in the same way as that of the BCH code.

Let us now examine the decoding method for a Reed-Solomon code consisting of a code length (n), information symbols (k), and check symbols (nk). However, each symbol above is a Galois field, which is a finite field having (m) binary bits, that is, 2 ^m elements.
It is the source of GF (2 ^m ).

In this case, the generating polynomial g(x) of the (t) multiple error correction Reed-Solomon code is expressed as the following equation (1) or (2), where (α) is a primitive element of the Galois field GF(2 ^m ). is expressed in

g(x)=(x+α)(x+α ² )……(x+α ^2t )
…(1) g(x)=(x+α ⁰ )(x+α)…(x+α ^2t-1
)
...(2) Also, if the transmitted codeword is represented by C _(x) , the received codeword is represented by R _(x) , and the error polynomial is E _(x) , the following relationship holds between them. .

R _(x) = C _(x) + E _(x) …(3) In this case, the coefficients of the polynomial are contained in the Galois field GF (2 ^m ), and the error polynomial E _(x) is defined by the error location and value ( contains only the terms corresponding to the magnitude).

Therefore, if the error value at position x ^j is Y _j , E(x) = 〓 ^j Y _j x ^j ...(4), and in equation (4), Σ means the sum of errors over all positions. There is.

Here, the syndrome S _i is S _i =R(α ⁱ ) [however, i=0, 1...2t-1]
...If defined as in (5), then S _i =C(α ⁱ )+E(α ⁱ ) from equation (3) above.

In this case, since C _(x) is always divisible by g _(x) , C (α ⁱ ) = 0, so S _i = E (α ⁱ ). Therefore, from equation (4) above,
It can be expressed as S _i = ^E (α ⁱ )=〓 j _{Y j} (α ⁱ ) ^j =〓 ^j Y _j X ⁱ _j (6). However, α ^j =X _j , where X _j represents the error location at α ^j .

Here, the error location polynomial σ _(x) is calculated as follows, where the number of errors is e: σ (x) = 〓 ⁱ (x−X _i ) = x ^e + σ ₁ x ^e-1 +……+σ _e …(7) defined.

Moreover, σ ₁ to σ _e in equation (7) are related to syndrome S _i as follows.

S _i+e +σ ₁ S _i+e-1 + ...σ _e-1 S _i+1 +σ _e S _i ...(8) In other words, the decoding procedure for the Reed-Solomon code as described above is () (5) The syndrome S _i is calculated by:

() Calculate the coefficients σ ₁ to σ _e of the error location polynomial using equation (8).

() Find the root X _j of the error location polynomial using equation (7).

() Find the error value Y _j using equation (6), and find the error polynomial using equation (4).

() Error correction is performed using equation (3).

This results in the steps () to ().

Next, as a specific example of error correction using the above decoding procedure, a case will be described in which four check symbols are used for one block of data.

In other words, the generator polynomial g _(x) in this case is g _(x) = (x + 1) (x + α) (x + α ² ) (x + α ³ ), and it is possible to correct up to double errors, but here We will discuss the two methods [A] and [B] separately.

[Method A]

() Calculate syndromes S ₀ to S ₃ .

() Rewriting equation (8) for e=1 and e=2, in the case of e=1, S ₁ +σ ₁ S ₀ =0 S ₂ +σ ₁ S ₁ =0 S ₃ +σ ₁ S ₂ =0 ( 9) becomes. Also, in the case of e=2
S ₂ +σ ₁ S ₁ +σ ₂ S ₀ =0 S ₃ +σ ₁ S ₂ +σ ₂ S ₁ =0 (10).

Here, assuming that the actual decoder starts its operation from the case where e=1, it is first necessary to find a solution σ ₁ that satisfies the simultaneous equations (9). Then, if this solution does not exist, the decoder then e
In the case of =2, solutions σ ₁ and σ ₂ that satisfy simultaneous equations (10) must be found. Note that if no solution is obtained here, it is assumed that e≧3.

The solution σ ₁ of equation (9) is obtained as σ ₁ =S ₁ /S ₀ =S ₂ /S ₁ =S ₃ /S ₂ , and the solutions σ ₁ and σ ₂ of equation (10) are obtained as σ ₁ =S ₀ S ₃ +S ₁ S ₂ /S ₁ ² +S ₀ S ₂ , σ ₂ =S ₁ S ₃ +S ₂ ² /S ₁ ² +S ₀ S ₂ .

() Once the coefficient σ ₁ of the error location polynomial has been obtained as described above, the roots of the error location polynomial are then determined using equation (7).

First, when e=1, σ _(x) =x+σ ₁ =0, ∴X ₁ =σ ₁ . In addition, in the case of e=2, σ _(x) = x ² + σ _1x + σ ₂ = 0 ...(11), and by sequentially substituting the elements of the Galois field GF (2 ^m ) into equation (11), All you have to do is find the solution, and now find this root.
Let X ₁ and X ₂ be.

() Once the roots of the error location polynomial have been found, the error value Y _j is then found using equation (6).

First, when e=1, S ₀ =Y ₁ ∴Y ₁ =S ₀ . In _addition , in the case of e=2, S ₀ = Y ₁ + Y ₂ S ₁ = Y ₁ X ₁ + Y ₂ X ₂ , _{∴Y 1} = X ₂ S ₀ + S ₁ / _{X 1 +} ) The error value Y ₁ obtained as above,
Correct by Y ₂ .

By the way, if the value of the error location can be accurately known using the pointer erasure method or the like, it is possible to correct up to quadruple errors using the above-mentioned Reed-Solomon code for double error correction. This is [Method B], which will be described later.

[Method B]

() Calculate syndromes S ₀ to S ₃ .

(), () Find out the error location using another detection method.

() Calculate the error value using equation (6).

First, in the case of e=1 and e=2, it is the same as () of the above-mentioned [method A].

Then, in the case of e=3, S ₀ =Y ₁ +Y ₂ +Y ₃ S ₁ =Y ₁ X _{1 +} Y ₂ X ₃ + ^Y ₃ X ₃ S ₂ = _{Y 1 X 1 2} ^{+ Y} ₂ Solve Y ₁ =(S ₂ +X ₃ S ₁ )+X ₂ (S ₁ +X ₃ S ₀ )/(X ₁ +X ₂ )(
_{X 1} + X ₃ ) Y ₂ = (S ₁ + X ₃ S _{0 )} + Y ₁ ( _{X 1} + _{X 3 )} /(X _{2 +}

Also, in the case of e=4, S ₀ =Y ₁ +Y ₂ +Y ₃ +Y ₄ S ₁ =Y ₁ X ₁ +Y ₂ X ₂ +Y _{3 X 3} +Y _{4 X 4} ^S ₂ = _{Y 1} ² +Y ₃ ^X ₃ ² ₊ ^Y ₄ X ₄ ² _{S 3} =Y ₁ X ₁ ³ _{+ Y 2 X 2} ³ _{+ Y 3 3} + (S ₁ X ₄ + S ₂ )}X ₂ + (S ₁ X ₄
+S ₂ )X ₃ +(S ₂ X ₄ +S ₃ )/(X ₁ +X ₂ )(X ₁ +X ₃ )(X ₁ +
X ₄ ) Y ₂ = (S ₀ X ₄ + S ₁ ) X ₃ + (S ₁ X ₄ + S ₂ ) + Y ₁ (X ₁ + X ₃ )
_{( X 1} +X ₄ )/ ₍ X ₂ +X ₃ ) (X ₂ + _{X 4} ) _{Y 3 = ( S 0}
(X ₃ +X ₄ ) Y ₄ =S ₀ +Y ₁ +Y ₂ +Y ₃ .

() Correction is made using Y ₁ to _{Y 4} obtained as described above.

FIG. 1 is a schematic configuration diagram showing an error correction circuit which is an actual Reed-Solomon code decoding system based on the above principle. That is, the data to be corrected (of course Reed-Solomon code is used for error correction) led through the input terminal (IN) is divided into two parts, one of which is used as a data buffer during the decoding operation described later. 11, and the other one is led to the syndrome calculator 12 and below for decoding operations.

The syndrome calculated by the syndrome calculator 12 is stored in the syndrome buffer 13.

Here, the OR gate 14 connected to the output part of the syndrome buffer 13 indicates the presence or absence of an error, and if there is an error, an error correction operation is started according to the procedure described above.

In other words, the error location polynomial calculator 15
calculates the coefficients of the error location polynomial σ _(x) ,
An error location calculator 16 calculates the root of the error location polynomial, an error value calculator 17 calculates an error value, and corrects the data output from the data buffer 11 using these error locations and error values. It is.

By the way, each of the calculators 12, 15, 16, and 17 of such a decoding system detects whether or not it is 0 and performs necessary algebraic operations such as addition, multiplication, and division. Conventionally, an error location polynomial calculator (Japanese Patent Publication No. 56-20575) constructed as shown in FIG. 2 is known.

That is, in FIG. 2, 21 is a syndrome buffer, which is a RAM for storing the syndrome S _i .
Each syndrome, which is an element of the Galois field GF (2 ^m ), is stored in m-bit binary format.

Further, 22 is a work buffer, which is used to store intermediate results and final results of algebraic operations when calculating the coefficients of the error location polynomial.
Partial results used in later calculations are also stored in the working buffer 22.

23 is a sequence control device for instructing the order of algebraic operations, and the syndrome buffer 2
1 and working buffer 22 to access appropriate storage locations;
It is used to check the result of the algebraic operation executed and branch to the next appropriate operation.

Furthermore, 24 and 25 are each Galois field GF
These are a logarithm buffer and an antilog buffer consisting of ROMs that store the original logarithm and antilog of (2 ^m ) separately in the form of tables.

Here, the address of the former logarithm buffer 24 is the binary representation of the element α ⁱ , and its entry is the logarithm of α with α as the base, that is, i, but the entry at the address i of the latter logarithm buffer 25 is This is the binary representation of α ⁱ .

For example, if the modulus polynomial F _(x) of the Galois field GF (2 ⁸ ) is F _(x) = x ⁸ + x ⁶ + x ⁵ + x ⁴ + 1, the elements other than 0 are the powers of the root α of F _(x) = 0. or a linear combination from α ⁰ to α ⁷
₇ 〓 ⁱ⁼⁰ a _i α ⁱ (however, a _i =0 or 1).

Furthermore, in this case, eight coefficients from a ₀ to a ₇ can be extracted and expressed as a binary vector.

For example, α ¹ =0・α ⁰ +1・α ¹ +0・α ² +0・α ³ +0・α ⁴ +0・α ⁵ +0・α ⁶ +0・α ⁷ = (01000000) α ⁷ =0・α ⁰ +…… +0・α ⁶ +1・α ⁷ = (00000001) α ⁸ = 1 + α ⁴ + α ⁵ + α ⁶ = (10001110) α ⁹ = α・α ⁸ = α+α ⁵ + α ⁶ + α ⁷ = (01000111) The element of can also be represented as a vector in the same way.

In this case, the address of the logarithm table (1
~255) is the 8-bit binary vector representation of element α ⁱ , and the corresponding entry is the binary representation of index i.

Further, the antilog table uses the index i as an address, and the entry is a binary vector representation of α ⁱ .

Next, the actual algebraic operations performed by the error location polynomial calculator shown in FIG. 2 will be explained separately.

(1) Addition When elements α ⁱ and α ^j are added, these two elements are subjected to an exclusive OR gate 27 via the A register 20 and the B register 26 for each bit. The result of the sum of the two elements thus obtained is transferred to the working buffer 22 via the C register 19.

(2) Detection of whether or not element α ⁱ is 0 When checking whether element α i is 0, element α ⁱ
are logically summed by the OR gate 29 via the H register 28. This result is transferred to the working buffer 22 via the M register 30. In this case, the contents of the M register 30 become 0 only when the element α ⁱ is 0.

(3) Multiplication When multiplying elements α ⁱ and α ^j , first it is checked whether these two elements are 0 or not. If,
If either element is 0, the multiplication result is 0 without actually needing to be multiplied. However, if both are non-zero, these elements are sequentially loaded into the address register 31 for the logarithmic buffer 24. Then, the outputs i and j from the logarithm buffer 24 are converted to 2 ⁸ −
One's complement addition is performed modulo one. The result i+j=tmod(2 ⁸ -1) obtained by this is L
It is loaded via the register 35 into the address register 36 for the antilog buffer 25. In this case, if the address input of the antilog buffer 25 is t, the output α ^t is the multiplication result of the G register 37.
The data is transferred to the work buffer 22 via the.

(4) Division The division of α ⁱ by the element α ^j (α ⁱ /α ^j ) is basically the same as the multiplication in (3) above, but the contents of the E register 33 are transferred to the D register 32. They differ in that they are subtracted from the content. That is, the logarithm of element α ^j in the E register 33 is complemented by the complement converter 38 and sent to the one's complement adder 34 via the F register 39. and,
The following processing is performed in the same manner as in the case of multiplication (3), but in this case, the output of the antilog buffer 25 is the result of the division, that is, the quotient.

[Problems with background technology]

However, the conventional error correction circuits described above require logarithm buffers and antilog buffers for multiplication and division among the algebraic operations in the error location polynomial calculator. Since the memory capacity of ROM etc. becomes enormous, it hinders the conversion to LSI and creates the problem that large capacity memory must be externally attached.

This is 255 x 8 bits = 2040 bits when one symbol is 8 bits as in the example above.
This can be easily seen from the fact that two ROMs are required, totaling 4080 bits.

In other words, conventionally known multipliers and dividers in Galois fields require logarithm buffers and antilog buffers consisting of large-capacity memories that store the logarithms and antilogarithms of these elements separately in the form of tables. Therefore, there was a problem in that the configuration of the entire error correction circuit became complicated and expensive.

[Purpose of the invention]

Therefore, this invention was made in view of the above points, and it is possible to perform multiplication in the Galois field without using logarithm buffers or antilog buffers that require a large amount of memory, especially in the error location polynomial calculator section. It is an object of the present invention to provide an extremely good error correction circuit that can perform division and thus contribute to simplifying the configuration and lowering the cost.

[Summary of the invention]

That is, the error correction circuit according to the present invention is
By taking advantage of the fact that the multiplication device in the Galois field required for the error location polynomial calculator section can be constructed relatively easily using a linear shift register, division in the Galois field can be converted into multiplication processing. It is characterized in that the process of converting division into multiplication can be realized in as short a time as possible.

That is, in an error correction circuit that calculates an error location and an error value for error correction using an error location polynomial calculator based on a syndrome generated from a Reed-Solomon code to be corrected expressed in a Galois field, A multiplication device configured using a linear shift register that performs multiplication processing in the Galois field necessary for the error location polynomial calculator section, and a division processing α in the Galois field that is necessary for the error location polynomial calculator section. ⁱ ÷ α ^j is multiplied by α ⁱ ×α ^M (where α ^j
×
α ^M = 1), and is equipped with a division device configured using a two-system linear shift register group that multiplies the dividend and divisor in advance by α ^N (where N<M). This is an error correction circuit characterized by:

[Embodiments of the invention]

First, the optical type (CD type) to which this invention is applied
An overview of a digital audio disc (DAD) playback device will be explained.

That is, as shown in FIG. 3, the turntable 1 is rotated by a disk motor 111.
A disk 113 mounted on the optical pickup 112 is played back by an optical pickup 114. in this case,
The optical pickup 114 is a semiconductor laser 114.
A beam splitter 114b transmits the light emitted from the
It illuminates the signal surface of the disk 113 through the objective lens 114c, and corresponds to the digitized (PCM) data of the audio signal to be reproduced that is recorded on the disk 113 in a form with predetermined (EFM) modulation and interleaving. The reflected light from the pits (irregularities with different reflectances) is reflected by the objective lens 11.
4c, 4 through beam splitter 114b
The four reproduced signals are led to a divided photodetector 114d and photoelectrically converted by the four-divided photodetector 114d, and can be outputted to the outside.
The disk 113 is then linearly driven in the radial direction of the disk 113 by a pick-up feed motor 115.

The four reproduced signals from the four-division photodetector 114d are then supplied to the matrix circuit 116 and subjected to predetermined matrix calculation processing, thereby generating a focus error signal (F), a tracking error signal, and a high frequency signal (RF). separated into

Of these, the focus error signal F is used together with the focus search signal from the focus search circuit 110 to drive the focus servo system (FS) of the optical pickup 114.

Further, the tracking error signal (T) is used to drive the tracking servo system (TS) of the optical pickup 114 and the pickup feed motor 115 together with a search control signal given via the system controller 117 (described later).
(linear tracking).

The remaining high frequency signal RF is then supplied to the reproduction signal processing system 118 as the main reproduction signal component. That is, this reproduced signal processing system 118 first passes the reproduced signal to a slice level (eye pattern) detector 119.
The signal is guided to a waveform shaping circuit 120 controlled by a PLL type synchronous clock regeneration circuit 121 and a first signal processing system 12 to separate unnecessary analog components and necessary data components.
2 edge detector 122a.

Here, the synchronous clock from the synchronous clock regeneration circuit 121 is guided to the synchronous signal separation clock generation circuit 122b in the first signal processing system 122 for data demodulation, and is used to generate a synchronous signal separation clock. .

On the other hand, the reproduced signal that has passed through the edge detector 122a is guided to a sync signal detector 122c, where the sync signal is separated by the sync signal separation clock, and is also guided to a demodulation circuit 122d where it is EFM demodulated.

Among these, the synchronization signal is transmitted to the synchronization signal protection circuit 122.
The signal is guided to the input data processing timing signal generation circuit 122f together with the synchronization signal separation clock through the signal line e in a state where it is protected from malfunction.

Also, the demodulated signal is transmitted to the data bus input/output control circuit 1.
A second signal processing system 123 to be described later via 22g
is supplied to the input/output control circuit 123a of
The control signal and display signal components, which are subcodes, are sent to the control display processing circuit 1.
22h and subcode processing circuit 122i.

The subcode data subjected to necessary error detection and correction by the subcode processing circuit 122i is sent to the system controller 117 via the system controller interface circuit 122q.
supplied to

Here, the system controller 117 includes a microcomputer, an interface circuit, a driver integrated circuit, etc., and controls the DAD playback device to a desired state by command signals from the control switch 124, and also controls the above-mentioned subcode ( For example, the display 125 is used to display the index information of the played music on the display 125.

The timing signal from the input data processing timing signal generation circuit 122f is provided to control the data bus input/output control circuit 122g via the data selection circuit 122j, and is also used to control the data bus input/output control circuit 122g. 1
22l and a PWM modulator 122m for automatic frequency control AFC and automatic phase control APC for driving the disk motor 111 in a constant linear velocity CLV method.

In this case, the phase detector 122l is supplied with a system clock from a system clock generation circuit 122p which operates based on an oscillation signal from a crystal oscillator 122n.

The demodulated data passing through the input/output control circuit 123a of the second signal processing circuit 123 is sent to the syndrome detector 1 for error detection and correction or correction.
23b, an error pointer control circuit 123c, a correction circuit 123d, and a data output circuit 123e.
A) Derived to converter 126.

In this case, the external memory control circuit 123f cooperates with the data selection circuit 122j to select the external memory 127 in which data necessary for correction is written.
By controlling the above input/output control circuit 12
3a, data necessary for correction is taken in.

Further, the timing control circuit 123g is configured to supply timing control signals necessary for error correction and correction and D/A conversion based on the system clock from the system clock generation circuit 122p.

Additionally, the mutating (detection) control circuit 123
h performs predetermined muting control necessary for error correction and for starting and ending the operation of the DAD playback device, based on the output from the error pointer control circuit 123c or the control signal given via the system controller 117. It is offered to

Then, the audio signal converted back to an analog signal by the D/A converter 126 is passed through a low-pass filter 128 and an amplifier 129, and then sent to the speaker 130 for sound.

Next, an embodiment of the error correction circuit according to the present invention applied to the DAD playback device as described above will be described in detail with reference to the drawings.

That is, FIG. 4 shows the above-mentioned error location polynomial calculator section mainly included in the correction circuit 123d of the second signal processing circuit 123 in FIG. A multiplication device 41 that allows multiplication and division in a Galois field without using
It is the same as that of FIG. 2 described above except that it includes a dividing device 42 and a dividing device 42. In other words, the role of the error location polynomial calculator is to perform various algebraic operations for decoding (error correction) the Reed-Solomon code, which is a type of BCH code used as an error correction code. Of these, addition and detection of whether or not it is 0 are explained in the second section.
Since they are performed in the same way as those in the figure, the same reference numerals are given and the explanation thereof will be omitted. Multiplication and division that are different from those in FIG. 2 will be described below.

First, let's look at multiplication in a Galois field. For example, the multiplication of the elements α ⁱ and α ^j of the Galois field GF (2 ⁸ ) (α ⁱ · α ^j , where α is the modulus polynomial F _(x) = X ⁸ + X ⁶ ＋X ⁵ ＋
^{The root} _{of _ _} ^{_ _} _{_ _ _} ^_ (However, C ₀ to C ₇ and d ₀ to d ₇ are 0 or 1) α ⁱ・α ^j =C(α)・D(α)=d ₇ α ⁷ C(α)+d ₆ α
⁶ C (α)……d ₀ C (α) = α ⁶ [αd ₇ C (α) + d ₆ C (α)] + d ₅ α ⁵ C (α) +
...+d ₀ C (α) = α ⁵ [α [αd ₇ C (α) + d ₆ C (α)] + d ₅ C (α)]
＋d ₄ α ⁴ C(α)＋……＋d ₀ C(α) 〓 =[α〔α〔α〔α〔α〔α〔αd ₇ C(α)＋d ₆ C(α
)〕＋d ₅ C(α)〕＋d ₄ C(α)〕＋d ₃ C(α)〕＋d ₂ C(α)〕＋d ₁ C(α)＋d ₀ C(α)
] becomes.

In other words, the story shows that such multiplication of the elements α ⁱ and α ^j of the Galois field GF(2 ⁸ ) can be realized by the multiplier 41 configured as shown in FIG. 5 using a linear shift register. It's on.

That is, in FIG. 5, AND ₀ to AND ₇ are serially supplied with coefficients d ₀ to _{d 7} of the multiplier D (α) in order from the upper bit to one end of each, and
At each other end are coefficients of the multiplicand C(α), C ₀ to _{C 7}
is an AND gate in which the bits are supplied in parallel in order from the most significant bits. Furthermore, FF ₀ to FF ₇ are exclusive OR gates to which the output from each of the AND gates AND ₀ to AND ₇ is supplied correspondingly to one input end.
These flip-flop circuits are connected in cascade via EX-OR ₀ to EX-OR ₇ and are also connected in feedback to form a linear shift register SR ₀ .

In this case, the flip-flop circuits FF ₃ in the 4th and 5th stages, the 5th and 6th stages, and the 6th and 7th stages are
- FF ₄ , FF ₄ - FF ₅ , FF ₅ - Between the stages of FF ₇ , there is an exclusive OR gate with each end connected to the return path.
EX-OR ₄ ′, EX-OR ₅ ′, and EX-OR ₆ ′ are further inserted and combined. Further, a clock pulse CP from a clock generator (not shown) is supplied in parallel to the clock input terminal CK of each of the flip-flop circuits FF ₀ to _{FF 7} .

In other words, by inputting the coefficients C ₀ to _{C 7} of C(α) in bit serial format, X ₀ is first calculated,
After that, X ₁ , X _{2 ,} and so on, and when the 8-bit input ends _{, X 7 ,} that is, C
(α)·D(α) is realized, and the outputs x ₀ , x _{1 .} . . x ₇ of each flip-flop circuit FF ₀ to FF ₇ give the multiplication result.

Here, X ₀ to X ₇ are as follows.

X ₀ = d ₇ C (α) X ₁ = αX ₀ + d ₆ C (α) X ₂ = αX ₁ + d ₅ C (α) X ₃ = αX ₂ + d ₄ C (α) X ₄ = αX ₃ + d ₃ C (α) X ₅ = _{αX 4} + d _{2 C (} α) X ₆ = αX _{5 +} d ₁ C _{( α} ) , looking at division in a Galois field, for example, division of elements α ⁱ and α ^j of Galois field GF(2 ⁸ ) α ⁱ ÷ α ^j (where α is the modulus polynomial F _(x) = x ⁸ + x ⁶ + x ⁵ ＋x ⁴ ＋
1 root) is equivalent to α ⁱ ÷ α ^j = (α ⁱ・α ^M ) ÷ (α ^j・α ^M ) (where M is an integer) In this case, α ^j・α ^M = α ²⁵⁵ If = α ⁰ = 1, then α ⁱ ÷ α ^j = α ⁱ・α ^M.

In other words, when performing division (α ⁱ ÷ α ^j ) between elements α ⁱ and α ^j of the Galois field GF(2 ⁸ ), in the process of multiplying the dividend α ⁱ and the divisor α ^j by α several times, If α ^j・α ^M = 1 when multiplied by α M times, then α ⁱ・α ^M , which is the product of the dividend α ⁱ and α ^M , is the result of division. By using , the desired division can be performed in the multiplication process.

Here, it goes without saying that the multiplication process is performed using the multiplication device 41 using a linear shift register as described above.

By the way, in this case, the number of times of multiplication by α required to obtain α ^j・α ^M = α ²⁵⁵ = α ⁰ = 1 is the divisor α ^j =
When α is ¹ , the maximum number of times is 254 (that is, M = 254), but if this were simply done, the time required for the multiplication process would become unnecessarily long, which is not preferable.

Therefore, in this invention, the dividend α ⁱ and the divisor α ^j are multiplied by α an appropriate number N times in advance, thereby reducing the number of times actually required for multiplication by α and speeding up the multiplication process (and by extension, The purpose of this is to make it possible to perform division processing (division processing).

FIG. 6 shows a specific example of the division device 42 that realizes division in the Galois field by multiplication processing as described above. In this case, the above-mentioned N is N ₁ =64,
N ₂ = 128, N ₃ = 192, that is, α ⁶⁴ , α ¹²⁸ , and α ¹⁹² are multiplied in advance.

That is, the divisor α ^j data is directly transmitted or transmitted through the α ⁶⁴ multiplication circuit 51, α ¹²⁸ multiplication circuit 52, and α ¹⁹² multiplication circuit 5.
3 through linear shift registers A ₁ , A ₂ , A ₃ , A ₄
is set to Here, the linear shift register
A ₁ , A ₂ , A ₃ , and A ₄ are constructed in the same way as the linear shift register _{SR 0} shown in _FIG . It will be multiplied by α for each shift.

1 detection circuits 54, 55, 56, which are supplied with the outputs of the shift registers _A1 , _A2 , _A3 , _A4 ,
57 is designed to produce a 1 detection output when the contents of the register become (10000000)=1. The 4-input NOR gate NOR ₁₀ to which each output of the 1 detection circuits 54, 55, 56, and 57 is supplied is as follows:
When any of the 1 detection outputs occurs, the output becomes "0" and the passage of the clock pulse _Cp is changed from the permissible state to the prohibited state through the AND gate _AND10 . It's in control.

In addition, the dividend α ⁱ data is also transferred directly or via the α ⁶⁴ multiplication circuit 58, α ¹²⁸ multiplication circuit 59, and α ¹⁹² multiplication circuit 60 to ^the linear shift registers B ₁ , B ₂ , B ₃ , B as well as the divisor α j data. After being set to ₄ , α is multiplied by the clock pulse C _p a suitable number of times.

Here, each output of the shift registers B ₁ , B ₂ , B ₃ , B ₄ corresponds to each output from the above-mentioned 1 detection circuits 54 , 55 , 56 , 57 and the AND circuits 61 , 62 , 6 .
3,64, an AND is taken.

Then, by passing each output of the AND circuits 61, 62, 63, and 64 to the OR circuit 65, a division result of α ⁱ ÷ α ^j can be obtained.

FIG. 7 shows a specific example of the 1 detection circuits 54 to 57 in the above, and shows the linear shift registers A ₁ to 57.
It is composed of an 8-input NOR gate NOR ₁₁ in which only the output corresponding to α ¹ from each output from A ₄ is applied via an inverter I ₁₀ , and the outputs corresponding to other α ² to ^{α 7} are directly applied. This is the case.

FIG. 8 shows a specific example of the AND circuits 61 to 64 described above, in which each input terminal is supplied with each output from the linear shift registers B ₁ to B ₄ correspondingly, and each input terminal is supplied with one terminal at the other end. This is a case where the outputs of the detection circuits 54 to 57 are constructed of eight two-input AND gates _AND20 to _AND27 , which are respectively supplied in common.

FIG. 9 shows a specific example of the OR circuit 65 described above, which includes eight 4-input OR gates to which each output of the AND circuits 61 to 64 is supplied correspondingly.
This is a case where it is composed of OR ₂₀ to OR ₂₇ .

FIG. 10 shows a specific example of the above α ⁶⁴ multiplier circuit 58, in which case α ^j is expressed as α ^j =B(α) =b ₇ α ⁷ +b ₆ α ⁶ +...b ₁ α+b ₀ It is based on the following principle (however, b ₁ to b ₇ are 0 or 1).

In other words, α ⁶⁴ = α ⁷ + α ⁶ + α ⁵ , so α ⁶⁴・B(α) = (α ⁷ + α ⁶ + α ⁵ ) (b ₇ α ⁷ +……+
b ₁ α + b ₀ ) = (b ₀ + b ₁ + b ₅ + b ₇ ) α ⁷ + (b ₀ + b ₄ + b ₆ ) α ⁶ + (b ₀
+b ₁ +b ₃ ) α ⁵ + (b ₁ + b ₂ + b ₅ ) α ⁴ + (b ₄ + b ₅ ) α ³ + (b ₃ + b ₄ ) α ² + (b ₂ + b ₃ + b ₇ ) α
+(b ₁ +b ₂ +b ₆ ). In other words, such an operation is performed using the exclusive or group EX―OR ₁₁ ~ as shown in Figure 10.
It is realized by EX-OR ₂₅ , and if B(α) is input, a multiplication output of α ⁶⁴ ·B(α) can be obtained.

Note that the α ¹²⁸ multiplication circuit 59 and the α ¹⁹² multiplication circuit 60 can also be easily configured in accordance with the α ⁶⁴ multiplication circuit 58 described above.

Next, in the specific example of Figure 6, α ²⁰⁰ ÷ α ¹⁸⁰ = α ²⁰
We will explain the case when executing.

In this case, shift registers A ₁ to A ₄ , B ₁ to B ₄
is set as follows.

A ₁ : α ¹⁸⁰ A ₂ : α ¹⁸⁰ . α ⁶⁴ = α ²⁴⁴ A ₃ : α ¹⁸⁰ . α ¹²⁸ = α ³⁰⁸ = α ⁵³ A ₄ : α ¹⁸⁰ . α ¹⁹² = α ³⁷² = α ¹¹⁷ B ₁ : α ²⁰⁰ B ₂ : α ²⁰⁰ . α ⁶⁴ = α ²⁶⁴ = α ⁹ B ₃ : α ²⁰⁰ . α ¹²⁸ = α ³²⁸ = α ⁷³ B ₄ : α ²⁰⁰ . α ¹⁹² = α ³⁰² = α ¹³⁷ And 11 clock pulses C _p In this state, the contents of shift register A ₂ become α ²⁵⁵ =1, and when this is detected by 1 detection circuit 55, the supply of clock pulse C _p is stopped.

At this time, the content of shift register B ₂ is α ²⁰ , and the output α ²⁰ is outputted via AND circuit 62 and OR circuit 65 .

In this way, according to the specific example shown in Figure 6, the desired division can be performed by multiplication while reducing the number of times α is multiplied to at most 63 times (when α ^j = α ¹ ). .

In this case, by increasing the number of linear shift register pairs, the number of times of multiplication by α can be reduced.

FIG. 11 shows another specific example of a division device that realizes division in a Galois field by multiplication processing as described above. In this case, the above N is N ₁ =1, N ₂
=2, N ₃ =3, that is, α ¹ , α ² , α ³ are multiplied in advance, and N ₀ =4, that is, α ⁴ is multiplied every time.

That is, the divisor α ^j data is directly transmitted or transmitted through the α ¹ multiplication circuit 51′, α ² multiplication circuit 52′, and α ³ multiplication circuit 53′.
are set to linear shift registers A ₁ ′, A ₂ ′, A ₃ ′, and A ₄ ′ that constitute the α ⁴ multiplier circuit.

Here, linear shift registers A ₁ ′, A ₂ ′, A ₃ ′,
_A4 ' is the flip-flop circuit _FF10 to _FF17 connected to the exclusive OR gate EX- as shown in Figure 12.
It is configured by appropriately connecting cascade and feedback via OR' ₁₀ to EX-OR' ₃₁ , and is an AND gate.
It is shifted by a clock pulse C _p applied via AND ₁₀ , and has an α ⁴ multiplication function such that it is multiplied by α ⁴ every shift.

1 detection circuits 54', 55', 5 to which respective outputs of shift registers _A1 ', _A2 ', _A3 ', and _A4 ' are supplied;
6' and 57' are inverters as shown in Figure 12.
It is composed of I ₁₀ and 8-input NOR gate NOR ₁₀ , and the contents of the register are (10000000) =
When the signal becomes 1, a 1 detection output is generated. These 1 detection circuits 54', 55', 56',
4-input NOR gate supplied with each output of 57'
NOR ₁₁ generates a clock pulse C _p through the AND gate AND ₁₀ when the output becomes "0" when any of the 1 detection outputs occurs.
It is controlled so that the passage of the vehicle is changed from the previously permitted state to the prohibited state.

Similarly to ^the divisor α ^j data, ^the dividend α ⁱ data can also be converted to α ⁴ as ^shown in FIG. After being set in the linear shift registers B ₁ ', B ₂ ', B ₃ ', and B ₄ ' constituting the multiplication circuit, the clock pulse C _p is multiplied by α ⁴ an appropriate number of times.

Here, each output of the shift registers B ₁ ′, B ₂ ′, B ₃ ′, B ₄ ′ is sent to the first detection circuit 54 ′, 55 ′, 56 ′,
AND circuits 61', 62', 63', configured as shown in FIG. 8 corresponding to each output from 57'.
64' causes an AND to be taken.

And AND circuits 61', 62', 63', 6
By passing each output of 4' through an OR circuit 65 configured as shown in FIG. 9, a division result of α ⁱ ÷ α ^j can be obtained.

FIG. 13 shows a specific example of the α ¹ multiplication circuit 58' in the above case, where α ^j is expressed as α ^j =B(α) =b ₇ α ⁷ +b ₆ α ⁶ +...+b ₁ α+b _0. It is based on the following principle. In other words, α・B(α) is α・B(α)=b ₇ α ⁸ +b ₆ α ⁷ +……+b ₁ α ² +b ₀ α=b
₆ α ⁷ + (b ₅ + b ₇ ) α ⁶ + (b ₄ + b ₇ ) α ⁵ + (b ₃ + b ₇ ) α ⁴ + b ₂ α ³ + b ₁ α ² + b ₀
α, so it is realized using exclusive OR EX-OR ₃₂ ~ EX-OR ₃₄ as shown in Figure 13,
If B(α) is input, a multiplication output of α·B(α) can be obtained.

Incidentally, the α ² multiplication circuit 59' and the α ³ multiplication circuit 60' can also be easily constructed in accordance with the above-mentioned α multiplication circuit 58'.

Therefore, in the above configuration, the dividend α ⁱ and the divisor α ^j
are directly or α, α ² , α ³ multiplier circuits 58' to
Initially, the linear shift registers A ₁ ′ to A ₄ ′, B ₁ ′ to B ₄ ′, which are α ⁴ multiplication circuits, are
A ₁ ′: α ^j A ₂ ′: α ^j+1 A ₃ ′: α ^j+2 A ₄ ′: α ^j+3 B ₁ ′: α ⁱ B ₂ ′: α ⁱ⁺¹ B ₃ ′: α ^{i +2} B ₄ ': After being set to α ⁱ⁺³ , it is multiplied by α ⁴ every time the clock pulse C _p is input. In this process, the contents of any one of registers A ₁ ′ to A ₄ ′ become α ²⁵⁵ =
When the clock pulse C p becomes 1, the 1 detection circuits 54' to 57' stop the clock pulse C _p and the above α ²⁵⁵
The contents of registers B ₁ ′ to B ₄ ′ corresponding to registers A ₁ ′ to A ₄ ′ that have become 1 are sent to the AND circuit 6 as the division result.
1' to 64' are output via the OR circuit 65.

Next, in the specific example of FIG. 11, α ¹⁰ ÷ α ²⁴⁰ =
A case will be described in which the division α ^10-240 = α ⁻²³⁰ = α ²⁵ is executed.

In this case, registers A ₁ ′ to A ₄ ′, B ₁ ′ to B ₄ ′ are
A ₁ ′: α ²⁴⁰ A ₂ ′: α ²⁴¹ A ₃ ′: α ²⁴² A ₄ ′: α ²⁴³ B ₁ ′: α ¹⁰ B ₂ ′: α ¹¹ B ₃ ′: α ¹² B ₄ ′: α ¹³ Initially set to
By multiplying α ⁴・α ⁴・α ⁴ = α ¹² with 3 C _ps ,
A ₁ ′: α ²⁵² B ₂ ′: α ²⁵³ A ₃ ′: α ²⁵⁴ A ₄ ^′ : α 255 B ₁ ′: α ²² B ₂ ′: α ²³ B ₃ ′: α ²⁴ B ₄ ′: α ²⁵ , the register A ₄ ' has α ²⁵⁵ =1, so the corresponding content α ²⁵ of the register B ₄ ' is output as the quotient.

In this way, in the specific example of FIG. 11, α ⁴
By multiplying by , the desired division can be performed by multiplication processing while reducing the number of required multiplications of α to 63 times at most (when α ^j =α ¹ ).

In addition, in this case, five sets of linear shift registers, α ⁵
If a multiplication circuit is used, the number of required multiplications of α can be reduced to 50 times at most, and further reductions can be achieved by expanding it.

The error correction circuit described above uses a Galois field for multiplication and division processing in the Galois field, which is necessary for the error location polynomial calculator section.
The multiplication process can be performed simply by using a linear shift register without using a logarithm buffer or an antilog buffer consisting of a large-capacity memory such as a ROM that stores the original logarithm and antilog of GF (2 ^m ) in the form of a table. At the same time, division is converted to multiplication so that it can be done by multiplication processing.In this case, it has the advantage of being able to realize the process of converting division into multiplication processing in as short a time as possible. are doing.

It goes without saying that the present invention is not limited to the embodiments described above and illustrated, and that various modifications and applications can be made without departing from the gist of the invention.

For example, it is suitable for digitized information transmission and recording/reproducing system equipment such as tape PCM.

〔Effect of the invention〕

Therefore, as detailed above, according to the present invention, multiplication and division in the Galois field can be performed without using logarithm buffers or antilog buffers that require a large capacity of memory, especially in the error location polynomial calculator section. Thus, it is possible to provide an extremely good error correction circuit that can contribute to simplifying the configuration and reducing the cost.

[Brief explanation of the drawing]

Fig. 1 is a schematic block diagram showing an error correction circuit comprising a Reed-Solomon code decoding system, Fig. 2 is a block diagram showing a conventional error location polynomial calculator, and Fig. 3 is a DAD playback to which this invention is applied. FIG. 4 is a block diagram showing an outline of the device, FIG. 4 is a block diagram of main parts showing an embodiment of the present invention, FIG. 5 is a block diagram showing a specific example of the multiplication unit shown in FIG. 4, and FIG. 4 is a block diagram showing a specific example of the division device section, FIGS. 7 to 10 are block diagrams showing a specific example of each part in FIG. 6, and FIG. 11 is another specific example of the division device section in FIG. 4. FIGS. 12 and 13 are block diagrams showing specific examples of each part in FIG. 11. 21...Syndrome buffer, 22...Work buffer, 23...Sequence control device, 19, 20, 26,
28, 30, 33...Register, 29...OR circuit,
27... Exclusive OR gate, 41... Multiplication device, 42... Division device.

Claims (1)

[Claims] 1. A generator polynomial ( ^{where α} is the atomic element of the Galois field GF (2 ^m )), and by solving the roots of the error location polynomial f(x) = X ² + σ ₁ X + σ ₂ , the above An error correction circuit for correcting errors in a BCH code for double error correction, comprising a storage means for storing the double error correction BCH code, and 4 syndromes S ₀ , S from the double error correction BCH code. ₁ , S ₂ and S ₃ , and based on the above four syndromes S ₀ , S ₁ , S ₂ and S ₃ , σ ₁ =S ₀ S ₃ +S ₁ S ₂ /S ₁ ² +S ₀ S ₂ , σ ₂ = S ₁ S ₃ +S ₂ ² /S ₁ ² +S ₀ S ₂ By performing predetermined operations including addition, multiplication, and division, the above error location can be converted to the polynomial f(x). An error location where the coefficients σ ₁ and σ ₂ are calculated, and the root of f(x) is calculated by substituting the coefficients σ ₁ and σ ₂ into the above f(x), and an error value is calculated from this root. and an error value calculation means, and a correction means for correcting an error in the double error correction BCH code stored in the storage means according to the error value, In order to perform the predetermined multiplication, the means includes a multiplication device consisting of a first linear shift register, and in order to convert the predetermined division into multiplication, the error location and error value calculation means include a divisor α ^j second and third linear shift registers in which data and dividend α ⁱ data are set separately; a first "1" detection circuit connected to the output of the second linear shift register; The “1” detection circuit detects the number of times that no output is produced, and according to this detection result, the second and third
a first shift means that generates a shift signal for shifting the linear ^{shift register M times} ; In response to the "1" detection output from the "1" detection circuit, the output of the second linear shift register controlled by the first shift means becomes α ^j ·α ^M =1. a first output means for outputting the output α ⁱ · α ^M of the third linear shift register as the quotient of the division between ^the divisor data α ^j and the dividend data α ⁱ ; A predetermined multiplier α ^N for each ⁱ
at least one first and second multiplier circuits, respectively, and at least one fourth and fifth linear shift registers, respectively, in which respective outputs of the first and second multiplier circuits are respectively set;
at least one second "1" detection circuit connected to the output of the fourth linear shift register and detecting the number of times the second "1" detection circuit does not produce an output; Therefore, the fourth
and a second shift means for generating a shift signal for shifting the ^fifth linear shift register ^M times ^; In response to the "1" detection output from the second "1" detection circuit, the output of the fourth linear shift register controlled by the second shift means is α ^j · α ^N · α The output α ⁱ · α ^N · α ^M of the fifth linear shift register obtained when ^M = 1 is expressed as the divisor data α ^j and the dividend data α ⁱ
and second output means for outputting a quotient of a division between.