## Fast linear canonical transforms

JOSA A, Vol. 27, Issue 1, pp. 21-30 (2010)

http://dx.doi.org/10.1364/JOSAA.27.000021

Enhanced HTML Acrobat PDF (526 KB)

### Abstract

The linear canonical transform provides a mathematical model of paraxial propagation though quadratic phase systems. We review the literature on numerical approximation of this transform, including discretization, sampling, and fast algorithms, and identify key results. We then propose a frequency-division fast linear canonical transform algorithm comparable to the Sande–Tukey fast Fourier transform. Results calculated with an implementation of this algorithm are presented and compared with the corresponding analytic functions.

© 2010 Optical Society of America

**OCIS Codes**

(070.4560) Fourier optics and signal processing : Data processing by optical means

(080.2730) Geometric optics : Matrix methods in paraxial optics

(100.2000) Image processing : Digital image processing

(200.2610) Optics in computing : Free-space digital optics

(200.3050) Optics in computing : Information processing

(200.4560) Optics in computing : Optical data processing

(200.4740) Optics in computing : Optical processing

**ToC Category:**

Fourier Optics and Signal Processing

**History**

Original Manuscript: August 25, 2009

Manuscript Accepted: November 2, 2009

Published: December 3, 2009

**Citation**

John J. Healy and John T. Sheridan, "Fast linear canonical transforms," J. Opt. Soc. Am. A **27**, 21-30 (2010)

http://www.opticsinfobase.org/josaa/abstract.cfm?URI=josaa-27-1-21

Sort: Year | Journal | Reset

### References

- T. Kreis, Handbook of Holographic Interferometry, Optical and Digital Methods (Wiley-VCH, 2005).
- J. W. Goodman, Introduction to Fourier Optics, 3rd ed. (Roberts, 2005).
- S. Abe and J. T. Sheridan, “Optical operations on wave functions as the Abelian subgroups of the special affine Fourier transformation,” Opt. Lett. 19, 1801-1803 (1994). [CrossRef] [PubMed]
- H. M. Ozaktas, Z. Zalevsky, and M. A. Kutay, The Fractional Fourier Transform with Applications in Optics and Signal Processing (Wiley, 2001).
- M. J. Bastiaans, “Wigner distribution function and its application to first-order optics,” J. Opt. Soc. Am. 69, 1710-1716 (1979). [CrossRef]
- H. O. Bartelt, K.-H. Brenner, and A. W. Lohmann, “The Wigner distribution function and its optical production,” Opt. Commun. 32, 32-38 (1980). [CrossRef]
- K. B. Wolf, Integral Transforms in Science and Engineering (Plenum, 1979).
- S. A. Collins, “Lens-system diffraction integral written in terms of matrix optics,” J. Opt. Soc. Am. 60, 1168-1177 (1970). [CrossRef]
- S. Abe and J. T. Sheridan, “Generalization of the fractional Fourier transformation to an arbitrary linear lossless transformation an operator approach,” J. Phys. A 27, 4179-4187 (1994). [CrossRef]
- B. M. Hennelly, D. P. Kelly, R. F. Patten, J. E. Ward, U. Gopinathan, F. T. O'Neill, and J. T. Sheridan, “Metrology and the linear canonical transform,” J. Mod. Opt. 53, 2167-2186 (2006). [CrossRef]
- D. P. Kelly, J. E. Ward, B. M. Hennelly, U. Gopinathan, F. T. O'Neill, and J. T. Sheridan, “Paraxial speckle-based metrology systems with an aperture,” J. Opt. Soc. Am. A 23, 2861-2870 (2006). [CrossRef]
- R. F. Patten, B. M. Hennelly, D. P. Kelly, F. T. O'Neill, Y. Liu, and J. T. Sheridan, “Speckle photography: mixed domain fractional Fourier motion detection,” Opt. Lett. 31, 32-34 (2006). [CrossRef] [PubMed]
- B. M. Hennelly and J. T. Sheridan, “Image encryption and the fractional Fourier transform,” Optik (Stuttgart) 114, 251-265 (2003).
- A. Nelleri, J. Joseph, and K. Singh, “Digital Fresnel field encryption for three-dimensional information security,” Opt. Eng. (Bellingham) 46, 045801 (8 pages) (2007). [CrossRef]
- J. E. Ward, D. P. Kelly, and J. T. Sheridan, “Three-dimensional speckle size in generalized optical systems with limiting apertures,” J. Opt. Soc. Am. A 26, 1858-1867 (2009). [CrossRef]
- M. J. Bastiaans and K. B. Wolf, “Phase reconstruction from intensity measurements in one-parameter canonical-transform systems,” in Proceedings of Seventh International Symposium on Signal Processing and Its Applications, Vol. 1 (IEEE, 2003), pp. 589-592. [CrossRef]
- U. Gopinathan, G. Situ, T. J. Naughton, and J. T. Sheridan, “Noninterferometric phase retrieval using a fractional Fourier system,” J. Opt. Soc. Am. A 25, 108-115 (2008). [CrossRef]
- S.-C. Pei and J.-J. Ding, “Closed-form discrete fractional and affine Fourier transforms,” IEEE Trans. Signal Process. 48, 1338-1353 (2000). [CrossRef]
- B. M. Hennelly and J. T. Sheridan, “Fast numerical algorithm for the linear canonical transform,” J. Opt. Soc. Am. A 22, 928-937 (2005). [CrossRef]
- J. J. Healy and J. T. Sheridan, “Sampling and discretization of the linear canonical transform,” Signal Process. 89, 641-648 (2009). [CrossRef]
- J. J. Healy, B. M. Hennelly, and J. T. Sheridan, “An additional sampling criterion for the linear canonical transform,” Opt. Lett. 33, 2599-2601 (2008). [CrossRef] [PubMed]
- A. Stern, “Why is the linear canonical transform so little known?” in Proceedings of 5th International Workshop on Information Optics, G.Cristóbal, B.Javidi, and S.Vallmitjana, eds (Springer, 2006), pp. 225-234.
- F. Oktem and H. M. Ozaktas, “Exact relation between continuous and discrete linear canonical transforms,” IEEE Signal Process. Lett. 16, 727-730 (2009). [CrossRef]
- A. Koç, H. M. Ozaktas, C. Candan, and M. A. Kutay, “Digital computation of linear canonical transforms,” IEEE Trans. Signal Process. 56, 2383-2394 (2008). [CrossRef]
- B. M. Hennelly and J. T. Sheridan, “Generalizing, optimizing, and inventing numerical algorithms for the fractional Fourier, Fresnel, and linear canonical transforms,” J. Opt. Soc. Am. A 22, 917-927 (2005). [CrossRef]
- X. Liu and K.-H. Brenner, “Minimal optical decomposition of ray transfer matrices,” Appl. Opt. 47, E88-E98 (2008). [CrossRef] [PubMed]
- T. Alieva and M. J. Bastiaans, “Properties of the linear canonical integral transformation,” J. Opt. Soc. Am. A 24, 3658-3665 (2007). [CrossRef]
- G. Kloos, Matrix Methods for Optical Layout (SPIE Press, 2007). [CrossRef]
- L. Onural, “Some mathematical properties of the uniformly sampled quadratic phase function and associated issues in digital Fresnel diffraction simulations,” Opt. Eng. (Bellingham) 43, 2557-2563 (2004). [CrossRef]
- F. Gori, “Fresnel transform and sampling theorem,” Opt. Commun. 39, 293-297 (1981). [CrossRef]
- J. J. Healy and J. T. Sheridan, “Cases where the linear canonical transform of a signal has compact support or is band-limited,” Opt. Lett. 33, 228-230 (2008). [CrossRef] [PubMed]
- X.-G. Xia, “On bandlimited signals with fractional Fourier transform,” IEEE Trans. Signal Process. 3, 72-74 (March 1996). [CrossRef]
- J.-J. Ding, “Research of fractional Fourier transform and linear canonical transform,” Ph.D. dissertation (National Taiwan University, 2001).
- A. Stern, “Sampling of linear canonical transformed signals,” Signal Process. 86, 1421-1425 (2006). [CrossRef]
- B. Deng, R. Tao, and Y. Wang, “Convolution theorems for the linear canonical transform and their applications,” Sci. China Ser. F, Inf. Sci. 49, 592-603 (2006). [CrossRef]
- B.-Z. Li, R. Tao, and Y. Wang, “New sampling formulae related to linear canonical transform,” Signal Process. 87, 983-990 (2007). [CrossRef]
- J. Zhao, R. Tao, and Y. Wang, “Sampling rate conversion for linear canonical transform,” Signal Process. 88, 2825-2832 (2008). [CrossRef]
- B. Barshan, M. Alper Kutay, and H. M. Ozaktas, “Optimal filtering with linear canonical transformations,” Opt. Commun. 135, 32-36 (1997). [CrossRef]
- A. W. Lohmann, R. G. Dorsch, D. Mendlovic, Z. Zalevsky, and C. Ferreira, “Space-bandwidth product of optical signals and systems,” J. Opt. Soc. Am. A 13, 470-473 (1996). [CrossRef]
- W. T. Rhodes, “Light tubes, Wigner diagrams and optical signal propagation simulation,” in Optical Information Processing: A Tribute to Adolf Lohmann, H.J.Caulfield, ed. (SPIE Press, 2002) pp. 343-356 (2002).
- J.-C. Kuo, C.-H. Wen, and A.-Y. Wu, “Implementation of a programmable 64~2048-point FFT/IFFT processor for OFDM-based communication systems,” in Proceedings of the 2003 International Symposium on Circuits and Systems, Vol. 2 (IEEE, 2003), pp. 121-124.
- H. M. Ozaktas, A. Koç. I. Sari, and M. Alper Kutay, “Efficient computation of quadratic-phase integrals in optics,” Appl. Opt. 31, 35-37 (2006). [CrossRef]
- H. M. Ozaktas, O. Arikan, M. A. Kutay, and G. Bozdagt, “Digital computation of the fractional Fourier transform,” IEEE Trans. Signal Process. 44, 2141-2150 (1996). [CrossRef]
- W. M. Gentleman and G. Sande, “Fast Fourier transforms--for fun and profit,” in Proceedings of AFIPS Fall Joint Computer Conference, Vol. 29 (ACM, 1966), pp. 563-578.
- M. Frigo and S. G. Johnson, “The design and implementation of FFTW3,” Proc. IEEE 93, 216-231 (2005). [CrossRef]
- C. M. Rader, “Discrete Fourier transforms when the number of data samples is prime,” Proc. IEEE 56, 1107-1108 (1968). [CrossRef]
- B. Kernighan, and D. Ritchie, The C Programming Language (Prentice-Hall, 1978).
- MATLAB, Users Guide (The MathWorks, Inc., 1998).
- S. Wolfram, The Mathematica Book, 3rd ed. (Wolfram Media, 2003).
- J. W. Cooley and J. W. Tukey, “An algorithm for the machine computation of complex Fourier series,” Math. Comput. 19, 297-301 (1965). [CrossRef]
- S. G. Johnson and M. Frigo, “A modified split-radix FFT with fewer arithmetic operations,” IEEE Trans. Signal Process. 55, 111-119 (2007). [CrossRef]
- T. J. Lundy and J. Van Buskirk, “A new matrix approach to real FFTs and convolutions of length 2k,” Computing 80, 23-45 (2007). [CrossRef]
- A. Cortes, I. Velez, and J. F. Sevillano, “Radix rk FFTs: matricial representation and SDC/SDF pipeline implementation,” IEEE Trans. Signal Process. 57, 2824-2839 (2009). [CrossRef]
- A. Averbuch, R. R. Coifman, D. L. Donoho, M. Elad, and M. Israeli, “Fast and accurate polar Fourier transform,” Appl. Comput. Harmon. Anal. 21, 145-167 (2006). [CrossRef]

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article | Next Article »

OSA is a member of CrossRef.