Fast decimation-in-frequency direct binary search (DBS) algorithms for the computation of binary computer-generated holograms (CGH’s) are developed. The algorithms use the geometry of the image plane and the decimation-in-frequency property to design a fast method of scanning the hologram with the DBS method. In this way the computational complexity of the method is substantially reduced. For complex-amplitude-based error, the asymptotic computational complexity for an L-point CGH is reduced by a factor of O[(L/log2L)1/2]. For intensity-based error, the asymptotic computational complexity for an L-point CGH is reduced by a factor of O[(L log2L)1/4]. When the probability of accepting an inversion is small, an acceleration technique is also used to reduce further the time complexity.
© 1994 Optical Society of America
Original Manuscript: May 28, 1993
Revised Manuscript: July 19, 1993
Manuscript Accepted: July 20, 1993
Published: January 1, 1994
J-Y. Zhuang and O. K. Ersoy, "Fast decimation-in-frequency direct binary search algorithms for synthesis of computer-generated holograms," J. Opt. Soc. Am. A 11, 135-143 (1994)