Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






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

Теореми, що пояснюють суть перетворення Фур’є (наведені без доведення).

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

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

(2.4)

Теорема 3.

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

(2.5)

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

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

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

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

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

x[even]n = x2n, x[odd]n = x2n+1, (2.6)

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

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

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

(2.7).

Формула (2.7) дозволяє скоротити число множень удвічі (не враховуючи множень при обчисленні X[even]k і X [odd]k), якщо обчислювати Xk не послідовно від 0 до N - 1, а попарно: X0 і XN/2, X1 і XN/2+1,..., XN/ 2-1 і XN. Пари утворяться за принципом: Xk і XN/2+k.

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

(2.8)

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

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

Розглянемо ШПФ для різних N. Додамо ще один нижній індекс, який буде вказувати на загальну кількість елементів послідовності, до якої цей елемент належить. Тобто X{R}k - це k-ий елемент послідовності {X{R}} з R елементів. X{R}[even]k - це k-ий елемент послідовності {X{R}[even]} з R елементів, обчислений по парних елементах послідовності {X{2R}}. X{R}[odd]k - це k-ий елемент послідовності {X{R}[odd]}, обчислений по непарних елементах послідовності {X{2R}}.

У випадку, коли доданок лише один (N = 1) формула (1) спрощується до:

,

Оскільки в цьому випадку k може бути рівне тільки 0, то X{1}0 = x{1}0, тобто, ДПФ над одним числом дає це ж саме число.

Для N = 2 за теоремою (2.5) отримаємо:

Для N = 4 за теоремою (2.5) отримаємо:

Звідси виходить, що якщо елементи вихідної послідовності були дійсними, то при збільшенні N елементи ДПФ стають комплексними.

Для N = 8 за теоремою (2.5) отримаємо:

Необхідно звернути увагу, що на попередньому кроці використовувалися ступені W4, а на цьому - ступені W8. Зайвих обчислень можна уникнути, якщо врахувати, що

Тоді формули для N=4 будуть використовувати ті ж W-множники, що і формули для N=8:

Висновок:

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

(2.9)


Читайте також:

  1. II. Основні закономірності ходу і розгалуження судин великого і малого кіл кровообігу
  2. Адвокатура в Україні: основні завдання і функції
  3. Амортизація основних засобів, основні методи амортизації
  4. Артеріальний пульс, основні параметри
  5. Банківська система та її основні функції
  6. Безпосереднє обчислення з використанням формули Ньютона-Лейбніца.
  7. Біржові товари і основні види товарних бірж. Принципи товарних бірж.
  8. Будова й основні елементи машини
  9. Будова оптоволокна та основні фізичні явища в оптоволокні.
  10. Бюджетування (основні поняття, механізм).
  11. Валютний ринок, основи його функціонування. Основні види валютних операцій
  12. Варіатори та їхні основні параметри




Переглядів: 909

<== попередня сторінка | наступна сторінка ==>
Основні положення алгоритму ШПФ | Організація DSP- процесорів для задач опрацювання сигналів та зображень

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.006 сек.