Contents

1 Motivation

• Usually happens that the differences between consecutive PCM (Pulse-Code Modulation) [2, 3] samples
  $$e\left[n\right]=s\left[n\right]-s\left[n-1\right],$$

  tend to have a smaller variance (and therefore, smaller entropy) than the original ($s$) ones

  $${\sigma }^2\left(e\right)\le {\sigma }^2\left(s\right),$$

  which potentially provides better lossless compression ratios for $e$ than for $s$.

• Finally, notice that by definition, if a source of “noise” (such as the quantization noise) has not been introduced during the encoding process, differential encoding is a fully reversible process:
  $$s\left[n\right]=e\left[n\right]+s\left[n-1\right].$$

2 Lab

• Compute $e$ signal for the Jfk_berlin_address_high.ogg $s$ signal and plot the probability density function (also known as the histogram) of $e$. Note: use Python and Matplotlib, and insert the code here.

IPython notebook

3 DPCM (Differential PCM)

• Signals sampled at Nyquist rate exhibit correlation between consecutive samples. Therefore, the variance of the first difference

  $${\sigma }^2\left({\left\{s\left[n+1\right]-s\left[n\right]\right\}}_{n=0}^{N-1}\right)$$

  (1)

  will be smaller than the variance of the signal itself

  $${\sigma }^2\left({\left\{s\left[n+1\right]-s\left[n\right]\right\}}_{n=0}^{N-1}\right)<{\sigma }^2\left(s\right)={\sigma }_s^2.$$

  (2)

• In general, DPCM consist in computing the residual (error signal):

  $$e\left[n\right]=s\left[n\right]-ŝ\left[n\right]$$

  (3)

  where for the simplest case:

  $$ŝ\left[n\right]=s\left[n-1\right]$$

  (4)

• Used in the G.726 standard.

4 ADPCM (Adaptive DPCM)

• In orter to minimize ${\sigma }_e^2$, the predictor $P$ can change its behaviour depending on the characteristics of $s$.

5 Forward adaptive prediction

• Splits the input into blocks, optimizes the predictor for each block and sends with each ADPCM block the predictor coefficients as side information.

6 Optimal prediction based on Weiner-Hopf optimization

• The predictor can be any structure capable of producing a signal

  $$ŝ\approx s.$$

  (5)

• In the case of using LPC (Linear Predictive Coding), where

  $$ŝ\left[n\right]=\sum _{i=1}^M{a}_{i}s\left[n-i\right],$$

  (6)

  ${\left\{a_i\right\}}_{i=1}^M$ are the LPC coefficients and $M$ is the predictor order.

• Optimal foeffs $\left\{a_i\right\}$ can be found when they minimize the variance of the residue (error signal)

  $${\sigma }_e^2=\text{E}\left[\right.{\left(s\left[n\right]-\sum _{i=1}^M{a}_{i}s\left[n-i\right]\right)}^2\left]\right..$$

  (7)

• For this, it must me hold that

  $$\left.\begin{array}{c}\hfill \frac{\partial {\sigma }_e^2}{\partial a_1}=-2\text{E}\left[\right.\left(\right.s\left[n\right]-\sum _{i=1}^M{a}_{i}s\left[n-i\right]\left)\right.s\left[n-1\right]\left]\right.=0\hfill \\ \hfill \frac{\partial {\sigma }_e^2}{\partial a_2}=-2\text{E}\left[\right.\left(\right.s\left[n\right]-\sum _{i=1}^M{a}_{i}s\left[n-i\right]\left)\right.s[n-2\left]\right.=0\hfill \\ \hfill ⋮\hfill \\ \hfill \frac{\partial {\sigma }_e^2}{\partial a_M}=-2\text{E}\left[\right.\left(\right.s\left[n\right]-\sum _{i=1}^M{a}_{i}s\left[n-i\right]\left)\right.s\left[n-M\right]\left]\right.=0\hfill \end{array}\right\}.$$

  (8)

• Appying expectations we get that

  $$\left.\begin{array}{c}\hfill \sum _{i=1}^M{a}_i{\text{R}}_{ss}\left(i-1\right)={\text{R}}_{ss}\left(1\right)\hfill \\ \hfill \sum _{i=1}^M{a}_i{\text{R}}_{ss}\left(i-2\right)={\text{R}}_{ss}\left(2\right)\hfill \\ \hfill ⋮\hfill \\ \hfill \sum _{i=1}^M{a}_i{\text{R}}_{ss}\left(i-M\right)={\text{R}}_{ss}\left(M\right)\hfill \\ \hfill \hfill \end{array}\right\},$$

  (Weiner-Hopf equations)

  where ${\text{R}}_{ss}\left(k\right)$ is the autorrelation function of $s$, defined as

  $${\text{R}}_{ss}\left(k\right)=\text{E}\left[\right.s\left[n\right]s\left[n-k\right]\left]\right.=\frac{1}{M-k}\sum _{i=1}^{M-k}s\left[i\right]s\left[i+k\right].$$

  (autocorrelation)

7 Lab

For each $M=\left\{1,2,3\right\}$, determine the optimal predictor for the audio Jfk_berlin_address_high.ogg, using Weiner-Hopf optimization. Next, compute the variance of $e$ for each prediction order.

8 Backward adaptive prediction

• Both, the encoder and the decoder can constinuosly adapt the prediction to the characteristics of $s$, if both only use the information that is available at the decoder.

9 Adaptive prediction based on Least Mean Squared (LMS) algorithm

• As we know,

  $$e\left[n\right]=s\left[n\right]-ŝ\left[n\right]=s\left[n\right]-\sum _{i=1}^M{a}_{i}s\left[n-i\right].$$

  (9)

• Our objective is to minimize $e\left[n\right]$, which is the same that minimizing the energy of the prediction error $e^2$, by controlling the ${\left\{a_i\right\}}_{i=1}^M$ coefficients.
• Suppose that we can control iteratively these coefficients, by incrementing or decrementing them with a proportionality constant $\alpha$ (the larger $\alpha$, the faster the convergence but possiblely the oscillation, and viceversa). Let’s denote $a_i^{\left[n\right]}$ the value of coeff $a_i$ at iteration $n$ of the algorithm. If happens, for example, that

  $$\frac{\partial e^2\left[n\right]}{\partial a_i}<0$$

  (10)

  (the squared prediction error for iteration $n$ has been increased compared to the previous iteration), then the prediction $ŝ\left[n\right]$ should have been larger, and viceversa. Let’s define the iterative control of ${\left\{a_i\right\}}_{i=1}^M$ coefficients as

  $$\left\{\right.a_i^{\left[n+1\right]}=a_i^{\left[n\right]}-\alpha \frac{\partial e^2\left[n\right]}{\partial a_i}{\left\}\right.}_{i=1}^M$$

  (LMS_idea)

• Applying derivatives we obtain for $a_i$ that

  $$\frac{\partial e^2\left[n\right]}{\partial a_i}=\frac{\partial \left(\right.s\left[n\right]-\sum _{i=1}^M{a}_{i}s\left[n-i\right]{\left)\right.}^2}{\partial a_i}=-2\left(\right.s\left[n\right]-\sum _{i=1}^M{a}_{i}s\left[n-i\right]\left)\right.s\left[n-i\right]=-2e\left[n\right]s\left[n-i\right].$$

  (11)

• Substituting this expression in Eq. (LMS_idea), we get that

  $$\left\{\right.a_i^{\left[n+1\right]}=a_i^{\left[n\right]}+2\alpha e\left[n\right]s\left[n-i\right]{\left\}\right.}_{i=1}^M.$$

  (LMS_control)

• Notice that, in a backward adaptive prediction scheme, both elements $e\left[n\right]$ and $s\left[n-i\right]$ are known at iteration $n$ at both, the encoder and the decoder.

10 Lossy DPCM

• The prediction error is quantized to decrease the variance

  $$ẽ\left[n\right]=Q\left(e\left[n\right]\right),$$

  (12)

  where

  $$e\left[n\right]=s\left[n\right]-\widehat{\tilde{s}}\left[n\right],$$

  (13)

  where

  $$\tilde{s}\left[n\right]=\widehat{\tilde{s}}\left[n\right]+ẽ\left[n\right].$$

  (14)

• Used in hybrid (lossy DPCM/transform) video coding [1].

References