Why does a 16bit LFSR pass all Diehard tests?

Question

I made a implementation of an LFSR in Hardware. It was based on the LFSR from the wikipedia page. It has the same output.

It pass all the tests for dieharder, however, if I plot the pairs I get this not very random lines in 2D

2D plot of the LFSR

So, how can I have a strong statistical test that could prove this PRNG is not ideal?

SOLVED:

I have to use comand

dieharder -a -f exemple_LSRF_BS_1_DH.txt -g 202

And add a header to the output file I have my numbers.

Answer 1

By the looks of your plot, I'd guess that your random bitstream emits the entire register after each cycle, rather than emitting just one bit per cycle. This means that when viewed as 16-bit words, x_(n+1) is either X_n / 2 or X_n / 2 + 32768. This manifests as two diagonal lines with a gradient of 0.5 (or 2.0, depending on the order and/or shift direction).

Normal usage of an LFSR would emit either one bit per cycle, or all n bits every n cycles. This does produce some negative properties, but they're not so obvious as what you've shown.

As for why your test fails dieharder; I think there must be a flaw in your test set-up. I modified code from Wikipedia to emit the 16-bit state on every cycle on stdout, and piped that into dieharder -a -g200, and it failed immediately on the first five tests. That's what one would expect; even hexdump -C shows obvious visible patterns.

Modifying the code to emit the 16-bit state every 16 cycles, hexdump -C looks much more random, but dieharder still fails just the same.

Perhaps you didn't specify the generator source to dieharder, and so it used its default internal generator. You can confirm this on line five of the output:

   rng_name    |rands/second|   Seed   |
        mt19937|  1.42e+08  |1473327481|

Even so, if you want more thorough tests for your generators, have a look at TestU01.