Random Numbers at particular rate in fix time interval

[aquanaut]

Hi Everybody,

I am working on wired communication project. In that I need to send packets with specified rate in a fixed time interval. The condition is, these packets should arrive in a random manner. For example, I want to send 10 packets in an interval of 1sec then, all 10 packet should arrive independently in a 1sec timing window. The expected result should be as given in attached image...


Here all t1, t2....t9 should be independent and should not be predictable.

I searched about it a lot but I could not find such number generation. Please help me how can I find time after which I send the packet.

Thanks in advance...

 

[mrflibble]

You could use an LFSR to generate your random numbers. Keep in mind that as usual this is pseudo random, but for an application like this that should be sufficient.

http://en.wikipedia.org/wiki/Linear_feedback_shift_register
http://www.asic-world.com/examples/verilog/lfsr.html
http://outputlogic.com/?page_id=275

All you need to do is spend some time reading the above and you are good to go.

 

[aquanaut]

Thanks for your valuable reply....

I have spent lot of time for this. I have found that Poisson Distribution is good option for this but I don't know how to apply Poisson Distribution for this implementation and whether it can be implemented in hardware or not.

 

[mrflibble]

Well, if you make that lambda nice and large for your Poisson distribution, look no further. LFSR spits out normal distribution, and it so happens that for large lambda Poisson disitrbution approximates the normal distribution. Put another way, make that lambda large and you can just do it with a LFSR which is nice and cheap in terms of hardware.

 

[aquanaut]

I didn't get you...how can I generate Poisson's distribution using simple LFSR? Can you please provide some more details about it? Or can I generate random number distributed in Poisson dist fashion, from Normally distributed numbers?

 

[mrflibble]

Or can I generate random number distributed in Poisson dist fashion, from Normally distributed numbers?

That. Lemme see if I can quickly find something.

- - - Updated - - -

Ah, there we go: http://www.youtube.com/watch?v=u9onO78hDlw

- - - Updated - - -

More to the point is ... where do you get the fact that you need Poisson distribution? Did you think of that yourself? If so, what reasoning?

 

[aquanaut]

From **broken link removed**... Under Random Processe->Poisson process. After going through this I came to know about this...

 

[mrflibble]

You do realize that that doesn't answer the question right? I know how to get a Poisson distribution. And then what? Ah what the hell, short version is just use an LFSR and you will be fine.

 

[aquanaut]

Ok...lets not use Poisson Distribution for this. So using LFSR can you please elaborate how will you send 10 packets in a 1 sec time interval, as I have given in my first post example? What should be the t1, t2,...t9 value?

 

[mrflibble]

Strictly speaking what you should do is for each packet generate random number x (with the LFSR), then transform to exponential distribution, and then accumulate that to give t0, t1, t2, etc.

But what you can probably get away with is: generate random number x, use x as address of LUT to get the MSB of your sortof-exponential distribution. accumulate that to give MSBs of t0, t2, t3.
So you have random time slots of 1 LSB. Then if you want smaller chunks you generate another random number, which you then use as the LSBs. That does not have exactly a Poisson distribution, but get suspiciously close to it at a reasonable hardware cost IMO.

Or if you don't like that, you can always implement a fullblown log function to plug x into. Personally I'd use the LFSR ==> LUT ==> MSB and LFSR ==> LSB approach. Oh and obviously first write a quick matlab script to verify that you indeed get a decent distribution this way. You can even use the very same matlab script to generate your vhdl/verilog LUT for you. ;-) That way you can play around a little with the number of bits you need for the lookup table (for those MSBs), and how many bits you want to use for the LSB part.

Capiche?

- - - Updated - - -

Incidentally, your specs are a bit mutually exclusive. The above answer I gave is for what you probably want. But if you really really meant what you wrote (probably not), then you should generate 10 timestamps between 0.0 and 1.0 seconds, sort them in ascending order, and then use those. But as said, you probably don't mean what you wrote and it becomes impractical for larger numbers of packets. While for the LFSR with inverse transform (that LUT thingy) it doesn't suddenly become more expensive for more packets.

- - - Updated - - -

Since I am far too lazy to type all that I thought I'd see if there was some reading material you can use:

http://electronicdesign.com/digital-ics/random-number-generator-has-predefined-distribution

See the pretty pictures, that's precisely what I mean. So in figure 2 you have a LUT that spits out M random bits. And my suggestion is to accumulate that to get the MSB's of your t0, t1, t2, etc. And then for each t0, t1, t2 you generate some extra random bits directly from LFSR and use that as the LSB part.

- - - Updated - - -

While we're at it, this as well:

https://en.wikipedia.org/wiki/Inverse_transform_sampling
https://stackoverflow.com/questions/2106503/pseudorandom-number-generator-exponential-distribution

Notably this bit:

So, generate a uniform random number, u, in [0,1), then calculate x by:

x = log(1-u)/(−λ),

if that doesn't explain it I don't know what does.

 

[permute]

I'm not sure what the exact requirements are. One method that might give you something reasonable would be the following:

1.) have a counter (C) that counts from 0 to F/P-1 and repeats.
2.) have a large but efficient lfsr, L, (eg 63b state where the lowest tap value is still in a high index).
3.) have two counters that can count from 0 to P-1 (or 1 to P).
4.) have a ram that has P entries (or more) that can contain B=lg(F/P + 1) bits per entry.

now, create a state machine that does the following:
1.) init phase -- take entries from the LFSR in B sized chunks. if the value is less than F/P, than add it to ram. do this until P entries have been added. This might take a variable amount of time, but should complete reasonably fast (eg, ~20 cycles).
2.) scanning phase -- now, repeatedly loop through the P entries until the free running counter, C, is greater. send a packet and then set the ram entry to all 1's. (which must be greater than F/P).
3.) if the free running counter reaches the end, run a scanning pass an send out a packet for any entry not already equal to all 1's.

each part might require a few sub-states. You can decide how fancy you need this to be.

This should tend to limit the worst case to 2P consecutive packets, in the case where all packets are delayed until the end on the first interval and then all packets are at the start of the next interval.

 

[aquanaut]

Ok...Thanks for your solutions...

I will try it for my implementation.

Thanks again....