Recursive data compression
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
14 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11)
-
-
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. - View Dependent Claims (13, 14)
-
Specification