3.4 Performance

Asymptotic performance analysis

• For an $N\times N$ transform coder, Equation 1 from "Gain over PCM" presented an expression for the reconstruction error variance ${\sigma }_r^2{|}_{\text{TC}}$ written in terms of the quantizer input variances $\left\{{\sigma }_{y_k}^2\right\}$ . Noting the N -dependence on ${\sigma }_r^2{|}_{TC}$ in Equation 1 from "Gain over PCM" and rewriting it as ${\sigma }_r^2{|}_{\text{TC},N}$ , a reasonable question might be: What is ${\sigma }_r^2{|}_{\text{TC},N}$ as $N\to \infty$ ?
• When using the KLT, we know that ${\sigma }_{y_k}^2={\lambda }_k$ where λ _k denotes the $k^{th}$ eigenvalue of ${\mathbf{R}}_x$ . If we plug these ${\sigma }_{y_k}^2$ into Equation 1 from "Gain over PCM" , we get
  $$\begin{array}{ccc}\hfill {\sigma }_r^2{|}_{\text{TC},N}& =& {\gamma }_y{2}^{-2R}{\left(\prod _{k=0}^{N-1},{\lambda }_k\right)}^{1/N}.\hfill \end{array}$$
  Writing ${\left({\prod }_k{\lambda }_k\right)}^{1/N}=exp(\frac{1}{N}{\sum }_{k}ln{\lambda }_k)$ and using the Toeplitz Distribution Theorem (see Grenander&Szego)
  $$\begin{array}{c}\hfill \text{For}\text{any}f(·)\text{,}\underset{N\to \infty }{lim}\frac{1}{N}\sum _{k}f\left({\lambda }_k\right)=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }f\left(S_x\left(e^{j\omega }\right)\right)d\omega \end{array}$$
  with $f(·)=ln(·)$ , we find that
  $$\begin{array}{ccc}\hfill \underset{N\to \infty }{lim}{\sigma }_r^2{|}_{\text{TC},N}& =& {\gamma }_y{2}^{-2R}exp\left(\frac{1}{2\pi },{\int }_{-\pi }^{\pi },ln,S_x,\left(e^{j\omega }\right),d,\omega \right)\hfill \\ & =& {\gamma }_y{\sigma }_x^2{2}^{-2R}{\text{SFM}}_x\hfill \end{array}$$
  where ${\text{SFM}}_x$ denotes the spectral flatness measure of $x\left(n\right)$ , redefined below for convenience:
  $$\begin{array}{ccc}\hfill {\text{SFM}}_x& =& \frac{exp\left(\frac{1}{2\pi },{\int }_{-\pi }^{\pi },ln,S_x,\left(e^{j\omega }\right),d,\omega \right)}{\frac{1}{2\pi }{\int }_{-\pi }^{\pi }{S}_x\left(e^{j\omega }\right)d\omega }.\hfill \end{array}$$
  Thus, with optimal transform and optimal bit allocation, asymptotic gain over uniformly quantized PCM is
  $$\begin{array}{c}\hfill \begin{array}{|c|}\hline G_{\text{TC},N\to \infty }=\frac{{\sigma }_r^2{|}_{\text{PCM}}}{{\sigma }_r^2{|}_{\text{TC},N}\to \infty }=\frac{{\gamma }_x{\sigma }_x^2{2}^{-2R}}{{\gamma }_y{\sigma }_x^2{2}^{-2R}{\text{SFM}}_x}=\frac{{\gamma }_x}{{\gamma }_y}{\text{SFM}}_x^{-1}\\ \hline\end{array}.\end{array}$$
• Recall that, for the optimal DPCM system,
  $$G_{\text{DPCM},N\to \infty }=\frac{{\sigma }_r^2{|}_{\text{PCM}}}{{\sigma }_r^2{|}_{\text{DPCM},N\to \infty }}=\frac{{\sigma }_x^2}{{\sigma }_e^2{|}_{min}},$$
  where we assumed that the signal applied to DPCM quantizer is distributed similarly to the signal applied to PCM quantizerand where ${\sigma }_e^2{|}_{min}$ denotes the prediction error variance resulting from use of the optimal infinite-lengthlinear predictor:
  $${\sigma }_e^2{|}_{min}=exp\left(\frac{1}{2\pi },{\int }_{-\pi }^{\pi },ln,S_x,\left(e^{j\omega }\right),d,\omega \right).$$
  Making this latter assumption for the transform coder (implying ${\gamma }_y={\gamma }_x$ ) and plugging in ${\sigma }_e^2{|}_{min}$ yields the following asymptotic result:
  $$\begin{array}{|c|}\hline G_{\text{TC},N\to \infty }=G_{\text{DPCM},N\to \infty }={\text{SFM}}_x^{-1}\\ \hline\end{array}.$$
  In other words, transform coding with infinite-dimensional optimal transformation and optimal bit allocation performs equivalently toDPCM with infinite-length optimal linear prediction.

Finite-dimensional analysis: comparison to dpcm

• The fact that optimal transform coding performs as well as DPCM in the limiting case does not tell us the relative performanceof these methods at practical levels of implementation, e.g., when transform dimension and predictor length are equal and $\ll \infty$ . Below we compare the reconstruction error variances of TC and DPCMwhen the transform dimension equals the predictor length. Recalling that
  $$G_{\text{DPCM},N-1}=\frac{{\sigma }_x^2}{{\sigma }_e^2{|}_{min,N-1}}$$
  and
  $${\sigma }_e^2{|}_{min,N-1}=\frac{|{\mathbf{R}}_N|}{|{\mathbf{R}}_{N-1}|}$$
  where ${\mathbf{R}}_N$ denotes the $N\times N$ autocorrelation matrix of $x\left(n\right)$ , we find
  $$\begin{array}{c}\hfill G_{\text{DPCM},N-1}={\sigma }_x^2\frac{|{\mathbf{R}}_{N-1}|}{|{\mathbf{R}}_N|},G_{\text{DPCM},N-2}={\sigma }_x^2\frac{|{\mathbf{R}}_{N-2}|}{|{\mathbf{R}}_{N-1}|},G_{\text{DPCM},N-3}={\sigma }_x^2\frac{|{\mathbf{R}}_{N-3}|}{|{\mathbf{R}}_{N-2}|},\cdots \end{array}$$
  Recursively applying the equations above, we find
  $$\begin{array}{c}\hfill \prod _{k=1}^{N-1}{G}_{\text{DPCM},k}={\left({\sigma }_x^2\right)}^{N-1}\frac{|{\mathbf{R}}_1|}{|{\mathbf{R}}_N|}=\frac{{\left({\sigma }_x^2\right)}^N}{|{\mathbf{R}}_N|}\end{array}$$
  which means that we can write
  $$\begin{array}{c}\hfill |{\mathbf{R}}_N|={\left({\sigma }_x^2\right)}^N{\left(\prod _{k=1}^{N-1},G_{\text{DPCM},k}\right)}^{-1}.\end{array}$$
  If in the previously derived TC reconstruction error variance expression
  $$\begin{array}{ccc}\hfill {\sigma }_r^2{|}_{\text{TC},N}& =& {\gamma }_y{2}^{-2R}{\left(\prod _{\ell =0}^{N-1},{\lambda }_{\ell }\right)}^{1/N}\hfill \end{array}$$
  we assume that ${\gamma }_y={\gamma }_x$ and apply the eigenvalue property ${\prod }_{\ell }{\lambda }_{\ell }=\left|{\mathbf{R}}_N\right|$ , the TC gain over PCM becomes
  $$\begin{array}{ccc}\hfill G_{\text{TC},N}& =& \frac{{\sigma }_r^2{|}_{\text{PCM}}}{{\sigma }_r^2{|}_{\text{TC},N}}=\frac{{\gamma }_x{\sigma }_x^2{2}^{-2R}}{{\gamma }_x{2}^{-2R}·{\sigma }_x^2{\left({\prod }_{k=1}^{N-1},G_{\text{DPCM},k}\right)}^{-1/N}}\hfill \\ & =& {\left(\prod _{k=1}^{N-1},G_{\text{DPCM},k}\right)}^{1/N}\hfill \\ & <& G_{\text{DPCM},N}.\hfill \end{array}$$
  The strict inequality follows from the fact that $G_{\text{DPCM},k}$ is monotonically increasing with k . To summarize, DPCM with optimal length- N prediction performs better than TC with optimal $N\times N$ transformation and optimal bit allocation for any finite value of N . There is an intuitive explanation for this:the propagation of memory in the DPCM prediction loop makes the effective memory of DPCM greater than N , while in TC the effective memory is exactly N .