- 學位論文
交替矩陣與離散分數信號轉換
Commuting Matrices and Discrete Fractional Signal Transforms
摘要
許多離散時間訊號轉換有重複之特徵值。例如，離散傅立葉轉換(DFT)矩陣只有四個不同的特徵值{+1, -j, -1, +j }。因此，為了利用特徵分解來定義此類離散信號轉換之分數型轉換，我們必須先解決其特徵向量模糊的問題。為達此目的，Pei與Yeh利用一個離散傅立葉轉換之近似三對角交換矩陣(此矩陣最早是由Dickinson及Steiglitz二人發現）來定義離散分數傅立葉轉換(discrete fractional Fourier transform)。由Dickinson-Steiglitz之離散傅立葉轉換交替矩陣，我們可決定唯一的一組離散傅立葉轉換特徵向量基底。而且，Dickinson-Steiglitz矩陣的特徵向量近似於連續Hermite-Gaussian函數之取樣值。這使得Pei與Yeh定義的離散分數傅立葉轉換近似於連續分數傅立葉轉換之取樣值。但是，Dickinson-Steiglitz矩陣之具有較多零交叉點的特徵向量並無法有效地近似於高階的連續Hermite-Gaussian函數。 本論文中，我們提出一個新的離散傅立葉轉換近似三對角交替矩陣。該離散傅立葉轉換交替矩陣之特徵向量比Dickinson-Steiglitz矩陣更接近於連續Hermite-Gaussian函數之取樣值。有了這個新的離散傅立葉轉換交替矩陣，我們可決定唯一的一組離散傅立葉轉換特徵向量基底。而且，經由適當地線性組合二個獨立的近似三對角離散傅立葉轉換交替矩陣，我們可建構出一組新的近似三對角離散傅立葉轉換交替矩陣，且該組新的離散傅立葉轉換交替矩陣之特徵向量更接近連續Hermite-Gaussian函數。由此，我們可以定義出更接近連續分數傅立葉轉換的離散分數傅立葉轉換。 其次，我們提出二種建構任意階離散傅立葉轉換交替矩陣的方法，該二種方法都是先前Candan相關結果的延伸。我們所提出的任意階離散傅立葉轉換交替矩陣具有比前述的近似三對角離散傅立葉轉換交替矩陣更接近於連續Hermite-Gaussian函數的特徵向量。但是，任意階離散傅立葉轉換交替矩陣的結構比近似三對角離散傅立葉轉換交替矩陣複雜。 離散分數傅立葉轉換為傳統離散傅立葉轉換之推廣，因為它比傳統離散傅立葉轉換多一個額外的參數。本論文中，我們進一步推廣離散分數傅立葉轉換，使其具有N個參數，其中N為輸入信號之點數。我們證明此多參數離散分數傅立葉轉換(MPDFRFT)符合所有分數轉換須具備之性質。我們並利用多參數離散分數傅立葉轉換之多參數性質來提高雙隨機相位編碼加密法之安全性。 最後，前人已知 I、IV、V與VIII型的離散餘弦轉換(DCT)及離散正弦轉換(DST)矩陣都只有二個不同的特徵值（即+1與-1）。為了解決此類離散餘弦及正弦轉換矩陣之特徵向量模糊問題，本論文針對I、IV、V與VIII型的離散餘弦及正弦轉換矩陣各導出二個具有類似Hermite-Gaussian特徵向量的線性獨立三對角交替矩陣。基於這些新的三對角交替矩陣，我們可定義此類離散餘弦及正弦轉換之分數型轉換。此外，我們也發現離散分數傅立葉轉換、分數廣義離散傅立葉轉換（fractional generalized DFT）、分數離散餘弦及正弦轉換之新的關係式，這些新的關係式可使離散分數傅立葉轉換與分數廣義離散傅立葉轉換的計算量減少一半。
並列摘要
Many discrete signal transforms have multiple eigenvalues. For example, the discrete Fourier transform (DFT) matrix has only four distinct eigenvalues: {+1, -j, -1, +j}. Consequently, to define fractional versions of such discrete signal transforms based on eigendecompositions, we must resolve their eigenvector ambiguity problems. To achieve this purpose, Pei and Yeh defined the discrete fractional Fourier transform (DFRFT) based on a nearly tridiagonal DFT-commuting matrix, which was first discovered by Dickinson and Steiglitz. From the Dickinson-Steiglitz DFT-commuting matrix, an orthonormal eigenvector basis of the DFT can be uniquely determined. Furthermore, the eigenvectors of the Dickinson-Steiglitz matrix are similar to samples of the continuous Hermite-Gaussian functions (HGFs). As a result, transform results of the DFRFT defined by Pei and Yeh are sample approximations of the continuous fractional Fourier transform (FRT). However, eigenvectors of the Dickinson-Steiglitz matrix with larger numbers of zero-crossings cannot well approximate the higher order continuous HGFs. In this dissertation, we propose a new nearly tridiagonal DFT-commuting matrix whose eigenvectors are closer to samples of the continuous HGFs than those of the Dickinson-Steiglitz matrix. With the new nearly tridiagonal DFT-commuting matrix, an orthonormal eigenvector basis of the DFT can be uniquely determined. Furthermore, by linearly combining two independent nearly tridiagonal DFT-commuting matrices, we construct a set of nearly tridiagonal DFT-commuting matrices whose eigenvectors are even closer to the continuous HGFs. New versions of the DFRFT whose transform outputs are more similar to samples of the continuous FRT can then be defined. Secondly, two methods, which are extensions of a previous work of Candan, are developed to construct the arbitrary-order DFT-commuting matrices. The resulting arbitrary-order DFT-commuting matrices are shown to possess eigenvectors which are even more accurate sample approximations of the continuous HGFs than those of the nearly tridiagonal DFT-commuting matrices previously described. However, the matrix structures of the arbitrary-order DFT-commuting matrices are more complicated than those of the nearly tridiagonal DFT-commuting matrices. The DFRFT is a generalization of the DFT with one additional order parameter. In this dissertation, we further generalize the DFRFT to have N order parameters, where N is the number of input data points. This multiple-parameter DFRFT (MPDFRFT) is shown to have all of the desired properties for fractional transforms. The multiple-parameter property of the MPDFRFT is exploited to enhance security of the double random phase encoding encryption scheme. Finally, it is known that the DCT and DST matrices of types I, IV, V, and VIII all have only 2 distinct eigenvalues: +1 and -1. To resolve eigenvector ambiguity problems for these DCT and DST matrices, two new independent tridiagonal commuting matrices with Hermite-Gaussian-like eigenvectors for each of the DCT and DST matrices of types I, IV, V, and VIII are derived in this dissertation. Fractional versions of these DCT and DST matrices can then be defined based on their new tridiagonal commuting matrices. New relationships among the DFRFT, the fractional generalized DFT (GDFT), the fractional DCT and the fractional DST matrices are developed to reduce half of the required computations for the DFRFT and fractional GDFT.