Представлення кодів Ріда-Соломона за допомогою теорії автоматів

Autor: Semerenko, Vasyl
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Zdroj: Technology audit and production reserves; Том 4, № 2(54) (2020): Information and control systems; 31-35
Technology audit and production reserves; Том 4, № 2(54) (2020): Інформаційно-керуючі системи; 31-35
Technology audit and production reserves; Том 4, № 2(54) (2020): Информационно-управляющие системы; 31-35
ISSN: 2664-9969
2706-5448
Popis: The object of research is the processes of error-correcting coding in telecommunication and computer systems. The main attention is paid to Reed-Solomon codes, which belong to the very widespread error-correcting codes. Despite the 60-year existence of these codes, the complexity of their decoding still remains a problem. This problem is mainly due to the use of an algebraic approach to their description.The article proposes to use the theory of linear finite-state machine (LFSM) for RS codes as a mathematical basis, which is a combination of the theory of digital filters and finite automaton over nonbinary Galois fields. In the course of research, 12 types of LFSMs are considered for the first time: the recursive LFSMs of 8 types and the non-recursive LFSMs of 4 types.The recursive LFSMs are used for systematic encoding and form a circuit for dividing of polynomials, and the non-recursive LFSMs are used for non-systematic encoding and form a circuit for multiplying of polynomials. All types of LFSMs give the same result for encoding and decoding, but with different complexity, which is important for practical implementation.The automaton representation is the most suitable for PC codes, since it takes into account the cyclicity property and other features of these codes to the maximum. In contrast to algebraic methods, automaton decoding methods have a simple software and hardware implementation and high performance. With the help of automaton-graphical models, it can accurately estimate the corrective capability of the code. Automaton representation combines known methods of representing Reed-Solomon codes (polynomial, matrix, algebraic) and provides mutual transitions between them.The article attention is spare to the fact that automaton methods for encoding and decoding (n, k)-codes of RS using quantum computers give a gain in time n times.
Объектом исследования являются процессы помехоустойчивого кодирования в телекоммуникационных и компьютерных системах. Основное внимание обращено на коды Рида-Соломона, которые принадлежат к очень распространенным помехоустойчивым кодам. Несмотря на 60-летний период существования этих кодов, пока остается проблемой сложность их декодирования. Эта проблема обусловлена главным образом использованием алгебраического подхода к их описанию.В работе предложено использовать для кодов Рида-Соломона в качестве математической основы теорию линейных последовательностных схем, которая представляет собой сочетание теории цифровых фильтров и конечных автоматов в недвоичных полях Галуа. В ходе исследований впервые рассматриваются 12 типов линейных последовательностных схем: 8 типов рекурсивных линейных последовательностных схем и 4 типа нерекурсивных линейных последовательностных схем. Рекурсивные линейные последовательностные схемы используются для систематического кодирования и образуют схему для деления полиномов, а нерекурсивные линейные последовательностные схемы – для несистематического кодирования и образуют схему для умножения полиномов. Все типы линейных последовательностных схем дают одинаковый результат при кодировании и декодировании, но с различной трудоемкостью, что важно для практической реализации.Автоматное представление является наиболее пригодным для кодов Рида-Соломона, поскольку максимально учитывает свойство цикличности и другие особенности этих кодов. В отличие от алгебраических методов автоматные методы декодирования имеют простую программно-аппаратную реализацию и высокое быстродействие. C помощью автоматно-графовых моделей можно точно оценить корректирующую способность кода. Автоматное представление объединяет известные способы представления кодов Рида-Соломона (полиномиальное, матричное, алгебраическое) и обеспечивает взаимные переходы между ними.В работе обращено внимание, что автоматные методы кодирования и декодирования (n,k)-кодов Рида-Соломона с помощью квантовых компьютеров дают выигрыш во времени в n раз.
Об’єктом дослідження є процеси завадостійкого кодування в телекомунікаційних та комп’ютерних системах. Основну увагу звернуто на коди Ріда-Соломона, які належать до найпоширеніших завадостійких кодів. Незважаючи на 60-річний період існування цих кодів, поки що залишається проблемою складність їх декодування. Ця проблема обумовлена головним чином використанням алгебраїчного підходу до їх опису.В роботі запропоновано використати для кодів Ріда-Соломона у якості математичної основи теорію лінійних послідовнісних схем, яка є поєднанням теорії цифрових фільтрів та скінчених автоматів в недвійкових полях Галуа. В ході досліджень вперше розглядаються 12 типів лінійних послідовнісних схем: 8 типів рекурсивних лінійних послідовнісних схем і 4 типи нерекурсивних лінійних послідовнісних схем. Рекурсивні лінійні послідовнісні схеми використовуються для систематичного кодування та утворюють схему для ділення поліномів, а нерекурсивні лінійні послідовнісні схеми – для несистематичного кодування та утворюють схему для множення поліномів. Всі типи лінійних послідовнісних схем дають однаковий результат при кодуванні та декодуванні, але з різною трудомісткістю, що важливо для практичної реалізації.Автоматне представлення є найбільш придатним для кодів Ріда-Соломона, оскільки максимально враховує властивість циклічності та інші особливості цих кодів. На відміну від алгебраїчних методів автоматні методи декодування мають просту програмно-апаратну реалізацію та високу швидкодію. За допомогою автоматно-графових моделей можна точно оцінити коректувальну здатність коду. Автоматне представлення об’єднує відомі способи представлення кодів Ріда-Соломона (поліноміальне, матричне, алгебраїчне) та забезпечує взаємні переходи між ними.В роботі звернуто увагу, що автоматні методи кодування та декодування (n,k)-кодів Ріда-Соломона за допомогою квантових комп’ютерів дають виграш в часі в n разів.
Databáze: OpenAIRE
Externí odkaz: