Method and system for error-free data transfer

Claim 7

A method according to claim 3, wherein the packets are transmitted in a maximally interleaved fashion.

Claim 10

A method according to claim 5, wherein the symbols within the coded packets Y are also error detection and correction encoded before transmission and decoded after reception.

Claim 11

A method according to claim 5, wherein the left k×k submatrix of the code generator matrix G is the identity matrix.

Claim 14

A system according to claim 8, wherein said encoder is a processor and the encoding is performed by a computer program stored in a storage medium accessed by said processor.

Claim 15

A system according to claim 9, wherein the processor is within the host computer.

Claim 16

A system according to claim 8, wherein said decoder is a processor and the decoding is performed by a computer program stored in a storage medium accessed by said processor.

Claim 17

A system according to claim 11, wherein the processor is within the at least one subscriber computer.

Claim 18

A system according to claim 8, wherein said transmitter is a satellite broadcast transmitter.

Claim 23

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.

Claim 24

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.

Claim 25

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.

Claim 26

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.

Claim 27

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.

Claim 28

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.

Claim 29

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 th message vector being formed by taking the a 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×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 th coded packet being formed by taking the b 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 -1 ; (10) forming j vectors z from the k packets received without error used in step (8), the c th vector z being formed by taking the c 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 -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 th original packet being formed by taking the d 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).

Claim 30

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 th message vector being formed by taking the a 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×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 th coded packet being formed by taking the b 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 -1 ; (10) forming j vectors z from the k packets received without error used in step (8), the c th vector z being formed by taking the c 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 -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 th original packet being formed by taking the d 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).

Claim 35

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 th message vector being formed by taking the a 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×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 th coded packet being formed by taking the b 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 -1 ; (12) forming j vectors z from the k packets having no error used in step (10), the c th vector z being formed by taking the c 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 -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 th original packet being formed by taking the d 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).

Claim 36

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 th message vector being formed by taking the a 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×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 th coded packet being formed by taking the b 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 -1 ; (12) forming j vectors z from the k packets having no error used in step (10), the c th vector z being formed by taking the c 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 -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 th original packet being formed by taking the d 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).