2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ @JohnPapakostas, does this answer your question? $\endgroup$ – kodlu Nov 11 '15 at 19:31
0
$\begingroup$

One can use the Berlekamp-Massey algorithm

|improve this answer|||||
$\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.