How to test if a pseudo-random sequence is complete?

[fra93]

Hi I invented a "shift register" like circuit that behaves similarly to a linear feedback shift register, but it has a complete sequence.
From here on I will call this circuit Non-Linear Pseudo Random Generator NLPRG for simplicity.

Below some circuit typologies ranging from 3 up to 16 bits ( if you somebody wants I can explain how it works and provide the Verilog an C code ).



I tested all the NLPRG sequences with a counter. For example in the 16 bits case, both of them are initialized with 0x0000, any number would work. If the counter or the NLPRG reaches the number 0x0000, than end the simulation. If at the end of the simulation, both the counter and the nlprg are in the 0x0000 state than the sequence of the nlprg is complete.

But this approach does not scale up because the simulation time increases exponentially with the number of bits.

Can somebody propose an alternative testing methodology? I want to see if the NLPRG has 2^n states where n is the number of registers.

 

[vGoodtimes]

you can possible use a ram to test if you reach all states of your de-bruijn or nlfsr sequence.

eg, on each cycle ram[value] == 0. and if so you set ram[value] = 1. and in sim, this is easy to do.

for larger values of n, I think you want a mathematical proof. this is pretty easy for de-bruijn sequences. I think it isn't as easy for nlfsr cases.

 

[fra93]

Is analytical proof the only way?

Is there any form of formal verification method and tool that can assist?

 

[pjmelect]

One very good way of testing a random number generator is to use the random numbers generated as coordinates to plot points on the screen and see if you can see any paterns or other non random anomalies.

 

[fra93]

Do you mean as a 2d plot? I plotted the generated numbers as an hystogram and they looked random. I also tested the sequence using all the Dieharder tests, and I got slightly better results than a simple lfsr.

My concearn is not on the quality of the sequence, but on the testability as I scale the bit length. The simulation time grows exponentially.

 

[KlausST]

Hi,

I'm not sure, but I guess if you check on one single value, then this might be sufficient.

My idea:
If one single value repeats, then the whole sequence will repeat.

If I'm not mistaken then with LFSR you get 2^n -1 different values, but they repeat, they are in a strong order.
So start with any seed, and clock by clock compare the output with your seed. If there is a match before 2^n, then this indicates that there are some redundant codes that are not used in your sequence.

You should be able to verify if this is true for your algorithm.

But one requirement still remains: for any number of "n" the whole test should last 2^n steps.
This may be long time.

Klaus

 

[fra93]

That is exactly what I did, and all the circuits I drawn in the first post have a complete sequence.

 

[ThisIsNotSam]

you know there are known polynomials for maximal LFSR sequences, right? you don't need to perform any simulation, just look at the generator polynomial.

(perhaps I don't understand what you are trying to do)

 

[KlausST]

Hi,

(perhaps I don't understand what you are trying to do)

Yes, I´m confused, too.

Maybe I misunderstood the problem.

The headline says: "How to test if a pseudo-random sequence is complete?"
(maybe I misunderstand "test" or "complete")
In my eyes: If you want to test for 2^n different results, then you need to 2^n steps. Else you never know...
If you just look for 2^n- 1 values (or less) you can not be sure that the last one is different to all the previous ones.

Klaus

 

[fra93]

you know there are known polynomials for maximal LFSR sequences, right? you don't need to perform any simulation, just look at the generator polynomial.

(perhaps I don't understand what you are trying to do)

I am not testing LFSR. I am testing my circuit that has a complete sequence.
For complete I mean 2^n numbers, and not 2^n-1 as in the LFSR case.

I can run simulations for small bit-lengths, lets say n < 24. If I add more bits the simulation will take too much time to complete. I can not run a simulation with 2^256 numbers for example.

Do you know if there is some property checker, or formal verification tool that can test if the period of the generated sequence is 2^n?

 

[wwfeldman]

according to Wolfram Alpha, 2^256 is about 1.15 x10^77, with 78 decimal digits
likewise, the time from the big bang is about 4.8 x 10^17 seconds

if you started at the big bang, you would have to test one state about every 10^-60 seconds,
about 10^50 times faster than anything available today, or use an extraordinarily parallel system
a year is about 3 x 10^7 seconds, so you would need about 3 x 10^43 parallel(?) simultaneous(?) processors.

fuhgeddaboudit

are you looking to build an encryption device?

 

[ThisIsNotSam]

Do you know if there is some property checker, or formal verification tool that can test if the period of the generated sequence is 2^n?

in theory, you can write an assertion for this property very easily. will the tools handle it? no clue.

 

[fra93]

in theory, you can write an assertion for this property very easily. will the tools handle it? no clue.

How can you express such property?

 

[std_match]

It is difficult to verify large versions of your generators.
You want a "complete LFSR", and this has been researched.
One general way is to modify a normal LFSR so an all-zero state is inserted after the "00000......00000001" state.

 

[ThisIsNotSam]

How can you express such property?

I am not sure this works, but maybe the construct is what you need:

a ##1 b [*1:$] ##1 a  // sequence is a b b[..] b b a

This could be teh mechanism you need to detect a repeating pattern. you would have to add some intelligence to it. maybe once you detect the first repeated pattern, the next cycle has to be a repeated pattern too.

 

[wwfeldman]

it appears no one knows how to verify your system analytically

https://en.wikipedia.org/wiki/Nonlinear-feedback_shift_register

or if they do know, its a secret