《数字信号处理与控制课件：Chapter 5 Finite-Length Discrete Transforms(new)》由会员分享，可在线阅读，更多相关《数字信号处理与控制课件：Chapter 5 Finite-Length Discrete Transforms(new)（115页珍藏版）》请在金锄头文库上搜索。
1、1Chapter 5 Finite-Length Discrete Transforms第五章：有限长度离散变换2Outline Definition of DFT The Relationship Between DFT and DTFT DFT Properties DFT ComputationDTFT: 离散时间傅立叶变换离散时间傅立叶变换 DFT：离散傅立叶变换：离散傅立叶变换3Fourier Transform Time domain Frequency domainContinuous Aperiodic FT Continue Aperiodic连续非周期信号连续非周期信号Co
2、ntinuous Periodic FS Discrete Aperiodic连续周期信号连续周期信号Discrete Aperiodic DTFT Periodical Continuous 离散非周期信号离散非周期信号Discrete Periodic DFT Periodical Discrete离散周期信号离散周期信号4Make a Signal Discrete and PeriodicThe engineering signals are often continuous and aperiodic. If we want to process the signals with D
3、FT, we have to make the signals discrete and periodic.Sampling to make the signal be discrete.Make the signal periodic by periodic expanding.5Make a signal discrete and periodical6From DTFT to get DFTDTFT: discrete in time domain, continuous in frequency domain.Sampling the DTFT of sequences to get
4、N frequency points, that is DFT.1234567(k=N-1)k=0Rez75.2 The Discrete Fourier Transform (DFT)A kind of useful tool to process finite sequences.Based on DFT , we can use computer to perform signal processing.FFT （fast Fourier transform）algorithm is a core in DSP.85.2.1 The Definition of DFTwhere:whic
5、h can easily be deduced from:(1)(2)9The Definition of DFTNote: Xk is also a length-N sequence in the frequency domain.The sequence Xk is called the Discrete Fourier Transform (DFT) of the sequence xn.To verify the above expression we multiply both sides of equation (2) by and sum the result from n =
6、 0 to n=N-1.10The Definition of DFTresulting in:11The Definition of DFTby means of the following equation:r an integerHenceas 12The Definition of DFTExample 1- Consider the length-N sequence:Its N-point DFT is given by:13The Definition of DFTExample 2- Consider the length-N sequence:Its N-point DFT
7、is given by:14The Definition of DFTExample 3- Consider the length-N sequence defined for 0 n N-1Using a trigonometric identity we can write:15The Definition of DFTThe N-point DFT of gn is thus given by:16The Definition of DFTMaking use of the identity:m an integerwe get:175.2.2 Matrix RelationsThe D
8、FT samples defined by:Can be expressed in matrix form as X=DNxWhere X=X0 X1 XN-1T x=x0 x1 xN-1T18Matrix RelationsAnd DN is the N N DFT matrix given by:19Matrix RelationsLikewise, the IDFT relation given by:can be expressed in matrix form as x=DN-1X,where DN-1 is the N N IDFT matrix.Note: DN-1=DN*/N.
9、20Matrix RelationswhereNote: DN-1=DN*/N.215.3 Relation Between the DTFT and the DFT and the Their InversesThe relation between the DTFT and the N-point DFT of a length-N sequence.Numerical computation of the DTFT using the DFT.DTFT from DFT by interpolation.Sampling the DTFT.225.3.1 Relation with DT
10、FTDTFT: discrete in time domain, continuous in frequency domain.Sampling the DTFT of sequences with the space is 2/N to get N frequency points to research, that is DFT.235.3.2 Numerical Computation of the DTFT Using the DFTTo compute the DTFT of a length-N sequence xn .1. Sampling the X(ejw) to get
11、a length-M sequence, MN. So, each frequency component is X(ej2/M).2. Build a length-M sequence use xn.24Numerical Computation of the DTFT Using the DFTWe can see above equation is the DFT of alength-M sequence. Because MN, it can beseen as an approach of the DTFT of a length-Nsequence.25Numerical Co
12、mputation of the DTFT Using the DFT265.3.3 DTFT from DFT by InterpolationThe N-point DFT Xk of a length-N sequence xn is simply the frequency samples of its DTFT X(ej) evaluated at N uniformly spaced frequency points =k=2k/N, 0kN-1.Given the N-point DFT Xk of a length-N sequence xn, its DTFT X(ej) c
13、an be uniquely determined from Xk.27DTFT from DFT by InterpolationThus:28DTFT from DFT by InterpolationTo develop a compact expression for the sum S,29DTFT from DFT by InterpolationTherefore:305.3.4 Sampling the DTFTConsider a sequence xn with DTFT X(ej).We sample X(ej) at N equally spaced points k=
14、2k/N, 0kN-1 developing the N frequency samples .These N frequency samples can be considered as an N-point DFT Yk whose N-point IDFT is a length-N sequence yn.31Sampling the DTFTNowThus:An IDFT of Yk yields:32Sampling the DTFTMaking use of the identity:33Sampling the DTFTWe arrive at the desired rela
15、tion:Thus yn is obtained from xn by adding an infinite number of shifted replicas of xn, with each replica shifted by an integer multiple of N sampling instants, and observing the sum only for the interval 0nN-1.34Sampling the DTFTTo apply：to finite-length sequences, we assume that the samples outsi
16、de the specified range are zeros.Thus if xn is a length-M sequence with MN, then yn=xn for 0nN-1.35Sampling the DTFTIf MN, there is a time-domain aliasing of samples of xn in generating yn, and xn cannot be recovered from yn.Example: Let xn=0 1 2 3 4 5 By sampling its DTFT X(ej) at k=2k/4, 0k3 and t
17、hen applying a 4-point IDFT to these samples, we arrive at the sequence yn given by:36Sampling the DTFTyn=xn+xn+4+xn-4, 0n 3i.e. yn=4 6 2 3 xn cannot be recovered from yn375.4 Operations on Finite-Length SequencesThe DFT properties also show useful functions in signal processing applications. Two op
18、erations:(1) Circular Shift 循环移位 of a Sequence(2) Circular Convolution 循环卷积385.4.1 Circular Shift of a SequenceCircular Shift39Circular Shift of a Sequence40Circular Shift of a SequenceIllustration of the concept of a circular shift:415.4.2 Circular convolutionLinear convolution:Circular Convolution
19、: a length-N sequenceNycn = gn hn42Circular convolutionExample - Determine the 4-point circular convolution of the two length-4 sequences:as sketched below:nn43Circular convolutionThe result is a length-4 sequence yCn given by:4From the above we observe:44Circular convolutionLikewise:45Circular conv
20、olution46Tabular Method in Circular convolutionn0123gng0g1g2g3hnh0h1h2h3g0h0g1h0g2h0g3h0g3h1g0h1g1h1g2h1g2h2g3h2g0h2g1h2g1h3g2h3g3h3g0h3ycnyc0yc1yc2yc3Given two sequences gn and hn,0n 3 , generating the convolution:447ExamplesAssume a length 9 sequence which is Type 1 sequence. Try to compute its ph
21、ase function.48Type 1: Symmetric impulse response with odd lengthIn the general case for Type 1 FIR filters, the phase function is of the form: We get:where or 49Type 2: Symmetric impulse response with even lengthFor simplicity, assume length=8. We get:In the general case for Type 2 FIR filters, the
22、 phase function is of the form:50Type 3: Antisymmetric impulse response with odd lengthFor simplicity, assume length=9. We get:In the general case for Type 3 FIR filters, the phase function is of the form:51Type 4: Antisymmetric impulse response with even lengthFor simplicity, assume length=8. We ge
23、t:In the general case for Type 4 FIR filters, the phase function is of the form:525.6 DFT Symmetric RelationsLength-N SequenceN-point DFTxnXkx*nX*Nx*NX*kRexnXcsk=XN+X*N/2J*ImxnXcak=XN-X*N/2x_csnReXkx_canJ*ImXkNote: xn is a complex sequence. 53DFT Symmetric RelationsNote: xn is a real sequence.Length
24、-N SequencecN-point DFTxnXk=ReXk+jImXkx_evnReXkx_odnJ*ImXkSymmetry relationsXk=X*NReXk=ReXNImXk=-ImXN|Xk|=|XNargXk=-argXN545.7 DFT TheoremsType of Property length-N sequence N-point DFT Parsevals relationModulation gnhnGkHkCircular ConvolutionDuality Gn Ng -k NFrequency-shifting WN-k0ngn G k-k0 NCir
25、cular Time-shifting g n-n0 N WNkn0GkLinearity agn+bhn aGk+bHkhn Hkgn Gk55DFT Properties ApplicationsExample - Consider the two length-4 sequences repeated below for convenience:The 4-point DFT Gk of gn is given by:56DFT Properties ApplicationsTherefore:Likewise,57DFT Properties ApplicationsHence,The
26、 two 4-point DFTs can also be computed using the matrix relation given earlier.58DFT Properties ApplicationsD4 is the 4-point DFT matrix.59DFT Properties ApplicationsIf YCk denotes the 4-point DFT of yCn, then we get: YCk=GkHk, 0k3Thus:60DFT Properties ApplicationsA 4-point IDFT of YCk yields:615.9
27、Computation of the DFT of Real sequencesIn most practical applications, sequences of interest are real.In DFT definition, the sequence is assumed to be complex.Question 1: N-point DFTs of two real sequence using a single N-point DFT.Question 2: 2N-point DFT of a real sequence using a single N-point
28、DFT.625.9.1 N-point DFTs of two real sequence using a single N-point DFTApproach: Building a complex sequence with two real sequence to perform complex DFT, then use symmetry properties to recover two real DFTs.P222, processing and Examples.635.9.2 2N-point DFT of a real sequence using a single N-po
29、int DFTApproach: Building a complex sequence with the 2N-point real sequence to perform complex DFT, then use symmetry properties to recover the 2N-point real DFTs.P223, processing and Examples.645.10 Linear Convolution Using DFTLinear convolution is a key operation in many signal processing applica
30、tions.Since a DFT can be efficiently implemented using FFT algorithms, it is of interest to develop methods for the implementation of linear convolution using the DFT.655.10.1 Linear Convolution of Two Finite-Length SequencesExample: Now given two length-4 sequences: let us extended the two length-4
31、 sequences to length 7 by appending each with three zero-valued samples, i.e.66Linear Convolution of Two Finite-Length SequencesWe will determine the 7-point circular convolution of gen and hen:67Linear Convolution of Two Finite-Length SequencesFrom the above y0=g0h0=1 2=2y1 =g0h1+ g1h0 =(1 2)+(2 2)
32、=6y2 =g0h2+g1h1 +g2h0 =(1 1)+(2 2)+(0 2)=5y3 =g0h3+g1h2+ g2h1+ g3h0 =(1 1)+(2 1)+(0 2)+(1 2)= 5y4 =g1h3+g2h2+ g3h1 =(2 1)+(0 1)+(1 2)= 4y5 =g2h3+g3h2=(0 1)+(1 1)=1y6 =g3h3=(1 1) =168Linear Convolution of Two Finite-Length SequencesAs can be seen from the above that yn is precisely the sequence yLn o
33、btained by a linear convolution of gn and hn0 1 2 3 4 5 626541yLn69Linear Convolution of Two Finite-Length SequencesLet gn and hn be two finite-length sequences of length N and M, respectively.Denote L=N+M-1.Define two length-L sequences:70Linear Convolution of Two Finite-Length SequencesThen yLn=gn
34、 hn=yCn=gen henThe corresponding implementation scheme is illustrated below:*N715.10.3 Linear Convolution of a Finite-Length Sequence with an Infinite-Length SequenceWe next consider the DFT-based implementation of:*where hn is a finite-length sequence of length M and xn is an infinite length (or a
35、finite length sequence of length much greater than M).72Overlap-Add MethodFirst segment xn, assumed to be a causal sequence here without any loss of generality, into a set of contiguous finite-length subsequences xmn of length N each:where73Overlap-Add MethodThus we can write:*where*74Overlap-Add Me
36、thodL* As a result, the desired linear convolution has been broken up into a sum of infinite number of short-length linear convolutions of length N+M-1 each: Each of these short convolutions can be implemented using the DFT-based method discussed earlier, where now the DFTs (and the IDFT) are comput
37、ed on the basis of N + M - 1 points.75Overlap-Add MethodUsing the DFT-based approach,Now the first convolution in the above sum, , is of length N+M-1 and is defined for 0 n N + M 2.*76Overlap-Add Method* The second short convolution , is also of length N+M-1 but is defined for N n 2N + M 2.There is
38、an overlap of M - 1 samples between these two short linear convolutions.* Likewise, the third short convolution , is also of length N+M-1 but is defined for 2N n 3N + M 2.77Overlap-Add Method* Thus there is an overlap of M-1 samples between and .*In general, there will be an overlap of M-1 samples b
39、etween the samples of the short convolutions and for rN n rN + M 2.This process is illustrated in the figure on the next slide for M = 5 and N = 7.78Overlap-Add Method79Overlap-Add MethodAddAdd80Overlap-Add MethodTherefore, yn obtained by a linear convolution of xn and hn is given by:81Overlap-Add M
40、ethodThe above procedure is called the overlap-add method since the results of the short linear convolutions overlap and the overlapped portions are added to get the correct final result.The function fftfilt can be used to implement the above method.82Overlap-Add MethodProgram 5_5 illustrates the us
41、e of fftfilt in the filtering of a noise-corrupted signal using a length-3 moving average filter. The plots generated by running this programis shown below:83Discrete Cosine Transform A special style for DFT. DCT represents a real time-domain sequence xn by a real transform-domain sequence Xk.A kind
42、 of useful tool to help process digital images.5 DFT 与 FFT 的应用 利用 FFT 进行频谱分析 用FFT计算线性卷积 线性调频 Z 变换（Chirp-Z变换）及快速算法利用 FFT 进行频谱分析利用FFT进行频谱分析的基本方法设设设设 为长为为长为为长为为长为 N N 的有限长序列，则：的有限长序列，则：的有限长序列，则：的有限长序列，则：利用利用利用利用 FFT FFT 进行频谱分析的实现过程框图为：进行频谱分析的实现过程框图为：进行频谱分析的实现过程框图为：进行频谱分析的实现过程框图为：几个常用基本概念利用利用 FFT 进行频谱分析
43、进行频谱分析1 1、数字频率分辨率：、数字频率分辨率：、数字频率分辨率：、数字频率分辨率：2 2、模拟频率分辨率：、模拟频率分辨率：、模拟频率分辨率：、模拟频率分辨率：3 3、用于、用于、用于、用于FFTFFT的采样点数：的采样点数：的采样点数：的采样点数：4 4、频率刻度值：、频率刻度值：、频率刻度值：、频率刻度值：5 5、模拟信号长度：、模拟信号长度：、模拟信号长度：、模拟信号长度：6 6、分辨率：、分辨率：、分辨率：、分辨率：典 型 例 题例：例：用FFT来分析信号的频谱，若已知信号的最高频率为 ，要求频率分辨率为 ，试确定： 1、采样间隔 T ；2、采用基-2FFT的最小样点数 N ，
44、以及与此相对应的最小记录长度；3、按您确定的参数所获得的实际分辨率。解：解：解：解： 1 1、据采样定理，采样间隔据采样定理，采样间隔2 2、基基-2FFT-2FFT的最小样点数的最小样点数N N当采用基当采用基-2FFT-2FFT算法时，要求算法时，要求典典 型型 例例 题题与此相对应的最小记录长度为：与此相对应的最小记录长度为：3 3、按确定的参数所获得的实际分辨率按确定的参数所获得的实际分辨率用FFT进行频谱分析存在的两个问题利用利用 FFT 进行频谱分析进行频谱分析1 1、频谱泄漏、频谱泄漏、频谱泄漏、频谱泄漏在实际应用中，通常将所观测与处理的信号限制在一定的时间间隔内，即在时域对信号
45、进行 “ 截断操作 ” ，或 称作加时间窗加时间窗（用时间窗函数乘以信号）。由卷积定理可知：时域相乘、频域卷积，这就造成 “ 拖尾现象 ” ，称之为频谱泄漏频谱泄漏。若序列若序列 的长度为无限长，为了利用的长度为无限长，为了利用 FFT FFT 进行频谱分进行频谱分析，首先必须将其截断为有限长序列析，首先必须将其截断为有限长序列卷积定理卷积定理卷积定理卷积定理显然，两种频谱是有差别的，该现象就是显然，两种频谱是有差别的，该现象就是频谱泄漏频谱泄漏频谱泄漏频谱泄漏解决办法解决办法解决办法解决办法： 采用其它形式的窗函数采用其它形式的窗函数 对于周期序列，取其过零点截取对于周期序列，取其过零点截取
46、利用利用 FFT 进行频谱分析进行频谱分析2 2、栅栏效应、栅栏效应、栅栏效应、栅栏效应利用利用 FFT FFT 进行频谱分析时，只知道离散频率点进行频谱分析时，只知道离散频率点 的整数的整数倍处的频谱。在两个谱线之间的情况就不知道，这如同倍处的频谱。在两个谱线之间的情况就不知道，这如同通过一个栅栏观察景象一样，故称作通过一个栅栏观察景象一样，故称作栅栏效应栅栏效应栅栏效应栅栏效应。 解决办法：解决办法：解决办法：解决办法：在序列后面补零点加大在序列后面补零点加大FFTFFT点数点数 ，可使谱线，可使谱线间隔变小来提高分辨力，以减少栅栏效应。间隔变小来提高分辨力，以减少栅栏效应。注意：注意：注
47、意：注意：若需要加窗，则应先加窗再补零。若需要加窗，则应先加窗再补零。用FFT计算线性卷积线性卷积设设 是是 和和的线性卷积：的线性卷积： 总运算量为：总运算量为：可见，直接运算时运算量很大，必须寻找新思路。可见，直接运算时运算量很大，必须寻找新思路。思路：思路：思路：思路：利用利用利用利用 FFT ,FFT ,通过循环卷积来计算线性卷积通过循环卷积来计算线性卷积通过循环卷积来计算线性卷积通过循环卷积来计算线性卷积利用循环卷积计算线性卷积的条件用用FFT计算线性卷积计算线性卷积设设 是是x(n)x(n)和和h(n)h(n)长为长为L L的循环卷积：的循环卷积：其中其中 LMaxN,M,LMax
48、N,M,用用FFT计算线性卷积计算线性卷积用用FFT计算线性卷积计算线性卷积上式表明上式表明上式表明上式表明： 是将是将 以以L L为周期进行延拓后再取为周期进行延拓后再取主值区间所得的序列。主值区间所得的序列。利用循环卷积计算线性卷积的利用循环卷积计算线性卷积的利用循环卷积计算线性卷积的利用循环卷积计算线性卷积的条件为：条件为：条件为：条件为：利用循环卷积计算线性卷积如下图利用循环卷积计算线性卷积如下图用用FFT计算线性卷积计算线性卷积利用FFT进行线性卷积的步骤、将已知序列、将已知序列 （长为（长为N N）和）和 （长为（长为MM）补零）补零延长，使它们的长度延长，使它们的长度 。若采用基
49、。若采用基 -2 -2 FFTFFT算法，还应使算法，还应使 大于或等于大于或等于 的的 2 2 的最小整数次的最小整数次幂。幂。、做、做 和和 的长为的长为 点的点的 FFT FFT 得到得到 和和 ，并求它们的积并求它们的积 。、求、求 的的 IFFTIFFT并取前并取前 点获得线性卷积的结果为点获得线性卷积的结果为长序列FFT卷积的计算方法用用FFT计算线性卷积计算线性卷积实际中常常出现两个待卷积序列长度相差很大的情形，实际中常常出现两个待卷积序列长度相差很大的情形，例如输入序列例如输入序列 的长度的长度 远远大于滤波器的脉冲响远远大于滤波器的脉冲响应应 的长度的长度 时时, ,若仍然取
50、若仍然取 FFT FFT 的长度的长度 , ,则必须对则必须对 补很多补很多0 0，同时也做不到，同时也做不到 “ “ 实时处理实时处理 ” ” 。此时常采用以下两种分段处理方法。此时常采用以下两种分段处理方法。用用FFT计算线性卷积计算线性卷积1 1、重叠相加法、重叠相加法、重叠相加法、重叠相加法设设 长度为长度为 , , 为无限长。取为无限长。取 “ “ 段长段长 ” ”尽可尽可能能 与与 接近。则：接近。则： 是两个长度接近且分别为是两个长度接近且分别为和和 的序列的线性卷积，可很有效地求其的序列的线性卷积，可很有效地求其L L点的点的FFT.FFT.用用FFT计算线性卷积计算线性卷积分
51、别求得各段卷积后再将结果相加，即可求得分别求得各段卷积后再将结果相加，即可求得 和和 的完整的线性卷积。的完整的线性卷积。该方法中由于运用了该方法中由于运用了“ “分段卷积的重叠分段卷积的重叠” ”和和“ “各段卷积结各段卷积结果的相加果的相加” ”，故称为，故称为重叠相加法重叠相加法重叠相加法重叠相加法。用重叠相加法计算两个长度悬殊序列线性卷积的步骤如下：用重叠相加法计算两个长度悬殊序列线性卷积的步骤如下：用重叠相加法计算两个长度悬殊序列线性卷积的步骤如下：用重叠相加法计算两个长度悬殊序列线性卷积的步骤如下： 将 补零延长到 ，并计算其 点FFT，得 到 分别将各 补零延长到 ，并计算其 点
52、FFT，得到 计算计算 ，并求其，并求其L L点的反变换，即：点的反变换，即： 将将 的重叠部分相加，最后得到结果的重叠部分相加，最后得到结果用用FFT计算线性卷积计算线性卷积重叠相加法卷积示意图2 2、重叠保留法、重叠保留法、重叠保留法、重叠保留法用用FFT计算线性卷积计算线性卷积设序列设序列 的长度为的长度为 ，则对长序列，则对长序列 的分段方法如的分段方法如下：先在序列下：先在序列 前补前补 个个0 0，然后对补，然后对补0 0后的序列后的序列进行分段，每段的长度为进行分段，每段的长度为 , ,即：即：对每一段对每一段 ，通过循环卷积，通过循环卷积 ，获，获得俩者的线性卷积得俩者的线性卷
53、积 。而输入的每段。而输入的每段序列重叠序列重叠N-1N-1点，故每段的循环卷积的输出应去掉前面点，故每段的循环卷积的输出应去掉前面N-1N-1点只保留后面点只保留后面MM点，即点，即 ：用用FFT计算线性卷积计算线性卷积重重重重叠叠叠叠保保保保留留留留法法法法分分分分段段段段方方方方法法法法示示示示意意意意图图图图用用FFT计算线性卷积计算线性卷积线性调频Z变换(Chirp- Z 变换)算法问题的引入仅管采用仅管采用 FFT FFT 可计算出有限长序列的可计算出有限长序列的DFT DFT ，但它要求序，但它要求序列长度列长度 为为2 2的整数幂或合数。实际中的整数幂或合数。实际中有时只对信号
54、有时只对信号的某一频段感兴趣，即只需要计算单位圆上某一段的频的某一频段感兴趣，即只需要计算单位圆上某一段的频谱值，例如对窄带信号进行频谱分析时，总是要求在窄谱值，例如对窄带信号进行频谱分析时，总是要求在窄带范围内的抽样点足够密集，而窄带范围外则不需考虑。带范围内的抽样点足够密集，而窄带范围外则不需考虑。此时若依然采样以上方法，则需增加频域抽样点数，增此时若依然采样以上方法，则需增加频域抽样点数，增加了窄带范围外的不需要的计算量；加了窄带范围外的不需要的计算量；在语声信号处理在语声信号处理时信号极点处的频谱十分关键，而极点位置往往离单位时信号极点处的频谱十分关键，而极点位置往往离单位圆较远，此时
55、不能采用圆较远，此时不能采用FFTFFT；若若 是大素数时也无法是大素数时也无法采用采用FFTFFT。上述几种情形可采用上述几种情形可采用线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法加以解决。算法的基本原理线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法设设 是有限长序列，是有限长序列，沿沿Z Z平面上的一段螺线做平面上的一段螺线做MM点抽样，得到以下抽样点：点抽样，得到以下抽样点：其中其中A A和和WW为复数为复数, ,极坐标形式分别为：极坐标形式分别为：式中式中 和和 为实数，当为实数，当K=0K=0时有时有可见，可见， 决定谱分析起始点决定谱分析起始点
56、 的位置；的位置； 的值决定分析的值决定分析路径的盘旋趋势；路径的盘旋趋势； 表示两个相邻分析点之间的夹角表示两个相邻分析点之间的夹角线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法如果如果 ， 则则 的抽样点位于半径为的抽样点位于半径为 r r 的的圆上；如果圆上；如果 ，则，则 的抽样点位于单位圆的抽样点位于单位圆上（常规的上（常规的DFTDFT变换）；如果变换）；如果 ，则随着，则随着k k增大，分增大，分析点析点 以以 为步长向外盘旋；为步长向外盘旋； 时向内旋。时向内旋。C Ch hi ir rp p- -Z Z变变变变换换换换的的的的频频频频率率率率抽抽抽抽样样样样
57、点点点点线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法Chirp- Z 变换的方框图线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法Chirp-ZChirp-Z变换变换的方框图如下：如下：说明线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法 上面框图中，上面框图中， 可看成一个数字网络的可看成一个数字网络的单位脉冲响应。单位脉冲响应。 所对应的系统的输出为：所对应的系统的输出为： 这可以设想为频率随时间线性增长的复指数序列这可以设想为频率随时间线性增长的复指数序列, ,即即线性调频线性调频线性调频线性调频(Chirp)(Chirp)信号信号信号
58、信号。故将上述变换称为。故将上述变换称为线性调频线性调频Z变换变换(Chirp- Z 变换变换)（简称为CZT）Chirp-Z变换的实现线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法 确定线性卷积的区间。序列 的长度为N， 的长度也应是N ，而而 是无限长的，需是无限长的，需截取。但因谱分析点数仅为截取。但因谱分析点数仅为MM点，故只需要计算点，故只需要计算 在在 00，M-1M-1上上MM个值。个值。为计算出V(n)在区间0,M-1上的M个值，只要截取h(n)在区间-(N-1),(M-1)上的(N+M-1)个值。这时经线性卷积所得V(n)的非零值区间为-(N-1)，(N+M
59、-2)，长度为2N+M-2。线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法 确定用循环卷积计算线性卷积时的循环卷积计算线性卷积时的 FFT FFT 长度长度 L L 。为了用循环卷积代替线性卷积计算出V(n)在0,(M-1)区间上的 M个序列值，必须保证在上式的周期延拓中，在0，M-1区间上不能有混叠，循环卷积区间长度 L应大于或等于N+M-1。故在用基-2 FFT算法进行快速卷积计算时，应选择应选择L L(N+M-1)(N+M-1)且满足且满足且满足且满足 (m(m为自然数为自然数为自然数为自然数) )的最小值的最小值的最小值的最小值。计算计算Chirp- Z 变换变换所用
60、的序列见下图线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法注意注意: 若选择L=N+M-1，那么y(n)尾部应补M-1个零。并将h(n)从-(N-1)到(M-1)所截取的一段序列以L为周期进行周期延拓，取主值序列形成 ，这时可以用快速卷积法计算如上构造的两个序列y(n)和 的循环卷积。 当选择 N+M-1时，y(n)应补L-N个零点，而h(n)从区间(-N+1)，(M-1)截取后在-N+1点前面补 L-N+M-1)个零点后，以L为周期进行周期延拓。或直接截取-（L-M），（M-1）上的值后，再以L为周期进行周期延拓取主值。Chirp- Z 变换算法具体步骤线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法 形成形成 序列序列 计算计算 的的 FFTFFT 作序列作序列线性调频线性调频Z变换变换(Chirp- Z 变换变换)算法算法 计算计算 的的 FFTFFT 计算计算 的的 IFFT IFFT 得得 求求115HomeworkBook 4th Edition in EnglishP. 238: 5.25, 5.26P.240: 5.41, 5.43P.242: 5.60, 5.61P. 243: 5.63P. 248: M 5.7
