加载中…【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率
(2012-08-18 07:00:47)
标签：
杂谈 |
分类： 技术相关 |
Title:
Detect the specific frequency of input signal
Using the Goertzel Algorithm
Watch the video
of this program:
Before you read
through this article, you should understand DFT and FFT algorithm
well.
1. Introduction
of DFT:
The DFT of a finite-length sequence
of length N is defined by:
http://s8/middle/55a4cddcgc77e50dd07b7&690Goertzel Algorith(戈策尔算法）用于检出特定输入频率" TITLE="【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率" />
where http://s9/middle/55a4cddcgc77e5a874f98&690Goertzel Algorith(戈策尔算法）用于检出特定输入频率" TITLE="【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率" /> the root-of-unity,
is also known as the twiddle
factor.
2.
Like FFT algorithm, Goertzel Algorithm is
actually a kind of FFT algorithm. When we are only interested in
some specific frequencies, we can use Goertzel Algorithm to
calculate more data points and use less time to calculate the
result. It will take shorter time for our processor to process the
input signal.
This Goertzel approach for computation of the DFT uses the
periodicity property of the WN^kn
to reduce computations. The result is a recursive algorithm
that is more efficient for
computing some DFT values compared with FFT algorithms. Using
the result:
http://s13/middle/55a4cddcgc77e2a9c311c&690Goertzel Algorith(戈策尔算法）用于检出特定输入频率" TITLE="【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率" />
(1)
we can express (0.1) as:http://s5/middle/55a4cddcgc77e41c96474&690Goertzel Algorith(戈策尔算法）用于检出特定输入频率" TITLE="【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率" />(2)
which appears to be a linear convolution sum. However (2) is
also a polynomial in WN^(-k) which can be efficiently computed as nested
evaluations using the Horner’s rule. To understand
this computation let N = 4. Then (2) becomes:
http://s13/middle/55a4cddcgc77e6f189a9c&690Goertzel Algorith(戈策尔算法）用于检出特定输入频率" TITLE="【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率" />
(3)
If we make the assignments:
http://s15/middle/55a4cddcgc77e740975ae&690Goertzel Algorith(戈策尔算法）用于检出特定输入频率" TITLE="【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率" />
then these assignments suggest a recursive approach for computation of X[k]:
then these assignments suggest a recursive approach for computation of X[k]:
http://s16/middle/55a4cddcgc77e7ee493ff&690Goertzel Algorith(戈策尔算法）用于检出特定输入频率" TITLE="【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率" />
with initial condition yk[−1] = 0 and input x[n] = 0 for n
< 0 and n ≥ N. Thus to compute one
DFT value we will need O(N) complex operations and to compute all
DFT values we will need O(N^2) complex operations
which is the same as that for the DFT.
However, there are some advantages: (a) if only few M
< logN DFT values are needed then
we need only O(MN) < O(NlogN) operations; (b) we do
not have to compute or store {WN^(−kn)} complex values since these are
computed recursively in the algorithm; and (c)
the computations can start as soon as the first
input sample is available, that is, we do not
have to wait until all samples are
available.
The computational efficiency of the algorithm in (4)(5) can be
improved further by converting it into a
second-order recursive algorithm with real coefficients. Note that
the system function of the recursive filter in (4)
can be written as:
http://s6/bmiddle/55a4cddcgc77e9a4b8275&690Goertzel Algorith(戈策尔算法）用于检出特定输入频率" TITLE="【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率" />
which suggests a two-step approach. The first
term on the right is a recursive second-order
filter with real coefficients that can be
operated on the input x[n] to obtain an intermediate
signal, say v[n]. The second term is an FIR
filter with a complex coefficient that processes
v[n]
but it needs to be operated only at n = N to determine X[k]. Thus
the modified
Goertzels algorithm (Goertzel (1958)) is given
by:
http://s13/middle/55a4cddcgc77ea60d47cc&690Goertzel Algorith(戈策尔算法）用于检出特定输入频率" TITLE="【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率" />
with initial conditions
vk[−1] = vk[−2] = 0. This algorithm requires
O(N^2) real and O(N)
complex operations to compute all DFT values and
hence is more efficient in computation
than
the one in (4)(5).
The MATLAB function gafft, given below
implements Goertzel’s algorithm of (8.61) for the
computation of one sample of x[k]. It can help you understand the
Goertzel Algorithm:
3.
The code for
declaration of the parameters:
http://s8/middle/55a4cddcgc77f1940b2e7&690Goertzel Algorith(戈策尔算法）用于检出特定输入频率" TITLE="【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率" />
The code for using the Goertzel function:
http://s12/middle/55a4cddcgc77f36409ecb&690Goertzel Algorith(戈策尔算法）用于检出特定输入频率" TITLE="【技术】 Goertzel Algorith(戈策尔算法）用于检出特定输入频率" />
The
code for Goertzel
function:
http://s15/bmiddle/55a4cddcgc77f21db053e&690GoertzelAlgorith(戈策尔算法）用于检出特定输入频率" />
http://s15/bmiddle/55a4cddcgc77f21db053e&690Goertzel
Watch the video of this program:
Path1. from youku.com
:http://v.youku.com/v_show/id_XNDQwMDcwNDAw.html
Path2. from youtube.com :http://www.youtube.com/watch?v=sIRVT5iqEVQ
喜欢
0
赠金笔
前一篇：[转载]波士顿 别样风情