Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

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

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

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

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Березкин Александр Александрович. Модели и методы декодирования помехоустойчивых кодов на основе нейросетевого базиса : диссертация ... кандидата технических наук : 05.13.01 / Березкин Александр Александрович; [Место защиты: С.-Петерб. гос. ун-т телекоммуникаций им. М.А. Бонч-Бруевича].- Санкт-Петербург, 2009.- 190 с.: ил. РГБ ОД, 61 09-5/2877

Содержание к диссертации

Введение

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

1.1. Постановка задачи декодирования 11

1.2. Анализ методов «мягкого» декодирования блоковых кодов 15

1.3. Искусственные нейронные сети в задаче декодирования блоковых кодов 18

1.4. Проблемы оценки сложности методов декодирования 24

1.5. Постановка задачи на исследование 32

2. Характеристика существующих моделей декодеров двоичных блоковых кодов 33

2.1. Модель и метод итеративного декодирования 33

2.2. Модель декодера блоковых кодов на основе нейронного классификатора 37

2.2.1. Структура модели РНД1 37

2.2.2. Функционирование модели РНД1 41

2.3. Модель декодера блоковых кодов на основе обучаемой ИНС 45

2.3.1. Подход к оптимизации архитектуры нейронного декодера 46

2.3.2. Структура и функционирование модели 49

2.3.3. Выбор параметров модели 52

2.3.3.1. Решение задачи статистического обучения. Модель обучения «с учителем» 53

2.3.3.2. Общее решение задачи выбора размера обучающего множества 58

2.3.4. Процедура синтеза обучаемого нейронного декодера 60

2.4. Выводы 64

3. Разработка моделей и методов кодирования и декодирования двоичных блоковых кодов 66

3.1. Итеративно-перестановочный метод декодирования двоичных линейных блоковых кодов 66

3.2. Модель нейронного кодера как параллельное вычислительное устройство 77

3.3. Разработка усовершенствованной модели нейронного декодера РНД1 82

3.3.1. Режим «жесткого» декодирования с исправлением ошибок и стираний 82

3.3.2. Режим «мягкого» декодирования 90

3.4. Разработка нейронного кодера и декодера на основе модели НДПР 94

3.4.1. Нейронный кодер прямого распространения 95

3.4.2. Нейронный декодер прямого распространения 98

3.4.2.1. Методика формирования обучающего множества 99

3.5. Исследование корректирующих способностей 108

3.6. Выводы 111

4. Оценка сложности функционирования разработанных методов декодирования двоичных блоковых кодов 114

4.1. Выбор критерия оценки сложности алгоритмов 114

4.1.1. Выбор показателей эффективности методов декодирования 114

4.1.2. Оценка сложности программной реализации методов декодирования на основе комплексного показателя 122

4.2. Оценка сложности функционирования РНД и его модификаций 131

4.3. Оценка сложности функционирования НДПР 135

4.4. Оценка эффективности полученных результатов 140

4.4.1. Эффективность параллельной и последовательной реализаций 140

4.4.2. Сравнение с результатами других исследователей 145

4.4.3. Аппаратная реализация 147

4.5. Выводы 151

Заключение 153

Список литературы 156

Приложение 1 167

Приложение 2 174

Введение к работе

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

К наиболее эффективным методам обеспечения высокого качества цифровой передачи в условиях помех в канале связи относятся уже весьма мощные в настоящее время алгоритмы декодирования корректирующих кодов. Возможность применения корректирующих кодов связана со значительными достижениями в течение последних лет в теории помехоустойчивого кодирования, в соответствии с которыми были разработаны методы кодирования и декодирования, вполне реализуемые современной техникой. За 50 лет своего интенсивного развития в технику связи были успешно внедрены пороговые декодеры, декодеры Витерби, турбо декодеры, многопороговые декодеры и пр. Такие декодеры позволяют реализовать системы помехоустойчивого кодирования (СГЖ) с недостижимыми ранее потребительскими параметрами и существенно улучшить характеристики таких систем. В то же время современный этап развития телекоммуникационных систем характеризуется широким развитием проводных и беспроводных сетей передачи данных. Рост числа пользователей таких сетей, появление новых мультимедийных услуг предъявляют высокие требования к скорости, надежности и количеству задержек при обработке информации. Одна різ самых весомых задержек связана с помехоустойчивым кодированием и декодированием данных.

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

нейронных сетей (ИНС). Элементной базой ИНС является технипг^^еская реализация прототипа биологического нейрона, который служит базисс^^ач* для построения таких систем. На сегодняшний день отечествен Hbirzzzvrn и зарубежными исследователями (Галушкин А.И-., Комашинский В.И., F^zz^pGaHb А.Н., Оссовский С, Bruck J., Blaum М., Mayora-Ibarra О., Zeng G., Ни ~Fsh D: Ahmed N., Stefano A.D., Lippmann R.P., Ahmed S. и др.) предложено мно:г=ь^сество различных нейросетевых моделей, в том числе решающих ^задачи декодирования помехоустойчивых кодов. Однако до. сих пор не разра_!^Зотана единая концепция их применения и- настройки. Это влечет за собой увелг:^зг*їение структурной избыточности нейронных декодеров и сложност^-Е^т. их функционирования. Более того, указанные вопросы требуют детл^^_п;ЬНсщ проработки применительно к широко используемым кодовым констрз-^Есциям блоковых помехоустойчивых кодов, что обуславливает актуальность насзсг-оящей работы, направленной на повышение обоснованности применения {-ЗЦс в задачах помехоустойчивого кодирования.

В то же время разработчики' современных СПК должны цгз>ешать компромиссную задачу «сложность-эффективность». На прогр^зі_тугмно-аппаратном уровне, решение этих задач приводит к необходимосжг^Рі как алгоритмического, так и технического упрощения, включающего ^выбор наименее сложной реализации алгоритма. Сегодня критерием выбора тосег-о или иного метода декодирования, как правило, является его помехоустой^^п^а^ость или корректирующая способность, сложности же программной реагпЕзгзации декодеров уделено явно недостаточное'внимание.

Целью диссертационной работы является повышение эффектигг^иости системы помехоустойчивого кодирования на основе совершенста<^>^ания методов и параметров итеративных и нейронных декодеров двос^тчных блоковых кодов.

В связи с этим выделены два направления, определяющие пост?:^а.иовку задачи диссертационной работы. Первое направление связано-с исследо;в^з.нием современного итеративного метода декодирования. Второе - направлт^^ио на

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

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

В работе использовался математический аппарат теорий вероятностей, помехоустойчивого кодирования, нейронных сетей, статистического обучения, полезности, сложности вычислений, а также методы имитационного моделирования (Монте-Карло). Экспериментальные исследования проведены с использованием пакета математического, статистического и имитационного моделирования MATLAB 7.01 и программных средств Statistica Neural Networks 4.0.

Научные результаты и их новизна:

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

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

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

существенно сократить объем обучающих данных и, как следствие, уменьшить время на разработку нейронных декодеров, сократить число используемых нейронов и расширить применение нейронных декодеров в область исправления стираний;

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

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

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

  1. предложенный подход к повышению обоснованности выбора параметров нейронных декодеров (НД) расширяет возможности их реализации для кодов больших длин и может быть использован при проектировании перспективных СПК, работающих в реальном масштабе времени;

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

3) практическое применение разработанных аналитических выражений
оценки сложности нейронных декодеров позволит до этапа эксплуатации
оценить пригодность конкретных реализаций нейронных декодеров при
заданных ограничениях на сложность функционирования;

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

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

  1. метод декодирования двоичных линейных блоковых кодов на основе итеративно-перестановочного подхода;

  2. модель «жесткого» и «мягкого» нейронного декодера с исправлением ошибок и стираний;

3) методика формирования обучающего множества, обеспечивающая
построение нейронного декодера как обучаемой модели с меньшим числом
нейронов;

4) методика оценки сложности функционирования методов кодирования и
декодирования на основе комплексного показателя.

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

Основные положения работы обсуждались и были одобрены на: 57, 58, 59, 60, 61-й НТК профессорско-преподавательского состава, научных сотрудников и аспирантов ГУТ им. проф. М.А. Бонч-Бруевича в 2005, 2006, 2007, 2008 и 2009гг., XI международной конференции «Региональная информатика-2008» в 2008г., Международной НПК «Перспективы развития телекоммуникационных систем и информационные технологии» в 2008г. По результатам диссертации опубликовано 13 печатных работ, из них 3 в изданиях, рекомендованных ВАК, получено положительное решение о выдаче патента РФ на полезную модель.

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

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

Исследования по ИНС связаны с тем, что способ обработки информации человеческим мозгом в корне отличается от методов, применяемых обычными цифровыми компьютерами. Мозг представляет собой сложный, нелинейный, параллельный компьютер (систему обработки информации). Он обладает способностью организовывать свои структурные компоненты, называемые нейронами, так, чтобы они могли выполнять конкретные задачи во много раз быстрее, чем могут позволить самые быстродействующие современные компьютеры. Примерами такой задачи обработки информации могут служить обычное зрение [72, 127, 128] и локация [3, 70].

В общем случае, нейронная сеть представляет собой машину, моделирующую способ обработки мозгом конкретной задачи. Эта сеть обычно реализуется с помощью электронных компонентов или моделируется программой, выполняемой на цифровом компьютере. Для того, чтобы добиться высокой производительности ИНС используют множество взаимосвязей между элементарными ячейками вычислений — нейронами. Таким образом, в научно-технической литературе дано следующее определение нейронных сетей, выступающих в роли адаптивной машины [2, 69]:

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

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

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

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

Изменение синаптических весов представляет собой традиционный метод настройки ИНС. Этот подход очень близок к теории линейных адаптивных фильтров [4, 129]. Однако ИНС могут изменять собственную топологию. В литературе нейронные сети часто называют нейрокомпьютерами, сетями связей, параллельными распределенными процессорами и т.д.

Как было показано ранее, для построения отображения (1.1) может применяться аппарат ИНС. Для этого могут быть использованы нейросетевые модели, предназначенные для решения задач классификации и задач относящихся к классу проблем построения отношений на множестве объектов.

Опубликованные работы по применению ИНС для задач декодирования помехоустойчивых кодов в основном включают в себя использование сетей Хопфилда [6, 8, 9, 33, 40, 84, 146, 147] для блоковых кодов [45, 46], сетей работающих по принципу "победитель забирает все" [47], сетей Хэмминга [148, 149], сетей встречного распространения (СВР), и многослойных сетей с алгоритмом обратного распространения ошибки (ОРО) [48, 49, 50].

Например, декодирование линейного блокового кода по методу максимального правдоподобия в [45] сформулирована как проблема нахождения глобального максимума функции энергии нейронной сети Хопфилда, где каждый локальный максимум является кодовым словом:

выбирается случайно, что не дает гарантии достижения сетью глобального минимума функции энергии. Также обязательным условием использования сети Хопфилда является "сбрасывание" значений синаптических весов сети при поступлении очередного вектора, что усложняет процедуру декодирования и практически не дает возможность использовать данный декодер на высоких скоростях передачи данных в канале связи. Идеи, заложенные в [45] дали свое развитие в [51], где начальное состояние сети формируется из кодовой структуры используемого кода, а не выбираются случайно, что позволило ускорить процедуры декодирования, но емкость декодера на основе сети Хопфилда все равно осталась достаточно низкой.

Идеи «мягкого» декодирования блоковых кодов с использованием нейронной сети Хопфилда на примере (7,4) кода Хэмминга были также предложены в [52], где структура сети зависит от порождающей матрицы кода G. При таком построении сети функция энергии записывается следующим 7=1 где Vf—j-и элемент переданного вектора, Мц— элементы матрицы М = [Р:0], Nff— элементы матрицы N = [0:1И_ ]. Каждая точка с минимумом энергии (Е = 0) соответствует разрешенной кодовой комбинации. В работе показано, что при декодировании функция энергии сети уменьшается, пока система не достигнет стабильного состояния (разрешённой КК). Однако не оценено количество циклов, необходимых для достижения стабильного состояния при декодировании кодового слова.

Важным параметром сети Хопфилда является ее емкость, т.е. максимальное количество запомненных образов. В [132] показано, что максимальная емкость памяти (количество запомненных образов) составляет около 15% от количества нейронов, образующих данную сеть.

В [47] для «мягкого» декодирования (24, 12) кода Голея предложено использовать ИНС, работающие по принципу "победитель забирает все" совместно с некоторой дополнительной логикой. В [48] для декодирования кодов Хэмминга предложено использовать сеть Хэмминга (классификатор по минимальному расстоянию Хэмминга), которая содержит в весах синаптических связей каждого нейрона первого слоя образцов все разрешенные кодовые комбинации, в связи с этим число нейронов в слое образцов сети Хэмминга эквивалентно числу РКК (рис. 1.1). Кроме того, в составе сети Хэмминга имеется конкурирующий слой нейронов, размер которого также равен числу РКК. Он вводит задержки на декодирование, зависящие от распределения ошибок в принятом кодовом слове. Общее число нейронов в сети Хэмминга при таком построении в среднем равно удвоенному числу РКК.

Структура и функционирование модели

Таким образом, в качестве модели обучаемого НД выберем модель многослойного персептрона с одним скрытым слоем, которая представлена на рис. 2.6. Модель будем называть нейронным декодером прямого распространения (НДПР) по типу ИНС, входящей в его структуру.

Модель (рис. 2.6) состоит из двух слоев технических нейронов (рис. 2.3): скрытого слоя и выходного слоя. Причем слой 0 (входной) не производит вычислений, а предназначен для распределения сигналов принятой кодовой комбинации по нейронам скрытого слоя. На вход каждого нейрона того или иного слоя подаются выходные сигналы со всех нейронов предыдущего слоя. Тип входных сигналов - целые или действительные числа. Тип выходных сигналов - действительные числа из интервала, определяемого принятой функцией активации нейронов. Нейроны выполняют взвешенное суммирование входных сигналов с соответствующими синаптическими весами. К полученной сумме добавляется смещение (порог) нейрона. Над результатом суммирования выполняется нелинейное преобразование, определяемое функцией активации нейрона [68]. Нейронный декодер, показанный на рис. 2.6, в общем случае называется декодером N—L—K, так как он имеет N входных, где N — длина кода, L скрытых и К выходных нейрона, где К— длина информационного слова. В качестве активационных функций нейронов скрытого и выходного слоев НДПР используются антисимметричные сигмоидальные функции активации, значения которых вычисляются в соответствии с выражением: 2), соответственно, w.,, w., — веса синаптических связей скрытого слоя и выходного слоя, соответственно, WQA: W0k весовые коэффициенты эквивалентные значениям смещений (порогов) нейронов скрытого и выходного слоя.

Размеры входного и выходного слоев НДПР определяются параметрами используемого кода (N, К), в то время как размер скрытого слоя и параметры свободных параметров определяются в процессе обучения. В связи с этим, размер скрытого слоя полностью определяет сложность функционирования НД.

Очевидно, что модель НДПР может быть использована как кодер блокового кода с точностью до размерности входных и выходных данных. Назовем такой кодер нейронным кодером прямого распространения (НКПР).

Процесс функционирования НДПР при построении оператора отображения (1.1) (декодировании) показан на рис. 2.7.

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

Очевидно, что НДПР является декодером максимального правдоподобия. В то же время построение НДПР с такими свойствами полностью зависит от правильной настройки в его структуре статистических свойств кодового пространства используемого кода. Данный процесс кодирования (настройки) представляет собой процедуру обучения. Далее рассмотрим теоретические аспекты процедуры настройки НДПР для выполнения отображения (1.1), т.е. процедуру обучения и выбора размера ОМ.

Одно из важнейших свойств ИНС — это способность к обобщению полученных знаний. Феномен обобщения возникает вследствие большого количества комбинаций входных данных, которые могут кодироваться в сети с N входами. Подбор весов сети в процессе обучения имеет целью найти такую комбинацию их значений, которая наилучшим образом воспроизводила бы последовательность ожидаемых обучающих пар (хг-, dj). При этом наблюдается тесная связь между количеством весов сети (числом степеней свободы) и размером ОМ [85].

Разработка усовершенствованной модели нейронного декодера РНД1

В случае использования «мягких» решений в демодуляторе структура РНД2 может быть усовершенствована. В соответствии с (1.7) для для минимизации ошибки декодирования при использовании «мягкой» схемы принятия решений в демодуляторе требуется минимизация квадрата Евклидова расстояния, что является метрикой для декодирования по максимуму правдоподобия. Для этого в качестве подсети нейронов слоя образцов предлагается использовать вероятностную нейронную сеть (PNN — Probability Neural Network) [116], которая представляет собой параллельную реализацию известных статистических методов ядерной аппроксимации, оформленных в виде нейронной сети. В ней образцы классифицируются на основе оценок их близости к соседним образцам. В данном случае в основу классификации в слое образцов положено использование методов Байеса [117]. Идея состоит в том, что для каждого образца можно принять решение на основе выбора наиболее вероятного класса из тех, которым мог бы принадлежать этот образец. Такое решение требует оценки функции плотности вероятностей для каждого класса. Формальным правилом является то, что РКК с наиболее плотным распределением в области неизвестного кодового слова будет иметь преимущество по сравнению с другими РКК.

Нейроны слоя образцов РНД2м представляют собой радиальные нейроны [85, 89, 116, 118], активность которых определяется функцией Гаусса с нормальным законом распределения [85, 116] (3.35). В соответствии с этим, выражение (3.32) для РНД2м записывается в виде:

где у,— выходное значение нейрона к слоя образцов, w-ic— весовые коэффициенты синаптической связи, соединяющей вход і нейронной сети и нейрон к первого слоя, Xj — /-й элемент входной кодовой комбинации, 5 — дисперсия, характеризующая ширину радиально-базисной функции. Количество радиальных нейронов определяется РКК, которые образуют классы. Таким образом, слой образцов РНД2м выполняет классификацию входа по классам и выходы нейронов слоя образцов есть оценка вероятности принадлежности входного вектора к классам РКК.

Для РНД2м (рис. ЗЛО) не требуется обучение в том смысле, какое требуется для многослойных персептронов, так как все параметры сети определяются непосредственно РКК, записанными в память сети. W є[-1,і]/ ч.Л w2e[-l,l]

Алгоритм работы РНД2м полностью совпадает с алгоритмом работы РНД2 за исключением того, что выходные значения нейронов слоя образцов у, вычисляются в соответствии с (3.35), а весовые коэффициенты синапсов выходного слоя эквивалентны информационным элементам разрешенных кодовых комбинаций, представленных в биполярной форме wfj = 2cf -1, где Wy- весовой коэффициент синапса /-го нейрона слоя образцов иу -го нейрона выходного слоя. Соответственно, РНД2м предназначен для «мягкого» декодирования блоковых кодов.

В качестве примера на рис. 3.11 представлена обобщенная структура системы передачи данных, использующая рекуррентный нейронный кодер (РНК) и РНД2.

. Структурная схема системы передачи данных с использованием РНД2 Использование нейронных сетей в качестве составных частей кодеров и декодеров наделяет систему кодирования важными дополнительными свойствами. Данные свойства, безусловно, являются преимуществом нейросетевых систем кодирования по сравнению с классическими методами защиты от ошибок. Основные из этих свойств представлены ниже и являются достоинствами любых нейросетевых схем кодирования. Основными достоинствами являются: простота реализации; высокая скорость функционирования при постоянной сложности реализации. Результат на выходе сети декодера получается практически

Оценка сложности программной реализации методов декодирования на основе комплексного показателя

Задача количественного оценивания методов декодирования может быть сформулирована в терминах критерия превосходства в форме [168]

где п — количество оцениваемых методов, у І — 1-й оцениваемый метод. Наличие неоднородных связей между отдельными показателями методов декодирования (4.5) приводит к проблеме корректности критерия презо сходства, к необходимости идти на компромисс и выбирать для каждой характеристики не оптимальное значение, а меньшее, но такое, при котором и другие показатели тоже будут иметь приемлемые значения [168].

Для решения проблемы корректности критерия превосходства будем использовать методы теории полезности [166, 167, 168], которые основаны на аксиоматическом использовании отношения предпочтения множества векторных оценок систем и, в частности, методов декодирования.

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

Ваэюность показателя — это действительное число, приписываемое показателю и характеризующее его предпочтительность по сравнению с другими альтернативами относительно цели [168]. Определение коэффициентов важности сталкивается с серьезными трудностями и сводится либо к использованию формальных процедур, либо к применению экспертных оценок [166, 168]. В случае задачи оценки сложности методов декодирования важность показателей сг- будем выбирать из диапазона [О, 1], причем значение

сі = 1 будет означать, что показатель имеет наивысшую важность, a c = О — показатель безразличен.

Зная возможные показатели с их коэффициентами важности, можно построить функцию сложности метода декодирования, которая дает основу для сравнения и выбора решений. Функция сложности представляет собой числовую обратную ограниченную функцию Тj (/?), определенную на множестве методов декодирования (альтернатив) А = {а }, /с=1, 2, ..., /, так, что ха.(п) = ха .(п), когда сложность методов декодирования а і и а, і j .і неразличима, и ха.(п) 4Ja . (/?), когда метод щ предпочтительнее в смысле сложности метода а ,. При аксиоматическом подходе к оценке методов декодирования на основе теории полезности отсутствуют определения нулевой полезности, единицы полезности и шкалы полезности, что позволяет лицу принимающему решение (ЛПР) вводить свои предпочтения, которые формулируются в виде аксиом. Поскольку системы предпочтений у разных ЛПР могут различаться, то разные аксиоматики приводят к различным видам свертки векторного показателя (5.5). Поэтому для оценки сложности методов декодирования в качестве функции свертки будем использовать аддитивную свертку компонентов векторного показателя (5.5), состоящую в представлении комплексного скалярного показателя в виде суммы взвешенных частных показателей:

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

Для удобства сравнения методов кодирования и декодирования в пространстве их сложности можно использовать логарифм от комплексного. показателя сложности (4.8). В данном случае критерий превосходства (4.6) можно переписать следующим образом K?VGB - min[logT0. (N)}, /=1, ... , л, (4.9) где п — количество оцениваемых методов, aj — /-й оцениваемый метод. Выражение (4.8) задает комплексный показатель сложности последовательной реализации алгоритма, т.е. показатель трудоемкости алгоритма в данном случае может быть вычислен в соответствии с выражением: , Ып) = /аощ{п), (4-Ю) где faon (п) пооперационная функция трудоемкости /-й операции (трудоемкость операции). Очевидно, что если алгоритм частично допускает параллельную реализацию, то его сложность по показателю трудоемкости будет существенно ниже сложности определяемой (4.8). Здесь и далее под параллельной реализацией будет пониматься реализация алгоритма декодирования на базе параллельно функционирующих цифровых процессоров. Для рассматриваемых НД в качестве таких процессоров выступают отдельные нейроны. В соответствии с этим показатель трудоемкости алгоритма (4.10) может быть адаптирован с учетом параллельных блоков выполнения: где А{П) — сложность реализации алгоритма при наличии параллельных блоков выполнения. Очевидно, что (4.8) является частным случаем (4.13) при отсутствии параллельных блоков выполнения (faon(n) — 0). Анализ сложности алгоритма декодирования любого типа может быть выполнен на основе комплексного показателя (5.8) и (5.13). Двойственная задача минимизации емкостной сложности Sr при ограничениях на трудоемкость не является первоочередной задачей в силу архитектурных особенностей современных ЭВМ. При анализе сложности алгоритмов декодирования без привязки к конкретной реализации 3-й член выражений (4.8) и (4.13), характеризующий меры сложности ПО, можно исключить, поскольку он больше характеризует исполнителя (машину), его язык, а не метод решения задачи. Поэтому для простоты исследований 3-й и 4-й члены выражений (4.8) и (4.13) можно не учитывать. В связи с этим, вектор коэффициентов важности с примет вид При оценке сложности нейронных декодеров целесообразно в качестве базисного программного модуля (алгоритмической конструкции) рассматривать модель технического нейрона и/или слой нейронов. В данном случае сложность нейрона может быть оценена количеством операций умножения с накоплением значений входного сигнала с весами синаптических связей. Для простоты трудоемкость функции активации принимается равной единице. В связи с этим функция трудоемкости одного нейрона с Т синаптическими связями примет вид /нейронСО = Г + (Г -1) +1 = 2Т, (4.17) где /нейрон СО трудоемкость одного нейрона, "7" — число «элементарных» операций умножения, "(Г-1)" - число «элементарных» операций сложения и "1" - трудоемкость функции активации. Очевидно, что при использовании многослойной ИНС величина Т равна числу нейронов в предыдущем слое. Трудоемкость j-ro слоя нейронов при последовательной реализации с учетом (4.17) может быть оценена как сумма трудоемкостей всех нейронов слоя:

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