fa
`vi
`
`-
`
`0 -
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL 37, NO. 2, FEBRUARY 1989
`6961 AIYMfli3d 'I *ON L "IOA 'SNOUV3LYINflNiOZ NO SNOLLJVSNLL 3331
`
`A Multiplication-Free Multialphabet Arithmetic
`o ouqmniJV joqn .qdpu!jlnw oaij-uoi vo!idt iInN V
`Code
`opoJ
`
`NJG~flIHOIW1 "4 "X Cay NaNVSSIa Jotf
`JORMA RISSANEN AND K. M. MOHIUDDIN
`
`93
`
`for symbol from left to right. When encoding the symbol i,
`Abstract—A new recursion for arithmetic codes used for data compres-
`sp mpomuo uoqA.
`loqwAs
`" qg.j 01 13l uxojj loqn-s .o1
`',I
`-aidiou wisp 3jo pasn saop apinq uru joj uops e
`rqV
`VMI
`immediately following the so-far processed string s, the code
`sion is described which requires no met iplleation or division, even in the
`opoo -alp -v Sixsuus pssoosd mj-os op gumotoJ klisrpoumz!
`ap t1 uS)A 'nOjlqo p io uoTvaildppiWa on swanba qssjA poqps*p q uols
`requires as input the data that represent the conditional
`case with noabinary alphabets. For this reason, such a code admits a
`piuopipuoo 543 3u5sojdSj
`imp 135u o4 3ndut su sw!nboa
`a iwps a poa a q31 'osa slqs jO.1 "spqvqdI SJntiqou q54& am
`probability of the symbol's occurrence at its context, which in
`simple and fast hardware implementation. The inputs to the code are, in
`U! K3tqAM '153UOO si! 35 ozuJaJnooo s~loqmus 4 jo A!Uquqod
`iq 'is
`a-dml szu.pssq p5 pus a.dzljs
`apoo a s Ol 6ndtq uj. "uoL
`the must general case is the entire past string s. Such
`addition to the symbols to be encoded, either the symbol probabilities or,
`osinu otp S! asr 35uf isotu o4
`n.Las Ised
`qo4s -s
`'o siqzqoid Ioq=As aql
`saq ol qoqm9 Sq) o) uolilppu
`zp 'papo
`parameters are provided by the so-called mcalrling unit. In the
`more 'drably, the corresponding occurrence counts. Hence, the code is
`a4p uT "I!mn SUT
`.1 m poo-*s siP Aq pOp!Aoid we s.lstqsd
`-Siunw asaazun5oo 8ujpuodsauo aq) 'LIdmws ajow
`q Vas ai '3515ow
`special case where the string is modeled by a stationary
`applicable in conjunction with stationary and nonstationary models alike.
`out s! Srqtii mp oa154M aiSU psisds
`Alsuopss e Aq po
`5P0
`"ImW ppom Amopuiguou piu Lnmoph qiti uop3un'uos Lq 2lqs Idl
`source, these parameters do not depend on s. Often, the
`The code efficiency Is typically in the range of 97-99 percent.
`Sip 'u134O "s uo puodap ,ou op ssizitirawed 2sS3 '5o:3os
`o a3n 043 qi gq CpA q p ajjp apow aUq
`66-d 6-
`•U
`simplest way to represent the model parameters is in terms of
`jo suuKo-i U! s= simsusisd 3111 oip iSo~sdai o XSM iIdu.s
`integer-valued symbol occurrence counts, say ni for the
`I. INTRODUCTION
`5U.
`'siunoo =2susinooo
`loqmAs .pn*jA-.t15
`sip toj lu Ss
`5
`symbol f in its context, which we from here on do not indicate.
`"18ospi. Iou op uo 0isq 0o10*A & qorqtA '1X400 Si! U!! IoqusLu
`Al
`codes, introduced in the UFO-form (last-in
`n-is,) uuoJ-o qd o3 ti pI npoxnu
`'sopo JIILaHLI V
`These numbers need not correspond to the real occurrences of
`ou pso sjsqunu osoqL
`1o sSSuorSoo pisi oqi o puodsou o
`
`first-out) in Rissanen [3) and subsequently modified to the
`the symbols; instead, the modeling unit may update them in a
`(C] usussri
`.(n
`oql 01 pogpow Apuonbsqns pt
`smn 1.nm Buqapow oip 'psoism
`sloqwus alp
`tustp olpdn
`a u!
`important FIFO-form (first-in first-out) in Pasco [2), are by far
`uoj-od
`luS iodt
`.j Aq sm I [Z] oosed u! (ino-isg u.-sg).
`sophisticated manner to reflect changing statistics. If n denotes
`the most flexible and powerful coding techniques available for
`SO3oUop u Jl
`"
`Su35usso
`01.151555W psSssSs.idos
`.0J *IjIM. A5 SnbrUq0M g1q3o Ilom od pus alqrxatj isou oip
`the sum of the counts nt, then we may say that the symbol i
`I IoquiAs o53 imp3 Ass mn *A uoM tp I u sunoo o1 jo uris oqp
`the purpose of achieving compression, for they can be used
`soj "uoisswdiuoo ulAorqo Jo ssodrnd op
`,osi
`posn sq ii
`following string s is modeled by the probability P(lIs) =
`/ u = (sI!)d ,Aiiquqojd sip Aq po'lopou s! s gufns .rmKofloj
`with equal ease to encode strings modeled by stationary or
`.o Aisuo.ns Xq polpow sSu.ns opoouo o 55
`[inbo K!,m
`n. In addition to these counts, the Modeling unit collects and
`(n uop.ppe uT -u
`pu S3ol.oo iS 3TUPl
`QEP51 0 si3 s noS
`nonstationiny sources. The basic encoding operation in an
`i
`delivers also the cumulative sums Q(i) = no + • - • +
`US u. uo.1tudo gutpoowr Olsmq OsIL -s-
`os A.rsuopsisuou
`',-u + •.. + Ou
`P oSM szs*Aqsp
`(!3 , Ws 0ATI nnmr
`arithmetic code requires an update of the probability P(s) of
`jo (s)d A.ipqsqoxd itp jo oiepdn us swmnbo spoo o.unwpgus
`= 1, • - • , m, Q(0) = 0. The modeling unit should update for
`sin pjnoqs :ipn Z.qopow oEL 0 = Co)j "3
`'[ =
`joj
`...
`the so-far processed string s, which can be done by multiplica-
`each symbol I not only the count ni but also the cumulative
`'s Suus psssoood xu;-os otp
`,
`-s.qd~nu _q uop sq um Ko
`oAnnsniuno sql osp nq fu inoo oip Auo
`qmo
`iou I joqms
`tion P(s)P(i I s) where POI st) is a conditional probability of the
`(sj ')J(s)d uoi
`oin jo Arqqd
`si(sj;),=si3
`josp~uoss
`counts Q(j),J > i, which are affected by nu. Finally, because
`(r)
`ssnvsq '(Ipm.I .u Aq pajoaip sm qorqM' <
`Slunos
`symbol i given s. However, the multiplication in a hardware
`p 15 AMOH "S UoA.i ! loqtuks
`a5M3p,55 v m uo.uvo5qctfl
`of the approximations that we introduce later, we assume for
`soj sunssr SM, 'ica oonpoiru, *A& Ivti
`suounpn ozdds OMq jo
`implementation of the code is relatively expensive and slow
`mOlS pun oAjsudx2 k-Apnvlw 53 s!poo oq jo uornmuotuolduq
`the best compression efficiency that the symbol with the
`is-aq otp
`2tp
`tplA oquiAn sip imp auosUpjo uoKsSoSdtoo
`even though both probabilities are numbers which in their
`ipoq q5not UoAS
`mm al iP.r
`06M son Iqozd
`sJoqunu
`highest count to be the last, i.e.,
`S.o-t 'IMls;q oq ol unoo soqlq
`binary representation have at most a fixed number of
`sou. 1i okAi uoni.uzs-aida kasqq
`squmnu poxg 1
`jo
`significant digits. In the special case with a binary alphabet.
`(u"z)
`(2.1)
`.up 5mvoUpa.s
`• aqmqdi krmqq u qitpA oso pImsds sqp ul *sl
`n„, ni, all i.
`"; P "u~tuu
`the multiplication was replaced in Langdon and Rissanen
`[() umussrst pus uopuir7 u! psssjdw ssA uonsoqdi uu sip
`An arithmetic code constructs the code string as a cumula-
`by the much simpler shift operation, which was made possible
`-sjlntEM:i SR uSM 2urOs spas S!0ipU0 siuuOsO Orpas
`oiU'V
`olqlssod opsui s% qo.qw, 'uos.xodo ijnp pold.s qontu op Aq
`tive probability of the strings that precede the considered one
`by an approximation of the smaller symbol probability with an
`-uo pnop:suoo os p sp psd p
`sguls= oqi jo Ap nq.1d SA
`um toy At.pqqoad ioquLks jIspmus otp jo uounsu!xodds ts Aq
`in the lexical order of the strings. When calculating this
`integral power of 1/2. However, the same idea does not
`su Soap 53p! 5(15 5Q1 'JoAMOOH -z/I Jo xo~iod re.Imul
`Sup
`ftunulm U q
`-sg .us am jo Japao M!Xi otp a!
`cumulative probability, the code uses a certain approximation
`generalize to nonbinary alphabets for the reason that the
`uoussurrosdda txrsiuxu v sssn opas sip 'qIqsqos
`RAlsinno
`otp itp
`uos
`ot
`oj sloquqdpi Asuquou 01
`,qersos
`of the probability P(s) defined by the model, which we denote
`symbol probabilities cannot be approxiMated well enough as
`'spowm sp Aq pouIgsp (s)jr Airpqstqosd sip jo
`o Sup A qn iFia~
`su tiSnouo IpA% pmncxoiddv sq iouUmn so.n!lpfqvqod toquLks
`by A(s). This approximation satisfies all the properties of an
`powers of 1/2.
`us jo s rudozd sip He ss'
`sps uopsurxosddv sq.
`(s) V Aq
`"
`information source, as explained below. The lexical order on
`poupivdxs se '2winos uonmuoju!
`In this paper, we describe a new implementation of
`no mapao Iu.Ixo ouj. ",oq
`isdvd s.tp ul
`sqtusap SM
`jo uo.uSusotdu! A=u
`the strings implies, in particular, that if s' < s, both strings
`arithmetic codes in which the proper multiplication is avoided
`al '92dti ~pa
`i
`, s j p
`>
`'xpsird
`sgumxs tpoq Is
`pOpIOAR ST uol.480sduInm .zdoid oq q3TiA& t. sopoo oposuIjw
`have the same length, then for all symbols f, s' i < sO where si
`even with nonbinary alphabets. As an added bonus the code
`!s ooqA Os > !,v
`'p sloqu3As flu soj utq
`'qlguoi oms
`oq oA5
`sioqvwdjv Assixquou tp.m uA.S
`opom otp snuoq popps ue sV
`denotes the string consisting of s followed by the symbol i.
`can accept as inputs the occurrence counts of the symbols in
`loqwAs aqi Aq poAonlo; s jo gupsisnso BSUps 21P S53uop
`-
`u! sloqtuis op jo smuno souson.so sip sindut su id55- uv3
`Therefore, if C(s) denotes the binary fractional number
`place of probabilities. This means that no division is needed to
`.xss!q oqi ssiouop ().
`joqumu Fuoqssx
`.
`'sojuzsqL
`n.qqod jo sss~d
`0n popssu s! uoX.ATP ou ip sussn sujq -s
`representing the code, i.e., the cumulative probability of the
`convert the counts into probabilities. Because of the reduced
`P~tnp.K 5133 jo *sfl55O5 5513fqqoId 03131 SltM05 5131 IIAUOO
`oo oip fut.uoswd=n
`"o
`d oAn -InKml
`oqi jo A .qs
`string 5, then the code of the one symbol longer string si is
`complexity, this algorithm is well suited for implementation in
`s
`is S.nxs ssSuoI Ioqtu~s suo osp jo opos op u
`'" s Smnus
`U. uorpusss lduq .jq pa.ms noM& s npuogv sup 'A uxjdno
`VLSI.
`given by
`"IS1A
`Aq UaA^.
`We give an analysis of the code efficiency and discuss the
`atp ssnmsp pus ky uoojo opoo op jo ssAlism us oA.S at
`C(s0) = C(s)
`choice of various parameters. We have also studied the code
`(s-)a = OO;
`s0osoL
`OP 01 3)POT3PrS OSiR 0ASq oft "saviaumind snoUISA Jo
`olul UI "ulluUu .rsdxs iusgis
`efficiency experimentally. In typical strings with the alphabet
`usqsqdjs op tpyA snuts
`0<! '(I-A v +'. +(0s)v+.(00 =(040
`(zz)
`C (si) = C(s) + A (s0) + • • • + A (si — 1), i > 0
`(2.2)
`sizes varying from 2 to 84, the efficiency was found to be 97-
`-.6 sq 01 PUnoJ s1M 3Auo! !o
`533Q 't8 03 Z
`oUUJ SU!AIkA sOs
`99 percent or better. A particularly simple implementation
`uo. .uourldtu oldu!s A[jsnsx.usd v -i.uq io usosd 66
`1 was used for
`where for the sake of clarity the notation sf
`Is uou. ou tp ATjUo jo o4ss otp soj oaoqi
`zoj posn swa I
`-
`results in the rage with a binary alphabet for which the
`s0 qq
`the string consisting of s followed by the symbol f — 1. The
`-oJ )5qqdlg Aisinq v tp.& 09" oq u! sllnss
`"tu. ^1 -
`psiuoo guis otp
`I loqt(s otp Acq poooj
`s jo
`efficiency of our code exceeds that of the fast code in Langdon
`initial conditions are C ( X) = 0 and A(X) = 1 where X
`uopur" M OU 0330 op 510 tJO spooox1 S p3 o. 5 o 530 j
`a3!JJO
`( z=q4
`I = (')V
`ptm 0 =
`()
`we suoaqm
`po3
`rqi.
`and Rissanen [1] mentioned above.
`denotes the empty string. The truth of this recursion for the
`"2AOqV pOUO5.nUU [I] Um5SSt3[M pun
`aip soJ uotssno=
`p jo qWu stM 'Su.is &dmra oqi ssouap
`binary alphabet becomes immediate if the reader cares to draw
`II. REVIEW OF .ARMEATEYIC CODES
`t-p
`03 Usos .ipw.o4 It
`sosoosq isqvdle knu.q
`.poQiu
`-11
`Ss30 3 3U3M1JM3V AO MaIAHU
`a binary tree with the root up, and at each internal node 0
`0 spou pmsucqt qoso is pue 'dn 3 00
`tqlw =a 51
`inssq
`Let the alphabet consist of the symbols I = 0, 1, - • • , m. An
`I SIPqUAS otp Jo 3s1s1O loqvKqdl oq wli
`'1 '0
`1U'i A'...
`points to the left son and 1 to the right son. Then the ordering
`04 o1 pun uos MaiS oq cn saulod
`RKUqjo o1 UoSUL UoS 3qKtU
`arithmetic code encodes the string to be compressed, symbol
`of the strings of length n grows from left to right, and the
`loqtwks 'poissdmos sq o3 Nu.us aq sspoouo soso ansimpu
`sqi pts "i42oJ
`01 3 401 Uos. SM01o U tfPl20 jo s81.n3S Mp jo
`formation of the cumulative string probabilities indeed follows
`sA,olOJ poopu, sonlpquqowd utus aApsrlnumo op.;o uoUMrMoj
`Paper approved by the Editor for rmieg Theory and Applications of the
`Sip jo nKonwSjqddV puu '&011 SUI~oot IM0J
`the given recursion. We shall also see to it that
`p Xq p jiAQid ssdu
`3l 0i (n oos osi
`S nvqs at "uotsjnow UOA.2 o4
`IEEE Communications Society. Manuscript received April 4, 1986; revised
`suosSKUKTUU.
`oD =
`!."zSnUs "sos
`261 '6, MdV POLA!
`Pgi!
`August 24, 1987.
`('z)
`(wu)v+... + (os)v =(s)v
`"L261 'L86 n V
`(2.3)
`A (s)= A (s0) + • • • + A (s m)
`The authors are with IBM Almaden Research Center, San Jose, CA 95120.
`IEEE Log Number 8825337.
`which ensures deeodability (Rissanen and Langdon [4]) which
`"LEESM8 X~qunN 90123M'J
`tp!qA ([VI uopaw-i pus UouessT),
`o
`r A.q.
`saitsu lprqM
`
`0
`
`aaI 6861 ( OO1O$£60O"OOZO/6I8/LL9-06OO
`1989 IEEE
`0090-6778/89/0200-0093$01.00
`
`t3EST AVAILABLE COPY AdOO 3IVIIVAV ±S9P
`
`Unified Patents, Ex. 1017
`
`000001
`
`

`

`94
`
`IEEE TRANSACTIONS ON COMMUNICATIONS. VOL. 37. NO. 2. FEBRUARY 1989
`6561 ANV2flHUH
`'V "ON *LC "OA "SNOLLvO)1NnlNSOO NO SNOLmVSmI.I 3m311
`
`proportion of the conditional probabilities of i given s.
`!o so!nxpqnozd jnonpuoo oip jo uontodoid
`"S UoA4S /
`However, it is exactly the above multiplication that we would
`pinoA% oi& inmp uonno!idnpmu *AOqa o4 Apavxo si i '1OAoMOH
`like to avoid. We first approximate the ideal conditional
`Iguonpuoo
`pp'
`01 ownxo!x.ddn iwg
`ohM "P!OAU ox OqTI
`probability by p(xls) = nr /n = 17,111 and then rewrite the
`oni amuoi uotp pun ylxy = ulxu = (slx)d Aq A pqnqod
`recursion for a(sr) from (3.2) as
`s(e (Z.) u°o (xs)o
`.xoj uo!sano
`
`=
`
`WE)0
`(3.3)
`
`with its initialized value 1 causes A (s) to define a bona fide
`opU -uoq U3 OUJop ol (s)V
`ssnno tI an[UA PZT.IU1IU. S2! tp!A
`information source. These equations leave open the issue of
`3O onss, oTl uodo OAUOjI suox.nnbo osoU0L "0.2wnos uornuio03.
`how A(s) is computed recursively, which will be dealt with
`4mI
`im )pp oq MIM , qr. "Ato atsIowJ poxndwuoo s! (s)V Anoq
`later.
`The arithmetic operations called for by the two recursions
`suotsin= o&4 o4 Aq oj poIIo suonmodo opounp.u ouLL
`will be done in two fixed size registers with width w (typically,
`o!dAi) mn tp.!A% 2!M S.1 025121 .O74 POXI Oh UT, U Ou0 0u JfInM
`'1
`w = 16 or 12), one for C(s) and the other for A (s). This is
`toj ouo '(ZI io 91 = m
`o4 pun (v)
`st stjL "(s)V 103 1oo
`possible if we introduce the normalized quantities a(s) = 2'44
`.p
`wou o4 oonpou.u oA% j Olqlssod
`(-7= (s)v sopunnb
`A(s) where L(s) is a nonnegative integer determined by the
`oqi Aq pou!xUtroxp 1O22u0! 2A1 UoUUOU U St (s)7 OlOIM (S) V
`requirement that a(s) is a w digit binary number in a fixed
`imp iuowuainboi
`2iT!p mn v s (s),
`pox13 u .zoqtunu A Jiq
`range. The selection of the range is discussed under Section V.
`-A u0naS 1opun possnasip S 02um*IV01O 0uoP 1s QtL -"o Su
`For case of implementation, the following range turns out to
`ox 0no .mum out
`Srmnolloj o4 'uonxunioldun 30 055 .od
`be suitable:
`:ojqmms oq
`
`(tZ)
`0.75 a(s)< 1.5.
`(2.4)
`• S,'I > (S0o5 5'0
`This normalization is easy to do by means of shift operations.
`kq op ox (n-1 Asy. UO. .mZ ou
`•*suoqnodo 14qs jo suo
`.1
`To do the encoding/decoding in a single cycle, special
`nip op oJ.
`.pooop/3.poouo
`n ux n
`pnoods "l'opo oIws
`hardware should be provided to do shifts by multiple bit-
`-I1q old.inTu Aq sI.ls op ox poplAo-d oq pnoqs 0Jnepxsq
`positions in a single cycle. In these notations, the recursion
`uorsanoz o4
`'suopnou
`0-01-2 uI "0LO5O ojuxs n o. suopisod
`(2.3) reads
`spv= (C-)
`
`(s
`(S) 7 = (;a)
`a(sr)= (S) fix
`a(s) .
`n
`fi
`U
`_U
`Since a(s) and fl are in the same range of (2.4), their ratio is of
`os o
`w no (tp'7r) JO 2 n ounrs op oq 0-M y ptm (s)o ores
`the order of unity. We can now approximate the recursion for
`.toj uorsinoi oqi oivunxoiddn Mou uno OA -.un jo .zopao oTx
`a(sx) and a(sx') as
`Sna (,x').v ptn ("s)v
`(3.4)
`a(sx)= fix, a(sx')= o(s)- fix
`WE'
`Qv- =C(s)o =(,xs)v x = (tXy)v
`and then normalize the new value of a(s) to be in the range of
`jo ouni oqx ut oq ox (s)n jo onVlSA Aou oq
`,OZ!puou uoqx pun
`(2.4), quite analogously with the general normalization with
`:qn~b '(t,Z)
`.Ieuuou puuoR otp Cm ,qsno8olu=
`tp!m uorn
`which we bring the addends A(s) to the same range. In case
`osno ul oguw~ own otp oi (s) y spuoppv oqx Rup.q omt qonqft
`the inputs are available as probabilities, our approximation is
`o
`st uoitnunxoxddB .no "s04!1145o0d 55 o'qnpnptn om snduI
`equivalent to the following recursions:
`:suoisiznooi SrmAOlloj otp ox xuojnA&jnb*
`(3.5)
`a(sx)=p(x!s), a(sx')=1 p(xls).
`(5'z)
`(uIS)v +...- + (0S)p = (S)v
`(2.5)
`a(s)= a(s0)+ • • • +11(sm)
`Let us illustrate the approximations with an example. Suppose
`osoddnS "oldumxo ue qx.in suo4Uuilxaddu znip o
`rxsnt, sn
`n = 1101 and no = 0010 in binary representation. By
`where d(si) = 240 A (si). As s increases in length, A (s)
`Xq "uoninuzsojsd=z kAmq u! 0100 = Ou pm
`1o1l = u
`-o104M&
`(!S)4
`V€01Z =
`(s)V "'SQoI U! S05U OU! SV "(s)y
`normalization of the counts it = 0.1101 and no = 0.0010.
`decreases as by (2.3) and L(s) increases, and the quantities
`m 1011O0 = y'
`"0100"0 = O/ p
`sw1o zip jo uozlvnqIou
`sorrnunmb oX0 puna 'sosoJoul (S)7 pun ('z) Aq so sosnoop
`1
`Let, for example, a(s) = 1.001. Using the recursion of (3.4),
`added to the code string according to (2.2) move to the right.
`m ioj "r'l
`"(
`j) jo uo!sinoo 04 S sfl "100"1 = (s)p 'oldux
`iop ox poppn
`-IqST- W.P ox OAOtl (z'Z) ox gU.pooon 5UIS opo
`d(s0) = 0.0010 and d(s1) = 1.000. Even though 0.001/1.001
`Equivalently, the code string C (s)is shifted left relative to the
`100" 1/100"0 q1nOt UOAS "000" 1 = (Is)! Ptu 0100'0 = (os)p
`nIq (n
`oA1U 01 O
`(sU
`) Tups OpOO 042 'Sa2UZIVAnba
`s
`differs from the count ration 0010/1101 by about 50 percent,
`'xuxoaod O inoct Aq 10 11/0100 uonwe iunoo otp uzoij s10.HT
`fixed register where the addition takes place.
`"=Id so*nx uopxrpe o4 0aqA% os!oaz poxU
`the effect to the code length turns out to be small. The issue of
`jo onsst -aLL -ITums oq o1 Ino sum cxuol opOo q o(n oojja aqx
`M. BINARY CODE
`the efficiency of the code is dealt with in greater detail in
`inq pnxop Iwr-us U1
`1n fl imp st i C opoo 014 JO
`taj
`zipJ 04
`Section V.
`*A uOnOOS
`A particularly simple implementation results in the case of
`Jo 0510 oip u! sxinsoi uotumumoidrn olduns Apnjno.dnd V
`We now clerribe the coding operations in terms of the
`binary alphabets, which we describe first. Let x denote the
`o04 jo suail. 11 suofrwlodo gu.poo 0tp oquosop mou a.
`actions in two registers, C and A, both having width w. We
`symbol to which the model assigns the lower count, i.e., n„
`'yv puU 3 'S102s!Z*0
`*A "n t22Ip SMAvu xploq
`.O0 o t suoo
`I
`01 Ioatis
`l*pouI 0142
`lo.oui
`-S.-
`5 zU ""'! '"lunoo20 .aAo
`interpret the content of C as being a fractional binary. number
`n/2. This low probability symbol, of course, depends on the
`.xoqumu .fmq
`mnuo otuj e Zu.oq sv a jo juao oti mdrnu!
`=Vpuo spuodop "503noojo "IoquLs ,4'!qrqojdaoj srtJL Z/u
`resulting when the binary point is placed to its left end, while
`past string. Denote by x' the opposite high probability
`olpxA 'pu* V0o s31 ox ponId st xuod Auz.q mnp uoqin gutp.s0
`,0uyqqowdr yfflf OIsoddo oqx ,x Aq oxouoa St us42 isnd
`in register A we place the binary point after the first position.
`symbol. First, convert the integral count n into a fractional
`1uUoPOUJ R (null U 1M5o0
`1U42 2OAUOO "xsW!ai -[oqwAs
`i5
`•uo.sod isig otp zox4 itod ,C,-umq otp oauld o. V ioxq.w u!
`The code string C(s) consists of the symbols that get emitted
`number in the range of (2.4). This is achieved by shifting n by
`pouo log vnp sloquLks oqx jo sisxsuoo (.v) a gIuS020
`u
`Aq u nppqs Aq pAo*Tqou 1 5tLL "(",,) jo o uZ oq u. soqunu
`from the left end of register C together with the symbols in C.
`enough positions k(n) to the left such that the resultant number
`xo sa
`jo pu* 4*I oqx woij
`" u! sloqwAs o1 qv!A .zoqa)ool,
`t qons VoI otp oi (u)-y suouisod q~nouo
`14qum1u luynlnsw oq
`fl will be in the range (2.4). Let the counts be maintained in
`0q1 u oq IM U
`u! pou1muUX
`-ct si0noo otp io-I "(t,'Z) atm
`A. Encoding Algorithm
`registers of width w. Let 1(n) by the number of significant
`11301311151 JO .oqtunu otp Aq (U)) xo'1 mi t4Ppm JO s.10251501
`wqTuO Iy 8utpo3u' "y
`'0 -.. Of 01 V 1s pull r.,O twL D .a1.xs
`Initially fill register C with O's and set A to 10 • • • 0.
`flu pmxI
`binary digits in n. If the second significant digit of n is 1 (the
`I S! u Jo xITIp UoTUwsT Pu0005 oqx 31 u u. Sa!STp Amuq
`OIp)
`1) Read the next symbol. If none exists, shift the contents of
`first of course being 1 by definition) then k(n), the number of
`jo slu0lu01 o 1. 1 "Sssxo ouou 1 -[oquAs Ixo oqx pUo)
`(I
`Jo 1oqumu oqj '(u) 4 uoq:t (uoprurjop ,q
`2 Suxoq asnoo jo wU
`positions of shift, is equal to (w - 1) - 1(n). If, however, the
`C left w positions to obtain the final string.
`• Suus Im'n ox umqo o3 suon!sod.% Vol 3
`.'Uqs jo snon.sod
`(I -m) m unnbo
`oqp "iaOMoq .
`'A "(u), -
`2) If the next symbol is the low probability symbol x,
`significant digits of n start as 10 • • • , then k(n) is equal to w
`(Z
`.!qTqOzd mol ot4 s1 loquxks xxou oqa'
`loqtuAs
`'x
`in 02 iunba ST (u)4
`"... Ox 5 1 su ums u jo r2p iuvog4U.s
`- 1(n). In the former case, one can think of the radix point as
`replace the contents of A by fir and go to 4).
`"(t, ox o pun xy Aq V jo suomoo 0q1 oodaz
`sn 2Urod xtpnx oip jo 2u15112taro ouo 'osi10o1J 104 ul "(u)l -
`3) If the next symbol is the high probability symbol, add to
`being just to the left of the most significant digit. Correspond-
`ox ppe I oqiAs Ax~tpqsqaqd qSuq oqi s! joqwAs Ixou mp
`l (C
`-puodsoZso -1121.p jnnojiuSjs 2so
`*ip jo Vol atp oxn isnf Stoq
`ingly, in the latter case, the radix point is just to the right of the
`register C the number n„, and subtract from register A the
`oip a nsio
`jnnqns pue Ixy r oqu
`zip " xoxsjZ~j rao.
`imMx oqaul "XA[.u
`'osn
`am
`oap jox.u gip ox isnf st iuod =Pu
`most significant digit. For example, assume that the width w
`same number. Go to 4).
`of
`"(tv
`-oqmtnu oumn
`imp oumssn 'olduarxo jao "i!grp iuvUogjus isow
`mn 1p~t oq42
`= 8. If n = 00001101 (binary), then fl = 0.1101000, but if n
`4) Shift the contents of both registers A and C left as many
`Aum so Vol
`-y u I'(A .mnq)r Tolio000 = ujI " =
`uI! iq 'O001011"O
`, pun V simSlIf qoq jo sluauoo o0p UN s (t,
`positions as required to bring A to the range (0.75, 1.5). Go to
`= 00001011 then fl = 1.0110000. In both cases, l(n) = 4. In
`(of) C(5*1 '5LvoJ OSUnW oxp ox ypq o3 paznbaoz suosso
`-
`-(U)l "sso qtoq ul "00011O'I
`uI "'
`tt0 T4 I11010000 =
`the first case, n is shifted by (8 - 1) - 4 = 3 positions and in
`1).
`u. pu-e suo2lsod C = , -
`(
`sig op
`s u oso*
`-8)Cq po
`.io1st2ad on poppe iog stoqwumu sV."(I
`As numbers get added to register C, a carry-over may
`the second case by 8 - 4 = 4 positions. Notice that for
`'0
`Setu -IOAO-AIle0 v
`g Aq osno puo-os o04
`mxp o.b "suop~sod
`-- f, -
`,
`ioj
`occur. A special bit stuffing routine may be used to handle
`gaining the maximum speed in a VLSI implementation, these
`fui outxnol RuLffn~s liq pipods y -mnoo
`oTpuUIT 02 posn aq
`"011 'uotmnuoUotdmx ISIA n tH poods umuqxmm 014 Burmu.
`0
`such carries (I angdon and Rissanen [1)). Also, in order to
`shifts have to be done in a single cycle using special hardware
`o" J.ip-o u! '0IW *((I] urUssrd pt5 UpPgm-W) sOu.x-n
`a15Atpmq pliods utsn liOpAo *Tgus, U u. ouap oq 0) oArq sWW3S
`tons
`reduce the frequency of the carry occurrences a guard register
`such as barrel shifters. We will define it = 2-40n. Further
`jOas7ZaJ pivnS u souauino
`wCL1U 014 JO umdbai o oonpax
`ko
`" M 1 9124TRIS 4.Uq sn q1ns
`OAP
`= Y
`J0142nJI 'U()v-_
`define 0, = 2- kom. Notice that the individual count nn is
`of width w, may be placed to the left end of C to take care of
`jo avo oxmn ox 0 jo pu* Vol otp on poonjd oq Amu -,At qpyA Jo
`!Uo1"PUu
`"O =
`OUUOP
`sl xu 3131 0
`,
`IMP QOR
`UI(
`carries shorter than w,. In such a case, a corresponding
`shifted by the same number of positions k(n) as n. In such
`sop
`'03
`'o
`Bu.puodso.uooa
`Ipfls ur "'t uinp 1o0ots
`qons ul "u su (u)4y suolTsod jo oqumu omns oqx Aq ponls
`row.s where the inputs are available not as counts but as
`register should be used at the decoder also.
`se inq simnoo se wou olq A elmA0 aim sndul wp o.aoqA sosw
`.osT japooop !o4 vR posn oq plnoqs omSwz
`We illustrate the encoding algorithm using a simple exam-
`probabilities, each written with w - 1 fractional digits, we put
`ind o*t '"21.p. 150o42m 1J I -m tp. uoupA qt a 'sp!pqeqod
`-uxmx, olduxrs a 2utsn npmjofpx Butpoouo 014 oxnxsnrn oA&
`= fl = 1, which gives ft = p,. Since n =
`'0100
`lu pun
`ple. Let n = 1000, no = 0010, and a l = 0110. After
`'000I
`J 2V "0110 =
`= u W1 oid
`+
`u
`= 0
`we
`-u
`qO.q% t I I
`.sOA
`OtA IXu + 2u = u aoom.S "'d
`have
`normalization, we have fl = 1.000, no = 0.010, and
`l puB '010"0 = OU '000I = Y oA4 OAM 'UO.M.lUXIOU
`=
`0.110. We assume the register width w to be 4 bits. Let the
`a14 1'1 "sa!q t oq (n
`a J-01 aMumssw OM -011 -0
`I EPP!AA.
`-
`(3.1)
`(*')
`string to be encoded be 0111010. Table I lists the contents of
`I .olqeL "010I 10 oq popoouo oq o Suins
`jo s2u~2uoo o4 9s5.
`both C and A registers after each symbol has been encoded.
`•ppou uzaq svi loqi~uks tpno
`.imp sj~wxoa V- puy 0 3i)oq
`A recursion that would satisfy the basic decomposition of
`The (terming is done by virtually reversing the steps in the
`otpiq sdmxs Otp SUIS~uAOJ 4A11E2IA Aq Quop 91 BUtpO"Op OtLL
`jo uon!sodxuooop otseq otpl Ajsum plnoA% imp uoxsln= V
`(2.5) (for m = 1) is
`(z)
`(o Q = us mj)
`encoding.
`a (sr) = a (s)p (x I s), a (sx' )= a (s)- a (s)p (xis) (3.2)
`'(sl x)d~s)n = (xs)v
`(z'O) (slx)d(s)b -(s)v = (,xs)v
`B. Decoding Algorithm
`if
`uWyij)o~v sUipoaa
`Initialize C with w leftmost symbols of the code string and
`!
`where p(xls) is the conditional probability of x given the past
`-qoid pxuoivrpuoo atp s! (six) d axuqA%
`pug Sum1s opo0 arp jo sloqui~s isojuiVo
`3 ..r ntxu.
`xsn ump UfA1 x jo A.Tq
`A with 10 • • • 0.
`string s. The goal is to apportion a(s) into a(si) in the
`01 itnh V Oo' U! (!)V orq! (s)o uoT~uoddu ox st vog u.L "s Uu.ns
`10
`
`O
`
`C
`
`ft= tl„+ fix..
`*iXy+x&IyLI
`
`t3EST AVAILABLE COPY AdOO 3'IV-lVAV ±SP
`
`Unified Patents, Ex. 1017
`
`000002
`
`

`

`RISSANEN AND MOHILTDDIN: MULTIALPHABET ARITHMETIC CODE
`mammowfl~ ON N11NVs-sm
`aao10 aLLawt(Lrdlv ±aaydruinHl
`
`95
`
`TABLE I
`I Hiff.L
`ENCODING EXAMPLE FOR BINARY ALPHABET
`JL39YHZrT A*&VMS'Og hd cPCVX3 DNIOONH
`Symbol
`Reg C
`Reg A
`IOVW'
`:)ra
`V 202f
`1000
`0001
`1000
`0001
`0110
`0110
`1000
`0001
`0110
`0110
`1000
`0001
`0110
`0t0
`1000
`0001
`
`0000
`0000
`00 0000
`0000 00
`00 0100
`0010 00
`001 6000
`0000 T00
`001 0100
`0010 t00
`00101 0000
`0000 10100
`00101 0100
`0010 10100
`0010101 0000
`0000 1010100
`
`Start
`=r12S
`0
`0
`1
`1
`1
`I
`1
`I
`0
`0
`1
`1
`0
`0
`
`bring it close to a(s), which then allows us to define the next
`3xou ot
`uoto q:.pqA% '(s)vn o SOla
`ol sn sAOtl
`og2ap
`i -, g1q
`addends simply as rix and a(s) — fly, respectively. The same
`u
`011 1qL "-I^.no
`(s)v ptu x
`sO Aidurs spuopps
`-
`ads-
`idea can be applied in the general case as well. We recall that
`A& "Iam s o5 jIaOuag ot § ! po11dda *q uSo 54p
`ow i
`o
`the modeling unit places the symbol with the highest count as
`s11111o002591t2.q o 4a& IOqtuLs §t4 swavld itun Bu21 o4 114
`the last symbol in, which is done for the reason to reduce the
`aI 1 o
`oqj zonpoi ol uosvw oxp jq ouop st qorqA% "a loqu
`approximation errors; the ordering of the other symbols does
`o413 2iUop-o00 1 !sjoLo uonmuFx odda
`sop soqus Aoto0
`not matter. As before, we define k(n) as the value of the
`0o jo onfuth oq so (u)' ouop OA "o 0oq sv
`-101m1
`2ou
`integer k which brings 2'k52 in the range [0.75, 1.5). Then, we
`Z sguuq qoUyM
`*( 1 'FL'O] ogui o4 u! u,-
`§M& 'u§
`o -029u21
`define the normalized counts
`sjunoo
`paqmou atp ougap
`PI = 2- k(")n
`
`fii= 2- kO)ni
`
`TABLE 11
`H aliev.L
`DECODING EXAMPLE FOR BINARY ALPHABET
`3 Ot YCddIVX2 ONIO-YG
`§HOVI4JTY AdVNII
`
`1
`
`-
`
`Decoded
`Symbol
`oq9WCS
`Start
`VS
`0
`0
`1
`I
`1
`I
`0
`0
`1
`K
`0
`0
`
`Reg C
`
`Reg A
`
`0010
`0100
`1010
`0101
`0110
`0110
`0101
`1010
`0001
`1000
`0100
`0010
`0000
`0000
`0000
`0000
`
`1000
`0001
`1000
`0001
`0110
`0110
`1000
`0001
`0110
`0110
`1000
`0001
`0110
`0tt0
`1000
`0001
`
`Q(i)=I di, 0(0)=0.
`ICI
`In case the inputs are probabilities, each written with w
`41.M U1'-).L% qoo "son~pflq~qo.e d §rv sndu! 941 os1 uI
`fractional binary digits, we put n = d = 1 and it = p t.
`-1d .
`:y pun
`u Ind *A% '5s.1.p krn.q 15uo
`=
`pow
`=
`The idea for updating the addends is to define them as a(si)
`unvapdn joj 105p, oqj.
`)p0
`(15)n su u04 aug§p ol si spupp
`= ti;, t < m, and a(sm) = a(s) Q(m). But because we
`,v *n500 2
`(s)D = (wov)v pue 4w > 1 'ly
`-
`*(u")i
`may have it > a(s), the last addend d(srn) = a(s) — Q(m)
`= (Ws')p 4)1104)4)1l 2011 §4000s < m/ *A14
`(uw)i
`(T
`sm
`-
`may be negative. In that case, we replace k(n) by k(n) + 1,
`'I + (u) t ,(q (u)
`zosldoi -m
`'s0 Tupt u3"Ap1u 0q
`.U1
`and this guarantees positivity of all the addends. The final
`1I11 oq.L "Spupp1 MP IM1 JO /Anpnsod sQ92utwva s, V ptr0
`enecvling algorithm receives di and a as the inputs, and then
`puu hr 5 AIt.1 tu.uoge Ou.4po0u
`uot puls "Sandu.. od se O
`progresses by the following algorithm using two registers C
`C) sa1m2S1g om4 Ou!sn n1.1o401 21 1mo4oj aq Aq sassoo.12d
`and A. The content of C register is interpreted as a binary
`jo muoo q. "-V pum
`i .at1
`knruqq U s poi1.d1tmx2.
`fractional number resulting when the binary point is placed to
`o0 p§oard s. lu1od k.m.nq §qi uy4AM
`o4o
`upIjsw j aqumu
`the left end, while in A the binary point is placed right after the
`o§4113 .l02!. pouId st 2uIod Amlqjq §4p V u. !11qAM "puo f3t tp
`first position. Hence, for example, if register C has width w
`'oldumxo 1oj 'oouH "uo14sod is1nJ
`Mf Ep1t% suq a -C2SISO§ J!
`= 4 then its content 0100 represents the number 0.0100, while
`Sluosadid
`1oqumu o
`opqA '0010"0
`0010 1lumuo sit0 u04 t =
`in A the same content represents the number 0.100.
`"001 0 oqumu 94p spuoxoxdoi 1uo2uoo ourss aij V ut
`A. Encoding Algorithm
`tuq!Jo81lf 2uvpo3u' "V
`Initially fill register C with 0's and set A to 10 • • • 0.
`T11Q .1
`V 205 pul s,0 41!t 0 10U51201 II
`.01
`1) Read the next symbol i. If none exists, shift the contents
`1) Form an auxiliary quantity T by subtracting fix from the
`Ixau tp pezW
`(I
`x ouou 3H -! Ioqm10
`'S'
`s2umuoo 0 0 4rq1
`vtp uioij xy gunpowqns ,q
`nu Aanb ,.za.Lxnu ua UUod CQ
`contents of C. Test if T < 0.
`of C left w positions and stop. Else, test if 0(m) < A. If true,
`SJ! SaL "0 51o slu110
`"dons pua sosod m U o1a jo
`"0 > j3
`,"V > (u)h0 j1 ism 'S q
`"nn jI
`2) If T < 0, decode the symbol as x. Load A with fix. Go to
`put .0 = 0. Otherwise, put iS = 1.
`o0 oD "xy tp!r V pop "x su loquAs oql apooap '0 > j
`jl (Z
`nd
`0 =
`1 ip0
`.I = S Ind '9
`2) If the symbol i is not the last m add the number 2-6 0(1)
`4).
`i loqmus axp 11 (Z
`(!)O-z .oqurnu zip pp4) Ut 11 34120ou
`"(t,
`to the contents of register C, load register A with the number
`3) It 7" z 0, decode the symbol as the high probability
`Uoqtunu §tp 42vM y
`I 1(C
`js050. pvol '0) imsi.gai jo smuoo o13
`0 0
`,¢rpquqoid q2.q oq su loquis §t
`0 z
`pooop
`symbol. Load C with 7', subtract rt.. from A, and go to 4).
`2-11/1i, and normalize, Step 4).
`'.iL !Al C) P
`-1 loqtws
`"(V 01 og pun 'V tu30j "V p011qns
`-(t, dnS ".ozqvtou pua 11ugZ
`4) Shift both registers left by as many positions as required
`3) If the symbol in the last, i.e., i m, add the number
`1zqtmu §41 pp4 'U
`= -
`'1.
`'25lJ o1q4 loqu.LS otp jI (C
`sto2K21 tpoq j.qS (Vz
`poiinbo se suopnsod umm se Aq ijzl
`2-00(m) to the contents of register C, subtract the same
`to bring A to the range [0.75, 1.5), and read the same number
`§m4s OL p)R pum '(i T "sL'] tsrma §103 V su.q on
`ioqwr1nu
`jo siumuo0 3tp o
`ouSs §41 1anqns '3 xzisdit
`(u)iDOg-
`number from A, and normalize, Step 4).
`of symbols from the code string in the vacated positions in C.
`•(p dois 'Oazfmou pus '
`1110
`2 U! suonu!sod poaluouA §41. uBu.s apoo mp0 tuoi sloquXAs jo
`IoqwLu
`4) Shift the contents in both registers C and A left as many
`If none exists, stop. Else, go to I).
`j
`*doas Instxo oou
`(I on og 'osr
`positions as needed to bring the contents of A to the range
`Let us use the coding parameters of the encoding-example
`§1d01o-Ui.po0u§ p0 jo
`sW2wa §t1 oq
`02 su0uo *1 UN S (1,
`02t V p0
`o(usm s
`unoxd Supoo §41 osn sn lo'
`joi
`.od
`oguej tp oi V jo suomoo otp gmut.q cn popoou su suo.
`[0.75, 1.5), and fill the vacated positions with 0. Go to 1).
`and decode the string generated by the encoder. Table II lists
`'0 IPIM suOT.IISOd p,.nvaaA §41 UJ puv 4(g,
`I 5L]0
`'(I 02 00
`sIsn II olquJ, ".1§pozua §41 Aq pow0u12 S1ums o.p 2pocop puy
`JJO ,gu.[ej,, s214 §41 'otp T 4
`Whenever register C is shifted left, the bits "falling" off
`the contents of both registers after each symbol has been
`S. s) 1J§2wS2
`1§A§U§Jq,
`IO tlp sacs~gai qloq jo sluzuoo o04
`IOqtuLs qos
`u§oq M
`the left end arc the survv.asive symbols in the code string C(s),
`decoded.
`"(s) a gu.aS opoo o4 t. sloqu.Cs *A1Ss§ns nSp
`zip
`am puo 4
`"pap0o34
`which may be either transmitted or stored in an appropriate
`Notice in Step 2) of the encoding algorithm that the
`q1nt&
`s p101S 10 p r 215o.1513
`mleJdodde tm U
`§41 21 14u01.~ol
`§4p jo (Z doz ut oanolq
`.4poouo
`storing device. We may imagine this device to