Source: https://patents.google.com/patent/WO2004034589A9/en
Timestamp: 2018-07-20 05:01:43
Document Index: 522171085

Matched Legal Cases: ['Application no. 60', 'Application No. 10', 'Application No. 09', 'Application No. 09', 'Application No. 09', 'application no. 10', 'Application No. 09', 'Application No. 10', 'Application No. 10']

WO2004034589A9 - Systematic encoding and decoding of chain reaction codes - Google Patents
WO2004034589A9
WO2004034589A9 PCT/US2003/031108 US0331108W WO2004034589A9 WO 2004034589 A9 WO2004034589 A9 WO 2004034589A9 US 0331108 W US0331108 W US 0331108W WO 2004034589 A9 WO2004034589 A9 WO 2004034589A9
PCT/US2003/031108
WO2004034589A2 (en )
WO2004034589A3 (en )
M Amin Shokrollahi
Michael G Luby
A method of encoding data into a chain reaction code includes generating a set of input symbols from input data. Subsequently, one or more non-systematic output symbols is generated from the set of input symbols, each of the one or more nonsystematic output symbols being selected from an alphabet of non-systematic output symbols, and each non-systematic output symbol generated as a function of one or more of the input symbols. As a result of this encoding process, any subset of the set of input symbols is recoverable from (i) a predetermined number of non-systematic output symbols, or (ii) a combination of (a) input symbols which are not included in the subset of input symbols that are to be recovered, and (b) one or more of the non-systematic output symbols.
This application claims the benefit of US Provisional Application no. 60/319,597 entitled "Systematic Encoding and Decoding of Chain Reaction Codes," filed October 5, 2002, the contents of which are herein incorporated by reference in its entirety for all purposes.
Another consideration in selecting a code is the protocol used for transmission. In the case of the Internet, a packet protocol is used for data transport. That protocol is called the Internet Protocol or "IP" for short. When a file or other block of data is to be transmitted over an IP network, it is partitioned into equal size input symbols and input symbols are placed into consecutive packets. The "size" of an input symbol can be measured in bits, whether or not the input symbol is actually broken into a bit stream, where an input symbol has a size of M bits when the input symbol is selected from an alphabet of 2M symbols. In such a packet-based communication system, a packet oriented coding scheme might be suitable.
The Transport Control Protocol ("TCP") is a point-to-point packet control scheme in common use that has an acknowledgment mechanism. Using TCP, a sender transmits ordered packets and the recipient acknowledges receipt of each packet. If a packet is lost, no acknowledgment will be sent to the sender and the sender will resend the packet. With protocols such as TCP, the acknowledgment paradigm allows packets to be lost without total failure, since lost packets can just be retransmitted, either in response to a lack of acknowledgment or in response to an explicit request from the recipient.
One solution that has been proposed to solve the transmission problem is to avoid the use of an acknowledgment-based protocol, and instead use Forward Error-Correction (FEC) codes, such as Reed-Solomon codes, Tornado codes, or chain reaction codes, to increase reliability. The basic idea is to send output symbols generated from the content instead of just the input symbols that constitute the content. Traditional erasure correcting codes, such as Reed-Solomon or Tornado codes, generate a fixed number of output symbols for a fixed length content. For example, for K input symbols, N output symbols might be generated. These N output symbols may comprise the K original input symbols and N-K redundant symbols. If storage permits, then the server can compute the set of output symbols for each content only once and transmit the output symbols using a carousel protocol. One problem with some FEC codes is that they require excessive computing power or memory to operate. Another problem is that the number of output symbols must be determined in advance of the coding process. This can lead to inefficiencies if the loss rate of packets is overestimated, and can lead to failure if the loss rate of packets is underestimated.
"Chain Reaction Coding" as described in U.S. Patent No. 6,307,487 entitled "Information Additive Code Generator and Decoder for Communication Systems" (hereinafter "Luby I") and in U.S. Patent Application No. 10/032,156 entitled "Multistage Code Generator and Decoder for Communication Systems" (hereinafter "Raptor") represents a different form of forward error-correction that addresses the above issues. For chain reaction codes, the pool of possible output symbols that can be generated is orders of magnitude larger than the number of the input symbols, and a random output symbol from the pool of possibilities can be generated very quickly. For chain reaction codes, the output symbols can be generated on the fly on an as needed basis concurrent with the sending step. Chain reaction codes have the property that all input symbols of the content can be regenerated from any subset of a set of randomly generated output symbols slightly longer in length than the original content.
Other descriptions of various chain reaction coding systems can be found in documents such as U.S. Patent Application No. 09/668,452, filed September 22, 2000 and entitled "On Demand Encoding With a Window" and U.S. Patent Application No. 09/691,735, filed October 18, 2000 and entitled "Generating High Weight Output symbols Using a Basis." Some embodiments of a chain reaction coding system consist of an encoder, and a decoder. Data may be presented to the encoder in the form of a block, or a stream, and the encoder may generate output symbols from the block or the stream on the fly. In some embodiments, for example those described in Raptor, data may be pre-encoded offline using a static encoder, and the output symbols may be generated from the plurality of the original data symbols and the static output symbols.
In some embodiments of a chain reaction coding system the output symbols are generated as follows: for every output symbol a key is randomly generated. Based on the key, a weight W is computed from the weight table. Then a random subset of W source symbols is chosen. The output symbol will then be the XOR of these source symbols. These source symbols are called the neighbors or associates of the output symbol hereinafter. Various modifications and extensions of this basic scheme are possible and have been discussed in the above mentioned patents and patent applications.
Once an output symbol has been generated, it may be sent to the intended recipients along with its key, or an indication of how the key may be regenerated. In some embodiments, many output symbols may make up one transmission packet, as for example described in the U.S. Patent Application No. 09/792,364, filed February 22, 2001 and entitled "Scheduling of multiple files for serving on a server."
Figs.lA and IB illustrate exemplary embodiments of a non-systematic chain reaction encoder and decoder, respectively.
Fig. 7A illustrates an exemplary method for encoding data using systematic chain reaction codes in accordance with the present invention. Fig. 7B illustrates an exemplary method for decoding systematic chain reaction codes in accordance with the present invention.
For clarity and convenience, features and components' which are identified in earlier drawings retain their reference numerals in subsequent drawings. Detailed Description of Exemplary Embodiments
Figs. 1A and IB depict exemplary embodiments of a non-systematic chain reaction encoder 130 and decoder 170, respectively, as described in Luby I and Raptor. While not referred to as such in Luby I and Raptor, these embodiments are referred to herein as "non-systematic" to differentiate their architecture and operation from the systematic encoders and decoders presented below.
Referring now to Fig.lA, the non-systematic encoder 130 accepts as input symbols IS(0), IS(1), ...., and keys Io, Ii, ... generated by key generator 120. The number of input symbols may or may not be known in advance. In some embodiments, the non- systematic encoder 130 generates for each key I an output symbol. In Fig. 1A the output are denoted B(Io), B(Iι), ... corresponding to the keys Io, Ii, .... The number of generated output symbols is potentially limitless. Key generator 120 may have access to a random number generator from which it generates the keys. Alternatively, the keys I may be generated by some other mechanism. Encoder 130 may include static and dynamic encoders, as described for example in Raptor. It may have access to an additional key generator used to describe a static encoder.
Various embodiments of the chain reaction decoder 170 of Fig. IB are described in detail in Luby I and Raptor. In some embodiments the decoding process starts as soon as enough output symbols have been collected. In some embodiments the number of collected output symbols is slightly larger than the number of original input symbols. In other embodiments, the number of collected output symbols needed to start the decoding process can be significantly smaller than the number of original input symbols.
In some embodiments the decoding starts by identifying an output node Oi of degree one. Then the unique neighbor of Oi is declared recovered and is removed from the Decoding Graph, and the process is continued by identifying another output node O2 of degree one. For example, in the situation depicted in Fig. 3, Oi could be the output node denoted 330(a). Removal of its unique neighbor, 320(b), from the Decoding Graph, leads to another output node of degree one, namely 330(c). The process continues until all the source nodes are recovered, or until there are no output node of degree one left.
Fig. 4 is an illustration of the Decoding Matrix for the Decoding Graph of Fig. 3. As is known to those skilled in the art, the decoding problem can be phrased in terms of solving a system of equations given by the Decoding Matrix. If M denotes the Decoding Matrix corresponding to the Decoding, and if the vector of values of the output symbols is denoted by b, and if there are K source nodes, then the unknown source symbol values Xi, x2, ..., XK satisfy the matrix equation:
M • x = b, where x is the column vector (xi, x2, ... , K). The chain reaction decoding is successful if there is a permutation of rows and columns of M such that the resulting matrix is a lower triangular matrix, i.e., such that the values in the matrix above the main diagonal are zero. For example, by performing the permutation (3→2, 8→3, 2→5, 10→6, 5→7, 6→8, 7→9) on the rows, and the permutation (2→1, 5→2, 8→3, 9→4, 1→5, 3→7, 7→8, 4→9) on the columns of M a lower triangular matrix is produced. Stated in terms of matrices, this means that the chain reaction decoding algorithm produces permutation matrices P and Q such that P • M • Q is a lower triangular matrix. There are various methods for solving a system of linear equations, as is known to those of skill in the art. For example, it is possible to use the Gaussian elimination algorithm.
The matrix view of the decodmg is for illustrative purposes only and not restrictive. In particular, the actual operations of the decoder may differ substantially from the preceding discussions, as described in Luby I, Raptor, and the above mentioned patent applications.
To the Modified Decoding Graph corresponds a Modified Decoding Matrix consisting of zeros and ones, which has as many columns as there are source nodes, and as many rows as the aggregate value of output nodes and check nodes. Correspondingly, the Modified Decoding Matrix consists of two sets of rows, one corresponding to the output nodes, and one corresponding to the check nodes. Where there are L output nodes, C check nodes, and K source nodes, the Modified Decoding Matrix may be decomposed into a submatrix M0 consisting of L rows and K columns, and a matrix Mc consisting of C rows and K columns. If i, ..., XK denote the unknown values of the source symbols, and bi, ... ,bL denote the known values of the received output symbols, the task of the decoder may be to solve the system of equations given by M0 • x = b, and Mc • x = 0. The combined system of equations would be the one given in Fig. 6.
In some embodiments of a chain reaction decoder a different decoder, called an Inactivation Decoder, may be used. This Decoder is described in greater detail in the commonly assigned co-pending US patent application no. 10/459,370, entitled "Systems and Process for Decoding a Chain Reaction Code through Inactivation," herein incorporated by reference, and referred to as the "Inactivation Decoder." II. Systematic Chain Reaction Encoder & Decoder and Methods of Operation
Fig. 7A illustrates an exemplary method for encoding data using systematic chain reaction codes in accordance with the present invention. As used herein, the term "output symbol(s)" refers to a chain reaction code, examples of which are described in Luby I and Raptor. Systematic and non-systematic output symbols are, accordingly, specific types of chain reaction codes, a systematic output symbol comprising a transmitted input symbol, and a non-systematic output symbol comprising a output symbols which is a function of one or more input symbols.
Next, one or more non-systematic output symbols are generated from the input symbols. In a particular embodiment of that process, intermediate input symbols are initially generated from the input symbols (704). Subsequently, one or more non- systematic output symbols are generated from the intermediate input symbols (706). In alternative embodiments under the invention, the process of 706 may be omitted and the non-systematic output symbols are generated from the input symbols. Each of these processes are illustrated in greater detail below.
The method continues at 716, where one or more of the input symbols which were not acquired, are recovered. In a specific embodiment of this process, the missing input symbols may be recovered either from the non-systematic output symbols, or from a combination of non-systematic output symbols and the acquired input symbols. The recovery process at 716 may be used to recover one, several, or all of the missing input symbols. Once the desired number of missing input symbols is recovered, they may be added to the acquired input symbols to re-form the original set of input symbols, and accordingly, a copy of the original data.
Fig. 7C is a block diagram of an exemplary communications system 700 that uses systematic coding and decoding in accordance with one embodiment of the present invention. In the communication system 700, an input file 721, or an input stream 725, is provided to an input symbol generator 726. Input symbol generator 726 generates a sequence of one or more input symbols (IS(0), IS(1), IS(2), ...) from the input file or stream, with each input symbol having a value and a position (denoted in Fig. 7 as a parenthesized integer). As explained above, the possible values for input symbols, i.e., its alphabet, is typically an alphabet of 2M symbols, so that each input symbol codes for M bits of the input file. The value of M is generally determined by the use of communication system 700, but a general purpose system might include a symbol size input for input symbol generator 726 so that M can be varied from use to use. The output of input symbol generator 726 is provided to a systematic encoder 728.
The non-systematic key generator 727 generates keys Io, Ii, I2, ... corresponding to the input symbols provided to the encoder 728, the non-systematic keys being used to compute the values of the non-systematic output symbols B(Io), B(Iι), B(I2), ... output from the encoder 728. Each non-systematic key Io, Ii, h, -is generated so that a large fraction of the keys for the same input file are unique. In one embodiment, the non- systematic key generator 727 comprises the key regenerator 120 illustrated in Fig. 1A above and described in Luby I and Raptor, although in other embodiments another type of device operable to generate non-systematic keys may be used.
Systematic key generator 730 generates systematic keys Co, , C2, ... corresponding to the input symbols provided to the encoder 728, these keys being used to recover one or more of the input symbols not received, as will be further described below. It may use random numbers generated by random number generator 735 to generate the keys. The generation of the systematic keys will be subsequently described in greater detail. The outputs of non-systematic key generator 727 and the systematic key generator 730 are provided to encoder 728. From each non-systematic key I provided by the non-systematic key generator 727, encoder 728 generates a non-systematic output symbol, with a value B(I), from the input symbols provided by the input symbol generator. The non-systematic output symbol generated may be that as described in Luby I (single stage encoding/decoding) or the output symbol described in Raptor (multiple stage encoding/ decoding). The operation of an exemplary systematic encoder 728 will be described in more detail below. The value of each output symbol is generated based on its key, and on some function of one or more of the input symbols.
Systematic encoder 728 forwards the input symbols IS(0), IS(1), ... together with the systematic keys Co, , ... , Cκ-ι, or an indication on how to regenerate the systematic keys to transmit module 740. When transmitted, the symbols IS(0), IS(1), ... are herein referred to as "systematic output symbols". Systematic encoder 728 may create a copy of the input symbols for the generation of further output symbols before forwarding the input symbols to the transmit module.
Systematic encoder 728 also provides the non-systematic output symbols B(Io), B(Iτ), B(I2), ... to transmit module 740. Transmit module 740 is also provided the non- systematic keys (Io, Ii, I2, ...) for each such output symbol from the non-systematic key generator 727. Transmit module 740 transmits the systematic and non-systematic output symbols, and depending on the keying method used, transmit module 740 might also transmit some data about the keys of the transmitted output symbols, over a channel 745 to a receive module 750. Channel 745 is assumed to be an erasure channel, but that is not a requirement for proper operation of communication system 700. Modules 740, 745 and 750 can be any suitable hardware components, software components, physical media, or any combination thereof, so long as transmit module 740 is adapted to transmit output symbols and any needed data about their keys to channel 745 and receive module 750 is adapted to receive symbols and potentially some data about their keys from channel 745. The value of K, if used to determine the associates, can be sent over channel 745, or it may be set ahead of time by agreement of encoder 728 and decoder 755.
Receive module 750 receives the non-systematic and/or systematic output symbols from the channel 745 which it supplies to a decoder 755. Data corresponding to the keys of the received output symbols are provided to the non-systematic key regenerator 760, and the systematic key regenerator 780. In the illustrated embodiment of Fig.7, a set of systematic output symbols denoted by IS(x), IS(y), ...,IS(z) is received along with a set of non-systematic output symbols B(Ia), B(Ib), B(IC), ... In alternative embodiments, the receive module 750 may receive systematic output symbols exclusively, or a combination of systematic and non-systematic output symbols.
The non-systematic key regenerator 760 regenerates the non-systematic keys for the received non-systematic output symbols and provides these keys to the systematic decoder 755. In one embodiment, the non-systematic key regenerator 760 comprises the key regenerator 160 illustrated in Fig. IB above and described in Luby I and Raptor, although in other embodiments another type of device operable to regenerate non- systematic keys may be used. Systematic key regenerator 180 regenerates the systematic keys Co, Ci, ... and provides them to the systematic decoder 755. The systematic key regenerator 780 may have access to some shared information with the systematic key generator 730 which facilitates the regeneration of the systematic keys. Alternatively, systematic key regenerator 780 may regenerate the keys based on additional information transmitted through channel 745. In some embodiments, systematic key regenerator 780 may have access to the same random number generator 735 which may be used to generate the systematic keys. This can be in the form of access to the same physical device if the random numbers are generated on such device, or in the form of access to the same algorithm for the generation of random numbers to achieve identical behavior.
Decoder 755 uses the non-systematic keys provided by non-systematic key regenerator 760 and systematic key generator 780 together with the corresponding output symbols, to recover the input symbols (again IS(0), IS(1), IS(2), ...). The recovered input symbols are forwarded to the input file reassembler 765. Systematic decoder 755 may forward the received systematic output symbols IS(x), IS(y), ... , IS(z) directly to the input file reassembler 765, before recovering the remaining input symbols. In particular, if all input symbols are received, the decoder may choose to just forward the received data to input file reassembler without further computation. Input file reassembler 765 generates a copy 770 of input file 721 or input stream 725.
In the following the operations of the systematic encoder 728 arid decoder 755 will be described in greater detail. In some embodiments of the present invention these units may use chain reaction encoding and decoding, as described above.
Fig. 8A illustrates the operation of the systematic encoder 728 in a specific embodiment of the invention. Initially, the systematic encoder 728 receives the input symbols IS(0), IS(1), ..., IS(K-l) from input symbol generator 726 in Fig. 7. The input symbols may be known in their entirety at the start of the encoding, or they may only be partially known.
In this embodiment, the systematic encoder 728 has access to the non-systematic key generator 727, which generates as many non-systematic keys Io,Iι, .... as the number of non-systematic output symbols generated. In addition, the systematic key generator 730 generates as many systematic keys C0, Cj., ... , Cκ. as there are input symbols. Systematic Encoder 728 passes the original input symbols to the transmit module 750, these symbols being transmitted as the systematic output symbols. The systematic encoder 728 also operates to generate non-systematic output symbols B(Io), B(Iι), ... for each of the keys Io, Ii, ... generated by non-systematic key generator 727. The operation of the systematic key generator 730 is further described below.
Systematic key generator 730 and systematic key regenerator 780 (Fig. 7) may have access to some shared information so systematic key regenerator 780 can succeed in generating the same keys as the systematic key generator 730. In some embodiments the shared information may be transmitte'd to the systematic key regenerator 780. In other embodiments the systematic keys may be a deterministic function of other parameters of the code, e.g., the number of input symbols and the weight table.
Fig. 8B illustrates the operation of the systematic decoder 755 in a specific embodiment of the invention. Systematic decoder 755 receives systematic and non- systematic output symbols from receive module 750 denoted as IS(x), IS(y), ... , IS(z), and B(Ia), B(Ib), ... , respectively. In a particular embodiment, systematic decoder 755 has access to the systematic key regenerator 780, and to non-systematic key regenerator 760. The output of the systematic chain reaction decoder is the set of initial input symbols IS(0), IS(1), ... , IS(K-1).
Fig. 9A illustrates the systematic encoder 728 in more detail. The systematic encoder 728 includes a chain reaction decoder 910, and a chain reaction encoder 920. Additionally, it may have access to a memory device (not shown) to store intermediate symbols S(0), S(l), ... , S(K-l).
Upon receiving the input symbols IS(0), IS(1), ... , IS(K-l), and the systematic keys Co, Ci, ..., Cκ-l5 chain reaction decoder 910 computes a set of intermediate input symbols S(0), S(l), ... , S(K-1) using, for example, the decoding methods for chain reaction codes described in the patents and patent applications incorporated herein. In some embodiments of the present invention the intermediate input symbols may be stored in memory, or on disk. In other embodiments, the intermediate input symbols may be forwarded to chain reaction encoder 920 as they become available.
Chain reaction encoder 920 uses the intermediate input symbols generated by chain reaction decoder 910 together with non-systematic keys Io, Ij., I2, ... generated by non-systematic key regenerator 727, to generate non-systematic output symbols B(Io), B(Iι), ... . In some embodiments, this encoding process may be accomplished using the input symbol encoding process described in either Luby I or Raptor, with the modification that the intermediate input symbols of the present invention are used as the input symbols of Luby I. In a particular embodiment the non-systematic output symbols are supplied to the transmit module 140 after the input symbols IS(0), IS(1), ...., IS(K- 1). This is however not essential for the functioning of this invention. Further, the order of transmission from the transmit module 740 may vary as well.
Fig. 9B is an illustrative embodiment of the systematic decoder 755, which includes a chain reaction decoder 930, and a chain reaction encoder 940. The input to the systematic decoder includes the received output symbols some of which comprise the received systematic output symbols IS(x), IS(y), IS(z), ... , and some of which may comprise received non-systematic output symbols B(Ia), B(Ib), .... In some embodiments, the decoder may copy the received systematic symbols to a memory device, and directly forward them to input file reassembler 765.
Chain reaction decoder 930 uses the symbols IS(x), IS(y), ... , IS(z), B(Ia), B(Ib), ..., the systematic keys Cx, Cy, ... , Cz, generated by the systematic key regenerator 780, and the non-systematic keys Ia, lb, ... generated by non-systematic key regenerator 760 to produce intermediate input symbols S(0), S(l), ..., S(K-l). The systematic keys Cx, Cy, ...,CZ, correspond to the received input symbols IS(x), IS(y), ... , IS(z). In some embodiments, the recovered intermediate symbols may be stored to a secondary storage before being passed to the chain reaction encoder 440. In other embodiments, these intermediate symbols may be passed directly to the chain reaction encoder 940.
Chain reaction encoder 940 uses the intermediate input symbols and the systematic keys Cu, Cy, ... , Cw corresponding to erased systematic output symbols IS(u), IS(v), ... , IS(w) to generate and output the missing original input symbols IS(u), IS(v), ..., IS(w). As an exemplary embodiment, for each of the initial keys Cu, Cv, ... , Cw, the decoder identifies a weight W and W symbols among the intermediate input symbols S(0), ..., S(K-1), and XOR's the values of output symbols to obtain the erased input symbols IS(u), IS(v), ... , IS(w) corresponding to the systematic keys Cu, Cv, ..., Cw. The amount of computational resources used by chain reaction encoder 940, in one embodiment, will be proportional to the number of systematic output symbols that are erased. For example, if all the systematic output symbols are received, then the decoder may not perform any computations, and forward the received symbols to input file reassembler 765.
In a specific embodiment of the present invention, the systematic keys are calculated by systematic key generator 730 before symbol transmission, and re-computed by the systematic key regenerator 780 after symbol reception. The systematic keys are used by the chain reaction decoder 910 and encoder 930 to obtain the intermediate input ' symbols S(0), S(l), . . . S(K-l).
Fig. 10 is an exemplary embodiment of the systematic key generation process. One input to the systematic key generator may be the number K of input symbols IS(0), IS(1), ... , IS(K-l). Systematic key generation starts by setting a variable j equal to 0. During the algorithm a matrix M with K columns, which, initially, has zero rows, is updated by adding rows as the algorithm progresses. For every different value of j the algorithm generates a different key D(j) at 1020. This key may be generated by the methods described in Luby I or Raptor, and may use the random number generator 135 shown in Fig. 1. Next at 1030, the key D(j) is used to compute the entries of the j-th row of the matrix M. One possible embodiment of such a computation would be to use key D(j) in the chain reaction coding process. In this case, using the weight table, the key D(j) identifies a weight W and W values among the values 0, 1, ... , K-l. It then may set a 1 at position m of the jth row of M if m is one of the random or pseudorandom values generated, and set the other values of the jth row to zero.
If the test in 1040 is positive, and rows r(0), r(l), ... , r(K-l) of M are discovered to be linearly independent, then the systematic keys Co, Ci, ... , Cκ-ι are set to the keys D(r(0)), ... , D(r(K-l)), and the keys are output. If the test in 1040 is negative, then the counter j is incremented in 1060, and the computation is repeated from 1020 on.
At 1110, L keys D(0), .., D(L-l) are generated. This process may be accomplished through the use of a random number generator 735. In other embodiments, these keys may be generated from a fixed list of re-usable keys. This process may also provide an indication of how the keys were generated. For example, if a random number generator is used, the seed for the generator may be recorded for future use by the systematic key regenerator. Using the keys D(0), D(l), ... , D(L-1) a Modified Decoding Graph is set up in 1120 as described above and exemplified in Fig. 5. This process may employ the knowledge of the specific weight table for the code, as well as the knowledge of any static encoding used, as described in Raptor.
At 1130, the Modified Decoding Graph is decoded using any of the methods presented earlier. As a by-product of the decoding, the indices r(0), r(l), ..., r(K-l) of those output nodes that trigger the recovery of an input node are recorded. At 1140, the systematic keys are outputted as Co=D(r(0)), ... , CK=D(r(K-l)).
Fig. 12 illustrates a third method for computing the systematic keys. Similar to the method of Fig. 11 the keys D(0), ... ,D(IA) are generated in 1210, and the Decoding Graph is set up using these keys, and possibly the weight table. Next a set S is initialized as the empty set in 1230. The set S will contain the indices of those output symbols which are used in the chain reaction decoding process to recover the value of an input node. In 1240 the chain reaction decoding process is applied to the Decoding Graph by identifying an output node of degree one. The index of this output node is added to the set S in accordance with the above mentioned role of this set. A test is performed at 1250 as to whether the set S already has the right number of elements. If not, the algorithm loops back to 1240 where another input node of degree one is chosen to continue the decoding process. If the size of S is K, then the elements of S are sorted starting with the smallest element to yield the sorted elements So, ... ,Sκ-ι and the systematic keys are calculated as Co=D(S0), ... ,Cκ-ι=D(Sκ-ι) in 1260.
Fig. 13 illustrates a fourth method for computing systematic keys in accordance with the present invention. . In this method it is assumed that a decoding algorithm is available which on input K and a set of keys can decide whether the original K symbols are decodable from the given set of keys. Examples of such algorithms are provided by the decoders described in Luby I, Raptor, of Inactivation Decoding.
At 1310 L keys D(0), ... ,D(L-1) are generated. Similar to the above description, this process may be accomplished through the use of a random number generator 735, or the keys may be generated from a fixed set of re-usable keys. At 1315, the decoder is used to decide whether or not it is possible to decode the K symbols from the set of keys D(0), ... ,D(L-1). If decoding is not successful, then the given set of keys does not contain as a subset the systematic keys, and the algorithm aborts at 1325. Otherwise, three sets are initialized at 1330. These sets are called Systematic, Non_Systematic, and Unvisited, respectively. At the end of the algorithm, the set Systematic will contain the set of systematic keys. Originally, at 1330 the sets Systematic and Non_Systematic are initialized to empty sets, while the set Unvisited contains all the original keys D(0),...,D(L-1). At processes 1335 through 1360 a key is removed from the set Unvisited and a decoding attempt is made on the keys contained in the sets Systematic and Unvisited. If the attempt is successful, then the chosen key C does not belong to the set of systematic keys. On the contrary, if decoding is not successful, then the key does belong to the set of systematic keys. The procedure consisting of removal of an unvisited key and decoding (1335), a test as to whether decoding was successful (1340), and the following addition of the chosen key to the set Systematic or Non_Systematic based on the outcome of the decoder (1345 and 1350) are repeated as long as the set Systematic has fewer than the number K of original input symbols.
Fig. 14 illustrates a method for decoding a chain reaction code having systematic and non-systematic symbols in accordance with the present invention. At 1410, non- systematic keys Ia, lb, ...corresponding to the received non-systematic output symbols B(Ia), B(Ib), ... are used to generate a matrix B which has as many rows as there are received non-systematic output symbols and as many columns as there are input symbols. For each key the same mechanism as for encoding chain reaction codes is used to generate a weight W and a set JlsJ2, ... ,J of indices of input symbols from which the output symbol corresponding to the key is generated. Then, in the corresponding row of the matrix B the positions corresponding to Jl5J2, ... Jψ are set to 1, while the other positions in that row are set to 0. The procedure is repeated until all keys corresponding to non-systematic received symbols are exhausted.
Next at 1420, a similar procedure is applied to construct a square matrix C with as many rows and columns as the number of input symbols from the systematic keys Co, d, ... , Cκ-1- This process also computes the inverse of the matrix C, called A. Computing the inverse of A can be performed in a variety of ways, as is known to those of skill in the art. For example, a Gaussian elimination algorithm can be used to calculate A. In other embodiments a version of chain reaction decoding can be utilized to perform this step. This is further illustrated in an example later in this disclosure.
At 1430, the product of the matrices B and A is calculated over the binary field GF(2) to obtain a matrix H. Next at 1440, two sets of indices E and R are determined: E is the set of indices of the non-received systematic symbols, while R is the set of indices of the received systematic symbols. For example, assume there are 11 input symbols with indices 0, 1, 2, ... , 10. If, after the transmission, the systematic symbols corresponding to the indices 0, 3, 9, 10 are received, then R={0,3,9,10}, while E = {1,2,4,5,6,7,8}. The matrix H, computed in 1430 as the product of B and A is then subdivided into two submatrices HE and HR: HE is the submatrix of H obtained by taking the columns of H corresponding to the indices of the systematic symbols not received, and HR is the submatrix of H corresponding to the indices of the received systematic symbols. In the example above, HE would be the submatrix of H formed by the columns 1, 2, 3, 4, 5, 6, 7, and 8 of H.
At 1450, the matrix HR is multiplied with the vector formed by the received systematic symbols IS(x), IS(y), ... , IS(z). For example, in the scenario above, HR would be multiplied with the values of the systematic symbols 0, 3, 9, 10 (in this ordering). The actual multiplication can be performed in a variety of ways, as is known to those skilled in the art. The result of this multiplication, called the vector y in the following, may be stored for future use. At 1460, the non-systematic received output symbols are used to set up a vector b. Where there are L such symbols, the number of entries in the vector b is L. This step may only be logical. In other words, this step may not require any computations. Next, the results of the previous multiplication stored in the vector y is component-wise XOR'd with the entries of the vector b, i.e., each of the non-systematic received output symbols are XOR'd with the corresponding symbols of the vector y. The result of this operation may be stored in place of the received non-systematic symbols, or it may be stored at a different location.
ELI. Exemplary Systematic Coding and Decoding
Fig. 15A describes a Decoding Graph used to obtain systematic keys Co, Ci, „., C8. It is assumed that 12 keys D(0), D(l), ... , D(ll) have already been generated, for example by the operation in 1110 of Fig. 11. The graph in Fig. 15 A describes the Modified Decoding Graph between the input nodes denotedl520(a), ... , 1520(i), and output nodes denotedl530(a), ... , 1530(1) using the keys D(0), ...,D(11). Chain reaction decoding may now be applied to this graph to obtain the systematic keys as the keys of those output nodes which trigger the recovery of an input node in the course of chain reaction decoding.
In operation, node 1530(a) may be used to recover the input nodel520(b). Accordingly, the first systematic key C0 is then equal to the first of the generated keys, namely D(0). Recovery of input node 1520(b) causes output node 1530(c) to become of degree 1, and hence to trigger recovery of node 1520(e). Continuing in this way, it can be seen that the nodes colored light gray in Fig. 15A can be used to recover the input nodes. The sequence of output nodes used to recover the input nodes is equal to 1530(a), 1530(b), 1530(c), 1530(d), 1530(e), 1530(f), 1530(g), 1530(h), 1530(j). As a result, the sequence of systematic keys may be chosen as shown in Fig.l5B. It should be noted that the recovery process for the illustrated chain reaction decoding is only conceptual. In particular, no XOR operation is performed in this particular example.
Fig. 16B exemplifies the operation of the chain reaction decoder 910. The input symbols are denoted by IS(0), ... ,IS(8). The keys Co, Cl5 ... , C8 are used to set up the graphical dependency between the input symbols and the intermediate input symbols S(0), ... , S(8). For example, the key Co shows that IS(0) is equal to the value of S(l), while the key C4 shows that IS(4) is equal to the XOR of the values of S(2), S(5), and S(7). Chain reaction decoding can now be applied to obtain the values S(0), S(l), ... , S(8). The schedule to obtain these values may have been forwarded to the chain reaction decoder 910 from the systematic key generator 730 in Fig. 7, since this schedule was set up to obtain the keys Co, Ci, ... , C8. Unlike the operation of the systematic key generator, this step may employ XOR'ing the values of the individual symbols.
In the example of Fig. 16A the schedule may first produce the value of S(l), which in turn may produce the value of S(4) using the value of IS(1). This triggers the recovery of the values of S(0), and S(7), etc.
Fig. 16B exemplifies the operation of the chain reaction encoder 920 in Fig. 9 A by showing the generation of the first 11 non-systematic output symbols O(0), ... , O(10). (The illustrated output symbols O(i) refers to previously described output symbols B(L).) As was described before, the output of the systematic encoder consists of the systematic output symbols IS(0), ... , IS(8), followed by the output symbols O(0), ....,O(10), .... This particular ordering is only exemplary, and other orderings can be used in alternative embodiments under the present invention. Systematic Decoding
Figs. 17 A and 17B exemplify an embodiment of the process of systematic chain reaction decoding. It is assumed that the received systematic output symbols are IS(1), IS(6), and IS(7), while the received non-systematic output symbols are O(0), 0(3), 0(4), 0(6), 0(7), 0(8), 0(9), and O(10). The task of the decoder is to compute the values of the missing systematic output symbols, i.e., the values IS(0), IS(2), IS(3), IS(4), IS(5), and IS(8). Fig. 17A is an example of how the chain reaction decoder 930 and the chain reaction encoder 940 in Fig. 9B may be combined into one decoder. In some applications, such a combination may lead to computational savings.
Using the keys , C6, and C7 corresponding to the received systematic output symbols, and the keys corresponding to the received non-systematic output symbols, a graph is set up between the received output symbols, and the intermediate input symbols S(0), ..., S(8). A connecting line is drawn between an output symbol and all the intermediate input symbols whose XOR yields the value of the output symbol. The individual connections are the same as the ones shown in Fig. 16A and Fig.lόB. The particular ordering of the received output symbols may not be equal to the ordering chosen to represent the Decoding Graph.
This graph is extended by another layer of nodes, corresponding to the erased systematic output symbols. This graph corresponds to the upper part of Fig. 17 A, in which the input symbols IS(0), IS(2), IS(3), IS(4), IS(5), and IS(8) are connected via dotted lines to those intermediate input symbols of which they are an XOR of. Again, these connections may be verified against the corresponding connections in Fig. 17A.
The process of decoding in this particular example may start by applying the chain reaction decoding to the lower graph; every time one of the intermediate symbols is recovered, its value may be XOR'd to the value of the all the neighbors of this symbol among the non-received original symbols in the upper part of the figure.. Originally, the values of these symbols may be set to zero.
For example, output symbol 0(4) may be used to recover the value of S(3). The value of S(3) may then be XOR'd into the current value of IS(5). After this step, the value of IS(5) is equal to that of S(3). Recovery of S(3) reduces the degree of the output node O(10) to one. This output node in turn recovers the value of the intermediate symbol S(6). This value is XOR'd into the current value of IS(5), so that after this step the value of IS(5) is recovered. The process may continue until all the non-received systematic input symbols are recovered.
For example, symbol 0(4) is used to recover S(3). Symbol O(10) is used to recover S(6). S(3) and S(6) together recover S(5). Recovery of S(6) triggers the recovery of S(8) (using 0(9)) and the recovery of S(0) (using the received systematic output symbol IS(7)). Recovery of S(8) triggers the recovery of IS(3). Recovery of S(0) triggers the recovery of S(4) (using IS(1)). On the other hand, using O(0), the recovery of S(8) triggers that of S(l), which together with S(4) recovery IS(2). Furthermore, recovery of S(l) leads to recovery of IS(0), since these values are identical. Using 0(8), and the recovered value of S(4), the value of S(5) is obtained. This, in turn, recovers the value of IS(8), since the latter is the XOR of S(5), S(4), and S(0), and all these values are known at this stage. Using IS(6) and S(4), the value of S(7) is obtained. Using 0(7), this recovers the value of S(2), which together with S(7) recovers the value of the last remaining input symbol, namely IS(4).
Documents Herein Incorporated by Reference:
U.S. Patent No. 6,307,487 to Michael G. Luby, entitled "Information Additive Code Generator and Decoder for Communication Systems" (referred to herein as Luby I); U.S. Patent Application No. 09/792,364, filed February 22, 2001, entitled "Scheduling of Multiple Files for Serving on a Server";
U.S. Patent Application No. 10/032,156, filed December 21, 2001, entitled "Multi-Stage Code Generator and Decoder for Communication Systems" (referred to herein as "Raptor"); and
U.S. Patent Application No. 10/459,370, filed June 10, 2003, entitled "Systems and Processes for Decoding Chain Reaction Codes through Inactivation" (referred to herein as "Inactivation Decoding").
1. A method of encoding data into a chain reaction code having systematic output symbols and non-systematic output symbols, the method comprising: generating, from the data, a set of input symbols, the input symbols comprising systematic output symbols; and generating, from the set of input symbols, one or more non-systematic output symbols, wherein each of the one or more non-systematic output symbols is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols, wherein any subset of the set of input symbols is recoverable from (i) a predetermined number of non-systematic output symbols, or (ii) a combination of (a) input symbols which are not included in the subset of input symbols that are to be recovered and (b) one or more of the non-systematic output symbols.
2. The method of claim 1, wherein generating one or more non-systematic output symbols comprises: generating a plurality of intermediate input symbols from the set of input symbols; and encoding the plurality of intermediate input symbols into one or more non- systematic output symbols, wherein one or more intermediate input symbols are encoded into one non-systematic output symbol.
3. The method of claim 2, wherein generating the plurality of intermediate input symbols comprises: computing systematic keys for the plurality of input symbols; and generating, from the plurality of input symbols and corresponding systematic keys, a plurality of intermediate input symbols.
4. The method of claim 3, wherein computing systematic keys for the plurality of input symbols comprises constructing a matrix having K columns and J rows, wherein K corresponds to the number of input symbols, the method further comprising:
(ii) computing a key D(J) as a function of J;
(iii) computing row entries of the Jth row as a function of the key D(J); and (iv) determining if the rows in the matrix are linearly independent, wherein if the matrix rows are not linearly independent J is incremented to J + 1 and (ii)-(iϋ) are repeated, and wherein if the matrix rows are linearly independent the systematic keys are computed as a function of the linearly independent rows.
5. The method of claim 4, wherein (ii) computing a key D(J) comprising using a random number generator to compute key D(J) as a function of J.
(i) computing L unique keys D(0)-D(L-1), wherein L is a predefined number;
(ii) constructing a modified decoding matrix having K columns and L rows, wherein K corresponds to the number of input symbols, and wherein for any value of j between 0 and L-1 the row entries along the jth row are computed as a function of the key D(j); and
(iii) solving the set of linear equations described by the modified decoding matrix, wherein the systematic keys are computed as a function of the solutions of the linear equations.
8. The method of claim 1, further comprising transmitting the systematic output symbols and the non-systematic output symbols over a communication channel.
9. The method of claim 8, further comprising: receiving one or more systematic output symbols comprising a first subset of the set of input symbols; receiving one or more non-systematic output symbols, wherein each non- systematic output symbol is selected from an alphabet of non-systematic output symbols, arid wherein each non-systematic output symbol is generated as a function of one or more of the input symbols; and recovering a remaining subset of the set of input symbols comprising one or more input symbols not included in the first set of input symbols, the remaining subset of input symbols recovered from:
10. The method of claim 9, wherein recovering a remaining subset of input symbols from a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols comprises: decoding a combination of the one or more received non-systematic output symbols and the one or more received systematic input symbols into a plurality of intermediate input symbols; and encoding the plurality of intermediate input symbols into a plurality of input symbols comprising a remaining subset of input symbols, the remaining subset of the input symbols comprising one or more input symbols not included in the first set of input symbols.
11. The method of claim 10, wherein decoding the one or more non-systematic output symbols and the one or more systematic output symbols into a plurality of intermediate input symbols comprises: computing systematic keys corresponding to the received systematic output symbols; computing non-systematic keys corresponding to the received non-systematic output symbols; and generating, from the systematic keys, the non-systematic keys, the received non- systematic output symbols, and the received systematic output symbols the plurality of intermediate input symbols.
12. The method of claim 10, wherein encoding the plurality of intermediate input symbols into one or more input symbols comprising the remaining subset of input symbols comprises: computing systematic keys for the systematic output symbols not received; and generating, from the systematic keys corresponding to the systematic output symbols not received and the intermediate input symbols, the remaining subset of input symbols.
13. A method of decoding a chain reaction code having systematic output symbols and non-systematic output symbols into a set of input symbols, the input symbols comprising data which is sought, the method comprising: providing a first subset of the set of input symbols, the first subset of input symbols comprising one or more systematic output symbols; providing one or more non-systematic output symbols, wherein each non- systematic output symbol is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols; and recovering a remaining subset of the input symbols comprising one or more input symbols not included in the first set of input symbols, the remaining subset of input symbols recovered from:
14. The method of claim 13, wherein recovering a remaining subset of input symbols from a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols comprises: decoding a combination of the one or more received non-systematic output symbols and the one or more received systematic input symbols into a plurality of intermediate input symbols; and encoding the plurality of intermediate input symbols into one or more input symbols comprising a remaining subset of input symbols, the first subset and remaining subset of input symbols collectively forming the set of input symbols.
15. The method of claim 14, wherein decoding the one or more non-systematic output symbols into a plurality of intermediate input symbols comprises: computing systematic keys corresponding to the received systematic output symbols; computing non-systematic keys corresponding to the received non-systematic output symbols; and generating, from the systematic keys, the non-systematic keys, the non-systematic output symbols, and the received systematic output symbols the plurality of intermediate input symbols.
16. The method of claim 13, wherein encoding the plurality of intermediate input symbols into one or more input symbols comprising the remaining subset of input symbols comprises: computing systematic keys for the systematic output symbols not provided; and generating, from the systematic keys corresponding to the systematic output symbols not received and the intermediate input symbols, the remaining subset of input symbols.
17. The method of claim 13, further comprising receiving the systematic and non- systematic output symbols by means of a transmission sent along a communication channel.
18. A method of processing data using chain reaction codes, the method comprising: generating, from the data, a set of input symbols, the input symbols comprising systematic output symbols; generating, from the set of input symbols, one or more non-systematic output symbols, wherein each of the one or more non-systematic output symbols is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols; receiving a first subset of the set of input symbols, the first subset of input symbols comprising one or more systematic output symbols; receiving one or more non-systematic output symbols, wherein each non- systematic output symbol is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols; and recovering a remaining subset of the input symbols comprising one or more input symbols not included in the first set of input symbols, the remaining subset of input symbols recovered from:
19. The method of claim 18, wherein generating one or more non-systematic output symbols comprises: generating a plurality of intermediate input symbols from the set of input symbols; and encoding the plurality of intermediate input symbols into one or more non- systematic output symbols, wherein one or more intermediate input symbols are encoded into one non-systematic output symbol.
20. The method of claim 19, wherein generating the plurality of intermediate input symbols comprises: computing systematic keys for the plurality of input symbols; and generating, from the plurality of input symbols and corresponding systematic keys, a plurality of intermediate input symbols.
21. The method of claim 18, wherein recovering a remaining subset of input symbols from a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols comprises: decoding a combination of the one or more received non-systematic output symbols and the one or more received systematic output symbols into a plurality of intermediate input symbols; and encoding the plurality of intermediate input symbols into one or more input symbols comprising a remaining subset of input symbols, the first subset and remaining subset of input symbols collectively forming the set of input symbols.
22. The method of claim 21, wherein decoding the one or more non-systematic output symbols and the one or more received systematic output symbols into a plurality of intermediate input symbols comprises: computing systematic keys corresponding to the received systematic output symbols; computing non-systematic keys corresponding to the received non-systematic output symbols; and generating, from the systematic keys, the non-systematic keys, the non-systematic output symbols, and the received systematic output symbols the plurality of intermediate input symbols.
23. The method of claim 18, wherein encoding the plurality of intermediate input symbols into one or more input symbols comprising the remaining subset of input symbols comprises: computing systematic keys for the systematic output symbols not provided; and generating, from the systematic keys corresponding to the systematic output symbols not received and the intermediate input symbols, the remaining subset of input symbols.
24. The method of claim 18, further comprising receiving the systematic and non- systematic output symbols by means of a transmission sent along a communication channel.
26. An encoder configured to encode a set of input data into a chain reaction code, the chain reaction code including systematic output symbols and non-systematic output symbols, the encoder comprising: an input symbol generator coupled to receive the set of input data and operable to output, in response, one or more input symbols; a systematic key generator operable to generate a systematic key corresponding to each input symbol; a non-systematic key generator operable to generate one or more non-systematic keys; and a systematic encoder coupled to receive the one or more input symbols, the systematic keys, and the non-systematic keys and to output, in response, one or more non-systematic keys and one or more input symbols, wherein the output input symbols comprise systematic output symbols.
27. The encoder of claim 26, wherein the systematic encoder comprises: a chain reaction decoder coupled to receive the one or more input symbols and systematic keys corresponding to the one or more input symbols, the chain reaction decoder operable to produce, in response, one or more intermediate input symbols; a chain reaction encoder coupled to receive the one or more intermediate input symbols and the one or more non-systematic keys, the chain reaction decoder operable to produce, in response, one or more non-systematic output symbols.
28. The encoder of claim 27, further comprising a transmit module coupled to receive the one or more input symbols and the one or more non-systematic output symbols, the transmit module operable to transmit the input symbols and the non-systematic output symbols, wherein the transmitted input symbols comprise systematic output symbols.
29. An decoder configured to decode a set of chain reaction codes, the chain reaction code including one or more non-systematic output symbols and one or more systematic output symbols, the decoder comprising: a non-systematic key generator configured to generate a set of non-systematic keys for each acquired non-systematic output symbols; a systematic key generator configured to regenerate one or more systematic keys; a systematic decoder coupled to receive the one or more systematic output symbols, the one or more systematic output symbols, the systematic keys, and the non- systematic keys, and to output, in response, one or more input symbols.
30. The decoder of claim 29, wherein the systematic key regenerator is configured to regenerate a first set of systematic keys and a second set of systematic keys, wherein each of the first set of systematic keys corresponds to an acquired systematic output symbol, and wherein each of the second set of systematic keys corresponds to a missing systematic output symbol.
31. The decoder of claim 30, wherein the systematic encoder comprises: a chain reaction decoder coupled to receive the received systematic output symbols, the set of non-systematic keys, and the first and second set of systematic keys, the chain reaction decoder producing, in response, a corresponding set of intermediate input symbols; and a chain reaction encoder coupled to receive the intermediate input symbols and the second set of systematic keys, the chain reaction encoder producing, in response, a copy of the missing systematic output symbols, wherein the received systematic output symbols in combination with the copy of the non-received systematic output symbols comprises the complete set of transmitted input symbols comprising the set of original data.
32. A computer program product, stored on a computer readable medium, for encoding data into a chain reaction code, the chain reaction code including systematic output symbols and non-systematic output symbols, the computer program product comprising: instruction code to generate, from the data, a set of input symbols, the input symbols comprising systematic output symbols; and instruction code to generate, from the set of input symbols, one or more non- systematic output symbols, wherein each of the one or more non-systematic output symbols is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols, wherein any subset of the set of input symbols is recoverable from (i) a predetermined number of non-systematic output symbols, or (ii) a combination of (a) input symbols which are not included in the subset of input symbols that are to be recovered and (b) one or more of the non-systematic output symbols.
33. The computer program product of claim 32, wherein instruction code to generate one or more non-systematic output symbols comprises: instruction code to generate a plurality of intermediate input symbols from the set of input symbols; and instruction code to encode the plurality of intermediate input symbols into one or more non-systematic output symbols, wherein one or more intermediate input symbols are encoded into one non-systematic output symbol.
34. The computer program product of claim method of claim 33, wherein the instruction code to generate the plurality of intermediate input symbols comprises: instruction code to compute systematic keys for the plurality of input symbols; and instruction code to generate, from the plurality of input symbols and corresponding systematic keys, a plurality of intermediate input symbols.
35. A computer program product, stored on a computer readable storage medium, for decoding a chain reaction code into a set of input symbols, the chain reaction code including systematic output symbols and non-systematic output symbols, the input symbols comprising data which is sought, the computer program product comprising: instruction code to provide a first subset of the set of input symbols, the first subset of input symbols comprising one or more systematic output symbols; instruction code to provide one or more non-systematic output symbols, wherein each non-systematic output symbol is selected from an alphabet of non-systematic output symbols, and wherein each non-systematic output symbol is generated as a function of one or more of the input symbols; and instruction to recover a remaining subset of the input symbols comprising one or more input symbols not included in the first set of input symbols, the remaining subset of input symbols recovered from:
36. The computer program product of claim 35, wherein the instruction code to recover a remaining subset of input symbols from a combination of (a) one or more input symbols from the first subset, and (b) one or more non-systematic output symbols comprises: instruction code to decode a combination of the one or more received non- systematic output symbols and the one or more received systematic input symbols into a plurality of intermediate input symbols; and instruction code to encode the plurality of intermediate input symbols into one or more input symbols comprising a remaining subset of input symbols, the first subset and remaining subset of input symbols collectively forming the set of input symbols.
37. The computer program product of claim 36, wherein the instruction code to decode the one or more non-systematic output symbols and the one or more received systematic input symbols into a plurality of intermediate input symbols comprises: instruction code to compute systematic keys corresponding to the received systematic output symbols; instruction code to compute non-systematic keys corresponding to the received non-systematic output symbols; and instruction code to generate, from the systematic keys, the non-systematic keys, the non-systematic output symbols, and the received systematic output symbols the plurality of intermediate input symbols.
38. The computer program product of claim 36, wherein instruction code to encode the plurality of intermediate input symbols into one or more input symbols comprising the remaining subset of input symbols comprises: instruction code to compute systematic keys for the systematic output symbols not provided; and instruction code to generate, from the systematic keys corresponding to the systematic output symbols not received and the intermediate input symbols, the remaining subset of input symbols.
PCT/US2003/031108 2002-10-05 2003-10-01 Systematic encoding and decoding of chain reaction codes WO2004034589A9 (en)
US31959702 true 2002-10-05 2002-10-05
US60/319,597 2002-10-05
JP2004543067A JP4546246B2 (en) 2002-10-05 2003-10-01 Systematic symbols and decoding the chain encryption reaction
EP20030808111 EP1552617A2 (en) 2002-10-05 2003-10-01 Systematic encoding and decoding of chain reaction codes
KR20057005861A KR101143282B1 (en) 2002-10-05 2003-10-01 Systematic encoding and decoding of chain reaction codes
WO2004034589A2 true WO2004034589A2 (en) 2004-04-22
WO2004034589A3 true WO2004034589A3 (en) 2004-06-10
WO2004034589A9 true true WO2004034589A9 (en) 2004-07-15
ID=32093637
PCT/US2003/031108 WO2004034589A9 (en) 2002-10-05 2003-10-01 Systematic encoding and decoding of chain reaction codes
US (5) US6909383B2 (en)
EP (5) EP2357732A1 (en)
JP (3) JP4546246B2 (en)
KR (1) KR101143282B1 (en)
CN (1) CN100539439C (en)
WO (1) WO2004034589A9 (en)
EP1788708A1 (en) * 2005-11-16 2007-05-23 BenQ Corporation Method and device for decoding encoded symbols
JP4722693B2 (en) * 2005-12-16 2011-07-13 Ｋｄｄｉ株式会社 Communications system
EP1980074A4 (en) * 2006-02-13 2012-12-19 Digital Fountain Inc Fec streaming with aggregation of concurrent streams for fec computation
US20080317243A1 (en) * 2007-03-30 2008-12-25 Ramprashad Sean A Low complexity encryption method for content that is coded by a rateless code
CN101540778B (en) 2008-03-19 2014-09-03 华为技术有限公司 Method, device and system for transmitting data
US8301974B2 (en) * 2008-10-22 2012-10-30 Samsung Electronics Co., Ltd. System and method for low complexity raptor codes for multimedia broadcast/multicast service
EP2234304B1 (en) 2009-03-19 2013-01-02 Deutsches Zentrum für Luft- und Raumfahrt e.V. Method for recovery of lost and/ or corrupted data
WO2013067219A3 (en) 2011-11-01 2013-07-11 Qualcomm Incorporated Content delivery system with allocation of source data and repair data among http servers
FR2951339B1 (en) * 2009-10-09 2011-12-09 Commissariat Energie Atomique Method for non-binary code decoding
KR101651683B1 (en) * 2010-05-07 2016-08-29 삼성전자주식회사 Apparatus and method for channel encoding in a communication system
US8732565B2 (en) * 2010-06-14 2014-05-20 Samsung Electronics Co., Ltd. Method and apparatus for parallel processing in a gigabit LDPC decoder
CN103166647B (en) * 2011-12-13 2016-02-10 北京慧眼智行科技有限公司 Coded picture data verification method and system
DE102012200134B4 (en) * 2012-01-05 2013-08-22 Deutsches Zentrum für Luft- und Raumfahrt e.V. A method for transmitting an analog or digital signal
CN102571104B (en) * 2012-01-15 2014-01-15 西安电子科技大学 Distributed encoding and decoding method for RA (Repeat Accumulate) code
CN102594368B (en) * 2012-02-29 2014-04-02 西安空间无线电技术研究所 LDPC (Low Density Parity Check) decoding method with variable maximum iterations and decoder
CN102832951B (en) * 2012-04-23 2015-04-08 中国科学技术大学 Realizing method for LDPC (Low Density Parity Check) coding formula based on probability calculation
CN102651651B (en) * 2012-04-23 2014-07-09 北京交通大学 Method and device for constructing quasi-cyclic LDPC codes by utilizing cyclotomic cosets
CN102820890B (en) * 2012-05-09 2015-02-18 天津大学 Encoder device and method for short code length multi-system weighted repeat-accumulate code
CN102811063A (en) * 2012-05-29 2012-12-05 中国农业大学 Construction method for low-density parity-check code
CN102882674B (en) * 2012-07-10 2016-09-21 中国电力科学研究院 Substation for quantum key generation and key distribution system to restore
CN102811064B (en) * 2012-08-01 2014-11-26 清华大学 Method for constructing multi-rate low density parity check (LDPC) code
CN102811065B (en) * 2012-08-09 2015-02-04 福州大学 Mini-sum decoding correcting method based on linear minimum mean error estimation
US8839067B2 (en) 2012-08-31 2014-09-16 Industrial Technology Research Institute Apparatus and method for accelerating the encoding of raptor codes
CN102891686B (en) * 2012-09-20 2015-07-22 中国科学院上海微系统与信息技术研究所 Irregular quasi-cyclic low-density parity check code construction method
CN102916705B (en) * 2012-09-25 2015-05-13 广东省电信规划设计院有限公司 LDPC (low density parity check) code construction method and LDPC code construction device
CN102843150B (en) * 2012-09-27 2015-03-11 张燕 Low-latency QC-LDPC (Quasi-Cyclic Low-Density Parity-Check) parallel encoder and encoding method
CN102857238B (en) * 2012-09-27 2015-03-11 刘志文 LDPC (Low Density Parity Check) encoder and encoding method based on summation array in deep space communication
CN102882532B (en) * 2012-09-27 2015-03-25 苏州威士达信息科技有限公司 LDPC (low density parity check) encoder in CMMB (China mobile multimedia broadcasting) based on rotate right accumulation and encoding method
CN102882533B (en) * 2012-09-27 2015-03-25 苏州威士达信息科技有限公司 Low density parity check (LDPC) serial encoder in digital terrestrial multimedia broadcasting (DTMB) and based on lookup table and coding method
CN102843152B (en) * 2012-09-27 2015-03-25 中国传媒大学 LDPC (Low-Density Parity-Check) encoder and encoding method based on parallel filtering in CMMB (China Mobile Multimedia Broadcasting)
CN102891687B (en) * 2012-09-27 2015-03-11 张燕 Summation array-based QC-LDPC (Quasi-Low-Density Parity-Check) parallel encoder and encoding method
CN102882531B (en) * 2012-09-27 2015-03-25 苏州威士达信息科技有限公司 Coder and coding method for LDPC (low-density parity-check) codes in DTMB (digital television terrestrial multimedia broadcasting) based on summation array
CN102843148B (en) * 2012-09-27 2015-02-04 刘志文 QC-LDPC (Quasi-Cyclic Low-Density Parity-Check) serial encoder and encoding method based on lookup table
CN102857235B (en) * 2012-09-27 2015-03-25 中国传媒大学 LDPC (low-density parity-check) encoder and encoding method in DTMB (digital terrestrial multimedia broadcasting) system based on shared register
CN102857239B (en) * 2012-09-27 2015-03-25 苏州威士达信息科技有限公司 LDPC (Low Density Parity Check) serial encoder and encoding method based on lookup table in CMMB (China Mobile Multimedia Broadcasting)
CN102891688B (en) * 2012-10-12 2015-08-19 同济大学 A stochastic code construction method of mapping
CN102932008B (en) * 2012-11-21 2015-11-18 苏州威士达信息科技有限公司 Parallel encoding method based on a lookup table deep space communications qc-ldpc
CN102932010B (en) * 2012-11-21 2015-11-18 苏州威士达信息科技有限公司 Highly parallel encoders and encoding method code Qc-ldpc
CN102932009B (en) * 2012-11-21 2015-11-18 苏州威士达信息科技有限公司 Based on the lookup table dtmb parallel encoding method qc-ldpc
CN103117749B (en) * 2012-12-31 2016-02-10 中国科学院微电子研究所 Check matrix construction method and apparatus for encoding and decoding and low density parity check code
CN103117750B (en) * 2013-01-14 2016-02-24 天津大学 Error probability of the low density parity check code estimation method
CN103117751B (en) * 2013-02-28 2016-03-02 航天恒星科技有限公司 Ldpc decoding method
CN103346802B (en) * 2013-06-04 2014-12-31 上海华力创通半导体有限公司 Construction method for QC-LDPC code
CN103475378B (en) * 2013-09-09 2016-11-23 复旦大学 Suitable for optical communication, high-throughput coder ldpc
CN103475379B (en) * 2013-09-10 2016-02-24 电子科技大学 One kind of encoding method ldpc
DE102013218311B4 (en) * 2013-09-12 2015-05-13 Deutsches Zentrum für Luft- und Raumfahrt e.V. A method for restoring lost and- / or corrupted data
CN103532570B (en) * 2013-10-25 2016-12-07 重庆工程职业技术学院 Ldpc a quasi-random method and the convolutional code structure Encoder
US9264181B2 (en) 2013-12-30 2016-02-16 Industrial Technology Research Institute Communication system, method and receiver applicable thereto
WO2015109472A1 (en) * 2014-01-23 2015-07-30 华为技术有限公司 Decoding method and apparatus for system code
CN103795424B (en) * 2014-02-25 2017-06-16 清华大学 A communication method based on the qc-ldpc
CN103888225B (en) * 2014-04-17 2017-05-31 淮海工学院 A binary code method in a fountain delete channel
CN104980169A (en) * 2015-06-20 2015-10-14 荣成市鼎通电子信息科技有限公司 QC-LDPC encoder in highly parallel WPAN
BE629437A (en) 1962-04-02
JP3234130B2 (en) 1995-05-30 2001-12-04 三菱電機株式会社 Error correction code decoding method and a circuit using this method
FR2767940A1 (en) 1997-08-29 1999-03-05 Canon Kk Processes and devices for coding and decoding and apparatuses implementing them
JP2002529550A (en) 1998-11-11 2002-09-10 アクイジティオ ソチエタ ペル アツィオニ Use of the crosslinked hyaluronic acid and medicine
EP1487117B1 (en) * 1999-07-06 2016-09-07 Samsung Electronics Co., Ltd. Rate matching device and method for a data communication system
DE60033011D1 (en) 1999-09-27 2007-03-08 Koninkl Philips Electronics Nv Dividing a file for emulation of a data stream
WO2001058131A3 (en) 2000-02-03 2002-01-10 Edan Ayal Broadcast system
DE10009443A1 (en) 2000-02-29 2001-08-30 Philips Corp Intellectual Pty Receiver and method for detecting and decoding a DQPSK-modulated and channel-encoded receive signal
FR2837332A1 (en) 2002-03-15 2003-09-19 Thomson Licensing Sa Device and method of correction codes insertion errors and reconstructing data stream, and corresponding products
ES2459065T3 (en) 2002-06-11 2014-05-07 Digital Fountain, Inc. Code decoding chain reaction inactivation
EP1547382A4 (en) 2002-07-16 2013-10-30 Nokia Corp A method for random access and gradual picture refresh in video coding
EP1526659A4 (en) 2002-07-31 2010-12-01 Sharp Kk Data communication device, its intermittent communication method, program describing its method, and recording medium on which program is recorded
WO2004068715A3 (en) 2003-01-29 2004-11-25 Digital Fountain Inc Systems and processes for fast encoding of hamming codes
CA2535741C (en) 2003-10-14 2015-11-10 Matsushita Electric Industrial Co., Ltd. Data converter and method thereof
US20060093634A1 (en) 2004-04-23 2006-05-04 Lonza Inc. Personal care compositions and concentrates for making the same
WO2006020826A3 (en) 2004-08-11 2007-08-02 Digital Fountain Inc Method and apparatus for fast encoding of data symbols according to half-weight codes
JP4950206B2 (en) 2005-10-11 2012-06-13 ノキア コーポレイション System and method for efficient scalable stream adaptation
RU2409910C2 (en) 2006-01-11 2011-01-20 Нокиа Корпорейшн Backward-compatible aggregation of images in scalable video coding
WO2007127741A3 (en) 2006-04-24 2009-04-16 Andreas Bechtolsheim Media server system
US20080058958A1 (en) 2006-06-09 2008-03-06 Chia Pao Cheng Knee joint with retention and cushion structures
KR101089072B1 (en) 2006-11-14 2011-12-09 퀄컴 인코포레이티드 Systems and methods for channel switching
US20100011274A1 (en) 2008-06-12 2010-01-14 Qualcomm Incorporated Hypothetical fec decoder and signalling for decoding control
CN104780385B (en) 2009-01-29 2018-01-16 杜比实验室特许公司 A video device, means sequences encoding multi-view frame is used bitstream
US8812735B2 (en) 2009-10-15 2014-08-19 Sony Corporation Content reproduction system, content reproduction apparatus, program, content reproduction method, and providing content server
WO2004034589A2 (en) 2004-04-22 application
EP2357732A1 (en) 2011-08-17 application
WO2004034589A3 (en) 2004-06-10 application
KR101143282B1 (en) 2012-05-08 grant
US20090189792A1 (en) 2009-07-30 application
US7532132B2 (en) 2009-05-12 grant
US20040075593A1 (en) 2004-04-22 application
US6909383B2 (en) 2005-06-21 grant
CN1717871A (en) 2006-01-04 application
EP1552617A2 (en) 2005-07-13 application
USRE43741E1 (en) 2012-10-16 grant
JP2006502440A (en) 2006-01-19 application
KR20050059238A (en) 2005-06-17 application
EP2357731A1 (en) 2011-08-17 application
JP4546246B2 (en) 2010-09-15 grant
JP2013156644A (en) 2013-08-15 application
US9236885B2 (en) 2016-01-12 grant
JP2010239625A (en) 2010-10-21 application
EP2348640A1 (en) 2011-07-27 application
JP5675876B2 (en) 2015-02-25 grant
EP2355360A1 (en) 2011-08-10 application
US7394407B2 (en) 2008-07-01 grant
US20080180285A1 (en) 2008-07-31 application
US20050242974A1 (en) 2005-11-03 application
JP5485008B2 (en) 2014-05-07 grant
CN100539439C (en) 2009-09-09 grant
WO2006135878A2 (en) 2006-12-21 In-place transformations with applications to encoding and decoding various classes of codes
Free format text: PAGES 1/25-25/25, DRAWINGS, REPLACED BY NEW PAGES 1/17-17/17; DUE TO LATE TRANSMITTAL BY THE RECEIVING OFFICE
Ref document number: 1020057005861
Ref document number: 2004543067
Ref document number: 2003808111
Ref document number: 20038A43076
2009-10-15 DPE2 Request for preliminary examination filed before expiration of 19th month from priority date (pct application filed from 20040101)