Data compaction system and apparatus

• US 4,021,782 A
• Filed: 04/30/1975
• Issued: 05/03/1977
• Est. Priority Date: 01/07/1974
• Status: Expired due to Term

• Current Assignee: Microsoft Corporation
• Original Assignee: John S. Hoerning
• Inventors: Hoerning, John S.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US05/573,571
• Time in Patent Office: 734 Days
• Field of Search: 340/172.5, 340/347 DD, 444/1
• US Class Current: 341/51
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence

Abstract

A data compaction system and apparatus is disclosed which, in the preferred embodiment, includes a high speed compaction controller utilizing both read only storage and read-write storage. A compaction device according to the present invention could then be placed upon both ends of a transmission line, the data received by a compaction unit at one end of the line from whatever apparatus wished to transmit data on the line, the data compacted within the compaction unit according to the present invention, the data transmitted on the line to a compaction unit on the other end of the line, the data decompacted, and the data provided to whatever apparatus wished to receive the data. Data received by the compaction device according to the present invention in a fixed length, fixed number base, coded manner would then be compacted by altering the expression of the data, as by altering the number bases in which the data is expressed and by switching between number bases. Thus, it has been found that expressing the data as a string of characters of varying lengths and varying number bases, that is characters not all expressed in the same number base, shortens the overall length of the data transmitted. This is true even if the length of certain characters may be increased by the techniques according to the present invention. Also, prior character and prior record comparisons according to the present invention significantly enhance the compaction ability of the present invention.

Claims

1. Data compaction apparatus for use on a path of communication of groups of symbols, comprising in combination:

compaction apparatus inserted into the communication path at the transmission end and decompaction apparatus inserted into the communication path at the reception end for compacting data to be transmitted and decompacting data to be received, the compaction apparatus comprising;

means for accepting an input from the communication path;

means for controlling the compaction apparatus and causing the compaction apparatus to perform a data dependent sequence of operations;

means for storing, associated with the compaction apparatus and including a portion for storing selected data from the communication path and a portion for storing preset coding including coding for at least selected of the symbols from the communication path;

means for selectively causing the storage of symbols from the communication path and for providing sequential, real time, adaptive coding of symbols from the communication path by comparing the symbols received by the compaction device in a sequential and serial fashion with prior symbols received and stored in the means for storing and for causing a type of compacted symbol to be transmitted if a symbol within the coding means of the compaction apparatus conforms to a symbol of a prior symbol received and stored in the means for storing, and for causing another type of compacted symbol to be transmitted if the symbol within the coding means of the compaction apparatus is not appropriately conforming to prior symbols received and stored in the means for storing but conforms to the preset coding within the means for storing, and for causing yet another type of compacted symbol to be transmitted if the symbol within the coding means of the compaction apparatus is not appropriately conforming to prior symbols received and stored in the means for storing and not appropriately conforming to preset coding within the means for storing;

means for providing the sequences of symbols from the coding means to the communication path in a sequential fashion conforming to the sequence received; and

the decompaction apparatus comprising;

means for accepting an input from the communication path;

means for controlling the decompaction apparatus and causing the decompaction apparatus to perform compacted data dependent sequence of operations;

means for storing, associated with the decompaction apparatus and including a portion for storing selected data from the communication path and a portion for storing preset decoding including decoding for at least selected of the symbols from the communication path conforming to the selected symbols stored in the means for storing associated with the compaction apparatus;

means for providing sequential, real time, adaptive decoding of symbols from the communication path by recognizing the first mentioned type of compacted symbols, the another type of compacted symbols, and the yet another type of compacted symbols, and for providing appropriate decoded symbols from the means for storing conforming to the particular symbols received;

means for providing the decoded sequences of symbols from the decoding means to the communication path in a sequential fashion conforming to the sequence received;

means for providing electrical connection between the means for storing associated with the compaction apparatus and the means for controlling associated with the compaction apparatus;

means for providing electrical connection between the means for storing associated with the compaction apparatus and the coding means;

means for providing electrical connection between the means for storing associated with the decompaction apparatus and the means for controlling associated with the decompaction apparatus;

means for providing electrical connection between the means for storing associated with the decompaction apparatus and the decoding means;

means for providing electrical connection between the means for controlling associated with the compaction apparatus and the coding means;

means for providing electrical connection between the means for controlling associated with the decompaction apparatus and the decoding means.

2. The data compression apparatus of claim 1, wherein the coding means of the compaction apparatus comprises means for comparing the symbols received by the compaction device in a sequential and serial fashion with prior symbols received and prior groups of symbols received and stored in the means for storing associated with the compaction apparatus and for causing a first type of first mentioned sequence of compacted symbols to be transmitted if the symbol within the coding means of the compaction apparatus conforms to a symbol of a prior group received and stored in the means for storing associated with the compaction apparatus and for causing a second type of first mentioned sequence of compacted symbols to be transmitted if the symbol within the coding means of the compaction apparatus conforms to a symbol of a current group received and stored in the means for storing associated with the compaction apparatus.

3. The data compaction apparatus of claim 2, wherein the means for causing yet another type of sequence of symbols to be transmitted comprises means for transmitting the received symbols without compaction.

4. The data compression apparatus of claim 1, wherein the means for accepting an input from the communication path comprises buffering means and wherein the means for providing symbols to the communication path comprises buffering means.

5. Data compression apparatus for use on a path of communication of groups of symbols, comprising in combination:

means for storing;

means for providing sequential, real time, adaptive, open ended compaction of the symbols;

means for providing an electrical connection between the means for storing and the compaction means; and

means for providing an electrical connection between the compaction means and the communication path.

6. The apparatus of claim 5, wherein the means for storing includes a portion for providing read-only storage and a portion for providing read-write storage.

7. The apparatus of claim 5, wherein the means for providing an electrical connection between the communication path and the compaction means is transparent.

8. The apparatus of claim 5, wherein the means for providing an electrical connection between the compaction means and the communication path comprises input means for buffering the symbol input.

9. The apparatus of claim 8, wherein the means for providing an electrical connection between the communication path and the compaction device comprises output means for buffering the symbol output.

10. The apparatus of claim 5, further including decompaction apparatus and including means for providing an electrical connection between the decompaction means and the communication path.

11. A method of data compaction for use in conjunction with a path of transmission of groups of symbols, comprising the steps of:

intercepting data in the form of symbols upon the transmission path;

comparing the intercepted data with prior symbols received and stored;

if a comparison is reached, encoding the intercepted data to reflect such a comparison;

if no comparison is reached, encoding the intercepted data in a preset manner;

transmitting the results of the foregoing steps.

12. The method of claim 11, further including the steps of:

buffering the input and output;

monitoring the input and the output;

inactivating compaction upon the inability of the input and output buffering to properly maintain all intercepted data.

13. The method of claim 11, including the steps of:

monitoring the input and output; and

controlling the status of compaction with respect to the input and output of symbols.

14. The method of claim 11, wherein the comparison step further comprises:

comparing the intercepted data to a prior record received; and

comparing the intercepted data to a prior character received, both in an integrated manner.

15. The method of claim 14, wherein the encoding step if no comparison is reached comprises adding a transmission code to the intercepted data without further compaction.

16. The method of claim 14, wherein the encoding step if no comparison is reached comprises encoding the intercepted data by substituting a preset coding for the intercepted data.

17. The method of claim 14, wherein the encoding step if no comparison is reached comprises:

encoding the intercepted data by substituting a preset coding for selected of the data for which a coding has been preset; and

adding a transmission code to the intercepted data without further compaction for remaining of the intercepted data.

18. The method of claim 11, wherein the encoding step if no comparison is reached comprises adding a transmission code to the intercepted data without further compaction.

19. The method of claim 11, wherein the encoding step if no comparison is reached comprises encoding the intercepted data by substituting a preset coding for the intercepted data.

20. The method of claim 11, wherein the encoding step if no comparison is reached comprises:

encoding the intercepted data by substituting a preset coding for selected of the data for which a coding has been preset; and

adding a transmission code to the intercepted data without further compaction for remaining of the intercepted data.

21. The method of claim 11 wherein the step of comparing the intercepted data with prior symbols received and stored comprises comparing the symbols of the data of the group currently intercepted against symbols of the data of the group previously intercepted and stored by first comparing the symbols of the currently intercepted data with the symbols stored within specific storage space allocated to storage of previously intercepted symbols and (1) if no comparison is reached, storing the symbols of the data of the group currently intercepted, and compared in the previous method step, within the specific storage space allocated to storage of previously intercepted symbols and (2) if a comparison is reached between the symbols of the data of the group currently intercepted and symbols of the data of the group previously intercepted and stored within the storage space allocated to the storage of previously intercepted symbols, skipping the previous step of storing the symbols of the data of the group currently intercepted and compared, as the symbols of the data of the group currently intercepted and the symbols of the data of the group previously intercepted and stored are identical and it is not necessary to restore identical symbols.

22. The method of claim 21:

wherein the step of comparing the symbols of the data of the group currently intercepted against symbols of the data of the group previously intercepted and stored further comprises comparing the currently intercepted symbol with the correspondingly situated symbol of the data of the group of previously intercepted symbols received and stored; and

where the encoding step if a comparison is reached further comprises setting up a data independent coding indicating only that the symbol currently intercepted is identical to the correspondingly situated symbol in the previously intercepted group of symbols received and stored; and

wherein the step of comparing the symbols of the data of the group currently intercepted against the symbols of the data of the group previously intercepted and stored further comprises comparing the currently intercepted symbol with the immediately previously intercepted symbol received;

wherein the encoding step if a comparison is reached comprises setting up a data independent coding indicating only that the symbol currently intercepted is identical to the immediately previously intercepted symbol.

23. The method of claim 22 wherein the storage of symbols of data intercepted within the specific storage space allocated comprises storage of currently intercepted symbols over previously intercepted symbols.

24. The method of claim 22 wherein the step of comparing the currently intercepted symbol with the immediately previously intercepted symbol received is performed only if no comparison is reached indicating the currently intercepted symbol is identical to the correspondingly situated symbol in the group of previously intercepted symbols received and stored.

25. The method of claim 24 wherein the storage of symbols of data intercepted within the specific storage space allocated comprises storage of currently intercepted symbols over previously intercepted symbols.

26. The method of claim 21 wherein the storage of symbols of data intercepted within the specific storage space allocated comprises storage of currently intercepted symbols over previously intercepted symbols.

27. The method of claim 21:

wherein the step of comparing the symbols of the data of the group currently intercepted against symbols of the data of the group previously intercepted and stored further comprises comparing the currently intercepted symbol with the correspondingly situated symbol of the data of the group of previously intercepted symbols received and stored; and

where the encoding step if a comparison is reached further comprises setting up a data independent coding indicating only that the symbol currently intercepted is identical to the correspondingly situated symbol in the previously intercepted group of symbols received and stored.

28. The method of claim 27 wherein the step of encoding if a comparison is reached, comprises:

first setting up a symbol representing the reaching of a comparison;

next setting up a data independent symbol representing only the number of such symbols compared which are identical; and

collecting the symbols of the immediately preceding two steps in a manner allowing the transmission of the collected symbols.

29. The method of claim 28 further comprises automatically returning to the original comparing step.

30. The method of claim 28 wherein the storage of symbols of data intercepted within the specific storage space allocated comprises storage of currently intercepted symbols over previously intercepted symbols.

31. The method of claim 27 wherein the storage of symbols of data intercepted within the specific storage space allocated comprises storage of currently intercepted symbols over previously intercepted symbols.

32. The method of claim 21 wherein the step of encoding if a comparison is reached, comprises:

first setting up a symbol representing the reaching of a comparison;

next setting up a data independent symbol representing only the number of such symbols compared which are identical; and

collecting the symbols of the immediately preceding two steps in a manner allowing the transmission of the collected symbols.

33. The method of claim 21 wherein the step of encoding the intercepted data to reflect a comparison if a comparison is reached in the situation where at least two consecutive symbols are identical comprises the steps of:

first setting up an encoded symbol indicated the reaching of a comparison with respect to the first such identical symbol; and

subsequently setting up an encoded symbol indicating the number of such identical symbols.

34. The method of claim 33 wherein the encoding step if a comparison is reached comprises encoding in a data independent manner not reflective of data but only reflective of the reaching of a comparison.

35. The method of claim 11 wherein the step of encoding the intercepted data to reflect a comparison if a comparison is reached in the situation where at least two consecutive symbols are identical comprises the steps of:

first setting up an encoded symbol indicated the reaching of a comparison with respect to the first such identical symbol; and

subsequently setting up an encoded symbol indicating the number of such identical symbols.

36. The method of claim 35 wherein the encoding step if a comparison is reached comprises encoding in a data independent manner not reflective of data but only reflective of the reaching of a comparison.

37. The method of claim 11 wherein the encoding step if a comparison is reached comprises encoding in a data independent manner not reflective of data but only reflective of the reaching of a comparison.