Fast Ecoding/Decoding Algorithms for Reed-Solomon Erasure Codes.
Sian-Jheng Lin, Wei‐Ho Chung, Yunghsiang Sam Han · 2014
In this paper, we present a practical algorithm for (n = 2r, k) systematic Reed-Solomon (RS) erasure codes over characteristic-2 finite fields F2r, r ∈ Z+. At first, we define a new transform over F2r and proposed a fast transform algorithm. Based on this transform, we then develop the encoding and erasure decoding algorithms for the (n = 2r, k) Reed-Solomon codes. Thanks to the efficiency of transform, the encoding can be completed in O(n log2(k)) finite field operations, and the erasure decoding in O(n log2(n)) finite field operations. To the best of our knowledge, this is the first approach supporting Reed-Solomon erasure codes over characteristic-2 finite fields to achieve a complexity of O(n log2(n)), in both additions and multiplications. It is worth noting that the proposed algorithm does not rely on finite field FFTs. Due to the small complexity leading factor and ease of implementation, the algorithms are advantageous in practical applications. I.