Skew-Feedback Shift-Register Synthesis and Decoding Interleaved Gabidulin Codes
Vladimir R. Sidorenko, Lan Jiang, Martin Bossert · IEEE Transactions on Information Theory · 2011
An efficient algorithm which synthesizes all shortest skew-feedback shift-registers (defined in the paper) generatingLsequences of varying length over a field is derived and its correctness is proved. It generalizes the Berlekamp-Massey algorithm and some other algorithms, and has time complexityO(LN2), whereNis the length of a longest sequence. The proposed algorithm can be applied for efficiently solving the key equation when decoding interleaved (or direct sum of) Gabidulin codes beyond half minimum distance. Those codes have many applications and, as shown by Kötter and Kschischang, can be used for random network coding.