Представлення кодів Ріда-Соломона за допомогою теорії автоматів
DOI:
https://doi.org/10.15587/2706-5448.2020.210272Ключові слова:
коди Ріда-Соломона, теорія автоматів, лінійна послідовнісна схема (ЛПС), декодування, квантовий комп’ютер.Анотація
Об’єктом дослідження є процеси завадостійкого кодування в телекомунікаційних та комп’ютерних системах. Основну увагу звернуто на коди Ріда-Соломона, які належать до найпоширеніших завадостійких кодів. Незважаючи на 60-річний період існування цих кодів, поки що залишається проблемою складність їх декодування. Ця проблема обумовлена головним чином використанням алгебраїчного підходу до їх опису.
В роботі запропоновано використати для кодів Ріда-Соломона у якості математичної основи теорію лінійних послідовнісних схем, яка є поєднанням теорії цифрових фільтрів та скінчених автоматів в недвійкових полях Галуа. В ході досліджень вперше розглядаються 12 типів лінійних послідовнісних схем: 8 типів рекурсивних лінійних послідовнісних схем і 4 типи нерекурсивних лінійних послідовнісних схем. Рекурсивні лінійні послідовнісні схеми використовуються для систематичного кодування та утворюють схему для ділення поліномів, а нерекурсивні лінійні послідовнісні схеми – для несистематичного кодування та утворюють схему для множення поліномів. Всі типи лінійних послідовнісних схем дають однаковий результат при кодуванні та декодуванні, але з різною трудомісткістю, що важливо для практичної реалізації.
Автоматне представлення є найбільш придатним для кодів Ріда-Соломона, оскільки максимально враховує властивість циклічності та інші особливості цих кодів. На відміну від алгебраїчних методів автоматні методи декодування мають просту програмно-апаратну реалізацію та високу швидкодію. За допомогою автоматно-графових моделей можна точно оцінити коректувальну здатність коду. Автоматне представлення об’єднує відомі способи представлення кодів Ріда-Соломона (поліноміальне, матричне, алгебраїчне) та забезпечує взаємні переходи між ними.
В роботі звернуто увагу, що автоматні методи кодування та декодування (n,k)-кодів Ріда-Соломона за допомогою квантових комп’ютерів дають виграш в часі в n разів.
Посилання
- Luzhetskyi, V. Semerenko, V. (2019). Automaton Presentations of Reed-Solomon Codes. Advanced Information and Communication Technologies. Lviv, 50–53. doi: http://doi.org/10.1109/aiact.2019.8847892
- Sklar, B. (2001). Digital Communications. Fundamentals and Applications. Los Angeles: Prentice Hall PTR.
- Morelos-Zaragosa, R. H. (2002). The Art of Error Correcting Coding. Jon Wiley & Sons. doi: http://doi.org/10.1002/0470847824
- Semerenko, V. (2018). Automaton Presentations of Cyclic Codes. Herald of Vinnytsia Polytechnical Institute, 2 (137), 89–100.
- Ifeachor, E. C., Jervis, B. W. (2002). Digital Signal Proccesing. A practical Approach. Los Angeles: Prentice Hall, 925.
- Friedland, B. (1959). Linear Modular Sequential Circuits. IRE Transactions on Circuit Theory, 6 (1), 61–68. doi: http://doi.org/10.1109/tct.1959.1086529
- Gill, A. (1967). Linear Sequential Circuits. Analysis, Synthesis and Application. New York, London: McGraw-Hill Book Company, 215.
- Milovanovic, E., Stojcev, M., Milovanovic, I., Nikolic, T. (2015). Concurrent Generation of Pseudo Random Numbers with LFSR of Fibonacci and Galois Type. Computing and Informatics, 34, 941–958.
- Semerenko, V. P. (2011). Dekodirovanie kodov Rida-Solomona na osnove grafovoi i avtomatnoi modelei. Elektronnoe modelirovanie, 1, 57–72.
- Solovyev, V. M. (2015). Quantum Computers and Quantum Algorithms. Part 1. Quantum Computers. Izvestiya of Saratov University. New Series. Series: Mathematics. Mechanics. Informatics, 15 (4), 462–477. doi: http://doi.org/10.18500/1816-9791-2015-15-4-462-477
- Calderbank, A. R., Rains, E. M., Shor, P. M., Sloane, N. J. A. (1998). Quantum error correction via codes over GF(4). IEEE Transactions on Information Theory, 44 (4), 1369–1387. doi: http://doi.org/10.1109/18.681315
- Häffner, H., Hänsel, W., Roos, C. F., Benhelm, J., Chek-al-kar, D., Chwalla, M. et. al. (2005). Scalable multiparticle entanglement of trapped ions. Nature, 438 (7068), 643–646. doi: http://doi.org/10.1038/nature04279
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Vasyl Semerenko
![Creative Commons License](http://i.creativecommons.org/l/by/4.0/88x31.png)
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.