Back to results
US 6,012,159 AGranted
Method and system for error-free data transfer
AssigneeKencast, Inc.
InventorsMichael Fischer, Sophia Paleologou
Life of this patent
Estimating the term…
Abstract
A method and system are provided for transferring data from a host computer to one or more subscriber computers, the data consisting of k original packets. The method includes the steps of encoding the k original packets to form n encoded packets, where n>k, transmitting the encoded packets from the host computer to the subscriber computers, receiving some of the transmitted packets, and decoding any combination of k correctly-received encoded packets to reconstruct the k original packets.
Claims23
A method for transferring data from a host computer to at least one subscriber computer, the data comprising a plurality of k original packets, where k is a positive integer, said method comprising the steps of:
- encoding the k original packets to form a plurality of n encoded packets, where n>k;
- transmitting the encoded packets from the host computer to the at least one subscriber computer;
- and
- decoding any combination of k correctly-received encoded packets to reconstruct the k original packets,
- wherein the original packets are encoded with a k.times.n code generator matrix and the left k.times.k submatrix of the k.times.n code generator matrix is the identity matrix, so that the first k encoded packets are the original k packets, and thus if the first k encoded packets are received correctly, the decoding step is not performed, and wherein n is recomputed for each transmission based on an estimate of the percentage of packets expected to be lost during that transmission.
2 more elements
A method for transferring data from a host computer to at least one subscriber computer, the data comprising a plurality of k original packets, where k is a positive integer, said method comprising the steps of:
- dividing the original k packets into a plurality of groups of 1 packets;
- separately encoding each group of 1 packets to form a plurality of n' encoded packets for each group, where n'>1, and wherein n' is recomputed for each transmission based on an estimate of the percentage of packets expected to be lost during that transmission;
- separately transmitting each group of encoded packets from the host computer to the at least one subscriber computer;
- receiving, for each transmitted group, at least some of the transmitted packets;
- separately decoding any combination of 1 correctly-received encoded packets for each group to reconstruct the 1 original packets of each group so as to form a plurality of decoded groups;
- reconstructing the file from the plurality of decoded groups.
3 more elements
A method for transferring data from a host computer to at least one subscriber computer, the data comprising a plurality of k original packets, where k is a positive integer, said method comprising the steps of:
- dividing the original k packets into a plurality of groups of 1 packets;
- separately encoding each group of 1 packets to form a plurality of n' encoded packets for each group, where n'>1;
- transmitting the encoded packets of all the groups in an interleaved fashion from the host computer to the at least one subscriber computer;
- receiving at least some of the transmitted packets within each group in a deinterleaved fashion;
- separately decoding each group by using any combination of 1 correctly-received packets of the group to reconstruct the 1 original packets of each group, so as to form a plurality of decoded groups;
- and
- reconstructing the data from the plurality of decoded groups.
4 more elements
A method for transferring data from a host computer to at least one subscriber computer, said method comprising the steps of:
- (1) dividing the data into k original packets X, each original packet comprising j symbols from a finite field F;
- (2) forming j message vectors x each of length k, the a.sup.th message vector being formed by taking the a.sup.th symbol from each of the k original packets X in sequence;
- (3) matrix multiplying each of the j message vectors x by a code generator matrix G on the right to form j codeword vectors y each of length n, the code generator matrix G being a k row.times.n column matrix defined over the finite field F, where n>k and any k columns out of the n columns are linearly independent;
- (4) forming n encoded packets Y, each encoded packet comprising j symbols, from the j codeword vectors y, the b.sup.th coded packet being formed by taking the b.sup.th symbol from each of the j codeword vectors y in sequence;
- (5) transmitting the encoded packets Y from the host computer to the at least one subscriber computer;
- (6) receiving Y' packets of the encoded packets Y by the at least one subscriber computer;
- (7) determining which and how many of the received packets Y' have no error;
- (8) if the number of received packets having no error is greater than or equal to k, forming a matrix A of k rows and k columns that comprises the columns from the code generator matrix G that correspond to k packets received without error;
- (9) inverting the matrix A to form an inverted matrix A.sup.-1 ;
- (10) forming j vectors z from the k packets received without error used in step (8), the c.sup.th vector z being formed by taking the c.sup.th symbol from each of the k packets Y in sequence;
- (11) matrix multiplying each of the j vectors z by the inverted matrix A.sup.-1 on the right to form the j message vectors x of step (2);
- (12) reconstructing the k original packets X from the j message vectors x of step (11), the d.sup.th original packet being formed by taking the d.sup.th symbol from each of the j message vectors x in sequence;
- and
- (13) reconstructing the original data of step (1) from the k original packets X of step (12).
11 more elements
A system for transferring data from a host computer to at least one subscriber computer, the data comprising a plurality of k original packets, where k is a positive integer, said system comprising:
- an encoder for encoding the k original packets to form a plurality of n encoded packets, where n>k;
- a transmitter for transmitting the encoded packets from the host computer to the at least one subscriber computer;
- a receiver for receiving at least some of the transmitted packets;
- and
- a decoder for decoding any combination of k correctly-received encoded packets to reconstruct the data, wherein the original packets are encoded with a k.times.n code generator matrix and the left k.times.k submatrix of the k.times.n code generator matrix is the identity matrix, so that the first k encoded packets are the original k packets, and thus if the first k encoded packets are received correctly by the receiver, no decoding is performed by the decoder, and wherein n is recomputed for each transmission based on an estimate of the percentage of packets expected to be lost during that transmission.
2 more elements
A system for transferring data from a host computer to at least one subscriber computer, the data comprising a plurality of k original packets, where k is a positive integer, said system comprising:
- dividing means for dividing the original k packets into a plurality of groups of 1 packets;
- an encoder for separately encoding each group of 1 packets to form a plurality of n' encoded packets for each group, where n'>1, and wherein n' is recomputed for each transmission based on an estimate of the percentage of packets expected to be lost during that transmission;
- a transmitter for separately transmitting each group of encoded packets from the host computer to the at least one subscriber computer;
- a receiver for receiving, for each transmitted group, at least some of the transmitted packets;
- a decoder for separately decoding any combination of 1 correctly-received encoded packets for each group to reconstruct the 1 original packets of each group so as to form a plurality of decoded groups;
- and
- reconstructing means for reconstructing the file from the plurality of decoded groups.
4 more elements
A system for transferring data from a host computer to at least one subscriber computer, the data comprising a plurality of k original packets, where k is a positive integer, said system comprising:
- dividing means for dividing the original k packets into a plurality of groups of 1 packets;
- an encoder for separately encoding each group of 1 packets to form a plurality of n' encoded packets for each group, where n'>1;
- a transmitter for transmitting the encoded packets of all the groups in an interleaved fashion from the host computer to the at least one subscriber computer;
- a receiver for receiving at least some of the transmitted packets within each group in a deinterleaved fashion;
- a decoder for separately decoding each group by using any combination of 1 correctly-received packets of the group to reconstruct the 1 original packets of each group, so as to form a plurality of decoded groups;
- and
- reconstructing means for reconstructing the data from the plurality of decoded groups.
4 more elements
A storage medium storing a computer readable program executable by a host computer to perform a method for transferring data from a host computer to at least one subscriber computer, the data comprising a plurality of k original packets, where k is a positive integer, said method comprising the steps of:
- encoding the k original packets to form a plurality of n encoded packets, where n>k;
- transmitting the encoded packets from the host computer to the at least one subscriber computer;
- and
- decoding any combination of k correctly-received encoded packets to reconstruct the k original packets,
- wherein the original packets are encoded with a k.times.n code generator matrix and the left k.times.k submatrix of the k.times.n code generator matrix is the identity matrix, so that the first k encoded packets are the original k packets, and thus if the first k encoded packets are received correctly, the decoding step is not performed, and wherein n is recomputed for each transmission based on an estimate of the percentage of packets expected to be lost during that transmission.
2 more elements
A storage medium storing a computer readable program executable by a host computer to perform a method for transferring data from a host computer to at least one subscriber computer, the data comprising a plurality of k original packets, where k is a positive integer, said method comprising the steps of:
- dividing the original k packets into a plurality of groups of 1 packets;
- separately encoding each group of 1 packets to form a plurality of n' encoded packets for each group, where n'>1, and wherein n' is recomputed for each transmission based on an estimate of the percentage of packets expected to be lost during that transmission;
- separately transmitting each group of encoded packets from the host computer to the at least one subscriber computer;
- receiving, for each transmitted group, at least some of the transmitted packets;
- separately decoding any combination of 1 correctly-received encoded packets for each group to reconstruct the 1 original packets of each group so as to form a plurality of decoded groups;
- and
- reconstructing the file from the plurality of decoded groups.
4 more elements
A storage medium storing a computer readable program executable by a host computer to perform a method for transferring data from a host computer to at least one subscriber computer, the data comprising a plurality of k original packets, where k is a positive integer, said method comprising the steps of:
- dividing the original k packets into a plurality of groups of 1 packets;
- separately encoding each group of 1 packets to form a plurality of n' encoded packets for each group, where n'>1;
- transmitting the encoded packets of all the groups in an interleaved fashion from the host computer to the at least one subscriber computer;
- receiving at least some of the transmitted packets within each group in a deinterleaved fashion;
- separately decoding each group by using any combination of 1 correctly-received packets of the group to reconstruct the 1 original packets of each group, so as to form a plurality of decoded groups;
- and
- reconstructing the data from the plurality of decoded groups.
4 more elements
A storage medium storing a computer readable program executable by a host computer to perform a method for transferring data from a host computer to at least one subscriber computer, said method comprising the steps of:
- (1) dividing the data into k original packets X, each original packet comprising j symbols from a finite field F;
- (2) forming j message vectors x each of length k, the a.sup.th message vector being formed by taking the a.sup.th symbol from each of the k original packets X in sequence;
- (3) matrix multiplying each of the j message vectors x by a code generator matrix G on the right to form j codeword vectors y each of length n, the code generator matrix G being a k row.times.n column matrix defined over the finite field F, where n>k and any k columns out of the n columns are linearly independent;
- (4) forming n encoded packets Y, each encoded packet comprising j symbols, from the j codeword vectors y, the b.sup.th coded packet being formed by taking the b.sup.th symbol from each of the j codeword vectors y in sequence;
- (5) transmitting the encoded packets Y from the host computer to the at least one subscriber computer;
- (6) receiving Y' packets of the encoded packets Y by the at least one subscriber computer;
- (7) determining which and how many of the received packets Y'.sub.-- have no error;
- (8) if the number of received packets having no error is greater than or equal to k, forming a matrix A of k rows and k columns that comprises the columns from the code generator matrix G that correspond to k packets received without error;
- (9) inverting the matrix A to form an inverted matrix A.sup.-1 ;
- (10) forming j vectors z from the k packets received without error used in step (8), the c.sup.th vector z being formed by taking the c.sup.th symbol from each of the k packets Y in sequence;
- (11) matrix multiplying each of the j vectors z by the inverted matrix A.sup.-1 on the right to form the j message vectors x of step (2);
- (12) reconstructing the k original packets X from the j message vectors x of step (11), the d.sup.th original packet being formed by taking the d.sup.th symbol from each of the j message vectors x in sequence;
- and
- (13) reconstructing the original data of step (1) from the k original packets X of step (12).
11 more elements
A system for transferring data from a host computer to at least one subscriber computer, comprising:
- an encoder for (1) dividing the data into k original packets X, each original packet comprising j symbols from a finite field F, (2) forming j message vectors x each of length k, the a.sup.th message vector being formed by taking the a.sup.th symbol from each of the k original packets X in sequence, (3) matrix multiplying each of the j message vectors x by a code generator matrix G on the right to form j codeword vectors y each of length n, the code generator matrix G being a k row.times.n column matrix defined over the finite field F, where n>k and any k columns out of the n columns are linearly independent and (4) forming n encoded packets Y, each encoded packet comprising j symbols, from the j codeword vectors y, the b.sup.th coded packet being formed by taking the b.sup.th symbol from each of the j codeword vectors y in sequence,
- a transmitter for transmitting the encoded packets Y from the host computer to the at least one subscriber computer;
- a receiver for receiving Y' packets of the encoded packets Y by the at least one subscriber computer;
- and
- a decoder for (1) determining which and how many of the received packets Y'.sub.-- have no error, (2) if the number of received packets having no error is greater than or equal to k, forming a matrix A of k rows and k columns that comprises the columns from the code generator matrix G that correspond to k packets received without error, (3) inverting the matrix A to form an inverted matrix A.sup.-1, forming j vectors z from the k packets received without error, the c.sup.th vector z being formed by taking the c.sup.th symbol from each of the k packets Y in sequence, (4) matrix multiplying each of the j vectors z by the inverted matrix A.sup.-1 on the right to form the j message vectors x, (5) reconstructing the k original packets X from the j message vectors x, the d.sup.th original packet being formed by taking the d.sup.th symbol from each of the j message vectors x in sequence, and (6) reconstructing the original data of step (1) from the k original packets X.
2 more elements
A method for transferring data from a host computer to at least one subscriber computer, said method comprising the steps of:
- (1) dividing the data into k original packets X, each original packet comprising j symbols from a finite field F;
- (2) forming j message vectors x each of length k, the a.sup.th message vector being formed by taking the a.sup.th symbol from each of the k original packets X in sequence;
- (3) matrix multiplying each of the j message vectors x by a code generator matrix G on the right to form j codeword vectors y each of length n, the code generator matrix G being a k row.times.n column matrix defined over the finite field F, where n>k and any k columns out of the n columns are linearly independent;
- (4) forming n encoded packets Y, each encoded packet comprising j symbols, from the j codeword vectors y, the b.sup.th coded packet being formed by taking the b.sup.th symbol from each of the j codeword vectors y in sequence;
- (5) performing bit-level error detection and correction (EDAC) encoding on the symbols within the coded packets Y;
- (6) transmitting the encoded packets Y from the host computer to the at least one subscriber computer;
- (7) receiving Y' packets by the at least one subscriber computer;
- (8) performing bit-level EDAC decoding on the symbols within the received packets Y';
- (9) determining which and how many of the bit-level decoded packets Y' have no error;
- (10) if the number of bit-level decoded packets having no error is greater than or equal to k, forming a matrix A of k rows and k columns that comprises the columns from the code generator matrix G that correspond to k bit-level decoded packets having no error;
- (11) inverting the matrix A to form an inverted matrix A.sup.-1 ;
- (12) forming j vectors z from the k packets having no error used in step (10), the c.sup.th vector z being formed by taking the c.sup.th symbol from each of the k packets Y in sequence;
- (13) matrix multiplying each of the j vectors z by the inverted matrix A.sup.-1 on the right to form the j message vectors x of step (2);
- (14) reconstructing the k original packets X from the j message vectors x of step (13), the d.sup.th original packet being formed by taking the d.sup.th symbol from each of the j message vectors x in sequence;
- and
- (15) reconstructing the original data of step (1) from the k original packets X of step (14).
13 more elements
A storage medium storing a computer readable program executable by a host computer to perform a method for transferring data from a host computer to at least one subscriber computer, said method comprising the steps of:
- (1) dividing the data into k original packets X, each original packet comprising j symbols from a finite field F;
- (2) forming j message vectors x each of length k, the a.sup.th message vector being formed by taking the a.sup.th symbol from each of the k original packets X in sequence;
- (3) matrix multiplying each of the j message vectors x by a code generator matrix G on the right to form j codeword vectors y each of length n, the code generator matrix G being a k row.times.n column matrix defined over the finite field F, where n>k and any k columns out of the n columns are linearly independent;
- (4) forming n encoded packets Y, each encoded packet comprising j symbols, from the j codeword vectors y, the b.sup.th coded packet being formed by taking the b.sup.th symbol from each of the j codeword vectors y in sequence;
- (5) performing bit-level error detection and correction (EDAC) encoding on the symbols within the coded packets Y;
- (6) transmitting the encoded packets Y from the host computer to the at least one subscriber computer;
- (7) receiving Y' packets by the at least one subscriber computer;
- (8) performing bit-level EDAC decoding on the symbols within the received packets Y';
- (9) determining which and how many of the bit-level decoded packets Y' have no error;
- (10) if the number of bit-level decoded packets having no error is greater than or equal to k, forming a matrix A of k rows and k columns that comprises the columns from the code generator matrix G that correspond to k bit-level decoded packets having no error;
- (11) inverting the matrix A to form an inverted matrix A.sup.-1 ;
- (12) forming j vectors z from the k packets having no error used in step (10), the c.sup.th vector z being formed by taking the c.sup.th symbol from each of the k packets Y in sequence;
- (13) matrix multiplying each of the j vectors z by the inverted matrix A.sup.-1 on the right to form the j message vectors x of step (2);
- (14) reconstructing the k original packets X from the j message vectors x of step (13), the d.sup.th original packet being formed by taking the d.sup.th symbol from each of the j message vectors x in sequence;
- and
- (15) reconstructing the original data of step (1) from the k original packets X of step (14).
13 more elements
A system for transferring data from a host computer to at least one subscriber computer, comprising:
- a packet encoder for (1) dividing the data into k original packets X, each original packet comprising j symbols from a finite field F, (2) forming j message vectors x each of length k, the a.sup.th message vector being formed by taking the a.sup.th symbol from each of the k original packets X in sequence, (3) matrix multiplying each of the j message vectors x by a code generator matrix G on the right to form j codeword vectors y each of length n, the code generator matrix G being a k row.times.n column matrix defined over the finite field F, where n>k and any k columns out of the n columns are linearly independent, (4) forming n encoded packets Y, each encoded packet comprising j symbols, from the j codeword vectors y, the b.sup.th coded packet being formed by taking the b.sup.th symbol from each of the j codeword vectors y in sequence;
- a bit-level encoder for performing bit-level error detection and correction (EDAC) encoding on the symbols within the coded packets Y;
- a transmitter for transmitting the encoded packets Y from the host computer to the at least one subscriber computer;
- a receiver for receiving Y' packets by the at least one subscriber computer;
- a bit-level decoder for performing bit-level EDAC decoding on the symbols within the received packets Y';
- and
- a packet decoder for (1) determining which and how many of the bit-level decoded packets Y' have no error, (2) if the number of bit-level decoded packets having no error is greater than or equal to k, forming a matrix A of k rows and k columns that comprises the columns from the code generator matrix G that correspond to k bit-level decoded packets having no error, (3) inverting the matrix A to form an inverted matrix A.sup.-1, (4) forming j vectors z from the k packets having no error, the c.sup.th vector z being formed by taking the c.sup.th symbol from each of the k packets Y in sequence, (5) matrix multiplying each of the j vectors z by the inverted matrix A.sup.-1 on the right to form the j message vectors x, (6) reconstructing the k original packets X from the j message vectors x, the d.sup.th original packet being formed by taking the d.sup.th symbol from each of the j message vectors x in sequence, and (7) reconstructing the original data of step (1) from the k original packets X.
4 more elements
Dependencies are inferred from the claim text.