An optimal partial decoding algorithm for rateless codes

Rateless codes are designed to decode all the input symbols when a certain number of coded symbols have been received. However, it is possible to recover a subset of the input symbols from the actually received coded symbols: this process is called partial decoding and the number of recovered input symbols is termed the intermediate performance of rateless codes. In this paper we study the problem of the optimality of the partial decoding process: we say that a partial decoding algorithm is optimal if, given a rateless code, it is able to maximize the intermediate performance of the code, i.e. it is able to retreive the maximum number of input symbols when a certain number n of coded symbols have been received, for every n. We propose OPD, an optimal partial decoding algorithm for any rateless code, proving its optimality. The proposed algorithm is finally used to analyze the intermediate performance of LT codes.