数字信号处理之FT, DTFT, DTFS, DFT (5)

在前一节说过 \(X(e^{j\omega})\) 写法的由来,这里还是提一下

模拟信号的频域写成 \(X(j \Omega)\) 的形式

数字信号的频域写成 \(X(e^{j\omega})\) 的形式,

我们引入欧拉公式 \[
e^{j\omega} = \cos \omega + j \sin \omega
\]
因此 \(e^{j 2 \pi} = \cos 2\pi + j \sin 2\pi =1\)

公式证明在另外一篇博客提到过,用麦克劳林公式展开即可证明公式两边相等

从上面这张图我们可以看到什么情况使用哪种形式的傅里叶变换

  • 时域连续非周期,频域连续非周期 – FT
  • 时域连续周期,频域离散非周期 – FS
  • 时域离散非周期,频域连续周期 – DTFT
  • 时域离散周期,频域离散周期 – DTFS -> DFT

上图中 \(x[n]\)\(x_{ps} [n]\) 是利用周期延拓

这张图在学习完本节之后会有更深的了解

1. FT – Fourier Transform

傅里叶变换是如此重要,我们在前面两个2个小节中都提到过 \[
X(j\Omega) = \int_{-\infty} ^{\infty} x(t) e^{-j \Omega t} dt \\\\
x(t) = \cfrac {1} {2\pi} \int_{-\infty} ^{\infty} X(j \Omega) e^{j \Omega t} d \Omega
\]

2. DTFT – Discrete-time Fourier Transform

由于ADC芯片不可能做到无间隔连续采样,自然我们采集的数字信号是时间离散的(其实就是和梳状函数相乘),自然连续状态的积分变为离散状态的求和 \[
X(e^{j \omega}) = \sum_{n = -\infty} ^{\infty} x[n] e^{-j \omega n} \\\\
x[n] = \cfrac {1} {2 \pi} \int_{-\pi} ^{\pi} X(e^{j \omega}) e^{j\omega n} d \omega
\]

证明:

假设有 \[
\hat x[n] = \cfrac {1} {2\pi} \int_{-\pi}^{\pi} (\sum_{m = -\infty} ^{\infty} x[m] e^{-j \omega m}) e^{+j \omega n}) d \omega
\]
我们证明 \(\hat x[n] = x[n]\) \[
\hat x[n] = \sum_{m = -\infty} ^{\infty} x[m] (\cfrac {1} {2\pi}\int_{-\pi}^{\pi} e^{+j \omega (n-m)} d \omega)
\]
如果 $ m = n$ ,那么 \(e^{j \omega (n-m)} = 1\) ,则 \[
\cfrac {1} {2\pi}\int_{-\pi}^{\pi} 1. d \omega = 1
\]
如果 $ m n$ , 那么 \(e^{j \omega (n-m)} = \cos \omega(n-m) + j \sin \omega(n-m)\) (利用欧拉公式) \[
\begin {align}
\cfrac {1} {2\pi}\int_{-\pi}^{\pi} e^{j \omega (n-m)} d \omega &= \cfrac {1} {2\pi}\int_{-\pi}^{\pi} \cos \omega(n-m)d \omega + \cfrac {j} {2\pi}\int_{-\pi}^{\pi} \sin \omega(n-m)d \omega \\
&= \cfrac {1} {2\pi} \cfrac {\sin \omega (n-m)} {(n-m)} \mid_{-\pi} ^{\pi} + \cfrac {j} {2\pi} \cfrac {\cos \omega (n-m)} {(n-m)} \mid_{-\pi} ^{\pi} \\
&= 0
\end {align}
\]
因此 \(m = n\) , 于是 \(\hat x[n] = x[n]\)

性质:

  1. 周期性 (periodicity)
    \(X(e ^ {j \omega}) = X( e^ {j (\omega +2k \pi )}), k \in N\)

  2. 线性 (linearity)

  3. 共轭 (conjugation)
    如果 \(\{ x[n]\} \leftrightarrow X(e^{j \omega})\)
    那么 \(\{ x^{\ast}[n]\} \leftrightarrow X^{\ast}(e^{-j \omega})\)
    这里 \(\ast\) 表示 复共轭,即实部不变,虚部取反
    证明: \[
    \begin {align}
    \sum_{ n = -\infty} ^{\infty} x^{\ast}[n] e^{-j \omega n} &= \sum_{ n = -\infty} ^{\infty} [x[n] e^{j \omega n}]^{\ast} \\
    &= \sum_{ n = -\infty} ^{\infty} [x[n] e^{-j {(-\omega)}n }]^{\ast} \\
    &= X^{\ast}(e^{-j \omega})
    \end {align}
    \]

  4. 时域取反 \[
    \{ x[-n]\} \leftrightarrow X(e^{-j \omega})
    \]

  5. 时移和频移 \[
    \{ x[n – n_0]\} \leftrightarrow e^{-j \omega n_0} X(e^{j \omega})
    \]

    \[
    \{ e^{j \omega_0 n} x[n – n_0]\} \leftrightarrow X(e^{j (\omega – \omega_0)})
    \]

  6. 时域卷积等于频域相乘,但反之不成立,见下一个性质
    如果 \(\{ y[n]\} = \{ x[n]\} \ast \{ h[n]\}\)
    那么 \(Y(e^{j \omega}) = X(e^{j \omega}) H(e^{j \omega})\)
    证明过程非常类似傅里叶变换的卷积证明

  7. 但是如果时域相乘,频域则是周期卷积
    如果 \(\{ z[n]\} = \{ x[n]\} \{ y[n]\}\)
    那么 \[
    Z^(e^{j \omega}) = \sum_{n=-\infty} ^{\infty} x[n] y[n] e^{-j \omega n}
    \]
    \(x[n]\) 做 IDFT 变换 \[
    = \sum_{n=-\infty} ^{\infty} (\cfrac {1} {2 \pi} \int_{-\pi} ^{\pi} X(e^{j \alpha}) e^{j\alpha n} d \alpha) y[n] e^{-j \omega n}
    \]
    改变积分和求和的次序 \[
    \begin {align}
    &= \cfrac {1} {2 \pi} \int_{-\pi} ^{\pi} X(e^{j \alpha}) [\sum_{n=-\infty} ^{\infty} y[n] e^{-j (\omega-\alpha) n}] d \alpha \\
    &= \cfrac {1} {2 \pi} \int_{-\pi} ^{\pi} X(e^{j \alpha}) Y(e^{j (\omega – \alpha)}) d \alpha
    \end {align}
    \]
    可以看到积分的周期是从 \(-\pi\)\(\pi\)\(X(e^{j \omega})\)\(Y(e^{j \omega})\) 都是周期函数,因此等式又称周期卷积 \[
    \{ x[n] y[n] \} \longleftrightarrow \cfrac {1} {2 \pi} X(e^{j \omega}) \otimes Y(e^{j \omega})
    \]
    其中 \(\otimes\) 表示 周期卷积

3. DTFS – Discrete-time Fourier Series

3.1 基本离散周期复指数 – \(e^{\frac {j 2 \pi}{N}}\)

这里不知道怎么翻译,英文为: basic periodic discrete-time complex exponentials

性质:

  1. \(e^{\frac {j 2 \pi n}{N}}\) 为周期函数,周期为 \(N\)

  2. \(e^{\frac {j 2 \pi kn}{N}}\) 也是周期为 \(N\) 的周期函数,即 \[
    e^{\frac{j 2 \pi k}{N}(n +N)} = e^{\frac{j 2 \pi k n}{N}} \cdot e^{\frac{j 2 \pi k N}{N} = e^{\frac{j 2 \pi k n}{N}}}
    \]
    但如果 \(k \neq 1\), 则 \(N\) 不是基本周期

  3. 由于 \(k\)\(n\) 的对称性, \[
    e^{j 2 \pi \frac{(k + N)}{N}n} = e^{\frac{j 2 \pi k n}{N}}
    \]

  4. 求和性质 \[
    \sum_{n = 0}^{N-1} e^{\frac{j 2 \pi k n}{N}} =
    \begin{cases}
    0, & k \neq 0 \\
    N, & k = mN
    \end{cases}
    \]
    利用等比数列求和证明
    \(k \neq 0\) 时, \[
    \begin{align}
    \sum_{n = 0}^{N-1} e^{\frac{j 2 \pi k n}{N}} &= \frac{1 – e^{\frac{j 2 \pi k N}{N}}}{1 – e^{\frac{j 2 \pi k}{N}}}, \\
    &= \frac{1 – 1}{1 – e^{\frac{j 2 \pi k}{N}}} \\
    &= 0
    \end{align}
    \]
    \(k = mN\) 时, \[
    e^{\frac{j 2 \pi k N}{N}} = e^{\frac{j 2 \pi m N n}{N}} = 1
    \]

    \[
    \sum_{n=0}^{N-1} 1= N
    \]

  5. harmonically-related complex exponential series are orthogonal \[
    \sum_{n = 0}^{N -1} e^{\frac{j 2 \pi k_1 n}{N}} e^{\frac{j 2 \pi k_2 n}{N}} =
    \begin{cases}
    0, & k_1+k_2 \neq mN \\
    N, & k_1 + k_2 = mN
    \end{cases}
    \]

3.2 DTFS

假设 \(x[n]\) 是离散时间信号,周期为 \(N\)

声明(a): \(x[n]\) 完全可以用基本周期为 \(N\) 的复指数的线性组合表示

根据前面的复指数性质1\(e^{\frac {j 2 \pi n}{N}}\) 的基本周期为 \(N\)

于是,该声明可以写为: \[
x[n] = \sum_{ k =0}^{N-1} a_k e^{\frac {j 2 \pi n}{N}}
\]
声明(b) 这种表示方式是唯一的 \[
\left [
\begin{matrix}
x[0] \\
x[1] \\
\vdots \\
x[N-1]
\end{matrix}
\right]
=
\left[
\begin{matrix}
1 & 1 & 1 & \ldots & 1\\
1 & e^{\frac{j 2 \pi}{N}} & e^{\frac{j 2 \pi 2}{N}} & \ldots & e^{\frac{j 2 \pi (N-1)}{N}}\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & e^{j 2 \pi \frac{(N-1)}{N}} & e^{j 2 \pi \frac{2(N-1)}{N}} & \ldots & e^{j 2 \pi \frac{(N-1)(N-1)}{N}}
\end{matrix}
\right]
\cdot
\left[
\begin{matrix}
a_o \\
\vdots \\
\vdots \\
a[N-1]
\end{matrix}
\right]
\]
\[
X =
\left [
\begin{matrix}
x[0] \\
x[1] \\
\vdots \\
x[N-1]
\end{matrix}
\right]
\]

\[
A =
\left[
\begin{matrix}
a_o \\
\vdots \\
\vdots \\
a[N-1]
\end{matrix}
\right]
\]

\[
D =
\left[
\begin{matrix}
1 & 1 & 1 & \ldots & 1\\
1 & e^{\frac{j 2 \pi}{N}} & e^{\frac{j 2 \pi 2}{N}} & \ldots & e^{\frac{j 2 \pi (N-1)}{N}}\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & e^{j 2 \pi \frac{(N-1)}{N}} & e^{j 2 \pi \frac{2(N-1)}{N}} & \ldots & e^{j 2 \pi \frac{(N-1)(N-1)}{N}}
\end{matrix}
\right]
\]

我们可以写成: \[
X = DA
\]
如果 \(D^{-1}\) 存在,则可以得到 \(A = D^{-1} X\)

还是利用 复指数的求和性质,得到 \(D^{-1} = \cfrac {1}{N} D^{\ast}\), 其中 \(D^{\ast}\)\(D\) 的共轭矩阵 \[
D^{\ast} =
\left[
\begin{matrix}
1 & 1 & 1 & \ldots & 1\\
1 & e^{-\frac{j 2 \pi}{N}} & e^{-\frac{j 2 \pi 2}{N}} & \ldots & e^{-\frac{j 2 \pi (N-1)}{N}}\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & e^{-j 2 \pi \frac{(N-1)}{N}} & e^{-j 2 \pi \frac{2(N-1)}{N}} & \ldots & e^{-j 2 \pi \frac{(N-1)(N-1)}{N}}
\end{matrix}
\right]
\]
对于 \(D^{\ast}\)\(i\) 行和\(D\)\(k\) 列点乘: \[
D^{\ast}(i, \colon) \cdot D(\colon, k) = \sum_{n = 0}^{N-1} e^{\frac{j 2 \pi i n}{N}}e^{-\frac{j 2 \pi k n}{N}}
\]

\[
\sum_{n = 0}^{N-1} e^{\frac{j 2 \pi (i) n}{N}}e^{-\frac{j 2 \pi (k) n}{N}} =
\begin{cases}
0, & i \neq k \\
N, & i = k
\end{cases}
\]

于是我们同时证明了声明(a)和(b)

完整写出 DTFS 的公式: \[
x[n] = \sum_{k = 0}^{k -1}a_k e^{\frac{j 2 \pi k N}{N}}
\]

\[
a_k = \frac{1}{N} \sum_{n=0}^{N-1} x[n]e^{-\frac{j 2 \pi k n}{N}}
\]

4. DFT – Discrete Fourier transform

任何信号 \(x[n]\) 的 N-point DFT 定义如下: \[
X[k] \triangleq \begin{cases}
\sum_{n=0}^{N-1} x[n]e^{-j \frac {2\pi}{N}kn} &,k=0,…, N-1 \\
?? &, \text {otherwise}.
\end{cases}
\]
反 DFT 运算 \[
\tilde x[n] =
\begin{cases}
\frac {1}{N} \sum_{n=0}^{N-1} X[k]e^{j \frac {2\pi}{N}kn} &,n=0,…, N-1 \\
0 &, \text {otherwise}.
\end{cases}
\]
注意 \(\tilde x[n]\)\(x[n]\) 不一定是相等的。只有在 \(x[n]\) 的非0点的总长度 \(L \le N\) 时,才有 \(\tilde x[n] = x[n]\)

the DFT/DTFT relationship holds only if \(x[n]\) is an L-point signal with \(L \le N\)

对于仅仅是时间离散的DTFT变换,我们可以看到频域仍然是连续的。进行反 DTFT 变换要进行积分运算,非常麻烦,我们喜欢的是类似 DTFT 的求和运算。

后面出现了两个思路:

  1. 将离散的时域进行周期延拓,然后自然可以用 DTFS
  2. 进一步离散频域,然后用离散点求和得到时域点

Any signal that is stored in a computer must be a finite length sequence.

我们可以先从思路2看出 DTFS 和 DFT 的联系

如果将 \(X[k]\) 视为 \(N\) 点周期函数,对于 \(k \in \mathbb Z\) \[
X[k+N] = \sum_{n=0}^{N-1} x[n] e^{-j \frac {2\pi}{N} (k+N)n} = \sum_{n=0}^{N-1} x[n]e^{-j \frac {2\pi}{N}kn} = X[k]
\]
反 DTFS 运算会得到周期函数 \(x_{ps}[n]\) ,周期为 \(N\) , 然后 DFT 运算就是取其中的一个周期的 \(N\) 个点,其他的点都不用定义

从思路1看出 DTFT 和 DFT 的联系

进行 DTFT 运算获得连续频谱后,对 \([0, 2 \pi]\) 进行 \(N\) 点划分,得到的就是 DTFT 运算得到的 N 点

如果 \(x[N]\) 是一个 \(L\) 点信号 \(L \le N\), 那么\(N\) 点 DFT 的值是 DTFT 信号的采样点 \[
X[k] = X[e^{j \omega}] \; \mid_{\omega = \frac{2\pi}{N}k}
\]
看下下面两者的联系

4.1 C Code for DFT

\[
X[n] = \cfrac {1} {\sqrt N}\sum_{m=0}^{N-1} x[m]e^{-j \frac {2\pi}{N}mn}, \quad x[m] = \cfrac {1} {\sqrt N}\sum_{n=0}^{N-1} X[n]e^{j \frac {2\pi}{N}mn}
\]

下面是对应的代码:

for (n=0; n<N; n++) {
    Xr[n]=Xi[n]=0;
    for (m=0; m<N; m++) {
        w=2*pi*m*n/N;
        if (forward) w=-w;
        wr=cos(w); wi=sin(w);
        Xr[n]=Xr[n]+wr*xr[m]-wi*xi[m];
        Xi[n]=Xi[n]+wr*xi[m]+wi*xr[m];
    }
    Xr[n]=Xr[n]/sqrt(N);
    Xi[n]=Xi[n]/sqrt(N);
}

以前向DFT为例,有: \[
\begin {aligned}
X[n] &= X_r[n] + j X_i[n] = \cfrac {1} {\sqrt N} \sum_{m=0}^{N-1} x[m] e^{-j \frac {2\pi}{N}mn} \\
&= \cfrac {1} {\sqrt N} \sum_{m=0}^{N-1} (x_r[m] + j x_i[m]) \big (\cos (2\pi mn/N) – j \sin (2\pi mn/N) \big )
\end {aligned}
\]
于是: \[
X_r[n] = \cfrac {1} {\sqrt N} \sum_{m=0}^{N-1} x_r[m] \cos (2\pi mn/N) + x_i[m] \sin (2\pi mn/N) \\
X_i[n] = \cfrac {1} {\sqrt N} \sum_{m=0}^{N-1} x_i[m] \cos (2\pi mn/N) – x_r[m] \sin (2\pi mn/N)
\]
这就是前面公式里面的计算 !!!

4.2 一些结论,和数学相关

通常,实数信号 \(x[m]\) (即虚部为0)的频谱 \(X[n]\) 有如下结论:

注意:这里把系数 \(\cfrac {1}{N}\) 放在 \(X[n]\) 的计算中

  1. \(X_r[0]\) 是信号的直流分量,或者说平均值: \[
    X_r[0] = Re \{ X[0] \} = \cfrac {1} {N} \sum_{m=0}^{N-1} x[m] \cos (2\pi m0/N) = \cfrac {1} {N} \sum_{m=0}^{N-1} x[m]
    \]

  2. \(X_r[N/2]\) 是偶数序列信号和奇数序列信号的差值 \[
    \begin {aligned}
    X_r[N/2] &= Re \{X[N/2] \} = \cfrac {1} {N} \sum_{m=0}^{N-1} x[m]\cos (2\pi m N/(2N)) \\
    &= \cfrac {1} {N} \sum_{m=0}^{N-1} x[m] \cos(\pi m) = \cfrac {1} {N} \sum_{m=0}^{N-1} x[m] (-1)^m
    \end {aligned}
    \]

  3. \(X_i[0]\)\(X_i[N/2]\) 均为0 \[
    X_i[0] = Im \{ X[0] \} =- \cfrac {1} {N} \sum_{m=0}^{N-1} x[m] \sin (2\pi m0/N) = 0 \\
    X_i[N/2] = Im \{ X[N/2] \} =-\cfrac {1} {N} \sum_{m=0}^{N-1} x[m] \sin (2\pi m N/(2N)) = 0
    \]

  4. 对于 \(0 \lt n \lt N/2\) , \(X[n]\) 的实部是偶对称,虚部奇对称 \[
    \begin {aligned}
    Re \{X[N-n] \} &= \cfrac {1} {N} \sum_{m=0}^{N-1} x[m]\cos (2\pi m (N-n)/N) \\
    &= \cfrac {1} {N} \sum_{m=0}^{N-1} x[m]\cos (2\pi m n/N) \\
    &= Re \{X[n] \}
    \end {aligned}
    \]

    \[
    \begin {aligned}
    Im \{X[N-n] \} &= – \cfrac {1} {N} \sum_{m=0}^{N-1} x[m]\sin (2\pi m (N-n)/N) \\
    &= \cfrac {1} {N} \sum_{m=0}^{N-1} x[m]\sin (2\pi m n/N) \\
    &= -Im \{X[n] \}
    \end {aligned}
    \]

我们在傅里叶变换中提到的一点,幅频谱关于原点偶对称,同时 DFT 的周期为 \(N\)

于是同样可以得到 \(Re \{X[N-n] \} = Re \{X[-n] \} = Re \{X[n] \}\)

此时我们可以得到另外一个结论:

magnitude spectrum 关于 \(N/2\) 点偶对称,而 phase spectrum 关于 \(N/2\) 点奇对称

注意: 低频分量和高频分量的表征

DFT 变换中,\(X[0], X[1], \ldots, X[N-1]\) 表示 \(N\) 个频率成分 (\([0, 2\pi]\) 分布)

其中最低频率成分为 \(X[0]\), 最高频率成分为 \(X[N/2]\) (通过采样定理可以很好理解),超过 \(N/2\) 记为负数频率成分,下图很清晰地表述这一点,但下图没有表示清楚 DFT 的关于 \(N/2\) 点对称的特点,这里不要在意。

因此我们把 \(N/2\) 对应的频率称为 Nyquist frequency. This is the highest frequency component that should exist in the input series for the DFT to yield “uncorrupted” results. More specifically if there are no frequencies above Nyquist the original signal can be exactly reconstructed from the samples.

如果我们想把最高频率移动到两边,把最低频率移动到中心,怎么做 ?

(注: 这个需求在二维傅里叶变换中会出现) \[
X'[n] = X[n-N/2]
\]
1. 原始信号获得对应的频谱后,再将低频搬移到中心

  1. 根据傅里叶变换的移位性质: \[
    x[m]e^{j2\pi mn_0/N} \Leftrightarrow X[n-n_0]
    \]
    \(n_0 = N/2\) ,我们有: \[
    x[m] e^{j\pi m} = x[m] (-1)^m = \mathcal {F}^{-1} [X[n-N/2]]
    \]
    也就是说,如果原始信号奇数序列对应的值改变正负号,偶数序列不变,直接进行傅里叶变换,可以得到低频中心化的频谱

2 thoughts on “数字信号处理之FT, DTFT, DTFS, DFT (5)

发表评论

电子邮件地址不会被公开。 必填项已用*标注