Data compression system

• US 4,516,246 A
• Filed: 02/26/1982
• Issued: 05/07/1985
• Est. Priority Date: 02/26/1982
• Status: Expired due to Fees

• Current Assignee: Prentice Corporation
• Original Assignee: Prentice Corporation
• Inventors: Kenemuth, James A.
• Primary Examiner(s): Griffin, Robert L.
• Assistant Examiner(s): Chin, Stephen
• Application Number:
  US06/352,681
• Time in Patent Office: 1,166 Days
• Field of Search: 375/37, 375/25, 358/133, 358/135, 340/347 DD, 375/122
• US Class Current: 375/259
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

A character base input data stream is encoded in compressed form by using a histogram of a sample of the data stream to determine the frequency of appearance of characters in the stream. A code for a character M+1 is generated in an encoder (112) to be of a length which is an inverse function of the frequency of appearance of character M+1 in the preceding M characters in the sample. Decoding can be achieved by forming a comparable sample window in a decoder (118) to which is applied an estimated index of the incoming character being decoded.

Claims

1. A data transmission system, comprising, in combination:

(a) transmitter means for creating codes as a function of a character based input data stream and including encoder means for encoding each character with a code having a bit length which is an inverse function of the frequency of appearance of the character in a sample of a predetermined number of immediately preceding characters in said data stream, said encoder means including code generating means for receiving said input data stream and for developing a code for each character received, and bit length means for receiving the same input data stream as said code generating means and for determining from said predetermined number of characters the number of bits of a code to be developed by the code generating means for a specific character k, said code having a bit length β

(k), where β

(k) is the smallest positive integer such that the non-zero probability p(k) of a character appearing in said predetermined number of characters is >

or = to 1/(2 to the β

(k) power);

(b) data link means connected to said transmitter means for receiving the codes created by said encoder means; and

(c) receiver means connected to said data link means for receiving said codes generated by said transmitter means and for decoding the data back to a character based data stream.

2. A data transmission system, comprising, in combination:

(a) transmitter means for creating codes as a function of a character based input data stream and including encoder means for encoding each character with a code having a bit length which is an inverse function of the frequency of appearance of the character in a sample of a predetermined number of immediately preceding characters in said data stream;

(b) data link means connected to said transmitter means for receiving the codes created by said encoder means; and

(c) receiver means connected to said data link means for receiving said codes generated by said transmitter means and for decoding the data back to a character based data stream, said receiver means including decoder means comprising

(i) index guess means for receiving a coded data from said data link means and for computing a hypothetical character index based on the data received;

(ii) histogram reforming means based on a sample of decoded characters for developing a history of such sample, said histogram reforming means having a window identical to a window of said histogram forming means, an index computed by said index guess means being fed to said histogram reforming means;

(iii) power-of-2 frequency estimating means forming an input to said index guess means for developing a power-of-2 frequency q(k) for a coded character; and

(iv) comparator means having respective inputs connected to said histogram forming means and said power-of-2 frequency estimating means for sequencing possible characters until q(k'"'"')=q(k).

3. Apparatus as defined in claim 2 wherein said bit length means assigns any character k a code of bit length β

(k), where β

(k) is the smallest positive integer such that the non-zero probability p(k) of a character appearing is >

or = to 1/(2 to the β

(k) power).

20. Apparatus as defined in claim 2 wherein said code generating means includes, in combination:

(a) fractional coding resources means for receiving the input data stream and for determining all characters of a predetermined frequency;

(b) character index means for receiving the character based input data stream and for specifying the position of a given character in an ordered set within the range .0. <

or = to i(k) >

or = to η

(q)-1, where i(k) is a character index and η

(q) is a table of the power-of-2 frequencies contained in the incoming data streams; and

(c) summing means connected to said fractional coding resources means and said character index means for receiving and summing output signals from same to develope a code for each character contained in the data input stream.

21. Apparatus as defined in claim 2 wherein said code generating means includes, in combination:

(a) fractional coding resources means for receiving the input data stream and for determining all characters of a predetermined frequency;

(b) character index means for receiving the character based input data stream and for specifying the position of a given character in an ordered set within the range .0. <

or = to i(k) <

or = to η

(q)-1, where i(k) is a character index and η

(q) is a table of the power-of-2 frequencies contained in the incoming data streams; and

(c) summing means connected to said fractional coding resources means and said character index means for receiving and summing output signals from same to develope a code for each character contained in the data input stream.

4. A data transmission system, comprising, in combination:

(a) transmitter means for creating codes as a function of a character based input data stream and including encoder means for encoding each character with a code having a bit length which is an inverse function of the frequency of appearance of the character in a sample of a predetermined number of immediately preceding characters in said data stream, said encoder means including code generating means for receiving said input data stream and for developing a code for each character received, and comprising;

(i) fractional coding resources means for receiving the input data stream and for determining all characters with a power-of-2 frequency q(k) for a given character;

(ii) character index means for receiving the character based input data stream and for specifying the position of a given character in an ordered set within the range .0. <

or = to i(k) <

to η

(q)-1, where i(k) is a character index and η

(q) is a table of the power-of-2 frequencies contained in the incoming data streams;

(iii) scaler means connected to said character index means and said bit length means for receiving and scaling outputs from same; and

(iv) summing means connected to said fractional coding resources means and to said scaler means for receiving and summing output signals from same to develope a code for each character contained in the data input stream; and

bit length means for receiving the same input data stream as said code generating means and for determining from said predetermined number of characters the number of bits of a code to be developed by the code generating means for a specific character k;

(b) data link means connected to said transmitter means for receiving the codes created by said encoder means; and

(c) receiver means connected to said data link means for receiving said codes generated by said transmitter means and for decoding the data back to a character based stream.

5. Apparatus as defined in claim 4 wherein said fractional coding resources means includes a table forming means for performing a look-up function of a table η

(y), where y is a set of all possible power-of-2 frequencies [1/2, 1/4, 1/8 . . . , .0.].

6. A data transmission system, comprising, in combination:

(a) transmitter means for creating codes as a function of a character based input data stream and including encoder means for encoding each character with a code having a bit length which is an inverse function of the frequency of appearance of the character in a sample of a predetermined number of immediately preceding characters in said data stream, said encoder means further including code generating means for receiving said input data stream and for developing a code for each character received, and bit length means for receiving the same input data stream as said code generating means and for determining from said predetermined number of characters the number of bits of a code to be developed by the code generating means for a specific character k, said encoder means further including histogram forming means associated with and arranged for receiving the same input data stream as said code generating means and bit length means and for developing a histogrammic analysis of a sample thereof;

(b) data link means connected to said transmitter means for receiving the codes created by said encoder means; and

(c) receiver means connected to said data link means for receiving said codes generated by said transmitter means and for decoding the data back to a character based stream.

7. Apparatus as defined in claim 6 wherein the histogram forming means comprises, in combination:

(a) sample window means for receiving a character based sample of an input data stream containing in sequence the last M characters to appear in the input data stream; and

(b) character comparing means connected to said sample window means and monitoring the input data stream for comparing the next character, M+1, in the stream with the preceding M characters in said sample window means and generating said histogrammic analysis for character M+1 based on the M characters preceding character M+1.

8. Apparatus as defined in claim 7 wherein said sample window means includes character sequencing means for dropping the first character in the sample sequence of M characters and adding the most recent character, M+1, to the sample sequence to continuously revise the sample sequence of M characters in said sample window means.

9. Apparatus as defined in claim 6 wherein said encoder means further includes probability means connected to said histogram forming means for determining the probability of occurrence of a given character, and power-of-2 frequency means connected to said probability means for determining all power-of-2 frequencies present in the sample and inputting same into said code generator means and said bit length means.

10. Apparatus as defined in claim 9 wherein said probability means comprises divider means for forming a binary fractional frequency, and said power-of-2 frequency means comprises a gating circuit means for changing to zero all decimals to the right of the most significant "1" bit appearing in the binary fraction formed by said divider means.

11. Apparatus as defined in claim 10 wherein said sample window means includes character sequencing means for dropping the first character in the sample sequence of M characters and adding the most recent character, M+1, to continuously revise the sample sequence of M characters in said sample window means.

12. Apparatus as defined in claim 11 wherein said encoder means further includes probability means connected to said histogram forming means for determining the probability of occurrence of a given character, and power-of-2 frequency means connected to said probability means for determining all power-of-2 frequencies present in the sample and inputting same into said code generator means and said bit length means.

13. Apparatus as defined in claim 12 wherein said bit length means assigns any character k a code of bit length β

(k), where β

(k) is the smallest positive integer such that the non-zero probability p(k) of a character appearing is >

or = to 1/(2 to the β

(k) power).

14. Apparatus as defined in claim 11 wherein said code generating means includes, in combination:

(a) fractional coding resources means for receiving the input data stream and for determining all characters of a predetermined frequency;

(b) character index means for receiving the character based input data stream and for specifying the position of a given character in an ordered set within the range zero <

or = to i(k) <

or = to η

(q)-1, where i(k) is a character index and η

(q) is a table of the power-of-2 frequencies contained in the incoming data streams; and

(c) summing means connected to said fractional coding resources means and said character index means for receiving and summing output signals from same to develope a code for each character contained in the data stream.

15. Apparatus as defined in claim 14 wherein said fractional coding resources means includes a table forming means for performing a look-up function of a table η

(y), where y is a set of all possible power-of-2 frequencies [1/2, 1/4, 1/8 . . . , 0].

16. Apparatus as defined in claim 15 wherein said receiver means includes decoder means, comprising, in combination:

(a) index guess means for receiving a coded data from said data link means and for computing a hypothetical character index based on the data received;

(b) histogram reforming means based on a sample of decoded characters for developing a history of such sample, said histogram reforming means having a window identical to a window of said histogram forming means, an index computed by said index guess means being fed to said histogram reforming means;

(c) power-of-2 frequency estimating means forming an input to said index guess means for developing a power-of-2 frequency q(k) for a coded character; and

(d) comparator means having respective inputs connected to said histogram forming means and said power-of-2 frequency estimating means for sequencing possible characters until q(k'"'"')=q(k).

17. Apparatus as defined in claim 16 wherein said decoder means further comprises a comparator unit, and table reforming means partially forming said index guess means and also connected in parallel thereto and to said comparator unit, the output of the comparator unit being i'"'"'≦

η

(q'"'"'), a multiplexer, and the output of the comparator unit forming one input to said multiplexer, and output of said multiplexer enabling said index guess means until a correct index is computed.

18. Apparatus as defined in claim 16 wherein said comparator means causes a decoded character k to be gated from an input to said histogram forming means when q.sup.(k'"'"') =q(k).

19. Apparatus as defined in claim 18 wherein said decoder means further comprises a comparator unit, and table reforming means partially forming said index guess means and also connected in parallel thereto and to said comparator unit, the output of the comparator unit being i'"'"'>

η

(q'"'"'), a multiplexer, and the output of the comparator unit forming one input to said multiplexer, and output of said multiplexer enabling said index guess means until a correct index is computed.