Error-Erasure Decoding of Linearized Reed-Solomon Codes in the Sum-Rank Metric
Felicitas Hörmann, Hannes Bartz, Sven Puchinger · 2022 IEEE International Symposium on Information Theory (ISIT) · 2022
Codes in the sum-rank metric have various applications in error control for multishot network coding, distributed storage and code-based cryptography. Linearized Reed-Solomon (LRS) codes contain Reed-Solomon and Gabidulin codes as subclasses and fulfill the Singleton-like bound in the sum-rank metric with equality. We propose the first known error-erasure decoder for LRS codes to unleash their full potential for multishot network coding by incorporating erasures into the known syndrome-based Berlekamp-Massey-like decoder. This allows to correct tFfull errors, tRrow erasures and tCcolumn erasures up to $2{t_F} + {t_R} + {t_C} \leq n - k$ in the sum-rank metric requiring at most $\mathcal{O}\left( {{n^2}} \right)$ operations in ${\mathbb{F}_{{q^m}}},$ where n is the code’s length and k its dimension. We show how the proposed decoder can be used to correct errors in the sum-subspace metric that occur in (noncoherent) multishot network coding.