You are here

Online codes (Extended Abstract)

TitleOnline codes (Extended Abstract)
Publication TypeMiscellaneous
Year of Publication2002
AuthorsMaymounkov, P
Keywordscoding theory, local encodability, rateless-ness, sparse bipartite graphs
Abstract

We introduce online codes – a class of near-optimal codes for a very general loss channel which we call the free channel. Online codes are linear encoding/decoding time codes, based on sparse bipartite graphs, similar to Tornado codes, with a couple of novel properties: local encodability and rateless-ness. Local encodability is the property that each block of the encoding of a message can be computed independently from the others in constant time. This also implies that each encoding block is only dependent on a constant-sized part of the message and a few preprocessed bits. Rateless-ness is the property that each message has an encoding of practically infinite size. We argue that rateless codes are more appropriate than fixed-rate codes for most situations where erasure codes were considered a solution. Furthermore, rateless codes meet new areas of application, where they are not replaceable by fixed-rate codes. One such area is information dispersal over peer-to-peer networks.

URLhttp://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.1333
AttachmentSize
PDF icon 10.1.1.112.1333.pdf213.03 KB