автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Характеризационно-инвариантный синтез быстрых ортогональных и теоретико-числовых преобразований



ой

На правах рукописи

Гагарин Юрий Иванович

ХАРАКТЕРИЗАШЮННО ИНВАРИАНТОМ СИНТЕЗ БЫСТРЫХ ОРТОГОНАЛЬНА И ТЕОРЕТИКО-ЧИСЛОВЫХ ПРЕОБРАЗОВАНИЙ.

Специальность: 05.13.13 - вычислительные машины. комплексы,

системы и сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора техническим наук

САНКТ-ПЕТЕРБУРГ 1997

Работа выполнена в Санкт-Петербургском государственном техническом университете .

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

доктор технических наук , профессор Очин Е. Ф.

доктор технических наук . профессор Рохыистров А. Н.

доктор технических наук . профессор мелехин В. Ф.

Ведущая организация - АО "Ленинеи-холдинг"-АООТ " Радар ммс г. Санкт-Петербург.

Защита состоится Pf., ....._ 1997 г.

в Ш. часов на заседании диссертационного совета Д063.38.04 Санкт-Петербургского Государственного Технического Университета по адресу: 195251. г.Санкт-Петербург. Политехническая ул..д.29. 9-й корпус, аудитория 325.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного технического университета по адресу: 195251. г.Санкт-Петербург. Политехническая ул., д.29.

Автореферат разослан йпрекЯ 1997 г.

Ученый секретарь и } ■)

диссертационного совета к. ^ ' ». Дураьдин К. П.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность. Создание и использование современных вычислительных нвшин базируется «а сложных ««тематических моделях, которыми представлены решены« задач*.

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

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

Для расширения сферы применения спзцкалязярвг&гших процессоров требуются адаптивные, гибкие технологии их проектирования, основой которых является теоретически развитое математическое обеспечение; ориентированное на задачи синтеза быстрых алгоритмов, разработки' на их основе высокопроизводительных архитектур спецпроцессоров м создания автоматизированных средств их моделирования и отладки.

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

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

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

Важность и актуальность поставленной а диссертационной работе ца-, ли согласовывается с плановыми научно-исследовательской г. р. N8X8613?, Л 1988, и опытно-конструкторской г. р. И»Г269Э9, Л. 1991 работами, а также внедрениями, выполняемыми в соответствии - с приказом министра Ш1СС СССР N«208 от 13.11.89, постановлением Щ КПСС и Совмина СССР N 222-90 от 16.03. 90. Решением ВПК Совмина СССР N»209 от 10.07.90, приказом министра ПРИ СССР N»218 от 27.07.90..

Предмет исследрвэний! , - методы синтеза быстрых ортогональных и теоретико-числовых пра-. образований на основе обобщенных иатрично-рекурсивных и Факторизовлн-ных форм) *

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

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

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

к теоретико-числовых преобразований через обобщенные иатрично-

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

Исходя из поставленной цели,-можно сформулировать основные задачи!

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

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

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

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

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

■ Научные результаты них новизна»

1. Разработаны к теоретически обоснованы математические модели и методы нарахтеризаиионно-инвармантного синтеза быстрых ортогональных и теоретико-числовых преобразований, отличающиеся от известных иэтодоа тем, что основаны на патрично-блоковыи рекурсивных и яатрично-разря-женным и пчгг.у *""7;гоТл Факторизация*, обобщенных на различные типы и свойства базисных функций в полях вещественных н комплексных чисел и в полях Галуа.

2. На основе блочно-матричных рекурсивны» Форм в базисе дискретных экспоненциальных функций в поле комплексных чисел получены одномерные и многомерные псевдогнездовые алгоритмы быстрого преобразования Фурье (БПФ), обладающие наименьшим общим количеством арифметических

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

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

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

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

6. Для быстрого и точного вычисления вещественных сверток и корреляций. длина которых представлена степенями числа два. ''Получен новый тип теоретико-числовых преобразований Иерсенна в основных полях и быстрые алгоритмы, подобные быстрому преобразованию Хартли в поле вещественных чисел.

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

8. Лля двумерного дискретного косинусного преобразования а базисе

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

I

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

а. Псздан новый вакторно-разностный пегод компрессирования циф-

- ь -

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

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

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

2. Созданы адаптивные технологии обработки радиолокационных сигналов на основе БПФ с повышенным спектральным разрешением.

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

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

Основные положения, выносимые на защит» представлены в разделе "Научные результаты и их новизна".

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

Полученные результаты нашли применение на промышленных предприятиях Г НИЙССИ (г. Москва). АО "Ленинеи-холдинг"-АООТ "Радар ННС\ НПО "Импульс", АО "Ланэнерго" (г. Санкт-Петербург), ОКВ "Радуга" а так*» в учебном процессе отраслевого факультета АВТ и РЭ Санкт-Петербургского государственного технического университета по специальностям "ЭВМ.комплексы. системы и сети", шифр 220100 и "Сметены автоматического управления летательным аппаратами", ииФР 210500. (

а -

i Апробация результатов!

Основные результаты диссертационной работы докладывались к обсуждались на международном симпозиуме ЩРО-бЭСНинск, 1989г. на международной конференции "Системы цифровой обработки и,анализа изображений" CU0H-91 (Рига .1991г), конференции "Цифровая обработка сигналов'Чг.Рига. 1930г. ), на всесоюзных симпозиумах "Логическое управление с.исподь-

I

зованиеи ЗВМ "(Ижевск, 1988, 1987 г. г*.. Ташкент. 1986г., Орджонакид-эе, 1988г.,Симферополь, 1909г.. Москва, 1990г), на международном симпозиуме "Интеллектуальные системы" ИНТЕЛС-98 СС.-Петербург.Д998г). на всесоюзной конференции "Локальные вычислительные сети'ЧРига, 1987г.).

Публикации, tío теме диссертации опубликовано 40 печатных работ, среди которых 3 учебных пособия и 4 авторских свидетельства на изобретения.

Структурами о^'ем радотц., Диссертация состоит из введение, секи разделов, выводов по каждому разделу, заключения, приложений, списка литературы из 18В наименований по разделам. Общий об'ем диссертации,, составляет 236 страниц машинописного текста, включая 60. рисунков и 9 таблиц.

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

Зо введении обоснована актуальность и проведен краткий у.ас. ^ктаризационный анализ проблемы синтеза быстрых ортогональных «.Фурье. Хартли, Уолша. косинусного) и теоретико-числовых (верна и Кэрсвнназ преобразований, сформу.'чрована цель и задачи диссертационной работи. ук&зана научная новизна и практическая ценность полученных результатов.

В пдсдоЦ » соответствии с характэдмэаиирми Ef№ предложено

:1'~1илъзоаать ъ качества инвариантов патрично-блоковые и полмноми-клы'лщ рек'.'рели. Для длины преобразования N • 2п была исполь-

хдриял-еризания нечнтно - периодических продолженных базисных

ФУНКЦИЙ ДПФ , сивных форм.

В результате получены ива вила натрично-блоковых рекур-

2М

г2и • j2n

rae

"м

IK.

'N *Н

3N«*N ~аМ»*М

-1

си

С 2)

1. Ш ■ 0.N-1 1

1

— *н вм . N

II • Ц «нр < -121 С 21+1) «

я

2N

-1

»М «

«м " 'м ,j2n- матрица четно-нечетной перестановки строк.

Из рекурсивны» форм (1) м (2) слединг факторизованныа форны.

• j2h(diiaí

1 1 1 -1

я dlatf

J2N - матрица двоично-инверсно перестановки строк.

г2н

JStt

i.

ам

и diag

4n n Du -Рч

).(3)

К/2

к dita

С4)

1 1 1 -1

Факторизованная форма (3> cootbstctbvst известному аикгоритии вп*

соответствует новому алгоритму БПФ, названному в работе алгоритмом ЕПФ с циркулянтной факторизацией так как ■ нем вместо традиционных диагональных матриц весовых множителей используются циркулянты. Данный алгоритм имеет практические применения. Например, рекурсивное вычисление коэффициентов ДПФ при переходе от двух анализируемых смежных фрагментов цифрового сигнал» к одному, ми объединяющему

'.'.•„•---и-Тьюки по основанию два с прореживанием по частоте. Форма> СО

Фрагменту. Или, например, для вычисления с высокой точность» спектров' цифрового сигнала с большой4 выборкой, если умножение вектор« на циркилянт выполнять через быстрые теоретико-числовые преобразования Ферма или Нерсенна. Данный алгоритм имеет большое теоретическое значение, как обобщение известных алгоритмов Кили-Тыэки на матрично-рекурсивной основе их построения.

Пользуясь выражениями (1) и С2). легко построить рекурсивны» Форму для алгоритма БПФ по основанию Г • 4. Для этого достаточно подставить вместо матрицы гн ее блочно-рекурсивную Форму ^N/2 ГН/2

'ы/г^Н^г ~ГН/2*°Н/2

или

H

'НУ 2 Н/2

Н/2*ГН/2 ~3Н/2*ГШ2

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

<Г>

. FN » Jh (I ® F

f N/Г

г-l cj> ) « с ф D ) и (f & i ), j-0 «T r H/f

< J)

где D

N//"

diea < exp С -1 21 lt j^N >

fi/r -1 > • ,

k-0

J • 0.H/F -1. <

В целом для БПФ с D-матрицами с Г-оснггением

сладуш^я матрично-Факторизованиая форма

Ci") n-1 Ctkî С®Ю Г« ■ J« П ÈN « f , ' k-0 f

гди F • 1я/ k.i i F i I к , ■ Г f t f

CtUÏ u M Ct)

dn » t.) $ I Ф P k ),

r 1-0 f •

справедлива

- s -

tt) » P -l D m • © вир C-121-kV k+1), ■ P >0 Г

t • O.P-l

ÎP)

JK - матрица P -- ично-инверсноА перестановки

Блочно - рекурсивную форму типа (2) можно получить, используя

полиномиальные Факторизации типа ШФ в виде

к

Xtk) • ГС«) mod CZ-wn) м-»

rua fCe) ê£. m t - многочлен соответствующий

>0

последовательности отсчетов (комплексных или вещественных) сигнала, к

ыя • е-12JK/N - h-* степень корня степени H из единицы.

Суть рекурсивного БПФ через свертки в этом случае выступает

C6J

более наглядно, если представить многочлен ГС в) в виде

W2

f(*ï • VCD >2 « Udî

где VCe)

к'2-1 •

J

■ Z *J h а ,

J-О

H-l

uta)

К/2

XJ м в .

Интерполируя многочлены UCs) к VCiï соответственно в четных и

к

нечетных степенях корня Un и кспользоваа выражение (6) можно записать ХС2Ю - at к) + PC к).

Х(2к+1) « sN/2 CQCk) - PCkîî Св)

где *n - циркулянт с порожлаткп вектором

sh « t H ? х < il - i cts ce

I

2M

tk —- )J > N k-0

Выражение СБ) можно обобщить в виде -

«о сР-1>*0 fC*î • voCtî ♦ в « wiCb) ♦..«■•«•»* tí)

r-i

N

где "о " - .

P

Таким образом рекурсивное БП* можно выполнять по общему

С7>

)

- ю -

основанию ГIN в соответствии с выражением аналогичным (6)

cvj <v) «v» cv>

X (Ю » 3мо С®оСк) + 6 tACk) + ... + б и Q (к>>.

Г-1 . Г-1 ■

с v) <Kl"+v)Í"o где 01 • ин

CV) С V) СКР+V)

n0

II s ю II ,l¡ lJ cuN

Lj - j-тый интерполяционный многочлен Лагранжа. (1атрично-блоковые рекурсии (1) и (2) можно обобщить на случай Факторизации длины преобразования N в виде взаимно-простых множителей N « Ni « нг * ■ ■ « wl . tMJ."i) - 1 при 1 * J. В сличав h - 2 матрицу fn можно представить в виде

íO>> fh • (Jn )

rN2 'N2 fh2 sn2*rn2

rN2

Cl.«1-1)

JN2

n2

H2

(N1-1.1) SN2 *TH2

Cl) '

(n1-1, n1-1) 3N2 * *N2

которое следует из Факторизации

cn..im huí N2-1

где 3N2 * diag { С wju >

J-0

C0>/ ti >./

» С JH ) ( ГН2 9 rNl 3 CJN ) . (9J

со) en

где Ji4 и Ji; - матрицы перестановки строк и столбцов, выполненные по китайско-риританскому соотвэтс.-вию.

Примечательно, что матрицу ги можно записать также с (J. к) .

использованием матриц °«2 которые в данном сличав совпадают с

С J, ю

матриаами sh2 . что непосредственно вытекает из тождества 'ш в *Я2 * fN2'® где в и"© - знаки соответствия правого и левого кронекер-вских произведений. От (>екурсианой Формы (8) легко можно переЛти к Фамориэован! ой матричной формз, используи в которой ь свок С1ЧврейЬ «лг01>ИТ.1ы хороткик сверток, можно получить алгоритмы простых Цс'с^ите.цвЛ БГ№. Наличие ргаакства snj ■ °nj характеризует алгоритмы n;.ctJ~;пкажитадей тьм, что для ии* шдльно алгоритмам Кули-Тыоки с

прореживанием по времени и по частоте существуют взаимно-инверсные графы.

Построение гнездовых алгоритмов БПФ основано на представлении

в вырамании (9) матриц в Факториэованном виде, например гю *

* * которые получаются иЗ алгоритмов коротких сверток.

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

простых множителей обладают меньшим числом умножений, но бо'льишк

числом сложений. В конвейерных архитектурах сигнальных процессоров

желательно иметь алгоритмы с наименьшш обеим числом арифметических

операций. _ ,

& работе предложены - псевлогиеэдовые алгоритмы БПФ как

обобщение алгоритмов простых множителей с гнездовыми алгоритмами. В

псевдогнездовых алгоритмах весовые множители могут быть сосредоточены

более чем в одной диагональной матрице. При этопдля малых длин N • 3. 5

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

числа нетривиальным весовых множителей. Преобразованиями на сигнальных

графах демонстрируется получение гнездового алгоритма БПФ для N » 0. В

работе приведена таблица оценок числа арифметических операций

гнездовых и псевдогнездовых алгоритмов БПФ.

Дальнейшее развитие принципов построения псевдогнезловых

га

алгоритмов получили для двумерных БПФ размерности N * N. где N>2.6 этом случае на основе представления двумерного ДПФ в виде одномерного размерности Ко ■ ИхН с матрицей • Ги 0 Рн, представив каждую из. матриц гы в факториэованном виде

СО) СР> со>

н * "о и * ... • "1-1.

(03 21-.1-1

3 • ф

№1

можно представить псевдогнездовой алгоритм двумерного БПФ для (••2а виде матричной Факторизации

где V

12 -

У

<0> со» 1-1 "413 С23 лс2) С 21 Т1Г • (JN 0 JN ) П (°И ) «С DM 3.

J«o

л ti) -42)

где t>N • (I .-J-l в СI j » D i)}» рм - CI .-j-l 9 2 2 2

I 1 2J 2J

1 -1 гл 2J

С 21

X - вторая кронехеровская степень матрицы X. В общем виде для Г основания псевдогнеэдовой алгоритм можно записать в виде

со>'С23 п-1 с tic) с 23 <«ю с23

*м2 ■ с J ) П С°м ) * ÍF ) .

h-О Г

I tk> С 23 f-1 Ct> С 23

где Ссы ) » ('м/ к-1 í с Ф D * )) Г t-0 f

<t> Г -1 - _

D к . ф • вхрС-1 2*tJ/ ,t • О.Г-1. п - log N .

Г J-0 Г Р

сек) С23 С«>'С21 («) С23 Сф) С23 <ф) С23

CF ) - U > » (vo 5 ' » ívi i >» ... * ívi ) , t Г Г

o

сфз cd>

VJ ■ '«/ Ы Й VJ «I К I

r ■ F

cu) o 21-J-l Vj' » t©

ffl»l

121 121

D21 -D21

C»> '

í J )

r

lM »(0)91 . Гк+l f Г к

& работе выведена обшя Форма псевдогнездового алгоритма 'с циркулянтной «актоьизаииай по осиоаанив два для двумерного БГ№.

. Для двумерного БПФ приведень сравнительные оценки по числу арифметических операций псевдогнездовых алгоритмов с другими износгниии алгиритнами! построчно - ..столбцовым , Рейдера-Бреннера м Н ^ с и е аи ив р а- Каен да лла.

Цгррвр г-Д^иа посвящена синтезу быстрых алгоритмов дискретного пуеаЬуваовинля. Хартли через характериэацми ортогонального зоЭуазувакия с нечитио-лродолжэниыии базисными функциями, а именно

п

сдвинутыми на 1/4 по «азе косинусоидами,то есть матрица ДПХ может выть

представлена а виде о

нм • II h Ц - Ц сое (2Ikm/N) й « 42 || сое km

Я.

I 21 kn 4 n

Тогда по аналогии с выражениями (1) и С2). выведенными для ДПФ. можно получить следующие блочно-рекурсивныв матричные Формш

H2N • J2H

Н,

к нк cm сн>

M«DM -MHDH

"2N

J2M

HN Н„

<«> CHI/

SH #1* 4,)

CIO)

Cll)

CH) H-l l(m»S»+bm) H-l 1сга*»м+ьп)

гее °н • С Ф •n» cos - J + С Ф sin - 5 JN,

№0 N m«0 N

1. b>0. n/2

-1. n-N/2, H-l

0, m.O.K/2

N, m.N/2*l.N-l

n ■ 1 • lN-i , ^N-i - единичная инверсная матрица» H-l

CH) -1 ^ -1

aN - N •• £ reo« CI nC2J-2k-l)*N ) + »in CJ nC2J*2k+l)*N )) n-0

(Ю

Необходимо заметить, что матрица Dn является двудиагональной. ,<н>

а элементы циркулянта Зм есть вещественные числа. Из рекурсивных форм (10) и (11) легко строятся иатрично-факторкзованные Формы, соответствующие быстрым алгоритмам преобразования Хартли с основанием

гг 11 ГГг- 11

- ; Г

ИИ • Jtt (dlaej

1 i 1 -1

I - «^Щ

«

*N/2 И/2 СЮ СИ» °К/2 Н/2

M« ■ J«

1 H/2 Н/2 СН> СЮ SH/2 "ТН/2

м ... и dlag

»2 '2 CH) CH)

»2 -*г

ь

* й!ла

1 1 1 -1

Можно построить быстрые алгоритмы преобразования Хартли по

<н>

основанию Г » 2, однако вследствии того, что матрицы °н является двудиагональными. в таких алгоритмах значительно усложняется управление данными. ■ -

В работе решены задачи синтеза быстрых - алгоритмов ДЛХ для случаев, когда длина преобразования N есть либо число .простое, либо Факторизовано взаимно простыми' числами.

Таким образом для малых простых значения N получены простым множителем,гнездовые и псевдогнездовые алгоритмы преобразования Хартли.

.Для составных длин ДПХ N ■ м н2 *...»• (и1,и,>) • I при 1У.1 нет возможности представить ее матрицу нм кронекееоаской Факторизованной Формой, например подобно (9).

Поэтому вывод алгоритма простых множителей для составтик длин ДПХ в работе осуществлен опять с использованием «арактериэации ортогонального преобразования с нечетно-продолженными периодическими базисными функциями. Например, для к • Сн1,мг) " 1 получена

следукщая блочно-рекурсивнея Форма матрицы пм

<0)

нн ... ни

2.2 2

(1X1) <1.N1-1)

■ н1ч Зн • ии .. ан "и

2 2 2 2 2

(N1-1.1) <N1.1. N1-1)

ИЫ ВМ НН ... эн

2 2

"2-1

с 1)

(12)

n2-1

1-де «м « Ф (сое По) + ч'( Ф (в1п (.21и/М1))о) « >н -

' • 2 . ■> О О 2

- £-азра>1<онныэ,двидиагональныа патрицы.

кл и

Ч. -

число простое, та Форма (12) * преобразуется к

- 15 - . 'Ч

блоковом» циркулянт«, к которой» можно применить »равнение коротких

сверток и подключить алгоритм простых множителей.

Другой подход к построению алгоритма простых, множителей ДПХ в

работе демонстрируется через кронекеровскию Факторизацию матриц ДПФ.

которые выражены произведением пароходных Рн на матрицы Ни ДПХ. В

итоге для N • м1»«м21<м1.н2) • 1 на основе "(9) поличена факторизация

СО) ' с и '

"м ■ ( ) (НН1 в НН2> « С7м ), (13)

СО)' » СО) '

где ) ■ рм С,'м ) •« (РК1 в р«2 ). /

На основе С13) в работе приведены сигнальные графы простых

множителей и псевдогнеэдовых алгоритмов соответственно 'для N • 12 и

для N • 1С, а также для гнездовых алгоритмов N «8 и N > 16.

Далее рассмотрены способы построение гнездовых и

псевдогнездовых алгоритмов двумерного " ДПХ на основе выражения _СО) ' (0> ' С23 „СП ' СП '

НМ1 • [[ 7К' ) 8С •'н ) * С"К1 ® *М2 ) « С( ¿М ) ® С )3.

где ню могут быть также Факгориэованы по любой мэ рассмотрении

ранее Форм.

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

1 (Н> я* » - С 9 "и ) » "к" ( "м ® нн )■

м"

, .. СЮ -1 -1 СП

где . »м- ■ С рм в рн ) « "»м» С 'к»рн!,

1Т) СмО н»«1

°гг • с11ав < «и > , >0

(№) С№) (№) _ . ; .

<1 ■ < ... . вИ,-1 > " I ** ® М > " Ч* '

•Чр- вектор-столбеи, образованный последовательностью

*

векторов-столбцов матрицы С 'ЧгЭ. соответствующей импульсном» отклик»

двумерного Фильтра.

В работе приведены инвариантные матрично-рекурсивные Формы для

ортогональных , преобразований с нечётным образом продолженными

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

алгоритмы, аналогичные БПФ или БПХ.

В третьей глава решены задачи синтеза быстрых алгоритмов

теоретико-числовых преобразований (ТЧП).В частности, разложению подлежат

ТЧП в полях Галуа и в числовых .кольцах.образованных по модулю

простых и составных чисел Ферма Ft • 2 +1 .t • 1,2,3,. . и Р

Мерсенна Нр«2 -1 ,р-простое.

Для практических приложений, где требуется обеспечить требуемый

динамический диапазон'цифрового сигнала,наиболее отвечают значения 32

ts5 и рз31.Но *б»2 -»1 является составным числом "и ТМП Ферма в »том

случае строятся в кольце К(Fe).Исследование ТЧП в полях___и кольцах

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

Практические приложения имеют ТЧП, обладающие свойством

цикличности свЁртки,которое например для двумерных сверток momio

записать в следующ&м виде«

-i -i , . - . N»-1

Зп» • Cfn 8 Jn ) Vi'»« *n) . где » diag <aj >

>0

'й'иг « C^O.^l.....IÍN ® ÍW *hN*.

-вектор-столбец, состоящий из последовательности вектор-столбцов матрицы t^tá'- двумерного импульсного отклика.

Анализ Быстрых алгоритмов ТЧП Ферма в кольце К(ге) с <*«>)2 при Н'128 показал,что использование различных оснований. В том числе алгоритмов с рвешепльнкып основанном выигрыша ' по числу ^ри^етичиских операций не дают. Зато сокращения числа арифметических

операций можно достигнуть,если для двумерных ДЧП Ферма использовать _

псевдогнеэдовые алгоритмы.

Далее рассмотрены комплексные ТЧП' Мерсенна в 2-расширенном поле

* 2р-2 р , GFC(Mp)a3 с образующим аС • а + 1 й a p.i» ± 2 mod С2-1). р-2 232 232 232 2 2 и

b р-1 • ±С-3) rood (2 -13. 2

В работе доказано для этого типа ТЧП Мерсенна существование

способов построения хартли-пояобных ТЧП,а именно ТЧП Мерсенна в

основном поле

р га р+1

GFC2 -U с длиной №2 , Млюх*2 .Для нового класса ТЧП г Мерсенна

синтезирован набор быстрых алгоритмов, в том. числе для случая р •

31. При этом созданный комплекс программ моделирования. является.

неотгемлемой частью практических приложений данный алгоритмов.

В работе демонстрируется применение новых ТЧП Мерсенна в поле

GFC231-i) для вычисления автокорреляционной Функции речевого сигнала

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

использованием для этой же задачи ВПХ в арифметике с Фиксированной и

плавающей точкой.

В четвёртой главе рассмотрении способы синтеза быстых

преобразований прямоугольными функциями Уолша СПФУЗ, которые могут . ,

иметь различное упорядочение по Адамару по Пели и по Уолшу . быстрые

известные алгоритмы ПОД преимущественно традиционно строились через

матрично-рекурсивнук Форму матриц преобразования Адамара

аМ/2 AN/2

aN/2 -ftN/2

' Для ПОД с упорядочением по Ыолшу - можно, построить быстрые алгоритмы с использованием матриц перестановок

Сгр) ~

«М • JN * JN * (14)

N

Сгр) jn -

перестановки,соответствующая переходу от кода Грея ь обычный двоичный

где jn - матрица двоичной инверсной перестановки, jn - матрица

код.

Для практических целей пользоваться выражением (14) затруднительно.хотя именно на практике чаше всего используется ПФУ с упорядочением по Цолшу.

В работе для всех указанных трёх примечательно упорядоченных систем дискретных функций Уолша доказано существование обобщенных иатрично-рекурсивных Форм в виде!

СО) С1.М СО) С2.0) СО) « ("'ы. Н/2 * ВМ/2 I •'ы, N/2 * "N/2 >. где 0 - признак упорядочения С по Адамару - А.по Иолшу - и. по Пели - Р).

а. Р) N/2 -

С2. Р) N/2

и.Ю (1) м.к/2 С1)

Зн. н/2 ■ diag < > . *

■1-0

(2, Ы) N..N/2 Й1»в < *Л >

>0

(2)

С2, и) 3Н. N/2

С1. А) ''ы, N/2

С А)

<2) Л N. Н/2 С11«в < (-1) >

¿■О

Г |к/2

I N/2

(2. А) 3Ы. Н/2

Н/2 N/2

N1

(Ы)

Ср)

4« » вм - рн

Тогда обобщенная факторизованная форма матрицы представлена

С») Вы может

быть

(0>

(Пай

1 1 - X (11 аа (1.0) Л

1 -1 2.1 2,1

(1.0) 3 п п-1 2 .2

(2.6) О п п-1 2 .2

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

выражанно через одномерное ПФУ в виде!

и,

Н2

(11аа

С1.и5 -,2П. 2П~1

С1.Ы) 32. 2

(2, и) '2,2

С 2] X____

(2) 1 1 ■

X (Пае - 1 -1

Аналогичные матричные факторизации приведены в работе для других

случаев упорядочения функций 1)олша.

В пятой главе диссертации рассмотрено натрично-Факторизированное

обобщение быстрых алгоритмов дискретного косинусного преобразования

<ДКП>.

Известен целый ряд быстрых - алгоритмов ДКП. которые в работе обобщены по виду слабозаполненным матриц в факторизованных Формам. А

ч

именно.рассмотрении подлежат Факторизации либо через

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

ТМ ■ ,5Н ( тН/2 © *Н/2 ) *

Н/2

Н/2

N/2

'N/2

С16)

где •'и - матрица четно-нечетной перестановки. - Матрица инверсной перестановки. С2ш+1)С2к+1) II

"N/2

■и. соз

к. и)« 0. N/2-1

2 N

1/^2 . к«0> 1 . к-1. N/2-1 . На основе блочно-матричной рекурсии С163 выведена ебшая Факторизоованная Форма матрицы тм.

Г-

л/ 1 1

• •'и ® "2

1 -1

'2 Т2

®

2 -'2

20 л-

»4 V

-14

Ф

'к/в

*Н/4

Г

N/4

- I

N/4

• *м/2

*н/2 'м/2 'и/2 ~1Н/2

где ^г-"! . при N«4

Транспонируя форму (18) .можно получить

быстрый

алгоритм

Т,

к

Т,

N НОЖНО

обратного ДКП .а пользуясь Факторизацией вида тм»

получить лсевдогнездовые алгоритмы двумерного ДКП.

Однако, из-за наличия в Факторизованных Форгах двидкагоналънмх

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

алгоритме сопровождается значительный усложнением прошэсса управлечия данными. Поэтому в работе уделено больше внимания быстром!; алгоритму

ДКП,основанному на однодиагональных матрицах весовых инохптелей.

За основу взят известный алгоритм .для которого выведе>;<:< общая

матрично-факторизованная Форма.В (.оответ^твим с этим алгоритмом.

матрица обратного ДКП представлена в виде. -I

тк • тн » Сыи/Лг 9 1н-1) .

ам » гн .

где и рм Факториэованы

рм • Иаа<*4> « (11ав{р8> «... и Й1ав<рн/2>«,'н. рм слабозаполненные матрицы с элементами О и 1 ,

'к/2

'N/2

-о,

1Н/2 М/2

« <11 ав

'Н/4

•К/«

М/4

иК/4

X .. .

х й!ав

о

(2*.М)*1 -1 п-1

н • <11 аа «2 и сое- ) >

4«п >0

й,,- '»п^п . !п - матрица инверсной перестановки. Соответственно,для матрицы ДКП имеем тн • С1/2 • !м-0 и •» б1ай<рм/2> ». ..* <р4> « «"»в

1 1

А -Ч

n

(Г 'N/4 *М/4 I ВМ/4

. . X (Пае

Тогда псевдогнеэдовому алгоритму

соответствовать следующая факторизация'

С2Э . С 21

'N/2

. I

N/2

Н/2

Л/2

двумерного

ДКП

будет

'мм

(1/42 ® 'м-О » Срм)

- 1 1 С 23

<11ад 1 -1 » н. . . м (Над

». Сй1ав Ср4> )

[23

С 23

N/4

'N/4

"N/4

В работе приведены примеры псевдогнездового двумерного 6»8 ДКП в

виде сигнального векторного графа. Приведены точные оценки

вычислительной сложности псевдогнездовых алгоритмов двумерных ДКП, по

сравнению с построчно-столбцовыми алгоритмами.

В работе рассмотрено также быстрое аппроксимированное косинусное

преобразование,основанное на известном соотношении

1 ~

'N/4

'N/4

N/4

-р

Н/4

С 23

N

гм « н.

где патрица Ун может быть аппроксимирована патрицей сн с целыми

г

числами« см • 'г © сг-1 > ■

В работе с учётом полученных матричных рекурсий для матрицы ^Н

выведена факторизованная Форма, соответствующая

аппроксимированному алгоритму ДКП.

быстрому

н

-н *

и«

2" , п - 1,5

Г 1-1Л 1 Г »г»4-1 'г"-*

т», . I и да е__. ^ „

[ " >1 ] I «г"-1 -'г"-!

Тогда быстрый ' алгоритм двумерного

и спад

1 1 1 -1

аппроксимированого ДКП

может быть представлен в вида I 1

"и* •

N«13'

С -"и 0 ■'и ) » С тн ® тм ) « •

X

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

моделирования . В частности . рассмотрении . подлежали

высокопроизводительные одноконвейерные никропрограммируемые

архитектуры,реализующие гнездовые или псе&догнездовые алгоритмы одно и двумерных БГЖ БПХ и ДКП. Характерной особенностью разработанных архитектур является ацикличность микропрограмм и однотактное время выполнения каждой из микрокоманд. При этом предложено три типа' конвейерных архитектур процессоров . быстрых ортогональных преобразований.

К первому типу относится архитектура.арифметическое устройство в которой включает параллельный умножитель общего назначения. Такая архитектура ориентирована на реализацию гнездовых,псевдогнездовых и простых множителей алгоритмов БПФ.и БПХ,а также быстрых алгоритмов ДКП с однодиагональными матрицами весовых множителей.Длина преобразований N в этом случае определяется выбранным быстрым алгоритмом и может

принимать большие значения. Для данного типа архитектур процессоров—г-'-----

разработаны программы моделирования и автоматизированного синтеза отлаженных микропрограмм.В- работе приведён листинг синтезированной микропрограммы вычисления 64-х-точечного ДКП.

Время выполнения быстрого алгоритма на таком процессоре определяется выражением *-ба ■ СЛ-ЮиТ ♦ .где - число вершин графа быстрого алгоритма.

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

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

т

-.1 -1 -1 Х»Ы - /. О-.! * 2 - 2 (Ы-1 •• х + 2 . СЫ-2 «X +. . . . >1 -1

+ 2 »• Ч-га * X). .. ) , к

и • £, Ц-Л * 2 - дробное двомчное представление >1

весового нножителя, х - отсчёт сигнала.

Например,для 12-точечного БПФ имеет

__-з -7

Ы» -1«к|з/2 - -1*0.868 - 1С1-2 -2 ), и операция умножения

сводится к двум операциям сдвига и сложения

-4 -3

1) у » х+х*2 2) г * х-у*2

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

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

' типа, ревизованный, например на ПЗУ.

ариМТЯКТМрЛ ТЛКПГП прпцяггоря ПЯГГМПТ11ЙНА применительно к ЕПФ, пла

которого помимо вычисления собственно коэффициентов преобразования

требуется вычислять ии модуль и умножать на весовую

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

предложено использовать спектральные модульно-комбинированные весовые

Функции,которые строятся на основе окна Ханна гшсредстьзн наложанил

компенсационной последовательности следующего вида!

~сн> 1 <Р) 1 <о) СО)

хк. ■ - ( I хк I - - ( | | * | хк-1 | )) ,

CD>

где xk - к-ый спектральный отсчёт ДПФ с окном Дирихле.

Моделирование такой спектральной весовой Функции показало значительные преимущества ей использования по сравнению с другими весовыми функциями.

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

На основные архитектурные решения.предлагаемые в

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

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

частности,рассмотрена задача доплеровской-фильтрации с использованием

БПФ в радиолакационных станциях управления воздушным движением с частотой повторения зондирукшего импульса Рз^ЮОО Ги. При этом

л - • '

принимаемый от цели эхо-сигнал есть промоделированный доплеровским- ,'

смещением эталонный ЛММ-сигнал. Таким образом.доплеровский сигнал можно

записать в Форме видеосигнала,дмскретизованного с частотой выборки £*э '

Зек м ) • |8 Ск о« | (со8(2»Гэ » к о» ♦ 1*в1п{21Гз « к ои>.

где • IVРз . Р» • 2уг/Х , X - длина волн эталонного излучения*

2

Г К - *о

i 2п

> - амплитуда сигнала.

1 Stk ot)| • А » ехр <-2.776

20

модулированного антенным лучом, к » 1,2,3,... -, (Ь-ût - момент времени с наилучшей видимостью цели.

С- учётом помех.представленных также в дискретной Форме n(kot). результирующий сигнал ножно записать

V(k ot) • SCk ot) ♦ ntk otî Модуляция эхо-сигнала антенным лучом приводит к тому,что при амплитудном пороге - 6 dB интервал уверенного привма сигнала.

составляет около 20 отсчетов.

Поскольку аэродромные радиолокационные станции работают в условиях отражений от местных предметов и различных поверхностей, то в программных моделях были предусмотрены в спектральной области помехи,вызванные такими отражениями. Кроме того учитывалась также неопределенность при обнаружении цели, вызванная ' явлением свёртывания частоты доплеровского сигнала fя вокруг частоты fз. Исходя из реальных условий,в работе сформулирован ряд требований.предъявленных к алгоритмам и структуре процессора БПФ.

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

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

векторно-разностному кодированию во временной области. Разработанные быстрые алгоритмы векторно-вазностного явухурпяняго «одироз»ння позволили выполнить компрессию речевого сигнала ..программными средствами типового компьютера (например . IBH PC/AT) в реальном времени. Коэффициент компрессии при субъективной оценке качества восприятия восстановленной речи.близкой к одному баллу (т.е. близкой к исходной) достигает- около десяти. Разработанные средства

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

информационно-справочных системах и для других применений.

Третьей областью применения рассмотрена компрессия изображений. В работе приведены ссылки на стандартные средства кодирования изображений и отпечены достоинства способов ' кодирования через преобразования. Поскольку НККТТ ДКП рекомендовано в качестве стандарта,то в работе приведены результаты моделирования алгоритмов компрессии аэрофотоснимков при использовании быстрых алгоритмов ДКП и ДПХ.В соответствии с этими результатами, предпочтительность кодирования через ДКП по величине коэффициента компрессии и по качеству восстановленного изображения является очевидной.Однако , по средстванреализации быстрых алгоритмов следует отдать предпочтение кодированию через ДПХ.

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

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

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

1. Разработаны и теоретически обоснованы математические модели и

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

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

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

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

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

ПОД с рекурсивным обновлением коэффициентов разложения..

/

6. Для быстрого вычисления вещественных сверток и корреляций,

длина которых Факторизована степенями числа два. получен новый тип ТЧП

Персеннав основных полях и быстрые алгоритмы, подобные, подобные БПХ.

которые обеспечивают, высокую точность вычислений и имеют значительные

преимущества по скорости и сложности 'реализации по сравнении с арифма-

*• .

тихой с плавающей запятой.

?.. Для двумерного дискретного косинусного преобразования в базисе

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

8. На основе синтезированных, быстрых ортогональный и теоретико-числовых преобразований разработаны высокопроизводительные архитектуры процессоров с программными средствами моделирования и от'ладки. Характерными признаками разработанных архитектур являются конвейеризация вычислений, ацикличность микропрограмм и однотактовый цикл выпол- 1 > нения микрокоманд.

9. С помощью натрично-блоковых рекурсий получена векторная' форма* сигнальных графов многомерных быстрых ортогональных и теоретико-числовых преобразований, являющихся наиболее доступными для инженерного применения. Использование векторных графов позволяет сократить сроки и повысить качество разработки программно-аппаратных средств реализации быстрых алгоритмов> их отладки.

10. На основе разработанного комплекса алгоритмов БПФ в поле комплексных чисел и архитектур процессоров, ориентированных на их реализацию. созданы адаптивные технологии' быстрой спектральной обработки ''

.радиолокационных сигналов с повышенный спектральным разрешением.

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

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

Разработанные быстрые алгоритмы со средствами реализации и моде-

лирования позволили создать новые и усовершенствовать известные (стандартные) технологии сжатия и обработки изображений.

ПУБЛИКАЦИИ ПО ГЕНЕ ДИССЕРТАЦИИ

1. Гагарин Ю, И. Рекурсивное преобразование Фурье через свертки. П Проблемы передачи информации П. 1989. N 4,с. 93

2. Гагарин К). И. Обобщенные быстрые преобразования сигналов по нечетно-периодическип ортогональный функциям .' // Радиотехника и электроника П. 1990 N 4 с. 774.

3. Гагарин Ю. И. Быстрые алгоритмы ' ДПФ на основе обобщенных матрнчно - рекурсивных форм // Известия BU30B СССР. Радиоэлектроника . Киев . 1989 , N 12 с. 51.

4. Гагарин Ю. И., быстрые алгоритмы дискретного преобразования Фурье на основе циркулянтной факторизации // Математическое обеспечение САПР и ГАП . - Ижевск ИМИ . 19S7 , с. 121.

5. Гагарин Ю. И. Процессор для рекурсивного ДП4> через быстрые свертки // Микропроцессорные средства обработки и отображения информации в системах управления и связи . Радио и связь . - М. < 1986, с. 66.

в. Гагарин НЗ. И. .Егоров В. В. Адаптивные быстрые преобразования Фурье с повышенной точностью вычислений . // Электронное моделирование .

- Киев! 1988 , N 6 с. 92. ,

7. Гагарин Ю. И. Обобщенный блочно - рекурсивный матричный метод построения быстрых алгоритмов ДПФ . ЛенМехИн-т - И. i 1989 - с. 20. Библиография В названий дел. в ВИНИТИ 05.06.88 , N 3614.

8. Гагарин Ю. И. Быстрые алгоритмы дискретного преобразования Хартли на основе обобщенных матрично - рекурсивных Форм. ЛенМехИн-т - И. i 1988

- с. 23 , Библиография 7 названий деп. в ВИНИТИ 05.05.88, N 3515.

9. Гагарин Ю. И. Лсевдогнездовые алгоритмы двумерных Фурье и Хартли преобразований цифровых сигналов // Известия BU30B СССР. Радиоэлектроника. - Киев ,1991. N 3. с; 8.

10. Гагарин Ю. И. Матрично - Факторизованнре обобщение гнездовых и простых множителей алгоритмов Фурье и Хартли преобразований . // Радиотехника и электроника - М. i 1992 , N 12 с. 2182.

11 Гагарин Ю.И. Характеризационно - инвариантное представление быстрых ьлгоритиов дискретного преобразования Хартли . // Логическое» управление) с использованием ЭВМ. i Тезисы докладов 11 Всесоюзного симпозиума . - Москва - Орджоникьдзе ■ 1S88, с. 152-155.

12. Гагарин Л. И. Обобщенные быстрые алгоритмы дискретного прьобРа?ования Хартли. .// сб. трудов ЛМИ. - Л. > 1988, выпуск 7.с. 167,.

13. Гагарин Я. И. Гагарин К. К). Теоретике числовые преобразования Мерсенна для быстрого вычисление вещественных сверток . длина которыч■ Факторизована степенями числа два . // Известия BÜ20B СССР . Радиоэлектроника. - Киев! 1991, N 12 с. 17.

14. Гагарин Ю. И. Гагарин К. Ю. Псевдогнездовью алгоритмы теоретико -

- числовых преобразований для быстрого вычисления вещественных и комплексных двумерных сверток. // Системц цифровой обработки и анализа изображений. - Рига« ИЭВТ. 1991 с? 105.

15. Гагарин Ю. И. Козлов В. Р. Шифрин В. В. Гагарин К.Ю. Программы моделирования и отладки алгоритмов и структур процессоров быстрых ортогональных и теоретико - числовых преобразований. // INFO-89. Труды международного симпозиума. - Минск« 1989, т. 2 с. 775.

16. Гагарин Ю. И Егоров В.В. Дискретное преобразование Гильберт? через быстрые свертки . П Методы и микроэлектронные средства цифровой обработки сигналов« Тезисы докладов Всесоюзной конференции . Рига! 1988 с. 167.

17. Гагарин И). И. Егоров В. В. Шифрин В. В. Быстрое вычисление корреляций и сверток на основе процессоров преобразования Ферма. // Труды ЛенМехИн-та, Л. i 1988, вып. 6 с.161.

18. Гагарин Ю. И. Козлов В. Р. Вычисление сверток корреляций через преобразования Фурье-Галуа средствами типовых ЭВМ. // Техника Средств связи. Системы связи.- Hi 1989

19. Гагарин Ю.И.Козлов В. Р. Шифрин В. В. Гагарин К.Ю. Системы моделирования и отладки алгоритмов и структур процессоров быстрых ортогональных и теоретико - числовых преобразований. // Логическое управление _с_ использованием. __ЭВМ______Труды 11-Всесоюзного симпозиума .--------

- М. i 1989 с. 114.

20. Гагарин Ю. И. Козлов В. Р. Гагарин К.Ю. Быстрые алгоритмы теоретико - числовых преобразований Нерсенна. // Логическое управление с использование« ЭВМ. Jpynu 13 Всесоюзного симпозиума,- М. »1990 с.163.

21. Гагарин Ю.И. Характеризационный анализ быстрых алгоритмов преобразований цифровых сигналов . П математическое' обеспечение интегрированных систем САПР и ГАП. - Ижевск, ИМИ, 1987, с. 116.

22. Гагарин (0. И. Обобщенное рёкурсивное представление .матриц преобразования Уолша К Автоматизированное проектирование мехэноэлектроннык систем . Тез. докл. Всебоюзн. Конф. - ,Ижевск 1985,

г. D9.

23. Гагарин Ю И. Алгоритм рекуррентного вычисления корреляций и сверток . // Автоматизированное проектирование механоэлектронных систем. Тез. докл. Всесоюзн. конф. - Ижевск 1985, с. 72.

i

24 Гагарин Ю. И. О рекуррентных алгоритмах статистической

обработки цифровых последовательностей в микропроцессорных системах . // Лог ическое управление в промышленности . Труды 7 Всесоюзного симпозиума . Ижевск ,1984. с. 155. -

26. Гагарин Ю. И. Шифрин В. В. Модульно- конбинировднные спектральные весовыо функции для дискретного преобразования Фурье . // Радиотехника к электроника.- И. ! 1992. H 2. с. 247.

26. Гагарин Ю. И. Шифрин В. В. 'Инструментальная система отладки

пикропгогрвммируриых вычислитольных устройств. // Техника средств связи . Системы связи, - M. t 1988. с. 51. -

27. A.C. N 1617440. Гагарин Ю. И. Гагарин К.Ю.Козлов В. Р. Устройство йля выполнения быстрого преобразования Уолшэ, - опубл. 30. 12.199СГ. бюл. N48.

28. A.C. N 1486833. Гагарин К. Ш. Гагарин Ю. И. Блок формирования адресов для преобразований Уолша. - опубл. 23. 06. 1989, бюл. N 23.

29. A.C. N 1606977. Гагарин (0. И. Гагарин К. Ю. Устройство для быстрых ортогональных преобразований, - опубл. 15.11.1990.бюл. N 42.

30. A.C. M 1725227. Гагарин KÍ. И. ШиФрин В. В. Процессор быстрых дискретных преобразований, - опубл. 07.04.1992. бюл. N 13.

31. Микропроцессор К584. Организация . функционирование и применение. Учебное пособие /Гагарин Ю. И.,Скорубский В. И. .Смирнов Ю. Н. М. i ЭКОС. 1982.'

32. Микропроцессорный комплект К539. Организация,функционирование и применение . Учебное пособие / Гагарин Ю. И. . Скорубский В.И , Чекмарев O.A. . Чижев A-A. M. i ЗКОС, 1982.

33. Математическое обеспечение микропроцессорных систем . Учебное пособие / Богданов В. В. . Гагарин Ю. И. , Герасимов И. В. , ПетровГ. А. , Родионов С. Ь. М. i ЭКОС, 1983.

34. Gagarin V. I..Qvchlnnlcov G. R..MesheryaKov S P. Signal processors for coir.pressing of pictures and spech with transform. // Proc. ' lnt'. conf. signal proctsslnfl. Rlfiat 1990, v. 1. p. 97.

35. Гагарин H). И. . Соколов A.M. Сжатие изображений методом рекурсивного преобразования Уолша в вычислительной сети '. // Локальные вычислительные сети . Тезисы докладов Всесоюзной конференции.- Рига« 1987 . с. 83

38. Гагарин Ю.,И. - Псевдогнеэдовые алгоритмы 'Двумерного дискретного, косинусного преобразования. // Электронное моделирование. Киев!1991 N 2 с. 107.

37. Гагарин Ю. И. Быстрое аппроксимированное дискретное косинусное преобразование. // Техника средств связи . Системы связи.. 1989, с.23

38. Гагарин tu. И. ьыстрыи алгоритм увкирдивпого ЯП» чсроз сгертк:;. // сборник трудов ЛМИ. - Л. «1986, вып. 8. с. 108.

39. Гагарин Ю. И- Гагарин К. Ю. Козлов В. Р. О мультипликативных группах и ортонормировании* векторных пространствах в простых полях Галуа и в |юльиах, образованных по модулю чйсел Ферма. // Сборник, научных трудоа СПбГТЫ, M 457. ВТАРЭ, 1995. с. 108.

40. Гагарин Ю. И. Гагарин К. Ю. Быстрое векторно - рааностнов кодированное цифровых речевых сигналов и его применение в мнтелектузлышм системах .' // Триды второго международного симпозиума " Интьльктуг»льныа системы Россия. С.- Петербург 1 - 4 июля 199o.с.Ш

Л i Vi »..-