RX-0731
`
`UNIVERSAL VARIABLE LENGTH CODE FOR DCT CODING
`
`YujiItoh and Ngai-Man Chetmg
`Tsukuba Research & Development Center, Texas Instruments Japan Ltd
`l7 Miyukigaoka-,Tsukuba, Ibamki, 305-0841 Japan
`
`ABSTRACT
`
`A new technique for entropy coding named Universal VLC
`(i.e., UVLC) was developed and applied to motion vector.
`It was shown that UVLC for motion vector coding provides
`good performance in terms of coding efficiency as well as
`error resiliency. In this paper UVLC for DCT coefficient
`coding is presented. The features of the scheme arc:
`l)
`adaptable by parametric representation, 2) support of very
`low bitrate mode and 3) extensible to error resilient mode
`with bi-directionally dccodablc code. This favors stflexible
`image and video coding that should handle a variety of
`picture types and applications. The simulation results show
`that the proposed scheme slightly outperforms several VLC
`tables of existing standards in terms of coding efficiency. It
`is also expected that the proposed scheme can simplify the
`implementation and processing of VLC decoder. It shall
`also be noted that UVLC is being considered as a candidate
`component
`technique
`for
`ITU-T
`i.e.,
`next
`generation video coding algorithm standard.
`
`t
`
`1..INTRODUCTION
`
`is a statistical coding
`Variahledength curling (VLC)
`technique that assigns codewords to values to be encoded.
`Values of high frequency of occurrence are assigned short
`codewords, and those of infrequent occurrence are assigned
`long codewords. On average,
`the more frequent shorter
`codewords dominate such that the code string is shorter
`than the original data. The VLC tables in MPEG-2 [I] and
`H.263 [2], for example, are not Huffman tables in the true
`sense of Huffman coding, but are more like the tables used
`in Group 3 fax. They are entropy constrained, that is, non­
`adaptable and optimized for a limited range of bit rates. A
`better way would be to say that the tables are optimized for
`a range of ratios of hit rate to sample rate (e.g. 0.25
`hit/pixel to 1.0 bit/pixel). It is obvious that DC1‘ VLC table
`of H.263, which is ‘tuned for low bitrate coding, can’t
`readily handle near lossless still picttue coding. Therefore a
`type of configurable VLC is desirable for generic coding
`that should be able to deal with various coding conditions.
`We already invented such VLC technique named Universal
`VLC (UVLC) [3]. The UVLC was applied to motion vector
`coding and gave better error
`resiliency compared to
`
`MPEG-4 Video, whereas the coding efficiency is fairly
`comparable.
`In this paper UVLC for DCT coefficlent coding is
`described. This was mainly designed to handle a wide
`range of bitrates, but has some other merits. The features of
`the scheme sire: 1) adaptable by parametric representation.
`2) support of very low bitmte mode and 3) extensible to
`reversible VLC for error
`resilient coding. Also the
`proposed scheme gives an advantage that
`the VLC
`decoding process can be significantly simplified.
`
`2. CONVENTIONAL VLC FOR DCT
`
`We have investigated the conventional VLC techniques
`employed for existing video coding standards. In DCT
`coefficient coding, a coefficient
`to be coded is usually
`represented in terms of three components;
`last non~zero
`coefficient indication (LAST - ‘0’: there are more non-zero
`coefficients in this block,
`‘l’:
`this is the last non-zero
`coefficient in this block), the number of successive zero
`coefficients preceding the coded coefficient (RUN), and
`magnitude of coded coefficient (LEVEL). It was, then,
`found that
`there are mainly two types regarding VLC
`tables;
`I)
`(LAST, RUN,
`l.F.VEI_.) type in H.263 and
`MPEG-4 [4], 2) {(RUN, LEVEL)+EOB)
`type in H.261,
`MPEG-1 and MPEG-2. Note EOB stands for “end of
`block" which indicates that a coefficient being processed is
`the last coded one in a block. In H.263, for instance, since
`LAST. LEVEL and RUN range [Oil], [-127,
`I27] and
`[0,63], respectively, up to 32K codewords are present in the
`VLC table. Among them, l03 codewords are represented as
`VLC. The remaining combinations of
`(LAST, RUN,
`LEVEL) are represented as escape codes. The escape codes
`are 22 bit word consisting of '7bits ESCAPE, l bit LAST, 6
`bits RUN and 8 bits LEVEL.
`
`3. UNIVERSAL VLC
`
`Fig. l illustrates the structure of UVLC for DCT coefficient
`coding. This looks similar to {(RUN, LEVELHEOB} type
`employed in H.261, MPEG-1 and MPEG-2. But
`the
`proposed method is unique in the sense that RUN and
`LEVEL are coded separately, so it
`is expressed like
`(E()B+LEVEl..+RUN).
`
`
`
`0-vans-6297-7/oo/$10.00©
`
`940
`
`837MED|ATEK000027517
`
`RX-0731.0001
`
`Avago Ex. 2005, Page 1 of 4, Amazon v. Avago, IPR2017-00964
`
`

`

`i‘
`—%—>lE013
`
`level_vl¢ H
`
`run_vlr
`
`code bound
`code boundm-y
`Figure 1. Proposed DCT coefficient coding
`3.1. Adaptability
`The existing coding standards don’t offer configurable
`VLC that is adaptable to distribution of DCT coefficients in
`an on-the-fly fashion. So we set the code length of EOB as
`a parameter, and achieved the adaptability by tuning the
`parameter. This approach is not optimal in terms of coding
`efficiency, however,
`it can provide near optimal efficacy
`while attaining low implementation cost and easy decoding
`process. The EOB was designed to save unnecessary run­
`length codes. MPEG-1 uses EOB of 2 bit length, which
`implies there is an average of only 3 or 4 nonwero AC
`coefficients per block. While in MPEG-2 an "intra VLC
`table" is added, which has been optimized for intra DCT
`block. The "intra VLC table" has a 4 bit EOB code. that
`indicates there should exists 9 - 16 coefficients per block.
`In the proposed scheme, EOB length (named EOB_lcngth)
`is variable so that the VLC table can support various kinds
`of DCT coefficient distribution; hence, various application.
`
`1
`
`l
`
`_xx$x$¥gxx¥xgx;¥¥xxxxx"J_J_
`5Table 2. LEVEL UVLC table (EOB_Iength: 2)
`!evel_vlc
`code
`absolute value of level’ 7
`coarse
`additional
`511°
`
`my
`
`§
`
`1
`
`s
`
`I
`
`l
`
`BOB
`01
`;
`001
`‘
`"xt,“+_2(2:3)
`0001
`l
`“x‘§9"+4 (4:7)
`00001 mxfils
`“x,x‘_:t_u”+8(8:15)
`“x,x,x@”+l6 (16:31)
`x‘x,x ‘Es
`3
`000001
`x x,x,x\§,s
`i
`000000!
`“x43_t3x1x‘_:5,"+32(32:63)
`x_c<,x,x,xs,5
`l
`00000001
`“x,_1£,,x,x,x|3t_u"+64(64:127)
`15
`I
`‘s’ denotes the sign of level. ‘O’for positive and ‘l ' for
`1
`__ negative
`1
`‘ Table 3. LEVEL UVLC table (EOB__length: 3)
`absolute value of level
`1
`Ievel_vlc
`C066
`5
`coarse
`additional
`Si"
`l
`
`ms
`x x
`
`11
`13
`
`s
`
`l
`“x0"+2 (2:3)
`E011.
`“x,5‘,"+4 (4:7)
`“x,x[1t_,,"+8(8:15)
`“it,x,x\§9"+l6 (16:31)
`“X4X‘X,XQ_fi9"+32(32:63)
`“x53t_4x1x,xx "+64 (64:12?)
`
`x x s
`
`01
`
`X ~
`
`‘
`00001
`‘
`;
`‘
`
`ll
`13
`15
`
`001
`0001
`x,x\§9s
`x.x,x,§,s
`000001
`It x x,x\5,s
`0000001
`x<x4x3x;x,x0S
`00000001
`3.2. Very low bitrate mode
`The proposed scheme is also applicable to very low bitrate
`coding. Through the statistical analysis. it has been found
`that the distribution of DCT coefficients is not yet fully
`taken into consideration to further optimize the VLC table.
`The following property will be employed in the proposed
`scheme;
`P[“LAST:1"l
`>
`P(“LAST:O”],
`where
`P{“EVENT”)
`indicates the occurrence probability of an
`event “EVENT”. To prove this, one may attempt to code
`DCT coefficients using the modified VLC table in which
`the meaning of the events “LAST:l” and “LAST:0” are
`exchanged.
`In (LAST, RUN, LEVEL)
`type VLC,
`for
`instance, this is simply done by adding the process LAST =
`LAST91 just prior to coding a coefficient (LAST, RUN,
`LEVEL).
`By applying this modification at very low
`bitrates, one can reduce the bits for DCT coefficients up to
`several percent whenever P(“LAST:l”] > Pl“LAST£0”} is
`guaranteed. This is because conventional VLC tables were
`mostly optimized for such a situation that P{“LAST:1") <
`P[“LAST:0"] like 4xP(“LAST:l") = P{"LAST:0"}. Now
`we propose as follows. Suppose one-bit flag "nEOB”,
`which stand for “negative EOB”. can be tailored in the
`syntax. This flag shall be set by the rule:
`
`With this technique, as many as 32K VLC entries can be
`constructed from a dozen of VLC roots, i.e., coarse code.
`Therefore VLC decoder for the UVLC table only have to
`search one such code among one dozen of candidate codes
`(as compared to 103 candidates for H.263). In addition the
`UVLC doesn‘t have to deal with escape codes. On the other
`hand, the proposed scheme should do the search twice. i.e..
`each for RUN and LEVEL. However. the UVLC can still
`release computations from the decoding process.
`
`rtm_vlc
`comsc
`additional
`
`l
`U1
`001
`l
`it
`0001
`x,xL§u
`00001
`000001 xxlxeo
`000000]
`XX-iK,X‘l(fl
`
`code
`511*‘?
`
`__
`
`value of run
`
`ll
`l
`“xo"+2 (2:3)
`“xQt_0"+4(4:7)
`"x,x‘§0”+8 (3:15)
`“x,x,x‘§0“+l6 (16:31)
`"x4§x,x@”+32 (32:63)
`
`941
`
`if
`nE0B={l
`P(LAST.l}>P{LAST.0}
`0lhETWlSe‘
`O
`Then, just prior to coding a coefficient (LAST, RUN,
`LEVEL) we apply the operation LAST = LAST$nEOB.
`It
`shall be noted that
`this “negative EOB” can be easily
`
`837MED|ATEK00O027518
`
`RX-0731 0002
`
`€
`Avago Ex. 2005, Page 2 of 4, Amazon v. Avago, IPR2017-00964
`
`

`

`Table 5. LEVEL UVLC table in error resilient mode
`
`!evel:_vlr2
`
`is
`H 000
`010s
`
`_
`
`l0__
`12
`
`H absolute value of level W
`l
`EOB
`2
`_
`___
`“x@,"+3 (3:6)
`“i;x¢,"+7 (’I:l4)
`“x1x1xQ_t_u"+l5(l5:3O)
`__ “x@@‘1.”"+3l (3l:62)
`“x<x4l,x,xL&’lfi3 (63: I26)
`
`_
`
`_
`
`My
`
`°><|i.>rr51§
`0x,lx|_l_3_t,;0s
`0x.Qt,]x|_E|,0s
`,,°?€4&¢1"2'Xt.lL‘ti95
`0x.lx4L:_t,lit,lxQ‘,Os
`3.4. Bitstream Syntax
`The bitstrenm syntax at picture and DCT block layer are
`given in Table 6 and 7, respectively.
`Table 6. Syntax at picture layer
`SYNTAX
`
`it HITS
`
`MNEMUNIC
`
`2
`2
`l
`
`bitfirst
`
`uimsbf
`
`it BITS
`
`MNEMONIC
`
`Z-l5
`
`vlclbf
`
`i~l2
`
`vlclb!
`
`2~l5
`
`Z»!5
`
`I- I1
`
`vlrlhf
`
`vlclbf
`
`vlcllsf
`
`l:umin_EOBr..len;zvh
`Chr0m_E0B_ [mink
`nEOB
`
`_l*1tdii.:_\timsbf- 1-insistedi"R nificant
`
`Table 7. Syntax at DCI‘ block layer
`SYNTAX
`
`dm_t~ude(tl
`l.AS'l‘=0
`/"‘IIE(7!l=-0*!
`il'( !r|EOl7) l
`while (l.AS'l‘»=uQl I
`lt'vel_vIr­
`ifllifllii
`l.-AST=l
`else
`nm__vIc
`l I’ while ‘I
`l else I
`l‘nEOB==l‘*I
`while (l..AST=-=0) l
`Iew:!,_v!t‘
`il‘ (BOB)
`leveI_v!c
`else
`LA-5'l%l
`r|m_v!c
`l l"‘ while *1
`/‘ if */
`
`l
`
`ggg vlg ll! -~yggjgh g ggggh gflg,
`
`lgfl mg‘fig]
`
`4. SIMULATION
`
`lfl
`
`In the simulation, we compared the bit consumed between
`the UVLC and the standard VLC employed in the MPEG
`and H.263.
`Figure 3 shows the differences
`in the bit
`consumed to encode DCT coefficients (except intra DC
`coefficicnts) using the UVLC and the MPEG VLC schemes.
`Negative differences mean UVLC consumed smaller
`number of bits than the MPEG VLC. As shown in the
`figure. the UVLC consumed no more than 3% number of
`bits when compared with MPEG VLC while simplified
`significantly the implementation of the VLC codec.
`In
`another simulation, we used UVLC to encode motion
`vectors (Table 8) and DCT coefficients (Table 2 for intra
`chrominance and Table 3 for intra luminance).
`The
`parameter nEOB was set adaptively according to the
`criteria described in the section 3.2. The quantization scale
`was fixed to 15 for intra frame and 20 for inter frame.
`which resulted in adequate visual qualities,
`i.e., 3ldB ­
`
`applied to VLC tables with BOB code such as the proposed
`method as “LAST:1" is identical to "end of block".
`We also apply another technique to save the number of bits.
`ln MPEG the first code of an inter-coded block cannot be
`an BOB. So wc can assign the code of thc EOB (=01,
`when EOB_lcngth=2) and a sign bit to represent the pairs
`(RUN=O, LEVEL:-zlzl) when they are the only pair (i.e.
`coefficient) in a block. The code also signals the end of the
`block. This way we could save about 0.8% number of bits
`in low bit-rate applications, when the pairs (RUN=0,
`LEVEIAM) are often the only run~level pair in a block.
`3.3. Extension to reversible VI.-Cfor error resilient
`coding
`Fig. 2 depicts the structure of reversible (i.e., decodable
`both in forward and backward directions) UVLC in error
`resilient mode. Table 4 and 5 show the UVLC tables for
`RUN and LEVEL, respectively. With this scheme, trpart of
`bitstteam which can't be decoded in the forward direction
`due to errors can be recovered by backward decoding. The
`backward
`decoding
`begins with
`next
`immediate
`resyncltronization word (e.g., start code)
`sought after
`encountering errors, and thcn decode hitstrcam from the
`resynchronization word up to the error portion. This way
`reversible VLC helps
`improve
`error
`resiliency
`for
`image/video compression algorithms employed in error
`prone environments like wireless communication.
`
`runu_vl¢'2
`*-H
`code boundary
`
`level__vlc2 J-}-P
`code boundary
`(a) Forward coding process
`
`i
`
`I
`
`.
`
`4e}-“l7 runWvlc2
`code boundary
`
`l@Wl_\’l¢‘2 14+
`code boundary
`(b) Backward coding process
`Figure 2. Error resilient mode with two~wnydecoding
`
`As observed in the two tables, the same codeword “O00” is
`assigned as EOB. The coarse code appears in even-indexed
`bits such as “l”, “O0”, “O10”, while the additional code is
`represented as a sequence of odd-indexed bits. In other
`words,
`the UVLC code words
`are
`constructed
`by
`interleaving additional code into coarse code. This enables
`the decoding in both directions as illustrated in Fig. 2.
`Table 4. RUN UVLC table in error resilient mode
`run_vlc2
`size
`value of run
`1
`3
`
`1
`0x,,0
`
`0
`
`if "x0"='0', then EOB
`else, run = l
`,_
`
`°9= I
`0x,lx
`1
`0
`0X\lX;lX l
`...Q1<r.L>5;,1.2<1l>tIx ti
`0x,lx,lx.lx,lx
`lx (l
`
`._
`
`V
`
`_.
`
`<2=5)_
`“m"+2
`“x,,x¢9"+6 (6:l3_)__
`“x,§1gl_1§fl"+l4 (14439)
`.i‘>t4snu>.u_n1'it3Q (30115-1),,
`
`“)(.Xq_l§3X77(\£o“-6-62(62:l25)
`
`_ _
`
`942
`
`837MED|ATEK000027519
`
`RX-0731 0003
`
`Avago Ex. 2005, Page 3 of 4, Amazon v. Avago, IPR2017-00964
`
`

`

`D:mm
`
`20
`
`lb
`
`‘um ($1 '
`‘s
`
`4
`
`40 32 28
`
`Di" (‘)1
`°
`
`I
`
`l6
`
`7'; 7-
`
`I2
`
`1‘
`
`-to-1
`
`* ‘
`
`n ti rut-Em nun
`"TI
`_
`i
`~§—
`'
`
`iL
`
`.
`
`om t1ttF'F
`2 --V 2.. § + ~~
`l
`" ’
`f
`'
`
`“
`
`I-Pic
`
`-
`
`..........
`
`i.ti::.'I__|—.'tt$I
`_._...___i_______.._..
`III nutimnpn
`i
`
`om no
`------~
`a
`»~-~—----
`2
`....i ..,..._,._,,..._.. __,
`7*/W
`2
`
`l’-Pt"
`
`---<
`
`‘---
`_
`
`___
`
`5
`'
`
`MPEG-1 Foreman (352x2Bfl;l).5-l.9l\rlb]>s) MPEG-»2Football (7lMxA80:2.5-8.5Mbps) MPEG-2 Flower (704x48tl;8-20Mhps)
`Quantization
`scale
`Wits)
`
`s
`
`4 tnnnpntuenn;
`1
`I
`5 I5
`(W -;-—-
`.,_.,,_w,T
`~"--"’l;;T:;:.-.::.7.;F
`
`fin
`
`25
`
`‘
`
`'7 ff:7'“f'f'i'7i'TT“"“"'}
`ntt Itiutu(Mun!
`,
`
`our (tn
`
`“mm
`
`.,....n..,.,.,........,.
`
`c
`
`on
`s
`
`H14
`
`B-Pit:
`
`U
`
`rt
`
`it
`llt nmgrmep-3 |
`
`.5
`
`2
`
`i
`
`__ _
`
`Iota Mhps)
`
`i
`
`‘
`
`‘P’
`
`i
`
`'
`
`out
`
`tar
`
`"
`
`"i:1;;.
`
`l~Pic
`
`PSNR (dB)
`
`E
`
`5
`
`'
`
`5
`
`t
`
`i"":F"'"""-“ii
`id; turnout mm i
`tdqlfll DD!)
`1"?
`37.5
`3l.7 33.1
`-34.9
`35.7 36.4 36.9 38.2 391
`40.3
`39.l
`36.3
`fi8.l
`sequent» when atu 4 nu mm on-.>. Chmm_,EOB_L0|gllt u nlvmyat2
`no->1 u) Lumih_)F0l_l1myIh is 2 for inter en. and :4for intro rs.-. (~!)ttt‘cptin flower‘
`(1) ln the MPEQ-I toneman sequence. we assign the code ot the EOB (=11!)and ll sign hit to end: the pais (RUN=l>.l.EVEL=:l) when they are the only
`rutvlevel pan In an inter-rotted block.
`Figure 3. Comparing the bit consumed between the UVLC and the MPEG VLC
`33dB. Table 9 summarizes the simulation results in terms
`of the number of bits consumed per frame. Note the value
`represents the average bits consumed per frame (each for
`intm» and intertframe separately) over
`I0 seconds. It
`is
`observed that
`the proposed scheme can reduce the bits
`about 3% for intro frame and 2% for inter frame.
`
`Table 8. Motion Vector (MV) UVLC table
`mv_vlc
`code
`absolute value of dmv
`coarse
`additional
`film
`..L W. .
`
`O
`
`___
`
`“x°"+2 (2:3)
`x s
`001
`0001 xxs
`“XQ_t9"+4(4:7)
`0000]
`x1x¢t,,s
`fi>s1Xm|'.'+3 (81.15).
`“x1x,x,5°"+t 6 (I613!)
`ll
`0O000l_
`x.)t,it,_it0.fs
`‘
`"
`I3
`0000001
`X
`_ mi
`5 .x,x ¢t_,',s
`‘x¢_,x,x|_:_tu+32 (32:63)
`s’ denotes the sign of dmv; '0' for positive and ‘1’ for negative
`Table 9. Simulation result (bits consumed per frame)
`intral
`Test
`WWV’
`VLC table
`'I'Bl..-0
`sequence
`TBL-l
`7inter
`l5,0l9
`intra
`frame
`(+l.l0%)
`inter
`105.2
`92.8
`NM R
`(+l l.4%)
`944,
`. .. .._..__ (""69%)
`intra
`29,660
`29,292
`29.973
`frame
`(t | 23%)
`(~2.2o%)
`(4.48%)
`2277.2
`N/A
`2148.6
`(-2.3l%)
`(+354%)
`TBIA): MPEG 2 DCT coefiicients ?al:§l?ie5
`THE-_1:MPEG2 DCT coefficigtts table one
`
`1 UVLC
`
`15.623} 14,377
`(+5-l5%)
`(-3.22%)
`
`H.263
`14,856
`
`30.347
`
`IIIICI
`
`2199.4
`
`Motherdt
`Daughter
`(352,040)
`
`,
`
`Foreman
`(3574288)
`
`Note
`
`5. CONCLUSIONS
`
`The UVLC for DCT coefficient coding was presented. The
`features of the scheme are:
`l) adaptable by parametric
`representation, 2) support of very low bitrate mode and 3)
`extensible to error resilient mode with bi-directionally
`deeodable code. The simulation results show that
`the
`UVLC slightly outperforms several VLC tables of existing
`standards in terms of coding efficiency. Besides the
`proposed scheme can simplify the implementation and
`processing of VLC decoder. These features and advantages
`can be justified by the fact
`that
`the UVLC is being
`considered for H.26L [5], that is, a next generation video
`coding algorithm standard.
`
`.
`
`6. REFERENCES
`
`[ll
`
`ll]
`
`ITU—TRecommendation H.263, “Video coding for
`low bit rate communication,” March I996.
`ISO/IEJC 13818-2.
`“Generic
`coding
`of moving
`pictures and associated audio information - Part 2:
`Video," November 1994.
`
`[4]
`
`[3] Yuji ltoh, “Bi-directional motion vector coding using
`universal
`VLC,”
`Signal
`Processing:
`lmuge
`Communication, Vol. I4, pp. 541-557, May I999.
`ISOIIEC 14496-2, “Information technology - Generic
`coding of audio-visual objects — Part 2: Visual,"
`October 1998.
`G. Bjontegaard. ”H.26L Test Model Long Term
`Number 1 (TML~l)," ITU-T QJ5/16, Doc. # Ql5—
`1-tso, Sept. 1999.
`
`[5]
`
`943
`
`837MED|ATEK000027520
`
`RX-0731 0004
`
`­
`Avago Ex. 2005, Page 4 of 4, Amazon v. Avago, IPR2017-00964
`
`