摘要摘要離散余弦變換是廣泛應(yīng)用于信號(hào)處理、圖像處理領(lǐng)域的重要工具之一，已經(jīng)被多個(gè)國(guó)際標(biāo)準(zhǔn)所接受，如JPEG、MPEG、H263等。DCT應(yīng)用到實(shí)際系統(tǒng)中的前提是具有能夠快速實(shí)現(xiàn)的算法，自從1977年第一個(gè)真正的DCT快速算法出現(xiàn)以來(lái)，尋求更快、更規(guī)則、更簡(jiǎn)單的DCT快速算法一直是信號(hào)處理領(lǐng)域的一個(gè)熱點(diǎn)研究方向。作為正交變換的DCT算法具有計(jì)算復(fù)雜度適中、快速算法等特點(diǎn)，在數(shù)字信號(hào)處理等方面有著廣泛的應(yīng)用。由于應(yīng)用領(lǐng)域的不同，也出現(xiàn)了很多形式的DCT算法。本論文主要研究的是二維離散余弦變換的快速算法設(shè)計(jì)，其研究的重點(diǎn)是實(shí)現(xiàn)二維DCT變換的直接分解算法。論文工作分為三個(gè)部分一對(duì)DCT算法進(jìn)行總結(jié)，概括和描述了近幾年出現(xiàn)的DCT算法并進(jìn)行分類。二在研究已有DCT算法的基礎(chǔ)上提出了一種改進(jìn)的快速算法一部分和分解算法PSDA算法；在PSDA算法中，通過(guò)引入部分和的定義，實(shí)現(xiàn)了頻域輸出數(shù)據(jù)的分集；通過(guò)頻域輸出數(shù)據(jù)的分集將二維DCT變換轉(zhuǎn)換為若干個(gè)一維DCT變換；PSDA算法還給出了部分和的計(jì)算方法及組成部分和的公共加法項(xiàng)的合并原則。三從VLSI實(shí)現(xiàn)的角度出發(fā)，提出了部分和分解算法的VLSI結(jié)構(gòu)，基于該結(jié)構(gòu)的RTL代碼通過(guò)了綜合和FPGA原型驗(yàn)證，為該算法的后續(xù)研究和應(yīng)用提供了理論基礎(chǔ)和實(shí)現(xiàn)參考。論文最后給出了PSDA算法的VLSI實(shí)現(xiàn)結(jié)果；指出了PSDA算法未來(lái)的應(yīng)用前景和發(fā)展方向。相比其它DCT算法，本文提出的PSDA算法實(shí)現(xiàn)了以下幾個(gè)方面的創(chuàng)新和改進(jìn)。1提出了部分和相等的分集準(zhǔn)則，通過(guò)該準(zhǔn)則實(shí)現(xiàn)了對(duì)頻域輸出數(shù)據(jù)的分集，并證明了每一個(gè)分集內(nèi)的元素為時(shí)域輸入數(shù)據(jù)部分和的一維DCT變換輸出。2通過(guò)對(duì)頻域數(shù)據(jù)進(jìn)行子集劃分，將一個(gè)二維DCT變換轉(zhuǎn)換為若干個(gè)一維DCT變換，完成DCT變換的乘法運(yùn)算次數(shù)減少了一半。3提出了部分和的計(jì)算方法和公共加法項(xiàng)的合并原則，通過(guò)合并公共加法項(xiàng)減少了加法運(yùn)算量。摘要4傳統(tǒng)的DCT算法是針對(duì)輸入數(shù)據(jù)長(zhǎng)度為2N進(jìn)行計(jì)算的，但是在很多應(yīng)用領(lǐng)域中都要用到長(zhǎng)度非2“的DCT算法，而素長(zhǎng)度的DCT算法是非2“長(zhǎng)度DCT的核心。因此本文在2“長(zhǎng)度PSDA算法的基礎(chǔ)上提出了改進(jìn)的二維素長(zhǎng)度PSDADCT算法，該算法是基于頻域輸出數(shù)據(jù)與部分和的轉(zhuǎn)換和映射關(guān)系，將二維素長(zhǎng)度DCT變換分解為多個(gè)一維素長(zhǎng)度DCT變換。同已有的素長(zhǎng)度DCT算法相比，減少了一半的乘法計(jì)算量。5提出了基于2“長(zhǎng)度PSDA算法的VLSI結(jié)構(gòu)，同間接算法的VLSI結(jié)構(gòu)相比，該結(jié)構(gòu)具有不需要轉(zhuǎn)置變換，處理延時(shí)低的優(yōu)點(diǎn)；同其他直接算法的VLSI結(jié)構(gòu)相比，該結(jié)構(gòu)具有更規(guī)則的結(jié)構(gòu)，和更少的乘法器和加法器開(kāi)銷。6目前的DCTIP核都是針對(duì)2N長(zhǎng)度的，并不能滿足完全實(shí)際應(yīng)用中的需要。本文在PSDA算法的基礎(chǔ)上，分別基于FPGA和ASIC工藝進(jìn)行了素?cái)?shù)長(zhǎng)度DCT的D核設(shè)計(jì)。仿真和綜合結(jié)果表明，該設(shè)計(jì)結(jié)構(gòu)簡(jiǎn)單、層次清晰，具有高度的規(guī)則性和模塊性。關(guān)鍵詞離散余弦變換，快速算法，部分和分解算法PSDA，VLSI實(shí)現(xiàn)UABSTRACTABSTRACTTHEDISCRETECOSINETRANSFORMISONEOFTHEIMPORTANTTOOLSINSIGNALPROCESSINGANDIMAGEVIDEOPROCESSINGITISNOWACCEPTEDBYSEVERALINTERNATIONALSTANDARDS，SUCHASJPEG,MPEC弓H263ETCTHEPRECONDITIONFORUSINGDCTINPRACTICALSYSTEMISTHEALGORITHMSFORFASTIMPLEMENTATIONOFDCTSINCETHEFIRSTTRUEDCTFASTALGORITHMISPROPOSEDIN1977，LOOKINGFORTHEFASTER,MORESTRUCTUREDANDSIMPLERALGORITHMFORDCTISONEOFHOTRESEARCHTOPICSINSIGNALPROCESSINGFIELDSASANORTHOGONALTRANSFORM，DCTHASMANYFASTCOMPUTATIONALGORITHMSINTHEDIFFERENTAPPLICATIONFILEDS，THEREAREDIFFERENTTYPESOFDCTALGORITHMS刀ETHESISDEALSWITHTHEFASTALGORITHMSOF2DDCTANDTHEIRVLSIIMPLEMENTATIONSTRUCTURESSUITEDFORIMPLEMENTINGINHARDWAREANDPARALLELPROCESSINGANDTHETHESISEMPHASIZESONTHERESEARCHOFDIRECTDECOMPOSITIONALGORITHMFOR2DDCTITCONTAINSTHREEPARTS1THETHESISSUMMARIZESTHEFASTALGORITHMSFORDCTANDCLASSESTHEMINTOSEVERALTYPES2THETHESISPRESENTSANEWFAST2一DDCTALGORITHMPSDABYTHEDEFINITIONOFPARTIALSUNL，ALLALLOCATIONALGORITHMISDESIGNEDONTHEFREQUENCYOUTPUTDATABYTHECOMPUTATIONOFPARTIALSUM，THE2DDCTISCONVERTEDTOSEVERALLDDCT，ANDTHEPARTIALSUMDECOMPOSITIONALGORITHMUTILIZESONLYHALFMULTIPLIERSANDDISCARDSTRANSPOSITIONMEMORYCOMPARINGTORCALGORITHM3THETHESISPRESENTSTHECORRESPONDINGVLSISTRUCTUREOFPARTIALSLIMDECOMPOSITIONALGORITHMPSDAANDPOINTSOUTTHEAPPLITIONFIELDOFPSDAINTHEFUTURECOMPAREDTOOTHERDCTALGORITHMS，SUCHINNOVATIONISARCHIVEDINTHEFOLLOWING1NETHESISPRESENTSTHEDEFINITIONOFPARTIALSUM，RESEARCHSTHESUBSETALLOCATIONALGORITHMBASEDONPARTIALSUMANDTHECOMPUTATIONOFPARTIALSLIM2ATHESUBSCTALLOCATIONBASEDONPARTIALSLAM。THEORIGINALTWODIMENSIONALDCTTRANSFCLITNISCOVERTEDINTOSEVERALONEDIMENSIONALDCTTRANSFORMS3THETHEISRESEARCHSTHEPROPERTYOFPARTIALSUM，DEDUCEANDPRESENTOUTANEWIIIALGORITHMFORCOMPUTING2療2刀TYPE2DDCTBASEDONPARTIALSUMSHAFTNGMEMODILLUSTRATEHOWTODECREASEADDOPERATIONSTIMESDURINGPARTIALSUMCOMPUTATIONTHEALGORITHMCOSTSFEWERMULTIPLINGANDADDINGTIMESTHANOTHERKNOWN2DDCTALGORITHMS4RESEARCHANEWALGORITHMFORCOMPUTINGPRIMENUMBERSIZED2DDCTBASED0NPANLALSUMDECOMPOSITIONANDCONVERTTHEORIGINALTWODIMENSIONALCOMPUTATIONTOSEVERAL1DPRIMENUMBERSIZEDCTCOMPUTATIONS，ANDDEDUCEOUTTHECOMPUTATIONCOMPLEXITYOFTHEALGORITHMANDTHEALGORITHMGETSTHEARCHJEVEIILENTOFABOUTHALFMULTIPLYINGTIMESCOMPARINGTORCALGORITHM5RESEARCHTHE2療2露TYPE2DDCTVLSISTRUCTUREBASEDONPSDACOMPARINGTOTHEINDIRECTVLSISTRUCTURES，ITDOESNTUSETRANSPOSITIONRAMANDARCHIEVESALOWERPROCESSLNGDELAYCOMPARINGTOTHEDIRECTVLSISTRUCTURES，ITHASAMORERE2UDARSTRUCTUREANDFEWERMULTIPLIERANDADDERCOST6RESEARCHTHEQGTYPE2DDCTVLSISTRUCTUREBASEDONPSDAGISAPRIMENUMB哪COMPARINGTOTHEINDIRECTVLSISTRUCTURES，ITDOESNTUSETRANSPOSITIONRAMANDARCHIEVESALOWERPROCESSINGDELAYKEYWORDSDISCRETECOSINETRANSFORMDCT，PARTIALSUMDECOMPOSITIONALGORITHMPSDA，F(xiàn)ASTALGORITHM，VLSIIMPLEMENTATIONIV圖目錄圖2一L圖41圖42圖53圖6一L圖62圖63圖64圖66圖67A圖67B圖68圖69圖6一LO圖6一11附圖1附圖2圖目錄二維DCT行列分解法框圖L8算法L的16點(diǎn)DCT信號(hào)流程39算法2的16點(diǎn)DCT信號(hào)流程4L二維DCT變換輸出6988DCT算法的VLSI實(shí)現(xiàn)原理框圖84部分和計(jì)算單元原理框圖84數(shù)據(jù)選擇單元原理框圖84乘加單元原理框圖85A1，1計(jì)算原理框圖87部分和分解算法頂圖189部分和分解算法頂圖289加入了門級(jí)延時(shí)以后信號(hào)相對(duì)于時(shí)鐘的延時(shí)。9LFPGA原型驗(yàn)證系統(tǒng)測(cè)試原理圖92FPGA原型驗(yàn)證系統(tǒng)原理圖91FPGA原型驗(yàn)證系統(tǒng)板9LDCT變換輸入數(shù)據(jù)。129DCT變換輸出數(shù)據(jù)129IX表目錄表21表51表5一IB表5一LC表52表53表54表61表62表63表目錄8點(diǎn)DCT各種算法的計(jì)算量16AX1，2K的部分和表項(xiàng)65X2K，1的部分和表項(xiàng)一66X1，2K1的部分和表項(xiàng)67計(jì)算復(fù)雜性比較71加法運(yùn)算復(fù)雜性比較80乘法運(yùn)算復(fù)雜性比較80不同2DDCT算法的性能比較86P核綜合和仿真結(jié)果9】本設(shè)計(jì)與業(yè)界銷售產(chǎn)品的性能比較9LX縮略詞表ASICDADCTDFTFFTPSDARCMNRCMVLSI1DDCT2DDCT縮略詞表APPLICATIONSPECIFICINTEGRATEDCIRCUITDISTRIBUTEDARITHMETICDISCRETECOSINETRANSFORMDISCRETEFOURIERTRANS；FORMFASTFOURIERTRANSFORMPARTIALSUMDECOMPOSITIONALGORITHMROWCOLUNMMETHODNONROWCOLUNMMETHODVERYLARGESCALEINTEGRATION0NEDIMENSIONALDISCRETECOSINETRANSFORMTWODIMENSIONALDISCRETECOSINETRANSFORMV獨(dú)創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。據(jù)我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過(guò)的研究成果，也不包含為獲得電子科技大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書而使用過(guò)的材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示謝意。簽名口璽日期如年2彩日關(guān)于論文使用授權(quán)的說(shuō)明本學(xué)位論文作者完全了解電子科技大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人授權(quán)電子科技大學(xué)可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。保密的學(xué)位論文在解密后應(yīng)遵守此規(guī)定簽名盟導(dǎo)師簽名日期第一章緒論技術(shù)背景和研究意義第一章緒論帚一早三百Y匕數(shù)字圖像處理DI百TALIMAGEPROCESSING又稱為計(jì)算機(jī)圖像處理，它是指將圖像信號(hào)轉(zhuǎn)換成數(shù)字信號(hào)并利用計(jì)算機(jī)對(duì)其進(jìn)行處理的過(guò)程。數(shù)字圖像處理最早出現(xiàn)于20世紀(jì)50年代，當(dāng)時(shí)的電子計(jì)算機(jī)已經(jīng)發(fā)展到一定水平，人們開(kāi)始利用計(jì)算機(jī)來(lái)處理圖形和圖像信息。數(shù)字圖像處理作為一門學(xué)科大約形成于20世紀(jì)60年代初期。早期的圖像處理的目的是改善圖像的質(zhì)量，它以人為對(duì)象，以改善人的視覺(jué)效果為目的。圖像處理中，輸入的是質(zhì)量低的圖像，輸出的是改善質(zhì)量后的圖像，常用的圖像處理方法有圖像增強(qiáng)、復(fù)原、編碼、壓縮等。圖像處理技術(shù)在許多應(yīng)用領(lǐng)域受到廣泛重視并取得了重大的開(kāi)拓性成就，屬于這些領(lǐng)域的有航空航天、生物醫(yī)學(xué)工程、工業(yè)檢測(cè)、機(jī)器人視覺(jué)、公安司法、軍事制導(dǎo)、文化藝術(shù)等，使圖像處理成為一門引人注目、前景遠(yuǎn)大的新型學(xué)科。隨著圖像處理技術(shù)的深入發(fā)展，從70年代中期開(kāi)始，隨著計(jì)算機(jī)技術(shù)和人工智能、思維科學(xué)研究的迅速發(fā)展，數(shù)字圖像處理向更高、更深層次發(fā)展。人們已開(kāi)始研究如何用計(jì)算機(jī)系統(tǒng)解釋圖像，實(shí)現(xiàn)類似人類視覺(jué)系統(tǒng)理解外部世界，這被稱為圖像理解或計(jì)算機(jī)視覺(jué)。70年代末MIT的MARR提出的視覺(jué)計(jì)算理論，這個(gè)理論成為計(jì)算機(jī)視覺(jué)領(lǐng)域其后十多年的主導(dǎo)思想。圖像理解雖然在理論方法研究上已取得不小的進(jìn)展，但它本身是一個(gè)比較難的研究領(lǐng)域，存在不少困難，因人類本身對(duì)自己的視覺(jué)過(guò)程還了解甚少，因此計(jì)算機(jī)視覺(jué)是一個(gè)有待人們進(jìn)一步探索的新領(lǐng)域。數(shù)字圖像處理的信息大多是二維信息，處理信息量很大。如一幅256256低分辨率黑白圖像，要求大約64KBIT的數(shù)據(jù)量；對(duì)高分辨率彩色512512圖像，則要求768KBIT數(shù)據(jù)量；如果要處理30幀秒的電視圖像序列，則每秒要求1MBIT“225MBIT數(shù)據(jù)量。因此對(duì)計(jì)算機(jī)的計(jì)算速度、存儲(chǔ)容量等要求較高。21世紀(jì)的人類社會(huì)已經(jīng)進(jìn)入了信息化時(shí)代。數(shù)字化后的信息，尤其是數(shù)字化后的視頻和音頻信息具有數(shù)據(jù)海量性，它給信息的存儲(chǔ)和傳輸造成較大的困難，成為阻礙人類有效獲取和使用信息的瓶頸問(wèn)題之一。因此，研究和開(kāi)發(fā)有效的多媒體數(shù)據(jù)壓縮編碼方法，以壓縮的形式存儲(chǔ)和傳輸這些數(shù)據(jù)是非常有必要的。視頻數(shù)據(jù)壓縮目前的主要目標(biāo)是追求較大的壓縮率、較快的壓縮解壓縮速度電子科技大學(xué)博士學(xué)位論文以及盡可能好的圖像重構(gòu)質(zhì)量，同時(shí)也在向壓縮數(shù)據(jù)的處理如數(shù)據(jù)組織、檢索、重構(gòu)等方向發(fā)展，力求發(fā)展一個(gè)比較完整的圖像壓縮處理解決方案，因此在這方面仍有許多的工作要做，其中最基本的就是要有比較合理且高效的壓縮算法。111圖像壓縮算法基本框架標(biāo)準(zhǔn)化是產(chǎn)業(yè)化活動(dòng)成功的前提，標(biāo)準(zhǔn)的制定保證了數(shù)據(jù)流可以在不同的終端和應(yīng)用間交換。自國(guó)際無(wú)線電咨詢委員會(huì)CCIRINTERNATIONALRADIOCONSULTATIVECOMMITTEE于1982年通過(guò)了電視演播室數(shù)字編碼的國(guó)際標(biāo)準(zhǔn)CCIR601號(hào)建議以來(lái)，視頻編碼技術(shù)日趨成熟，目前的國(guó)際視頻編碼標(biāo)準(zhǔn)己有很多種。如國(guó)際標(biāo)準(zhǔn)化組織ISOINTERNATIONALSTANDARDIZATIONORGANIZATION和國(guó)際電子學(xué)委員會(huì)IECINTERNATIONALELECTRONICSCOMMITTEE下屬的活動(dòng)圖像專家組MPEGMOVINGPICTURESEXPERTSGROUP組織制定的MEPGL，MPEG2，MPEG一4標(biāo)準(zhǔn)，國(guó)際電信聯(lián)盟ITUINTEMATIONALTELECOMMUNICATIONUNION帶LJ定的H261和H263標(biāo)準(zhǔn)，以及ISOIEC下屬的MPEG和ITU下屬的視頻編碼專家組VCEGVIDEOCODINGEXPERTSGROUP共同成立的聯(lián)合視頻小組JVTJOINTVIDEOTEAM最新完成的H264標(biāo)準(zhǔn)也稱為MPEG4AVCADVANCEDVIDEOCODING，以及國(guó)內(nèi)第一個(gè)針對(duì)音視頻產(chǎn)業(yè)需求制定的標(biāo)準(zhǔn)AVSAUDIOVIDEOSTANDARD等都是基于混合編碼HYBRIDCODING框架之上的。這里的所謂混合編碼框架是指綜合運(yùn)用預(yù)測(cè)，變換以及熵編碼的編碼框架，有以下三個(gè)主要特點(diǎn)L、利用幀間預(yù)測(cè)消除圖像間的冗余，利用幀內(nèi)預(yù)測(cè)消除圖像內(nèi)的冗余。2、通過(guò)對(duì)預(yù)測(cè)殘差進(jìn)行變換和量化來(lái)消除圖像內(nèi)的視覺(jué)冗余。3、利用熵編碼來(lái)消除統(tǒng)計(jì)上的冗余。在實(shí)際應(yīng)用中，編碼端首先通過(guò)幀內(nèi)預(yù)測(cè)或幀間預(yù)測(cè)，得到相應(yīng)的殘差數(shù)據(jù)塊，對(duì)原始圖像數(shù)據(jù)塊或殘差數(shù)據(jù)塊進(jìn)行二維變換，然后在變換域中對(duì)變換系數(shù)進(jìn)行量化，最后進(jìn)行熵編碼，即采用變長(zhǎng)編碼或者算術(shù)編碼等。而在解碼端，則對(duì)殘差的變換量化系數(shù)進(jìn)行反量化反變換，然后和預(yù)測(cè)值相加即可得到重建圖像塊。圖L一1是圖像和視頻壓縮系統(tǒng)的結(jié)構(gòu)框圖。由圖可知，變換是系統(tǒng)中的一個(gè)核心部分。2第一章緒論HLPUIIMAGERECONSTRUCTIMAGE112離散余弦變換圖11圖像和視頻壓縮系統(tǒng)研究表明，視頻數(shù)據(jù)、圖像數(shù)據(jù)或其殘差數(shù)據(jù)在空間域上仍有著較強(qiáng)的相關(guān)性。進(jìn)行變換的目的就是為了將這些在空間域上有較強(qiáng)相關(guān)性的數(shù)據(jù)變換到以變換矩陣的歸一化向量表達(dá)的變換域上。在變換域上，這些信號(hào)的變換域表示的相關(guān)性就很弱，有利于進(jìn)一步進(jìn)行壓縮處理。因此，變換是視頻編碼和圖像編碼中非常重要的部分。當(dāng)今流行的視頻編碼標(biāo)準(zhǔn)中大多采用了離散余弦變換作為它們的核心變換。離散余弦變換是由離散傅立葉變換DFT發(fā)展過(guò)來(lái)的，由于離散傅立葉變換在數(shù)字信號(hào)處理頻譜分析等領(lǐng)域中己成為有力的數(shù)學(xué)工具，但其缺點(diǎn)是復(fù)數(shù)域運(yùn)算，運(yùn)算量太大以至難以實(shí)時(shí)處理，為克服這些缺點(diǎn)，1974年，AHMED等人構(gòu)造了一種實(shí)數(shù)域變換一DCT【11。由于該變換性Z日,匕。,，4L3適用于人類語(yǔ)言及圖像信號(hào)的特點(diǎn)，從這個(gè)意義上，DCT常常被認(rèn)為是接近KL變換性能的次佳變換。DCT有一個(gè)重要性質(zhì)，就是它的變換矩陣的基向量很近似于TOEPLITZ矩陣即沿對(duì)角線方向的元素都相同的特征向量。這就是說(shuō)，對(duì)TOEPLITZ矩陣DCT將非常接近KL變換。統(tǒng)計(jì)表明，人類的語(yǔ)言、圖像等信號(hào)的自相關(guān)矩陣常常表現(xiàn)出具有TOEPLITZ矩陣的特點(diǎn)。從這個(gè)意義上來(lái)說(shuō)，DCT是比較適合對(duì)語(yǔ)言、圖像等信號(hào)作變換處理的一種變換，它的性能接近于KL變換。DCT還具有以下性質(zhì)1對(duì)于具有高相關(guān)性的數(shù)據(jù)信號(hào)，DCT具有非常好的能量聚焦性，經(jīng)過(guò)變換，信號(hào)能量的絕大部分被集中到變換域的少數(shù)系數(shù)上；2DCT具有可實(shí)現(xiàn)的快速算法；基于以上優(yōu)點(diǎn)，離散余弦變換被廣泛應(yīng)用于JPEG壓縮解壓縮、DVDVCD播放機(jī)、電纜電視、HDTV、圖形與圖像處理卡、超聲波核磁共振成像系統(tǒng)、數(shù)字電子科技大學(xué)博士學(xué)位論文錄像機(jī)、數(shù)字照相機(jī)、視頻電話與會(huì)議系統(tǒng)、圖像傳輸系統(tǒng)等。目前DCTIDCT已成為運(yùn)動(dòng)圖像壓縮標(biāo)準(zhǔn)MPEG和靜止圖像壓縮標(biāo)準(zhǔn)JPEG等的重要組成部分。實(shí)際的應(yīng)用促進(jìn)著快速算法的發(fā)展，在這之后，針對(duì)各個(gè)應(yīng)用領(lǐng)域，不同形式的DCT算法也應(yīng)運(yùn)而生。DCT變換也出現(xiàn)了多種擴(kuò)展形式，如音頻壓縮中使用的修正離散余弦變換MDCT，H264標(biāo)準(zhǔn)中使用的整型DCT變換等。在音頻編碼中，編碼器通常將PCM數(shù)據(jù)分成若干個(gè)等寬的子帶等待心理聲學(xué)模型的判斷，做進(jìn)一步的量化壓縮，這種壓縮法我1FINQ做SUBBANDCODING。這種方式由于是等寬的頻帶濾波，不符合人耳的聽(tīng)覺(jué)特性的，對(duì)后續(xù)量化階段的處理不利，相鄰子帶間也容易發(fā)生混疊效應(yīng)。為了克服以上缺點(diǎn)，音頻編碼器使用MDCT轉(zhuǎn)換，進(jìn)一步將劃分成更細(xì)的頻帶，提高對(duì)頻率的解析度。離散余弦變換并不是整數(shù)可逆的，因此，在利用有限計(jì)算精度的計(jì)算機(jī)來(lái)實(shí)現(xiàn)DCT變換域編碼時(shí)，只能是有損的編碼。雖然這對(duì)于很多應(yīng)用是可以允許的，但還有一些應(yīng)用卻不允許有任何的圖像失真，比如醫(yī)學(xué)圖像和遙感圖像。此外，一些應(yīng)用還要求有損和無(wú)損編碼同時(shí)兼顧，即算法要統(tǒng)一。而對(duì)于這些應(yīng)用，就需要實(shí)現(xiàn)可逆的整數(shù)DCT變換。進(jìn)行整數(shù)DCT變換的方法有很多，有代表性的有基于矩陣分解的分裂基DCT算法和基于提升結(jié)構(gòu)的算法。但是最根本的原理是利用了提升結(jié)構(gòu)的特點(diǎn)，使逆變換得到的值與原始值沒(méi)有差別。提升結(jié)構(gòu)不僅能實(shí)現(xiàn)靈活的正交變換，而且還能達(dá)到無(wú)損壓縮效果，因此在變換編碼中是一個(gè)非常有用的工具。1999年后發(fā)展起來(lái)的二進(jìn)制DCT算法利用提升結(jié)構(gòu)消去了乘法，只用移位和加法來(lái)實(shí)現(xiàn)，得到基于提升結(jié)構(gòu)的無(wú)乘法DCT。整數(shù)DCT算法的另一個(gè)優(yōu)點(diǎn)是若有足夠的字長(zhǎng)來(lái)表示數(shù)據(jù)的話，那么中間的誤差可以完全消除，實(shí)現(xiàn)信息在傳輸過(guò)程的無(wú)損。綜上所述，離散余弦變換是音視頻編解碼的核心變換。因此研究DCTIDCT算法及其VLSI實(shí)現(xiàn)的地位日趨重要，尤其是高性能低功耗的算法及其VLSI實(shí)現(xiàn)結(jié)構(gòu)。113ASIC技術(shù)概述專用集FI茈電路ASICAPPLICATIONSPECIFICINTEGRATEDCIRCUIT是種為專門目的而設(shè)計(jì)的集成電路，它與標(biāo)準(zhǔn)集成電路或通用集成電路有著很大的區(qū)別。從1948年第一只半導(dǎo)體晶體管問(wèn)世以后，微電子技術(shù)就得到了日新月異的發(fā)展，50年代4第一章緒論中期可用于工業(yè)上的產(chǎn)品以鍺材料制作的結(jié)型半導(dǎo)體晶體管為多，由于鍺材料比硅材料具有較高的載流子遷移率，因而較易于實(shí)現(xiàn)高頻性能。但鍺材料制作的半導(dǎo)體器件有著固有的缺點(diǎn)。50年代末出現(xiàn)的硅平面制造工藝技術(shù)，不但成為硅半導(dǎo)體晶體管的基本制造工藝，也成為將多個(gè)分立器件制作在同一塊面積不大的硅片上的集成電路的基本制造工藝。硅器件有效地克服了鍺器件所存在的缺點(diǎn)，這種技術(shù)也一直沿用到今天。1131ASIC電路的分類ASIC電路可分為以下三個(gè)類別。1全定制集成電路全定制集成電路指設(shè)計(jì)和制作所有的邏輯單元和掩膜版都是按定制的方式進(jìn)行的集成電路。設(shè)計(jì)者需要對(duì)電路版圖進(jìn)行最精細(xì)的制作，以免浪費(fèi)芯片上任何一個(gè)平方微米的空間，由于這些專門設(shè)計(jì)的IC產(chǎn)量高，適用于通用的應(yīng)用目的，故稱它們?yōu)槿ㄖ仆ㄓ眉呻娐稦ULLCUSTOMIC。2半定制集成電路半定制集成電路指所有的邏輯單元預(yù)先進(jìn)行設(shè)計(jì)，但其中一些或所有的掩膜版按照定制方式進(jìn)行制作的集成電路。使用單元庫(kù)中預(yù)先設(shè)計(jì)好的單元可以大大的簡(jiǎn)化設(shè)計(jì)。半定制集成電路可分為標(biāo)準(zhǔn)單元集成電路和門陣列集成電路。31可編程ASIC電路可編程ASIC指所有的邏輯單元都預(yù)先進(jìn)行設(shè)計(jì)，但沒(méi)有一塊掩膜版是按定制方式進(jìn)行制作的集成電路。它主要分為兩類可編程邏輯器件PLD和現(xiàn)場(chǎng)可編程門陣YTFPGA。1132基于標(biāo)準(zhǔn)單元的ASIC設(shè)計(jì)流程對(duì)于P核的ASIC驗(yàn)證，大致的流程如下1設(shè)計(jì)輸入，采用已有的VERILOGHDL代碼即可。2邏輯綜合，使用邏輯綜合工具將設(shè)計(jì)輸入的VERILOGHDL代碼轉(zhuǎn)化成門級(jí)網(wǎng)表，通過(guò)網(wǎng)表來(lái)描述邏輯單元間的連接關(guān)系。3系統(tǒng)劃分，如果有必要，將大系統(tǒng)劃分為幾個(gè)ASIC。4布圖前仿真，檢查設(shè)計(jì)的功能是否正確。5布圖規(guī)劃，在芯片上排列網(wǎng)表模塊。電子科技人學(xué)博士學(xué)位論文6布局，決定模塊中單元的位置。7布線，單元與模塊之間的連接。8提取參數(shù)，確定真實(shí)的互連電阻和電容。9布圖后仿真，加上互連線負(fù)載后檢查設(shè)計(jì)是否能夠正常工作。一般來(lái)說(shuō)，步驟14為邏輯設(shè)計(jì)部分，59為物理設(shè)計(jì)部分。隨著工藝的不斷提升，現(xiàn)代的設(shè)計(jì)方法逐漸傾向于前后端設(shè)計(jì)的融合。113。3ASIC的單元庫(kù)單元庫(kù)是ASIC設(shè)計(jì)的關(guān)鍵部分，對(duì)于可編程ASIC而言，F(xiàn)PGA公司以成套設(shè)計(jì)工具形式提供邏輯單元庫(kù)，通常用戶沒(méi)有其他選擇。而對(duì)于標(biāo)準(zhǔn)單元ASIC設(shè)計(jì)來(lái)說(shuō)，可有3種選擇ASIC供應(yīng)商開(kāi)發(fā)ASIC的公司提供單元庫(kù)；從第三方單元庫(kù)供應(yīng)商處購(gòu)買單元庫(kù)；建立自己的單元庫(kù)。第一種選擇采用ASIC供應(yīng)商單元庫(kù)，要求用一套ASIC供應(yīng)商認(rèn)可的設(shè)計(jì)工具輸入并進(jìn)行仿真設(shè)計(jì)。出于某些原因，在日本，一般的模式是采用ASIC供應(yīng)商提供的工具，而在美國(guó)，歐洲以及其它地方的設(shè)計(jì)者情愿選擇自己的工具。ASIC供應(yīng)商的單元庫(kù)通常是虛庫(kù)一單元都是空框或者說(shuō)是虛的，但含有足夠的版圖信息。完成版圖后，將網(wǎng)表傳遞給ASIC供應(yīng)商，在芯片制造前將其填入空框內(nèi)。第2種和第3種選擇是由用戶決定購(gòu)買還是開(kāi)發(fā)。如果購(gòu)買單元庫(kù)來(lái)完成ASIC設(shè)計(jì)，用戶就擁有制造ASIC的掩膜板加工模具，這也稱為客戶控制的加工模具。庫(kù)供應(yīng)商利用ASIC芯片加工廠提供的工藝信息開(kāi)發(fā)單元庫(kù)，ASIC芯片加工廠不同于ASIC供應(yīng)商僅是制造，不提供設(shè)計(jì)幫助。如果單元庫(kù)滿足芯片加工廠的加工規(guī)格，則稱其為合格單元庫(kù)。這些單元庫(kù)一般都很貴可能幾十萬(wàn)美元，但如果單元庫(kù)符合幾個(gè)加工廠的規(guī)格，就可以選擇最合適的加工廠。這表明，對(duì)大批量生產(chǎn)，購(gòu)買較貴的庫(kù)最終費(fèi)用比其他解決方案低。第3種選擇是自行開(kāi)發(fā)單元庫(kù)，很多大的計(jì)算機(jī)和電子公司會(huì)做此選擇。盡管單元庫(kù)開(kāi)發(fā)過(guò)程既復(fù)雜又花錢，但是如今已設(shè)計(jì)的單元庫(kù)多數(shù)是自行開(kāi)發(fā)的。不管哪種方法，ASIC單元庫(kù)的每個(gè)單元必須包括以下內(nèi)容11物理版圖2行為級(jí)模型3VERILOGVHDL模型6第一章緒論4詳細(xì)時(shí)序模型5N試策略61電路原理圖71單元圖符8連線一負(fù)載模型9布線模型以上列出的某些方面，像版圖，圖符等等的庫(kù)單元內(nèi)容是顯而易見(jiàn)必須有的，但對(duì)于行為級(jí)模型等內(nèi)容，這里要做一個(gè)簡(jiǎn)單的介紹。行為級(jí)模型是指對(duì)單元電路做的一種高層次的描述，這是因?yàn)橛脩粼趯?duì)一個(gè)定態(tài)的ASIC系統(tǒng)作詳細(xì)的時(shí)序分析時(shí)需要花費(fèi)大量的時(shí)間，為了節(jié)約時(shí)間，在電子系統(tǒng)分析的初期采用行為模型可以大大縮短仿真時(shí)間。ASIC電路設(shè)計(jì)者為了掌握電路關(guān)鍵路徑的時(shí)序性能，就需要對(duì)每一個(gè)庫(kù)單元有各自對(duì)應(yīng)的時(shí)序模型。一般庫(kù)設(shè)計(jì)人員是通過(guò)對(duì)單元電路所做的參數(shù)提取來(lái)仿真庫(kù)單元電路的延遲時(shí)間。為了在實(shí)際布線完成前估算出引線的寄生電容，就需要對(duì)給定大小的電路模塊中線網(wǎng)的電容進(jìn)行統(tǒng)計(jì)估算。這常常采取查表的方式，也稱為連線一負(fù)載模型。這里還需要每個(gè)單元的布線模型。直接用物理設(shè)計(jì)或版圖工具處理大單元太復(fù)雜，此時(shí)需要比較簡(jiǎn)單的物理版圖表示法一虛庫(kù)法，但它仍需包含所有必要的信息。虛庫(kù)可能包含的信息為告訴自動(dòng)布線工具能在單元上何處布線，以及連接到單元的位置和類型。114超大規(guī)模集成電路VLSI自從1958年美國(guó)德州儀器公司發(fā)明集成電路以來(lái)，特別是在最近的20年，集成電路技術(shù)的發(fā)展，已成為當(dāng)代科技界最引人注目的焦點(diǎn)之一。在當(dāng)今世界上，無(wú)論是科學(xué)技術(shù)、軍事、經(jīng)濟(jì)，還是人們的日常生活，都早己和它密切結(jié)合，息息相關(guān)。集成電路由于電路復(fù)雜程度不同，可根據(jù)集成規(guī)模分為小規(guī)模集成電路、中規(guī)模集成電路、大規(guī)模集成電路和超大規(guī)模集成電路。對(duì)于數(shù)字集成電路來(lái)說(shuō)，習(xí)慣上認(rèn)為小規(guī)模集成電路是集成度小于10個(gè)門電路或集成元件數(shù)少于100個(gè)元件的集成電路；中規(guī)模集成電路是集成度在0100個(gè)門電路之間，或集成元件數(shù)在100“1000個(gè)元件之間的集成電路；大規(guī)模集成電路是集成度在100個(gè)門電路7電子科技大學(xué)博T學(xué)位論文以上或集成元件數(shù)在1000個(gè)元件以上的集成電路。大規(guī)模集成電路是在一般中、小規(guī)模集成電路的基礎(chǔ)上發(fā)展起來(lái)的，中、小規(guī)模集成電路一般是以簡(jiǎn)單的門電路或單級(jí)放大器為集成對(duì)象的，而大規(guī)模集成電路則以功能部件、整機(jī)、子系統(tǒng)為集成對(duì)象。從分立元件發(fā)展到集成電路是半導(dǎo)體電子技術(shù)發(fā)展的一次飛躍；從一般中、小規(guī)模集成電路發(fā)展到大規(guī)模集成電路是又一次飛躍，并且還在向超大規(guī)模集成電路發(fā)展。超大規(guī)模集成電路一般指集成度達(dá)1萬(wàn)個(gè)門電路或集成元件數(shù)在10萬(wàn)個(gè)元件以上的大規(guī)模集成電路。隨著超大規(guī)模集成電路VLSI和專用集成電路ASIC的廣泛應(yīng)用，集成電路設(shè)計(jì)已經(jīng)不再是集成電路行業(yè)單獨(dú)包攬所能勝任的了。由于芯片內(nèi)部電路的規(guī)模越來(lái)越大，線路越來(lái)越復(fù)雜，集成電路專家很難應(yīng)付各種用戶的要求。ASIC技術(shù)的特點(diǎn)是提倡用戶自行設(shè)計(jì)IC。自行設(shè)計(jì)ASIC是電子、信息業(yè)發(fā)展的方向。目前許多集成電路工廠向用戶開(kāi)放，接受用戶自行設(shè)計(jì)的芯片版圖進(jìn)行專用芯片的加工。電子專家只要掌握了VLSI設(shè)計(jì)技術(shù)，就可以設(shè)計(jì)自己的專用芯片，將原來(lái)安裝在一塊印刷電路板上的電路，集成在一個(gè)芯片內(nèi)。從而大大縮小整機(jī)的體積，降低功耗，提高性能，增加可靠性和保密性，節(jié)省裝配成本?，F(xiàn)代電子產(chǎn)品的更新?lián)Q代，很重要的一條，就是要依靠VLSI技術(shù)，要求電子產(chǎn)品設(shè)計(jì)師自己設(shè)計(jì)ASIC。一個(gè)復(fù)雜數(shù)字系統(tǒng)往往由許多功能模塊構(gòu)成，而設(shè)計(jì)者的新思想往往只體現(xiàn)于部分單元之中，其它單元的功能則是通用的，如FFT，F(xiàn)IR，IIR，VITERBI譯碼，PCI總線接口，調(diào)制解調(diào)，信道均衡等。這些通用單元具有可重用性，適用于不同的系統(tǒng)。如果預(yù)先設(shè)計(jì)好這些通用單元并根據(jù)各種工藝對(duì)布局和布線進(jìn)行優(yōu)化，從而構(gòu)成具有自主知識(shí)產(chǎn)權(quán)的功能模塊，稱之為IPINTELLECTUALPROPERTY模塊，也可稱為P核IPCORE。那么，相應(yīng)的，針對(duì)不同的數(shù)字圖像系統(tǒng)，就必須采用不同的處理方法和算法才能加以解決，不可能研制一個(gè)圖像處理ASIC芯片就可以解決所有的信息處理問(wèn)題。但是圖像處理的許多算法都建立在一些基本運(yùn)算之上，如加法，乘法，離散卷積，矢量?jī)?nèi)積，矩陣相乘以及FFT變換，DCT變換和圖像矩陣計(jì)算等。而它們?cè)趫D像分析與處理以及圖像壓縮編碼中有著廣泛的應(yīng)用。所以，開(kāi)發(fā)人員可以設(shè)計(jì)出圖像處理基本運(yùn)算和算法的VLSI宏單元電路，建立具有自主知識(shí)產(chǎn)權(quán)的基本運(yùn)算和算法芯片核簡(jiǎn)稱基本運(yùn)算和算法口核庫(kù)，可以方便的構(gòu)建專門應(yīng)用的圖像處理算法芯片。因此，本文的大背景就是開(kāi)展圖像處理核心變換算法研究和口核設(shè)計(jì)驗(yàn)證技術(shù)研究。充分考慮基本運(yùn)算的內(nèi)在并行性，研制可復(fù)用圖像處理基本運(yùn)算與算法IP核，為嵌入式實(shí)時(shí)圖像處理系統(tǒng)芯片的研制第一章緒論提供關(guān)鍵技術(shù)。針對(duì)實(shí)時(shí)圖像數(shù)據(jù)，該算法的IP核可以與國(guó)內(nèi)自行設(shè)計(jì)ASIC或RISCCPU核結(jié)合在一起，組成極具特色的高效圖像處理系統(tǒng)芯片，滿足實(shí)時(shí)圖像處理的需要。開(kāi)展基本運(yùn)算可復(fù)用IP核的設(shè)計(jì)工作，對(duì)于提高圖像處理系統(tǒng)芯片的設(shè)計(jì)效率具有積極意義。同時(shí)這些IP核也適用于通信，家電，工業(yè)檢測(cè)，醫(yī)學(xué)診斷等圖像處理應(yīng)用領(lǐng)域，具有巨大的經(jīng)濟(jì)價(jià)值。當(dāng)前世界半導(dǎo)體市場(chǎng)增長(zhǎng)最顯著的領(lǐng)域是IP核。在國(guó)外，目前自主開(kāi)發(fā)和經(jīng)營(yíng)IP核的公司主要有英國(guó)的ARM，AMPHION，美國(guó)DESOC，RAMBUS等。以ARM公司為例，在1985年ARM公司設(shè)計(jì)開(kāi)發(fā)出第一塊擁有自主知識(shí)產(chǎn)權(quán)的RISC處理器模塊，1990年首次將其IP專利權(quán)轉(zhuǎn)讓給APPLE公司。到2003年全球已有IBM，TI，PHILIPS，NEC，SONY等幾十家公司采用其IP開(kāi)發(fā)自己的產(chǎn)品。有關(guān)IP核設(shè)計(jì)的報(bào)道首次出現(xiàn)在1997年召開(kāi)的CICC專用IC國(guó)際年會(huì)的“單元建庫(kù)”論文分冊(cè)上。1998年在美國(guó)加州的硅谷召開(kāi)國(guó)際年會(huì)“半導(dǎo)體戰(zhàn)略論壇”上，以IP產(chǎn)業(yè)的現(xiàn)狀和發(fā)展為大會(huì)專題，共有48個(gè)全球著名的微電子公司的主要負(fù)責(zé)人作了大會(huì)發(fā)言。同年，“半導(dǎo)體戰(zhàn)略論壇98”組織了IP專題研討會(huì)。在1999年“ASICSTATUS99”的國(guó)際年會(huì)上論文總量的三分之一是圍繞IP核的設(shè)計(jì)開(kāi)發(fā)的文章。這些關(guān)于IP設(shè)計(jì)的國(guó)際年會(huì)從另一個(gè)角度展示了P產(chǎn)業(yè)迅猛的發(fā)展勢(shì)頭。目前國(guó)內(nèi)總體來(lái)說(shuō)在IP的開(kāi)發(fā)和應(yīng)用方面還處于初級(jí)階段。令人可喜的是，近年來(lái)國(guó)家在口產(chǎn)業(yè)上也有了很大的動(dòng)作。科技部于2000年啟動(dòng)了“十五“國(guó)家863計(jì)劃超大規(guī)模集成電路SOC專項(xiàng)工作。目前，我國(guó)己初步建成起具有自主知識(shí)產(chǎn)權(quán)，品種較為齊全和管理科學(xué)的國(guó)家級(jí)M核庫(kù)并掌握國(guó)際水平的SOC軟硬件協(xié)同設(shè)計(jì)，IP核復(fù)用和超深亞微米集成電路設(shè)計(jì)的關(guān)鍵技術(shù)。由摩托羅拉向中國(guó)釋放MCORE而觸發(fā)的產(chǎn)業(yè)界SOC一口討論實(shí)質(zhì)上是我國(guó)IP產(chǎn)業(yè)的啟動(dòng)。我國(guó)IP產(chǎn)業(yè)正在從概念階段向?qū)嵱秒A段過(guò)渡。最近幾年，數(shù)字電視和高清電視核心芯片、多功能和智能手機(jī)相關(guān)芯片、MP3、閃存和視頻播放等新概念電子產(chǎn)品SOC以及CPU和DSP等基礎(chǔ)IC成為中國(guó)IC公司開(kāi)發(fā)的熱點(diǎn)。而圖像處理口核既可作為數(shù)字電視和高清電視專用芯片的核心，又可與通用CPU，DSP結(jié)合作為圖像處理系統(tǒng)解決方案，有著良好的通用性和廣泛的應(yīng)用。正因?yàn)橛兄鲜鰞?yōu)點(diǎn)，圖像處理P核的研究與設(shè)計(jì)成為近幾年產(chǎn)業(yè)研究的熱點(diǎn)。115離散余弦變換及其VLSI結(jié)構(gòu)的發(fā)展現(xiàn)狀1974年AHMEL等首先提出了DCT概念【L】，隨后DCT在數(shù)字信號(hào)處理的各個(gè)電子科技大學(xué)博士學(xué)位論文領(lǐng)域迅速得到應(yīng)用，應(yīng)用的需要激發(fā)了人們對(duì)DCT快速算法的研究，由于FFT的優(yōu)異性能，最初的DCT快速算法基本上都是建立在FFT基礎(chǔ)上的。但是研究表明，直接設(shè)計(jì)的DCT快速算法將具有更高的效率，1977年，WHCHEN，C，HSMITH，SCFRALICK利用對(duì)DCT變換矩陣的直接分解，第一次提出不通過(guò)FFT實(shí)現(xiàn)的FDCT算法【2】，至此以后出現(xiàn)了多種DCT快速算法。其中，最多也是應(yīng)用得最普遍的是長(zhǎng)度為2”的算法。由于應(yīng)用中對(duì)DCT長(zhǎng)度的要求，針對(duì)非2”長(zhǎng)度DCT的算法研究受到人們的重視，實(shí)時(shí)處理應(yīng)用要求以更快的速度實(shí)現(xiàn)DCT變換，通過(guò)數(shù)字濾波器以及硬件實(shí)現(xiàn)DCT的途徑也越來(lái)越受到人們的注意。最初的DCT算法是基于FFT的，HARALICK3】用N點(diǎn)FFT構(gòu)造了第一個(gè)基于FFT的N點(diǎn)DCT算法，隨后NARASHIMA和PETCRSON引、TSANG和MILERL5L、MAKHOUL61、VETTERLI和NUSSBAOMERT7】也提出基于FFT的DCT算法。第一個(gè)直接設(shè)計(jì)的FDCT算法是由CHELA等根據(jù)矩陣分解方法提出的，計(jì)算8點(diǎn)DCT只需要16次乘法，比基于FFT的DCT算法減少了16，由于矩陣分解的方法不是唯一的，因此，存在類似的其它矩陣分解算法。LEE8】提出了一種以COS函數(shù)的倒數(shù)作乘法因子的快速算法，但當(dāng)變換長(zhǎng)度較大時(shí)將出現(xiàn)很大的乘法因子，使運(yùn)算過(guò)程中產(chǎn)生的計(jì)算誤差變大。HOU9】提出了一種與LEE算法類似的算法，但使用COS函數(shù)作為乘法因子，避免了LEE算法中的計(jì)算誤差大的問(wèn)題。HOU和LEE算法具有相同的計(jì)算復(fù)雜性，計(jì)算8點(diǎn)DCT都只需要12次乘法，達(dá)到了最少的乘法次數(shù)。CHAN和HO10】、WU和PAOLONI】將HOU算法推廣到二維DCT。ARGUELLO和ZAPATA121、BRITANAK13】【141，提出了修正的HOU算法，減少了算法中的移位操作量，根據(jù)應(yīng)用中并非所有DCT系數(shù)都需要的特點(diǎn)，SKODRAS”】提出了計(jì)算DCT低頻系數(shù)的截?cái)嗨惴?。?yīng)用中往往需要非2”長(zhǎng)度的DCT快速算法，YANGLL6】等提出了第一個(gè)素因子DCT實(shí)現(xiàn)算法并將算法應(yīng)用到硬件實(shí)現(xiàn)中【17】，然而，他們的算法要求比較復(fù)雜的下標(biāo)映射。WANG和YIPTL8】推廣了YANG的算法，提出了一組計(jì)算離散三角變換DTT的素因子快速算法。隨后，LEE19】也修改了YANG算法，用查表的方法通過(guò)兩個(gè)映射表來(lái)實(shí)現(xiàn)下標(biāo)映射。針對(duì)快速變換算法的硬件實(shí)現(xiàn)，CHAKRABARTI和JAJAT20】提出了計(jì)算素因子DCT和離散哈脫萊變換DHT的SYSTOLIC結(jié)構(gòu)，其下標(biāo)映射類似LEE算法。LEE和HUANG2I】修正了LEE算法，提出了另一種素因子DCT算法，輸入下標(biāo)映射采用RUITANIAN映射，而輸出下標(biāo)映射則采用LEE算法的映射方法。不同于素因子算法，HEID鋤AN【22】提出一種將奇長(zhǎng)度DCT轉(zhuǎn)化為同長(zhǎng)度DFT的算法。CHCN和SIU23】利用數(shù)論方法，提出了一種將DCT轉(zhuǎn)化為循環(huán)卷積的快速算法，并建議采用分布結(jié)構(gòu)實(shí)現(xiàn)卷積【241。GUO等【25】修IEYCHELA和SIU算法，提出了素長(zhǎng)度DCT的SYSTOLIC陣列算法。10第一章緒論在各種一維DCT快速算法不斷提出的同時(shí)，為了適應(yīng)多維信號(hào)處理的需要，二維及多維DCT算法的研究也受到人們的重視，KAMANGAR和RAO261提出了一種將二維DCT轉(zhuǎn)化為一維變換的算法，HAQUE從變換矩陣分解的角度出發(fā)，修改了KAMANGAR和RAO的算法【271，NASRABADI和KING281、VETTERLI29】采用類似一維的方法，提出將二維DCT轉(zhuǎn)換為二維DFT的實(shí)現(xiàn)算法。CHO等3032通過(guò)輸入輸出下標(biāo)映射的方法，將NN二維DCT用N個(gè)N點(diǎn)一維DCT實(shí)現(xiàn)，乘法復(fù)雜性降低到行列法計(jì)算的一半；HUANG和W033】用類似的方法給出另一種將NN二維DCT用N個(gè)N點(diǎn)一維DCT實(shí)現(xiàn)的算法。除了上面所述的各種DCT算法，還有多種將DCT轉(zhuǎn)換為其它變換進(jìn)行計(jì)算的方法。DUHAMEL和GUILLEMOT34】利用快速多項(xiàng)式變換算法提出了另一種計(jì)算二維DCT的方法。TA掣”】提出用快速離散RADON變換實(shí)現(xiàn)二維DCT。在研究各種DCT快速算法的同時(shí)，為了適應(yīng)實(shí)時(shí)信號(hào)處理的要求，獲得更快的變換速度，人們也在尋找采用硬件或并行處理的DCT實(shí)現(xiàn)方案【36441。12本文的創(chuàng)新點(diǎn)本文主要對(duì)離散余弦變換的快速算法設(shè)計(jì)及其VLSI結(jié)構(gòu)進(jìn)行了研究，研究?jī)?nèi)容包括一維DCT快速變換算法，二維以及高維DCT快速變換算法，DCT快速算法實(shí)現(xiàn)的VLSI結(jié)構(gòu)研究等幾個(gè)方面。本文的主要?jiǎng)?chuàng)新點(diǎn)簡(jiǎn)述如下1提出了一種計(jì)算二維DCT的快速算法一部分和分解算法PSDA。利用積化和差的性質(zhì)，該算法將變換形式中的兩個(gè)余弦因子相乘的形式轉(zhuǎn)換為兩個(gè)余弦因子相加的形式。在時(shí)域上將余弦因子相同的數(shù)據(jù)進(jìn)行累加求得部分和。根據(jù)部分和相同的準(zhǔn)則，將頻域上的數(shù)據(jù)進(jìn)行子集劃分，同一集合內(nèi)的頻域數(shù)據(jù)為其相關(guān)部分和的一維DCT變換輸出。2研究了PSDA算法在2”2”長(zhǎng)度二維DCT中的應(yīng)用，提出了變換輸出的頻域子集劃分理論，部分和的計(jì)算方法及公共加法項(xiàng)的合并原則。與目前已知的高效直接算法CHO算法和森川良孝算法相比，PSDA算法有著更少的乘法次數(shù)和加法次數(shù)。3研究了PSDA算法在QXQQ為素?cái)?shù)長(zhǎng)度二維DCTII變換中的應(yīng)用。PSDA算法將二維數(shù)據(jù)變換轉(zhuǎn)換為若干個(gè)N點(diǎn)一維素?cái)?shù)長(zhǎng)度DCT奇系數(shù)或偶系數(shù)的計(jì)算；進(jìn)而將奇系數(shù)或偶系數(shù)的變換轉(zhuǎn)化為循環(huán)卷積或扭循環(huán)卷積的形式，解決了當(dāng)前常用高效算法只適用于長(zhǎng)度為2”的情況而不能應(yīng)用于素?cái)?shù)長(zhǎng)度的問(wèn)題。電子科技大學(xué)博士學(xué)位論文4研究了PSDA算法在2N2打長(zhǎng)度二維DCTII變換中的VLSI實(shí)現(xiàn)結(jié)構(gòu)。一般一個(gè)硬件算法結(jié)構(gòu)的優(yōu)劣主要決定于三個(gè)性能參數(shù)面積，速度，精度，在此三個(gè)參數(shù)基礎(chǔ)上，還要求結(jié)構(gòu)規(guī)則，具有模塊化，這樣有利于設(shè)計(jì)及版圖布局布線。PSDA算法的VLSI結(jié)構(gòu)著眼于減少使用乘法器和加法器的數(shù)目。該結(jié)構(gòu)使用了2臚1個(gè)乘法器和2川個(gè)加法器。相對(duì)于行列分解法結(jié)構(gòu)RCM，該結(jié)構(gòu)不需要轉(zhuǎn)置存儲(chǔ)器，而加法器和乘法器的數(shù)量與之規(guī)模相當(dāng)。相對(duì)于其他直接算法，該結(jié)構(gòu)所用的乘法器的數(shù)量是最少的。5研究了PSDA算法在QXQQ為奇素?cái)?shù)長(zhǎng)度二維DCTII變換中的VLSI實(shí)現(xiàn)結(jié)構(gòu)。該結(jié)構(gòu)的核心為一個(gè)部分和計(jì)算單元和矩陣變換單元。相對(duì)于行列分解法結(jié)構(gòu)RCM，該結(jié)構(gòu)不需要轉(zhuǎn)置存儲(chǔ)器，加法器和乘法器的數(shù)量與之規(guī)模相當(dāng)。13全文結(jié)構(gòu)安排本文主要研究二維DCT快速算法及其VLSI實(shí)現(xiàn)結(jié)構(gòu)，文章的內(nèi)容安排如下第一章為緒論，首先介紹了離散余弦變換DCT的概念然后介紹了應(yīng)用背景，實(shí)現(xiàn)原理和未來(lái)發(fā)展趨勢(shì)；最后說(shuō)明了本論文所要解決的問(wèn)題和取得的成果。第二章為離散余弦變換DCT快速算法及其VLSI實(shí)現(xiàn)綜述。首先指明了DCT快速算法發(fā)展中面臨的主要問(wèn)題，重點(diǎn)說(shuō)明了DCT快速算法所要解決的關(guān)鍵技術(shù)問(wèn)題，綜述了各種一維和二維的DCT快速算法的發(fā)展概況。一般的DCT快速算法可劃分為兩種間接算法和直接算法。兩種算法都是集中在蝶型結(jié)構(gòu)上，而且目的都是為了減少乘法和加法的計(jì)算量。其次介紹并總結(jié)了適合VLSI實(shí)現(xiàn)的各種DCT硬件結(jié)構(gòu)的特點(diǎn)。介紹了基于乘法器，分配算法，脈動(dòng)陣列，CORDIC算法等當(dāng)前流行的DCT結(jié)構(gòu)。最后介紹了ASIC技術(shù)和ASIC設(shè)計(jì)流程。對(duì)EDA開(kāi)發(fā)工具進(jìn)行了簡(jiǎn)單的說(shuō)明。第三章敘述了數(shù)論基本知識(shí)，分別敘述了同余，唯一分解定理，剩余類，簡(jiǎn)化剩余系，同余式，中國(guó)剩余定理，原根和指標(biāo)，為后續(xù)章節(jié)的展開(kāi)提供理論基礎(chǔ)。數(shù)論理論在快速變換領(lǐng)域有著廣泛的應(yīng)用。由于很多正交變換系的核函數(shù)是三角函數(shù)，而三角函數(shù)對(duì)2萬(wàn)做求模運(yùn)算具有不變性。因此快速變換的算法研究可以轉(zhuǎn)化為數(shù)論中的同余問(wèn)題。在一維DCT變換中，當(dāng)變換長(zhǎng)度為合數(shù)時(shí)，通過(guò)數(shù)論中的中國(guó)剩余定理可以將一個(gè)長(zhǎng)序列的一維DCT變換轉(zhuǎn)換為一個(gè)多維短序列DCT變換。從而大大減少了計(jì)算復(fù)雜度。當(dāng)變換長(zhǎng)度為素?cái)?shù)時(shí)，通過(guò)數(shù)論中的原根與指標(biāo)可以將一維FFT變換轉(zhuǎn)換為循環(huán)卷積，一維DCT變換轉(zhuǎn)換為循環(huán)卷積或12第一章緒論扭循環(huán)卷積。循環(huán)卷積的計(jì)算可以通過(guò)先求兩個(gè)序列Z變換乘積的反Z變換求得。而數(shù)論理論中的同余式理論在這個(gè)領(lǐng)域得到了廣泛的應(yīng)用。第四章敘述了一維離散余弦變換DCT的快速變換算法設(shè)計(jì)。一維DCT快速變換算法是所有DCT快速變換算法的基礎(chǔ)。本章詳細(xì)敘述了2”，礦，素長(zhǎng)度以及任意長(zhǎng)度DCT變換算法，為下一章的部分和分解算法打下基礎(chǔ)。第一部分?jǐn)⑹隽?訂長(zhǎng)度DCT的常用快速變換算法一基2遞歸分解算法。第二部分為礦長(zhǎng)度的基G遞歸分解算法。第三部分為素長(zhǎng)度DCT快速算法，算法的核心在于去掉變換核中的2針1項(xiàng)，將2X1K形式轉(zhuǎn)換為M形式，再通過(guò)數(shù)論理論中原根的特性，將原變換轉(zhuǎn)換為循環(huán)卷積的形式。最后為任意復(fù)合長(zhǎng)度的一維DCT快速算法的設(shè)計(jì)思想，通過(guò)中國(guó)剩余定理，闡述了一維DCT與多維DCT之間的相互轉(zhuǎn)換關(guān)系。通過(guò)坐標(biāo)變換，一維DCT可以分解為多維DCT，而多維DCT也可以轉(zhuǎn)換為一維DCT。第五章為二維離散余弦變換算法研究。利用數(shù)論理論，本章提出了二維DCT變換的部分和分解快速算法PSDA。PSDA算法是一種直接分解算法，其核心思想為將二維DCT變換直接轉(zhuǎn)換為若干個(gè)一維DCT變換實(shí)現(xiàn)。根據(jù)同余理論，將頻域輸出劃分為若干個(gè)子集，每一子集內(nèi)的所有元素構(gòu)成一個(gè)維DCT變換的輸出。第2節(jié)詳細(xì)講述了2”2療型部分和分解算法的推導(dǎo)和實(shí)現(xiàn)。在本節(jié)中給出了部分和定義，分析了部分和的特性，提出了變換輸出的子集劃分準(zhǔn)則，部分和的計(jì)算方法，公共加法項(xiàng)的合并原則。第三節(jié)把部分和算法擴(kuò)展到QXQQ為奇素?cái)?shù)型二維DCT，將變換輸出劃分為四個(gè)分量之和。第一個(gè)分量為一個(gè)Q12XQ12型二維DCT，PSDA算法可以將其直接轉(zhuǎn)換為2G一1個(gè)G一12長(zhǎng)度循環(huán)卷積的計(jì)算。第二個(gè)分量和第三個(gè)分量為一個(gè)一維DCT變換，可通過(guò)第四章中敘述的算法求解，第四個(gè)分量為一個(gè)常量。本節(jié)最后一節(jié)給出了PSDA算法在該類型DCT中的運(yùn)算復(fù)雜度。第六章是PSDA算法的VLSI實(shí)現(xiàn)。第二節(jié)講述了PDSA算法的VLSI結(jié)構(gòu)設(shè)計(jì)。該結(jié)構(gòu)的核心是部分和的計(jì)算。根據(jù)PSDA算法原理，經(jīng)過(guò)預(yù)處理對(duì)該類型DCT的每一列輸入數(shù)據(jù)，某一特定余弦因子對(duì)應(yīng)的元素不會(huì)超過(guò)兩個(gè)。這兩個(gè)元素可以通過(guò)查表法選出累加得到部分和輸出。最終的變換輸出可以既可以通過(guò)乘加運(yùn)算求和輸出，也可以使用其他一維DCT變換模塊輸出。在本節(jié)中，分別給出了2打2一型和QQ型DCT的VLSI結(jié)構(gòu)。第三節(jié)講述了算法的ASIC驗(yàn)證過(guò)程，并將驗(yàn)證后的IP核與其他公司的產(chǎn)品進(jìn)行了比較分析。第七章總結(jié)了全文的設(shè)計(jì)工作，提出了算法未來(lái)的發(fā)展方向。電子科技入學(xué)博士學(xué)位論文第二章離散余弦變換DOT快速算法及其VLSI實(shí)現(xiàn)綜述本章敘述了一維離散余弦變換，