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

Программа на языке МАТЬАВ расчета производных для учета чувствительности критерия качества к изменениям возмущения и настройки регулятора приведена на рис.5. На основании полученных выражений построены графики критериев вида (1) и (2), представленные на рис. 6.

Из рис.6, а) видно, что минимуму 1к соответствует 11 для к1, а минимуму 1=1к+д1к/дМ соответствует 12 для к2. Менее чувствительное управление характеризуется худшим качеством: 12 > ¡г На рис.6, б) приведены полученные в результате моделирования системы зависимости показателя качества управления 1к от возмущения М при значениях коэффициентов кс равных к1 и к2. Из приведенных графиков видно, что выбор коэффициента кос без учета чувствительности обеспечивает лучшее качество регулирования в середине рассматриваемого диапазона действия возмущений. Выбор коэффициента кос с учетом чувствительности обеспечивает лучшее качество регулирования в начале диапазона.

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

Библиографический список

1. Справочник по теории автоматического управления [Текст]: / Под ред. А.А. Красовского.— М.: Наука. Гл. ред.физ.-мат. лит., 1987.— 712 с. ил.; 22 см. — Библиогр.: с. 681-704. — Предм. указ.: с. 707 — 711 — 35000 экз. —ББК 32.81 (в пер.).

2. Трофимов, А.И., Принципы построения автоматических регуляторов теплоэнергетических процессов АЭС [Текст]: Учебное пособие/ А.И. Трофимов, Н.Д. Егупов, Я.В.Слекенич с. — М.: Энергоатомиздат, 1999. 340 с. : ил.; 22 см. — Библиогр.: с. 332-334.. - 300 экз. -ISBN 5-283-03189-6 (в пер.).

3. Ротач, В.Я. Теория автоматического управления теплоэнергетическими процессами [Текст]: Учебник для вузов / В.Я. Ротач. - М.: Энергоатомиздат, 1985. 296 с. : ил.; 25 см.-Библиогр.: с. 289. - Предм. указ.: с. 290-291.- 7300 экз. -ББК 32.815 (в пер.).

4. Иглин, С.П. Математические расчеты на базе MATLAB [Текст]:/ С.П. Иглин. - СПб.: БВХ-Петербург, 2005. 640 с. ил.; 25 см. - Библиогр.: с. 627-630. - Предм. указ.: с. 631-6343000 экз. - ISBN 5-94157-290-5 (в пер.).

5. Иванов, В.А. Регулирование энергоблоков [Текст]: / Л.: Машиностроение, Ленингр. отд-ние, 1982. 311 с. ил.; 22 см. - Библиогр.: с. 302-309. - 3000 экз. - (в пер.).

6. Денисова, Л.А. Исследование чувствительности системы регулирования [Текст]: Труды Всероссийской научной конференции «Проектирование научных и инженерных приложений в среде MATLAB». - СПб.: Изд-во С.-Петерб. ун-та, 2007. - С.1022-1028. - 200 экз. - 1603 с.: ил. ISBN 978-5-288-04327-7.

ДЕНИСОВА Людмила Альбертовна, кандидат технических наук, доцент кафедры «Автоматизированные системы обработки информации и управления».

Дата поступления статьи в редакцию: 14.04.2008 г.

© Денисова Л.А.

УДК 62137 Е. А. АЛЬТМАН

Омский государственный университет путей сообщения

ОПТИМИЗАЦИЯ ВЫЧИСЛИТЕЛЬНОЙ СХЕМЫ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

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

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

«ОМСКИЙ НАУЧНЫЙ ВЕСТНИК» № 1 (64) ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ. РАДИОТЕХНИКА И СВЯЗЬ

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ. РАДИОТЕХНИКА И СВЯЗЬ «ОМСКИЙ НАУЧНЫЙ ВЕСТНИК» № 1

Рис. 1. Структура обработки данных

(Cooley-Tukey) имеющие удобную структуру для программной реализации [1].

Алгоритмы Кули-Тьюки позволяют организовать вычислительный процесс таким образом, чтобы на каждой стадии вычислений результаты размещались в тех же ячейках памяти, что и входные данные (так называемые вычисления «на месте», in-place). Эта схема оказалась удобной в реализации и получила широкое распространение.

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

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

При реализации этой идеи данные на различных стадиях вычислений будут расположены различным образом, т.е. организовать вычисления «на месте» при данном подходе не получится. Поэтому для хранения данных нужно использовать два буфера. В текущей стадии один из них используется для входных данных, другой — для выходных, на следующей стадии они меняются местами. В русском языке для обозначения такого подхода часто применяется термин «пинг-понг», на английском, по аналогии с обычной схемой, более удачным будет название «out-place».

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

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

Для изложения этого подхода отметим некоторые моменты, лежащие в основе алгоритмов Кули-Тьюки.

ДПФ для N точек, где N = M*L, можно выполнить более эффективно следующим способом:

— исходный массив из N элементов представляется в виде двумерной матрицы размером M*L;

— вычисляются L-точечные ДПФ всех столбцов;

— все элементы матрицы умножаются на так называемые поворачивающие множители (twiddle factors);

— вычисляются M-точечные ДПФ всех строк;

— меняются местами строки и столбцы с получением спектра сигнала.

Данная схема может применяться рекурсивно, т.е. в том случае, если L или M составное число, ДПФ строк (или столбцов) также вычисляется с помощью представления строки (столбца) в виде матрицы.

В том случае, если N является степенью двойки, рекурсивные вычисления можно реализовать, оставляя на каждой стадии столбцы (строки) из двух элементов и выполняя вычисления ДПФ для двух точек. Это будет алгоритм Кули-Тьюки по основанию 2. Если на каждой стадии выполнять ДПФ для четырех точек, то получится алгоритм по основанию 4.

Обмен строк и столбцов после каждой стадии вычислений не позволяет организовать вычисления «inplace», поэтому применяется другой подход — один раз до или после выполнения основной операции (в зависимости от того, для строк или столбцов выполняется двухточечная ДПФ) выполняется так называемая бит-реверсная (дибит-реверсная для алгоритмов по основанию 4) сортировка элементов. Соответственно различают так называемые алгоритмы с прореживанием по частоте и с прореживанием по времени [2].

Рассмотрим возможный вариант реализации «out-place» алгоритма Кули-Тьюки по основанию 2.

На входе алгоритма мы имеет N точек входного сигнала, N = 2 K, где K — количество стадий алгоритма.

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

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

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

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

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

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

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

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

По аналогии с алгоритмами прореживания по времени и по частоте, можно построить «пинг-понг» алгоритмы считывающие данные в один поток, а сохраняющие в 2 или 4 потока.

Рассмотренный алгоритм был реализован на процессоре ZSP400 фирмы LSI Logic. Время выполнения преобразования Фурье для 128 точек (вход — комплек-

сные 16-битные целые числа в формате Q15 нормированные на половину диапазона, для предотвращения переполнения после каждой стадии данные делятся на два) включая сохранение контекста составило 1900 тактов (менее 15 тактов на точку). Этот результат на 20% быстрее наилучшего из известных результатов (2400 тактов, менее 19 тактов на точку) для алгоритмов, выполняющих вычисления «на месте» [3].

Таким образом, алгоритмы типа «пинг-понг» позволяют получать в общем случае, более быстрые и простые функции для вычисления спектров сигналов. Они были использованы при разработке функций БПФ математической библиотеки для процессоров на ядрах ZSP. Разработанные функции имеют производительность на 10-20% выше оценочных значений производительности классических алгоритмов.

Библиографический список

1. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов — М. : Мир, 1989. — 445 с.

2. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов — М. : Мир, 1978. — 835 с.

3. Форум разработчиков для процессоров ZSP http:// www.zsp-ug.com

АЛЬТМАН Евгений Анатольевич, кандидат технических наук, доцент кафедры «Автоматика и системы управления».

Дата поступления статьи в редакцию: 24.04.2008 г.

© Альтман Е.А.

удк 687.oi6. 5 Ж. А. ФОТ

Омский государственный институт сервиса

ПУТИ СОВЕРШЕНСТВОВАНИЯ ПРОЦЕССА ЭСКИЗНОГО ПРОЕКТИРОВАНИЯ КОСТЮМА В САПР

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

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

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

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

«ОМСКИЙ НАУЧНЫЙ ВЕСТНИК» № 1 (64) ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ. РАДИОТЕХНИКА И СВЯЗЬ