Дискретное преобразование Фурье
Анализ статистики быстродействия алгоритмов для различного количества входных значений данных. Характеристика различных методов реализации алгоритма быстрого преобразования Фурье, исследование их быстродействия в консольном приложении на языке Си.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | отчет по практике |
| Язык | русский |
| Дата добавления | 18.02.2019 |
| Размер файла | 808,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на 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 - Быстродействие алгоритмов
|
Кол-во точек N |
Быстродействие 1 измерения функций, мс |
||||
|
ditfft2, мс |
splitfft, мс |
conjfft, мс |
tangentfft4, мс |
||
|
8 |
16 |
17 |
9 |
10 |
|
|
16 |
54 |
63 |
30 |
31 |
|
|
32 |
152 |
186 |
85 |
95 |
|
|
64 |
339 |
505 |
222 |
237 |
|
|
128 |
962 |
1276 |
553 |
579 |
На рисунке 1 изображен график быстродействия функций, наглядно иллюстрирующий зависимость необходимого времени для 1 измерения и количества входных значений данных.
Рисунок 1 - График быстродействия функций
Заключение
фурье алгоритм приложение консольный
В ходе учебной практики были рассмотрены различные методы реализации алгоритма быстрого преобразования Фурье, а так же протестированы их быстродействия в консольном приложении на языке С++.
В процессе разработки программы была изучена лексика и синтаксис языка С++.
Размещено на Allbest.ru
...Подобные документы
Разработка функции вычисления дискретного преобразования Фурье от входного вектора. Исследование свойств симметрии ДПФ при мнимых, четных и нечетных входных сигналах. Применение обратного преобразования Фурье для генерации периодической функции косинуса.
лабораторная работа [228,8 K], добавлен 13.11.2010Сигнал как некоторое средство для передачи информации. Знакомство с параллельными алгоритмами двумерного быстрого преобразования Фурье, анализ способов вычисления. Общая характеристика процессора Power5 64-bit RISC. Рассмотрение функций библиотеки MPI.
дипломная работа [1,6 M], добавлен 09.10.2013Анализ проблем, возникающих при совмещении изображений в корреляционно-экстремальных навигационных системах. Использование двумерного дискретного преобразования Фурье. Нахождение корреляционной функции радиолокационного и моделируемого изображений.
дипломная работа [3,6 M], добавлен 07.07.2012Состав и принцип работы аппаратуры. Выбор параметров корреляционного анализа и Фурье-анализа. Разработка и применение алгоритма корреляционного анализа. Реализация алгоритма Фурье-анализа на языке С++ и алгоритма корреляционного анализа на языке С#.
дипломная работа [4,6 M], добавлен 30.11.2016Характеристика сигнала и его представление в виде математического ряда. Условия ортогональности двух базисных функций. Ряд Фурье, его интегральное преобразование и практическое использование в цифровой технике для обработки дискретной информации.
реферат [69,9 K], добавлен 14.07.2009Исследование простейших радиотехнических сигналов, разложение их в ряд Фурье. Построение амплитудных спектров синуса, суммы синусов и синка. Создание в среде программирования Matlab программ с параметрами: длина сигнала, амплитуда, частота дискретизации.
лабораторная работа [990,4 K], добавлен 23.11.2014Обзор существующих методов межпроцедурного анализа. Получение входных и выходных данных подпрограмм с помощью графа алгоритма. Описание входных и выходных данных подпрограммы в терминах фактических параметров. Определение параллелизма по графу алгоритма.
учебное пособие [77,5 K], добавлен 28.06.2009Разработка приложений для измерения и сбора данных, управления измерительными приборами, анализа данных измерений и составления отчетов. Электронный цифровой двухканальный осциллограф в LabVIEW. Разложение несинусоидального напряжения в ряд Фурье.
курсовая работа [2,4 M], добавлен 03.06.2019Создание программного продукта на языке Pascal в визуальной среде программирования Borland Developer Studio в консольном приложении. Разработка типизированного файла для записи данных и их вывод на экран, добавление данных в конец файла, поиск информации.
курсовая работа [1,0 M], добавлен 04.12.2011Обзор алгоритмов решения задачи: точные методы, генетический и жадный алгоритмы. Характеристика жадного алгоритма: его описание, анализ точности приближения, вычислительной сложности. Программная реализация и проверка корректности и быстродействия.
курсовая работа [228,7 K], добавлен 14.10.2017Алгоритмы и стандарты криптографических преобразований. Криптографические преобразования на основе специального программного обеспечения. Метод криптографических преобразований на основе жесткой логики. Аналоги модуля шифрования и дешифрования данных.
курсовая работа [971,6 K], добавлен 30.01.2018Исследование особенностей разработки линейных алгоритмов и их реализации в среде Delphi. Составление тестов для проверки программы. Характеристика основных элементов интерфейса, компонентов, значения их свойств. Построение графической схемы алгоритма.
лабораторная работа [316,6 K], добавлен 08.11.2012Разработка и анализ задания. Требования к программному и техническому обеспечению. Разработка алгоритма чтения файла, обработки данных, подбора трека. Расчеты и оценки быстродействия: скорость расчетов и поиска. Разработка руководства пользователя.
курсовая работа [446,7 K], добавлен 22.08.2011Исследование системы распределения ключей на основе линейных преобразований. Описание компонентов сети конфиденциальной связи. Характеристика отечественного алгоритма шифрования данных. Обзор результатов расчетов криптостойкости алгоритма шифрования.
контрольная работа [56,5 K], добавлен 26.09.2012Как изготавливается процессор. Выбор процессора для офисного, игрового и домашнего компьютеров. Как заменить центральный процессор в компьютере. Повышение быстродействия процессоров, тактовой частоты, быстродействия памяти, понижение таймингов.
дипломная работа [1,7 M], добавлен 29.04.2014Изучение применяемых в программировании и информатике структур данных, их спецификации и реализации, алгоритмов обработки данных и анализ этих алгоритмов. Программа определения среднего значения для увеличивающегося количества чисел заданного типа.
контрольная работа [16,0 K], добавлен 19.03.2015Разработка программы тестирования студентов по MS PowerPoint с кодом на языке Delphi. Создание алгоритма для решения функциональных требований задачи. Описание переменных, вспомогательных процедур, входных и выходных данных для реализации программы.
курсовая работа [1,5 M], добавлен 21.09.2010Описание алгоритма решения задачи графическим способом. Вывод элементов массива. Описание блоков укрупненной схемы алгоритма на языке Pascal. Листинг программы, а также ее тестирование. Результат выполнения c помощью ввода различных входных данных.
контрольная работа [150,4 K], добавлен 03.05.2014Написание программного обеспечения на языке ассемблер для AVR-МК ATmega16, позволяющего осуществлять вычисление заданной функции. Введение входных данных с помощью определенного макроса с командой загрузки значений в регистры ldi. Исходный код программы.
контрольная работа [521,0 K], добавлен 23.11.2014Техническое обеспечение, расчет информационно-измерительного канала системы автоматического управления. Методическое обеспечение: описание модели АЦП, спектральный анализ на основе преобразования Фурье. Разработка прикладного программного обеспечения.
курсовая работа [501,2 K], добавлен 21.05.2010
