Cognitive Networks: Towards Self-Aware Networks

13.4. Traditional Erasure Codes

Traditional erasure codes are typically block codes with a fixed rate, i.e. K input packets are used to generate N output packets with N – K redundant packets and code rate K/N. For example, an (N, K) Reed–Solomon code [^[], ^[]] has the ideal property that if any K of the N transmitted packets are received then the original K packets can be recovered perfectly. But this code has the following limitations:

1. In a high loss channel, for a fixed value of N, the receiver may not receive K out of N packets. In order to recover original K packets, a retransmission is necessary causing duplicate reception of the previously received packets and thus decreasing the channel efficiency.

2. A more serious limitation is with respect to its encoding and decoding complexity. The reason is that, standard algorithms for encoding and decoding Reed–Solomon codes require quadratic time, which are too slow for even moderate values of K. One way to deal with this problem is to encode over small blocks of data. This approach reduces the total computation, but can significantly increase the number of packets that must be obtained before complete decoding.

Another code is a class of LDPC codes called Tornado codes. Tornado codes are a class of erasure-correcting codes that have linear encoding and decoding times in N. 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 ...