JPH0744463B2 - Error correction circuit - Google Patents

Description

The present invention relates to an error correction circuit applied to a Reed-Solomon code decoder.

"Background art and its problems" As an error correction code when recording / reproducing a digital audio signal, a digital video signal, or recording / reproducing data by a digital data recorder,
Reed-Solomon code is used. In the decoding of this Reed-Solomon code, a syndrome is formed by the product of the received data sequence and a check matrix (so-called H matrix), and from this syndrome, the position of the error symbol and the error pattern in the received data sequence are Galois field (GF ₂ ^m ) The error is corrected by the above calculation. A conventional circuit for performing the above-mentioned error correction in real time is either a stored program system using time division multiplexing processing or a hard wired system.

However, in the case of high-speed data with a high sampling frequency, the stored program method cannot perform time-division multiplexing processing due to the operating speed constraint of the arithmetic element,
Further, when a parallel processing configuration is used for high speed operation, there is a drawback that the circuit scale becomes large. On the other hand, the hard-wired method can process high-speed data, but has a drawback that the circuit scale is larger than that of the stored program method and the versatility is lacking.

SUMMARY OF THE INVENTION Therefore, an object of the present invention is to provide an error correction circuit which has a small circuit scale and can process high-speed data by utilizing the time margin of the error correction processing. It is what In other words, according to the present invention, when the syndrome is formed from the data input for each clock, there is no time margin, so the processing is performed by the hard-wired method, and once for each series of codes composed of a plurality of symbols. When calculating the error position and the error pattern from the input syndrome, there is a time margin, so the rotation of the program stored method is used.

[Summary of the Invention] The present invention is controlled by a hard-wired syndrome generation circuit that generates a syndrome from input data including redundant data of an error correction code and a program stored in a program memory. The error correction circuit includes a circuit that calculates and outputs an error pattern and a circuit that corrects a symbol at an error position in input data.

[Embodiment] An embodiment of the present invention will be described below with reference to the drawings. In this embodiment, the present invention is applied to a Reed-Solomon code decoding circuit capable of correcting a 2-symbol error.

First, the generation and error correction of a Reed-Solomon code that can correct a 2-symbol error will be described.
The H matrix of Reed-Solomon code is (However, α is the primitive element of GF ( ^2m ).) The data sequence C including parity is C = (D ₁ D ₂ … D _n-4 P ₃ P ₂ P ₁ P ₀ ), and this parity P ₀ , P ₁ , P ₂ , P ₃ , (HC ^T = 0) It is obtained by solving the following two-dimensional simultaneous equations derived from. Addition, subtraction, multiplication, and division in the following equations are operations on Galois field, and Σ is Means

P ₀ ＋ P ₁ ＋ P ₂ ＋ P ₃ ＝ ΣD _i P ₀ ＋ αP ₁ ＋ α ² P ₂ ＋ α ³ P ₃ ＝ Σα ⁿⁱ Di P ₀ ＋ α ² P ₁ ＋ α ⁴ P ₂ ＋ α ⁶ P ₃ ＝ Σα ^{2 (ni)} Di P ₀ + Α ³ P ₁ + α ⁶ P ₂ + α ⁹ P ₃ = Σα ^{3 (ni)} Di When the above data sequence C is transmitted, if the i and jth errors of the pattern ei, ej occur,
The received data sequence C ′ is C ′ = D ₁ , D ₂ , ..., Di + ei, ..., Dj + ej, ..., P ₃ , P ₂ , P ₁ , P ₀ ) = C + (0, ..., 0, ei, 0, ... 0, ej, 0 ... 0). Therefore, the syndrome obtained by multiplying the received data sequence C ′ by the H matrix is as follows.

S ₀ = ei + ej S ₁ = 0α ⁿⁱ ei + α ^nj ej S ₂ = α ^{2 (ni)} ei + α ^{2 (nj)} ej S ₃ = α ^{3 (ni)} ei + α ^{3 (nj)} ej. In the case of a 1-symbol error, S ₀ = ei S ₁ = α ⁱ ei S ₂ = α ²ⁱ ei S ₃ = α ³ⁱ ei. An error position and an error pattern can be obtained from the syndromes S _{0 to} S ₃ .

In case of 2-symbol error: From the syndrome equation, α ⁿⁱ S ₀ + S ₁ = (α ⁿⁱ + α ^nj ) ej α ⁿⁱ S ₁ + S ₂ = (α ⁿⁱ + α ^nj ) α ^nj ej α ⁿⁱ S ₂ + S ₃ = (α ⁿⁱ ＋ α ^nj ) α ^{2 (nj)} ej ∴ (α ⁿⁱ S ₀ + S ₁ ) (α ⁿⁱ S ₂ + S ₃ ) ＝ (α ⁿⁱ S ₁ + S ₂ ) ² (S ₀ S ₂ ＋ ▲ S ² ₁ ▼) α ^{2 (nj)} + (S ₀ S ₃ + S ₁ S ₂ ) α ⁿⁱ + (S ₁ S ₃ + ▲ S ² ₂ ▼) = 0 Here, A = S ₀ S ₂ ＋ S ² ₁ ▼ B = S ₀ If S ₃ + S ₁ S ₂ C = S ₁ S ₃ + ▲ S ² ₂ ▼ and (α ^nj = α ^{n-i + a} ), then D = B / A = α ⁿⁱ + α ^nj = α ⁿⁱ (1 + α ^a ) E = C / A = α ⁿⁱ・ α ^nj = α ^{2 (ni)}・ α ^a ∴D ² / A = α ^-a + α ^a , and 1 + α ^a and 1 + α ^-a using the conversion table stored in the ROM. Ask for. By this, Is required. The error positions i and j are obtained from α ^nj and α ⁿⁱ by the conversion table. If the error symbols in the received data sequence are Die and Dje, error correction is performed by Die + ei = Di Die + ej = Dj.

In case of 1-symbol error: Since the syndrome is S ₀ = ei S ₁ = α ⁿⁱ ei S ₂ = α ^{2 (ni)} ei S ³ = α ^{3 (ni)} ei, the error position i and error pattern ei are Required by.

α ⁿⁱ = S ₁ / S ₀ ei = S ₀ Here, the operation on GF (2 ^m ) will be described. If one symbol of digital data is, for example, 8 bits, this one symbol on GF (2 ⁸ ). Treat as a vector representation of the element. For example, (01001010) = α ³⁸ . This way, GF
The addition (α ^x + α ^y ) above (2 ⁸ ) can be expressed by supplying each element of this vector expression to an exclusive OR gate (abbreviated as EXOR gate). Also, the multiplication (α ^x ·
α ^y ) cannot be performed as a vector expression,
It can be realized by the product of the vector representation of the matrix representation T ^x and alpha ^y of alpha ^x. That is, α ^x · α ^y = T ^x · α ^yT where α ^yT is a vertical vector of the vector representation of α ^y , Is.

As another method of realizing the multiplication, using a conversion table,
There is a method in which x, y is obtained from α ^x , α ^y , (x + y) (mod.255) is calculated, and (α ^{x + y} ) is obtained using an inverse conversion table.

FIG. 1 shows the overall construction of an embodiment of the present invention. 1
Byte-serial input data having a symbol of, for example, 8 bits and encoded by the (n, n-4) Reed-Solomon code is supplied to the 2-block delay circuit 1 and the syndrome generation circuit 2. 1 block is, (n-4) information symbols _{D 1, D 2, ... D} n-4 and four parity symbols _{P 0, P 1, P 2} , P 3
And n symbols in total. In this example, a period of 1 block is assigned to each of the process of generating the syndrome and the process of calculating the error position and the error pattern. The delay circuit 1 is composed of, for example, a RAM, and is supplied with a write address and a read address from the address counter 3, and the read address has a delay of 2n with respect to the write address, thereby realizing a delay of 2 blocks. ing.

FIG. 2A shows input data sequentially supplied to the first block, the second block, and the third block. Each symbol of the second block is appended with ′, and each symbol of the third block has “″. Syndrome generation circuit 2
As shown in FIG. 2B, the syndromes S _{0 to} S ₃ of the first block are output at the timing when the input of the data of the first block is completed, and the input of the data of the second block is completed. Syndrome S'of the second block
₀ to S _'3 is output. The syndrome generation circuit 2
It is required to operate at the data rate of the input data in order to calculate the symbols of the continuously input data to form the syndrome. Therefore, as will be described later, the syndrome generation circuit 2 is composed of a hard-wired circuit.

The syndrome from the syndrome generation circuit 2 is supplied to the error position / error pattern calculation circuit 4. The error position and error pattern relating to the first block are made during the period when the data of the second block is being input. Since there is a margin for this one block period, the error position / error pattern calculation circuit 4 has a circuit configuration of a program stored system as will be described later. As an example, if the i, j symbol in the first block is an error symbol,
As shown in FIGS. 2C and 2D, the error position / error pattern calculation circuit 4 outputs the data of the error positions i, j and the error patterns ei, ej during the period of the third block.

The data at the error positions i and j are supplied to the comparison circuit 5 and compared with the read endless from the address counter 3.
When the two pieces of input data coincide with each other, the comparison circuit 5 generates a comparison output having a high level, as shown in FIG. 2E. The comparison output of the comparison circuit 5 is supplied to the selector 6.
The error pattern data and the output data of the delay circuit 1 are
It is supplied to the EXOR gate 7, and the output data of the EXOR gate 7 and the output data of the delay circuit 1 are selected by the selector 6 to be output data.

FIG. 2F shows the output data of the delay circuit 1, and Die and D
je represents an error symbol. This error symbol is corrected in the EXOR gate 7, the error-corrected symbols Di and Dj are selected by the output of the comparison circuit 5 (FIG. 2E), and the output of the selector 6 is as shown in FIG. 2G. The output data of the first block after error correction is obtained.

FIG. 3 shows an example of the syndrome generation circuit 2 in this embodiment. As described above, in order to perform the multiplication on GF (2 ⁸ ) necessary for forming the syndrome, α ¹ , α ² , α ³
Transforms each of the to the elements of T ¹ , T ² , and T ^{3 in} the matrix representation
ROMs 11, 12, and 13 are provided. The EXOR gate 20 and the 8-bit register 30 are for forming the syndrome S _{0. The} EXOR gate 20 has the input data and the register 30.
The output of is input. ROM11, EXOR gate 21 and 8-bit register 31 form syndrome S ₁
2, the register 32 of the EXOR gate 22 and 8-bit syndrome S ₂ are formed, the syndrome S ₃ is formed by ROM 1, the EXOR gate 23 and 8 bits of the register 23. That is, the ROMs 11, 12, and 13 convert the respective outputs of the registers 31, 32, and 33 into respective elements of the matrix representation and convert the EXOR gates 21, 22, and 23.
Feed back to.

The syndrome generating circuit 2 shown in FIG. ₃ outputs the syndromes S _{0 to} S ₃ represented by the following equations when n blocks of 1 block are supplied.

S ₀ = D ₁ ＋ D ₂ ＋… ＋ D _n-4 ＋ P ₃ ＋ P ₂ ＋ P ₁ ＋ P ₀ S ₁ ＝ D ₁・ α ^n-1 + D ₂・ α ^n-2 ＋ ・ ・ ・ ＋ D _n-4・ α ⁴ + P ₃ α ³ + P ₂ · α ² + P ₁ · α + P ₀ S ₂ = D ₁ + α ^{2 (n-1)} + D ₂ · α ^{2 (n-2)} +… + D _n-4 · α ⁸ + P ₃ · α ⁶ + P ₂・ Α ⁴ + P ₁・ α ² + P ₀ S ₃ = D ₁ + α ^{3 (n-1)} + D ₂・ α ^{3 (n-2)} +… + D _n-4・ α ¹² + P ₃・ α ⁹ + P ₂・ α ⁶ + P ₁ · α ³ + P ₀ FIG. 4 shows a specific configuration of the error position / error pattern calculation circuit 4 to which the above-mentioned syndromes S _{0 to} S ₃ are supplied.
In FIG. 4, 40A, 40B, 40C and 40D are data buses. A program counter 41 is cleared for each block, incremented for each clock, and the value of the jump address memory 42 is loaded by a jump instruction. The jump address memory 42 outputs the jump address according to the flag register 43 when a jump instruction is generated. The flag register 43 inputs the result of the comparator 44 when a comparison instruction is generated, and
It is a shift from the previous flag. comparator
44 compares the data on the data bus 40D with a given value and produces a high level output when the former is greater than the latter. 45 is the program memory, and the program counter 41
The micro-instruction for controlling the entire circuit is generated from the program memory 45 by the address from. The program memory 45 is composed of ROM or RAM.

46,47,48,49 are synchronous load registers,
Register 46, 47, 48 is data bus 40D by load instruction
Data is latched in, and the register 49 latches the output data of the function memory 66. These registers 46-
The output of 49 is supplied to the data bus 40A via the buffers 50A, 51A, 52A and 53A, and is output to the data bus 40B via the buffers 50B, 51B, 52B and 52B. ALU (arithmetic circuit) 54
Is for performing arithmetic processing on the data selected by the buffers 50A to 53A and the data selected by the buffers 50B to 53B. The ALU54 uses the control signal to
Binary addition operation, EXOR gate (addition of mod.2) operation and AN
This is a configuration in which the operation of the D gate can be switched. 55
Reference numerals 56 and 56 are registers with an out enable, which output the output of the function memory 66 and the output of the ALU 54 to the data bus 40C by a gate command.

Reference numerals 57, 58, 59 and 60 are conversion ROMs to which the syndromes S _{0 to} S ₃ from the syndrome generation circuit 2 are supplied. That is,
When (S ₀ = α ^k , S ₁ = α ^l , S ₂ = α ^m , S ₃ = α ⁿ ), RO
Each of M57-60 outputs k, l, m, n. This ROM57 ~ 6
Outputs of 0 are supplied to the out-enable registers 61, 62, 63 and 64, respectively, and output to the data bus 40D by a gate command. Reference numeral 65 is also a register with an out enable, and is for outputting the output of the function memory 66 to the data bus 40D. 67, 68, 69 and 70 are synchronous load registers, which can be loaded with data buses 40C and 40D by a load instruction.
Latch data from. Registers 67 and 68 latch the data at error locations ni and nj and register 69
And 70 latch the data of the error patterns ei and ej.

The function memory 66 has 8 banks, and the contents are assigned by the upper 3 bits of the address (represented by 0 to 7) as follows.

A table for converting 0,1: x ′ into α ^x .

A table that converts 2,3: x ′ to x in (mod.255).

4: A table that converts α ^x to x.

5: A table for converting α ^x to −x.

6: A table that converts Z to -x.

7: A table for converting -x to -y.

However, x'is 9 bits in the output of the full adder. Further, (α ^x = 1 + α ^a , α ^y = 1−α ^a ), and (α ^Z
= Α ^−a + α ^a ).

The above-mentioned calculation of the error position and the error pattern is performed by the calculation shown in the above equation. First, from the syndrome, calculate A = S ₀ S ₂ + ▲ S ² ₁ ▼ = α ^a B = S ₀ S ₃ + S ₁ S ₂ = α ^b C = S ₁ S ₃ + ▲ S ² ₂ ▼ = α ^c To do. FIG. 5 is a flow chart of this processing, in which + is an adder, is an EXOR gate operation, Is a conversion operation when the upper 3 bits of the function memory 66 are k, and the duty 'indicates that the result of the adder is 9 bits. The flow once shows the order from left to right in the figure. First, the ROMs 57 to 60 convert the syndromes S _{0 to} S ₃ into k, l, m, n, and the ALU 54 outputs (k +
m) ', (l + l)', (k + n) ', (l + m)',
(L + n) 'and (m + m)' are calculated. This ALU54
Is supplied to the function memory 66 via the register 56 and the data bus 40C. Juan Simon Memory
66 uses the table when the value of the upper 3 bits is 0 to generate the illustrated output. The output of the function memory 66 is the register 49, buffers 53A, 53B and the data bus 40A,
Input to ALU54 via 40B. The ALU 54 generates an EXOR output of both inputs, and this output is supplied to the function memory 66 via the register 56 and the data bus 40C. The function memory 66 has a value of the upper 3 bits of 5,
Data conversion is performed using the table for 4 and 4, −a,
Outputs of b and c are obtained. The operations of this calculation and data conversion are performed by time division multiplexing.

Next, D = B / A = α ^d E = C / A = α ^e D ² / E = α ^-a + α ^a → 1 + α ^a = α ^x , 1 + α ^-a = α ^y D, E, 1 + α ^{Calculate a} , · 1 + α ^-a . The flow of processing at this time is shown in FIG. The arithmetic operation in this flow is performed by the ALU 54, data conversion is performed by the function memory 66, and arithmetic operation or data conversion is performed by time division multiplexing.

Further, as the step of FIG. 3, α ⁱ = D / α ^x α ^j D / α ^y The error positions i, j and the error patterns ei, ej represented by FIG. 7 is a flow chart of calculation and data conversion performed by time division multiplexing at this stage.
The data of the error positions i and j are latched in the registers 67 and 68, and the data of the error patterns ei and ej are latched in the registers 69 and 70.

“Application Example” The present invention is not limited to the error correction of the Reed-Solomon code, but is also applicable to other error correction codes for generating an error position and an error pattern from the syndrome by generating a syndrome from a received data sequence, for example, error correction of an adjacent code. It can be applied. In this case, it is possible to deal with this by simply changing the program of the error position / error pattern calculation circuit 4 of the above-described embodiment.

[Advantages of the Invention] According to the present invention, since the syndrome is generated by the hard-wired circuit configuration and the error position and the error pattern are calculated by the program stored system circuit configuration, the error correction of the high-speed data is performed. This makes it possible to reduce the circuit scale and to provide versatility with respect to the types of codes, unlike the case where the hard wired system is used for all operations.

[Brief description of drawings]

FIG. 1 is a block diagram showing the construction of an embodiment of the present invention,
FIG. 2 is a time chart used for explaining the operation of one embodiment of the present invention, FIG. 3 is a block diagram of the syndrome generation circuit in one embodiment of the present invention, and FIG. 4 is an error position in one embodiment of the present invention. Block diagrams of the error pattern calculation circuit, FIGS. 5, 6, and 7 are flow charts used to explain the operation of the error position and error pattern calculation circuit. 2 …… Syndrome generation circuit, 4 …… Error position, error pattern calculation circuit, 7,20,21,22,23 …… Exclusive OR gate, 40A, 40B, 40C, 40D …… Data bus, 45 ……
Program memory.

Claims (1)

[Claims] 1. Input data divided into blocks consisting of a predetermined number of information symbols and parity symbols,
When the syndrome is generated from the one including the redundant data of the error correction code, at the time when the data input of each block is completed, the syndrome generation circuit of the hard-wired system that generates the syndrome of the block and the writing of the input data On the other hand, the delay circuit delaying the reading by two blocks and the error position of the block immediately before the block while being controlled by the program stored in the program memory, while the data of the predetermined block are being input. An error correction circuit comprising: an arithmetic circuit that calculates an error pattern from the syndrome; and a correction circuit that corrects a symbol at the error position in the input data.