一種可實現零內存存取的CAVLC解碼算法

黃明政，韓一石

一種可實現零內存存取的CAVLC解碼算法

黃明政，韓一石

(廣東工業大學信息工程學院，廣州 510006)

在基于上下文的自適應可變長度編碼(CAVLC)解碼算法中，對非結構化自適應可變長度編碼碼表進行解碼時需要反復查找碼表進行碼字匹配，從而導致解碼速度慢和需要大量內存存取的問題。為此，提出一種可實現零內存存取的CAVLC解碼算法。將CAVLC碼字前綴0的個數作為一級索引，同時通過一級索引獲得輸入碼流的可能長度。將碼字后綴作為二級索引并獲得碼字的值，直接通過碼字快速獲得解碼結果。對于確定的輸入碼字，只需通過無碼表查找代碼操作即可得到對應的解碼輸出。測試結果表明，該算法不僅可以實現零內存存取的CAVLC解碼，而且其解碼速度比標準算法提高了45%。

基于上下文的自適應可變長度編碼；零內存存取；碼字前綴；一級索引；碼字后綴；二級索引

1 概述

H.264/AVC是最新的國際性的視頻編解碼標準，它通過ITU-T(電信聯盟)和ISO/IEC(標準聯盟)進行制定[1]。H.264/AVC標準包括基本檔次、高級檔次和主要檔次3種。其中，H.264/AVC基本檔次只包括基于上下文的自適應可變長度編碼(ContextAdaptive Variable Length Coding, CAVLC)技術，這個技術被用來對視頻圖像的塊殘差數據進行編碼。它適用于移動設備環境，這些環境都具有低復雜度、低功耗要求等特點。在H.264/AVC CAVLC編碼中，在對視頻圖像的塊殘差數據量化并進行之字形掃描后，利用Coeff_token、(1)、、和這5個語法元素對視頻圖像的塊殘差數據進行編碼壓縮。其中，語法元素代表非零系數個數()和拖尾系數個數()(1)；1代表拖尾系數符號；代表除了拖尾系數外的非零系數幅值；代表最后一個非零系數之前0的個數；代表每個非零系數前的0個數。在CAVLC解碼算法中，只有和1這2個語法元素通過規則的算術運算進行解碼，其中算術運算的解碼過程不需要查找任何的碼表，所以它不需要進行存儲碼表的內存存取，則這2個語法元素的解碼碼表內存存取次數為0。其余的3個語法元素，如、和，都是通過可變長度的編碼碼表(VLCTs)進行解碼，在此過程中，需要不斷地查找碼表進行相應的解碼碼流的匹配；如果碼字跟解碼的碼流不匹配，需要重新查找；因此，在一次解碼的過程中，需要多次地查找匹配碼表操作才能完成一個碼字的解碼；以此類推在這3個語法元素的解碼過程中，一個視頻圖像碼流需要反復查找匹配存儲在內存中的不規則碼表，因此，這需要消耗大量的內存存取直到所期望的碼字被匹配。在嵌入式系統特別是在多媒體應用場合中，內存存取次數是系統性能和功耗的瓶頸[2]。

為了能夠減少內存存取次數，許多優化的CAVLC解碼算法已經被提出。在硬件設計方案中，文獻[3]將所有的碼表融合成一個碼表，同時將碼表構建成多個子表來減少40%的功耗。文獻[4]提出流水線架構來大幅度降低系統操作頻率，從而進一步減少功耗。在軟件設計方案中，傳統的碼表查找算法，如順序查找碼表算法(TLSS)和二叉樹查找碼表算法(TLBS)被用來進行CAVLC解碼。然而，由于TLSS要進行完整地碼表查找匹配而得到所需要的解碼碼字，因此它需要在每一個解碼碼字上進行碼表的內存存取。由于TLBS對于碼表的內存存取的隨機性，因此它在某些系統中表現得并不是很高效。在一些新的方案中，由于整數算術運算可以直接進行碼字的解碼而不需要碼表查找操作的特性，因而，整數算術運算被引入CAVLC解碼算法中來減少碼表的內存存取次數。在Moon的方案中，用于和語法元素的新碼表被提出來，它通過利用整數算數運算來減少約65%~88%的內存存取次數[5]。在Kim方案中，其他一些整數算數運算被提出來，它可以減少大約94%的內存存取次數[6]。然而，在Moon方案中，少量內存取次數是必須的，因為部分語法元素還使用TLBS來進行解碼。

為消除CAVLC碼表的內存訪問次數，進一步提高解碼速度，本文提出一種可實現零內存存取的CAVLC解碼算法，設計能夠表達非結構化可變長度編碼碼表的代碼，同時利用該算法，不通過任何碼表查找獲得解碼的碼字。

2 CAVLC的解碼原理

在H.264/AVC基本檔次中，CAVLC和Exp-Golomb碼字被用來作為熵編碼的方法。指示信息通過Exp-Golomb碼來進行編碼，其中這些碼字都具有規則性結構。那些殘差塊數據的量化變換系數通過CAVLC碼來進行編碼[7]。在CAVLC中，那些量化的系數被之字形掃描，然后被5個語法元素進行編碼：，(1)，，，。

在CAVLC解碼器中，一個4×4塊殘差數據的之字掃描值通過壓縮的比特流來進行重建。圖1為CAVLC解碼過程的一個例子，它可以在H.264/AVC標準中找到[8]。該圖顯示了在H.264/AVC基本檔次中的CAVLC解碼原理。其中，Zero_left指示了剩余的0系數的個數。1和語法元素一般都通過整數算術運算進行解碼，因為它們都是通過規則的可變長度編碼碼字(VLC)進行編碼的。語法元素、和通過可變長度編碼碼表進行解碼，因為他們都是通過碼表查找來執行的。在解碼的過程中，需要大量的內存存取來找到所需碼字。

圖1 CAVLC解碼示例

3 本文算法

在H.264/AVC CAVLC解碼中，那些利用可變長度編碼碼表進行解碼的語法元素必須得到處理才能減少內存存取次數以進一步降低功耗。在這些語法元素中，語法元素是二維碼表，然而和這2個語法元素的碼表是一維碼表。通過分析可變長度編碼碼表的碼字相關性，本文提出了一種直接的CAVLC解碼方案[9]，具體步驟如下：

(1)將輸入碼流的最開始連續0的個數作為一級索引，同時通過一級索引獲得輸入碼流的可能長度。

(2)確定所提出的碼表中的二級索引并獲得碼字的值。

(3)通過碼字快速地獲得解碼結果。

基于這種原則，二維碼表和一維碼表被分別設計如表1和表2所示。

表1 Coeff_token(VLCT0, 0≤NC＜2)語法元素的部分二維碼表

表2 Total_zeros(Tc=5)語法元素的部分一維碼表

在表1中，碼字(Code)表示對應語法元素的輸入比特流；8位的解碼碼字(Codeword)表示解碼輸出結果；其中前3位表示拖尾系數(1)的個數，后5位表示非零系數的個數()；碼字前綴0的個數表示碼字的第1個非零系數之前部分的連續0個數；碼字后綴(Code Suffix)表示第1個非零系數之后的部分。在表2中，解碼碼字直接表示單一的解碼輸出結果；其他元素表示與表1相同的意思。表3和表4分別表示碼字長度與表1、表2中所提到的碼字前綴0的個數之間的關系。

表3 表1中碼字前綴0的個數和碼字長度之間的關系

表4 表2中碼字前綴0個數和碼字長度之間的關系

本文所提出的解碼算法由以下步驟組成：

Step1 選擇語法元素的可變長編碼碼表的入口。語法元素有3個可變長度編碼碼表和1個固定長度編碼的碼表，分別為(VLCT0, 0≤＜2)、(VLCT1, 2≤＜4)、(VLCT2, 4≤＜8)、(FCLT,=–1)[10]。

Step2 讀取碼字前綴0的個數值，并將其值作為一級索引。

Step3 通過一級索引獲取碼字的長度。其中，語法元素的碼字長度和一級索引之間的關系如表3所示。設定一個參數RL作為二級索引，其中，=碼字長度–碼字前綴的長度。

Step4 讀取在輸入碼流中的可能碼字后綴，并將它假設為，其中，的長度是根據來確定的。將的值跟CAVLC算法中的標準碼字后綴進行比較，可以獲得如表1中的解碼碼字。

其他2種語法元素和也通過同樣的步驟進行解碼，只不過利用碼表表2和表4來代替表1和表3。語法元素和1可以通過規則的整數算術運算進行直接解碼。

圖2展示了一個選擇VLCT0入口開始而實現CAVLC的5個語法元素解碼例子。對于語法元素，一級索引和二級索引可以逐步獲得，則和1的結果可根據一級索引直接得到。

圖2 本文算法的解碼原理

圖2中語法元素的輸入碼流(0000100)，其一級索引為4。如表3所示，可以直接獲取碼字長度為6或7，這樣就可以得到二級索引為1或2。如表1所示，在VLCT0中的碼字后綴可能為(1)，(00)或(01)。對于輸入碼流(0000100)，值與它的碼字后綴相等。筆者轉換值，并與標準的碼字相比較，可以得到解碼碼字為(0X65)。這個解碼的碼字可被解碼為1=2，=5。根據、、1、和元素即可得到解碼輸出。在表1~表4中，加下劃線的數字表示這個例子中所用到的相應參數。

4 仿真結果

本文計算4種算法的CAVLC解碼碼表內存存取次數節省數據，包括二叉樹查找碼表算法(TLBS)、Moon算法，Kim算法和本文算法。針對不同QP值的測試序列，與標準按順序查找碼表算法(TLSS)相比，上述4種算法內存存取次數的減少比例如圖3所示。其中，TLSS算法數值利用JM16.2[11]得到，仿真環境為Windows XP操作系統，CPU為Intel 2.00 GHz，內存大小為1 GB。

圖3 不同序列的碼表內存存取次數節省比例

由圖3可以看出，本文提出的算法完全消除解碼過程中的碼表內存存取次數，并且本文算法節省比例比其他各種算法都高。由于本文算法可以在代碼中完全表達解碼過程中非結構化的可變長度編碼碼表，從而完全省略對碼表的查找，繼而完全省略碼表的內存存取。此外還可以看出，Kim算法比TLBS算法和Moon算法的內存存取次數節省比例更高一點。可以看出，TLBS算法在圖像高QP值處的內存存取次數會少一點，而Moon算法在圖像低QP值處的內存存取次數會少一點。相似結論也可在文獻[6]中找到。

解碼時間通過Window系統的API接口函數Query PerformanceCounter()進行計算，算法的時間節省比例根據下式計算：(1–本文算法/標準算法)×100%。圖4顯示了用不同QP值的各種序列進行測試時，各種算法的解碼時間節省比例。

圖4 120幀圖像序列的時間節省比例結果

表5是圖4的解碼時間數據。其中，Forman、Crew和Paris序列是CIF格式的，而Harbour、Soccer和Mobile序列是QCIF格式的。可以看出，本文算法比其他各種算法具有優越性。與TLSS標準算法相比，本文算法表現出45%的時間節省比例，這是因為該算法不需要進行碼表查找從而可以快速定位解碼碼字。由于Moon算法和Kim算法利用了部分整數算術運算操作，這2種算法相對于TLSS算法也表現出了一定的高效性。而由于TLBS算法的二叉樹隨機內存存取性質，因此，該算法表現得并不高效。

表5 系統的CAVLC解碼次數

5 結束語

H.264標準的CAVLC查表解碼算法在匹配解碼碼字時，需要反復查找碼表，會導致解碼速度慢和需要消耗大量內存存取的問題，為此，本文提出一種可實現零內存存取的直接CAVLC解碼算法。該算法根據CAVLC算法的語法元素、、中前綴0的個數與碼字長度之間的對應關系，利用二級索引思想來提出能夠表達CAVLC中的非結構化碼表，同時利用二級索引技術設計能夠表達非結構化碼表解碼的代碼，實現CAVLC的無碼表查找的直接解碼。仿真結果表明，相比于標準的TLSS算法，本文算法可以實現零內存存取的CAVLC解碼。同時，本文算法比標準TLSS算法快45%，優于目前常見CAVLC解碼算法。這些內存存取次數的節省不僅適用于高比特率的場合，也適用于低比特率的場合。本文算法尤其適用于對功耗要求嚴格的嵌入式平臺編解碼環境[12]。下一步工作是設計無碼表查找同數字算術運算相結合的解碼算法，或純數字算術運算的解碼算法，以實現CAVLC解碼速度、內存存取次數的消除和內存存儲空間的最佳平衡。

[1] ITU. Advanced Video Coding for Generic Audio Visual Services[EB/OL]. (2011-11-01). http://citeseerx.ist.psu.edu/ showciting?cid=323674.

[2] Lee J, Park C, Ha S. Memory Access Pattern Analysis and Stream Cache Design for Multimedia Applications[C]//Proc. of DAC’03. Anaheim, USA: [s. n.], 2003: 21-24.

[3] Lin Hengyao, Lu Yinghong, Liu Binda, et al. A Highly Ef?cient

VLSI Architecture for H.264/AVC CAVLC Decoder[J]. IEEE Transactions on Multimedia, 2008, 10(1): 31-42.

[4] Lee B, Ryoo K. A Design of High-performance Pipelined Architecture for H.264/AVC CAVLC Decoder and Low-power Implementation[J]. IEEE Transactions on Consumer Electronics, 2010, 56(4): 2781-2789.

[5] Moon Y H, Kim G Y, Kim J H. An Efficient Decoding of CAVLC in H.264/AVC Video Coding Standard[J]. IEEE Transactions on Consumer Electronics, 2005, 51(3): 933-938.

[6] Kim Y, Yoo Y, Shin J, et al. Memory-efficient H.264/AVC CAVLC for Fast Decoding[J]. IEEE Transactions on Consumer Electronics, 2006, 52(3): 943-952.

[7] 薛 全, 張 穎, 劉濟林, 等. 基于變步長分組的H.264系數碼表優化[J]. 電路與系統學報, 2006, 11(3): 115-117.

[8] Sullivan G, Bjontegaard G. Recommended Simulation Common Conditions for H.26L Coding Efficiency Experiments on Low-resolution Progressive-scan Source Material[EB/OL]. (2001-09-28). http://65.54.113.26/Publica tion/4142353/.

[9] 張秀麗, 萬 忠, 鮑程紅. 基于碼頭分組的CAVLC解碼算法優化[J]. 電路與系統學報, 2007, 14(3): 26-30.

[10] 畢厚杰. 新一代視頻壓縮編碼標準——H.264/AVC[M]. 北京: 人民郵電出版社, 2005.

[11] Suhring K. JM16.2 Software[EB/OL]. (2011-11-10). http:// iphome.hhi.de/suehring/tml/.

[12] 龔建鋒, 金文光, 季愛明. 基于H.264解碼中CAVLC的優化[J]. 微電子學與計算機, 2007, 24(1): 85-87.

編輯 金胡考

A CAVLC Decoding Algorithm with Zero Memory Access

HUANG Ming-zheng, HAN Yi-shi

(School of Information Engineering, Guangdong University of Technology, Guangzhou 510006, China)

This paper proposes a zero memory access algorithm for direct Context-based Adaptive Variable Length Coding(CAVLC) decoding, aiming to solve the problems of slow decoding speed and a large of memory accesses caused by the repeated table look-up for the match codeword during the unstructured variable length coding table decoding. This algorithm takes the numbers of zero in CAVLC code prefix as the primary index, and gets the probably length of the input code stream. It takes the code suffix as the secondary index and gets the codeword value. It can get the decoded result by the codeword quickly. For the specific input code, the decoded output can be directly gotten without any table look-up. Test results show that not only the algorithm can achieve zero memory access for CAVLC decoding, but also the decoding speed of this algorithm can achieve 45% speed-up, compared with the standard algorithm.

ContextAdaptive Variable Length Coding(CAVLC); zero memory access; code prefix; primary index; code suffix; secondary index

1000-3428(2014)03-0278-05

A

TP919.81

廣東省科技計劃基金資助項目(2011B090400344, 2011B010200029)

黃明政(1989－)，男，碩士研究生，主研方向：視頻通信，視頻編/解碼；韓一石，副教授

2013-03-22

2013-04-23 E-mail：634099571@qq.com

10.3969/j.issn.1000-3428.2014.03.059