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

Размещено на http://www.allbest.ru/

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

Автореферат диссертации

на соискание ученой степени кандидата технических наук

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

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

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

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

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

Научный руководитель кандидат технических наук, профессор Когновицкий Олег Станиславович.

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

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

Ведущее предприятие ФГУП ЛОНИИС, г. Санкт-Петербург.

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

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

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

Автореферат разослан «1» июня 2009 года.

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

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

циклический двоичный базис декодирование

Содержание работы

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

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

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

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

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

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

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

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

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

Элементы S_i M-последовательности {S} могут быть представлены через функцию след T(c?ⁱ), где ? - первообразный корень характеристического полинома P(x) рекуррентной последовательности; c - элемент поля GF(2^k), определяющий начальную фазу M-последовательности.

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

.

Из работ профессора Когновицкого О.С. следует, что начальный элемент c может быть определен по произвольному k-элементному участку (S_g S_g+1 ... S_g+k1) как:

, (1)

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

, GF(2^k), i=1, 2, …, k, (2)

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

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

Дальнейшим развитием МДБ является дополнительная обработка M-последовательностей с учетом процедуры децимаций. Индекс децимации q принимает значения 2^z, где показатель z=0, ..., (k1), таким образом, q=1, 2, 4, 8, …, 2^(k-¹⁾. При этом алгоритм декодирования остается прежним, исключение составляют поступающие на его вход k-элементные участки M-последовательности:

; еⁱGF(2^k). (3)

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

. (4)

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

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

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

Найденный в данном примере (рис. 1) элемент поля с=е⁵ в результате мажоритарного декодирования позволяет определить информационную часть принятой последовательности, для этого требуется вычислить значение функции след для k последовательных элементов поля, начиная с е⁵:

T(е⁵)T(е⁶)T(е⁷)T(е⁸) = (S₀ S₁ S₂ S₃) = (0110).

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



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

P(x)=x⁵+x³+x²+x+1,

использование децимаций позволило значительно приблизить корректирующие возможности МДБ к классическим методам (КМ и ТМ) при

.

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

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

.

Построение экспериментальной зависимости P_c.эксп(p_ош) требует, в отличие от полного перебора всех комбинаций ошибок, проведения анализа статистики декодирования потока случайных комбинаций. В результате, полученные экспериментальным путем статистические зависимости P_c.эксп(p_ош) при достаточно большой выборке (N=10⁵ комбинаций) были сопоставлены теоретическим зависимостям P_c.теор(p_ош) и оценены по методу наименьших квадратов.

Рис. 3. Экспериментальная зависимость Pc.эксп(pош) при N=105 для различных методов декодирования эквидистантных кодов: а - (15,4); б - (31,5)

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

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

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

Вторым этапом исследования является применение двойственного базиса для декодирования (n,m)-кодов БЧХЭ (БЧХ эквивалентных), удовлетворяющих рекуррентным свойствам. Для них определяются коэффициенты двойственного базиса, которые позволяют производить обработку m-элементных участков, в результате чего формируется многомерный «лес». Как показано на примере кода (15,6),

P(x)=(x⁴+x+1)(x²+x+1)=x⁶+x⁵+x⁴+x³+1,

при обработке последовательности (111011111111011) с вектором ошибки (010011000000000) определяются пары элементов е и м, соответствующие полям GF(2⁴) и GF(2²) (рис. 4).



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

Эксперимент, поставленный для кодов БЧХ, потребовал декодирования множества кодовых комбинаций (N=10⁵) при значениях вероятности ошибки в канале p_ош=10-⁴; 10-³; 10-² и 10-¹. На основании результатов эксперимента построены зависимости P_c.эксп(p_ош) (рис. 5).



Рис. 5. Зависимость Pc.эксп(pош) при декодировании кодов БЧХ:

а) - (15,6); б) - (15,7); в) - (15,8); г) - (15,9)

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

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

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

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

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

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

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

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

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

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

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

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

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

В работе приведены два метода оценки качества канала на основе обработки кодов БЧХЭ двойственным базисом. Первый метод предполагает определение показателя H - среднего отклонения Д между максимальным «деревом» и ближайшим к нему «деревом» по высоте:

Д=ц₁-ц₂,

где ц₁=max{С_i}; ц₂ = max{С_i}, С_i ? ц₁, i=1, 2, .., (2^k-1) для поля GF(2^k).

Данный показатель вычисляется по формуле:

, (5)

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

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

, (6)

где b_i - фактор появления нового «дерева» при обработке i-го m-элементного участка j-ой последовательности, l_j - количество обработанных m-элементных участков в пределах j-ой последовательности. Согласно методике, приведенной в работе, на основании показателя J определяется интервал (p_0min; p_0max).

В отличие от первого второй метод оценки канала по частоте появления «деревьев» не требует приема всей комбинации целиком. Вычисление показателя J производится по результатам обработки m-элементных участков, то есть оценка вероятности ошибки ведется последовательно в процессе приема кодовых комбинаций. Процесс вычисления доверительного интервала (p_0min; p_0max) является автономным и не использует результаты декодирования кодовых комбинаций. Из рис. 7 видно, что вычисленная по предложенной методике вероятность p₀ для случая с накоплением L=Nn двоичных элементов, где L - общее число обработанных m-элементных участков во всех N последовательностях, с увеличением L сколь угодно близко стремится к p_ош модели канала.

Рис. 7. Оценка качества канала по частоте появления «деревьев», определение границ p0min и p0max при декодировании комбинаций кода (15,6)

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

Для обоих методов на примере кодов n=15 при заданных N=100 (L=1500) и различных значениях p_ош в канале были определены доверительные интервалы (p_0min; p_0max). Таким образом, были получены и аппроксимированы зависимости p_0min(H); p_0max(H) - для первого и p_0min(J); p_0max(J) - для второго метода оценки качества канала. Показано, что предварительное построение функций для нижней и верхней границ диапазона (p_0min; p_0max) для различных N (L - для второго метода) значительно упрощает процесс последующего их нахождения.

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

Определение интервала (p_0min; p_0max) производится при обработке m-элементных участков двойственным базисом методом оценки канала по частоте появления «деревьев» с учетом L=nN. В работе этот интервал (p_0min; p_0max) вычисляется при значениях L, кратных N, что обусловлено упрощенной реализацией имитационной модели. Критерием оценки являются вероятности правильного P_c(n,m) или ложного P_e(n,m) декодирования циклического (n,m)-кода, для которых по результатам набора статистики (N=10⁵) были построены зависимости P_c(n,m)(p_ош) и P_e(n,m)(p_ош) (рис. 8).



В качестве анализируемого параметра выступает

p_0avg=(p_0min+p_0max)/2.

При выполнении условия

N>N_A

начинается проверка соответствия критерия оценки P_c(n,m)(p_ош) или P_e(n,m)(p_ош) при

p_ош=p_0avg

требуемой величине P_c или P_e, соответственно. Должно выполняться одно из двух условий:

P_c(n,m)(p_0avg)>P_c или P_e(n,m)(p_0avg)<P_e. (7)

В случае невыполнения условия (7) по выбранному критерию осуществляется переход на более помехоустойчивый код, если такой доступен в системе. При этом происходит обнуление счетчика N, и снова начинается накопление элементов с обработкой m-элементных участков принимаемых последовательностей. В случае, когда наблюдается улучшение состояния канала, характеризуемого уменьшением величины p_ош, или происходит снижение требований к параметрам P_с и P_e, возможен переход на менее помехоустойчивый код, который должен повысить информационную скорость передачи. Переходные процессы показаны на временных диаграммах (рис. 9).

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

В первом случае (рис. 9, а) происходит адаптация системы при ухудшении качества канала. Первоначальное использование системой кода (15,11) с накоплением N приближает p_0avg к реальной p_ош=0,023, условие (7) выполняется, но при N?2·10³ происходит скачкообразный рост вероятности ошибки до 0,098. Система продолжает считать канал стационарным и ведет обработку принятых последовательностей, при этом происходит проверка условия (7). С накоплением N>3·10³ (L>4,5·10⁴) условие (7) перестает выполняться, принимается решение о переходе на более помехоустойчивый код (15,6), при этом обнуляется счетчик N. С накоплением N=N_A=10³ начинается проверка условия (7). Выясняется, что условие (7) не выполняется, и, следовательно, требуется переход на еще более помехоустойчивый код (15,4). Подобная система может быть построена с учетом перехода от текущего кода сразу к наилучшему, минуя промежуточные, но в данном случае требовалось показать процесс поэтапного перехода между кодами в соответствии с критерием оценки.

Во втором случае (рис. 9, б) происходит улучшение качества канала. После приема N?1,3·10³ p_ош снижается с 0,083 до 0,018. Аналогично предыдущему случаю, система проверяет условие (7), которое перестает выполняться при N>2·10³. Система переходит на менее избыточный код (15,6), при этом счетчик N обнуляется. При накоплении N=N_A=10³ снова начинается проверка условия (7), которое опять не выполняется. Таким образом, происходит переход системы на еще менее помехоустойчивый код (15,11). При этом повышается скорость передачи данных с 4/15 при p_ош=0,083 до 11/15 при p_ош=0,018.

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

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

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

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

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

Основные результаты работы

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

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

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

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

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

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

Список публикаций по теме диссертации

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

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

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

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

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

6. Кукунин Д.С. Декодирование M-последовательностей с применением двойственного базиса поля Галуа // 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. Кукунин Д.С., Березкин А.А. Нейроцифровая реализация перспективных методов передачи данных с использованием двойственного базиса // 61-я НТК профессорско-преподавательского состава: мат-лы / СПбГУТ. СПб, 2009. С.47-48.

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

Подписано к печати 29.05.2009

Объем 1 печ. л. Тираж 80 экз. Зак. 18

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

Размещено на Allbest.ru

...