Алгоритм Герцеля

редактировать

Алгоритм Герцеля - это метод цифровой обработки сигналов (DSP) для эффективного оценка отдельных членов дискретного преобразования Фурье (ДПФ). Это полезно в некоторых практических приложениях, таких как распознавание тонов двухтональной многочастотной сигнализации (DTMF), производимых кнопками клавиатуры традиционного аналогового телефона. Алгоритм был впервые описан Джеральдом Гертцеля в 1958 году.

Как и DFT, алгоритм Гертцеля анализирует одну выбираемую частотную составляющую из дискретного сигнала. В отличие от прямых вычислений ДПФ, алгоритм Герцеля применяет один действительный коэффициент на каждой итерации, используя действительную арифметику для действительных входных последовательностей. Для покрытия всего спектра алгоритм Герцеля имеет более высокий порядок сложности, чем алгоритмы быстрого преобразования Фурье (БПФ), но для вычисления небольшого количества выбранных частотных компонентов он более численно эффективный. Простая структура алгоритма Герцеля делает его хорошо подходящим для небольших процессоров и встроенных приложений.

Алгоритм Герцеля можно также использовать «в обратном порядке» в качестве функции синтеза синусоиды, для которой требуется только 1 умножение и 1 вычитание для каждой сгенерированной выборки.

Содержание

1 Алгоритм
2 Числовой стабильность
3 Вычисления ДПФ
4 Приложения
- 4.1 Члены спектра мощности
- 4.2 Одиночный член ДПФ с вещественной арифметикой
- 4.3 Обнаружение фазы
- 4.4 Комплексные сигналы в реальной арифметике
5 Вычислительная сложность
6 См. Также
7 Ссылки
8 Дополнительная литература
9 Внешние ссылки

Алгоритм

Основное вычисление в алгоритме Герцеля имеет форму цифровой фильтр, и по этой причине алгоритм часто называют фильтром Герцеля. Фильтр работает с входной последовательностью $x [n] {\ displaystyle x [n]}$ $x [n]$ в каскаде из двух этапов с параметром $ω 0 {\ displaystyle \ omega _ {0 }}$ $\ omega _ {0}$ , задающая частоту для анализа, нормированную на радиан на выборку.

На первом этапе вычисляется промежуточная последовательность, $s [n] {\ displaystyle s [n]}$ $s [n]$ :

s [n] = x [n] + 2 cos ⁡ (ω 0) s [n - 1] - s [n - 2]. {\ displaystyle s [n] = x [n] +2 \ cos (\ omega _ {0}) s [n-1] -s [n-2].}

{\ displaystyle s [n] = x [n] +2 \ соз (\ omega _ {0}) s [n-1] -s [n-2].}

(1)

Второй stage применяет следующий фильтр к $s [n] {\ displaystyle s [n]}$ $s [n]$ , создавая выходную последовательность $y [n] {\ displaystyle y [n]}$ $y [n]$ :

y [n] = s [n] - e - j ω 0 s [n - 1]. {\ displaystyle y [n] = s [n] -e ^ {- j \ omega _ {0}} s [n-1].}

{\ displaystyle y [n] = s [n] -e ^ {- j \ omega _ {0}} s [n-1].}

(2)

Первый этап фильтрации можно наблюдать до быть БИХ-фильтром второго порядка со структурой прямой формы. Эта конкретная структура обладает тем свойством, что ее внутренние переменные состояния равны прошлым выходным значениям этого этапа. Предполагается, что входные значения $x [n] {\ displaystyle x [n]}$ $x [n]$ для $n < 0 {\displaystyle n<0}$ $n <0$ равны 0. Чтобы установить начальное состояние фильтра, чтобы оценка могла начаться с образца $x [0] {\ displaystyle x [0]}$ ${\ displaystyle x [0]}$ , состояниям фильтра присваиваются начальные значения $s [- 2] = s [- 1] = 0 {\ displaystyle s [-2] = s [-1] = 0}$ ${\ displaystyle s [-2] = s [-1] = 0}$ . Чтобы избежать опасности наложения, частота $ω 0 {\ displaystyle \ omega _ {0}}$ $\ omega _ {0}$ часто ограничивается диапазоном от 0 до π (см. Найквист – Шеннон теорема выборки ); использование значения вне этого диапазона не бессмысленно, но эквивалентно использованию частоты с псевдонимом внутри этого диапазона, поскольку экспоненциальная функция является периодической с периодом 2π в $ω 0 {\ displaystyle \ omega _ {0}}$ $\ omega _ {0}$ .

Фильтр второй ступени можно наблюдать как КИХ-фильтр, поскольку его вычисления не используют никакие из его прошлых выходных сигналов.

Методы Z-преобразования могут применяться для изучения свойств каскада фильтров. Z-преобразование первой ступени фильтра, заданное в уравнении (1), равно

S (z) X (z) = 1 1 - 2 cos ⁡ (ω 0) z - 1 + z - 2 = 1 (1 - e + j ω 0 z - 1) (1 - e - j ω 0 z - 1). {\ displaystyle {\ begin {align} {\ frac {S (z)} {X (z)}} = {\ frac {1} {1-2 \ cos (\ omega _ {0}) z ^ { -1} + z ^ {- 2}}} \\ = {\ frac {1} {(1-e ^ {+ j \ omega _ {0}} z ^ {- 1}) (1-e ^ {-j \ omega _ {0}} z ^ {- 1})}}. \ end {align}}}

{\ Displaystyle {\ begin {align} {\ frac {S (z)} {X (z)}} = {\ frac {1} {1-2 \ cos (\ omega _ {0}) z ^ {- 1} + z ^ {- 2}}} \\ = {\ frac {1} {(1-e ^ {+ j \ omega _ {0}} z ^ {- 1}) (1-e ^ {- j \ omega _ {0}} z ^ {- 1})}}. \ End {align}}}

(3)

Z-преобразование второй ступени фильтрации, заданное в уравнении (2) равно

Y (z) S (z) = 1 - e - j ω 0 z - 1. {\ displaystyle {\ frac {Y (z)} {S (z)}} = 1-e ^ {- j \ omega _ {0}} z ^ {- 1}.}

{\ displaystyle {\ frac {Y (z)} {S (z)}} = 1-e ^ {- j \ omega _ {0}} z ^ {- 1}.}

(4)

Комбинированная передаточная функция каскада двух каскадов фильтра будет тогда

S (z) X (z) Y (z) S (z) = Y (z) X (z) = (1 - e - j ω 0 z - 1) (1 - e + j ω 0 z - 1) (1 - e - j ω 0 z - 1) = 1 1 - e + j ω 0 z - 1. {\ Displaystyle {\ begin {align} {\ frac {S (z)} {X (z)}} {\ frac {Y (z)} {S (z)}} = {\ frac {Y (z) } {X (z)}} = {\ frac {(1-e ^ {- j \ omega _ {0}} z ^ {- 1})} {(1-e ^ {+ j \ omega _ { 0}} z ^ {- 1}) (1-e ^ {- j \ omega _ {0}} z ^ {- 1})}} \\ = {\ frac {1} {1-e ^ { + j \ omega _ {0}} z ^ {- 1}}}. \ end {align}}}

{\ displaystyle {\ begin {align} {\ frac {S (z)} {X (z)}} {\ frac { Y (z)} {S (z)}} = {\ frac {Y (z)} {X (z)}} = {\ frac {(1-e ^ {- j \ omega _ {0}}) z ^ {- 1})} {(1-e ^ {+ j \ omega _ {0}} z ^ {- 1}) (1-e ^ {- j \ omega _ {0}} z ^ {- 1})}} \\ = {\ frac {1} {1-e ^ {+ j \ omega _ {0}} z ^ {- 1}}}. \ End {align}}}

(5)

Это может быть преобразовано обратно в эквивалентную последовательность во временной области, а термины развернут обратно к первому входному элементу с индексом $n = 0 {\ displaystyle n = 0}$ $n = 0$ :

y [n] = x [n] + e + j ω 0 y [n - 1] = ∑ k = - ∞ nx [k] e + j ω 0 (n - k) = ej ω 0 n ∑ k = 0 nx [k] e - j ω 0 k, поскольку ∀ k < 0, x [ k ] = 0. {\displaystyle {\begin{aligned}y[n]=x[n]+e^{+j\omega _{0}}y[n-1]\\=\sum _{k=-\infty }^{n}x[k]e^{+j\omega _{0}(n-k)}\\=e^{j\omega _{0}n}\sum _{k=0}^{n}x[k]e^{-j\omega _{0}k}\qquad {\text{since }}\forall k<0,x[k]=0.\end{aligned}}}

{\ displaystyle {\ begin {выровнено} y [n] = x [n] + e ^ {+ j \ omega _ {0}} y [n-1] \\ = \ sum _ {k = - \ infty} ^ {n} x [k] e ^ {+ j \ omega _ {0 } (nk)} \\ = e ^ {j \ omega _ {0} n} \ sum _ {k = 0} ^ {n} x [k] e ^ {- j \ omega _ {0} k} \ qquad {\ текст {поскольку}} \ forall k <0, x [k] = 0. \ end {align}}}

(6)

Числовая устойчивость

Можно заметить, что полюса преобразования Z фильтра расположены в $e + j ω 0 {\ displaystyle e ^ {+ j \ omega _ {0}}}$ ${\ displaystyle e ^ {+ j \ omega _ {0}}}$ и $e - j ω 0 {\ displaystyle e ^ {- j \ omega _ {0}}}$ ${\ displaystyle e ^ {- j \ omega _ {0}}}$ на окружности единичного радиуса с центром в начале плоскости комплексного Z-преобразования. Это свойство указывает, что процесс фильтрации является предельно стабильным и уязвим для накопления числовых ошибок при вычислении с использованием арифметических операций с низкой точностью и длинных входных последовательностей. Численно стабильная версия была предложена Кристианом Райншем.

Вычисления ДПФ

Для важного случая вычисления члена ДПФ применяются следующие специальные ограничения.

Фильтрация завершается с индексом $n = N {\ displaystyle n = N}$ ${\ displaystyle n = N}$ , где $N {\ displaystyle N}$ $N$ - количество терминов в входная последовательность ДПФ.
Частоты, выбранные для анализа Гертцеля, ограничены специальной формой

ω 0 = 2 π k N. {\ displaystyle \ omega _ {0} = 2 \ pi {\ frac {k} {N}}.}

{\ displaystyle \ omega _ {0} = 2 \ pi {\ frac {k} {N} }.}

(7)

Номер индекса $k {\ displaystyle k}$ $к$ , указывающий, что «элемент разрешения по частоте» ДПФ выбирается из набора индексных номеров

k ∈ {0, 1, 2,..., N - 1}. {\ displaystyle k \ in \ {0,1,2,..., N-1 \}.}

{\ displaystyle k \ in \ {0,1,2,..., N-1 \}.}

(8)

Выполнение этих замен в уравнении (6) и наблюдение, что член $e + j 2 π k = 1 {\ displaystyle e ^ {+ j2 \ pi k} = 1}$ ${ \ displaystyle e ^ {+ j2 \ pi k} = 1}$ , тогда уравнение (6) принимает следующий вид:

y [N] = ∑ n = 0 N x [n] e - j 2 π nk N. {\ displaystyle y [N] = \ sum _ {n = 0} ^ {N} x [n] e ^ {- j2 \ pi {\ frac {nk} {N}}}.}

{\ displaystyle y [N] = \ sum _ {n = 0} ^ {N} x [n] e ^ {- j2 \ pi {\ frac {nk} {N}}}.}

(9)

Мы можем заметить, что правая часть уравнения (9) очень похожа на формулу, определяющую член ДПФ $X [k] {\ displaystyle X [k]}$ $X [k]$ , член ДПФ для порядкового номера $k {\ displaystyle k}$ $к$ , но не совсем то же самое. Для суммирования, показанного в уравнении (9), требуется $N + 1 {\ displaystyle N + 1}$ $N + 1$ входных членов, но только $N {\ displaystyle N}$ $N$ входных членов. доступны при оценке ДПФ. Простой, но неэлегантный прием - расширить входную последовательность $x [n] {\ displaystyle x [n]}$ $x [n]$ еще одним искусственным значением $x [N] = 0 {\ displaystyle x [N] = 0}$ ${\ displaystyle x [N] = 0}$ . Из уравнения (9) видно, что математический эффект на конечный результат такой же, как и при удалении члена $x [N] {\ displaystyle x [N]}$ ${\ displaystyle x [N]}$ из суммирования, что дает предполагаемое значение DFT.

Однако есть более элегантный подход, позволяющий избежать лишнего прохода фильтра. Из уравнения (1) мы можем отметить, что когда расширенный входной член $x [N] = 0 {\ displaystyle x [N] = 0}$ ${\ displaystyle x [N] = 0}$ используется на последнем этапе,

s [N] = 2 cos ⁡ (ω 0) s [N - 1] - s [N - 2]. {\ displaystyle s [N] = 2 \ cos (\ omega _ {0}) s [N-1] -s [N-2].}

{\ displaystyle s [N] = 2 \ cos (\ omega _ {0}) s [N-1] -s [N-2]. }

(10)

Таким образом, алгоритм может быть завершен следующим образом:

завершить БИХ-фильтр после обработки входного члена $x [N - 1] {\ displaystyle x [N-1]}$ ${\ displaystyle x [N-1]}$ ,
применить уравнение (10) для построения $s [N] {\ displaystyle s [N]}$ ${\ displaystyle s [N]}$ из предыдущих выходных данных $s [N - 1] {\ displaystyle s [N-1]}$ ${\ displaystyle s [N-1]}$ и $s [N - 2] {\ displaystyle s [N-2]}$ ${\ displaystyle s [N-2]}$ ,
применить уравнение (2) с вычисленным значением $s [N] {\ displaystyle s [N]}$ ${\ displaystyle s [N]}$ и с $s [N - 1] {\ displaystyle s [N-1]}$ ${\ displaystyle s [N-1]}$ , полученный в результате окончательного прямого вычисления фильтра.

Последние две математические операции упрощаются за счет их алгебраического объединения:

y [N] = s [N] - e - j 2 π k N s [N - 1] = (2 cos ⁡ (ω 0) s [N - 1] - s [N - 2]) - e - j 2 π k N s [N - 1] = ej 2 π k N s [N - 1] - s [N - 2]. {\ displaystyle {\ begin {align} y [N] = s [N] -e ^ {- j2 \ pi {\ frac {k} {N}}} s [N-1] \\ = (2 \ cos (\ omega _ {0}) s [N-1] -s [N-2]) - e ^ {- j2 \ pi {\ frac {k} {N}}} s [N-1] \ \ = e ^ {j2 \ pi {\ frac {k} {N}}} s [N-1] -s [N-2]. \ end {align}}}

{\ displaystyle {\ begin {align} y [N] = s [N] -e ^ {- j2 \ pi {\ frac {k} {N}}} s [N-1] \\ = (2 \ cos (\ omega _ {0}) s [N-1] -s [N-2]) - e ^ {- j2 \ pi {\ frac {k} { N}}} s [N-1] \\ = e ^ {j2 \ pi {\ frac {k} {N}}} s [N-1] -s [N-2]. \ End {выравнивается} }}

(11)

Обратите внимание, что при остановке обновлений фильтра в элементе $N - 1 {\ displaystyle N-1}$ $N-1$ и немедленном применении уравнения (2), а не уравнения (11), последние обновления состояния фильтра не обновляются, что дает результат с неправильной фазой.

Конкретная структура фильтрации, выбранная для алгоритма Герцеля, является ключом к его эффективным вычислениям ДПФ. Мы можем заметить, что только одно выходное значение $y [N] {\ displaystyle y [N]}$ ${\ displaystyle y [N]}$ используется для вычисления ДПФ, поэтому вычисления для всех остальных выходных членов опускаются. Поскольку КИХ-фильтр не вычисляется, вычисления этапа БИХ $s [0], s [1] {\ displaystyle s [0], s [1]}$ ${\ displaystyle s [0], s [1]}$ и т. Д. Могут быть немедленно отброшены. после обновления внутреннего состояния первого этапа.

Это, кажется, оставляет парадокс: для завершения алгоритма этап КИХ-фильтра должен быть оценен один раз с использованием двух последних выходных сигналов этапа БИХ-фильтра, в то время как для вычислительной эффективности итерация БИХ-фильтра отбрасывает свои выходные значения. Здесь применяются свойства структуры фильтра прямой формы. Две внутренние переменные состояния БИХ-фильтра обеспечивают последние два значения выходного БИХ-фильтра, которые являются условиями, необходимыми для оценки каскада КИХ-фильтра.

Приложения

Члены спектра мощности

Изучив уравнение (6), последний проход БИХ-фильтра для вычисления члена $y [N] {\ displaystyle y [N ]}$ ${\ displaystyle y [N]}$ с использованием дополнительного входного значения $x [N] = 0 {\ displaystyle x [N] = 0}$ ${\ displaystyle x [N] = 0}$ применяет комплексный множитель величины 1 к предыдущему члену $y [N - 1] {\ displaystyle y [N-1]}$ ${\ displaystyle y [N-1]}$ . Следовательно, $y [N] {\ displaystyle y [N]}$ ${\ displaystyle y [N]}$ и $y [N - 1] {\ displaystyle y [N-1]}$ ${\ displaystyle y [N-1]}$ представляют эквивалентная мощность сигнала. Точно так же можно применить уравнение (11) и вычислить мощность сигнала из члена $y [N] {\ displaystyle y [N]}$ ${\ displaystyle y [N]}$ или применить уравнение (2) и вычислить мощность сигнала из термина $y [N - 1] {\ displaystyle y [N-1]}$ ${\ displaystyle y [N-1]}$ . Оба случая приводят к следующему выражению для мощности сигнала, представленного членом ДПФ $X [k] {\ displaystyle X [k]}$ $X [k]$ :

X [k] X ′ [k] = y [N] y ′ [ N] = y [N - 1] y ′ [N - 1] = s 2 [N - 1] + s 2 [N - 2] - 2 cos ⁡ (2 π k N) s [N - 1] s [ N - 2]. {\ Displaystyle {\ begin {выровнен} Икс [к] \, X '[k] = y [N] \, y' [N] = y [N-1] \, y '[N-1] \ \ = s ^ {2} [N-1] + s ^ {2} [N-2] -2 \ cos \ left (2 \ pi {\ frac {k} {N}} \ right) \, s [N-1] \, s [N-2]. \ End {align}}}

{\begin{aligned}X[k]\,X'[k]=y[N]\,y'[N]=y[N-1]\,y'[N-1]\\=s^{2}[N-1]+s^{2}[N-2]-2\cos \left(2\pi {\frac {k}{N}}\right)\,s[N-1]\,s[N-2].\end{aligned}}

(12)

В псевдокоде ниже переменные sprevи sprev2временно хранят историю вывода из IIR-фильтра, в то время как x [n]является индексированным элементом массива x, в котором хранится ввод.

Nterms, определенные здесь Kterm, выбранные здесь ω = 2 × π × Kterm / Nterms; cr: = cos (ω) ci: = sin (ω) coeff: = 2 × cr sprev: = 0 sprev2: = 0 для каждого индекса n в диапазоне от 0 до Nterms-1 do s: = x [n] + coeff × sprev - sprev2 sprev2: = sprev sprev: = s end power: = sprev2 × sprev2 + sprev × sprev - coeff × sprev × sprev2

Вычисления можно организовать так, чтобы входящие выборки доставлялись по отдельности в программный объект, который поддерживает состояние фильтра между обновлениями, с доступом к окончательному результату мощности после выполнения другой обработки.

Одиночный член ДПФ с вещественной арифметикой

Случай с действительными входными данными возникает часто, особенно во встроенных системах, где входные потоки являются результатом прямых измерений физических процессов. По сравнению с иллюстрацией в предыдущем разделе, когда входные данные являются действительными, переменные внутреннего состояния фильтра sprevи sprev2также могут быть действительными, следовательно, на первом этапе ИИХ не требуется сложной арифметики. Оптимизация для вещественной арифметики обычно так же проста, как применение соответствующих типов данных с действительным знаком для переменных.

После вычислений с использованием входного члена $x [N - 1] {\ displaystyle x [N-1]}$ ${\ displaystyle x [N-1]}$ и завершения итераций фильтра, уравнение (11) должно быть применяется для оценки члена ДПФ. В окончательном вычислении используется комплексная арифметика, но ее можно преобразовать в действительную арифметику путем разделения действительных и мнимых членов:

cr = cos ⁡ (2 π k N), ci = sin ⁡ (2 π k N), y [N] = crs [N - 1] - s [N - 2] + jcis [N - 1]. {\ displaystyle {\ begin {align} c_ {r} = \ cos (2 \ pi {\ tfrac {k} {N}}), \\ c_ {i} = \ sin (2 \ pi {\ tfrac {k} {N}}), \\ y [N] = c_ {r} s [N-1] -s [N-2] + jc_ {i} s [N-1]. \ end {выровнено }}}

{\ displaystyle { \ begin {align} c_ {r} = \ cos (2 \ pi {\ tfrac {k} {N}}), \\ c_ {i} = \ sin (2 \ pi {\ tfrac {k} { N}}), \\ y [N] = c_ {r} s [N-1] -s [N-2] + jc_ {i} s [N-1]. \ End {align}}}

(13)

По сравнению с приложением спектра мощности, единственная разница заключается в вычислении, используемом для завершения:

(те же вычисления БИХ-фильтра, что и в реализации мощности сигнала) XKreal = sprev * cr - sprev2; XKimag = sprev * ci;

Обнаружение фазы

Это приложение требует такой же оценки члена ДПФ $X [k] {\ displaystyle X [k]}$ $X [k]$ , как обсуждалось в предыдущем раздел, используя поток ввода с действительным или комплексным знаком. Тогда фаза сигнала может быть оценена как

ϕ = tan - 1 ⁡ ℑ (X [k]) ℜ (X [k]), {\ displaystyle \ phi = \ tan ^ {- 1} {\ frac {\ Im (X [k])} {\ Re (X [k])}},}

{\ displaystyle \ phi = \ tan ^ {- 1} {\ frac {\ Im (X [k])} {\ Re (X [k])}},}

(14)

принимая соответствующие меры предосторожности для сингулярностей, квадранта и т. Д. При вычислении функции обратной касательной.

Сложные сигналы в действительной арифметике

Поскольку комплексные сигналы линейно разлагаются на действительную и мнимую части, алгоритм Герцеля можно вычислить в действительной арифметике отдельно по последовательности действительных частей, давая $лет [n] {\ displaystyle y _ {\ text {r}} [n]}$ ${\ displaystyle y _ {\ text {r}} [n]}$ , и над последовательностью мнимых частей, давая $yi [n] {\ displaystyle y _ {\ text {i }} [n]}$ ${\ displaystyle y _ {\ text {i}} [n]}$ . После этого два комплексных частичных результата могут быть повторно объединены:

y [n] = y r [n] + j y i [n]. {\ displaystyle y [n] = y _ {\ text {r}} [n] + jy _ {\ text {i}} [n].}

{\ displaystyle y [n] = y_ {\ text {r}} [n] + jy _ {\ text {i}} [n].}

(15)

Вычислительная сложность

Согласно теория вычислительной сложности, вычисление набора из $M {\ displaystyle M}$ $M$ терминов DFT с использованием $M {\ displaystyle M}$ $M$ приложений Goertzel алгоритм для набора данных со значениями $N {\ displaystyle N}$ $N$ с «стоимостью операции» $K {\ displaystyle K}$ $K$ имеет сложность $O (KNM) {\ displaystyle O (KNM)}$ $O (KNM)$ .

Для вычисления одного DFT bin

X (f) {\ displaystyle X (f)}

Икс (е)

для сложной входной последовательности длиной

N {\ displaystyle N}

N

алгоритм Герцеля требует

2 N {\ displaystyle 2N}

2N

умножений и

4 N {\ displaystyle 4 \ N}

4 \ N

сложения / вычитания внутри цикла, а также 4 умножения и 4 финальных сложения / вычитания, всего

2 N + 4 {\ displaystyle 2N + 4}

2N + 4

умножения и

4 N + 4 {\ displaystyle 4N + 4}

4N + 4

сложения / вычитания. Это повторяется для каждой из частот

M {\ displaystyle M}

M

Напротив, использование FFT на наборе данных с $N {\ displaystyle N}$ $N$ значения имеют сложность $O (KN log ⁡ N) {\ displaystyle O (KN \ log N)}$ $O (KN \ log N)$ .

Это сложнее применить напрямую, потому что это зависит от используемого алгоритма БПФ, но типичным примером является БПФ с основанием 2, для которого требуется

2 log 2 ⁡ (N) {\ displaystyle 2 \ log _ {2} (N)}

{\ displaystyle 2 \ log _ {2} (N)}

умножения и

3 журнал 2 ⁡ (N) {\ displaystyle 3 \ log _ {2} (N)}

{\ displaystyle 3 \ log _ {2} (N)}

сложений / вычитаний на DFT bin для каждого из

N {\ displaystyle N}

N

интервалов.

В выражениях порядка сложности, когда количество вычисляемых членов $M {\ displaystyle M}$ $M$ меньше, чем $log ⁡ N { \ displaystyle \ log N}$ $\ log N$ , преимущество алгоритма Герцеля очевидно. Но поскольку код БПФ сравнительно сложен, коэффициент «затраты на единицу работы» $K {\ displaystyle K}$ $K$ часто больше для БПФ, и практическое преимущество отдает предпочтение алгоритму Герцеля даже для $M {\ displaystyle M}$ $M$ в несколько раз больше, чем $log 2 ⁡ (N) {\ displaystyle \ log _ {2} (N)}$ $\ log _ {2} (N)$ .

Как на практике для определения того, является ли БПФ с основанием 2 или алгоритм Герцеля более эффективным, отрегулируйте количество членов $N {\ displaystyle N}$ $N$ в наборе данных вверх до ближайшей точной степени 2, вызывая это $N 2 {\ displaystyle N_ {2}}$ $N_ {2}$ , и алгоритм Герцеля, вероятно, будет быстрее, если

M ≤ 5 N 2 6 N log 2 ⁡ (N 2) {\ displaystyle M \ leq {\ frac {5N_ {2}} {6N}} \ log _ {2} (N_ {2})}

{\ displaystyle M \ leq {\ frac {5N_ {2}} {6N}} \ log _ {2} (N_ {2 })}

Реализации БПФ и платформы обработки оказывают значительное влияние на относительную производительность. Некоторые реализации БПФ выполняют внутренние вычисления комплексных чисел для генерации коэффициентов на лету, значительно увеличивая их «стоимость K на единицу работы». Алгоритмы БПФ и ДПФ могут использовать таблицы предварительно вычисленных значений коэффициентов для повышения числовой эффективности, но для этого требуется больший доступ к значениям коэффициентов, буферизованным во внешней памяти, что может привести к увеличению числа конфликтов в кэше, что нивелирует некоторое численное преимущество.

Оба алгоритма повышают эффективность примерно в два раза при использовании входных данных с действительным знаком, а не с комплексным знаком. Однако этот выигрыш естественен для алгоритма Герцеля, но не будет достигнут для БПФ без использования определенных вариантов алгоритма, специализированных для преобразования данных с действительным знаком.

См. Также

Справочные материалы

Дополнительная литература

Proakis, JG; Манолакис, Д.Г. (1996), Цифровая обработка сигналов: принципы, алгоритмы и приложения, Верхняя Сэдл-Ривер, Нью-Джерси: Прентис Холл, стр. 480–481

Внешние ссылки

Алгоритм Герцеля на Wayback Machine (архивировано 28.06.2018)
Алгоритм DSP для частотного анализа
Алгоритм Герцеля, Кевин Бэнкс