Investigation of the computational complexity of the formation of checksums for the Cyclic Redundancy Code algorithm depending on the width of the generating polynomial Odilzhan A. Turdiev a, Vladimir A. Smagin b and Vladimir N. Kustov a a Petersburg State Transport University, 9 Moskovsky pr, Saint Petersburg, 190031, Russian Federation b International Academy of Informatization St. Petersburg, Saint Petersburg, 190031, Russian Federation Abstract 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. Keywords computational complexity, generator polynomial, cyclic redundancy code, CRC, burst errors, bit errors, data integrity. 1. Introduction The CRC algorithm is based on the theory of cyclic error correction codes. This algorithm One of the important tasks in modern was first proposed by V.V. Peterson and D.T. communication networks is to ensure data Brown, in [1]. The CRC algorithm computes a integrity. The most common algorithm for short binary sequence that has a certain constant determining the integrity of transmitted data is the length, known as a check value or CRC algorithm CRC (Cyclic Redundancy Check) algorithm. 1. code. The CRC is calculated for each individual block of data to be transmitted over the network and added to the block to form a codeword. When Models and Methods for Researching Information Systems in Transport, Dec. 11-12, St. Petersburg, Russia a codeword is received on the receiving side, one EMAIL: odiljan.turdiev@mail.ru (O.A. Turdiev); of two things is done. Either the received CRC va_smagin@mail.ru (V.A. Smagin). ORCID: 0000-0002-1651-5493 (O.A. Turdiev). check value is compared with the value of the ©️ 2020 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CRC that is generated anew for the transmitted CEUR Workshop Proceedings (CEUR- data on the receiving side, or the CRC is generated WS.org) again on the receiving side for the entire received 129 codeword and the resulting CRC check value is To find ways to reduce the computational compared with the expected residual constant. If complexity in the work, a study of the the control values do not match, then the computational complexity of the formation of transmitted data contains an error and the CRC checksums was carried out depending on receiving device can take actions to correct them, various generating polynomials and their bit such as re-reading the block or sending it again. width. To assess the computational complexity of The theoretical provisions of the functioning the CRC, we simulated the process of transmitting of the CRC algorithm are given in [2-5]. It is binary data over a symmetric channel. assumed that when a data block and its check CRC are received correctly, integrity is ensured for that 2. Basic concepts and data block. The process of generating and characteristics of CRC codes checking the CRC can be quite laborious when using network devices with low speed or high data Cyclic redundancy codes CRC are a transfer rates. In this regard, reducing the subclass of block codes and are used in HDLC, computational complexity of the CRC algorithm is Token Ring, Token Bus protocols, Ethernet an urgent scientific and practical task. protocol families and other link layer protocols In addition, in real transmission conditions, [8]. Computing resources mean memory, the communication channel can be affected by processor power, and the number of shift registers. various kinds of interference, which appear in the One of the ways to represent a cyclic code is to process under study in the form of erroneous bits, represent it in the form of a generating polynomial which lead to a violation of data integrity [6]. In - the set of all polynomials of degree (r – code-1), the work of V.V. Yakovlev [7] proposed the containing some fixed polynomial G (x) as a choice of the generating polynomial to increase common factor. The polynomial G (x) is called the the probability of error recognition when generating polynomial of the code. For example, generating checksums in the transmitted data. π‘₯ 4 + π‘₯ +1, here r-code = 5, since the binary Summarizing the above, it can be noted that sequence looks like 10011. The standardized and the purpose of the work is to perform search recommended generator polynomials for the CRC studies to substantiate the fundamental possibility algorithm are given in Table 1, where the name of and possible ways to reduce the computational the standard and the generator polynomial are complexity of the CRC checksum generation shown: for example, the notation π‘₯ 4 + π‘₯ + 1 is algorithm used to control the integrity of the transmitted data. equivalent to 1βˆ™ π‘₯ 4 + 0βˆ™ π‘₯ 3 + 0βˆ™ π‘₯ 2 + 1βˆ™π‘₯ + 1βˆ™ π‘₯ 0 = 10011 (in binary). Table 1. Popular standardized generator polynomials [9]. nomination Generating polynomials 4 CRC-4-TU π‘₯ + π‘₯ + 1 (ITU G.704) CRC-5-EPC π‘₯ 5 + π‘₯ 3 + 1 (Gen 2 RFID) CRC-5-ITU π‘₯ 5 + π‘₯ 4 + π‘₯ 2 + 1 (ITU G.704) CRC-5-USB π‘₯ 5 + π‘₯ 2 + 1 (USB token packets) CRC-6-ITU π‘₯ 6 + π‘₯ + 1 (ITU G.704) CRC-7 π‘₯ 7 + π‘₯ 3 + 1 (ITU-T G.707, ITU-T G.832, MMC, SD) CRC-8-CCITT π‘₯ 8 + π‘₯ 2 + π‘₯ + 1 (ATM HEC), ISDN Header Error Control and Cell Delineation ITU-T I.432.1 (02/99) CRC-8-Dallas/Maxim π‘₯ 8 + π‘₯ 5 + π‘₯ 4 + 1 (1-Wire bus) CRC-8 π‘₯ 8 + π‘₯ 7 + π‘₯ 6 + π‘₯ 4 + π‘₯ 2 + 1 (ETSI EN 302 307, 5.1.4) CRC-8-SAE J1850 π‘₯8 + π‘₯4 + π‘₯3 + π‘₯2 + 1 CRC-10 π‘₯10 + π‘₯ 9 + π‘₯ 5 + π‘₯ 4 + π‘₯ + 1 CRC-11 π‘₯ + π‘₯ 9 + π‘₯ 8 + π‘₯ 7 + π‘₯ 2 + 1 (FlexRay) 11 CRC-12 π‘₯12 + π‘₯11 + π‘₯ 3 + π‘₯ 2 + π‘₯ + 1 (систСмы Ρ‚Π΅Π»Π΅ΠΊΠΎΠΌΠΌΡƒΠ½ΠΈΠΊΠ°Ρ†ΠΈΠΈ) 130 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 The value of the result of the The use of polynomial codes during implementation of the CRC algorithm is the transmission is as follows. The sender and the remainder of dividing the binary sequence M (x) receiver pre-select the same generator corresponding to the input data by the generating polynomial G (x), whose coefficients at the binary sequence G (x) of degree r. higher term and at the lower term must be equal Each final sequence of bits is one-to-one to 1. When calculating the checksums of a block associated with a binary polynomial, the of m bits in size, the following condition m > r sequence of which is the original sequence. For must be met. Further, implementing the CRC example, bit sequence 1011010 corresponds to calculation algorithm, the sender adds the 6 5 checksum to the transmitted block, considered as the binary polynomial M(x) = 1Β· x + 0Β· x + 1Β· a polynomial M (x), so that the transmitted block x4 + 1Β· x3 + 0Β· x2 + 1Β· x1 + 0Β· x0 = x6 + with the checksum is a multiple of G (x). When x4 + x3 + x. the recipient receives the checksum block, he divides it by G (x). If a nonzero remainder is Let's consider examples in which addition formed, then this indicates the occurrence of an and subtraction are performed without carrying error during transmission [10,11]. the digits in accordance with the "exclusive OR" Checksum calculation algorithm: operation, which corresponds to the addition 1. Add r zeros to the end of the block so that it modulo 2 of binary arithmetic. 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 Polynomial division is performed in the with a checksum. binary system, with the difference that the subtraction is performed modulo 2. 131 Currently, most network technologies most often use the following three types of Thus, the example shows that with the generating polynomials G (x) [12]: generator polynomial CRC-4-TU (10011) and CRC-12 = π‘₯12 + π‘₯11 + π‘₯ 3 + π‘₯ 2 + π‘₯ + 1 the bit length of the information frame equal to CRC-16-IBM = π‘₯16 + π‘₯15 + π‘₯ 2 + 1 10 bits, 10 divisions and 50 modulo 2 additions CRC-16-CCITT = π‘₯16 + π‘₯12 + π‘₯ 5 + 1 are required. In the general case, the relationship CRC-12 is used to transmit 6-bit between the computational complexity (the characters. The other two are for 8-bit. CRC-16 number of additions and divisions), the size of and CRC-CCITT detect all single and all double the generating polynomial and the size of the errors, an odd number of isolated errors, single information polynomial. bursts of errors less than 16 in length, and many For the best understanding of the number burst errors greater than 16 with a 99.997% of divisions and additions in the CRC algorithm probability. with various generator polynomials and After getting acquainted with the basic information frames, software has been created to concepts and characteristics of CRC codes, let assess the computational complexity of the CRC us consider an example of calculating the algorithm. remainder of cyclic redundancy codes and estimate the computational complexity of this 4. A program for evaluating the process. computational complexity of the CRC algorithm 3. An example of calculating the remainder for constructing a CRC The program is designed to estimate the code word and estimating the complexity of the CRC algorithm by the width of the polynomial using the CRC checksum computational complexity method, which is shown in the example of cyclic redundancy codes. By estimating the Calculation of CRC. Information frame - 1101011011 complexity of the implementation of the CRC algorithm by performing additions according to Generator polynomial - 10011 Frame with additional zeros – 11010110110000 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 [16,17]. 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). CRC codeword (transmitted frame) - 3. Operation (xor). 11010110111110 [13-15]. 132 The initialize operation processes the bit Figure 1: The result of evaluating the sequence array and passes it to the table, the xor computational complexity of the CRC operation emulates the operations of logical generation algorithm, expressed in the number addition of the bits of the input code and the of operations. CRC code to the input and gives two parameters X and Y - a binary code, 1 and 1, or 1 and 0, or Conclusions 0 and 1, or 0 and 0. The article investigates the computational 5. Analysis of the results of CRC algorithm. It is shown that with an increase evaluating the computational in the number of bits of generating polynomials, complexity of the CRC algorithm the number of operations increases, while the number of division operations remains The calculation of the number of unchanged. With an increase in the number of additions, which is one of the important digits and division operations, the generating components of the CRC algorithm, is carried out polynomials remain unchanged, but the number in accordance with formula 1. Note that the of additions increases. value obtained as a result of the calculations It is shown that a possible way to reduce should not be small, as this will lead to the need the computational complexity of the CRC to retransmit the data. In this case, the checksum generation algorithm used to control transmission algorithm is repeated, which leads the integrity of the transmitted data is to reduce to secondary calculations. Polynomials are the number of addition operations while chosen so that there is no downtime in the data maintaining the number of division operations in transmission channels. the algorithm under consideration. The calculation of the number of additions As a result of this work, on the basis of is carried out according to the formula: research on generating polynomials and the number of division operations, an expression for 𝑅 = (𝑃 βˆ™ 𝑁) mod 2, (1) calculating the number of addition operations here R is the number of addition operations was obtained. The research results pave the way modulo 2; for further research to reduce the computational P - packet size; complexity of the operation of cyclic N - is the length of the polynomial. redundancy codes. Let us consider an example in which the digit capacity of 8 polynomials has 48 divisions, Appendix 1. therefore the number of additions according to the formula (1) R = 48 βˆ™ 8 = 384. The results of By the logic of the method, the logical evaluating the computational complexity of the operator "or" is emulated, that is, xor, as shown CRC generation algorithm, expressed in the in Listing 1. number of operations, are shown using the graph in Fig. 1 and are confirmed a simulation model. Listing 1: Emulation of the logical operator "or". The CRC class contains fields with the original message, that is, a variable that stores a 133 bit sequence of a certain length, as shown in Listing 2. References [1] Peterson, W. W. and Brown, D. T. (January 1961). "Cyclic Codes for Error Listing 2: Variable storing a bit sequence of a Detection". Proceedings of the IRE 49: certain length. 228. [2] Ritter, Terry (February 1986). "The Great Next, a polynomial of a certain bit depth is CRC Mystery". Dr. Dobb's Journal 11 (2): generated and the CRC code is calculated in the http://www.ciphersbyritter.com/ARTS/CR calculation method. CMYST.HTM. Retrieved 21 May 2009 The program simulates the process of data 26–34, 76–83. transfer between the source and the receiver [3] N. Cam-Winget, Nancy; R. Housley, (Fig. 2), and also provides the following Russ; D. Wagner, David; J. Walker, Jesse functions: (May 2003). "Security Flaws in 802.11 1. Specifying the initial data in the specified Data Link Protocols". Communications of table ("polynomial" and "information frame", the ACM 46 (5): 35–39. Fig. 2) creates a number generator using a [4] Stigge, Martin; PlΓΆtz, Henryk; MΓΌller, unique seed. Wolf; Redlich, Jens-Peter (May 2006). 2. Calculation of the initial data is displayed in Reversing CRC – Theory and Practice the program window (button "Calculation", Fig. (http://sar.informatik.hu- 2). berlin.de/research/publications/SAR-PR- 3. As a result of the initial data, the number of 2006-05/SAR-PR-2006-05_.pdf). Berlin: additions and the formation of CRC checksums Humboldt University Berlin. p. 17. of cyclic redundancy codes (β€œparameters and Retrieved 4 February 2011 data” field, Fig. 2) is calculated. [5] Anachriz (30 April 1999). "CRC and how 4. Additionally, at the discretion of the user, you to Reverse it" Retrieved 21 January 2010. can reset and start the calculation over again (the Online essay with example x86 assembly "Reset" button, Fig. 2). code. [6] "Eurocontrol – FAQ: Technologies" (http://www.eurocontrol.int/aim/public/fa q/chain faq3.html). European Organisation for the Safety of Air Navigation. 29 April 2009. [7] Yakovlev V.V., Fedorov R.F. Stochastic computers. L., "Mechanical Engineering", 1974, [8] Ross N. Williams Π­Π»Π΅ΠΌΠ΅Π½Ρ‚Π°Ρ€Π½ΠΎΠ΅ руководство ΠΏΠΎ CRC – Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°ΠΌ Figure 2: CRC calculation. обнаруТСния ошибок. Copyright (C) Ross Williams, 1993 After the simulation of the data [9] Cyclic redundant code [Electronic resource]. - Internet page. - Access mode: calculation process, the number of addition of https://ru.wikipedia.org/wiki/Cyclic_Redu the CRC checksum algorithm of cyclic ndant_code, free redundancy codes is calculated again, which are [10] Yakovlev VV Assessment of the influence then compared with those previously calculated of interference on the performance of the to reveal the fact of calculating the addition of channel level protocols / VV Yakovlev, FI the checksum algorithm of the transmitted data Kushnazarov // Izv. Petersburg. state un- (Fig. 2); field "CRC calculation". that ways of communication. - SPb .: 134 PGUPS, 2015. - Issue. 1 (42). - S. 133- 138. [11] Halsall F. Fifth edition, computer networks and the Internet / F. Halsall. – Addison-Wesley: Pearson Education, 2005. β€’ 803 Ρ€. [12] Lin S. and Costello D.J. Jr. Error Control Coding: Fundamentals and Applications. Prentice-Hall, Inc., EnglewoodCliffs, N. J., 1983. [13] Halsall F. Data communications, computer networks and open systems / F. Halsall. – Addison-Wesley: Pearson Education, 1996. β€’ 907 Ρ€. [14] Olifer V. G. Computer networks. Principles, technologies, protocols / V. G. Olifer, N. A. Olifer. - SPb .: Peter, 2008 .- - 958 p. [15] A. Romashchenko, A. Rumyantsev, A. Shen. NOTES ON THE THEORY OF CODING. Notes on coding theory. | 2nd ed., Rev. and add. | M .: MTsNMO, 2017. | 88 p. ISBN 978-5-4439-0689-8 [16] Turdiev O.A., Yakovlev V.V., Klimenko S.V., Boltaev A.Kh. Investigation of the formation of the block checksum (BCC) of the transmitted data. Izvestia ETU "LETI" Issue No. 6 2019. [17] Turdiev O.A., Klimenko S.V., Tukhtakhodzhaev A.B. Evaluations of the efficiency of detecting checksum errors (CRC) of transmitted data Izvestia ETU "LETI" Issue No. 8 2019. 135