Online codes (Extended Abstract). Maymounkov, P. 2002.
Online codes (Extended Abstract) [link]Paper  abstract   bibtex   
We introduce online codes \textendash 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.
@booklet {Maymounkov02onlinecodes,
	title = {Online codes (Extended Abstract)},
	year = {2002},
	abstract = {We introduce online codes {\textendash} 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.},
	keywords = {coding theory, local encodability, rateless-ness, sparse bipartite graphs},
	url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.1333},
	author = {Petar Maymounkov}
}

Downloads: 0