Image compression method and apparatus employing distortion adaptive tree search vector quantization with avoidance of transmission of redundant image data

• US 5,247,357 A
• Filed: 11/19/1991
• Issued: 09/21/1993
• Est. Priority Date: 05/31/1989
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Scientific-Atlanta Incorporated (Cisco Systems, Inc.)
• Inventors: Israelsen, Paul D.
• Primary Examiner(s): Kostak, Victor R.
• Application Number:
  US07/794,589
• Time in Patent Office: 672 Days
• Field of Search: 358/133, 358/135, 358/136, 375/122, 381/31, 381/32, 341/106
• US Class Current: 375/240.12
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 7/10 Adaptations for transmission by electrical cable H04N7/12 takes precedence
• CPC Class Codes: H04N 7/20 Adaptations for transmission via a GHz frequency band, e.g. via satellite

Abstract

A variable rate vector quantization apparatus and method employs a tree structured codebook. Code vectors are selected from different levels of the codebook according to the value of a threshold. The value of the threshold is periodically adjusted according to the fullness of a buffer that stores vector quantized data to be transmitted. According to the invention, vector quantized data for redundant, or similar, vectors is not transmitted. Rather, a "copy last vector" instruction is transmitted for these vectors to achieve further data compression. A method of mean removal from vectors to be vector quantized is also disclosed.

Claims

1. In a Vector quantization encoder of the type that employs a tree structured codebook to vector quantize input vectors and sequentially transmits vector quantized data for input vectors to a remote decoder for reconstructing a substantial representation of each input vector therefrom, the codebook having plural levels of codevectors, each codevector being representative of a possible input vector and there being an identification (ID) code associated with each codevector, the codevectors at each successive level representing possible input vectors with greater accuracy than codevectors at a preceding level, a method comprising the steps of:

a) comparing a representation of a previous input vector that has already been vector quantized to a current input vector to obtain a first measure of difference between the representation of the previous input vector and the current input vector;

b) transmitting to the decoder an instruction to reconstruct a substantial representation of the current input vector from vector quantized data already stored in the decoder for the previous input vector only when the first measure of difference is less than a threshold value, but otherwise performing the following steps for the current input vector;

c) processing the current input vector and selecting an initial level of the codebook;

d) comparing the processed input vector to the codevectors at the selected level of the codebook and selecting the codevector that most closely resembles the processed input vector;

e) obtaining a second measure of difference between the processed input vector and the selected codevector;

f) transmitting an indication of the ID code associated with the selected codevector only if the second measure of difference is less than the threshold value, but otherwise selecting a next level of the codebook and repeating steps (d) and (e) until either the second measure of difference is less than the threshold value or a last level of the codebook has been employed, then transmitting the indication of the ID code associated with the finally selected codevector, the transmitted indication being the vector quantized data for the current input vector;

wherein vector quantized data for the current input vector need not be transmitted to reconstruct a representation of the current input vector at the decoder when the first measure of difference is less than the threshold value.

2. Method according to claim 1 wherein the representation of the previous input vector is a copy of the previous input vector.

3. Method according to claim 1 wherein the representation of the previous input vector is constructed from a codevector finally selected from the codebook for the previous input vector and from a mean vector quantity.

4. Method according to claim 1 wherein step (c) comprises determining a mean of the current input vector and removing the mean from the current input vector to obtain a residual vector, the processed input vector comprising the residual vector.

5. Method according to claim 4 wherein step (b) further comprises transmitting the mean with the instruction and step (f) further comprises transmitting the mean with the indication.

6. Method according to claim 1 wherein a mean value of each input vector is determined and a mean vector for the current input vector is interpolated from the mean value of the current input vector and any adjacent vectors and wherein step (c) comprises subtracting the mean vector from the current input vector.

7. Method according to claim 6 wherein the result of the subtraction defines a first residual vector and step (c) further comprises calculating a mean value of the first residual vector and subtracting the mean value of the first residual vector from the first residual vector to define a second residual vector, the processed input vector comprising the second residual vector.

8. Method according to claim 7 wherein the codevectors in the codebook are representative of possible second residual vectors.

9. Method according to claim 1 wherein the codebook is stored in a memory and each ID code is a memory address, and a compression code is assigned to each possible address, each compression code having a length that is substantially inversely proportional to a predetermined probability that a particular codevector will be finally selected, the transmitted indication comprising the compression code for the address associated with the finally selected codevector.

10. Method according to claim 9 wherein the compression codes are Huffman codes.

11. Method according to claim 10 wherein the instruction is a Huffman encoded instruction.

12. Method according to claim 1 wherein the transmitted indications have variable length, further comprising the step of automatically adjusting the threshold based upon a measure of average length of previously transmitted indications and instructions.

13. Method according to claim 9 wherein the indications and instructions are transmitted at a fixed data rate, further comprising the steps of storing indications and instructions to be transmitted in a buffer, periodically obtaining a measure of unused capacity of the buffer, and automatically adjusting the threshold value based upon the measure of unused buffer capacity.

14. Method according to claim 1 further comprising the step of determining a mean value for each input vector and wherein the following steps (i) and (ii) are performed prior to performing steps (c)-(f)

i) obtaining a third measure of difference between the mean value and the current input vector;

and,

ii) comparing the third measure of difference to the threshold value;

and wherein steps (c)-(f) are performed for the current input vector only if the third measure of difference is greater than the threshold value;

and further comprising the step of transmitting an indication of only the mean value of the current input vector when the third measure of difference is less than the threshold value.

15. Method according to claim 1 further comprising the step of determining a mean value for each input vector and wherein the following steps (i) and (ii) are performed prior to performing steps (a)-(f):

i) interpolating a mean vector from the mean value of the current input vector and any adjacent vectors;

i) obtaining a third measure of difference between the mean vector and the current input vector; and

,

ii) comparing the third measure of difference to the threshold value;

and wherein steps (a)-(f) are performed for the current input vector only if the third measure of difference is greater than the threshold value;

and further comprising the step of transmitting an indication of only the mean value of the current input vector when the third measure of difference is less than the threshold value.

16. Method according to claim 3 wherein a mean value is calculated for each input vector and the mean vector quantity for the current input vector is interpolated from the mean values for the current input vector and any adjacent input vectors, and the representation of the previous input vector is constructed according to the following steps:

i) adding the mean vector quantity for the current input vector to the codevector finally selected from the codebook for the previous input vector;

ii) determining a mean value of the result of step (i);

iii) determining a difference between the mean value determined in step (ii) and the mean value calculated for the current input vector; and

,

iv) adding the result of step (iii) to the result of step (i).

17. Method according to claim 1 wherein the input vectors are derived from portions of image frames representing moving images to be displayed on a television set, each image frame comprising a matrix of pixels and each pixel within each image frame having at least an associated intensity value, and at least ones of the input vectors are representative of the intensity values of a block of pixels in the image, the transmission of an instruction being an indication that the current input vector and the previous input vector represent portions of image frames that are substantially similar.

18. Method according to claim 1 wherein the input vectors are derived from portions of image frames representing moving images to be displayed on a television set, each image frame comprising a matrix of pixels and each pixel within each image frame having at least associated luminance and chrominance values, and at least ones of the input vectors are representative of the luminance and chrominance values of a block of pixels in the image, the transmission of an instruction being an indication that the current input vector and the previous input vector represent portions of image frames that are substantially similar.

19. Method according to claim 1 wherein the decoder is in a locale of a television setand the decoder has another substantially identical tree structured codebook, and wherein the following steps are performed at the decoder:

(i) receiving an indication transmitted in step (f), obtaining the ID code therefrom, and retrieving from the codebook at the decoder the codevector associated with the obtained ID code to provide a substantial representation of the input vector that resulted in the transmission of the indication;

(ii) receiving an instruction transmitted in step (b) and, in response thereto, retrieving from the codebook at the decoder a codevector, defining a previous codevector, having the same ID code as a previously received ID code, and reproducing from the previous codevector a substantial representation of the input vector that caused the transmission of the instruction;

(iii) employing the reproduced representations of the input vectors to substantially re-create each image frame at the locale of the television set.

20. Method according to claim 19 wherein step (ii) further comprises adding a mean value to the previous codevector.

21. Method according to claim 8 wherein the decoder is in a locale of a television set, the decoder has a codebook that is substantially identical to the codebook at the encoder, and wherein the following steps are performed at the decoder:

i) for indications that are received at the decoder, obtaining the ID code from the received indications, retrieving from the codebook at the decoder the second residual codevector associated with the obtained ID code, and reproducing from the retrieved second residual codevector a substantial representation of the input vector that caused the transmission of the indication;

ii) for instructions that are received at the decoder, obtaining from a buffer in the decoder the same ID code as a previously received ID code, retrieving from the codebook at the decoder the second residual codevector associated with the previously received ID code, and reproducing from the retrieved second residual codevector a substantial representation of the input vector that caused the transmission of the instruction;

iii) employing the reproduced representations of the input vectors to substantially re-create each image frame at the locale of the television set.

22. Method according to claim 21 wherein the mean value of each input vector is transmitted to the decoder and steps (i) and (ii) each comprise:

i'"'"') for a current input vector whose substantial representation is to be reproduced, interpolating from the mean value of the current input vector and any adjacent input vectors a substantial reproduction of the mean vector;

ii'"'"') adding the mean vector reproduced in step (i'"'"') to the second residual codevector retrieved at the decoder;

iii'"'"') calculating the mean value of the result of step (ii'"'"');

iv'"'"') calculating a difference between the mean value calculated in step (iii'"'"') and the mean value received at the decoder for the current input vector;

v'"'"') adding the result of step (iv'"'"') to the result of step (ii'"'"');

the result of step (v'"'"') being the substantial representation of the input vector.

23. Method according to claim 19 or 21 wherein the indications and instructions are transmitted via satellite to a reception site then retransmitted at the reception site over a cable television distribution network to a plurality of cable television subscribers.

24. Method according to claim 19 or 21 wherein the indications and instructions are transmitted via satellite directly to a pay television subscriber.

25. Method according to claim 1 wherein the decoder is in a locale of a reception site and the indications and instructions are transmitted via satellite to the reception site and the following steps are performed at the reception site:

providing at the decoder a codebook that is substantially identical to the codebook at the encoder;

receiving an indication transmitted in step (f), obtaining the ID code therefrom, and retrieving from the codebook at the decoder the codevector associated with the obtained ID code to provide a substantial representation of the input vector that resulted in the transmission of the indication;

receiving an instruction transmitted in step (b) and, in response thereto, retrieving from the codebook at the decoder a codevector, defining a previous codevector, having the same ID code as a previously received ID code, and reproducing from the previous codevector a substantial representation of the input vector that caused the transmission of the instruction;

employing the reproduced representations of the input vectors to substantially re-create each image frame at the reception site and encoding data for each re-created image frame in NTSC format;

transmitting the NTSC encoded data from the reception site to a plurality of cable television subscribers over a cable television distribution network.

26. Method according to claim 17 or 18 wherein the indications are transmitted at a substantially fixed rate, further comprising the step of selecting a value for the threshold that causes a predetermined number of image frames to produce just a sufficient number of indications to yield the fixed rate over the predetermined number of frames.

48. Method according to claim 1, 27 or 40 wherein the codevectors are transformed to a transform domain before being provided in the codebook, and the codevectors are stored in the codebook in the transform domain, and wherein each input vector is transformed to the transform domain for selecting one of the codevectors from the codebook.

49. Method according to claim 48 wherein the transform domain is the frequency domain and the codevectors and input vectors are transformed to the frequency domain by a Fourier transform.

27. In a vector quantization encoder of the type employing a tree structured codebook having plural levels of codevectors representative of possible input vectors to be processed by the encoder, each input vector being indicative of a block of data, the codebook being stored in a memory and each codevector having an associated memory address, and wherein the encoder transmits vector quantized data for input vectors to a remote decoder and the decoder reconstructs substantial representations of each input vector from the transmitted vector quantized data, a method comprising the steps of:

a) providing at the encoder an input vector to be processed;

b) determining a mean of the input vector and transmitting data indicative of the mean to the decoder;

c) obtaining a first measure of difference between the input vector and the mean, and comparing the first measure of difference to a threshold value;

d) performing steps (i) and (ii) below only when the first measure of difference exceeds the threshold value, but otherwise proceeding to step (e);

(i) selecting a codevector from the codebook based upon a processed version of the input vector and the threshold value; and

,

(ii) transmitting to the decoder data indicative of the address associated with the selected codevector;

the data transmitted in step (b) and, when performed, step (d)(ii), being the vector quantized data, the decoder reconstructing a representation of the input vector from the transmitted vector quantized data,

e) providing at the encoder another input vector and obtaining a second measure of difference between said another input vector and at least a representation of the input vector provided in step (a), the input vector provided in step (a) defining a previous vector;

f) transmitting to the decoder at least an instruction to employ the vector quantized data transmitted for the previous vector to reconstruct a substantial representation of the said another input vector only if the second measure of difference is less than the threshold value, but otherwise performing steps (b) through (d) for said another input vector.

28. Method according to claim 27 wherein a scalar mean value is calculated for each input vector and the mean transmitted in step (b) is the scalar mean value, and prior to performing step (c), a mean vector is interpolated from the scalar mean value for the input vector of step (a) and from scalar mean values for adjacent input vectors, the mean employed in step (c) being the mean vector.

29. Method according to claim 27 wherein, prior to performing step (d)(i), the mean is removed from the input vector of step (a) to obtain a residual vector, the processed version of the input vector comprising the residual vector.

30. Method according to claim 28 wherein, prior to performing step (d)(i), the following steps are performed:

i'"'"') removing the mean vector from the input vector of step (a);

ii'"'"') determining a mean value of the result of step (i'"'"');

iii'"'"') subtracting the mean value determined in step (ii'"'"') from the result of step (i'"'"');

the result of step (iii,) being the processed version of the input vector of step (a).

31. Method according to claim 27 wherein step (f) comprises transmitting both the instruction and a mean of the said another input vector.

32. Method according to claim 27 wherein the representation of the input vector provided in step (a) is a copy of the input vector provided in step (a).

33. Method according to claim 27 wherein the mean determined in step (b) is a scalar quantity and the representation of the input vector provided in step (a) is reconstructed from the codevector selected from the codebook in step (d) for input vector of step (a) and from a mean vector interpolated from the scalar mean quantity for the said another input vector.

34. Method according to claim 33 wherein the representation of the input vector provided in step (a) is reconstructed according to the following steps:

i) adding the mean vector to the codevector selected in step (d);

ii) determining a mean value of the result of step (i);

(iii) determining a difference between the mean value determined in step (ii) and the scalar mean quantity for said another input vector; and

,

(iv) adding the result of step (iii) to the result of step (i).

35. Method according to claim 27 wherein a compression code is assigned to each possible address, each compression code having a length that is substantially inversely proportional to a predetermined probability that a particular codevector will be selected in step (d)(i), and step (d)(ii) comprises transmitting the compression code for the address associated with the selected codevector, and further wherein compression codes are assigned to the mean and to the instruction and step (b) comprises transmitting a compression code indicative of the mean and step (f) comprises transmitting a compression code indicative of the instruction.

36. Method according to claim 35 further comprising the step of periodically adjusting the threshold value based upon an average length of data transmitted in steps (b), (d)(ii) and (f).

37. Method according to claim 35 wherein the compression codes to be transmitted are temporarily stored then transmitted at a substantially fixed data rate.

38. Method according to claim 29 wherein step (d)(i) comprises:

a'"'"') selecting an initial level of the codebook;

b'"'"') selecting the codevector at the selected level that most closely resembles the residual vector;

c'"'"') obtaining a third measure of difference between the selected codevector and the residual vector;

d'"'"') proceeding to step (d)(ii) only if the third measure of difference is less than the threshold value, but otherwise selecting a next level of the codebook and repeating steps (b'"'"') and (c'"'"') until either the third measure of difference is less than the threshold value or a last level of the codebook has been employed, then proceeding to step (d)(ii).

39. Method according to claim 35 wherein the compression codes are Huffman codes.

40. A variable rate method for vector quantizing input vectors and transmitting vector quantized data to a remote decoder for reconstruction of substantial representations of each input vector comprising the steps of:

a) providing, in a memory, a tree structured codebook;

b) receiving data indicative of an image to be compressed, organizing the image data into blocks, and converting each block to a multi-dimensional input vector;

c) determining a scalar mean value of each input vector and interpolating, from the scalar mean values, a mean vector for each input vector;

d) selecting an input vector;

e) obtaining a first measure difference between the selected input vector and the mean vector for the selected input vector;

f) storing in a FIFO buffer only an indication of the scalar mean value of the selected input vector only if the first measure of difference is less than a threshold value then selecting another input vector and returning to step (e), but proceeding to step (g) if the first measure of difference is greater than the threshold;

g) constructing a representation of a previous input vector that has already been vector quantized and obtaining a second measure of difference between the selected input vector and the representation of the previous input vector;

h) storing in the FIFO buffer both an indication of the scalar mean value of the selected input vector and an instruction to the decoder to reproduce a substantial representation of the selected input vector from vector quantized data already stored in the decoder for the previous input vector only if the second measure of difference is less than the threshold then selecting another input vector and returning to step (e), but proceeding to step (i) if the second measure of difference is greater than the threshold;

i) constructing from the selected input vector a secondary vector having a mean at least once removed and defining a residual vector, there being stored in the codebook a plurality of codevectors at a plurality of levels, each codevector being representative of a possible residual vector and each successive level of codevectors representing possible residual vectors in greater detail than a preceding level of codevectors, there being a memory address associated with each codevector;

j) selecting an initial level in the codebook;

k) comparing the residual vector to the codevectors at the selected level and selecting the codevector that most closely resembles the residual vector;

l) obtaining a third measure of difference between the selected codevector and the residual vector, and comparing the third measure of difference to the threshold;

m) defining the selected codevector as a finally selected codevector and proceeding directly to step (o) if either the third measure of difference is less than the threshold or a last level of the codebook has been employed, but proceeding to step (n) if the third measure of difference exceeds the threshold;

n) selecting the next level in the codebook and repeating steps (k) through (m);

o) storing an indication of the address of the finally selected codevector in the FIFO buffer, selecting another input vector, and returning to step (e), at least the address indications having variable length;

p) transmitting the indications and instructions stored in the FIFO buffer to the decoder at a fixed data rate; and

,

q) maintaining a measure of unused FIFO buffer capacity and periodically adjusting the threshold by automatically increasing the threshold value when the measure of unused FIFO buffer capacity indicates that unused capacity is decreasing and automatically decreasing the threshold value when the measure of unused FIFO buffer capacity indicates that unused capacity is increasing, adjustment of the threshold ensuring that the buffer does not empty or overflow as a result of storing variable length indications but transmitting the same at a fixed data rate, and wherein address indications are not stored in the FIFO buffer or transmitted to the decoder when the first or second measure of difference is less than the threshold.

41. Method according to claim 40 wherein at least the address indications are compression codes and each compression code has a length that is substantially inversely proportional to a predetermined likelihood that a particular codevector will be finally selected.

42. Method according to claim 41 wherein the compression codes are Huffman codes.

43. Method according to claim 40 wherein step (g) comprises:

aa) adding the mean vector for the selected input vector to a codevector finally selected from the codebook for the previous vector;

bb) determining a mean value of the result of step (aa);

cc) determining a difference between the result of step (bb) and the scalar mean value for the selected input vector;

dd) adding the result of step (cc) to the result of step (aa).

44. Method according to claim 43 wherein step (i) comprises:

aa) subtracting from the selected input vector the mean vector for the selected input vector;

bb) determining a mean value of the result of step (aa);

cc) subtracting the mean value determined in step (bb) from the result of step (aa).

45. Data compression apparatus comprising:

a) first means for receiving a multi-dimensional vector representative of a block of data to be compressed;

b) a tree structured codebook having plural levels of codevectors, each codevector being representative of a possible vector and the codevectors at each successive level representing possible vectors in greater detail than codevectors at a preceding level, each codevector having a unique address associated therewith;

c) a controller for selecting one of the codevectors in the codebook based upon the vector and a threshold value according to a distortion adaptive vector quantization technique;

d) second means for transmitting data indicative of the address of the selected codevector; and

,

e) third means for obtaining a measure of difference between the vector received by the first means and a representation of a previous vector and for providing, based upon the measure of difference and the threshold value, an indication to a remote vector quantization decoder that the vector received by the first means is substantially similar to the previous vector and may be copied therefrom.

46. In a vector quantization encoder of the type employing a tree structured codebook having plural levels of codevectors representative of possible input vectors to be processed by the encoder, each input vector being indicative of a block of data, the codebook being stored in a memory and each codevector having an associated memory address, and wherein the encoder transmits vector quantized data for input vectors to a remote decoder and the decoder reconstructs substantial representations of each input vector from the transmitted vector quantized data, a method comprising the steps of:

a) providing at the encoder an input vector to be processed;

b) determining a mean of the input vector and transmitting data indicative of the mean to the decoder;

c) obtaining a first measure of difference between the input vector and the mean, and comparing the first measure of difference to a threshold value;

d) performing steps (i) and (ii) below only when the first measure of difference exceeds the threshold value, but otherwise proceeding to step (e);

(i) selecting a codevector from the codebook based upon a processed version of the input vector and the threshold value; and

,

(ii) transmitting to the decoder data indicative of the address associated with the selected codevector;

the data transmitted in step (b) and, when performed, step (d)(ii), being the vector quantized data, the decoder reconstructing a representation of the input vector from the transmitted vector quantized data,

e) providing at the encoder another input vector, determining the mean of said other input vector and performing at least steps (c) and d(i) for said other input vector to obtain a codebook address for said other input vector;

f) comparing the address for said other input vector to the address for the input vector provided in step (a) and transmitting to the decoder an instruction to substantially copy the input vector reconstructed from the vector quantized data transmitted in step (b) and, when performed, step (d)(i), to reconstruct a representation of said other input vector if the addresses are substantially identical but otherwise performing the following steps;

g) obtaining a second measure of difference between said other input vector and the input vector provided in step (a);

h) transmitting to the decoder an instruction to substantially copy the input vector reconstructed from the vector quantized data transmitted in step (b) and, when performed, step (d)(ii), to reconstruct a representation of said other input vector only if the second measure of difference is less than the threshold value, but otherwise transmitting the vector quantized data for said other input vector.

47. Data compression apparatus comprising:

a) first means for receiving a multi-dimensional vector representative of a block of data to be compressed;

b) a tree structured codebook having plural levels of codevectors, each codevector being representative of a possible vector and the codevectors at each successive level representing possible vectors in greater detail than codevectors at a preceding level, each codevector having a unique address associated therewith;

c) a controller for selecting one of the codevectors in the codebook based upon the vector and a threshold value according to a distortion adaptive vector quantization technique;

d) second means for transmitting data indicative of the address of the selected codevector; and

,

e) third means for comparing an address associated with a previous vector received by the first means to an address associated with a current vector received by the first means and, when the addresses are substantially identical, for providing an indication that the current vector is substantially similar to the previous vector and may be copied therefrom, but when the addresses are not substantially identical, for obtaining a measure of difference between the current vector and the previous vector and for providing, when the measure of difference is less than the threshold value, an indication that the current vector is substantially similar to the previous vector and may be copied therefrom.

50. A decoder for use at a reception site of vector quantization data, wherein the vector quantization data originates from an encoding site employing a tree search vector quantization data compressor for compressing digital data indicative of at least intensity values of pixels of images to be transmitted to recipients by converting input vectors indicative of a block of pixels to addresses of a first codebook in the compressor, the first codebook having plural levels of codevectors representative of possible input vectors and each successive level representing codevectors with a greater accuracy than a preceding level of codevectors, the encoding site transmitting, for each input vector, data indicative of a mean of at least selected ones of the input vectors and one of either (i) data indicative of an address of the codevector found to most closely approximate each input vector or, (ii) an instruction to copy a representation of a previous input vector, the decoder comprising:

a) a second codebook being substantially identical in content to the first codebook;

b) a memory for storing at least the means and address data transmitted by the encoder for at least a current and a previous frame of image data;

c) a controller for retrieving codevectors from the second codebook based upon the address data stored in the memory, the controller being responsive to each received instruction to employ address data for the previous frame stored in the memory to retrieve a codevector, defining a previous frame codevector, from the second codebook and to employ the previous frame codevector as a representation of an input vector in the current frame, but the controller, in selected instances, otherwise employing address data for the current frame to retrieve a codevector from the second codebook to obtain a representation of the input vector;

d) at least one converter for converting each codevector to NTSC format image data and for providing the NTSC format image data at an output thereof for substantially reproducing an image that was input to the encoding site.

51. Decoder according to claim 50 further comprising a summing circuit for adding each codevector retrieved from the second codebook to a corresponding one of the means stored in the memory.

52. Decoder according to claim 51 wherein a mean is transmitted from the encoding site for every input vector and stored in the memory of the decoder.

53. Decoder according to claim 50 wherein a mean is transmitted from the encoding site for every input vector and stored in the memory of the decoder, each transmitted mean being a scalar value, further comprising a mean vector calculator for providing a mean vector for a current input vector whose representation is to be obtained at the decoder, the mean vector being interpolated from the scalar mean value associated with the current input vector and the scalar mean value associated with any adjacent input vectors.

54. Decoder according to claim 53 further comprising:

a first summing circuit for adding each retrieved codevector to a corresponding one of the mean vectors;

a mean value calculator for computing a mean value of an output of the first summing circuit;

a difference calculator for calculating a difference between the mean value computed by the mean value calculator and the scalar mean value associated with the current input vector;

a second summing circuit for adding an output of the difference calculator to the output of the first summing circuit;

an output of the second summing circuit being the representation of the current input vector.