改進的離散餘弦變換

维基百科，自由的百科全书

改進的離散餘弦變換（Modified Discrete Cosine Transform, MDCT）是一種與傅立葉變換相關的變換，以第四型離散餘弦變換（DCT-IV）為基礎，重疊性質如下：它是應用於處理較大的資料集合，當連續的資料區塊中，當前的資料區塊跟後續的資料區塊有重疊到的情形；即當前資料區塊的後半段與下一個資料區塊的前半段為重疊的狀態。這樣的重疊情形，除了具有離散餘弦變換（Discrete Cosine Transform, DCT）的能量壓縮特性外，也使這種變換在應用於信號壓縮時更引人注目。因為它有助於避免由於資料區塊邊界所產生的多餘資料。因此，這種變換可應用於MP3，AC-3， ogg vorbis，和AAC的音頻壓縮等方面。

改進的離散餘弦變換是由Princen，Johnson和Bradley承接早前（1986年）Princen和Bradley所提出關於時域混疊消除法（Time-Domain Aliasing Cancellation, TDAC ）的改進的離散餘弦變換基本定理，於1987年所提出，詳述如下。至於其他類似的變換還有如以離散正弦變換為基礎的改進的離散正弦變換（Modified Discrete Sine Transform, MDST）。以及其他較少使用的變換，例如以其他不同類型的DCT或DCT/DST的組合為基礎的改進的離散餘弦變換。

在MP3的應用上，改進的離散餘弦變換，並不適用於直接處理音頻信號，而適用於處理32波段多相正交濾波器（Polyphase quadrature filter, PQF）陣列的輸出端信號。這樣的改進的離散餘弦變換輸出是由一個混疊削減公式作後置處理，用以減少多相正交濾波器陣列的特殊混疊。這樣的改進的離散餘弦變換與濾波器陣列組合，被稱作混合濾波器陣列或子帶改進的離散餘弦變換。相反地，AAC通常使用一個純粹的改進的離散餘弦變換；僅Sony公司使用的MPEG – 4 AAC - SSR技術採用了運用改進的離散餘弦變換的四波段多相正交濾波器陣列（但也是很少使用）。自適應聽覺變換編碼（Adaptive TRansfeorm Acoustic Coding, ATRAC）利用運用改進的離散餘弦變換的堆疊型正交鏡像濾波器（Quadrature Mirror Filter, QMF）。

[编辑] 定義

作為一個重疊變換，改進的離散餘弦變換，跟其他傅立葉相關的變換比起有些不一樣，因為它的輸出數為輸入數的一半（而非相同）。特別的是，它是一個線性函數F : R^2N -> R^N（其中R 代表實數集合）。根據公式：

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

將2N個實數x₀, ..., x_2N-1變換成N個實數X₀, ..., X_N-1。（在這個變換前面的正規化係數，單位不為一定且根據不同的解釋方法而有所改變。下面只考慮改進的離散餘弦變換跟改進的離散餘弦逆變換的正規化乘積。）

[编辑] 逆變換

改進的離散餘弦逆變換（IMDCT），乍看之下由於輸入數與輸出數並不相同，改進的離散餘弦變換應為不可逆的。然而，透過加入造成錯誤並且必須要回復原始資料的子帶重疊區塊中重疊的改進的離散餘弦逆變換部份，完美的可逆性是可以達成的。這種技術被稱為時域混疊消除法（Time-Domain Aliasing Cancellation, TDAC ）。改進的離散餘弦逆變換根據公式：

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

將N個實數X₀, ..., X_N-1變換成2N個實數y₀, ..., y_2N-1。（如同第四型離散餘弦變換為一正交變換，其逆變換具有與正變換一樣的形式）。具有一般窗式正規化（usual window normalization, 如下所示）的窗式改進的離散餘弦變換（windowed MDCT），其逆變換的正規化係數必須乘2（即變成2/N）。

[编辑] 計算

雖然直接應用改進的離散餘弦變換公式的計算複雜度為O(N²)，但是透過遞迴的將計算分解化有可能將計算複雜度降到O(N log N)，就如同快速傅立葉變換（Fast Fourier Transform, FFT）一樣。另外也可以透過其他變換計算改進的離散餘弦變換。通常一個離散傅立葉變換（或快速傅立葉變換）或是一個離散餘弦變換包含的前置處理跟後置處理的複雜度為O(N)。此外，如下所述，任何第四型離散餘弦變換的演算法都能衍生出一種方法來計算偶數項的改進的離散餘弦變換和改進的離散餘弦逆變換。

[编辑] 窗函數

在一般的信號壓縮應用中，變換特性可透過利用將窗函數（window function）w_n (n = 0, ..., 2N-1)乘以改進的離散餘弦變換中的x_n 及改進的離散餘弦逆變換中的y_n作進一步的改良，為了避免在n = 0 and 2N的邊界點產生不連續並且使函數於這些點可以變得平滑而趨近零（即window the data before the MDCT and after the IMDCT）。原則上，x 和 y可以有不同的窗函數，而窗函數再資料區塊變換時可以改變（尤其是當兩個不同尺寸的資料區塊結合在一起時）。但為簡單起見，我們考慮給相同尺寸的資料區塊應用的窗函數。變換仍然是可逆的（即TDAC依然可以正常作用），考慮一個對稱的窗w_n = w_2N-1-n，只要w滿足Princen-Bradley condition：

$w_n^2 + w_{n + N}^2 = 1$

各種不同應用的窗函數都是一樣的，例如：

$w_n = \sin \left[\frac{\pi}{2N} \left(n+\frac{1}{2}\right) \right]$

為應用於MP3和MPEG - 2的AAC的窗函數，而

$w_n = \sin \left( \frac{\pi}{2} \sin^2 \left[\frac{\pi}{2N} \left(n+\frac{1}{2}\right) \right] \right)$

為Vorbis所應用。此外AC-3與MPEG - 4 AAC均採用了Kaiser-Bessel derived (KBD) window。值得注意的是，應用在改進的離散餘弦變換的窗函數與應用於其他類型的信號分析的窗函數是不同的。因為它們必須滿足Princen – Bradley condition。原因之一，改進的離散餘弦變換應用了兩次窗函數，包括改進的離散餘弦變換（分析）和改進的離散餘弦逆變換（合成）。

[编辑] 第四型離散餘弦變換與原始TDAC的關係

由定義可以看出，一個偶數點N的改進的離散餘弦變換基本上就相當於一個輸入位移了N/2且兩個N點資料區塊同時變換的第四型離散餘弦變換。而再更進一步的檢視這個等效關係，則重要的特性例如TDAC可以很容易地推導出來。為了更明確的定義與第四型離散餘弦變換的關係，我們必須了解第四型離散餘弦變換分別對應到偶數點跟奇數點的邊界條件：偶數點在左邊邊界，（約在n=–1/2 ），奇數點在右邊邊界（約在n=N–1/2 ）諸如此類（而不是DFT那樣的週期性邊界）。這些遵從以下所述：

$\cos\left[\frac{\pi}{N} \left(-n-1+\frac{1}{2}\right) \left(k+\frac{1}{2}\right)\right] = \cos\left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) \left(k+\frac{1}{2}\right)\right]$

和

$\cos\left[\frac{\pi}{N} \left(2N-n-1+\frac{1}{2}\right) \left(k+\frac{1}{2}\right)\right] = -\cos\left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) \left(k+\frac{1}{2}\right)\right]$

因此，如果輸入為一組長度為N的x陣列，我們可以想見這個陣列會擴增至(x, –x_R, –x, x_R, ...)，其中x_R代表x的反向序列。考慮一個有2N個輸入與N個輸出的改進的離散餘弦變換。我們將輸入分成4組區塊(a, b, c, d)，每組大小為N/2。如果我們把這些資料位移N/2（即改進的離散餘弦變換的定義中的+N/2項），然後(b, c, d)擴增到N點第四型離散餘弦變換的輸入結尾。因此，我們必須將這些資料根據上述邊界條件“疊”（“fold”）回來。是故，一個具有2N點輸入(a, b, c, d)的改進的離散餘弦變換，就確實的相當於一個具有N點輸入(–c_R–d, a–b_R)的第四型離散餘弦變換，其中R的意義與前述相同。（以這種方式，任何用來計算第四型離散餘弦變換的演算法都可以很直觀的套用在改進的離散餘弦變換上）。同樣地，上述改進的離散餘弦逆變換公式恰好正是第四型離散餘弦變換的1/2，其中輸出位移了N/2且擴增長度為2N（透過邊界條件）。而第四型離散餘弦逆變換可以簡單的給定如上述之輸入(–c_R–d, a–b_R)。當透過邊界條件完成位移跟擴增的動作後，我們可以得到：

IMDCT(MDCT(a, b, c, d)) = (a–b_R, b–a_R, c+d_R, c_R+d) / 2

（因此有一半的改進的離散餘弦逆變換輸出是多餘的。）

我們現在明白了TDAC的運作原理。考慮計算一個改進的離散餘弦變換的子帶，有50％的重疊，2N個資料區塊(c, d, e, f)。則得到的改進的離散餘弦逆變換會跟上述類似：(c–d_R, d–c_R, e+f_R, e_R+f) / 2。當加入這些到先前由重疊到一半所產生的改進的離散餘弦逆變換時，反向的項被消除了，並獲得一簡單的已回復的原始資料(c, d)。

[编辑] TDAC的起源

”時間域混疊消除法”的起源現在很清楚了。邏輯上第四型離散餘弦變換中根據邊界條件所擴增的輸入資料造成資料發生混疊的現象，正如同頻譜中奈奎斯特頻率（Nyquist frequency）會與較低的頻率發生混疊一樣。因此，當c–d_R及其他被加進來會有準確的符號（right sign）提供作消除之用。對於奇數點 N （事實上很少使用），N/2不是整數，所以改進的離散餘弦變換並不是由第四型離散餘弦變換透過一個簡單的位移就可以互相對應。在這種情況下，額外的位移一半的樣本，代表著改進的離散餘弦變換/改進的離散餘弦逆變換等同於第三/二型離散餘弦變換，其分析類似上述。

[编辑] 窗式改進的離散餘弦變換的TDAC

如上所述，TDAC性質已被證明適用於普通改進的離散餘弦變換，顯示加入子帶資料區塊的改進的離散餘弦逆變換於重疊的一半部份可回復原始的資料。推導這項窗式改進的離散餘弦變換逆性質較上述稍微複雜一些，敘述如下。根據前述當 $(a, b, c, d)$ 和 $(c, d, e, f)$ 經過改進的離散餘弦變換與改進的離散餘弦逆變換，並且加上其重疊一半時，我們得到 $(c + d R, c R + d) / 2 + (c - d R, d - c R) / 2 = (c, d)$ ，即原始的資料。現在我們假設我們將改進的離散餘弦變換的輸入和改進的離散餘弦逆變換的輸出兩者均乘上一個長度為2N的窗函數。如前所述，我們假設一個對稱的窗函數其形式為 $(w, z, z R, w R)$ 其中w 跟 z 是長度N/2的向量，而R代表反向。如此則Princen – Bradley condition可以寫成： $w^2 + z_R^2 = (1,1,\ldots)$ ，其中乘法和加法為點對點的運算，或等效成 $w_R^2 + z^2 = (1,1,\ldots)$ （將w 跟 z反向）。因此，我們對 $(w a, z b, z R c, w R d)$ 作改進的離散餘弦變換取代對 $(a, b, c, d)$ 作改進的離散餘弦變換（所有的乘法跟加法均為點對點）。當完成改進的離散餘弦逆變換再乘以窗函數（點對點相乘），最後N點的一半，成為：

$(z_R, w_R) \cdot (z_R c+w d_R, z c_R + w_R d) = (z_R^2 c+wz_R d_R, w_R z c_R + w_R^2 d)$

（請注意，我們不再乘1/2，因為改進的離散餘弦逆變換的正規化與窗式的例子中的因數2有所不同）。同樣的，對於產生 $(c, d, e, f)$ 的窗式改進的離散餘弦變換和窗式改進的離散餘弦逆變換，是在其前N點的一半：

$(w,z) \cdot (w c - z_R d_R, z d - w_R c_R) = (w^2 c - w z_R d_R, z^2 d - w_R z c_R)$

當我們這兩個各半的結果加總起來，我們得到：

$(z_R^2 c+wz_R d_R, w_R z c_R + w_R^2 d) + (w^2 c - w z_R d_R, z^2 d - w_R z c_R)$

$= \left( [z_R^2 + w^2] c + [wz_R - wz_R] d_R, [ w_R^2 + z^2] d + [w_R z - w_R z] c_R \right) = (c, d)$

即回復的原始資料。

[编辑] 參考

Henrique S. Malvar, Signal Processing with Lapped Transforms (Artech House: Norwood MA, 1992).

John P. Princen and Alan B. Bradley, "Analysis/synthesis filter bank design based on time domain aliasing cancellation," IEEE Trans. Acoust. Speech Sig. Proc. ASSP-34 (5), 1153-1161 (1986). (Described a precursor to the MDCT using a combination of discrete cosine and sine transforms.)

J. P. Princen and A. W. Johnson and A. B. Bradley, "Subband/transform coding using filter bank designs based on time domain aliasing cancellation," IEEE Proc. Intl. Conf. on Acoustics, Speech, and Signal Processing (ICASSP) 12, 2161-2164 (1987). (Initial description of what is now called the MDCT.)

A. W. Johnson and A. B. Bradley, "Adaptive transform coding incorporating time domain aliasing cancellation," Speech Comm. 6, 299-308 (1987).

For algorithms, see e.g.:
- Chi-Min Liu and Wen-Chieh Lee, "A unified fast algorithm for cosine modulated filterbanks in current audio standards", J. Audio Engineering 47 (12), 1061-1075 (1999).
- V. Britanak and K. R. Rao, "A new fast algorithm for the unified forward and inverse MDCT/MDST computation," Signal Processing 82, 433-459 (2002)
- Vladimir Nikolajevic and Gerhard Fettweis, "Computation of forward and inverse MDCT using Clenshaw's recurrence formula," IEEE Trans. Sig. Proc. 51 (5), 1439-1444 (2003)
- Che-Hong Chen, Bin-Da Liu, and Jar-Ferr Yang, "Recursive architectures for realizing modified discrete cosine transform and its inverse," IEEE Trans. Circuits Syst. II: Analog Dig. Sig. Proc. 50 (1), 38-45 (2003)
- ...and references thereof.

zh-hans:;zh-hant:zh-hans:查;zh-hant:檢 • zh-hans:;zh-hant:論 • zh-hans:;zh-hant:編 • zh-hans:;zh-hant:歷

数据压缩方法

无损数据压缩

理论	熵 · 复杂性 · 信息冗余
熵編碼法	哈夫曼树 · 算术编码（Shannon-Fano · 区间） · Golomb · Exp-Golomb · 统一编码（Elias · Fibonacci） · Asymmetric binary
字典编码	RLE · LZ77/78 · LZSS · LZW · LZWL · LZO · DEFLATE · LZMA · LZX · LZJB
其他	CTW · BWT · PPM · DMC

音频压缩

理论	卷积 · 采样 · 采样定理
音频编解码器	LPC · WLPC · CELP · ACELP · A-law · μ-law · MDCT · 傅里叶变换 · 音响心理学
其他	动态范围压缩 · 语音编码 · 子带编码

图像压缩

条件	色彩空間 · 像素 · 色度抽样 · Compression artifact
方法	RLE · 分形压缩 · 小波压缩 · SPIHT · DCT · KLT
其他	比特率 · 标准测试图像 · 峰值信噪比

视频压缩

条件	視訊特性 · Frame · 視訊類型 · 視訊質量
视频编解码器	运动补偿 · DCT · 量化
其他	率失真理论（CBR · ABR · VBR）

分类: 傅里叶分析

See also ebooksgratis.com: no banners, no cookies, totally FREE.