Goertzel Theory

background image

The Goertzel algorithm is derived from the Discrete Fourier Transform (DFT) and exploits the

periodicity of the phase factor

N

k

j

e

π

2

to reduce the computational complexity associated with the DFT

as the Fast Fourier Transform (FFT) does. However the Goertzel algorithm is more efficient than the
FFT, when only a few samples of the DFT are required. With the Goertzel algorithm only 16 samples
of the DFT are required. The Goertzel algorithm can be derived as follows using the DFT equation.

( )

( )

( )

)

1

(

;

2

1

0

2

2

1

0

2

=

=

=

=

=

N

kN

j

N

n

N

kn

j

N

kN

j

N

n

N

kn

j

e

e

n

x

e

e

n

x

k

X

π

π

π

π

[1]

( )

k

X

can be written as:

( )

( ) (

)

=

=

1

0

N

n

k

n

N

h

n

x

k

X

where:

(

)

(

)

N

n

N

k

j

k

e

n

N

h

=

π

2

.

( )

k

X

can now be identified as an output of a filter at

N

m

=

and the filter can be written as follows:

( )

( ) (

)

=

=

1

0

N

n

k

k

n

m

h

n

x

m

y

.

[2]

Therefore:

( )

( )

N

m

k

k

m

y

N

X

=

=

[3]

This can be read as: the Discrete Fourier Transform

( )

N

X

k

is the output of the filter

( )

m

y

k

at

N

m

=

.

The z-transform of

k

y

,

( )

z

y

k

is given by:

( )

( )

1

2

1

=

z

e

z

X

z

y

N

k

j

k

π

.

[4]

Deriving the difference equation,

( ) ( )

(

)

( )

0

1

;

1

2

=

+

=

k

k

N

k

j

k

y

n

y

e

n

x

n

y

π

.

[5]

This can be implemented as a single pole IIR filter as shown in Figure 8.2.

background image

z

-1

+

x(n)

y(n)

N

k

j

e

π

2

Figure 8.2 Structure of a Single Pole Resonator for computing the DFT

Equation [5] involves multiplication by a complex number and each complex multiplication results in
four real multiplications and four real additions.

To avoid complex multiplication, Equation [4] is multiplied by a complex conjugate pole and simplified
as follows:

( )

( )

( )

(

)

(

)

(

)

(

)

( )

]

6

[

.

2

cos

2

1

1

sin

cos

1

sin

cos

1

1

1

1

1

2

1

1

2

1

1

1

2

1

2

1

2

1

2

+





=

+





=













=

z

z

k

N

z

e

z

X

j

z

j

z

z

e

z

X

z

e

z

e

z

e

z

X

z

y

k

N

j

k

N

j

k

N

j

k

N

j

k

N

j

k

π

θ

θ

θ

θ

π

π

π

π

π

Equation [6] can be implemented using the structure shown in Figure 8.3.

+

+

+

-1

1

z

1

z

)

( n

y

)

( n

x

k

N

j

e

π

2

k

N

π

2

cos

2

2

n

Q

n

Q

1

n

Q

Figure 8.3 Structure of a two Pole Resonator for Computing the k

th

DFT sample

where

background image

( )

2

1

2

cos

2

+

=

n

n

n

Q

Q

N

k

n

x

Q

π

[7]

and

( )

k

N

j

n

n

k

e

Q

Q

n

y

π

2

1

=

[8]

or

( )

( )

N

m

k

k

m

y

N

X

=

=

.

This means that

( )

n

y

k

need not be calculated for every value of m as it only needs to be calculated

at

N

m

=

.

Finally Equations [7] and [8] can be rewritten as follows:

( )

N

n

Q

Q

N

k

n

x

Q

n

n

n

+

=

0

;

2

cos

2

2

1

π

[9]

and

( )

( )

N

n

e

Q

Q

k

X

n

y

k

N

j

N

N

N

n

k

=

=

=

=

;

2

1

π

.

[10]

With this modified structure there is only one complex multiplication for the calculation of each

( )

k

X

.

To implement this algorithm the feedback stage has to be repeated N times and the feedforward stage
to be done once only. Since with DTMF detection we are not interested in the phase information, the
Goertzel algorithm maybe modified to produce an output which is proportional to the magnitude of the
signal. This has the advantage of using only real coefficients and minimising processing time as
shown below.

( )

[

]

,

sin

cos

1

2

θ

θ

θ

π

jB

B

A

Be

A

Q

e

Q

N

y

j

N

k

N

j

N

k

+

=

=

=

where:

n

Q

A

=

1

=

n

Q

B

N

k

π

θ

2

=

.

The square of the magnitude is:

( ) (

) (

)

θ

θ

θ

θ

θ

θ

cos

2

sin

cos

cos

2

sin

cos

2

2

2

2

2

2

2

2

2

2

AB

B

A

B

B

AB

A

B

B

A

n

y

k

+

=

+

+

=

+

=

Therefore:

( )

( )

( )

(

)

( ) (

)

1

2

cos

2

1

2

2

2

2

+

=

=

N

Q

N

Q

N

k

N

Q

N

Q

k

X

N

y

k

π

.

[11]

Equation [11] shows that the calculation of

( )

2

k

X

requires only real additions and multiplications.


Wyszukiwarka

Podobne podstrony:
(ebook PDF)Shannon A Mathematical Theory Of Communication RXK2WIS2ZEJTDZ75G7VI3OC6ZO2P57GO3E27QNQ
Hawking Theory Of Everything
Maslow (1943) Theory of Human Motivation
Goertzel
Habermas, Jurgen The theory of communicative action Vol 1
The Big?ng Theory
Psychology and Cognitive Science A H Maslow A Theory of Human Motivation
Pohlers Infinitary Proof Theory (1999)
Goodale Ethical Theory as Social Practice
Habermas, Jurgen The theory of communicative action Vol 2
Civil Society and Political Theory in the Work of Luhmann
Marxism and?onomic Theory
Theory and practise of teaching history 18.10.2011, PWSZ, Theory and practise of teaching history
Constituents of a theory of media
AC THEORY
Bilinear Theory

więcej podobnych podstron