Linear Feedback Shift Register

[Jacob Roman]

I'm a bit baffled, not to mention frustrated beyond comprehension and hopefully I can explain this right or I just once again created a dead thread noone can answer due to the advanced nature of what I'm about to write.

Theres a type of randomness out there called a Linear Feedback Shift Register, or for short, LFSR. A LFSR is a shift register whose input bit is a linear function of its previous state. Basically it works at a binary level. With that said, the most commonly used linear function of single bits of the LFSR is an XOR. The XOR gate of the LFSR shifts the bits either left or right. Just to give you an idea, take a look at this image of a 4 bit LFSR


And you can read more up on it through wikipedia HERE

I actually need this because I wrote an NES Emulator in VB6, which you can find in my signature. The Nintendo Entertainment System used this LFSR in one of their sound channels called Noise. The Noise sound channel is used in things such as percussion, explosions, bricks breaking, someone being hit, etc. However, this monstrosity uses a 15 bit size LFSR numbered from bit 14 to bit 0. Although I implemented it, it only half works. And I have no idea why. Some games it sounds great such as Double Dragon, but games like Super Mario Bros, I hear only half the percussion, and don't hear the bricks breaking. Just a thump. So it all boils down to only half the LFSR working. And mods, don't move this to the Games and Graphics section as it is regarding a programming problem. Just hear me out. The NES does Noise through 3 8-bit registers in memory which are (in Hex) $400C, $400E, and $400F. $400D is not used. Noise goes through a pseudo-random bit sequence and has 2 modes. The modes are determined by Bit 7 of register $400E which can be either 0 or 1, shown here:

Bits
7 6 5 4 3 2 1 0
M - - - - - - -

Where M is Mode. If its 0, the Noise is 32767 steps long. If its 1, then Noise is only 93 steps long. However, the particular 93-step sequence depends on where in the 32767-step sequence the shift register was when Mode flag was set. I personally have a feeling that one of my modes are not being executed. Probably the 32767 step sequence. Now before this sequence can be produced, it must go through a series of rules, which are:

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:

    1. Feedback is calculated as the exclusive-OR of bit 0 and one other bit: bit 6 if Mode flag is set, otherwise bit 1.
    2. The shift register is shifted right by one bit.
    3. Bit 14, the leftmost bit, is set to the feedback calculated earlier.

You can find all the information on this here:
http://wiki.nesdev.com/w/index.php/APU_Noise

as well as even more information on it through a few of the links I put up in one of my posts in my NES Emulator thread. The code I used to execute this is here, with a lot of comments:

Public Function Noise_Channel_Render_Sample() As Long
    
    Dim Bit0 As Long
    Dim Bit1 As Long
    Dim Bit6 As Long
    
        'if (Noise.datatype)
        '    Noise.CurD = (Noise.CurD << 1) | (((Noise.CurD >> 14) ^ (Noise.CurD >> 8)) & 0x1);
        'else    Noise.CurD = (Noise.CurD << 1) | (((Noise.CurD >> 14) ^ (Noise.CurD >> 13)) & 0x1);
    
    With Noise_Channel
        If .Length_Counter > 0 And .Enabled Then
            '.SampleCount = Within_Range(.SampleCount + 1, 0, LONG_RANGE) 'causes minor slowdown
            .SampleCount = .SampleCount + 1
            If .SampleCount >= .RenderedWavelength Then
                .SampleCount = .SampleCount - .RenderedWavelength
                If .Noise_Random_Generator_Mode = True Then '93 bits long
                    'According to [url]http://wiki.nesdev.com/w/index.php/APU_Noise[/url]
                    
                    '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
                    
                    'Step 1) Feedback is calculated as the exclusive-OR of bit 0 and one other bit: bit 6 if Mode flag is set, otherwise bit 1.
                    '        Note: Exclusive Or is Xor, not Or! Or is Inclusive.
                        Bit0 = (.NoiseShiftData) \ Power_Of_2(14) 'Right Shifts it to bit 0 by right shifting 14 bits (see shift register table above)
                        Bit6 = (.NoiseShiftData) \ Power_Of_2(8) 'Right Shifts it to bit 6 by right shifting 8 bits (see shift register table above)
                        .Noise_Feedback = (Bit0 Xor Bit6)
                Else '32767 bits long
                    'According to [url]http://wiki.nesdev.com/w/index.php/APU_Noise[/url]
                    
                    '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
                    
                    'Step 1) Feedback is calculated as the exclusive-OR of bit 0 and one other bit: bit 6 if Mode flag is set, otherwise bit 1.
                    '        Note: Exclusive Or is Xor, not Or! Or is Inclusive.
                        Bit0 = (.NoiseShiftData) \ Power_Of_2(14) 'Right Shifts it to bit 0 by right shifting 14 bits (see shift register table above)
                        Bit1 = (.NoiseShiftData) \ Power_Of_2(13) 'Right Shifts it to bit 1 by right shifting 13 bits (see shift register table above)
                        .Noise_Feedback = (Bit0 Xor Bit1)
                End If
                
                'Step 2) The shift register is shifted right by one bit.
                    .NoiseShiftData = .NoiseShiftData * 2
                'Step 3) Bit 14, the leftmost bit, is "set" to the feedback calculated earlier.
                '        Note: You set it using the Or operator, not the And operator like you would see in most emulators' source code
                    '.Noise_Feedback = .Noise_Feedback Or BIT_14
                'Then the Noise shift gets updated and prepared to be outputed for sound.
                    .NoiseShiftData = .NoiseShiftData Or (.Noise_Feedback And &H1&)
            End If
            
            If .Envelope_Decay_Disable Then
                Noise_Channel_Render_Sample = ((.NoiseShiftData And &H1&) * &H40&) * .Volume
                Exit Function
            Else
                Noise_Channel_Render_Sample = ((.NoiseShiftData And &H1&) * &H40&) * .Envelope
                Exit Function
            End If
        Else
            .Volume = 0
        End If
        Noise_Channel_Render_Sample = 0
        Exit Function
    End With
End Function

Seems like my code is consistent with the documentation thus far, unless I missed something. But here is another thing I noticed. The NesDev site also mentioned the shift register is 15 bits wide. However in my sound debugger of my emulator, Im seeing the shift register numbers far exceed that in the millions range randomly in either positive or negative. If you do the math, 15 bits is $8000 in hex, or in other words, 32768 in decimal. Im not sure if I should keep the shift register within the range of 32767 as I didn't ever find any other open source emulator do this. So through all this advanced crap thats probably making all of you scratch your heads and be like "huh?" , my 2 problems are basically:

1. Only one of the modes are being heard, especially in super mario bros. Why is this? Could there be a bug in my code I overlooked in that function?

2. I'm not so sure if I should keep the LFSR within the range of 32767 (15 bits) as it really isnt done in any other emulator.

Hopefully I did the LFSR right. I given all the information I could at the moment as its super late but if anyone has any questions, let me know, or if any of you all have some bright ideas on how to properly do it, I would appreciate it. Thanks in advance. (Crosses my fingers)

[Doogle]

I wont pretend to understand what you're trying to do but this looks 'funny'

'Step 2) The shift register is shifted right by one bit.
42.                    .NoiseShiftData = .NoiseShiftData * 2

Doesn't that shift it to the left by one bit ? (or am I demonstrating my complete ignorance?)

[Jacob Roman]

Wow how could I've missed that! The funny thing is that now I don't hear sound at all because the shift register is brought down to 0. So I'm not sure if the documentation is wrong. In Double Dragon, using a Left Shift produces accurate noise emulation, and stays in 32767 mode throughout the game. So it wasnt 32767 mode it seems, but instead 93 mode.

Also I have a feeling I need to use a lookup table because I have another NES emulator written in C++ that setup the LFSR like this:

static void shift_register15(int8 *buf, int count)
{
   static int sreg = 0x4000;
   int bit0, bit1, bit6, bit14;

   if (count == APU_NOISE_93)
   {
      while (count--)
      {
         bit0 = sreg & 1;
         bit6 = (sreg & 0x40) >> 6;
         bit14 = (bit0 ^ bit6);
         sreg >>= 1;
         sreg |= (bit14 << 14);
         *buf++ = bit0 ^ 1;
      }
   }
   else /* 32K noise */
   {
      while (count--)
      {
         bit0 = sreg & 1;
         bit1 = (sreg & 2) >> 1;
         bit14 = (bit0 ^ bit1);
         sreg >>= 1;
         sreg |= (bit14 << 14);
         *buf++ = bit0 ^ 1;
      }
   }
}

Where *buf is the array being stored data, and count either is the constant 93, or the constant 32767. Then while it plays the sound, it saves the position the XOR tap has been produced using this function:

INLINE int8 shift_register15(uint8 xor_tap)
{
   static int sreg = 0x4000;
   int bit0, tap, bit14;

   bit0 = sreg & 1;
   tap = (sreg & xor_tap) ? 1 : 0;
   bit14 = (bit0 ^ tap);
   sreg >>= 1;
   sreg |= (bit14 << 14);
   return (bit0 ^ 1);
}

But it bugs me because none of this stuff is consistent with the documentation with the exception of the xor position. Yet the sheer thought of a look up table does sound intriguing. So I'm gonna see what I can do. Thanks for the possible flaw Doogle. But if it doesn't work I'm gonna have to go back to left shift and assume the docs were wrong.

[Doogle]

One other thing I noticed, and this might be a comment error

26.                        Bit6 = (.NoiseShiftData) \ Power_Of_2(8) 'Right Shifts it to bit 6 by right shifting 8 bits (see shift register table above)

Bit 6 would be 'isolated' by shifting 6 bits rather than 8 (?)

I think If I were doing this I'd be using Ands and in 'small steps' (so I could follow what's going on):

Bit0 = .NoiseShiftData And &H1&             'Isolate Bit0 of NoiseShiftData into bit0 of Bit0
Bit6 = (.NoiseShiftData And &H40&) / &H40&  'Isolate Bit6 of NoiseShiftData into bit0 of Bit6
' If the Comment is incorrect and you really need Bit8:
' Bit8 = (.NoiseShiftData And &H100&) / &H100&
Bit1 = (.NoiseShiftData And &H2&) / &H2&    'Isolate Bit1 of NoiseShiftData into bit0 of Bit1
'
' Xor the values depending on Mode
'
If Noise_Random_Generator_Mode = True Then
    .NoiseFeedBack = Bit0 Xor Bit6          '
Else
    .NoiseFeedBack = Bit0 Xor Bit1
End If
'
' At this point .NoiseFeedBack is either '1' or '0'
' Shift the result into bit14 of .NoiseFeedBack
'
.NoiseFeedBack = .NoiseFeedBack * Power_Of_2(14)
'
' NoiseFeedback is now either '16384'(2^14) or '0'
' Right shift NoiseShiftData by one bit
'
.NoiseShiftData = .NoiseShiftData / 2
'
' Set Bit14 of NoiseShiftData to the value of bit14 of .NoiseFeedBack
'
.NoiseShiftData = .NoiseShiftData Or .NoiseFeedBack

[Jacob Roman]

In the site http://wiki.nesdev.com/w/index.php/APU_Noise, it clearly states "Feedback is calculated as the exclusive-OR of bit 0 and one other bit: bit 6 if Mode flag is set, otherwise bit 1. " It all starts at Bit 14. To get to Bit 6 you have to right shift 8 bits:
------------------------>
14-13-12-11-10-9-8-7-6-5-4-3-2-1-0

And I technically already small stepped it. Take a look at this C# code from another emulator that was commented inside the function:

        'if (Noise.datatype)
        '    Noise.CurD = (Noise.CurD << 1) | (((Noise.CurD >> 14) ^ (Noise.CurD >> 8)) & 0x1);
        'else    Noise.CurD = (Noise.CurD << 1) | (((Noise.CurD >> 14) ^ (Noise.CurD >> 13)) & 0x1);

Although ugly, if you break it down, its actually

        'if (Noise.datatype){
        '    Bit_0 = (Noise.CurD >> 14);
        '    Bit_6 = (Noise.CurD >> 8);
        '    Feedback = (Bit_0 ^ Bit_6);
        '    Noise.CurD = (Noise.CurD << 1) | (Feedback & 0x1);
        '}
        'else {   
        '    Bit_0 = (Noise.CurD >> 14);
        '    Bit_1 = (Noise.CurD >> 13);
        '    Feedback = (Bit_0 ^ Bit_1);
        '    Noise.CurD = (Noise.CurD << 1) | (Feedback & 0x1);
        '}

And even though I did it a tad different, the results were the same either way. Removing &H1 in any of those places resulted in a much higher pitched Noise.

[EDIT] I was playing around with my emulators noise code and, not sure if you have or not but download my NES Emulator, and remove the ".Length_Counter > 0" if statement in the beginning of the function. Play Super Mario Bros, ignor the Noise sound for a minute (youll see why), grab a mushroom, and break a brick block. Youll hear something that was missing. The sound of bricks breaking with a nice bass thump. Although the length counter code is correct, I may have to do what the C++ emulator did, and actually use a lookup table that I can XOR tap.

[Doogle]

It all starts at Bit 14. To get to Bit 6 you have to right shift 8 bits

(EDIT: If you wanted to put bit6 into bit 14 then you'd have to shift it 8 bits to the left)

I think we're talking at cross purposes. To get the value of Bit 6 there's no 'shift' involved. To 'isolate' bit6, as suggested in my last Post, you 'And' it with 2^6 (&H40), if the result is zero bit6 is not set, otherwise it is; or as I did, calculate (value And &H40&) / &H40&), if the result is 0 bit6 is not set if it's 1 it is set.

If you take a value of 2^6 = 64 and shift it right by 8 bits (256) using a calculation such as: (2^6) \ (2^8) the result will be zero, whereas you actually want '1' (which you'd get by shifting it right by 6 bits i.e. (2^6) \ (2^6) = 1
.
Just shifting does not necessarily 'isolate' the bit you're looking for.

For example: take a value of Binary '000001001000000' (2,176) shift it right by 6 bits gives '000000000001001' (9). All that's done is moved all the bits right by 6 bits. To determine whether the original bit6 was set you'd have to And the result with &H1& which would give you '000000000000001'

I knocked up a very simple emulator using the 'rules' from the site you quoted and the 'And' methodology for 'isolating' the necessary bits. I haven't run it for more than 32,767 steps but it certainly repeats the pseudo-random sequence after 93 steps when 'Mode' is set. It's attached for your amusement.

[Jacob Roman]

Ok I'll take a look at it.

I setup a Look up table and placed them in a listbox. You can see the ones and zeros created. Although I'm pretty sure it goes against the docs, it'll give me something to XOR tap. Just create a new project, and add a listbox:

Option Explicit
 
Private Const APU_MODE_32k As Long = &H7FFF&
Private Const APU_MODE_93 As Long = 93
 
Private Noise_Long_LUT() As Long
Private Noise_Short_LUT() As Long
 
Private Function Linear_Feedback_Shift_Register_Lookup_Table(ByRef LUT() As Long, ByVal Count As Long)
 
    Dim Bit0 As Long
    Dim Bit1 As Long
    Dim Bit6 As Long
    Dim Bit14 As Long
    Dim Shift_Register As Long
    Dim Inc As Long
    
    If Count = APU_MODE_93 Then
        ReDim LUT(APU_MODE_93) As Long
        Shift_Register = &H4000
        While Count >= 0
            Count = Count - 1
            Bit0 = Shift_Register And &H1&
            Bit6 = (Shift_Register And &H40&) \ &H40&
            Bit14 = (Bit0 Xor Bit6)
            Shift_Register = Shift_Register \ &H2&
            Shift_Register = Shift_Register Or (Bit14 * &H4000)
            LUT(Inc) = Bit0 Xor &H1
            List1.AddItem Inc & ": " & LUT(Inc)
            Inc = Inc + 1
        Wend
    ElseIf Count = APU_MODE_32k Then
        ReDim LUT(APU_MODE_32k) As Long
        Shift_Register = &H4000
        While Count >= 0
            Count = Count - 1
            Bit0 = Shift_Register And &H1&
            Bit1 = (Shift_Register And &H2&) \ &H2&
            Bit14 = (Bit0 Xor Bit1)
            Shift_Register = Shift_Register \ &H2&
            Shift_Register = Shift_Register Or (Bit14 * &H4000)
            LUT(Inc) = Bit0 Xor &H1&
            Inc = Inc + 1
        Wend
    End If
 
End Function
 
Private Sub Form_Load()
    Me.Show
    Linear_Feedback_Shift_Register_Lookup_Table Noise_Short_LUT(), APU_MODE_93
    Linear_Feedback_Shift_Register_Lookup_Table Noise_Long_LUT(), APU_MODE_32k
End Sub

[Doogle]

I think we're now in violent agreement

[Jacob Roman]

Well I like how you executed your project but I had to make a minor change in the variable names to avoid confussion because "Feedback is calculated as the exclusive-OR of bit 0 and one other bit: bit 6 if Mode flag is set, otherwise bit 1. ". See the Shift function:

Option Explicit
 
Private Feedback As Long
Private Shift_Register As Long
Private lngCount As Long
 
Private Sub cmdStart_Click()
    Dim lngVal As Long
    lngVal = 1
    Call Shift
    Timer1.Enabled = True
End Sub
 
Private Sub cmdStop_Click()
    Timer1.Enabled = False
End Sub
 
Private Sub Form_Load()
    Dim intI As Integer
    Dim lngVal As Long
    lngVal = 0
    For intI = 13 To 0 Step -1
        Load labB(intI)
        labB(intI).Left = labB(intI + 1).Left + labB(intI + 1).Width
        labB(intI).Top = labB(intI + 1).Top
        labB(intI).Caption = "Bit" & CStr(intI)
        labB(intI).Visible = True
        Load labBit(intI)
        labBit(intI).Left = labBit(intI + 1).Left + labBit(intI + 1).Width
        labBit(intI).Top = labBit(intI + 1).Top
        labBit(intI).Caption = "0"
        labBit(intI).Visible = True
    Next intI
    labBit(14).Caption = "0"
    lv.ColumnHeaders.Add , , "Step"
    lv.ColumnHeaders.Add , , "Shift Register Value"
    DisplayBits Feedback
    Timer1.Interval = 500
    Shift_Register = 1
End Sub
 
Private Sub DisplayBits(lngVal As Long)
    Dim lngI As Long
    Dim intI As Integer
    For intI = 14 To 0 Step -1
        If (lngVal And (2 ^ intI)) = 0 Then
            labBit(intI).Caption = "0"
        Else
            labBit(intI).Caption = "1"
        End If
    Next intI
End Sub
 
Private Sub Timer1_Timer()
    Timer1.Enabled = False
    Shift
    Timer1.Enabled = True
End Sub
 
Private Sub Shift()
 
    Dim lvi As ListItem
    Dim lngBit0 As Long
    Dim lngBit1 As Long
    Dim lngBit6 As Long
    lngBit0 = Shift_Register And &H1&
    lngBit1 = (Shift_Register And &H2&) \ &H2
    lngBit6 = (Shift_Register And &H40&) \ &H40
    If chkMode.Value = vbChecked Then
        Feedback = lngBit0 Xor lngBit6
    Else
        Feedback = lngBit0 Xor lngBit1
    End If
    Feedback = Feedback * (2 ^ 14)
    Shift_Register = Shift_Register \ 2
    Shift_Register = Shift_Register Or Feedback
    DisplayBits Shift_Register
    lngCount = lngCount + 1
    labS.Caption = CStr(lngCount)
    Set lvi = lv.ListItems.Add(, , CStr(lngCount))
    lvi.SubItems(1) = Shift_Register
End Sub

The only difference between your project and my project is that mine returns ones and zeros in the lookup table with one bit per index in the array, while yours returns shift register values.

[Doogle]

Yes, I did make a small modification to display the Binary value in the ListView as well, really just for interest to see the 'pattern'.

[Jacob Roman]

Another thing is that I had to make a minor change in mine as well to be more consistent with the docs because the shift register starts with a value of one, not bit 14. I have 2 open source nintendo emulators in C# and C++ that started at bit 14. Now Im not sure if thats true but here are the changes Ive made. I may need to change the LUT receiving (Bit0 Xor &H1&) To (Shift_Register And &H1&) Xor &H1&, but not sure till I actually hear sound with this thing once I splice it into my emulator:

Private Function Linear_Feedback_Shift_Register_Lookup_Table(ByRef LUT() As Long, ByVal Count As Long)
 
    Dim Bit0 As Long
    Dim Bit1 As Long
    Dim Bit6 As Long
    Dim Feedback As Long
    Dim Inc As Long
    
    If Count = APU_MODE_93 Then
        ReDim LUT(APU_MODE_93) As Long
        While Count >= 0
            Count = Count - 1
            Bit0 = Shift_Register And &H1&
            Bit6 = (Shift_Register And &H40&) \ &H40&
            Feedback = (Bit0 Xor Bit6)
            Feedback = Feedback * &H4000&
            Shift_Register = Shift_Register \ &H2&
            Shift_Register = Shift_Register Or Feedback
            LUT(Inc) = Bit0 Xor &H1
            List1.AddItem Inc & ": " & LUT(Inc)
            Inc = Inc + 1
        Wend
    ElseIf Count = APU_MODE_32k Then
        ReDim LUT(APU_MODE_32k) As Long
        While Count >= 0
            Count = Count - 1
            Bit0 = Shift_Register And &H1&
            Bit1 = (Shift_Register And &H2&) \ &H2&
            Feedback = (Bit0 Xor Bit1)
            Feedback = Feedback * &H4000&
            Shift_Register = Shift_Register \ &H2&
            Shift_Register = Shift_Register Or Feedback
            LUT(Inc) = Bit0 Xor &H1&
            Inc = Inc + 1
        Wend
    End If
 
End Function

[EDIT] I see why there is so much misinformation out there. The famous emulation textfile to the NES called everynes.txt says this about the Noise channel:

The random number generator consists of a 15bit shift register. The MSB (Bit14)
is output/inverted (1=Low/Zero, 0=High/Decay/Volume). At the specified
frequency, Bit14 is XORed with Bit13 (32767-bit mode) or with Bit8 (93-bit
mode), the register is then shifted to the left, with the result of the XOR
operation shifted-in to Bit0.

[Doogle]

That description in your last post will do exactly the same thing but will start at a different value in the sequence and with a '1' in bit14. The problem with shifting left in VB is that there's no Unsigned Long type, so you have to clear out bits 15 to 31 before / after you shift to stop a '1' propagating to bit31 and the value becoming 2's compliment (i.e. negative). I'd stick with shifting right - it appears to work.