DOT快速算法及其通用架构设计

黄 海，刘红雨，邢 琳，那 宁，李春宝

(1.哈尔滨理工大学 软件与微电子学院，哈尔滨 150080；2.哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080)

0 引 言

DOT主要分为两大类，即离散非正弦类正交变换和离散正弦类正交变换。其中正弦类一直是数字信号处理领域的研究热点，主要包括离散 Hartley 变换(DHT)、离散傅里叶变换(DFT)、离散余弦变换(DCT)、和离散正弦变换(DST)等[1]。

为了满足图像和视频领域的要求，许多正交变换快速算法被提出。最早出现的快速算法大多是通过计算FFT间接得到其他正交变换[2-3]，由于FFT算法本身存在许多的复数乘法，因此这种方法总有一定的局限性。随后，许多利用矩阵分解来计算正交变换的方法相继被提出[4-5]，虽然很大程度上降低了计算复杂度，但是难于扩展到大点数DOT，并未得到广泛使用。为了实现算法的可扩展性，许多针对序列长度N=2n和N≠2n的DOT快速算法相继被提出[6-7]。如基-r的DOT快速算法、基于混合基DOT快速算法，以上计算序列长度N≠2n的DOT快速算法不具有通用性且算法计算复杂度较高。相比之下，对于序列长度为N=2n的DOT快速算法多是采用分治策略[8]，通过奇偶分解法将长序列分解成两个大小相等的短序列，之后再利用变换核函数自有的特点，进而降低了计算复杂度。但多数都是基于乘法器的，不易于VLSI的实现，所以也并未得到广泛应用。在此基础上，文[9]提出一种通过向量编码来计算DOT的快速算法,文[10]一种基于分裂基的DOT快速算法。归纳以上DOT快速算法，都存在以下问题：许多算法都是针对具体点数的DOT，没有考虑到可扩展性；……