RU2834287C1 - Method of monitoring and restoring data integrity based on two-dimensional code structures in complex domain - Google Patents

Abstract

FIELD: physics.

SUBSTANCE: invention relates to information storage systems. Method of monitoring and restoring data integrity based on two-dimensional code structures in a complex region is provided by constructing protected multi-valued code structures based on structural-algebraic transformations and a subsequent expansion operation. Structural-algebraic transformations make it possible to reduce the sequence of data subunits to the form of a sequence of complex numbers, and the expansion operation to calculate redundant elements. Conversion of the sequence of data units to the form of complex numbers enables to build a data storage subsystem, in which the imaginary part of the complex number acts as the header of the array of stored data, its filling is carried out with values of real part of complex number due to correlation of header of data array with imaginary part of received complex number, at coincidence of which value of its real part is recorded in next memory cell.

EFFECT: high efficiency of the data storage system by reducing the level of stored redundant information required for monitoring and restoring integrity of information.

1 cl, 5 dwg

Description

Field of technology to which the invention relates

The proposed invention relates to the field of radio and telecommunications, namely to the field of data storage methods and systems.

a) Description of analogues

There are known methods of storing information, the integrity of which is ensured (protected against loss) by means of data backup using hardware, software or software implementation, for example, RAID (Redundant Array of Independent Disks) technology [US Patent No. 7,392,458 published 06/24/2008; US Patent No. 7,437,658 published 10/14/2008; US Patent No. 7,600,176 published 10/06/2009; US Patent Application No. 20090132851 published 05/21/2009; US Patent Application No. 20100229033 published 09/09/2010; US patent application No. 201101145677 publ. 06/16/2011; US patent application No. 20110167294 publ. 07/07/2011].

The disadvantage of these methods is the rather complicated procedure for recovering lost data.

A method is known [Patent of the Russian Federation No. 2502124 C1 published 20.12.2013] for distributed storage of information, in which ensuring integrity is based on backup methods, when a storage device (storage) is built on the basis of several storage nodes (hard drives, flash drives, etc.), which is resistant to data loss even if a certain number of media that form the storage device (storage) fail.

The disadvantages of this method are:

- a fixed level of recoverable data in the event of a single failure or malfunction;

- high level of redundancy of stored information.

b) Description of the closest analogue (prototype)

The method described in [Patent of the Russian Federation No. 2785862 published on 14.12.2022] is closest in its technical essence to the declared technical solution and is accepted as a prototype.

The prototype method under consideration provides the ability to detect and localize two or more sub-blocks of a data block with signs of integrity violation without calculating and introducing high redundancy of control information for this purpose.

The disadvantages of the known method are:

- the complexity of implementing algebraic transformations associated with the calculation of redundant data subblocks;

- the need to store all the information required to implement the procedures for detecting and localizing sub-blocks of a data block with signs of integrity violation.

Disclosure of invention

a) The technical result that the invention is aimed at achieving

The purpose of the claimed technical solution is to increase the efficiency of the data storage system based on control and restoration of the integrity of information.

b) A set of essential features

The stated goal is achieved by the fact that in the known method of monitoring the integrity of multidimensional data arrays based on the rules for constructing the Reed-Solomon code, which consists in the fact that the data block M of the multidimensional data array, presented in the form of a vector, is fragmented into data subblocks to monitor the integrity of the data contained in it of fixed length m, according to which the extended binary Galois field is chosen each non-zero element of which is represented as a power of α, and the infinite set of its elements is formed from the initial set {0,1, α} by successively multiplying the elements by a, after which the generating polynomial d(x) of the corresponding Reed-Solomon code is specified, and the original data block M is written using primitive elements, to obtain the required dimension of which, depending on the information length the selected Reed-Solomon code is supplemented if necessary zero subblocks, where t is equal to the number of detected or localized data subblocks with signs of integrity violation, the resulting extended data block M' contains subblocks which are represented by elements as a result of coding of which the code polynomial c(x) is formed, the error polynomial c(x) is determined, the values are calculated hash functions and syndromes S _ω at points α ^ω , where the verification of which allows us to determine the signs characterizing the violation of the integrity of the subblocks. data block M of the multidimensional array to be protected. What is new is that the data subblocks of the data block M in the complexification block, a structural-algebraic transformation procedure is applied, which allows, on the basis of the introduced complex module, obtained by forming mutually prime numbers (p,q) by the first and second generators, perform the procedure of one-to-one transformation of data subblocks data block M to a protected representation in the form of complex numbers and the implementation of the expansion operation, allowing for a protected data subblock calculate the reference value with subsequent formation in the buffer of two-dimensional code structures of the form in which the actual and imaginary parts are sent to the data analysis unit. What is also new is that the data analysis unit sends the values of the imaginary and real parts of the obtained complex numbers for storage in the data storage subsystem in the memory cells of the first and second data storage subblocks, respectively. What is new is that the memory cells of the first data storage subblock contain the headers of the array of stored data, which are assigned the values of the imaginary parts of the complex numbers {b ₁ i, b2i, …, b _ki }, the real part {α ₁ , α ₂ , …, α _k } of which is written to the corresponding cells of the imaginary parts of the complex numbers of the second storage subblock. What is new is that the subsequent filling of the memory cells of the first and second data storage subblocks is carried out by the data analysis block by correlating the value of the header of the array of stored data with the imaginary part of the complex number received for storage, when they coincide, the real part of the received complex number is written to the next free memory cell of the data array of the second subblock for storing the real part of the complex number. What is new is that the set of values of the headers of the data array and the corresponding values of the real numbers

stored complex numbers are used by the control and distortion correction units to control and restore the integrity of the data, followed by the execution of the inverse transformation procedure by the objectification unit from the protected representation in the form of complex numbers to the open view of data subblocks M data block.

c) Cause-and-effect relationship between features and technical result Thanks to the new set of essential features, the following capabilities are realized in the method:

- ensuring control and restoration of data integrity in the data storage system;

- reducing the level of input redundant information required to control and restore data integrity.

- maintaining the integrity of stored information at a level that allows achieving the goal of operating the storage system with suitable quality.

Evidence of compliance of the claimed invention with the patentability conditions of “novelty” and “inventive step”

The conducted analysis of the state of the art made it possible to establish that there are no analogues characterizing the sets of features identical to all the features of the declared technical solution, which indicates that the declared method complies with the patentability condition of “novelty”.

The results of the search for known solutions in this and related fields of technology in order to identify features that coincide with the distinctive features of the claimed object from the prototype showed that they do not follow explicitly from the state of the art. The state of the art also does not reveal the familiarity of distinctive essential features that determine the same technical result that is achieved in the claimed method. Consequently, the claimed invention corresponds to the patentability level of "inventive step".

Brief description of the drawings

The claimed method is illustrated by drawings showing:

- Fig. 1 - structure (components) of the data storage system;

- Fig. 2 - generalized magic square. General view of the generalized magic square;

- Fig. 3 - subblock coding rule data block M;

- Fig. 4 - generalized magic square containing complex numbers;

- Fig. 5 - a diagram explaining the process of filling the memory cells of the first and second data storage subblocks.

Implementation of the invention

The structure of the data storage system implementing control and restoration of data integrity based on two-dimensional code structures in a complex area within the framework of the method under consideration is presented in Figure 1.

A data storage system implementing control and restoration of data integrity based on two-dimensional code structures in a complex domain includes: a mutually prime number generator 10.1, a mutually prime number generator 10.2, a complexification unit 11, a complex number expansion unit 12, a buffer 13, a data analysis unit 14, a first data storage sub-unit 15.1, a second data storage sub-unit 15.2, a distortion control checking unit 16, a distortion correction unit 17, a reification unit 18, and a data output unit 19.

In one embodiment, the claimed method for monitoring and restoring the integrity of data based on two-dimensional code structures in a complex domain can be implemented using provisions that determine the order of constructing generalized magic squares and the fundamental theorem of Gauss.

It is known that the property of error control and correction also applies to magic squares. This property consists in the fact that on a certain set of arbitrarily selected numbers, using the principles of constructing magic squares, some additional conditions can be imposed by introducing excess numbers [S.I. Samoylenko. Noise-Immune Coding, Moscow, "Nauka", 1966, 238 p.].

The construction of generalized magic squares of order k is carried out as follows. k arbitrary numbers are selected and are written in any order, for example, in the order of increasing indices in the first row of the square (Figure 2). Then, some permutations of these numbers are written in all the remaining rows, in which no number remains in the same place. When placing such permutations in rows, it is necessary to ensure that there are no repeating numbers on both diagonals. As a result, we obtain the structure of a generalized magic square with k arbitrarily chosen numbers, in which the operation on k numbers located along the rows, columns and diagonals gives the same results. Such a square is designated by a pair of numbers that determine the total number of numbers written in the square and the number of arbitrarily chosen numbers: (k ² , k). We will assume that the columns are numbered from left to right, and the rows from bottom to top. In this case, each number in a square of order k (figure 2) occurs exactly k times, located in cells with different coordinates. Each sample (a set of k numbers, operations on which give the same results) involves k numbers, each of which can be selected from one of the k cells in which the same numbers are located. Consequently, the total number of possible samples in a given square is equal to

The increase in the number of randomly selected elements can be achieved by introducing additional randomly selected elements and replacing some of the elements of the original square with the result of the selected operation on the initial element and a new, randomly selected one. The result of the adopted operation is the introduction of a new randomly selected member and its replacement in some cells of the original elements M _i with During the replacement process, it is necessary to preserve the conditions of the square's magic. The maximum number of additional randomly selected elements is limited by the requirement that the resulting new square contain all the original elements. in its original form [S.I. Samoylenko. Noise-resistant coding, Moscow, "Nauka", 1966. 238 p.]

The second stage of mathematical transformations of the invention is based on the fundamental theorem of Gauss [I. Ya. Akushsky, D-I. Yuditsky. Machine arithmetic in residual classes. Moscow, “Soviet Radio”, 1968. 440 p.; V. M. Amerbaev, I. T. Pak. Parallel computing in the complex plane. Alma-Ata: “Nauka” Publishing House. 1984. 183 p.; V. G. Labunets. Algebraic theory of signals and systems (digital signal processing). Krasnoyarsk: Publishing house of Krasnoyarsk University, 1984. 244 p.].

Gauss's theorem. Given a complex modulus whose norm is K = p ² + q ² and for which p and q are relatively prime numbers, each complex number is congruent to one and only one residue from the series

Proof From number theory it is known that for two relatively prime numbers p and q one can find two integers u and υ such that

Let's form an identity

and let a complex number α+bi be given, which we rewrite by replacing i from (2)

Let h denote the smallest positive real residue of a number modulo K and assume that

Then the equality will be satisfied

or in comparative form

Thus, it has been proven that α+bi is comparable to one of the numbers 0.1, 2.3, ..., K-1 modulo . Moreover, this number is unique. Let us assume that two comparisons take place

By the property of congruences, the numbers h ₁ and h ₂ are comparable in absolute value. , i.e.

or

From (4) it follows that the equality is satisfied

equivalent to two real equalities:

Multiplying the first equality (5) by u and the second by υ and adding them together, we obtain

from which, taking into account (1), it follows

or

Since by assumption then (7) is possible only in the case h ₁ =h ₂ .

Thus, the existence of two numbers h ₁ and h ₂ , less than K, which would be comparable to α+bi in absolute value is excluded. and there is only one such number, which is determined from the comparison

or

The given theorem establishes an isomorphism between complex numbers and their real residues.

The user-generated data block M of the data array is fragmented into data subblocks and enters the data storage system. In order to ensure a suitable level of security for the stored information, data subblocks are subject to the procedure of structural-algebraic transformation, for which the generated sequence of data subblocks enters the complexification block 11, where the data subblock is transformed into a complex number according to the expression:

where (p, q) are mutually prime numbers generated by generators 10 1 and 10.2 of mutually prime numbers and fed to the complexification block 11 to form a complex module and calculations of the norm K. In this case, the elements of the complex module mutually prime numbers (p, q) are kept secret.

Then the resulting set of complex numbers enters the block 12 for expanding complex numbers, which also receives the values of mutually prime numbers (p,q), generated by generators 10.1 and 10.2 of mutually prime numbers. In the block 12 for expanding, the coding procedure is performed taking into account the rules for constructing generalized magic squares, which consists of calculating I - randomly selected elements from the obtained set of complex numbers Mutually prime numbers (p, q) are required to calculate the norm K, for the case when the coding process is implemented using the operation "addition by modulo". Then the ordered sequence of complex numbers or a sequence of complex numbers constructed in the order of increasing coordinates of the square cells is transferred to buffer 13. Here - verification elements. From buffer 13 for further processing, a protected multi-valued code structure, transformed to the form is fed to the input of data analysis block 14, which determines and directs:

- values of imaginary parts complex numbers in the first subblock

15.1. In the first subblock 15.1, the headers of the array of stored data are assigned the values of the imaginary parts of complex numbers.

- values of real parts complex numbers in the second subblock 15.2. In the second subblock 15.2 the real part complex numbers are written into the corresponding memory cells of the second storage subblock, corresponding to the memory cells of the first subblock 15.1 with the imaginary part of the complex number.

Subsequent filling of the memory cells is carried out by the data analysis unit 14 by correlating the header of the array of stored data with the imaginary part of the complex number received for storage, when they coincide, the real part of the received complex number is recorded in the next free memory cell of the data array of the second sub-unit 15.2 for storing the real part of the complex number. The set of values of the headers of the data array and the corresponding values of the real numbers stored complex numbers are used by the distortion checking and correction units to control and restore data integrity.

The search and localization of distortions is carried out by the block 16 of distortion verification, which consists of sequential calculation of the results of transformations over elements included in various admissible samples and comparing the obtained results with the reference, the symbol "*" indicates the presence of possible distortions caused by destructive effects. In the simplest case, the number of samples used may include only rows and columns of a square. After detecting and localizing distortions in a sequence of complex numbers In the block 18 of distortion correction its correction is carried out, for example, the simplified method of error correction includes the following stages. A sample is found, which contains a single distorted element. This element is corrected and substituted into other samples, containing unknown elements, then the search for a sample with one unknown element is carried out again. The procedure is repeated in a similar way until either all distorted elements are not determined, or it turns out that there are no samples with one unknown. Otherwise, it is worth resorting to more complex algorithms of error correction [S.I. Samoylenko. Noise-proof coding, Moscow, "Nauka", 1966 238 p.]. In this case, the values of mutually prime numbers (p, q), generated by generators 10.1 and 10.2 of mutually prime numbers, required for calculating the norm K, for the case when the coding process is implemented using the operation "addition modulo" enter the block 16 of distortion checking and the block 17 of distortion correction.

Corrected sequence of complex numbers enters the objectification block 18, in which the subsequent calculation of the data subblocks is carried out according to the expression

Where complex modulus obtained on the basis of mutually prime numbers (p, q) generated by generators 10.1 and 10.2 of mutually prime numbers; here the symbols "**" indicate the probabilistic nature of the recovery.

Computed data subblocks data blocks M are sent to data output block 20.

Example. Let us assume that the data subblocks have the following values: M ₁ = 7; M ₂ = 12; M ₃ = 49; M ₄ = 35; M ₅ = 9; M ₆ = 3; M ₇ = 5. Let the generators 10.1 and 10.2 of mutually prime numbers produce the numbers 5 and 6, which are fed to the complexification block 11 to form the complex modulus m - 5+6i and its norm K = 61.

In block 11 of complexification, in accordance with expression (8), the procedure of structural-algebraic transformation is performed and the data subblocks are converted to the form of complex numbers

Then the resulting set of complex numbers enters the block 12 for expanding complex numbers, which also receives the values of mutually prime numbers (5, 6), generated by the generators 10 1 and 10.2 of mutually prime numbers. In the block 12 for expanding, the coding procedure is performed based on the magic square shown in Figure 3. The coding process consists of calculating the sums of pairs of these numbers by the complex modulus , used to construct a square: mod mod mod

The checksum for all samples is 3+6i. Then the generalized magic square will have the form shown in Figure 4

Then the sequence of complex numbers, constructed in the order of increasing coordinates of the square cells through the buffer 13 to the form <-4, 6i>; <-1, 7i>; <1,5i>; <0,4i>; <0,10i>; <0,10i>; <-1,2i>; <2,6i>; <1,2i>; <-1,i>; <-2,9i>; <4,5i>; <-1,4i>; <-2,4i>; <-2,6i>; <1,8i>, where the imaginary part is directed to the first subblock 15.1 for storing data and the real part to the second subblock 15 2 for storing data. The result of filling the memory cells of subblocks 15.1 and 15.2 is shown in Figure 5.

Let us assume that during data storage, a distortion occurred in the memory cell of the second storage subblock 15.2 and the value 2 was transformed into the value 4. When the user requests the original data block M of the data array from storage subblocks 15.1 and

15.2 the values of the imaginary and real parts of the sequence of complex numbers are sent to the distortion checking block 16, in which the search and localization of possible distortions is carried out by calculating the checksum and comparing it with that calculated in the complex number expansion block 12.

1. The result of summing the values of complex numbers mod (5+6i) corresponding to the rows of the generalized magic square (Figure 4):

2. The result of summing the values of complex numbers mod (5+6i), corresponding to the columns of the generalized magic square (Figure 4):

3. The result of summing the values of complex numbers mod (5+6i) corresponding to the diagonal of the generalized magic square (Figure 4):

Thus, block 16 has searched for and localized the erroneous complex number 4*+6o. Now the value 4*+6i must be corrected in the distortion correction block 17, for example,

Let's run a check

Next, the procedure for forming information elements of multi-valued code structures is performed.

to perform procedures for the inverse transformation of a sequence of blocks of complex numbers into a sequence of blocks of plaintext in the objectification block 18. The resulting data subblocks

through the data output block 19, the data is sent to the user.

The given example showed that the claimed method of monitoring and restoring data integrity functions correctly, is technically feasible and allows solving the task.

Claims (3)

A method for monitoring and restoring the integrity of data based on two-dimensional code structures in a complex domain, which consists in the fact that a data block M of a multidimensional data array, represented as a vector, is fragmented into data subblocks M ₀ , M ₁ , …, M _θ of a fixed length m for monitoring the integrity of the data contained therein, in accordance with which an extended binary Galois field GF(2 ^m ) is selected, each non-zero element of which is represented as a power of α, with an infinite set of its elements being formed from the initial set {0, 1, α} by successively multiplying the elements by α, after which the generator polynomial g(x) of the corresponding Reed-Solomon code is specified, and the original data block M is written using primitive elements, to obtain the required dimension of which, depending on the information length k = ^2m - 1 - 2t of the selected Reed-Solomon code, is supplemented, if necessary, with η = k - θ - 1 zero subblocks, where t is equal to the number of detected or localized data subblocks with signs of integrity violation, the resulting extended data block M' contains subblocks M ₀ , …, M _θ , M _θ+1 , …, M _θ+η , which are represented by elements of GF(2 ^m ), as a result of encoding which a code polynomial c(x) is formed, the error polynomial e(x) is determined, the values H ₀ , H ₁ , …, H _ω of the hash function and syndromes S _ω are calculated at points α ^ω , where ω=1, 2, …, 2t, the verification of which makes it possible to determine the signs characterizing the violation of the integrity of subblocks M ₀ , M ₁ , …, M _θ of the data block M of the multidimensional array to be protected, characterized in that the procedure is applied to the data subblocks M ₁ , M ₂ , …, M _k of the data block M in the complexification block structural-algebraic transformation, allowing on the basis of a complex module obtained by forming it with the first and second generators of mutually prime numbers (p, q), perform the procedure of one-to-one transformation of the data subblocks M ₁ , M ₂ , …, M _k of the data block M to a protected representation in the form of complex numbers a ₁ + b ₁ i, a ₂ + b ₂ i, …, a _k + b _k i, which are fed to the complex number expansion block, in which the coding procedure is performed taking into account the rules for constructing generalized magic squares, consisting of performing the operations and calculating the reference value , after receiving which an ordered sequence of complex numbers from the expansion block it enters the buffer, in which the transformation to the form of two-dimensional code structures (a ₁ , b ₁ i) is carried out; from the first and second outputs of which the values of the actual and imaginary M, parts of two-dimensional code structures are sent through the data analysis unit for storage in the data storage subsystem in the memory cells of the first and second data storage sub-blocks, respectively, while the memory cells of the first data storage sub-block contain the headers of the array of stored data, which are assigned the values of the imaginary parts of complex numbers real part which is written into the corresponding memory cells of the second storage sub-block, and the subsequent filling of the memory cells of the first and second data storage sub-blocks is carried out by the data analysis block by correlating the value of the header of the array of stored data with the imaginary part of the complex number received for storage, when which coincide, the real part of the received complex number is written into the next free memory cell of the data array of the second sub-block for storing the real part of the complex number, as well as the set of values of the headers of the data array and the corresponding values of the real numbers are used by the distortion control check block, into which two-dimensional code structures are received from the first and second data storage subblocks with the subsequent formation of an ordered sequence of complex numbers which is subjected to a decoding procedure taking into account the rules for constructing generalized magic squares, where the control procedure consists of performing operations subsequent calculation of a new reference value and checking reference values, the discrepancy of which allows us to determine signs of data integrity violation, and move the sequence of complex numbers into the distortion correction unit, in which erroneous values of complex numbers are corrected, and the corrected sequence enters the objectification block, where the procedure of inverse transformation from the protected representation in the form of complex numbers is carried out to the open view of data subblocks data block M, which enters the data output block; in this case, the first and second mutually prime number generators form numbers (p, q), which enter the blocks for checking distortion control, distortion correction and reification for constructing a complex module

Images