2
$\begingroup$

Here is the question I am dealing with. I have some sort of a solution but I need more specific results. If someone can help I'd appreciate:

Given 3 maximum length (max period) LFSR's of lengths L1,L2,L3 which are clocked simultaneously and L1,L2,L3 are pairwise relatively prime. The output sequence is the output of the 1st or 3rd one depending on the output of the second one being 0 or 1, respectively.

1) If we pick only every fourth bit of the output sequence how does linear complexity(LC) and period change? What would they be in terms of the previous LC and Period?

2) What is the weightt of the sequence in one period?

Now here is my solution in short: First of all this is Geffe Generator and combining function is f(x1,x2,x3)=x2.x1+x2.x3 +x3$.

-Linear Complexity= LC= f(L1,L2,L3)=L2.L1+L2.L3 +L3. (since lengths are all relatively prime)

- Period = P = (2^L1 -1).(2^L2 -1).(2^L3 -1) (since they are of max period and relatively prime lengths i.e. Li's)

Now let's say the output sequence of the system is {a_n} = {a0,a1,a2,a3,...}

1) Picking up every fourth bit of the output sequence is the 4-decimation of the sequence starting from a3. Therefore 3 terms need to truncated before the decimation is taken into account. Decimation does not increase the LC but truncation makes LC at most LC+3. I solved this by considering the denominator of the generating function which is the connection polynomial whose degree gives the LC after all simplifications are done.

i.e. if new LC is L then:

L <= LC+3

But I don't know how to find the period in terms of the period of the unmodified system P. I could only say that, if the new period is T, then:

T<= (2^{L+3}-1)

Can anyone give a more specific bound for the new period which is in terms of the unmodified period P of the system?

2) for the weight of the function in a period : I checked the Truth Table of the function f. And it is balanced, thus weight must be: (2^{3-1})= 4. But how can I find the weight of the sequence in a period?

My idea is: in one period function takes all possible input values (x1,x2,x3) that is possible. ( as many as integer multiples of lengths.) Thus it must be the weight of the function multiplied by some integer? I am not sure of that one? Does anyone have an idea?

$\endgroup$
  • $\begingroup$ The equation for f is not standard with x2 selecting, but it's OK, no? $\endgroup$ – kodlu Aug 18 '18 at 12:39
  • $\begingroup$ equation is not the standard one but it's oki. my main problem was the period and linear complexity manipulations here. $\endgroup$ – esra Aug 18 '18 at 15:15
  • 1
    $\begingroup$ is the answer below satisfactory? $\endgroup$ – kodlu Oct 18 '18 at 6:03
1
$\begingroup$

If you pick every 4th term in the sequence, since the original period $P$ is $$ (2^{L_1}-1)(2^{L_2}-1)(2^{L_3}-1)=2^{L_1+L_2+L_3}-2^{L_1+L_2}-2^{L_1+L_3}-2^{L_2+L_3}+ \sum_{i=1}^3 2^{L_i}-1,$$ and relatively prime to 4, except for trivially small choices for the $L_i,$ you get a proper decimation and a reordering of the sequence. There is no truncation.

Thus $LC_{new} \leq LC_{old}.$ But note that each of the component maximal length sequences can be written as $\mathrm{tr}(c_i \alpha_i^t),$ where $\alpha_i$ is a primitive element in $GF(2^{L_i})$ and the constant $c_i$ from the same field is used to adjust the phase.

However, the trace map is linear under repeated squaring $$\mathrm{tr}(x)=\mathrm{tr}(x^2)=\mathrm{tr}(x^4),$$ (constant on cyclotomic cosets) and decimation by 4 is equivalent to taking the fourth power, so I contend that the linear complexity also stays the same.

In addition, the weight of the decimated sequence obviously doesn't change.

The weight of the original sequence will simply be $(P+1)/2,$ since the function is balanced and the all zero point $f(0,0,0)=0$ is missing from the truth table.

$\endgroup$
  • $\begingroup$ What I was thinking was that I omitted the first 3 terms and then starting from a3 I calculated the decimated sequence's generating function by using the 4th roots of unity in terms of the old generating funtion. if the old generating function is f(x) than the generating function for the truncated sequence is (f(x)-a0-a1.x-a2.x^2 )/x^3. So there is a x^3 factor at the denominator of the new generating function which makes it less than or equal to LC+3.Decimation itself alone does not increase the LC. But truncation does? I still don't get what to say about period in terms of the old one though $\endgroup$ – esra Aug 18 '18 at 18:09
  • $\begingroup$ Say period is 7, 4 is relatively prime to 7. So decimation gives the indices: 3,0,4,1,5,2,6,3,.. with period 7 $\endgroup$ – kodlu Aug 19 '18 at 1:24

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.