Feedback Shift Register

The following reference is cited to show the state of the art:

W. Weslay Peterson and E. J. Weldon, Jr. "Error-Correcting Codes" second edition, published by the MIT Press, pp. 365-372.

This invention relates to a data error detecting and correcting device for use in a system processing data received from a memory such as a magnetic drum or magnetic disc or from, for example, a communication line. In particular, this invention relates to a feedback shift register which is constructed according to a peculiar polynomial suited to the characteristic of an associated memory or communication line and can generate data error check bits and a data error correcting pattern.

FIG. 1 is a basic circuit diagram of a prior art feedback shift register to illustrate the construction of the shift register and its check bit generating operation.

FIG. 2 shows a data format employed for error detection and correction.

FIG. 3 is a block diagram illustrating the operation of a prior art data error correcting circuit using a feedback shift register as shown in FIG. 1.

FIGS. 4 and 5 are circuit diagrams to illustrate how the prior art feedback shift register has been defective.

FIG. 6 is a circuit diagram of a preferred embodiment of the feedback shift register according to the present invention.

It is commonly known that a check bit of redundant length is added to the end of each data block and is recorded together with the data block during writing of the data in a memory, so that this check bit can be used for error detection and correction of the recorded data during reading out of the data from the memory. FIG. 1 shows a basic circuit of a feedback shift register 1 which has been used hitherto for the purpose of data error detection and correction. The blocks 2 and 3 designate a central processor unit (CPU) of a computer system, and a memory such as a magnetic disc or magnetic drum memory, respectively. A plurality of flip-flops F.sub.0 to F.sub.n-1 constitute the feedback shift register 1. A setting trigger signal and a reset signal for these flip-flops F.sub.0 to F.sub.n-1 are applied to input terminals T and R respectively. Exclusive-OR gates E.sub.0 to E.sub.n-1 are connected to the inputs of these flip-flops F.sub.0 to F.sub.n-1 respectively, and AND gates A.sub.1 to A.sub.n-1 are connected to the inputs of these Exclusive-OR gates E.sub.1 to E.sub.n-1 respectively. The gates A.sub.1 to A.sub.n-1 are opened when an actuating signal is applied to terminals J connected therewith. An input data and the output of the flip-flop F.sub.n-1 in the last stage are applied to the Exclusive OR-gate E.sub.0, and the output of this gate E.sub.0 is applied to the flip-flop F.sub.0 in the first stage. The data obtained by the Exclusive-OR operation on the outputs of the flip-flops F.sub.0 to F.sub.n-2 and the outputs of the AND gates A.sub.1 to A.sub.n-1 are applied to the flip-flops F.sub.1 to F.sub.n-1 respectively.

Suppose that a polynomial G(X)=X.sup.n +g.sup.n-1 X.sup.n-1 +. . . +g.sup.1 X+1 is employed in the feedback shift register having such a construction. In such a case, coefficients of g.sup.1 to g.sup.n-1 are equal to 1 when the associated AND gates A.sub.1 to A.sub.n-1 are opened, while the coefficients of g.sup.1 to g.sup.n-1 are equal to 0 when the associated AND gates A.sub.1 to A.sub.n-1 are closed. Thus, the feedback shift register can operate according to any desired polynomial when suitable ones of the AND gates A.sub.1 to A.sub.n-1 are selectively opened.

The feedback shift register produces a check bit in a manner as described presently. In this description, it is supposed that the data format is as shown in FIG. 2. At first, a reset signal is applied to the reset signal input terminal R to reset all the flip-flops F.sub.0 to F.sub.n-1. Thereafter, the data bits transmitted from the central processor unit 2 are applied to the feedback shift register 1 through a path 11 in sequential order from the first bit 2.sup.l-1 and are simultaneously supplied to the memory 3 through a path 12 and then recorded on the recording medium of the memory 3. The Exclusive-OR gate E.sub.0 carries out is Exclusive-OR operation on the data bit 2.sup.l-1 and the output of the flip-flop F.sub.n-1 in the last stage, and the resultant output of the Exclusive-OR gate E.sub.0 is applied to the flip-flop F.sub.0 in the first stage. At the same time, the output of the Exclusive-OR gate E.sub.0 passes through the opened ones of the AND gates A.sub.1 to A.sub.n-1 to be applied to the corresponding ones of the Exclusive-OR gates E.sub.1 to E.sub.n-1. These Exclusive-OR gates carry out their Exclusive-OR operation on the output of the Exclusive-OR gate E.sub.0 and the outputs of the flip-flops in the preceding stages, and their outputs are applied to the associated flip-flops. This operation is repeated so that the contents of the register 1 at the time of application of the last data bit 2.sup.n correspond to the check bits of n bits, 2.sup.n-1 to 2.sup.0. These check bits are transmitted to the memory 3 through a path 13 and then recorded on the recording medium of the memory 3 after the last data bit 2.sup.n in the form shown in FIG. 2.

Error detection is carried out in a manner as described presently. In response to the application of a reset signal to the reset signal input terminal R of the feedback shift register 1, all the flip-flops F.sub.0 to F.sub.n-1 are reset. Then, the data bits read out from the recording medium of the memory 3 are applied sequentially to the shift register 1 through the paths 12 and 11. In this case, the first bit 2.sup.l-1 of the data bits provides the first input to the shift register 1, and the shift is ceased at the time at which the last bit 2.sup.0 of the check bits is applied. The contents of the shift register at this time are checked, and the data thus read out or transferred are proved error-free when the contents of all the flip-flops are in the "0" state. However, an error exists when the content of at least one of the flip-flops is a 1. In such a case, the shift register 1 is shifted without application of any input thereto until the contents of a specific series of the flip-flops F.sub.0 to F.sub.n-1 attain "0". At that time, the contents of the remaining flip-flops provide the error bit pattern used for the error correction.

The error correcting operation will be described with reference to FIG. 3. Referring to FIG. 3, reference numeral 4 designates a buffer register for sequentially storing the data bits of the first bits 2.sup.l-1 to the last bit 2.sup.n when the data bits are read out of the memory 3. When the contents of the feedback shift register 1 indicate that an error exists in the read-out data, the shift register 1 is shifted until all the inputs to an OR circuit 5 are "0". An error exists in the data bit output of a buffer register 4 appearing at the time at which all the inputs to the OR circuit 5 are "0" and simultaneously the feedback shift register provides a "1" to AND gate 7. This erroneous bit is applied to an Exclusive-OR gate 9 which is provided to correct the error by making its Exclusive-OR operation on the erroneous bit input and the output of an AND circuit 7 applied at that time. More precisely, when all the inputs applied to the OR circuit 5 are "0", its output is also "0", and this output is inverted by a NOT circuit 6 to apply a "1" to the input of the AND circuit 7. The logical output of the AND circuit 7 at this time is "1" since the erroneous bit output of the shift register 1 is applied to the other input of the AND circuit 7. Such an output of the AND circuit 7 is applied to one of the inputs of the Exclusive-OR gate 9 to invert the bit output of the buffer register 4 in which data is stored, and the resultant output of the Exclusive-OR gate 9 is applied to the central processor unit 2. In this manner, the data error is corrected. On the other hand, the AND circuit 7 is kept closed so long as the output of the OR gate 5 remains "0". In this case, the output of the buffer register 4 is transferred intact to the central processor unit 4, and at the same time, such a logical output of the OR circuit 5 is fed back to the shift register 1 through an AND circuit 8 to sequentially shift the contents of the shift register 1 toward the left. This operation continues until a logical output "0" appears from the OR circuit 5. Therefore, error correction of the data transferred from the memory 3 to the central processor unit 2 is completed at the time at which the contents of all the flip-flops of the shift register 1 provide "0".

The primary factor which determines the maximum code length of the code consisting of the data bits and the check bits is the polynomial which is peculiar to and selected to suit the characteristic of a memory employed in a specific system. The error detecting ability and error correcting ability are also greatly dependent upon this peculiar polynomial G(X). It is therefore necessary to prepare a feedback shift register which satisfies the polynomial G(X) selected to suit the characteristic of a memory or data transfer means.

In a modern data processing system, data is processed at a very high speed. Thus, it is required to use high-speed circuit elements resulting in an increase in the system cost when data is applied one bit at a time as in the prior art feedback shift register. A method has been proposed in which a plurality of data bits are simultaneously applied to a feedback shift register. While this proposed method is advantageous in that employment of circuit elements operating at an excessively high speed can be dispensed with, it has such disadvantages that the circuitry is very complex, and many circuit elements are required resulting also in an increase in the system cost. Such prior art defect will be described with reference to FIGS. 4 and 5.

FIG. 4 illustrates a feedback shift register adapted to operate with a polynomial G(X)=X.sup.8 +X.sup.7 +X.sup.2 +1. In FIG. 4 like reference characters are used to designate like parts appearing in FIG. 1. It is supposed herein that n=8, and data is applied one bit after another to the feedback shift register.

Referring to FIG. 4, the contents of flip-flops F.sub.0 to F.sub.7 are initially a.sub.0 to a.sub.7 respectively, and a data input of four bits is applied in sequential order of d.sub.0, d.sub.1, d.sub.2 and d.sub.3. The contents of the register are shown in Table 1 in which the symbol .sym. designates Exclusive-OR operation.

In this Table, C.sub.0 =a.sub.7 .sym.d.sub.0, C.sub.1 =a.sub.6 .sym.d.sub.1, C.sub.2 =a.sub.5 .sym.d.sub.2, and C.sub.3 =A.sub.4 .sym.d.sub.3.

Therefore, a feedback shift register will have a construction as shown in FIG. 5 when four data bits are simultaneously applied, and the same polynomial G(X) as that of the feedback shift register shown in FIG. 4 is used. In FIG. 5, like reference characters are used to designate like parts appearing in FIG. 1. As in FIG. 1, A designates AND gates opened in response to application of an actuating signal to a terminal J, and .sym. designates Exclusive-OR gates. It will be readily seen from comparison between FIG. 4 and FIG. 5 that the circuitry becomes very complex, and the number of circuit elements increases excessively when a plurality of data bits are simultaneously applied although the polynomial G(X) is the same.

In a data processing system, a single feedback shift register may be incorporated in a control unit which controls a plurality of magnetic memories of different characteristics such as magnetic discs and magnetic drums. It may be desired in such a system to provide a plurality of polynomials G(X) suited individually to the characteristics of the magnetic memories by merely changing over the feedback mode of the feedback shift register depending on the individual magnetic memories.

It is therefore a first object of the present invention to realize a high-speed feedback shift register with simple circuit arrangement.

A second object of the present invention is to provide a feedback shift register which permits ready change-over of its feedback mode.

In accordance with a first aspect of the present invention, there is provided a feedback shift register comprising register means including a bistable memory element in each of a plurality of stages, means for producing address information by making a first predetermined logical operation on the input data and the internal state of said register means, memory means for providing data determined by a second predetermined logical operation among the bits of said address information upon reception of said address information from said address information producing means, and means for renewing the iternal state of said register means upon reception of said data from said memory means.

In accordance with a second aspect of the present invention, there is provided a feedback shift register comprising register means including a bistable memory element in each of a plurality of stages, means for producing address information by making a first predetermined logical operation on the input data and the internal state of said register means, memory means for providing data determined by a second predetermined logical operation among the bits of said address information upon reception of said address information from said address information producing means, and means for renewing the internal state of said register means upon reception of said data from said memory means, wherein said address information applied to said memory means is divided into a plurality of groups so as to read out the data by logical operations which differ from each other depending on the groups of address information.

FIG. 6 illustrates a preferred embodiment of the feedback shift register according to the present invention. The feedback shift register shown in FIG. 6 has the same function as that of the feedback shift register shown in FIG. 5, as described presently. It is apparent that the contents of the register after the application of a 4-bit data are as shown in Table 1. The values C.sub.0 =a.sub.7 .sym.d.sub.0, C.sub.1 .times.a.sub.6 .sym.d.sub.1, C.sub.2 =a.sub.5 .sym.d.sub.2, and C.sub.3 =a.sub.4 .sym.d.sub.3, and they are produced by Exclusive-OR gates E.sub.10 to E.sub.13 respectively. The combinations of C.sub.o to C.sub.3 shown in the parentheses in Table 1 are produced by a memory M. This memory M has a capacity of thirty-two words each consisting of eight bits and has five address inputs A.sub.0 to A.sub.4 and eight data outputs D.sub.0 to D.sub.7 for sixteen addresses ranging from an address No. 0 to an address No. 15. It is so programmed that, when C.sub.0 to C.sub.3 are applied to the address inputs A.sub.0 to A.sub.3 respectively while fixing the input to the address input A.sub.4 at "0", the contents according to the following Table 2 appear at the data outputs D.sub.0 to D.sub.7 of the memory M:

Therefore, the relation between the address inputs and the data outputs of this memory M will be as shown in the upper half of the following Table 3:

Thus, for example, A.sub.0 =0, A.sub.1 =0, A.sub.2 =0, A.sub.3 =1 and A.sub.4 =0 when c.sub.0 =0, c.sub.1 =0, c.sub.2 =0 and c.sub.3 =1. In this case, D.sub.0 (=c.sub.0 .sym.c.sub.1 .sym.c.sub.2)=0, D.sub.1 (=c.sub.0 .sym.c.sub.1)=0, D.sub.2 (=c.sub.1 .sym.c.sub.2 .sym.c.sub.3)=1, D.sub.3 (=c.sub.0 .sym.c.sub.1 .sym.c.sub.2)=0, D.sub.4 (=c.sub.0 .sym.c.sub.1)=0, D.sub.5 (=c.sub.0)=0, D.sub.6 =0, and D.sub.7 (=c.sub.0 .sym.c.sub.1 .sym.c.sub.2 .sym.c.sub.3)=1, and such information is read out from the corresponding address or address No. 1 of the memory M. The data outputs D.sub.0 to D.sub.7 of the memory M are applied to Exclusive-OR gates E.sub.0 to E.sub.7 respectively. According to Table 1 shown hereinbefore, c.sub.3 to c.sub.0 and a.sub.0 to a.sub.3 are applied to the other input of the Exclusive-OR gates E.sub.0 to E.sub.7 respectively. It is therefore apparent that the feedback shift register having the construction shown in FIG. 6 has the same function as that shown in FIG. 5.

Description will then be directed to changeover of the polynomial G(X) from the aforementioned one to, for example, G(X)=X.sup.8 +X.sup.4 +X+1. In such a case, the contents of the register after the application of the 4-bit data will be as shown in the following Table 4:

In the above table, c.sub.0 =a.sub.7 .sym.d.sub.0, c.sub.1 =a.sub.6 .sym.d.sub.1, c.sub.2 =a.sub.5 .sym.d.sub.2, and c.sub.3 =a.sub.4 .sym.d.sub.3.

The address input A.sub.4 among the five address inputs A.sub.0 to A.sub.4 of the memory M is fixed at "1" by the output of a polynomial selection circuit 10 so that, in response to the application of c.sub.0 to c.sub.3 to the address inputs A.sub.0 to A.sub.3 respectively, the contents according to Table 5 shown below appear at the data outputs D.sub.0 to D.sub.7 for sixteen address ranging from an address No. 16 to an address No. 31. Therefore, the relation between the address inputs and the data outputs of this memory M will be as shown in the lower half of Table 3 described hereinbefore. Thus, for example, A.sub.0 =0, A.sub.1 =0, A.sub.2 =0, A.sub.3 =1 and A.sub.4 =1 when c.sub.0 =0, c.sub.1 =0, c.sub.2 =0 and c.sub.3 =1. In this case, D.sub.0 =0, D.sub.1 (=c.sub.3)=1, D.sub.2 (=c.sub.2)=0, D.sub.3 (=c.sub.1)=0, D.sub.4 (=c.sub.0 .sym.c.sub.3)=1, D.sub.5 (=c.sub.2)=0, D.sub.6 (=c.sub.1)=0, and D.sub.7 (=c.sub.0)=0, and such information is read out from the corresponding address or address No. 17.

In this manner, the polynomial G(X) can be readily changed over by merely changing the address input A.sub.4 of the memory M from a "0" to "1".

It will be understood from the foregoing description of an embodiment of the present invention that the construction of the feedback shift register is not complex compared with that shown in FIG. 5 although its function is the same as that of the latter, and that the register can operate at a high speed since a plurality of data bits can be applied at the same time. Further, the present invention finds very useful practical applications because the polynomial G(X) can be changed over to any desired one by merely providing a simple selection circuit.