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

064618646 На правах рукописи

Забеглов Валерий Валерьевич

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

Специальность:

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

2 3 ДЕК 2010

ТАГАНРОГ 2010

004618646

Работа выполнена в ГОУВПО «Таганрогский государственный педагогический институт».

Научный руководитель: доктор технических наук,

профессор Ромм Яков Евсеевич

Официальные оппоненты: доктор технических наук,

профессор Турулин Игорь Ильич

кандидат технических наук, старший научный сотрудник Станишевский Олег Борисович

Ведущая организация: ФГНУ НИИ «СПЕЦВУЗАВТОМАТИКА»

Защита состоится « 29 » декабря 2010 г. в 14.20 на заседании диссертационного совета Д 212.208.21 Южного федерального университета по адресу: г. Таганрог, пер. Некрасовский, 44, ауд. Д- 406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан « ш » ияД-й^А 2010 г.

Просим Вас прислать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу: 347928, ГСП-17А, Ростовская область, г.Таганрог, пер. Некрасовский, 44, диссертационный совет Д 212.208.21.

Ученый секретарь диссертационного совета Д 212.208.21 доктор технических наук, профессор

Чернов Н.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В настоящее время интенсивно развиваются исследования в области ортогональных преобразований (ОП) для цифровой обработки сигналов (ЦОС). ОП используются для обработки сигналов, представляющих сейсмические, акустические, биомедицинские данные, а также данные обработки изображений, речевых сигналов, анализа и проектирования систем связи и др. К наиболее часто применяемым относятся преобразования Фурье, Хаара, Уолша, а также вейвлет- и пилообразное преобразования. При этом актуальны задачи сокращения времени и объёма вычислений в процессе выполнения преобразований. В частности, при обработке изображений возникают трудности, связанные с тем, что изображение представляется двумерным массивом, содержащим большой объем информации. Изображение часто выступает как особый сигнал, предназначенный для визуального восприятия, требуется, чтобы обработка выполнялась в реальном масштабе времени. Проблема снижения временной сложности пилообразного преобразования обусловлена тем, что оно применяется для выделения характерных признаков изображений, с помощью этого преобразования обеспечивается высокая степень концентрации энергии изображения, помимо того, оно используется для обработки водяных знаков и кодирования сигналов. Преобразование Уолша ориентировано на цифровую обработку сложных сигналов, на применении которых основана технология кодового разделения каналов для сотовой связи третьего и четвертого поколений. Наличие многоканальное™ наряду с обработкой сложных сигналов обусловливает необходимость сокращения времени преобразования. Вейвлет-преобразование является базовой техникой компьютерной графики, используется при редактировании и сжатии изображений, поиска изображений по запросу, автоматического контроля уровня детальности при редактировании и создании кривых и поверхностей по контурам, в быстрых методах решения задач физического моделирования в анимации и глобальном освещении. Отсюда актуальна задача снижения временной сложности вейвлет-преобразования. Для современных цифровых систем передачи, синтеза речи, верификации, в которых используются алгоритмы дискретного преобразования Фурье (ДПФ), требуется осуществлять распознавание слов, словосочетаний и фраз в реальном масштабе времени. Аналогичные требования предъявляются для ЦОС в системах радио- и гидролокации, а также в синтетической телефонии. Алгоритмической основой построения таких систем является цифровой динамический спектральный анализ, который позволяет получать оценку текущего спектра сигнала в реальном масштабе времени. Динамический спектральный анализ в различных частотных диапазонах одного и того же сигнала дает возможность наблюдать спектр как во всем частотном диапазоне (панорамный режим), так и детальный анализ спектра в выбранных частотных диапазонах. Это влечет необходимость выполнять ОП при условии динамического изменения числа отсчетов в строго ограниченное время или в режиме реального времени, поэтому схемы вычисления ОП должны быть минимизированы по временной сложности. Таким образом, тема работы актуальна.

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

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

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

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

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

O(log2log2w) и o(l) для формирования матрицы в реальном времени при динамическом изменении числа отсчетов.

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

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

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

7. На основе кусочно-полиномиальной аппроксимации элементов базиса и редукции аргумента синтезировать параллельный алгоритмы вычисления базиса ДПФ за время o(l) и выполнения преобразования за время o(iog2,v) при динамическом изменении отсчетов.

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

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

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

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

выполнять преобразование в режиме реального времени при динамическом изменении отсчетов.

2. Предложены параллельные схемы вычисления функций Радемахера с использованием схем Стоуна с временной сложностью o(iogjA') при количестве процессоров N2 и кусочно-полиномиальной аппроксимации тригонометрических функций - с временной сложностью о{\) при количестве процессоров ,vlog, N, которые улучшают известные оценки за счет увеличения числа процессоров и объема постоянной памяти.

3. На основе предложенных схем вычисления функций Радемахера разработаны алгоритмы построения матрицы преобразования Уолша с временной сложностью о (log 2 log 2 Л') при количестве процессоров n1 log, n и о( i) - с

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

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

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

5. Предложены две модификации быстрого вейвлет-преобразования, первая из которых позволяет параллельно вычислять все коэффициенты вейвлет-преобразования за время o(iog2log2A'xiog2,v) при количестве процессоров N3;

вторая позволяет подмножество коэффициентов, определяемое конкретным разрешением, вычислять за время o(l) при количестве процессоров l*n , где l -длина вейвлет-фильтра, что улучшает известные оценки алгоритма Малла и позволяет выполнять вейвлет-преобразование в реальном времени при динамическом изменении отсчетов.

6. Разработано параллельное видоизменение преобразования Хаара, выполняемое с временной сложностью o(tog2/v)', которое включает динамическое

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

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

динамически меняющегося числа отсчетов и временной сложностью o[\o%2n) в

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

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

o(log2w), позволяющие выполнять преобразование в режиме реального времени при динамическом изменении отсчетов.

2. Предложены параллельные схемы вычисления функций Радемахера с использованием схемы Стоуна с временной сложностью о(log2//) и на основе кусочно-полиномиальной аппроксимации тригонометрических функций - с временной сложностью o(i) при количестве процессоров wiog2/V .

3. Синтезированы алгоритмы построения матрицы преобразования Уолша с временной сложностью o(log2log2//) при количестве процессоров N2 iog2 А' и о(\) -

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

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

выполнять преобразование в реальном времени при переменном количестве отсчетов за счет динамического пересчета матрицы преобразования.

5. Предложены две модификации быстрого вейвлет-преобразования, первая из которых позволяет параллельно вычислять все коэффициенты преобразования за время o(log3log2//xlog2 N) при количестве процессоров N3; вторая - позволяет

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

6. Разработано параллельное видоизменение преобразования Хаара, выполняемое с временной сложностью o(log2<v), которое включает динамическое

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

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

заданной границы погрешности вычислений.

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

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

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

Апробация работы были представлены на Всероссийской научно-технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, ЮФУ, 2008); Всероссийской научно-технической конференции с международным участием «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, ЮФУ, 2009); XIII Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов» (ВК-95-90) (Пенза, ПДЗ, Пензенская государственная технологическая академия, 2010); VIII Региональной научно-практической конференции «Аспекты модернизации образования и развития промышленности» (Таганрог, ДГТУ, 2010); XI Всероссийском симпозиуме по прикладной и промышленной математике, осенняя открытая сессия (Сочи-Дагомыс, 2010).

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе излагаются схемы параллельного выполнения пилообразного преобразования, которое записывается в виде

dn=sn*xn, (1)

£>^' = [0(0), о(1).....£>(лг-1)] - вектор коэффициентов, Х;/ = [х(о), х(1),...,х(//-1)] -

вектор входной последовательности, - матрица, n х и, которая задаётся рекуррентной формулой

1 о

о

о

-Ь„ а„

О '(лг/2)-2

О

1 О - а„ Ь„ О

О -1

Ьп а„

О

О

о

^N/2 0 „ 1 "1 1"

"о" Г%2 1 -1

п = n , (2)

где 1т - единичная квадратная клетка, т ут. Постоянные ак и ьк вычисляются по формулам:

£2,=1 , ьк

1 + 4 а!

или

а к =

. ак

2а

-1

, к = 1,2,..., ]о$2 N .

(3)

(4)

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

Первая схема вычисления коэффициентов строится с помощью схемы Стоуна. Из (3) исключается Ьк и производятся последовательно замены ск=а\,

Г 5 -4") (<7^-1>

^ =1+4ск, дк =</*<7*-1. Соотношение (3) принимает вид

Як Як-1

. 9о = 1'

д\ = 5. В силу рекуррентности

ч„

5 -41 (<?1

1 0 ) 2) . Схема вычисления строится

; о) ^

следующим образом. Сначала находятся все двоичные степени а2', 1 = 1,2,...,

2' йп-1, - а2° =а,...,а2' =(л2"'} , / = 1,2.....Г1о§2(«-1)1, где 1У1 -

наибольшее целое, не превосходящее с • Пусть

(5)

1082^-1) [о

!= > = \,'е=1'2.....

ыо I

Каждому I из (5) взаимно однозначно сопоставляется процессор с номером I. Процессоры, работая синхронно, параллельно найдут все степени матрицы с показателем е. При этом (-й процессор перемножает те и только те двоичные степени матрицы, перед показателем 2' которой в (5) а,= 1. С учётом того, что и = N, временная сложность датой схемы составит т(1о£г(м/2))=о(\о£2\о2,г{м/2)) • Формулы (4) позволяют по заданному номеру

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

В этой же главе строится схема параллельного формирования матрицы преобразования. Предполагается, что все значения (3-4) вычислены и априори заданы. По рекуррентности матрица sn из (2) представляется в виде произведения log2 N матриц

О

■Jn

Pn*

Рю 2 о'"

гщг

О О

о д о о о О О

О '•. о О О Р4 ООО

о s2 о о о

о о о

о

(6)

' д(о) ~ - x(o) ■

= S„x

d(n -1) x(N- l)

где рк - левая матрица в правой части (2). Произведение (б) с учетом внутренней

клеточной структуры вычисляется на Л'3'2 процессорах за логарифмическое от числа сомножителей количество шагов по схеме сдваивания, равное о{ь&2\оё2 л).

С другой стороны, элементы матрицы можно вычислить априори и хранить в памяти, затем посредством адресации к хранимым элементам считывать их из памяти с временной сложностью Т (,\'2)=о (1). В максимально параллельной форме собственно само преобразование (1) выполнимо с помощью схемы сдваивания парных произведений с временной сложностью Т(л/2 )= о(1с^2 N).

В главе предлагается еще один параллельный алгоритм выполнения пилообразного преобразования. Соотношение (1) с помошью (6) записывается в следующем виде

(7)

где SN из (б). Умножения матриц в (7), с учетом структуры sN из (6), выполняется последовательно справа налево. Каждое умножение вычисляется параллельно с помощью схемы сдваивания за время ty + 2tc, где ty - время умножения, tc - время

сложения, иными словами, за время o(l), результатом каждого такого умножения является матрица-столбец, которая в свою очередь умножается на следующую матрицу. Временная сложность схемы составляет t(sN/2 )■= 0(log2 N) • Таким образом, имеет место

Теорема 1. Пилообразное преобразование, ограниченное N членами, в условиях первой схемы можно выполнить с временной сложностью

т [n2 )=o(iog2 Л')+о (iog2 iog2 N), в условиях второй схемы данное преобразование

выполняется с оценкой г(5Л'/2 )=o(iog2 N).

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

rad(j,e) = sig"(sin{2Jr(?j), 6>с[о, >), j = 1,2,..., log2N (8)

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

sin^*-^) Зе[о, 0, вм-в, = \/N 1 = 0,1.....N-\ j =1,2,... ,log2N (9)

с временной сложностью т(ы\о%2 Л') = o(l). Иначе функции (9) и соответственно (8) можно вычислить с помощью полиномов Чебышева I н II рода т,{х) и и,{х) на основе рекуррентных соотношений:

r0(xi)=l>7i(x,.)=^. J' {/„(*,)= 1,^)= 2*,. j'

Зависимости (10) представляются в матричной форме

(TM(xt))(2xl (имЩ_(2х, -lVtfifoH

ITt(xi)J=l' oJU-.wJ'U.wJi'

с теми же начальными значениями, отсюда

(TM(*i)\ fa -iVfTlfe)) (UtM))_fa -lYf^ifc))

[т-д)Д| ojUwj'Uw ru 0JW> W J'

При помощи схемы Стоуна вычисление Jj для всех значений (, t = \,2,...,N ,

выполняется на o(n2) процессорах с временной сложностью o(iog2A'). Используя соотношения sin((2i + l);rt?,) = (-l)' r2£+1(sin(^,)), sin(2^,)=(-l)'"lcos(w9,)c/2i.,(sin(;!^/)) > cos((2£ + (-1)'cos(x8f) U2t(s'n(^i)) > cos(2i^)=(-jy r2,(sm(^)), функции %т{(Щ), ( = l,2,...,N, можно выразить через полиномы Чебышева. Отсюда с учетом (8), (9) вычисляется система функций Радемахера.

В итоге, по предложенным схемам пилообразное преобразование вычисляется в максимально параллельной форме, число процессоров в одних случаях линейно, в других квадратично зависит от числа отсчётов, - схемы разнятся по составу операций, их минимальная временная сложность o(log2 ,v). Временная

сложность второй схемы вычисления функций Радемахера, имеющей сложность o(log2Jv), существенно уступает первой, но в отличие от первой схемы сложности т(n log2 Л') = o(l) не требует затрат постоянной памяти.

Во второй главе излагается третья схема параллельного вычисления

. . лтГг-'-е,)

функций Радемахера. Она строится на основе соотношения rad{j, #/)=(-1) • ', <?, e[o,i), _/=',2,...,iog2л7, / = 0,1,...,//-I, достигая временной сложности T{N\og2N)=o{]). По значениям функций Радемахера (8) в точках 0 = 0,,

log 2 N »

¡ = 0J,...,N~l, Й,.-(?,_, = [го правилу wal{r,e)= П radii-''0°иJ) , где

j'i

гi - j -й разряд представления числа г в двоичной системе счисления, © - символ

поразрядного суммирования по модулю 2, вычисляются функции Уолша. Каждой такой функции с номером /-, г = 0,1,..., Л' - ], ставится в соответствие A'!og2 .V

процессоров, чтобы произведение при каждом 0 = 0, вычислялось по схеме сдваивания на mt^-log2/vj процессорах. Процессоры, работая параллельно по всем

г и i, перемножат функции Радемахера за время г(лг2 log 2 А' )= О (log2 log. N).

Последняя оценка может быть улучшена до о(l) с сокращением числа процессоров в o(log2<v), если вместо схемы сдваивания применить битовый счётчик числа отрицательных двоичных единиц - сомножителей.

Еще одна параллельная схема получится, если матрицу преобразования Уолша h„(n) вычислять непосредственно поэлементно. Пусть г, и v, цифры /-го разряда в двоичном представлении чисел г и v соответственно: r=kbi2N-\ г\о&2ы-г-г\ го)г. v = (viog2«-i l'iog2,v-2 - ^ vo)i ■ Элементы h^J матрицы Hw{n) имеют вид

logj N~ 1

Ai-v)=(-0 ; r = 0,l,...,w-l, v = Q,\,...,N-l , (11)

где Uo{r)=r\oiiN-\ > «IW = rlug2 A1-! + rb%2N-2 > M2 (r) = rlog2 ,V-2 + '"logz JV-3 > ■ • • ; " log2 N-l (r) = rl + 'o •

Все элементы (11) вычисляются параллельно, при этом суммы в показателях степени вычисляются по схемам сдваивания. Временная сложность данного варианта составит ?'(л'2 Jog2 Л' )- o(iog2 iog2 л?).

После вычисления всех элементов матрицы Hw(n) вычисляется собственно само преобразование b(n)=\/nhw(n)xX(n). Схема основана на естественном параллелизме и аналогична схеме пилообразного преобразования. С учетом логарифмической оценки умножения матрицы на вектор временная сложность схемы t(n2 log2 ,v)=0 (log2 log2 n). Таким образом, имеет место

Теорема 2. Преобразование Уолша, ограниченное n членами, можно выполнить параллельно с временной сложностью 7'(,v2log2A')=o(log2Л'), при этом матрицу преобразования- Hw(n) можно параллельно вычислить с оценкой

т (л'2 ¡og2 n )= о (log2 log2 n ).

В случае фиксированного n при каждом значении / в показателе степени (11) априори известны номер строки г, и номер столбца v, матрицы Hw{n) , поэтому априори можно вычислить их двоичное разложение, парные произведения u,{r)v,, а также сумму, задающую показатель. Отсюда все элементы h(™) можно найти

априори и записать в память компьютера. В этом случае время определения матрицы равно времени считывания o(i). Для переменного n оценки о(l) можно достигнуть на той же основе, применив счётчик одноразрядных единиц для вычисления суммы в показателе (II).

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

разложения с помощью алгебраических операций на основе свёртки по рекуррентным соотношениям:

в/-и = 2 К а},„+2к , ¿/-и = 8пау,и+и > (12)

II N

где {/;„} - масштабирующий фильтр масштабирующей функции, {§„} - фильтр вейвлета; [а^] - начальные коэффициенты разложения функции /(.<) для некоторого уровня разрешения у, которые предполагаются известными. Рассматриваются вейвлеты Добеши, в которых масштабирующий фильтр {а,;}- и фильтр вейвлетов {#,,} состоят из конечного числа ненулевых элементов (рис. I).

Рис. 1. Вейвлеты Добеши из 2,4 и 8 ненулевых элементов

Формулы вычисления коэффициентов (12), зафиксировав конкретное разрешение } = у0, можно представить в матричной форме. Первый шаг БВП:

"лн.1

1,2

а ле

Л- ■т

1,1

1.2

* . , N

70 'Т

=4г

ь2 >>3 и4 К 0 0 0 0

0 0 А, и2 К К Ь 0 0 0

Л/. 0 0 0 0 Й, *2

й й а &( SL 0 0 0 0

0 0 81 8г ё4 ё1. 0 0 0

а #4 и 0 0 0 0 «I £2.

а дг

я.т

а N ,

Л.у+1 а ^ ,

Л.Т+2

(13)

где n - целая степень по основанию два. В (13) матрица фильтров (МФ) имеет размерность NxN.Ua втором шаге БВП преобразованию подлежат элементы аЛ_и, ) = 1,2,..., N/2, и МФ имеет порядок N¡2 х ,\'/2 , в остальном все строится по схеме первого шага. Полное БВП заключается в вычислении наборов коэффициентов

с!ю_, к, которые итеративно определяются через , пока размерность МФ

будет не меньше длины фильтра, т.е. N¡2' > I..

Предложенная модификация БВП представляется в виде

= 22

r*Vi 0 0 "м2 0

0 1 0 0 'л/, о"

Х...Х 0 1

0 1

0 1 0 I

0 1

(И)

где [Лд] - вектор-столбсц входной последовательности, at0, dk, к = 1,2,...,i0 - серии вейвлет-коэффициентов, клетка ме имеет размерность N¡2'xn/2', i = o,l,...,f0-i, и является матрицей фильтров для конкретного разрешения у0 - е, все перемножаемые матрицы из (14), кроме [4], имеют размерность N*N. Первый алгоритм выполнения БВП строится следующим образом. Сначала вычисляется матрица преобразования, обозначаемая [р], т.е. произведение матриц, содержащих клетки М/, из правой части (14). Умножение производится с помощью схемы сдваивания с учетом клеточной структуры. Временная сложность схемы составит r(A,3)=o(iog2log2A'x iog2/V). Затем на основе схемы сдваивания вычисляются наборы вейвлет-коэффициентов [/'Мл] с временной сложностью t(n2)=o(iog2w). Второй алгоритм заключается в последовательном умножении справа налево матриц из (14), при этом каждое умножение выполняется в параллельной форме. Временная сложность схемы составит т(1уn)=o(log2,v), где l - длина вейвлет-фильтра. Таким образом, для второго алгоритма имеет место

Теорема 3. Вейвлет-преобразование, где вейвлеты Добеши заданы парой фильтров {/!„} и {#„}, п =-!, 2,..., l, для коэффициентов ajq k, к = 1,2.....n , глубины

разложения (0, £0 <1о°2Л', может быть параллельно вычислено с временной

сложностью о (log г n).

С помощью схем на основе (14) можно вычислить преобразование Хаара с соответствующими оценками временных сложностей. Масштабирующий фильтр для матрицы Хаара состоит из двух ненулевых элементов ft, = l/>/2 , ft2 = 1/V2, фильтр

вейвлетов - g,= 1/V2, £2 = -1/1/2 . Предлагаемая схема параллельного вычисления преобразования Хаара r(/v)=l/Nh'(n)kX(n) включает алгоритм построения матрицы преобразования h'{n). Предполагается, что все степени vn и -2-"'2 при о<j<log2N вычислены априори и записаны в память компьютера. Первая строка матрицы заполняется единицами. Далее, каждому ненулевому элементу матрицы ставится в соответствие процессор, который считывает этот элемент из памяти. Элементом матрицы с индексами (г7 +п, 2m~J(n-\)+k) при \<n<2j, l<k<2"''J^ будет значение 2j/I, при 1<л<2', 2"'~J~i + l<k£2"'~J , - значение ~2J/1, все остальные элементы - нули. Количество процессоров равно числу ненулевых элементов.

Первая строка матрицы состоит из единиц, последовательно сверху вниз располагаются прямоугольные клетки с номерами у , у = 0,1,..., log2 ,v , размерность у -й из которых 2' х N , причем ненулевые элементы в такой клетке располагаются ступенчато так, что их число всегда равно числу столбцов n . Умножением на число клеток с учетом первой строки получится число ненулевых элементов матрицы, которое равно yv(log2W+1). Данный способ не требует вычислений, поэтому временная сложность заполнения матрицы составитг(/?)=о(1), R -- A;(log2,v+1).

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

меняется с учетом схемы сдваивания как у в первой строке и, далее, как jxjj без изменения внутри клетки с 2 > строками, где у1 = о, 1,..., log2 Л'-1 ■ Отсюда число

jj j Iog2 -MM, ,

сумматоров равно-+-Х £ 2J * —(l f log2 Л').

2 2 j-Q 2J 2

Теорема 4. Преобразование Xaapa, ограниченное N членами, можно выполнить параллельно с временной сложностью т(к)=о{ 1<^2лг),.где количество

процессоров r = n[log2,v+l) требуется при параллельном считывании из памяти всех элементов матрицы преобразования за время o(l).

Без учета произведений, в которые входят нули, потребуется A'-(iog2A' +1) процессорных элементов, временная сложность схемы составит r(OTog2//)=0(log2Jy).

Входная

последовательность

Г *(о) 1

А-(1)

Н X(N-2) x{N-1)

Динамический пересчет матрицы преобразования Л ^ в ортогональном базисе при переменном N

Ортогональное преобразование

АкгХХкг

Рис. 2. Матричная схема ортогональных преобразований при динамическом изменении отсчетов

Предложенные видоизменения преобразований Уолша, Хаара, а также ВВП на основе вейвлетов Добеши согласно утверждениям теорем 2-4 инвариантны относительно м , поэтому применимы при динамическом изменении отсчетов (рис. 2).

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

[Щ|=и1'А|)и[»м.'Д *1+\-*> ='//'. < = 0,1,...,/>-1. (15)

i-0

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

/(jt) = sin(;rx), хе[0л]. (16)

С этой целью для каждого отдельно взятого подынтервала из (15) строится интерполяционный полином Ньютона степени «, где п выбирается минимальным для достижения заданной точности приближения одновременно на всех подынтервалах. Полином Ньютона преобразуется путем приведения подобных так, что на i -м подынтервале принимает канонический вид:

P„(x)=a0l + aux+a2ix2 +..ла„,х", хе[х(>*(+1), i = 0J,...,P-l , (17) Построение (17) выполняется для всех Р подынтервалов при условии

|sm(^jr)-P„(i)j<E, ie[ii,J(H|), i = 0,\,...,P-\ . (18)

В (17) п выбирается минимально возможным, одинаковым для всех подынтервалов. При таком п для функции (16) и для каждого подынтервала из (15) набор коэффициентов в (17) записывается в память машины и хранится в ней. Для вычисления функции дешифруется номер подынтервала /, его значение служит адресом выборки коэффициентов (17). Если хе[г,,х1+1), то i = int(x/tf), где

Я = 1 - , int - целая часть числа. Порядок времени дешифрации оценивается как единичный. Если для рассматриваемой функции вычислить и хранить коэффициенты для всех 2* подынтервалов, то в дальнейшем время вычисления функции зависит только от степени полинома (17). По схеме Горнера значение этого полинома вычисляется за время t(l)=n(ty + tc), где ty, tc - время бинарного

умножения и сложения соответственно. Поскольку п в дальнейшем остается фиксированным, «=const, то временная сложность вычисления функции (16) при любом выборе аргумента составит <(i)=o(i).

Выбирается и фиксируется количество отсчетов N в ДПФ, для определённости предполагается, что N - целая степень двойки. По схеме кусочно-полиномиальной аппроксимации вычисляются значения (16) в точках x[j]=2j//n, j = о, 1,..., N/2 -1. Каждой точке x\j] с номером j ставится в соответствие процессор с таким же номером. Процессоры работают синхронно и независимо друг от друга.

Каждый процессор дешифрирует номер подынтервала )=itit(-^-|, в который

-Н )

попала точка x[j], затем считывает коэффициенты полинома (17), хранящиеся в памяти компьютера, по адресам (», ?), и с помощью схемы Горнера вычисляет значение функции в конкретной точке:

/(*[у])=(-(а„у*Ь']+а(Я-1)/)д:Ь']+<'(„-2)<)*[у]+-+ооу • Значения функции и её аргумента записываются в память в виде пары элементов (*{./]./(*[./])) последовательности, где у - номер ячейки. Временная сложность схемы вычисления (16) в точках *[]] с учётом наперёд вычисленных коэффициентов полинома Ньютона при л=сотш составит т{ы/2)=о(\).

Далее строится базис ДПФ, точнее, действительная, со${2тгпк/м), и мнимая, 5ш(2жпк/ы), части по значениям (¿[у],/(*[./])). Для построения используется формула редукции синуса:

8го(*) = (-1)ЛГ4<ги(*)8т(^-г), К = т1(|х|/тг), 2 = {|л|/яг}, (19)

где {л} обозначает дробную, ¡м(а) - целую часть числа а. Схема параллельного вычисления строится следующим образом. Каждой точке х[п,к]=2л-пк/А', /г = 0,1,...,Л'-!, А = 0,1,...,А'-1, ставятся в соответствие процессоры с индексами (М,р), р = 0,1,..., лг/2-1. Процессоры, работая параллельно, вычислят значения

параллельно дешифрируют адрес J\ по совпадению в двумерном массиве следующим образом:

у, =0,1,...,^/2-1, (20)

при этом в ячейке памяти с номером у, также хранится значение функции /(*[у,]).

ТГ I \К Г 1(2 хпк)/ы\* Далее вычисляются значения (-1) , К = >т| —--—1

I *

эти значения перемножаются в соответствии с формулой (19) (рис. 3).

/« „■ . . , ч

/Ш)

14

[\

Затем N/2 процессоров по значению г\п,к ]

= И (2япк/ы),

Рис. 3. Схема параллельного вычисления базиса ДПФ

Действительная часть строится аналогично мнимой, отличие заключается лишь в том, что в точке х[п,к]=2!гпк/ы значение cos(2япк/ы) вычисляется с помощью формулы приведения, т.е. из (19) редуцируется функция sin(л-/2-2япк/ы). Временная сложность схемы составит

7-(л-3/2)=о(1). (21)

Таким образом, имеет место

Теорема 5. Базис ДПФ вида cos(2xnk/N)-js'm(2xnk/N), n = 0,l,...,N-\, к-о, l,..., <v -1, можно вычислить с произвольно заданной априори границей погрешности с при помощи таблично-алгоритмической схемы вычисления функций на основе интерполяционного полинома Ньютона и формулы редукции (19) на //3/2 процессорах с временной сложностью o(l), иными словами, вычисление выполнимо с единичной оценкой времени (21).

Поскольку левая и правая части равенства (20) вычисляются по разным алгоритмам, то точное равенство (20) не обязательно будет выполнено, мантиссы чисел могут принимать разные значения, равенство следует заменить приближенным. Трудность адресации можно обойти, заменив (20) на неравенство ]-z[n,ii3|<2\ j, =0, i,..., лг/2-1 , где £ определяется как априори заданная

граница погрешности, которая должна быть строго меньше половины расстояния между отсчетами x[j]=2j/N, у = 0, l,..., N/2-l функции (16). Границу можно задать, например, как /ы , поскольку в этом случае ?<i//V = (jr[y+i]-.r[y])/2.

Данную схему можно модифицировать с целью сокращения числа процессоров. По-прежнему параллельно вычисляются значения функции (16) в точках x[j]=2j/N, у = о, 1,-..., N/2 -1, но эти значения записываются в одномерный массив f{x[j]). Каждой точке х[п,к)=2жпк ¡N , n = %\,...,Nfc = 0,1,... ,N-\, ставится в соответствие процессор с индексами (п,к). Процессоры, работая

параллельгго, вычислят значения z[n,k\=j-^7tnk^lVH=|. Затем каждый

процессор независимо от других и синхронно с ними дешифрируют адрес у, в массиве по формуле

y, = mt(z[«,i]^/2), (22)

затем считывает значение функции f(x[j^. Далее процессор вычисляет значения

(-1)*, К = int К2 ? и *Мj_j и sign{iTtnk/n), затем перемножает их в

соответствии с (19). Действительная часть вычисляется аналогично. В результате число процессоров сократилось в N раз при сохранении временной сложности:

r(w2)=o(l).

1 AM 1 N-]

Последующее ДПФ Re(x(*))= — X>(«)cos(2Tr/jA/iV), Im(*(*))=-— 5>(fi)sin(2i™i/iV) с

N //=0 N n=0

использованием схемы сдваивания выполняется с оценкой o(log2w).

Теорема 6. В условиях теоремы 5 базис и собственно ДПФ, ограниченное n членами, можно вычислить с произвольно заданной априори границей погрешности е на основе таблично-алгоритмической схемы и схемы сдваивания с применением модификации (22) с временной сложностью т(л,2)= о(\о%2 /V).

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

В каждой из трех глав даны сравнения результатов с известными, которые ниже сведены в одну таблицу (результаты автора отмечены символами *)):

Таблица 1

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

Число процессоров Временная сложность

Пилообразное преобразование

*) 1-й предложенный алгоритм при динамическом изменении числа отсчетов о(я2) о{\о%2ы)

*) 2-й предложенный алгоритм при динамическом изменении числа отсчетов о{м)

Алгоритм типа Кули-Тьюки с фиксированным числом отсчетов не приведено о(лПоа2АГ ]

Метод усечения с фиксированным числом отсчетов не приведено о{ы)

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

Преобразование Уолша

*) Предложенный алгоритм (включает вычисление матрицы преобразования при динамическом изменении числа отсчетов) оИ О(1о82Л')

Параллельный алгоритм на основе квантовых вычислений с фиксированным числом отсчетов о(л-) о{\0ё2м)

Быстрое преобразование Уолша с фиксированным числом отсчетов не приведено о(мог2м)

Эффективный алгоритм аффинной формы без динамического изменения числа отсчетов не приведено о{тоё2м)

Быстрое вейвлет-преобразование

*) 1-й предложенный алгоритм (включает вычисление матрицы преобразования) при динамическом изменении числа отсчетов

*) 2-й предложенный алгоритм преобразования при динамическом изменении числа отсчетов о{ы) О^ОЕзЛ')

Алгоритм Мала без динамического изменения числа отсчетов не приведено o{N\o%гN)

Преобразование Хаара

*) Предложенный алгоритм при динамическом изменении числа отсчетов о{ь$2ы)

Алгоритм Эндрюса с фиксированным числом отсчетов не приведено о(лг)

Алгоритм Кули-Тьюки с фиксированным числом отсчетов не приведено

Дискретное преобразование Фурье

*) Предложенная параллельная схема ДПФ на основе кусочно-полиномиальной аппроксимации и редукции синуса (с дешифрацией базиса за время 0(1) при динамическом изменении числа отсчетов) <?И о(1оё2//)

Параллельная схема ДПФ с вычислением базиса на основе схемы Стоуна (с вычислением базиса за время О (log,//) при динамическом изменении числа отсчетов) оИ O(log2*)

Параллельная схема ДПФ с вычислением базиса на основе кусочно-полиномиальной аппроксимации (с вычислением базиса за время 0(l) при переменном числе отсчетов) о(л0 O(log2tf)

Параллельная схема ДПФ на основе квантовых вычислений (без учета вычисления базиса и изменения числа отсчетов) o(N) О (log 2 Л^)

Как видно из табл. 1, временные оценки предложенных схем положительно отличаются от известных целом или же в части вычисления базиса.

Основной результат диссертационной работы заключается в построении динамически распараллеливаемых схем выполнения пилообразного преобразования, преобразований Уолша и Хаара, быстрого вейвлет-преобразования и ДПФ при условии динамического изменения числа отсчетов с минимизацией временной сложности до о[\о$гы) путем параллельного пересчета элементов базиса для

переменного значения N.

Список опубликованных работ по теме диссертации в изданиях ВАК

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

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

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

4. Ромм Я.Е., Забеглов В.В. Параллельные схемы некоторых дискретных ортогональных преобразований // Автометрия. - 2010. - Т. 46. - № 6. - С. 54 - 70

Основные публикации по теме работы

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

6. Ромм Я,Е., Забеглов В.В. Параллельные схемы преобразований Уолша и Хаара / ТГПИ. - Таганрог, 2008. - 29 с. - Деп. в ВИНИТИ 26.02.2009, №106 -В2009.

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

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

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

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

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

Личный вклад автора в работах, написанных в соавторстве, состоит в следующем [1,4,9] - разработка схем параллельного выполнения пилообразного преобразования; [5,6, 9, 10] - синтез распараллеливаемых алгоритмов и оценки временной сложности преобразований Уолша и Хаара; [7,9,12] - разработка схем и оценки временной сложности параллельного выполнения быстрого вейвлет-преобразования; [2,3,8,9] - синтез параллельного алгоритма ДПФ на основе кусочно-полиномиальной аппроксимации элементов базиса и редукции аргумента.

Соискатель Забеглов В.В.

Тип.ТТИ ЮФУ Заказ экз.

ВВЕДЕНИЕ.

ГЛАВА 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

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