Error correction on a mobile device

• US 6,209,111 B1
• Filed: 11/09/1998
• Issued: 03/27/2001
• Est. Priority Date: 11/09/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Deo, Vinay, Kadyk, Don, OʼLeary, Michael J.
• Primary Examiner(s): De Cady, Albert
• Assistant Examiner(s): Ton, David
• Application Number:
  US09/188,755
• Time in Patent Office: 869 Days
• Field of Search: 340/572, 714/797, 714/747, 709/206, 705/35
• US Class Current: 714/747
• CPC Class Codes: H04L 1/08 by repeating transmission, e.g. Verdan system H04L1/1858 and H04L1/189 take precedence

Abstract

First and second instances of a message are received over a wireless connection. It is determined whether the first and second instances of the message contain an error. If both instances contain an error, an error free instance of the message is reconstructed from the two erroneous instances by merging portions of the first and second instances.

Claims

1. A method of receiving a message over a wireless connection, comprising:

receiving at least first and second instances of a message;

determining whether one of the first and second instances contain an error;

if so, determining whether at least another of the first and second instances contain an error; and

when both the first and second instances contain an error, reconstructing the message by merging portions of the first and second instances to obtain a reconstructed instance, wherein merging includes creating a list of permutations identifying substantially all possible reconstructed messages that can be formed using portions of the first and second instances which match one another and different combinations of the portions of the first and second instance which do not match one another.

2. The method of claim 1 and further comprising:

when either of the first and second instances is an error free instance, using the error free instance to represent the message.

3. The method of claim 1 and further comprising:

after receiving the first instance and prior to determining whether one of the first and second instances contain an error, determining whether the second instance is to be sent, and, if not, using the first instance to represent the message.

4. The method of claim 3 wherein determining whether the second instance is to be sent comprises:

examining a tag in the first instance, the tag indicating whether the second instance is to be sent.

5. The method of claim 1 wherein receiving first and second instances comprises:

receiving the first instance;

waiting for a time out period to receive the second instance; and

if the second instance is not received within the time out period, using the first instance to represent the message.

6. The method of claim 5 wherein the step of determining whether the first instance contains an error is performed during the time out period.

7. The method of claim 6 and further comprising:

if the first instance is error free, stopping the timer.

8. The method of claim 7 and further comprising:

if the first instance is error free, discarding the second instance, when the second instance is received.

9. The method of claim 6 wherein, if the first instance contains an error, determining whether the second instance contains an error, and if not using the second instance to represent the message.

10. The method of claim 1 wherein merging the first and second instances comprises:

determining whether the first and second instances correspond to the message.

11. The method of claim 10 wherein determining whether the first and second instances correspond to the message comprises:

examining a sequence number in each instance.

12. The method of claim 1 wherein merging the first and second instances comprises:

determining a location of errors in one of the first and second instances to identify erroneous portions; and

merging portions of another of the first and second instances, corresponding to the erroneous portions, into the one of the first and second instances.

13. The method of claim 1 wherein creating a list of permutations comprises:

comparing the first and second instances to identify corresponding portions of the first and second instances which do not match one another.

14. The method of claim 13 wherein creating a list of permutations comprises:

forming each reconstructed message including portions of the first and second instances which match one another; and

inserting in each reconstructed message portions of the first and second instances which do not match one another such that the reconstructed message is not identical to either of the first and second instances, or to other reconstructed messages in the first of permutations.

15. The method of claim 14 wherein merging the first and second instances further comprises:

determining whether the reconstructed message contains an error and, if not, using the reconstructed message to represent the message.

16. The method of claim 15 wherein merging the first and second instances further comprises:

if the reconstructed message contains an error,

repeating the step of determining whether a next reconstructed message contains an error.

17. The method of claim 13 wherein merging the first and second instances further comprises:

determining whether any of the possible reconstructed messages is error free, and, if so, using the error free reconstructed message to represent the message.

18. The method of claim 17 wherein merging the first and second instances further comprises:

if all possible reconstructed messages contain an error, using the first instance to represent the message.

19. A mobile device, comprising

a wireless receiver configured to receiver configured to receive a first instance of a message and a second instance of the message;

and

a reconstruction component configured to determine whether the first and second instances contain errors and configured to reconstruct the message when both the first and second instances contain an error by merging portions of the first and second instances;

wherein the reconstruction component is configured to merge the first and second instances by comparing the first and second instances to identify corresponding portions of the first and second instances which do not match one another and to form a reconstructed message by including portions of the first and second instances which match one another and by inserting in the reconstructed message portions of the first and second instances which do not match one another such that the reconstructed message is not identical to either of the first and second instances; and

determining whether the reconstructed message contains an error and, if not, using the reconstructed message to represent the message, and if the reconstructed message contains an error, repeating the inserting step using different portions of the first and second messages which do not match one another and repeating the step of determining whether the reconstructed message contains an error.

20. The mobile device of claim 19 wherein the wireless receiver comprises a one-way communication device.

21. The mobile device of claim 20 wherein the wireless receiver comprises a pager.

22. The mobile device of claim 19 wherein the reconstruction component is configured such that when either of the first and second instances is an error free instance, the reconstruction component returns the error free instance.

23. The mobile device of claim 19 wherein the reconstruction component is configured such that, after receiving the first instance and prior to determining whether one of the first and second instances contain an error, the reconstruction component determines whether the second instance is to be sent, and, if not, the reconstruction component returns the first instance.

24. The mobile device of claim 19 wherein the reconstruction component is configured to receive the first instance, wait for a time out period to receive the second instance;

and if the second instance is not received within the time out period, return the first instance.

25. The mobile device of claim 24 wherein the reconstruction component is configured to determine whether the first instance contains an error during the time out period, and if the first instance is error free, stop the timer and discard the second instance, when the second instance is received.

26. The mobile device of claim 25 wherein the reconstruction component is configured to merge the first and second instances by determining whether the first and second instances correspond to the message.

27. The mobile device of claim 19 wherein the reconstruction component is configured to merge the first and second instances by determining a location of errors in one of the first and second instances to identify erroneous portions, and merging portions of another of the first and second instances, corresponding to the erroneous portions, into the one of the first and second instances.