Designer’s Guide Community

neoflash Community Fellow Offline Mixed-Signal Designer Posts: 397	Any algo to calculate the randomness of data pattern 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
Back to top	IP Logged

Visjnoe Senior Member Offline Posts: 233	Re: Any algo to calculate the randomness of data pattern Reply #1 - 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
Back to top	IP Logged

pancho_hideboo

Senior Fellow

Offline

Posts: 1424
Real Homeless

Re: Any algo to calculate the randomness of data pattern
Reply #2 - 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

Back to top

Kita━━━━━━(ﾟ∀ﾟ)━━━━━━ !!!!!
http://www7.plala.or.jp/ungeromeppa/flash/kita.html
http://www.youtube.com/watch?v=mjIxGh55bMM&feature=related

IP Logged

neoflash

Community Fellow

Offline

Mixed-Signal
Designer

Posts: 397

Re: Any algo to calculate the randomness of data pattern
Reply #3 - 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?

Back to top

IP Logged

pancho_hideboo

Senior Fellow

Offline

Posts: 1424
Real Homeless

Re: Any algo to calculate the randomness of data pattern
Reply #4 - 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.

Back to top

« Last Edit: Apr 18^th, 2009, 6:59am by pancho_hideboo »

Kita━━━━━━(ﾟ∀ﾟ)━━━━━━ !!!!!
http://www7.plala.or.jp/ungeromeppa/flash/kita.html
http://www.youtube.com/watch?v=mjIxGh55bMM&feature=related

IP Logged

ywguo

Community Fellow

Offline

Posts: 943
Shanghai, PRC

Re: Any algo to calculate the randomness of data pattern
Reply #5 - 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

Back to top

IP Logged

Frank Wiedmann Community Fellow Offline Posts: 678 Munich, Germany	Re: Any algo to calculate the randomness of data pattern Reply #6 - May 5^th, 2009, 1:48am See also http://en.wikipedia.org/wiki/Randomness_tests and the links given there.
Back to top	IP Logged

neoflash Community Fellow Offline Mixed-Signal Designer Posts: 397	Re: Any algo to calculate the randomness of data pattern Reply #7 - 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.
Back to top	IP Logged

vivkr

Community Fellow

Offline

Posts: 780

Re: Any algo to calculate the randomness of data pattern
Reply #8 - 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

Back to top

IP Logged