Fast skew-feedback shift-register synthesis

A skew-feedback shift-register is a generalization of a linear-feedback shift-register and can be applied in decoding (interleaved) Reed–Solomon codes or Gabidulin codes beyond half their code distance. A fast algorithm is proposed which synthesizes all shortest skew-feedback shift-registers generating L sequences of varying length over a field. For fixed L, the time complexity of the algorithm is ${{\mathcal O}(M(N) \log N)}$ operations, where N is the length of a longest sequence and M(N) is the complexity of the multiplication of two skew polynomials of maximum degree N.