Швидке перетворення Фур’є

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

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

Реферат

Швидке перетворення Фур'є

Вступ

Перетворення Фур'є використовується в багатьох галузях науки - в фізиці, теорії чисел, комбинаториці, обробці сигналів, теорії ймовірності, статистиці, криптографції, акустиці, океанології, оптиці, геометрії, та багатьох інших. При обробці сигналів різної природи перетворення Фур'є звичайно розглядається як трансформація сигналу з часової ділянки в частотну.

Дискретне перетворення Фур'є грає важливу роль при аналізі, синтезі та розробці систем та алгоритмів цифрової обробки сигналів. Одна з причин того, що аналіз Фур'є грає таку важливу роль в цифровій обрабці сигналів, полягає в існуванні ефективних алгоритмів дискретного перетворення Фур'є.

Ці перетворення зворотні, при чому зворотнє перетворення має практично таку ж саму форму, що й пряме перетворення.

Швидке перетворення Фур'є застосовується в багатьох галузях: радіолокации, стисненні відео та зображень, геології. Багато з цих задач вимагають виконання перетворень в реальному часі, з мінімальною часовою затримкою обчислень.

Для зменшення часу, необхідного для виконання перетворень, можливо розпаралелювання задачі, виконання її на паралельній обчислювальній системі.

Мета цієї роботи - вивчення алгоритмів швидкого перетворення Фур'є двовимірних сигналів.

1. Перетворення Фур'є

Перетворення Фур'є - перетворення, що зіставляють функції якоїсь дійсної змінної. Дана операція виконується кожен раз, коли ми сприймаємо різні звуки. Вухо виробляє автоматичне «обчислення», виконати яке наше свідомість здатна тільки після вивчення відповідного розділу вищої математики.

Орган слуху у людини будує перетворення, в результаті якого звук (коливальний рух умовних частинок в пружною середовищі, які поширюються в хвильовому вигляді у твердій, рідкому або газоподібному середовищі) надається у вигляді спектра послідовно йдуть значень рівня гучності тонів різної висоти. Після цього мозок перетворює дану інформацію в звичний всім звук (рис. 1).

Рисунок 1. Наочне подання перетворення Фур'є

Перетворення звукових хвиль або інших коливальних процесів (від світлового випромінювання і океанського припливу і до циклів зоряної або сонячної активності) можна проводити і за допомогою математичних методів. Так, користуючись даними прийомами, можна розкласти функції, представивши коливальні процеси набором синусоїдальних складових, тобто хвилеподібних кривих, які переходять від мінімуму до максимуму, потім знову до мінімуму, подібно до морської хвилі. Перетворення Фур'є - перетворення, функція якого описує фазу або амплітуду кожної синусоїди, що відповідає певній частоті. Фаза являє собою початкову точку кривої, а амплітуда - її висоту.

Перетворення Фур'є є досить потужним інструментарієм, який застосовується в різноманітних галузях науки. В окремих випадках він використовується як засіб вирішення досить складних рівнянь, які описують динамічні процеси, що виникають під впливом світлової, теплової або електричної енергії. В інших випадках він дозволяє визначати регулярні складові в складних коливальних сигналах, завдяки цьому можна правильно інтерпретувати різні експериментальні спостереження в хімії, медицині та астрономії.

Першою людиною, який застосував цей метод, став французький математик Жан Батист Фур'є (рис. 2).

Рисунок 2. Французький математик Жан Батист Фур'є

Перетворення, назване згодом його ім'ям, спочатку використовувалося для опису механізму теплопровідності. Фур'є все своє свідоме життя займався вивченням властивостей тепла. Він зробив величезний внесок у математичну теорію визначення коренів алгебраїчних рівнянь. Фур'є був професором аналізу в Політехнічній школі, секретарем Інституту єгиптології, перебував на імператорській службі, на якій відзначився під час будівництва дороги на Турин (під його керівництвом було осушено понад 80 тисяч квадратних кілометрів малярійних боліт). Проте вся ця активна діяльність не завадила вченому займатися математичним аналізом. У 1802 році їм було виведено рівняння, яке описує поширення тепла у твердих тілах. У 1807 році вчений відкрив метод вирішення даного рівняння, яке і отримало назву «перетворення Фур'є».

2. Основа та принципи перетворення

Алгоритм перетворення Фур'є став викликом теоретичним основам математики того часу. На початку дев'ятнадцятого століття більшість видатних учених, у тому числі і Лагранж, Лаплас, Пуассон, Лежандр і Біо, не прийняли його твердження про те, що початковий розподіл температури розкладається на складові у вигляді основної гармоніки і більше високочастотні. Однак академія наук не могла проігнорувати результати, отримані математиком, і удостоїла його премії за теорію законів теплопровідності, а також проведення порівняння її з фізичними експериментами.

У підході Фур'є головне заперечення викликав той факт, що розривна функція представлена сумою декількох синусоїдальних функцій, які є безперервними. Адже вони описують розриваються прямі і криві лінії. Сучасники вченого ніколи не стикалися з подібною ситуацією, коли розривні функції описувалися комбінацією безперервних, таких як квадратична, лінійна, синусоїда або експонента. У тому випадку, якщо математик був правий у своїх твердженнях, то сума нескінченного ряду тригонометричної функції повинна зводитися до точної ступінчастою. У той час подібне твердження здавалося абсурдним. Однак, незважаючи на сумніви, деякі дослідники (наприклад Клод Навьє, Софі Жермен) розширили сферу досліджень і вивели їх за межі аналізу розподілу теплової енергії. А математики тим часом продовжували мучитися питанням про те, чи може сума кількох синусоїдальних функцій зводитися до точного поданням розривної.

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

Перший з них застосовується в тому випадку, коли вихідна функція є безперервною, а другий - в тому випадку, коли вона представлена безліччю дискретних окремих змін. Якщо вираз отримано із значень, які визначені дискретними інтервалами, то його можна розбити на кілька синусоїдальних виразів з дискретними частотами - від найнижчої і далі вдвічі, втричі і так далі вище основної. Таку суму прийнято називати поруч Фур'є.

Якщо початкове вираз задано значенням для кожного дійсного числа, то його можна розкласти на кілька синусоїдальних всіх можливих частот. Його прийнято називати інтегралом Фур'є, а рішення має на увазі під собою інтегральні перетворення функції. Незалежно від способу отримання перетворення, для кожної частоти слід вказувати два числа: амплітуду і частоту. Дані значення виражаються у вигляді єдиного комплексного числа.

Теорія виразів комплексних змінних спільно з перетворенням Фур'є дозволила проводити обчислення при конструюванні різних електричних ланцюгів, аналіз механічних коливань, вивчення механізму поширення хвиль та інше.

3. Застосування перетворення Фур'є

У наші дні вивчення даного процесу в основному зводиться до знаходження ефективних методів переходу від функції до її перетвореному увазі і назад. Таке рішення називається пряме і зворотне перетворення Фур'є. Що це означає? Для того щоб визначити інтеграл і провести пряме перетворення Фур'є, можна скористатися математичними методами, а можна і аналітичними. Незважаючи на те що при їх використанні на практиці виникають певні труднощі, більшість інтегралів вже знайдені і внесені в математичні довідники. За допомогою чисельних методів можна розраховувати вираження, форма яких грунтується на експериментальних даних, або функції, інтеграли яких в таблицях відсутні і їх складно уявити в аналітичній формі.

До появи обчислювальної техніки розрахунки таких перетворень були вельми нудними, вони вимагали ручного виконання великої кількості арифметичних операцій, які залежали від числа точок, що описують хвильову функцію. Для полегшення розрахунків сьогодні існують спеціальні програми, що дозволили реалізувати нові аналітичні методи (рис. 3, 4).

Так, в 1965 році Джеймс Кулі та Джон Тьюки створили програмне забезпечення, що здобуло популярність як «швидке перетворення Фур'є». Воно дозволяє економити час проведення розрахунків за рахунок зменшення числа множень при аналізі кривої. Метод «швидке перетворення Фур'є» заснований на поділі кривої на велике число рівномірних вибіркових значень. Відповідно кількість множень знижується вдвічі при такому ж зниженні кількості точок.

Рисунок 3. Програмне забезпечення для виконання швидкого перетворення Фур'є

Рисунок 4. Приклад виконання швидкого перетворення Фур'є

Даний процес використовується в різних областях науки: в теорії чисел, фізиці, обробці сигналів, комбінаторики, теорії ймовірності, криптографії, статистикою, океанології, оптиці, акустиці, геометрії та інших. Багаті можливості його застосування засновані на ряді корисних особливостей, які отримали назву «властивості перетворення Фур'є». Розглянемо їх.

1. Перетворення функції є лінійним оператором і з відповідною нормалізацією є унітарною. Дана властивість відомо як теорема Парсеваля, або в загальному випадку теорема Планшереля, або дуалізм Понтрягіна.

2. Перетворення є оборотним. Причому зворотний результат має практично аналогічну форму, як і при прямому рішенні.

3. Синусоїдальні базові вирази є власними диференційованими функціями. Це означає, що таке подання змінює лінійні рівняння з постійним коефіцієнтом у звичайні алгебраїчні.

4. Згідно з теоремою «згортки», даний процес перетворює складну операцію в елементарне множення.

5. Дискретне перетворення Фур'є може бути швидко розраховане на комп'ютері з використанням «швидкого» методу.

4. Різновиди ШПФ

1. Найбільш часто цей термін використовується для позначення безперервного перетворення, що надає будь квадратично інтегрувальне вираження у вигляді суми комплексних показових виразів з конкретними кутовими частотами і амплітудами. Даний вид має декілька різних форм, які можуть відрізнятися постійними коефіцієнтами. Безперервний метод включає в себе таблицю перетворень, яку можна знайти в математичних довідниках. Узагальненим випадком є дробове перетворення, за допомогою якого даний процес можна звести в необхідну речову ступінь.

2. Безперервний спосіб є узагальненням ранньої методики рядів Фур'є, визначених для різних періодичних функцій або виразів, які існують в обмеженій області і представляють їх як ряди синусоид.

3. Дискретне перетворення Фур'є. Цей метод використовується в комп'ютерній техніці для проведення наукових розрахунків і для цифрової обробки сигналів. Для проведення даного виду розрахунків потрібно мати функції, що визначають на дискретній множині окремі точки, періодичні або обмежені області замість безперервних інтегралів Фур'є. Перетворення сигналу в такому випадку представлено як сума синусоїд. При цьому використання «швидкого» методу дозволяє застосовувати дискретні рішення для будь-яких практичних завдань.

4. Віконне перетворення Фур'є є узагальненим видом класичного методу. На відміну від стандартного рішення, коли використовується спектр сигналу, який взятий в повному діапазоні існування даної змінної, тут особливий інтерес представляє всього лише локальний розподіл частоти за умови збереження початкової змінної (час).

5. Двовимірне перетворення Фур'є. Даний метод використовується для роботи з двовимірними масивами даних. У такому випадку спочатку перетворення проводиться в одному напрямку, а потім - в іншому.

Висновки

Сьогодні метод Фур'є міцно закріпився в різних галузях науки. Наприклад, в 1962 році була відкрита форма подвійний ДНК-спіралі з використанням аналізу Фур'є в поєднанні з дифракцією рентгенівських променів. Останні фокусувалися на кристалах волокон ДНК, в результаті зображення, яке виходило при дифракції випромінювання, фіксувалися на плівці. Дана картинка дала інформацію про значення амплітуди при використанні перетворення Фур'є до даної кристалічній структурі. Дані про фазу отримали шляхом зіставлення дифракційної карти ДНК з картами, які отримані при аналізі подібних хімічних структур. В результаті біологи відновили кристалічну структуру - вихідну функцію.

Перетворення Фур'є відіграють величезну роль у вивченні космічного простору, фізики напівпровідникових матеріалів та плазми, мікрохвильовою акустиці, океанографії, радіолокації, сейсмології та медичних обстеженнях.

У теперешній час існує багато методів та алгоритмів ШПФ, які реалізовані як у вигляді спеціальних пакетів, так і в таких стандартних потужних математичних пакетах, як Matlab, Mathcad та Mathematica.

Але за достатньо великих об'ємів обчисленнь вони можуть не надавати необхідної швидкості виконання перетворень, хоч і є ідеальним засобом перевірки вірності отриманих результатів.

Новизна полягає в реалізації дискретного двовимірного швидкого перетворення Фур'є для великих зображень в реальному часі, орієнтуючись на те, щоб отримані результати можна було використовувати для подальшої обробки, без відчутної часової затримки.

Перелік посилань

1. Говидараю Н.К., Ллойд Б., Доценко Ю., Смит Б., Манферделли Д. Высокопроизводительные дискретные преобразования Фурье на графических процессорах/ компания Microsoft, - ../library/translate.htm

2. Троянский А.В. Поточные процессоры быстрого преобразования Фурье с перестраиваемой архитектурой на однотипных СБИС: Дис. канд. техн. наук: 05.12.21 / Одесский гос. политехнический ун-т. - О., 1997. - 185 с. - http://www.dissua.com/contua/pk-15757.html

3. Гюрджян М.К. Некоторые вопросы организации параллельных вычислений в многопроцессорных вычислительных системах кластерного типа: дис. канд. техн. наук: 05.13.05 / Институт проблем информатики и автоматизации НАН РА. - Ереван, 2004. - http://www.dissua.com/contua/pk-20301.html

4. Потопальский В.В. Оценка качества преобразования Фурье в радиотехнических и телевизионных системах: дис. канд. техн. наук: 05.12.17 / АН Украины. - Львов, 1993. - 189 с. - http://www.dissua.com/contua/pk-260506.html

5. Керекеша П.В. Комбинированный метод преобразования Фурье и сопряжения аналитических функций в задачах теории упругости: Дис. д-ра физ.-мат. наук: 01.02.04 / Одесский гос. ун-т им. И.И. Мечникова. - О., 1999. - 314 с. - http://www.dissua.com/contua/pk-11181.html

6. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. Москва, Мир - 1989. 248 с.

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