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

На правах рукописи

Кукунин Дмитрий Сергеевич

АНАЛИЗ ЭФФЕКТИВНОСТИ ДЕКОДИРОВАНИЯ ЦИКЛИЧЕСКИХ КОДОВ С ИСПОЛЬЗОВАНИЕМ ДВОЙСТВЕННОГО БАЗИСА

Специальность 05.13.01 - Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2009

003474030

Работа выполнена в Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича

Научный кандидат технических наук, профессор

руководитель Когновицкий Олег Станиславович

Официальные оппоненты

доктор технических наук, профессор Деев Владимир Викторович

Ведущее предприятие

кандидат технических наук Химин Сергей Васильевич

ФГУП ЛОНИИС, г. Санкт-Петербург

Защита состоится « 2-» О V 2009 года в /2- часов на заседании диссертационного совета Д 219.004.02 при Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича по адресу: 191186 Санкт-Петербург, наб. р. Мойки, д.61, ауд. 20Г.

С диссертацией можно ознакомиться в библиотеке университета.

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

Автореферат разослан«_/_» С>£ 2009 года.

Ученый секретарь диссертационного совета кандидат технических наук, доце

В.Х. Харитонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Классическое описание циклических кодов опирается на такие понятия, как кодовое расстояние и избыточность, что способствует выбору кода с заданными параметрами. Исследуемые в данной работе циклические коды составляют большой спектр от "медленных" до "быстрых" помехоустойчивых кодов, обладающих минимальными корректирующими способностями. При этом особое внимание уделяется двоичным кодам БЧХ (Боуза-Чоудхури-Хоквингема).

Свойства кодов БЧХ подробно рассмотрены в работах Питерсона У., Уэл-дона Э., Касами Т., Кларка Дж., Кейна Дж„ Берлекэмпа Э. Повышенный интерес к кодам БЧХ подтверждается и тем, что разработано значительное количество алгоритмов декодирования таких кодов, как в частотной, так и во временной области. В работах профессора Когновицкого О.С. рассмотрена применимость двойственного базиса поля Галуа в вопросах декодирования циклических кодов с учетом их рекуррентных свойств. Рациональный выбор того или иного алгоритма требует проведения сравнительного анализа по корректирующим способностям различных методов декодирования кодов БЧХ, в том числе методов декодирования с использованием двойственного базиса.

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

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

Методы исследования. Проводимые исследования основываются на теории полей Галуа, теории двойственного базиса поля Галуа, теории кодирования, теории рекуррентных регистров сдвига и теории вероятностей. Для прове-

дения численных расчетов использовались программные пакеты: MS Excel 2003, Mathcad 13, Advanced Grapher 2.11 и другие. Программное обеспечение, необходимое для решения поставленных в диссертации задач, реализовано в среде MS Visual С++ 6.0.

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

1. Исследован новый метод декодирования кодов БЧХ как рекуррентных последовательностей с использованием двойственного базиса.

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

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

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

5. Предложен новый вариант реализации дискретного логарифмирования в полях Галуа до GF(23) с использованием контрольных точек.

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

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

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

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

В качестве основного инструмента для проведения экспериментов был использован разработанный диссертантом программный комплекс - калькулятор

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

Реализация результатов работы. Основные научные результаты работы внедрены в практическую деятельность ЗАО НПП «ИСТА-Системс», а также используются в учебном процессе Санкт-Петербургского государственного университета телекоммуникаций им. проф. М.А. Бонч-Бруевича, что подтверждено соответствующими актами внедрения.

Апробация работы. Результаты работы обсуждались и были одобрены на НТК профессорско-преподавательского состава и НТК студентов, аспирантов и молодых специалистов СПбГУТ. По результатам диссертации опубликовано 15 работ, в том числе четыре в изданиях из перечня, рекомендованного ВАК.

Структура и объем работы. Диссертация состоит из введения, 5 глав, заключения и приложений. Работа содержит 169 страниц машинописного текста, 71 рисунок, 19 таблиц и список литературы из 130 наименований. Основные положения, выносимые на защиту:

1. Результаты исследования эффективности декодирования кодов БЧХ на основе двойственного базиса.

2. Методы оценки качества канала, основанные на обработке комбинаций циклического кода с использованием двойственного базиса.

3. Методика адаптации системы передачи данных к состоянию канала с выбором оптимального варианта кода на основе предложенного метода оценки качества канала.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

В диссертационной работе проведен анализ эффективности декодирования двоичных циклических кодов (эквидистантных и БЧХ) как рекуррентных последовательностей с использованием теоретических результатов, полученных профессором Когновицким О.С., в частности:

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

- выражения, позволяющего по различным ^-элементным участкам рекуррентной последовательности с использованием двойственного базиса определять начальные элементы, формирующие рекуррентную последова-

тельность кода, что реализует алгоритм мажоритарного декодирования комбинации (1);

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

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

Во второй главе проводится сравнительный анализ эффективности методов декодирования двоичных циклических кодов по корректирующей способности. Критерием оценки является вероятность правильного декодирования Рс в зависимости от вероятности ошибки рош в канале. В качестве модели канала использован двоичный симметричный канал без памяти с биномиальным распределением ошибок. Исследования были организованы благодаря функциям разработанного калькулятора Галуа, с помощью которого производилось имитационное моделирование следующих методов декодирования циклических кодов: корреляционного (КМ) - метода максимального правдоподобия, использующего согласованные фильтры; табличного метода (ТМ) на основе анализа остатков от деления на образующий многочлен; синдромного метода (СМ), предполагающего определение корней полинома локаторов ошибок, и метода декодирования с использованием двойственного базиса (МДБ).

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

Элементы 5,- М-последовательности {5} могут быть представлены через функцию след Т(сг'), где е - первообразный корень характеристического полинома Р{х) рекуррентной последовательности; с - элемент поля GF(2*), определяющий начальную фазу М-последовательности.

Как известно, функция след от элемента е вычисляется по формуле:

Т(£) = е + е2 +е22 +... + £г"'. Из работ профессора Когновицкого О.С. следует, что начальный элемент с может быть определен по произвольному fc-элементному участку (Sg Se+t ... Ss+k- О как:

C = £-8i>,.Sg+M, (1)

(=1

где g - определяет расстояние А>элементного участка от начала М-последова-тельности, а элементы двойственного базиса Xt определяются по формуле:

I, = , 0Р(2к), ¿-1,2.....С2)

Р{г)

где Р'(г) - значение производной характеристического многочлена Р(х) в точке, соответствующей примитивному элементу поля СР(2 ).

Применяя формулы (1) и (2), по любому безошибочному участку М-после-довательности можно однозначно определить начальный элемент с, порождающий эту последовательность. В случае возникновения ошибок образуются искаженные ¿-элементные участки, при этом определяются ложные с. Таким образом, реализуется алгоритм декодирования ^-последовательности по большинству одинаковых значений элемента с, то есть мажоритарный принцип.

Дальнейшим развитием МДБ является дополнительная обработка М-последовательностей с учетом процедуры децимаций. Индекс децимации ц принимает значения 2г, где показатель г=0,(к-\), таким образом, <7=1, 2, 4, 8, ..., 2"' 1'. При этом алгоритм декодирования остается прежним, исключение составляют поступающие на его вход ¿-элементные участки ^-последовательности: 5, = т(е*), 7 = 0,1,...,(2' -1); е'6 ОБ(2*). (3)

В результате перестановки элементов М-последовательности согласно правилу (3) будут получены новые последовательности, сохраняющие рекуррентные свойства исходной М-последовательности. Таким образом, мажоритарное декодирование комбинации эквидистантного кода при помощи МДБ с использованием децимаций сводится к накоплению элементов с по сумме последовательно проводимых децимаций с учетом (1) - (3). При этом элементы с вычисляются по формуле:

Це-фЛы^У- (4)

Рассмотрим пример декодирования МДБ комбинации (011010111100010) эквидистантного кода (15,4), построенного на основе Р(х)=х4+х+1, и искаженной полиномом ошибки е=(001000010000100) (рис. 1).

Рис. 1. Декодирование МДБ комбинации кода (15,4), с тремя ошибками

Из результатов декодирования (рис. 1) видно, что решение принимается в пользу элемента с=в5 на основании мажоритарного принципа по максимальному количеству накопленных значений каждого элемента в результате обработки ^-элементных участков последовательности. Возникновение различных элементов с можно представить "ростом деревьев", "высота" которых отображает количество появлений соответствующих элементов. Вся совокупность "деревьев" представляет собой "лес", общая высота "деревьев" которого соответствует количеству ^-элементных участков, обработанных с использованием двойственного базиса с учетом децимаций с показателями г. На диаграмме "лес", построенный для каждого следующего показателя децимации г (рис. 1), учитывает также все "деревья", полученные при предыдущих значениях г.

Найденный в данном примере (рис. 1) элемент поля с=в5 в результате мажоритарного декодирования позволяет определить информационную часть принятой последовательности, для этого требуется вычислить значение функции след для к последовательных элементов поля, начиная с е5: Т(е5)Т(е6)Т(е7)Т(ещ) = (5Ь ЗД = (0110).

На примере эквидистантных кодов был проведен эксперимент, определяющий потенциальную эффективность методов декодирования. Результатом моделирования стало определение доли правильно декодированных последовательностей Рп в зависимости от кратности ошибок т| (рис. 2). При моделировании были декодированы все разрешенные кодовые комбинации с наложенными на них всевозможными комбинациями ошибок кратности т|.

Рп

\ \

МДБ-'' 2=0

\\\\ ,2=1

км'

™ __

а) л б)

Рис. 2. Зависимость /'„(л) Для эквидистантных кодов: а- (15,4); б - (31,5)

Результаты моделирования с полным перебором ошибок показали (рис. 2), что код (15,4) с ¿тш=8, гарантированно исправляющий до г=3 ошибок, имеет также возможность исправить значительную долю ошибок кратности 4. Причем, эта доля будет наибольшей (более 40%) для метода декодирования на основе двойственного базиса. Кроме того, МДБ позволяет в отличие от других методов (КМ, ТМ), исправлять и часть ошибок более высокой кратности (т|>4). Для этого кода исправление наибольшей доли ошибок до кратности 5 включительно при использовании МДБ достигается после второй децимации (г-2). В случае кода (31,5) с (¿„¡„-16, Р(х)-х'+х3+х2+х+1, использование децимаций позволило значительно приблизить корректирующие возможности МДБ к класси-

ческим методам (КМ и ТМ) при 6 < Т| < 9. Вместе с тем, использование децимаций для МДБ обеспечивает более высокие корректирующие способности при кратностях г| > 9 по сравнению с КМ и ТМ.

Полученные значения Рп(п) позволяют определить теоретическую вероятность правильного декодирования Рс теор в зависимости от рош в канале:

л-о

Построение экспериментальной зависимости РСЭксп(рош) требует, в отличие от полного перебора всех комбинаций ошибок, проведения анализа статистики декодирования потока случайных комбинаций. В результате, полученные экспериментальным путем статистические зависимости РСЖп(р0ш) при достаточно большой выборке (М=105 комбинаций) были сопоставлены теоретическим зависимостям Рстеор(Рош) и оценены по методу наименьших квадратов.

Рис. 3. Экспериментальная зависимость РСЖсп(Рош) при ЛЬЮ5 для различных методов декодирования эквидистантных кодов: а- (15,4); б - (31,5)

На основании результатов сравнения экспериментальных и теоретических зависимостей был сделан вывод, что количество декодируемых комбинаций ДО=105 является достаточным для оценки корректирующих способностей методов декодирования. Это подтверждает адекватность экспериментальной модели, применяемой для набора статистики, и целесообразность ее использования в дальнейшем при анализе методов декодирования кодов БЧХ.

Анализируя зависимости РСЖп(Рош) (рис. 3), отметим, что для кода (15,4) МДБ с применением децимаций обеспечивает лучшие результаты по сравнению с классическими методами, особенно после двух децимаций (г=2). В случае с кодом (31,5) наилучший результат декодирования методом МДБ достигается после проведения всех четырех децимаций (г=4).

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

Вторым этапом исследования является применение двойственного базиса для декодирования (/г,т)-кодов БЧХЭ (БЧХ эквивалентных), удовлетворяющих рекуррентным свойствам. Для них определяются коэффициенты двойственного базиса, которые позволяют производить обработку »¡-элементных участков, в результате чего формируется многомерный "лес". Как показано на примере кода (15,6), Р(х)=(х4+х+ 1)(х2+х+1)=х6+х5+х4+х3+1, при обработке последовательности (111011111111011) с вектором ошибки (010011000000000) определяются пары элементов е и ц, соответствующие полям ОР(2 ) и ОБ(22) (рис. 4).

Рассматриваемый код БЧХЭ (15,6) имеет с1тт-=6 и, таким образом, способен гарантированно исправлять ошибки кратности 1 и 2. Вместе с тем, как видно из рис. 4, обработка двойственным базисом позволяет исправить определенные трехкратные ошибки. Применение децимаций увеличивает "высоту правильного дерева" (5 - без децимаций, 12 - после трех децимаций), что повышает достоверность приема исходной комбинации (101000111111011).

Эксперимент, поставленный для кодов БЧХ, потребовал декодирования множества кодовых комбинаций (ЛЫО5) при значениях вероятности ошибки в канале раш=10^; 10~3; 10~2 и Ю-1. На основании результатов эксперимента построены зависимости Рсжс„(р«ш) (рис. 5).

Рис. 5. Зависимость РСжсп(Рош) при декодировании кодов БЧХ: а) - (15,6); б) - (15,7); в) - (15,8); г) - (15,9)

Анализируя полученные результаты для кодов с «=15 (рис. 5), можно заметить очевидное преимущество МДБ с децимациями перед остальными методами декодирования по корректирующей способности.

В работе были также исследованы коды БЧХ с характеристикой л=31: (31,6), (31,10), (31,15) и (31,20). На примере кода (31,15) (рис. 6) показано преимущество МДБ перед классическими методами декодирования. Во всех остальных случаях наблюдается стремление МДБ посредством децимаций приблизиться к КМ, показывающему несколько лучшие результаты декодирования.

Для кодов (15,5), (15,6) и (15,7) (рис. 5) и всех исследованных в работе кодов с характеристикой //=31 последовательное применение децимаций положительно сказывается на качестве декодирования. Так, например, из рис. 6 видно, что накопление "деревьев" по сумме всех децимаций (г=4) обеспечивает более эффективное декодирование для МДБ, чем классические методы.

Таким образом, при обработке комбинаций кода БЧХ как рекуррентных последовательностей с длинами п=15 и /¡=31 каждая дополнительная децимация в общем случае повышает Рс. При возникновении в комбинациях данных кодов более чем одной ошибки имеет смысл применять все децимации.

Развитием МДБ является введение порогового значения "высоты максимального дерева". Если максимальное "дерево" ниже заданного порога, проис-

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

0.8 Ов

Рс

0.4 0.2

Рош

Рис. 6. Экспериментальная

ЗАВИСИМОСТЬ гсэксп

(рош) при №=10 при различных методах декодирования для кода (31,15)

В диссертационной работе также был проведен детальный анализ результатов декодирования кода (31,20), на примере которого показано, что МДБ позволяет исправлять пачки ошибок, кратность которых превышает гарантированно исправляемую кратность ошибок в соответствии с с!т1п кода. Корректирующие способности кода проявляют себя в большей степени при группировании ошибок, чем в канале с независимыми ошибками. Данное свойство может оказаться полезным для каналов с памятью. Вместе с тем, в работе предложена дополнительная процедура для МДБ, обеспечивающая повышение корректирующих свойств кода в канале без памяти, но понижающая возможность исправления пачек ошибок. Данный подход МДБ-ВФ (метод двойственного базиса с виртуальными фильтрами) аналогичен корреляционному методу, но в отличие от него не требует наличия согласованных фильтров и работает по принципу сложения принятой последовательности только с разрешенными кодовыми комбинациями, сформированными по выделенным "деревьям".

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

При использовании статических накопителей (МДБ-СН) производится выделение памяти под всевозможные совокупности элементов, которые могут быть получены после обработки т-элементных участков циклического (п,т)-кода. Применение динамических накопителей (МДБ-ДН) позволяет значи-

тельно сэкономить ресурсы системы, так как при этом работать будут только выделенные в процессе декодирования накопители.

Сравнительный анализ ресурсоемкости показал, что метод МДБ-ДН по затратам памяти лежит в пределах одного порядка с методом СМ. Методы КМ и ТМ оказались значительно более ресурсоемкими, особенно в случае с кодом (31,16), для которого КМ требует В> 10 байт. Очевидно, что для более длинных кодов это может ограничить применение данных методов.

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

Если после обработки принятой комбинации без децимаций (г=0), максимальная "высота дерева" будет больше, чем (и-ш-1), что характерно для "хороших" каналов связи, то последующие децимации (г>0) применять не следует. При этом отсутствует необходимость хранения принятой последовательности в накопителе, и реализация декодера МДБ сводится к минимуму. Однако если канал "плохой" и кратность ошибок г|>1, как правило, требуется проведение децимаций. В этом случае принятая комбинация должна храниться в памяти.

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

В работе приведены два метода оценки качества канала на основе обработки кодов БЧХЭ двойственным базисом. Первый метод предполагает определение показателя Я - среднего отклонения Д между максимальным "деревом" и ближайшим к нему "деревом" по высоте: Л=ф1-<р2, где ф!=тах{С,}; ф2 = тах{С,}, С-, Ф фь г=1, 2,.., (2*-1) для поля СР(2*). Данный показатель вычисляется по формуле:

N Д

и

где N - число принятых комбинаций. Приведенная в работе методика позволяет на основании величины показателя Я определить доверительный интервал (ротп, Роаах), в котором находится истинная вероятность ошибки в канале.

Второй метод оценки канала основан на определении показателя ], который представляет собой среднюю частоту появления "деревьев" при обработке т-элементных участков принимаемой последовательности:

ъ,=

1, новое "дереве!'

(6)

.. [О, приращение "деревеГ где Ь, - фактор появления нового "дерева" при обработке г'-го »¡-элементного участка у'-ой последовательности, ^ - количество обработанных т-элементных участков в пределах 7-ой последовательности. Согласно методике, приведенной в работе, на основании показателя J определяется интервал (ршт Ротах)-

В отличие от первого второй метод оценки канала по частоте появления "деревьев" не требует приема всей комбинации целиком. Вычисление показателя 3 производится по результатам обработки т-элементных участков, то есть оценка вероятности ошибки ведется последовательно в процессе приема кодовых комбинаций. Процесс вычисления доверительного интервала (р(ып\ ротах) является автономным и не использует результаты декодирования кодовых комбинаций. Из рис. 7 видно, что вычисленная по предложенной методике вероятность р0 для случая с накоплением Ь=Ып двоичных элементов, где Ь - общее число обработанных т-элементных участков во всех N последовательностях, с увеличением Ь сколь угодно близко стремится к рош модели канала.

Рис. 7. Оценка качества канала по частоте появления "деревьев", определение границ /?отт и /?о1Па, при декодировании комбинаций кода (15,6)

Отметим, что проведенное в работе сравнение методов оценки канала показало, что точность определения рош у второго метода по частоте появления "деревьев" выше, чем у первого. Это можно объяснить большим размером выборки второго (в п раз) по сравнению с первым методом.

Для обоих методов на примере кодов /¡=15 при заданных N=100 (¿=1500) и различных значениях рош в канале были определены доверительные интервалы (Р(ы„', Ропах)- Таким образом, были получены и аппроксимированы зависимости /?0тш(#); РотАН) - для первого и р0тш(1); ротахСО - для второго метода оценки качества канала. Показано, что предварительное построение функций для ниж-

ней и верхней границ диапазона (ротт, Роты) для различных N (L- для второго метода) значительно упрощает процесс последующего их нахождения.

В четвертой главе разработана имитационная модель системы с адаптивным выбором кода, в основу которой положен метод оценки качества канала с использованием двойственного базиса. В качестве входных параметров выбирается критерий оценки: вероятность правильного Рс или ложного Ре декодирования. Задается параметр NA, определяющий минимальное количество принятых последовательностей N, после которого начинается проверка соответствия критерию оценки результатов обработки и становится возможным переход на более подходящий код из заданного множества. В качестве примера заданы следующие коды: (15,4), (15,6) и (15,11).

Определение интервала (pomin ; /w) производится при обработке ш-эле-ментных участков двойственным базисом методом оценки канала по частоте появления "деревьев" с учетом L=nN. В работе этот интервал (/?|)тш; ротах) вычисляется при значениях L, кратных N, что обусловлено упрощенной реализацией имитационной модели. Критерием оценки являются вероятности правильного PC(njn) или ложного Ре(п,т) декодирования циклического (л,ш)-кода, для которых по результатам набора статистики (ЛГ=105) были построены зависимости ош ) И Ре{„ .т ОШ ) (рис. 8).

Рис. 8. Экспериментальные зависимости для кодов: а - 1\<„,т1(РошУ, б - Ре<„,т)(Рош)

В качестве анализируемого параметра выступает роаЧ=(ршп+Ропшх)12- При выполнении условия ТУ>Л/4 начинается проверка соответствия критерия оценки РсМ(Рош) или Ре(„,т,(Рош) при рош=ра>ч требуемой величине Рс или Ре, соответственно. Должно выполняться одно из двух условий:

Рс(п,т){Р0ь\?)>Рс ИЛИ Ре(п,т)(РОап)<Ре- О)

В случае невыполнения условия (7) по выбранному критерию осуществляется переход на более помехоустойчивый код, если такой доступен в системе. При этом происходит обнуление счетчика /V, и снова начинается накопление элементов с обработкой /«-элементных участков принимаемых последовательностей. В случае, когда наблюдается улучшение состояния канала, характеризуемого уменьшением величины рош, или происходит снижение требований к параметрам Рс и Ре, возможен переход на менее помехоустойчивый код, кото-

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

■ код (15,11).;'.

КОЯ (15,6) •

КОЯ (15,4)

код

Ш)

га и а а

код (15.11)

с

5 81 я 5, ¡я я &

Рис. 9. Диаграмма перехода системы с критерием оценки 0,95 и Л^=10 : а - на более помехоустойчивый код; б - на менее помехоустойчивый код

В первом случае (рис. 9, а) происходит адаптация системы при ухудшении качества канала. Первоначальное использование системой кода (15,11) с накоплением N приближает р0т к реальной рош=0,023, условие (7) выполняется, но при N=2-103 происходит скачкообразный рост вероятности ошибки до 0,098. Система продолжает считать канал стационарным и ведет обработку принятых последовательностей, при этом происходит проверка условия (7). С накоплением N>3- Ю3 (¿>4,5-104) условие (7) перестает выполняться, принимается решение о переходе на более помехоустойчивый код (15,6), при этом обнуляется счетчик N. С накоплением ЛЬЛ/д=103 начинается проверка условия (7). Выясняется, что условие (7) не выполняется, и, следовательно, требуется переход на еще более помехоустойчивый код (15,4). Подобная система может быть построена с учетом перехода от текущего кода сразу к наилучшему, минуя про-

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

Во втором случае (рис. 9, б) происходит улучшение качества канала. После приема Л^.З-Ю3 рош снижается с 0,083 до 0,018. Аналогично предыдущему случаю, система проверяет условие (7), которое перестает выполняться при ЛГ>2-103. Система переходит на менее избыточный код (15,6), при этом счетчик N обнуляется. При накоплении N=NA=\03 снова начинается проверка условия (7), которое опять не выполняется. Таким образом, происходит переход системы на еще менее помехоустойчивый код (15,11). При этом повышается скорость передачи данных с 4/15 при рош-0,083 до 11/15 при /?ош=0,018.

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

В работе была проанализирована актуальная задача выбора способов формирования и хранения поля. Статическое поле предполагает постоянное хранение всех элементов в памяти. При этом использование ячеек памяти для хранения элементов малого поля является не совсем целесообразным, так как это не дает ощутимого выигрыша при использовании мощных процессоров. Современные микропроцессоры способны обеспечить максимально быструю обработку команд, поэтому для небольших полей целесообразно генерировать элементы поля динамически. Метод динамической генерации элементов поля в калькуляторе Галуа используется при работе с полями до GF(220) включительно. Вместе с тем, любые системы, использующие метод построения динамического поля, обладают недостатком, связанным с неизбежными временными затратами. Поэтому, начиная с полей GF(221) и заканчивая GF(231), в калькуляторе Галуа применяется метод контрольных точек, предполагающий хранение только части поля в памяти, а точнее, некоторых его элементов, взятых с определенным интервалом. Таким образом, доступ к любому произвольному элементу поля осуществляется через определенный элемент, хранящийся в оперативной памяти. Исследования, проведенные в работе, показали, что это значительно сокращает время выполнения операций и делает калькулятор Галуа гибким инструментом в работе с полями больших размеров.

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

Требования к серверной части затрагивают, прежде всего, мощность вычислительного устройства. Наличие мощного процессора позволяет ускорить вычисления и оперативно отправить результат пользователю. В качестве операционной системы может выступать как Windows, так и Linux, что делает вэб-приложение универсальным. Для функционирования клиентской части требуется наличие Интрернет-обозревателя и соединение с Интернетом.

В настоящее время разработанный вэб-калькулятор Галуа расположен в Интернете по адресу: http://www.webgalois.spb.ru.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведен сравнительный анализ эффективности методов декодирования циклических кодов, в результате которого отмечено, что применение двойственного базиса по сравнению с классическими методами (корреляционным, табличным и синдромным) обеспечивает более высокий уровень достоверности передачи данных. В качестве примеров рассмотрены ^-последовательности, коды БЧХ длиной п=15, а также ряд кодов БЧХ с п=31.

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

3. Установлено, что метод декодирования на основе двойственного базиса позволяет исправлять ошибки, кратность которых превышает гарантированно исправляемую кратность ошибок в соответствии с d^,a кода. При этом корректирующие способности кода проявляют себя в большей степени при группировании ошибок, чем в канале с независимыми ошибками.

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Кукунин Д.С., Охорзин В.М., Новодворские М.С. Построение каскадных кодов на основе Боуза-Чоудхури-Хоквингема и Рида-Соломона: Методические указания по курсовому проектированию (спец. 220200) / СПбГУТ. СПб, 2004. 58С.

2. Кукунин Д.С., Когновицкий О.С. Сетевая версия калькулятора Галуа// 57-я Юбилейная НТК профессорско-преподавательского состава: мат-лы / СПбГУТ. СПб, 2005. С.25.

3. Кукунин Д.С., Когиовицкий О.С. Анализ методов декодирования эквидиствнтных кодов II 58-я НТК профессорско-преподавательского состава: мат-лы / СПбГУТ. СПб,

2006. С. 17.

4. Кукунин Д.С., Когновицкий О.С. Оценка качества канала с помощью псевдослучайных последовательностей // 58-я НТК профессорско-преподавательского состава: мат-лы / СПбГУТ. СПб, 2006. С. 17.

5. Кукунин Д.С., Когновицкий О.С. Метод декодирования эквидистантных кодов // Труды учебных заведений связи / СПбГУТ. СПб, 2006. № 174. С.45-52. (из перечня изданий, рекомендованных ВАК).

6. Кукунин Д. С. Декодирование Л/-последователыюстей с применением двойственного базиса поля Галуа // 59-я НТК студентов, аспирантов и молодых специалистов: мат-лы / СПбГУТ. СПб, 2006. С.19-23.

7. Кукунин Д.С., Когновицкий О.С. Метод оценки качества канала передачи данных при декодировании циклических кодов как рекурсивных последовательностей // 59-я НТК профессорско-преподавательского состава: мат-лы / СПбГУТ. СПб, 2007. С.26.

8. Кукунин Д.С. Калькулятор Галуа с удаленным доступом через Интернет // 59-я НТК профессорско-преподавательского состава: мат-лы / СПбГУТ. СПб, 2007. С.31.

9. Кукунин Д.С., Когновицкий О.С. Методика оценки качества канала при передаче рекурсивных последовательностей // Труды учебных заведений связи / СПбГУТ. СПб,

2007. № 176. С.155-165.

10. Кукунин Д.С., Когновицкий О.С. Адаптация системы передачи к состоянию канала // 60-я НТК профессорско-преподавательского состава: мат-лы / СПбГУТ. СПб, 2008. С.28-29.

11. Кукунин Д.С., Когновицкий О.С. Методика оценки качества канала в процессе передачи данных // Научно-технические ведомости / СПбГПУ. СПб, 2008. № 5. С.86-92. (из перечня изданий, рекомендованных ВАК).

12. Кукунин Д.С. Модель системы с адаптивным выбором кода// Научно-технические ведомости / СПбГПУ. СПб, 2008. № 5. С.81-86. (из перечня изданий, рекомендованных ВАК).

13.Кукунин Д.С., Когновицкий О.С. Сравнительный анализ методов декодирования циклических кодов БЧХ // 61-я НТК профессорско-преподавательского состава: мат-лы / СПбГУТ. СПб, 2009. С.46.

14. Кукунин Д.С., Березкин A.A. Нейроцифровая реализация перспективных методов передачи данных с использованием двойственного базиса //61-я НТК профессорско-преподавательского состава: мат-лы / СПбГУТ. СПб, 2009. С.47-48.

15.Кукунин Д.С. Дискретное логарифмирование в полях Галуа с использованием контрольных точек // Научно-технические ведомости / СПбГПУ. СПб, 2009. № 2. С. 186-192. (из перечня изданий, рекомендованных ВАК).

Подписано к печати 29.05.2009 Объем 1 печ. л. Тираж 80 экз. Зак. 18

Тип. СПбГУТ, 191186 СПб, наб. р. Мойки, 61

Введение.

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

1.1. Двойственный базис поля Галуа.

1.2. Применение двойственного базиса.

1.3. Проблемы работы с полями Галуа.

1.4. Выводы. Задачи диссертационной работы.

2. Анализ эффективности декодирования двоичных циклических кодов

2.1. Особенности построения двоичных циклических кодов.

2.1.1. Двоичные циклические коды БЧХ.

2.1.2. Построение циклических кодов как рекурсивных последовательностей.

2.1.3. Коды максимальной длины.

2.2. Методы декодирования циклических кодов.

2.2.1. Оцениваемые параметры системы передачи данных.

2.2.2. Алгебраический декодер. Таблица остатков.

2.2.3. Корреляционный метод.

2.2.4. Синдромный метод декодирования кодов БЧХ.

2.3. Обработка рекуррентных последовательностей двойственным базисом поля Галуа

2.3.1. Декодирование кодов максимальной длины.

2.3.2. Использование децимаций при декодировании кодов максимальной длины.

2.3.3. Декодирование кодов БЧХЭ.

2.3.4. Эффективность методов декодирования кодов БЧХ.

2.4. Выводы.

3. Разработка методов оценки качества канала.

3.1. Особенности методов оценки качества канала.

3.2. Разработка методов оценки качества канала на основе двойственного базиса.

3.2.1. Метод разности двух наибольших "деревьев".

3.2.2. Метод оценки канала по частоте появления "деревьев".

3.2.4. Выбор метода оценки канала.

3.3. Выводы.

4. Разработка методики адаптации системы к состоянию канала.

4.1. Подходы к построению адаптивных систем.

4.2. Система с адаптивным выбором кода.

4.3. Выводы.

5. Разработка инструментария для работы в полях Галуа.

5.1. Программная реализация калькулятора Галуа.

5.1.1. Формирование поля и его хранение.

5.1.2. Реализация базовых операций в калькуляторе Галуа.

5.1.3. Особенности работы с полем большого порядка.

5.1.4. Метод контрольных точек.

5.2. Организация калькулятора Галуа.

5.2.1. Структура калькулятора Галуа.

5.2.2. Калькулятор Галуа для работы в локальной сети.

5.2.3. Калькулятора Галуа для работы в глобальной сети.

5.3. Выводы.

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

Классическое описание циклических кодов опирается на такие понятия, как кодовое расстояние и избыточность, что способствует выбору кода с заданными параметрами. Исследуемые в данной работе циклические коды составляют большой спектр от "медленных" до "быстрых" помехоустойчивых кодов, обладающих минимальными корректирующими способностями. При этом особое внимание уделяется двоичным кодам БЧХ.

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

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

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

Методы исследования. Проводимые исследования основываются на теории полей Галуа, теории двойственного базиса поля Галуа, теории кодирования, теории рекуррентных регистров сдвига и теории вероятностей. Для проведения численных расчетов использовались программные пакеты: MS Excel 2003, Mathcad 13, Advanced Grapher 2.11 и другие. Программное обеспечение, необходимое для решения поставленных в диссертации задач, реализовано в среде MS Visual С++ 6.0.

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

1. Исследован новый метод декодирования кодов БЧХ как рекуррентных последовательностей с использованием двойственного базиса.

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

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

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

5. Предложен новый вариант реализации дискретного логарифмирования в

Л | полях Галуа до GF(2 ) с использованием контрольных точек.

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

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

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

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

В качестве основного инструмента для проведения экспериментов был использован разработанный диссертантом программный комплекс — калькулятор

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

Реализация результатов работы. Основные научные результаты работы внедрены в практическую деятельность ЗАО Н1111 «ИСТА-Системс», а также используются в учебном процессе Санкт-Петербургского государственного университета телекоммуникаций им. проф. М.А. Бонч-Бруевича, что подтверждено соответствующими актами внедрения.

Апробация работы. Результаты работы обсуждались и были одобрены на 57, 58, 59, 60, 61 НТК профессорско-преподавательского состава и 57, 58, 59, 60 НТК студентов, аспирантов и молодых специалистов СПбГУТ. По результатам диссертации опубликованы работы [3, 10, 84, 85, 87, 119, 121 - 124, 126- 130].

Структура и объем работы. Диссертация состоит из введения, 5 глав, заключения и приложений. Работа содержит 169 страниц машинописного текста, 71 рисунок, 19 таблиц и список литературы из 130 наименований.

4.3. Выводы

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

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

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

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

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

Глава 5. Разработка инструментария для работы в полях Галуа

5.1. Программная реализация калькулятора Галуа

5.1.1. Формирование поля и его хранение

Поле GF(2*) представляет собой набор элементов 1,8,8 ,., 8 , количество которых 2k-l определяет порядок поля. Каждому элементу ет поля GF(2A) соответствует вектор, состоящий из к бит. Таким образом, программная реализация функций работы с полем требует определенных затрат ресурсов. В целях экономии памяти и рационального использования процессора, на который возлагается обработка операций над элементами, целесообразно выделять на хранение векторов и показателей степеней элементов целые числа.

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

Данную задачу можно решить с использованием языка программирования С++. Сначала определим переменные, необходимые для построения поля Галуа с заданными характеристиками. Для примера построим поле с характеристикой к=4 и характеристическим многочленом P(jc)=1+jc+jc4 [3]: int k=4; int n=15; int vector[15]; int exponents 6];.

Переменная к соответствует, вышеуказанному параметру поля, п=2к—\ определяет число ненулевых элементов. В данной ситуации нецелесообразно хранить в памяти нулевой элемент поля.

Массив vector содержит переменные, соответствующие векторам поля. Число элементов массива равно числу ненулевых элементов поля. Векторы поля будут храниться в памяти в виде целых чисел. В Windows при использовании 32-разрядных приложений на число типа int отводится 4 байта. Данное

147 свойство позволяет работать с полями GF(2*) с характеристикой до к=31 включительно. Для работы с большими полями требуются свои типы данных.

Дальнейшая методика построения поля состоит в определении вычета, который представляет собой часть характеристического многочлена без старшей степени. Для вычет в двоичном виде будет иметь вид (1100), что соответствует числу 12 в десятичной системе счисления: int Polinom=l2;

Формирование поля происходит путем сдвигов векторов с добавлением к ним вычета. Сначала необходимо определить первый элемент поля е°, соответствующий вектору (1000): vector[0]=1«k-1;.

Далее происходит присвоение первого элемента дополнительной переменной alpha, которая необходима для вычисления остальных векторов поля [3]: int alpha=vector[0]; for(inti=1;i<n;i++){ asm shr alpha, 1 asm jnc label alpha=alphaAPolinom; label: vector[i]=alpha;}.

Ассемблерная команда shr производит битовый сдвиг вправо. Бит, выходящий за пределы числа, помещается в регистр флагов в бит CF. Если в CF оказывается единица, к вектору добавляется вычет по mod 2. После этих операций массив vector будет хранить в памяти целые числа (табл. 5.1) [3].

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

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

1. Проведен сравнительный анализ эффективности методов декодирования циклических кодов, в результате которого отмечено, что применение двойственного базиса по сравнению с классическими методами (корреляционным, табличным и синдромным) обеспечивает более высокий уровень достоверности передачи данных. В качестве примеров рассмотрены М-последовательности, коды БЧХ длиной п=\ 5, а также ряд кодов БЧХ с я=31.

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

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

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

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

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

1. Когновицкий О.С. Основы циклических кодов: Учеб. пособие. — Л., 1972.

2. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М., 1976.

3. Кукунин Д.С., Охорзин В.М., Новодворский М.С. Построение каскадных кодов на основе кодов БЧХ и Рида-Соломона. СПб., 2004. 58 С.

4. Касами Т., Токура Н., Ивадари Ё., Инагаки Я. Теория кодирования. — М., 1978.

5. Когновицкий О.С. Алгебраический метод нахождения двойственного базиса в поле Галуа и его практическое применение // Сборник научных трудов учебных институтов связи, -JL, 1982.

6. Когновицкий О.С. Об одном алгоритме мажоритарного декодирования кодов максимальной длины / Девятая всесоюзная конференция по теории кодирования и передачи информации. Тезисы докладов. Часть 1. Одесса, 1988.

7. Когновицкий О.С., Свердлов JI.M. Мажоритарное декодирование М-последовательно-стей с использованием децимаций // 49-я НТК: тез. докл./ СПбГУТ. СПб, 1996.

8. Когновицкий О.С. Метод мажоритарной обработки псевдослучайной последовательности по ^-произвольным линейно независимым ее элементам // 49-я НТК: тез. докл./ СПбГУТ. СПб, 1996.

9. Когновицкий О.С. Алгоритмы обработки рекуррентных псевдослучайных последовательностей в задачах передачи данных // Юбилейная НТК: тез. докл./ СПбГУТ. СПб, 2000.

10. Кукунин Д.С., Когновицкий О.С. Метод декодирования эквидистантных кодов // Труды учебных заведений связи / СПбГУТ. СПб, 2006. № 174. С. 45-52.

11. Когновицкий О.С. Мажоритарное декодирование циклических кодов как рекуррентных последовательностей с разложимым характеристическим многочленом // 50-я НТК: тез. докл./СПбГУТ. СПб, 1997.

12. Когновицкий О.С. Метод алгебраического кодового разделения рекуррентных последовательностей с различными характеристическими многочленами // 51-я НТК: тез. докл./ СПбГУТ. СПб, 1998.

13. Когновицкий О.С. Аналитические методы решения линейных модулярных разностных уравнений и их сравнение // 52-я НТК: тез. докл./ СПбГУТ. СПб, 1999.

14. Когновицкий О.С. Реализационные основы применения двойственного базиса поля Галуа в задачах передачи и обработки данных // 54-я НТК: тез. докл./ СПбГУТ. СПб, 2002.

15. Когновицкий О.С. Циклические коды БЧХЭ как рекурсивные последовательности // Труды учебных заведений связи / СПбГУТ. СПб, 2006.

16. Когновицкий О.С. Циклические коды Рида-Соломона как рекурсивные последовательности // 57-я НТК: тез. докл./ СПбГУТ. СПб, 2005.

17. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. Перевод с англ. М.: Радио и связь, 1987.

18. Zook Christopher P. Finite Field Inversion // Патент WO 95/12845. May 11.- 1995.

19. Zook Christopher P. Finite Field Inversion // Патент US 5,467,297. -Nov. 14. 1995.

20. Fenn S.T.J., Benaissa M., Taylor D. GF(2*) Multiplication and Division Over the Dual Basis // IEEE Transactions on Computers. 1996. - Vol. 45. - P. 319-327.

21. Fenn S.T.J., Benaissa M„ Taylor D. Finite Field Inversion Over the Dual Basis // IEEE Transactions on VLSI Systems. 1996. - Vol. 4. - n. 1. - P. 134-137.

22. Chiou-Yng Lee, Che Wun Chiou, Jim-Min Lin Concurrent Error Detection in a Bit-Parallel Systolic Multiplier for Dual Basis of GF(2m) // Journal of Electronic Testing: Theory and Applications. 2005. - Vol. 21. - P. 539-549.

23. Burton S. Kaliski Jr., Yiqun Lisa Yin Method and apparatus for efficient finite field basis conversion // Патент US 5,854,759. Dec. 29. - 1998.

24. Lambert R„ Gallant R„ Mullin R., Scott A. Vanstone Method and apparatus for finite field basis conversion 11 Патент US 2002/0025038 Al. Feb. 28. - 2002.

25. Weon-Il Jin, Mi-Suk Hun, Shang-Woo Seo Method and apparatus for basis conversion in finite field // Патент US 2004/0098437 Al. May 20. - 2004.

26. Weon-Il Jin Method and apparatus for basis conversion in finite field and a multiplier // Патент ЕР 1 455 270 A2. Sept. 8. - 2004.

27. Weon-Il Jin Method and apparatus for basis conversion in finite field and a multiplier // Патент ЕР 1 455 270 A3. Jun. 28. - 2006.

28. Chang-Hyi Lee, Jong-In Lim A New Aspect of Dual Basis for Efficient Field Arithmetic // PKC'99, LNCS 1560. 1999. - P. 12-28.

29. Zook Christopher P. Method and apparatus for determining the coefficients of a locator polynomial // Патент US 4,845,713. Jul. 4. - 1989.

30. Ba-Zhong Shen Error correction system for five or more errors // Патент US 6,343,367 B1. -Jan. 29. 2002.

31. ТанакаХ., Касахара M. Использование регистров сдвига для вычислений в полях Галуа // Экспресс-информация. Передача информации. 1969. - №2.

32. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971.33