2
$\begingroup$

Linear complexity of a sequence $s_0,s_1,\ldots$ over a finite field is the shortest length $n$ of linear recurrence of the sequence such that $s_{n+j}=\sum_{i=0}^{n-1}a_is_{i+j}$ for $j=0,1,2,\ldots$ for constants $a_i$ in the field. My question is at which $n$ should we stop computing $a_i$? Assuming the sequence is periodic with period $N$ at which $n$ should we stop the search for the coefficients in the recurrence relation above so that the relation will be valid for all subsequent longer sequences until the full period?

The definition doesn't seem to give any clear idea of the computation of linear complexity. Even the Berlekamp Massey algorithm doesn't say at what $n$ less than $N$ to stop.

$\endgroup$
2
$\begingroup$

My question is at which $n$ should we stop computing $a_i$? Assuming the sequence is periodic with period $N$ at which n should we stop the search for the coefficients in the recurrence relation above so that the relation will be valid for all subsequent longer sequences until the full period?

If the sequence is periodic then the linear complexity of the sequence will not change after some point. Remember, an LFSR with length $L$ can produce a periodic sequence at most length $2^L-1$ if the minimal polynomial is maximal.

But the Berlakamp-Massay algorithm cannot detect the period, it must process all inputs. It works interactively such that it updates the internals if a new bit cannot match the output, i.e. there is a discrepancy. Once the period is reached it will not update the internals but the algorithm can only be modified to output the last modified internal distance.

If you know the period, you can stop the Berlakamp-Massay after processing $N$ bits. The reason can be seen as in the next extreme example. Consider the periodic sequence where in the period it has 99-zero followed by 1.

$$\overbrace{\underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}}^{\text{ the preiod}}\, \underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}\cdots \underbrace{\texttt{000}\cdots\texttt{000}}_{99 \text{ times}}\texttt{1}\cdots$$

The linear complexity of this sequence is 100. Therefore you have to process all of the period to find the linear complexity of the sequence.

The definition doesn't seem to give any clear idea of computation of linear complexity. Even the Berlekamp Massey algorithm doesn't say at what $n$ less than $N$ to stop

Because it is designed to produce the LFSR that produces the given sequence, nothing more. As said before it must process all of the inputs.

If you want to find the period use period finding algorithm like Z-algorithm

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.