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

Очевидно, что поскольку в каждый момент времени на выходе радиопередающей части Уз-СПИ присутствуют все 2N отсчетов полезного сигнала, то не представляется возможным дешифровать передаваемое сообщение, если не иметь информации на радиоприемной стороне о виде используемых при формировании пар ДКП.

Поскольку количество таких пар равно величине 0,5N для каждого из способов формирования символических равенств [3, 4], общее количество которых равно восьми, то, следовательно, использование описанного подхода позволяет существенно повысить криптостойкость передаваемых сообщений, поскольку информация о виде используемой кодирующей последовательности доступна только на приемной стороне. Нетрудно показать, что общее количество возможных ком-

2

бинаций при использовании только бинарных последовательностей достигает величины 4 N 2.

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

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

Это позволяет одновременно передавать с высокой степенью криптостойкости несколько сообщений по одному каналу радиосвязи, имеющих различные характеристики, что приводит к повышению криптостойкости всей УзСПИ.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Кук Ч., Бернфельд М. Радиолокационные сигналы: Теория и применение: пер. с англ. / под ред. В.С. Кельзона. М.: Сов. радио, 1971. 568 с.

2. Варакин Л.Е. Теория систем сигналов. М.: Сов. радио, 1978. 340 с.

3. Литюк В.И., Литюк Л.В. Методы цифровой многопроцессорной обработки ансамблей радиосигналов. М.: СОЛОН-ПРЕСС, 2007. 592 с.

4. Литюк В.И., Литюк Л.В. Введение в основы теории математического синтеза ансамблей сложных сигналов: учеб. пособие. Таганрог: Изд-во ТРТУ, 2006. 80 с.

5. Литюк В.И. Особенности применения сложных сигналов в узкополосных системах радиосвязи // Известия ВУЗов России «Электромеханика». Специальный выпуск «Радиоэлектронные устройства и системы». 2005. С. 43-48.

6. Радиоприемные устройства / под ред. А.П. Жуковского. М.: Высшая школа, 1989. 342 с.

7. Буга Н.Н., Фалько А.И., Чистяков Н.И. Радиоприемные устройства. М.: Радио и связь, 1986. 320 с.

Я.Е. Ромм, Л.Н. Аксайская

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

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

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

>> = /С хе\,Ъ\

где промежуток |г3 Ь произвольно фиксирован. Выбирается система непересекающихся подынтервалов, покрывающая |г, Ъ :

- P_1

U 1.^.41 > x1+i-Xl = ii-a2P, i = 0,\,...,P-\

Для априори заданной границы S погрешности аппроксимации функции (1) и для каждого отдельно взятого подынтервала из (2) строится полином Ньютона степени n , где n выбирается минимальным для достижения заданной точности приближения одновременно на всех подынтервалах. При этом полином Ньютона в общем случае преобразуется по дистрибутивности с приведением подобных так, что в результате на i -м подынтервале принимает канонический вид:

Р„4Уа0г/+а1г/Х + а2г/х2+- + апг/Х" * £ , *i+1 ^ И = COÜSt , /=0,1.....Р -1 <3>

где i - номер подынтервала, f соответствует аппроксимируемой функции. Построение (3) выполняется для всех P подынтервалов, чтобы на каждом из них не превышалась заданная граница погрешности

Ixel,xMl i = 0,\,...,P-\ W

В (3), (4) значение n выбирается одинаковым для всех подынтервалов. Если функция известна и для нее n найдено, то для каждого подынтервала из (2) набор коэффициентов из (3) можно записать в память компьютера и сделать хранимым. Для вычисления функции дешифруется номер / , который служит адресом выборки коэффициентов (3). Если х е [х(, Л"(+|). то

• • (х-аЛ . тт

l = int - , где int - целая часть числа, а из (1), Н =хг + 1-хг-. Время дешифрации

V Н

t = О ^ , сложность дальнейшего вычисления функции зависит от степени полинома (3), по схеме Горнера его значение вычисляется за время t = П у + I где lc. ty - время бинарного сложения и умножения соответственно. За счет уменьшения длины подынтервала степень n в (3) можно сделать «сколь угодно» малой при соответственном возрастании P в (2). Соответственно n время вычисления функции оказывается минимальным. Для осуществления данного построения вычисление коэффициентов начинается с П — 1 при минимальном Р . В случае невозможности достижения точности (4) значение P удваивается; это продолжается до нарушения границ P ; при их нарушении снова делается переход к минимальному Р , но уже при П — 2, и т.д. В рамках интерполяции по Ньютону схема минимизации степени полинома детализируется следующим образом. Если границы i -го подынтервала из (2) обозначить аг 0, bi0, шаг интерполяции

bi0~ai0 . „ 1 1 т-г

II'( =-, то узлы записываются в виде Л"; = aj0 + jwi , j = U, I, ..., n — v. Полином

п

Ньютона степени n на i -м подынтервале для функции (1) примет вид [2]:

j=1 J ! 0

= 0

где Л'_>'(П - конечная разность / -го порядка в точке хг0 , t =

х-х.

. Процесс приведения (5) к

виду, аналогичному (3), влечет = _/(хг0), — ^ ^¿у^у > ГДе =

АЧ

7!

ач -

коэффициенты полиномов вида Рп б/(|; + (11. t + (12.12 +... + с!п /1 " с натуральными

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

вычисление

р X

П] ^ -

Результаты программной реализации схемы даны в таблице. Во входном столбце таблицы £ обозначает априори задаваемую границу погрешности. Во входной строке к задает показатель степени Р = 24 для количества подынтервалов из (2). На пересечении строки, содержащей £, и

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

Таблица 1

Степени интерполяционного полинома Ньютона, аппроксимирующего функцию у = 1а/'С/^1 е

по таблично-алгоритмической схеме

х«

]/2,\

к

10-'

10-5

10-6

10-

10

10

10

-ТО"

10

-п~

10

-12"

10

-13"

10

-14"

10

-13"

10

-15"

10

-17"

10

-18"

10

11

11

12

11

12

12

10

10

10

11

12

13

14

15

16

17

0

1

2

3

4

5

6

7

8

9

2

2

1

1

1

1

1

1

1

4

3

2

2

1

1

1

1

1

6

5

3

2

2

2

1

1

1

8

6

4

3

3

2

2

1

1

7

5

4

3

2

2

2

2

8

6

5

4

3

3

2

2

2

2

9

7

6

4

4

3

3

2

2

2

2

8

6

5

4

3

3

3

2

2

2

2

2

9

7

5

5

4

4

3

3

2

2

2

2

2

2

9

8

6

5

4

4

4

3

3

2

2

2

2

2

2

8

7

6

5

4

4

3

3

3

3

2

2

2

2

2

9

7

6

5

5

4

4

3

3

3

2

2

2

2

2

8

7

6

5

4

4

3

3

3

3

3

2

2

2

9

7

6

6

5

4

4

3

3

3

3

2

2

2

8

7

6

5

5

4

4

3

3

3

3

3

2

Из таблицы видно, что аппроксимация функции у

)1

агсЩ

V

интерполя-

ционным полиномом Ньютона, например, второй степени обеспечивает точность порядка 10

-18

Формула (5) для каждого j — 1, 2, ... , П включает разложение полинома по целым

корням Р - , = | J (j — к). корни и, соответственно, коэффициенты которого не зависят от

Ы 0

вида интерполируемой функции и номера подынтервала. Коэффициенты данного полинома (с помощью матричного видоизменения [3] формул Виета) можно вычислить наперед для произвольно фиксированного j , считать хранимыми в памяти компьютера и заданными без вычисления. Отсюда для параллельного перевода всего интерполяционного полинома Ньютона nj ^

в форму (3) достаточно вычислить конечные разности А1 yi0 по максимально параллельной

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

А->,„ =Уи - />«»-.) + /( /2~]) У,и-» - J(J ~ 3|(7 ~ 2) У,и-» +-+Н»о. при этом все биномиальные коэффициенты Cj имеют априори известные значения. Достаточно параллельно умножить эти значения на узловые значения функции yi i}_ ,), затем выполнить алгебраическое сложение по схеме сдваивания. Временная сложность этой операции составит / (/") = t + |log 2 j tс, а количество процессоров Г = j . Факториалы в знаменателях слагаемых выражения полинома ^ можно считать априори присоединенными к биномиальным коэффициентам. Остается вычисленные значения коэффициентов параллельно умножить на хранимые коэффициенты полиномов Р { и привести подобные при равных степенях. Временная

сложность описанного параллельного алгоритма составит Т ^ j= /у + | log 2 п t с на одном подынтервале, R - количество процессоров, в данном случае R — fl (п — 1) / 2 . При параллель: одновременно по всем Р подынтервалам Т ^п 2 /2 = / + [log 2II tс.

ном вычислении одновременно по всем ^ иидшш^вшш.. ^ >,, , ^ , г , 2,

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

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

При интерполяции по Ньютону /(х)«ХИП1.(7), где ^„¿(0 из (6). Отсюда

Х~Хг0

/X*) *%,(?): При t =-!- получится /'(^(^(ОУЛ- Очевидно,

wi

QVm (0)'t = auf + 2 a2lft + 3 a3lft2 +... + П anift^l), где /', = — . Значение Ч"йг (t) вычисля-

W-

ется по схеме Горнера, на основании которой

ЛЛ Л ~> 1

/'(*) « f- • %anift + (n-1 )ain_1)if J + -- + 2a (n_2)if J + ax if -

w.

Существенно, что функция и производная могут вычисляться одновременно. Для наперед известной функции, например при построении библиотеки стандартных подпрограмм, коэффициенты аппроксимирующего полинома могут быть хранимыми для каждого подынтервала. В этом случае производная будет вычисляться за время нескольких сложений и умножений, поэтому временная сложность вычисления стандартной функции и одновременно производной от нее оценивается как Т = 0{ 1).

Вычисление интеграла от функции (1) на промежутке [а, Ь] по аддитивности влечет

Ь р-1 хм

и о X = ^ ]"/(х)й?х, где [х,Х+| ) из (2). Для / -го подынтервала справедливо

а 2=1 щ

Х7+1 Х7+1

/(х) « РП1 (х), где Рп г (х) из (5) удовлетворяет (4). Отсюда | /'(х)б/х « (х) с/х. В свою

хг хг

Ь р-1 хш

очередь, | / с1 X ~ ^ (х)с/х. Для интерполяции по Ньютону используется замена пе-

а '=1 х1

Ь'0~а,о „ , -

ременной II'( =-. При ее выполнении значениям X — х{ и X — хм соответствуют 1 — 0

П

и г = п. С учетом Рп г С У, г < где Ч^ г < из (5), получится Рп г (х) сЬс - и'^ (V) Ж. В

П П

ТГ 1 Т Г / И

где

результате \РпХх)Ох = wi Л . Имеем: и*, (1)сН = и*, ^(и+1)г(0

щ О О

*~Р, „ ,, = С Л--Л——л———. Для минимальной степени П интер-

(й+1)г 12 3 п + 1

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

п Ь р—\

¡ЧщфЖ^^^п+ъМ  в результате }/ ^ ^«^^(^„¡(я), где ¥(я+1)»

О а 2=1

вычисляются по схеме Горнера:

VI/

х (и + 1)г

( г с „ \ \ \

, а(п-2)2 / , , а0г/

п + ——— пл— +

Диг/ а(п-\)гГ

-п + -

п + 1 п

п-1

1

и.

V ЧЧ" / у у

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

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

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

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

X

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

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

Временная сложность максимально параллельного вычисления конечного множества функций по схеме с динамическим распараллеливанием сохраняет оценку T(R) = 0(1) , где R зависит от максимального количества одновременно готовых аргументов. По величине порядка оценка не изменится, если в схему максимально параллельного вычисления функций дополнительно включить ярус аналогичного вычисления производных и определенных интегралов.

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

1. Аксайская Л.Н. Разработка и исследование параллельных схем цифровой обработки сигналов на основе минимизации временной сложности вычисления функций: автореф. дис. ... тех. наук. Таганрог: Изд-во ЮФУ, 2008. 20 с.

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

3. Ромм Я.Е. Параллельные итерационные схемы линейной алгебры с приложением к анализу устойчивости решений систем линейных дифференциальных уравнений // Кибернетика и системный анализ. Киев, 2004. № 4. С. 119-142.

4. Ромм Я.Е., Аксайская Л.Н. Кусочно-полиномиальная аппроксимация функций на основе интерполяции по Ньютону в приложении к параллельной цифровой обработке сигналов // Вопросы современной науки и практики. Университет им. В.И. Вернадского. Серия «Технические науки», 2007. Т. 2. С. 107-118.

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

Исходные соотношения преобразования Уолша и определения. Функции Уолша представляют собой полную систему ортонормированных прямоугольных функций. Для нормированных функций Уолша принято обозначение 0 , где V - номер функции, а в находится в полуинтервале 0 < 0 < 1. Обычно рассматривается множество функций Уолша Ч'С{1 О при

БИБЛИОГРАФИЧЕСКИМ СПИСОК

Я.Е. Ромм, В.В. Забеглов

ПАРАЛЛЕЛЬНОЕ ПРЕОБРАЗОВАНИЕ УОЛША

j 1