In our previous work we transformed the optimisation problem of finding the k-error linear complexity of a sequence into an optimisation problem in the DFT (Discrete Fourier Transform) domain, using Blahut's theorem. We then gave an approximation algorithm of polynomial complexity for the transformed problem by restricting the search space to error sequences whose DFT have period up to k. However, when applying the inverse transformation, the error vectors obtained are in general in an extension of the original field.#R##N##R##N#In the present paper we develop our previous approximation algorithm so that now it can be constrained to only obtain errors over the original field. Essentially, we give a polynomial approximation algorithm for the computation of the k-error linear complexity of a sequence. More precisely, the algorithm will find the optimum among a restricted set of errors over the original field. While this restricted search space is still exponential, the complexity of the algorithm is polynomial, O(N2 logN log logN).
['Ana Sălăgean', 'Alexandra Alecu']
An improved approximation algorithm for computing the k-error linear complexity of sequences using the discrete fourier transform