#### DFS(离散傅里叶序列)

DFS是DFT的周期扩展，公式如下：

### DFT,DFS,DTFT

#### DFTF(离散时间傅里叶变换)

• $\mathrm x[n] \in \ell_{2}(\mathbb{Z})$

• 定义$\omega \in \mathbb{R}$的函数

• 逆变换（如果$F(\omega)$存在）：

##### 基本性质
• $F(\omega)$以$2\pi$为周期

• 为了表达这点，记$F(\omega)$为

• 为了方便起见，$X\left(e^{j \omega}\right)$定义在区间$[-\pi, \pi]$

• 有限长度信号：DFT
• 周期序列：DFS
• 无限序列：DTFT

### DTFT：直觉和性质

#### 基变换视角

• 将DFTF视为$\mathbb{C}^{\infty}$的内积：

• “基”是无限不可数集$\left\{e^{j \omega n}\right\}_{ \omega \in \mathbb{R}}$

DFT

DFS

DFTF

#### 性质

1. linearity

2. time shift

3. modulation (dual)

4. time reversal

5. conjugation

6. 如果$x[n]$对称，那么DTFT对称

7. 如果$x[n]$Hermitian对称，那么DTFT是Hermitian对称

8. 如果$x[n]$是实数，DTFT的模长是对称的

9. 如果$x[n]$是实对称，那么$X\left(e^{j \omega}\right)$也是实对称

2.

3.

#### 例子

##### 2.Dirac delta函数

• $\text{DTFT}\{1\}=\tilde{\delta}(\omega)$
• $\text{DTFT}\left\{e^{j \omega_{0} n}\right\}=\tilde{\delta}\left(\omega-\omega_{0}\right)$
• $\text{DTFT}\left\{\cos \omega_{0} n\right\}=\left[\tilde{\delta}\left(\omega-\omega_{0}\right)+\tilde{\delta}\left(\omega+\omega_{0}\right)\right] / 2$
• $\text{DTFT}\left\{\sin \omega_{0} n\right\}=-j\left[\tilde{\delta}\left(\omega-\omega_{0}\right)-\tilde{\delta}\left(\omega+\omega_{0}\right)\right] / 2$

### FFT

DFT的时间复杂度为$O(N^2)$，现在希望减少其时间复杂度，这里介绍FFT。

### DFT的矩阵分解视角

• 分离偶数和奇数样本
• 计算两个大小为$N、2$的DFT，分别输出$X ^ {\prime} [k]$和$X ‘’[k]$
• 计算$X’ [k]$和$W ^ {k} X’’ [k]$的和与差

### 习题

#### 1

(Difficulty: $\star$ ) Consider the magnitude DTFTs $\left|X\left(e^{j \omega}\right)\right|$ and $\left|Y\left(e^{j \omega}\right)\right|$ shown below, where vertical lines represent Dirac deltas:

Both underlying signals $x[n]$ and $y[n]$ are periodic. Find their periods and write them below, separated by a space. Please write the smallest period, i.e. a 5 -periodic signal is also obviously 15 -periodic but we’re interested in 5.
Enter the period of $x[n]$ and $y[n]$ with a unique white space in between.

$y$的频率为

#### 2

(Difficulty: $\star$ ) We will see in later lectures that communication systems must fulfill what is called the “bandwidth constraint”, that is, the energy of the signals that they transmit must strictly fit into pre-defined frequency bands. In this problem we will look at the bandwidth constraint in the discrete-time domain.

The signal $x[n]$ is real-valued and its spectrum is nonzero only over the $[-\pi / 8, \pi / 8]$ interval. Due to the bandwidth constraint we need to “fit” the signal over the bands indicated in green in the following figure

To this aim, we need to design a processing block $\mathcal{H}$ in order to convert $x[n]$ into a sequence $s[n]$ satisfying the following requirements:
The support of the DTFT of $s[n]$ must be limited to $[-3 \pi / 4,-\pi / 2] \cup[\pi / 2,3 \pi / 4]$
The sequence $s[n]$ must be real-valued $(x[n]$ is real-valued)
Which of the following input/output relationships for $\mathcal{H}$ meet both requirements? (check all correct answers):

• $s[n]=e^{j \frac{5 \pi}{8} n} \cdot x[n]$
• $s[n]=\sin \left(\frac{21 \pi}{8} n\right) \cdot x[n]$
• $s[n]=\cos \left(\frac{5 \pi}{8} n\right) \cdot x[n]$
• $s[n]=\operatorname{IDTFT}\left\{X\left(e^{j(\omega-5 \pi / 8)}\right)\right\}$

#### 3

(Difficulty: $\star$ ) Consider the length- $L$ signal
$x[n]=\left\{\begin{array}{ll}1 & 0 \leq n \leq M-1 \ 0 & M \leq n \leq L-1\end{array}\right.$
Write out the closed-form analytical expression for its DFT coefficients $X[k]$
Be careful with your typing since the regular-expression parser can be a bit picky. Check Coursera help to enter math expression. In particular, remember that in the Coursera platform the symbols are different:
$I(\text { capital i) is used for the imaginary unit instead of } j$

• Euler’s number is $E$ instead of $e$
you can also use the exponential function $\exp (\cdot)$
• $\pi$ is defined as $p i$
The only other symbols you’ll need for the answer are the case-sensitive variables $k, M, L$
For instance, the expression $e^{j(\pi L+3 \pi)} /(k+M)$ should be entered as

#### 4

The real and imaginary parts of $X\left(e^{j \omega}\right)$ are:

After examining the plots, check all the correct statements below.

• $x[n]$ is Hermitian-symmetric $x[n]=x^{*}[-n]$
• $x[n]$ is 0-mean, i.e. $\sum_{n \in \mathbb{Z}} x[n]=0$
• $x[n]$ is real-valued.

• 如果$x[n]$Hermitian对称，那么DTFT是Hermitian对称

• 如果$x[n]$是实数，DTFT的模长是对称的

#### 5

(Difficulty: $\star \star)$ Consider a signal $x[n]$ and its DTFT $X\left(e^{j \omega}\right) .$ Assume $X\left(e^{j \omega}\right)$ is differentiable. Compute the inverse DTFT of
$j \frac{d}{d \omega} X\left(e^{j \omega}\right)$

#### 6

(Difficulty: $\star$ ) Which property of the DTFT allows you to easily compute the inverse DTFT of $4 X\left(e^{j \omega}\right) / \pi-2$ once you know $x[n] ?$ Just type the name of the property.

#### 7

(Difficulty: $\star$ ) Take a length- $N$ signal $x[n]$ and its DFT $X[k],$ with $0 \leq n, k, \leq N-1$. Next, consider its periodized version $\tilde{x}[n]=x[n \bmod N]$ with its DFS $\tilde{X}[k]$ where now $n, k \in \mathbb{Z}$
Which of the following statements are true?

• $\tilde{X}[-2]=X[2]$ for all $x[n]$ and $N>2$
• $\tilde{X}[l]=X[l \bmod N],$ for all $l \in \mathbb{Z}$
• $\tilde{X}[k+l N]=X[k],$ for all $l \in \mathbb{Z}$ and $k=0, \ldots, N-1$

#### 8

(Difficulty: $\star$ ) In the class, we learned how the modulation theorem can help us tune a musical instrument. Martin showed us an example with a bass but of course the same works with a classical guitar. Listen carefully to these two samples (with earphones, if possible); each audio clip is the recording of two notes played together:

• Audio clip B

Select the correct options below.

• The notes are in tune in both audio clips
• The notes are in tune in audio clip $A$ and out of tune in audio clip $B$
• The notes are out of tune in both audio clips
• The notes are in tune in audio clip $\mathrm{B}$ and out of tune in audio clip $\mathrm{A}$

#### 9

(Difficulty: $\star \star)$ A ringback tone is the sound you hear in your landline telephone when the remote phone you are trying to call is ringing.
In most European countries, the ringback tone is a single sinusoid turned on and off periodically while in the USA, the ringbback tone is the sum of 2 sinusoids with relatively close frequencies turned on and off periodically.
Here are two audio clips:

• Sample $A$
• Sample $B$

Just by listening to the clips, you should be able to identify the US ringback tone. Explain in the box below what helped you identify the US tone. Use the wording and concepts that appear in the lecture slides. No credit, without a proper explanation, e.g., “I live there” is not an answer.

US tone has beats from the frequency

#### 10

(Difficulty: $\star$ ) As explained in previous question, the European and US ringback tones are composed of one or two sinusoids respectively, multiplied by a square wave switching between 0 and $1 .$ This multiplication by a square wave periodically mutes the sinusoid(s).
Look at the following magnitude DTFT plots (each plot shows the interval $[-\pi, \pi]):$

Select the correct statement amongst the choices below.

• Spectrum (a) corresponds to the European ringback tone.
• Spectrum (a) corresponds to the US ringback tone.
• Spectrum (b) corresponds to the European ringback tone.
• Spectrum (b) corresponds to the US ringback tone.

#### 11

(Difficulty: $\star$ ) Consider the sequences

with $n \in \mathbb{Z}$
Select the correct statements below.

• There exists $N \in \mathbb{N}$ for which $x_{1}[n]$ has a DFS of size $N$
• There exists $N \in \mathbb{N}$ for which $x_{2}[n]$ has a DFS of size $N$

#### 12

(Difficulty: $\star \star$ ) Consider a signal $x[n] ;$ the only thing we know about the signal is that its DTFT is strictly bandlimited between $-\frac{\pi}{10}$ and $\frac{\pi}{10} .$ We now modulate the signal to obtain $y[n]=x[n] \cos \left(\omega_{c} n\right)$
Among the possibilities below, select all the values for $\omega_{c}$ that allow us to perfectly demodulate $y[n]$

• $\frac{\pi}{20}$
• $\frac{\pi}{3}$
• $\frac{9\pi}{10}$
• $\frac{11 \pi}{12}$

• $|\frac{\pi}{20}-\frac \pi {10}| <\frac{\pi}{10}$
• $|\frac{\pi}{3}-\frac \pi {10}| >\frac{\pi}{10},|\frac{\pi}{3}+\frac \pi {10}|<\pi$
• $|\frac{9\pi}{10}-\frac \pi {10}| >\frac{\pi}{10},|\frac{9\pi}{10}+\frac \pi {10}|=\pi$
• $|\frac{11\pi}{12}-\frac \pi {10}| >\frac{\pi}{10},|\frac{11\pi}{12}+\frac \pi {10}|>\pi$