Размещено на http://www.allbest.ru/

Федеральное агентство железнодорожного транспорта

Омский государственный университет путей сообщения

Кафедра «Автоматика и системы управления»

ОТЧЕТ

по учебной практике

Место прохождение учебной практики

ООО «Системы комплексной энергоэффективности»

Студент гр. 26м

Котельный С.И.

« » 2017 г.

Руководитель учебной практики -

доцент кафедры «АиСУ»

Елизаров Д.А.

Омск 2017

Содержание

Введение

1. Реализация теста функции FFT

1.1 Задание

1.2 Используемые библиотеки

1.3 Алгоритм Simple radix-2 FFT

1.4 Алгоритм Simple split-radix FFT

1.5 Алгоритм Simple conjugate-pair FFT

1.6 Алгоритм Simple tangent FFT

1.7 Тесты быстродействия алгоритмов функций FFT

Заключение

Введение

Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) - это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путем дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как свертки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье.

Быстрое преобразование Фурье (БПФ, FFT) - алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем O(N2). O(N2), требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени, имеющий сложность O(N*log(N)).

1. Реализация теста функции FFT

1.1 Задание

Необходимо собрать статистику работы различных реализаций функций алгоритма "Быстрое преобразование Фурье" FFT. 1 измерением будем считать измерение времени выполнения функции 1000 раз. Нужно провести 100 измерений (100 циклов, в каждом из которых делается измерение всех методов).

1.2 Используемые библиотеки

В реализации функций используются стандартные библиотеки С++:

1.2.1. <stdio.h> - стандартный заголовочный файл ввода-вывода

1.2.2. <stdlib.h> - заголовочный файл стандартной библиотеки языка С++, который содержит в себе функции, занимающиеся выделением памяти, контроль процесса выполнения программы, преобразования типов и другие.

1.2.3. <iostream> - заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C++.

1.2.4. <cmath> - заголовочный файл стандартной библиотеки языка программирования С++, разработанный для выполнения простых математических операций.

1.2.5. <complex> - заголовочный файл стандартной библиотеки языка программирования С++, в котором объявляются функции для комплексной арифметики.

1.2.6. <ctime> - заголовочный файл стандартной библиотеки языка программирования С++, содержащий типы и функции для работы с датой и временем.

1.3 Алгоритм Simple radix-2 FFT

Листинг 1 - Алгоритм функции Simple radix-2 FFT

1.4 Алгоритм Simple split-radix FFT

Листинг 2 - Алгоритм функции Simple split-radix FFT

1.5 Алгоритм Simple conjugate-pair FFT

Листинг 3 - Алгоритм функции Simple conjugate-pair FFT

1.6 Алгоритм Simple tangent FFT

Листинг 4 - Алгоритм функции Simple tangent FFT

Листинг 5 - Алгоритм функции Simple tangent FFT

1.7 Тесты быстродействия алгоритмов функций FFT

Листинг 6 - Тесты функций FFT

Листинг 7 - Тесты функций FFT

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

Таблица 1 - Быстродействие алгоритмов

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

Рисунок 1 - График быстродействия функций

Заключение

фурье алгоритм приложение консольный

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

В процессе разработки программы была изучена лексика и синтаксис языка С++.

Размещено на Allbest.ru