dc.contributor.author |
Speidel, U. |
en |
dc.date.accessioned |
2012-01-16T03:19:44Z |
en |
dc.date.available |
2012-01-16T03:19:44Z |
en |
dc.date.issued |
2011 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-403 (2011) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/10556 |
en |
dc.description.abstract |
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 Ci over
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 hi of wi. Secondly, wi can be used to extend Ci to yield a larger
code Ci+1. In this case, the actual length |wi| of wi determines the growth in the
expected codeword length hi+1 for the codeword wi+1 ∈ Ci+1 that follows in s after
the end of wi. If |wi| > hi, then hi+1 grows 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. |
en |
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
CDMTCS Research Report Series |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial |
en |
dc.title |
A Forward-Parsing Randomness Test Based on the Expected Codeword Length of T-codes |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research::280000 Information, Computing and Communication Sciences |
en |
dc.rights.holder |
The author(s) |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |