Decoding punctured Reed–Solomon codes up to the Singleton bound

Abstract:
We show that punctured Reed–Solomon codes can be decoded virtually up to the Singleton bound with computational complexity quadratic in the code length using our algorithm based on multi-sequence shift-register synthesis. Our decoder may fail, but the probability of a decoding failure can be made negligibly small. We compare our results with the ones of Guruswami-Rudra, who considered list decoding of Folded Reed-Solomon codes up to their distance.