離散正弦變換

離散正弦變換（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).