Skew-Feedback Shift-Register Synthesis and Decoding Interleaved Gabidulin Codes
An efficient algorithm which synthesizes all shortest skew-feedback shift-registers (defined in the paper) generating L sequences 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 complexity O(LN(2)), where N is 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 Kotter and Kschischang, can be used for random network coding.
skew-feedback shift-register synthesis decoding gabidulin codes direct sum of codes interleaved codes linearized-feedback multiple sequences rank-distance