Self-correcting device

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

SUBSTANCE: device contains original circuit, four groups of AND elements, group of OR elements, encoding device, register, error syndrome circuit, checks circuit, three decoders, 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 funktsioniruyuschaya, 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 the maximum number of errors.

This objective is achieved in that the device contains the original scheme, the encoder, the scheme of the 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 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", and 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 the first input is the fourth element And to the third input register, 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 of encoder connected to the 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 schema 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 includes: 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, case 8, a diagram of the syndrome error 9, the circuit checks 10, the first decoder 11, the second decoder 12, the third dash is Prator 13, the corrector 14, the information input 15 address inputs 16, entry 17 entries, entry 18 reading input 19 reset, the outputs 20 of the device.

An information input device 15 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 14, the outputs of the corrector 14 are outputs 20 device address inputs 16 is connected to the second input source circuit 1 and to the first inputs of the register 8, entry 17 records connected to the third input of the source schema to the second input of the first element 2 And to the second input of the register 8, the input 18 connected to read 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 of the register 8, entry 19 "Reset" is connected to the fifth input source circuit 1 and to the fourth input of the register 8, 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 second inputs of the third element 4 And and fifth inputs of the register 8, the input circuit 9 of the syndrome of the error connected to the outputs of the third element 4 And the which inputs connected to the outputs of the register 8, 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 14.

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=r1,r2,...r2l;

2) formation of a (similarly) vector control bits RPadopted 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 the coding device 7, are respectively the vectors of control bits:

R=r1r2...,r2l,

RP=rP1rP2...rP2l.

Scheme 9 error syndrome is a bitwise comparison and is designed to generate values of the syndrome of the error on the basis of p is expressed and received.

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

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 additional checks generates the control signal corrector 14 to correct erroneous information bits.

The corrector 14 is designed to repair errorsappearing at the outputs of the original circuit 1, and implements a function relative to the control signals ui outputs of decoder:

The device operates as follows. Before working on the entrance 19 signal that sets the device to its original state. When the input information to the information input 15 address inputs 16 and signal "Write" to the input 17, in which armacia 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 17, 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.

With outputs of encoder 7, and the vector of control bits to the input of the register 8 and is written to the specified address.

When reading data at the specified address, the output signal of the source schema 1, through the second element 3 And is opened by the signal "Read" input 18, item 6, OR re-fed to the input of the coding device 7, where the values of the signals in the control bits of the diagonal checks the received information.

In this case, the outputs of the coding device 7 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 8.

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 by the rule (11)described in the application.

The first decoder 11, when an error generates nomnom 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 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-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=h1h2,...hmthe vector of parity rows; Z=z1,z2,...zbthe vector of parity columns. Vector parity rows and columns form a set of control bits R1={r1 2,rm,rm+1,...,rb}. When receiving a code combination regarding information bits of the re-formed values of the control bits RP1={r1,r2,rm,rm+1,...,rb}. 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:

In this case, the bits of the syndrome of the error e1e2...em(received regarding the vector of parity lines) indicate the module information having an error, and the digits of emem+1...eb(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 of x simultaneously different code words. The parameters of iterative codes dimension of x as follows [3]:

where ni, kidirespectively 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 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 a zero value 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 parity 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 check, and parity check rows and columns. Structure of the considered errors are presented in figure 4.

Fig.4 Structure errors, n is detectable 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 all possible errors.

Corollary 1. For the information of 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 r1,r2......rl- match the right diagonal checks; rl,rl+1......r2lleft.

Clearstream 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).

On the basis of the received encoding rules formed the decoding strategy, which solves the problem of distinguishing errors in 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:

Table 1.
№ p/py1y2y3y4e1E2E3E4E5E6
00000000000
11100110011
200 11011110
31111101101
41010110110
50101011011
61001101000
70110000101
81110100111
91101111001
1011111100
110111001111
121000100010
130100010001
14000010100
150001001010

For this example, table 2 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 allow you to plug the em to formulate the following statement:

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

In this case, to save hardware costs, it 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 the proposed encoding method allows 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, 197, 270 C.

A self-correcting device containing the encoder, designed to exercise the right and left diagonal checks and forming vector 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 the first through the fourth group elements And group elements OR the register, the circuit checks the second decoder, the third decoder, the address inputs, the input recording the entrance reading the 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 to 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, United to the first input element of the fourth group and to require the input Lemo register 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 elements And the second group, the outputs are connected to first inputs of a group of elements OR, the second inputs of which are connected to the outputs of the first group of elements And outputs connected to the inputs of encoder outputs of encoder 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 third group of elements, And 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 elements of the fourth group, the outputs of which are connected to second inputs of the offset.



 

Same patents:

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

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

EFFECT: increased trustworthiness of device operation.

1 dwg, 1 app

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

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

EFFECT: increased trustworthiness of device operation.

1 dwg, 1 app

FIELD: information-carrying mediums.

SUBSTANCE: information about record/playback in real-time, ensuring record/playback in real-time, is stored in file control information area, in every real-time file, or in a separate file; file is given attributes of record/playback in real-time.

EFFECT: files, recorded in real-time, can be played back without interruptions.

34 cl, 14 dwg

FIELD: computer science.

SUBSTANCE: device has storage, data control block, decoders groups, commutator, encoders group. Method describes operation of said device.

EFFECT: higher trustworthiness, higher efficiency.

2 cl, 1 dwg

The invention relates to electronic storage devices (memory) with electrically programmable cells

The invention relates to the field of automation and computing

The invention relates to a means for programming/erasing an electrically erasable programmable semiconductor permanent storage devices

The invention relates to test devices electronic elementary and group lines connections

The invention relates to a method of recording in non-volatile memory and can be used in the devices performing the storing and updating of operational information in the course of their work

Testing memory // 2155996

The invention relates to a semiconductor storage device that contains the schema detecting and correcting multiple errors

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

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

EFFECT: increased trustworthiness of device operation.

1 dwg, 1 app

FIELD: engineering of printers and memory devices for printers.

SUBSTANCE: in accordance to suggested method for detecting error in data, received from memory device of replaceable printer component, ensured is first evenness control bit, associated with first data element. First data element and first evenness control bit are stored in memorizing device. Printer includes a set of electro-conductive lines. Memorizing device includes a set of bits. At least one of electro-conductive lines is associated with each bit. First data element and first evenness control bit are read from memorizing device. Electric test of at least one of electro-conductive lines is performed. Error is identified in first data element on basis of first evenness control bit, read from memorizing device, and electric test. Other inventions of group envelop printing system, two variants of realization of replaceable printer component for printing system and method for storing information in replaceable printer component are provided.

EFFECT: creation of memory device with increased reliability, timely detection and correction of errors in replaceable components of printers ensures their continuous operation.

5 cl, 7 dwg

FIELD: automatics and computer science, possible use for controlling and correcting errors during relaying of information, and also for performing arithmetical operations by computer.

SUBSTANCE: device has two blocks for calculating error syndrome on basis of control bases, made on two-layer neuron network, register, memory block, output adder, and also due to application of polynomial residuals system, in which as system base, minimal polynomials are used, determined in extended Galois fields GF(2ν) and in terms of neuron network technologies.

EFFECT: decreased dimensions of equipment, higher speed of detection and correction of errors.

3 dwg, 2 tbl

FIELD: computer science.

SUBSTANCE: network has end ring neuron network, Hopfield neuron network, demultiplexer and multiplexer.

EFFECT: broader functional capabilities, higher efficiency, higher speed of operation.

1 dwg

The invention relates to the field of automation and computer engineering and can be used in computational structures to control the accuracy of arithmetic operations

Device for backup // 2123202
The invention relates to the field of automation and computer engineering and can be used in computing machines and devices operating in the system of residual classes

The invention relates to computer technology and is intended for use in digital computing devices

The invention relates to computer technology and is intended for use in digital computing device to form the final fields

The invention relates to computing and can be used to build devices for control in module three

FIELD: computer science.

SUBSTANCE: network has end ring neuron network, Hopfield neuron network, demultiplexer and multiplexer.

EFFECT: broader functional capabilities, higher efficiency, higher speed of operation.

1 dwg

Up!