116
`
`Image and Video Compression for Multimed ia Engineering
`
`TABLE 5.9
`Source Alphabet and Huffman Codes in Example 5.9
`
`Source Symbol Occurrence Probability Codew,ord Assigned Length of Codeword
`
`•
`
`s,
`S2
`S3
`s~
`S.s
`s6
`
`• t. ,
`
`~-'.,
`.
`j S1 ( 0:.3 )
`•
`:!J
`I
`· s, ( 0..%5)
`~
`: l
`. ., S3 ( 0.20)
`
`4
`• , SSA ( 0.1°5 )
`
`0.3
`0.1
`0.2
`0.05
`0.1
`0.25
`
`00
`IO I
`.
`l l
`1001
`1000
`01
`
`2
`3
`2
`4
`4
`2
`
`l
`
`•
`
`--~-----.-(cid:173)
`s. ( 0.3·)
`MUS)
`
`S1 ( 0.3)
`s, (0.25)
`
`S( 1.0)
`
`0, SM IJ ( OAS ,-..,
`1
`
`•
`
`•
`
`•
`
`•
`
`~f 0.20)
`
`'
`
`1
`
`l
`
`•
`
`1....
`
`" =· .
`
`7
`
`~
`J
`
`FIGURE 5.1 Huffman coding procedure in Exampl e 5.9.
`
`5.2.2.1 Procedures
`
`In summary, the Huffman coding algorithm consists of the following steps.
`
`I. Arrange all source symbols in such a way that their occurrence probabilities are in a
`nonincreasing order.
`2. Combine the two least probable source symbols:
`• Form a new source symbol with a probability equal to the sum of the probabilities
`of the two least probable s·ymbols.
`• Assign a binary O and a binary I to the two least probable symbols.
`3. Repeat until the newly created auxiliary source alphabet contains only one source symbol.
`4. Start from. the source symbol in the last au~iliary source alphabet and trace back to each
`source symbol in the original sou.rce alphabet to ·find the corresponding codewords.
`
`s.2 .. 2.2 Comments
`
`First, it is noted that the a.ssignment of the binary O and I to the two least probable source symbols
`in the original source alphabet and each of the first (u - 1) auxiliary source alphabets can be
`implemented in two different ways. Here u denotes the total number of the auxiliary source symbols
`in the procedure. Hence, there is a total of 211 possible Huffman codes .. In Example 5.9, there are
`five auxiliary source alphabets, hence a total ,of 25 = 32 different codes. Note that each is optimum:
`that is, each has the same average length.
`Second, in sorting the so·urce symbols, there may be more than one. symbol having equal
`probabilities. This results in multiple arrange,ments of symbols., hen.ee multiple Huffman codes .
`While ail of these Huffman eodes are optimum, they may have some other different properties.
`
`IPR2021-00827
`Unified EX1008 Page 142
`
`

`

`Variable-Lengtl1 Coding: Informa tion Theory Results (11)
`
`117
`
`For instance, sorne Huff111an codes result in tl1e minirnun1 codeword length variance (Sayood, 1996).
`Tt1.is property is desired for appl icalions in \.vhicl1 a constant bit rate is requ.ired.
`Third, Huf fman coding ca,, be applied to r-ary encoding with r > 2. Tt1at is, code symbols are
`r-ary \Vitl1 ,. > 2.
`
`5.2.2.3 Applications
`
`As ,1 systemati c procedure to cr1code a ti ni le discrete n1en1oryless source, the Hu ffrnan code has
`found wide application in image and video coding. Recall tl1at it has been used i11 di·fferential
`coding and tr,tnsf'o11n coding. In transfonn coding, as introduced i11 Cl1apter 4, the magnitude of
`the quantized tra11sfo1m cocfficjenls and tl1e run-1engtl1 of zeros in the zigzag scan are encoded by
`usi11g the Huff man code. Tl1i l1as been adopted by both still image and video coding standards.
`
`5.3 MODIFIED HUFFMAN CODES
`
`5.3.1 MOTIVATION
`
`As a result of Huffn1an codi11g, a set of all tl1e code\vords, ca11·ed a codebook, is created. It is an
`agreen1ent between Ll1e transn1itter and the receiver. Co11sider tl1e case where tl1e occurrence
`probabiliti es are skewed, i.e., some are large, while sorne are small. Under tl1ese circumslances,
`the improb able SOL1rce sy111bols take a disproportionately large amount of memory space in tl1e
`codebook. The size of the codebook w.ill be very large if the nu1nber of the improbable source
`symbols is large. A. large codebook requires a large memory space and increases tl1e computatjonal
`complexity. A n1odified Huff,nan procedure was tl1erefore devised in order to reduce tl1e n1en1ory
`requirement wl1i le keeping al most tl1e san1e optimality (Hankarner, I 979).
`
`Example 5.10
`Co11sider a source alphabet consisting of 16 symbols, eacl1 b.eing a 4-bit binary sequence. That is,
`S == {s,, i == 1,2,· ··,16 } . The occurrence probabilities are
`
`p(.s·,) = p(.r2 ) = 1/ 4,
`p(s3) = p(s4 ) = · · · = p(s,6 ) = 1/ 28.
`
`The source entropy can be calculated as follows:
`
`/-/(S) =2 · _ _!_loo. ! +14 ·
`4
`02 4
`
`-
`
`I
`1
`loo
`'02 28
`28
`
`= 3 .404 bit.s· pe,· S) 1111.bol
`
`Applying the Huffman coding algorith1111 we find tl1at the codeword lengths assoc,iated \Vith
`the symbols are : / 1 = /2 = 2, [3 = 4, and [4 = /5 = ... = !16 = 5, \Vhere L; denotes the length of the ith
`codeword. The average lengtl1 of Huffn1an code is
`
`'
`
`16
`L = t' p(s.)l. = 3.464 bits pe1· S) 1nzbol
`,L..J
`, 1
`i=l
`
`avg
`
`We see that tl1e average length o:f HufTman code is quite close to tl1e lower e11tropy bound. It is
`noted, 'however, that the required codebook mer11ory, M (defin.ed as the sum ot· tl1e code,vord lengths),
`is qu,ite large:
`
`IPR2021-00827
`Unified EX1008 Page 143
`
`

`

`118
`
`Image and Video Con11Jression for Multim edia E11gin eeri ng
`•
`
`16
`
`M = L l; = 73 bi ts
`
`i =l
`
`This number is obviou,s·Iy larger tl1an the aver.age codeword lengtl1 multipli·ed by tl1e 11un1ber or
`code\vords. This sl1ould not come as a su1-prise since tl1e average l1ere is in tl1e statistical se11se i nste,id
`of i11 the aritl1metic sense. When tl1e total nun1ber of i111probable sy111bols incre()ses, tl1e reqt1ired
`eodebook n1en1ory space \Viii increase dramatically, res.ulling in a great dem,1nd on men1ory space.
`
`5.3.2
`
`ALGORITHM
`
`Consider a source alpl1abet S tl1at consists of 2\' bi11ary seque11ces, each of lengtl1 i,. In otl1er \vords.
`each source sy1nb0I is a v-bit codeword in tl1e 11atural bi 11ary code. Tl1e occurrence probabi Ii ties
`are l1ighly skewed and there is a large nu111ber of improbable sy1nbols in. S. The 111odificd HL1ffn1a11
`codin·g algoritl1m is· based on the follo\ving idea: lun1ping all tl1e in1probable source sy,nbols ir1to
`a category nam·ed ELSE (Wea\1er, 1978). The algoritl1m is described below.
`
`l. Categorize the source alpl1abet S into tvvo disjoint groups, S 1 and S2, sucl1 ll1at
`
`S=
`I
`
`and
`
`s. p(J'.) > 1
`? \' -·
`
`I
`
`I
`
`(5 . 17)
`
`(5. 18)
`
`I
`s? = · s. p(s.) ~ -
`2 \'
`
`I
`
`I
`
`•
`
`2. Establisl) a source symbol ELSE with its occurrence probability equal to p(S2).
`3. Apply the Huffman coding algorithn1 to th.e source alphabet S3 with S3 = S1 U ELSE.
`4. Convert the codebook of S3 to that of .S as follo\VS.
`• Keep tl1e same codewords for Ll1ose symbols in S1•
`• Use the codeword assigned to ELSE as a prefix for tl1ose symbols in S2 •
`.
`
`5.3.3
`
`CODEBOOK MEMORY REQUIREMENT
`
`Codebook memory M is the sum of the codeword lengths. The .M required by Huffman, coding
`with respect to tbe original source alphab.et S is
`
`ieS
`
`ieSi
`
`(5.19)
`
`whe.r:e f; denotes the len.gth of tl1e ith codew0rd, as de·fined previou-sly. In the cas·e of the modified
`Huffman ood.ing algorithm, the memory req-uired M,,,H is
`
`•
`
`(5.2.0)
`
`where tELS·E is the length of the codewoud assig11e·cl to ELSE. The above equation reveals tl1e ~ig
`sayings in memory Fe.quirement when Che probability is s·kewed. The f0llowing exa,mpJe is used Lo
`illustrate the modified Huffman coding algorithm and the resulting dramatic memory savings.
`
`IPR2021-00827
`Unified EX1008 Page 144
`
`

`

`Variable-Lengtn C.oding: Information Theory Results (11)
`
`119
`
`ELSE ~
`2
`
`ELSE !
`2
`
`l
`s, -
`4
`
`1
`s, -
`4
`
`0
`t-------=-
`I
`
`I
`S1.2 -
`2
`
`0
`
`I
`
`FIGURE 5.2 Tl1e modified Huff111an coding procedure in Exa111ple 5.11.
`
`Example 5.11
`In this exar11ple, we apply tl1e 111odified Huffmar1 coding algorithm to the source alphabet presented
`in Ex,1m.ple 5. 10. We first lu111p the 14 sy111bols having the least occurre11ce pro.babilities toge.tl1er
`to form a new sy,nbo1 ELSE. The probability of ELSE is the s·u1n of tl1·e l 4 probabilities. That is,
`
`•
`
`p(ELSE) = * · 14 = ~-.
`~-
`-
`Apply Huffma11 cod,ir1g to the new source alphabet S3 -= { s 1, s2, ELSE}, as sl1own in Figure 5 .2.
`Fron1 Figure 5.2, it is seen that the codewords assigned to syn1bols s 1, s2, and ELSE, respectively,
`are 10, 11, and 0. He11·ce, for every source syn1bol lun1ped into ELSE, its codeword is O followed
`by tl1e original 4-bit binary sequence. Therefore, M,,,H = 2 + 2 + I = 5 bits, i.e., tl1e required
`codebook 1nemory is only 5 bits. Co1npared with 73 bits required by Huffman coding (refer to
`Exam·ple 5.10 ), there is a savings of 68 bits in codebook memory space. Similar to the coinn1ent
`made in Example 5.10, the n1en1ory savings \\1ill be ·even larger jf' tl1e probability distribution is
`ske\ved inore severely and the number of in1probable symbols is larger. The average length of the
`Lf = ~4 • 2 · 2 + ~ · 5 · J 4 = 3.5 bits pe,· S) 111i,bol. This demonstrates
`
`modified Huffn1an algorithm is L
`tl1at modified H1.,1.ff1nan coding retains almost tl1e san1e cod.ing efficiency as tl1at acl1ieved by
`Huffman coding.
`
`._.
`
`(II '.~ .Ill r .
`
`1
`
`- o
`
`5.3.4
`
`BOUNDS ON AVERAGE CODEWORD LENGTH
`
`It has been shown that the average length of the n1odified Huffman codes satisfies the followjng
`condition:
`
`•
`
`H(S) ~ Lavg < H(S) + 1- p log2 p
`
`(5.21)
`
`where p = r.s, e s
`/J(:S,). It is seen tl1at, con1pared witl1 tl1e 11oiseles .. s source coding theorem, tl1e upper
`bou·nd of· tl1e code averag.e length is increased by a quantity of -p log2 p. In Example 5.11 it is
`seen tl1at tl1e average Iengtl1 of 1J1e 1nodified Huffmar.1 code is close to that acJ1ieved by the Huftinan
`code. Hence the modified Huffrnan code is aln1ost optin1um.
`
`2
`
`5.4 ARITHMETIC CODES
`
`Arithn1etic coding, whicl1 is quite differe11t fron1 Huffn1ao coding, is gainin,g increasing p0pL1larity.
`In this seotion, we" will first analyze the Jimitatior1s of Huffn1ar1 coding. Then Ll1e principle of
`arith1netic coding will be introduced. Fi11ally some irnplementation ·issues are discussed briefly.
`
`IPR2021-00827
`Unified EX1008 Page 145
`
`

`

`120
`
`Image and Video Compression fo.r Multimedia Engineering
`
`5.4.1
`
`. LIMITATIONS OF HUFFMAN CODING
`
`As seen in Section 5.2, Huffman coding is a systematic procedure t·or e11codi11g a source alpl1abet,
`,vith each source syn1bol having an occurrence probability. U11der tl1ese circun1slances, Huffn1an
`coding is opti1nun1 in the ser1se tl1at it produces a n1inin111111 codi11g redunda ncy. ll l1as been shown
`tl1at the a,,erage codeword lengtl1 acl1ieved by Huffman coding satisfies lhe fol low i 11g inequa lity
`(Gallagher, 1978).
`
`H(S) ~ La,•g < H(S) + f)m ux + 0.086
`
`(5.22)
`
`\Vl'1ere H(S) is the entropy of the source alphabet, and Prrlli:r. denotes the max in1u111 occurrence
`probability in the set of the source symbols. Tl1is inequality in1plies tl1at tl1e upper bot1nd or the
`average codeword length of Huffn1an code is deter111ined by the entropy and tl1e n1axin1urn occur(cid:173)
`rence probability of the source symbols being encoded.
`In the case ,vhere the. probability distribution among source symbols is skc\ved (son1e proba(cid:173)
`bilities are small, \vhile some are quite large), tl1e upper bound may be large, in1plyi11g tf1at tt1e
`coding redundancy may not be small. Imagine the follo\ving extreme situation. Tt1ere c1rc only l\VO
`source symbols. One has a very small probability, \Vl1ile tl1e other has a very large probability (very
`close to 1 ). Tl1e entropy of tJ1e source alphabet in this case is close to O since the uncertainty is
`very small. Using Huffman coding, however, \:Ve need tvvo bits: 011e for eacl1. That is, tl1e average
`codeword length is 1, whicl1 means t11at tl1e redunda11cy is very close to 1. Tl1i. agrees \Vitl1
`Equation 5.22. This inefficiency is due to tl1e fact Ll1at Huffn1a11 coding always encodes a source
`symbol with an integer number of bits.
`The noiseless coding tl1eorem (rev.ie\:ved in Section 5.1) indicates tl1at the average code\vord
`length of a block code can approacl1 the source alphabet entropy \Vhen the block size approaches
`infinity. As tl1e block size approaches infi.nity, tl1e storage required, the codebook size, and the
`coding delay will approach infinity, 110\veve.r, and the complexity of Lhe coding will be out of cont rol.
`The fundame.ntal idea behi·nd Huffman coding and Shannon-Fano coding (devised a little earlier
`than Hu·ffrnan coding [Bell et al., 1990]) is block coding. Tl1at is, some codeword havi11g a,1 integral
`number of bits is assigned to a source symbol. A message may be encoded by cascading tl1e relevant
`codewords. It is the block-based approach that is responsible for the limitations of Huffman codes.
`Another limitation is that when encoding a message that consists of a sequence of source
`symbols, the nth extension Huff man coding needs to enumerate all possible sequences of source
`symbols having the same length, as discussed in coding the ,ith extended source alphabet. This is
`no.t computationally efficient.
`Quite different from Huffman coding, arithmetic coding is streani~based. It overcomes tl1e
`drawbacks of Huffman coding. A string of source symbols is encoded as a string of code symbols .
`Hence, .it .is free of the integral-bits-per-source symbol restriction and is more efficient. Arithmetic
`coding n1ay reach the theoretical b.ound to coding efficiency specified in tl1e noiseless source codir1g
`theorem for any inforrnation source. Below, we introduce the principle of arithmetic cod ing~ t·rom
`which we can see the stream-based nature of arithmetic coding.
`
`5.4.2
`
`PRINCIPLE OF ARITHMETIC CODING
`
`To und.erstand the different natures ot· Huffman coding and arithmetic coding, let us look at
`Example 5.12, where we use the same source alphabet and the associated occurrence probabilities
`used i'n ExampJe 5.9. In this example, however, a string of source symbols s1s2s3.s·4s5s6 is encoded.
`Note that we consider the ter1ns stri11,g and streanz to be slightly different. By stream, we mean a
`message, or possibly seve.ral mes.sages, wh.ich may coHespon.ti to qu,ite a 1011g sequence of source
`sym1bols. ~oreover, stream gives a dynamic ''flav,or;'' Later on we will see that arithmetic coding
`
`•
`
`IPR2021-00827
`Unified EX1008 Page 146
`
`

`

`Variable-Length C.odin g: Inform ati on Theory Result s (11)
`
`•
`
`121
`
`TABLE 5.10
`Source Alphabet and Cumulative Probabilities in Example 5.12
`
`Source Symbol
`
`Occurr ence Probability
`
`Associated Subintervals
`
`SI
`S2
`SJ
`S4
`S5
`S6
`
`•
`
`0.3
`0. 1
`0.2
`0.05
`0. 1
`0.25
`
`[O. 0.3)
`(0.3. 0.4)
`[0.4. 0.6)
`[0.6. 0.65)
`[0.65. 0. 7 5)
`[0.75. I .0)
`
`CP
`
`0
`0.3
`0.4
`0.6
`0.65
`0.75
`
`is implemented in an increme ntal n1anner. Hence stream is a suitable term to use for arithmetic
`coding. In this exa111ple, however, only six source symbols are involved. Hence \Ve consider the
`ter.1n .st,·i,zg to be suitab le, ain1ing at distinguishing it from the term block.
`
`Example 5.12
`The seL of six source sy1nbols and their occurrence probabilities are listed in Table 5. 10. In this
`exan1ple, the st1-ing Lo be encoded usir1g aritl1meric codi.ng is s 1.s·2s~s4.s·5s6 . In tl1e following four
`subsec tions we will use this examp le to illustrate the principle of arithn1etic coding and decodi.ng.
`
`5.4.2.1
`
`Dividing
`
`Interval [O, 1) into Subintervals
`
`As pointed out by Elias, it is not necessary to sort out source symbols according to their occurrence
`probabiliti es . Therefore· in Figure 5.3(a) the six symbols are arranged in their natural order, from
`symb ols s 1, s2 , ··· ,u p to s6 . The real interval between O and I is divided into six subintervals, each
`havin g a length of p(s;), i = 1,2,·. -,6. Specifically, the interval denoted by [0, 1)
`\vhere O is
`includ ed in (the left end is closed) arid 1 is excluded from (the right e·nd is open) the interval -
`is divid ed into six subintervals. The first subinterval [O, 0.3) corresponds to s 1 and I1as a length of
`P (s 1), i.e., 0 .3. Sin1ilar]y, the subinterval [O, 0.3) is said to be closed 0 11 tl1e le.ft and open on the
`right . The remaining five subintervals are sin1ilarly constructed. All six subintervals thus forn1ed
`are disj oint and their union is equc1l Lo tlie i11terval [0, 1 ). This is because the su1n of all the
`probabiliti es is equal to I.
`_ We list the sum of the preced,i ng probabi I ities, known as c1111111/ati've p1·obability (Langdon,
`1984) , in tl1e right-n1ost column of Table 5. 10 as \veil. Note tl1at tl1e concept of cumula tive prob(cid:173)
`ability (CP) is slightly diffe rent from that of cun1ulative distribution functio11 (CDF) in probability
`theory . Recall that in the case of discrete randon1 variables the CDF is defined as follows .
`
`The CP is defined as
`
`•
`I
`
`CDF(s;) == L,p(si)
`
`J:: I
`
`i - 1
`
`CP(s;)= L,p(sj)
`
`j= I
`
`(5.23)
`
`(5.24)
`
`where CP(s 1) = O is defined . Now we see eac,h subinterval l1as its lo\ver end point located at CP(s;).
`Tbe width of. each subinterval is equal to tl1e probability of the corresponding sou1·ce symb 0l .. A
`sqb'interval can be completely defined by its lower end point and its width. Alternatively, it is
`
`IPR2021-00827
`Unified EX1008 Page 147
`
`

`

`122
`
`Image and Video Compression for Multimedia Engineering
`
`0
`
`(a
`
`0.3
`
`0.4
`
`0.6 0.65
`
`0.75
`
`1.0
`
`[ 0, 0.3)
`
`l o.3. o:4>, l o;4, o.6)
`
`[ 0.75, 1.0)
`
`(b)
`
`I'
`
`0
`
`(c)
`
`0.09
`
`(d)
`
`• 0.102
`
`(e)
`
`•
`
`0.1056
`
`(f)
`
`O.IOS795
`
`[ 0.6, 0.65)
`
`( 0.65, 0.75)
`
`0.09 S2 0.12
`
`0.18
`
`0.195
`
`0.225
`
`[ 0.09. 0.12)
`
`0.®9
`
`0. 102
`
`0. 108
`
`0.1095 0.1125
`
`[ 0. 102. 0. 108)
`
`0. 1083
`
`0.1044
`I
`
`0.1056 0.l059
`
`0.1065
`
`----------------1([(>.0
`
`. l 056. 0.J 059
`
`•
`
`0.10569
`I
`
`0.10572
`I
`
`0.10578 0.105795 0.105825
`
`I ___.
`G)
`
`( 0.105795, 0.105825)
`
`,Q.105804
`
`0.105807
`.
`
`0.105813 0.1058145 0.1058175
`
`0.3
`
`0. 12
`
`•
`
`0. 108
`
`•
`
`0. 1059
`
`@ 0.1058250
`
`[ 0.1058175, 0.1058250)
`
`FIGURE ·S.t3 Aiiithmetic coding working on the same source alphabet as that in Example 5.9. Tl1e encoded
`symbol srring is s·1 S.2 S3 S4 S5 S6•
`
`•
`
`deterrnined by its two end l)Oints: the lower and upper end points .(sometimes also called the left
`and right end peints) .
`Now we consider encoding the string of source symbols s1s2s3s4s5s6 with the arithmetic coding
`method.
`
`5.4.2.2
`
`~ncoding
`
`Encoding tb.e F:irst Source Symbol
`Refer to Figure 5.3(a). Since the first symbol is Si, .we pjck up its subinterval (0, 0.3). Pic~ng up
`the subinterval [0, 0.3) means that any real number in the subinterval, i.e., any real number equal
`to or greater th·an Cl and smaller than Q.3, c'an be a pointer to the subinterval, thus representing
`the
`source symbol s 1• This can be justified by considering that all the six subintervals are disjoint.
`:EocQdiog .the Second Saurce Symbol
`Refer to Figu .re 5.3(b ). We use the same pfoc.edure as used jn_ part {a) ro div,ide the inter.v-al [O, 0.3)
`into six ·suointervals ~ Sin.ce the seeo,nd symbol t.0 be encoded is s2, we pick up its subinterval [0.09,
`C). J~ ).
`
`IPR2021-00827
`Unified EX1008 Page 148
`
`

`

`Variable-Len gth Codin g: Informati on Tl1eory Results (11)
`
`123
`
`. Notice that the subintervals are recursively generated fron1 part (a) to part (b). It is known that
`an interval n1ay be con1pletely specified by its lower end point and width. Hence, the subinterval
`recursion in the arithmetic coding procedure is equivalent to the following two recursions: end
`point recur sion and width recursion.
`From interval [O, 0.3) derived in part (a) lo· interval [0.09, 0.12) obtained in part (b), we can
`c.onclude the follo\.ving lower end point recursion:
`
`L =L
`c11r r en1
`
`/I t' ll '
`
`+W
`
`· CP
`c11r rt! 11t
`
`t1t' 1I'
`
`(5.25)
`
`where L11,.:1r, L,.,,,,."n' represe nt, respectively, tl1e lower end points of the new and current recursions,
`and the ~ 11,.,1:,i, and Lhc CP,,e11 denote, respectively, tl1e \vidth of the interval in the current recursion
`and the cumulative probabiljty in the new recursion. The width recursion is
`
`W = W
`
`nt'11·
`
`curren t
`
`· p(s)
`i
`
`(5 .26)
`
`\.vhere W,,e11. , and p (si) are, respectively,. tl1e width of the new subjnterval and tJ1e probability oft.he
`source symb ols·; that is being encoded. These two recursions, also called double recursion (Langdon,
`1984 ), play a central role in arithmelic coding.
`
`Encoding the Third Source Syn1bol
`Refer to fjgur e 5.3(c). When the third source symbol is encoded, the subinterval gerierated above
`in part (b) is similarly divided into six subintervals. Since the third symbol to encode js s3 , its
`subinte1-val [0. 102, 0. 108) is picked up.
`
`Encoding the Fourth, Fifth, and Sixth Source Symbols
`Refer to Figur e 5.3(d,e,f). The subinterval division is carried out according to Equation s 5.25 and
`5.26. The symbols s4
`, s5 , and s6 are encoded. The final subinterval generated is [0.1058175,
`0.1058250) .
`That is, the resulting subinterval [0.1058 J 75, 0.1058250) can represent the source symbol string
`s,s 2s3s4s5s6 . Note that in this example decimal digits instead of binary digits are used. In binary
`arithmetic coding , lhe binary digits O and 1 are used.
`
`5.4.2.3 Decoding
`
`As seen in this exan1ple, for the encoder of arithmetic coding, the input is a source syn1bol string
`and the output is a subi.nterval. Let us call tl1is the final subinterval or the resultant subinterval.
`Theoretically, any real numbers in tl1e interval can be the code string for the ir1put syn1l:>ol string
`since all subint ervals are disjoint. Often, ho\vever, the lower end of the final st1binterval is used as
`the code string. Now let us examine 110w tl1e decoding process is carried out with the lower e11d
`of the final subinterval .
`Decoding sort of reverses what encoding t1as done. The decoder k.nows the encoding procedure
`and therefore has tl1e inforrnatior1 contained in. Figure 5.3(a). It con1pares the lo\ver end point of
`the fin.al subinterval 0.1058175 with all the end points in (a). It is determined that O < 0.1058175 <
`0.3. That is, the lower end falls i11to t11e subinterval associated with the· symbol s,. Therefore, tl1e
`symbol s 1 is first decoded ..
`Once the first symbol is decoded, the decoder may know tl1e· partition of subintervals sl10\vn in
`Figure 5.3(b). It is then d·ete·rn1ii1ed that 0.09 < 0.1058175 < 0. 12. That is, the lower e11d is contained
`in the subinterval corre_sponding to tl1e symbol s2 . As a result, s2 is the second decoded sy1nbol.
`The procedure repeats itself until all six symbols are dee.oded. That is, based on Figure 5.3(c) ,
`it is found that 0.102 < 0.1058175 < 0.108. The syn1bol s3 is decpded. Then, the S) 1r11.bols s4 , s5, s6.
`are subsequently decoded because the following inequalities are determi11ed:
`
`IPR2021-00827
`Unified EX1008 Page 149
`
`

`

`12~
`
`I
`
`•
`
`Image and Video Compre ssion for Multim edi a Engin-eerin g
`
`0.1056 < 0.1058175 < 0.1059
`
`0.105795 < 0. 1058175 < 0.1058250
`
`0.1058145 < 0.1058175 < 0. 1058250
`
`Note that a term.inal syn1bol is necessary to infonn the decoder to stop decoding.
`The above procedure gives us an idea of how decoding works. The decoding process, however,
`does not need to construct parts (b), (c), (d), (e), and (t) of Figure 5.3. Instead, the decoder only
`nee·ds the infot u1ation conta.ined in Figure 5.3(a). Decoding can be split into the following three
`step.s.: co11ipariso,i, ,·eadjustnzetit (subtraction), and scali1zg (Langdon, 1984).
`As described above, through comparison we decode the first syn1bol s 1• From the \vay
`Figure 5.3(b) is constructed, \Ve know the decoding of s2 can. be accon1plished as follows. We
`subtract the lower end of the subinterval associated with s I in part (a), tl1at is, 0 i.n this example ,
`from the lower end of the final subinterval 0.1058175, resulting in 0.10 58 175. Tl1en \Ve divide c'his
`number by the width of the subinterval associated \Vith s 1, i.e., the probability of s 1, 0.3 , resulting
`in 0.352725. Looking at part (a) of Figure 5.3, it is found that 0.3 < 0.352725 < 0.4. Tl1at is , the
`nu.mber is within the subinterval corresponding to s2• Therefore the second decoded symbo l is s1 .
`Note that these three decoding steps exactly ''undo'' wh at encoding did .
`T0 decode the third syn1bol, we subtract the lo\ver end of the subinterval w ith .s·2 , 0.3 fron1
`0.352725, obtaining 0.052725. This number is divided b.y the probability of s 2 , 0 .1, resulting in
`0.52725. The comparison of 0.527 25 with end points in part (a) reveals that the third decode d
`symbol is s3 •
`In decodjng t'he fourth sympol, \Ve first subtract the lo\ver e11d of the s 3's subinterval in part (a),
`0.4 from 0·.52725, getting Q.12725 . Dividing 0. 12725 by the probability of s3 , 0.2, . results in 0. 63625.
`Referring to part (a), we decode the fourth symbol as s4 by comparison.
`Subtraction of the lower end of the subinterval of s4 in part (a), 0 .6, from 0 .63625 leads to
`0.0 .3625. Division of 0.03625 by the probabilit y of s4 , 0.05 , produces 0.725 . T he comparison
`oet\veen Q.725 and the end points in part (·a) de.codes the fifth symbol as s5 .
`Subtracting 0.725 by the lower end of the subinterval associated with s 5 in part (a) , 0.65, gives
`0.075. Dividing . 0.075 by the probability of s5, 0. 1, generates 0.75 . The comparison indicates that
`the sixth decoded symbol is sc,·
`In summary , c0nsidering the way in which parts (b), (c), (d), (e), and (f) of Figure 5.3 are
`constructed, we see that the three steps discussed in the decoding process: comparison., readjustment,
`a:nd scaling, exactly ''undo'' what the encoding procedure has done.
`
`•
`
`5.4.2.4 Observations
`
`Both encoding a.nd decoding involve only arithmetic operations (addition and multiplic ation in
`encoding, suotraction and division in decoding) . This explains the name aritl111zet.it codi,ig.
`We see that an input source symbol string s1s2s3s4s5s6 , via encoding, corres.ponds to a subint erval
`[0.1058175, 0.1058250). Any number in this interval can be used to denote tl1e string 0f the source
`sy·mbols.
`We also observe that arithmetic cooing can be carried out in an inc1·eme11tal 1n.anner. That is,
`sou~€ e symbols are fed into the encoder one by one and the fi.nal subinterval is refined continually,
`i.e., the code string is. generated c.ontinually. Furthet 1.nore, it is done in a manner called first ·iii first
`out ·(FlFO). That is, the source symbol encoded first is decoded first. This manner is superior to
`that of last in first ()ltt (LIFO}. This is because FIFO is suitable for adaptation to the statistics o.f
`the S)"mbol string .
`It is obvlaus that the width of the fin·al subinterval becomes smaller and smaller whe.n the le11gth
`of tile sou tce ~ymbol string beco·mes Ja·rger and larg~er. This ca.uses wl1at is known as th.e precision
`
`-
`
`IPR2021-00827
`Unified EX1008 Page 150
`
`

`

`•
`
`Variable-L ength Coding: Inform ation Theory Results (11)
`
`125
`
`proble111. IL is this problem Ll1at prohibited arithmetic coding fro1n practical usage for quite a long
`period of time. Only after this problem w·as solved in the late 1970s, did arithmetic coding be·come
`an increasingly important coding tecl1nique.
`It is necessa ry to have a ter,nination symbol at the end of an input source symbol string. In
`Ll1is way, an arithn1etic codi11g syste m is able to know \Vhen to tem1inate decoding .
`Compared witL1 Huffman coding, aritl1metic coding is quite d.ifferent. Basically, Huffman c9ding
`converts e,1ch source symbol into a fixe .d codeword witl1 a11 integral number of bits, while arithmetic
`codi11g converts a source syn1bol stri11g to a code symbol string. To encode the sarne so.urce symbol
`string, Huffman codi ng can be irnp ]emented in two different ways. One way is shown in Exan1ple 5.9.
`We co nstruct a fixed codeword for eac h source symbol. Since Huffman coding is instantaneous ,
`\Ve ca n cascade
`the co rrespond ing co dewords to form the out put , a l 7-bit co de string
`00.101.11. ·100 1. 1000.0 I, where, for easy reading, tl1e five periods are used to indicate dit:ferent
`codeword.s. As vve see that for the san1e source syn1bol string, the final subinterval obtained by
`using aritl1metic codi 11g is [0. 1058 175, 0.1058250). It is noted tl1at a decimal in binary number
`system , 0.000110 I l 11111 I 1, which is of 15 bits, is equal to the deci111al jn decimal nun1ber system,
`0.10582 11962, which falls into the final subinterval representin.g the string s 1s2s3s4 s5.5'6 • This indi(cid:173)
`cates that, fo.r tl1is examp le, arithn1etic coding is more efficient than Huffamn coding.
`Another way is to forn1 a sixtJ1 extension of the source alpl1abet as discussed in Section 5.1 .4:
`treat ea.ch group of six source syn1bols as a 11ew s·ource symbol; calculate its occurrence pro.bability
`by mult iplyin g the related six probabilit ies; then apply tl1e Huffman coding algorithn1 to the sixth
`exte11sion of tl1e discrete 1ne n1oryless source. Tl1is is called (l1e sixtl1 exte11sion of Huff111a11 block
`code (ret·er to Section 5.1.2.2). In other words, in order to encode the source string s 1s2s3s4s5s6,
`Huffm an coding encodes ,111 of tl1e 66 = 46,656 codewords in tl1e sixth exte11sion ot· the source
`alphabet. Tl1is irnplies a high complexity in implernentation and a large codebook. It is Lherefore
`not efficient.
`Note that we use the decimal fraction in this section. In binary ·arithn1etic coding., \Ve use the
`bin_ary fraction. In (Langdon, 1984) both binary source and code alp11abets are used in binary
`arithmetic coding.
`Similar to the case of Huffman coding, arithmetic coding is also applicable to r-ary encqd ing
`witI1 ,. > 2.
`
`5.4.3
`
`IMPLEMENTATION ISSUES
`
`As me11tioned, the final subi11terval resulti11g fron1 arithmetic encoding of a source symb0l String
`becomes smalJer and smaller as the le11gtl1 of tl1e source symbol String increases. That is, the lower
`and upper bou11ds of the final subinterval be·con1e closer and closer. Tl1is causes a growing precision
`problem. It is tl1_is problen1 that prol1ibited aritl11netic c·od.i11g fron1 practical usage for a long period
`of time. This problem has been resolved and the finite precision arill1n1etic is no\v used in aritl1metic
`coding. This advanc e is due to tl1e incremental irnplementation of arithn1etic coding.
`
`5.4.3.1
`
`Incremental Implementation
`
`Recall Exan1ple 5.12. As source syrnbols co1ne in one by orre, the lo\ver and upper ends· of the
`final subinterval get closer and closer. In Figure 5.3, these lower and upper ends in Exan1ple 5. l2
`are listed. We observe ·that after the third symbol, s3, is ·encoded, tl1e resultant subint erval is [0.102,
`0.108). That is, th-e two most significant decimal digits are tl1e sa111e and tl1ey remain the same in
`the encoaing proces s. Hence , we can transmit these two digits without aft·ecti'ng the final code
`string. At·ter the fourth symbol s4 is encoded,. the resultant subinterval is [0.J 056, 0.1059). That i.s,
`one more. di.git, 5, can be transmitted. Or we say the cun1ulative output is now .105. After the sixth
`sy·mbol is encoded, the final subi11terval is [0.1058175, 0.1058250). TlJe cuniulative output .is 0.1058.
`Refer to Table 5.11. This important observation reveals that we are able to increm.entally transn1it
`output (the code sy1nbols) and receive i11p·ut (the source syn1bols tl1at need to be e11coded).
`
`•
`
`•
`
`IPR2021-00827
`Unified EX1008 Page 151
`
`

`

`126
`
`ln1age and Vide,o Compression for Multi111edia Eng ir1eeri ng
`
`TABLE 5.11
`Final Subintervals and Cumulative Output in Example 5.12
`
`Source Symbol
`s . I
`S~
`-
`S3
`S-1
`Ss
`s6
`
`Final Subinterval
`Upper End
`Lo,ver End
`
`Cun1ulative Outp ,ut
`
`0
`0.09
`0. 102
`0.1056
`0.105795
`0. 1058 175
`
`0.3
`0 .12
`0. 108
`0. 1059
`0. 105825
`0.1058250
`
`-
`0. 10
`0. 105
`0. 105
`0. 1058
`
`5.4.3.2
`
`Finite Precision
`
`With the incremental n1an11er of trans111issio11 of encoded digits and receptio11 of i111Jut source
`·Sytnbols, it is possible to use finite precision to represent tl1e lower and upper bour1ds of tl1e resultant
`subinterval, which gets closer and closer ·as the length of the source symbol string beco,111cs long.
`Instead of floating-point n1arl1, integer inath is us·ed. The potential problen1s kno\vn as u11derfl 0\\1
`and overflow, ho\vever, need to be carefully monitored and controlled (Bell et al.1 199()).
`
`5.4.3.3 Other Issues
`
`There are son1e other problems that need to be handled in in1plen1entation of binary arithn1etic
`coding. T\vo of them are listed belo\v (Langdon and Rissanen, 198 1 ).
`
`Eliminating Multiplication
`The m,ultiplication in the recursive division of subintervals is expensive in l1ardware as \ve11 as
`software. It can be avoided in binary arithmetic coding so as to simplify the implementation of
`binary aritl1metic coding. The id