# US 10,374,627 B2 · Entropy encoding and decoding scheme > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,374,627 B2 - Document ID: US10374627B2 - Status: Granted - Kind: B2 - Application number: 16/109,953 - Filed: 2018-08-23 - Published: 2019-01-10 - Granted: 2019-08-06 - Earliest claimed: 2011-01-14 - Assignees: Ge Video Compression, LLC - Applicants: Ge Video Compression, LLC - Inventors: Detlev Marpe; Tung Nguyen; Heiko Schwarz; Thomas Wiegand - Web page: https://patentgrep.com/patent/US10374627B2 ## CPC - H03M 7/00: Conversion of a code where information is represented by a given sequence or number of digits to a code where the same {, similar or subset of} information is represented by a different sequence or number of digits - H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code - H03M 7/4006: {Conversion to or from arithmetic code} - H03M 7/46: Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract Decomposing a value range of the respective syntax elements into a sequence of n partitions with coding the components of z laying within the respective partitions separately with at least one by VLC coding and with at least one by PIPE or entropy coding is used to greatly increase the compression efficiency at a moderate coding overhead since the coding scheme used may be better adapted to the syntax element statistics. Accordingly, syntax elements are decomposed into a respective number n of source symbols si with i=1 . . . n, the respective number n of source symbols depending on as to which of a sequence of n partitions into which a value range of the respective syntax elements is sub-divided, a value z of the respective syntax elements falls into, so that a sum of values of the respective number of source symbols si yields z, and, if n>1, for all i=1 . . . n−1, the value of si corresponds to a range of the ith partition. ## Claims ### Claim 1 An apparatus for decoding comprising: a symbol decoder configured to obtain, based on codewords from a data stream, a first sequence of source symbols and a second sequence of source symbols, wherein source symbols of the first and second sequences are related to level values of transform coefficients of a transform coefficient block, wherein the level values of transform coefficients are encoded into the data stream according to a scan order leading through the transform coefficients of the transform coefficient block, and the symbol decoder is configured to obtain a first source symbol of the first sequence using a Rice code and a second source symbol of the first sequence using an Exp-Golomb code; and a composer configured to: compose a sequence of syntax elements having a value range which is sub-divided into a plurality of disjoint portions including at least three portions by, for each syntax element: obtaining a set of source symbols from the first and second sequences based on a portion of the plurality of disjoint portions associated with the syntax element, and combining values of the source symbols of the set to determine the value of the syntax element; and adapt one or more limits between the plurality of disjoint portions according to previously obtained source symbols. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein the symbol decoder comprises: a first decoder configured to: receive a first portion of the data stream, and reconstruct source symbols of the first sequence of source symbols from codewords of the first portion of the data stream; and a second decoder configured to: receive a second portion of the data stream, and reconstruct source symbols of the second sequence of source symbols from codewords of the second portion of the data stream. ### Claim 3 (depends on 1) The apparatus of claim 1, wherein a source symbol in the second sequence of source symbols corresponds to a first-ordered portion in the plurality of disjoint portions, and the plurality of disjoint portions is arranged such that a first portion covers higher values of the value range than a second portion. ### Claim 4 (depends on 1) The apparatus of claim 1, wherein the source symbols from the first sequence and the source symbols from the second sequence correspond to different portions. ### Claim 5 (depends on 1) The apparatus of claim 1, wherein source symbols of the first and second sequences are related to absolute level values of transform coefficients of a transform coefficient block. ### Claim 6 (depends on 1) The apparatus of claim 1, wherein the apparatus is at least a portion of a programmable logic device, a programmable gate array, a microprocessor, a computer or an electronic circuit. ### Claim 7 (depends on 2) The apparatus of claim 2, wherein one of the first decoder and the second decoder is configured to use arithmetic coding to reconstruct the source symbols, and the other of the first decoder and the second decoder is configured to use Golomb-Rice coding to reconstruct the source symbols. ### Claim 8 (depends on 1) The apparatus of claim 1, the composer is configured to adapt at least one limit between the plurality of disjoint portions during composing absolute transform coefficient levels of the transform coefficients of the transform coefficient block based on at least one of: a previously reconstructed absolute transform coefficient level of a transform coefficient preceding in the scan order, a position of a current absolute transform coefficient level to be composed in the scan order, an evaluation of previously reconstructed absolute transform coefficient levels of transform coefficients spatially neighboring the position of the current absolute transform coefficient level to be composed, and an evaluation of previously reconstructed absolute transform coefficient levels of transform coefficients neighboring according to the scan order the position of the current absolute transform coefficient level to be composed. ### Claim 9 A method for decoding comprising: obtaining, based on codewords from a data stream, a first sequence of source symbols and a second sequence of source symbols, wherein source symbols of the first and second sequences are related to level values of transform coefficients of a transform coefficient block, wherein the level values of transform coefficients are encoded into the data stream according to a scan order leading through the transform coefficients of the transform coefficient block, and the obtaining includes obtaining a first source symbol of the first sequence using a Rice code and obtaining a second source symbol of the first sequence using an Exp-Golomb code; and composing a sequence of syntax elements having a value range which is sub-divided into a plurality of disjoint portions including at least three portions by, for each syntax element: obtaining a set of source symbols from the first and second sequences based on a portion of the plurality of disjoint portions associated with the syntax element, and combining values of the source symbols of the set to determine the value of the syntax element, wherein one or more limits between the plurality of disjoint portions are adapted according to one or more previously obtained source symbols. ### Claim 10 (depends on 9) The method of claim 9, further comprising: receiving, by a first decoder, a first portion of the data stream; reconstructing, by the first decoder, source symbols of the first sequence of source symbols from codewords of the first portion of the data stream; receiving, by a second decoder, a second portion of the data stream; and reconstructing, by the second decoder, source symbols of the second sequence of source symbols from codewords of the second portion of the data stream. ### Claim 11 (depends on 9) The method of claim 9, wherein a source symbol in the second sequence of source symbols corresponds to a first-ordered portion in the plurality of disjoint portions, and the plurality of disjoint portions is arranged such that a first portion covers higher values of the value range than a second portion. ### Claim 12 (depends on 9) The method of claim 9, wherein the source symbols from the first sequence and the source symbols from the second sequence correspond to different portions of the plurality of disjoint portions. ### Claim 13 (depends on 10) The method of claim 10, wherein one of the first decoder and the second decoder is configured to use arithmetic coding to reconstruct the source symbols, and the other of the first decoder and the second decoder is configured to use Golomb-Rice coding to reconstruct the source symbols. ### Claim 14 (depends on 9) The method of claim 9, wherein at least one limit between the plurality of disjoint portions is adapted during composing absolute transform coefficient levels of the transform coefficients of the transform coefficient block based on at least one of: a previously reconstructed absolute transform coefficient level of a transform coefficient preceding in the scan order, a position of a current absolute transform coefficient level to be composed in the scan order, an evaluation of previously reconstructed absolute transform coefficient levels of transform coefficients spatially neighboring the position of the current absolute transform coefficient level to be composed, and an evaluation of previously reconstructed absolute transform coefficient levels of transform coefficients neighboring according to the scan order the position of the current absolute transform coefficient level to be composed. ### Claim 15 (depends on 9) A non-transitory computer readable medium including a computer program comprising program code for performing, when executing on a computing device, a method according to claim 9. ### Claim 16 An apparatus for encoding comprising: a decomposer configured to: receive a sequence of syntax elements having a value range which is sub-divided into a plurality of disjoint portions including at least three portions, wherein the sequence of syntax elements are related to level values of transform coefficients of a transform coefficient block and the level values of transform coefficients are encoded into the data stream according to a scan order leading through the transform coefficients of the transform coefficient block, and obtain a sequence of source symbols based on the sequence of syntax elements by decomposing each syntax element into a corresponding set of source symbols based on a portion of the plurality of disjoint portions associated with the syntax element, such that a combination of values of the source symbols of the set yields the value of the syntax element; and a sub-divider configured to: receive the sequence of source symbols, and sub-divide the sequence of source symbols into a first sequence of source symbols and a second sequence of source symbols, wherein a first source symbol of the first sequence is encoded using a Rice code and a second source symbol of the first sequence is encoded using an Exp-Golomb code, and wherein the decomposer is configured to adapt one or more limits between the plurality of disjoint portions according to one or more previously obtained source symbols. ### Claim 17 (depends on 16) The apparatus of claim 16, further comprising: a first encoder configured to encode the source symbols of the first sequence; and a second encoder configured to encode the source symbols of the second sequence. ### Claim 18 (depends on 16) The apparatus of claim 16, wherein a source symbol in the second sequence of source symbols corresponds to a first-ordered portion in the plurality of disjoint portions, and the plurality of disjoint portions is arranged such that a first portion covers higher values of the value range than a second portion. ### Claim 19 (depends on 17) The apparatus of claim 17, wherein the first encoder or the second encoder is further configured to encode a scaling factor. ### Claim 20 (depends on 16) The apparatus of claim 16, wherein the source symbols from the first sequence and the source symbols from the second sequence correspond to different portions of the plurality of disjoint portions. ### Claim 21 (depends on 17) The apparatus of claim 17, wherein one of the first encoder and the second encoder is configured to use arithmetic coding to encode the source symbols, and the other of the first encoder and the second encoder is configured to use Golomb-Rice coding to encode the source symbols. ### Claim 22 (depends on 16) The apparatus of claim 16, wherein the apparatus is at least a portion of a programmable logic device, a programmable gate array, a microprocessor, a computer or an electronic circuit. ### Claim 23 A non-transitory computer-readable medium for storing video data, comprising: a data stream stored in the non-transitory computer-readable medium and comprising data associated with a first sequence of source symbols and a second sequence of source symbols, wherein the source symbols of the first and second sequences are related to level values of transform coefficients of a transform coefficient block, which are encoded into the data stream according to a scan order leading through the transform coefficients of the transform coefficient block, and the source symbols are obtained based on a sequence of syntax elements having a value range which is sub-divided into a plurality of disjoint portions including at least three portions by executing operations using a processor, the operations including: decomposing each syntax element into a corresponding set of source symbols based on a portion of the plurality of disjoint portions associated with the syntax element, such that a combination of values of the source symbols of the set yields the value of the syntax element, and adapting one or more limits between the plurality of disjoint portions according to one or more previously obtained source symbols, wherein a first source symbol of the first sequence is encoded using a Rice code and a second source symbol of the first sequence is encoded using an Exp-Golomb code. ### Claim 24 (depends on 23) The non-transitory computer-readable medium of claim 23, the operations further comprising: encoding the source symbols of the first sequence using a first encoder; and encoding the source symbols of the second sequence using a second encoder. ### Claim 25 (depends on 24) The non-transitory computer-readable medium of claim 24, wherein the first encoder or the second encoder is configured to encode a scaling factor. ### Claim 26 (depends on 24) The non-transitory computer-readable medium of claim 24, wherein one of the first encoder and the second encoder is configured to use arithmetic coding to encode the source symbols, and the other of the first encoder and the second encoder is configured to use Golomb-Rice coding to encode the source symbols. ### Claim 27 (depends on 23) The non-transitory computer-readable medium of claim 23, wherein a source symbol in the second sequence of source symbols corresponds to a first-ordered portion in the plurality of disjoint portions, and the plurality of disjoint portions is arranged such that a first portion covers higher values of the value range than a second portion. ### Claim 28 (depends on 23) The non-transitory computer-readable medium of claim 23, wherein the source symbols from the first sequence and the source symbols from the second sequence correspond to different portions of the plurality of disjoint portions. ### Claim 29 (depends on 9) The method of claim 9, wherein source symbols of the first and second sequences are related to absolute level values of transform coefficients of a transform coefficient block. ### Claim 30 (depends on 16) The apparatus of claim 16, wherein source symbols of the first and second sequences are related to absolute level values of transform coefficients of a transform coefficient block.