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

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

БЕРЁЗКИН Александр Александрович

МОДЕЛИ И МЕТОДЫ ДЕКОДИРОВАНИЯ ПОМЕХОУСТОЙЧИВЫХ КОДОВ НА ОСНОВЕ НЕЙРОСЕТЕВОГО БАЗИСА

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

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

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

003474051

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

Научный руководитель: кандидат технических наук, доцент

Охорзин Виктор Михайлович

Официальные оппоненты: доктор технических наук, профессор

Саенко Игорь Борисович

кандидат технических наук Кунгурцев Вадим Викторович

Ведущая организация: ФГУП НИИ «Рубин»

Защита состоится «С'2.» 2009 г. в Щ часов на заседании

диссертационного совета Д219.004.02 при Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича по адресу: 191065, Санкт-Петербург наб.р. Мойки, 61.

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

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

Автореферат разослан «С1» 2009 г.

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

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

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

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

В настоящее время подобные проблемы решаются различными путями, в том числе внедрением параллельных методов кодирования и декодирования, основанных на элементах теории искусственных нейронных сетей (ИНС). На сегодняшний день отечественными и зарубежными исследователями (Галушкин А.И., Горбань А.Н., Комашинский В.И., Оссовский С., Bruck J., Blaum М., Mayora-Ibarra О., Zeng G., Hush D., Ahmed N., Stefano A.D., Lippmann R.P., Ahmed S. и др.) предложено множество различных нейросетевых моделей, в том числе решающих задачи декодирования помехоустойчивых кодов. Однако они слабо связаны с параметрами используемых кодов и до сих пор не разработана единая концепция их применения и настройки. Это влечет за собой увеличение структурной избыточности и сложности функционирования нейронных декодеров. Более того, в современной научно-технической литературе недостаточно проработан вопрос обоснованности применения различных нейросетевых моделей для декодирования широко используемых на практике блоковых помехоустойчивых кодов, что обуславливает актуальность настоящей работы, направленной на повышение обоснованности применения ИНС в задачах помехоустойчивого кодирования.

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

Объектом исследования система помехоустойчивого кодирования (СПК).

Предметом исследования являются методы декодирования и их реализация на основе ИНС.

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

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

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

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

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

Научная новизна работы определяется:

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

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

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

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

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

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

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

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

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

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

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

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав с выводами, заключения, списка литературы и двух приложений. Основная часть работы содержит 155 страниц текста, 44 рисунка, 16 таблиц, включает 169 наименований отечественной и зарубежной литературы, объем приложений составляет 24 страницы.

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

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

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

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

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

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

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

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

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

а) DMN / или б) D:A." ->А<"Л> ->АК, (1)

где А,- алфавит из {-1,1,*}: * - символ стирания, D - оператор нахождения кодового слова, А" - множество принимаемых КК, А'",К) - множество всех разрешенных кодовых комбинаций (РКК), Ак — множество информационных слов РКК. Отмечено, что на задержки декодирования напрямую влияет сложность отображения D.

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

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

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

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

Во второй главе выбраны, изучены и исследованы известные модели НД и итеративного декодера.

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

L{d) = Lc{x) + L{d) + L.{d), (2)

где L{d) - LLR («мягкий» выход) вне декодера, Lc(x) - LLR канала (получается в результате канальных измерений в приемнике), L(d) - априорное LLR бита данных, Le(d) ~ внешнее LLR (внешняя информация о структуре кода, выявляемая в процессе декодирования). На основе используемой математической модели описан обобщенный алгоритм итеративного декодирования блоковых кодов и показаны возможности его модификации [4].

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

модель нейронного классификатора Хэмминга, в виде рекуррентного нейронного декодера 1-й модификации (РНД1) (рис. 1а) [5-7]. Использование данной модели позволяет решить задачу декодирования блоковых кодов по критерию максимального правдоподобия с использованием «жесткой» схемы принятия решений в демодуляторе. Показано, что РНД1 обеспечивает отображение (16);

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

а) б)

Рис. 1. Модели НД а) нейронный классификатор Хэмминга (РНД1); 6) обучаемая ИНС

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

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

Принятая КК

Слой распознавания

Декод upoeai тог информационное слово Выходной I

, оо

Множество принимаемых кодовых слов

Принятая КК

Множество разрешенных КК

а)

Гипермоскости

Множество информационных слов

Декодированное информационное слово Выходной /

Множество принимаемых кодовых слов

Множество информационных слов

б)

Рис.2. Реализация отображения множества принимаемых КК на множество информационных слов а) при использовании РНД1; б) при использовании НДПР

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

Л*,, (3)

где Л.", - г-ая КК из множества всех принимаемых КК, Ак, - г'-ое информационное слово, связанное с Аj\. Результаты декодирования с использованием НДПР априорно реализуются на этапе разработки в виде множества частных отобра-

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

Суть действий НДПР полностью определяется качеством ОМ (3). Установлено, что выбор данных обучения и их размещение относительно конкретных гиперплоскостей становится очень важным для минимизации размера скрытого слоя L (рис. 16), который полностью определяет структуру и сложность функционирования НДПР, где под размером слоя понимается количество нейронов в нем. Поэтому задача минимизации L выделена в отдельную научно-техническую задачу.

Минимизировать L возможно, опираясь на использование различных алгоритмов инициализации и обучения, а также за счет варьирования их параметрами. Этому посвящен целый ряд работ зарубежных авторов (Lippmann R.P., Stefano A.D., Mirabella О., Wu J.L., El-Khamy S.E. и др.). В данной работе предлагается взять за основу уменьшение избыточности ОМ и проанализировать, каким образом это отразится на L и корректирующих возможностях НДПР.

В данной части задачу исследования можно сформулировать так: создать и обучить НДПР с минимально достаточным количеством нейронов, позволяющий получить результаты безошибочного декодирования в пределах </min кода, где dmn - минимальное кодовое расстояние.

Для построения НД на основе модели НДПР использован метод минимизации структурного риска и соответствующая процедура синтеза НДПР (рис. 3), суть которой заключается в использовании совокупности моделей НДПР с монотонно возрастающим значением L до достижения безошибочного декодирования в пределах i/mm кода. В качестве методов оптимизации использованы известные алгоритмы обучения на примерах (Левенберга-Марквардта, обратного распространения ошибки), параметры которых устанавливались значениями по умолчанию. Требование поиска минимально достаточного количества нейронов обуславливается тем, что чем меньше нейронов содержит НДПР, тем меньше требуется вычислительных ресурсов для его реализации.

Рис. 3. Процедура синтеза НДПР блокового кода

Далее в главе 2 подробно описаны теоретические положения статистического обучения, влияющие на сложность и корректирующие свойства НДПР.

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

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

Суть ИП метода состоит в мажоритарном принципе построения дополнительных проверочных уравнений путем линейной комбинации строк проверочной матрицы кода и группировки полученных уравнений в дополнительные фазы итерации декодирования с целью получения более надежных решений относительно информационных элементов при ограничении числа итераций. В общем случае на примере (8,4) кода Хэмминга данную схему декодирования можно представить как последовательное соединение 7 декодеров с «мягкой» схемой принятия решений на входе и выходе (SISO Декодер и) (рис. 4), использующих различные комбинации проверочных уравнений для одной фазы итерации декодирования. Они последовательно обмениваются между собой «внешней» информацией Le(d), и образуют одну полную итерацию декодирования. Результат декодирования по каждому информационному биту вычисляется в соответствии с (2).

k(d)

Щ)

L,(d)

L,(d)

4W

SISO SISO SISO

Декодер Декодер Декодер

1 2 Г* 3

Основные фазы

г

siso

Декодер 7

L(J)

Дополнительные фазы

На|Решающев уртройство I

без кодирования ИП-мегад (1 итерация) только основные фазы Декздер Мегила

Рис. 4. Функциональная схема ИП метода декодирования на примере (8,4) кода Хэмминга

Результаты моделирования (рис. 5) показали, что энергетический выигрыш (ЭВ) от использования разработанного ИП метода на примере (7,4) кода Хэмминга составил [0,1 -0,5] дБ (для 1 итерации) по отношению к методу еь/ио (ов) использования только

Рис. 5. Оценка помехоустойчивости ИП метода для основных фаз итерации (8,4) кода Хэмминга в канале АБГШ

декодирования. Выигрыш заметен уже при вероятности ошибки 10 [13].

С целью уменьшения вычислительных затрат на операцию декодирования усовершенствованы рассмотренные в главе 2 модели НД. Разработана упрощенная модель РНД1 в виде РНД2 (рис. 6а) [12]. На данную модель получено положительное решение о выдаче патента РФ на полезную модель [14].

Рис.6. Модель РНД2 блокового кода а) «жесткое» декодирование (РНД2); б) «мягкое» декодирование (РНД2м) Идея заключается в удалении из состава РНД1 (рис. 1а) рекуррентного слоя нейронов (слоя распознавания), который вводит переменную задержку при декодировании. Для этого в качестве активационных функций (АФ) нейронов слоя образцов РНД1 доказано использование пороговых АФ единичного скачка (функций Хэвисайда) со смещениями (порогами) Ь = -{Ы- </т]п -1), которые получены автором самостоятельно. Кроме того, преобразована в биполярный вид матрица весов синаптических связей нейронов слоя образцов РНД1 ХУ^е]^, 1], что позволило исправлять стирания в принятой КК путем их замены нулевым элементом на входе декодера.

Усовершенствована разработанная модель РНД2 (рис. 6а) в виде РНД2м (рис. 66) с целью использования «мягких» решений в демодуляторе. Для этого в качестве нейронов слоя образцов РНД2 обоснована необходимость использования радиальных нейронов, активность которых определяется функцией

Гаусса с нормальным законом распределения: у\ = ехр[-(^(и4-х^)128г],

м

к = Х, ...,М (М=2К), где 52 =1 - дисперсия, характеризующая ширину радиально-базисной функции, у\ - значение выходного сигнала к-то нейрона слоя образ-

Запрещенные КК

цов РНД2м. Показано, что слой образцов РНД2м осуществляет выбор РКК с наибольшей плотностью распределения вероятности к входным данным. Кроме того, преобразована в биполярный вид матрица весов синаптических связей нейронов выходного слоя РНД2м W(2) e[-i,l], что позволило выделить нейрон слоя образцов с максимальным значением вероятности у\. Показано, что РНД2м и РНД2 являются декодерами максимального правдоподобия. Установлено, что РНД2 устраняет переменную задержку при декодировании, а также обеспечивает исправление стираний [6].

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

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

качестве ОМ Гиперплоскости Разрешенные КК

используется мно- Рис. 7. Методика формирования ОМ для построения НДПР

жество запрещенных кодовых комбинаций, отстоящих на расстоянии t (и/или р) от соответствующей РКК (рис. 7): Т = 2К , где t (р) — кратность исправляемых кодом ошибок (стираний), Т- размер ОМ [9, 12].

Предложенные обучающие данные находятся на границах гиперплоскостей, формируемых нейронами скрытого слоя НДПР, что позволяет в среднем сократить размер ОМ на 13,5% для режима исправления ошибок и на 29,5% для режима исправления ошибок и стираний (рис. 8).

Размер ОМ

зооооо

250000

15МШ 100000

-предложенный набор ОМ ~ ^

-полный набор ОМ К

/к^

/^^^^^исправление ошибок 1 исправление ошибок

и стираний

(15,5) (15,7) (15,11) <?'4' >15'" Рис. 8. Изменение размера ОМ НДПР при Рис. 9. Изменение I НДПР некоторых кодов БЧХ _исправлении ошибок и стираний___при изменении состава ОМ_

- Все кодовое пространство как ОМ

- Предлагаемый набор ОМ (рис. 7)

Исследовано влияние размера ОМ на изменение Ь (рис. 9), где под полным набором понимается множество (3) [12]. Установлено, что при использовании предложенной методики Ь НДПР уменьшается в среднем на 9,8%. Необходимо отметить, что существует связь между размером ОМ и V. чем меньше размер ОМ, тем меньше Ь. Показано, что полученные результаты согласуются с результатами статистической теории восстановления зависимостей по эмпирическим данным В.Н. Вапника и А.Я. Червоненкиса.

В научно-технической литературе введены эвристические формулы для оценки теоретических границ изменения Ь и необходимого числа синаптиче-ских весов в зависимости от структуры ИНС и размера ОМ (в многослойной сети с сигмоидальными функциями активации):

К'Т " + К + = (7)

) ы+м

размерность выходного вектора, Т -

:<L<K

log L

1 + 1оё2Г " {К где N - размерность входного вектора, К -размер ОМ. Установлено, что при непосредственном применении (7) оценка Ь НДПР становится сильно завышена (рис. 10 и 11).

Рис. 10. Изменение L НДПР некоторых кодов БЧХ Рис. 11. Изменение L НКПР некоторых кодов при исправлении ошибок БЧХ

В работе экспериментально получены практические аппроксимации L НДПР (рис. 10) и НКПР (рис. 11), где НКПР - нейронный кодер прямого распространения. Анализ рис. 10 показывает, что более точная привязка ОМ к параметрам кодового пространства обеспечивает значительное снижение L НДПР.

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

о

(АБГШ) сГ=1 и двоичной фазовой манипуляцией (BPSK) (рис. 12а,б,в), а также в дискретном однородном двоичном симметричном канале без памяти (ДСК) при варьировании вероятности ошибки Раш от 0 до 0.5 (рис. 12г).

Рис.12. Оценка помехоустойчивости РНД2 и РНД2м кодов БЧХ при работе в канале АБГШ а) код (7,4); б) код (15,5); в) код (15,7); г) Оценка Р„„ при изменении Ршп в ДСК

На основе графиков, отражающих результаты моделирования (рис. 12), где БМА - классический синдромный метод декодирования (алгоритм Берлекэмпа-Месси), могут быть сделаны следующие выводы: предложенные модели РНД2(2м) и НДПР не ухудшают качество СПК, при этом имеют меньшее значение Ь по сравнению с существующими моделями; предложенная методика формирования ОМ не ухудшает корректирующих возможностей разрабатываемых декодеров.

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

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

При оценке сложности выделено два класса: сложность функционирования (вычисления) и сложность построения (разработки).

Установлено, что построение НД значительно сложнее классических декодеров (КД), однако сложный процесс в данном случае реализуется априорно до приема кодовых слов (сложность построения). В то время как сложность КД переносится на интервал времени приема каждого кодового слова (сложность функционирования) [1,2]. Иными словами, сложности НД и КД реализуются в

разных классах (рис. 13). Обосновывается исследование сложности функционирования НД.

разработки

Классические .-,

декодеры

_ , Этап

Этап

1 функционирования

I » II «-II л II П ■■■ „

\ I / Время

Сюжность ^ ,

Сложность функционирования

разработки

Этап

разработки

Нейронные -

декодеры

функционирования

КК1 КК2 ККЗ КК4 КК5 КК6 КК7 КК8 КК9

г^пргргргрпглгпгп

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

Рис. 13. Реализация сложности методов декодирования Введена искусственная мера на основе функции полезности в виде комплексного показателя сложности последовательной и параллельной программной реализации алгоритмов кодирования и декодирования, позволяющая соизмерить отдельные показатели алгоритмической и программной сложности по неравномерной шкале для выявления порядка предпочтений. Такая мера определена через важность отдельных показателей в виде функции сложности метода декодирования. Для ее построения использована аддитивная свертка ее отдельных компонентов [3]:

Ч'ж.одер (и) 'ИИ Удекодср (») = С, • /дскодср (и) + с2 ■ + с3 • С + с4 ■ 5Г, (8)

где Ч^Ди) - последовательная сложность реализации, Тлск1);юр (») - сложность реализации алгоритма при наличии параллельных блоков выполнения, Лск<,»ер(")> /де„тер (") ~ функция трудоемкости последовательной/параллельной реализации (число «элементарных» операций), се [0,1] - коэффициенты важности, .У, — память, необходимая для реализации вычислительного процесса (число «элементарных» ячеек), 5г - память, необходимая для хранения промежуточных результатов.

Третий показатель "С" в выражении (8) является оценкой сложности ПО как совокупность метрик сложности ПО. Показано, что для задач СПК могут использоваться метрики Холстеда, отражающие размер ПО, или интегральная оценка сложности ПО, введенная в работах отечественных ученых, например, 1 м С

Бахтизиным В.В.: с =—где С> ~ Рассчиганное значение /-й метрики

сложности ПО, с(бп - базовое значение /-й метрики сложности ПО (в качестве С16аз может быть использовано статистическое значение ¿-й метрики сложности предприятия), М - количество метрик сложности ПО. Важно отметить, что функция сложности (8) характеризует относительную, а не абсолютную предпочтительность методов декодирования.

Рассмотрим случай, когда показатели оперативности (трудоемкость) и ресурсоемкости (память) алгоритма имеют наибольшую важность. В этом случае вектор коэффициентов важности примет вид с = (1100). С учетом (8) в работе получены аналитические выражения для оценки сложности НД (табл. 1),

где У - число слоев НД (за исключением входного), Ц - число нейронов в ¡'-м слое.

Таблица 1

Последовательная реализация Параллельная реализация

3 J /„«„«„(") = • ^ = ££,(£,-, +1) /™р(") = 25Х,. = ££,(£,_, +1)

при с, = с2 = 1, с3 = сА = 0:

М /=1

Для рассматриваемых моделей декодеров значения 3 и Ц определяются в соответствии с табл. 2.

Таблица 2

Наименование декодера

РНД1 РНД2 (РНД2м) НДПР

>3,10 = лм, =¿2=2*, ь}=к У=2, ¿0 =ЛГ, Ц =2*, 12=К У=2, ¿0 = ЛГ, ¿2 = К , Л, - определяется экспериментально.

Установлено, что трудоемкость НД в "лучшем", "худшем" и "среднем" случаях совпадает, поэтому сложность может быть рассчитана аналитически (рис. 14) в соответствии с табл. 1 без проведения имитационного моделирова-

а) б)

Рис. 14. Оценка сложности функционирования моделей НД некоторых кодов БЧХ

а) РНД1 и РНД2(2м); б) НДПР На основе графиков, отражающих изменение сложности НД для рассматриваемых кодов БЧХ и кодов длины до 127 (рис. 14), а также табл. 3 сделаны следующие выводы:

сложность РНД2(2м) меньше сложности РНД1 в среднем в 2К раз в связи с отсутствием рекуррентного слоя нейронов;

сложность НДПР меньше сложности РНД1 в среднем на 67,6%; использование предложенной методики формирования ОМ сокращает сложность НДПР в среднем на 9,7%.

В результате проведенных исследований, удалось получить оптимальные (в смысле минимального необходимого количества нейронов) характеристики НДПР для некоторых кодов БЧХ (табл. 3), позволяющие обеспечить результаты

декодирования, аналогичные декодеру максимального правдоподобия [12].

Таблица 3

Разработанные типы и структуры НД для некоторых кодов БЧХ_

№ п/п Код Тип нейронного декодера Структура нейронного декодера для различных режимов работы Порядок роста сложности

Исправление ошибок Исправление ошибок и стираний

1 РНД1 7-16-16-4 0(2")

2 (7,4) РНД2 (РНД2м) 7-16-4 0(N2K)

3 НДПР 7-7-4 7-9-4 OI.L-N)

4 РНД1 15-32-32-5 0(2")

5 (15,5) РНД2 (РНД2м) 15-32-5 0(N2K)

6 НДПР 15-38-5 15-58-5 O(L-N)

7 РИД! 15-127-127-7 0( 22А)

8 (15,7) РНД2 (РНД2м) 15-127-7 0(N2K)

9 НДПР 15-34-7 15-39-7 0(L ■ N)

Рассчитанные матрицы свободных параметров представлены в Приложении 2 диссертации.

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

Таблица 4

№ п/п Исследователь Наименование Структура Обучение

1 Zeng G., Hush D„ Alimed N. РНД1 N-2'--2К - К Нет

2 Htay M.M., Iyengar S.S. СНД и-\и- 2ЛГ-Л7 Нет

3 Ahmed S.

4 Stefano A.D, Mirabella 0., Cataldo G.D. В PN Ы-1ой(2Т) -2к-К Да

5 Предлагаемые ВД РНД2 N - 2А- К Нет

РНД2м N-2 ^-К

НДПР ы-ь-к Да

Рис. 15. Сложность реализации НД блоковых кодов в режиме исправления ошибок

Эффективность РНД2(2м) и НДПР сравнена с частными результатами других исследователей (табл. 4) (РНД1, СНД, ВРИ) с точки зрения сложности функционирования. Анализ графиков (рис. 15), полученных в результате использования разработанных аналитических выражений (табл. 1), показывает, что полученные результаты согласуются с известными данными и в случае рассматриваемых кодов сложность предлагаемых в работе НД меньше сложности известных НД в среднем на 56,4% при всех равных условиях.

Таким образом, проведенные в главе 4 исследования сложности функцио-

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

В заключении сформулированы основные научные и практические результаты работы, полученные автором.

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

1. Разработан итеративно-перестановочный метод декодирования двоичных линейных блоковых кодов, обеспечивающий увеличение надежности приема информационных элементов путем мажоритарного построения дополнительных проверочных уравнений. Моделированием оценен энергетический выигрыш от его использования на примере (7,4) кода Хэмминга. Он составляет [0,1 - 0,5] дБ (для 1 итерации) по отношению к методу использования только основных фаз итерации декодирования. Выигрыш заметен уже при вероятности

ошибки 10 .

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

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

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

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

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

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

1. Берёзкин A.A. Оценка сложности реализации современных методов декодирования помехоустойчивых кодов // Труды учебных заведений связи / СПбГУТ. СПб, 2005. № 172. С.89 - 96. (Из перечня изданий, рекомендованного ВАК).

2. Берёзкин A.A., Охориш В.М. Опенка сложности реализации декодирования кодов Рида-Соломона при исправлении стираний // 57-я НТК: материалы / СПбГУТ. СПб,

2005. С. 6.

3. Берёзкин A.A. Критерии оценки сложности программной реализации методов кодирования и декодирования // 59-я СНТК / СПбГУТ. СПб, 2005. С. 21.

4. Берёзкин A.A., Охорзин В.М Оценка сложности реализации итеративных методов декодирования // Труды учебных заведений связи / СПбГУТ. СПб, 2006. № 174. С.39 -44.

5. Берёзкин A.A. Альтернативное декодирование помехоустойчивых кодов с использованием нейронных сетей // Груды учебных заведений связи / СПбГУТ. СПб,

2006. № 175. С.8 -15.

6. Берёзкин A.A. Рекуррентный нейронный декодер двоичных блоковых кодов и его модификации // Труды учебных заведений связи / СПбГУТ. СПб, 2007. № 176. С.135 - 146.

7. Берёзкин A.A. Пейросетевой подход к вопросам кодирования/декодирования помехоустойчивых кодов // 59-я НТК: материалы / СПбГУТ. СПб, 2007. С. 29.

8. Берёзкин A.A. Оптимальный нейронный кодер/декодер прямого распространения: характеристики и применение // 61 -я СНТК / СПбГУТ. СПб, 2007. С. 20.

9. Берёзкин A.A. Выбор обучающего множества для построения нейронных декодеров помехоустойчивых кодов // 60-я НТК: материалы / СПбГУТ. СПб, 2008. С. 25.

И). Берёзкин A.A., Ко.нашинский В.И. Введение в нейро-цифровые инфоком-муникационные технологии /У XI Санкт-Петербургская международная конференция «Региональная информатика-2008» (РИ-2008): материаты / СПОЛСУ. СПб. 2008. С. 76.

\]. Берёзкин A.A. Перспективы развития современных методов помехоустойчивого кодирования в нейро-цифровом логическом базисе // Международная НПК «Перспективы развития телекоммуникационных систем и информационные технологии»: труды конференции /СПБГПУ. СПб, 2008. С. 10 -16.

12.Берёзкин A.A. Построение оптимальных нейронных декодеров блоковых кодов // Научно-технические ведомости СПбГПУ / СПбПГУ. СПб, 2008. № 5. С.34 - 41. № перечня гаданий, рекомендованного ВАК).

13. Берёзкин A.A. Итеративно-перестановочный метод декодирования двоичных линейных блоковых кодов // Научно-технические ведомости СПбГПУ / СПбПГУ, СПб. 2009. № 2. С.193 - 199. (Из перечня изданий, рекомендованного ВАК).

14. Берёзкин АА. Нейронный декодер двоичных блочных кодов с исправлением ошибок и стираний, патент РФ на полезную модель по заявке №2009108326/22, положительное решение о выдаче патента от 25.03.2009г.

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

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

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ.

ВВЕДЕНИЕ.б

1. АНАЛИЗ МЕТОДОВ ДЕКОДИРОВАНИЯ ПОМЕХОУСТОЙЧИВЫХ КОДОВ.

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

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

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

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

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

2. ХАРАКТЕРИСТИКА СУЩЕСТВУЮЩИХ МОДЕЛЕЙ ДЕКОДЕРОВ ДВОИЧНЫХ БЛОКОВЫХ КОДОВ.

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

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

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

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

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

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

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

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

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

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

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

2.4. Выводы.

3. РАЗРАБОТКА МОДЕЛЕЙ И МЕТОДОВ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ДВОИЧНЫХ БЛОКОВЫХ КОДОВ.

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

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

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

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

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

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

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

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

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

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

3.6. Выводы.

4. ОЦЕНКА СЛОЖНОСТИ ФУНКЦИОНИРОВАНИЯ РАЗРАБОТАННЫХ МЕТОДОВ

ДЕКОДИРОВАНИЯ ДВОИЧНЫХ БЛОКОВЫХ КОДОВ.

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

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

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

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

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

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

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

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

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

4.5. Выводы.

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

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

В настоящее время задачи сокращения задержек подобного рода решаются различными путями, в том числе внедрением параллельных методов кодирования и декодирования, основанных на элементах теории искусственных нейронных сетей (ИНС). Элементной базой ИНС является технипгг^геская реализация прототипа биологического нейрона, который служит базисс^хзч* для построения таких систем. На сегодняшний день отечественныз^гч/ги и зарубежными исследователями (Галушкин А.И-., Комашинский В.И., бан ь

А.Н., Оссовский С., Bruck J., Blaum М., Mayora-Ibarra О., Zeng G., Htl ~Fsh D: Ahmed N., Stefano A.D., Lippmann R.P., Ahmed S. и др.) предложено мно^^ь^сество различных нейросетевых моделей, в том числе решающих ^задачи декодирования помехоустойчивых кодов. Однако до. сих пор не разра5чсЗотана единая концепция их применения и- настройки. Это влечет за собой увехгг^згчение структурной избыточности нейронных декодеров и сложности—е^т их функционирования. Более того, указанные вопросы требуют проработки применительно к широко используемым кодовым констр^ч-^кциям блоковых помехоустойчивых кодов, что обуславливает актуальность настиг-оящей работы, направленной на повышение обоснованности применения %г-ЗГЕ-IC в задачах помехоустойчивого кодирования. •

В то же время разработчики' современных СПК должны цгзэешать компромиссную задачу «сложность-эффективность». На прогр^2!л\<гмно-аппаратном уровне, решение этих задач приводит к необходимосжг~л как алгоритмического, так и технического упрощения, включающего ^выбор наименее сложной реализации алгоритма. Сегодня критерием выбора толг^о или иного метода декодирования, как правило, является его помехоустой*^с^ВОсть или корректирующая способность, сложности же программной реахг^агзации декодеров уделено явно недостаточное внимание.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.5. Выводы

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

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

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

4. Установлено, что сложность РНД2 и РНД2м меньше сложности РНД1 в среднем в 2К раз в связи с отсутствием рекуррентного слоя распознавания.

НД11Р в случае рассматриваемых кодов имеет наименьшую сложность функционирования при всех равных условиях и по сравнению с РНД1 она меньше в среднем на 67,6%.

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

6. Эффективность разработанных в работе РНД2(2м) и НДПР сравнена с частными результатами других исследователей с точки зрения сложности функционирования с использованием введенного комплексного показателя. Показано, что полученные результаты согласуются с известными данными и в случае рассматриваемых кодов сложность предложенных НД меньше сложности известных НД в среднем на 56,4% при всех равных условиях.

ЗАКЛЮЧЕНИЕ

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

Основными результатами данной диссертационной работы являются:

1. Итеративно-перестановочный метод декодирования двоичных линейных блоковых кодов. Предложены дополнительные проверочные уравнения для метода итеративного декодирования линейных блоковых кодов. Показано, что энергетический выигрыш от использования итеративно-перестановочного метода на примере (7,4) кода Хэмминга составляет [0,1 - 0,5] дБ (для 1 итерации) по отношению к методу использования только основных фаз итерации декодирования. Выигрыш заметен уже при вероятности ошибки 10

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

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

4. Модель нейронного кодера и декодера, построенная на основе модели нейронного классификатора Хэмминга, для использования «жестких» и «мягких» решений в демодуляторе, а также исправления стираний, которая в отличие от известных не содержит второй скрытый слой рекуррентных нейронов. Это позволило сократить в среднем в 2 раза общее число нейронов и уменьшить в среднем в 2К раз сложность функционирования, а также устранить переменную задержку при декодировании.

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

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

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

7. Матрицы значений свободных параметров разработанных моделей (значений весовых коэффициентов и смещений (порогов) слоев нейронных декодеров) для кодов БЧХ длины до 15, работающих в режимах исправления: 1) ошибок, 2) ошибок и стираний.

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

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

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

1. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В.Б.Афанасьева. — М.: Техносфера. 2005.

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

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

4. Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.

5. Скляр Б. Цифровая связь. Теоретические основы и практическое применение / пер. с англ. — изд. 2-е., испр. — М.: Вильяме, 2004.

6. Всрнер М. Основы кодирования / пер. с нем. Д.К.Зигангирова. — М.: Техносфера, 2004.

7. Витерби А.Д., Омура Д.К. Принципы цифровой связи и кодирования. — М.: Радио и связь, 1982.

8. Hagenauer J. Iterative Decoding of Binary Block and convolutional Codes // IEEE Transactions on Information Theory. 1996. - Vol. 42. - n. 2. - P. 1261-1271.

9. Wolf J.K. Efficient Maximum-Likelihood Decoding of Linear Block Codes Using a Trellis // IEEE Transactions on Information Theory. 1978. - Vol. IT-24. -n. 1. - P. 76-80.

10. Bahl L.R., Cocke «/., Jelinek F., Raviv J. Optimal decoding of linear codes for minimizing symbol error rate // IEEE Transactions on Information Theory. — 1974. — Vol. 20. — n. 2. — P. 284-287.

11. Forney G.D. jr, Trott M.D. The dynamics of group codes: State spaces, trellis diagrams and canonical encoders // IEEE Transactions on Information Theory. — 1993. — Vol. 39. — P. 1491-1513.

12. Kschischang F.R., Sorokine V. On the trellis structure of block codes // IEEE Transactions on Information Theory. 1995. - Vol. 41. - P. 1924-1937.

13. Massey J.L. Foundations and methods of channel encoding // Proc. Int. Conf. on Information Theory and Systems. Berlin. — 1978.

14. McEliece RJ. On the BCJR trellis for linear block codes // IEEE Transactions on Information Theory. 1996. - Vol. 42. - P. 1072-1092.

15. Muder D.J. Minimal trellises for block codes // IEEE Transactions on Information Theory. — 1988.-Vol. 34.-P. 1049-1053.

16. Lin S., Kasami T., Ftijiwcira T., Fossorier M. Trellises and Trellis-Based Decoding Algorithms for Linear Block Codes. — Kluwer: Kluwer Academic Press, 1998.

17. Honay B., Markarian G.S. Trellis Decoding of Block Codes: A Practical Approach. — Kluwer: Kluwer Academic Press, 1996.

18. Hagenauer J., Hoher P. A Viterbi Algorithm with Soft-Decision Outputs and Its Applications // IEEE Global Telecommunications Conference (GLOBECOM'89). 1989. - P. 47.1.1 -47.1.7.

19. Robertson P., Villebrun E., Hoeher P. A Comparison of'Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain // IEEE International Conference on Communications (ICC'95). 1995. - P. 1009-1013.

20. Fossorier M., Lin S. Soft-Decision Decoding on Linear Block Codes Based on Ordered Statistics // Transactions on Information Theory. — 1995. — Vol. 41. — n. 5. — P. 1379-1396.

21. Forney G.D. Generalized Minimum Distance Decoding // IEEE Transactions on Information Theory. 1966. - Vol. IT-12. — P. 125-131.

22. Kaneko T., Nishijima T., Inazumi II., Hirasawa S. An Efficient Maximum-Likelihood Decoding Algorithm for Linear Block Codes with Algebraic Decoder // IEEE Transactions on Information Theory. 1994. - Vol. 40. - n. 2. - P. 320-327.

23. Kamiya N. On Algebraic Soft-Decision Decoding Algorithms for BCH Codes // IEEE Transactions on Information Theory. — 2001. — Vol. 47. — n. 1. — P. 45-58.

24. Tokushige H., Koumoto T., Kasami T. An Improvement to GMD-like Decoding Algorithms // Proc. 2000 IEEE Int. Symp. Info. Theory (ISIT'00). 2000. - P.396.

25. Fossorier M., Lin S. Complementary Reliability-Based Soft—Decision Decoding on Linear Block Codes Based on Ordered Statistics // IEEE Transactions on Information Theory. — 1997. — Vol. 42. — n. 5. — P. 1667-1672.

26. Tang H., Liu Y., Fossorier A/., Lin S. On Combining Chase-2 and GMD Decoding Algorithms for Nonbiliary Block Codes // IEEE Comm. Letters. 2001. - Vol. 5. - n. 5. - P. 209-211.

27. Berrou C., Glavieux A., Thitimajshima P. Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes // IEEE Prceedings of the Int. Conf. on Communications (ICC'93). — 1993. -P. 1064-1070.

28. Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. — Morgan Kaufmann, 1988.

29. Kschischang R.R., Frey B.J., Loeliger HA. Factor Graphs and the Sum-Product Algorithm //s

30. EE Transactions on Information Theory. 2001. - Vol. 47. - n. 2. - P. 498-519.

31. Forney G.D. Codes and Graphs: Normal Realizations // IEEE Transactions on Information Theory. 2001. - Vol. 47. - n. 2. - P. 520-548.

32. Gallager R.G. Low-Density Parity-Check Codes // IRE Transactions on Information Theory. — 1962.-Vol. 8.-P. 21-28.

33. MacKay D. Good Error-Correcting Codes Based on Very Sparse Matrices // IEEE Transactions on Information Theory. 1999. - Vol. 45. - n. 2. - P. 399-432.

34. Tanner R.M. Recursive Approach to Low Complexity Codes // IEEE Transactions on Information Theory. 1981. - Vol. 1T-27. - n. 5. - P. 533-547.

35. Sipser M., Spielman DA. Expander Codes // IEEE Transactions on Information Theory. — 1996.- vol. 42. n. 6. - P. 1710-1722.

36. Richardson T.J., Shokrollahi MA., Urbanke R.L. Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes // IEEE Transactions on Information Theory. — 2001. — Vol. 47. -n. 2.-P. 619-637.

37. Classon B.K. Chase iteration processing for decoding input data // Патент US 6,460,160 Bl. — Oct. 1.-2002.

38. Narayanan K.R., Jiang ./., Nangare NA. Iterative decoding of linear block codes by adapting the parity chcck matrix // Патент US 2005/0229091 A1. Oct. 13. - 2005.

39. Chouly A. Iterative decoding for binary block codes // Патент US 6,574,775 Bl. — Jun. 3. — 2003.

40. Tomlinson M. Error correction decoder using parity check equations and Gaussian reduction // Патент GB 2,426,671 A. Nov. 11,- 2006.

41. Gerlach D., KoralekR., Jones V.K., Raleigh G.G. Iterated soft-decision decoding of block codes // Патент US 6,725,411 Bl. Apr. 20. - 2004.

42. Кожичкин E.C. Поисковая система, основанная на нейронной сети // Проект InterSearch.2001. Электронный ресурс. URL: http://kes.narod.ru/projecls/lnterSearch (дата обращения: 21.11.2008).'

43. Карпов Ю.Г. Теория автоматов. — СПб.: Питер, 2002.

44. Bruck J., Blaum M. Neural Networks, Error-Correcting Codes, and Polynomails Over the Binary N-cube // IEEE Trans. On Information Theory. 1989. - Vol. 35. - P. 976-987.

45. Takefuji Y., Hollis P., Foo Y.P., Cho Y.B. Error Correcting System Based on Neural Circuits // Proc. Of IEEE 1st International Conference on Neural Networks. 1987. - Vol. 3. - P. 293-300.

46. Yuan J., Chen C.S. Correlation Decoding of the (24, 12) Golay Code Using Neural Networks // IEEE Procecdings-I. 1991. - Vol. 138. - P. 517-524.

47. Zeng g., Hush D., Ahmed N. An application of neural net in decoding error-correcting codes // IEEE International Symposium on Circuits and Systems. 1989. - P. 782-785.

48. Stefano A.D, Mirabella ()., Cataldo G.D., Palumbo G. On the use of neural networks for hamming coding // IEEE International Symposium on Circuits and Systems. 1991. - Vol. 3. - P. 1601-1604.

49. Co id W.R., Means R.W. Neural Network Error Correcting Decoders for Block and Convolutional codes // GLOBECOM'90 Proceedings. 1990. - P. 1028-1031.

50. Mayora-Ibarra O., Gonzales-Gutierres A., Ruiz-Suarez, J.C. Neural Networks for Error Correction of Hamming Codes // IEEE Information Theory and Statistics. — 1994.

51. MakS.K., Aghvami A.H. Soft-decision decoding of block codes using neural network // Global Telecommunications Conference, Technical Program Conference Record, IEEE in Huston (GLOBECOM'93). 1993. - P. 971-974.

52. Lippmann R. P. An Introduction to computing with neural nets // IEEE Trans. On Acoustics, Speech and Signal Processing. — 1987. — P. 4-22.

53. Wu J.l., Tseng y.H., Huang Y.M. Neural Network decoders for linear block codes // International Journal of Computational Engineering Science. —2002. — Vol. 3. — P. 235-255.

54. Рутковская д., Пилиньский m., Рутковский ji. Нейронные сети, генетические алгоритмы и нечеткие системы / пер. с польского И.Д. Рудинского. — М.: Горячая линия — Телеком, 2006.

55. Bar tie tt P., Downs Т. Training a neural networks with a genetic algorithm // Technical Report, Dept. of Elec. Eng. — University of Queensland. — 1990.

56. Ack.ley D.H. A connectionist machine for genetic hillclimbing. — M.A.: Kluwer Academic Publishers, 1987.

57. El-Khamy S.E., El-Sayed A.y., Hossam-El-Din MA. Soft decision decoding of block codes using artificial neural network // Proceedings of the IEEE Symposium on Computers and Communications (ISCC'95). 1995.

58. Hamalainen A., Henriksson. Convolutional Decoding Using Recurrent Neural Networks // IEEE Proceedings of International Joint Conf. on Neural Networks. — 1999. — Vol. 5. — P. 3323-3327.

59. Hamalainen A., Henriksson. Novel Use of Channel Information in a Neural Convolutional Decoder // IEEE Proceedings of International Joint Conf. on Neural Networks (IJCNN^OOO). —2000. Vol. 5. - P. 337-342.

60. Wicker S.B., Wang X. An Artificial Neural Net Decoder // IEEE Transaction on Communications. Feb. 1996. - Vol. 44. - n. 2. - P. 165-171.

61. Berber S.M. Soft Decision Decoding (SONNA) Algorithm for Convolutional Codes Based on Artificial Neural Networks // Second IEEE International Conference on Intelligent Systems. — June 2004, P. 530-534.

62. Terence E.D. Neural Networks Decoder // Патент US 2004/0220891 Al. Nov. 2004.

63. Masakazu E., Hidenori I., Shigeru K., Iwamura. Data Communication method and apparatus using neural-networks // Патент US 4,972,473. — Nov. 1990.

64. Alec K.E., TerryA.W. Method and apparatus for recognizing characters // Патент US 5,303.311. -Apr. 1994.

65. ТюрингА. Может ли машина мыслить? — М.: Физматгиз, 1960.

66. Savage J.E. The Complexity of Decoders: Classes of Decoding Rules // IEEE Transactions on Information Theory! 1969. - Vol. IT-15. - P. 689-695.

67. Savage J.E. The Complexity of Decoders. Part IV. Computational Work and Decoding Time // IEEE Transactions on Information Theory. — 1971. — Vol. IT-17. — P. 77-85.

68. Блох Э.Л., Зяблое B.B. Обобщённые каскадные коды. Алгебраическая теория и сложность реализации. — М.: Связь, 1976.

69. Fortune, J.W. Parallelism in Random Access Machines // Proceedings of the 10th Annual ACM Symposium on Theory of Computing. — 1978. — P. 114-118.

70. Макконел Д. Основы современных алгоритмов. — М.: Техносфера, 2004.

71. Кормен Т., Лейзерсоп Ч., Pueecm Р. Алгоритмы: построение и анализ. — М.: МЦНМО,2001.

72. Garey М., Johnson D. Computers and Intractability: A Guide to the Theory of NP-Completeness. — San Francisco: Freeman, 1978.

73. Сложность алгоритма: сайт кафедры ИТ Курганского Государственного Университета. — 2003. Электронный ресурс. URL: http://it.kgsu.ru l'I7/oglav.htinl (дата обращения: 21.11.2008).

74. Гори М., Джопсоп Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982.

75. Berlekamp Е., McEliece R,, Tilborg Н. On the inherent intractability of certain coding problems // IEEE Trans. On Information Theory. 1978. - Vol. IT-24. - P. 384-386.

76. Изосимов A.B., Рыжко АЛ. Метрическая оценка качества программ. — М.: МАИ, 1989.

77. Xo.icmed М. Начала науки о программах. — М., 1981.

78. Павлов В. Метрики // персональный сайт Павлова В. — 2006. Электронный ресурс. URL: hllp: Vmct-rix.naH4l.ru/pagcl .htm (дата обращения: 21.11.2008).

79. Oviedo E.J. Control flow, data flow and program complexity // Proc. IEEE COMPSAC. — Nov. 1980.-P. 146-152.

80. Капустин A.B. Модели и метрики оценки качества ПО // персональный сайт Андрея Капустина. — 2003. Электронный ресурс. Дата обновления: 03.02.2006. — URL: http://kapustin-anclre\.boom.ru/Materiais/Mctrics2.htm (дата обращения: 21.11.2008).

81. Бахтизин В.В., Глухова JIA. Применение метрик сложности при разработке программных средств. Мн.: БГУИР, 2003.

82. Elias P. Error-Free Coding // IRE Transactions on Information Theory. — 1954. — Vol. PGIT-4. P. 29-37.

83. MasseyJ.L. Threshold Decoding. — MIT Press, 1963.

84. Оссовский С. Нейронные сети для обработки информации / пер. с польского И.Д. Рудинского. — М.: Финансы и статистика, 2004.

85. Floreen P. The convergence of Hamming memory networks // IEEE Trans. Neural Networks. -1991.-Vol. 2.-P. 449-457.

86. Hornik K., Stinchcombe M., White H. Multilayer feedforward networks are universal approximators // Neural Networks. 1989. - Vol. 2. - P. 359-366.

87. Haykin S. Neural networks, a comprehensive foundation. — N.Y.: Macmillan College Publishing Company, 1994.

88. Хайкип С. Нейронные сети: полный курс / пер. с англ. — 2-е изд., испр. — М.: ООО "И.Д. Вильяме", 2006.

89. Sprecher DA. On the structure of continuous functions of several variables // Transactions of the American Mathematical Society. — 1965. — Vol. 1. — P. 36-45.

90. Gallant, A.R., White, H. There exists a neural network that does not make avoidable mistakes // IEEE International Conference on Neural Networks. — 1988. — vol. 1. — P. 675-664.

91. Cybenko, G. Aproximation by superpositions of a sigmoidal function // Mathematics of Control, Signals and Systems. 1989. - Vol. 2. - P. 303-314.

92. Cybenko, G. Aproximation by superpositions of a sigmoidal function. — Urbana, IL.: University of Illinois, 1988.

93. ФорниД. Каскадные коды / пер. с англ. — М.: Мир, 1970.

94. Osowski S. Sieci neuronowe w ujeciu algorytmicznym. — Warszawa: WNT. 1996.96. #ec/zi-Nielsen R. Neurocomputing. — Amsterdam: Addison Wesley, 1991.

95. Kolmogorov A.N. On the representation of continuous functions of many variables by superposition of continuous functions of one variable and addition // Доклад академии наук СССР. 1957. - Vol.114. - P. 953-956.

96. Ресурс по программному обеспечению Statistica Neural Networks компании StatSoft Russia. — 2008. Электронный ресурс. URL: http://vvvvw.statsoft.ru (дата обращения: 21.11.2008).

97. Vapnik V.N. Statistical Learning Theory. New York: Wiley, 1998.

98. Vapnik V.N. Principles of risk minimization for learning theory // Advances in -Neural Information Processing Systems. 1992. - Vol. 4. - P. 831-838.

99. Vapnik V.N., Chervonenkis A.Y. On the uniform convergence of relative frequencies of events to their probabilities // Theoretical Probability and Its Applications. — 1971. — Vol. 17. — P. 264-280.

100. BanniiK B.H., Червоненкис АЛ. О равномерной сходимости частот появления событий к их вероятностям // ДАН СССР. Т. 181. - № 4. - 1968.

101. Вапник В.II., Червоненкис АЛ. Теория распознавания образов. — М.: Наука, 1974.

102. Вапник В.Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.

103. Vapnik V.N. Estimation of Dependences Based on Empirical Data. — New York: SpringerVerlag, 1982.

104. Kearns M.J., Vazirani U.V. An Introduction to Computational Learning theory. Cambridge. M.A.: MIT Press, 1994.

105. Vidyasagar M. A Theory of Learning and Generalization. — London: Springer-Verlag, 1997.

106. Baum E.B., Haussler D. What size net gives valid generalization // Neural Computation. — 1989.-Vol. l.-P. 151-160.

107. Cover T.M. Capacity problems for linear machines. — Washington, DC: Thompson Book Co, 1968.

108. Koiran P., Sontag E.D. Neural networks with quadratic VC dimension. Cambridge. — M.A.: MIT Press, 1996.

109. Hush D., Horme B. Progress in supervised neural networks 11 IEEE Signal Processing Magazine. — January 1993. — P. 8-39.

110. Htay M. M., Iyengar S. S., Si-Oing Zheng. Correcting Errors in Linear Codes with Neural Network // Proceedings of the 27th Southeastern Symposium on System Theory (SSST'95). — 1995. -P. 386-391.

111. Evans D. J., Adamopoulos M., Kortesis S., Tsouros K. Searching sets of properties with neural networks // Parallel Computing 16. North-Holland. 1990. - P. 279-285.

112. Esposito A., Rampone S. A Neural Network for Error Correcting Decoding of Binary Linear Codes //Neural Networks. 1994. - Vol. 7. - P. 195-202.

113. Hertz J., Kaogh A., Palmar R.G. Introduction to the theory of neural computing. — Addison Welsley Publishing Company, 1991.

114. Kcvuian P. Основные концепции нейронных сетей. М.: Вильяме, 2003.

115. Вешпцель Е.С. Теория вероятностей: учеб. для вузов. — 6-е изд., стереотипное. — М.: Высш. шк., 1999.

116. Haykin S. Neural networks expand SP's horizons // IEEE Signal Processing Magazine. — 1996.-Vol. 13.-n. 2.-P. 24-29.

117. Дьяконов В.П., Круглое B.B. Matlab 6.5 SP1/7/7 SP1/7 SP2 + Simulink 5/6. Инструменты искусственного интеллекта и биоинформатики. — М.:СОЛОН-ПРЕСС, 2006.

118. Mehrotra К., Mohan С., Ranka S. Bounds on the number of samples needed for neural learning // IEEE Trans. Neural Networks. 1991. - Vol. 2. - P. 548-558.

119. Гудмаи С. Хидетниеми С. Введение в разработку и анализ алгоритмов. — М.: Мир, 1981.

120. Ульянов М.В. Классификации и методы сравнительного анализа вычислительных алгоритмов. — М.: Издательство физико-математической литературы, 2005.

121. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука, 1994.

122. Ершов А.П. Введение в теоретическое программирование. Беседы о методе. — М.: Наука, 1977.

123. Евстигнеев В А. Применение теории графов в программировании. — М.: Наука, 1985.

124. Уилсон Р. Введение в теорию графов. — М.: Мир, 1977.

125. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы / пер. с англ. — М.: Вильяме, 2001.

126. Вирт Н. Алгоритмы и структуры данных / пер. с англ. 2-ое изд., испр. — СПб.: Невский диалект, 2001.

127. Березкин А А. Оценка сложности реализации современных методов декодирования помехоустойчивых кодов // Труды учебных заведений связи / СПбГУТ. — СПб, 2005. № 172. С. 11-18.

128. Разборов АА., Кузюрин Н.Н. Оценка состояния и прогнозные исследования эффективных алгоритмов для точного и приближённого решения переборных задач дискретной оптимизации, отчёт по НИР, 1996.

129. КуцА.К. Математическая логика и теория алгоритмов. — О.: Наследие. 2003.

130. Березкин А А., Охорзин В.М. Оценка сложности реализации методов декодирования кодов Рида-Соломона// 58 НТК: маг-лы. / СПбГУТ. СПб, 2004.

131. Вялый М., КитаевА., ШенъА. Классические и квантовые вычисления. — М.: МЦПМО, 1999.

132. Березкин А А., Охорзин В.М. Исследование методов декодирования кодов Рида-Соломона при исправлении стираний // 57 НТК: мат-лы. / СПбГУТ. СПб, 2005.

133. Elias P. Error-Correcting Codes for List Decoding // IEEE Transactions on Information Theory. 1991. - Vo. 37. - n. 1. - P. 5-12.

134. Guruswami V., Sudan M. Improved Decoding of Reed-Solomon and Algebraic-Geometry Codes // IEEE Transactions on Information Theory. — 1999. — Vol. 45. — n. 6. — P. 1757-1767.

135. Sudan M. Decoding of Reed-Solomon Codes Beyond the Error-Coriection Bound // J. Complexity. 1997. - Vol. 12. - P. 180-193.

136. Berlekamp E.R. Bounded Distance + 1 Soft—Decision Reed-Solomon Decoding // IEEE Transactions on Information Theory. — 1996. — Vol. 42. — n. 3. — P. 704-720.

137. Mason S. J. Feedback theoiy — Some properties of signal-flow graphs. Processings of the Institute of Radio Engineers. 1953. - Vol. 41. - P. 1144-1156.

138. Mason S. J. Feedback theory — Further properties of signal-flow graphs. Processings of the Institute of Radio Engineeis. 1956. - Vol. 44. - P. 920-926.

139. Barron A. R. Approximation and estimation bounds for artificial neural netwoiks. Machine learning. 1994. - Vol. 14. - P. 115-133.

140. Koetter R., Vardy A. Algebraic Soft-Decision Decoding of Reed-Solomon Codes // IEEE International Symposium on Information Theory (ISIT'OO). — 2000. — P. 61.

141. Levine M. Man and Machine Vision. — New York: McGraw-Hill, 1985.

142. Aleksander I., Morton H. An Introduction to Neural Computing. — London: Chapman and Hall, 1990.

143. Suga N. Computations of velocity and range in the bat auditory system for echo location, in Computational Neuroscience, Cambridge. — MA: MIT Press, 1990. — P. 213-231.

144. Hopfield J. Neural networks and physical systems with emergent collective computational abilities // Proc. National Academy of Science USA. 1982. - Vol. 79. - P. 2554-2558.

145. Hopfield J., Tank D. Computing with neural circuits: a model // Science. — 1986. — Vol. 233.-P. 625-633.

146. Li Z.J., Shi ВЛ'., Li B.O. Hamming neural network circuit // Патент US 5,630,021. May 1997.

147. Li Z.J., Shi BX., Lu W. Current-mode Hamming neural network // Патент US 5,720.004. -Feb. 1998.

148. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

149. Мшлер Р., Боксер Л. Последовательные и параллельные алгоршмы / пер. с англ. —М.: БИНОМ. Лаборатория знаний, 2006.

150. Гергелъ В.П. Теория и практика параллельных вычислений. — М.: БИНОМ. Лаборатория знаний, Интернет университет информационных технологий — ИНТУИТ.ру, 2007.

151. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. — СПБ.: БХВ-Петербург, 2002.

152. Гергелъ В.П., Стронгип Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. — Н.Новгород: ННГУ, 2003.

153. Материалы информационно-аналитического центра по параллельным вычислениям // МГУ, Москва. 2008. Электронный ресурс. URL: http://paraUcl.ru (дага обращения: 28.01.2009).

154. Антонов А.С. Введение в параллельные вычисления. — М.:МГУ, 2002.

155. Старченко А.В., Есаулов А.О. Параллельные вычисления на многопроцессорных вычислительных системах. — Томск: ТГУ, 2002.

156. Хокпи Р., Джессхоуи К. Параллельные ЭВМ. Архитектура, программирование, алгоритмы. — М.: Радио и связь, 1986.

157. Корнеев В.В. Параллельные вычислительные системы. — М.: Изд-во "Нолидж", 1999.

158. Ahmed S. Linear block code decoder using neural network // IEEE International Joint Conference on Neural Networks (IJCNN'08). 2008. - P. 1111-1114.

159. Проблемы построения и обучения нейронных сетей / под ред. А.И. Галушкина и В.А. Шахнова. — М.: Изд-во Машиностроение. Библиотечка журнала Информационные технологии.- 1999.-№ 1.-С. 105.

160. Галушкин А.И. Некоторые исторические аспекты развития элементной базы вычислительных систем с массовым параллелизмом (80- и 90-е годы) // Неирокомпышер. — 2000.-№ 1.-С. 68-82.

161. Горбапъ А.Н., Россиев Д.А. Нейронные сети на персональном компьютере. — Новосибирск: Наука. Сибирская издательская фирма РАН, 1996.

162. Власов А.И. Аппаратная реализация нейровычислительных управляющих систем // Приборы н системы управления. — 1999. — №2. С. 61-65.

163. Колесников С. Аппаратная реализация нейронных сетей // Журнал «Компьютер-ниформ» №17. — 2005. Электронный ресурс. URL: hüp://\\\\ w.ci.m/inform 17 05'р 24.htm (дата обращения: 28.01.2009).

164. Лнфилатов B.C., Емельянов A.A. Кукушкин A.A. Системный анализ в управлении: Учеб. пособие. — М.: Финансы и статистика, 2002.

165. Месарович М., Такахара Я. Общая теория систем: Математические основы. — М.: Мир, 1978.

166. Лагоша Б.А., Емельянов A.A. Основы системного анализа. — М.: Изд-во МЭСИ. 1998.

167. Процессор цифровой обработки сигналов J11879BM1 (NM6403) // НТЦ «Модуль». — 2009. Электронный ресурс. URL: http://www.module.ru/ruproducts/proc/nrn6403.shtml (дата обращения: 10.03.2009).