Інтеграція засобів спрощення обчислень в завадостійкому кодуванні
DOI:
https://doi.org/10.15587/2706-5448.2021.233656Ключові слова:
циклічні коди, NP-повнота задач, складність обчислень, циклічна перестановка, ітеративне декодуванняАнотація
Об’єктом дослідження є процеси завадостійкого перетворення інформації в автоматизованих системах. Дослідження направлене на зменшення складності декодування циклічних кодів за допомогою об’єднання сучасних математичних моделей та практичних засобів. Основною передумовою ускладнення обчислень в детермінованих лінійних завадостійких кодах стало використання алгебраїчного представлення як основного математичного апарату для цих типів кодів. Незважаючи на універсалізм алгебраїчного підходу, його основним недоліком є неможливість врахування характерних особливостей всіх підкласів лінійних кодів. Зокрема, для циклічних кодів зовсім не враховується властивість циклічності. При врахуванні вказаної властивості можна перейти до принципово іншого математичного представлення циклічних кодів – теорії лінійних автоматів в полях Галуа (лінійних послідовнісних схем).
Для автоматного представлення циклічних кодів доведено, що задача синдромного декодування цих кодів в загальному випадку є NP-повною задачею. Однак, якщо використати запропонований ієрархічний підхід до задач складності, тоді на його основі можна здійснити більш точний аналіз зростання складності обчислень. Виправлення поодиноких помилок протягом одного часового інтервалу (одної ітерації) декодування має лінійну складність декодування від довжини кодового слова, а виправлення помилок протягом m ітерацій перестановок розрядів кодового слова – поліноміальну складність. Відповідно виділені три підкласи циклічних кодів в залежності від складності їх декодування: легкодекодовані (лінійної складності), ітеративно декодовані (поліноміальної складності), складнодекодовані (експоненціальної складності). Розглянуті практичні способи зменшення складності обчислень: почергове використання ймовірнісних та детермінованих лінійних кодів, спрощення програмно-апаратної реалізації за рахунок збільшення часу декодування, використання перемежування. Запропоновано спосіб перемежування, який дозволяє одночасно як формувати пакети помилок, так і заміняти їх поодинокими помилками. Математичний апарат лінійних автоматів дозволяє інтегрувати та розв’язувати разом вказані задачі завадостійкого кодування.
Посилання
- Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27 (3), 379–423. doi: http://doi.org/10.1002/j.1538-7305.1948.tb01338.x
- Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27 (4), 623–656. doi: http://doi.org/10.1002/j.1538-7305.1948.tb01338.x
- 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: http://doi.org/10.1109/18.720548
- Morelos-Zaragosa, R. H. (2002). The Art of Error Correcting Coding. Jon Wiley & Sons, 278. doi: http://doi.org/10.1002/0470847824
- Berlekamp, E., McEliece, R., van Tilborg, H. (1978). On the inherent intractability of certain coding problems (Corresp.). IEEE Transactions on Information Theory, 24 (3), 384–386. doi: http://doi.org/10.1109/tit.1978.1055873
- Melentev, O. G. (2007). Teoreticheskie aspektyi peredachi dannyih po kanalam s gruppiruyuschimisya oshibkami. Moscow: Goryachaya liniya–Telekom, 232.
- Vardy, A. (1997). The intractability of computing the minimum distance of a code. IEEE Transactions on Information Theory, 43 (6), 1757–1766. doi: http://doi.org/10.1109/18.641542
- 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: http://doi.org/10.15587/1729-4061.2015.39947
- Cormen, Т. H., Leiserson, C. E., Rivest R. L., Stain C. (2014). Introduction to Algorithms. London: The MIT Press, 1183.
- Semerenko, V. (2016). The theory of parallel crc codes based on automaton models. Eastern-European Journal of Enterprise Technologies, 6 (9 (84)), 45–55. doi: http://doi.org/10.15587/1729-4061.2016.85603
- Forney, G. D. (1967). Concatenated Codes. Cambridge: MIT Press.
- Wei, Y., Jiang, M., Xia, B., Chen, W., Yang, Y. (2013). A CRC-Aided Hybrid Decoding Algorithm for Turbo Codes. IEEE Wireless Communications Letters, 2 (5), 471–474. doi: http://doi.org/10.1109/wcl.2013.052813.130259
- Aho, A. V., Hopcroft, J. T., Ullman, J. D. (1976). The Design and Analysis of computer Algorithms. Addison-Wesley Publishing Company Reading.
- Semerenko, V. (2018). Iterative hard-decision decoding of combined cyclic codes. Eastern-European Journal of Enterprise Technologies, 1 (9 (91)), 61–72. doi: http://doi.org/10.15587/1729-4061.2018.123207
- Prange, E. (1962). The use of information sets in decoding cyclic codes. IEEE Transactions on Information Theory, 8 (5), 5–9. doi: http://doi.org/10.1109/tit.1962.1057777
- Clark, G. C. Jr., Cain, J. B. (1981). Error-Correction for Digital Communications. New York and London: Plenum Press, 422. doi: http://doi.org/10.1007/978-1-4899-2174-1
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2021 Vasyl Semerenko, Oleksandr Voinalovich
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
