Программная реализация корректирующего кодирования на основе алгоритма Боуза-Чоудхури-Хоквингема

Размещено на http://www.allbest.ru/

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

Программная реализация корректирующего кодирования на основе алгоритма Боуза-Чоудхури-Хоквингема

И. С. Киреев¹, М. Г. Уланский¹

Аннотация

Были рассмотрены основные алгоритмы и принципы программной реализации процедуры Боуза-Чоудхури-Хоквингема (БЧХ). Разработана модель реализации кодера и декодера БЧХ, произведен синтез и моделирование работы данных устройств в пакете имитационного моделирования ModelSim. Произведена оценка статистических данных по результатам работы декодера. Предложена перспектива аппаратной реализации на основе ПЛИС.

Ключевые слова: цифровая обработка сигналов, циклические коды, корректирующее кодирование, коды БЧХ, ПЛИС.

Abstract

The main algorithms and principles of the software implementation of the Bose-Chowdhury-Hokvingem (BCH) procedure were considered. The implementation model of the BCH encoder and decoder has been developed, the synthesis and simulation of the operation of these devices in the ModelSim simulation package has been carried out. The evaluation of statistical data on the results of the decoder. The prospect of hardware implementation based on FPGA is proposed.

Keywords: digital signal processing, cyclic codes, corrective coding BCH codes, FPGA

В настоящее время цифровая обработка сигналов является одним из самых перспективных направлений в телекоммуникационных системах. Данная ветвь развития современных систем связи и передачи информации важна тем, что цифровые устройства являются наиболее помехоустойчивыми. Как известно, для повышения эффективности передачи требуется либо повышение мощности передатчика (что ограничено требованиями электромагнитной совместимости и экономически не выгодно с точки зрения использования энергетических ресурсов), либо использование частотных ресурсов, которые так же ограничены. В отличии от аналоговых систем связи, где основным критерием качества является соотношение сигнал/помеха, в цифровых системах используется такой критерий, как вероятность ошибочного/верного приема сигнала, это позволяет увеличить качество связи за счет усложнения алгоритмов обработки, а не за счет увеличения мощности передатчика. Корректирующее кодирование позволяет исправить уже произошедшие ошибки за счет внесения избыточной информации в передаваемое сообщение, результате чего возникла идея программной реализации одного из алгоритмов корректирующего кодирования. Проблемы, решаемые в этой статье, были затронуты в работе [1], в которой решалась задача минимизации эффекта одиночных ошибок и работе [2], в которой был описан способ распараллеливание кодера БЧХ с возможностью изменять корректирующую способность.

В ходе данной работы были решены следующие задачи:

1) были рассмотрены теоретические основы корректирующего кодирования;

2) реализован один из перспективных алгоритмов, а именно кодер БЧХ, способный исправлять как одиночные, так и групповые ошибки (до 3 ошибок), используя средства ПЛИС;

3) произведено моделирование алгоритма в среде ModelSim.

Классическое описание алгоритма работы кодера и декодера БЧХ

Циклические коды, к которым относится БЧХ были получены на основе кодов Хэмминга. Построение кодов Хэмминга основано на принципе проверки на четность числа единичных символов, к последовательности добавляется такой элемент, чтобы число единичных символов в получившейся последовательности было четным.

(1)

где знак означает сложение по модулю 2.

Первой составляющей процедуры декодирования является вычисление так называемого синдрома, который определяется следующим образом:

(2)

Если - ошибок нет, если присутствует однократная ошибка.

В качестве примера рассмотрим классический код Хэмминга (7,4). Нахождение синдрома осуществляется по следующему выражению

(3)

где - кодовое слово без ошибки, - матрица ошибок, - транспонированная проверочная матрица. Данное выражение показывает связь между матрицей ошибок и синдромом, что позволяет исправлять искажения в сообщении.

Выражение, приведенное ниже показывает процесс кодирования информации.

(4)

На вход декодера поступает кодовое слово:

(5)

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

(6)

где - синдром последовательности.

Получение синдрома выглядит следующим образом

(7)

Синдром (0,0,0) показывает, что в последовательности нет искажений, каждому ненулевому синдрому соответствует определенная конфигурация ошибок, которая исправляется на этапе декодирования.

Схема кодера приведена на рисунке 1.

Рис. 1. Схема кодера

Схема декодера приведена на рисунке 2.

Рис. 2. Схема декодера

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

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

На основе полинома строится регистр деления при прохождении через который информационных символов, формируются проверочные.

Так на рисунке 3 показана схема регистра деления для полинома

(8)

Рис. 3. Схема регистра деления

В свою очередь коды БЧХ являются модификацией обычного циклического кода с помощью использования поля Галуа, о котором подробно написано в [3]. Особенности данных кодов будут рассмотрены на примере кода БЧХ (15,5) в дальнейшем при описании устройства. Данный код способен исправлять вплоть до трех ошибок.

Описание процедур кодирования и декодирования модели для ПЛИС

Блок схема реализации алгоритма кодирования приведена на рисунке 4.

Рис 4. - Алгоритм кодирования БЧХ

Работа кодера осуществляется следующим образом: вводим информационные символы (data), затем алгоритм ветвится. Одна из ветвей начинает работать при появлении тактового сигнала (clk) или строба о начале передачи (wr_d), другая ветвь работает при поступлении на вход тактового, при условии, что счетчик (counter) равен 1. Если условия не выполняется, то кодер переходит в режим ожидания (wait). Рассмотрим каждую ветвь по отдельности.

Первая ветвь описывает стационарную работу кодера. Если на вход поступает сигнал wr_d, значение счетчика устанавливается в 11 (4b1011), во временные буферы заносится информация с дополнительными нулевыми битами, после чего строб готовности информации обнуляется, иначе данные во втором буфере (buf2) проходят через регистр деления для полинома P(x)=10100110111. После прохождения данные записываются из буфера 2 в буфер 1, после чего осуществляется декрементация счетчика.

Вторая ветвь алгоритма, отвечает за выходной код. Она устанавливает строб готовности и «склеивает» информационные символы и проверочные. В описании декодера используются однообразные конструкции, которые целесообразно выделить в виде подфункций. Их описание будет производиться отдельно заранее.

Начнем с подфункции умножения и деления в полях Галуа, приведенных на рисунке 5.а и 5.б соответственно.

а) б)

Рис. 5. а) умножение б) деление в полях Галуа

алгоритм программный декодер хоквингем

Начнем описание работы с подфункции умножения в поле Галуа. Вносим в память поле Галуа. Вводим перемножаемые числа, после чего сравниваем их с элементами поля Галуа и находим соответствующие индексы, далее проверяем на наличие нулевых чисел. Если этих чисел нет, то вычисляем произведение по соответствующей формуле (см. блок-схему). Если хотя бы один из множителей нулевой, то соответствующее произведение обращается в нуль.

Операция деления выполняется аналогично операции умножения. Первым этапом является занесение в память элементов поля Галуа. Вводим делимое (d2) и делитель (d1), после чего находим соответствующие индексы. Проверяем, не больше ли второй индекс первого. Если больше, то проводим нормировку (см. блок-схему), далее вычисляем частное по соответствующей формуле.

Процедура вычисления синдрома также выделена в отдельную подфункцию и приведена на рисунке 6, а ее принцип работы описан ниже.

Рис. 6. Процедура вычисления синдрома

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

Блок схема, описывающая алгоритм работы декодера приведена на рисунке 7.

Рис. 7. Блок схема работы декодера БЧХ

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

1) три ошибки;

2) две ошибки;

3) одна ошибка;

4) отсутствие ошибок.

Вычисляются сигма коэффициенты и проводится процедура Ченя. Результатом работы является матрица ошибок, которая суммируется по модулю 2 с ошибочной кодовой комбинацией, тем самым исправляя ее. Информационные символы изымаются из кодовой комбинации, являясь результатом работы декодера.

Результат моделирования устройства

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

Рис. 8. Фрагмент схемы кодера

Фрагмент синтезированной схемы декодера приведен на рисунке 9.

Рис. 9. Фрагмент схемы декодера

На рисунке 10 приведены временные диаграммы, характеризующие работу кодера.

Рис. 10. Диаграммы работы кодера

Как видно из диаграмм работа устройства осуществляется согласно описанным алгоритмам.

На рисунке 11 приведены временные диаграммы, характеризующие работу декодера.

Рис. 11. Диаграммы работы кодера

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

Исследование влияния позиции ошибки на корректирующую способность

В ходе данного исследования производилось принудительное внесение ошибок в разные позиции кодовой комбинации и отслеживалась корректирующая способность декодера. Результат данных исследований приведен в таблице 1.

Таблица 1. Результаты исследования

Как видно, устройство исправляет как группирующиеся ошибки, так и одиночные.

Заключение

В ходе данной работы был выполнено устройство, способное производить кодирование и декодирование информации на основе кодов БЧХ, были решены задачи устранения до трех ошибок. Данная работа в настоящее время является весьма актуальной в силу широкого применение цифровых систем передачи информации, а также возможности реализовывать столь сложные в структурном понимании, устройства на основе ПЛИС.

Литература

1. Фенчук М.М., Синева И.С. Анализ помехоустойчивости БЧХ-кодов при предварительном генетическом кодировании метризированного источника сообщений // Журнал Связь, 2015 №2 30-33 с

2. Поперечный П.С. Разработка параллельного кодера БЧХ с регулируемой корректирующей способностью. М.: Информационная безопасность. Раздел 1 19-31 с.

3. Матвеев Б.В. Основы корректирующего кодирования: теория и лабораторный практикум. Учебное пособие. Воронеж 2018 ISBN 978-7731-0315-8.

4. Требования к оформлению докладов на РЛНС*2018. http://rlnc.ru, 15.12.2017.

5. Библиографическая ссылка. ГОСТ Р 7.05 - 2008, Москва, 2008. - 22 с.

Размещено на Allbest.ru