throbber
Case 8:20-cv-00529 Document 1-7 Filed 03/13/20 Page 1 of 13 Page ID #:238
`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
`
`

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket