EP0283735A2 — Adaptive data compression method and apparatus

Claim 1

Independent Claim 218 words

In a communication system including an encoding modem (10) and a decoding modem (15), each of the modems including a memory (35) for storing data, a controller (30), a telephone interface circuit (24), and a computer interface circuit (22), a dynamic data compression method CHARACTERIZED BY the steps of: (1) providing an encoding table (T1) comprising a plurality of digital codes (60a, 60b) associated with characters of an alphabet (45), some of the digital codes (60a) being shorter than others (60b); (2) presenting for encoding an item of data (70) represented by one of the characters of the alphabet (45); (3) in response to the presented item of data, selecting a code (60) from the encoding table which corresponds to the particular character of the alphabet represented by the presented item of data (70); (4) providing the selected code (60) as an output; and (5) periodically adjusting the corresponding relationship of the codes (60) and the characters of the alphabet (45) in the encoding table as a function of the frequency of occurrence (CC) of characters of the alphabet over a plurality of characters presented for encoding, whereby as the frequency of occurrence of characters over a plurlity of characters presented for encoding changes, the more frequently occurring characters become associated with shorter codes in the encoding table.

Claim 2

Dependent Claim 218 words

In a communication system including an encoding modem (10) and a decoding modem (15), each of the modems including a memory (35) for storing data, a controller (30), a telephone interface circuit (24), and a computer interface circuit (22), a dynamic data compression method CHARACTERIZED BY the steps of: (1) providing an encoding table (T1) comprising a plurality of digital codes (60a, 60b) associated with characters of an alphabet (45), some of the digital codes (60a) being shorter than others (60b); (2) presenting for encoding an item of data (70) represented by one of the characters of the alphabet (45); (3) in response to the presented item of data, selecting a code (60) from the encoding table which corresponds to the particular character of the alphabet represented by the presented item of data (70); (4) providing the selected code (60) as an output; and (5) periodically adjusting the corresponding relationship of the codes (60) and the characters of the alphabet (45) in the encoding table as a function of the frequency of occurrence (CC) of characters of the alphabet over a plurality of characters presented for encoding, whereby as the frequency of occurrence of characters over a plurlity of characters presented for encoding changes, the more frequently occurring characters become associated with shorter codes in the encoding table.

Claim 3

Dependent Claim 210 words

A data decompression method for decompressing data compressed by the method of Claim 1, FURTHER CHARACTERIZED BY the steps of: (1) providing a decoding table (T2) in parallel to the'encoding table (T1) used for compression, said decoding table having a plurality of digital codes (60) associated with the characters of the alphabet in the manner of the encoding table, some of the digital codes (60a) being shorter than others (60b); (2) presenting for decoding an item of coded data represented by one of the digital codes (60); (3) in response to the presented item of coded data, selecting a character (65) from the decoding table which corresponds to the particular digital code (60) represented by the presented item of coded data; (4) providing the selected character (65) as a decoded output; and (5) periodically adjusting the corresponding relationship of the codes and the characters of the alphabet in the decoding table as a function of the frequency of occurrence (CC) of characters of the alphabet over a plurality of characters resultant from decoding, whereby as the frequency of occurrence of characters over a plurality of characters resultant from decoding changes, the more frequently occurring characters become associated with shorter codes in the decoding table in parallel with the encoding table.

Claim 4

Dependent Claim 213 words

The method of Claim 1 FURTHER CHARACTERIZED IN THAT the characters in the alphabet (45) and their corresponding codes (60) are arranged in an initial ordered array, with shorter codes (60a)toward the beginning of the array and longer codes toward the end of the array, and FURTHER CHARACTERIZED IN THAT the step of periodically adjusting the corresponding relationship of the codes and the characters of the alphabet in the encoding table comprises the steps of: (6) maintaining a character count (CC) associated with each character of the alphabet; (7) incrementing .the particular character count (CC1) associated with the particular character. represented by an item of data presented for encoding after selecting a code from the encoding table; (8) after incrementing the character count (CC1 comparing the particular character count to the character count for a preselected character (CC2) at a position in the array more likely to be associated with a shorter code; and (9) if the particular character count is greater than the character count for the preselected character, exchanging the relative positions in the array of the character just encoded with the preselected character so as to associate the character having the larger character count (CC1) with a position in the array more likely to be associated with a shorter code.

Claim 5

Dependent Claim 32 words

The method of Claim 3, FURTHER CHARACTERIZED IN THAT the preselected character is positioned a predetermined number of positions in the array toward the beginning of the array from the particular character.

Claim 6

Dependent Claim 16 words

The method of Claim 4, FURTHER CHARACTERIZED IN THAT the predetermined number of positions is sixteen.

Claim 7

Dependent Claim 85 words

The method of Claim 1, FURTHER CHARACTERIZED IN THAT the encoding table comprises a plurality of sets of digital codes (50a, 50b, 50c), each of the sets comprising digital codes of the same predetermined length within each set but different between sets, with the sets being arranged in an initial ordered array associated with the characters of the alphabet beginning with a set having shorter codes (50a) toward the beginning of the array and a set having larger codes (50b)toward the end of the array.

Claim 8

Dependent Claim 65 words

The method of Claim 6, FURTHER CHARACTERIZED IN THAT each of the sets of codes (50a, 50b, 50c) are initially preset at a predetermined size, and further comprising the step of periodically adjusting the sizes of the sets, whereby the numbers of characters represented by different digital codes changes as a function of the frequency of occurrence of characters in the data presented for encoding.

Claim 9

Dependent Claim 142 words

The method of Claim 7, FURTHER CHARACTERIZED IN THAT the step of periodically adjusting the sizes of the sets comprises the steps of: (1) summing the character counts for predetermined groups of consecutive characters to obtain a plurality of group counts (80); (2) comparing the group count (80a) for groups towards the end of the array with the character counts (CCa) for characters towards the beginning of the array; (3) increasing the size of the set of the shortest digital codes (50a) until there is a correspondence between a group count and a character count at the end of the set of shortest digital codes, whereby the size of the set of the shortest digital codes is increased to include more characters having a higher probability of occurrence than any the characters in the set of codes associated with the group counts.

Claim 10

Dependent Claim 61 words

The method of Claim 8, FURTHER CHARACTERIZED IN THAT there are at least three sets of digital codes (50a, 50b, 50c), and wherein the set associated with the longest digital codes (50c) increases in size in increments of the size of the groups while the set associated with the shortest codes (50a) increases in size in increments of a single characters.

Claim 11

Dependent Claim 25 words

The method of Claim 9, FURTHER CHARACTERIZED IN THAT the set associated with the shortest digital codes (50a) varies in size between 0 and 15.

Claim 12

Dependent Claim 25 words

The method of Claim 9, FURTHER CHARACTERIZED IN THAT the set associated with the longest digital codes (50c) varies in size between 0 and 240.

Claim 13

Dependent Claim 24 words

The method of Claim 9, FURTHER CHARACTERIZED IN THAT the shortest digital code is 4 bits, and the longest digital code is 12 bits.

Claim 14

Dependent Claim 36 words

The method of Claim 9, FURTHER CHARACTERIZED IN THAT the set associated with the shortest digital codes (50a) initially has 4 members and the set associated with the longest digital codes (50c) initially has 64 members.

Claim 15

Dependent Claim 37 words

1 4. The method of Claim 8, FURTHER CHARACTERIZED IN THAT the step of periodically adjusting the sizes of the sets is repeated after the occurrence of a predetermined number of items of data presented for encoding.

Claim 16

Dependent Claim 24 words

The method of Claim 14, FURTHER CHARACTERIZED IN THAT the predetermined number of items between adjustments to the size of the sets is 128.

Claim 17

Dependent Claim 18 words

The method of Claim 8, FURTHER CHARACTERIZED IN THAT the predetermined groups of consecutive characters have sixteen characters.

Claim 18

Dependent Claim 30 words

The method of Claim 7, FURTHER CHARACTERIZED IN THAT the step of periodically adjusting the sizes of the sets is taken after every k items of data presented for encoding.

Claim 19

Dependent Claim 12 words

The method of Claim 17, FURTHER CHARACTERIZED IN THAT k is 128.

Claim 20

Dependent Claim 226 words

The method of Claim 7, FURTHER CHARACTERIZED IN THAT there are n characters in the alphabet (45), wherein the set associated with the shortest digital code (50a) has a members, and the set associated with the longest digital code (50c) has c members, and FURTHER CHARACTERIZED IN THAT the step of periodically adjusting the sizes of the sets comprises changing the relative values of the numbers a and c by taking the following steps: (i) summing the character counts (CC) for consecutive groups (80) of m characters to obtain a plurality of n/m group counts; (ii) comparing the group count (80) for group (n/m)-i -1 to the character count for character j, where I is an integer index of group counts beginning at zero and j is an integer index into the array beginning at zero at the top of the array; (iii) if the group count (80) for group (n/m)-i-1 is less than the character count for character j then, incrementing I and j and going back to the step (ii); (iv) if the group count (80) for group (nlm)-1-1 is greater than or equal to the character count for character j, then establishing an encoding level of a =] + 1 6y assigning + 1 of the shortest digital codes, and c = (nlm) x (I + 1 ) of the longer digital codes.

Claim 21

Dependent Claim 48 words

The method of Claim 19, FURTHER CHARACTERIZED IN THAT there is a set of characters having digital codes sized in between the shortest digital code and the longest digital code and having b members, and wherein b = n -(j + 1) -((nlm ) x (I + 1)).

Claim 22

Dependent Claim 239 words

In a data processing, storage, or communication system wherein data is to be compressed for processing, storage or communication, including a memory means (35) for storing data, a data processor (30) for manipulating data, an input circuit (22) for receiving an item of data (70) for encoding, and an output circuit (24) for providing an output; a dynamic data compression apparatus, CHARACTERIZED BY: said memory means storing an encoding table (T1) comprising a plurality of digital codes (60) associated with characters of an alphabet (45), some of the digital codes (60a) being shorter than others (60b); said item of data (70) being represented by one of the characters of the alphabet (45); said data processor (30) being responsive to the presented item of data (70) for generating a code (60) which corresponds to the particular character of the alphabet represented by the presented item of data; said output circuit (24) providing the generated code (60) as an output; and said data processor (30) periodically adjusting the corresponding relationship of the codes (60) and the characters of the alphabet in the encoding table in said memory means as a function of the frequency of occurrence of characters (CC) of the alphabet over a plurality of characters presented for encoding, whereby as the frequency of occurrence of characters over a plurality of characters presented for encoding changes, the more frequently occurring characters become associated with shorter codes in the encoding table.

Claim 23

Dependent Claim 239 words

In a data processing, storage, or communication system wherein data is to be compressed for processing, storage or communication, including a memory means (35) for storing data, a data processor (30) for manipulating data, an input circuit (22) for receiving an item of data (70) for encoding, and an output circuit (24) for providing an output; a dynamic data compression apparatus, CHARACTERIZED BY: said memory means storing an encoding table (T1) comprising a plurality of digital codes (60) associated with characters of an alphabet (45), some of the digital codes (60a) being shorter than others (60b); said item of data (70) being represented by one of the characters of the alphabet (45); said data processor (30) being responsive to the presented item of data (70) for generating a code (60) which corresponds to the particular character of the alphabet represented by the presented item of data; said output circuit (24) providing the generated code (60) as an output; and said data processor (30) periodically adjusting the corresponding relationship of the codes (60) and the characters of the alphabet in the encoding table in said memory means as a function of the frequency of occurrence of characters (CC) of the alphabet over a plurality of characters presented for encoding, whereby as the frequency of occurrence of characters over a plurality of characters presented for encoding changes, the more frequently occurring characters become associated with shorter codes in the encoding table.

Claim 24

Dependent Claim 256 words

A data decompression apparatus for decompressing data compressed by the apparatus of Claim 21, including a second memory means (35) for storing data, a data processor (30) for manipulating data, an input circuit (24) for receiving a coded item of data (60) for decoding and an output circuit (22) for providing a decoded output output, CHARACTERIZED BY: said second memory means (35) storing a decoding table (T2) in parallel to the encoding table (T1) used for compression, said decoding table having a plurality of digital codes (60) associated with the characters of said alphabet (45) in the manner of the encoding table, some of the digital codes (60a) being shorter than others (60b); said data processor (30) being responsive to the presented item of coded data (60) for selecting a character (65) from the decoding table (T2) in said memory means which corresponds to the particular digital code represented by the presented item of coded data; said output circuit (22) providing the selected character as a decoded output; and said data processor (30) periodically adjusting the corresponding relationship of the codes (60) and the characters of the alphabet in the decoding table in said second memory means as a function of the frequency of occurrence of characters (CC) of the alphabet over a plurality of characters resultant from decoding, whereby as the frequency of occurrence of characters over a plurality of characters resultant from decoding changes, the more frequently occurring characters become associated with shorter codes in the decoding table in parallel with the encoding table.

Claim 25

Dependent Claim 228 words

The apparatus of Claim 21, FURTHER CHARACTERIZED IN THAT the characters in the alphabet and their corresponding codes are arranged in an initial ordered array in said memory means, with shorter codes (60a) towards the beginning of the array and longer codes (60b) toward the end of the array, and wherein said data processor (30) adjusts the corresponding relationship of the codes and the characters of the alphabet in the encoding table in said memory means and FURTHER CHARACTERIZED BY: maintaining a character count (CC) associated with each character of the alphabet (45) in said memory means (35); said data processor (30) incrementing the particular character count associated with the particular character represented by an item of data presented for encoding after providing a coded output; said data processor (30) comparing the particular character count to the character count for a preselected character at a position in the array more likely to be associated with a shorter code after incrementing the character count; and said data processor (30) being responsive to the particular character count being greater than the character count for the preselected character for exchanging the relative positions in the array of the character just encoded with the preselected character so as to associate the character having the larger character count with a position in the array more likely to be associated with a shorter code.

Claim 26

Dependent Claim 33 words

The apparatus of Claim 23, FURTHER CHARACTERIZED IN THAT the preselected character is positioned a predetermined number of memory locations in the array toward the beginning of the array from the particular character.

Claim 27

Dependent Claim 17 words

The apparatus of Claim 24, FURTHER CHARACTERIZED IN THAT the predetermined number of memory locations is sixteen.

Claim 28

Dependent Claim 90 words

The apparatus of Claim 21, FURTHER CHARACTERIZED IN THAT the encoding table comprises a plurality of sets of digital codes (50a, 50b, 50c), each of the sets comprising digital codes of the same predetermined length within each set but different between sets, with the sets being arranged in an initial ordered array in said memory means associated with the characters of the alphabet beginning with a set having shorter codes (50a) toward the beginning of the array and a set having larger codes (50c) toward the end of the array.

Claim 29

Dependent Claim 62 words

The apparatus of Claim 26, FURTHER CHARACTERIZED IN THAT each of the sets of codes (50) are initially preset at a predetermined size, and said data processor (30) periodically adjusts the sizes of the sets, whereby the numbers of characters represented by different digital codes changes as. a function of the frequency of occurrence of characters in the data presented for encoding.

Claim 30

Dependent Claim 145 words

The apparatus of Claim 27, FURTHER CHARACTERIZED IN THAT: said data processor (30) is operative for summing the character counts for predetermined groups of consecutive characters to obtain a plurality of group counts (80); said data processor (30) is operative for comparing the group count (80) for groups towards the end of the array with the character counts (CC) for characters towards the beginning of the array; said data processor (30) is operative for increasing the size of the set of the shortest digital codes until there is a correspondence between a group count and a character count at the end of the set of shortest digital codes, whereby the size of the set of the shortest digital codes is increased to include more characters having a higher probability of occurrence than any the characters in the set of codes associated with the group counts.

Claim 31

Dependent Claim 16 words

The apparatus of Claim 21, FURTHER CHARACTERIZED IN THAT said apparatus is employed in a modem.

Claim 32

Dependent Claim 157 words

In a data processing, storage, or communication system wherein data is to be compressed for processing, storage or communication, including a data processor (30) for manipulating data, an input circuit (22) for receiving a character to be transmitted or stored, and an output circuit (24) for providing an output, a method for compressing an input data string having a string of m repetitive characters, particularly useful for transmitting data with a modem (10) over a communications link (12), CHARACTERIZED BY the steps of: (1) entering a "repeat state" (90) by detecting the occurrence of a predetermined number n instances of repetitive characters received by said input circuit (22); (2) transmitting data with said output circuit (24) representing the predetermined number n repetitive characters; and (3) immediately following step (2), transmitting with said output circuit (24) a coded first indicium (91) representing the number o of occurrences of the repetitive characters subsequent to the n instances, where n+o=m.

Claim 33

Dependent Claim 157 words

In a data processing, storage, or communication system wherein data is to be compressed for processing, storage or communication, including a data processor (30) for manipulating data, an input circuit (22) for receiving a character to be transmitted or stored, and an output circuit (24) for providing an output, a method for compressing an input data string having a string of m repetitive characters, particularly useful for transmitting data with a modem (10) over a communications link (12), CHARACTERIZED BY the steps of: (1) entering a "repeat state" (90) by detecting the occurrence of a predetermined number n instances of repetitive characters received by said input circuit (22); (2) transmitting data with said output circuit (24) representing the predetermined number n repetitive characters; and (3) immediately following step (2), transmitting with said output circuit (24) a coded first indicium (91) representing the number o of occurrences of the repetitive characters subsequent to the n instances, where n+o=m.

Claim 34

Dependent Claim 15 words

The method of Claim 30, FURTHER CHARACTERIZED IN THAT the predetermined number n is three.

Claim 35

Dependent Claim 94 words

A method of decompressing data compressed with the method of Claim 30, CHARACTERIZED BY the steps of: (1) detecting a "repeat state" (90) in received data by detecting the occurrence of a predetermined number n instances of repetitive characters; (2) providing n characters representing the predetermined number n repetitive characters; and (3) following the n repetitive characters, receiving the first indicium (91) representing the number o of occurrences of the repetitive data subsequent to the n instances, where n + o = m; and (4) providing o decoded characters subsequent to the n characters.

Claim 36

Dependent Claim 23 words

The method of Claim 30, FURTHER CHARACTERIZED IN THAT the first indicium (91) represents a number between zero and a predetermined numberp characters.

Claim 37

Dependent Claim 37 words

The method of Claim 33, FURTHER CHARACTERIZED IN THAT in response to the first indicium being p, providing a second coded indicium (91 b)representing an additional number of occurrences of repetitive characters subsequent to the p instances.

Claim 38

Dependent Claim 12 words

The method of Claim 33, FURTHER CHARACTERISED IN THAT p is fifteen.

Adaptive data compression method and apparatus

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag