Methods and means for image and voice compression

• US 6,018,303 A
• Filed: 11/10/1998
• Issued: 01/25/2000
• Est. Priority Date: 09/07/1992
• Status: Expired due to Term

• Current Assignee: Amstr Investments 2 KG LLC (Intellectual Ventures LLC)
• Original Assignee: Visnet Ltd.
• Inventors: Sadeh, Ilan
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US09/188,526
• Time in Patent Office: 441 Days
• Field of Search: 341/51, 341/87
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A system for lossy compression of digital data for transmission to a remote location or to a storage medium and subsequently reconstructing the digital data includes an encoder which compares sequences of characters with an encoder database of data records to generate a compressed code. The compressed code includes pointer information relating to locations within the encoder database of data records corresponding within a given average distortion tolerance level per character to the sequences, and update information for the addition to the encoder database of new data records corresponding within the average distortion tolerance level per character to the sequences. The system also includes a decoder for receiving the compressed code, the receiver processing the compressed code to substantially reconstruct the digital data.

Claims

1. A method for compressing source data for transmission to a remote location or to a storage medium, the source data being made up of data units from a first alphabet U, the source data units being mappable on to code data units of a second alphabet V, there being defined a distortion measure indicative of the distortion caused by encoding any given source data unit as any given code data unit, the method comprising the steps of:

(a) setting a current string length, l, to an initial value;

(b) imputting l data units of source data to generate a current string;

(c) searching within at least part of a tree-structured database of code data units for a database substring corresponding within a given non-zero average distortion tolerance level per data unit to said current string, said tree-structured database of code data units being structured as a multi-branch structure in which at least one node has in excess of two nodes branching therefrom;

(d) in a case that such a said database substring is found;

(i) storing last-find pointer information relating to the location within said database of said database substring which corresponds within said average distortion tolerance level per data unit to said current string.

(ii) inputting a next data unit of source data and appending said data unit to said current string such that said current string contains l+1 data units made up of a most recently found string and a most recently added data unit,

(iii) incrementing said current string length, l, by 1, and

(iv) returning to step (c); and

(e) when no such said database substring is found;

(i) transmitting a compressed data signal indicative of;

(A) said last-find pointer information, and

(B) a code data unit corresponding to said most recently added unit of said current string, and

(ii) updating said database to include a database substring corresponding within said average distortion tolerance level per data unit to said current string.

2. The method of claim 1, wherein said last-find pointer information includes information to identify a terminal node at the termination of a path corresponding to said most recently found string.

3. The method of claim 1, wherein said step of updating said database is performed by adding a new branch corresponding to said most recently added data unit to said terminal node.

4. The method of claim 1, wherein the method is repeated until said tree structure utilizes all available memory, the method subsequently continuing without further updating of said database.

5. The method of claim 1, further comprising a step of re-defining said database substring added by said updating based upon analysis of subsequent source data.