(16C) Linear Feedback Shift Registers

[wynen]

Here is a programm for an LFSR of any length (up to 64 bits) and any structure, such as this one for example.

   

The n XOR gates form an adder for n+1 1-bit numbers without carry. This means that the output of the last gate is 1 if the number of ones at the inputs is odd.

This leads to a very simple programm.

The WSIZE is set to the length of the shift register (in the example 8).
The "polynomial" is stored in register 0 (in the example 10111000 binary).
The value of the shift register is in register 1 (initial value not equal to zero).

A step in the shift register is thus calculated as follows:

Code:


45,1        RCL 1       Initial value of the shift register
45,0        RCL 0       
42,20       f AND       Input of the XOR registers
43,7        g #B        Number of bits set
42,B        f SR        If the number is odd, set the carry flag
45,1        RCL 1       
43,C        g RLC       Shift one bit left and set Bit 0 by the carry bit
44,1        STO 1       Store the new value of the shift register

For such problems, the HP-16C is exactly the right calculator.
Thank you for the inspiring thread and the stimulating article.

Hartmut