Способ быстрого декодирования длинных псевдослучайных кодов на основе линейных рекуррентных последовательностей Перцев, Леонид Викторович

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

Введение

ГЛАВА1. Псевдослучайные коды 13

1.1 Линейные рекуррентные последовательности 13

1.2 Последовательности максимальной длины 17

1.3 Связь корректирующих и корреляционных свойств ПС кодов 21

1.4 Симплексные коды максимальной длины 23

1.5 Коды Голда 24

1.6 Коды малого семейства последовательностей Касами 29

1.7 Коды большого семейства последовательностей Касами 32

Выводы

ГЛАВА 2. Методы декодирования псевдослучайных кодов

2.1 Классификация методов цифровой обработки псевдослучайных кодов 35

2.2. Универсальные методы приема псевдослучайных кодов 36

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

2.4 Прием псевдослучайных кодов методами ускоренного векторно-матричного умножения 44

2.5 Синхронизация по информационной совокупности 51

2.6 Сравнение методов приема псевдослучайных кодов 52

2.7 Декодирование бинарных блоковых кодов и адресных последовательностей с помощью быстрых спектральных преобразований 54

2.8 Декодирование кодов максимального периода с помощью быстрого преобразования Адамара 56

2.9 Декодирование кодов Голда с помощью быстрого преобразования Адамара

2.10 Декодирование кодов малого семейства Касами 66

2.11 Декодирование кодов большого семейства Касами 70

2.12 Сравнение сложности различных реализаций быстрого корреляционного декодирования 71

Выводы 73

ГЛАВА 3. Метод декодирования длинных псевдослучайных кодов 74

3.1 Идеи метода быстрого декодирования 74

3.2 Описание метода быстрого декодирования 77

3.3 Общие понятия о сложности реализации декодирования

3.4 Анализ сложности метода быстрого декодирования 88

Выводы 107

ГЛАВА 4. Исследование помехоустойчивости метода быстрого декодирования 109

4.1 Критерий для оценки и сравнения помехоустойчивости 109

4.2 Описание проводимого исследования 114

4.3 Описание экспериментальной установки 116

4.4 Описание эксперимента 119

4.5 Расчет погрешности вычислений 121

4.6 Результаты исследования декодера БДК симплексного кода 124

4.7 Результаты исследования декодера БДК симплексного кода 13 8

4.8 Сравнение помехоустойчивости методов МП и БДК 148

4.9 Рекомендации к применению 150

Выводы 152

Заключение 153

Список работ по теме диссертации 154

Список цитируемой литературы

• Симплексные коды максимальной длины
• Декодирование кодов максимального периода с помощью быстрого преобразования Адамара
• Общие понятия о сложности реализации декодирования
• Результаты исследования декодера БДК симплексного кода

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

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

Кодовые ансамбли, которые используются для формирования ШПС сигналов с большой базой, можно рассматривать также как блочные корректирующие коды большой длины. В настоящее время растет интерес и потребность в быстродействующих декодерах для обработки очень длинных кодов (п = 10³ ^ 10¹²), так как прогресс в этой области определяет развитие систем спутниковой, космической и наземных видов связи. Это обстоятельство подчеркивает, что применяемые в технике связи алгоритмы коррекции ошибок должны быть максимально упрощены, а поиск простых и эффективных алгоритмов декодирования - актуальная задача в современной теории помехоустойчивого кодирования.

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

Цель и задачи работы

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

Для достижения поставленной цели необходимо решить следующие задачи:

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

2. Исследовать помехоустойчивость разработанного метода при воздействии аддитивного белого гауссовского шума и непрерывной хаотической импульсной помехи.

3. Реализовать разработанный метод в виде программной модели.

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

Проводимые исследования основываются на методах и математическом аппарате теории информации и помехоустойчивого кодирования, теории вероятностей, статистической радиотехники и математической статистики. Для моделирования и проведения численных расчетов использовались программные пакеты MATLAB7.6 и MS Excel 2007.

Научная новизна диссертационной работы

Научная новизна состоит в следующем:

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

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

   производить декодирование псевдослучайных кодов по сегменту длины много меньшей длины кодового слова: 1) поиск «чистого» отрезка импульсной характеристики приемного согласованного фильтра содержащей m+1 нулей; 2) поиск импульсной реакции приемного согласованного фильтра; 3) по совместному поиску «чистого» сегмента и импульсной реакции. Эти способы позволяют реализовать декодер с вычислительной сложностью в nlog₂ (п) /L раз меньшей вычислительной сложности декодера, на основе быстрого преобразование над матрицами Адамара.

   3. 3. Разработанный метод быстрого декодирования на основе пассивной согласованной фильтрации позволяет сократить емкость запоминающего устройства в n раз.

      4. Для симплексных (n,k) кодов с параметрами (2¹³ — 1,13) и (2⁴² — 1,42) найдены оптимальные параметры длины сегмента вынесения решения для декодирования при передаче по двоичному симметричному каналу.

      5. Разработанный метод за счет вынесения решения на неполной

      длине выигрывает по отношению — перед классическим приемом в

      N о

      канале ДСК.

      3. 6. Одновременное воздействие в канале шумовой и непрерывной хаотической импульсной помехи приводит к ухудшению корректирующей способности кода (блоковой вероятности ошибки) всего лишь в 2-3 раза по сравнению со случаем воздействия только шумовой помехи.

         Достоверность полученных результатов

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

         Личный вклад автора

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

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

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

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

         3. 6. 1. По сравнению с известными методами, использующие быстрые преобразования над матрицами Адамара, разработанный метод снижает вычислительную сложность декодера в « nlog₂ (n)/L раз, где п - длина кода, а L << п, и сокращает в «п раз емкость запоминающего устройства.

               2. Появление хаотической импульсной помехи в канале ухудшает корректирующие характеристики декодера всего в 2-3 раза, что свидетельствует об устойчивости предложенного алгоритма к воздействию шумов типа ХИП.

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

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

               Внедрение результатов работы

               Результаты исследования внедрены в учебном процессе кафедры телекоммуникационных систем Национального исследовательского университета МИЭТ при проведении лекций и лабораторных работ по курсам «Основы теории информации и помехоустойчивого кодирования», «Проектирование модемов», «Встраиваемые системы реального времени для ТКС», а также в ОКР ОАО «Радиотехнический институт имени академика А.Л. Минца».

               Апробация работы

               Результаты работы докладывались и обсуждались на научных семинарах кафедры телекоммуникационных систем Национального исследовательского университета МИЭТ и на 3 -х научно-технических конференциях: 16-ой Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика» (г.Москва, 2010 г.), 13-ой Международной конференции

               «Цифровая обработка сигналов и ее применении - DSPA'2011» (г.Москва, 2011г.), 14-ой Международной конференции «Цифровая обработка сигналов и ее применении - DSPA'2012» (г.Москва, 2012г.).

               Публикации

               Основные результаты диссертации изложены в 11 работах. Из них 4 статьи в изданиях из перечня, рекомендованного ВАК.

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

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

                        2. Три способа обнаружения безошибочного сегмента линейной рекуррентной последовательности позволяющие реализовать декодер с вычислительной сложностью в nlog₂ (п) /L раз меньшей вычислительной сложности декодера на основе быстрого преобразование над матрицами Адамара.

                        3. Энергетическая эффективность разработанного метода вынесения решения на неполной длине (выигрыш по отношению —

                        N о

                        перед классическим приемом в канале ДСК).

                        3. 6. 4. 4. Высокая помехоустойчивость декодирования в сложной помеховой обстановке. (Воздействие в канале шума и непрерывной хаотической импульсной помехи приводит к ухудшению корректирующей способности кода только в 2-3 раза.)

                                 5. Предельно низкая вычислительная и логическая сложность декодирования (L - вычислительная сложность, 3log₂п - логическая сложность).

                                 Структура и объем диссертации

                                 Диссертационная работа состоит из введения, 4 глав, заключения и приложения. Она содержит 166 страниц текста, включая 58 рисунков, 15 таблиц, список используемой литературы из 52 наименований, 1 приложения.

                                 Симплексные коды максимальной длины

                                 Примитивные полиномы подробно табулированы в ряде руководств по современной алгебре и теории кодирования, а также (в основном для р=2) в некоторых книгах по широкополосной связи [11-14]. Не составляет труда и их поиск с помощью компьютера. Соответствующие команды, в частности, имеются в среде MATLAB.

                                 Каждому примитивному полиному соответствует вполне определенная М-последовательность. Соответственно число различных М-последовательностей памяти т равно числу примитивных многочленов степени т, которое для GF(2) определяется как Q = (р(2т — 1)/т, где (p(N) - функция Эйлера, в теории чисел, равная количеству положительных целых чисел, включая единицу, меньших числа N и взаимно простых с ним [15]. Ниже приведены значения Q для некоторых т.

                                 Рассмотрим бинарную М-последоватьельность [щ] памяти т, т.е. длины L = 2т — 1. Отобразим ее символы 0 и 1 в бинарный алфавит ±1 согласно правилу где при возведении -1 в степень а.1 последняя величина формально трактуется как действительно число 0 или 1. Полученная таким образом последовательность {Ь{) действительных бинарных символов ±1 обладает периодом N — L = 2т — 1 и является взаимно-однозначным отображением исходной М-последовательности {а }. Представляется естественным сохранить за ней то же самое наименование бинарной М-последовательности. Для устранения риска перепутываения можно при необходимости использовать дополнительную маркировку типа «бинарная {±1} последовательность», или «бинарная {0,1} последовательность». Найдем ненормированную периодическую автокорреляционную функцию (ПАКФ) последовательности {bj:

                                 Яр(0 = ЙГоЧ -г = 2Й(-1)а (-1) - = Й=о(-1)аі+аі- (1.8) Воспользуемся свойством сдвига и сложения бинарных {0,1} последовательностей. Суммирование в показателе степени здесь можно выполнить по модулю 2, так как это даст тот же итог возведения в степень, что и обычное арифметическое сложение. При этом {dj = [at + aj_J окажется {0,1} М-последовательностыо периода L при тФОтосИ или последовательностью из одних нулей в противном случае. В силу уравновешенности при m O mod N на одном периоде {dj = [щ + аг_г} содержится L0 = 2m_1 — 1 нулей и = 2m_1 единиц, поэтому сумма (1.8) состоит из L0 положительных и Lt отрицательных единиц, давая в итоге

                                 Последовательности, удовлетворяющие соотношению (1.9) при N = Ah — 1, где h - целове, обладают теоретически минимальным уровнем боковых лепестков ПАКФ для бинарных кодов нечетной длины. Такие последовательности называются минимаксными. Таким образом, бинарные М-последовательности имеют двухуровневую ПАКФ и относятся к числу минимаксных.

                                 Дискретные сигналы, основанные на бинарных М-последовательностях чрезвычайно популярны в современных информационных системах благодаря оптимальным периодическим корреляционным свойствам и простоте формирования и обработки. В числе наиболее наглядных примеров их практического применения можно упомянуть 2G стандарт мобильной связи cdmaOne(IS-95), в котором М-последовательности различной длины используются как пилот-сигналы начальной синхронизации и зондирования канала, а также коды мультиплексирования сигналов базовых станций и скремблирования данных. Помимо этого М-последовательности служат базисом для формирования других важных семейств сигналов (Касами, Голда и др.).

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

                                 Одним из популярных методов оценки корректирующей способности блоковых (п,к) кодов является число Т ошибок (или по другому кратность исправляемых ошибок), которое гарантировано исправляется на длине п кодового блока. Такая оценка хорошо описывает корректирующие свойства эквидистантных кодов при декодировании по методу максимального правдоподобии (МП). Эквидистантными называются блоковые коды, все пары слов которых равноудалены друг от друга, и расстояние между ними равно минимальному расстоянию кода dmin. Ансамбль таких слов, также называют симплексным кодом. Решение по методу МП принимается в пользу кодового слова, которое наиболее близко (в смысле Евклидома расстояния) к принятому канальному слову. В этом случае число ошибок Т, которое гарантированно исправляет код, определяется минимальным расстоянием кода из соотношения: dmin = 2T+l (1.10) Если число ошибок t в кодовом слове превышает порог Т, то после декодирования с высокой вероятностью получается кодовое слово, отличное от исходного слова. В этом случае можно утверждать, что код не исправляет число ошибок, большее порога Т. Тогда вероятность неправильного декодирования кодового блока (вероятность блоковой ошибки) практически полностью поределяется вероятностью появления t Т ошибок в кодовом слове.

                                 Декодирование кодов максимального периода с помощью быстрого преобразования Адамара

                                 На рисунок 2.7 приведена схема процесса с повышающейся тактовой частотой [32]. Блок задержки каждой ступени задерживает сигнал на п/2 тактов. Тактовая частота первой ступени совпадает с частотой поступления значений входного сигнала, а в каждой последующей ступени тактовая частота увеличивается вдвое. Устройство работает в соответствии с графом, показанным на рисунок 2.4. Арифметическое устройство АУ производит одновременно суммирование и вычитание значений сигнала со входа и выхода блока задержки. Вентильное устройство ВУ работает с частотой в два раза большей, чем тактовая частота блока задержки, и выдает на вход следующей ступени преобразования последовательно значения суммы и разности. Это требует увеличения тактовой частоты последующей ступени вдвое по сравнению с предыдущей. После поступления п отсчетов входного сигнала все п коэффициентов преобразования будут вычислены.

                                 На рисунке 2.8а показан процессор последовательно-параллельного типа, состоящий из разветвленных ступеней преобразования [33]. Число блоков в каждой последующей ступени увеличивается вдвое по сравнению с предыдущей. Блок преобразования состоит из элемента задержки ЭЗ и арифметического устройства АУ. Длина элемента задержки первой ступени равна единице и увеличивается вдвое в каждой последующей ступени. Схема реализует граф, показанный на рисунке 2.86, т.е. вычисляет коэффициенты, упорядоченные по Уолшу, когда строки матрицы Адамара располагаются в порядке возрастания числа перемен знака. Время вычисления всех коэффициентов такое же, как и в предыдущем устройстве.

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

                                 При большой длине М-последовательности обработка, как правило, производится процессором последовательного типа (рисунке 2.5). Современные микросхемы позволяют создать компактные запоминающее устройство большой емкости (216 слов и более) и арифметическое устройство большой разрядности (8 разрядов и более). Для повышения быстродействия можно распараллелить вычислительный процесс, используя взаимосвязь одномерного и многомерного преобразований (см. [20]). Пример такого распараллеливания показан на рисунке 2.9. Не исключено таюке применение специализированных БИС или построение процессора на основе заказных или полузаказных БИС [33]. Таким образом, для современного уровня развития элементной базы и вычислительных методов реализация специализированных процессоров для обработки М-последовательностей при помощи быстрого преобразования даммара не представляет принципиальных трудностей для баз, превышающих 30-50 тыс. Н(4) W Н(4) Н( Н(4) — . Рисунок 2.9 Вычисление 16-точечного преобразования Адамара с помощью 4-точечного

                                 Рассмотрим теперь методы синхронизации по информационной совокупности. Они, как правило, используют лишь часть общей энергии сигнала, поэтому основные применения этих методов лежат в области слабых и средних шумов с вероятностью ошибки на символ 0.05-0.4. При сильных шумах требуемая помехоустойчивость может быть получена только за счет усложнения оборудования, что делает более целесообразным использование последовательностей быстрого поиска или обработку при помощи спектральных преобразований. Уникальным применением методов синхронизации по информационной совокупности является апериодическая синхронизация в отсутствие целеуказания о фазе синхропоследовательности. Здесь эти методы являются - единственно возможными среди всех рассмотренных. Хотя синхронизация по информационной совокупности возможна для любой линейной рекуррентной последовательности, предпочтительнее использовать М-последовательности, так как они имеют информационные совокупности минимального объема и, следовательно, позволяют минимизировать вероятность ошибки синхронизации.

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

                                 Общие понятия о сложности реализации декодирования

                                 Для поиска чистого отрезка можно использовать зависимость (1.4). Каждый символ кодовой последовательности формируется на основе m предыдущих символов, часть этих символов участвует в формуле расчета, которая задается в (1.5) проверочным многочленом д(х). Рассмотрим сегмент годового слова длиной L = т + і символов. Каждый і-іі символ может быть предсказан по закону д(х) по m предыдущим символам, причем при отсутствии канальных ошибок символы сегмента L и их предсказания совпадают. Таким образом, последние / - символов могут быть проверены на основе т предыдущих символов, при этом, наличие ошибки в закономерности символов может послужить критерием различия чистых и зашумленных сегментов. Такой критерий и лежит в основе нового метода быстрого декодирования.

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

                                 Процедуру поиска можно организовать следующим образом. Допустим, из канала принято m символов слова х , т.е. символы x\,x z,...,x m. На основе этих символов можно предсказать (т+1)-ый символ д{х\,х 2, ...,л: т) и сравнить с символом х т+1, принятым из канала. Если сравнение показало совпадение принятого символа и предсказаного, т.е. х т+і = д(.х і х 2 — х т) т0 можно предположить, что начался чистый кодовый сегмент. При обнаружении такого сегмента можно считать, что в принятом сегменте из m символов нет ошибки, и использовать его для декодирования. Однако такое решение будет ложным, если канальные ошибки не нарушают указанную проверку, основанную на сравнении канального символа и его предсказания. Будем называть доверительным сегментом сегмент из т символов, предсказание которых совпадает с (т+1) -ым символом.

                                 При малой частоте появления канальных ошибок может наблюдаться ситуация, когда на принятом сегменте длины (2т+1) появляется одна ошибка на символе (т+1). Рассмотрим этот случай подробнее. Пусть на первых m шагах формируется оценка (т+1)-го символа. При возникновении канальной ошибки в этом символе появится несовпадение х т+1 Ф д(х \,х г, ...,x m), которое приведет к ложной оценке следующих m входных символов. Если на следующих т+1 шагах поиска чистого сегмента в канале отсутствуют ошибки, то результатом сравнения предсказания и принятого символа будет импульсная характеристика кодирующего регистра, соответствующая прохождению одной канальной ошибки через регистр. В момент времени (т+1) импульсная характеристика заканчивается, что свидетельствует о вероятном обнаружении чистого сегмента, на основе которого можно производить декодирование всего ПС кода. Таким образом, обнаружение импульсной характеристики как результата сравнения канальных символов с их предсказаниями может служить признаком появления чистого кодового сегмента на временном отрезке появления импульсной характеристики, форма сигнала которой известна.

                                 Длина сверхдлинных ПС кодов может достигать порядка 250 символов и больше. При этом поиск чистого сегмента на всей длине D кодового слова является затруднительным, т.к. прием кодов такой длины может занимать достаточно продолжительное время. В связи с этим представляется целесообразным ограничить интервал поиска доверительного сегмента конечной длинной L « D. Выбор интервала поиска L производится на основе заданной вероятности отказа от декодирования при известной средней частоте ошибок в канале, и осуществляется экспериментальным путем. Как правило, величину отказа от декодирования выбирают равной Ю-2,10 3.

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

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

                                 Процесс кодирования осуществляется на кодирующем т-разрядном регистре (см. рисунок 1.2). Будем называть такую регистр генераторным фильтром. Содержимое сдвигового регистра на произвольном сдвиге, когда включена обратная связь через «ключ», будем называть фазой кода. Содержимое сдвигового регистра в начальный момент времени будем называть начальной фазой кода. Для описания процедуры декодирования воспользуемся схемой декодера, представленной на рисунке 3.1.

                                 Метод БДК выполняет работу декодирования в соответствии с шагами, перечисленными ниже.

                                 Шаг 1. Принятое из канала кодовое слово х посимвольно подается на согласованный цифровой фильтр, который представляет собой кодирующий регистр (см. рисунок 1.2) с разомкнутой обратной связью. Отклик согласованного фильтра (СФ) на безошибочное ПС кодовое слово после приема первых m символов - есть нулевая последовательность. Такой фильтр выполняет роль пассивной согласованной фильтрации принятого слова и может использоваться для приема ПС последовательности (например, для быстрого вхождения в синхронизм).

                                 Результаты исследования декодера БДК симплексного кода

                                 Модель канала с действующей импульсной помехой или с непрерывной хаотической импульсной помехой (ХИП). Обычная импульсная помеха на длине ПС кода появляется, как правило, один раз и поражает s символов на длине п с вероятностью s/n. В данном случае можно считать что символы, подверженные импульсной помехе, изменяются на противоположные. Если импульсная помеха поражает число символов s меньше чем длина сегмента поиска доверительной фазы кода (s «L), то среди символов сегмента наблюдения не подверженных импульсной помехи найдется чистый сегмент, позволяющий обнаружить доверительную фазу кода. Непрерывная ХИП, в отличие от обычной импульсной помехи действует постоянно, на всей длине кодового слова, при этом интервалы между импульсами случайны. В нашем эксперименте в качестве непрерывной ХИП будем использовать псевдослучайную последовательность, построенную на основе плоских совершенных разностных множеств с Я = 1. В такой последовательности длина каждого интервала между импульсами встречается только один раз на всей длине этой последовательности [Мешковский К.А., Кузнецов B.C. Методы построения оптимальных расстановок частот и однополярных ПСП. Серия техника радиосвязи, вопросы радиоэлектроники, выпуск 1,1973 г.].

                                 Для исследования помехоустойчивости метода быстрого декодирования была разработана программная модель в среде Matlab, имитирующая кодирование ПС кода, передачу кода через ДСК канал, и его восстановление декодером БДК. Структурная схема программной модели представлена на рисунке 4.2.

                                 Согласно рисунок 4.2 программная модель включает в себя четыре модуля: 1) блок кодирования ПС кода (кодер); 2) блок моделирования канала передачи данных (Канал); 3) блок быстрого декодирования ПС кода (Декодер); 4) блок управления экспериментом (анализатор).

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

                                 Блок Кодер реализован в среде Matlab и представляет собой функцию (см. Приложение 1, файл "Encode.m", функция "Encode"), которая принимает информационный блок и выдает кодовое слово. Дополнительно есть возможность изменить параметры кодирования: проверочный многочлен д{х) ПС кода, длину кодового блока п. Реализация Кодера соответствует описанию схемы кодирующего регистра, рассмотренного в Главе 1. Кодовый блок из п символов передается в блок канал ДСК.

                                 Блок "Канал" реализован в среде Matlab и представляет собой функцию (см. Приложение 1, файл "channel_BSC.m", функция "channel_BSC"), которая принимает на входе кодовое слово длины п, и выдает канальное слово длины и, которое получается искажением символов в исходном слове. Т.к. декодирование осуществляется по сегменту длины L « N = 2т — 1, поэтому п задается равной L. Блок "Канал" позволяет изменять вероятность ошибки р в канальном символе в диапазоне от 0 до 1. Данная вероятность задается блоком "Анализатором". Дополнительно есть возможность изменить параметры канала: вероятность символьной ошибки в канале, и наличие, либо отсутствие ХИП. С выхода блока "Канал" канальное слово поступает на блок "Декодер".

                                 Блок "Декодер" реализован в среде Matlab и представляет собой функцию (см. Приложение 1, файл "Decode.m", функция "Decode"), которая принимает на вход канальное слово длины L и выдает следующие данные: а) результат декодирования в виде решения «Декодировано - Отказ от декодирования»; б) декодированный информационный блок длины т символов. Также, блок «Декодер» может изменять следующие параметры: 1) параметры, характеризующие работу блока «Кодер», 2) порог J обнаружения доверительной фазы кода, 3) длина сегмента наблюдения. Блок «Декодер» реализован в соответствии с описанием декодера БДК, представленным в Главе 3. Следует отметить, что общий параметр блоков «Кодер» и «Декодер», а именно, проверочный многочлен д(х) ПС кода должен быть одинаковым в рамках одного эксперимента. Причиной возврата декодером решения в виде отказа от декодирования может стать только одна причина: на длине принимаемого сегмента не было обнаружено ни одной доверительной фазы кода. Это означает, что на данном сегменте не обнаружен доверительный интервал ширины J=m+1 символ, и не была обнаружена импульсная характеристика приемного согласованного фильтра. После декодирования выходные данные блока «Декодер» поступают на блок «Анализатор» для дальнейшей обработки.

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

                                 

                                 Разработка устройств быстрого поиска шумоподобных сигналов на основе многозначных псевдослучайных последовательностейЧащин Александр Александрович

                                 

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

                                 

                                 Декодирование кодов с малой плотностью проверок на четностьКирьянов Иван Андреевич

                                 

                                 Разработка и моделирование алгоритмов неалгебраического декодирования систематических кодов в каналах со стиранием элементовГладких Алексей Анатольевич

                                 

                                 Исследование и разработка алгоритмов итеративного декодирования избыточных кодов в системе информационно-управляющих комплексовБаскакова, Екатерина Сергеевна

                                 

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

                                 

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

                                 

                                 Исследование и разработка способов повышения производительности последовательного декодирования сверточных кодов на примере алгоритма Фано Бабенко Денис Викторович

                                 

                                 Модели и методы декодирования помехоустойчивых кодов на основе нейросетевого базисаБерезкин Александр Александрович

                                 

                                 ТЕОРИЯ КАСКАДНОГО ДЕКОДИРОВАНИЯ ЛИНЕЙНЫХ КОДОВ ДЛЯ ЦИФРОВЫХ РАДИОКАНАЛОВ НА ОСНОВЕ МНОГОПОРОГОВЫХ АЛГШОРИТМОВОВЕЧКИН, ГЕННАДИЙ ВЛАДИМИРОВИЧ