Lossless Data Compression Using Cellular Automata

Abstract

This thesis presents an investigation into the idea of using Cellular Automata to compress digital data. The approach is based on the fact that many CA configurations have a previous configuration, but only one next generation. By going backwards and finding a smaller configuration we can store that configuration and how many steps to go forward, instead of the original.

In order to accomplish this an algorithm was developed that can backtrace a 2 dimensional CA configuration, listing its previous configurations. The algorithm is used to find a rule that often has previous configurations and also find an example where a matrix appears to become smaller by backtracing. The conclusion, however, is that when increasing the configuration size to trace the algorithm rapidly becomes too time consuming.