Data compression, encryption, and in-line transmission system

• US 4,386,416 A
• Filed: 06/02/1980
• Issued: 05/31/1983
• Est. Priority Date: 06/02/1980
• Status: Expired due to Term

• Current Assignee: SGS-Thomson Microelectronics (STMicroelectronics NV)
• Original Assignee: Mostek Corporation (Raytheon Technologies Corporation d/b/a RTX)
• Inventors: Mueller, Jack C., Giltner, Michael E., Fiest, Robert R.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US06/261,123
• Time in Patent Office: 1,093 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300
• US Class Current: 710/68
• 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
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 9/0637 Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]
• CPC Class Codes: H04L 9/065 Encryption by serially and continuously modifying data stream elements, e.g. stream cipher systems, RC4, SEAL or A5/3

Abstract

An in-line data compression system which reduces the number of binary bits required to transmit a given text or similar message over a data network such as Telex or TWX. The compression unit can transmit or receive standard messages or can transmit compressed and encrypted messages to remote stations decrypt, and decompress messages from remote stations. The text data is compressed by identifying each word, searching for the word in a fixed library of words, and transmitting a first escape code plus the library address if the word is found. If the word is not found in the fixed library, a search is made for the word in a reconfiguration library and a second escape code plus the reconfiguration library address is transmitted if the word is found. If the word is not found in the reconfiguration library, the word is transmitted one character at a time using variable length character codes produced by a "Huffman" type code generator. The reconfiguration library is compiled by placing each word which is not in the library in the reconfiguration library before it is transmitted by variable length code. Then the second and each subsequent time that the same word is found in the message, the second escape code plus the address in the reconfiguration library will be transmitted in lieu of the Huffman coded characters of the word. The system is also applicable to compression of other types of data, serial or parallel, such as digital color television, for example.

Claims

1. A system for compressing data by reducing the number of binary bits required to represent the data comprising:

memory means for storing each of a plurality of selected units of a set of units in unit positions to form a library, each unit position having a memory address expressed in bits,

processing means for detecting each unit in the data and searching the memory to determine if the respective unit in the data is in the library, and alternatively compiling data representative of the units which are not stored in the memory library or the addresses of the units which are stored in the memory library together with a code indicating which alternative is compiled in each instance.

2. The system of claim 1 wherein:

each unit of data is representative of a word in a textual message,

each word is comprised of two or more characters, and

each character is represented by a predetermined number of binary bits.

3. The system of claim 2 wherein the processing means further comprises means for compiling the characters not included as a word unit stored in the library as a variable length code.

4. The system of claim 1 wherein:

each unit of data is represented by the same number of binary bits, which number is greater than the number of binary bits required to represent the addresses of the unit positions in memory.

5. The system of claim 1 wherein

the memory means for storing the selected unit comprises memory from which data can only be read.

6. The system of claim 1 wherein the memory means for storing the selected units is a memory into which data representative of the units can be written and from which the data representative of the units can be read.

7. The system of claim 6 wherein the memory means also includes means for storing selected units from which data can only be read, and wherein

the processing means sequentially searches the portion of the memory means from which data can only be read and the portion of the memory means into which the data can be written and from which the data can be read.

8. The system of claim 6 wherein the processing means further comprises means for compiling the units which are not found in the library by a variable length code representing sub parts of the unit.

9. The system of claim 1 further comprising means coupled to the processing means for encrypting the compressed data stream.

10. The system of claim 1 wherein the units of data are each comprised of sub units of fixed binary length and the processing means compiles the units not stored in the memory means as a variable length code representing the fixed length sub units.

11. The system of claim 1 wherein the processing means further comprises:

storage means for receiving and storing a non-compressed data stream received from an outside source, and

the processing means includes

means for transmitting a compressed data stream.

12. The system of claim 7 further comprising

storage means coupled to the processing means for storing compressed data and wherein

the processing means further comprises means for storing at least a portion of the compressed data stream before the compressed data stream is transmitted.

13. The system of claim 1 wherein the processing means further comprises:

means for automatically receiving a standard data stream from a first station, compressing the data stream and sending the compressed data stream to a second station, or automatically receiving a compressed data stream from a second station, decompressing the received compressed data stream, and sending the decompressed data stream to the first station.

14. The system of claim 13 further comprising

buffer means coupled to the processing means for storing call-up instructions for establishing communication with the second station and at least a portion of a standard message received from the first station, and wherein

the processing means includes means for automatically executing the call up of the second station and compressing and sending the standard message so stored.

15. The system of claim 14 wherein the processor means includes

means for detecting an answer back from the second station indicating whether the second station is equipped with decompression capability and for sending the data stream in standard form if the second station does not have decompression capability.

16. The system of claim 15 wherein the processor means includes:

means for detecting whether a received data stream is in standard form or compressed form, and for sending a standard data stream received from the second station to the first station in standard form.

17. The system of claim 16 further comprising a second system for compressing data having the same capabilities as the system of claim 15, each of the systems being coupled to a local text encoding and decoding unit, and, the systems for compressing data being coupled by a data transmission link.

18. A text compression unit for disposition between a local text encoding and decoding station of a telecommunication network and the communications network interface for communication with remote stations which may or may not be equipped with a similar text compression unit comprising:

multiplex means for coupling the unit between the local text encoding and decoding station and the network interface unit, and

data processing and storage means coupled to the multiplex means for automatically receiving a standard data stream from the local station, compressing the standard data stream to produce a compressed data stream, and sending the compressed data stream to a remote station, and for receiving a compressed data stream from a remote station, decompressing the compressed data stream received from the remote station, and sending the decompressed data stream to the local station and for compiling a library of data units in a memory during compression of the data by writing each data unit into the memory upon the first occurrence of each data unit and for each occurrence thereafter compiling the address of the data 1 unit in the library instead of an original representation of the data unit.

19. The text compression unit of claim 18 wherein the data processing and storage means further includes means for:

storing call-up instructions for establishing communications with the remote station and at least a portion of a standard message received from the local station,

automatically and repeatedly executing the call-up of the remote station until the remote station answers-back,

determining from the answer-back whether the remote station is equipped to decompress a compressed message, and either

sending a compressed or standard message to the remote station in accordance with the capability of the remote station as signalled by the answer-back.

20. The text compression unit of claim 18 wherein the data processing and storage means further includes means for simultaneously receiving and storing a message from both the local station and from the remote station, then forwarding the respective messages to the other terminals.

21. The text compression unit of claim 18 wherein the data processing and storage means further includes means for:

answering a call-up from a remote station with an indication of being equipped with compatible decompression means,

receiving and storing a message from the remote station,

determining whether the received message is a standard or compressed message,

decompressing the message if compressed, and

sending the standard message, either as received or as decompressed, to the local station.

22. The text compression unit of claim 18 wherein the data processing and storage means further includes a fixed library of words each stored at predetermined addresses from which the words can be read,

a variable length encoder for encoding individual text characters as a variable number of binary bits with the least number of binary bits used to represent the most frequently occurring characters, and wherein

the data processing and storage means compiles a compressed message by, with respect to each successive word of the standard message,

(a) searching a fixed library for the word and compiling a first escape code plus the address of the word in the fixed library if the word is found, and if the word is not found

(b) searching the reconfiguration library for the word and compiling a second escape code plus the address of the word in the fixed library is the word is found, and if the word is not found, then

(c) writing the word into a word position of the reconfiguration library selected in a predetermined manner and

(d) encoding each character of the word in a variable length code, and wherein

the data processing and storage means compiles a decompressed message from a received compressed message by

(a) unless a second or first escape code is detected, decoding the variable length code to compile the words in standard form in a standard message and writing the decoded characters of the words into a word position of the reconfiguration library selected in a predetermined manner, and

(b) if a second escape code is detected, compiling the word from the address of the reconfiguration library received with the second escape code, and

(c) if a first escape code is detected, compiling the word from the address of the fixed library received with the first escape code.

23. The text compression unit of claim 22 wherein the predetermined manner in which the word position in the reconfiguration library is selected by the data processing and storage means comprises:

maintaining a resettable access counter for each word position to determine the number of times the word position designated by the address has been written into or read from, and establishing a sequential order in which the count of the access counters is determined,

resetting all access counters at the beginning of a data batch to an initial lowest reference count,

selecting the first word position in the sequential order of those word positions having the lowest count, and

incrementing the count of the access counter for the word position each time the word position is accessed for writing or reading.

24. The text compression unit of claim 22 further comprising

encryption and decryption means coupled to the data processing and storage means for encrypting a data stream for security in accordance with an ecryption key and for decrypting a data stream in accordance with said encryption key, and wherein

the data processing and storage means further includes means for selectively operating the encryption and decryption means to encrypt the compressed data stream before the data stream is sent to a remote station, and

detecting an encrypted data stream from a remote station and operating the encryption and decryption means to decrypt the incoming data stream to produce a compressed data stream for compression.

25. A method for compressing data by reducing the number of binary bits required to represent the data comprising:

storing each of a plurality of selected units of a set of units in unit positions to form a library, each unit position having a memory address expressed in bits,

detecting each unit in the data and searching the memory to determine if the respective unit is in the library, and alternatively compiling data representative of the units which are not stored in the memory library or the addresses of the units which are stored in the memory library together with a code indicating which alternative is compiled in each instance.

26. The method of claim 25 wherein:

each unit of data is representative of a word in a textual message,

each word is comprised of two or more characters, and

each character is represented by a predetermined number of binary bits.

27. The method of claim 26 further comprising compiling the characters not included as a word unit stored in the library as a variable length code.

28. The method of claim 25 wherein:

each unit of data is represented by the same number of binary bits, which number is greater than the number of binary bits required to represent the addresses of the unit positions in memory.

29. The method of claim 25 wherein

the selected units stored in memory are selected statistically from data sample other than the specific data being compressed.

30. The method of claim 25 wherein the selected units stored in memory are selected statistically from the specific data batch being compressed.

31. The method of claim 30 further comprising

compiling the library of units in the memory during compression of the data by writing each unit into the memory upon the first occurrence of each unit to form a reconfiguration library and for each occurrence thereafter compiling the address of the unit in the library instead of the original representation of the unit.

32. The method of claim 31 wherein

the selected units stored in memory are selected statistically from a data sample over than the specific data being compressed and stored in a fixed library, and

sequentially searches the fixed library and the reconfiguration library and compiling the address of each unit found therein instead of the original data representative of the unit.

33. The method of claim 32 wherein the units are text words and further comprising compiling each character of the words which are not found in a library as a variable length code representing each character.

34. The method of claim 33 further comprising encrypting the compressed data stream.

35. The method of claim 25 further comprising encrypting the compressed data stream.

36. The system method of claim 25 wherein the units of data are each comprised of sub units of fixed binary length and the units not stored in the memory means are compiled as a variable length code representing the fixed length sub units.

37. The method of claim 25 further comprising:

receiving and storing at least a portion of a non-compressed data stream from a sending source, and

storing at least a portion of the compressed data stream and then sending the compressed data stream to a receiving station.

38. The method of claim 25 further comprising

decompressing the compressed data stream by detecting the library addresses and compiling the original data by fetching units from an identically compiled library as designated by the respective addresses.

39. The method for compressing and decompressing data by reducing the number of binary bits required to represent the data, comprising:

(1) during compression compiling a reconfiguration library of data units in which data units are stored in a limited number of data unit positions in a memory by

(a) searching the reconfiguration library for each data unit and if the data unit is not stored in the library, writing the data unit into a data unit position selected in a predetermined manner and then compiling the data unit in a compressed data stream in a form representative of the original data, or

(b) if the data unit is stored in the reconfiguration library, compiling a code so indicating together with the address of the data unit in the reconfiguration library in the compressed data stream, and

(2) during decompression compiling a reconfiguration library of data units in which data units are stored in a corresponding number of data unit positions in a memory by distinguishing between data units and addresses in the compressed data stream, and

(a) when a data unit is received, searching the reconfiguration library for the data unit and if the data unit is not stored in the library, writing the data unit into a data unit position selected in said predetermined manner and then compiling the data unit in a decompressed data stream in a form representative of the original data, and

(b) when an address is received, compiling the data unit stored in the data unit position designated by the address in the decompressed data stream in the form of the original data.

40. The method of claim 39 wherein said predetermined manner of selecting the data unit positions comprises

establishing a predetermined sequence of search for the data unit positions,

establishing an access counter for each data unit position,

resetting all data unit positions to indicate that the positions are empty before the beginning of a data batch, and

writing each successive data unit not found in the reconfiguration library into the next successive data unit position having the lowest access count, and

incrementing the access counter for each data unit position each time the data unit position is accessed for writing data into or reading data from the data unit position.

41. The method for compressing text data having binary coded characters formed into words comprising

compiling a fixed library of words each stored at predetermined addresses in a memory from which the words can be read,

establishing a reconfiguration library having a plurality of empty word positions into which words can be written and from which words can be read,

providing variable length encoding for individual text characters as a variable number of binary bits with the least number of binary bits used to represent the most frequently occurring characters, and

compiling a compressed message by, with respect to each successive word of the standard message,

(a) searching the fixed library for the word and compiling a first escape code plus the address of the word in the fixed library if the word is found, and if the word is not found

(b) searching the reconfiguration library for the word and compiling a second escape code plus the address of the word in the fixed library if the word is found, and if the word is not found, then

(c) writing the word into a word position of the reconfiguration library selected in a predetermined manner and

(d) encoding each character of the word in a variable length code, and

compiling a decompressed message from a received compressed message by

(a) unless a second or first escape code is detected, decoding the variable length code to compile the words in standard form in a standard message and writing the decoded characters of the words into a word position of the reconfiguration library selected in a predetermined manner, and

(b) if a second escape code is detected, compiling the word from the address of the reconfiguration library received with the second escape code, and

(c) if a first escape code is detected, compiling the word from the address of the fixed library received with the first escape code.

42. The method of claim 41 wherein the predetermined manner in which the word position in the reconfiguration library is selected comprises:

maintaining a resettable access counter for each word position to determine the number of times the word position designated by the address has been written into or read from, and establishing a sequential order in which the count of the access counters is determined,

resetting all access counters at the beginning of a data batch to an initial lowest reference count,

selecting the first word position in the sequential order of those word positions having the lowest count, and

incrementing the count of the access counter for the word position each time the word position is accessed for writing or reading.