Tornado code: Difference between revisions

Revision as of 00:28, 5 December 2023

Revision as of 15:23, 25 June 2024

Line 1:

In [[coding theory]], '''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 [[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.

Line 21:

== Patent issues ==

Tornado codes were formerly patented inside the United States of America.<ref>{{harvnbsfn|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 have expired as of February 5, 2019, and September 17, 2019, respectively.

== Citations ==

[[Michael Luby]] created the Tornado codes.<ref>{{harvnbsfn|Luby|Mitzenmacher|Shokrollahi|Spielman|1997}}</ref><ref>{{harvnbsfn|Luby|Mitzenmacher|Shokrollahi|1998}}</ref>

== See also ==

Line 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 journal | refvauthors={{harvid|Luby|1997}} |M, author=[[MichaelMitzenmacher Luby|M., Luby]]Shokrollahi A, [[Spielman D, Stemann V |author-link1=Michael MitzenmacherLuby |M.author-link2=Michael Mitzenmacher]], [[|author-link3=Amin Shokrollahi|A. Shokrollahi]], [[|author-link4=Daniel Spielman|D. Spielman]], V. Stemann | title=Practical Loss-Resilient Codes | journal=Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing | pages=150–159 | year=1997}}

* {{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=Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms | pages=364–373 | year=1998}}

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

== External links ==