Алгоритмическое и программное обеспечение системы для разработки кодеков помехоустойчивых кодов

В настоящее время в связи с многократно возросшими объёмами передаваемой и хранимой в различных устройствах информации ужесточились требования к её достоверности. Одним из самых перспективных методов решения проблемы обеспечения достоверности передачи и приёма информации является помехоустойчивое кодирование данных на основе корректирующих кодов. В последнее время коды, исправляющие ошибки, нашли применение во многих системах сбора, передачи и хранения данных. Наиболее известные из них — это сотовые системы связи, спутниковая спасательная система КОСПАС — САРСАТ, система глобальной морской связи Инмарсат, системы автоматизации технологических процессов, сети сбора информации с датчиков различного назначения и др. Во всех вышеприведённых примерах систем с помехозащищённой обработкой информации обычно используются наиболее простые и эффективные циклические корректирующие коды небольшой длины, которые, наряду с простотой кодирования и декодирования, отличаются достаточно большой корректирующей способностью.

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

До сегодняшнего дня многие известные коды (Хэмминга, Рида-Маллера, Боуза-Чоудхури-Хоквенгема (БЧХ) и т. п.) применяют не системно, нет методики выбора кодов, обеспечивающих требуемые корректирующие свойства при минимальной избыточности в заданном диапазоне информационных разрядов [4,27,29,32,40,45,47,53]. Успешному применению помехоустойчивых кодов разработчиками систем сбора и передачи данных препятствует тот факт, что для непосредственного выбора помехоустойчивого кода под конкретные условия эксплуатации систем требуются глубокие знания теории помехоустойчивого кодирования.

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

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

Цель работы и задачи исследования. Целью диссертационного исследования является разработка алгоритмического и программного обеспечения системы для создания кодеков помехоустойчивых полиномиальных кодов, исправляющих независимые ошибки кратности от 1. до 4 включительно. Система должна позволять подготавливать данные для различных САПР при аппаратной реализации кодеков на ПЛИС или для программной реализации кодеков на микроконтроллерах в зависимости от задаваемых пользователем параметров (длина информационного блока и корректирующая способность кода): г.

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

1. Формирование требований к системе для разработки кодеков-помехоустойчивых кодов и создание алгоритма её функционирования.

2. Разработка алгоритма поиска образующих полиномов и алгоритмов деления полиномов в арифметике по модулю два, а также исследование их эффективности. Решение данной задачи предполагает разработку ПО для проведения таких исследований;

3. Разработка алгоритма функционирования проектируемого кодека и создание на его основе шаблона для САПР при реализации кодеков на ПЛИС различных фирм-производителей.

4. Разработка, ПО системы для создания кодеков помехоустойчивых полиномиальных кодов. Результатом решения этой задачи должны явиться структура ПО системы и программные модули системы, разработанные с использованием технологии объектно-ориентированного программирования.

5. Апробация разработанного ПО системы на примере решения прикладных задач повышения достоверности передачи данных.

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

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих симпозиумах, конференциях и семинарах: региональная научно-практическая конференция «Молодежь и современные информационные технологии» (г. Томск, 2003 г.), Корейско-Русский Международный симпозиум науки и технологии «KORUS 2003» (Республика Корея, г. Ульсан, 2003 г.), Конференция-конкурс «Технологии Microsoft в информатике и программировании» (г. Новосибирск, 2004 г.), II, III, IV и VI Всероссийская научно-практическая конференция студентов, аспирантов и молодых учёных «Молодежь и современные информационные технологии» (г. Томск, 2004, 2005, 2006 и 2008 гг.), X, XIII и XIV Международная научно-практическая конференция студентов, аспирантов и молодых учёных «Современные техника и технологии» (г. Томск, 2004, 2007 и 2008 гг.), Пятая юбилейная Всероссийская научно-практическая конференция «Средства и системы автоматизации» (г. Томск, 2005 г.).

Результаты диссертационной работы оценивались на конкурсах и получили следующие награды: медаль Министерства образования и науки РФ «За лучшую научную студенческую работу» в 2005 г. и медаль Российской академии наук для студентов высших учебных заведений в области информатики, вычислительной техники и автоматизации в 2006 г.

По результатам диссертационных исследований опубликовано 15 работ, в том числе 4 статьи в рецензируемых изданиях, рекомендованных ВАК РФ.

Кратко изложим основное содержание работы.

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

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

Анализ существующих систем для создания кодеков и имеющиеся тенденции проектирования кодеков с использованием современной элементной базы позволили сформулировать требования к практически значимым системам для разработки кодеков помехоустойчивых кодов.

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

Сформулированы цель и задачи исследований.

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

На основе сформулированных в главе 1 требований к системе разработан алгоритм её функционирования.

Предложен оригинальный алгоритм поиска образующих полиномов. В основу этого алгоритма положен способ уменьшения количества итераций вычислений, учитывающий зависимость корректирующей способности кода и веса образующего полинома. Представлены результаты поиска образующих полиномов, который проводился на суперкомпьютерном кластере «СКИФ-политех» с помощью специально разработанного ПО. Показано, что полиномиальные коды в ряде случаев (например, для случая исправления двукратной независимой ошибки t=2 и длин информационного блока т=(1−4,8−13,22−24)) обладают меньшей избыточностью, чем БЧХ-коды.

В остальных случаях избыточность одинаковая. Это говорит о большей эффективности (меньшей избыточности) предлагаемых полиномиальных кодов.

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

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

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

Третья глава посвящена описанию созданного ПО системы MagDiv для разработки кодеков помехоустойчивых полиномиальных кодов, кроссплатформенной библиотеки классов PCodeWords и ПО для поиска образующих полиномов.

Сформулирован набор требований к ПО системы MagDiv. С учётом этих требований разработана структура ПО этой системы. ПО системы MagDiv реализует предложенный в главе 2 алгоритм функционирования системы и представляет из себя набор программных модулей, часть из которых в своей работе использует библиотеку классов PCodeWords. Другие модули системы используют эту библиотеку через методы класса DivLib. Входными данными для модулей системы является задаваемые пользователем параметры проектируемого кодека (длина информационного блока и корректирующая способность кода), файл данных образующих полиномов и файл данных шаблона проектируемого кодека. Результатом работы ПО являются файлы проекта кодека. В случае выбора пользователем программной реализации кодека на микроконтроллерах в проекте содержатся данные, необходимые для написания управляющей программы для микроконтроллера. В случае аппаратной реализации кодека на ПЛИС с использованием выбранной САПР проект кодека компилируется и затем конфигурируется конкретная ПЛИС.

Описывается кроссплатформенная библиотека классов PCodeWords, лежащая в основе разработанного ПО для поиска образующих полиномов и ПО системы MagDiv. Эта библиотека создана с учётом современных требований к разработке библиотек классов. Библиотека классов PCodeWords имеет самостоятельную практическую ценность, поскольку позволяет создавать на её основе исследовательское ПО в области полиномиальных вычислений и помехоустойчивого кодирования.

Приводится описание ПО для поиска образующих полиномов. Указываются особенности программной реализации и описывается структура ПО. Даётся описание разработанного интерфейса пользователя. Приводятся примеры результатов работы созданных программных средств для компьютера под управлением ОС Windows ХР и для суперкомпьютерного кластера «СКИФ-политех» под управлением ОС Linux.

В четвёртой главе приводятся результаты апробации разработанного ПО системы MagDiv при решении прикладных задач повышения достоверности передачи данных на основе применения кодеков помехоустойчивых полиномиальных кодов.

Описываются результаты применения разработанного ПО системы MagDiv для решения задачи повышения достоверности передачи данных в системе управления процессом бурения и для решения задачи повышения достоверности передачи данных в инклинометрической системе для буровой установки. Разработаны соответствующие кодеки помехоустойчивых полиномиальных кодов. По результатам апробации сделан вывод о работоспособности и эффективности алгоритмического и программного обеспечения системы MagDiv. Указывается, что результаты диссертационного исследования внедрены в ООО «Технологическая Компания Шлюмберже» (в прошлом Томский филиал ООО «Сибирская Геофизическая Компания») и в ООО «ТомскНефтеГазИнжиниринг».

В заключении приведены основные выводы и результаты диссертационной работы.

В приложение 1 вынесены акты о внедрении полученных результатов.

Научную новизну полученных в работе результатов определяют.

1. Предложенный алгоритм функционирования автоматизированной системы для разработки кодеков помехоустойчивых полиномиальных кодов, позволяющий создавать проектные файлы кодеков, как для последующей программной реализации кодеков на микроконтроллерах, так и для САПР при проектировании кодеков на ПЛИС различных фирм-производителей.

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

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

4. Разработанный шаблон кодека помехоустойчивых полиномиальных кодов, реализованный на языке описания аппаратуры Verilog.

Практическая ценность и реализация результатов работы. Практически значимыми являются созданные алгоритмы, ПО системы для разработки кодеков MagDiv и ПО для поиска образующих полиномов. Разработанное ПО системы MagDiv и ПО для поиска образующих полиномов имеют в своём составе кроссплатформенную библиотеку классов PCodeWords, также имеющую самостоятельную практическую ценность. ПО системы MagDiv функционирует на компьютерах под управлением ОС Windows 9x/NT72000/XP/Vista. ПО для поиска образующих полиномов функционирует на суперкомпьютерном кластере «СКИФ-политех» под управлением ОС Linux или на компьютерах под управлением ОС Windows 9x/NT/2000/XP/Vista. Объём исходного кода разработанного ПО составляет более 2500 строк на языках С++ и Verilog.

Результаты работы внедрены в ООО «Технологическая Компания Шлюмберже» (в прошлом Томский филиал ООО «Сибирская Геофизическая Компания») и в ООО «ТомскНефтеГазИнжиниринг». Результаты внедрения подтверждены соответствующими актами.

Личный вклад.

1. Постановка задач диссертационного исследования выполнена автором совместно с Н. Г. Марковым.

2. Разработка алгоритма функционирования системы для создания кодеков помехоустойчивых полиномиальных кодов выполнена автором совместно с А. Н. Осокиным.

3. Математическое обоснование матричного алгоритма деления полиномов по модулю два выполнено совместно с Ю. Б. Буркатовской.

4. Разработка остальных предложенных алгоритмов выполнена автором.

5. Разработка ПО системы MagDiv, ПО для поиска образующих полиномов и программных средств для проведения исследований эффективности предложенных алгоритмов проведена автором.

6. Шаблон проектируемого кодека помехоустойчивых полиномиальных кодов на языке Verilog разработан автором.

Основные положения, выносимые на защиту.

1. Созданное ПО системы MagDiv позволяет разрабатывать кодеки помехоустойчивых полиномиальных кодов, реализуемые как программно на микроконтроллерах, так и аппаратно на ПЛИС различных фирм-производителей.

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

3. Матричный алгоритм деления полиномов в арифметике по модулю два позволяет вычислять остаток от деления полиномов в 3−6 раз быстрее по сравнению с известным классическим алгоритмом деления полиномов.

4. Шаблон проектируемого кодека помехоустойчивых полиномиальных кодов, написанный на языке Verilog, позволяет создавать в САПР кодеки на ПЛИС различных фирм-производителей.

Автор выражает глубокую благодарность научному руководителю доктору технических наук, профессору Н. Г. Маркову за помощь в написании работы, ценные советы и замечания. Автор выражает особую благодарность за всестороннюю помощь и поддержку доцентам кафедры вычислительной техники Томского политехнического университета кандидату технических наук А. Н. Осокину и кандидату физико-математических наук Ю. Б. Буркатовской. Также автор благодарит за своевременные советы по организационным вопросам доцента кафедры вычислительной техники Томского политехнического университета, кандидата технических наук Ю. Р. Цоя.

4.3. Основные результаты и выводы по главе.

1. Проведена апробация разработанного ПО системы MagDiv при решении задачи повышения достоверности передаваемых данных в системе управления процессом бурения. Разработаны аппаратная и программная реализации кодека помехоустойчивого полиномиального кода, удовлетворяющего требованиям этой задачи. Аппаратная реализация кодека осуществлена с помощью САПР Мах+ plus II на ПЛИС фирмы Altera. Программно кодек реализован на микроконтроллере ADuC812 фирмы Analog Devices, входящем в состав вычислительного блока интеллектуального датчика натяжения талевого каната.

2. Проведена апробация разработанного ПО системы MagDiv при решении задачи повышения достоверности данных в инклинометрической системе для буровой установки. Спроектированный кодек основывается на помехоустойчивом полиномиальном коде, превосходящем по характеристикам (длина информационного блока, меньшая избыточность, а значит большая эффективность кода [44]) аналогичный БЧХ-код. Кодек реализован аппаратно с помощью САПР Мах+ plus II на ПЛИС фирмы Altera.

3. Результаты моделирования работы кодеков для решения каждой из поставленных прикладных задач показали их высокое быстродействие (в режиме кодирование 20 не, декодирования 30 не) при аппаратной реализации на ПЛИС ЕР1К50ТС144−1 семейства АСЕХ1К фирмы Altera.

4. Результаты диссертационного исследования и разработанное ПО системы MagDiv внедрены в ООО «Технологическая Компания Шлюмберже» (в прошлом Томский филиал ООО «Сибирская Геофизическая Компания») и в ООО «ТомскНефтеГазИнжиниринг», о чём свидетельствуют соответствующие акты о внедрении.

ЗАКЛЮЧЕНИЕ

.

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

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

1. Проведён анализ существующих автоматизированных систем для разработки кодеков помехоустойчивых кодов, а также анализ современных методов и алгоритмов помехоустойчивого кодирования. Сделан вывод о необходимости создания практически значимых систем для разработки таких кодеков, имеющих эффективное алгоритмическое и программное обеспечение.

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

3. Разработан оригинальный алгоритм поиска образующих полиномов, отличающийся от известных меньшим количеством требуемых итераций вычислений. На основе предложенного алгоритма разработано ПО для поиска образующих полиномов. Проведены компьютерные эксперименты на суперкомпьютерном кластере «СКИФ-политех», в результате которых вычислены образующие полиномы, позволяющие строить помехоустойчивые полиномиальные коды, имеющие в ряде практически значимых случаях меньшую избыточность, чем БЧХ-коды.

4. Разработан быстродействующий алгоритм матричного деления полиномов в арифметике по модулю два. Результаты компьютерного эксперимента подтвердили теоретические предположения о его эффективности по быстродействию. Матричный алгоритм позволяет создавать быстродействующие кодеки помехоустойчивых полиномиальных кодов.

5. Предложены методы уменьшения требуемого объёма энергонезависимой памяти при аппаратной реализации кодека с синдромным декодированием, которые позволяют создавать кодеки в условиях нехватки объёма такой памяти.

6. Разработаны структура ПО и программные модули системы MagDiv для создания кодеков помехоустойчивых полиномиальных кодов. В рамках этой системы разработан шаблон проектируемого кодека на языке описания аппаратуры Verilog. Шаблон позволяет ПО системы MagDiv создавать проектные файлы кодеков для САПР различных фирм-производителей ПЛИС.

Разработано исследовательское ПО для поиска образующих полиномов, с помощью которого проведён компьютерный эксперимент и найдены образующие полиномы. Результаты применения этого ПО позволили исключить из ПО системы MagDiv ресурсоёмкую часть по подбору образующих полиномов.

Объём исходного кода разработанного ПО составляет более 2500 строк на языках С++ и Verilog.

7. Разработана кроссплатформенная библиотека классов PCodeWords, реализующая предложенный матричный алгоритм деления полиномов в арифметике по модулю два и входящая в состав ПО системы MagDiv и в состав ПО для поиска образующих полиномов. Эта библиотека имеет также самостоятельную практическую ценность для полиномиальных вычислений и помехоустойчивого кодирования.

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