Теорія і практика CRC кодів: нові результати на основі автоматних моделей

Автор(и)

  • Василий Петрович Семеренко Вінницький національний технічний університет Хмельницьке шосе 95, м. Вінниця, 21021, Україна, Україна https://orcid.org/0000-0001-8809-1848

DOI:

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

Ключові слова:

CRC коди, вкорочені циклічні коди, контрольна сума, породжувальний поліном, лінійна послідовнісна схема

Анотація

Розглянуті теоретичні основи кодів CRC за допомогою математичного апарату лінійних послідовнісних схем (ЛПС). Проаналізована інтерпретація CRC як контрольної суми (Cyclic Redundancy Check) та як вкорочених циклічних кодів (Cyclic Redundancy Code). Дані рекомендації з вибору породжувальних поліномів для CRC. Запропоновано метод паралельного обчислення CRC зі скороченням числа ітерацій в  () разів для довільного поліному степені .

Біографія автора

Василий Петрович Семеренко, Вінницький національний технічний університет Хмельницьке шосе 95, м. Вінниця, 21021, Україна

Кандидат технічних наук, доцент

Кафедра обчислювальної техніки

Посилання

  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]

##submission.downloads##

Опубліковано

2015-08-21

Як цитувати

Семеренко, В. П. (2015). Теорія і практика CRC кодів: нові результати на основі автоматних моделей. Eastern-European Journal of Enterprise Technologies, 4(9(76), 38–48. https://doi.org/10.15587/1729-4061.2015.47860

Номер

Том 4 № 9(76) (2015): Інформаційно-керуючі системи

Розділ

Інформаційно-керуючі системи

Ліцензія

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

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.