Memory based vector quantization

• US 5,300,931 A
• Filed: 09/04/1987
• Issued: 04/05/1994
• Est. Priority Date: 09/04/1987
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Grant, Patrick S., Vaughn, Val D., Lindsay, Robert A.
• Primary Examiner(s): Cangialosi, Salvatore
• Application Number:
  US07/093,331
• Time in Patent Office: 2,405 Days
• Field of Search: 364/200, 341/106, 341/87, 358/156, 358/263
• US Class Current: 341/106
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

Apparatus is provided for performing two stages of high-speed compression of vector data inputs. Two input channels of vector data are compressed and encoded through a vector quantizer encoder to provide a first stage of data compression. The output of the first encoder is further decoded then compressed and encoded in a novel high-speed computing mapping means which may be implemented in the form of a look-up table. Vector quantized encoded output is double the previous data compression of a single stage. The second stage of data compression causes very little degradation of the data from the first stage of data compression.

Claims

1. Apparatus for high-speed compression of vector data inputs comprising:

means for storing groups of scalar data,

means for formatting said groups of scalar data into a plurality of vector dimensional data inputs coupled to said means for storing groups of scalar data,

first encoder means for vector quantizing said plurality of vector data inputs to provide a plurality of compressed encoded index data outputs, said compressed encoded index data outputs providing a unique index pointer output, and

means for computing mapping of data on said compressed encoded index data outputs to provide a compressed compressed output coupled to said unique index pointer output.

2. Apparatus as set for in claim 1 wherein said means for computing mapping comprises a look-up table.

3. Apparatus as set forth in claim 2 wherein said look-up table comprises a memory having up to 2²⁰ unique possible address inputs for producing up to 2⁴ outputs.

4. Apparatus as set forth in claim 2 wherein said look-up table comprises a precomputed mapping of index information representations of vector quantized values.

5. Apparatus as set forth in claim 1 wherein said means for computing mapping comprises vector quantizing decoding means coupled to said first encoder means, and

second encoder means for quantizing the output of said decoder means.

6. Apparatus as set forth in claim 5 wherein said decoder means comprises a memory look-up table.

7. Apparatus as set forth in claim 6 wherein said second encoder means comprises VHSIC gate arrays.

8. Apparatus as set forth in claim 1 wherein said means for storing groups of scalar data comprises memory means for storing digital data.

9. Apparatus as set forth in claim 1 wherein said groups of scalar data each defines a 2×

2 matrix of individual image pixel data.

10. Apparatus as set forth in claim 1 wherein said first encoder means comprises a pair of vector quantizing encoders.

11. Apparatus as set forth in claim 1 where said first encoder means comprises a plurality of pairs of vector quantizing encoders.

12. Apparatus as set forth in claim 1 wherein the plurality of outputs of said first encoder means are combined to form a unique index pointer.

13. Apparatus as set forth in claim 12 wherein said means for computing mapping comprises a precomputed map having as many address locations as there are unique addresses and each memory address location is provided with as many bits stored therein as there are bits in said pre-computed extended representative set output from said pre-computed map.

14. Apparatus as set forth in claim 1 which further includes a vector quantizer decoder coupled to the output of said means for computing mapping.

15. Apparatus as set forth in claim 14 wherein said vector quantizer decoder comprises a look-up table.

16. Apparatus as set forth in claim 1 wherein said means for computing mapping comprises a look-up table having a compressed compressed encoded index data output which is adapted to be coupled to a vector quantizing decoder having an extended vector space stored in memory locations therein.

17. A method for high-speed compression of vector data comprising the steps of:

storing groups of scalar data,

formatting said groups of scalar data into a plurality of vector dimensional data inputs,

vector quantize-encoding said plurality of vector data inputs to provide a compressed encoded index data output indicative of a unique index address, and

addressing a pre-computed look-up table with said unique index address to provide a concatenated vector space representative vector index of said compressed encoded index thereby further compressing said compressed encoded index data.