Tornado code: Difference between revisions

Revision as of 11:49, 4 May 2012

Revision as of 11:53, 4 May 2012

Line 1:

In [[computer science]], '''Tornado codes''' are a class of [[erasure codescode]]s that support [[error correction]]. Tornado codes require a constant C more redundant blocks than the more data-efficient [[Reed–Solomon erasure code]]s, but are much faster to generate and can fix erasures faster. Software-based implementations of tornado codes are about 100 times faster on small lengths and about 10,000 times faster on larger lengths than Reed–Solomon erasure codes.<ref>A digital fountain approach to reliable distribution of bulk data. http://portal.acm.org/citation.cfm?id=285243.285258</ref> Since the introduction of Tornado codes, many other similar [[erasure code]]scodes have emerged, most notably [[Online codes]], [[LT codes]] and [[Raptor codes]].

Tornado codes use a layered approach. All layers except the last use an [[LDPC]] error correction code, which is fast but has a chance of failure. The final layer uses a Reed-SolomonReed–Solomon correction code, which is slower but is optimal in terms of failure recovery. Tornado codes dictates how many levels, how many recovery blocks in each level, and the distribution used to generate blocks for the non-final layers.

== Overview ==

The input data is divided into blocks. Blocks are sequences of bits that are all the same size. Recovery data uses the same block size as the input data. The erasure of a block (input or recovery) is detected by some other means. (For example, a block from disk does not pass a CRC check or a network packet with a given sequence number never arrived.)

Line 15 ⟶ 14:

Since xor is a fast operation and the recovery blocks are an xor of only a subset of the blocks in the input (or at a lower recovery level), the recovery blocks can be generated quickly.

The final level is a Reed-SolomonReed–Solomon code. Reed-SolomonReed–Solomon codes are optimal in terms of recovering from failures, but slow to generate and recover. Since each level has fewer blocks than the one before, the Reed-SolomonReed–Solomon code has a small number of recovery blocks to generate and to use in recovery. So, even though Reed-SolomonReed–Solomon is slow, it only has a small amount of data to handle.

During recovery, the Reed-SolomonReed–Solomon code is recovered first. This is guaranteed to work if the number of missing blocks in the next-to-final level is less than the present blocks in the final level.

Going lower, the LDPC (xor) recovery level can be used to recover the level beneath it ''with high probability'' if all the recovery blocks are present and the level beneath is missing at most C' fewer blocks than the recovery level. The algorithm for recovery is to find some recovery block that has only one of its generating set missing from the lower level. Then the xor of the recovery block with all of the blocks that are present is equal to the missing block.

== Patent issues ==

Tornado codes are patented inside the United States of America.<ref>{{harv|Mitzenmacher|2004}}</ref>

== Citations ==

[[Michael Luby]] created the Tornado codes.<ref>{{harv|Luby|1997}}</ref><ref>{{harv|Luby|1998}}</ref>

== External links ==

A readable description from CMU (PostScript) [http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/tornado.ps] and another from Luby at the [[International Computer Science Institute]] (PostScript) [http://www.icsi.berkeley.edu/~luby/PAPERS/tordig.ps].