In the paper, an error detection and correction algorithm was developed on the basis of modular correcting codes and a two-dimensional scheme. The developed algorithm provides effective correction of error packets, is characterized by high corrective ability and low complexity of decoding device implementation, and accordingly can be applied to increase the reliability of data transmission in wireless sensor networks. Check symbols are calculated separately for rows and columns of the data matrix. Due to the fact that the same mutually prime coefficients are used to calculate checksums along the rows and columns of the matrix, it allows for detecting and correcting error packets that are in the same row or column. The developed algorithm provides correction of error packets of maximum length = 3 − 2 ( − number of information symbols) when they are placed in two columns and one row or two rows and one column. Possible examples of placing the maximum number of distorted symbols in a data block and methods of their correction are given. The work of the coder for calculating check symbols and forming a data packet is described in the Verilog language and implemented on an FPGA by Altera. The structure of the decoder, which performs error detection based on the error correction syndrome check based on the solution of the system of modular equations, has been developed.
With the constant development and wide implementation of wireless technologies, improving the reliability of data transmission in wireless sensor networks (WSN) remains an important and urgent task [1]. In order to ensure the necessary level of reliability of data transmission in WSN, unlike wireless computer networks, it is necessary to take into account the limitations imposed by the low computing resources of nodes and the use of autonomous power [2, 3, 4]. In addition, additional complications are caused by the packet relay mode used in most WSN applications. Since WSN often uses methods of reducing traffic redundancy by compressing data and filtering correlated data, the requirements for the reliability of each packet transmission are increasing accordingly. Therefore, for the effective operation of WSN, it is necessary to ensure high reliability and energy efficiency of data transmission in different modes of network operation [16].
The main mechanism for improving the reliability of data transmission in WSN is the use of error control schemes. Their task is to ensure reliable communication in a wireless channel in which errors • • • occur due to interference, fading, and loss of bit synchronization. This leads to channel errors that affect the integrity of the packets forming the sensor nodes. The low power of WSN transmitters, which is connected with the use of autonomous power, also leads to an increase in errors [4, 5, 6].
Thus, in addition to methods of improving reliability at the physical level, which guarantees the reliability of transmission at the bit level, WSN also requires the application of error control schemes at the channel level to ensure reliability at the level of packet transmission.
the low complexity of encoding/decoding algorithms; low hardware requirements for the implementation of algorithms (microcontroller bit rate and clock frequency, memory volume);
adaptive change in the number of check symbols when changing the channel parameters.
The conducted analysis showed that many studies prove the advantages of using Reed–Solomon codes in WSN [11, 12, 13]. However, the use of Reed-Solomon codes makes it impossible to use adaptive error control schemes. Because when increasing/decreasing the number of check characters, it is necessary to list all check characters. To choose an effective error control scheme and the type of correction code, it is also necessary to take into account the permissible error probability for a given
Nowadays, there is considerable interest in the application of the residual number system (RNS) in new areas, such as increasing the reliability and security of cloud storage, homomorphic encryption, post-quantum cryptography, and others [14, 15, 20].
The residual number system belongs to the non-positional counting systems and is based on the concept of a remainder and the Chinese theorem on remainders. Any positive integer in RNS is presented as a set of the smallest positive remainders from dividing this number by the selected system of mutually prime numbers (modules) 1, 2, … , [14, 16, 21].
Data processing and transmission in RNS has a number of advantages due to independence, low bit rate and equality of balances, and the possibility of parallel execution of arithmetic operations. In addition to the above-mentioned advantages of RNS for data processing, effective RNS correction codes have also been developed that are capable of detecting and correcting error packets [17, 18,
Modular correcting codes developed in [22, 23] belong to symbol codes characterized by low redundancy and allow efficient detection and correction of single symbol errors.
In modular correction codes, the data packet in the binary code to be transmitted is divided into blocks of the same length (tetrads or bytes) [24]: 1 … 31 21 11 01, 2 … 32 22 12 02, … 3
2 1 0, … , … 3
2
1
0 , where – bit of data in binary code, = 4,8.
At the same time, the value of the control bit is equal to system, moreover where – coefficients, mutually prime with ; – byte of data in a binary or decimal calculation = 7 … 3 2 1 0 = 7 ∙ 27 + ⋯ + 3 ∙ 23 + 2 ∙ 22 + 1 ∙ 21 + 0 ∙ 20.
Suppose that an error occurred in one of the data blocks during the transmission (from 1 to 8
+1 = | 1 ∙ 1 + 2 ∙ 2 + ⋯ + ∙ + ⋯ + ∙ | ,
(
′ = ( 1, 2, … , ′, … , , +1).
′ +1 = | 1 ∙ 1 + 2 ∙ 2 + ⋯ + ∙ ′ + ⋯ + ∙ | .
= − + 1 where – total code length, – the number of information blocks. Accordingly, this correcting code detects or a smaller number of errors under the condition that
≥ + 1.
codes based on modular arithmetic is shown, which allows for detecting and correcting errors in two or more information symbols. However, the proposed method of correcting errors in two symbols based on the extended Euclid algorithm has a high time complexity, which depends on the value of the module increases with the gain in the number and bit rate of information symbols, as it requires finding all and solutions of the Diophantine equation. Algorithms for correcting error packets also require additional research. Therefore, the development of a two-dimensional coding method based on a modular correcting code and error packet correction algorithms is an urgent scientific task.
Moreover, the codes may be the same 1 = 2, and different 1 ≠ 2.
either 2.
= 1 × 2 two codes 1 and 2 name of code, code words which are all two-dimensional tables with rows and which are code words 1 and columns which are code words For building a two-dimensional code was chosen, modular corrective codes 1 and 2 [24, 25].
k fjk(x) = ∑i=1 xijvi modP encoded with the 1 and then each column is encoded with the 2. where – information symbols, , – coefficients (prime numbers), – module (prime number).
The formation of the two-dimensional modular code is shown in Table 1. At the first, each row is
The coding process is as follows (Figure 1): data for symbols are sent to the internal encoder 1,
where the verification symbols are calculated line by line according to formula (
Error detection is based on syndrome analysis, which is calculated as the difference between check symbols calculated in the encoder and decoder [26-30].
Syndrome calculation by rows:
1′ ( ) − 1 ( ) ⎛ 2′ ( ) − 2 ( ) ⎞
⋯ ⋯ ⋯ ⎟. = ⎜⎜ ⎜ ′ ( ) − ( ) ⎟⎟
⋯ ⋯ ⋯ ⎝ ′ ( ) − ( ) ⎠
′1( ) − 1( ) Syndrome calculation by columns:
If = 0, = 0 – errors do not exist. Else if ≠ 0, ≠ 0 – an error exists.
The position of the distorted symbol is determined by the value of the syndromes, which are not equal to zero at the intersection of the row and the column.
( ′ − ) = ( ). (
If syndromes ≠ 0, ≠ 0 are not equal to zero in two or more rows or columns, this means that errors occurred in two or more characters. Moreover, if the syndrome ≠ 0 in two columns – it means that two characters in the string are garbled. The positions of non-zero characters correspond to non-zero syndrome values in the column.
Error correction in two information symbols. Analysis of the syndrome by rows and columns allows you to identify the positions of the distorted characters. It is necessary to solve the equation to correct them:
+ = ( ′ + ′ − )( ), where , t – position of garbled symbols.
+ = с( ). (
It is known if gcd( , ) = 1, that is and mutually prime numbers, then equation (
= − ( ). (
As 0 ≤ < 2 0 ≤ < 2 then by substituting in equation (
With the minimum code distance of codes 1 and 1 equal 1 and 2 in accordance then the
minimum code distance of a two-dimensional code equal 1 × 2. It follows that if codes 1 and 1
( ′ − ) + ( ′ − ) = (
′ − + ′ − = (
− − = ( − ′ − ′)(
);
);
);
(
However, this code will not be able to correct a package of errors of six characters, which are located at the intersection of three rows and three columns (Figure 3). * * *
A two-dimensional code based on modular correcting codes has been developed, which provides effective correction of error packets of maximum length = 3 − 2 symbols, provided that the distorted characters are placed in two rows and one column, or in two columns and one row. 3.2. An algorithm for the detection and correction of error packages based on modular correction codes
Based on the method of correcting error packets, an algorithm for detecting and correcting error packages using modular correcting codes and a two-dimensional scheme has been developed.
The algorithm works as follows (Figure 4): in block 1, we enter mutually simple coefficients ,
the value of the module P, and information symbols . Then, in block 2 and block 3, syndromes are
calculated by rows and columns by formulas (
If the value of the syndrome (block 4) = 0, = 0, then no error is detected, and if ≠ 0, ≠ 0 or if in at least one of the syndromes = 0, ≠ 0, then the error is detected and we proceed to its correction.
( ′ − ) = ( ), where – mutually prime coefficients, ′ – received message and – the message that was already sent.
After finding the solutions of this equation for all rows, we check the value of the syndrome (block
6) when: ≠ 0, = 0 – there are errors in the columns, which we correct according to the formula
(
Start m, P, vi i=1 k =1 = 0, = 0
A 1 10 13 11 5 3 7 ( ′ − ) = (
)
In block 10, we check, if the value of the syndrome = 0, = 0 , then the errors are corrected, and if the value of the syndrome ≠ 0, ≠ 0 – more errors than the algorithm can correct
Let’s see the example. Let's start to build a two-dimensional code based on a modular correction 1 = 17, 2 = 19, 3 = 23, 4 = 29, 15 = 31, 6 = 37, 7 = 43, 8 = 47 (Table2). code with = 8, = 8, bit rate of information symbols = 4, module = 1019, and coefficients: A two-dimensional modular code at the output of the transmitter 1 2 3 B
5 3 13 11 6 9 4 12
Consider the error correction algorithm for the maximum number of distorted symbols (Table 3). 12* 10* 6 9 4 12 13 15 539 12* 11* 13* 3* 5* 928 11* 7* 10 9 7 5 0 1 253 845 36 983 71 55 4 901 72 8 4* 9* 15 13 0 5 9 3 655
Check symbols calculated by rows 275 846 181 51 690 845 845 718 Check symbols calculated by
columns * – distorted symbols.
2. By substituting the calculated values in Table 3, we will get a new table of syndromes (Table 6).
After analyzing Table 6 it shows that there are errors in all columns but only in two rows. That is,
all symbols in the first and second lines are distorted. Correction of errors in two symbols is carried
out using equation (
To correct errors in the symbols placed in the first column, if we substitute numerical values in
equation (
17 1 + 19 2 = 417( 1019); (
After solving equation (
As can we can see from Table 7, the found solutions of equation (
An algorithm for detecting and correcting random single errors and error packets with a maximum length of = 3 − 2, at a code speed of = 0.67, has been developed.
Considering the low complexity of the decoding algorithm implementation, this code is planned to be used to increase the reliability of data transmission in wireless sensor networks. 3.3. An interference-resistant data encoding/decoding device based on two-dimensional modular correction codes
The coding process is as follows (Figure 5). A message with k symbols is received at the encoder input. The coder calculates the check symbol and writes the message with the check symbol to the buffer. The process is repeated until messages are received. A data array is formed from the received messages, from which verification symbols are calculated by the columns of the array.
+ +
After the encoder completes the calculation of check symbols by columns, a new array of the received message with calculated check symbols by rows and columns is formed at the output. The structure of the message at the output of the encoder is presented in Figure 6.
An example of interference-resistant coding based on modular codes and a two-dimensional scheme. Incoming messages formed in the form of a two-dimensional array are shown in Table 8.
To implement the coder, we will choose mutually simple coefficients : 1 = 211, 2 = 257, 3 = 263, 4 = 269, 5 = 271, 6 = 277, 7 = 283, 8 = 288 and module = 131297. x5 2 205 204 15 133 161 254 33 10678
We calculate the verification symbols by rows according to formula (
The operation of the coder is described in the Verilog language and synthesized on a FPGA by
The decoder calculates check symbols on the received data and compares them with those that were calculated by the encoder and sent. To correct errors in the data packet, a table of syndromes is formed in the decoder by rows and columns.
The correction of single errors is based on the comparison of the calculated syndrome with the table of syndromes, if the values match, the error has been detected and can be corrected. After that, the table of syndromes is calculated by rows and columns, if the value of the syndrome is zero, then the errors have been corrected.
If the values in the table of syndromes are not equal to zero, it means that errors have been
detected and they are placed in two lines. To correct such errors, equation (
The developed device of interference-resistant data decoding based on two-dimensional modular correction codes makes it possible to detect and correct a large number of errors in a data packet.
A two-dimensional approach to error correction based on modular correction codes is proposed, which provides effective correction of error packets, is characterized by high correction ability and low complexity of decoding algorithm implementation, and accordingly can be applied to increase the reliability of data transmission in wireless sensor networks.
An algorithm for detecting and correcting error packets based on modular correcting codes and a two-dimensional scheme has been developed. This algorithm provides detection and correction of packets with the length of errors that are in one row or column of the data matrix of size × , or 2 ∙ errors that are in two rows or two columns of the data matrix. Moreover, the algorithm provides correction of the maximum length of error packets that can be = 3 − 2 at speed of code = 0.67, if the distorted characters are in two rows and one column or in two columns and one row.
A structure was developed and an encoder for calculating check symbols and forming a data packet based on two-dimensional modular correction codes was developed and implemented on an FPGA. To be more precise, the limitations of the conducted research should be attributed to the low bit rate message size of only 8 bits, as well as the fact that only an 8x8 matrix size was considered.
Further research is required on algorithms for finding mutually prime coefficients with a minimum value of the check module for encoding messages with a bit depth of 8-16.
[15] D. Schoinianakis. Residue arithmetic systems in cryptography: a survey on modern security
applications. Journal of Cryptographic Engineering, 10(
Radioelectronics And Communications Systems, 60 (
Conference Proceedings of 14 th International Conference Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (TCSET-2018) (Lviv-Slavske, Ukraine February 20-24 2018). Lviv. 2018, pp. 389-392. doi:10.1109/TCSET.2018.8336388. [26] Chen, Z.; Zhao, Y.; Lu, J.; Liang, B.; Chen, X.; Li, C. TECED: A Two-Dimensional Error-Correction Codes Based Energy-Efficiency SRAM Design. Electronics 2022, 11, 1638. https://doi.org/10.3390/electronics11101638 [27] Sergii Lysenko, Kira Bobrovnikova, Roman Shchuka, Oleg Savenko. A Cyberattacks Detection Technique Based on Evolutionary Algorithms. 11th International Conference on Dependable
[28] Antony, B.; Divya, S. Modified Hamming Codes with Double Adjacent Error Correction along with
Enhanced Adjacent Error Detection. Int. J. Innov. Res. Comput. Commun. Eng. 2015, 3, 7706–7713. [29] Chen, X.; Lu, Z.; Lei, Y.; Wang, Y.; Chen, S. Multi-bit transient fault control for NoC links using 2D fault coding method. In Proceedings of the 2016 Tenth IEEE/ACM International Symposium on
[30] Rostand, N.; Hubert, G.; Martinie, S. SEU Prediction for Very Integrated Circuits based on Advanced Physical Considerations. In Proceedings of the 2019 19th European Conference on Radiation and Its Effects on Components and Systems (RADECS), Montpellier, France, 16–20 September 2019; pp. 1–