in reply to LFSRs & binary encode / decode functions

in: 
$x >>= 1;
$x |= next_bit();

[download]
out: 
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.

Replies are listed 'Best First'.
Re^2: LFSRs & binary encode / decode functions
by Anonymous Monk on Jul 03, 2009 at 02:34 UTC
    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.
[reply]

      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

[reply]
[d/l]

In Section Seekers of Perl Wisdom