Введение к работе
Актуальность темы, Многие процедуры цифровой обработки
сигналов (декодирование ходов по методу максимального
правдоподобия, цифровая фильтрация, определение фазы
сигналов) могут быть описаны как произведение вектора на
патрицу. Сокращение времени выполнения этой процедуры и
повышение эффективности РТС в целоп ВОЗМОЖНО ПРИ
использовании методов ускоренного вычисления
векторно-матричного произведения. Эффективный средством
сокращения времени вычисления векторно-матричного
произведения является Факторизация матриц, которая
позволяет представить исходную патрицу в виде произведения слабозаполненных патриц с простым алгоритмом умножения на вектор. Последовательно выполняя умножение входного вектора на каждую из натриц-сомножителей, ножно существенно ускорить обработку сигнала.
Использование известных методов векторно-матричного умножения связано со значительными вычислительными затратами. Факторизация матриц ряда сигналов с хорошими корреляционными свойствами Споследовательиости квадратичных вычетов, Якоби. характеристические последовательности) невозможна из-за ограничений на размер и структуру матриц, которые налагаются традиционными методами.
Разработка метода Факторизации, который был бы свободен
от ограничений на структуру и рззпер матрицы, позволит
Фэкторизовэть матрицы любых сигналов /в том числе и..
нелинейных/ и ускорить процедуру векторно-патричного
умножения. Таким образом, разработка метода Факторизации
бинарных матриц и создание на его основе алгоритмов
ускоренного векторно-натричного упножения для
синхронизации и декодирования бинарным сигналов является актуальной задачей.
Связь работы с научными программами.темами. Тема диссертационной работы является составной частью тематики научно-исследовательских работ, проводившихся на кафедре РТС в рамках договора НИР ГБЧ 91-3026/06.
Цель и задачи исследования. Целью работы является р-э.3-
работка методов факторизации бинарных матриц нелинейных сигналов и устройств векторно-патричного умножения, для синхронизации и декодирования. Для достижения поставленной цели решаются следующие задачи!
-разрабатываются методи Факторизации произвольной бинарной патрицы, патриц сигналов на основе квадратично-вычетных последовательностей, последовательностей Якоби, характеристических последовательностей и устройство для вычисления векторно-матричного произведения данных последовательностей; -разрабатывается метод и устройство.формирования расширенного ансамбля последовательностей де Брейна и исследуется их эквивалентная линейная сложность;
-разрабатывается метод быстрого декодирования кода на основе .последовательностей де Брейна...
При решении поставленныхзадач .использовались понятия. результаты и методы теории помехоустойчивого кодирования, теории сигналов, матричного анализа, комбинаторики и алгебры логики.
Научная новизна. Доказана возможность Факторизации произвольной бинарной матрицы. Предложен метод, позволяющий представить произвольную бинарную матрицу в виде произведения натриц-сопножителей. в которых любая строка содержит не более двух ненулевых элементов в строке. Получено выражение верхней границы сложности умножения Факто-ризованной матрицы на вектор для предложенного метода. Факторизованы циркулянты сигналов на основе квадратич-но-вычетных последовательностей, последовательностей Яко-би и характеристических последовательностей. Установлено, что аддитивная сложность умножения на Факторизовакный циркулянт не превышает сложности умножения с помощью двукратного преобразования Фурье и метода Агарвала-Кули для рас- смотренных длин последовательностей.
Предложен метод Формирования последовательностей де Брейна в поле GFC2"). Получено выражение, определяющее размер ансамбля, и исследована эквивалентная линейная сложность полученных последовательностей. Установлено, что по числу Формируемых реализаций предложенный метод превосходит известные; эквивалентная линейная сложность
полученных последовательностей стремится к максимальной. Практическая значиность полученных результатов заключается в:
разработке устройств для ускоренного вычисления векторно-яатричного произведения последовательностей квадратичных вычетов, характеристических последовательностей, последовательностей Якоби и Формирования последовательностей де Брей-на с расширенньш ансамблем;
разработке программного обеспечения для Факторизации произвольной бинарной патрицы и циркулянтов сигналов на основе двузначных характеров.
Экономическая значимость полученных результатов. Практические и теоретические результаты диссертационной работы готовы к коммерческому использованию в виде программного обеспечения и разработанных устройств.. На защиту выносятся; 1.Методы Факторизации произвольных бинарных матриц, матриц сигналов на основе двузначных характеров, последовательностей де Брейна: 2.Метод Формирования последовательностей де Брейна; 3.Устройства для ускоренного вычисления векторно-матричного произведения на основе Факторизации матриц и формирования последовательностей де Брейна.
Личный вклад соискателя. Лично автору принадлежат:
разработка метода Факторизации бинарных матриц для синхронизации и декодирования нелинейных сигналов;,
разработка метода Формирования расширенного ансамбля последовательностей де Брейна и их быстрого декодирования;
разработка метода ускоренного вычисления векторно-матричного произведения последовательностей на основ* двузначных характеров.
Апробация результатов диссертации. Результаты диссертационной работы докладывались и обсуждались на совместных совещаниях и семинарах представителей ОКБ ИЗИ и кафедры РТС Белорусского государственного университета информатики и радиоэлектроники, на семинарах кафедры КиТ РЭС Полоцкого государственного университета.
Опубликованность результатов. Результаты диссертации опубликованы в шести работах. Из них: четыре статьи и два отчета по НИР.
4 Структура и обгеп диссертации,Диссертация изложена на 80 страницах машинописного текста, содержит 15 рисунков, 12 таблиц и состоит из введения, общей характеристики работы, четырех глав, заключения, списка использованных источников, приложения. Библиография включает 63 наименования.
