FORWARD ERROR-CORRECTING (FEC) CODING AND STREAMING
First Claim
1. In a data decoder for decoding data from received symbols received over a channel from an encoder, wherein the received data can include erasures and include source symbols and repair symbols and wherein the decoder uses a generator matrix in decoding, any square submatrix of which is invertible, such that the decoder can perform decoding operations concurrently with the arrival of the source symbols and repair symbols, a method of decoding comprising:
- representing a system of equations in a decoder memory derived, at least in part, from the generator matrix;
substituting received source symbols into the system of equations as the source symbols are received before receiving all source symbols;
identifying, using decoder logic, repair equations to be used for solving the system of equations as repair symbols arrive;
calculating, using decoder logic, vector values for equations as source symbols arrive; and
converting the system of equations into an upper triangular form as repair symbols arrive at the decoder.
2 Assignments
0 Petitions
Accused Products
Abstract
In a data decoder for decoding data from received symbols received over a channel from an encoder, wherein the received data can include erasures and include source symbols and repair symbols and wherein the decoder uses in decoding a generator matrix, any square submatrix of which is invertible, such that the decoder can perform decoding operations concurrently with the arrival of the source symbols and repair symbols, a method of decoding comprising representing in decoder memory a system of equations derived, at least in part, from the generator matrix, substituting received source symbols into the system of equations as the source symbols are received before receiving all source symbols, identifying, using decoder logic, repair equations to be used for solving the system of equations as repair symbols arrive, calculating, using decoder logic, vector values for equations as source symbols arrive, and converting the system of equations into an upper triangular form as repair symbols arrive at the decoder. Novel methods can be used for interleaving and specifying encoding structure for a large class of FEC codes, scheduling the sending of packets and the like.
-
Citations
17 Claims
-
1. In a data decoder for decoding data from received symbols received over a channel from an encoder, wherein the received data can include erasures and include source symbols and repair symbols and wherein the decoder uses a generator matrix in decoding, any square submatrix of which is invertible, such that the decoder can perform decoding operations concurrently with the arrival of the source symbols and repair symbols, a method of decoding comprising:
-
representing a system of equations in a decoder memory derived, at least in part, from the generator matrix;
substituting received source symbols into the system of equations as the source symbols are received before receiving all source symbols;
identifying, using decoder logic, repair equations to be used for solving the system of equations as repair symbols arrive;
calculating, using decoder logic, vector values for equations as source symbols arrive; and
converting the system of equations into an upper triangular form as repair symbols arrive at the decoder. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. In a data encoder for encoding data to be sent over a channel, a method of generating encoded data comprising source symbols and repair symbols, the source symbols representing the data being encoded and the repair symbols usable to recover information about missing source symbols, and wherein the source symbols represent the data to be encoded as an ordered plurality of source symbols, the method comprising:
-
obtaining a generator matrix for a code wherein the generator matrix represents and encoding of the repair symbols from the source symbols;
reading in at least some of the source symbols;
including the at least some of the source symbols as encoded symbols in an encoded set in an order in the encoded set corresponding to an order of the source symbols in the ordered plurality of source symbols;
reordering the source symbols according to a set of one or more reordering rules to form a reordered set of source symbols;
applying the generator matrix to the reordered set of source symbols to form a set of repair symbols; and
outputting the encoded set as the encoded data and the set of repair symbols. - View Dependent Claims (12, 13, 14, 15, 16, 17)
-
Specification