Tornado code: Difference between revisions

Revision as of 12:10, 24 December 2008

Revision as of 13:57, 25 December 2008

Line 1:

In [[computer science]], '''tornado codes''' are a class of [[erasure codes]] that support [[error correction]] and have fast encoding and decoding algorithms. Software-based implementations of tornado codes are about 100 times faster on small lengths and about 10,000 times faster on larger lengths than software-based [[Reed-Solomon]] erasure codes while having only slightly worse overhead.{{cnFact|date=December 2008}}

Tornado codes are fixed rate, near optimal erasure correcting codes that use sparse bipartite graphs to trade encoding and decoding speed for reception overhead. Since the introduction of Tornado codes, many other similar codes have emerged, most notably [[Online codes]], [[LT codes]] and [[Raptor codes]].

== Rough Overview ==

Line 23 ⟶ 22:

The subsets for each parity block are generated in a semi-random fashion. The algorithm assigned for each input block a number of parity blocks it will be present in. The algorithm also assigns for each parity block the number of input blocks that will be in it. Then randomly parity blocks with remaining slots are assigned input blocks with remaining slots. This is called a random degree-constrained bipartite graph. This method generates parity blocks with random subsets of input blocks with a specific distribution that allows the input file or message to be recovered with very high probability.

== Patent Issues ==

Tornado codes and many similar codes (LT codes, Online codes) are patented inside the United States of America and cannot be used without the patent holder's permission.

== Citations ==