HK1000651B - Method and apparatus for reed-solomon encoding an identification field using words of four bits - Google Patents

Abstract

Identification (ID) error detection codes are formed which are synchronized at least with ID data and digital data of fixed length. The ID data are firstly separated per four bits. A first data is added to each separated four-bit data. The data to which the first data is added is delayed by a period corresponding to each four-bit data. Further, a second data is added to the delayed data. The data to which the second data is added is delayed by the period corresponding to each four-bit data. The delayed data to which the second data is added is multiplied by a coefficient related to a Galois Field ( ) to generate the second data. Further, the delayed data to which the second data is added is multiplied by a coefficient a related to the Galois Field ( ) to generate the first data. Four-bit Reed-Solomon codes defined on the Galois Field ( ) is thus formed. The Reed-Solomon codes become the ID data error detection codes.

Description

BACKGROUND OF THE INVENTION

The present invention relates to an error detection code forming method and apparatus, and more specifically to a method and apparatus for forming an error detection code such as a parity code each added to each fixed length of digital data as a redundant code.

There are a conventional apparatus for recording digital data on a storage medium and reproducing the recorded digital data therefrom and a conventional apparatus for receiving and transmitting digital data. In these apparatus, digital data required to be recorded or reproduced are firstly separated per fixed length; secondly an error detection code is added to the separated digital data of fixed length together with a synchronous signal and identification (ID) data, such as, address data; and then these data are recorded/reproduced or transmitted all together in unit of block signals.

Figure 1 shows an example of the format of the block signals. In Fig. 1, one block is composed of 112 bytes including a two-byte synchronous (Sync) area 11 arranged at a head position as a reference for reproduction, a three-byte ID data area 12 (e.g., address data), a 99-byte data field 13, and an eight-byte parity area 14, all arranged in sequence. Here, in the eight-byte parity area 14, a parity code is multiplexed to detect an error existing in this block. As the parity error code, Reed-Solomon codes is used, for instance.

Here, the three-byte ID data multiplexed in the area 12 for transmission and reproduction are important data used for returning the normally obtained block to the original position, when a part of block signals is missing (e.g., ID data on each track are reproduced discontinuously by high-speed reproduction). Therefore, it is necessary to judge whether the reproduced ID data are reliable or not as accurately as possible.

For this purpose, as shown in Figs. 2A, 2B and 2C, the three-byte ID data are composed of first ID data ID1, second ID data ID2, and ID parity data. Further, the eight-bit first ID data ID1 includes four-bit data 15 and three-bit data 16; the eight-bit second ID data ID2 includes nine-bit data 17; and the ID parity data includes an eight-bit error detection code (e.g., parity data) for detecting an error of these ID data 15, 16 and 17. Here, since being used only to detect an error of the ID data, the above-mentioned parity code is referred to as an ID parity.

Further, the above-mentioned four-bit ID data 15, three-bit ID data 16, and nine-bit ID data 17 are three different ID data, respectively, and the number of bits of thee ID data and the number of these ID data are both set to an appropriate value, respectively according to the apparatus to which these ID data are applied. Further, conventionally, the one-byte ID parity as shown in Fig. 2(C) forms a simple parity code constructed as follows: $\text{ID parity = (ID1 + ID2) mod 2}$    where ID1 and ID2 denote the first byte ID data and the second byte ID data as shown in Figs. 2A and 2B, respectively. Here, the above expression indicates that the ID parity code is an addition of corresponding bits of the two ID data ID1 and ID2 by using 2 as modulo. Therefore, the ID parity code can be expressed by use of 8 codes of (3, 2, 2: code length, data length, minimum distance). In other words, although the one-bit error can be detected, there exists a possibility that a two-bit error may be overlooked.

In the conventional error detection code forming method, however, since the (3, 2, 2) codes are formed basically, there exists a possibility that a two-bit error cannot be detected when it is present. Therefore, in the conventional error detection code forming method, in spite of the fact that errors occur in the ID parity codes at a relatively high frequency, there exists the case where the errors are overlooked. In this case, the error detection capability can be improved by increasing the number of bits of the ID parity data. However, the ID data 12 and the parity data in the ID parity area 12 are both redundant bit areas (not the data area 13), and there exists a limit of the capacity of a storage medium. It is thus impossible to increase the ID area 12. Rather, there exists a need of reducing the ID area 12, as narrow as possible.

US-A-5,404,249 discloses a digital video tape recorder with data block ID signal error correction in which the ID signal is divided into a sequence of four-bit symbols and at least two parity symbols are generated according to an error correction code for correcting errors in the sequence of four-bit symbols. In particular, a Reed-Solomon code which has a data length of six symbols and a parity of two symbols is used.

SUMMARY OF THE INVENTION

With these problems in mind, therefore, it is an object of the present invention to provide an error detection code forming method and apparatus which can improve the error detection capability markedly.

The present invention provides a method of forming identification (ID) error detection codes to be synchronized at least with ID data and digital data of fixed length, the method comprising the steps of:

• separating the ID data per four bits;
• adding a first data to each separated four-bit data;
• delaying the data to which the first data is added by a period corresponding to each four-bit data;
• adding a second data to the delayed data;
• delaying the data to which the second data is added by the period corresponding to each four-bit data;
• multiplying the delayed data to which the second data is added by a first coefficient related to a Galois Field (24) to generate the second data; and
• multiplying the delayed data to which the second data is added by a second coefficient related to the Galois Field (24) to generate the first data, four-bit Reed-Solomon codes defined on the Galois Field (24) thereby being formed, Reed-Solomon codes becoming the ID data error detection codes.

The present invention also provides an apparatus for forming an identification (ID) error detection code to be synchronized at least with ID data and digital data of fixed length, the apparatus comprising:

• separating the ID data per four bits;
• first adding means for adding a first data to the ID data per four bits;
• first delaying means for delaying the data to which the first data is added by a period corresponding to the four bits;
• second adding means for adding a second data to the delayed data;
• second delaying means for delaying the data to which the second data is added by the period corresponding to the four bits;
• first multiplying means for multiplying the data thus delayed by the second delaying means with a first coefficient related to Galois Field (24) to generate the second data; and
• second multiplying means for multiplying the data thus delayed by the second delaying means by a second coefficient related to the Galois Field (24) to generate the first data, four-bit Reed-Solomon codes defined on the Galois Field (24) thereby being formed, the Reed-Solomon code becoming the ID data error detection codes.

In these arrangements the first and second coefficients are preferably a4 and a respectively.

BRIEF DESCRIPTION OF THE DRAWINGS

• Fig. 1 is an illustration showing an example of a signal format for transmitting error detection codes;
• Figs. 2(A), 2(B) and 2(C) are illustrations each showing a detail of the ID area shown in Fig. 1.
• Fig. 3 is a block diagram showing an embodiment of the error detection code forming apparatus according to the present invention;
• Fig. 4 is a timing chart for assistance in explaining the operation of the error detection code forming apparatus shown in Fig. 3;
• Figs. 5A and 5B are block diagrams showing error detection circuits in the code word reproducing system (or reception system); and
• Fig. 6 is a timing chart for assistance in explaining the operation of the error detection circuit shown in Figs. 5A and 5B.

DETAIED DESCRIPTION OF THE PREFERRED EMBODIMENTS

An embodiment of the error detection code forming method and apparatus according to the present invention will be described hereinbelow with reference to the attached drawings.

Figure 3 shows an error detection code forming apparatus according to the present invention, and Fig. 4 shows the timing chart for explaining the operation of the apparatus shown in Fig. 3. The error detection code forming apparatus shown in Fig. 3 is provided with a first adder 21, a first switch 22, a first delay circuit 23, a second adder 24, a second delay circuit 25, a first multiplier 26 for multiplying a coefficient α⁴, a second multiplier 27 for multiplying a coefficient α, and a second switch 28. The second switch 28 changes the output data from four-bit ID data applied through an input terminal 20 to four-bit output data applied from the delay circuit 25 or vice versa, and outputs the switched four-bit data through an output terminal 29.

The respective elements of the error detection code forming apparatus shown in Fig. 3 operates in synchronism with a clock as shown in Fig. 4(a). Further, the first and second delay circuits 23 and 25 and the first and second multipliers 26 and 27 are all cleared by a clear pulse as shown in Fig. 4(b), before data are input to the input terminal 20.

The ID data of eight-bit (one-byte) unit are input 4 bits by 4 bits in parallel to each other in sequence through the input terminal 20 to the first adder 21 and a terminal H of the second switch 28, as symbol data.

In other words, as shown in Fig. 4(c), 16-bit ID data are input as four-bit symbol data in sequence of S0, S1, S2 and S3 in synchronism with the clock as shown in Fig. 4(a). While these four symbol data S0 to S3 are being input, a switch control signal applied to the first switch 22 is set to the high level as shown in Fig. 4(d) to set the first switch 22 to its terminal H. In the same way, a switch control signal applied to the second switch 28 is set to the high level as shown in Fig. 4(e) to set the second switch 28 to its terminal H.

Therefore, the four symbol data S0 to S3 input through the input terminal 20 are output to the output terminal 29 through the second switch 28 as they are, as shown in Fig. 4(f). Further, the four symbol data SO to S3 are supplied to the first delay circuit 23 through the first adder 21 and the first switch 22. After having been delayed one-symbol period (corresponding to symbol data SO, for example) by the first delay circuit 23, the four delayed symbol data SO to 53 are supplied to the second adder 24. The output data of the second adder 24 are further delayed the one-symbol period by the second delay circuit 25 and supplied to the first and second multipliers 26 and 27. The further delayed symbol data SO to 53 are multiplied by two coefficients α⁴ and α. The output data of the first and second multipliers 26 and 27 are supplied to the second and first adders 24 and 21, respectively, and then added to the output data of the first delay circuit 23 and to the symbol data input through the input terminal 20, respectively.

After that, at a moment when the fourth symbol data S3 have been all input, the switch control signals of the first and second switches 22 and 28 are both changed to a low level, as shown in Figs. 4(d) and 4(e). The first and second switches 22 and 28 are then both set to their terminals L, so that the output terminal 29 is disconnected from the input terminal 20, and connected to an output end of the second delay circuit 25. Therefore, at a moment when the fourth symbol data 53 have been all inputted, the four-bit output data of the second delay circuit 25 are output, as parity data, to the output terminal 29 through the second switch 28 in sequence of P0 and P1, as shown in Fig. 4(f).

Here, the above-mentioned four-bit parity data P0 and P1 are Reed-Solomon codes each defined on a finite field, that is, Galois Field (GF) 2⁴, which can be expressed by a primitive polynomial x⁴+x+1 and a generating polynomial (x+α) · (x+1) (α: a primitive element of 0010). The parity data P0 and P1 formes a code word CW of 24 bits (=three bytes) in total together with the four symbol data S0 to S3 as follows:    where S4 =P0 and S5 =P1

The generating polynomial (x+α)·(x+1) equals x²+(α +1)x+α. And, α⁴ is identical to (α+1) when calculated on the finite field GF defined by the primitive polynomial x⁴+x+1. Thus, the expression x²+(α+1)x+α is identical to x²+α⁴x+α. These α⁴ and α correspond to the coefficients α⁴ and α of the multipliers 26 and 27, respectively.

As described above, in the present invention, the ID parity is defined by forming the Reed-Solomon code on the basis of multiplication obtained by using x⁴+x+1 on a finite field GF (2⁴) as modulo and by using α=(0010) as a primitive element. Therefore, in spite of the one-byte parity quantity (the same as the conventional simple parity), two ID parity codes can be formed on the basis of the four symbol data in unit of four bits, so that it is possible to improve the error detection capability of the ID data markedly, as compared with the conventional parity code.

As described above, a feature of the invention is that, with respect to Fig. 1, the error detection code (area 14) in unit of 1 byte (8 bits) is attached to the data (area 13) while two ID error detection codes each in unit of 4 bits are attached to the ID data (area 12). The entire block signal format according to the invention is the same as shown in Fig. 1.

Here, the construction and operation of a reproduction system (reception system) for the code words having the error correction codes formed as described above will be described hereinbelow.

Figures 5A and 5B show block diagrams each showing the reproduction system (reception system), and Fig. 6 shows a timing chart for assistance in explaining the operation thereof.

In the reproduction system (reception system) shown in Fig. 5A, four-bit reception signal data are input through an input terminal 30 in synchronism with the clock as shown in Fig. 6(a), and then input to a delay circuit 32 via an adder 31 cleared by a clear pulse as shown in Fig. 6(b). After having been delayed by one-symbol time by the delay circuit 32, the four-bit reception data are output through an output terminal 33 and further feed-backed to the adder 31.

Here, since four symbol data S0 to S3 and two ID parity codes P0 and P1 are input to the input terminal 30 in sequence, as shown in Fig. 6(c), a syndrome SYO obtained by adding these six data in sequence by using 2 as modulo is output from the output terminal 33 at a timing as shown in Fig. 6(f).

Further, in the reproduction system (reception system) shown in Fig. 5B, four-bit reception signal data are input through an input terminal 40 in synchronism with the clock as shown in Fig. 6(a), and then input to a delay circuit 42 via an adder 41 cleared by a clear pulse as shown in Fig. 6(b). After having been delayed by one-symbol time, the four-bit reception data are output through an output terminal 44 and further feed-backed to the adder 41 via a multiplier 43 (after having been multiplied by a coefficient α).

Here, four symbol data S0 to S3 and two ID parity codes P0 and P1 are input to the input terminal 40 in sequence, as shown in Fig. 6(c). The input data are added to a value obtained by multiplying the preceding data among these six data by the coefficient α by using 2 as modulo, and further the succeeding data are added to a value obtained by multiplying the obtained addition result data by the coefficient α by using 2 as modulo. That is, a syndrome SY1 obtained by repeating the above-mentioned additions is outputted in sequence from the output terminal 44 at a timing as shown in Fig. 6(g). Further, Figs. 6(d) and 6(e) indicate the control signals of the circuits shown in Figs. 5A and 5B, respectively. Therefore, when the two syndromes SY0 and SY1 obtained as described above are both at "O", it can be judged that there is no error.

As described above, since the ID parity detecting circuit is constructed for detecting the Reed-Solomon codes on the finite field GF (2⁴), the detecting circuit can be constructed simply, as compared with the conventional error detecting circuit.

Further, the present invention is not limited only to the above-mentioned embodiment. For instance, as far as an addition of the ID data and the ID parity code is less than 4 x 15 bits, any combination of both can be adopted. Further, in the above-mentioned embodiment, although the primitive polynomial x⁴+x+1 is used to introduce the a finite field on GF (2⁴), another primitive polynomial (e.g., x⁴+x²+1) can be also used. Further, with respect to the generating polynomial of (x+α) · (x+1), another generating polynomial (e.g., (x+α²)·(x+1)) can be also used.

As described above, in the error detection code forming method and apparatus according to the present invention, the ID data are input as symbol data for each four-bit unit and further the Reed-Solomon code defined on the finite field GF (2⁴) is used as the ID data error detection code. It is thus possible to improve the ID data detection capability markedly, as compared with the conventional ID data error detection code using eight (3, 2, 2) codes, in spite of the fact that the same parity quantity is used. Further, since the parity forming apparatus can form the Reed-Solomon code defined on the finite field GF (2⁴), it is possible to simplify the circuit construction by using only 16 bits.

Claims (6)

1. A method of forming identification (ID) error detection codes to be synchronized at least with ID data and digital data of fixed length, the method comprising the steps of:

   separating the ID data per four bits;

   adding a first data to each separated four-bit data;

   delaying the data to which the first data is added by a period corresponding to each four-bit data;

   adding a second data to the delayed data;

   delaying the data to which the second data is added by the period corresponding to each four-bit data;

   multiplying the delayed data to which the second data is added by a first coefficient related to a Galois Field (2⁴) to generate the second data; and

   multiplying the delayed data to which the second data is added by a second coefficient related to the Galois Field (2⁴) to generate the first data, four-bit Reed-Solomon codes defined on the Galois Field (2⁴) thereby being formed, Reed-Solomon codes becoming the ID data error detection codes.
2. The method according to claim 1, wherein each Reed-Solomon code is expressed by a primitive polynomial x⁴+x+1 and a generating polynomial (x+α) · (x+1) (α: a primitive element of 0010).
3. The method according to claim 1, wherein each Reed-Solomon code is expressed by a primitive polynomial x⁴+x²+1 and a generating polynomial (x+α²) · (x+1) (α: a primitive element of 0010).
4. The method according to claim 1 in which the first and second coefficients are α⁴ and α respectively.
5. An apparatus for forming an identification (ID) error detection code to be synchronized at least with ID data and digital data of fixed length, the apparatus comprising:

   separating the ID data per four bits;

   first adding means (21) for adding a first data to the ID data per four bits;

   first delaying means (23) for delaying the data to which the first data is added by a period corresponding to the four bits;

   second adding means (24) for adding a second data to the delayed data;

   second delaying means (25) for delaying the data to which the second data is added by the period corresponding to the four bits;

   first multiplying means (26) for multiplying the data thus delayed by the second delaying means with a first coefficient related to Galois Field (2⁴) to generate the second data; and

   second multiplying means (27) for multiplying the data thus delayed by the second delaying means by a second coefficient related to the Galois Field (2⁴) to generate the first data, four-bit Reed-Solomon codes defined on the Galois Field (2⁴) thereby being formed, the Reed-Solomon code becoming the ID data error detection codes.
6. The apparatus according to claim 5 in which the first and second coefficients are α⁴ and α respectively.