Complexity Analysis of The GAO Algorithm
Ning Chen, Zhiyuan Yan · SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems · 2007
In this paper, we investigate the complexity of the Gao algorithm for decoding Reed-Solomon (RS) codes. We study both direct and fast implementations of the Gao algorithm and compare their complexities to those of traditional syndrome-based decoding algorithms. Our results show that, regardless of the implementation, the Gao algorithm has higher complexity than syndrome-based decoding algorithms for high rate RS codes that are used in practice.