Patent ID: 7030785
Filing Date: 2006-04-18
Classification: H03M

Abstract:
1. In a decoder that receives output symbols from a communication channel and is configured to decode a sequence of input symbols from received output symbols wherein the input symbols represent source data conveyed in encoded form over the communication channel, a method of decoding comprising: 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 input symbols with which an output symbol is associated and the output symbol being such that an unknown one of the input 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 input symbols associated with the 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 output symbols in a chain reaction process, wherein input symbols are recovered from output symbols of degree one and output symbols of degree greater than one that are associated with recovered input symbols have their degree reduced accordingly, thereby generating additional output symbols of degree one that can be used to recover input symbols; determining if the chain reaction process would stall for lack of 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 output symbols of degree one remain for input symbol recovery, thereby associating a reduced output symbol degree of output symbols associated with the inactivated input symbol; continuing processing of output symbols in the chain reaction process using output symbols having an associated reduced degree of one; and recovering the inactivated input symbols from associated output symbols.