non-overlapping template matching for bit sequences : why non-periodic templates?

To test a 'random' bit sequence for cryptographic strength I have been using the NIST's Non-overlapping Template Matching Test (See page 2-14 but I will explain here). This test uses a non-periodic bit template $B$ of length $m$ and counts the occurrences of the template in the bit sequence over $N$ blocks (where the blocks are just the original bit sequence split up into chunks). Then a Chi-squared test is done.

Let's say $B$ is $0001$, which is non-periodic.

If the bit sequence is $000010100010000...$ then we have...

    000010100010000...
0001                  no match
0001                 match. advance by m
0001             no match
0001            no match
0001           match. advance by m...
0001       no match.
...


Now the question is why should we particularly care about the distribution of non-periodic patterns as compared with periodic ones? Are they special in some way as related to random number generators?

-

1 Answer

I contacted someone from the NIST to answer this question: essentially the counting of aperiodic templates is different to the counting of periodic ones, and the maths is easier when considering aperiodic ones. Unfortunately my training is not good enough to give a better explanation, however there is more information in Volkovich and Rukhin, the Journal of Statistical Computation and Simulation, v 78, 2008, 1131-42, which well beyond my mortal soul.

-