Maximum Length Linear Feedback Shift Registers
I first heard about Linear Feedback Shift Registers reading an interesting article by Eniko Fox about Memory Management in their custom VM named Bismuth.
LFSRs, in this case Galois LFSRs, can be used to generate streams of pseudo random numbers and have some interesting properties. Because they have a finite number of states they must eventually repeat. And with carefully choosen feedback functions, they can generate a so called Maximum Length Sequence.
Wikipedia: Maximum length sequences are bit sequences generated using maximal linear-feedback shift registers and are so called because they are periodic and reproduce every binary sequence except the zero vector, that can be represented by the shift registers (i.e., for length-m registers they produce a sequence of length 2^m - 1)
This youtube video (which is also linked on the blog post mentioned earlier) does a great job explaining how LFSRs work.
OpenTTD - The Tile Update Cycle (Linear Feedback Shift Registers)
So a 4bit LFSR will generate a
repeating pseudo random sequence of numbers between
1-15, exhausting all possible numbers, without repeating
any of them.
That's a pretty useful property in the context of GameAudio! One could use this to fully exhaust all possible sounds in an array of sound variations without repetition. Given that the array size is a power of two.
This seemed like a neat idea for a simple first Unreal Engine Metasound Node to have a stab at.
Before writing my own LFSR implementation, I did a quick search through the UE source, and lo and behold, there's of course a LFSR class in the depths of the Math headers.
This class also can output a value for the
all-zeros state of the LFSR. LFSRs cannot actually
represent this state, as that would break the LFSR. Neat!
So instead of just numbers between 1-15 in case of a
4bit sized LFSR, it outputs 0-15,
16 values in total, which is nice for array lookups, and
in my experience one often deals with asset numbers of sound
variations that are powers of two in GameAudio.
Unfortunately the member variable holding the start state of the LFSR
is private and cannot be initialized via the constructor. It defaults
to
1, and therefore the LFSR will always generate the
exact same pseudo random sequence.
NOTE: There is however a way to work around that, more on that later.
Finally, this LFSR implementation is "limited" to
2-12 bits, but that should suffice, as a 12 bit LFSR will
generate a 4095 long sequence, plus the added
0.
| bits | sequence length |
|---|---|
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
| ... | .. |
| 12 | 4096 |
With all that out of the way it is time to wrap it as a Metasound Node!
Navigating the Metasound C++ source was a bit challenging, but eventually things fell into place. I won't go into much detail here, the source code is linked at the end of the article.
The node requires the number of bits to be set, which will internally
get clamped between 2-12, and for each trigger will
output the next value of the LFSR.
So far so good, but since it's impossible to change the start state of this LFSR class, the node will create the exact same sequence of random numbers over and over again.
This could be useful, but maybe not ideal in context of picking random sounds from an array.
One simple way around that, is to just create a random number between
0 and the maximum length of the LFSR once before each
run, add it to the output, and take the modulo against the maximum
sequence length.
NOTE: Since the LFSR has an internal state, this node of course only works within Metasounds that are NOT setup as oneshots!
There a couple things that would improve this node, but require altering the LFSR class provided by Unreal or rolling your own.
- add a reset trigger that resets the internal state of the LFSR
- provide a different start state to generate a different sequence for each run through providing random start values
- a first trigger out
- an output value counter
- more?
For now, creating this simple Metasound node was a quick exercise to familiarize myself with the Metasound framework.
You can find the Node wrapped in a UE plugin on my github linked below. If you have any questions or ideas feel free to reach out via discord or drop me a mail.