Fault-tolerant information storage device

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

SUBSTANCE: device contains memorizing device, four groups of AND elements, AND element, group of OR elements, seven OR elements, encoding device, register, error syndrome circuit, NOT element, inversion block, decoder, even parity check circuit, corrector.

EFFECT: increased trustworthiness of device operation.

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 the functioning of the disorder, since reed-Solomon allow you to correct the error in one byte of information, and to detect an error in two bytes.

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 the second group of outputs connected to the input of the OR element, the output of which is removed signal is "failure".

The disadvantage of this device is the low reliability of operation, so as not corrected errors that occur simultaneously in the information and check bits.

The aim of the invention is to increase the reliability of operation of the device due to the correction of 94% of the detected errors does not exceed the multiplicity k-1, subject to a maximum detection number of errors in the code set.

This objective is achieved in that the device contains the original scheme, the encoder, the scheme of the syndrome of the error, the 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 are the outputs of the device, further comprises between the first and fifth elements And, from first to eighth elements OR scheme, parity, block inversion, the register, the element does NOT address inputs, input write input read input "Reset", and the information input device connected to the first inputs 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 original silent hill is we, 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 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 second inputs of the second element And whose outputs are connected to first inputs of the first element OR the second input of which is connected to the outputs of the first element, And outputs connected to the inputs of the circuit of parity, to the inputs of the block inversion and to the first inputs of encoder, the output circuit of the even parity is connected to the second input of the coding device, to the second inputs of the third element And the fifth inputs of the register, the outputs of the block inversion is connected to a third input of the coding device, the outputs of encoder connected to the third inputs of the third element And to the sixth input 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 inputs of the decoder and to the inputs of the second element OR the output of which is connected to the first input of the fifth element And the first group of outputs of the decoder are connected to the inputs of the third element OR the second group of outputs decoder connected to the inputs of the fourth element, OR the third group of vicodindesyrel connected to the inputs of the fifth element OR the fourth group of outputs of the decoder are connected to the inputs of the sixth element OR group of outputs of the decoder are connected to the inputs of the seventh element, OR the outputs from the third and sixth elements OR connected respectively with the second, fourth and fifth inputs of the fourth element And first to fourth inputs of the eighth element OR the output of the seventh element OR is connected to the fifth input of the eighth element OR the output of which through the element is NOT connected to the second input of the fifth element And the fifth input element And an output device that outputs the fourth element And connected to the 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, the second element And 3, the third element And 4, the fourth element And 5, the fifth element And 6, the first element OR 7, the second element, OR 8, the third element OR 9, the fourth element, OR 10, the fifth element OR 11, the sixth element OR 12, the seventh element OR 13, the eighth element OR 14, the encoder 15, a diagram of the syndrome of the error 16, a decoder 17, the corrector 18, figure 19 parity, block 20 inversion, the register 21, the element NOT 22, informational inputs 23, the address input 24 input 25 entries, entry 26 reading input 27 reset, the outputs 28 of the device, the output 29 "Failure".

An information input device 23 is connected to the first inputs of first the element 2 to the first input source circuit 1, the outputs of which are connected to the first input of the corrector 18, the address input 24 is connected to the second input source circuit 1 and to the first inputs of the register 21, entry 25 entries connected to the third input source circuit 1 to the second input of the first element 2 and to the second input register 21, entry 26 reading connected to the fourth input source circuit 1, to the first input of the second element And 3, to the first input of the third element And 4, to the first input of the fourth element 5 and to the third input of the register 21, entry 27 "Reset" is connected to the fifth input source circuit 1 and to the fourth input register 21, the outputs of the original circuit 1 is connected to the second inputs of the second element And 3, the outputs of which are connected to first inputs of the first element OR 7, the second input of which is connected to the outputs of the first element 2, and outputs connected to the inputs of the circuit 19 of parity, to the inputs of the block 20 of the inversion and to the first inputs of encoder 15, the output circuit 19 of the even parity is connected to the second input of the coding device 15, to the second inputs of the third element And 4 and to the fifth input of the register 21, the outputs of the block 20 inversion is connected to the third inputs of encoder 15, the outputs of encoder 15 is connected to a third input of the third element And 4 and to the sixth input of the register 21, the first input circuit 16 syndromes errors connected to the outputs of the third e is ment And 4, the second inputs connected to the outputs of the register 21, and outputs connected to the inputs of decoder 17 and to the inputs of the second element, OR 8, the output of which is connected to the first input of the fifth element And 6, the first group of outputs of the decoder 17 is connected to the inputs of the third element OR 9, the second group of outputs of the decoder 17 is connected to the fourth inputs of the OR element 10, the third group of outputs of the decoder 17 is connected to the inputs of the fifth element OR 11, the fourth group of outputs of the decoder 17 is connected to the inputs of the sixth element OR 12, the fifth group of outputs of the decoder 17 is connected to the inputs of the seventh element OR 13, the outputs the third 9 on the sixth of 12 items OR connected respectively with the second, fourth and fifth inputs of the fourth element and 5, And first to fourth inputs of the eighth element 14 OR the output of the seventh element OR 13 is connected to the fifth input of the eighth element OR 14, the output of which through the element is NOT 21 is connected to the second input of the fifth element And 6, the input of the fifth element And 6 is an output device that outputs the fourth element 5 is connected to the second input of the corrector 18.

Scheme 19 parity is designed for forming the control of the discharge of parity on direct and inverse values of the information bits.

The block 20 of the inversion is to invert the values of the information razreda is, outputs of the first element OR 7, respectively, when reading and writing information.

In the encoding device 15 information bits and parity bit are represented as two-line information matrix:

where_i,r_CHET,respectively the direct and inverse values of the i-th information bits and a value of the discharge parity code set.

Relative to the formed matrix encoding device 15 are the right and left diagonal checks.

The number of diagonal checks is determined by the formula:

R_D=2(k+2).

When reading information, the encoder 15 generates (similarly) vector control bits R^Padopted code set.

Thus, during recording and reading information on the output of the coding device 15 are respectively the vectors of control bits:

R=r₁r₂no, r_2(k+2),

R^P=r₁ ^Pr^P.................................... r^P _2(k+2).

Scheme 16 syndrome of the error is for bitwise comparison of the values of the control bits received in the transmission code set and formed relative to this value the deposits of the information bits and the direct and inverse value of the control bits parity. It represents the set of adders for mod 2 (the number of control bits is the number of diagonal checks matrix and one discharge parity).

The result of the addition in mod 2 values of the signals transferred and formed the control bits will give the syndrome of the error:

E=e₁e₂e₃...........e_2(k+2)e_CHETe_CETIN.

The decoder 17 contains 2k+6 inputs (the number of bits of the error syndrome) and L=l₁+l₂outputs (number of schema matching, representing 2k+6 - input And schema), where

- l₁- group elements And for the various syndromes that characterize errors only check bits);

- l₂- group elements And (for syndromes that characterize the errors that occur simultaneously in the information and check bits).

In case of an error on one of its outputs is formed of a single signal.

The outputs of the decoder 17 combined respectively into one output using third element OR 9, the fourth item OR 10, the fifth element OR 11, the sixth (k-th) element OR 12 for generating control signals to the corrector, respectively, for the correction of the first, second ...the k-th information bits.

The seventh element OR 13 combines the outputs of the decoder 17, the outputs of circuits And)belonging to the subset of l₁and the corresponding occurrence isibonelo in the control bits (which do not require the formation of control signals for concealer).

Corrector 18 includes k elements disparities and is designed to repair errorsappearing at the outputs of the original circuit 1. When error correction is implemented function with respect to control signals ui outputs of elements OR:

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

When errors occur, belong to the subset of n₁for the same syndromes, indicating an error in a variety of informational bits (having the same value of syndromes and additional checks, see Appendix), characterized by the presence of singular values on the output of the circuit 16 syndromes of errors and the absence of unit values on the outputs from the third 9 on the seventh of 13 items, OR using the second element, OR 8, the eighth element OR 14 element 22, the fifth element And 6, a signal is generated ″Failure″.

The device operates as follows. Before you begin to input 27 of the signal that sets the device to its original state. When the input information to the information input 23, the address inputs 24 and signal ″Record″ input 25 information is written at the specified address and the output of the circuit 1. At the same time she arrives at the inputs of the first element 2 And open the input 25 and then through the element OR 7 input information is supplied to the first input of the coding device 15, to the input circuit 19 of the even parity and the input unit 20 of the inversion. To the second input of the coding device 15 receives the value of the discharge parity information bits, and the third input receives the inverse values of the information bits. From the received bits, parity, direct and inverse values of the information bits is formed two-line information matrix, against which in the encoding device 15 based on the group of adders for mod 2, are arranged right and left diagonal checks.

With outputs of encoder 15 is a vector of control bits received at the input register 21 and is written at the specified address, which is also written direct and inverse values of discharge parity outputs of circuit 19 parity.

When reading information on the address signals from the output of the source circuit 1, through the second And gate 3 is opened by the signal "Read" input 26, the element OR 7 re-fed to the input of the coding device 15, which are formed of the values of signals in the control bits regarding information matrix, is formed on the obtained information.

The information from the outputs of the coding device 15 through the third element And 4 is fed to the input circuit 16 of the syndrome of the error, on the second input of which receives the information read from the register 21.

Scheme 16 syndrome error performs a bitwise comparison of the values taken control of discharges and formed relative to the received information.

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

The decoder 17 when an error generates at one of its outputs a single signal in accordance with the incoming value of the syndrome of the error. Depending on the number of information digits, having an error control signal appears at the output of the corresponding (9...12) OR. This signal through the open fourth element 5 is fed to the input of the corrector 18, where the correction of erroneous information bits.

If the error occurred only in the control bits of the signal appears at the output of the seventh element OR 13 (not required to apply control signals to the corrector).

The outputs of the decoder 17 combined respectively into one output using third element OR 9, the fourth item OR 10, the fifth element OR 11, the sixth (k-th) element OR 12 for generating control signals for a concealer that matched the public for the correction of the first, second ...the k-th information bits.

The seventh element OR 13 combines the outputs of the decoder 17 outputs schemes And)belonging to the subset of l₂and the corresponding errors only check bits (which do not require the formation of control signals for concealer).

Corrector 18 includes k elements disparities and is designed to repair errorsappearing at the outputs of the original circuit 1. When error correction is implemented function with respect to control signals ui outputs of elements OR:

When errors occur, belong to the subset of n₁for the same syndromes, indicating an error in a variety of informational bits (having the same value of syndromes and additional checks, see Appendix), characterized by the presence of singular values on the output of the circuit 16 syndromes of errors and the absence of unit values on the outputs from the third 9 on the seventh of 13 items, OR using the second element, OR 8, the eighth element OR 14 element 21, the fifth element And 6, a signal is generated ″Failure″.

Application

Correction of errors of a given multiplicity, provided error detection in other bits of information may be accomplished on the basis of it is exploring the 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-bits in 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. Vectors 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:

When this bit of the syndrome of the error e₁e₂...e_m(received otnositel 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 information.

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) error ratio of 6.

Fig.2 the structure of the errors of the two-dimensional iterative code, leading to erroneous correction: (a) 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 Kodo the use of checks, with the highest detection capability.

So, the organization diagonal checks the considered matrix will help to identify patterns of errors not detected by the iterative code that implements parity rows and columns.

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

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 two-dimensional iterative code, since the parity p is K and the 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 check, and parity check rows and columns. Structure of the considered errors are presented in Fig.4.

Fig.4 Structure of errors not detected diagonal checks and inspections of rows and columns.

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 the maximum number of possible errors (except for sets 2^k-1 forbidden code sets, Transfo miroamer in the allowed code sets).

Thus, when using iterative code that implements the right and left diagonal check and parity, code set is transmitted in the form:

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

r₁=y₁; r₂=y₂⊕y₃; r₃=y₄; r₄=y₃; r₅=y₁⊕y₄; r₆=y₂.

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_2l- match the right diagonal checks, r_l, r_l+1.........r_2l- left and formed relative to the received information bits;

values obtained control bits.

Property 1. There are configuration errors in the information and check bits, for which the error syndromes have the same value.

To distinguish between these errors when forming the values of the syndromes of errors there are extra diagonal checks:

Thus, each error from a variety of errors M=(2ⁿ)k can be put into correspondence with the value of the error syndrome is and the value of additional diagonal checks.

Property 2. Each set of values of the syndrome and error values for additional inspections corresponds to a subset of the Q-error of different configurations.

Corollary 1. To distinguish between errors that belong to this subset, it is necessary to limit the ratio of corrected errors and to increase the number of control bits (to implement the additional coding information bits).

In this regard, the proposed encoding method includes the following provisions:

1) in order to ensure the correction of 94% errors, it will be limited to bug fixes, the multiplicity does not exceed k-1;

2) is the parity information bits;

3) of the direct inverse values of the information bits and

values (direct and inverse) discharge parity information matrix is formed:

4) to the obtained information of the matrix are arranged right and left diagonal checks. The number of diagonal checks (number of control bits) is determined by the formula:

5) code set is transmitted in the form:

6) the result of addition of values of the signals transferred and formed the control bits will give the syndrome of the error:

7) when forming the syndrome of the error relative to the received and generated values of the control bits are organized additional diagonal scan, the number of which is determined by the expression:

8) as a result we have a lot of errors of a given multiplicity (in this case from a single to multiplicity k-1, defined by the expression:), characterized by a certain value of the syndrome of the error and additional checks;

9) the set N is divided into four subsets of N=n₁+n₂+n₃+n₄where

n₁- syndromes that have the same additional checks (unrecoverable error);

n₂- a subset of groups (each group consists of 2^k-the same values of the syndromes) in the presence of errors in the information bits;

n₃- a subset of groups (each group consists of 2^k-the same values of the syndromes) if there are errors only in the control bits;

n₄- a subset of groups (each group consists of 2^k-the same values of the syndromes) when errors occur simultaneously in the information and check bits.

Note that for errors not exceeding multiplicity k-1, no erroneous code sets that can be transformed allowed (OK) code sets.

based On the received encoding rules are formed decoding strategy, the crucial task of distinguishing errors in the information and check bits, and rules for the correction of errors, which includes the following items:

1) revealed the same additional checks, which of the set N are excluded syndromes of errors belonging to the subset of n₁observed (uncorrected errors in which a signal is generated "Failure");

2) to define groups of similar syndromes (indicating an error in the corresponding information bits) for a subset of n₂;

3) define groups of syndromes of errors belonging to the subset of n₃that do not require correction of information bits;

4) identify clusters of similar values of the syndromes of errors belonging to the subset of n₄and to correct errors in the corresponding information bits.

For this example, implements the proposed encoding method are:

- total number of error - 15792;

- 960 - number of similar syndromes of errors, with the same additional checks (a subset of n₁);

- 14832 - the number of corrected errors (94%);

- the number of errors in the information bits is 0;

- the number of errors in the check bits - 7312 (l₂=457-groups, each of which includes 16 of the same syndromes);

- the number of errors that have distortion at the same time in the information and check bits - 7520 (l₃=470-groups, each of which includes 16 of the same syndromes).

In table 1 presents the values of the syndromes of error for subsets of n₂n₃n₄(excluded syndromes errors subset of n₁that have the same value additional checks).

Table 1.
Error	INF. bit.	Taken KR	Formed. CU	Syndrome
y1y2y3y4	r1r2r3r4r5r6r7r8r9r10	r1r2r3r4r5r6r7r8r9r10	e1e2e3e4e5e6e7e8e9e10
Only in the control	0101		000000100010	000000000001
0101		000000100010	100000000000
0101		000000100010	110000000000
0101		000000100010	000000000011
0101		000000100010	111000000000
0101		000000100010	000000000111
Only information		000101100111	000000100010	000101000101
	110011010001	000000100010	110011110011
	101000001010	000000100010	101000101000
	001010101000	000000100010	001010001010
	101101001111	000000100010	101101101101
	111001011011	000000100010	111001111001
And control, and information			000000100010	010011110011
		000000100010	110011110010
		000000100010	100101000101
		000000100010	111000101000
		000000100010	011100111100
		000000100010	000101000110

The proposed encoding method allows you to:

to correct the error specified ratio;

to find the maximum number of errors (with the exception of the erroneous code sets that can be transformed enabled code sets);

to signal a malfunction of the memory device when the occurrence of the unrecoverable error.

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 redundant methods Kodirov the deposits. M: Energy, 1974, 270 S.

Failover storage device containing the storage device, encoder, designed to exercise the right and left diagonal checks and forming vector control bits, the syndrome of the error, the decoder, the corrector is designed to correct errors that occur at the outputs of the storage device, the information input device connected to the first inputs of the storage device, 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 the first through fourth groups of elements And the fifth element And element group OR from second to eighth elements OR scheme parity, block inversion, the register, the element does NOT address inputs, 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 storage device and to the first inputs of the register, the input record is connected to the third input of the storage device, to the second inputs of elements And the first group and to the second input register, input reading is connected to the fourth input of the storage device, to the first inputs of elements And the second is the group to the first inputs of elements And the third group to the first input element of the fourth group and to the third input register, input "Reset" is connected to the fifth input of the storage device and to the fourth input of the register, the outputs of the storage device connected to the second inputs of elements And the second group, the outputs are connected to first inputs of the first group 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 the circuit of parity, to the inputs of the block inversion and to the first inputs of encoder, the output circuit of the even parity is connected to the second the input of the coding device, to the second inputs of elements And the third group and to the fifth input of the register, the outputs of the block inversion is connected to a third input of the coding device, the outputs of encoder connected to the third inputs of elements And the third group and to the sixth input of the register, the input circuit of the syndrome of the error connected to the outputs of the elements And the third group, the second inputs connected to the outputs of the register, and outputs connected to the inputs of the decoder and to the inputs of the second element OR the output of which is connected to the first input of the fifth element And the first group of outputs of the decoder are connected to the inputs of the third element OR the second group the outputs of the decoder are connected to the inputs Thursday is REGO element OR the third group of outputs of the decoder are connected to the inputs of the fifth element OR the fourth group of outputs of the decoder are connected to the inputs of the sixth element OR group of outputs of the decoder are connected to the inputs of the seventh element, OR the outputs from the third and sixth elements OR connected to the second inputs of the elements of the fourth group and first to fourth inputs of the eighth element OR the output of the seventh element OR is connected to the fifth input of the eighth element OR the output of which through the element is NOT connected to the second input of the fifth element And the output of the fifth element And is output "Failure", the outputs of the elements And the fourth group is connected to the second inputs of the offset.