United States Patent [19J
`Spiess
`
`I lllll llllllll Ill lllll lllll lllll lllll lllll 111111111111111111111111111111111
`US005889818A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,889,818
`*Mar. 30, 1999
`
`[54] ADAPTIVE DISPLAY REFRESH AND DATA
`COMPRESSION IN A RADIO FREQUENCY
`ENVIRONMENT
`
`[75]
`
`Inventor: Gary N. Spiess, Lisbon, Iowa
`
`[73] Assignee: Norand Corporation, Cedar Rapids,
`Iowa
`
`[ * l
`
`Notice:
`
`The term of this patent shall not extend
`beyond the expiration date of Pat. No.
`5,592,512.
`
`[21]
`
`Appl. No.: 536,814
`
`[22]
`
`Filed:
`
`Sep. 29, 1995
`
`Related U.S. Application Data
`
`[63]
`
`[51]
`[52]
`
`[58]
`
`Continuation-in-part of Ser. No. 270,239, Jul. 1, 1994, Pat.
`No. 5,592,512, which is a continuation-in-part of Ser. No.
`265,712, Jun. 24, 1994, abandoned.
`Int. Cl.6
`...................................................... H03M 7/30
`U.S. Cl. .............................. 375/240; 341/51; 341/55;
`341/87; 341/106
`Field of Search ..................................... 375/240, 259,
`375/377; 341/51, 55, 59, 63, 67, 87, 95,
`99, 106, 107; 358/426, 261.1, 261.2, 261.4;
`348/384, 400; 370/474, 476, 477
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,899,147
`4,926,482
`4,971,407
`5,016,009
`5,048,104
`5,051,745
`5,300,931
`
`2/1990 Schiavo et al. ... ... .... ... ... ... ... ..... 341/60
`5/1990 Frost et al. ................................ 381/31
`11/1990 Hoffman ... ... ... ... ... ... .... ... ... ... ... . 341/87
`5/1991 Whiting et al. ........................... 341/67
`9/1991 D' Aoust et al. .......................... 382/46
`9/1991 Katz .......................................... 341/51
`4/1994 Lindsay et al. ......................... 341/106
`
`Primary Examiner-Amanda Le
`
`[57]
`
`ABSTRACT
`
`An adaptive display refresh and data compression solution
`for use in an RF network environment is described, where a
`network controller and portable terminals maintain an adap(cid:173)
`tive history of commonly used past information in order that
`it may be repeated quickly and communication speeds can
`be increased. A network controller maintains a separate
`history for each of the terminals in the RF network, and
`transmits a coded reference for the activities that are con(cid:173)
`tained in the history, which is stored in the memory of both
`the controller and the portable terminal. Terminals and the
`controller additionally may negotiate to determine the data
`compression features which will be supported in communi(cid:173)
`cation between the two devices. Data is compressed accord(cid:173)
`ing to the present invention by utilizing a hybrid run length
`and sliding dictionary compression scheme. Data is pre(cid:173)
`compressed by a run length compressor, and is further
`compressed by a specialized sliding dictionary technique
`designed to minimize memory storage and transmission time
`requirements, resulting in an efficient data compression
`method requiring little additional storage.
`
`4,701,745 10/1987 Waqterworth .................... 340/347 DD
`
`20 Claims, 6 Drawing Sheets
`
`105
`
`( START )
`t
`
`IMPLEMENT RUN-LENGTH
`DATA COMPRESSION SCHEME
`ON INPUT DATA
`
`/ 106
`
`t
`
`IMPLEMENT SLIDING DICTIONARY
`SCHEME ON RUN-LENGTH
`COMPRESSED DATA
`
`/ 107
`
`t
`
`FORMAT DATA OUTPUT FROM
`SLIDING DICTIONARY SCHEME
`BY ADDING A BIT TO THE
`OUTPUT DATA INDICATING A
`CHARACTER OR A POINTER
`
`i
`
`ACCUMULATE BITS ADDED TO
`THE OUTPUT DATA INTO THE
`FIRST BYTE OF A SET OF
`BYTES OF DATA OUTPUT FROM
`THE SLIDING DICTIONARY SCHEME
`
`/ 108
`
`/ 109
`
`IPR2016-01710
`UNIFIED EX1010
`
`

`
`U.S. Patent
`
`Mar. 30, 1999
`
`Sheet 1of6
`
`5,889,818
`
`10
`CONTROLLER
`HISTORY FOR TERMINAL 1 HISTORY FOR TERMINAL 2
`
`2t02~ 2t0 2~
`2~ 2ZG 2t0 3t0
`22
`B 2~ 2t0 2ZG
`3t03B 2t0 3B
`
`HISTORY FOR TERMINAL 3 HISTORY FOR TERMINAL 4
`
`24
`c
`
`12,
`
`TERMINAL 1
`
`2t02EJ
`2tEJ2~
`
`ctS
`
`"D,,
`
`TERMINAL 2
`
`{ 14
`
`2t02~
`
`2l0~
`
`TERMINAL 4
`
`18 .
`
`2t02~
`
`2l03~
`
`16
`
`TERMINAL 3
`
`2f 1o12\8 !;;!
`~~
`3p r;t3\2~
`~· ~
`
`FIG.1
`
`

`
`U.S. Patent
`
`Mar. 30, 1999
`
`Sheet 2 of 6
`
`5,889,818
`
`40
`
`42
`
`TERMINAL
`POWERS UP
`
`CONTROLLER SENDS
`NEGOTIATE PACKET
`TO TERMINAL
`
`TERMINAL AND
`CONTROLLER ARE
`IN DATA
`COMMUNICATION MODE
`66
`
`FIG.2
`
`NO
`
`46
`
`TERMINAL SENDS
`NEGOTIATE PACKET;
`TERMINAL ANO
`CONTROLI.ER ENTER
`NEGOTIATION MODE
`
`48
`
`CONTROLLER SENDS
`PACKET TO TERMINAL
`
`52
`
`NO
`
`PACKET SENT BY
`CONTROLLER WAS
`A DATA PACKET
`
`56
`
`58
`
`60
`
`NEGOTIATIONS
`MAY BEGIN
`
`TERMINAL SENDS
`CONTROLI.ER A UST OF
`REQUESTED FEATURES
`
`CONTROLLER ANSWERS
`"WAS" OR "WON!
`TO EACH FEATURE
`
`TERMINAL INHIBITS
`TRANSMISSION UNTIL
`A NEGOTIATE PACKET
`IS RECEIVED
`
`54
`
`62
`
`NEGOTIATIONS
`CONTINUE UNTIL
`FEATURES ARE
`AGREED UPON
`
`

`
`U.S. Patent
`
`Mar. 30, 1999
`
`Sheet 3 of 6
`
`5,889,818
`
`80
`
`START
`
`82
`
`NEXT CHARACTER IS
`INPUT TO BE
`COMPRESSED
`
`86
`
`DEFAULT PREVIOUS
`CHARACTER PROVIDED
`BY A VARIABLE
`~=----i
`
`90
`
`YES
`
`DISCARD CHARACTER,
`ADD ONE TO
`REPETITION COUNT
`
`94
`
`OUTPUT NEXT
`CHARACTER
`
`98
`OUTPUT PREVIOUS
`CHARACTER AGAIN,
`OUTPUT NEXT
`CHARACTER
`
`104
`
`RESET
`REPETITION
`COUNT
`
`100
`
`102
`
`PREVIOUS REPETITION
`COUNT > 1
`
`OUTPUT A FLAG
`FOLLOWED BY
`REPETITION COUNT
`UINUS ONE AND NEXT
`CHARACTER
`
`FIG.3
`
`

`
`U.S. Patent
`
`Mar. 30, 1999
`
`Sheet 4 of 6
`
`5,889,818
`
`105
`
`( START
`
`IMPLEMENT RUN-LENGTH
`DATA COMPRESSION SCHEME
`ON INPUT DATA
`
`1,,..-106
`
`IMPLEMENT SLIDING DICTIONARY
`SCHEME ON RUN-LENGTH
`COMPRESSED DATA
`
`/ 107
`
`I
`
`FORMAT DATA OUTPUT FROM
`SLIDING DICTIONARY SCHEME
`BY ADDING A BIT TO THE
`OUTPUT DATA INDICATING A
`CHARACTER OR A POINTER
`
`108
`
`/
`
`~
`
`ACCUMULATE BITS ADDED TO
`THE OUTPUT DATA INTO THE
`FIRST BYTE OF A SET OF
`BYTES OF DATA OUTPUT FROM
`THE SLIDING DICTIONARY SCHEME
`
`v
`
`109
`
`FIG.3A
`
`

`
`U.S. Patent
`
`Mar. 30, 1999
`
`Sheet 5 of 6
`
`5,889,818
`
`(110
`
`(112
`
`• •
`
`•
`
`CHARACTER OR POINTER
`
`FIG.4
`
`SET
`
`( 120
`
`FLAG BYTE
`
`CHARACTER
`
`CHARACTER
`
`POINTER
`
`CHARACTER
`
`POINTER
`
`CHARACTER
`
`CHARACTER
`
`CHARACTER
`
`FIG.5
`
`122
`124
`
`126
`
`128
`130
`
`132
`134
`
`136
`
`138
`
`/
`
`/
`
`/
`
`/
`v
`v
`/
`
`/
`
`/
`
`

`
`U.S. Patent
`
`Mar. 30, 1999
`
`Sheet 6 of 6
`
`5,889,818
`
`v-1 50
`
`DATA
`INPUT
`
`154
`1 152
`___ _L _ _ -,
`
`FRAGMENT
`DATA INTO
`PACKETS
`
`:
`COMPRESS
`:
`DATA
`__ _ _ _ _ _ _J
`
`/"'" 156
`
`TRANSMIT
`DATA
`
`RECEIVE
`DATA
`
`v 158
`
`162
`1 160
`___ _L __ -,
`
`ASSEMBLE
`DATA PACKETS
`
`EXPAND
`DATA
`_ _ _ _ _ _ _ _J
`
`:
`l
`
`OUTPUT DATA v 164
`(E.G •. TO A
`DISPLAY)
`
`FIG.6
`
`

`
`5,889,818
`
`1
`ADAPTIVE DISPLAY REFRESH AND DATA
`COMPRESSION IN A RADIO FREQUENCY
`ENVIRONMENT
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation-in-part of U.S. appli(cid:173)
`cation Ser. No. 08/270,239, filed Jul. 1, 1994, now U.S. Pat.
`No. 5,592,512 issued Jan. 7, 1997 (Attorney Docket No.
`38076A), which in turn is a continuation-in-part of U.S.
`application Ser. No. 08/265,712, filed Jun. 24, 1994
`(Attorney Docket No. 38076), now abandoned.
`
`AUTHORIZATION PURSUANT TO THE
`COMMISSIONER'S NOTICE
`
`OF MAR. 20, 1987 (1077 OG 22)
`
`A portion of the disclosure of this patent document
`contains material which is subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent document or the patent
`disclosure, as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`TECHNICAL FIELD
`
`The present invention relates generally to adaptive data
`compression and more particularly to a method of updating
`display histories and determining data compression features
`to implement in a radio frequency communication system.
`The present invention also relates to a method for compress(cid:173)
`ing data in a radio frequency communication system
`designed to minimize storage requirements.
`
`BACKGROUND OF THE INVENTION
`
`35
`
`2
`display in memory, applications which run terminal emula(cid:173)
`tion must have coded versions of the emulation software in
`both the terminal and the controller. New terminal emula(cid:173)
`tions would need to be coded twice to obtain mirroring
`5 benefits. Also, it is extremely difficult to keep the function(cid:173)
`ality of a controller in sync with the functionality of one or
`more portable terminals. If these devices are not in sync, the
`mirroring solution does not work at all. Finally, even if the
`mirroring is working perfectly, there is no way to toggle
`10 between two or three display screens quickly, which is
`useful in many applications.
`Another possible solution is known as a "static dictio(cid:173)
`nary" approach. A network controller can be pre-loaded with
`certain display screens that may be utilized most often in
`15 portable terminals, and these screens can be forwarded to the
`terminals. Whenever a portable terminal requires a new
`display screen that is among the pre-loaded screens, the
`controller can transmit a reference, such as a number, which
`tells the terminal to use the appropriate screen, which is
`20 already in its memory. This approach allows a portable
`terminal to completely change from a current display to
`another display in a fraction of the time otherwise required.
`However, there are also some negative factors associated
`with the static dictionary solution. The main problem with
`25 this approach is that someone must decide initially which
`display screens are the most probable in the application
`environment, to pre-load into the controller. This pre(cid:173)
`loading must be done differently for each individual appli(cid:173)
`cation in order to attempt to pre-load the most frequently
`30 occurring screens for each application. Also, any time the
`pre-loaded screens need to be changed, the controller must
`be manually reprogrammed.
`Static dictionary solutions also provide only one set of
`display screens, known as a "history," in the controller's
`memory for all terminals. Modifying this solution to be
`adaptive would require the controller to transmit dictionary
`updates to every portable terminal, which would substan(cid:173)
`tially reduce the benefits of implementing the compression
`in the first place. Neither the mirroring approach, the static
`dictionary approach, nor a static dictionary approach modi(cid:173)
`fied to be adaptive completely satisfy the objectives of data
`compression in a radio frequency communication system.
`Another problem with data compression in a radio fre-
`45 quency communication system is the inflexibility of data
`compression features between different devices. There are
`multiple data compression techniques, and communication
`devices generally support only one or a limited number of
`them in combination. It is often the case that a device
`attempting communication will only execute data compres(cid:173)
`sion in its transmission if the receiving device supports the
`exact same data compression technique, or the same com(cid:173)
`bination of techniques.
`As a result, two differently configured devices will com-
`55 municate with no data compression at all, when it is possible
`that they may both support some of the same data compres(cid:173)
`sion features, but with a different combination.
`There have been many attempts to compress data so as to
`reduce communication times. Some of the resulting tech(cid:173)
`nologies are referred to as bit-oriented techniques, such as
`Huffman, Arithmetic, or Shannon-Pano encoding. With
`these schemes, the number of bits used to represent a code
`element vary in inverse proportion with the frequency of
`usage. The space character, for example, may only take 1 bit
`65 to encode, and the 'Q' character may take 23 bits to encode.
`These techniques are often used in conjunction with other
`methods to achieve significant compression ratios.
`
`40
`
`Radio frequency (RF) communication systems, particu(cid:173)
`larly in the context of communication involving portable,
`battery-powered terminals, have always had to deal with
`slow communication speeds. In an application environment,
`data is communicated between portable terminals, network
`controllers, and host computers, for example. In order for a
`system to truly be a "real-time" system, there cannot be any
`significant delay in operation when data communication
`takes place.
`In a typical RF system, it can take approximately two
`milliseconds to transmit a character of information. In order
`to fill even a relatively small portable screen with characters,
`it can take approximately one second. When fragmentation
`into packets and packet overhead time is taken into account, 50
`the time required to refresh a full screen of information is
`well over a second, which results in a noticeable delay for
`an end user. Such a delay has a negative effect on the user's
`time productivity, and also on the overall ease of use and
`comfort with the communication system.
`There have been a number of attempts to solve the
`problems created by insufficient communication speed. One
`such solution is known as "mirroring." This approach is
`implemented by having a network controller "mirror" a
`portable terminal's display image in its memory. When the 60
`display screen needs to be updated, the controller transmits
`only the changes from the current screen, rather than trans(cid:173)
`mitting the entire new screen information. This approach
`gives a portable terminal the ability to redisplay the same
`screen or a similar screen very quickly.
`There are many drawbacks to the mirroring solution. By
`requiring both a controller and a portable terminal to have a
`
`

`
`5,889,818
`
`25
`
`30
`
`3
`However, without hardware support, the receiving pro(cid:173)
`cessor has to inspect each bit of the compressed data to
`determine what it means. The data is looked up in a binary
`tree until a leaf has been found in the tree, and the repre(cid:173)
`sented code can be determined. In an adaptive compression 5
`scheme, the expansion process must also adjust the binary
`tree for every character decoded. All this data manipulation
`takes a significant amount of time and memory, which is not
`acceptable in a radio frequency "real-time" communication
`system.
`Another technique for compressing data is known as a
`sliding dictionary scheme. While the data is being
`compressed, a certain amount of past uncompressed data is
`searched for a match to what is about to be compressed. If
`no match is found, one character is output and the search for 15
`a match begins again with the next input character. When a
`match is found, a pointer to the previous uncompressed
`stored data and its length is output instead. During
`expansion, each character is inspected to determine if it
`represents a pointer. If not, the character is transferred to the 20
`output unchanged. If it is a pointer, it is used to point back
`into the uncompressed stored data, and the data is copied to
`the output.
`Sliding dictionary compression can be extremely slow
`when it is searching for a match. Special techniques are
`required to speed up the search for a match. Also, there are
`a large number of flags in sliding dictionary compressed
`data, and an entire 8-bit character is transmitted every time
`a flag is transmitted. This occupies significant space in a
`transmission which is not directly related to data, and is
`inefficient.
`Thus, there is a need for a display refresh and data
`compression solution that flexibly and efficiently minimizes
`the effects of slow transmission speeds on operation of a 35
`radio frequency communication system. There is also a need
`for a data compression solution that is fast, efficient, and
`requires a relatively small amount of memory.
`An object of the invention is to provide a display refresh
`and data compression solution that decreases operating
`delay for a user of a portable terminal in a radio frequency
`communication system.
`Another object of the invention is to provide a display
`refresh and data compression solution that decreases average
`screen update time without requiring terminal emulation 45
`coding in both a network controller and a portable terminal.
`Yet another object of the invention is to provide a display
`refresh and data compression solution that is adaptable to
`decrease average screen update time in a variety of diverse
`applications without manual reprogramming.
`A further object of the invention is to provide a display
`refresh and data compression solution that eliminates the
`need to transmit dictionary updates to all portable terminals.
`A still further object of the invention is to provide a data
`compression solution that allows communication devices to
`execute data compression even when they are not configured
`with all of the exact same compression features.
`An object of the invention is to provide a data compres(cid:173)
`sion solution that requires a minimal amount of memory in
`the place of expansion, such as a portable terminal.
`Another object of the invention is to provide a data
`compression solution that utilizes communication band(cid:173)
`width efficiently to directly communicate data information.
`Yet another object of the invention is to provide a data
`compression solution that speeds up the search for a match
`in a sliding dictionary compression scheme.
`
`4
`SUMMARY OF THE INVENTION
`The present invention solves many of the foregoing
`problems in the art through the implementation of an adap(cid:173)
`tive display refresh and data compression solution. A radio
`frequency communication system of the present invention
`may comprise multiple portable terminals, a network
`controller, and a host computer. Data is transmitted from
`portable terminals, though the network controller, to the host
`computer, and vice versa. The displays of the portable
`10 terminals are updated according to the information received
`by the controller from the host computer.
`In one embodiment of the present invention, the network
`controller stores a dictionary, or history, of the display
`strings most commonly used in each portable terminal. A
`display string is a sequence of characters that represents a
`portion of a display image or a command sequence that may,
`for example, be required to format a display or print image.
`The dictionary of strings allows the controller to transmit a
`short, reference code, such as a letter, to a portable terminal
`to indicate that the corresponding stored string is to be
`displayed or implemented on the terminal. By doing so, the
`amount of information which needs to be transmitted is
`significantly reduced. The dictionary of display strings also
`may change, according to the specific characteristics of the
`application environment in which the communication sys(cid:173)
`tem is being used. If a display string is being used more often
`than one of the strings stored in the dictionary, the more
`probable string is loaded into the controller's memory to
`replace the less probable string. In this way, the communi(cid:173)
`cation system can adapt to any of a range of diverse
`applications, while still providing efficient data compression
`and display refresh features.
`A separate history is maintained in the controller for each
`terminal in the system, which eliminates the need to send
`dictionary updates to every terminal in the network. When a
`new display string is to be kept in a terminal's history, that
`change can be transmitted to the terminal individually,
`affecting none of the other terminals. While such a compre-
`40 hensive list of terminal histories occupies more memory in
`the network controller, the memory taken up is no more than
`is commonly used in a "mirroring" approach, and yields
`substantial data compression benefits.
`It is also possible, according to the present invention, for
`the controller to remember not only strings of data, but also
`common command and print sequences executed by a
`portable terminal. Where an application requires repetitive
`actions to be performed by terminals, keeping such a com(cid:173)
`mand history can result in noteworthy time savings.
`Another embodiment of the present invention allows a
`portable terminal and a network controller to negotiate
`between themselves which data compression features to
`utilize. For example, a terminal may only use one data
`compression feature, while a network controller is config-
`55 ured to use a combination of three data compression fea(cid:173)
`tures. The terminal and the controller can negotiate and
`agree to use only the data compression feature supported by
`both of them, so that the maximum amount of data com(cid:173)
`pression is performed in their communication. The size of
`60 the history to be maintained and the method of saving old
`and new strings in the history may also be negotiated. The
`negotiation process may occur between the controller and
`any of the portable terminals, so that in fact the controller
`may communicate with different terminals using different
`65 data compression features.
`Data is compressed according to the present invention by
`implementing a hybrid compression scheme. Data to be
`
`50
`
`

`
`5
`transmitted first is compressed according to a run length
`compression technique. Repeated characters are detected
`and are reformatted by the run length technique as a flag
`followed by a count of the number of repetitions. Use of this
`"pre-compression" technique makes it unnecessary to spend 5
`processing time on long strings of repeated characters in a
`primary compression scheme.
`The present invention further compresses data via a
`sliding dictionary type of technique. If a character is occur(cid:173)
`ring for the first time in a data stream, then it can merely be 10
`transmitted as is, and is stored in a dynamic dictionary. If a
`character is occurring that has occurred before and is there(cid:173)
`fore stored in the dictionary, then it can be transmitted as a
`pointer to the location in the dictionary where it was
`originally stored. When the data is expanded, a pointer can 15
`be decoded by implementing a lookup, which saves addi(cid:173)
`tional decoding time. Also, there is no need to transmit
`dictionary updates for this sort of transmission, since the
`expansion of data creates the same dictionary created by
`compression.
`Flags must accompany the compressed data to indicate
`whether a particular element is a character or a pointer.
`Rather than transmitting a full flag whenever there is a
`pointer, an additional bit may preferably be added to each
`data element, indicating whether it is an uncompressed 25
`character or a pointer to the dictionary. Data may further be
`transmitted as a set of elements, where the first element is an
`accumulation of all of the additional flag bits indicating the
`nature of the following elements which make up the set.
`Data must be formatted and fragmented into packets for 30
`transmission in a wireless communication system. Accord(cid:173)
`ing to the present invention, data is also compressed in the
`fragmenting operation, which allows the data to be manipu(cid:173)
`lated all at once and thereby saves time and reduces the need
`for additional formatting. Similarly, expansion of data pref-
`erably takes place as part of the same step as reassembly of
`data packets in a receiving device.
`Other objects, advantages, and novel features of the
`present invention will become apparent from the following 40
`detailed description of the invention when considered in
`conjunction with the accompanying drawings.
`
`35
`
`20
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagrammatic illustration of a controller
`and portable terminals in an RF communication system
`utilizing display refresh and data compression according to
`the present invention.
`FIG. 2 is a flow diagram of the negotiation process
`executed between a controller and a portable terminal
`according to an embodiment of the present invention.
`FIG. 3 is a flow diagram of the run length compression
`technique utilized to pre-compress data according to the
`present invention.
`FIG. 3A is a flow diagram of the sequence of implemen(cid:173)
`tation of data compression schemes and formatting accord(cid:173)
`ing to an embodiment of the present invention.
`FIG. 4 is a diagrammatic illustration of a transmitted
`element including a flag bit according to the present inven(cid:173)
`tion.
`FIG. 5 is a diagrammatic illustration of a set of transmit(cid:173)
`ted elements including a flag byte according to the present
`invention.
`FIG. 6 is a block diagrammatic illustration of the path
`traveled by data in a wireless communication system and the
`location of data compression and expansion according to the
`present invention.
`
`5,889,818
`
`6
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`Referring now to the drawings, FIG. 1 is a block diagram
`of a network controller 10 and portable terminals 12, 14, 16,
`and 18 in an RF communication system. According to one
`embodiment of the present invention, the controller 10
`stores in its memory a display history for each of the
`portable terminals 12, 14, 16, and 18. For example, the
`history for terminal 12 consists of detailed display informa(cid:173)
`tion for a string A (20), a string B (22), a string C (24), and
`a string D (26). That display history is stored in both the
`controller 10 and the terminal 12.
`Similarly, the history for terminal 14 consists of display
`information for a string A (20), a string C (24), a string D
`(26), and a string F (30), which is all stored in controller 10
`and in terminal 14. The history for terminal 16 consists of
`display information for a string B (22), a string E (28), a
`string F (30), and a string G (32), which is all stored in
`controller 10 and in terminal 16. The history for terminal 18
`consists of display information for a string A (20), a string
`D (26), a string E (28), and a string G (32), which is all
`stored in controller 10 and in terminal 18.
`When the string to be displayed on a terminal corresponds
`to one of the display strings stored in the memory of the
`controller 10 for that particular terminal, the controller can
`transmit a short reference code, such as a letter, to indicate
`to the terminal that the appropriate string is in the terminal's
`memory. For example, if the next string to be displayed on
`terminal 18 was string D (26), which is stored in the history
`for terminal 18 in the controller 10 and in the terminal 18,
`the controller 10 would simply transmit a reference code
`"D" to the terminal 18 to indicate that the display informa(cid:173)
`tion was stored in the memory of terminal 18 under that
`reference code. As a result, the controller 10 does not have
`to send all of the display information over the airwaves, and
`the information can be accessed much more quickly by the
`terminal 18.
`The present invention also provides adaptive history
`capability. If, for example, portable terminal 16 reached the
`point where it was using a string C (24) more often than a
`string B (22) stored in its display history, the controller 10
`could replace the string B (22) in its stored history with the
`string C (24), and could transmit the display information for
`45 the string C (24) to the terminal 16 with instructions to store
`string C (24) in the history of terminal 16 in the space
`formerly occupied by string B (22). None of the other
`terminals 12, 14, or 18 would be affected by the history
`change. In this way each terminal can have an up to date list
`50 of the most commonly used display strings in its history.
`According to another embodiment of the present
`invention, the histories stored in the controller 10 for each
`terminal may be not only display information, but also
`command and print sequences for instance. A terminal could
`55 implement a commonly executed command sequence by
`looking it up in its history in response to a short instruction
`from the controller 10, thereby saving the time required to
`receive the sequence of commands or print sequences over
`a radio frequency link. The command sequences can be
`60 adaptively updated in a manner similar to the updating of
`display strings explained above.
`The actual display information in controller 10 is prefer(cid:173)
`ably stored in a common memory (not shown) of the
`controller 10, and the 'display strings' represented in con-
`65 troller 10 in FIG. 1 are merely reference codes which refer
`to the actual display or command sequence information for
`each string stored in the corresponding location of the
`
`

`
`5,889,818
`
`7
`memory in controller 10. Each history may preferably be
`implemented in the controller 10 by an array of memory
`lookup codes such as A through G in FIG. 1.
`While FIG. 1 shows the RF network with only four
`portable terminals, and shows each history consisting of 5
`only four items, it is understood that the present invention is
`applicable to networks and histories of any size, and FIG. 1
`serves not to limit, but to give an example of the present
`invention.
`In a preferred embodiment of the present invention, 10
`histories of display strings are not transmitted as a separate,
`independent function, but instead represent compressed or
`uncompressed data that each terminal needs to perform its
`functions, accompanied by proper formatting and instruc(cid:173)
`tions to be processed by the terminal to maintain a history 15
`according to the present invention.
`FIG. 2 is a flow diagram of a process which could be
`implemented by a portable terminal such as 12 (FIG. 1) and
`a network controller such as 10 (FIG. 1) to negotiate and
`establish data compression parameters in an RF communi- 20
`cation network, according to an exemplary embodiment of
`the present invention. A terminal initially powers up in box
`40. Upon detecting a new terminal in the network, the
`network controller transmits a negotiate packet to the ter(cid:173)
`minal in box 42. This negotiate packet may for example be 25
`an empty packet, or may be a specially configured packet. If
`the terminal desires to enter into negotiation mode, at
`decision box 44, it responds by transmitting a negotiation
`packet back to the controller at box 46. The terminal and
`controller are then both in negotiation mode. The terminal 30
`waits for the controller to transmit a packet at box 48. If the
`packet is a negotiation packet, then negotiations may begin
`at box 56. If the packet is a regular data packet, as shown in
`box 52, then the terminal processes the packet but inhibits
`transmission at box 54 until a negotiation packet is received. 35
`Transmission in response to the data packet does not occur
`until the terminal and controller have finished negotiations.
`After negotiations may begin, at box 56, the terminal
`transmits a list of requested data compression features to the
`controller at box 58. It is possible that the terminal and 40
`controller will support different data compression features,
`so they negotiate to determine which features are supported
`by both. The controller answers either "WILL" or "WON'T"
`to each of the features suggested by the terminal in box 60.
`The controller may then propose a list of further data 45
`compression features, or may otherwise continue negotia(cid:173)
`tions with the terminal generally in box 62. This will
`continue until a list of features is agreed upon and a "return
`to normal" message is agreed upon in box 64. The controller
`and terminal may transmit back and forth in the negotiation 50
`process before they can agree on a set of features and agree
`to return to normal data communication mode. The control-
`ler and terminal then return to data communication mode in
`box 66, which continues until the controller and terminal
`decide to enter negotiation mode at a later time. It is also
`conceivable that the terminal may initiate the process to
`enter negotiation mode rather than the controller, in another
`alternate embodiment of the present invention. The end
`result is for a terminal and controller to select the most
`efficient data compression feature combination supported by
`both devices, to optimize average communication speed in
`an RF network environment
`In a communication system specifically designed to allow
`real-time channel negotiation, messages can be "piggy(cid:173)
`backed" on the end of regular data packets without having
`to enter a special mode of operation. Data compression
`features can be negotiated in such a system as well.
`
`8
`FIG. 3 is a flow diagram of a possible run length data
`compression technique which could be implemented accord(cid:173)
`ing to an embodiment of the present invention. A data stream
`is input to the run length compressor which begins the
`compression process at start box 80. The next character to be
`compressed is input to the run length compressor at box 82.
`If the