臺灣博碩士論文加值系統

本篇論文由三部分組成，在第一部分中，我們將討論數論中的兩個主題，分別是高斯和以及拉瑪努江和。我們不但要討論這兩個和的基本特性，還要研究它們在數位訊號處理的應用，尤其是在數位傅立葉轉換中的應用。由於數論轉換在某些特性上跟數位傅立葉轉換很像，所以我們也會提到它。
本論文的第二部分是在探討快速的位元反轉演算法，使用的方法是向量式的計算。這個新方法利用了MATLAB在計算向量方面的優勢，可以用短短的四行程式來實現。
最後，我們在第三部分將專注於退化四元數，又稱雙複數。雙複數有兩種運用，一個用在陣列信號處理，另一個則用在四元有限場轉換。前者跟著名的MUSIC演算法有關， 後者則是跟複數數論轉換有關。

This dissertation is composed of three parts. The first part discusses two topics in number theory, Gauss Sum and Ramanujan Sum, respectively. We will not only research some basic properties of these Sums, but also study their applications in digital signal processing, especially in discrete Fourier Transform (DFT). Because Number Theoretic Transform (NTT) has similar traits with DFT, we will also talk about it.
The second part of this dissertation discusses the topic in the efficient bit and digital reversal algorithm, using vector calculation. The novel algorithm takes the advantage of MATLAB’s vector characteristics and can be implemented by no more than 4 lines MATLAB procedures.
Finally, we will focus on Reduced Biquaternions (RB), also called Bicomplex numbers, in the third part of this paper. There are two applications to the RB. One is array processing and the other is quaternion finite field transform. The former is related to the MUSIC algorithm; the latter is similar to complex NTT.

Contents
Part A Number theory and its applications in DFT……………………………………………1
Chapter 1 Using Gauss Sequence to calculate eigenvectors of Normalized DFT matrix…... ……………………………………3
1.1 Introduction……………………………. 3
1.2 Definition………………………………...4
1.3 Construct eigenvectors of Normalized DFT matrix with odd N………………...4
1.4 Construct eigenvectors of Normalized DFT matrix with even N………………10
Chapter 2 Using Gauss Sequence to calculate eigenvectors of Normalized NTT matrix………………………………………..12
2.1 Introduction…………………………. .12
2.2 Definition………………………………12
2.3 Construct eigenvectors of NTT matrix with p=4k+3...........................................13
2.4 Construct eigenvectors of NTT matrix with p=4k+1…………………………...19
2.5 Conclusion and Future work…………21
Reference…………………………………….23
Chapter 3 Odd Ramanujan Sums of the Complex Roots of Unity…………………….25
3.1 Introduction…………………………...25
3.2 Odd Signals (mod r) and their Fourier Coefficients…………………………….26
3.3 Z-Domain Characteristic of Odd Signal and Odd Ramanujan Sums……….….32
3.4 Conclusion………………………..……33
Reference…………………………………….33
Appendix…………………………………….35
Part B Fast Bit and Digital Reversal Algorithm…..37
Chapter 4 Efficient Bit and Digital Reversal Algorithm using Vector Calculation……….39
4.1 Introduction……………………….…..39
4.2 Using vector calculation…………...…40
4.3 Table look-up method……...…………41
4.4 Generalization to digit reversal…...…43
4.5 New in-place algorithm……..………..44
4.6 Comparison…………..……………….45
4.7 Conclusion…………………………….47
Reference……………………………………47
Part C Reduced Biquaternions…………………….49
Chapter 5 Bicomplex MUSIC for Vector-Sencor Array Processing…………...51
5.1 Introduction………………………….51
5.2 The Bicomplex algebra………...……51
5.3 Polarization Model……….………….52
5.4 Bicomplex Covariance Matrix and BMUSIC……………………………...54
5.5 Simulation Results…………...………56
5.6 Conclusion and Future work………..57
Reference…………………………………….57
Chapter 6 The Quaternion Finite Field Transforms…………………………………..61
6.1 Introduction……………………...…61
6.2 The RB over GF(q)…………………61
6.3 Finite Field Transform over GF (q4)…………………………………...63
Reference…………………………………….63

[1] J. H. McClellan and T. W. Parks, “Eigenvalue and eigenvector decomposition of the discrete Fourier transform,” IEEE Trans. Audio Electroacoust., vol. AU-20, pp. 66-74,1972
[2] B. W. Dickinson and K. Steiglitz, “Eigenvectors and functions of the discrete Fourier transform,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-30, pp. 25-31, Feb. 1982
[3] 溫家昶, “Closed-form eigenvectors of Discrete Fourier and Number Theoretic Transform”, Master thesis in Graduate Institute of Communication Engineering, National Taiwan University, 2002.
[4] A. Terras, Fourier analysis on finite groups and applications, Ch8 1999, Cambridge University Press
[5] D. T. Birtwistle, “The eigenstructure of the number theoretic transforms”, Signal Processing, vol. 4, No. 4, pp. 287-294, 1982
[6] I. S. Reed and T. K. Truong, “The use of finite fields to compute convolutions,”IEEE Trans. Inform. Theory,
vol. IT-21, pp. 208–213, 1975.
[7] B. C Berndt, R. J. Evans, and K. S. Williams, Gauss and Jacobi Sums, Ch1 1998, A Wiley-Interscience publication
[1] E. Cohen,” A class of arithmetical functions”, Proc. Nat. Acad. Sci. U.S.A., vol. 41, 1955, pp. 939-944.
[2] E. Cohen, “Representations of even functions . I. Arithmetical identities,” Duke Math. J., vol. 25, pp. 401-421, 1958.
[3] Alan V. Oppenheim and Ronald W. Schafer with John R. Buck, Discrete-Time Signal Processing, 2nd ed. Prentice Hall International Editions, 1989.
[4] S. Ramanujan, “On certain trigonometrical sums and their application in the theory of numbers,” Trans. Comb. Phil. Soc., vol. 22, pp. 259-276, 1918
[5] M. Planat, H. Rosu, and S. Perrine, “Ramanujan sums for signal processing of low-frequency noise,” Phys. Rev. E, vol. 66, p. 51128, 2002.
[6] Saed Samadi, M. Omair Ahmad, and M. N. S. Swamy, “Ramanujan Sums and Discrete Fourier Transforms,” IEEE Signal Processing Letters, vol. 12, no. 4, pp. 293-296, April 2005.
[1] A. Karp, “Bit reversal on uniprocessors,” SIAM Rev., vol. 38, no. 1, pp. 1-26, Mar. 1996.
[2] A. Elster, ”Fast bit-reversal algorithms,” in Proc, ICASSP’89, 1989, pp.1099-1102.
[3] D. Evans, “An improved digital-reversal permutation algorithm for the fast fourier transforms,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-35, pp. 1120-1125, Aug.1987.
[4] D. Evans, “A second improved digital-reversal permutation algorithm for the fast fourier transforms,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 37, pp. 1288-1291, Aug. 1989.
[5] J. Walker, “A new bit-reversal algorithm," IEEE Trans. Signal Processing, vol. 38, pp. 1472-1473, Aug. 1989.
[6] P. Duhamel and J. Prado, “A connection between bit-reverse and matrix transpose, hardware and software consequences,” in Proc, ICASSP’88, 1988, pp. 1403-1406.
[7] B. Gold and B. Rader, Digital Processing of Signal. New York:McGraw-Hill, 1969.
[8] A. Yong, “A better FFT bit-revesal algorithm without tables,” IEEE Trans. Signal Processing, vol. 39. pp. 2365-2367, Oct. 1991.
[9] M. Orchard, “Fast bit-reversal algorithms based on index representations in gf(2b),” IEEE Trans. Signal Processing, vol. 40, pp. 1004-1008, Apr. 1992.
[10] J. Rius and R. D. Porrata-Dorin, “New FFT bit-reversal algorithm,” IEEE Trans. Signal Processing, vol. 49, pp. 251-254, Jan. 2001.
[11] K. Drouiche, “A new efficient computational algorithm for bit reversal mapping," IEEE Trans. Signal Processing, vol. 49, pp. 251-254, Jan. 2001.
[12] J. Prado, “A new fast bit-reversal permutation algorithm based on a symmetry" IEEE Signal Processing Letters, vol. 11, pp. 933-936, Dec. 2004.
[1] Schtte, H.-D., Wenzel, J., “Hypercomplex numbers in digital signal processing”, IEEE International Symposium on Circuits and Systems, 1990 pp. 1557-1560 vol.2
[2] Clyde M. Davenport, “A communicative Hypercomplex Algebra with Associated Function Theorey”, In R. Ablamowicz, editor, Clifford Algebra with Numeric and Symbolic Computations, pp. 213~227. Birkhauser, Boston, 1996.
[3] Sebastian. Miron, Nicolas Le Bihan, and Jérôme I. Mars, “Quaternion-MUSIC for Vector-Sensor Array Processing”, IEEE Transactions on Signal Processing, vol. 54, NO. 4, April 2006. pp. 1218-1229.
[4] Ralph O. Schmidt, “Multiple Emitter Location and Signal Parameter Estimation”, IEEE Transactions on Antennas and Propagation, vol. AP-34, No. 3, March 1986. pp 276-280.
[5] JH Chang, “Applications of Quaternions and Reduced Biquaternions for Digital Signal and Color Image Processing” Doctoral dissertation in Graduate Institute of Communication Engineering, National Taiwan University, 2004.
[1] I. S. Reed and T. K. Truong, “The use of finite fields to compute convolutions,”IEEE Trans. Inform. Theory, vol. IT-21, pp. 208–213, 1975.