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

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

Введение

ГЛАВА 1. Синтез математических моделей телекоммникационных систем интегрированных инормационно-управляющих комплексов 23

1.1. Задача синтеза телекоммуникационных систем, используемых в составе информационно-управляющих комплексов 23

1.2. Совершенствование характеристик информационно-управляющих комплексов на базе современных сетевых технологий 33

1.3. Асимптотическая эффективность процедуры декодирования блоковых избыточных кодов 43

1.4. Концепция математических моделей непрерывного канала связи... 51

1.5. Модель канала связи со стиранием элементов 57

1.6. Основные модели дискретного канала связи 59

1.7. Метод скользящих окон в стирающем канале связи 63

1.8. Стирающий канал как основа концепции полярных кодов 69

1.9. Выводы по главе 79

ГЛАВА 2. Математические модели формирования мягких решений символов в системе декодирования избыточных кодов 82

2.1. Классификация алгоритмов формирования мягких решений символов 82

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

2.2. Снижения доли ложных стираний на основе случайного поиска решения о стирании элемента 88

2.2.1. Алгоритм с динамично изменяющейся границей (алгоритм 1) 91

2.2.2. Алгоритм с жесткой границей (алгоритм 2) 93

2.2.3. Алгоритм с использованием границы в формате отношения правдоподобий 96

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

2.4. Принцип оптимизации рабочей характеристики приемника 112

2.5. Формирование мягких решений символов в системе сложных сигналов 113

2.6. Оптимизация приемника с мягким решающим правилом в условиях преднамеренных помех 117

2.7. Выводы по главе 122

ГЛАВА 3. Субоптимальное лексикографическое декодирование двоичных кодов 125

3.1. Концепция разбиения пространства кодовых векторов на кластеры 125

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

3.2.1. Декодирование двоичных кодов 133

3.2.2. Геометрическое представление алгебраической группы 135

3.2.3. Декодирование непрерывных кодов с применением метода кластеризации пространства кодовых векторов 137

3.2.4. Декодирование кодов с малой плотностью проверок на четность методом разбиения на кластеры 140

3.2.5. Модулярное представление линейных кодов и их эквивалентность 149

3.2.6. Декодирование низкоплотностных кодов методом перестановок 156

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

3.4. Классификация методов защиты номера кластера 166

3.5. Лексикографическое декодирование полярных кодов 175

3.6. Выводы по главе 179

ГЛАВА 4. Эффективное декодирование недвоичных блоковых кодов 183

4.1. Особенности применения не двоичных кодов в современных телекоммуникационных технологиях 183

4.2. Итеративные преобразования кодов Рида-Соломона на основе упорядоченных статистик 197

4.3. Описание алгоритма исправления ошибок недвоичными кодами... 201

4.4. Эффективное декодирование недвоичных кодов с провокацией стертого элемента 211

4.5. Оценка сложности реализации декодера не двоичного кода 218

4.6. Лексикографическое декодирование недвоичных блоковых кодов.. 226

4.7. Принципы формирования произведений кодов размерности 3D и более 231

4.8. Выводы по главе 241

ГЛАВА 5. Реализация и результаты натурных испытаний адаптивного информацонно-управляющего коплекса

5.1. Аппаратная платформа мата и методика проведения его испытаний 243

5.2. Результаты статистических испытаний макета

5.3. Выводы по главе - 59

Заключение 261

Библиографический список 264

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. На основе предложенных рабочих характеристик вычисления оценок МРС разработаны и исследованы алгоритмы в условиях использования преобразований 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 наименования.

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

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

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

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

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

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

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

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

Совершенствование характеристик информационно-управляющих комплексов на базе современных сетевых технологий

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

Показатели эффективности (ПЭ) допустимых (возможно определенных только в виде граничных значений) условий из U и выбранных или жестко заданных элементов из V для реализации Fy ] оцениваются набором вещественных чисел {R\. Процедура подбора или поиска V для выявленных условий U и достижения F\»}, ИХ допустимые вариативные изменения F:VxU — R в процессе обоснования структуры и характеристик реальных объектов отражают особенности концептуального и семантического моделирования синтезируемых систем, позволяющих сформулировать постановку математических задач и организовать их решение в виде формальных моделей [47, 152, 155].

В случае конкретизации условий {и0,щ,...,ип,..}= , где UQEU, процесс функционирования синтезируемой системы принимает классический характер оптимизации (в общем случае многокритериальный) в смысле достижения тех или иных экстремальных показателей Тэкст є R и (или) Рэкст є R. Ffr,U0} max. (1.1) VeV В качестве решений задачи (1.1) рассматривается множество Ve(V,U0) так называемых є - оптимальных систем Ve{& О), определяемое выражением VeeVe(V,U0,T,P) F{V,U,T,P}F$.,U0,T,p}+s (1.2) для любых V GV [152, 155]. Таким образом, для выбранных V и конкретизированных условий U0 показатели функционирования є -оптимальной системы не могут быть улучшены, и, если є 0, сохраняется целесообразность поиска вариантов снижения вычислительных затрат. При є = 0 оптимальные элементы системы отсутствуют

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

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

Важным свойством класса условий UHO, приводящим к специфическим задачам синтеза систем, является их конфликтность. Конфликтность условий функционирования ТКС накладывает существенный отпечаток на принципы постановки и решения задач синтеза подобных систем. Синтезируемый для функционирования в конфликтных условиях элемент ТКС должен обладать свойством устойчивости не к какому-либо заданному типу внешних воздействий, а к целому классу. Подразумевается, что воздействие может выбираться в определенном отношении оптимальным (по крайней мере оптимизированным) из класса, ограниченного совокупностью энергетических, технических, экономических и интеллектуальных ресурсов противодействующей системы [152]. Сущность конфликтной среды заключается в том, что конкретизация элемента Uно є U, для данной системы V может осуществляться за счет влияния природных стохастических факторов или противной стороной (противником), целью которой является решение противоположной задачи (например, оптимизированным в энергетическом смысле, влиянием на ТКС с целью минимизации значения ПЭ Fy }) вплоть до фатального срыва функционирования ИУК [47, 155]. Если в ТКС из состава ИУК используется помехоустойчивый код Сп , где п - длина кодовой комбинации, к - число информационных разрядов, a d -метрика Хемминга, то достаточно вносить в комбинацию кода t yd +1)/2 ошибок, чтобы сорвать работу кодека или перевести ТКС в режим повторения информации по запросам и неоправданному увеличению параметра Тсс.

Целесообразность рассмотрения задачи синтеза в данном случае обусловлена практической необходимостью проектирования систем, функционирование которых предполагается при применении противником средств, специально разработанных для подавления проектируемой системы. В указанных выше условиях є -оптимальная система способна обеспечивать субоптимальные режимы функционирования декодера, например, за счет использования режима мягкой обработки данных и исправления стираний, а не только режима исправления ошибок [1, 3, 4, 50, 57, 78,87, 153-155].

В новых условиях декодер формирует максимально возможное число стертых позиций [9, 65, 151, 155] для минимизации ошибочного декодирования данных (декодирование за пределами конструктивных возможностей кода). Обычно близкие к этому алгоритмы алгебраического декодирования используют сведения о весовой структуре кода [123, 126, 229].

Алгоритм с использованием границы в формате отношения правдоподобий

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

Достоинством метода является получение целочисленных МРС, что востребовано при обработке ПК [130]. На рисунке 2.3 представлены сравнительные характеристики knp(h) для схемы квантования и схемы со скользящими окнами, в которой использовалось р = 0,7.

Близость указанных характеристик к граничной характеристике говорит о целесообразности введения широкого интервала стирания в системе формирования оценок по методу скользящих окон для снижения вероятности ошибочных решений [47, 155]. Однако введение широкого интервала стирания приводит к росту ложных стираний, что оказывает отрицательное влияние на процедуру сортировки оценок в мягком декодере из-за снижения количества МРС с показателем A,max.

В работе [116] для снижения доли ложных стираний предлагается и исследуется метод рандомизации в ходе принятия решения о стирании. Для этого рассматривается модель непрерывного канала связи, представленная выражением (1.24) :(t)= jh(t,t )w(t )dt + n(t). Известно, что первое слагаемое композиция двух плотностей вероятностей представляет собой интеграл свертки +00 f(t) = fi(t)f2(t)= jfiMMtjdT, (2.7) —00 где r = t — t [116, 142]. В целях формирования плотностей вероятностей с различными аналитическими выражениями соотношение (2.7) можно трансформировать процедурой рандомизации, иначе говоря, процедурой случайного поиска решения [116]. Пусть р(х,д) - плотность вероятности, зависящая от параметра д, и р(д) - некоторая, вообще говоря, произвольная плотность вероятности. Тогда функция будет также плотностью вероятности. Если параметр д принимает дискретные значения с вероятностями Ph = Р{д = д}, j = 1, 2..., то интегральное выражение (2.8) принимает вид которое получило название смеси непрерывного и дискретного распределений [116,142]. Пусть в стирающем канале связи с симметричным р параметр р(х,д) из (2.9) подчиняется нормальному закону распределения и, значит, Рпр Рлс Снижение влияния параметра является центральной задачей в процедуре мягкого декодирования при использовании метода скользящих окон при формировании МРС. В целях минимизации вероятности рлс в работах [47, 116] предлагается использовать алгоритм рандомизации, который учитывает особенности уровня принятого сигнала, попавшего в зону неопределенности. Применительно к каналу с независимым потоком ошибок при і = 1 вероятность правильного стирания оценивается как О

Тогда pnc{zi=-p jRb\wi) pnc{zi=0\wi). Учитывая эту особенность, в [116] предлагается использовать случайный поиск решения о стирании, применяя закономерности равномерной ПРВ совместно с оценкой удаления сигнала z7 от порога zt = -pyjEb . При этом интервал значений случайной величины z от границы - РдД до порога 0 разбивается на п равных участков величиной А, для которых вычисляется среднее значение 8 = pnc{zt \st).

Общее выражение для определения вероятности ошибочных решений приобретает вид [116] в котором второе слагаемое определяет долю ошибок, вносимых процедурой рандомизации. В [116] показано, что применение метода обеспечивает получение энергетического выигрыша, начиная с h = 3 дБ, равного примерно 0,2 дБ при Рош= и Р = 0Д- Увеличение интервала стирания приводит к росту указанного выигрыша, где г] - среднее значение стираний для верно принятых символов. Оценка получаемого выигрыша при использовании данной методики показала, что лучшие показатели от введения процедуры рандомизации обеспечиваются при малом значении р. Это объясняется тем, что при таких интервалах стирания вероятность ложных стираний невелика, в то время, как для больших значений р выигрыш становится менее заметен из-за роста вероятности ложных решений о стирании.

Алгоритм с динамично изменяющейся границей. Алгоритм 1 В целях минимизации параметра рлс в работе [116] был предложен и исследован способ формирования неопределенного решения на основе перехода от масштаба стирающего канала связи к масштабу датчика случайных чисел (ДСЧ) с равномерной ПРВ и диапазоном значений от 0 до 1. Если в ходе обработки сигнала z7-ero параметры оказываются вне интервала стирания, то такой сигнал фиксируется в виде жесткого решения [47, 116]. В условиях, когда выполняется 0 \zj: Py/Efj , приемник фиксирует предварительное решение о стирании и фиксирует пороговое значение у = \zt / р- Е}, . Очевидно, 0 у 1.

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

Декодирование непрерывных кодов с применением метода кластеризации пространства кодовых векторов

Применение итеративных преобразований для проверки значений (ф) и (к - ф) позволяет избежать процедуры Skxk х S xk = Е, и это обеспечивает резкое снижение вычислительных затрат, выполняемых декодером. Пусть приемник принял кортеж данных ...1 0 0 1 1..., который с учетом МРС преобразуется в последовательность вида ...+Xt-Ai+l -Лі+2 + А,г+3 + 4+4 --6 мягком декодере она обрабатывается по правилу: Ь{ХМ) + Ь{Хр) « (- 1)х sign[L{XM)\xsign[b(Xp)]x тшд ), ЦхЖ (3.48) 163 здесь функция sign(») возвращает знак своего аргумента; LiX ) - МРС, участвующее в формировании проверочного бита; L{Xp) - индекс мягкого решения проверочного символа [133, 164]. Обозначая через конечный алфавит \Xj} множество формируемых декодером индексов МРС, получим \Aj у — Amjn, Amax.

Задача состоит в оценке условий того, что после передачи по каналу последовательности С0 функции правдоподобия всех последовательностей CL будут больше функции правдоподобия последовательности С0. В общем случае для системы частных проверочных соотношений, создаваемых при уточнении параметров (fy и (-ф) допустимо исключение из процедуры (3.48) бит с высокими индексами МРС. Это снижает число выполняемых операций, но в этом случае выражение (3.48) трансформируется к виду L{XM) + L(Xp) (- \f m х sign[L{XM)\xsign[L{Xp)]x тіп(ц ),Ц )), (3.49) где m- число вычеркиваемых из частного проверочного соотношения единиц с высокими показателями МРС. Для вычеркнутых нулевых бит т = 0. С учетом выражения (3.49) процедура коррекции двух информационных разрядов из последовательности длины (ф) со значениями L(Akl) и L(Ak2) имеет вид stepj mm(sign[L(Xkl) + Щкорк2)]х sign(Xp)) sign(XKOpk2) х (-1)1 т; L{Xk2) + L(KoPk\)JX signCkp)) sign{XKOpkl) x (-1) m. Из (3.50) следует несколько важных свойств. Свойство 3.15. При выполнении условия Ь(Хк\) = Ь(Хк2) Для произвольного значения ЦЛр) и невыполнении условия четности для системы проверяемых символов процедура С CQ теряет смысл.

Действительно: для любого шага с номером / КорЫ = корк2 поэтому коррекция значений МРС не происходит, и CL =С0.

Следствие 3.15-1. Выполнение четности (+рс) для группы корректируемых символов при L(Akl) L(Ak2) является достаточным условием для коррекции значения функции правдоподобия С0. Следствие 3.15-2. Невыполнение условия четности (-рс) для группы корректируемых символов при Ь(Хы) Ь(Хк2) или Ь(Хы) Ь(Хк2) приводит к однозначной смене знака для меньшего показателя МРС, что равносильно исправлению ошибки на уровне жесткого решения.

Следствие 3.15-3. При невыполнении условия четности {-рс) для группы Корректируемых СИМВОЛОВ И ДОПОЛНИТеЛЬНОМ УСЛОВИИ L(X/ci) L{\fc2) или L{Xkl) LQ hl) значение жесткого решения для символа с наименьшим МРС может быть инвертировано на противоположное значение без реализации итеративных преобразований. Свойство 3.16. Высокое значение МРС для L(Ap) способствует сокращению числа итераций для достижения CL CQ. Следствие 3.16-1. В случае низкого значения L(Xp) = Xmin допускается циклический сдвиг индексов МРС с целью размещения на позиции L(Ap) символа с максимальным МРС L(Xp) = A,max Свойство 3.17. В случае выполнения L(Xp) = Xmax и Х - А 2 і число итераций до получения надежного корректирующего значения становится тем больше, чем меньше разница между Х \ и А 2 Следствие 3.17-1. В целях снижения числа итеративных преобразований целесообразность использования целочисленных МРС предпочтительнее относительно их дробных аналогов.

Сравнительные данные для рациональных МРС: 1 - дробный формат с минимальной разницей между корректируемыми МРС; 2 - дробный формат с большой разницей между корректируемыми значениями; 3 - целочисленный формат Пример 3.4. Передатчик передает вектор Vnep=\0\\\0. В канале связи действует помеха вида Volu = 101010, которая частично поразила символы (ф), (к-ф) и (п-к}. Приемник принимает комбинацию кода, в которой нижними индексами показаны значения МРС

В результате декодер обеспечивает исправление первого символа: - 3 + 7 = +4, и подтверждение знака второго символа: -4-2 = -6. В соответствии со следствием 3.14-3 значение первого жесткого решения могло быть инвертировано с указанием произвольного значения МРС. Следовательно, итеративные преобразования не оказывают влияния на число арифметических операций и не влекут за собой повышение сложности декодера. Вектор Vnp принимает вид: Vnp = I4O5O2I7O1O6 и Для этои кодовой комбинации значение (ф) определено надежно. В соответствии с перечнем комбинаций LDPC кода вектор Vnp принадлежит второму кластеру, но однозначно эту кодовую комбинацию декодер идентифицировать не может из-за неопределенности значения (k — ty.

Выделяя символы 02І70б или -2+7-6, по следствию 3.14-3 получаем вектор кодовой комбинации, у которой элементы ф) и (к - ф) приняты надежно, следовательно, комбинация определена декодером однозначно. Таким образом, применение итеративных преобразований позволяет избежать мало продуктивных вычислений, связанных с определением обратной матрицы, поиском порождающей матрицы в систематической форме, выработкой перестановочной матрицы и ее транспонированного аналога.

Перечисленные свойства лексикографического разбиения пространства кодовых комбинаций линейных кодов во многом зависят от дополнительных свойств используемых в системе обмена данными кодов [73]. Структура выражений (3.50) указывает на целесообразность использования в системе итеративных преобразований двоичных кодов трех-четырех бит, один из которых является символом проверки четности. Проверочный бит может быть введен искусственно [47, 69, 73, 116], но наиболее рациональным является использование свойств проверочной матрицы Н линейного кода, которые обеспечивают защиту номера кластера (ф) и разрядов (к - ф) без дополнительных аппаратурных затрат. Пусть дан код БЧХ (15,5,7), проверочная матрица которого имеет вид

Эффективное декодирование недвоичных кодов с провокацией стертого элемента

Исследования в области помехоустойчивого кодирования показали достоинства кодов с проверкой на четность (КПЧ), которые наиболее эффективно реализованы в кодах с малой плотностью проверок на четность, в последовательных каскадных конструкциях и в плетеных сверточных кодах [42, 43, 86, 103]. Применение классических конструкций КПЧ с одной проверкой четности в виде произведений нескольких кодов описано в работах [42, 71]. В них особое внимание уделено исследованию кодов размерностей 2D, а коды размерности 3D описаны в работе [62, 196]. Повышенное внимание к подобным системам защиты данных от ошибок объясняется возможностью применения в них простых алгоритмов декодирования, основанных на итеративных преобразованиях МРС. Важной особенностью подобных кодов является их структурная приспособленность к использованию в процедуре декодирования перспективных моделей клеточных автоматов [119].

Принцип построения ПРК заданной размерности заключается в системном изменении избыточности при наращивании объема информационных блоков. Рассмотрим модели построения ПРК произвольной размерности. Пусть кодер избыточного кода формирует слова конечной длины п из замкнутого множества S, для которых справедливо правило единственной проверки четности, применяемое к информационным векторам длины к, тогда п = к + \. В общем случае символы этих слов выбираются из конечного алфавита А = {а}, которые приемником фиксируются в виде жестких решений. Параметр а принимает значения из GF\2mJ, где m N. Обозначим через а0 =\ау,...,а ) переданную по каналу связи последовательность, а через as = \ау,...,а\п ), s = \,S другие последовательности рассматриваемого множества. Задача декодера, как и ранее, такой, что Q) Cs для всех последовательностей из S. При передаче сигналов а по каналу с помехами на входе приемника наблюдается вектор 232 z = \zy,...,zf )= a +1 , где ft - вектор шума, компоненты которого -независимые гауссовские величины с нулевым математическим ожиданием и дисперсией NQ/2. Условная плотность распределения вектора z , при т = \ наблюдаемого на выходе канала, имеет вид /(г 14 )= ( оТУ2 ехр{- {z - Е Ц, 4.53) где Е - энергия сигнала, приходящаяся на один бит.

В общем случае порождающая матрица тривиального КПЧ имеет вид G = \jkxkPkxA гДе Ikxk единичная матрица, а Рд.х1 - единичный вектор-столбец. Для подобного кода при невыполнении условий четности исправление ошибки выражается в инвертировании символа, имеющего наименьший МРС [47]. Для получения ПРК из двух тривиальных КПЧ размерности 2D кодер формирует из к векторов-строк квадратную матрицу Ак = tfxozi , ГДО х = \,к, z = \,k и только для данной размерности положим у = 0. Таким образом, для удобства последующих рассуждений матрица Ak рассматривается в плоскости xOz пространственной системы координат. Матрица А путем проверок четности по векторам-строкам и векторам-столбцам преобразуется в матрицу вида Лг=ІГх(ЬІі- Очевидно, что в Ак общее число информационных элементов достигает значения к , тогда как число проверочных разрядов в Ап будет равно r2D =2к + \. Для выявления общих закономерностей формирования избыточных символов ПРК произвольной размерности целесообразно значение г2/) разделить на две составляющие: г =2к, определяющую избыточность по проверкам информационных разрядов, и r jj = 1 (проверка проверок) выражающую избыточность для вектора-столбца и вектора-строки. В последующем избыточность, непосредственно зависящую от проверок информационных разрядов, обозначим символом ). Проверка от проверочных разрядов представим символом «)) . Матричная форма описанного кода имеет вид:

Структура ПРК в 3D образуется при у О, если следом за матрицей pxlzL по координате у дополнительно разместить новую матрицу Ця Ці и так ДО значения у = п -1, а затем на позиции у = п сформировать матрицу проверок всевозможным х и z. Полученная конструкция в пространстве координат х, у и z образует куб из информационных и проверочных элементов (в общем случае прямоугольный параллелепипед), который назовем кадром. Порождающая матрица этого кода определяется кронекеровским произведением матриц G исходных кодов. Введенная в код избыточность (относительная скорость кода) R оценивается соотношением R = Y\vcq/riq)= T\v- ynq) а минимальное кодовое Применяя последовательно это правило несколько раз, можно получить широкий диапазон длин кодов. Например, код размерности 4D получают из п кадров кода 3D, при этом новые проверочные символы формируют соответствующим сложением одноименных матриц размерности 2D, взятых по одной из всех кадров 3D.