蝶形运算

Radix-4_FFT

4点DFT定义为：
$$X(k) = \sum_{n=0}^{3} x(n)W_4^{nk}$$
其中

$$W_4 = e^{-j2\pi/4} = e^{-j\pi/2} = -j$$

因此
$$W_4^0 = 1, \quad W_4^1 = -j, \quad W_4^2 = -1, \quad W_4^3 = j$$

蝶形算子（Butterfly Operation）

基本蝶形运算（以 Radix-2 DIT 为例）是 FFT 算法的核心单元。它接收两个复数输入，只需一次复数乘法和两次复数加/减法，就能产生两个输出：

输入： $a, b$（两个复数）
输出：
$$u = a + b \cdot W$$
$$v = a - b \cdot W$$

其中 $W$ 是旋转因子（Twiddle Factor），$W = W_N^k = e^{-j\frac{2\pi k}{N}}$

计算过程：

关键在于 $b \cdot W$ 只算一次，然后被两个输出共用。引入中间量 $t = b \cdot W$：

  1. 先计算 $t = b \cdot W$（唯一的一次复数乘法）
  2. $u = a + t$（上路输出，加法）
  3. $v = a - t$（下路输出，减法）

因为加法和减法共享同一个乘积 $t$，所以整个蝶形只有 1 次乘法，而不是 2 次。这正是蝶形结构”省乘法”的来源。

FFT 的本质：

FFT 通过分治（Divide and Conquer）策略，把一个 $N$ 点的 DFT 递归拆成两个 $N/2$ 点的 DFT，再用蝶形把子结果合并。整个过程呈现为 $\log_2 N$ 级（Stage）的蝶形级联。以 DIT、输入按位反序（bit-reversed）排列为例：

  • 第 1 级： 对间距为 1 的相邻样本做蝶形，此级旋转因子全为 $W^0 = 1$（无需真正乘法）
  • 第 2 级： 蝶形跨度翻倍到 2，用到 2 个不同的旋转因子
  • …每深入一级，跨度翻倍、用到的不同旋转因子数量也翻倍
  • 最后一级： 跨度为 $N/2$，用到 $N/2$ 个不同的旋转因子

每一级都恰好包含 $N/2$ 个蝶形运算，共 $\log_2 N$ 级，因此总运算量约为 $\frac{N}{2}\log_2 N$ 次复数乘法，复杂度从 $O(N^2)$ 降到 $O(N\log_2 N)$。

硬件实现优势：

在 BBE32EP 这样的 SIMD DSP 中，蝶形运算的特点非常适合向量化：

  • 加/减法是逐元素操作，可以 16 路并行
  • 复数乘法（旋转因子）可以用专用的 MAC 单元高效实现
  • 内存访问模式规则，充分利用 cache 和预取

IQ信号

传统的无线电信号是通过改变高频正弦波的幅度或相位来传输信息的。但在数学和硬件实现上，直接控制相位非常困难。因此，将一个信号拆分成了两路互相垂直（相位相差 90 度）的分量：

  • I (In-phase，同相分量)：代表原始的余弦波（Cosine）载波。
  • Q (Quadrature，正交分量)：代表与 I 信号相位相差 90 度的正弦波（Sine）载波。

在数学上，我们将 I 作为实部（Real），Q 作为虚部（Imaginary），组合成一个复数：

$$
S = I + jQ
$$

利用欧拉公式 $e^{j\omega t} = \cos(\omega t) + j\sin(\omega t)$，DSP 芯片只需要对复数进行简单的乘加运算（如 BBE_CMUL），就能在数字世界里完美实现信号的旋转、滤波和频率变换。这比在模拟电路里去调电容电感要精准得多。

IQ反转

IQ 反转，通俗来说就是 I 和 Q 的位置或者相位颠倒了。在数学上，它通常表现为共轭（Conjugate）操作。最常见的 IQ 反转有两种形式：

  1. I 和 Q 互换位置：原本是 $I + jQ$，变成了 $Q + jI$。
  2. Q 信号取反（频谱镜像）：原本是 $I + jQ$，变成了 $I - jQ$（即复数共轭）。

卷积（Convolution）

用于描述一个线性时不变（LTI, Linear Time-Invariant）系统对输入信号的响应。
简单来说，只要知道了系统的单位冲激响应，通过卷积，你就能计算出系统在任何信号输入下的输出。

LTI 系统具有两个超级特性：

  • 叠加性（Linearity）： 输入 $x_1(t) + x_2(t)$，输出就是 $y_1(t) + y_2(t)$。
  • 时不变性（Time-Invariance）： 输入延迟 $\tau$，输出就延迟 $\tau$。

基于这两个特性，我们可以把任意复杂的输入信号 $x(t)$，拆解为无数个不同强度、不同位置的单位冲激信号 $\delta(t)$ 的组合。如果我们已知系统对一个标准冲激信号 $\delta(t)$ 的响应是 $h(t)$（称为单位冲激响应），那么根据 LTI 特性：系统对延迟了 $\tau$ 的冲激 $\delta(t-\tau)$ 的响应就是 $h(t-\tau)$。系统对强度为 $x(\tau)$ 的延迟冲激 $x(\tau)\delta(t-\tau)$ 的响应就是 $x(\tau)h(t-\tau)$。把所有这些微小的响应全部叠加（积分）起来，就得到了系统最后的总输出 $y(t)$。这个叠加的过程，在数学上就叫做卷积。

根据信号是连续的还是离散的，卷积分为两种形式：

  1. 连续信号的卷积（卷积积分）对于连续时间信号 $x(t)$ 和 $h(t)$，其卷积定义为：

    $$
    y(t) = x(t) * h(t) = \int_{-\infty}^{+\infty} x(\tau)h(t-\tau) d\tau
    $$

  2. 离散信号的卷积（卷积和）对于离散时间信号 $x[n]$ 和 $h[n]$，其卷积分形式转为累加：

    $$
    y[n] = x[n] * h[n] = \sum_{k=-\infty}^{+\infty} x[k]h[n-k]
    $$

Symmetric FIR && DFT

对称有限冲激响应滤波器 和 离散傅里叶变换

Symmetric FIR

  1. FIR（Finite Impulse Response）称为有限冲激响应滤波器。其核心特点是系统的冲激响应 $h(n)$ 只有有限个非零点（长度为 $N$）。其输出 $y(n)$ 仅取决于当前输入、过去输入的加权组合，不依赖过去的输出（无反馈）。其差分方程为：

$$
y(n) = \sum_{k=0}^{N-1} h(k)x(n-k)
$$

  1. 为什么必须“对称”？—— 严格线性相位 (Linear Phase)在语音、通信（如 LTE/5G 基带）、图像处理中，波形畸变是致命的。如果滤波器对不同频率的信号分量产生不同的时间延迟，输出的波形就会发生扭曲。要让滤波器实现严格线性相位（即所有频率成分通过滤波器后，延迟的时间完全相同，群延迟为常数），滤波器的系数（冲激响应）必须满足对称性。根据长度 $N$ 的奇偶性，对称 FIR 分为两种基本形态（加上反对称共四种类型）：

    • 奇数长度对称 (Type I)： 长度 $N$ 为奇数，关于中心点 $h(\frac{N-1}{2})$ 镜像对称。例如 $N=5$：
      $[h_0, h_1, h_2, h_1, h_0]$
    • 偶数长度对称 (Type II)： 长度 $N$ 为偶数，关于中心两个点之间镜像对称。例如 $N=4$：
      $[h_0, h_1, h_1, h_0]$

  2. 硬件实现与乘法器级联优化 (Hardware Optimization)

    1. 对称性在微架构（如 DSP 核心、FPGA MAC 单元）中带来了一个巨大的红利：乘法器数量直接减半。以 $N=5$ 的 Type I 对称 FIR 为例：

    $$
    (n) = h_0 x(n) + h_1 x(n-1) + h_2 x(n-2) + h_1 x(n-3) + h_0 x(n-4)
    $$

    通过提取公因数，可以改写为：

    $$
    (n) = h_0 \cdot [x(n) + x(n-4)] + h_1 \cdot [x(n-1) + x(n-3)] + h_2 \cdot x(n-2)
    $$

    • 传统实现： 需要 5 次乘法，4 次加法。
    • 对称折叠（Folded）实现： 只需要 3 次乘法（系数减半），4 次加法。
    • DSP 实践： 现代 DSP 的乘加单元（MAC）通常带有前置加法器（Pre-Adder）。在单个时钟周期内，硬件先将 $x(n)$ 和 $x(n-4)$ 相加，然后直接送入乘法器与 $h_0$ 相乘。这对于像 BBE32 这种超宽向量流水线来说，意味着在相同吞吐量下，节省了一半的乘法器资源和功耗。

DFT

DFT（Discrete Fourier Transform）是连续傅里叶变换在时域和频域同时离散化后的形式。它是计算机和 DSP 芯片能够直接处理的“唯一”傅里叶变换形式。对于一个长度为 $N$ 的离散信号序列 $x(n)$，其 DFT 定义为：

$$
$$X(k) = \sum_{n=0}^{N-1} x(n) W_N^{kn}, \quad k = 0, 1, \dots, N-1
$$

其中 $W_N = e^{-j\frac{2\pi}{N}}$ 称为旋转因子（Twiddle Factor）。
物理意义： $X(k)$ 反映了数字信号 $x(n)$ 在第 $k$ 个频率基底上的复数幅度（包含模长/能量，以及初始相位）。

旋转因子 $W_N^{kn}$ 的矩阵与正交性如果把 DFT 写成矩阵乘法的形式，它实际上是一个正交矩阵线性变换：

$$
\mathbf{X} = \mathbf{W} \cdot \mathbf{x}
$$

因为 $W_N^{kn} = \cos(\frac{2\pi}{N}kn) - j\sin(\frac{2\pi}{N}kn)$，DFT 的本质就是将时域信号与一组在复平面单位圆上均匀分布的正弦/余弦基波进行内积运算。

DFT 的计算复杂度与 FFT 的引出如果直接按照定义计算一个 $N$ 点的 DFT：

  • 算出每个 $X(k)$ 需要进行 $N$ 次复数乘法和 $N-1$ 次复数加法。
  • 整个序列共有 $N$ 个点，总计算复杂度为 $\mathcal{O}(N^2)$。

当 $N=1024$ 时，$N^2 \approx 10^6$ 次运算，这在实时通信或雷达信号处理中开销过大。利用旋转因子的周期性（$W_N^{k+N} = W_N^k$）和对称性（$W_N^{k+N/2} = -W_N^k$），可以将大点数的 DFT 拆解为多个小点数的变换，这就是快速傅里叶变换（FFT，如 Cooley-Tukey 算法），它将复杂度骤降至 $\mathcal{O}(N \log_2 N)$。