Career: Theory and Applications of Reversible Cellular Automata

点击翻译按钮获取中文摘要

Reversible Cellular Automata (RCA) are locally computed parallel one-to-one mappings of cellular space onto itself. They provide a solid theoretical model for massively parallel non-dissipative computation. This project investigates the theory of RCA and closely related Quantum Cellular Automata (QCA), and introduces new applications in image compression and cryptography. The main theoretical goal is to understand the structure of RCA and find new representations of RCA in terms of simple local operations. The representations should allow easy generation of new RCA rules that can be used in the applications. Most useful representations are ones that allow desired properties to be programmed directly into the RCA. Quantum CA are generalizations of RCA. The first goal is to find a correct definition of QCA in the sense that it is realizable in the actual physical world with quantum interactions. The definition should be also general enough to allow implementations of arbitrary quantum algorithms. Then the relation between QCA and homogeneous arrays of finite quantum gates will be determined. Image compression applications arise from analogy to subband coding. Reversible Cellular Automata are interpreted as non-linear versions of perfect reconstruction filter banks. Energy compaction by linear transforms is replaced by the idea of information compaction by RCA. The new compression techniques will be most suitable for efficient lossless compression but also lossy image compression applications are considered. In addition, analogy to RCA theory provides new insight into the theory of higher dimensional filter banks. In cryptography the project continues investigating the feasibility and security of RCA based cryptosystems. Applications to image compression and cryptography, together with related results on finite automata in fractal image generation and compression will be introduced to the computer science curriculum through standard computation theory cou rses. They provide practical examples of how automata theory can be useful in seemingly unrelated fields, and increase student motivation to study challenging theoretical concepts. A new graduate course and seminar on image compression will be developed with emphasis on algorithmic aspects of compression in addition to the traditional signal processing approach.