A Class of Rateless Reed-Solomon Codes With Near-Linear Computational Complexities

This paper proposes a class of rateless Reed-Solomon (RLRS) codes with near-linear encoding/decoding complexities. Like fountain codes, the RLRS codes can generate a reasonably large number of encoded packets in packet-level transmissions. Furthermore, the RLRS codes are maximum distance separable (MDS) codes that always maintain zero reception overhead. In the proposed RLRS codes, the preservative field extensions are realized through Cantor’s field tower, which avoids searching some quadratic irreducible polynomials as in the prior RLRS codes based on Cauchy generator matrices. Additionally, the proposed RLRS codes are based on Vandermonde generator matrices, whereby the LCH transforms, a variant of fast Fourier transforms (FFTs) over binary extension fields, can be employed to reduce the encoding/decoding complexity. To further improve computational efficiency, this paper also proposes a scheduling scheme for the LCH transforms to generate encoded packets on demand, instead of generating packets whose number must be a power of two. Analysis shows that compared to the prior approach, the used field tower leads to a lower speed of computational complexity growth caused by field extensions. In addition, with the total number of source packets to be transmitted being <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> , analysis shows that the proposed RLRS codes have the encoding/decoding complexity <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i> (log <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> ) per source packet, superior to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i> ( <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> ) in the prior approach.