徐世寅，徐妮妮，楊雪玲，王 靜

（天津工業(yè)大學(xué)電子與信息工程學(xué)院，天津 300387）

基于QM算術(shù)編碼器的CX序列的反推原理及實(shí)現(xiàn)

徐世寅，徐妮妮，楊雪玲，王 靜

（天津工業(yè)大學(xué)電子與信息工程學(xué)院，天津 300387）

通過對ISO/IEC 10918-1：1993（E）中的QM算術(shù)編碼器流程圖和測試序列進(jìn)行分析，得出CX序列反推原理.利用測試序列中已有的D、MPS、Qe 3列數(shù)據(jù)，結(jié)合QM算術(shù)編碼器的概率推斷狀態(tài)機(jī)和最小化原則，將QM算術(shù)編碼器的測試序列中所缺的CX序列補(bǔ)充完整，同時(shí)得到MPS、Index的初始值，然后將所得數(shù)據(jù)輸入QM算術(shù)編碼器，驗(yàn)證所產(chǎn)生CX序列的正確性.

CX序列；QM算術(shù)編碼；最小化原則；反推原理

QM算術(shù)編碼是一種自適應(yīng)二進(jìn)制算術(shù)編碼[1-5]，是IBM公司的專利技術(shù).它采用遞歸劃分概率區(qū)間的編碼方式，當(dāng)有足夠多的數(shù)據(jù)輸入時(shí)，QM算術(shù)編碼能夠逼近香農(nóng)熵編碼極限，比霍夫曼編碼擁有更高的編碼效率和靈活性，被廣泛應(yīng)用于JBIG[1]和JPEG[6]國際標(biāo)準(zhǔn)中.國內(nèi)算術(shù)編碼方面的文獻(xiàn)相當(dāng)缺乏，僅有的一篇論文原理還不正確，并且算術(shù)編碼器方面的測試實(shí)例更是難以找到. ISO/IEC10918-1：1993（E）國際標(biāo)準(zhǔn)[6]給使用者設(shè)置了相當(dāng)高的門檻，并且標(biāo)準(zhǔn)中給出的流程圖存在瑕疵，導(dǎo)致使用者無法看懂和正確理解QM算術(shù)編碼器.在標(biāo)準(zhǔn)中雖然給出了QM算術(shù)編碼器的流程圖和測試序列，但是標(biāo)準(zhǔn)制定者卻故意把測試序列中的CX序列隱去了，讓初學(xué)者很難通過流程圖和測試序列看懂和正確使用QM算術(shù)編碼器.因此，本文在QM算術(shù)編碼器的基礎(chǔ)上，給出CX序列的反推原理、實(shí)現(xiàn)及相關(guān)分析，編程產(chǎn)生CX序列、MPS的初始值、Index的初始值，使測試序列成為一個(gè)完整的實(shí)例，并將產(chǎn)生的各序列輸入QM算術(shù)編碼程序，驗(yàn)證其正確性.

1 CX反推原理

1.1CX在QM算術(shù)編碼器中的作用

QM算術(shù)編碼的編碼器、解碼器如圖1所示.

圖1 QM算術(shù)編碼的編碼器與解碼器Fig.1 Encoder and decoder of QM arithmetic

在編碼器中，上下文索引CX和待壓縮二進(jìn)制數(shù)據(jù)D構(gòu)成比特、索引對，例如（1，17），（1，19），（0，36）輸入編碼器編碼產(chǎn)生壓縮數(shù)據(jù)，壓縮數(shù)據(jù)以十六進(jìn)制字節(jié)的形式存儲，例如0X65，0X7D，0X46；在解碼器中，與編碼器中相同的上下文索引CX和存儲的壓縮數(shù)據(jù)共同輸入解碼器，解碼產(chǎn)生原始二進(jìn)制數(shù)據(jù)D.上下文索引CX由DCT變換的量化系數(shù)所得，具體產(chǎn)生過程請參考ISO/IEC 10918-1：1993（E）國際標(biāo)準(zhǔn)中的相關(guān)說明.

1.2 CX反推原理變量說明

反推原理中用到的變量包括：CX、D、MPS（CX）、Index（CX）、NMPS、NLPS、Switch.上下文索引CX為所求的變量，它的取值變化范圍為0～294；待壓縮數(shù)據(jù)D為二進(jìn)制，它的取值范圍為0，1；MPS（CX）是對應(yīng)于每個(gè)CX的大小概率判斷標(biāo)志，MPS（CX）取值范圍為0，1；Index（CX）是對應(yīng)于每個(gè)CX的概率推斷狀態(tài)機(jī)中的索引值，Index（CX）取值范圍為0~113，在概率推斷狀態(tài)機(jī)中每個(gè)Index（CX）都對應(yīng)NMPS、NLPS、Switch 3個(gè)變量；NMPS為下一個(gè)大概率索引值；NLPS為下一個(gè)小概率索引值；Switch為大小概率判斷標(biāo)志的反轉(zhuǎn)標(biāo)志.NMPS、NLPS的取值范圍與Index（CX）相同，Switch的取值范圍為0，1.為便于查看，上述變量的取值范圍如表1所示.

表1 變量取值表Tab.1 Variable value table

Qe、Index（CX）、NMPS、NLPS、Switch共同組成概率推斷狀態(tài)機(jī)，在編解碼中用到的變量Qe值與概率推斷狀態(tài)機(jī)中的Index（CX）相對應(yīng)，根據(jù)Qe值可在概率推斷狀態(tài)機(jī)中查到與之對應(yīng)的Index（CX）、NMPS、NLPS、Switch值，以便確定下一個(gè)狀態(tài).

1.3 MPS（CX）與CX的關(guān)系

待壓縮數(shù)據(jù)D輸入算術(shù)編碼器后，根據(jù)D是0或1，選擇是CODE1還是CODE0流程，如圖2所示.

在進(jìn)入子程序后，根據(jù)MPS（CX）的值選擇是大概率還是小概率子程序.由流程圖可知，當(dāng)D和MPS（CX）的值相同時(shí)進(jìn)行大概率編碼，不同時(shí)進(jìn)行小概率編碼.MPS（CX）為當(dāng)前CX大小概率標(biāo)志，程序初始化時(shí)默認(rèn)MPS（CX）=1為大概率，MPS（CX）=0為小概率；當(dāng)遇到大小概率判斷標(biāo)志的反轉(zhuǎn)標(biāo)志Switch=1時(shí)，MPS（CX）的大小概率判斷標(biāo)準(zhǔn)發(fā)生反轉(zhuǎn)，MPS（CX）=0為大概率，MPS（CX）=1為小概率；當(dāng)再次遇到Switch=1時(shí)，MPS（CX）將反轉(zhuǎn)回默認(rèn)值.

圖2 編碼1和0的流程Fig.2 CODE1 and CODE0 procedure

1.4 Qe、Index（CX）與CX的關(guān)系

當(dāng)進(jìn)入大小概率編碼子程序時(shí)，程序根據(jù)CX的值查概率推斷狀態(tài)機(jī)找到相應(yīng)Index（CX）對應(yīng)的Qe值進(jìn)行編解碼，操作相關(guān)區(qū)間寄存器和編碼寄存器，然后根據(jù)CX對應(yīng)的Index（CX）值查概率推斷狀態(tài)機(jī)找到對應(yīng)的下一個(gè)遷移狀態(tài)的Index（CX），即NMPS、NLPS值，并根據(jù)Switch的值完成MPS（CX）的條件性反轉(zhuǎn).

1.5 CX反推原理說明

根據(jù)以上CX自身及相關(guān)量的描述，可以確定基于ISO/IEC 10918-1：1993（E）中測試序列的CX反推原理.在測試序列中，MPS（CX）是測試序列的最終結(jié)果，并不是每個(gè)CX對應(yīng)的MPS（CX）初始值，同時(shí)在測試序列中，根據(jù)Qe值，查找概率推斷狀態(tài)機(jī)可找到對應(yīng)的Index（CX）值.將測試序列中的Qe值替換成Index（CX）值，構(gòu)成新數(shù)據(jù)表，由于篇幅限制，讀者可自行完成新數(shù)據(jù)表，此處僅列出部分?jǐn)?shù)據(jù)，如表2所示.

表2 數(shù)據(jù)表Tab.2 Data table

設(shè)變量index（CX）（CX為變量，變化范圍為0~ 294），用以記錄當(dāng)前正在使用的Index（CX）值（Index（CX）代表數(shù)據(jù)表2中的256個(gè)數(shù)據(jù)中的一個(gè)，僅是代表值的符號而已）；設(shè)變量mps（CX）（CX為變量，變化范圍為0~294），用以記錄當(dāng)前正在使用的MPS（CX）值（MPS（CX）代表數(shù)據(jù)表2中的256個(gè)數(shù)據(jù)中的一個(gè)，僅是代表值的符號而已）.初始化第一個(gè)index（CX=0）=0，mps（CX=0）=0.

CX反推原理主要分為2部分：①已有值index（CX）的處理；②新賦值index（CX）的處理.反推原理中用到了產(chǎn)生CX的最小化原則，即每次都將原CX加1賦給下一個(gè)新CX，這樣產(chǎn)生的CX的數(shù)值范圍最小.反推原理通過處理index（CX）值來產(chǎn)生CX值，并通過最小化原則控制產(chǎn)生CX的數(shù)值范圍最小.

對于選擇哪一部分產(chǎn)生CX，需要判斷index（CX）所記錄的值中是否有與當(dāng)前Index（CX）相等的值，即遍歷所有已有值index（CX）查找.如果有，則選擇已有值index（CX）部分處理；如果沒有，則選擇新賦值index（CX）部分處理.

對于已有值index（CX）部分，首先判斷數(shù)據(jù)表2中與Index（CX）對應(yīng)的D與MPS（CX）是否相等，以便確定是大概率還是小概率.如果是大概率，將與數(shù)據(jù)表2中Index（CX）對應(yīng)的NMPS值賦給index（CX），確定下一個(gè)index（CX）的更新值，然后判斷當(dāng)前mps（CX）值是否與數(shù)據(jù)表2中當(dāng)前Index（CX）對應(yīng)的MPS（CX）值相同.如果相同，則將數(shù)據(jù)表2中當(dāng)前MPS（CX）值的下一個(gè)值賦給當(dāng)前mps（CX）；如果不相同，則需要從新賦值的index（CX）處重新開始.如果是小概率，將與數(shù)據(jù)表2中Index（CX）對應(yīng)的NLPS值賦給index（CX），重復(fù)大概率index（CX）更新值后的過程，最后將出現(xiàn)過的CX記錄下來.

對于新賦值index（CX）部分，即產(chǎn)生新的CX，將數(shù)據(jù)表2中Index（CX）當(dāng)前值賦給index（CX），然后判斷D與MPS（CX）是否相等，以便確定是大概率還是小概率.如果是大概率，將與數(shù)據(jù)表2中Index（CX）對應(yīng)的NMPS值賦給index（CX），確定下一個(gè)index（CX）的更新值，然后將數(shù)據(jù)表2中當(dāng)前Index（CX）對應(yīng)的MPS（CX）值賦給mps（CX）；如果是小概率，將數(shù)據(jù)表2中與Index（CX）對應(yīng)的NLPS值賦給index（CX），確定下一個(gè)index（CX）的更新值，然后將數(shù)據(jù)表2中當(dāng)前Index（CX）對應(yīng)的MPS（CX）值賦給mps（CX）.將期間使用過的CX記錄下來.

在新賦值index（CX）部分，每次都是產(chǎn)生新的CX，即index（CX）和mps（CX）記錄的都是Index（CX）和MPS（CX）的初始值.因此可以通過以上過程獲得CX值，Index（CX）、MPS（CX）初始值.

2 CX反推原理流程圖

CX反推原理總流程圖如圖3所示.程序通過Initialize程序初始化所需的變量，通過Find index[CX]程序查找與Index[CX]相等的index[CX]，如果找到則執(zhí)行Old_index[CX]子程序（已有值index（CX）部分），如果沒有找到，則執(zhí)行New_index[CX]子程序（新賦值index（CX）部分）.

圖3GET_CX流程Fig.3 GET_CX procedure

Initialize程序如圖4所示.初始化各變量，初始化CX=0，變量CX用以記錄當(dāng)前正在使用的CX的值；初始化y=0，變量y用以記錄新產(chǎn)生CX的值；初始化result=0，變量用以記錄當(dāng)前Old_index[CX]和New_index[CX]的選擇標(biāo)志位，即是否找到了匹配的index [CX]，result=0表示未找到，result=1表示已找到；初始化數(shù)組index[295]，用以記錄各個(gè)CX對應(yīng)的index [CX]值；初始化數(shù)組mps[295]，用以記錄各個(gè)CX對應(yīng)的mps[CX]值；初始化數(shù)組cx[256]，用以記錄測試序列中使用過的CX.

Find index[CX]程序如圖5所示，通過遍歷所有已有的index[CX]來查找與Index[CX]匹配的index[CX]，返回已有的CX值和子程序選擇標(biāo)志位result以確認(rèn)使用Old_index[CX]和New_index[CX]哪一個(gè)子程序來產(chǎn)生CX.

圖4 初始化流程Fig.4 Initialisation procedure

圖5 Find index[CX]流程Fig.5 Find index[CX]procedure

圖6所示為Old_index[CX]子程序流程，在流程中存在無條件跳轉(zhuǎn)Go to Mark，跳轉(zhuǎn)到主程序Mark處轉(zhuǎn)而執(zhí)行New_index[CX]子程序.圖7所示為New_index [CX]子程序流程.

圖6 Old_index[CX]流程Fig.6 Old_index[CX]procedure

圖7 New_index[CX]流程Fig.7 New_index[CX]procedure

3 實(shí)驗(yàn)結(jié)果驗(yàn)證

實(shí)驗(yàn)是在VC6.0[7]環(huán)境下測試通過的，運(yùn)行程序得到數(shù)據(jù)CX、MPS初始值、Index初始值，如表3所示.

表3 CX對應(yīng)MPS和Index初始值Tab.3 Initial value of MPS and Index corresponding to CX

測試序列中共256個(gè)CX取值，CX取值如表4所示.

表4 所有CX值Tab.4 All values of CX

為了驗(yàn)證GET_CX程序的正確性，將程序中所得的數(shù)據(jù)和待壓縮數(shù)據(jù)D輸入QM算術(shù)編碼器，QM算術(shù)編碼器程序仍然在VC6.0環(huán)境下運(yùn)行，程序運(yùn)行正確，在此僅將測試序列編碼表的部分?jǐn)?shù)據(jù)列出，測試序列的解碼表中的CX與編碼表中對應(yīng)CX值相同，程序結(jié)果如表5所示.

表5 測試序列Tab.5 Test sequence

4 結(jié)束語

故意缺省CX列的測試序列，給人們學(xué)習(xí)QM算術(shù)編碼器帶來諸多困難.本文設(shè)計(jì)的CX序列反推程序很好地解決了這個(gè)問題，并且提供了完整的測試序列所需的CX、MPS和Index初始值，供人們測試自己編寫的QM算術(shù)編碼器；而且在設(shè)計(jì)CX反推程序的過程中，涉及到一些QM算術(shù)編碼器的概念理解，對人們學(xué)習(xí)QM算術(shù)編碼器起到了一定的啟發(fā)作用，舉一反三，對理解其他算術(shù)編碼器也有一定的幫助.

[1] 小野定康，鈴木純司（日）.JPEG技術(shù)[M].葉明，譯.北京：科學(xué)出版社,2003.

[2] 小野定康，鈴木純司（日）.JPEG2000技術(shù)[M].強(qiáng)增福，譯.北京：科學(xué)出版社，2004.

[3] LANGDON G.IBM J Res Develop:An Introduction to Arithmetic Coding[Z].1984.

[4] ONO F,YOSHIDA M，KIMURA T，et al.Subtraction-type arithmetic coding with MPS/LPS conditional exchange[C]//Annual Spring Conference of IECED.Japan:D-288，1990.

[5] LANGDON G.Method for carry-over control in a fifo arithmetic code string[J].IBM Technical Disclosure Bulletin，1980，23（1）：310-312.

[6] CCITT.ISO/IEC 10918-1，T.81(09/92)[Z].FRENCH:CCITT，1992.

[7] HANLY Jeri R，KOFFMAN Elliot B.Problem Solving and Program Design in C[M].萬波，潘蓉，鄭海紅，譯.北京：人民郵電出版社，2007.

Backstepping principle and implementation of CX sequence based on QM arithmetic encoder

XU Shi-yin，XU Ni-ni，YANG Xue-ling，WANG Jing
（School of Electronics and Information Engineering，Tianjin Polytechnic University，Tianjin 300387，China）

The backstepping principle of CX sequence is obtained by the analysis of the flow chart and test sequence about QM arithmetic encoder in ISO/IEC 10918-1：1993(E).Using D,MPS,Qe,the three columns of data in test sequence,and combining probability estimation state machine of QM arithmetic encoder and the minimization principle,the test sequence of QM arithmetic encoder is supplemented with its lacking CX sequence,meanwhile,initial values of MPS and Index is gotten.Then,the obtained data are entered into QM arithmetic encoder and the correctness of produced CX sequence is verified.

CX sequence；QM arithmetic encoder；minimization principle；backstepping principle

TN911.7

：A

：1671-024X（2013）01-0061-05

2012-05-16

：國家自然科學(xué)基金資助項(xiàng)目（60602036）

徐世寅（1986—），男，碩士研究生.

徐妮妮（1974—），女，博士，副教授，碩士生導(dǎo)師.E-mail:xunini@tjpu.edu.cn