中南民族大學碩士學位論文嵌入式塊解碼器研究與硬件設計姓名:陳方強申請學位級別:碩士專業(yè):通信與信息系統(tǒng)指導教師:熊承義20090607中南民族大學碩士學位論文摘要嵌入式優(yōu)化截斷塊編碼(EmbeddedBlockCoderwithOptimizedTruncation,簡記為EBCOT算法是由DavidTaubman提出的一種圖像壓縮編碼技術。EBCOT編碼算法采用了獨特的兩層編碼結構,并引入了多通道位平面編碼以及分層組織比特流的技術,這樣不僅具有更好的壓縮性能,而且使得生成的碼流具有分辨率可伸縮、質量可伸縮、隨機訪問和處理等優(yōu)秀的特性。EBCOT算法被最新的靜止圖像壓縮標準JPEG2000采納為其編解碼引擎。在JPEG2000的諸多應用中,如數碼相機、高清電視、衛(wèi)星遙感圖像處理,考慮到速度、面積和功耗的需求,研究高性能EBCOT編解碼器的硬件實現具有十分重要的意義。論文的主要工作包括:首先對靜態(tài)圖像壓縮標準JPEG2000及其主要架構進行了簡要的介紹。然后詳細介紹了JPEG2000中的EBCOT算法以及整體架構,并對位平面解碼BPD算法進行了重點介紹。在此基礎上,針對硬件高速實現,對其進行了優(yōu)化。采用了基于選擇性采樣跳過策略和推測處理方式的位平面解碼架構,這樣就可以大大減小關鍵路徑的延遲。相對于現有方法的基本BPD架構,改進的算法可以將吞吐量提高50%-100%,同時只增加25%-30%的硬件消耗。在介紹MQ算術解碼算法的基礎上,詳細分析了架構中解碼的工作流程及各個流水級模塊的設計。進行相應算法優(yōu)化的基礎上,提出了基于4級流水線的高性能MQ解碼器結構。在QuartusII開發(fā)環(huán)境下對設計進行RTL級描述,用Modelsim進行了相應的功能仿真;針對Altera系列FPGACycloneIIEP2C35F484C8進行綜合,并完成時序仿真。實驗結果表明:該設計的最高工作頻率可達37.64MHz,占資源為557個LE。在利用有限資源的情況下可以大幅度提高MQ算術解碼器的速度,基本能滿足JPEG2000系統(tǒng)的要求。關鍵詞:嵌入式優(yōu)化截斷塊編碼位平面解碼MQ算術解碼現場可編程門陣列-I-I嵌入式塊解碼器研究與硬件設計AbstractEBCOT(EmbeddedBlockCoderwithOptimizedTruncationalgorithmisanimagecompressioncodingtechniquesproposedbyDavidTaubman.EBCOTencodingalgorithmusesauniquetwo-tiercodingstructureandintroducethetheoryofmulti-channelbit-planecodingandthehierarchicalorganizationofbit-stream.Thus,ithasnotonlybettercompressionperformance,butalsomakesthegeneratedcodestreamwithOutstandingcharacteristicsofscalableresolution,scalablequality,andrandomaccess.EBCOTalgorithmisadoptedascodecengineofthelateststillimagecompressionstandardJPEG2000.Inconsiderationofspeed,areaandpower,thestudyonthehardwareimplementationofhighperformanceEBCOTcodecissignificantinmanyrealsystemsusingJPEG2000,suchasdigitalcamera,highdefinitiontelevision,Satelliteremotesensingimageprocessingandsoon.Thecontributionsofthisthesisincludes:Atfist,abriefintroductionofstillimagecompressionstandardJPEG2000anditsmainstructurewasmadeinthispaper.WedescribedtheEBCOTalgorithmindetail,aswellastheoverallframework.Basedonspecialintroductionofbit-planedecoderalgorithm,weoptimizedthedecoderflowforthehigh-speedhardwareimplement.Wehavestudiedanovelselectivesample-skippingstrategyforBPDtoincreasetheoverallblockdecoderthroughput.Thecriticalpathoftheproposedarchitectureisfurtherimprovedbytheuseofspeculativeprocessing.Thethroughputratesoftheusedarchitecturesarehigherby50%-100%,thanthebaselinearchitecturethatisbasedonexistingapproaches.Theincreasedthroughputratesarearchivedwithonlya25%-30%increaseoftheBPDhardwarecost.Then,theMQarithmeticdecodingalgorithmhasbeeninvestigatedindepthinthispaper.AhighperformancearchitectureofMQdecoderwith4-stagepipelinehasbeenproposedbyalgorithmoptimization.ThisdesignhasbeendescribedbyusingRTLHDL,andimplementedwithAltera’sFPGACycloneIIEP2C35F484C8.ThefunctionalsimulationandtimingsimulationarecarriedoutunderQuartusIIsoftware.Experimentalresultsindicatethatthemaximumoperationfrequencyoftheproposeddesigncanreachashighas37.64MHz,using557LE.Byusingonlylimitedresources,thespeedofMQdecodercanbeefficientlyincreased,whichalsomeettherequirementsofJPEG2000system.Keywords:EBCOTBPDMQdecoderFPGAII中南民族大學學位論文原創(chuàng)性聲明本人鄭重聲明:所呈交的論文是本人在導師的指導下獨立進行研究所取得的研究成果。除了文中特別加以標注引用的內容外,本論文不包含任何其他個人或集體已經發(fā)表或撰寫的成果作品。對本文的研究做出重要貢獻的個人和集體,均已在文中以明確方式標明。本人完全意識到本聲明的法律后果由本人承擔。作者簽名:日期:年月日學位論文版權使用授權書本學位論文作者完全了解學校有關保留、使用學位論文的規(guī)定,同意學校保留并向國家有關部門或機構送交論文的復印件和電子版,允許論文被查閱和借閱。本人授權中南民族大學可以將本學位論文的全部或部分內容編入有關數據庫進行檢索,可以采用影印、縮印或掃描等復制手段保存和匯編本學位論文。本學位論文屬于1、保密□,在______年解密后適用本授權書。√2、不保密□。(請在以上相應方框內打“√”作者簽名:日期:年月日導師簽名:日期:年月日中南民族大學碩士學位論文第1章緒論1.1課題背景近些年來,隨著多媒體技術和互聯(lián)網的不斷發(fā)展,圖像壓縮技術也獲得了空前的進步。數碼相機、數碼攝像機等手持式設備的普及應用,要求圖像壓縮技術能夠在較高的壓縮比下實現較好的圖像質量,以滿足存儲空間有限條件下的海量數據壓縮問題。同時,醫(yī)療,遙感等應用領域要求圖像壓縮提供較好的靈活性和延展性。傳統(tǒng)的JPEG標準已無法滿足人們對于多媒體圖像處理的要求,由此誕生了新一代靜止圖像壓縮標準JPEG2000[1]。相對于JPEG來說,JPEG2000提供了一套新的標準,它所具有的一些特征對于一些互聯(lián)網和多媒體技術應用是非常重要的。JPEG的四種模式——順序模式、漸進模式、無損模式和分層模式被集成在一個新的標準之中。在編碼端以最佳的壓縮質量(包括無失真壓縮和最大的圖像分辨率壓縮圖像,在解碼端可以從碼流中以任意的圖像質量和分辨率解壓圖像。因而,JPEG2000可以在大多數圖像領域得到應用,如數碼相機、互聯(lián)網、彩色傳真、數字攝像、醫(yī)療圖像、移動通信、數字電影等。JPEG2000編碼系統(tǒng)的基本架構可以分為預處理、空間變換、位平面建模和算術編碼等幾個部分。其中,空間變換采用DWT[2](DiscreteWaveletTransformation,離散小波變換,在相同的圖像壓縮率下,對靜止圖像,DWT編碼能夠獲得比DCT編碼高約1dB的峰值信噪比[3]。JPEG2000引入全新的EBCOT(EmbeddedBlockCodingwithOptimizedTruncation算法,它是JPEG2000體系中的關鍵部分,數據壓縮和碼流控制都在這里實現,具有計算密集,以位處理為主,耗時較大的特點。EBCOT編碼算法采用了獨特的兩層編碼結構,第一層(Tier-1包括上下文環(huán)境建模[4]和算術編碼[5]兩部分,進行嵌入式塊編碼產生壓縮的碼流。第二層(Tier-2對生成的壓縮碼流進行分層組織,采用了壓縮后率失真優(yōu)化算法和質量層技術。在整個JPEG2000編解碼系統(tǒng)中,EBCOT編解碼器已經成為系統(tǒng)運算速度的瓶頸。因此,如何立足于硬件實現,提高EBCOT編解碼效率成為JPEG2000編解碼系統(tǒng)硬件高速實現需要解決的關鍵問題之一。因此在本課題中,需要對JPEG2000中的位平面解碼算法和算術解碼算法進行優(yōu)化,降低其算法復雜度,并使其適合于硬件實現;同時設法提高編解碼效率和降低硬件規(guī)模,使其達到高速解碼及節(jié)省硬件資源的要求。-1-11.2研究現狀在JPEG2000編解碼系統(tǒng)的實現上,有基于軟件的實現方案和基于硬件的實現方案。其中,Jasper[6],Kakadu,OpenJPEG等都是比較流行的JPEG2000編解碼軟件。與基于軟件的解決方案相比,基于VLSI的硬件解決方案在編解碼效率上更高,更適合實時編解碼的要求,但其開發(fā)的復雜度也更高,調試更困難。自從JPEG2000標準誕生以來,多家公司和研發(fā)機構發(fā)布了基于JPEG2000標準的硬件解決方案,其中最成功的是ADI公司的ADV202芯片[7]。它是一款單片JPEG2000編解碼芯片,具有實時壓縮和解壓縮標準清晰度(SD視頻信號和高清晰度(HDTV視頻信號功能,該芯片帶有一個靈活接口,適用于多種視頻和靜止圖像格式。ADV202有兩種工作模式,一種是編碼模式,另一種是解碼模式。在編碼模式下,視頻數據通過VDATA總線輸入ADV202,由小波核對輸入的數據進行小波變換,并把所有頻率子帶的小波系數存入ADV202內部的存儲器。每一個子帶根據ADV202編碼參數的設置進一步分成編碼子塊,然后由熵編碼器對編碼子塊執(zhí)行內容建模和算術編碼,運算的結果存入內部存儲器。隨后由內部DMA傳輸到CODEFIFO,通過HDATA總線把壓縮數據流輸出ADV202。在解碼模式下,工作過程是編碼模式的逆過程[8]。然而,由于JPEG2000編解碼算法的復雜性,直到目前為止,其VLSI實現的大規(guī)模市場應用尚未展開,因此,研究JPEG2000編解碼系統(tǒng)的高性能低資源占用的VLSI實現仍然是當前的一個研究熱點,而其中對于作為系統(tǒng)速度瓶頸的自適應算術編解碼VLSI實現的研究尤其具有重要意義。算術編碼是一種到目前為止最佳的熵編碼方法。但早期的算術編碼存在無限精度運算的問題,即隨著編碼消息長度的增加,遞歸運算需要的計算精度隨之增加,表示數據所需的位數也隨之增多,這導致軟硬件實現的成本太高,阻礙了它的應用。直到有人證明編碼過程可以用有限精度處理技術逼近,算術編碼才真正開始得到廣泛的應用。算術編碼的另一缺陷是編碼速度太低,這是因為編碼迭代過程中含有整數乘除運算,這些運算對于軟件執(zhí)行和硬件設計是十分不利的。IBM公司對算術編碼進行了大量的研究,提出了一個用移位和加法實現二值算術編碼的方法,從而避免了復雜的乘除運算,并發(fā)表了著名的Q編碼器[9][10],隨后又提出QM編碼器[11](用于JBIG標準和MQ編碼器(用于JBIG2和JPEG2000標準。MQ編碼器在Q編碼器的基礎上,進一步改進了符號概率估計系統(tǒng)。在MQ算術編解碼器的VLSI實現方面,國內外的研究人員做了大量的研究,提出了很多有價值的實現方案,并采用了很多先進的VLSI設計技術。本文對當前國內外在該方向的研究現狀和先進技術進行了了解并加以綜合分析,以作為本文的參考和借鑒。1.3本文的主要內容和結構論文共分5章,第1章緒論,第2-4章為論文的主體部分,第5章為總結和展望。論文的詳細安排如下:第2章為本論文的理論基礎。主要對靜態(tài)圖像壓縮標準JPEG2000及其主要架構進行了簡要的介紹。然后詳細介紹了JPEG2000中的EBCOT算法以及整體架構。第3章對位平面解碼算法進行了重點介紹,并在此基礎上,針對硬件高速實現,對其進行了優(yōu)化,采用了基于選擇性采樣跳過策略和推測處理方式的位平面解碼架構,并做了相應的性能分析。第4章在詳細介紹了MQ解碼算法的基礎上,詳細分析了架構中解碼的工作流程及各個流水級模塊的設計,并進行了相應的算法優(yōu)化,提出基于4級流水線的高性能MQ解碼器結構。最后進行了性能分析和功能仿真。第5章得出結論,對本文的成果進行了總結,并對今后的研究進行了展望。第2章JPEG2000標準介紹本章闡述了最新的靜態(tài)圖像壓縮標準——JPEG2000核心編碼技術的發(fā)展背景,介紹了該標準的應用領域及其新特征、編碼系統(tǒng)結構、標準文件格式和相對JPEG所采用的新技術。2.1JPEG2000核心編碼技術的發(fā)展基于小波變換的圖像編碼方法是上個世紀90年代左右提出的新方法,它吸收了變換編碼和子帶編碼的優(yōu)點,克服了傳統(tǒng)DCT[12]編碼在低比特率時會產生方塊效應的缺點,能夠更好的利用人的視覺特性。另外,由于小波變換具有非常好的能量聚集性能,而且能夠用于圖像變換的小波基非常豐富,因此基于小波變換的圖像編碼成為目前圖像壓縮領域的一個研究熱點。最新的靜態(tài)圖像壓縮標準——JPEG2000中采用的是一種基于最優(yōu)截斷的嵌入式塊編碼算法(EBCOT:EmbeddedBlockCodingwithOptimizedTruncation,它是將圖像小波變換后生成的子帶進一步分成小的矩形碼塊。每個碼塊采用基于位平面的方式進行獨立編碼,并采用基于內容模型的算術編碼進行壓縮生成壓縮碼流。為了使編碼圖像達到目標比特率,對每個碼塊計算率失真曲線上的幾個分割點,并由此實現對每個碼塊的比特數進行最優(yōu)分配。因此在編碼時,首先對每個碼塊用較高的比特率編碼,然后再根據最優(yōu)比特率分配計算確定的分割點來截斷每個塊的比特流。對應于一個目標比特率集合,可以確定其對應的最優(yōu)分割點集。碼塊的比特流一旦被截斷來達到目標比特率,就按通常的位平面順序重新組織形成嵌入式比特流。EBCOT編碼算法得到的比特流具有多分辨率和多層次質量優(yōu)化的特征,其率失真性能略優(yōu)于SPIHT算法,但復雜程度也高于SPIHT算法。2.2JPEG2000的應用及特征JPEG2000標準提供了一套新的特征,它把JPEG的四種模式(順序模式、漸進模式、無損模式和分層模式集成在一個標準之中。在編碼端以最大的壓縮質量和最大的圖像分辨率壓縮圖像,在解碼端可以從碼流中以任意的圖像質量和分辨率解壓圖像,最大可達到編碼時的圖像質量和分辨率。JPEG2000應用的領域包括互聯(lián)網、傳真、打印、掃描、數字攝像、遙感、移動通信、醫(yī)療圖像和電子商務等等。它的最主要的特征如下:(l高壓縮率:由于在離散子波變換算法中,圖像可以轉換成一系列更加有效存儲像素模塊的“子波”,因此,JPEG2000格式的圖片壓縮比可在現在的JPEG基礎上再提高10%—30%,而且壓縮后的圖像顯得更加細膩平滑。(2無損壓縮和有損壓縮:JPEG2000提供無損和有損兩種壓縮方式,無損壓縮在許多領域是必須的,例如醫(yī)學圖像中有時有損壓縮是不能忍受的。同時JPEG2000提供的是嵌入式碼流,允許從有損到無損的漸進解壓。(3漸進傳輸:采用JPEG2000格式的圖像支持漸進傳輸(ProgressiveTransmission。即先傳輸圖像輪廓數據,再逐步傳輸其他數據來不斷提高圖像質量。(4感興趣區(qū)域壓縮:可以指定圖片上感興趣區(qū)域(RegionofInterest,然后在壓縮時對這些區(qū)域指定壓縮質量,或在恢復時指定某些區(qū)域的解壓縮要求。這是因為子波在空間和頻率域上具有局域性,要完全恢復圖像中的某個局部,并不需要所有編碼都被精確保留,只要對應它的一部分編碼沒有誤差就可以了。(5碼流的隨機訪問和處理:這一特征允許用戶在圖像中隨機地定義感興趣區(qū)域,使得這一區(qū)域的圖像質量高于其它區(qū)域,碼流的隨機處理允許用戶進行旋轉、移動、濾波和特征提取等操作。(6容錯性:在碼流中提供容錯性有時是必要的,例如在無線等傳輸誤碼很高的通信信道中傳輸圖像時,沒有容錯性是讓人不能接受的。(7開放的框架結構:為了在不同的圖像類型和應用領域優(yōu)化編碼系統(tǒng),提供一個開放的框架結構在是必須的,在這種開放的結構中編碼器只實現核心的工具算法和碼流的解析,如果需要,解碼器可以要求數據源發(fā)送未知的工具算法。(8基于內容的描述:圖像文檔、圖像索引和搜索在圖像處理中是一個重要的領域,基于內容的描述在JPEG2000中是壓縮系統(tǒng)的特性之一。2.3JPEG2000編碼系統(tǒng)結構國際標準15444中給出了JPEG2000標準核心處理算法的處理流程。這里給出了詳細的編碼器結構如圖2.1所示。圖2.1JPEG2000編碼框圖在編碼過程中,首先對輸入圖像進行預處理和直流變換,分成不同的圖像分量和基本的編碼單元塊(稱為Tile,然后對每個Tile進行小波變換,變換后的數據根據要求選擇是否進行標量量化處理。然后將處理后的各個子帶數據分成固定尺寸的碼塊(CodeBlock,每個碼塊單獨地進行位平面編碼和算術編碼處理,生成各個碼塊的嵌入式碼流。然后,按照率失真最優(yōu)理論分層組織,形成不同質量的層(Layer對每一層,按照一定的碼流格式打包,輸出壓縮碼流。解碼過程是編碼過程的逆過程,根據壓縮碼流中存儲的參數,對應于編碼器各個部分進行逆向操作,首先對碼流進行算術解碼、位平面解碼,然后解量化和小波反變換,最后生成重建圖像。JPEG2000編碼過程主要分為以下幾個過程:預處理、核心處理、碼率控制和位流組織。預處理部分包括直流變換(DC變換、分量變換和圖像分片。核心處理部分由離散小波變換、量化、位平面編碼和算術編碼組成。碼流組織部分則包括區(qū)域劃分、碼塊、層和包的組織。2.4JPEG2000的文件格式在ISO-15444Part1規(guī)定基本的文件格式JP2。文件格式JP2提供了如下一種機制,即可以將應用規(guī)范與JPEG2000的碼流數據關聯(lián)起來。雖然,JPEG2000的碼流是完全自包含的,但是在應用的時候必須對其進行解碼,此外一些與廠商相關的信息以及版權信息是無法在JPEG2000的壓縮數據碼流中包含的,而這些應用規(guī)范的內容可以以包含在JPEG2000的文件格式中。這種文件格式提供了知識產權信息和廠商信息,可以做到添加水印以保護產權。根據上面的說明,我們相信JPEG2000將會成為主流的靜態(tài)圖像壓縮標準,廣泛得應用于因特網、移動和便攜設備、印刷、掃描(出版物預覽、數字攝影、遙感、傳真(包括彩色和因特網傳真、醫(yī)學應用、數字圖書館、電子商務等領域。2.5JPEG2000與JPEG標準比較較之前身JPEG靜態(tài)圖像壓縮標準,JPEG2000標準有了很大的發(fā)展。其編解碼器采用了如下的很多新技術:(1用離散二維小波變換(DWT取代離散余弦變換(DCT;(2在應用離散小波變換時,分別引入對數據整型到整型(IntegertoInteger的可逆(Reversible變換和實型到實型(RealtoReal的不可逆(Irreversible變換,從而實現對圖像的無損(Lossless壓縮和有損(Lossy壓縮兩種不同的編碼處理;(3采用了較以往各種零樹編碼更優(yōu)越的編碼算法——EBCOT算法(基于優(yōu)化截斷的嵌入式塊編碼算法;(4對量化后的小波變換系數采用基于位平面的多通道編碼技術;(5采用基于上下文關系(Context-Based的自適應二進制算術編碼器(MQCoder實現高效的算術熵編碼;(6采用兩級原語表示編碼后的圖像,分別為碼流和文件格式原語。2.6EBCOT算法簡介嵌入式優(yōu)化截斷塊編碼EBCOT(EmbeddedBlockCoderwithOptimizedTruncation算法是由DavidTaubman提出的一種最新的圖像壓縮編碼技術。EBCOT編碼算法采用了獨特的兩層編碼結構,引入了多通道位平面編碼及分層組織位流的思想,因此不僅具有更好的壓縮效果,而且生成的碼流具有分辨率可伸縮性、質量可伸縮性、隨機訪問及處理等優(yōu)良的特性。EBCOT被采納為最新的靜止圖像壓縮標準JPEG2000的編解碼引擎。由EBCOT生成的嵌入碼具有下列優(yōu)秀的特征:1可伸縮性的實現。通過以代碼塊為單位對小波變化后的子帶信號進行為平面編碼,可以實現分辨率、失真(SNR和位置的可伸縮性。還由于對色彩圖像也增加了分量的可伸縮性,所以,在JPEG2000中可在這些四維度上實現可伸縮性編碼。2緊密的內嵌處理。在通常的位平面編碼中,由于以位平面進行壓縮碼的截斷,所以,構成嵌入碼時的截斷精度粗糙。在EBCOT中,再以3個編碼掃描對一個位平面進行編碼,將各個掃描結束時間點選為代碼截斷點,因此,可實現更精密的內嵌處理。3可并行處理。由于能以代碼塊為單位單獨進行編碼,所以,可通過編碼和解碼的并行處理實現高速處理。4高容錯性。由于碼流被分層為空間位置、質量層,使子帶分層化,所以,可使部分碼流里引起的錯誤限制在局部區(qū)域。EBCOT算法的兩層編解碼結構如圖2.2所示。第一層(Tier-1包括上下文環(huán)境建模和算術編碼兩部分,進行嵌入式塊編碼產生壓縮的碼流。第二層(Tier-2對生成的壓縮碼流進行分層組織,采用了壓縮后率失真優(yōu)化算法和質量層技術。具體來說第一層編碼由以下幾個步驟組成:(1將經過小波變換和量化后的子帶系數組織成編碼塊(code-block;(2對每個編碼塊進行獨立的多通道位平面編碼(fractionalbit-planecoding,形成相應位樣本的上下文環(huán)境和決策數據對(Context-Decisiondatapairs;(3用基于上下文環(huán)境的自適應算術編碼器(MQ-coder對形成的上下文環(huán)境(Context和數據(Data進行算術編碼,產生嵌入式位流(embeddedbit-stream。EBCOT算法的第二層編碼對壓縮位流進行分層組織,即按照率失真最優(yōu)的原則,選取合適的截斷點截斷每一個編碼塊的壓縮位流,在滿足目標碼率的要求下,將位流組織成具有分辨率可伸縮性和質量可伸縮性的最終碼流。圖2.2EBCOT算法架構在EBCOT算法的兩層編碼結構中,其編碼獨立地實現于每一個編碼子塊,基于每個編碼塊的獨立編碼使得隨機存取及分辨率可伸縮性〔resolutionscalable〕成為可能。EBCOT算法中的上下文環(huán)境建模引入多通道分數位平面編碼的思想,由此可得到比單一位平面編碼更多的截斷點個數。越多的截斷點,表明圖像可提供更多的質量選擇。EBCOT算法在第二層編碼中通過采用率失真優(yōu)化及質量層的技術保證了壓縮碼流具有質量層的可伸縮性(SNRscalable。2.7小結本章首先介紹了JPEG2000核心編碼技術的發(fā)展及其應用和特征;詳細說明了JPEG2000編碼系統(tǒng)結構中的劃分:其中包括預處理、核心處理、碼率控制,及這三個部分的工作原理,JPEG2000的文件格式;然后對JPEG2000和JPEG標準進行了比較,最后介紹了EBCOT算法、特征及其特殊的兩層結構。第3章位平面解碼器的硬件設計研究3.1研究現狀為滿足多媒體應用和互聯(lián)網產品如數碼相機,高清電視等的高速實時運行的要求,位平面編解碼器的硬件實現成為一種必然,為此高速高性能位平面編解碼器的VLSI實現已成為國內外有很多機構和學者研究的熱點。迄今為止,已經出現很多新的技術[13-23]能夠很好的提高位平面解碼器的性能,其中主要包括三類:通道并行編碼,優(yōu)化串行編碼和位平面并行編碼。為提高位平面編解碼器的吞吐量,必須減少掃描冗余時間,提高處理的并行性;為了降低系統(tǒng)功耗可以考慮減少對存儲單元的訪問次數;為減小系統(tǒng)VLSI實現的面積,通常會盡量減少中間存儲單元的的規(guī)模.在減少冗余掃描時間方面,Lian等人[24]首先提出了一種基于采樣跳躍(sampleskipping和樣條組跳躍(Group-of-columnskipping的優(yōu)化串行位平面編碼掃描技術,朱悅心等人[25]提出了一種基于多級查詢表的位平面掃描優(yōu)化方法,它們都可以一定程度上減少冗余掃描時間.在并行編解碼方面,Chiang等人[26]提出了一種通道并行編碼技術,在提出對當前樣條列的重要性傳播通道,延遲樣條列的幅度細化通道和清除通道并行處理的基礎上,實現了3個編碼通道對位平面的掃描一次完成.在改進存儲單元訪問方面,Fang等人[17]提出了一種基于字級(位平面并行的編碼算法和結構,在文獻[18]中Fang等人又提出用兩次掃描來完成字級位平面并行編碼,這種方法需要較多的中間存儲單元.Amit等人[27]提出一種基于選擇性樣本跳過方法的位平面解碼器結構,它與Dyer等人[28]提出的低延遲算術解碼器級聯(lián)可以減少位平面解碼器在解碼過程中的等待時間,大大提高了處理速度和吞吐量。3.2位平面編解碼概述上下文建模又稱為位平面編碼(BPC,Bit-PlaneCoding,上下文建模就是將小波變換系數劃分成固定大小的代碼塊,再將各個變換系數作位平面展開,對碼塊進行逐個位平面的掃描,對每個位形成一個上下文標志(CX,ContextLabel和判決位(D,Decision。圖3.1上下文建模掃描方式在上下文建模過程中,編碼過程從最重要的位平面開始依次進行掃描編碼,每次編碼一個系數位平面;每個位平面按照規(guī)定的順序進行數據掃描。掃描過程從位平面的左上面的系數開始,連續(xù)掃描第一列的第一組4個系數后,然后轉向掃描第二列的第一組4個系數,如此一直掃描到最后一列的第一組4個系數;然后,轉向掃描第一列的第二組4個系數,一直到最后一列的第二組4個系數;按照這樣的順序依次掃描整個位平面。這里定義各列4個系數組成的數據塊為一個數據編碼帶(stripe。圖3.1給出了每個位平面的掃描方式示意圖。每個位平面按照上述方式進行三次掃描,分別對應著三種編碼過程:重要性傳播編碼過程(SignificancePropagationPass、幅度精煉編碼過程(MagnitudeRefinementPass和清除編碼過程(CleanupPass。這種多次位平面掃描編碼方式的主要優(yōu)點是可以生成最優(yōu)的嵌入式碼流,可以提供多個率失真截斷點。在編碼過程中,編碼塊中的每個系數對應著一個狀態(tài)變量,用來表示編碼過程中對應系數的狀態(tài)情況,這樣每個碼塊對應著一個狀態(tài)變量平面。編碼的初始化時,狀態(tài)變量平面的各個狀態(tài)初始化為“0”,表示相應的系數為不重要.在編碼過程中,當遇到每個系數的第一個比特“1”時,該系數對應的狀態(tài)變量變?yōu)椤?”,表示該系數成為重要系數.編碼過程中,每個位平面的各個編碼系數比特對應著一個內容矢量。該內容矢量是由編碼的系數比特周圍的8個相鄰系數比特重要性情況組成,如圖3.2中系數內容窗所示。D0V0D1H0XH1D2V1D3圖3.2每個系數的8個相鄰位在EBCOT編碼算法中的上下文環(huán)境建模模塊執(zhí)行對碼塊的每個非零位平面進行多通道編碼,產生相應被編碼樣本的上下文環(huán)境和決策數據對。在對每個位平面的編碼包含3個編碼通道:重要性傳播編碼通道、幅度細化編碼通道和清除編碼通道。上下文環(huán)境建模包含4個編碼原語:零編碼原語、符號編碼原語、幅度細化編碼原語和游程編碼原語。重要性傳播編碼通道執(zhí)行零編碼原語,如果被編碼樣本的幅度值為1,緊接著還將執(zhí)行符號編碼原語完成對該系數的符號編碼。幅度細化編碼通道執(zhí)行幅度細化編碼原語。清除編碼通道執(zhí)行零編碼原語,如果被編碼樣本的幅度值為1,緊接著也將執(zhí)行符號編碼原語完成對該系數的符號編碼。在清除編碼通道,如果連續(xù)4個樣本處在同一條帶列,且4個樣本的8鄰域重要性貢獻都為0,滿足游程編碼的條件時,將啟動游程編碼原語。游程編碼結束后,將繼續(xù)采用零編碼原語和符號編碼原語進行剩余樣本的上下文環(huán)境建模,直到再次檢測到游程編碼的條件滿足。3.3位平面解碼過程在一個編碼子塊中每個系數有一個關聯(lián)的二進制狀態(tài)變量,即稱為系數的重要性狀態(tài)。重要性狀態(tài)初始化為0,表示系數不重要,并且可能在對編碼子塊編碼過程中變?yōu)?,表示系數重要。一個給定的當前系數的上下文矢量是一個由它的8個最近的鄰點重要性狀態(tài)組成的二進制矢量。在對一個當前系數的位編碼時,任何處于當前系數的編碼子塊外面的最鄰近點被認為是不重要的,即它被當作有一個值為零的重要性狀態(tài)。一般地,當前一個系數可以有256種可能的上下文矢量。這些矢量根據以下的上下文信息規(guī)則被分成數目不多的幾個組。這里定義了4條上下文信息規(guī)則,每條針對4種編碼操作之一:重要性編碼,符號編碼,幅度細化編碼以及清除編碼。這些編碼操作在每個位平面上分三個編碼通道執(zhí)行:重要性和符號編碼位于重要性傳播通道,幅度細化編碼位于幅度細化通道,而清除和符號編碼位于清除通道。對于一個給定的編碼操作,提供給算術編碼引擎的上下文標號是一個賦于當前系數的上下文的一個標號。從最高有效位開始的、不含任何重要系數(即僅含不重要比特的位平面?zhèn)€數在數據包頭中指明。第一個帶有一個非零元素的比特面只有一個清除通道。剩下的位平面在三個通道中進行編碼。一個系數比特在哪一個通道中編碼取決于該通道的條件。一般地,重要性傳播通道包含那些被預測為、或者“極有可能”變?yōu)橹匾南禂?以及他們的符號。幅度細化通道包含已經成為重要系數的比特。清除通道則包含所有剩余的系數。當前系數(如圖3.2的8個最鄰近的系數用于產生9個上下文區(qū)域,依據是其中有多少個系數和哪些系數為重要系數。如果一個系數是重要的,則在產生上下文時賦于1,反之為0。上下文的映射也依賴于(在給定小波分解級上編碼子塊位于哪個子帶。表3.1為這些上下文。重要性傳播通道僅包含那些不重要系數(即他們的最高有效比特尚未遇到的比特,但其上下文非零。所有其他系數被跳過。上下文與比特流一起被傳送到算術解碼器,解碼系數比特被返回。如果該比特值為1,則重要性狀態(tài)被設置為1,而且緊接著的下一個被解碼比特是該系數的符號比特。否則,重要性狀態(tài)保持為0。當考慮連續(xù)的系數和編碼通道的上下文時,系數最近的重要性狀態(tài)則被使用。表3.1重要性編碼通道和清除通道的上下文LLandLHsubbandHLsubbandHHsubbandContextLableiH∑iV∑iD∑iH∑iV∑iD∑(iiDV+∑iD∑2xxx2xx≥381≥1x≥11x≥12710≥101≥1026100010≥21502x20x11401x10x01300≥200≥2≥202001001101000000正負符號位解碼的上下文標志使用另外一種鄰點的上下文來決定。上下文標志的計算可以看作一個兩步驟的處理。第一步是總結垂直和水平鄰點的貢獻,第二步是把這些貢獻減少到5種上下文標號中的一種。在第一步,兩個垂直的鄰點被一起考慮。每個鄰點可能有三種狀態(tài)之一:重要的正數,重要的負數,或不重要。如果這兩個垂直鄰點都是重要的,且符號相同,或者只有一個是重要的,則垂直方向的貢獻為1(符號為正或-1(符號為負。表3.2垂直(和水平方向鄰點對符號上下文的貢獻0V(或0H1V(或1HV(或H的貢獻重要,正重要,正1重要,負重要,正0不重要重要,正1重要,正重要,負0重要,負重要,負-1不重要重要,負-1重要,正不重要1重要,負不重要-1不重要不重要如果兩個垂直鄰點均為不重要的,或者他們雖然都是重要的但符號相反,則垂直方向的貢獻為0。水平方向的貢獻也類似計算。再者,如果鄰點落在編碼子塊的外面,則他們就被認為的不重要的。表3.2列出了這些貢獻。第二步將垂直和水平貢獻的9種排列減少到5種上下文標號。表3.3顯示了這些上下文的標號。這些上下文隨著比特流提供給算術解碼器。解碼器返回的比特再與表3.3中的XORbit進行邏輯異或運算,由此得到符號比特。該過程由以下等式表示:(SignbitACcontextlabelXORbit=⊕(3.1式中,Signbit是當前系數的符號位(1表示系數為負,0表示系數為正。(ACcontextlabel是在給定上下文標號和比特流時,算術解碼器的返回值。當前上下文標號對應的XORbit參見表3.3。表3.3垂直和水平方向貢獻產生的符號上下文水平方向貢獻垂直方向貢獻上下文標號XORbit11130101201-11100110000900-1101-11111-10121-1-1131幅度細化通道包含已經成為重要系數的比特,但要除去剛好在此之前的那個重要性傳播通道后才被確定的重要比特。使用的上下文由水平、垂直以及對角鄰點重要性狀態(tài)之和決定。這些是解碼器當前已知的狀態(tài),而不是在重要性解碼通過之前使用的狀態(tài)。而且,上下文依賴于當前是否是第一個細化比特(即緊接著重要性和符號比特。表3.4為細化通道的三種上下文區(qū)域。表3.4幅值細化的編碼規(guī)則iiiHVD++∑∑∑是當前系數第一次細化上下文標號任意否16≥1是150是14所有剩余的系數是不重要的,而且他們的上下文值在重要性傳播通過期間為零。這些系數的編碼都在清除通道。該通道不僅使用鄰點之間的上下文,例如在重要性傳播通道中表3.1的上下文,而且也使用一個游程長度上下文。首先,在此通道的系數鄰點的上下文由表3.1重新計算。注意到上下文標號現在可以有任何值,因為在重要性傳播通道中被發(fā)現為重要的系數在清除通道被認為是重要的。游程長度被用唯一的單上下文解碼。如果編碼掃描時一列中的4個連續(xù)系數都在此清除通道編碼,而且所有的上下文標號為0(包括前一個幅度重要性和清除通道的上下文系數,那么該唯一的游程長度上下文將與比特流一起供給算術解碼器。如果符號0被返回,則該列所有4個連續(xù)系數仍然為不重要。此外,如果符號1被返回,則該列中至少有4個連續(xù)系數中的一個為重要的。接著2比特由UNIFORM上下文返回,他們注明該列中從上到下哪一個系數被首先發(fā)現是重要的。這兩個用UNIFORM上下文解碼的比特先是MSB,然后是LSB。該系數的符號位的確定如3.2節(jié)描述。對所有剩下的系數的解碼如3.2節(jié)的方式繼續(xù)。如果一列中的4個連續(xù)系數不全在清除通道中解碼。注意到這里使用與重要性傳播時同樣的上下文(狀態(tài)和模型被使用。表3.5為清除通道的邏輯。表3.5清除通道的游程長度解碼器一列中4個連續(xù)系數仍然待解碼,并且各系數當前上下文值為0帶有游程長度上下文的符號4個待解碼的連續(xù)比特為用UNIFORM上下文解碼的符號待解碼的系數個數是0是無無是1否跳至第一個系數符號跳至第一個系數符號跳至第一個系數符號跳至第一個系數符號MSBLSB00011011321否無任意無剩下的列如果一個編碼子塊的剩余行少于4行,則不使用游程長度編碼。需要重申的是,任何系數的重要性狀態(tài)在解碼第一個“1”量值比特后立即改變。表3.6是一個例子,顯示了在掃描中一個4個采樣的列的量化系數的編碼次序。該例子中假定沒有被包括在表中的所有鄰點同為0,而且指出每個比特在哪一個通道被編碼子塊中最早的通道總是一個清除通道,因為它可能沒有被預測成重要的或細化的比特。在第一次通過后,第一個系數的解碼出的“1”比特將引用起第二個系數在下一個比特面的重要性通道中編碼。而在第二次清除通道中的最后一個系數的編碼的“1”比特將引起第三個系數在下一個重要性通道中被編碼。表3.6子位平面編碼次序好重要性傳播示例系數值編碼通道1013-7清除1+00000重要性幅度細化清除01-01+11重要性幅度細化清除1+011重要性幅度細化清除當上下文被初始化或重新初始化時,其值設置為表3.7的值。在每一個編碼通道結束時或者僅在每個編碼子塊結束時,上下文被重新初始化。標記COD和COC指示上下文被重新初始化的位置。表3.7所有上下文的初始狀態(tài)上下文初始下標MPSUNIFORM460游程長度30全0鄰點40其它所有上下文00表3.8算術編碼器的終止模式示例編號通道編碼運算僅在最后的通道終止編碼通道在每個通道終止1清除AC(算術編碼器AC,終止2重要性傳播ACAC,終止2幅度細化ACAC,終止2清除ACAC,終止…………最后重要性傳播ACAC,終止最后幅度細化ACAC,終止最后清除AC,終止AC,終止在正常運算時(即不是選擇性算術編碼通過,算術編碼器必須或者終止在每個編碼通道的結尾,或者僅僅終止在每個編碼子塊的結尾處。表3.8顯示了在一個編碼子塊中編碼通道的兩個終止模式的例子。其中用到了COD或COC標記,他們指示所用的終止模式。當算術編碼器提供了多重終止時,每個被終止的字段的長度在數據包頭中指示。對于解碼器而言,給定字節(jié)的碼流將在算術編碼器終止之前解碼出給定次數的編碼通道。在解碼時,數據按字節(jié)從碼流連續(xù)取出直到該編碼通道的所有字節(jié)被解碼使用完畢。編碼通道中對應的字節(jié)數在數據包頭規(guī)定。通常編碼通道中有許多符號待解碼。因此,解碼器必須根據需要用0xFF字節(jié)把輸入比特流擴展到算術編碼器,直到所有符號被解碼。實際添加兩個以內0xFF字節(jié)就足夠了。這將使得算術編碼器在其輸入有至少一對連續(xù)的0xFF字節(jié),他們被解釋成一個碼流結束標記。比特流中實際上不含一個終止標記。然而,字節(jié)長度被顯示指示,由此可以為算術編碼器合成一個終止標記。3.4位平面解碼器的硬件設計本節(jié)中我們將介紹BPD的基本架構,相關的實驗結果將用于與本文后面提出的架構做比較。該基本架構學習了一些已有的架構[29-32]并做了一些關鍵修改:(1在文獻[33]中提到的適應性JPEG200解碼器中,BPD有正常和因果兩種工作模式。(2該結構是基于改進的樣本跳躍算法基礎上的。(3在該結構中每個位置只需要用到兩個狀態(tài)位。圖3.3樣條s列c中每個取樣位置的處理過程以及相應上下文窗口這個架構是基于條帶-列處理進程的。一個條帶列的上下文窗口中所有位置的狀態(tài)、數據、符號位信息如圖3.3所示。一個高有效的啟動信號load會在每次樣條-列處理進程結束時產生,以裝載下一個列。假定樣條s列c為當前解碼列,一個高有效啟動信號load將列c-1寫入存儲器單元。與此同時對列寄存器左移三位,將一個新列從存儲器單元中寫入到列c+1。如圖3.4所示為基本BPD算法的VLSI實現。在每個時鐘周期里,更新位單元(UpdateBit依據當前解碼位置(locp、上下文類型(typec、該樣條-列當前產生的上下文總數(gentcx以及判決位(dbit等信息更新樣條-列c的當前數據和符號位。已更新的數據位和狀態(tài)位傳遞到通道選擇單元(flagsPGeneration產生通道選擇標志flagsP。采樣跳過生成單元(Sample-skippingGeneration負責處理flagsP、locp、typec和gentcx信息以產生下一組locp、typec和load信號。上下文生成單元(ContextGeneration根據上下文類型、狀態(tài)位、數據和符號位產生上下文。圖3.4基本BPD算法的VLSI實現采樣跳過算法要求在產生樣條-列最后一個上下文的同時產生load信號。但是在BPD算法中存在一些困難,因為判決位dbit只能在兩個時鐘周期后到達(現有算術解碼器解碼一個dbit通常需要2~3個時鐘周期。為此在BPD算法中我們引入一種改進的采樣跳過策略,即在沒有更多的位置需要解碼時才產生load信號。舉例說明,如圖3所示樣條-列c處于SP通道中,假定位置A和B都已經成為重要位。由圖3.5的時序圖中可知,位置0的1typec在第k個時鐘周期產生,在第k+1個時鐘周期里BPD處于停止狀態(tài),等待AD產生dbit。假設dbit=0,在第k+2個時鐘周期內BPD為位置1產生一個上下文。這個時候即便樣條-列c的最后一個上下文已經產生也并不產生load信號。在下一個時鐘周期里(k+3,BPD等待AD產生dbit。在第k+4個時鐘周期里,僅當dbit為0時load信號被置高,否則解碼繼續(xù)。需要說明的是該架構是與文獻8中提到的AD級聯(lián),而且假定AD只有一個解碼延遲周期。01stallstall00110stallstallstall01160stallplocctypeloaddbit圖3.5改進的采樣跳過策略時序圖通過分析位平面解碼算法,我們知道BPD存在兩種可能的狀態(tài):依賴(statep=1和獨立(statep=0。當處于依賴的狀態(tài)時,下一個上下文的產生取決于當前上下文的dbit值。如表3.9所示typec的轉換方式取決于已產生的dbit值。對于1typec和3typec,下一個typec取決于dbit,當dbit=1時,他們分別轉換成4typec和6typec;而當dbit=0時,對于3typec則產生load信號,對于1typec則有兩種可能:如果有更多的位置需要解碼時下一個typec為1typec,否則將產生load信號。當處于獨立的狀態(tài)時(2,4,5,6時,下一個typec與相應的dbit值無關。對于每個轉換都有一個對應已知的下一狀態(tài),或者產生load信號(僅對于2typec和6typec,且當前樣條-列的所有上下文都已經產生時。在基本BPD架構中,無論一個樣條-列是否處于依賴狀態(tài)都需要一個額外的時鐘周期。為了避免這個額外的時鐘周期,我們引入一種選擇性采樣跳過算法(SelectiveSample-Skipping。表3.9取決于解碼判決位dbit的上下文類型轉換方式State(PstateNextContext-typePresentContext-typedbit=0dbit=1111/load6202/load31load4405506601/load圖3.6用于改進算法的4*6位寄存器在選擇性采樣跳過策略中,我們用一個4*6位寄存器去存儲4列的狀態(tài)、符號、數據位信息。如圖3.6所示這些寄存器用于當前樣條-列c(set0以及下一個樣條-列c+1(set1的上下文窗口的狀態(tài)、符號和數據的存取。我們用dp信號來表示BPD當前處于依賴狀態(tài)而且可能正在處理當前樣條-列的最后一個上下文(1lastcx=。dp用于當前上下文窗口set0到下一個上下文窗口set1的轉換過程中,具體依據如下:(lastgencpcxtcxt===(4.2(1&dstatelastppcx===(4.3其中cpt表示在當前樣條-列中出現的所有上下文總數,并且在解碼過程的每個時鐘周期更新。dp將被存儲并用于當dbit可用時在下一個時鐘周期推動上下文轉變。如果dp=1,當dbit=1時BPD選擇set0,否則選擇set1。如果選擇set1,load信號將在讀入一個新列c+3時或樣條-列c在當前通道中不在產生上下文時被觸發(fā)。這種策略可以很有效的避免額外的時鐘周期需求。在處于獨立狀態(tài)時(statep=0,是否改變上下文取決于當前typec(表3.9,如果當前以產生的上下文為該樣條-列的最后一個上下文,則load信號將被觸發(fā)以載入下一個列。圖3.7基于SelectiveSample-Skipping策略的BPD結構框圖如圖3.7所示為基于SelectiveSample-Skipping策略的BPD結構框圖,更新位單元(UpdateBit根據load值、上下文窗口的選擇、typec和locp來接收dbit數據和更新樣條-列c-1或者c的數據和符號位。窗口選擇單元(ChooseSet根據dp和dbit值選擇寄存器組中的一個窗口并更新set信號。選擇性采樣跳過生成單元(SelectiveSample-SkippingGeneration負責生成新的dp、typec、locp和load信號以及更新符號位、數據和狀態(tài)值。將該BPD架構與文獻[33]中提出的低延遲AD級聯(lián),則可以避免BPD在解碼過程中處于停止等待狀態(tài)。上節(jié)提到的級聯(lián)方式有助于避免依賴狀態(tài)下的BPD處于停止狀態(tài),與此同時AD中dbit生成路徑上的延遲也會增加BPD的關鍵路徑延遲。為了減小關鍵路徑延遲我們引入推測處理方式(speculativeprocess,即根據dbit的兩種可能值進行兩種操作。如圖3.8中所示為基于推測處理的BPD結構框圖。圖3.8基于SpeculativeProcess的BPD結構框圖通過分析整個解碼架構的關鍵路徑,我們需要將推測處理一直進行到選擇性采樣跳過生成單元。這樣的推測方式可以嚴格控制BPD的關鍵路徑,使其接近于最小額外消耗下AD的關鍵路徑。而整個塊解碼器的關鍵路徑取決于BPD的模式,這點與前面提到的基于選擇性采樣跳過策略的結構恰恰相反。3.5實驗結果分析我們采用Altera公司的CyloneII系列FPGA作為硬件實現平臺,對基本架構和改進架構下的BPD的硬件消耗和性能做了分析和比較。表3.10中列舉了3種架構下的硬件消耗和工作頻率,其中基本架構下的BPD工作頻率最高,這是因為改進算法需要為上下文窗口選擇器增加額外的邏輯單元。推測模式下的BPD相對與選擇性采樣跳過策略的BPD在工作頻率上有更多優(yōu)勢,這是因為它的關鍵路徑中不包含dbit邏輯。表3.10三種結構的性能比較硬件消耗(ofLogicCells架構位平面解碼器(BPD算術解碼器(AD工作頻率(MHz基本(Baseline654162454.6選擇性跳過(Selective820196032.3推測方式(Speculative980200446.53.6小結本節(jié)中我們介紹了位平面解碼器的基本原理,并采用了一種基于選擇性采樣跳過策略的BPD架構,該結構可以增加整個塊解碼器的吞吐量。然后又在上述架構基礎上引入推測處理方式,這樣就可以大大減小關鍵路徑的延遲。相對于現有方法的基本BPD架構,改進的算法可以將吞吐量提高50%-100%,同時只增加25%-30%的硬件消耗。第4章MQ算術解碼器研究與硬件設計4.1研究現狀在JPEG2000標準的嵌入式塊編碼模塊部分,采用了一種自適應二元算術編碼算法,MQ編碼器,來實現對原始數據的熵編碼。在JPEG2000標準,MQ編碼器用來讀入位于前端的位平面編碼模塊產生的子塊系數位樣本的上下文環(huán)境標簽和數據對,經過編碼得到每個獨立子塊系數的數據壓縮的碼流。MQ算術編碼具有很好的壓縮性能,但同時其算法也要復雜很多,軟件的處理速度己經遠遠不夠,MQ算術編解碼器的高速硬件實現已經成為一種必然。在基于FPGA的MQ算術解碼器的VLSI實現方面,文獻[34]提出了一種動態(tài)流水線結構,并使用RAM_I和ROM_Qe來實現動態(tài)的概率估計;文獻[35]在解碼器部分對解碼算法進行了一些優(yōu)化,并采用資源復用技術,將編解碼器合并,大大提高了資源利用率;文獻[36]中修改了基于概率估計的狀態(tài)機方法,能最大幅度的消減解碼器延遲。本文對MQ解碼算法進行了進一步深入研究和總結,并對優(yōu)化后的算法分模塊實現,最后提出一種基于4級流水線的MQ算術解碼器結構,該結構在利用有限資源的情況下可以大幅度提高MQ算術解碼器的速度,基本能滿足JPEG2000系統(tǒng)的要求。4.2MQ算術編解碼原理20世紀60年代Elias為算術編碼奠定了理論基礎[37],在Elias編碼中,對于具有“0”或“1”值的二進制符號序列,以各自概率值比率將當前概率區(qū)間劃分成兩個子區(qū)間,被分配給實際產生符號的概率值區(qū)間下限值構成代碼串。即代碼串按二進制符號序列的輸入逐次被遞歸地修改下去。算術編碼將一串輸入碼流編碼成表示概率的小數,輸入碼流越長越復雜,概率區(qū)間劃分的越細,輸出也越長,大概率符號細化的較慢,小概率符號細化得較快,因此大概率符號越多,壓縮效果越明顯。MQ算術編碼的基本操作是遞歸劃分當前子區(qū)間。當編碼器接收到了一個新的待壓縮碼D及對應的上下文CX,根據D將當前子區(qū)間劃分成更小的2個子區(qū)間。子區(qū)間的下限值被更新,并且指向由待壓縮碼流所選定的新子區(qū)間的下邊界,子區(qū)間的間隔值也更新為新子區(qū)間的間隔。MQ編碼器用區(qū)間寄存器A來記錄當前子區(qū)間的區(qū)間長度,用寄存器C來記錄當前子區(qū)間的下限值。MQ編碼過程的當前區(qū)間可以表示為[C,C+A]。隨著編碼次數的增加,這一子區(qū)間的精度會不斷提高,意味著C和A的有效位數不斷增加。由于實際可操作的寄存器位數是有限的,因此引入區(qū)間重歸一化的概念,即當滿足一定條件時,將C和A進行左移操作,同時將C寄存器不再變化的高位送入存儲區(qū)。在充分考慮進位的影響后將該字節(jié)輸出,這就是輸出的壓縮碼流CD。對于MQ編碼器來說,進行區(qū)間重整的條件是A<0.75,當該條件滿足時,將C和A都乘以2(左移1位,直到0.75≤A<1.5。MQ解碼過程與編碼很類似,根據輸入的壓縮碼流CD及對應的上下文CX判斷當前碼流屬于大概率區(qū)間還是小概率區(qū)間,一邊逐個地對二進制判決解碼,同時從編碼器生成的壓縮數據中去掉已完成解碼的代碼字節(jié)。其結構圖如圖4.1所示。圖4.1MQ算術解碼器圖4.2MQ算術解碼器流程4.3算術解碼過程圖4.2為MQ編碼的解碼器流程。解碼器的初始化由INTDEC完成。所有的CX和所需的壓縮數據字節(jié)被讀入DECODE。DECODE子程序解碼二進制判決D,返回一個0或1的值。概率估計過程內置在DECODE中,它提供了對每個上下文概率的自適應估計。當所有上下文被讀入處理后(即圖中的“已完成?”判決為真時,壓縮數據被解碼完畢。本節(jié)的解碼流程圖所假設的解碼器寄存器結構如表4.1。Chigh和Clow可以被認為是一個32比特的C寄存器,因為對C重新歸一化將新數據的一個比特從Clow的MSB移位到Chigh的LSB。但是,解碼比較只用Chigh。新數據被一次1字節(jié)地插入Clow的“b”比特處。表4.1解碼器寄存器結構MSBLSB寄存器Chighxxxxxxxxxxxxxxxx寄存器Clowbbbbbbbb00000000寄存器Aaaaaaaaaaaaaaaaa對于帶有填充比特的數據處理的詳細描述將在本節(jié)的后面部分給出。注意到本節(jié)中假定了所示的各種過程中的比較精度大于16比特。用16比特精度可以使用邏輯比較。解碼器一次解碼一個二進制判決。解出該判決后,解碼器從壓縮數據中減去由編碼器加入的任何數值。留在壓縮數據中的數值是從當前區(qū)間的基到一個子區(qū)間的偏移。該子區(qū)間是分配給所有尚未被解碼的二進制判決。在DECODE過程(如圖4.2進行的第一次檢測中,Chigh寄存器與LPS子區(qū)間的尺寸進行比較。只要不需要進行條件交換,這一檢測決定是否有一個MPS或LPS被解碼。如果Chigh邏輯上大于或等于存貯在CX的當前下標I的LPS概率估計值Qe,那么Chigh將被減去這一數值。如果A不小于0x8000,存貯在CX的MPS的意義被用于設置被解碼的判決D。當需要一次重新歸一化時,MPS/LPS的條件交換可能發(fā)生。MPS路徑的條件交換過程如圖4.3。只要圖中第一步計算的MPS子區(qū)間尺寸A邏輯上不小于LPS的概率估計值Qe(I(CX,則出現一個MPS,判決可以從MPS(CX設置。然后,下標I(CX從表中的下一個MPS下標欄(NMPS更新。但是如果LPS子區(qū)間較大,條件交換發(fā)生,而且出現一個LPS。如果SWITCH欄為1,概率刷新切換MPS的意義,并且根據表4.2中下一個LPS下標欄(NLPS更新下標I(CX。注意到解碼器中的概率估計需要與解碼器中的概率估計完全相同。圖4.3解碼器MPS路徑的條件交換過程表4.2Qe概率估值表NLPSSWITCHIndexQeNMPS00x560111110x340126020x180139030x0AC1412040x0521529050x05213833060x560176170x5401814080x4801914090x380110140100x300111170110x240112180120x1C0113200130x160129210140x560115141150x540116140160x510117150170x480118160180x380119170190x340120180200x300121190210x280122190220x240123200230x220124210240x1C0125220250x180126230260x160127240270x140128250280x120129260290x110130270300x0AC131280310x09C132290320x08A133300330x052134310340x044135320350x02A136320360x022137340370x014138350380x011139360390x008540370400x004941380410x002542390420x001543400430x000944410440x000545420450x000145430460x560146460解碼器LPS路徑的條件交換過程如圖4.4。同樣的MPS子區(qū)間A和LPS子區(qū)間Qe(I(CX的邏輯比較決定是否發(fā)生了條件交換。在圖中所有兩條路徑上,新的子區(qū)間A被設置為Qe(I(CX。在左邊和右邊的路徑上,分別對應條件交換發(fā)生時,對于MPS和LPS的判決和刷新處理。圖4.4解碼器LPS路徑的條件交換過程解碼器中的重新歸一化過程RENORMD如圖4.5。通過一個計數器跟蹤寄存器C的Clow分部的壓縮比特的數目。當CT為零時,一個新字節(jié)被BYTEIN過程插入Clow。所有子區(qū)間寄存器A和碼字寄存器C被一次1比特移位,直到A不再小于0x8000。圖4.5解碼器中的重新歸一化過程RENORMD調用的BYTEIN過程如圖4.6。該過程讀入1個字節(jié)的數據,同時補償處理中跟在0xFF后面的任何填充比特。它也檢測在編碼掃描結尾處或再同步區(qū)間必須出現的標記碼字。本過程中寄存器C是Chigh和Clow寄存器的級聯(lián)。圖中B為壓縮數據緩存指針BP指向的字節(jié)。如果B不為0xFF字節(jié)。BP加1,新的B值插入到Clow的高8位比特。圖4.6解碼器的BYTEIN過程如果B是0xFF字節(jié),那么B1(由BP+1指向的字節(jié)被檢測。如果B1超過0x8F,則B1必須是一個標記碼字。該碼字被根據需要解釋,而緩存指針仍然指向該標記碼字的0xFF前綴。這個標記碼字停止了算術壓縮數據。之后,若干“1”比特被一只填充到解碼器的解碼結束。圖中該過程由將寄存器C加0xFF00和設置比特計數器CT為8來顯示。如果B1不是一個標記碼字,則BP加1,指向包含一個填充比特的下一個字節(jié)。B被加到寄存器C,其字節(jié)對準的條件是使填充比特(它包含任何進位比特被加到Chigh的低位比特。INITDEC過程用于啟動算術解碼器。圖4.7為其基本步驟。壓縮數據指針BP初始化為BPST,指向壓縮數據的第一個字節(jié)。壓縮數據第一個字節(jié)被移入Chigh的低位字節(jié),然后再讀入一個新字節(jié)。寄存器C然后移動7位,并將CT減7,使得寄存器C與A的起始值對齊。區(qū)間寄存器A設置為與編碼器中的起始值相匹配。圖4.7解碼器初始化解碼中某些時刻,一些或者所有的算術編碼統(tǒng)計參數被重新設置。它包括對某些或所有CX值,把I(CX和MPS(CX設置為零。在某些情況下,解碼器需要保存或恢復某些I(CX和MPS(CX的值。4.4MQ解碼器算法優(yōu)化與硬件實現在JPEG2000中,為達到更好的壓縮效果,MPS和LPS所對應的概率值是動態(tài)更新的,解碼器根據當前CX查索引表I得到I和當前MPS,然后再根據查Qe表得到的NLPS、NMPS和SWITCH,在下一個時鐘周期更新索引表I,以實現概率值動態(tài)更新。在硬件實現上本設計采用文獻[34]提出的用RAM來實現I表,與此同時,由于Qe表是一個具有47個不同狀態(tài)的狀態(tài)機,本設計采用有限狀態(tài)機來實現,其中索引值I為輸入變量,Qe的47個狀態(tài)加上一個Idle狀態(tài)構成狀態(tài)表。RAM_I與fsm_Qe相互配合可以在兩個時鐘周期內實現讀取I表和讀取Qe表的操作。該模塊的主要功能是實現MPS或LPS解碼,完成區(qū)間寄存器A和解碼寄存器C的更新。標準算法中的解碼區(qū)間更新分DECODE、MPS_EXCHANGE、LPSEXHCHANGE3個子流程,算法復雜,且是串行操作,效率很低;為提高處理速度,本設計對該算法流程進行了歸納總結,將該流程分成5種情況并行處理,流程圖如圖4.8所示。圖4.8解碼區(qū)間更新在解碼區(qū)間更新模塊完成一個D解碼同時產生一個更新信號I_update給RAM_I,配合當前NLPS、NMPS和SWITCH,在下一個時鐘周期更新索引表I,與此同時進行重新歸一化操作。對標準算法中重新歸一化進行進一步分析:每次完成一個D解碼,A都有兩種更新方式A=A-Qe或A=Qe;當A=A-Qe時,由于A≥0.75(0x8000,Qe的最大值是0x5601,則更新后A≥0x2901,要滿足0.75≤A<1.5,則A至多需要左移2位;當A=Qe時,由于只有在A<2Qe時才會出現這種情況,又因為A≥0.75(0x8000,所以Qe≥0x4000,更新后A≥0x4000,則A至多需要左移1位;而無論當前CT為何值A至少要左移一次,總結得到重新歸一化中對A的操作只有2種:左移一次或者兩次。根據文獻[36]所提到的前導零檢測方法,只需要檢測A[14]是否為零即可判斷A是左移一位還是兩位,具體流程圖如圖4.9所示。圖4.9重新歸一化字節(jié)讀入模塊在初始化和重新歸一化時調用,主要功能是讀入新的待解碼數據。為解決不同模塊之間數據處理速度不匹配的問題,本設計在字節(jié)讀入模塊中引入一個16*8的同步FIFO作為數據緩沖區(qū),并在字節(jié)讀入模塊中設定兩個8位寄存器B、B1作為緩存器,每次完成一次自己讀入都會從FIFO讀入一個字節(jié)更新B1,用之前的B1更新B。圖4.10字節(jié)輸入本文在歸納標準算法后,將BYTEIN分成3種情況[35],其中情況B=0xff&&B1>0x8f表明緩存器指針指向了終結算術解碼標記符,即完成該段壓縮數據CD的解碼工作。具體流程圖如圖4.10所示。解碼器在開始讀入數據解碼之前需要進行各個模塊的初始化,主要包括RAM_I的初始化,Qe表的初始化,解碼區(qū)間的初始化,字節(jié)讀入的初始化,本設計中通過引入reset_I,reset_Qe控制完成前面兩個的初始化,而解碼區(qū)間的初始化是在字節(jié)讀入初始化完成之后產生的A_init,C_init和reset_Interval控制完成的。由于位平面解碼器BPD和MQ解碼器并不能同步解碼,通常是BPD工作時MQ解碼器處于等待狀態(tài),MQ工作時BPD等待;另外,各個算術解碼階段所用的時間也不一樣,也有同時處于等待狀態(tài)的過程,如果有效的將這些等待時間利用起來,將大大提高解碼速度。當BPD傳遞的CX到來時,首先讀I表和Qe表,再進行MPS或LPS解碼,由于此時解碼數據已經得到,更新索引表I和重新歸一化可以并行處理,與此同時BPD可以開始下一次解碼CX,以此來實現流水操作,具體實現圖如圖4.11所示。update_I、圖4.114級流水線MQ解碼器結構4.5仿真及試驗結果該設計采用VerilogHDL對MQ解碼器進行了RTL級描述,采用Altera公司的CycloneII系列FPGA作為硬件平臺,并在QuartusII平臺下進行了設計、綜合,與此同時還進一步在Modelsim平臺下進行功能仿真,實驗結果與軟件仿真結果一致,且最高工作頻率可達37.64MHz。試驗結果表明,該設計可以大大提高MQ解碼器的運行效率,基本可以滿足JPEG2000實時解碼系統(tǒng)的需要。功能仿真結果如圖4.12所示,資源使用情況如表4.3所示。圖4.12功能仿真圖表4.3實驗結果工作頻率37.64MHz總邏輯單元數557個總組合函數551個專用邏輯寄存器123個總寄存器123個總引腳數27個總存儲單元位120位4.6小結本節(jié)分析了JPEG2000標準中MQ解碼器的算法流程,對其中幾個流程進行了相應的算法優(yōu)化,并提出了一種基于4級流水線的MQ算術解碼器結構,該結構可以在平均每兩個時鐘周期解碼一個D判決,該設計選取AlteraCycloneIIEP2C35F484C8系列FPGA進行實現,結果表明所占用的資源只有557LE,最高工作頻率可以達到37.64MHz,在利用有限資源的情況下可以大幅度提高MQ算術解碼器的速度,基本能滿足JPEG2000系統(tǒng)的要求。第5章總結與展望5.1.全文總結本文主要做了以下幾方面的工作:首先介紹了位平面解碼器的基本原理,并采用了一種基于選擇性采樣跳過策略的BPD架構,該結構可以增加整個塊解碼器的吞吐量。然后又在上述架構基礎上引入推測處理方式,這樣就可以大大減小關鍵路徑的延遲。相對于現有方法的基本BPD架構,改進的算法可以將吞吐量提高50%-100%,同時只增加25%-30%的硬件消耗。然后分析了JPEG2000標準中MQ解碼器的算法流程,對其中幾個流程進行了相應的算法優(yōu)化,并提出了一種基于4級流水線的MQ算術解碼器結構,該結構可以在平均每兩個時鐘周期解碼一個D判決。在QuartusII開發(fā)環(huán)境下對設計進行RTL級描述,用Modelsim進行了相應的功能仿真;針對Altera系列FPGACyclo