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

На правах рукописи Аксайская Любовь Николаевна РАЗРАБОТКА И ИССЛЕДОВАНИЕ ПАРАЛЛЕЛЬНЫХ СХЕМ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ НА ОСНОВЕ МИНИМИЗАЦИИ ВРЕМЕННОЙ СЛОЖНОСТИ ВЫЧИСЛЕНИЯ ФУНКЦИЙ Специальность: 05.13.17 – Теоретические основы информатики 05.13.18 – Математическое моделирование, численные методы и комплексы программ А В Т О Р Е Ф Е Р А Т диссертации на соискание ученой степени кандидата технических наук Таганрог 2008 Работа выполнена в ГОУВПО «Таганрогский государственный педагогический институт». Научный руководитель: доктор технических наук, профессор Ромм Яков Евсеевич Официальные оппоненты: доктор технических наук, профессор Финаев Валерий Иванович доктор технических наук, профессор Карелин Владимир Петрович Ведущая организация: Ростовский государственный университет путей сообщения (РГУПС) Защита состоится « 19 » июня 2008 г. в 14.20 на заседании диссертационного совета Д 212.208.21 Южного федерального университета по адресу: ауд. Д-406, пер. Некрасовский, 44, г. Таганрог, Ростовская область, ГСП-17 А, 347928. С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул. Пушкинская, 148. Автореферат разослан « 16 » мая 2008 г. Ученый секретарь диссертационного совета Д 212.208.21 доктор технических наук, профессор Чернов Н.И. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Важнейшими областями применения цифровой обработки сигналов (ЦОС) является биомедицина, акустика, звуковая локация, радиолокация, сейсмология, ядерная техника, обработка изображений и др. К числу основных направлений ЦОС относятся цифровая фильтрация и спектральный анализ. Исследование повышения быстродействия и вычислительной точности алгоритмов ЦОС актуально, несмотря на наличие процессоров ЦОС с производительностью нескольких миллиардов комплексных умножений/сек. При реализации основных алгоритмов ЦОС таких, как свертка, корреляция, ковариация, необходимо вычислять элементарные функции (базисные функции ортогональных разложений). Объем и точность их вычисления в значительной мере влияют на быстродействие и точность ЦОС. Помимо актуальности быстрого вычисления функций базиса ортогональных разложений, существует широкий круг задач с большим объемом вычисления функций, где требуется высокая скорость и точность аппроксимации. К категории таких задач относятся задачи гидро- и аэродинамики, задачи по расчету течений в условиях сложной пространственно-временной структуры с учетом влияния различных физических и химических процессов. Задачи управления движением летательных аппаратов, включая гидросамолеты, требуют эффективных способов улучшения аэродинамических характеристик, при этом в описании законов векторного управления пространственным движением используются тригонометрические функции на каждом шаге управляющих воздействий. В практических приложениях часто необходимо вычислять значения рациональных, степенных, тригонометрических, обратных тригонометрических, показательных, логарифмических, гиперболических и обратных гиперболических функций. При этом к методам их вычисления предъявляются требования одновременно высокого быстродействия, вычислительной устойчивости, высокой точности аппроксимации и универсальности схем вычислений. Значительные объемы вычисления элементарных функций и функций специального вида могут включать задачи моделирования управлением различными техническими и технологическими процессами, задачи моделирования физических процессов различной природы. Такие задачи необходимо решать в строго ограниченное время или в режиме реального времени, поэтому схемы вычисления функций должны быть оптимизированы по временной сложности. Применение быстродействующих алгоритмов вычисления функций в задачах ЦОС позволяет сократить аппаратурные и вычислительные затраты, снизить стоимость устройств или систем, уменьшить габариты, массу и энергопотребление, что особенно важно для бортовых систем и систем с автономным питанием. Цель диссертационной работы состоит в разработке и исследовании компьютерных схем минимизации временной сложности вычисления функций с обеспечением инвариантности алгоритмов относительно вида функций, точности их вычисления, промежутка изменения аргумента. Оптимизированные алгоритмы должны применяться в качестве основы для параллельного вычисления одновременно всех элементов базиса ортогональных разложений, используемых в ЦОС, и при этом отличаться инвариантностью относительно вида разложений, быть совместимыми с параллельным выполнением базового набора операций ЦОС в целом. Для достижения поставленной цели в диссертационной работе решаются следующие задачи: 1. Средствами информатики построить устойчивую распараллеливаемую схему минимизации временной сложности таблично-алгоритмического вычисления функций на основе интерполяции по Ньютону, которая была бы инвариантна относительно вида функции, промежутка изменения аргумента и априори заданной границы погрешности. 2. Распространить исследуемую схему на компьютерное вычисление производных и определенных интегралов с сохранением инвариантности относительно вида функции, устойчивости, параллелизма и минимальности временной сложности для произвольно заданной границы погрешности. 3. Осуществить программную реализацию синтезированной таблично-алгоритмической схемы, выполнить численный эксперимент по практической проверке инвариантности, устойчивости и точности вычисления функций при условии минимальной временной сложности схемы. 4. Разработать метод параллельного вычисления всех последовательных элементов тригонометрического базиса дискретного преобразования Фурье (ДПФ) с временной сложностью , который отличался бы инвариантностью относительно количества отсчетов и сохранял данный порядок оценки при параллельном выполнении ДПФ и обратного дискретного преобразования Фурье (ОДПФ) в целом. 5. Синтезировать алгоритм параллельного выполнения ДПФ и ОДПФ на основе таблично-алгоритмической аппроксимации всех элементов базиса с временной сложностью , который отличался бы минимизированным до значения числом последовательных умножений, а также инвариантностью относительно количества отсчетов в условиях произвольно заданной границы погрешности вычислений. 6. Распространить синтезированные параллельные алгоритмы на выполнение совокупности схем ЦОС, включая операции корреляции, свертки, ковариации, быстрого преобразования Фурье (БПФ), двумерные ДПФ и ОДПФ с логарифмическими оценками временной сложности в условиях инвариантности относительно количества отсчетов. Методы исследования опираются на теоретические основы информатики и информационные технологии, на методы прикладной информатики, численного анализа, теории сложности, теоретические и прикладные методы ЦОС. Достоверность результатов вытекает из их математического обоснования, подтверждается оценками временной сложности, представленными в форме доказательных утверждений и теорем, детально иллюстрируется результатами программного моделирования и численного эксперимента. Научная новизна заключается в следующем: 1. Синтезирована динамически распараллеливаемая компьютерная схема минимизации временной сложности таблично-алгоритмической аппроксимации функций на основе интерполяции по Ньютону, которая отличается от известных аналогов построением с помощью матричного параллельного видоизменения формул Виета, инвариантностью относительно вида функции, промежутка изменения аргумента и априори заданной границы погрешности. 2. На основе использования средств информатики выполнено распространение таблично-алгоритмической аппроксимации функций для случая вычисления производных и определенных интегралов с сохранением свойств инвариантности относительно вида функции, устойчивости, параллелизма и минимальности временной сложности в условиях произвольно заданной границы погрешности. Показано, что динамически распараллеливаемая схема таблично-алгоритмического вычисления функций, производных и определенных интегралов применима для синхронизации параллельных процессов вычисления данных функциональных зависимостей в параллельных вычислительных системах с перестраиваемой архитектурой. 3. Дана программная реализация предложенных таблично-алгоритмических схем, выполнен численный эксперимент и сравнение с известными методами, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной временной сложности алгоритма, – предложенные схемы ускоряют известные методы в , где – степень аппроксимирующего полинома, и позволяют достигать времени параллельного выполнения всего комплекса данных вычислительных схем в случае априори заданных функций. 4. Разработан метод динамически распараллеливаемого вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью , который отличается инвариантностью относительно количества отсчетов и сохраняет данный порядок оценки при параллельном выполнении ДПФ и ОДПФ в целом. В случае применения таблично-алгоритмической схемы для параллельного вычисления элементов базиса отличие от известных аналогов заключается в сокращении до количества последовательных умножений в условиях произвольно заданной границы погрешности вычислений. 5. Предложены модификации параллельных схем выполнения ДПФ для параллельного выполнения БПФ и вычисления частичной суммы ряда Фурье. Разработанные схемы распространяются на параллельное выполнение совокупности алгоритмов ЦОС, включающей операции корреляции, свертки, ковариации и ОДПФ, при этом сохраняется логарифмический порядок оценок временной сложности. Видоизменения данных схем с сохранением порядка оценок распространяются на случай двумерных ДПФ и ОДПФ. Предложенные схемы отличаются от известных аналогов построением, сокращением числа последовательных умножений и, в частности, тем, что число процессоров модифицированного БПФ сокращается в раз при сохранении логарифмической оценки временной сложности вычисления. 6. Выполнено сравнение предложенных схем параллельной ЦОС с известными параллельными методами, при этом показано, что предложенные схемы, в целом, отличаются инвариантностью относительно числа отсчетов, быстродействием в условиях повышенной точности вычисления и общностью для комплекса алгоритмов цифровой обработки. Синтезированная динамически распараллеливаемая схема таблично-алгоритмического вычисления элементов базиса преобразований Фурье позволяет сохранить быстродействие в условиях произвольно заданной границы погрешности вычислений, распараллеливаемая настройка схемы на динамически изменяющиеся параметры может осуществляться в режиме реального времени. Основные положения, выносимые на защиту: 1. С помощью средств информатики построена динамически распараллеливаемая схема минимизации временной сложности таблично-алгоритмической аппроксимации функций на основе интерполяции по Ньютону, схема опирается на параллельное видоизменение формул Виета, инвариантна относительно вида функции, промежутка изменения аргумента и априори заданной границы погрешности. 2. На основе средств информатики таблично-алгоритмическая аппроксимация функций распространяется на случаи вычисления производных и определенных интегралов с сохранением инвариантности относительно вида функции, качества устойчивости, параллелизма и минимальности временной сложности в условиях произвольно заданной границы погрешности. 3. Выполнены программные реализации таблично-алгоритмических схем, численные эксперименты, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной временной сложности алгоритма. Предложенные схемы ускоряют известные методы в , где – степень аппроксимирующего функцию полинома, и позволяют достигать времени параллельного выполнения комплекса данных вычислительных схем для априори заданных функций. 4. Разработан метод динамически распараллеливаемого вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью , инвариантный относительно количества отсчетов , который сохраняет порядок данной оценки при параллельном выполнении ДПФ и ОДПФ в целом. При этом применение таблично-алгоритмической схемы для параллельного вычисления базиса позволяет сократить количество последовательных умножений до в условиях произвольно заданной границы погрешности вычислений. 5. Разработаны модификации предложенных схем ДПФ для параллельного вычисления БПФ и частичной суммы ряда Фурье, которые распространяются на параллельное выполнение совокупности алгоритмов ЦОС, включающей операции корреляции, свертки, ковариации и ОДПФ, при этом сохраняется логарифмический порядок оценок временной сложности. Данные схемы с сохранением порядка оценок распространяются на двумерные ДПФ и ОДПФ. 6. Схема таблично-алгоритмического вычисления элементов базиса преобразований Фурье позволяет сохранить быстродействие в условиях произвольно заданной границы погрешности вычислений, распараллеливаемая настройка схемы на динамически изменяющиеся параметры может осуществляться в режиме реального времени. Практическая ценность диссертационного исследования заключается в прикладном характере разработанных схем последовательного и параллельного вычисления функций, производных и определенных интегралов при условии минимизации временной сложности. Предложенные методы доведены до практической программной реализации, применимы для решения актуальных задач ЦОС. На основе предложенных схем минимизации временной сложности вычисления функций могут создаваться новые библиотеки стандартных подпрограмм, ориентированные на практическое применение в быстродействующих вычислительных системах, а также новые системы параллельной ЦОС. Внедрение и использование результатов работы. Полученные в работе результаты приняты к использованию в ОАО «Таганрогский завод «Прибой» в качестве единой распараллеливаемой схемы минимизации кусочно-полиномиальной аппроксимации функций применительно к основным алгоритмам ЦОС; в госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО «ТГПИ»; в учебном процессе кафедры информатики Таганрогского государственного педагогического института в курсах «Математика и информатика», «Численные методы», «Компьютерное моделирование», курсах по выбору и практикуме решения задач на ЭВМ, что подтверждено соответствующими актами об использовании, приведенными в приложении 3 к диссертационной работе.

Похожие:

	Рабочая программа дисциплины «Алгоритмы и процессоры цифровой обработки сигналов» ...		Радиофизический факультет Целью изучения дисциплины является ознакомление с видами и моделями информационных сигналов, с основными методами аналоговой и цифровой...
	Декомпозиция сигналов на основе вейвлетов Гаусса и Морле (dwsignal) Программа предназначена для декомпозиции сигналов и может применяться в научных исследованиях и при обучении студентов специализирующихся...		Разработка и исследование методов распознавания объектов в массивах...
	Разработка методов получения и цифровой обработки рентгеновских изображений.		Московский энергетический институт (технический университет) институт... Целью дисциплины является углубленное теоретическое и практическое освоение методов и средств цифровой обработки речевых сигналов,...
	Разработка и исследование распределенной подсистемы конструкторского... Работа выполнена в Технологическом институте Южного федерального университета в г. Таганроге		Исследование и оптимизация алгоритмов и устройств уровневой обработки... Работа выполнена в Технологическом институте Южного федерального университета в г. Таганроге на кафедре Радиоприемных устройств и...
	Исследование методов обработки электроэнцефалографических сигналов... Работа выполнена в таганрогском технологическом институте Южного федерального университетана на кафедре Радиоприёмных устройств и...		Урок "Курская битва" Основная идея преподавателя истории – формирование рационального мышления на основе создания опорных схем и использования опорных...
	Тема: «Аксиома параллельных прямых» Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых		Исследование причин и способов минимизации на рынке труда позволяют... Также рассмотрены способы их минимизации. На современном этапе проблема трансакционных издержек приобрела особую актуальность. Причиной...
	Тема урока: «Вычисление площадей с помощью интегралов» Цель урока Обобщить и систематизировать теоретический материал по теме. Отработать навыки вычисления первообразных для функций. Отработать навыки...		Доклад ронжина Андрея Леонидовича по диссертационной работе «Разработка... «Разработка адаптивного метода робастного понимания слитной речи на основе интегральной обработки данных», представленной на соискание...
	«Реализация фгос на уроках математики: нетрадиционные уроки» Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых		Календарно-тематическое планирование учебного материала Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых