JPH077919B2 - Binary information conversion circuit - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a binary information conversion circuit of an error correction unit using a Reed-Solomon code according to the present invention.

ART information sequence a _0, a _1, indicating ......, ak _-1 polynomial expression S (x) with the following equation.

S (x) = a ₀ xk ^-1 ＋ a ₁ xk ^-2 ＋ …… ak _-2 x ＋ ak _-1 ……
(1) Generate a codeword using the m-th order generator polynomial G (x) of the Reed-Solomon code, and express it in polynomial form as F ₁ (x)
Is shown by the following equation.

_{F 1 (x) = a 0} xn -1 + a 1 xn -2 + ...... ak -1 xn - k + b 0 xm -1 + ...... + bm -2 x + bm -1 ...... (2) where k is the information unit , M is the length of the check code, and n is the length of the codeword (n = m + k).

The code word generated in this way is used as a transmission signal and transmitted, and the receiving side corrects the error that occurred during transmission by the check code. Error correction is performed by generating syndromes and calculating error position information and error patterns. The error position information obtained here is, for example, n− as the error position information when a ₁ is incorrect in Expression (2).
2 is obtained. By the way, when correcting, it is necessary to calculate the address value of the memory in which a ₁ is stored from the error position information. Generally, in the memory, a ₀ is written in address 0, a ₁ is written in address 1, ... Therefore, when the code length n is 28, 0 → 27, 1 → 26, ...
The error position information must be converted into the actual memory address value, such as 26 → 1, 27 → 0. As a circuit that realizes the above operation, RO as shown in FIG.
It is possible to use M. EL0 as input to ROM
After the conversion was carried out in the ROM consists of 5 bits of error position information ～EL4, and outputs the A ₀ to A ₄ as an address signal.

Problems to be Solved by the Invention In the configuration using the ROM as described above, the data in the ROM must be changed when the code length changes. Therefore, when considering the LSI, if the ROM is built in, the code length must be fixed, and the versatility is lost. There are many problems such as having to attach an external ROM to maintain versatility.

In consideration of such a problem, the present invention provides a binary information conversion circuit suitable for LSI without using a ROM.

Means for Solving Problems When the address signal of the memory is generated from the error position information obtained from the syndrome, the present invention uses the code length n of 1
A memory for storing a code word from the error position information, comprising means for inverting each bit of the binary information obtained by subtraction, means for adding the inverted result and error position information, and means for inverting the added result. 2 is a binary information conversion circuit for generating the address signal.

Action As described above, the present invention can be realized with a simple circuit configuration by generating an address signal with an inverter and an adder.

First, a Reed-Solomon code which is an error correction code used in the present invention will be described. Considering the irreducible polynomial F (x) of degree 1 on GF (2), since there are only elements of "0" and "1", F (x) has no root on GF (2). . Therefore, consider a root α that satisfies F (x) = 0. At this time, 2n different elements 0, α represented by the power of α including zero element
⁰ , α ¹ , ..., α ² l ^-2 form the extension field GF (2l). GF
Each element of (2l) can be expressed as a linear combination of α ⁰ (= 1), α ₁ , α ² , ..., α l ^-1 .

Now, the information by a _0, a _1, ......, when polynomial representation of ak _-1, as described above (1) _{S (x) = a 0 xk} -1 + a 1 xk -2 + ...... ak -2 x ＋ ak _-1 ……
(1) M-th order generator polynomial G (x) of Reed-Solomon code
Is It is expressed as equation (3). The code words obtained by this generator polynomial G (x) are m check codes, and the minimum distance (m +
It becomes 1). To generate a codeword, first xmS (x)
Is divided by the generator polynomial G (x) to obtain the remainder R (x).
At this time, xmS (x) = Q (x) G (x) + R (x) (4) where the quotient is Q (X). If F ₁ (x) = xmS (x) + R (x), then F ₁ (x) = xmS (x) + R (x) = Q (x) G (x).
(5) and F ₁ (x) is divisible by G (x). F _{1 at} this time
Each coefficient string in (x) represents a code word. The remainder R (x) is R (x) = b ₀ xm ^-1 + b ₁ xm ^-2 + ...... bm _-2 x + bm _-1 ......
When (6), polynomial representation F ₁ codeword (x) is _{F 1 (x) = a 0} xn -1 + a 1 xn -2 + ...... + ak -1 xn - k + b 0 xm -1 + ...... + bm _-2 x + bm _-1 It becomes (2). Here, n indicates a code length. (N = m + k) Considering this codeword as a transmission signal sequence, the original information sequence a ₀ , a ₁ ,
The check code string b ₀ , b ₁ , ..., bm _-1 is added to ... ak _-1 and transmitted.

The received signal sequence is F ₂ (x), and the error sequence generated during transmission is e
When (x), the following equation is established.

F ₂ (X) = F ₁ (x) + e (x) (7) On the receiving side, a syndrome is generated to check whether or not there is an error that occurred during transmission. The syndrome can be obtained as a remainder obtained by dividing the received signal sequence by the generator polynomial G (x).

As a specific example, when the fourth generation polynomial of Expression (8) is used, G (x) = (x−α ⁰ ) (x−α ¹ ) (x−α ² ) (x
-Α ³ ) (8) At this time, the syndromes S ₀ , S ₁ , S ₂ , and S ₃ are represented by the equation (9).

In this case, if the error is up to two points, the error position and the error pattern can be obtained.

The polynomial expression F ₂ (x) of the received signal is expressed by the following equation.

here, Indicates the received information of the original information ai, bi.

Now, assuming that the error pattern is ei, ej, F ₂ (x) = F ₁ (x) + eixi + ejxj (11) is obtained. Therefore, the following equation is obtained from the syndrome.

The error pattern ei, ej and the error position i, j can be calculated from the equation (12).

Consider the case of FIG. 2 as the signal format. When the error correction is completed in units of N blocks, the length of one block is 32, and the two-series Reed-Solomon codes C ₁ and C ₂ take a generation sequence in the direction of the arrow in the figure, and both have a length of 4 And

On the receiving side, once the received signals for N blocks are written in the memory, error correction is performed in the order of C ₁ and C ₂ . At that time, the signal is sequentially read for each generation sequence. For the sake of convenience, the signal format of FIG. 2 is arranged in the memory as it is, the vertical position is specified by the lower 5 bit address signal, and the position in the block direction (horizontal direction) is specified by the 6th bit or more address signal. Shall be specified. By the way, in the received signal represented by the equation (10), in the C ₁ generation sequence, as shown in FIG. 3 (a), the address signal of the lower 5 bits is d _{31 at} the place of 0, 1, 2 ,. The signals of, d ₃₀ , d ₂₉ , ... Will be written. For example, if d ₂₉ is erroneous, i = 29 is obtained as a result of calculating the error position, but it must be converted to an address on the memory when correcting the error. That is, in the column of FIG. 3 (a), it is necessary to use address 2 of the lower 5 bits instead of i = 29.
Similarly, the error position calculated to be 0 → 31, 1 → 30, ..., 30 → 1, 31 → 0 is converted into a memory address value. FIG. 3 (b) shows a C ₂ generation sequence. The length of the code word of C ₂ is 28. Therefore, in this case, from the error position information obtained, 0 → 27,1 → 27,2 → 25, ……, 26 → 1,27 → 0 I have to convert.

FIG. 1 shows a binary information conversion circuit according to the present invention. Reference numeral 1 is an inverter, 2 is a 5-bit binary adder, and 3 is an inverter. Inverter 1 minus 1 from code length 2
Enter the base information. If n is 28, 11011 is input. At this time, the output of the inverter 1 becomes 00100. When the error position information is 24, that is, when the binary representation is 11000, 11100 is obtained as an output by the adder 2. Therefore, the inverter 3 obtains 00011 as an address signal and 3 in decimal notation. If the code length is 28, this is converted from 24 to 3, so it can be seen that the operation is normal. The circuit configuration of FIG. 1 can handle code lengths up to 32, but when more code length is required, it can be adapted by increasing the number of bits. For example, if the code length is 50, the configuration of 6 bits in FIG. 1 may be used. At this time, even if the code length is 28, the binary information value obtained by subtracting 1 from the code length may be 011011.

EFFECTS OF THE INVENTION As described above, according to the present invention, by implementing a binary information conversion circuit by an inverter and an adder, the circuit can be simplified without using a ROM and can be suitable for LSI implementation. . Further, even if the code length is changed, it can be realized with the same circuit configuration, and the practical effect is great.

[Brief description of drawings]

FIG. 1 is a circuit diagram of a binary information conversion circuit according to an embodiment of the present invention, FIG. 2 is a signal format diagram showing an error correction code generation sequence, and FIG. 3 is an explanatory diagram of an address conversion operation.
FIG. 4 is an explanatory diagram showing a conventional binary information conversion circuit. 1 ... Inverter, 2 ... Adder, 3 ... Inverter.

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Hirotake Takeuchi 1006 Kadoma, Kadoma City, Osaka Prefecture Matsushita Electric Industrial Co., Ltd. (56) Reference JP-A-58-66159 (JP, A)

Claims (1)

[Claims] 1. When performing error correction using a Reed-Solomon code, when the length of the code word is n (n is a positive integer), means for inverting the binary information of (n-1) and inversion. Result and error position information i (i is a positive integer and 0 ≦ i <
n) binary means for adding the binary information and means for inverting the addition result, and converting the error position information i into address information (ni-1) of the memory in which the code word is stored. Information conversion circuit.