The Designer's Guide Community Forum

The Designer's Guide Community Forum
https://designers-guide.org/forum/YaBB.pl
Design >> Mixed-Signal Design >> Any algo to calculate the randomness of data pattern
https://designers-guide.org/forum/YaBB.pl?num=1239938942

Message started by neoflash on Apr 16^th, 2009, 8:29pm

Title: Any algo to calculate the randomness of data pattern
Post by neoflash on Apr 16^th, 2009, 8:29pm

I want to build an algo to judge whether input N length pattern is noise like or very repetetive pattern.

Any known reference to recommend?

Thanks,
Neo

Title: Re: Any algo to calculate the randomness of data pattern
Post by Visjnoe on Apr 17^th, 2009, 4:06am

Dear Neo,

the subject of randomness by itself is not as 'trivial' as some people may think. Please have a look at 'Kolmogorov complexity'. In short: there's no general algorithm to proof that your string is random.

Regards

Peter

Title: Re: Any algo to calculate the randomness of data pattern
Post by pancho_hideboo on Apr 17^th, 2009, 4:55am

neoflash wrote on Apr 16^th, 2009, 8:29pm:

I want to build an algo to judge whether input N length pattern is noise like or very repetetive pattern.

Calculate auto-correlation function and plot it.
Here judgement is dependent on your own thinking.

http://en.wikipedia.org/wiki/Auto_correlation

Title: Re: Any algo to calculate the randomness of data pattern
Post by neoflash on Apr 17^th, 2009, 8:39pm

pancho_hideboo wrote on Apr 17^th, 2009, 4:55am:

neoflash wrote on Apr 16^th, 2009, 8:29pm:

I want to build an algo to judge whether input N length pattern is noise like or very repetetive pattern.

Calculate auto-correlation function and plot it.
Here judgement is dependent on your own thinking.

http://en.wikipedia.org/wiki/Auto_correlation

When we calculated the Rx vector, how to judge the randomness of the data? I think it is still hard to tell from the Rx vector.

Any suggestions or reference paper?

Title: Re: Any algo to calculate the randomness of data pattern
Post by pancho_hideboo on Apr 18^th, 2009, 12:50am

neoflash wrote on Apr 17^th, 2009, 8:39pm:

When we calculated the Rx vector, how to judge the randomness of the data? I think it is still hard to tell from the Rx vector.

It depends on your need or thinking for randomness.

Anyway try to plot Rxx[n], n=0,...,N-1 for your target sequences, then consider and make criteria.

Title: Re: Any algo to calculate the randomness of data pattern
Post by ywguo on May 5^th, 2009, 12:05am

Hi neo,

What's your need? What's your application? If you don't have any special requirement, plot the FFT of the data stream or calculate the auto-correlation as what pancho_hidiboo said. Otherwise, maybe you need to check the run length of continous 0 and 1, the balance between number of 0 and number of 1, etc.

Yawei

Title: Re: Any algo to calculate the randomness of data pattern
Post by Frank Wiedmann on May 5^th, 2009, 1:48am

See also http://en.wikipedia.org/wiki/Randomness_tests and the links given there.

Title: Re: Any algo to calculate the randomness of data pattern
Post by neoflash on May 5^th, 2009, 8:15pm

I think calculating FFT is a good idea. But calculating Rx is more practical a idea and easier to implement.

The statistics could be collected over time and updated in a accumulator.

Thanks.

Title: Re: Any algo to calculate the randomness of data pattern
Post by vivkr on May 6^th, 2009, 1:12am

neoflash wrote on May 5^th, 2009, 8:15pm:

I think calculating FFT is a good idea. But calculating Rx is more practical a idea and easier to implement.

The statistics could be collected over time and updated in a accumulator.

Thanks.

That is a strange comment to make since autocorrelation (Rx) and power spectral density (based on FFT) provide identical information, provided that they are used correctly, and ideally both are computed to provide an overview in time- and frequency- domains.

As for computation, I don't believe that one or the other is more difficult. Matlab for instance will give you both in a flash. In the old days, it might have been computationally easier to compute Rx than the FFT but I think those were very old days.

Vivek