Online codes

Online codes

In computer science, online codes are an example of rateless 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). Rateless codes produce an arbitrarily large number of symbols which can be broadcast until the receivers have enough symbols.

High level view of the use of Online codes

The online encoding algorithm consists of several phases. First the message is split into n fixed size message blocks. Then the outer encoding is an erasure code which 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.

Contents

Detailed Discussion

Online codes are parameterised by the block size and two scalars, 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)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-randomly choose q auxiliary blocks (from a total of 0.55qε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

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:

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\le i\le 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 currently decode. A check block can only be decoded when all but one of the blocks which is it 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 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.

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Codes and Keys — Studio album by Death Cab for Cutie Released May 31, 2 …   Wikipedia

  • Online Mendelian Inheritance in Man — (OMIM) is a database that catalogues all the known diseases with a genetic component, and when possible links them to the relevant genes in the human genome and provides references for further research and tools for genomic analysis of a… …   Wikipedia

  • Online shopping — is the process whereby consumers directly buy goods or services from a seller in real time, without an intermediary service, over the Internet. It is a form of electronic commerce. An online shop, eshop, e store, Internet shop, webshop, webstore …   Wikipedia

  • Online ethnography — refers to a number of related online research methods that adapt ethnographic methods to the study of the communities and cultures created through computer mediated social interaction. As modifications of the term ethnography, online ethnography… …   Wikipedia

  • Online fax — Online faxing (also known as Internet fax, digital fax and e fax) utilizes an online fax service provider to convert a fax transmission into file that can be received via email or a fax machine.[1] Online fax services bridge the gap between the… …   Wikipedia

  • Codes postaux — Code postal Le code postal est un ensemble court de chiffres et/ou de lettres, utilisé par les entreprises postales afin de simplifier et d accélérer l acheminement du courrier. Sa forme varie selon les pays mais il représente le plus souvent une …   Wikipédia en Français

  • Online judge — An online judge is an online system to test programs in programming contests. They are also used to practice for such contests. Many of these systems organize their own contests. The system can compile and execute codes, and test them with pre… …   Wikipedia

  • Online-Ticket — Ein Online Ticket der Deutschen Bahn. Das Zertifikat befindet sich in der ersten Zeile rechts oben unterhalb des Aztec Codes. Ein Online Ticket ist eine Eintritts oder Fahrkarte, die auf elektronischem Wege (meistens über das Internet) erworben… …   Deutsch Wikipedia

  • Online-Beratung gegen Rechtsextremismus — Logo der Online Beratung gegen Rechtsextremismus Die Online Beratung gegen Rechtsextremismus ist eine anonym nutzbare Internet Anlaufstelle für Menschen, die direkt oder indirekt mit rechtsextremen Denken, Auftreten oder Gewalt konfrontiert sind …   Deutsch Wikipedia

  • Online-Kriminalität — Internetkriminalität sind Straftaten, die auf dem Internet basieren oder mit den Techniken des Internets geschehen. Inhaltsverzeichnis 1 Erscheinungsformen 2 Technischer Fortschritt 3 Situation in Deutschland 4 Steigende Gefahren …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”