Method and system for error-free data transfer
First Claim
Patent Images
1. 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×
n code generator matrix and the left k×
k submatrix of the k×
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.
4 Assignments
0 Petitions
Accused Products
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.
1577 Citations
23 Claims
-
1. 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×
n code generator matrix and the left k×
k submatrix of the k×
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. 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. 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. - View Dependent Claims (4)
-
-
5. 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 ath message vector being formed by taking the ath 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×
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 bth coded packet being formed by taking the bth 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-1 ; (10) forming j vectors z from the k packets received without error used in step (8), the cth vector z being formed by taking the cth symbol from each of the k packets Y in sequence; (11) matrix multiplying each of the j vectors z by the inverted matrix A-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 dth original packet being formed by taking the dth 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). - View Dependent Claims (6, 7)
-
-
8. 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×
n code generator matrix and the left k×
k submatrix of the k×
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. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. 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.
-
-
15. 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.
-
-
16. 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×
n code generator matrix and the left k×
k submatrix of the k×
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.
-
-
17. 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.
-
-
18. 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.
-
-
19. 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 ath message vector being formed by taking the ath 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×
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 bth coded packet being formed by taking the bth 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-1 ; (10) forming j vectors z from the k packets received without error used in step (8), the cth vector z being formed by taking the cth symbol from each of the k packets Y in sequence; (11) matrix multiplying each of the j vectors z by the inverted matrix A-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 dth original packet being formed by taking the dth 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).
-
-
20. 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 ath message vector being formed by taking the ath 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×
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 bth coded packet being formed by taking the bth 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'"'"'-- 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-1, forming j vectors z from the k packets received without error, the cth vector z being formed by taking the cth symbol from each of the k packets Y in sequence, (4) matrix multiplying each of the j vectors z by the inverted matrix A-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 dth original packet being formed by taking the dth 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.
-
-
21. 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 ath message vector being formed by taking the ath 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×
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 bth coded packet being formed by taking the bth 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-1 ; (12) forming j vectors z from the k packets having no error used in step (10), the cth vector z being formed by taking the cth symbol from each of the k packets Y in sequence; (13) matrix multiplying each of the j vectors z by the inverted matrix A-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 dth original packet being formed by taking the dth 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).
-
-
22. 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 ath message vector being formed by taking the ath 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×
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 bth coded packet being formed by taking the bth 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-1 ; (12) forming j vectors z from the k packets having no error used in step (10), the cth vector z being formed by taking the cth symbol from each of the k packets Y in sequence; (13) matrix multiplying each of the j vectors z by the inverted matrix A-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 dth original packet being formed by taking the dth 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).
-
-
23. 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 ath message vector being formed by taking the ath 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×
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 bth coded packet being formed by taking the bth 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-1, (4) forming j vectors z from the k packets having no error, the cth vector z being formed by taking the cth symbol from each of the k packets Y in sequence, (5) matrix multiplying each of the j vectors z by the inverted matrix A-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 dth original packet being formed by taking the dth 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.
-
Specification