[硕士论文精品]离散余弦变换快速算法的研究

华中科技大学硕士学位论文I摘要离散余弦（逆）变换（DCT/IDCT）和改进型离散余弦（逆）变换（MDCT/IMDCT）被广泛运用于视频和音频编解码器中，如MEPG1,MPEG2,和MPEG4的第二部分等。但现有的离散余弦变换快速算法计算复杂度较高，解码精度不理想而产生“漂移”等问题。本文分别提出了新的IDCT算法和MDCT/IMDCT算法，算法在计算复杂度和计算精度等性能上都有所提高。本文首先介绍了DCT/IDCT算法的定义并分析了两种经典的DCT/IDCT算法BGLEE算法和AAN算法。我们用移位和加法运算分别取代了两种算法中原有的乘法运算，以实现定点无乘法的DCT/IDCT计算。虽然很多硬件设备实现乘法运算也是用移位累加的方法，但是我们这里采用的移位累加与一般的不同。因为我们是为特定的快速变换设计移位累加策略，而不是通用的逐位累加。对于特定的算法中的乘法运算有一个因子是预先已知的，在实现这个已知数与其它数相乘时我们充分考虑到了这个已知因子的特点来减少冗余的移位和累加操作的次数，从而达到优化算法减少算法复杂度的目的。根据国际标准IEEE1180对这两种定点无乘法算法进行测试。由于修改的算法没有涉及到乘法操作，这种算法比传统的算法耗时更少。其中修改的AAN算法完成一维IDCT计算只要46次加法和20次移位操作，二维IDCT计算只要737次加法和320移位操作。修改的AAN算法的误差小于IEEE1180规范要求误差的1/20。新的算法在运算复杂度和计算精度之间达到了很好的平衡，适合用于无乘法计算单元的移动通讯设备。本文还对改进型离散余弦变换MDCT的快速算法的实现做了改进和优化。本文分析了BRITANAK提出一种计算MDCT的快速算法，此算法思想是引入扩展因子以达到利用DCT来计算MDCT/IMDCT的目的。在此基础上，我们进一步改进算法流图，改变了扩展因子的位子，提出了一种拥有更高计算精度的新算法。我们用新的MDCT/IMDCT和现有的其它几种算法（如TKTRUONG的算法、VLADIMIRNIKOLAJEVIC的算法）对随机数据进行编解码并测试恢复数据与原数据的信噪比（SNR），测试结华中科技大学硕士学位论文II果表明用我们给出的新算法编解码得到的信噪比（SNR）高于在相同测试条件下用其它的几种方法得到的信噪比。本算法能很好的计算N2N的MDCT/IMDCT，并在G711宽带扩展层的编解码器中得到运用。关键词离散余弦变换离散余弦逆变换改进型离散余弦变换改进型离散余弦逆变换快速算法华中科技大学硕士学位论文IIIABSTRACTDCTDISCRETECOSINETRANSFORMANDIDCTINVERSEDISCRETECOSINETRANSFORMAREWIDELYUSEDINVIDEO/IMAGECODEC,SUCHASMEPG1,MPEG2,ANDMPEG4PART2,WHICHREQUIRETHEIMPLEMENTATIONOFINTEGER8X8DCTANDIDCTANDMODIFIEDDCTANDIDCTMDCTANDIMDCTHAVEALSOBEENADOPTEDINSEVERALINTERNATIONALSTANDARDSANDCOMMERCIALPRODUCTS,SUCHASMPEG1,MPEG2,ANDAC3FORAUDIOCODINGHOWER,THECOMPUTIONALCOMPLEXIEYOFEXISTINGFASTALGORITHSISISRELATIVELYHIGHANDCOMPUTATIONALPRECISIONISLOWWHICHLEADTO“DRIFT”PROBLEMINTHISTHESIS,WEPROPOSENEWIDCTFASTALGORITHMSANDMDCT/IMDCTFASTALGORITHMSWHICHPERFORMACEBETTERINCOMPUTATIONALCOMPLEXITYANDPRECISIONINTHISTHESISIINTRODUCETHEDEFINITIONOFDCT/IDCTANDANALYSISTWOCLASSICALALGORITHMSBGLEESIDCTALGORITHMANDAANSIDCTALGORITHMTHEN,BASEDONTHESETWOALGORITHMS,IREPLACETHEMULTIPLICATIONOPERATORSINORIGINALALGORITHMSWITHADDITIONANDSHIFTOPERATORSTOREALIZETHEFIXPOINTANDMULTIPLIERFREECOMPUTATIONOFIDCT,RESPECTIVELYDUETOTHEABSENCEOFTHEMULTIPLICATIONOPERATORS,THESEIMPROVEDALGORITHMSTAKELESSTIMETOCOMPLETETHECOMPUTATIONTHANTHECLASSICALALGORITHMAMONGOFTHEM,AANALGORITHMJUSTNEED46ADDITIONAND20SHIFTOPERATORSTOCOMPLETE1DIDCTAND737ADDITIONAND320SHIFTOPERATORSTOCOMPLETE2DIDCTTHEERROROFTHEALGORITHMISLESSTHAN1/20ERRORINIEEE1180ANDISO/IEC230021SPECIFICATIONSTHESENOVELFASTALGORITHMSOBTAINTHESOUNDBALANCEBETWEENCOMPUTATIONALCOMPLEXITYANDPRECISIONANDARESUITABLETOBEAPPLIEDTOMOBILEDEVICEANEFFICIENTFASTALGORITHMOFTHEFORWARDMDCTISPRESENTEDWEIMPROVETHEFLOWGRAPHOFBRITANAKSALGORITHMWHICHEMPLOYSDISCRETECOSINETRANSFORMOFTYPEIIDCTIIANDDISCRETESINETRANSFORMOFTYPEIIDSTIITOCOMPUTEMDCT/IMDCTINORDERTOOBTAINMOREPRECISION,WECHANGETHELOCATIONOFTHESCALINGFACTORSANDREDUCETHEAMOUNTOFMULTIPLICATIONOPERATORSWETESTOURNOVELALGORITHMANDOTHEREXISTINGALGORITHMSSUCHASTKTRUONGALGORITHMANDVLADIMIRNIKOLAJEVICSALGORITHMTHESEALGORITHMSAREUSEDTOENCODESOMERANDAMDATAANDDECODETHEM,ANDTESTTHESNRSIGNALNOISERATEBETWEENRECOVEDDATAANDORIGINALDATATHERESULTOFTHETESTISTHATOURALGORITHMS华中科技大学硕士学位论文IVSNRISHIGHERTHANOTHEREXISTINGALGORITHMSTHISALGORITHMISSUITABLEFORN2MDCT/IMDCT,ANDISUSEDINCODECING711WIDEBRANDSCALINGLAYKEYWORDSDCTIDCTMDCTIMDCTFASTALGORITHM独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。学位论文作者签名祝平平日期08年6月9日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密，在_年解密后适用本授权书。不保密。（请在以上方框内打“”）学位论文作者签名祝平平指导教师签名刘建国日期08年6月9日日期08年6月9日本论文属于华中科技大学硕士学位论文11绪论11快速余弦变换算法的研究目的及意义自从AHMED和RAO于1974年给出了离散余弦变换（DCT）1的定义以来，离散余弦变换（DCT）与改进型离散余弦变换（MDCT）就成为广泛应用于信号处理和图像处理特别是用于图像压缩和语音压缩编解码的重要工具和技术，一直是国际学术界和高科技产业界的研究热点。现在的很多图像和视频编码标准（如MPEG12，MEPG23，MEPG44中的第二部分）都要求实现整数的88的DCT和IDCT，而MDCT和IMDCT则主要被应用于音频信号的编解码中（如MPEG1，MEPG2和AC35等标准的音频编码部分）。正是由于这类变换被广泛采用，对于这类变换的快速算法的研究才显得尤为重要。特别是针对特定的应用条件下的快速算法的研究对于提高整个系统的性能表现有很大帮助。本文针对不同的应用条件与要求，分别提出了新的IDCT和MDCT/IMDCT的快速实现算法。我们用实验证明了提出的算法的优势，包括算法复杂度、计算精度等。12国内外研究现状经过几十年的运用与发展DCT/IDCT变换以及MDCT/IMDCT已经被很多领域所使用，为了使这种算法有更好的性能，不少学者对DCT/IDCT和MDCT/IMDCT快速算法做了很深入的研究。首先来看看DCT/IDCT快速算法。有三种经典的快速算法BGLEE算法6、AAN算法7,8和LLM算法9。但是由于这些经典算法的非规整的计算结构使其需要较多的乘法运算，并且不易于实现。为了能在VLSI上完成DCT/IDCT算法，递归算法被提出10，11，12，13，14，15，16，17，这种算法利用重复单元来简化算法结构，从而达到易于硬件实现的目的。华中科技大学硕士学位论文2然而，比较起其它的DCT/IDCT快速算法，较大的计算量和误差损失限制了递归算法的运用，这种算法只适于在VLSI上实现。为了减少计算复杂度，查表累加法被用来取代原有算中的乘法运算18，19,20,21,22。这种改进思想被广泛的运用于数字信号处理中，如DFT，DCT，卷积计算和数字滤波器。虽然查表累加法取代了原有算法中的乘法运算，但为了存储所查格数据我们就需要一定量的存储空间，而这种要求在有些应用环境下并不能得到满足。如在移动通讯设备中由于设备体积重量等限制不可能拥有较多的存储单元。DCT/IDCT在视频编码中得到了很好的运用，但是由于其自身特性（这一点将在第六章中具体讨论）不能直接运用于音频编码中，而出现了MDCT/IMDCT来代替DCT/IDCT。在高质量音频编码中，作为TDAC的重要组成部分的MDCT越来越受到重视，如在MPEG4中的音频编码标准TWINVQ、MPEG2和AAC都在不同程度上使用了MDCT。由于MDCT的广泛应用，MDCT快速算法的研究愈来愈显得意义重大。现在实现快速算法主要有两种方法1将MDCT转化成DCT或DST计算23,24,25,26,27,28,29；2在VSLI上实现的递归算法30,31,32,33,34，35。在第六章中我们将对这两种方法做具体讨论。13本论文研究内容和结构安排本文在讨论了现有的离散余弦（逆）变换DCT/IDCT和改进型离散余弦（逆）变换MDCT/IMDCT的基础上，分别提出了新的IDCT算法和MDCT/IMDCT算法。各章内容安排如下第一章“绪论”简要介绍了离散余弦（逆）变换和改进型离散余弦（逆）变换应用和发展情况。从第二章到第五章，主要讨论了离散余弦（逆）变换DCT/IDCT。第二章给出了DCT/IDCT的定义和一种修改现有DCT/IDCT算法中蝶形结构的通用方法。第三章和第四章分别分析了BGLEE和AAN两种经典的DCT/IDCT快速算法并在这两种算法的基础上加以改进给出新的IDCT快速算法。第五章用IEEE1180的国际标准华中科技大学硕士学位论文3测试了我们提出的新算法，并比较了两种新的IDCT算法在计算复杂度和计算精度两个方面的性能。从第六章到第八章，讨论了改进型离散（逆）余弦变换MDCT/IMDCT。第六章介绍了MDCT/IMDCT算法产生的背景及定义并给出了被应用于G711宽带扩展层编码器中的MDCT/IMDCT算法的具体实现要求。第七章具体分析了两种现有算法的优缺点，在此基础上，第八章提出了新的适于在G711宽带扩展层编码器中运用的MDCT/IMDCT算法，并对该算法进行了测试。华中科技大学硕士学位论文42DCT/IDCT快速算法21算法的定义与应用背景离散余弦变换共包括一型、二型、三型和四型变换，其一维运算公式分别表示如下36DCTI102COS,0,1,1NNNKXKCXNNNNNNULL21DCTII10221COS,0,1,12NNKNXKCXNNNNNNULL22DCTIII10221COS,K0,1,12NNNKXKCXNNNNNULL23DCTIV1022121COS,K0,1,12NNKNXKCXNNNNNULL24上式中1/2,01,0NCN。其中二型（前向DCT或简称DCT）和三型（后向DCT或称IDCT）常常被分别用于编码和解码器中。在很多标准（如MPEG1，MEPG2，MEPG4中第二部分）中都要求实现二维的8X8的DCT/IDCT。二维的DCT和IDCT的定义如下372DDCTII1100222121,COSCOS220,1,1,0,1,1NMNMNMKNLMXKLCCXNMNMNMNNMNNULLNULL252DDCTIII1100222121,COSCOS,220,1,1NMNMNMNKMLXKLCCXNMNMNMKNNULL26华中科技大学硕士学位论文5其中1/2,01,0NNCN和1/2,01,0MMCM。当MN8时，就是8X8的二维DCT和IDCT的定义式。由定义知二维DCT/IDCT可以用两个一维的DCT/IDCT来实现，所以我们将先讨论一维的实现再推广到二维。如果按25和26式完成这样的计算需要用到浮点乘法运算且运算量较大，而对于很多实用设备来说过大的计算量不但意味着要消耗较长的计算时间，也表示需要消耗较多的能量。对于目前使用率很高的移动通讯设备来说过多的能量消耗将导致用电量大待机时间短等问题。而且很多移动设备都没有配备用于计算浮点乘法的浮点运算乘法器。由于DCTIII常常被用于解码端，而移动通讯设备也往往是要对收到的信号解码，那么设计较低计算复杂度DCTIII快速算就很是重要了。本文将只对IDCT（三型DCT）快速实现算法进行讨论。应此，为了消除算法中的浮点乘法运算并尽量减少算法的运算复杂度，我们提出了无乘法的定点IDCT算法。当然，算法的精度要求也是非常重要的。我们设计的算法也满足通行的国际标准。22改进一维DCT/IDCT的一般方法现有的大多数快速算法中都用到了蝶形运算单元，如图21。这种蝶形运算单元可以用27式表示COSCOSCOSCOS图21蝶形运算单元流图COSCOSCOSTUAVB27其中U和V是扩展因子，A和B是整数输入，令1COSCOSWU，2COSCOSWV，那么12TAWBW28华中科技大学硕士学位论文6下面给出用移位累加取代上式中乘法的具体方法。不失一般性，假设W1和W2都是正整数，并将其用二进制表示1110112011222222TTTTITTTTIWMMMMM0OR1I0,1,TWNNNNN0OR1,I0,1,TNULLNULL，29那么112001122TTTTAWBWAMBNAMBNAMBNNULL210如果把0,1,IIAMBNIT计算出来，那T就可以通过T次移位和T次累加得到。由于,I0,1,TIIMNNULL只能等于0或者1，A和B的组合一共只有四种，分别是0,ABAB。所以T可以用TS次移位和TS次累加得到。这里S表示IIAMBN等于0的次数。又由于W1和W2都是常数，,I0,1,TIIMNNULL就是可以预先知道的。我们可以有选择的设计移位和累加的策略，从而减少算法的复杂度。大多数的DCT/IDCT快速算法仅仅用移位和累加运算取代单个的乘法运算，但是我们提出的这种方法通过移位和累加运算实现了乘法的线性组合，这将更明显的减少算法复杂度。虽然这种修改方法可以推广到很多现有快速算法，但是由于它只考虑了一般情况没有考虑各个算法的自身特性，如果对现有快速算法只是简单的套用本方法并不一定可以得到更优的快速算法。然而，以此为改进的思想并充分考虑到各算法自身的特性将可以得到很好的改进算法。接下来将分别介绍基于BGLEE算法和AAN算法的IDCT改进算法。华中科技大学硕士学位论文73基于BGLEE算法的改进31BGLEE算法的介绍2123式给出了一维IDCT的定义式，对于此定义的BGLEE的快速算法推导如下2NXNCXNN,1,1,0NNNULL31为了介绍方便，这里还是用XN表示XN，那么1021COS,2NNNKXKXNN1,1,0NKNULL32由于TN2，则/21/21002121212COS21COS2NNNNNKKNXKXNXNNN33上式可以表示为,K0,1,N/21XKGKHK/21/21001112121212COS21COS2,K0,1,N/21NNNNXNKGNKHNKNKKNXNXNNNGKHK即,K0,1,N/21XKGKHK341,K0,1N/21XNKGKHK35可以发现，GK是一个数长为N/2的IDCT变换，但是缺少常数项。若令10X，则华中科技大学硕士学位论文8/210/210/21/2101212COS2212121212COSCOS222121121COSCOS212121COS21COS22121COSNNNNNNNNKHKNKKNXNNNKNKNXNNNKNKNXNXNKXNXN/2101K0,1,N/21NNNN,36其中设X10。根据以上分析，可知此算法步骤如下第一步计算2,GNXN372121,0,1,HNXNXNNN/2138第二步计算两个数长为N/2的IDCT变换/21021COS,NNKNHKGNN39/21021COS,NNKNGKHNN0,1,NN/21310第三步计算21/2COS,2KXKGKHKN311211/2COS,2K0,1,1KXNKGKHKNN312这样计算一个数长为N的IDCT变换就变成了计算两个数长为N/2的IDCT。对于我们具体要讨论的18的IDCT变换XN0,1,2,7NNULL作为输入序列，令1,0,12NXNCXNN7313则华中科技大学硕士学位论文97021COS16NNKXKXN（N0,1,7）314同上所述，计算步骤如下第一步计算2,GNXN3152121,0,1,2310HNXNXNNX，；316第二步计算两个数长为N/2的IDCT变换3021COS,8NKNGKGN3173021COS,8NKNHKHN0,1,N2,3318第三步计算21/2COS,16KNXKGKHK319217/2COS,K0,1,2,316KNXKGKHK320此算法的流图如下，其中符号IJC表示COSIJ。121212121212121214C14C14C14C14C3812C1812C1812C3812C11612C31612C71612C51612C0X4X2X6X1X5X3X7X0X1X3X2X7X6X4X5X图31BGLEE_IDCT算法流图华中科技大学硕士学位论文1032改进的BGLEE算法为了增加算法的计算精度和运算速度我们用22节中介绍的移位累加法同时考虑到BGLEE算法自身的特性来改进BGLEE算法。在算法流图的开始端我们先将输入数据扩展。为了得到足够的计算精度，预处理阶段输入数据被扩展了162，在算法的末端我们又将数据缩小以得到最终的输出数据。关于算法末端数据缩小的细节部分我们将在33节中讨论。考虑到1421C，我们对每个数据流都乘以2来减少流图中14C的个数。我们用右移操作来代替X0和X4数据流上的1/2，并组合其它的乘法因子得到6个蝶形结构T1T6。图32给出了改进后的流图，由于乘以2数据经过流图后被扩展了122倍。14C14C0X4X2X6X1X5X3X7X0X1X3X2X7X6X4X5X图32改进后的BGLEE_IDCT算法流图根据23节计算6个蝶形结构或14C需要TS次移位和TS次加法运算。然而，考虑到二进制序列M0,M1,MT和N0,N1,NT中有重复的数据段，我们可以利用这些重复部分来减少移位和累加运算的次数。下面给出实现6个蝶形结构和14C的移位和累加策略华中科技大学硕士学位论文11表31T1T6的实现策略T12AB/2COS/8/4COS/16W12/4COS/1647248/131072W22/8COS/8COS/1625568/131072ALGORITHMSADDSSHIFTSXA2A3/B100112XXA6/B100101112XXA10A13/B10010111000100100002XXB3B4/B2000112XXB7B12/B2000110001111100000289T22AB/2COS3/8/4COS3/16W12/4COS3/1655728/131072W22/8COS3/8COS3/1672816/131072ALGORITHMSADDSSHIFTSXA2A3/B100112XXX3/B100110112XXX7/B1001101100110112X1B4B7/B2000001112XXX1X16/B2000001110001112XXB1/B201000111000111278T32AB/2COS/8/4COS7/16W12/4COS7/16237536/131072W22/8COS/8COS7/16128552/131072ALGORITHMSADDSSHIFTSXA2/B11112XXA4A12/B111100111111112X1B6B8/B200000010100000002X2BX1X16/B20111110110001012XXX277华中科技大学硕士学位论文12T42AB/2COS/8/4COS5/16W12/4COS5/1683410/131072W22/8COS3/8COS5/16108982/131072ALGORITHMSADDSSHIFTSCAB/B11/B21X1A3B2/B100012/B200102X2X1C1/B101012/B20102XX2X14X28/B10101000101012/B20110001001102X3X1B3/B100012/B20012XXX310/B1010100010111010012X313B4A10/B20110101001101101121010T52ABCOS/4/4COS/8W12/4COS/850159/131072W22COS/4/4COS/835466/131072ALGORITHMSADDSSHIFTSCAB/B11/B21X1C2A3/B100112/B20102X2X16X18/B10000000011112/B20000000010102XX1X2X26/B10011000011110011112/B20010000010100010102XXB6A12/B10011000011111011112/B2001000101010001010277华中科技大学硕士学位论文13T62ABCOS/4/4COS3/8W12/4COS3/8121092/131072W22COS/4/4COS3/885624/131072ALGORITHMSADDSSHIFTSCAB/B11/B21X1A2C3/B100112/B20012X2B7B8/B10000000002/B2000012X3A9X2/B100000000012/B200000001102XX1X13/B100110110010000012X3X36/B200010011100001102XXC1X24/B10111011001000001002/B2010100111001111000299表3214C的实现策略2/246341/65536ALGORITHMSADDSSHIFTSXAA2/B11012X1X2/B1001012X2AX1/B1010112X3XX16/B1101000001012XX2X36/B101011010100000101244表31，32中C,X,X1,X2,X3都是变量，符号“”表示右移操作。跟在代码后面的二进制数B1和B2分别是输入数据A和B的系数。每行代码的结果可以用B1，B2，A和B来表示。为了更清楚地解释以上表格，我们先以T1为例加以说明。由图二知，T1表示为1212/2COS8/4COS162/4COS162/8COS8COS16TABABWAWB321华中科技大学硕士学位论文14其中12/4COS16W，22/8COS8COS16W。W1和W2可以用二进制表示，考虑到算法精度要求我们取217作为分母。1247248/131072001011100010010000W2225568/131072000110001111100000W当输入数据A被右移了R位，那么这个值就等于2RA。那么代码“XA2A3”可以用数学式表示为2323222220011XAAAA322所以跟在这句代码后代表输入数据系数的二进制数B1就等于00112。同理，代码“B3B4”表示为34342222200011BBBB323二进制数B2等于000112。变量的右移操作也遵循同样规则。在14C实现策略中只有一个输入A，我们令22/246341/6553601011010100000101。代码“XAA2X1X2”可表示为222212101XAAAA324222242122122200101XXAA325T1T3和14C的优化策略只利用了单个二进制序列M0,M1,MT或N0,N1,NT。然而有些情况时，我们利用两个序列组合得重复段，如实现T4T6的过程中我们就用到了这种方法。以T4的实现策略为例。变量X1和X3都是输入A和B的线性组合。代码“X1A3B2”和“X3X1B3”表示为32221220001001XABAB32633233232231222222200010011XXBABBABAB327这里二进制数B1和B2仍然表示输入数据A和B的系数。当二进制数B1和B2等于W1和W2时，我们就完成了12WAWB或22A。华中科技大学硕士学位论文1533基于改进的BGLEE算法的二维IDCT32节中已经介绍过，在预处理过程中输入数据被扩展了216倍，在通过一次一维流图后数据又被多大了21/2倍，所以输入数据在两次经过一维流图后一共被放大了217161/21/217倍。考虑到变换最后的四舍五入，我们给每个输出数据加上216再统一将它们右移17位。观察图32，我们发现如果加2T到X0,那么X0X7都被增加了2T1。所以我们只需对DC量X0加上偏置（BIAS）218161118，而省去了给每个输出数据加216的操作。我们统计本算法中所有的加法和移位操作来衡量本算的算法复杂度，统计如下。表33BGLEEIDCT算法的计算复杂度OPERATIONADDITIONSSHIFTSOUTSIDE232T189T278T377T41010T577T699SQRT2/288ROUND101DTOTAL234881802508602DTOTAL7916112656016960用改进的BGLEE的算法是实现一维的8个点IDCT运算需要加法和移位操作的次数分别是80次和60次；实现二维8X8的IDCT运算需要加法和移位操作的次数分别是1265次和960次华中科技大学硕士学位论文164基于AAN算法的改进41AAN算法介绍1988年YARAI,TAGUI,MNAKAJIMA三人发表了6，就是我们普遍说的AAN的DCT/IDCT算法。AAN的DCT/IDCT算法用蝶形计算和矩阵分解减少了实现DCT/IDCT的计算量。1993年WBPENNEBAKER和JLMITCHELL又给出了计算8点的一维DCT/IDCT的AAN算法7，这个算法的实现只用了5个乘法和29个加法。下图就是8点的一维IDCT的AAN算法流图。C4C4C6C6C2C200AX44AX33AX55AX11AX66AX22AX77AX7X6X5X4X3X2X1X0X图41AANIDCT算法流图其中符号CI表示COS16I，并且060353553392210A,1504499881128/3SIN216/7COS1A,2406532814828/COS2A,950254897788/3COS2216/5COS3A,060353553392214A,391281457728/3COS2216/3COS5A,华中科技大学硕士学位论文170102705980528/3COS6A,350300672448/3SIN2216/COS7A变换系数先要和AII0,7相乘，这个过程称为预处理。42改进的AAN算法为了实现定点无乘法的快速算法我们主要从两个方面改进这个算法。第一用移位和累加运算取代原算法中的乘法运算，这将是本节的内容；第二对预处理部分的A0A7进行系数扩展来提高整个算法的计算精度，这部分内容将在下一节中介绍。按照类似于修改BGLEE算法的方法，下图是修改后的一维IDCT的AAN算法流图。其中C4表示COS4C4C4T1T200AX44AX33AX55AX11AX66AX22AX77AX7X6X5X4X3X2X1X0XINPUTBINPUTBINPUTA图42修改后的AAN算法流图原算法中的蝶形运算单元被T1和T2所取代。下面给出具体的实现T1和T2的算法优化过程。121COS8COS38TABAWBW41其中1COS8W和2COS38W算法华中科技大学硕士学位论文18X1AA3/B101112X2B3B7/B2000100012XX1A4X16X114/B10111011001000001112X3X2X210B2/B20011000011111011112XXX3122COS38COS8TABAWBW42其中1COS38W，2COS8W。算法X1BB3/B201112X2A3A7/B1000100012XX1B4X16X114/B20111011001000001112X3X2X210A2/B10011000011111011112XXX3关于C4的实现过程由于前面讲过，这里不再赘述。我们统计本算法中为了取消乘法操作而花费的加法和移位操作的次数。表41移位累计取代乘法操作的计算复杂度OPERATIONADDITIONSSHIFTST188T2882288一共用了24次加法和24次移位操作。然而，按22中所介绍的方法优化的算法并不是最优的。我们考虑到图41中蝶形算法单元的对称性，给出了另一个优化算法。为了方便介绍，将原算法流图标注如下图。华中科技大学硕士学位论文1900AX44AX33AX55AX11AX66AX22AX77AX7X6X5X4X3X2X1X0XC2C2C6C6C4C4G6G7H6H7图43AAN的IDCT算法流图（标注）由上图知67COS86COS38DAHGGTT4376COS87COS38BCHGGTT44这里记，6COS38ATG，6COS8BTG，7COS38CTG和7COS8DTG。下面给出H6和H7的具体实现过程，为了确保算法的计算精度我们仍选217作为分母。T1G6G64/011112T2T1G63/100012T3T1T210/0111100000100012TAG61T33/0011000011111011112TBT3T16/0111011001000012T1G7G74/011112T2T1G73/100012T2T1T210/0111100000100012TCG71T33/0011000011111011112TDT3T16/0111011001000012H6TDTAH7TBTC华中科技大学硕士学位论文20为了减少算法复杂度，我们用12COS8121096131072011101100100001W来代替12COS8121095131072011101100100000111W虽然这样的处理会稍微降低计算精度，但是这样的处理所降低的算法复杂度是很显著的。再来统计一下本算法中为了取消乘法操作而花费的加法和移位操作的次数。表42移位累计取代乘法操作的计算复杂度OPERATIONADDITIONSSHIFTST156T2562288一共用了18次加法和20次移位操作，显然这样的改进更合理。43基于改进的AAN算法的二维IDCT前面讲过二维IDCT可以用两个一维的IDCT来实现。由图43知，输入数据要先经过预处理即乘以A0A7后才进入算法流图。而对于二维的IDCT实现来说，我们可以先将两次的预处理合二为一，即输入的8X8的输入数据先乘以预处理矩阵COEFIJ，COEFIJ被定义如下COEFIJIJAA45为了确保算法的计算精度，我们需要先对输入数据进行扩展，由于有预处理环节我们只用扩展预处理矩阵COEFIJ。设正整数P1和P2为扩展因子，对于浮点矩阵COEFIJ我们乘以12P并四舍五入得到整数扩展系数矩阵COEF0IJ以便于流图中的移位和累加运算。COEF0IJ由下式得到COEFIJCOEFIJ1P2410类似于BGLEE算法，我们在DC量上加上112P的偏置来达到四舍五入的目的。BLOCK00BLOCK001P1412431适于32位硬件环境下实现的算法对于8比特的DCT输入系数，相应的IDCT需要解码的系数最多只有11比特。考虑到算法流图中数据之间的加法，对于32位的硬件环境来说我们令，P118，P23，如此我们得到了扩展系数矩阵和补偿系数矩阵如下COEF032768417066054723624327681187682508027867417065308177062300684170615116331920354686054777062111877436526054721945546341514912362430068436521703223624856271808120091327684170660547236243276811876825080278671187681511632194558562711876843047690901101004250803192046341180812508090901191952132827867354685149120091278671010042132823699COEF10233004123222022320230023222312102330041000100004202401312211032华中科技大学硕士学位论文22对于410式中的乘法，我们同样用移位累加的方法消去乘法运算。观察到COEF064只有28个值，而COEF164不考虑正负情况下只有1,2,3,4这4种情况，分别列出如下表43COEF0IJ系数的移位累加实现过程COEF0COEF4COEF32COEF3632768BITS00000000000000001000000000000000ALGORITHMSADDSSHIFSXAP2418在预处理之后，数据再被按照图44的标准存储格式存储并进行后续的IDCT处理。通过上面的讨论可知，对于16位硬件环境下的算法在理论上和24位硬件环境下算法是一样的，只是由于位宽限制作了些技术上的处理。因此，在算法精度上来说，这两种实现过程有相同的计算精度。下面我们再来讨论一下AAN算法实现IDCT的计算复杂度，由于预处理部分可以和量化过程合并，预处理的计算量不计入IDCT算法的复杂度中。表45AANIDCT算法的计算复杂度ADITONSSHIFTSOUTSIDE280T156T2562288TOTAL1D285584666820TOTAL2D164617371620320用改进的ANN的算法实现一维的8个点的IDCT运算需要加法和移位操作次数分别是46和20次；实现二维的8X8IDCT运算需要加法和移位操作分别是737次和320次。华中科技大学硕士学位论文305DCT/IDCT算法性能分析51算法复杂度比较我们统计了BGLEE和AAN两种算法的二维IDCT中加法运算和移位运算的次数，如下表所列。表51BGLEE和AAN算法复杂度比较ALGORITHMSIDIDCTADDITIONS/SHIFTSIIDIDCTADDITIONS/SHIFTSBGLEE80A/60S1265A/960SAAN46A/20S737A/320SBGLEE和AAN两种算法流图都已经给出，可以看出AAN算法流图更为简单只用到了两个移位累加单元即T1和T2，而类似的结构单元BGLEE算法却有6个之多。明显复杂度上AAN的IDCT算法有很好的优势。这也是由于AAN算法将很多运算转移到了预处理中，而预处理可以和量化过程相结合，没有将其运算量算在IDCT的复杂度内。在现在流行的很多硬件设备中移位和累加这两种运算都只用一个周期就可以完成，而对于没有独立乘法计算单元的硬件设备（如很多移动通信设备）完成一次乘法运算需要十几个周期。由此可知这两种算法都要比有乘法IDCT算法的复杂度低。52算法计算精度比较521算法计算精度测量方法为了评价新算法的计算精度性能我们依据IEEE118038和ISO/IEC23002139的规范对算法进行测试。下图给出的是IEEE1180测试规范和测试步骤。首先，随机算法RANDOMALGORITHM产生大量的随机序列并组成多个8X8的像素矩阵，再对这些8X8的像素矩阵做“无限”前向DCT变换。所谓“无限”前向DCT变换就是用DOUBLE型数据完成计算，理论上这步DCT变换精度无损的。接下来对得到的精度无损的系数COEFFICIENTS量化取整得到整数的系数。之后对刚得到的整数系数矩阵做“无限”后向DCT变换IDCT并取整得到参考恢复数据REFERENCERECOVERDATA。华中科技大学硕士学位论文31最后用测试的IDCT算法同样也对经过“无限”DCT变换并取整得到的数据块做变换得到测试恢复数据TESTRECOVERDATA。整个过程如图51。图51IEEE1180测试规范华中科技大学硕士学位论文32图52IEEE1180测试步骤522算法计算精度测量结果按照图52说明，我们分别对BGLEE的IDCT算法、32位AAN的IDCT算法和24位AAN的IDCT算法（由于16位AAN的IDCT算法的计算精度和24位AAN的IDCT算法计算精度相同，这里没有给出测试结果）进行测试，分别测试了五个测量指标峰值误差PPEAKPIXELERR、峰值均方误差EPEAKMEANSQUAREERR、全体均方误差NOVERMEANSQUAREERR、峰值平均误差DPEAKMEANERR和全体平均误差MOVERMEANERR。根据IEEE11808以上五个指标分别要满足如下精度要求P1，E006，N002，D0015和M00015。按照标准38，在测试中取Q个块，每个块由64个数组成及一个88的矩阵，Q的取值为10000和1000000。L、H为确定随机数范围的参数，NEGATION表示所取随机数是否取负。在以上三个测试参数确定的情况下对算法测试。测试结果如下华中科技大学硕士学位论文33表52BGLEE测试结果QL,HNEGATIONPPPE1EPMSE006NOMSE002DPME0015MOME00015100005,5NO10000000000400000012800004000000087100005,5YES1000000000040000000980000400000004810000256,255NO1000000000890000049890002000000027010000256,255YES100000000085000004992001900000002010000300,300NO1000000000800000042780001500000004710000300,300YES1000000000750000043550001300000012310000384,383NO1000000000680000038580001600000008310000384,383YES1000000000670000038640001500000003910000512,511NO1000000000600000033920001600000007710000512,511YES1000000000620000033660001500000025010000005,5NO1000000000018900001240000111000006410000005,5YES100000000001950000125000009900000671000000256,255NO100000000079980004964000018100000651000000256,255YES100000000080280004964000024100000901000000300,300NO100000000070900004462000021900000621000000300,300YES100000000070770004468000025200000621000000384,383NO100000000060050003887000023500000381000000384,383YES100000000060450003883000020400000451000000