о뷢չ
JOURNAL OF COMPUTER RESEARCH
AND DEVELOPMENT
1999 36 12 Vol.36 No.12 1999



ͨõĸ
ɡʯ
ժҪлڳQM˶Գƶı뷽ʽSTQMŶı뷽ʽOTQMSTQMOTQMǴżر.ǲQMĳ96%ıЧʣҲ.OTQMԶ̬ĵṹʹñٶȴﵽֵ.STQMڿɲԺ߼·Ƽ򵥵ص㣬ʹ֮ʺ̬ͼĻרӲƵرģ.
ؼʡQMSTQMOTQMѹӦģ
ͼšTP391
UNIVERSAL HIGH PERFORMANCE ARITHMETIC ENCODER
YAN Yu-Song and SHI Qing-Yun
(National Laboratory of Machine Perception,
Peking University, Beijing 100871)
AbstractIn this paper, symmetry binary tree coder (STQM) and optimal binary tree coder (OTQM) are proposed based on the QM-coder. STQM and OTQM are multiplication-free arithmetic coders with high performance for multi-symbol alphabet, which not only keep the encoding efficiency of QM-coder, but also keep its high speed. OTQM can adjust its binary tree structure dynamically. This advantage enables the encoder to reach its maximum speed. STQM can be implemented by special hardware as a parallel coder, so that it is very useful for video coding. 
Key wordsQM-coderSTQMOTQMdata compressionadaptive model
1
QMһֳѹ㷨.90ľֹͼѹ׼JPEGJBIGУ1.ѡõԭг96%ıЧʣܴﵽȻõѹˮƽ.ͬʱĳ˷òͼĴĽһ޳˷ı뷽.ڱŵĸʸ£QM״̬λõתʵֵģַCACM872ĳ㣬ͬʱӦ.ЩʹQMΪһֱȽϺõıѡ.QM״̬ĸ»ƣʹֻܷӳŵĸʱ仯Ҫ뽫ƹżϣṹ.JPEG׼õڷǶԳƶṹֽṹDCT任ϵֲģͨ.ĶԳƶ뷽STQMŶı뷽ʽOTQMʹQMͨá١ЧʡӦṹ򵥡ɲСִַ֧ŵ.
Ľڵ2ڶQM򵥽ܣڵ3ڸSTQMĹ췽4ڶַ֤5ڸOTQMĹۣ6ڸʵ.
2QM
QMԴIBM˾QLangdon,Rissanen˵ڹչģ뷽һQMԭϿطΪƱͳģ֣
QMһֶƱ뷽ζž͵һĶԣֻܶ01Žб룮ڱУQM¹һʹĴA0.751.5֮䣬ͬʱԱĴCӦA㣺0.75A1.51ȽϽӽɽҪó˷ȷĸʼϸAQeQeֱӽƣȥ˳˷㣬ٶ.
ͳģͲ֣QMɫ״̬ĸʹֵÿһӦķŸʣQMܹ״ָ̬ʽж̬ƣʵʵ㷨У״̬һ״ֵ̬ʾģ״̬ʵĹֵQeԼ״̬תƷ򣮳ʼʱΪһʼ״̬ӦĸʹֵQeӳ˷ŵĳʼֲű̵ĲϼĸʷֲҲڲϵı仯ÿ¹һʱ״̬ᰴ״ֵ̬״̬תƷı䵽һ״̬״̬ӦQeֵǶԵǰŸʵĸ¹ƣ״ֵ̬Ʊֵֹ֤׼ȷԣPennebakerMitchellף3жԴϸĲ.ڷ״̬ӳ˷ŵĸʣÿһֻҪάһ״ֵ̬ȷǰʲô״̬õʵĹƣ룮
QMһӦ룮ڷ״̬ı仯ŷŵԶģQMܹշľֲֲԣԷŵͳƣкǿӦͬʱ״̬תƷʹһӦԸʹҪĳ㣬һٶ.
УͨΪÿһһضSͬSӦŲͬķҲӦŲͬķŸʣܹͬʱԲͬķøԵķŸʽб룬ôֱͳΪı룬ͳΪһı룮QM״̬һ113״̬һʹ۶ԵһĻǻĶܱ֤ʹֵ׼ȷ.
ʹQMҪ¼ⲿ

Initenc()ʼ
Code_0(S)S0о
Code_1(S)S1о
Flush()ֹ

Initdec()ʼ
Decode(S)Sо
ʱȵInitenc()ǶԱгʼŶΪSĶֵб룬Ϊ0͵Code_0(S)Ϊ1͵Code_1(S).ʱFlush()ԱĴÿ.
ʱʹInitdec()Խгʼ.ŲϵDecode(S)Sн룬õ01ɵĶƷ.
ڱУSǱ־ͬķQMı룬Ҳ˵ԶԼ·ͬʱ룬ÿһ·øԵ״ֵ̬ƸʣһصʹǿԽQMĹ죮ʵϣıÿһڵͶӦһģͱ൱һĵQM
3STQMĹ
QMԭֻԶֵżб룬ҪʹԴżб룬رʣöĽṹ.ǽ۶ṹQMνϵ.
ŴkķżΪSS={x0,x1,,xN-1}xi,i=0,,N-1ʾkпֵܳNַ.ǶNΪżSĳȣΪ|S|.ڶֵżȻ|{x0,x1}|=2.NȽϴǾͳSΪż.
żSԷֳS0S1֣㣺S=S0S1ôڷŴkеκһxӦ

(1)
p(x=xi|xS)ΪŴkзxiĸʣӳڱ뷽Ͼǣ
(1)ȶxS0xS1б;
(2)xS0xS1֪ʱԷӼS0S1x=xiı룮
(1)xĹȻһֵֶж01ʾkÿһŵĹ01ʾ͵õһֵжǿʹQMԸ÷жֵ룮ʱһʾֵжһ״ֵ̬ӳʣȻֵĸʷֲʽ(1)еp(xS0|xS)p(xS1|xS)ڱ÷״̬Ӧĸʹֵƣ
(2)ʵȼڷӼϵ룬ʹõĸʽ(1)еp(x=xi|xS0)p(x=xi|xS1)Ȼһֵֶ룬ǿԼӼS0S1ֽɸСӼÿһεķֽǶͬ(1)һжֵ룮ڷӼÿֽһΣȶҪ٣һ̿ظֱӼĳȵ1Ϊֹ
ӦĽ뷽ʵΪ
(1)ȶxS0xS1н룻
(2)xS0xS1֪ʱԽõķӼS0S1xĽ룮һظֱӼĳȵ1ΪֹʱӼΨһxiΪ
ԳΪ8ķżΪQMĶ
ͼ1ʾһ8ŵĶṹÿһҶڵһ07ķţÿһڵһżָ߳ΪֵжԲڵʹQMжֵ룬ֵжķ֧0룬ҵķ֧1룮һŵͿöļڵQMֵʾҪԷ3б룬ڸڵ07żS07ֽӼS03S473S03S03ڶֵжķ֧ڸýڵ㴦ʹ0룮ͬڲڵ031ҷ֧S23.ڲڵ231ҷ֧ʱﵽҶڵ㣬żS3ֻһ3ʱڸڵ㴦QM0żS07ΪS03ţڲڵ03ǽ1żΪS23ڲڵ231ʹյõżS33S3еΨһţ3ǽ.

ͼ1żΪ8Ķṹ
׿ͼ1ÿһڵӦӽڵͬķ.ǳֽڵΪԳͶ.ȻеıʹöԳͶʹʲôʽĶӦþ.JPEG׼УıǷǶԳƵ.ھDCT任Ժ󣬱任ϵֲ0㸽󣬸ѸٱС.СϵԽ϶࣬ڱʱJPEG׼ֵСҶڵλڿڵĵطһСĲڵͷǳͣӶӿ˱ٶ.ԭıƳɷǶԳ͵.Ƕһ⣬ڱ֮ǰ֪ݵķֲ.Ҳ޷ȷһҶڵӦڿڵλ.ǽͨñĶƳɾԶԳƵĽṹÿһڵϵķżֽ㣺

(2)
дȡ.ֶԳƽṹıSTQMκʽѹĵͼƵ.
STQM㷨:

(1)InitEnc()ʼ
(2)FormTree(N)շżֽʽ(2)ΪγSTQMNΪżȣͬķӦʹòͬıñTS־
(3)Code(TS,Symbol)Symbol˳űӸڵһֱൽҶڵ㣮ÿһֲڵʹQMĶֵ뺯Code_0(S)Code_1(S)SֲڵģTSΪSymbolıģ
(4)Flush()ֹ룮

(1)InitDec()ʼ
(2)FormTree(N)γSTQMñTS־
(3)Decode(TS)TSӦıӸڵһֱ뵽Ҷڵ㣮
Զ׼STQMԶԻĽر룮ͬķͨTS֣ÿһַȿСͳģʽöӦıʾSTQMǷżرʣǽһи֤.
4STQM֤
һУ÷żָķQMĹ.ֹǷرԭǽ֤.
ŴkķżΪSһxiSkеĳָΪp(x=xi|xS)ôرԭڷŴkеı䳤룬Сƽ볤.ѱֻxiӦ볤Ϊ-log2p(x=xi|xS)ܴﵽ
ȻQMÿһxiıͨԼڵνQMõ.ˣֻ֤QM⼸ڵϵı볤֮Ծ-log2p(x=xi|xS)˵͵QMر.ǽԴ˸֤.
Ͻڵʽ(1)Ӧ׵õ


(3)
ʽ(3)-log2p(x=xi|xS)رڷxiżΪSʱӦ볤ʽ(3)p(xS0|xS)p(xS1|xS)ʾǷżSֽɵӼS0S1ĸʣȻ㣺p(xS1|xS)+p(xS0|xS)=1.ˣǼQMһ(ʵϣκܻһЩ)ôڵQMֵΪxS0xS1¼볤ֱΪ-log2p(xS0|xS)-log2p(xS1|xS).ʣµ-log2p(x=xi|xS0)-log2p(x=xi|xS1)԰ͬķֽȥдкڵQM볤ֱͣҶڵΪֹ.֤͵QMĴżر.
ͼ1ΪȻ


ڷ3رҪ볤õQMS07S03S23ڵʹõ볤֮ͣرҪ.
5OTQMĹ
ǽоͱ(OTQM)Ĺԭͷ.ǰۿ֪JPEGķǶԳƶṹǸDCT任ƵһٶŵıԣֻʺDCTϵֲص㣬.STQMͨıݶԽЧı룬ıٶҲǱȽϿģݱķֲﵽ.ΪʹֲͬݶܴﵽٶȼޣǱʹĽṹڱж̬ظı.ֿɶ̬ͽṹήѹЧʣܹﵽѱٶȣԲͬ;.
ȴоOTQMĶԭ.Ϊ˷ʱ䣬Ǽÿһڵϣκһζֵõʱ䶼ǹ̶ģһΪ1.ôκһŵıʱͿڱڵȷ.
ڷżΪ{x0,x1,,xN-1}ķӦĸʷֲΪ{p0,p1,,pN-1}űʱĽڵΪn0,n1,,nN-1ôƽʱͿԱʾΪоĿŶṹʹTֵС.
֤¶ݣ{p0,p1,,pN-1}{q0,q1,,qN-1}0pi10qi1Ƿֱpi=1͡qi=1ô

(4)
ȺųΪpi=qi,i=0,,N-1.
ǽÿniʾ-log2-ni(µĶĬΪ2Ϊ)ڶĹ㣬ͨʽ(4)֪

(5)
ҵȺų(ҲTȡСֵ)Ϊpi=2-ni,i=0,,N-1.Ϊʹʱ̣ÿһӦĽڵΪni=-logpi,i=0,,N-1.ҲűӦѭԭ.ǴʵʳOTQMĶ.
˵ni=-logpi,i=0,,N-1ÿһӦѽڵǽڵĸӦһһֻһŵı뷽
ҪԷŽ.ڽʱѾõ˷żĸʷֲ{p0,p1,,pN-1}Ϳ԰ÿŵĸʴӴС򣬾ķżΪ{xs0,xs1,,xsN-1}ӦķŸΪ{ps0,ps1,,psN-1}
Ӧмָ.jʹС0jN.Ȼ󽫼{xs0,xs1,,xsN-1}ֽΪ{xs0,xs1,,xsj}{xsj+1,xsj+2,,xsN-1}Ӽ.ϵĽӼϰͬķֽ⣬ֱϳȵ1Ϊֹ.ռϵķֽ̽ٶŵOTQM
֤Ÿʶ2ĸݵ£ƷԴﵽֵ.Ÿʲ2ĸݵʱ򣬴˷ֵѽ.ܹDCTͳص㣬OTQMƽJPEGƱһ.
ھıУQMӦı뷽ǿԱ߽߱ͳƣͨͳƽ̬صOTQMĽṹӦݵͳص.ڷƽݣܹӦӦݵľֲͳص㣬ﵽЧ.
ȻOTQMĶ̬ҲҪķһʱ䣬ǲҪÿһž͵һǿڱԽϳһԺٵһṹ磬ÿ2000źһعַʹõõʱԺԲ.һ棬ĵڱ˺ͽӦñֻܱ֤ͬڽ˵ȷ룮
רӲƶԣ̬߼ƺȽϸ.Ǹоܹ֪ĸʷֲƽȣԽƳɹ̶OTQM.ݷֲƽȣŸʲ֪ѡOTQMSTQMӦۺϿ.ʹʵ֣OTQMһֽϺѡ
6STQMʵ
QM֮ԱʹΪֻҪӼλ㣬ȫ˷ʱĳ˷CACM87иߵٶ.ͬʱıЧܹ96%ϣҲһĻԴﵽ.
ӦģSTQMÿһıϣֻҪһ㣬ͬ˳˳һ̶ϱQMĸԣÿһڵϽеĶQM룬ıЧҲܳ96%.
STQMͬQMӦͳƵص㣬ʹñݲֵͬͳصı仯仯ӦصʹQMͻصƣǷӦرı뼫ޣ
ı1ǱĵĶԳQMʵȽϵӦCACM87ʵȡһΪ19475644ֽڵͨDOCļǶԸļÿȡӶõӦСĸʵļ
1ѹ

żߴŴ(bits)Ӧ뼫(bytes)STQM(bytes)CACM87(bytes)
3194756441.243019302607420948091975054
9194756442.176346529821730628213152563
16194756442.702360657877534839083820366
24194756442.708569659389034515923953770
32194756443.029870737608337353114338500


ӱ1ʵԿSTQMıЧԶԶͻ˷Ӧļޣ˸ݾзƽȵͬʱSTQMıЧһ㶼CACM87бCACM87õӦ
ͼ2Сַ£ĵĶԳͱSTQMCACM87࣮ܶʵϣַĴСΪ2ʱSTQMCACM871ϣַС30ʱSTQMCACM87ٶȽؽӽҪΪSTQMҪĽڵַߴӶӴٶȻὥرCдɣʵPentium90лãųļӰ죬ٶȻһߣ

ͼ2STQMCACM87Pentium90΢ϵıٶ
ֵᵽף4еҲһ޳˷ĵSTQMٶϱȸĵķԺһЩͬʱƺҲַ̫ߴӰ죬ϵͳԴҪ󲻸ߣڸ߽ͳģ͵ӦãⱾȽõCACM87ƽٶȿԴﵽ200Ksymbols/sף4еCACM87ƽٶֻ20Ksymbols/s˴ٶȲڳŻɵģ
ڶԳQMֻõ͵ļӼλ㣬רӲƴ˼ķ㣮ͬʱӲĿɲԣʹԳɱٶȣҲһֻӲƵźرĽϺõѡ񣮵ͬʱҲӦרӲʵУQMҪάһ洢ô洢ҲռһоƬܵĳɱ޶ִۣ΢DSPУ˷ٶƺҲȼӷһCACM87STQMľ룮ѡ񣬻Ӧ
õȻѧصĿ(Ŀ69735020)863-2-4Ŀ͡Ŀ(ĿG1998030606)
߼飺ɣУ196912ʿоҪоΪģʽʶͼ
Ӿ
ʯƣŮ19368ڣпԺԺʿҪоΪģʽʶͼ
Ӿ
ߵλѧӾϢصʵҡ100871
ο
1William B Pennebaker, Joan L Mitchell. JPEG Still Image Data Compression StandardNewYork: Van Nostrand Reinhold, 1993
2Cleary J G, Witten I H, Neal R M. Arithmetic coding for data compression. IBM Journal of Research and Development, Commun of the ACM, 1987, 30(6): 520541
3Pennebaker W B,Mitchell J L.Probability estimation for the Q-coder.IBM Journal of Research and Development,1988,32(6):737752
4Ѧԣ . Сĸĸ. ѧ. 1997, 20(11): 974981
(Xue Xiaohui,Gao Wen.High performance arithmetic coding for small alphabets.Chinese Journal of Computers,1997,20(11):974981)
ԭյڣ1999-03-01޸ĸյڣ1999-04-28.
