可變長(zhǎng)編碼" title="變長(zhǎng)編碼">變長(zhǎng)編碼(VLC)是一種無(wú)損熵編碼，它廣泛應(yīng)用于多媒體信息處理等諸多領(lǐng)域。在H.261/263、MPEG1/2/3等國(guó)際標(biāo)準(zhǔn)中，VLC占有重要地位。VLC的基本思想是對(duì)一組出現(xiàn)概率各不相同的信源符號(hào)，采用不同長(zhǎng)度的碼字表示，對(duì)出現(xiàn)概率高的信源符號(hào)采用短碼字，對(duì)出現(xiàn)概率低的信源符號(hào)采用長(zhǎng)碼字。Huffman編碼是一種典型的VLC，其編碼碼字的平均碼長(zhǎng)非常接近于數(shù)據(jù)壓縮的理論極限——熵。
　　可變長(zhǎng)解碼(VLD)是VLC的逆過(guò)程，它從一組連續(xù)的碼流中提取出可變長(zhǎng)碼字，并將之轉(zhuǎn)換為對(duì)應(yīng)的信源符號(hào)。由于在VLC過(guò)程中，碼字之間通常不會(huì)加入任何分隔標(biāo)識(shí)，這就造成了在解碼過(guò)程中識(shí)別碼字的困難。因此，在VLD過(guò)程中，變長(zhǎng)碼字必須逐一識(shí)別，只有碼流中居前的碼字被識(shí)別之后，才能定位后序碼字的起始位置，這一點(diǎn)在很大程度上限制了VLD運(yùn)行的效率。
　　本文討論一種新型的VLD解碼結(jié)構(gòu)，它通過(guò)并行偵測(cè)多路" title="多路">多路碼字，將Buffer中的多個(gè)可變長(zhǎng)碼一次讀出，這將極大地提高VLD的吞吐量和執(zhí)行效率。然后采用FPGA對(duì)這種并行VLD算法的結(jié)構(gòu)進(jìn)行驗(yàn)證，最終得出相應(yīng)結(jié)論。
1 算法描述
　　由于碼流中的可變長(zhǎng)碼之間具有前向依賴性，因此如何確定可變長(zhǎng)碼碼字在連續(xù)碼流中的起始位置是VLD的關(guān)鍵所在。傳統(tǒng)的VLD解碼方案主要分為位串行解碼方案和位并行解碼方案兩種。
　　在位串行解碼方案中，碼流逐位送入解碼器，解碼器通過(guò)逐位匹配實(shí)現(xiàn)可變長(zhǎng)碼的解碼。這種過(guò)程實(shí)質(zhì)上是一種建造Huffman樹(shù)的反過(guò)程，從根節(jié)點(diǎn)出發(fā)，直至葉子節(jié)點(diǎn)為止。由于這種方式采用逐位操作方式，而可變長(zhǎng)碼的碼長(zhǎng)又各不相同，使得碼字識(shí)別所需的運(yùn)行周期也不相同。在解碼長(zhǎng)較短的碼字時(shí)，其解碼速度較快，而在解碼長(zhǎng)較長(zhǎng)的碼字時(shí)，其解碼速度較慢。顯然，位串行解碼方案效率相對(duì)較低，解碼速度因碼字長(zhǎng)度不同而不同，無(wú)法滿足某些對(duì)實(shí)時(shí)性要求較高的應(yīng)用場(chǎng)合。
　　針對(duì)位串行解碼方案的不足，多種位并行解碼方案被提出。位并行解碼方案采用并行方式工作，通過(guò)對(duì)可變長(zhǎng)碼的碼字進(jìn)行排序(Ordering)、分割(Partitioning)和簇化(Clustering)，采用基于邏輯塊的匹配模式或基于樹(shù)的匹配模式來(lái)實(shí)現(xiàn)^[1～3]。并行解碼方案大大提高了可變長(zhǎng)碼的解碼效率，而且可以確保每個(gè)運(yùn)行周期輸出一個(gè)解碼碼字，實(shí)現(xiàn)穩(wěn)定的解碼輸出。在高級(jí)的位并行解碼方案中，還可以將解碼過(guò)程分解為若干階段，引入流水線操作，進(jìn)一步提高解碼效率^[4]。
　　在傳統(tǒng)的VLD解碼方案的基礎(chǔ)之上，采用并行操作方式，增加硬件資源和相應(yīng)的控制邏輯，可實(shí)現(xiàn)一個(gè)運(yùn)行周期輸出多個(gè)解碼碼字，使可變長(zhǎng)碼的解碼效率進(jìn)一步得到提高。
　　由于可變長(zhǎng)碼長(zhǎng)度不同，在解碼過(guò)程中碼字存在前向依賴性。如果采用多路并行操作方式，在所有可能成為可變長(zhǎng)碼碼字的起始位置同時(shí)進(jìn)行預(yù)測(cè)，然后通過(guò)后續(xù)控制篩選出合法的碼字，就可以對(duì)多個(gè)可變長(zhǎng)碼實(shí)現(xiàn)同時(shí)解碼。這就是多符號(hào)可變長(zhǎng)并行解碼方案的基本思想。

　　具體說(shuō)明如下：假設(shè)某個(gè)信源符號(hào)集有K個(gè)符號(hào)，K個(gè)符號(hào)所對(duì)應(yīng)的變長(zhǎng)碼字用{0,1},k=0,…,K-1表示,這些變長(zhǎng)碼的長(zhǎng)度為集合L，其中最長(zhǎng)的碼長(zhǎng)用l_n表示，最短的碼長(zhǎng)用l1表示;具有相同碼長(zhǎng)的碼字最多為d_max個(gè)。現(xiàn)采用分頁(yè)方式重新組織這些可變長(zhǎng)碼，將具有相同碼長(zhǎng)的碼字存入一個(gè)頁(yè)內(nèi)，那么易知一個(gè)頁(yè)內(nèi)最多可能擁有d_max個(gè)碼字。為了識(shí)別一個(gè)頁(yè)內(nèi)的不同碼字，還需要引入頁(yè)內(nèi)偏移量，然后采用線性結(jié)構(gòu)將這些頁(yè)面重新組合。
　　下面給出一個(gè)依據(jù)該思想重新組織信源符號(hào)的實(shí)例：
　　假設(shè)可變長(zhǎng)碼碼表如表1所示。用變長(zhǎng)碼的長(zhǎng)度表示頁(yè)號(hào)，用變長(zhǎng)碼的最右一位表示頁(yè)內(nèi)偏移量，重新組織符號(hào)表，如表2所示。這樣，在解可變長(zhǎng)碼時(shí)，可以將焦點(diǎn)主要集中在獲取可變長(zhǎng)碼長(zhǎng)度和頁(yè)內(nèi)偏移量的問(wèn)題上來(lái)，然后再將其轉(zhuǎn)換成對(duì)應(yīng)的信源符號(hào)。

?

　　對(duì)于存儲(chǔ)在Buffer中的等待解碼的數(shù)據(jù)碼流X，用滑動(dòng)窗口從中截取前N位，這里的N應(yīng)當(dāng)大于或等于可變長(zhǎng)碼中最長(zhǎng)碼字的碼長(zhǎng)，即N≥l_n。由于可變長(zhǎng)碼最短的碼長(zhǎng)為l₁，因此在這N位碼流中，最多可包含M=[N/l1]個(gè)可變長(zhǎng)碼。為了表示方便，這里用W_i(i=0,1,…，M-1)表示這M個(gè)可變長(zhǎng)碼。
　　顯然，對(duì)于W₀，其起始位置必然為0；如果W₀的碼長(zhǎng)為L(zhǎng)₀，那么W₁的起始位置則為L(zhǎng)₀；如果W1的碼長(zhǎng)為L(zhǎng)₁，那么W₂的起始位置為L(zhǎng)₀+L₁，依此類推。由于在解碼開(kāi)始時(shí)，L₀的取值無(wú)法明確，其可能取值范圍是l₁≤L₀≤L_n，因此每個(gè)W_i的可能起始位置分別由一組值組成。
　　為了實(shí)現(xiàn)并行解碼，采用多個(gè)可變長(zhǎng)碼檢測(cè)單元從所有可能的起始位置同時(shí)偵測(cè)，一旦W₀的碼長(zhǎng)L₀被偵測(cè)出，就可以從所有已解碼的可能的變長(zhǎng)碼中找出W₁，并確定W₁的碼長(zhǎng)L₁，由此W₂的起始位置也就得以確定。依此類推，最多可逐次將W_i(i=0,1,…，M-1)個(gè)變長(zhǎng)碼解出。
　　每個(gè)W_i的解碼過(guò)程只比W_i-1的解碼過(guò)程多一個(gè)加法操作的延遲，相對(duì)于變長(zhǎng)碼的識(shí)別，加法操作的延遲非常的小。當(dāng)然，如果滑動(dòng)窗口N的取值過(guò)大，每個(gè)W_i之間的加法操作的延遲將累加，這將降低解碼的整體效率。因此對(duì)于滑動(dòng)窗口N的選擇，需要結(jié)合實(shí)際應(yīng)用中可變長(zhǎng)碼編碼的特點(diǎn)來(lái)權(quán)衡。
　　設(shè)某個(gè)待解碼流為B={110110100011000011001111, ...}。這里采用長(zhǎng)度N=12的滑動(dòng)窗口進(jìn)行碼流提取，由于變長(zhǎng)碼的長(zhǎng)度從2~8不等，因此每個(gè)運(yùn)行周期至少可以解碼出1個(gè)碼字，最多可解碼出6個(gè)碼字，這6個(gè)變長(zhǎng)碼字可能的起始位置分別為W₀：{0}；W₁：{2,3,4,5,6,7,8}；W₂：{4,5,6,7,8,9,10}；W₃：{6,7,8,9,10}；W₄：{8,9,10}；W₅：{10}。
　　綜合起來(lái)，可能成為該可變長(zhǎng)碼起始位置的集合為{0,2,3,4,5,6,7,8,9,10}，因此在應(yīng)用上共需要10個(gè)可變長(zhǎng)碼檢測(cè)單元并行執(zhí)行。
2 實(shí)現(xiàn)與驗(yàn)證
　　多碼字并行解碼方法實(shí)現(xiàn)的關(guān)鍵在于解碼過(guò)程的并行性，采用硬件方案實(shí)現(xiàn)起來(lái)并不難。上例中10個(gè)可變長(zhǎng)碼檢測(cè)單元可采用經(jīng)典的位并行解碼方案實(shí)現(xiàn)，因?yàn)槲徊⑿薪獯a方案能夠保證不同長(zhǎng)度碼字的輸出時(shí)間基本相同，為其后的操作帶來(lái)便利。在本文中，采用基于查找表" title="查找表">查找表的方式來(lái)實(shí)現(xiàn)。
　　碼字檢測(cè)單元所檢測(cè)到的可變長(zhǎng)碼的碼長(zhǎng)及頁(yè)內(nèi)偏移量(這里采用碼字的最右位作為頁(yè)內(nèi)偏移量)，在識(shí)別過(guò)程中可能存在沒(méi)有任何有效碼字的情況。為此，增加了一位有效狀態(tài)位，作為輸出是否有效的標(biāo)志。變長(zhǎng)碼檢測(cè)單元CD的結(jié)構(gòu)框圖如圖1所示。
　　由于前一個(gè)有效碼字W_i-1的碼長(zhǎng)控制著碼字W_i的選取，而對(duì)應(yīng)W_i-1的檢測(cè)單元CD_i-1輸出了W_i-1的碼長(zhǎng)，因此在實(shí)現(xiàn)上可以采用將CD_i-1的輸出作為有效碼字W_i選取的控制位，它通過(guò)控制一個(gè)多路選擇器MUX，從所有對(duì)應(yīng)可能是W_i起始位置的CD輸出中選取有效的輸出作為有效碼字W_i。在有效碼字W_i被成功識(shí)別后，需要將其碼長(zhǎng)即CD_i的輸出與CD_i-1的輸出相加，作為有效碼字選擇的控制。這些功能通過(guò)一個(gè)復(fù)合的多路復(fù)用器" title="多路復(fù)用器">多路復(fù)用器-加法器MA實(shí)現(xiàn)，多路復(fù)用器-加法器MA的結(jié)構(gòu)如圖2所示。

　　在所有有效碼字的起始位置被識(shí)別后，根據(jù)對(duì)應(yīng)CD單元的輸出，即碼長(zhǎng)信息和頁(yè)內(nèi)偏移量，可以通過(guò)查表將對(duì)應(yīng)的碼長(zhǎng)數(shù)據(jù)轉(zhuǎn)換成相應(yīng)的信源符號(hào)或存儲(chǔ)相應(yīng)信源符號(hào)的地址。這些功能由信號(hào)轉(zhuǎn)換單元SYMBOL完成。
　　根據(jù)上面的討論，設(shè)計(jì)出用于上例的多符號(hào)并行解碼器，其結(jié)構(gòu)圖如圖3所示。

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