Fast Fourier Transforms

Presentation on theme: "Fast Fourier Transforms"— Presentation transcript:

1 Fast Fourier Transforms
Chapter 4 FFT__ Fast Fourier Transforms SHNU.信息机电学院

2 第四章概要： 1. DFT, FFT的计算量估计 2. FFT快速运算的措施 3. 蝶形运算节：输入点的距离, 旋转因子的特点 4. FFT I/O数据的译序（倒位序、原位运算） 5. 基2（Radix-2）DIT-FFT原理，23分解的流图 DIF-FFT原理，23分解的流图 6. IFFT, FFT的运算关系 7. N为复合数的FFT： 矩阵形式、译序方法 8. CZT特点和算法思想 9. 长序列线性卷积、线性相关的FFT： 重叠相加、重叠保留、 快速相关。 SHNU.信息机电学院

3 4.1 Introduction 1/3 一．FFT 实现DFT的各种快速算法. FFT计算量比直接计算DFT大大减少.
二．直接计算N点DFT的计算量: X(k)DFT[x(n)]= x(n)WNk n, k =0, 1, …, N1. 每个k，复数乘：N次，复数加： N-1次。  N个k： N2次， N(N1)次. 直接DFT计算运算量(复数乘、加)  N2. N很大时, 运算量很大,费时,不适用实时数据处理. SHNU.信息机电学院

4 4.1 Introduction 2/3 e-j(2/N)kN=1 SHNU.信息机电学院 三. DFT计算量减少的原理:
 变换因子WN: WN = ej(2/N)  旋转因子WNm ：具有周期性、对称性、可约性. 周期性: WNm+Nl = ej(2/N)(m+N l)=ej(2/N)m =WNm=WN(m+N l)mod(N). 对称性: 相对z平面实轴： WNk(N m)=WNkm=(WNkm)* 相对z平面原点： WNN/2+m=e-j(2/N)(m+N/2) =e-j(2/N)me-j=－WNm 可约性： WNm =WNkmk = WN/km/k,  利用旋转因子WNm的对称性,周期性,可约性,长序列的DFT分解为更小点数的DFT, 运算量. e-j(2/N)kN=1 SHNU.信息机电学院

5 4.1 Introduction 3/3 四. 两类算法  按时间抽取法 Decimation in Time:
WN(Nm) =WNm =(WNm)* WNk(N+n) =WN(N+k)n =WNkn WNm WN0 对称性 周期性 图4.1 旋转因子的圆周对称性、N点周期性示意 四. 两类算法  按时间抽取法 Decimation in Time:  按频率抽取法 Decimation in Frequency: SHNU.信息机电学院

6 4.2 Radix-2 FFT 1/19 一. Radix-2 FFT: 设输入序列x(n), n=0, 1, …, N1. 长为N.
 DFT的点数: N=2M. M=log2(N) N是2的整数幂.  x(n)后补零达到最接近的N=2M值. 二. Cooley-Tukey (DIT－FFT) Method  思路: 把N=2M点DFT  N/2点 DFT  N/4点 DFT  … 2点 DFT 计算量. SHNU.信息机电学院

7 4.2 Radix-2 FFT 2/19 SHNU.信息机电学院  算法依据及相关特性:  x(n)
x(2r) = x1(r), x(2r+1)= x2(r), r =0, 1, …, N/21. 2. x(n)的N点 DFT:  X(k) x(n)WNkn, k =0, 1,…,N1. X(k)= x(2r)WNk (2r) x(2r+1)WNk (2r+1), = x1(r)(WN2)k r+ WNk x2(r)(WN2)k r,  X(k) X1(k)+ WNkX2(k), k=0,1,…,N/21， X1(k), X2(k): 序列x1(r),x2(r)的N/2点DFT. 得到一半的DFT ,X(k) SHNU.信息机电学院

8 4.2 Radix-2 FFT 3/19  k=N/2, …, N1, 另一半DFT：
∵ WN/2周期N/2 , WN/2(k+N/2) =WN/2k， 且WN(k+N/2) =－WNk ∴ X1(k+N/2) = x1(r)(WN/2)(k+N/2)r = x1(r)(WN/2)kr =X1(k) X2(k+N/2) =X2(k)  X(k+N/2) X1(k+N/2)+WN(k+N/2)X2(k+N/2), =X1(k)WNkX2(k), k =0, 1, …, N/21. N/ N-1 Xi(k) 图4.2 奇偶抽取序列的DFT在k=0~N-1上,前后复制 SHNU.信息机电学院

9 4.2 Radix-2 FFT 4/19 3. 蝶形运算 已知k=0, 1, …, N/2-1区间的X1(k) , X2(k).
 蝶形运算求出 X(k), X(k+N/2).  信号流图符号: 复数乘1次 X(k)=X1(k)+WNk X2(k) X1(k) 输出 输入 加减 WNk X(k+N/2)=X1(k) –WNkX2(k) X2(k) 乘系数 复数加2次 图4.3 蝶形运算规则 SHNU.信息机电学院

10 4.2 Radix-2 FFT 5/19 4. 按时间抽取的算法: 1) N点序列,分解成2个N/2点，
3) …….经M-1次分解，… N’=2M/2M-1 =2点 4) N点DFT  N/2个2点DFT。 5) 蝶形运算有M级，每级N/2个蝶形运算 图4.4 N点DIT―FFT运算流图(N=8=23) SHNU.信息机电学院

11 4.2 Radix-2 FFT 6/19 5. DIT-DFT和直接DFT运算量的比较  N=2M点DFT的DIT－DFT方法:
M级，每级N/2个蝶形运算。 一个蝶形运算: 1次复数乘, 2次复数加。  Radix-2 FFT: 复数乘: CM(2)＝M*N/2＝N/2 log2(N) 复数加: CA(2)＝M*2*N/2＝Nlog2(N)  直接运算, 复乘: N2， 复加: N(N-1)；  当N>>1时，N2>> N/2 log2(N) SHNU.信息机电学院

12 4.2 Radix-2 FFT 11/19  蝶形运算两个点的 “间距”  N=23距离: Lth级 系数 两点间距=2L-1
1st : WN0=1, 2nd : WN0, WN2, 3rd : WN0, WN1, WN2, WN SHNU.信息机电学院

13 4.2 Radix-2 FFT 12/19 左起Lth级, 每个蝶形运算的两节点“距离”2L-1. L=1,…,M.
X3(0) X3(1) X1(0) X1(1) X1(2) X1(3) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) WN0 x(4) WN0 x(2) WN0 X4(0) X4(1) x(6) WN2 x(1) X5(0) X5(1) X2(0) X2(1) X2(2) X2(3) x(5) WN1 X6(0) X6(1) WN2 x(3) WN3 x(7) 左起Lth级, 每个蝶形运算的两节点“距离”2L-1. L=1,…,M. 图4.6 系数WNp的变化规律、蝶形运算的间距示意 SHNU.信息机电学院

14 4.2 Radix-2 FFT 13/19  系数WNk的变化规律: N=2M.  M级(列); 每级有N/2个蝶形运算.
每个蝶形要乘因子WNp， p=旋转因子的指数, p＝0,1,…,N/2－1。  Lth级， 第J个系数WNp ： J＝0,1,…, 2L-1-1， p＝2M－LJ 例:N=23, M=3. 2nd蝶形运算 ,L=2 ∵2L-1-1＝1, ∴J＝0,1； p＝2M－LJ = 0, 2.  2nd蝶形运算的两个乘因子WN0,WN2; XL-1(k) XL(k)=XL-1(k) +WNpXL-1(k+2L-1) XL-1(k+2L-1) XL(k+2L-1)=XL-1(k) –WNpXL-1(k+2L-1) WNp SHNU.信息机电学院

15 4.2 Radix-2 FFT 14/19  系数WNp总结 : 10 第一级（列） WN0=1;
30 第M级有N/2个系数：WN0, WN1, …, WNN/2. 从右向左每推进一列： 系数取右列系数中偶数序号的那一半. SHNU.信息机电学院

16 4.2 Radix-2 FFT 8/19  Shuffling (重整、整序)
 bit reversal (倒位序,变址运算,位反序): DIT:  对N点序列奇偶抽取,直到2点DFT. 对自然顺序输入的数据的重整, 整序.  以N=8为例: 10 奇偶抽取：位反序. 20 整序后的4个2点序列可作2点DFT. 30 DIT-FFT的结果是自然序列。 SHNU.信息机电学院

17 4.2 Radix-2 FFT 9/19 整序规律, 变址运算(位反序): 设N=8. 位反序 奇偶抽取 2nd 1st n0n1n2
111 x(0) x(2) x(4) x(6) x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) 000 100 010 110 001 101 011 111 x(2) x(6) x(1) x(5) x(1) x(3) x(5) x(7) x(3) x(7) 按n0的奇偶性 按n1的奇偶性 图4.5a N=23点DIT―FFT的整序示意 SHNU.信息机电学院

18 4.2 Radix-2 FFT 10/19 倒序的实现： 10 用硬件电路和汇编程序实现,交换寄存器内容。 20 用高级语言程序实现倒序.
根据倒序数的十进制数的运算规律。 把原自然顺序排列的输入数组中相应序号的数组内容互换。 n＝(n2,n1,n0) 倒位序 n^＝(n0,n1,n2) n^< n，已交换， n^= n, 不交换 n^>n，交换 图4.5b N=23点DIT―FFT的整序实现 SHNU.信息机电学院

19 4.2 Radix-2 FFT 7/19 6. DIT－FFT的运算规律及编程思想 原位运算: 同一存储单元存储蝶形运算I/O数据。
 N=2M点DIT-FFT: M级, 每级N/2个蝶形运算. 各蝶形运算: 两输入 两输出: 直接存入原输入数据占用的存储单元.  DIT-FFT运算结束, N个存储变量对应的内容全部更新成X(k). ____节省内存. 硬件处理器, 成本. SHNU.信息机电学院

20 4.2 Radix-2 FFT 15/19  FFT的程序步骤  x(n)倒序, 存入数组x中, L=1,…,M。
 Lth级蝶形运算后, 一半的数组元素值XL(J)； J＝0,1,…,2L－1-1， 各蝶形的两个输入数据间距B=2L-1; 乘子WNp对应间隔为2L点的2M－L个蝶形。 p＝2M－LJ  DIT-FFT的输出X(k)是自然顺序： XL(k) =XL-1(k)＋WNpX L-1(k+B) XL(k+B)=XL-1(k)－WNpX L-1(k+B) k=J:2L:N-1， MatLab colon oper. Start:skip:end SHNU.信息机电学院

21 4.2 Radix-2 FFT 16/19 三．Sand-Tukey(DIF)–FFT 1. 特点:  自然顺序序列x(n)前后对半分组,
 一直分到2点序列.  N=2M点的DFT  由 2M－1个 2点DFT得到。  DFT是”乱序”___位反序排列. 2. 与DIT-FFT的比较:  DIF和DIT ： x(n)的整序, DFT的顺序排列规律不同.  复乘子在减法运算后. 均可进行原位运算.  运算量相同。 SHNU.信息机电学院

22 4.2 Radix-2 FFT 17/19 图4.7 DIF―FFT二次分解运算流图(N=8) SHNU.信息机电学院 正序 乘子在蝶形后
位反序 图4.7 DIF―FFT二次分解运算流图(N=8) SHNU.信息机电学院

23 4.2 Radix-2 FFT 18/19 四．IDFT 直接用现成的FFT程序。(以前讲过) 据旋转因子的共轭对称性,
用共轭运算+FFT程序实现Fast IDFT－IFFT. 专门编制IFFT程序。程序流图：  DIT-FFT,or DIF-FFT流图中的旋转因子  WNp  WN－p，  最后的输出乘1/N。  输入X(k)，输出就是序列x(n)。 SHNU.信息机电学院

24 4.2 Radix-2 FFT /19 图4.8 DIF―IFFT运算流图,N=8 (防止溢出)) SHNU.信息机电学院

25 基2FFT的扩展：分裂基算法 设序列的长度N=4p，p＝N/4＝2R。 则N点DFT可1次分解  1个N/2点的DFT，radix2(2点抽取);+ 2个N/4点的DFT，radix4(4点抽取). 特点: 基2, 基4抽取合在一起. 运算流图与基2FFT相似. 运算稍快;减少运算量30%. 程序复杂.适用于专用硬件处理器中 P ， 本节不要求 SHNU.信息机电学院

26 4.3 General FFT Theory____Matrix Form 1/10
一. Methodology DFT的点数N=ML.  一维序列x(n)可写成L*M矩阵形式; 矩阵中行n1,列n0上的元素x(n1,n0)对应序列值x(n), n=Mn1+n0. 列序号 x L*M  L行 行序号 M列 SHNU.信息机电学院

27 4.3 General FFT Theory____Matrix Form 2/10
 按列作L点DFT（如n0列）， L个谱值记为 X1 L*M矩阵的对应n0列的各行元素： 原位运算 X1 L*M= SHNU.信息机电学院

28 4.3 General FFT Theory____Matrix Form 3/10
 X1 L*M 各元素分别乘旋转因子得 X'1 L*M=WNn0k0mod(N).*{X1(k0,n0)}  X'1 L*M按行作M点DFT， M个谱值是X2 L*M中对应k0行的各列元素: X2 L*M = SHNU.信息机电学院

29 4.3 General FFT Theory____Matrix Form 4/10
 X2 L*M转置得XM*L(k1,k0); 实现: 对X2 L*M中X2(k0,k1)译序: k＝Lk1+ k0。就是N= LM点DFT X(k)， 把大点数的DFT分解成了两个小点数的DFT。 同样, 还可对L,M点的DFT用矩阵形式继续分解。 如硬件同址运算，要考虑整序-位反序. SHNU.信息机电学院

30 4.3 General FFT Theory____Matrix Form 5/10
二． 进一步减少运算量的措施 1. 多类蝶形单元运算： 用程序的复杂度换取计算量的提高. 无关紧要的旋转因子： 旋转因子＝ 1, j 。如WN0, WNN/2, WNN/4。 乘这些因子的蝶形运算单独编程。可使普通N=2M点DIT-FFT的复乘次数从 NM/2 降至 CM(2)=N(M-3)/2+2。 SHNU.信息机电学院

31 4.3 General FFT Theory____Matrix Form 6/10
特殊的复数运算: WNN/8=(1-j)/ 的特殊性，使每个与该因子复乘所需的4次实数乘，2次实数加  2次实数乘，2次实数加。 eg. N=2M点DIT-FFT的实数乘次数： RM(2)= 4 [N/2(M-3)+2]－(N/2 －2) =N(2M－13/2)+10 SHNU.信息机电学院

32 4.3 General FFT Theory____Matrix Form 7/10
 （程序中）各类蝶形单元运算 1类：包含所有的旋转因子； 2类：去掉WNr=1的旋转因子； 3类：去掉WNr= 1、WNr =j 的旋转因子； 4类：去掉WNr=1、WNr=j 的旋转因子，并 考虑 WNr=(1-j)/ 的特殊性； （编专用子程序） SHNU.信息机电学院

33 4.3 General FFT Theory____Matrix Form 8/10
2. Generation of twiddle factors 用多占内存，换取计算量的提高。预先计算出所有的 旋转因子，存于数组中，用时直接查表得其值。 3. FFT to real sequence 一个N点FFT同时运算两个实序列. 设x1(n)  X1(k), x2(n)  X2(k). 10 构造N点复序列x(n)＝x1(n)＋j x2(n)，  DFT: X(k)= X1(k)+j X2(k) 20 利用共轭对称性： X1(k)＝ [X(k)+X*(N-k)]/2 ＝Xep(k), X2(k)＝－j[X(k)－X*(N-k)]/2 ＝－j Xop(k) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) SHNU.信息机电学院

34 4.3 General FFT Theory____Matrix Form 9/10
 用N/2点的FFT，计算N=2M点实序列x(n)的FFT。 10 把x(n)进行奇偶抽取，分成两个子序列。 构造：y(n)=x(2n)+jx(2n+1)，n＝0,1,…,N/2-1 计算N/2点FFT得Y(k)。k＝0,1,…,N/2-1。 20 DFT(x(2n)) X1(k) =Yep(k) = [Y(k)+Y*(Nk)]/2； DFT(x(2n＋1)) X2(k) =－jYop(k)= j[ Y(k) Y*(Nk)]/2； X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) SHNU.信息机电学院

35 4.3 General FFT Theory____Matrix Form 10/10
30 蝶形运算 X(k)= X1(k)+WNkX2(k) X(N-k) =X1(k) WNk X2(k) ， k＝0,1,…,N/2-1。 40 但x(n)是实序列，另一半DFT也可如下求： X(N-k)=X*(k) ， k＝0,1,…,N/2-1。 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) SHNU.信息机电学院

36 4.4 FFT应用于长序列卷积 1/5  快速卷积: 快速线性卷积用(FFT)快速圆周卷积实现. 设x(n)长L, h(n)长M
各自的N=L+M1点DFT (FFT)X(k), H(k)  X(k)H(k)  IDFT : x(n) h(n)  线性卷积, 系统输出.  运算量：直接卷积md=LM; 快速卷积mF=(3/2)Nlog2N+N LM>64: M, mF<<md; L>>M: 分段圆周卷积(重叠相加,重叠保留法). y(n) x(n) N h(n) L M L+M-1 N点 SHNU.信息机电学院

37 4.4 FFT应用于长序列卷积 2/5  重叠相加: Overlap-Add  h(n)长为M，
把x(n)分成长为L的小段. L> M。 各小段后补零为长N点的序列 xk(n), N=L+M-1 每组输入: L个新点＋最后M-1个零 每段与h(n)的线性卷积: xk(n)*h(n) 快速卷积 (N=L+M-1点圆周卷积), xk(n) h(n) 把各段的卷积(含重叠部分)相加 系统输出. 各段圆周卷积结果有 N-L=L+ M -1- L = M 1点的重叠. “重叠相加” N SHNU.信息机电学院

38 4.4 FFT应用于长序列卷积 3/5 ＋ 图4.14 重叠相加原理示意 SHNU.信息机电学院 每组点数N=L+M-1 后补M-1个零
图4.14 重叠相加原理示意 SHNU.信息机电学院

39 4.4 FFT应用于长序列卷积 4/5  重叠保留: Overlap-save，
 h(n)长为M.把x(n)分成长为L的小段，L>M。 各小段均补成长N点的序列 xk(n). 特殊点：1st段,在其前补M-1个零. xk(n)的前M-1点是xk-1(n) 的最后M-1点. ”重叠保留” 每组输入: 前一段保留下的M-1点＋L个新点  每段与h(n)的线性卷积 快速卷积 (N=L+M-1点圆周卷积),  把各段的卷积结果的前L+ M -1- L= M 1点舍去。  各段卷积结果连接起来.系统输出. SHNU.信息机电学院

40 4.4 FFT应用于长序列卷积 5/5 图4.15 重叠保留原理示意 SHNU.信息机电学院 每组点数N=L+M-1
重叠保留法： 每段输出的前M-1个舍弃 前M－1个输入点:上段保留下来的 图4.15 重叠保留原理示意 SHNU.信息机电学院

41 4.5 Chirp-ZT (CZT) 1/9 一、意义  窄带信号的高频率分辨率快速分析：fA~fB  准确地快速测定极点频率
极点离单位圆远 螺线上采样 谱有尖峰 圆周上采样 谱平坦 图4.9 CZT快速测定极点频率 SHNU.信息机电学院

42 4.5 Chirp-ZT (CZT) 2/9 二、定义：  X(zk)= x(n)[AW-k]-n ,
= x(n)A-n Wkn ；k=0,…M-1 其中, A=A0ej0 W=W0e-j0 ,任意复常数。 图4.10 CZT算法定义 SHNU.信息机电学院

43 4.5 Chirp-ZT (CZT) 3/9 三、特点：  输入和输出序列长可以不相等；N,M可为素数。
 可从任意频率0开始，对x(n)做窄带高分辨率的谱分析；  谱分析路径可以是螺旋形的。W0>1, k,螺线内缩 W0<1, k,螺线外伸  复抽样点：zk =A0W0-k ej(0+k0), k=0,…,M-1. A0,W0, 0 ,0 任意实数  DFT是CZT的特例： A=1,M=N, W=e－j2/N。 SHNU.信息机电学院

44 4.5 Chirp-ZT (CZT) 4/9 四、实现：  N点x(n)  M点CZT线性卷积圆周卷积 FFT快速计算
 X(zk)= x(n)A-n Wkn , k=0,…M-1 = W k2/2 [x(n)A-nWn2/2 ]W-(k-n)2/2 =W k2/2 g(n)h(k-n) nk=[n2+k2-(k-n)2]/2 g(n),n=[0,N-1] SHNU.信息机电学院

45 4.5 Chirp-ZT (CZT) 5/9 具体：  选 LN+M-1, L= 2v ,为2的整数次幂,
 构造L点序列h(n): h(n)= W-n2/2 , 0nM-1 0 , MnL-N W-(L-n)2/2, L-N+1nL-1 L L点,主值区间 N+M-1 W-n2/2非因果,截[-(N-1), M-1]段; 以L为周期延拓；取主值=h(n) 取零值 n W-n2/2 图4.11a CZT运算结构中h(n)的构造 SHNU.信息机电学院

46 4.5 Chirp-ZT (CZT) 6/9  g(n)后补零 L点序列L点DFT: G(r), r=0,…,L-1
 h(n)  L点DFT: H(r), r=0,…,L-1  频域相乘： Q(r)=H(r)G(r) , r=0,…,L-1  IFFT: h(n) g(n)=q(n)=(1/L) H(r)G(r)ej2r n/L 取前M个值：X(zk)=W k2/2q(k), k=0,…,M-1 L 取前M点的值.用于计算x(n)的M点“DFT”－CZT n g(n)=x(n)A-nWn2/2 图4.11b CZT运算中g(n)的构造，L点圆周卷积示意。 SHNU.信息机电学院

47 4.5 Chirp-ZT (CZT) 7/9 实现结构示意：  X(zk)= x(n)A-n Wkn , k=0,…M-1
= W k2/2 [x(n)A-nWn2/2 ]W-(k-n)2/2 =W k2/2 g(n)h(k-n) nk=[n2+k2-(k-n)2]/2 g(n),n=[0,N-1] q(n) n无限制 图4.11c CZT运算结构 SHNU.信息机电学院

48 4.5 Chirp-ZT (CZT) 8/9 五、快速算法的发展： 提高频率分辨率：ZFFT_放大镜式FFT,仪器中常用.
 x(n):取样间隔T, fs=1/T  N点FFT f=fs/N。 欲提高fd 附近的谱分辨率， 复调制x(n) e－j2nfdT+LPF, 输出频率fdfB/2范围的信号分量。 频率分辨率。 带宽为B 取样频率fsM=fs/A 图4.12 ZFFT系统(测量仪器中常用) SHNU.信息机电学院

49 4.5 Chirp-ZT (CZT) 9/9 |Y(ej)| |G(ej)| 重抽样频率fsM=fs/A,
|X(ej)| d s/2  |Y(ej)| -B/2 B/  复调制： 频点d左移到零频 LPF: 频带缩小A=s/B倍。dB/2范围的频率分量 |G(ej)| -B/2 B/  重抽样频率fsM=fs/A, 无频率混叠 同样N点FFT: f=fs/(AN) ,  频率分辨率A倍。 |R(k)| s/2  图4.13 ZFFT算法过程中频谱图 SHNU.信息机电学院

50 4.6 Discrete Hartley Transform 1/6
实序列x(n)的N点DFT X(k)具有共轭对称性， X(N-k)=X*(k)，k＝0,1,…,N-1。 只要知道其前N/2个X(k)， 后N/2个X(k)可用对称性求出。  计算X(k)前N/2个X(k)复值，等效于：求N个实数。  DHT就是对N点实序列进行变换，得到N个实数。 这N个实数与该序列的N/2个X(k)有简单的关系。 SHNU.信息机电学院

51 4.6 Discrete Hartley Transform 2/6
Definition to DHT 设x(n)，n＝0,1,…,N-1为实序列。  DHT定义： XH(k)=DHT[x(n)]= x(n)cas( kn), k=0,1,…,N-1 cas＝cos+sin x(n)=IDHT[XH(k)]=(1/N) XH(k)cas( kn), n=0,1,…,N-1  实数域  实数域 SHNU.信息机电学院

52 4.6 Discrete Hartley Transform 3/6
Relationships between DHT and DFT 1. 将XH(k)表示为奇对称和偶对称分量之和： XH(k)=XHe(k)＋XHo(k) XHe(k)=[XH(k)+ XH(N－k)]/2, XHo(k)=[XH(k)－XH(N－k)]/2, 2. 由DHT的定义： XHe(k)= x(n)cos( kn)； XHo(k)= x(n)sin( kn) 3. x(n)的DFT: X(k)=XHe(k)－j XHo(k) X(k)=[XH(k)+XH(N-k)]/2 - j[XH(k)-XH(N-k)]/2 SHNU.信息机电学院

53 4.6 Discrete Hartley Transform 4/6
Properties of DHT 设x(n)  XH(k)， y(n)  YH(k)， 1. 线性性： a x(n)＋b y(n)  a XH(k) ＋b YH(k) 2. 逆序列 x(N-n)的DHT: x(N-n)  XH(N-k) 且XH(N-k)= x(n)[ cos( kn)－sin( kn)] XH(N)=XH(0) SHNU.信息机电学院

54 4.6 Discrete Hartley Transform 5/6
3. 循环移位性质 x((n n0)NRN(n)  XH(k)cos( kn0) XH(N-k)sin( kn0) 4. 奇偶性： DHT序列的奇偶性和原序列的奇偶性一致。 5. 循环卷积定理：  x(n)*y(n)  YH(k)XHe(k) +YH(N-k)XHo(k) ＝ XH(k)YHe(k) +XH(N-k)YHo(k)  当x(n)是偶对称序列，  XH(k)=XHe(k)+jXHo(k)是偶对称的. XHo(k)＝0 x(n)*y(n)  YH(k)XH(k) SHNU.信息机电学院

55 4.6 Discrete Hartley Transform 6/6
4.6 数字信号处理的软、硬件实现 软件：C程序, MatLab: m文件. explain mfile： 硬件：相关课程中更详细介绍。 eg3_5 SHNU.信息机电学院

56 第四章小结: 1. N=2M点DFT, FFT的计算量: C=N2, CFFT=(N/2)log2N 2. FFT: 通过将大点数的DFT分解为小(2)点数的DFT. 3. Lth级蝶形运算节：输入(出)点的距离B=2L-1. 一旋转因子对应间隔为2L点的2M-L个蝶形. 4. FFT I/O数据的译序(倒位序,原位运算) DIT-FFT输入逆序,输出自然顺序. 5. 基2（Radix-2）DIT-FFT原理，23分解的流图. 6. 2次FFT的运算结果,比例于IFFT. 7. CZT可分析频谱的精细结构,可快速检测极点频率. 9. 长序列线性卷积、线性相关常用分段圆周卷积实现.主要有重叠相加、重叠保留。 SHNU.信息机电学院

57 作业： P127 4－1, 4－2， 4－3, 长序列的卷积补充习题： 4-5 设数字系统的单位取样相应h=[1,2,-1]。 试用重叠相加法，通过4点圆周卷积，求输入信号x(n)=[1,1,2,1,2,2,1,1,1]时系统的输出y(n)。 并用线性卷积结果进行验证。 4-6 设数字系统的单位取样相应h=[1,2,-1,-1]。 试用重叠保留法，通过6点圆周卷积，求输入信号x(n)=[1,1,2,1,2,2,1,1,0,1]时，系统的输出y(n)。并用线性卷积结果进行验证。 cc.shnu.edu.cn /课程习题/数字信号处理补充习题 .doc cc.shnu.edu.cn /课程资料/通信 数字信号处理教案2012秋 /LiDSP_04FFT SHNU.信息机电学院

58 Introduction to MatLab Introduction to Complex Exponentials
SHNU.信息机电学院

59 END & THANK YOU！ SHNU.信息机电学院