??? 摘 要: 在簡單介紹算術編碼" title="算術編碼">算術編碼和自適應算術編碼的基礎上，介紹了利用FPGA器件并通過VHDL語言描述實現自適應算術編碼的過程。整個編碼系統在ALTERA公司的MAX+plusⅡ軟件上進行了編譯仿真，測試結果表明：編碼器各個模塊的設計在速度和資源利用兩方面均達到了較優的狀態，可以滿足實時編碼的要求。
?? ?關鍵詞: 算術編碼? 自適應? FPGA? VHDL? 仿真
?
??? 算術編碼是一種無失真的編碼方法，能有效地壓縮信源冗余度，屬于熵編碼的一種。算術編碼的一個重要特點就是可以按分數比特逼近信源熵，突破了Haffman編碼每個符號只能按整數個比特逼近信源熵的限制。對信源進行算術編碼，往往需要兩個過程，第一個" title="第一個">第一個過程是建立信源概率表，第二個過程是對信源發出的符號序列進行掃描編碼。而自適應算術編碼在對符號序列進行掃描的過程中，可一次完成上述兩個過程，即根據恰當的概率估計模型和當前符號序列中各符號出現的頻率，自適應地調整各符號的概率估計值，同時完成編碼。盡管從編碼效率上看不如已知概率表的情況，但正是由于自適應算術編碼具有實時性好、靈活性高、適應性強等特點，在圖像壓縮、視頻圖像編碼等領域都得到了廣泛的應用。
??? 現場可編程門陣列（FPGA）是一種新興的可編程邏輯器件，具有更高的密度、更快的工作速度和更大的編程靈活性，被廣泛應用于各種電子類產品中。而硬件描述語言（HDL）是一種快速的電路設計工具，其功能涵蓋了電路描述、電路合成、電路仿真等的三大電路設計工作。VHDL是HDL的一種，因其簡單易懂而被廣泛使用。本文采用VHDL編程實現了自適應算術編碼，為算術編碼器的硬件實現提供了借鑒。
1 算術編碼的基本原理[1]
??? 實現算術編碼首先需要知道信源發出每個符號的概率大小，然后再掃描符號序列，依次分割相應的區間，最終得到符號序列所對應的碼字。整個編碼需要兩個過程，即概率模型建立過程和掃描編碼過程。
??? 算術編碼的基本原理是：根據信源可能發出的不同符號序列的概率，把[0，1]區間劃分為互不重疊的子區間，子區間的寬度恰好是各符號序列的概率。這樣，信源發出的不同符號序列將與各子區間一一對應，因此每個子區間內的任意一個實數都可以用來表示對應的符號序列，這個數就是該符號序列所對應的碼字。顯然，一串符號序列發生的概率越大，對應的子區間就越寬，要表達它所用的比特數就越少，因而相應的碼字就越短。
??? 圖1給出一個實現算術編碼的示例。要編碼的是一個來自四符號信源{A, B, C, D}的由五個符號組成的符號序列：ABBCD。假設已知各信源符號的概率分別為：P(A)=0.2，P(B)=0.4，P(C)=0.2，P(D)=0.2。編碼時，首先根據各個信源符號的概率將區間[0，1]分成四個子區間。符號A對應[0，0.2]，符號B對應[0.2，0.6]，符號C對應[0.6，0.8]，符號D對應[0.8，1.0]。符號序列中第一個符號是A，其對應的區間為[0，0.2]，接下來將這個區間擴展為整個高度，再根據各個信源符號的概率將這個新區間分成四段；第二個符號是B，它對應新的子區間的第二個子區間，即對應區間[0.04，0.12]；再將該區間擴展為整個高度，再根據各個信源符號的概率將這個新區間分成四段。繼續這個過程直到最后一個符號得到一個區間[0.08032，0.0816]，這樣該區間內的任何一個實數就可以表示整個符號序列，如0.081。
?
2 自適應算術編碼的基本原理
??? 自適應算術編碼在一次掃描中可完成兩個過程，即概率模型建立過程和掃描編碼過程。
??? 自適應算術編碼在掃描符號序列前并不知道各符號的統計概率，這時假定每個符號的概率相等，并平均分配區間[0，1]。然后在掃描符號序列的過程中不斷調整各個符號的概率。同樣假定要編碼的是一個來自四符號信源{A, B, C, D}的由五個符號組成的符號序列：ABBCD。編碼開始前首先將區間[0，1]等分為四個子區間，分別對應A，B，C，D四個符號。掃描符號序列，第一個符號是A，對應區間為[0，0.25]，然后改變各個符號的統計概率，符號A的概率為2/5，符號B的概率為1/5，符號C的概率為1/5，符號D的概率為1/5，再將區間[0，0.25]等分為五份，A占兩份，其余各占一份。接下來對第二個符號B進行編碼，對應的區間為[0.1，0.15]，再重復前面的" title="面的">面的概率調整和區間劃分過程。具體的概率調整見表1。
?
??? 隨著符號序列中符號個數的不斷增多，由自適應算術編碼器估計得到的各符號的概率將趨于各符號的真實概率。
3 自適應算術編碼的FPGA實現[2]
3．1 總體設計
??? 在利用FPGA實現自適應算術編碼的過程中，首先遇到的問題就是將浮點運算轉化為定點運算，即將[0，1]區間的一個小數映射為一個便于硬件實現的定點數。考慮到硬件實現的簡便性，本文中將[0，1]之間的浮點數與[0，256]之間的定點數對應。相應的對應關系如表2所示。
?
??? 編碼器在實現編碼的整個過程中按照耦合弱、聚合強的原則分為四個模塊：修改碼表、計算確定區間、并行編碼" title="并行編碼">并行編碼、串行輸出。四個模塊相對獨立，通過輸入、輸出信號使其構成一個整體。系統的頂層結構如圖2所示。
?
3．2? 碼表的設計及修改
??? 自適應算術編碼器可以在許多場合中得到應用。本文實現的自適應算術編碼器應用在采用6符號對小波變換系數進行零樹編碼的小波域視頻編碼中[3]，因此設計的碼表中含有六個符號。這樣根據自適應算術編碼的基本原理，將區間分成六個子區間，整個區間含有七個分割點。所以碼表可以用七個8位寄存器表示。初始時設定為等概率，這時七個寄存器可以順序地存儲0到6這七個數，即每個子區間的數值為1。隨著符號不斷地輸入，自適應地修改碼表，并且在修改碼表的過程中時刻要保持寄存器中的數值是遞增的。
??? 修改碼表時，首先判斷輸入符號，確定其所在區間，同時為后續模塊輸出該子區間的兩個端點值l_count和h_count以及碼表的最后一個端點值scale，然后進行碼表的修改：將當前符號所在區間之后的所有端點值都加1，即當前區間及后面所有子區間的h_count=h_count+1，這樣即完成了碼表的修改。在數值不斷累加過程中，寄存器中存儲的值將不斷增大。當碼表中最后一個寄存器中的數值為255時，需要對每一個寄存器中的值都取半，并同時對相鄰的兩個寄存器中的值進行比較，時刻保持數值是遞增的。這樣，處理前后的概率十分接近，對壓縮比影響不大。
??? 修改碼表模塊在輸出h_count、l_count和scale之后，后面的計算子區間的模塊即可進行計算；而修改碼表模塊在輸出h_count、l_count和scale之后，亦可進行碼表的修改。因此，這兩個操作可以采用并行處理的方法實現，極大地節省了所用的時鐘周期，相應地提高了速度，達到了優化的目的。表3給出了輸入符號為3（對應于寄存器2與寄存器3之間的區間）時碼表的修改過程。
?
?
3．3 區間計算及確定
??? 初始時符號所在的總區間為high=0xff，low=0（high和low分別表示已編碼的符號序列所在子區間的上下界）。隨著符號的不斷輸入，high和low的值也不斷地減小，用以表示輸入符號序列所對應的子區間。通過如下的公式可確定輸入符號的區間：
??? 
??? 計算時，最耗資源的是乘法器和除法器。本方案中乘法器采用參數化模塊lpm中的lpm_mult生成，而除法器則自行編寫。雖然占用的時鐘周期較多，但與使用lpm相比，這樣做可以大大地提高工作頻率，從總體上提高性能。
3．4 并行編碼
??? 在區間計算過程中，high和low總是有限值，不可能無限制地劃分下去。為了能夠實現連續的編碼，通過對high和low的處理，可以實現利用有限長的寄存器表示無限精度的區間，即在不斷修改high和low的過程中輸出high和low中相同的高端位，形成輸出碼流。詳細過程如下：
??? 在區間確定之后，將low和high按位比較，若首位" title="首位">首位相同，則輸出首位二進制碼，產生輸出碼流，同時把low和high左移，low末位補0，high末位補1。循環比較輸出，直到首位不同為止。如：
??? high?????=??? 00110110
??? low????? =??? 00100111
??? 輸出碼流為001，而high和low的結果為：
??? high???? =??? 10110111
??? low????? =??? 00111000
??? 通過這種連續地處理便可生成符號序列的自適應算術編碼結果。但隨著待編碼符號序列的不斷輸入，可能會出現high和low十分接近，并且high和low的首位沒有相同位的情況，如：
??? high???? =??? 10000000
??? low????? =??? 01111111??
??? 稱這種現象為產生了下溢。產生下溢后，后面的編碼都失去了意義，此時需要特殊處理。
??? 對于下溢的處理方法為：保留首位，同時刪除緊接在首位后的high中連續的0和low中連續的1，并且保證對high和low刪除的位數相同，若連續0和連續1的位數不同，則取其較小者；然后把high和low左移相同的位數，同時high的低位補1，low的低位補0。表4給出了下溢處理前后high和low值。
?
??? 經過處理后，擴大了區間，使得后面的編碼可以順利地進行。
??? 在考慮了下溢的編碼輸出中，下溢作為輸出碼流的一部分，使得解碼時能對下溢進行同樣的處理，達到編解碼的一致。但是下溢產生后并不馬上輸出，只記下下溢的個數，下溢則是在下一個符號編碼時進行輸出的。在下一個符號編碼時，如果high和low比較后高端有相同位則輸出下溢，即在第一個輸出位后緊接著插入首位的反，插入首位反的個數為前面產生下溢的個數，然后輸出相同的次高位及以后相同的各位。這樣處理既保留了下溢的信息又使得輸出碼流不偏離編碼符號所在的子區間，使得解碼時很容易處理。但是如果high和low比較后沒有相同位輸出則不輸出下溢，而是把兩次產生的下溢的個數進行累加，再輸入下一個符號，直到high和low有相同首位才輸出下溢。
??? 例如：在一個符號編碼計算后得到的high=11010010和low=11001101，而前一個符號編碼產生的下溢為1個，比較后輸出為1010，同時記錄下產生的下溢2個，如表5所示。
?
3．5 串行輸出
??? 并行編碼后產生的碼流存儲在并行數據中，但在大多的情況下只有兩、三個輸出，甚至沒有輸出，若采用并行輸出，就會產生極大的浪費。為了充分利用資源，在并行編碼之后進行并/串轉換，使其一位一位地輸出，并且這個輸出過程與下一個符號編碼的過程并行完成，因此并不占用多余的時鐘周期。
??? 在編碼過程中，當一個符號編碼結束后，觸發reload信號，通知此次編碼結束，進行下一次編碼，讀取輸入的符號。同時需判斷輸入是否合法，如果是合法的輸入，就進行編碼；否則停止編碼，處于等待狀態，直到復位信號rst置1，重新初始化、編碼。
4 仿真結果
??? 本文算法采用VHDL硬件描述語言實現，并在ALTERA公司的MAX+plusⅡ軟件上編譯仿真。設計采用全局同步時鐘，避免了毛刺的產生，保證了信號的穩定性。編碼的仿真結果如圖3所示。
?
??? 其中，rst、clk、c為輸入信號，rst為模塊中各寄存器的初始化信號，clk為時鐘同步信號，而c則為輸入的編碼信號；out_flag、out_bit、reload、end_code為輸出信號，out_flag和out_bit分別為輸出標志位和輸出位（若out_falg=1，則此時out_bit為有效輸出；否則out_bit輸出無效），reload為一個符號編碼結束）下一個符號輸入的標志位，end_code為編碼結束的標志（若end_code=0，則繼續編碼，否則編碼結束）。
??? 在進行性能仿真時[4]，采用的器件是FLEX1K系列的EP1K30TC144-1器件，其最大工作頻率為40MHz，消耗1533個LC，平均編碼時間為20個時鐘周期。一個符號的編碼時間不到500ns，對于QCIF格式的圖像完全可以滿足每秒鐘實時編碼30幀圖像的要求。
??? 自適應算術編碼是一種效率很高的無失真編碼，本文通過VHDL語言實現了自適應的算術編碼，在編碼過程中，根據硬件結構的特點，充分利用其并行特性。通過并行執行，實現了速度的優化。由于滿足每秒鐘編碼30幀圖像的要求，因此可以應用于視頻圖像的實時編碼中。
參考文獻
1 Mark Nelson. Arithmetic Coding +?Statistical Modeling = Data Compression.Dr.Dobb’s Journal，February 1991
2?Uwe Meyer-baese著，劉 凌,胡永生譯. 數字信號處理的FPGA實現. 北京：清華大學出版社, 2003
3 Arturo San Emeterio Campos. http://www.arturocampos.com/ac_arithmetic.html， 1999
4 潘 松,黃繼業.EDA技術實用教程.北京：科學出版社,2002