## 11682 - Shift Register

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### 11682 - Shift Register

Use this thread to discuss this problem.
Check input and AC output for thousands of problems on uDebug!

pointless0
New poster
Posts: 9
Joined: Wed Jan 13, 2016 3:24 am

### Re: 11682 - Shift Register

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