by W. B. Pennebaker
`Jo~jPqeuUed 'j * Aq
`J. L. Mitchell
`Ileqol!Iq -1 P
`G. G. Langdon, Jr.
`'uop6uei "E *
`'jp
`R. B. Arps
`sciv '8 "H
`
`An overview
`\Ae^IAJOAO UV
`of the basic
`oiseq eit, Jo
`principles
`seldiouid
`of the Q-Coder
`adaptive binary
`Ai-euiq eA!1depe
`arithmetic coder
`iepoo 3!1GLU4flPU
`
`The Q-Coder is a new form of adaptive binary
`Azeu!q oiqeudpe lo uuo mou e s! Jepoo-
`04l
`arithmetic coding. The binary arithmetic coding
`Bulpoo o1ewqlW!e Aeuq e4tL -6u!poo oilemq1e
`part of the technique is derived from the basic
`oiseq et tuol POAIeP si enbtuqoo et# lo .ed
`concepts introduced by Rissanen, Pasco, and
`puB 'oosed 'uouessiti Aq ponpoiju! sideauoo
`Langdon, but extends the coding conventions to
`0 SUoI.UDAUoo 6U!pOo e4 spuaixe inq 'uopBurl
`resolve a conflict between optimal software and
`pus eiJeMOS leu.1do uoegApq joilluoO e eAIOSSI
`hardware implementations. In addition, a robust
`isnqoj e 'uof!ppe Ul suoi eue,,od,!
`8JeMpJeq
`form of probability estimation is used in which
`4014M u! pesn s! uogew!rse fAlllqeqwd ;o uuo;
`the probability estimate is derived solely from
`uo4 Alelos pOA!uOP S oSu!)se AI!qeqoid 041
`the interval renormalizations that are part of the
`0t lo tJd ea ze41 suoqezllvuuoWUJ l
`JIul 014
`arithmetic coding process. A brief tutorial of
`lo iepoln jepq V sseooid 6u!poo olotww4wqu
`arithmetic coding concepts is presented,
`'poeuessid s! sldeouoo 6ulpoo op Iu0qle
`followed by a discussion of the compatible
`elqpredwoo 044 jo uolesnos p e Aq pamollo;
`optimal hardware and software coding
`U!POo GJMUOjs pue
`IJMpJ84 ltu!)do
`structures and the estimation of symbol
`IoqtuAs lo uo!Bugso eq p
`u seiofnirs
`probabilities from interval renorrnalization.
`•uogezileJuwou8J ileluo woi; gotllqeqojd
`
`1. Introduction
`uoflonpoJIul "L
`The Q-Coder is an adaptive binary arithmetic coding system
`tuolss urpoo orputllm kmutq oAndepe ur si japooy aqr.
`which allows different, but compatible, coding conventions
`suoAuoo Ouqpoo 'olq.ledmoo
`inq iuoj Ujp SO
`lo'tt
`to be used in optimal hardware and optimal software
`lmtudo puu axa.pxq lvuw.ndo ut posn *q ol
`ros
`°Copyright 1988 by International Business Machines Corporation.
`'uo
`od.o"cS WuhPI ssungs 9mio[ En1rqR1 Aq 8861 li sgdo"J
`Copying in printed form for private use is permitted without
`inoqilv poi!murd s osn aeAUc1 xoj uuoj pnuud in Ru.xdo)
`Payment of royalty provided that (1) each reproduction is done
`auop s! uonnpoidai qo
`(I) Iml popAo.d Ag[eA jo 1ua .ed
`without alteration and (2) the Journal reference and IBM copyright
`1q2uJdow wqlf pum ouajoajai Ivumof oql (Z) pum uonoll
`inoql.!
`notice are included on the first page. The title and abstract, but no
`ou vnq llsquz ptm an a.L "_ad IS.g al. 0o papnlout am 2opou
`other portions, of this paper may be copied or distributed royalty
`Aij ow panq imsTp jo po!do oq Acm jaded sndi jo snuoriod ni~o
`free without further permission by computer-based and other
`nqo
`pm pgeq-tnndwoo Aq uo. sqtiad ,otlpnj inox.m
`ij
`information-service systems. Permission to republish any other
`jotlo Am qsyjqndaj ol uosmauj
`"swmdss aa1Ant-uo1iuuoju!
`portion of this paper must be obtained from the Editor.
`"jolqrg otp uxzoj poupnqo oq isnw jaded srql jo uopriod
`
`implementations. It also incorporates a new probability-
`-Apqvqoid mou le souiodiou
`osle l -suoiwpxiutuaduji
`estimation technique which provides an extremely simple yet
`ia, aldutts Alotu-nx uc sap.Aowd iqo!qA% nb.uqoal uo.nsw
`robust mechanism for adaptive estimation of probabilities
`s.4T.qqqojd jo uors
`o^A.dvpeds .xj tustustooup msqo.
`during the coding process.
`•ssoood uqp ot 2u.np
`This paper presents an overview of the principles of the
`oql Jo saIdpuud oqljo m omAZo ur nuoswid jaded s.q!J
`Q-Coder. A brief discussion of the basic principles of
`Jo sld.upd tseq oql jo uossnoslp Jolq V "po-
`arithmetic coding is presented in Section 2. A discussion of
`jo uo.ssnossp, V "Z uoTnoS Ut poluoswd s ButWOo OrntuqDuS
`the coding conventions which lead to optimal, compatible
`olq. cuoo 'rmundo ol peal lipqA suonauAuO3 2u.poO Ot
`hardware and software implementations of arithmetic coding
`lurpoo oiutu .pe jo suo
`tuooldut anxiUos pus
`tAmpisq
`follows in Suction 3. In addition, Section 3 introduces some
`outos saonponu £ uoraS
`'uo~nppe UI "E uO.oS U! SMOflOJ
`aspects of implementation using fixed-precision arithmetic.
`"o
`tnlun uoz.oaid-paxg Su.sn uonvtUtmoldm!jo sloodsu
`Section 4 covers the estimation of probabilities by a new
`ma u q saneuT qqodjo uonwzs
`0 iJ~ SJOAOO t, UOr.PO
`technique which uses only the interval renormalization that
`Iql uoquzfuuouaI feSmA t o Al lUO sosn pqMo onbmqQ
`is a nft-Prsnry part of the finite-precision arithmetic coding
`Su.poo opatuq.u uo
`zstd-mmuq atq jo ud Axessoou r s.
`process. Dynamic probability estimation makes the Q-Coder
`napoD-b atD samum uoutmunsa Ai.qiqoid otruuXAG -ss~oo.d
`an adaptive binary arithmetic coder. Section 5 gives some
`owos sa.2 g uo~r ".poX 3fl~u4).-i
`nApdqpm ue
`,£xu~q
`experimental results.
`• slnsa. Ie~mupdya
`2. Basic principles of binary arithmetic coding'
`OWetuDuJ AJBu!q ;o seldiou!d l!seg "Z
`BU!POo
`Traditionally, Huffman coding [2] is used to code a sequence
`oouanbos u opoo oq posn s. [Z] Su.po ueaUnH ',TIReuOUPIPI
`of symbols which describes the information being
`2ui~oq uoumajojul oiD saq.
`p qo.qM SlOqtuAs jo
`compressed. As an example, Figure 1 shows a possible
`1q!ssod e s~oqs 1 ajn !_
`'[Iduica us sy "x-sudio3
`Huffinan tree for a set of four symbols—w, x, y, and z—
`-z pue 'A '
`'---soquIAs .n, jo Joas v .1oj an uuJnH
`with respective probabilities 0.125, 0.125, 0.25, and 0.5. The
`aqLL "O put 'SZ'O 'gZ "0 'r 1,O sonq!qsuqoid a^.noodsa1 ql.A
`vertical axis of Figure 1 represents the number line from 0 to
`o 0 iUo.j OUIl nqurnu aql sluasajdr 1 aa .i_ jo sIXu l r ^A
`1, which is the probability interval occupied by the four
`.noj oql Aq po!dnooo
`Iuolur X.spqiqojd oq, si qoit, 'II
`symbols. Each of the four symbols is assigned a subinterval
`resAIuqns e pm Sye si sloqtAs .moj ot jo qog
`"stoquL~s
`A much more eciensive tutorial on arithmetic coding is found in
`"1) u! pamv
`s
`B IUT1p--
`Do
`pniJ Vi
`
`717
`
`IBM I. RES. DEVELOP. VOL 32 NO. 6 NOVEMBER 1983
`I w
`"IoA AaOMI 's
`E
`"AON 9 'oN
`9s61 'd39
`
`siwv v -w OaNv a
`W. B. PENNED...KER., J. L. MITCKELL, C. G. LANGDON, IL, AND R. B. ARPS
`'NOwrIl "O "o TrmiaiJ "1 "f 'wxNN3d
`g A
`
`BEST AVAILABLE COPY
`AdOO 318VIIVAV ±382
`
`Unified Patents, Ex. 1018
`
`000001
`
`

`

`Binary
`Symbol Probability Code fraction
`uo!2-ej opo &Ilqeqozd
`loqtuAS
`
`0.5
`
`0.1
`
`Y
`
`w
`
`St.0
`0.25
`5zl-0
`0.125
`5z 1,O
`0.125
`
`t0
`10.0
`01
`0.01
`0.001
`001
`100*0
`t00
`0000O 000
`0.000
`000
`
`The tree in Figure I is constructed in a particular way to
`01 ft LZtlflotImid U u! p02lz1uisuoo St I a311 Jut 0031 04j
`illustrate a concept which is fundamental to arithmetic
`aj10tuiqt 01 ol uoWuipulj S st 114Mt idouoo Us 21wiIlT
`coding: The code words, if regarded as binary fractions, are
`j! 'spiom apoo atuj guqmo
`wI suop0ujJ Ajuutq sit popn~o
`pointers to the particular interval being coded. In Figure 1
`3 J14ul pwO 2utq juit0ut .zitnotued otp 01 SJinuiod
`the code words point to the base of each interval. The
`041 *[CA-J01UI 40t0Z JO aSitC) *04)01 iUTiod spio. apoo i
`general concept that a code string can be a binary fraction
`u0opt3I f~uutq Ua oq dUO 2uuls 2poo U jvll 1dodum fmuI0U
`pointing to the subinterval for a particular symbol sequence
`oouonbos loqtusmltnonlut v .103 1U!A11utqfs 041 01 gunutiod
`is due to Shannon [3] and was applied to sum-ssive
`aArss000ts 01 pQrdde SUM% puu [El uouuu4S 01 anp s!
`subdivision of the interval by FBAs [4], The idea of
`JO tOp! DU13 t'] S-114 Aq TBAJ0IUl 04130' uomSATpq1
`arithmetic coding, derived by Rissanen [5] from the theory
`Auooqj oqi ruoaj [g] uourritsrd Aq poAuap 'luipoa ojyyatuyku
`of enumerative coding, was approached by Pasco [6] as the
`241 set [91 oosed 4Cq poeoxdde SUM "Sur. oo oA!IuJuinluojo
`solution to a finite-precision constraint on the interval
`1 oiuoflUos
`IUA.101U! 04) UO JUTU.ISU0 U0l1lZald-olruU
`subdivision methods of Shannon and Elias.
`.143 P.
`.0U4J SPqiU u05
`pqns
`Any decision selecting one symbol from a set of two or
`.zo oAIIjo 105 v tUotj loquiAs ouo gap l~os uois!toop Auy
`more symbols can be decomposed into a sequence of binary
`aq una sloqutAs a10tu
`Lrtuiq 30 2ouanbas LU olul poduop
`decisions. For example, Figure 2 shows two possible
`o_ dsu-ts-oo,
`ojqlssod oma SMOqlS Z amgg 'oldtum=
`decompositions of the four-symbol choice of Figure 1. From
`ui-4 *I oxng_4jo otpq loqtuAs-.Inoj oqt jo suolilsodrUoooP
`a coding-efficiency point of view there is no difference
`23uoiojprp OU S5101041 MaA JO JU!Od XZUoioqp1uZ poo
`between the two alternatives, in that the interval size and
`PU13 aZIS UAIM1U a41 Imp u! 'S*Art'W.0jT9 0MI 20 U22Ml0q
`of size proportional to the probability estimate of that
`position on the number line are the same for both. However,
`(n IgUUot)1doid azts jo
`'AQOAMOH qloq i03 Otuie tD am uq
`iUmpjo n~ui!=SOdquqoid
`iU~ sqxunu 2qi tro uontod
`2t
`symbol. If each subinterval is identified by its least or base
`from the point of view of computational efficiency,
`'fbuapqja jcutorUIflduao 30 moiA ja 1u10d 041 tuojj
`osgq -to ISUoj st Aq pogpuop! s! Ie~iioiutqns qmj
`-IoquL~s
`value, the four symbols are identified respectively by the
`decomposition (a) is better. Fewer computations are required
`paxinboi am~ suo~1l~ndmoo io~p_4 *.iomoq S! (rt) uomspodmooop
`OtP Xq kAtI3~XSS0J p0of1uop! weU sjoqtutn
`otp0 041 0luA
`binary numbers 0.000, 0.001, 0.01, and 0.1. Note that the
`to code the most probable symbol. Thus, although the
`941l impf MONt * 10 Ptm '10,0 'locYO
`'oooo
`sjaqtunu AnJuiq
`041 qgnotiru %-nri *oqwuAs olqeqoxd IsOtu aj 2poo 01
`Huffman coding tree is not required to achieve efficient
`subinterval size (or probability estimate) determines the
`IU010 0 *A0I43= 01 poinbQJ iou s! =n1 Su!po0 uvutJglH
`far~ AiqqO-d .zo) =!s jUruolutq
`oto soutiuop (01epa
`compression, it remains useful as an approximate guide for
`length of the code word. Ideally this length for some symbol
`303 opplS *wuxprO.xddu ur sv [rnpsn supsui 11 luorsswdido,3
`loquvs QWOS 303 qlual su. p ,ll7apI -pjoA%,poo a4130 4jguol
`a is given by log2pe(a), where p,(a) is the probability estimate
`minimizing the computational burden.
`-uop~mq Inuopnndtuoo oqj ftiz~uirujtu
`lpqeqod otj1 S! (z4d =xoq& '(ofcIo
`Aqtlr2
`ois
`In general, as coding of each additional binary decision
`for symbol a. Far the example in Figure 1, the probabilities
`uoilpop Aniuuq juuortrppe qoiojo 2tpo
`sop~p~q~eqoid oth 'I I IMAr u! oldmexao tfl Ioq v jOquiAs ioj
`Upuo
`u
`have been chosen such that the code lengths are iriPal
`occurs, the precision of the code string must be sufficient to
`tions umso uwq *ArM
`1Upi amU mvuo opoo o1 ip
`01 wauoiins oq smm gums opoo otp jo uosTo.d 0q, &&msooo
`
`Example of a Huffman coding tree.
`!ipo guH jo "dm
`--a! n u
`
`0.1
`
`y
`
`10*0
`0.01
`
`100,0
`0.901
`
`000,01
`0.000
`
`0
`
`0
`
`(a)
`
`y
`
`j,
`
`0.1
`
`100
`0.01
`
`100,0A
`0.001
`
`0000o
`0.000
`
`0
`
`00*
`
`(b)
`
`'i;figfiaiir#:?:•;i5a;gfzif;tat5.2,03,-Ail,lisfi7.1trite-Pgavo-4:1,);eizge01164.14.4.011E-..geig-i:-.3g,14;730.4.0iii114.:41tzt1Wit13
`ZMA
`Two examples of decomposition of a four-symbol alphabet into a sequence of three binary decisions: (a) Example corresponding to Figure I.
`aingi oi ff uipuodsa-uo:) oldwT!yg (u) :suoisp Dp Ajuuiq awqj jo amonbas in olui )oqvqdpi loqui4s-inoj c jo uop!sodwo=p jo sajda=2 oA%,L
`(b) Example showing the most probable symbol encoded as a succession of three binary decisions.
`*sUoispapp Ajeutq 2amp jo uolssamns u su papo3ua loqwAs alctectaid now atp guiAoqs DjdUMg (q)
`f:V4:6tv:itVVs:i•A-fr; A'tiggr4;Att,,:gaZxiz4t;V.V.
`:t'zekWTf.,2-f*AV-eZa,tii:ff
`PiagfigV6:f.%teagig;-glt
`
`718
`
`vUUNIa3aA%.
`
`'t
`
`-d aNY -at iwomvi 0 ~o 1-rnat -i
`
`W. B. PENNEBAKER, 3. L. MITCHELL, G. G. LANGDON. JR. AND R. B. ARPS
`
`ONtE OA m~~a ss~ ~ uzsa1IY 'a
`516 ~3N~AN
`
`IBM 1. RES. DEVELOP. VOL 32 NO. 6 NOVEMBER 1988
`"61
`'839MAON 9 'ON ZE -IOA
`'JO-IaA3G 'SHU I MI
`
`Unified Patents, Ex. 1018
`
`000002
`
`

`

`provide two distinguishable points within the subinterval
`juAmoautqns oq uttpAt s1utod ojqeqstn2uilstp oml op!Aod
`p(s) allocated to the sequence of symbols, s, which actually
`AWemov qo 4q,
`'s 'sloquiAs jo oouonbos o41 ol polmOli
`(i)d
`occurred. The number of bits, b, required to express the code
`apoo aq =soidxo O po0Jal bu 'q 'sllq jo iaqwl nu oqjL "p0una
`string is then given by [3]
`[E] fq UOALS Uq St 1U1S
`
`4 > 2°p(s) a 2,
`'Z Z (,v)alz < t,
`which can be rewritten using the left inequality as
`se Ahrfnbout IjOl ,p gursn uoaluMO o1 u03 qorqm
`
`b < 2 — log2(p(s)).
`• ((v)d)Soi -z > q
`
`~:oq-.S
`O'!
`
`Ia
`
`1
`
`"
`
`etc.
`
`Example of Elias-type coding on string M L L M.
`d~ulgjo
`ouxa
`l~s o
`u
`o
`io
`gu~s
`
`After many symbols are coded, p(s) becomes very small,
`'luus AOA s3cooq (s)d 'popoo am3 sloquts Aueui .oUV
`and the code-string length required to express the fraction
`uo
`j oq sSOzdxo o poj!nboi qiSuo guuis-opoo 0q1 pur
`approaches the ideal value of — logs p(s).
`so -jo onlYe Mopj 04 soqom0ddo
`(s)d
`An example of Elias coding is shown in Figure 3 for the
`s! lu.poo sqg jo oldumoxo uv
`o411oj E an2I ut Uoqs
`binary decision sequence, M L L M, where M is the more
`0.o1 oq si N oq0m 'N
`-1 II 'oouonbos uoistoop Altumq
`probable symbol (MPS) and L is the less probable symbol
`loquaAs olqeqoid ssol 2ql 0 .I pus (SaW) IoqwAs olqtqoid
`(LPS). The interval subdivision in Figure 3 is a
`v s. E ajn2g1[ u! uols.A.pqfns
`oaiut o
`"(Sj-)
`generalization of that in Figures 2(a) and (b). The interval
`u! 1m jo UOITZ!IWOUOS
`fOAJl~Ut oqj (q) pur (u)z s=n9n
`subdivision process is defined in terms of a recursion that
`imp uo0s013u- jo s,,,,0 Ut poutop st ss=0-d uoismxpqns
`selects one subinterval as the new current interval. The
`ot so IrAxouq ns ouo sIlS
`oUj -.nA3lu! 1uano A%=
`recursive splitting of the current interval continues until all
`1no 01 SurlIdS 0AD^!fl0n=
`0l*
`u
`lit Inun s0nu1uoo
`decisions have been coded. By convention, as in Figure 1,
`'uoInuoAuoo AR "popoo uooq OA0q SuoIS. op
`' orilA u! s
`interval added by the encoder, after decoding a given
`the code string in Figure 3 is defined to point at the base of
`umA.g v Ru8pooop 1o13 '.0po300ou Aq poppu roiuo ui
`jo 0004 ot j0 1u!od o pougj0p si E an
`u! Su.s opo3 0q
`symbol. The code-string remainder will be smaller than the
`the current interval. The symbol-ordering convention is
`oq urq0 jofpiWs oq WrAkopuimowa 2uu -opoo oqL "joquiAs
`si uoIIuoAuo3 guuopo-loquis aq.u "IAJmui luoj.mo 041
`corresponding current-interval measure, since it is a pointer
`adopted from [7], where the MPS probability estimate, P., is
`'[L] tuolj poldopv
`"! 'd 'OlOetUIso Al.rxqod J
`'019,00nse0! 1o1u.!-uaLo gutpuodsauoo
`joluod -a Os 1!u.
`aqj 11qA
`to a particular subinterval within that interval.
`ordered above the LPS probability estimate, Q,, in the
`IVAMI01U impa U!At~ fOAjluiqns bo[03il.3d v 01
`041 ux '7 'ovwuuo
`.as.qoqoid Sj'j 1I OAoqg poaopio
`Renormalization then keeps the precision of the arithmetic
`current interval. The translation of the 0 and 1 symbols into
`o.punmq .oijlo uo.sooicd 041 sdwij uotp uonrzqwoua-
`o0u! SlOqULs I puE 0 04
`jo uo1uans00 o.I, "IAiju! uu mL3
`MPS and LPS symbols and the subsequent ordering of the
`operations within the required bounds. Decoder
`0poo0G "spunoq pownboi oxn ux.lIm suopnodo
`oq jo Suuopio 1unbosqns 0ip pun sloqmiX S
`put SdV4
`renormali7Ition must be the same as in the encoder.
`MPS and LPS subintervals is important for optimal
`oq lsniu uonozijomjouai
`• opooao oqi u! se au050
`luunl.do -Toj iuhodix s. sIuA£0lulqns &n pur SdW
`Another problem to be resolved for implementation in
`arithmetic coding implementations [8].
`u uoninuoutIdu. £ol poAosw aq 01 uiolqojd 1j4 1O0y
`"[8] suotluouUoldxtu 2utpoo opromq.m
`fixed-precision arithmetic is a carry propagation problem. It
`After each symbol is coded, the probability interval
`loqmAs qo0 JoUV
`AJrutk AlqP.qo.td 4l 'popoo s.
`11 "uaoqCUd uojwrodcud Aut le s. opomquo uots.owd-poxt
`f
`is possible to generate a code string with a consecutive
`remaining for future coding operations is the subinterval of
`JO fOA.3Olulqns 045 SUOjado Surpo3 .n9njoj gu t utuoi
`0
`I1M~ZJS 2PO3 0 1OJOUQS 01 Ojq!SSod S!
`oAr13U0
`ognoosuoo v q." g .sapoo
`oo
`q
`.
`the symbol just coded. If the more probable symbol M is
`sequence of 1-bits of arbitrary length. If a bit is added to the
`st W loquiAs olqeqoczd wo.Ou oqll *popoo 150f ToquxAs 041
`otD ol poppe S j1q e3 "qtutol Axos!qq jo sljq-I jo onbos
`least significant bit of this sequence, a carry will propagate
`coded, the interval allocated to the less probable symbol L
`oleggdoid IvLtaMA=uo
`'oouonbos sopjo u'q juis~g xuis so
`'popoo
`,I loqaAs olqtqo3d Sn1 oq o po lOolle uA0u! o4
`must be added to the code-string value so that it points to
`until a 0-bit is encountered. Langdon and Rissanen [8]
`0 SuTod 1' 1041 os OnlO SuLIS-0poo 041 o poppe oq 1-nm
`[S] uauvs!" puv uop~m'I "paunoouo st i!q-O v plan
`resolved this problem by "bit stuffing" If a sequence of 1-
`the base of the new interval.
`-1 Jo oouonbos a34 ,,UP1 -iv!q,, Xq wlqoid sM poAIo s
`•A2JUx , Ou 0l jo o"s0 0q
`bits of a predefined maximum length is detected, an extra 0-
`-0 inxo ug 'Vpopp s! 41uoI 1umuptu pougopowd 13 jo sxq
`Arithmetic coders such as the Q-Coder avoid the
`041 p!0oA .P3OpD-)o 04 1oqons 0 poo 3o otl4.UV
`bit is stuffed into the code string. The stuffed 0-bit acts as a
`increasing-precision problem of Fling coding by using a
`P I!q-O peffnts o, L u.qs opoo oq, olu! poS s
`o su
`s! ,!q
`v 211SO Aq fuipo3 se1 jo tuolqoid uo.s.ooud-2u.woiut
`carry trap for any carry from future coding operations. The
`fixed-precision arithmetic. implementation in fixed-precision
`oql .suopiIodo Su.poo 03n0 u0o0j Aimn Aue ioj dun Aim
`uo.iooid-poxu ut uonouousotduLi ",jonu-q0.p uo.isild-poxg
`decoder, after detecting this same sequence, removes the
`arithmetic requires that a choice be made for the ftxed-
`otp soAm
`'oouanbos oumrS si.p ft1op
`'xopooop
`1o0
`-poxy 041.1j opera oq aoooqo e I0,p sw!nlboJ mo011p1.0
`stuffed bit, adding any carry contained in it to the code-
`precision representation of the interval. Then, a
`-apoo 0q1 0n U! pou.nuo AIM Aug gu.ipn Ihq pOms
`0 'uoUj "0uAJ ! *tpjo uo.inuosaid uosi.1d
`string remainder. The Q-Coder follows this general scheme,
`renormalization rule must be devised which maintains the
`omtoqos puuo suP SMO4OJ .osPo3Z) OqL -£opuromw su=u
`0q4 sum u 1 qo.1m posop oq isntm oltu uo1zfuuWouai
`but with the additional constraints that the string of I-bits is
`interval size within the bounds allowed by the fixed-precision
`51 s~q-
`o J Sugis
`I~ nq
`ppuOISO t0U)p 41
`su1m4
`uotiod-poxg a0 Aq pomOljj spunoq o04 unrqw ozis lololul
`representation. Both the code string and the interval size
`eight bits in length and is byte-aligned.
`•pouj!-0lAq s. put; qlf-ol un sj!q lqg.o
`Sl
`llOt1
`4 410
`2O)
`0=!5 jAJMV! 041 PUB05SU=)
`One final practical problem needs to be resolved. In
`must be renormalized identically, or the identification of the
`043 Ol03gU p 041 £0e 'Afuonms
`15010uomus~d
`ppozioo oq
`ul "poAlo= oq o so00u ualqoid nowd pmi ou0
`otp jO 'k [pnuopz pm .utuouai Oq! isni
`oql jo uonwquop.
`general, arithmetic coding requires a multiply operation to
`code string as a pointer to the current interval will be lost.
`01 uopodo Aldrni0 sunb01 3upoo 3bai1.u0 'BUuT
`isol aq Him IEmAIolu lu ,o
`0q0 ot -olutod c se guus opoo
`scale the interval after each coding operation. Generally,
`Efficiency of hardware and software implementations
`suonmuwouotdtui 0omn os pue oImp.mqj fou1o3q~
`multiplication is a costly operation in both hardware and
`suggests that renormalization be done using a shift-left-
`puv aremp£ qioq a! uowiodo Apsoo n si uotlo.xdnliu
`-1A1-Ils v Sus-n ouop oq uollvztleuuouoi mp smgns
`software implementations. An early implementation of
`logical operation.
`jo uoiuoruolduq Apnu uv Suo liuomolduq WUMaos
`"uotgmdo Iw.gol
`adaptive binary arithmetic coding avoided multiplication [8].
`The Elias decoder maintains the same current-interval size
`'[sI uot
`!ld.nw pOP0Ae RUrpoo
`OAndn. umq OpO
`o09005 SuItMUMO 12pOOOp sirn 04
`oz2s [0A-OI!-lut-namno
`However, the Skew Coder [7] uses an even simpler
`as the encoder, and performs the same subdivision into
`'IOAOMtOH
`.rojduats UOAO n0 sas5n (L] QPCO A3zAS 01
`omu! uosiAqjns o0r1s Oxp suuod
`0q se
`pue 'Jzpoouo
`approximation to avoid the multiply; the same
`subintervals. The decoder simply determines, for each
`amins 0q4 "Afd lini zip ploAr o uoillouidds
`q4r0 oj 'sou!tu.mlap Ajdms iopooop oqj, "soiAjujqns
`approximation is used in the Q-Coder. If renorinalizations
`decision, the subinterval to which the code suing points. For
`suorQ .UuUooU Ji ' P00 01 u! uyps s! uonetiutoddn
`10 _su!od SUM3S Opoo OL Q31"M 01 foAlolu.iqns 0q
`'uorstop
`are used to keep the current interval, A, of order unity, i.e.,
`finite-precision implementations following the coding
`"'o! 'Xlun .iopo jo 'V 'I
`u 1uaujno atp doo ol posn oue
`2ujpoo oq, 2 u oloj suonmuooldtu, uos.3d-ojiug
`in the range 1.5 > A z 0.75, the multiplications required to
`conventions above, however, the decoder must subtract any
`Aug iooxiqns Ism11 1apoop 2ot 0 'aOAMooq 'oAoqu SUorI00AUOO
`ol poamboa suopedpmm
`041 'xL'0
`-I aguwuo3 at x
`
`0
`
`OI!
`
`"Sod "I
`"dO13AO
`9 *ON Zt "1OA
`9861 lIl gRAON
`IBM J. RES. DEVELOP. VOL. 32 NO. 6 NOVEMBER [988
`
`W. B. PENNEBAKER, r. L MITCHELL. 0- 0. LANGDOK SIL AND a a ARM
`saw Y
`-s aY nu 'NoaoNV1
`'o 0o -TFlH),iP -11 aV3NN3d 9M
`
`719
`6GiL
`
`Unified Patents, Ex. 1018
`
`000003
`
`

`

`Aluo uotiLztitnnb iiq-Zt
`
`Cl-
`
`proppe hAiunutA !q -
`
`08*0
`
`0.08
`
`0.02
`
`0.00
`
`z'
`
`2
`
`4
`
`9
`
`6
`
`3. 0 -Coder hardware and software coding
`Suipoo GIsmIJOS pUe aisrplell Jepo3-O "S
`conventions
`qUOI1ueAUO0
`The description of the arithmetic coder and decoder in the
`otl ut iapooop pun 10po3 3otuq!-1s u
`jo untdpasp osqj
`preceding section is precisely that of a hardware-optimized
`pozluirjdo-a=A~pxnq ejo lsip Alosmwi SI oposST po
`implementation of the arithmetic coder in the Q-Coder. It
`uses the same hardware optimizations developed for the
`01)1 103 podolaop suoliwzx)1oanmus
`ms
`p O
`earlier Skew Coder [7]. A sketch of the unrenormalized
`poz4tgnaiou0Juf 24130 433i031S V ILI
`-t000O)S 101[m5
`code-string development is shown in Figure 5(a), and a
`v )1m
`'(Ns an1811 Ul UM~o4s St
`lUalnd010AP Suuis-apoo
`sketch of the corresponding decoding sequence is found in
`ui punoj st oouznbo;s 2nipoaap Surpuodsasuoo 011130 ipioIs
`Figure 5(b). Note that the coding (and decoding) process
`ss30od (gu"poop pun) SuTpoo an1 1511) aoON *qi)S ajmgv,
`requires that both the current code string and the current
`luomnoI 041 puu Sus
`0)103 iu0.ufl otp ioq imp1 swInfbwl
`interval be adjusted on the more probable symbol path. On
`no iT1zd louk olquqoxd aiou otil uo poisnfle aq ISAjoluT
`the less probable symbol path only the current interval must
`Isnux 15A.101ui luwa-rop Ajuo qlvd loquix(s ojqeqocxd sso 2up
`be changed.
`*po2ursp aq
`The extra operations for the MPS path do not affect
`I303jo IOU op, ipud ~,Sd 2tD .10 suozwodo siixo oqj.
`hardware speed, in that the reduction in the interval size and
`puu azis [SAizlu! 041 Ut uo1)3f)10 o415
`'tpoods aJmmpinq
`Imp
`the addition to (or subtraction from) the rids string can be
`oq um 2uns 0)103 op (woijl uoniosxqns 10)0 oluor1P1
`041
`done in parallel. The illustration of the hardware decoder
`.10)1030)1
`pm OIS)15i 04)3 uo[1.3tgu1m 01 jofllmd ni ouop
`implementation in Figure 6(a) shows this parallelism.
`tu1si101111.1d sup sm08)s (t3)9 oinS'tj ut uor.lluouboldsua
`However, this organization is not as good for software.
`01MU0S 103 P005 SU IOU ST UOnlSZ!UUlIO 511 'IOAOAOJ
`Having more operations on the more probable path, as seen
`noos su 'qled olqrqoid woo oqs no sunpsido asoi SUp~vH
`in the decoder flowchart of Figure 7(a), can be avoided.
`*PPOUoq =15 'U)L aznSj
`)J UrMOUj 10)1030) 08)1 i
`Coding inefficiency as a function of log,(q), where q is the less
`ssol o st b oji/ '(b)t
`Software speed can be enhanced by exchanging the location
`Lol jo uoiiounj z ses £lUpIutu
`gulp03
`uo~isool 2tR 2tu!Suvpxo Aq poomuan oq uno poods am1J0
`probable symbol probability. The solid line is for the 12-bit integer
`.io~oiut iiq-Zj otp.3oj st ouil pijas *U
`-A(ijlqsqoad loqwAs
`Iquqoid
`of subintervals representing the MPS and LPS. As illustrated
`pOIUI1SflI p
`scn -SIpu SdyN :1)l RulIu~swdwi S)SAJluiqnsjo
`The dashed line shows the effect of restricting
`representation of
`2UjIjUSW u 10 ~J O" SAO4S Ousj poqsap 24jL -li
`jo uotouoswda
`the set of allowed Qe to the values in Table 1.
`1115d 21qtqoid w10ow 041 u0 su0T)31)su! 0111
`in Figure 7(b), the instructions on the more probable path
`I 2lqLW ul sIOnlgA -afl 01 "j
`JO JS Qt4I
`jlPO[011
`'(q)i. a'ngi u!
`are reduced to a minimum and, instead, more instructions
`suopzmIIXsuT 010811 'prom!11 'pusn amt
`rU1IUU 501 p03flpoi as
`5)1)1IMP 1))ON 41qld ojqneqcrd ssol 0111 no popoou ans
`are needed on the less probable path. Note that this
`organization gives slower hardware, in that two serial
`)SU2S
`0MI IMPf UT
`'QXUSMSII OS SOAIS UOtj9Z!UV&0i
`arithmetic operations must be done on the LPS path [see
`oos1 tped Sa-l au no aaop oq isnin suoinsuio 3110W41U5
`Figure 6(b)1. To decode, first the new MPS subinterval size is
`St ozis jr-Ailu~qns Sdyw m~ou 011) WU11 'opOrp ojL I(q)g antlig
`calculated, then the result is compared to the code string.
`SuuxIs apoo o14101 posdsuoo s1 ll
`01)1 u01)1 Mp)ln)p
`If the choices were limited to the two organizations
`suonuzsuegio om4 )
`ol10 pQI)1UilOM 5030i) = 01113)l
`Both the code string and the current interval are periodically
`Affeonpopod ass ~sIv~ui luwuno atp pun Sus
`sketched in Figures 6 and 7, there would be a fundamental
`e
`apoo au p
`imeuounpunj u oq p)fl0M 01041 IL puv 9 s0IflSIa Uq pq101
`renormalized such that the value of A is in the desired range
`oftri pox~p, oqp ut si yjo anm~ *qi 15111 spus pomt1vufluou
`conflict between optimal hardware and software
`o=i&los pun asn, apssq )5su1do uoovqoq Ionjuoo
`relative to Q. for the next derision. The true interval is
`s! TruAolul on atL -u0oSp39
`Ixoa oql -103 'o 0 aAnISIO1
`implementations. However, there are two ways to resolve
`Oa)OIos 01 SK"M M ON4 we1) at'IOAOM'OH SUOIluOWO~dUI
`obtained by scaling A by the current rtnormalbation factor.
`*iomnj touonzsquuouax luano *q Aq V' gutgms Aq pgaumiqo
`this conflict [9]. First, it is possible to invert the code string
`suunS OP00 01)1 IJAUI 01 olq~ssod St
`1T'ST
`611310WO SUP
`The idea that A should be kept in the range from 0.75 to 1.5
`5 1 01 SL0O UJtU 2SUW. *ql u W03 dOq Pln~up y IMl VON OU
`created for one symbol-ordering convention, and achieve a
`1B *Aaiqo35 pu- 'uoT2UOAUOO guuopio-joquiAs 2uo 103 PQIVW
`is due to Rissanen.2
`loeU01 otlp S!
`code string identical to that created with the opposite
`altsoddo oil ip)AS )10150. Iml 1
`rtap g511!)T US 0)10
`A calculation of the instantaneous coding inefficiency
`Kamu~ijout guqPo snoaiunSsuz mafl3 uo12SelnoU V
`convention. A second (and simpler) technique uses the same
`atuns at sasn anbiulpom (.zo~dUrp pun) puooosV'U011U2AUO3
`introduced by this approximation is shown in Figure 4. The
`QtL t amalj ul uMOq4ST ~UOnvUlnxoxdd
`snp Aq poonpoiw
`symbol-ordering convention for both hardware and software,
`aism~lj0s pug =XmpJmq qioq 103 uo1)uoAuoo Supopio-loqwAs
`abscissa is a log scale of the true (not the estimated) LPS
`san (poltunso otp iou) onn otp jo alros gol 'a st =npqu
`but assigns different code-string pointer conventions for
`.101 SuOt)U2AUO0.titqo~d guulsSop03 luoiOJlip stI2TsS inq
`probability, q. The ordinate is the coding inefficiency relative
`*Anqwja A.buouuptzm Surpoo otp S snii
`u uo, ot *bIpqqi
`hardware and software implementations. The code-string
`asmmjos pun wvt~pxsq
`ouiL -suoniquoamIdi
`guuls-opoO
`to the ideal code length, assuming that the best possible
`ojqtssod lsoq *t qi
`gutass 2UUI'qtluol op0o
`I5mpl otu o
`convention shown in Figure 5(a), in which the code string is
`integer value of q is selected. The coding inefficiency is
`S! Aaui U olqjt BUTipO3 otLL pvws si b lo an
`1.Wut
`pointed at the bottom of the interval, is used for hardware
`WgAM)1154 .101
`)1osnl WA-tjutu oijo wjoloq oqp le p.olulod
`dominated on the left side of the plot by the approximation
`uosgruxodde aip Aq bild orpj o -a~ Ija owi u polwutaop
`implementations. However, a different code-string
`Sw4-opO 101.p
`z 'IOaOmoH S013Us'lUT
`to the multiply. On the right side of the plot, the coding
`convention, illustrated in Figure 8(a), is used for software. In
`nl assmljo p103 sl '(Yg)g
`oaM21A Ut MP015lnp
`'UOftUIMU00
`inefficiency is dominated by quantization effects. The solid
`PnIOS OEu sp
`uopis74um~b Aq pnutuop si Aoluomgjou!
`this software code-string convention the code string is
`s! ftUIS 0)103011) UOIaUaAUOO 2U
`IS-Op03 OISM1JOS511
`line gives the coding efficiency for the 12-bit integer
`1m2m1ui! q-Zi aEpxo10 kouato a SuTpoo o1q1 s~amg aux
`pointed at the top of the interval. When the software code-
`-apoo anA%)Jos 01)1 =qfM 15ea.0u! otfljo dol otn li poitulod
`arithmetic precision used in the Q-Coder. When the allowed
`poonv zq uarzM -ipo~-?
`:tp ut posn uomsiad optuxqiun
`string convention is followed, coding an MPS does not
`IOU 500)1 SjJAJ UR gUi.POO
`'pQMOflOJ ST UO!I10AU03 SUUIS
`LPS probability estimates are further restricted to the small
`Ifta ql oi p sal .iupxnj =s soswrmq= Xqr qnid Sj-j
`change the code string, while coding an LPS does. Figure
`wnrsSj 500op Sa-
`l
`ulpoz zITIIm Tuulrs 0a03 041 02US
`subset of 30 values actually used in the Q-Coder, the dashed
`p~qSnp Qql 'x~p0o-?b Qq-i ts plWn k'nl3'R S~nUnA Z JO pZSqns
`8(a) also shows the relationship between hardware and
`pus ox~p~st)UOO
`14S u VuonW 011) SA%04S
`(V!)8
`(15)
`curve labeled "5-bit granularity added" results.
`software code strings. Note that the gap between the two
`otq 04p uoo~vIq dia otp Imip ojoq 'S!uuls apoo
`, u'jos
`code strings is simply the current interval.
`01) Aldtuis st sguyvapoo10
`IuunoJ~
`
`01
`10
`
`ZI
`12
`
`8
`
`9
`—1082 (q)
`(b) Zsol-
`
`subdivide the interval can be approximated as follows:
`:SMoloj se
`pneumacidde --q UVO JVAXDUoiru o p!rpqns
`A X Q.cg $24,
`
`Ax.P.=Ax(1—WeKA—Q.
`
`3 I, J. Rissanco, IBM Almaden Rctatarch Conan, San low., CA, private
`communication.
`
`-piAIolut
`
`sdiv a -d am~v -dr 'Noaoi
`'8 *A
`-o 'o Tlmi-mrw -1 1 'U7XVG3X~aa
`w. B. PENNEBAKER. J. L. MITCHELL, G. G. LANGDON, JR., AND R. B. ARPS
`
`IBM J. RES. DEVELOP. VOL. 32 NO. 6 NOVEMBER 1955 SS61 W3Ryf3A0N 9*0N Zs -10A
`'dO1SA3G SaW *r 4
`
`Unified Patents, Ex. 1018
`
`000004
`
`

`

`A(0)
`
`0
`
`Symbol: M
`:Ioqulxs
`w
`
`M
`w
`
`M
`N
`
`L
`-1
`
`(a)
`
`Symbol: M
`W IoqwAS
`
`W
`
`L
`-1
`
`M
`w
`
`(b)
`
`:1:1R:
`SIR R5 lRRApqqpyjjl=
`Code-string treatment with hardware-oriented conventions: (a) Hardware encoder code-string development. (b) Hardware decoder code-string
`'Jupis-apoonpooop oxampjnH (q) -iuzwdOl2AZP 9UInS-OPOO JVODUO 3"MpJgH (P) :SUOIJU2AUOD POW-3110-OnANPIP4 41!m JU;Xulvan guLlIS-OPOZ)
`remainder.
`-npuleww
`
`Q. index
`)COPU!K4
`
`5
`
`iii
`Decode
`into Q.
`
`13
`
`13
`
`13
`
`13
`
`13
`
`Qe
`
`T
`C LOAD
`GATE
`
`Undcrflow
`
`Inhibit
`
`(2
`
`13
`A—Qr
`0
`
`1
`
`Q. index
`Xwm 8
`
`/5
`
`Decode
`into (4
`
`13
`
`A—Qe
`0
`1
`MIX
`
`Undcrflow
`
`I C LOAD
`GATE
`
`Inhibit
`
`A SHIFT
`REGISTER
`
`C SHIFT
`REGISTER
`
`A SHIFT
`REGISTER
`
`C SHIFT
`REGISTER
`
`(MPS) DATA OUT
`
`
`
`C)
`
`CODE IN
`
`(MPS) DATA OUT
`
`CODE IN
`
`(a)
`
`(b)
`
`.11, 1 1 ,
`Cll j ::i
`: LIM !
`11''', lll OMNI
`Data path trade-offs: (a) Hardware-optimized MPS and LPS subinterval ordering. (b) Software-optimized MPS and LPS subinterval ordering.
`-Suu2pio IeAjzquiqns Sjj pue SdW p-,zjtuijdo-2mA jjoS (q) -2uLlaNo leAjmutqns SI-l ptm SdVq poz!wndo-aiumpmH (a):sjjo-zpea qled meG
`•
`•
`—`" •
`
`01 1111
`
`'•
`
`'
`
`• • -
`
`A 1:1
`?;
`
`Ul
`
`W.~
`721
`
`IBM J. RES. DEVELOP. VOL. 32 NO. 6 NOVEMBER 1988
`996t IMHPGAON 9 *ON ZE *IOA AOIUM 'MH I WM
`O33O~
`NZCb
`
`W. a PENNEBAKER, J. L Raraimi, O. O. LANGOON, nt., AND FL B. ARPS
`'D 'D T13101W1 1 r
`-g 'AN1~l~3O
`7XVaRilN13a
`'NOOOt,(V
`&INV Tf I ONY -W
`
`~
`
`Unified Patents, Ex. 1018
`
`000005
`
`

`

`START
`
`YES (MPS)
`
`NO (LPS)
`
`YN MPS
`
`A.-A-Qc
`TEST(A): RENORMALIZE?
`
`YN LPS
`A *- g
`RENOItMALIZE
`
`(a)
`
`(b)
`
`Inner-loop trade-offs: (a) Hardware-optimized MPS and LPS subinterval ordering. (b) Software-optimized MPS and LPS subinterval ordering.
`-Sut.L;)pjo Ltwomiqn Sd-I pulE s
`p~znuipdo-aBmijoS (q) -uupio IcAj~Iuiqns Sd1 pun Sd
`pozrwtido-azmmpn
`(9) :fopBndOOI-32uul
`is
`i
`
`a~
`
`A(0)
`
`1
`
`Software code string
`
`Pe
`
`P.
`
`Q c
`
`Hardware code string
`
`Q.
`
`Symbol: M
`N :joqviAS
`
`Wi
`
`M
`wi
`
`L
`'1
`(a)
`
`0
`
`Symbol: M
`Ni .o-AS
`
`Ni
`
`'I
`
`Ni
`
`(b)
`
`A(0)
`
`Code-string treatment with software-oriented conventions: (a) Software encoder code-string development. (The hardware code string is shown for
`.)UQAUOD poluopo-ammucPs 1PIM luauwoA gut
`joj uAoqs stSums 2poo wemp-mq OtW -Iwwdol2AOP su ns-opoom