Skip to main content ↑ ↓

Notice

Please note that most of the software linked on this forum is likely to be safe to use. If you are unsure, feel free to ask in the relevant topics, or send a private message to an administrator or moderator. To help curb the problems of false positives, or in the event that you do find actual malware, you can contribute through the article linked here.
Topic: Frequency spectrum of PRN from LFSR (Read 8749 times) previous topic - next topic
0 Members and 1 Guest are viewing this topic.

Frequency spectrum of PRN from LFSR

Read any (appropriate) text book, and it will describe generating pseudo random numbers from linear feedback shift registers.

You can find suitable feedback configurations to give maximum length sequences in many books too. As long as you don't pick the one that locks it, the seed doesn't matter.

I've tried this, both for 16 bits and 19 bits, and for some reason I can't make it workas I expect. I get a maximum length sequence, uniform PDF, single spike autocorrelation, but non-flat frequency response. It is 10dB higher at low frequencies than high frequencies.

Any idea what I might be doing wrong?

Cheers,
David.

Frequency spectrum of PRN from LFSR

Reply #1 –
Maybe the problem lies in your spectral analysis.  Are you properly windowing and overlapping the data?  Maybe your 10dB low frequency boost is caused by the impulse generated by a rectangular window?  Have you tried a 'natural' noise source to see if you're seeing the same thing?

Frequency spectrum of PRN from LFSR

Reply #2 –
Thanks for the hint benski, but it wasn't the window.

It was something even more silly, which I realised in the bath this morning(!).

I will share it in case anyone else ever makes the same mistake...

For 8-bits of dither, I was just grabbing the bottom 8 bits of the LFSR. On the next clock, I was doing the same. So I only had one new bit each time!

This meant each dither sample was equal to the previous, multiplied (or divided) by 2, plus a small (or large) noise signal (i.e. the new bit). You could look at it as an IIR filter with noise at the input, and noise added to the output. The frequency response of this inner filter is what I was seeing.

Clocking the LFSR 8 times per 8-bit sample gives me 8 new bits each time, and solves the problem.

Cheers,
David.

Frequency spectrum of PRN from LFSR

Reply #3 –
Bit independence is a major deal for cryptography people, who use many methods for testing PRNGs for "true randomness". It's probably overkill for an audio dither generator, but it's nonetheless interesting to look at the methods and quality measures used in the cryptography community (a starting point can be this or this or this).

Frequency spectrum of PRN from LFSR

Reply #4 –
Very interesting, thank you!

Cheers,
David.

Frequency spectrum of PRN from LFSR

Reply #5 –
Quote from: 2Bdecided on
Thanks for the hint benski, but it wasn't the window.

It was something even more silly, which I realised in the bath this morning(!).

I will share it in case anyone else ever makes the same mistake...

For 8-bits of dither, I was just grabbing the bottom 8 bits of the LFSR. On the next clock, I was doing the same. So I only had one new bit each time!

This meant each dither sample was equal to the previous, multiplied (or divided) by 2, plus a small (or large) noise signal (i.e. the new bit). You could look at it as an IIR filter with noise at the input, and noise added to the output. The frequency response of this inner filter is what I was seeing.

Clocking the LFSR 8 times per 8-bit sample gives me 8 new bits each time, and solves the problem.

Cheers,
David.



David,

Just to confirm again, the valid random number every 8 cycles? 
Besides, how do u relate few bits of change will have effect on the freq response?  Can you explain it?

thanks

Frequency spectrum of PRN from LFSR

Reply #6 –
Something you might also consider is the dual form of the LFSR, where instead of taking 'n' bits and xoring them into the first, you take the last bit and XOR it into the appropriate bits in the shift register.  While it's been a long, long time since I did this, it is possible to make a shift register from this that changes more bits at a time. For that kind of register, you want to choose a complex, as opposed to simple, polynomial for the register, though.

There is also a hardware form I used to use that used two parallel registers and a bunch of XOR's that gave very, very nice results at one tick per value. As I write this, I must say that I also realize I built this in 1977, and I can't remember a (*&(*& thing except that it was published somewhere and it worked like a charm for sequences of length 2^15 -1 ... Sorry.
-----
J. D. (jj) Johnston

Frequency spectrum of PRN from LFSR

Reply #7 –
Quote from: 2Bdecided on
I've tried this, both for 16 bits and 19 bits, and for some reason I can't make it workas I expect. I get a maximum length sequence, uniform PDF, single spike autocorrelation, but non-flat frequency response. It is 10dB higher at low frequencies than high frequencies.

David, you should post the picture of your spectrum.
One possible explanation is the fact that random numbers are unsigned, i.e. have a DC offset.

Frequency spectrum of PRN from LFSR

Reply #8 –
1st post = 13th December 2007.




@jasonkee111,

If you are using it in the simple way I was, and you want an N-bit output, then you need to clock the LFSR N times per output. Otherwise the consecutive outputs are not independent*. They may be sufficiently independent with fewer than N clocks per output, but there's this obvious problem if you reduce it to 1 clock per output.

* - I know it's not really independent mathematically, but in the time- and frequency domains the samples look sufficiently independent for normal use.

Cheers,
David.