h1

2 Lessons on PRBS Generators and Randomness

July 10, 2007

The topic of “what is random” is rather deep and complicated. I am far from an authority on the subject and must admit to be pretty ignorant about it. However, this post will deal with two very simple but rather common errors (or misbehaviors) of random number generators usage.

    LFSR width and random numbers for your testbench

Say you designed a pretty complicated block or even a system in HDL and you wish to test it by injecting some random numbers to the inputs (just for the heck of it). For simplicity reasons lets assume your block receives an integer with a value between 1 and 15. You think to yourself that it would be pretty neat to use a 4-bit LFSR which generates all possible values between 1 and 15 in a pseudo-random order and just repeat the sequence over and over again. Together with the other type of noise in the system you inject, this should be pretty thorough, right? Well, not really!

Imagine for a second how the sequence looks like, each number will always be followed by another specific number in this sequence! For example, you will never be able to verify a case where the same number is injected immediately again into the block!
To verify all other cases (at least for all different pairs of numbers) you would need to use an LFSR with a larger width (How much larger?). What you need to do then is to pick up only 4 bits of this bigger LFSR and inject them to your block.

I know this sounds very obvious, but I have seen this basic mistake done several times before – by me and by others as well (regardless of their experience level).

    PRBS and my car radio “mix” function

On sunny days I ride my bicycle to work, but on rainy days I chicken out and use the car for the 6km I have to go. Since I don’t often like what is on the radio, I decided to go through my collection of CDs and choose the 200 or so songs I would like to listen to in the car and burn them as mp3s on a single CD (Don’t ask how much time this took). Unfortunately, if you just pop in the CD and press play, the songs play in alphabetical order. Luckily enough, my car CD player has a “mix” option. So far so good, but after a while I started to notice that when using the “mix” option, always song 149 is followed by song 148, which in turn is followed by song 18, and believe me this is annoying to the bone. The whole idea of “mixing” is that you don’t know what to expect next!

I assume that the “mix” function is accomplished by some sort of PRBS generator, which explains the deterministic order of song playing. But my advice to you if you design a circuit of this sort (for a CD player, or whatever), is to introduce some sort of true randomness to the system. For example, one could time the interval between power-up of the radio and the first human keystroke on the CD player and use this load the PRBS generator as a seed value, thus producing a different starting song for the play list each time. This however, does not solve the problem of the song playing order being deterministic. But given such a “random” number from the user once could use it to generate an offset for the the PRBS generator making it “jump” an arbitrary number of steps instead of the usual one step.

My point was not to indicate that this is the most clever way to do things, but I do think that with little effort one could come up with slightly more sophisticated systems, that make a big difference.

Advertisements

One comment

  1. nice…..example i like it….



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: