# A Simpler Goertzel Algorithm

In this blog I propose a Goertzel algorithm that is simpler than the version of the Goertzel algorithm that is traditionally presented DSP textbooks. Below I very briefly describe the DSP textbook version of the Goertzel algorithm followed by a description of my proposed simpler algorithm.

**The Traditional DSP Textbook Goertzel Algorithm**

The so-called Goertzel algorithm is used to efficiently compute a single *m*th-bin sample of an *N*-point discrete Fourier transform (DFT) [1-4]. The traditional DSP textbook version of the Goertzel algorithm is implemented using the network shown in Figure 1.

** Figure 1: Traditional DSP textbook Goertzel network.**

** **

The ‘*m*’ variable in Figure 1 is the index of the single DFT bin sample being computed where *m* = 0,1,2,…,*N*-1, *N* is the DFT size, and the *X*(*m*) output is the desired *m*th-bin DFT sample. The *z*-domain transfer function of the Figure 1 network is:

$$H_1(z) = {1-e^{-j2{\pi}m/N}z^{-1}\over 1-2cos(2{\pi}m/N)z^{-1}+z^{-2}}.\qquad\qquad\qquad(1)$$

The processing steps used to compute the complex-valued *X*(*m*) output sample in the Figure 1 network are as follows:

1) Apply an *N*-sample *x*(*n*) input sequence to the network performing the Figure 1 Stage# 1 computations *N* times.

2) Shift the data samples downward through the two delay elements.

3) Apply a zero-valued input sample to the network’s input and perform the Figure 1 Stage# 1 computations one more time.

4) Perform the Figure 1 Stage# 2 computations one time to obtain the desired *X*(*m*) sample.

**The Proposed Simpler Goertzel Algorithm**

We can eliminate the above traditional Figure 1 processing Steps 2) and 3) by using the network shown in Figure 2.

** Figure 2: Proposed simpler Goertzel network.**

The *z*-domain transfer function of the Figure 2 network is:

$$H_2(z) = {e^{j2{\pi}m/N}-z^{-1}\over 1-2cos(2{\pi}m/N)z^{-1}+z^{-2}}.\qquad\qquad\qquad(2)$$

The simpler processing steps used to compute the complex-valued *X*(*m*) output sample in the Figure 2 network are as follows:

1) Apply an *N*-sample *x*(*n*) input sequence to the network performing the Figure 2 Stage# 1 computations *N* times.

2) Perform the Figure 2 Stage# 2 computations one time to obtain the desired *X*(*m*) sample.

**A Noteworthy Aspect Regarding the Original 1958 Goertzel Algorithm**

It is interesting to note that the traditional Figure 1 DSP textbook version of the so-called Goertzel algorithm does * not* implement the processing originally proposed by Gerald Goertzel in his 1958 paper [5].

I make the above claim because in Gerald Goertzel’s original paper the input data sequence must be reversed in order to produce the desired *a*(*k*) data sequence as indicated by his decrementing time-domain index ‘*k*’ shown in Figure 3.

**Figure 3: The original algorithm proposed by G. Goertzel in 1958. [Reproduced from [5] without permission.]**

At this point I’ll also state that I believe the lower limit of the ‘*S*’ summation in the text of Figure 3 should be zero rather than one.

**Conclusions**

I briefly described the Figure 1 network and processing steps of the traditional DSP textbook version of the so-called Goertzel algorithm. (I refer to that textbook algorithm as “so-called” because it does not implement the original algorithm proposed by G. Goertzel in his 1958 paper.) Then I proposed the Figure 2 network and processing steps of a simpler Goertzel algorithm.

My proposed algorithm is only slightly computationally simpler than the traditional algorithm but it does eliminate the tradition algorithm’s cumbersome processing Steps 2) and 3).

**References**

[1] S. Mitra, "*Digital Signal Processing*", Fourth Edition, McGraw Hill Publishing, 2011, pp. 618-620.

[2] J. Proakis and D. Manolakis, "*Digital Signal Processing-Principles, Algorithms, and Applications*", Third Edition, Prentice Hall, Upper Saddle River, New Jersey, 1996, pp. 480-481.

[3] A. Oppenheim, R. Schafer, and J. Buck, "*Discrete-Time Signal Processing*", Second Edition, Prentice Hall, Upper Saddle River, New Jersey, 1996, pp. 633-634.

[4] R. Lyons, “*Understanding Digital Signal Processing”, 3rd Ed.*, Prentice Hall, Upper Saddle River, New Jersey, 2011, pp. 738–740.

[5] G. Goertzel, “An Algorithm for the Evaluation of Finite Trigonometric Series” *The American Mathematical Monthly*, Vol. 65, No. 1, Jan. 1958, pp. 34-35

- Comments
- Write a Comment Select to add a comment

To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.

Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.