Editing Online codes (section)

==Detailed discussion==
Online codes are parameterised by the [[Block size (cryptography)|block size]] and two [[Scalar (mathematics)|scalar]]s, ''q'' and ''ε''. The authors suggest ''q''=3 and ε=0.01. These parameters set the balance between the complexity and performance of the encoding. A message of ''n'' blocks can be recovered, [[with high probability]], from (1+3ε)''n'' check blocks. The probability of failure is (ε/2)<sup>q+1</sup>.

===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-random]]ly choose ''q'' auxiliary blocks 
(from a total of 0.55''q''ε''n'' auxiliary 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===
[[Image:online_codes_time_against_blocks_graph.png|frame|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 the [[XOR]] of all the blocks from the composite message that it is attached to.

The ''degree'' of 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:

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

:<math>p_1=1-\frac{1+1/F}{1+\epsilon}</math>

:<math>p_i=\frac{(1-p_1)F}{(F-1)i(i-1)}</math> for <math>2\le i\le F</math>

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 currently [[wikt:decode|decode]]. 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 &gt; 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 received ''n'' check 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.