基于FPGA的并行可變長(cháng)解碼器的實(shí)現技術(shù)

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

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

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

　　1 算法描述

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

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

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

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

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

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

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

　　對于存儲在Buffer中的等待解碼的數據碼流X，用滑動(dòng)窗口從中截取前N位，這里的N應當大于或等于可變長(cháng)碼中最長(cháng)碼字的碼長(cháng)，即N≥ln。由于可變長(cháng)碼最短的碼長(cháng)為l1，因此在這N位碼流中，最多可包含M=[N/l1]個(gè)可變長(cháng)碼。為了表示方便，這里用Wi(i=0,1,…，M-1)表示這M個(gè)可變長(cháng)碼。

　　雖然，對于W0，其起始位置必然為0;如果W0的碼長(cháng)為L(cháng)0，那么W1的起始位置則為L(cháng)0;如果W1的碼長(cháng)為L(cháng)1，那么W2的起始位置為L(cháng)0+L1，依此類(lèi)推。由于在解碼開(kāi)始時(shí)，L0的取值無(wú)法明確，其可能取值范圍是l1≤L0≤Ln，因此每個(gè)Wi的可能起始位置分別由一組值組成。

　　為了實(shí)現并行解碼，采用多個(gè)可變長(cháng)碼檢測單元從所有可能的起始位置同時(shí)偵測，一旦W0的碼長(cháng)L0被偵測出，就可以從所有已解碼的可能的變長(cháng)碼中找出W1，并確定W1的碼長(cháng)L1，由此W2的起始位置也就得以確定。依此類(lèi)推，最多可逐次將Wi(i=0,1,…,M-1)個(gè)變長(cháng)碼解出。

　　每個(gè)Wi的解碼過(guò)程只比Wi-1的解碼過(guò)程多一個(gè)加法操作的延遲，相對于變長(cháng)碼的識別，加法操作的延遲非常的小。當然，如果滑動(dòng)窗口N的取值過(guò)大，每個(gè)Wi之間的加法操作的延遲將累加，這將降低解碼的整體效率。因此對于滑動(dòng)窗口N的選擇，需要結合實(shí)際應用中可變長(cháng)碼編碼的特點(diǎn)來(lái)權衡。

　　設某個(gè)待解碼流為B={110110100011000011001111，…}。這里采用長(cháng)度N=12的滑動(dòng)窗口進(jìn)行碼流提取，由于變長(cháng)碼的長(cháng)度從2～8不等，因此每個(gè)運動(dòng)周期至少可以解碼出1個(gè)碼字，最多可解碼出6個(gè)碼字，這6個(gè)變長(cháng)碼字可能的起始位置分別為W0：{0};W1：{2，3，4，5，6，7，8};W2：{4，5，6，7，8，9，10};W3：{6，7，8，9，10};W4:{8,9,10};W5:{10}。

　　綜合起來(lái)，可能成為該可變長(cháng)碼起始位置的集合為{0，2，3，4，5，6，7，8，9，10}，因此在應用上共需要10個(gè)可變長(cháng)碼檢測單元并行執行。

　　2 實(shí)現與驗證

　　多碼字并行解碼方法實(shí)現的關(guān)鍵在于解碼過(guò)程的并行性，采用硬件方案實(shí)現起來(lái)并不 難。上例中10個(gè)可變長(cháng)碼檢測單元可采用經(jīng)典的位并行解碼方案實(shí)現，因為位并行解碼方案能夠保證不同長(cháng)度碼字的輸出時(shí)間基本相同，為其后的操作帶來(lái)便利。在本文中，采用基于查找表的方式來(lái)實(shí)現。

　　碼字檢測單元所檢測到的可變長(cháng)碼的碼長(cháng)及頁(yè)內偏移量(這里采用碼字的最右位作為頁(yè)內偏移量)，在識別過(guò)程中可能存在沒(méi)有任何有效碼字的情況。為此，增加了一位有效狀態(tài)位，作為輸出是否有效的標志。變長(cháng)碼檢測單元CD的結構框圖如圖1所示。

　　由于前一個(gè)有效碼字Wi-1的碼長(cháng)控制著(zhù)碼字Wi的選取，而對應Wi-1的檢測單元Cdi-1輸出了Wi-1的碼長(cháng)，因此在實(shí)現上可以采用將Cdi-1的輸出作為有效碼字Wi選取的控制位，它通過(guò)控制一個(gè)多路選擇器MUX，從所有對應可能是Wi起始位置的CD輸出中選取有效的輸出作為有效碼字Wi。在有效字Wi被成功識別后，需要將其碼長(cháng)即Cdi的輸出與Cdi-1的輸出相加，作為有效碼字選擇的控制。這些功能通過(guò)一個(gè)復合的多路復用器-加法器MA實(shí)現，多路復用器-加法器MA的結構如圖2所示?！　?/p>

 　　在所有有效碼字的起始位置被識別后，根據對應CD單元的輸出，即碼長(cháng)信息和頁(yè)內偏移量，可以通過(guò)查表將對應的碼長(cháng)數據轉換成相應的信源符號或存儲相應信源符號的地址。這些功能由信號轉換單元SYMBOL完成。

　　根據上面的討論，設計出用于上例的多符號并行解碼器，其結構圖如圖3所示?！　?/p>

 　　為了驗證這種這種結構，采用FPGA器件實(shí)現它，選擇的是一片Xilinx xc2s400e-6ft256器件，其規模為145000門(mén)。在這里，采用VHDL語(yǔ)言進(jìn)行RTL級描述，利用XST進(jìn)行綜合，并在ModelSim5.8中進(jìn)行仿真。結果驗證正確，其仿真結果如圖4所示?！　?/p>

 　　實(shí)驗表明，系統允許最大時(shí)鐘頻率為44.172MHz，占用了197個(gè)SlICe(4%)，74個(gè)Slice Flip Flops(<1%)，347個(gè)四輸入查找表(12%)和1個(gè)全局時(shí)鐘(25%)。