Online codes

Upon receiving a certain number of check blocks some fraction of the composite message can be recovered.

Online codes are parameterised by the block size and two scalars, q and ε.

The inner encoding takes the composite message and generates a stream of check blocks.

The degree is determined by sampling a random distribution, p, which is defined as: Once the degree of the check block is known, the blocks from the composite message which it is attached to are chosen uniformly.

This climbs almost linearly at first as many check blocks with degree > 1 are received but unusable.

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.

High level view of the use of online codes
A graph of check blocks received against number of message blocks fixed for a 10000 block message.