Проекты участников финального этапа НТТМ-2017

← К списку проектов

Проект
Быстродействующий кодек помехоустойчивого кода, исправляющий пакетные ошибки длиной до 3 бит на ПЛИС
НТТМ-2017-0276 | Категория II

Автор:

Рыжова Светлана Евгеньевна

Научный руководитель:
Мальчуков Андрей Николаевич
Организация:
Национальный исследовательский Томский политехнический университет,
Томская область, Томск
Цель работы
В современном мире отмечается рост передачи больших объемов информации по различным системам связи, в том числе и по беспроводным. В связи с этим растет необходимость высокой защищенности каналов от помех, которые могут возникать в процессе передачи или долгосрочного хранения информации. Для того чтобы исправлять ошибки, возникающие в данных используются помехоустойчивые коды. Наиболее широкое распространение получили коды БЧХ, способные исправлять независимые ошибки, и коды Рида-Соломона, исправляющие пакеты ошибок. Существуют такие каналы передачи, в которых необходимо быстрое исправление ошибок, с минимальными временными задержками в процессе передачи и обработки данных.
Данный проект представляет аппаратное решение для обнаружения и исправления пакетов ошибок, возникающих при передаче данных.
Обзор предметной области
Коды Рида-Соломона (РС), исправляющие пакетные ошибки также являются частным случаем кодов Боуза-Чоудхури-Хоквингема (БЧХ). Это широкий класс помехоустойчивых циклических кодов, способных исправлять сколь угодное количество ошибок в принятой комбинации.
За счет своей схожести с кодами БЧХ, коды Рида-Соломона имеют аналогичные алгоритмы декодирования, а именно: алгоритм Мэсси, Евклидов алгоритм и алгоритм Питерсона-Горенстейна-Цирлера. Основное различие составляет вычисление значений ошибок: в случае кодов БЧХ это производится с помощью поиска Ченя, в кодах РС – с помощью алгоритма Форни. Данные алгоритмы являются итеративными и требуют четкой последовательности и перехода по этапам декодирования по строго заданным условиям выхода. За счет этого время обработки данных и исправление ошибок в принятых комбинация вырастает. Также стоит отметить тот факт, что все вышеизложенные алгоритмы требуют вычислений в полях Галуа (GF(2n)), а не в машинном коде, за счет чего необходимо осуществление перехода от бинарной системы исчисления.
Наибольшее развитие в современном мире получили программные реализации алгоритмов декодирования кодов РС. В отличие от этого предлагаемая разработка представляет собой аппаратную реализацию кодека (кодер и декодер) на ПЛИС. Это позволяет распараллелить все вычисления этапов декодирования. Также процесс декодирования был заменен от классических алгоритмов на циклический метод декодирования, в котором используется основное свойство данных кодов – цикличность.
Предлагаемая работа является продолжением изучения помехоустойчивых кодов. Изначально рассматривались коды БЧХ, как наиболее распространенные и имеющие большее количество аналогов, находящихся в открытом доступе.
В мировом масштабе проблему обнаружения и исправления ошибок при передаче данных решили с помощью программных реализаций, компенсируя время обращения к программе декодера вычислительной мощностью процессора принимающего устройства. Аппаратных реализаций кодов БЧХ мало, а кодов РС и того меньше. Данный подход к разработке используется для того, чтобы была возможность реализовать параллельные вычисления, а не последовательные или по прерываниям.
Описание результатов проекта
Предлагаемый проект представляет собой аппаратное решение, благодаря которому сокращается время обработки данных в силу отсутствия необходимости обращения к программе декодера.
Работа представляет собой кодек (кодер и декодер), описанный в САПР Quarus II с использованием языка описания аппаратуры Verilog HDL. Реализация включает в себя модификации циклического алгоритма декодирования с последующими улучшениями, выявленными в результате исследований на примере декодеров БЧХ-кода для обнаружения и исправления 2-хкратных ошибок. Данный кодек способен кодировать входное информационное сообщение (дополнять их контрольными битами проверки целостности), или исправлять пакеты ошибок длиной до 3 бит. Время работы предлагаемого устройства составляет 24,6 нс. Для обнаружения и исправления пакетов ошибок используется проверка остатков на соответствие шаблону пакета ошибки.
Для получения данных результатов была проведена большая научно-исследовательская работа в области декодирования помехоустойчивых кодов, включающая в себя несколько этапов разработки декодеров, на примере БЧХ-кодов, для исправления двукратных независимых ошибок. Первоначальная реализация представляет собой декодер, основанный на циклическом алгоритме декодирования с классическим делением полиномов. Первой модификацией устройства является замена классического деления полиномов на матричный метод. Это позволило улучишь время работы декодера с 16 мкс до 500 нс. Следующим изменение в разработанном устройстве является переход к комбинационной логике, которая не требует записи считываемых данных в регистры. Время работы устройства уменьшилось до 28,05 нс. При увеличении числа исправляемых ошибок с 2-х до 3-х, время работы составило 29 нс.
Данное решение является оптимальным в плане быстродействия по сравнению с аналогичными, время работы которых составляет порядка 40 мкс, причем в аналогах используется более мощная по производительности ПЛИС. В аналогах используется Xilinx 3, в то время как предлагаемое устройства использует Altera Cyclone I.
Новизну проекта составляет его аппаратная реализация, за счет чего сокращается время обработки принимаемых данных, поскольку нет необходимости вызова программы декодера для обработки и исправления ошибок в принятой комбинации в принимающем устройстве. Предельное время работы предлагаемого устройства составляет 24.6 нс.
Визуально работа реализована на макете, состоящем из трех соединенных между собой макетов SDK 6.1., оснащенных ЖК-дисплеями. Первый макет является принимающим устройством, на которое поступает информационный блок входной кодовой комбинации и формирует в соответствии ему контрольный блок сообщения. Второй макет вносит произвольные помехи в принятую комбинацию. Третий макет является декодером и исправляет внедренные ошибки в кодовом слове, или же выводит сообщение о невозможности исправления ошибок в силу меньшей корректирующей способности кода.
По результатам работы были опубликованы 3 статьи, в т.ч. в журнале, индексируемом базой данных WoS.
Сертификат о государственной регистрации программы для ЭВМ № 2016662525.
Победитель программы финансирования УМНИК – 2016 (г. Казань);
Результаты работы неоднократно представлялись на конференциях международных и всероссийских уровней, и были отмечены дипломами различных степеней и сертификатами.
Описание применимости
В своем большинстве помехоустойчивое кодирование используется в системах связи (проводных или беспроводных). Наиболее известными областями применения кодов Рида-Соломона являются спутниковая (космическая) связь (стандарт NASA), системы цифровой записи (CD/DVD и др.), цифровые системы высокоточного телевидения (HDTV), а также в модемах на кабельных линиях, в оптоволокне и т.п. В силу быстродействия предлагаемой разработки есть возможность внедрения в повседневные технологии в качестве микросхемы специального назначения (ASIC), которая позволит улучшить качество существующих технологий (обработка и проверка дисков, увеличение пропускной способности для телевидения 4К, повышение качества сотовой связи).
Дальнейшее развитие проекта
Дальнейшее развитие проекта направлено на увеличение длины исправляемого пакета ошибок и длины входной кодовой комбинации. Время работы при данных увеличениях должно остаться неизменным или же увеличиться незначительно. Также планируется проведение исследований свойства цикличности кодов БЧХ и РС, с целью выявления закономерностей, которые можно будет использовать либо как альтернативный метод декодирования, либо как способ ускорения работы кодека. Помимо этого планируется всестороннее рассмотрение помехоустойчивых кодов, с целью поиска наиболее оптимального решения для обнаружения и исправления ошибок при передаче данных.

Информация предоставлена участником конкурса. Организаторы конкурса не несут ответственности за содержание информации о проекте.

← К списку проектов




Список всех проектов финального этапа с датами защиты

 

© Всероссийский конкурс научно-технического творчества молодежи НТТМ