автореферат диссертации по радиотехнике и связи, 05.12.17, диссертация на тему:Синхронизация и декодирование бинарных сигналов на основе факторизации матриц

„ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ > [ б ОД ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

2 2 МАЙ 1ЕГ3

УДК 621.391

МАЛЬЦЕВ Сергей Васильевич

СИНХРОНИЗАЦИЯ И ДЕКОДИРОВАНИЕ БИНАРНЫХ СИГНАЛОВ НА ОСНОВЕ ФАКТОРИЗАЦИИ МАТРИЦ

Специальность 05.12.17 - Радиотехнические и телевизионные системы и устройства

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Минск 1995

Работа выполнена е Белорусской государственном университете информатики и радиоэлектроники

Научные руководители - доктор технических нзук

профессор Лосев В. В.

доктор технически* нзук профессор Конэг.елько В, К.

Официальные оппоненты

доктор технических нзук профессор Садыков Р. X. кандидат техническим наук Бобов И. Н.

Ведущая организация - Институт технической кибернетики

АН РБ

Зашита состоится & июня 1995 г. 14 в часов на заседании совета по защита диссертаций в Белорусском государственном университете информатики и радиоэлектроники по адресу* 220027 Минск, ул. П. Бровки 6.

С диссертацией можно ознакомиться в библиотеке БГУИР.

Автореферат разослан 5 пая 1995 г.

Ученый секретарь совета по защите диссертаций

д. т. н., профессор

ОошАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

Разработка метода Факторизации, который был бы свободен от ограничений на структуру и размер матрицы, позволит Фэкторизовэть матрицы любых сигналов /в том числе и., нелинейных/ и ускорить процедуру векторно-матричного умножения. Таким образом, разработка метода Факторизации бинарных матриц и создание на его основе алгоритмов ускоренного векторно-натричного умножения для

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

Связь работы с научными программами.темами. Тема диссертационной работы является составной частью тематики научно-исследовательских работ, проводившихся на кафедре РТС в рамках договора НИР ГБЧ 91-3026/06.

Цель и задачи исследования. Целью работы является р-з.з-

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

-разрабатываются методы Факторизации произвольной бинарной патрицы, патриц сигналов на основе квадратично-вычетных последовательностей, последовательностей Якоби, характеристических последовательностей и устройство для вычисления векторно-матричного произведения данных последовательностей; -разрабатывается метод и устройство, формирования рас^рен-нога ансамбля последовательностей де Брейна и исследуется их эквивалентная линейная сложность;

-разрабатывается метод быстрого декодирования кода на основе .последовательностей де Брейна..,

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

Научная новизна. Доказана возможность Факторизации произвольной бинарной матрицы. Предложен метод, позволяющий представить произвольную бинарную матрицу в виде произведения матриц-сомножителей. в которых любая строка содержит не более двух ненулевых элементов в строке. Получено выражение верхней границы сложности умножения Факто-ризованной матрицы на вектор для предложенного метода. Факторизованы циркулянты сигналов на основе квадратично-вычетных последовательностей, последовательностей Яхо-би и характеристических последовательностей. Установлено, что аддитивная сложность умножения на Факторизованный циркулянт не превышает сложности умножения с помощью двукратного преобразования Фурье и метода Агарвала-Кули для рас-■ смотренных длин последовательностей.

Предложен метод Формирования последовательностей де Брейна в поле СРС2"). Получено выражение, определяющее размер ансамбля, и исследована эквивалентная линейная сложность полученных последовательностей. Установлено, что по числу Формируемых реализаций предложенный метод превосходит известные,- эквивалентная линейная сложность

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

- разработке устройств для ускоренного вычисления векторно-яатричного произведения последовательностей квадратичных вычетов, характеристических последовательностей, последовательностей Якоби и Формирования последовательностей де Брейна с расширенньш ансамблем;

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

Экономическая значимость полученных результатов. Практические и теоретические результаты диссертационной работы готовы к коммерческому использованию в виде программного обеспечения и разработанных устройств.. На защиту выносятся;

1.Методы Факторизации произвольных бинарных матриц, матриц сигналов на основе двузначных характеров, последовательностей де Брейна:

2.Метод Формирования последовательностей де Брейна;

3.Устройства для ускоренного вычисления векторно-матрично-го произведения на основе Факторизации матриц и формирования последовательностей де Брейна.

Личный вклад соискателя. Лично автору принадлежат:

- разработка метода Факторизации бинарных матриц для синхронизации и декодирования нелинейных сигналов;,

- разработка метода Формирования расширенного ансамбля последовательностей де Брейна и их быстрого декодирования;

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

йпробэ-ция результатов диссертации. Результаты диссертационной работы докладывались и обсуждались на совместных совещаниях и семинарах представителей ОКБ МЭИ и кафедры РТС Белорусского государственного университета информатики и радиоэлектроники, на семинарах кафедры КиТ РЭС Полоцкого государственного университета.

Опубликованность результатов. Результаты диссертации опубликованы в шести работах. Из них: четыре статьи и два отчета по НИР.

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

СОДЕРЖАНИЕ РАБОТЫ

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

дана краткая характеристика работы. >

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

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

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

При использовании обычных методов произведение вектора длиной N на матрицу размером Ni*N выполняется за N*Ni операций умножения и Ni(N-l) операций 'сложения.

Наиболее употребительным классом сигналов в настоящее время являются бинарные сигналы. Их обработка сводится к умножению вектора входных отсчетов на бинарную матрицу с коэффициентами (il). При этом нет необходимости выполнять операции умножения. Количество сложений при использовании обычных методов равно N^CN -1).

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

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

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

В работе проводится анализ следующих основных методов Факторизации:

-Факторизация методом Гуда; -Факторизация методом Пойда; -Факторизация методом Ярославского.

Показано, что рассмотренные методы факторизации применимы к матрицам, которые имеет определенную структуру и размеры. Сигналы на основе последовательностей квадратичных вычетов, последовательностей Якоби, характеристических последовательностей не аогут быть факторизованы известными метода- • ни, что вынуждает применять для их обработки двукратное преобразование Фурье, требующее значительных вычислительных затрат.

Для циркулянтов таких сигналов необходима разработка метода Факторизации, свободного от ограничений на размер матрицы и ее структуру.

Во второй главе разрабатывается метод Факторизации произвольной бинарной матрицы для обработки любых сигналов.

Доказаны теоремы: Теорема 1. Любая матрица А. состоящая из С±1,0размера N*m, может быть представлена в виде

A=D*Q.

причем матрица Q имеет блочно-диагональную структуру. Теорема 2. Любую матрицу А, состоящую из Cil), размера N*m,>-можно представить в виде произредения h слабозаполненных сомножителей с блочно-диагональисй структурой, причем каждый из сомножителей содержит не более двух единиц в строке и h=floq2n"i. где M наименьшее целое, большее или равное х.

Теоремы 1 и 2 позволяют предложить метод Факторизации произвольной бинарной матрицы А размером N*m. Сущность метода состоит в следующем!

1. Входная матрица А разбивается на блоки, которые включают в себя попарно соседние столбцы С в общем случае). При этом, если irt»0nio<i2, то один из блоков состоит из одного столбца.

Число блоков Р равно

fm/2l»(n/2, если п>Ошо<12.

fm/2l+l, если iw»Omod2.

Формируются вспомогательные патрицы В, которые получаются вычеркиванием повторявшихся и инверсных строк.

2. Составляется блочно-диагокальная матрица 1-го сомножителя.

3. Образуется матрица D с блоками Di из вспомогательных патриц Bj и блоков матрицы Aj. Для этого каждую строку блока flj сравниваем со строками Bj и получаем элемент d[r по следующему правилу:

Количество столбцов в блоке 0,1 равно количеству строк во вспомогательной матрице В.). поэтому индекс г при элементе <1 указывает на нояер столбца в блоке

4. Сформированная матрица Си используется в качестве входной матрицы й.

5. Проверяется число шагов Факторизации 1. Если 1<Г1о22!ч7, то 1»1+1, в противном случае Факторизация завершена.

Таким образом, произвольная бинарная матрица А размером раскладывается на Г1об2)п1 сомножителей за 1 шагов.

Для предложенного метода определена верхняя граница сложности векгорно-матричного произведения бинарных Бб и троичных сигналов Этр.

Для бинарных и троичных сигналов если 1-и27-

если 27<.Ни210.

При этом обеспечивается выигрыш На, Ытр в числе операций по

1. если -1, если bj=-ai О, в остальных случаях

сравнению с обычный методом векторно-патричкого произведения

- 4-Н/С12-ю. если М<.27-

ывг-

- 8 М/схаг-ю, если 27<Н*21=.

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

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

Факторизация циркулянтов последовательностей квадратичных вычетов, последовательностей Якоби, характеристических последовательностей проведена с использованием разработанного программного обеспечения. В таблицах 1-3 приведены величины коэффициента сложности векторно-матричного произведения Фак-торизованных циркулянтов, где N - длина последовательности, 5кв - вычислительная сложность векторно-иатричного произведения последовательностей квадратичных вычетов. Бх - характеристических последовательностей, Эгр - граница вычислительной сложности при использовании Факторизации предложенным методом. ЭФ - вычислительная сложность с использованием двукратного преобразования Фурье.

Таблица 1

Коэффициент сложности умножения циркулянта квадратичных вычетов на вектор

К 11 13 17 19 23 23 31 37 41 43 47 53 59 61

Экв 4.5 5.6 6.6 6.3 7.7 9.3 9.6 11 12 13 13 14 16 16

Продолжение табл. 1

-м 67 71 73 79 83 89 97 101 103 107 109 113 127

Экв 18 18 19 19 20 21 23 24 23 26 25 27 28

N 137 151 163 173 191 139 211

5кв 30 32 35 35 39 40 41

Таблица 2

Сравнение коэффициентов сложности различных методов векторно-матричного умножения

N 32 64 128 256 512 1024

БФ 54 69 84 100 116 132

Бгр 11 19 35 51 83 147

БФ/'БГР 4. 9 3. 5 2. 4 1. 9 1. 39 0. 89

Таблица 3

Коэффициент сложности векторно-натричного умножения Факторизованного циркулянта характеристических последовательностей

N 10 12 16 18 22 28 30 36 40 42 46 52

Эх 4.4 5.0 5.8 6.8 7.6 9.0 9.4 И 11 13 13 15

К 58 60 66 72 78 88 100 112 126 136 138

15 16 18 18 21 22 25 26 23 30 32

N 150 162 172 180 190 198 210 222

Эх 33 34 35 36 39 41 43 43

В таблице 4 приведены результаты сравнения вычислительной сложности операции векторно-натричного произведения Факто-ризованного циркулянта последовательностей Якоби предложенная методом Эя и методом Агарвала-Кули Э»-« и двойного преобразования Фурье Эф для различных длин N.

Таблица 4

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

N 15 21 35 72 143 221

5я - 5. 8 7. 6 10 19 28 36

в л- к - 25.3 35. 4 39. 8 56

Эв-к/Зя 2. 5 1. 9 1. 42 1. 4

Анализ данных табл. 1-4 показал, что унножение Факторизо-ванного циркулянта по сравнению с методами двукратного преобразования Фурье и Агарвала-Кули не сложнее для длин N<400 и N<700 соответственно.

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

Синтезировано устройство ускоренного вычисления векторно-натричного произведения на основе предложенного метода факторизации матриц. Нстановлено, что быстродействие и требуемый объем папяти Ы устройства определяется как

и= Л- Б/СНо- СЪвыч+Ьэял+^оч) ), № И2, где ДОо-число сумматоров, Ьвыч. ^«л, ^ч-время вычисления, записи и считывания соответственно. Показано, что применение синтезированного устройства вычисления векторно-натричного произведения в РТС обеспечит уменьшение времени вхождения в синхронизм при палых и сред-

них длинах сигналов за счет увеличения быстродействия устройств корреляционной обработки.

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

Для Формирования последовательностей де Брейна разработан петод с использованием преобразований в поле СРС 2П). Предложенный петод базируется на следующей доказанной теореме 3.

Теорема 3. Пусть Кх-множество циклов, которым принадлежат иг, а N2-множество циклов, которым принадлежат Все Р.

циклов образуют множество Т. Для того, чтобы циклы были объединены в полное кодовое кольцо, необходимо, чтобы N1 ГМ2= Т.

Ниже в табл.5 представлены данные о размере Форпируеяого предложенный методом ансамбля и эквивалентной линейной сложности полученных последовательностей, где N -длина формируемых последовательностей; (МЪ - размер ансамбля: Сп1п. Сиах-эквивалентная линейная сложность Сминимальная.максимальная? соответственно.

Таблица 5

Размер ансамбля и эквивалентная линейная сложность Формируемых последовательностей.

N 16 32 64 126 256

Нйь 6 144 17280 4. 9-10« 2-Ю18

Ст1п 13 20 50 109 244

С шах 14 30 62 126 254

Предложен метод декодирования кодов на основе последовательностей де Брейна. Метод основан на Факторизации патрицы кодовых слов. Коэффициент сложности векторно-матричмого произведения входного вектора на факторизованную матрицу

кодовых слов кодов на основе последовательностей де Брейна равен п-3 и асимптотически совпадает со сложностью декодирования кода Голда. который имеет такую же мощность кодирования. Предложены устройства Формирования последовательностей де Брейна с использованием преобразований в поле 0КС2П) и вычисления векторно-матричного произведения, разработано программное обеспечение для их Формирования.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Разработаны методы Факторизации последовательностей квадратичных вычетов, последовательностей Якоби. характеристических последовательностей. Исследована аддитивная сложность векторно-матричного умножения циркулянтов сигналов на основе двузначных характеров.

3. Разработана методы формирования последовательностей де Брейна с использованием преобразований в поле СРС2"5 быстрого декодирования кодов на их основе. Исследована эквивалентная линейная сложность полученных последовательностей и размер Формируемого ансамбля.

4. .Синтезированы устройства вычисления векторно-матрично-го произведения на основе предложенного метода Факторизации матриц и быстрого декодирования кодов на основе последовательностей де Брейна.

СПИСОК ОПЫБЛИКОВАННЫХ РАБОТ

1. Лосев В.В., Пальцев C.B. Факторизация бинарных патриц //Радиотехнические тетради, 1991.N1,с. 47-49.

2. Лосев В. В. .Мальцев C.B. Факторизация матриц бинарных сигналов// Радиотехника и электроника, 1992, N12, с. 2190-2196.

3. Конопелько В. К. , Мальцев С. В. Формирование последовательностей де Брейна в поле GFC2") //Радиотехнические тетради, 1991. N1. с. 75-76.

4. Конопелько В. К. , Мальцев С. В. Нормирование последовательностей де Брейна в поле GFC2") //Известия вузов. Радиоэлектроника, 1931, N9, с. 63-84.

РЭЗЮМЗ

Мальцау Сяргей, с1нхраи1запыя 1 дэкадыраванне на падставе фактарызацъи патрыц. с1нхран!заиыя. дэкадыраванне, бинарный с!гналы, Фактарызацыя б1нарных матрыц, вектарна-матрычны здабытак , аддытыуная складанасгь выл1чэння. послядоунасш квадратичных вычэтау. Якаб1, характэрыстычныя, дэ Брейна.

Схнхран1зацыя и дзкадмраванне б1нарных схгиалау разгдя-даецца як выл1чэнне здабытка вектара на матрицу. Фактарызацыя матриц прапануецца для памяньшэння Еътчальнай склада-насц1 гэтай алерацьи. Прапануецца метад Фактармзацы1 б:нар-най матрицы. ПраводШца Фактарызацыя патриц схгналау паслядоунасцей на падставе двузначных характэрау 1 кодау на падставе паслядоунасцей дэ Брейна. Прыводяцца вын1к! памяньюи-ня выл!чальнай складанасц! аперадш! вектарна-натрычнага зда-бытку Фактарызованных прапанаваным метадам матриц 1 метадам! Фурье 1 Йгарвала-Кул1.

Прапануеииа метад Фарм1равання павял!чэннага ансамбля паслядоунасцей дэ Брейна. Прыводяииа вын1к! памера ансамбля I л!нейнай складанасц1 вырабленных паслядоунасцей.

Разглядаюииа тэхн1чныя рашенн1 будовы выл1чэння паскорэн-нага вектарна-матрычнага здабытку 1 фарм!равання паслядоунасцей дэ Брейна.

РЕЗЮМЕ

Мальцев Сергей Васильевич, синхронизация и декодирование основе Факторизации матриц, синхронизация, декодирование, бинарные сигналы. Факторизация бинарных матриц, векторно-натричное произведение, аддитивная сложность вычисления, последовательности квадратичных вычетов. Якоби, характеристические, де Брейна.

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

теров и кодов на основе последовательностей де Брейна. Приводятся результаты уменьшения вычислительной сложности операции векторно-патричного умножения Факторизованных предложенный методой матриц и традиционными методами /двукратное преобразование Фурье, Агарвала-Кули/.

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

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

RESUME

Maltsev Sergey Vasllevich, synchronization and decoding basis on factorization matrix, vector-matrix multiplication, decoding, matrix factorization, nonlinear binary sequences, de BrulJn sequences.

The conducted research has theoretical and applied direction. Calculation of the vector—matrix multiplication is mathematical basis of many devices and systems workl This operation computational complexity reduction allows to make the work of devices more effective.

The main direction of research is to explore the possibility of vector-matrix multiplication computational complexity redaction. Matrix factorization is the basis of vector-matrix smiitiplication algorithm creation. Arbitrary blnar matrix factorization possibility is theoretically proved. Method of factorization is developped. nonlinear signals matrix are factorizated.