2015/10/15 by Puchinger, Sven, Nielsen, Johan Rosenkilde né, Li, Wenhui +1
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1510.04728
We show that decoding of ℓ-Interleaved Gabidulin codes, as well as list-ℓ decoding of Mahdavifar--Vardy codes can be performed by row reducing skew polynomial matrices. Inspired by row reduction of \F[x] matrices, we develop a general and flexible approach of transforming matrices over skew polynomial rings into a certain reduced form. We apply this to solve generalised shift register problems over skew polynomial rings which occur in decoding ℓ-Interleaved Gabidulin codes. We obtain an algorithm with complexity O(ℓ μ2) where μ measures the size of the input problem and is proportional to the code length n in the case of decoding. Further, we show how to perform the interpolation step of list-ℓ-decoding Mahdavifar--Vardy codes in complexity O(ℓ n2), where n is the number of interpolation constraints.