DD241800A1 - METHOD AND DEVICE FOR CORRECTION MORE BIT ERRORS - Google Patents

Abstract

The invention serves to correct bunching errors in bit serial data blocks. Their goal is to correct bugs that are made up of wrong and / or missing or too much recognized bodies. Two shift registers, the first of which is used in the forward direction for the generation and control of the cyclic code, are operated for correction in the backward direction and therefore have feedback paths which implement the inverse generator polynomial. Both shift registers receive the data in reverse order, the first starting from the remaining content and the second from the content zero. The Datenzuufuehrung and clocking is offset by the digit number error. Two comparators control the beginning and end of the correction when the shift registers match. The correction data arises from the antivalence of the values entered in the first shift register and those generated in the feedback path of the second shift register. Until the correction data is generated, the receive data is offset in reverse order by the digit number error. Areas of application of the invention are the information storage and the information transmission. Fig. 1

Description

Field of application of the invention

The invention relates to a method and a device for the correction of multi-bit errors which occur in the form of an error bundle in bit-serially represented data blocks.

Cyclic codes, preferably fire codes, are used for the correction. The generation of the code and the control at the reception is realized in a known manner by a shift register.

Bit-sized data blocks occur in information transfer and in most information storage methods. For example, in the case of magnetic disk memories, but also in the case of optical memories, the data is stored in the form of bit-serially represented data blocks. Even with magnetic tape memories, the information representation in each track can be interpreted as a series of bit-serial data blocks.

In all these methods, the information in one area can be falsified by a time-limited disturbance. For the correction of such error bundles, the method and the device can be advantageously used.

Characteristic of the known technical solutions

In all methods of information transfer or information storage errors may occur. Since in many cases the effort to increase the error safety is very high or makes it impossible to comply with other parameters, methods for error correction have been developed. In particular, such methods have gained importance, by which it is possible to correct error bundles.

Based on the known mathematical principles, a large number of solutions has been proposed that have advantages in terms of complexity or with regard to certain parameters.

A summary of the basics on cyclic codes and proposals for the design of correction devices were already given in 1961 by W. PETERSON in the book "Error correcting codes".

Further developments have been carried out with the aim of improving the ratio between the number of redundant locations and the length of the correctable error bundles. For this purpose, e.g. DE-OS 1905138, DE-AS 2014062, DE-AS 1524891 and with the restriction to two bits DE-AS 2162833 designed.

Another aim is to increase the speed of correcting the information, as indicated in DE-AS 2160 595 or DE-OS 3032468 as an advantage.

With the device according to DE-OS 2460263 "Slip errors" can be corrected, ie errors caused by a shift by S places from the otherwise assumed correct data stream, the same cyclic code is used as it is for correcting errors to Use comes.

However, all previously known methods require that the number of digits of the received data is correct and errors occur only by changing the content of the bodies in a certain area or caused by a total shift.

Known solutions assume that the error zero reception of a cyclic code, the remainder of zero in the division arises and each error can be regarded as an overlay with an error pattern that generates the same remainder as the error. After a defined number of shifts, the correction word is generated, which is then superimposed on the incorrectly received area. The correction possibility is recognized by the fact that only certain places have a non-zero content. Further developed solutions use the division of the shift register used for division and shift or additionally arranged decoders which respond to specific results or recognition devices which determine the range of error locations with a given probability. Other solutions modify the method through the use of multipliers or tables for transcoding. Since only the rest is assumed, it is not possible to correct missing or too much recognized positions.

Receive units for bit serial data blocks have a synchronizing device, by means of which the correct classification of the data takes place. If strong faults occur, the received data is corrupted so that only the fault bit pattern is detected. The synchronizer responds after a certain settling time on the Störbitmuster and thus loses the synchronism to the transmitting unit. After the end of the disturbances, the synchronism with the receiving data is restored. This has the consequence that in the area of the resulting error bundle can also be missing jobs or too many jobs can be detected. Such errors can not be corrected with all previously known devices.

Object of the invention

The object of the invention is to expand the possibilities for the detection and correction of error bundles and thus to increase the security in the transmission and storage of information in bit-serial representation.

Explanation of the essence of the invention

The object of the invention is to provide a method and a device with which error bundles can be corrected, which can be composed of wrong places, missing places, too many recognized places or the combination of wrong and too much or too little recognized places.

According to the invention the object is achieved in that a first shift register, which is used in the forward direction in a known manner for the generation and control of the cyclic code, is operated when a fault occurs in the reverse direction and therefore has a feedback path, which implements the inverse polynomial to the generator polynomial and, starting from the resulting residual content, the data is fed in reverse order. Furthermore, the solution includes a second shift register which is also operated in the reverse direction and has a feedback path which realizes the inverse polynomial to the generator polynomial and which, starting from the content zero, the data are also supplied in reverse order. This results in the first shift register, a content that matches the target content in the front error bundle and in the second shift register content that matches the target content in the area after the error bundle. The timing of the shift registers and the provision of the data for the shift registers is done by as many places offset, as is apparent from the difference of the received to the setpoint number, resulting in two shift registers content that refers to the same place. To implement the polynomials shift registers are used in which the exclusive-or stages are arranged in the feedback paths, so that forms in the registers of the quotient of the respective remainder, the parts of which shift gradually linear. For a polynomial of form

G (x) = (X ^C + 1) * P (x) points to an error bundle of length

the match of the least significant c places the point at which the correction must begin. Via a first comparison device, the correction process is now initiated by the first shift register continues to operate unchanged and the second shift register in the position X ^{0 of} the reverse direction, the same data are written, as they result for the first shift register. The correction data to be written in are generated by the exclusive-ORing of the written-in data of the point X ⁰ and the data formed in the feedback path of the second shift register. At the same time, the received data is shifted by the difference between the number of received and setpoint positions until the beginning of the generation of the correction data with the beginning of the backward reading of the data. Further features of the invention relate to variants. This concerns the use of parity detector circuits instead of the exclusive OR stages arranged in the feedback paths for all three feedback paths and that the data read to perform the correction in reverse order are fed to a shift register connected to two switching devices, the first of which Provides data for the first shift register and the second provides the data for both the second shift register and the rewrite of the shifted data, that the two switching means are set according to the difference between the received and the set digit numbers and that two address counters are present, of which the first one begins to read the data at the number of digits received and the second begins to write the data at the setpoint count and both counters are operated backwards.

embodiment

The solution according to the invention for the method and the device for the correction of multi-bit errors, which occur in the form of error bundles in bit-serially represented data blocks, wherein the error bundles can consist of erroneous and missing points or of incorrect and too many recognized points, will be used in the following example with a low number of digits be explained. Show

1 shows a block diagram of the solution according to the invention,

2 shows a table for the switching states generated by the control,

3 shows the contents of the shift register SR1, as it is obtained step by step upon receipt of the error-free polynomial E (x), FIG. 4 shows the contents of the shift registers SR1 and SR2, as it is in the correction of the erroneous data record E '(FIG. x), where

FIG. 5 shows the contents of the shift registers SR1 and SR2, as it results from the correction of the erroneous data record E "(x), where

in the record three digits are missing and Fig. 6: the contents of the shift registers SR1 and SR 2, as it results in the correction of the erroneous record E "'(x), where in the record three digits were recognized too much and three digits incorrect are.

For the embodiment, the following polynomial is used, which allows the correction of bundles of length b Si 3 in records of length 1 S 35:

G (X) = (X ⁵ +1) (X ³ + X + 1)

= X ⁸ + X ⁶ + X ⁵ + X ³ + X + 1

The corresponding inverse polynomial is then:

G * (x) = X ⁸ + X ⁷ + X ⁵ + X ³ + X ² + 1 The output data set is:

D (x) = X ¹⁰ + X ⁷ + X ⁵ + X ² + X + 1

All the following functional descriptions refer to the block diagram of FIG. 1 and the table of switching states of FIG. 2.

For the generation of the cyclic code, the gates A1 and A2 are opened via the lines 1 and 2 during the feeding of the data record D (x). Thus, the record passes via A2 and the OR gate 02 to the output C (x). At the same time, the data set via gate A2, OR gate 01 and gate A1 is fed to the forwardly operated shift register SR1. For this purpose, the shift register SR1 receives the forward shift clock Tvi. After all eleven digits of the data set have been entered, a content results in the shift register SR1

modX ⁹ = X ⁶ + X ⁵ + X ⁴ + 1

I ₁ (X)

G (x)

This content corresponds to the point a in FIG. 3. Now the gates A1 and A2 are blocked and via the line 3 the gate A3 is opened. This creates over A3 and O 2 of the rest to be attached

R '(x) = Kx) * G (x) mod X ⁹ = X ⁶ + X ⁵ + X ³ + X + 1 At the output C (x) the cyclic code C (x) = D (x) X ⁹ + R '(x)

When receiving the cyclic code E (x), gate A1 and gate A4 are opened. The receive data is fed via gate A4, the OR gate 01 and gate A1 to the forwardly operated shift register SR1, for which purpose the timing sequence Tvi is also applied. This results in the shift register SR1 gradually a content, as shown in Fig. 3 in the order from top to bottom. As a result of the erroneous record, the content is zero. In parallel, the data set via gate A4 and OR gate 05 is entered into the memory SP, in which it is arranged via a first address counter AZ1 in forward sequence. In the memory SP is the error-free record

E (x) = C (x) = D (x) * X ⁹ + R '(x)

Since the shift register SR2 is at zero, both comparators VE 1 and VE2 indicate the value "one" and signal the correctness of the data.

In the second case, it is assumed that the received data record has the correct number of digits but three incorrect digits, as shown in FIG. E '(x) consists of nine correct digits, followed by three incorrect digits and then again seven correct digits. The stepwise development of the contents of the shift register SR1 upon receipt of the record E '(x) is shown in Fig.4 in the order from top to bottom.

The result is in the order of presentation

11101100 and corresponds to l '(x) = X ⁵ + X ⁴ + X ² + X + 1

Since the shift register SR 2 has the content zero, the comparator VE 1 does not indicate a match, ie, V1 = 0. Since the digit number was correct, the first address counter AZ1 indicates k = η. This corresponds to the sequence according to 3b) in Fig.2. The correct number of digits causes the two multiplexers formed switching devices MX1, MX2 are brought over i = 0 and j = 0 in the normal position. Now the lines are laid 5 and 6 to "one" and operated in the reverse direction, both shift registers SR1 and SR2. For this purpose, the reverse shift Overclocks them are _R supplied 2i and T _R2. In the first cycle the point is corresponding to the first address counter AZ1 k = η With the second clock of the first cycle, the value above MX1 and A5 is applied to the shift register SR1 as well as via MX2, A6.1, 03., A6.2 and

04 is supplied to the shift register SR 2. At the same time, the value via MX2, A6.1 and 05 arrives at the entry of the memory SP "and is entered in the position η in accordance with the state of the second address counter AZ2, after which this process is repeated with the counter readings of the two address counters reduced by" one " AZ1 and AZ2. In the shift registers SR1 and SR2 thereby creates a content, as can be seen in Figure 4 in the order from bottom to top. After m = 7 steps have been executed, VE 1 indicates the match. Line 6 is now switched back and line 7 is set to "1", so that the data is only fed via MX 1 and A5 to shift register SR 1. The same values as are entered in position X ⁰ of shift register SR1 are transferred via A7.1 and 04 are also fed to the shift register SR2, which is indicated by dots in the table for SR2 in Fig. 4. The correction data are formed via A7.1, 03 and A7.2, which are fed via the OR gate 05 into the After three correction steps, both comparators VE 1 and VE2 indicate agreement, ie, V1 × V2 = 1, indicating that the correction is complete.

The remaining digits can be used by the input process of the record E '(x).

A third case is when a record is received where digits are missing. Fig. 5 shows a case where three digits are missing after receiving eight proper digits. The stepwise development of the contents of the shift register SR1 upon receipt of the record E "(x) is shown in the order from top to bottom in Fig. 5. The resulting content is at

01110001 and corresponds to l "(x) = X ⁷ + X ³ + X ² + X

The comparator VE 1 indicates a mismatch, since the shift register SR 2 has the content zero at this time, as required. Furthermore, the number of digits received is k = 16, while the setpoint number η = 19. In FIG. 2, the settings required for this are indicated under i.sub.3a and j = 0 under 3a). This results in the following sequence: Reading the digit by writing into the shift register SR 3. The value is entered via MX 2, A6.1, 03, A6.2 and 04 in the shift register SR 2, which is operated in the reverse direction. At the same time, the value is entered via MX2, A6.1 and 05 in the memory SP in the position η. After decrementing k and η, this process is repeated twice more. This corresponds to the expiration of the lowest three stages for SR 2 in FIG. 5. The fourth digit also becomes the line

5 is set to "1" and SR1 receives the backward shift clock T _R i, via MX 1 and A5, the value offset by i = 3 digits from the shift register SR 3 is supplied to the shift register SR1 1, the line 6 is switched to "zero" and the line 7 to "one", so that only SR1 receives the data offset by three digits, the same values as in the position X ^{0 of} the shift register SR1 is also entered to the input of the shift register SR2 via A7.1 and 04. This is indicated in Figure 5 by points in the table for SR 2. Via A7.1,03, A7.2 and 05, the correction data is written in the memory SP.

After three correction steps, there is a full match between the two shift registers SR1, SR2, which is indicated by V1 · V2 = 1. The correction process can be aborted because the remaining locations, i. the first received digits of the record E "(x) were correct.

FIG. 6 shows an example in which too many digits were recognized and additionally incorrect digits are contained. The record E "'(x) contains, in the sequence of the reception: twelve correct digits, the error bundle with three incorrect digits and three digits too many and at the end four correct digits, whereby the order of the false and too many recognized digits in the burst can be arbitrarily interpreted., The successive contents of the shift register SR1 are shown in Fig. 6 in the top-down order corresponding to the forward direction of SRL at the end of the record the content arises

10111110, the I "'(χ) = X ⁶ + X ⁵ + X ₄ + X ³ + X ² + 1

equivalent. The mismatch with the "zero" shift register SR 2 is indicated by V1 = 0. The number of digits received is k = 22, the setpoint number η = 19. Therefore, in the control, i = 0 and j = 3 are formed The control signals generated are indicated at 3c in Fig. 2. First, only the line 5 is switched to "one". The read data from the point k are entered in the shift register SR 3 and then immediately supplied via MX 1 and A5 to the shift register SR1 operating in the backward direction. Then k is decremented by "one." The setting η = 19 and SR 2 with content "zero" remains. Thus, the first three steps corresponding to the bottom three steps of the SR1 in FIG. 6 are executed. After the first j = 3 steps have been processed in the above-mentioned form, the line 6 is switched to "one" and the reverse shift clock Tr2 is supplied to the shift register SR 2. The first step in this setting is reading the position k -j = η = 19 and writing the value to the shift register SR 3. The data continues to go from the first position of the SR3 to the shift register SR1 via MX 1 and Ά5, and the data offset by three digits becomes the fourth stage of the shift register SR3, that is, port number 3 through MX2 At the same time, these data are entered via MX2.A6.1 and 05 into the position η = 16 of the memory SP This process repeats itself with the addresses counted back until, after the fourth step, the output V1 = 1 indicates the coincidence of the least significant five digits in the reverse direction, which causes the line 6 to switch back and the line 7 to "one " is placed. The shift register SR1 continues to receive the data on MX 1 and A5. The same values as are entered in the position X ^{0 of} the shift register SR1 also pass to the shift register SR 2 via A7.1 and 04. In FIG. 6, these steps are characterized by dots for the shift register SR 2. The correction data are generated via A7.1.0 3 and A7.2 and are supplied via the OR gate O 5 to the memory SP. After three correction steps V1 · V2 = 1 shows the full match of the two shift registers SR 1, SR2 and thus the end of the correction. The remaining digits have already been properly written into the memory SP from E "'(x) and thus can be taken over." In practice, the exclusive-or stages in the feedback paths can be effectively replaced by parity detector circuits.

The device can be designed for any number of digits, correctable burst length and digit number differences. For the dimensioning applies: A polynomial of the form

G (x) = (X ^c +1) -P (x)

has the degree

g = c + p (p = degree of P [x])

and can be under the condition

- c> p +.1 error bundle of length

in records of length

correct.

For this purpose use:

SR 1, SR 2 with a number of digits g

VE1 with a number of digits -b

VE2 with one digit number b

SR3 with a number of positions max (i + 1, j + 1)

MX1 with a number of inputs i + 1

MX2 with a number of inputs j + 1

For the nominal number of points η = d + g

of the data record applies

k = n + jSI

For this purpose use:

SP with a number of digits k = η + j

AZ1 with a number of characters k = n + j

AZ2 with an item number η

Claims (4)

claims: 1. A method for correcting multi-bit errors that occur in the form of error bursts in bit serially displayed data blocks and can be composed of wrong and missing digits or from wrong and additionally inserted digits, using cyclic codes, preferably fire codes, using a first shift register operated in the forward direction and having a feedback path for the generation of the generator polynomial G (x), both the generation of the cyclic code and the control on reception, characterized in that the first shift register (SR 1) is used for the correction is operated backward and realized by means of a feedback to the generator polynomial inverse polynomial G * (x), this shift register (SR 1) starting from the resulting remainder of the data block is fed in reverse order and that a second shift register (SR2) is also operated backwards and means a feedback The polynomial G * (x), which is inverse to the generator polynomial, is also implemented, this shift register (SR 2) being fed backwards from the content zero and the backward shift clocks (T _R1 , T ^) being fed to the shift registers (SR 1, SR 2) and the provision of the data are offset by as many digits as is apparent from the difference of the received to the setpoint number that the contents of the shift registers (SR1, SR2) are compared with each other, wherein for a polynomial of the form G (x) = (X ⁰ +1) · P (x) first, the least significant c positions are compared with each other, and the coincidence generating the correction points is triggered and the remaining ρ locations are compared and the match is indicated at the end of the correction and the correction character generation takes place in the form that the first shift register (SR 1 ) is operated unchanged and in the second shift register (SR2) stepwise into the stage X ^0, the same values are written, as they result for the first shift register (SR 1) and that while the inscribed in the point X ⁰ and via the feedback values generated by the second shift register (SR 2), the correction points to be used are generated and that the data received from the beginning of the reverse reading until the beginning of the generation of the correction points are shifted by the difference between the number of received and setpoint positions. 2. The method according to claim 1, characterized in that the data read in order to perform the correction in reverse order are supplied to a third shift register (SR3), which is connected to two switching devices (MX1, MX2), of which the first (MX 1) provides the data for the first shift register (SR 1) and the second (MX2) provides the data for the second shift register (SR 2) that the two switching means (MX 1, MX 2) are set according to the difference between the received and the setpoint number and that two address counters (AZ 1, AZ2) are present, of which the first (AZ 1) for reading the data starts at the number of digits received and the second (AZ2) for writing the data starts at the setpoint number and that both address counter (AZ 1, AZ2) are operated backwards. 3. A device for correcting multi-bit errors, which occur in the form of error bursts in bit serially displayed data blocks and may be composed of wrong and missing digits or wrong and additionally inserted digits, using cyclic codes, preferably fire codes, using a first shift register operated in the forward direction and having a feedback path for the generation of the generator polynomial G (x), both the generation of the cyclic code and the control on reception, characterized in that the first shift register (SR 1) for the reverse operation has a feedback path (RW 12) and a second shift register (SR2) is provided, which also has a feedback path (RW22) for the reverse operation, that exclusive-or stages for realizing the polynomials in all feedback paths (RW 11, RW12, RW22) (EO) are arranged, that two Vergleichseinrichtunge n (VE 1, VE 2) are connected between the shift registers (SR 1, SR 2) for comparing the least significant c digits (VE 1) and the remaining ρ digits (VE 2), that a third shift register (SR 3) provided to supply the data read for performing the correction in reverse order, which is connected to two switching means (MX 1, MX 2), of which the first (MX 1) with the first shift register (SR 1) and the second (MX2) with the second shift register (SR2) is in communication and that finally for reading the data, a first address counter (AZ 1) and for writing the data, a second address counter (AZ2) are present. 4. Device according to claim 1, characterized in that in the feedback paths (RW11, RW12, RW22) arranged exclusive OR stages (EO) is replaced in each path by a parity detector circuit. For this 4 pages drawings