Модели и методы декодирования помехоустойчивых кодов на основе нейросетевого базиса
Исследование современного итеративного метода декодирования. Особенности повышения эффективности системы помехоустойчивого кодирования за счет использования параллельных нейронных декодеров, существенно снижающих задержки на операцию декодирования.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | автореферат |
Язык | русский |
Дата добавления | 31.07.2018 |
Размер файла | 1,3 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
Модели и методы декодирования помехоустойчивых кодов на основе нейросетевого базиса
Специальность 05.13.01 - Системный анализ, управление и обработка информации
кандидата технических наук
Берёзкин Александр Александрович
Санкт-Петербург, 2009г.
Работа выполнена в Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича.
Научный руководитель: кандидат технических наук, доцент Охорзин Виктор Михайлович
Официальные оппоненты: доктор технических наук, профессор Саенко Игорь Борисович
кандидат технических наук Кунгурцев Вадим Викторович
Ведущая организация: ФГУП НИИ «Рубин»
Защита состоится «02» июля 2009г. в 14 часов на заседании диссертационного совета Д219.004.02 при Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича по адресу: 191065, Санкт-Петербург наб.р. Мойки, 61.
С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного университета телекоммуникаций им. проф. М.А. Бонч-Бруевича.
Отзыв на автореферат в двух экземплярах, заверенный печатью учреждения, просим направлять по указанному адресу на имя ученого секретаря диссертационного совета.
Автореферат разослан «01» июня 2009 г.
Ученый секретарь диссертационного совета,
кандидат технических наук, доцент В.Х. Харитонов
декодирование нейронный помехоустойчивый
Общая характеристика работы
Актуальность работы. Современный этап развития телекоммуникационных систем характеризуется широким развитием проводных и беспроводных сетей передачи данных. Рост числа пользователей таких сетей, появление новых мультимедийных услуг предъявляют высокие требования к скорости, надежности и времени задержки при обработке информации. Одна из самых весомых задержек связана с помехоустойчивым кодированием и декодированием данных. Для снижения этого фактора постоянно необходимо решать проблемы совершенствования существующих и разработки новых методов обработки информации.
В настоящее время подобные проблемы решаются различными путями, в том числе внедрением параллельных методов кодирования и декодирования, основанных на элементах теории искусственных нейронных сетей (ИНС). На сегодняшний день отечественными и зарубежными исследователями (Галушкин А.И., Горбань А.Н., Комашинский В.И., Оссовский С., Bruck J., Blaum M., Mayora-Ibarra O., 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. Методика оценки сложности функционирования методов кодирования и декодирования на основе комплексного показателя.
Содержание работы
Во введении обоснована актуальность рассматриваемой проблемы, сформулированы цели и задачи работы, определены практическая ценность и область применения результатов, представлены основные научные положения, выносимые на защиту.
В первой главе диссертации рассмотрено современное состояние проблемы декодирования помехоустойчивых кодов и оценки сложности методов декодирования.
Показано, что декодирование есть отображение множества принимаемых кодовых комбинаций (КК) на множество информационных слов, которое может состоять из композиции двух отображений (нахождения кодового слова по принятому и определения вектора информационных символов по кодовому слову):
а) или б) , (1)
где - алфавит из : * - символ стирания, D - оператор нахождения кодового слова, - множество принимаемых КК, - множество всех разрешенных кодовых комбинаций (РКК), - множество информационных слов РКК. Отмечено, что на задержки декодирования напрямую влияет сложность отображения D.
Отмечено, что новые методы декодирования, необходимо рассматривать с позиций развития существующих современных методов. Приведен обзор направлений развития современных методов «мягкого» декодирования блоковых кодов и отмечены их недостатки. Обосновывается выбор метода итеративного декодирования, а также направление его модификации.
Выявлена необходимость в разработке параллельных методов кодирования и декодирования на основе моделей ИНС. Проведен обзор результатов различных исследователей в данной области.
Сделаны выводы об актуальности рассмотрения проблем декодирования применительно к сложности их функционирования.
Таким образом, полученные в главе 1 результаты, позволили обосновать выбор направления исследований и выявить необходимость в разработке параллельных методов кодирования и декодирования на основе моделей ИНС.
Во второй главе выбраны, изучены и исследованы известные модели НД и итеративного декодера.
Обосновывается использование известной математической модели итеративного декодера, описываемой формулой
, (2)
где ? LLR («мягкий» выход) вне декодера, Lc(x) ? LLR канала (получается в результате канальных измерений в приемнике), L(d) ? априорное LLR бита данных, ? внешнее LLR (внешняя информация о структуре кода, выявляемая в процессе декодирования). На основе используемой математической модели описан обобщенный алгоритм итеративного декодирования блоковых кодов и показаны возможности его модификации [4].
Для достижения цели работы выбраны, изучены и исследованы известные в научно-технической литературе модели ИНС, предназначенные для решения задач классификации и задач, относящихся к классу проблем построения отношений на множестве объектов. Показано, что данные модели непосредственно осуществляют отображение (1) без проведения сложных процедур комбинаторного или алгебраического декодирования:
модель нейронного классификатора Хэмминга, в виде рекуррентного нейронного декодера 1-й модификации (РНД1) (рис. 1а) [5-7]. Использование данной модели позволяет решить задачу декодирования блоковых кодов по критерию максимального правдоподобия с использованием «жесткой» схемы принятия решений в демодуляторе. Показано, что РНД1 обеспечивает отображение (1б);
модель обучаемой ИНС (рис. 1б), построенной на основе многослойного персептрона (сети с прямым распространением сигнала) с антисимметричными сигмоидальными функциями активации, в виде нейронного декодера прямого распространения (НДПР), обеспечивающего отображение (1а). Использование НДПР позволит разработчику СПК полностью реализовать корректирующие возможности используемых кодов [8].
Рис. 1. Модели НД а) нейронный классификатор Хэмминга (РНД1); б) обучаемая ИНС
Установлено, что РНД1 вводит случайные задержки при декодировании, зависящие от кратности и распределения ошибок и использует «жесткие» решения в демодуляторе. Показано, что совершенствовать структуру РНД1 можно путем сокращения циклов в слое распознавания; в данной работе предлагается исключить слой распознавания из структуры РНД1 как избыточный путем более точной настройки параметров нейронов слоя образцов на параметры кода, адаптировать структуру для использования «мягких» решений в демодуляторе и проанализировать, каким образом это отразится на функционировании декодера в целом.
Показаны физические процессы декодирования, протекающие при выполнении отображения (1) с помощью предлагаемых моделей НД (рис. 2).
а)
б)
Рис.2. Реализация отображения множества принимаемых КК на множество информационных слов а) при использовании РНД1; б) при использовании НДПР
Для определения направления совершенствования НДПР (рис. 1б) детализируем процесс его настройки и функционирования при непосредственной реализации отображения (1а). Каждый из нейронов скрытого слоя (слой 1) НДПР отвечает за создание гиперплоскости в пространстве свободных (настраиваемых) параметров декодера. Под свободными параметрами будем понимать веса синаптических связей и смещений нейронов НДПР. В процессе обучения (настройки) НДПР комбинация гиперплоскостей, сформированных всеми нейронами декодера, итеративно трансформируется (с наименьшей средней ошибкой) для разделения примеров обучающего множества (ОМ), преднамеренно взятых из разных классов РКК, где под ОМ понимается множество частных отображений вида:
, (3)
где - i-ая КК из множества всех принимаемых КК, - i-ое информационное слово, связанное с . Результаты декодирования с использованием НДПР априорно реализуются на этапе разработки в виде множества частных отображений (3). В процессе функционирования при зафиксированных значениях свободных параметров производится простой расчет отображения (1), а именно получение результатов декодирования из памяти сети. Рассмотренный процесс проиллюстрирован на рис. 2б.
Суть действий НДПР полностью определяется качеством ОМ (3). Установлено, что выбор данных обучения и их размещение относительно конкретных гиперплоскостей становится очень важным для минимизации размера скрытого слоя L (рис. 1б), который полностью определяет структуру и сложность функционирования НДПР, где под размером слоя понимается количество нейронов в нем. Поэтому задача минимизации L выделена в отдельную научно-техническую задачу.
Минимизировать L возможно, опираясь на использование различных алгоритмов инициализации и обучения, а также за счет варьирования их параметрами. Этому посвящен целый ряд работ зарубежных авторов (Lippmann R.P., Stefano A.D., Mirabella O., Wu J.L., El-Khamy S.E. и др.). В данной работе предлагается взять за основу уменьшение избыточности ОМ и проанализировать, каким образом это отразится на L и корректирующих возможностях НДПР.
В данной части задачу исследования можно сформулировать так: создать и обучить НДПР с минимально достаточным количеством нейронов, позволяющий получить результаты безошибочного декодирования в пределах кода, где - минимальное кодовое расстояние.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Для построения НД на основе модели НДПР использован метод минимизации структурного риска и соответствующая процедура синтеза НДПР (рис. 3), суть которой заключается в использовании совокупности моделей НДПР с монотонно возрастающим значением L до достижения безошибочного декодирования в пределах кода. В качестве методов оптимизации использованы известные алгоритмы обучения на примерах (Левенберга-Марквардта, обратного распространения ошибки), параметры которых устанавливались значениями по умолчанию. Требование поиска минимально достаточного количества нейронов обуславливается тем, что чем меньше нейронов содержит НДПР, тем меньше требуется вычислительных ресурсов для его реализации.
Далее в главе 2 подробно описаны теоретические положения статистического обучения, влияющие на сложность и корректирующие свойства НДПР.
Таким образом, полученные в главе 2 результаты позволили обосновать выбор моделей НД и итеративного декодера, а также получить основу для решения научной задачи в рамках первого, второго и третьего научных результатов.
В третьей главе рассмотрены вопросы совершенствования метода итеративного декодирования двоичных линейных блоковых кодов в виде итеративно-перестановочного (ИП) метода. Разрабатываются модификации РНД1 и НДПР с целью сокращения числа используемых нейронов, а также анализируется корректирующая способность предложенных модификаций.
Суть ИП метода состоит в мажоритарном принципе построения дополнительных проверочных уравнений путем линейной комбинации строк проверочной матрицы кода и группировки полученных уравнений в дополнительные фазы итерации декодирования с целью получения более надежных решений относительно информационных элементов при ограничении числа итераций. В общем случае на примере (8,4) кода Хэмминга данную схему декодирования можно представить как последовательное соединение 7 декодеров с «мягкой» схемой принятия решений на входе и выходе (SISO Декодер n) (рис. 4), использующих различные комбинации проверочных уравнений для одной фазы итерации декодирования. Они последовательно обмениваются между собой «внешней» информацией , и образуют одну полную итерацию декодирования. Результат декодирования по каждому информационному биту вычисляется в соответствии с (2).
Рис. 4. Функциональная схема ИП метода декодирования на примере (8,4) кода Хэмминга
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Результаты моделирования (рис. 5) показали, что энергетический выигрыш (ЭВ) от использования разработанного ИП метода на примере (7,4) кода Хэмминга составил [0,1 - 0,5] дБ (для 1 итерации) по отношению к методу использования только основных фаз итерации декодирования. Выигрыш заметен уже при вероятности ошибки [13].
С целью уменьшения вычислительных затрат на операцию декодирования усовершенствованы рассмотренные в главе 2 модели НД. Разработана упрощенная модель РНД1 в виде РНД2 (рис. 6а) [12]. На данную модель получено положительное решение о выдаче патента РФ на полезную модель [14].
а) |
б) |
Рис.6. Модель РНД2 блокового кода а) «жесткое» декодирование (РНД2); б) «мягкое» декодирование (РНД2м)
Идея заключается в удалении из состава РНД1 (рис. 1а) рекуррентного слоя нейронов (слоя распознавания), который вводит переменную задержку при декодировании. Для этого в качестве активационных функций (АФ) нейронов слоя образцов РНД1 доказано использование пороговых АФ единичного скачка (функций Хэвисайда) со смещениями (порогами) , которые получены автором самостоятельно. Кроме того, преобразована в биполярный вид матрица весов синаптических связей нейронов слоя образцов РНД1 , что позволило исправлять стирания в принятой КК путем их замены нулевым элементом на входе декодера.
Усовершенствована разработанная модель РНД2 (рис. 6а) в виде РНД2м (рис. 6б) с целью использования «мягких» решений в демодуляторе. Для этого в качестве нейронов слоя образцов РНД2 обоснована необходимость использования радиальных нейронов, активность которых определяется функцией Гаусса с нормальным законом распределения:
, (M=2K),
где - дисперсия, характеризующая ширину радиально-базисной функции, - значение выходного сигнала k-го нейрона слоя образцов РНД2м. Показано, что слой образцов РНД2м осуществляет выбор РКК с наибольшей плотностью распределения вероятности к входным данным. Кроме того, преобразована в биполярный вид матрица весов синаптических связей нейронов выходного слоя РНД2м , что позволило выделить нейрон слоя образцов с максимальным значением вероятности . Показано, что РНД2м и РНД2 являются декодерами максимального правдоподобия. Установлено, что РНД2 устраняет переменную задержку при декодировании, а также обеспечивает исправление стираний [6].
С целью уменьшения L РНД2 обоснована необходимость использования модели НДПР и соответствующей процедуры синтеза (рис. 3). В качестве ОМ использовалось множество отображений (3). Для минимизации размера ОМ при сохранении требуемого уровня помехоустойчивости и получения НДПР с меньшим числом нейронов использовано свойство обобщения НДПР.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
С этой целью усовершенствована методика формирования ОМ для построения НДПР блоковых кодов, работающих в режимах исправления ошибок и стираний. Суть заключается в том, что в качестве ОМ используется множество запрещенных кодовых комбинаций, отстоящих на расстоянии t (и/или p) от соответствующей РКК (рис. 7): , где t (p) - кратность исправляемых кодом ошибок (стираний), T - размер ОМ [9, 12].
Предложенные обучающие данные находятся на границах гиперплоскостей, формируемых нейронами скрытого слоя НДПР, что позволяет в среднем сократить размер ОМ на 13,5% для режима исправления ошибок и на 29,5% для режима исправления ошибок и стираний (рис. 8).
Рис. 8. Изменение размера ОМ НДПР при исправлении ошибок и стираний ?Все кодовое пространство как ОМ ? Предлагаемый набор ОМ (рис. 7)
Рис. 9. Изменение L НДПР некоторых кодов БЧХ при изменении состава ОМ
Исследовано влияние размера ОМ на изменение L (рис. 9), где под полным набором понимается множество (3) [12]. Установлено, что при использовании предложенной методики L НДПР уменьшается в среднем на 9,8%. Необходимо отметить, что существует связь между размером ОМ и L: чем меньше размер ОМ, тем меньше L. Показано, что полученные результаты согласуются с результатами статистической теории восстановления зависимостей по эмпирическим данным В.Н. Вапника и А.Я. Червоненкиса.
В научно-технической литературе введены эвристические формулы для оценки теоретических границ изменения L и необходимого числа синаптических весов в зависимости от структуры ИНС и размера ОМ (в многослойной сети с сигмоидальными функциями активации):
, , (7)
где N ? размерность входного вектора, K ? размерность выходного вектора, T ? размер ОМ. Установлено, что при непосредственном применении (7) оценка L НДПР становится сильно завышена (рис. 10 и 11).
Рис. 10. Изменение L НДПР некоторых кодов БЧХ при исправлении ошибок
Рис. 11. Изменение L НКПР некоторых кодов БЧХ
В работе экспериментально получены практические аппроксимации L НДПР (рис. 10) и НКПР (рис. 11), где НКПР - нейронный кодер прямого распространения. Анализ рис. 10 показывает, что более точная привязка ОМ к параметрам кодового пространства обеспечивает значительное снижение L НДПР.
Покажем, что корректирующая способность предложенных модификаций РНД2(2м) и НДПР не хуже РНД1 и оптимального «жесткого» (HDD) и «мягкого» (SDD) декодеров. Для этого проведем моделирование работы разработанных декодеров в канале с аддитивным белым гауссовским шумом (АБГШ) с и двоичной фазовой манипуляцией (BPSK) (рис. 12а,б,в), а также в дискретном однородном двоичном симметричном канале без памяти (ДСК) при варьировании вероятности ошибки от 0 до 0.5 (рис. 12г).
Рис.12. Оценка помехоустойчивости РНД2 и РНД2м кодов БЧХ при работе в канале АБГШ а) код (7,4); б) код (15,5); в) код (15,7); г) Оценка при изменении в ДСК.
На основе графиков, отражающих результаты моделирования (рис..12), где БМА - классический синдромный метод декодирования (алгоритм Берлекэмпа-Месси), могут быть сделаны следующие выводы: предложенные модели РНД2(2м) и НДПР не ухудшают качество СПК, при этом имеют меньшее значение L по сравнению с существующими моделями; предложенная методика формирования ОМ не ухудшает корректирующих возможностей разрабатываемых декодеров.
Таким образом, исследования, проведенные в главе 3, позволили расширить применение итеративного метода декодирования, получить усовершенствованные модели НД, а также результаты оценки их корректирующей способности, что позволило решить научную задачу в рамках первого, второго и третьего научных результатов.
В четвертой главе решались задачи оценки сложности функционирования НД блоковых кодов на основе разработанных моделей, а также сравнение полученных результатов с частными результатами других исследователей.
При оценке сложности выделено два класса: сложность функционирования (вычисления) и сложность построения (разработки).
Установлено, что построение НД значительно сложнее классических декодеров (КД), однако сложный процесс в данном случае реализуется априорно до приема кодовых слов (сложность построения). В то время как сложность КД переносится на интервал времени приема каждого кодового слова (сложность функционирования) [1, 2]. Иными словами, сложности НД и КД реализуются в разных классах (рис. 13). Обосновывается исследование сложности функционирования НД.
Рис. 13. Реализация сложности методов декодирования
Введена искусственная мера на основе функции полезности в виде комплексного показателя сложности последовательной и параллельной программной реализации алгоритмов кодирования и декодирования, позволяющая соизмерить отдельные показатели алгоритмической и программной сложности по неравномерной шкале для выявления порядка предпочтений. Такая мера определена через важность отдельных показателей в виде функции сложности метода декодирования. Для ее построения использована аддитивная свертка ее отдельных компонентов [3]:
или , (8)
где ? последовательная сложность реализации, ? сложность реализации алгоритма при наличии параллельных блоков выполнения, , - функция трудоемкости последовательной/параллельной реализации (число «элементарных» операций), ? коэффициенты важности, ? память, необходимая для реализации вычислительного процесса (число «элементарных» ячеек), ? память, необходимая для хранения промежуточных результатов.
Третий показатель “C” в выражении (8) является оценкой сложности ПО как совокупность метрик сложности ПО. Показано, что для задач СПК могут использоваться метрики Холстеда, отражающие размер ПО, или интегральная оценка сложности ПО, введенная в работах отечественных ученых, например, Бахтизиным В.В.:
,
где - рассчитанное значение i-й метрики сложности ПО, - базовое значение i-й метрики сложности ПО (в качестве может быть использовано статистическое значение i-й метрики сложности предприятия), M - количество метрик сложности ПО. Важно отметить, что функция сложности (8) характеризует относительную, а не абсолютную предпочтительность методов декодирования.
Рассмотрим случай, когда показатели оперативности (трудоемкость) и ресурсоемкости (память) алгоритма имеют наибольшую важность. В этом случае вектор коэффициентов важности примет вид . С учетом (8) в работе получены аналитические выражения для оценки сложности НД (табл. 1), где J - число слоев НД (за исключением входного), - число нейронов в i-м слое.
Таблица 1. Аналитические выражения оценки сложности нейронных декодеров
Последовательная реализация |
Параллельная реализация |
|
, |
, |
|
при , : |
||
Для рассматриваемых моделей декодеров значения J и определяются в соответствии с табл. 2.
Таблица 2. Размеры скрытых слоев нейронных декодеров
Наименование декодера |
|||
РНД1 |
РНД2 (РНД2м) |
НДПР |
|
J=3, , , |
J=2, , , |
J=2, , , - определяется экспериментально. |
Установлено, что трудоемкость НД в “лучшем”, “худшем” и “среднем” случаях совпадает, поэтому сложность может быть рассчитана аналитически (рис. 14) в соответствии с табл. 1 без проведения имитационного моделирования.
Рис. 14. Оценка сложности функционирования моделей НД некоторых кодов БЧХ а) РНД1 и РНД2(2м); б) НДПР
На основе графиков, отражающих изменение сложности НД для рассматриваемых кодов БЧХ и кодов длины до 127 (рис. 14), а также табл. 3 сделаны следующие выводы:
сложность РНД2(2м) меньше сложности РНД1 в среднем в раз в связи с отсутствием рекуррентного слоя нейронов;
сложность НДПР меньше сложности РНД1 в среднем на 67,6%;
использование предложенной методики формирования ОМ сокращает сложность НДПР в среднем на 9,7%.
В результате проведенных исследований, удалось получить оптимальные (в смысле минимального необходимого количества нейронов) характеристики НДПР для некоторых кодов БЧХ (табл. 3), позволяющие обеспечить результаты декодирования, аналогичные декодеру максимального правдоподобия [12].
Таблица 3. Разработанные типы и структуры НД для некоторых кодов БЧХ
№ п/п |
Код |
Тип нейронного декодера |
Структура нейронного декодера для различных режимов работы |
Порядок роста сложности |
||
Исправление ошибок |
Исправление ошибок и стираний |
|||||
1 |
(7,4) |
РНД1 |
7?16?16?4 |
|||
2 |
РНД2 (РНД2м) |
7?16?4 |
||||
3 |
НДПР |
7?7?4 |
7?9?4 |
|||
4 |
(15,5) |
РНД1 |
15?32?32?5 |
|||
5 |
РНД2 (РНД2м) |
15?32?5 |
||||
6 |
НДПР |
15?38?5 |
15?58?5 |
|||
7 |
(15,7) |
РНД1 |
15?127?127?7 |
|||
8 |
РНД2 (РНД2м) |
15?127?7 |
||||
9 |
НДПР |
15?34?7 |
15?39?7 |
Рассчитанные матрицы свободных параметров представлены в Приложении 2 диссертации.
Для проверки адекватности полученных аналитических выражений, задача декодирования с использованием разработанных НД сведена к задаче умножения вектора на матрицу, для которой в теории сложности вычислений установлены границы роста сложности, величины ускорения и эффективности при параллельной реализации. Показано, что полученные результаты оценки порядка роста сложности разработанных НД (табл. 3) полностью согласуются с теоретическими.
Рис. 15. Сложность реализации НД блоковых кодов в режиме исправления ошибок
Таблица 4. Различные НД при исправлении ошибок
№ п/п |
Исследователь |
Наименование |
Структура |
Обучение |
|
1 |
Zeng G., Hush D., Ahmed N. |
РНД1 |
N - 2K -2K - K |
Нет |
|
2 |
Htay M.M., Iyengar S.S. |
СНД |
N - [N-K] - N -2N - N |
Нет |
|
3 |
Ahmed S. |
||||
4 |
Stefano A.D, Mirabella O., Cataldo G.D. |
BPN |
N -log2(2T) - 2K-K |
Да |
|
5 |
Предлагаемые НД |
РНД2 |
N - 2K- K |
Нет |
|
РНД2м |
N - 2K- K |
||||
НДПР |
N - L - K |
Да |
Эффективность РНД2(2м) и НДПР сравнена с частными результатами других исследователей (табл. 4) (РНД1, СНД, BPN) с точки зрения сложности функционирования. Анализ графиков (рис. 15), полученных в результате использования разработанных аналитических выражений (табл. 1), показывает, что полученные результаты согласуются с известными данными и в случае рассматриваемых кодов сложность предлагаемых в работе НД меньше сложности известных НД в среднем на 56,4% при всех равных условиях.
Таким образом, проведенные в главе 4 исследования сложности функционирования разработанных НД позволили показать их эффективность, а также применимость разработанных аналитических выражений оценки сложности и решить научную задачу в рамках четвертого научного результата.
В заключении сформулированы основные научные и практические результаты работы, полученные автором.
Основные результаты работы
1. Разработан итеративно-перестановочный метод декодирования двоичных линейных блоковых кодов, обеспечивающий увеличение надежности приема информационных элементов путем мажоритарного построения дополнительных проверочных уравнений. Моделированием оценен энергетический выигрыш от его использования на примере (7,4) кода Хэмминга. Он составляет [0,1 - 0,5] дБ (для 1 итерации) по отношению к методу использования только основных фаз итерации декодирования. Выигрыш заметен уже при вероятности ошибки .
2. Разработана структура и определены параметры модели нейронного кодера и декодера на основе нейронного классификатора Хэмминга для использования «жестких» и «мягких» решений в демодуляторе, а также исправления стираний. Более точная настройка параметров модели на характеристики кода позволила исключить из состава классификатора Хэмминга второй скрытый слой распознавания. Это позволило сократить в среднем в 2 раза общее число нейронов и уменьшить в среднем в раз сложность функционирования, а также устранить переменную задержку при декодировании.
3. Предложена методика формирования обучающего множества для построения обучаемого нейронного декодера блоковых кодов, работающего в режимах исправления ошибок и стираний. Использование предложенной методики позволило повысить обоснованность выбора обучающего множества путем его привязки к структуре кодового пространства и уменьшить сложность функционирования обучаемых нейронных декодеров в среднем на 9,7% при сокращении избыточности обучающего множества на 21,5%.
4. Предложена методика оценки сложности функционирования последовательной и параллельной программной реализации алгоритмов кодирования и декодирования на основе комплексного показателя, учитывающая алгоритмическую и программную сложность реализации. Ее использование позволяет осуществить рациональный выбор реализации предложенных методов с учетом алгоритмической и программной составляющих.
5. Теоретическим результатом являются полученные аналитические выражения для оценки сложности функционирования нейронных декодеров блоковых кодов, которые напрямую зависят от параметров используемых кодов. Данные выражения позволяют до этапа эксплуатации оценить пригодность конкретных реализаций нейронных декодеров при заданных ограничениях на сложность функционирования.
6. Исследован порядок роста сложности, проведена оценка помехоустойчивости и сравнение полученных результатов с частными результатами других исследователей. Это дает основание утверждать, что полученные результаты согласуются с известными данными и в случае рассматриваемых кодов сложность предложенных в работе модификаций нейронных декодеров меньше сложности известных нейронных декодеров в среднем на 56,4% при всех равных условиях.
Список публикаций по теме диссертации
1. Берёзкин А.А. Оценка сложности реализации современных методов декодирования помехоустойчивых кодов // Труды учебных заведений связи / СПбГУТ. СПб, 2005. № 172. С.89 - 96. (Из перечня изданий, рекомендованного ВАК).
2. Берёзкин А.А., Охорзин В.М. Оценка сложности реализации декодирования кодов Рида-Соломона при исправлении стираний // 57-я НТК: материалы / СПбГУТ. СПб, 2005. С. 6.
3. Берёзкин А.А. Критерии оценки сложности программной реализации методов кодирования и декодирования // 59-я СНТК / СПбГУТ. СПб, 2005. С. 21.
4. Берёзкин А.А., Охорзин В.М. Оценка сложности реализации итеративных методов декодирования // Труды учебных заведений связи / СПбГУТ. СПб, 2006. № 174. С.39 - 44.
5. Берёзкин А.А. Альтернативное декодирование помехоустойчивых кодов с использованием нейронных сетей // Труды учебных заведений связи / СПбГУТ. СПб, 2006. № 175. С.8 - 15.
6. Берёзкин А.А. Рекуррентный нейронный декодер двоичных блоковых кодов и его модификации // Труды учебных заведений связи / СПбГУТ. СПб, 2007. № 176. С.135 - 146.
7. Берёзкин А.А. Нейросетевой подход к вопросам кодирования/декодирования помехоустойчивых кодов // 59-я НТК: материалы / СПбГУТ. СПб, 2007. С. 29.
8. Берёзкин А.А. Оптимальный нейронный кодер/декодер прямого распространения: характеристики и применение // 61-я СНТК / СПбГУТ. СПб, 2007. С. 20.
9. Берёзкин А.А. Выбор обучающего множества для построения нейронных декодеров помехоустойчивых кодов // 60-я НТК: материалы / СПбГУТ. СПб, 2008. С. 25.
10. Берёзкин А.А., Комашинский В.И. Введение в нейро-цифровые инфоком-муникационные технологии // XI Санкт-Петербургская международная конференция «Региональная информатика-2008» (РИ-2008): материалы / СПОАСУ. СПб, 2008. С. 76.
11. Берёзкин А.А. Перспективы развития современных методов помехоустойчивого кодирования в нейро-цифровом логическом базисе // Международная НПК «Перспективы развития телекоммуникационных систем и информационные технологии»: труды конференции / СПБГПУ. СПб, 2008. С. 10 - 16.
12. Берёзкин А.А. Построение оптимальных нейронных декодеров блоковых кодов // Научно-технические ведомости СПбГПУ / СПбПГУ. СПб, 2008. № 5. С.34 - 41. (Из перечня изданий, рекомендованного ВАК).
13. Берёзкин А.А. Итеративно-перестановочный метод декодирования двоичных линейных блоковых кодов // Научно-технические ведомости СПбГПУ / СПбПГУ. СПб, 2009. № 2. С.193 - 199. (Из перечня изданий, рекомендованного ВАК).
14. Берёзкин А.А. Нейронный декодер двоичных блочных кодов с исправлением ошибок и стираний, патент РФ на полезную модель по заявке №2009108326/22, решение о выдаче патента от 25.03.2009г.
Подписано к печати 29.05.2009.
Объем 1 печ. л. Тираж 80 экз. Зак. 19
Тип. СПбГУТ, 191186 СПб, наб. р. Мойки,61
Размещено на Allbest.ru
...Подобные документы
Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.
курсовая работа [212,6 K], добавлен 25.02.2009Разработка алгоритма и программы кодирования и декодирования данных кодом Рида-Малера. Понятие избыточных кодов, их применение. Корелляционный код. Особенности построения простых помехоустойчивых кодов Рида-Маллера. Рассмотрение частных случаев.
курсовая работа [31,9 K], добавлен 09.03.2009Разработка утилиты кодирования и декодирования формата Base 64 в программной среде Linux с использованием компилятора. Написание программы на языке С++. Кодирование символьной строки любого набора байт в последовательность печатных ASCII символов.
курсовая работа [1,4 M], добавлен 10.09.2013Принципы защиты от ошибок информации при ее передаче по каналам связи. Блоковые коды и методы их декодирования. Построение линейных блочных аддитивных алгебраических кодов и принципы их декодирования синдромным методом. Основные возможности SciLab.
курсовая работа [394,4 K], добавлен 17.05.2012Анализ методов сверточного кодирования. Понятие канала связи и корректирующих кодов, характеристика автомата типа Мура. Особенности сверточного декодирования Витерби. Сущность разработки программного обеспечения системы кодирования сверточным кодом.
дипломная работа [4,9 M], добавлен 11.03.2012Циклические коды как подкласс (подмножество) линейных кодов, пошаговый алгоритм и варианты их кодирования и декодирования. Методика построения интерфейса отладочного модуля. Элементарный план и элементы отладки декодирующего модуля циклических кодов.
лабораторная работа [133,8 K], добавлен 06.07.2009Разработка программы для осуществления работы с файлами и их последующего помехоустойчивого кодирования-декодирования по методу Хемминга 15-11 в интерактивном режиме. Обзор языка С и его особенностей. Взаимодействие пользователя с программным интерфейсом.
курсовая работа [145,5 K], добавлен 12.05.2013Сущность метода перестановочного декодирования. Особенности использования метода вылавливания ошибок. Декодирование циклического кода путем вылавливания ошибок. Распознавание пакетов ошибок как особенность циклических кодов. Вычисление вектора ошибок.
доклад [20,3 K], добавлен 24.05.2012Коды Боуза-Чоудхури-Хоквингема (БЧХ) – класс циклических кодов, исправляющих многократные ошибки. Отличие методики построения кодов БЧХ от обычных циклических. Конкретные примеры процедуры кодирования, декодирования, обнаружения и исправления ошибок.
реферат [158,2 K], добавлен 16.07.2009Разработка программы кодирования текстового файла при помощи блочного алгоритма шифрования ТЕА типа "Сеть Фейштеля", который основан на битовых операциях с 64-битным блоком и имеет 128-битный ключ шифрования. Результаты кодирования и декодирования.
лабораторная работа [299,9 K], добавлен 18.07.2013Понятие и отличительные черты аналоговой и цифровой информации. Изучение единиц измерения цифровой информации: бит (двоичная цифра) и байт. Особенности передачи, методы кодирования и декодирования текстовой, звуковой и графической цифровой информации.
реферат [479,4 K], добавлен 22.03.2010Анализ способов кодирования информации. Разработка устройства кодирования (кодера) информации методом Хемминга. Реализация кодера–декодера на базе ИМС К555ВЖ1. Разработка стенда контроля передаваемой информации, принципиальная схема устройства.
дипломная работа [602,9 K], добавлен 30.08.2010Создание циклического кода по задающему полиному методом порождающей матрицы, анализ полученных комбинаций. Кодограммы для оптического и магнитного внешнего запоминающего устройства. Построение принципиальной схемы кодирования и декодирования информации.
контрольная работа [263,8 K], добавлен 11.12.2014Двоичный код, особенности кодирования и декодирования информации. Система счисления как совокупность правил записи чисел с помощью определенного набора символов. Классификация систем счисления, специфика перевода чисел в позиционной системе счисления.
презентация [16,3 K], добавлен 07.06.2011Разработка программной базы для исследований в области распознавания речи и поиска ключевых слов в ней. Расчет mel-фильтров. Скрытые марковские модели. Применение в алгоритме сверточного декодирования Витерби. Методы визуализации и обработки аудиоданных.
курсовая работа [1,1 M], добавлен 01.06.2015Изучение сущности циклических кодов - семейства помехоустойчивых кодов, включающих в себя одну из разновидностей кодов Хэмминга. Основные понятия и определения. Методы построения порождающей матрицы циклического кода. Понятие открытой системы. Модель OSI.
контрольная работа [99,5 K], добавлен 25.01.2011Разработка приложения, представляющего собой графический многопользовательский чат с передачей данных в закодированном виде. Алгоритмы обработки данных. Графические диалоговые системы. Тестирование и анализ результатов. Алгоритм декодирования сообщений.
курсовая работа [830,1 K], добавлен 12.03.2014Методика и алгоритм статистических испытаний. Исследование сверточного кода порогового, мажоритарного декодеров, Витерби и Меггита. Исследование достоверности принятой информации на приемной стороне с УЗО и без него. Варианты корректирующих кодов.
курсовая работа [680,3 K], добавлен 23.01.2015Функционально микропроцессор делят на операционную и интерфейсную части. В состав микропроцессора Pentium входят: ядро МП, исполняющий модуль, регистры, блок для работы с числами, кэш первого уровня, блоки декодирования инструкций и интерфейсные шины.
лекция [1,5 M], добавлен 05.02.2009Функциональная схема и алгоритм работы устройства. Техническое обоснование выбора серии ИМС. Состав и описание работы узлов устройства. Расчёт необходимых сопротивлений резисторов, потребляемой мощности и тока. Построение и анализ временных диаграмм.
курсовая работа [311,7 K], добавлен 19.05.2011