Online codes

Incomputer science,online codesare an example ofrateless erasure codes.These codes can encode a message into a number of symbols such that knowledge of any fraction of them allows one to recover the original message (with high probability).Ratelesscodes produce an arbitrarily large number of symbols which can be broadcast until the receivers have enough symbols.

High level view of the use ofonline codes

The online encodingalgorithmconsists of several phases. First the message is split intonfixed size message blocks. Then theouter encodingis anerasure codewhich produces auxiliary blocks that are appended to the message blocks to form a composite message.

From this the inner encoding generates check blocks. Upon receiving a certain number of check blocks some fraction of the composite message can be recovered. Once enough has been recovered the outer decoding can be used to recover the original message.

Detailed discussion

Online codes are parameterised by theblock sizeand twoscalars,qandε.The authors suggestq=3 and ε=0.01. These parameters set the balance between the complexity and performance of the encoding. A message ofnblocks can be recovered,with high probability,from (1+3ε)ncheck blocks. The probability of failure is (ε/2)^q+1.

Outer encoding

Any erasure code may be used as the outer encoding, but the author of online codes suggest the following.

For each message block,pseudo-randomlychooseqauxiliary blocks (from a total of 0.55qεnauxiliary blocks) to attach it to. Each auxiliary block is then the XOR of all the message blocks which have been attached to it.

Inner encoding

A graph of check blocks received against number of message blocks fixed for a 10000 block message.

The inner encoding takes the composite message and generates a stream of check blocks. A check block is theXORof all the blocks from the composite message that it is attached to.

Thedegreeof a check block is the number of blocks that it is attached to. The degree is determined by sampling a random distribution,p,which is defined as:

$F=\left\lceil {\frac {\ln(\epsilon ^{2}/4)}{\ln(1-\epsilon /2)}}\right\rceil$

$p_{1}=1-{\frac {1+1/F}{1+\epsilon }}$

$p_{i}={\frac {(1-p_{1})F}{(F-1)i(i-1)}}$for$2\leq i\leq F$

Once the degree of the check block is known, the blocks from the composite message which it is attached to are chosen uniformly.

Decoding

Obviously the decoder of the inner stage must hold check blocks which it cannot currentlydecode.A check block can only be decoded when all but one of the blocks which it is attached to are known. The graph to the left shows the progress of an inner decoder. The x-axis plots the number of check blocks received and the dashed line shows the number of check blocks which cannot currently be used. This climbs almost linearly at first as many check blocks with degree > 1 are received but unusable. At a certain point, some of the check blocks are suddenly usable, resolving more blocks which then causes more check blocks to be usable. Very quickly the whole file can be decoded.

As the graph also shows the inner decoder falls just shy of decoding everything for a little while after having receivedncheck blocks. The outer encoding ensures that a few elusive blocks from the inner decoder are not an issue, as the file can be recovered without them.

External links

• Original paper
• Rateless Codes and Big Downloads(A more accessible paper by the same author)
• Papers by Petar Maymounkov
• A Ruby project hosted at RubyForge containing a Ruby library for Online Coding