Method and apparatus for adaptively companding data packets in a data communication system

I claim:

1. A method for adaptively compressing data packets for transmission between a first communication device and a second communication device, the method comprising the steps of:

a) generating, by the first communication device, a plurality of data packets;

b) selecting, by the first communication device, at least one of the plurality of data packets to produce at least one selected data packet, wherein a quantity of the at least one selected data packet is less than the plurality of data packets;

c) performing, by the first communication device, a first compression of each data packet in a first group of the plurality of data packets that includes the at least one selected data packet to produce compressed data packets;

d) transmitting, by the first communication device, the compressed data packets to the second communication device;

e) receiving, by the second communication device, the compressed data packets to produce received compressed data packets;

f) determining, by the second communication device, whether the received compressed data packets include the at least one selected data packet;

g) when the received compressed data packets include the at least one selected data packet, transmitting, by the second communication device, a response packet to the first communication device, the response packet indicating which selected data packets of the at least one selected data packet were received by the second communication device; and

h) upon receipt of the response packet, performing, by the first communication device, a second compression of each data packet in a second group of the plurality of data packets based on the response packet to produce adaptively compressed data packets.

2. The method of claim 1, wherein each of the plurality of data packets includes a selection flag, and wherein step (b) further comprises the step of setting the selection flag of each selected data packet to indicate that a particular data packet has been selected.

3. The method of claim 2, wherein step (f) comprises the step of determining whether the selection flag of at least one of the received compressed data packets is set.

4. The method of claim 1, wherein step (b) comprises the steps of:

b1) assigning each of the plurality of data packets a corresponding sequence number; and

b2) selecting, in sequence, at least two of the plurality of data packets to produce the at least one selected data packet.

5. The method of claim 4, wherein each of the plurality of data packets further includes an error correction flag, and wherein step (b) further comprises the steps of:

b3) assigning the error correction flag of the at least one selected data packet and each unselected data packet having a sequence number less than the corresponding sequence number of a first selected data packet of the at least one selected data packet to a first value to indicate a respective grouping of data packets; and

b4) assigning the error correction flag of each unselected data packet having a sequence number larger than the corresponding sequence number of a last selected data packet of the at least one selected data packet to a second value to distinguish the respective grouping from subsequent unselected packets;

the method further comprising the steps of:

i) determining, by the second communication device, whether a value of the error correction flag of each received compressed data packet is identical to an expected value of the error correction flag; and

j) when the received compressed data packets do not include the at least one selected data packet and the value of the error correction flag of a received compressed data packet is not identical to the expected value of the error correction flag, transmitting, by the second communication device, a second response packet to the first communication device, wherein the second response packet indicates that the at least one selected data packet was not received.

6. The method of claim 4, wherein step (g) further comprises the step of, when the received compressed data packets include a selected data packet having a sequence number lower than an expected sequence number, excluding any reference to the selected data packet having the sequence number lower than the expected sequence number in the response packet.

7. The method of claim 1, wherein step (c) comprises the steps of:

c1) comparing a first string of data in each data packet of the first group to a database of data entries; and

c2) when at least a portion of the first string of data is identical to a data entry in the database, replacing the at least a portion of the first string of data with a code associated with the data entry, the code comprising less bits than the at least a portion of the first string of data.

8. The method of claim 7, wherein step (h) comprises the steps

h1) upon receipt of the response packet, creating at least one additional data entry in the database based on which selected data packets were received by the second communication device;

h2) comparing a second string of data in each data packet of the second group to the database of data entries including the at least one additional data entry; and

h3) when at least a portion of the second string of data is identical to a data entry in the database, replacing the at least a portion of the second string of data with a code associated with the data entry, said code comprising less bits than the at least a portion of the second string of data.

9. The method of claim 1, further comprising the step of:

i) when the received compressed data packets do not include the at least one selected data packet, transmitting, by the second communication device, a second response packet to the first communication device, wherein the second response packet indicates that the at least one selected data packet was not received.

10. The method of claim 1, wherein step (h) comprises the steps of:

h1) upon receipt of the response packet, selecting, by the first communication device, at least one data packet of the second group of the plurality of data packets to produce at least one supplemental selected data packet; and

h2) performing the second compression of each data packet in the second group based on the response packet to produce the adaptively compressed data packets, wherein the second group includes the at least one supplemental selected data packet.

11. The method of claim 10, further comprising the steps of:

i) transmitting, by the first communication device, the adaptively compressed data packets to the second communication device;

j) receiving, by the second communication device, the adaptively compressed data packets to produce received adaptively compressed data packets;

k) determining, by the second communication device, whether the received adaptively compressed data packets include the at least one supplemental selected data packet;

l) when the received adaptively compressed data packets include the at least one supplemental selected data packet, transmitting, by the second communication device, a second response packet to the first communication device, the second response packet indicating which selected data packets of the at least one supplemental selected data packet were received by the second communication device; and

m) upon receipt of the second response packet, performing, by the first communication device, a third compression of each data packet in a third group of the plurality of data packets based on the second response packet to produce supplemental adaptively compressed data packets.

12. The method of claim 11, further comprising the step of:

n) repeating steps (h) through (m) until the plurality of data packets are transmitted.

13. A method for a first communication device to adaptively compress data packets for transmission to a second communication device, the method comprising the steps of:

a) generating a plurality of data packets;

b) selecting at least one of the plurality of data packets to produce at least one selected data packet, wherein a quantity of the at least one selected data packet is less than the plurality of data packets;

c) performing a first compression of each data packet in a first group of the plurality of data packets that includes the at least one selected data packet to produce compressed data packets;

d) transmitting the compressed data packets to the second communication device;

e) receiving a response packet from the second communication device, the response packet indicating which selected data packets of the at least one selected data packet were received by the second communication device; and

f) performing a second compression of each data packet in a second group of the plurality of data packets based on the response packet to produce adaptively compressed data packets.

14. The method of claim 13, wherein each of the plurality of data packets includes a selection flag, and wherein step (b) further comprises the step of setting the selection flag of each selected data packet to indicate that a particular data packet has been selected.

15. The method of claim 13, wherein step (b) comprises the steps of:

b1) assigning each of the plurality of data packets a corresponding sequence number; and

b2) selecting, in sequence, at least two of the plurality of data packets to produce the at least one selected data packet.

16. The method of claim 15, wherein each of the plurality of data packets further includes an error correction flag, and wherein step (b) further comprises the steps of:

b3) assigning the error correction flag of the at least one selected data packet and each unselected data packet having a sequence number less than the corresponding sequence number of a first selected data packet of the at least one selected data packet to a first value to indicate a respective grouping of data packets; and

b4) assigning the error correction flag of each unselected data packet having a sequence number larger than the corresponding sequence number of a last selected data packet of the at least one selected data packet to a second value to distinguish the respective grouping from subsequent unselected packets.

17. The method of claim 13, wherein step (c) comprises the steps of:

c1) comparing a first string of data in each data packet of the first group to a database of data entries; and

c2) when at least a portion of the first string of data is identical to a data entry in the database, replacing the at least a portion of the first suing of data with a code associated with the data entry, the code comprising less bits than the at least a portion of the first string of data.

18. The method of claim 17, wherein step (f) comprises the steps of:

f1) creating at least one additional data entry in the database based on which selected data packets were received by the second communication device;

f2) comparing a second string of data in each data packet of the second group to the database of data entries including the at least one additional data entry; and

f3) when at least a portion of the second string of data is identical to a data entry in the database, replacing the at least a portion of the second string of data with a code associated with the data entry, said code comprising less bits than the at least a portion of the second string of data.

19. A method for a first communication device to adaptively decompress data packets received from a second communication device, the method comprising the steps of:

a) receiving a plurality of compressed data packets from the second communication device to produce received compressed data packets;

b) determining whether the received compressed data packets include at least one data packet selected by the second communication device to produce at least one selected data packet;

c) when the received compressed data packets include the at least one selected data packet, storing the at least one selected data packet to produce at least one stored selected data packet and transmitting a response packet to the second communication device, the response packet indicating which selected data packets of the at least one selected data packet were received;

d) receiving a plurality of adaptively compressed data packets from the second communication device to produce received adaptively compressed data packets, the plurality of adaptively compressed data packets being compressed based on the response packet; and

e) performing an expansion of the received adaptively compressed data packets based on the at least one stored selected data packet.

20. The method of claim 19, wherein each of the plurality of compressed data packets includes a selection flag and wherein step (b) comprises the step of determining whether the selection flag of at least one of the received compressed data packets is set.

21. The method of claim 19, wherein each of the plurality of compressed data packets further includes a sequence number and an error correction flag, the error correction flag of the at least one selected data packet being assigned a first value to indicate a respective grouping of selected data packets, and the error correction flag of each unselected data packet having a sequence number larger than a sequence number of a last selected data packet being assigned a second value to distinguish the respective grouping from subsequent unselected data packets, the method further comprising the steps of:

f) determining whether a value of the error correction flag of each received compressed data packet is identical to an expected value of the error correction flag; and

g) when the received compressed data packets do not include the at least one selected data packet and the value of the error correction flag of a received compressed data packet is not identical to the expected value of the error correction flag, transmitting a second response packet to the second communication device, wherein the second response packet indicates that the at least one selected packet was not received.

22. The method of claim 19, wherein each of the plurality of compressed data packets includes a sequence number and wherein step (c) further comprises the step of, when the received compressed data packets include a selected data packet having a sequence number lower than an expected sequence number, excluding any reference in the response packet to the selected data packet having the sequence number lower than the expected sequence number.

23. The method of claim 22, wherein the expected sequence number comprises a sequence number subsequent to a sequence number of a last unselected data packet received prior to receiving the plurality of compressed data packets.

24. The method of claim 22, wherein the expected sequence number comprises a sequence number subsequent to a sequence number of a last data packet received prior to receiving the plurality of compressed data packets.

25. The method of claim 19, wherein the step of transmitting the response packet to the second communication device comprises the step of transmitting a bitmap to the second communication device, the bitmap indicating which selected data packets of the at least one selected data packet were received.

26. A communication device for transmitting adaptively compressed data packets, the communication device comprising:

a data packet generator;

a selector, coupled to the data packet generator, for selecting at least one of a plurality of data packets produced by the data packet generator to produce at least one selected data packet, wherein a quantity of the at least one selected data packet is less than the plurality of data packets;

a memory, coupled to the selector, for storing the at least one selected data packet;

a database, coupled to the memory, containing data entries that associate particular data strings to corresponding compressed code words, each compressed code word containing fewer bits than a corresponding particular data string;

a compressor, coupled to the selector and the database, for comparing portions of a group of the plurality of data packets, that includes the at least one selected data packet, to the data entries in the database and, when particular portions of the group match respective data entries, substituting corresponding compressed code words for those particular portions to produce compressed data packets;

a transmitter, coupled to the compressor, for transmitting the compressed data packets to a target communication device; and

a receiver, coupled to the database, for receiving a response packet from the target communication device, instructing the database to retrieve, from the memory, selected data packets of the at least one selected data packet identified in the response packet, and instructing the database to create additional data entries corresponding to the selected data packets, thereby allowing the database to be adaptively updated for subsequent compressed data packet transmissions.

27. A communication device for receiving adaptively compressed data packets, the communication device comprising:

a receiver that receives a plurality of compressed data packets from a sending communication device to produce received compressed data packets, the plurality of compressed data packets including at least one data packet selected by the sending communication device prior to transmission to produce at least one selected data packet, wherein a quantity of the at least one selected data packet is less than the plurality of compressed data packets;

a database containing data entries that associate compressed code words with corresponding expanded data strings, each of the expanded data strings including more bits than a corresponding compressed code word;

a selected packet determiner, coupled to the receiver and the database, that determines which of the received compressed data packets comprise the at least one selected data packet and that instructs the database to create an additional data entry for each selected data packet, thereby adaptively updating the database for use during a subsequent reception of compressed data packets; and

an expander, coupled to the receiver and the database, that compares portions of the received compressed data packets to the data entries in the database and, when particular portions of the received compressed data packets match respective data entries, that substitutes corresponding expanded data strings for those particular portions to reproduce original data packets from the received compressed data packets.

28. The communication device of claim 27, further comprising:

a response packet generator, coupled to the selected packet determiner, that produces a response packet indicating which selected data packets of the at least one selected data packet were received by the selected packet determiner; and

a transmitter, coupled to the response packet generator, that transmits the response packet to the sending communication device, thereby allowing the sending communication device to adaptively compress data packets prior to transmission based on which selected data packets of the at least one selected data packet were received by the selected packet determiner.

29. The communication device of claim 28, wherein the response packet generator comprises a bitmap generator that creates a bitmap representing which selected data packets of the at least one selected data packet were received by the selected packet determiner.

30. The communication device of claim 27, further comprising:

a memory, coupled to the expander and the database, that stores expanded representations of the received compressed data packets that comprise the at least one selected data packet and, upon request from the database, provides the expanded representations to the database to facilitate creation of additional data entries for the at least one selected data packet.

Description Submit all comments and votes

FIELD OF THE INVENTION

The present invention relates generally to data communication systems and, in particular, to a method and apparatus for adaptively compressing and expanding data packets in a data communication system.

BACKGROUND OF THE INVENTION

Packet data communication systems are known in both the wireless and wireline environments. In the wireless environment, the packet data system includes packet data routers, base site controllers, base sites, and wireless communication devices (e.g., mobile radios, portable radios, radiotelephones, or wireless data terminals). In the wireline environment, the packet data system includes switches and wireline communication devices (e.g., personal computers, computer servers, mainframes, laptop computers, personal communication devices, or custom data terminals). Packet data communications are also known to exist between wireless and wireline systems.

Data is transmitted over wireline systems using one of two primary formats: connectioned and connectionless. In a connectioned wireline system, a data communication is established during a connection set-up phase in which the participating wireline communication devices interchange set-up messages. Once the communication has been established, data transmission typically occurs between the two participating wireline communication devices when a transmitting device apportions its data into data packets and sends the data packets sequentially to the switch supporting the transmitting device. The switch then forwards the data to other switches (as necessary), while maintaining packet sequence, until the data eventually reaches the target communication device. The time delay associated with the transmission is related to the size (in bits) and the quantity of data packets.

In order to reduce the transmission delay, connectioned wireline systems typically use compression techniques to reduce the quantity of data necessary to complete a data transmission. Compression is performed by the transmitting device to reduce the number of bits necessary to represent a portion of the data. In a typical form known as dictionary compression, the transmitting device compares portions of the data stream to entries in a database and, when a match occurs, replaces the matching stream with a code word containing less bits than the matching stream. In this manner, the data stream is compressed using the code words in the database. Upon receipt of the compressed data, the target device expands the compressed data in a similar, but opposite, manner using an identical database to recover the original, uncompressed data.

Dictionary compression exists in two forms: static and dynamic. With static compression, both the sending device and the receiving device are prestored with identical compression/expansion databases to be used for all communications. This approach works well when the characteristics of the data (e.g., data type) remain constant for each communication and when relatively small quantities of data are transferred during each communication. By contrast, with dynamic compression, the sending and receiving devices update their databases based on the content of the data being transferred. Thus, dynamic compression facilitates every type of packet data communication because dynamic compression does not rely on a priori knowledge of the data.

To accomplish dynamic, or adaptive, compression, the sending device updates its compression database with information contained in each data packet of the communication, unless the existing entries in the database are sufficient to compress all the data in a particular packet. Similarly, the receiving device updates its expansion database with information contained in each data packet of the communication, unless the existing entries in the database are sufficient to expand all the data in a particular packet. Since each data packet is being used to update the compression/expansion databases, the sending device must be sure that the receiving device has received each data packet in sequence in order for the receiving device to properly update its database.

To insure that the receiving device receives each data packet, the sending and receiving devices typically employ a reliable link protocol, such as a high-level data link control (HDLC) protocol with Link Access Procedure M (LAPM) to perform error correction and recovery. As is known, reliable link protocols transmit data packets in groups, stopping and waiting between each group transmission until acknowledgment of receipt of the group by the receiving device. If the receiving device does not receive a group of packets, the sending device retransmits the lost group, thereby insuring that the receiving device receives each group and, therefore, can update its expansion database to coincide with the sending device's compression database. Since many wireline systems employ high speed data links, retransmission of lost data packets does not substantially impact overall transmission delay of the communication.

Similar to connectioned wireline systems, connectionless wireline systems, such as the Internet, utilize high reliability links; however, in contrast to connectioned systems, connectionless systems do not guarantee packet sequence during transmission. Thus, existing compression/expansion techniques are not readily adaptable to connectionless systems since the existing techniques require receipt of the transmitted packets at the receiving device in the same order as they were transmitted.

In contrast to wireline systems, wireless data systems--in particular narrowband wireless data systems--are lower reliability systems than wireline systems due to the higher probability of errors when communicating over a radio frequency (RF) channel than when communicating over a wireline transmission path. Thus, in wireless systems, there is a much greater chance that data packets will be lost or will arrive out-of-sequence at the receiving device. Therefore, the existing compression/expansion techniques used in connectioned wireline networks are not suitable for packet data transmissions in many wireless environments. In those wireless systems that may support existing compression/expansion techniques, the additional delays associated with the stop-and-wait high reliability approach result in timing-out of upper level protocol layers, such as the transmission control protocol (TCP), in the sending and receiving communication devices.

Therefore, a need exists for a method and apparatus for adaptively compressing and expanding data packets in a data communication system that facilitates use in wireless and connectionless wireline systems. Such a method and apparatus that also allowed continuous transmission of data packets, as opposed to a stop-and-wait approach, would be an improvement over the prior art.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 illustrates a radio communication system that may beneficially employ the present invention.

FIG. 2 illustrates a group of compressed selected and unselected data packets in accordance with the present invention.

FIG. 3 illustrates a response packet in accordance with the present invention.

FIG. 4 illustrates an exemplary adaptive compression/expansion database in accordance with the present invention.

FIG. 5 illustrates a block diagram depiction of a communication device that transmits adaptively compressed data packets in accordance with a preferred embodiment of the present invention.

FIG. 6 illustrates a block diagram depiction of a communication device that receives adaptively compressed data packets in accordance with a preferred embodiment of the present invention.

FIG. 7 illustrates a logic flow diagram of steps executed by a communication device to transmit adaptively compressed data packets in accordance with a preferred embodiment of the present invention.

FIG. 8 illustrates a logic flow diagram of steps executed by a communication device to receive adaptively compressed data packets in accordance with a preferred embodiment of the present invention.

DESCRIPTION OF A PREFERRED EMBODIMENT

Generally, the present invention encompasses a method and apparatus for adaptively companding (compressing and expanding) data packets in a data communication system. A first communication device generates a plurality of data packets and selects one or more, but not all, of the data packets. The first communication device then performs a compression of each data packet in a first group of data packets that includes the selected data packets. The first communication device transmits the compressed data packets to a second communication device. Upon receiving the compressed data packets, the second communication device determines whether the received compressed data packets include one or more of the data packets selected by the first communication device. When the received compressed data packets include one or more of the selected data packets, the second communication device transmits a response packet to the first communication device indicating which, if any, of the selected data packets were received.

Upon receipt of the response packet, the first communication device performs a compression of each data packet in a second group of data packets based on the response packet to produce adaptively compressed data packets and transmits the adaptively compressed data packets to the second communication device. Upon receipt of the adaptively compressed data packets and confirmation that the first communication device received the response packet, the second communication device expands the adaptively compressed data packets based on which selected data packets were received in the previous transmission. By adaptively compressing and expanding data packets in this manner, the present invention permits adaptive compression to be utilized over unreliable transmission links without requiring retransmission of packets that were lost due to the unreliability of the transmission link or that were received out of sequence (e.g., as in connectionless wireline networks) as is required to utilize prior art adaptive compression techniques.

The present invention can be more fully described with reference to FIGS. 1-8. FIG. 1 illustrates a radio communication 100 system that may beneficially employ the present invention. The radio communication system 100 preferably comprises a data communication system, although a combined voice and data communication system may also be used. The radio communication system 100 includes one or more base sites (one base site 101 shown), a base site controller (BSC), a mobile switching center (MSC), a packet data router 105, and a plurality of communication devices 107-109. The BSC and the MSC are depicted together as BSC/MSC block 103 because their independent functions are not critical to understanding the present invention. However, it is well understood that the BSC and the MSC might, and often do, comprise interconnected, yet separate, entities. The base site 101, the BSC/MSC 103, and the packet data router 105 are all well-known; thus, no further discussion will be presented except to facilitate an understanding of the present invention.

The communication devices 107-109 comprise wireless and/or wireline devices. As shown, communication device 107 comprises a portable data terminal 111 (e.g., a notebook computer) coupled to a wireless communication unit 113, such as a mobile or portable radio, a radiotelephone, or a two-way paging device. In an alternate embodiment, communication device 107 might only comprise the portable data terminal 111, wherein the portable data terminal 111 includes the means necessary to provide radio frequency (RF) transmission without necessitating an external wireless communication unit 113. Similar to wireless communication unit 113, communication device 109 is wireless and preferably comprises a mobile or portable radio, a radiotelephone, a two-way paging device, or a wireless data terminal. By contrast, communication device 108 is a wireline device, such as a computer terminal, a laptop computer, a custom data terminal (e.g., a vertical market device), or any other personal communicator that can transmit and receive packet data.

Referring to FIGS. 1-4, operation of the radio communication system 100 occurs substantially as follows in accordance with the present invention. When a communication device (e.g., 107) desires to transfer data to another communication device (e.g., 108 or 109), the communication device 107 requests a radio frequency (RF) communication channel 115 by transmitting a channel request to the BSC/MSC 103 via the base site 101. The channel request includes the identification of the target communication device (108 or 109). If a channel is available at the base site 101, the BSC/MSC 103 assigns the RF channel 115 to the requesting communication device 107. The RF channel 115 assigned depends on the communication platform used in the communication system 100. For example, in a frequency division multiplexed (FDM) system, the RF channel 115 comprises two radio frequencies, one for transmitting and one for receiving. Similarly, in a time division multiplexed (TDM) system, the RF channel 115 comprises two or more time slots, one or more time slots assigned on a transmit frequency and one or more time slots assigned on a receive frequency. Further, in a code division multiple access (CDMA) system, the RF channel 115 comprises a transmit code and a receive code used to transceive information over a common, wideband channel.

Upon receiving a channel grant from the BSC/MSC 103, the requesting communication device 107 generates a plurality of data packets within which to convey its data. For example, the requesting communication device 107 might generate 20 294-millisecond long data packets to transfer a data file of 20 kilobytes (assuming a link speed of 28 kilobits per second over the RF channel 115). Each data packet preferably includes a packet header that contains a selection flag, an error correction flag, and a sequence number. During the generation of the data packets, each data packet is assigned a respective sequence number.

Upon generating the data packets, the communication device 107 begins the transmission process. The communication device 107 first selects a predetermined number of the data packets (e.g., four), preferably in sequence, and identifies them as being selected by setting their selection flags (e.g., to logical 1). In addition, the communication device 107 assigns the error correction flag in each selected data packet and in each unselected data packet immediately preceding the selected data packets (i.e., those unselected packets having sequence numbers lower than the sequence numbers of the selected packets) to a first value (e.g., a logical 1 or a logical 0) to indicate a subgroup of the first group of packets. Similarly, the communication device 107 assigns the error correction flag in each unselected data packet of the first group following the selected data packets (i.e., those unselected packets having sequence numbers larger than the sequence numbers of the selected packets) to a second value (e.g., a logical 1 when the error correction flag of the selected data packets is a logical 0 or a logical 0 when the error correction flag of the selected data packets is a logical 1) to indicate the end of the subgroup containing selected data packets. This subgrouping allows the receiving communication device (e.g., 108) to determine whether all selected packets of a group have been lost during transmission, as is later described. The communication device 107 then stores the selected packets in a memory buffer for later use.

After the selection process, the communication device 107 compresses the first group of data packets. The first group includes selected data packets and unselected data packets. The compression is performed by comparing bit strings in each data packet to current entries in an adaptive compression database, such as the exemplary database 400 shown in FIG. 4. Assuming that the exemplary database 400 currently includes four data entries 402-405, the communication device 107 compares bit strings in the data packets (selected and unselected) of the first group to the expanded representations of the current data entries 402-405 and, when a match occurs, replaces the particular bit string with a corresponding code, or compressed representation. Each expanded representation provides a full binary representation of a character or character string; whereas, each compressed representation provides a more succinct representation of the character or character string. That is, each compressed representation contains less bits than the fully expanded representation. Thus, by compressing data prior to transmission, more data (i.e., more characters or character strings) can be throughput for a given transmission rate (e.g., kilobits per second). For example, if the character string "and the" is to be transmitted, the character string would require 24 bits if each character of the string is represented by four bits and the string is transmitted in its expanded form. However, by compressing commonly used character strings in the exemplary manner shown in FIG. 4, the character string "and the" can be transmitted using only four bits (i.e., using "11" for "and" and "10" for "the"), thereby freeing the previously used 20 bits for other compressed or expanded character string representations.

An exemplary first group of compressed selected data packets 202-205 and compressed unselected data packets 201, 206-207 resulting from the aforementioned selection and compression processes is shown in FIG. 2. Each data packet 201-207 includes a selection flag 208-214, an error correction flag 215-221, a sequence number 222-228, and compressed binary data. The compressed selected data packets comprise four contiguous data packets 202-205 having sequence numbers 223-226 two through five. The compressed selected data packets 202-205 are designated as being selected by having their selection flags 209-212 set to a logical 1. In an alternate embodiment, the compressed selected data packets 202-205 could be designated as being selected by having their selection flags 209-212 set to some other value (e.g., a logical 0).

The subgroup arranged to allow the receiving communication device 108 to identify when a complete set of compressed selected data packets has been lost consists of the compressed selected data packets 202-205 and the compressed unselected data packet 201 preceding the compressed selected data packets 202-205 and having sequence number 222 one. The subgroup is designated by having their error correction flags 215-219 set to logical zero, although any other value would suffice for identification purposes. The compressed unselected data packets 206-207 following the selected data packets 202-205 are not part of the aforementioned subgroup (as denoted by their error correction flags 220-221 having a different value than the error correction flags 215-219 of those packets 201-205 in the subgroup), but they effectively become part of the next subgroup, if such a next subgroup exists. That is, if another set of data packets is selected in the next group of data packets, the next set of selected data packets will have error correction flag values identical to the preceding compressed unselected data packets 206-207 of the previous group. For example, if the next group of compressed selected and unselected data packets were identical to the group shown in FIG. 2, the selected packets in the next group would have their error correction flags set to logical 1, as do the preceding unselected data packets 206-207. The discussion of subsequent compression and selection of data packets is provided below.

After compression of the first group of data packets 201-207, the transmitting device 107 formats the packets for transmission over the RF channel 115 and transmits the compressed packets 201-207 to the receiving communication device 108. The transmitting device 107 transmits the packets 201-207 to the base site 101, which processes the packets 201-207 in accordance with known techniques, and forwards the packets 201-207 to the BSC/MSC 103. The BSC/MSC 103 forwards the packets 201-207 to the packet data router 105 connecting the receiving device 108 to the RF portion of the system 100. The packet data router 105 then forwards the packets 201-207 to the receiving device 108.

Upon receiving the compressed data packets 201-207, the receiving device 108 determines whether any of the received packets 201-207 had been selected by the transmitting device 107. This determination comprises reading the selection flag 208-214 of each received packet 201-207 to determine whether it is set (i.e., has a value of logical 1). If a selection flag is set, then the respective received packet 201-207 was selected by the transmitting device 107. The determination also includes examining the error correction flag of each received packet 201-207 to determine an end of the set of selected packets. For example, if the receiving device 108 received all the transmitted packets 201-207 in the first group in the order shown in FIG. 2 (i.e., in sequential order), the receiving device would determine that packets 202-205 were selected because their selection flags 209-212 are set and that any selected packets must have preceded packet 206 because the error correction flag 220 of packet 206 is different than the error correction flags 215-219 of the preceding packets 201-205.

When the receiving device 108 determines that it has received selected packets, the receiving device 108 generates a response packet indicating which selected packets were received and transmits the response packet to the transmitting communication device 107. An exemplary response packet 301 is depicted in FIG. 3. The response packet 301 preferably includes a starting sequence number 303 and a bitmap 305. The starting sequence number 303 indicates the sequence number (e.g., 223) of the selected received packet (e.g., 202) having the lowest sequence number of the selected received packets 202-205. The bitmap 305 then indicates, in sequence, which of the selected packets were received. For example, if the selected and unselected packets 201-207 of FIG. 2 were received in order, the receiving device 108 would generate a response packet 301 upon receiving unselected packet 206 (i.e., after noticing a change in the value of the error correction flag) that contained a starting sequence number 303 of "2" and a bitmap