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

Міністерство освіти і науки України

Національний університет „Львівська політехніка”

Кафедра ЕОМ

Розрахункова робота

з дисципліни: «Проектування комп'ютерних засобів обробки сигналів і зображень»

на тему: «Програмна реалізація алгоритмів швидкого перетворення Фур'є»

Варіант №15

Виконав:

ст. гр. КСМм-13

Назаров Б.С.

Перевірив:

Лашко О.Л.

Львів 2013

Завдання

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

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

Створити завершений програмний засіб обчислення заданого варіантом виду ШПФ. Він повинен забезпечувати:

1. Повноцінний графічний інтерфейс для вводу вхідних параметрів та виводу вихідних значень, а саме:

· табличне представлення вхідної комплексної послідовності у заданому форматі (згідно заданої розрядності). Тут слід передбачити можливість окремої генерації випадковим чином дійсної та уявної частини а також діапазону випадкових чисел;

· табличне представлення повертаючих множників для кожного етапу (ярусу) перетворення;

· табличне та графічне відображення вихідної послідовності (окремо дійсна та уявна частини);

· відображення кількості здійснення математичних операцій та операцій пересилання даних;

· відображення загального часу роботи програми та обчислювального блоку зокрема.

2. Обчислювальна частина повинна реалізовувати:

· ефективну процедуру біт-інверсної перестановки елементів;

· обрахунок повертаючих множників з мінімізацією обчислень;

· основне функціональне перетворення;

· впорядкування результатів у природному порядку слідування.

Вступ

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

Слід мати на увазі, що поняття «спектральний аналіз» включає велике число різних вимірювань. В широкому значенні його можна визначити як вимірювання, яке дає точні або наближені значення z-перетворення дискретного сигналу для заданих значень z. Створення адекватної теорії спектрального аналізу утруднено тією обставиною, що на практиці всі спектральні вимірювання проводяться на кінцевих тимчасових інтервалах, довжина яких звичайно визначається інтуїтивно або на основі накопиченого досвіду. Наприклад, «спектр» мовного сигналу дуже сильно залежить від часу, змінюючись приблизно із швидкістю зміни параметрів мовного тракту (біля 10раз за секунду). Не дивлячись на це, в багатьох прикладних задачах короткочасний спектр мовного сигналу є однією з найважливіших характеристик.

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

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

1. Теоретичний розділ

1.1 Опис ШПФ

програма швидке перетворення Фур'є

1.1.1 Основні визначення

Визначення 1. Дано кінцеву послідовність x₀, x₁, x₂,..., x_N-1 (у загальному випадку комплексних чисел). ДПФ полягає в пошуку послідовності X₀, X₁, X₂,..., X_N-1, елементи якої обчислюються за формулою:

(1)

Визначення 2. Зворотне ДПФ полягає в пошуку послідовності x₀, x₁, x₂,..., x_N-1, елементи якої обчислюються за формулою:

(2)

Основною властивістю перетворень (1) і (2) є те, що з послідовності {x} отримується (при прямому перетворенні) послідовність {X}, а якщо застосувати до {X} зворотне перетворення, то знову отримується вихідна послідовність {x}.

Визначення 3. Величина називається повертаючим множником.

1.1.2 Властивості повертаючих множників

При k = 1

Пряме перетворення Фур'є можна виразити через повертаючі множники. Тоді формула (1) матиме вигляд:

(3)

Геометричне тлумачення повертаючих множників наведене на рис.1. Комплексне число (re^jц) представлене у вигляді вектора, що виходить із початку координат (r - модуль числа, а ц - аргумент). Модуль відповідає довжині вектора, а аргумент - куту повороту. Модуль повертаючого множника . дорівнює одиниці, а фаза - 2р/N. Оскільки при множенні комплексних чисел, представлених у показниковій формі, їхні модулі перемножуються, а аргументи підсумовуються, множення вихідного числа на повертаючий множник не змінить довжину вектора, але змінить його кут. Тобто, відбудеться повертання вектора на кут 2р/N.

З формули (3) можна визначити геометричний зміст перетворення Фур'є таким чином: представити N комплексних чисел-векторів з набору {x}, кожне у вигляді суми векторів з набору {X}, повернених на кути, кратні 2р/N.

Рис. 1. Геометричне тлумачення повертаючих множників

1.1.3 Основні формули

Теорема 1. Якщо комплексне число представлене у вигляді e ^j2рN, де N - ціле, то e ^j2рN = 1.

Теорема 2. Величина періодична по k і по n з періодом N. Тобто, для будь-яких цілих l і m виконується рівність:

(4)

Теорема 3.

Для величини справедлива формула:

(5)

З наведених теорем визначається основна ідея алгоритму ШПФ:

1. Необхідно розділити суму (1) з N доданків на дві суми по N/2 доданків, і обчислити їх окремо. Для обчислення кожної з підсум, треба їх теж розділити на дві і т.д.

2. Необхідно повторно використовувати вже обчислені доданки.

При обчисленні алгоритму ШПФ застосовують або "проріджування за часом" (в першу суму попадають доданки з парними номерами, а в другу - з непарними), або "проріджування за частотою" (в першу суму попадають перші N/2 доданків, а в другу - інші). Обидва варіанти рівноцінні. В силу специфіки алгоритму доводиться застосовувати тільки N, що є ступенями 2.

Теорема 4. Визначимо ще дві послідовності:{x_[even]} і {x_[odd]} через послідовність {x} таким чином:

x_[even]n = x_2n, x_[odd]n = x_2n+1, (6)

n = 0, 1,..., N/ 2-1

Нехай до цих послідовностей застосовані ДПФ і отримані результати у вигляді двох нових послідовностей {X_[even]} і {X_[odd]} по N/2 елементів у кожній.

Елементи послідовності {X} можна виразити через елементи послідовностей {X_[even]} і {X_[odd]} за формулою:

(7)

Формула (7) дозволяє скоротити число множень удвічі (не враховуючи множень при обчисленні X_[even]k і X _[odd]k), якщо обчислювати X_k не послідовно від 0 до N - 1, а попарно: X₀ і X_N/2, X₁ і X_N/2+1,..., X_{N/ 2-1} і X_N. Пари утворяться за принципом:

X_k і X_N/2+k.

Теорема 5. ДПФ можна обчислити і за формулою:

(8)

З теореми випливає, що можна не зберігати обчислені значення X_[even]k і X_[odd]k після обчислення чергової пари, і одне обчислення можна використовувати для обчислення двох елементів послідовності {X}.

На цьому кроці буде виконане N/2 множень комплексних чисел. Якщо застосувати подібні схеми для обчислення послідовностей {X_[even]} і {X_[odd]}, то кожна з них вимагатиме N/4 множень, разом ще N/2. Продовжуючи аналогічно далі log₂N разів, можна дійти до сум, що містять лише один доданок, так що загальна кількість множень рівна (N/2)log₂N.

Висновок:

В основі алгоритму ШПФ лежать такі формули:

(9)

Відомі два різновиди алгоритмів ШПФ - проріджування за часом (decimation in time - DIT) і проріджування по частоті (decimation in frequency - D1F), що мають однакову обчислювальну складність.

2. Розробка блок-схеми алгоритму ШПФ з основою 4

2.1 Біт інверсний порядок видачі даних

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

2.2 Розробка граф-схеми алгоритму ШПФ з основою 4

3. Обрахунки

1. Кількість ярусів для виконання ШПФ визначається наступною формулою:

V=logbaseN=log41024=5

2. Кількість метеликів на одному ярусі:

Кмет1=N/base=1024/4=256 (метеликів)

3. Загальна кількість метеликів для виконання ШПФ:

Кмет=Кмет1*V=256*5=1280 (метеликів)

4. Для виконання 1 метелика необхідно 22 операцій додавань. Отже загальна кількість додавань становить:

Кдод=Кмет*22=1280*22=28160 (операцій)

5. Для виконання 1 метелика необхідно 12 операцій множення. Отже загальна кількість множень становить:

Кмнож=Кмет*12=1280*12= 15360 (операцій)

6. Для виконання 1 метелика необхідно 4 операції читання дійсної частини, 4 операції читання уявної частини, 6 операції читання вагових коефіцієнтів, 4 операції запису дійсної частини, 4 операції запису уявної частини. Отже для виконання усього ШПФ необхідна кількість операцій запису/читання становить:

Кзап/чит=Кмет*(4+4+4+4+6)=1280*22=28160 (операцій)

7. Сумарна кількість операцій становить:

Ксум=28160+28160+15360= 71680 (операцій)

4. Дослідження роботи програми

Рис. 4.1 Вхідні дані

Рис. 4.2 Результати обрахунку



Рис. 4.3 Абсолютна величина чисел

Рис. 4.4 Дійсна частина чисел

Рис. 4.5 Уявна частина чисел

Висновки

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

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

Також було отримано часові характеристики алгоритмів ШПФ та ДПФ. В результаті було зроблено висновок щодо швидкодії виконання цих двох алгоритмів. З результатів виконання програми бачимо що алгоритм ДПФ виконався за ~45 секунд. Алгоритм ШПФ виконався за ~48 секунд, при кількості точок N=1024. Бачимо, що реалізація алгоритму ДПФ виконується швидше на декілька секунд від алгоритму ШПФ.

Література

Цифровые фильтры и устройства обработи сигналов на интегральных микросхемах: Справочное пособие/Ф.Б.Высоцкий, В.И. Алексеев, В.П. Пачин и др.; Под ред. Б.Ф.Высоцкого.-М.: Радио и связь, 1984.-216с.

Цифровая обработка сигналов/ А.Б.Сергиенко - СПб.:Питер, 2002.-608с.

http://www.analog.com/ru/processors-dsp/tigersharc/adsp-ts101s/products/product.html

Цифрове опрацювання сигналів та зображень: Алгоритми та реалізація.

Навчальний посібник до лекційного курсу з дисципліни “Проектування комп'ютерних засобів обробки сигналів та зображень” для студентів спеціальностей 7.091501 і 8.091501 "Комп'ютерні системи та мережі" 7.091503 і 8.091503 “Спеціалізовані комп'ютерні системи.

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

...