离散正弦变换

离散正弦变换（Discrete Sine Transform，缩写：DST）是一类与离散傅立叶变换（DFT）密切相关的正交积分变换，属于傅立叶相关变换（Fourier-related transforms）家族之一。DST 将有限长度的实数序列表示为一组正弦基底函数的线性组合，因此其变换矩阵仅包含实数元素。从数学上来看，DST 可视为对具有特定奇对称延拓之离散讯号所进行的离散傅立叶变换，其结果对应于傅立叶频谱中的虚数部分。

由于正弦函数天然满足零值边界条件，因此 DST 特别适合处理具有狄利克雷边界条件（Dirichlet boundary condition）的问题。在有限差分法与谱方法中，DST 能够将离散拉普拉斯算子对角化，进而将大型联立方程组转换为彼此独立的代数方程式，大幅降低计算成本。

与 DST 对应的变换为离散余弦变换（DCT）。两者皆可视为离散傅立叶变换在不同对称延拓条件下的实数表示形式，其中 DCT 建立于偶对称延拓，而 DST 则建立于奇对称延拓。因此，DCT 通常对应于纽曼边界条件（Neumann boundary condition），而 DST 则对应于狄利克雷边界条件。由于不同边界条件会影响讯号的能量分布与压缩效率，因此两者在讯号处理与资料压缩领域具有互补的应用特性。

依据输入与输出端是否进行半取样（half-sample）位移，以及奇对称边界的位置不同，DST 可进一步分为八种标准型态，通常记为 DST-I 至 DST-VIII。

## 定义

形式上，离散正弦变换是一个线性的可逆函数$F:R^N\rightarrow R^N$，其中R为实数集，或等价的说是一个$N \times N$ 方阵。离散正弦变换有几种稍微不同定义的变形，皆根据以下公式之一把$N$个实数$x_0,\ldots ,x_{N-1}$变换到另$N$个实数$X_0,\ldots ,X_{N-1}$。

### DST-I

$$X_k = \sum_{n=0}^{N-1} x_n \sin \left[\frac{\pi}{N+1} (n+1) (k+1) \right] \quad \quad k = 0, \dots, N-1$$

一个DST-I矩阵为正交矩阵（差一个系数）。

$N=3$的实数abc的DST-I变换等价于8点实数0abc0(-c)(-b)(-a)（奇对称）的DFT转换，再除2（而DST-II~DST-IV等价于DFT有半个取样的位移）。

因而DST-I对应的边界条件是：$x_n$对$n = -1$奇对称，也对$n = N$奇对称；$X_k$也类似。

### DST-II

$$X_k = <pre> \sum_{n=0}^{N-1} x_n \sin \left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) (k+1)\right] \quad \quad k = 0, \dots, N-1$$

### DST-III

$$X_k = \frac{(-1)^k}{2} x_{N-1} + <pre> \sum_{n=0}^{N-2} x_n \sin \left[\frac{\pi}{N} (n+1) \left(k+\frac{1}{2}\right) \right] \quad \quad k = 0, \dots, N-1$$

### DST-IV

$$X_k = <pre> \sum_{n=0}^{N-1} x_n \sin \left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) \left(k+\frac{1}{2}\right) \right] \quad \quad k = 0, \dots, N-1$$

一个DST-IV矩阵为正交矩阵（差一个系数）。

### DST-V 至 VIII

离散正弦变换的 V 至 VIII 型态相较于 I 至 IV 型态较为少见，其变换的特征在于对空间域或频率域（或两者同时）进行了半个取样单位的平移。这些变型常被视为广义上的重叠变换，并且在特定的讯号处理或边界条件推导中具有严格的对称性。

#### DST-V

$$X_k = \sum_{n=0}^{N-1} x_n \sin\left[ \frac{\pi}{N + \frac{1}{2}} (n + 1)(k + 1) \right], k = 0, 1, \dots, N-1$$

#### DST-VI

$$X_k = \sum_{n=0}^{N-1} x_n \sin\left[ \frac{\pi}{N + \frac{1}{2}} \left(n + \frac{1}{2}\right)(k + 1) \right], k = 0, 1, \dots, N-1$$

#### DST-VII

$$X_k = \sum_{n=0}^{N-1} x_n \sin\left[ \frac{\pi}{N + \frac{1}{2}} (n + 1)\left(k + \frac{1}{2}\right) \right], k = 0, 1, \dots, N-1$$

#### DST-VIII

$$X_k = \sum_{n=0}^{N-1} x_n \sin\left[ \frac{\pi}{N - \frac{1}{2}} \left(n + \frac{1}{2}\right)\left(k + \frac{1}{2}\right) \right], k = 0, 1, \dots, N-1$$

## 反变换

DST-I的反变换是把DST-I乘以$\frac{2}{N+1}$。

DST-IV的反变换是把DST-IV乘以$\frac{2}{N}$。

DST-II的反变换是把DST-III乘以$\frac{2}{N}$，反之亦然。

类似离散傅立叶变换，这些定义前面的归一系数只是习惯，不同人有不同定义。例如有人在变换前面乘$\sqrt{\frac{2}{N}}$，使反变换和变换在形式上更相似，而不需另外的归一系数。

## 快速算法

如同离散傅立叶变换拥有快速傅立叶变换（FFT）一样，离散正弦变换也具有对应的快速正弦变换（Fast Sine Transform, FST）算法。若直接根据定义计算长度为 $N$ 的 DST 序列，其时间复杂度为 $O(N^2)$。然而，透过 FST 算法，可以将计算复杂度大幅降低至 $O(N \log N)$。在实务与理论上，FST 主要有两种实现途径：

### 基于快速傅立叶变换的扩展法（间接计算）

这是科学计算软件（如 SciPy 或 MATLAB）中最常见的实作方式。其核心是把 DST 转换为离散傅立叶变换（DFT）来计算。由于正弦函数是奇函数，可以将原始的实数序列透过特定的奇对称规则进行边界扩展。

例如，在计算长度 $N$ 的 DST-I 时，可将序列扩展为长度 $2N+2$ 的全序列，并将扩展部分补上奇对称的值及零。接着，对这个扩充后的序列执行标准的 FFT 计算，最后再从频域结果的虚部中截取所求的 DST 系数。这种方法的优点是能直接受益于现有且高度最佳化的 FFT 函式库（例如 FFTW），但缺点是需要额外的内存来储存扩展后的序列，且即使经过实数 FFT（Real-FFT）的最佳化，仍可能牵涉不必要的计算开销。

### 原生快速正弦递回算法（直接计算）

为了克服扩展法的缺点，学者们从 DST 的数学定义出发，推导出专用的快速算法。例如 A. Gupta 与 K. R. Rao 于 1990 年提出了一种针对 DST 的快速递回算法。这种算法利用三角函数的恒等式将长度为 $N$ 的变换递回拆解为长度 $N/2$ 的变换。

这种原生算法具有以下显著优势：

- 不需扩展序列：输入与输出的资料长度皆维持为 $N$。
- 仅使用实数运算：运算过程完全在实数域进行，彻底避开了复数运算。
- 适合硬件实作：该算法推导出了类似 Cooley-Tukey FFT 的蝴蝶图结构，大幅减少了乘法器与加法器的使用数量，适合应用于超大型积体电路的硬件芯片设计。

## 与离散余弦变换的比较

离散正弦变换与离散余弦变换皆可视为离散傅立叶变换在特定对称延拓条件下的实数形式，因此在计算架构与快速算法上具有高度相似性。

两者最根本的差异来自于其隐含的边界条件与对称性假设。DCT 的基底函数建立于偶对称延拓之上，可对应至纽曼边界条件，即讯号在边界处的一阶导数为零。相对地，DST 则基于奇对称延拓，其数学模型对应于狄利克雷边界条件，亦即讯号在边界处的函数值趋近于零。

由于边界条件不同，两者在能量集中能力上的表现亦有所差异。对于自然影像、语音讯号等具有高度相邻相关性的平滑讯号，DCT 能够将大部分能量集中于少数低频系数，因此成为影像与视讯压缩领域最重要的变换工具之一。然而，对于边界附近快速衰减的讯号，或经预测编码产生的残差讯号，由于其边界值通常接近零，因此更符合 DST 的奇对称假设。在此情况下，DST 往往能获得比 DCT 更佳的能量集中效果。相较之下，DST 早期主要用于偏微分方程数值求解及科学计算，其不同变体可对应不同的边界条件。

随着高效率视讯编码技术的发展，现代编码标准引入复杂的区块内预测机制，使得预测残差在边界附近常呈现接近零的特性。基于此原因，DST 开始被纳入视讯编码标准中。在现代视讯压缩系统中，DCT 仍然适合处理平滑且高相关性的讯号，而 DST 则更适合表示具有零边界特性的预测残差。

## 应用领域

### 偏微分方程的数值求解

在科学计算与数值分析领域，DST 是求解具有特定边界条件的偏微分方程（如泊松方程、热传导方程或波动方程）的核心工具。当微分方程的定义域两端受到狄利克雷边界条件（Dirichlet boundary conditions）（即函数在边界上的值被固定为零或特定常数）约束时，二阶连续微分算子（$\nabla^2$）或其对应的离散有限差分矩阵，在正弦基底下会自然地被对角化。

透过FST，可以将原本在空间域中高度耦合的微分方程组转换到正弦频域中成为一组互相独立的线性代数方程式。这种解法将大尺度物理模拟（如流体力学中的压力泊松求解器）的计算时间大幅缩短。

### 新一代视讯编码标准

在早期的影像压缩标准（如 JPEG 和 MPEG-2）中，由于一般影像区块的统计特性较符合偶对称边界，DCT 几乎被独占使用。然而，在现代高效率视讯编码标准（如 HEVC/H.265、VVC/H.266 以及开源的 AV1）中，DST成为了不可或缺的关键技术。

这是因为现代视讯编码广泛使用利用区块边界上已解码的像素来预测当前区块的内容。这种预测方式产生的残差讯号在靠近参考边界处的误差通常极小，而距离边界越远的误差越大。这种讯号特性契合 DST-VII 的正弦基底函数波形。将 DST-VII 应用于影像编码的残差区块，其能量集中度显著优于传统的 DCT，从而大幅提升了压缩效率。

### 音讯讯号处理与频谱分析

在音讯处理中，DST 通常以改良式离散正弦变换（Modified Discrete Sine Transform, MDST）的形式出现。MDST 与广为人知的改良式离散余弦变换（MDCT）同属基于时域混叠消除（Time-Domain Aliasing Cancellation, TDAC）原理的滤波器组，两者可组合为复数频域表示，以提取完整的相位资讯。

MDCT 和 MDST 的结合能够在时频分析中提供完整的相位资讯，并实现时域混叠消除的特性。这使得 DST 在进阶的音频特效处理、音讯特征提取（如频谱包络与瞬态侦测）以及部分的音讯浮水印技术中，成为重建精确讯号的重要辅助工具。

## 参考资料

- S. A. Martucci, "Symmetric convolution and the discrete sine and cosine transforms," IEEE Trans. Sig. Processing SP-42, 1038-1051 (1994).
- Matteo Frigo and Steven G. Johnson: FFTW, http://www.fftw.org/ . A free (GPL) C library that can compute fast DSTs (types I-IV) in one or more dimensions, of arbitrary size. Also M. Frigo and S. G. Johnson, "The Design and Implementation of FFTW3," Proceedings of the IEEE 93 (2), 216–231 (2005).