Systems and processes for decoding a chain reaction code through inactivation

In a decoder that receives multi-stage output symbols from a communication channel and is configured to decode a sequence of input symbols from received multi-stage output symbols wherein the input symbols represent source data conveyed in encoded form over the communication channel and wherein the multi-stage output symbols each comprise either an output symbol or a check symbol, a method of decoding comprising:

• storing a plurality of received multi-stage output symbols having been conveyed over the communication channel, each received multi-stage output symbol having a degree of one or more, wherein the degree of a multi-stage output symbol represents the number of input symbols with which a multi-stage output symbol is associated and the multi-stage output symbol being such that an unknown one of the input symbols associated with the multi-stage output symbol can be recovered from a value of the multi-stage output symbol and the values of a number, one less than the degree of the multi-stage output symbol, of other associated input symbols associated with the multi-stage output symbol;
• providing storage for a state for at least some, and more than two, input symbols, wherein the state for an input symbol is a value that can have at least an active value or an inactive value;
• processing multi-stage output symbols in a chain reaction process, wherein input symbols are recovered from multi-stage output symbols of degree one and multi-stage output symbols of degree greater than one that are associated with recovered input symbols have their degree reduced accordingly, thereby generating additional multi-stage output symbols of degree one that can be used to recover input symbols;
• determining if the chain reaction process would stall for lack of multi-stage output symbols of degree one to recover input symbols;
• modifying a state for at least one input symbol from the active value to the inactive value when the decoder determines in the step of determining that no multi-stage output symbols of degree one remain for input symbol recovery, thereby associating a reduced multi-stage output symbol degree of multi-stage output symbols associated with the inactivated input symbol;
• continuing processing of multi-stage output symbols in the chain reaction process using multi-stage output symbols having an associated reduced degree of one;
• and
• recovering the inactivated input symbols from associated multi-stage output symbols.

A computer program product, on a computer readable storage medium, for receiving output symbols from a communication channel and is configured to decode a sequence of source symbols from received output symbols, wherein the source symbols represent source data conveyed in encoded form over the communication channel, the computer program product comprising:

• instruction code for storing a plurality of received output symbols having been conveyed over the communication channel, each received output symbol having a degree of one or more, wherein the degree of an output symbol represents the number of source symbols with which an output symbol is associated and the output symbol being such that an unknown one of the source symbols associated with the output symbol can be recovered from a value of the output symbol and the values of a number, one less than the degree of the output symbol, of other associated source symbols associated with the output symbol;
• instruction code for providing storage for a state for at least some, and more than two, source symbols, wherein the state for a source symbol is a value that can have at least an active value or an inactive value;
• instruction code for processing output symbols in a chain reaction process, wherein source symbols are recovered from output symbols of degree one and output symbols of degree greater than one that are associated with recovered source symbols have their degree reduced accordingly, thereby generating additional output symbols of degree one that can be used to recover source symbols;
• instruction code for determining if the chain reaction process would stall for lack of output symbols of degree one to recover source symbols;
• instruction code for modifying a state for at least one source symbol from the active value to the inactive value when the decoder determines in the step of determining that no output symbols of degree one remain for source symbol recovery, thereby associating a reduced output symbol degree of output symbols associated with the inactivated source symbol;
• instruction code for continuing processing of output symbols in the chain reaction process using output symbols having an associated reduced degree of one;
• and
• instruction code for recovering the inactivated source symbols from associated output symbols.

A decoder configured to decode input symbols using received output symbols associated with the input symbols, the decoder comprises a processor that when executing instruction codes for decoding the input symbols using the output symbols performs operations, the operations comprising:

• determining a reception overhead number of a set of output symbols required to decode the input symbols, wherein the reception overhead number is greater than a predetermined decoding process failure threshold;
• for a set of the output symbols that contain a number of output symbols greater than the predetermined reception overhead number, separating the set of output symbols into a set of output symbols of degree one, and a set of output symbol of degree two or higher;
• processing the set of output symbols of degree one to recover the associated input symbols until there are no remaining output symbols of degree one;
• deactivating at least one active input symbol thereby transforming at least one output symbol of degree two to an output symbol having a degree of one;
• and
• recovering the input symbol associated with the transformed output symbol having the degree of one.