FAST DECIMATION-IN-FREQUENCY DIRECT BINARY SEARCH ALGORITHMS FOR SYNTHESIS OF COMPUTER-GENERATED HOLOGRAMS

Fast decimation-in-frequency direct binary search (DBS) algorithms for the computation of binary computer-generated holograms (CGH's) are de veloped. The algorithms use the geometry of the image plane and the de cimation-in-frequency property to design a fast method of scanning the hologram with the DBS method. In this way the computational complexit y of the method is substantially reduced. For complex-amplitude-based error, the asymptotic computational complexity for an L-point CGH is r educed by a factor of O[(L/log(2) L)(1/2)]. For intensity-based error, the asymptotic computational complexity for an L-point CGH is reduced by a factor of O[(L log(2) L)(1/4)], When the probability of acceptin g an inversion is small, an acceleration technique is also used to red uce further the time complexity.