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?

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

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.

RIP PCW

$x >>= 1;
$x |= next_bit();
[download]

next_bit($x & 1);
$x <<= 1;
[download]

Update: Oops, ignore the above. I misunderstood what you wanted because I made some inferences based on what you said, but you don't seem to know what you were talking about either.

You don't feed bits into an LFSR. LFSRs output a long chain of non-repeating numbers. As such, they neither encode nor decode. They also neither encrypt nor decrypt.

You could potentially use the seemingly random sequence generated for encryption, but how you decrypt would depend on how you encrypt.

LFSRs CAN be used to encrypt sequences of bits - this is the basic algorithm used to generate CRCs (well nowadays, they are now often generated by looking up data in tables, data generated by the LFSR). When used to generate a sequence of pseudo random numbers, the state of the LFSR is based on the initial seed. The LSB of the next state is based on the XOR of data from all of the taps. When used to encode a bit sequence, the next bit of the sequence is also XOR'ed with the tap data to generate the LSB.

Except for the initial value of the register, there are no inputs (as shown by the code below). What bit sequence are you talking about when you say "When used to encode a bit sequence"?

use strict;
use warnings;

sub make_lfsr {
    my ($size, $taps, $seed) = @_;
    my $mask = 2**$size - 1;
    my @taps = grep $_, map $_-1, sort { $b <=> $a } (@$taps);
    my $r = $seed;
    return sub {
        my $bit = 0;
        $bit ^= ($r >> $_) & 1 for @taps;
        $r = (($r << 1) & $mask) | $bit;
    };
}

sub to_binary {
    my ($i, $size) = @_;
    return substr(unpack('B32', pack('N', $i)), -$size);
}

{
    my $size = 16;
    my @taps = (16, 14, 13, 11, 1);
    my $seed = 1;

    my $lfsr = make_lfsr($size, \@taps, $seed);

    for (;;) {
        my $r = $lfsr->();
        print(to_binary($r, $size), "\n");
        last if $r == $seed;
    }
}
[download]

Update: Added code