Methods and apparatus employing FEC codes with permanent inactivation of symbols for encoding and decoding processes
First Claim
1. A method of electronically transmitting data via one or more transmitters capable of outputting an electronic signal, wherein the data to be transmitted is represented by an ordered set of source symbols and the data is transmitted as a sequence of encoded symbols representing at least a portion of the electronic signal, the method comprising:
- obtaining, in an electronically readable form, the ordered set of source symbols;
generating a set of intermediate symbols from the ordered set of source symbols, wherein the source symbols can be regenerated from the set of intermediate symbols;
designating sets of the intermediate symbols such that each intermediate symbol is designated as a member of one of the sets of intermediate symbols and there are at least a first set of intermediate symbols and a second set of intermediate symbols, and wherein each set of intermediate symbols has associated with it distinct encoding parameters and has as members at least one intermediate symbol; and
generating a plurality of encoded symbols, wherein an encoded symbol is generated from one or more of the intermediate symbols, wherein at least one encoded symbol is generated, directly or indirectly, from a plurality of intermediate symbols selected from a plurality of the sets of intermediate symbols.
1 Assignment
0 Petitions
Accused Products
Abstract
Encoding of a plurality of encoded symbols is provided wherein an encoded symbol is generated from a combination of a first symbol generated from a first set of intermediate symbols and a second symbol generated from a second set of intermediate symbols, each set having at least one different coding parameter, wherein the intermediate symbols are generated based on the set of source symbols. A method of decoding data is also provided, wherein a set of intermediate symbols is decoded from a set of received encoded symbols, the intermediate symbols organized into a first and second sets of symbols for decoding, wherein intermediate symbols in the second set are permanently inactivated for the purpose of scheduling the decoding process to recover the intermediate symbols from the encoded symbols, wherein at least some of the source symbols are recovered from the decoded set of intermediate symbols.
456 Citations
114 Claims
-
1. A method of electronically transmitting data via one or more transmitters capable of outputting an electronic signal, wherein the data to be transmitted is represented by an ordered set of source symbols and the data is transmitted as a sequence of encoded symbols representing at least a portion of the electronic signal, the method comprising:
-
obtaining, in an electronically readable form, the ordered set of source symbols; generating a set of intermediate symbols from the ordered set of source symbols, wherein the source symbols can be regenerated from the set of intermediate symbols; designating sets of the intermediate symbols such that each intermediate symbol is designated as a member of one of the sets of intermediate symbols and there are at least a first set of intermediate symbols and a second set of intermediate symbols, and wherein each set of intermediate symbols has associated with it distinct encoding parameters and has as members at least one intermediate symbol; and generating a plurality of encoded symbols, wherein an encoded symbol is generated from one or more of the intermediate symbols, wherein at least one encoded symbol is generated, directly or indirectly, from a plurality of intermediate symbols selected from a plurality of the sets of intermediate symbols. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A method of receiving data from a source, wherein the data is received at a destination over a packet communication channel, and wherein the data representable by a set of encoded symbols derived from an ordered set of source symbols representing the data sent from the source to the destination, the method comprising:
-
obtaining the set of received encoded symbols; decoding a set of intermediate symbols from the set of received encoded symbols; associating each of the intermediate symbols with a set of intermediate symbols, wherein the intermediate symbols are associated into at least two sets, and wherein one set is designated as a set of permanently inactive symbols for purposes of scheduling a decoding process to recover the intermediate symbols from the received encoded symbols; and recovering at least some of the source symbols of the ordered set of source symbols from the set of intermediate symbols according to the decoding process. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
37. A method for serving a file using a server coupled to a data network, wherein serving includes organizing data of the file into one or more blocks, generating one or more encoded symbols for a block based on the data of the block, and wherein at least one block is physically or logically organized into a plurality of sub-blocks and at least one encoded symbol is physically or logically organized into a plurality of sub-symbols, the method comprising:
-
partitioning an input file into an integer number of blocks, wherein each block includes at least one sub-block, and wherein each sub-block includes at least one source symbol; determining a value, WS, representing a maximum size for a sub-block based on a memory constraint; determining a value SS, wherein SS*AL represents a lower bound for sub-symbol size, in units of a preferred memory unit size, AL; determining which blocks of the integer number of blocks is to be organized into a plurality of sub-blocks, and for each such block, organizing the block into a plurality of sub-blocks having a size determined by the available space within packets for encoded symbols that are to be sent, a symbol size that is to be used within each sent packet, in a manner to ensure that a number of source symbols for source blocks is equal within a threshold and the number is equal to the number, Kt, of source symbols in the file and to ensure that the sub-symbol size of each sub-block is at most SS*AL and to ensure that the size of each sub-block is at most WS; generating encoded symbols from blocks, wherein sub-symbols are generated from sub-blocks such that each encoded symbol depends on data from one block; and outputting the generated encoded symbols.
-
-
38. A method for recovering a block of data at a receiver using a client coupled to a data network, wherein a block includes a grouping of one or more sub-blocks, the method comprising:
-
receiving a plurality of encoded symbols generated from the block, wherein each encoded symbol includes a plurality of sub-symbols generated from at least one sub-block using a common set of operations; determining a value, WS, representing a maximum size for a sub-block based on a memory constraint; determining a value SS, wherein SS*AL represents a lower bound for sub-symbol size, in units of a preferred memory unit size, AL; determining which blocks of the integer number of blocks organized into a plurality of sub-blocks, and for each such block, organizing the block into a plurality of sub-blocks having a size determined by a first parameter set by a sender representing available space within packets, a second parameter representing a symbol size used within each packet, the parameters being such that a number of source symbols for source blocks is equal within a threshold and the number is equal to the number, Kt, of source symbols in the file; decoding blocks from received encoded symbols, wherein sub-blocks are decoded from sub-symbols and the sub-blocks form blocks, wherein the sub-symbol size of each sub-block is at most SS*AL and the size of each sub-block is at most WS; and outputting the decoded blocks.
-
-
39. An apparatus for encoding data to be transmitted via one or more transmitters capable of outputting a signal, the apparatus comprising:
-
memory; and a processor; the memory and processor configured to perform operations comprising; obtaining an ordered set of source symbols; generating a set of intermediate symbols from the ordered set of source symbols, wherein the source symbols can be regenerated from the set of intermediate symbols; designating sets of the intermediate symbols such that each intermediate symbol is designated as a member of one of the sets of intermediate symbols and there are at least a first set of intermediate symbols and a second set of intermediate symbols, and wherein each set of intermediate symbols has associated with it distinct encoding parameters and has as members at least one intermediate symbol; and generating a plurality of encoded symbols, wherein an encoded symbol is generated from one or more of the intermediate symbols, wherein at least one encoded symbol is generated, directly or indirectly, from a plurality of intermediate symbols selected from a plurality of the sets of intermediate symbols. - View Dependent Claims (40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53)
-
-
54. An apparatus for decoding data a set of received encoded symbols, the set of received encoded symbols derived from an ordered set of source symbols, the apparatus comprising:
-
memory; and a processor; the memory and processor configured to perform operations comprising; obtaining the set of received encoded symbols; decoding a set of intermediate symbols from the set of received encoded symbols; associating each of the intermediate symbols with a set of intermediate symbols, wherein the intermediate symbols are associated into at least two sets, and wherein one set is designated as a set of permanently inactive symbols for purposes of scheduling a decoding process to recover the intermediate symbols from the received encoded symbols; and recovering at least some of the source symbols of the ordered set of source symbols from the set of intermediate symbols according to the decoding process. - View Dependent Claims (55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74)
-
-
75. An apparatus for serving a file using a server coupled to a data network, wherein serving includes organizing data of the file into one or more blocks, generating one or more encoded symbols for a block based on the data of the block, and wherein at least one block is physically or logically organized into a plurality of sub-blocks and at least one encoded symbol is physically or logically organized into a plurality of sub-symbols, the apparatus comprising:
-
memory; and a processor; the memory and processor configured to perform operations comprising; partitioning an input file into an integer number of blocks, wherein each block includes at least one sub-block, and wherein each sub-block includes at least one source symbol; determining a value, WS, representing a maximum size for a sub-block based on a memory constraint; determining a value SS, wherein SS*AL represents a lower bound for sub-symbol size, in units of a preferred memory unit size, AL; determining which blocks of the integer number of blocks is to be organized into a plurality of sub-blocks, and for each such block, organizing the block into a plurality of sub-blocks having a size determined by the available space within packets for encoded symbols that are to be sent, a symbol size that is to be used within each sent packet, in a manner to ensure that a number of source symbols for source blocks is equal within a threshold and the number is equal to the number, Kt, of source symbols in the file and to ensure that the sub-symbol size of each sub-block is at most SS*AL and to ensure that the size of each sub-block is at most WS; generating encoded symbols from blocks, wherein sub-symbols are generated from sub-blocks such that each encoded symbol depends on data from one block; and outputting the generated encoded symbols.
-
-
76. An apparatus for recovering a block of data at a receiver using a client coupled to a data network, wherein a block includes a grouping of one or more sub-blocks, the apparatus comprising:
-
memory; and a processor; the memory and processor configured to perform operations comprising; receiving a plurality of encoded symbols generated from the block, wherein each encoded symbol includes a plurality of sub-symbols generated from at least one sub-block using a common set of operations; determining a value, WS, representing a maximum size for a sub-block based on a memory constraint; determining a value SS, wherein SS*AL represents a lower bound for sub-symbol size, in units of a preferred memory unit size, AL; determining which blocks of the integer number of blocks organized into a plurality of sub-blocks, and for each such block, organizing the block into a plurality of sub-blocks having a size determined by a first parameter set by a sender representing available space within packets, a second parameter representing a symbol size used within each packet, the parameters being such that a number of source symbols for source blocks is equal within a threshold and the number is equal to the number, Kt, of source symbols in the file; decoding blocks from received encoded symbols, wherein sub-blocks are decoded from sub-symbols and the sub-blocks form blocks, wherein the sub-symbol size of each sub-block is at most SS*AL and the size of each sub-block is at most WS; and outputting the decoded blocks.
-
-
77. A non-transitory processor-readable storage medium having stored thereon processor-executable instructions configured to cause a processor of a computing device to perform operations for encoding data to be transmitted via one or more transmitters capable of outputting a signal, the operations comprising:
-
obtaining an ordered set of source symbols; generating a set of intermediate symbols from the ordered set of source symbols, wherein the source symbols can be regenerated from the set of intermediate symbols; designating sets of the intermediate symbols such that each intermediate symbol is designated as a member of one of the sets of intermediate symbols and there are at least a first set of intermediate symbols and a second set of intermediate symbols, and wherein each set of intermediate symbols has associated with it distinct encoding parameters and has as members at least one intermediate symbol; and generating a plurality of encoded symbols, wherein an encoded symbol is generated from one or more of the intermediate symbols, wherein at least one encoded symbol is generated, directly or indirectly, from a plurality of intermediate symbols selected from a plurality of the sets of intermediate symbols. - View Dependent Claims (78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91)
-
-
92. A non-transitory processor-readable storage medium having stored thereon processor-executable instructions configured to cause a processor of a computing device to perform operations decoding data a set of received encoded symbols, the set of received encoded symbols derived from an ordered set of source symbols, the operations comprising:
-
obtaining the set of received encoded symbols; decoding a set of intermediate symbols from the set of received encoded symbols; associating each of the intermediate symbols with a set of intermediate symbols, wherein the intermediate symbols are associated into at least two sets, and wherein one set is designated as a set of permanently inactive symbols for purposes of scheduling a decoding process to recover the intermediate symbols from the received encoded symbols; and recovering at least some of the source symbols of the ordered set of source symbols from the set of intermediate symbols according to the decoding process. - View Dependent Claims (93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112)
-
-
113. A non-transitory processor-readable storage medium having stored thereon processor-executable instructions configured to cause a processor of a computing device to perform operations for serving a file using a server coupled to a data network, wherein serving includes organizing data of the file into one or more blocks, generating one or more encoded symbols for a block based on the data of the block, and wherein at least one block is physically or logically organized into a plurality of sub-blocks and at least one encoded symbol is physically or logically organized into a plurality of sub-symbols, the operations comprising:
-
partitioning an input file into an integer number of blocks, wherein each block includes at least one sub-block, and wherein each sub-block includes at least one source symbol; determining a value, WS, representing a maximum size for a sub-block based on a memory constraint; determining a value SS, wherein SS*AL represents a lower bound for sub-symbol size, in units of a preferred memory unit size, AL; determining which blocks of the integer number of blocks is to be organized into a plurality of sub-blocks, and for each such block, organizing the block into a plurality of sub-blocks having a size determined by the available space within packets for encoded symbols that are to be sent, a symbol size that is to be used within each sent packet, in a manner to ensure that a number of source symbols for source blocks is equal within a threshold and the number is equal to the number, Kt, of source symbols in the file and to ensure that the sub-symbol size of each sub-block is at most SS*AL and to ensure that the size of each sub-block is at most WS; generating encoded symbols from blocks, wherein sub-symbols are generated from sub-blocks such that each encoded symbol depends on data from one block; and outputting the generated encoded symbols.
-
-
114. A non-transitory processor-readable storage medium having stored thereon processor-executable instructions configured to cause a processor of a computing device to perform operations for recovering a block of data at a receiver using a client coupled to a data network, wherein a block includes a grouping of one or more sub-blocks, the operations comprising:
-
receiving a plurality of encoded symbols generated from the block, wherein each encoded symbol includes a plurality of sub-symbols generated from at least one sub-block using a common set of operations; determining a value, WS, representing a maximum size for a sub-block based on a memory constraint; determining a value SS, wherein SS*AL represents a lower bound for sub-symbol size, in units of a preferred memory unit size, AL; determining which blocks of the integer number of blocks organized into a plurality of sub-blocks, and for each such block, organizing the block into a plurality of sub-blocks having a size determined by a first parameter set by a sender representing available space within packets, a second parameter representing a symbol size used within each packet, the parameters being such that a number of source symbols for source blocks is equal within a threshold and the number is equal to the number, Kt, of source symbols in the file; decoding blocks from received encoded symbols, wherein sub-blocks are decoded from sub-symbols and the sub-blocks form blocks, wherein the sub-symbol size of each sub-block is at most SS*AL and the size of each sub-block is at most WS; and outputting the decoded blocks.
-
Specification