There has been enough theory in this blog of late. Time to make it concrete.
What do the numbers 31 and 32767 have in common? The former is equal to 25 - 1. The latter is equal to 215 - 1, or equivalently (and tellingly), 25 * 3 - 1.
Why does this relationship have anything to do with the cryptic picture from two posts back?
Consider the relationship between this image and another lightpost. This one has only five lights, and is connected to produce its next light from the fifth and third lights:
If you investigate this shorter lightpost, you will find that has two cycles: the trivial cycle, with every light off, and one other, which covers the other 31 possible light patterns. You will also find that this single, 31-length cycle matches the 'seed' cycle we found in the last post.
Here, then, we have our answer: the lightpost we have been studying has behaviour that resembles the behaviour of three shorter lightposts, which have been interleaved together. We got a bunch of different cycles in the larger lightpost, depending on how the three smaller 'internal' lightposts were initially configured, which explains why the hot bits go a long way in classifying the various cycles.
Why did this structure arise in this case, but our initial lightpost did not? (Recall that the original produced a single, 32767-length cycle, with no apparent substructure.) The answer is in which lights were used to determine the next light's state: in the latter case, the output light and the input lights were all multiples of three apart. This meant that changing a single light's initial configuration could only affect a third of the lights in a cycle. Thus we find that there are three lightposts, leading largely independent lives. In contrast, the first lightpost we encountered was not separable in this manner.
I probably won't go into any more depth about the cycles and structure of lightposts, but I will say that I have only scratched the surface of their behaviour. Consider how many different lightpost families there are. We only looked at lightposts where two of the lights controlled the next light, but since the operation is exclusive or, we could 'tap' as many as we wanted. This means that each lightpost with N lights can produce 2N - 1 possible configurations of cycles (we exclude the case where none of the lights are tapped). The simplest structure between each family to find is that each configuration of taps has a 'twin' configuration that produces the same number and length of cycles, but reverses the lights in each. (It is pretty easy to see why: remember that the predecessor and successor of each lightpost is deterministic, so we expect and can find that each tap configuration will have a 'twin' tap configuration that will swap the predecessor and successor operation).
Now, at last: what does this have to do with NES audio? To answer this, I will at last reveal that our various lighposts are examples of what electrical engineers call Linear Feedback Shift Registers: that is, they are shift registers, where the feedback value shifted in to the empty place at each shift is not a constant 0 or 1, but some linear combination of the pre-shifted state. Unsurprisingly, the NES audio processing unit contains an LFSR, which it uses for its 'noise' channel, and equally unsurprisingly, it is 15 bits long, and has two modes: one where bits 14 and 15 are tapped, and another where bits 9 and 15 are tapped. Now you understand my particular interest in these two tap configurations.
The NES APU's noise channel uses bit 15 of this LFSR as an output signal to your television. When it is set up to feedback according to bits 14 and 15, the signal that it outputs is 32767 units long. This 'wavelength' is so long that humans don't perceive any tone in it, and instead it sounds like static. If you instead set it up to feedback on bits 9 and 15, the signal is only 93 units long, and the human ear can distinguish a definite tone in the output. You can get subtly different timbres depending on whether your particular cycle has 16, 32 or 48 'on' bits: sixteen bits gives a metallic buzz, while 48 bits is a bit more mellow. The tone gets much higher if in addition to tapping bits 9 and 15, you also seed the LFSR with a bit pattern which forces it to the length-31 cycle. This outputs a harsh metallic buzz.
You can hear samples of all five different modes in the WAV files in this zip file.
It was not common to have the noise channel outputting long samples like this. Instead, it was played in very short bursts, and was used to approximate percussive instruments. My favourite example of a slick 'drum' beat can be heard in Wood Man's theme from Mega Man 2.
That is the story of how a seemingly useless thought experiment can have a very practical application. Tune in again when we look at the other audio channels available in the NES, and of the challenges of duplicating the characteristic sound on more modern hardware.
The audio samples attached to this story were created by simulating a linear feedback shift register in software. The source code for that simulation can be seen below:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/// <summary>
/// Represents a shift register whose feedback is a linear function (XOR) of a subset of the bits
/// in its current value, referred to as the tap bits.
/// </summary>
public class LinearFeedbackShiftRegister
{
#region Member variables
int[] taps;
int highBit;
ulong registerValue;
#endregion
#region Properties
/// <summary>
/// Gets or sets the current value of the shift register.
/// </summary>
public ulong RegisterValue
{
get
{
return registerValue;
}
set
{
if (value == 0)
throw new ArgumentOutOfRangeException("value", "RegisterValue cannot be set to zero.");
// --- If the 63rd bit is the high bit, then any
// --- input is valid. Otherwise, check that the input
// --- doesn't set any bits beyond the register size
if (highBit < 63 && (value >> (highBit + 1)) > 0)
throw new ArgumentOutOfRangeException("value", "Input value is larger than the shift register");
registerValue = value;
}
}
#endregion
#region Constructors
/// <summary>
/// Initializes a new instance of the LinearFeedbackShiftRegister class.
/// </summary>
/// <param name="numBits">The size, in bits, of the shift register.</param>
/// <param name="tappedBits">A binary value where a bit value of 1 means that the corresponding bit of the register will be tapped.</param>
public LinearFeedbackShiftRegister(int numBits, ulong tappedBits)
: this(numBits, TapsFromBits(tappedBits))
{
}
static int[] TapsFromBits(ulong taps)
{
return Enumerable.Range(0, 64).Where(i => (taps & (1ul << i)) == (1ul << i)).ToArray();
}
/// <summary>
/// Initializes a new instance of the LinearFeedbackShiftRegister class.
/// </summary>
/// <param name="numBits">The size, in bits, of the shift register.</param>
/// <param name="tappedBits">An array of integers specifying which bits of the register will be tapped.</param>
public LinearFeedbackShiftRegister(int numBits, int[] tappedBits)
{
if (numBits < 2 || numBits > 64)
throw new ArgumentOutOfRangeException("numBits", "NumBits must be between 2 and 64 inclusive.");
if (tappedBits == null)
throw new ArgumentNullException("tappedBits");
if (tappedBits.Length == 0)
throw new ArgumentException("No taps specified.", "tappedBits");
if (tappedBits.Length != tappedBits.Distinct().Count())
throw new ArgumentException("Duplicate taps specified.", "tappedBits");
foreach (var tappedBit in tappedBits)
if (tappedBit < 0 || tappedBit >= numBits)
throw new ArgumentOutOfRangeException("tappedBits", string.Format("{0} is not between 0 and {1} inclusive.", tappedBit, numBits - 1));
taps = tappedBits.ToArray(); // Make a copy so caller can't modify the array from underneath us
highBit = numBits - 1;
registerValue = 1;
}
#endregion
#region Instance methods
/// <summary>
/// Advances the shift register to its next state.
/// </summary>
public void Shift()
{
if (CurrentRegisterValueProducesFeedback)
registerValue = (registerValue >> 1) | (1ul << (highBit));
else
registerValue = (registerValue >> 1);
}
bool CurrentRegisterValueProducesFeedback
{
get { return (taps.Where(tap => IsRegisterBitSet(tap)).Count() & 1) == 1; }
}
bool IsRegisterBitSet(int index)
{
var mask = 1ul << index;
return ((registerValue & mask) == mask);
}
/// <summary>
/// Determines how many times the shift register can be shifted before it returns to its current value.
/// </summary>
public ulong GetCycleLength()
{
var result = 0ul;
IterateCycle(val => result++);
return result;
}
/// <summary>
/// Computes the bit pattern that is produced by one iteration of the current cycle.
/// </summary>
public string GetCyclePattern()
{
var result = new StringBuilder();
IterateCycle(val => result.Append((val & 1ul) == 1ul ? '1' : '0'));
return result.ToString();
}
/// <summary>
/// Determines the state in the current cycle of the shift register with the smallest binary value.
/// </summary>
public ulong GetSmallestValueInCycle()
{
var result = ulong.MaxValue;
IterateCycle(val => result = Math.Min(result, val));
return result;
}
/// <summary>
/// Computes the shift register values possible in the current cycle.
/// </summary>
public List<ulong> GetCycleValues()
{
var result = new List<ulong>();
IterateCycle(val => result.Add(val));
return result;
}
/// <summary>
/// Iterate through the shift register values in the current cycle and pass them to the input callback.
/// </summary>
/// <param name="callback">The callback to invoke on each shift register value.</param>
public void IterateCycle(Action<ulong> callback)
{
var startingValue = registerValue;
do
{
callback(registerValue);
Shift();
}
while (registerValue != startingValue);
}
#endregion
}
No comments:
Post a Comment