# 短時距傅立葉變換

## 與傅立葉轉換在概念上的區別

${\displaystyle x(t)={\begin{cases}\cos(440\pi t);&t<0.5\\\cos(660\pi t);&0.5\leq t<1\\\cos(524\pi t);&t\geq 1\end{cases}}}$

 傅立葉轉換後, 橫軸為頻率(赫茲) 短時距傅立葉轉換, 橫軸為時間(秒)，縱軸為頻率(赫茲)

## 定義

### 連續短時傅立葉轉換

${\displaystyle X(t,f)=\int _{-\infty }^{\infty }w(t-\tau )x(\tau )e^{-j2\pi f\tau }\,d\tau }$

${\displaystyle X(t,\omega )=\int _{-\infty }^{\infty }w(t-\tau )x(\tau )e^{-j\omega \tau }\,d\tau }$

### 離散短時傅立葉轉換

${\displaystyle \mathbf {STFT} \{x[n]\}(m,\omega )\equiv X(m,\omega )=\sum _{n=-\infty }^{\infty }x[n]w[n-m]e^{-j\omega n}}$

### 反短時距傅立葉轉換

${\displaystyle \int _{-\infty }^{\infty }w(\tau )\,d\tau =1.}$

${\displaystyle \int _{-\infty }^{\infty }w(t-\tau )\,d\tau =1\quad \forall \ t}$

${\displaystyle x(t)=x(t)\int _{-\infty }^{\infty }w(t-\tau )\,d\tau =\int _{-\infty }^{\infty }x(t)w(t-\tau )\,d\tau .}$

${\displaystyle X(\omega )=\int _{-\infty }^{\infty }x(t)e^{-j\omega t}\,dt.}$

${\displaystyle x(t)}$ 進行上述的替換：

${\displaystyle X(\omega )=\int _{-\infty }^{\infty }\left[\int _{-\infty }^{\infty }x(t)w(t-\tau )\,d\tau \right]\,e^{-j\omega t}\,dt}$
${\displaystyle =\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }x(t)w(t-\tau )\,e^{-j\omega t}\,d\tau \,dt.}$

${\displaystyle X(\omega )=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }x(t)w(t-\tau )\,e^{-j\omega t}\,dt\,d\tau }$
${\displaystyle =\int _{-\infty }^{\infty }\left[\int _{-\infty }^{\infty }x(t)w(t-\tau )\,e^{-j\omega t}\,dt\right]\,d\tau }$
${\displaystyle =\int _{-\infty }^{\infty }X(\tau ,\omega )\,d\tau .}$

${\displaystyle x(t)={\frac {1}{2\pi }}\int _{-\infty }^{\infty }X(\omega )e^{+j\omega t}\,d\omega ,}$

${\displaystyle x(t)={\frac {1}{2\pi }}\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }X(\tau ,\omega )e^{+j\omega t}\,d\tau \,d\omega .}$

${\displaystyle x(t)=\int _{-\infty }^{\infty }\left[{\frac {1}{2\pi }}\int _{-\infty }^{\infty }X(\tau ,\omega )e^{+j\omega t}\,d\omega \right]\,d\tau .}$

${\displaystyle x(t)w(t-\tau )={\frac {1}{2\pi }}\int _{-\infty }^{\infty }X(\tau ,\omega )e^{+j\omega t}\,d\omega .}$

${\displaystyle x(t)=w(t_{1}-t)^{-1}\int _{-\infty }^{\infty }X(t_{1},f)e^{j2\pi ft}\,df;\ \ w(t_{1}-t)\neq 0}$

${\displaystyle x(t)={\frac {1}{2\pi }}w^{-1}(t_{1}-t)\int \limits _{-\infty }^{\infty }X(t_{1},w)e^{jwt}dw}$

### 窗函數

1. ${\displaystyle w(t)=w(-t)\,}$ ，即為偶函數。
2. ${\displaystyle max(w(t))=w(0)\,}$ ，即窗函數的中央通常是最大值的位置。
3. ${\displaystyle w(t_{1})\geq w(t_{2}),|t_{2}|\geq |t_{1}|}$ ，即窗函數的值由中央開始向兩側單調遞減。
4. ${\displaystyle w(t)\cong 0,|t|\to \infty }$ ，即窗函數的值向兩側遞減為零。

## 優缺點

• 優點：比起傅立葉轉換更能觀察出信號瞬時頻率的資訊。
• 缺點：計算複雜度高

## 方形窗函數的短時距傅立葉轉換

### 概念

${\displaystyle X(t,f)=\int _{t-B}^{t+B}x(\tau )e^{-j2\pi f\tau }\,d\tau }$

${\displaystyle x(t)=\int _{-\infty }^{\infty }X(t_{1},f)e^{j2\pi ft}\,df;t-B

### 特性

• 積分特性
${\displaystyle \int _{-\infty }^{\infty }X(t,f)\,df=\int _{t-B}^{t+B}x(\tau )\int _{-\infty }^{\infty }e^{-j2\pi f\tau }\,df\,d\tau ={\begin{cases}\ x(0);&|t|\leq B\\\ 0;&|t|>B\end{cases}}}$
• 位移特性(時間軸方向的移動)
${\displaystyle \int _{t-B}^{t+B}x(\tau +\tau _{0})e^{-j2\pi f\tau }\,d\tau =X(t+\tau _{0},f)e^{j2\pi f\tau _{0}}}$
• 調變特性(頻率軸方向的移動)
${\displaystyle \int _{t-B}^{t+B}\left(x(\tau )e^{j2\pi f_{0}\tau }\right)e^{-j2\pi f\tau }\,d\tau =X(t,f-f_{0})}$
• 線性特性

• 能量積分特性
${\displaystyle \int _{-\infty }^{\infty }|X(t,f)|^{2}\,df=\int _{t-B}^{t+B}|x(\tau )|^{2}\,d\tau }$
${\displaystyle \int _{-\infty }^{\infty }X(t,f)Y^{*}(t,f)\,df=\int _{t-B}^{t+B}x(\tau )y^{*}(\tau )\,d\tau }$
• 特殊信號
1. 當${\displaystyle x(t)=\delta (t)\,}$
${\displaystyle X(t,f)={\begin{cases}\ 1;&|t|\leq B\\\ 0;&|t|>B\end{cases}}}$
2. 當${\displaystyle x(t)=1\,}$
${\displaystyle X(t,f)=2Bsinc(2Bf)e^{-j2\pi ft}\,}$

### 方形窗函數寬度${\displaystyle (B)}$ 的選取

• 由上述特性中的特殊信號${\displaystyle x(t)=\delta (t)}$ 來分析，信號只有在${\displaystyle t=0}$ 的時候有值；若短時距傅立葉轉換是理想的話，${\displaystyle X(t,f)}$ 應該只有在${\displaystyle t=0}$ 的時候有能量。但由上面的特性可發現，能量會出現在${\displaystyle {\begin{smallmatrix}|t|\leq B\end{smallmatrix}}}$ 中間。因此，若我們取較小的${\displaystyle B}$ ，則可使結果趨近理想。
• 接著我們來分析${\displaystyle x(t)=1}$ ，信號因為沒有改變，應該為DC。若短時距傅立葉轉換是理想的話，${\displaystyle X(t,f)}$ 應該只有在${\displaystyle f=0}$ 的時候有能量。但由上面的特性可發現，能量會沿著頻率軸呈現sinc函數。若我們取較大的${\displaystyle B}$ ，可使sinc函數沿著頻率軸變窄，使得結果趨近理想。
• 綜合以上說明，若我們使用較大的方形窗函數寬度${\displaystyle (B)}$ ，則${\displaystyle X(t,f)}$ 時間軸的解析度會下降；頻率軸的解析度上升。若使用較小的${\displaystyle B}$ ，則${\displaystyle X(t,f)}$ 時間軸的解析度會上升；頻率軸的解析度下降。我們以下面做為例子說明：
${\displaystyle x(t)={\begin{cases}\cos(2\pi t);&t<10\\\cos(6\pi t);&10\leq t<20\\\cos(4\pi t);&t\geq 20\end{cases}}}$

### 優缺點

• 優點：方形窗函數的短時距傅立葉轉換有許多可應用的數學特性，在數位的應用上所需的計算時間較少。
• 缺點：時頻分析的表現較差

## 頻譜(Spectrogram)

Spectrogram即短時傅立葉轉換後結果的絕對值平方，兩者本質上是相同的，在文獻上也常出現spectrogram這個名詞。

${\displaystyle SP_{x}(t,f)=|X(t,f)|^{2}=|\int _{-\infty }^{\infty }w(t-\tau )x(\tau )e^{-j2\pi f\tau }\,d\tau |^{2}}$

## 短時距傅立葉變換實現方法

${\displaystyle {X}\left({t,f}\right)=\int _{-\infty }^{\infty }{w\left({t-\tau }\right)\cdot }{x}\left({\tau }\right)\,{e^{-j2\pi \,f\tau }}\cdot d\tau }$


${\displaystyle t=n\Delta _{t},f=m\Delta _{f},\tau =p\Delta _{t}}$  ，則上述式子時域可從連續轉為離散

${\displaystyle {X}\left({n{\Delta _{t}},m{\Delta _{f}}}\right)=\sum \limits _{p=-\infty }^{\infty }{w\left({(n-p){\Delta _{t}}}\right){x}\left({p{\Delta _{t}}}\right)}{e^{-j2\pi \,mp{\Delta _{t}}{\Delta _{f}}}}{\Delta _{t}}}$

${\displaystyle {X}\left({n{\Delta _{t}},m{\Delta _{f}}}\right)=\sum \limits _{p=n-Q}^{n+Q}{w\left({(n-p){\Delta _{t}}}\right){x}\left({p{\Delta _{t}}}\right)}{e^{-j2\pi \,mp{\Delta _{t}}{\Delta _{f}}}}{\Delta _{t}}}$


### 直接運算

#### 限制條件

(1)要滿足Nyquist criterion

${\displaystyle {\Delta _{t}}<{\frac {1}{2\Omega }}\qquad {\Omega }={{\Omega _{x}}+{\Omega _{w}}}}$
${\displaystyle x(\tau )}$ 的頻寬為${\displaystyle \Omega _{x}}$ 。而${\displaystyle w(\tau )}$ 的頻寬則為${\displaystyle \Omega _{w}}$ ${\displaystyle w(t-\tau )}$ 的頻寬也為${\displaystyle \Omega _{w}}$

#### 推導

${\displaystyle X(t,f)=\int _{-\infty }^{\infty }w(t-\tau )x(\tau )e^{-j2\pi f\tau }d\tau }$

${\displaystyle X(n\Delta _{t},m\Delta _{f})=\sum _{p=-\infty }^{\infty }w((n-p)\Delta _{t})x(p\Delta _{t})e^{-j2\pi pm\Delta _{t}\Delta _{f}}\Delta _{t}}$ ，由於無限大的上下限實務上做不到，所以嘗試變成有限大的上下限。

${\displaystyle X(n\Delta _{t},m\Delta _{f})=\sum _{p=n-Q}^{n+Q}w((n-p)\Delta _{t})x(p\Delta _{t})e^{-j2\pi pm\Delta _{t}\Delta _{f}}\Delta _{t}}$
• 對於縮放的加伯轉換${\displaystyle Q={\frac {1.9143}{{\sqrt {\sigma }}\Delta t}}}$

#### 時間複雜度

${\displaystyle TF(2Q+1)\to O(TFQ)}$

### 快速傅立葉變換

#### 限制條件

(1)要滿足Nyquist criterion

${\displaystyle {\Delta _{t}}<{\frac {1}{2\Omega }}\qquad {\Omega }={{\Omega _{x}}+{\Omega _{w}}}}$

(2)${\displaystyle {\Delta _{t}}{\Delta _{f}}={\textstyle {1 \over {N}}}}$  (N可為任意整數)

(3) ${\displaystyle N\geq 2Q+1}$  (做N點傅立葉轉換，輸入必要<=N)

#### 推導

${\displaystyle Y[m]=\sum \limits _{n=0}^{N-1}y[n]e^{-j{\frac {2\pi mn}{N}}}}$

${\displaystyle {X}\left({n{\Delta _{t}},m{\Delta _{f}}}\right)=\sum \limits _{p=n-Q}^{n+Q}{w\left({(n-p){\Delta _{t}}}\right){x}\left({p{\Delta _{t}}}\right)}{e^{-j2\pi \,mp{\Delta _{t}}{\Delta _{f}}}}{\Delta _{t}}}$

${\displaystyle {X}\left({n{\Delta _{t}},m{\Delta _{f}}}\right)={\Delta _{t}}{e^{j{\textstyle {{2\pi \,(Q-n)m} \over N}}}}\sum \limits _{q=0}^{N-1}{x_{1}\left({q}\right){e^{-j{\textstyle {{2\pi \,qm} \over N}}}}}}$

#### 運算步驟

${\displaystyle \,f=m_{0}\Delta _{f},(m_{0}+1)\Delta _{f},\cdots \cdots ,(m_{0}+F-1)\Delta _{f}}$

• 範例

${\displaystyle {\begin{cases}x(t)=\cos {(2\pi t)},&{\mbox{when }}t<10\\x(t)=\cos {(6\pi t)},&{\mbox{when }}10\leq t<20\\x(t)=\cos {(4\pi t)},&{\mbox{when }}t\geq 20\\\end{cases}}}$

${\displaystyle \;t=0\sim 30}$ ${\displaystyle \Delta _{t}=0.1}$ ，則經由${\displaystyle t=n\Delta _{t}}$ 可得${\displaystyle n=0\sim 300}$

${\displaystyle X(n\Delta _{t},m\Delta _{f})=X_{1}[m]\Delta _{t}e^{j{\frac {2\pi (Q-n)m}{N}}}}$
• 註：若是於程式中執行，要注意m可能為負數，所以需要利用到週期性性質${\displaystyle X_{1}[m]=X_{1}[m+N]}$
${\displaystyle X_{1}[-50]=X_{1}[50],X_{1}[-49]=X_{1}[51],\cdots \cdots ,X_{1}[-1]=X_{1}[99]}$

### 使用快速傅立葉變換加上遞迴關係式

#### 限制條件

(1)要滿足Nyquist criterion

${\displaystyle {\Delta _{t}}\leq {\frac {1}{2\Omega }}\qquad {\Omega }={{\Omega _{x}}+{\Omega _{w}}}}$

(2)${\displaystyle {\Delta _{t}}{\Delta _{f}}={\textstyle {1 \over {N}}}}$

(3)${\displaystyle N\geq 2Q+1}$

(4)需為方形窗函數的短時距傅立葉轉換

#### 推導

${\displaystyle {X}\left({n{\Delta _{t}},m{\Delta _{f}}}\right)=\sum \limits _{p=n-Q}^{n+Q}{{x}\left({p{\Delta _{t}}}\right)}{{w}\left((n-p){\Delta _{t}}\right)}{e^{-j2\pi \,mp{\Delta _{t}}{\Delta _{f}}}}{\Delta _{t}}\to {X}\left({n{\Delta _{t}},m{\Delta _{f}}}\right)=\sum \limits _{p=n-Q}^{n+Q}{{x}\left({p{\Delta _{t}}}\right)}{e^{-j2\pi \,mp{\Delta _{t}}{\Delta _{f}}}}{\Delta _{t}}}$

${\displaystyle {X}\left({(n-1){\Delta _{t}},m{\Delta _{f}}}\right)=\sum \limits _{p=n-1-Q}^{n-1+Q}{{x}\left({p{\Delta _{t}}}\right)}{e^{-j2\pi \,mp{\Delta _{t}}{\Delta _{f}}}}{\Delta _{t}}={X}\left({n{\Delta _{t}},m{\Delta _{f}}}\right)+x((n-Q-1)\Delta _{t})-x((n+Q+1)\Delta _{t})}$

(1)以FFT計算${\displaystyle {X}\left({{n_{0}}{\Delta _{t}},m{\Delta _{f}}}\right)={\Delta _{t}}{e^{j{\textstyle {{2\pi \,(Q-n_{0})m} \over N}}}}\sum \limits _{q=0}^{N-1}{x_{1}\left({q}\right){e^{-j{\textstyle {{2\pi \,qm} \over N}}}}}\qquad {n_{0}}=min(n)}$

(2)利用遞迴關係式計算算${\displaystyle {X}\left({{n}{\Delta _{t}},m{\Delta _{f}}}\right),\qquad n={n_{0}}+1\backsim max(n)}$

${\displaystyle {X}\left({{n_{0}}{\Delta _{t}},m{\Delta _{f}}}\right)={X}\left({(n-1){\Delta _{t}},m{\Delta _{f}}}\right)-{x}\left((n-Q-1){\Delta _{t}}\right){e^{-j{\textstyle {{2\pi \,(n-Q-1)m} \over N}}}}{\Delta _{t}}+{x}\left((n+Q){\Delta _{t}}\right){e^{-j{\textstyle {{2\pi \,(n+Q)m} \over N}}}}{\Delta _{t}}}$

#### 時間複雜度

(1)FFT計算一次 ${\displaystyle {X}\left({{n_{0}}{\Delta _{t}},m{\Delta _{f}}}\right)={\Delta _{t}}{e^{j{\textstyle {{2\pi \,(Q-n_{0})m} \over N}}}}\sum \limits _{q=0}^{N-1}{x_{1}\left({q}\right){e^{-j{\textstyle {{2\pi \,qm} \over N}}}}}\qquad {n_{0}}=min(n)}$

• 時間複雜度：${\displaystyle O(N\log _{2}N)}$

(2)利用遞迴關係，計算${\displaystyle n=n_{0}+1}$ 時的數值，因此共會執行T-1次遞迴，如下式

${\displaystyle {X}\left({{n_{0}}{\Delta _{t}},m{\Delta _{f}}}\right)={X}\left({(n-1){\Delta _{t}},m{\Delta _{f}}}\right)-{x}\left((n-Q-1){\Delta _{t}}\right){e^{-j{\textstyle {{2\pi \,(n-Q-1)m} \over N}}}}{\Delta _{t}}+{x}\left((n+Q){\Delta _{t}}\right){e^{-j{\textstyle {{2\pi \,(n+Q)m} \over N}}}}{\Delta _{t}}}$

• 時間複雜度：${\displaystyle 2F(T+1)\to O(TF)}$

#### 優缺點

1. 只適用於方形窗函數的短時傅立葉轉換
2. 由於遞迴的關係，會有累加誤差。所以只要當中有小錯誤，誤差會累積到最後，造成無可預期的錯誤
3. 不能用在不平衡的取樣點

### 使用Chirp-Z 轉換

#### 限制條件

(1)要滿足Nyquist criterion

${\displaystyle {\Delta _{t}}\leq {\frac {1}{2\Omega }}\qquad {\Omega }={{\Omega _{x}}+{\Omega _{w}}}}$

#### 推導

${\displaystyle exp(-j2\pi \,mp{\Delta _{t}}{\Delta _{f}})=exp(-j\pi \,p^{2}{\Delta _{t}}{\Delta _{f}})exp(j\pi \,{(p-m)}^{2}{\Delta _{t}}{\Delta _{f}})exp(-j\pi \,m^{2}{\Delta _{t}}{\Delta _{f}})}$

${\displaystyle {X}\left({n{\Delta _{t}},m{\Delta _{f}}}\right)={\Delta _{t}}\sum \limits _{p=n-Q}^{n+Q}{w\left({(n-p){\Delta _{t}}}\right){x}\left({p{\Delta _{t}}}\right)}{e^{-j2\pi \,mp{\Delta _{t}}{\Delta _{f}}}}\to {X}\left({n{\Delta _{t}},m{\Delta _{f}}}\right)={\Delta _{t}}{e^{-j\pi \,m^{2}{\Delta _{t}}{\Delta _{f}}}}\sum \limits _{p=n-Q}^{n+Q}{w\left({(n-p){\Delta _{t}}}\right){x}\left({p{\Delta _{t}}}\right)}{e^{-j\pi \,p^{2}{\Delta _{t}}{\Delta _{f}}}}{e^{j\pi \,{(p-m)}^{2}{\Delta _{t}}{\Delta _{f}}}}}$

#### 運算步驟

Step1:${\displaystyle x_{1}[p]=w((n-p)\Delta _{t})x(p\Delta _{t})e^{-j\pi p^{2}\Delta _{t}\Delta _{f}}}$  ${\displaystyle \quad \quad n-Q\leq p\leq n+Q}$

Step2:${\displaystyle X_{2}[n,m]=\sum _{p=n-Q}^{n+Q}x_{1}[p]c[m-p]\quad \quad c[m]=e^{j\pi m^{2}\Delta _{t}\Delta _{f}}}$

Step3:${\displaystyle X(n\Delta _{t},m\Delta _{f})=\Delta _{t}e^{-j\pi m^{2}\Delta _{t}\Delta _{f}}X_{2}[m,n]}$

#### 時間複雜度

(1)假設${\displaystyle x_{1}[p]=w((n-p)\Delta _{t})x(p\Delta _{t})e^{-j\pi p^{2}\Delta _{t}\Delta _{f}}\to }$  相乘時間複雜度為2Q+1

(2)令${\displaystyle c[m]=e^{j\pi m^{2}\Delta _{t}\Delta _{f}}}$ ，則${\displaystyle \sum \limits _{p=n-Q}^{n+Q}x_{1}[p]c[m-p]\to }$  convolution時間複雜度為 ${\displaystyle 3N{\log _{2}}N}$

(3)${\displaystyle {\Delta _{t}}{e^{-j\pi \,m^{2}{\Delta _{t}}{\Delta _{f}}}}\sum \limits _{p=n-Q}^{n+Q}{w\left({(n-p){\Delta _{t}}}\right){x}\left({p{\Delta _{t}}}\right)}{e^{-j\pi \,p^{2}{\Delta _{t}}{\Delta _{f}}}}{e^{j\pi \,{(p-m)}^{2}{\Delta _{t}}{\Delta _{f}}}}\to }$ 相乘時間複雜度為 F

### Unbalanced Sampling for STFT and WDF

#### 1.直接法

${\displaystyle X(t,f)=\int _{-\infty }^{\infty }w(t-\tau )x(\tau )e^{-j2\pi f\tau }d\tau }$

${\displaystyle \int _{t+B}^{t-B}\to \int _{n\Delta _{t}+Q\Delta _{\tau }}^{n\Delta _{t}-Q\Delta _{\tau }}}$  則上限可以寫成${\displaystyle n\Delta _{t}+Q\Delta _{\tau }==nS\Delta _{\tau }+Q\Delta _{\tau }=\Delta _{\tau }(nS+Q)}$ ，下限則以此類推

${\displaystyle \Delta _{t}}$ (在t軸上的輸出訊號的取樣間隔)

• 假設一聲音訊號：

${\displaystyle {\begin{cases}\Delta _{\tau }={\frac {1}{44100}}\\\Delta _{t}={\frac {1}{100}}\end{cases}}}$  則經由上述公式可求得S=441，代表經由unbalanced sampling，我們跟原本${\displaystyle \Delta _{t}=\Delta _{\tau }={\frac {1}{44100}}}$ 相比可減少441倍的取樣點。

#### 2.快速傅立葉轉換

##### 限制條件

(1) ${\displaystyle \Delta _{\tau }\Delta _{f}={\frac {1}{N}}}$

(2) ${\displaystyle N={\frac {1}{\Delta _{\tau }\Delta _{f}}}>2Q+1}$  : (${\displaystyle \Delta _{\tau }\Delta _{f}}$ 只要是整數的倒數即可)

(3) ${\displaystyle \Delta _{\tau }<{\frac {1}{2\Omega }}}$ ${\displaystyle w(\tau -t)x(\tau )}$ 的頻寬是 ${\displaystyle \Omega }$

i.e. ${\displaystyle |FT\{w(\tau -t)x(\tau )\}|=|X(t,f)|\approx 0}$  ，當 ${\displaystyle |f|>\Omega }$

##### 過程

${\displaystyle X(n\Delta _{t},m\Delta _{f})=\sum _{p=nS-Q}^{nS+Q}w((nS-p)\Delta _{\tau })x(p\Delta _{\tau })e^{-j{\tfrac {2\pi pm}{N}}}\Delta _{\tau }}$

${\displaystyle q=p-(nS-Q)\longrightarrow p=(nS-Q)+q}$

${\displaystyle x_{1}(q)=w((Q-q)\Delta _{\tau })x((nS-Q+q)\Delta _{\tau })}$  for ${\displaystyle 0\leq q\leq 2Q}$

${\displaystyle x_{1}(q)=0\qquad \qquad \qquad \qquad \qquad \qquad \quad \quad }$ for ${\displaystyle 2Q

#### 運算步驟

${\displaystyle \quad \;\;f=m_{0}\Delta _{f},(m_{0}+1)\Delta _{f},\cdots ,(m_{0}+F-1)\Delta _{f}}$

${\displaystyle \quad \;\;\tau =n_{0}\Delta _{\tau },(n_{0}+1)\Delta _{\tau },\cdots ,(n_{0}+T-1)\Delta _{\tau }}$

#### 複雜度

${\displaystyle O({\frac {T}{S}}N\log _{2}N)}$

### Non-Uniform ${\displaystyle \Delta _{t}}$

(1) 先用比較大的${\displaystyle \Delta _{t}}$

(2) 如果發現${\displaystyle |X(n\Delta _{t},m\Delta _{f})|}$ ${\displaystyle |X((n+1)\Delta _{t},m\Delta _{f})|}$  之間有很大的差異，則在${\displaystyle n\Delta _{t}}$ ${\displaystyle (n+1)\Delta _{t}}$  之間選用比較小的取樣區間${\displaystyle \Delta _{t1}}$

(${\displaystyle \Delta _{\tau }<\Delta _{t1}<\Delta _{t}}$ ${\displaystyle {\frac {\Delta _{t}}{\Delta _{t1}}}}$ ${\displaystyle {\frac {\Delta _{t1}}{\Delta _{\tau }}}}$ 皆為整數)

(3) 以此類推，如果 ${\displaystyle |X(n\Delta _{t}+k\Delta _{t1},m\Delta _{f})|,|X((n+1)\Delta _{t}+(k+1)\Delta _{t1},m\Delta _{f})|}$ 的差距還是太大，則再選用更小的取樣間隔${\displaystyle \Delta _{t2}}$

(${\displaystyle \Delta _{\tau }<\Delta _{t2}<\Delta _{t1}}$ ${\displaystyle {\frac {\Delta _{t1}}{\Delta _{t2}}}}$ ${\displaystyle {\frac {\Delta _{t2}}{\Delta _{\tau }}}}$ 皆為整數)

• 比較

1. 選擇${\displaystyle \Delta _{t}=\Delta _{\tau }}$ ，則共有${\displaystyle 44100*1.6+1=70561}$
2. 選擇${\displaystyle \Delta _{t}=0.01=441\Delta _{\tau }}$ ，則共有${\displaystyle 100*1.6+1=161}$
3. t隨時間不同有不同的選擇，如下
${\displaystyle t=0,0.05,0.1,0.15,0.2,0.4,0.45,0.46,0.47,0.48,0.49,0.5,0.55,0.6,0.8,0.85,0.9,0.95,0.96,0.97,0.98,0.99,1,1.05,1.1,1.15,1.2,1.4,1.6}$ ，共29點

## 參考書目、資料來源

1. Jian-Jiun Ding, Time frequency analysis and wavelet transform class notes, the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2011.
2. Alan V. Oppenheim, Ronald W. Schafer, John R. Buck : Discrete-Time Signal Processing, Prentice Hall, ISBN 0-13-754920-2
3. Jian-Jiun Ding, Time frequency analysis and wavelet transform class notes, Graduate Institute of Communication Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2017.
4. Jian-Jiun Ding, Time frequency analysis and wavelet transform class notes, Graduate Institute of Communication Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2020.