Содержание к диссертации
Введение
Глава 1. Псевдослучайные коды 14
1.1. Линейные рекуррентные последовательности 14
1.2. Последовательности максимальной длины 18
1.3. Связь корректирующих и корреляционных свойств псевдослучайных кодов 22
1.4. Симплексные коды максимальной длины 25
1.5. Коды Голда и вновь образованные последовательности 26
1.6. Коды малого семейства последовательностей Касами 32
1.7. Коды большого семейства последовательностей Касами 34
1.8. Выводы 36
Глава 2. Методы цифровой обработки псевдослучайных кодов
2.1. Классификация методов цифровой обработки псевдослучайных кодов 37
2.2. Универсальные методы приема псевдослучайных кодов 38
2.3. Метод полихотомического поиска 42
2.4. Методы ускоренного векторно-матричного умножения 45
2.5. Прием по информационной совокупности 51
2.6. Сравнение методов приема псевдослучайных кодов 51
2.7. Декодирование бинарных блоковых кодов и адресных
последовательностей с помощью быстрых спектральных преобразований 53
2.8. Быстрое декодирование кодов максимальной длины 54
2.9. Быстрое декодирование кодов Голда
2.10. Быстрое декодирование кодов малого семейства Касами 63
2.11. Быстрое декодирование кодов большого семейства Касами 66
2.12. Сравнение сложности методов быстрого декодирования 67
2.13. Выводы 69
Глава 3. Метод быстрого декодирования длинных псевдослучайных кодов 70
3.1. Идеи метода быстрого декодирования 70
3.2. Описание метода быстрого декодирования 73
3.3. Общие понятия о сложности реализации декодирования 77
3.4. Анализ сложности метода быстрого декодирования 82
3.5. Выводы 104
Глава 4. Исследование помехоустойчивости метода быстрого декодирования псевдослучайных кодов 106
4.1. Критерий для оценки и сравнения помехоустойчивости 106
4.2. Потенциальная помехоустойчивость метода БДК 111
4.3. Описание экспериментальной установки 117
4.4. Методика исследования декодера 123
4.5. Оценка погрешности вычислений 127
4.6. Результаты исследования декодера БДК симплексного кода 129
4.7. Результаты исследования декодера БДК кода Голда 136
4.8. Сравнение помехоустойчивости методов МП и БДК 142
4.9. Сравнение результатов исследования с потенциальной
помехоустойчивостью метода БДК 144
4.10. Рекомендации к применению метода БДК 146
4.11. Выводы 147
Заключение 149
Список работ по теме диссертации 151
Список цитируемой литературы
- Связь корректирующих и корреляционных свойств псевдослучайных кодов
- Универсальные методы приема псевдослучайных кодов
- Описание метода быстрого декодирования
- Описание экспериментальной установки
Введение к работе
В диссертации разрабатывается и исследуется новый метод быстрого декодирования длинных псевдослучайных кодов для передачи информации в системах цифровой радиосвязи специального назначения с высокими требованиями к структурной скрытности, конфиденциальности и достоверности информации. Алгоритм базируются на рекурсивной зависимости символов псевдослучайных кодов. В основе алгоритма лежит метод приема линейных рекуррентных последовательностей по информационной совокупности с использованием пассивной согласованной фильтрации и способ мажоритарного решения по нескольким информационным блокам. Рассматриваются алгоритмы для декодирования симплексного кода максимальной длины и кода Годда, которые могут быть без существенного изменения использованы для декодирования кодов малого и большого семейств Касами. Исследуется помехоустойчивость разработанного метода декодирования в двоичном симметричном канале, проведена оптимизация его параметров для канала с вероятностью ошибки на символ 0,1. Рассматриваются также вопросы сложности программно-аппаратной реализации разработанного метода.
Актуальность работы
В настоящее время для повышения помехозащищенности радиосистем передачи информации в условиях радиоэлектронной борьбы используются шумоподобные сигналы (ШПС) с большой базой. Такие сигналы формируются ортогональными и квазиортогональными кодами, длина которых может намного превышать 103 символов. Широкое применение получили квазиортогональные коды максимальной длины, коды Голда, коды малого и большого семейств Касами; все перечисленные коды образуются линейными рекуррентными последовательностями и не редко называются псевдослучайными кодами. Оптимальный корреляционный приемник для ШПС сигналов, осуществляющий процедуру приема "в целом", не всегда реализуем по причине экспоненциальной сложности устройства обработки в функции от длины кода. Для разрешения проблемы сложности используют регенерацию символов принимаемого сигнала (посимвольный прием), а затем обрабатывают полученную кодовую последовательность двоичных символов, используя цифровые схемы. Разумеется, такая схема приема проигрывает по помехоустойчивости
оптимальному приемнику. Этот проигрыш служит платой за упрощение практической реализации схемы приема "в целом" в непрерывном канале.
Проблеме ускоренной цифровой обработки ШПС сигналов с большой базой посвящено много монографий и публикаций. Наибольший вклад в теоретическое развитие этой проблемы внесли Д. Спилкер, Титсворт, Р. Уорд, В. В. Лосев, Л. Е. Варакин, Г. И. Тузов, Н. В. Семаков, В. А. Зиновьев, Г. В. Зайцев, Л. В. Канатова, В. А. Сивов. Однако известные алгоритмы основаны на вычислении корреляционной функции сигнала и выборе наиболее вероятного слова из большого набора разрешенных слов по методу максимального правдоподобия. Один из популярных на сегодняшний день быстрых алгоритмов максимального правдоподобия - это быстрое преобразование над матрицами Адамара. Однако программно-аппаратная реализация этого алгоритма наталкивается на трудности при обработке сверхдлинных кодов в режиме реального времени.
Кодовые ансамбли, которые используются для формирования ШПС сигналов с большой базой, можно рассматривать также как блочные корректирующие коды большой длины. В настоящее время растет интерес и потребность в быстродействующих декодерах для обработки очень длинных кодов (п = 103 -г-1012), так как прогресс в этой области определяет развитие систем спутниковой, космической и наземных видов связи. Это обстоятельство подчеркивает, что применяемые в технике связи алгоритмы коррекции ошибок должны быть максимально упрощены, а поиск простых и эффективных алгоритмов декодирования - актуальная задача в современной теории помехоустойчивого кодирования. Среди последних достижений в этой области хочется отметить заслуги отечественных ученых В. В. Золотарева и Г. В. Овечкина, открывших эффективный метод многопорогового декодирования, развитие которого продолжается в наши дни.
В диссертационной работе изучается проблема высокой сложности процедуры декодирования псевдослучайных кодов большой длины и предлагается новый метод их цифровой обработки, который снимает ограничения на программно-аппаратную реализацию декодера при обработке сверхдлинных кодовых последовательностей. Актуальность работы подтверждена тем, что она выполнялась в рамках проектно-конструкторской деятельности ФГУП СКБ «Радэл» при разработке
аппаратуры радиосвязи, что подтверждено соответствующим актом о внедрении результатов работы.
Цель и задачи диссертационном работы
Целью диссертационной работы является разработка метода быстрого декодирования длинных псевдослучайных кодов с невысокой сложностью программно-аппаратной реализации декодера для передачи информации в цифровых системах радиосвязи специального назначения с высокими требованиями к структурной скрытности, конфиденциальности и достоверности информации; исследование эффективности использования такого метода в дискретном канале; а также оценка реализуемости метода на современных цифровых процессорах. Вычислительная сложность метода декодирования должна быть не хуже nlog2n. Программно-аппаратная реализация декодера должна требовать минимальных ресурсов цифрового процессора, слабо зависящих от длины кодового слова.
Для достижения поставленной цели требуется решить следующие задачи:
— изучить свойства псевдослучайных кодов и известные методы их
декодирования;
-разработать метод быстрого декодирования длинных псевдослучайных кодов с невысокой сложностью декодера;
-реализовать разработанный метод декодирования в виде программной модели;
- исследовать помехоустойчивость разработанного метода с
помощью программной модели.
Объект и предмет исследования
Объект предстоящего исследования - передача информации в цифровых системах радиосвязи специального назначения с высокими требованиями к структурной скрытности, конфиденциальности и достоверности информации. Предмет исследования - поиск методов быстрого декодирования, позволяющих использовать длинные псевдослучайные коды в таких системах.
Методы исследования
При проведении работы использованы методы теории информации и помехоустойчивого кодирования, теории псевдослучайных сигналов, теории вероятности и математической статистики, а также методы компьютерного моделирования. При разработке программ, моделировании и проведении численных расчетов использовались следующие программные продукты: MATLAB 7.0 и Microsoft Visual Studio 2005 (алгоритмические языки C/C++ и С#).
Научная новизна
В процессе исследований и разработок получены следующие новые научные результаты.
Разработан метод приема линейных рекуррентных последовательностей с использованием пассивной согласованной фильтрации с помощью генератора последовательности; показано, что такой метод позволяет реализовать декодер псевдослучайных кодов с логарифмической сложностью в функции от длины кода.
Разработан метод быстрого декодирования длинных псевдослучайных кодов для передачи информации в цифровых системах радиосвязи специального назначения. В основе алгоритма лежит обнаружение с помощью пассивной согласованной фильтрации безошибочного сегмента линейной рекуррентной последовательности и определение информационного блока по найденному сегменту с помощью зеркального генератора последовательности.
а) Оценка сложности метода показала, что при сравнительно
одинаковом с алгоритмом быстрого преобразования Адамара росте
вычислительной сложности программно-аппаратная реализация
предложенного метода требует значительно меньших ресурсов
цифрового процессора, что снимает ограничения на схемотехническую
реализацию декодера при обработке сверхдлинных кодовых
последовательностей.
б) Для симплексного кода максимальной длины (1023, 10) и кода
Голда (1023, 10) путем компьютерного моделирования получены
оптимальные параметры метода по критерию максимума вероятности
правильного декодирования блока при передаче по двоичному
симметричному каналу с вероятностью ошибки на символ 0,1. Для
оптимальных параметров метода построены экспериментальные графики зависимости помехоустойчивости от вероятности ошибки на символ в двоичном симметричном канале, которые представляют большую теоретическую и практическую ценность для анализа помехоустойчивости метода и определения области его применения.
в) Путем компьютерного моделирования установлено, что мажоритарное решение по нескольким информационным блокам, полученным по различным кодовым сегментам, позволяет значительно улучшить помехоустойчивость метода.
Практическая значимость результатов работы
Практическая значимость результатов, полученных в диссертационной работе, заключается в следующем.
Использование разработанного метода декодирования позволяет реализовать декодер псевдослучайных кодов схемотехнически или на цифровых процессорах с ограниченными ресурсами для приема сверхдлинных кодовых последовательностей в режиме реального времени. По сравнению с известными методами, использующими быстрые преобразования над матрицами Адамара для ускоренного декодирования псевдослучайных кодов, при сравнительно одинаковом росте вычислительной сложности разработанный метод снижает сложность декодера в « n/(5 log2 ті) раз, где п - длина кода, а В = 1 + 5, и сокращает емкость запоминающего устройства в а п/В раз.
Разработанная на алгоритмических языках C/C++ и С# программная модель передачи и декодирования псевдослучайных кодов в дискретном канале может быть использована при проектировании цифровых систем связи, а также в учебном процессе по курсу «Теория информации и помехоустойчивого кодирования».
3. Разработанные для метода декодирования программные модули на алгоритмическом языке C/C++ позволяют снизить время проектирования декодера псевдослучайных кодов на цифровых процессорах за счет использования готового программного обеспечения.
Достоверность результатов
Достоверность результатов диссертационной работы подтверждена результатами компьютерного моделирования в среде MATLAB 7.0 и программном пакете, разработанном автором диссертации.
Личный вклад автора
Все основные результаты диссертационной работы, включая положения, выносимые на защиту, получены лично автором диссертации.
Внедрение результатов работы
Результаты диссертационной работы внедрены в виде:
- программной реализации декодера псевдослучайных кодов,
результатов его исследования на программной модели, а также
методики его расчета и моделирования в проектно-конструкторскую
деятельность ФГУП СКВ «Радэл» при разработке аппаратуры
радиосвязи;
- программной модели декодера псевдослучайных кодов в учебный
процесс на кафедре телекоммуникационных систем Московского
государственного института электронной техники (технического
университета) при проведении лекций и лабораторных работ по курсу
«Основы теории информации и помехоустойчивого кодирования»;
что подтверждено соответствующими актами.
Положения, выносимые на защиту
Метод приема линейных рекуррентных последовательностей с использованием пассивной согласованной фильтрация с помощью генератора последовательности.
Метод декодирования длинных псевдослучайных кодов, в основе которого лежит обнаружение с помощью пассивной согласованной фильтрации безошибочного сегмента линейной рекуррентной последовательности и определение информационного блока по найденному сегменту с помощью зеркального генератора последовательности.
Способ мажоритарного решения по нескольким информационным блокам для повышения помехоустойчивости метода декодирования длинных псевдослучайных кодов, основанного на пассивной
согласованной фильтрации линейной рекуррентной последовательности и определении информационного слова по кодовому сегменту без ошибок.
4. Медленный рост сложности декодера псевдослучайных кодов, определяемый как логарифм от длины кодового слова, при использовании метода декодирования, основанного на пассивной согласованной фильтрации линейной рекуррентной последовательности и определении информационного слова по кодовому сегменту без ошибок.
Апробация работы
Основные результаты диссертационной работы представлены и обсуждены на научных семинарах кафедры телекоммуникационных систем Московского государственного института электронной техники и научно-техническом семинаре ФГУП СКВ «Радэл» и 2-х научно-технических конференциях: Всероссийской научно-практической конференции молодых ученых, аспирантов и студентов в рамках Программы «Участник молодежного научно-инновационного конкурса «Электроника 2006-2007» (г. Москва, 2006 г.), 14-ой Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика» (г. Москва, 2007 г.).
Публикации
Результаты диссертационной работы опубликованы в 5 работах. Из них 1 статья в журнале из перечня ВАК «Естественные и технические науки»; 2 статьи в журнале, не входящем в перечень ВАК: «Сборник научных трудов под ред. д. т. н., профессора Баринова В. В. «Методы проектирования и защиты мобильных систем связи» (Изд. МИЭТ), и 2 тезиса в трудах, перечисленных выше российских конференций.
Структура и объем диссертации
Диссертационная работа состоит из введения, 4 глав, заключения и приложения. Она содержит 177 страниц текста, включая 45 рисунков, 23 таблицы, списка используемой литературы из 71 наименований, 5 приложений, включая два акта о внедрении ее результатов.
Связь корректирующих и корреляционных свойств псевдослучайных кодов
ЛРП памяти га, имеющие максимально возможный период рт — 1, играют особую роль в современных информационных технологиях и называются последовательностями максимальной длины или просто М-последовательностями. Будучи полностью детерминированными, они обладают многими свойствами, присущими случайным последовательностям типа последовательности исходов подбрасывания правильной монеты. Следующие замечательные свойства являются ключевыми для понимания ценности М-последовательностей в плане построения кодов с хорошей автокорреляцией [23].
Возможны лишь две взаимоисключающие ситуации. Предположим вначале, что сдвиг I равен целому числу периодов L. Тогда щ = а1+1 и а ; = 0 для всех і, т.е. последовательность, описываемая (1.9), состоит из одних нулей.
Пусть теперь / не кратно L. Тогда at и а1+г не могут совпадать для всех і = ОД, ...,L — 1 . поскольку сдвинутая копия может полностью повторить исходную последовательность только при сдвиге, кратном периоду, что противоречит предположению. Тогда очевидно, что рекурсия (1.9), полностью повторяющая (1.2), генерирует некоторую ненулевую последовательность. Однако, согласно предыдущему свойству, если рекурсия (1.2) генерирует М-последовательность, стартуя с некоторого определенного начального состояния, то никакой другой непулевой последовательности, кроме сдвинутой копии той же самой М-последовательности, она при другом начальном состоянии сгенерировать не может. Мы, таким образом, приходим к заключению: поэлементное вычитание двух сдвинутых копий одной и той же М-последовательности дает либо нулевую последовательность, если взаимный сдвиг кратен периоду, либо некоторую новую сдвинутую копию исходной М-последовательности в противном случае. Для двоичных последовательностей вычитание равносильно сложению, благодаря чему рассмотренное свойство нередко упоминается как свойство сдвига и сложения.
Очевидно, для генерирования р-ичной М-последовательности, т.е. ЛРП с максимальным периодом, возможным для фиксированной памяти т (а не некоторой последовательности меньшей длины), требуется специальный подбор коэффициентов gt в рекурсии (1.2). Для того, чтобы ЛРП была М-последовательностью. необходимо и достаточно, чтобы характеристический многочлен (1.3) схемы генерации М-последовательности был примитивным полиномом над полем GF(p) . Примитивные полиномы составляют подкласс неприводимых полиномов. Полином д{х) степени т над полем GF(p) (т.е. с коэффициентами из GF(p)) называется неприводимым над GF(jp), если его нельзя представить как произведение двух полиномов степени, меньшей т. Подобным полиномам в множестве всех полиномов принадлежит та же роль, что простым числам в множестве целых. Не каждый неприводимый полином примитивен, хотя. к примеру, в частном случае р = 2 и простого 2т — 1 все неприводимые полиномы примитивны. С доказательством необходимости и достаточности вышеуказанного выбора коэффициентов в рекурсии (1.2) для генерирования р-ичной М-последовательности можно ознакомиться в [24, 25].
Примитивные полиномы подробно табулированы в ряде руководств по современной алгебре и теории кодирования, а также (в основном для р = 2) в некоторых книгах по широкополосной связи [25-28]. Не составляет труда и их поиск с помощью компьютера. Соответствующие команды, в частности, имеются в среде MATLAB (см. Communications Toolbox).
Каждому примитивному полиному соответствует вполне определенная М-последовательность. Соответственно число различных М-последовательностей памяти т равно числу примитивных многочленов степени т, которое для GF(2) определяется как Q = ср(2т — 1)/т, где (p(N) - функция Эйлера в теории чисел, равная количеству целых чисел, включая единицу, меньших числа N взаимно простых с ним [29]. В Табл. 1.1 приведены значения Q для некоторых т.
Число различных проверочных многочленов М-последовательностей т 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Q 1. 1 2 2 6 6 18 16 48 60 176 144 630 756 1800 Рассмотрим бинарную М-последовательность {aj памяти т, т.е. длины L = 2т — 1. Отобразим ее символы 0 и 1 в бинарный алфавит ±1 согласно правилу .=(-«"={X х=г. (1Л0) где при возведении -1 в степень at последняя величина формально трактруется как действительно число 0 или 1. Полученная таким образом последовательность {bj действительных бинарных символов ±1 обладает периодом N = L = 2т — 1 и является взаимно-однозначным отображением исходной М-последовательности {aj. Представляется естественным сохранить за ней то же самое наименование бинарной М-последовательности. Для устранения риска перепутывания можно при необходимости использовать дополнительную маркировку типа «бинарная {+1} последовательность» или «бинарная {0,1} последовательность». Найдем ненормированную периодическую автокорреляционную функцию (ПАКФ) последовательности {bj:
Воспользуемся теперь свойством сдвига и сложения бинарных {0,1} последовательностей. Суммирование в показателе степени здесь можно выполнить по модулю 2. так как это даст тот же итог возведения в степень, что и обычное арифметическое сложение. При этом {a J = {a + aj_ J окажется {0,1} М-последовательностью периода L при т Ф 0 mod L или последовательностью из одних нулеіі в противном случае. В силу уравновешенности при т = 0 mod N на одном периоде {a J = {a + а } содержится L0 = 2т 1 — 1 нулей и Ьг = 2771-1 единиц, поэтому сумма (1.11) состоит из L0 положительных и L-L отрицательных единиц, давая в итоге
Последовательности, удовлетворяющие соотношению (1.12) при N = 4/i — 1, где h - целое, обладают теоретически минимальным уровнем боковых лепестков ПАКФ для бинарных кодов нечетной длины. Такие последовательности называются минимаксными. Таким образом, бинарные М-последовательности имеют двухуровневую ПАКФ и относятся к числу минимаксных.
Универсальные методы приема псевдослучайных кодов
В данном и последующих параграфах рассмотрим известные методы цифровой обработки сложных сигналов, которые образуются с помощью ПС кодов. Будем считать сигнал определенным в дискретных точках временной оси, что соответствует наличию тактовой синхронизации. Основное внимание уделяется дискретном} по амплитуде каналу с символами 0,1 (или 1, -1), что соответствует приемнику с первой решающей схемой, в которой эти символы отождествляются со значениями субэлементов составного сигнала. Причем вопросы декодирования и синхронизации будем рассматривать в одном контексте, так как синхропоследовательность можно рассматривать как циклический корректирующий код. Отсюда следует, что задача определения фазы последовательности сводится к задаче декодирования кода, словами которого являются все циклические перестановки синхропоследовательности. И, наоборот, определение фазы синхропоследовательности решает задачу декодирования кода.
Известные методы приема ПС кодов (определение начальной фазы синхропоследовательности в случае синхронизации или информационной последовательности в случае декодирования) можно разбить на две группы: универсальные и специфические. К универсальным относятся методы, не зависящие от вида сигнала, к специфическим - методы, основанные на использовании определенных закономерностей в структуре сигнала. Проверка таких закономерностей возможна, как правило, сравнительно простыми техническими средствами, что делает методы этой группы довольно простыми, но ограниченными по применению. Сущность всех универсальных методов заключается в вычислении взаимно корреляционной функции приходящего и опорного сигналов и определении точки максимума. Характерной чертой вычислительного процесса является инвариантность к виду сигнала. Прямые методы вычисления соответствуют шаговому поиску, косвенные методы используют преобразования типа свертки с быстрыми алгоритмами счета, когда корреляционная функция Rr вычисляется при помощи двукратного преобразования Фурье: Rr = п Т СГХ х 77/) = (го.п г У (2.1) где X — входной сигнал, Н — опорная последовательность, Т — оператор обобщенного преобразования Фурье, п - длина последовательности. Достоинством этого способа является возможность использования для обработки любого периодического сигнала. К недостаткам следует отнести сравнительно большие вычислительные затраты, обусловленные двукратным вычислением преобразования (считывается, что произведение ТН может быть вычислено заранее).
Методы, основанные на использовании структурных свойств сигнала можно разбить на две группы. К первой группе отнесем методы, которые, как и раньше, вычисляют корреляционные функции принятого сигнала с набором опорных, представляющих все фазы исходной последовательности. Это полихотомический поиск и методы прямого умножения на матрицу фазовых сдвигов синхропоследовательности. Ко второй группе относятся методы, в которых опорная последовательность синтезируется по принятому сигналу, а корреляционная функция вычисляется с целью проверки правильности синтеза в точке предполагаемого максимума. Это методы синхронизации по информационной совокупности.
Простейшим способом определения фазы псевдослучайной кодовой последовательности является шаговый поиск. Он заключается в следующем. В месте приема формируется копия передаваемого сигнала, называемая опорным сигналом. Выбирается некоторая фаза опорного сигнала и вычисляется корреляция опорной и приходящей последовательностей. Если фаза опорного сигнала совпадает с фазой приходящего, то значение корреляционного интеграла (в данном случае - сумма) превышает некоторый порог. При несовпадении фаз, превышения порога не происходит. В этом случае следует взять новое значение фазы опорного генератора и повторить испытание.
Шаговый поиск реализуется достаточно просто и сводится к анализу точек области неопределенности последовательно или параллельно-последовательно в заранее выбранном порядке или путем случайного зондирования. Существует много разновидностей шагового поиска, основными из которых являются поиск с фиксированным объемом выборки, с задержанным решением, с последовательным анализом, многоэтапный поиск. Эти и другие разновидности шагового поиска описаны в работах [42-45].
С точки зрения спектрального подхода шаговый поиск заключается в разложении принятого сигнала по базису, состоящему из всех циклических сдвигов исходной последовательности. Количество подлежащігх анализу спектральных коэффициентов равно длине сигнала, а вычисление коэффициентов производится последовательно путем корреляции приходящего и опорного сигналов. Результаты вычислений, выполненных на предыдущих шагах, либо вообще не используются в дальнейшем, либо используются, но довольно слабо (многоэтапный поиск).
Если вероятность ошибки (пропуска или ложной тревоги) близка к нулю, то среднее время шагового поиска одноканальным коррелятором равно где Т — время анализа одной точки области неопределенности, Pt - априорная вероятность поступления на вход приемника фазового сдвига с номером і. При равномерном распределении фазы поиск заканчивается в среднем через п/2 шагов. Например, если п = 215, длительность субэлемента составного сигнала т0=1 мкс, а интервал анализа на каждом шаге поиска равен периоду последовательности, то среднее время поиска п2 т0/2 = 536,9 с 9 мин, что может превышать длительность что может превышать длительность сеанса связи современных радиотехнических систем.
На вычисление одной точки корреляционной функции затрачивается п — 1 сложений ип умножений. Поэтому общий объем вычислении пропорционален п2. С формальной точки зрения алгоритм шагового поиска соответствует построчному умножению вектора-сигнала на матрицу циклических сдвигов синхропоследовательности. Характерный для этого алгоритма квадратичный рост объема вычислений, вызванный низкой эффективностью вычислительного процесса, приводит к относительно большому времени поиска.
В сверточных методах все точки области неопределенности анализируются одновременно. Хотя базис разложения по-прежнему состоит из всех циклическітх перестановок синхропоследовательности, одновременный анализ всех фаз позволяет исключить повторение значительного количества арифметических операций и увеличить эффективность вычислительного процесса. В результате число операций, приходящихся на одну точку области неопределенности, снижается с п до log2 п. Платой за это является увеличение памяти и сложности устройства поиска. Время поиска
Описание метода быстрого декодирования
Для поиска чистого отрезка можно использовать зависимость кодовых символов (1.5). Каждый символ кодовой последовательности определяется линейной рекурсией из 771 предыдущих символов, часть этих символов или все символы участвуют в формуле расчета, которая задается в (1.6) проверочным многочленом д(Х) . Рассмотрим сегмент кодового слова шириной L = m+j символов. Каждый из последних У символов сегмента может быть предсказан по закону д{Х) по предыдущим символам, причем в случае отсутствия канальных ошибок символы сегмента и их предсказания совпадают. Таким образом, последние j символов сегмента могут быть проверены с помощью предшествующих символов, причем при наличии ошибок некоторые проверки покажут нарушение зависимости между символами, что может послужить критерием различения чистых и зашумленных сегментов. Такой критерий и взят за основу метода БДК.
Для определения местоположения чистого отрезка в методе БДК будем использовать поиск в слове а сегмента из L т + J безошибочных символов, будем называть такой сегмент чистым сепментом шириной L. Причем последние 771 символов такого сегмента будем использовать для восстановления символов кодового слова и соответственно декодирования символов информационной последовательности, a j = L —т символов - для проверки достоверности символов сегмента. Очевидно, чем больше порог / глубины проверок j, тем достовернее метода БДК отличает чистые кодовые сегменты от сегментов, содержащих канальные ошибки.
Для предсказания и проверки (т + 2)-ого символа можно выбрать ближайшие т символов, принятые до него, то есть а 2 , а 3 ...., а т+1 . Если сх +г = д{.ос 2,а3,...,ат+1) считаем, что чистый кодовый сегмент продолжается. Процедуру поиска продолжается, пока совпадают символы и их предсказания и не достигнут конец слова а . Теперь, если на (/ + 1) шаге встретилось первое несовпадение а +;+1 g{ct m+j_m,a!rn+j_m+1,...,alni+ ), можно предположить, что чистый сегмент закончился, а символ a m+j+1 содержит канальную ошибку. На этом поиск чистого сегмента можно закончить и считать, что сегмент осі, ос2,..., c - m+j шириной L = т. + j не содержит ошибок. Однако такое решение будет ложным, если канальные ошибки не нарушат указанные j проверок, основанные на сравнении канального символа и его предсказания. Вероятность ложного решения уменьшается с увеличением глубины проверок у, поэтому для достоверного обнаружения чистого сегмента, можно задаться нижним порогом/ глубины проверок. Достижение или превышение порога будет свидетельствовать о вероятном обнаружении чистого сегмента. Будем называть доверительным сегмент, удовлетворяющий порогу, то есть для которого j J. Если глубина проверок найденного сегмента не достигает выбранного порога, процедуру поиска доверительного сегмента можно продолжить пока не будет достигнут конец кодового слова.
Процедуру поиска чистого сегмента можно завершить до окончания приема кодового слова, как только найден первый доверительный сегмент. Однако в этом случае не будет использована полностью избыточность ПС кода. На длине кодового слова при определенной конфигурации ошибок е может быть несколько чистых сегментов разной ширины. Каждый из них можно использовать для декодирования. В связи с этим представляется целесообразным производить поиск доверительных сегментов на всей длине слова. Встает вопрос, как можно использовать совместно несколько доверительных сегментов для декодирования. Самым простым решением в данном случае может быть мажоритарное решение. Это последняя идея, которая была использована при разработке метода БДК.
Рассмотрим, как можно использовать мажоритарное решение по нескольким доверительным сегментам. Напомним, что по т символам кодового слова, можно восстановить все остальные. Тогда, если из каждого найденного доверительного интервала выбрать т. символов для декодирования и на их основе получить первые символов кодового слова, можно применить методы мажоритарного декодирования, когда решение по символу выносится по принципу большинства. На основе нескольких решений, полученных для первых символов кодовой последовательности, можно таким образом сформировать более достоверное решение и использовать его для декодирования.
На этом завершим обсуждение идей, послуживших основой для разработанного метода, и перейдем к обсуждению их технической реализации.
Идеи, изложенные в предыдущем параграфе, послужили основой для разработки метода быстрого декодирования длинных кодов Голда, описанного в статье [59]. Здесь дадим его общее определение применительно к декодированию любых ПС кодов, образованных ЛРП, и в следующих параграфах проведем детальный анализ сложности реализации декодирования по методу БДК.
Будем считать, что для кодирования используется т - разрядный кодирующий регистр (см. Рис. 1.2). Содержимое кодирующего регистра на произвольном сдвиге кодирования (когда включена обратная связь) будем называть фазой кода, а содержимое в начальный момент времени — начальной фазой кода. В начальной фазе кода младшие к т разрядов соответствуют информационным символам, а остальные разряды, число которых равно h = rule, соответствуют начальной установке. Для описания процедуры декодирования воспользуемся структурной схемой декодера БДК, изображенной на Рис. 3.1.
Метод БДК выполняет процедуру декодирования ПС кода в соответствие с перечисленными ниже шагами.
Принятое из канала кодовое слово а подается посимвольно на согласованный цифровой фильтр (см. Рис. 3.1). Согласованный фильтр представляет собой кодирующий регистр (см. Рис. 1.2) с выключенной обратной связью, вход и выход которого замкнуты на полусумматор. Отклик согласованного фильтра на ПС слово без ошибок после приема первых т символов — есть нулевая последовательность. Такой фильтр выполняет процедуру пассивной согласованной фильтрации принятого слова и может использоваться для приема ПС последовательности (например, для быстрого входа в синхронизм).
Описание экспериментальной установки
Напомним, что метод БДК предназначен для декодирования кодов, образованных ЛРП. Рекурсивная зависимость символов ЛРП позволяет по отрезку из т безошибочных символов кодового слова восстановить целиком все кодовое слово, где т — память кода. Метод БДК основан на поиске в кодовом слове, принятом из канала с ошибками, сегмента из L = m + J безошибочных символов, будем называть такой сегмент чистым окном шириной L. Причем т символов чистого окна используются для восстановления кодового слова и декодирования т символов информационной последовательности, a J символов используются для проверки первых т символов чистого окна. Очевидно, чем больше глубина проверки J , тем достовернее метод БДК отличает чистые окна от кодовых сегментов, содержащих канальные ошибки. Однако увеличение глубины проверки, снижает возможность найти чистое окно на длине кодового слова. Таким образом, возникает задача достижения компромисса между достоверностью обнаружения чистого окна и возможностью найти такое окно в кодовом слове.
Рассмотрим случаи, которые могут привести к ложному декодированию при использовании метода БДК.
1. Если при определенной реализации канальных ошибок в кодовом слове апостериори отсутствует чистое окно шириной т, метод БДК в идеальном случае должен выдавать отказ от декодирования, так как в описанной ситуации отсутствует возможность правильно декодировать принятое слово. В этом случае положительное решение декодера БДК о наличии чистого окна всегда приводит к ложному декодированию.
2. Рассмотрим ситуацию, когда в канальном слове присутствует чистое окно шириной не менее т символов. В этом случае существует возможность правильного декодирования, однако встает задача правильного выбора т безошибочных символов для декодирования. Так как декодер БДК принимает решение о наличии чистого окна по J проверкам, отсутствие апостериори такого окна шириной L-m + J всегда приводит к ложному решению о его наличии. В этом случае, существует вероятность ошибки в выбранных для декодирования т символах, что приводит к ложному декодированию. Если же апостериори есть чистое окно шириной не менее L — m + J символов, решение декодера БДК о его наличии может быть правильным.
Таким образом, приходим к выводу, что возможность правильного декодирования кодового слова, практически полностью определяется наличием чистого окна из L = m + J и более символов в кодовом слове.
Теперь, если рассмотреть идеальный декодер БДК, который при заданном уровне канальных ошибок всегда правильно обнаруживает чистое окно шириной L = m + J символов и всегда выдает отказ от декодирования, если такого окна нет, можно считать, что вероятность Рп„ правильного декодирования определяется вероятностью события А={"В канальном слове есть хотя бы одно чистое окно шириной L или более символов"}. Это и будет потенциальной помехоустойчивостью декодера БДК. Для реального декодер БДК существует вероятность Рдож ложного обнаружения чистого окна, что приводит к ложному декодированию и снижает помехоустойчивость метода. Вероятность Рдож определяется глубиной проверок J и законом таких проверок, то есть схемой конкретного декодера БДК. Аналитическое изучение зависимости Рлож от схемы декодера БДК представляется затруднительным, поэтому автор исследовал такую зависимость с помощью компьютерного моделирования декодера в ДСК. Для сравнения результатов моделирования с потенциальными возможностями декодера БДК автором была выведена аналитическая фордгула. определяющая нижнюю границу вероятности блоковой ошибки декодирования в ДСК. При этом под блоковой ошибкой декодирования подразумевались события, связанные с отказом от декодирования (вероятность Ротк) и ложным декодированием кодового блока (вероятность Рдож ) Для идеального декодера БДК ложное декодирование отсутствует (Рлож = 0). Дальнейшие рассуждения при выводе формулы потенциальной помехоустойчивости основаны на положения теории вероятности [65].
Нижнюю границу Qmin вероятности блоковой ошибки декодера БДК можно оценить блоковой ошибкой идеального декодера БДК. Тогда, если вероятность события А равна Рд, по формуле полной вероятности событий получаем:
Начнем перебор всех различных групп исходов G EJ , которые приводят к наступлению события А. Пронумеруем группы Ggj, начиная с индекса j - 0. В качестве GE,0 рассмотрим чистое окно ширины L в начале кодового слова (то есть, первые L символов приняты без ошибок, и не важно, как приняты все остальные символы). Тогда GE,0 = ipLxn-L} дальнейшем, если вектор GE содержит элементы х в конце, будем удалять их из краткой записи GE и подразумевать, что они там есть. Следующие L групп выберем по закону GE,J =(X/-I10L) (ТО есть? не важно, как приняты первые j— \ символов кодового слова, после которых следует одиночная ошибка в j - ом символе; за ошибкой следует L безошибочных символов и не важно, как приняты все последующие символы). Не трудно убедиться, что исходы каждой такой группы GEJ отличаются от исходов всех предыдущих групп как минимум в j-ом символе. Группы (рЕ,\) С индексами j Lпостроим по закону GEJ =(а/10/Л, где вектор a І =(еіЄ2-"е/-1/ определяет конфигурации ошибок в первых (/-і) символах кодового слова. Вектор а ; выбирается так, чтобы группа GEJ не содержала в себе исходы, рассмотренные в предыдущих группах. Другими словами каждый исход группы GEJ должен отличаться как минимум в одном символе от любого исхода из объединения GE,0 +GE,l GEJ-1 всех предыдущих групп. Не трудно убедиться, что исходы каждой группы GEJ отличаются от исходов L предыдущих групп как минимум в у-ом символе. Однако при определенном выборе а у исходы GEJ могут совпасть с исходами из объединения GE,0 +GE,1 +.... + GEJ-L-1 первых (j-L) групп. Отсюда следует, что вектор а; должен содержать конфигурации ошибок в первых в _/ —1 символах кодового слова, взятые из объединения GEJ-L +GEJ-L+1 + --- + GEJ-1 предыдущих L групп. Построенная по такому закону группа GEJ соответствует конфигурациям ошибок, для которых чистое окно шириной L не наблюдается в первых j символах кодового слова, и возникает, начиная с j +1 -го символа. Не трудно убедиться, что последней группой GEJ, исходы которой могут привести к наступлению события А, будет группа с номером j = n-L . Рассмотренное правило построения групп GEJ позволяет осуществить полный перебор всех реализаций вектора ошибок, приводящих к наступлению события А . Правило выбора вектора аі=(е\Є2—Єі—\) для группы GEJ =\аЛь) можно выразить аналитически через рекуррентную последовательность а = a\,a2---;dyj—l, , элементы которой связаны правилом (4.24):
