Data Compression with Cellular Automata

Wiktor Macura

University of Maryland

Most modern lossless data compression systems compress files by finding patterns within the data and encoding them into a shorthand. During decompression the shorthand is processed into the original data. A potentially more effective form of compression would be the conversion of the data into a program that generates the original data when it is executed. Research into this area is already starting to become prolific, primarily in the use of grammars and deterministic finite automata. However, a novel approach is the translation of the original data into a cellular automaton rule and initial condition. Our research so far has resulted in a system that translates data into a series of elementary cellular automaton outputs combined using the logical exclusive-or operation, although at this early stage the compression ratio is only 94.80%, on average, over all possible sequences of 26 bits. Besides the compression utility of the system, it is also useful for generating MD5-like hashes of data.

[presentation materials]