论文部分内容阅读
矩阵理论已广泛用于工程领域,是一种不可替代的数学工具。哈达玛矩阵是其中最重要的一类,与其它典型矩阵如协商矩阵(Conference matrices)、循环矩阵(Circulent matrices)、循环权重矩阵(Circulent Weighting matrices)、Pn-矩阵等广泛用于信号处理、图像处理、编码设计等领域。以中心权重哈达玛矩阵为出发点,Moon Ho Lee于1989年提出“Jacket矩阵”。这一类矩阵具有求逆简单(比特翻转求逆)和行/列正交的优异性质,已在信号处理、通信、图像压缩、密码学等领域中发挥了非常重要的作用。大部分信号矩阵,如离散傅里叶变换( Discrete Fourier Transform)、离散余弦变换(Discrete Cosine Transform)、Slant和Haar矩阵都从属于Jacket矩阵家族。
本论文的工作是围绕“Jacket矩阵”来展开,并结合了抽象代数、组合数学、著名的斐波那契数列以及离散傅里叶变换等理论,构造了两类新的Jacket矩阵,并研究了相应矩阵的快速分解与构造算法,同时探讨了基于质数因子算法的离散傅里叶矩阵快速变换。具体内容结构如下:
1.构造基于有限域GF(p)的斐波那契Jacket矩阵。首先定义有限域GF(p)上的斐波那契数列,按照给定的行线性关系构造斐波那契Jacket矩阵。然后定义了基本矩阵,并以此为基础,探讨高阶斐波那契Jacket矩阵的快速构造与快速分解算法。
2.提出基于质数因子算法的离散傅里叶矩阵快速算法。根据离散傅里叶矩阵从属于Jacket矩阵这一性质,在质数因子算法基础上,提出离散傅里叶矩阵快速分解与构造算法。
3.利用中国剩余定理对离散傅里叶矩阵进行指数映射,证明映射后的离散傅里叶矩阵满足Cocyclic定义,由此构造出Cocyclic离散傅里叶矩阵,并研究相应的矩阵构造(分解)算法。
本文所构造的斐波那契Jacket矩阵和Cocyclic离散傅里叶矩阵,均属于Jacket矩阵家族。针对构造矩阵所提出的快速算法,在形式上清晰简单,仅牵涉到稀疏矩阵之间的Kronecker积和普通乘积。此外,基于质数因子算法的离散傅里叶矩阵快速变换也具有同样类似的稀疏矩阵形式。在运算量方面,每一种快速算法都与直接计算做了比较,并且优势明显,而且当矩阵阶数越大,所节省的运算量就越大。