11682 - Shift Register
Moderator: Board moderators
-
- 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!
-
- 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)
I have the following working values:
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....
For input (3rd sample input case)
Code: Select all
7 3
0 2 3
4d 1a
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