Signal Processing - September 2017 - 185

1

t = 25

1

t = 26

Real

Imag

0

0
-1
0

5

10

15
Sample
(a)

20

x [n]

+

25

-1
0

30

20

40

60

80

100

Sample
(b)

Imag

1
ω

0
-1

×

-1

0
Real
(c)

x [n]

x n (ω)
e -1/τe j ω

1

+
z

z -1

-N

-

X n [k]

+
e j 2πk /N z -1
×

X n -1(ω)

(d)

X n -1[k]

(e)

FIGURE 1. (a) The signal windowing for the SWIFT algorithm. The data samples and window used for the first computation (blue) and second computation
(green). (b) The impulse response and (c) the pole/zero map for a single bin SWIFT with x = 50 samples and ~ = r/10 radians/sample. (d) The singlebin SWIFT filter structure and (e) the single-bin SDFT filter structure.

calculating the DTFT with an exponential
window on all previous data. However,
because the window is infinite in length,
the output will never truly become valid
but will instead asymptote to the true
value with a time constant of x. In practice, however, if x is short enough, this
is not an issue.

Transfer function and impulse
response
The z-domain transfer function of the
SWIFT filter with normalized angular
frequency ~ is given by
H SWIFT (z) =

1
.
1 - e -1/x e j~ z -1

(6)

The SWIFT IIR filter has one zero
at the origin and a single pole lying
inside the unit circle at e -1/x e j~. The
SWIFT's impulse response and pole/
zero map are shown in Figure 1(b) and
(c), with x = 50 samples and ~ = r/10
radians/sample.

IIR filter implementation
Like the SDFT algorithm, the SWIFT
algorithm can be implemented as an
IIR filter with a complex resonator, as
shown in Figure 1(d). The major difference between the SWIFT filter and
an SDFT filter [Figure 1(e)] is that the
SWIFT filter does not require a comb
filter. Any arbitrary number of frequency bins can be calculated by add-

ing more complex resonators at the
desired frequencies.

SWIFT versus SDFT
The SWIFT has several advantages over
the SDFT, as discussed in the following.

Computational efficiency
The SWIFT is more efficient than the
SDFT. To objectively compare the algorithms, we will consider only the costs
of computing a single bin for each.
Both the SWIFT and SDFT share the
property that the number of computations required to calculate X n (~) from
X n - 1 (~) (or X n [k] from X n - 1 [k]) is
fixed and independent of the window
length. However, the SWIFT requires one
complex multiply and one real add to compute the next output, whereas the SDFT
requires one complex multiply and two
real adds. In addition to increased computational efficiency, the SWIFT has drastically reduced memory requirements.
To facilitate comparison, we have
converted complex operations into real

operations, assuming that one complex multiply requires two real adds
and four real multiplies (although it
is possible to compute with three real
multiplies and five additions [4]). Both
the SWIFT and SDFT require storing
one previous complex output and one
complex constant (four floating points).
However, the SDFT must store N previous input samples, while the SWIFT
does not require storage of any previous input samples. The storage and re trieval of N previous samples may be
a significant limitation for small sensors
and embedded devices. Table 1 compares the computational efficiency and
memory requirements of the SDFT and
SWIFT algorithms.

Frequency-domain sampling
As a type of DFT, the SDFT's output is limited to normalized frequencies of 2rk/N, k ! Z. To achieve finer
frequency-domain sampling, the SDFT
requires a larger N, reducing temporal
resolution and thus producing a tradeoff

Table 1. A single-bin comparison of the computational cost and memory requirements
of computing the next Xn[k]/Xn(~ ) using the DFT, SDFT, and SWIFT.
Method

Real multiplies

Real adds

Memory (floats)

DFT

Two N

Two N

N

SDFT

Four

Four

N + Four

SWIFT

Four

Three

Four

IEEE SIGNAL PROCESSING MAGAZINE

|

September 2017

|

185
Table of Contents for the Digital Edition of Signal Processing - September 2017
