Алгоритм параллельного вычисления быстрого преобразования Фурье для сигнальных процессоров

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

Рубрика Программирование, компьютеры и кибернетика
Вид дипломная работа
Язык русский
Дата добавления 09.04.2022
Размер файла 3,2 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.Allbest.Ru/

Выпускная квалификационная работа

Тема:

Алгоритм параллельного вычисления быстрого преобразования Фурье для сигнальных процессоров

Реферат

Выпускная квалификационная работа содержит (без учета разделов в приложениях) 110 с., 39 рис., 50 табл., 4 прил. Использовано 46 источников.

Ключевые слова: дискретное преобразование Фурье, быстрое преобразование Фурье, БПФ, ДПФ, параллельное программирование, корреляционный анализ, спектральный анализ, частотно-временной корреляционный анализ, цифровая обработка сигналов, оптимизации, ЦП, многоядерные процессоры.

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

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

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

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

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

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

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

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

Обозначения и сокращения

БПФ - быстрое преобразование Фурье; ВКФ - взаимно-корреляционная функция;

ГП - графический процессор;

ДПФ - дискретное преобразование Фурье; НИР - научно-исследовательская работа; НР - научный руководитель;

ОБПФ - обратное быстрое преобразование Фурье; ОС - операционная система;

ПО - программное обеспечение; ПФ - полосовой фильтр;

ЦОС - цифровая обработка сигналов; ЦП - центральный процессор;

ЧВ ВКФ - частотно-временная взаимно-корреляционная функция.

Оглавление

  • Введение
    • 1. Алгоритмы спектрального и частотно-временного корреляционного анализа
      • 1.1 Спектральный анализ
        • 1.1.1 Ряды Фурье
        • 1.1.2 Дискретное преобразование Фурье
        • 1.1.3 Быстрое преобразование Фурье
        • 1.1.4 Алгоритм Кули-Тьюки
        • 1.1.5 Алгоритмическая реализация обработки сигналов при решении задачи обнаружения утечек
        • 1.1.6 Функции когерентности
      • 1.2 Частотно-временной корреляционный анализ
    • 2. Исследование и оптимизация алгоритмов спектрального и частотно-временного корреляционного анализа
      • 2.1 Исследование быстрое преобразование Фурье
        • 2.1.1 Последовательная реализация быстрого преобразования Фурье
        • 2.1.2 Реализация быстрого преобразования Фурье на параллельной архитектуре путём распараллеливания обхода рекурсии в ширину
        • 2.1.3 Анализ эффективности распараллеливания быстрого преобразования Фурье
        • 2.1.4 Вычисление обратного преобразования Фурье через прямое быстрое преобразование Фурье
      • 2.2 Исследование взаимнокорреляционной функции
        • 2.2.1 Последовательная и параллельная реализация расчёта взаимнокорреляционной функции
        • 2.2.2 Анализ эффективности распараллеливания взаимнокорреляционной
          • функции
      • 2.3 Исследование функций когерентности
        • 2.3.1 Последовательная и параллельная реализация расчёта функций когерентности
        • 2.3.2 Анализ эффективности распараллеливания функций когерентности
        • 2.3.3 Оптимизация работы с памятью при расчёте функций когерентности
      • 2.4 Исследование частотно-временных корреляционных функций
        • 2.4.1 Последовательная и параллельная реализация расчёта частотно- временных корреляционных функций
        • 2.4.2 Применение архитектурных и компиляторных оптимизаций к вычислению частотно-временных корреляционных функций
    • 3. Финансовый менеджмент, ресурсоэффективность и ресурсосбережение
      • 3.1 Оценка коммерческого потенциала и перспективности с позиции ресурсоэффективности и ресурсосбережения
        • 3.1.1 Потенциальные потребители результатов исследования
        • 3.1.2 Анализ конкурентных технических решений
        • 3.1.3 SWOT-анализ
      • 3.2 Определение возможных альтернатив проведения научных исследований
      • 3.3 Планирование научно-исследовательских работ
        • 3.3.1 Структура работ в рамках планируемого исследования
        • 3.3.2 График проведения научного исследования
        • 3.3.3 Бюджет научно-технического исследования
      • 3.4 Определение ресурсной (ресурсосберегающей), финансовой, бюджетной, социальной и экономической эффективности исследования
        • 3.4.1 Расчёт интегральных показателей финансовой эффективности
        • 3.4.2 Расчёт интегральных показателей ресурсоэффективности
        • 3.4.3 Расчёт интегральных показателей эффективности вариантов исполнения разработки
      • 3.5 Оценка научно-технического уровня научно-исследовательской работы
      • 3.6 Оценка экономического эффекта
    • 4. Социальная ответственность
      • 4.1 Производственная безопасность
        • 4.1.1 Анализ вредных производственных факторов и санитарных норм
        • 4.1.2 Анализ опасных производственных факторов
      • 4.2 Экологическая безопасность
      • 4.3 Безопасность в чрезвычайных ситуациях (техногенного, природного, социального характера)
      • Заключение
    • Conclusion
    • Список публикаций студента
    • Список использованных источников
    • Приложение А (Обязательное). Некоторые оконные функции
    • Приложение Б (Обязательное). Архитектурные и компиляторные оптимизации
      • Б.1 Архитектурные оптимизации
        • Б.1.1 Векторизация
        • Б.1.2 Упреждающее помещение данных в кэш первого уровня
        • Б.1.3 Уменьшение числа ветвлений
      • Б.2 Компиляторные оптимизации
    • Приложение В (Обязательное). Анализ эффективности распараллеливания вычисления частотно-временной корреляционной функции
    • Приложение Г (Обязательное). Application of time-frequency correlation analysis for leak detection
      • G.1 Time-frequency correlation analysis
        • G.2 Algorithm of the time-frequency correlation function acquisition
        • G.3 Informative assessment of time-frequency correlation function
        • G.4 The study of signals received during the leakage survey

Введение

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

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

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

Несмотря на принципиальную применимость метода для решения различных задач обнаружения утечек, качество их решения определяется эффективностью цифровой обработки сигналов. Данная работа посвящена исследованию, оптимизации и программной реализации алгоритмов спектрального анализа и вычисления частотно-временной корреляционной функции, обладающей рядом преимуществ, по сравнению с традиционными подходами, для корреляционной обработки акустических сигналов в рамках проекта РФФИ (№16-37-00049).

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

1.1 Спектральный анализ

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

1.1.1 Ряды Фурье

Любой ?? - периодический сигнал ??(??), изменяющийся во времени, может быть представлен в виде суммы постоянного члена и некоторого числа синусоидальных и косинусоидальных членов, имеющих частоты кратные ?? = 2 ??/??. Такое представление называется рядом Фурье и определяется следующим выражением [2]:

(1)

где коэффициенты ????, ?? = 0,1, …, ? и ????, ?? = 1,2, …, ? получаются из соображений попарной ортогональности функций sin(??????) и ??????(??????) на отрезке [0, ??] [2]:

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

(2)

(3)

В полученном представлении частоты ???? принято называть ?? ? ыми гармониками частоты ??. Следовательно, ряд (1) содержит зависящие от частоты синусоидальные и косинусоидальные члены с различными амплитудами ???? и ???? на положительных частотах гармоник ???? [2].

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

(4, 5)

После подстановки (4) и (5) в исходное выражение (1) и приведения подобных получено следующее выражение [1]

??(??) = ????????????????. (6)

Комплексные коэффициенты ???? могут быть определены из выражения (6) способом, использованным ранее:

(7)

В выражении (7) интегрирование осуществляется в диапазоне [???/2, ??/2], однако из свойств интегралов периодических функциях следует, что интегрирование может осуществляется на любом интервале длительностью в период, то есть [??0, ??0 + ??] при любом значении времени начала отсчета ??0 [12].

Следует обратить внимание, что в выражении (6) коэффициент ?? при члене ???? принимает как положительные, так и отрицательные значения, следовательно, половину ряда составляют отрицательные частоты ?????. Они в полной мере не имеют физического смысла и являются скорее математическим понятием, однако отрицательные частоты все же может быть интерпретированы как вращение с угловой скоростью ???? в направлении противоположном принятому за положительное [2]. Тем не менее, вследствие того, что амплитуды |????| равномерно распределяются между соответствующими положительными и отрицательными частотами, для определения реального значения амплитуды на частоте ???? необходимо удвоить рассчитанную величину [2]. Для того, чтобы перейти от формы (6) к сумме тригонометрических функций можно воспользоваться следующим выражением:

(8)

На практике, использование выражения (8) предпочтительнее, чем выражения (1). Это связано с тем, что последнее не обладает свойством инвариантности, то есть изменение начала отчета времени приводит к нетривиальному преобразованию коэффициентов ????, ????. Напротив, коэффициенты ???? в выражении (8) инварианты к выбору начала отсчета, следовательно, при наблюдении одного и того же сигнала будут получаться одинаковые значения коэффициентов [2].

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

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

Пусть сигнал ??(??) наблюдается на ограниченном отрезке [? ??/2; ??/2]. В таком случае, формулы преобразования Фурье совпадают с формулами для коэффициентов ???? ряда Фурье периодической функции, полученной продолжением на всю вещественную ось функции ??(??). Таким образом, формула прямого дискретного преобразования Фурье может быть получена из (7), путем замены интеграла суммой в соответствии с методом прямоугольников [2]

(9)

где ?? - количество временных отсчетов; ??/?? = ??0 - интервал дискретизации. С учетом того, что ?? = 2??/??, выражение может быть переписано следующим образом

(10)

Если ???? = 0 при |??| > ??/2, обратная формула имеет вид

(11)

Таким образом, (10) и (11) - прямое и обратное преобразования Фурье соответственно. Последовательность |????| называют амплитудным дискретным спектром временного ряда ???? [2].

Другой распространенной формой записи формул ДПФ является запись через поворачивающий множитель

(12)

Используя (12), можно переписать (10) и (11) как

(13)

(14)

Несмотря на то, что ДПФ связано с приближенным вычислением коэффициентов ряда Фурье, оно обладает свойством взаимной однозначности образа и оригинала. Среди других свойств ДПФ - ??-периодичность последовательностей ???? и ????, что позволяет производить в (9) и (10) суммирование по любым последовательным ?? отсчетам [2].

При неправильном выборе частоты дискретизации сложного сигнала наблюдается явление растекания спектра [1]. Взвешивание окном уменьшает утечку ДПФ за счёт уменьшения уровня боковых лепестков [3]. Различные взвешенные оконные функции приведены в приложении A.

1.1.3 Быстрое преобразование Фурье

В связи с тем, что вычисление ДПФ по формулам (10) и (11) требует большого количества операций, широко используется более эффективный с данной точки зрения подход, получивший название быстрого преобразования Фурье (БПФ). В его основу положен эффективный алгоритм расчета последовательности [2]

(15)

К вычислению последовательности с помощью (15) может быть сведено как прямое, так и обратное ДПФ. Из (13) и (15) видно, что если ???? = ????, то ????/?? = ????. Аналогично, из (14) и (15) следует, что если ???? = ??????? при ?? > 0 и ???? = ???? при ?? = 0, то ???? = ????.

Эффективная схема вычисления (15) реализуется через формулу, получившую название формулы Ланцоша - Даниэльсона [2]

, (16)

где ?? = 2??, ??' = ?? ? ??, а последовательности ??0, ??1 могут быть вычислены по следующей формуле [2]

(17)

Применение (16) позволяет свести задачу вычисления исходной последовательности к задаче вычисления двух вдвое меньших последовательностей, содержащих четные и нечетные члены исходной, что видно из (17). Рекуррентное применение (16), позволяет в конечном итоге, свести вычисление - точечной последовательности к вычислению ?? одноточечных и последующим многоэтапным расчетам по (16). При этом вычисление одноточечной последовательности фактически не требуется, так как ???? = ????.

Таким образом, прежде всего вычисление ДПФ по методу БПФ требует разбиения последовательности ????, имеющей ?? = 2?? членов, на ?? одноточечных последовательностей. Для этого, требуется ?? последовательных делений ???? по (16). В таблице 1 смоделирована данная процедура для ?? = 3 [2]. Связь индексов всех элементов в исходном и конечном массивах показана в таблице 2. Из таблицы 2 видно, что разбиение исходной последовательности на одноточечные сводится к перестановке элементов (операция «бит-реверсирование»), причем индекс элемента в выходном массиве получается путем «переворачивания» индекса данного элемента в исходном массиве. Далее происходят последовательные расчеты по (16) [2].

Таблица 1

Разбиение исходной последовательности для N = 8

Исходная последовательность

Этап разбиения

Первый

Второй

Третий

??0

??0

??0

??0

??1

??2

??4

??4

??2

??4

??2

??2

??3

??6

??6

??6

??4

??1

??1

??1

??5

??3

??5

??5

??6

??5

??3

??3

??7

??7

??7

??7

Таблица 2

Связь между индексами элементов (бит-реверсирование)

Элемент

Индекс в исходном массиве

Индекс в выходном массиве

??0

000 (0)

000 (0)

??1

001 (1)

100 (4)

??2

010 (2)

010 (2)

??3

011 (3)

110 (6)

??4

100 (4)

001 (1)

??5

101 (5)

101 (5)

??6

110 (6)

011 (3)

??7

111 (7)

111 (7)

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

1.1.4 Алгоритм Кули-Тьюки

Данный алгоритм отличают наглядность (схема производимых вычислений, может быть легко изображена графически), относительная простота и достаточно высокое быстродействие. Количественно быстродействие оценивается следующим образом - количество необходимых операций умножения для БПФ имеет порядок ?? log2 ??, в то время как для ДПФ - ??2. При ?? = 1024, алгоритм БПФ выполняется примерно в 208 раз быстрее, чем ДПФ [2].

Дополнительная минимизация вычислительных операций в алгоритме Кули-Тьюки при вычислении быстрого преобразования Фурье достигнута за счёт использования разбиения исходной анализируемой последовательности на две, более коротких (рисунок 1). При этом количество операций сокращается в два раза [4].

Рисунок 1 - Замена N-точного БПФ двумя N/2-точными БПФ

Необходимо отметить, что последующее разбиение полученных последовательностей возможно проводить до тех пор, пока число отсчетов в анализируемой выборке кратно 2. При N = 8 возможное разбиение представлено на рисунке 2 [4].

Операции объединения и разбиения проводятся в соответствии с сигнальными графами [3].

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

Рисунок 2 - Разбиение и объединение последовательности при N = 8

Рисунок 3. Сигнальный граф «бабочка» для 8-точечного БПФ с прореживанием по времени, входные отсчёты которого подвергнуты бит-реверсивной перестановке

На рисунке 3 цифрами в прямоугольниках показаны поворотные коэффициенты. Например, 0 в прямоугольнике значит W80.

Отметим, что в этом сигнальном графе на каждом вычислительном этапе повторяется одна и та же операция, которая в литературе носит название операция «бабочка» [5].

Обозначим верхний вход через x, нижний - через y, тогда верхний выход будет определяться выражением (18), а нижний - выражением (19).

*(18, 19)

Рисунок 4 - Операция «бабочка»

1.1.5 Алгоритмическая реализация обработки сигналов при решении задачи обнаружения утечек

Обнаружение утечки корреляционно-акустическим методом сводится к вычислению взаимной корреляционной функции сигналов, поступающих с датчиков. Блок обработки сигналов, на основании полученных данных осуществляется вычисление взаимной корреляционной функции (ВКФ) [6]

(20)

где ?? = ???/2, ?1,0,1 …, ??/2 - 1

Оценка запаздывания ?? определяется по максимуму взаимной корреляционной функции ??0 с использованием очевидного соотношения [6]

???0 = ??0 • ???. (21)

Размещено на http://www.Allbest.Ru/

Рисунок 5 - Схема обнаружения утечки корреляционно-акустическим методом

В соответствии с рисунком 9 расстояние от любого из датчиков до утечки (???? и ????) [1] определяется по формуле (22):

(22)

где ?? - скорость распространения сигнала по линейному участку трубопровода;

???? и ???? - расстояния от утечки до датчиков А и В соответственно; ?? - расстояние между датчиками.

Однако на практике, так как размер исследуемых выборок достаточно велик, использование (20) для вычисления корреляционной функции не является целесообразным. Очевидно, что реализация (20) требует умножения каждого отсчета последовательности ????, на каждый из отсчетов последовательности ????, то есть ??2 операций умножения [1]. Так как величина ?? оказывает влияние на точность обнаружения утечки, она является достаточно большой (имеет порядок десятков тысяч), что затрудняет расчет корреляции непосредственно.

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

(23)

где ???? - прямое дискретное преобразование Фурье (ДПФ); ?????1 - обратное ДПФ; ????? - комплексно-сопряженное представление результатов прямого ДПФ.

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

Рисунок 6 - Схема вычисления взаимной корреляции через БПФ

Основным преимуществом корреляционной функции ?????? (??) является удобство последующего анализа.

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

Описанный алгоритм схематически изображен на рисунке 6.

1.1.6 Функции когерентности

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

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

(24)

где ??(•) - оператор усреднения; ????(??), ???? (??) - собственные спектры сигналов ????(??) и ????(??) соответственно. Собственные спектры сигналов могут быть вычислены по следующей формуле:

(25)

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

(26)

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

????(??) = ????(????(??)) = ????(??) + ?? • ????(??),

????(??) = ????(????(??)) = ????(??) + ?? • ????(??),

где ????(??), ????(??) - вещественные составляющие спектров сигналов ????(??), ????(??);

????(??), ????(??) - мнимые составляющие спектров сигналов ????(??), ????(??). Далее произведем расчет знаменателя (26):

????(??) = ????(??) • ?????(??) = ????2(??) + ????2(??),

????(??) = ????(??) • ?????(??) = ????2(??) + ???? 2(??),

????(??)????(??) = ????2(??)????2(??) + ????2(??)????2(??) + ????2(??)????2(??) +

+ ????2(??)????2(??).

Аналогично, производится вычисление числителя (26):

?????? (??) = ????(??) • ?????(??) = (????(??)????(??) + ????(??)????(??)) + ?? • (????(??)????(??) ? ????(??)????(??)),

?????? 2(??) = ????2(??)????2(??) + ????2(??)????2(??) + ????2(??)????2(??) +

+ ????2(??)????2(??).

Несложно убедиться в тождественном равенстве единице отношения

?????? 2(??)

????(??)????(??) ? 1.

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

В литературе [1, 9] встречаются различные подходы к вычислению функции когерентности, отличающиеся способом усреднения значения в знаменателе. Наиболее распространенным в настоящее время является метод усреднения по Бартлетту [10], который описывается (26). С учетом введенных обозначений (26) можно привести к виду

. (27)

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

(28)

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

1.2 Частотно-временной корреляционный анализ

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

Для разрешения данной проблемы, в рамках научного коллектива автора, был разработан и зарегистрирован в качестве изобретения метод частотно-временного корреляционного анализа сигналов [12]. Особенностью метода является получение частотно-временных взаимнокорреляционных функций (ЧВ ВКФ), в явном виде содержащих информацию о степени коррелированности сигналов в различных частотных областях. Алгоритм получения ЧВ ВКФ приводится далее.

Пусть сигналы x(t) и y(t) представлены дискретными последовательностями x(ti) и y(ti) соответственно. На начальном этапе, в соответствии с Теоремой о корреляции [1], путём поэлементного перемножения отсчетов дискретного спектра сигнала y(ti) и результата комплексного сопряжения дискретного спектра сигнала x(ti) вычисляется кросс-спектр сигналов Sxy (k).

(29)

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

(30)

(31)

На заключительном этапе полученные векторы обратному дискретному преобразованию Фурье:

(32)

Полученный в результате (32) сложный вектор m состоит из M векторов, каждый из которых в свою очередь содержит все отсчеты ВКФ исходных сигналов x(ti) и y(ti) на m-ом частотном интервале. Путём простых преобразований из векторов m могут быть восстановлены значения ЧВ ВКФ:

(33)

Поскольку ЧВ ВКФ имеет два независимых аргумента, наиболее наглядным способом ее представления является поверхность, построенная в трехмерном пространстве.

В таком случае, признаком наличия утечки является присутствие выраженных пиков на поверхности

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

2.1 Исследование быстрое преобразование Фурье

2.1.1 Последовательная реализация быстрого преобразования Фурье

По алгоритму, описанному в пункте 1.1.4, разработана функция для вычисления прямого БПФ. Экспериментальные исследования проводились на трёх процессорах Intel: Core 2 Q6700, Xeon 5160, Core i5-750. В экспериментальных вычислениях размер выборки последовательности варьировался от 4 до 131072 отсчётов. Было произведено 1000 временных замеров 1000 преобразований БПФ. Поскольку существует множество факторов, в том числе псевдопараллельная работа планировщика процессов ядра ОС, обработка прерываний устройств, способных замедлить, но не ускорить проведение вычислительной операции [12, 13], для повышения достоверности за время выполнения принималось наименьшее время по выборке. Результаты приведены таблице 3.

Таблица 3

Результаты вычисления 1000 преобразований Фурье

Размер выборки

Intel Core 2 Q6700, c. (4 ядра)

Intel Xeon 5160, c. (2 ядра)

Intel Core i5 -750, c. (4 ядра)

4

0,00024075

0,00021465

0,00015828

8

0,00075717

0,00067474

0,00044916

16

0,00211405

0,0018886

0,00128905

32

0,00541865

0,00486566

0,00333004

64

0,01335926

0,01185663

0,00821746

128

0,03145305

0,02798085

0,01862822

256

0,07274957

0,06557836

0,04182029

512

0,16645052

0,15079034

0,09292365

1024

0,37508703

0,34058475

0,20636104

2048

0,83740993

0,76407335

0,448927

4096

1,84897964

1,6919186

0,97540429

8192

4,04408304

3,72334611

2,12225743

16384

8,79226033

8,13358534

4,60217241

32768

19,0863284

17,86104067

9,90601857

65536

41,35974078

39,62870942

21,21087834

131072

89,84323728

87,70679429

45,51673787

2.1.2 Реализация быстрого преобразования Фурье на параллельной архитектуре путём распараллеливания обхода рекурсии в ширину

В качестве инструмента параллельных вычислений в данной работе использована кроссплатформенная библиотека Intel® TBB, на основе которой в среде разработки Visual C++ 2015 создано программное обеспечение. Выбор этой библиотеки объясняется использованием вычислительных систем на базе ЦП Intel и AMD.

Для реализации параллельного вычисления БПФ использовался подход, заключающийся в распараллеливании метода обхода рекурсии в ширину при расчёте поворотных коэффициентов графа «бабочка». Основное преимущество такого подхода перед другими реализациями БПФ [14,15] очевидно и заключается в отсутствии необходимости проводить предварительный тест с целью определения оптимальных значений степеней детализации (grainsize) для различных выборок перед массивными математическими вычислениями.

Вычисление БПФ представлено в шаблоне библиотеки Intel TBB как логическая задача класса tbb::task, которая в свою очередь порождает другие вычислительные логические задачи в момент разбиения исходной анализируемой последовательности. После объединения последовательностей, соответственно созданные задачи уничтожаются.

Экспериментальные исследования были проведены на модельных примерах с размером выборки 4-131072 отсчётов. Массив входных данных состоял преимущественно из действительных чисел. Экспериментальные исследования проведены на трех процессорах фирмы Intel: Xeon® 5160, Core 2 Quad 6700, Core i5-750. В таблице 4 приведены временные результаты вычисления быстрого преобразования Фурье на многоядерных процессорах.

Таблица 4

Результаты параллельных вычислений 1000 преобразований Фурье

Размер выборки

Intel Core 2 Q6700, c. (4 ядра)

Intel Xeon 5160, c. (2 ядра)

Intel Core i5 -750, c. (4 ядра)

4

0,00056012

0,00029708

0,00017144

8

0,00084838

0,00075982

0,00043799

16

0,00225578

0,00194729

0,0010752

32

0,00570983

0,00492981

0,0028454

64

0,01372574

0,01199732

0,00738605

128

0,03214769

0,02807533

0,01685715

256

0,07459504

0,06530345

0,04056767

512

0,16966321

0,14892508

0,08994134

1024

0,23420794

0,19616322

0,13117278

2048

0,32721335

0,43127884

0,1904456

4096

0,71485054

0,93534788

0,42766034

8192

1,51241585

1,97059527

0,92581837

16384

3,18103463

4,27614957

1,87070088

32768

6,75964589

9,24869119

4,05282814

65536

14,34330215

20,55700017

8,36174447

131072

31,39113339

44,21680053

17,18434964

2.1.3 Анализ эффективности распараллеливания быстрого преобразования Фурье

В параллельном программировании для анализа эффективности распараллеливания существуют специальные показатели, такие как ускорение (8), эффективность использования (9) вычислительных ресурсов и накладным расходам (10) [17].

(35, 36, 37)

где p - количество вычислительных ядер;

T1 - время выполнения последовательного кода;

Tp - время выполнения параллельного кода.

Произведём расчёт показателей эффективности распараллеливания для реализации БПФ (пункт 2.1.2). Результаты вычислений приведены в таблицах 5-7.

Таблица 5

Показатели эффективности распараллеливания БПФ для ЦП Intel Core 2 Q6700

Размер выборки

Sp

Ep, %

T0, c.

4

0,42981861

10,74546526

0,00199973

8

0,892489215

22,31223037

0,00263635

16

0,937170291

23,42925729

0,00690907

32

0,949003736

23,72509339

0,01742067

64

0,9732998

24,33249501

0,0415437

128

0,978392227

24,45980567

0,09713771

256

0,975260151

24,38150378

0,22563059

512

0,98106431

24,52660774

0,51220232

1024

1,601512869

40,03782173

0,56174473

2048

2,559216884

63,9804221

0,47144347

4096

2,586526185

64,66315462

1,01042252

8192

2,673922678

66,84806695

2,00558036

16384

2,763962469

69,09906173

3,93187819

32768

2,823569268

70,58923171

7,95225516

65536

2,883557799

72,08894498

16,01346782

131072

2,862057772

71,55144429

35,72129628

Таблица 6

Показатели эффективности распараллеливания БПФ для ЦП Intel Xeon 5160

Размер выборки

Sp

Ep, %

T0, c.

4

0,722532651

36,12663256

0,00037951

8

0,888026111

44,40130557

0,0008449

16

0,969860678

48,49303391

0,00200598

32

0,986987328

49,34936641

0,00499396

64

0,988273214

49,41366072

0,01213801

128

0,996634768

49,8317384

0,02816981

256

1,004209732

50,21048658

0,06502854

512

1,012524821

50,62624106

0,14705982

1024

1,73623144

86,81157202

0,05174169

2048

1,77164581

88,58229052

0,09848433

4096

1,808865596

90,44327978

0,17877716

8192

1,889452475

94,47262375

0,21784443

16384

1,902081582

95,10407911

0,4187138

32768

1,931196566

96,55982832

0,63634171

65536

1,927747682

96,38738408

1,48529092

131072

1,983562656

99,17813279

0,72680677

Таблица 7

Показатели эффективности распараллеливания БПФ для ЦП Intel Core i5 - 750

Размер выборки

Sp

Ep, %

T0, c.

4

0,923238451

23,08096127

0,00052748

8

1,025502865

25,63757163

0,0013028

16

1,198893229

29,97233073

0,00301175

32

1,170324032

29,25810079

0,00805156

64

1,112564903

27,81412257

0,02132674

128

1,10506343

27,62658575

0,04880038

256

1,030877297

25,77193243

0,12045039

512

1,03315839

25,82895974

0,26684171

1024

1,573200172

39,33000429

0,31833008

2048

2,357245324

58,93113309

0,3128554

4096

2,280792018

57,01980046

0,73523707

8192

2,292304299

57,30760748

1,58101605

16384

2,460132702

61,50331754

2,88063111

32768

2,444223695

61,10559237

6,30529399

65536

2,536657083

63,41642709

12,23609954

131072

2,648732063

66,21830157

23,22066069

Отметим, что показатель «накладные расходы» возрастает пропорционально объёму анализируемых данных, что может быть объяснено асимптотическим значением алгоритма

Зависимость показателей «ускорение» и «эффективность использования вычислительных ресурсов» от размера выборки показана на рисунках 11 и 12 соответственно.

Рисунок 11 - Зависимость ускорения от размера выборки

Рисунок 12 - Зависимость «эффективности использования выч. ресурсов» от размера выборки

При реализации специализированного решения вычисления БПФ необходимо учитывать данные особенности (рисунок 11-12) - для выборок менее 128 элементов использовать алгоритм без параллельных вычислений.

2.1.4 Вычисление обратного преобразования Фурье через прямое быстрое преобразование Фурье

Существует две схемы для вычисления ОБПФ через БПФ (первая схема приведена на рисунке 13, вторая - на рисунке 14) [18].

Рисунок 13 - Первая схема вычисления ОБПФ через БПФ

Рисунок 14 - Вторая схема вычисления ОБПФ через БПФ

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

Что касается второй схемы, в случае размещения действительной и мнимой частей входных данных в отдельных массивах предварительная обработка сводится лишь к одной операции перестановки местами указателей на начало массивов (которая обычно выполняется за один такт ЦП [19, 20]). После выполнения БПФ нужно провести повторную перестановку указателей. Таким образом, вычисление ОБПФ может быть сведено к вычислению БПФ без существенных потерь времени.

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

2.2 Исследование взаимнокорреляционной функции

2.2.1 Последовательная и параллельная реализация расчёта взаимнокорреляционной функции

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

На этапе инициализации функции вычисления определяется количество окон для последующих расчётов с учётом коэффициента перекрытия соседних окон преобразования Фурье. В случае если переменная параметра расчета Param_IN принимает значение «1», остаток данных, не достаточный для формирования очередного окна дополняется данными с начала исходной анализируемой выборки. Если Param_IN = 2 - остаток данных дополняется нулями, в случае значения «0» остаточные данные, не образующие собой полное окно откидываются.

Основной цикл запускается с заданным количеством исполнений (по количеству окон, рассчитанному ранее). На каждой итерации цикла происходит отбор данных для образования окна нужной ширины. Смещение относительно предшествующего исполнения определяется значением коэффициента перекрытия, принимающего значения от 0 до 100%. Далее данные окна умножаются на соответствующие значения оконной функции, вид которой выбирается параметром Win (используемые оконные функции приведены в приложении А). Для каждого окна выполняется расчёт корреляции в соответствии с методом «быстрой корреляции». Отметим, что в цикле реализуется только накопление суммы и усреднение взаимных спектров. Затем для каждого из окон рассчитывается нормирующий коэффициент для корреляции.

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

Для реализации параллельного вычисления использован шаблон библиотеки Intel TBB tbb::parallel_for.

Распределение итераций между потоками определяет параметр «Grainsize». Планированием распределения итераций между потоками занимается специальный планировщик, предусмотренный библиотекой. Принцип распределения итераций по потокам в зависимости от параметра «Grainsize» следующий [21]:

1. если параметр «Grainsize» равен числу итераций, то все итерации будут выполнены в одном потоке;

2. если параметр «Grainsize» равен отношению общего числа итераций к числу вычислительных устройств (ядер ЦП), то каждый поток выполнит примерно одинаковое количество итераций. Слово «примерно» используется по той причине, что распределение данных между потоками происходит в динамическом режиме;

3. если «Grainsize» меньше отношения общего числа итераций к числу вычислительных устройств, то планировщик распределит итерации динамически. При этом какие-то потоки обработают большее количество итераций. Листинг пересчёта оптимального значения grainsize на языке C++ приведён ниже:

uint uGrain = grainsize / flyCount;

if (uGrain < 1) uGrain = 1;

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

Для оценки производительности от использования многоядерных центральных процессоров было создано экспериментальное программное обеспечение и проведен ряд тестов на модельных примерах. Результаты приведены в таблицах 8-10.

SizeWin - размер окна, N - количество отчётов исходного анализируемого сигнала, Ts - время выполнения последовательного кода, Tp - время выполнения параллельного кода.

Таблица 8

Временные замеры для ЦП Intel Core 2 Q6700

SizeWin

N

Ts, с.

Tp, с.

32768

524288

0,563049821

0,180386105

1048576

1,125053171

0,357660741

2097152

2,255201346

0,711129095

4194304

4,506509118

1,43976893

65536

524288

0,601127708

0,193063013

1048576

1,196051644

0,378804668

2097152

2,389619047

0,75176517

4194304

4,774019639

1,530567285

131072

524288

0,645206608

0,210609876

1048576

1,278819791

0,407388882

2097152

2,537439463

0,80229469

4194304

5,056756319

1,593727469

Таблица 9

Временные замеры для ЦП Intel Core i3 - 4330

SizeWin

N

Ts, с.

Tp, с.

32768

524288

0,266390674

0,10794683

1048576

0,48576787

0,180842667

2097152

0,963025629

0,362803837

4194304

1,918917244

0,723630443

65536

524288

0,25683239

0,11577372

1048576

0,509672226

0,193907736

2097152

1,015157971

0,385850809

4194304

2,024144357

0,776553324

131072

524288

0,273566663

0,111901891

1048576

0,539220198

0,210680765

2097152

1,071236131

0,41084228

4194304

2,135150785

0,815101699

Таблица 10

Временные замеры для ЦП Intel Core i5 - 750

SizeWin

N

Ts, с.

Tp, с.

32768

524288

0,296852289

0,113044387

1048576

0,590822681

0,223425157

2097152

1,17881237

0,44243635

4194304

2,369131607

0,878894138

65536

524288

0,311063406

0,114927362

1048576

0,61796447

0,227109962

2097152

1,233416703

0,442382645

4194304

2,470918967

0,876683651

131072

524288

0,331201308

0,123951079

1048576

0,654487494

0,239070838

2097152

1,3024929

0,458107634

4194304

2,597991038

0,908922106

2.2.2 Анализ эффективности распараллеливания взаимнокорреляционной функции

Произведём расчёт показателей эффективности распараллеливания для реализации ВКФ. Результаты вычислений приведены в таблицах 11-13.

Таблица 11

Показатели качества распараллеливания вычисления ВКФ для ЦП Intel Core 2 Q6700

SizeWin

N

S

E, %

T0, c.

32768

524288

3,12136

78,034

0,158494599

1048576

3,14559

78,640

0,305589793

2097152

3,17130

79,282

0,589315034

4194304

3,13002

78,251

1,252566602

65536

524288

3,11364

77,841

0,171124344

1048576

3,15744

78,936

0,319167028

2097152

3,17868

79,467

0,617441633

4194304

3,11912

77,978

1,348249501

131072

524288

3,06352

76,588

0,197232896

1048576

3,13906

78,477

0,350735737

2097152

3,16273

79,068

0,671739297

4194304

3,17291

79,323

1,318153557

Таблица 12

Показатели качества распараллеливания вычисления ВКФ для ЦП Intel Core i3 - 4330

SizeWin

N

S

E, %

T0

32768

524288

2,46781

61,695

0,165396646

1048576

2,68614

67,153

0,237602798

2097152

2,65440

66,360

0,488189719

4194304

2,65179

66,295

0,975604528

65536

524288

2,21841

55,460

0,20626249

1048576

2,62843

65,711

0,265958718

2097152

2,63096

65,774

0,528245265

4194304

2,60658

65,164

1,082068939

131072

524288

2,44471

61,118

0,174040901

1048576

2,55942

63,986

0,303502862

2097152

2,60741

65,185

0,572132989

4194304

2,61949

65,487

1,125256011

Таблица 13

Показатели качества распараллеливания вычисления ВКФ для ЦП Intel Core i5 - 750

SizeWin

N

S

E, %

T0

32768

524288

2,62598

65,650

0,155325259

1048576

2,64439

66,110

0,302877947

2097152

2,66437

66,609

0,59093303

4194304

2,69558

67,390

1,146444945

65536

524288

2,70661

67,665

0,148646042

1048576

2,72099

68,025

0,290475378

2097152

2,78812

69,703

0,536113877

4194304

2,81848

70,462

1,035815637

131072

524288

2,67203

66,801

0,164603008

1048576

2,73763

68,441

0,301795858

2097152

2,84320

71,080

0,529937636

4194304

2,85832

71,458

1,037697386

Из анализа полученных данных (таблицы 11-13) следует, что показатель «накладные расходы» не зависит от размера окна SizeWin, но зависит количества отсчётов исходного анализируемого сигнала N. Нелинейная зависимость параметра «накладных расходов» от размера исходной выборки может быть объяснена нелинейной асимптотической оценкой алгоритма. Зависимости ускорения от размера выборки при различных значениях SizeWin показаны на рисунках 15-17.

Рисунок 15 - Зависимость ускорения от размера исходного анализируемого сигнала (SizeWin = 32768)

Рисунок 16 - Зависимость ускорения от размера исходного анализируемого сигнала (SizeWin = 65536)

Рисунок 17 - Зависимость ускорения от размера исходного анализируемого сигнала (SizeWin = 131072)

На рисунках 18-20 приведены зависимости эффективности использования вычислительных ресурсов от количества отсчётов анализируемого сигнала.

Рисунок 18 - Зависимость эффективности использования вычислительных ресурсов от размера исходного анализируемого сигнала (SizeWin = 32768)

Рисунок 19 - Зависимость эффективности использования вычислительных ресурсов от размера исходного анализируемого сигнала (SizeWin = 65536)

Рисунок 20 - Зависимость эффективности использования вычислительных ресурсов от размера исходного анализируемого сигнала (SizeWin = 131072)

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

Построим зависимость показателя «ускорение» от размера окна Sw.

Рисунок 21 - Зависимости ускорения от размера окна

Отметим, что показатель «ускорение» не зависит от размера окна. Эффективность использования вычислительных ресурсов также не зависит от размера окна, поскольку согласно уравнению (36) отличается от ускорения только наличием нормирующего множителя ??

2.3 Исследование функций когерентности

2.3.1 Последовательная и параллельная реализация расчёта функций когерентности

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

Рисунок 22 - Функциональная схема вычисления функций когерентности

На этапе инициализации функции вычисления определяется количество окон для последующих расчётов. В случае если переменная параметра расчета Param_IN принимает значение «1», остаток данных, не достаточный для формирования очередного окна дополняется данными с начала исходной анализируемой выборки. Если Param_IN = 2 - остаток данных дополняется нулями, в случае значения «0» остаточные данные, не образующие собой полное окно откидываются.


Подобные документы

  • Сигнал как некоторое средство для передачи информации. Знакомство с параллельными алгоритмами двумерного быстрого преобразования Фурье, анализ способов вычисления. Общая характеристика процессора Power5 64-bit RISC. Рассмотрение функций библиотеки MPI.

    дипломная работа [1,6 M], добавлен 09.10.2013

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

    дипломная работа [3,6 M], добавлен 07.07.2012

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

    лабораторная работа [228,8 K], добавлен 13.11.2010

  • Разработка и анализ алгоритмов с использованием электронных таблиц и прикладных программ Smath Studio, Microsoft Excel. Проверка алгоритма ветвления или выбора. Реализация циклов на примере вычисления определённого интеграла с заданной точностью.

    контрольная работа [1,0 M], добавлен 19.03.2016

  • Методы и алгоритмы вычисления определенных интегралов: метод трапеций и метод Симпсона (метод парабол). Оформление функции вычисления заданного определённого интеграла на Visual Basic 6.0. Программный код функции. Создание приложения для вычисления.

    курсовая работа [483,6 K], добавлен 25.06.2014

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

    курсовая работа [2,5 M], добавлен 25.01.2013

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

    курсовая работа [568,3 K], добавлен 07.03.2015

  • Использование нестандартных функций и подпрограмм (процедур) для составления алгоритмов вычислений. Программы для вычисления значение корней нелинейного уравнения по методу половинного деления. Составление алгоритма операций над матрицами и интегралами.

    курсовая работа [580,0 K], добавлен 23.08.2015

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

    контрольная работа [831,0 K], добавлен 24.11.2013

  • Состав и принцип работы аппаратуры. Выбор параметров корреляционного анализа и Фурье-анализа. Разработка и применение алгоритма корреляционного анализа. Реализация алгоритма Фурье-анализа на языке С++ и алгоритма корреляционного анализа на языке С#.

    дипломная работа [4,6 M], добавлен 30.11.2016

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.