Tornado code: Difference between revisions

Revision as of 21:48, 4 June 2016

Latest revision as of 10:47, 23 April 2025

(16 intermediate revisions by 13 users not shown)

Line 1:

In [[computercoding sciencetheory]], '''Tornado codes''' are a class of [[erasure code]]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> {{sfn|Byers|Luby|Mitzenmacher|Rege|1998}} Since the introduction of Tornado codes, many other similar erasure codes have emerged, most notably [[Online codes]], [[LT codes]] and [[Raptor codes]].

Tornado codes use a layered approach. All layers except the last use an [[Low-density parity-check code|LDPC]] error correction code, which is fast but has a chance of failure. The final layer uses a Reed–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.)

The number of recovery blocks is given by the user. Then the number of levels is determined along with the number of blocks in each level. The number in each level is determined by a factor B which is less than one. If there are N input blocks, the first recovery level has B*N blocks, the second has B*B*NB×B×N, the third has B*B*B*NB×B×B×N, and so on.

All levels of recovery except the final one use an LDPC, which works by xor (exclusive-or). Xor operates on binary values, 1s and 0s. A xor B is 1 if A and B have different values and 0 if A and B have the same values. If you are given result of (A xor B) and A, you can determine the value for B. (A xor B xor A = B) Similarly, if you are given result of (A xor B) and B, you can determine the value for A. This extends to multiple values, so given result of (A xor B xor C xor D) and any 3 of the values, the missing value can be recovered.

So the recovery blocks in level one are just the xor of some set of input blocks. Similarly, the recovery blocks in level two are each the xor of some set of blocks in level one. The blocks used in the xor are chosen randomly, without repetition. However, the ''number'' of blocks xor'ed to make a recovery block is chosen from a very specific distribution for each level.

Line 21:

== Patent issues ==

Tornado codes arewere formerly patented inside the United States of America.<ref>{{harvsfn|Mitzenmacher|2004}}</ref> Patents US6163870 A (filed Nov 6, 1997) and US 6081909 A (filed Nov 6, 1997) describe Tornado codes, and have expired as of November 6, 2017. Patents US6307487 B1 (filed Feb 5, 1999) and US6320520 B1 (filed Sep 17, 1999) also mention Tornado codes., and Patentshave areexpired currentlyas validof untilFebruary 205, years2019, afterand September 17, 2019, filingrespectively.

== Citations ==

[[Michael Luby]] created the Tornado codes.<ref>{{harvsfn|Luby|Mitzenmacher|Shokrollahi|Spielman|1997}}</ref><ref>{{harvsfn|Luby|Mitzenmacher|Shokrollahi|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].

== See also ==

* [[Erasure code]]

* [[Raptor code]]

[[Erasure code]]

== Notes ==

Line 39 ⟶ 34:

== References ==

* {{cite conference |vauthors=Byers JW, Luby M, Mitzenmacher M, Rege A |date=October 1998 |title=A digital fountain approach to reliable distribution of bulk data |book-title=SIGCOMM '98: Proceedings |conference=ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication |pages=56–67 |doi=10.1145/285237.285258 |doi-access=free}}

* {{cite journal | ref={{harvid|Mitzenmacher|2004}} | author=[[Michael Mitzenmacher|M. Mitzenmacher]] | title=Digital Fountains: A Survey and Look Forward | journal=Proc. 2004 [[IEEE]] Information Theory Workshop (ITW) | year=2004}}

* {{cite journalbook | refvauthors={{harvid|Luby|1997}} | author=[[Michael Luby|M. Luby]], [[Michael Mitzenmacher|M. Mitzenmacher]]M, Shokrollahi [[Amin Shokrollahi|A. Shokrollahi]], [[DanielSpielman Spielman|D. Spielman]] , Stemann V. Stemann|chapter=Practical loss-resilient codes |author-link1=Michael titleLuby |author-link2=PracticalMichael LossMitzenmacher |author-Resilientlink3=Amin CodesShokrollahi |author-link4=Daniel journalSpielman |title=Proceedings of the twenty-ninth annual [[Association for Computing Machinery|ACM]] symposium on Theory of computing ([[- STOC]]) |'97 |pages=150–159 | year=1997|doi=10.1145/258533.258573 |isbn=0-89791-888-6 }}

* {{cite journal | refvauthors={{harvid|Luby|1998}} |M, Mitzenmacher M, Shokrollahi A |author-link1=[[Michael Luby |M. Luby]], [[author-link2=Michael Mitzenmacher |M. Mitzenmacher]], [[author-link3=Amin Shokrollahi|A. Shokrollahi]] | title=Analysis of Random Processes via And-Or Tree Evaluation | journal=Proc.Proceedings of the 9th Annual [[Association for Computing Machinery|ACM]]-SIAM Symposium on Discrete Algorithms | pages=364–373 | year=1998}}

* {{cite book |vauthors=Mitzenmacher M |chapter=Digital fountains: A survey and look forward |author-link=Michael Mitzenmacher |title=Manufacturing Engineer |year=2004|pages=271–276 |doi=10.1109/ITW.2004.1405313 |isbn=0-7803-8720-1 }}

== External links ==

A readable description from CMU (PostScript) [httphttps://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].

[[Category:Coding theory]]