On the Concatenation of Non-Binary Random Linear Fountain Codes with Maximum Distance Separable Codes

Abstract

The performance of a novel fountain coding scheme based on maximum distance separable (MDS) codes constructed over Galois fields of order q is investigated. Upper and lower bounds on the decoding failure probability under maximum likelihood decoding are developed. Differently from Raptor codes (which are based on a serial concatenation a high-rate outer block code, and an inner Luby-transform code), the proposed coding scheme can be seen as a parallel concatenation of an outer MDS code and an inner random linear fountain code, both operating on the same Galois field. A performance assessment is performed on the gain provided by MDS based fountain coding over linear random fountain coding in terms of decoding failure probability vs. overhead. It is shown how, for example, the concatenation of a (15,10) Reed-Solomon code and a linear random fountain code over F16 brings to a decoding failure probability 4 orders of magnitude lower than the linear random fountain code for the same overhead in a channel with a packet loss probability of epsilon=5*10^{-2}. Moreover, it is illustrated how the performance of the concatenated fountain code approaches that of an idealized fountain code for higher-order Galois fields and moderate packet loss probabilities. The scheme introduced is of special interest for the distribution of data using small block sizes.