Введение к работе
. ї. ,_jі:
Актуальность. Эффективность сложных технических систем в большой степени определяется надежностью систем связи, обеспечивающих обмен информацией между элементами втих систем. Високая помехоустойчивость систем связи достигается примененном корректирующих кодов. Использование корректирующих кодов позволяет бороться с сшибками, возникающими вследствие шумов и помех в каналах связи. Для кодирования информации на передаваемой сторони системы связи и для декодирования этой информации на приемной стороне требуются специализированные устройства - кодер и декодер. Для достижения высокой помехоустойчивости требуется использовать кода больной длины, исправляющие большое число ошибок. С увеличением длины и числа исправляемых ошибок возрастает сложность кодера и декодера, а также. уменьшается их быстродействие. Это в свою очередь сказывается на быстродействии всей системы в целом. В связи с этим становится весьма ванной задача поиска новых эффективных методов кодирования н декодирования информации.
На практике в качестве корректирующих кодов очень часто используются коды Рида-Соломона (PC-коды) над полем GP(2*). Это связано прежде всего с тем, что кода Рида-Соломона обладают наибольшим кодовым расстоянием, а кроме того имеют алгебраические методы декодирования. Коды Рида-Соломона успешно используются в каскадных конструкциях, при построении кодов с большими длинами. Практический интерес к кодам Рида-Соломона над полем GF(2m) обусловлен еще и тем, что элементы поля G?{2*) представляются в виде двоичных векторов и с ними легко оперировать, используя цифровые схемы или ЭВМ.
Как известно, кодирование, а также наиболее трудоемкие этапы декодирования PC-кодов (вычисление синдрома и поиск номеров ошибочных позиций) по-существу являются вычислением преобразования Фурье (ПФ) в поле GF(2m). Такое спектральное представление позволяет использовать быстрые алгоритмы вычисления ПФ (БПФ) в кодировании и декодировании PC-кодов. Построение
алгоритмов БПФ в полях характеристики 2 посвящены работы В.Б.Афанасьева, Р.Блейхута, И.И.Грушко и некоторых других авторов. Однако, известные алгоритмы БПФ позволяют уменьшить число операций как правило только при вычислении всех компонент спектра. При декодировании PC-кодов вычисляется только часть спектральных компонент, поэтому использование известных алгоритмов БПФ оказывается неэффективным. Кроме того, построение оптимального вычислителя известішми методами связано с большой подготовительной работой, что сильно затрудняет разработку декодера.
Исходя из этого, можно сделать вывод о том, "что задача построения быстродействующих декодирующих устройств РС-кодов тесно связана с задачей поиска новых аффективных методов вычисления преобразования Фурье в полях характеристики 2.
В диссертационной работе разработан алгоритм построения БПФ в поле GFO^). Основное преимущество предлагаемого алгоритма состоит в том, что он позволяет уменьшить число операций но только в случае вычисления полного преобразования Фурье, но также пра вычислении только части спектральных компонент. Кроме того, формализованный подход к построении ПФ позволяет строить вичисяиголл БПФ с помощью ЭВМ. Предлагаемый алгоритм БПФ может быть полезен при создании быстродействующих декодирующих устройсгв РС-кодов.
Целью диссертационной работы является разработка эффективних алгоритмов кодирования и декодирования информации, обеспечиващих защиту информации от оашбок.
Для достижения поставленной цели представляется необходимым решение следующих задач :
разработать алгоритм вычисления ПФ в поле GF(2m), инвариантный к числу вычисляемых компонент и размеру поля;
исследовать эффективность разработанного алгоритма по числу операций сложения и умножения;
исследовать возможность применения разработанного алгоритма БПФ для кодирования и декодирования РС-кодов:
- разработать программное обеспечение для построения
вычислителей БПФ;
Методи исследования. Основными методами исследования являются теоретические исследования с использованием методов теории конечных полей, алгебраической теории кодирования, а также экспериментальные исследования с помощью ЭВМ, в частности, иммитвционное моделирование алгоритмов кодирования и декодирования.
Новые результаты и положения, выносимые на защиту :
алгоритм вычисления преобразования Фурье в поле GT(2), позволяющий сократить число операций при вычислении ПФ в поле GPie*), в том числе при вычислении неполного ПФ;
подход к вычислению ПФ, позволящий снизить трудоемкость создания вычислителя ПФ в поле G^)m.
представление блоковых кодов, позволяющее аффективно использовать ати коды в каскадных конструкциях совместно с кодаш Рида-Соломона в каналах с мягкими решениями.
Практическая ценность работы. Практическая ценность работы состоит в следующем:
предложена методика эффективной реализации вычислителя синдрома, вычислителя номеров ошибочных позиций и реализации кодирования для кодов Рида-Соломона;
разработан пвкет программ для построения вычислителя преобразования Фурьо в поле GP(2'n) с заданным числом входных и выходных символов;
предложен алгоритм декодирования коротких блоковых кодов, получаемых из свврточяых, ориентированных на использование в каскадных конструкциях совместно с кодаш Рида-Соломона в канале с мягкими решениями.
Результаты исследования нашли применение в научно исследовательских работах, проводимых кафедрой "Автоматизированные системы управления" Института авиационного приборостроения, отражены в отчетах по НИР и использоввпи при
разработке систем связи, выполненных совместно с научно-исследовательскими институтами, что подтверждаете? соответствующими документами.
Апробация работа.Основные результаты диссертационной работы докладывались, обсуадались и получили одобрение на:
К Всесоюзном симпозиуме по проблемам избыточности і информационных системах (С-Петербург, 1989);
девятой всесоюзной конференции по теории кодирования і передачи информации (Одесса, 1988);
научном семинаре НТО РЭС им. А.С. Попова (С-Петербург 1990);
-ХПІІ Всесоюзной школе-семинаре по теории информации и ei приложениям, проводимой ИППИ (Белорецк, 1991); а также семинарах по теории информации и кодирования кафедры АСУ СПИАП (С-Петербург, 1988-1992).
Публикации. По результатам проведенных исследовани опубликовано 7 печатных работ, получено авторское свидетельств на изобретение.
Структура и объем диссертации. Диссертация состоит и введения, четырех разделов, заключения, списка литературы приложений. Работа содержит 128 страниц основного текста, рисунков, список использованой литературы содержит А наименования.
