Разработка и исследование параллельных схем цифровой обработки сигналов на основе минимизации временной сложности вычисления функций тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Аксайская, Любовь Николаевна

• Аксайская, Любовь Николаевна
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Аксайская, Любовь Николаевна

ВВЕДЕНИЕ.

ГЛАВА 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. Параллельные схемы многомерной ЦОС.

3.8. О применении максимально параллельной схемы минимизации временной сложности таблично-алгоритмического вычисления функций к ЦОС.

3.9. Выводы.

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

Актуальность проблемы. Решение задач в вычислительных системах с использованием аппроксимации функций требует значительных затрат времени, объема оперативной памяти и вычислительных ресурсов [1, 2]. В практических приложениях часто необходимо вычислять значения t элементарных функций: рациональных, степенных, тригонометрических, обратных тригонометрическим, показательных и логарифмических, гиперболических и обратных гиперболическим. При этом к методам их вычисления предъявляются требования одновременно высокого быстродействия, вычислительной устойчивости, высокой точности аппроксимации и универсальности схем вычислений. К категории задач, требующих большого объема вычислений, относятся задачи гидро- и аэродинамики, задачи по расчету течений в условиях сложной пространственно-временной структуры с учетом влияния различных т физических и химических процессов. Задачи управления движением летательных аппаратов, включая гидросамолеты, требуют эффективных способов улучшения аэродинамических характеристик, при этом в описании законов векторного управления пространственным движением используются тригонометрические функции для определения углов тангажа, крена, рыскания. Базовая нелинейная математическая модель пространственного движения твердого тела, записанная через углы Эйлера, имеет вид [3]: xi (t)=—хъ х5 + х2 х6 — g sin X|q + (l/m)ux;

X2{t)=—x6 +x3 x4 — gcosxn cosx10 + (l/m)u2; хз (t)=—x2 x4 + x, + g sin xx j eos x,o + (l/m)u2;

X5 (t)=a4x4x6 + a3u5;

4 л4 ти3 и5 ,

Xl (t)= x¡ cosx12 cosx10 +x2 (sinxn sinx12 -cosxn cosx12 sinx10)+ +x3 (cosxn sinx]2 +sinxu cosx12 sinx10) ;

X8(t)= X¡ sinx10 +x2 COSXjj COSX]0 -x3 sinxncosx10;

X9 (t)= - Xj sinX12 COSXl0 + x2 ( sinXj t COS X12 + COS xn sin Xj2 sin X,Q)+ +x3 (cosxncosx12-sinxnsinx12sinx]0) ; x\o(t)= x5sinxH +x6cosxH ; xn(/)= x4-tgx10 (x5cosxn -x6sinxn );

• / \ cosxn sinx,,

X\2\t J= Xj-— ~X6- ? cosx10 cosx10 где xx - Vx, x2=Vy, x3=V, - проекции вектора линейной скорости на оси связанной системы координат; х4=сох, х5=соу, х6=со:. - проекции вектора угловой скорости на оси той же системы; х7-Х, х8=7, x9=Z - координаты центра масс летательного аппарата в земной системе координат; х|0=&, хи=у, х12=х ~ углы тангажа, крена и рыскания, соответственно; u{=Fx, u2=Fy, u3=F, - результирующие силы по осям координат; иА=Мх, и5 = Му, и6 -Mz - суммарные моменты сил; g - ускорение свободного падения; т -масса аппарата; ax-\jlx, a2={ly-Iz)/Ix, a3=l/Iy, a4=(l:~Ix)/Iy, a5=l/L, ae={lx-Iy)jI,; Ix, Iy, I: - моменты инерции самолета.

Быстродействие и точность вычисления функций, очевидно, определяют важнейшие параметры управления летательным аппаратом.

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

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

Г(г)= интеграл вероятностей е^(г)=~1=§ехр\^-Г)с11; у

I' о

71 0 интеграл Досона F(y)=exp(—y2'j |ехр(^2) Ж; интегралы Френеля

С(г)= $соб^^2 ск, 5^)= интегральная показательная функция

Ех[—Ж; интегральный логарифм Ы{х)- Г—, х>0, хФ\\ х * о интегральный синус и косинус С1(х)=- дилогарифм о

00 х" ; функция распределения Пирсона %2 (хи-квадрат) я=1« распределение случайной величины Х=Х2+Х% +.+ Хгп, случайные величины Хх, Х2, .,Хп независимы и имеют одно и тоже распределение ч щ 2 2

N(0,1); распределение Фишера ^ где %п, хт - независимые 1т П случайные величины, подчиненные распределению хи-квадрат с п, т степенями свободы, £ -распределение Стьюдента , и,Х независимые случайные величины).

Приближенные методы вычисления функции /(х) на интервале (а, Ь) сводятся к вычислению аппроксимирующей функции ф(х). Для оценки ошибки г(х)=/(х)-ф(х) вводятся некоторые числовые характеристики, называемые «нормами» функции. Наибольшее значение имеют [1]:

1) «равномерная норма» ошибки:

II г 1с= т,ахЛИ*)| = тах1/(*)- ф(*)| ; ха{а,Ь) 1С (а,Ь)

2) «квадратическая норма» ошибки:

1 г ||2 = рг(х)]2Лх = , или более общая квадратическая норма с весом р(х)>0 :

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

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

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

00 источников является разложение функции в степенной ряд (х-х0)к , где к=О х 0 - фиксированное число, центр сходимости ряда. Если функция п +1 раз дифференцируема при хе(л:0-г,х0+г), г>0, то для всех хе(х0-г,х0+г) имеет место формула Тейлора

С1) с остаточным членом П

XQ

Необходимым и достаточным условием сходимости правой части (1) к функции /(х), xe(x0-r,x0+r) является выполнение равенства lim Rn (х) =0. n—> 00

Если функция /(х) непрерывна на \а, х] и обладает на этом отрезке производными до порядка т+п+1 включительно, то справедлива обобщенная формула Тейлора [4, 5] к=1 [т + п)\ где я = (-1)п т-п^х а>--/("+и+1)(0); а<е<х; рСк- биномиальный т + п)! (т + п +1)! коэффициент, причем рСк=0 при к> р.

Элементарные и аналитические функции принадлежат к числу представимых степенными рядами. Если функция /(х) представима п АкЦ0\ формулой /(х)= ——хк + Яп (х), то, обрывая ее на п -ом члене, получим о к! многочлен Рп(х) п-ой степени, который обладает следующим свойством: на интервале (0, К) система многочленов степени п наилучшего приближения при к—>0 стремится к многочлену Рп(х). Поэтому многочлен Рп{х) дает наилучшее приближение к функции /(х) вблизи нуля.

В вычислительных системах используют не только сходящиеся, но и «полусходящиеся» ряды, которые сходятся при малом количестве членов, обеспечивая необходимую точность, и расходятся при увеличении числа членов.

Для вычисления многочленов наиболее часто используется схема Горнера, но для ускорения процесса применяются схемы Винограда, Мотцкина - Белаги - Пана [1,5-11].

Схема Горнера может быть записана в виде: р„{х)={(Лапх+ап-\)х+ .-)х+ах)х+а0 .

Ее вычисление сводится к рекуррентному алгоритму

К=ап'> Ук=ак+хУк+Х9 к = п-1,0; Ра(х)=Г0.

Схема Горнера требует п операций алгебраического сложения и п операций умножения. В случае, когда требуется вычислять один и тот же полином многократно и время выполнения операции умножения значительно больше времени выполнения операции сложения, более экономно применять методы Мотцкина - Белаги - Пана. Например, многочлен четвертой степени 4

РА (х)= ак хк, О представляется по схеме Мотцкина [12] в виде к-0 х)=((м+д:+а2)м+аз )а4, где и=(л;+а0 )л:+а1, ак — соответственно-подобранные коэффициенты. Эта схема содержит три умножения, пять сложений, т.е. меньше операций умножения, чем схема Горнера. Минимальное количество операций1 умножения (деления) и сложения при построении схем, подобных схеме Мотцкина, определяется теоремой Белаги [7], утверждающей, что для любого п всякая схема вычисления многочлена Рп{х) содержит не менее [(и+1)/2] операций умножения (деления) и не менее п операций сложения (вычитания).

Для ускоренного вычисления функций применяются параллельные алгоритмы вычисления аппроксимирующих полиномов.

Ускорение в этом случае достигается не за счет сокращения общего количества операций, а за счет параллельного выполнения взаимно независимых частей аппроксимирующего функцию алгоритма при условии готовности значений данных. Многочисленные примеры параллельных алгоритмов вычисления полиномов представлены в [10, 11, 13 — 16].

Все параллельные алгоритмы здесь и в дальнейшем описываются на модели неветвящейся параллельной программы. Понятие неветвящейся параллельной программы как последовательности параллельных арифметических команд заимствуется из [17]. При этом арифметические команды отождествляются с конкретными арифметическими операциями. Временная сложность алгоритма понимается как длительность выполнения представляющей его неветвящейся параллельной программы. Ускорение — как отношение временной сложности последовательного алгоритма к временной сложности его параллельного варианта, эффективность — как отношение ускорения к количеству процессоров, требуемому для реализации параллельного варианта алгоритма с максимальным параллелизмом каждого-последовательного шага. Более точно в дальнейшем временная сложность алгоритма измеряется количеством последовательных шагов его выполнения, при этом будет учитываться вид операции на каждом последовательном шаге. Временная сложность будет обозначаться Т(я), где R - количество процессоров. Каждое из данных понятий аналогично интерпретируется в [18-24]. Конкретная программная.реализация неветвящихся параллельных программ в данной модели не учитывается, не учитывается отображение на архитектуру параллельной вычислительной системы. Данная модель абстрагируется от способов обмена: в рамках модели * предполагается [17], что параллельная вычислительная система работает как идеальный параллельный процессор [20].

Пусть до начала вычислений известна вещественно-значная функция f(x), допускающая полиномиальную аппроксимацию f{x)K±aixl. (2)

1=0

Пусть /(х) задана на фиксированном отрезке [а, б], допустимая погрешность аппроксимации (2) s также фиксирована, т.е. а = const, b =const , е = const, х е \а, b\. В этих условиях степень п и коэффициенты at априори могут быть найдены. Поэтому можно считать, что при каждом значении 1=0,1,., п at = const , п = const. (3)

Полином (2) разлагается на квадратичные множители: где а=1 при п нечетном и а=0, если п четно; ап, г, вещественны,

1=1, 2,.,[п/2]. (Разложение (4) получается из известного п разложения Рп{х)=ап\\{^~У,-)> гДе У/ ~~ вещественные или комплексно1 сопряженные корни). В условиях (3) ап, г, р{, д1, /=1, 2,., [и/2] можно также считать вычисленными и априори известными. Поэтому для (3) можно построить неветвящуюся параллельную программу [17—19]: Шаг1: х+г, х+р¡, /=1, 2,., [и/2].

Шаг2: ап(х+г), {х+р)2, 1=1, 2,., [п/2]. (5)

Шаг 3: (х+р{)2+д{, 1=1, 2,., [и/2].

Шаги 4, 5, ., ["к^2([и/2]+1)1 состоят в умножении" по схеме сдваивания [18, 19] [и/2]+1 сомножителей и ап(х+г), вычисленных на шаге 3. Здесь и ниже |~а~| - ближайшее целое, не меньшее самого числа; [а] -целая часть числа (наименьшая часть числа, не превосходящая а). Имеет место

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

Г([и/2]+1)=(Т1оё2([и/2]+1)1+1) 1у п)гу =0(1о§2 п). (6)

Здесь и ниже, при оценках временной сложности, 1у — длительность одного бинарного арифметического умножения, /с - длительность бинарного алгебраического сложения.

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

В [6, 25] используется схема распараллеливания вида т-1 г=О являющаяся сравнительно универсальной и имеющая временную сложность рп(х)= 11хг{.(апгхт +аптг) хт+ап2тг)хт+. + а,г, п — г т.

Т(т) = — О(и) + 0( 1оё2т) > 0(^2 п)\ 1г=п-гт [ т

Известна следующая неветвящаяся параллельная программа вычисления значения полинома [26, 27]: Шаг 1: х • х.

Шаг 2: х2 -х; х2 -х2. ттт 4 • 4 2.4 3.4 4

1-1.1. цГ ^ • X * X 2 X * X ^ X ' X у X * X ■ ттт 29"1 29-1 2 2<?1 29-1 ^ П 1

Шаг д: х -х; х -х ; .; х -х ; д <| (7)

Шаг [~1оё2 п |+1: щ х1, / = 1, 2,., п.

Шаги [~1о§2и]+2, 2(~1о§2и~]+1 состоят в сложении по схеме сдваивания. Очевидно, временная сложность алгоритма (7) есть

Т(п)=(Г1оё2 п\ +1)^ + Г1оё2 п\ Гс ~ 2 \о%2 п та , /с) = 0(1о§2 и)

Данная неветвящаяся параллельная программа применима для параллельной полиномиальной аппроксимации функций в условиях сходимости. Схему Горнера [28] параллельный алгоритм (5) ускоряет в ~ п [{ + ¿с): n)ty) ~ 2 л 1п2 раз при ? « ценой затраты п/2 процессоров. Отсюда ее эффективность ~41п2 Неветвящаяся параллельная программа (7) универсальна, но обладает вдвое меньшим ускорением и вчетверо меньшей эффективностью.

Для деления применяется следующая неветвящаяся параллельная программа [29]. Пусть в результате редукции вещественного аргумента функции х 1 выполнено соотношение хе к Пусть выбрана двоичная система счисления. Тогда для редукции достаточно выделить порядок и мантиссу: х 1 =2 р-т\ \^<т< 1 [29] Пусть аппроксимация т 1 выполняется по методу Эмбла [30] у0=2-т. (8) т 1 ~

Стандартным приемом [30 - 32] (8) разворачивается в полином

1=0 1=0 1=0 2=1 -т. Аналогично разложению для треугольных матриц, использованному в [33 -35], получается

9)

1 + 2 ъ

1=0 1 где г требуется выбрать так, чтобы 2 -1=/+2, что всегда можно сделать, не увеличив погрешности метода. Тогда к=log2 (z+З) - 1.

Неветвящаяся параллельная программа для (9) примет вид: Шаг 1: z2.

Шаг 2: (z2f.

Шаг к: (z2*-' J. (10)

Шаг k+1: 1+z2', / = 0,1, .Д.

Шаги к+2, к+3, ., &+[~log2(A;+l)~|+l состоят в умножении по схеме сдваивания сомножителей (10), вычисленных на шаге к+1. В описанных условиях имеет место

Теорема 2. Функция х~1 может быть вычислена посредством неветвящейся параллельной программы (10) со сложностью

Г(1оё2 (i+3))=(log2 (i'+3)+j"log2 log2 (/+3)] + 1)^+3^, (11) где i+3 - наименьшая целая степень двойки, такая, что число итераций i+\ в (8) достаточно для достижения требуемой точности вычисления.

Сложность ' неветвящейся параллельной программы (10) ~ (1о§2 = 0(\о^2 /); ускорение метода Эмбла ~2/1п2; эффективность 2/1п2/к^2/ ~ 2/1п22. Вычисление (9) на одном процессоре возможно со сложностью ~ / ({у +tc) = /). Данные оценки можно считать оценками сложности деления, ввиду того, что у/х=у-х~х.

Схемы кусочно-полиномиальных аппроксимаций. Схемы кусочно-полиномиальной аппроксимации часто рассматривали в качестве V оптимальных машинных алгоритмов вычисления функций [36,37]. Такое представление об .оптимальности обусловлено следующими качествами данных схем. Аппроксимирующий полином строится на каждом подынтервале, объединение подынтервалов покрывает основной интервал. Длину подынтервала можно выбрать такой малой, чтобы приближение на нем достигало априори* заданной границы погрешности. На этой основе возможно достигать высокой точности приближения полиномом малой степени. Именно это качество определяет преимущество таких схем и .сравнительную оптимальность их временной сложности.

При построении таких схем, однако, в окончательной форме нет общего подхода: в зависимости от разновидности приближения на подынтервале, схемы отличаются количеством операции, временем и точностью вычисления. Например, для аппроксимации на подынтервале в [38] предлагается1 использовать интерполяционный полином Ньютона, в котором не приводятся подобные, вследствие чего аппроксимация обладает существенно избыточным числом операций. В [39] ту же аппроксимацию предлагается выполнять с помощью интерполяционного полинома Лагранжа. В общем виде приведение подобных не осуществляется, и эта схема обладает тем же недостатком избыточности. Существуют разновидности [1] аппроксимации на подынтервале с помощью метода «цифра за цифрой», в которых, как и в отмеченных схемах, не сохраняется инвариантность относительно произвольной точности приближения, не достигается оптимизация временной сложности на подынтервале. Аналогичный недостаток сохраняется при аппроксимации на подынтервалах с помощью ортогональных полиномов Чебышева [36, 37].

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

Некоторые разновидности приближений функций. Разложение функции /(х) по невязкам строится следующим образом. Пусть функция У - /(х) задана уравнением

12) I

Невязка уравнения (12) [2] определяется соотношением получающимся при замене точного значения у на у0, которое является приближением функции у=/(х) на заданном отрезке \а, Ь]. При этом необходимо выполнение условия Нш г0=0. Один из способов получения

У~*Уо разложения функций по невязкам состоит в том, что из уравнения невязки (13) определяется х0=ф(у0,г0), а из этого уравнения находится искомая функция /(х)=/(ф(у0,г0))- Для наиболее часто употребляемых элементарных функций допускается представление суперпозиции функций /{ф(у0,г0)) в явном виде. При соответствующем выборе структуры невязки

13) уравнения (12) для хе[а, Ь\ элементарные функции (1 + х)", ах, 1пх, агсэтл:, агссозх, ак^х, АгбЬл;, АгсЬх, АлЬх удовлетворят функциональному уравнению: /(*) = /(*0)®Ф (*о)> гДе хо=/~1(уо\/~1(у)~ взаимно обратная функция по отношению к у = /(х), у0 - приближенное значение к функции /(х), х&\а,Ь\, ® - знак некоторой операции (для функций (1 + х)", ха, ах знак ® означает операцию умножения, а для остальных функций - операцию сложения (вычитания)). Для рассматриваемых функций ер (г0) определяется на основе тождества ф (г0) = /(г0), а для остальных функций - на основе тождеств

Ф (^оЬДС1*^)*1) Для ха, ф (20)з/(г0/1па) для а\

Лы±11

А ^—I дЛЯ 1пд;

1 1 + гг 1 о.

В зависимости от выбранного вида невязки (знак «+» либо «-» зависит от порядка вычитания членов в невязке).

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

Для приближения табличных и аналитически заданных функций наряду с многочленами широко используются дробно-рациональные приближения вида [2]:

14)

1=0 1=0

Выражения, по которым вычисляются специальные функции- в вычислительных системах, в основном, — рациональные приближения. Это объясняется тем, что общее количество операций для достижения заданной точности при рациональном приближении обычно меньше, чем при многочленном. Однако при использовании дробно-рациональных приближений появляется операция деления, что не для всех вычислительных систем является удобным. Во многих вычислительных системах само деление организуется как приближенное вычисление функции /(х)=х-1, для которой требуется алгоритм, сопоставимый по числу операций с вычислением Як1 (х). В тех случаях, когда скорость деления близка к скорости умножения, эффективность использования рациональной аппроксимации возрастает. Общее количество операций при. вычислении цепной дроби меньше, чем при вычислении рациональной дроби, образуемой по схеме подходящей дроби [40]. Для цепной дроби с единичными частными числителями и положительными частными знаменателями относительная погрешность ее значения асимптотически (с точностью до бесконечно малых первого порядка) не превышает максимальной из относительных погрешностей ее компонентов независимо от числа звеньев дроби [41,42]. Вместе с тем на практике, при вычислении цепных дробей в режиме с плавающей точкой, погрешности округления могут накапливаться быстрее, чем при счете дробно-рациональной функции [9]. Цепную или непрерывную дробь определяют как выражение а.

Ь0 +

7 а ъх+-

Ы-К.,' в* ьк+~ где — — к-е звено цепной дроби; Ь0 - нулевое звено; а 1 - частные делители; К

Ь1 - частные знаменатели (/=1,2,.). Помимо отмеченных, имеется еще одно затруднение: цепная дробь, непосредственно по построению; не допускает эквивалентной записи в параллельной форме. Отсюда вытекает существенное несоответствие тенденции распараллеливания вычислений и несоответствие архитектуре программного обеспечения параллельных вычислительных систем.

Иногда с помощью сжатия цепных дробей удается преобразовать равноценную цепную дробь в соответствующую. Для построения равноценных цепных дробей на практике чаще всего используют тождество« Эйлера [40] к ахх а2х ахаъх яг2 а1 х

2-1акх =ао + —--—---;-------;-

Л=о 1 а1+а2х а2+а3х + а1 х

С целью уменьшения количества операций умножения при вычислении рациональных функций вида (14) для числителя и знаменателя можно использовать схему Горнера либо методы Мотцкина - Белаги - Пана.

Одним из методов получения дробно-рационального приближения является аппроксимация Паде. Под обычной аппроксимацией Паде понимают получение дробно-рационального приближения Як1{х), для которого при х —> 0 точность приближения составляет при условии, что на заданном интервале знаменатель ни в одной точке не обращается в нуль. При таком определении аппроксимации Паде она является естественным обобщением разложения функции в ряд Тейлора. Метод Паде позволяет получить рациональные приближения из степенного ряда.

Примером итеративного процесса является модификация метода Чебышева. Метод Чебышева построения итераций высших порядков [43] основан на отыскании корней уравнения /(х)=0. По модифицированному методу Чебышева [44] рассматривается уравнение х,у)=0, (15) где х<=\а, Ь ], у - искомая функция или г0=Г(х, у0), где у0 - приближенное значение искомой функции на заданном промежутке а, б]. Пусть функция г=Е{х,у) непрерывно дифференцируема достаточное число раз по у в окрестности точки у0. Формула для построения итераций высших порядков по модифицированному методу Чебышева [44, 45] имеет вид

3 12?К*,у,У-4>М2?Ы ,, ч

---77YT-ч s -z \Х,у.)----.

Zy (х, У,)]

Если в выражении (16) оставить два члена, получится итерационная формула второго порядка (метод Ньютона) [1]. Если оставить три члена, получится итерационная формула третьего порядка, и т.д.

Модифицированный метод Доморяда получается при задании уравнения (15) [2,44]. Итерационный метод Доморяда второго порядка сходимости совпадает с итерационным методом Ньютона. Итерационные формулы третьего и четвертого порядка сходимости соответственно имеют вид

F(x> У,Ж(Х>У^ где

A=[F'y{x,yi)]2-F(x, yi)F;(x,yi)/2,

B=[Fy{x,yi)f - F{x, у;Уу(х,У;)Р;(х,У;)+[Р{х, yi)]2F;(x,yi)/6.

Еще одним примером итеративного процесса является метод «цифра за цифрой». Для нахождения x=log2у (l<.y<2) ищется значение л: в двоичной системе:x=a0,aja2 . аи . (аг=0,1 ). Последовательно определяются хп> Уп> ап (л =0,1,-•■)*<)=*> Уи=У\ а{ = 0, если у\<2, оц = 1, если У2 >2. Пусть уже определены al5 a2, ., аг-! и найдено уг Если yi <2, то a• = 0, yi+l=yf. Если у] > 2, то а,- = 1, yi+l=2~lyf. После п шагов найдутся п цифр двоичного разложения x=log2 у « 0, at a2. .an .

В' алгоритмах вычисления функций, основанных на методах «цифра за цифрой», используются итеративные процессы, позволяющие последовательно определять цифровое значение /-го разряда аг искомого значения функции f{x), заданной в позиционной системе счисления. Большинство алгоритмов рассматриваемого вида разработано для двоичной системы счисления, хотя имеются алгоритмы для десятичной и произвольной систем счисления [2]. Длительность работы алгоритма пропорциональна числу разрядов с достаточно большим значением коэффициента пропорции. Схема «цифра за цифрой» по этим причинам не соответствует архитектуре суперкомпьютеров, число разрядов мантиссы в которых достигает 256 и более цифр [46 - 52]. Трудности усугубляются тем, что в описаниях метода, как правило, не указывается зависимость точности аппроксимации функции от диапазона изменения независимой переменной'. С другой стороны, методы типа «цифра за цифрой» успешно применяются в специализированных устройствах, где упрощается обработка текущего разряда [53, 54]. Очевидна возможность конвейеризации метода в общем случае.

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

Методы кусочной аппроксимации можно условно разделить на три группы: простая сегментная аппроксимация, телескопическая сегментная аппроксимация и нониусная сегментная- аппроксимация: При простой сегментной аппроксимации исходный промежуток \а, b\ разбивается на ряд непересекающихся подынтервалов. На каждом подынтервале искомая функция f{x) приближается многочленом, дробно-рациональной или нелинейной функцией, содержащей малое количество параметров и операций. Простую сегментную аппроксимацию наиболее удобно реализовать в вычислительной системе, если на всех подынтервалах функция1 /(х) приближается выражением одного вида. Частным случаем такого приближения является сплайн. Пусть отрезок \а, б] разбит на N равных частичных отрезков *,•+)]> где Х;=а+1Ъ, 1=0,1,.,N -1, хы=Ь, к={Ь-а)!N. Функцию &т (х) называют сплайном степени т дефекта к, если Зт(х) - полином степени? т на частичном отрезке [д:,-, х(+, ] и £т(х) е С тк \а, Ь]. На практике наиболее широкое распространение получили^ сплайны третьей' степени, имеющие на [а, Ъ\ непрерывную, но крайней мере, первую производную [55, 56]. При условии высокой точности резко* возрастает количество частичных отрезков и; как следствие, время г вычисления. С возрастанием степени сплайна возрастает число уравнений-системы, по которым: согласуются: значения производных, поэтому на; практике: ограничиваютсясплайнами невысокой степени.

При нониусной кусочной аппроксимации сначала аргумент приводится к нониусу (относительно небольшому промежутку), в котором вычисляется; нониусное значение функции. Затем с использованием опорных; значений, получают искомое: значение функции. Опорные значения могут находиться в: памяти вычислительной системы или вычисляться каким-либо быстрым» способом. В основу нониусной кусочной аппроксимации могут быть положены разложения функций по невязкам [36, 57 - 59]: К ним примыкают методы;. называемые табличными или. таблично-алгоритмическими- [6, 60 -63].

При' телескопической сегментной аппроксимации система вложенных подынтервалов; строится; так, что они- имеют вид +/г(х)), где ¡г{х) зависит от свойств функции /(х)1 и количества.точек разбиения. В некоторых случаях систему подынтервалов выбирают таким способом, чтобы> на больших подынтервалах многочлен, аппроксимирующий функцию, имел на одно слагаемое больше, чем на меньших подынтервалах. При этом-каждому подынтервалу соответствует многочлен с разными коэффициентами [36, 64, 65].

Для приближения функций в вычислительной системе часто используется интерполирование функций. Пусть на отрезке \а, b] задано п+1 значение функции y=f(x): y0=f(xQ), y.x=f(X]), ., yn=f(xn) в точках а<х0 < x1 <х2 <. < хп < b, которые называются узлами интерполяции. Требуется построить интерполирующую функцию F{x), принадлежащую определенному классу и принимающую в узлах интерполяции те же значения, что и fix). Если интерполирующую функцию F(x) задать в виде многочлена Рп{х) степени не выше п, то всегда существует только один интерполяционный многочлен, который может быть представлен в различных формах. Таблично заданную функцию {хг}, /(х;), /=0,п, можно приблизить с помощью многочлена Лагранжа

Р М- ги \ )(х~хг) (*~*н) , \ (х-х0){х-х2) ■■• (х-х„) хо-^ххо-хз) ••• (х0-х„) (л^ - х0 ДЛ^ ~ Х2) ••• - X „) /(* )- (Х-Хо)(Х~Х\) ••• (Х~Хп-\)

Хп~ХоХХп~Х\) {Хп~Хп-1)

Интерполирование с использованием многочлена Чебышева функции п х)ща, Ь] базируется на минимизации выражения тах ^(х-х^). Узлы к=О интерполяции выбираются в нулях многочлена Чебышева: х1 =(а + б)/2+((б-а)/2)-со8 [(2/+1)я/(2и+2)], /=07п. Интерполяционный многочлен имеет вид / 1 л л г (2х-Ъ-а\

2 к=1 V. Ь~а ) где Ак=——^/(^соб^*"1"^71, к=0,п; Тк(х) - многочлен Чебышева. п+1 2 п +2

Если функция /(х) для хе[0, 2тг] является периодической с периодом Т=Ь-а и задана в 2п+1 узлах интерполяции /(.хк), А:=0, 2и, и у(а)=у(Ь), то ее можно интерполировать тригонометрическим многочленом о. п х) =~ + ХКя* со8 кг + Ьк бш кг), 2 к=1 где хе[0, 2%).

Ъ—а

Для приближения функций, кроме многочленов и рациональных дробей, используются и более сложные выражения [66 - 74]. Рассмотрим две ограниченные функции /{х) и тз(х): М, < /(*)< М2, 0 < А^, < ш(*)< заданные на множестве

Х={хеХ:а<х<$}, (17) содержащем не менее тп + 2 точек, и приближающую функцию

Г(А,х)=Е(а0,а1,.,ат;х), А&Р, (18) где Р — открытое множество (т+1)'-мерного пространства.

В качестве меры близости функций /(х) и ^(А, х) принимаем норму ||/ - = шах|г{А, х)|, где г(Л, х)=[/(х)-Г(А, х)]/т(х). хеХ

Необходимо найти такую функцию В вида (18), чтобы

Х&Л.

Таким образом, ищется наилучшее приближение с весом ш(х) выражением вида (18) функции /(х) на множестве чисел (17).

Приближения тригонометрическими полиномами используются, как правило, для характеристики качеств аппроксимируемой функции, выражаемых периодическими свойствами [75 - 77]. Это делается для того, чтобы получить по возможности адекватное представление о физическом процессе, который выражается посредством аппроксимируемой функции. В качестве одного из источников приближения функций тригонометрическими полиномами используется интерполяция на основе полиномов Чебышева. Полиномы Чебышева I и II рода традиционно [30, 78] обозначаются Тп (х) и

Un(x). Для цели аппроксимации функций используются соотношения: r„(x) = cos(«6), X = COS0, r2w(sin0)= (-1)" cos(2«0), (19)

T2n+l (sin 0) = (-1)" sin((2« + 1)0), (20)

Un (x) = cosec (0) sin((n +1)9), x = cos 0,

COS0

22)

COS0

На этой основе конструируется полином, интерполирующий функцию /(х), в виде m

23) z = 0

Чаще встречаются разложения по ортогональным полиномам [43] вида - Рп (4

Рп СХ)=С0 + ClTl iX)+c2T2 (*)+- + с„ Тп М>

С0=— J/(cos в) d0, ск=- J/(cos cos кв dO, (k>l),

7Г Q 7Г q

24) где Тк (х) - алгебраические полиномы. Такие приближения используются в качестве наилучших среднеквадратичных приближений. С другой стороны, приближения (19) - (23) используются как среднеквадратичные приближения функций непосредственно тригонометрическими полиномами, в частности, для приближения функций, заданных таблицей, по методу наименьших квадратов. В последнем случае тригонометрические полиномы образуют ряд Фурье [43]. Обе формы интерполяционных полиномов связаны между собой, допуская преобразование одной формы в другую. Эти преобразования основаны на известных рекуррентных зависимостях [30, 78]

ТтЛХ)=2хТт(Х)-Тт-х{Х) 1

Г0(х) = 1, 7;(л;)=л; У

0(х)=1, и1(х)= 2х ]'

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

РА{х)=а$ хА + ах хъ + . + а4 используется преобразование:

Ф) = «оЫ*) + ЬМ+* +я4},

27) где

A-j ——-——, А/2 ——~— —— + (Aj + l)A, j ,

2 а0 а() а0 — + l) + A,j, —-— %2 А<з ■ aQ aQ

В качестве сложного для компьютерной реализации примера ортогональных многочленных разложений можно привести разложение [1]

1 1 a-bx Ja2—b2

Г1+2±ркТк(х) к=1 |б|<Я, I JCI <1, а-4а2~Ъ2 2 рп ь ' -р) оо l + 2Z(-lfqkTk(2x-l)

-, 0<jc<1, q = 2a+\-2^a2+a a+x Jâ* a +a

Формула справедлива и для комплексных а при ] , аФ0.

В качестве еще более сложных для компьютерной реализации алгоритмов можно взять следующие примеры. Для вычисления корня используется рациональная дробь вида [1]

Для показательной функции используется разложение по многочленам Чебышева [1]:

2х-22 о

Гл \ оо (л Л

1п2 ч2 у к=1

2ЕА -1п2 Тк{2х-\) У 0 <х< 1, при к>4 к з2 -ю-* к\

Для вычисления гамма - функции и ее преобразований [79]:

00

Г(г)=рг \е~рЧ2-хЖ, Я{р)>О, Я(г)>0; о если 0<7фг)<1;

Г(г+п)= п-1 к=О г(г)г(1 - г)=71 созес 7Г г; Г(тг)={24Х~т)12ттг-1121[Т{г+г/т)включая логарифмическую производную а х¥(г)=—либо \nT(z) = ZЫt)dt; с12 1 ш-1 иг)=/и 1 ^^{г+к/гг^+Хпт; к=о п-1 о

1)=-у, у=0,57721566490153286061; используются следующие разложения [79]:

1пг(2+1)=£(-1)Ч^Л> М<1, к=\ г = 1

1/Г(г + 1)=2>*г\ До=1, Н<оо, к=0 г гаг = Ц{-1) к+^кагк, г> 0, ¿=1 а также разложение в ряд Тейлора [79]: оо оо и =0 л=О

Помимо того, применяются ортогональные разложения по полиномам Чебышева:

00 00 п=0 п=О ии ии

Г(1+3)=2>Х(*Х Г(1+х)=^7Г(х), 0 <х< 1 п=О

1пГ(х)= и=0 П 1

1пх -х +—1п27г+5,(х), х-

2, ф)=(12*Г'2;(-1)чг2„ п=О

Г-1

Vх/ х>1

Т(т)(х+3)=|;С^)Г;(х), т=0,1,.,6, ^(0)(х+3)=^(х+3), 0<х<1. п= О

Примером рационального приближения функции ^(г), представимой в виде гипергеометрического ряда ^(г) +у служить приближение вида [79]:

2И

3^2

1,1,2-г 2,1+г

-1 может

ЛЛ >-( >"к [(2)4]2(3-г)4 4 \ 1+*. 2+4, 3

4(г)=(г3+387г2 + 2906 г+192о)/12,

4(г)=(зг4 + 3643 г3 + 86068г2 + 293508г+ 149760)/б0, 1

Я3(г)=14г2+204г+ЗЮ, Я4(г)=22г3+864г2 + 4958г+4956 . Для вычисления кубического корня предлагается [79] аппроксимация Паде:

- 1 у/з 1+V (4/3) Вп (г,1/3) , , il.il V ^

-1/3(2/3)„^(г,-1/3) 1/3), ф)пВп(гМъ) агё(1+ 1/г)| < 71,

2?и (г, 1/3) =«0-1 ±ак гк , Вп (г, -1/3) '' ** • к=0 £=0

Для интегралов Френеля используются разложения вида [79]: )г1/2 соз/^=х,/2Г2п(х/8), |Г1/2 *ШЖ=хх1г Т2п+1(ф), 0 <х< 8, л=0 и=0 п=О

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

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

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

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

К цифровым .фильтрам относятся- фильтры с конечной импульсной характеристикой (КИХ-фильтры) и фильтры с бесконечной импульсной характеристикой (БИХ-фильтры). КИХ-фильтром - называют фильтр, у которого импульсная характеристика представляет собой конечный дискретный сигнал (Л^-точечный дискретный сигнал), который может принимать от нуля; значения: лишь при п=0,1, .,N-1БИХ-фильтром называют фильтр, у, которого импульсная характеристика может принимать отличные от нуля значения на-бесконечном множестве значений; п=0,1,. В случае, когда представляемая последовательность имеет конечную длительность, т.е. имеет только конечное число ненулевых значений,. используется1 вид преобразования Фурье, называемый ДПФ. ДГГФ есть преобразование Фурье4 последовательности конечной длины, являющееся? само по себе также последовательностью; а не непрерывной функцией, которое соответствует равноудаленным по частоте выборкам преобразования Фурье-сигнала.

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

Несмотря? на наличие процессоров- ЦОС с быстродействием: порядка нескольких миллиардов комплексных умножений в< секунду, проблема; повышения' быстродействия? алгоритмов ЦОС остается? актуальной [82, 83]. Это связано с тем, что ряд задач, например цифровая обработка движущихся изображений; в; реальном масштабе; времени, требует больших вычислительных затрат. К числу таких задач относятся также различные видеосистемы слежения; и телеметрии. Значительные вычислительные, а следовательно; и аппаратурные затраты, необходимы при реализации нерекурсивных фильтров- нижних частот высокого порядка. Такие фильтры применяются в качестве ограничителей спектра; перед вторичной-дискретизацией сигнал а. в высокоточных скоростных интегральных аналогов цифровых преобразователях на основе дельта-модулятора.и; сумматора (ДЕ ,-АЦП). Применение быстродействующих алгоритмов- цифровой фильтрации позволяет сократить аппаратурные и вычислительные затраты, снизить стоимость устройств или систем. Кроме этого, появляется возможность уменьшить габариты, массу и энергопотребление [82], что особенно важно для бортовых систем и систем с автономным питанием. В системах ЦОС, работающих под управлением вычислительных систем, применение быстродействующих алгоритмов фильтрации дает возможность реализовать часть подсистем программно и, таким образом, отказаться от ряда средств аппаратной поддержки.

Существует ряд задач, которые трудно решить без применения быстродействующих алгоритмов ЦОС, несмотря на высокий уровень развития современной микроэлектроники. Это, например, создание радиолокатора реального времени с синтезированной апертурой при разрешении порядка длины волны (3-10 см) и хорошими массогабаритными характеристиками, формирующего трехмерное изображение на экране монитора. Такие системы нужны как для повышения безопасности посадки самолетов в условиях плохой видимости, так и для высокоточной воздушной разведки с помощью самолетов или вертолетов. I

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

Существует несколько алгоритмов ЦОС, для которых необходимы одни и те же основные операции. К таким операциям относятся свертка, корреляция, фильтрация, преобразования и модуляция.

Для двух заданных последовательностей конечной длины х(к) и к{к) с длиной Ы^ и Ы2 соответственно линейная свертка равна оо оо у(п)=к(п) <8> х(п к=-<я к-О где М = Их+И2- 1. Для двух заданных последовательностей х(к) и у(к) длины N с нулевыми средними значениями оценка их взаимной корреляции равна г. где гху{п) - оценка взаимной ковариантности, определяемая как Xх(к)у(к+п,), п= 0,1,2,. гху{п) =

N ь=о

ЛГ+л-1

1 ^+/7-1

- "=0,-1,-2,. ги(о)=± ТШ]1» «-„(о)=1 2 •

М к=0 ¿=0

Оценка автокорреляции рд:х(и) последовательности х(к) длины N с нулевым средним значением задается как ч гх(п) где гхх(п) - оценка автоковариантности, определяемая как Ы-п-1

М = — Xх{к)х{к+п), п= 0,1,2,.

Уравнение для фильтрации с конечной импульсной характеристикой имеет вид:

N-п-\ у(п)= /г (к)х(п-к), к=0 где х(^) и у{к) — соответственно вход и выход фильтра, а к(к), к = 0, 1,., 7У-1 - коэффициенты фильтра.

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

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

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

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

Анализ непрерывных (аналоговых) линейных стационарных систем в случае нулевых начальных условий при частотном подходе выполняется в последовательности [84]:

- с помощью прямого преобразования Фурье определяют спектр Х(у со) входного сигнал *(/);

- умножением спектра ^Т(у'со) на комплексный коэффициент передачи системы //(у ю) находят спектр выходного сигнала у(7):

- с помощью обратного преобразования Фурье функции Дую) вычисляют реакцию у{Г) системы на воздействие х{{).

Сравнение спектров непрерывных х(/) и дискретных сигналов позволяет выявить их общие свойства и различия. Общим является то, что периодические сигналы описываются рядами Фурье, а непериодические -преобразованиями Фурье. Спектры периодических сигналов — дискретные линейчатые, расстояние между спектральными линиями определяется частотой повторения сигнала. Спектральная плотность непериодического аналогового сигнала представляет собой непрерывную функцию частоты со, а спектр дискретного сигнала х\п\ - периодическую функцию частоты со с периодом, равным частоте дискретизации юд = - 2%/Т.

Анализ дискретных линейных стационарных систем в случае нулевых начальных условий при частотном подходе выполняется в последовательности [84]:

- с помощью прямого ДПФ определяют спектрХ(к~) входногосигнала х[и], {п = О, N -1);

- умножением всех компонент спектра Х{к) на комплексный коэффициент передачи системы для соответствующих частот находят спектр выходного сигнала у\п\:

Y(k) = Х(к)Н f .271 ^

J-* ч NT (к = 0,N

- с помощью обратного ДПФ функции У(к) вычисляют реакцию у\п\ системы на воздействие х[п]. I

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

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

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

Существует множество применяемых для данных целей преобразований. Преобразование Винограда-Фурье [85 - 87] и алгоритм первоначального множителя [85, 87] представляют собой оригинальные, но сложные методы повышения скорости вычисления БПФ. Дискретное косинус-преобразование особенно целесообразно для сжатия данных. В рамках преобразования Уолша сигнал раскладывается на прямоугольные импульсы; а не на синусоиды, и преобразование вычисляется быстрее, чем БПФ. Преобразование Адамара, построенное с помощью перестановки последовательности Уолша, вычисляется еще более быстро. Преобразование Хаара полезно для определения краевых элементов при Обработке изображений [88].

1. Дискретное косинус-преобразование по сути представляет собой действительную часть ДПФ п=О v N

2. Дискретное преобразование Уолша [89] основано на наборе гармонических прямоугольных импульсов, которые называются функциями Уолша WAL (n,t) (t — время, п - порядок). Четные функции WAL(2£, t) записываются как CAL (A:, t), а нечетные функции WAL(2¿+1, t) записываются как SAL(2á:+1, t), где к=\, 2,., N/2—1. Любую функцию f{t) можно разложить по набору функций Уолша (аналог разложения в ряд Фурье) как

N/2-XN/2-1 tf0WAL(0, t)+ £ Xk SAL(i, t) + b, CAL (y, t)],

1=1 j=i где а,- и b — коэффициенты ряда.

3. Преобразование Адамара (Уолша-Адамара) - это, по сути, то же преобразование Уолша, но с другим порядком функции Уолша и, следовательно, строк матрицы преобразования. Получающаяся при такой перестановке матрица Адамара содержит подмассивы матриц второго порядка. Например, матрицу Адамара порядка 8x8 можно записать через матрицы

2Н=

Любую матрицу Адамара порядка 2И можно рекурсивно получить из 2Н как

1 1" и — 2Н= "-1 -1~

1 -1 -1 1

Н= N н N н н -"н

4. Вейвлетное преобразование предоставляет средства для анализа нестационарных сигналов [83]. Вейвлетное преобразование применяется также для фильтрации сигналов, устранения шумов, определения местонахождения сингулярностей и их распределения. В вейвлетном преобразовании в качестве весовых коэффициентов значений сигнала выступают вейвлетные функции. Все вейвлетные функции получаются из основной (материнской, базовой) вейвлетной функции. Например, морлетовская, или модифицированная гауссова материнская вейвлетная функция (вейвлет Морле) [83]

Фурье-образ которой

Н( со)=л/2^е(с0~Юо)2/2-Остальные (дочерние) функции получаются путем такого изменения масштаба материнской, чтобы образовалось семейство функций. Каждую дочернюю функцию можно записать как

-^{(г-т )/*},

Ыа где а - переменный коэффициент масштабирования, т - константа переноса.

В большинстве (фактически во всех случаях) рассмотренных преобразований необходимо вычислять базисные, функции. Так, в двух последних случаях это* е,ю°' , е~' e"(U)wo) jj преобразованиях Фурье к2%п\ . (к2пп\ гг такими функциями являются cos - и sin -— . При вычислении

N* V Nкорреляции присутствуют операции- деления и вычисления; квадратного? корня: рху{п)= у / \ 1/2 • В ряде ортогональных разложений! ^хх У^туу \Р/] базисными функциями; являются алгебраические: и тригонометрические: полиномы. Рассмотренные базисные функции необходимо вычислять для каждого элемента прямого и, обратного ортогональных разложений; г поскольку аргументы базисных- функций меняются в зависимости от порядкового номера элемента базиса.

Первый важный аспект этого обстоятельства - это то, что-большой объем? вычисления: базисных функций принципиально влияет на быстродействие ЦОС в целом.

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

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

Если, наконец, алгоритмы вычисления базисных функций* не инвариантны относительно произвольно заданной границы, погрешности: вычисления; то при переходе от одной задачи к другой могут измениться программные и аппаратные параметры выполнения ЦОС.

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

На основании изложенного целью диссертационной: работы является разработка и исследование: компьютерных алгоритмов- минимизации' временной сложности вычисления функций с обеспечением инвариантности! алгоритмов относительно вида функций,, точности их вычисления; промежутка изменения аргумента. Оптимизированные алгоритмы должны, применяться для параллельного вычисления одновременно всех, элементов; базиса ортогональных разложений, используемых в ЦОС, и при этом отличаться: инвариантностью относительно вида разложений; быть совместимыми с параллельным выполнением базового набора операций ЦОС в целом. I

Для: достижения поставленной! цели в диссертационной работе: решаются следующие задачи:

1. Средствами информатики и информационных технологий построить устойчивую распараллеливаемую схему минимизации временной' сложности таблично-алгоритмического вычисления; функций; на основе: интерполяции по Ньютону, которая: была, бы инвариантна относительно вида, функции, промежутка изменения аргумента и априори заданной границы,погрешности:

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

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

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

5. Синтезировать алгоритм параллельного выполнения ДПФ и О ДПФ на основе таблично-алгоритмической аппроксимации всех элементов базиса с временной сложностью Т = 0 (1оё2 А^), который отличался бы минимизированнымь до значения 0(1) числом последовательных умножений, а также инвариантностью относительно количества отсчетов в условиях произвольно заданной границы погрешности вычислений.

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

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

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

Научная новизна диссертационной работы заключается в следующем:

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

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

3. Дана программная реализация предложенных таблично-алгоритмических схем, выполнен численный эксперимент и сравнение с известными методами, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной временной сложности алгоритма, - предложенные схемы ускоряют известные методы в 0(\og2m), где т — степень аппроксимирующего полинома, и позволяют достигать времени O(l) параллельного выполнения всего комплекса данных вычислительных схем в случае априори заданных функций.

4. Разработан метод динамически распараллеливаемого вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью Т = 0(log2 N), который отличается инвариантностью относительно количества отсчетов N и сохраняет данный порядок оценки при параллельном выполнении ДПФ и ОДПФ в делом. В случае применения таблично-алгоритмической схемы для параллельного вычисления элементов базиса отличие от известных аналогов заключается в сокращении до 0(1) количества последовательных умножений в условиях произвольно заданной границы погрешности вычислений.

5. Предложены модификации параллельных схем выполнения ДПФ для параллельного выполнения БПФ и вычисления частичной суммы ряда Фурье. Разработанные схемы распространяются на параллельное выполнение совокупности алгоритмов ЦОС, включающей операции корреляции, свертки, ковариации и ОДПФ, при- этом сохраняется- логарифмический порядок оценок временной сложности. Видоизменения данных схем с сохранением порядка оценок распространяются на случай двумерных ДПФ и ОДПФ: Предложенные схемы отличаются от известных аналогов построением, сокращением числа последовательных умножений и, в частности, тем, что число процессоров модифицированного БПФ сокращается в \og2 N раз при сохранении логарифмической оценки временной сложности вычисления.

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

Основные положения, выносимые на защиту:

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

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

3. Выполнены программные реализации таблично-алгоритмических схем, численные эксперименты, показывающие отличительно высокую точность вычисления функций, производных и интегралов при минимальной-временной .сложности алгоритма. Предложенные схемы ускоряют известные методы в 0{\о£2т), где т - степень аппроксимирующего функцию полинома, и позволяют достигать времени 0(\) параллельного выполнения1 комплекса данных вычислительных схем для априори-заданных функций.

4. Разработан метод динамически распараллеливаемого вычисления всех последовательных элементов тригонометрического базиса ДПФ' с временной сложностью \0g2N), инвариантный относительно количества отсчетов N, который сохраняет порядок данной оценки при параллельном выполнении ДПФ и- ОДПФ в целом. При этом применение таблично-алгоритмической схемы для параллельного вычисления базиса позволяет сократить количество последовательных умножений до 0(1) в условиях произвольно заданной границы погрешности вычислений.

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

Данные схемы с сохранением порядка оценок распространяются на двумерные ДПФ и ОДПФ.

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

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

Внедрение и использование результатов работы. Результаты диссертации приняты к использованию в ОАО «Таганрогский завод «Прибой» в качестве единой распараллеливаемой схемы минимизации временной сложности кусочно-полиномиальной аппроксимации функций применительно к основным алгоритмам ЦОС; в госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания» (№ гос. регистрации 01.2.00 106436, код ГРНТИ 28.23.15), проводимой на кафедре информатики ГОУВПО «ТГПИ»; в учебном процессе факультета информатики Таганрогского государственного педагогического института в курсах «Математика и информатика», «Численные методы», «Компьютерное моделирование», курсах по выбору и практикуме решения задач на ЭВМ, что подтверждено соответствующими актами об использовании, приведенными в приложении 3 к диссертационной работе.

Апробация работы. Основные результаты работы докладывались на следующих семинарах и конференциях:

-Международная научно-техническая конференция «Математические модели и алгоритмы для имитации физических процессов» (Таганрог, ТГ1Ш, 2006 г.).

- The Fourth International Conference «Theoretical and Applied Aspects of Program Systems Development» (Ukraine, Berdyansk, 2007).

- XII международная конференция «Математические модели физических процессов» (Таганрог, ТГПИ, 2007 г.).

- VII международная научно-техническая конференция «Математическое моделирование, обратные задачи, информационно-вычислительные технологии» (Пенза, ПТУ, 2007).

-Всероссийская научно-техническая конференция с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, ЮФУ, 2008).

Публикации. По материалам диссертационной работы опубликовано 11 печатных работ общим объёмом 10,3 печатных листов, в том числе статья в журнале из списка допущенных ВАК РФ.

Структура и объем работы. Диссертационная работа состоит из введения, 3 глав основного раздела, заключения, списка литературы и 3 приложений. Основное содержание работы изложено на 154 страницах, включая 33 таблицы, 4 рисунка и список литературы из 113 наименований.

Заключение диссертации по теме «Теоретические основы информатики», Аксайская, Любовь Николаевна

3.9. Выводы

1. Предложен метод параллельного вычисления всех последовательных элементов тригонометрического базиса ДПФ на основе схемы Стоуна с временной сложностью Т= 0{[og1N\, который отличается от известных аналогов по построению, инвариантностью относительно количества отсчетов, при этом позволяет сохранять- данный порядок временной сложности при* параллельном- выполнении ДПФ и О ДПФ с применением схемы сдваивания.

2. Синтезирован алгоритм параллельного выполнения ДПФ и ОДПФ на основе таблично-алгоритмической аппроксимации всех последовательных элементов базиса с помощью интерполяционного полинома Ньютона с временной сложностью Т= 0(к^2 ТУ"), который отличается от известных аналогов по построению, сокращенным-до О(ь) числом последовательных умножений и инвариантностью относительно количества отсчетов.

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

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

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

ЗАКЛЮЧЕНИЕ

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

Работа включает следующие научные результаты.

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

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

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

4. Разработана динамически распараллеливаемая схема вычисления всех последовательных элементов тригонометрического базиса ДПФ с временной сложностью Т = 0 ЛГ) инвариантная относительно количества отсчетов А/", которая сохраняет порядок данной оценки при параллельном выполнении ДПФ и ОДПФ в целом. При этом применение таблично-алгоритмической схемы для параллельного вычисления базиса позволяет сократить количество последовательных умножений до 0{\) в условиях произвольно заданной границы погрешности вычислений.

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

Научная новизна'результатов диссертационной работы заключается в следующем.

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

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

3. Дана программная реализация предложенных таблично-алгоритмических схем, выполнен численный эксперимент и сравнение с известными методами, ' показывающие отличительно высокую точность вычисления функций, производных и интегралов, при минимальной временной сложности алгоритма,. — предложенные схемы ускоряют известные методы в 0{\о%2т\, где т - степень аппроксимирующего полинома, и позволяют достигать времени 0( 1) параллельного выполнения всего комплекса данных вычислительных схем в случае априори заданных функций.

4. Разработан метод динамически распараллеливаемого вычисления всех последовательных, элементовтригонометрического базиса ДПФ с временной сложностью Т = 0(Лг), который отличается инвариантностью относительно количества отсчетов. N и сохраняет данный порядок оценки при параллельном выполнении ДПФ и ОДПФ в целом: В случае применения таблично-алгоритмической схемы для параллельного вычисления элементов базиса отличие от известных аналогов, заключается в сокращении до 0( 1) количества последовательных умножений в,условиях произвольно заданной границы.погрешности вычислений.

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

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

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

Практическое использование результатов работы.

Полученные в» работе результаты использованы в ОАО «Таганрогский завод «Прибой»; в госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ГРНТИ 28.23.15, регистрационный номер 01.2.00106436; в учебном процессе кафедры информатики Таганрогского государственного педагогического института в курсах «Математика и информатика», «Численные методы», «Компьютерное

Список литературы диссертационного исследования кандидат технических наук Аксайская, Любовь Николаевна, 2008 год

1. Люстерник Л.А., Червоненкис О.А., Янпольский А.Р. Математический анализ: Вычисление элементарных функций. - М.: Физматгиз, 1963. — 248 с.

2. Попов Б.А., Теслер Г.С. Вычисление функций на ЭВМ: Справочник. -Киев: Наукова думка, 1985. 600 с.

3. Кобзев В.А. Синергетический метод аналитического конструирования систем взаимосвязанного управления движением гидросамолетов / Автореферат диссертации на соискание ученой степени кандидата технических наук. Таганрог: ТРТУ, 2006. - 17 с.

4. Ланцош К. Практические методы прикладного анализа. М.: Физматгиз, 1961.-524 с.

5. Литвин О.М., Рвачев В.Л. Класична формула Тейлора, й узагальнення та застосування. Киев: Наукова думка, 1973. — 122 с.

6. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. М.: Мир, 1977. - 726 с.

7. Белага Э.Г. О вычислении значений многочленов от одного переменного с предварительной обработкой коэффициентов // Проблемы кибернетики, 1961. Вып. 5. - С. 7-15.

8. Пан В.Я. Некоторые схемы для вычисления значений полиномов с вещественными коэффициентами // Проблемы кибернетики, 1961. -Вып. 5.-С. 17-29.

9. Fike С.Т. Computer evaluation of mathematical function. New Jersey: Prentice-Hall, 1968. - 228 p.

10. Winograd S. On the Parallel Evaluation of Certain Arithmetic Expressions. "Journal ACM", 1975. v. 22, № 4. - P. 477-492.

11. Winograd S. On the Speed Gained in parallel methods. "New Concepts andi

12. Technologies in Parallel Information Processing, Ed. Coianielle, Leiden, Nordhoft, 1975", 1975.-P. 155-165.

13. Motzkin T.S. Evaluation of polinomials. Bull. Amer. Math. Soc, 1956. — 61, №2.-P. 163.

14. РоммЯ.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки / Диссертация на соискание ученой степени доктора технических наук. Таганрог: ТРТУ, 1998. - 546 с.; ВНТИ Центр. - № 05.990.001006.

15. Maruyama К. On the Parallel Evaluation of Polynomials // IEEE Trans, on Computers, 1973. v. c, 22, № 1. - P. 2-5.

16. Miranker W.L. A Survey of Parallelism in Numerical Analysys // SIAM Review, 1971. v. № 7. - P. 524-547.

17. Stone H.S. Problems of parallel computation. In: Complexity of Sequent. Paral Numer. Algor. // Ed. T.F. Traub. N.Y.: Acad. Press, 1973. - P. 1-16.

18. Солодовников В. И. Верхние оценки сложности, решения систем линейных уравнений. В кн.: Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР. - Л. - 1982. Т. 118. - С. 159-187.

19. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре // Кибернетика, 1977. № 6. - С. 28-40.

20. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре. II // Кибернетика, 1982. № 3. - С. 18-31.

21. Котов В.Е. О связи алгебраических и архитектурных аспектов параллельных вычислений. В кн.: Вычислительные процессы и системы. Под ред. Г.И. Марчука. - М.: Наука, 1983. - С. 54-80.

22. Миклошко И. Связь между алгоритмами, программами и структурой параллельных ЭВМ. В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под ред. А.П. Ершова. - М.: Наука, 1982. - С. 6-36.

23. Миклошко И. Синтез параллельных алгоритмов. В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под ред. А.П. Ершова. - М.: Наука, 1982. -С. 220-240.

24. Миклошко И. Сложность параллельных алгоритмов. В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем / Под ред. А.П. Ершова. — М.: Наука, 1982. - С. 241-253.

25. Пьявченко О.Н., Сурженко И.Ф., РоммЯ.Е. Метод распараллеливания схемы Горнера и его приложение к цифровым вычислительным устройствам // Автоматика и вычислительная техника, 1978. № 5. -С. 73-78.

26. CsankyL. Fast parallel matrix inversion algorithms // "SIAM Journal on Computers". 1976. - 5, № 4. - P. 618-623.

27. РоммЯ.Е., ШаповалВ.Г. Некоторые алгоритмы организации параллельных вычислений / ТРТН Таганрог, 1982. - 80 с. Деп. в ВИНИТИ 23.02.83, № 970-83.

28. Курош А.Г. Курс высшей алгебры. М.: Наука, 1975. - 431 с.

29. Hart I.E., Cheney E.W., е.а. Computer Approximation, New York, John Willey, 1968.-P. 420.

30. Kogg P., Ston H.S. A parallel algorithm for the efficient solution of a general class of recurrence equation // IEEE Trans. Comput, 1973. v. c., 22. - № 8. -P. 786-790.

31. Heller D:E. On the efficient computation of recurrence relations I I ICASE Rep. NASA Langley Res. Confer. Hampton, Va, Dept. Comput. Sci, Carnegie. Mellon Univ, 1974.

32. Orcutt S.E. Compyter organization and parallel computing. Diss., Dept. Comput. Sci., Stanford Univ, 1974.

33. Orcutt S.E. Parallel Solution methods for triangular linear systems of equations. Stanford Electronics Labs., Stanford, Calif, Tech, Rep, 1974. -№77.

34. Голубков Ю.А.' К правильному выбору алгоритмов, аппроксимации функций для ЭВМ, работающих в реальном масштабе* времени // Электронные вычислительные машины. М.: ИТМ и ВТ АН СССР, 1965. - Вып. 3.-С. 115-154.

35. Лебедев В.Н. Введение в системы программирования. М.: Статистика, 1975.-312 с.

36. Смолов В.Б., БайковВ.Д. Анализ табличных и таблично-алгоритмических методов воспроизведения элементарных функций // Электронное моделирование, 1980. № 1. - С. 22-27.

37. ПалагинЛВ., Иванов В.А., КурчаевА.Ф., Денисенко В.П. Мини-ЭВМ. Принципы построения и проектирования. — Киев: Наукова думка, 1975. -352 с.

38. Хованский А.Н. Приложения цепных дробей и их обобщений к вопросам приближенного анализа. -М.: Гостехиздат, 1956. 203 с.

39. Боднарчук П.И., Скоробогатько В.Я. Успехи и задачи теории цепных и ветвящихся цепных дробей. В кн.: Цепные дроби и их применения. -Киев: ИМ АН УССР, 1976. - С. 5-8.

40. Скоробогатько В.Я. Теория ветвящихся цепных дробей и ее применение в вычислительной математике. М.: Наука, 1983. - 312 с.

41. Березин И.С., Жвдков НГ. Методы вычислений. Т. 1. -М.: Наука, 1970. -464 с.

42. Теслер Г.С. Модификация методов Чебышева и Доморяда построения итераций высших порядков. В кн.: Алгоритмы и программы для

43. Теслер Г.С. Вычисление некоторых элементарных функций на ЦВМ. — В кн.: Математическое обеспечение ЭВМ и эффективная организация вычислительного, процесса. — Киев: ИК АН УССР, 1976. Вып. 2. -С. 91-110.

44. Головкин Б.А. Параллельные вычислительные системы. — М.: Наука, 1980.-520 с.

45. Головкин Б.А. Вычислительные системы с большим числом процессоров. М.: Радио и связь, 1995. - 318 с.

46. Воеводин В.В. Некоторые машинные аспекты распараллеливания вычислений. М.: «Проблемы вычислительной математики» под руководством Г.И. Марчука. Препринт № 22, 1981. - 10 с.

47. Воеводин В.В. Математические проблемы освоения супер-ЭВМ // Вычислительные процессы и системы / Под ред. Г.И. Марчука. М.: Наука, 1985.-С. 3-12.

48. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

49. Воеводин В.В. Просто ли получить обещанный гигафлоп? // Программирование, 1995. № 4. - С. 13-23.

50. Воеводин В.В. Массовый параллелизм и декомпозиция алгоритмов // Вычисл. мат. и мат. физ., 1995. 35, № 6. - С. 988-996.

51. Meggit Т. Psevdo Division and psevdo Multiplication Process. IBM J. Res. and Dev, 1962. - v. 6, № 2. - P. 210-226.

52. Voider Т.Е. The CORDIC Trigonometric Computing Technique. IRE on* el. Comput, 1959. - v.e.c. 8, № 3. - P. 330-334.

53. Писарский A.B., Кургаев А.Ф. Нониусная аппроксимация функций. В кн.: Моделирующие гибридные системы. - Киев: Наукова.думка, 1978. -С. 117-127.

54. Попов Б.А., ТеслерГ.С. Приближение функций для технических приложений. Киев: Наукова думка, 1980. - 352 с.

55. Теслер Г.С. Сегментная аппроксимация функций, основанная на: рекуррентных формулах и разложениях в ряды невязок. — В кн.: Алгоритмы и программы для вычисления функций на ЭЦВМ. — Киев: ИК АН УССР, 1976. Вып. 3. - С. 117-125.

56. БайковВ.Д., СмоловВ.Б., Аппаратная реализация элементарных функций в ЦВМ. JL: Изд-во Ленингр. ун-та, 1975. - 96 с.

57. Оранский A.M. Аппаратные методы в цифровой вычислительной технике. Минск: Изд-во Белорус. Ун-та, 1977. - 208 с.

58. Сергиенко И.В., Теслер Г.С. Методы быстрого деления, основанные на итеративных процессах // Кибернетика, 1974. № 6. - С. 21-25.

59. СмоловВ.Б. Функциональные преобразователи, информации. JL: Энергоиздат, 1981. - 248 с.

60. Голубков Ю.А., Лебедев A.B. Некоторые пути повышения скорости вычисления элементарных функций. В кн.: Электронные вычислительные машины. - М.: ИТМ и ВТ АН СССР, 1962. - Вып. 1. -С. 20-43.

61. Писарский A.B., Кургаев А.Ф. Телескопическая аппроксимация функций // Автоматика, 1978. № 2. - С. 80-84.

62. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. М.: Наука, 1981. — 720 с.

63. Коллатц JL, Крабе В. Теория приближений: Чебышевские приближения и их приложения. М.: Наука, 1978. - 272 с.

64. Barrodate I., Roberts F.D.K., Hunt C.R. Computing best Lp approximation by function non-linear in one parameter. Comput. J., 1970. - 14, № 4. - P. 382386.

65. Dunham C.B. Chebyshev approximation by A +B ln(l+Cx). II. Inst. Math. Appl:, 1972. - 10, № 3. - P. 369-372.

66. Dunham C.B. Chebyshev approximation by A{Bx). ZAMM, 1973. - 53, №6.-P. 353-354.

67. Dunham C.B. Chebyshev approximation by exponential-polynomial product. J. Approxim. Theory, 1975. - 14, № 1. - P. 77-78.

68. Dunham C.B. Approximation by ф(дх) L(Ax) on finite point sets. Ibid., 1977. - 20, №3,-P. 296-301.

69. Meinardus G. Approximation on Functions. Theorie and numerical methods. -Berlin: Springer, 1967. 198 p.

70. Meinardus G., Schwedt D. Nicht-lineare approximation. Arch. Ration. Mech. Und Anal., 1964. 17, № 2. - P. 297-326.

71. Nosenko Yuri L. Approximation of functions by some means of their Fourier series. Facta Univ. Ser. Math. AndTnf. Univ. Nis., 1998. № 13. - P. 73-77.

72. Сердук A.C. Приближение периодических аналитических функций интерполяционными тригонометрическими полиномами в метрическом пространстве L II Укр. мат. ж., 2002. 54, № 5. - С. 692-699.исслед.: 011-8612.

73. Люк Ю. Специальные математические функции и их аппроксимации. — М.: Мир, 1980. -608 с.

74. Оппенгейм А.В., Шафер Р.В. Цифровая обработка сигналов: Пер. с англ. / Под ред. С.Я. Шаца. М.: Связь, 1979. - 416 с.

75. Применение цифровой обработки сигналов // Под ред. Э. Оппенгейма. -М.: Мир, 1980.-398 с.

76. Турулин И.И. Основы теории рекурсивных фильтров с конечной импульсной характеристикой и реализующих их структур / Автореферат диссертации на соискание ученой степени доктора технических наук. -Таганрог: ТРТУ, 2000. 32 с.

77. Цифровая обработка сигналов: практический подход // Э. Айфичер, Б. Джервис. 2-е изд. - М.: Вильяме, 2004. - 989 с.

78. Рабинер Л., Гоулд М. Теоретические основы цифровой обработки сигналов. М.: Мир, 1978. - 848 с.

79. Barlow J.S. and RemondA. Eye movement artifact nulling in EEGs by multichannel on-line EOG subtrractio. // Electroencephalography and Clinical Neurophysiology, 1981. 52. - P. 418-423.

80. Bierman G.J. Measurement updating using the U-D factorization. Automatica, 1976.- 12.-P. 375-382.

81. Ifeachor E.C. A Practical Guide for MATLAB and С Language Implementations of DSP Algorithms. Harlow: Person Education, 2001.

82. Залманзон JI.A. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука. Гл. ред. физ.-мат. лит, 1989. - 496 с. - ISBN 5-02-014094-5.

83. Ромм Я.Б., Фирсова С.А. Устойчивое распараллеливаемое вычисление функций на основе таблично-алгоритмической аппроксимации с приложениями в численном анализе. Таганрог: Изд-во ТРТУ, 1999. — 86 с.

84. РоммЯ.Е., Аксайская JI.H Схема кусочно-полиномиальной аппроксимации с минимальной временной сложностью на основе интерполяционного полинома Ньютона / ТГПИ. Таганрог, 2007. - 17 с. Деп. в ВИНИТИ 12.02.2007, № 12Г-В2007.

85. Пулькин С.П., Никольская JI.H., Дъячков-А.С. Вычислительнаяматематика. -М.: Просвещение, 1980. 176 с.

86. Бахвалов Н.С. Численные методы. Т. 1. М.: Наука, 1973. - 632 с.

87. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука, 1987.-600 с.

88. Фаронов B.B. Delfi. Программирование на языке высокого уровня. -СПб.: Питер, 2004. 640 с.