A forward-parsing randomness test based on the expected codeword length of T-codes
Ulrich Speidel · 2011
This paper proposes an algorithm for randomness testing. It is a variant of an algorithm presented earlier by the author for the construction of random sequences. The algorithm exploits two facts: Firstly, given a complete finite prefix code Ciover an alphabet A, every semi-infinite sequence s of symbols x0, x1, x2, ... from A starts with a codeword wi∈ Ci, and if one presumes that s is random, one can compute the expected length hiof wi. Secondly, wican be used to extend Cito yield a larger code Ci+1. In this case, the actual length |Wi| of widetermines the growth in the expected codeword length hi+1for the codeword wi+1∈ Ci+1that follows in s after the end of wi. If |wi| >; hithen hi+1grows less compared to hi, than if |Wi| ≤ hi. By comparing expected codeword lengths and actual codeword lengths cumulatively, one may assess the randomness of s: If the hypothesis that s is random holds, then the cumulative values should closely mirror each other.