Carter McCall

In our previous project, “Kolmogorov Complexity and Error-Correcting Codes” supported by the Iowa Space Grant Consortium, we studied the attributes of algorithmically random error-correcting codes. In this earlier work we wrote a program in Java to generate families of algorithmically random strings, which were then used to generate random linear codes. The transmission rate and error correction capacity of each of these codes was then calculated, experimentally verifying a classical result on random linear codes due to Coffey and Goodman.

An important notion of algorithmic randomness, defined in terms of deterministic finite state automata, has recently received increased attention among researchers. We intend to implement our classification of random error-correcting codes for the newly developed notion of finite state randomness. One primary obstacle to doing so is that it is less straightforward to generate finite state random strings compared to the notions of randomness studied in our previous work. The primary aim of this project is thus to find a streamlined procedure for generating families of finite state random strings and then to calculate the transmission rate and error-correction capability of the associated linear codes using the above-described program. In addition, connections to random number generation using finite state machines will be explored.