Статья: Работа декодера на основе лексикографического подхода

Работа декодера на основе лексикографического подхода

Б.А.С. Саид

Ульяновский Государственный Технический Университет (УлГТУ), Ульяновск, Россия

Аннотация

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

Ключевые слова: Списочное декодирование, недвоичный код, линейные коды, кодовой вектор, стирающий канал, кластер, РС код, метод, комбинация, декодер, помеха.

OPERATION OF A DECODER ON THE BASIS OF A LXICOGRAPHIC APPROACH

B. A. S. Saeed

Ulyanovsk State Technical University (UlSTU), Ulyanovsk, Russia

Annotation. This article discusses the work of a decoder based on a lexicographic approach. The essence of the decoder is that it is proposed to use algorithms based on the lexicographic approach and the selection of a small group of combinations from the set of allowed combinations of such a code combined with a unique feature in the form of a cluster number to search for the error vector of a non-binary code. The proposed method eliminates the method of selecting the error locator vector, which reduces the complexity of the implementation of the decoder. It also reduces the complexity of the computational process during the decoding of the code vector of the non-binary code.

Keywords: List decoding, non-binary code, linear codes, code vector, erase channel, cluster, RS code, method, combination, decoder, interference.

Введение

Декодирование списком позволяет во многих случаях повысить вероятность успешного декодирования данных после передачи по каналам с высоким уровнем шума. Эффективные алгоритмы декодирования списка доступны только для очень узкого класса кодов, исправляющих ошибки [2].

Механизм работы декодера

декодер алгоритм лексикографический ошибка

Для того, чтобы понять как работает декодер рассмотрим следующий пример: Пусть имеется код РС (7, 3, 5), над полем GF(23) с порождающим полиномом:

Пусть поступает следующий вектор на вход кодера от источника информации

После прохождения переданный вектор по каналу связи, который будет искажен в зависимости от уровня помеха в канале связи. Предполагаем, что на переданный вектор действовал вектор ошибок такого вида:

В результате принятый вектор будет иметь вид:

Так как:

Пусть будут самыми надежными элементами исходя из значения приоритетов, но они не будут в начале кодовой комбинации. При этом будет не надо осуществить операцию поиска локаторов ошибок, что делает работу декодера проще [1].

Затем в блоке выделения кластера выделяется по самым надежным элементам, , нужный кластер, которому принадлежат эти элементы. Потом поступают в блок формирования ключевого вектора и при этом вместо третьего элемента оставляется 0 т.е. будут иметь такой вид. По образуется ключевой вектор путем их кодирования в кодере. Кодирование последовательности из 3 символов в систематической форме на основе РС кода (7,3,5), определяемого генератором [4, 5].

В результате регистр будет содержать 4 контрольных символа, и . Эти 4 контрольных символа подаются на выход после того как переключатель 1 переходит во втрое положение. Тогда ключевой вектор будет иметь такой вид

Комбинаций нулевого кластера и других кластеров нужных данному примеру, представленные в таблицах 1-2.

Таблица 1. Структура комбинаций нулевого кластера

Таблица 2. Структура комбинаций кластер = 010100

В блоке суммирования ключевой вектора сложим по модулю 2 с принятым вектором (принятой комбинацией) с накопителя кодовых комбинаций в результате сложения образуется суммарный вектор.

Также от списка эталонных комбинаций выбирается нулевой вектор, который будет иметь такой вид в нашем примере

В блоке вектора ошибок выполняется операция сложения по модулю 2 нулевого вектора с суммарным вектором для того, чтобы найти вектор ошибок.

В блок исправления ошибок поступает вектор ошибок, который необходимо сложить по модулю 2 с принятым вектор (принятой комбинацией) с накопителя кодовых комбинаций 3 для того, чтобы найти переданный вектор.

Затем переданный вектор (переданная комбинация) передается в блок выделения информационных разрядов, который является выходом декодера [3].

В представленном коде РС число разрешенных комбинаций составляет 512 комбинаций, которые могут быть разбиты на 64 кластера. В случае организации работы декодера по системе списочного декодирования декодер в первом случае должен составить наиболее вероятных комбинаций из общего числа комбинаций 512. Предложный метод декодирования по единственному списку эталонных комбинаций т.е. по нулевому кластеру в первом приближении повышает скорость обработки данных декодером 64 раза [6].

Заключение

Списочное декодирование блоковых систематических и несистематических кодов относится к разряду наиболее эффективных методов исправления ошибок за счет простоты реализации. Этот метод относится к лексикографического разбиения кодовых комбинаций. Применение лексикографического подхода сокращает время составления списка вероятных комбинаций путем выделения кластеров, исправляет большое число ошибок и использует особенности максимально декодируемых кодов в каскадных структурах.

Литература

1. Агеев, С. А. Декодирование на основе лучших показателей качества приема сигнала / С. А. Агеев, С. А. Бодров, А. А. Гладких, Ю. П. Егоров // Автоматизация процессов управления. - 2004. - №1(3). - С.43-46.

2. Арнольд, В. И. Динамика, статистика и проективная геометрия полей Галуа/ В. И. Арнольд - М.: МЦНМО, 2005. -- 72 с.

3. Гладких А.А. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи. Ульяновск: УлГТУ, 2010. - 379 с.

4. Саид Басем А. С. Современные проблемы проектирования, производства и эксплуатации радиотехнических систем // Сборник научных трудов Г. Ульяновск УлГТУ 2014 - с.92ЬЬ95.

5. Скляр, Бернард. Цифровая связь. Теоретические основы и практическое применение / Бернард Скляр - Изд. 2-е, испр. пер. с англ. - М.: Издательский дом «Вильямс», 2003. - 1104 с.

6. Форни, Д. Г. Экспоненциальные границы для ошибок в системах со стиранием, декодированием списком и решающей обратной связью / Д. Г. Форни // Некоторые вопросы теории кодирования. - М.: 1970, - С.166-205.

References

1. Ageev, S. A. Decoding based on the best indicators of signal reception quality / S. A. Ageev, S. A. Bodrov, A. A. Gladkikh, Yu. P. Egorov // Automation of control processes. - 2004. - №1 (3). - P.43-46.

2. Arnold, V. I. Dynamics, statistics and projective geometry of Galois fields / V. I. Arnold - Moscow: MSCNMO, 2005. - 72 p.

3. Gladkikh A.A. Fundamentals of the theory of soft decoding of redundant codes in the erasing communication channel. Ulyanovsk: UlSTU, 2010. - 379 p.

4. Saeed Basem A. S. Modern problems of design, production and operation of radio engineering systems // Collection of scientific works of City Ulyanovsk UlSTU 2014 - p.92-95.

5. Sklar, Bernard. Digital communication. Theoretical foundations and practical application / Bernard Sklyar - Ed. 2nd, rev. per. from English - M .: Publishing house "Williams", 2003. - 1104 p.

6. Forni, DG Exponential Bounds for Errors in Systems with Erasure, List Decoding and Decisive Feedback / DG Forni // Some Questions of Coding Theory. - M .: 1970, pp. 1666-205.