Method for data compression

• US 5,533,051 A
• Filed: 03/12/1993
• Issued: 07/02/1996
• Est. Priority Date: 03/12/1993
• Status: Expired due to Fees

• Current Assignee: HyperSpace Communications, Inc.
• Original Assignee: James Group LLC
• Inventors: James, David C.
• Primary Examiner(s): Rogers, Scott A.
• Assistant Examiner(s): Esposo, Allan A.
• Application Number:
  US08/030,741
• Time in Patent Office: 1,208 Days
• Field of Search: 375/122, 341/67, 341/87, 341/51, 348/415, 348/409, 348/390, 348/384, 382/244, 364/715.02, 380/42, 380/49
• US Class Current: 375/240
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

Methods for compressing data including methods for compressing highly randomized data are disclosed. Nibble encode, distribution encode, and direct bit encode methods are disclosed for compressing data which is not highly randomized. A randomized data compression routine is also disclosed and is very effective for compressing data which is highly randomized. All of the compression methods disclosed operate on a bit level and accordingly are insensitive to the nature or origination of the data sought to be compressed. Accordingly, the methods of the present invention are universally applicable to any form of data regardless of its source of origination.

Claims

1. A method of extracting redundancy from a stream of electrically encoded binary data, comprising the steps of:

A) parsing n-bits from said stream of data;

B) determining the value of said parsed n-bit;

C) based on the result of step B, associating the value of said parsed n-bits with one of a plurality of coded strings;

D) dividing said coded string of step C into first and second segments;

E) assigning said first segment of said coded string to at least one of a first and third target string; and

F) assigning said second segment of said coded string to at least a second target string.

2. The method of extracting redundancy of claim 1, wherein parsing n-bits includes parsing 2-bits.

3. The method of extracting redundancy of claim 1, wherein the assigning of step E further includes concatenating.

4. The method of extracting redundancy of claim 1, wherein the assigning of step F includes concatenating.

5. The method of extracting redundancy of claim 1, further including the step of:

G) assigning said contents of at least one of said first, second, and third target strings to said stream of data, and repeating steps A through F on said stream of data.

6. A method of compressing a stream of binary data, comprising the steps of:

A) parsing n-bits from said stream of binary data;

B) determining the value of said parsed n-bits;

C) based on the result of step B, coding said value of said n-bits in at least one of a first, second, and third target string, wherein coding said value includes generating a plurality of code strings and correlating said value with one of said code strings and dividing said correlated code string variable length codes and dividing at least some of said into at least first and second segments, and assigning at least one of said correlated code string segments to at least one of said first, second, and third target strings, wherein at least one of said plurality of codes is not greater than n-1 bits long.

7. The method of compressing a stream of binary data in claim 6, wherein n=2.

8. The method of compressing a stream of binary data of claim 6, further including the steps of:

D) assigning said contents of at least one of said first, second, and third target strings to said stream of binary data, and repeating steps A through C on said stream of binary data.

9. A method of extracting and compressing redundant data from a stream of electrically encoded binary data, comprising the steps of:

A) parsing n-bits from said stream of data;

B) determining the value of said parsed n-bits of data;

C) associating a coded string with the value determined in step B;

D) dividing said coded string into first and second string portions and concatenating said first portion of the coded string of step C to a contents of at least one of a first and third target strings;

E) concatenating said second portion of the coded string of step C to a contents of a second target string;

F) parsing n-bits at a time from the contents of at least one of said first, second, and third target strings;

G) assigning a coded string, from a plurality of coded strings, to each of the parsed n-bits of step F, said assigning of said coded string based in part, upon the value of said parsed n-bits of step F and wherein at least one of said coded strings is not greater than n-1 bits long;

H) dividing said assigned coded string into at least first and second portions, and assigning at least one of said first and second coded string portions to at least one of a first, second, and third output registers.