close

Вход

Забыли?

вход по аккаунту

?

Параллельное выполнение основных дискретных ортогональных преобразований.

код для вставкиСкачать
Вестник ТГПИ
Естественные науки
влечет следующие значения нулей (код программы полностью дан в [2]):
Действительные части нулей
Мнимые части нулей
Значения функции
-4.58445604293577511E+0000
-2.80568528774483195E+0000
-1.03656895433724402E+0002
-1.66591190983139839E+0002
4.70946395391531174E-0009
-5.27266666666666667E+0000
-5.27266666666666667E+0000
-2.45930000000000000E+0001
-2.45930000000000000E+0001
-3.65508747547457647E-0026
-2.70958460951182288E-0029
-2.88552909746462807E-0028
-1.75654297877690656E-0023
-1.08753776697701395E-0034
2.29837333333333333E+0002
-2.29837333333333333E+0002
3.46355333333333333E+0002
-3.46355333333333333E+0002
4.86070674693958763E+0038
3.87688758647364437E+0036
5.78024178051377293E+0038
3.64364867607685689E+0035
4.48680606796407673E+0036
5.25425580557896453E+0035
4.57676705867643764E+0033
5.04576930357129645E+0036
3.84764390362970963E+0038
Среди нулей есть значение с нулевой действительной частью. Чтобы удостовериться, что
нулевая действительная часть не является результатом погрешности данный нуль можно найти с
помощью программы поиска действительных нулей [2], поскольку мнимая часть с высокой точностью приближения является нулевой. Получим: 4.70946395391531182E-0009.
Тем самым наличие нулевой действительной части подтверждено с достаточной степенью
достоверности. Следовательно, система устойчива относительно состояния равновесия, при этом
она не обладает асимптотической устойчивостью.
Следует отметить, что исследования проводились в среде Delphi 7 на персональном компьютере класса Pentium 4, при этом время программного анализа устойчивости для второго случая
составило 9 секунд.
Необходимо подчеркнуть, что приведенный анализ выполнен способом, принципиально отличающимся от способа компьютерного анализа устойчивости, который применялся в [1].
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Буланов С.Г. Разработка и исследование методов программного моделирования устойчивости систем линейных дифференциальных уравнений на основе матричных мультипликативных преобразований разностных схем: автореф. дис. … канд. техн. наук. Таганрог: ТРТУ. 20 с.
2. Веселая А.А. Вычисление нулей и экстремумов функций при вариации параметров на основе сортировки с
приложением к моделированию устойчивости систем линейных дифференциальных уравнений: автореф.
дис. … канд. техн. наук. Таганрог: ТРТУ, 2010. 17 с.
3. Гантмахер Ф.Р. Теория матриц. 5-е изд. М.: Физматлит, 2004. 560 с.
4. Гоноровский И.С. Радиотехнические цепи и сигналы. М.: Радио и связь, 1986. 408 c.
5. Демидович Б.П. Лекции по математической теории устойчивости. М.: Наука, 1967. 472 с.
6. Ромм Я.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. II // Кибернетика и системный анализ. 2001. № 5. С. 81-101.
7. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений // Теория сложности
вычислений. I: Записки научных семинаров ЛОМИ АН СССР. Л., 1982. Т. 118. С. 159-187.
8. Филлипс Ч., Харбор Р. Системы управления с обратной связью. М.: Лаборатория Базовых Знаний, 2001.
615 с.
Я.Е. Ромм, В.В. Забеглов
ПАРАЛЛЕЛЬНОЕ ВЫПОЛНЕНИЕ ОСНОВНЫХ
ДИСКРЕТНЫХ ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ
Введение. В настоящее время интенсивно развиваются исследования в области ортогональных преобразований (ОП) для цифровой обработки сигналов (ЦОС). ОП используются для
обработки сигналов, представляющих сейсмические, акустические, биомедицинские данные, а
также данные обработки изображений, речевых сигналов, анализа и проектирования систем связи
и др. К наиболее часто применяемым относятся преобразования Фурье, Хаара, Уолша, а также
138
Раздел IV
Информатика
вейвлет- и пилообразное преобразования. При этом актуальны задачи сокращения времени и объѐма вычислений в процессе выполнения преобразований. В этом аспекте ниже излагаются параллельные схемы ортогональных преобразований с минимизированной временной сложностью.
Параллельные схемы пилообразного преобразования. Пилообразное преобразование записывается в виде
(1)
DN S N X N ,
где D N
– вектор коэффициентов, X N
D 0 , D 1 , ... , D N 1
–
X 0 , X 1 , ... , X N 1
вектор входной последовательности, S N – матрица, N N , которая задаѐтся рекуррентной формулой
1
an
2
I
0
bn
1
0
an bn
0
0
1
bn an
0
0
0
1
SN
0
bn
N 2
1
an
2
0
0
I
N 2
2
0
I
N 2
SN 2
0
2
0
I
N 2
0
SN
1 1
2 1
, S2
2
1
,
1
2
где I m – единичная квадратная клетка, m m , n log2 N . Постоянные a k
(2)
и b k вычисляются по
формулам:
a1
1
1 , bk
, ak
1 4 a k2
1, 2,  , log2 N
2bk a k 1 , k
(3)
1
или
2k
ak
1
, bk
22k
ak
2a k
2
1
, k 1, 2, ... , log2 N .
(4)
2
1
4 2k 1
1
1
2
1
3
Предлагаются две схемы параллельного вычисления пилообразного преобразования [3],
включая вычисление матрицы преобразования.
Первая схема строится с помощью алгоритма Стоуна. Из (3) исключается b k и производятa k2 , d k
ся последовательные замены c k
qk
qk
1
5
1
4
0
qk
1
qk
2
, q0
1 , q1
2k
1 4ck , qk
1.
d k qk
Соотношение (3) принимает вид
5 . В силу рекуррентности
qn
qn 1
5
1
4
0
n 1
q1
.
q0
i
Схема вычисления строится следующим образом. Сначала находятся все двоичные степени A 2 ,
i 1, 2,  , 2 i
n 1, A
5
1
4
0
,–
A2
0
A,  , A 2
– наибольшее целое, не превосходящее
A2
i 1
2
, i 1, 2,  , log2 n 1 , где
. Пусть
log 2 n 1

i
i
2i ,
i 0
0
i
1
,  1, 2,  , n 1 .
(5)
Каждому  из (5) сопоставляется процессор с номером  . Процессоры параллельно найдут
все степени матрицы с показателем  . При этом  -й процессор перемножает те и только те двоичные степени матрицы, перед показателем 2 i которой в (5)
схемы составит T log2 N 2
O log2 log2 N 2
i
1 . Временная сложность данной
. Согласно (4) по заданному номеру вычис-
ляются коэффициенты для соотношения (2) и формируется матрица преобразования. Во второй
схеме коэффициенты вычисляются из (4) на основе кусочно-полиномиальной аппроксимации с
временной сложностью O 1 .
139
Вестник ТГПИ
Естественные науки
С целью параллельного формирования матрицы преобразования все значения (3 – 4) вычисляются априори и хранятся в памяти компьютера. По рекуррентности S N из (2) представляется в
виде
SN
1
N
PN 2
0
PN
P4
0
0
0
0
0
PN
2
0 0 0
P4 0 0
0  0
0 0 P4
0 0 0
0
0
0
0
P4
S2
0
0
0
0
0 0 0
S2 0 0
0  0
0 0 S2
0 0 0
0
0
0 ,
0
S2
(6)
где PN – левая матрица в правой части (2). Произведение (6) с учетом внутренней клеточной
структуры вычисляется на N 3 2 процессорах по схеме сдваивания за время O log2 log2 N .
С другой стороны, элементы матрицы S N можно вычислить априори и хранить в памяти,
затем считывать их с временной сложностью T N 2
O 1 . В максимально параллельной форме
собственно само преобразование (1) выполнимо с помощью схемы сдваивания парных произведений с временной сложностью T N 2
O log2 N .
Еще один параллельный алгоритм преобразования (1) с помощью (6) записывается в виде
D0
X 0

DN 1
SN

,
X N 1
(7)
где S N из (6). Умножения матриц в (7) выполняется последовательно справа налево. Каждое умножение выполняется параллельно по схеме сдваивания за время t y
2 t c , где t y – время умно-
жения, t c – время сложения, т.е. за время O 1 , результатом каждого умножения является матрица-столбец, которая в свою очередь умножается на следующую матрицу, время выполнения
T 5N 2 O log2 N . Имеет место
Теорема 1. Пилообразное преобразование, ограниченное N членами, в условиях первой
схемы можно выполнить с временной сложностью T N 2
O log2 N
O log2 log2 N , в усло-
виях второй схемы данное преобразование выполняется с оценкой T 5N 2
O log2 N .
В итоге, пилообразное преобразование вычисляется в максимально параллельной форме,
число процессоров в одних случаях линейно, в других квадратично зависит от числа отсчѐтов, –
схемы разнятся по составу операций, их минимальная временная сложность O log 2 N .
Схемы параллельного вычисления функций Радемахера. Функции Радемахера определяются следующим соотношением [5]
sign sin 2 j
rad j,
,
0, 1 , j 1, 2, ... , log2 N ,
(8)
с их помощью в дальнейшем вычисляется преобразование Уолша. Первая схема основана на кусочно-полиномиальной аппроксимации, согласно которой значения функций
sin 2 j
i
0, 1 ,
i
i 1
вычисляются с временной сложностью T N log2 N
1N, i
i
0, 1, ... , N 1 ,
(9)
O 1 . Функции (9) и (8) можно также вы-
числить с помощью полиномов Чебышева I и II рода T x и U  x на основе рекуррентных
соотношений:
T
1
T0 xi
xi
2 xi T xi
1, T1 xi
T
xi
1
xi
,
U
1
xi
U 0 xi
2 xi U  xi
1, U1 xi
U
2 xi
1
xi
,
Зависимости (10) представляются в матричной форме
T 1 xi
T xi
2 xi
1
1
0
T xi
T 1 xi
с теми же начальными значениями, отсюда
140
,
U  1 xi
U  xi
2 xi
1
1
0
U  xi
U  1 xi
,  1, 2, ... ,
(10)
Раздел IV
Информатика
T 1 xi
T xi
2 xi
1
2 xi
1
По схеме Стоуна
1
1
0

T1 xi
T0 xi
0
,
U  1 xi
U  xi
2 xi
1
1
0
1  1 cos
i
cos 2
U 2
i

1 T2 sin
i
1
.
для всех значений  ,  1, 2, ... , N , вычисляются на O N 2
sin
cos 2 1
,
i
, функции sin 
i
U1 xi
U 0 xi

процессорах за время O log2 N . Используя соотношения sin 2 1
sin 2

i
i
1  cos
i
1  T2
i
sin
i
,
U 2 sin
i
,
1
,  1, 2, ..., N , можно выразить из (10). Отсюда
с учетом (8), (9) вычисляется система функций Радемахера.
Временная сложность второй схемы O log2 N , в отличие от первой она не требует затрат
постоянной памяти.
Третья схема параллельного вычисления функций Радемахера строится на основе соотношения rad j,
1
i
int 2
сложностью T N log2 N
j
,
i
i
0, 1 ,
0, 1, ... , N 1 , с временной
j 1, 2, ... , log2 N , i
O 1 .
Алгоритмы параллельного выполнения преобразования Уолша. По значениям функций
Радемахера (8) в точках
по правилу [5]
i 0, 1, ... , N 1 ,
i
i 1 1 N ,
i,
log 2 N
wal r,
rad j,
r
log2 N
r
j 1
log2 N
j
, где r j – j -й разряд представления числа r в двоич-
j 1
ной системе счисления,
– символ поразрядного суммирования по модулю 2 , вычисляются
функции Уолша. Каждой такой функции с номером r , r 0, 1, ... , N 1 , ставится в соответствие
N log 2 N процессоров, чтобы произведение при каждом
на int
1
log 2 N
2
i
вычислялось по схеме сдваивания
процессорах. Процессоры, работая параллельно по всем r и i , перемножат
функции Радемахера за время T N 2 log 2 N
O log2 log2 N .
Последняя оценка может быть улучшена до O 1
с сокращением числа процессоров в
O log2 N , если применить битовый счѐтчик числа отрицательных двоичных единиц. Еще одна
параллельная схема получится, если матрицу преобразования Уолша H w N
вычислять поэле-
ментно. Пусть ri и vi цифры i -го разряда в двоичном представлении чисел r и v соответственно: r
r log 2 N
1
r log 2 N
2
... r1 r0
2
, v
v log 2 N
1
v log 2 N
2
... v1 v0
2.
)
Элементы h (w
rv
матрицы
H w N имеют вид
log2 N 1
u i r vi
h (rwv)
u0 r
rlog 2 N 1 , u1 r
rlog 2 N
1
1
i 0
rlog 2 N
; r
2,
u2 r
0, 1, ... , N 1 , v 0, 1, ... , N 1 ,
rlog 2 N
2
rlog 2 N
3,
… , u log 2 N
(11)
1
r
r1
r0 .
Все элементы (11) вычисляются параллельно, при этом суммы в показателях степени вычисляются по схемам сдваивания. Временная сложность данного варианта составит
T N 2 log 2 N
O log2 log2 N .
После вычисления всех элементов матрицы H w N вычисляется собственно само преобразование B N
1 N Hw N
X N . Схема основана на естественном параллелизме, с учетом ло-
гарифмической оценки умножения матрицы на вектор временная сложность схемы составит
T N 2 log2 N
O log2 log2 N . Таким образом, имеет место
141
Вестник ТГПИ
Естественные науки
Теорема 2. Преобразование Уолша, ограниченное N членами, можно выполнить параллельно с временной сложностью T N 2 log2 N
O log2 N , при этом матрицу преобразования
H w N можно параллельно вычислить с оценкой T N 2 log2 N
O log2 log2 N .
В случае фиксированного N при каждом значении i в показателе степени (11) априори известны номер строки ri и номер столбца vi матрицы H w N , поэтому априори можно вычислить
их двоичное разложение, парные произведения ui r vi , а также сумму, задающую показатель.
)
Отсюда все элементы h (w
r v можно найти априори и записать в память компьютера. В этом случае
время определения матрицы O 1 . Для переменного N оценки O 1 можно достигнуть на той
же основе, применив счѐтчик одноразрядных единиц.
Схемы параллельного вычисления быстрого вейвлет-преобразования (БВП). БВП позволяет вычислять коэффициенты вейвлет-разложения с помощью алгебраических операций на
основе свѐртки по рекуррентным соотношениям [7]:
aj
2
1,k
hn a j ,n
, dj
2k
2
1,k
n
g n a j ,n
2k
,
(12)
n
где hn – масштабирующий фильтр масштабирующей функции, g n – фильтр вейвлета; a j ,k –
начальные коэффициенты разложения функции f x для некоторого уровня разрешения j , которые предполагаются известными. Рассматриваются вейвлеты Добеши, в которых масштабирующий фильтр hn и фильтр вейвлетов g n состоят из конечного числа ненулевых элементов.
Формулы вычисления коэффициентов (12), зафиксировав конкретное разрешение j
j0 , можно
представить в матричной форме. Первый шаг БВП:
a j0
1,1
a j0
1, 2

a
j0 1,
N
2
d j0 1,1
d j0 1,2

d
N
j0 1,
2
h1
0
h2
0
h3
h1
h4
h2

h3
hL
h4
0 0
 hL
 
0 
0
0
a j0 ,1
0
0
a j0 ,2









  

h h4  hL 0   0 0 0 h1 h2
2 3
g1 g 2 g 3 g 4  g L 0 0   0 0
0 0 g1 g 2 g 3 g 4  g L 0  0 0








  

g 3 g 4  g L 0   0 0 0 g1 g 2



N
a
a
a
j0 ,
N
2
j0 ,
N
1
2
j0 ,
N
2
2
,
(13)

a j0 , N
где N – целая степень по основанию два. В (13) матрица фильтров (МФ) имеет размерность
N
N . На втором шаге БВП преобразованию подлежат элементы a j0
1, i
, i 1, 2, ... , N 2 , и МФ
имеет порядок N 2 N 2 , в остальном всѐ строится по схеме первого шага. Полное БВП заключается в вычислении наборов коэффициентов d
a j0
 1, k
j0 , k
, которые итеративно определяются через
, пока размерность МФ будет не меньше длины фильтра, т.е. N 2 
L.
Предложенная модификация БВП представляется в виде
Al0
Dl 0

D2
D1
M l0
0
22
0
1
0
0
1

0
M2
0
0
1
...
0
0
M1 0
0
1
M0
A0 ,
(14)
1
0
1
0
1

P
где
A0 – вектор-столбец входной последовательности, A 0 , Dk , k 1, 2, ... ,  0 – серии вейвлет-
коэффициентов, клетка M  имеет размерность N 2 
142
N 2  ,  0, 1, ... ,  0 1 , и является матри-
Раздел IV
Информатика
цей фильтров для конкретного разрешения j0
A0 , имеют размерность N
 , все перемножаемые матрицы из (14), кроме
N . Первый алгоритм выполнения БВП строится следующим обра-
зом. Сначала вычисляется матрица преобразования, обозначаемая P , т.е. произведение матриц,
содержащих клетки M  , из правой части (14). Умножение производится с помощью схемы сдваивания
T N
с
3
учетом
клеточной
Временная
сложность
схемы
составит
log2 N . Затем на основе схемы сдваивания вычисляются наборы вейв-
O log2 log2 N
лет-коэффициентов
структуры.
P
с временной сложностью T N 2
A0
O log2 N . Второй алгоритм
заключается в последовательном умножении справа налево матриц из (14), при этом каждое умножение выполняется в параллельной форме. Временная сложность схемы составит
T L N
O log2 N , где L – длина вейвлет-фильтра. Таким образом, для второго алгоритма
имеет место
Теорема 3. Вейвлет-преобразование, где вейвлеты Добеши заданы парой фильтров hn и
gn ,
0
n 1, 2, ... , L , для коэффициентов
a
j 0 ,k
k 1, 2, ... , N , глубины разложения
,
0,
log 2 N , может быть параллельно вычислено с временной сложностью O log 2 N .
Схемы параллельного преобразования Хаара. С помощью схем на основе (14) можно
вычислить преобразование Хаара. Масштабирующий фильтр для матрицы Хаара состоит из двух
ненулевых элементов h 1 1
2 , h2
2 , фильтр вейвлетов – g 1 1
1
1 N H* N
гаемая схема вычисления Y N
H * N . Предполагается, что все степени 2 j
и
1
2 . Предла-
включает алгоритм построения матрицы
X N
2
2 , g2
2j
2
при 0
j log2 N вычислены априори и
записаны в память компьютера. Первая строка матрицы заполняется единицами. Далее, каждому
ненулевому элементу матрицы ставится в соответствие процессор, который считывает этот элемент из памяти. Элементом матрицы с индексами
1 k 2m
j 1
будет значение 2 j 2 , при 1 n 2 j , 2 m
j 1
2j
n, 2 m
1 k 2m
j
j
n 1
k
, – значение
при 1 n 2 j ,
2 j 2 , все ос-
тальные элементы – нули. Количество процессоров равно числу ненулевых элементов. Первая
строка матрицы состоит из единиц, последовательно сверху вниз располагаются прямоугольные
клетки с номерами j , j
0, 1, ... , log2 N , размерность j -й из которых 2 j
N , причем ненулевые
элементы в такой клетке располагаются ступенчато так, что их число всегда равно числу столбцов
N . Умножением на число клеток с учетом первой строки получится число ненулевых элементов
матрицы, которое равно N log2 N 1 . Данный способ заполнения матрицы имеет временную
сложность T R
O 1 , R
N log2 N 1 . Само преобразование вычисляется с той специфи-
кой, что при умножении строки на столбец множитель выносится за скобки, по схеме сдваивания
выполняется алгебраическое сложение в скобках, затем – одно бинарное умножение. Вместо процессоров для данной операции целесообразно взять один умножитель и соответственное число
сумматоров. В результате число умножителей равно числу строк матрицы без одной, а количество
N
сумматоров по строкам меняется с учетом схемы сдваивания как
в первой строке и, далее, как
2
1 N
без изменения внутри клетки с 2 j строками, где j 0, 1, ... , log2 N 1 . Отсюда число
2 2j
сумматоров равно
N
2
1
2
log 2 N 1
2
j
0
j
N
2
j
N
1 log2 N .
2
Теорема 4. Преобразование Хаара, ограниченное N членами, можно выполнить параллельно с временной сложностью T R O log 2 N , где количество процессоров R N log 2 N 1
требуется при параллельном считывании из памяти всех элементов матрицы преобразования за
время O 1 .
143
Вестник ТГПИ
Естественные науки
Без учета произведений, в которые входят нули, потребуется N
элементов, временная сложность схемы составит T N log2 N
log2 N 1 процессорных
O log2 N .
Предложенные видоизменения преобразований Уолша, Хаара, а также БВП на основе вейвлетов Добеши согласно утверждениям теорем 2 – 4 инвариантны относительно N , поэтому применимы при динамическом изменении отсчетов.
Схема параллельного вычисления ДПФ включает параллельный алгоритм вычисления
базиса с произвольно заданным числом элементов. Базис ДПФ вычисляется следующим образом.
Выбирается система непересекающихся подынтервалов равной длины:
P 2

0, 1
xi, xi
1

x P 1, x P , x i
xi
1
0, 1, , P 1 .
1 P, i
(15)
i 0
При априори заданной границе
абсолютной погрешности аппроксимации с помощью кусочно-полиномиальной схемы вычисляется тригонометрическая функция
(16)
f x sin x , x 0, 1 .
С этой целью для каждого отдельно взятого подынтервала из (15) строится интерполяционный полином Ньютона степени n , где n выбирается минимальным для достижения заданной
точности приближения одновременно на всех подынтервалах. Полином Ньютона преобразуется
путем приведения подобных так, что на i -м подынтервале принимает канонический вид:
Pn x
a 1i x a 2 i x 2 ... a n i x n , x
a 0i
xi , xi
1
,i
0, 1, , P 1 ,
(17)
Построение (17) выполняется для всех подынтервалов при условии
sin
x
Pn x
, x
xi , xi
1
, i
0, 1, , P 1 .
(18)
В (17) n выбирается минимально возможным, одинаковым для всех подынтервалов. При
таком n для функции (16) и для каждого подынтервала из (15) набор коэффициентов (17) записывается в память компьютера и хранится в ней. Для вычисления функции дешифруется номер подынтервала i , его значение служит адресом выборки коэффициентов (17). Если x xi , xi 1 , то
i
int x H , где H
xi
1
xi , int – целая часть числа. Порядок времени дешифрации оценива-
ется как единичный. Если для рассматриваемой функции вычислить и хранить коэффициенты для
всех 2k подынтервалов, то в дальнейшем время вычисления функции зависит только от степени
полинома (17). По схеме Горнера значение этого полинома вычисляется за время
t 1 n t y tc , где t y , tc – время бинарного умножения и сложения соответственно. Поскольку
n const , то временная сложность вычисления функции (16) при любом выборе аргумента соста-
вит t 1
O 1 .
Выбирается и фиксируется количество отсчетов N в ДПФ, для определѐнности предполагается, что N – целая степень двойки. По схеме кусочно-полиномиальной аппроксимации вычисляются значения (16) в точках x j
2 j N , j 0, 1, ... , N 2 1 . Каждой точке x j с номером j
ставится в соответствие процессор с таким же номером. Процессоры работают синхронно и независимо друг от друга. Каждый процессор дешифрирует номер подынтервала i
int
2j
, в коN H
торый попала точка x j , затем считывает коэффициенты полинома (17), хранящиеся в памяти
компьютера, по адресам i,  , и с помощью схемы Горнера вычисляет значение функции в конкретной точке: f x j
 an i x j
a (n
1) i
x j
a (n
2) i
и еѐ аргумента записываются в память в виде пары элементов
x j
... a0 i . Значения функции
x j , f x j
последовательно-
сти, где j – номер ячейки. Временная сложность схемы вычисления (16) в точках x j с учѐтом
наперѐд
вычисленных
T N 2
O 1 .
144
коэффициентов
полинома
Ньютона
при
n const
составит
Раздел IV
Информатика
Далее строится базис ДПФ, точнее, действительная,
sin 2 n k N , части по значениям
n k N , и мнимая,
cos 2
. Для построения используется формула
x j , f x j
редукции синуса [6]:
sin x
где
K
sign x sin
обозначает дробную, int
строится
k
1
следующим
образом.
z ,K
int
x
– целую часть числа
Каждой
точке
, z
x
,
(19)
. Схема параллельного вычисления
x n, k
2 nk N ,
n 0, 1, ... , N 1 ,
0, 1, ... , N 1 , ставятся в соответствие процессоры с индексами n, k , p , p 0, 1, ... , N 2 1 .
Процессоры, работая параллельно, вычислят значения z n, k
N 2 процессоров по значению z n, k
2 nk
N
2nk
. Затем
N
параллельно дешифрируют адрес j 1 по совпадению в
двумерном массиве следующим образом:
z n, k , j1
x j1
0, 1, ... , N 2 1 ,
(20)
при этом в ячейке памяти с номером j1 также хранится значение функции f x j1
числяются значения
1
K
, K
2 nk
int
N
int
2nk
N
. Далее вы-
и sign 2 n k N , эти значения
перемножаются в соответствии с формулой (19).
Действительная часть строится аналогично мнимой, отличие лишь в том, что в точке
2 n k N значение cos 2 n k N вычисляется с помощью (19), где редуцируется функ-
x n, k
ция sin
2 2 nk N .
Временная сложность схемы составит
T N3 2
Теорема
k
5.
Базис
ДПФ
вида
O 1 .
cos 2 n k N
(21)
j sin 2 n k N ,
n 0, 1, ... , N 1 ,
0, 1, ... , N 1 , можно вычислить с произвольно заданной априори границей погрешности
при помощи таблично-алгоритмической схемы вычисления функций на основе интерполяционного полинома Ньютона и формулы редукции (19) на N 3 2 процессорах с временной сложностью
O 1 , иными словами, вычисление выполнимо с единичной оценкой времени (21).
Последующее ДПФ Re X k
Im X k
1
N
1
N
N 1
x n cos 2 n k N ,
n 0
N 1
x n sin 2 n k N с использованием схемы сдваивания выполняется с оценn 0
кой O log 2 N .
Теорема 6. В условиях теоремы 5 базис и собственно ДПФ, ограниченное N членами,
можно вычислить с произвольно заданной априори границей погрешности
алгоритмической схемы и схемы сдваивания с временной сложностью T N
на основе таблично3
O log 2 N .
Таблично-алгоритмическая схема построения базиса ДПФ имеет временную сложность
O 1 для произвольно заданной априори границы погрешности . Оценка времени вычисления
базиса инвариантна относительно числа отсчѐтов ДПФ.
Выводы. Предложенный алгоритм пилообразного преобразования при динамическом изменении числа отсчетов имеет сложность O log 2 N , что улучшает известную оценку O log22 N
[1]. Аналогично, оценка O log 2 N
для быстрого вейвлет-преобразования улучшает известную
оценку Мала O N log 2 N [8].
145
Вестник ТГПИ
Естественные науки
Основной результат работы заключается в построении динамически распараллеливаемых
схем выполнения пилообразного преобразования, преобразований Уолша и Хаара, быстрого вейвлет-преобразования и ДПФ при условии динамического изменения числа отсчетов с минимизацией временной сложности до O log 2 N путем параллельного пересчета элементов базиса для переменного значения N .
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Режим доступа: arXiv:quant-ph/0201120v1 26 Jan 2002
2. Блаттер К. Вейвлет-анализ. Основы теории. М., 2004. 280 с.
3. Забеглов В.В. Компьютерно-ориентированные схемы минимизации временной сложности цифровой обработки сигналов при динамическом изменении отсчетов: автореф. дис. канд. техн. наук. Таганрог: ТТИ
ЮФУ, 2010. 20 с.
4. Залманзон Л.А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука, 1989. 496 с.
5. Никитин Г.И. Применение функций Уолша в сотовых системах связи с кодовым разделением каналов.
СПб.: СПбГУАП, 2003. 86 с.
6. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на основе сортировки. II // Кибернетика и системный анализ. 2007. № 2. С. 161-174.
7. Смоленцев Н.К. Основы теории вейвлетов. Вейвлеты в MATLAB. М.: ДМК Пресс, 2005. 304 с.
8. Столниц Э., ДеРоуз Т., Салезин Д. Вейвлеты в компьютерной графике: пер. с англ. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002. 272 с.
146
Документ
Категория
Без категории
Просмотров
6
Размер файла
556 Кб
Теги
основные, дискретное, выполнения, параллельное, преобразование, ортогональных
1/--страниц
Пожаловаться на содержимое документа