Fault-tolerant device

FIELD: computer engineering, possible use in combination devices, and also devices for storing and transferring information.

SUBSTANCE: device contains original circuit, four groups of AND elements, group of OR elements, encoding device, folding circuit, register, error syndrome circuit, checks circuit, three decoders, corrector.

EFFECT: decreased number of controlling discharges.

1 dwg, 1 app

The invention relates to computer technology and can be used to improve the reliability in the functioning of the combinational devices, as well as the storage and transmission of information (operational and permanent storage of the computer devices and the like).

Known discrete self-correcting device [1], which uses the decoding device correcting unit (byte) of the error based on application of the reed-Solomon codes with the original schema, the encoder, the redundant circuit, a decoding device that includes a circuit calculations syndrome, shaper imaginary syndromes decoder errors in a byte, the scheme of calculation of a malformed byte, switches, errors, offset errors, the input devices are connected to the inputs of the original scheme and to the inputs of encoder outputs encoder devices are connected to the inputs of redundant circuits, the outputs of which are connected to first inputs of the circuit computing the syndrome, the outputs of the original circuit connected to the second inputs of the circuit computing the syndrome and to the first inputs of the offset, the output schema of the calculation of the syndrome are connected to the inputs of decoder errors, the outputs of which are connected to second inputs of the offset, the outputs of the corrector are the outputs of the device.

The disadvantage of this device is the low reliability of funktsioniruyuschaya, since reed-Solomon allow you to correct the error in one byte of information, and to detect an error in the two bytes of information, in addition, these codes cannot be used when a small number of information bits.

The closest technical solution is self-correcting discrete device [2], containing the original schema, the first encoder, a diagram of the syndrome of the error, the decoder error corrector, second, third and fourth encoders, the first through fourth convolution scheme, the scheme of the sign of the error, the element OR the input device is connected to a source schema and to the inputs of the first encoding device, to the second inputs of encoder and outputs of the original circuit connected to the inputs of the third and fourth coding device, to the first input of the corrector whose outputs are the outputs of the device, the outputs from the first to the fourth coding devices connected respectively to the inputs of the first through fourth circuits convolution, the outputs of the first and third circuits convolution is connected to the input circuit of the syndrome of the error, the outputs of the second and fourth circuits convolution connected to the inputs of the circuit characteristic of the error, the output circuit of the syndrome of the error and the error indicator connected to the inputs of decoder errors, the first group of outputs of decoder errors connected to the second inputs of the offset, and W heaven group of outputs connected to the input item (OR, since the output of which is signal "failure".

The disadvantage of this device is a great informational redundancy.

The aim of the invention is to reduce the number of control bits.

This objective is achieved in that the device contains the original scheme, the encoder, the convolution scheme, the scheme syndrome of the error, the first decoder, the corrector, the information input device connected to the first inputs of the original scheme, the outputs of which are connected to first inputs of the offset, the outputs of the corrector connected to the inputs of the convolution scheme, the outputs of the corrector are the outputs of the device, characterized in that it further comprises first to fourth elements And the element OR register, the scheme checks, the second decoder, the third decoder, the address inputs, the input write input read input "Reset"moreover , the information input device connected to the first inputs of the first element And the address inputs connected to the second inputs of the original circuit and to the first inputs of the register, the input record is connected to the third input of the source schema to the second input of the first element And to the second input register, input reading is connected to the fourth input of the source schema to the first input of the second element And to the first input of the third element And to the first input of the fourth element And to the third input re the Istra, the input "Reset" is connected to the fifth input source circuit and to the fourth input of the register, the outputs of the original circuit connected to the first inputs of the circuit checks and to second inputs of the second element And whose outputs are connected to first inputs of the element OR the second input of which is connected to the outputs of the first element, And outputs connected to the inputs of encoder outputs encoder devices are connected to the inputs of the convolution scheme, the outputs of which are connected to second inputs of the third element And the fifth inputs of the register, the first input circuit of error syndromes are connected to the outputs of the third element And the second inputs connected to the outputs of the register, and outputs connected to the second inputs of the circuit checks and to the inputs of the first decoder, the outputs of which are connected to first inputs of the third decoder, the outputs of the circuit checks connected to the inputs of the second decoder, the outputs of which are connected to second inputs of the third decoder, the outputs of the third decoder is connected to the second inputs of the fourth element And whose outputs are connected to second inputs of the offset.

The drawing shows a block diagram of the device.

The device comprises a source schema 1, the first element 2 And the second element 3 And the third element 4 And the fourth element 5 And element 6 OR, the encoder 7, the convolution scheme 8, a diagram of the syndrome error 9, scheme about eroc 10, the first decoder 11, the second decoder 12, the third decoder 13, a register 14, the corrector 15 information 16 inputs, address inputs 17, entry 18 entry, entry 19 reading input 20 reset, the outputs 21 of the device.

An information input device 16 is connected to the first input source circuit 1 and to the first inputs of the first element 2 And the outputs of the original circuit 1 is connected to the second inputs of the second element 3 And to the first input circuit 10 checks and to the first input of the corrector 15, the outputs of the corrector 15 are the outputs 21 of the device address input 17 is connected to the second input source circuit 1 and to the first inputs of the register 14, entry 18 entry connected to the third input source circuit 1 to the second input of the first element 2 And to the second input register 14, entry 19 reading connected to the fourth input source circuit 1, to the first input of the second element 3 And to the first input of the third element 4 And to the first input of the fourth element 5 And to the third input register 14, entry 20 "Reset" is connected to the fifth input source circuit 1 and to the fourth input register 14, the outputs of the second element 3 And is connected to the first inputs of the element 6 OR the second input of which is connected to the outputs of the first element 2, And outputs connected to the inputs of encoder 7, the outputs of the coding device 7 is connected to the input circuit 8 convolution, the outputs of which are connected to second inputs t is Atego element 4 And to the fifth input of the register 14, the input circuit 9 of the syndrome of the error connected to the outputs of the third element 4 And second inputs connected to the outputs of the register 14, and outputs connected to the second inputs of the circuit 10 checks and to the inputs of the first decoder 11, the outputs of which are connected to first inputs of the third decoder 13, the output circuit 10 checks connected to the inputs of the second decoder 12, the outputs of which are connected to second inputs of the third decoder 13, the outputs of the third decoder 13 is connected to the second inputs of the fourth element 5 And whose outputs are connected to second inputs of the corrector 15.

The encoder 7 is designed for:

1) implementation of right and left diagonal checks based on the use of groups of adders for mod 2, when recording information in accordance with the rules presented in the Appendix. Diagonal check form the vector R=r₁,r₂,............r_2l.;

2) formation of a (similarly) vector control bits R^Padopted code set on the basis of the information read from the outputs of the original circuit 1.

Thus, during recording and reading information, the output of encoder 7 are respectively the vectors of control bits:

R=r₁,r₂,............r_2l,,

R^P=r₁ ^P,r^P ₂,............r^P _2l.

With the EMA 8 convolution is designed to minimize the number of control bits of left and right diagonal checks (for the information matrix, containing an even number of columns) by adding at the mod 2 value of the first discharge diagonal checks with other discharges diagonal checks.

Scheme 9 syndrome errors represent a bitwise comparison and is designed to generate values of the syndrome of the error based on the transmitted and received information.

The circuit 10 checks the values of the information bits and the values of the bits of the error syndrome generates a vector of additional checks.

The first decoder 11 when an error generates at one of its outputs a single signal in accordance with the incoming value of the syndrome of the error.

The second decoder 12 generates at one of its outputs a single signal in accordance with the incoming value additional checks.

The third decoder 13 by the values in accordance with the value of the syndrome of the error and the value of the additional checks generates the control signal corrector 14 to correct erroneous information bits.

The register 14 is intended for storage of signal values of the vector control bits generated when recording information in the source scheme 1.

Corrector 15 is designed to correct errorsappearing at the outputs of the original circuit 1, and implements the function regarding manage is their signals u _ioutputs of decoder:

The device operates as follows. Before you begin to input 20 signal that sets the device to its original state. When the input information to the information 16 inputs, address inputs 17 and signal "Write" to the input 18 of the information is written to the specified address in the source scheme 1. At the same time she arrives at the inputs of the first element 2 And open the input 18, and then through the element 6 OR the input information is fed to the input of the coding device 7. The encoder 7, based on the group of adders for mod 2, implements the right and left diagonal verification of the information matrix.

Scheme 8 convolution reduces to a single digit number of digits to the right and left diagonal checks by adding in the mod 2 value of the first discharge diagonal checks with other discharges diagonal audits (see Appendix).

With the output circuit 8 convolution value vector control is transferred to the input register 14 and written to the specified address.

When reading information on the address signals from the output of the source circuit 1 through the second element 3 And is opened by the signal "Read" input 19, item 6, OR re-fed to the input of the coding device 7, where the signal value is Alov in the control bits of the diagonal checks the received information, and scheme 8 convolution is carried out to minimize these risks.

The information from the outputs of the convolution scheme 8 is fed to the input circuit 9 of the syndrome of the error, on the second input of which receives the information read from the register 14.

As a result, the output of the circuit 9 syndrome errors are generated value of the syndrome of the error.

The circuit 10 checks the values of the information bits and the values of the bits of the error syndrome generates a vector of additional checks on the rule stated in the application.

The first decoder 11 when an error generates at one of its outputs a single signal in accordance with the incoming value of the syndrome of the error.

The second decoder 12 generates at one of its outputs a single signal in accordance with the incoming value additional checks.

The third decoder 13 according to the values of the syndrome of the error and additional checks generates the control signal corrector 14 to correct erroneous information bits.

Application

Correction of errors in a single byte and error detection in the remaining bytes of information is achieved through an iterative code.

The procedure of constructing a two-dimensional iterative code is as follows [3]. Given a set of information symbols are divided into groups (blocks, modules) information, b-discharges in to the each group. Received information modules are in the form of the information matrix (1):

Next, the encoding information according to the method of parity (by adding on mod 2 characters of rows and columns of the resulting matrix). The result is a two-dimensional iterative code to detect and correct any single error:

where H=h₁h₂,...h_mthe vector of parity rows; Z=z₁,z₂,...z_bthe vector of parity columns. Vector parity rows and columns form a set of control bits R₁={r₁,r₂,r_m,r_m+1,...,r_b}. When receiving a code combination regarding information bits of the re-formed values of the control bits R^P ₁={r₁,r₂,r_m,r_m+1,...,r_b}. In this case, the difference between the transmitted control bits and received after the receipt of the information forms the syndrome of the error E:

While the bits of the error vector e₁e₂...e_m(received regarding the vector of parity lines) indicate the module information having an error, and the digits of e_me_m+1...e_b(received regarding the vector of parity columns) indicate an erroneous discharge in the module and the formation.

As the code combinations of the rows and columns have minimum distance d=2, then the minimum distance of this code is d=4. This code allows you to correct any single error and detect a significant share of multiple-error.

Patterns of errors not detected two-dimensional iterative code shown:

Figure 1 Patterns of errors not detected two-dimensional iterative code: (a) errors of multiplicity 4; b) errors of multiplicity 6.

Fig.2 the structure of the errors of the two-dimensional iterative code, leading to erroneous correction: (a) the error ratio of 5; (b) error ratio 7.

In the General case, one can construct an iterative codes higher dimensions (three-dimensional, four-dimensional, and so on), where each information symbol will be the component simultaneously of two different code words. The parameters of iterative codes the dimension of x as follows [3]:

where n_i, k_id_irespectively the length, the number of information bits, the minimum distance between the code sets of rows and columns.

On this basis, to build an iterative codes you should use a test that has the highest detection capability.

So, the organization diagonal checks the considered matrix will allow in order to reveal patterns of errors not detected iterative code that implements parity rows and columns.

The structure of the diagonal checks that detect considered errors is presented on Fig.3.

Fig.3 Structure of diagonal checks:

- results-right diagonal inspections;the results of the left diagonal checks

The results of the left diagonal checks are generated by the rule:

The results of the right diagonal checks are formed by summing the values of the following information categories:

In this case, the total number of diagonal checks equal to 2l or:

Example 1. Let's consider the word consists of four information bits, which have zero values. For this code set information matrix has the form:

In this case, the parity rows and columns of the information matrix will give a zero value and in addition will have zero values, the results of all right and left diagonal checks. If an error occurs, all the information bits have odd error not detected womern the m iterative code because of the even parity of rows and columns of the information matrix are zero values:

At the same time, right and left diagonal checks will result 101.

Approval 1. Iterative code that implements the right and left of the diagonal scan detect all odd errors that are not detected two-dimensional iterative code, and identifies odd errors, perceived two-dimensional iterative code as corrected.

In turn, there are patterns of errors not detected by the iterative code that implements the right and left diagonal checker and parity rows and columns. Structure of the considered errors are presented in Fig.4.

Fig.4 Structure of errors not detected diagonal checks.

For example, regarding the information matrix with zero diagonal checks will not be detected following structure errors:

In order to exclude the appearance of the considered errors, the information matrix should contain no more than two lines.

2 approval. For the information of the matrix b×2 iterative code that implements the right and left of the diagonal scan detect all possible errors.

Corollary 1. For information the matrix b× 2 iterative code that implements the right and left diagonal checks distinguishes all possible errors.

Assertion 3. When conducting diagonal checks for the information matrix b×2 errors are detected and are different if the number of control bits is equal to:

where k is the number of information bits.

Thus, when using four-dimensional iterative code code set is transmitted in the form:

The result of the addition of signal values of the control bits sent and received, will give the syndrome of the error:

where the bits of the error vector r₁,r₂......r_lcorrespond to right diagonal scan; r_l,r_l+1......r_2lleft.

For the considered example, the encoding information is as follows:

In table 1 presents the values of the syndrome of the error (relative error-free zero set)obtained when carrying out the right and left diagonal checks for erroneous sets of information matrix 2×2 (cover errors only in the informational bits).

Naturally, this code has too much redundancy, so there is required the industry to minimize the number of control bits.

Proposition 4. When conducting diagonal checks for the information matrix b×2 errors are detected and are different if the number of control bits is equal to:

that is, the number of control bits is reduced by two.

In this case, the information matrix has an even number of columns, reducing the number of control bits can be performed by convolution of the values of left and right diagonal checks, for example by adding to the first category of e₁, (e_l+1) considered subsets of the syndrome of the error with the rest of the digits.

For the information matrix, containing an odd number of columns, reducing the number of control bits can be performed by convolution of the values of the right (left) diagonal checks, for example by adding to the first category of e₁the values of the digits of the left subset of the syndrome of the error with the other bits, then adding the first digit of the right subset of the values of the syndrome of the error with the other bits of this subset.

Then for this example the table of syndromes of errors can be presented in table 2.

On the basis of the received encoding rules formed the decoding strategy, which solves the problem of distinguishing osibo the information and check bits and correction of errors.

To this end relative to the obtained values of the syndromes of errors there are extra checks:

For the considered example, additional checks are of the form:

In table 3 presents the values of the syndromes of errors and the values of the additional checks received with respect to part of the errors in the information bits, check bits, and at the same time in control and information digits:

The analysis of the table of the obtained results allows us to formulate the following statement:

Proposition 4. For the information of the matrix b×2 minimized the number of values of the syndromes of errors and the values of additional checks can detect and distinguish between errors in the information and check bits.

In this case, to save hardware costs should be limited to correcting errors in the information bits. Then the required number of values of the syndromes of errors (values additional checks) will be:

From this example it follows that minimized the number of control razreda which allows you to correct any possible error in the information bits, except for such combinations of errors in the information and check bits that will put the wrong code set to allowed, which is a significant lack of any linear code.

Sources of information

1. Shcherbakov NS Reliability of digital devices. M.: Mashinostroenie, 1989, 224 S. 39, is.

2. A positive decision on the application (21)99111190/09 from 15.01.03 (filed 31.05.09), authors: Tsarkov A.N., Kinless BY, Novikov N., Romanenko Y.A., Pavlov A.A.

3. Has had AA P. Rudnev improving the reliability of digital devices methods of redundant coding. M: Energy, 1974, 270 S.

Failover device containing the original scheme, the encoder, designed to exercise the right and left diagonal checks and forming vector control bits, the convolution scheme designed to minimize the number of control bits, the syndrome of the error, the first decoder, the corrector is designed to correct errors that occur at the outputs of the source schema, the information input device connected to the first inputs of the original scheme, the outputs of which are connected to first inputs of the offset, the outputs of the corrector are the outputs of the device, characterized in that it further comprises four groups of elements And group elements OR the register, the scheme is of rovero, a second decoder, the third decoder, the address inputs, the input write input read input "Reset", and the information input device connected to the first inputs of elements And the first group of address inputs connected to the second inputs of the original circuit and to the first inputs of the register, the input record is connected to the third input of the source schema to the joint second inputs of elements And the first group and the second input register, input reading is connected to the fourth input of the source schema to the United first inputs of elements And the second group, to the United first inputs of elements And the third group, first United the inputs of the elements of the fourth group and to the third input register, input "Reset" is connected to the fifth input source circuit and to the fourth input of the register, the outputs of the original circuit connected to the first inputs of the circuit checks and to the second inputs of elements And the second group, the outputs are connected to first inputs of elements OR groups of elements OR, the second inputs of which are connected to the outputs of the elements And the first group, and outputs connected to the inputs of encoder whose outputs are connected to the inputs of the convolution scheme, the outputs of which are connected to the second inputs of elements And the third group and to the fifth input of the register, the input circuit of the syndrome of the error connected to the outputs of the elements And the third group, is that the inputs connected to the outputs of the register, and outputs connected to the second inputs of the circuit checks and to the inputs of the first decoder, the outputs of which are connected to first inputs of the third decoder, the outputs of the circuit checks connected to the inputs of the second decoder, the outputs of which are connected to the second inputs of the third decoder, the outputs of which are connected to the second inputs of the elements of the fourth group, the outputs of which are connected to the second inputs of the offset.