3.5 Sub-optimum orthogonal transforms

An introduction to source-coding Page 1 / 1

The KLT, which is the optimal orthogonal transform for transform coding, requires knowledge of the source statistics that may be unavailable in practice, and eigendecomposition that may be too expensive in practice. This motivates the consideration of other orthogonal transforms, like the DFT, DCT, and DHT. Here we discuss these and analyze the resulting performance when possible. In addition, we discuss practical matters like real-valued DFTs and fast DCT implementations.

Goal: Recall that the goal of the optimal orthogonal transform was tominimize the ratio of geometric to arithmetic output variances:
$\begin{matrix} \frac{{(\prod_{k = 0}^{N - 1}, σ_{y_{k}}^{2})}^{1 / N}}{\frac{1}{N} \sum_{k = 0}^{N - 1} σ_{y_{k}}^{2}} . \end{matrix}$
The ratio [link] attains its maximum value ( $= 1$ ) when $σ_{y_{k}}^{2}$ are equal for all k and takes on much smaller values when the difference between the $σ_{y_{k}}^{2}$ (sometimes called the dynamic range of ${σ_{y_{k}}^{2}}$ ) is large.
Problem with KLT: The KLT, i.e., the orthogonal transform minimizing [link] , is a function of the input signal statistics.Specifically, the KLT equals the eigenvector matrix of the input autocorrelation matrix.Unfortunately, realistic signals are non-stationary, requiring continual KLT redesign if optimality is to be preserved, andeigenvector computation is computationally intensive, especially for large N . Thus, the question becomes: Are there fixed orthogonal transforms that do a good job of minimizing the ratio [link] for “typical” input signals? As we will see, the answer is yes...
DFT Intuitions: For the sake of intuition, lets first consider choosing T as an orthogonal DFT matrix.In this case, the coefficient variances ${σ_{y_{k}}^{2}}$ would be samples of the power spectrum and the dynamic range of ${σ_{y_{k}}^{2}}$ would be determined by the relative input power in different frequency bands.Recalling that asymptotic TC ( $N \to \infty$ ) performance is determined by ${SFM}_{x}$ , which has the same geometric-to-arithmetic-average structure as [link] :
${SFM}_{x} = \frac{exp (\frac{1}{2 π} \int_{- π}^{π} ln S_{x} (e^{j ω}) d ω)}{\frac{1}{2 π} \int_{- π}^{π} S_{x} (e^{j ω}) d ω} = lim_{N \to \infty} {(\frac{{(\prod_{k = 0}^{N - 1}, S, (e^{j ω_{k}}))}^{1 / N}}{\frac{1}{N} \sum_{k = 0}^{N - 1} S (e^{j ω_{k}})}|}_{ω_{k} = 2 π k / N},$
we might intuit that the DFT is optimal as $N \to \infty$ . The asymptotic optimality of the DFT can, in fact, be proven(see Jayant&Noll). Of course, we don't have much reason to expect that the DFT wouldbe optimal for finite transform dimension N . Still, for many signals, it performs well.(See [link] .)
Other Transforms: The most commonly used orthogonal transform in speech, image, audio,and video coding is the discrete cosine transform (DCT). The excellent performance of the DCT follows from the fact that it isespecially suited to “lowpass” signals, a feature shared by most signals in the previously mentioned applications.Note that there are plenty of signals for which the DCT performs poorly—it just so happens that such signals are not frequentlyencountered in speech, image, audio, or video. We will describe the DCT and provide intuition regarding it's good“lowpass” performance shortly. Like the DFT, the DCT has fast algorithms which make it extremelypractical from an implementation standpoint. Another reasonably popular orthogonal transform, requiring even lessin the way of computation, is the discrete Hadamard transform (DHT), also described below. [link] compares DFT, DCT, DHT, and KLT for various transform lengths N along with asymptotic TC performance. [link] (a) shows gain over PCM when using a lowpass autoregressive (AR) source ${x (n)}$ generated from white Gaussian noise ${v (n)}$ via:
$X (z) = \frac{1}{1 - 0.8 z^{- 1}} V (z),$
while [link] (b) shows the gain for highpass ${x (n)}$ :
$X (z) = \frac{1}{1 + 0.8 z^{- 1}} V (z) .$
See [link] for the power spectra of these two processes.

$G_{TC, N}$ for various transforms and various N on an AR(1) lowpass (left) and highpass (right) sources.

Power spectra of AR(1) sources used in the transform matrix comparisons of [link] .
The DHT: The $N \times N$ DHT is defined below for power-of-two N :
$\begin{matrix} H_{2} = \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}) H_{2 N} = \frac{1}{\sqrt{2}} (\begin{matrix} H_{N} & H_{N} \\ H_{N} & - H_{N} \end{matrix}) \end{matrix}$
Note that H _N is orthogonal Caution: outputs of the Matlab command hadamard must be scaled by $1 / \sqrt{N}$ to produce orthogonal DHT matrices! , i.e., $H_{N} H_{N}^{t} = I$ . As an example
$H_{4} = \frac{1}{2} (\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & - 1 & 1 & - 1 \\ 1 & 1 & - 1 & - 1 \\ 1 & - 1 & - 1 & 1 \end{matrix})$
[link] illustrates DHT basis vectors for the case $N = 8$ . The primary advantage of the DHT is that its implementationcan be accomplished very efficiently. [link] suggests that the DHT performs nearly as well as the KLT for $N = 2$ and 4, but its performance falls well short of optimal for larger N .

$8 \times 8$ DHT basis vectors.
The DFT: The normalized Due to the norm-preserving scale factor $1 / \sqrt{N}$ , the DFT definitions above differ from those given in most digitalsignal processing textbooks. DFT from ${x_{n}}$ to ${y_{k}}$ is defined below along with its inverse.
$\begin{matrix} y_{k} & = & \frac{1}{\sqrt{N}} \sum_{n = 0}^{N - 1} x_{n} e^{- j \frac{2 π}{N} k n}; k = 0 \dots N - 1, \\ x_{n} & = & \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} y_{k} e^{j \frac{2 π}{N} k n}; n = 0 \dots N - 1 . \end{matrix}$
The normalized DFT can be represented by a symmetric unitary Outputs of the Matlab command dftmtx must be scaled by $1 / \sqrt{N}$ to produce unitary DFT matrices. matrix $W_{N}$ :
$\begin{matrix} {[W_{N}]}_{k, n} = \frac{1}{\sqrt{N}} e^{- j \frac{2 π}{N} k n}; k, n = 0 \dots N - 1 . \end{matrix}$
By unitary, we mean that $W_{N} W_{N}^{* t} = I$ , where ${(\cdot)}^{*}$ denotes complex conjugation. Note that a unitary matrix is the complex-valued equivalentof an orthogonal matrix. In practice, the $N \times N$ DFT is implemented using the fast Fourier transform (FFT), which requires $\approx \frac{N}{2} {log}_{2} N$ complex multiply/adds when N is a power of two.
The Real-Valued DFT: Since we assume real-valued x _n , complex-valued DFT outputs y _k might seem problematic since transmitting both real and imaginary components would decrease our transmission efficiency.For a real-valued DFT input, however, the DFT outputs exhibit conjugate symmetry which allows us to represent the N complex valued outputs with only N real-valued numbers. More precisely, real-valued DFT input { x n } implies that DFT output { y k } has the property
$y_{k} = y_{N - k}^{*}, k = 1, 2, \dots, N / 2,$
which implies
$\begin{matrix} Re {y_{k}} & = & Re {y_{N - k}} k = 1, 2, \dots, N / 2, \\ Im {y_{k}} & = & - Im {y_{N - k}} k = 1, 2, \dots, N / 2, \\ Im {y_{0}} & = & Im {y_{N / 2}} = 0 . \end{matrix}$
A good method by which to select non-redundant components of the DFT output is:
1. Compute complex-valued ${y_{k}}$ using the standard DFT.
2. Construct real-valued ${y_{k}^{'}}$ from ${y_{k}}$ as follows:
  $\begin{matrix} y_{0}^{'} & = & y_{0} (\in R) \\ y_{1}^{'} & = & \sqrt{2} Im {y_{1}} \\ y_{2}^{'} & = & \sqrt{2} Re {y_{1}} \\ ⋮ \\ y_{N - 3}^{'} & = & \sqrt{2} Im {y_{N / 2 - 1}} \\ y_{N - 2}^{'} & = & \sqrt{2} Re {y_{N / 2 - 1}} \\ y_{N - 1}^{'} & = & y_{N / 2} (\in R) . \end{matrix}$
The method above is convenient because (i) it preserves the frequency ordering of the DFT and (ii) it preserves the norm of theDFT output vector, i.e., ∥ y ' ∥ = ∥ y ∥ . Using the conjugate symmetry property of DFT outputs, we canwrite the transformation from { y k } from { y k ' } as a matrix operation U N :
$\begin{matrix} y^{'} = \underset{U_{N}}{\underset{︸}{(\begin{matrix} 1 & 0 & 0 & 0 & \dots & \dots & 0 & 0 & 0 \\ 0 & - j / \sqrt{2} & 0 & 0 & \dots & \dots & 0 & 0 & j / \sqrt{2} \\ 0 & 1 / \sqrt{2} & 0 & 0 & \dots & \dots & 0 & 0 & 1 / \sqrt{2} \\ 0 & 0 & - j / \sqrt{2} & 0 & \dots & \dots & 0 & j / \sqrt{2} & 0 \\ 0 & 0 & 1 / \sqrt{2} & 0 & \dots & \dots & 0 & 1 / \sqrt{2} & 0 \\ ⋮ & ⋮ \\ 0 & \dots & 0 & - j / \sqrt{2} & 0 & j / \sqrt{2} & 0 & \dots & 0 \\ 0 & \dots & 0 & 1 / \sqrt{2} & 0 & 1 / \sqrt{2} & 0 & \dots & 0 \\ 0 & \dots & 0 & 0 & 1 & 0 & 0 & \dots & 0 \end{matrix})}} \underset{y}{\underset{︸}{(\begin{matrix} Re {y_{0}} \\ Re {y_{1}} + j Im {y_{1}} \\ Re {y_{2}} + j Im {y_{2}} \\ ⋮ \\ Re {y_{N / 2 - 1}} + j Im {y_{N / 2 - 1}} \\ Re {y_{N / 2}} \\ Re {y_{N / 2 - 1}} - j Im {y_{N / 2 - 1}} \\ ⋮ \\ Re {y_{2}} - j Im {y_{2}} \\ Re {y_{1}} - j Im {y_{1}} \end{matrix})}} \end{matrix}$
The normalization feature guarantees that U N is unitary (which is easily checked by inspection).Then U N W N , the product of two unitary matrices, is also unitary.Since U N W N is actually real-valued (since it takes any real-valued x to a real-valued y ^' ) it should be referred to as orthogonal rather than unitary.Henceforth we rename U N W N the real-valued DFT matrix W N r
$W_{N}^{r} := U_{N} W_{N} .$
It is easily checked that the basis vectors of W N r are sampled sines and cosines at the uniformly spaced frequencies { 2 π k / N ; k = 0 , ⋯ , N / 2 } . [link] gives an illustration of the real-valued DFT basis vectors for the case N = 8 .

$8 \times 8$ Real-valued DFT basis vectors.

[dft and real-valued dft for $N = 4$ ]

$W_{4} = \frac{1}{2} (\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & - j & - 1 & j \\ 1 & - 1 & 1 & - 1 \\ 1 & j & - 1 & - j \end{matrix}), x = (\begin{matrix} 3 \\ - 1 \\ 4 \\ 2 \end{matrix}), W_{4} x = (\begin{matrix} 4 \\ - 1 / 2 + j 3 / 2 \\ 3 \\ - 1 / 2 - j 3 / 2 \end{matrix}) .$

$W_{4}^{r} = \frac{1}{2} (\begin{matrix} 1 & 1 & 1 & 1 \\ 0 & - \sqrt{2} & 0 & \sqrt{2} \\ \sqrt{2} & 0 & - \sqrt{2} & 0 \\ 1 & - 1 & 1 & - 1 \end{matrix}), x = (\begin{matrix} 3 \\ - 1 \\ 4 \\ 2 \end{matrix}), W_{4}^{r} x = (\begin{matrix} 4 \\ 3 / \sqrt{2} \\ - 1 / \sqrt{2} \\ 3 \end{matrix}) .$

Recall that when N is a power of 2, an N -dimensional complex-valued FFT requires ≈ N 2 log 2 N complex multiply/adds. When the input is real, however, an N -dimensional FFT may be computed using ≈ N log 2 N real multiply/adds (see Sorensen&Jones&Heideman&Burrus TASSP 87).
The DCT: The DCT is defined below along with its inverse
$\begin{matrix} y_{k} & = & \sqrt{\frac{2}{N}} α_{k} \sum_{n = 0}^{N - 1} x_{n} cos \frac{(2 n + 1) k π}{2 N}; k = 0 \dots N - 1, \\ for α_{0} = 1 / \sqrt{2}, α_{k \neq 0} = 1, \\ x_{n} & = & \sqrt{\frac{2}{N}} \sum_{k = 0}^{N - 1} α_{k} y_{k} cos \frac{(2 n + 1) k π}{2 N}; n = 0 \dots N - 1, \end{matrix}$
The DCT can be represented by an orthogonal matrix $C_{N}$ :
$\begin{matrix} {[C_{N}]}_{k, n} = \sqrt{\frac{2}{N}} α_{k} cos \frac{(2 n + 1) k π}{2 N}; k, n = 0 \dots N - 1 . \end{matrix}$
See [link] for an illustration of DCT basis vectors when $N = 8$ .

$8 \times 8$ DCT basis vectors.
A Fast DCT: There are a number of fast algorithms to compute the DCT.The method presented below is based on the FFT and leads to intuition concerning the good “lowpass” performance of the DCT.
1. Create a $2 N$ -length mirrored version of N -length ${x_{n}}$ (see [link] (c)):
  ${\bar{x}}_{n} = \{\begin{matrix} x_{n} & n = 0, 1, \dots, N - 1, \\ x_{2 N - 1 - n} & n = N, N + 1, \dots, 2 N - 1 . \end{matrix})$
2. Compute ${{\bar{y}}_{k}}$ , the $2 N$ -point DFT of ${{\bar{x}}_{n}}$ :
  ${\bar{y}}_{k} = \frac{1}{\sqrt{2 N}} \sum_{n = 0}^{2 N - 1} {\bar{x}}_{n} e^{- j \frac{2 π}{2 N} k n} = \sqrt{\frac{2}{N}} e^{j \frac{π}{2 N} k} \sum_{n = 0}^{N - 1} x_{n} cos \frac{(2 n + 1) k π}{2 N} .$
3. Compute ${y_{k}}$ , the N -point DCT outputs, from ${{\bar{y}}_{k}}$ :
  $y_{k} = e^{- j \frac{π}{2 N} k} α_{k} {\bar{y}}_{k}; k = 0, 1, \dots, N - 1 .$
Assuming a real-valued input, the scheme outlined above can be implemented using
$\approx 2 N + 2 N {log}_{2} \frac{2 N}{2} = 2 N (1 + {log}_{2} N) real-valued multiply/adds$
where we are assuming use of the real-FFT described previously.
DCT vs. DFT Performance for Lowpass Signals: [link] suggests that DCT and DFT performance both equal KLT performance asymptotically, i.e., as transform dimension $N \to \infty$ . Indeed, this can be proven (see Jayant&Noll). A more practical question is: How do DCT and DFT performances comparefor finite N ? To answer this question, we will investigate the effects of input datablock length on the DCT and DFT. To start, consider the DFT of an N -length input block ${x_{0}, \dots, x_{N - 1}}$ :
$y_{k} = \frac{1}{\sqrt{N}} \sum_{n = 0}^{N - 1} x_{n} e^{- j \frac{2 π}{N} k n}; k = 0 \dots N - 1 .$
It can be seen that the DFT outputs ${X_{0}, \dots, X_{N - 1}}$ are samples of the discrete-time Fourier transform (DTFT) at frequencies ${ω_{k} = \frac{2 π}{N} k; k = 0 \dots N - 1}$ :
$X (ω) = \frac{1}{\sqrt{N}} \sum_{n = 0}^{N - 1} x_{n} e^{- j ω n}, y_{k} = X (\frac{2 π}{N} k) .$
Now lets consider a periodic extension of ${x_{0}, \dots, x_{N - 1}}$ which repeats this N -length sequence a total of L times:
$x_{n}^{'} = \{\begin{matrix} \frac{1}{\sqrt{L}} x_{{⟨ n ⟩}_{N}} & - \frac{N L}{2} \leq n < \frac{N L}{2} \\ 0 & else . \end{matrix})$
Above, ${⟨ n ⟩}_{N}$ denotes “ $n modulo N$ ” and L is assumed even (see [link] (a)-(b)). Here is the interesting point: the DTFT of the $N L$ -length periodic extension equals the DTFT of the original N -length data block when sampled at the frequencies ${ω_{k}}$ !
$\begin{matrix} X^{'} (ω_{k}) & = & \frac{1}{\sqrt{N L}} \sum_{n = - N L / 2}^{N L / 2 - 1} x_{n}^{'} e^{- j \frac{2 π}{N} k n} \\ = & \frac{1}{\sqrt{N L}} \sum_{ℓ = - L / 2}^{L / 2 - 1} \sum_{m = 0}^{N - 1} x_{m + ℓ N}^{'} e^{- j \frac{2 π}{N} k (m + ℓ N)} \\ = & \frac{1}{L \sqrt{N}} \sum_{ℓ = - L / 2}^{L / 2 - 1} \sum_{m = 0}^{N - 1} x_{m} e^{- j \frac{2 π}{N} k (m + ℓ N)} \\ = & \frac{1}{\sqrt{N}} \sum_{m = 0}^{N - 1} e^{- j \frac{2 π}{N} k m} \\ = & X (ω_{k}) . \end{matrix}$
This implies that the overall spectral shape of $X^{'} (ω)$ will be inherited by the DFT outputs ${X_{0}, \dots, X_{N - 1}}$ . So what is the overall shape of $X^{'} (ω)$ ? Say that ${x_{n}}$ is a lowpass process. Being lowpass, we expect the time-domain sequence ${x_{n}}$ to look relatively “smooth.”If the starting and ending points of the N -block, are different, however, the periodic extension ${x_{n}^{'}}$ will exhibit time-domain discontinuities (see [link] (b)) that are uncharacteristic of the process ${x_{n}}$ . These discontinuities imply that $X^{'} (ω)$ will contain high-frequency content not present in the power spectrum of the lowpass input process.Based on our previous findings, if artificial high-frequency content exists at $X^{'} (ω_{k})$ , it must also exist at $X (ω_{k}) = X_{k}$ . In conclusion, the periodic extension ${x_{n}^{'}}$ provides an intuitive explanation of why short-block DFT analysis of lowpass signals oftenseems corrupted by “artificial” high-frequency content. So why is this important?Recall that transform performance is proportional to the dynamic range of transform output variances.If the DFT outputs corresponding to otherwise low spectral energy are artificially increased due to short-window effects,the dynamic range of ${σ_{y_{k}}^{2}}$ will decrease, and DFT performance will fall short of optimal.

Illustration of periodic extensions inherent to DFT and DCT: (a) N -length DFT input block, (b) periodic extension inherent to DFT, (c) equivalent $2 N$ -length DFT-input-block for DCT, (d) periodic extension inherent to DCT.

Now lets consider the DCT. From derivation of the fast algorithm, we know that the N DCT output magnitudes from length- N input ${x_{0}, \dots, x_{N - 1}}$ are equal to the first N DFT output magnitudes from length- $2 N$ input ${{\bar{x}}_{n}}$ —a mirrored version of ${x_{0}, \dots, x_{N - 1}}$ . (See [link] (c).) Due to the mirroring effect, the periodic extension of ${{\bar{x}}_{n}}$ will not have the discontinuities present in the periodic extension of ${x_{n}}$ , and so a $2 N$ -point DFT analysis of ${{\bar{x}}_{n}}$ will not have “artificial” high frequency enhancement.Assuming that the process from which ${x_{n}}$ was extracted is lowpass, the DCT outputs will exhibit large dynamic range, andan improvement over DFT coding performance is expected. This is confirmed by [link] (a).

<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

100% Free Mobile Applications
Receive real-time job alerts and never miss the right job again

Source: OpenStax, An introduction to source-coding: quantization, dpcm, transform coding, and sub-band coding. OpenStax CNX. Sep 25, 2009 Download for free at http://cnx.org/content/col11121/1.2

Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'An introduction to source-coding: quantization, dpcm, transform coding, and sub-band coding' conversation and receive update notifications?

Ask

	7 Biology 07 Cellular Respiration MCQ By OpenStax Start Quiz
	9 AP Key Terms 09 Joints Key Terms By OpenStax Start Key Terms
©flickr: U.S.	Biology Chapter 10 By Michael Sag Start Exam
	4 Gang of Four Design Patterns By JavaChamp Team Start Quiz
	2 Physiotherapy Flashcards Set 2 By Rhodes Start Flashcards
	13 Lec:13 Hypothesis Testing P-values By Janet Forrester Start Quiz
	NCE Ch 10 Professional Orientation By Anh Dao Start Quiz
	Interviewing Skills MCQ By Mary Matera Start Quiz
	Time and Stress Management MCQ By Dionne Mahaffey Start Quiz
	World Capitals Quiz By Yasser Ibrahim Start Quiz

3.5 Sub-optimum orthogonal transforms

[dft and real-valued dft for N = 4 ]

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

[dft and real-valued dft for $N = 4$ ]