Введение 4
1 Постановка задачи 6
1.1 Современное состояние проблемы 6
1.2 Актуальность задачи 10
2 Вводная глава 12
2.1 Точная постановка задачи 12
2.2 Преобразование Фурье 12
2.3 Двумерное дискретное преобразование Фурье и его обращение 15
2.4 Вычисление двумерного дискретного преобразования Фурье 18
2.5 Вычисление трёхмерного дискретного преобразования Фурье 25
2.6 Описание библиотеки MPI 28
2.7 Комплекс высокопроизводительных вычислений ИКИТ СФУ 31
3 Основные достигнутые результаты 33
3.1 Словесное описание алгоритма работы программы 33
3.1 Блок-схема алгоритма работы программы 35
3.2 Основные трудности, возникшие в процессе работы 36
3.3 Результаты численного эксперимента в двумерном случае 41
3.4 Результаты численного эксперимента в трёхмерном случае 42
Заключение 43
Список использованных источников 44
Приложение А. Текст программы двумерного БПФ 46
Приложение Б. Текст программы трёхмерного БПФ 67
Одним из сопутствующих факторов компьютерной революции оказалось появление совершенно новых областей исследования. С каждым годом по мере увеличения быстродействия, уменьшения стоимости и размеров ИС растут возможности решения задач все возрастающей сложности. К ним относится цифровая обработка многомерных сигналов, требующая значительных объемов цифровой памяти и соответствующего количества арифметических операций. Несмотря на сложность, цифровая обработка сигналов уже позволила найти решение ряда важных задач, начиная с компьютерной томографии (методики, позволяющей по проекциям рентгеновского изображения, полученным при различных ориентациях детекторов, выполнять трехмерную реконструкцию органов человеческого тела) и кончая проектированием полей пассивных акустических датчиков и исследованием ресурсов Земли с помощью спутников. Цифровая обработка многомерных сигналов имеет также прочное математическое обоснование, позволяющее не только понять уже достигнутое, но и эффективно исследовать новые проблемы по мере их возникновения и успешно их решать.
Сигнал - это некоторое средство для передачи информации, а целью обработки сигналов является извлечение этой информации. Так, ансамбли изменяющихся во времени электрических потенциалов, плотность зерен серебра фотографической эмульсии или массивы чисел в памяти ЭВМ представляют собой примеры сигналов. Обычно обработка сигналов включает в себя перенос информации с одного сигнала на другой. Независимо от своей физической сущности сигналы представляют интерес только благодаря содержащейся в них информации. Можно сказать, что обработка сигналов включает в себя две основные задачи - преобразование способа представления информации в сигнале и сокращение ее объема.
Цифровая обработка сигналов касается обработки сигналов, которые можно представить в виде последовательности чисел, а цифровая обработка многомерных сигналов - обработки сигналов, представленных в виде многомерных массивов чисел, например массивов, получаемых после дискретизации изображений или результатов дискретизации непрерывно изменяющихся во времени сигналов, поступающих одновременно от нескольких датчиков.
В ходе магистерской диссертации были закреплены знания, полученные в процессе обучения, приобретены новые знания в области параллельного программирования, разработаны параллельные алгоритмы двумерного быстрого преобразования Фурье, данные алгоритмы реализованы на языке программирования высокого уровня С++ с использованием библиотеки MPI, разработаны алгоритмы трёхмерного быстрого преобразования Фурье.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
