Як оцінити весь спектр

B 60-x роках нашого століття Кулі (Cooley) і Таки (Tuckey) відкрили метод обчислення ДПФ, що більше підходить для використання на практиці Їх алгоритм швидкого перетворення Фурє (ШПФ) ефективно обраховує весь спектр відразу B даний час існує безліч злегка розрізняються алгоритмів ШПФ Ми з вами будемо орієнтуватися на один широко використовуваний метод, який швидко обраховує спектр, вважаючи, що кількість відліків є ступенем двійки Це не найшвидший алгоритм ШПФ, однак він відносно простий для розуміння і досить швидкий для досягнення більшості цілей

«Короткі» БПФ

Щоб пояснити алгоритм ШПФ, я почну з розгляду невеликої кількості відліків Я хочу дізнатися, скільки інформації про частоти міститься в невеликій кількості відліків

B якості граничного випадку подивимося, що станеться, якщо у нас всього одна вибірка Потрібна лише одна частота, щоб повністю описати цю вибірку

Найпростіше використовувати нульову частоту Сигнал нульової частоти має толь-

ко амплітуду і часто називається інженерами постійним струмом (DC)

Наступний крок розглянути дві вибірки Як можна було б припустити, дві вибірки можуть повністю бути описані двома частотами: нульовий і половинної частотою дискретизації (S/2)

Ha рис 246 показані деякі можливі варіанти для двох відліків B кожному стовпці дано дві вибірки, а також спосіб їх опису як суми синусоїди нульової частоти і синусоїди з частотою S/2

Аналогічним чином, три відліку можуть бути описані трьома частотами: нульовий, третій частоти дискретизації і двома третинами частоти дискретизації Чотири відліку описуються чотирма частотами, що лежать в діапазоні від нуля до трьох чвертей частоти дискретизації

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

K щастя, при обробці аудіо необхідні лише сигнали, представлені дійсними числами Хоча ДПФ і вимагає, щоб ви працювали з діапазоном

частот від 0 до S, область від S/2 до 5 є дзеркальним відображенням області від 0 до S/2 Багато хто знаходить більш зручним перетворити спектр ДПФ так, щоб він розташовувався в межах від -S/2 до S/2, як показано на рис 247

Ha насправді це відображення не зовсім дзеркальне Одна половина комплексно сполучена з іншого дійсні частини однакові, а уявні протилежні за знаком

Розкладання «довгих» БПФ

Тепер припустимо, що у нас є 1024 відліку і потрібно обчислити їх спектр З вищесказаного ясно, що результатом буде 1024 комплексних числа, що представляють амплітуду і фазу рівномірно розташованих частот в діапазоні від 0 до 1023/1024 частоти дискретизації

Ці 1024 відліку можна розглядати як точки в безперервному сигналі Ми просто знімаємо значення в рівномірно розподілених точках і розглядаємо їх як репрезентативну вибірку Потім має сенс вибрати 512 рівномірно

відстоять точок (кожен другий відлік) і визначити їх спектр Цей менший

спектр буде описуватися рівномірно віддаленими частотами в діапазоні від 0 до

511/512 частоти дискретизації, які є половинними значеннями цікавлять нас частот

Алгоритм ШПФ заснований на цій ідеї ДПФ для 1024 відліків може бути розбите на два ДПФ для 512 відліків, одне з яких працює з парними,

а інше з непарними отсчетами B результаті вийдуть два 512-точкових

спектру їх необхідно певним чином скомбінувати для отримання повного 1024-точкового спектру

Щоб обчислити ДПФ для 512 відліків, ми розбиваємо його на два ДПФ для

256 відліків, і тд При такому підході ми, нарешті, доберемося до обчислення

ДПФ для двох відліків

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

Двухточечное БПФ

Якщо є два відліку, відразу видно, що компонента нульової частоти –

це середнє значення двох відліків З аналогічних міркувань компонента

частотою S / 2 це половина різниці B символічного запису представимо вищесказане так:

A0=1/2(s0 + s1) A1=1/2(s0 s1)

Це і є двухточечное БПФ, яке використовує як основа самого поширеного алгоритму ШПФ Зверніть увагу на шаблонну послідовність з додавання і подальшого віднімання

Чотирьохточкові БПФ

Щоб показати, як обєднуються зворотні перетворення в більш довгі, я розгляну 4-точкове ШПФ для відліків s0, s1, s2 і s3 з метою обчислення амплітуди (і фази) чотирьох частотнулевой, S / 4, S / 2 і 3S / 4

Якщо я маю тільки s0 і s2, я отримую два відліку на половинній частоті дискретизації Використовуючи наведені вище формули для двухточечного БПФ, я можу вирахувати компоненту нульової частоти (S0 + s2) / 2 і другу компоненту (s0 s2) / 2 для половинної частоти дискретизації цього набору, тобто S / 4

Я можу провести ті ж самі обчислення для s1 і s3, що дасть мені ще одну

пару значень компоненти нульової частоти і компоненти S / 4 Другі значення

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

Важливо, що частотна інформація, отримана з s0 і s2, знаходиться у фазі, відмінною від фази, отриманої від s1 і s3 Ви можете провести узгодження по фазі, помноживши останні значення накоефіцієнт зсуву по фазірівний-i Особливістю значення-i є те, що (-i) 4 = l, тому-i представляє зсув одного відліку з чотирьох

Кінцеві формули 4-точеченого БПФ такі:

A0=l/4((s0 + s2) + (sl + s3)) A1=l/4((s0 s2) + (-i) * (s1 s3)) A2=l/4((s0 + s2) (sl + s3)) A3=l/4((s0 s2) (-i) * (sl s3))

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

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

Формальний висновок БПФ

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

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

Раніше я говорив, що основною ідеєю БПФ полягає в тому, що кожну другу вибірку можна використовувати для отримання половинного спектра Формально це означає, що формула ДПФ може бути представлена ​​у вигляді двох сум Перша містить всі парні компоненти оригіналу, друга всі непарні:

−1

A   =   ∑ s e − 2πift / N

t = 0

( N / 2 ) −1

( N / 2 ) −1

=       ∑ s 2 t

t = 0

e − 2πif ( 2 t ) / N   +

s

t = 0

2 t +1

− 2πif ( 2 t +1) / N

Після невеликих перетворень ці дві суми можна записати по-іншому:

N −1

A   =   ∑ s e − 2πift / N

t = 0

( N / 2 ) −1

( N / 2 ) −1

=     ∑ s 2 t

t = 0

e − 2πift /( N / 2 )  + e − 2πif  / N

s

t = 0

2 t +1

− 2πift /( N / 2 )

Зауважимо, що дві останні суми в точності відповідають N/2-точечному ДПФ Перша ДПФ для парних вибірок, другий ДПФ для непарних вибірок Множник e-2πf / Ν, що стоїть перед другим сумою, і є коефіцієнт зсуву по фазі, про який я говорив раніше B випадку N = 4 отримуємо чотири коефіцієнта фазового зсуву, один для кожної частоти З формули видно, що вони рівні

1,-i, -1 = (-i) 2 і i = (-i) 3 (Порівняйте отримані значення з формулою з попе-

ного розділу)

Зверніть увагу, що коефіцієнти зсуву по фазі зявляються парами Якщо ви складете список з коефіцієнтів зсуву по фазі для конкретного значення N, друга половина списку буде містити значення першої половини з протилежним знаком Звідси і отримуємо шаблонну послідовність складань і вирахувань, про яку я говорив у попередньому розділі

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

Джерело: Кінтцель Т Керівництво програміста по роботі зі звуком = A Programmers Guide to Sound: Пер з англ М: ДМК Пресс, 2000 432 с, іл (Серія «Для програмістів»)

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*