11682 - Shift Register

[brianfry713]

Use this thread to discuss this problem.

[pointless0]

If anyone could clarify how totally off base this approach is, that would be great... I am attempting to solve this using baby step, giant step. Being my first attempt at solving a LFSR, I am very likely failing to model the problem correctly.

For input (3rd sample input case)

Code: Select all

7 3
0 2 3
4d 1a

I have the following working values:

Code: Select all

m = ceil(sqrt(2**7))
              Source: 00000000000000000000000001001101
              Target: 00000000000000000000000000011010
        Mask of Taps: 00000000000000000000000000001101
--+---------------------------------
i | LFSR Transformation(i)
--+---------------------------------
 0| 00000000000000000000000001001101
 1| 00000000000000000000000001100110
 2| 00000000000000000000000001110011
 3| 00000000000000000000000001111001
 4| 00000000000000000000000000111100
 5| 00000000000000000000000000011110
 6| 00000000000000000000000000001111
 7| 00000000000000000000000001000111
 8| 00000000000000000000000000100011
 9| 00000000000000000000000001010001
10| 00000000000000000000000001101000
11| 00000000000000000000000001110100
12| 00000000000000000000000001111010
------------------------------------

Inverse Mask of Taps: 00000000000000000000000001000110
i | Inverse LFSR Transformation(i)
--+---------------------------------
 0| 00000000000000000000000001001101
 1| 00000000000000000000000000011010
 2| 00000000000000000000000000110101
 3| 00000000000000000000000001101011
 4| 00000000000000000000000001010110
 5| 00000000000000000000000000101101
 6| 00000000000000000000000001011011
 7| 00000000000000000000000000110110
 8| 00000000000000000000000001101100
 9| 00000000000000000000000001011000
10| 00000000000000000000000000110001
11| 00000000000000000000000001100010
12| 00000000000000000000000001000100
------------------------------------

i | Trial multiplications and table search
--+---------------------------------
 0| 00000000000000000000000000011010
 1| 00000000000000000000000001101000 <- matches #10 in LFSR table

Result = 10 + i * 12 = 22

The sample output is 61 != 22. Am I formulating the problem incorrectly? Perhaps I am merely wrecking a not so embarrassingly proper subset of everything? If nothing else, through busywork I have consoled myself by presenting a cogent summary to the void....