Instead of modulo 2, Alice have a LFSR works with modulo 3.

Question: Instead of modulo 2, Alice have a LFSR works with modulo 3. The formula of this LFSR is X_{n+3} = X_n + 2X_{n+1}+2X_{n+2} (mod 3), where the initial values are X0=0, X1=1, X2=2.
(a) Compute first 20 outputs (including X0, X1 and X2) of the above LFSR.
(b) What is the period? What is the largest period of a LFSR with 3 registers under modulo 3?

Solution: (a) the output for (a) 01202011121100120201.

(b) Clearly from part a) output is

01202011121100120201
X0X1X2x3X4X5X6X7X8X9X10X11X12X13X14X15X16X17X18X19

So, clearly after X12 value starts repeating
X13=X0, X14=X1,X15=X2
So, period = 13 (number of steps from X0 to X12)
Maximum period = 3^n -1 (where n=3 since 3 register)
Maximum period = 3^3 -1 =26

Leave a Reply

Your email address will not be published. Required fields are marked *