Complexity Comparison of the Use of Vandermonde versus Hankel Matrices to Build Systematic MDS Reed-Solomon Codes

International audienceReed Solomon RS(n, k) codes are Maximum Distance Sep- arable (MDS) ideal codes that can be put into a systematic form, which makes them well suited to many situations. In this work we consider use-cases that rely on a software RS codec and for which the code is not fixed. This means that the application potentially uses a different RS(n,k) code each time, and this code needs to be built dynamically. A light- weight code creation scheme is therefore highly desirable, otherwise this stage would negatively impact the encoding and decoding times. Constructing such an RS code is equivalent to construct- ing its systematic generator matrix. Using the classic Vander- monde matrix approach to that purpose is feasible but adds significant complexity. In this paper we propose an alternative solution, based on Hankel matrices as the base matrix. We prove theoretically and experimentally that the code construc- tion time and the number of operations performed to build the target RS code are largely in favor of the Hankel approach, which can be between 3.5 to 157 times faster than the Van- dermonde approach, depending on the (n, k) parameters