Главная » Программирование звука » Как оценить весь спектр

0

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

«Короткие» БПФ

Чтобы  объяснить  алгоритм  БПФ,  я  начну  с  рассмотрения  небольшого  количества отсчетов. Я хочу узнать, сколько информации о частотах содержится в небольшом количестве отсчетов.

B  качестве  предельного  случая  посмотрим,  что  произойдет,  если  у  нас  всего одна выборка. Нужна всего одна частота, чтобы полностью описать эту выборку.

Проще  всего  использовать  нулевую  частоту.  Сигнал  нулевой  частоты  имеет  толь-

ко амплитуду и часто называется инженерами постоянным током (DC).

Следующий  шаг   рассмотреть  две  выборки.  Как  можно  было  бы  предположить,  две  выборки  могут  полностью  быть  описаны  двумя  частотами:  нулевой и половинной частотой дискретизации (S/2).

Ha  рис.  24.6  показаны  некоторые  возможные  варианты  для  двух  отсчетов. B каждом столбце даны две выборки, а также способ их описания как суммы синусоиды нулевой частоты и синусоиды с частотой S/2.

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

Следует  обратить  внимание  на  последние  два  замечания.  B  разделе  «Побочные  эффекты  дискретизации»  в  третьей  главе  я  говорил,  что  половина  частоты дискретизации   это  волшебный  предел;  никакой  дискретный  сигнал  не  может иметь частоту его превышающую. Так как же две трети или три четверти частоты дискретизации   могут   являться   компонентами   звукового   сигнала?   Исчерпывающий  ответ  на  этот  вопрос  основан  на  том  факте,  что  ДПФ  работает  с  сигналами, представленными  комплексными  числами,  для  которых  предел  Найквиста  трактуется несколько иначе.

K  счастью,  при  обработке  аудио  необходимы  лишь  сигналы,  представленные действительными числами. Хотя ДПФ и требует, чтобы вы работали с диапазоном

частот от 0 до S, область от S/2 до 5 является зеркальным  отображением области от 0 до S/2. Многие находят более удобным преобразовать спектр ДПФ так, чтобы он располагался в пределах от -S/2 до S/2, как показано на рис. 24.7.

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 Programmer’s Guide to Sound: Пер. с англ. М.: ДМК Пресс, 2000. 432 с, ил. (Серия «Для программистов»).

По теме:

  • Комментарии