Decoding Method for Multiple Bit Error Correction BCH Codes

The invention is concerned with an error correcting code decoding system for use in digital communication networks using error correcting codes where transmission errors are corrected automatically at the receiving station.

Of various kinds of error correcting code proposed so far, Bose-Chaudhuri-Hocquenghem code (in short BCH code) has been widely used in practice for its high degree of freedom for choosing code length and number of correctable errors, and its error correcting capability achieved with relatively few check bits.

A decoding process of the BCH code word is shown, for example, in Chapter 7.3 of "Coding theory" (by Miyagawa, Iwadare, and Imai; Shokodo Publishing Co.) where a received code word (it may have a bit error or bit errors) is first input to a feedback shift register whose structure corresponds to the code generator polynomial in order to obtain the syndromes. The syndromes thus obtained make it possible to derive an error locator polynomial by means of Peterson's method or Barenkampf-Massey's methods. The roots of the error locator polynomial indicate the error bit positions, if any, of the received code word, and the correction can be performed accordingly.

Several methods for deriving an error locator polynomial from given syndromes, other than one described above, have been known.

One of them is described in the following paper. (Koga: "A new decoding method of binary BCH code.", Trans. of the Institute of Electronics and Communication Engineers of Japan, Vol J 66-A, No. 10, pp. 925/932, October 1983)

This method shows that the coeffieicnts of the error locator polynomial of a received code word are calculated with symmetrical determinants whose elements are chosen from among the syndromes. And a useful method for calculating these determinants is proposed in the following paper. (Koga, Yamasaki: "A simple method of calculating the coefficients of error location polynomial in binary BCH code.", 1984 National Convention of the Institute of Electronics and Communication Engineers of Japan, 1456, March 1984)

This method shows that a determinant of order k of the kind is calculated by adding a certain number of products of determinant of order less than k and the square of syndrome.

The conventional methods for obtaining the error locator polynomial have a drawback in common that the procedure required for deriving it becomes too much complicated to be used in practice with increasing the number of correctable errors.

Therefore, almost all the error correction systems using the BCH code that have been used so far are limited to those of one-error correction or two-error correction.

It is an object, therefore, of the present invention to overcome the disadvantages and limitations of a prior error correction decoding system by providing a new and improved error correction decoding system.

It is also an object of the present invention to provide an error correction decoding system for deriving the error locator polynomial with simple circuitry and reduced quantity of calculation even when the number of correctable errors is relatively large.

According to the present invention, a Q determinant or a Q polynominal that gives the value of a coefficient of an error locator polynomial is calculated one by one, using those already claculated, and the A determinants or Q polynomials thus obtained determine the number of error bits, and all the coefficients of the error locator polynomial.

The foregoing and other objects, features, and attendant advantages of the present invention will be appreciated as the same become better understood by means of the following description and accompanying drawings wherein;

FIG. 1 shows a set of Q determinants that must be calculated to obtain a Q determinant denoted by [t.vertline.0],

FIG. 2 shows a set of Q determinants that must be calculated to obtain a Q determinant denoted by [t-1.vertline.0],

FIG. 3 shows a set of Q determinants that must be calculated to obtain three sets of Q determinants denoted by <t.vertline.0>.sup.c, <t.vertline.1>.sup.c, and <t-1.vertline.0>.sup.c,

FIG. 4 shows a set of Q polynomials that must be calculated to obtain a Q polynominal denoted by (t.vertline.0),

FIG. 5 shows a set of Q polynomials that must be calculated to obtain a Q polynomial denoted by (t-1.vertline.0),

FIG. 6 shows a set of Q polynomials that must be calculated to obtain three sets of Q polynomials denoted by <<t.vertline.0>>.sup.c, <<t.vertline.1>>.sup.c, and <<t-1.vertline.0>>.sup.c,

FIG. 7 is a construction diagram of the embodiment of an decoding system according to the present invention,

FIG. 8 is a construction diagram of the circuit for calculating an error locator polynomial in FIG. 7,

FIG. 9A shows a first portion of an example of controls performed by the Q determinant register control circuit and the syndrome register control circuit of FIG. 8,

FIG. 9B shows a second portion of the example of FIG. 9A, and

FIG. 10 is a construction diagram of the circuit for calculating an error locator polynomial in FIG. 7, where Q polynomials are used.

In the first place, a brief explanation of the t-error correcitng BCH code is given. In the t-error correcting BCH code, any of its code word, denoted by C, comprises k information bits (a.sub.1, a.sub.2, - - - , a.sub.k) and q check bits (a.sub.k+1, a.sub.k+2, - - - a.sub.k+q) that are calculated from the information bits. That is, a codeword C is represented as

where a.sub.i (i=1, 2, - - - , k+q) is either 0 or 1. And k, q are determined by the following equation.

where m is an integer and is chosen so that k may be positive. The code length, k+q=2.sup.m -1, will be denoted by n in the following.

The check bits of a code word C are determined by the following equation.

where H.sup.T is the transposed matrix of the check matrix H.

The check matrix H is given as follows. ##EQU1## where .alpha. is a primitive element of the Galois field GF (2.sup.m). Each element of the check matrix H is an element of GF (2.sup.m) and can be represented by a column vector with m elements.

Suppose a codeword C=(a.sub.1, a.sub.2, - - - , a.sub.n) changes to another vector Y=(y.sub.1, y.sub.2, - - - , y.sub.n) because of an error vector E=(e.sub.1, e.sub.2, - - - , e.sub.n). If an error took place at the ith position of C, then e.sub.i is given by 1, and if no error took place at the kth position of C, then e.sub.k is given by 0. That is, y.sub.i of Y is represented by the modulo-2 sum of a.sub.i of C and e.sub.i of E.

The decoding process is defined as restoring the initial code word C from a received word Y by means of the evaluation of error vector E. The invention provides a simple, efficient decoding system for the purpose.

As preliminary knowledge of the explanation to follow, let's explain the concept of a Q determinant and a Q polynomial briefly.

A determinant, denoted by Q.sub.t, whose elements are chosen from among the syndromes, is defined as follows. ##EQU2##

A determinant generated from Q.sub.t by removing all the pairs of a row and a column of Q.sub.t sharing one of specified diagonal elements of Q.sub.t is called a Q determinant. Q.sub.t is also a Q determinant. A Q determinant can be represented by simply noting the arrangement of its diagonal elements. For example, in the case of Q.sub.t, since it has all of S.sub.2, S.sub.4, - - - , S.sub.2t as diagonal elements it is represented by [1, 2, - - - , t], where S.sub.2i is denoted by i. A Q determinant generated from Q.sub.t by removing a row and a column sharing a diagonal element S.sub.2i and a row and a column sharing a diagonal element S.sub.2j is, likewise, represented by [1, 2, - - - , i-1, i+1, - - - , j-1, j+1, - - - , t]. In the representation of a Q determinant [b.sub.1, b.sub.2, - - - , b.sub.p ], it is assumed that b.sub.1 <b.sub.2 < - - - <b.sub.p. As explained above, [b.sub.1, b.sub.2, - - - , b.sub.p ] is the representation derived by noting the existing diagonal elements of Q determinant, (and will be called the first representation of a Q determinant). Inversely, it is also possible to represent a Q determinant by noting the lacking diagonal elements of the Q determinant. With this notation, a Q determinant can be represented as [v.vertline.c.sub.1, c.sub.2, - - - , c.sub.l ]. (This will be called the second representation of a Q determinant). [v.vertline.c.sub.1, c.sub.2, - - - , c.sub.l ] represents a determinant derived from Q.sub.v by removing all the pairs of a row and a column, each of which shares one of diagonal elements c.sub.1, c.sub.2, - - - , c.sub.l. In the above expression, v is called a head number and c.sub.1, c.sub.2, - - - , c.sub.l are called lacking elements. If there is no lacking element, it is represented by [v.vertline.0]. A representation where the head number is included in the set of lacking elements is also permitted. That is, if v is included in c.sub.1, c.sub.2, - - - , c.sub.l.

If v, v-1, v-2, - - - , v-i are included in c.sub.1, c.sub.2, - - - , c.sub.l then,

where d.sub.1, d.sub.2, - - - , d.sub.l-i-1 are obtained by removing v, v-1, v-2, - - - , v-i from c.sub.1, c.sub.2, - - - , c.sub.l.

Therefore, in general, the second representation of a Q determinant is not determined uniquely. But, the second representation of a Q determinant where the head number v is not included in the its lacking elements is uniquely determined. This is called a canonical representation. If it is necessary to emphasize that a second representation is canonical, c is put on the right shoulder of the expression, that is,

In a canonical representation, its head number and lacking elements are called a canonical head number, canonical lacking elements respectively.

Suppose that c.sub.1, c.sub.2, - - - , c.sub.l are l natural numbers that are different from one another and not exceeding v. The set of Q determinants represented by [v.vertline.c.sub.1, c.sub.2, - - - , c.sub.l ] is denoted by <v.vertline.l>. In the same way, if c.sub.1, c.sub.2, - - - , c.sub.l are l natural numbers that are different from one another and not exceeding v-1, then the set of Q determinants represented by [v.vertline.c.sub.1, c.sub.2, - - - , c.sub.l ] is denoted by <v.vertline.l>.sup.c. Apparently, <v.vertline.l> includes <v-i.vertline.l-i> (i=0, 1, 2, - - - , l). And <v.vertline.l> is the union of sets represented by <v-i.vertline.l-i>.sup.c (i=0, 1, 2, - - - , l).

Since a Q determinant is a symmetrical determinant, any element of which is a syndrome belonging to GF (2.sup.m), and since a diagonal element of it denoted by S.sub.2i can be expressed as S.sub.2i =S.sub.i.sup.2, it is always given as the square of a polynomial of syndromes. The root of a Q determinant, i.e., a polynomial of syndromes, is called a Q polynomial. As in the case of Q determinant representation, two kinds of representation are used for a Q polynomial. That is, the first representation of a Q polynomial is given by (b.sub.1, b.sub.2, - - - , b.sub.p) and the second representation is given by (v.vertline.c.sub.1, c.sub.2, - - - , c.sub.l). Naturally, the following relationships hold.

The terms such as "head number", "lacking element", "canonical representation" are equally used in the representation of Q polynomial. Moreover, in the quite same way as in the case of Q determinant, the set of Q polynomials represented by (v.vertline.c.sub.1, c.sub.2, - - - , c.sub.l) where c.sub.1, c.sub.2, - - - , c.sub.l are l natural numbers that are different from one another and not exceeding v, is denoted by <<v.vertline.l>>. Likewise, the set of Q polynomials represented by (v.vertline.c.sub.1, c.sub.2, - - - , c.sub.l) where c.sub.1, c.sub.2, - - - , c.sub.l are l natural numbers that are different from one another and not exceeding v-1, is denoted by <<v.vertline.l>>.sup.c. <<v.vertline.l>> includes <<v-1.vertline.l-i>> (i=0, 1, 2, - - - , l). The set <<vl.vertline.>> is the union of sets represented by <<v-i.vertline.l-i>>.sup.c (i=0, 1, 2, - - - , l).

The following equation concerning Q determinants holds.

(Koga, Yamasaki: "A simple method of calculating the coefficients of error location polynomial in binary BCH code.", paper no. 1456, 1984 National Convention of the Institute of Electronics and Communication Engineers of Japan, March 1984). ##EQU3## where p is greater than or equal to 3. If p is 2, the following equation holds.

In terms of Q polynomials, the following equation are obtained in place of (11) and (12). ##EQU4##

The relationship between Q determinants, Q polynomials and the error locator polynomial is explained below.

The error locator polynomial of a received word Y is defined as a polynomial whose roots are the error location numbers of the errors in Y. Each error location number indicates a position of Y where a bit error took place. If the number of error bits in Y, denoted by u, does not exceed t, and suppose bit errors took place at the i.sub.1 th, i.sub.2 th, - - - , i.sub.u th positions of Y, error position numbers are defined as

Suppose a polynomial of u-degree having u error location numbers of (15) as its roots is given as the following equation. ##EQU5## Squaring the equation (16), we get, ##EQU6## Coefficients appearing in the right-hand side of (17), i.e., .sub.u .theta..sub.i.sup.2 's are given by determinants as described in the paper below. (Koga: "A new decoding method of binary BCH code.", Trans. of the Institute of Electronics and Communication Engineers of Japan. Vol. J66-A, No. 10, pp. 925/932, October 1983).

Namely,

In terms of Q polynomials, equation (18) becomes as follows.

Therefore, if u, the number of error bits is determined, the coefficients of E.sub.u (x) or (E.sub.u (x)).sup.2 are obtained according to (18) or (19). Apparently, since E.sub.u (x) and (E.sub.u (x)).sup.2 have the same roots, either of them can be used as an error location polynomial in question. The number of error bits u can be estimated as described below.

(Koga: "A new decoding method of binary BCH code.", Trans. of the Institute of Electronics and Communication Engineers of Japan, Vol. J66-A, No. 10, pp. 925/932, October 1983).

That is,

if v=u or v=u-1 then [v.vertline.0].noteq.0 and

if v>u then [v.vertline.0]=0.

In terms of Q polynomials, the above rule becomes as follows.

if v=u or v=u-1 then (v.vertline.0).noteq.0 and

if v>u then (v.vertline.0)=0.

Therefore, the number of error bits u is obtained by the following process. Calculation of [v.vertline.0] or (v.vertline.0) is continued for a series of v's values that are decreasing and starting with t one by one, i.e., v=t, t=t-1, v=t-2, - - - . Then, at v=u [v.vertline.0] or (v.vertline.0) becomes non-zero for the first time in the calculation process.

Since the error locator polynomial E.sub.v (x) or (E.sub.v (x)).sup.2 can be used not only in v=u but in v=u+1, it is not necessary to determine the value of u uniquely.

The paper shows that it is also possible to estimate that either u=v.sub.0 or u=v.sub.0 +1 where v.sub.0 is obtained by the following process. That is, calculating [v.vertline.0] or (v.vertline.0) for a series of v's values starting with v=t-1 and decreasing with a common difference of 2, and finding v=v.sub.0 at which [v.vertline.0] or (v.vertline.0) becomes non-zero for the first time in the calculation process. (Koga: "A new decoding method of binary BCH code.", Trans. of the Institute of Electronics and Communication Engineers of Japan. Vol. J66-A, No. 10, pp. 925/932. October 1983.)

Since the number of error bits u of a received word is estimated by calculating Q determinants or Q polynomials and the corresponding error locator polynomial is also obtained by calculating Q determinants or Q polynomials, it is highly desireable to calculate Q determinants or Q polynomials efficiently with simple circuitry. The decoding system of this invention is characterized by efficient calculation of required Q determinants or Q polynomials with simple circuitry and with reduced quantity of calculation.

Let's explain the calculation method for Q determinants and Q polynomials of the invention. In the first place, consider the calculation of Q determinants.

As stated earlier, in order to estimate u, the number of error bits, at first [t.vertline.0] or [t-1.vertline.0] should be calculated. FIG. 1 shows all the Q determinants that should be calculated in the course of obtaining [t.vertline.0]. Likewise, FIG. 2 shows all the Q determinants that should be calculated in the course of obtaining [t-1.vertline.0]. In FIG. 1 and FIG. 2, a point whose coordinates of the horizontal axis and that of the vertical axis are given by v, l respectively represents the set of Q determinants <v.vertline.l>.sup.c. To obtain [t/0] it is necessary to calculate <v.vertline.l>.sup.c 's that are in the area enclosed with three lines, i.e., the horizontal axis, l=v-1, and l=-v+t one by one in the ascending order to v (To calculate <v.vertline.l>.sup.c means to calculate Q determinants in <v.vertline.l>.sup.c. Likewise, to obtain [t-1.vertline.0] it is necessary to calculate <v.vertline.l>.sup.c 's that are in the area enclosed with three lines, i.e., the horizontal axis, l=v-1 and l=-v+t-1 one by one in the ascending order of v. The order of calculations of <v.vertline.l>.sup.c 's having the same value of v is arbitrary. Furthermore the order of calculations of Q determinants in the same <v.vertline.l>.sup.c is also arbitrary. If the Q determinants are calculated in the order described above, the calculation of Q determinant can necessarily be carried out in one of the following three manners (a), (b), and (c).

(a) When <v.vertline.l>.sup.c which contains the Q determinant to be calculated is on l=v-1, <v.vertline.l>.sup.c is equal to <v.vertline.v-1>.sup.c and any Q determinant that belongs to it is a determinant composed of only one element. Therefore, the value of the Q determinant is obtained as the element itself which is a syndrome.

(b) When <v.vertline.l>.sup.c which contains the Q determinant to be calculated is on l=v-2, <v.vertline.l>.sup.c is equal to <v.vertline.v-2>.sup.c and any Q determinant that belongs to it is determinant of degree 2. Therefore, according to equation (12), the Q determinant can be calculated by using the syndrome and the Q determinant which was already calculated.

(c) When <v.vertline.l> which contains the Q determinant to be calculated is on neither l=v-1 nor l=v-2, any Q determinant that belongs to it is expanded according to equation (11) as follows. ##EQU7## Therefore, the Q determinant is obtained as the sum of v-l products, each of which is a product of the square of a syndrome and a Q determinant whose head number is v-1 and the number of lacking elements is l or l+1. It should be noted that any Q determinant whose head number, number of lacking elements are v-1, l, respectively, is contained in <v-1.vertline.l> and any Q determinant whose head number, number of lacking elements are v-1, l+1, respectively is contained in <v-1.vertline.l+1>. Since <v-1.vertline.l> is the union of <v-1-i.vertline.l-i>.sup.c (i=0, 1, - - - , l) and <v-1.vertline.l+1> is the union of <v-1-i.vertline.l+1-i>.sup.c (i=0, 1, - - - , l+1), both were calculated before the Q determinant in <v.vertline.l>.sup.c is calculated. Therefore, any Q determinant belonging to <v.vertline.l>.sup.c is obtained as the sum of products, each of which is a product of the square of a syndrome and a Q determinant that was already calculated.

In FIG. 1, when the calculation of <v.vertline.l>.sup.c 's in an area enclosed with the three lines is performed one by one in the ascending order of v up to <t.vertline.0>.sup.c not only [t.vertline.0] but also all the [i.vertline.0]'s (i=1, 2, - - - , t-1) are obtained in the course of calculation. Therefore, the number of error bits can be estimated using them. In the same way, in FIG. 2, when the calculation of <v.vertline.l>.sup.c 's is performed one by one in the ascending order of v up to <t-1.vertline.0>.sup.c not only [t-1.vertline.0] but also all the [t-1-2i.vertline.0] (i=1, 2, - - - , [t-1/2 ]) where x stands for a maximum integer not exceeding x, are obtained. Therefore, the number of error bits can be estimated using them as either u or u-1.

When the number of error bits is estimated as u, or it is estimated as either u or u-1, (E.sub.u (x)).sup.2 is generated as an error locator polynomial.

As equation (18) indicates, the coefficients u.theta..sub.i.sup.2 's (i=0, 1, 2, - - - , u,) of (E.sub.u (x)).sup.2 are given by Q determinants represented by [u.vertline.i]'s, which are contained in <u.vertline.0>.sup.c, <u.vertline.1>.sup.c, and <u-1.vertline.0>.sup.c. Accordingly, if u is equal to t, <t.vertline.0>>.sup.c <t.vertline.1>.sup.c, and <t-1.vertline.0>.sup.c have to be calculated. In FIG. 3, the calculaton for them is carried out by calculating <v.vertline.l>.sup.c 's that are in an area enclosed with four lines, i.e., the horizontal axis, l=v-1, l=-v+t+1, and v=t one by one in the ascending order of v. As FIG. 3 shows, in the course of obtaining <t.vertline.0>0>.sup.c, <t.vertline.1>.sup.c, all the Q determinants that are required to determine the coefficients of (E.sub. u (x)).sup.2 for any u, the number of error bits, less than t are calculated as well.

Moreover, the set of <v.vertline.l>.sup.c 's in FIG. 3 includes those in FIG. 1 and FIG. 2. Therefore, when all the <v.vertline.l>.sup.c 's in FIG. 3 are calculated, the number of error bits u can be estimated and all the coefficients of (E.sub.u (x)).sup.2 are determined for any value of u not exceeding t. At a decoder of this system, if a supposed maximum amount of calculation for obtaining an error locator polynomial, i.e., equivalent to that for the case of u=t, is allowed for any received word regardless of the number of errors in it, all the <v.vertline.l>.sup.c 's shown in FIG. 3 should be calculated for any received word. This makes the decoding process constant and easy to control. On the other hand, if the average amount of calculation required for obtaining an error locator polynomial is to be reduced >v.vertline.l>.sup.c 's shown in FIG. 2 should be calculated first to estimate the number of error bits u. If all the Q determinants that give the coefficients of (E.sub.u (x)).sup.2 of the estimated u have not been calculated in the above calculation, only ones that have not been obtained should be calculated. That is, <v.vertline.l>.sup.c 's that are shown in FIG. 3 and not shown in FIG. 2 are calculated one by one in the ascending order of v, according to equation (20) using already calculated Q determinants until the coefficients of (E.sub.u (x)).sup.2 get determined.

What is described above is an efficient method of calculating Q determinants for use in estimating the number of error bits and deriving the error locator polynomial. Then, in the following, an efficient method of calculating Q polynomials for the same purpose is described.

The estimation of the number of errors necessarily requires the calculation of either (t.vertline.0) or (t-1.vertline.0). FIG. 4 shows all the Q polynomials that should be calculated in the course of obtaining (t.vertline.0), and FIG. 5 shows all the Q polynomials that should be calculated in the course of obtaining (t-1.vertline.0). In FIG. 4 and FIG. 5, a point whose coordinate of the horizontal axis, that of the vertical axis are v, l, respectively stands for the set of Q polynomials denoted as (v.vertline.c.sub.1, c.sub.2, - - - , c.sub.l).sup.c, that is <<v.vertline.l>>. In order to obtain (t.vertline.0), the calculation of <<v.vertline.l>>.sup.c 's that are in an area enclosed with three lines, i.e., the horizontal axis. l=v-1, and l=-v+t, is performed one by one in the ascending order of v. In the same way, for obtaining (t-1.vertline.0), the calculation of <<v.vertline.l>>.sup.c 's that are in an area enclosed with three lines i.e., the horizontal axis, l=v-1, and l=-v-t-1, is performed one by one in the ascending order of v. The order of calculation of <<v.vertline.l>>.sup.c 's having the same value of v is arbitrary. The order of calculation of Q polynomials in the same <<v.vertline.l>>.sup.c is also arbitrary. If the Q polynomials are calculated in the order described above, the calculation of Q polynomials can necessarily be carried out in one of the following three manners (d), (e), and (f).

(d) When <<v.vertline.l>>.sup.c which contains the Q polynomial to be calculated is on l=v-1, <<v.vertline.l>>.sup.c is equal to <<v.vertline.v-1>>.sup.c, any Q polynomial belonging to it is easily obtained as the square root of a Q determinant composed of only one element.

(e) When <<v.vertline.l>>.sup.c which contains the Q polynomial to be calculated is on l=v-2, <<v.vertline.l>>.sup.c is equal to <<v.vertline.v-2>>.sup.c, and any Q polynomial belonging to it is calculated as the sum of a syndrome and a product of a Q polynomial already calculated and a syndrome according to equation (14).

(f) When <<v.vertline.l>>.sup.c which contains the Q polynomial to be calculated is on neither l=v-1 nor l=v-2, any Q polynomial that belongs to it is expanded according to equation (13) as follows. ##EQU8## Therefore, the Q polynomial is obtained as the sum of v-l products, each of which is a product of a syndrome and a Q polynomial whose head number is v-1 and the number of lacking elements is l or l+1. Any Q polynomial whose head number, number of lacking elements are v-1, l, respectively is contained in <<v-1.vertline.l>>, and any Q polynomial whose head number, number of lacking elements are v-1, l+1, respectively is contained in <<v-1.vertline.l+1>>. As <<v-1.vertline.l>> is the union of <<v-1-i.vertline.l-i>>.sup.c 's (i=0, 1, - - - , l) and <<v-1.vertline.l+1>> is the union of <<v-1-i.vertline.l+1-i>>.sup.c 's (i=0, 1, - - - , l+1), both were calculated before the Q polynomial in <<v.vertline.l>>.sup.c is calculated. Therefore, any Q polynomial contained in <<v.vertline.l>>.sup.c can be calculated as the sum of products, each of which is a product of a Q polynomial already calculated and a syndrome.

In FIG. 4, when the calculation of <<v.vertline.l>>.sup.c 's in an area enclosed with three lines is performed one by one in the ascending order of v up to <<t.vertline.0>>.sup.c, not only (t.vertline.0) but also all the (i.vertline.0)'s (i=1, 2, - - - , t-1 are obtained in the course of calculation. Therefore, the number of errors u can be estimated using them. Likewise, in FIG. 5, when the calculation of <<v.vertline.l>>.sup.c 's is performed one by one in the ascending order of v up to <<t-1.vertline.0>>.sup.c, not only (t-1.vertline.0) but all the (t-1-2i.vertline.0)'s (i=1, 2, - - - , (t-1)/2 ) are obtained in the course of calculation. Therefore, the number of error bits can be estimated as u or u-1.

In this way, when the number of error bits is estimated u or when it is estimated either u or u-1, the corresponding error position polynomial E.sub.u (x) is generated. As equation (19) indicates, each coefficient of E.sub.u (x), i.e., u.theta.i (i=0, 1, - - - , u) is given by a Q polynomial (u.vertline.i) that is contained in <<u.vertline.0>>.sup.c, <<u.vertline.1>>.sup.c, and <<u-1.vertline.0>>.sup.c. Therefore, if u is equal to t, <<t.vertline.0>>.sup.c, <<t.vertline.1>>.sup.c, and <<t-1.vertline.0>>.sup.c should be calculated. The calculation required for them is carried out, as shown in FIG. 6, by calculating <<v.vertline.l>>.sup.c 's in an area enclosed with four lines, i.e., the horizontal axis, l<v-1, l=-v+t+1, and v=t one by one in the ascending order of v. Also, as is seen in FIG. 6, in the course of calculating <<t.vertline.0>>.sup.c, and <<t.vertline.1>>.sup.c, all the Q polynomials that give the coefficients of E.sub.u (x) for any u, the number of error bits, not exceeding t are obtained. Moreover, the set of <<v.vertline.l>>.sup.c 's in FIG. 6 includes those of <<v.vertline.l>>.sup.c 's in FIG. 4 and FIG. 5. Therefore, the calculation of all the <<v.vertline.l>>.sup.c 's in FIG. 6 is sufficient to estimate the number of error bits u as well as to give the coefficients of E.sub.u (x) for any u not exceeding t.

If a supposed maximum amount of calculation for obtaining an error position polynomial, i.e., equivalent to that for the case of u=t is allowed for any received word regardless of the errors in it, all the <<v.vertline.l>>.sup.c 's shown in FIG. 6 should be calculated for any received word to make the calculation control simple. On the other hand, if the average amount of calculation required for obtaining an error locator polynomial is to be reduced <<v.vertline.l>>.sup.c 's shown in FIG. 5 should be calculated first to estimate the number of error bits u. If all the Q polynomials required for determining the coefficients of E.sub.u (x) have not been calculated in the above calculation, <<v.vertline.l>>.sup.c 's that are shown in FIG. 6 and not shown in FIG. 5 should be calculated according to equation (21) in the ascending order of v using already calculated Q polynomials.

The order of calculating Q determinants explained above is shown in the following example of t=6. All the <v.vertline.l>.sup.c 's shown in FIG. 3 are calculated.

As seen in the above example, a new Q determinant is easily calculated using Q determinants already calculated and syndromes. In the above example, if all the Q determinants are replaced with the corresponding Q polynomials and any square of a syndrome is replaced with the syndrome itself, the above example of Q determinant calculation becomes that of Q polynomial calculation.

Let's explain the embodiment of a decoder of this invention with drawings. FIG. 7 is a construction diagram of the embodiment of a decoding system of this invention. In FIG. 7, 1 stands for a data buffer for temporally storing received words, 2 stands for a syndrome generation circuit for generating the syndromes of received words, 3 stands for a circuit for calculating an error locator polynomial from the syndromes obtained in 2, 4 stands for a circuit for obtaining the roots of an error locator polynomial that calculates the roots of an error locator polynomial provided by 3. 5 stands for an error correction circuit that inverts error bits of a received word indicated by the roots of an error locator polynomial obtained by 4. FIG. 8 and FIG. 10 show construction diagrams of circuit for calculating an error locator polynomial 3 of FIG. 7. The construction diagrams of FIG. 8 and FIG. 10 are those of using Q determinants and of using Q polynomials respectively. What follows is an explanation of this decoding system.

When a received word Y is input at the decoding system, it gets stored in data buffer 1 and at the same time it is supplied to syndrome generation circuit 2, where the syndromes of Y, i.e., S.sub.1, S.sub.2, - - - , S.sub.2t are calculated. The calculation of syndromes can be performed by putting Y into feedback shift register circuits as described, e.g., in "The Theory of Error-Correcting Codes, Part 1" (by F. J. Mac Williams, and N. J. A. Sloane, North-Holland Publishing Company pp. 270/272.). Syndromes of the form S.sub.2i (i=1, 2, - - - , t) can also be obtained by squaring S.sub.i that is obtained in the above explained method. As each syndrome is an element of GF(2.sup.m) and can be represented by a vector with m elements, a circuit for squaring syndrome is realized with a ROM (Read Only Memory) of m-bit words whose address size is m bits.

Then, S.sub.1, S.sub.2, - - - , S.sub.2t, syndrome thus generated are supplied to circuit for calculating an error locator polynomial 3. At this circuit, an error locator polynomial is generated from the syndromes. The circuit for calculating an error locator polynomial will be explained in detail later with reference to FIG. 8 and FIG. 10. The roots of an error locator polynomial provided by the above circuit is calculated in circuit for obtaining the roots of an error locator polynomial 4. Usually, as described in "The Theory of Error-Correction Codes, Part 1" (by F. J. Mac Williams and N. J. A. Sloane, North-Holland Publishing Company, pp. 275/277), so-called Chien Search is conducted where error location numbers are generated one by one, and are substituted into the error locator polynomial to examine if it becomes zero or not. In this way by finding out the roots of the error locator polynomial at this circuit, the position of error bits included in the received word get clarified. When the received word stored in data buffer 1 is shifted out to error correcting circuit 5, the error bits are corrected by inversion. This kind of error correction circuit is usually realized with exclusive-or logic circuits.

Then, let's explain the circuit for calculating error locator polynomial mentioned earlier, that is one of the characteristic features of this invention. The circuit for calculating error locator polynomial in a decoding system of this invention calculates Q determinants or Q polynomials from the syndrome of a received word efficiently with simple circuitry, to determine the coefficients of the error locator polynomial. In the first place, a circuit of using Q determinants is explained with FIG. 8, where all the <v.vertline.l>.sup.c 's that are shown in FIG. 3 are calculated one by one in the ascending order of v. In FIG. 8, 11 stands for a Q determinant register for storing a calculated Q deternimant, 12 stands for a syndrome register for storing the syndromes, i.e., S.sub.1, S.sub.2, - - - , S.sub.2t generated in syndrome generation circuit 2, 13 stands for a squaring circuit for squaring a syndrome, 14 stands for a multiplier for calculating a product of a Q determinant stored in Q determinant register 11 and the square of a syndrome produced at squaring circuit 13, 15 stands for an adder for adding the output of multiplier 14 and that of register 16, 17 stands for s syndrome register control circuit for controlling the input and the output of a syndrome to and from syndrome register 12, 18 stands for a Q determinant register control circuit for controlling the input and the output of a Q determinant to and from Q determinant register 11, 19 stands for number of error bits judging circuit for judging the number of error bits by using the Q determinants, and 20 stands for a timing circuit.

How this circuit for calculating an error locator polynomial works is described below for the case of t=6 as an example.

To begin with, Q determinant register 11 and register 16 get reset, and syndromes S.sub.1, S.sub.2, - - - , S.sub.2t that are generated in syndrome generation circuit 2 are transferred to syndorme register 12. In an address position of Q determinant register 11 that is not used by any Q determinant, 1 is stored which is first read out and is put into multiplier 14. At the same time, S.sub.1 is read out from syndrome register 12, and it becomes S.sub.1.sup.2 in passing through squaring circuit 13, then this is put into multiplier 14. The result of multiplication, S.sub.1.sup.2 is stored into register 16 and then it is transferred to Q determinant register 11 as [1]. Register 16 is reset after S.sub.1.sup.2 is stored in Q determinant register 11. Then, [1] is read out from Q determinant register 11 and is input into multiplier 14. At the same time, S.sub.2 is read out from syndrome register 12 which becomes S.sub.2.sup.2 in passing through squaring circuit 13 and S.sub.2.sup.2 is input into multiplier 14. To the output of multiplier 14, i.e., S.sub.2.sup.2 [1], 0, the contents of register 16 is added at adder 15, and the output of adder 15, S.sub.2.sup.2 [1], is stored into register 16. Then, 1 is read out from Q determinant register 11 and is input into multiplier 14, at the same time, S.sub.3 is read out from syndrome register 12 which becomes S.sub.3.sup.2 in passing through squaring circuit 13 and S.sub.3.sup.2 is input into multiplier 14. To the output of multiplier 14, i.e., S.sub.3.sup.2 and the contents of register 16, S.sub.2.sup.2 [1] is added at adder 15, and the output of adder 15, S.sub.2.sup.2 [1]+S.sub.3.sup.2 is stored into register 16 and is transferred to Q determinant register 11 as [1, 2]. Then, register 16 is reset as before. In this way, with repetition of a simple process, Q determinants are calculated one by one. In the course of calculation, whenever [ i.vertline.0]=[1, 2, - - - , i] (i=1, 2, - - - , t) is calculated, the number of error bits judging circuit 19 examines its value. If [i.vertline.0].noteq.0 the number of error bits judging circuit 19 holds the value of i and at the same time the previous one that has been held in it is erased. Therefore, the value of i the number of error bits judging circuit 19 holds when calculation of all the Q determinants is over, is the number of error bits u. When the number or error bits u is determined in this way, each coefficient u.theta.i.sup.2 =[u.vertline.i] of the corresponding error locator polynomial (E.sub.u (x)).sup.2 is read out from Q determinant register 11 and is sent to circuit for obtaining the roots of error locator polynomial 4. The performance described above is controlled by Q determinant register control circuit 18 and syndrome register control circuit 17. For storing each syndrome into syndrome register 12, syndrome register control circuit 17 provides a write command and an address of storage location to syndrome register 12. When storage of all the syndromes in syndrome register 12 is completed then calculation of Q determinants follows. As explained earlier, calculation of Q determinants is carried out by calculating all the <v.vertline.l>.sup.c 's shown in FIG. 3 one by one in the ascending order of v. An example of the order of calculating Q determinants was already shown for the case of t=6. In calculating each Q determinant, Q determinant register control circuit 18 controls the reading out of the appropriate Q determinants from Q determinant register 11 and the writing of the calculated Q determinant into the appropriate address of Q determinant register 11 by means of designating an appropriate address of Q determinant register, while, syndrome register control circuit 17 controls the readout of appropriate syndrome from the syndrome register 12. For example, a Q determinant denoted by [1, 3, 4, 5] is calculated as follows.

FIG. 9 shows the controlling functions performed by Q determinant register control circuit 18 and syndrome register control circuit 17 in calculating the above equation. As seen in FIG. 9, a lot of controls with appropriate designated addresses for read-out and write-in are required. The contorl information can be stored in a ROM beforehand, and it can be read out according to time.

When calculation of Q determinants is completed, and so a judged number of error bits u is obtained, this number of error bits u is input to Q determinant register contorl circuit 18, which performs the control of reading out each [u.vertline.i], being equal to u .circle.H i (i=0, 1, 2, - - - , u), from Q determinant register 11. The address of each [u.vertline.i] where the value of u is given, can be stored in a ROM beforehand so that the control becomes simpler.

A circuit shown in FIG. 10 is the one for calculating an error locator polynomial using Q polynomials. In FIG. 10, 21 stands for a Q polynomial register for storing calculated Q polynomials, 22 stands for a syndrome register for storing syndromes S.sub.1, S.sub.2, - - - , S.sub.2t that are generated in syndrome generation circuit 2, 23 stands for a multiplier for obtaining a product of an already calculated Q polynomial stored in Q polynomial register 21 and a syndrome, 24 stands for an adder for calculating the sum of the output of multiplier 23 and the output of register 25, 26 stands for s syndrome register control circuit for controlling the input and output of a syndrome to and from the syndrome register 22, 27 stands for a Q polynomial register control circuit for controlling the input and output of a Q polynomial to and from Q polynomial register 21, 28 stands for a number of error bits judging circuit, and 29 stands for a timing circuit.

The performance of this circuit for calculating an error locator polynomial shown in FIG. 10 can be understood easily with reference to the circuit in FIG. 8 because it is only necessary to replace the Q determinants with Q polynomials and to omit the squaring circuit 13.

This invention provides an error correction equipment with simple circuitry that can decode any received code word with reduced quantity of calculation.

From the foregoing it will now be apparent that a new and improved error correction code decoding system has been found. It should be understood of course that the embodiments disclosed are merely illustrative and are not intended to limit the scope of the invention. Reference should be made to the appended claims, therefore, rather than the specification as indicating the scope of the invention.