The Tight Error Linear Complexity of Periodic Sequences

Based on linear complexity, k-error linear linear complexity, k-error linear complexity profile and minerror, the m-tight error linear complexity is presented to study the stability of the linear complexity of periodic sequences. The m-tight error linear complexity of sequence S is defined as a two tuple (k_m, LC_m), which is the mth jump point of the k-error linear complexity profile of sequence S. The Wei-Xiao-Chen algorithm can not be generalized into a k-error linear linear complexity algorithm as it does not have a Stamp-Martin pattern. By using error vectors, an efficient approach for computing m-tight error linear complexity of binary sequences with period 2ⁿp^m is given. One of our main contributions is to show that every fast algorithm for linear complexity can be generalized to a fast algorithm for m-tight error linear complexity for small m.