=Paper=
{{Paper
|id=Vol-2803/paper18
|storemode=property
|title=Investigation of the computational complexity of the
formation of checksums for the Cyclic Redundancy Code
algorithm depending on the width of the generating
polynomial (short paper)
|pdfUrl=https://ceur-ws.org/Vol-2803/paper18.pdf
|volume=Vol-2803
|authors=Odilzhan A. Turdiev,Vladimir A. Smagin,Vladimir N. Kustov
}}
==Investigation of the computational complexity of the
formation of checksums for the Cyclic Redundancy Code
algorithm depending on the width of the generating
polynomial (short paper)==
https://ceur-ws.org/Vol-2803/paper18.pdf
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