Method for validating communicated packets of data and for locating erroneous packets

• US 6,336,200 B1
• Filed: 05/19/1999
• Issued: 01/01/2002
• Est. Priority Date: 05/22/1998
• Status: Expired due to Term

• Current Assignee: KenCast Inc.
• Original Assignee: KenCast Inc.
• Inventors: Wolfgang, H. Lewis
• Primary Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US09/314,120
• Time in Patent Office: 958 Days
• Field of Search: 714/751, 714/752, 714/747, 714/757, 714/755, 714/761, 714/774, 714/776, 370/469, 370/473, 370/476, 704/202, 704/207, 704/228, 709/219, 709/236, 375/240
• US Class Current: 714/752
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/03 Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words

Abstract

A method is provided that verifies whether K original packets have been correctly reconstructed, and if not, locates an erroneously marked packet so that it may be removed from the reconstruction process. The reconstruction, verification and location process may then be repeated, if there are enough remaining packets, until the reconstructed original packets are deemed correct.

Claims

1. A method for validating that K packets of a file have been successfully received by a receiver out of N packets transmitted thereto by a transmitter, wherein the receiver deems each received packet as “

good”

or “

bad”

, said method comprising the steps of;

determining whether at least (K+1) packets have been deemed “

good”

by the receiver;

if so, selecting a (K+1)th packet out of the at least (K+1) “

good”

packets;

reconstructing K original packets and a (K+1)th′

packet from K of the non-selected “

good”

packets, the (K+1)th′

packet corresponding to the selected (K+1)th packet; and

determining whether the selected (K+1)th packet and the reconstructed (K+1)th′

packet are identical, whereby the K non-selected “

good”

packets, and thus the reconstructed K original packets, are validated if so.

2. A method according to claim 1, whereby said step of determining whether the selected (K+1)th packet and the reconstructed (K+1)th′

packet are identical is accomplished by computing a first error vector between those packets, whereby the K original packets are validated if the error vector is a zero vector.

3. A method according to claim 2, wherein the first error vector is the exclusive OR of the bytes of the selected (K+1)th packet and the respective bytes of the reconstructed (K+1)th′

packet.

4. A method according to claim 3, wherein at least (K+2) packets have been determined to be deemed “

good”

by the receiver, further comprising the step of attempting to locate an erroneous packet if the first error vector is not the zero vector.

5. A method according to claim 4, further comprising the steps of:

selecting a (K+2)th packet out of the at least (K+2) “

good”

packets, the (K+2)th packet being neither one of the K “

good”

packets used to reconstruct the K original packets nor the selected (K+1)th packet;

reconstructing a (K+2)th′

packet corresponding to the selected (K+2)th packet; and

computing a second error vector between the selected (K+2)th packet and the reconstructed (K+2)th′

packet, whereby the K non-selected “

good”

packets, and thus the reconstructed K original packets, are validated if the second error vector is the zero vector.

6. A method according to claim 5, wherein the second error vector is the exclusive OR of the bytes of the selected (K+2)th packet and the bytes of the reconstructed (K+2)th′

packet.

7. A method according to claim 6, wherein DIFFA is the first non-zero byte of the first error vector and DIFFB is the first non-zero byte of the second error vector, DIFFB being at the same vector position as DIFFA, further comprising the steps of:

forming a K×

2 matrix [C₁ C₂] by concatenating K×

1 column vectors C₁ and C₂ used in reconstructing the (K+1)th′ and

(K+2)th′

packets respectively;

determining the location “

n”

of an erroneous packet by searching the K×

2 matrix [C₁ C₂] for a multiple of [DIFFA DIFFB] and determining the row “

n”

at which that multiple occurs.

8. A method according to claim 7, wherein if more than one row of the K×

2 matrix [C₁ C₂] is a multiple of [DIFFA DIFFB], then the file is marked bad.

9. A method according to claim 7, wherein if no row “

n”

is found, and if at least (K+3) packets have been determined to be deemed “

good”

by the receiver, the location process is repeated using a (K+3)th packet selected out of the at least (K+3) “

good”

packets, the (K+3)th packet being neither one of the K “

good”

packets used to reconstruct the K original packets, nor the selected (K+1)th and (K+2)th packets.

10. A method according to claim 1, wherein the file comprises a plurality of shares of packets, and the K packets are the packets in any one of those shares.