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

!/2Е:И:С7:ЕРС1ВС образс ЗАБЙЯ

РОССИЙСКОЙ ФЕда?/-.ДИИ Чувашский государственный университет: имени И.Н. Ульянова

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

? Г 5 ОД

ГАЛА1ШНА НАТАЛИЯ АНДРЕЕВНА £ П

СИНТЕЗ, ОПТИМИЗАЦИЯ И КОМПЬЮТЕРНОЕ ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ БЫСТРЫХ НШОЗИЦИОННЫХ АЛГОРИТМОВ СПЕКТРАЛЬНОГО

АНАЛИЗА

05.13.16- Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (технические науки)

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

Чебоксары 2000

Работа выполнена в Марийскок государственном техническом университете и Чувашском государственном университете имени И.Н. Ульянова

Научный руководитель:

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

доктор технических наук, профессор Е.К. Лебедш

доктор технических наук, профессор В.А. Пссошин

кандидат технических наук, доцент В.И. Антош®

Ведущая организация - Всероссийский научно-исследовательский институт релестроенш.

Защита состоится 17 марта 2000 года в 15 часов в аудитории В-310 на заседании диссертационного совета К064.15.07 в Чувашском государственном университете имени И.Н. Ульянова (428015, г.Чебоксары, Московский просп., 15).

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

С диссертацией можно ознакомиться в библиотеке Чувашского государственного университета имени И.Н. Ульянова.

Автореферат разослан 15 февраля 2000 года.

Ученый секретарь

диссертационного совета __—

к.т.н., доцент /Ш/уС^^----- В.А. Байшулшш

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

Актуальность проблемы. Классические научные достижения в области статистических исследований свойств сигналов и устройств сбора, хранения и регистрации данных отражены в работах Л. С. Гугкика, П. А. Бакулева, Ю.Г. Сосулина, Р.Л. Стратоновича, В.И. Тихонова, Б.Р. Левина и др. Особое место :реди них занимает цифровая обработка сигналов (ЦОС), главными источниками развития которой стали исследования ряда отечественных и зарубежных ученых: С.З. Кузьмина, В. А. Лихарева, Б. Гоулда, Ч. Рейдера, Д. Даджиона, А. Антонью, Л. Рабинера, и др., а также успехи в области микроэлектроники и компьютерных систем. Однако перед исследователями по-прежнему остро стоят проблемы эбеспечения высокой вычислительной эффективности: уменьшения аппаратурных затрат, увеличения быстродействия, точности и отказоустсйчх'зости устройств ЦОС. Поэтому в настоящее время актуальны вопросы применения алгоритмических методов улучшения качества вычислительных процедур и, в первую очередь, использования теоретико-числовых алгоритмов (ТЧА), представленных в работах Дж. Макклеллана, Ч. Рейдера, Р. Блейхута и др. К сожалению, использование ТЧА не всегда оправдано я часто уступает БПФ. Поэтому важен и актуален второй путь повышения качества ЦОС - непозихдаонное кодирование сигналов на выходе АЦП. В [щссертадии рассматривается одна из этих непозиционных систем - машинная фифметиха в системе остаточных классов (СОК). Ее суть состоит в использовании совокупности неотрицательных вычетов по группе взаимно простых оснований Ns (1 Г- округление в сторону меньшего целого):

хs (кТ) = х{кТ) - ll х{кТ) /Ns Г9 Ns =« х(кТ)» mod Ns,

В работах Лебедева Е.К. создана и получила развитие теория ЦОС в СОК, •исследованы методы синтеза устройств непозиционной оптимальной, линейной i нелинейной фильтрации марковских сигналов и оценивания ее параметров, 1редложены также эффективные методы решения задач построения ^позиционных ЦФ и алгоритмы оценивания их эффективности, синтезированы отказоустойчивые фильтры, обладающие свойствами самовосстановления результатов.

Одна:«) по-прежнему не решен ряд проблем. Среди них важное место ¡анимает необходимость улучшения параметров многомерных теоретико-шсловых алгоритмов ДПФ и БПФ при их реализации з СОК, когда

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

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

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

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

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

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

5. Разработкой моделей и компьютерных программ исследования позиционных и непозиционных алгоритмов БПФ; разработкой программного комплекса для моделирования и интерактивного синтеза на ПЭВМ устройств

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

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

Научна® шгавмзиа. В диссертации исследуются новые методы синтеза и нализа эффективности устройств ДПФ и БПФ в СОК. При этом получены педующие новые результаты:

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

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

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

4. Исследованы проблемы реализации на позиционных сигнальных роцессорах быстрых непозиционных алгоритмов. Дана оценка вычислительной ффективности такого решения и показаны методы еш оптимизации.

5. Создан программный комплекс, реализующий модели алгоритмов БПФ СОК и позволяющий провести интегральный синтез и оптимизацию

араметров непозиционных устройств БПФ. Оценены ошибки преобразования найдены экспериментально оптимальные варианты реализации БПФ в СОК.

Научная новизна и приоритет исследований подтверждаются авторским видетельством СССР.

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

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

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

Реализация и вгаедршше результате® работы. Основные результаты диссертационной работы были использованы:

1. В учебном процессе на кафедре информационно-вычислительных систем Марийского государственного технического университета по дисциплинам: "Микропроцессорные системы" и "Теория и методы цифровой обработки сигналов" по специальности 2201 "Вычислительные машины, комплексы, системы и сети".

2. В учебном процессе на кафедре информационных технологий Чувашского государственного университета имени И.Н. Ульянова по дисциплинам "Быстрые алгоритмы цифровой обработки сигналов", "Теоретические основы защиты информации" по специальности 2201 "Вычислительные машины, комплексы, системы и сети" .

3. Результаты диссертации использовались при выполнении НИР:

3.1. "Исследование и разработка принципов построения программируемых вычислительных систем обработки радиолокационных сигналов" (отчет деп. в ВИНИТИ, № 0287.0025455).

3.2. "Методология проектирования специализированных микропроцессорных систем с эффективными алгоритмами. Аппаратная реализация мультипроцессорной непозиционной МПС обработки сигналов. Создание пакета функциональных программ" (отчет деп. в ВИНИТИ, № 0286.064966).

3.3. "Разработка и исследование микропроцессорных систем сбора, обработки и регистрации данных" (отчет деп. в ВИНИТИ, №

0289.000:798).

3.4. "Разработка методология проектирования специализированных микропроцессорных систем с эффективными алгоритмами. Построение и анализ вычислительных теоретико-числовых алгоритмов обработки сигналов" (отчет деп. в ВИНИТИ, № 0287.0067112).

3.5. "Разработка и исследование оптимальных алгоритмов интеллектуального интерактивного абонентского доступа по гибридным сетям ЦСИО" по единому заказ-наряду Министерства образования Российской Федерации (1999-2000 гг.).

Анробашциш работы. Основные положения и результаты диссертационной »аботы докладывались и обсуждались на международной конференции Перспективные технологии в средствах передачи информации" (г. Владимир, 995 г.), на всесоюзных конференциях "Микропроцессоры-85" (г. Зеленоград, 985 г.), "Информационно-измерительные системы-93" (г. Куйбышев, 1993 г.), а всероссийских конференциях "Информационные технологии в электротехнике [электроэнергетике" (г. Чебоксары, 1996), "Динамика нелинейных дискретных лектротехническях и электронных систем" (г. Чебоксары, 1997, 1999 гг.), а акже на республиканских и университетских научно-технических конференциях г. Йошкар-Оле в 1983-1997 гг. и в г. Чебоксары в 1997 г.

Публшкяшцига. По результатам выполненных исследований по теме ;иссертации опубликовано 20 печатных работ, в том числе авторское видетельство СССР, 5 статей, 5 тезисов докладов на конференциях, а также 3 рошгоры и 6 отчетов по НИР, депонированных в ВИНИТИ.

На защиту выииисягтеж

1. Методика и вычислительные алгоритмы синтеза одномерного и [ношмернош устройств поразрядного ДПФ (ПДПФ), а также разработанные хемы соответствующих устройств ПДПФ.

2. Алгоритмы оптимизация устройств ПДПФ и программное обеспечение ля их компьютерного интерактивного синтеза.

3. Алгоритмы реализации БПФ в системе остаточных классов.

4. Многоканальное устройство БПФ в СОК.

5. Алгоритм индексирования чисел в коммутативном кольце вычетов.

6. Алгоритмы и программа компьютерного синтеза БПФ в СОК с четом локальной и глобальной оптимизации числа каналов СОК, весовых оэффициентов и разрядности данных по методам нормирующего

множителя и кулевизации.

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

8. Математическая модель БПФ в системе остаточных классов и реализующей ее программный комплекс интерактивного синтеза и оптимизации устройств БПФ в СОК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, приложения. Материал изложен на 158 страницах текста компьютерной верстки, в том числе основной текст - на 121 стр. В работе содержится 8 таблиц, 52 рисунка. Список литературы включает 91 наименование.

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

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

(1)

п=О

где р-к- к-ая гармоника спектра для чисел х(п),

=со5(2

В спецпроцессорах обычно используются числа х(п) в дополнительном

коде с фиксированной запятой *(")- хг(")2 -хзн{п)2 ^ где К- число

г = О

разрядов чисел в последовательности х(п), хзн(п)- знаковый разряд чисел. Следовательно,

п = О 5

^(з») = • 5[х„(И)-1] 2*"1.

п=0 5

Л-2 г=О

где 5[0]=1; г = £,и = 0,ЛГ-1.

В диссертации приведена схема поразрядного одномерного вычислителя ЦПФ. Объем памяти используемых в схеме ПЗУ для ^ £?шм = 2 ' где

1^23 - разрядность , а полное время преобразования составит ИД тактов. Зсли где Ъ -разрядность ПЗУ, то число т корпусов ПЗУ определяется

гак: из общего числа разрядов ПЗУ к = разрядов вьщеляется на код

гастоты, х = 2-\о%разрядов - под часть выборки сигналов. Тогда п=\] М5/х I. Например, если N=64, то к = =6. При2=11 х=2-к=5. В этом

:лучае ш= ] 64/5 I =13 (_| |_ - округление в большую сторону). Показано, что )дномерное устройство ПДПФ имеет быстродействие в два раза выше, чем БПФ. Эднако одномерный алгоритм ПДПФ может использоваться до М3=64-256. При ^>512 от одномерного К- точечного ПДПФ можно перейти к многомерному 1ДПФ через мерные в соответствии с алгоритмом Гуда. Многомерное ПДПФ »держит V шагов по М5 точек для всех £ = ^. Такое преобразование включает

яедующие этапы:

1. Переиццексация (реконфигурация) данных

Х(п)->Х(пъп2,-,п3,...п„),

V

п =< ^и^/Л^ > тосШ. 5=1

2. Вычисление коротких точечных ПДПФ.

При у=2 сначала вычисляются N N - точечных ПДПФ

К(к1гп2)= I Цхг{пьП2)-т^Х 2 2Г ■ «1=0 1 '

И,—1

Затем осуществляется М, вычислений Ы2- точечных ДПФ

п2= 0

^ №,¿2) = (Мг)" ^ (М"2) .

3. Наконец, переупорядочиванием выходных значений многомерного массива определяется Рк.

В диссертации приведена защищенная авторским свидетельством схема двумерного устройства ПДПФ, которое при N,=63; М2=64 осуществляет до 4032 точек преобразования.

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

Для сокращения объема памяти для ПДПФ проведено оптимальное разбиение последовательности хг(пТ) длиной N на т частей длиной х. Тогда соотношение (1) принимает следующий вид:

/Ъ(г)=Е I (2)

'=1к = ¡х

где А=(Ы /х)-1, В=(1+1)х-1. Величина х определяется, исходя из разрядности Ъ адресных шин ПИЗУ и числа отсчетов Ы5, которое обуславливает число страниц в ППЗУ у=] 1о£2М51. На каждой странице ППЗУ хранятся яу=2х наборов вариантов сумм для различных кодов х - разрядного бинарного слова. Минимальный объем памяти обеспечивает решение, при котором из х -разрядного кода дополнительно выделены х, - разрядные части, объединенные в группы по ух бит, подаваемые на дополнительную память. Целью оптимизации является определение значений х, х и у, минимизирующих целевую функцию

&*=пм][11:, где ш, I и с соответственно число корпусов, число сложений и объем памяти ППЗУ в е-м разряде. В случае Z>x+y целевая функция равна

р* =(Л(х-1 +1)3(1'-1 + 1)2Х+У(2~Х1 +2УХ1у~1)- Исследования ф* показывают, что

1 области допустимых значений есть локальный минимум при х^ 1. Локальный шнимум х[2]=3 для N<16, а при N>32 х[2]=4. Экстремум по v определяется из

рансцендентнош уравнения 2Х1^+1)(ж1(к+1)1п2-((/ + 3)к-1) = 2- имеющего

динственное решение: при х,=1 целочисленное значение у=3.

При использовании ППЗУ с малым объемом памяти (г<х+у) для схем

юз дополнительной памяти целевая функция ф^ = 2уМ3г~32х(х+у+г)3х~3 ■

Линимум Ф3 существует в точках х[3]=3 и х[3]=4.

При введении дополнительной памяти ф\ =Фз(1+к~1)2(2_;Г1 +У~12Х1У~Х). ¡скальный экстремум <£>* по х в области допустимых значений (х>0) щределяется в точках х[4]>3...4. Локальный минимум по х1 определяется

13 уравнения 2Х1 +2Х1^~Х =0, имеющего единственное решение при :1[4] = 3...4/(У + 1). Поиск экстремума по V приводит к решению

рансцендентнош уравнения г2.?12::'1""!' +у(х12ух1~х1п2-2ух1~х -21~Х1)~6(21/Х1~Х)=0.

Зтсюда для х[4]=3, у=3 х =1, а при х[4]=4, У=4 х =1. Кроме того, отметим, что * *

Р2пш1 <ф41шп'

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

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

Наибольшее влияние на число каналов БПФ в СОК оказывают иксимальный диапазон результата ршах, который зависит от числа отсчетов Н, азрядности ^ данных х[пТ] и разрядности весовых коэффициентов Wk:

Разрядность И входных чисел определяется динамическим диапазоном

D (дБ) входных сигналов: R^Dj/6.

Величина R^ выбирается, исхода либо кз точности дискретизации е либо из заданного отношения среднеквадратичного значения (СКЗ) ошибки к СКЗ сигнала е2,либо принимается, чпго R^HR^:

R2 =log2(l + 0.5/s1); 0<е<<1; (3)

£2=0.5(log2log2Wi-log26-log2e2); 0<s2«l; (4)

R2=Dl/6. (5)

Отсюда следует основное соотношение для теоретического определения числа каналов v и модулей в СОК при реализации N- точечного БПФ:

log2 р ^ log2 N + R\ +R2 -1. (6)

Зная N, D, и задаваясь е,(е2), из (3 - 6) можно определить систему модулей СОК {Ns}, минимизируя v и (или) R^. После вычисления N, D, и е определяется Rsmax и система модулей {Ns}. Так можно вычислить верхний предел v и {Ns}. Он носит теоретический характер. При этом ртах>220. Моделирование на ПЭВМ показывает, что практически максимально возможный результат не превышает 218 для подавляющего большинства алгоритмов.

Для осуществления вычислительной операции "бабочка" в каждом s-m СОК необходимо провести операции сложения и умножения по соответствующему модулю (будем рассматривать случай прореживания по времени):

CS=AS+BSWÏ>

Ds=As-Bswb=As+Bsvb\ где CS=<C> mod N s ; A? =< A > moàNs ; Bs =<B > mod Ns ; Ds =<D> mod Ns ; Ws =<Wk >moàNs^Vk =<N/2-Wk > mod Ns. Отметим,

что <Wk >=<N12-Wk >-<Wk + N/2>= VkVk + N/2=Wk.^mсоотношения

используются при построении схемы БПФ в СОК. Схемы базовых табличных модулей (ТМ), реализующих операцию "бабочка" в СОК, представлены на рис. 1 и 2.

Рис. 1. Базовый табличный модуль для К3=3...4

Рис. 2. Базовый табличный модуль для 1^=5...6

Операнды подаются на пшну адреса ТМ, с информационных выходов ягорых снимаются числа С3 и 03. При К <3...4 объем памяти ТМ составляет 56 байт, а при II =5...6 -не превышает 4Кбайх Аппаратурные затраты «еныпагогся, а быстродействие увеличивается, если функциональные модули СОК реализованы на комбинированных операционных схемах КОС, «пголненных в виде заказных СБИС, или синтезированных на ПЛМ(ПЛИС). а рис. 3 показана такая схема, в которой совмещен ряд логических операций I" и "ИЛИ". Можно существенно упростить вычислительный блок,

штывая, что если <В1Ук >=г, то <ВУ^ >=< >= Лг - г.

Рис. 3. Схема СБИС для вычисления БПФ на КОС

В диссертации приведена схема устройства для вычисления -точечного БПФ в СОК. Она содержит по V арифметических блоков, блоков определения вычетов и блоков памяти весовых коэффициентов (у-число каналов СОК), а также блох восстановления результата.

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

Для определения первообразных корней и расчета индексов I

(антииндексов Г1) необходимо решить задачу нахоэвдения остатка от деления

числа М ы на число К, хде М,Ы,К - натуральные числа. Сложность этой задачи заключается в необходимости решения сравнений для значений модулей

ЛГ^ > 1000...2000, чтобы обеспечивать минимальное количество каналов БПФ

в СОК.

В диссертации найден алгоритм вычисления q, 1А, , который при произвольно больших N3 имеет следующий вид:

1. /0 = 1, /дг5_ 1 = 1, где /„ - остаток от деления qn / N5

V?

2. 1п+1=1г,'1-Ч-1ыт

ЛЪ

Если In+i = 1, то q не является первообразным корней. Идти к 7 и = « +1. если п < - 2, то идти 2

q является первообразным корнем, печатать /0, /j,...,/д^ _ j Идти к 8

Взять другое ? или TV^, идти к 1 Останов

Численные расчеты 1А и Z^1 впервые позволили найти систему модулей #$>1000 для реализации индексных цифровых устройств спектрального анализа.

В третьей главе приведен сравнительный анализ и оптимизация позиционных и иепозиционных устройств спектрального анализа и фильтрации при их реализации на позиционных сигнальных процессорах (Digital Signal Processing - DSP).

DSP 1-го поколения, построенные, как правило, по архитекторе ОКОД, не позволяют напрямую реализовывать алгоритмы непозиционной обработки. В этом случае обработку в каждом из каналов СОК организуют на отделвных DSP, что ведет к росту аппаратурных затрат. При этом наблюдается проигрыш и по быстродействию. Сравнительная оценка различных устройств ЦОС, реализованных на DSP первого поколения (типа TMS320C10), приведена на рис.4.

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

t, МО

tms320c10

Рис. 4. Сравнительная оценка быстродействия устройств БПФ для TMS320C1Q

При реализация устройств ЦОС на ОБР 2-ш поколения выигрыш позиционных устройств по отношению к непозиционным сохраняется. Сравнительная оценка быстродействия позиционных и непозиционных

Рис. 5. Сравнительная оценка быстродействия устройств БПФ для TMS320C20

Перспективной является реализация непозиционных устройств ЦОС на DSP третьего поколения. Эти процессоры используют архитектуру ОКМД и МКМД, что делает возможной реализацию устройства ЦОС в СОК на одном DSP, использующем режим мультипроцессорной обработки. При реализации непозициоыных устройств ЦОС на DSP третьего поколения с более современной архитектурой, высоким быстродействием, распараллеливанием операций при равных аппаратных затратах проигрыш непозиционных устройств ЦОС по быстродействию становится минимальным (рис. 6).

t, мксф 546

500 410 400

30

200 ■■

10

0

512

1024

Рис.6. Сравнительная оценка быстродействия устройств БПФ для Sproc 1400

Кроме этого непозиционные устройства ЦОС имеют резервы для (Тзеличения быстродействия, так как возможна оптимизация ЦОС в СОК, когда ■шсло умножений и сложений сокращается до 90 %.

На рис. 7 показана оценка быстродействия позиционных и непозиционных устройств ЦОС при их реализации на DSP четвертого поколения, которые юддерживают режим мультипроцессорной обработки.

Рис.7. Сравнительная оценка быстродействия устройства БПФ при использовании DSP четвертого поколения Методом имитационного моделирования проведено сравнение юзиционных и непозиционных устройств ЦОС с учетом такой возможности рис. 8).

Рис. 8. Сравнительная оценка быстродействия нерекурсивного ЦФ-IV при мультипроцессорной обработке в DSP четвертого поколения

Приведенные расчеты показывают, что непозиционные устройства ЦОС фи реализации на DSP по прототипу имеют некоторый проигрыш по ¡ыстродействию, если не проводить оптимизацию непозиционных устройств.

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

1) отсутствуют ошибки округления и повышается точность вычислений;

2) каналы СОК работают независимо, что позволяет динамически менять их загрузку;

3) БПФ в СОК обладают повышенной отказоустойчивостью, причем при сбоях информация самовосстанавливается;

4) многоканальная структура СОК позволяет оптимально использовать преимущества мультипроцессорной архитектуры.

Перспективным направлением развития непозиционных устройств ЦОС является их реализация на DSP, ориентированных на обработку информации на непозиционных спецпроцессорах в СОК. На рис. 9 показана сравнительная оценка быстродействия позиционных и непозиционных устройств БПФ при их реализации на штатном DSP 3-ш поколения и специализированном DSP непозициокной обработки.

Рис. 9. Сравнительная оценка быстродействия устройства БПФ при их реализации на DSP - СОК

Далее в третьей главе рассмотрена оптимизация непозиционных устройств цифровой обработки сигналов. Ее смысл заключается в повышении вычислительной эффективности, основанном на исключении или замене сложных операций на более простые и быстрые путем подбора модулей СОК при проектировании устройств БПФ. При этом уменьшается количество каналов СОК; разрядность устройства ЦОС; число арифметических операций.

Можно выделить следующие основные этапы оптимизации:

1) первоначальный выбор множества оснований СОК, минимальных по йтратам и времени;

2) оптимизация выбранных оснований путем изменения их до \¥± 1; Ш+2 I подсчета аппаратурных затрат и быстродействия во всех случаях;

3) вычисление погрешностей.

Рис. 10. Синтез БПФ в СОК и его оптимизация

Синтез устройства БПФ в СОК сопровождается вычислением коэффициентов оптимизации: Кор1 =0/2 ■ V ■ М, где V- число каналов СОК;

V - число точек спектрального анализа или порядок фильтрации; <2 - показатель штимизации: сокращение числа алгебраических операций для »птимизированного алгоритма..

Блок-схема синтеза БПФ и ЦФ в СОК приведена на рис. 10. При оптимизации коэффициентов БПФ - СОК получены результаты, показанные в табл. 1. Ею можно пользоваться при синтезе многомерных БПФ, »еализугохщих алгоритм Гуда.

Таблица 1

N 3 5 7 11 13 17 19 31 32 37

<3 9 14 1В 26 27 35 39 62 72 69

На рис.11 - 13 показаны зависимости показателя оптимизации р (в

процентах) от порядка цифровых фильтров N при различных частотах среза и заграждения ,УУс и . г также для разных форм аппроксимации АЧХ: фильтров Баттерврта, Чебышевг 1 и 2 рода и эллиптического фильтров. При этом в диссертации рассмотрены гак фильтры низкой чатоты - ФЫЧ, так и высокой -ФВЧ. При исследовании выбрана частота дискретизации ¥д=50 кГц.

<3

■ N

Рис. 11. Зависимость (2=®(К) для ФВЧ Баттерворта

5 "'

О

4 5

\Ус=2хГц, \У3=7.5кГц Рз=50кГц

Рис. 12. Зависимость (5=Г(М) для ФВЧ Чебышева I рода

Wc=5кГц, 1А'з=7.5кГц Ра=50кГц

Рис. 13. Зависимость 0|=Г(М) для эллиптичесгош ФВЧ

«о

6

1->

<3

5

10

На рис Л 4. приведена зависимость коэффициента оптимизация Кор( от айда аппроксимации ЦФ. Особо отметим тот факт, что на величину К влияет

начение нормирующего множителя (1. Программа моделирования вычисляет качения с1, при которых Кор=гпах 1 ри реализации схем СПП и СОП.

качения с1, при которых Кор=гпах и ошибка Б=тт. Это значение учитывается

Корг 0,9

0,6

0,3

Батгерворта

Чебышева 1

0,67 0,64

0,6 1

0,57

рж рж

нч

вч

0,42

Чебышева 2 Эллигггич.

Рис. 14. Зависимость коэффициента оптимизации Кор( от вида аппроксимации (рж, нч, вч - режекгорный, низкочастотный и высокочастотный фильтры)

нч. вч

Исследования показали, что при возрастании порядка цифровой »ильтрации коэффициент оптимизации стабилизируется в среднем на уровне 0-70 % от числа исходных алгебраических операций, но всегда можно найти кстремум, достигающий значений Кор(шах=90-95 %. При этом форма ппроксимации АЧХ играет незначительную роль.

Приведем несколько примеров реализации БПФ в СОК, полученных юделированием при глобальной оптимизации, когда число множителей может ыть вообще исключено, но каждый шаг алгоритма Гуда требует кодирования / егодирования. Например, при п1=7 модули, обеспечивающие максимальный ээффициент оптимизации Кор=82 %, равны: N,=32; N¡=47; N,=61. При п2=8 1ор(=100 %, если выбрана система N,=31; N¿=47; М3=59 ...

При локальном экстремуме число умножений несколько увеличивается, о исключаются промежуточные этапы восстановления результата. Например, ри N,=31; N =43; N^57 коэффициенты оптимизации равны соответственно: ри п,=7 Кор=71 %; при п,=8 Кор=90 %; при п =9 Кор=63 %; при п=11 Кор=64

%; при 11=13 К р(=64 %; при п,=16 Кор(=71 %.

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

чисел ^ = Аг1,А,2,...,Аг|', у шорых ПЛ'з ^ 216 -220 при минимальной сумме

разрядности этих элементов; погрешность, вносимая перекодированием ¥/ в СОК; сумма остатков для контроля максимальности результата; коэффициент оптимизации; нормирующий множитель <1. Для этого последовательно производится поиск N при изменении ё. Далее находились наиболее оптимальные множители й для фиксированных наборов N. Следующим этапом был выбор наиболее выгодного сочетания из набора п1, п2, пЗ, произведение

1 у

вторых > 210. Погазано, что сочетаниеп1=8, п2=11, п3=13 при ПЛ^ - 2 имеет

Кор(тах=76%. При оптимизации удобно пользоваться графиками зависимости ошибок от нормирующего множителя (I. Один из них приведен на рис. 15.

Опт. % Точек ЕШ): 64

41.(

Ост 419

244

ГЬгр 1.923

0.485

N,• = [27,49,50]

(ГЩЗ] = 850

17

17

40

40

17

40

Рис. 15. Зависимость результата от множителя <! при Р> 216

В четвертой главе описывается программный комплекс моделирования

и автоматизированного синтеза непозиционных устройств БПФ. Он содержит

четыре блока программ: геа!_т1; орйпи; геа1_тос1 и независимо работающую

рогршму расчета индексных устройств I.

Программа real_ml предназначена для моделирования быстрого реобразованкя Фурье (БПФ) применительно к входному потоку данных с роизвольным числом комплексных переменных.

Программа optima предназначена для оптимизации данных для БПФ в истеме остаточных классов. Программа осуществляет оптимизацию БПФ по езультатам работы программы realjrnl.

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

Есть дна пути оптимизации непозиционной системы: первый -птимизирует вычислительный процесс по минимуму числа разрядов и по авенству весовых гоэффициентов БПФ и модулей СОК (или их отличию на :1, ±2); второй - в реальном времени приводит к нулю некоторые разряды самого исла. Тот и другой путь вносят в вычисление спектра определенные погрешности , которые необходимо учитывать и выбирать преобразования так, чтобы £<smm. Совмещение двух способов оптимизации, а также отыскание рекомендуемых истем модулей для непозиционных БПФ, сравнение характеристик этих реобразований с позиционными является основной задачей программы аделирования.

Для выполнения моделирования достаточно иметь следующие файлы: ialjml.exe, optim.exe, real_niod.exe (исполняемые файлы), dpfS.dfc (файл ходных переменных) и файл koef (файл таблицы коэффициентов).

Для работы с программой необходимы следующие ресурсы: компьютер ЗМ PC 286/386/486/Pentium или другой с ними совместимый; 640 Кб перативной памяти или больше; EGA монитор или выше; оперативная система IS-DOS версии 3.3 и зыше или операционные системы, способные эмулировать су ОС; 200 Кб свободного места на диске для хранения программы и входных выходных данных; 3,5 или 3,25 дюймовые накопители. В программе оделирования, написанной на языке PASKAL, использованы однонаправленные исковые структуры данных. В качестве входного и выходного потоков данных ыбраны текстовые файлы, что обусловлено: возможностью долгосрочного и здежного хранения данных на диске; наглядностью данных; возможностью ;спрсблемного использования данных файлов другими программистами.

Основные результаты работы программы.

При моделировании определяются погрешности перекодирования для

различных практически важных случаев, а также и оптимальные значения модулей СОК и требуемые режимы оптимизации. В таблице 2 показывается зависимость среднеквадратичного отклонения от системы оснований и шага нулевизации при неизменных входных данных. Серым цветом выделены случаи, соответствующие выходу весовых коэффициентов за пределы существования, когда | sin | или | cos | >1.

Таблица 2

Шаг оптимизации

Система Оснований Шаг 1 Шаг 2 Шаг 3

3, 5,7, 11 0,007 0,270 17849

3,7, 11, 17 0,012 Ш 1,512

3, 7, 17, 19 0,006 1,003 ÍSi?.8S

5,7, 11, 23 0,015 ГШ 17355

5, 7, 43, 59 0,002

3, 11,31,47 0,002 0,074 1,438

3,7,23,31 0,005 Кш. ШЙ',376

3,7, 11, 37 0,001 0,076 &464

7, 11, 17,29 0,044 V у;/.'

3, 5, 7, 59 0,001 fcboí ЬЛ26

ЗАКЛЮЧЕНИЕ

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

1. Синтезирован и исследован алгоритм поразрядного одномерного ДПФ (ПДПФ), использующий табличные процессоры. Большинство арифметических операций в нем выполнено на этапе проектирования; сигналы, подлежащие обработке, сгруппированы, что ведет к увеличению быстродействия устройств спектрального анализа. Ограничением на применение одномерного ПДПФ является число сгруппированных точек отсчета, которое не превышает 64-256 для современных СБИС и БИС ППЗУ и ПЛМ. Разработаны и исследованы высокоэффективные вычислительные алгоритмы многомерного ПДПФ для спектральной и корреляционной обработки сигналов при произвольно большом числе отсчетов сигнала. Показано, что многомерный ПДПФ имеет высокое быстродействие и минимальные ошибки округления. Представлены схемы технической реализации многомерного ПДПФ. Исследованы шути оптимизации

ДПФ> по многомерной целевой функции, зависящей от союл^тпности аппаратурных временных затрат. Разработаны вычислительные алгоритмы и программное 5еспечение для инпгеракшвного синтеза поразрядных устройств ДПФ. Алгоритмы шпьютернош исследования этих устройств улучшают качественные ха-даеристики ПДПФ, обнаруживают идентичные алгебраические операции и Зеспечивают программирование ПЗУ, ПЛМ (или ПЛИС) в диалоговом режиме в »ответствии с синтезируемыми алгоритмами. Это дополнительно увеличивает »мислжтельнуго эффективность устройств поразрядного спектрального анализа, жлютая из поразрядных алгоритмов до 90 % алгебраических операций..

2. Исследованы алгоритмы реализации БПФ в СОК. Д аны рекомендации по .1бору и оптимизации системы модулей для кепозиционных процессоров БПФ. интезированы непозиционные операционные устройства для практической ¡ализации базовых операций БПФ в СОК. Описаны программы для вычисления (эффициенгов БПФ в кольце вычетов и выбора системы модулей СОК. Разработано исследовано многоканальное устройство для БПФ в СОК. Показано, что оно 'личается более высоким быстродействием по отношению к классическим схемам 1Ф. Разработан метод улучшения вычислительных характеристик БПФ в СОК. сшучен алгоритм индексирования чисел в коммутативном кольце вычетов для учаев произвольно больших модулей, что ослабляет зависимость числа каналов Ж от максимального результата, снижает аппаратурные затраты и увеличивает казсустойчивость и быстродействие БПФ в СОК. Разработаны алгоритмы и »грамма интерактивного синтеза и оптимизации БПФ в СОК. Использование щ этом свойств целых чисел в коммутативном кольце вычетов позволило упростить пгоритмы непозиционного БПФ с коэффициентом оптимизации в среднем до 60

Достижимо значение Кор1=100 %, если проводится глобальная оптимизация, ложниющая алгоритмы БПФ.

3. Исследована возможность реализации непозиционных алгоритмов ¡ектрального анализа на сигнальных процессорах различных поколений и 13ЛИЧНОЙ архитектуры. Показано, что применение алгоритмов непозиционных урье- преобразований в обычных спецпроцессах не обеспечивает выигрыша в -лислительной эффективности. По этой причине, если создание непозиционных ВИС невозможно, что теоретически всегда обеспечивает преимущества позиционных устройств ЦОС, то обязательна оптимизация алгоритмов Фурье-¡еобразовашта в СОК. В этом случае достигается выигрыш непозиционных торигмов по быстродействию, аппаратурным затратам, ошибкам округления и 'казоустойчивости. Вычислены и проанализированы системы модулей, еспечивающие максимальный коэффициент оптимизации.

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

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

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

1. Галаннна H.A., Лебедев Е. К. Интерактивный синтез устройств ПДПФУ /М., 1986. Деп. в ВИНИТИ. 17.06.86, №4461-886. 64 с.

2. Галанина Н. А., Юферев А.Е. Оптимизация непозиционных алгоритмов спектрального анализа// Информационные технологии в электротехнике и электроэнергетике: Тез. докл. всерос. межвуз. научн.-техн. конф./ Чебоксары: Изд. Чуваш, ун-та, 1996. С. 74-75.

3. Галанина H.A., Лебедев Е.К. Спектральный анализ в коммутативном кольце вычетов. М., 1986. Деп. в ВИНИТИ. 10.04.86 № 4Ш-В86. 72 с.

4. Галанина H.A., Лебедев Е.К., Давыдов O.E. Повышение эффективности фильтрации сигналов в цифровых системах абонентского доступа// Динамика нелинейных дискретных электротехнических и электронных систем: Материалы III всеросс. научн. конф./ Чебоксары: Изд-во Чуваш, ун-та, 1999. С. 226-237.

5. Галанина H.A., Лебедев-Е.К. и др. Аппаратные средства и математическое обеспечение информационно-измерительных комплексов обработки сигналов//М., 1986. Деп. в ВИНИТИ № 0286.0035351.

6. Галанина H.A., Лебедев Е.К. и др. Синтез адаптивных мультипроцессорных вычислительных структур обработки сигналов//М., 1986. Деп. в ВИНИТИ № 0286.0031315.

7. Галанина H.A., Лебедев Е.К. и др. Исследование и разработка принципов построения программируемых вычислительных систем обработки радиолокационных сигналов (Часть 1)//М., 1987. Деп. в ВИНИТИ № 0287.0025455.

8. Лебедев Е.К., Галанина H.A. и др. Разработка методологии проектирования специализированных микропроцессорных систем с эффективными алгоритмами. Построение и анализ вычислительных теоретико-числовых алгоритмов обработки сигналов (Часть 2)// М., 1987. Деп. в ВИНИТИ №0287.0067112. 67 с.

9. Лебедев Е.К., Галанина H.A. и др. Методология проектирования специализированных микропроцессорных систем с эффективными алгоритмами.

\ппгратная реализация мультипроцессорной непозиционной МПС обработки ¡игналов. Создание пакета функциональных прсгр?.мм//М., 1988. Деп. в ЗИНИТИ№ 0288.064966. 71 с.

10. Лебедев Е.К., Галакина H.A. и др. Разработка и исследование микропроцессорных систем сбора, обработки и регистрации данных//М., 1989. Цеп. в ВИНИТИ № 0289.001798. 162 с.

11. Лебедев Е.К., Галанииа H.A. Адаптивные ИИС, реализующие шгоритмы поразрядной фильтрации. //Информационно-измерительные юмплексы: Тез. докл. на 6 всесоюзн. конф./Куйбышев: 1983. С.79.

12. Лебедев Е.К., Галанина H.A., Лапий В.Ю. Методы и устройства юразряднош ДПФ//Изв. вузов СССР. Радиоэлектроника. 1985. № 8. С.32-36.

13. Лебедев Е.К., Галанина H.A. Быстрые преобразования Фурье в юммутативном кольце вычетов. //Микропроцессоры: Тез. докл. на всесоюзн. юнф./Зеленоград: 1985. С.61-62.

14. Лебедев Е.К., Галанина Н. А, Лапий В.Ю. Устройство для дискретного цвумерного преобразования Фурье//Автор, свид-во № 1254505 СССР. Бюл. № 12. 30.08.86. 1986.

15. Лебедев Е.К., Галанина H.A. Байесовская фильтрация в системе (статочных классов//М., 1989. Деп. в ВИНИТИ 03.08.89 № 5258-В89. 42 с.

16. Лебедев Е.К., Галанина H.A. Способы кодирования в непозиционных !ычислнггельныхустройС1пвах//Прое1агирование ЭВМ: межвуз. сб. научн. трудов: 'язань: Изд-во РРТИ. 1992. С. 104-109.

17. Лебедев Е.К., Галанина H.A. Оптимальные алгоритмы БПФ в СОК// Терспекгивные технологии в средствах передачи информации: Тез. докл. на I 1еждунар. конф./Владимир: Изд-во Влад. политех, ин-та, 1995. С. 118-119.

18. Лебедев Е.К., Галанина H.A. Многоальтернативное совместное )бнаружение и фильтрация непозиционных марковских сигналов// Динамика юлинейных дискретных электротехнических и электронных систем: Материалы 1-й всеросс. научн. конф./ Чебоксары: Изд-во Чуваш, ун-та. 1997. С. 4-8.

19. Лебедев Е.К., Галанина H.A. Дисперсия шумов обработки юпозиционных сигналов в линейных цепях// Технические науки: сегодня к автра: Тез. докл. гобил. научн. конф./ Чебоксары: Изд-во Чуваш, ун-та. 1997.

171-172.

20. Лебедев Е.К., Галанина H.A., Егоров Е.Г. Оптимизация АЦП в истемах с фазовой модуляцией сигналов// Электрические аппараты: Межвуз. б. научн. трудов./ Чебоксары: Изд-во Чуваш, ун-та. 1998. С. 123-128.

Список условных сокращений и обозначений.

Введение.

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

Фурье.

1.1. Одномерный поразрядный метод вычисления ДПФ.

1.2. Многомерный поразрядный метод вычисления ДПФ.

1.3. Оптимизация параметров ПДПФ.

1.3.1. Разрядность адресных шин ППЗУ- высокая: z>x+y.

1.3.2. Использование ППЗУ с малым объемом памяти: z<x+y.

1.4. Интерактивный синтез ПДПФ.

Выводы.

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

2.1. Выбор системы модулей для БПФ в СОК и ее оптимизация.

2.2. Синтез функциональных модулей БПФ в СОК.

2.3. Реализация схем БПФ в СОК.

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

Выводы.

3. Сравнительный анализ позиционной и непозиционной цифровой обработки сигналов при использовании DSP.

3.1. Сравнительная оценка быстродействия позиционной и непозиционной обработки при реализации на DSP.

3.2. Перспективные направления развития непозиционных устройств

ЦОС на DSP.

3.3. Оптимизация непозиционных устройств цифровой обработки сигналов.

3.4. Определение оптимального набора модулей СОК и погрешностей перекодирования.

Выводы.

4. Программный комплекс моделирования и автоматизированного синтеза непозиционных устройств БПФ.

4.1. Пути компьютерной оптимизации непозиционных БПФ.

4.2. Описание программы моделирования и оптимизации.

4.3. Список требуемых файлов и необходимых ресурсов.

4.4. Руководство программиста.

4.4.1. Структура данных.

4.4.2. Описание процедур и функций.*.

4.5. Основные результаты работы программы.

4.6. Программный комплекс синтеза спецпроцессора БПФ.

Выводы.

Актуальность проблемы. Классические научные достижения в области статистических исследований свойств сигналов и устройств сбора, хранения и регистрации данных отражены в работах [6, 20, 54, 68, 69, 74, 75 и др.]. При этом особое место занимает цифровая обработка сигналов (ЦОС), главными источниками развития которой стали исследования ряда отечественных и зарубежных ученых [18, 19, 21, 23-25, 55, 63, 66], а также успехи в области микроэлектроники и компьютерных систем. Создание одного за другим нескольких поколений сигнальных процессоров Digital Signal Processing (DSP) от TMS320C10 до TMS320C30, DSP96002, DSP32C, DSSP1 привело к увеличению качества вычислительных алгоритмов за счет использования гарвардской архитектуры, конвейеризации процессов, сокращения командного цикла, аппаратной реализации умножения и т.п. Однако использование в DSP традиционной позиционной арифметики, во-первых, требует увеличения разрядности операндов, что не снижает аппаратные затраты и не улучшает отказоустойчивость; во-вторых, делает желательным наличие режима с плавающей запятой, что потенциально уменьшает быстродействие и требует введения лишних циклов для преобразования целых чисел в числа с плавающей запятой и наоборот; в-третьих, не снижает стоимости изделий. Наконец, даже в наиболее мощных сигнальных процессорах форматы операндов обеспечивают требуемую точность далеко не для всех практических применений.

Перед исследователями по-прежнему остро стоят проблемы обеспечения высокой вычислительной эффективности: уменьшения аппаратурных затрат, увеличения быстродействия, точности и отказоустойчивости устройств ЦОС. Поэтому в настоящее время актуальны вопросы применения алгоритмических методов улучшения качества вычислительных процедур и, в первую очередь, -теоретико-числовых алгоритмов (ТЧА) [8, 21, 56]. Основная идея, заложенная в ТЧА - переиндексация чисел во временной последовательности, переход к многомерным процедурам на укороченных выборках данных. Как показано ниже, этот сложный путь не всегда оправдан и часто уступает простым (таким, как БПФ). Поэтому важен и актуален второй путь повышения качества ЦОС -непозиционное кодирование сигналов на выходе АЦП [25-38].

Рис.1. Обобщенная схема цифровой обработки сигналов в СОК

Между непозиционными устройствами кодирования по числам Фибоначчи, в системе остаточных классов (СОК) и т.п. нет принципиальных отличий. Выводы, которые вытекают из исследования одной из непозиционных систем (в частности, - СОК) распространены на другие [58]. Поэтому в диссертации рассматривается одна из этих непозиционных систем - машинная арифметика в системе остаточных классов (СОК). Ее суть состоит в использовании совокупности неотрицательных вычетов по группе взаимнопростых оснований. Основными узлами непозиционных устройств ЦОС в общем виде являются (рис.1):

1. Шифраторы His, кодирующие входной сигнал х(кТ) числами в СОК: х(кТ) = х(кТ) -1 х(кТ) /Ns Г Ns =< х(кТ) > mod Ns. (1)

2. Спецпроцессоры СПб , обеспечивающие заданный алгоритм обработки

F: х(кТ)-> rs(kT) VS= 1у.

3. Дешифратор DS, перекодирующий результат в позиционный код у(кт) = ^ Yrs (kt)Gs ^ mod N, (2) v где Gs - ортогональные базисы СОК [2]; N = П . s=1

4. Решающее устройство РУ, в котором вычисляется сумма по п п наблюдениям у(пТ) = X у(кТ) и происходит сравнение у(пТ) с пороговым к=1 сигналом С, определяемым по одному из известных критериев принятия решения. Так синтезирован нерекурсивный фильтр в [34].

Возможен более сложный случай синтеза по прототипу, реализованный в алгоритме Нифонтова-Лихарева [59-60]. Он состоит в умножении каждой последующей выборки сигнала на вес, зависящий от корреляционных характеристик аппроксимирующей марковской цепи. На рис.2 показан непозиционный цифровой оптимальный фильтр, синтезированный по позиционному прототипу [65]. В матрице памяти (МП) спецпроцессора хранятся вычеты = \,v) весовых коэффициентов, вычисленные априорно в соответствии с алгоритмом: а=1 /?=1 где Радаруи Рпа/Зу ~ вероятности перехода из состояния аР на двух предыдущих шагах в состояние у на текущем шаге процедуры обнаружения.

Индексы «сп» и «п» обозначают случаи наличия и отсутствия сигнала в смеси с помехой. Отсчеты х^ и х входного сигнала подаются на адресные шины МП. В каждой ячейке матрицы хранятся v вычетов:

V. Текущие отсчеты входного сигнала х (/,о) кодируются вычетами в шифраторах Шь Ш2,. В каждом из V каналов соответствующий вычет умножается на вес ¿^у и суммируется с другими в соответствии с алгоритмом: Як8 + Е х (7, а) . (4)

В схеме восстановления результата СВР числа дешифрируются в соответствии с (2). а)

8= 1, V X

Рис.2. Схема непозиционного ЦОФ, синтезированного по прототипу

Отличием фильтра рис.2 от прототипа [60] является упрощение арифметических устройств. При этом объем матриц памяти остается прежним: С>М1, = | х | •2<-М(у+1)\ где формат весовых коэффициентов, v - связность марковской цепи. При 111=10, 121 =1 байт, v = 1, С>мп = 1 Мбайт.

Усложнение аппроксимирующей цепи Маркова (при более адекватном описании реальных сигналов) увеличивает аппаратурные затраты: при V = 2, С>мп = Ю00 Мбайт, что нереально для современных быстродействующих малогабаритных ЦОФ. Практическая реализация этого алгоритма ограничена случаем Я]< 6. Таким образом, синтез сложных вычислительных процедур по прототипу не всегда целесообразен, хотя и часто встречается.

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

1. N = р*, где р=2к, 1- целое число, к=0, 1, 2.

2. N = р*, где р=2к+1.

В первом случае чаще других применяется БПФ. Во втором случае для v реализации ДПФ используется алгоритм Рейдера. В третьем случае N = П Л^ наиболее распространен алгоритм Гуда, преобразующий одномерный массив в многомерный в соответствии с китайской теоремой об остатках. Алгоритм Гуда уступает БПФ, если вычисляются короткие ДПФ прямым методом. Поэтому используются его разновидности, наиболее эффективными из которых являются [22, 25, 56]:

1. Алгоритм простых множителей (АПМ), объединяющий алгоритм Гуда и Рейдера.

2. Алгоритм Винограда для ДПФ (АВПФ).

3. Алгоритм поразрядного ДПФ (ПДПФ).

В [571] представлена проведенная автором сравнительная оценка этих вычислительных алгоритмов по аппаратурным затратам и быстродействию. Оценки получены путем компьютерного моделирования перечисленных алгоритмов. Наименьшую память для хранения программ и данных требует БПФ, наибольшую - АВПФ. В АПМ и АВПФ уменьшено число умножений, но возрастает число пересылок. Оценка временных затрат для АПМ, АВПФ и БПФ проводилась на моделях микропроцессоров с различными способами выполнения сложных операций. При программной реализации операции умножения эффективнее других оказался АВПФ. При аппаратном выполнении умножения БПФ не проигрывает АПМ и АВПФ. Известно, что время пересылки данных влияет на производительность не меньше, чем умножение. Поэтому необходимо сделать вывод о том, что БПФ по-прежнему остается одним из самых высокоэффективных вычислительных алгоритмов и на практике не проигрывает АПМ и АВПФ. В этой связи актуально исследование поразрядных алгоритмов ДПФ, число пересылок данных в которых не выше, чем в БПФ, но большинство сложных операций могут выполняться на этапе проектирования [47, 48].

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

Однако по-прежнему не решен ряд проблем. Среди них важное место занимает решение задач улучшения параметров многомерных теоретико-числовых алгоритмов ДПФ и БПФ при их реализации в СОК, когда обеспечиваются известные преимущества машинной арифметики в системе остаточных классов [30].

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

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

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

Можно выделить следующие теоретические вопросы, связанные с синтезом и анализом непозиционных устройств ЦОС:

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

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

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

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

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

Первая глава посвящена исследованию специальных вычислительных алгоритмов спектрального анализа в СОК. При этом рассматривается поразрядный метод вычисления ДПФ (ПДПФ) в его модификации, связанной с использованием процедуры Гуда. Многомерное ПДПФ включает следующие этапы:

1. Переиндексация данных.

2. Вычисление 14/ N3 коротких N3 - точечных ПДПФ.

3. Переупорядочивание выходных значений многомерного массива.

Методы и устройства ПДПФ имеют преимущества в быстродействии по сравнению с позиционными устройствами БПФ [47, 48]. Кроме того, в ПДПФ существенно уменьшаются ошибки округления [42]. С целью дальнейшего улучшения характеристик ПДПФ решены задачи оптимизации параметров синтезированных схем [13].

Во второй главе рассмотрены методы технической реализации устройств БПФ в СОК [14, 41, 44, 45]. Исследование непозиционных устройств БПФ заключается в выполнении следующих этапов:

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

2. Интерактивная оптимизация непозиционных быстрых алгоритмов по критерию равенства весовых коэффициентов БПФ и модулей СОК и нулевизации обрабатываемых данных.

3. Синтез оптимальных алгоритмов быстрого спектрального анализа.

4. Программная и техническая реализация алгоритмов БПФ в СОК с заданными свойствами.

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

В третьей главе исследуется возможность реализации непозиционных алгоритмов спектрального анализа на сигнальных процессорах, ориентированных на обработку обычных двоично-кодированных сигналов. Это в настоящее время обеспечивает оптимальность реализации ЦФ и БПФ в СОК на штатных процессорах, а также связано с невозможностью освоения производства СБИС непозиционной обработки сигналов. В диссертации проведен анализ использования всех поколений сигнальных процессоров, первые из которых ориентированы на применение архитектуры «один поток команд - один поток данных» (ОКОД), а последние - на весьма перспективные методы параллельных и матрично-векторных вычислений таких, например, как «много потоков команд - много потоков данных» (МКМД). При этом была эмулирована обработка сигналов на перечисленных процессорах. В результате исследования определены пути достижения минимальных потерь по быстродействию. Наилучшие показатели достигаются при использовании сигнальных процессоров третьего-четвертого поколений. При оптимизации непозиционных алгоритмов спектрального анализа, которая всегда возможна и достижима и поэтому обязательна, выигрыш БПФ в СОК по быстродействию возможен всегда и тем более существенен, чем больше число точек наблюдаемого сигнала, т.е. чем выше точность спектрального анализа.

В четвертой главе диссертации рассмотрена программа моделирования БПФ как позиционного, так и непозиционного типов. В программе реализована оптимизация БПФ в системе остаточных классов. Найден ряд систем модулей, которые обеспечивают минимум среднеквадратичной ошибки при подборе весовых коэффициентов, когда они равны 0, ± 1 и ±2, что исключает из алгоритма БПФ в среднем 60 % алгебраических операций. Рассмотрен также второй путь оптимизации, когда один из каналов потоков данных исключается из-за их нулевизации. Программный комплекс позволил сравнить между собой известные алгоритмы БПФ, оптимизировать параметры БПФ в СОК и предоставил исследователям возможность осуществлять интерактивный синтез БПФ с заданными параметрами.

В Заключении приведены основные результаты теоретических исследований, проведенных в диссертации.

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

ЗАКЛЮЧЕНИЕ. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

1. Синтезирован и исследован алгоритм поразрядного одномерного ДПФ (ПДПФ), использующий табличные процессоры. Большинство арифметических операций в нем выполнено на этапе проектирования; сигналы, подлежащие обработке, сгруппированы, что ведет к увеличению быстродействия устройств спектрального анализа. Ограничением на применение одномерного ПДПФ является число сгруппированных точек отсчета, которое не превышает 64-256 для современных СБИС и БИС ППЗУ и ПЛМ. Разработаны и исследованы высокоэффективные вычислительные алгоритмы многомерного ПДПФ для спектральной и корреляционной обработки сигналов при произвольно большом числе отсчетов сигнала. Показано, что многомерный ПДПФ имеет высокое быстродействие и минимальные ошибки округления. Представлена схема технической реализации многомерного ПДПФ. Исследованы пути оптимизации ПДПФ по многомерной целевой функции, зависящей от совокупности аппаратурных и временных затрат. Разработаны вычислительные алгоритмы и программное обеспечение для интерактивного синтеза поразрядных устройств ДПФ. Алгоритмы компьютерного исследования этих устройств улучшают качественные характеристики ПДПФ, обнаруживают идентичные алгебраические операции и обеспечивают программирование ПЗУ, ПЛМ (или ПЛИС) в диалоговом режиме в соответствии с синтезируемыми алгоритмами. Это дополнительно увеличивает вычислительную эффективность устройств поразрядного спектрального анализа, исключая из поразрядных алгоритмов до 90 % алгебраических операций.

2. Исследованы алгоритмы реализации БПФ в СОК. Даны рекомендации по выбору и оптимизации системы модулей для непозиционных процессоров БПФ. Синтезированы непозиционные операционные устройства для практической реализации базовых операций БПФ в СОК. Описаны программы для вычисления коэффициентов БПФ в кольце вычетов и выбора системы модулей СОК. Разработано и исследовано многоканальное устройство для БПФ в СОК. Показано, что оно отличается более высоким быстродействием по отношению к классическим схемам БПФ. Разработан метод улучшения вычислительных характеристик БПФ в СОК. Синтезирован алгоритм индексирования чисел в коммутативном кольце вычетов для случаев произвольно больших модулей, что ослабляет зависимость числа каналов СОК от максимального результата, снижает аппаратурные затраты, и увеличивает отказоустойчивость и быстродействие БПФ в СОК. Разработаны алгоритмы и программа интерактивного синтеза и оптимизации БПФ в СОК. Использование при этом свойств целых чисел в коммутативном кольце вычетов позволило упростить алгоритмы непозиционного БПФ с коэффициентом оптимизации в среднем до 60 %. Достижимо значение КОрг=100 %, если проводится глобальная оптимизация, усложняющая непозиционные алгоритмы БПФ.

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

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

Теоретические и практические результаты диссертации использовались в научно-исследовательских работах, выполненных на кафедре информационно-вычислительных систем Марийского государственного технического университета в 1985-1996 гг. и кафедре информационных технологий Чувашского государственного университета в 1997-1999 гг. Основные результаты докладывались и обсуждались на следующих международных, всесоюзных и всероссийских конференциях:

- всесоюзная конференция «Информационно-измерительные системы ИИС-83», г. Куйбышев, 1983 г.

- всесоюзная конференция «Микропроцессоры-85», г. Зеленоград, 1985 г.

- I международная конференция «Перспективные технологии в средствах передачи информации», г. Владимир, 1995 г.

- Всероссийская научная конференция «Информационные технологии в электротехнике и электроэнергетике», г. Чебоксары, 1996 г.

- Юбилейная научная конференция «Технические науки: сегодня и завтра», г. Чебоксары, 1997 г.

- II и III всесоюзные научно-технические конференции «Динамика нелинейных дискретных электротехнических и электронных систем», г. Чебоксары, 1997 и 1999 гг.

По материалам диссертационной работы опубликовано 20 научных работ, из них 5 статей в центральных журналах и сборниках научных трудов, 9 работ депонированы в ВИНИТИ в виде отчетов по итогам выполнения НИР, а также в виде брошюр и статей, получено одно авторское свидетельство СССР; опубликовано 5 тезисов докладов на международной, всесоюзных и всероссийских конференциях.

1. Адаптивные фильтры /Пер. с англ. Под ред. К.Ф.Н. Коуэна и М.Гранта. М.: Мир, 1988. 392 с.

2. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М.: Сов. Радио, 1968. 440с.

3. Алексенко А.Г., Шагурин И.И. Микросхемотехника: Учеб. пособие для вузов. М.: Радио и связь, 1982. 416с.

4. Амербаев В.М. Теоретические основы машинной арифметики. Алма-Ата. Наука, 1976. 196с.

5. Аппаратные средства и математическое обеспечение информационно-измерительных комплексов обработки сигналов //Деп. в ВИНИТИ, №0286.0035351, 1986.

6. Бакулев П.А. Радиолокация движущихся целей. М.: Сов.радио, 1964. -264с.

7. Белов Г.А. Сигналы и их обработка в электронных устройствах: Учебное пособие. Чебоксары: Изд-во Чуваш, ун-та, 1996. 376 с.

8. Р.Блейхут. Быстрые алгоритмы цифровой обработки сигналов/ Пер. с англ. М.: Мир, 1989. 448с.

9. Бовбель Е.И., Зайцева Е.М., Микулович В.И. Ошибки цифровых систем, основанных на вычислении ДПФ. // М.: Зарубежная радиоэлектроника. 1981. № 5. С.3-25.

10. Ю.Быков B.B. Цифровое моделирование в статистической радиотехнике. М.: Сов. радио, 1971. 127 с.

11. П.Вариченко Л.В., Попович Р.Б., Раков М.А. Цифровая фильтрация случайных сигналов с использованием теоретико-числовых преобразований. //Изв. вузов СССР. Радиоэлектроника. 1958. №12. С.36-40.

12. Галанина H.A., Лебедев Е.К. Интерактивный синтез устройств ПДПФ//Деп. в ВИНИТИ. 17.06.86, №4461-В86, 1986.

13. Галанина H.A., Юферев А.Е. Оптимизация непозиционных алгоритмов спектрального анализа// Тезисы докл. на всерос. научн. конф. «Информационные технологии в электротехнике и электроэнергетике». Изд-во Чуваш, ун-та: Чебоксары, 1996. С. 74-75.

14. Галанина H.A., Лебедев Е.К. Спектральный анализ в коммутативном кольце вычетов//Деп. в ВИНИТИ, № 4111-В86, 1986.

15. Голубов В.И., Ефимов A.B., Скворцов В.А. Ряды и преобразования Уолша: Теория и применение. М.: Наука, 1987. 344с.

16. Гольденберг Л.М., Матюшин Б.Д., Поляк М.Н. Цифровая обработка сигналов/ Справочник. М.: Радио и связь, 1985. 312с.

17. Гоулд Б., Рейдер Ч. Цифровая обработка сигналов. /Пер. с англ. под ред. А.М.Трахтмана. М.: Сов.радио, 1973. 368с.

18. Гришин Ю.П., Казаринов Ю.М. Динамические системы устойчивые к отказам. М: Радио и связь, 1985. 176с.

19. Гуткин Л. С. Теория оптимальных методов радиоприёма при флюктуационных помехах. М.:Сов.радио, 1972. 448с.

20. Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов/ Пер. с англ. М.: Мир, 1988. -448с.

21. Исследование и разработка принципов построения программируемых вычислительных систем обработки радиолокационных сигналов//Деп. в ВИНИТИ, №0287.0025455, 1986.

22. Каппелини В., Константинидис А.Дж., Эмилиани П. Цифровые фильтры и их применение/ Пер. с англ. М.: Энергоавомиздат, 1983. -360с.

23. Кузьмин С.З. Основы проектирования систем цифровой обработки радиолокационной информации. М.: Радио и связь, 1986. -352с.

24. Лебедев Е.К. Быстрые алгоритмы цифровой обработки сигналов. Красноярск: Изд-во Краснояр. ун-та, 1989. 192с.

25. Лебедев Е.К. Методы и устройства непозиционной отказоустойчивой обработки сигналов //Тезисы докл. на всесоюз. конф. по статистическим методам обработки сигналов. Рига, 1986.

26. Лебедев Е.К. Оценка точности измерения параметров радиолокационных сигналов в СОК//С6. научных трудов «100 лет радио», Йошкар-Ола, 1995. С. 103-109.

27. Лебедев Е.К. Ошибки округления в спецпроцессорах непозиционной обработки сигнал ов//Материалы всерос. научн. конф. «Цифровая обработка многомерных сигналов». Йошкар-Ола, Изд-во минитипогра-фии «Луч», 1996. С. 98-101.

28. Лебедев Е.К. Проблемы цифровой обработки сигналов в телекоммуникационных сетях//Сб. материалов 2-ой всерос. научн.-техн. конф. «Динамика нелинейных дискретных электрических и электронных систем». Изд-во Чуваш, ун-та, 1997. С. 4-8.

29. Лебедев Е.К. Синтез и анализ устройств непозиционной обработки сигналов//Тезисы докл. юбилейной научн. конф. ЧГУ. Изд-во «Клио», Чебоксары, 1997. С. 173-174.

30. Лебедев E.K. Синтез нелинейных непозиционных устройств обработки марковских сигналов //Изв. вузов СССР. Радиоэлектроника. 1987. Т.30 №12. С.69-72.

31. Лебедев Е.К. Синтез нерекурсивных непозиционных фильтров СДЦ //Межвузовский сб. научн. трудов «Цифровая обработка многомерных сигналов» /Map. политехи, ин-т. Йошкар-Ола, 1992. С.31-41.

32. Лебедев Е.К. Синтез цифровых фильтров на ЭВМ // Тезисы докл. на всесоюз. конф. «Автоматизация поискового конструирования». г.Йошкар-Ола, 1978. С. 56.

33. Лебедев Е.К. Цифровая фильтрация в системе остаточных классов //Изв. вузов СССР. Радиоэлектроника. 1985. Т.28. №8. С.58-62.

34. Лебедев Е.К. Устройство для быстрого преобразования Фурье//Автор. св-во №1488831, СССР, БИ № 23, 1989.

35. Лебедев Е.К. Устройство для вычисления быстрого преобразования Фурье//Автор. св-во № 1488830, СССР, БИ № 23, 1989.

36. Лебедев Е.К., Бакулев П.А. Проблемы реализации алгоритмов цифровой обработки сигналов на современных СБИС/Материалы всерос. научн. конф. «Цифровая обработка многомерных сигналов». Йошкар-Ола, Изд-во минитипографии «Луч», 1996. С. 27-35.

37. Лебедев Е.К., Галанина H.A. Адаптивные ИИС, реализующие алгоритмы поразрядной фильтрации. // Тезисы докл. на 6 всесоюзн. конф. «ИИС-93». г.Куйбышев, 1983. -С.79.

38. Лебедев Е.К., Галанина H.A. Байесовская фильтрация в системе остаточных классов//Деп. в ВИНИТИ. 03.08.89, № 5258-В89, 1989.

39. Лебедев Е.К., Галанина H.A. Быстрые преобразования Фурье в коммутативном кольце вычетов. //В сб. докл. на всесоюзн. конф. «Микропроцессоры-85». г.Зеленоград, 1985. С.61-62.

40. Лебедев Е.К., Галанина H.A. Дисперсия шумов обработки непозиционных сигналов в линейных цепях//Тезисы докл. юбилейной научн. конф. ЧТУ. Чебоксары, Изд-во «Клио». 1997. С. 171-172.

41. Лебедев Е.К., Галанина H.A. Оптимальные алгоритмы БПФ в СОК//С6. тезисов докл. на I Международной конф. «Перспективные технологии в средствах передачи информации», 14-16 мая 1995 г. Владимир, Изд-во Влад. политех, ун-та, 1995. С. 118-119.

42. Лебедев Е.К., Галанина H.A. Способы кодирования в непозиционных вычислительных устройствах//Межвуз. сб. науч. Трудов «Проектирование ЭВМ», РРТИ, Рязань, 1992. С. 104-109.

43. Лебедев Е.К., Галанина H.A., Егоров Г.Е. Оптимизация АЦП в системах с фазовой модуляцией сигналов//Межвуз. сб. научн. трудов «Электрические аппараты», Чебоксары, Изд-во Чуваш, ун-та, 1998. С.123-128.

44. Лебедев Е.К., Галанина H.A., Лапий В.Ю. Методы и устройства поразрядного ДПФ //Изв. вузов СССР. Радиоэлектроника. 1985. № 8. С.32-36.

45. Лебедев Е.К., Галанина Н.А, Лапий В.Ю. Устройство для дискретного двумерного преобразования Фурье//Автор. свид-во № 1254505, СССР, Бюл. № 32, 30.08.86, 1986.

46. Лебедев Е.К., Галютин М.Ю. Реализация алгоритмов деления в коммутативном кольце целых чисел для спецпроцессоров в СОК//С6. научн. трудов «100 лет радио», Йошкар-Ола, 1995. С.112-116.

47. Лебедев Е.К., Лапий В.Ю. Устройство для быстрого преобразования Фурье//Автор. свид-во № 1290350, СССР, БИ № 6, 1987.

48. Лебедев Е.К., Мясников В.И. Микропроцессорные корреляторы: Учебное пособие. Йошкар-Ола: Изд-во МарГТУ, 1996. 106 с.

49. Лебедев Е.К., Суворов В.И. Синтез рекурсивных фильтров в СОК //Межвузовский сб. научн. трудов /Map. политехи, ин-т. Йошкар-Ола, 1992. С.42-46.

50. Левин Б.Р. Теоретические вопросы статистической радиотехники. В 2-х т. М.: Сов.радио, 1974-1975. -1231с.

51. Лихарев В.А. Цифровые методы и устройства в радиолокации. М.: Сов.радио, 1969. -447с.

52. Макклеллан Дж.Н., Рейдер Ч.М. Применение теории чисел в цифровой обработке сигналов. /Пер. с англ. под ред. Ю.И.Минина. М.: Радио и связь, 1983. -264с

53. Лебедев Е.К., Финько O.A. Методы и устройства преобразования фибоначчиевых модулярных кодов /Деп. ВИНИТИ 12.11.87г. №7994-В87. 27 с.

54. Нифонтов Ю.А., Лихарев В.А. Анализ цифровой системы селекции движущихся целей. //Радиотехника и электроника, 1970. №7. С. 10231027.

55. Пелед А., Лиу Б. Цифровая обработка сигналов /Пер. с англ. под ред. А.И.Петренко. Киев: Вища шк., 1979. 264с.

56. Кей С.М., Марпл С.Л. Современные методы спектрального анализа: Обзор// ТИИЭР, 1981. Т. 69, № 11, с. 5-51.

57. Разработка и исследование микропроцессорных систем сбора, обработки и регистрации данных. Отчет о НИР//Деп. в ВИНИТИ, № 0289.0001798, 1989.

58. Разработка методологии проектирования специализированных микропроцессорных систем с эффективными алгоритмами. Построение и анализ вычислительных теоретико-числовых алгоритмов обработки сигналов. Отчет о НИР//Деп. в ВИНИТИ, №0287.0067112, 1987. 67с.

59. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов/ Пер. с англ. под ред. Ю.Н. Александрова. М.: Мир, 1978. 848 с.

60. Синтез адаптивных мультипроцессорных вычислительных структур обработки сигналов. Отчет о НИР//Деп. в ВИНИТИ, № 0286 0031315, 1986.

61. Сосулин Ю.Г. Теория обнаружения и оценивания стохастических сигналов. М.:Сов.радио, 1978. 320с.

62. Сосулин Ю.Г., Фишман М.М. Теория последовательных решений и её применения. М.: Радио и связь, 1985. - 272 с.

63. Сосулин Ю.Г. К задаче многоальтернативного обнаружения сигналов //Изв. АН СССР. Сер. Техн. кибернетика. -1969. т.14, №4. С. 1635-1643.

64. Стахов А.П. Введение в алгоритмическую теорию измерения. М.: Сов. радио. 1977. 288с.

65. Стахов А.П. Коды золотой пропорции. М.: Радио и связь, 1984. 152с.

66. Стахов А.П. Перспективы применения систем счисления с иррациональными основаниями// Измерения, контроль, автоматизация. №6(40), 1981. С.73-79.

67. Стратонович P.JI. Избранные вопросы теории флюктуации в радиотехнике. М.: Сов.радио, 1961. 263с.

68. Тихонов В.И. Статистическая радиотехника. М.: Сов.радио, 1966. 678с.

69. Торгашев В.А. Система остаточных классов и надёжность ЦВМ. М.: Сов. радио. 1973. 120с.

70. Харкевич А.А. Борьба с помехами. М.: Физматгиз. 1963. 322с.

71. Цифровая обработка информации на основе быстродействующих БИС /С.А.Гамкрелидзе, А.В.Завьялов и др. М.:Энергоатомиздат, 1988. 136с.

72. Юфряков Б.А. Синтез цифровых фильтров по заданной амплитудно-частотной характеристике/ Сб. науч. трудов Моск. авиац. ин-та.М: Вып. 431. М.; 1978. С.26-29.

73. Wan-Chi Sin, A.G. Constantinides. On the computation of DFT using Fermat number transform //IEE Proceedings. Y.31. Part F. N1, Feb. 1884, p. 7-14.

74. W.C. Sin, A.G. Constantinides. Approach to the hardware implementation of digital processors using mersenne number transofms //IEE Proceedings, V.31, PartE, N1, Jan 1984, p. 10 -19.

75. Pollard J.M. Fast Fourier Transform in a Finite Field, Math. Сотр. №25, 1971. p. 365-374.

76. Nussbaumer H.J. Fast Fourier Transform and Convolution Algorithms, 2nd ed., Springer-Verlag? Berlin/ 1982. 127 p.

77. Aho A.V., Hopcroft J.E., Ullman J.D. The Design and Analyses of Computer Algorithms, Addison-Wesley, Reading, Mass. 1974. 379 p.

78. Elliot D.F., Rao R. Fast Transforms: Algorithm, Analyses and Applications, Academic Press, New York. 1983. 262 p.

79. Oppenheim A.V., Schafer R.W. Digital Signal Processing. Englewood Cliffs, N.Y., Prentice-Hall, Inc., 1975. 308 p.

80. Oppenheim A.V., Willsky A.S., Young i.t. Signals and Systems. Englewood Cliffs, N.Y., Prentice-Hall, Inc., 1983. 198 p.

81. Chu S., Burrus C.S. A prime factor FFT algorithm, using distributed arithmetic // IEEE Trans, on ASSP. 1982. Vol. ASSP 30. N2, p.217-226.

82. Jenkins W.K., Leon B.J. The use of Residue Coding in the Design of Hardware for Nonrecursive Digital Filters //Eighth Asilomar Conference on Circuits, Systems and Computers. 1974. p. 265-262.

83. Jenkins W.K., Leon B.J. Composite Number-theoretic Transforms for Digital Filtering //Ninth Asilomar Conference on Circuits, Systems and Computers. 1975. p. 265-262.

84. Murakami U., Reed I.S. Recursive Realization of Finite Impulse Filters Using Finite Arithmetic //IEEE Trans, on IT 23. p. 675-683.1. Usescrt, graph; {$M 50000,0,655360} type

85. PHelpY=AHelpY; HelpY=recordn:integer; next:PHelpY;end;

86. POsn=AOsn; Osn=record r:real; c:real; next:POsn;end;var1. N,N1,Nh,Pr:longint;i,k,Cyc,Cycl,1,z,j,Num:integer;

87. Res:array1.100. of integer;1. Out, Out1,Inm,Inml:POsn;

88. FOut,FOutl,FInm,Finml:POsn;1. M:boolean;

89. Tr,Tc,Trl,Tel,rl,cl,koef:real; h,F:pointer;

90. Mnozh, FMnozh,PerM,FPerM:PHelpY; Fk:text;function MovMas(FMas:PHelpY;nn:integer)¡integer; var

91. Go:PHelpY; ii:integer; begin1. Go:=FMas;for ii:=l to nn-1 do Go:=GoA.next; MovMas:=GoA.n;end;procedure PutMas(FMas:PHelpY;nn:integer;z:integer); var

92. Go:PHelpY; ii:integer; begin1. Go:=FMas;for ii:=l to nn-1 do1. Go:=GoA.next;1. GoA.n:=z;end;function D Mov Mas(z:char;F Mas:P0sn;nn:integer):realvar

93. Go:POsn; ii:integer; begin1. Go:-FMas;for ii:=0 to nn-1 do Go:=GoA.next; if z='r' then1. DMovMas:=GoA.r else1. DMovMas:=GoA.c;end;procedure DPutMas(zz:char;FMas:POsn;nn:integer;z:real); var

94. Go:Posn; ii:integer; begin1. Go:=FMas;for ii:=0 to nn-1 do

95. Go:=GoA.next; if zz='r' then GoA.r:=zelse GoA.c:=z;end;procedure Number; vari:integer; m: integer; beginfor i:=2 to k do beginm:=m*MovMas(FMnozh,i-1); Num:=Num+m*MovMas(FPerM,i);end;

96. Num:=Num+MovMa s(FPe rM,1);end;procedure MainCount; vari,j j,ii:integer; e,cs,ss:real; Del:integer; sti:string; begineye:=cyc+l ; if cyc<k+l thenif cycOcycl then beginfor i:=0 to MovMas(FMnozh,eye)-1 do begin

97. PutMas(FPerM,eye,i); MainCount;end;endelse begin1. MainCount;endelsefor jj:=0 to MovMas(FMnozh,cycl)-1 do begin1. Tr:=0;Tc:=0;{COUNTING}for ii:=0 to MovMas(FMnozh,cycl)-1 do begin

98. Del:=MovMas(FMnozh,cycl);e:=0; for i:=cycl+l to k do begin

99. Del:=Del*MovMas(FMnozh/i);e:=e+2*Pi*MovMas(FPerM,i)*ii/Del;end;e:=e+2*Pi*jj*ii/MovMas(FMnozh,cycl)cs:=cos(e);ss:=sin(e);str(cs,sti);writeln(Fk,sti);str (ss,sti);writeln(Fk,sti) ;1. PutMas(FPerM,cycl,ii);1. Number;

100. Tr:=Tr+DMovMas('r',FInm,Num)*cs; Tr:=Tr+DMovMas('c',FInm,Num)*ss; Tc:=Tc+DMovMas('c',FInm,Num)*cs; Tc:=Tc-DMovMas('r',FInm,Num)*ss;end;

101. PutMas(FPerM,cycl,j j); Number;

102. Out1:=FOutl ; Out:=FOut; Inm:=Finm; Inml:=Finml; Mnozh:=FMnozh ; PerM:=FPerM; cc:=SizeOf(Out) ; for i:=l to N do begin

103. FOutl:=OutlA.next;Dispose(Outl);Outl:=FOutl FOut:=OutA.next; Dispose(Out);Out:=FOut; FInm:=InmA.next;Dispose(Inm);Inm:=FInm; Finml:=InmlA.next;Dispose(Inml);Inml:=FInmlend;for i:=l to k-1 do begin

104. FMnozh:=MnozhA.next;Dispose(Mnozh); Mnozh:=F Mnozh;

105. FPerM:=perMA.next; Dispose(PerM); PerM:=FPerM;end;end;procedure Change; varil:integer; begineye:=cyc+l; if cyc<k thenfor i1:=0 to MovMas(FMnozh,eye)-1 do begin

106. PutMas(FPerM,eye,il); Change;endelse beginfor il:=0 to MovMas(FMnozh,k)-1 do begin

107. PutMas(FPerM,k,il); Number;

108. OutA.r:=DMovMas('r',Finm,Num); OutA.c:=DMovMas('c',Finm,Num); Out:=OutA.next;end;end; eye:=cyc-l;end; BEGIN1. Fill; Noise;

109. DDDDDDDDDDDDDPPPPPPPPPPPPPPPPPPFFFFFFFFFFFFFF} {!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!}1. Count;eye:=0;Out:=Fout ;1. Change;1. Outing;1. Done;end.1. Usescrt, graph; {$M 50000,0,655360} type

110. PHelpY=AHelpY; HelpY=recordn:integer; next:PHelpY;end;

111. POsn=AOsn; Osn=record r:real; c: real ; next:POsn;end;var1. N,Nl,Nh,Pr:longint;i,k,Cyc,Cycl,1,z,j,Num:integer;

112. Res:array1.100. of integer;1. Out, Outl, Inm,Inml:POsn;

113. FOut,FOut1,FInm,Finml:POsn;1. M:boolean;

114. Tr,Tc,Trl,Tel,rl,cl,koef:real; h,F:pointer;

115. Mnozh,FMnozh,PerM,FPerM:PHelpY; Fk:text; Max:real;function MovMas (FMas : PHelpY ;nn: integer) ¡integer;var

116. Go:PHelpY; ii:integer; begin1. Go:=FMas;for ii:=l to nn-1 do

117. Go:=GoA.next; MovMas:=GoA.n ;end;procedure PutMas(FMas:PHelpY;nn:integer;z:integer); var

118. Go-.PHelpY; ii:integer; begin1. Go:=FMas;for ii:=1 to nn-1 do1. Go:=GoA.next; GoA.n:=z;end;function DMovMas(z:char;FMas:POsn;nn:integer):real; var

119. Go:POsn; ii:integer; begin1. Go:=FMas;for ii:=0 to nn-1 do Go:=GoA.next; if z='r' then1. DMovMas:=GoA.r else1. DMovMas:=GoA.c;end;procedure DPutMas(zz:char;FMas:POsn;nn:integer;z:real); var

120. Go:POsn; ii:integer; begin1. Go:=FMas;for ii:=0 to nn-1 do

121. PutMas(FPerM,eye,i); MainCount;end;endelse begin1. MainCount;endelsefor jj:=0 to MovMas(FMnozh, cycl)-1 do begin1. Tr:=0;Tc:=0;{COUNTING}for ii:=0 to MovMas(FMnozh,cycl)-1 do begin

122. Del:=MovMas (FMnozh,cycl);e:=0;for i:=cycl+l to k dobegin

123. Del:=Del*MovMas(FMnozh,i) ; e:=e+2*Pi*MovMas(FPerM,i)*ii/Del;end;e:=e+2*Pi*jj*ii/MovMas(FMnozh,cycl);}readln(Fk,sti) ;val(sti,cs,lin);readln(Fk,sti) ;val(sti,ss,lin) ;1. PutMas(FPerM,cycl,ii) ;1. Number;

124. Tr:=Tr+DMovMas('r',FInm,Num)*cs; Tr:=Tr+DMovMas('c',FInm,Num)*ss; Tc:=Tc+DMovMas('c',FInm,Num)*cs ; Tc:=Tc-DMovMas('rT,FInm,Num)*ss;end;

125. PutMas(FPerM,cycl,jj); Number;

126. DPutMas('r',FOut,Num,Tr) ; DPutMas('c',FOut,Num,Tc) ;end; eye:=cyc-l;end;procedure Count; var1:integer; beginassign(Fk,1c:\temp\paskal\bin\l\W.in'); reset(Fk);for 1:=1 to k do begincycl:=k-l+l;

127. OutTextXY(round(GetMaxX/3),round(GetMaxY/10),ch);} koef:=(4*round(GetMaxY/12)-15)/long*0.9; Graphics1(FOut,0) ; Graphicsl(Foutl,round(GetMaxY/2)) ;end else

128. Writeln('Graphics error:', GraphErrorMsg(ErrCode)); readln; CloseGraph;end;procedure Init; beginclrscr;

129. Tr:=0;Tc:=0;1:=0 ; Cyc:=0;Cycl: = 0; New(FOutl);Outl:=FOutl; New(Fout);Out:=F0ut; for i:=0 to N-l do begin

130. OutlA.r:=0; OutlA.c:=0; New (OutlA.next); Outl:=OutlA.next; OutA.r:=0; OutA.c:=0; New(OutA.next); Out:=0utA.next;end;

131. New(FPerM);PerM:=FPerM; PerMA.n:=0; for i:=l to k do begin

132. Out:=FOut;Out:=OutA.next; Outl.:=FOutl;

133. FOut1:=OutlA.next;Dispose(Outl);Outl:=FOutl FOut:=OutA.next;Dispose(Out);Out:=FOut; FInm:=InmA.next;Dispose(Inm);Inm:=FInm; Finml:=InmlA.next;Dispose(Inml);Inml:=FInmlend;for i:=l to k-1 do begin

134. FMnozh:=MnozhA.next;Dispose(Mnozh);1. Mnozh:=FMnozh;1. FPerM:=PerMA.next;1. Dispose(PerM);1. PerM:=FPerM;end;end;procedure Change; varil:integer; begineye:=cyc+l; if cyc<k thenfor il:=0 to MovMas(FMnozh,eye)-1 do begin

135. PutMas(FPerM,eye,il); Change;endelse beginfor il:=0 to MovMas(FMnozh,k)-1 do begin

136. PutMas (FPerM, k, il) ; Number;

137. DDDDDDDDDDDDDDDPPPPPPPPPPPPPPPFFFFFFFFFFFFFFF}1. DPF;} Filll;1. Count;eye:=0;Out:=Fout;1. Change;1. Outing;1. MaxElem;graphics;1. Diff(Fout,Foutl) ;1. Done ;end.$М 16384,1024,65536} Uses

138. RegOne : Boolean; Matr : PMatr; Stek : Stekl; FileName : String; DSP Type : Real;режим с одним набором оснований} указатель на матрицу оснований } стек оптимальных наборов оснований } имя файла исходных данных } тип устройства ЦОС. 1-ЦФ 2-БПФ }

139. Procedure InitMenu(var M:Menu); Const

140. Colorl : MenuColorArray = ($17, $1E, $1B, $7B, $1B, S3F, $19, $3E) ;

141. Color2 : MenuColorArray = ($4E, $4E, $4F, $7E, $4F, $3F, $19, $3E) ;

142. Framel : FrameArray =' '; Frame2 : FrameArray =' ' ; Frame3 : FrameArray =' '; Begin1. M NewMenu(.,nil);

143. Submenu (1, 2, ScreenHeight, Horizontal, Framel, Colorl, 1 Оптимизация в OK');

144. MenuMode(True,True, False) ;

145. Menultern('Файл2,1,0Ввод исходных данных и запись результатов работы');

146. SubMenu(3,4,ScreenHeight,Vertical,Frame2,Colorl,'');

147. MenuMode(True, True, False);

148. Menultern('Чтение',1,1,1,'Чтение исходного набора коэффициентов из файла');

149. Menultem('Запись',2,1,2,'Запись модифицированного набора коэффициентов в файл');1. PopSublevel;

150. Menultem('Оптимизация', 8,1, 0, 'Оптимизация коэффициентов в системе остаточных классов');

151. Submenu(20,4,ScreenHeight, Vertical,Frame2,Colorl, '');

152. MenuMode(True, True, False);

153. Menultem('Множитель',1,1,0,'Оптимальный перевод коэффициентов в СОК подбором нормирующего множителя');

154. Submenu(35,6,ScreenHeight, Horizontal,Framel,Colorl, '');

155. MenuMode(True, True, False);

156. Menultem('Один набор',1,1,б,'Используется один набор оснований');

157. Menultem('Множество наборов', 13,1,7,'Используется все рассчитанное множество наборов оснований');1. PopSublevel;

158. Menultem('Нулевизация',2,1, 0, 'Оптимизация коэффициентов в СОК методом нулевизации');

159. SubMenu( 35, б, ScreenHeight, Horizontal,Framel,Colorl, '');

160. MenuMode(True, True, False);

161. Menultem('Один шаг',1,1,12,'Обнуляется 1 цифра');

162. Menultem('Два шага',13,1,13,'Обнуляются 2 цифры');

163. Menultem('Три шага',24,1,14,'Обнуляются 3 цифры');1. PopSublevel;1. PopSublevel;

164. Menultem('Результаты', 21, 1,0, 'Вывод таблиц');

165. SubMenu(33,4,ScreenHeight,Vertical,Frame2,Colorl,'');

166. MenuMode (True, True, False);

167. Menultem('Таблицы',1,1,9,'Вывод таблиц');1. PopSublevel;

168. Menultem('Выход',33,1,0,'Завершение работы программы оптимизации');

169. SubMenu(19,11,ScreenHeight,Horizontal,Frame3,Color2,'Вы уверены,что хотите закончить работу?');

170. MenuMode(True, False, False);1. MenuWidth(44);

171. Menultem.(' Да ',4,7,5,'Да, я действительно хочузакончить работу с программой');

172. Menultem(' Нет ',24,7,0,'Нет, я продолжу работу');1. PopSublevel;

173. PopSublevel; Resetnenu(М);

174. SetMenuDelay(M,200); End; {InitMenu}p***************************************************************

175. Procedure MemoryError; Begin

176. Window(1,1,ScreenWidth,ScreenHeight);1. NormVideo;1. ClrScr;1. NormalCursor;1. SetBlink(True);

177. Writeln('Ошибка выделения памяти.'); Halt(1); End; {MemoryError}

178. NoSound; Delay(50); Sound(1200); Delay(400); NoSound; while ReadKey<>#27 do ; W:=EraseTopWindow; DisposeWindow(W);

179. End; {ErrorHessage} {****************************************************************

180. Function Answer(Mess:string;BBB:boolean)¡boolean; Var W:WindowPtr; b:boolean; x:byte; color:word; Beginx:=((80-Length(mess)) SHR 1)-1; if NOT

181. Delay(50); NoSound; x:=Ord(ReadKey); if (x=75) OR (x=77) thenif b then b:=False else b:=True until x=13;

182. Var x, y, h,m,s,slOO:word;1. Beginx:=wherex;у:=wherey; GetTime(h,m,s,sl00) ;gotoxy(37, 20); if h<10 then write ('0'); write (h, ' : '); if m<10 then write ('0'); write(m, ' : '); if s<10 then write ('0'); write (s), gotoxy(x,y); End; { Time }

183. Procedure OutToScreen; Var

184. FastWrite(St,Pos,10,NO); Pos:=Pos+l;end;

185. FastCenter('Стрелки просмотр, Esc - выход', 13, NC) ; Ch:=ReadKey;

186. Ch=Chr(72) then Start:=Start-l; If Ch=CHr(80) then Start:=Start+l; If Start<l then begin PlaySound; Start:=1; end; If Start>(NumbCoef-10) then begin PlaySound; Start:=NumbCoef-10; end Until Ch=Chr(27) ;

187. W:=EraseTopWindow; DisposeWindow(W); End; { OutToScreen }1. Procedure FromFile; Var

188. W:WindowPtr; FileData:Filel; resul:Integer; St:String; ex:Boolean; Beginif NOT MakeWindow(W,5,10,75,24,True,True,True,NC,NC,ТС,'Набор матриц оснований1)then HemoryError; if NOT DisplayWindow(W) then MemoryError; HideCur; NumbCoef:=0; St:=1cf.dfс';

189. Readstring('Введите имя файла исходных данных', 15,10,12,ТС,ТС,ТС,ex, St) FastCenter(' FileName:=St;

190. St : = ' считано. '+Long2Str (NumbCoef) + ' исходных коэффициентов');

191. Message(St); OutToScreen; DataPresent:=True; end; {1} ShowCur;

192. W:=EraseTopWindow; DisposeWindow(W); End;{ FromFile }

193. Procedure SaveCoef ( fname:string); Var W:WindowPtr;

194. Readstring('Введите имя файла исходных данных', 15, 10, 12, ТС, ТС, ТС, ex, St);1. FastCenter( ' }

195. W:=EraseTopWindow; DisposeWindow(W);1. End;

196. Procedure OsnFromK(var flag:Boolean)1.bel 11;1. Var

197. Pmax : Integer; Ch : Char; St : String; i: Byte; W : WindowPtr; Begin if NOT

198. MakeWindow(W,5,10,75,24,True,True,True,NC,NC,ТС,'Параметры оптимизации')then MemoryError; if NOT DisplayWindow(W) then MemoryError; Pmax:=16;

199. St:='BBeflHTe модуль '+Chr(i+48)+'канала 1.61. => '; Readlnteger(St,13+i, 10,3,NC,NC,1,61,Flag,Nv1.); if flag then goto 11;end;11: W:=EraseTopWindow; DisposeWindow(W); End; {OsnFromK}

200. Procedure Otrezok(Var Qbeg,Qend,Qstep:Integer;var Flag:Boolean); Label 11,12; Var W:WindowPtr; Beginif NOT

201. MakeWindow(W,5,10,75,24,True,True,True,NC,NC,ТС,'Параметры оптимизации ')then MemoryError; if NOT DisplayWindow(W) then MemoryError; Qbeg:=l;

202. FastCenter('Допустимые значения : положительные числа ', 13,NC);

203. Readlnteger('Введите начало отрезка =>', 13, 10, 5,NC,NC, 1, 2048, Flag, Qbeg) ; if flag then goto 11; Qend:=100;

204. FastCenter('Допустимые значения: больше начала отрезка',13,NC);

205. Readlnteger('Введите конец отрезка => ' ,14,10,5,NC,NC,Qbeg, 2 04 8,Flag,Qend); if flag then goto 11; Qstep:=1;

206. Просчитываем коэффициенты для всего отрезка множителей ***} dopt:=Qbeg; q:=Qbeg; st:=0; p012max:=0;

207. MaxQ:=Round((Qend-Qbeg)/Qstep)+1; { количество итераций } repeatst:=st+l; n:=Round((st*lOO)/MaxQ);

208. GotoXY(18,18); Write('Для данного набора произведено ',n:3,' % вычислений.'); Time;con:=q*NvNumbChan.; p012:=0; sumdeltacoef:=0; sumost:=0; for n:=l to NumbCoef do begina:=Abs(Round(Coefn.*con));1.tCoefn.:=a;

209. Otrezok( Qbeg,Qend,Qstep,NoDate);if NoDate then ErrorMessage('Данные не быливведены1)elsebegin

210. RegOne:=True; { один набор оснований } Optiml(Qbeg, Qend, Qstep, p012max) ; Modify:=True; end;end;end;1. End;j****************************************************************procedure SokAdd(var Slagl,Slag2:Mass2);

211. Mnulii.:=0; diap:=diap*Nv[ii];end;

212. Mnulkey.:=raz; Mmin:=Mnul; min:=SokToDec(Mmin); curpos:=NumbChan-1; repeatif numcurpos+1.<>0 then begincurpos:=NumbChan-l; for ii:=0 to NvNumbChan.-1 do begin

213. SokToDec(num)+SokToDec(Mmin))<diap then SokAdd(num, Mmin);) ; }; }do write (Mminj.,' ');}write (out,numj.,' '); write (num[j],' '); SokToDec(num)); ',SokToDec(num));

214. Modify:=False; { не была произведена модификация коэффициентов }

215. Nulev:=False; { не была проведена нулевизация } DataPresent:=False; { исходные данные не загружены } OsnPresent:=False; { не определены основания } Matr:=Nil; { список из наборов оснований }repeat1. ClrScr;1. Window(0, 3, 80, 25) ;

216. Modify:=False; { не была произведена модификация коэффициентов }

217. Nulev:=False; { не была проведена нулевизация } DataPresent:=False; { исходные данные не загружены } OsnPresent:=False; { не определены основания } Matr:=Nil; { список из наборов оснований }repeat1. ClrScr;1. Window(0,3,80,25);

218. Синтез, оптимизация и компьютерное исследование эффективности быстрых непозиционных алгоритмов спектрального анализа".

219. Комиссия в составе: д.т.н., профессора Н.М. Скулкяна (председатель)!к.т.н., доцента И.Г. Сидоркиной (член комиссии); к.т.н., доцента Н.В. Костромино! (член комиссии), аосмотрела диссертационную работу H.A. Галаниной и пришла к заключеию, что:

220. Председатель комиссии, профессорассистент1. Г.Е. Егоров