离散傅立叶变换的运算特点.ppt
快速傅立叶变换,快速傅立叶变换,2,2023/9/18,引言,有限长序列通过离散傅里叶变换(DFT)将其频域离散化成有限长序列。但其计算量太大，很难实时地处理问题，因此引出了快速傅里叶变换(FFT)。FFT 并不是一种新的变换形式，它只是DFT 的一种快速算法。并且根据对序列分解与选取方法的不同而产生了FFT 的多种算法。FFT:Fast Fourier Transform1965年，Cooley,Turkey 机器计算傅里叶级数的一种算法,3,2023/9/18,直接计算DFT的问题及改进途径,离散傅立叶变换（DFT）的定义为：,4,k0，1，2，N1,n0，1，2，N1,2023/9/18,DFT运算量,2023/9/18,5,由此看出：直接计算DFT时，乘法次数与加法次数都是和N的平方成比例的。当N很大时，所需工作量非常可观。当N=1024点时，直接计DFT需要：次，即四百多万次的实数乘法运算。这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求。可利用DFT运算的系数 的固有对称性和周期性，改善DFT的运算效率,2023/9/18,6,2023/9/18,7,8,2023/9/18,9,2023/9/18,FFT算法分类:,时间抽选法DIT:Decimation-In-Time频率抽选法DIF:Decimation-In-Frequency,7-2 按时间抽取的FFT算法,7-2 按时间抽取的FFT算法,一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式,11,2023/9/18,一、按时间抽取的算法原理,设序列点数 N=2L，L 为整数。若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：,12,2023/9/18,13,则x(n)的DFT:,2023/9/18,14,再利用周期性求X(k)的后半部分,2023/9/18,15,一个“蝶形运算”包含1次乘法，2次加法,2023/9/18,16,2023/9/18,17,分解后的运算量：,运算量减少了近一半,2023/9/18,N/2仍为偶数，进一步分解：N/2 N/4,18,2023/9/18,19,同理：,其中：,这样逐级分解，直到2点DFT,基2时间抽取FFT算法流图,20,N=2,xk=x0,x1,2023/9/18,4点基2时间抽取FFT算法流图,21,X10,X11,X20,X21,-1,-1,-1,-1,X 0,X 1,X 2,X 3,2023/9/18,22,2023/9/18,4点基2时间抽取FFT算法流图,8点基2时间抽取FFT算法流图,23,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,2023/9/18,24,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,8点基2时间抽取FFT算法流图,2023/9/18,基2时间抽取FFT算法,25,第一级,第二级,第三级,2023/9/18,二、按时间抽取的算法特点,26,1.计算速度 当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。,复数乘法：,复数加法：,比较DFT,2023/9/18,27,2023/9/18,算法的计算复杂度,28,2023/9/18,例.如果一台通用计算机的速度为平均每次复乘，每次复加，用它来计算512点的，问直接计算需要多少时间，用 运算需要多少时间。,复乘所需时间,复加所需时间,所以直接利用DFT 计算所需时间：,2023/9/18,29,复乘所需时间,复加所需时间,所以用 FFT 计算所需时间,(2)利用 计算：复乘次数为，复加次数为。,2023/9/18,30,2.倒序排列,31,32,倒序,k,0,k,1,k,2,2023/9/18,3.同址运算 在同一级蝶形运算中，两信号只参与一次运算。4.蝶距规律,33,三、按时间抽取FFT算法的其它形式,34,2023/9/18,35,2023/9/18,36,2023/9/18,37,2023/9/18,7-3 按频率抽取的FFT算法,一、按频率抽取的算法原理二、按频率抽取的算法特点三、与按时间抽取算法的对称性,38,一、按频率抽取的算法原理,设序列点数 N=2L，L 为整数。若不满足，则补零将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半,39,40,则x(n)的DFT:,41,按k的奇偶将X(k)分成两部分：,令,42,则X(2r)和X(2r+1)分别是x1(n)和x2(n)的 N/2点DFT，记为X1(k)和X2(k),43,N/2仍为偶数，进一步分解：N/2 N/4,44,45,逐级分解，直到2点DFT,46,同理：,其中：,48,X0,X6,X4,X2,X1,X5,X3,X7,49,0,N,W,1,N,W,2,N,W,3,N,W,-1,-1,-1,-1,x0,x3,x1,x2,x4,x5,x6,x7,0,N,W,2,N,W,2,N,W,0,N,W,X0,X6,X4,X2,X1,X5,X3,X7,0,N,W,0,N,W,0,N,W,0,N,W,-1,-1,-1,-1,-1,-1,-1,-1,时间抽取和频率抽取FFT算法：,二、按频率抽取的算法特点,50,1.计算速度 当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。,复数乘法：,复数加法：,无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率抽取算法这两种FFT算法是完全等价的。,2.排序规则输入序列x（n）是自然顺序的，输出序列X（k是倒置顺序的。其整序规则与按时间抽取算法是完全一致的。,51,3.同址运算该算法和按时间抽取算法一样也是进行同址运算的。4.蝶距规律其蝶形系数的分布规律与按时间抽取算法是完全对称的。,52,三、与按时间抽取算法的对称性,二者具有完全对称的蝶距规律蝶形结构和运算流图也都是完全对称的需要的复乘和复加次数也相同频率抽取法运算流图是时间抽取法运算流图的转置，若知道其中一个，应用转置关系就可以得到另一个。,53,7-3 按频率抽取的FFT算法,一、按频率抽取的算法原理二、按频率抽取的算法特点三、与按时间抽取算法的对称性,54,一、按频率抽取的算法原理,设序列点数 N=2L，L 为整数。若不满足，则补零将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半,55,56,则x(n)的DFT:,57,按k的奇偶将X(k)分成两部分：,令,58,则X(2r)和X(2r+1)分别是x1(n)和x2(n)的 N/2点DFT，记为X1(k)和X2(k),59,N/2仍为偶数，进一步分解：N/2 N/4,60,61,逐级分解，直到2点DFT,62,同理：,其中：,64,X0,X6,X4,X2,X1,X5,X3,X7,65,0,N,W,1,N,W,2,N,W,3,N,W,-1,-1,-1,-1,x0,x3,x1,x2,x4,x5,x6,x7,0,N,W,2,N,W,2,N,W,0,N,W,X0,X6,X4,X2,X1,X5,X3,X7,0,N,W,0,N,W,0,N,W,0,N,W,-1,-1,-1,-1,-1,-1,-1,-1,时间抽取和频率抽取FFT算法：,二、按频率抽取的算法特点,66,1.计算速度 当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。,复数乘法：,复数加法：,无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率抽取算法这两种FFT算法是完全等价的。,2.排序规则输入序列x（n）是自然顺序的，输出序列X（k是倒置顺序的。其整序规则与按时间抽取算法是完全一致的。,67,3.同址运算该算法和按时间抽取算法一样也是进行同址运算的。4.蝶距规律其蝶形系数的分布规律与按时间抽取算法是完全对称的。,68,三、与按时间抽取算法的对称性,二者具有完全对称的蝶距规律蝶形结构和运算流图也都是完全对称的需要的复乘和复加次数也相同频率抽取法运算流图是时间抽取法运算流图的转置，若知道其中一个，应用转置关系就可以得到另一个。,69,
