离散分数傅里叶变换

在建立离散分数傅里叶变换的算法之前，必须对离散傅里叶变换（Discrete Fourier Transform）有一定的理论认识。

对于一般的傅里叶变换具有4周期性质，也就是对任何信号连续做4次傅里叶变换就会回到它自己。然而离散傅里叶变换也有这样的性质，所以以下先讨论离散傅里叶变换的4周期性质。

离散傅里叶变换的矩阵

对于一串数字序列信号${\displaystyle x_{0},x_{1},...,x_{N-1}}$ ，定义它的离散傅里叶变换是：

${\displaystyle y_{m}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi mni}{N}}},m=0,1,...,N-1}$ 

引入矩阵符号

${\displaystyle X={\begin{bmatrix}x_{0}\\x_{1}\\\vdots \\x_{N-1}\end{bmatrix}}\quad Y={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{N-1}\end{bmatrix}}}$ 

${\displaystyle E={\frac {1}{\sqrt {N}}}{\begin{bmatrix}W^{0\times 0}&W^{0\times 1}&\vdots &W^{0\times N-1}\\W^{1\times 0}&W^{1\times 1}&\vdots &W^{1\times N-1}\\\vdots &\vdots &\ddots &\vdots \\W^{N-1\times 0}&W^{N-1\times 1}&\vdots &W^{N-1\times N-1}\\\end{bmatrix}}}$ 

其中 ${\displaystyle W=e^{-{\frac {\pi 2i}{\sqrt {N}}}}}$  ，现在可以把离散傅里叶变换写成： ${\displaystyle Y=EX}$ 

由上面的分析可知一串长度为N的数字序列信号${\displaystyle x_{0},x_{1},...,x_{N-1}}$ ，其离散傅里叶变换在N维向量空间相当于一个线性变换，也就是矩阵E，矩阵E称作离散傅里叶变换的矩阵。又因为

${\displaystyle {\frac {1}{N}}\sum _{l=0}^{N-1}W^{l\times m}\times {\overline {W}}^{l\times n}={\frac {1}{N}}\sum _{l=0}^{N-1}e^{-{\frac {2\pi li}{N}}(m-n)}={\begin{cases}1\quad m=n\\0\quad m\neq n\end{cases}}}$ 

所以 ${\displaystyle EE^{*}=I}$ 

离散傅里叶变换的线性变换是正交变换。

离散傅里叶变换4周期性质的证明

利用离散傅里叶变换的矩阵，可以证明4周期性质。因为

${\displaystyle {\frac {1}{N}}\sum _{l=0}^{N-1}W^{l\times m}\times {\overline {W}}^{l\times n}={\frac {1}{N}}\sum _{l=0}^{N-1}e^{-{\frac {2\pi li}{N}}(m-n)}={\begin{cases}1\quad \mod (m+n)=0\\0\quad \mod (m+n)\neq 0\end{cases}}}$ 

而且${\displaystyle 0\leqslant m,n\leqslant N-1}$ ，所以

${\displaystyle E^{2}={\begin{bmatrix}1&0&\vdots &0\\0&0&\vdots &1\\\vdots &\vdots &\ddots &\vdots \\0&1&\vdots &0\end{bmatrix}}}$ 

由上可知信号${\displaystyle x_{0},x_{1},...,x_{N-1}}$ 做两次离散傅里叶变换后会得到${\displaystyle x_{0},x_{N-1},...,x_{1}}$ ，除了第一个数字不动其余顺序皆颠倒，这意味着发生了时间反射。现在用矩阵来表达连续两次的离散傅里叶变换：

${\displaystyle Z=E^{2}X={\begin{bmatrix}1&0&\vdots &0\\0&0&\vdots &1\\\vdots &\vdots &\ddots &\vdots \\0&1&\vdots &0\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\x_{2}\\\vdots \\x_{N-1}\end{bmatrix}}={\begin{bmatrix}x_{0}\\x_{N-1}\\x_{N-2}\\\vdots \\x_{1}\\\end{bmatrix}}}$ 

再来计算连续三次的变换：

${\displaystyle E^{3}=E^{2}E={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&0&\vdots &0\\0&0&\vdots &1\\\vdots &\vdots &\ddots &\vdots \\0&1&\vdots &0\end{bmatrix}}{\begin{bmatrix}W^{0\times 0}&W^{0\times 1}&\vdots &W^{0\times N-1}\\W^{1\times 0}&W^{1\times 1}&\vdots &W^{1\times N-1}\\\vdots &\vdots &\ddots &\vdots \\W^{N-1\times 0}&W^{N-1\times 1}&\vdots &W^{N-1\times N-1}\\\end{bmatrix}}}$ 

${\displaystyle ={\frac {1}{\sqrt {N}}}{\begin{bmatrix}W^{0\times 0}&W^{0\times 1}&\vdots &W^{0\times N-1}\\W^{N-1\times 0}&W^{N-1\times 1}&\vdots &W^{N-1\times N-1}\\\vdots &\vdots &\ddots &\vdots \\W^{1\times 0}&W^{1\times 1}&\vdots &W^{1\times N-1}\\\end{bmatrix}}}$ 

最后计算连续四次的变换：

${\displaystyle E^{4}=E^{2}\times E^{2}={\begin{bmatrix}1&0&\vdots &0\\0&0&\vdots &1\\\vdots &\vdots &\ddots &\vdots \\0&1&\vdots &0\end{bmatrix}}{\begin{bmatrix}1&0&\vdots &0\\0&0&\vdots &1\\\vdots &\vdots &\ddots &\vdots \\0&1&\vdots &0\end{bmatrix}}={\begin{bmatrix}1&0&\vdots &0\\0&1&\vdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\vdots &1\end{bmatrix}}}$ 

由上式可知，离散傅里叶变换连续做4次一定会让信号返回它自己，这就是离散傅里叶变换4周期性质的证明。

为了得到离散傅里叶变换的周期性定理，必须理解它的运算性质，因此现在用另外一个观点去说明4周期性质。

${\displaystyle U=E^{3}X=E\times E^{2}X}$ 

${\displaystyle ={\begin{bmatrix}W^{0\times 0}&W^{0\times 1}&\vdots &W^{0\times N-1}\\W^{1\times 0}&W^{1\times 1}&\vdots &W^{1\times N-1}\\\vdots &\vdots &\ddots &\vdots \\W^{N-1\times 0}&W^{N-1\times 1}&\vdots &W^{N-1\times N-1}\\\end{bmatrix}}{\begin{bmatrix}1&0&\vdots &0\\0&0&\vdots &1\\\vdots &\vdots &\ddots &\vdots \\0&1&\vdots &0\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\\vdots \\x_{N-1}\end{bmatrix}}}$ 

${\displaystyle ={\begin{bmatrix}W^{0\times 0}&W^{0\times 1}&\vdots &W^{0\times N-1}\\W^{1\times 0}&W^{1\times 1}&\vdots &W^{1\times N-1}\\\vdots &\vdots &\ddots &\vdots \\W^{N-1\times 0}&W^{N-1\times 1}&\vdots &W^{N-1\times N-1}\\\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{N-1}\\x_{N-2}\\\vdots \\x_{1}\\\end{bmatrix}}}$ 

${\displaystyle ={\begin{bmatrix}1&0&\vdots &0\\0&0&\vdots &1\\\vdots &\vdots &\ddots &\vdots \\0&1&\vdots &0\end{bmatrix}}{\begin{bmatrix}W^{0\times 0}&W^{0\times 1}&\vdots &W^{0\times N-1}\\W^{1\times 0}&W^{1\times 1}&\vdots &W^{1\times N-1}\\\vdots &\vdots &\ddots &\vdots \\W^{N-1\times 0}&W^{N-1\times 1}&\vdots &W^{N-1\times N-1}\\\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\\vdots \\x_{N-1}\end{bmatrix}}}$ 

${\displaystyle ={\begin{bmatrix}y_{0}\\y_{N-1}\\y_{N-2}\\\vdots \\y_{1}\end{bmatrix}}}$ 

上面的分析可以理解为原始信号作三次离散傅里叶变换其成分还是跟原本信号相同，只是顺序上做了调整，也就是从第二个信号至最后一个信号作了颠倒的顺序。又或者可以这样理解，原本的信号经过交换顺序而得到${\displaystyle x_{0},x_{N-1},x_{N-2},...,x_{1}}$ ，其离散傅里叶变换就是${\displaystyle y_{0},y_{N-1},y_{N-2},...,y_{1}}$ ，若再做一次离散傅里叶变换，结果就是将${\displaystyle x_{0},x_{N-1},x_{N-2},...,x_{1}}$ 的下标按照前面规则作了交换，连续四次的离散傅里叶变换其结果应该为${\displaystyle x_{0},x_{1},...,x_{N-1}}$ ，由此可知离散傅里叶变换具有4周期的性质。

因此，${\displaystyle E^{4}=1}$  ，即任何数字序列作四次离散傅里叶变换就会返回它自己，在矩阵乘法之下，集合 ${\displaystyle {\begin{Bmatrix}I,E,E^{2},E^{3}\end{Bmatrix}}}$  会构成一个四阶循环群。

定理

离散傅里叶变换的整数次重复运算等价于一个4阶循环矩阵群 ${\displaystyle {\begin{Bmatrix}I,E,E^{2},E^{3}\end{Bmatrix}}}$  。

利用前述离散傅里叶变换的计算方法可以得到离散分数傅里叶变换的计算方法，因此接下来的分析就先从离散傅里叶变换出发。

推导

根据离散傅里叶变换的矩阵形式，定义符号：

${\displaystyle X^{(l)}={\begin{bmatrix}x_{0}^{(l)}\\x_{1}^{(l)}\\\vdots \\x_{N-1}^{(l)}\end{bmatrix}},l=0,1,2,3}$ 

其递回关系为：

${\displaystyle X^{(l+1)}=EX^{(l)}=E^{l+1}X^{(0)},l=0,1,2,3}$ 

当 ${\displaystyle l=0}$  时，对应的是原始数字序列信号；当 ${\displaystyle l=1}$  时，对应的昰原始数字序列信号的离散傅里叶变换。现在定义幂次a的离散分数傅里叶变换为：

${\displaystyle X^{(a)}=\sum _{l=0}^{3}A_{l}(a)X^{(l)}=(\sum _{l=0}^{3}A_{l}(a)E^{l})X^{(0)}}$ 

上式中的 ${\displaystyle A_{j}(a),j=0,1,2,3}$  是a的连续函数。引入矩阵符号为：

${\displaystyle E^{a}=\sum _{l=0}^{3}A_{l}(a)E^{l}}$ 

称作矩阵E的a次幂，因此幂次a的离散分数傅里叶变换可以写成：

${\displaystyle X^{(a)}=E^{a}X^{(0)}}$ 

其中 ${\displaystyle A_{j}(a),j=0,1,2,3}$  是只与a有关的系数，它使得 ${\displaystyle a\in R^{+},F_{s}^{a}}$  全体生成的矩阵族 ${\displaystyle {\begin{Bmatrix}F_{s}^{a},a\in R^{+}\end{Bmatrix}}}$  满足以下公理。

1. 连续性公理： ${\displaystyle \forall a\in R,E^{a}:C^{N}\to C^{N}}$  为连续的；
2. 边界性公理： ${\displaystyle \forall a\in R,E^{a}}$  是离散傅里叶变换连续作用a次的结果；
3. 周期性公理： ${\displaystyle \forall a\in R,n\in N,E^{a}=E^{a+4n}}$  ；
4. 可加性公理： ${\displaystyle \forall a,b\in R,E^{a}E^{b}=E^{b}E^{a}=E^{a+b}}$  。

由以上可得连续函数 ${\displaystyle A_{j}(a),A_{i}(b),i,j=0,1,2,3}$  的方程组：

${\displaystyle {\begin{cases}A_{0}(a+b)=A_{0}(a)A_{0}(b)+A_{1}(a)A_{3}(b)+A_{2}(a)A_{2}(b)+A_{3}(a)A_{1}(b)\\A_{1}(a+b)=A_{0}(a)A_{1}(b)+A_{1}(a)A_{0}(b)+A_{2}(a)A_{3}(b)+A_{3}(a)A_{2}(b)\\A_{2}(a+b)=A_{0}(a)A_{2}(b)+A_{1}(a)A_{1}(b)+A_{2}(a)A_{0}(b)+A_{3}(a)A_{3}(b)\\A_{3}(a+b)=A_{0}(a)A_{3}(b)+A_{1}(a)A_{2}(b)+A_{2}(a)A_{1}(b)+A_{3}(a)A_{0}(b)\end{cases}}}$ 

为了解得这个方程组的解，先做变数变换：

${\displaystyle {\begin{bmatrix}B_{0}(a)\\B_{1}(a)\\B_{2}(a)\\B_{3}(a)\end{bmatrix}}={\begin{bmatrix}1&i&1&1\\1&-i&-1&i\\1&1&1&-1\\1&i&-1&-i\end{bmatrix}}{\begin{bmatrix}A_{0}(a)\\A_{1}(a)\\A_{2}(a)\\A_{3}(a)\end{bmatrix}}}$ 

则方程组可表达为： ${\displaystyle B_{l}(a+b)=B_{l}(a)B_{l}(b),l=0,1,2,3}$ 

同时又由边界性公理可得： ${\displaystyle A_{(}m)=\delta (m-l)={\begin{cases}1\quad m=l\\0\quad m\neq l\end{cases}}}$ 

因此 ${\displaystyle B_{l}(a),l=0,1,2,3}$  的边界条件就是： ${\displaystyle B_{l}(m)=e^{-{\frac {2\pi lmi}{4}}}}$ 

此外周期性条件为： ${\displaystyle B_{l}(a+4)=B_{l}(a)}$ 

考虑了这些条件后方程组 ${\displaystyle B_{l}(a+b)=B_{l}(a)B_{l}(b),l=0,1,2,3}$  有唯一解：

${\displaystyle B_{l}(a)=e^{-{\frac {2\pi lai}{4}}},j=0,1,2,3}$ 

最后再根据

${\displaystyle {\begin{bmatrix}B_{0}(a)\\B_{1}(a)\\B_{2}(a)\\B_{3}(a)\end{bmatrix}}={\begin{bmatrix}1&i&1&1\\1&-i&-1&i\\1&1&1&-1\\1&i&-1&-i\end{bmatrix}}{\begin{bmatrix}A_{0}(a)\\A_{1}(a)\\A_{2}(a)\\A_{3}(a)\end{bmatrix}}}$ 

得到方程组的通解为：

${\displaystyle A_{l}(a)={\frac {1}{4}}{\frac {1-e^{-2\pi (a-l)i}}{1-e^{-{\frac {2\pi (a-l)i}{4}}}}}=\cos({\frac {(a-l)\pi }{4}})\cos({\frac {2(a-l)\pi }{4}})e^{-{\frac {3i(a-l)\pi }{4}}},l=0,1,2,3}$ 

所以满足前述4个公理的矩阵E之a次幂定义为：

${\displaystyle E^{a}=\sum _{l=0}^{3}\cos({\frac {(a-l)\pi }{4}})\cos({\frac {2(a-l)\pi }{4}})e^{-{\frac {3i(a-l)\pi }{4}}}E^{l}}$ 

结果

上式得到了 ${\displaystyle E^{a}}$  的离散形式并把它带入 ${\displaystyle X^{(a)}=E^{a}X^{(0)}}$  最后得到了离散分数傅里叶变换的计算方法：

${\displaystyle X^{(a)}=(\sum _{l=0}^{3}\cos({\frac {(a-l)\pi }{4}})\cos({\frac {2(a-l)\pi }{4}})e^{-{\frac {3i(a-l)\pi }{4}}}E^{l})X^{(0)}}$ 

若去对照分数傅里叶变换的形式，上式的计算方法可以说是C.C.Shih的分数傅里叶变换的离散算法。

• 傅里叶变换
• 分数傅里叶变换
• 离散傅里叶变换

• 冉启文. 小波变换与分数傅里叶变换理论及应用. 哈尔滨工业大学出版社. 2001: 262–268. ISBN 9787560316031.