Содержание к диссертации
Введение
ГЛАВА 1. Формирование многозначных шумоподобных сигналов 15
Введение 15
1.1. Постановка задачи 18
1.2. Формирование линейных рекуррентных последовательностей максимального периода 18
1.3. Свойства линейных рекуррентных последовательностей максимального периода 21
1.4. Корреляционные характеристики шумоподобных сигналов 22
Выводы по главе 1 25
ГЛАВА 2. Разработка оптимальных и квазиоптимальных алгоритмов быстрого поиска многозначных ШПС 27
2.1. Постановка задачи 27
2.2. Методы последовательной оценки символов ШПС (быстрый поиск). 27
2.3. Уравнения оптимальной фильтрации дискретного параметра последовательности д-значных импульсных коррелированных сигналов, аппроксимированных цепью Маркова с ^-значениями 30
2.4. Уравнения оптимальной фильтрации m-значных комбинаций значений дискретного параметра ШПС, сформированных на основе многозначных МЛРП 37
2.5. Квазиоптимальный алгоритм нелинейной фильтрации дискретного параметра многозначных МЛРП ШПС № 1 39
2.6. Квазиоптимальный алгоритм нелинейной фильтрации дискретного параметра многозначных МЛРП ШПС № 2 42
Выводы по главе 2 46
ГЛАВА 3. Разработка адаптивных алгоритмов быстрого поиска многозначных ШПС 47
3.1. Постановка задачи 47
3.2. Алгоритм адаптации по входу 48
3.3. Алгоритм адаптации по выходу 49
3.4. Алгоритм комбинированной адаптации 50
3.5. Разработка структур устройств быстрого поиска многозначных ШПС 52
3.5.1. Структуры приемных устройств быстрого поиска ШПС, сформированных на основе многозначных МЛРП 54
3.5.2. Структуры адаптивных приемных устройств быстрого поиска ШПС, сформированных на основе многозначных МЛРП... 56
3.6. Прием ШПС на основе многозначных МЛРП 57
3.6.1. Распознавание ШПС, сформированных на основе двоичных МЛРП 59
3.6.2. Распознавание ШПС, сформированных на основе многозначных МЛРП 63
3.6.3. Одновременное обнаружение и распознавание ШПС, сформированных на основе двоичных МЛРП (поиск ШПС) 66
3.6.4. Одновременное обнаружение и распознавание ШПС, сформированных на основе многозначных МЛРП (поиск ШПС) 70
3.6.5. Анализ времени поиска ШПС, сформированных на основе двоичных МЛРП 73
3.6.6. Анализ времени поиска ШПС, сформированных на основе многозначных МЛРП 76
Выводы по главе 3 79
ГЛАВА 4. Аппаратно-программная реализация устройств быстрого поиска ШПС 81
4.1. Постановка задачи 81
4.2. Обзор существующих технических возможностей реализации устройств быстрого поиска ШПС... 82
4.3. Анализ сложности технической реализации устройств быстрого поиска ШПС 90
4.4. Аппаратно-программная реализация алгоритмов быстрого поиска ШПС 105
Выводы по главе 4 123
Заключение 124
Используемая литература
- Свойства линейных рекуррентных последовательностей максимального периода
- Уравнения оптимальной фильтрации дискретного параметра последовательности д-значных импульсных коррелированных сигналов, аппроксимированных цепью Маркова с ^-значениями
- Разработка структур устройств быстрого поиска многозначных ШПС
- Анализ сложности технической реализации устройств быстрого поиска ШПС
Введение к работе
ВВЕДЕНИЕ
В современном мире все сферы деятельности человека связаны с телекоммуникациями, без которых не возможно было бы осуществлять взаимодействие и контроль над объектами деятельности человека. В связи с тем, что степень совершенства техники и уровень информатизации и компьютеризации общества с каждым годом существенно возрастает, возможности доступа населения к информации, передаваемой по каналам передачи данных, в том числе и радиоканалы, также растут. Это имеет как положительные, так и отрицательные стороны, затрагивающие проблемы конфиденциальности передаваемой информации.
Актуальной задачей, с которой приходится сталкиваться в наше время, это конфиденциальность информации, передаваемой по радиоканалам. В современных условиях обострившейся конкуренции и проникновения информационных технологий во все виды деятельности, обладание необходимой информацией может стать ключом к победе над конкурентами. В связи с этим, организации все больше задумываются о необходимости защиты своей конфиденциальной информации. Многие используют изощренные методы и средства такой защиты: документы и сообщения кодируются, применяется сложная многоуровневая система доступа и защиты корпоративных информационных систем от внешнего проникновения. Однако, как показывает мировой опыт, непрозрачность и бесконтрольность внутренней информационной среды, т.е. угрозы изнутри - со стороны собственных сотрудников организации - представляют собой опасность не менее значимую, чем атаки на информационные системы извне, на которые обычно приходится основное внимание сотрудников соответствующих служб организации.
Надежная защита информации может быть обеспечена в системах цифровой радиосвязи, где применимы методы криптографии.
ВВЕДЕНИЕ
Криптографические алгоритмы используются в ряде получивших широкое распространение цифровых стандартов сотовой связи, обеспечивая достаточно высокую степень защиты информации от несанкционированного доступа.
При использовании радиоканалов для передачи данных необходимо обеспечить надежную работу в условиях совместного использования выделенного частотного ресурса многочисленными радиоэлектронными системами. В связи с постоянным ростом количества и типов радиоэлектронных средств решить задачу достоверного приема информации в условиях сложной помеховой обстановке можно только за счет увеличения мощности радиопередающих устройств, что увеличивает уровень электромагнитного загрязнения.
Значительно снизить степень электромагнитного загрязнения с одновременным повышением уровня конфиденциальности передаваемой информации при использовании радиоканала в цифровых системах передачи информации можно в случае использования сигналов с расширением спектра (шумоподобные сигналы). Такие системы передачи данных обладают рядом преимуществ перед традиционными узкополосными системами, в частности, им не требуется выделенный частотный диапазон. Системы с ШПС имеют повышенную помехоустойчивость при воздействии преднамеренных естественных помех, высокую энергетическую скрытность сигналов, повышенную пропускную способность, устойчивость к многолучевости и др.
В системах связи с расширением спектра широко применяются шумоподобные сигналы, построенные на двоичных линейных рекуррентных последовательностях максимального периода или на хаотических сигналах, обладающих наибольшей скрытностью. Использование недвоичных (многозначных) МЛРП позволяет значительно
ВВЕДЕНИЕ
увеличить ансамбль кодовых последовательностей по сравнению с двоичными МЛРП (особенно при больших основаниях МЛРП), что существенно усложнит распознавание закона формирования МЛРП сравнимого с хаос системами, в результате чего повысится емкость и конфиденциальность адресных систем связи.
Одним из основных показателей систем связи с ШПС является время вхождения в кодовый синхронизм, т.е. одновременное обнаружение и распознавание (поиск) ШПС абонента за ограниченное время, что является основным ограничением широкого внедрения хаос систем связи [10]. Алгоритмы и устройства кодовой синхронизации бинарных ШПС, широко используемые в системах связи с множественным доступом, не могут быть использованы для кодовой синхронизации ШПС, построенных на МЛРП с основанием больше двух.
Отсутствие алгоритмов быстрого поиска ШПС, сформированных на
основе многозначных МЛРП, делает актуальной задачу разработки и
исследования таких алгоритмов и устройств. Разработанные в данной
диссертационной работе алгоритмы и устройства базируются на
представлении МЛРП многозначными сложными цепями Маркова и
использовании теории фильтрации условных марковских процессов,
разработанную Р. Л. Стратоновичем, В. И. Тихоновым,
И. Н. Амиантовым, Ю. Г. Сосулиным, М. С. Ярлыковым,
Б. И. Шахтариным, Е.П.Петровым и др. В работах Петрова Е. П. [1,24] решена задача быстрого поиска ШПС на основе бинарных МЛРП, что позволило использовать предложенную в них методику при решении задачи построения алгоритмов и устройств быстрого поиска ШПС на основе многозначных МЛРП.
Целью диссертационной работы является разработка и исследование алгоритмов и устройств быстрого одновременного
ВВЕДЕНИЕ
обнаружения и правильного распознавания (поиск) шумоподобных сигналов, построенных на основе многозначных рекуррентных псевдослучайных последовательностях максимального периода, обеспечивающих высокую конфиденциальность передаваемой информации.
Для достижения поставленной цели необходимо решить следующие задачи:
Анализ современного состояния методов быстрого поиска шумоподобных сигналов, построенных на псевдослучайных последовательностях максимального периода с произвольным основанием.
Исследование статистических характеристик ШПС на МЛРП с основанием больше 2.
Разработка оптимальных и квазиоптимальных алгоритмов и устройств быстрого поиска ШПС на основе многозначных МЛРП.
Разработка адаптивных алгоритмов и устройств быстрого поиска ШПС на основе многозначных МЛРП.
Анализ помехоустойчивости разработанных оптимальных, квазиоптимальных и адаптивных устройств быстрого поиска ШПС на основе многозначных МЛРП.
Аппаратно-программная реализация разработанных устройств быстрого поиска ЩПС, построенных на многозначных МЛРП. Методы исследования. Для решения поставленных задач в
диссертационной работе использовалась теория фильтрации условных марковских процессов, теория принятия решений, теория математической статистики и методы численного анализа и статистического моделирования на ЭВМ.
На защиту выносятся основные научные результаты автора:
ВВЕДЕНИЕ
Статистические характеристики ШПС на основе многозначных МЛРП.
Оптимальные алгоритмы быстрого поиска шумоподобных сигналов, построенных на многозначных МЛРП.
Квазиоптимальные алгоритмы быстрого поиска шумоподобных сигналов, построенных на многозначных МЛРП.
Адаптивные алгоритмы быстрого поиска шумоподобных сигналов, построенных на многозначных МЛРП.
Результаты качественного и количественного анализа помехоустойчивости разработанных устройств быстрого поиска ШПС, построенных на многозначных МЛРП.
Новизна научных результатов состоит в следующем:
На основе теории условных марковских процессов получены уравнения и алгоритмы оптимальной фильтрации ШПС, сформированных на основе многозначных МЛРП, представляющих собой сложные многозначные цепи Маркова.
Проведен качественный анализ уравнений оптимальной фильтрации дискретного параметра ШПС, построенных на основе многозначных МЛРП, позволивший получить различные модификации квазиоптимальных алгоритмов поиска ШПС, со сложностью реализации близкой к алгоритмам поиска ШПС, построенных на МЛРП с q=2.
На основе уравнений нелинейной фильтрации дискретного параметра ШПС, построенных на МЛРП с произвольным основанием, разработаны адаптивные алгоритмы поиска ШПС с адаптацией по входному сигналу.
Разработан адаптивный комбинированный алгоритм поиска ШПС с адаптацией по входу и выходу, обеспечивающий быстрое
ВВЕДЕНИЕ
достижение максимальной вероятности одновременного обнаружения и правильного распознавания ШПС, построенных на многозначных МЛРП.
Проведен анализ помехоустойчивости и времени поиска оптимальными, квазиоптимальными и адаптивными алгоритмами быстрого поиска ШПС, сформированных на основе многозначных МЛРП.
Проведен расчет технической сложности реализации и программно-аппаратная реализация разработанных устройств на цифровом сигнальном процессоре TMS320C6711 и программируемой логике ПЛИС.
Практические результаты диссертационной работы могут быть использованы при разработке устройств быстрой кодовой синхронизации в системах цифровой связи, применяющих ШПС на многозначных МЛРП для обеспечения повышенной конфиденциальности передаваемой информации соизмеримой с конфиденциальностью хаос-систем.
По теме диссертации опубликовано 17 печатных работ. Из них 1 статья в журнале, рекомендованном ВАК, 1 депонированная рукопись в ВИНИТИ (№ 826-В2005), 2 статьи в сборнике «Проблемы обработки информации: Вестник Вятского научного центра Верхне-Волжского отделения Академии технологических наук Российской Федерации», 13 статей в сборниках материалов и трудов конференций. Основные положения и результаты диссертационной работы отражены в печатных изданиях, докладывались и обсуждались на международных, всероссийских и региональных научно-технических конференциях: «Наука-производство-технология-экология», Киров, ВятГУ (2005, 2006, 2007); «Современные проблемы создания и эксплуатации радиотехнических систем», Ульяновск, УлГТУ (2004); «Радиоэлектроника,
ВВЕДЕНИЕ
электротехника и энергетика», Москва, МЭИ (2005, 2007); «Цифровая обработка сигналов и ее применение», Москва (2005); «Микроэлектроника и информатика», Москва, МИЭТ (2005); депонированная работа в ВИНИТИ (2005); «Вестник Вятского научного центра Верхнее-Волжского отделения Академии технологических наук РФ», (2005, 2007); «Научные сессии, посвященные Дню Радио», Москва (2005, 2006); «Радиолокация, навигация, связь», Воронеж (2006); «Обработка сигналов в системах телефонной связи и вещания», Н.Новгород (2006); «Вестник МЭИ», Москва, МЭИ (2005).
Диссертационная работа состоит из четырех глав и приложений.
В первой главе рассмотрены методы формирования и свойства шумоподобных сигналов, построенных на основе многозначных линейных рекуррентных последовательностей максимального периода. Рассмотрены корреляционные характеристики шумоподобных сигналов при различных основаниях МЛРП.
Во второй главе проведен обзор методов быстрого поиска ШПС на основе последовательной оценки символов, позволяющие сократить время вхождения в синхронизм с искомой ПСП за счет использования информационной избыточности ПСП, заложенной в нее при кодировании. Используя метод последовательной оценки символов с накоплением разработаны алгоритмы и устройства быстрого обнаружения и распознавания ШПС, построенных на многозначных МЛРП с основанием q>2. На основании уравнений оптимальной фильтрации дискретного параметра последовательности g-значных импульсных коррелированных сигналов, аппроксимированных цепь Маркова с д-значениями, предложенных Петровым Е.П. [1], разработаны оптимальные и квазиоптимальные алгоритмы и устройства быстрого поиска ШПС, сформированных на основе многозначных МЛРП. На основании
ВВЕДЕНИЕ
нелинейной функции в уравнениях фильтрации [24] дискретного параметра ШПС, построенных на многозначных МЛРП, получено более простое, с точки зрения сложности технической реализации, уравнение модифицированной нелинейной функции (квазиоптимальный алгоритм № 1), сложность реализации которой не зависит от основания МЛРП и соизмерима со сложностью реализации нелинейной функции для фильтрации двоичных МЛРП, что существенно снижает требования к сложности технической реализации устройств быстрого поиска ШПС на основе многозначных МЛРП в интегральном исполнении. На основе квазиоптимального алгоритма № 1 получен более простой, с точки зрения сложности технической реализации, квазиоптимальный алгоритм № 2, аппроксимирующий нелинейную функцию двумя прямыми линиями.
В третьей главе разработаны адаптивные алгоритмы быстрого поиска ШПС на основе многозначных МЛРП: с адаптацией по входу, с адаптацией по выходу и с комбинированной адаптацией. На основании полученных алгоритмов разработаны структуры оптимальных, квазиоптимальных и адаптивных устройств быстрого поиска многозначных ШПС. Проведен анализ помехоустойчивости разработанных устройств быстрого поиска ШПС на основе многозначных МЛРП: вероятность правильного распознавания m-значных комбинаций МЛРП, вероятность правильного одновременного обнаружения и распознавания m-значных комбинаций МЛРП, анализ времени поиска ШПС на основе многозначных МЛРП. Результаты проведенных исследований показывают, что при решении задач быстрого поиска ШПС на основе многозначных МЛРП при неизвестном времени появления сигнала на входе ПУ наибольший выигрыш по времени поиска достигается применением алгоритмов с комбинированной адаптацией.
ВВЕДЕНИЕ
В четвертой главе приведен обзор существующих технических возможностей для реализации разработанных устройств быстрого поиска ШПС на специализированных больших интегральных схемах, цифровых сигнальных процессорах и ПЛИС. Проведен подробный анализ сложности технической реализации отдельных блоков проектируемых устройств при заданной разрядности и точности вычисления сложных математических функций. Описаны методы быстрого вычисления сложных математических функций (экспоненциальная функция и натуральный логарифм) при заданной точности вычисления для более простой реализации в интегральном исполнении. Проведен численный анализ сложности технической реализации адаптивных устройств быстрого поиска ШПС на основе многозначных МЛРП. Рассмотрена программная реализация разработанных устройств быстрого поиска ШПС на цифровом сигнальном процессоре с плавающей точкой TMS320C6711. Проведен расчет технической сложности аппаратной реализации разработанных алгоритмов на программируемых схемах ПЛИС различных семейств фирм Altera и Xilinx, а также даны рекомендации по выбору тех или иных микросхем ПЛИС различных фирм-производителей для реализации разработанных алгоритмов.
Свойства линейных рекуррентных последовательностей максимального периода
Рассмотрим основные свойства МЛРП, формируемые согласно рекуррентному правилу (1.1):
1. Периодичность. МЛРП является периодической с периодом, состоящим из L символов. Максимальный период последовательности с памятью последовательности т и основанием последовательности q определяется с помощью выражения [3]: L = qm-\ (1.3)
2. Сбалансированность. Период МЛРП содержит одинаковое число ненулевых символов l,2,...,(q-\), равное qm l и (qmA -lj нулевых символов, иными словами, для каждого периода последовательности количество различных ненулевых чисел одинаково, количество нулевых чисел на единицу меньше количества ненулевых [3, 15].
3. Свойство «хаотичности» [13]. Если из периода МЛРП, содержащего L = qm -1 членов выбрать все возможные отрезки по m-членов в каждом, тогда: среди этих отрезков не будет совпадающих; среди них найдутся любые комбинации чисел от 0 до (#-1), состоящие из w-членов (кроме «запрещенной» комбинации, состоящей только из нулей). 4. Корреляционные свойства. Автокорреляционная функция (АКФ) МЛРП имеет форму, сходную с формой АКФ квазибелого шума с ограниченным спектром. Боковые пики периодической АКФ МЛРП равны -1/L. АКФ усеченной (непериодической) МЛРП длиной в период L имеет величину боковых пиков, близкую к l/yJL . Поэтому с ростом L величина боковых лепестков уменьшается [3]. Методы формирования ШПС, образованных за счет расширения спектра, рассмотрены в работах [3, 11, 12, 14, 15, 16].
Рассмотрим автокорреляционные характеристики МЛРП со следующими правилами кодирования при т=3 и различных основаниях q=2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 (см. приложение 1, рис. 1-12). АКФ показывает связь сигнала со своей копией, смещенной во времени на величину т. Изучение АКФ играет важную роль при выборе кодовых последовательностей с точки зрения наименьшей вероятности установления ложной синхронизации.
Периодическая АКФ (периодически продолжающаяся во времени) МЛРП вычисляется согласно уравнению: где і - относительный сдвиг (символов) опорной МЛРП и ее копии; ак, а(к+х) значение А го и (& + т)-го символов МЛРП соответственно; q — основание МЛРП, L - период МЛРП, j = v-1 - мнимая единица.
Апериодическая АКФ (периодически не продолжающаяся во времени) МЛРП вычисляется согласно уравнению: На рис. 4 (при q=l, т=Ъ) и в приложении (см. приложение 1, рис. 1-12) при различных основаниях q и одинаковой для всех исследуемых МЛРП начальной m-значной комбинации PC генератора МЛРП представлены периодические (а) и апериодические (б) АКФ МЛРП.
Значения модуля максимального уровня боковых лепестков периодической и апериодической АКФ для различных правил формирования МЛРП при заданной начальной m-значной комбинации. (RG0 = {0;0;1}) PC генератора МЛРП и значениями коэффициентов отводов обратной связи (C = {Cj;c2;c3}) согласно (1.1) представлены в приложении (см. приложение 1, табл. 1). Уровень боковых лепестков ААКФ зависит от правила кодирования МЛРП и начальной m-значной комбинации PC генератора МЛРП. Выбор лучших МЛРП может быть сделан на основе минимаксного критерия [2], согласно которому для заданного класса МЛРП с параметрами (q, т) и всевозможных значениях начальных га-значных комбинаций PC генератора наилучшими корреляционными свойствами обладают те МЛРП, которые имеют наименьший уровень боковых компонент (лепестков) АКФ. Боковые компоненты АКФ МЛРП имеют нулевое среднее значение и дисперсию, пропорциональную \JL, где L - период МЛРП (см. рис. 5). Закон «корня из » является приближенным [2]. ШПС, сформированные на основе МЛРП с основанием q 2, обладают лучшими корреляционными свойствами и высокой структурной сложностью сигнала в сравнении с двоичными МЛРП (q=2), что позволяет рекомендовать их к применению в конфиденциальных системах связи с использованием многозначных ШПС.
Выводы по главе 1
1. МЛРП с основанием q 2 образуют существенно больший ансамбль кодовых последовательностей по сравнению с бинарными рекуррентными последовательностями максимального периода, что с учетом других положительных свойств позволяет рекомендовать их применение в системах связи с защищенными каналами связи.
2. Рассмотрены корреляционные характеристики (периодические и апериодические АКФ) МЛРП при различных основаниях q. ШПС, сформированные на основе МЛРП с основанием q 2, обладают лучшими корреляционными свойствами и высокой структурной сложностью сигнала в сравнении с двоичными МЛРП, что позволяет рекомендовать их к применению в конфиденциальных системах связи.
3. Выбор наилучших МЛРП, с точки зрения корреляционных свойств, определяется минимальным уровнем боковых компонент АКФ при всевозможных значениях начальных комбинаций PC генератора
Уравнения оптимальной фильтрации дискретного параметра последовательности д-значных импульсных коррелированных сигналов, аппроксимированных цепью Маркова с ^-значениями
Будем полагать, что подлежащий выделению дискретный параметр \ik сигнала s{\ik) принимает в каждом такте работы системы =1,2,... одно из нескольких значений Mv...,Mq с вероятностями pl,...,pq соответственно, где q - число состояний. Будем считать, что процесс \ik является простой однородной цепью Маркова с заданной матрицей вероятностей перехода (МВП) из значения М. в к-ом такте в значение М в (&+1)-ом такте: л, 1 Kv (2.1) 7U ?1 7С„ где элементы матрицы TV = p(\ik+l = Mj \\ik =М,) = n{Mj \МІ), где i,j = l,q, 1-7Г, nv= q-\ f-Лі Л, (2.2) (2.3) при этом выполняется условие нормировки: (2.4)
Матрица вероятностей перехода (2.1) вместе с вероятностями pi, удовлетворяющими условию Л=1;і = й, (2-5) (=1 полностью определяют однородную цепь Маркова и предполагаются известными на приемной стороне канала связи.
Будем полагать, что последовательность импульсных коррелированных сигналов с дискретным параметром \хк образует сложную цепь Маркова с «-значениями М,,...,Ма с вероятностями Ч р{,...,р соответственно и вероятностями перехода: Ъу = л(ш+ік-т+і -,Ц ), где /,у = \,q . (2.6) Сведем сложную цепь Маркова к простой. Обозначив га-значную комбинацию {[ik_m+1,...,\ik} как оценку \х,к следующего за ней значения параметра \ik+l, получим простую цепь Маркова с -значениями и вероятностями перехода: Ъц =7t( i -m+iv ) = w -М7.Д, =М;), где i,j = l,q. (2.7) Учитывая, что \хк+1 и \ik формируются по одному правилу и образуют -значную детерминированную цепь Маркова, в которой т значная комбинация {\\.к_т+х,...,\лк} однозначно определяет \ак, уравнение для апостериорной плотности вероятности Pklii k+i) значений дискретного параметра искомого ШПС в (А;+1)-м такте можно записать в виде [1]: где f([ik+i) - логарифм функции правдоподобия параметра цк+1, w(vLk+\\vik) = w(lxk+\\vLk-m+i - lik) - плотность вероятности перехода из значения ДА в \х,к+х на (к+\)-м такте, с -коэффициент нормировки: )d[ir..d[ik+l, (2.9) где /і+1((а15...,Лі+1) - многомерная функция правдоподобия параметра \хк+1 в (&+1)-м такте; р1Р+1(щ,...,\лк+1) - априорно известная многомерная плотность вероятности фильтруемого процесса.
Представим в (2.8) апостериорные плотности вероятности и плотность вероятности перехода в виде [24]: У=1 где р., , р . +1ч - апостериорные вероятности значений параметра щ в к-м и (&+1)-м такте соответственно; %у - вероятность смены значения \хк =М. в к-м такте на \ik+1 = Mj в (+1)-м такте, б(-) - дельта функция.
Подставив уравнения (2.10), (2.11), (2.12) в (2.8), проинтегрировав и приравняв коэффициенты при одинаковых 8-функциях, получим систему рекуррентных уравнений для финальной апостериорной вероятности дискретного параметра ШПС [1]: PJ(M) =сх ехР {/ы (MJ )} 2 (Л (2-13) г =1 где J = l,2,...,q; fk+1(Mj) = f(nk+l=Mj).
Уравнения (2.13) являются основой для построения устройств фильтрации дискретного параметра импульсного коррелированного сигнала, последовательность значений которого является стационарной цепью Маркова с q значениями.
Для удобства различения значений дискретного параметра переведем уравнения (2.13) в аддитивную форму.
Будем полагать, что МЛРП с основанием q > 2 искомого ШПС и опорная МЛРП, генерируемая в ПУ, формируются по одному правилу и являются вариантами одной и той же детерминированной /и-связной сложной детерминированной цепью Маркова с q значениями.
Пусть в (&+1)-м такте работы системы значение дискретного параметра \ак опорного ШПС сформировано на основе т-значной комбинации оценок \хк_т,...,\Хк принятых на такт раньше символов МЛРП искомого ШПС и записанных в регистр сдвига генератора опорной МЛРП согласно (1.1): (2.27) (=1 у где с. (/ = 1,...,т) - целочисленные коэффициенты, к - номер такта. Если шума нет, то символы МЛРП искомого ШПС и опорной МЛРП совпадают, т.е. ц4+] = \хк. Значения дискретного параметра искомого ШПС \xk+l=Mj и опорного \ik=Mt, где i,j = l,q, связанные общим правилом формирования МЛРП, образуют вырожденную (детерминированную) m-связную цепь Маркова с q равновероятными (/?. =l/q) значениями Мп i = l,q, и матрицей условных вероятностей перехода (МВП) %tj в (&+1)-м такте [24]:
Разработка структур устройств быстрого поиска многозначных ШПС
Структура ПУ быстрого поиска ШПС, реализующая квазиоптимальный алгоритм № \у описываемый уравнениями (2.21), (2.32) , (2.39), представлена на рис. 10.
Устройство (рис. 10) состоит из дискриминатора (Д), вычисляющего разность логарифмов функций правдоподобия fk+i{Mj)-fk+i{Mq) Для каждого из /-каналов НФ, j = l...(q-l); (q-\)-канального нелинейного фильтра, каждый канал которого один сумматор и умножитель (); решающего устройства (РУ) для различения значений МЛРП в соответствии с критерием (2.34); генератора МЛРП, состоящего из регистра сдвига (PC) m-значной комбинации символов МЛРП и сумматора по модулю q; мультиплексора (MUX) и регистра задержки (РЗ) согласно (2.33); и Чк) на такт, формирующие значение модуля единственного блока вычисления нелинейной функции (БНФ) и сумматора, формирующих напряжение обратной связи для каждого из каналов НФ, знак которого формируется в соответствии с (2.39); блоков и. для каждого из каналов v(k) формирования знака (БФЗ) модуля значения НФ в соответствии с условием (2.32); решающего устройства (РУг), определяющего наличие, либо отсутствие ШПС в соответствии с критерием (3.12).
Структура ПУ быстрого поиска ШПС (см. приложение 3, рис. 2), реализующая квазиоптимальный алгоритм № 2, описываемый уравнениями (2.21), (2.32), (2.48), отличается от структуры, реализующей квазиоптимальный алгоритм №1, наличием компаратора (и Н), управляющий ключом К согласно условию (2.48), на основании сравнения г п 5L 3. напряжения Uv(k) на выходе РЗ с заданным порогом Н = In —- , і Ф j Структуры квазиоптимальных ПУ двоичных ШПС (q=2) с НФ для случая аппроксимации нелинейной функции zx{-) одной линией (2.46) и двумя линиями (2.47) представлены в приложении 2 на рис. 2 и рис. 3 соответственно.
Структура ПУ с адаптацией по входу, реализующая квазиоптимальный алгоритм № 1, описываемый уравнениями (2.21), (2.32), (2.39) и алгоритм адаптации (3.3), представлена в приложении (см. приложение 3, рис. 3). Отличительной особенностью данного ПУ является наличие дополнительного решающего устройства (РУ), осуществляющего различение значений дискретного параметра ШПС на входе НФ согласно (2.34).
Структура ПУ с адаптацией по входу, реализующая квазиоптимальный алгоритм № 2, описываемый уравнениями (2.21), (2.32), (2.48) и алгоритм адаптации (3.3), представлена в приложении (см. приложение 3, рис. 4).
Структура ПУ с адаптацией по выходу, реализующая квазиоптимальный алгоритм № 1 и алгоритм адаптации (3.5), представлена в приложении (см. приложение 3, рис. 5). Структура ПУ с адаптацией по выходу, реализующая квазиоптимальный алгоритм № 2 и алгоритм адаптации (3.5), представлена в приложении (см. приложение 3, рис. 6).
Структура ПУ с комбинированной адаптацией (по выходу и входу), реализующая квазиоптимальный алгоритм № 1 алгоритм адаптации (3.6), представлена в приложении (см. приложение 3, рис. 7).
Структура ПУ с комбинированной адаптацией (по выходу и входу), реализующая квазиоптимальный алгоритм № 2 и алгоритм адаптации (3.6), представлена в приложении (см. приложение 3, рис. 8).
Структуры ПУ с комбинированной адаптацией (см. приложение 3, рис. 7-8), в сравнении со структурой ПУ с адаптацией по входу, отличаются наличием блока выбора адаптации (БВА) [40]. Входными параметрами блока БВА являются значения дискретных параметров \i "+l и \ik+l, полученные со входа и выхода НФ соответственно, а также значения оценки пи,к) и порога переключения К с адаптации по выходу на адаптацию по входу. Параметр К 0 задается априорно. Блок БВА согласно условию (3.6) выбирает параметр (\i kn+i или \ik+l), который затем сравнивается блоком адаптации (БА) с оценкой \ik, сформированной на основе принятой w-значной комбинации в PC ПУ.
Анализ сложности технической реализации устройств быстрого поиска ШПС
Основные поставщики FPGA-микросхем - компании Actel, Altera, Atmel, Lattice Semicoductor, QuickLogic, Triscend, Xilinx.
На сегодняшний день наиболее перспективны следующие ПЛИС фирмы Xilinx. Это ПЛИС FPGA серии: Virtex, Spartan, за исключением микросхем семейств Spartan (напряжение питания 5 В) и Spartan-XL (3,3 В); CPLD серий ХС9500 и CoolRunner-II.
Перепрограммируемые пользователем базовые матричные кристаллы (FPGA - Field Programmable Gate Array), перепрограммируемые микросхемы с традиционной PAL архитектурой (CPLD - Complex Programmable Logic Devices - сложное устройство с программируемой логикой), а также средства их проектирования и отладки, выпускаемые фирмой Xilinx, используются в устройствах цифровой обработкой информации - например, в системах телекоммуникации и связи, вычислительной технике, периферийном и тестовом оборудовании, электробытовых приборах.
Помимо всех преимуществ стандартных базовых матричных кристаллов (БМК), при использовании FPGA разработчик электронных устройств получает возможность реконфигурации кристалла на рабочем месте. Это даёт принципиально новые средства коррекции ошибок и существенно сокращает время выхода устройства на рынок готовой продукции.
Фирма XILINX производит микросхемы в различных типах корпусов и в нескольких исполнениях, включая индустриальное, военное и радиационно-стойкое.
Для проектирования цифровых устройств на основе ПЛИС фирмы Xilinx существуют две конфигурации пакета ISE (Integrated Synthesis Environment): ISE Foundation - платный пакет без ограничений логической емкости ПЛИС и ISE WebPack - бесплатный пакет (ограничение: поддержка ПЛИС емкостью до 1,5 млн. системных вентилей; все функции пакета аналогичны ISE Foundation, в том числе (начиная с версии 8 Л і) CoreGen, FPGA Editor, работа с EDK и ChipScope). Несмотря на то, что пакет ISE WebPack является бесплатным, он представляет собой полнофункциональную САПР, которая позволяет выполнить все этапы разработки, начиная с создания проекта и заканчивая программированием кристалла. САПР WebPACK ISE не имеет ограничений по времени его использования [20].
К числу последних разработок фирмы Altera относятся и FPGA семейства Stratix GX, в которых наряду с архитектурой ПЛИС выполнен быстродействующий приемопередатчик (SERDES). Семейство Stratix GX, изготавливаемое по 0,13-мкм КМОП-технологии с полностью медной металлизацией, содержит 40 тыс. логических элементов, TriMatrix-память емкостью до 3,4 Мбит, DSP-блоки, усовершенствованную схему управления синхронизацией. Семь микросхем, входящих в семейство, поддерживают от 4 до 20 каналов передачи с пропускной способностью от 622 Мбит/с до 3,125 Гбит/с.
При работе с микросхемами программируемой логики основным инструментом является система автоматизированного проектирования (САПР). Фирма Altera предлагает два САПР MAX+PLUS II и Quartus П. Каждый САПР поддерживает все этапы проектирования: ввод проекта, компиляция, верификация и программирование. Каждый САПР имеет самоучитель, который устанавливается при инсталляции пакета.
САПР MAX+PLUS II является более простым в освоении по сравнению с Quartus П. Он поддерживает семейства MAX, FLEX и АСЕХ, которые содержат микросхемы с 5В питанием и количеством функциональных преобразователей от 32 до 4992 и имеет меньшее количество настроек. Этот САПР фирма Altera не развивает и рекомендует переходить на Quartus П. САПР Quartus II является основным. Фирма Altera активно его развивает. Он поддерживает все новые семейства микросхем и обладает дополнительными функциями, которых нет в MAX+PLUS П.
Фирма Altera предлагает бесплатные версии САПР MAX+PLUS II BASELINE и Quartus II Web Edition, которые поддерживают все этапы проектирования от ввода проекта до программирования. Ограничениями являются количество поддерживаемых микросхем и некоторые функции для Quartus II.
