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

• Забеглов, Валерий Валерьевич
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Забеглов, Валерий Валерьевич

ВВЕДЕНИЕ.

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

1.1. Описание исходной схемы пилообразного преобразования.

1.2. Первый алгоритмпараллельного вычисления коэффициентов матрицы, пилообразного преобразования.

1.3. Второй алгоритм параллельного вычисления коэффициентов матрицы пилообразного преобразования.

1.4. Рекуррентный алгоритм параллельного формирования матрицы пилообразного преобразования:.

1.5. Первый алгоритм параллельного выполнения пилообразного преобразования.

1.6. Второй алгоритм выполнения пилообразного преобразования.

1.7. Сравнение предложенных схем с известными.

1.8. Исходные-данные о системе-функций Радемахера.:.

1.9. Параллельное вычисление системы функций Радемахера с помощью схемы кусочно-полиномиальной аппроксимации.

1110. Параллельное вычисление системы функций Радемахера на основе схемы Стоуна.

1.11. Выводы.

1 ГЛАВА 2. ПАРАЛЛЕЛЬНЫЕ СХЕМЫ МИНИМИЗАЦИИ ВРЕМЕННОЙ СЛОЖНОСТИ ПРЕОБРАЗОВАНИЯ УОЛША И БЫСТРОГО ВЕЙ ВЛЕТ-ПРЕОБРАЗОВАНИЯ.

2.1. Вспомогательные утверждения для гильбертовых пространств и существенное свойство системы функций Уолша.

2.2. Исходные соотношения преобразования Уолша и определения.

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

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

2.5. Синтез схемы параллельного поэлементного формирования матрицы преобразования Уолша.

2.6. Исходные данные и определение вейвлет-преобразования.

2.7. Модификация быстрого алгоритма вейвлет-преобразования.

2.8. Алгоритм параллельного построения матрицы-преобразования вейвлетов Добеши.:.

2.9. Алгоритм быстрого параллельного вейвлет-преобразования.

2.10. Параллельный алгоритм быстрого вейвлет-преобразования с числом процессоров 0(Лг).

2.11. Параллельное выполнение преобразования Хаара.

2.12 Сравнение предложенных схем с известными.

2.13. Выводы.

ГЛАВА 3. ВИДОИЗМЕНЕНИЕ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ ДЛЯ ДИНАМИЧЕСКОГО ВЫЧИСЛЕНИЯ БАЗИСА С ЕДИНИЧНОЙ ВРЕМЕННОЙ СЛОЖНОСТЬЮ.

3.1. Исходные соотношения ДПФ.'.

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

3.3. Вычисление базиса ДПФ с учетом редукции аргумента к основному интервалу.

3.4. Синтез схемы параллельного вычисления ДПФ с учетом редукции аргумента к основному интервалу.

3.5. Последовательное численное моделирование параллельного вычисления базиса и выполнения ДПФ.

3.6. Сравнение предложенных схем с известными.

3.7. Выводы.

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

Актуальность проблемы. Цифровая обработка, сигналов (ЦОС), основываясь на математике XVII—ХИХ веков, в настоящее, время является существенным инструментом во многих сферах техники и науки. ЦОС — наиболее развивающаяся; отрасль современной*! электроники- которая используется в любой области, где информация представлена в цифровом виде или контролируется цифровым процессором. К числу областей, где применяется,ЦОС можно ,отнести следующие. о Обработка изображений: распознавание образцов, машинное зрение; улучшение изображения, факсимиле, спутниковые карты погоды, анимация: о Инструментальные средства/контроль: спектральный: анализ, контроль. | положения и скорости, снижение шума. о Речь/аудио: • распознавание речи, синтез речи, озвучивание текста,, цифровые аудиосистемы, выравнивание. о Военные цели: безопасная связь, работа с радарами, работа с сонарами; управление ракетами. ••.'■' о Телекоммуникации: устранение эха, адаптивное выравнивание, транскодеры АБРСМ', расширение спектра, видеоконференц-связь, передача данных. о Биомедицина: наблюдение за пациентами, сканеры, карты электроэнцефалограммы мозга, анализ электрокардиограмм, хранение (улучшение) рентгеновских снимков [ 1 ].

Цель обработки состоит в оценке характерных параметров сигнала или в преобразовании сигнала в форму, которая в некотором смысле- более удобна^ И

При цифровой обработке используются» ортогональные преобразования: Среди ортогональных преобразований широко4 известны [3] и активно применяются преобразования/ Фурье, Адамара, Хаара, Уолша,. вейвлет, пилообразное, синусоидальное и др. При использовании ортогональных. преобразований возникают задачи повышения скорости обработки информации, и сокращения объёма вычислений.

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

Дискретное преобразование Фурье (ДПФ). Преобразование Фурье применяется во многих сферах науки — в теории вероятности, теории чисел, комбинаторике, ЦОС, статистике, физике, геометрии, криптографии, акустике, оптике, океанологии, и многих других. В ЦОС и связанных областях ДПФ обычно рассматривается как декомпозиция сигнала на амплитуды и частоты. Его видоизменения используются при сжатии звука в МРЗ, сжатии I изображений в JPEG [5]. ДПФ определяется следующим образом.

Пусть ' от = 0, 1, .,N-1 элементы конечной числовой последовательности {x(m)} (действительных или комплексных чисел). 1

Преобразование Фурье последовательности {х(т ) } определяется как

Х{к)= ¿ = 0,1,., 7V-1, (1) т=О где, / = л/—I, WN=e~'27t!N [6]. Экспоненциальные функции в (1) ортогональны, т.е.

N, к-1 = О 0, к-1ф0 т=0

Для вычисления ДПФ нужно выполнить немалое количество операций умножения и сложения. ДПФ при N = 8 и фиксированном к записывается как

Х{к)=х(0)Т¥^ +х(\)1¥^ +х(1)ТГ£2 +х{ъ)ш£2 х(5)]¥*5 +х{6)1¥£6 л-х^^'1

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

Г) выполнить 8" -64 операции комплексного умножения и 8x7 = 56 операций комплексного сложения. Для N -точечного ДПФ число операций равно Л7"2 и N(N-1) соответственно. Так, например, для N = 1024 требуется выполнить

1 I приблизительно один миллион операций комплексного умножения и комплексного сложения.

Алгоритм5 быстрого преобразования Фурье (БПФ). Для вычисления ДПФ применяют алгоритмы, в которых объём вычислений значительно сокращён. Например, для N = 1024 ДПФ количество необходимых операций снижается в 204,8 раз. Соответствующим алгоритмам дали название «быстрого преобразования Фурье». Если этот алгоритм используется во временной области, то его именуют БПФ с прореживанием во временной области временной децимацией - ВД). Впервые появился алгоритм БПФ-ВД благодаря

Кули и Тьюки [7], в честь которых его называют. С помощью децимации снижается значительное число операций, выполняемых с данными во I временной области. Сокращение вычислений растёт по закону ' А'"2 — ( N¡1 )1о§2 N.

Вначале рассмотрим ./V-точечное БПФ для случаев N - 4, N = 8. Схемы 4-точечного и 8-точечного разложения по основанию 2 ДПФ-ВД [2] представлены соответственно на рис. 1 и 2.

Формулы этого алгоритма для 4-точечного ДПФ записываются в виде 1 г=О г=0 гк

ИЛИ

ХА(к) = [х(0)+х(2)1¥£ ]+Жк[х(1)+х(з)Ж2к ].

Чтобы перейти от всех предыдущих узлов ко всем последующим, согласно представленным диаграммам и формульной записи, нужно иметь все предыдущие вычисленные значения х(0)+х(2)Иг2к, х(1)+х(з)И/2/с и значение множителя . При этом множитель Игк представляется в виде -к

Ж4к =е 4 СОБ

2 71 781П

2п к = 0,3.

14 ;

В общем случае множитель представляется в виде

271 л. . . (2ж Л

П"=со8| ^пк |+у зт| —пк ) ^ и, как известно, обладает следующими свойствами [8] трк+М/2 тук

Ж, к + Ы

N 2 л, ¥У N ■>

-У

2л

N/2'

4-точечное БПФ-ВД

Рис. 1 8-точечное БПФ-ВД

Рис.2

Общая запись быстрого преобразования Фурье может быть представлена в виде г=0 /=0 I

Для перехода от всех предыдущих узлов ко всем последующим нужно иметь все предыдущие вычисленные суммы вида х(р)+х(д) IV . БПФ включает {^¡2)\о%1 N операций комплексного умножения в отличие от ДПФ, которое содержит Л^" комплексных умножении. При комплексном умножении экономия составляет

-/V 2 - ( N¡2 ) N. Для выполнения БПФ также I необходимо вычислить N 1о§2 N операций комплексного сложения в сравнении ДПФ, которое включает в себя N(1^ -1) операций комплексного сложения. Выигрыш при комплексном сложении составит

Алгоритм БПФ-ВД в основе которого лежит многократное деление исходного ДПФ в виде соотношения (>1) на два преобразования, одно из которых состоит из чётных членов, а другое - из нечётных, до тех пор, пока исходное преобразование не будет разложено на двухточечные преобразования исходных данных. Другой подход заключается в разделении исходного преобразования, одно включает в себя первую половину данных, другое -вторую. Впервые этот алгоритм частотной децимацией (БПФ-ЧД) был предложен [10], его часто именуют алгоритмом Сэнда-Тьюки.

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

В работе [11] предложена реализация параллельной? схемы ДПФ с временной» сложностью (9(^1 о£2 М)1. Также показана^ неоправданность подхода;: в котором в условиях предельного распараллеливания? двумерное: ДПФ сводится к; серии БПФ, в виду того, что в методах, вычисления БПФ сокращено число операций, но они не позволяют; использовать потенциал естественной параллельности преобразования: В работах [12, 13] построены схемы; параллельного вычисления базиса ДПФ и непосредственно* самого преобразования с оценкой' 0(1о§2 ТУ") на модели неветвящихся параллельных . , . . I программ [14, 15] без учета обмена.

Преобразование Уолша. Преобразования, основанные . на импульсоподобных сигналах, принимающие значения только ±1, больше подходят для г описания сигналов с нарушением» непрерывности, например они встречаются в изображениях. Функции Уолша используются: в спектральной:' обработке сигналов, при построении специализированных вычислительных устройств для кодирования и сжатия аудио- и видео-данных, в многоканальных, системах тестирования и диагностирования цифровых устройств шлогических структур большой степени интеграции [16 - 19]. Также преобразование Уолша применяется в сотовых системах связи с кодовым, разделением каналов [20]. Такие преобразования менее пригодны для описания непрерывных сигналов, они могут быть не инвариантны по фазе, может искажаться полученный спектр.

Дискретное преобразование Уолша основано на наборе прямоугольных гармонических импульсов, которые называются функциями Уолша [21]. Частота для прямоугольных импульсов не определена, используется аналогичный термин «частость». Частость — половина среднего числа переходов через нуль за единицу времени. На рис. 3 приведены функции Уолша до N = 8 порядка, упорядоченные по возрастанию. и

Функции Уолша, упорядоченные по Уолшу, при N = 8

У/АЦО. /> О

VALO, Г) О

VALC2, /) о

ЖЛЦЭ,1) О

VALC4, /) о

АЦ5,0 О о О

Ч'А1(7, о О

Рис. 3

Функция с порядком п и временем / обозначается Из рис.3 видно, что существует равное число нечётных и чётных функций Уолша. Нечётные функции ма1^2к + \Л) записываются как ,ш/(2А; + 1,/), чётные са/(2М), к = 1,2,., Я/2-1.

Функции Уолша ортогональны, т.е. ( \ ( \ (Ж п = т /=о [0, пФт

Преобразование Уолша определяется следующим соотношениям

1 N-1

Х(к) = — ^х(т)луа1(к,т), к = ., N-1

N /=1

Существует быстрый алгоритм преобразования Уолша, он выполняется с помощью сложения и вычитания без умножения на множитель 1/7У [5]. При использовании такого подхода требуется переход от кода Грея к двоичному коду, также требуется двоичная инверсия, поэтому он является не достаточно эффективным. Алгоритм быстрого преобразования Уолша, предложенный Манцем [22], который выполняется N N операций сложения и вычитания, также требует двоичной инверсии.

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

Преобразование Хаара. Преобразование Хаара активно применяется в графической обработке данных [24], используется для построения списков уменьшенных копий текстур'с размерами 2пх2п, п е N, при осуществлении пространственно-аккуратного текстурирования [25], также применимо для сжатия сеток высот поверхностей, параметризуемых на плоскости [26], распознавания зашумлённых изображений [27]. Коэффициенты преобразования Хаара У {к), к = 0,1,., N — 1, соответствующие входной последовательности I

X (/« )} = {X ( О )Х (1) . X ( N -1) } вычисляются по формуле [5] где Н*{Ы) - матрица Хаара размерностью N х N, которая получается в I результате дискретизации множества функций Хаара [28]

Наг (0, 0, 0) = 1, каг (/, г, в) =

2 лг9 О, ве г-1 г- \/2 2] ' г-7 г-1/2 г 27 ' 21 г -1 г 4

Матрица Хаара размерностью 8x8 записывается в виде [29]

13

1 1' 1 1 1 1 1 1

1 1 1 1 -1 -1 -1 -1 л/2 л/2 -л/2 -л/2 0 0 0 0

0 0 0 0 л/2' л/2 -л/2 -л/2

2 -2 0 0 0 0 0 0

0 0 2 -2 0 0 0 0

0 0 0 0 2 -2 0 0

0 0 0 0 0 0 2 -2

Алгоритм для вычисления преобразования Хаара, предложенный Эндрюсом [30], требует вычислить 2(Лг-1) операций сложения и вычитания и N операций умножения. Преобразование Хаара можно выполнять с помощью алгоритма типа Кули-Тьюки [7], для этого требуется N двоичных инверсий инверсий, 2 (ТУ -1) сложений и вычитаний и N операций умножений. В работе [31] предложена схема вычисления преобразования Хаара за время О (Ы).

Пилообразное (наклонное) преобразование. Ортогональное I преобразование, основанное на «пилообразных», базисных векторах длиною I четыре и восемь, было предложено Шибата и Эномото [32]. Пилообразный вектор представляет собой результат дискретизации пилообразной волны, убывающей равномерными шагами вдоль её длины. На рис. 4 изображён пилообразный сигнал при N - 4 и шаге, равном два.

Пилообразный сигнал при N = 4 и шаге, равном два.

-1 -2 -3

Рис. 4

Обобщение, введённое Праттом, Уэлчем, и Ченом [33, 34], привело к определению пилообразного преобразования, которое широко применяется при кодировании изображений [35, 36]. Пилообразное преобразование используется во многих приложениях для обработки изображений, среди которых кодирование, сжатие [37] и восстановление изображений [38-40], также применяют при создании водяных знаков [41^43].

Пилообразное преобразование обладает следующими особенностями:

1) среди базисных векторов имеется вектор с одинаковыми компонентами (постоянный базисный вектор);

2) наклонный базисный вектор монотонно убывает от максимального до минимального значения скачками постоянной величины;

3) матрица преобразования обладает секвентным свойством;

4) существует быстрый алгоритм преобразования;

5) обеспечивается высокая степень концентрации энергии изображения.

Пилообразное преобразование определяется как

Ау = х , I где Гу - вектор коэффициентов пилообразного преобразования, Ху — вектор входной последовательности, Ям — матрица преобразования размерностью уУХАА.

Пилообразное преобразование можно вычислить с помощью 1 быстрого алгоритма. Для случая N = 4 алгоритм приведён на рис. 5 [6]. '

Граф пилообразного преобразования, N = 4

1/2

-Э (0)

25£о (1)

2)

3/2\/5

-Л— Р (3)

Рис. 5

Из рис. 5 следует, что для вычисления коэффициентов пилообразного преобразования £> ( к ), к = 0,1, 2, 3, 4, необходимо выполнить восемь сложений и шесть умножений. Наряду с этим, были предложены быстрые алгоритмы пилообразного преобразования [44, 45] с временными сложностями О (/V Ы) и О (м) . В работах [46^49] излагаются модификации алгоритмов пилообразного преобразования.

Быстрое вейвлет-преобразование. По сравнению с традиционным анализом данных преобразования Фурье, результаты, которые получаются с помощью вейвлет-анализа, часто имеют большую информативность и способны обрабатывать особенности данных, которые при традиционном подходе анализировать затруднительно. Сравнение прежнего и новых подходов рассмотрено в литературе, в работах И. Добеши [50-53], А. Луиса и соавторов [54], В Свелдсена [55-61], К.Чуи [62]. Вейвлет-методы дополняют, а иногда» могут полностью заменить обработку данных традиционными методами. При вейвлет-преобразовании функции / (х) вычисляется серия коэффициентов сЛдг,сДу,с£>лг1,. с£>, }. Каждый коэффициент вычисляется по формулам [58-60]: а]-т,к = (/><Р^т,к)= (*)бЬг, Я где т = 1, 2,., N. Быстрое вейвлет-преобразование, которое предложил Малла [66], позволяет вычислять коэффициенты вейвлет-разложение без интегрирования, с помощью операции на основе свёртки. я « где {/*„} - масштабирующий фильтр масштабирующей функции <р(х), {} фильтр вейвлета у/ (х). Соотношения (3) позволяют вычислять вейвлеткоэффициенты, используя операции умножения и сложения. Для случая, когда длина фильтров конечна и равна Ь, требуется выполнить 2ЬИ умножений [67]. В книге [68] упоминается схема вычисления быстрого вейвлет-преобразования I на основе блока фильтров с оценкой" 0(ы). В книге [69] сравнивается вычислительная сложность алгоритмов одиночного, двойного и частотно-временного вейвлет-преобразований одномерного сигнала длиной N и* дерева максимальной длины <Л, которая составляет 0(Ы<}), и о{и2с1) соответственно.

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

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

Процессоры ЦОС для удобства делят на две большие категории: специализированные и универсальные. Специализированные устройства делят на два вида.

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

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

Большая часть универсальных процессоров доступных сейчас основаны на архитектуре фон Неймана, где операции выполняются последовательно [70]. На рис. 6 приведена архитектура фон Неймана.

Архитектура фон Неймана

Рис. 6

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

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

Стандартная универсальная аппаратная архитектура обработки сигналов

Ялройства ввода-вывода

Арифметические устройства ш

Схема сдвига

Накопитель

Запом инающие устройства I

Память для хранения данных X

Память для хранения данных У

Память для хранения программы

1 Шина данных X |

1 1 4 * 1 { 1

1 Шнна данных У 5 1

1

1 Шнна данных Р

Рис. 7

Она имеет следующие особенности.

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

Порт ввода-вывода делает возможным обмен данными с внешними устройствами (ЦАП, АЦП) или передачу цифровых данных процессорам. Прямой доступ к памяти позволяет быстро обмениваться блоками данных с памятью для хранения данных, причём, обычно это совершается при внешнем управлении.

- Арифметические устройства для арифметических и логических операций, в число которых входят аппаратные умножители, схемы сдвига (или умножители-накопители) и АЛУ.

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

ЦОС важно оптимизировать под операции ЦОС и систему команд, и 1 аппаратную архитектуру. Для этого в процессорах ЦОС обширно применяется концепция параллелизма. Используются следующие средства:

- гарвардская архитектура; 1

- конвейерная обработка;

- быстрые специализированные аппаратные умножители-накопители;

- специальные команды, определенные для ЦОС;

- копирование;

- встроенная память/кэш;

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

Гарвардская архитектура. В процессорах ЦОС применяется гарвардская архитектура, названная по работе, реализованной в 1940-х годах в университете Гарварда под руководством Г. Айкена [71]. Главная особенность гарвардской архитектуры состоит в том, что память для хранения программы и память для хранения данных находятся в разных местах, делая возможным полное совмещение во времени операций вызова из памяти команды и её I выполнения. Стандартные процессоры, например Intel 6502, имеют одну шину, через которые передаются и команды и данные. Одношинная структура приведена на рис. 8.

Упрощённая архитектура стандартных микропроцессоров I

Рис. 8

В стандартном процессоре без гарвардской архитектуры данные (операнды) команды программы (программный код) хранятся в одной области памяти (Рис. 8). Таким образом, невозможен вызов следующей команды при I исполнении текущей, т.к. обе операции требуют обращения к памяти. В гарвардской архитектуре, приведённой на рис. 9, данные и команды программы содержаться в разных областях памяти, вызов следующей команды возможен вместе с выполнением текущей команды.

Стандартная гарвардская архитектура с раздельными областями памяти для хранения данных и программы

Рис. 9. i

Строгая гарвардская архитектура применяется, только в нескольких процессорах ЦОС (Motorola DSP56000), большей части устройств используется 1 модифицированная гарвардская архитектура (TMS320) [1]. В модифицированной гарвардской архитектуре области памяти для хранения данных и программ также отдельны, но здесь возможна связь между этими областями памяти.

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

Число этапов, на которые разделяется процесс выполнения команды, отличается в различных процессорах [72].

- В процессорах TI С2Х имеется три этапа конвейера: выборка, I декодирование, выполнение команды. В процессорах TI С24Х, С5Х, С20Х -четыре: выборка команды, декодирование команды, подготовка операнда, выполнение. В процессорах TI С5000 - шесть этапов. В процессорах С6000 число этапов переменное и достигает до одиннадцати.

- В процессорах ADIAD2100 и AD2106x - три этапа.

- В процессорах Motorola DSP56K - три этапа, в процессоре DS56300 -семь. ,

Рассмотрим пример конвейерной обработки, где команда разделяется на три этапа [1]. Каждый этап команды рассматривается как каскад конвейера. Используя данный метод можно сформировать наложение команд, в котором новая команда начинает выполняться в первый момент каждого такта, как показано на рис. 10.

Концепция конвейерной обработки

Команда I Команда 2 Команда 3

Каскад конвейера 1

Каскад конвейера 2

Каскад конвейера 1

Каскад конвейера 3

Каскад конвейера 2

Каскад конвейера 1

Каскад конвейера 3

Каскад конвейера 2

Каскад конвейера 3

Рис. 10 t

На рис. 11 показана временная диаграмма, на которой выделены этапы команд трёхкаскадного конвейера. I

Временная диаграмма трёхкаскадного конвейера и

Выборка команды Декодирование команды Выполнение команды

1 1 1 1 1 1 1 1 1 1 1 1 /+1 1 /+ 2

1 * "И 1 1 1 1 !с ''-1 ,!. I 1 / { (+1 /+ 2

1 1 1 1 !. '-2 .¡ 1 1 ¿-1 \ 1 " 1 " /41 /+2

Г 1 1 Г 1 11111

Рис. 11 I

Каждый этап в конвейере занимает один машинный цикл, в течении этого цикла одновременно активны могут быть до трёх различных команд, но все они будут на разных фазах завершения. Таким образом, три части команды (выборка из I памяти, декодирование, выполнение) независимы и может совмещаться выполнение нескольких команд. На рис. 11 представлено, что в ходе / -го цикла процессор может синхронно считывать из памяти г -ю команду, декодировать (г-1)-ю команду и одновременно выполнять (/-2)-ю команду.

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

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

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

Аппаратный умножитель-накопитель. Основными численными операциями в ЦОС являются сложение и умножение. Умножение в программной форме известно своей трудоёмкостью, если применяется арифметика с плавающей запятой, то сложение представляет ещё более трудоёмкую операцию. Чтобы максимально увеличить скорость ЦОС в реальном времени, рекомендуется применять специализированные аппаратные умножители-накопители с арифметикой с фиксированной или плавающей запятой. Такое аппаратное обеспечение повсеместно применяется во всех цифровых процессорах сигналов. В процессоре с фиксированной запятой аппаратный умножитель за такт получает два 16-битовых дробных числа, представленных в форме дополнения до двух, и затем вычисляет их 32-битовое произведение. Среднее время выполнения команды умножения-накопления значительно сокращается, если применяются специальные команды повторения. I

Типичная конфигурация аппаратного умножителя-накопителя ЦОС представлена на рис. 12.

Конфигурация умножителя-накопителя

Дани ые X I Данные У

Рис. 12

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

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

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

ЦОС, содержат: 1

1) команды, обеспечивающие поддержку базовых операций ЦОС; команды, снижающие служебные издержки-для порядка циклов ^команд;

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

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

I ! памяти, часть кода, которая обычно требует цикла из нескольких тактов, эффективно трансформируется в однотактовую> команду. Команды повтора особенно полезны в ЦОС для расчёта внутренних циклов, например, в адаптивной фильтрации и записи данных в порядке при вычислении БПФ, определяемом обращёнными битами.

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

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

Расширенный параллелизм и статическая суперскалярная обработка. В настоящий момент в архитектуре процессоров ЦОС прослеживается тенденция к повышению производительности за счёт увеличения числа команд, которые выполняются в каждом такте, и количества операций, которые > выполняются при вызове одной команды [74—78].

В новых архитектурах процессоров ЦОС для увеличения вычислительной эффективности применяются методы параллельной обработки. Наиболее часто используются (порой совместно) следующие архитектуры: архитектура SIMD (single instruction, multiple data - с одним потоком команд и многими потоками данных, она же ОКМД — «одна команда, много данных»), архитектура VLIW ' (very-large-instruction-word - архитектура с командными словами сверхбольшой длины) и суперскалярная обработка [76, 78, 79].

Обработка на основе архитектуры SIMD применяется для увеличения I числа операций, которые выполняются при вызове одной команды. Как правило, процессор ЦОС с архитектурой SIMD обладает несколькими^ операционными блоками и несколькими трактами передачи данных. 'Таким образом, одна команда передаётся нескольким операционным блокам для обработки блоков данных одновременно, увеличивая число1 операций, которые выполняются за один такт. На рис. 13 приведён процессор ЦОС, который ■ располагает двумя операционными блоками, каждый имеет АЛУ, умножитель-накопитель и схему сдвига. Процессор способен выполнять две различных арифметических операции одновременно в течение одной команды.

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

Двойные арифметические устройства и двойные тракты передачи данных для обработки по схеме ЭГМБ

Шина данных—А 1

Шина данных — В

АЛ у

Умножитель/ накопитель

Схема сдвига

Операционное устройство А

АЛУ Умножитель/ накопитель Схема сдвига

Операционное устройство В

РИС. 13 1

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

Обработка с помощью командных слов сверхбольшой длины (УЪ^) позволяет значительно увеличить число команд, которые обрабатываются за такт [78]. Командное слово сверхбольшой длины, по сути, является

I > конкатенацией (операция склеивания объектов линейной структуры) нескольких коротких команд, для выполнения которых за один такт требуется несколько операционных блоков, работающих параллельно.

Схема архитектуры и схема потока данных процессоров ЦОС с фиксированной запятой ТМ8320С62х приведены на рис. 14. Центральный процессор имеет два тракта передачи данных и восемь независимых операционных блоков, которые организованы в два набора, где Ь1, Ь2 -логические элементы, 81, 82 - схемы сдвига/логические элементы, М1, М2 -умножители, Б1, Б2 - адресные элементы. Длина каждой короткой команды равна 32 битам, восемь таких команд вместе образуют пакет командного слова сверхбольшой длины, который может обрабатываться параллельно несколькими устройствами.

Обработка по принципу УЫ\¥ начинается со считывания центральным процессором из встроенной программной памяти пакета команд (восемь 32-битовых команд). Восемь команд в вызванном пакете образовывают исполняемый пакет, если они могут выполняться параллельно, а затем передаётся восьми операционным блокам. Следующий 256-битовый пакет команд считывается из программной памяти во время декодирования и выполнения исполняемого пакета. Если восемь команд нельзя выполнять параллельно, тогда формируется несколько исполняемых пакетов, которые передаются операционным блокам по одному за один раз.

Принцип архитектуры с командными словами сверхбольшой длины

Внутренняя память для хранения программы (кэш)

8 32-битовых команд и 51 М1 01

Блок регистров А

32 и. 82 М2 т

Елок регистров В

•Г32

Пакет извлеченных команд

Внутреннее ОЗУ данных

Исполняемые пакеты

Два тракта данных

Рис. 14

Архитектура УЬГУ специализирована для поддержки параллелизма на уровне команд. Если объединить конкретную архитектуру с большой тактовой частотой, то получаются очень эффективные процессоры ЦОС [1].

Ещё один метод повысить скорость выполнения команд процессора ЦОС - суперскалярная обработка. В ней применяется параллелизм на уровне команд. Традиционно термином «суперскалярный» называют архитектуру компьютера, которая позволяет выполнять несколько команд за один такт [79]. Суперскалярные процессоры ЦОС имеют несколько операционных блоков, и несколько команд могут передаваться этим блокам для параллельной обработки.

В процессорах ЦОС, построенных на архитектурах уЫ"\Л^ и суперскалярной обработке, для эффективного использования параллельных операционных блоков необходимо статистическое планирование команд перед

1 I выполнением программы. Также нужно учитывать возможную зависимость по данным (например, результаты нужны до того, как они готовы) и зависимость по управлению (например, применение команд ветвления), что способно приводить к проблемам при параллельной обработке.

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

Для выполнения ортогональных преобразований необходимо формировать матрицы преобразований, вычислять коэффициенты данных матриц. Также необходимо вычислять базисные функции преобразования, т.к. совокупность значений дискретных базисных функций образуют матрицу преобразования, иными словами, дискретные значения базисных функций являются коэффициентами матриц. Например, в ДПФ такими функциями к2тгп\ . (к2пп являются сое - и бш N ) V N . В некоторых ортогональных разложениях базисными функциями (например, функции Уолша, Хаара) являются кусочно-постоянные функции. Значение базисных функций в конкретной точке необходимо вычислять для каждого элемента последовательности ортогонального преобразования, поскольку аргументы базисных функций меняются в зависимости от порядкового номера элемента базиса.

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

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

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

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

О (1о§2 N ) и 0(1) для формирования матрицы в реальном времени при динамическом изменении числа отсчетов.

4. Синтезировать алгоритм параллельного преобразования Уолша с минимизацией временной сложности до значения О ( \о%2 N ) для выполнения преобразования в реальном времени при переменном количестве отсчетов.

5. Разработать модификации быстрого вейвлет-преобразования, на их основе построить параллельные схемы преобразования, позволяющие i 32 вычислять одновременно все вейвлет-коэффициенты и выполнять преобразование в реальном времени при. динамическом изменении отсчетов:

6. Разработать схему параллельного преобразования Хаара; включающую алгоритм, формирования' матрицы преобразования, с минимальной временной« сложностью* О(l), для! выполнения!преобразования в реальном времени при динамически.меняющемся количестве отсчетов. ,

7. На основе кусочно-полиномиальной' аппроксимации5 элементов? базиса: и редукции аргумента синтезировать, параллельный алгоритм; вычисления базиса ДПФ за время О (l) и выполнения преобразования за время О (log2 N ) при динамическом изменении; отсчетов./

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

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

Научная? новизна»

1. Предложены схемы параллельного вычисления, матрицы пилообразного преобразования с временной сложностью 0( log2 log2 N ) и <9(l), на . этой основе синтезированы параллельные алгоритмы выполнения преобразования, отличающиеся от известных временной сложностью

0(log2 N ) и позволяющие выполнять , преобразование в режиме реального времени при динамическом изменении отсчетов^ i

2. Предложены параллельные схемы вычисления функций Радемахера с использованием схем Стоуна с временной сложностью 0(log2]V) при количестве процессоров N2 и кусочно-полиномиальной аппроксимации тригонометрических функций — с временной сложностью 0 ) при-количестве процессоров N\og2 N, которые улучшают известные оценки за счет увеличения числа процессоров и объема постоянной памяти.

3. На основе предложенных схем вычисления функций Радемахера разработаны алгоритмы построения матрицы преобразования Уолша с временной сложностью 0[\о^21о§2 N) при количестве процессоров

ТУ"2 \og-yN и О (Г) - с использованием счетчика.одноразрядных единиц, — что отличается от известной; оценки алгоритма афинной формы и позволяет, в реальном времени формировать матрицу преобразования5 при динамическом, изменении числа отсчетов.

4. Построены схемы параллельного преобразования Уолша! с временной сложностью 2 при количестве процессоров N2, улучшающие известную оценку на основе квантовых вычислений и позволяющие выполнять преобразование в реальном* времени- при переменном, количестве, отсчетов за счет динамического пересчета матрицы преобразования. ,

5. Предложены две Модификации быстрого вейвлет-преобразования, первая из которых позволяет параллельно вычислять все коэффициенты вейвлет-преобразования за время 1о§2 .<У х 1о&2 тУ ) при количестве процессоров N3l вторая позволяет подмножество коэффициентов,; определяемое конкретным разрешением, вычислять за время 0(1) при .количестве процессоров ЬхЫ, где Ь — длина вейвлет-фильтра, что улучшает известные оценки алгоритма Малла и позволяет выполнять вейвлетг преобразование в реальном времени при динамическом, изменении, отсчетов.

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

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

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

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

1. Предложены схемы параллельного вычисления матрицы пилообразного преобразования с временной сложностью 0(log2 к^2 N ) и 0(1), синтезированы параллельные алгоритмы выполнения преобразования с временной сложностью N ), позволяющие выполнять преобразование в режиме реального времени при динамическом изменении отсчетов.

2. Предложены параллельные схемы вычисления функций Радемахера с использованием схемы Стоуна с временной сложностью 0(1о§2 N) и на основе кусочно-полиномиальной аппроксимации тригонометрических функций - с временной сложностью 0{\ ) при количестве процессоров N.

3. Синтезированы алгоритмы построения матрицы преобразования Уолша с временной сложностью 0{\о£2 1о§ 2 А^ ) при количестве процессоров

N 2 1о§2 N и (9(1)—с использованием счетчика одноразрядных единиц - для формирования матрицы преобразования в реальном времени.

4. Построены схемы параллельного преобразования Уолша с временной сложностью ОN ) при количестве процессоров И2, которые позволяют выполнять преобразование в реальном времени при переменном количестве отсчетов за счет динамического пересчета матрицы преобразования.

5. Предложены две модификации быстрого вейвлет-преобразования, первая из которых позволяет параллельно вычислять все коэффициенты преобразования за время О ( log 2 log 2 N х log 2 N ) при количестве процессоров о

N ; вторая — позволяет подмножество коэффициентов, определяемое конкретным разрешением, вычислять за время 0(l) при количестве процессоров LxN, где L - длина вейвлет-фильтра.

6. Разработано параллельное видоизменение преобразования Хаара, выполняемое с\ временной сложностью 0(log2 N), которое включает динамическое формирование матрицы преобразования за время ), позволяя выполнять преобразование в реальном времени при динамически меняющемся количестве отсчетов.

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

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

Внедрение неиспользование результатов работы. Полученные в работе результаты использованы в ОАО «Таганрогский завод «Прибой» при обработке плоского отображения сигналов гидроакустической локации, при выполнении интегральных преобразований гидроакустических сигналов, а также при оценке скорости их изменений для сокращения времени обработки при одновременном увеличении ее точности; в учебном процессе факультета информатики и управления Таганрогского государственного педагогического института в курсах «Основы информатики», «Теоретические основы информатики», «Теоретические основы нейроинформатик^», «Информационные технологии в математике», «Численные методы», «Программирование», «Компьютерное моделирование», а также в курсах по выбору и практикуме решения задач на ЭВМ, что подтверждено соответствующими актами об использовании, приведенными в приложении 2 к диссертационной работе.

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

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

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

- XIII Всероссийская научно-техническая конференция «Современные i методы и средства обработки пространственно-временных сигналов» (ВК-95-90) (Пенза, ПДЗ, Пензенская государственная технологическая академия, 2010).

- VIII региональная научно-практическая конференция «Аспекты модернизации образования и развития промышленности» (Таганрог, ДГТУ, 2010).

- XI Всероссийский симпозиум по прикладной и промышленной математике (осенняя открытая сессия) (Сочи-Дагомыс, 2010).

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

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

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

3.7. Выводы

1. Синтезирован параллельный алгоритм вычисления всех элементов базиса ДПФ на основе кусочно-полиномиальной' аппроксимации и редукции синуса с временной сложностью (9(1). Алгоритм инвариантен относительно числа отсчетов ДПФ, не требует избыточных затрат памяти, что в сочетании с минимальной оценкой времени отличает его от известных и создает предпосылки выполнения ДПФ в реальном времени при динамическом изменении количества отсчетов. I

2. Предложена параллельная схема ДПФ с использованием схемы сдваивания и алгоритма параллельного вычисления базиса ДПФ, применимая для вычисления ДПФ при условии динамического изменения числа отсчетов. 1

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

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

141

заключение

Основной результат диссертационной работы заключается в построении динамически распараллеливаемых схем; выполнения пилообразного преобразования, преобразований Уолша и Хаара,. быстрого вейвлет-преобразования и ДПФ при условии динамического изменения числа отсчетов с минимизацией временной сложности, до* о (log2 n ) путем, параллельного пересчета элементов, базиса для переменного значения N. Работа включает следующие научные результаты.

1. Предложены схемы- . параллельного вычисления матрицы пилообразного преобразования с временной сложностью 0('log2 log2 n ) и O(l), синтезированы параллельные алгоритмы выполнения.преобразования с временной сложностью 0( log2 n ), позволяющие выполнять преобразование в режиме реального времени при динамическом изменении отсчетов.

2. Предложены параллельные схемы вычисления функций Радемахера с использованием схемы Стоуна с временной сложностью 0(log2 n )< и- на основе кусочно-полиномиальной аппроксимации тригонометрических функций^ — с временной сложностью 0( l ) • при-количестве процессоров* n log2 n. I

3. Синтезированы алгоритмы построения матрицы- преобразования' Уолша с временной сложностью O(log2 log2 n ) при количестве процессоров n 2 log2 TV и О (1) — с использованием счетчика одноразрядных единиц - для формирования матрицы преобразования в реальном времени:

4. Построены схемы параллельного преобразования Уолша с временной сложностью о (log2 n ) при количестве процессоров n2, которые позволяют выполнять преобразование в реальном времени при переменном количестве отсчетов за счет динамического пересчета матрицы преобразования:

5. Предложены две модификации быстрого вейвлет-преобразования, первая из которых позволяет параллельно вычислять все коэффициенты, преобразования за время- 0(log2 log2 n- х log2 n ) при количестве процессоров л n ; вторая — позволяет подмножество коэффициентов, определяемое конкретным разрешением, вычислять за время 0(1) при количестве процессоров Ь х N, где Ь — длина вейвлет-фильтра. I

6. Разработано параллельное видоизменение преобразования Хаара, выполняемое с временной сложностью которое включает динамическое формирование матрицы преобразования за время 0{\ ), позволяя выполнять преобразование в реальном времени при динамически меняющемся количестве отсчетов.

7. Синтезированы инвариантные относительно числа отсчетов параллельные алгоритмы вычисления всех элементов базиса ДПФ на основе кусочно-полиномиальной аппроксимации и редукции аргумента за время О (1) без избыточных затрат памяти. На этой основе параллельные схемы ДПФ инвариантны относительно динамически меняющегося числа отсчетов и позволяют выполнять преобразование с временной сложностью n ) в условиях произвольно заданной границы погрешности вычислений.

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

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

2. Предложены параллельные схемы вычисления функций Радемахера с использованием схем Стоуна с временной сложностью <Э(1о§2 N) при количестве процессоров Ы2 и кусочно-полиномиальной аппроксимации тригонометрических функций - с временной сложностью О (1) при количестве процессоров N\og2N, которые улучшают известные оценки за счет увеличения числа процессоров и объема постоянной памяти.

3. На основе предложенных схем вычисления функций Радемахера разработаны алгоритмы построения матрицы преобразования Уолша с временной сложностью 0(log2 log2 N) при количестве процессоров

N2 log2 N и 0(\) - с использованием счетчика одноразрядных единиц, - что отличается от известной оценки алгоритма афинной формы и позволяет в реальном времени формировать матрицу преобразования при динамическом изменении числа отсчетов.

4. Построены схемы параллельного преобразования Уолша с временной сложностью О(log2 N) при количестве процессоров N2, улучшающие известную оценку на основе квантовых вычислений и позволяющие выполнять преобразование в реальном времени при переменном количестве отсчетов за счет динамического пересчета матрицы преобразования.

5. Предложены две модификации быстрого вейвлет-преобразования, первая из которых позволяет параллельно вычислять все коэффициенты вейвлет-преобразования за время О (log 2 log 2 N х log 2 N ) при количестве о процессоров N ; вторая позволяет подмножество коэффициентов, определяемое конкретным разрешением, вычислять за время О (1) при количестве процессоров LxN, где L — длина вейвлет-фильтра, что улучшает известные оценки алгоритма Малла и позволяет выполнять вейвлет-преобразование в реальном времени при динамическом изменении отсчетов.

6. Разработано параллельное видоизменение преобразования Хаара, выполняемое с временной сложностью 0(log2 N), которое включает динамическое формирование матрицы преобразования с временной сложностью O(l), что отличается от оценок алгоритмов Эдрюса и Кули

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

7. Синтезированы параллельные алгоритмы вычисления всех элементов базиса ДПФ на основе кусочно-полиномиальной аппроксимации и редукции аргумента с временной сложностью 0(1), инвариантные относительно числа I отсчетов,ДПФ, без избыточных затрат памяти, что в сочетании с минимальной оценкой времени отличает их от известных и позволяет построить параллельную схемы ДПФ, применимые для вычисления ДПФ при условии динамического изменения числа отсчетов. Параллельные схемы ДПФ отличается от известных по построению, по способу адресации к данным, инвариантностью относительно динамически меняющегося числа отсчетов и временной сложностью (3(1о§2 n ) в условиях произвольно заданной границы погрешности вычислений.

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

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

Полученные в- работе результаты использованы в ОАО «Таганрогский завод «Прибой» при обработке плоского отображения сигналов гидроакустической локации, при выполнении интегральных преобразований гидроакустических сигналов, а также при оценке скорости их изменений для сокращения времени обработки при одновременном увеличении ее точности; в учебном процессе факультета информатики и управления Таганрогского государственного педагогического института в курсах «Основы информатики», «Теоретические основы информатики», «Теоретические основы нейроинформатики», «Информационные технологии в математике»,

Численные методы», «Программирование», «Компьютерное моделирование», 1 а также в курсах по выбору и практикуме решения задач на ЭВМ, что подтверждено соответствующими актами об использовании, приведенными в приложении 2 к диссертационной работе.

146

Список литературы диссертационного исследования кандидат технических наук Забеглов, Валерий Валерьевич, 2010 год

1. Айфичер, Эммануил С., Джервис, Барри У. Цифровая обработка сигналов: практический подход, 2-е-издание. : Пер. с англ. - М.: Издательский дом «Вильяме», 2004. - 992 с. : ил. - Парал. тит. англ.

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

3. Ромм Я.Е., Забеглов В.В. Параллельные алгоритмы , пилообразного преобразования для цифровой обработки изображений / ТГПИ. — Таганрог, 2008. 19 с. - Деп. в ВИНИТИ 30.09.2008, №783 - В2008. '

4. Быстрые алгоритмы в цифровой обработке изображений / Т.С. Хуанг,i

5. Дж.-О. Эклунд, Г. Дж. Нуссбаумер и др.; Под ред. Т.С. Хуанга: Пер. с англ. -М.: Радио и связь, 1984. 224 е., ил.

6. Красильников H.H., Красильникова СШ. Мультимедиатехнологии в информационных системах. Методы сжатия и форматы записи графической информации: Учеб. Пособие / СПбГУАП. СПб., 2004. 68 е.: ил. ISBN 5-80880104-4.

7. Ахмед 'Н., Pao K.P. Ортогональные преобразования при обработкеiцифровых сигналов: Пер. с англ. Т.Э. Кренкеля / Под ред. И.Б. Фоменко. М.: Связь, 1980.-248 с.

8. Cooley J.W. and Tukey J.W. (1965) An algorithm for the machine calculation of complex Fourier series. Mathematics Computation, 19, 297-301.

9. Гольденберг JI.M. и др. Цифровая обработка сигналов: Учебное пособие для вузов / JI.M. Гольденберг, Б.Д. Матюшкин, М.Н. Поляк. — 2-изд., перераб. и доп. М.: Радио и связь, 1990. - 256 е.: ил.

10. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. М.: Мир, 1989. - 448 е., ил.

11. O.Gentleman W.M. and. Sande G. (1966) Fast Fourier transforms for fun and profit. In Fall Joint Computing Conf., AFIPS Proc., 29, 563-578.

12. Jleyc В.А., «О временной сложности параллельной реализации численного преобразования Фурье», Матем. моделирование, 7:10 (1995), 99110.

13. Ромм Я.Е., Фирсова С.А. Параллельная схема дискретного и быстрого1.*преобразований Фурье на основе полиномиального представления базиса // Известия РАН. Математическое моделирование, 2006. Т. 18. - № 11. - С. 3-12.

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

15. Голубов Б.И., Ефимов A.B., Скворцов В.А. Ряды и преобразования

16. Уолша. М.: Наука, 1987. - 344 с.

17. Дядюнов Н.Г., Сенин А.И. Ортогональные и квазиортогональные сигналы. М.: Связь, 1977. - 224 с.

18. Карповский М.Г., Москалев Э.С. Спектральные методы анализа и синтеза дискретных устройств. Ленинград: Энергия, 1973. - 142 с.

19. Никитин Г.И. Применение функций Уолша в сотовых системах связи с кодовым разделением каналов. Санкт-Петербург: СПбГУАП, 2003. — 86 с.

20. Х.Ф. Хармут. Передача информации ортогональными функциями. Пер. с англ. Дядюнова Н.Г. и Сенина А.И. М., «Связь», 1975.

21. Manz, J.W.: A Sequency-Ordered Fast Walsh Transform. IEEE Trans. Audio and Electroacoustics AU-20 (1972) 204-205. '

22. Визор Я.Е., Чичирин E.H., Семотюк M.B. Формирование функций Уолша для многоканальных систем реального времени // Проблеми шформатизаци та управлшня. — 2009. — 4(28). — С. 24—27 (http://www.iit.nau.edu.ua/uk/science/compnum4-28/).

23. Милов А.Н. Оптимизированные алгоритмы преобразования Хаара для отечественной платформы DSP «ELCORE» и их применение в задачах графической обработки данных. — Вычислительные методы и программирование, 2007, Т. 8, с.:34-39.

24. Williams L. Pyramidal parametrics // Computer graphics. 17, №3. 1983. 111.

25. Переберин A.B. Многомасштабные методы синтеза и анализа изображений: Дисс. кандидата физико-математических наук. М.: ИМП им. М.В. Келдыша, 2002.

26. Гринь Н.Ю., Гальченко В.Я. Применение дискретных вейвлетIпреобразований Хаара для распознавания зашумленных изображений с помощью модифицированного алгоритма Юра-Фосслера. Научно-теоретический журнал "Искусственный интеллект" No.l, 2004

27. И.М. Соболь. Многомерные квадратные формулы и функции Хаара. Под ред. В.М. Гринберга М.: Наука, 1969. - 288 с.

28. Ahmed, N., Natarajan, Т., and Rao, K.R.: Some Considerations of the Modified Walsh-Hadamard and Haar Transforms. Proc. 1973 Symp, Applications of Walsh Functions, 91-95.

29. Andrews, H.C., and Caspari, K.L.: A Generalized Technique for Spectral Analysis. IEEE Trans. Computers C-19 (1970) 16-25.

30. K.P. Chan and A.W. Fu. Efficient time series matching by wavelets. In Proceedings of the 15th International Conference on Data Engineering, pages 126133, 1999.

31. Enomoto, H., and Shibata, K.: Orthogonal Transform Coding System for Television Signals. Proc. 1971 Symp. Application of Walsh Function, 11-17.

32. Pratt, W.K., Welch, L.R., and Chen, W.H.: Slant Transforms. Proc. 1972 Symp. Application of Walsh Function, 229-234.

33. Chen, W.H., and Pratt, W.K.: Color Image Coding with the Slant Transform. Proc. 1973 Symp. Application of Walsh Function, 155-161.

34. Shibata, K.: Waveform Analysis of Image Signals by Orthogonali

35. Transformation. Proc. 1972 Symp. Application-of Walsh Function, 210-215.

36. Shibata, K.: Block Waveform Coding of Image Signals by Orthogonal Transformation. Proc. 1973 Symp. Application of Walsh Function, 137-143.

37. P.C. Mali and D.D. Majumder, "An analytical comparative study of a class of discrete linear basis transforms", IEEE Trans., Syst., Man & Cyber. 24(3), pp. 531— 536, 1994.i

38. R.J. Clarke, Transform Coding of Image, Academic Press, New York, 1985.

39. W.K. Pratt, L.R. Welch, and W.H. Chen, «Slant transform for image coding», Proc. Symp. Appl. Walsh Function, Mar. 1972.

40. W.K. Pratt, W.H. Chen and L.R. Welch, «Slant transform coding», IEEE Trans. Commun., vol. COM-22, Aug. 1974.41 .http://watermarking.unige.ch/Checkmark/index.html. i

41. A. T. S. Ho, J. Shen, and S. H. Tan, "Digital image-in-image watermarking technique for copyright protection of satellite images using the fast Hadamard transform", in IGARSS'02, Toronto,Canada, June 2002.

42. A. T. S. Ho, J. Shen, and S. H. Tan, "A robust digital image-in-image watermarking technique for satellite images," in ICICS'01, Singapore, Oct. 2001.

43. Z. D. Wang, "New algorithm for the slant transform", IEEE Trans. Pattern Anal. Machine Intell., vol. pami-4, pp. 551-555, Dec. 1982.

44. Maurence M. Anguh and Ralph R. Martin. "A Truncation Method for Computing Slant Transforms with Application to Image Processing", IEEE Transaction on Communications, vol. 43, NO. 6 June 1995.

45. S. Agaian, К. Tourshan, J.P. Noonan, "Generalized Parametric Slant-Hadamard Transform," Signal Processing, vol 84, issue 8, August, 2004', 1299-1306.

46. S. Agaian, K. Tourshan,. J.P. Noonan, "Parametrization. of Slant-Haar transforms," IEE Proc. Vis. Image Signal Process vol 150, No. 5, 2003, pp. 306-311.

47. B.J. Pino, V.R. Algazi, "Slant Haar transform," Proceeding of the: IEEE, vol. 62, is. 5. May 1974, pp. 653-654.

48. J:Xie,, S. Agaian, J. Noonan; "Digital watermarking in. parametric; slant transform domain," Proc. of SP IE on.Multimedia on Mobile Devices, vol. 6821, pp. 6821OC-6821OC-8, 2008.

49. И. Добсши. Десять лекций по вейвлетам. Пер; сангл. — Ижевск, НИЦ регулярная и хаотическая динамика, 2001.

50. Daubechies. Recent Results in. Wavelet Applications. — Proceedings of SPIE Aerosense Symposium, 1998, pp. 23-31.

51. Daubeches. Ten Lectures on Wavelets. — MIAN, Philadelphia, 1992. 53.1. Daubechies. The wavelet transform, time-frequency localization and signal analysis.—IEEE Trans. Inf. Theory, vol. 36 (1990), pp. 961-1005.

52. A. Louis, P. Maas, A. Reider. Wavelet Theory and Applications. —John Wiley & Sons, 1997. .

53. W. Sweldens. The Lifting Scheme: A Construction of Second Generation Wavelek — SIAM J. Math. Anal, vol: 29 (1997), №. 2, pp. 511-546.

54. W. Sweldens. The Lifting Scheme: A new Philosophy in Biorthogonal . Wavelet Constructions. In Wavelet Applications in Signal: and Image Processing HE — Proc. SPIE 2569,1995, pp. 68-79.

55. W. Sweldens. Wavelets and the lifting scheme: A 5 minute tour. Zeitschrift für Angewandte Mathematik und Mechanik, vol. 76 (Suppl. 2) (1996), pp. 41-44.

56. W.: Sweldens. Wavelets: What Next? — Proceedings of the IEEE, vol. 84 (1996), № 4, pp. 680-685. , ' '

57. W. Sweldens, I. Daubechies. Factoring Wavelet Transforms-into Lifting Steps. — Fourier, Anal; Appl-., voL 4 (1998), Ж 3; pp; 247^-269.1

58. W. Sweldens, R. Pissens. Wavelet Sampling Techniques. — Proceedings of the Statistical Computing Section, American Statistical Association, pp. 20—29, 1993.

59. W. Sweldens, P. Schroder. Building your own Wavelets at Home (in Wavelets in Computer Graphics). — ACM SIG-GRAPH Course Notes, 1996, pp. 15-87.

60. C. Chui. A Tutorial in Theory and Applications. — Academic Press Inc., 1992.

61. Блаттер К. Вейвлет-анализ. Основы теории. Москва, 2004. — 280 с. ISBNI5.94836-033-4.

62. Новиков И.Я.,-Протасов В.Ю., Скопина М.А. Теория всплесков. М.: ФИЗМАТЛИТ, 2005. - 616 с. - ISBN 5-9221-0642-2.

63. Чуи Ч. Введение в вэйвлеты: Пер. с англ. М.: Мир, 2001. - 412 е., ил.1.BN 5-03-003397-1.

64. Mallat S., Multiresolution approximation and wavelet orthonormal basis of LA2(R) // Trans. AMS. Vols 315. - 1989: - P. 69-87.

65. Новиков- JI.В. Спектральный анализ сигналов в базисе вейвлетов // Научное приборостроение; 2000. Т. 10. - № 3. - С. 70-76.

66. Столниц Э., ДеРоуз Т., Салезин Д. Вейвлеты в компьютерной графике: Пер. с англ. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002, 272 стр.

67. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. СПб: ВУС, 1999.

68. Толковый словарь по вычислительным системам- / Под ред. В. Иллингуорта и др.: Пер с англ. М.: Машиностроение, 1989.

69. Steven W. Smith The Scientist and Engineer s Guide to Digital Signal Processing. Second Edition. California Technical Publishing San Diego, California, 1999.

70. Солонина А.И., Улахович Д.А., Яковлев Л.А. Алгоритмы и процессоры цифровой обработки сигналов. — СПб.: БХВ-Петербург, 2002. 464 е.: ил.

71. Hennessy J.L. and Patterson D.A. (1990) Computer Architecture: A Quantitative Approach. San Mateo CA: Morgan Kaufman^

72. Berkeley Design Technology (1999) Buyer's Guide to DSP Processors. Fremont CA.: Berkeley Design Technology Inc. Подробности, см. на www.bdti.com.

73. Blalock G. (1997) General-purpose pPs for DSP applications: consider the trade-offs. EDN, 23 oktober, pp. 165-172.

74. Hacker S. (1999) Static superscalar design: a new architecture for the

75. TigerSHARC DSP processor. Analog Devices Whitepaper.1www.analog.com/publications/whitepapers/products/sharc.html.

76. Levy M. (1999) DSP architecture directory. EDN, 15 April, pp. 67-102.

77. Texas Instruments (1988) TMS320C2x Software Development system User's Guide. Dallas TX: Texas Instruments.

78. Hayes J.P. (1998) Computer Architecture and Organization, 3rd edn. Boston MA: McGraw-Hill.

79. Куприянов M.C., Матюшкин Б.Д. Цифровая обработка сигналов: процессоры, алгоритмы, средства проектирования. СПб.: Политехника, 1999:t

80. Stone H.S., Kogge P.M. A parallel algorithm for the efficient solution of a general class of recurrence equations // IEEE Trans, on Comput. 1973. — V. C. 22, №8. -P. 386-392.

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

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

83. Прэт У. Цифровая обработка изображений, в двух книгах. Книга 1: Пер. с англ. / Под ред. Д.С. Лебедева. М.: Мир, 1982. — 311 с.

84. Ильин В. А., Позняк, Э. Г. Линейная алгебра. 4-е изд. М: Наука, 1999. ? Стр. 158. .

85. Ромм Я.Е., Забеглов В.В. Пилообразное преобразование в параллельной; iформе. // Изв. ЮФУ. Технические науки. 2008. -№11. - 51-56.

86. N. Ahmed, MIC. Chen, "A Cooley-Tukey Algorithm* for Slant, Transform,"- Int. Jour. Of Computer Mathematics, vol.5, issuel-4, 1976, pages 331-338.

87. S 92.arXiv:quant-ph/0201120vl 26Jan 2002i 93.POMM Я.Е., Забеглов B:B. Параллельные схемы преобразований Уолша и

88. V Хаара / ТГГ1И. Таганрог, 2008. - 29 с. - Дет в ВИНИТИ 30.09.2008, №783i В2008.

89. Ромм Я.Е., Забеглов В.В. Параллельное преобразование Уолша. Вестникi ТГПИ. Физико-математические и естественные науки. № 1. 2009. С. 115 121. . ;"■•.

90. Ромм Я.Е. Локализация и устойчивое вычисление нулей многочлена на1., основе сортировки: П //Кибернетика и; системный анализ. — 2007. — № 2. С.1.. 161-1741 '

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

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

93. Смоленцев Н.К. Основы теории вейвлетов. Вейвлеты в MATLAB. М.: ДМК Пресс, 2005. - 304 е., ил.

94. Ромм Я.Е., Забеглов В.В. Параллельные алгоритмы быстрого вейвлет-преобразования / ТГПИ Таганрог, 2009. - 17 с. - Деп. в ВИНИТИ 16.09.2009, №564 - В2009.

95. Ромм Я.Е., Забеглов В.В. Параллельные схемы Уолша, Хаара, Фурье и быстрого вейвлет-преобразования / ТГПИ — Таганрог, 2010. — 26 с. Деп. в ВИНИТИ 01.06.2010, №327 - В2010.

96. Ромм Я.Е., Забеглов В.В. Преобразование Хаара в параллельнойформе. VIII Всероссийская научно-техническая конференция «Современные методы и средства обработки пространственно-временных сигналов». Пенза. -2010.-С. 20-22.

97. Piotr Porwik, "Efficient algorithm of affine form searching for weakly specified Boolean function", Fundamenta Informaticae 77 (2007) 277-291 IOS Press.

98. Zhen James Xiang and Peter J. Ramadge, "Morphological wavelet transform with adaptive dyadic structures" in IEEE International Conference on Image Processing, 2010. >

99. Ahmed, N., Natarajan, Т., and Rao, K.R.: Cooley-Tukey type Algorithm for the Haar Transform. Electronics Letters 9 (1973) 276-278.

100. Ромм Я.Е., Забеглов В.В. Моделирование дискретного преобразования Фурье на основе кусочно-полиномиального вычисления базиса / ТГПИ — Таганрог, 2010. 21 с. Деп в ВИНИТИ 28.01.2010, № 60 - В2010

101. Ромм Я.Е., Забеглов В.В. О параллельной, форме дискретного преобразования Фурье Известия ЮФУ. Технические науки. 2010. — № 5. — С. 127-134.

102. Ромм Я.Е., Забеглов В.В. Дискретное преобразование Фурье с логарифмической временной сложностью на основе редукции тригонометрического аргумента // Обозрение прикладной и промышленной математики.-Т.17.-Вып.4,-2010. С. 512-513.

103. Ромм Я.Е., Забеглов В.В. Параллельные схемы некоторых дискретных ортогональных преобразований // Автометрия. — 2010. №6.

104. С.К. Chui, J.Z. Wang. On compactly supported spline wavelet and a duality principle // Transaction of the AMS, 1992, v. 330, p. 903-915.i