ON THE COMPUTATION OF THE NON-PERIODIC AUTOCORRELATION FUNCTION OF TWO TERNARY SEQUENCES AND ITS RELATED COMPLEXITY ANALYSIS
Christos Koukouvinos, Dimitris E. Simos · Journal of applied mathematics & informatics · 2011
We establish a new formalism of the non-periodic autocorrelation function (NPAF) of two sequences, which is suitable for the computation of the NPAF of any two sequences. It is shown, that this encoding of NPAF is efficient for sequences of small weight. In particular, the check for two sequences of length n having weight w to have zero NPAF can be decided in . For n > , the complexity is O(n) thus we cannot expect asymptotically faster algorithms.