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

• Автор: Аксайская, Любовь Николаевна
• Шифр специальности: 05.13.17, 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Таганрог
• Количество страниц: 180 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.
ГЛАВА 1. СИНТЕЗ КОМПЬЮТЕРНЫХ СХЕМ МИНИМИЗАЦИИ ВРЕМЕННОЙ СЛОЖНОСТИ ТАБЛИЧНОАЛГОРИТМИЧЕСКОГО ВЫЧИСЛЕНИЯ ФУНКЦИЙ НА ОСНОВЕ ИНТЕРПОЛЯЦИОННОГО ПОЛИНОМА НЬЮТОНА
1.1. Схема табличноалгоритмической аппроксимации функций на основе интерполяционного полинома Ньютона с минимизацией временной сложности
1.2. Сравнение погрешности табличноалгоритмического вычисления функций на основе интерполяционных полиномов Ньютона и Лагранжа
1.3. Сравнение погрешности табличноалгоритмической схемы вычисления функции на основе интерполяционного полинома Ньютона и ряда Тейлора .
1.4. Максимально параллельная схема минимизации временной сложности табличноалгоритмического вычисления функций на основе интерполяционного полинома Ньютона.

1.5. Выводы.

ГЛАВА 2. ОПТИМИЗИРОВАННАЯ СХЕМА ТАБЛИЧНОАЛГОРИТМИЧЕСКОГО ВЫЧИСЛЕНИЯ ПРОИЗВОДНЫХ И ОПРЕДЕЛЕННЫХ ИНТЕГРАЛОВ НА ОСНОВЕ ИНТЕРПОЛЯЦИИ ПО НЬЮТОНУ .
2.1. Табличноалгоритмическое вычисление производных на основе интерполяционного полинома Ныотона с минимизацией временной сложности.
2.2. Метод приближенного вычисления определенных интегралов на основе табличноалгоритмической схемы с помощью интерполяционного полинома Ньютона.
2.3. Схема временной оптимизации приближенного вычисления определенных интегралов в случае специальных функций.
2.4. Статическое и динамическое распараллеливание схемы табличноалгоритмического вычисления функций, производных и определенных интегралов на основе интерполяционного полинома Ныотона
2.5. Выводы
ГЛАВА 3. ПАРАЛЛЕЛЬНАЯ ЦИФРОВАЯ ОБРАБОТКА СИГНАЛОВ С ПРИМЕНЕНИЕМ ТАБЛИЧНОАЛГОРИТМИЧЕСКОЙ АППРОКСИМАЦИИ БАЗИСНЫХ ФУНКЦИЙ
3.1. Параллельное вычисление прямого и обратного ДГФ с использованием схемы Стоуна.
3.2. Параллельная табличноалгоритмическая аппроксимация базиса ДПФ и ОДПФ на основе интерполяционного полинома Ньютона
3.3. Параллельная аппроксимация ряда Фурье на основе модифицированной схемы Стоуна и табличноалгоритмической схемы с использованием интерполяционного полинома Ньютона
3.4. Параллельные схемы для совокупности алгоритмов ЦОС
3.5. Применение схем параллельного вычисления тригонометрического базиса для выполнения БПФ
3.6. Сравнение временной сложности алгоритмов ЦОС
3.7. Параллельные схемы многомерной I ОС
3.8. О применении максимально параллельной схемы минимизации временной сложности табличноалгоритмического вычисления функций к ЦОС
3.9. Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Временная сложность будет обозначаться Тя, где количество процессоров. Каждое из данных понятий аналогично интерпретируется в . Конкретная программная реализация невствящихся параллельных программ в данной модели не учитывается, не учитывается отображение на архитектуру параллельной вычислительной системы. Данная модель абстрагируется от способов обмена в рамках модели предполагается , что параллельная вычислительная система работает как идеальный параллельный процессор . Пусть х задана на фиксированном отрезке , , допустимая погрешность аппроксимации 2 е также фиксирована, т. Поэтому можно считать, что при каждом значении 0,1,. Разложение 4 получается из известного
разложения где У вещественные или комплексно
сопряженные корни. Шаг1 дг, хр, 1, 2,л2. Шаг 2 ахг, хр, 1, 2,и2. Шаг 3 хрд, , 2,. Шаги 4, 5, . Здесь и ниже а ближайшее целое, не меньшее сахмого числа а целая часть числа наименьшая часть числа, не превосходящая а. Теорема 1. Здесь и ниже, при оценках временной сложности, у длительность одного бинарного арифметического умножения, с длительность бинарного алгебраического сложения. Данный алгоритм целесообразен для вычисления элементарных или стандартных функций, поскольку в этом случае наперед известен вид аппроксимирующего многочлена, следовательно, априори могут быть вычислены его корни. Шаг 1 хх. Шаг 2 х2 х х2 х2. Шаг 3 х4 х х4 х2 х4 х3 х4 х4. Шаг2 х х2 х2х2 2 д1о2я. Шаг к2л1 ЯХ7, 1, 2,я. Тп1оц2 п1, 1 1о2 п 1С 2 п шах, с 0к 2. Данная неветвящаяся параллельная программа применима для параллельной полиномиальной аппроксимации функций в условиях сходимости. Отсюда ее эффективность п2 ус. Для деления применяется следующая неветвящаяся параллельная программа . Пусть в результате редукции вещественного аргумента
, 1 . Пусть выбрана двоичная
система счисления. У,т1т2. УФгМ1 с
где требуется выбрать гак, чтобы 1 2, что всегда можно сделать, не увеличив погрешности метода. Тогда к о2 3 1. Шаг 1 г2. Шаг2 г. Шаг к г2 . Шаг к 1 , 0,1,. Шаги 2, к3, . Теорема 2. Вычисление 9 на одном процессоре возможно со сложностью с о. ТОГО, что ухух1. Схемы кусочнополнномиальных аппроксимаций. Схемы кусочнополиномиальной аппроксимации часто рассматривали в качестве оптимальных машинных алгоритмов вычисления функций ,. Такое представление об . Аппроксимирующий полином строится на каждом подынтервале, объединение подынтервалов покрывает основной интервал. Длину подынтервала можно выбрать такой малой, чтобы приближение на нем достигало априори, заданной границы погрешности. На этой основе возможно достигать высокой точности приближения полиномом малой степени. Именно это качество определяет преимущество таких схем и . При построении таких схем, однако, в окончательной форме нет общего подхода в зависимости от разновидности приближения на подынтервале, схемы отличаются количеством операции, временем и точностью вычисления. Например, для аппроксимации на подынтервале в предлагается1 использовать интерполяционный полином Ньютона, в котором не приводятся подобные, вследствие чего аппроксимация обладает существенно избыточным числом операций. В ту же аппроксимацию предлагается выполнять с помощью интерполяционного полинома Лагранжа. В общем виде приведение подобных не осуществляется, и эта схема обладает тем же недостатком избыточности. Аналогичный недостаток сохраняется при аппроксимации на подынтервалах с помощью ортогональных полиномов Чебышева , . В диссертационной работе для преодоления существующих недостатков будет выполнено применение быстрой дешифрации номера подынтервала и будет построен алгоритм оптимизации временной сложности вычисления функций на всех подынтервалах. При этом обеспечивается инвариантность алгоритма относительно наперед заданной границы погрешности аппроксимации функции. Некоторые разновидности приближений функций. Разложение функции по невязкам строится следующим образом. Один из способов получения
разложения функций по невязкам состоит в том, что из уравнения невязки определяется хФу0,г0, а. ГУо1 Гу взаимно обратная функция по отношению к р .