Author: Notus([email?protected])
Create: 2019-02-18
Update: 2019-02-18

随机数测试：Frequencey test(monobit test),Serial test(two-bit test),Poker test,Runs test and Autocorrelation test

环境

Python version: 3.7.1

代码如下(PseudorandomTest.py)

‘‘‘
    Pseudorandom Sequences Tests: 
        1. Frequency test (monobit test)
        2. Serial test (two-bit test)
        3. Poker test
        4. Runs test
        5. Autocorrelation test
    @Author: Notus([email?protected])
    @Create: 2019-02-15
    @Update: 2019-02-18
    @Version: 1.0
‘‘‘

import math

# 1. Frequency test(monobit test)
def monobitTest(num):
    n = len(num)
    n0 = num.count(‘0‘)
    n1 = num.count(‘1‘)
    X = (n0 - n1) ** 2 / n
    return n,n0,n1,X

# 2. Serial test(two-bit test)
def serialTest(num):
    n = len(num)
    n0 = num.count(‘0‘)
    n1 = num.count(‘1‘)
    n00 = n01 = n10 = n11 = 0

    for i in range(0,n-1):
        i0 = num[i]
        i1 = num[i+1]
        if i0 == ‘0‘:
            if i1 == ‘0‘: 
                n00 += 1
            else: 
                n01 += 1
        else:
            if i1 == ‘0‘: 
                n10 += 1
            else: 
                n11 += 1
        i += 1

    X = 4 * (n00**2 + n01**2 + n10**2 + n11**2) / (n-1) - 2 * (n0**2 + n1**2) / n + 1
    return n,n00,n01,n10,n11,X 


# 3. Poker test
def pokerTest(num,m):
    n = len(num)
    k = n // m
    if k < 5 * (2 ** m):
        raise ValueError("Error: the value of m is invalid for Poker Test!")

    # ni count list,0 <= i <= 2**m - 1
    ni_list = [0] * (2 ** m)

    # counting  
    for b in range(0,n-m,m):
        index = 0
        for c in range(m):
            index = index * 2 + int(num[b + c])
        ni_list[index] += 1

    s = 0
    for i in range(1,2**m + 1):
        s += ni_list[i - 1] ** 2

    X = (2 ** m) * s / k - k
    return k,ni_list,X


# 4. Runs test
def runsTest(num):
    n = len(num)
    e = {}
    for i in range(1,n + 3):
        e_i = (n - i + 3) / (2 ** (i + 2))
        if e_i >= 5:
            e[i] = e_i
    k = max(e.keys())
    B = [0] * k
    G = [0] * k
    
    def countBG(bit,runLength):
        counts = 0
        contNumbs = 0               # continuous number counts
        for idx in range(n):
            if num[idx] != bit: 
                if contNumbs == runLength:
                    counts += 1
                contNumbs = 0
                continue

            contNumbs += 1

            # last block or gap
            if contNumbs == runLength and idx == n - 1: 
                counts += 1 
        return counts

    for i in range(k):
        B[i] = countBG(‘1‘,i + 1)
        G[i] = countBG(‘0‘,i + 1)

    x1 = x2 = 0
    for i in range(1,k + 1):
        x1 += (B[i-1] - e[i]) ** 2 / e[i]
        x2 += (G[i-1] - e[i]) ** 2 / e[i]
    X = x1 + x2

    return e,k,B,G,X


# 5. Autocorrelation test
def autocorrelationTest(num,d):
    n = len(num)
    if not 1 <= d <= math.floor(n / 2):
        raise ValueError("Error: d value is invalid!")
    Ad = 0
    for i in range(n - d):
        Ad += ( int(num[i]) ^ int(num[i + d]) )
    X = 2 * (Ad - (n - d) / 2) / math.sqrt(n - d)
    return Ad,X


if __name__ == ‘__main__‘:
    num = (‘11100‘ + ‘01100‘ + ‘01000‘ + ‘10100‘ + ‘11101‘ + ‘11100‘ + ‘10010‘ + ‘01001‘) * 4
    
    x1 = monobitTest(num)
    print("frequency test: nn = {},n0 = {},n1 = {},nX1 = {}n".format(*x1))

    x2 = serialTest(num)
    print("serial test: nn = {},n00 = {},n01 = {},n10 = {},n11 = {},nX2 = {}n".format(*x2))

    m = 3
    try:
        x3 = pokerTest(num,m)
    except ValueError as err:
        print(err.args[0])
        sys.exit()
    print("poker test: nk = {},ni_list = {} nX3 = {}n".format(*x3))
    
    x4 = runsTest(num)
    print("runs test: ne = {},k = {},B = {},G = {} nX4 = {}n".format(*x4))

    d = 8
    try:
        x5 = autocorrelationTest(num,d)
    except ValueError as err:
        print(err.args[0])
        sys.exit()
    print("Autorcorrelation test: nA({}) = {} nX5 = {}".format(d,*x5))

运行结果

python PseudorandomTest.py
frequency test:
n = 160,n0 = 84,n1 = 76,X1 = 0.4

serial test:
n = 160,n00 = 44,n01 = 40,n10 = 40,n11 = 35,X2 = 0.6251572327043959

poker test:
k = 53,ni_list = [5,10,6,4,12,3,7]
X3 = 9.641509433962263

runs test:
e = {1: 20.25,2: 10.0625,3: 5.0},k = 3,B = [25,5],G = [8,20,12]
X4 = 31.791306264856992

Autorcorrelation test:
A(8) = 100
X5 = 3.893314107138301