Theory and practice of crc codes: new results based on automaton models

Authors

DOI:

https://doi.org/10.15587/1729-4061.2015.47860

Keywords:

CRC codes, shortened cyclic codes, checksum, generator polynomial, linear finite-state machine

Abstract

The theoretical foundations of CRC codes based on the mathematical apparatus of linear finite-state machine (LFSM) were considered.

A mathematical analysis of two interpretations of CRC was performed. Interpretation of CRC as Cyclic Redundancy Check means computing the stream hash function or checksum of the given information message . It is shown that CRC will be an effective hash function (checksum) under the following conditions: CRC generator polynomial must be primitive, of degree  and the message length must be equal to . Cyclic Hamming codes meet such requirements.

Interpretation of CRC as Cyclic Redundancy Code means the search for errors by the rules of shortened cyclic code. Using the automaton-graph model, it is shown that generator polynomials of the Abramson code in the form of , where  is primitive polynomial have the best error detection properties.

Only specified Hamming and Abramson codes are proposed to consider as CRC codes and recommendations for the optimal selection of generator polynomials for them were given.

A method for parallel CRC computation with the reduction in the number of iterations by  () times for a random polynomial of degree  was proposed.

Author Biography

Василий Петрович Семеренко, Vinnytsia National Technical University Khmelnytske shose 95, Vinnytsia, Ukraine, 21021

PhD, Associate Professor

Department of computer technique

References

  1. Stallings, W. (2007). Data and Computer Communications. Eighth Edition. – Upper Saddle River, NJ: Pearson Prentice Hall, 901.
  2. Costello, D. J., Hagenauer, J., Imai, H., Wicker, S. B. (1998). Applications of error-control coding. IEEE Transactions on Information Theory, 44 (6), 2531–2560. doi: 10.1109/18.720548
  3. Cyclic Redundancy Check (CRC) in Stratix Series FPGAs. Published 1995- 2015. Available at: https://www.altera.com/products/general/devices/stratix-fpgas/about/crc.html
  4. Kazakov, P. (2001). Fast calculation of the number of minimum-weight words of CRC codes. IEEE Transactions on Information Theory, 47 (3), 1190–1195. doi: 10.1109/18.915680
  5. Sarwate, D. V. (1988). Computation of cyclic redundancy checks via table look-up. Commun. ACM, 31 (8), 1008–1013. doi: 10.1145/63030.63037
  6. Nguyen G. D. (2009). Fast CRCs. IEEE Trans. on Computers, 58 (10), 1321–1331.
  7. Koopman, P., Chakravarty, T. (2004). Cyclic redundancy code (CRC) polynomial selection for embedded networks. International Conference on Dependable Systems and Networks, 2004, 1–10. doi: 10.1109/dsn.2004.1311885
  8. Baicheva, T. (2008). Determination of the Best CRC Codes with up to 10-Bit Redundancy. IEEE Trans. Commun., 56 (8), 1214–1220. doi: 10.1109/tcomm.2008.070033
  9. Ahmad, A., Hayat, L. (2011). Selection of Polynomials for Cyclic Redundancy Check for the use of High Speed Embedded – An Algorithmic Procedure. IEEE Trans. on Computers, 60 (1), 16–20.
  10. McDaniel, B. (2003). An algorithm for error correcting cyclic redundancy checks. C/C++ Users Journal, 6.
  11. Babaie, S., Zadeh, A. K., Es-hagi, S. H., Navimipour, N. J. (2006). Double bits error correction using CRC method. In Proc. ITS Telecommunications, 6, 254–257.
  12. Mandel, T., Mache, J. (2009). Selected CRC Polynomials Can Correct Errors and Thus Reduce Retransmission. WITS (DCOSS).
  13. Blahut, R. E. (1984). Theory and Practice of Error Control Codes. London: Reading, MA: Addison-Wesley Addison-Wesley Publising Company. (Russ. Ed.: Blejhut R. Teorija i praktika kodov, ispravljajushhih oshibki Moscow: Mir, 1986. 576 p.)
  14. Gill, A. (1967). Linear Sequential Circuits. Analysis, Synthesis and Application. New York, London: McGraw-Hill Book Company. (Russ. Ed.: Gill A. Linejnye Posledovatel'nostnye Mashiny (Linear Sequential Machines). Moscow, USSR: Nauka, 1974. 288.)
  15. Semerenko V. P. (2015). Estimation of the correcting capability of cyclic codes based on their automation models. Eastern-European Journal of Enterprise Technologies, 2/9 (74), 16–24. doi: 10.15587/1729-4061.2015.39947
  16. Impagliazzo, R., Levin, L., Luby, M. (1989). Pseudo-random generation from one-way functions. Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89, 12–24. doi: 10.1145/73007.73009
  17. Hastad, J. (1990). Pseudo-random generators under uniform assumptions. Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90, 395–404. doi: 10.1145/100216.100270
  18. Yarmolnik, V. N. (1988). Kontrol i diagnostika tsifrovyih uzlov EVM [Control and diagnostics of the computer digital units]. Minsk: Nauka i tehnika, 240.
  19. Abramson, N. (1959). A class of systematic codes for non-independent errors. IEEE Transactions on Information Theory, 5 (4), 150–157. doi: 10.1109/tit.1959.1057524
  20. Lin, S., Costello, D. J. (2004). Error-Control Coding: Fundamentals and Applications. Second edition. Upper Saddle River, NJ: Pearson Prentice Hall.
  21. Bogdanov, V. N., Vihlyantsev, P. S., Simonov, M. V. (2002). Zaschita ot oshibok v setyah ATM. [Error protection in ATM networks]. INFORMOST, 3, 20–24.
  22. Semerenko, V. P. (2014). Temporal models of the parallel computing. – Austrian Journal of Technical and Natural Sciences, «East West» Association for Advanced Studies and Higher Education GmbH. Vienna, 1, 13–25. [in Russian]
  23. Semerenko, V. P. (2012). Parallelnoe dekodirovanie ukorochennyih tsiklicheskih kodov [Parallel decoding of the shortened cyclic codes]. Optiko-elektronnyie informatsionno-energeticheskie tehnologii, 1, 30–41. [in Russian]

Downloads

Published

2015-08-21

How to Cite

Семеренко, В. П. (2015). Theory and practice of crc codes: new results based on automaton models. Eastern-European Journal of Enterprise Technologies, 4(9(76), 38–48. https://doi.org/10.15587/1729-4061.2015.47860

Issue

Vol. 4 No. 9(76) (2015): Information and controlling system

Section

Information and controlling system

License

Copyright (c) 2015 Василий Петрович Семеренко

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.