Performance—complexity tradeoffs of rateless codes

We analyze performance-complexity tradeoffs of rateless codes over noisy symmetric channels. Unlike in erasure channels, the decoder for such codes needs to use all received symbols in noisy channels because each of them have some information about the transmitted message. To reduce the complexity, the receiver can discard some unreliable symbols, but it must receive more symbols due to the lost information. This results in a performance-complexity tradeoff. We also consider another scenario where a rateless code is concatenated with a fixed-rate code, which is typically used in practice, e.g., in [1]. The fixed-rate code provides a soft-decision decoding and only correctly decoded blocks are used in the rateless code decoder. If some soft information of error-detected blocks is also used, the receiver can decode the message with less received symbols at the expense of increased processing. This results in another type of performance-complexity tradeoff. For these scenarios, we find the optimal tradeoffs and show sub-optimal tradeoffs achievable by practical rateless codes.