General Linearized Polynomial Interpolation and Its Applications

In this paper we propose a general interpolation algorithm in a free module of a linearized polynomial ring, and apply this algorithm to decode two families of subspace codes, Kotter-Kschischang (KK) codes and Mahdavifar-Vardy (MV) codes. When applied to decode KK codes, our algorithm is equivalent to the Sudan-style list-1 decoding algorithm proposed by Kotter and Kschischang. Our algorithm also obtains the multivariate linearized polynomial for the list decoding of MV codes, and has a much lower complexity than solving linear equations.