Device for detecting and correcting errors in polynomial residual-class system

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

 

The device relates to the field of automation and computer engineering and can be used for monitoring and correcting errors in the transmission of information, and by carrying out arithmetic operations in the computer.

A device for detecting and correcting errors in the system of residual classes (A.S. No. 714399, CL G 06 F 11/08, 1980)containing the register, whose input is connected to the input device, two modular block convolution, three of the adder, and the output of the third adder being the output device, the memory block.

A disadvantage of the known device is its complexity and poor performance, due to the large amount of equipment.

The main objective is the reduction of the equipment and increase the speed of bug fixes.

The technical result achieved in the implementation of the claimed invention is to increase the speed of detection and correction of errors and reduction of equipment.

This technical result is achieved due to the fact that the claimed device comprises two blocks calculate the syndrome of the error on the test grounds, and these blocks are made on a two-layer neural network, and the first output register is connected to the first outputs of blocks calculate the syndrome of the error, the second and third output register connected, respectively, in the which the outputs of the first and second blocks calculate the syndrome of the error, the outputs are connected to inputs of the memory block; and through the use of a polynomial system of deductions (PSCW), in which as the Foundation of the system is minimal polynomials pi(z), i=1,2,...,n, defined in the extended Galois fields GF(2ν) and neural network technology.

Functional diagram of the device represented in figure 1. It includes: register, input 2, the first computing unit syndrome error 3, the second computing unit syndrome error 4, the memory unit 5, an adder 6, 7.

The device operates as follows.

On the input 2 of the device is controlled by the number represented in polynomial form:

where αi(z) is the remainder of A(z) modulo Pi(z); Pi(z),..., Pn(z) - operating bases; Pn+1(z), Pn+2(z) - control of the base.

This vector A(z)=(α1(z), α2(z),..., αn(z), αn+1(z), αn+2(z) is written into register 1. The input of the first unit for computing the syndrome of the error 3 with output register 1 is:

With education at its signal output:

When you do this:

α*n+1(z)=λ(1)1α1(z)+λ(1)2α2(z)+...+λ(1)nαn (z),

where λ(1)1- constants of the system.

The inputs of the second unit for computing the syndrome of the error 4 output register 1 is:

With the formation of the output signal:

When you do this:

α*2(z)=λ(2)1α1(z)+λ(2)2α2(z)+...+λ(2)nαn(z),

where λ(2)1- constants of the system.

Values δ1(z) and δ2(z) in binary form are received at the inputs of the memory block 5 and pick out the appropriate constant errors. This constant error is supplied to the adder 6, which is summed up with A distorted(z)outside the positional form of the register 1 is fixed representation of a(z) from the output of the adder 6 is supplied to the output 7 of the device.

As an example, consider the extended Galois field GF(24), which outlines the following reasons:

P1(z)=z+1

P2(z)=z2+z+1

P3(z)=z4+z3+z2+z+1,

where P1(z), P2(z) and R3(z) - working Foundation,

P4(z)=z4+z3+1

P5(z)=z4+z+1,

and P4(z) and P5(z) - control of the base.

Have:

B1(z)=z14+z13+z12+z11+z10+z9+z8+z7+z 6+z5+z4+z3+z2+z+1,

B2(z)=z14+z13+z11+z10+z8+z7+z5+z4+z2+z

B3(z)=z14+z13+z12+z11+z9+z8+z7+z6+z4+z3+z2+z

B4(z)=z14+z13+z12+z11+z9+z7+z6+z3,

B5(z)=z12+z9+z8+z6+z4+z3+z2+z

Bslave(z)=z7+z6+z5+z2+z+1,

Then,

B1(z)=(z7+z4+z2+z) Pslave(z)+z6+z4+z3+z2+1,

B2(z)=(z7+z5+z2+z+1) Pslave(z)+z6+z5+z+1,

B3(z)=(z7+z4+z3+z+1) Pslave(z)+z5+z4+z3+z2+z+1,

B4(z)=(z7+z4+z3) Pslave(z),

B4(z)=(z5+z4+z) Pslave(z).

If the polynomial A(z) Pslavethen true:

1(z), α2(z), α3(z))=(α1(z), α2(z), α3(z), α4(z), α5(z)),

where the left part of the equality represented on the working grounds P1(z), P2(z), R3(z), and the right - polynomial system bases P1(z), P2(z), R3(z), P4(z), P5(z) extended Galois fields GF(24).

Then according to Chinese theorem about who headed the remainder of the

Therefore,

and

where B*i(z) - orthogonal bases without excessive system class deductions on the grounds P1(z), R2(z), R3(z).

Proceeding from the condition that α1(z) is represented as a binary position code, the expression (7) and (8) can be represented in the form:

and

where αki- values of k-th bit of the i-th residue; k=0, 1, ord pi(z)-1; ord Ri(z) is the degree of the i-th base in PCCW.

The values of the constantsandpresented in table 1.

Table 1
Values αki(z)Foundation
P4(z)=z4+z3+1P5(z)=z4+z+1
α01(z)z3+z+1z
α02(z)z2+z+1z3+1
α12(z)z3+zz2+z+1
α0Ȋ 3(z)z3+z2+1z3+z
α13(z)z+1z2+z+1
α23(z)zz3
α33(z)z2z+1

Then the difference between the calculated values α*4(z) and α*5(z), according to (2), and the remnants of the polynomial A(z)belonging α4(z) and α3(z) on the test grounds P4(z) and P5(z) form the syndrome of the error.

δ1(z)≡α4(z)-a*4(z)mod P4(z)

δ2(z)≡α5(z)-a*5(z)mod P5(z)

Thus, the first computing unit error syndrome implements procedure

A second unit for computing the syndrome of the error implements procedure

If δ1(z)=0 and δ2(z)=0, then no positional representation of the polynomial A(z) does not contain errors. Otherwise, the values δ1(z) and δ2(z) is determined by the location and depth errors. Given a polynomial A(z)=(1, z+1, z3+z2+z+1, z3+z2+1, z3+z). Dene the convolution:

α*  4(z)=z3+z2+1

α*5(z)=z3+z

Define the syndrome of the error:

δ1(z)≡((z3+z2+1)+(z3+z2+1))mod P4(z)=0

δ2(z)≡((z3+z)+(z3+z))mod P5(z)=0

Therefore, the original combination (1, z+1, z3+z2+z+1, z3+z2+1, z3+z) does not contain errors. The memory block will contain the following constants errors:

Table 2
BaseErrorδ1(z)δ2(z)
P1(z)=z+11z3+z+1z
P2(z)=z2+z+11z2+z+1z3+1
zz3+zz2+z+1
P3(z)=z4+z3+z2+z+11z3+z2+1z3+z
zz+1z2+z+1
z2Zz3
z3z2z+1

Let the input 2 of the device is controlled value:

A(z)=(1, z+1, z2+z+1, z3+z 2+1, z3+z)

Then, according to expressions (9) and (10) we obtain:

α*4(z)=z2+1

α*5(z)=z3

Defined the syndrome of the error:

δ1(z)≡(z3+z2+z+z2+1)mod(z4+z3+1)=z3+z+1

δ2(z)≡(z3+z+z3)mod(z4+z+1)=z

From the memory unit 5 in accordance with the δ1=z3+z+1 and δ2=z is selected the value of (1, 0, 0), which is controlled by the number in the adder 6 in the output:

(1, z+1, z2+z+1, z3+z2+z, z3+z)+(1,0,0,0,0)=(0, z+1, z2+z+1, z3+z2+z, z3+z).

Note that if A(z) will not contain errors, then the value of syndrome δ1and δ2is equal to zero. The use in the present invention the two blocks 3 and 4 compute the syndrome of the error allows us to simplify the device, since the data blocks function block convolution modular modular adder for each of the control base. In addition, the use of a two-layer network and the combination calculation procedures α*4(z)(α*4(z)) and δ1(z)(δ2(z)) can increase performance of the device.

The unit for computing the syndrome of the error modulo P4(z)=z4+z3+1 is presented in figure 2. It is particularly the two-layer neural network.

The first layer contains 11 neurons. The inputs of the neurons 8, 9-10, 11-14 in binary form are placed the remains of α1(z), α2(z), α3(z) on the working grounds P1(z), P2(z), R3(z). On neurons 15-18 supplied binary code α4(2) modulo P4(z)=z4+z3+1.

The second layer of the neural network contains 4 neuron performs a basic operation of summing modulo 2, and the first neuron 2 layer 23 is connected to the outputs 8, 9, 11, 12, and 15 neurons in layer 1. Neuron 2 layer 24 is connected to the outputs 8, 9, 10, 12, 13, and 16 neurons in layer 1, neuron 2 layer 25 is connected to the outputs 9, 11, 14 and 17 neurons in layer 1 and neuron 2 layer 26 is connected to the outputs of 8, 10, 11, and 18 neurons in layer 1.

The unit for computing the syndrome of the error modulo P5(z)=z4+z+1 is presented in figure 3. He is a two-layer neural network.

The first layer contains 11 neurons. The inputs of the neurons 8, 9-10, 11-14 in binary form are placed the remains of α1(z), α2(z), α3(z) on the working grounds P1(z), P2(z), R3(z). On neurons 19-22 supplied binary code α5(z) modulo P4(z)=z4+z+1.

The second layer of the neural network contains 4 neuron performs a basic operation of summing modulo 2, and the first neuron 2 layer 27 is connected to the outputs 9, 10, 12, 14 and 19 of neurons in layer 1. Neuron 2 layer 28 is connected to the outputs of 8, 10, 11, 12, 14, and 20 are not what 1 layer of neurons, neuron 2 layer 29 is connected to the outputs 10, 12 and 21 neurons in layer 1 and neuron 2 layer 30 is connected to the outputs 9, 11, 13, and 22 of neurons in layer 1.

Device for detecting and correcting errors in polynomial system of the residue class containing the register, whose input is an input device, a memory unit and an output of the adder, the first, second and third inputs of which are connected respectively with the first, second and third outputs of the register, and the fourth input is connected to the output of the memory block, characterized in that it contains two blocks calculate the syndrome of the error on the test grounds, and the first output register is connected with the first inputs of blocks calculate the syndrome of the error, and the second and third outputs of the register are connected respectively to the second outputs of the first and second blocks calculate the syndrome of the error, the outputs are connected to inputs of the memory block, the first block calculate the syndrome of the error made on a two-layer neural network and contains in the first layer 11 of neurons to the inputs of which are served in binary form the remains of three workers and one of the controlling reasons, the second layer of the neural network contains 4 neuron that performs the basic operation of summing modulo 2, the inputs of the first neuron of the second layer are connected to the outputs 1, 2, 4, 5, and 8 neurons in the first layer, the inputs of the second neuron of the second layer with dynany 1, 2, 3, 5, 6, and 9 neurons in the first layer, the inputs of the third neuron of the second layer are connected to the outputs of 2, 4, 7 and 10 neurons in the first layer, the fourth inputs of the neuron of the second layer are connected to the outputs 1, 3, 4 and 11 neurons in the first layer, the outputs of the neurons of the second layer are the outputs of the first adder, a second unit for computing the syndrome of the error made on a two-layer neural network and contains in the first layer 11 of neurons to the inputs of which are served in binary form rests on three work and the second control reasons, the second layer of the neural network contains 4 neuron that performs the basic operation of summing modulo 2, the inputs of the first neuron of the second layer are connected to outputs 2, 3, 5, 7 and 8 neurons in the first layer, the inputs of the second neuron of the second layer are connected to the outputs 1, 3, 4, 5, 7 and 9 neurons in the first layer, the inputs of the third neuron of the second layer are connected to the outputs 3, 5 and 10 neurons in the first layer, the fourth inputs of the neuron of the second layer are connected to the outputs of 2, 4, 6 and 11 neurons in the first layer, the outputs of the neurons of the second layer are the outputs of the second computing unit syndrome errors.



 

Same patents:

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

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: 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: 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, 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

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, decoder, inversion block, even parity check circuit, corrector.

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, four groups of AND elements, AND element, group of OR elements, seven OR elements, encoding device, register, error syndrome circuit, NOT element, decoder, even parity check circuit, corrector.

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 memorizing device, four groups of AND elements, AND element, group of OR elements, seven OR elements, encoding device, register, error syndrome circuit, inversion block, decoder, corrector.

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, four groups of AND elements, AND element, group of OR elements, seven OR elements, encoding device, register, error syndrome circuit, NOT element, decoder, corrector.

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 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

Up!