ADAPTIVE DIFFERENTIAL PULSE CODE MODULATION
FOR IMAGE COMPRESSION
by
Douglas Ray Gschwind
B.S., Michigan State University, 1988
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Electrical Engineering
1995
This thesis for the Master of Science
degree by
Douglas Ray Gschwind
has been approved
by
Mike Radenkovic
b JULl 1^5
Date
Gschwind, Douglas Ray (M.S., Electrical Engineering)
Adaptive Differential Pulse Code Modulation for Image Compression
Thesis directed by Assistant Professor Tamal Bose
ABSTRACT
A one-dimensional (1-D) and a two-dimensional (2-D) data compression scheme
using Adaptive Differential Pulse Code Modulation (ADPCM) are presented using the
sample based Fast Conjugate Gradient (FCG) algorithm to adapt the filter coefficients.
The sample based FCG algorithm has a very fast convergence characteristic
comparable to that of the Recursive Least Squares (RLS) but with a lower
computational complexity. The FCG algorithm will be shown to be much more
efficient in terms of convergence and also less sensitive to changes in system
parameters, than the Least Mean Squares (LMS) algorithm. In both the 1-D and 2-D
cases, both adaptive prediction and adaptive quantization are implemented in a fixed
bit rate transmission scheme, to evaluate the performance of the FCG algorithm in the
ADPCM context.
This abstract accurately represents the content of the candidates thesis. I recommend
its publication.
Signed
Tamal Bose
in
CONTENTS
Chapter
1. Introduction to ADPCM 1
1.1 Adaptive Prediction 9
1.1.1 Least Mean Squares (LMS) Adaptive Prediction 11
1.1.2 Fast Conjugate Gradient (FCG) Adaptive Prediction 12
1.2 Quantization 16
1.2.1 Non-Adaptive Quantization 18
1.2.2 Adaptive Quantization 18
2. 1-Dimensional Adaptive Prediction 24
2.1 Adaptive Prediction via the Least Mean Squares Algorithm 27
2.2 Adaptive Prediction via the Fast Conjugate Gradient Algorithm 32
3. 1-Dimensional Quantization 41
3.1 Non-Adaptive Quantization 44
3.2 Adaptive Quantization 58
4. 2-Dimensional Signal Compression via ADPCM 64
References 81
Appendix 82
A. LMS Adaptive Prediction 82
B. FCG Adaptive Prediction 95
C. FCG Non-Adaptive Quantization 109
D. FCG 1-Dimensional ADPCM Simulation Results 126
E. 2-Dimensional FCG ADPCM Image Compression 153
IV
1 Introduction to ADPCM
Communication systems require a certain bandwidth or channel capacity to be
allocated to them so that information may be successfully communicated between
point A and point B. (Figure 1.1). This requirement has a certain monetary figure
associated with it which is required to be able to provide this bandwidth or capacity. It
is this fact that motivates a communication system to require less bandwidth or
capacity. Adaptive Differential Pulse Code Modulation (ADPCM) is a method by
which this bandwidth or channel capacity requirement may be reduced, without
adversely affecting the information which is received from the data source. This
bandwidth or channel capacity reduction is known as both Data Coding and Data
source Communication
A
A Channel
receiver
Figure 1.1 Simple Communications Channel
Compression.
ADPCM reduces the bandwidth or channel capacity requirements of a
communications system by removing the redundancy present in adjacent sampled
signal values. The redundancy which is present in adjacent sampled signal values is
simply that portion that exists within each of the two adjacent sampled signal values
which are the same or did not change.
For example, assume that the sampled values from a particular data source are
l
the following : 0,1,2, 3,4, 3,2, 3. A simple use of Differential Pulse Code
Modulation (DPCM) allows the transmission of the difference of all adjacent sampled
values, thus, the above sequence would be transmitted across a Communications
Channel as 1,1,1,1,-1,-1,1. The original data sequence requires three bits per
sample (assuming a minimum signal value of zero and a maximum of four) while this
ADPCM sequence only requires one (transmission of bit = 0 implies -1, transmission
of bit = 1 implies 1). In this very simple case the channel capacity requirements for the
communications channel have been reduced from three bits per sample to one bit per
sample. A savings of two bits per sample.
ADPCM employs two significant processes to both increase the redundancy in
adjacent sampled signal values and reduce the difference between adjacent sampled
signal values. These two processes are Prediction and Quantization. ADPCM uses
Prediction to predict the next sampled signal value before the next sampled signal
value is actually attained. As the predicted signal value gets closer and closer to the
actual signal value, the prediction error gets closer and closer to zero which is highly
desirable. This prediction actually takes place in both the transmitter and receiver
portions of an ADPCM communications system. ADPCM uses Quantization to further
decrease the capacity requirements of the communications channel by transmitting
across the channel a value which represents the prediction error, instead of the
prediction error itself.
Consider the conceptual diagram of an ADPCM communications system as
depicted in Figure 1.2. The transmitter, also known as the encoder, and receiver, also
known as the decoder, blocks indicate what takes place within the confines of ADPCM
on each side of the communications channel. S(n) indicates the actual sampled signal
value, Sp(n) indicates the predicted signal value, e(n) indicates the prediction error,
and eq(n) indicates the quantized representation of the prediction error, all at sample n.
2
The receiver side has like variable names with prime () notation.
At a given sample n, the predicted signal value Sp(n) is calculated based upon
previous prediction errors and reconstructed values (to be addressed later). The current
prediction error e(n) is then calculated simply from
e(n) = S(n)-Sp(n) . (1.1)
The prediction error e(n) is then passed through the quantizer, to arrive as the
quantized representation of the prediction error eq(n), at sample n. This quantized
prediction error is then passed on to the receiver over the communications channel and
at the same time to the transmitters prediction process for the computation of the next
predicted signal value.
3
The receiver then receives a value eq(n) from the transmitter which is the
Transmitter
Receiver
Figure 1.2 Conceptual ADPCM Diagram
quantized representation of the prediction error from the transmitter, plus any noise
introduced in the communications channel (which will be ignored for now). The
receiver calculates its predicted signal value Sp(n), and uses this to compute its
version of the signal value S(n), as
SXn) = S'p(n) + e'q(n) . (1.2)
4
This is, at a high level, what takes place on both the transmitter and receiver
sides of a communications channel utilizing ADPCM at a given sample n. What has
not been mentioned thus far is how the prediction process operates.
Refer to Figure 1.3 for a detailed depiction of a transmitter which is
responsible for transmitting ADPCM data across a communications channel. New in
this figure is the notion of the MA and AR portions of the prediction process. This is
very similar to that found in [1].
Figure 1.3 ADPCM Transmitter
Figure 1.3 depicts the MA (Moving Average) and AR (Auto Regressive)
portions of the transmitter prediction process in full. The MA portion, also known as
the Transversal portion of the predictor, is only concerned with the prediction errors,
while the AR portion, also known as the Recursive portion, is concerned with the
reconstructed signal values, Sr(n). The reconstructed signal value at sample n depends
5
on the predicted signal values Sp(n -1) and eq(n -1) as
Sr(n) = Sp(n -1) + eq(n 1) . (1.3)
Equation (1.3) indicates that the reconstructed signal value at sample n is the
sum of the previous predicted signal value and prediction error.
The receiver must produce the same predicted signal value as the transmitter at
each sample n to remain in sync with the transmitter. The details of the prediction
process on the receiver side of an ADPCM communications channel is depicted in
Figure 1.4. This is very similar to that detailed in [2]. In the presence of quantization
noise, which will be discussed in detail in section 1.2, S(n) on the receiver side will
directly reflect the value of Sr(n) on the transmitter side. S(n) on the receiver side
directly reflects the value of S(n), the actual input signal being sampled on the
transmitter side, if the quantization process is not present in the ADPCM process.
The MA and AR portions of the prediction process are identical, and must be,
in both the transmitter and receiver sides of an ADPCM communications channel. The
MA portion is only concerned with the current and some number of previous
representations of the prediction error. The AR portion is concerned with the current
6
representation of the prediction error and some number of reconstructed signal values.
This is also apparent from the discussions in [2].
The output of the MA block, on either the transmitter or receiver side, is
defined as
MA(n) = a1eq(n-l) + a2eq(n-2) +... + azeq(n-Z) . (1.4)
The eq(i) scalar values are the Z previous quantized prediction errors, while the a;
scalar values are the corresponding Moving Average filter coefficients. Let
A = [aj a2... &z)T and E = [eq(n -1) eq(n 2)... eq(n Z)]T. The output of the MA
block may then be represented as
MA(n) = AtE . (1.5)
The output of the AR block, again on the transmitter or receiver side, is defined
similarly to that of the MA block as
AR(n) = hjS/n -1) + b2sr{n 2) + ... + bpsr(n P) . (1.6)
The Sj.(i) scalar values are the P previous reconstructed signal values, while the b,
scalar values are the corresponding Auto Regressive filter coefficients. Let
B = [bj b2 ... bp]T and S = [s^n -1) Sj.(n 2)... s/n P)]T. The output of the AR block
may then be represented as
AR(n) = BTS . (1.7)
The A and B vectors which contain filter coefficients are updated at each
sample n using a method such as Least Mean Squares (LMS), Recursive Least Squares
(RLS), or the Fast Conjugate Gradient (FCG) algorithms. The updating of the filter
7
coefficients will be discussed in detail in sections 1.1.1 and 1.1.2.
The E and S vectors are updated very simply. At the completion of processing
for sample n, the first element in the vector becomes the current prediction error and
reconstructed signal value respectively, while the remaining positions in each vector
are all values except the last value from the previous vector definition. This then
simply shifts the latest prediction error or reconstructed signal value into the beginning
of the vector while the last value in the vector is displaced out of the vector never to be
accessed again.
In general, Sr(n) and S(n) are given by
Sr(n) = axeq(n-\) + ...+azeq(n-Z) + bxsr{n-\) + ...+bpsr(n-P) . (1.8)
Taking the z-transform of both sides of (1.8) yields
Sr(z) = axe^z)z~l + ... + azeq(z)z~z + bxsr(z)z-x + ... + bpsr(z)zrp . (1.9)
After rearranging terms and simplifying, the transfer function for the
prediction process may be found as
S(z) a,z_1 + a0z~2 + ... + a7z~z
= ------------------------------------ (1.10)
eq(z) l (bxz~l + b2z~2 + ... + bpz~p)
This then highlights the fact that the number of prediction errors that are saved
for predicting future signal values equates to the number of zeroes in the transfer
function of the prediction process. Also, the number of reconstructed signal values that
are saved for predicting future signal values equates to the number of poles in the
8
transfer function of the prediction process.
The number of poles and zeroes used in the prediction process has very
significant implications with regard to system stability and speed of convergence.
These topics will be addressed in the next section detailing the specifics of the filter
coefficients and their adaptation to changes in the input signal S(n).
The ADPCM process involves the following conceptual steps, in both the
transmitter and receiver sides, in the exact order stated:
1) Predict the sampled signal value
2) Compute the prediction error between the actual and predicted signal values
3) Compute the reconstructed signal value
4) Update the MA and AR filter coefficients
5) Update the vectors which contain previous errors and previous reconstructed
signal values.
It is step 4, the process of updating the MA and AR filter coefficients, which is
the subject of the next section.
1.1 Adaptive Prediction
Prediction of a given signal based upon previous errors and reconstructed
values may be done in a non-adaptive (coefficients do not change over time) sense or
in an adaptive sense. This document will be investigating the adaptive prediction
scheme only, where the MA and AR filter coefficients will change over time.
In general, the depiction of the conceptual ADPCM communications channel
9
must be updated to appropriately depict adaptive prediction taking place in both the
transmitter and receiver sides of the system. This is depicted in Figure 1.5.
Transmitter
Receiver
Figure 1.5 Conceptual ADPCM Diagram with Adaptive Prediction
The predictor portions of the ADPCM communications system continue to
receive the values eq(n) or S(n) on the transmitter and receiver sides respectively, but
the arrow drawn through the predictor boxes indicates that those values force the filter
coefficients to adapt to those changes according to the filter coefficient updating
mechanism used.
10
This section will describe in detail two schemes for updating the MA and AR
filter coefficients. The first method describes the use of the Least Mean Squares
algorithm for updating the filter coefficients. The second method discussed describes
the sample based Fast Conjugate Gradient algorithm and its application to the
ADPCM problem domain. Of course, the chosen method must be used on both the
transmitter and receiver sides of an ADPCM communications channel to force the
transmitter and receiver to be in sync at all times.
1.1.1 Least Mean Squares (LMS) Adaptive Prediction
In general, the LMS method of updating the ADPCM MA and AR filter
coefficients is given as
A(n + 1) = (l-S)A(n) + aeg(n)E , (1.11)
and
B(n+ 1) = (l-5)5(/i) + p^(/i)S (1.12)
where the leakage factor (8,0 < 5 1) represents a diminishing effect over time of
previous filter coefficient values, and the adaptation constants, (a,(3), provide certain
speeds of convergence as indicated in [2] and [3]. A, B, E, and S are vectors as defined
in the previous section.
In step 4 of ADPCM processing, both the transmitter and receiver sides of the
communications system must perform the operations indicated in both (1.11) and
(1.12). Once completed, step 5 in the sequence may be performed. Later, in section
2.1, simulation results will be presented highlighting the effectiveness of this
algorithm.
11
It is well known that the LMS method is computationally inexpensive, but
does not provide reliable stability, and requires a considerable amount of time to
converge. These facts motivate the use of a more stable algorithm with better
convergence characteristics.
1.1.2 Fast Conjugate Gradient (FCG) Adaptive Prediction
The sample based FCG algorithm has been found to produce very fast
convergence properties while providing very reliable stability, as discussed in [4], and
is only slightly more computationally expensive than the LMS method. These facts
motivate the investigation of the use of this method in the ADPCM context.
First, a review of how the FCG algorithm is obtained. Let
A(i) = [eq(n 1) eq(n 2)... eq(n Z) Sr(n 1) Sr(n 2)... Sr(n P)]T,
xn = [a! a2... bj b2... bp]T, and s(i) = sampled input signal at time i. Define an error
function as
J(xn) = X *n-f(Ar0X-*(i))2 . G.13)
i = 0
where A, is a forgetting factor. The FCG algorithm is designed to minimize this error
function. Let
d2J(xn)
0*)2 '
(1.14)
Qn may then be found by partially differentiating J(xn) with respect to xn as
12
n
(1.15)
dJ(xn)
dxn
= 2]?X'-i(AT(i)xn-s(i))A(0 ,
1 = 0
Q
n
3V(-t)
OJt)2
n n-1
= 2 Xn~iA(i)AT(i) = 2A(n)Ar(n) + 2 ]T Xn-A(i)AT(i) (1.16)
i=0 i=o
Since
<2
n- 1
(3*-t)2
I = 0
V-'/KiM7 ,
(1.17)
(1.16) may be rewritten as
Q = lAm^ + XQ^j . (1.18)
The gradient gn (first partial derivative) found in (1.15) may also be rewritten as
g = 2 2 V-'04 T(i)x-s(i))A(i)
i = 0
n n
= 2 ]T Xn-iA{i)AT{i)xn-2 Â£ V-'s(iM(i)
1=0 1=0
= Qnxn-2yÂ£X"-is(i)A(i) (1.19)
i = 0
Now, let
13
n
Dn = 2^^-'5(0A(0 , (1.20)
/ = 0
the second term from (1.19). Simplifying terms, Dn may be rewritten as
n-l
Dn = 2 Â£ Xn~is(i)MS) + 2s(n)A(n) = XDn_l + 2s(n)A(n) . (1.21)
i = 0
Combining (1.19) and (1.20), gn may be written as
Sn = QnXn~Dn d-22)
With this, the formulation of the FCG algorithm is essentially complete. Further steps
below are carried out to remove any redundant computation which may be required of
the FCG algorithm as of its current definition. Substituting (1.18) and (1.21) into
(1.22) shows that (1.22) may be written as
Sn = a<2n_l + 2A(n)AT(n))xn-U>n_l-2s(n)A(n) . (1.23)
Adding one and subtracting one kQn lxn l term on the right hand side of (1.23)
and rearranging terms, yields
Sn = XQn-lXn-l-^Dn-l+XQn-l^Xn-Xn-0 + 2A(n) (AT(n)Xn~ s(n)) (1.24)
Let
(Sn)TDn
(Dn)TQnn '
(1.25)
then substituting this into (1.24) yields
Qn = l(Sn-i+an-iQn-iDn-i) + 2A(n) (AT(n)xn~ s(n)) . (1.26)
14
The complete FCG algorithm may now be stated as follows. Before the
algorithm may be used, initialize the matrix, the constant a, and vectors to contain all
zeros. The steps of the algorithm defined below, must be executed in entirety in
sequence, once per sample n.
a) e(ri) = AT(n)x(n) Sin)
b) gin) = \(g(n 1) + ap(n)) + e(n)A(n)
op- gT^n)
gT(n 1 )g(n 1) + e
d) if ||g(/i)|2 > ||g(n 1)B2, d(n) = -gin) else din) = -gin) + (3d(/i)
e) pin) = Qin)din)
f) a = gT(n)gjn)
dTin)pin) + E
g) xin) = xin) + adin)
h) The A vector must have the appropriate prediction error and reconstructed
signal value shifted into it at this point as described in section 1
i) Qin) = XQin) + Ain + \)ATin + 1)
In steps (c) and (f), e is added in the denominator to avoid division by zero.
The accuracy and performance of the algorithm will not be significantly degraded
under the condition that e is chosen to be very small. At any given sample n, the
prediction error is computed in step a and all steps including step i will be performed
before the processing for sample (n + 1) may take place.
Simulation results using the sampled based FCG algorithm in the ADPCM
context will be present in section 2.2 of this document.
15
1.2 Quantization
Quantization is the phase in ADPCM processing where the greatest reduction
in bit transmission rate requirements may be realized. It is simply not enough to
attempt to predict the next sampled signal value and transmit the prediction errors. The
quantization portion of an ADPCM process determines the bit pattern to transmit to
the receiver which represents a certain, and the same, quantized error value to both the
transmitter and the receiver. An example of this is depicted in Figure 1.6.
eq(n)
e(n)
Figure 1.6 Quantized Error vs. Prediction Error
Assume that the range of prediction errors for a given ADPCM
communications system is 0 <= e(n) <= 0.001. This will certainly vary per system
given the input signal characteristics and statistics, but the case stated is to highlight
the benefits to be gained from the quantizer in the ADPCM system. Figure 1.6
indicates that eq(n) equates to one single value for any given range of e(n). The value
chosen for eq(n) is that value which minimizes the absolute value of the difference
16
between e(n) and eq(n).
Suppose for this example we wish to quantize all prediction errors into a three
bit codeword. The following table, Table 1.1, describes the quantization error and
codeword to transmit to the receiver given any transmitter prediction error, e(n). Note
that for any prediction errors outside the expected range, e(n) < 0.0 or e(n) > 0.001, the
quantized error is simply the minimum or maximum quantized value.
Table 1.1 depicts the quantization levels and how they are to be used. For
example, if the prediction error e(n) is anywhere in the range 0.0005 <= e(n) <
0.000643, the value 4 is transmitted to the receiver which indicates to the receiver that
the quantized prediction error for that sample n, is actually 0.000572.
Table 1.1: Quantization Levels vs. Prediction Error e(n)
e(n) >= e(n) < eq(n) Codeword Transmitted to Receiver
0.0000714 0.0 0002 = 0
0.000714 0.000214 0.000143 0012 = 1
0.000214 0.000357 0.000286 0102 = 2
0.000357 0.0005 0.000429 0112 = 3
0.0005 0.000643 0.000572 n
0.000643 0.000786 0.000715 1012 = 5
0.000786 0.000929 0.000858 1102 = 6
0.000929 0.001 1112 = 7
Quantization noise becomes present in the system due to the fact that the
difference between the prediction error and quantized prediction error is non-zero for a
very large percentage of the time. This directly affects the convergence performance
17
and stability of an ADPCM system as both the transmitter and receiver use the
quantized prediction error, 0.000572 in the above case, in updating the MA and AR
filter coefficients which will be used to predict the next sampled signal value.
The next two sections discuss different quantization schemes that are useful for
ease and cost of implementation, or may provide reduced quantization noise present in
the transmitter and receiver.
1.2.1 Non-Adaptive Quantization
Non-Adaptive Quantization is the easiest to implement, and due to its static
nature may be more conservative in a stability sense than any adaptive method. This
method of quantization simply ignores changes in the input data stream, using one
quantization scheme all the time. An example would be an ADPCM system which
utilizes the quantization levels present in Table 1.1, even after prediction errors in the
transmitter and receiver are seen to grow much larger than 0.001.
This form of quantization may provide a good amount of compression, but it
ignores changes in the input data sequence which could prove to render an ADPCM
communications channel inaccurate.
1.2.2 Adaptive Quantization
Adaptive Quantization is quantization as described above, with the difference
being the ability to change the quantization leveling scheme based upon quantized
prediction errors or the reconstructed signal values themselves. There are both variable
and fixed bit rate transmission schemes which are adaptive. For practical purposes,
only those adaptive quantization schemes which provide fixed bit transmission rates
will be considered.
18
Again, there are two pieces of information, given no significant transmission
errors to the receiver, which may be used to adapt the quantization leveling scheme.
These two pieces are the quantized prediction error eq(n), and the reconstructed signal
value Sr(n). These two values should be identical on both the transmitter and receiver
sides at all times in the presence of error free transmission to the receiver.
This document addresses the use of the quantized prediction error eq(n) to
determine how to adapt the quantization leveling scheme. This was chosen as the
factor to drive adaptation of the quantization leveling scheme since it logically follows
that it is more sensitive to changes in prediction errors than reconstructed signal
values. There are many ways in which the quantization leveling scheme may adapt to
changes in the quantized prediction errors. The method on which all of the simulation
results are based is described in [5].
Given a certain quantization scheme at sample n, H(n), the adaptive method
described above uses (1.27) below to determine the quantization scheme to be used at
sample (n + 1). The value of the constant M may also be
H(n +1) = M H(n) (1.27)
adapted based upon quantized prediction errors or reconstructed signal values. The
use of this method will be considered when sensitive to changes in the prediction error
as opposed to changes in the reconstructed signal values as suggested in [5].
The results of computer simulations of ADPCM communications utilizing this
adaptive quantization scheme are presented in later chapters, but do not actually
perform this multiplication per sample n. The schemes implemented based upon (1.27)
19
performed this multiplication in an a priori sense and therefore the dynamic
readjustment of the quantization leveling scheme presented above is not necessary
once quantized representations of the prediction error are transmitted to the receiver.
Assuming a three bit fixed transmission rate communications channel with
sampled signal values in the range [-1,1], an example of a two depth adaptive
quantization scheme is presented in Tables 1.2 and 1.3. The key to this adaptive
Table 12: Quantization Leveling Scheme First Depth
e(n) >= e(n) < eq(n) Codeword Transmitted to Receiver
-0.8571 -1.0 0002 = 0
-0.8571 -0.5714 -0.7143 O O >* II
-0.5714 -0.2857 -0.4286 0102 = 2
-0.2857 0.0 -0.1429 0112 = 3
0.0 0.2857 0.1429 1002 = 4
0.2857 0.5714 0.4286 o II L/\
0.5714 0.8571 0.7143 1102 = 6
0.8571 1.0 1112 = 7
quantization scheme is to know when to use which depth in the scheme and when to
change to the other. Since the transmitter and receiver both know the quantized
prediction error at any sample n, ignoring significant errors in transmission, these
rules may be predetermined and depth changes in the quantization leveling scheme
need not be communicated from the transmitter to the receiver via the communications
channel. Both transmitter and receiver initialize to the first depth and adapt over
time as described below.
20
Operate under the conditions specified in the first depth until the codeword
to transmit to the receiver at sample n is three or four. The transmission of a codeword
having value three or four represents an opportunity to decrease the quantization noise
introduced into the system by using the quantization leveling scheme available in the
second depth. The quantization noise may be reduced by use of the second depth
since the difference between adjacent quantized prediction errors is significantly less
in the second depth than in the first. Therefore, whenever a codeword of three or
four is transmitted to the receiver when operating in the first depth at sample n, both
the transmitter and receiver use the quantization leveling scheme in the second
depth at sample (n + 1). Similarly, operate under the conditions specified in the
second depth until the codeword to transmit to the receiver at sample n is zero or
seven. The transmission of a codeword having value zero or seven indicates the
potential of introducing additional quantization noise into the system since the
quantization leveling scheme in the second depth has a much more limited range
than that in the first and is only effective while attempting to quantize a very limited
range of prediction errors e(n). Therefore, whenever a codeword of zero or seven is
transmitted to the receiver when operating at the second depth at sample n, both the
transmitter and receiver use the quantization leveling scheme in the first depth at
sample (n + 1).
21
This scheme simply helps to reduce quantization noise in the transmitter and
Table 1J: Quantization Leveling Scheme Second Depth
e(n) >= e(n) < eq(n) Codeword Transmitted to Receiver
-0.1225 -0.1429 0 11
-0.1225 -0.08167 -0.1021 0012= 1
-0.08167 -0.04084 -0.06124 0102 = 2
-0.04084 0.0 -0.02014 0112 = 3
0.0 0.04084 0.02014 Ti- ll ts 0 0
0.04084 0.08167 0.06124 1012 = 5
0.08167 0.1225 0.1021 1102 = 6
0.1225 0.1429 1112 = 7
receiver ADPCM processes to allow the filter coefficient updating algorithm to
converge to the input signal characteristics as fast as possible.
For example, suppose the current operating depth in the ADPCM
communications channel is the first depth. Suppose the prediction error e(n) at
sample n is -0.223. A value of three (0112) is transmitted to the receiver to indicate
that the quantized prediction error at that time is -0.1429. Both the transmitter and
receiver recognize the fact that this indicates to use the second depth of quantization
leveling when performing the ADPCM processing at sample (n + 1). Suppose the
prediction error e(n) at sample (n + 1) is then 0.08. A value of five (IOI2) is
transmitted to the receiver to indicate that the quantized prediction error at that time is
0.06124.
The adaptive quantization scheme here could also be changed to only change
22
depth when the minimum/maximum quantized prediction error has achieved some
N consecutive sample iterations. This is just one simple way in which several
alternative schemes may be implemented where each could obviously have different
performance characteristics.
The example adaptive quantization scheme detailed above has been
implemented for simulation purposes when attempting to compress both one-
dimensional and two-dimensional data sources, the results of which will be presented
in later chapters.
23
2 1-Dimensional Adaptive Prediction
This section will highlight the differences between the LMS and FCG
algorithms for updating the filter coefficients for modelling a 1-Dimensional input
signal. The computer simulations discussed in this section have intentionally omitted
the quantization phase of the ADPCM process to show the performance characteristics
of the given algorithm without the damaging effects of quantization noise. Figure 2.1
depicts the transmitter side of the ADPCM process in the absence of the quantizer
which is the focus of this section. The prediction error e(n) is unquantized.
S(n)
Sp(n) J 5 e(n)
/
Predictor /
'
Communications Channel
Transmitter
Figure 2.1 ADPCM Transmitter without Quantizer
The input signals selected for the computer simulations discussed here and in
Chapter 3 are simple sinusoids. The first input signal is very much like that discussed
in [2], with the center frequency being 1511 Hz and the sampling frequency being 8
kHz. Figure 2.2 depicts a portion of the sampled signal values Si(n). This is described
24
by
Figure 2.2 Sampled Signal Values S^n)
S^n) = sin (2tc/i 1511/8000) . (2.1)
The second input signal was chosen to be the sum of two simple sinusoids
where the center frequencies were chosen fairly close together (1080,1501 Hz) as this
somewhat appears to the ADPCM process as random (uncorrelated) data values as
discussed in [2]. This input signal is described as
S2(n) = sin (2nn 1511/8000) + 2.5 sin (2tc 1080/8000) . (2.2)
Note that the sampling frequency 8000 Hz is the same for both input signals. Figure
2.3 depicts a portion of the sampled input signal S2(n).
25
Figure 2.3 Sampled Signal Values S2(n)
In all the computer simulations in this and Chapter 3, the number of zeroes in
the predictor process (the order of the Moving Average portion of the prediction
process) is six, and the number of poles in the predictor process (the order of the Auto
Regressive portion of the prediction process) is two, as in [2], for the input sequence
Sj(n). The number of poles is increased to four for the input sequence S2(n).
The prediction error e(n), first Moving Average filter coefficient al, and first
Auto Regressive filter coefficient bl, will be investigated in each case as these values
are good indicators of system convergence and stability.
26
2.1 Adaptive Prediction via the Least Mean Squares Algorithm
The equations to be used to update the filter coefficients via the LMS algorithm
are stated in (1.11) and (1.12). The best LMS processing results for the input signal
sequence S^n) were obtained when the leakage factor 8 and the speed of convergence
factors a, P defined in (1.11) and (1.12) were defined as
(6 = 0.00), (a = 0.008), (P = 0.002) As before, E contains all previous Z (6)
prediction errors (i.e. E = [eq(n -1) eq(n 2)... eq(n 6)]T) and S contains all previous
P (2) reconstructed signal values (i.e. S = [Sr(n -1) Sr(n 2)]T) as described in Chapter
1. Given these parameters, the equations for updating the Moving Average and Auto
Regressive filter coefficients may be represented respectively as
The resulting prediction error e(n) found, when utilizing LMS with the above
constant definitions and ignoring the quantization phase of the ADPCM process, is
depicted in Figure 2.4. The prediction error e(n) is easily seen to be
MA(n + 1) = MA(ri) + 0.008^(/i)E ,
(2.3)
AR(n + 1) = AR(n) + 0.002eq(ri)S .
(2.4)
e(n) = S(n)-Sp(n) .
(2.5)
Where Sp(n) may be represented as
Sp(n) = ETMA(n) + STAR(n) .
(2.6)
27
LMS Prediction error e(n) at the encoder
n
Figure 2.4 Sj(n) LMS Prediction Error e(n)
Also, depicted in Figures 2.5 and 2.6, are the first MA and AR filter coefficient
at each sample n. It can be seen that the prediction error e(n) and the filter coefficients
converge simultaneously. If e(n) has fully converged, so has the first MA filter
coefficient al and first AR filter coefficient bl, and vice versa. Also, it is apparent that
this process has not converged even after 1000 iterations. This is the slow convergence
property of the LMS algorithm that is well known.
Depicted in Figures 2.7, 2.8, and 2.9 are the prediction error e(n) and the first
MA and AR filter coefficient when processing the second input signal S2O1) via LMS.
28
It can be seen that this converges considerably faster than the Sj(n) example, but has
yet to fully converge on the input signal. This has a good amount to do with the center
frequencies of the two sinusoids being relatively close to each other in Hz. These
results were obtained by setting the constants in the LMS filter coefficient updating
equations to the following : (8 = 0.00), (a = 0.008), (P = 0.002). Again it can be
seen that the MA and AR filter coefficients for the input signal S2(n) have not
converged either, even after 2000 iterations of the ADPCM system.
LMS Leakage factor = 0.000000 ALPHA = 0.008000 BETA = 0.002000
Figure 2.5 S^n) First LMS MA Filter Coefficient al
29
Encoder/Decoder AR coefficient bl
LMS Leakage factor = 0.000000 ALPHA = 0.008000 BETA = 0.002000
Figure 2.6 S^n) First LMS AR Filter Coefficient bl
30
Encoder/Decoder MA coellident al Encoder prediction error
n
Figure 2.7 S2(n) LMS Prediction Error e(n)
LMS Leakage factor = 0.000000 ALPHA = 0.008000 BETA = 0.002000
Figure 2.8 S2(n) First LMS MA Filter Coefficient al
31
LMS Leakage factor = 0.000000 ALPHA = 0.008000 BETA = 0.002000
Figure 2.9 S2(n) First LMS AR Filter Coefficient bl
The software which was written to provide the simulation results depicted in
this section may be found in Appendix A : LMS Adaptive Prediction.
2.2 Adaptive Prediction via the Fast Conjugate Gradient Algorithm
Figure 2.1 changes slightly when utilizing the FCG algorithm to update the
filter coefficients as mentioned in Chapter 1. Figure 2.10 depicts this change which is
to simply rearrange the subtraction that takes place to determine the prediction error
e(n).
The best FCG processing results for the input signal S^n) were found when
the forgetting factor X was set to 0.995 and the stability constant Â£ was set to
32
- 1.0 x 10-34. Equations (2.7) through (2.15) define the FCG algorithm as used to arrive
at the results depicted in Figures 2.11,2.12, and 2.13, and are performed in the order
stated, once per sample n. All appropriate values are set to zero upon initialization of
the algorithm. The algorithm is defined by the following:
if ||g( + l)ll2 > llÂ£()ll2, d{n) = -g(n + 1) else d(ri) = -g(n + 1) + $d(n 1) (2.10)
Update vector A with current prediction error and reconstructed signal value (2.14)
Note that Sp(n) as defined in (2.6) is in reality that quantity defined in (2.16).
The vector A contains the previous six prediction errors followed by the previous two
(Sj(n)) or four (S2(n)) reconstructed signal values. The vector x contains all Z (6) MA
filter coefficients followed by all P (two for Sj(n) or four for S2(n)) AR filter
coefficients, and
Figure 2.11 depicts the prediction error e(n), in the absence of quantization
e(n) = AT(ri)x(ri) S(n)
(2.7)
g(n + 1) = 0.995 (g(n) + ap(ri)) + e(n)A(n)
e>T(n 4- 4- 1^\
(2.8)
(2.9)
p(n) = Q(n)d(n)
_ gT(n + l)g(* + 1)
(2.11)
dT(n)p(ri) + 1.0 x lO"34
x(n + 1) = x(n) + ad(n)
(2.12)
(2.13)
Q(n + 1) = 0.995 Q(n) + A(n + 1 )AT(n + 1)
(2.15)
Spin) = AT(n)x(n) .
(2.16)
33
noise, using the FCG algorithm to update the filter coefficients. It is seen that this
method fully converges in a very short period of time. This is also directly reflected in
the convergence characteristics of both the first MA filter coefficient al and first AR
filter coefficient bl as indicated in Figures 2.12 and 2.13. These results show a
Transmitter
Figure 2.10 ADPCM FCG Transmitter without Quantizer
significant speed of convergence improvement over the LMS method of updating the
filter coefficients for 1-Dimensional highly correlated input signals such as human
speech.
The results with respect to the input signal S2(n) are depicted in Figures 2.14,
2.15 and 2.16. These also show a great improvement over the LMS method. These
results were obtained with the forgetting factor X and the constant e unchanged from
34
Encoder prediction error
the previous simulation parameters chosen, 0.995 and 1.0 x 10'34 respectively.
FCG Prediction error e(n) al the encoder
Figure 2.11 Sj(n) FCG Prediction Error e(n)
35
Encoder/Decoder MA coefficient al
FCG Lambda = 0.995000 Epsilon = 1e-034
Figure 2.12 Si(n) First FCG MA Filter Coefficient al
36
Encoder/Decoder AR coefficient bl
FCG Lambda = 0.995000 Epsilon = 1e-034
37
Encoder predidion error
FCG Prediction error e(n) at the encoder
Figure 2.14 S2(n) FCG Prediction Error e(n)
38
Encoder/Decoder MA coetticient al
FCG Lambda = 0.995000 Epsilon = 1e-034
Figure 2.15 S2O1) First FCG MA Filter Coefficient al
39
FCG Lambda = 0.995000 Epsilon = 1e-034
Figure 2.16 S2(n) First FCG AR Filter Coefficient bl
Due to the impressive convergence characteristics of the FCG algorithm in the
ADPCM context, all subsequent chapters will focus on the FCG algorithm for filter
coefficient updating. The next chapter discusses the convergence characteristics of the
FCG algorithm in the presence of 1-Dimensional quantization noise.
The software which was written to provide the simulation results depicted in
this section may be found in Appendix B : FCG Adaptive Prediction.
40
3 1-Dimensional Quantization
Chapter 2 discussed the convergence characteristics of an ADPCM system
utilizing the Least Mean Squares (LMS) or Fast Conjugate Gradient (FCG) algorithm
to update the Moving Average (MA) and Auto Regressive (AR) filter coefficients in
the absence of quantization. This chapter is intended to highlight the damaging effects
of quantization noise on the convergence characteristics of an ADPCM system. This
and subsequent chapters will solely investigate the use of the FCG algorithm in the
adaptive prediction portion of the ADPCM process.
The quantizer portion of an ADPCM system exists only on the transmitter
(encoder) side of an ADPCM communications channel as depicted in Figure 1.2. This
particular portion is depicted in Figure 3.1. The quantizer maps a given range of
e(n)
Quantizer
eq(n)
---------
Figure 3.1 ADPCM Quantizer
prediction error values e(n) to a specific quantized prediction error value eq(n) which
may be communicated to the receiver in a manner which reduces the bit transmission
rate requirements of the communications channel. Table 1.1 depicts this mapping of
e(n) to eq(n) for an example data set. For example, Table 1.1 indicates that for a given
range of values of the actual prediction error e(n), 0.0005 <= e(n) < 0.000643, the
quantized prediction error eq(n) = 0.000572. This relationship between e(n) and eq(n)
41
is conceptually modelled in Figure 3.2.
Cq(n)
e(n)
Figure 3.2 Plot of eq(n) vs. e(n)
The quantization portion of an ADPCM system reduces bit transmission rate
requirements since the actual quantized prediction error value 0.000572 is not sent to
the receiver. The quantization level 4 (IOO2) indicated is sent to the receiver instead of
the actual quantized prediction error itself. It can be seen that the bits required to
transmit the quantized prediction error 0.000572 (much more than 3 bits) would be
much higher than that of the quantization level (3 bits) which indicates the quantized
prediction error. The quantization portion of an ADPCM communications system is
therefore the place where the greatest reduction in bit transmission rates may be
realized.
In the above example, the quantization level (4) is transmitted to the receiver,
while both the transmitter (encoder) and receiver (decoder) use the quantized
prediction error defined for quantization level 4,0.000572, to update their respective
42
filter coefficients. This is what takes place in an ADPCM communications system in
the presence of quantization.
This chapter will investigate the performance of a 1-dimensional ADPCM
communications channel in the presence of quantization noise. Quantization noise,
L(n), is simply the difference between the quantized prediction error eq(n) and the
actual prediction error e(n) per sample n, as defined by
L(n) = eq(n)-e(n) . (3.1)
The quantization noise present in an ADPCM system may have adverse effects
on both the speed of convergence and the stability of the system. This quantization
noise causes a loss of optimality in the adaptation provided by the FCG algorithm.
This is due to the fact that the quantized prediction error eq(n) is passed through to the
prediction process, instead of the prediction error e(n) itself. The quantization noise in
a system may also grow to such an extent that the prediction portion of the ADPCM
process totally loses its ability to track the input signal and this is when the ADPCM
system will become unstable and useless.
There are several measures which may be taken to assist the ADPCM system
in maintaining the system stability. One method which has been put to use in the
computer simulations discussed in later sections is to simply check the predicted
signal value Sp(n) before attempting to compute the prediction error e(n) at sample n.
It is assumed that the input signal characteristics, namely the minimum and maximum
values that the signal is expected to take on, are known in an a priori sense, and are
therefore also identically known by the transmitter and receiver sides of an ADPCM
system. The stability check performed at each sample n, on both transmitter and
receiver sides, simply adjusts the predicted signal value to be within the range of
43
expected signal values, if the predicted signal value strays outside of this range. For
example, if the expected range of sampled signal values for a given input signal is [-
1,1], and the predicted signal value at some sample n is 1.5, the ADPCM system uses
1 as the predicted signal value for that sample n instead of 1.5. Similarly, if the
predicted signal value at some sample n is -1.25, the ADPCM system uses -1 as the
predicted signal value for that sample n instead of -1.25. Computer simulation results
have shown that the incorporation of this simple rule into an ADPCM communications
channel yields both increased system stability and reduced quantization noise.
In this chapter, two methods of quantization will be investigated, non-adaptive
and adaptive quantization. The results of computer simulations performed to
investigate the overall performance of an ADPCM system utilizing these quantization
schemes will also be presented.
3.1 Non-Adaptive Quantization
Non-adaptive quantization is a quantization scheme which does not change
over time under any circumstances. A quantization scheme of this type ignores
changes in quantized prediction errors and reconstructed signal values and does not
vary in time. This section will highlight the ease of implementing a quantization
scheme of this type and its convergence performance characteristics.
Since a non-adaptive quantization scheme does not change over time, it is
defined in an a priori sense and is thus identically known by the transmitter (encoder)
and receiver (decoder) at all times. An example of this would be an ADPCM system
utilizing non-adaptive quantization which intends to provide a fixed bit transmission
rate of say, 3 bits per sample n. Assume for this example that the valid range of inputs
to this system is [-1,1], as in a simple sinusoid. In this case, a non-adaptive
44
quantization scheme as depicted in Table 3.1 may be utilized.
Table 3.1: Quantized Prediction Error vs. Prediction Error
e(n) >= e(n) < eq(n) Codeword Transmitted to Receiver
-0.8571 -1.0 0002 = 0
-0.8571 -0.5714 -0.7143 0012= 1
-0.5714 -0.2857 -0.4286 0102 = 2
-0.2857 0.0 -0.143 0112 = 3
0.0 0.2857 0.143 *r 11
0.2857 0.5714 0.4286 1012 = 5
0.5714 0.8571 0.7143 1102 = 6
0.8571 1.0 1112 = 7
As mentioned previously, a range of values of e(n) maps to a single value of
eq(n). For example, when 0.2857 <= e(n) < 0.5714, the value 5 (IOI2) is transmitted to
the receiver and the quantized prediction error eq(n) takes on the value 0.4286.
This non-adaptive quantization scheme is easily implemented for any given
input signal characteristics and desired fixed bit transmission rate. Given a known
maximum sampled signal value max(S(n)), minimum sampled signal value min(S(n)),
and desired number of bits (b) to transmit to the receiver per sample n, the
quantization levels for this quantization scheme may be computed as follows:
0 transmitted to receiver indicates eq(n) = min(S(n))
2b -1 transmitted to receiver indicates eq(n) = max(S(n)).
The quantization step size is given by
45
. max(S(n)) min(S(n))
2b-\
(3.2)
Of course, the range of values of e(n) which maps to any given eq(n) is chosen to
minimize the quantization noise. Each range is defined such that the exact middle of
the range is the quantized error value eq(n).
In this section computer simulation results will be presented for the input
signals Sj(n) and S2(n) as described in Chapter 2. Fixed transmission rates of 8,5, and
3 bits per sample n will be considered utilizing the non-adaptive quantization scheme
just described.
Figures 3.3 and 3.4 illustrate the prediction error e(n) and the quantized
prediction error eq(n) respectively, utilizing a fixed bit transmission rate of 8 bits per
sample n, for the input signal Sj(n) defined below
5j(/i) = sin (27tnl511/8000) . (3.3)
2
In this case A becomes - = 0.007843. It can be seen that the predicted
signal value Sp(n) basically fully converges on the input signal Si(n), since the
difference between the two, the prediction error e(n), is driven to zero after about 70
iterations of the ADPCM system. The quantized prediction error eq(n) begins to
illustrate the presence of the discrete quantization levels. Figures 3.5 and 3.6 indicate
the convergence characteristics of the first Moving Average (MA) and Auto
Regressive (AR) FCG filter coefficients. These coefficients converge as e(n)
converges, but this convergence is directly affected by the quantization noise
introduced by the quantization scheme in place. For the S^n) 8 bit transmission case,
the maximum quantization noise at a typical sample n would be ^ = 0.00392, a
fairly small number. It will be shown that as increases, the speed
46
Encoder prediction error
FCG Prediction error e(n) at the encoder # bits = 8
47
Encoder quantization error
of convergence of the ADPCM system decreases.
FCG Encoder Quantization error eq(n) # bits = 8
48
Encoder/Decoder MA coefficient al
FCG Lambda = 0.995000 Epsilon = 1e-034
49
FCG Lambda = 0.995000 Epsilon = 1e-034
Figure 3.6 Sj(n) First AR Filter Coefficient bl (b = 8)
Figures 3.7 and 3.8 illustrate this same prediction error and quantized
prediction error utilizing this non-adaptive quantization scheme with a fixed
transmission rate of 5 bits per sample n. It can be seen that the prediction error
converges to within a small tolerance, but cannot fully converge due to the increased
level of quantization noise introduced by the quantization scheme. This becomes more
apparent in Figures 3.9 and 3.10 which are the results of this quantization scheme
using only 3 bits per sample n.
50
Encoder prediction error
FCG Prediction error e(n) at the encoder # bits = 5
Figure 3.7 S^n) Prediction Error e(n) (b = 5)
51
FCG Encoder Quantization error eq(n) # bits = 5
These results show the effects of quantization noise on the ADPCM system
while transitioning from an 8 to a 5 to a 3 bit quantizer. As the number of bits in the
quantizer decreases, the quantization noise present in the ADPCM system increases,
and the speed of convergence of the ADPCM system, or its ability to track or adjust to
changes in the input signal, slows down or decreases.
52
1.5
FCG Prediction error e(n) at the encoder # bits = 3
-1.5,
*Qt+/***
lNT'**
100 200 300 400 500 600 700 800
Iteration (n) # Zeroes = 6 # Poles = 2
900
1000
Figure 3.9 Si(n) Prediction Error e(n) (b = 3)
Comparing Figures 3.9 and 3.3 it can be seen that the 8 bit quantizer provides a
much faster speed of convergence (about 70 iterations), while the 3 bit quantizer
requires about 500 iterations before it appears to have converged or stabilized.
This again is due to the quantization noise present in the system. The typical
maximum quantization noise introduced into the system is ^ = 0.00392 for the
A ^
implemented 8 bit quantizer, but is = 0.143 for the implemented 3 bit quantizer.
This is a difference of roughly 2 orders of magnitude and as seen, has significant
impacts on the speed of convergence of the ADPCM system.
53
FCG Encoder Quantization error eq(n) # bits = 3
1 -------1--------1-------1-------1--------1-------1-------1--------r
0.8
0.6
-0.8
'o 100 200 300 400 500 600 700 800 900 1 000
Iteration (n)# Zeroes = 6 # Poles = 2
Figure 3.10 SjCn) Quantized Prediction Error eq(n) (b = 3)
Figures 3.11 and 3.12 depict the prediction error e(n) and quantized prediction
error eq(n) for the input signal S2(n) utilizing a fixed transmission rate of 8 bits per
sample n. Similarly, Figures 3.13 and 3.14 depict those same errors with a fixed
transmission rate of 3 bits per sample n.
The differences in terms of speed of convergence of the ADPCM system
between the 8 bit and 3 bit quantization schemes is again very apparent.
54
FCG Prediction error e(n) at the encoder# bits = 8
200
400
600 800 1 000 1 200 1 400 1600 1 800 2000
Iteration (n) # Zeroes = 6 # Poles = 4
Figure 3.11 S2(n) Prediction Error e(n) (b = 8)
55
Encoder quantization error
FCG Encoder Quantization error eq(n) # bits = 8
56
Encoder prediction error
8
T
FCG Prediction error e(n) at the encoder# bits = 3
t--------1-------1--------1-------1--------1-------1--------r
60 200 400 600 800 1000 1200 1400 1600 1800 2000
Iteration (n) # Zeroes = 6 # Poles = 4
Figure 3.13 S2(n) Prediction Error e(n) (b = 3)
57
o
73
.td
O
TD
8
C
UJ
Iteration (n) # Zeroes = 6 # Poles = 4
Figure 3.14 S2(n) Quantized Prediction Error eq(n) (b = 3)
The next section will investigate the use of adaptive quantization methods to
provide more extensive convergence on the input signal. This will simply be
accomplished by reducing the quantization noise present in the ADPCM system as
much as possible.
3.2 Adaptive Quantization
In this section an adaptive quantization scheme modified from that discussed in
[5] will be presented. These modifications force the quantizer to adapt only when
certain conditions are met. These conditions are of course defined in an a priori sense
and both the transmitter and receiver are aware of these before active communication
takes place across an ADPCM communications channel. These conditions simply
dictate when and how the quantizer will adapt.
58
This adaptation is truly directed at the values which the quantized prediction
error eq(n), may take on. This is depicted in Figure 3.15. It is for this reason that both
the transmitter and receiver must simultaneously adapt to changes in eq(n). Changes in
eq(n) are the driving force in this adaptive quantization scheme. The major difference
between this scheme and a non-adaptive scheme is that a non-adaptive scheme ignores
changes in eq(n) and Sr(n) while an adaptive scheme does not.
Figure 3.15 ADPCM Adaptive Quantizer
Let V(n) indicate the possible quantized prediction error values eq(n) at sample
n. This quantization scheme looks much like that in [5],
V(n + 1) = MdV(n) (3.4)
where a < Md < b. The implemented scheme discussed here does allow Md to adapt
within the imposed constraints, yet restricts Md to take on only a few discrete values
between a and b as opposed to any value between a and b. In other words, 0 < d <= N,
where N may be on the order of three, four, or five. For example, if N = 3, V(n) at any
sample n may be one of three possible depths of quantization. Each depth of
quantization, d = 1,2,3 in this example, indicates a different range of possible
quantized prediction error values eq(n).
Assume for the simple sinusoid S^n) and a fixed bit transmission rate of 3 bits
per sample n, Tables 3.1 (1.2), 1.3, and 3.2 indicate the quantization schemes to be
59
used for the various depths 1,2, and 3. This shows that Mj = 1, M2 = 0.1429, and M3
= 0.0204. What this also indicates is that the quantized prediction error eq(n) at any
one sample n, must be one of the eq(n) values listed in tables 1.2,1.3, or 3.2. No other
values of eq(n) are allowed. Both transmitter and receiver are initialized using the first
quantization depth as listed in Table 1.2.
The quantization depth, and thus the quantizer, are allowed to adapt via the
following rules or conditions. If the quantized prediction error at sample n indicates
that a three or a four is to be transmitted to the receiver (the minimum absolute value
of all quantized prediction errors for that depth), the transmitter knows to switch
down one level from depth one to depth two, or from depth two to depth three, at
sample (n + 1). When the receiver receives the 3 or 4, it too knows to switch down one
quantization depth at sample (n + 1). Similarly, if the quantized prediction error at
sample n indicates that a 0 or a 7 is to be transmitted to the receiver (the maximum
absolute value of all quantized prediction errors for that depth), the transmitter
knows to switch back one level from two to one or from three to two at sample (n + 1).
60
Consequently, the receiver is aware of the depth change by the receipt of the 0 or 7.
Table 3.2: Quantization Leveling Scheme Third Depth
e(n) >= e(n) < eq(n) Codeword Transmitted to Receiver
-0.0175 -0.0204 o ii ts 8 o
-0.0175 -0.0117 -0.0146 0012= 1
-0.0117 -0.00584 -0.00874 0102 = 2
-0.00584 0.0 -0.00291 0112 = 3
0.0 0.00584 0.00291 tj- n
0.00584 0.0117 0.00874 II ~~
0.0117 0.0175 0.0146 VO II CN 0 ^H 1 1~~
0.0175 0.0204 1112 = 7
It is this very simple scheme which has been employed in general for both the 1-
Dimensional and 2-Dimensional ADPCM computer simulations. Figures 3.16 and
3.17 depict the prediction error e(n) and the adaptive quantized prediction error eq(n)
utilizing the adaptive quantization scheme described above with a fixed bit
transmission rate of 3 bits per sample n while processing the input signal SjCn).
61
FCG Prediction error e(n) at the encoder
It can be seen that the system converges on the input signal Sj(n) after
approximately 250 iterations, while the non-adaptive case (Figure 3.9) requires some
500 or so iterations before relative convergence is attained. This is a significant
improvement and is caused by the reduction in quantization noise introduced into the
system. This reduction is achieved by adapting the quantized prediction error eq(n) via
the quantizer portion of the ADPCM process. In this case, the maximum absolute
value of the quantization noise may vary between 0.1429 > x > 0.00292 at any
sample n. This adaptation is also easily observed in Figure 3.17, where the quantized
error values are very different in samples 1-125 than they are in samples 300-400. It
can be seen in these two portions of the quantized prediction error samples how the
quantized prediction error levels may change over time.
62
1
FCG Encoder Adaptive Quantization error eq(n)# bits = 3 # depths = 3
0.8
0.6
-Â§ -0.2
8
^ -0.4
-0.6
-0.8
'10 100 200 300 400 500 600 700 800 900 1000
Iteration (n) # Zeroes = 6 if Poles = 2
Figure 3.17 Sj(n) Adaptive Quantized Prediction Error eq(n) (b = 3)
These results indicate that for a signal sampled at 8k Hz such as speech, only 3
bits of information need to be communicated from transmitter to receiver at each
sample n. These results show that a 64k bits per second signal (e.g. 8 bits of speech
data per sample, 8000 samples per second) may be suitably compressed down to 24k
bits per second (i.e. 3 bits of speech data per sample, 8000 samples per second), which
is an interesting result for those in the telephony business.
The software written to produce the results seen here in section 3.2 may be
found in Appendix D : FCG 1-Dimensional ADPCM Simulation Results.
63
4 2-Dimensional Signal Compression via ADPCM
Thus far, the discussions have focused on 1-Dimensional ADPCM processing.
In this chapter the focus will be directed entirely at 2-Dimensional signal sources,
namely images. 2-Dimensional image compression is simply an extension of the 1-
Dimensional case, but may not be thought of as 1-Dimensional compression of a 2-
Dimensional input data stream. In other words, the 2-Dimensional input signal may
not be converted to a 1-Dimensional signal and processed via 1-Dimensional ADPCM
signal compression techniques. 2-Dimensional data is context sensitive, a sampled
signal value typically looks very similar to sampled signal values in a close
neighborhood to itself.
This section is devoted to highlighting the fundamentals of 2-Dimensional
Signal Compression in the ADPCM context utilizing the Fast Conjugate Gradient
(FCG) algorithm to update the filter coefficients. This section will also only consider
using an adaptive quantizer, very similar to that found in section 3.2, for the sole
purpose of reducing quantization noise, and thus increasing the signal-to-noise ratio
between the source image matrix and the received image matrix. The ADPCM
processing utilized in this chapter is identical to that depicted in Figures 1.5 and 3.15.
The images discussed in this chapter are digital images, comprised of many
pixels such as those visible on a television screen or computer monitor. Each image
is a collection of pixels where each pixel represents some small subset of the original
picture which has been digitized. Each pixel is then a sampled version of a very small
subset of a given image. The images used in the computer simulations presented in
this chapter are thus the sampled input signals to the ADPCM process. The sample
64
images used for these simulations are in general 200 by 320 pixels.
Each image is stored as a matrix of colormap indices. Therefore, each pixel
position contains a colormap index which indicates to a television, or in this case a
computer monitor, the color in which the given pixel is to be rendered. For example, if
an image matrix contains the value 25 at position (2,3), this indicates to the monitor
that the pixel located at row 2, column 3, is to be rendered in the color known to the
monitor as 25. An example of this relationship is depicted in Figure 4.1. This
colormap index of 25 indicates to the monitor to render the given pixel in the
appropriate Red Green Blue (RGB) mixture as defined by colormap index 25. The
colormap used for a given image may then specify that colormap index X is light blue,
and that colormap index (X + 1) is dark blue, just by simply defining the appropriate
RGB values for colormap indices X and (X + 1). The colormap indices present in an
image matrix are thus the sampled input values S(row,column) to the ADPCM process
discussed in this chapter.
Image Matrix
Colormap Index R Color Definition G B
24 0.1 0.4 0.7
25 - 0.2 0.5 0.8
26 0.3 0.6 0.9
Figure 4.1 Relationship between Pixel Colormap Index and Rendered Pixel Color
The colormap indices present in an image matrix are typically based upon a
colormap defined specifically for that image. The colormap which is actually used for
65
the graphical depiction of an image may be different than the one specifically defined
for the image, however. Given this flexibility, a gray scale colormap defininition will
be used for all computer simulations presented in this chapter. This will not affect the
computed signal-to-noise ratios presented later, but will have an interesting effect on
the graphical depiction of the transmitted and received images. This effect is due to the
fact that the source image matrix may have a more extensive colormap index range
than the gray scale colormap being used actually supports. What this means then, is
that two pixels with different colormap indices may appear as the same gray scale
color when rendered using the gray scale colormap definition. For example, if two
adjacent pixel positions in the source image matrix are 73 and 74, these may both be
rendered as colormap index 56 as the gray scale colormap only supports indices in the
range [1,64]. The primary benefit to using this gray scale colormap definition is that
this colormap has been defined where index 1 indicates pure black and index 64
indicates pure white, with very small shade changes taking place between each actual
colormap index shade. Therefore, small differences in pixel colormap indices between
transmitted and received images are difficult to detect by the human eye.
The FCG algorithm may be basically used as previously described in section
1.1.2 with simple notation changes as described in [6]. The primary difference
between 1-Dimensional and 2-Dimensional FCG processing is the manner in which
the x vector (filter coefficients) and A vector (quantized prediction errors and
reconstructed signal values) are populated. The notion of the Moving Average (MA)
and Auto Regressive (AR) portions remains with a slight modification. If the order of
the MA filter coefficients is three, then the MA portion of the x and A vectors within
the FCG algorithm are comprised of 32 -1 = 8 individual values. These values
represent the 3X3 matrix of filter coefficients and quantized prediction errors which
surround the given pixel position which is to be predicted next. Figure 4.2 depicts the
66
MA portion of the FCG A vector at sample i = row, j = column. This also highlights
the neighborhood of interest relative to a sample at row i and column j with regard to
quantized prediction errors eq(i,j) and signal reconstructed values Sr(i j). The AR
portion works very similarly as just described with N2 -1 individual values in the x
and A vectors following the MA portion, if the AR order is N.
FCG A Vector
MA portion of interest of quantized prediction error matrix
eq(i,j-1)
eq(i,j-2)
eq(i- l,j)
eq(i-1, j -1)
eq(i- l,j-2)
eq(i-2,j)
eq(i 2, j -1)
eq(i 2, j 2)
Sr(i,j-1)
Figure 4.2 Population of FCG A Vector with Quantized Prediction Errors
Given the above mechanism for updating the 2-Dimensional filter coefficients,
the model used is a linear ARMA predictor similar to that discussed in [7]. The
predicted pixel value for pixel (i,j) is in general defined by the linear ARMA predictor
as
(22
\
X X ee(i-kj-[)a(i-k,j-l)
v Jt = 0/ = 0 )
+
(22
\
X Xsrii-k,j-m-k,j-D
'k = 01 = 0 '
(4.1)
67
- where the summations going from 0 to 2 indicate the order of the Moving Average (3)
or the Auto Regressive (3) portion of the 2-Dimensional model. Note that all terms
are included in the summation with the exception of the k = 1 = 0 case. This term is
removed from the summation since k = 1 = 0 indicates the pixel position currently
being predicted. This is a well known implementation concern in 2-Dimensional
signal processing and is known as the (1,1) delay.
The implementation of this linear ARMA predictor removes the need for the
filter coefficients (x) and the previous quantized prediction errors and reconstructed
pixel values (A) to be stored as matrices. Again, A is stored as depicted in Figure 4.2
and x is represented as
x = [a(i, j -1) a(i, j 2)... a(i 2, j 2) b(i, j -1)... b(i 2, j 2)]T. Therefore the
predicted pixel value for pixel (i,j) is found exactly as described in the 1-Dimensional
case as
Sp(i,f) = ATx . (4.2)
This implementation directly reflects the model defined in (4.1), without the
computational overhead of matrix multiplications. All computer simulation results
presented later are based upon this model.
The manner in which the source image matrix is traversed is typically left to
right, top to bottom. This traversal order dictates how the A vector, on both the
transmitter and receiver sides of an ADPCM communications channel, is populated at
each sample (i, j). As noted previously, the A vector is updated near the completion of
processing for sample (i, j). The A vector is populated with the appropriate values
assuming that the next pixel position to predict is (i, j + 1). In the case where (j + 1)
extends beyond the width of the image matrix, the next pixel position to predict
68
becomes (i + 1,1). This population must also take into account where the MA or AR
portion of interest may extend outside the bounds of the image matrix. This is done
fairly simply and in these cases, any (i k), (j -1) which extend outside the image
matrix bounds have the corresponding individual value set to zero. This then describes
how the FCG A vector, on both the transmitter and receiver sides, is updated before
attempting to predict the next pixel colormap index. The FCG algorithm itself takes
care of the appropriate modification to the x vector (filter coefficients) just as in the 1-
Dimensional case.
The adaptive quantization scheme used in all of the following computer
simulations is very similar to that detailed in section 3.2. In this section, discrete
quantization levels and depths will again be employed to adapt the quantized
prediction error eq(i,j) for a given sample i, j. The adaptive quantizer implemented in
the 2-Dimensional computer simulations has undergone slight modification. Assume
that the transmission rate is desired to be three bits per sample i, j. Assume also for
example that two depths of quantization levels are to be used. Lastly, assume that
the range of colormap indices for a given type of image is [1,81]. The adaptive
quantization scheme employed here is defined in Tables 4.1 and 4.2.
69
Note that all quantized prediction error values eq(i,j) are integers since the colormap
Table 4.1: 2-D Quantization Leveling Scheme First Depth
e(i,j) >= e(i,j) < eq(i,j) Codeword Transmitted to Receiver
-69 I OO o o II
-69 -46 -57 0012= 1
-46 -23 -34 0102 = 2
-23 0 -11 0112 = 3
0 23 11 Ti- ll ts O O *H
23 46 34 H-4 o 4 to II Lrt
46 69 57 1102 = 6
69 80 1112 = 7
indices found in an image matrix are also integers. This is done in an attempt to further
reduce quantization noise introduced into the ADPCM system.
Table 4.2: 2-D Quantization Leveling Scheme Second Depth
e(i,j) >= e(i,j) < eq(i,j) Codeword Transmitted to Receiver
-34 -40 o o o to II o
-34 -23 -29 0012 = 1
-23 -11 -17 0102 = 2
-11 0 -6 0112 = 3
0 11 6 1002 = 4
11 23 17 1012 = 5
23 34 29 1102 = 6
34 40 1112 = 7
70
The quantization levels are defined by the following. Let XI be the minimum
colormap index expected for a given type of image. Let X2 be the maximum colormap
index expected for that same type of image. The maximum quantized prediction error
found in the first depth should then be X2 XL In the above case, for the Clown
image, this is 81 -1 = 80. The minimum quantized prediction error, zero transmitted to
the receiver, is simply the additive inverse of the maximum quantized prediction error,
or -80. Each quantization level in between the minimum and maximum quantized
prediction errors are separated in value by
2QC2-X1)
2*-l * '
where b is the number of bits to be transmitted to the receiver per sample i, j. This is
the definition of the first depth. The second and subsequent depths each divide the
range covered by the previous depth by two. This is why Table 4.2 covers the range
[-40,40]. Note that (4.3) is used to define the quantization levels for each depth
implemented in the scheme. In this manner, an N depth scheme of this type is very
easily implemented.
Given these depths of quantization levels, adaptation of the quantizer and thus
the quantized prediction errors takes place when the quantized prediction error at
sample (i, j), eq(i, j), is smaller in absolute value than the maximum quantized
prediction error at the next depth. This is very similar to the adaptation strategy
discussed and implemented in section 3.2. Once the quantized prediction error at a
sample (i, j) becomes less than the maximum quantized prediction error of the next
depth down, the transmitter and receiver both know to use the next depth down, if one
exists, for the next sample pixel to be processed. Identically to section 3.2, when a zero
or a 2b -1 (b = 3 ==> seven in the above example) is transmitted to the receiver, the
transmitter and receiver both know to use the next depth up, if one exists, for the next
71
sample pixel to be processed. It is this scheme, using depths of three, four, or five, that
has been used to produce the computer simulation results that follow.
We have now arrived at another significant part of this document, the computer
simulation results of ADPCM image compression using the FCG algorithm and the
adaptive quantization scheme just described. Figure 4.3 depicts the digital image,
Clown, which is 200 by 320 pixels, and has a range of colormap index values of [1-
81]. This image was processed using ADPCM, the FCG algorithm to update the filter
coefficients, and the adaptive quantization scheme all as described in this chapter.
Figure 4.4 depicts the received image transmitting three bits per sample (i, j), and
using three quantization depths as described in this chapter. The signal-to-noise ratio
of the received image is computed as,
72
FCG Original Image C:\MATLAB\TOOLBOX\MATLAB\DEMOS\CLOWN.MAT
Horizontal Pixel Positions
Figure 4.3 Original Digital Image of Clown
S
N
YZ&V'j)
, j___
EE (S(i,j)-R(i,j))
2
(4.4)
where S is the original digital image, R is the received digital image, and i = 1,2,
vertical pixel positions, j = 1,2,..., horizontal pixel positions. This number may then
be converted to decibels (dB) by 10*log10(S/N). The compression ratio 3:7 indicates
73
that three bits were transmitted to the receiver per seven sample bits detected in the
digital image matrix. In other words, the size required to store the digital image has
been reduced by 57.1%, at the cost of image quality which has been indicated by the
23.711 dB figure. Figure 4.5 depicts the error image (S R) resulting from this
ADPCM processing.
FCG Received image : Lambda = 0.985000 AR # 3 MA# 3
&N =23.711 dB
Figure 4.4 Received Digital Image of Clown
The image of Earth, depicted in Figure 4.6, which is also 200 by 320 pixels,
having a colormap index range of [1-64], was also processed in this same manner.
74
Figure 4.5 Clown Difference Image
75
FCG Original Image C:\MATLAB\TOOLBOXyyATLAB\DEMOStARTH.MAT
50 100 150 200 250 300
Horizontal Pixel Positions
Figure 4.6 Original Digital Image of Earth
It can be seen that the increased signal-to-noise (25.986 dB) ratio is due to the
vast black areas which appear to the left and right sides of the Earth. There is a large
amount of redundancy in these areas and the ADPCM process does a good job of
removing that redundancy.
76
Compression ratio 3:6
FCG Received image : Lambda = 0.985000 AR # 3 MA# 3
50 100 150 200 250 300
S/N =25.986 dB
Figure 4.7 Received Digital Image of Earth
77
FCG Original/Received image difference : Lambda = 0.985000 AR # 3 MA # 3
Depths = 3 Error Average = 0.008998 Error Variance = 2.333954
Figure 4.8 Earth Difference Image
Several compression ratios and adaptive quantization depth schemes were
simulated against the Clown, Earth, and Lena images. These results are summarized in
Table 4.3. It is worth mentioning that small changes to the parameter values used in
this processing such as the Lambda value or the manner in which quantization leveling
depths are determined will produce slightly different results possibly better, possibly
worse than that shown in Table 4.3. Determining these optimum parameter values is
78
image dependent
Table 4.3: 2-D ADPCM Compression Results
Image Compression Ratio 3 depth (dB) 4 depth (dB) 5 depth (dB)
Clown 5:7 26.641 21.413 18.951
200 x 320 4:7 26.096 21.405 18.816
[1-81] 3:7 23.711 21.150 18.851
2:7 17.656 18.769 17.773
Earth 5:6 34.368 26.467 23.074
200 x 320 4:6 30.201 26.387 23.125
[1-64] 3:6 25.986 25.161 22.763
2:6 18.493 21.546 21.204
Lena 5:8 40.679 33.725 28.053
480x512 4:8 35.819 33.135 27.927
[10-227] 3:8 29.859 31.277 27.387
2:8 21.562 25.889 25.725
These results indicate that using the FCG algorithm in the ADPCM context
with adaptive quantization yields very good signal-to-noise ratios in the lossy received
image. This may be sufficient for some applications given that some minimum signal-
to-noise ratio is provided in the received image on average. These results are also
interesting in comparison with other like-image results using the LMS algorithm in the
ADPCM context as found for example in [7]. In [7], Chung and Kanefsky make use of
the Woman test image for simulation purposes involving a two-bit quantizer. This
image is very similar to the Lena image used for simulation purposes here, yet the
79
Lena image appears to contain more edges and is in general busier (contains more
high frequency components) than the test image used in [7]. From these two different
results it can be seen that the results presented here offer a 9 db gain in signal-to-noise
ratio when comparing the two-bit quantization results with four depths (25.889 dB)
against those depicted in [7] (16.74 dB). Computer simulations of this Woman test
image would most likely yield two-bit quantization results in excess of 26 dB, again
due to the existence of fewer edges in the Woman test image. This then makes the
ADPCM processing techniques described in this chapter very attractive in terms of the
received image signal-to-noise ratio which is provided by its use.
The software written to provide these computer simulation results may be
found in Appendix E : 2-Dimensional FCG ADPCM Image Compression.
80
References
[1] Shomit M. Ghosh and Wasfy B. Mikhael, Two-Dimensional Optimal
Algorithms For Image Compression Using ARMA Predictors, ISCAS 94,
vol. 2, pp. 613-616,1994.
[2] Madeleine Bonnet, Odile Macchi, and Meriem Jaidane-Saidane, Theoretical
Analysis of the ADPCM CCITT Algorithm, IEEE Transactions on
Communications, vol. 38, pp. 847-857, June 1990.
[3] Peter M. Clarkson, Optimal and Adaptive Signal Processing, CRC Press, pp.
358-361,1993.
[4] Tamal Bose and Kyung Sub Joo, A Fast Conjugate Gradient Algorithm for
Adaptive Filtering, Department of Electrical Engineering, University of
Colorado at Denver, 7 February 1995.
[5] Craig R. Watkins, Robert R. Bitmead, and Sam Crisafulli, Destabilization
Effects of Adaptive Quantization in ADPCM, IEEE Transactions on Speech
and Audio Processing, vol. 3, pp. 137-141, March 1995.
[6] Kyung Sub Joo and Tamal Bose, A Fast Conjugate Gradient Algorithm for
2-D Nonlinear Adaptive Filtering, Department of Electrical Engineering,
University of Colorado at Denver, 7 March 1995.
[7] Young-Sik Chung and Morton Kanefsky, On 2-D Recursive LMS Algorithms
Using ARMA Prediction for ADPCM Encoding of Images, IEEE
Transactions on Image Processing, vol. 1, No. 3, pp. 416-421, July 1992.
81
Appendix A : LMS Adaptive Prediction
Appendix A contains the MATLAB source code files which were used to
produce the computer simulation results presented in section 2.1. The following
source code files are included:
lmsld.m
lmsadpcm.m
82
LMS1D.M
%
% A one dimensional ADPCM example using Least Mean Squares (LMS) to adapt
% the filter coefficients.
%
NUM_POLES = 2; % of the HR predictor
NUM_ZEROS = 6; % of the HR predictor
ALPHA = 0.008;
BETA =0.002;
MAXJTERATIONS = 1000;
%
% Construct a suitable input sequence
%
F = 1511; % In Hz
Fs = (2*F) + 5; % In Hz
index = 1;
for i = 1 :MAX_ITERATIONS,
sampled_signal_value(index) = sin(2*pi*i*F/Fs);
83
index = index + 1;
end
INPUT_SAMPLES_TO_PLOT = 50;
% Plot out the first few samples in the actual input signal sequence
plot(sampled_signal_value(l:INPUT_SAMPLES_TO_PLOT));
xlabel(n); ylabel(S(n));
str = sprintf(S(n) = sin(2*pi*n*%f/%f),F,Fs);
title(str);
print -dps lmsadpcm;
pause;
clg;
LEAKAGE_FACTOR = 0.0;
lmsadpcm(LEAKAGE_FACTOR,...
ALPHA,...
BETA,...
NUM_ZEROS,...
NUM_POLES,...
sampled_signal_value);
LEAKAGE_FACTOR = 0.05;
84
lmsadpcm(LEAKAGE_FACTOR,...
ALPHA,...
BETA,...
NUM_ZEROS,...
NUM_POLES,...
sampled_signal_value);
LEAKAGE.FACTOR = 0.005;
hnsadpcm(LEAKAGE_FACTOR,...
ALPHA,...
BETA,...
NUM.ZEROS,...
NUM.POLES,...
sampled_signal_value);
%
% Now, reconstruct the input with a different sampling frequency
%
F = 1511; % InHz
Fs = 8000; % In Hz
index = 1;
for i = 1 :MAX..ITERATIONS,
85
sampled_signal_value(index) = sin(2*pi*i*F/Fs);
index = index + 1;
end
% Plot out the first few samples in the actual input signal sequence
plot(sampled_signal_value(l:INPUT_SAMPLES_TO_PLOT));
xlabel(V); ylabel(S(n));
str = sprintf(S(n) = sin(2*pi*n*%f/%f),F,Fs);
title(str);
print -dps -append lmsadpcm;
pause;
clg;
LEAKAGE_FACTOR = 0.0;
lmsadpcm(LEAKAGE_FACTOR,...
ALPHA,...
BETA,...
NUM.ZEROS,...
NUM_POLES,...
sampled_signal_value);
LEAKAGE.FACTOR = 0.05;
86
lmsadpcm(LEAKAGE_FACTOR,...
ALPHA,...
BETA,...
NUM_ZEROS,...
NUM.POLES,...
sampled_signal_value);
LEAKAGE.FACTOR = 0.005;
lmsadpcm(LEAKAGE_FACTOR,...
ALPHA,...
BETA,...
NUM_ZEROS,...
NUM.POLES,...
sampled_signal_value);
%
% Construct another suitable input sequence
%
FI = 1501; % In Hz
F2 = 1080; % In Hz
Fs = 8000; % In Hz
MAXJTERATIONS = 2000;
87
index = 1;
for i = 1 :MAX_ITERATIONS,
sampled_signal_value(index) = sin(2*pi*i*Fl/Fs)+...
2.5 *sin(2*pi*i*F2/Fs);
index = index + 1;
end
% Plot out the first few samples in the actual input signal sequence
plot(sampled_signal_value(l:INPUT_SAMPLES_TO_PLOT));
xlabel(n); ylabel(S(n));
str = sprintf(S(n) = sin(2*pi*n*%f/%f) + 2.5sin(2*pi*n*%Wcf),Fl,Fs,F2,Fs);
title(str);
print -dps -append lmsadpcm;
pause;
clg;
NUM_POLES = 4;
LEAKAGEJFACTOR = 0.0;
lmsadpcm(LEAKAGE_FACTOR,...
ALPHA,...
88
BETA,...
NUM.ZEROS,...
NUM.POLES,...
sampled_signal_value);
LEAKAGE_FACTOR = 0.05;
lmsadpcm(LEAKAGE_FACTOR,
ALPHA,...
BETA,...
NUM.ZEROS,...
NUM.POLES,...
sampled.signal.value);
LEAKAGE.FACTOR = 2A(-7);
ALPHA = 3.2A(-8);
BETA = 2A(-7);
lmsadpcm(LEAKAGE_FACTOR,
ALPHA,...
BETA,...
NUM.ZEROS,...
NUM.POLES,...
sampled.signal.value);
LMSADPCM.M
%
% A one dimensional ADPCM example using the HR Least Mean Squares (LMS)
% algorithm to adapt the HR filter coefficients. This test ignores the quantization
% phase of ADPCM processing to determine the ability of the LMS algorithm in
% the absence of quantization noise.
%
% leakage_factor >= 0.0;
% alpha <1.0 (For redefining the numerator coefficients)
% beta <1.0 (For redefining the denominator coefficients)
% num_zeros = The number of desired zeros within the HR filter.
% num_poles = The number of desired poles within the HR filter.
% sampled_signal_value = An array of sampled inputs to pass through this
% ADPCM process.
function lmsadpcm(leakage_factor,...
alpha,
beta,
num_zeros,
num_poles,
sampled_signal_value)
number_of_iterations = size(sampled_signal_valuesr2); % # columns in row vector
encoder_A = zeros(num_zeros,l);
90
encoder_B = zeros(num_poles,l);
decoder_A = zeros(num_zeros,l);
decoder_B = zeros(num_poles,l);
encoder_tilde_S = zeros(num_poles,l);
encoder_errors = zeros(num_zeros,l);
decoder_tilde_S = zeros(num_poles,l);
decoder_errors = zeros(num_zeros,l);
BEGIN_ITERATION = 1;
for n = BEGIN_ITERATION:number_of_iterations,
encoder_predicted_value = (encoder_B*encoder_tilde_S) + .
(encoder_A *encoder_errors);
encoder_prediction_error(n) = sampled_signal_value(n) -...
encoder_predicted_va!ue;
encoder_tilde_sn = encoder_prediction_error(n) +...
encoder_predicted_value;
encoder_al(n) = encoder_A(l,l);
encoder_bl(n) = encoder_B(l,l);
encoder_A = ((1 leakage_factor)*encoder_A) +...
91
(alpha*encoder_prediction_error(n)*encoder_errors);
encoder_B = ((1 leakage_factor)*encoder_B) + ...
(beta* encoder_predic tion_error (n) *encoder_tilde_S);
encoder_tilde_S = [encoder_tilde_sn encoder_tilde_S(l:(num_poles 1))];
encoder_errors = [encoder_prediction_error(n) encoder_errors(l:(num_zeros
D)T;
decoder_tilde_sn = encoder_prcdiction_error(n) +...
(decoder_A*decoder_errors) +...
(decoder_B *decoder_tilde_S);
decoder_al(n) = decoder_A(l,l);
decoder_bl(n) = decoder_B(l,l);
decoder_A = ((1 leakage_factor)*decoder_A) +...
(alpha*encoder_prediction_error(n)*decoder_eirors);
decoder_B = ((1 leakage_factor)*decoder_B) +...
(beta*encoder_prediction_error(n)*decoder_tilde_S);
decoder_tilde_S = [decoder_tilde_sn decoder_tilde_S(l:(num_poles -1))];
decoder_errors = [encoder_prediction_error(n) decoder_errors( 1: (num_zero s
d_tilde_sn(n) = decoder_tilde_sn encoder_tilde_sn;
end
92
x = [BEGIN_r 1 fcRATTON :number_of_iterations];
% Plot differences between the al coefficient of the encoder and decoder
plot(x,encoder_al ,x,decoder_al);
xlabel(n); ylabel(Encoder/Decoder MA coefficient al);
str = sprintf(LMS Leakage factor = %f ALPHA = %f BETA = %f ...
leakage_factor,...
alpha,...
beta);
title(str);
print -dps -append lmsadpcm;
pause;
clg;
% Plot differences between the bl coefficient of the encoder and decoder
plot(x,encoder_b 1 ,x,decoder_b 1);
xlabel(n); ylabel(Encoder/Decoder AR coefficient bl);
str = sprintf(LMS Leakage factor = %f ALPHA = %f BETA = %f ,...
leakage_factor,...
alpha,...
beta);
title(str);
print -dps -append lmsadpcm;
pause;
93
clg;
% Plot the encoder side prediction error
plot(x,encoder_prediction_error);
xlabel(n); ylabel(Encoder prediction error);
title(LMS Prediction error e(n) at the encoder);
print -dps -append lmsadpcm;
pause;
clg;
% Plot the difference in the reconstructed signal on the encoder and
% decoder sides.
plot(x,d_tilde_sn);
xlabel(n); ylabel(Encoder/Decoder tilde s difference);
tide(LMS Difference in reconstructed signal between Encoder and Decoder);
print -dps -append lmsadpcm;
pause;
clg;
94
Appendix B : FCG Adaptive Prediction
Appendix B contains the MATLAB source code files which were used to
produce the computer simulation results presented in section 2.2. The following
source code files are included:
fcgld.m
fcgadpcm.m
95
FCG1D.M
%
% A one dimensional ADPCM example using the Fast Conjugate Gradient (FCG)
% algorithm to adapt the HR filter coefficients. This test ignores the
% quantization phase of the ADPCM process.
%
NUM_POLES = 2; % of the HR predictor
NUM ZEROS = 6; % of the HR predictor
MAXJTERATIONS = 1000;
% Construct a suitable input sequence
F = 1511; % In Hz
Fs = 8000; % (2*F) + 5; % In Hz
index = 1;
for i = 1 MAXJTERATIONS,
sampled_signal_value(index) = sin(2*pi*i*F/Fs);
index = index + 1;
96
~~
~~ |