# Profile Complexity LFSR

I try to understand how Complexity of an LSFR calculated.

For example I have a bit sequence 110101 and it's profile 1 1 2 2 3 3.

Is there any easy way in order to produce the profile?

Given any $n-$bit sequence $(a_1,\ldots,a_n)$ with $a_k \in \{0,1\}$ you can use the Berlekamp Massey algorithm (which is conveniently recursive) to obtain minimal degree characteristic polynomials $C_m(X)$ where $C_m(X)$ is the output polynomial of Berlekamp Massey, when its input is $(a_0,\ldots,a_m)$ with $1\leq m\leq n.$

The linear complexity profile of $(a_1,\ldots,a_n)$ is simply the sequence $d_1,\ldots,d_n$ where $d_m$ is the degree of $C_m(X)$.

If you have $n=2^k,$ then there is a much faster algorithm to compute just $d_n$ due to Richard Games and Agnes Chan, the so-called Chan-Games algorithm, which of course can be used to obtain $d_1,d_2,d_{2^2},\ldots,d_{2^k}$ but not the complete profile. This has complexity $O(n \log n)$ while Berlekamp Massey has complexity $O(n^2).$

There are other fast algorithms for cases such as $n=m 2^k$ where $m$ is odd which use various generalisations of the coding theoretic result also known as Blahut's Theorem, which is that the linear complexity of a sequence is the Hamming weight of an appropriately defined and normalized finite fourier transform of the sequence.

• @JohnPapakostas, does this answer your question? – kodlu Nov 11 '15 at 19:31

One can use the Berlekamp-Massey algorithm