A model of computation for Fourier optical processors
Departmental seminar, 6 December 1999
Tom Naughton, Department of Computer Science, NUI Maynooth, Ireland
Abstract. The discovery of efficient algorithms is important for the development of optical information processing. In order to measure and compare the efficiency of these algorithms we need a theoretical model of computation that is easy to analyse and yet yields meaningful results by corresponding closely to physical implementations.
The ability of Fourier processors to compute constant time Fourier transforms and constant time image multiplication (but little else) requires us to construct specialised models of computation. We explain the limitations of existing approaches and present a novel and simple theoretical machine model that captures what we believe to be the most important characteristics of an optical Fourier transform processor.
Its very restricted instruction language has neither conditional branching nor iteration. This allows us to argue that algorithms describable with this model should have optical implementations that do not require a digital electronic computer to act as a master unit. Through theoretical simulations of well-known universal machines we hypothesise that our model is universal.