The paper presents the results of theoretical and experimental studies of the ability of the rank codes, proposed by the authors, to detect and correct errors introduced by information transmission channels. The introduction discusses the principles of rank codes building and their application in decision-making systems. In the main part of the presented work, aspects of research related to the theoretical and experimental evaluation of their ability to detect and correct errors introduced by the transmission channel are highlighted. Algorithms for finding and correcting errors are presented.
Today, the problem of developing theoretical foundations and practical means of unified presentation of information about the states of control objects, its coding and transmission in control systems during decision-making is quite relevant. It is known that decisions regarding the management of objects of various nature in control systems are made on the basis of information about the distance between the current and target states of the object [1]. These distances in different parametric spaces (deterministic, probabilistic, approximate, fuzzy, etc.) are described differently, which requires for each case the development of separate methods and algorithms for presenting information and making decisions [2, 3, 4, 5]. In order to unify the methods and algorithms of presenting and processing information for decision-making in control systems, the authors proposed to describe the states of the systems by rank configurations, and the rank configurations themselves by potential codes (or DRP codes – codes that preserve the ranks of the distances between states). The proposed codes were called potential by analogy with the electric field. In them, the rank value of the distance between code words is defined as the difference between their values, just as the field strength between electric charges is defined as the difference in their potentials. Such codes make it possible to reduce information processing algorithms in various parametric descriptions to performing a single logical operation on them [6, 7]. To determine the type of this operation and the characteristics of the codes themselves, a number of models of rank configurations, including their interval model, have been developed [6].
Unfortunately, there is a small number of works in the direction of applying such an approach to the description, processing and transmission of information in decision-making systems. As an example, we can note works [8, 9] in which difference codes are proposed for 0000-0002-7624-7072 (V. Kovtun); 0000-0001-5385-8084 (M. Bykov); 0000-0002-4308-2654 (T. Gryshchuk); © 2024 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). description and pattern recognition. In [10], we showed the advantages of our approach compared to the one proposed in [8, 9], which makes further research in this area relevant
The codes proposed by us can be used to increase the efficiency of the decision-making process in systems of various purposes [11, 12] and to increase the immunity of the information transmission process in communication channels. For example, in the proposed hierarchical parallel-serial pattern recognition strategy [11], it is convenient to use the description of these objects in a rank scale for the classification of objects at the upper level of the described strategy, since their clusters in the feature space do not intersect.
The authors also developed a system for transmitting rank information through communication channels, proposed schemes for encoding and decoding information in this system without taking into account the influence of interferences on the communication channel [13]. In real network communication channels of computer-integrated control systems, there are intense interference signals that generate errors in code words. Therefore, in this work the task of conducting theoretical and experimental studies is set for the purpose of developing algorithms of localization and correcting asymmetric and symmetric errors introduced by the communication channel in DRP codes.
For a better understanding of the carried out in this work research we present a number of necessary theoretical provisions regarding the models of rank configurations and rank codes (DRP-codes), presented by the authors in the work [6].
For a better understanding of the research carried out in this work, we will present a number of necessary theoretical provisions regarding the models of rank configurations and rank codes (DRP codes), presented by the authors in the work [6].
The rank configuration of the space of objects described in some parametric space is called a set of elemental subsets, the elements of these subsets are the ranks of distances incident to the same object [6, 9].
It is convenient to compactly present the rank configuration in algebraic form. For example, the rank configuration in Fig. 1 can be written in algebraic form as
K4 = {{1, 4,6},{2, 4,5},{2,3,6},{1,3,5}}. (
The geometric (Fig. 1) and combinatorial (Fig. 2) models of rank configurations are the most relevant for the task of determining the interference resistance and corrective capabilities of the proposed rank codes.
The simplex and the graph give a visual representation of the rank configuration. In Fig. 1 a) the vertices A, B, C, D denote coded objects, and the numbers on the edges of the simplex and arcs of the graph are their incident ranks.
The use of the graph incidence matrix of Fig.2 a) allows us to directly determine the codes of
the A, V, C, D vertices in the DRP-code. It can be seen from Fig. 2a) that this code is by its nature
,
(
In the following sections of the work, we will perform theoretical and experimental studies necessary to determine the ability of the proposed rank codes to detect and correct errors introduced by the information transmission channel, and based on them we will develop algorithms for localization and correction of these errors.
Since the transmission channels of industrial networks, in which the proposed rank code
should be used, are subject to the influence of interference capable of generating both
symmetric and asymmetric errors, the use of error localization and correction methods used for
standard CWC codes is impossible. Accordingly, the theoretical evaluation of the effectiveness of
these methods should be carried out taking into account the principles of construction of these
codes. According to the characteristics of rank codes, when the number of coded states of
systems m increases, the bit rate n of the code increases according to the expression (
To obtain a theoretical estimate, we will first prove the theorem: for a rank configuration of dimension m, the Hamming distance dx between words of the rank code is equal to dx =2(m-1)-2.
Proof: The two code words of the rank code, between which the Hamming distance is calculated, contain 2(m-1) single digits, and the single digits match only in one digit, one from each word, in total 2. Therefore, the number of digits in which the ones do not match, is equal to 2(m-1)-2, and the logical XOR operation on these words, by which the Hamming distance is calculated, will give 2(m-1)-2 units, which is what we needed to prove.
It follows from the proven theorem according to [14] that the theoretical estimate of the
possibility of detecting errors by the multiplicity gd is determined by the formula
gd ≤ d x −1 = 2(m −1) − 3 , (
2 2
(
The identification of the model was performed experimentally on the examples of specific rank configurations of dimensions m=4 and m=5 using models of rank configurations in the form of incidence matrices, the rows of which form the DRP-codes of the vertices of the rank simplex. dX(A,B)=000111 ⊕ 011001=4 dX(A,D)=000111 ⊕ 110100=4 dX(B,D)= 011001 ⊕ 110100=4 dX(A,C)=000111 ⊕ 101010=4 dX(B,C)= 011001 ⊕ 101010=4 dX(C,D)= 101010 ⊕ 110100=4 error detecting error correction gd ≤ dx − 1 = 4 − 1 = 3 , gc ≤ (dx − 1) = 3 = 1.
2 2 dX(A,B)=0001111000 ⊕ 0010001110=6 dX(A,D)=0001111000 ⊕ 0100010011=6 dX(B,C)= 0010001110 ⊕ 1000100101=6 dX(B,E)= 0010001110 ⊕ 1111000000=6 dX(C,E)= 1000100101 ⊕ 1111000000=6 dX(A,C)=0001111000 ⊕ 1000100101=6 dX(A,E)=0001111000 ⊕ 1111000000=6 dX(B,D)= 0010001110 ⊕ 0100010011=6 dX(C,D)= 1000100101 ⊕ 0100010011=6 dX(D,E)= 0100010011 ⊕ 1111000000=6 error detecting error correction gd ≤ d x −1 = 6 −1 = 5 , gc ≤ (d x −1) = 5 = 2 .
2 2
According to the law of induction, it is easy to show numerical values of the multiplicity of detected and corrected errors for rank configurations of higher dimensions m=6..11. For configurations with a dimension higher than 11, it is inefficient to use potential codes, since their bit rate exceeds the bit rate of modern PC n≥64, and computational operations on the codes become complex and inefficient.
Before proceeding to experimental studies on the assessment of the ability of the rank code to detect and correct errors introduced by the channel, we will perform a theoretical assessment of the dependence of the DRP code's reliability on the properties of the transmission channel itself. This will make it possible to focus attention in the experiment on methods of localization and correction of those errors that are most likely to occur in the channel.
The enhanced noise immunity of the proposed DRP-code is based on the fact that it is inherently a constant-weight code (CWC) in which each single bit is placed in the same positions simultaneously in two codewords. The probability of not detecting one error in the code word (the combined probability of converting one zero point into one unit and one unit point into zero) for the CWC, and therefore the DRP-code, is equal to [14]:
Pn = Cm1−1 p(1 − p)m−2 Cn1−m+1 p(1 − p)n−m , (
2 2
The number of units point in the code word of this configuration is (m-1)=3. From the
expression (
PnDRP = C31 p(1 − p)2 C31 p(1 − p)2 = 9 p2 (1 − p)4 .
Taking the value of p = 1 ⋅ 10 −4 , we obtain for the CWC PnCWC ≈ 12 ⋅10−8 PnDRP ≈ 9 ⋅10−8 for the DRP-code. Since for the DRP-code the unit must not be detected simultaneously in two codewords, then PnDRP ≈ 81⋅10−16 .
Let's find a relationship
PnCWC = 8112⋅⋅1100−−186 ≈ 0,15 ⋅108
PnDRP
and
(
From expression (
The conducted theoretical assessment of the DRP code immunity to the influence of symmetric channel interference showed that the probability of introducing a single symmetric error into the DRP code by the channel is quite small, but higher than the probability of multiple type errors. Therefore, in experimental studies, it is necessary to first of all focus efforts on finding methods for building algorithms for localization and correction of single errors. 3.3.
According to the standard classification, CWC belongs to block nonlinear codes. The analysis of mathematical models of the rank code shows that it is a set of m multivalued logical functions of significance n, the values of the arguments of which are obtained by mapping the ordered distances between the elements of the original space to an ordered set of ranks using the logical operation "AND". Since the "AND" operation on a set of code words is not a group one, standard 6 methods are not suitable for correcting DRP code transmission errors, and the development of original algorithms for localization and error correction based on the study of heuristic patterns is required. Since asymmetric errors in code words (erasure of “1” to “0” or insertion of a “1” instead of “0”) are detected in the CWC by a standard algorithm for counting the number of units in a code word, the main attention will be paid to the study of symmetric errors,, i.e. pairwise replacement in certain digits of code words 0" to "1" and vice versa. For research, we will choose the rank configurations of the three-dimensional simplex shown in Fig. 1 a) and DRP-codes, representing by incidence matrix in Fig. 2 a) respectively.
For asymmetric errors in code words, when an additional “1” is introduced, or one “1” is erased to “0”, the localization and correction algorithm is simple:
The number of p units in the code word is counted, and if p > m-1, then the algorithm erases the extra unit in the bit that corresponds to the column of the matrix with the number “1” greater than 2; if p < m-1, then the algorithm inserts a “1” into the bit that corresponds to the column of the MKOD matrix, in which there is only one “1”. An example of a DRP code with an additional error introduced by an asymmetric channel in the form of an additional “1” is shown in Table 1.
In Table 2, in the 6th digit of the code of symbol A, value “1” is replaced by "0". This code word is localized as false by the number of units p= < 3, and since there are less than two units in the 6th column of the matrix, the correction algorithm must write a unit in the 6th digit.
The study of symmetric errors will consist in the analysis of the appearance of the DRP code after entering the selected code word with an even error. The number of different variants Ev of such errors can be determined by the formula:
Ev = m(Cm1−1C(1n−m+1) ),
(
In Table 1 an additional “1” is entered in the code of symbol C in the 5th digit (this is an asymmetric error). This code word is localized as erroneous by the number of units p=4 >3, and since there are more than two units in the 5th column of the matrix, the localization algorithm and the correction should erase it.
An example of a DRP code with an additional error introduced by an asymmetric channel in the form of an erased "1" is shown in Table 2. where m is the number of coded symbols (system states), Cm1−1- the number of possible errors in units digits, C(1n−m+1) ) - the number of possible variants of errors in zero digits. For the DRP-code of the configurations selected for the study (Fig. 1 and Fig. 2, m=4, n=6), the number of error variants for the study is equal to:
Ev = 4(C41−1C(16−4+1) ) = 4 ⋅ 3 ⋅ 3 = 36. (10)
The analysis of the results of the research for these options showed that in order to build a heuristic algorithm, in addition to the erroneous code words themselves, it is also necessary to analyze the verification matrix G[n,n] of the rank distances between all pairs of code words. As an example, we determine the distance d(AD) between the code words of symbols A and D in the table of Fig. 2a), for which we use the expression:
d ( AD) = xA ∧ xD = 101001 ∧ 010101 = 000001 , where ∧ is the logical operation AND, and xA, xD are DRP-codes of vertices A and D.
Examples of the correct DRP code and the verification matrix Gnn for them are shown in Fig.5, and the wrong DRP codes and the verification matrices Gnn for them are shown in Fig. 6-7. b) Figure 5: The correct DRP code of the rank configuration (a) and the verification matrix G[n,n] of rank distances for it (b) b) Figure 6: DRP code of the rank configuration (a) with an error in code word B (“1” from digit 5 moved to digit 6, and “0” became in its place) and the check matrix of rank distances for it (b) b) Figure 7: DRP code of the rank configuration (a) with an error in code word B (“1” from bit 5 moved to bit 1, and in its place became “0”) and the check matrix G[n,n] of rank distances for it (b) We will consider those shown in tables 1 and 2, as well as in fig. 5a), 6a) and 7a) DRP codes of words A, B, C and D in the interpretation of some code matrix MKOD. Then symbol A will correspond to the row index i=1, symbol B - i=2, symbol C - i=3, symbol D - i=4. Ranks 1, 2, 3, 4, 5, 6 will correspond to the significant index j of the column of the code matrix j=1, j-2, j=3, j=4, j=5 and j=6, respectively.
Distances d(i,j) between code words (for example, d(AB) is d(
Therefore, in the matrix of MKOD codes for an undamaged code, in each column there are two “1” in the codes of their symbols (vertices of the simplex), which are the incident edge with the rank corresponding to the number of this column, and in the corresponding columns of the verification matrix there is only one “1”, and there is also one “1” in each row of this matrix. These are signs of error-free code.
For the code damaged by a symmetric error in Fig. 7 (where the “1” from the 5th digit moved to the 1st digit, and a “0” was entered in its place), we have in the code matrix MKOD three “1” in the column of the 1st digit and one “1” in the column of the 5th discharge. This is a sign of code damage, since there are still three “1” left in the code words (rows of the MKOD matrix). That is, the code by the number of “1” in the word remains a code with a constant weight of CWC=3, and the number of “1” and the number of "1" in the row of the MKOD matrix is not a feature of introducing a symmetric error into the code word.
In the verification matrix G[n,n] for this case (Fig. 7), we can see that there is no “1” in the 5th
digit column (this is a sign to which digit of the damaged word should be returned “1”), and in
the 1st digit column there are as many as three “ 1" (this is a sign in which digit of the damaged
word should be returned "0"). Now it remains to determine the index of the damaged word (the
row number in the MKOD matrix, in which a single symmetric error is introduced). For this case
of the values of the verification matrix G[n,n], the sign is simple - there are two "1"s only in the
distance with index 2 (d(АВ)=d(
For the code damaged by a single symmetric error in Fig.6 case for the verification matrix G[n,n] is more complicated. Again, by the number of "1" in its digit columns, we can see that it is necessary to transfer "1" from the 6th digit to the 5th digit of the damaged word, and the indicator for detecting the number of the damaged word will be the priority of the index in the lines with which the incorrect number of “1” (> one).
Since in the rows of the matrix for d(AB), d(BC) (respectively d(
According to the regularities found in the previous sections, the heuristic algorithm for localization and correction of single asymmetric and symmetric errors in the DRP code can have the following verbal description.
In the first step, a two-dimensional array of m × n size of m code words received from channel is formed in the decoder memory, where n is the bit rate of the code. Under the condition of error-free transmission, this array will correspond to the incidence matrix of the transmitted rank configuration of system states, and each raw of the array will correspond to the correct DRP code word.
In the second step, by counting units in each line of the array, code words with asymmetric errors are localized in the case of t≠m-1, where t is the number of units point in the word. Correction of asymmetric errors is carried out according to the procedure: if the number of units t>m in some word, then the columns of the array of code words are scanned and in the found erroneous word units are replaced with zeros point in those digits whose columns contain more than 2 units point; if the number of units point in some word is t<m-1, then the columns of the array of code words are scanned and in the found erroneous word, zeros point are replaced by units point in those bits whose columns contain less than 2 units point.
In the third step, the columns of the array are scanned and the presence of symmetric even errors is detected in the case of columns with units point, in which the number of units is not equal to 2. Localization of the erroneous code word is carried out using the verification matrix GR[n, n] according to the following procedure: those rows of the matrix that contain two units point are marked. If there is more than one such code word, then the one whose index is contained in the indices of pairs of distances twice is chosen as false.
In the fourth step, the numbers of damaged bits are located and corrected. For asymmetric errors, they are determined by the presence or absence of the necessary units point in the words, and for symmetric errors, as a rule: the column with zeros in the verification matrix of the codeword distances, obtained by the logical operation “AND” over all pairs of codewords, shows a bit with a replacement of 1→ 0, and the column with three units point is a bit with 0→1 replacement.
By the pseudocode 1, with the selected code vatrix MKOD and verification distance matrix G[n,n], the algorithm for localization and correction of asymmetric and symmetric errors is shown. To implement the algorithm, a Python program was developed, which is a commercial product and can be provided upon separate request.
Algorithm 1: detection and correction of errors in DRP-code function ASSYMETRIC_ERRORS_CHECK (MKOD) (M , N) ← MKOD.shape ▷ dimentions of code matrix sum_of_rows ← P ∑ MKOD for (i, sum) ∈ enumerate(sum_of_rows) do if sum ≠ M − 1 then
▷ get list of sums of rows sum_of_columns ← P ∑ MKOD for (j, sum) ∈ enumerate(sum of columns) do if sum > 2 then
MKOD i,j ← 0 end if if sum < 2 then
MKOD i,j ← 1 end if end for end if end for return MKOD end function function SYMETRIC_ERRORS_CHECK(MKOD) (G, pairs) ← buid_check_table (MKOD) sum_of_rows ← P ∑G words_with_errors ← ” ” for (i, sum) ∈ enumerate(sum_of_rows) do if sum = 2 then
words_with_errors ← ” ”.join([words with errors, str(pairsi,0), (strpairsi,1)])
end if
end for
word_with_error ← int(Counter(words_with_errors) .most_common(
end if if sum = 3 then bit2 ← j
end if end for return (MKOD, word_with_error, bit1, bit2) end function
It is rather difficult to investigate with the help of a machine experiment all variants of errors that can be introduced into DRP codes during their transmission over a communication channel, since the number of these variants is quite large. For example, it follows from expression (10) that only for the code that transmits information about only one rank configuration, the number of variants of introduced errors is Ev=36. And since for a rank simplex of dimension m=4, the number of different rank configurations Mc=30 [6], the total of such different variants of errors is equal to Ev*Mc = 36*30=1080. For m>4, the number of options for processing by a person is unthinkable, and the mechanism of computer generation of various error options in the DRP code at this stage of research has not yet been developed by the authors. Therefore, to check the adequacy of the developed algorithm on the ability to detect and correct errors in rank codes, software testing was conducted, part of the results of which are presented below. The results show that the developed algorithm correctly localizes and corrects both asymmetric and symmetric errors in codes.
Start of asymmetric errors check: input matrix: [[1 0 1 0 0 1] [0 1 1 0 1 0] [1 1 0 1 1 0] [0 1 0 1 0 1]] sum of rows = [3 3 4 3] index of corrupted word = 3 code of corrupted word = [1 1 0 1 1 0] corrupted bit = 5 fixed matrix: [[1 0 1 0 0 1] [0 1 1 0 1 0] [1 0 0 1 1 0] [0 1 0 1 0 1]] End Fixed! Start of asymmetric errors check: input matrix: [[1 0 1 0 0 1] [0 1 1 0 1 0] [1 0 0 1 1 1] [0 1 0 1 0 1]] sum of rows = [3 3 4 3] index of corrupted word = 3 code of corrupted word = [1 0 0 1 1 1] corrupted bit = 1 fixed matrix: [[1 0 1 0 0 1] [0 1 1 0 1 0] [1 0 0 1 1 0] [0 1 0 1 0 1]] End Fixed!
The theoretical and experimental studies carried out in the work on the evaluation of the interference resistance and corrective ability of the rank codes proposed by the authors showed that these codes are highly resistant to communication channel interference and make it possible to localize asymmetric and symmetric errors in them with the help of simple algorithms. The work theoretically proved that the Hamming distance dx between the codewords of the DRP code is equal to 2(m-1)-2, which provides the possibility of localizing errors with a multiplicity of 2(m-1)-3 and correcting errors with a multiplicity (2(m-1) -3)/2. The corrective ability of the proposed rank code increases with an increase in the number of code words m that describe the given rank configuration of coded elements in the feature space. The conducted experimental studies of error variants in the DRP code made it possible to develop a heuristic algorithm for their localization and correction using an auxiliary verification matrix. Testing of the algorithm on a code with a bit rate of n=6 confirmed the adequacy of the developed algorithm for localization and correction errors of multiplicity 1. Assessment of the correctness of the algorithm's operation on codes of a higher bit rate and with errors of a higher multiplicity requires additional research.
The authors are grateful to all colleagues and institutions that contributed to the research and made it possible to publish its results.