JPS6237414B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Technical Field of the Invention] The present invention relates to an improvement of a division device in a Galois field suitable for decoding an error correction code used, for example, in 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 accompanied by signal processing called cross interleaving to give it a high correction ability 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 GF, which is a finite field having (m) binary bits, that is, 2 ^m elements.
(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, the transmission codeword is C _(x) and the reception codeword is R _(x).
, and if the error polynomial is E _(x) , then
The following relationship holds between these.

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

Therefore, if the error value at position x ^j is Y _j In Equation (4), Σ means the sum of errors over all positions.

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

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 However, α ^j =X _j , where X _j represents the error location at α ^j .

Here, the error location polynomial σ _(x) is
Let the number of errors be e is defined as

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

S _i+e +σ ₁ S _i+e-1 +...σ _e-1 S _i+1 +σ _e S _i
......(8) That is, in the decoding procedure of the Reed-Solomon code as described above, the syndrome S _i is calculated using the equation () (5).

() 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 of () 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.

That is, the generator polynomial g _(x) in this case is g _(x) = (x + 1) (x + α) (x + α ² ) (x + α
³ ), which makes it possible to correct up to a double error, but here we will discuss the cases using 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, becomes. Also, in the case of e=2 becomes.

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 σ ₁ =S ₁ /S ₀ =S ₂ /S ₁ =S ₃ /S
₂ , and the solutions σ ₁ and σ ₂ of equation (10) are σ ₁ =S ₀ S ₃ +S ₁ S ₂ /S ₁ ² +S ₀ S ₂ , σ ₂
It is determined as =S ₁ S ₃ +S ₂ ² /S ₁ ² +S ₀ S ₂ .

() Once the coefficient σ _i 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 ² + σ ₁ x + σ ₂ = 0 (11), and sequentially substitute the elements of the Galois field GF (2 ^m ) into equation (11). All you have to do is find the solution, and now let these roots be X ₁ and X ₂ .

() Once the root of the error location polynomial has been found, the error value Y _j is next found using equation (6).

First, when e=1, S ₀ =Y ₁ and ∴Y ₁ =S ₀ . In addition, in the case of e=2, S _{0 =} Y ₁ +Y ₂ S ₁ =Y ₁ X ₁ +Y _{2 X 2 ,} ∴Y ₁ =X ₂ S ₀ + _{S 1 /} ) Correction is performed using the error values Y ₁ and Y ₂ obtained as described above.

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 ₁ +X ₃ ) Y ₂ =(S ₁ +X ₃ S ₀ )+Y ₁ (X ₁ +X ₃ )/
(X ₂ +X ₃ ) Y ₃ =S ₀ +Y ₁ +Y ₂ .

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
₃ )/( _X1 + _X2 )( _X1 + _X3 )( _X1 + _X4 ) _Y2 =( _S0X4 + _S1 ) _X3 +( _{S1X4 +} S2)+ _{Y1 ( X1} + _{X3 )} )(X ₁ +X ₄ )/(X ₂ +X _{3
) ( X 2 + X 4 ) Y 3 = ( S 0 _ _ _ _} +Y ₃ .

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

FIG. 1 is a schematic configuration diagram showing 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) , the error location calculator 16 calculates the roots of the error location polynomial, and the error value calculator 1
7 calculates the error value, and by these error locations and error values, the above data buffer 1
This is to correct the data output from 1.

By the way, each of the calculators 12, 15, 16, and 17 of such a decoding system performs the detection of 0 or not and performs necessary algebraic operations such as addition, multiplication, and division. 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 .
1 stores each syndrome which is an element of the Galois field GF(2 ^m ) in m-bit binary format.

Further, 22 is a work buffer for storing 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 a ROM that stores the original logarithm and antilog of (2 ^m ) in table format separately.

Here, the address of the former logarithm buffer 24 is the binary representation of the original α ⁱ , and its entry is α
The logarithm of α, i.e., the base is i, and the entry at address i in the latter antilog buffer 25 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 linear combination from α ⁰ to α ⁷ It can be expressed as

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 logarithm table address 1~
255 is an 8-bit binary vector representation of element α ⁱ , and the corresponding entry is a 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 adding elements α ⁱ and α ^j , these two elements are added to the exclusive OR gate 27 via the A register 20 and the B register 26.
Exclusive OR is performed for each bit. The result of the sum of the two elements thus obtained is sent to the working buffer 2 via the C register 19.
Transferred to 2.

(2) Detection of whether or not it is 0 When checking whether or not the element α ⁱ is 0,
The element α ⁱ passes through the H register 28 to the OR gate 2
The logical sum is calculated using 9. 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 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. The outputs i and j from the logarithm buffer 24 are then passed through a D register 32 and an E register 33 to a one's complement adder 34 where they are subjected to one's complement addition modulo 2 ⁸ -1. The result (i+j)=tmod(2 ⁸ -1) obtained by this is the L register 35.
is loaded into the address register 36 for the antilog buffer 25 through. In this case, if the address input to the antilog buffer 25 is t, its output is transferred to the working buffer 22 via the G register 37 as the result of multiplication by α ^t .

(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. Processing is carried out in the same manner as in the case of multiplication (3) below, 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 device as described above requires a logarithm buffer and an antilog buffer 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.

If one symbol is 8 bits as in the example above, this means 255 x 8 bits = 2040 bits of ROM.
This can be easily seen from the fact that two 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 was complicated and the price was high.

[Purpose of the invention]

Therefore, the present invention has been made in view of the above points, and it is possible to perform division in a Galois field without using a logarithm buffer or an antilog buffer, which requires a particularly large capacity of memory. It is an object of the present invention to provide an extremely good division device in a Galois field that can contribute to simplification, lower cost, and higher processing speed.

[Summary of the invention]

That is, the division device in a Galois field according to the present invention divides ^two elements ^{α i} and α ^j (where α is the modulus polynomial F
(root of _(x) ) α ⁱ ÷ α ^j is α ⁱ・α ^M ÷α ^j・α ^M
(where M is an integer), convert it into the form of the quotient of the first multiplication [α ⁱ · α ^M ] and the second multiplication [α ^j · α ^M ],
Utilizing the fact that the second multiplication is α ^j・α ^M = α ^2m-1 = α ⁰ = 1, the result is α ⁱ ×÷α ^j = α ⁱ・α ^M
The above element α ^j
is the dividend data directly or an appropriate number of α _N
1 , α _N2 ... multiplier circuit (however, N ₁ , N ₂ ... is 1≦
N ₁ <N ₂ ...), and each shift is set by α _N0 (however, N ₀ is 1
<N ₀ ), and the element α ⁱ is set as divisor data either directly or through an appropriate number of α ^N1 , α ^N2 . . . multiplication circuits. ^The second
a linear shift register group, one detection circuit group for detecting one output from each register of the first linear shift register group, and an appropriate number of detection circuits until one output is detected by any one of the one detection circuit group. a first means for shifting both the first and second linear shift register groups by times; an output for each register of the second linear shift register group; and an output for each detection circuit of the first detection circuit group; and a second means for deriving the ANDed register output by performing the AND operation.

[Embodiments of the invention]

First, the optical type (CD type) to which this invention is applied
An overview of a digital audio disk (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, the beam splitter 114b leads to a 4-split photodetector 114d, and the 4 playback signals photoelectrically converted by the 4-split photodetector 114d can be outputted to the outside, and from the beam splitter 114b to a pick-up feed motor 115. Therefore, the disk 113 is linearly driven in the radial direction.

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, the reproduced signal processing system 118 first passes the reproduced signal to the slice level (eye pattern) detector 1.
A waveform shaping circuit 120 controlled by a PLL type synchronous clock reproducing circuit 121 and a first signal processing system 1 separate unnecessary analog components and necessary data components by guiding a waveform shaping circuit 120 controlled by a PLL type synchronous clock reproducing circuit 121 and a PLL type synchronous clock reproducing circuit 121.
22 edge detectors 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 demodulated (FFM). .

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 PWM modulator 122m to drive the disc motor 111 at constant linear velocity (CLV).
Automatic frequency control (AFC) for driving
and automatic phase control (APC).

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 a speaker 130 for sounding.

Next, an embodiment of a division device in a Galois field according to the present invention applied to an error correction section of a 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.

Next, let's look at multiplication in a Galois field. For example, the multiplication of the elements α ⁱ and α ^j of the Galois field GF (2 ⁸ ) (α ⁱ · α ⁱ , where α is the modulus polynomial F _(x) = X ⁸ + X ⁶
+X ⁵ +X ⁴ +1) is α ⁱ =C(α)=c ₀ +c ₁ +α+……c ₇ α ⁷ ) α ^j =D(α)=d ₀ +d ₁ α+……d ₇ α ⁷ _{If expressed as _} ^{_ _} _{_} ^_ ₆ α ⁶ 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 (α)].

In other words, the element α ⁱ of such Galois field GF(2 ⁸ )
This shows that the multiplication of α ^j by α j can be realized by a multiplier configured as shown in FIG. 5 using a linear shift register.

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 c ₀ to _{c 7} which are the coefficients of the multiplicand C(α) above.
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 series 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 ₅ -FF ₇ are connected to exclusive or gates EX-OR ₅ ′, EX-OR ₆ ′, EX-OR ₇ with one step each connected to the return route. ′ is further inserted. In addition, the clock input terminal CK of each flip-flop circuit FF ₀ to FF ₇
A clock is supplied in parallel from a clock generator (not shown).

In other words, by inputting the coefficients c ₀ to _{c 7} of C(α) in a bit-serial manner, first X ₀ is calculated, then X ₁ , X ₂ , etc., and then the linear shift register SR is ₀ has X ₇ or 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 1 C} ( _α ) The multiplication device for the Galois field GF(2 ⁸ ) as described above is a logarithm buffer or an antilog buffer consisting of a large capacity memory such as a ROM that stores the logarithm and antilog of the elements of the Galois field GF(2 ⁸ ) in the form of a table. Since this can be achieved simply by using a linear shift register without using a , it has the effect that the configuration can be made simple and inexpensive.

Next, let's look at division in a Galois field. For example, the division of elements α ⁱ and α ^j of Galois field GF (2 ⁸ ) is α ⁱ ÷ α ^j (where α is the modulus polynomial F _(x) = x ⁸ + x ⁶ +x ⁵
+x ⁴ +1) is equivalent to α ⁱ ÷ α ^j = (α ⁱ · α ^M ) ÷ (α ^j · α ^M ) (where M is an integer).

In this case, if α ^j · α ^M = α ²⁵⁵ = α ⁰ = 1, then α ⁱ ÷ α ^j = α ⁱ · α ^M.

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

It goes without saying that the multiplication process is performed using a multiplication device using a linear shift register as described above.

By the way, in this case, α ^j・α ^M = α ²⁵⁵ = α ⁰ =
The number of times of multiplication by α required to obtain 1 is at most 254 times when the divisor α ^j = α ¹ (that is, M =
254), but simply allowing it to do so would undesirably increase the time required for the multiplication process.

Therefore, in this invention, by multiplying the dividend α ^j and the divisor α ^j by α an appropriate number (N) times in advance, the number of times actually required for multiplication by α is reduced and the multiplication process (delayed) is done in a short time. The purpose of this is to make it possible to perform division processing.

FIG. 6 shows the configuration of a division device that realizes division in a Galois field by multiplication processing as described above. In this case, as (N) mentioned above, 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 or α ¹
It is set via a multiplication circuit 51, an _α2 multiplication circuit 52, and an ^α3 multiplication circuit 53 into linear shift registers A ₁ , A ₂ , A ₃ , and A ₄ that constitute an ^α4 multiplication circuit.

Here, linear shift registers A ₁ , A ₂ , A ₃ , A ₄
is a flip-flop circuit as shown in Figure 7.
FF ₁₀ ~ FF ₁₇ Exclusive or Gate EX−
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 Cp applied via AND ₁₀ , and has an ^α4 multiplication function in which it is multiplied by ^α4 every shift.

1 detection circuits 54, 55, 56, which are supplied with the outputs of the shift registers _A1 , _A2 , _A3 , _A4 ,
57 is the inverter _I10 and 8 as shown in FIG.
It is composed of an input NOR gate NOR ₁₀ , and 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 becomes "0" when any of the 1-detection outputs occurs. and gate
Through AND ₁₀ , the passage of clock pulse Cp is controlled from the previously allowed state to the prohibited state.

Similarly to ^the divisor α ^j data, ^{the dividend α i data can also be input to the α 4 multiplication circuit} as ^shown in FIG. After being set in the constituent linear shift registers B ₁ , B ₂ , B ₃ , and B ₄ , it is multiplied by α ⁴ an appropriate number of times by the clock pulse Cp.

Here, each output of the shift registers B ₁ , B ₂ , B ₃ , and B ₄ is outputted from AND circuits 61 , 62 , and 6 correspondingly to each output from the first detection circuit 54 , 55 , 56 , and 57 .
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. 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 connected to the other terminal of the AND circuits 61 to 64. This is a case in which eight two-input AND gates _AND20 to _AND27 are respectively supplied with the outputs of the one detection circuits 54 to 57 correspondingly.

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 α ¹ multiplication circuit 58 in the above, in which case α ^j is expressed as α ^j =B(α)=b ₇ α ⁷ +b ₆ α ⁶ +...+b ₁ α+b ₀ 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 the 10th This is realized using exclusive OR gates EX-OR ₃₂ to EX-OR ₃₄ as shown in the figure, 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.

In the above configuration, the dividend α ⁱ and the divisor α ^j are transferred directly or via the α, α ² and α ₃ multipliers 58 to 60 to the linear shift registers A ₁ to _{A 4} , which are α ⁴ multipliers. Initially in B ₁ ~ _{B 4} After being set to , it is multiplied by ^α4 every time a clock pulse Cp is input. In this process, the contents of any one of registers A ₁ to _{A 4} become α ²⁵⁵
= 1, the 1 detection circuits 54 to 57 stop the clock pulse Cp, and the above α
The contents of the registers B ₁ to B ₄ corresponding to the registers A ₁ to _{A 4} that have become ²⁵⁵ = 1 are outputted as the division results via the AND circuits 61 to 64 and the OR circuit 65.

Next, as a specific example, α ¹⁰ ÷ α ²⁴⁰ = α ^10-240 = α
A case will be explained in which the division ^-230 = α ²⁵ is executed.

In this case, registers A ₁ to A ₄ and B ₁ to _{B 4} are By multiplying ^α4・^α4・^α4 = ^α12 with three clock pulses Cp initially set as shown in FIG. As shown, since α ²⁵⁵ =1 in register A ₄ , the content α ²⁵ of register B ₄ corresponding to this is output as the quotient.

In this way, by multiplying α ^{by 4} each time, the required number of multiplications of α can be reduced to at most 63 times (α
When ^j = α ¹ ), the desired division can be performed by multiplication processing.

Furthermore, if five linear shift registers and an ^α5 multiplication circuit are used, the number of α multiplications required can be reduced to 50 at most, and further reductions can be achieved by expanding this. It is possible.

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

For example, it is suitable for devices that require algebraic operations using Galois fields, such as tape PCM and other digitized information transmission, recording and reproducing systems, computer systems, and the like.

〔Effect of the invention〕

Therefore, as detailed above, according to the present invention, it is possible to perform division in a Galois field without using a logarithm buffer or an antilog buffer that requires a large capacity of memory, thereby simplifying the configuration and It becomes possible to provide an extremely good division device in a Galois field that can contribute to low cost and high speed processing.

[Brief explanation of the drawing]

Fig. 1 is a schematic block diagram showing a Reed-Solomon code decoding system, Fig. 2 is a block diagram showing a conventional error location polynomial calculator, and Fig. 3 is an overview of a DAD playback device to which the present invention is applied. A configuration diagram, FIG. 4 is a configuration diagram showing an embodiment of the present invention,
5 is a block diagram showing a specific example of the multiplication device section in FIG. 4, FIG. 6 is a block diagram showing a specific example of the division device section in FIG. 4, and FIGS. 7 to 10 are respectively shown in FIG. 6. A linear shift register section, a 1 detection circuit section, an AND circuit section, an OR circuit section, which constitute the α ⁴ multiplication circuit of
FIG. 2 is a configuration diagram showing a specific example of an α ¹ multiplication circuit. A ₁ to _{A 4} ... (for α ⁴ multiplier circuit) linear shift register, NOR ₁₁ ... NOR gate, AND ₁₀ ... AND gate, 51, 58 ... α ¹ multiplier circuit, 52,
59...α ² multiplication circuit, 53, 60...α ³ multiplication circuit, 54-57...1 detection circuit, 61-64...
...AND circuit, 65...OR circuit.

Claims (1)

[Claims] 1. Division α i between two elements α ⁱ and α ^j (where α is the root of the modulus polynomial F _(x) ) among 2 ^m elements ⁱⁿ the Galois field GF (2 ^m ) ÷α ^j in the form of the quotient of the first multiplication [α ⁱ · ^{α M} ] and the second multiplication [α ^j · α ^M ], which is α i · α ^M ÷ α ^j · α ^M (where M is an integer). Using the fact that the second multiplication is α ^j · α ^M = α ^2m-1 = α ⁰ = 1, the result is converted to the multiplication α ⁱ ÷ α ^j = α ⁱ · α ^M. The element α ^j is used as the dividend data directly or as an appropriate number of α ^N1 , α ^N2
...multiplication circuit (however, N ₁ , N ₂ ... is 1≦N ₁ <N ₂ ...
), and 1
The first linear shift resistor group is multiplied by α ^N0 (where N ₀ is 1<N ₀ ) for each shift, and the element α ⁱ is used as divisor data directly or as an appropriate number of α ^N1 , α ^N2 . . . A second linear shift register group which is set individually via a multiplier circuit and multiplied by α ^N0 for each shift, and a a first detection circuit group that detects one output; and a first detection circuit group that shifts the first and second linear shift register groups together an appropriate number of times until one output is detected in one of the one detection circuit groups.
and a second means for ANDing the output of each register of the second linear shift register group and the output of each detection circuit of the first detection circuit group to derive the ANDed register output. 1. A division device in a Galois field, comprising: means.