Page 1 of 1

### 11682 - Shift Register

Posted: Wed Sep 10, 2014 11:38 pm
Use this thread to discuss this problem.

### Re: 11682 - Shift Register

Posted: Sat Apr 09, 2016 2:09 am
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
--+---------------------------------
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
------------------------------------

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....