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

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛГВДИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ Н.Э.БАУМАНА

РГ6 он

На правах рукописи УДК 681.32

Ефимов Владншф Владишрович

ШЛ13 И СИНТЕЗ МЕТОДОВ БЫСТРОГО ПРЕОБРАЗОВАНА СУРЬЕ С "ДЕЮРМИРУЕМОП" ОСЬЮ ЧАСТОТ

05/13.05 - Элементы и устр >йства внчислителькой техники и систем управления

С5.13Л1 - Матзматическое и программное обеспечена? комплексов, систем и сетей

Автореферат

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

НаучшП руководитель: доктор технических неук, Профессор В,Д.Курганов

Москва - 1994

-Работа выполнена в Московском ордена Ленина, ордена Октябрьской революции и ордена Трудового Красного Знамени государственном техническом университете им. Н.Э.Баумана.

Научный руководитель - доктор технических наук, профессор Курганов В.Д.

Офик'яльные оппоненты - доктор технических наук, . профессор Бархоткин В. А.

кандидат технических наук, доцент Михайлов С. Ф.

, - Ведущая организации - НИИ "Аргон".

Защита состояться "_"__1994 г. в _ часов на заседании специализированного совета К.053.15.04 "Вычислительная и информационная техника" в Московском государственном техническом университете им. Н.Э.Баумана по адресу: 107005, Москва, 2-я Бауманская ул., д. 5.

С диссертацией можно ознакомиться в библиотеке МПУ им. Н.Э.Баумана.

Ваши .отзывы в двух экземплярах,__заверенные печатью, просим

высылать по указанному адресу. ' .

Автореферат разослан "апрО-ЛЯ 1994 г.

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

специализированного 7 /у

совета к.т.н., доцент ^^¿С^у^ Иванов С.Р.

Подписано в грчвть б.РЛ.^г. Обтгм 1.0г..л. Йаг. 184.. Туг. ЮО.

ТглоттеФия '.'ГТУ-м«.Н.Р.Бр-»><рне

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

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

ЦЕЛЬЮ диссертационной работы является разработка новых методов реализации преобразования Фурье с "деформируемой" осьв частот для повышения быстродействия БПФ-процессоров.

МЕТОДЫ ИССЛЕДОВАНИЯ. Для решения поставленной задачи в диссертации использованы методы спектрального анализа, аппаратурной реализации арифметических операций, комбинаторики, теории факторизации разреженных матриц преобразований, теории параллельной обработки информации.

НАУЧНАЯ НОВИЗНА. К основным научным результатам, полученным в диссертационной работе, относятся:

1. Методика синтеза БПФ с "де'ормируемой" осью частот.

2. Разработка на ее основе четырех методов ЕПФ:

- модифицированное'дискретное преобразование" Фурье (МДПФ);

- модифицированное быстрое преобразование Фурье (МЕПФ);

- модифицированное БПФ без фазового сдвига исходных данных (МБПФБФС); .

- ."деформируемое" БПФ (ДБПФ).

3". Проведение анализа быстродействия и точности реализации ВДПФ, МБПФ, МБПФБФС и ДБПФ.

4. Анализ технико-экономических характеристик архитектур процессоров для реализации БПФ с "деформируемой" осью частот.

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ. Рязработ&нныо в диеочрТЕ.ц.н: • <тире метода БПФ с "деформируемой" осью частот, полученные выражения для оценки быстродействия и точности их реализации могут быть использованы при построении спецпроцессоров БПФ для чсввозмо. :иих технических приложений.

Разработанные в диссертации три варианта архатактур лроцол«-

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

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

Разработанные в диссертации программы МДПФ и МБПФ могут быть использованы для эффективного решения многих задач спектрального анализа цифровых сигналов на универсальных ЭВМ.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Результаты диссертационной работы внедрены на Калужском приборостроительном заводе "Тайфун".

Применение разработанных в диссертации специализированного цифрового вычислительного устройства обработки информации (СЦВУОИ) и программы, реализующей МБПФ, позволило в системе управления устройством отображения визуальной информации сократить аппаратурные затраты на 40 56, потребляемую мощность на 30 % й повысить быстродействие в 2 раза. Годовой экономический эффект от внедрения составил в 1991 году 90 тысяч рублей. Программа, равлизущая МБПФ, использовалась при испытании на помехоустойчивость работы обратного канала кабельного телевидения (ОККТ) на Калужском приборостроительном заводе "Тайфун" в 1993 году для анализа частотного спектра сигналов, передаваемых и принимаемых устройствами ОККТ.

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

Результаты внедрения подтверждены соответствующими актами.

АПРОБАЦИЯ РАБОТЫ. Основные положения диссертации докладывались и обсуждались на трех конференциях: Всесоюзная конференция "Повышение эффективности средств обработки информации на базе математического и машинного моделирования" (Тамбов, 1989); Всесоюзная конференция НТТМ и студентов "Актуальные проблемы информатики, управления, радиоэлектроники' и лазерной техники" (Москва, 1989);

Всесоюзная научно-техническая конференция с международным участием стран членов СЭВ "Применение статистических методов в производстве и управлении" (Пермь, 1990).

Результаты диссертационной работы использовались в трех совместных НИР 31-го отдела НИИ ИСУ МГТУ им. Н.Э.Баумана с НИИ "Стрела" (г. Тула) и КЕМ (г. Коломна):

1. Архитектура поразрядного умноямтеля для ВПФ-проиессоров использовалась в НИР "Разработка процессора ЕПФ о использованием СГИС на базе К-МОП ЕМК" (т-ча И064588, НИИ "Стрела").

2. Методы БПФ с "деформируемой" осью частот использовались в двух НИР:

а) "Разработка экспериментального образца цифровой вычислительной системы для обработки сигналов" (тема И314989, НИИ "Стрела"); .

а) "Разработка экспериментального образца цифрового блока выделения сигналов" (тема И314089, КЕМ).

ПУБЛИКАЦИИ. Материалы диссертационной работы отражены в семи печатных работах, шесть из которых опубликованы лично автором и одна в соавторстве.

По материалам диссертации офс-млено изобретение.

СТРУКТУРА РАБОТЫ. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 62 наименований и трех приложений. Основное содержание изложено на' 121 страницах машинописного текста, содержит 34 рисунка и 11 таблиц.

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

Во ВВЕДЕНИИ обоснована актуальность темы диссертации и определен круг исследуемых вопросов.

В ПЕРВОЙ ГЛАВЕ проведен обзор основных известных методов реализации преобразования Фурье.

Непосредственная реализация дискретного преобразования Фу] -<е (ДПФ) для комплексной последовательности чх.сел г(п) (п-^ЛГ- ) ооущеотвляется-.согласно выражению

. п=а ь I 2£- -1.

.где

. ¿"/"Л;

' ' ' )

к - номер определяемого коэффициента Фурье (к= и,м-Г); N - размер массива исходных данных.

Быстрые преобразования Фурье - это различные методы, уменьшения времени реализации ДПФ.-

Одна из самых ранних идей возможности создания БПФ-алгоритмов относится к 1947 году - это алгоритм Левинсона.

Но т. ?!,ко со времени публикации в 1965 году метода Кули и Тъюю'/ и обоснование Стогхэмом возможности его применения для вы-ч/:.лония сверток, БПФ-алгоритмы начали широко применяться для цифровой обработки, сигналов. Затем появился целый ряд алгоритмов БПФ, основанных на методе Кули и Тъюки: БПФ-алгортмы с основанием 3, 4, 6, 8, 12, методы Рейдеру Бруна, Рейдера-Бреннера, БПФ с двойным родикалои и многие другие.

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

Наиболее просто как программно, так и аппаратурно реализовать БПФ о замещением при разложении по основанию 2, основанное на методе Кули и Тьюки.

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

БПФ, основанные на методе Кули и Тьюки, обеспечивают высокое быстродействие как правило лишь при N=2*% где Б - натуральное число. /

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

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

в заданном диапазоне частот.

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

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

Во ВТОРОЙ ГЛАВЕ разработаны и проанализированы методика синтеза ШФ о "деформируемой" ооыа частот и четыре метода на ее основе: модифицированное дискретное преобразование Фурье, модифицированное ШФ, модифицированное БПФ без фазового сдвига данных и "деформируемое" БПФ.

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

Остальные три метода позволяю-" вычислять с высоким быстрсдей отвием коэффициенты ДПФ P„,.-tP(l), F(l+h), ?(l=2h), ... ,.P(U(R-

Hin

1)h)J, где 1 - номер первого определяемого коиффидаента ДИ>, h -шаг следования коэффициентов (h=2s), а В - их число (R--2S).

Методика синтеза ЕПФ разработана путем факторизации разрешенных матриц преобразования Фурье и в матричном виде представл^пл выражением F h=Z Mj (I ® №мп),

где Z-[Z(0), Z(1), Z(2), ... , Z(N-1)] - исходные данные;

,F(1), ?(l+h), i(l+2h).....F(1+(R-1 )h) ] ~

Л J b

- результат преобразования; М^диаг.[w° , ... , w«H-l,,J;

W^'=e"J ~~iT n!;

I . ^ - столбец "из h единиц;

ОТ . п

к К w° .. w°

)) N ■ H

„О Wh wah ' . .. w(H- I )h

м N ы N

w'h w*h .. w(H- j la'h

N N , M ы

w° V¥H'h wa'(H-h) .. W(B' 1) (N

N N N N

где

Модифицированное дискретное преобразование Фурье реализовано ь три втапа.

I. Суммирование влементов массива исходных данных 1=12(0), '¿(1), 2(2).....7,(Ы -1) 1 (Ы-2е) согласно выражениям:

(к,1,т)= £ г

1=0 -1

8к„

«-г I а*а

где 1= О,

1бк„

-1;

т="07Т";

к=к к (к, - нечетное, к =2В).

1 44 1 <3

2

2. Домножение результатов первого втапа на (-(1-.Ш

а

* ■ . * а

т«0 7

Е У2(к,1,ш)(*—(1-;)))"

т=0 2

где 1= О,

'Г

1бк_

--1.

3- Формирование окончательного результата'преобразования:

1»о 3 н * 2 ы

Число нетривиальных умножений при определении й коэффициентов ДПФ методом МДПФ равно

МШЦ1Ф=К^8" -

Модифицированное быстрое преобразование Фурье реализовано за четыре втапа.

1. Определение массива частотномодулированных данных гп>= =[ г'11 (О), 2(1) (1), гп1(2), , 2;(1>(Ы-1)] путем частотного

одвига массива исходных даш IX г=[2(Р), г(1), 1(2), ... , )]

1

(№=2В) согласно выражению

г" 1(п)=г(п)^1, где п=Т!7ТГТ.

2. Суммирование в массиве гп> всех элементов г|П(п) (п- ТГГГГТ), отстоящих друг от друга на | :

г(ь1(п)=Ь112(П(п+ш-^-),

и«0 II

—и— где п= 0,—-1.

11 /ц,

Результат построчно записывается в вида двумерного'массива г*

г<ь>( о ] г(ь,( 1 ] ... 2(ь)(^--1]

2(ыг_м 1 _н+11.г(ыг_н+21 ... 2<ь>г агп

1 № > 1 тг > ^ Юг > ИЬ '

г'ыгЖ] ... г,м(-1 -1]

I № > I Шг ' I Шг >

№ > ' № > ^ й >

3. Формирование матрицы У как результат БПФ с основпштем й над столбцами матрицы г(ь):

Г(0,0) 1) .. Р'(0, N йй -1)

Р* С1.0) Р'П, 1) Г(1,2) . .. Р*(1. N -1)

У'(2,0) Г'С2Р 1) г (г.2) н {Ш -1)

Г(Н-1,0) Г (й- 1.1) рчи-ьг) .. Р'(й- 1, -

ЙЙ

О

4. Формирование р<?зул1 гата преобразования Фурье У -=[£,'л. ?(1нИ), Г(1+2Ь), ... , РЦИй-!)!!)] согласно выражению:

и

I Р'(1Д) К1'-1=0 £

где 1="<Г,ТГТ.

Число нетривиальных умножений, необходимых при реализшсии МЕПФ

шю 1а 211 2 НИ где 1 = — (1, - нечетное, 1=2Е).

Ч • 3 '

Модифицированное БПФ 0вз фазового сдвига данных реализовано в три этапа.

1. о^-зделение коэффициентов г*(п1) согласно выражению: гчп )= г(п).

па-о И

где п = 0,—-1.

1 И г

2. Вычисление промежуточных данных Р(1+И(Ыо(1п(Н+Р-— )),а)

" И

согласно выражению

Р(1+И(Мой„(Л+Р--^)),8)= Г г'ЧвП-^-) и*;15, в И 1.0 ЙИ в

где г'Ча+Ъ —)=г'(а+1; —) и»п»1ь>. ЙИ . НИ н

а= 0, Г;

НИ 0,й-1; " 1. и '

р=1+ 1

' 1= О.К-1.

Данное выражение реализуется с помощью — преобразований Фурье

над массивами из Н элементов по одному из известных БПФ-алгоритмов с разложением по основанию 2.

3. Нахождение искомых коэффициентов преобразования Фурье

У(1+1И)« £ ?(1+1И,3), где 1= О.Н-1.

Число нетривиальных умножений, необходимых при реализации МЕПФБФС

Если число определяемых коэффициентов ДПФ К=4Б, то первый и . третий етапы МБПФБФС можно оставить без-'изменений, а на втором ятапе ис"ользовать БПф-алгоритм с разложением по основанию 4.

Число нетривиальных уш.лений, необходимых при реализации

МЕПФБФС о использованием на втором втапе НПФ-алгоритма с разложением по основанию 4 (МЕПФБФС4)

■МБПФБФС4 gh 2 8h Rh ,

' "Деформируемое" быстрое преобразование Фурье реализовано за четыре втапа. -

1. Определение Z'(n¡) согласно выражению

Z*(n )= h¿ Zírij+n —),

1 »3=° *

-Я-

где п = 0,—-1.

h

2. Вычисление ¿"(s+t ——) и Z'»(в+( — +t) — ) согласно 'Rh 2 1 Rh

выражений i t (i)

2"(B+t,)=[Z'(s+t<-i)+(-1)SZ'(s+(— W 1 \

1 Rh 1 Rh 2 Rh

- t (i»!) z"(B+(S+t,) J-)=[z,(s+t1 -^-)-(-1)йгчв+( —+t() — )']w 1 4

O 1 nv. » nv* rt 1 t)Vi "

Rh ' ffli 2 1 Rh

• где t

1 2

Rh

3. Определение ?(l+2Ijh, в) и в) согласно

выражений:

Р(l+2i h, s)= l Z! 1 (s4-t —- )Wr , 1 i «o 1 Rh á

b P • H Ví

F(l+(2i +1)h, s)= £ Z'' (s+( — +t ) — )V?p , 1 t .o 2 Mi a

где i = O,—-1;

1 . 2

Шг

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

Г(1+1П)= 11(1+111,а)»5 11 . ■ «о ь

где ЫГ.ТГТ.

Число нетривиальных умножений, необходимых при реализации ДШФ с использованием на третьем этапе БПФ с минимальным числом умножений

Мпкпл3 ~ ~-К •

В твбл. приведены числа комплексных операций тина "Умножение", необходимых при вычислении кооффишентов ДШ> ), РЧ1+П), Р(1.42Ь), ... , У(1 ч-Ш-1 ] с помощью метода ЕПФ с минимальным числом умножений и.методами ЕПФ с "деформируемой" осью частот при N=(024, *г=2 в зависимости от числа определяемых коэффициентов К.

Таблица 1.

\ Ме-Ччй тод \х 8 .16 32 ■ 64 128

Ш 3586 3586 3586 3586 3586

МДПФ 1016 2032 4064 8128 16256

МБ11Ф 1203 1291 1515 1731 1919

МБПФБФС 632 816 1040 1232 1416

МБШБФС4 '752 - 1040

■ ДЕПФ 1016 1136 1312 ' 1504 1680

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

а) при ;^сле определяемых коэффициентов Фурье В <, если

им следуют «^Постоянным шагом Ь; -

о) при Н < 1о§ N. если, о;ш расположены произвольно.. Мпк-м&лиш ьячислателишв затраты требуются . при -реализации бел» и МБШБ! •--, есж (см. табл. ' 1), однако

и МЫНЫСД воде* нэлоодеа сложнуи- .■<1шэра'гур;1у)& и программ

мную реализацию.

Наиболее просто составить программу и разработать схему процессора для реализации ЦЦПФ и МЕПФ.

Основное преимущество МДПФ - с его помощью можно определять коэффициенты Фурье, как и при непосредственной реализации ДГ1Ф, независимо друг от друга, но, по сравнению с последней, МДПФ обеспечивает быстродействие в среднем в 8 раз вше.

В диссертации разработана методика, являющаяся математическим ядром методов ШФ с "деформируемой" осью частот. На ее основе выведены четыре метода: МДПФ, МИФ, МБПФВФС и ДЕПФ, рассмотренные, выше. Выбор метода В® для конкретной вычислительной системы зависит от числа определяемых коэффициентов Фурье и формы его реализации: аппаратурная или программная.

В ТРЕТЬИ! ГЛАВЕ проведена разработка и анализ трех архитектур вычислительных устройств для реализации ШФ с "деформируемой" осью частот: специализированное цифровое вычислительное устройство для обработко информации на микросхемах серии 585, сопроцессор БПФ на базовых матричных кристаллах (ШК) и сопроцессор БПФ на микросхемах серии 1838, а также рассмотрена архитектура поразрядного умно-кителя для ЕПФ-процессоров. '.

Результаты анализа архитектур БПФ-процессоров приведены ь табл. 2.

Наличие большого числа микросхем в СЦВУОИ на 585-сй серии объясняется тем, что это автономная микро-ЭВМ, содержащая ПЗУ на 68-ми микросхемах и оперативную память на четырех микросхемах.

Вычислительные устройства на БМК КМОП и серии_ 1838 являются сопроцессорами и, поэтому своих ПЗУ и оперативной памяти не имеют.

Как видно из табл. 2, минимальные аппаратурные затраты имеет сопроцессор БПФ на БМК КМОП, а максимальное быстродействие обеспечивает сопроцессор на микросхемах серии 1838.

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

Описанный в третьей главе поразрядный умножитель работает в два этапа:

1. с помощью вентилей формируются поразрядные произведения;

2. с помощью.древовидной схамы, состоящей из сумматоров и вы-

Таблица 2.

Основная серия микросхем БМК КМОП 1838 •585

Число кристаллов БМК КМОП 7 -

Число серийных, микросхем 5 32 131

Число реализаций преобразования Фурье за 1 с при N=1024, 11=2 и четных 1 ВПФ 11=8 651 1220 4,9

й=64 651 1220 4,9

ВДПФ 11=8 2167 5230 45,4

И=64 271 654 5,7

МБПФ К=8 2061 3925 14,8

Н=64 1431 2712 10,4

МБПФБФС Н=8 3123 6109 25

И=64 1787 3503 14,2

ДШФ И=8 2066 3925 16,2

И-64 1433 2712 11.1

чэтателей, определяется результат умножения.

Епагодаря применению в умножителе древовидной схемы, содержащей вычетатели, и отсутствию на его выходе многоразрядного сумматора повышается быстродействие в два раза и сокращаются аппаратурные затраты на 20%. На схему умкожитоля оформлено изобретение СТ]. Умножитель использован при разработке сопроцессора - БПФ на -БМК КМОП. ...

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

В вычислительных устройствах, где наряду с реализацией преобразования Фурье, необходима решать другие задачи цифровой обработки информации и не ':рвОуотся высокое быстродействие, но необходимы кнн1'маА».нш аппаратурные затраты, рекомендуется применять СЦВУОИ.

ЧЕТВЕРТАЯ ГЛАВА посвящена вопросам разработки и анализа программ, реализующих БПФ с "деформируемой" осью частот на универсальных ЭВМ.

Разработаны программы, реализующие МДПФ и МБПФ на языке Турбо-Паскаль и проведан их анализ по быстродействию.

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

В ПРШЮШШЯХ рассмотрена вычислительная система с ЕПФ-процесеором и приведены разработанные на языке Турбо-Паскаль программы для реализации МДПФ и МБПФ. Представлены акты внедрения диссертационной работы.

' 0СН02ЙЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведен анализ методов БПФ и обоснована актуальность преобразований Фурье с "деформируемой" осью частот.

2. Предложена методика, составившая математическое ядро для синтеза БПФ с "деформируемой" осью частот.

3. Разработаны и проанализированы по критериям быстродействия и аппаратурным затратам четыре метода реализации БПФ: ВДПФ, МБПФ, МБПФБФС и ДВПФ. Применение МДПФ позволило сократить в 4 раза аппаратурные затраты в систолических ДПФ-процессорах. МБПФ, МБПФБФС и ДБПФ обеспечил) быстродействие более, чем в 2 раза выше, по сравнению с известными.ЕПФ-алгоритмами.

. 4. Предложены три схемы вычислительных устройств для реализации БПФ с "деформируемой" осью частот.

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

сгиго? в 2 раза. ' •

6. Создан и проанализирован по окп^дчЯствию' пакет приклад-¡ш программ ЕПФ с "деформируемой" осно частот в сравнении- с из-гчотыш Ы1Ф-программами.

'<. Внедрение на Калужском приборостроительном заводе "Тайфун" МЫФ и ^ШОИ позволило в системе управления устройством отображения гадальной информации сократить аппаратурные затраты на 40!» , потребляемую мощность на 30?. и повысить быстродействие в 2 раза, '¡рогр.'ешу, реализующая МЕПФ, использовалась на Калужском приборо-г-'--итольном заводе "Тайфун" при испытании на помехоустойчивость Р'|."\>тц обратного канала кабельного телевидения.

ШЦй> и МВШ были использованы при разработке эксперимента«, -:;!): •> образца цифрового блока выделения сигналов в КЕМ (г. Колом-•!•■). , ■

Результаты внедрения подтверждены соответствующими актами.

СПИСОК РАБОТ

иснопюе содержание диссертации отражено в следущих работах. 1. ЬЗ^мои Ь. В. Реализация быстрого преобразования Фурье с •да^ииру-чк'й" осью чаотс-т для систем обработки . ияобраза-ннЯ. '' ним«» статистически* миголов в щшзводстя-5 и управлении: '¡'о.'.у^ы докладов Всесоюзной научно-технической конференции о мэвду-чардаш участием отрад членов ЗВ.- Педеь, 1990.- Т. 2,- С. ЗСйз.

ЕЗЕимов В. В. Метод реализации быстрого • преобразования 1урьв па произвольных частотах. - Рукопись представлена Московским Гооукпротвоштм Техническим Университетом им. Н. э.- .Баумана // Дчг.. РУХ.В ЧНИТН.- И.01.91.- Г ¿Ш.-'б е.,

3. НАИНОЙ К. В. .М^ТОР тсзддоа'лит с.нот1У»г-о г.М'.-^ра'-.бь'.ни.-!

Фуръо с "деформируемой" осью частот. Рукопись представлена Московским Государственным Техническим Университетом им. Н. Э. Баумана П Деп. рук. в ВИНИТИ.- 11.01.91.- № 201.- 5 с.

4. В£имов В. В. Метод параллельного умножения с высоким быстродействием // Актуальные проблемы информатики,-управления, р.-;-; оэлектроники и лазерной техники: Тезисы докладов Всесоюзной конференции НТТМ и студентов.- М., 1989.- Т. 1.- С. 109.

5. Ефимов В. В. Методы повышения быстродействия при выполнении ррифметичееких операций в системих цифровой обработки информации // Повышение эффективности средств обработки информации на базе математического и машинного моделирования: Тезисы докладов Всесоюзной конференции.- Тамбов, 1989.- С. 22.

6. Ефимов В. В., Курганов В. Д. Применение поразрядных умно-, жителей при реализации ВПФ // Труды Хабаровского Политехнического института.- Хабаровск, 1989,- С. 22.

7. А. с. 87904 СССР, МКИ3 С 06. Устройство для умножения в Дополнительном коде. / В. В. Е^шов (СССР). - N2 4881342/24.