Data compression system and apparatus

• US 4,232,375 A
• Filed: 06/12/1978
• Issued: 11/04/1980
• Est. Priority Date: 06/12/1978
• Status: Expired due to Term

• Current Assignee: NCR Corporation
• Original Assignee: NCR Corporation
• Inventors: Girard, Donald J., Paugstat, John F.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Chan, E.
• Application Number:
  US05/914,821
• Time in Patent Office: 876 Days
• Field of Search: 06F/5/00, 364/900 MS File, 364/200 MS File, 340/347 DD, 235/310
• US Class Current: 710/68
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

A system and apparatus for compressing a binary data message generated by a digital input device is disclosed wherein a data message generated in a data terminal device as part of a merchandise transaction is examined on the basis of information content with all data relating to redundant information previously generated or known being deleted together with encoding of preselected portions of the non-redundant data results in the compression of the data to a minimum amount without losing the informational content of the original data thereby allowing the compressed data to be stored in a relatively small storage unit located in the data terminal device. A compressed data record is generated including an encoded start of record character which may signify, in addition to the start of the compressed data record, the type of merchandise transaction being processed. Other non-redundant data which can be determined by knowing the corresponding data of a previous data message are also deleted with only that data required in order to reconstruct the original data generated being retained in the storage unit.

Claims

1. In a system for transmitting a plurality of data messages each comprising redundant and non-redundant characters between a data terminal device and a central processor in which a character is considered redundant if the character is the same in succeeding data messages, a data compression apparatus for generating a compressed data record representing the data messages generated as part of a merchandising operation by the data terminal device comprising in combination:

first storage means for storing the characters of the data messages generated by the data terminal devices;

means for generating a plurality of first control signals in response to the disabling of said central processing means and the storing of the data message in said first storage means;

timing control means operated in response to the generation of each of said first control signals to output a plurality of timing control signals;

second storage means for storing data representing a compressed data record;

table look-up means coupled to said first and second storage means and said timing control means for storing a plurality of first non-redundant characters together with an associated one of a plurality of start of compressed data record characters;

said table look-up means operated in response to the generation of another of said timing control signals to receive a first non-redundant character from said first storage means for storing in said second storage means one of said plurality of start of compressed data record characters in accordance with the first non-redundant character received from said first storage means, said start of compressed data record character also contains information representing the first non-redundant character;

third storage means coupled to said first storage means for storing a character of the first data message in response to the generation of one of said timing control signals;

means coupled to said first and third storage means for comparing the corresponding character of each succeeding data message with the character stored in said third storage means to determine if the character is redundant or non-redundant; and

control means responsive to the operation of said comparing means for storing in said second storage means the non-redundant character of the data message when a comparison is not found.

2. The data compression apparatus of claim 1 in which said timing control means includes:

counter means for generating consecutive counts in response to the generation of each of said first control signals, each count representing the position of a character in the data message;

and sequencing means responsive to a predetermined count generated by said counter means for outputting said timing control signals for processing the character being outputted by said outputting means, said sequencing means being logically constructed to stop outputting said timing control signals when responding to those counts of said counter means representing the position of known redundant characters of said data message.

3. The data compression apparatus of claim 2 which further includes fourth storage means enabled by said sequencing means for storing a second non-redundant character which varies with each second non-redundant character of each succeeding data message by a constant, and means responsive to the storage of said second non-redundant character for disabling said fourth storage means from storing a second non-redundant character of a subsequently-generated data message.

4. The data compression apparatus of claim 3 which further includes means for generating an end-of-record character in response to the output of a predetermined count from said counter means to said sequencer means, said end-of-record character being stored in said second storage unit to signify the end of the compressed data record.

5. In a data terminal device which outputs a plurality of digital messages each including a plurality of redundant and non-redundant data characters in which a character is considered redundant if the character is the same in succeeding data messages, a data compression apparatus for compressing each of said digital messages comprising:

means for serially outputting each character of the digital message;

means for generating a first control signal in response to the outputting of each character of the digital message;

counter means operated in response to the generation of each of said first control signals to output a predetermined count;

timing control means coupled to said counter means for outputting a plurality of second control signals in response to the outputting of each count of the counter means;

first storage means for storing a compressed data record;

table lookup means storing a plurality of first non-redundant characters together with an associated one of a plurality of start of compressed data record characters coupled to said outputting means, said timing control means and said first storage means for receiving a first non-redundant character from said outputting means when enabled by one of said second control signals, said table lookup means outputting one of a plurality of a start-of-record characters to said first storage means in accordance with the first non-redundant character received, said start-of-record characters indicating the start of the compressed data record in addition to the first non-redundant character received;

second storage means operated by one of said second control signals for storing a second non-redundant character of a digital message;

third storage means operated by one of said second control signals and coupled to said outputting means for storing a second non-redundant character of each succeeding digital message received from said outputting means;

compare means coupled to said second and third storage means for comparing the second non-redundant characters stored in said second and third storage means;

and first bistable means coupled to said compare means and operable in response to the finding of no comparison by said compare means for enabling said first and second storage means to store the second non-redundant character outputted from said outputting means.

6. The data compression apparatus of claim 5 which further includes second bistable means coupled to said compare means and operable in response to the finding of a comparison by said compare means for disabling said first and second storage means from storing the second non-redundant character outputted from said outputting means.

7. The data compression apparatus of claim 6 which further includes a third bistable means and a fourth storage means coupled to said outputting means and said timing control means and enabled by one of said second control signals for storing a third non-redundant character of a digital message outputted from said outputting means, said third non-redundant character varies with the third non-redundant character of each succeeding digital message by a constant and said third bistable means operable in response to the storage of the first occurring third non-redundant character in said fourth storage means for disabling said fourth storage means from storing a third non-redundant character of a succeeding digital message.

8. In a system for transmitting a plurality of data messages between a data terminal device and a central processor, said data messages including a plurality of characters representing redundant data in which a character is considered redundant if the character is the same in succeeding data messages and non-redundant data such as transaction data, merchandise-coded data and an operator ID data, an apparatus for compressing said data message comprising in combination:

means for serially outputting each data character of the data message;

means for generating a first control signal upon the outputting of each data character;

means for generating an identifying signal upon detecting the start of the first character in the data message;

binary counter means responsive to the generation of said identifying signal and said first control signal for generating a predetermined binary count;

means for generating a plurality of clock pulses;

timing control means operated in response to the generation of each of said binary counts and said clock pulses for outputting a plurality of second control signals, said timing control means include sequencing means for disabling said timing control means from generating said second control signals in response to the outputting of certain of said redundant data characters by said outputting means;

first storage means for storing a compression data message;

and table lookup means coupled to said outputting means, said first storage means and said timing control means for receiving a merchandise-coded data character when enabled by one of said second control signals, said table lookup means includes second storage means for storing a plurality of start-of-record characters each representing a merchandise-coded character, said table lookup means outputting to said first storage means one of said start-of-record characters in accordance with the merchandise coded character received wherein the start-of-record character stored in said first storage means represents the start of the compressed data message and the merchandise coded character outputted by said outputting means.

9. The data compression apparatus of claim 8 which further includes:

a third storage means coupled to said outputting means for storing the operator ID character of the previously-generated data message;

a fourth storage means coupled to said outputting means for storing the operator ID character received from said outputting means;

compare means coupled to said third and fourth storage means for comparing the operator ID characters stored in said third and fourth storage means;

and a first two-state logical device coupled to said compare means and said sequencing means and settable to a state in response to the finding of a no comparison by said compare means thereby enabling said timing control means to output a second control signal to said first and third storage means enabling the operator ID characters outputted by said outputting means to be stored in said first and third storage means.

10. The data compression apparatus of claim 9 which further includes a second two-state logical device coupled to said timing control means and settable in response to the finding of a compression by said compare means enabling said timing control means to output one of said second control signals to said first and third storage means disabling said first and third storage means from storing the operator ID character outputted by said outputting means.

11. The data compression apparatus of claim 10 which further includes a data register coupled to said outputting means and said timing control means and enabled by one of said second control signals generated by said timing control means in response to the outputting of a predetermined count from said binary counter means whereby the data register will store the transaction data outputted by said outputting means, said transaction data comprising one of a plurality of consecutive numbers identifying consecutive data messages, and a two-state logical device settable to a state upon the storing of the transaction data in said data register for disabling said data register from storing the transaction data of a subsequently-generated data message.

12. A method for use in an on-line data processing system in which data messages are transmitted from a data terminal device to a central processor of compressing redundant and non-redundant characters of a data message generated in a data terminal device upon the disabling of the central processor in which a character is considered redundant if the character is the same in succeeding data messages and said data terminal includes a storage table in which is stored a plurality of first non-redundant characters and an associated one of a plurality of different start-of-record characters comprising the steps of:

sensing the disabling of the central processor;

interrupting the data message transmitted from the terminal device upon sensing the disabling of the central processor;

storing all redundant and non-redundant characters of the first interrupted data message;

comparing all redundant characters of each data message with the redundant characters of a previous data message;

eliminating all redundant characters of the data message upon finding a match with the corresponding character of a previous data message;

comparing a first non-redundant character of the data message with the stored plurality of first non-redundant characters in said storage table;

generating one of a plurality of different start-of-record characters in accordance with the matching of said first non-redundant character;

storing in a first storage unit the start-of-record character generated as the first character of the compressed data record, the start-of-record character also representing the matched first non-redundant character;

storing in a second storage unit a second non-redundant character of the first data message received which varies with a corresponding second non-redundant character in each succeeding data message by a constant value in said first storage unit as a character in said compressed data record;

and disabling said second storage unit from receiving any subsequently received second non-redundant characters.