Discrete Fourier transform and permutations

• Autorzy: Hui S. , Żak S. H.

Identyfikatory

DOI

10.24425/bpasts.2019.130874

• Języki publikacji: EN

Abstrakty

EN

It is well known that the magnitudes of the coefficients of the discrete Fourier transform (DFT) are invariant under certain operations on the input data. In this paper, the effects of rearranging the elements of an input data on its DFT are studied. In the one-dimensional case, the effects of permuting the elements of a finite sequence of length N on its Discrete Fourier transform (DFT) coefficients are investigated. The permutations that leave the unordered collection of Fourier coefficients and their magnitudes invariant are completely characterized. Conditions under which two different permutations give the same DFT coefficient magnitudes are given. The characterizations are based on the automorphism group of the additive group ZN of integers modulo N and the group of translations of ZN. As an application of the results presented, a generalization of the theorem characterizing all permutations that commute with the discrete Fourier transform is given. Numerical examples illustrate the obtained results. Possible generalizations and open problems are discussed. In higher dimensions, results on the effects of certain geometric transformations of an input data array on its DFT are given and illustrated with an example.

Słowa kluczowe

EN

discrete Fourier transform; DFT; DFT invariants; Fourier coefficients; permutations; DFT coefficient magnitudes; circulant matrix; pattern recognition

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2019
• Tom: Vol. 67, nr 6
• Strony: 995--1005
• Opis fizyczny: Bibliogr. 27 poz., rys., tab.

Twórcy

autor

Hui S.

• Department of Mathematical Sciences, San Diego State University, San Diego, CA 92182, USA

autor

Żak S. H.

• School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA

Bibliografia

• [1] W.A. Adkins and S.H.Weintraub, Algebra: An Approach via Module Theory, Springer-Verlag, New York, 1992.
• [2] C. Aitken, Two notes on matrices, Proceedings of the Glasgow Mathematical Association 5(3), 109–113, January 1962.
• [3] E. Oran Brigham, The Fast Fourier Transform And Its Applications, Prentice-Hall, New York, 1988.
• [4] S. E. Borujeni, “Speech encryption based on fast Fourier transform permutation”, Proceedings of the 7th IEEE International Conference on Electronics, Circuits and Systems 1, 290–293, 2000.
• [5] C.-Y. Chao, “On a type of circulants”, Linear Algebra and its Applications 6, 241–248, 1973.
• [6] P. J. Davis, Circulant Matrices, Wiley, New York, 1979.
• [7] F. Farnoud (Hassanzadeh) and O. Milenkovic, “Sorting of per-mutations by cost-constrained transpositions”, IEEE Transac-tions on Information Theory 58(1), 3–23, January 2012.
• [8] P. Ferreira, “A group of permutations that commute with the discrete Fourier transform”, IEEE Transactions on Signal Pr-cessing 42(2), 444–445, 1994.
• [9] R.M. Gray, “Toeplitz and circulant matrices: A review”, Foundations and Trends in Communications and Information Theory2(3), 155–239, 2006.
• [10] F. Horn and K.-R. Muller, “Predicting pairwise relations with neural similarity encoders”, Bull. Pol. Ac.: Tech. 66(6), 821–830, 2018.
• [11] S. Hui and S.H. Żak, “Discrete Fourier transform based pattern classifiers”, Bull. Pol. Ac.: Tech. 62(1), 15–22, 2014.
• [12] T.W. Hungerford, Algebra, Springer-Verlag, New York, 1974.
• [13] J. Kurek, B. Swiderski, S. Osowski, M. Kruk, and W. Barhoumi, “Deep learning versus classical neural approach to mammogram recognition”, Bull. Pol. Ac.: Tech. 6(6), 831–840, 2018.
• [14] J. Lang, “Color image encryption based on color blend and chaos permutation in the reality-preserving multipleparameter fractional Fourier transform domain”, Optics Communications338, 181–192, 2015.
• [15] S. Liu, Y. D. Zhang, and T. Shan, “Detection of weak astronomical signals with frequency-hopping interference suppression”, Digital Signal Processing 72, 1–8, 2018.
• [16] G. Manjunath and G.V. Anand, “Speech encryption using circulant transformations”, Proceedings of the 2002 IEEE Inter-national Conference on Multimedia and Expo, ICME 2002, 1, 26–29, 2002.
• [17] A. Matsunaga, K. Koga, and M. Ohkawa, “An analog speech scrambling system using the FFT technique with high-level security”, IEEE Journal on Selected Areas in Communications 7(4), 540–547, 1989.
• [18] A.V. Oppenheim and R.W. Schafer, Discrete-Time Signal Processing, Prentice-Hall, New York, 1989.
• [19] D. Passman, Permutation Groups, Benjamin, New York, 1968.
• [20] S. Pawar and K. Ramchandran, “R-FFAST: A robust sub-linear time algorithm for computing a sparse DFT”, IEEE Transactions on Information Theory 64(1), 451–466, January 2018.
• [21] S.-C. Pei, C.-C. Wen, and J.-J. Ding, “Closed-form orthogonal DFT eigenvectors generated by complete generalized Legendre Sequence”, IEEE Transactions on Circuits and Systems— I: Reg-ular Papers 55(11), 3469–3479, December 2008.
• [22] Y. Qiu, G. Zhou, Q. Zhao, and A. Cichocki, “Comparative study on the classification methods for breast cancer diagnosis”, Bull. Pol. Ac.: Tech. 6(6), 841–848, 2018.
• [23] N.D. Sidiropoulos, M.S. Pattichis, A.C. Bovik, and J.W. Havlicek, “COPERM: Transform-domain energy compaction by optimal permutation”, IEEE Transactions on Signal Processing 47(6), 1679–1688, 1999.
• [24] E.M. Stein and R. Shakarchi, Fourier Analysis, Princeton University Press, Princeton, 2003.
• [25] R. Urbanke, Q. Li, and B. Rimoldi, “On the cardinality of the group of permutations that commute with the Discrete Fourier Transform”, 32nd Allerton Conf. on Communication, Control, and Computing, Monticello, IL, Sept. 28‒30, 1994.
• [26] A.Weil, Number Theory for Beginners, Springer-Verlag, New York, 1985.
• [27] H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).