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，没有考虑到可扩展性；过于追求降低算法复杂度，而忽略了算法的VLSI实现的。

现如今，人们对图像、视频的处理速度以及质量要求越来越高，一种正交变换编码已经不能满足需求[11-12]。将多种正交变换相互结合，充分发挥各自的优点，已经势在必行。上述方法的实施关键是正交变换通用架构的设计。目前也存在许多的通用架构，Chiper 等提出基于存储器的DCT-DST通用架构[13]；Wu 等提出一种低运算复杂度、低硬件复杂度的DCT-IDCT的通用架构[14]；刘媛媛等提出一种立体类蝶形运算的DCT-IDCT通用架构[15]；Wang等通过数学公式重构了FFT和DCT的公式，并设计了FFT-IFFT-DCT-IDCT通用架构[16]；Singh等提出了一种基于图像压缩的DCT-IDCT通用架构[17]；Feng等提出一种基于自适用编码CORDIC的低功耗、高PSNR的DCT-IDCT通用[18]架构。以上通用架构虽然可以实现多种正交变换，但存在以下缺点：硬件复用率比较低，控制电路比较复杂，不同的正交变换的变换核函数不同。

本文通过奇偶分解法，提出了一种可实现任意2的幂次点数的基于CORDIC的基-2DOT快速换算法，其变换核函数是旋转角度为等差序列的CORDIC单元。该算法利用变换核函数固有的特性降低了计算复杂度，具有易于VLSI硬件实现、硬件复杂度低、可扩展性强、易于流水线设计、易于模块化设计等优点。在该算法的基础上，设计了一种DOT通用架构，该架构可以同时实现DHT、DFT、DCT、IDCT、DST、IDST六种正交变换，且具有硬件复用率高、不同类型的DOT变换核函数相同、可扩展性强等优点。

1 基于CORDIC的DOT快速算法研究

1.1 基于CORDIC的基-2DHT快速算法研究

1.1.1 基-2DHT快速算法推导

DHT的计算见式(1)。

(1)

先按照n的奇偶把信号分成以下两组，

(2)

则DHT的计算公式可以重新写成：

(3)

其中，k=0,…,N-1。

(4)

其中YH(k)，ZH(k)分别表示N/2点DHT，且周期为N/2。

由于，

(5)

将式(3)重新写为：

(6)

即，N点DHT被分解成N/2点DHT。

由式(6)可得式(7)。

(7)

即,

(8)

其中，

(9)

可以看出，N点DHT最终可以分解为2点DHT。因此将该算法定义为基于CORDIC的基-2 DHT快速算法，该算法可以扩展到任意N=2n点DHT。此外，从式(9)可以看出N点DHT的变换核为：旋转角度为等差序列的CORDIC运算单元。对于VLSI硬件实现而言，由于该算法中只有加减法和CORDIC运算单元，而CORDIC运算单元VLSI实现只需要移位和加法，因此非常易于VLSI实现。

1.1.2 基-2DHT快速算法的信号流图

根据上述算法，可以得到N点DHT快速算法流程图，如图1所示。

图1 N点DHT快速算法流程图Fig.1 Signal flow of the N-point DHT

1.1.3 基-2DHT快速算法性能分析

本文提出的基于CORDIC的DHT快速算法，是将高阶DHT分解为低阶DHT，从而简化算法，有效降低算法的复杂度。计算N点DHT可以通过两个N/2点DHT，N/4-1个CORDIC运算单元以及N次加法来实现。因此计算N点DHT需要的CORDIC运算单元数及加法如式(10)所示：

(10)

为了对本文提出的算法进行评估，将本文的算法与现有的算法[2,4,6]在算法复杂度，是否易于流水线设计，可扩展性进行了比较。比较结果如表1所示。

表1 本文算法与现有的DHT快速算法比较结果Tab.1 Comparisons among the proposed algorithm and the existed DHT fast algorithms

1.2 基于CORDIC的基-2DFT快速算法研究

1.2.1 基-2DFT快速算法推导

(11)

1.2.2 基-2DFT快速算法的信号流图

根据上述算法，可以得到N点DFT快速算法流程图，如图2所示。

图2 N点DFT快速算法流程图Fig.2 Signal flow of the N-point DFT

1.2.3 基-2DFT快速算法的信号流图

本文提出的基于CORDIC的DFT快速算法,在现有的FFT算法基础上，将复数乘法转化成CORDIC运算单元，有效降低算法的复杂度且易于VLSI实现。为了对本文提出的算法进行评估，将本文的算法与现有的算法[9-10]在算法复杂度，是否易于流水线设计，可扩展性进行了比较。比较结果如表2所示。

表2 本文算法与现有的DFT快速算法比较结果Tab.2 Comparisons among the proposed algorithm and the existed DFT fast algorithms

此外，作者在文[19]中已经推导出基于CORDIC的基-2 DCT-Ⅱ、基-2 DST-Ⅱ、基-2 DST-Ⅲ/DST-Ⅲ的快速算法并实现。

2 基于CORDIC的正交变换通用架构设计

2.1 CORDIC设计

由于CORDIC算法只有加减和移位操作，因此非常易于硬件实现。且具有VLSI实现的规则化、模块化等要求；具有规则的数据流，易于流水线实现等优势。目前，CORDIC的实现方式主要有重叠结构和非重叠结构两种。重叠结构节省硬件资源、面积以及功耗比较低，但是难于流水线设计、运算速度较慢、吞吐率低。而非重叠结构，解决了迭代结构的弊端，但是存在精度和迭代的次数相互矛盾问题。本文采用第二种结构，并基于此进行完善与改进，改善其存在的问题。

对于CORDIC算法，为了将一个向量(x,y)旋转角度θ，θ分解为一系列可通过移位操作来实现的角度的加权和，其计算公式

(12)

则向量旋转可通过以下迭代方式实现。

xi+1=xi-σi·yi·2-i

yi+1=yi+σi·xi·2-i

(13)

在此基础上还需要将所得结果乘以比例因子，如式(14)所示：

xi+1=xi(1+γi·Fi)

yi+1=yi(1+γi·Fi)

(14)

其中：γi=(0,1,-1),Fi=2-i。

由此可知CORDIC的计算只需要移位和加法操作。由于DOT计算过程中使用的CORDIC是固定旋转角度且是等差序列，在实现过程中有一些角度是可以忽略的。将所需旋转的固定角度进行角度编码，用最小的旋转次数得到最佳的旋转结果，这也是与传统COEDIC的最大区别。表3给出了3种旋转角度的角度编码，包括迭代的次数和取值。

表3 3种旋转角度的角度编码[17]Tab.3 Angle coding for three rotation angles[17]

2.2 CORDIC模块化及复用设计

本文提出的算法是以旋转角度为等差序列的CORDIC为变换核函数，根据这一特点，采用三角函数，可以对不同旋转角度的CORDIC进行模块化设计，可以大幅度减少CORDIC运算单元的数量。

以16点DOT为例，按照本章提出的算法，共有24种不同类型的CORDIC运算单元，如表4所示。按照文[19]中公式(3-7),可以将CORDIC较少为14种，除了-π/32…-7π/32以外还有-π/8…-7π/8，利用文[19]中公式(3-10)旋转-3π/32可通过旋转-π/16和-π/32得到、旋转-5π/32可通过旋转-π/8和-π/32得到，如式(15)所示；利用文[19]中公式(3-8)旋转-3π/16可通过旋转-π/16之后再进行一次蝶形运算得到、旋转-7π/32可通过旋转-π/32之后再进行一次蝶形运算得到，如式(16)所示；其中旋转角度为-π/4、-π/2、-3π/4的CORDIC值均为常数，利用文[19]中公式(3-10)可以间接计算-3π/8、-5π/8、-7π/8，如式(17)所示。从式(15)、式(16)和式(17)可以看出，采用三种CORDIC即旋转角度分别为-π/8、-π/16、-π/32就可以实现16点DOT的计算。

对于16点DOT，计算旋转角度为-3π/32、-5π/32、-3π/16、-7π/32、-3π/8、-5π/8和-7π/8的CORDIC流程图如图3所示。可以看出，对于16点DOT只需要三种类型的CORDIC(-π/8)、CORDIC(-π/16)和CORDIC(-π/32)。通过复用设计思想，可以进一步降低了硬件复杂度[20]。

(15)

(16)

(17)

表4 N点DOT用到的旋转角度Tab.4 Rotation angles for 16-point DOT

图3 旋转角度为-3π/32、-5π/32、-3π/16、-7π/32、 -3π/8、-5π/8和-7π/8 CORDIC 流程图Fig.3 Signal flow of the CORDIC with -3π/32、 -5π/32、-3π/16、-7π/32、-3π/8、-5π/8 and -7π/8 angle rotation

2.3 16点DOT通用架构设计

本节以16点DOT为例介绍其通用架构设计。通过上述分析可知，对于16点DOT可以通过三种类型的CORDIC实现，不同的正交变化可以选择不同的CORDIC及相应的互连网络，16点DOT通用架构如图4所示。通用架构包括蝶形运算阵列、CORDIC阵列(含互连网络)、多路选择器阵列和控制器。

图4 16点DOT通用架构Fig.4 Unified architecture of the 16-point DOT

3 功能仿真与实验结果分析

3.1 DOT通用架构的功能仿真

为了验证DOT通用架构的功能是否正确，对设计的架构进行进行Verilog HDL建模，以DHT算法为例，利用Modelsim对DHT算法进行功能仿真，仿真结果如图5所示，图中clk为整个程序的时钟控制信号，信号open为整个程序的开始信号，open为1时整个程序开始运行，信号reset为复位信号，reset为0时进行复位，o0～o15为输出信号。通用架构可以通过控制信号sel来控制不同DOT算法的切换。当控制信号为1时，DOT通用架构执行DHT算法。与此同时，将测试文件产生的随机数输入到Matlab，并得到正确结果如图6所示。将Modelsim的仿真结果和Matlab产生的结果相比较，从仿真结果可以看出，本文提出的快速算法在误差允许的范围内，与正确结果基本保持一致。

图5 DOT通用架构的DHT算法仿真结果Fig.5 Accuracy of the 16-point DHT and DFT

图6 DHT的Matlab计算结果Fig.6 Matlab calculation results of DHT

3.2 DOT通用架构性能分析

本节对所设计的通用架构与现有的通用架构[14-17]在变换的种类、运算单元、控制复杂度、模块化及流水线实现等方面进行了比较。表5给出了比较结果。

1)变换种类：本文提出的架构可同时实现DHT、DFT、DCT、IDCT、DST、IDST六种正6种DOT的变换，而文[14]～[17]可实现的变换种类都少于本文提出的架构。

2)控制复杂度：本文提出的架构采用多路选择器即可实现不同正交变换间的切换。与文[14]需要较复杂的存储单元、文[15]需要特定的处理单元、文[16]需要地址发生器相比，其控制复杂度较低。

表5 与现有通用架构的性能比较Tab.5 Comparison with existing architectures

3)模块化：本文提出的通用架构采用的CORDIC，其旋转角度为等差序列，可以利用三角函数大幅度降低CORDIC的类型，有效的降低了硬件复杂度，使设计高度模块化，同时非常适合VLSI的流水线设计。

此外，本文提出的架构在预处理、流水线实现等方面由于其他架构。

4 结 论

针对传统正交变换，本文提出一种新型的基于CORDIC的DOT快速算法，该算法采用分治策略以及变换核固有的特性，大幅度降低了算法的复杂度，在算法复杂度、可扩展性等性能指标明显优于现有算法。再此基础上，设计出一种DOT的通用架构。该架构可以实现多种正交变换，具有高度的可扩展性、模块化、规律性，并且能够实现高效流水线技术。