Fundamentals of
Measurement Technology
(5)
Prof,Wang Boxiong
The discrete Fourier transform (DFT):
where
Since x(n) may be complex we can write
2.3.6 Fast Fourier transform (FFT)
1,,1,0,11 2
NkWnxenxkXD FT N
on
nk
N
N
on
nkNj
1,,1,011,11 2
NnWkXNekXNnxI D FT N
ok
nk
N
N
ok
nkNj
(2.232)
(2.233)
NjN eW?2
1
0
N
n
knNknNknNknN WImnxImWRenxRejWImnxImWRenxRekX
110 N,,,k? (2.234)
From Eq,(2.234) it is clear that
1) For each value of k,the direct computation of
X(k) requires 4N real multiplication and (4N-2)
real additions,
2) X(k) must be computed for N different values of
k,the direct computation of the discrete Fourier
transform of a sequence x(n) requires 4N2 real
multiplications and N(4N-2) real additions or,
alternatively,N2 complex multiplications and
N(N-1) complex additions,
2.3.6 Fast Fourier transform (FFT)
For the direct computation of the discrete
Fourier transform,4N2 real multiplications and
N(4N-2) real additions are required,
The amount of computation,and thus the
computation time,is approximately proportional
to N2,so the number of arithmetic operations
required to compute the DFT by the direct
method becomes very large for large values of N.
Conclusion,computational procedures that
reduce the number of multiplications and
additions are of considerable interest,
2.3.6 Fast Fourier transform (FFT)
Improving the efficiency of the computation
of the DFT exploits one or both of the
following special properties of the quantities
:
1) Symmetry
2) Periodicity
2.3.6 Fast Fourier transform (FFT)
knNW
*knNnNkN WW (2.235)
nNkNNnkNknN WWW (2.236)
For example,using the first property,we
can group terms in Eq,(2.234) as
By this method,the number of multiplications
can be reduced by approximately a factor of 2,
The second property,i.e.,the periodicity of
the complex sequence,can be employed
in achieving significantly greater reductions of
the computation,
2.3.6 Fast Fourier transform (FFT)
knNnNkNknN WRenNxRenxReWRenNxReWRenxRe
knNnNkNknN WImnNxImnxImWImnNxImWImnxIm
knNW
In 1965,Cooley and Tukey published an
algorithm for the computation of the discrete
Fourier transform that is applicable when N is a
composite number; i.e.,N is the product of two
or more integers,The algorithms are known as
fast Fourier transform,or simply FFT,
algorithms,
2.3.6 Fast Fourier transform (FFT)
The fundamental principle,decompose the
computation of the discrete Fourier transform of
a sequence of length into successively smaller
discrete Fourier transform,
Two basic classes of FFT algorithms:
– decimation-in-time
– decimation-in-frequency
2.3.6 Fast Fourier transform (FFT)
1,Decimation-in-Time FFT Algorithms
Assuming:
separating x(n) into two N/2-point sequence
consisting of the even-numbered points in x(n)
and the odd-numbered points in x(n),With X(k)
given by
then
2.3.6 Fast Fourier transform (FFT)
MN 2?
1,1,0,1
0
NkWnxkX
N
n
nk
N?
o l dn
nk
N
e v e nn
nk
N WnxWnxkX
With the substitution of variables n=2r for n
even and n=2r+1 for n odd,
But since
2.3.6 Fast Fourier transform (FFT)
1
2
2
1
2
2
1
2
1
2
122
122
122
N
or
rk
N
N
or
k
N
rk
N
N
or
N
or
r
N
rk
N
WrxWWrx
kWrxWrxkX
(2.237)
2
2 NN WW?
2
2222 NNjNjN WeeW
Consequently,
where
After the two DFTs corresponding to the two
sums in Eq,(2.238) are computed,they are then
combined to yield the N-point DFT,X(k),
2.3.6 Fast Fourier transform (FFT)
kHWkG
WrxWWrxkX
k
N
N
r
rk
N
k
N
N
r
rk
N
12
0
2
12
0
2 122
1,1,0 Nk?
(2.238)
12
0
22)(
N
r
rk
NWrxkG
12
0
212)(
N
r
rk
NWrxkH
12,1,0 Nk?
(2.239)
12,1,0 Nk?
(2.240)
This figure used the signal
flow graph conventions for
representing difference
equations,That is,branches
entering a node are summed
to produce the node variable,
When no coefficient is
indicated,the branch
transmittance is assumed to
be one,For other braches,
the transmittance of a branch
is an integer power of WN,
2.3.6 Fast Fourier transform (FFT)
Fig,2.74 Flow graph of the
decimation-in-time decomposition of
an N-point DFT computation into two
N/2-point DFT computations(N=8)
Equation (2.238) corresponds to breaking the
original N-point computation into two-N/2-point
computations,Breaking further each of the sums
in Eq,(2.238) into two N/4-point DFTs,which
would then be combined to yield the N/2-point
DFTs,
Similarly,
2.3.6 Fast Fourier transform (FFT)
14
0
42
14
0
4 122
N
l
lk
N
k
N
N
l
lk
N WlgWWlgkG
14
0
12
2
14
0
2
2
12
0
2 122
N
l
kl
N
N
l
lk
N
N
r
rk
N WlgWlgWrgkG
(2.241)
14
0
42
14
0
4 122
N
l
lk
N
k
N
N
l
lk
N WlhWWlhkH
(2.242)
2.3.6 Fast Fourier transform (FFT)
Fig,2.75 Flow graph of the
decimation-in-time decomposition of
an N/2-point DFT computation into
two N/4-point DFT computations
(n=8)
Fig,2.76 Result of substituting Fig,2.75
into Fig,2.74
2.3.6 Fast Fourier transform (FFT)
Fig,2.77 Flow graph of a two-point
DFT
Fig,2.78 Flow graph of complete decimation-
in-time decomposition of an eight=point DFT
computation
For the more general case with N a power of
2 greater than 3,we would processed by
decomposing the N/4-point transforms in Eqs,
(2.241) and (2.242) into N/8-point transforms,
and continue until left with only two-point
transforms,This requires v stages of computation,
where v=log2N,
2.3.6 Fast Fourier transform (FFT)
The flow graph of Fig,2.78 displays the
operations explicitly,Each stage has N complex
multiplications and N complex additions,There
are log2N stages,so we have a total of Nlog2N
complex multiplications and additions,
This is the substantial computational
savings!
2.3.6 Fast Fourier transform (FFT)
According to Fig,2.78,each stage of the
computation takes a set of N complex numbers
and transforms them into another set of N
complex numbers,For the case of N=8 as in
Fig,2.78
2.3.6 Fast Fourier transform (FFT)
77
36
55
14
63
22
41
00
0
0
0
0
0
0
0
0
xX
xX
xX
xX
xX
xX
xX
xX
(2.243)
Using this notation and ordering,it can be seen that the
basic computation in the flow graph of Fig,2.78 is as
shown in Fig,2.79,This flow graph are of the form
This computation is referred to as a butterfly
computation,
2.3.6 Fast Fourier transform (FFT)
Fig,2.79 Flow graph of basic butterfly computation in Fig,2.78
qXWpXqX
qXWpXpX
m
Nr
Nmm
m
r
Nmm
2
1
1
(2.244)
Since
so that equations (2.244) become
2.3.6 Fast Fourier transform (FFT)
Fig,2.80 Flow graph of simplified butterfly computation requiring only one
complex multiplication
1222 jNNjNN eeW
qXWpXqX
qXWpXpX
m
r
Nmm
m
r
Nmm
1
1
(2.245)
2.3.6 Fast Fourier transform (FFT)
Fig,2.81 Flow graph of eight-point DFT using the butterfly
computation of fig,2.80
In order that the computation may be done in
place as discussed above,we note that with the
flow graph of Fig,2.78 (or 2.79) the input data
must be stored in a nonsequential order,Write the
indices in Eq,(2.243) in binary form,we get
2.3.6 Fast Fourier transform (FFT)
111111
011110
101101
001100
110011
010010
100001
000000
0
0
0
0
0
0
0
0
xX
xX
xX
xX
xX
xX
xX
xX
(2.246)
Note:
If (n2n1n0) is the binary representation of
the index of the sequence x(n),then the
sequence value x(n2n1n0) is stored in the
array position X0(n2n1n0),That is,in
determining the position of x(n2n1n0) in the
input array,we must reverse the order of
the bits of the index n.
2.3.6 Fast Fourier transform (FFT)
2.3.6 Fast Fourier transform (FFT)
Fig,2.82 Tree diagram depicting bit-reversed sorting
Chapter 3 Characteristic
analysis of measuring systems
Wang Boxiong
Chap.3 Characteristic analysis of
measuring systems
3.1 Introduction
3.2 Error analysis
3.3 Static characteristics of measuring systems
3.4 Dynamic characteristics of measuring systems
3.5 Requirements on measuring instrument to
ensure accurate measurement
3.6 Loading effects of measuring system
Signals are closely related with systems,
The measured physical quantity (the measurand) or
input signal acts as an excitation on a measuring
system,which,in turn,“processes” the signal and
outputs the,processed” signal in a suitable form.
Influenced by the characteristic features of a
measuring system and the interference in signal
transmission,the quality of the output can be no
better than the quality of the input,
3.1 Introduction
The relationship between its input and output:
Case 1,To find y(t) for known x(t) and h(t).
Case 2,To find h(t) for known x(t) and y(t).
Case 3,To find x(t) for known y(t) and f(t).
3.1 Introduction
Fig,3.1 Block diagram of a measuring system
It is desired that the transfer characteristic of a
system be a linear one,
For static measurements,a linearity of system is
desired,but not necessary,
It is relatively easy for static measurements to realize
a nonlinear correction by use of curve correction and
data compensation,
For dynamic measurements,this requirement of
linearity of system is necessary.
The reason:It is difficult and even very expensive to
perform a nonlinear correction,
3.1 Introduction
Every measurement may be accompanied by
errors.
Definition of error E:
xm,the indication of instrument
x,the true value
Correction B:
3.2 Error analysis
xxE m (3.1)
mxxB (3.2)
According to their properties,measurement
errors are sorted as random error,systematic
error and illegitimate error.
1,Systematic errors,errors that occur in the same way
each time when a measurement of an identical
quantity is made.
2,Random errors,errors that are different for each
successive measurement but have an average value
of zero.
3,Illegitimate errors,errors that would not be expected
to exist.
3.2 Error analysis
The successive readings will generally cluster
about a central value and will extend over a
limited interval surrounding that central value,
We may use statistical analysis to estimate the
likely size of the error or,equivalently,the likely
rang of x in which the true value lies.
Systematic or bias errors cannot be treated using
statistical techniques,because such errors are
fixed and do not show a distribution.
In practice,bias and precision errors occur
simultaneously.
3.2 Error analysis
3.2 Error analysis
Fig,3.2 Systematic and random errors
(a) Systematic error larger than the typical random error.
3.2 Error analysis
Fig,3.2 Systematic and random errors
(b) Typical random error larger than the systematic error
Errors can also be divided into static errors and
dynamic errors in terms of types of
measurement.
1,Static errors,the input-output relationship for a
nonlinear measuring instrument is expressed by
algebraic or transcendental equations,So the error
caused is usually dependent only on the magnitude
of measurand and is not a function of time,Errors
of such kind are called static errors.
3.2 Error analysis
2,Dynamic errors,In measurement of time-
variant physical quantities,differential
equipments are to be used to describe the input-
output relations,The errors thus caused are
dependent not only on the magnitude,but also
on the time process of the measurand,and are
therefore called dynamic errors.
3.2 Error analysis
Performance characteristics of a measuring
system are divided into static and dynamic
characteristics.
Static characteristics usually include,
repeatability,drift,error,accuracy,uncertainly,
resolution,linearity or nonlinearity.
3.3 Static characteristics of measuring systems
Measurement Technology
(5)
Prof,Wang Boxiong
The discrete Fourier transform (DFT):
where
Since x(n) may be complex we can write
2.3.6 Fast Fourier transform (FFT)
1,,1,0,11 2
NkWnxenxkXD FT N
on
nk
N
N
on
nkNj
1,,1,011,11 2
NnWkXNekXNnxI D FT N
ok
nk
N
N
ok
nkNj
(2.232)
(2.233)
NjN eW?2
1
0
N
n
knNknNknNknN WImnxImWRenxRejWImnxImWRenxRekX
110 N,,,k? (2.234)
From Eq,(2.234) it is clear that
1) For each value of k,the direct computation of
X(k) requires 4N real multiplication and (4N-2)
real additions,
2) X(k) must be computed for N different values of
k,the direct computation of the discrete Fourier
transform of a sequence x(n) requires 4N2 real
multiplications and N(4N-2) real additions or,
alternatively,N2 complex multiplications and
N(N-1) complex additions,
2.3.6 Fast Fourier transform (FFT)
For the direct computation of the discrete
Fourier transform,4N2 real multiplications and
N(4N-2) real additions are required,
The amount of computation,and thus the
computation time,is approximately proportional
to N2,so the number of arithmetic operations
required to compute the DFT by the direct
method becomes very large for large values of N.
Conclusion,computational procedures that
reduce the number of multiplications and
additions are of considerable interest,
2.3.6 Fast Fourier transform (FFT)
Improving the efficiency of the computation
of the DFT exploits one or both of the
following special properties of the quantities
:
1) Symmetry
2) Periodicity
2.3.6 Fast Fourier transform (FFT)
knNW
*knNnNkN WW (2.235)
nNkNNnkNknN WWW (2.236)
For example,using the first property,we
can group terms in Eq,(2.234) as
By this method,the number of multiplications
can be reduced by approximately a factor of 2,
The second property,i.e.,the periodicity of
the complex sequence,can be employed
in achieving significantly greater reductions of
the computation,
2.3.6 Fast Fourier transform (FFT)
knNnNkNknN WRenNxRenxReWRenNxReWRenxRe
knNnNkNknN WImnNxImnxImWImnNxImWImnxIm
knNW
In 1965,Cooley and Tukey published an
algorithm for the computation of the discrete
Fourier transform that is applicable when N is a
composite number; i.e.,N is the product of two
or more integers,The algorithms are known as
fast Fourier transform,or simply FFT,
algorithms,
2.3.6 Fast Fourier transform (FFT)
The fundamental principle,decompose the
computation of the discrete Fourier transform of
a sequence of length into successively smaller
discrete Fourier transform,
Two basic classes of FFT algorithms:
– decimation-in-time
– decimation-in-frequency
2.3.6 Fast Fourier transform (FFT)
1,Decimation-in-Time FFT Algorithms
Assuming:
separating x(n) into two N/2-point sequence
consisting of the even-numbered points in x(n)
and the odd-numbered points in x(n),With X(k)
given by
then
2.3.6 Fast Fourier transform (FFT)
MN 2?
1,1,0,1
0
NkWnxkX
N
n
nk
N?
o l dn
nk
N
e v e nn
nk
N WnxWnxkX
With the substitution of variables n=2r for n
even and n=2r+1 for n odd,
But since
2.3.6 Fast Fourier transform (FFT)
1
2
2
1
2
2
1
2
1
2
122
122
122
N
or
rk
N
N
or
k
N
rk
N
N
or
N
or
r
N
rk
N
WrxWWrx
kWrxWrxkX
(2.237)
2
2 NN WW?
2
2222 NNjNjN WeeW
Consequently,
where
After the two DFTs corresponding to the two
sums in Eq,(2.238) are computed,they are then
combined to yield the N-point DFT,X(k),
2.3.6 Fast Fourier transform (FFT)
kHWkG
WrxWWrxkX
k
N
N
r
rk
N
k
N
N
r
rk
N
12
0
2
12
0
2 122
1,1,0 Nk?
(2.238)
12
0
22)(
N
r
rk
NWrxkG
12
0
212)(
N
r
rk
NWrxkH
12,1,0 Nk?
(2.239)
12,1,0 Nk?
(2.240)
This figure used the signal
flow graph conventions for
representing difference
equations,That is,branches
entering a node are summed
to produce the node variable,
When no coefficient is
indicated,the branch
transmittance is assumed to
be one,For other braches,
the transmittance of a branch
is an integer power of WN,
2.3.6 Fast Fourier transform (FFT)
Fig,2.74 Flow graph of the
decimation-in-time decomposition of
an N-point DFT computation into two
N/2-point DFT computations(N=8)
Equation (2.238) corresponds to breaking the
original N-point computation into two-N/2-point
computations,Breaking further each of the sums
in Eq,(2.238) into two N/4-point DFTs,which
would then be combined to yield the N/2-point
DFTs,
Similarly,
2.3.6 Fast Fourier transform (FFT)
14
0
42
14
0
4 122
N
l
lk
N
k
N
N
l
lk
N WlgWWlgkG
14
0
12
2
14
0
2
2
12
0
2 122
N
l
kl
N
N
l
lk
N
N
r
rk
N WlgWlgWrgkG
(2.241)
14
0
42
14
0
4 122
N
l
lk
N
k
N
N
l
lk
N WlhWWlhkH
(2.242)
2.3.6 Fast Fourier transform (FFT)
Fig,2.75 Flow graph of the
decimation-in-time decomposition of
an N/2-point DFT computation into
two N/4-point DFT computations
(n=8)
Fig,2.76 Result of substituting Fig,2.75
into Fig,2.74
2.3.6 Fast Fourier transform (FFT)
Fig,2.77 Flow graph of a two-point
DFT
Fig,2.78 Flow graph of complete decimation-
in-time decomposition of an eight=point DFT
computation
For the more general case with N a power of
2 greater than 3,we would processed by
decomposing the N/4-point transforms in Eqs,
(2.241) and (2.242) into N/8-point transforms,
and continue until left with only two-point
transforms,This requires v stages of computation,
where v=log2N,
2.3.6 Fast Fourier transform (FFT)
The flow graph of Fig,2.78 displays the
operations explicitly,Each stage has N complex
multiplications and N complex additions,There
are log2N stages,so we have a total of Nlog2N
complex multiplications and additions,
This is the substantial computational
savings!
2.3.6 Fast Fourier transform (FFT)
According to Fig,2.78,each stage of the
computation takes a set of N complex numbers
and transforms them into another set of N
complex numbers,For the case of N=8 as in
Fig,2.78
2.3.6 Fast Fourier transform (FFT)
77
36
55
14
63
22
41
00
0
0
0
0
0
0
0
0
xX
xX
xX
xX
xX
xX
xX
xX
(2.243)
Using this notation and ordering,it can be seen that the
basic computation in the flow graph of Fig,2.78 is as
shown in Fig,2.79,This flow graph are of the form
This computation is referred to as a butterfly
computation,
2.3.6 Fast Fourier transform (FFT)
Fig,2.79 Flow graph of basic butterfly computation in Fig,2.78
qXWpXqX
qXWpXpX
m
Nr
Nmm
m
r
Nmm
2
1
1
(2.244)
Since
so that equations (2.244) become
2.3.6 Fast Fourier transform (FFT)
Fig,2.80 Flow graph of simplified butterfly computation requiring only one
complex multiplication
1222 jNNjNN eeW
qXWpXqX
qXWpXpX
m
r
Nmm
m
r
Nmm
1
1
(2.245)
2.3.6 Fast Fourier transform (FFT)
Fig,2.81 Flow graph of eight-point DFT using the butterfly
computation of fig,2.80
In order that the computation may be done in
place as discussed above,we note that with the
flow graph of Fig,2.78 (or 2.79) the input data
must be stored in a nonsequential order,Write the
indices in Eq,(2.243) in binary form,we get
2.3.6 Fast Fourier transform (FFT)
111111
011110
101101
001100
110011
010010
100001
000000
0
0
0
0
0
0
0
0
xX
xX
xX
xX
xX
xX
xX
xX
(2.246)
Note:
If (n2n1n0) is the binary representation of
the index of the sequence x(n),then the
sequence value x(n2n1n0) is stored in the
array position X0(n2n1n0),That is,in
determining the position of x(n2n1n0) in the
input array,we must reverse the order of
the bits of the index n.
2.3.6 Fast Fourier transform (FFT)
2.3.6 Fast Fourier transform (FFT)
Fig,2.82 Tree diagram depicting bit-reversed sorting
Chapter 3 Characteristic
analysis of measuring systems
Wang Boxiong
Chap.3 Characteristic analysis of
measuring systems
3.1 Introduction
3.2 Error analysis
3.3 Static characteristics of measuring systems
3.4 Dynamic characteristics of measuring systems
3.5 Requirements on measuring instrument to
ensure accurate measurement
3.6 Loading effects of measuring system
Signals are closely related with systems,
The measured physical quantity (the measurand) or
input signal acts as an excitation on a measuring
system,which,in turn,“processes” the signal and
outputs the,processed” signal in a suitable form.
Influenced by the characteristic features of a
measuring system and the interference in signal
transmission,the quality of the output can be no
better than the quality of the input,
3.1 Introduction
The relationship between its input and output:
Case 1,To find y(t) for known x(t) and h(t).
Case 2,To find h(t) for known x(t) and y(t).
Case 3,To find x(t) for known y(t) and f(t).
3.1 Introduction
Fig,3.1 Block diagram of a measuring system
It is desired that the transfer characteristic of a
system be a linear one,
For static measurements,a linearity of system is
desired,but not necessary,
It is relatively easy for static measurements to realize
a nonlinear correction by use of curve correction and
data compensation,
For dynamic measurements,this requirement of
linearity of system is necessary.
The reason:It is difficult and even very expensive to
perform a nonlinear correction,
3.1 Introduction
Every measurement may be accompanied by
errors.
Definition of error E:
xm,the indication of instrument
x,the true value
Correction B:
3.2 Error analysis
xxE m (3.1)
mxxB (3.2)
According to their properties,measurement
errors are sorted as random error,systematic
error and illegitimate error.
1,Systematic errors,errors that occur in the same way
each time when a measurement of an identical
quantity is made.
2,Random errors,errors that are different for each
successive measurement but have an average value
of zero.
3,Illegitimate errors,errors that would not be expected
to exist.
3.2 Error analysis
The successive readings will generally cluster
about a central value and will extend over a
limited interval surrounding that central value,
We may use statistical analysis to estimate the
likely size of the error or,equivalently,the likely
rang of x in which the true value lies.
Systematic or bias errors cannot be treated using
statistical techniques,because such errors are
fixed and do not show a distribution.
In practice,bias and precision errors occur
simultaneously.
3.2 Error analysis
3.2 Error analysis
Fig,3.2 Systematic and random errors
(a) Systematic error larger than the typical random error.
3.2 Error analysis
Fig,3.2 Systematic and random errors
(b) Typical random error larger than the systematic error
Errors can also be divided into static errors and
dynamic errors in terms of types of
measurement.
1,Static errors,the input-output relationship for a
nonlinear measuring instrument is expressed by
algebraic or transcendental equations,So the error
caused is usually dependent only on the magnitude
of measurand and is not a function of time,Errors
of such kind are called static errors.
3.2 Error analysis
2,Dynamic errors,In measurement of time-
variant physical quantities,differential
equipments are to be used to describe the input-
output relations,The errors thus caused are
dependent not only on the magnitude,but also
on the time process of the measurand,and are
therefore called dynamic errors.
3.2 Error analysis
Performance characteristics of a measuring
system are divided into static and dynamic
characteristics.
Static characteristics usually include,
repeatability,drift,error,accuracy,uncertainly,
resolution,linearity or nonlinearity.
3.3 Static characteristics of measuring systems
