# 4.1 傅里叶级数

\begin{aligned} f(t)&\sim\frac{a_{0}}{2}+a_{1}cos(t)+a_{2}cos(2t)+a_{3}cos(3t)+\cdots \\ &b_{1}sin(t)+b_{2}sin(2t)+b_{3}sin(3t)+\cdots \\ &\sim\frac{a_{0}}{2}+{\sum_{n=1}^{\infty}}(a_{n}cos(nt)+b_{n}sin(nt)) \end{aligned} \quad(4.1)

$a_{0},a_{1},\cdots$
$b_{0},b_{1},\cdots$

\begin{aligned} a_{0}&=\frac{1}{\pi}\int_{-\pi}^{\pi}f(t)dt \\ a_{n}&=\frac{1}{\pi}\int_{-\pi}^{\pi}f(t)cos(nt)dt \\ b_{n}&=\frac{1}{\pi}\int_{-\pi}^{\pi}f(t)sin(nt)dt \end{aligned} \quad(4.2)

$a_{0},a_{1},\cdots$
,
$b_{0},b_{1},\cdots$

$a_{0}$

$a_{0}$

$b_{0}$

$t\equiv\frac{\pi t^\prime}{L} \quad(4.3)$

$dt=\frac{\pi{d} t^\prime}{L}\quad(4.4)$

$t^\prime=\frac{Lt}{\pi}$

$f(t^\prime)=\frac{a_{0}}{2}+{\sum_{n=1}^{\infty}}(a_{n}cos(\frac{n\pi{t^\prime}}{L})+b_{n}sin(\frac{n\pi{t^\prime}}{L}))\quad(4.5)$

$a_{0}=\frac{1}{L}\int_{-L}^{L}f(t^\prime)dt^\prime \quad$
$a_{n}=\frac{1}{L}\int_{-L}^{L}f(t^\prime)cos(\frac{n\pi{t^\prime}}{L})dt^\prime \quad(4.6)$
$b_{n}=\frac{1}{L}\int_{-L}^{L}f(t^\prime)sin(\frac{n\pi{t^\prime}}{L})dt^\prime \quad\quad$

$e^{jnt}=cos(nt)+jsin(nt)$

$f(t)=\sum_{n={-\infty}}^{\infty}c_{n}e^{jnt}\quad(4.7)$

$c_{n}$

$c_{n}=\frac{1}{2\pi}\int^{\pi}_{-\pi}f\left(t\right)e^{-jnt}dt\quad(4.8)$

$a_{n},b_{n}, and\,c_{n}$

$a_{n}=c_{n}+c_{-n}\text{ for }n=0,1,2,\cdots\quad\quad$
$b_{n}=j(c_{n}-c_{-n})\text{ for }n=0,1,2,\cdots\quad\quad$
$C_{n}=\begin{cases} 1/2\left( a_{n}-jb_{n}\right) n >0\\ 1/2a_{0} n =0\\ 1/2\left( a_{-n}+jb_{-n}\right) n <0 \end{cases} \quad(4.9)$

$a_{n},b_{n},c_{n}$

$cos(x)=Re\left(e^{jx}\right) =\dfrac{e^{ix}+e^{-jx}}{2}\quad(4.10)$

$sin(x)=Im\left(e^{jx}\right) =\dfrac{e^{ix}-e^{-jx}}{2j}\quad(4.11)$

$e^{jx}$
$e^{-jx}$
，图中可以看出这两个向量和是一个在实轴上的向量，大小为2cos(x)。所以，当我们将这两个向量的和除以2就到了式4.10中的cos(x)的值。图4.1中b)部分显示了类似的正弦的推导过程，这里我们添加两个复平面向量
$e^{jx}$
$e^{-jx}$
，图中可以看出这两个向量差是一个在虚轴上的向量，大小为2sin(x)。所以，当我们将这两个向量的差除以2j就到了式4.11中的sin(x)的值。

# 4.2 DFT背景介绍

DFT适用于同时包含实数和复数的输入函数。直观上，为了轻松入门，我们暂时忽略复数部分，从实数信号开始了解实际DFT的工作原理。

$\begin{bmatrix} 1 & 1 & 1 &\ldots &1\\ 1 & s &s^{2} &\ldots &s^{N-1}\\ 1 & s^{2} &s^{4} &\ldots &s^{2(N-1)}\\ 1 & s^{3} &s^{6} &\ldots &s^{3(N-1)}\\ \vdots& \vdots &\vdots &\ddots &\vdots\\ 1 & s^{N-1} &s^{2(N-1)} &\ldots &s^{(N-1)(N-1)} \end{bmatrix}\quad(4.12)$

$s=e^{\frac{-i2\pi}{N}}$
。 因此，频域中的样本被推导为
$G[t]=\sum_{n={0}}^{N-1}g[n]s^{kn}\quad for \; k=0,\ldots,N-1\quad(4.13)$

$S[i][j]=S[j][i]$
。另外，
$S[i][j]=s^{i}s^{j}=s^{i+j}$
。在第四行周围也会出现有趣的对称性现象。行3和行5中的相量是彼此的共轭复数，即
$S[j]=S[j]^{\ast}$
。 类似地，行2和6
$(S[j]=S[j]^{\ast})$

$(S[j]=S[j]^{\ast})$

#define SIZE 8
typedef int BaseType;
void matrix_vector(BaseType M[SIZE][SIZE], BaseType V_In[SIZE], BaseType V_Out[SIZE]) {
BaseType i, j;
data_loop:
for (i = 0; i < SIZE; i++) {
BaseType sum = 0;
dot_product_loop:
for (j = 0; j < SIZE; j++) {
sum += V_In[j] * M[i][j];
}
V_Out[i] = sum;
}
}

# 4.4 流水线和并行运行

$sum+= V_in [j] * M [i] [j]$
。乘法运行时，计数变量SUM在每次迭代中都被重复利用并赋予新的值。如图4.6所示，这个内部循环可以重新表述，此时变量 SUM 已被完全消除，并在较大表达式中替换为多个中间值。
#define SIZE 8
typedef int BaseType;
void matrix_vector(BaseType M[SIZE][SIZE], BaseType V_In[SIZE], BaseType V_Out[SIZE]) {
BaseType i, j;
data_loop:
for (i = 0; i < SIZE; i++) {
BaseType sum = 0;
V_Out[i] = V_In * M[i] + V_In * M[i] + V_In * M[i] +
V_In * M[i] + V_In * M[i] + V_In * M[i] +
V_In * M[i] + V_In * M[i];
}
}

$V\_In[j] * M [i][j]$

$log8 = 3$

$V\_In [j] * M [i] [j]$

# 4.5 存储权衡和数据分区

$\begin{bmatrix} 1 &2 &3 &4 &5 &6 &7 &8 &9 \end{bmatrix}$

$\begin{bmatrix} 1 &3 &5 &7 &9 \end{bmatrix}and \begin{bmatrix} 2 &4 &6 &8 \end{bmatrix}$
#define SIZE 8
typedef int BaseType;
void matrix_vector(BaseType M[SIZE][SIZE], BaseType V_In[SIZE], BaseType V_Out[SIZE]) {
#pragma HLS array_partition variable=M dim=2 complete
#pragma HLS array_partition variable=V_In complete
BaseType i, j;
data_loop:
for (i = 0; i < SIZE; i++) {
#pragma HLS pipeline II=1
BaseType sum = 0;
dot_product_loop:
for (j = 0; j < SIZE; j++) {
sum += V_In[j] * M[i][j];
}
V_Out[i] = sum;
}
}

#define SIZE 8
typedef int BaseType;
void matrix_vector(BaseType M[SIZE][SIZE], BaseType V_In[SIZE], BaseType V_Out[SIZE]) {
#pragma HLS array_partition variable=M dim=2 cyclic factor=2
#pragma HLS array_partition variable=V_In cyclic factor=2
BaseType i, j;
data_loop:
for (i = 0; i < SIZE; i++) {
BaseType sum = 0;
dot_product_loop:
for (j = 0; j < SIZE; j+=2) {
#pragma HLS pipeline II=1
sum += V_In[j] * M[i][j];
sum += V_In[j+1] * M[i][j+1];
}
V_Out[i] = sum;
}
}

HLS工具可以使用 unroll 指令自动展开循环。该指令采用一个因子作为参数，它是一个正整数，表示循环体应该展开的次数。

# 4.6 Baseline实现

$n^{2}$

#include <math.h> //Required for cos and sin functions
typedef double IN_TYPE; // Data type for the input signal
typedef double TEMP_TYPE; // Data type for the temporary variables
#define N 256 // DFT Size
void dft(IN_TYPE sample_real[N], IN_TYPE sample_imag[N]) {
int i, j;
TEMP_TYPE w;
TEMP_TYPE c, s;
// Temporary arrays to hold the intermediate frequency domain results
TEMP_TYPE temp_real[N];
TEMP_TYPE temp_imag[N];
// Calculate each frequency domain sample iteratively
for (i = 0; i < N; i += 1) {
temp_real[i] = 0;
temp_imag[i] = 0;
// (2 * pi * i)/N
w = (2.0 * 3.141592653589 / N) * (TEMP_TYPE)i;
// Calculate the jth frequency sample sequentially
for (j = 0; j < N; j += 1) {
// Utilize HLS tool to calculate sine and cosine values
c = cos(j * w);
s = sin(j * w);
// Multiply the current phasor with the appropriate input sample and keep
// running sum
temp_real[i] += (sample_real[j] * c - sample_imag[j] * s);
temp_imag[i] += (sample_real[j] * s + sample_imag[j] * c);
}
}
// Perform an inplace DFT, i.e., copy result into the input arrays
for (i = 0; i < N; i += 1) {
sample_real[i] = temp_real[i];
sample_imag[i] = temp_imag[i];
}
}

# 4.7 DFT优化

$s^\prime$
$S^\prime=S[.]=\begin{bmatrix} 1 & s &s^{2} &\ldots &s^{n-1}\\ \end{bmatrix}$

$s^\prime$

$s^\prime$

$s^\prime$

$s^\prime$

$s^\prime$

$s^\prime$

$s^\prime$
——S矩阵的一维版本的体系结构。这种体系结构是如何影响到所需的存储空间的？与使用二维的S矩阵的实现相比，这会改变逻辑利用率吗？