JPS6135731B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a system for automatically detecting and correcting bit errors that occur during transmission and storage of digital data.

Error correction coding technology is used as a method for automatically correcting errors that occur during data transmission and storage. There are various types of error correction codes used for this purpose, but among them, BCH (Bose-Cyodory-Hotsking Diem) code has a large degree of freedom in selecting the code length and error correction ability, and also It is known as a code with excellent error correction ability. The present invention is a BCH code that can correct bit errors when one code word has three or less errors, that is, a 3-error correcting BCH code. The present invention relates to a correction device, that is, a decoding device.

Here, we will briefly explain the 3-error correction BCH code.

3 In the error correcting BCH code, the code word C is k
information bits (a ₁ , a ₂ , ..., a _k ) and q check bits (a
_k+1 , a _k+2 ,..., a _k+q ). In other words, the sign error is: = (a ₁ , a ₂ , ..., a _k , a _k+1 , ..., a _{k +q} ).

However, k is determined so that k=2 ^m −3m−1 q=3m where m is an integer of 4 or more. Hereafter code length k=q=2 ^m
-1 is represented by n. That is, the code word 〓 becomes 〓=(a ₁ , a ₂ , . . . , a _o-1 , a _o ). The check bits are determined so that the code word satisfies H 〓 ^T =0. Here 〓 ^T is the transposed vector of 〓. H is a parity check matrix and GF
Using the primitive element α of (2 ^m ), It is expressed as Each element α ^w (w=0, 1,
..., n-1) is represented by a column vector of m elements.

Now suppose that an error occurs in 〓 and it becomes 〓′.

〓′=(a′ ₁ , a′ ₂ , . . . , a′ _o-1 , a′ _o ) 〓′ is expressed by 〓 and the error vector e as follows.

〓'=〓+e where 〓 is a vector consisting of elements that are 1 at the position of the error bit of 〓' and 0 at other positions.

〓 = (e ₁ , e ₂ , ...e _o-1 , e _o ) When 〓' is given, decoding is to reproduce the original 〓, and the present invention proposes a new device to realize this. It is something to give.

Decoding of the conventional 3-error correction code is normally performed by the method described below.

First, the first, second, and third syndromes defined by the following equations, ie, A ₁ , A ₂ , and A ₃ are calculated.

Syndromes A ₁ , A ₂ and A ₃ are e.g. FJ
“The Theory of
Error―Correcting Codes, Part” (North
Holland Publishing Company) pp. 270-272. In other words, the first syndrome _A1 inputs the bits of the feedback shift register C' corresponding to the minimum polynomial of α from a' ₁ to a' _o , and is completed in the shift register when a' _o is input. . The second syndrome _A2 inputs C' to the feedback shift register corresponding to the minimum polynomial of ^α3 , and performs exclusive OR of the bit string created in the shift register when the last bit is input. It can be obtained by converting using a circuit. Similarly, the third syndrome _A3 is a feedback shift register corresponding to the minimum polynomial of ^α5 .
It is obtained by inputting C' and converting the bit string created in the shift register when the last bit is input using an exclusive OR circuit. Next, using these A ₁ , A ₂ and A ₃ , the error locator polynomial σ
Find (Z).

σ(Z)=1+A ₁ Z (When A ₁ ³ +A ₂ = 0) Substitute α ^t (t=1, 2,..., n) for this σ(Z), and get σ(Z)=0. Assuming that the value of t indicates the position of an error, error correction is performed by inverting the bit at that position. The above is the decoding operation performed by the conventional decoding device. However, in this method, σ
A relatively complicated device is required to obtain each series of (Z), and it is time consuming.

Therefore, an object of the present invention is to provide a three-error correction code decoding system that can be decoded in a short time using a relatively simple device.

Next, the decoding operation performed by the decoding device of the present invention will be explained.

In the decoding device of the present invention, the first, second, and third syndromes A ₁ , A ₂ , and A ₃ are first calculated, as in the conventional method. Next, A ₁ ³ +A ₂ is calculated using the first syndrome A ₁ and the second syndrome A ₂ . A ₁ ³ can be calculated by inputting A ₁ into a cuber using a ROM table or the like. Addition of A ₁ ³ and A ₂ can be easily realized using an exclusive OR circuit. Furthermore, α ^nt , α ^3(nt) and α ^5(nt) are generated sequentially from t=1 to n. α ^nt is the bit string 1, α ^3
(nt) is represented by bit example 2, and α5 ^(nt) is represented by bit string 3. To generate α ^nt, for example, set the initial value α ⁿ = 1 to the feedback shift register corresponding to the minimum polynomial of α and shift it t times, as described in Coding Theory (Shokodo) by Miyagawa et al., p. 119. Then, α ^nt can be obtained. α ^3(nt) can be obtained by inputting α ^nt to a cuber using a ROM table, for example. α ^5(nt) is similarly obtained by inputting α ^nt to the fifth power. Or, set the initial value α ³ⁿ = α ⁵ⁿ = 1 in a shift register circuit that multiplies α ^-3 or α ^-5 in one shift, as described in Coding Theory by Miyagawa et al. (Shokodo) p. 120. It can be obtained by shifting t times. For each value of t, the first syndrome A ₁ , the second syndrome A ₂ ,
Third syndrome A ₃ , α ^nt , α ^3(nt) , and α
S ₁ , S ₂ and S ₃ defined by the following formula using ^5(nt)
Calculate.

S ₁ = A ₁ + α ^nt S ₂ = A ₂ + α ^{3 (nt)} S ₃ = A ₃ + α ^{5 (nt)} S ₁ is bit string 4, S ₂ is bit string 5, S ₃ is bit string 6. expressed. Addition of A ₁ and α ^nt , A ₂ and α ³
The addition of ^(nt) and the addition of A ₃ and α ^{5 (nt)} are easily realized by an exclusive OR circuit. Next, EL(t) defined by the following equation is calculated.

EL(t)=S ₁ ⁶ +S ₂ ² +S ₁ ³ S ₂ +S ₁ +S ₃ EL(t) calculates S 1 to S ₁ ⁶ from S ₁ using a 6th power circuit composed of a ROM table. Calculate S 2 2 from S ₂ with a square circuit, and calculate S ₂ ² from S ₁ and S ₃ with a cube and product circuit configured with a ROM table.
Calculate S ₁ ³ S ₂ , calculate S 1 S 3 from S ₁ and S ₃ using a product circuit also configured with a ROM table, and calculate S ₁ S 3 from S ₁ ⁶ and S _{2 2} ^.
It can be obtained by adding S ₁ ³ S ₂ and S ₁ S ₃ using an exclusive OR circuit. If the above A ₁ ³ + A ₂ is 0, then
Check the value of S ₁ for each value of t. At t when S ₁ = 0, the t-th bit in C' is a' _t . Assuming that the t-th bit in C' is an _error , a ' _t is inverted to correct the error, and if A ₁ ³ + A ₂ is not 0, check the value of EL(t) for each t value and calculate C at t where EL(t) = 0. The decoding operation performed by the decoding apparatus of the present invention is to correct the error by inverting a' _t , assuming that the t-th bit a' _t in ' is an error. In this decoding operation, a relatively simple operation is repeated for each bit of the codeword.
Since there is no complicated operation such as finding the error locator polynomial in the conventional decoding method, the device becomes simpler.

It will be shown below that by this operation, correct error correction is always performed when the number of error bits is 3 or less.

First, let's assume that there is not even a single bit wrong. At this time, A ₁ =A ₂ =A ₃ =0. Therefore, A ₁ ³ +A ₂ =0. Therefore, error correction is performed according to the value of S ₁ . By the way, S ₁ =A ₁ +α ^nt =α ^nt does not become 0 for any value of t. accordingly
No inversion is performed on any bit in C'.

Next, suppose that only the i-th bit a′ _i is wrong. At this time, A ₁ =α ⁿⁱ A ₂ =α ³⁽ⁿⁱ⁾ Therefore, A ₁ ³ +A ₂ =0 Therefore, error correction is performed according to the value of S ₁ .

At this time, S ₁ =A ₁ +α ^nt =α ⁿⁱ α ^nt S ₁ becomes 0 only when t=i, and does not become 0 when t≠i. Correct error correction is therefore performed.

Next, suppose that the i-th and j-th bits, ie, a' _i and a' _j , are errors. At this time, A ₁ = α ⁿⁱ + α ^nj A ₂ = α ³⁽ⁿⁱ⁾ + α ^3(nj) A ₃ = α ⁵⁽ⁿⁱ⁾ + α ^5(nj) A ₁ ³ +A ₂ = α ⁽ⁿⁱ⁾・α ^nj (α ⁿⁱ + α ^nj ) Since i≠j, A ₁ ³ +A ₂ ≠0 Therefore, error correction is performed according to the value of EL(t). At this time, S ₁ = A ₁ + α ^nt = α ⁿⁱ α ^nj + α ^nt S ₂ = A ₂ + α ^3(nt) = α ³⁽ⁿⁱ⁾ + α ^3(nj) + α ^3(nt) S ₃ = A ₃ + α ^{5 (nt)} = α ^{5 (ni)} + α ^{5 (nj)} + α ^{5 (nt)} EL (t) = S ₁ ⁶ + S ₂ ² + S ₁ ³ S ₂ + S ₁ S ₃ = α ⁿⁱ α ^nj α ^nt (α ⁿⁱ + α ^nj ) (α ^nt + α ⁿⁱ ) (α ^nt + α ^nj ) EL(t) becomes 0 only when t matches i or j, and does not become 0 when t takes other values. Correct error correction is therefore performed.

Next, suppose that the i-th, j-th, and l-th bits, ie, a' _i , a' _j , and a' _l , are errors. At this time, A ₁ = α ⁿⁱ + α ^nj + α ^nl A ₂ = α ³⁽ⁿⁱ⁾ + α ^3(nj) + α ^3(nl) A ₃ = α ⁵⁽ⁿⁱ⁾ + α ^5(nj) + α ^5(nl) A ₁ ³ +A ₂ = (α ⁿⁱ + α ^nj ) (α ^nj + α ^nl ) (α ^nl + α ⁿⁱ ) Since i≠j, j≠l, and l≠i, A ₁ ³ +A ₂ ≠0
Therefore, error correction is performed according to the value of EL(t).

At this time, S ₁ = A ₁ + α ^nt = α ⁿⁱ + α ^nj + α ^nl + α ^nt S ₂ = A ₂ + α ^3(nt) = α ³⁽ⁿⁱ⁾ + α ^3(nj) + α ^3(nl) + α ^3(nt) S ₃ = A ₃ + α ^{5 (nt)} = α ^{5 (ni)} + α ^{5 (nj)} + α ^{5 (nl)} + α ^{5 (nt)} EL (t) = S ₁ ⁶ + S ₂ ² + S ₁ ³ S ₂ + S ₁ S ₃ = (α ⁿⁱ + α ^nj ) (α ^nj + α ^nl ) (α ^nl + α ⁿⁱ ) (α ^nt + α ⁿⁱ ) (α ^nt + α ^nj ) (α ^nt + α ^nl ) EL(t) means that t is i, j, or l. It becomes 0 only when there is a match, and it does not become 0 when t takes other values. Correct error correction is therefore performed. As can be seen from the above, if the number of error bits is 3 or less, correct decoding is always performed.

Next, a decoding device according to the present invention will be explained with reference to drawings of embodiments. As described above, the decoding device of the present invention handles elements of a Galois field in its decoding procedure. It is well known that any element of GF(2 ^m ) can be expressed as a linear combination of 1, α, α ² , α ^m-2 , α ^m-1 with α as the primitive element. In this embodiment, the elements of the Galois field are represented by m bits, which are the series of linear combinations. Of course, it is not necessary to unify the representation of the original bit string of the Galois field in the entire decoding procedure.
In fact, the device may be made slightly simpler by using partially different representations, but for the sake of simplicity, the above representation will be used here.

FIG. 1 is a block diagram showing the configuration of an embodiment according to the present invention. In FIG. 1, input data α is sent to a data buffer 101 and a first syndrome generation circuit 1.
02, the second syndrome generation circuit 104, and the third syndrome generation circuit 106.
The data buffer 101 is made up of a shift register with a total of n+1 bits, which is n bits long for one code word and 1 bit for holding a time signal necessary to transfer the syndrome generated by the syndrome generation circuit to the syndrome buffer. configured.
The first syndrome generation circuit 102 has GF(2 _n )
It consists of an m-stage feedback shift register corresponding to the minimum polynomial of the primitive element α. The second syndrome generation circuit 104 consists of a bit string conversion circuit composed of an m-stage feedback shift register corresponding to the minimum polynomial of ^α3 and an exclusive OR circuit. The third syndrome generation circuit 106 consists of a bit string conversion circuit composed of a feedback shift register corresponding to the minimum polynomial of ^α5 and an exclusive OR circuit. When the last bit of the code word has entered data buffer 101, the first, second, and third syndromes have been generated by each syndrome generation circuit. The first generated
The second and third syndromes are moved to the first, second and third syndrome buffers, respectively, before the next codeword is destroyed when it is input to the syndrome generation circuit. The first syndrome (A ₁ ) and the second syndrome (A ₂ ) are input to the correction condition determination circuit 108, and the correction condition determination circuit 108
It is determined whether A ₁ ³ +A ₂ is 0 or not, and if A ₁ ³ +A ₂ is 0, 0 is output, otherwise 1 is output and given to the selection circuit 117. Correction condition determination circuit is ROM
It consists of a cube circuit made up of a table, an addition circuit made up of an exclusive OR, and an OR circuit that determines whether the addition result is all 0 bits. The code word stored in data buffer 101 is output bit by bit starting from the first bit and input to error correction circuit 118. When the t-th (t=1, 2,...n) bit is output from the data buffer 101 and input to the error correction circuit 118, the power generation circuit 110 generates bit string 1, which is an m-bit string representing α ^nt . The power generation circuit 112 of ^α3 generates α
A bit string 2, which is an m-bit bit string representing .alpha.3 ^(nt) , is generated, and a power of ^.alpha.5 generating circuit 114 generates a bit string 3 representing ^.alpha.5(nt) . The power generation circuit 110 of α consists of a feedback shift register corresponding to the minimum polynomial of α. The ^α3 power generation circuit 112 is composed of a feedback shift register corresponding to the minimum polynomial of ^α3 . α ⁵
The power generation circuit 114 consists of a feedback shift register corresponding to the minimum polynomial of ^α5 . Bit string 1 and the first syndrome are added by exclusive ORing each corresponding bit by exclusive OR circuit 109, and bit string 4 representing S ₁ =A ₁ +α ^nt is generated. Similarly, bit string 2
and the second syndrome are added using an exclusive OR circuit 111 to generate a bit string 5 representing S ₂ =A ₂ +α ^{3 (nt)} . Further, bit string 3 and the third syndrome are added using exclusive OR circuit 113 to generate bit string 6 representing S ₃ =A ₃ +α ^{5 (nt)} . Bit string 4 is supplied to a first error detection circuit 115 and a second error detection circuit 116, and bit strings 5 and 6 are supplied to the second error detection circuit. The first error detection circuit 115 outputs 1 when _S1 is 0, otherwise outputs 0, and sends it to the selection circuit 115.
7, and is composed of an OR circuit and a NOT circuit. The second error detection circuit 116 inputs the bit string 4 representing S ₁ , the bit string 5 representing S ₂ , and the bit string 6 representing S ₃ , and outputs S ₁ ⁶ +S ₂ ² +
S ₁ ³ S ₂ + S ₁ If S ₃ is 0, set it to 1, otherwise set it to 0.
is outputted and given to the selection circuit 117.

FIG. 2 shows an example of the configuration of the second error detection circuit 116. In FIG. 2, bit string 4 is a sixth power circuit 201,
Bit string 5 is supplied to a cube and product circuit 203 and a product circuit 204; bit string 5 is fed to a square circuit 202 and a cube and product circuit 203; furthermore, bit string 6 is fed to a product circuit 204. The sixth power circuit 201 is S ₁ ⁶
A bit string 7 representing . Square circuit 20
2 produces a bit string 8 representing S ₂ ² . The cube and product circuit 203 is a bit string 9 representing S ₁ ³ S ₂
generate. Product circuit 204 generates a bit string 10 representing S ₁ S ₃ . 6th power circuit 201, 2nd power circuit 2
02, cube and product circuit 203, and product circuit 204
consists entirely of ROM tables. The exclusive OR circuit 205 performs addition by performing exclusive OR for each corresponding bit of bit string 7 and bit string 8, and creates a bit string 11 representing S ₁ ⁶ S ₂ ² . The exclusive OR circuit 206 performs addition by performing exclusive OR for each corresponding bit of bit string 9 and bit string 10, and creates bit string 12 representing S ₁ ³ S ₂ +S ₁ S ₃ . The exclusive OR circuit 207 performs addition by performing exclusive OR on each corresponding bit of bit string 11 and bit string 12, and produces a bit string representing S ₁ ⁶ +S ₂ ² +S ₁ ³ S ₂ +S ₁ S ₃ . Create 13. OR circuit 20
8 is obtained by taking the logical sum of all bits in bit string 13.
S ₁ ⁶ +S ₂ ² +S ₁ ³ If S ₂ +S ₁ S ₃ is 0, output 0, otherwise output 1. The NOT circuit 209 inverts the polarity of the output of the OR circuit 208 and makes S ₁ ⁶ +
S ₂ ² +S ₁ ³ S ₂ +S ₁ 1 if S ₃ is 0, 0 otherwise
Output. Returning to FIG. 1, the selection circuit 117 is composed of an AND circuit, an OR circuit, and a NOT circuit, and when the correction condition determination circuit 108 determines that A ₁ ³ +A ₂ = 0 and outputs 0, takes the output of the first error detection circuit 115 as its output, and if the correction condition determination circuit 108 determines that A ₁ ³ +A ₂ ≠ 0 and outputs 1, the second error detection circuit 11
Let the output of 6 be its output. Error correction circuit 118
is an exclusive OR circuit, and the data buffer 10
The exclusive OR of the t-th bit a' _t , which is the output of 1, and the output of the selection circuit 117 is calculated. Therefore, if the output of the correction condition determination circuit 108 is 0 and the output of the first error detection circuit 115 is 1, or if the output of the correction condition determination circuit 108 is 1 and the output of the second error detection circuit 116 is 1, In some cases, the output of the error correction circuit 118 is the inverted version of the t-th bit a′ _t that is the output of the data buffer 101, and in other cases, the output of the error correction circuit 118 is the output a′ _t of the data buffer 101 as it is. It is. The output u of the error correction circuit 118 becomes output data.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of an embodiment of a decoding device according to the present invention, and FIG. 2 is a block diagram of a second error detection circuit 11 in FIG.
This is a configuration example of No. 6. In the figure, 101 is a data buffer, 102 is a first syndrome generation circuit, 1
03 is the first syndrome buffer, 104 is the second
Syndrome generation circuit, 105 is a second syndrome buffer, 106 is a third syndrome generation circuit, 107 is a third syndrome buffer, 108
1009 is an exclusive OR circuit, 110 is an α power generation circuit, 111 is an exclusive OR circuit, 112 is an α ³ power generation circuit, 11
3 is an exclusive OR circuit, 114 is an ^α5 power generation circuit, 115 is a first error detection circuit, and 116 is a second
Error detection circuit, 117 is a selection circuit, 118 is an error correction circuit, 201 is a 6th power circuit, 202 is a 2nd power circuit, 203 is a 3rd power and product circuit, 204 is a product circuit,
205 is an exclusive OR circuit, 206 is an exclusive OR circuit, 207 is an exclusive OR circuit, 208 is an OR circuit, 209 is a NOT circuit, a is input data,
b is the first syndrome, c is the second syndrome,
d is the third syndrome, e is the bit string, f is the bit string 2, g is the bit string 3, h is the bit string 4, p is the bit string 5, r is the bit string 6, u is the bit string 7,
x is a bit string of 8, y is a bit string of 9, aa is a bit string
10, cc is bit string 12, dd is bit string 13, and is the decoded output.

Claims (1)

[Claims] Input sequence 〓′=(a′ ₁ ,
a' ₂ , a' ₃ ,...a' _o ), (n is the code length n = 2 ^m-1 , m is a natural number) and performs error correction by inputting them to the decoding device. 〓′ to the first syndrome A ₁ , the second syndrome A ₂ , and the third syndrome
Syndrome A ₃ ; is obtained using a shift register, and then A ₁ ³ +A ₂
= 0, then S ₁ = A ₁ + α ^nt (α is the primitive element of the Galois field GF (2 ^m ) consisting of 2 ^m elements, t is the number specifying the bit to be judged as an error, and n is If there is a value of t that makes 0 (a natural number not exceeding 0), then the corresponding input bit a′ _t is considered an error and is inverted, and the other input bits are output as they are, and if A ₁ ³ + A ₂ ≠ 0, then S ₁ =A ₁ +α ^nt S ₂ =A ₂ +α ^3(nt) S ₃ =A ₃ +α ^5(nt) EL′(t) = S ₁ ⁶ +S ₂ ² +S ₁ ³ S ₂ +S ₁ S ₃ =0 By inverting the input bits (a' _t1 , a' _t2 , a' _t3 ) corresponding to up to three given t values (t ₁ , t ₂ , t ₃ ) and outputting the other input bits as they are, , a three-error correction code decoding system characterized by correcting up to three errors.