An XSLT linear feedback shift register

The  Linear Feedback Shift Register (LFSR) provides a simple yet very versatile solution for the generation of pseudo-random sequences of bits. This concept, can be efficiently emulated using XSLT 2.0 or 3.0, the sample show here uses XSLT 3.0 because it is quite neat to use a closure to maintain the state of the function that manipulates the shift-register.

The XSLT snippet below shows the low-level emulation of the shift-register. This takes a boolean sequence as an input argument which is then shifted right a single ‘bit’, the result of an XOR operation on the output bit (right-most bit) and bits at 2 tap points is then fed back to the left-most bit of the ‘register’.

                                      xsl:function>                  xsl:function>

Now that we have this low-level function, we need a way to maintain the state of the shift-register for each subsequent bit in the generated sequence. The approach I’ve taken is to use the following function that takes a bit sequence seed as an argument and returns an updated version of itself, along with the current output bit:

                xsl:function>

We can now use this function in any number of ways, but this example shows how xsl:iterate can be used to generate a specific number of bits:

                                                             xsl:next-iteration>        xsl:iterate>      xsl:function>

So, that is really all the XSLT we need to generate a pseudo-random sequence of bits. I have then just added some extra functionality to make the result more readable by showing bit-sequences a 8-bit words with ‘1’ and ‘0’ characters. The final complete test XSLT can be run against itself:

Input seed: 1011101101010111

Output sequence: