摘要：介紹了一種采用并行方式的構(gòu)建的多符號可變長碼解碼器。該解碼器通過增加結(jié)構(gòu)的復(fù)雜性對硬件資源的占用，換取可變長碼解碼的高吞吐量。這種結(jié)構(gòu)突破了可變長碼碼字之間的前向依賴性，可并行偵測出Buffer中的所有可能的碼字。采用FPGA實現(xiàn)了這種結(jié)構(gòu)。

        關(guān)鍵詞：可變長解碼 現(xiàn)場可編程邏輯門陣列 硬件描述語言

        可變長編碼（VLC）是一種無損熵編碼，它廣泛應(yīng)用于多媒體信息處理等諸多領(lǐng)域。在H.261/263、MPEG1/2/3等國際標準中，VLC占有重要地位。VLC的基本思想是對一組出現(xiàn)概率各不相同的信源符號，采用不同長度的碼字表示，對出現(xiàn)概率高的信源符號采用短碼字，對出現(xiàn)概率低的信源符號采用長碼字。Huffman編碼是一種典型的VLC，其編碼碼字的平均碼長非常接近于數(shù)據(jù)壓縮的理論極限——熵。

        可變長解碼（VLD）是VLC的逆過程，它從一組連續(xù)的碼流中提取出可變長碼字，并將之轉(zhuǎn)換為對應(yīng)的信源符號。由于在VLC過程中，碼字之間通常不會加入任何分隔標識，這就造成了在解碼過程中識別碼字的困難。因此，在VLD過程中，變長碼字必須逐一識別，只有碼流中居前的碼字被識別之后，才能定位后序碼字的起始位置，這一點在很大程度上限制了VLD運行的效率。

        本文討論一種新型的VLD解碼結(jié)構(gòu)，它通過并行偵測多路碼字，將Buffer中的多個可變長碼一次讀出，這將極大地提高VLD的吞吐量和執(zhí)行效率。然后采用FPGA對這種并行VLD算法的結(jié)構(gòu)進行驗證，最終得出相應(yīng)結(jié)論。

        1 算法描述

        由于碼流中的可變長碼之間具有前向依賴性，因此如何確定可變長碼碼字在連續(xù)碼流中的起始位置是VLD的關(guān)鍵所在。傳統(tǒng)的VLD解碼方案主要為位串行解碼方案和位并行解碼方案兩種。

        在位串行解碼方案中，碼流逐位送入解碼器，解碼器通過逐位匹配實現(xiàn)可變長碼的解碼。這種過程實質(zhì)上是一種建造Huffman樹的反過程，從根節(jié)點出發(fā)，直至葉子節(jié)點為止。由于這種方式采用逐位操作方式，而可變長碼的碼長又各不相同，使得碼字識別所需的運行周期也不相同。在解碼長較短的碼字時，其解碼速度較快，而在解碼長較長的碼字時，其解碼速度較慢。顯然，位串行解碼方案效率相對較低，解碼速度因碼字長度不同而不同，無法滿足某些對實時性要求較高的應(yīng)用場合。

        針對位串行解碼方案的不足，多種位并行解碼方案被提出。位并行解碼方案采用并行方式工作，通過對可變長碼的碼字進行排序（Ordering）、分割（Partitioning）和簇化（Clustering），采用基于邏輯塊的匹配模式中其它樹的匹配模式來實現(xiàn)。并行解碼方案大大提高了可變長碼的解碼效率，而且可以確何每個運行周期輸出一個解碼碼字，實現(xiàn)穩(wěn)定的解碼輸出。在高級的位并行解碼方案中，還可以將解碼過程分解為若干階段，引入流水線操作，進一步提高解碼效率。

        在傳統(tǒng)的VLD解碼方案的基礎(chǔ)之上，采用并行操作方式，增加硬件資源和相應(yīng)的控制邏輯，可實現(xiàn)一個運行周期輸出多個解碼碼字，使可變長碼的解碼效率進一步得到提高。

        由于可變長碼長度不同，在解碼過程中碼字存在前向依賴性。如果采用多路并行操作方式，在所有可能成為可變長碼碼字的起始位置同時進行預(yù)測，然后通過后續(xù)控制篩選出合法的碼字，就可以對多個可變長碼實現(xiàn)同時解碼。這就是多符號可變長并行解碼方案的基本思想。

        具體說明如下：假設(shè)某個信源符號集有K個符號，K個符號所對應(yīng)的變長碼字用Ck=（cok,…,cimk-1）|ckl∈{0,1},k=0,…,k-1表示，這些變長碼的長度為集合L，其中最長的碼長用ln表示，最短的碼長用l1表示；具有相同碼長的碼字最多為dmax個�，F(xiàn)采用分頁方式重新組織這些可變長碼，將具有相同碼長的碼字存入一個頁內(nèi)，那么易知一個頁內(nèi)最多可能擁有dmax個碼字。為了識別一個頁內(nèi)的不同碼字，還需要引入頁內(nèi)偏移量，然后采用線性結(jié)構(gòu)將這些頁面重新組合。

        下面給出一個依據(jù)該思想重新組織信源符號的實例：

        對于存