0 引 言
    近年來，隨著信息技術飛速發(fā)展和互聯(lián)網(wǎng)的日益普及，尤其是以視頻為信息主要來源的多媒體領域越來越受到人們的關注。H．264是ITU-T的視頻編碼專家組(VCEG)和ISO／IEC的活動圖像編碼專家組(MPEG)的聯(lián)合視頻組(Joint Video Tearn，JVT)開發(fā)的一個新的數(shù)字視頻編碼標準，它既是ITU-T的H．264，又是ISO／IEC的MPEG-4的一部分。H．264和以前的標準一樣，也是DPCM加變換編碼的混合編碼模式。H．264標準可分為三檔：基本檔次(其簡單版本，應用面廣)；主要檔次(采用了多項提高圖像質(zhì)量和增加壓縮比的技術措施，可用于SDTV、HDTV和DVD等)；擴展檔次(可用于各種網(wǎng)絡的視頻流傳輸)。
    H．264／AVC的編解碼框架的基本結構與早期的編碼標準(H．263、MPEG4等)相似，都是由運動估計、變換、量化、熵編碼、環(huán)路去塊效應濾波器等功能單元組成的。H．264視頻編碼框架的主要變化包括：引入了環(huán)內(nèi)去塊效應濾波器，去塊效應處理后的宏塊被保存在內(nèi)存中用于對后續(xù)宏塊的預側；采用了多參考幀運動估計，需要在內(nèi)存中保留多個參考視頻幀；引入了幀內(nèi)預測機制，可以通過同一幀內(nèi)的宏塊進行預測；采用了新的整型變換方式，取代了以前的離散余弦變換(DCT)；H．264與以前視頻標準在運動估計的模式上也有了較大的變化，H．264支持7種模式的可變塊運動估計。此外，在熵編碼中還引入了上下文自適應的變長編碼(CAVLC)和二進制算術編碼(CABAC)。
    在熵編碼方面，H．264使用了CABAC和CAVLC兩種不同的編碼方式。CABAC熵編碼是一種基于區(qū)間劃分的算術編碼方式。這種編碼方式的效率很高，接近信息熵值，但算法相對復雜，編解碼速度較慢。CAVLC是一種可變長編碼，它根據(jù)已編碼語法元素的情況動態(tài)調(diào)整編碼中使用的碼表，在編碼過程中有些語法元素是組合編碼的，當對這些元素進行查找時就會耗費很長的時間。因此對CAVLC的優(yōu)化顯得格外重要。

1 原碼表查找算法
    原碼表的存儲結構為二維表結構。存儲的內(nèi)容為碼字，二維坐標分別代表解碼后的兩個語法元素。對于二維表結構。若通過坐標查找內(nèi)容是很容易的；而通過內(nèi)容查找坐標，就需要對整個表進行遍歷。JM中的碼表查找算法就是通過遍歷整個碼表實現(xiàn)的，步驟如下：
    (1)取碼表的中的一個碼字；
    (2)根據(jù)碼字長度從碼流中取出相應長度的bit；
    (3)比較此碼字和bit串，若相同則查找成功，否則若碼表中還有碼字，回步驟(1)，否則查找失敗。

2 算法的優(yōu)化分析
2．1 基于前綴零分組子表搜索算法
    基于上下文自適應的變長編碼的解碼算法需要不斷的讀取碼流，判斷，直到在碼表中找到該碼字，如此反復，直至解碼整個塊。由此可見該過程的時間空間復雜度都是相當高的。由于變長碼為霍夫曼前綴碼，所以可以根據(jù)碼表的特性，按照碼字長度將原來的一個碼表，按照碼字長度對原碼表進行分割，以Coeff_token碼表為例，原碼表如表1所示，表中NC=-1。

    在參考模型中，搜索碼表算法過程如下：
    (1)從最短碼長開始，讀出該長度二進制數(shù)據(jù)流對應的碼字；
    (2)遍歷碼表，如找到該碼字進行步驟(4)，否則進入(3)；
    (3)碼字長度加1，重定位指針位置，重復步驟(2)；
    (4)讀取該碼字對應值，更新指針位置。
    從上面過程中不難發(fā)現(xiàn)，碼字長度的不確定性使得在讀取字節(jié)流時只能一次次的試探，導致了效率的下降。如果可以將變長碼的讀取采取固定的策略，一次讀取固定的長度，之后再做判斷，再讀取一定長度，這樣將判斷的次數(shù)也固定，從理論上可以降低不斷搜索和重定位指針帶來的時間和空間復雜性。利用可以利用碼表中碼字前綴零數(shù)目的不同，將表1拆分為兩個子表，如表2，表3所示NC為-1。

    改進后的碼表搜索算法如下：
    (1)讀取最大碼字長度的二進制流；
    (2)根據(jù)不同的前綴零位數(shù)、右移位、判零以確定碼字所在子表；
    (3)直接根據(jù)碼值讀取對應值，更新指針位置。
    新的搜索過程不但避免了不確定性，而且無需遍歷碼表，這樣可以在一定程度上提高變長解碼的效率。

    按照改進的算法步驟，解碼時，首先從字節(jié)流中讀取8位碼字，由于前綴零個數(shù)分為大于3和小于3的兩種情形，所以右移5位，若為零，則查找表2，否則查找表1，根據(jù)碼值直接解碼出±1個數(shù)，非零系數(shù)數(shù)目。此外在設計代碼時，還可利用二叉搜索樹的特性，設計搜索過程，提高解碼效率。
2．2 二叉樹一子表混合法
    拆分成子表后建立的數(shù)組中存在冗余現(xiàn)象。如當0≤N<2且Pre-Zeros<6時，一共有13個碼字。為了保留原先的查表方式以TC和Tls為矩陣下標的特點，必須要用4×7矩陣，多余位置零。由于實際搜索的對象是矩陣，怎么確定Pre-Zeros值，以保證在分塊數(shù)一定的情況下，使用的矩陣較小，成為提高搜索效率的關鍵。從表中可以看到，對不同的N值對應的列，子表之間的Pre-zeros的分界點選取了不同的閾值。按照表2中的分塊方法，矩陣的平均大小為4×6．5。相比JM中使用一個4×17矩陣，搜索效率理論上可以提高(17-6．5)／6．5=1．615倍(假設每張子表的使用概率相同)。以0≤N<2的一張VLC表為例，共分成4張子表。從查找一個碼字的比較次數(shù)來看。

    可知，子表法查找比較次數(shù)的理論最小值為此時要求n=s2。如果在第一個步驟(確定子表)中改為采用二分法，則這種情況下就可以對以上碼表中前綴連零再細化，將相同連零個數(shù)的碼字放在一起，增加子表數(shù)而減少子表中的碼字結點數(shù)，可以進一步提高查找效率。
    從以上分析可見，二叉樹的查找效率是最高的。因此可以將二叉樹應用到子表法中，對每一張子表分別建樹。對于二叉樹來說，查找時間與樹的深度有關。觀察子表中的碼字，發(fā)現(xiàn)它們都有不同長度的連零作為前綴，如果直接建樹將導致樹的不平衡并增加了樹的深度。為了解決這個問題，可以考慮在同一張子表中為每個碼字去除相同個數(shù)的連零前綴，然后建立二叉樹。在解碼時，先忽略這些連零個數(shù)，再進行樹的查找。在最理想情況下，這種查找方法的一次查找的平均比較次數(shù)為：

   
    對第一張VLC表采用二叉樹一子表法的最大比較次數(shù)：

   
    幾種算法的對比與復雜度分析如表4所示。

    空間復雜度也是需要考慮的問題。JM參考實現(xiàn)中為Tls和TC的聯(lián)合碼表建立了2個3×4×17的三維數(shù)組共需要408 B的存儲空間。二叉樹法經(jīng)過統(tǒng)計，一棵樹共有124個結點，其中葉結點62個，其余62個結點為根結點或枝結點。建3棵二叉樹所需要的空間為(62×4+62×2)×3=1 116 B。子表法將碼表分成12張子表，每張子表用2個二維數(shù)組表示，而數(shù)組的平均大小為4×6．5，則共要4×6．5×12×2=624 B。

3 結 語
    H．264是現(xiàn)在視頻編解碼領域研究的熱點也是未來發(fā)展的方向，它將代替MPEG2成為主流的信源壓縮標準。H．264應用領域非常廣泛。將H．264的編解碼速度盡可能的提高，可以使其在更多的領域中應用，如數(shù)字電視，消費電子類產(chǎn)品，網(wǎng)絡通信，可視電話等現(xiàn)在熱門領域。在此專門對于CAVLC碼表查找給出了改進方案，通過這三種改進方案，避免了對整個碼表的查找，對碼表的查找在效率上有了很大提高。具有明顯的實用意義。