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

• US 5,701,302 A
• Filed: 10/25/1995
• Issued: 12/23/1997
• Est. Priority Date: 10/25/1995
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Geiger, Robert L.
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US08/547,747
• Time in Patent Office: 790 Days
• Field of Search: 370/465, 370/477, 370/521, 375/240, 375/241, 455/72, 341/51, 341/55, 341/106
• US Class Current: 370/521
• 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
• CPC Class Codes: H04L 1/1614 using bitmaps
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365

Abstract

A data communication system (100) employs a method and apparatus for adaptively companding (compressing and expanding) data packets therein. A first communication device (e.g., 107) generates a plurality of data packets (201-207) and selects one or more, but not all, of the data packets. The first device then performs a compression of each data packet in a first group of data packets that includes the selected data packets (202-205). The first device transmits the compressed data packets to a second communication device (e.g., 108). Upon receiving the compressed data packets, the second device determines whether the received compressed data packets include one or more of the data packets selected by the first device. When the received data packets include one or more of the selected data packets, the second device transmits a response packet (301) to the first device indicating which, if any, of the selected data packets were received. Upon receipt of the response packet, the first device performs an adaptive compression of each data packet in a second group of data packets based on the response packet and transmits the adaptively compressed data packets to the second device. The second device expands the adaptively compressed data packets based on which selected data packets were received in the previous transmission.

Claims

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.