We present Tornado codes, linear-time encodable and decodable erasure codes that can transmit over lossy channels at rates extremely close to capacity. The encoding and decoding algorithms for Tornado codes have fast and simple software implementations. Implementations of our algorithms are faster by orders of magnitude than the best software implementations of previous erasure codes.
Despite the simplicity of the encoding and decoding algorithms for Tornado codes, their design and analysis are mathematically intricate. The design requires the careful choice of a random irregular bipartite graph, where the structure of the irregular graph is extremely important. We model the progress of the decoding algorithm by a set of differential equations. The solution to these equations can then be expressed as polynomials in one variable with coefficients determined by the graph structure. Based on these polynomials, we design a graph structure that guarantees successful decoding with high probability.
Originally appeared in the Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 150--159, 1997.