重叠保留法 将序列Xn)分解成长度为N的序列块xn(n), 其中有K-1个取样与相邻序列重叠,第一个 序列块在开头补K-1个零 对h(n)补零,使长度变为N 用长度为N的DF计算每个序列块的圆周卷 积。 拼接构成输出信号
重叠保留法 ◼ 将序列x(n)分解成长度为N的序列块xm(n)， 其中有K-1个取样与相邻序列重叠，第一个 序列块在开头补K-1个零； ◼ 对h(n)补零，使长度变为N； ◼ 用长度为N的DFT计算每个序列块的圆周卷 积。 ◼ 拼接构成输出信号
两种方法的区别 在重叠相加法中,计算长度N+K1的DF, 并将结果相加 」在重叠保留法中,只需计算长度N的DFT, 并通过舍弃、保留手段拼接构成最后输出 结果 DET FFT
两种方法的区别 ◼ 在重叠相加法中，计算长度N+K-1的DFT， 并将结果相加； ◼ 在重叠保留法中，只需计算长度N的DFT， 并通过舍弃、保留手段拼接构成最后输出 结果。 DFT FFT
FF算法 DF「运算归结为一系列的乘加运算,谱的 每一个频率点都要对N个乘法项求和,对N 个谱点总共作Ⅳ次乘法,计算量大,不利 于实时处理。 1965年, Cooley和而key提是出快速付里叶 变换(F「),极大地提高了运算速度
FFT算法 ◼ DFT运算归结为一系列的乘加运算，谱的 每一个频率点都要对N个乘法项求和，对N 个谱点总共作N2次乘法，计算量大，不利 于实时处理。 ◼ 1965年，Cooley和Tukey提出快速付里叶 变换（FFT），极大地提高了运算速度
运算量对比 →bog2N基2FT运算近 似的复乘次数 例:1024个采样点 直接DF:需1048576次乘法 FFT:仅需5120次乘法
运算量对比 例：1024个采样点 ◼ 直接DFT：需1048576次乘法； ◼ FFT：仅需5120次乘法。 N N N 2 2 log 2 → 基-2 FFT运算近 似的复乘次数