Recursive data compression

• US 5,488,364 A
• Filed: 02/28/1994
• Issued: 01/30/1996
• Est. Priority Date: 02/28/1994
• Status: Expired due to Fees

• Current Assignee: Sam H. Eulmi
• Original Assignee: Sam H. Eulmi
• Inventors: Cole, Michael L.
• Primary Examiner(s): Young, Brian K.
• Application Number:
  US08/203,998
• Time in Patent Office: 701 Days
• Field of Search: 341/67, 341/51, 341/50, 341/87, 358/261.1, 358/261.4
• US Class Current: 341/50
• 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

Reconfiguring data in a manner that increases bit redundancy, and compressing the reconfigured data in an iterative or recursive manner until the desired compression ratio is obtained. The data are divided into one or more packets and the bits of the data in each packet are redistributed between two blocks. In one block the number of occurrences of adjacent bits of the "1" state is, on average, greater than the number of occurrences of adjacent bits of the "0" state and adjacent bits of differing states. In the other block the number of occurrences of adjacent bits of the "0" state is, on average, greater than the number of occurrences of adjacent bits of the "1" state and adjacent bits of differing states. The blocks are thus conducive to compression algorithms that exploit bit redundancy.

Claims

1. A method for compressing data, comprising the steps of:

receiving a plurality of input data words, each consisting of a plurality of bits located in a plurality of positions;

compressing said plurality of input data words to form a plurality of compressed data words using a run-length based compression method;

forming a plurality of reconfigured data words in response to said plurality of compressed data words, said plurality of reconfigured data words having an average frequency of occurrence of adjacent bits of the same binary state that is greater than the average frequency of occurrence of adjacent bits of the same binary state in said plurality of compressed data words; and

compressing said plurality of reconfigured data words using said run-length based compression method.

2. The method for compressing data recited in claim 1, wherein each said input data word consists of eight bits.

3. The method for compressing data recited in claim 1, wherein said compression method is LZW.

4. The method for compressing data recited in claim 1, wherein said step of forming a plurality of reconfigured data words compresses the step of:

producing a plurality of bit-majoritized data words in response to said plurality of input data words, said plurality of bit-majoritized data words having a total number of bits of a predetermined binary state greater than one-half the total number of bits in said plurality of input data words;

distributing said bit-majoritized data words into first and second data blocks, said first data block having an average frequency of occurrence of adjacent bits of the same first binary state that is greater than the average frequency of occurrence of adjacent bits of the same first binary state in said plurality of input data words, said second data block having an average frequency of occurrence of adjacent bits of the same second binary state that is greater than the average frequency of occurrence of adjacent bits of the same second binary state in said plurality of input data words.

5. The method for compressing data recited in claim 4, wherein said step of distributing said bit-majoritized data words comprises the step of forming a key word, said key word relating the positions of bits in said input data words to the positions of bits in said first and second data blocks.

6. The method for compressing data recited in claim 4, wherein said step of distributing said bit-majoritized data words comprises the steps of:

receiving a packet comprising a predetermined number of bit-majoritized data words from among said plurality of bit-majoritized data words;

comparing each said bit-majoritized data word of said packet to a plurality of bit patterns consisting of all unique combinations of binary states of a plurality of bits equal in number to the number of bits in said bit-majoritized data words and having at least one bit of said predetermined binary state;

forming a plurality of pattern sums among all said bit-majoritized data words of said packet, each said pattern sum corresponding to one said bit pattern, each said pattern sum equaling the number of times one said bit-majoritized data word includes one or more bits having said predetermined binary state in the same positions as all said bits having said predetermined binary state in said bit pattern;

determining a key word, said key word consisting of said bit pattern corresponding to said greatest pattern sum;

sequentially comparing each said bit-majoritized data word of said packet to said key word;

copying said bits of said compared data word located in the same position in said compared data word as each bit of said key word having said predetermined binary state to bit locations in a first data block; and

copying said bits of said compared data word located in the same position in said compared data word as each bit of said key word having a binary state other than said predetermined binary state to bit locations in a second data block.

7. The method for compressing data recited in claim 4, wherein said step of producing a plurality of bit-majoritized data words comprises the steps of:

determining whether the binary state of a bit is a predetermined binary state for each said input data word of said plurality of input data words at each said position;

forming a plurality of bit sums among all said input data words, each bit sum of said plurality of bit sums corresponding to one said position, each said bit sum equaling the number of times a bit having said predetermined binary state occurs in each said position;

reversibly inverting the binary state of each bit in each said input data word located in a position corresponding to a bit sum having a value less than one-half the number of input data words in said plurality of input data words.

8. The method for compressing data recited in claim 7, wherein said step of producing a plurality of bit-majoritized data words further comprises the step of producing a mask word for indicating the positions of inverted bits.

9. A method for reconfiguring data to increase bit redundancy, comprising:

receiving a plurality of input data words, each said input data word consisting of a plurality of bits located in a plurality of positions, each said bit having a binary state;

producing a plurality of bit-majoritized data words in response to said input data words, said plurality of bit-majoritized data words having a total number of bits of a predetermined binary state greater than one-half the total number of bits in said plurality of input data words;

receiving a packet comprising a predetermined number of bit-majoritized data words from among said plurality of bit-majoritized data words;

determining a key word from among a plurality of bit patterns consisting of all unique combinations of binary states of a plurality of bits equal in number to the number of bits in said input data words and having at least one bit of said predetermined binary state, said key word having the greatest number of bits of said predetermined binary state in the same positions as bits of said bit-majoritized data words having said predetermined binary state;

forming a first data block having only bits of said bit-majoritized data words located in the same positions in said bit-majoritized data words as said bits of said key word having said predetermined binary state;

forming a second data block having only bits of said bit-majoritized data words located in the same positions in said bit-majoritized data words as said bits of said key word having a binary state other than said predetermined binary state; and

producing a plurality of output data words comprising said key word, said first data block, and said second data block.

10. The method for reconfiguring data recited in claim 9, wherein each said data word consists of eight bits.

11. The method for reconfiguring data recited in claim 9, wherein said predetermined binary state is a "1".

12. A method for reconfiguring data to increase bit redundancy, comprising:

receiving a plurality of input data words, each said data word consisting of a plurality of bits located in a plurality of positions, each said bit having a binary state;

determining whether the binary state of a bit is a predetermined binary state for each said data word of said plurality of data words at each said position;

forming a plurality of bit sums among all said data words, each bit sum of said plurality of bit sums corresponding to one said position, each said bit sum equaling the number of times a bit having said predetermined binary state occurs in each said position;

reversibly inverting the binary state of each bit in each said data word located in a position corresponding to a bit sum having a value less than one-half the number of data words in said plurality of data words;

receiving a packet comprising a predetermined number of data words from among said plurality of data words;

comparing each said data word of said packet to a plurality of bit patterns consisting of all unique combinations of binary states of a plurality of bits equal in number to the number of bits in said data words and having at least one bit of said predetermined binary state;

forming a plurality of pattern sums among all said data words of said packet, each said pattern sum corresponding to one said bit pattern, each said pattern sum equaling the number of times one said data word includes one or more bits having said predetermined binary state in the same positions as all said bits having said predetermined binary state in said bit pattern;

determining a key word, said key word consisting of said bit pattern corresponding to said greatest pattern sum among said plurality of pattern sums;

sequentially comparing each said data word of said packet to said key word;

copying said bits of said compared data word located in the same position in said compared data word as each bit of said key word having said predetermined binary state to sequential bit locations in a first data block;

copying said bits of said compared data word located in the same position in said compared data word as each bit of said key word having a binary state other than said predetermined binary state to sequential bit locations in a second data block; and

producing a plurality of output data words comprising said key word, said first data block, and said second data block.

13. The method for reconfiguring data recited in claim 12, further comprising the step of producing a mask word for indicating the positions of inverted bits, and said plurality of output data words further comprises said mask word.

14. The method for reconfiguring data recited in claim 12, wherein each said data word consists of eight bits.