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

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

Гладких Анатолий Афанасьевич

МЕТОДЫ ЛЕКСИКОГРАФИЧЕСКОГО ДЕКОДИРОВАНИЯ ИЗБЫТОЧНЫХ КОДОВ НА БАЗЕ МОДИФИКАЦИЙ СТИРАЮЩЕГО

КАНАЛА СВЯЗИ

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

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

21 ОКТ 2015

Ульяновск 2015

005563619

005563619

Работа выполнена на кафедре «Телекоммуникации» Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Ульяновский государственный технический университет»

Научный консультант: Васильев Константин Константинович,

доктор технических наук, профессор, заслуженный деятель науки и техники РФ

Официальные оппоненты: Овечкин Геннадий Владимирович, доктор

технических наук, доцент, профессор кафедры «Прикладной математики» Рязанского государственного радиотехнического университета

Савшценко Николай Васильевич, доктор технических наук, профессор, заместитель начальника кафедры № 2 Военной академии связи, Санкт-Петербург

Кумунжиев Константин Васильевич, доктор технических наук, профессор, профессор кафедры «Информационные технологии» Ульяновского государственного университета

Ведущая организация: ЗАО «Институт телекоммуникаций», 194100, Санкт-Петербург, ул. Кантемировская, д. 5.

Защита состоится 18 декабря 2015 года в 14.00 на заседании диссертационного совета Д219.003.02 при Федеральном государственном образовательном бюджетном учреждении высшего профессионального образования «Поволжский государственный университет телекоммуникаций и информатики» (ФГОБУ ВПО ПГУТИ) по адресу: 443010, г. Самара, ул. Льва Толстого, д. 23, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ФГОБУ ВПО ПГУТИ и на сайте www.psuti.ru/science/diss-ob. Автореферат разослан « 2015 г.

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

Ученый секретарь

диссертационного совета Д219.003.02, / ^/

доктор технических наук, профессор сС ** / Тяжев Л.И.

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

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

В процессе своей работы автор опирался на труды В.А. Котельникова, Л.М. Финка, Э.Л. Блоха, В.В. Зяблова, К.Ш. Зигангирова, Л.Ф. Бородина, В.П. Шувалова, В.М. Охорзина, Ю.Б. Зубарева, Ю.С. Шинакова, К.К. Васильева,

B.В. Золотарева, Г.В. Овечкина, Д.Д. Кловского, A.M. Чуднова, В.Г. Карташевского, Д.В. Мишина, Б.И. Николаева и др.

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

C.Е. Shannon, R.M. Fano, Р. Elias, J.M. Wozencraft, I.M. Jacjbs, E. Arikan, L.R. Bahl, C. Berrou, A. Glavieux, R. Gallager, G. Clark, G.D. Forny, R.W. Hamming, W.W. Peterson, R.T. Chien, E.R. Berlekamp, J.L. Massey, I.S. Reed, G. Solomon, R.C. Bose, J.F. MacWilliams, J.E. Meggitt, M. Sudan, S.B. Korada, I. Tal, A. Vardy, R. Morelos-Zaragoza, B. Sklar, J.G. Proakis и.др.

Актуальность темы исследования. Интенсивное развитие современных средств инфокоммуникационных технологий открывает новые возможности совершенствования существующих и создания перспективных подходов в реализации многофункциональных информационно-управляющих комплексов (ИУК). Особенно востребованным становится эффективное управление разнородным!! мобильными объектами, предназначенными для решения одной или нескольких задач, объединяемых единой целевой функцией. Наряду с передачей больших объемов данных, возрастающие требования к оперативности управления современных и перспективных ИУК диктуют необходимость применения в них коротких циклов управления, например, при реализации гиперзвукозых технологий. Использование радиоинтерфейса в таких комплексах требует учитывать достоверность обрабатываемых в них данных, и степень приспособленности ИУК к работе в условиях интенсивных помех в пределах заданных временных интервалов. В совокупности динамика перемещения элементов ИУК при жестком соблюдении требований по длительности цикла управления выводит такие комплексы в разряд систем реального времени, что накладывает существенные ограничения на параметры используемых в них избыточных кодов. В подобных системах целесообразно использовать короткие помехоустойчивые коды, которые с учетом специфики ИУК оказываются более универсальными относительно их длинных аналогов. Такие коды способны обеспечить оперативное переключение режимов работы ИУК, гибкую параметрическую адаптацию кодеков в условиях смены параметров используемых каналов связи. В случае возникновения потребности обмена мультимедийными данными больших объемов короткие коды могут быть трансформированы в каскадные конструкции или в произведение кодов размерности 3D и выше за счет структурной адаптации.

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

Идейный стержень развития цифровых систем связи заложен в основополагающих работах В.А. Котельникова, К.Е. Шеннона, P.M. Фано и П. Элайеса. В рамках данной работы особое значение приобретает фундаментальная теорема Л.М. Финка о декодировании в целом. Значительный вклад в разработку теории повышения спектральной и энергетической эффективности систем обмена данными внесли Д.Г. Форни, Р. Дж. Галлагер, Г. Унгербоек, А.Д. Витерби, В.И. Коржик, Э.Л. Блох, В.В. Зяблов, К.Ш. Зигангиров, в работах которых раскрываются теоретические основы дискретного стирающего канала связи применительно к различным классам избыточных кодов. Основное внимание в работах Дж. Возенкрафта и Л.Ф. Бородина уделяется оптимизации ширины зоны неопределенности в смысле минимизации ошибочного декодирования кодового вектора. Поэтому задача декодирования в целом не носит комплексного характера, а решается опосредованно.

Учитывая важность модели стирающего канала связи, подробное исследование принципа формирования стираний в полунепрерывном канале связи выполнил В.П. Шувалов, который раскрыл отрицательную роль ложных стираний. Вероятность таких решений при симметричном интервале стирания объективно превосходит вероятность правильных стираний, что отрицательно сказывается на процедуре исправления неопределенных решений избыточным кодом. В целях минимизации доли ложных стираний В.П. Шуваловым предлагалось анализировать не одну характеристик}/ непрерывного канала связи, а комплекс характеристик, что неоправданно повышает сложность вычислительного процесса. С развитием элементной базы важным шагом в решении задачи декодирования в целом явилось вещественное представление мягких решений символов (MPC) в формате логарифма отношения функций правдоподобия. По асимптотическим оценкам мягкое декодирование избыточных кодов способно обеспечить до 3 дБ энергетического выигрыша кода (ЭВК), однако при этом необходимо располагать сведениями о статистических характеристиках канала связи, что не всегда выполнимо при реализации ИУК.

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

декодирования, развитых в трудах Ю.Б. Зубарева, В.В. Золотарева и Г.В. Овечкина, а исследованиям мягкой обработки данных в каналах с памятью посвящены работы Д.Д. Кловского, В.Г. Карташевского, Д.В. Мишина, Б.И. Николаева. Как правило, указанные подходы реализуются на базе кодов значительной длины с большим числом итераций.

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

С целью повышения эффективности обмена данными в ИУК должны быть минимизированы временные затраты на получение статистических характеристик используемых каналов связи. Поэтому формирование MPC целесообразно осуществлять на базе модификаций стирающего канала, позволяющего исключить подобные действия. Для достижения требуемого ЭВК целесообразно использовать мягкие неалгебраические алгоритмы декодирования двоичных и недвоичных кодов совместно с итеративными преобразованиями, относящимися не к каждому символу кодовых векторов, а только к той части, от которой в наибольшей степени зависит правильное восстановление данных. Учитывая условия преимущественной эволюции пакетных технологий к сетям нового поколения с выраженными свойствами мультисервисности, одной из актуальных задач становится унификация средств помехоустойчивого кодирования и управления масштабируемой избыточностью в них на основе произведения двоичных кодов размерностью 2D, 3D и выше.

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

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

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

Поставленная цель обусловила основные задачи исследования:

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

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

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

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

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

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

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

7. Разработка методов масштабируемой избыточности для защиты мультимедийного трафика с использованием произведений кодов заданной размерности.

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

Методы исследования

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

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

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

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

Научная новизна

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

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

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

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

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

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

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

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

Научно-практическая значимость

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

Реализация результатов работы

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

1. ФНПЦ АО «НПО «Марс» (г. Ульяновск) - при выполнении ОКР «Каскад 1» (2010-2011 гг.) и НИР «Каскад 2» (2012-2013 гг.).

2. ЗАО «Интелтех» (г. Санкт-Петербург) — при выполнении ОКР «Булат-Интелтех» 2015 г.

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

Апробация работы и публикации

Основные положения и результаты работы докладывались на следующих конференциях: научная сессия РНТО РЭС им. Попова, посвященная Дню Радио, г. Москва (2009, 2010, 2011, 2012, 2013, 2015); Международная конференция «Цифровая обработка сигналов и ее применение» - DSPA, г. Москва (2012, 2013, 2015); Международная научно-техническая конференция «Радиолокация, навигация, связь» - RLNC, г. Воронеж (2013, 2014, 2015; X Международная научно-техническая конференция «Физика и технические приложения волновых процессов», г. Самара, 2009; Всероссийская научно-практическая конференция «Современные проблемы создания и эксплуатации радиотехнических систем», г. Ульяновск (1998, 2001, 2011, 2013, 2015) VII Международная конференция «Математическое моделирование физических, экономических, технических, социальных систем и процессов» г. Ульяновск, 2009; Научно-техническая конференция «Интегрированные автоматизированные системы управления», г. Ульяновск, ФНПЦ АО «НПО «Марс», 2011; XV Международная научно-техническая конференция «Проблемы техники и технологий телекоммуникаций» и XII Международной научно-технической конференции «Оптические технологии в телекоммуникациях», г. Казань, 2014.

Результаты работы опубликованы в 73 печатных трудах, в числе которых одна монография, 21 статья в журналах, входящих в перечень ВАК, 40 трудов и тезисов докладов на Международных и Всероссийских научно-технических

и научно-практических конференциях, 12 патентов Российской Федерации на изобретения.

Вклад автора в разработку проблемы. Выносимые на защиту положения предложены соискателем в ходе выполнения ОКР и НИР, выполняемых кафедрой «Телекоммуникации» Ульяновского государственного технического университета совместно с различными предприятиями, связанных с разработкой аппаратуры передачи данных в период с 2010 по 2015 год. Во всех работах и в том числе совместных работах по теме диссертации автору лично принадлежат постановка задачи и основной вклад в разработку концепций математических моделей и методов их реализации. Результаты данной диссертационной работы соответствуют пунктам 8, 11 и 13 паспорта специальности 05.12.13.

Структура, объем и содержание работы

Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложений. Основная часть работы содержит 315 страниц машинописного текста, 98 рисунков, 42 таблицы и 3 приложения. В список литературы вынесены 242 наименования.

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

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

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

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

4. Новые сравнительные данные по сложности реализации алгебраического декодера кода Рида-Соломона (РС) с использованием алгоритмов Берлекэмпа-Месси (АБМ) совместно с процедурой Ченя и алгоритмом фильтрации ошибок на основе МРС символов, позволяющего от 30% и более, в зависимости от введенной в код избыточности, повысить производительность декодера кода РС, что важно для высокоскоростных систем обмена данными.

5. Алгоритмы построения произведений кодов размерности ЗЭ и более с единственной проверкой четности. Определены их потенциальные

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

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

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

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

Первая глава. Рассматриваются вопросы синтеза математических моделей, используемых в телекоммуникационных системах (ТКС) из состава ИУК. Анализируются возможности известных методов формирования мягких решений на базе стирающего канала связи. Уменьшение длин кодовых последовательностей при заданных требованиях по достоверности данных, циркулирующих в ИУК, приводит к необходимости гибкого синтеза сведений о сигналах, получаемых из непрерывного канала связи, и мягких эффективных алгоритмов обработки избыточных кодов, используемых в системе связи ИУК. Поэтому телекоммуникационные технологии играют решающую роль в способах организации и структуре построения существующих и проектируемых мобильных ИУК или специализированных систем управления (СУ), призванных осуществлять сбор заданного набора сведений об управляемых объектах и, в соответствии с целевой функцией F{V,U,Т,Р}, выполнять управление этими объектами. В СУ множество объектов V считается априори заданным, в то время как множество условий функционирования U может изменяться и оказывать стохастическое влияние на достижение /•'{•} в актуальные интервалы времени Г и с заданной достоверностью Р информации, циркулирующей в СУ. Как правило, границы существования параметра Т СУ определяются длительностью цикла управления Tlfy. Выполнение цикла является показателем эффективности

достижения F{*}. В условиях действия интенсивных мешающих факторов снижение параметра Tlfv может быть достигнуто только за счет применения

интегрированных СУ и ИУК на основе материального носителя в виде системы связи, способной передавать не только короткие сигналы управления, но и большие объемы мультимедийных данных.

Наличие прямого и обратного канала связи в классической СУ требует выполнения обязательного условия кт (ТпК + Ток ) « 'Г, где k(J1 > 0 -

коэффициент, определяющий общую задержку данных при их обработке в кодеке. В простейшем случае коэ означает число повторов данных при использовании алгоритмических методов повышения достоверности, при этом ТПК и Ток представляют время нахождения управляющей информации в прямом и обратном канале связи соответственно. Время А = Тцу — Тсс, где Тсс =к03(Тпк +Ток), в СУ тратится на обработку данных и принятие решения как в управляемом, так и в управляющем объекте, при этом часто А»0. Учитывая неравенство Tcc«Tlfy, в /<'{•} при заданных V и U актуальным становится параметр Р, поскольку в ИУК к обработке могут быть приняты только достоверные данные.

Показатели эффективности (ПЭ) допустимых условий из U (возможно определенных только в виде граничных значений) и выбранных или жестко заданных элементов из V для реализации F{«} оцениваются набором вещественных чисел {R,R el). Процедура подбора или поиска V для выявленных условий U и достижения /•'{•} и их допустимые вариативные изменения F:V X U Hi в процессе обоснования структуры и характеристик реальных объектов отражают особенности концептуального и семантического моделирования синтезируемых систем, позволяющих сформулировать постановку математических задач и организовать их решение в виде формальных моделей.

В случае конкретизации условий {иа,и],...,ип,...} = и0, где Uq е U, процесс функционирования синтезируемой системы принимает классический характер оптимизации (в общем случае многокритериальный) в смысле достижения тех или иных экстремальных показателей Гэкст Е Е и (или)

P3Krr е к.

F{V,иЛ^тах. (1)

VeV

В качестве решений задачи (1) рассматривается множество V£(V,U0) так называемых е - оптимальных систем VE (е > 0), определяемое выражением

Ve е VZ(V,UQ,T,P)<* F{V,U,T,P}<F{VZ,UQ,T,P}+ е (2)

для любых VeV. Таким образом, для выбранных V и конкретизированных условий U0 показатели функционирования е-оптимальной системы не могут быть улучшены, и, если £>0, сохраняется целесообразность поиска вариантов снижения вычислительных затрат. При е = 0, оптимальные элементы системы отсутствуют VQ(V,U0,T,P)={ }, но f{Pe,u}> sup f{v,U0,T,p}-e при VeV.

VeV

С точки зрения общего подхода к синтезу телекоммуникационной системы (ТКС), множество условий функционирования системы U целесообразно рассматривать как совокупность двух подмножеств: Uоп е U, в котором условия функционирования системы априори определены, и подмножества UHO е U, для которого условия его реализации до реального применения системы остаются неизвестными. Условия из состава множества U,.n с высокой

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

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

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

Dkm=mg{k{\-R + \/rij)p5. (3)

Предполагается, что d = п — к +1. Здесь d — метрика Хемминга, п — общая длина кодовой комбинации, к — число информационных разрядов, при этом R = к/п. Это условие справедливо не для всех кодов. Известно, что недвоичные коды (например, коды PC) достигают значения Dкт, что нельзя сказать о двоичных кодах, которые в большинстве своем не являются максимально декодируемыми кодами. В случае к = п Dkm = 0 и Dkm —» тах при R ~ 0,5. Из (3) вытекает, что для двоичных линейных кодов существует возможность получения дополнительного энергетического выигрыша относительно мягких методов декодирования на уровне от 2 до 3 дБ, который может быть получен только за счет преобразований таких кодов с использованием концепции эквивалентных кодов. Совершенствование декодеров недвоичных кодов PC целесообразно осуществлять только за счет снижения сложности их реализации.

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

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

Вторая глава. Посвящается разработке математических моделей формирования оценок MPC в системе декодирования избыточных кодов. Осуществляется анализ наиболее важных методов формирования MPC. К ним относятся: метод квантования принятого сигнала на 2 уровней (метод Витерби); метод скользящих окон, сканирующих кортеж стираний; метод логарифма отношения правдоподобия (LLR).

Указанные методы обладают рядом недостатков, которые снижают эффективность применения мягких декодеров в современных системах обмена данными. К ним следует отнести: необходимость решения системы линейных неравенств, зависимость вырабатываемых оценок от вероятности появления ложных стираний, зависимость точности определения MPC от знания статистических характеристик, используемого канала связи. Именно эти обстоятельства тормозят широкое внедрение мягких методов декодирования избыточных кодов в ТКС и предметных областях, связанных с обработкой данных. Для объективной оценки методов вводится понятие коэффициента правдоподобия

где р'пр — вероятность появления MPC со значением X, совпавших с правильно

принятыми символами, а РдШ - вероятность появления таких же оценок с ошибочными символами.

Представлена методика улучшения показателя Ц'1р за счет введения

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

математического ожидания сигнала ^¡Еь , где Еь - энергия сигнала на бит. Этим достигается повышение значений параметра Р. Всем сигналам, принятым за пределами этой зоны, присваивается максимальная градация надежности Хтах, а внутри зоны неопределенности вводится функция f(z), в соответствии с которой определяются значения MPC. При этом

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

условиях символы с номерами Х^ < лтах, где (с, = 0,2'' -1) и (/? Е М) указывают

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

Если задан интервал стирания 0 < р < 1, то порог зоны неопределенности определяется выражением | • При этом все сигналы |z(/)| >

оцениваются как MPC с номером ^.тах =2^ -1. Другие MPC формируются по правилу:

Il /Ш -»• {%} € ж.

Пусть /(z) - линейная функция и решение 8 -оптимальной задачи требует получения целочисленных X,. Тогда интервал от 0 до |рj разбивается на (Хтах-1) уровней. Границей нулевого уровня от порога решающей схемы является число ЬН = кРл/^)/(^тах ~~ 1)_1- Вероятность появления MPC

А,- =

определяется выражением

vK+l)

¥(4+1)

рч= \p{z\i = \)dz+ jp(z | i = 0)ck, где ^ = 0,(2р-1).

(6)

Геометрическая интерпретация правила формирования целочисленных MPC с заданным диапазоном оценок для различных видов двоичной модуляции представлена на рисунке 1, на котором аргумент z - суть модулируемого параметра. Правило формирования MPC для внутренней части интервала {Яг} € Ж принимает вид

Р JËb

(7)

для условия целочисленных значений MPC и в расчете на наихудший случай (7) приводится к виду [_• J, при этом погрешность оценок MPC возрастает.

Рисунок 1 - Рабочая характеристика приемника с А.тах = 7 : а - с открытой правой границей зоны неопределенности (сигналы АМ), г - амплитуда сигнала; б - с закрытой границей (ФМ), где г - фаза сигнала

Преимуществом нового подхода в случае открытого интервала является значительный отрыв оценки А.тах =7 от других оценок, как показано на

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

Рисунок 2 - Сравнительные характеристики для значений (h) исследуемых методов

Сравнение (7) с набором характеристик, получаемых с использованием LLR, говорит о необходимости постоянного измерения параметра С (дисперсия гауссовского шума) на выходе канала связи при реализации LLR, что требует дополнительных вычислительных затрат. Вычисление коэффициента корреляции для оценок MPC, определенных с использованием метода LLR, и оценок, полученных по предложенному методу при А,гаах = 7,

2

путем сравнения гистограмм по критерию %

К 2(HLLR,Hs)=Y(HLLR(i)~Hsin)2. (8)

7 HLLR(ï)+Hs(i)

где HLLR— значение LLR в заданных интервалах, a Hs — значение оценок в тех же интервалах, определенных с использованием правила (7), показало, что отсутствие информации! о параметре с2 наиболее негативно сказывается в области высоких отношений сигнал-шум.

Правило (7) вычисления MPC распространяется не только на системы связи с двоичными методами модуляции, но и на системы с сигнальными созвездиями. На рисунке 3 показана система возможных альтернативных решений вычисления MPC с использованием концентрических границ с центрами в номинальных точках сигналов, например, QPSK. Для рационального вычисления индексов Х,тах целесообразно использовать еще одну границу, которую назначают в виде дробно-рациональной функции вида у = {ах + Ь)/(сх+Ъ) при с ^ 0 (см. первый квадрант схемы). Учет этой границы соответствует концепции открытого интервала и увеличивает число оценок

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

декодере.

Im(z)

- Re(z)

Рисунок 3 - Альтернативные принципы разбиения пространства сигналов QPSK на зоны для получения MPC

Рисунок 4 - Принцип определения минимума евклидовой метрики в сигнальном созвездии С>АМ-16

Задача заключается в том. чтобы вычислить евклидову метрику от принятой приемником точки z до ближайших точек созвездия. Аналогичная задача решается в системе сферического декодирования сигналов. Если выполняется условие а < (3 < у < Ç , то за метрику выбирается значение а. В случае появления равенства в любом сочетании указанных векторов сигналу целесообразно присвоить низшую оценку из диапазона возможных значений. Алгоритм вычисления MPC сохраняется для любых значений сигналов категории QPSK или QAM, что в совокупности с прг'.вилом (7) подчеркивает универсальность предложенного правила формирования MPC. С ростом индексов QAM эффективность правила снижается. Делаются выводы по главе.

Третья глава. Представляются суть и доказательства положений лексикографического разбиения пространства разрешенных кодовых комбинаций на кластеры. Показывается, что все классы линейных кодов могут быть представлены через подмножество кластеров. Источник информации, работая в поле элементов из GF(2k ), где к G И --- число разрядов в комбинации безызбыточного кода, после прохождения канального кодера, содержащего порождающую матрицу Gk:xn, формирует на его выходе последовательности длины п > к. Этой операцией групповой код Сп к над полем элементов из

G F (2" ) считается заданным. Исходя из свойств вложенности двоичных полей степени расширения п и менее, комбинации любого кода Сп к разбиваются на кластеры с уникальными номерами фл. и, следовательно, упорядочены лексикографически, где 1 < ф < к - число двоичных разрядов, определяющих номер кластера, a s — принятая система счисления. Тогда

C^KcoUq},-,^}}, (9)

где {с,} - множество комбинаций из Сп к, принадлежащих кластеру с номером

фЛ. = (, где / = 0.29 -1. В новых условиях все комбинации кода содержат три непересекающихся между собой по символам кодового вектора части: <ф) -сочетание любых произвольно выбранных разрядов кодовой комбинации, обозначающих номер ф,. кластера; (к - ф) - любые разряды кодового вектора, представляющие индикатор эквивалентности кода; (п-к) — другие, не используемые в процедуре кластеризации и не обязательно избыточные разряды.

В групповом С„ £ все кластеры {с, } разбиваются на два типа. К первому типу относится единственный кластер, содержащий единичный элемент аддитивной абелевой группы {сг=о) = {0,с0 2о ,...,с() 2Ч'_1}- В таком кластере все

элементы, относящиеся к группе (ф), равны нулю.

Ко второму типу относятся кластеры с номерами г ^ 0. Кластер {с;=0} является базовым. В этом случае, всегда работая с единственным списком, декодер на регулярной основе и с приемлемой сложностью реализации вычислительного процесса позволяет решить задачу быстрого поиска образца ошибок, действовавшего в канале связи. Показывается, что предлагаемый алгоритм носит универсальный характер, поскольку может быть использован как для двоичных, так и для недвоичных кодов различных классов. Другое достоинство описываемого подхода к процедуре декодирования избыточных кодов заключается в реализации возможностей выхода за пределы конструктивных параметров кода по исправлению стираний (ошибок), что особенно важно для современных ИУК и Интернет вещей, работающих с короткими избыточными кодами в условиях интенсивных помех. В последнее время внимание к реализации принципа списочного декодирования выросло в связи с появлением и развитием технологии обработки полярных кодов.

Раскрывается ряд важных свойств лексикографического разбиения.

Свойство 1. Для множества комбинаций, относящихся к одному значению ф5=/, векторы на позициях {к — ф) образуют элементы поля

СР'(2к~<>). Справедливость утверждения вытекает из свойства вложенности двоичных полей Галуа, а следствием этого утверждения является возможность создания эквивалентного кода только при наличии элементов единичной матрицы /(¿_ф)х(*-ф) среди (к — ф) выбранных позиций. Для недвоичных кодов указанное свойство выполняется всегда.

Свойство 2. Любой кластер с номером ф?=;*=0 содержит ключевую комбинацию с, ц, признаком которой является наличие единичного элемента

по операции сложения в поле на выбранных позициях.

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

справедливо и для недвоичных кодов.

Свойство 3. Сложение вектора с,- с любым другим вектором из этого кластера приводит к получению вектора, принадлежащего кластеру с / = 0. Это означает, что нулевой кластер может быть единственным списком, который обрабатывается списочным декодером, а все другие векторы с помощью соответствующих с,ы всегда могут быть приведены к векторам нулевого кластера. Действительно, {с,-^} © с,- у = {0,...,с0 }, поскольку <фТ7.0) е {с,и с1,к1 е 'с/} • После операции сложения в двоичном поле или в поле элементов из

<7/г(2а) для недвоичных кодов позиции (ф) = 0, что означает перевод комбинации в базовый кластер с номером /' = 0.

Это свойство кластерного разбиения позволяет декодеру всегда обрабатывать только один список. Ключевые комбинации кластеров могут храниться в памяти декодера или быть образованы за счет умножения вектора вида (ф/#о) х (к - ф = 0) на С1куп. Свойство справедливо для недвоичных кодов.

Свойство 4. Безошибочное декодирование по единственному списку возможно только при условии правильной идентификации <ф).

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

Использование перечисленных свойств кластерного разбиения пространства кодовых векторов позволяет привести любой вектор из Сп к к

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

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

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

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

900 -

еоо -

700 -600 -500 -400 -300 -200 -100 -о -

Дпина кодового вектора (бит)

Рисунок 5 - Сравнительные данные сложности реализации декодера LDPC кода: 1 - декодирование методом распространения доверия; 2 - декодирование методом быстрого

преобразования Фурье; 3 - перестановочное декодирование; 4 - лексикографическое декодирование (верхняя оценка); 5 - лексикографическое декодирование (нижняя оценка)

При мягком декодировании каждый /-й бит, i = \,n, представляется в виде жесткого решения, сопровождающего MPC в виде некоторого вещественного Л., {l} = ?i_,i.el. Обозначая жесткое решение 0 через знак «-», а решение 1 через «+», для кортежа двоичных данных ...1 0 0 1 1... получают последовательность вида + + которая итеративно

обрабатывается мягким декодером в соответствии с принципом Байеса

L(Xh) + £(Хг)»(-1)1- X sign[i(^)]х sign[£(^)]х mmfzaK)|,|ДЯ.,)|) ,(10)

где функция sign(») возвращает знак своего аргумента; L(Xtl) - MPC символа, участвующего в формировании проверочного бита; L(Xp) - индекс MPC

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

Действия по (10) способствуют повышению значения С0, но их исход не является однозначным. Процедура коррекции для двух информационных разрядов из последовательности длины п со значениями L(Xkl) и L(ktl), выполняемой согласно (10) и для шага итерации с номером j, имеет вид:

^ =|min(s/gn[i(À/l])+ UXcork2)j]^signL(Xp))^sign(Xcork2)j+x^{-\)x-m\ ^^

1 \min(s7g«[z.(/42) + L(Xcorkl )Jx signL(Xp))« sign(Xcorkl)j+l x (- l)'"m.

В соответствии с принципом Байеса при j = 1 на первом шаге итерации апостериорные оценки ХсМ = ХсМ = 0. Из (11) следует, что при L(Xtl) = L(Xtl), любом L(Xp) и при нарушении условия четности процедура коррекции теряет смысл из-за равенства апостериорных оценок ~XrMj = ï-cortlj,

1

Щ................—fr.:—• ' 5

10 12 20

отсюда Cs = Сп. Следовательно, условие L(Xtl) ф L{Xkl) является необходимым для изменения значений функции правдоподобия. Показано, что при реализации условия четности и выполнении равенства Xcorkl = Хеогк1 неравенство С0 > Cs обеспечивается всегда.

Другие возможные события, при которых выполняется С0 > Cs или C0=CS, как результат итеративных преобразований, представлены графом, показанным на рисунке 6.

¿(/й)> ¿(4-2)1 .

> -«г--'-ре ~ ''-max -Со > С s Со <

t s

L(?.M)> L{Akl-) --------«- Apt} = Ânia У

L(Zkl) = L(Âkl) -*C0=CS

Рисунок 6 - Граф переходных состояний в системе итеративных преобразований

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

Сомножитель min(») в (11) указывает на целесообразность формирования целочисленных MPC, поскольку приращение значений оценок определяется соотношением Д = |X,t, -и при рациональных показателях MPC необходим больший объем итераций. Показано, что итеративный процесс, сходящийся к значимым оценкам, не оптимален по параметру минимума числа итераций.

Предложенный алгоритм не является результативным по минимизации числа итеративных циклов, если ЦХк1) и ЦХк2)имеют одноименные знаки. В этом случае в работе предлагается осуществлять циклические сдвиги символов L(Xkl), L(Xkl)ii L(Xp) влево (вправо) так, чтобы на месте проверочного символа оказался MPC с наибольшим индексом из альтернативы L(Xkl) или L(Xt2). Естественно, после выполнения необходимого числа итераций в алгоритме предусматривается обратный циклический сдвиг символов вправо (влево) для их последующей обработки.

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

Четвертая глава. Исследуются методы декодирования недвоичных кодов PC. В целях эффективного достижения требуемых вероятностных характеристик по восстановлению принятых кодовых комбинаций в них целесообразно исправлять только стирания. Однако необходимо учитывать, что среди нестертых позиций символов с некоторой долей вероятности могут быть зафиксированы ошибки. В этой ситуации исправление ровно Е, = (c/mm —1) стираний {clmin - метрика Хэмминга) может привести к ошибочному результату декодирования кодового вектора. Для исключения подобной ситуации априори предполагают, что среди надежных символов возможно появление t ошибок. В таком случае должно соблюдаться соотношение dmbl > 2t + Е,. При исправлении максимально возможного числа стираний важно добиться точного отсутствия ошибок среди недвоичных символов, принятых к обработке после итеративного упорядочения стертых позиций. Для этого предлагается использовать метод провокации, примененный к одному из надежно принятых символов.

В подобном декодере предлагается использовать алгоритм Форни, который исключает применение метода подбора полинома локаторов стираний по алгоритму Берлекэмпа-Месси (АБМ). Алгоритм Форни предполагает выполнение следующих шагов: шаг 1 — по известным позициям нестертых элементов вычисляют полином синдромов Рг(х); шаг 2 - по позициям стертых элементов определяют полином локаторов стираний L(x) и получают производную L'(x); шаг 3 - вычисляют произведение Z(x) = Рк (*) х L(x); шаг 4 — восстанавливают стирания за счет деления Z(x~') на L'(x~'). Наиболее емкими по числу операций сложения и умножения в поле GF(2K) являются операции по определению значений Рг (х) и Цх). Если недвоичный код может исправить \ стираний, то для поиска Р, (х) выполняется K(N-K) операций умножения и (К -1) х (Дг - К) операций сложения, здесь к— число информационных разрядов кода PC, а N- общая длина кодового вектора. При вычислении полинома Р%(х) и в ходе исправления стираний возможна реализация распараллеливания вычислительного процесса, что способствует повышению скорости обработки данных. Работу декодера с системой итеративных преобразований индексов мягких решений Ä и проверками на четность в произведении кодов размерности 2D целесообразно описывать целевой функцией вида

sign{F) шах min

FMpc) № о2(ху

где F - выполнение четности для символов внешнего кода; параметр |Д/(>.)| -среднее значение кортежа мягких решений для символов внутреннего кода; а2(Д) — показатель разброса мягких решений символов внутреннего кода, вычисляемого по правилу

Таким образом, используя указанные параметры для оценки комбинации внутреннего кода Р, можно указать такие символы кода РС, которые трудно восстановить с помощью итеративных преобразований. Эти символы в алгоритме интерпретируются как стирания. Метод провокации стирания заключается в том, что один из элементов кода РС, у которого значение <?{»} оказывается приемлемым, назначается как стирание. Если при выполнении шага 4 алгоритма Форни значение этого стирания подтверждается, то с высокой вероятностью весь кортеж стираний комбинации кода РС оказывается восстановленным верно. В противном случае требуется новый цикл итеративных преобразований, начиная с шага 1.

На рисунках 7 и 8 представлены зависимости вероятности ошибки на бит от соотношения сигнал-шум для двух кодов РС. Заметно, что при ¿/т1П =3 граница исправления ошибок и рассматриваемый метод адекватны. С увеличением метрики Хэмминга энергетический выигрыш увеличивается и может достигать для каскадной конструкции значения 3.. .4 дБ.

Рош

Рош

1x10"

Исправление ошиОс* "

Метол

Ь {дБ)

1x10"

Рисунок 7 — Характеристики кода РС (15,9,7)

Ь{дЕ)

Рисунок 8 — Характеристики кода РС (15,13,3)

Анализируются и сравниваются по критерию скорости обработки данных различные схемы построения алгебраических и неалгебраических декодеров блоковых кодов. Ключевым условием для обоих типов декодеров является вычисление полинома синдромов, на основании которого выполняются все последующие шага. В случае алгебраического декодера для поиска полинома локаторов ошибок используется алгоритм (АБМ). Модифицированный АБМ типа пВМ требует (3/ + 1) операций сложения и (б/ +1) умножения, выполняемых за 21 циклов, где 1 = п-к - число, исправляемых кодом ошибок.

О,

пШ

= 21(31 +1) + 2((6( + 2) = 4,5(п-к)1 + 3(и- к) .

(14)

Эта оценка является точной. Утверждение, что сложность АБМ кратна

2

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

реализации С)(ъ = 2!(д'" — 1) . В совокупности при Я ~ 0,5 приближенная оценка на порядок хуже точной оценки. В неалгебраическом декодере АБМ и алгоритм Ченя заменяются процедурой исправления стираний в предположении, что стертые позиции в достаточной мере покрывают возможные комбинации ошибок (суть е-эффективной системы). Определив число .у ненадежных символов для кода РС, декодер стирает их, обеспечивая в = с! —1. При этом

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

Ч = ГVе> = , где ] = 1,..., п - к. (15)

1=0 8=1

Здесь 5 отвечает номерам нестертых позиций в кодовом векторе, а а — примитивный элемент поля 0!:(с/). Общее число арифметических операций для правой части неравенства оценивается как Ох ={п — к)(2к -1). Функция 05(Я) имеет максимум в точке к = (и/2) + 0,25 ~ 0,57?. Далее в мягком декодере по известным номерам стертых позиций получают полином локаторов стираний ¿Л(дг) = ПО ~ х). Число сомножителей в этом произведении по условию (15)

всегда равно (п - к). Сложность реализации этой процедуры оценивается как Од = Ол+ + 0Лх = (и - к — I)2 +(п- к)2. По найденным значениям полиномов ^(дг) и ¿Л (х) находят их произведение, в котором все элементы при х со степенями, равными и старше величины п — к, в расчет не принимаются. В качестве верхней оценки сложности реализации этого произведения на основе эмпирических данных целесообразно взять усредненную величину 05д я 0,20К. Выигрыш в, получаемый при использовании неалгебраического декодера, в процентах показан на рисунке 9.

о о

а) б)

Рисунок 9 - Сравнительные данные выигрыша в процентах при реализации алгоритмов: а) код PC длины 15; б) код PC длины 255

Исходя из приближенной оценки АБМ полученный выигрыш по производительности не превышает 34%. Он относительно одинаков на всем

интервале изменений параметра R. В случае использования оценки OriBMвыигрыш монотонно возрастает по мере увеличения Л, но не превышает 60% при R = 0,5. Таким образом, декодер с исправлением стираний, формируемых по правилу максимального числа стираний на длине кодового вектора, позволяет повысить производительность декодера, по крайней мере, на 37%.

Принцип построения произведений кодов (ПК) заданной размерности заключается в системном изменении избыточности при наращивании объема информационных блоков. В общем случае порождающая матрица тривиального кода с единственной проверкой четности (КПЧ) имеет вид G = гДе

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

Для получения ПК из двух тривиальных КПЧ размерности 2D кодер формирует из к векторов-строк квадратную матрицу Ак = |aa0z|f > гДе х = \,к,

z = l,k, и только для данной размерности положим >> = 0. Таким образом, .для удобства последующих рассуждений матрица Ак рассматривается в плоскости xOz пространственной системы координат. Матрица Лк путем проверок четности по векторам-строкам и векторам-столбцам преобразуется в матрицу вида Ап =\\ax0z j|". Очевидно, что в Ак общее число информационных

элементов достигает значения к1, тогда как число проверочных разрядов в Ап будет равно /^д = 2к+1. Для выявления общих закономерностей формирования избыточных символов ПК произвольной размерности целесообразно значение гго разделить на две составляющие: г2'о = , определяющую избыточность по

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

В последующем избыточность, непосредственно зависящую от проверок информационных разрядов, обозначим символом (•). Проверку от проверочных разрядов представим символом «•)). Матричная форма описанного кода имеет вид

ЙЮ1 а\02 — а№ Цол) а201 а202 А„= ..........

ак01 ак02 <«и01> <а«02>

«20к (а20п) .......... (16)

ак0к (ак0п) <«и0*> ««„Об-

общая избыточность оценивается выражением г20 = rl'jl + г"") = 2к +1.

Структура ПК в ЗЭ образуется при у ^ 0, если следом за матрицей ¡¡я^, по

координате у дополнительно разместить новую матрицу ||аЛ2г||" и так до

значения у = п-1, а затем на позиции у-п сформировать матрицу проверок

Следовательно, кодер формирует к матриц А„ размерности 2Э,

II II" II II" II II"

получая совокупность матриц = , = |аХ2г^ ' ••• »^и ^ЧиьЦ, •

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

II II"

ах]: ® ахо: ©...©ахк2 = ахп2, и формирует матрицу проверок (Ап) = Ца^^Ц по

всевозможным х и г.

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

соотношением Я = а минимальное кодовое

<7=1 9=1

О

расстояние для описанных конструкций определяется как = \\с1д=2 .

<7=1

Применяя последовательно это правило несколько раз, можно получить широкий диапазон длин кодов. Например, код размерности 40 получают из п кадров кода ЗЭ, при этом новые проверочные символы формируют соответствующим сложением одноименных матриц размерности 20, взятых по одной из всех кадров 30. Код размерности 40 образуется путем объединения к совокупностей с образованием матричной структуры вида:

4]=к12Г 4*=к! ... 4*=|ЫГ <Ап>=к,1

1 «н -"III - н -"III

(17)

^1=К4 ^2=Ь4 - ^=1Ь4 <^>=Ь4

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

(17) обозначение вида показывает, что берется матрица с номером ;

из кадра с номером у с образованием проверочных соотношений вида (•) и ((•)) . Для произвольных Э полная избыточность определяется соотношением

1 ) (2

(к + \У>-к° = " №к°~ 2+...+ " \к +1. (18)

О-1

Декодер приемника при любой размерности КПЧ обрабатывает только совокупность кадров, поэтому его сложность однозначно определяется сложностью декодирования кадра. Характеристики некоторых ПК представлены в таблице 1. Естественно, код Ш не является произведением кодов, но параметры других кодов, приведенных в этой таблице, кратны его к и п. В графе таблицы с символом я4представлены относительные скорости кодов при условии выкалывания избыточных символов порядка один и более, иначе тех символов, которые определяют структуру избыточных кадров «•».

Таблица 1 - Параметры произведений кодов ряда размерностей

Размерность кода Значение к Значение п 4шп я «4

т 8 9 2 0,89 -

64 81 4 0,79 0.80

зэ 512 729 8 0,70 0,73

40 4096 6561 16 0,62 0,67

5Э 32768 59049 32 0,55 0.67

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

Пятая глава. Посвящается описанию системы каскадного кодирования, выполненной на базе программно-аппаратного комплекса с использованием предложенных в диссертации алгоритмов. В состав комплекса входит: базовый модуль с постоянной конфигурацией (модуль «М-2С.ХК.01»); программа, реализованная на процессоре, встроенном в ПЛИС типа «ЕРЗС120Р78017», модуль с управляющей программой из состава программного комплекса каналообразующей аппаратуры; программа описывающая интерфейс взаимодействия модуля со средствами каналообразования из состава программного комплекса. Приводятся данные статистических испытаний разработанного комплекса, подтверждающие целесообразность применения предложенных алгоритмов в системах обмена данными ИУК.

В заключении сформулированы основные результаты исследований: 1. Разработана концепция применения избыточных кодов небольшой длины в современных высокоскоростных ИУК и представлены методы

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

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

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

4. Установлено, что незнание статистических характеристик используемых каналов связи отрицательно влияет на процесс формирования MPC, особенно в области высоких соотношений сигнал-шум. Если этот параметр находится в пределах от 0 до 5 дБ, то расхождения между предложенными в работе целочисленными MPC и оценками определенными методом логарифма отношения правдоподобия, не превышает 10%. Однако расхождение сравниваемых оценок резко возрастает при увеличении отношения сигнал-шум более 5 дБ, что является отрицательным фактором для большинства реальных ИУК, использующих канал с быстроменяющимися параметрами.

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

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

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

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

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

10. Разработана методика целенаправленных итеративных преобразований символов кодовых векторов внешнего кода каскадных конструкций на основе предложенной целевой функции, учитывающей результат обработки комбинаций внутреннего кода, значения математического ожидания и дисперсии обработанных MPC. Полное использование введенной в код избыточности повышает ЭВК каскадного кода в зависимости от параметров кода от 2 до 3 дБ, обеспечивая повышение производительности декодера от 30 до 50 процентов.

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ

Монография

1. Гладких A.A. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи. - Ульяновск: УлГТУ, 2010.— 379 с.

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

1. Гладких A.A., Мансуров А.И., Черторийский С.Ю. Статистическая оценка индексов достоверности символов, формируемых в системе с мягким декодированием // Инфокоммуникационные технологии. - 2008. - Том 6, № 1. -С. 39-43.

2. Гладких A.A., Шакуров Р.Ш., Украинцев К.Ю. Асимптотическая оценка процедуры неалгебраического декодирования избыточных кодов // Периодический научно-технический и информационно-аналитический журнал Инфокоммуникационные технологии. - 2009. - Том 6, № 3. - С. 30-34.

3. Гладких A.A., Агеев С.А., Ващенко А.П. Сравнительные оценки методов формирования индексов достоверности символов в системе мягкого декодирования избыточных кодов // Известия института инженерной физики. — 2010.-№ 1 (15).-С. 42^17.

4. Гладких A.A., Шакуров Р.Ш., Бородина Е.С. Декодирование недвоичных кодов в адаптивных системах обмена данными // Автоматизация процессов управления. — 2011. — № 2(24). — С. 51—55.

5. Гладких A.A. Применение метода гиперкодирования в системах передачи данных // Автоматизация процессов управления. - 2011. - № 2(24). — С. 77-81.

6. Капустин Д.А., Гладких A.A., Дементьев В.Е., Воронин В.В. Реализация процедуры мягкого декодирования блоковых кодов методом кластерного анализа // Успехи современной радиоэлектроники. Труды Всероссийского семинара по проблеме «Развитие теоретических аспектов в области синтеза технических систем и комплексов». - 2011. - № 9. - С. 30-37.

7. Гладких A.A. Модели формирования мягких решений при обработке сигналов телекоммуникационных систем // Радиотехника № 9. Радиосистемы № 175, Мат. моделирование инфокоммуникационных систем. - 2012. - №1. — С. 21-24.

8. Гладких A.A., Солодовникова Д.Н. Численное моделирование адаптивной системы обмена данными на основе многомерных произведений кодов // Радиотехника № 9. Радиосистемы № 175, Математическое моделирование инфокоммуникационных систем. — 2012. — №1. — С. 24—27.

9. Гладких A.A., Линьков И.С. Оптимизация процедуры итеративных преобразований данных // Автоматизация процессов управления. - 2012. -№3(29).-С. 3-7.

10. Агеев C.B., Саенко И.Б., Егоров Ю.П., Гладких A.A. К разработке комплекса математических моделей управления защищенной мультисервисной сетью // Автоматизация процессов управления. — 2012. — № 3(29). — С. 8—18.

11. Гладких A.A., Баскаков Е.С., Маслов A.A., Тамразян Г.М. Эффективное декодирование недвоичных кодов с провокацией стертого элемента // Автоматизация процессов управления. -2013. -№ 2(32). - С. 87-93.

12. Гладких A.A., Климов Р.В. Численное моделирование обобщенной процедуры формирования индексов мягких решений // Инфокоммуникационные технологии. - 2013. - Том 12, № 2. - С. 22-28.

13. Гладких A.A. Обработка изображений с кодовым квантованием на основе лексикографического метода // Наукоемкие технологии. - 2013. - № 5. -С. 42-45.

14. Гладких A.A., Линьков И.С., Чилихин Н.Ю. Мягкое декодирование произведений кодов произвольной размерности на базе кодов с единственной проверкой четности // Известия Самарского научного центра РАН. - 2013. - т. 15, 4(3).-С. 668-674.

15. Гладких A.A., Чилихин Н.Ю. Формирование мягких решений в системе широкополосного канала связи с QPSK-QAM // Автоматизация процессов управления. - 2013. - № 3(33). - С. 75-79.

16. Гладких А. А., Чилихин Н.Ю. Моделирование алгоритмов совместной обработки полярных кодов в системе произведения кодов // Радиотехника. -2014.-№ 7.-С. 111-115.

17. Гладких A.A., Юдина Е.А. Модели сжатия изображений с кодовым квантованием и лексикографическим восстановлением их по спискам // Радиотехника. - 2014. - № 7. - С. 116-119.

18. Гладких A.A. Оценка сложности аппаратурных затрат в процедуре мягкого алгебраического декодирования недвоичных кодов // Автоматизация процессов управления. - 2014. - № 3 (37). - С. 40-47.

19. Гладких A.A., Чилихин Н.Ю. Декодирование полярных кодов в декодере Арикана на базе индексов мягких решений // Инфокоммуникационные технологии. - 2014. - № 3. - С. 11-17.

20. Гладких A.A., Чилихин Н.Ю., Наместников С.М., Ганин Д.В. Унификация алгоритмов декодирования избыточных кодов в системе интегрированных информационно-управляющих комплексов // Автоматизация процессов управления. -2015. -№ 1(39). - С. 13-20.

21. Гладких A.A. Обобщенный метод декодирования по списку на базе кластеризации пространства кодовых векторов // Радиотехника. - 2015 - № 6-С. 37-41.

Список патентов

1. Гладких A.A., Тетерко В.В., Васильев К.К. Устройство для восстановления кодовой последовательности. Патент на изобретение RU № 2166235, опубликовано 27.04.2001. Бюл. № 12.

2. Гладких A.A., Визнренко А.Б., Тетерко В.В., Климентьев П.В., Сергеев В.А. Декодер с изменяемым интервалом стирания. Патент на изобретение RU № 2209519, опубликовано 27.07.2003. Бюл. № 12.

3. Гладких A.A., Тетерко В.В., Васильев К.К., Визиренко А.Б. Декодер с повышенным уровнем различия оценок надежности. Патент на изобретение RU № 2209520, опубликовано 27.07.2003. Бюл. № 12.

4. Гладких А.А.,Черторийский С.Ю., Тетерко В.В., Шакуров Р.Ш., Закирова Л.Р. Устройство исправления стираний. Патент на изобретение RU № 2344556, опубликовано 18.02.2009 г. Бюл. № 2.

5. Гладких A.A., Агеев С.А., Кержнер Д.А., Петров В.В., Репин Г.А., Служивый М.Н. Декодер с исправлением стираний. Патент на изобретение RU № 2379841, опубликовано 20.01.2010. Бюл. № 2.

6. Гладких A.A., Егоров Ю.П., Пятаков А.И., Кальников В.В., Бородина Е.С. Декодер с повышенной корректирующей способностью. Патент на изобретение RU № 2438252, опубликовано 27.12.2011. Бюл. № 36.

7. Гладких A.A. Способ мягкого декодирования систематических блоковых кодов. Патент на изобретение RU № 24444127, опубликовано 27.02.2012. Бюл №6.

8. Гладких A.A., Капустин Д.А., Климов Р.В., Солодовникова Д.Н. Адаптивный кодер гиперкода размерности 3D. Патент на изобретение № 2480918, опубликовано 27.04.2013. Бюл. № 12.

9. Агеев С.А., Гладких A.A., Егоров Ю.П., Саенко И.Б., Солодовникова Д.Н., Шитиков С.П. Система исправления стираний с защитой номера кластера. Патент на изобретение RU№ 2485702, опубликовано 20.06.2013. Бюл. № 17.

10. Гладких A.A., Капустин Д.А., Логинова К.Е., Ермолаева A.C. Декодер с упорядоченной статистикой символов. Патент на изобретение RU № 2901804, опубликовано 20.08.2013. Бюл. № 23.

11. Гладких A.A., Осадчий А.И., Агеев С.А., Комашинский В.И., Линьков И.С., Солодовникова Д.Н. Адаптивный декодер произведения кодов размерности 3D. Патент РФ № 2500073, опубликовано 27.11.2013. Бюл. № 32.

12. Гладких A.A., Маслов A.A., Тамразян Г.М. Мягкий декодер последовательного турбокода. Патент РФ. - № 2538331, опубликовано 10.01.2015. Бюл. №1.

Выборочный список основных публикаций в других изданиях

1. Охорзин В.М, Гладких A.A. Эффективность применения схем каскадного кодирования в стирающем канале связи: Сборник «Построение и анализ систем передачи информации», Наука, № 5, 1980. - С. 23-24.

2. Гладких A.A., Мансуров А.И., Закирова Л.Р. Принцип итеративного мягкого декодирования систематических кодов по стираниям: Ученые записки Ульяновского государственного университета. Серия Математика и информационные технологии. Вып.1 / ред. A.A. Смагина. - Ульяновск, 2008. -С. 34-38.

3. Гладких A.A. Асимптотические оценки методов декодирования избыточных кодов. Математическое моделирование физических, экономических, технических, социальных систем и процессов. Труды седьмой Международной конференции. - Ульяновск, 2009. - С. 81-83.

4. Гладких A.A. Асимптотические оценки различных процедур декодирования: Труды Российского научно-технического общества радиоэлектроники и связи им. A.C. Попова. Выпуск LXIV, 2009. - С. 319-321.

5. Солодовникова Д.Н., Гладких A.A. Гиперкоды - перспективное направление защиты цифровой информации от ошибок. X Международная научно-техническая конференция «Физика и технические положения волновых процессов», материалы конференции. - Самара, 2011. - С. 348-350.

6. Гладких A.A., Шакуров Р.Ш. Повышение эффективности декодирования по упорядоченным статистикам. Труды Российского научно-технического общества радиоэлектроники и связи им. A.C. Попова. Выпуск LXVI, 2011.-С. 237-239.

7. Гладких A.A., Капустин Д.А., Климов Р.В. Применение мягких декодеров в системе сетевого кодирования. Труды Российского научно-технического общества радиоэлектроники и связи им. A.C. Попова // Цифровая обработка сигналов и ее применение выпуск XIV-1,2012. — С. 161-165.

8. Гладких A.A., Бородина Е.С., Солодовникова Д.Н. Применение многомерных кодов произведений в адаптивных системах передачи данных. 67-я Всероссийская Конференция с международным участием «Научная сессия, посвященная Дню радио». Труды Российского научно-технического общества радиоэлектроники и связи им. A.C. Попова. Выпуск LXVII, 2012. - С. 431—434.

9. Гладких A.A., Климов Р.В., Линьков И.С. Принцип формирования индексов мягких решений символов на основе модификации стирающего канала связи. XIX Международная научно-техническая конференция «Радиолокация. Навигация. Связь». - Воронеж, 2013, Том 1. - С. 373-381.

10. Гладких A.A., Солодовникова Д.Н., Чилихин Н.Ю., Юдина Е.А. Декодирование произведений кодов на основе принципа работы клеточного автомата. XIX Международная научно-техническая конференция «Радиолокация. Навигация. Связь». - Воронеж, 2013, Том 1. — С. 364-372.

11. Гладких A.A., Баскакова Е.С., Тамразян Г.М. XIX Международная научно-техническая конференция «Радиолокация. Навигация. Связь». -Воронеж, 2013, Том 1. - С. 355-363.

12. Гладких A.A., Чилихин Н.Ю. Эффективное декодирование двоичных блоковых кодов. XV Международная НТК «Проблемы техники и технологий телекоммуникаций» и XII Международная НТК «Оптические технологии в телекоммуникациях». — Казань, 2014, Том 1. — С. 71—73.

Гладких Анатолий Афанасьевич

Методы лексикографического декодирования избыточных кодов на базе модификаций стирающего канала связи

Подписано в печать 18.09.2015. Формат 60x84/16.

Усл. печ. л. 1,86. Тираж 100 экз. Заказ 742. ИПК «Венец», 432027, г. Ульяновск, Северный Венец, 32