从连续短时距傅里叶变化的定义出发
令 ,则上述式子时域可从连续转为离散
若当
上式可改写为
直接运算
限制条件
(1)要满足Nyquist criterion
-
- 的带宽为 。而 的带宽则为 , 的带宽也为
- 因为在时域相乘相当于在频域做卷积,因此 的带宽为 (通常 会远大于 ,所以主要影响带宽的是 )
推导
-
- 变换到离散形式( ),其中
- ,由于无限大的上下限实务上做不到,所以尝试变成有限大的上下限。
- 假设 for
-
- 对于缩放的加伯变换,
时间复杂度
-
- 假设t-axis有T个采样点,f-axis有F个采样点,则我们总共要对TF个点做 次的运算,因此可得复杂度为
优缺点
- 优点:简单及有弹性(因为限制少)
- 缺点:复杂度较高
快速傅里叶变换
限制条件
(1)要满足Nyquist criterion
-
(2) (N可为任意整数)
(3) (做N点傅里叶变换,输入必要<=N)
推导
标准的离散傅里叶变换式子为
由直接运算得知如下公式
因此为了让上式符合离散傅里叶变换的上下界,令 代入上式即可得
其中
运算步骤
假设
-
步骤一:计算
步骤二:
步骤三:决定
步骤四:
步骤五:变换 成
步骤六:设 ,并回到步骤三,直到
借由采样定理可得知
假设 及 ,则经由 可得
- 及 ,则经由 可得
步骤一:
步骤二:
步骤三:计算
步骤四:利用求得的 计算快速傅里叶变换
步骤五:变换 到
-
- 注:若是于程式中执行,要注意m可能为负数,所以需要利用到周期性性质
-
- 因此可将上式改为 ,其中 代表取m除以N的余数
步骤六:设定 ,回到步骤三直到
时间复杂度
利用FFT计算 ,其中每次FFT的时间复杂度为
总时间复杂度为
优缺点
优点:与直接运算相比,复杂度较低
缺点:较多限制,包括
使用快速傅里叶变换加上递回关系式
限制条件
(1)要满足Nyquist criterion
-
(2)
(3)
(4)需为方形窗函数的短时距傅里叶变换
推导
因为是方形窗函数
,因此原式可由此关系变成以下式子
而由此可看出n和n-1有递回关系,如下
(1)以FFT计算
- 其中
(2)利用递回关系式计算算
- 则
时间复杂度
(1)FFT计算一次
- 时间复杂度:
(2)利用递回关系,计算 时的数值,因此共会执行T-1次递回,如下式
-
- 每次递回都要计算 及 两个乘法(相当于2F的复杂度)
- 时间复杂度:
总时间复杂度
优缺点
优点:四种运算中,最低的复杂度
缺点:
- 只适用于方形窗函数的短时傅里叶变换
- 由于递回的关系,会有累加误差。所以只要当中有小错误,误差会累积到最后,造成无可预期的错误
- 不能用在不平衡的采样点
使用Chirp-Z 变换
限制条件
(1)要满足Nyquist criterion
-
推导
令
即可由直接运算的式子导出Chirp_Z变换的式子,如下所示
运算步骤
Step1:
Step2:
Step3:
时间复杂度
当n为定值时
(1)假设 相乘时间复杂度为2Q+1
(2)令 ,则 convolution时间复杂度为
(3) 相乘时间复杂度为 F
因此,总时间复杂度为
虽然此实现方法和使用FFT计算的时间复杂度相同,但因为convolution相当于做三次FFT,因此实际操作时运算时间约为使用FFT计算的2~3倍
优缺点
优点:只有一项限制:
缺点:与前四种相比,复杂度是中间的。
Unbalanced Sampling for STFT and WDF
将直接法和快速傅里叶变换方法做修正
1.直接法
修正后 :
其中, ,
假设 for ,则上下限可借由以下推导而修正
则上限可以写成 ,下限则以此类推
注: (输入信号的采样间隔)
(在t轴上的输出信号的采样间隔)
然而, 是整数会是比较好的。
则经由上述公式可求得S=441,代表经由unbalanced sampling,我们跟原本 相比可减少441倍的采样点。
时间复杂度
由于t轴的采样点少了S倍,因此跟原本的直接运算复杂度相比,只要把 即可,如下:
复杂度:
2.快速傅里叶变换
限制条件
(1)
(2) : ( 只要是整数的倒数即可)
(3) , 的带宽是
i.e. ,当
过程
令
for
for
修正后:
运算步骤
假设
步骤一:计算
步骤二:
步骤三:决定
步骤四:
步骤五:变换
步骤六:设定 及返回步骤三,直到
复杂度
Non-Uniform
(1) 先用比较大的
(2) 如果发现 和 之间有很大的差异,则在 , 之间选用比较小的采样区间
( , 和 皆为整数)
再用Unbalanced Sampling for STFT and WDF 中修正后的快速傅里叶变换方法算出 ,
(3) 以此类推,如果 的差距还是太大,则再选用更小的采样间隔
( , 和 皆为整数)
若有一音乐信号总共有1.6秒,
- 选择 ,则共有 点
- 选择 ,则共有 点
- t随时间不同有不同的选择,如下
- ,共29点
- 可以这样做的原因为:有些音乐信号在和弦与和弦中间几乎没有变化,因此可以挑选较大的 采样;和弦在变换时,频率会变化的较剧烈,因此变换和弦是需要用较多的采样点。借由此种non-uniform的采样,可以让我们大幅减少运算量,从最一开始的 可看出我们的运算量大幅降低。