Студопедия
Контакти
 


Тлумачний словник

Реклама: Настойка восковой моли




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

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

Теорема 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. Варіатори та їхні основні параметри




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

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


 

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


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