`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 1 of 13 Page ID #:238
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EXHIBIT G
`
`EXHIBIT G
`
`
`
`ease 8241400529 Document 1-7 Fuelllllllllllllllilllllllllijllillllllllllliilllillllillllllllfllll
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 2 of 13 Page ID #:239
`SOO6744387B2
`
`(12) United States Patent
`US 6,744,387 B2
`(10) Patent N0.:
`
` Winger (45) Date of Patent: Jun. 1, 2004
`
`
`(54) METHOD AND SYSTEM FOR SYMBOL
`BI ARIZATIO
`N
`N
`Inventor: Lowell Winger, Waterloo (CA)
`
`(75)
`
`OTHER PUBLICATIONS
`Article—Predictive Quantizing Systems by J.B. O’Neil,
`Jr—.Manuscr1pt rece1ved Dec. 27> 1.965'
`.
`.
`Art1cle—A method for the construct1on of M1n1mum—redun-
`
`(73) Assignee: LSI Logic Corporation, Milpitas, CA
`(US)
`
`dancy COdeS by David A- HUffmaH, I10 date.
`Article—A Compressioin Method for Clustered Bit—Vec-
`tors—Oct. 1978.
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 7 days.
`
`Article—pp. 399—401 of the publication entitled IEEE
`Transactions on Information Theory Published 1966.
`* cited by examiner
`
`(21) Appl. No.: 10/191,596
`(22) F'l d
`J l 10 2002
`1 e :
`u .
`,
`(65)
`Prior Publication Data
`
`US 2004/0008769 A1 Jan.15, 2004
`Int. Cl.7 ................................................. H03M 7/00
`(51)
`(52) US. Cl.
`............................................ 341/50, 341/51
`-
`(58) Field of Search ............................ 341/50, 51, 107,
`341/106
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`Primary Examiner—Brian Young
`(74) Attorney, Agent, or Firm—Christopher P. Maiorana PC
`57
`ABSTRACT
`(
`)
`The present invention is directed to an improved method for
`the binarization of data in an MPEG data stream. The
`invention makes use of unary binarization to create code-
`words UP until an index threshold Once the threshold has
`een met, succee 1n co e s m o s
`ave a
`en e
`tot em
`b
`d’ g
`d
`y b 1 h
`pp
`d d
`h
`an eXp-Golomb suffix. This hybrid binarization scheme
`reduces the number of binary codewords to be processed by
`a Binary Arithmetic Coder (BAC), thus reducing the com-
`putation required by the BAC.
`
`5,471,207 A * 11/1995 Zandi
`
`......................... 341/107
`
`6 Claims, 4 Drawing Sheets
`
`14
`
`Encoder
`
`22
`
`18
`
`
`Encoder
`Transport
`System
`
`
`
`Content
`Provrder
`
`
`1 O
`
`(I)
`
`Transmitter
`
`22
`
`12
`
`16
`
`20
`
`24
`
`40
`
`36
`
`32
`
`28
`
`Transmission
`Medium
`
`
`
`
`Decoder
`
`Decoder
`Transport
`System
`
`
`
`Receiver
`
`22
`
`26
`
`38
`
`34
`
`3D
`
`
`
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 3 of 13 Page ID #:240
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 3 of 13 Page ID #:240
`
`P
`
`mE
`
`U_.0E
`
`e
`
`Mm.
`
`hS
`
`4M
`
`
`
`1E3605.M.862829:
`
`m\mm9E
`
`
`
`
`1.,NEmumxwmNqutrcmcmt.tOQmCmLFLOUOOCMLMW>MLQ
`JemuoocmHEo
`
`VNONorN?
`
`mm68000
`
`mmmmmm0v
`
`
`
`
`
`6E236mmm5280”.toamcmfi5880
`
`447,
`
`2Bm
`
`3,onvmmm
`
`
`
`
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 4 of 13 Page ID #:241
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 4 of 13 Page ID #:241
`
`US. Patent
`
`Jun. 1, 2004
`
`Sheet 2 0f 4
`
`US 6,744,387 132
`
`bmsm
`
`o:mE£:<
`
`mcfioocm
`
`N.0."—
`
`:0.ma_
`
`cozmwzcmzoEm
`
`
`
`.Hmemco_.mE.2mcE._.
`
`$52:
`
`cosmELchmF
`
`ucm
`
`86>;
`
`coszzcmso
`
`VP
`
`8:22
`
`cozmmcwaeoo
`
`:96.)—
`
`coszzwm
`
`
`
`
`
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 5 of 13 Page ID #:242
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 5 of 13 Page ID #:242
`
`US. Patent
`
`Jun. 1, 2004
`
`Sheet 3 0f 4
`
`US 6,744,387 132
`
`m.07.
`
`c0222
`
`SammcheOo
`
`
`
`cozmwzcmsdmm.m>c_
`
`
`
`Acozmw=onE>wvmcfioomo
`
`ucm
`
`$52:mhawk“.<$52:.m
`coszcmEo.9::cozmgohmcmt.
`
`
`
`
`
`
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 6 of 13 Page ID #:243
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 6 of 13 Page ID #:243
`
`US. Patent
`
`Jun. 1, 2004
`
`Sheet 4 0f 4
`
`US 6,744,387 B2
`
`FIG. 4
`
`100
`
`Start
`
`102
`
`
`
`Create
`lntial
`
`No
`
`Prefix
`
`106
`
`108
`
`110
`
`104
`
`
`
`
`
`
`
`Add Suffix
`
`
`Bits to Unary
`Prefix
`
`112
`
`
`
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 7 of 13 Page ID #:244
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 7 of 13 Page ID #:244
`
`US 6,744,387 B2
`
`1
`METHOD AND SYSTEM FOR SYMBOL
`BINARIZATION
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to a system and
`method for
`the compression of digital signals. More
`specifically, the present invention relates to reducing the file
`size or the bit rate required by a system using binary
`arithmetic encoding to entropy encode a digital signal such
`as a digital image or digital video.
`
`BACKGROUND OF THE INVENTION
`
`Throughout this specification we will be using the term
`MPEG as a generic reference to a family of international
`standards set by the Motion Picture Expert Group. MPEG
`reports to sub-committee 29 (SC29) of the Joint Technical
`Committee (JTC1) of the International Organization for
`Standardization (ISO) and the International Electro-
`technical Commission (IEC).
`Throughout this specification the term H26x will be used
`as a generic reference to a closely related group of interna-
`tional recommendations by the Video Coding Experts Group
`(VCEG). VCEG addresses Question 6 (Q6) of Study Group
`16 (SG16) of the International Telecommunications Union
`Telecommunication Standardization Sector (ITU-T). These
`standards/recommendations specify exactly how to repre-
`sent visual and audio information in a compressed digital
`format. They are used in a wide variety of applications,
`including DVD (Digital Video Discs), DVB (Digital Video
`Broadcasting), Digital cinema, and videoconferencing.
`Throughout this specification the term MPEG/H.26x will
`refer to the superset of MPEG and H.26x standards and
`recommendations.
`
`Afeature of MPEG/H.26x is that these standards are often
`capable of representing a video signal with data roughly
`1/so‘h the size of the original uncompressed video, while still
`maintaining good visual quality. Although this compression
`ratio varies greatly depending on the nature of the detail and
`motion of the source video,
`it serves to illustrate that
`compressing digital images is an area of interest to those
`who provide digital transmission. MPEG/H.26x achieves
`high compression of video through the successive applica-
`tion of four basic mechanisms:
`
`1) Storing the luminance (black & white) detail of the
`video signal with more horizontal and vertical resolu-
`tion than the two chrominance (colour) components of
`the video.
`
`2) Storing only the changes from one video frame to
`another, instead of the entire frame. Thus, often storing
`motion vector symbols indicating spatial correspon-
`dence between frames.
`
`3) Storing these changes with reduced fidelity, as quan-
`tized transform coefficient symbols,
`to trade-off a
`reduced number of bits per symbol with increased
`video distortion.
`
`4) Storing all the symbols representing the compressed
`video with entropy encoding, which exploits the sta-
`tistics of the symbols, to reduce the number of bits per
`symbol without introducing any additional video signal
`distortion.
`
`With regard to point 4), the symbols may be encoded as
`codewords in a variety of ways. One such encoding is
`binarization. Small codewords are well handled by unary or
`exp-Golomb binarizations while large codewords are best
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`represented with the binarization limited to a reasonable
`length. Thus there is a need for a method and system
`binarization system that retains the most valuable properties
`of the unary and exp-Golomb binarizations. That is, small
`codewords should be distinguishable as with a unary
`binarization, while large codewords should have their bina-
`rization limited to a reasonable length. A binarization that
`simultaneously satisfies these two requirements will reduce
`the complexity and the bitrate/size for compressing and
`decompressing video,
`images, and signals that are com-
`pressed using binary arithmetic encoding for entropy encod-
`ing. The present invention addresses this need.
`
`SUMMARY OF THE INVENTION
`
`invention is directed to a method of
`The present
`binarization, the method comprising the step of determining
`if a code symbol index value is less than a threshold value,
`if so then constructing a codeword using a first binarization
`model; else constructing a codeword using a second bina-
`rization model.
`
`The present invention is also directed to a binarization
`system, the system comprising means for determining if a
`code symbol index value is less than a threshold value, if so
`then utilizing means for constructing a codeword using a
`first binarization model; else utilizing means for construct-
`ing a codeword using a second binarization model.
`The present invention is further directed to a computer
`readable medium containing instructions for binarization,
`comprising instructions for determining if a code symbol
`index value is less than a threshold value,
`if so then
`constructing a codeword using a first binarization model;
`else constructing a codeword using a second binarization
`model.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`For a better understanding of the present invention, and to
`show more clearly how it may be carried into effect,
`reference will now be made, by way of example, to the
`accompanying drawings which aid in understanding an
`embodiment of the present invention and in which:
`FIG. 1 is a block diagram of a video transmission and
`receiving system;
`FIG. 2 is a block diagram of an encoder;
`FIG. 3 is a block diagram of a decoder; and
`FIG. 4 is a flowchart of a process for codeword construc-
`tion.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`By way of introduction we refer first to FIG. 1, a video
`transmission and receiving system, is shown generally as 10.
`A content provider 12 provides a video source 14 to an
`encoder 16. A content provider may be anyone of a number
`of sources but for the purpose of simplicity one may view
`video source 14 as originating from a
`television
`transmission, be it analog or digital. Encoder 16 receives
`video source 14 and utilizes a number of compression
`algorithms to reduce the size of video source 14 and passes
`an encoded stream 18 to encoder transport system 20.
`Encoder transport system 20 receives stream 18 and restruc-
`tures it into a transport stream 22 acceptable to transmitter
`24. Transmitter 24 then distributes transport stream 22
`through a transport medium 26 such as the Internet or any
`form of network enabled for the transmission of MPEG data
`
`streams. Receiver 28 receives transport stream 22 and passes
`
`
`
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 8 of 13 Page ID #:245
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 8 of 13 Page ID #:245
`
`US 6,744,387 B2
`
`3
`it as received stream 30 to decoder transport system 32. In
`a perfect world, steams 22 and 30 would be identical.
`Decoder transport system 32 processes stream 30 to create
`a decoded stream 34. Once again, in a perfect world streams
`18 and 34 would be identical. Decoder 36 then reverses the
`steps applied by encoder 16 to create output stream 38 that
`is delivered to the user 40.
`
`There are several existing major MPEG/H.26x standards:
`H.261, MPEG-1, MPEG-2/H.262, MPEG-4/H.263. Among
`these, MPEG-2/H.262 is clearly most commercially
`significant, being sufficient for all the major TV standards,
`including NTSC (National Standards Television Committee)
`and HDTV (High Definition Television). Of the series of
`MPEG standards that describe and define the syntax for
`video broadcasting, the standard of relevance to the present
`invention is the draft standard ITU-T Recommendation
`H.264, ISO/IEC 14496-10 AVC, which is incorporated
`herein by reference and is hereinafter referred to as “MPEG-
`AVC/H.264”.
`An MPEG video transmission is essentially a series of
`pictures taken at closely spaced time intervals. In the MPEG/
`H.26x standards a picture is referred to as a “frame”, and a
`“frame” is completely divided into rectangular sub-
`partitions known as “picture blocks”, with associated
`“motion vectors”. Often a picture may be quite similar to the
`one that precedes it or the one that follows it. For example,
`a video of waves washing up on a beach would change little
`from picture to picture. Except for the motion of the waves,
`the beach and sky would be largely the same. Once the scene
`changes, however, some or all similarity may be lost. The
`concept of compressing the data in each picture relies upon
`the fact that many images often do not change significantly
`from picture to picture, and that if they do the changes are
`often simple, such as image pans or horizontal and vertical
`block translations. Thus, transmitting only block translations
`(known as “motion vectors”) and differences between pic-
`ture blocks, as opposed to the entire picture, can result in
`considerable savings in data transmission.
`Usually motion vectors are predicted, such that they are
`represented as a difference from their predictor, known as a
`predicted motion vector residual.
`In practice,
`the pixel
`differences between picture blocks are transformed into
`frequency coefficients, and then quantized to further reduce
`the data transmission. Quantization allows the frequency
`coefficients to be represented using only a discrete number
`of levels, and is the mechanism by which the compressed
`video becomes a “lossy” representation of the original
`video. This process of transformation and quantization is
`performed by an encoder.
`Referring now to FIG. 2 a block diagram of an encoder is
`shown generally as 16. Encoder 16 accepts as input video
`source 14. Video source 14 is passed to motion estimation
`module 50, which determines the motion difference between
`frames. The output of motion estimate module 50 is passed
`to motion compensation module 52. At combination module
`54, the output of motion compensation module 52 is sub-
`tracted from the input video source 14 to create input to
`transformation and quantization module 56. Output from
`motion compensation module 52 is also provided to module
`60. Module 56 transforms and quantizes output from module
`54. The output of module 56 may have to be recalculated
`based upon prediction error, thus the loop comprising mod-
`ules 52, 54, 56, 58 and 60. The output of module 56 becomes
`the input to inverse transformation module 58. Module 58
`applies an inverse transformation and an inverse quantiza-
`tion to the output of module 56 and provides that to module
`60 where it is combined with the output of module 52 to
`provide feedback to module 52.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`Binarization module 62 is where the present invention
`resides. Module 62 accepts as input, symbols created by
`module 56 and creates a binary representation of each one in
`of the form of a codeword. The codewords are passed to
`binary arithmetic encoding module 64 where the frequency
`of each codeword is determined and the most frequently
`occurring codewords are assigned the lowest values. The
`output of module 64 is encoded stream 18.
`With regard to the above description of FIG. 2, as those
`skilled in the art will appreciate that the functionality of the
`modules illustrated are well defined in the MPEG family of
`standards. Further, numerous variations of modules of FIG.
`2 have been published and are readily available.
`Referring now to FIG. 3 a block diagram of a decoder is
`shown. Decoder 36 accepts as input decoded stream 34 to
`binary arithmetic decoding module 70. Module 70 decodes
`the binary arithmetic encoding performed by module 64 (see
`FIG. 2) and passes the output to inverse binarization module
`72. Module 72 reverses the binarization of module 62 (see
`FIG. 2) and passes its output to inverse transformation and
`inverse quantization module 74, which reverses the effects
`of module 56 (see FIG. 2). At combination module 76 the
`output from module 74 is combined with the output of
`motion compensation module 78 to create output stream 38.
`The MPEG/H.26x standards define precisely the syntax
`that
`is used for specifying how quantized coefficients,
`motion vectors, and other associated information such as
`block modes are to be represented, as well as the semantics
`for reconstructing video source 14 from the syntax of
`encoded stream 18.
`In particular, codewords such as
`transformed-quantized picture differences and predicted
`motion vector residuals are entropy coded with such
`schemes as variable length codes (e.g. Huffman codes) or
`arithmetic encoding to become the syntax elements that
`form encoded bitstream 18.
`
`types of arithmetic codecs (encoder/decoder
`Several
`pairs) exist. One of the most efficient is the family of binary
`arithmetic coders (BACs). Well-known members of this
`family include, among others,
`the Q-coder, QM-coder,
`MQ-coder, and Qx-coder. A BAC accepts as input a binary
`representation of a codeword and by recursively examining
`the codewords it receives, is able to compress the codewords
`based upon the probability of their frequency.
`Since BACs operate only on binary valued data, a signal
`compression standard such as MPEG-AVC/H.264 maps
`codewords such as transformed-quantized picture differ-
`ences and motion vector residuals to binarized symbol
`representations prior to binary arithmetic encoding.
`Among the commonly used binarization methods are the
`following: unary, binary, Golomb, and exp-Golomb.
`Unary binarization consists of a number of binary 1‘s
`equal to an index for a symbol followed by a zero as shown
`in Table 1.
`
`TABLE 1
`
`Binarization by means of the unary code tree
`
`Symbol Index
`0
`1
`2
`3
`4
`5
`6
`
`0
`1
`1
`1
`1
`1
`1
`
`0
`1
`1
`1
`1
`1
`
`0
`1
`1
`1
`1
`
`Codeword
`
`0
`1
`1
`1
`
`0
`1
`1
`
`0
`1
`
`0
`
`
`
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 9 of 13 Page ID #:246
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 9 of 13 Page ID #:246
`
`US 6,744,387 B2
`
`5
`
`TABLE 1-continued
`
`Binarization by means of the unary code tree
`
`Symbol Index
`
`Codeword
`
`binino.
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`The first column of Table 1 contains an index for a
`
`symbol. The corresponding row for each index contains a
`binarization of the symbol represented by the index into a
`codeword. Thus symbol index “0” results in a codeword of
`a single bit, namely “0”. Symbol “1” results in a codeword
`of “10’, which comprises two bits, and so on. The row
`labeled binino at
`the bottom of Table 1 contains the
`frequency of each bit for a codeword. For example binino
`“1” will contain the number of 0's and 1‘s that occur as the
`
`10
`
`15
`
`first bit of a codeword. Similarly binino “2” contains the
`number of 0's and 1's in the second bit of a codeword, and
`so on.
`
`20
`
`A BAC by examining each binino can determine the
`length and frequency of a codeword by determining if there
`is a zero in the bin. For example binino “5” will contain a
`zero for each codeword having a length of five, thus allow-
`ing the BAC to determine the number or frequency of five
`bit codewords.
`
`The advantage of the unary binarization is that a bin
`containing a value 0 distinguishes a particular codeword
`from all codewords with a larger symbol index. Therefore,
`the BAC can be constructed to separately account for the
`statistical frequency of every individual codeword by main-
`taining separate statistics on the frequency of zeroes and
`ones for every bin. A disadvantage of unary binarization is
`that in practice the statistics of high bins are lumped together
`since the smaller, more frequent codewords account for the
`majority of the bitstream, and infrequently occurring code-
`words do not occur often enough to enable accurate gath-
`ering of statistical data. A major disadvantage of unary
`binarization is that the number of binary values that must run
`through the BAC will, in the worst case, be as many bins as
`the largest symbol index (which may range into the tens of
`thousands). For example, the encoding of a large symbol
`index may require tens of thousands of binary bins to be sent
`through the BAC.
`Binary binarization creates a codeword as a fixed length
`binary representation of the symbol index. Thus symbol
`index “3” is encoded as “11” with the appropriate number of
`leading zeros applied. The disadvantage of binary binariza-
`tion is that a single bin no longer distinguishes each code-
`word uniquely. This results in a greatly reduced compression
`ratio.
`
`Golomb and exp-Golomb codewords, which use a unary
`prefix followed by a binary postfix, may be regarded as
`compromise positions between unrary and binary binariza-
`tions. Golomb codewords with parameter ‘k’ begin with
`unary binarizations as shown by the column labeled MSB
`(Most Significant Bits) in Table 2. Appended to the unary
`binerization are ‘k’ binary bits as is shown in the column
`labeled LSB (Least Significant Bits) in Table 2. This com-
`bination produces 2* *k distinct binerizations for each MSB.
`The example illustrated in Table 2 shows an exp-Golob code
`with k=1, thus the first LSB contains 2**1 values. The next
`levels contains 2*2 LSB values and so on. Unfortunately,
`this still permits extremely long binarizations to occur for
`large symbol indices.
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`
`TABLE 2
`
`Index
`
`Exp-Golomb codes.
`MSB
`
`0
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`
`0
`10
`10
`110
`110
`110
`110
`1110
`1110
`1110
`1110
`1110
`1110
`
`LSB
`
`0
`1
`00
`01
`10
`11
`000
`001
`010
`011
`100
`101
`
`The exp-Golomb code does greatly reduce the maximum
`possible number of bins in the binarization of symbol
`indices. However, it does not permit codewords with a small
`symbol index (other than index 0) to be uniquely distin-
`guished from codewords with larger symbol indices. This
`results in reduced compression ratio for the binarizations,
`relative to the unary binarization of Table 1.
`
`The present invention provides a binarization that retains
`the most valuable properties of the unary and exp-Golomb
`binarizations. That is, small codewords are distinguishable
`as with a unary binarization, while large codewords have
`their binarization limited to a reasonable length. By doing
`so, the present invention provides a binarization that reduces
`the complexity and the bitrate/size for compressing and
`decompressing video,
`images, and signals that are com-
`pressed using binary arithmetic encoding for entropy encod-
`ing.
`
`The present invention allows for the maintenance of a true
`prefix code, while switching between a unary binarization
`for small codeword indices and a modified exp-Golomb
`binarization for larger codewords. The invention prepends a
`fixed prefix to an exp-Golomb code that begins at a fixed
`index value, prior to which unary binarization is used.
`
`Tables 3 and Table 4 demonstrate particular instances of
`this new class of binary codes: hybrid unary-exp-Golomb
`codes. Table 3 illustrates a binerization that is particularly
`appropriate for the binarization of quarter or residual mag-
`nitudes of MPEG-AVC/H.264.
`
`TABLE 3
`
`Motion vector magnitude residual binarization.
`
`Index
`
`Unary
`Prefix
`
`exp-Golomb
`Suflix
`
`0
`1
`2
`
`63
`64
`65
`66
`67
`68
`69
`70
`71
`72
`73
`
`0
`10
`110
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`
`. 1 0
`. 1 10
`. 1 10
`. 1 110
`. 1 110
`. 1 110
`. 1 110
`. 1 1110
`. 1 1110
`. 1 1110
`. 1 1110
`
`0
`1
`00
`01
`10
`11
`000
`001
`010
`011
`
`
`
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 10 of 13 Page ID #:247
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 10 of 13 Page ID #:247
`
`US 6,744,387 B2
`
`7
`
`TABLE 3-continued
`
`Motion vector magnitude residual binarization.
`
`Index
`
`74
`75
`
`Unary
`Prefix
`
`1 .
`1 .
`
`.
`.
`
`. 1 1110
`. 1 1110
`
`exp-Golomb
`Suffix
`
`100
`101
`
`Table 4 is a binarization that is particularly appropriate for
`the binerization of the quantized frequency-transform coef-
`ficient magnitudes (also often called coefficient levels) of
`MPEG-AVC/H.264.
`
`TABLE 4
`
`Coefficient level binarization.
`
`Index
`
`Unary
`Prefix
`
`exp-Golomb
`Suffix
`
`0
`1
`2
`
`15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`26
`27
`
`0
`10
`110
`
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`1 .
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`. 1 0
`. 1 10
`. 1 10
`. 1 110
`. 1 110
`. 1 110
`. 1 110
`. 1 1110
`. 1 1110
`. 1 1110
`. 1 1110
`. 1 1110
`. 1 1110
`
`0
`1
`00
`01
`10
`11
`000
`001
`010
`011
`100
`101
`
`When these binarizations illustrated in Tables 3 and 4,
`bitrate and complexity are both reduced for MPEG-AVC/
`H.264 relative to other known
`
`Adetailed description of the method for constructing such
`hybrid binerization follows. Let N be the threshold at which
`unary to exp-Golomb switching occurs (N=64 for Table 3,
`N=16 for Table 4). The construction of a codeword of this
`modified unary binarization table for a given index v is given
`by the following algorithm:
`If v<N
`
`1) use a unary code of v 1's terminated with a 0
`If v>=N
`
`1) Form an initial prefix of (N—1) 1's;
`2) Determine the number of bits y+1 required to represent
`v—(N—2). For example, for N=64, y=Llog2(v—62)J, and
`put it in a unary representation. The unary representa-
`tion is appended to the initial prefix to form the unary
`prefix as shown in Tables 3 and 4.
`3) Append the y least significant bits of “g” where
`g=v—(N—2)—2**y in its binary representation to the
`prefix.
`4) The corresponding bits obtained at step 3) are shown in
`the exp-Golomb Suffix column of Tables 3 and 4.
`Referring now to FIG. 4, a flowchart of a process for
`codeword construction is shown generally as 100. Process
`100 illustrates the steps of the present invention. Process 100
`begins at step 102 where a test is made to determine if the
`value of the code symbol index is less than the value of the
`threshold. If it is processing moves to step 104 were a unary
`codeword is constructed comprising a series of v 1‘s termi-
`
`8
`nated with a 0. Processing then ends at step 112. Returning
`to step 102 if the test is negative, processing moves to step
`106, where an initial prefix of N 1‘s is created. Processing
`then moves to step 108 where the most significant bits of the
`value v—(N—2) are extracted and converted to a unary
`representation. The unary representation is then appended to
`the initial prefix to create a unary prefix. Process 100 then
`moves to step 110 where the binary representation of the
`least significant bits of the value of v—(N—2) are appended
`to the unary prefix to create the codeword.
`invention
`Although the description of the present
`describes a binarization scheme for MPEG-AVC/H.264, it is
`not the intent of the inventors to restrict this binarization
`
`scheme solely to the referenced proposed standard. As one
`skilled in the art can appreciate any system utilizing BAC
`may make use of the present invention improve binarization.
`Although the present invention has been described as
`being implemented in software, one skilled in the art will
`recognize that it may be implemented in hardware as well.
`Further, it is the intent of the inventors to include computer
`readable forms of the invention. Computer readable forms
`meaning any stored format that may be read by a computing
`device.
`
`Although the invention has been described with reference
`to certain specific embodiments, various modifications
`thereof will be apparent to those skilled in the art without
`departing from the spirit and scope of the invention as
`outlined in the claims appended hereto.
`What is claimed is:
`1. A method of binarization,
`comprising the step of:
`determining if a code symbol index value;
`if said code symbol index value is less than a threshold
`value, constructing a codeword using a unary binariza-
`tion; and
`if said code symbol index value is not less than said
`threshold value, constructing a codeword using a exp-
`Golomb binarization.
`
`2. The method of claim 1, wherein said exp-Golomb
`binarization model comprises the steps of:
`a) forming an initial prefix of 1’s, equal in number to said
`threshold value minus one;
`b) determining the number of bits, y+1 required to rep-
`resent v—(N—2) where y=Llog2(v—(N—2))J, v is the code
`symbol index value, and N is the threshold value, and
`then transforming y into a unary representation to create
`a result;
`c) appending the result of step b) to the result of step a);
`d) determining the least significant bits, of v—(N—2)—
`2**y, and
`e) appending the result of step d) in its binary represen-
`tation to the result of step c) to create said codeword.
`3. A binarization system comprising:
`means for determining if a code symbol index value is less
`than a threshold value
`
`means for constructing a codeword using a unary
`binarization if said code symbol index value is less
`than a threshold value; and
`means for constructing a codeword using a exp-Golomb
`binarization if said code symbol index value is less than
`a threshold value.
`
`4. The system of claim 3, wherein said exp-Golomb
`binarization comprises means for:
`a) forming an initial prefix of 1’s, equal in number to said
`threshold value minus one;
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`
`
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 11 of 13 Page ID #:248
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 11 of 13 Page ID #:248
`
`US 6,744,387 B2
`
`9
`
`b) determining the number of bits, y+1 required to rep-
`resent v—(N—2) where y=Llog2(v—(N—2))J, V is the code
`symbol index value, and N is the threshold value, and
`then transforming y into a unary representation to
`create a result;
`
`c) appending the result of step b) to the result of step a);
`d) determining the least significant bits, of v—(N=2)—
`2**y; and
`e) appending the result of step d) in its binary represen-
`tation to the result of step c) to create said codeword.
`5. A computer readable medium containing instructions
`for binarization, comprising instructions for:
`determining if a code symbol index value;
`if said code symbol index value is less than a threshold
`value, constructing a codeword using a unary binariza-
`tion; and
`if said symbol index value is not less than said threshold
`value constructing a codeword using a exp-Golomnb
`binarization.
`
`10
`
`15
`
`10
`6. The computer readable medium of claim 5, wherein
`said exp-Golomb binarization comprises instructions for:
`
`a) forming an initial prefix of 1’s, equal in number to said
`threshold value;
`
`b) determining the number of bits, y+1, required to
`represent v—(N=2) where y=Llog2(v—(N—2))J, v is the
`code symbol index value, and N is the threshold value,
`and then transforming y into a unary representation to
`create a result;
`
`c) appending the result of step b) to the result of step a);
`
`d) determining the least significant bits, of v—(N=2)—
`2**y; and
`
`e) appending the result of step d) in its binary represen-
`tation to the result of step c) to create said codeword.
`*
`*
`*
`*
`*
`
`
`
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 12 of 13 Page ID #:249
`Case 8:20-cv-00529 Document 1—7 Filed 03/13/20 Page 12 of 13 Page ID #:249
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`
`CERTIFICATE OF CORRECTION
`
`PATENT NO.
`APPLICATION NO.
`
`: 6,744,387 B2
`: 10/191596
`
`DATED
`
`: June 1, 2004
`
`INVENTOR(S)
`
`: Lowell Winger
`
`Page 1 0f 1
`
`It is certified that error appears in the above-identified patent and that said Letters Patent is hereby corrected as shown below:
`
`In column 8, line 32, replace “determining if a code symbol” with --determining a code symbol--.
`
`In column 8, line 59, replace “a threshold value” with --said threshold value--.
`
`In column 8, line 62, replace “a threshold value” with --said threshold value--.
`
`In column 9, line 13, replace “determining if a code symbol” with --determining a code symbol--.
`
`Signed and Sealed this
`
`Eighth Day of May, 2012
`
`
`
`David J. Kappos
`Director ofthe United States Patent and Trademark Oflice
`
`
`
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 13 of 13 Page ID #:250
`Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 13 of 13 Page ID #:250
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`
`CERTIFICATE OF CORRECTION
`
`PATENT NO.
`APPLICATION NO.
`
`: 6,744,387 B2
`: 10/191596
`
`DATED
`
`: June 1, 2004
`
`INVENTOR(S)
`
`: Lowell Winger
`
`Page 1 0f 1
`
`It is certified that error appears in the above-identified patent and that said Letters Patent is hereby corrected as shown below:
`
`In the Claims
`
`In column 8, line 62, replace “is less than” with --is not less than--.
`
`Signed and Sealed this
`
`Tenth Day of March, 2015
`
`WMXKAL.
`
`Michelle K. Lee
`
`Deputy Director ofthe United States Patent and Trademark Oflice
`
`