ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. «Приборостроение». 2012
139
2 /
1
1
( )
.
1
j
k N
H z
e
z
π
⋅
−
=
−
Это вычисление также требует
N
комплексных умножений, одна-
ко может быть преобразовано к виду
2 /
1
1
2
1
( )
,
1 2cos (2 / )
j
k N
e
z
H z
k N z z
π
π
− ⋅
−
− −
−
=
−
+
что реализуется БИХ-фильтром, приведенным на рис. 4,
б
.
Спектральный отсчет
Х
(
k
) имеет вид
2 /
( )
( 1) (
2),
j
k N
X k e
v N v N
π
− ⋅
=
− − −
где
( ) ( ) 2cos (2 / ) ( 1) ( 2).
v r x r
k N v r
v r
π
= +
− − −
Таким образом, алгоритм Герцеля использует в рекурсивной ча-
сти фильтра только вещественные умножения на коэффициент
2cos(2
πk
/
N
), что позволяет сократить число умножений в 2 раза по
сравнению с прямым расчетом.
Сравним аппаратную реализацию вычисления отсчета ДПФ пря-
мым расчетом и с помощью алгоритма Герцеля. В аппаратной реали-
зации обработки данных от АЦП, как правило, используется пред-
ставление с фиксированной запятой. Также в формате с фиксирован-
ной запятой представляются коэффициенты фильтров и оконных
функций.
В работе [5] рассмотрена особенность алгоритма, связанная с
необходимостью защиты реализации алгоритма Герцеля от перепол-
нений. В зависимости от номера вычисляемого спектрального отсче-
та коэффициент 2cos (2
πk
/
N
) может принимать значения в диапазоне
(0, 2]. Для предотвращения переполнений необходимо гарантировать
наличие достаточного числа целых разрядов (для длины преобразо-
вания
N
порядка log
2
N
) или динамически менять разрядность и по-
ложение фиксированной запятой в зависимости от номера отсчета,
что значительно усложняет аппаратную реализацию. При используе-
мых в данной работе параметрах (частота сигнала 2,5 МГц, частота
дискретизации 2,0 МГц, частота выделенной гармоники 500 кГц) ко-
эффициент принимает значение, равное 2.
Необходимость расширять разрядность приводит к увеличению
разрядностей умножителей. Например, в случае прямой реализации
расчета отсчета 256-точечного БПФ над числами в формате 1,15 тре-
буется 512 16-разрядных умножений с 32-разрядным результатом.
Для реализации алгоритма Герцеля получаемые в рекурсивной ветви
значения должны быть представлены в формате 8,15 и требуется
N
умножителей с разрядностью результата 39.
1,2,3,4,5,6,7,8 10,11