МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
Основні формулиТеореми, що пояснюють суть перетворення Фур’є (наведені без доведення). Теорема 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) Читайте також:
|
||||||||
|