# How did the NES's RP2A03 noise generator produce 32k bit long sequences despite only being 15 bits wide?

The NES Ricoh RP2A03 has a noise channel amongst its 5 sound channels. My sources include the NesDEV wiki: https://www.nesdev.org/wiki/APU_Noise

To quote the wiki directly,

The shift register is 15 bits wide, with bits numbered 14 - 13 - 12 - 11 - 10 - 9 - 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - 0

When the timer clocks the shift register, the following actions occur in order:

Feedback is calculated as the exclusive-OR of bit 0 and one other bit: bit 6 if Mode flag is set, otherwise bit 1. The shift register is shifted right by one bit. Bit 14, the leftmost bit, is set to the feedback calculated earlier. This results in a pseudo-random bit sequence, 32767 steps long when Mode flag is clear, and randomly 93 or 31 steps long otherwise. (The particular 31- or 93-step sequence depends on where in the 32767-step sequence the shift register was when Mode flag was set)

From what I understand, LFSRs (Linear-Feedback Shift-Registers) are relatively simple PRNGs (Pseudo-Random Number Generators). Most PRNGs, including LSGs often try to maximize periodicity. That is, if my PRNG number was m bits wide, I could get at most 2^m possible numbers out of the PRNG before the numbers start cycling

Of course, this is a highly ideal situations, something as simple as a badly implemented LFSR or a poor starting seed could cause numbers cycles to appear far earlier than the 2^m count

Now, the wiki states that the PRNG sequence of the 2A03's noise channel is 32k bits wide. 32k is 2^15, implying that the NES 2A03 chip somehow manages to get the ideal maximum periodicity

How exactly does this happen? How does it not begin cycling way earlier? There is no way to programmatically set its seed; it starts with a seed of 1 on startup. There is no way to change that so you're stuck with one seed

Yet how does this seed somehow manage to produce the ideal 32k bit cycle every time?

• A 15-bit LFSR can either have two cycles that are 16,384 bits long, or it can have one cycle that is 32,767 bits long and another that would be one state long. Hardware may be designed to detect the "all bits clear" scenario so that it merges with the 32,767-state one. Commented Jul 22 at 17:21
• @supercat But how does it generate such ideal large numbers instead of cycling early like many PRNGs out there? The LFSR is as simple as PRNGs get right, weaker than even LCGs?
– Hash
Commented Jul 22 at 18:13
• Any given LFSR polynomial will have some characteristic set of cycles whose total length equals the total number of states. Three approaches for avoiding short cycles are: (1) Picking a polynomial with two cycles each with half the total states, (2) picking a polynomial that maps all zeroes or all ones to itself, and has a cycle that contains all other states, add logic to detect when the LFSR is in the single-state cycle and shifts in the opposite bit; (3) ensure that at power up at least one bit is forced to a state that isn't the single-state cycle. Commented Jul 22 at 19:33
• "Something as simple as a badly implemented LFSR or a poor starting seed could cause cycles to appear far earlier than 2^m" -- okay, so it doesn't use a badly implemented LFSR or a poor starting seed. Does that fully answer the question? If not, why not? Why is it surprising that, supposing it is possible to choose a good LFSR, the NES creators did so? Commented Jul 23 at 15:46
• Spot on, @DanielWagner. OP, your question is really saying that you're surprised that maximal length LFSRs exist. They do and have done for much longer than the RP2A03. But an internet search would have told you that and in far better detail than you'll ever get on these sites - why did you post a question here instead of doing easy research? Commented Jul 24 at 4:48

This is something that can be calculated from the mathematics of LFSRs.

We know from Tausworthe, Robert C. (April 1965). "Random Numbers Generated by Linear Recurrence Modulo Two" that if the feedback polynomial for an LFSR is primitive mod 2 in the field GF(2), then the LFSR will either be stuck at zero, or output a maximum length sequence. We also know from Neal Zierler, John Brillhart. (1968) "On primitive trinomials (Mod 2)" that x15 + xk + 1 is a primitive polynomial mod 2 in the field GF(2) if k is 1, 4 or 7.

The RP2A03 chose the feedback polynomial x15 + x1 + 1 when the Mode bit is clear, which fits the requirements from the papers above.

Thus, just knowing the mathematics of an LFSR, we're able to see without testing that as long as the seed value is not 0, the LFSR will generate a sequence of length 215 - 1 before repeating itself. This is almost certainly how the RP2A03 was designed - a trinomial is one of the simplest feedback polynomials for an LFSR (it's a single XOR gate in the XOR + shift design), and a literature search would have told the designers how to design an LFSR that is either stuck at 0, or one state short of maximal length. Any seed value other than 0 would put you somewhere on the maximum length sequence, and as it just has to sound like noise, 1 is as good a value as any other.

• Another point I just thought of: just as simple as gating the output of an LFSR to turn noise on and off would be gating the feedback term. If one forces the feedback to the state opposite the one produced when the XOR gate inputs are equal, and makes the opposite output state the active one, then even if the noise generator somehow hit the all-zeroes cycle, disabling it would force it into a good cycle. On the other hand, the fact that the shorter-cycle mode can start up on either of two cycles suggests Nintendo didn't use that approach. Commented Jul 23 at 14:47
• @supercat I suspect you're overthinking this. We know that an LFSR will get stuck at all-zeroes. We know that if you include a + 1 term in your polynomial, then the next state of any state with at least 1 bit set will have at least 1 bit set. These properties, along with maximal length LFSR polynomials, can be found by a literature search. The RP2A03's LFSR options all have the + 1 set; in addition, the default is known maximal length. Seed to non-zero, and you cannot have the all-zeroes cycle, which is the only property Ricoh/Nintendo needed to care about for noise. Commented Jul 24 at 13:26
• Seeding to anything requires logic. Holding one bit set whenever noise is disabled would be simpler in hardware than forcing the state of all of them. Commented Jul 24 at 14:33
• Resets have to set the register to a stable state - once you're doing that, it's only marginally more logic to set one bit and clear the rest, rather than clearing all of them. If you don't set it to a stable state, then you've potentially got high power draw through the register (with heat production), as the transistors in the SRAM cell could be in their linear region instead of in saturation. Commented Jul 24 at 16:29
• @SimonFarnsworth Depending on the implementation, all bits zero may be a valid state and all bits one might be the lock-up state. It depends on how the feedback is arranged, e.g. XOR or XNOR. Commented Jul 25 at 11:44

The chip uses the oldest trick in the book, Linear Feedback Shift Register (LFSR) configured as Pseudo-Random Number Generator (PRNG).

The feedback taps (polynomial) of the shift register is generally selected so that it results in a maximal length sequence of (2^N)-1 for an N-bit shift register, but as always, the length can be shorter too.

It basically means that a 15-bit register will shuffle between all 32767 possible 15-bit states except for the only one state that makes it lock up, the all bits zero state.

And thus if the noise output is one of the bits, it means that you get a sequence of 32767 bits that repeat over and over again.

For a good reference, see https://en.m.wikipedia.org/wiki/Linear-feedback_shift_register

There is some maths involved how to generate or verify when the feedback tap configuration (i.e. the polynomial) is such that the sequence results into a maximal length sequence : https://en.m.wikipedia.org/wiki/Primitive_polynomial_(field_theory)

Most sound chips use the same technique but may have different amount of bits in the shift register for a different length sequence, or may have equal amount of bits but different feedback taps, so the sequence length is 32767 bits but the sequences are different.

The point of the sequence being longest possible is not very intuitive from the point of mathematics as it involves GF(2) Galois fields, but the implementation is very simple to implement in binary logic or software.

Basically you can make a for loop that generates all numbers from 1 to 32767 in sequence, and then just shuffle or map them in a way that from each number you jump to some other number and make sure each number is used only once as jump source and jump target. Simply make an algorithm that shuffles the numbers so that from any number you can jump to the next number by using the algorithm.

The algorithm is, if topomost bit is on, shift left and xor with polynomial. Else just shift left. Figure out the polynomial or all of them that leads to maximal length sequence.

• While I understand it uses an LFSR, I don't get exactly how the LFSR maximizes its length. The last I tried implementing an LCG on C++, I was told that getting a high periodicity is hard enough, let alone getting the maximum possible periodicity/length Sure, the taps is set up so that it gets a maximum length. But why exactly is this possible? I can't seem to wrap my mind around why a particular setup of taps lets you maximize the length sequence
– Hash
Commented Jul 22 at 18:12
• The mathematics of LFSRs are that of GF(2); how familiar are you with polynomial division in finite fields? The key insight is that because you're taking the remainder of the LFSR content (treated as a polynomial) when divided by the feedback polynomial, if the feedback polynomial is primitive, it'll take a maximum number of repetitions before you get back to the original LFSR content. Commented Jul 22 at 19:36
• Using a polynomial that yields two cycles that each hit half of the possible states will mean one only hits about half as many states as when using a maximal-length sequence, but it avoids having to worry about the degenerate case. Commented Jul 22 at 21:09
• @Hash Many years ago I implemented an LFSR in C, and I'm pretty sure it only took a handful of attempts before finding a pattern of bits that gave a maximal cycle. Commented Jul 23 at 1:49
• @Hash if you're not familiar with this stuff, try playing with the multiplicative group of integers modulo prime p instead. Primitive roots there are akin to primitive polynomials in GF(2^k). You can start from any element except 0 and keep multiplying by a primitive root and you'll visit every other element in a maximum-length cycle. OTOH if you multiply by a non-primitive element you get a shorter cycle and which cycle you land in depends on your starting point. It's easier to get a feel for what's going on when the operation is "multiplication mod 11" and the group is small. Commented Jul 23 at 19:20