Результати дослідження коректувальної здатності ітеративних завадостійких кодів

Автор(и)

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

DOI:

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

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

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

Анотація

Проведено дослідження впливу теорії інформації на розвиток теорії завадостійкого кодування. Показані основні відмінності між ймовірнісним та детермінованим підходами при аналізі коректувальної здатності різних класів лінійних кодів.

Розроблені автоматні ієрархічні моделі для аналізу перестановочного декодування циклічних кодів і запропоновано генератор циклічних перестановок на основі двох автоматів Мура.

На основі автоматного представлення циклічних кодів проведено дослідження регулярних і нерегулярних станів лінійних послідовнісних схем (ЛПС). Показана можливість суттєвого спрощення декодування циклічних кодів на основі переведення нерегулярних синдромів ЛПС в регулярні за допомогою перестановок.

Розроблено формалізовані методи визначення коректувальної здатності циклічних кодів, що ітеративно декодуються (ІДЦК). Традиційний повний перебір всіх можливих варіантів порівняння кодових слів замінено направленим пошуком розв’язання поставленої задачі, що призводить до значної економії часу обчислень. Наведено алгоритм визначення коректувальної здатності ІДЦК відносно подвійних помилок.

Показано, що всі ітеративні коди підвищують свою коректувальну здатність зі збільшенням числа ітерацій і її можна задавати у відсотках для помилок різної кратності. Синдроми помилок розподіляються по окремим ітераціям, що дозволяє зменшити розрядність перевіряльного слова коду. В кінцевому результаті це призводить до збільшення швидкості ітеративних кодів в порівнянні з традиційними коректувальними кодами.

Проведено порівняльний аналіз ІДЦК і LDPC-кодів для визначення сфери їх оптимального застосування

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

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

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

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

Посилання

  1. Shennon, K. (1963). Raboty po teorii informacii i kibernetike. Moscow, 829.
  2. Ursul, A. D. (1968). Priroda informacii. Filosofskiy ocherk. Moscow: Politizdat, 288.
  3. Hartley, R. V. L. (1928). Transmission of Information. Bell System Technical Journal, 7 (3), 535–563. doi: https://doi.org/10.1002/j.1538-7305.1928.tb01236.x
  4. Kolmogorov, A. N. (1965). Tri podhoda k opredeleniyu ponyatiya “kolichestvo informacii”. Problemy peredachi informacii, 1 (1), 3–11.
  5. Kolmogorov, A. N. (1987). Teoriya informacii i teoriya algoritmov. Moscow: Nauka, 304.
  6. Bulychev, I. I., Soroka, M. Yu. (2016). About the nature and the essense of information. Noosfernye issledovaniya, 1-2 (13-14), 191–207.
  7. Piterson, U., Ueldon, E. (1976). Kody, ispravlyayushchie oshibki. Moscow: Mir, 596.
  8. Sklyar, B. (2004). Cifrovaya svyaz'. Teoreticheskie osnovy i prakticheskoe primenenie. Moscow: Izd. dom «Vil'yams», 1104.
  9. Klark, Dzh. ml., Keyn, Dzh. (1987). Kodirovanie s ispravleniem oshibok v sistemah cifrovoy svyazi. Moscow: Radio i svyaz', 392.
  10. Dumer, I., Micciancio, D., Sudan, M. (2003). Hardness of approximating the minimum distance of a linear code. IEEE Transactions on Information Theory, 49 (1), 22–37. doi: https://doi.org/10.1109/tit.2002.806118
  11. Semerenko, V. (2018). Iterative hard­-decision decoding of combined cyclic codes. Eastern-European Journal of Enterprise Technologies, 1 (9 (91)), 61–72. doi: https://doi.org/10.15587/1729-4061.2018.123207
  12. Garrammone, G., Declercq, D., Fossorier, M. P. C. (2017). Weight Distributions of Non-Binary Multi-Edge Type LDPC Code Ensembles: Analysis and Efficient Evaluation. IEEE Transactions on Information Theory, 63 (3), 1463–1475. doi: https://doi.org/10.1109/tit.2016.2647724
  13. Liu, L., Huang, J., Zhou, W., Zhou, S. (2012). Computing the Minimum Distance of Nonbinary LDPC Codes. IEEE Transactions on Communications, 60 (7), 1753–1758. doi: https://doi.org/10.1109/tcomm.2012.050812.110073a
  14. Uryvskiy, L. A., Osipchuk, S. A.; Bezruk, V. M., Barannik, V. V. (Eds.) (2017). Issledovanie svoystv pomekhoustoychivyh kodov klassa LDPC. Naukoemkie tekhnologii v infokommunikaciyah: obrabotka informacii, kiberbezopasnost', informacionnaya bor'ba. Kharkiv, 137–139.
  15. Tomlinson, M., Tjhai, C. J., Ambroze, M. A., Ahmed, M., Jibril, M. (2017). Error-Correction Coding and Decoding. Bounds, Codes, Decoders, Analysis and Applications. Springer. doi: https://doi.org/10.1007/978-3-319-51103-0
  16. Bocharova, I. E., Kudryashov, B. D., Skachek, V., Yakimenka, Y. (2017). Distance Properties of Short LDPC Codes and Their Impact on the BP, ML and Near-ML Decoding Performance. Lecture Notes in Computer Science, 48–61. doi: https://doi.org/10.1007/978-3-319-66278-7_5
  17. Butler, B. K., Siegel, P. H. (2014). Error Floor Approximation for LDPC Codes in the AWGN Channel. IEEE Transactions on Information Theory, 60 (12), 7416–7441. doi: https://doi.org/10.1109/tit.2014.2363832
  18. Berlekemp, E. (1971). Algebraicheskaya teoriya kodirovaniya. Moscow: Mir, 477.
  19. Semerenko, V. P. (2009). Burst-Error Correction for Cyclic Codes. IEEE EUROCON 2009. doi: https://doi.org/10.1109/eurcon.2009.5167864
  20. Semerenko, V. P. (1998). Parallel Decoding of Bose-Chaudhuri-Hocquenghem Codes. Engineering Simulation, 16 (1), 87–100.
  21. Semerenko, V. P. (2015). Teoriya tsyklichnykh kodiv na osnovi avtomatnykh modelei. Vinnytsia: VNTU, 444.
  22. Gallager, R. (1966). Kody s maloy plotnost'yu proverok na chetnost'. Moscow: Mir, 144.
  23. 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: https://doi.org/10.15587/1729-4061.2015.39947

##submission.downloads##

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

2019-02-21

Як цитувати

Semerenko, V. (2019). Результати дослідження коректувальної здатності ітеративних завадостійких кодів. Eastern-European Journal of Enterprise Technologies, 1(4), 31–39. https://doi.org/10.15587/1729-4061.2019.157299

Номер

Том 1 № 4 (2019): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2019 Vasyl Semerenko

Creative Commons License

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

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

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