JPH0744466B2 - Lead Solomon encoding / decoding sigma arithmetic circuit - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a decoding system for a Reed-Solomon code capable of error correction used in digital audio equipment and the like, and in particular, a coefficient arithmetic circuit for an error locator polynomial as part of the decoding system. Regarding

[Conventional technology]

In digital audio equipment, a code error occurs due to various causes when creating information on a recording medium. Therefore, as a countermeasure against random errors, information is coded to make it a code capable of error correction. BCH code and Reed-Solomon code are well known as error-correctable codes. The Reed-Solomon code is a type of non-binary BCH code, and is 8 in digital audio disc players.
The C1 (32,28) code and the C2 (28,24) code in which the source of bits is treated as one symbol are in practical use. Here, the first term in parentheses is the number of symbols of the code block length, and the second term is the number of information symbols. In the above C1 and C2 codes, the number of check symbols is 4
The minimum distance between the individual symbols is 5 symbols, and the syndrome correction capability can correct a maximum of 2 symbols. By the way, in order to further improve the correction capability in the future, it is necessary to use a code with a further increased minimum distance. If the correction capability is increased to 3 symbols or 4 symbols, the decoding system becomes extremely complicated.

The decoding scheme is performed in several stages, first determining the syndrome and then locating the erroneous symbol within the code block. The position of the erroneous symbol is determined from the value of ⁱ at which the symbol represented by the power exponent a ⁱ of the primitive root α is sequentially input to the error locator polynomial and the error locator polynomial becomes zero. The present invention seeks to find the coefficients of the error locator polynomial. In the case of a Reed-Solomon code with 2-symbol error correction capability, the polynomial is 1 + σ ₁ X
+ Σ ₂ X ² and the coefficients σ ₁ and σ ₂ are the syndrome S
_It is a little complicated from _{0 to} S ₃ , but it can be obtained by algebraic expressions.

However, in a Reed-Solomon code having an error correction capability of 3 symbols or more, the coefficients σ ₁ , σ ₂ ... Are extremely complicated,
It is practically impossible to get from a specific algebraic expression from the beginning.

In the case of the Reed-Solomon code having such multi-symbol error correction capability, the so-called Berlekamp Massey method is suitable. For the explanation of this method, refer to a book dealing with code logic, for example, Hiroshi Miyagawa et al., "Theory of Code", Shokoido 3rd Edition, pp. 257 et seq.

This method is a polynomial C _n (X) of the following formula called a coupling polynomial.
= 1 + C _n , ₁ X + C _n , ₂ X ² + ... (1) is, for example, when the number of check symbols is 6 and the error correction capability is 3 symbols, C ₆ (X) = 1 + C ₆ , ₁ X + C ₆ , ₂ X ² + C ₆ , ₃ X ³ = σ (X) = σ ₀ + σ ₁ X + σ ₂ X ² + σ ₃ X ³ (2) where the error locator polynomial σ (X) is C ₆ , ₁ , C ₆ , ₂ ,
It can be calculated by C ₆ , ₃ .

C _n (X) is obtained by the following iterative algorithm starting from C ₀ (X) = 1.

The coupling polynomial is a recurrence formula C _{n + 1} (X) ＝ C _n (X)-(δ _n / δ _{k (n)} ) ・ X ^{nk (n)} C _{k (n)} (X) (3) Initial value at n = 0 C ₀ (X) = C ₋₁ (X) = 1, u ₀ = u ₋₁
= 0, δ ₋₁ = 1 (8), starting from n = 0, n = 1, 2, ..., For example, C ₆ (X) is obtained. However, although it is calculated as described above, an example of automatically calculating it by a specific arithmetic circuit is not known at present.

[Problems to be solved by the invention]

It is an object of the present invention to provide an execution circuit for obtaining a coefficient of an error locator polynomial of a Reed-Solomon code capable of multi-symbol correction based on the Berlekamp Massey method. In this case, how to reduce the circuit scale of the digital circuit and increase the processing speed was one of the important issues.

[Means for solving problems]

In the present invention, attention is paid to the fact that the operations of equations (3) to (8) by the above recurrence equation are further executed by the flowchart shown in FIG. This flow chart is document ER
BERLEKAMP "ALGE BRAIC CODING THEORY" by McGraw-Hill Company.

The above flow chart is for the case of 3 symbol correction, R1, R2,
R3 is a register. R1 is C _n (X) (Except C _n , ₀ = 1), and R2 is ▲ [S
(X)] ⁿ _σ ▼ R3 is X ^{nk (n)} C _{k (n)} (X) (Except F ₀ = 0).

If there are three symbols or more, the number of digits in each register may be increased.

Therefore, in the present invention, by providing a counting section for effectively performing various multiplications / divisions / additions shown in the above flow chart and a register and operating them at an appropriate timing, starting from n = 0 and finally Is R1
Since the sigma coefficient value is stored in the register, the circuit scale becomes small, and, for example, three sigma σ ₁ , σ
_{Since 2} and σ ₃ are calculated at the same time, the processing time can be shortened.

Arithmetic circuit of the present invention a plurality of operation blocks including the _{C n, 1, C n,} 2 ... counting unit connected to the data bus and the data bus for each and the plurality of register components, δ _n / δ _{k It} is composed of a calculation unit that determines _(n) , a control signal generation unit that generates a condition flag in the iterative algorithm, and a timing signal generation unit.

In the operation block, the counting unit converts a vector value input from the data bus into a power exponent value, performs a MOD operation, and converts the vector value into a multiplication value, and outputs the multiplication circuit and an input from the data bus. the consists of a summing circuit for vector addition, the register component respectively C _n in three registers that each component in each operation block is disposed
(X), ▲ [S (X)] ⁿ _σ ▼, X ^{nk (n)} C _{k (n)} Respective components of the R1, R2, and R3 registers representing (X), R2 register, R
In the 3 register, each component is connected in series, and the syndrome and predetermined data are input from the C _n , ₁ operation block side,
C _n , ₂ , C _n , ₃ ... Wiring that can be shifted to the operation block side.

The δ _n / δ _{k (n)} operation unit inputs and adds the outputs C _n , ₁ S _n-1 , C _n , ₂ S _n-2 , ... And S _n of the multiplication circuit of each operation block,
A circuit for converting δ _n converted into a power exponent value into a vector value after MOD calculation and outputting to a data bus of each calculation block is configured.

The control signal generating unit for generating the condition flag, the δ _n /
[delta] shows a [delta] _{n =} 0 per [delta] _n obtained by δ _{k (n)} arithmetic unit
_{It is} composed of a circuit for generating _n flags and n, u _n and n2u _n flags.

The timing signal generator is configured to operate the calculation block, δ _n /
A timing pulse for operating the Δ _{k (n)} calculation unit / control signal generation unit is generated, and the generation timing of this timing signal is controlled by a condition flag.

[Action]

The arithmetic circuit of the present invention is the execution circuit of the flow chart shown in FIG. 3, and each component operates in response to the timing signal from the timing signal generator starting from n = 0. n = d-
By repeating up to 2 (d is the minimum symbol interval), (d-
The value of each coefficient of the error locator polynomial is obtained for 1) / 2 error-correctable symbols, and the coefficient value is stored in the R1 register. Detailed description of the operation will be described in the embodiment.

〔Example〕

Embodiments of the present invention will be described with reference to the drawings. All of the embodiments are circuits for codes capable of correcting 3 symbols. FIG. 1 shows a calculation block, and FIG. 2 shows a δ _n / δ _{k (n)} calculation unit, a control signal generation unit for generating a condition flag, and a timing signal generation unit.

In FIG. 1, reference numerals 10, 20, and 30 are calculation blocks, respectively.
It corresponds to C _n , ₁ , C _n , ₂ , C _n , ₃ . The internal circuit of the counting unit is the same, and only the counting unit 11 is shown. The flip-flop connected to the data buses # 1, # 2 and # 3 is # 1
It is a D-type flip-flop with an enable terminal except for the flip-flop 14 connected to. The flip-flop 14 operates as a buffer. As shown in the figure, the above element groups laterally form R1 register, R2 register, and R3 register respectively, but the flip-flops 12, 22, 32 of the R1 register are only connected to the data buses # 1, # 2, # 3. Data is passed, but the R2 and R3 registers can be shifted to the right. And the R2 register has a syndrome bus
Syndrome S ₀ , S ₁ … is input from S _n , and the R3 register receives “1” or “0” depending on the status of P7 with the timing signal of P6.
Is entered.

Next, the counting unit 11 will be described. Vector input is ROM1
Converted by 1 into exponential notation of primitive root α,
The flip-flop 112, the MOD operation circuit 113, and the flip-flop 114 add the exponent, and the ROM 115 outputs the vector display. This part is a multiplication circuit, and the EX-OR circuit 117 and the flip-flop 118 form a vector addition circuit. This is because the zero detection circuit 120 and the AND circuit 116 output “0” because the multiplication result is “0” when the vector input is “0”. This is because the MOD operation does not work properly when the vector input is "0". The output of the multiplication circuit from the counting unit 11 is led to C _n , ₁ S _n-1 via the flip-flop 119 to the δ _n / δ _{k (n)} computing unit of FIG.

FIG. 2A shows the δ _n / δ _{k (n)} operation unit 40. 41 is EX-OR
After .SIGMA.C _n, the _i · S _ni we calculated a [delta] _n the circuit, [delta] _n / [delta]
_In order to obtain _{k (n)} , the vector is converted into a power exponent, divided, and converted into a vector again. That is, in order to obtain δ _{k (n)} from the exponent value δ _{n of the} ROM 42 output, it is delayed by the flip-flop 43 and then inverted, and the MOD operation circuit 44 takes the difference from σ _n . The vector value of δ _n / δ _{k (n)} is distributed to the data buses # 1, # 2, # 3 by the flip-flops 47, 48, 49.

FIG. 2B shows the control signal generator 50, which outputs the number of repetitions n from the counter 51 as an n flag. The flip-flop 52, an inverter 53, the adder circuit 54 and 55 u _n
Is a circuit for updating every clock input P2 with n-u _n +1 as the output, and outputs the u _n flag via the flip-flop 57, and inputs n and u _n with the comparator 56 to obtain the digit of the corresponding terminal. N2u _n is detected by shifting
Output the 2u _n flag.

FIG. 2 (c) shows the timing signal generator 60,
The micro-programming circuit generates the required timing signals P0, P1, ... For each clock input, inputs the flag input at an appropriate timing, and jumps by the flag. Timing signals are shown in FIG.

This operation circuit performs the operation shown in the flow chart of FIG. 3, and the circuit operation is decomposed in detail based on FIG. 3 and shown in flow chart form in FIGS. 4 and 5. The time chart of the timing signal at this time is shown in FIG. Sixth
4 and 5 are described for each of the time sections T1, T2, ... Shown in the upper part of the figure. In the following, in the meaning of complementing FIGS. 4 to 6, a brief description will be added for each time segment. Hereinafter, the flip-flop is abbreviated as DFF.

T1: Reset the counters 51, DFF52, 43, 119 (not shown in the drawing, but 219, 319 and below as corresponding). DFF24,3
For data bus 4, data buses # 1 and # 2 are low and take in "0". T2: DFF13,23,33 operates, R3 register sets (100) T3: DFF12,22,32 operates, R1 register (000 ) Set T4: δ _n = 0 flag, “0” if δ _n = 0, “1” if δ _n ≠ 0 T5: δ _n = 0, DFF13, 23, 33 operates, R3 register The data is sent to the bus and stored in the DFF on the right.
However, T6: DFF12, DFF112 (212,312) operation in which DFF13 becomes “0”, because R1 × R3 is calculated later to obtain δ _n T7: n2u _n flag, if n2u _n is “0”, n <2u If _n is "1" T8: n2u _n , DFF13,23,33 operates and is latched by DFF112,212,312 via data buses # 1,2,3. DFF4
Store δ _n / δ _{k (n) in} 7,48,49 T9: Output δ _n / δ _{k (n)} from DFF47,48,49 δ _n / δ _{k (n)} × R3
Stores the calculation result of in the DFF114 (214,314) T10: DFF12,22,32 R1 register data is sent to the bus DFF
Store to R3 register at 23,33. At this time, the data in the R1 register is moved to the R3 register and is shifted at the same time.
The left end DFF13 of the register stores “1”. The data of the R1 register is also sent via the bus to the counting unit 10 (20,3
0) EX-OR circuit 117 (217, 317) add and DFF118 (2
18, 318) to _{(δ n / δ k (n} ) × R3) + R 1 store T11: DFF118 (from _{218,318) (δ n / δ k} (n) × R3) + the R ₁ sends to the bus, the multiplication circuit DFF112 (212,312) and D
Stored in the R1 register of FF12, 22, 32 Also, in the δ _n / δ _{k (n)} operation unit 40, the DFF43 sends δ _{k (n)} ,
The control signal generator 50 calculates u _n T12: Sends the data of DFF13,23,33 of the R3 register to the bus and stores it in the DF112 (212,312) of the multiplier circuit. "0" is stored Also, δ _n / δ _{k (n)} store in DFF47, 48, 49 Same as T13: T9 T14: R1 register DFF12, 22, 32 data is sent to the bus EX-O
Add by R circuit 117 (217,317) and store in DFF118 (218,318) Store data of T15: DF118 (218,318) in R1 register DFF12,22,32 via bus. Also, as new R1, DFF112 (21
2,312) Store T16: Count counter 51 by 1. Right shift DFF24, 34 and store S _{n + 1 in} DFF14 At this time, the data of R2 register is input to the multiplier circuit via the bus and the operation result of R1 × R2 is stored in DFF114 (214, 314) T17: Counting unit 11 R21 x R2 to DFF119 (219,319) of (21,31),
That is, C _n , ₁ S _n-1 , C _n , ₂ S _n-2 , C _n , ₃ S _n-3 are stored, and δ _n is calculated at the same time. In a 3 symbol correctable signal, d = 7, n = d-2 = 5
Therefore, if it is repeated 4 times later, DFF12,22,32 of R1 register
Since _{C 6, 1 = σ 1,} C 6, 2 = σ 2, C 6, 3 = σ 3 are stored in the data bus # 1, # 2, can be output from the # 3.

〔The invention's effect〕

As described above in detail, according to the present invention, the coefficient of the error locator polynomial in the decoding system of the Reed-Solomon code capable of correcting an error of 3 symbols or more is used, the circuit scale is reduced by using the algorithm by the Berlekamp-Massie method, and Since the sigma coefficient is calculated simultaneously, the processing time can be shortened.

[Brief description of drawings]

1 and 2 are circuit block diagrams of one embodiment of the present invention,
FIG. 3 is a flowchart showing the algorithm of the Berlekamp Massey method, FIGS. 4 and 5 are diagrams for explaining the circuit operation of the embodiment, and FIG. 6 is a time chart. 10, 20, 30 ... Operation block, 11, 21, 31 ... Counting unit, 12-14, 22-24, 32-34 ... Flip-flop, 111 ... ROM (V → I conversion), 115 ... ROM (I → V conversion), 112, 114, 118, 119 ... Flip-flop, 113 ... MOD operation circuit, 116 ... AND circuit, 117 ... EX-OR circuit, 120 ... Zero detection circuit, 40 ... δ _n / δ _{k (n)} Arithmetic unit, 41 ... EX-OR circuit, 42,45 ... ROM (V → I conversion, I → V conversion), 43 …… Flip-flop, 44 …… MOD arithmetic circuit, 47 to 49 …… Flip-flop, 50 ... Control signal generator, 51 ... Counter, 52,57 ... Flip-flop, 54, 55 ... Adder circuit, 56 ... Comparator, 60 ... Timing signal generator.

Claims (1)

[Claims] 1. When a Reed-Solomon code having multi-symbol correction capability is combined, the syndrome S _n is input and a joint polynomial C is input based on the Berlekamp-Massie method.
Recurrence formula C of _n (X) = 1 + C _n , ₁ X + C _n , ₂ X ² + ...
_{n + 1} (X) = C _n (X) − (δ _n / δ _{k (n)} ) X ^{nk (n)} C
_{Using k (n)} (X), starting from n = 0, σ ₁ = C _n , ₁ ,
As σ ₂ = C _n , ₂ ... Coefficients of error locator polynomial σ ₁ , σ ₂
An arithmetic circuit for executing a repetitive algorithm to determine ..., A data bus defined for each C _n , ₁ , C _n , ₂ ..., a counting unit connected to the data bus, and a plurality of register components A plurality of arithmetic blocks, and a δ _n / δ _{k (n)} arithmetic unit that performs an operation to determine the coefficient δ _n / δ _{k (n)} of the recurrence formula based on the output from the arithmetic block. With a timing signal generator that generates a timing signal necessary for operation, and a timing signal from the timing signal generator,
And a control signal generating unit for generating a condition flag in the iterative algorithm, wherein, in the operation block, the counting unit converts an input vector value from the data bus into a power exponent value, performs a MOD operation, and converts into a vector value. The register component is composed of three registers, each of which is arranged in each of the arithmetic blocks. The register circuit is composed of an output circuit and an adder circuit for vector-adding the output of the multiplier circuit and the input from the data bus. C _n of each of the recurrence formula (X), the syndrome input [S
(X)] ⁿ , R1, R representing X ^{nk (n)} C _{k (n)} (X) in the recurrence formula
The components of the R2 register and the R3 register are connected in series in the R2 register and the R3 register, respectively, and the syndrome and predetermined data are input from the C _n , ₁ operation block side, and C _n , ₂ , C _n ,
₃ ... Wiring is connectable to the operation block side, and the δ _n / δ _{k (n)} operation unit outputs the outputs C _n , ₁ S _n-1 , C _n of the multiplication circuit of each operation block. , ₂ S _n-2 ... And S _n are input and added, and δ _n converted into a power exponent value is converted into a vector value after MOD calculation and output to the data bus of each calculation block. configured, the control signal generating unit for generating the condition flag, the [delta] _n /
[delta] shows a [delta] _{n =} 0 per [delta] _n obtained by δ _{k (n)} arithmetic unit
_The timing signal includes an _n flag, a circuit for generating _n flags indicating the number of iterations of the iterative algorithm, u _n indicating operation parameters of the operation block, and _{n 2} u _n indicating conditions at the time of operation of the operation block. The generation unit generates a timing signal for operating the calculation block, the δ _n / δ _{k (n)} calculation unit, and the control signal generation unit, and the timing signal is generated by the condition flag generated by the control signal generation unit. Reed-Solomon code / combining sigma arithmetic circuit characterized by controlling the generation timing of