Algebraic Decoding of Subspace and Rank-Metric Codes

Multivariate interpolation- and syndrome-based decoding schemes for subspace and rank-metric codes are presented and analyzed. The proposed interpolation-based decoding schemes allow to efficiently correct errors beyond the unique decoding region in the corresponding metric and can be used as a list or probabilistic unique decoder. Upper bounds on the average list size and the decoding failure probability of the presented decoding schemes are derived. Properties of minimal Gröbner bases for linearized polynomial modules are used to improve the decoding performance, to reduce the average list size and to reduce the computational complexity. It is shown how the linearized Kötter-Interpolation can be used to construct the required minimal Gröbner bases efficiently. Improved interpolation- and syndrome-based decoding schemes for interleaved subspace codes are presented that achieve the best known decoding region. An interpolation-based decoding scheme for folded subspace codes is proposed and analyzed. The presented subspace decoding schemes are compared with existing decoding algorithms with respect to different parameters and simulations.

An interpolation-based decoding scheme for folded Gabidulin codes, a variant of rank-metric codes, that improves upon existing schemes for high code rates is presented. The results are used to reduce the average list size of an existing decoding scheme that has an improved decoding performance for low-rate folded Gabidulin codes.