in reply to LFSRs & binary encode / decode functions

Isn't the point of a LFSR that it cannot be decoded?

Besides which, for 20-bit numbers there are only 1e6 mappings, so it would be easier and faster to set up a pair of lookup tables (One time pad): 

use List::Util qw[ shuffle ];;

@n = 1 .. 2**20;;
@encoded = shuffle @n;;

@encode{ @n } = @encoded;;
@decode{ @encoded } = @n;;

print total_size $_ for \( %encode, %decode );;
44036216
44068014

[download]

One-time pads are the safest encryption mechanism (used properly!), and < 100MB very easy to generate.

Of course, using them properly means never re-using them which can present an off-line storage problem, but an entire pad can be reduced to ~2.5MB. How many would you need?

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
RIP PCW

Replies are listed 'Best First'.
Re^2: LFSRs & binary encode / decode functions
by zardoz99 (Initiate) on Jul 03, 2009 at 02:04 UTC
    I should have mentioned (and have now updated my original post to include) the target of the algorithm is a microcontroller with very limited RAM & Flash. Large lookup tables are out of the question. As far as LFSRs being "undecodeable", read through the postings in the referenced link. I believe knowing the taps of the encode LFSR and the initial seed, there should be a (maybe not so trivial) mathematical algorithm that would decode the encoded bits. Mind you, I also believe in Santa, and that global warming is a myth. ;-)
[reply]

      In C or assembler, (or in Perl using pack) you can trivially reduce the size of the tables to 4MB instead of 40MB.

      With a little ingenuity, you could reduce that to 1MB by expoiting the fact that each 32-bit value has 12 'spare' bits in the simple packed encoding.

      Ie. For each of the 256k 32-bit values in a 1MB table, you reuse each 4 times: 

      ...
   0    1    2    3    4    5    6    7
0010 1100 1100 1001 1111 0000 0110 1101 
...

      [download]

      Say:

      1. input value 0 would be encoded as nybbles 0,1,2,3,4 of the 32-bit value at offset 0.
      2. input value 256k as nybbles 1, 2, 3, 5, 7.
      3. input value 512k as nybbles 0, 2, 4, 6, 7.
      4. input value 784k as nybbles 1, 3, 4, 5, 6.

      If you're really up against it you could get it down to a bare 73k by expoiting that there are 56 combinations of 5 nybbles in each 32-bit word.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]

In Section Seekers of Perl Wisdom