On Syndrome Decoding of Punctured Reed-Solomon and Gabidulin Codes

Punctured Reed-Solomon (RS) and Gabidulin (G) codes over the field F_q^m with locators from the subfield F_q can be represented as interleaving of m correspondent codes over the subfield F_q or can be considered as virtual interleaving of m correspondent codes over the field F_q^m. Using a probabilistic unique syndrome decoder, m-interleaved or virtually interleaved codes can be decoded up to the same radius mm+1(d−1), where d is the code distance in Hamming metric for RS codes and in rank metric for G codes. We show that the correspondent decoders over the subfield F_q and the field F_q^m are equivalent and conclude that in practice one should use a decoder over the subfield since it has less complexity.