Formulation of the problem: The need to ensure the integrity of data transmitted in communication networks makes the issue of ensuring the formation of checksums actual. At the same time, it is advisable to reduce the complexity of algorithms for generating checksums to improve data integrity. The well-known CRC (Cyclic Redundancy Code) checksum generation algorithm has high computational complexity. The aim of the work is to perform search studies to substantiate the fundamental possibility of reducing the computational complexity of the algorithm for generating CRC checksums and searching for possible ways of practical implementation. The novelty of the work lies in the fact that in order to achieve the goal of the work, the computational complexity of the CRC algorithm is investigated depending on various generating polynomials and their bit width. Result: on the basis of the conducted search studies, the possibility of reducing the computational complexity of the algorithm for generating CRC checksums for data transmitted in communication networks was confirmed. Additionally, a set of programs is presented for assessing the complexity of the CRC checksum generation algorithm depending on the length of the polynomial, as well as the analysis of the computational complexity of the CRC-based data integrity check algorithm. Practical relevance: The research results can be applied to reduce the computational complexity of the algorithm for generating CRC checksums in protocols of data transmission networks, as well as to substantiate promising ways for further research in this direction.
One of the important tasks in modern communication networks is to ensure data integrity. The most common algorithm for determining the integrity of transmitted data is the CRC (Cyclic Redundancy Check) algorithm.1.
Turdiev);
The CRC algorithm is based on the theory
of cyclic error correction codes. This algorithm
was first proposed by V.V. Peterson and D.T.
Brown, in [
The theoretical provisions of the functioning
of the CRC algorithm are given in [
In addition, in real transmission conditions,
the communication channel can be affected by
various kinds of interference, which appear in the
process under study in the form of erroneous bits,
which lead to a violation of data integrity [
Summarizing the above, it can be noted that the purpose of the work is to perform search studies to substantiate the fundamental possibility and possible ways to reduce the computational complexity of the CRC checksum generation algorithm used to control the integrity of the transmitted data.
To find ways to reduce the computational complexity in the work, a study of the computational complexity of the formation of CRC checksums was carried out depending on various generating polynomials and their bit width. To assess the computational complexity of the CRC, we simulated the process of transmitting binary data over a symmetric channel.
Cyclic redundancy codes CRC are a
subclass of block codes and are used in HDLC,
Token Ring, Token Bus protocols, Ethernet
protocol families and other link layer protocols
[
One of the ways to represent a cyclic code is to represent it in the form of a generating polynomial - the set of all polynomials of degree (r – code-1), containing some fixed polynomial G (x) as a common factor. The polynomial G (x) is called the generating polynomial of the code. For example, 4+ +1, here r-code = 5, since the binary sequence looks like 10011. The standardized and recommended generator polynomials for the CRC algorithm are given in Table 1, where the name of the standard and the generator polynomial are shown: for example, the notation 4+ + 1 is equivalent to 1∙ 4 + 0∙ 3 + 0∙ 2 + 1∙ + 1∙ 0 = 10011 (in binary).
Generating polynomials CRC-15-CAN 15 + 14 + 10 + 8 + 7 + 4 + 3 + 1
CRC-16-IBM 16 + 15 + 2 + 1 (Bisync, Modbus, USB, ANSI X3.28,) CRC-16-CCITT 16 + 12 + 5 + 1 (X.25, HDLC, XMODEM, Bluetooth, SD и др.) CRC-16-T10-DIF 16 + 15 + 11 + 9 + 8 + 7 + 5 + 4 + 2 + 1 (SCSI DIF) CRC-16-DNP 16 + 13 + 12 + 11 + 10 + 8 + 6 + 5 + 2 + 1 (DNP, IEC 870,
M-Bus) CRC-24 24 + 22 + 20 + 19 + 18 + 16 + 14 + 13 + 11 + 10 + 8 + 6 + 3 + + 1 (FlexRay) CRC-24-Radix-64 24 + 23 + 18 + 17 + 14 + 11 + 10 + 7 + 6 + 5 + 4 + 3 + + 1 (OpenPGP) CRC-30 30 + 29 + 21 + 15 + 13 + 12 + 11 + 8 + 7 + 6 + 2 + + 1 (CDMA) CRC-32-IEEE 802.3 32 + 26 + 23 + 22 + 16 + 12 + 10 + 8 + 7 + 5 + 4 + 2 + + 1 (V.42, MPEG-2, PNG, POSIX cksum) CRC-32C (Castagnoli) 32 + 28 + 27 + 26 + 25 + 23 + 22 + 20 + 19 + 18 + 14 + 13 + 11 + 10 + 9 + 8 + 6 + 1 CRC-32K (Koopman) 32 + 28 + 27 + 26 + 25 + 23 + 22 + 20 + 19 + 18 + 14 + 13 + 11 + 10 + 9 + 8 + 6 + 1
CRC-32Q 32 + 31 + 24 + 22 + 16 + 14 + 8 + 7 + 5 + 3 + + 1 CRC-64-ISO 64 + 4 + 3 + + 1 (HDLC — ISO 3309) CRC-64-ECMA 64 + 62 + 57 + 55 + 54 + 53 + 52 + 47 + 46 + 45 + 40 + 39 + 38 + 37 + 35 + 33 + 32 + 31 + 29 + 27 + 24 + 23 + 22 + 21 + 19 + 17 + 13 + 12 + 10 + 9 + 7 + 4 + + 1
implementation of the CRC algorithm is the remainder of dividing the binary sequence M (x) corresponding to the input data by the generating binary sequence G (x) of degree r.
Each final sequence of bits is one-to-one associated with a binary polynomial, the sequence of which is the original sequence. For example, bit sequence 1011010 corresponds to the binary polynomial M(x) = 1· x6 + 0· x5 + 1· x4 + 1· x3 + 0· x2 + 1· x1 + 0· x0 = x6 + x4 + x3 + x.
Let's consider examples in which addition and subtraction are performed without carrying the digits in accordance with the "exclusive OR" operation, which corresponds to the addition modulo 2 of binary arithmetic.
binary system, with the difference that the subtraction is performed modulo 2.
The use of polynomial codes during
transmission is as follows. The sender and the
receiver pre-select the same generator
polynomial G (x), whose coefficients at the
higher term and at the lower term must be equal
to 1. When calculating the checksums of a block
of m bits in size, the following condition m > r
must be met. Further, implementing the CRC
calculation algorithm, the sender adds the
checksum to the transmitted block, considered as
a polynomial M (x), so that the transmitted block
with the checksum is a multiple of G (x). When
the recipient receives the checksum block, he
divides it by G (x). If a nonzero remainder is
formed, then this indicates the occurrence of an
error during transmission [
Checksum calculation algorithm: 1. Add r zeros to the end of the block so that it contains m + r digits, the result is a polynomial xrM (x). 2. Divide the polynomial xrM (x) by G (x) modulo 2, the quotient is ignored. 3. Subtract modulo 2 the remainder (its length does not exceed r bits) from the string corresponding to xrM (x). The result is a block with a checksum.
CRC-12 = 12 + 11 + 3 + 2 + + 1 CRC-16-IBM = 16 + 15 + 2 + 1 CRC-16-CCITT = 16 + 12 + 5 + 1
CRC-12 is used to transmit 6-bit characters. The other two are for 8-bit. CRC-16 and CRC-CCITT detect all single and all double errors, an odd number of isolated errors, single bursts of errors less than 16 in length, and many burst errors greater than 16 with a 99.997% probability.
After getting acquainted with the basic concepts and characteristics of CRC codes, let us consider an example of calculating the remainder of cyclic redundancy codes and estimate the computational complexity of this process.
Thus, the example shows that with the generator polynomial CRC-4-TU (10011) and the bit length of the information frame equal to 10 bits, 10 divisions and 50 modulo 2 additions are required. In the general case, the relationship between the computational complexity (the number of additions and divisions), the size of the generating polynomial and the size of the information polynomial.
For the best understanding of the number of divisions and additions in the CRC algorithm with various generator polynomials and information frames, software has been created to assess the computational complexity of the CRC algorithm.
computational complexity of the
The program is designed to estimate the
complexity of the CRC algorithm by the width
of the polynomial using the CRC checksum
method, which is shown in the example of cyclic
redundancy codes. By estimating the
complexity of the implementation of the CRC
algorithm by performing additions according to
the width of the polynomial, we obtain an
approximate number of additions (shift into
cells). This study opens up possible ways to
reduce the computational complexity of the
CRC checksum generation algorithm used to
control the integrity of transmitted data [
For the considered CRC generation method, the "CRC calculation" application was written in Java, presented in Appendix 1, which allows for a user-specified frame size and generating polynomial to estimate the required number of additions and divisions to obtain the final CRC checksum. The javaFX library was used to write the application. The CRC and TableData classes are used from this library. There are three operations in the CRC class: 1. Operation (calculation) - it calculates the CRC code. 2. Operation (initialize). 3. Operation (xor).
sequence array and passes it to the table, the xor operation emulates the operations of logical addition of the bits of the input code and the CRC code to the input and gives two parameters X and Y - a binary code, 1 and 1, or 1 and 0, or 0 and 1, or 0 and 0.
The calculation of the number of additions, which is one of the important components of the CRC algorithm, is carried out in accordance with formula 1. Note that the value obtained as a result of the calculations should not be small, as this will lead to the need to retransmit the data. In this case, the transmission algorithm is repeated, which leads to secondary calculations. Polynomials are chosen so that there is no downtime in the data transmission channels.
The calculation of the number of additions is carried out according to the formula:
= ( ∙ ) mod 2, (1) here R is the number of addition operations modulo 2; P - packet size; N - is the length of the polynomial.
Let us consider an example in which the digit capacity of 8 polynomials has 48 divisions, therefore the number of additions according to the formula (1) R = 48 ∙ 8 = 384. The results of evaluating the computational complexity of the CRC generation algorithm, expressed in the number of operations, are shown using the graph in Fig. 1 and are confirmed a simulation model.
CRC algorithm. It is shown that with an increase in the number of bits of generating polynomials, the number of operations increases, while the number of division operations remains unchanged. With an increase in the number of digits and division operations, the generating polynomials remain unchanged, but the number of additions increases.
It is shown that a possible way to reduce the computational complexity of the CRC checksum generation algorithm used to control the integrity of the transmitted data is to reduce the number of addition operations while maintaining the number of division operations in the algorithm under consideration.
As a result of this work, on the basis of research on generating polynomials and the number of division operations, an expression for calculating the number of addition operations was obtained. The research results pave the way for further research to reduce the computational complexity of the operation of cyclic redundancy codes.
operator "or" is emulated, that is, xor, as shown in Listing 1.
Listing 1: Emulation of the logical operator "or".
original message, that is, a variable that stores a bit sequence of a certain length, as shown in Listing 2.
Listing 2: Variable storing a bit sequence of a certain length.
Next, a polynomial of a certain bit depth is generated and the CRC code is calculated in the calculation method.
The program simulates the process of data transfer between the source and the receiver (Fig. 2), and also provides the following functions: 1. Specifying the initial data in the specified table ("polynomial" and "information frame", Fig. 2) creates a number generator using a unique seed. 2. Calculation of the initial data is displayed in the program window (button "Calculation", Fig. 2). 3. As a result of the initial data, the number of additions and the formation of CRC checksums of cyclic redundancy codes (“parameters and data” field, Fig. 2) is calculated. 4. Additionally, at the discretion of the user, you can reset and start the calculation over again (the "Reset" button, Fig. 2).
After the simulation of the data calculation process, the number of addition of the CRC checksum algorithm of cyclic redundancy codes is calculated again, which are then compared with those previously calculated to reveal the fact of calculating the addition of the checksum algorithm of the transmitted data (Fig. 2); field "CRC calculation".