Разработка структуры быстродействующего декодера БЧХ-кода и его реализация на примере БЧХ-кода (15,7,5)

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

Цель работы: реализовать быстродействующий декодер БЧХ-кода (15, 7, 5)
Задачи:
- Исследовать имеющиеся алгоритмы декодирования БЧХ-кода;
- Разработать быстродействующий декодер БЧХ-кода (15,7,5);
- Провести сравнительный анализ с имеющимися реализациями;
- Провести тестирование разработанного декодера.

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

Одним из таких является класс циклических кодов  -  БЧХ-коды.

БЧХ-коды относятся к классу циклических кодов, за счет чего к ним применимы все методы декодирования, которые используются для циклических кодов. Однако существуют алгоритмы, которые были разработаны специально для БЧХ-кодов.

Основной идеей в использовании алгоритмов декодирования БЧХ-кодов является использование элементов конечного поля Галуа для того, чтобы пронумеровать позиции кодового слова.

На данный момент известны следующие алгоритмы декодирования:

1. Алгоритм Бэрлекемпа-Мэсси (БМА) – итеративный процесс построения минимального линейного регистра с обратной связью (ЛРОС), который генерирует последовательность синдромов. Данный алгоритм  обладает высокой эффективностью по числу операций в поле Галуа и используется для моделирования или программной реализации кодов БЧХ;
2. Алгоритм Питерсона-Горенстейна-Цирлера (ПГЦ) (прямое решение) –алгоритм, в котором находятся коэффициенты многочлена локаторов ошибок прямым решением, соответствующей системы линейных уравнений. Сложность обращения матрицы растет как куб корректирующей способности кода, поэтому данный алгоритм подходит только для малых значений;
3. Евклидов алгоритм (расширенный) – построен на процедуре поиска наибольшего общего делителя (НОД) двух полиномов или целых чисел;
4. Циклический метод декодирования – является наиболее распространенным методом обнаружения и исправления ошибок. Построен на процессе вычисления веса остатка, полученного от деления принятой комбинации на образующий многочлен.

В результате работы были исследованы алгоритмы декодирования БЧХ-кодов (БМА, ПГЦ, ЕА, циклический метод). Для каждого алгоритма декодирования  были рассчитаны конкретные примеры  для БЧХ-кода (15,7,5). В результате исследование был выбран циклический алгоритм декодирования для дальнейшенй реализации быстродействующего декодера за счет отсутствия необходимости перехода к полям Галуа, которое требует больших вычислительных затрат. 

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

• Формирование всех вариантов сдвига входного кодового слова вместо циклического сдвига;
• Параллельное вычисление остатков от деления;
• Параллельное вычисление весов остатков;
• Переупорядочивание битов вместо циклического сдвига.

На основе представленных изменений был реализован декодер БЧХ-кода. Для достижения максимальной производительности была использована комбинационная логика, вместо последовательной.

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

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

1. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.Ж Мир, 1986. – 576с.
2. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования: методы, алгоритмы, применение: учебное пособие: пер. с англ. – М.:Техносфера, 2006. – 320 c.
3. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: учебное пособие: пер. с англ. – М.: Мир, 1976. – 744 с.
4. Мак-Вильямс Ф., Слоэн Н. Теория кодов, исправляющих ошибки: учебное пособие: пер. с англ. – М. Свзяь, 1979. – 372 с.
5. Теоретическое пособие по лабораторной работе №6 – Код Боуза-Чоудхори-Хоквингема под редакцией доцента кафедры ВТ Томского Политехнического университета, Осокина А.Н. [Электронный ресурс]
6. Мальчуков А.Н. Методические указания к выполнению курсовых работ по курсу «Схемотехника ЭВМ ч.2» для студентов, обучающихся по направлению 09.03.01 «Информатика и вычислительная техника», 2014. – 63с.

This article presents the structure, which based for implementation of high-speed error-correcting decoder BCH code, which able to correct two independent errors, based on the cyclic decoding algorithm. In order to increase the decoder performance, a series circuit has been replaced by the combination. In addition to the implementation of the decoder were tested to confirm its efficiency in finding and correcting any various options of introduction single and double independent errors into the original combination. Also has been made comparison foreign decoder analogue, developed on FPGA, with the implementation represented in article.