Presentation of Reed-Solomon codes based on automaton theory

Vasyl Semerenko

doi:10.15587/2706-5448.2020.210272

Автор(и)

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

DOI:

https://doi.org/10.15587/2706-5448.2020.210272

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

коди Ріда-Соломона, теорія автоматів, лінійна послідовнісна схема (ЛПС), декодування, квантовий комп’ютер.

Анотація

Об’єктом дослідження є процеси завадостійкого кодування в телекомунікаційних та комп’ютерних системах. Основну увагу звернуто на коди Ріда-Соломона, які належать до найпоширеніших завадостійких кодів. Незважаючи на 60-річний період існування цих кодів, поки що залишається проблемою складність їх декодування. Ця проблема обумовлена головним чином використанням алгебраїчного підходу до їх опису.

В роботі запропоновано використати для кодів Ріда-Соломона у якості математичної основи теорію лінійних послідовнісних схем, яка є поєднанням теорії цифрових фільтрів та скінчених автоматів в недвійкових полях Галуа. В ході досліджень вперше розглядаються 12 типів лінійних послідовнісних схем: 8 типів рекурсивних лінійних послідовнісних схем і 4 типи нерекурсивних лінійних послідовнісних схем. Рекурсивні лінійні послідовнісні схеми використовуються для систематичного кодування та утворюють схему для ділення поліномів, а нерекурсивні лінійні послідовнісні схеми – для несистематичного кодування та утворюють схему для множення поліномів. Всі типи лінійних послідовнісних схем дають однаковий результат при кодуванні та декодуванні, але з різною трудомісткістю, що важливо для практичної реалізації.

Автоматне представлення є найбільш придатним для кодів Ріда-Соломона, оскільки максимально враховує властивість циклічності та інші особливості цих кодів. На відміну від алгебраїчних методів автоматні методи декодування мають просту програмно-апаратну реалізацію та високу швидкодію. За допомогою автоматно-графових моделей можна точно оцінити коректувальну здатність коду. Автоматне представлення об’єднує відомі способи представлення кодів Ріда-Соломона (поліноміальне, матричне, алгебраїчне) та забезпечує взаємні переходи між ними.

В роботі звернуто увагу, що автоматні методи кодування та декодування (n,k)-кодів Ріда-Соломона за допомогою квантових комп’ютерів дають виграш в часі в n разів.

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

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

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

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

Посилання

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