[p2p-hackers] Efficient Decoding of Online / LT / Raptor codes

[Nick Johnson]

After reading papers on Digital Fountain codes, it occurs to me that 
the decoding process can be more efficient than described: All the 
papers describe decoding by looking for encoded nodes that consist of a 
single source node, marking that node as decoded, and subtracting it 
from all the other nodes that include it. However, it occurs to me that 
it should be possible to be more efficient than this: The order of 
encoded nodes can be decreased without starting with nodes consisting 
of a single source node.
As an example, if I have nodes consisting of:
1: A+B+C
2: A+B+D
3: C+D+E

Assuming my operator is commutative (eg, XOR), I can add 1 and 2 to get 
C+D, and add that to 3 to recover E. Obviously this only works with 
much efficiency if the operator you use to subtract is the same as the 
one you use to add, such as XOR.

Unfortunately, I don't know enough stats to figure out if this is worth 
it - is anyone able to show if it's worth the extra effort, or if the 
cases in which this is useful are rare?

-Nick Johnson