Entropy encoding and decoding scheme

[0001] The present invention relates to entropy coding and decoding and can be used in applications such as, for example, audio and video compression.

[0002] Entropy coding can generally be considered the most common form of lossless data compression. Lossless compression is intended to represent discontinuous data with fewer bits than needed for the original data representation, but without losing information. Discontinuous data may be given in the form of text, graphics, images, video, audio, speech, facsimile, medical data, meteorological data, financial data, or any other form of digital data.

[0003] In entropy coding, specific features of the high level base discontinuous data source are often overlooked. Consequently, the data source can be given in the form of a sequence of source symbols that has values ​​in a given M-ary alphabet and which has an appropriate (discontinuous) probability distribution {p1, ..., pm}. In these abstract settings, the lower limit of any entropy coding method in terms of the expected code word length in bits per symbol is given by entropy m

H = · (Al) / = 1 [0004] Huffman codes and arithmetic codes are well known examples of practical codes enabling approximation of the entropy limit (in a defined sense). For a fixed probability distribution, Huffman codes are relatively easy to construct. The most attractive property of Huffman codes is that its implementation can be effectively implemented by using variable length code tables (VLC). However, when dealing with time-varying source statistics, that is, changing the symbol probabilities, adjusting the Huffman code and its corresponding VLC tables is very demanding, both in terms of algorithmic complexity as well as in terms of implementation costs. In addition, if you have a dominant alphabet value with pk> 0.5, the excess of the corresponding Huffman code (without using the alphabet extension, such as the length of the encoding run) can be quite significant. Another disadvantage of Huffman codes is that when dealing with higher order probability models, multiple VLC table sets may be required. Arithmetic coding, on the other hand, being much more complicated than VLC, has the advantage of being more consistent and appropriate behavior dealing with adaptive and higher order probability modeling as well as for very probability distribution curves. In fact, this feature basically results from the fact that arithmetic coding provides a mechanism, at least conceptually, for mapping any probability estimation value in a more or less direct way to part of the received codeword. Being equipped with such an interface, arithmetic coding allows for a clean separation between probability modeling and probability estimation tasks, on the one hand, and real entropy coding, i.e. mapping the code symbols from the other side.

[0005] An alternative to arithmetic coding and VLC coding is PIPE coding. To be more precise, in PIPE encoding, the unit interval is divided into a small set of disjoint probability intervals for fast receiving of coding processing along the probability estimates of random variable symbols. According to this sub-range, the input sequence of discrete source symbols of any alphabet size can be assigned to the alphabet symbol sequence, and each of the alphabet symbols is assigned to one specific probability range, which in turn is encoded by a specially designed entropy coding process. From each of the ranges that are represented by a fixed probability, the PIPE encoding process (ang. probability interval partitioning entropy) can be based on the construction and use of simple variable codes - of variable length. Probability modeling can be either fixed or adaptive. However, while PIPE coding is much less complex than arithmetic coding, it still has more complexity than VLC coding.

[0006] Thus, it would be beneficial to have an entropy coding scheme that allows for a better compromise between the complexity of coding on the one hand and the compression efficiency of the other, even compared to PIPE coding, which already combines the advantages of both arithmetic coding and VLC coding.

[0007] Furthermore, it would generally be beneficial to have an entropy coding scheme that allows for better compression efficiency per se, with moderate coding complexity.

[0008] WO 2008/129021 A2 relates to scalable compression of a 3D lattice time-coherent sequence. With regard to quantization and entropy coding, the document states that lattice vector prediction errors are compressed component by component. In particular, the components are mapped to integer values, i.e. signed, and maximum for quantity, i.e. imax is used to determine the time interval in the number of integers for which components within this range are entropy coded. The remaining amount, i.e. the distance from the proximal end of the compartment, is coded using Golomb codes.

[0009] The object of the present invention is to provide an entropy coding concept that meets the above-mentioned demand, that is, it allows a better compromise between coding complexity on the one hand, and compression efficiency on the other.

[0010] This object is achieved by the subject of the independent claims.

[0011] The present invention is based on the assumption of decomposing the value range of individual syntactic elements into a sequence of n intervals with encoding components of the values ​​of the syntactic element within the respective sub-ranges separately in at least one by VLC coding and at least one by arithmetic coding. Accordingly, in accordance with embodiments of the present invention, the syntactic elements are broken down into an appropriate number of n source symbols si z = 1 ... n, whereby the appropriate number of n source symbols depends on which of the sequence of n intervals (1401 -3) into which the value range of the respective syntactic elements is divided, the value from the relevant syntactic elements is contained, so that the sum of the values ​​of the appropriate number of source symbols s is provided from, and, if n> 1, for all i = 1 ... n-1, the value of si corresponds to the range of the ith interval.

[0012] Advantageous aspects of the present invention are covered by the dependent dependent claims. [0013] Preferred embodiments of the present invention are described below with reference to the figures. These embodiments represent, as long as they do not use arithmetic coding in addition to VLC coding, examples. Among the figures:

Fig. 1a shows a block diagram of an entropy coding apparatus;

Fig. 1b is a schematic diagram illustrating the possible distribution of syntax elements into source symbols;

Fig. 1c is a block diagram illustrating the possible mode of operation of the decomposition module shown in Fig. 1a in a distribution of syntax elements into source symbols;

Fig. 2a is a block diagram of an entropy decoding device;

Fig. 2b is a block diagram illustrating a possible mode of operation of the composition module of Fig. 2a in assembling syntax elements from source symbols;

Fig. 3 is a block diagram of a PIPE encoder according to a comparative embodiment that can be used in Fig. 1;

Fig. 4 is a block diagram of a PIPE decoder suitable for decoding the bit stream generated by the PIPE encoder in Fig. 3, according to a comparative embodiment that can be used in Fig. 2;

Fig. 5 is a schematic diagram illustrating a data packet with multiplexed partial bit streams;

Fig. 6 is a schematic diagram illustrating a data packet with an alternative segmentation using fixed-size segments;

Fig. 7 is a block diagram of a PIPE encoder using bit stream interleaving;

Fig. 8 is a schematic example illustrating for the status of the codeword buffer on the encoder side of Fig. 7;

Fig. 9 is a block diagram of a PIPE decoder using bit stream interleaving;

Fig. 10 is a block diagram of a PIPE decoder using code word interleaving using a single set of code words;

Fig. 11 is a block diagram of a PIPE encoder using constant length bit interleaving;

Fig. 12 is a schematic example illustrating for the global bit buffer status of the encoder side of Fig. 11;

Fig. 13 is a block diagram of a PIPE decoder using constant length bit interleaving;

Fig. 14 is a graph illustrating the optimal range of discretization probability at intervals K = 4 assuming a uniform probability distribution in (0.0.5],

Fig. 15 is a schematic diagram illustrating a binary event tree for the LPB probability with p = 0.38 and associated variable length code obtained using the Huffman algorithm,

Fig. 16 shows a chart from which an increase in the ratio of bit rates p (p, C) can be derived for obtaining optimal C codes. Given the maximum number of entries in the table

lm,

Fig. 17 is a graph illustrating the increase in ratio for the theoretically optimal interval of probability of division into K = 12 intervals and the true formula with V2V codes with a maximum number of Lm = 65 table entries;

Fig. 18 is a diagram illustrating an example for converting a triple selection tree to a full binary selection tree;

Fig. 19 is a block diagram of a system comprising an encoder (left side) and a decoder (right side);

Fig. 20 shows a block diagram of an entropy coding device;

Fig. 21 is a block diagram of an entropy decoding device;

Fig. 22 is a block diagram of an entropy coding apparatus;

Fig. 23 is a schematic diagram illustrating examples regarding the status of the global bit buffer on the encoder side of Fig. 22;

Fig. 24 is a block diagram of an entropy decoding device.

[0014] Before describing several embodiments of the present application below with reference to the drawings, it should be noted that the same reference numbers are used in all figures to designate equal or equivalent elements in these drawings, and the description of those elements of any of the previous figures also has apply to each of the following figures if only the previous description does not conflict with the description of the previous figures.

[0015] Fig. 1a shows an entropy coding device. The device contains a sub-compartment module 100, a VLC 102 encoder and a PIPE 104 encoder.

[0016] The sub-compartment module 100 is configured to divide the source symbol sequence 106 into a first sub-sequence of 108 source symbols and a second sub-sequence of 110 source symbols. The VLC encoder 102 has its input connected to the first output of the sub-compartment module 100 and is configured to convert, depending on the symbol, the source symbols of the first sub-sequence 108 into the code words constituting the first bit stream 112. The VLC encoder may include an array look-up table) and use, individually, source symbols as an indicator to check the source symbol for the corresponding code word in the table. The VLC encoder outputs this last codeword, and passes with the next source symbol in sub-sequence 110 to output a codeword sequence in which each codeword is associated with exactly one of the source symbols in sub-sequence 110. The code words may be of different lengths and may be designated such that no code word prefixes with another of the code words. In addition, the array can be static.

[0017] The PIPE encoder 104 has its input connected to the second output of the sub-compartment module 100 and is configured to encode the second sub-sequence of 110 source symbols represented in the form of an alphabet symbol sequence, and includes an allocation module 114 configured to assign a measure for a probability distribution estimate among possible values ​​that the corresponding alphabet symbols can take, to each alphabet symbol sequence for alphabet symbols based on the information contained in the previous alphabet symbol sequence for alphabet symbols, with a plurality of entropy coders 116 each of which is configured to convert the alphabet symbols transmitted to the respective entropy coder to the corresponding second bit stream 118, and a selection module 120 configured, to pass each alphabet symbol of the second sub-sequence 110 to one of the plurality of entropy encoders 116 selected, the choice being dependent on the above measure for the probability distribution estimate assigned to the corresponding alphabet symbol. The association between the source symbols and the alphabet symbols may be such that each alphabet symbol is uniquely associated with exactly one source symbol of the sub-sequence 110 to represent, together with possibly further alphabet symbols, a sequence of alphabet symbols that may follow directly, this one source symbol.

[0018] As described in more detail below, the sequence of source symbols 106 may be a sequence of syntax elements of the analyzeable bit stream. The analytical bit stream may, for example, represent video and / or audio content in a scalable or non-scalable manner with syntax elements representing, for example, transformation coefficient levels, motion vectors, movie reference indicators, scale factors, audio energy envelope values ​​or the like. Syntactic elements may in particular be of a different type or category with syntactic elements of the same type, for example, having the same meaning in an analytical bit stream, but with respect to individual parts thereof, such as different images, different macro-blocks, different spectral components or the like, while syntactic elements of different types may have different meanings in the bit stream, such as motion vector has a different meaning than the syntax element representing the transformation of the coefficient level representing the residual motion prediction.

[0019] The sub-compartment module 100 can be configured to make the sub-division depending on this type of syntax. That is, the sub-compartment module 100 may forward the syntax elements of the first type group to the first sub-sequence 108 and forward the syntax elements of the second type group remote from the first group to the second sub-sequence 110. The subdivision made by the sub-compartment module 100 can be designed so that the syntax statistics symbol in sub-sequence 108 is suitable for VLC coding by the VLC encoder 102, i.e. it causes the minimum possible entropy despite using the VLC coding and its limitation is in relation to its suitability for some statistical symbol as given in the introductory part of this description of the present application. On the other hand, the sub-compartment module 100 can forward all other syntax elements to the second sub-sequence 110 so that these syntax elements containing statistical data symbols not suitable for VLC encoding are encoded by a more complex but effective - depending on the compression ratio - PIPE encoder 104.

[0020] As is also more specific with reference to the following figures, the PIPE encoder 104 may include a symbiliser 122 configured to individually map each syntax element of the second subsection 110 to the respective partial sequence of alphabet symbols, together forming the abovementioned sequence of alphabet symbols 124 . In other words, the symbiliser 122 may not be present if, for example, 110 symbol source sub-sequences are already represented as corresponding partial alphabet symbol sequences. The symbiliser 122 is, for example, advantageous in the case of source symbols in sub-sequence 110 which have different alphabets, in particular, alphabets having different numbers of possible alphabet symbols. Namely, in this case, the symbiliser 122 may harmonize the alphabets of the symbols falling in the sub stream 110. The symbiliser 122 may, for example, be implemented as a binarization module configured to binarize the symbols falling in sub-sequence 110.

[0021] As indicated above, the syntactics can be of different types. This may also be true for syntax elements in sub stream 110. The symbiliser 122 may then be configured to map the individual syntax elements of subsection 110 using a symbolic mapping scheme, e.g., binarization scheme, different for other type syntax components. Examples of specific binarization schemes are described in the following description, such as the unary binary scheme, Exp-Golomb binary scheme of order 0 or order 1, for example, or truncated unary binarization scheme, truncated binarization scheme and in changed order exp-Golomb order 0 or unsystematic binarization scheme.

[0022] Accordingly, entropy encoders 116 may be configured to operate on a binary alphabet. Finally, it should be noted that the symbiliser 122 can be considered as part of the PIPE encoder 104 itself, as shown in Fig. 1a. Alternatively, however, the binarizer module can be treated as external to the PIPE encoder.

[0023] Similarly to the latter, it should be noted that the allocation module 114, although it has been shown to be connected in series between the balancer 122 and the selection module 120, can alternatively be considered connected between the output of the balancer 124 and the first input, the selection module 120, with allocation module output 114 connected to another input of selection module 120, as later described with reference to Fig. 3. As a result, the allocation module 114 accompanies each alphabet symbol from the above measure for the probability distribution estimate.

[0024] As for the output of the entropy coding device of Fig. 1a, it likewise consists of the first bit stream 112 outgoing through the VLC encoder 102 and the plurality of second bit streams 118 outgoing through the multiple entropy encoders 116. As described below, all these bit streams can be sent simultaneously. Alternatively, the same can be interleaved to the common bit stream 126 using interleaver 128. Fig. 22 to 24 show examples with such bit stream interleaving. As further shown in Fig. 1, the PIPE encoder 104 itself may include its own interleaver 130 to interleave a plurality of second bit streams 118 into the jointly encoded PIPE bit stream 132. The capabilities of such interleaver 130 can be judged from the description of Figs. 5 to 13 The bit stream 132 and the bit stream 112 may, in parallel, represent the output of the entropy coding device of Fig. 1a. Alternatively, the second interleaver 134 may interleave both bit streams, in which case interleaver 130 and 134 will form two stages of one two-stage interleaver 128.

[0025] As described above, the sub-compartment module 100 may perform subdivisions depending on the syntax element, i.e., the source symbol sub-compartment module 100 operates possibly on entire syntactic elements, or alternatively, the sub-compartment module 100 can operate on units of syntax elements.

[0026] However, the entropy coding device of Fig. 1a may include a decomposition module 136 to decompose the syntax into an analysable bit stream 138 individually into one or more source symbols of the source symbol sequence 106 entering the sub-compartment module 100. In particular, the decomposition module 136 may be configured to convert a sequence of 138 syntax elements into a sequence of 106 source symbols by individually decomposing each syntax element into the corresponding total number of source symbols. The total number may vary among syntactic elements. In particular, some syntactic elements may even be left unchanged by the decomposition module 136, with the other syntactic elements being arranged in exactly two, or at least two, source symbols. The sub-compartment module 100 may be configured to forward one of the source symbols of such distributed syntax elements to the first sub-sequence of 108 source symbols and another one of the source symbols of the same distributed syntax element to the second sub-sequence of 110 source symbols. As mentioned above, the syntax elements in bit stream 138 may be of a different type, and the decomposition module 136 may be configured to perform individual decomposition depending on this type of syntax element. The decomposition module 136 preferably performs individual decomposition of the syntax elements such that there is a predefined unique inverse mapping later used on the decoding side, with the total number of source symbols to the corresponding syntax element, common to all syntactic elements.

[0027] For example, the decomposition module 136 may be configured to decompose the syntax elements z into the analysis bit stream 138, into two source symbols x and y such that z = x + y, z = xy, z = x · y or z = x: y. In this way, the sub-compartment module 100 can break down syntactic elements into two components, i.e. source symbols of the source symbol stream 106, one of which is suitable to be encoded in VLC in terms of compression efficiency, such as x, and the other of which is not suitable for VLC coding and is thus passed to the second sub stream 110 and not to the first sub stream 108, such as y. The decomposition used by the decomposition module 136 does not have to be of the bijective type. However, as indicated above, there should be an inverted mapping that allows unique retrieval of the syntax elements of possible decompositions among which decomposition module 136 can choose whether or not the decomposition is of the bijective type. [0028] To date, various options have been described for operating various syntactics. As to whether such syntax elements or cases exist, this is optional. Further description, however, focuses on syntactic elements that are decomposed by the decomposition module 136 according to the following principle.

[0029] As shown in Fig. 1b, the decomposition module 136 is configured to decompose specific syntax elements with an analyzeable bit stream 138 in stages. There may be two or more stages. The steps are to divide the value range of the syntactic element into two or more adjacent sub compartments or subranges as shown in Fig. 1c. The value range of a syntax element can have two infinite endpoints, where only one or more have finite endpoints. In Fig. 1c, the value range of the syntax element is for example divided into three sub-compartments 1401-3. As shown in Fig. 1b, if the syntax element is greater than or equal to the boundary 142 of the first sub-compartment 1401, i.e. the upper boundary separating the sub-compartments 1401 and 1402, then the syntax element is subtracted by the boundary boundary of the first sub-compartment 1401 and z is checked again whether it is even greater than or equal to the boundary 144 of the second sub-compartment 1402, i.e. the upper boundary separating 1402 and 1403. If 'is greater than or equal to border 144, then z' is subtracted by border border2 of the second sub-compartment 1402 obtained with '. In the first case, where z is less than boundary1, the syntax element z is sent to the sub-compartment module 100 in the plane. In the case of being between boundary1 and boundary2, the syntax element z is sent to the 100-w sub module as fold (bound, z ') zz = boundary1 + z', and in the case of the above-bound2, the syntax element z is sent to the sub-module 100 w like triplet (boundary1, boundary2-boundary1, with ') zz = boundary1 + boundary2 + z'. The first (or alone) component, i.e. with or boundary1, creates the first source symbol to be encoded by the sub-compartment module 100, the second component, i.e. with 'or boundary2-boundary1, creates the second source symbol to be encoded by the sub-compartment module 100, if present, and the third component, i.e., from ", creates the third source symbol to be encoded by the sub-compartment module 100, if present. Thus, according to Fig. 1b and 1c, the syntax element is mapped to any of 1 to 3 source symbols, but a generalization to a smaller or larger maximum number of source symbols is easy to obtain from the description above, and such alternatives will also be described later.

[0030] In any case, all these different components or the resulting source symbols are in accordance with the following embodiments, encoded, among others, with encoded alternatives. At least one of them is forwarded by the sub-compartment module to the PIPE encoder 104, and eventually one other is sent to the VLC 102 encoder.

[0031] Particularly preferred embodiments are described in more detail below.

[0032] After describing the entropy coding device above, the entropy decoding device is described with reference to Fig. 2a. The entropy decoding apparatus of Fig. 2a includes a VLC decoder 200 and a PIPE decoder 202. The VLC decoder 200 is configured to reconstruct the source symbols of the first sub-sequence 204 from the code words of the first bit stream 206 according to the code. The first bit stream 206 is equal to the bit stream 112 of FIG. 1, and the same applies to sub-sequence 204 with respect to sub-sequence 108 of Fig. 1a. The PIPE decoder 202 is configured to reconstruct a second sub-sequence of 208 source symbols, represented in the form of an alphabet symbol sequence, and includes a plurality of entropy decoders 210, allocation module 212, and selection module 214. Many entropy decoders 210 are configured to convert the corresponding one of the second bit streams 216 to alphabet symbols of the alphabet symbol sequence. The allocation module 212 is configured to assign measures of estimated probability distribution among the possible values ​​of the corresponding alphabet symbols can assume, for each alphabet symbol, a sequence of alphabet symbols representing the second sub-sequence of 208 source symbols to be reconstructed based on information contained in previously reconstructed alphabet symbols sequence of alphabet symbols. To this end, the allocation module 212 can be connected in series between the output of the selection module 214 and its input, while the other inputs of the selection module 214 have correspondingly connected to them the entropy decoder outputs 210. The selection module 214 is configured to recover each symbol alphabet of the sequence symbols of the alphabet from one of the many entropy decoders 210 selected, the choice of which depends on the measure assigned to the corresponding alphabet symbol. In other words, the selection module 214 together with the allocation module 212 is used to retrieve the alphabet symbols received by entropy decoders 210 in order between the entropy decoders 210 obtained by viewing the information contained in the previous alphabet symbols of the alphabet symbol sequence. In other words, the allocation module 212 and the selection module 214 may reconstruct the original order of the alphabet symbols from the alphabet symbol to the alphabet symbol. Together with the prediction of the next alphabet symbol, the allocation module 212 may determine the above indicated measure of the probability distribution estimate for the corresponding alphabet symbol by using selection module 214, which selects among entropy decoders 210 to recover the actual value of this alphabet symbol. To be even more accurate, as will be described in more detail below, the PIPE decoder 202 may be configured to reconstruct a source symbol sub-sequence 208, represented in the form of an alphabet symbol sequence, responding to alphabet symbol requests sequentially requesting alphabet symbols, and an allocation module 212 may be configured, to assign to each alphabet symbol request a sequence of alphabet symbols representing the second sub-sequence (208) of source symbols to be reconstructed, wherein the measure of probability distribution estimation indicated above among the possible values ​​of the corresponding alphabet symbol may be assumed. Accordingly, the selection module 214 can be configured to recover, for each alphabet symbol request, an alphabet symbol sequence representing the second sub-sequence (208) of the source symbols to be reconstructed, the corresponding alphabet symbol alphabet sequence of symbols from a selected one of a plurality of entropy decoders 210, with which choice depends on the measure assigned to the appropriate request for the corresponding alphabet symbol. The compatibility between requests on the decoding side on the one hand, and data flow or coding on the coding side on the other hand will be described in more detail with reference to Fig. 4.

[0033] Since the first subsection 214 of the source symbols and the second subsection of 208 source symbols together form one common sequence of source symbols 210, the entropy decoding device of Fig. 2a may, optionally, include a reassembly module 220 configured to recombine the first subsection 204 and the second sub-sequence 208 to obtain a common sequence of 218 source symbols. This common sequence of 208 source symbols provides a reconstruction of the 106 sequence of Fig. 1a.

[0034] As described above with reference to Fig. 1, the source symbols of the first and second sub sequences 204 and 208 may be syntactic elements of the bit stream that can be analyzed. In this case, the reassembly module 220 may be configured to reconstruct this analyzeable bit stream of the 218 sequence of syntax elements by interleaving the source symbols passing through the first and second sub sequences 204 and 208 in the order determined by some syntactic analysis rules determining the order among the syntactic elements . In particular, the syntax elements may be, as described above, a different type, and the reassembly module 220 may be configured to recover or request the syntax elements of the first type group from the VLC decoder 200 by sub stream 204, and the syntax elements of the second type from the PIPE 202 decoder by sub stream 208. Accordingly, as soon as the parsing rule indicated above indicates that the type syntax element in the first group is next in queue, the reassembly module 202 inserts the actual source symbol of subsection 204 into common sequence 218, and otherwise from subsection 208.

[0035] Similarly, the PIPE decoder 202 could include a desymbolizer 222 connected between the output of the selection module 214 and the input of the reassembly module 220. Similarly to the one described above with reference to Fig. 1, the desymbilizer 222 could be considered as external to the PIPE decoder 202 and it could even be arranged downstream of the reassembly module 202, i.e., on the output side of the reassembly module 220, alternatively. The desymbilizer 222 could be configured to re-map, in units of partial alphabet symbol sequences, the alphabet symbol sequence 224 exiting through the selection module 214 to source symbols, i.e. the syntax elements of subsection 208. Similar to the reassembly module 220, the desymbilizer 222 knows about the construction of possible partial sequences of alphabet symbols. In particular, the desymbolizer 222 may analyze the last received alphabet symbols from the selection module 214 to make sure that these last received alphabet symbols provide valid partial alphabet symbol sequences associated with the corresponding value of the respective syntax element, or if it is not, in which the next alphabet symbol is missing . Still, in other words, the symbiliser 222 knows at any time whether further alphabet symbols are to be received from the selection module 214 to terminate the receipt of the corresponding syntax element or not, and accordingly, to which syntax element the corresponding one alphabet symbol outgoing through the selection module 214 belongs. To this end, the desymbilizer 222 may use a symbolizing (de) differentiated mapping scheme for other type syntax elements. Similarly, the allocation module 212 knows about the association of the current alphabet symbol to be recovered from any of the entropy decoders 210 by the selection module 214 to the appropriate one of the syntax elements and can set the above-indicated measure of the probability distribution estimate of that alphabet symbol respectively, i.e. depending on the associated type of syntax element. In addition, the allocation module 212 may be distinguished between different alphabet symbols belonging to the same partial sequence of the current alphabet symbol and may set the measure of probability distribution estimation differently for these alphabet symbols. Details in this regard are described in more detail below. As described herein, the allocation module 212 may be configured to assign contexts to alphabet symbols. The assignment may depend on the type and / or position of the syntax element in the partial alphabet symbol sequence of the current syntax element. As soon as the allocation module 212 has a context assigned to the current alphabet symbol to be recovered from any of the entropy decoders 210 by the selection module 214, the alphabet symbol may actually have a probability distribution estimation measure associated with it when each context has its estimation measure associated with it. . In addition, the context - and its associated measure of probability distribution estimation - can be adjusted according to the actual statistics of the alphabet symbols of the corresponding context already recovered from entropy decoders 210. Details in this regard are set out in more detail below.

[0036] As in the above discussion of Fig. 1, it is possible that the relationship between the above-indicated source symbols of subsection 204 and 208 in syntax elements is not one-to-one correspondence. Or rather, syntactic elements can be broken down into the total number of source symbols from many, eventually, variable syntax elements, but in any case larger than one of at least one syntax element. As mentioned above, the following description focuses on handling this type of syntax, and other type syntax may not even be present.

[0037] To handle the syntax elements just indicated, the entropy decoding device of Fig. 2a may include a composition module 224 configured to improve the decomposition performed by the decomposition module 136 of Fig. 1a. In particular, the composition module 224 may be configured to assemble the sequence 226 syntax from source symbols of sequence 218 or, if the reassembly module 220, subsection 204 and 208 are missing, by individually submitting each syntax element with the corresponding total number of source symbols from one of the source symbols of the total number of source symbols belonging to the first subsection 204 and another one of the source symbols of the total number of source symbols of the same syntax element belonging to the second subsection 208. Due to this, specific syntax elements can be distributed on the encoder side so that separate components suitable for VLC decoding with the remaining component that would pass through the PIPE decoding path. Similarly to the above discussion, the syntax element may be of a different type and the composition module 224 may be configured to perform an individual composition depending on this type of syntax. In particular, the composition module 224 can be configured to obtain the corresponding syntax elements by logically or mathematically combining the total number of source symbols of the respective syntax element. For example, the composition module 224 can be configured for each syntax element by applying +, -,: or · to the first and second source symbols of one syntax element.

[0038] As described above, the embodiments described below, however, focus on syntax elements that are decomposed by the decomposition module 136 according to Figs. 1b and 1c and the alternatives described in relation thereto. Fig. 2a illustrates how the composition module 224 can work to reconstruct these syntax elements from their source symbols 218.

[0039] As shown in Fig. 2b, the composition module 224 is configured to assemble such syntax elements in stages from incoming source symbols s1 to sx zx being any of 1 to 3 in the present example. Two or more stages may occur. As shown in Fig. 2b, the composition module 224 initially sets z to was the first symbol s1 and checks whether z is equal to the first boundary1. If this is not the case, it has been found. Otherwise, the composition module 224 adds the next source symbol s2 of the source symbol stream 218 to z and checks again if z is equal to border2. If not, z was found. If not, the composition module 224 adds the next source symbol s3 to the source symbol stream 218 to z to obtain from its final form. Generalizations on more or less the maximum number of source symbols are easily derived from the above description, and such alternatives will also be described below.

[0040] In any case, all these different components or the resulting source symbols are, as described below, coded from coding among the alternatives. At least one of them is forwarded by the sub-compartment module to the PIPE encoder 104, and finally another one is sent to the VLC encoder 102.

[0041] Particularly preferred details are described in more detail below. These details focus on the advantageous possibilities of sharing the range of values ​​of syntactic and VLC entropy and PIPE encoding schemes that can be used to encode source symbols.

[0042] Furthermore, as also described above with reference to Fig. 1, the entropy decoding apparatus of Fig. 2a may be configured to receive first bit stream 206 as well as a plurality of second bit streams 216 separately or in an interleaved form bit stream 228. In the latter case, the entropy decoding device of Fig. 2a may include deinterleaver 230 configured to deinterleave the bit stream 228 to obtain the first bit stream 206 on one side and the plurality of second bit streams 216 on the other side. Similar to the above discussion of Fig. 1, deinterleaver module 230 can be divided into two stages, i.e. deinterleaver module 232 for deinterleaving the interleaved bit stream 228 into two parts, i.e. bit stream 206 on one side and the braided form 234 of the second bit stream 216 on the other, and the deinterleaver 236 for deinterleaving the latter bit stream 234 to obtain individual bit streams 216.

[0043] Thus, Fig. 1a and Fig. 2a show an entropy coding apparatus on one side and an entropy decoding apparatus suitable for decoding the coding result obtained by the entropy coding apparatus on Fig. 1 on the other hand. Details of many of the elements shown in Figs. 1a and 2 are described in more detail with reference to the subsequent figures. Accordingly, reference is made to this information in the description below, and these details should also be considered as individually applicable to Figures 1a and 2, as long as these details are separately implemented in the encoders and decoders described above. Only for interleaving modules and deinterleaving modules 132 and 234, some additional references are made here. In particular, interleaving of bit streams 112 and 118 may be advantageous for bit streams to be multiplexed into one channel for sending. In this case, it may be advantageous to interleave VLC bit stream 112 on one side and PIPE encoding bit streams 118 on the other hand to comply with certain conditions to be met such as adherence to some maximum decoding delay. Still, in other words, it may be necessary that the relative time shift between the times of the syntax elements and the source symbols, respectively, be recovered on the decoding side on the one hand, and the relative time travel according to their positions into an analytical bit stream on the other hand, not exceeds the specified maximum delay. Many alternatives to solve this problem are described below. One of these possibilities includes entropy encoders 116 to be variable-length encoders configured to map sequence alphabet symbols to code words, and entropy decoders 210 to perform inverse mapping. The VLC code words of the bit stream 112 and PIPE of the bit streams 118 may be, but need not be, selected such that no code word of any of these bit streams is a prefix of any code word of any of the other bit streams, so that the boundaries of the code word remain uniquely determined on the decoder side. In any case, interleaver 128 can be configured to reserve and buffer codeword sequence entries for the codeword in the first bit stream 112 and the second bit stream 118 in a sequential order depending on the order in which the alphabet symbols of the sequence of 124 alphabet symbols forward through the selection module 120 to many entropy encoders 116 give a result at the beginning of a new alphabetic symbol sequence, which is to be mapped to the corresponding codeword in the respective entropy encoder 116 and the new source symbol of the second sub stream 108 is mapped by the VLC encoder 102, respectively. In other words, the interleaver 128 inserts the code words of the bit stream 112 into the common bit stream 126 in the order of the source symbols from which they were obtained by VLC encoding, in their order in sub stream 108 and source symbol stream 106, respectively. The code words output by entropy coders 116 are input to the common bit stream 126 between consecutive VLC code words of the bit stream 112. Thanks to the PIPE coding, the categorization of the alphabet symbols by the allocation module 114 and the selection module 120, respectively, each of the code words of the entropy coders 116 have alphabet symbols various source symbols of sub stream 110 encoded therein. The positions of the PIPE encoded code words of bit streams 118 in a common bit stream 126 among them and relative to the VLC, the code word of the bit stream 112 is determined by the first alphabet symbol encoded in each code word, i.e. the oldest in time, respectively. The order of these major alphabet symbols coded for the code words of bit streams 118 in the alphabet symbol stream 124 determines the order of the code words of the bit streams 118 in the common bit stream 126 among themselves; relative to the VLC bit words of the bit stream 112, the source symbol to which these main alphabet symbols encoded in the bit stream code words 118 belong, determine between which successive code words of the bit stream 112 the respective code word of any of the bit streams 118 is to be placed. In particular, subsequent VLC code words between which the respective code word of any of the bit streams 118 is to be placed are those between which the source symbol of sub stream 110 is placed in the original order of the un-divided source symbol stream 106, to which the corresponding main alphabet symbol belongs encoded to the corresponding code word of bit streams 118. Interleaver 128 can be configured to delete code words input on the above codeword entries in sequential order to obtain the common bit stream 126 of the entwined codewords. As already described above, entropy encoders 116 can be configured to sequentially enter their code words at the codeword inputs reserved for the corresponding entropy coder 116 and the selection module 120 can be configured. to forward the alphabet symbols representing the source symbols of the second sub stream 110 in the order in which the source symbols of the first sub stream 108 and the second sub stream 110 are intertwined into a sequence of 106 source symbols.

[0044] Additional measures may be provided to deal with situations where specific entropy encoders 116 are selected so infrequently that it takes a long time to obtain a valid code word in this very rarely used entropy encoder 116. Examples for such measures are described in more detail below. In particular, the interleaver 128 together with the entropy encoder 116 can, in this case, be configured to flow their alphabet symbols already collected and the codewords entered at the codeword inputs indicated above, respectively, in such a way that the time of this flowing procedure can be predicted or emulated on the decoding side.

[0045] On the decoding side, deinterleaver 230 can operate in the reverse sense: as soon as, according to the analysis scheme indicated above, the next source symbol to be decoded is a VLC encoded symbol, the current code word in the common bit stream 228 is considered to be the VLC code word and forwarded in bit stream 206 to the VLC decoder 200. On the other hand, whenever any of the alphabet symbols belonging to any of the PIPE encoded symbols of sub-stream 208 is the main symbol of the alphabet, i.e. it requires a new mapping of the code word corresponding to one of the bit streams 216 to the corresponding sequence of the alphabet symbol by the appropriate entropy decoder 210, current word The code bit of the common bit stream 228 is considered a PIPE encoded code word and forwarded to the corresponding entropy decoder 210. Detection of the next code word boundary, i.e. detecting the extension of the next codeword with the end of the codeword just passed on to any of the decoders 200 and 202, respectively, to its end in the incoming interlaced bit stream 228 may be delayed, and be performed according to knowledge, with the decoder 200 and 202 being dedicated the recipient of the next code words according to the above-outlined principle: based on this knowledge, the dictionary used by the receiving decoder is known and the corresponding detected codeword. If, on the other hand, dictionaries were designed so that codeword boundaries would be detected without a-priori knowledge of the receiving decoder among 200 and 202, then codeword separation could be performed in parallel. In any case, due to interleaving, source symbols are available at the decoder in entropy decoded form, i.e. as source symbols, in their correct order with reasonable delays.

[0046] After describing the above embodiments for the entropy coding device and the corresponding entropy decoding device, details for the above-indicated PIPE encoders and PIPE decoders are then described.

[0047] The PIPE encoder is shown in Fig. 3. They can also be used as the PIPE encoder in Fig. 1a. The PIPE encoder losslessly converts the source symbol stream 1 into a set of two or more partial bit streams 12. Each source symbol 1 can be associated with a category or type of a set of one or more categories or types. As an example, categories can specify the type of source symbol. In the context of hybrid video coding, a separate category may be associated with macro-block coding modes, block coding modes, reference image indexes, motion vector differences, subdivision flags, coded block flags, quantization parameters, transformation coefficient levels, etc. In other applications, such areas like audio, speech, text, document or general data encoding, different categorization of source symbols are possible. Generally, each source symbol may take a value from a finite or infinite countable set of values, where the set of possible values ​​of the source symbol may be different for different categories of the source symbol. To reduce the complexity of the coding and decoding algorithm, and to enable the overall coding and decoding structure of the structure for various source symbols and source symbol categories, source symbols 1 are transformed into sequential ordered binary decisions and these binary decisions are then processed by simple binary coding algorithms. Therefore, the binary module 2 maps the value of each source symbol 1 into the sequence (or string) bin 3 in a bijective manner. The sequence bin 3 represents a set of ordered binary decisions. Each bin 3 or binary decision can take one value of a set of two values, for example one of the values ​​0 and 1. The binarization scheme can be different for different categories of source symbols. The binarization scheme for a given category of source symbols may depend on the set of possible values ​​of source symbols and / or other properties of source symbols of a given category. Table 1 shows three examples of binarization schemes for countable infinite sets. Binarization schemes for countable infinite sets can also be applied to finite sets of symbol values. In particular for large sets of finite symbol values, inefficiency (resulting from unused bin sequences) may be insignificant, but the universality of such binarization systems provides an advantage in terms of complexity and memory requirements.

For small finite sets of symbol values, it is often desirable (in terms of coding efficiency) to adapt the binarization scheme to the number of possible symbol values. Table 2 presents three examples of binarization schemes of finite sets of 8 values. Binarization schemes for finite sets can be derived from universal binarization schemes for an infinite countable set by modifying some bin sequences in such a way that finite bin sequence sets are redundant code (and potential reorganization of bin sequences). As an example, the truncated unary binarization scheme in Table 2 was created by modifying the bin sequence on the source symbol 7 of universal unary binarization (see Table 1). Chisel and reordered binaryization of Exp-Golomb order 0 in Table 2 was created by the binary modification sequence of the source symbol 7 of the universal Exp-Golomb binaryization order 0 (see Table 1) and by changing the sequence of the bin sequence (truncated bin sequence for symbol 7 has been assigned to symbol 1). For a finite set of symbols, it is also possible to use non-systematic / non-universal binarization schemes, as described in the last column of Table 2.

Table 1: Examples of binarization of countable infinite sets (or large finite sets).

<td>symbol value</td><td>unary binarization</td><td>binarization of Exp-Golomb order 0</td><td>binarization of Exp-Golomb order 1</td>

<td> 0</td><td> 1</td><td> 1</td><td> 10</td>

<td> 1</td><td> 01</td><td> 010</td><td> 11</td>

<td> 2</td><td> 001</td><td> 011</td><td> 0100</td>

<td> 3</td><td> 0001</td><td> 0010 0</td><td> 0101</td>

<td> 4</td><td> 0000 1</td><td> 0010 1</td><td> 0110</td>

<td> 5</td><td> 0000 01</td><td> 0011 0</td><td> 0111</td>

<td> 6</td><td> 0000 001</td><td> 0011 1</td><td> 0010 00</td>

<td> 7</td><td> 0000 0001</td><td> 0001 000</td><td> 0010 01</td>

Table 2: Examples of binarization for finite sets.

<td>symbol value</td><td>beheaded unary binarization</td><td>beheaded and in a changed order binaryization ExpGolomb of 0</td><td>non-systematic binarization</td>

<td> 0</td><td> 1</td><td> 1</td><td> 000</td>

<td> 1</td><td> 01</td><td> 000</td><td> 001</td>

<td> 2</td><td> 001</td><td> 010</td><td> 01</td>

<td> 3</td><td> 0001</td><td> 011</td><td> 1000</td>

<td> 4</td><td> 0000 1</td><td> 0010 0</td><td> 1001</td>

<td> 5</td><td> 0000 01</td><td> 0010 1</td><td> 1010</td>

<td> 6</td><td> 0000 001</td><td> 0011 0</td><td> 1011 0</td>

<td> 7</td><td> 0000 000</td><td> 0011 1</td><td> 1011 1</td>

[0048] Each bin 3 of the bin sequence created by the binarization module 2 is fed to the parameter allocation module 5 in sequential order. The allocator parameter assigns a set of one or more parameters to each bin 3 and the output of the bin of the associated parameter set 5. The set of parameters is determined in the same way in the encoder and decoder. A parameter set may consist of one or more of the following parameters:

- a measure for the probability estimate for one of the two possible bin values ​​for the current bin,

- a measure for the probability estimate for the less likely bin or more likely bin value for the current bin,

- an identifier identifying the estimate for which of the two possible bin values ​​represent the less likely or more likely bin value for the current bin,

- the category of related source symbols,

- measure for the meaning of the related source symbol,

- a measure for the location of the related symbol (e.g. in a temporal, spatial or volumetric data set),

- an identifier that identifies the protection of the bin channel code or associated source symbol,

- identifier that specifies the bin encryption scheme or associated source symbol,

- class identifier for the associated symbol - the number of bins in the bin sequence for the associated source symbol.

[0049] The allocation module 4 parameter can assign each bin 3.5 to a measure for the probability estimate for one of the two possible bin values ​​for the current bin. The allocation module parameter 4 assigns each bin 3.5 with a measure to estimate the probability for the less likely or more likely bin value for the current bin, and an identifier identifying an estimate for which of the two possible bin values ​​represents the less likely or more likely bin value for the current bin. It should be noted that the probability of the less likely or more likely bin value and the identifier of which of the two possible bin values ​​means the less likely or more likely bin value are equivalent probabilistic measures of one of the two possible bin values.

[0050] The parameter allocation module 4 can assign each bin 3.5 with a measure to estimate the probability for one of the two possible bin values ​​on the current bin and one or more additional parameters (which may include one or more of the above mentioned parameters). In addition, the parameter assignment module 4 can assign each bin 3.5 with a measure for estimating the probability for the less likely or more likely bin value for the current bin, with the identifier specifying an estimate for which of the two possible bin values ​​the less likely or more likely is represented the bin value for the current bin, and one or more additional parameters (which may include one or more of the parameters listed above).

[0051] The parameter allocation module 4 may determine one or more of the above-mentioned probabilistic measures (measure for the probability estimate for one of the two possible bin values ​​for the current bin, measure for the probability estimate for the less likely or more likely bin value for the current bin, identifier specifying estimates, for which of the two possible bin values ​​means the less likely or more likely bin values ​​for the current bin) based on a set of one or more previously coded symbols. Coded symbols that are used to determine probabilistic measures may contain one or more already coded symbols of the same type of symbols, one or more already coded symbols of the same type of symbols that correspond to data sets (e.g. in the form of blocks or groups of samples) adjacent spatial and / or temporal positions (in relation to the data set related to the current source symbol), or one or more previously coded symbols of different symbol categories that correspond to data sets of the same and / or adjacent spatial and / or temporal locations (with respect to the data set associated with the current source symbol).

[0052] Each bin with associated parameter set 5, which is the output of the allocation module 4 parameter is fed to the bin selection module 6. The bin buffer selection module 6 optionally modifies the value of bin 5 based on the input bin values ​​and associated parameters 5 and provides output bin 7 - with the potentially modified value - to one of two or more bin 8 buffers. The bin buffer 8 to which the output bin 7 is sent is determined based on the value of the input bin 5 and / or the value of the associated parameters 5.

[0053] The bin buffer selection module 6 cannot modify the bin value, i.e. the output bin 7 always has the same value as the input bin 5.

[0054] The bin buffer selection module 6 can determine the value of the output bin 7 based on the value of the input bin 5 and the associated measure for the probability estimate for one of the two possible bin values ​​for the current bin. The output value of bin 7 can be set to a value equal to the value of bin 5 if the probability measure for one of the two possible bin values ​​on the current bin is less than (or lower than or equal to) the specified threshold; if the probability measure for one of the two possible bin values ​​on the current bin is greater than or equal (or greater) to the specified threshold, the value of output bin 7 is modified (i.e. it is set to the opposite value of the input bin). The output bin value 7 can be set equal to the value of bin 5 if the probability measure for one of the two possible bin values ​​for the current bin is greater than (or higher than or equal to) the specified threshold; if the probability measure for one of the two possible bin values ​​on the current bin is less than or equal (or less) to the specified threshold, the value of output bin 7 is modified (i.e. it is set to the opposite value of the input bin). The threshold value may correspond to a value from 0.5 for the estimated probability for both possible bin values.

[0055] The bin buffer selection module 6 can determine the value of the output bin 7 based on the value of the input bin 5 and an associated identifier defining an estimate for which of the two possible bin values ​​the less likely or more likely bin value for the current bin is represented. The value of the output bin 7 can be set to a value equal to the value of the input bin 5 if the identifier determines that the first of the two possible bin values ​​represents the less likely (or more likely) bin value for the current bin, and the value of output bin 7 is modified (i.e. the opposite bin value is set) if the identifier indicates that the second of the two possible bin values ​​represents the less likely (or more likely) bin value for the current bin.

[0056] The bin buffer selection module 6 may determine the bin buffer 8 to which the output bin 7 is sent based on the associated measure for the probability estimate for one of the two possible bin values ​​for the current bin. The set of possible values ​​for the measure for the probability estimate for one of the two possible bin values ​​can be finalized and the bin buffer selection module 6 contains a table that associates exactly one bin buffer 8 with each possible value for estimating the probability for one of the two possible bin values, where different values ​​for the measure for the probability estimate for one of the two possible bin values ​​can be associated with the same bin 8 buffer. In addition, the range of possible values ​​for the measure for the probability estimate for one of the two possible bin values ​​can be subdivided into a number of intervals, with the bin buffer selection module 6 determining the interval indicator for the current measure for the probability estimate for one of the two possible bin values ​​and the bin buffer selection module 6 contains a table that associates exactly one bin buffer 8 with every possible value for the interval indicator, where different values ​​for the range indicator can be associated with the same bin 8. Input bin 5 from opposite measures for probability estimation for one of two possible bin values ​​(opposite measures are those that represent probability estimates P and 1 - P) can be served in the same buffer bin 8. In addition, the association of the measure for the probability estimate for one of the two possible bin values ​​per current bin with a specific bin buffer is time-adjusted, for example to ensure that the created partial streams have similar bit rates.

[0057] The bin buffer selection module 6 may determine the bin buffer 8 to which the output bin 7 is sent based on the associated measure for the probability estimate for the less likely or more likely bin value for the current bin. The set of possible values ​​for the measure for the probability estimate for the less likely or more likely bin value can be finite, and the bin buffer selection module 6 contains a table that associates exactly one bin buffer 8 with each possible value of the estimated probability for a less likely or more likely bin value, where different values ​​for the measure for the probability estimate for the less likely or more likely bin value can be associated with the same bin 8 buffer. In addition, the range of possible values ​​for the measure for the probability estimate for the less likely or more likely bin value can be divided into several intervals, the bin buffer selection module 6 determines the interval indicator for the current measure for the probability estimate for the less likely or more likely bin value, and the module the bin 6 selection bin contains a table that associates exactly one bin 8 buffer with each possible value for the interval indicator, where different values ​​for the interval indicator can be associated with the same bin 8. The association of the measure for the probability estimate for the less likely or more likely bin value for the current bin with a specific bin buffer can be adjusted in time, for example to ensure that the created partial streams have similar bit rates.

[0058] Each of two or more bin 8 buffers is connected to exactly one bin 10 encoder and each bin encoder is connected to only one bin 8 buffer. Each bin 10 encoder reads the bins from the associated bin 8 buffer and converts the sequence of bin 9 into codeword 11, which represents a bit sequence. Bin 8 buffers represent first-in-first-of-buffers; bins that are passed on (in the order given) to the bin buffer 8 are not pre-encoded bin, which are given earlier (in the order shown) to the bin buffer. The code words 11 which are to come out of the specific bin encoder 10 are written in particular to the partial bit stream 12. The general coding algorithm converts source symbols 1 into two or more partial bit streams 12, with the number of partial bit streams equal the number of bin buffers and bin encoders. The bin encoder 10 can convert the variable number of bin 9 into code word 11 of the variable number of bits. One of the benefits of the above and below PIPE encoding is that bin coding can be performed in parallel (for example, for different groups of probability measures), which reduces processing time for several implementations.

[0059] Another advantage of PIPE encoding is that the bin coding that takes place through the bin encoders 10 can be designed for different sets of parameters 5. In particular, the bin coding and coding can be optimized (in terms of coding efficiency and / or complexity) for different groups of estimated probabilities. On the one hand, this allows the coding / decoding complexity to be reduced relative to the arithmetic coding of algorithms with similar coding efficiency. On the other hand, it allows improving coding efficiency relative to VLC coding algorithms with similar coding / decoding complexity. Bin 10 encoders can implement different coding algorithms (i.e., mapping code word to bin sequences) for different measure groups to estimate probability for one of two possible bin 5 values ​​for the current bin. Bin 10 encoders may implement different coding algorithms for different measure groups to estimate the probability for the less likely or more likely bin value for the current bin. Alternatively, bin encoders may implement different coding algorithms for different channel security codes. Bin 10 encoders can implement different encoding algorithms for different encryption schemes. Bin 10 encoders can implement different coding algorithms for different combinations of channel security codes and measure groups to estimate the probability for one of two possible bin 5 values ​​for the current bin. The bin 10 encoders implement different coding algorithms for different combinations of channel security codes and measure groups to estimate the probability for the less likely or more likely bin 5 value for the current bin. Bin 10 encoders can implement different coding algorithms for different combinations of encryption systems and measure groups for estimating the probability for one of the two possible bin 5 values ​​for the current bin. Bin 10 encoders can implement different coding algorithms for different combinations of encryption systems and measure groups for estimating the probability for the less likely or more likely value of bin 5 for the current bin.

[0060] Bin encoders 10 - or one or more of the bin encoders - can be binary arithmetic coding engines. One or more of the bin encoders may be a binary arithmetic coding engine in which the mapping of the representative probability pLPS LPS / LPB for a given bin buffer to the appropriate width Rlps of the code interval - i.e. the interval of the internal state subdivision of the binary arithmetic coding engine, which is defined by the current width R interval and current offset L of the interval, identifying, for example, the lower limit of the code interval - is implemented using an array. For each binary arithmetic coding engine based on an array associated with a given bin buffer, K representative of the width value {Q0, ... QK-1} of the interval can be used to represent RLPS with the choice of K and a representative width value {Q0, ... QK-1} of the interval depending on the bin buffer. For the selection K> 1, the arithmetic coding bin may include sub-steps of mapping the current width R of the interval to the quantization index q with the values ​​{0, ..., K-1}, and performing a division interval by accessing the appropriate partial value of the Qq value of the interval width from the array using q as an indicator. For the selection K = 1, i.e. for the case in which only one representative of the Q0 value of the interval width is given, this Q0 value can be selected as a power of two, so as to enable decoding of many MPS / MPB values ​​entered into the appropriate bin buffer in one renormalization cycle. The resulting code words from each arithmetic coding engine can be separately transmitted, packaged or stored, or they may be interleaved for transmission or storage as described below.

[0061] This means that the binary arithmetic coding engine 10 can perform the following steps in bin coding in bin buffer 8:

1. Receiving valLPS, bin from the bin buffer (reminder: the binary arithmetic coding engine 10 considered here was chosen to obtain "bin" because (or, in other words, "bin" was associated with the corresponding binary arithmetic coding engine) of probability distribution estimation, such as p_state [bin], has been associated with this binary arithmetic coding engine)

2. R quantization:

q index = Qtab [R »q] ..... ,. . ...

— ^{L, J.} (or other form of quantization)

3. Determination of RLPS and R:

RLPS = Rtab [q_index] (note that p_state is not listed here because it is set for the binary arithmetic coding engine under consideration, i.e. p_state [encoder] and Rtab have pre-calculated values ​​for p [p_state [encoder] ] · Q [q_index] R = R - RLPS [that is, R is pre-updated as if "bin" was MPS]

4. Calculation of the new partial range:] if (BIN + 1 - valMPS), then

L &lt;L + RR Rlps

5. Renormalization of L and R, entering bits with q_index describing the quantization value indicator read from Qtab, p_state describing the current state (constant for the binary arithmetic coding engine 10),

RLPS describes the width range corresponding to LPS and valMPS describes the bit value corresponding to MPS.

[0062] Accordingly, the binary arithmetic decoding engine 22 may perform the following steps when decoding bin output to bin buffer 20:

1. Receiving a request to the bin (reminder: the given binary arithmetic decoding engine 22 considered here was selected for "bin" decoding because (or, in other words, "bina" was associated with the corresponding binary arithmetic decoding engine 22) probability distribution estimates, for example such like p_state [bin], has been associated with this engine 22 decoding binary arithmetic)

2. R quantization:

q_index = Qtab [R »q] _{(a | h) other} p_:,,«_: quantization)

3. Determination of RLPS and R:

RLPS = Rtab [q_index] (note that p_state is not listed here because it is set for the binary arithmetic coding engine under consideration, i.e. p_state [encoder] and Rtab have pre-calculated values ​​for p [p_state [encoder] ] · Q [q_index] R = R - RLPS [that is, R is pre-updated as if "bin" was MPS]

4. Determining the bin depending on the location of the partial range:

if (V> R) is bin 1 - valMPS (bin is decoded as LPS; bin buffer selection module 18 will get the actual bin value by using this bin and valMPS information)

V VR

R Rlps or bin valMPS (bin is decoded as MPS: the bin buffer selection module 18 will get the actual bin value using this bin and valMPS information)

5. Renormalization of R, entering bits with q_index describing the quantization value indicator read from Qtab, p_state describing the current state (constant for the binary arithmetic decoding engine 22),

RLPS describes the width range corresponding to LPS and valMPS describes the bit value corresponding to MPS, and

V describes the value from inside the current partial interval.

[0063] Bin encoders 10 - or one or more of the bin encoders - can represent entropy encoders that directly map input bin sequences 9 to code words 10. Such mapping can be effectively implemented and does not require a complicated arithmetic coding engine. Reverse mapping of code words to bin sequences (as done in the decoder) should be unique to ensure perfect decoding of the input sequence, but mapping the bin 9 sequence to code words 10 does not necessarily have to be unique, i.e. it is possible that a specific bin sequence can be mapped on more than one sequence of code words. Mapping bin 9 input sequences to code words 10 can also be bijective. Preferably the bin encoders 10 - or one or more of the bin encoders - can represent entropy encoders that directly map variable length sequences of input bins 9 to variable length code words 10. The output codewords can represent redundancy-free codes such as general Huffman codes or canonical Huffman codes.

[0064] Two examples for mapping the bijective type of bin sequence to code free of redundancy are shown in Table 3. The output code words may be redundant codes suitable for detecting errors and removing errors. These output code words may be the appropriate encryption codes for encrypting the source symbols.

Table 3: Examples for mappings between bin sequences and code words.

<td>bin sequence (bin order from left to right)</td><td>codewords (bit order from left to right)</td>

<td>oooo oooo</td><td> 1</td>

<td> 0000 0001</td><td>oooo</td>

<td> 0000 001</td><td> 0001</td>

<td> 0000 01</td><td> 0010</td>

<td> 0000 1</td><td> 0011</td>

<td> 0001</td><td> 0100</td>

<td> 001</td><td> 0101</td>

<td> 01</td><td> 0110</td>

<td> 1</td><td> 0111</td>

<td colspan="2"></td>

<td>bin sequence (bin order from left to right)</td><td>codewords (bit order from left to right)</td>

<td> 0000 0000</td><td> 1</td>

<td> 0000 0001</td><td> 0000</td>

<td> 0000 001</td><td> 0001</td>

<td> 0000 01</td><td> 0010</td>

<td> 0000 1</td><td> 0011</td>

<td> 0001</td><td> 0100</td>

<td> 001</td><td> 0101</td>

<td> 01</td><td> 0110</td>

<td> 1</td><td> 0111</td>

<td colspan="2"></td>

[0065] Bin encoders 10 - or one or more of the bin encoders - can represent entropy encoders that directly map variable-length sequences of input bins of 9 fixed-length code words. The bin 10 encoders - or one or more of the bin encoders - represent entropy encoders that directly map 9 fixed-length input bin sequences to 10 variable-length code words.

[0066] The PIPE decoder is shown in Fig. 4. In general, the reverse operation decoder from the encoder of Fig. 3, such that the (previously encoded) source symbol sequence 27 is decoded from a set of two or more partial bit streams 24. The decoder includes two other flow processes: a flow for a data request that maps the data flow from an encoder and a flow of data that is the reverse of a data flow from an encoder. In the performance of Fig. 4, dashed arrows mean data request flow, while solid arrows indicate data flow. Decoder bricks generally replicate encoder bricks, but perform reverse operations.

[0067] The decoding of the source symbol is triggered by a request of a new decoded source symbol 13, which is sent to the binarization module 14. Each request of a new decoded source symbol 13 can be associated with a category of a set of one or more categories. The category that is associated with the source symbol request is the same as the category that was associated with the corresponding source symbol during encoding.

[0068] The binarization module 14 maps the source symbol request 13 to one or more bin requests that are sent to the parameter assignment module 16. In the final bin request response, which is sent to the parameter assignment module 16 by the binarization module 14, the binarization module 14 receives the decoded bin 26 from the bin buffer selection module 18. Binarization module 14 compares the received sequence of decoded bin 26 with the bin sequence of the specified binarization scheme for the desired source symbol, and if the received sequence of decoded bin 26 corresponds to the binarization of the source symbol, the binarization module empties its bin buffer and sends the decoded source symbol as the final request for a new decoded symbol.

If the already received decoded bin sequence does not match any of the bin sequences for the binarization scheme to the desired source symbol, the binarization module sends another bin request to the parameter allocation module until the decoded bin sequence matches one of the bin sequences of the binarization scheme for the desired source symbol. For each source symbol request, the decoder uses the same binarization scheme that was used to encode the corresponding source symbol. The binarization scheme may be different for different categories of source symbols. The binarization scheme for a given category of source symbols may depend on the set of possible values ​​of source symbols and / or other properties of source symbols of a given category.

[0069] The parameter allocator 16 determines a set of one or more parameters for each bin request and sends a bin request from the associated parameter set to the bin buffer selection module. The set of parameters that are assigned to the desired bin by the parameter assignment module is the same as the one that was assigned to the corresponding bin during coding. The parameter set may consist of one or more parameters that are listed in the encoder description.

[0070] The parameter allocator 16 may associate each bin request with a measure for estimating the probability for one of the two possible bin values ​​on the current bin request. In particular, the parameter allocator 16 can associate each bin request with a measure to estimate the probability for a less likely or more likely bin value for the current bin request and an identifier identifying an estimate for which of the two possible bin values ​​represents the less likely or more likely bin value for the current bin requests.

[0071] The parameter allocator 16 may associate each bin request 15.17 with a measure for estimating the probability for one of two possible bin values ​​per current bin request and one or more further parameters. The parameter allocator 16 can associate each bin request 15, 17 with a measure for estimating the probability for the less likely or more likely bin value for the current bin request, identifier identifying an estimate for which of the two possible bin values ​​the less likely or more likely bin value is represented on the current bin request, and one or more additional parameters (which may be one or more of the above-mentioned parameters).

[0072] The parameter allocation module 16 may determine one or more of the above-mentioned probabilistic measures (unit of measure for the probability estimate for one of the two possible bin values ​​on the current bin request, measure for the probability estimate for the less likely or more likely bin value for the current requested bin, an identifier that specifies the estimate, for which of the two possible bin values ​​the less likely or more likely bin value is represented on the current bin request) based on a set of one or more already decoded symbols. Specifying probabilistic measures for a specific bin request replicates the process in the encoder to the appropriate bin. Decoded symbols that are used to determine probabilistic measures may contain one or more already decoded symbols from the same type of symbols, one or more already decoded symbols from the same type of symbols that correspond to the data set (e.g. in the form of blocks or groups of samples) adjacent spatial and / or temporal location (in relation to the data set associated with the current source symbol request), or one or more already decoded symbols of different symbol categories that correspond to a data set of the same and / or in an adjacent spatial and / or temporal position (with respect to the data set associated with the current source symbol request).

[0073] Each bin request with the associated parameter set 17 that exits the allocation parameter module 16 is fed to the bin buffer selection module 18. Based on the associated parameter set 17, the bin buffer selection module 18 sends a bin 19 request to one of two or more bin buffers 20 and receives the decoded bin 25 from the selected bin buffer 20. The decoded bin 25 input is optionally modified and the decoded output bin 26 - with potentially modified values ​​- is sent to the binarization module 14 as the final response to the bin request from the associated parameter set 17.

[0074] The bin buffer 20 to which the bin request is forwarded is selected in the same way as the bin buffer to which the bin output of the bin buffer selection module on the encoder side was sent. [0075] The bin buffer selection module 18 can determine the bin buffer 20 to which the bin 19 request is sent based on the associated measure for the probability estimate for one of the two possible bin values ​​for the current bin request. The set of possible values ​​for the measure for the probability estimate for one of the two possible bin values ​​can be finalized and the bin buffer selection module 18 includes a table that associates exactly one bin buffer 20 with each possible probability estimation value for one of the two possible bin values, where different the values ​​for the measure for the probability estimate for one of the two possible bin values ​​can be associated with the same bin 20 buffer. The range of possible values ​​for the measure for the probability estimate for one of the two possible bin values ​​can be divided into several sub-ranges, the bin buffer selection module 18 determines the interval indicator for the current measure for the probability estimate for one of the two possible bin values, with the buffer selection module 18 bin contains a table that associates exactly one bin 20 buffer with every possible value for the range index, in which different values ​​for the range indicator can be associated with the same bin 20. Buffer requests 17 with opposite measures for the probability estimate for one of the two possible bin values ​​(opposite measures are those that represent the probability estimates P and 1 - P) can be forwarded to the same bin 20 buffer. In addition, the association of the measure for the probability estimate for one of the two possible bin values ​​on the current bin request with a specific bin buffer can be adjusted in time.

[0076] The bin buffer selection module 18 may determine the bin buffer 20 to which the bin 19 request is sent based on the associated measure for the probability estimate for the less likely or more likely bin value for the current bin request. The set of possible values ​​for the measure for the probability estimate for the less likely or more likely bin value can be finite, and the bin buffer selection module 18 can include a table that associates exactly one bin buffer 20 with each possible value of the probability estimate for a less likely or more likely bin value . where different values ​​for the measure for the probability estimate for the less likely or more likely bin value can be associated with the same bin buffer 20. The range of possible measure values ​​for the probability estimate for the less likely or more likely bin value can be divided into several intervals, the bin buffer selection module 18 specifies the interval indicator for the current measure for the probability estimate for the less probable or more likely bin value, and the buffer selection module 18 bin contains a table that associates exactly one bin 20 buffer with every possible value for the interval indicator, where different values ​​for the range indicator can be associated with the same bin 20 buffer. In conjunction the measures for the probability estimate for the less likely or more likely bin value for the current bin request from a given bin buffer it is adjusted in time.

[0077] Upon receiving the decoded bin 25 from the selected bin buffer 20, the bin buffer selection module 18 potentially modifies the input bin 25 and sends the output bin 26 - with the potentially modified value - to the binary module 14. An input / output bin mapping the bin buffer selection module 18 is the inverse of the input / output bin mapping the bin buffer selection module on the encoder side.

[0078] The bin buffer selection module 18 can be configured not to change the bin value, i.e. the output bin 26 always has the same value as the input bin 25.

[0079] The bin buffer selection module 18 may determine an output bin value of 26 based on the input bin value 25 and a measure for the probability estimate for one of the two possible bin values ​​for the current requested bin that is associated with the bin 17 request. The value of 26 bin output may be a set equal to the value of input bin 25 if the probability measure for one of the two possible bin values ​​for the current bin request is less than (or less than or equal to) the specified threshold; if the probabilistic measure for one of the two possible bin values ​​for the current bin request is greater than or equal to (or greater than) the specified threshold value, the 26 bin output value is modified (i.e., it is the set opposite to the input bin value). The 26 bin output value can be a set equal to the 25 bin value if the measure for the probability for one of the two possible bin values ​​for the current bin request is greater than (or greater than or equal to) the specified threshold; if the probability measure for one of the two possible bin values ​​for the current bin request is less than or equal to (or less than) the specified threshold value, the 26 bin output value is modified (i.e., it is the set opposite to the input bin value). The value for the threshold value may correspond to the value 0.5 for the estimated probability for both possible bin values.

[0080] The bin buffer selection module 18 may determine an output bin value of 26 based on an input bin value of 25 and an identifier defining an estimate for which of the two possible bin values ​​the less likely or more likely value for the current bin request that is associated with request bin 17. The value of 26 bin output can be a set equal to the value of 25 bin input if the identifier specifies that the first of the two possible bin values ​​represents the less likely (or more likely) bin value for the current bin request, and the 26 bin output value is modified (i.e., it is a set opposite to the input bin value) if the identifier specifies that the second of the two possible bin values ​​represents the less likely (or more likely) bin value for the current bin request.

[0081] As described above, the bin buffer selection module sends a bin 19 request to one of two or more bin 20 buffers. Bin 20 buffers represent the first-in-first-of-buffers that are fed from bin 21 decoded sequences with connected bin decoders 22. As a response to the bin 19 request, which is sent to the bin buffer 20 from the bin buffer selection module 18, the bin buffer 20 removes from its bin the content that was first fed to bin buffer 20 and sends it to the bin buffer selection module 18. Bins that are previously sent to bin buffer 20 are previously deleted and sent to the bin buffer selection module 18.

[0082] Each of the two or more bin buffers 20 is connected to exactly one bin decoder 22 and each bin decoder is only connected to one bin buffer 20. Each bin decoder 22 reads the code words 23, which represent a sequence of bits, with a separate partial stream bits 24. The bin decoder converts code word 23 into a sequence of bin 21 which is sent to the connected bin buffer 20. The general decoding algorithm converts two or more of the partial bit streams 24 into the number of decoded source symbols, where the number of partial bit streams is equal to the number of bin buffers and bin decoders, and the decoding of the source symbols is triggered by requests for new source symbols. The bin 22 decoder can convert 23 bit code words with a variable number to a sequence of bin 21 with a variable number. One of the benefits of the above PIPE configuration is that bin decoding from two or more partial bit streams can be done in parallel (e.g. for different groups of probabilistic measures), which limits processing time for several implementations.

[0083] Another advantage of the above PIPE decoding is that bin decoding, which is performed by bin 22 decoders, can be specifically designed for various parameter settings 17. In particular, bin coding and decoding can be optimized (in terms of coding efficiency and / or complexity) for different groups of estimated probabilities. On the one hand, this makes it possible to limit the complexity of coding / decoding relative to the arithmetic coding of algorithms with similar coding efficiency. On the other hand, it allows improving coding efficiency relative to VLC coding algorithms with similar coding / decoding complexity. Bin 22 decoders can implement various decoding algorithms (i.e. mapping the bin sequence into code words) for different measure groups for the probability estimate for one of the two possible bin values ​​17 for the current bin request. Bin 22 decoders can implement different decoding algorithms for different measure groups for a probability estimate for the less likely or more likely bin value for the current requested bin. Bin 22 decoders can implement different decoding algorithms for different channel security codes. Bin 22 decoders can implement different decoding algorithms for different encryption schemes. Bin 22 decoders can implement different decoding algorithms for different combinations of channel security codes and measure groups for probability estimates for one of the two possible bin values ​​17 for the current desired bin. Bin 22 decoders can implement different decoding algorithms for different combinations of channel security codes and measure groups for probability estimates for the less likely or more likely bin value 17 for the current requested bin. Bin 22 decoders can implement different decoding algorithms for different combinations of encryption schemes and measure groups for probability estimates for one of the two possible bin values ​​17 for the current desired bin. Bin 22 decoders can implement different decoding algorithms for different combinations of encryption schemes and measure groups for a probability estimate for the less likely or more likely value of bin 17 for the current requested bin.

[0084] Bin 22 decoders perform inverse mapping of respective bin encoders on the encoder side.

[0085] Bin 22 decoders - or one or more of the bin decoders - can represent binary arithmetic decoding engines.

[0086] Bin 22 decoders - or one or more of the bin decoders - can represent entropy decoders that directly map code words 23 to bin sequences 21. Such mappings can be efficiently implemented and do not require a complex arithmetic coding engine. Mapping code words to bin sequences must be unique. Mapping code words 23 to bin 21 sequences may be of the bijective type. Bin 10 decoders - or one or more of the bin decoders - can represent entropy decoders that directly map variable-length code words 23 to variable-length bin 21 sequences. Code word input can represent codes without redundancy such as general Huffman codes or canonical Huffman codes. Two examples for bijective code mapping without redundancy to the bin sequence are shown in Table 3. Code word input may represent unnecessary codes suitable for error detection and error recovery. The codeword input may represent encryption codes.

[0087] Bin 22 decoders - or one or more bin decoders - can represent entropy decoders that directly map fixed-length code words 23 to variable-length bin 21. Alternatively, bin 22 decoders - or one or more of the bin decoders represent entropy decoders that directly map variable-length code words 23 to a fixed-length bin 21 sequence.

[0088] Thus, Figs. 3 and 4 show the PIPE encoder for encoding the source symbol sequence 1 and the PIPE decoder for reconstructing the same. That is, the PIPE encoder in Fig. 3 can be used as the PIPE encoder 104 in Fig. 1a with the binarization module 2 operating as the symbiliser 122, the 4 parameter allocation module operating as the allocation module 114, the bin buffer selection module 6 operating as the 120 selection module, and a pair of bin 8 buffer connected in series and a bin 10 encoder acting as the appropriate one of entropy encoders 116 each of which sends bit streams 12 corresponding to bit streams 118 in Fig. 1a. As will become clear from the comparison with Fig. 3 and Fig. 1, the allocation module 114 of Fig. 1a may have an input alternatively connected to the input side of the balancer 122 differently than the output page of the latter. Similarly, the PIPE decoder of Fig. 4 can be used like the PIPE decoder 202 in Fig. 2a with partial bit streams 24 corresponding to bit streams 216 in Fig. 2, a pair of buffer 20 connected in series and a bin 22 decoder suitable for individual entropy decoders 210, a bin buffer selection module 18 operating as a selection module 214, a parameter allocation module 16 operating as an allocation module 212 and a binary module 14 operating as a desymbilizer 222. Again, a comparison between Fig. 2a and Fig. 4 clearly discloses that the connection between desymbolizer 222, allocation module 212 and selection module 214 can be configured differently, so that alternatively, the connections of Fig. 2a are changed to match those shown in Fig. 4. [0089] The PIPE encoder of Fig. 3 includes an allocation module 4 configured to assign the number of parameters 5 to each alphabet symbol of the alphabet 3 symbol sequence. Assignment is based on the information contained in the previous alphabet symbol sequence of alphabet symbols such as the category of the syntax element 1 for representation - such as binarization - to which the current alphabet symbol belongs and which, according to the syntactic structure of syntax elements 1, is currently expected which , in turn, is deduced from the history of previous syntactic elements 1 and symbols of alphabet 3. In addition, the encoder includes a plurality of entropy encoders 10 each of which is configured to convert the symbols of the alphabet 3 forwarded to the respective entropy coder to the corresponding bit stream 12, and a selection module 6 configured to forward each of the alphabet symbols 3 to one of the many encoders being selected. entropy 10, the choice depends on the number of parameters 5 assigned to the corresponding symbol of the alphabet 3. The PIPE decoder in Fig. 4 includes a plurality of entropy decoders 22, each of which is configured to convert the corresponding bit stream 23 to alphabet symbols 21; an allocation module 16 configured to assign the number of parameters 17 to each alphabet symbol 15 of the alphabet symbol sequence to be reconstructed based on information contained in the previously reconstructed alphabet symbols of the alphabet symbol sequence (see 26 and 27 in Fig. 4); and a selection module 18 configured to recover each alphabetic symbol of the alphabetic symbol sequence to be reconstructed with one of a plurality of entropy decoders 22 selected, wherein the selection depends on the number of parameters determined for the corresponding alphabetic symbol. The allocation module 16 may be configured such that the number of parameters assigned to each alphabet symbol includes, or is, a measure for an estimate of the probability of distribution among the possible values ​​of the alphabet symbol that the corresponding alphabet symbol may take. The sequence of alphabet symbols to be reconstructed can be a binary alphabet and the allocation module 16 can be configured such that the probability distribution estimation consists of a measure for the probability estimate of the less likely or more likely bin value of the two possible bin values ​​of the binary alphabet and an identifier identifying an estimate for which two possible bin values ​​represent the less likely or more likely bin value. The allocation module 16 may further be configured to internally assign a context to each alphabet symbol of the alphabet symbol sequence 15 to be reconstructed based on information contained in previously reconstructed alphabet symbols of the alphabet symbol sequence to be reconstructed from each context having a corresponding associated estimate probability distribution, and to adapt the probability distribution estimate for each context to the actual symbol statistics based on the symbol values ​​of the previously reconstructed alphabet symbols to which the respective context is assigned. The context may take into account the spatial relationship or proximity to the positions to which the syntax elements belong, such as in video or image coding, or even in tables for financial applications. Then, the measure for estimating the probability distribution for each alphabet symbol can be determined based on the probability distribution estimate associated with the context assigned to the corresponding alphabet symbol such as by quantizing the probability distribution estimate associated with the context assigned to the corresponding alphabet symbol to one of many representations of the distribution estimate probability to obtain a measure for estimating the probability distribution. The selection module can be configured such that the surjective association is determined between multiple entropy coders and multiple representations of a probability distribution estimate, i.e., each entropy coder has at least one representation of a probability distribution estimate associated with it, but more than one representation of a probability distribution estimate can be associated with one entropy encoder.

The binding can even be of the bijective type. The selection module 18 can be configured to vary the mapping quantization with a range of probability distribution estimates to multiple representations of the probability distribution estimates in a predetermined deterministic manner depending on these previously reconstructed alphabet symbols of the alphabet symbol sequence over time. That is, the selection module 18 can change the size of the quantization step, i.e. the probability distribution intervals are mapped to individual probability indices, which in turn can be surjectively associated with individual entropy decoders. Many entropy decoders 22, in turn, can be configured to customize their way of converting alphabet symbols to bit streams sensitive to a change in quantization mapping. For example, each entropy decoder 22 can be optimized for, i.e. may have an optimal compression rate for a given probability distribution estimate in the relevant quantization range, a probability distribution estimate, and may change the code word / symbol of the mapping sequence so as to adjust the location of that specific probability distribution estimate in the appropriate quantization range of the probability distribution estimate after changing the latter yes to optimize. The selection module can be configured to change the quantization mapping so that the rates at which alphabet symbols are recovered from multiple entropy decoders are less dispersed. As for the binarization module 14, it should be noted that the same can be left if the syntax elements are already binary. Also, depending on this type of decoder 22, the presence of buffers 20 is not necessary. In addition, buffers can be integrated in decoders.

[0090] To date, more details have been described above for the PIPE encoder 104 and the PIPE decoder 202 in Figs. 1a and 2, with reference to Figs. 3 and 4, which, if easily implemented in the devices of Figs. 1a and 2, lead to parallel outgoing bit streams in which the partial VLC and PIPE bit streams are converted in parallel. In the following, possibilities are described for combining partial PIPE bit streams for being subsequently transmitted in parallel with VLC bit streams, or with secondary interleaving of both bit streams, i.e., VLC bit stream and intertwined PIPE bit streams.

End of Sequence of Finite Source Symbols [0091] In PIPE encoders and decoders, encoding and decoding can be performed in a finite set of source symbols. Often, a certain amount of data, such as a still image, video frame or video sequence field, image slice, video frame slice or video sequence field, or a set of subsequent audio samples, etc. is encoded. For finite sets of source symbols, generally, partial streams that are created on the encoder side must be terminated, i.e. it must be ensured that all source symbols can be decoded from transmitted or stored partial bit streams. After the last one, bin is placed in the appropriate bin 8 buffer, the bin 10 encoder must ensure that the complete code word is written to the partial bit stream 12. If bin 10 represents the binary encoder of the arithmetic coding engine, the arithmetic codewords must be terminated. If the bin encoder 10 represents an entropy encoder that performs a direct mapping of the bin sequence to code words, the bin sequence that is stored in the bin buffer after the last bin has been written to the bin buffer cannot be the bin sequence that is associated with the code word (i.e. may represent the prefix of two or more bin sequences that are associated with code words). In this case, each of these code words associated with the bin sequence that contains the bin sequence in the receiver buffer as a prefix to be written to the partial bit stream (the bin buffer must be flushed). This can be done by placing a bin with a special or any value in the bin buffer until the code word is written. The bin encoder can choose one of the minimum code words (in addition to the property that the associated bin sequence must contain the bin sequence in the bin buffer as a prefix). On the decoder side, the bin decoder 22 may decode more encoders than required for the last codeword in the partial bit stream; these bin are not requested by the bin buffer selection module 18 and are rejected and ignored. Decoding of the finite set of symbols is controlled by requesting decoded source symbols; if no further source symbol is requested for the amount of data, decoding is completed.

Broadcasting and multiplexing partial bit streams [0092] Partial bit streams 12 that are formed by the PIPE encoder may be sent separately, or may be multiplexed into a single bit stream, or the code words of the partial bit streams may be interleaved in a single bit stream.

[0093] Each partial bit stream for the amount of data may be stored in one data packet. The amount of data can be any set of source symbols, such as a still image, video sequence box or frame, freeze frame slice, piece of video sequence box or frame or sound sample frame, etc.

[0094] Two or more partial bit streams for the amount of data or all partial bit streams for the amount of data may be multiplexed into one data packet. The structure of the data packet containing the multiplexed partial streams is illustrated in Fig. 5. That is, the data packet shown in Fig. 5 may be an intermediate part of the intertwined stream 132 and 234, respectively.

[0095] Data packet 300 consists of a header and one sub-compartment for the data of each partial bit stream (for the amount of data tested). The data packet header 300 includes indications for splitting the (remaining) data packet into data stream data segments 302 of the bit stream. In addition to the indications for division, the header may contain additional information. Indications for splitting a data packet can be arranged at the beginning of a data segment in units of bits or bytes or a multiple of bits or a multiple of bytes. The positions of the beginning of the data segment can be encoded as absolute values ​​in the header of the data packet, either relative to the beginning of the data packet or relative to the end of the header or relative to the beginning of the previous data packet. The positions of the beginning of the data segments may be coded differently, i.e. only the difference between the actual beginning of the data segment and the forecast of the beginning of the data segment is coded. The forecast can be obtained on the basis of already known or transmitted information, such as the overall size of the data packet, header size, number of data segments in the data packet, location of the beginning of the preceding data segment. The start position of the first data packet does not have to be coded, but derived from the size of the data packet header. On the decoder side, the transmitted indications of the sub-compartment are used to determine the beginning of the data segment. The data segments are then used as partial bit streams and the data contained in the data segments are fed to the respective bin decoders in sequential order.

[0096] There are several alternative solutions for multiplexing partial data streams 12 into a data packet. One alternative that can reduce the required auxiliary information, in particular in cases where the sizes of the partial bit streams are very similar, is shown in Fig. 6. The payload of a data packet, i.e. data packet 310 without its header 311, is segmented 312 in a certain way. For example, the payload of a data packet can be divided into segments of the same size. Then each segment is associated with a partial bit stream or with the first part of the partial bit stream 313. If the partial bit stream is larger than the associated data segment, its remaining portion 314 is in a free space at the end of the other data segments. This can be done in such a way that the remainder of the bit stream is placed in reverse order (from the end of the data segment), which limits side information. Binding the rest of the partial bit streams for data segments and, if more than one residue is added to the data segment, the start point for one or more residues must be signaled within the bit stream, for example in the data packet headers.

Variable-length code word interleaving [0097] In some applications, the above-described multiplexing of partial bit streams 12 (with respect to the number of source symbols) in one data packet may have the following advantages: on the one hand, for small data packets, the number of bits for side information that are required for partition signaling may become significant compared to actual data of partial bit streams that ultimately limit coding performance. On the other hand, multiplexing may not be suitable for applications that require low latency (e.g. for video conferencing applications). With the multiplexing described, the PIPE encoder cannot start transmitting the data packet before the partial streams are completely formed, because the starting locations of the sub-compartments are not known to date. Also, in general, the PIPE decoder must wait until it receives the beginning of the last data slice before decoding the data packet. For applications such as video conferencing systems, these delays can be added to the additional general system delay of several video images (in particular for bit rates that are close to the bit rate and for encoders / decoders that require a close time interval between two image coding / decoding images), which are key to these applications. In order to overcome these drawbacks in some applications, the PIPE encoder may be configured such that the code words that are generated by two or more bin transducers are interleaved into one bit stream. The bit stream from the interleaved codewords can be sent directly to the decoder (if a small buffer delay is omitted, see below). In a PIPE decoder, two or more bin decoders read code words directly from the bit stream in decoding order; decoding can start from the first bit received. In addition, side information is not required for multiplexing (or interleaving) partial bit streams signaling.

[0098] The basic structure of the PIPE coder interleaving is shown in Fig. 7. The bin encoders 10 do not write the codeword directly to partial bit streams, but bind to one codeword buffer 29 from which the codewords are written to stream 34 for coding. The bin encoders 10 send a request for one or more new code words to buffer 28 entries to code word buffer 29, and then send code words 30 to code word buffer 29, which are stored in reserved buffer entries. (Generally variable length) code words 31 of the code word buffer 29 are available through the codeword writing module 32, which writes the corresponding bits 33 to the generated bit stream 34. Code word buffer 29 acts as first-in-first-of-buffer; codeword entries that are reserved in advance have been previously written to the bit stream.

[0099] In a further generalization, multiple code word buffers and partial streams 12 are possible in which the number of code word buffers is less than the number of bin encoders. The bin 10 encoder reserves one or more code words in the code word buffer 29, wherein the reservation of one or more code words in the code word buffer is triggered by specific events in the connected bin 8 buffer. Code word buffer 29 may be operated such that the PIPE decoder can immediately decode bit stream 34, which corresponds to 132 in Figs. 1A and 134 in Fig. 2, respectively. The coding order in which the codewords are written to the stream is the same as the order in which the corresponding codewords are reserved in the codeword buffer. Each bin 10 encoder can reserve one code word, with a reservation triggered by some event in the connected bin buffer. Each bin 10 encoder can reserve more than one codeword, with a reservation triggered by some event in the connected bin buffer. Bin 10 encoders may reserve a different number of code words, where the number of code words that are reserved by a particular bin encoder may depend on the particular bin encoder and / or other properties of the given bin encoder / bin buffer (such as associated probabilistic measure, number of already saved bits, etc.).

[0100] The code word buffer may operate as follows. If the new bin 7 is sent to the specified bin 8 buffer and the number of bin already stored in the bin buffer is zero and there is currently no code word reserved in the buffer of the bin coder codeword that is connected to the given bin buffer, the connected bin 10 encoder sends request to the codeword buffer, as a result of which one or more codeword entries are reserved in codeword buffer 29 for a particular bin encoder. Codeword entries may have a variable number of bits; the upper limit on the number of bits in a buffer entry is usually given by the maximum code word size for the corresponding bin encoder. The next code word or subsequent code words that are produced by the bin encoder (for which the codeword entry or codeword entries have been reserved) are stored in the reserved entry or codeword buffer entries. If all reserved buffer entries in the code word buffer for a given bin encoder are filled with code words and the next bin is sent to the bin buffer that is connected to the specified bin encoder, one or more new code words are reserved in the code word buffer for the specific encoder bin, etc. Code word buffer 29 is first-in-first-of-buffer in a specific manner. Buffer entries are reserved in sequential order. The code words for which the corresponding buffer entries were previously reserved were previously written to the bit stream. The codeword recording module 32 checks the state of the codeword buffer 29, either continuously or after writing the codeword 30 to the codeword buffer 29. If the first buffer entry contains the complete codeword (i.e. the buffer entry is not reserved but contains the code word), the corresponding code word 31 and the corresponding buffer entry are removed from the code word buffer 20 and the bits of code word 33 are recorded in the bit stream. This process is repeated until the first buffer entry does not contain a codeword (i.e. it is reserved or free). At the end of the decoding process, that is, if all the source symbols of the amount of data considered have been processed, the code word buffer should be flushed. For this flushing process, the following is applied to each bin buffer / bin encoder as a first step:

If the bin buffer does not contain bin, a bin with individual or any values ​​is added until the bin sequence representing the bin sequence that is associated with the code word is obtained (as noted above, one of the preferred ways to add bin is to add bin values ​​that cause the shortest code word - or one of those - which is associated with the bin sequence, which contains bin buffer as prefix to the initial content), this codeword is written to the next buffer entry reserved for the corresponding bin encoder (and the corresponding bin buffer is flushed). If more than one buffer entry has been reserved for one or more bin encoders, the codeword buffer may still contain reserved codeword entries. In this case, these codeword entries are filled arbitrarily, but valid codewords for the respective bin encoders. Preferably, the shortest valid code word or one of the shortest valid code words (if there are many) is entered. Finally, all other code words in the code word buffer are saved in the bit stream.

[0101] Two examples regarding the status of the code word buffer are shown in Fig. 8. In example (a) it contains the code buffer entries 2 which are filled with the code word and 5 reserved positions. In addition, the next free buffer entry is marked. The first entry is filled with a code word (i.e. bin 2 has just written the code word for the previously reserved entry). In the next step, this codeword will be removed from the codeword buffer and written to the stream. Then, the first reserved codeword for bin 3 encoder has the first buffer entry, but this entry cannot be removed from the codeword buffer because it is reserved, but no codeword has been written to this entry. In example (b) the code word buffer contains 3 entries that are filled with the code word and 4 reserved items. The first entry is marked as reserved, and thus the codeword writing module cannot write the codeword to the bit stream. Although 3 codewords are contained in the codeword buffer, the codeword storage module must wait for the codeword to be saved in the first reserved buffer entry for bin 3 encoder. Note that the code words must be written in the order in which they were reserved to reverse this process in the decoder (see below).

[0102] The basic structure of a PIPE decoder with code interleaving is shown in Fig. 9. Bin 10 decoders do not read the code word directly from separate partial bit streams, but are connected to a bit buffer 38 from which code words 37 are read in coding order . It should be noted that the bit buffer 38 is not necessarily required because the code words can be read directly from the bit stream. The bit buffer 38 is mainly included in the illustration for clearly distinct various aspects of the processing chain. Bits 39 of bit stream 40 from the interleaved code words, which thus corresponds to bit stream 234 in Fig. 2, sequentially placed in bit buffer 38, which is the first-in-first-with buffer. If a given bin decoder 22 receives requests for one or more bin sequences 35, the bin decoder 22 reads one or more code words 37 from bit buffer 38 via bit request 36. The PIPE decoder can immediately decode source symbols. Note that the PIPE encoder (as described above) must ensure by proper buffer operation that the codewords are written in the same order as the bit stream in which they are required by the bin decoders. In the PIPE decoder, the entire decoding process is triggered by requests for source symbols. Parameters like the number of code words that are reserved in the encoder by the given bin encoder and the number of code words that are read by the corresponding bin decoder must be the same.

[0103] In a further generalization, multiple codeword buffers and partial bit streams are possible, where the number of bit buffers is less than the number of bin decoders. The bin decoder 22 reads one or more code words from the 38 bit buffer at an instant of time in which the reading of one or more code words from the bit buffer is triggered by specific events in the connected bin 20 buffer. The decoder may be used in a way in which one or more code words are read when bin 19 request is sent to the specified bin 20 and the bin buffer does not contain any bin. However, it is also possible to cause the code words of other events to be read, for example when the number of bin in the bin buffer is below a predetermined threshold. Each bin 22 decoder can read one code word, and the reading is triggered by some events in the connected bin buffer. Alternatively, each bin decoder 22 can read more than one codeword, with the reading being triggered by some event in the connected bin buffer. Bin 22 decoders can be read with a different number of code words, where the number of code words that are read by a particular bin decoder may depend on the particular bin decoder and / or other properties of the given bin buffer / decoder (e.g. related probability measure, number already read bits, etc.).

[0104] The reading of code words from the bit buffer may be handled as follows. If a new bin 19 request is sent from the bin buffer selection module 18 to the specified bin buffer 20 and the number of bin in the bin buffer is zero, the connected bin decoder 22 reads one or more code words 37 from bit buffer 38, by requesting 36 bit to bit buffer 38. The bin 22 decoder converts code words 37 into bin 21 sequences and writes those bin sequences to the connected bin buffer 20. In the final reply to bin 19, the first bin entered will be removed from bin 20 and sent to the bin 18 selection module. In response to subsequent bin requests, the remaining bin in the bin buffer is removed as long as the bin buffer is empty. An additional bin request runs the bin decoder to read one or more new code words from the bit buffer, etc. The bit buffer 38 is a first-in-first-buffer of a fixed size and is constantly filled with bits 39 from the bit stream 40. To ensure that code words are written to the bit stream in the same way as required in the decoding process, the codeword buffer in the encoder can be handled as described above.

[0105] In this way, each of the plurality of entropy decoders may be a variable-length decoder configured to map fixed-length codewords to a variable-length symbol sequence, and the codeword input, such as at codeword buffer output 43, is intended to receiving a single stream of interleaved code words. Many entropy decoders 22 can be configured to retrieve codewords with the codeword input in sequential order, depending on the order in which the symbols of the symbol sequence are to be played as picked by the selection module 18 of the plural entropy decoders to give a new symbol sequence to be mapped from a new code word in the corresponding entropy decoders.

Variable-length code interleaving with low latency limitation [0106] The interleaving codeword for PIPE encoding described does not require any partitioning information to be sent as side information. And because the code words are entwined in the bit stream, the delay is generally small. However, there is no guarantee that the specific delay limitation is being observed (e.g. specified by the maximum number of bits that are stored in the code word buffer). In addition, the required buffer size for the codeword buffer can theoretically become very large. Considering the example in Fig. 8 (b), it may be possible that no further bins are sent to the 3 bin buffer and as a result the 3 bin encoder will not send any new code word to the code word buffer until the processing at the end of the data packet is applied . Then, all code words for encoders 1 and 2 bin would have to wait until the end of the data packet before being rewritten to the bit stream. This disadvantage can be circumvented by adding another mechanism to the PIPE encoding process (and also to the PIPE decoding process, as described later). The basic concept of this additional mechanism is that if the delay or upper delay measure (see below) exceeds the specified threshold, the first reserved buffer entry is filled by processing the appropriate bin buffer (using a similar mechanism at the end of the data packet).

By this mechanism, the number of pending buffer entries is limited until the associated delay measure is less than the rounded threshold. On the decoder side, the bins that were introduced on the encoder side to comply with the delay constraint must be rejected. In principle, the same mechanism as for the encoder page can be used to reject bins. In the following, two options for such delay control are described.

[0107] In one possibility, the measure for delay (or upper limit of delay) is the number of active entries in the code word buffer, in which the number of active entries in the buffer is the number of entries in the reserved buffer plus the number of buffer entries that contain the code words. Note that the first buffer entry is always a restricted buffer entry or free buffer entry, because if the first buffer entry contains a code word, the code words are written to the stream. If, for example, the maximum allowed buffer delay is (as specified by the notification) D bits and the maximum code word size for all bin encoders is L, the lower limit for the maximum number of code words that can be contained in the code word buffer, without violating delay limit can be calculated by N = D / L. Measurement delay D in bits is not required by the system, but the maximum number of N code words must be known to both the encoder and the decoder. The maximum number of N buffer entries can be set by the application. Alternatively, the maximum number of buffer input N and code words in buffer N may be signaled within the bit stream, e.g., in the header of data packets (or segment header) or a set of parameters that are contained in the stream. If the 10 bin encoder sends a request for the reservation of one or more new codeword buffer entries 29, then the process is performed before a new entry in the codebase is reserved (i.e. it is executed repeatedly if multiple coding buffer entries are reserved by one request): if the number of entries in the currently active buffer and 1 (taking into account the buffer position that will be reserved next) is greater than the maximum number of codeword entries in the buffer N, the first buffer position (which is reserved) is processed as described later up to obtain the number of entries in the currently active buffer plus 1 is less than or equal to the maximum number of entries in the codeword buffer N. The processing of a reserved buffer entry is similar to the processing at the end of a data packet: the 10 bin encoder that is reserved for the corresponding input of the first buffer is emptied by adding bins with individual or arbitrary values ​​for the connected bin buffer 8 to the resulting bin sequence represents the bin sequence that is associated with a code word. The code words are then written to the reserved buffer input and finally added to the bit stream (when emptying the bin and deleting the previously reserved). As mentioned above, one of the preferred ways to add bins to the bin buffer is to add those bins that produce the shortest possible codeword. In the decoder, a similar process is performed by discarding bins that have been added to respect the delay constraint. Therefore, the decoder maintains the C counter counting the code words that were read from the bit buffer (this counter can be maintained in the bit buffer). This C counter is initialized (e.g., zero) at the beginning of the data packet decoding and is incremented by one after the code word being read. In addition, each bin 22 decoder includes a Cx counter, which stores the value of the C code counter, which was read by the respective bin 22 decoder before the last codeword, e.g. when a given bin 22 decoder reads new coded words, its Cx counter is C, as the first stage and then the coded words are read from the transmission buffer. When the request for bin 19 is sent to a given bin 20 buffer and the difference (C-Cx) between the general code word counter C and the counter Cx connected to the 22 bin decoder is greater than the maximum number of the code word of entries in buffer N, all bins that are currently bin 20 stored in a given buffer are rejected and ignored. In addition, the additional decoding step is handled as described above. If the bin 20 buffer to which the request for bin 19 is sent empty (either because all bins have already been removed or because the low delay mechanism did not reject all the bins in the first stage after the bin application was received) the connected bin decoder 22 reads one or more new code words from a 38-bit buffer, etc.

[0108] The measure for delay (or upper limit of delay) may be the sum of the codeword with the maximum length of active buffer entries in the codeword buffer, wherein the length of the codeword for a given buffer input depends on the decoded bin that is associated with this buffer entry . As an illustration, the maximum length of the code words for the buffer positions are shown in the examples in 6. Note again that the first buffer entry is always a reserved buffer entry or free buffer entry, because if the first buffer entry contains a code word, the code word is written to the bit stream. Let the maximum allowed buffer delay (as specified by the application) be D bits. This maximum buffer delay D must be known to both the encoder and the decoder. The maximum buffer D delay can be set by the application. The maximum buffer D delay can be signaled within the bit stream, for example in the header of the data packets (or segment header) or the set of parameters that are contained in the bit stream. This can be signaled in units of bits or bytes, or multiple bits or a multiple of bytes. If bin 10 encoder requests to reserve one or more new buffer entries for code word buffer 29, then the process is performed before a new entry in the code buffer is reserved (i.e. it is executed multiple times if multiple code word buffer entries are reserved by one request ).

[0109] If the sum of the maximum length codeword for all currently active buffer entries plus the maximum length codeword for buffer entries that can be reserved is greater than the maximum buffer delay D, the first buffer position (which is reserved) is flushed behind by the method described above, until the sum of the maximum codeword for all active buffer entries plus the maximum codeword codeword length that can be reserved is less than or equal to the maximum buffer delay D. As an example, consider the example shown in Fig. 8 (b) . The sum of the maximum codeword length for all currently active buffer entries is 29. Suppose the maximum buffer delay D is 32. If the next buffer entry is reserved by bin 2 encoder, for which the maximum codeword length is 3, the first buffer entry is not flushed because 29 + 3 is not greater than 32. However, if bin 1 is reserved next to the buffer entry , for which the code word with a maximum length is 7, the first buffer entry is flushed, because 29 + 7 is greater than 32. Flushing of the reserved buffer entry is performed as described above (adding a bin with individual or any values ​​in the appropriate bin buffer).

[0110] On the decoder side, a similar process is performed by discarding bins that have been added to respect the delay constraint. Therefore, the decoder maintains the C counter, which counts the maximum code word length for code words that have been read from the bit buffer (this counter can be maintained in the bit buffer). Note that the maximum length of the codeword that are associated with different bin decoders may be different. The C counter is initialized (e.g., zero) at the beginning of the data packet decoding and increases after the code word is read. This counter is not increased by the actual length of the code words read, but by its maximum length. That is, if the codeword being read is read by a specific bin decoder and the maximum codeword length that is associated with the codeword table used by a particular bin decoder is Lx (another bin decoder may be associated with a different maximum codeword length), counter C is increased by Lx. In addition to the general C counter, each bin 22 decoder includes a Cx counter that stores the value of the C code word counter before the last codeword reads by the respective bin decoder 22. That is, when the given bin 22 decoder loads the new code words, its opposite Cx is equal to C , as a first step, and then the code words are read from the transmission buffer. When the request for bin 19 is sent to the given bin 20 buffer and the difference (C - Cx) between the general counter C and the counter Cx of the connected bin 22 decoder is greater than the maximum time of buffer D, all the bin that was currently stored in the given bin 20 are removed and ignored. In addition to this additional step, decoding is handled as described above. If the bin 20 buffer to which the bin 19 request is sent is empty (either because all bins have already been removed or because the low latency mechanism rejected all the bins in the first stage after the bin request that was received) the connected bin decoder 22 reads one or more new code words from bit buffer 38, etc.

[0111] In this way, multiple entropy decoders 22 and selection module 18 can be configured to periodically discard symbol sequence suffixes so that they do not participate in the creation of symbol sequences that have been reconstructed 29. Intermittent ejection can be performed in events where the number of code words has been taken from the codeword entry by multiple entropy decoders between two consecutive downloads of the codewords with the corresponding entropy decoder since the codeword input meets the predetermined criterion. Many entropy encoders, and the codeword buffer, in turn, can be configured to interrupt extending currently transmitted, but not yet mapped symbols so that important symbol sequences with negligible symbols are currently transmitted, but not yet mapped symbols as prefixes, thus mapping extended symbol word sequences for code words to thereby enter the obtained code words into reserved code word entries and flush the code word entries. Stretching with breaks, entering and rinsing can take place at events where the number of codeword entries reserved plus the number of codeword entries after codeword entries meet a predetermined criterion. The specified criteria may take into account the maximum lengths of code words of many encoder / decoder pairs.

[0112] For some architecture, the codeword interleaving method described above may cause disadvantages with respect to the complexity of decoding. As shown in Fig. 9, all bin 22 decoders read code words (generally variable-length code words) from one bit buffer 38. Reading code words cannot be performed in parallel because the code word must be read in the correct order. This means that a given bin decoder must wait for other bin decoders to finish reading the code words. And when the complexity of reading variable-length code words is significant relative to the rest (partially in parallel) of the decoding process, access to variable-length code words can be the bottleneck of the entire decoding process. There are several variants that can be used to reduce the complexity of access from a single bit buffer, some of which will be described later. There, for example, there is one code word set (including, for example, excess free prefix) and a code word set that is used for each bin 22 decoder that is a subset of one code word set. Note that different bin 22 decoders can use different subsets of a single code word set. Even if the code word sets that are used by some bin 22 decoders are the same, their relationship to bin sequences is different for different bin 22 decoders. The same code word set can be used for all bin 22 decoders. If we have a single code set that contains a code word set for all decoders like bin subsets, code word parsing can be done outside of the bin decoders, which can reduce the complexity of the codeword access. The PIPE encoding process is not changed in relation to the process described above. The modified PIPE decoding process is shown in Fig. 10. One code reader is given with bits 46 from bit stream 40 and analyzes - in general, variable length - code words. The read code words 44 are introduced into the code word buffer 43, which is the first-in-first-with buffer. The bin decoder 22 sends a request via one or more code words 41 to the code word buffer 43, and in response to the request, wherein one or more code words are removed from the code word buffer (in the correct order) and then sent to the appropriate bin decoder 22. Note that in this case a potentially complex parsing code word can be performed in the background process and you do not have to wait for the bin decoder. The access of bin decoders of already analyzed code words, potentially complex code words to analysis is no more part of the total buffer request. Instead of the already analyzed code words, they are sent to bin decoders, which can also be implemented in such a way that only code word pointers are sent to bin decoders.

Interleaving a fixed-length bit sequence [0113] Another way to reduce the complexity of a PIPE decoder can be achieved when bin 22 decoders do not read variable-length code words from the global bit buffer 38, but always read the constant-length sequence from the global bit buffer 38 and add these fixed-bit sequences to the local bit buffer, where each bin decoder 22 is connected to a separate local bit buffer. These variable-length codewords are then read from the local bit buffer. Hence, parsing of variable-length code words can be performed in parallel, only access to fixed-length sequences must be synchronized, and access to such fixed-length sequences is usually very fast, so that the overall complexity of decoding can be reduced for some architecture. The set number of bins that are sent to a given local bit buffer may vary for different local bit buffers and may also change over time, depending on specific parameters such as events in the bin decoder buffer, bin buffer or bit buffer. However, the number of bits that are read in this in particular does not depend on the actual bits that are read in particular access, which is an important difference from reading the variable length code words. Reading a fixed bit length sequence is triggered by certain events in the bin decoders bin buffers or local bit buffers. As an example, you can request to read a new bit sequence when the number of bits that are present in the combined bit buffer falls below a predetermined threshold whose different threshold values ​​can be used for different bit buffers. In the encoder, it must be ensured that the sequences of the fixed bin length are placed in the same order in the bit stream in which they are read from the bit stream in the decoder. It is also possible to combine this interlacing of fixed-length sequences with low-delay control and similar to those explained above. Hereinafter, a method of interleaving a sequence of fixed bit lengths is described.

[0114] Fig. 11 is an illustration of the PIPE encoder structure that interleaves constant-bit sequences for two or more bin encoders. Unlike Fig. 7, bin encoders 10 are not combined into a single code word buffer. Instead, each bin 10 encoder is connected to a separate bit buffer 48 that stores bits for the corresponding partial bit stream. All 48 bit buffers are connected to the global bit buffer 51. The global bit buffer 51 is connected to the bit write module 53, which removes bits 52 in coding / decoding order from the global bit buffer and writes the deleted bits 54 to the bit stream 55. For certain events in a given bit buffer 48 or a connected bin encoder 10 or buffer bin 8, bit buffer 48 sends a request 49 to the global bit buffer 51, in which a number of bits are reserved in the global bit buffer 51. Fixed sequence bit reservation requests 49 are processed in order. Global bit buffer 51 is a first-in-first-buffer in a particular manner; bits that are reserved earlier have been previously written to the bit stream. It should be noted, however, that different bit buffers 48 may reserve a different number of bits that may change over time based on already coded symbols; but the number of bits that are reserved by the request is known at the time the request was sent to the global bit buffer.

[0115] In particular, the bit buffers 48 and the global bit buffer 51 are controlled as described below. The number of bits that is reserved in the specific 48 bit buffer is designated as Nx. This number of Nx bits may be different for different 48 bit buffers and may also change over time. The number of Nx bits that are reserved for a given 48 bit buffer can be set in time. The reservation of a specific number of Nx bits 49 is started based on the number of Mx bits in the bit buffer 48, the number of Nx bits for reservation requests, and the associated maximum length Lx code word. Please note that each bin 10 encoder can be associated with a different length of the Lx codeword. If bin 7 is sent to the specified bin 8 buffer, and especially the bin 8 buffer is empty, and no more than one sequence of Nx bits is reserved in the global bit buffer for the 48 bit buffer that is connected to the given bin buffer (using an encoder bin), and the difference Nx - Mx between the number of Nx bits that were reserved by the reservation request in bit buffer 48, which is connected (through the bin encoder) with the given bin 8, and the number of Mx bits, which are currently available in this 48 bit buffer is less than the maximum length of the Lx codeword that is associated with the corresponding bin encoder 10, the combined bit buffer 49 sends a request 49 for the reservation of Nx bits to the global bit buffer 51. The global bit buffer 51 reserves Nx bits for the given 48 bit buffer and increases its indicator until the next reservation. After this, the Nx bits are reserved in the global bit buffer, and bin 7 is stored in bin 8. If the single bin no longer represents the bin sequence that is associated with the code word, the bin encoder 10 removes the bin from the bin 8 buffer and writes the corresponding code word 47 to the connected 48 bit buffer. Otherwise (this single bin does not represent the bin sequence that is associated with the code word), in addition bin 7 has been accepted by the given bin buffer 8 until bin 8 contains the bin sequence that is associated with the code word. In this case, the combined bin encoder 10 deletes the sequence of bin 9 from the bin 8 buffer and writes the corresponding code word 47 to the connected 48 bit buffer. If the obtained number of Mx bits in the bit buffer 48 is greater than or equal to the number of reserved bits Nx, Nx bits, which were first written to the 48 bit buffer are entered into the previously reserved space in the global bit buffer 51. For the next bin 7, which is sent to the given bin 8 buffer, the same process as specified above is carried out; that is, it is marked first whether the new number of Nx bits must be reserved in the global bit buffer (if Nx - Mx is less than Lx), and then bin is placed in bin 8, etc. The bit writing module saves the bit sequences fixed length of the global bit buffer in the order in which they were reserved. If the first fixed-length input in the global bit buffer 51 contains a sequence of bits of a fixed length that have been correctly inserted in the global bit buffer (that is, not only reserved), the bit recording module 53 deletes the bits for this bit sequence 52 from the global bit buffer 51 and write bits 54 to the bit stream. This process is repeated until the first fixed-length entry in the global bit buffer represents a reserved or free entry. If the first fixed-length entry in the global bit buffer represents a reserved entry, the bit-writing module 53 waits until this entry is filled with real bits before it writes the next bits 54 to bit stream 55.

[0116] At the end of the data packet, the bin buffers are washed as described above. In addition, bit buffers must be flushed by adding bits with special or any value until all buffer entries reserved in the global bit buffer are filled and saved in the bit stream.

[0117] In Fig. 12, two examples of possible state of global bit buffer 51 are shown. For example: (a) illustrates a case in which different bit buffers / bin encoders reserved different numbers of bits. The global bit buffer contains 3 items from the actually written fixed-length bit sequence and 4 entries from the reserved-fixed bit sequence. The first fixed-length entry already contains the actual bits (which must simply be inserted by the bit buffer / bin 2 encoder); this entry (i.e. corresponding to 8 bits) can be deleted and written to the stream. The next entry reserves 10 bits for bin 3 encoder, but the actual bits have not yet been connected. This entry cannot be written to the bit stream; wait until the actual bits are inserted. In the second case (b), all bit buffers / bin encoders reserve the same number of bits (8 bits). The global bit buffer contains 4 reservations for 8 bit sequences and 3 actually written 8 bit sequences. The first entry contains a reservation for 8 bits for the bin encoder 3. Before any new bits can be written to the bit stream, the bit entry module must wait a bit until the bit buffer / bin 3 encoder writes the actual values ​​of 8 bits on the reserved entry.

[0118] Fig. 13 shows an illustration of a PIPE decoder structure that interleaves constant-bit length sequences. Unlike Fig. 9, bin 22 decoders are not combined into a single bit buffer. Instead, each bin decoder 22 is connected to a separate bit 58 buffer in which the bits from the respective partial bit stream are stored. All 58 bit buffers are connected to global bit buffer 61. Bits 62 from bit stream 63 is added to the global bit buffer 61. On certain events in a given bit buffer 58 and a connected bin decoder 22 or bin 20 buffer, bit buffer 58 sends a request 59 to the global bit buffer 61, in which the fixed length sequence 60 the bit bit is removed from the global bit buffer 61 and placed in particular the bit buffer 58. Requests for a fixed bit length sequence 59 are processed sequentially. Global Bit Buffer 61 is the first-in-first-of-buffer; bits that are previously inserted into the global bit buffer are previously removed. It should be noted that different 58-bit buffers may request different numbers of bits that may change over time based on already decoded symbols; but the number of bits that are required by the request is known at the time the request was sent to the global bit buffer. It should be noted that global bit buffer 61 is not necessarily required because the code words can be read directly from the bit stream. Global bit buffer 61 is mainly included in the illustration to clearly unravel different aspects of the processing chain. [0119] Bit buffers 58 and global bit buffer 61 may be operated as described below. The number of bits that is requested and read by the specified buffer bit 58 is designated as Nx and is equal to the number of bits that is written to the global bit buffer by the corresponding bit buffer in the encoder. This number of Nx bits may be different for different bit buffers 58 and may also change over time. Preferably, the number of Nx bits that is requested and read by the buffer of the specified bit 58 may be constant over time. The reading of the specified number of Nx bits 60 is triggered based on the number of Mx bits in bit buffer 58 and the associated code word with a maximum length of Lx. It should be noted that each bin 22 decoder can be associated with a different length of the LX codeword. If the bin 19 request is sent to the given bin 20 buffer, and especially the bin 20 buffer is empty, and the number of Mx bits in the bit buffer 58 that is connected (via the bin decoder) to the given bin 20 buffer is less than the maximum length of the Lx code word , which is associated with the respective bin decoder 22, connected buffer bit 58 sends a request 59 for a new sequence of Nx bits of global buffer bit 61. In response to this request, the first Nx bits are removed from the global bit buffer 61 and this sequence of Nx bits 60 is sent to buffer 58 from which the bit request was sent. Finally, this Nx bit sequence is added to the corresponding bit buffer 58. Then the next code word 57 is read from this bit buffer and the connected bin decoder 22 inserts the associated bin 21 sequences into the connected bin buffer 20. In the final reply in the original bin 19 request, the first bin is removed from the bin 20 buffer and this decoded bin 25 is sent to the bin buffer selection module 18. When subsequent bin 19 requests are sent to the given bin buffer 20 and the bin buffer is not empty, the next bit is removed from bin 20. If the bin buffer is empty, but the number of Mx bits in the connected bit buffer 58 is greater than or equal to the maximum length of the associated code word Lx, the next code word is read from the bit buffer, and the new bin sequence is placed in the bin buffer from which the first bit is removed and sent to the bin buffer selection module. If the bin buffer is empty and the number of Mx bits on the combined bit buffer 58 is less than the associated length of the Lx code word, the next Nx sequence, the bits are read from the global bit buffer 61 and entered into the connected local bit buffer 58, the next code word is read from the transmission buffer, the new bin sequence is placed in the bin buffer, and the first bin sequence is deleted and sent to the bin buffer selection module. This process is repeated until all source symbols are decoded.

[0120] At the end of the data packet, more bin and / or bits than required to decode the desired source symbol may be placed in the bin buffer and / or bit buffer. The remaining bin in the bin buffer and the remaining bits in the bit buffer are discarded and ignored.

Fixed-length bit interleaving with low latency limitation [0121] The PIPE encoder and decoder from the fixed-length bit sequence interleaving can be combined with an encoder buffer delay adjustment scheme as described above. The concept of PIPE coding is the same as for delay control as described above. If the delay-related measure or the upper delay limit (see below) exceeds the specified threshold value, the first reserved buffer entry is filled by flushing with the appropriate bin buffer (using a similar mechanism at the end of the data packet) and potentially writing additional bits to fill all reserved bits fixed length buffer entry. Thanks to this mechanism, the number of pending buffer entries is shorter because the associated delay measure is less than the specified threshold. In the decoder, when bin and bits are introduced in the encoder to fulfill the delay limit that should be removed. For this rejection of bins and bits basically the same mechanism as on the encoder side can be used.

[0122] The measure for delay (or upper limit of delay) may be the number of bits in active buffer entries in the global bit buffer, where the number of active buffer entries means the number of reserved entries in the fixed-length buffer plus the number of fixed-length buffer entries, which already contain saved bits. Note that the first buffer entry is always a reserved fixed-length buffer entry or pre-free buffer entry, because if the first buffer entry contains written bits, these bits are written to the stream. Let the maximum allowed buffer delay (as specified by use) be D bits. This maximum buffer delay D must be known to both the encoder and the decoder. The maximum buffer D delay can be set by the application. The maximum buffer delay D can be signaled within the bit stream, for example in the header of the data packets (or segment header) or the set of parameters that are contained in the stream. This can be signaled in units of bits or bytes, or multiple bits or a multiple of bytes. If bin 10 encoder sends a reservation request for a new fixed-length bit sequence to global bit buffer 51, then the process is performed before a new fixed-length buffer entry is reserved.

[0123] If the number of bits in the active buffer entries in the global bit buffer plus the number of bits that can be reserved in the current reservation request is greater than the maximum buffer delay D, the first buffer position (which is reserved) is flushed as described below until the number of bits in the active buffer position in the global bit buffer plus the number of bits, which will be reserved in the current reservation request is less than or equal to the maximum buffer delay D. Flushing the reserved buffer input of a fixed length is similar to flushing at the end of a data packet: the bin 10 encoder that is connected to the bit 48 buffer, which has the corresponding first buffer entry reserved, is flushed by adding a bin with a special or any of the values ​​for the connected buffer bin 8, until the obtained bin sequence represents the bin sequence that is associated with the code word, wherein the code word is then placed in the corresponding bit buffer 48. As mentioned above, one of the preferred ways to add bin to the bin buffer is to add those bin that produce the shortest possible code words. If after writing the codeword to the connected bit buffer and potential input of the fixed bit length sequence to the global bit buffer, there are still bits in the bit buffer (i.e. the codeword does not completely fill the reserved sequence of bits with a fixed length), subsequent bits with special or any values ​​are added to the bit buffer until all bits are removed from the bit buffer and written to the reserved buffer input. Finally, at the end of this method, the completed buffer entry (first fixed-length position in the global bit buffer) is removed from the global bit buffer and is saved in the bit stream.

[0124] At the decoder side, a similar process is performed by discarding bins and bits that have been added to respect the delay limit. Thus, the decoder maintains a C counter that counts the bits that were read from the global bit buffer (this counter can be maintained in the global bit buffer). The C counter is initialized (e.g., zero) at the beginning of the data packet decoding and increases after reading the fixed length sequence. If the fixed bit sequence Nx bits is read from the global bit buffer 61, the C counter is increased by Nx. In addition to the entire C counter, each bit buffer 58 includes a Cx counter, which stores the value of the C bit counter before the last fixed-length bit sequence read in the corresponding bit buffer 58. When bit buffer data 58 reads a new fixed-length sequence, its Cx counter is C in the first step, and then the fixed-length bit sequence is read from global bit buffer 61. When bin 19 request is sent to the specified bin 20 buffer and the difference (C - Cx) between the general counter C and the counter Cx of the connected bit buffer 58 is greater than the maximum delay of buffer D, all bin that is currently stored in the given buffer bin 20 and all bits stored in the combined bits buffer 58 are removed and ignored. In addition to this additional step, decoding is handled as described above. If the bin 20 buffer to which the bin 19 request is sent is empty (either because all bin has already been removed or because the low latency mechanism did not reject all bin in the first step after receiving the bin request), the connected bin decoder 22 tries to read the new word code from the connected bit buffer 58. If the number of bits in bit buffer 58 is less than the maximum code word length, the new fixed-bit sequence is read from the global bit buffer 61, before reading the code word, etc.

[0125] Figs. 7 to 13 are associated with the possibility of obtaining a path of intertwined bit streams between a PIPE encoder 104 on the one hand and a PIPE 202 decoder on the other hand. As described above with reference to Figs. 1 and 2, the entropy coding and decoding device may be connected to each other via two separate channels, one of which carries the VLC 112 bit stream and the other which the PIPE encoded bit stream encoded transmits. However, it is also possible to interleave even both VLC bit streams 112 and PIPE encoded bit streams 118, and such possibilities will be described later with reference to Figs. 20 to 24. However, before that, a mathematical background is provided with respect to the PIPE coding scheme as well as detailed information on how to optimally split the probability interval with the assigned results from individual partial ranges of individual entropy coders and entropy decoders respectively.

[0126] As already mentioned, in PIPE encoding the event space of the input sequence of discrete symbols is mapped to a small set of binary probability intervals. Probability models for source symbols can be fixed or adaptive, while entropy coding using probability intervals remains constant and is separated from the modeling stage. Each of the probability ranges can be coded using a very simple entropy code that has a level of complexity in Huffman codes. The excess speed of the entropy code (PIPE) probability interval is similar to that of pure coding arithmetic.

[0127] Entropy coding can in principle be considered the most typical of the lossless compression methods. Lossless compression is meant to represent discrete data with fewer bits than needed for the original data representation, but without losing information. Discontinuous data may be given in the form of text, graphics, images, video, audio, speech, facsimile, medical data, meteorological data, financial data, or any other form of digital data. In many coding applications, the original source data is first mapped to so-called coding symbols and these coding symbols are then entropy coded. Mapping to coding symbols may include quantization, in which case the overall coding scheme is lossy. The encoding symbol s can take any value in M ​​-ary (M> 2) alphabet A = {0, am -1}. For the purpose of encoding the symbol s, the alphabet is associated with the approximate probability mass function (pmf) {ps (a0), ..., ps (aM -1)}, and all relationships between symbol encoding that are not recognized in this PMF are overlooked. For these abstract settings, entropy

A / -1 ^H, = "Σα («;) 10g2P, («,) (B¹) / = 0 is the largest lower limit for the expected length of the codeword in bits per symbol, for coding symbols s, which can be achieved by entropy coding techniques. For decades, Huffman coding and arithmetic coding have dominated practical entropy coding. They are well-known examples of practical codes that allow approximation of the entropy limit (in a sense).

[0128] For a fixed probability distribution, Huffman codes are relatively easy to construct. The most attractive feature of Huffman codes is that their implementation can be effectively implemented by using a variable length code table (VLC). However, when we are dealing with source statistical data that is variable over time, i.e. changes in the probability of symbols, adjusting the Huffman code and its respective VLC tables is very demanding, both in terms of algorithmic complexity as well as in terms of implementation costs. In addition, if you have a dominant alphabet value with ps (ai)> 0.5, the redundancy of the appropriate Huffman code (without using the alphabet extension, such as the length of the encoding run) can be quite significant. Another disadvantage of Huffman codes is that when dealing with higher order probability modeling, multiple VLC table collections may be required.

[0129] Arithmetic coding, on the other hand, being much more complex than VLC, has the advantage of being more consistent and appropriate in overcoming adaptive and higher order probability modeling, as well as the very probability distribution curve s. In fact, this feature basically results from the fact that arithmetic coding provides a mechanism, at least conceptually, for mapping any probability estimation value in a more or less direct way to part of the received codeword. Being equipped with such an interface, arithmetic coding allows a clean separation of probability modeling and probability estimation tasks, on the one hand, and real entropy coding, i.e. mapping symbols to code words from the other side.

[0130] Unlike the conventional entropy coding schemes just discussed, PIPE coding uses the probability of sub-compartment division, the mathematical background of which is described in more detail below.

[0131] The sequence of encoding symbols {s0, ..., sN -1} should be considered. Each symbol is taken from the se Ai alphabet. Alphabets A “Go,^and\> · · ·} Contain two or more letters, each of which is associated with an F · '·' F · probability estimation¹· Probability estimates

P (flf *).

are known to the encoder and decoder and can be fixed or variable. It is assumed that variable probabilities are estimated simultaneously in the encoder and the decoder. Ai alphabets can be either identical to a symbol sequence or different types of symbols are associated with different alphabets. In the latter case, the decoder is assumed to know the alphabet of each symbol in the sequence. This assumption is justified because the practical descriptions of the source codec contain a syntax that predicts the order of the symbols and their alphabets.

[0132] The symbol sequence {s0, ..., sN -1} is converted into a sequence of binary symbols, which are also called bin. For each si symbol, binarization

<img file="PL2768145T3_D0001.tif" />

and.

represents the bijective mapping of alphabet letters to ordered bin sets ^m"γ¹

'' Binarization mapping can be different for different Si symbols or symbol categories. Each bin sequence^and for a given symbol Si consists of one or more bin ^: 'In the decoder, a, ę = f ​​ν'¹ and b ') the si symbols can be reproduced by inverse mapping the given bin b sequence^and. As a result of binarization, the sequence bin {b0, ..., bB -1} is obtained, which represents the sequence of source symbols {s0, ..., sN -1}.

[0133] All bin bj are associated with the same binary alphabet B = {0,1}, but the corresponding binary pmf-y '' z / · '·' "> are usually different. Binary pmf ^l'^:: '*' 'can be described by & LPB with a less likely "bin (LPB) value and its probability (z, Ρ ^ ΡΒΪ, ,,

0.5). This binary description of probability can be directly derived from estimates^pprobabilities for symbol alphabets considering binarization mapping 'It is also possible (and often recommended) to directly estimate' '^r ' ~' ⁼for both encoder and decoder at the same time. Therefore, bin can be associated with a probability model (which is also referred to as context) based on syntax and previously encoded symbols or bin. And for each probability model, a description of the probability can be determined based on the values ​​of those bin that are encoded in the probability model. An example of such binary probability modeling is described with reference to CABAC H.264.

[0134] Because binary entropy function

H (p) = —p log₂(p) - (1 - p)) stallion₂(l - p) (B3) is symmetrical around p = 0.5 the same binary encoder can be used to encode all bins that are associated with the same LPB probability, regardless of the value of b> ipp. Therefore, the sequence bin {bo, ..., bB -1} is transformed into the sequence encoding rt and b^e b '}, in For each bin bj, the corresponding bijective mapping is specified by bin through

<img file="PL2768145T3_D0002.tif" />

where φ is the exclusive element or operator. On the decoder side, bin bj can

Io? ,, bi,_Dabout _L _ · 'Encoding and corresponding LPB value by,. b = (Y^j} - \ b^c>\ = b^c®b reverse mapping

J = 0. "" 'Encoding bin' specifies the value

<img file="PL2768145T3_D0003.tif" />

<img file="PL2768145T3_D0004.tif" />

<img file="PL2768145T3_D0005.tif" />

the corresponding bin bj is equal to the LPB value and the coding bin specifies that the value of the corresponding bin bj is equal to the more likely value<img file="PL2768145T3_D0006.tif" />bin (MPB).

[0135] Order of coding bins<img file="PL2768145T3_D0007.tif" />uniquely represents the source symbol sequence {s0, ..., sN -1}, and the corresponding probability estimates that can be used for entropy coding are fully described by probabilities

<img file="PL2768145T3_D0008.tif" />

LPB. Hence, only the probabilities in the half-open gap (0.0.5] should be considered when designing the binary entropy coder for coding bin<img file="PL2768145T3_D0009.tif" /> [0136] For real binary entropy coding, the coding bin sequence

<img file="PL2768145T3_D0010.tif" />

is projected onto a small number of probability intervals Ik. Range ińrb.ra mn Cl I DD andorb IZ A * l] probability (0.0.5] LPB is divided into K intervals (B5) [0137] The set of K breaks is characterized by K -1 boundaries pk with kk = 1, ... , K -1. Without loss of generality, we assume pk &lt;pk +1 for k = 0, ..., K. The external boundaries of the range are constant and given by p0 = 0 and pK = 0.5 A. A simple non-adaptive binary entropy encoder is intended for b^c , each interval Ik. All coding bin¹ with associated probabilities LPB piLPB I are assigned to the interval Ik and coded with the appropriate constant entropy coder.

[0138] In the following description, all bin are coding bin and all probabilities p are LPB probabilities.

[0139] To investigate the effect of probability interval discretion on coding efficiency, we assume that we can design an optimal entropy encoder for a set probability that reaches the entropy limits. Each probability range Ik = (pk, pK + 1] is associated with a representative probability^Ξ · 'And the corresponding optimal entropy encoder must reach the entropy limit for this representative probability. In this assumption, the bin coding rate with a probability p using an optimal entropy coder for a peak interval representative is given for

R (p, P,_k ) = - p \ 0Zi (p,_k) - (1 - p) log₂(l - /? ,,) ϊ + ίρ-ρ, ^ Η '^ ρ,') ((36) where H (p) is the binary value of entropy function 3 and

<img file="PL2768145T3_D0011.tif" />

is the first derivative. We further assume that the distribution of probabilities in the range (0.0.5] &lt;-0.5_Λ ί / (ρ) ΦΧ ,, is given by f (p), z Then, the predicted speed, in bits per bin, for a given set of K breaks {Ik} with the corresponding representative probabilities {Pik} can be written as

<img file="PL2768145T3_D0012.tif" />

[0140] The first partial derivative with respect to each representative probability of pIK, zk = 0, ..., K -1, is given according to

<img file="PL2768145T3_D0013.tif" />

[0142] for a representative peak probability within the definition domain of Ik. The second partial derivative of this solution

<img file="PL2768145T3_D0014.tif" />

is always greater than zero if

<img file="PL2768145T3_D0015.tif" />

[0143] Therefore, if condition B12 is met, the value given in equation B10 is a probability representative of the interval Ik, which minimizes the expected overall index R due to the boundaries of the interval pk and pk +1. Otherwise, no bin is predicted in the Ik range and a representative probability '^Ξ can be chosen freely without affecting the overall R index; but this configuration should be avoided because the Ik interval will not be used for entropy coding.

[0144] In order to find optimal conditions for the range limits, we examine the first derivatives of the expected general R index in relation to the range limits pk zk = 1, ..., K d has one solution

- 1. If f (p)> 0 for all^ps equation ^f '

<img file="PL2768145T3_D0016.tif" />

for the boundary pk within the definition domain ' ^: -^;'^r and a second partial derivative for this solution

<img file="PL2768145T3_D0017.tif" />

is always greater than zero, so that it is the limit of the range "" which minimizes the expected overall speed R taking into account the representatives of the range pIK -1 and Pik. If there are d

probabilities '' with f (p) = 0, this equation ^{1 ,, J;}

Pi

Jf = 0 has many solutions, but as given in equation B13, it is still optimal, although there may be further optimal solutions.

[0145] Given the number of K intervals and the probability distribution f (p), the limits of the pk range, at k = 1, ..., K - 1, and representatives of the pLK range, at k = 0, ..., K - 1, which minimize the expected overall speed R can be obtained by solving the system of equations given by equations B10 and B13 subject to the conditions B12 for k = 0, ..., K -1. This can be achieved using the following iterative algorithm.

[0146] Algorithm 1:

1) divide the interval (0.0.5] into K of any interval 4 ⁼ * tP. Pitni with^After ~ ^pk ~ ^{0 5 1} and ^{P / i &lt;p}*⁺¹for all k = 0, ..., K - 1 in such a way that conditions B12 are respected for all k = 0, ..., K - 1.

2) Update the representatives of pIK with k = 0, ..., K - 1, according to equation B10

3) Update the limits of the interval pk zk = 1, ..., K - 1, according to equation B13

4) Repeat the previous two steps until convergence [0147] Fig. 14 shows an example of optimal interval discretization using the algorithm described. In this example, a uniform probability distribution of f (p) = 2 for 0 <p <0.5 was assumed and the probability interval (0.0.5] was separated into K = 4 intervals. It can be seen that the discretization of the probability interval leads to a segmental linear approximation of A (p) binary entropy function H (p) with A (p)> H (p) for all pe (0.0.5].

[0148] As a measure of the effect of interval discretization on coding efficiency, the expected increase in overall speed relative to the entropy limit ^ = 753 ------ 1 (θ'5) HH (p) J \ p) dp can be used. For the specific example of Fig. 14, entropy expected value _ r05.

is equal to 1 / (2 ln 2) bit per bin and the overall speed is 1.01%.

Table 4 shows the overall speed 'and' for an even distribution of probabilities and a linear increasing probability distribution f (p) = 8p zpe (0.0.5], for selected numbers of K intervals, respectively.

Table 4: Overall speed vs. number of probability intervals for a uniform and 20 linear increase in probability distribution

<td>K</td><td> 1</td><td> 2</td><td> 4</td><td> 8</td><td> 12</td><td> 16</td>

<td>Fum [% 1</td><td> 12.47</td><td> 3.67</td><td> 1.01</td><td> 0.27</td><td> 0.12</td><td> 0.07</td>

<td></td><td> 5.68</td><td> 1.77</td><td> 0.50</td><td> 0.14</td><td> 0.06</td><td> 0.04</td>

[0149] Research in this section has shown that the discretization of the interval (0.0.5] LPB probability to a small number of constant probability intervals (e.g., 8 to 10 intervals) has very little effect on coding efficiency.

[0150] The entropy coding discussed above for probability intervals, therefore, allows individual encoders to use constant probabilities.

[0151] In the following, we will first show how simple code can be designed with probability in mind. Given these results, we will develop an algorithm that jointly optimizes code design and interval breaks (0.0.5] LPB probability.

[0152] Entropy coding for constant probabilities p = pIK can be done by arithmetic coding or variable length coding. In the latter case, the following approach seems to be simple and very effective.

[0153] We consider a binary entropy coding scheme in which a variable number of bins is mapped to variable length code words. For unique decodability, the reverse mapping of the code word to the bin sequence must be unique. And because we want to design code that approaches the entropy boundary as close as possible, we can limit our considerations to bijective mapping. Such bijective mapping can be represented by a binary tree in which all leaf nodes are associated with code words, as shown in Fig. 15. The edges of the tree represent binary events. In the example of Fig. 15, the bottom edge represents the LPB bin value and the top edges are the MPB bin values. The binary tree represents the prefix code for bin, if it is fully binary, that is, when each node is either a leaf or two descendants. Each leaf node is associated with a probability based on a given LPB probability p. The main node has a probability of proot = 1. The probability of all other nodes is obtained by multiplying the probability of the corresponding ancestor p for LPB descendants and q = 1-p for MPB descendants. Each leaf node L1 has a number of LPB edges al and a number of MPB edges bl from the main node to the leaf node. For a specific LPB probability p, the probability pl for the leaf node L1 = {al, bl} is equal

Ρ: = Ρ^!(1-ΡΫ '(Β16) [0154] The binary T tree is fully characterized by the number of L leaf nodes and associated pairs {al, bl} with L = 0, ..., L -1.

[0155] Given the full binary tree T and LPB, the probability p, optimal assignment of code words to leaf nodes can be obtained using the Huffman algorithm. The obtained variable number of variable-length code word bits (V2V) mapping C is characterized by the number of code words L, which is identical to the number of leaf nodes, and the tuple {al, bl, ll} for L = 0,. .., L 1, in which Ll is the length of the codeword that is associated with the respective leaf node LI = {al, bl}. It should be noted that there are many possibilities for assigning a codeword considering the codeword length {II} and actual codeword assignment does not matter as long as the codewords are an extremely decodable prefix. The expected rate R (p, C) in bits per bin for a given C code and LPB probability p is the ratio of the expected length of the codeword and the expected number of bin per codeword

R (P, C) =

<img file="PL2768145T3_D0018.tif" />

Σα is + 6,) ΣΧ'ί¹"P) * 'is + 6,) (ΒΠ) [0156] Code design is often limited by factors such as the maximum number of L code words, the maximum number of bins per code word, and the maximum length of the code word or is limited to the codes of individual structures (for example, to enable optimal analysis). If we assume that the set of SC use codes for a specific application is given, the optimal C * e Sc code for a specific LPB probability p can be found by minimizing the expected speed R (p, C)

C (p) ~ ^arg min Λ (ρ, Ο (BI 8) [0157] As a faster alternative, minimization can also switch to a given set of ST binary trees and on each tree only one C V2V code that is obtained by the Huffman algorithm is taken into account. For example, we designed V2V codes for different LPB probabilities p considering all binary trees T in which the number of leaves of node L is less than or equal to the specified maximum Lm. 16, relative increase in p (p, C * (P)) = R (p, C * (p)) / H (P) is applied to LPB with probability p for selected maximum table sizes Lm. The increase in p (p) can usually be reduced by allowing the table to enlarge. For higher probabilities of LPB, the small size of table L from 8 to 16 code words is usually sufficient to keep p increase in speed p (p) reasonably small, but for smaller probabilities of LPB (e.g. p &lt;0.1), larger table L sizes are required.

[0158] In previous chapters we considered optimal discretization of probability assuming optimal codes and code designs for fixed probabilities of LPB. However, because, in general, we cannot reach the entropy boundary with real V2V codes limited by table dimensions, the code design and LPB probability partitioning (0.0.5] should be considered together for an optimized entropy coding design.

- C [0159] For a given range of 7 - (ρ ^ Ρλ + ιΙ-, Ck code of a given set Sc in the optimal code * if it minimizes the expected speed

R = i^{pk +}'R (p, Ck) Ap) dp ^jf,v for a given range.

<img file="PL2768145T3_D0019.tif" />

(B19) [0160] For practical formulas, the minimization of the integral in equation B19 can be simplified, with little effect on coding efficiency, by first determining the optimal »

, Ρι, representative probability '' of the interval Ik according to B10 then

C select the optimal code of a given Sc set for a representative probability p \, ^; according to B18.

[0161] Optimal limits range pK, zk = 1, ..., K -1, due to the set of Ck codes, zk = 0, ..., K - 1, can be obtained by minimizing the expected overall speed

<img file="PL2768145T3_D0020.tif" />

[0162] Setting the first derivatives to the boundaries of the interval as zero, o

bp, for k = 1, ..., K -1, gives

A = P * ^incl^ R (_ptC_tJ = R (PkCF) (B21) [0163] As in equation B13, it can be shown that '' is always the optimal solution, but depending on the probability distribution f (p), further *

Pt optimal solutions. Thus, the optimal boundary range '. between the two intervals Ik -1 and Ik from the given associated codes Ck -1 and Ck, respectively, is the intersection point of the function R (p,

CK -1) and R (p, CK).

[0164] Therefore, the following interactive algorithm can be used to jointly derive the partitioning probability of the interval and associated codes considering the number of K probability intervals, the set of possible SC codes, and the probability distribution f (p), zpe (0.0.5].

[0165] Algorithm 2:

1) Derive the initial limits of the probability interval pk, at k = 0, ..., K, using the algorithm 1 specified in sec. 3

2) Derive the representatives of pIK for the probability intervals Ik, at k = 0, ..., K - 1, in accordance with eq. B10

3) Derive the Ck e SC codes for representatives of the pIK ranges, zk = 0, ..., K - 1, in accordance with eq. B18

4) Update the limits of the pK range, where k = 1, ..., K - 1, according to the equation B21

5) Repeat the previous three steps until convergence [0166] Steps 2 and 3 in algorithm 2 can also be replaced by directly deriving the codes Ck e SC, zk = 0, ..., K - 1, based on the limits of the pk interval, with k = 0, ..., K, according to eq. B19. And as mentioned in sec. 4.1, minimization in step 3 can also go to a given set of ST binary trees, where for each binary T tree only one V2V Ck code obtained by the Huffman algorithm is included.

[0167] For example, we jointly derived divisions in K = 12 probability intervals and corresponding V2V codes using algorithm 2. To this end, the minimization in algorithm step 3 was replaced by an equivalent minimization in a given set of binary tree ST where the estimated C code for each T tree is obtained using the Huffman algorithm. We considered T trees with a maximum number of Lm = 65 leaf nodes and hence the C codes are with a maximum of 65 table entries. All binary T trees up to 16 leaf nodes were evaluated to minimize; for trees with more than 16 leaf nodes, we used suboptimal search considering the best results for trees with fewer leaf nodes.

[0168] In Fig. 17, the expected increase in speed relative to the entropy limit Δ R (p) = R (p) - H (p) for the code design example is plotted by the probability p LPB. For comparison, the expected increase in speed ΔR is also plotted for the theoretically optimal discretization of the probability interval (according to the study in section 3) and the theoretically optimal probability discretion with additional constraint - · "· '· inside the diagram. It can be seen that the joint discretization of the probability interval and the design of the V2V code leads to a shift of the interval (limits of the pK interval, with K = 1, ..., K 1, are given by local maxima in the curves). The relative expected overall speed increase relative to the entropy limit for an example project with real V2V codes is - -^{4 :} assuming an even distribution of f (p) probabilities. Corresponding relative increases in speed for the theoretically optimal discretization of the probability of the interval and the theoretically optimal discretization of the probability, with an additional limitation of the peak -1 = 0.5 are and ..... respectively.

of a finite sequence of symbols, each of the K binary encoders processes the finite [0169] The termination of the code words can be accomplished as follows. It hurts when coding^? , say &lt;

the coding sequence of bin zk = 0, ..., K - 1. And you must ensure that for

..., k of each of the K binary encoders coding, all bin sequences can be reproduced taking into account the codeword or codeword sequence '-^L>- '' [0170] When arithmetic coding is used, the arithmetic codeword for bin coding sequences must be terminated in such a way that all coding bin can be decoded with a given codeword. For the V2V codes described above, the bin at the end of the 'sequence may be the bina sequence that is associated with the code word. In this case, any code word that contains the rest of the bin sequence as a prefix can be saved. Overhead can be minimized if the corresponding code word that has the minimum length (or one of these code words) is selected. In the decoder, an additional read bin at the end of the bin sequence that can be identified, taking into account bit stream syntax systems and binaryization, was rejected.

[0171] A simple example of a code design is shown below. For illustrative purposes, we consider a simple example of the source {s} of three letters and constant associated probabilities '·' ~^_ - ^1: and '·· - ⁼ . The corresponding ternary selection trees can be converted to a full binary tree as shown in Fig. 18.

[0172] The binarization of the full binary tree of Fig. 18 is given in the Table. 5. The three argument symbol pmf ps is converted into two binary pmf-y pb 0 = (0.7, 0.3) and pb 1 = (0.6.0.4). Bin appears on each symbol in the bit stream. When b0 is 0, then b1 is also present. It should be noted that the binarization given in Table 2 is identical to the optimal one-letter Huffman code for source s.

Table 5: Binarization of the three-letter source. LPB pLPB probabilities are 0.3 for the first bin and 0.4 for the second bin

<img file="PL2768145T3_D0021.tif" />

<img file="PL2768145T3_D0022.tif" />

[0174] The average length of the code word of a single Huffman code is given as ^{= 1} -3 bit / symbol (B23) j-0 corresponding to redundancy pHC = 0.1274 bits / symbol or 10.87% of the overhead of the expected speed.

[0175] In a particular example of binarization with pmf constants, bin b0 and b1 are already coding _r , {nn,, bin, because for both bin the value - - LPB is equal to 0. The probability distribution f (s) of LPB is discrete with f (p) = 0, except p = 0.3 and p = 0.4. Therefore, optimal discretization of probability leads to K = 2 intervals with representatives pI0 = 0.3 and pI1 = 0.4.

The boundary of the p1 interval between these intervals can be freely selected in [0,3,0,4).

[0176] For source coding, the source symbol sequence is binarized into a bin sequence. Bin b0 is sent to each source symbol. Bin b1 is only sent if b0 = 0. Bin b0 and b1 are coded separately, respectively with fixed LPB probabilities pI0 =

0.3 and pI1 = 0.4.

[0177] Effective coding of the binary alphabet with a fixed probability can be achieved by simple V2V mapping. Examples of V2V mappings with small coding tables for LPB probabilities p LPB = 0.3 and p LPB = 0.4 are given in Table 6 and Table 7, respectively. V2V mapping for p LPB = 0.3 gives redundancy of 0.0069 bit / bin or 0.788%. For LPB probability pLPB = 0.4, redundancy is 0.0053 bit / bin or 0.548%.

Table 6: Bin tree and codes for LPB probability pLPB = 0.3. The redundancy of this code is 0.788%.

<img file="PL2768145T3_D0023.tif" />

Table 7: Bin tree and codes for LPB probability pLPB = 0.4. The redundancy of this code is 0.548%.

<td>Bin tree</td><td>Probability</td><td>Tree Code</td>

<td> ’111’</td><td> 0.6³ = 0.216</td><td> '11'</td>

<td>Ί10 '</td><td></td><td>Ό0Γ</td>

<td></td><td> 0.62-0.4 = 0.144</td><td></td>

<td>Ί0 '</td><td> 0.6.0.4 = 0.24</td><td>ΊΤ</td>

<td>Ό1 '</td><td> 0.4.0.6 = 0.24</td><td>Ό1 '</td>

<td>Ό0 '</td><td> 0.4² = 0.16</td><td>Ό00 '</td>

- [0178] The total predicted speed incurred by the new coding method is wr:

= 1.181 bit! Symbol (B24) [0179] In general, redundancy is 0.73% over the entropy limit, which is a significant improvement over single-letter Huffman codes.

[0180] It can be considered that a similar improvement in coding efficiency can be obtained by creating code with a wave length. In the example above, we can construct a code with the length of the waveform for the most likely symbol by considering waveforms for two symbols. Each of the events {a0a0, a0a1, a0a2, a1, a2} will be associated with a separate code word. Such a code gives a redundancy of 1.34% in relation to the entropy limit. In fact, V2V codes can be considered as a generalization of waveform codes for binary symbols (the V2V code in Table 3 is to effectively represent the waveform code). For a single symbol from the constant probability alphabet, similar coding efficiency as in the case of the presented approach can also be achieved by creating a code mapping the variable number of source symbols of the variable length code words. The main advantage of the presented solution is its flexibility in mapping arbitrary source symbol sequences from constant or adaptive probability estimates of a small number of simple binary encoders that are used with constant LPB probabilities. [0181] How to achieve unique decodability is considered below.

[0182] In the entropy coding scheme shown, the coding of the source symbol sequence s = {s0, ..., sN -1} consists of three basic steps:

• binarization of the symbol ^t!~ "'Resulting in a bin sequence' Ξ • conversion of bin sequences to bin coding sequences ·> ··· = i ^_h

<img file="PL2768145T3_D0024.tif" />

• binary entropy coding of coding sequences using bin discretization of the probability interval and K constants of binary coders [0183] Symbol sequence s = {s0, ..., sN -1} is exceptionally decoded if the coding sequence of bin

<img file="PL2768145T3_D0025.tif" />

it is extremely decoded and mapped and is reversible.

[0184] Let - notify the encoder mapping the sequence of one or more coding bin to the sequence of one or more code words (B25)

<img file="PL2768145T3_D0026.tif" />

[0185] For the unique decodability of the bin b coding sequence^c, given the lie coding sequence c (b^c), a mapping encoder ^T must have the property that the unique code word c (b^c) is assigned to every possible bin b encoding sequence^c:

<img file="PL2768145T3_D0027.tif" />

[0186] This property is always met if arithmetic or prefix codes are used. This is particularly true for the V2V codes described in sec. 4.1 (including the end of the code word described in section 4.3), because the V2V codes represent prefix codes with a variable number of bin.

[0187] However, in the entropy coding concept presented, the coding bin b sequence^c is divided into K sub compartments ¹ zk = 0, ..., K - 1,

<img file="PL2768145T3_D0028.tif" />

b ^L and to each of the sub-sequences the Ck (bkC) code word sequence is assigned by means of a specific mapping encoder ^!·^; Consequently, the state of unique decodability must be extended. Sequence of coding bin b^c is decoded unambiguously taking into account the K sequence of ck code words (bk^c) zk = 0, ..., K - 1 if each of the bin bk coding sub sequences^c it is uniquely decoded by taking into account the corresponding code word ck (bk^c) y γ and the partitioning principle 'is known by the decoder. The 'partitioning principle' is given by,, Alpb, the discretization of the LPB probability range {Ik} and the LPB probability that are associated with the coding bin zj = 0, ..., B- 1. Therefore, the discretization of the LPB probability range {Ik} must be known in the decoder and probability

Plpb

LPB each bin coding decoder.

zj = 0, ..., B-1, must be obtained in the same way in the encoder and [0188] In order to map the bin sequence to the coding sequence of bin ^c, each single bj, zj = 0, ..., B -1, is converted by binary mapping. In the decoder, the bin sequence can be obtained by binary mapping

<img file="PL2768145T3_D0029.tif" />

zj = 0, B - 1. If LPB the LPB value for each bin bj is obtained in the same way in the encoder and decoder, these mappings

From 'encoder' ^: where they represent the inverse of the respective mappings

<img file="PL2768145T3_D0030.tif" />

and hence the conversion. bin b sequences to bin b coding sequences^c, is reversible.

,, 5 = Zfi (s), [0189] Finally, we can examine the reversibility of binarization by which each symbol si, b '=) zi = 0, ..., N - 1, is mapped to the bin sequence of the Symbol si can be uniquely ii A decoded taking into account the corresponding sequence of bin b^and if binary mapping

Ib 'a' to each letter "of the alphabet Aj for the symbol si. However, this 6 = {i> 0 ..... ί> β.ή} condition is not sufficient because the division of the bin sequence into bin b sequence^and, which correspond to the symbols si, zi = 0, ..., N - 1, is not known by the decoder. A sufficient condition is given when, for each symbol si, the bin 'sequences that are associated with the letters a' n of the corresponding alphabet Ai form a prefix code and binarization mapping for each symbol si, with I = 0, ..., N - 1, are known in the decoder.

[0190] The unique decodability conditions for the entropy coding approach presented can be summarized as follows:

• binary mapping 'represent prefix codes and are known to the decoder (in the order of symbol encoding) • probability models' ··· -' · for all bj bins were obtained in the same way as in the encoder and decoder • LPB probability division ( 0.0.5] to K intervals Ik, zk = 0, ..., K -1, is known to the decoder y * • mapping '' for each probability interval Ik, zk = 0, ..., K-1 represents a unique decodable code [0191] The following describes examples of general encoder and decoder design, in more detail. We focus on coding schemes in which probability models -^ΣΞ -^ΣΞ for bin are estimated directly at the encoder and decoder and the binary K encoders use the V2V mappings described above. Each source of the s symbol is associated with a cs symbol category that specifies the type of symbol that includes its range of values. The order of symbols and related symbol categories must be given by a syntax that is known to be known in the encoder and decoder.

[0192] A block diagram for an example of a PIPE encoder and a PIPE decoder is illustrated in Fig. 19. On the decoder side, the symbols s with related categories of the symbol cs are fed to the module b = v '* (_s\ binarization, which transforms every symbol in the bin sequence y

[0193] The binarization scheme used '' is determined on the basis of the cs symbol category. In addition, the binarization module associates each bin b with a bin s sequence with the designation of the probability model cb, which specifies the probability model that is used to encode bin b. An indication of the probability model cb based on the cs symbol category, the number of current bin range within the bin s sequence, and / or the values ​​of already encoded bin and symbols.

[0194] The probability estimation module and the allocation module maintain multiple probability models that are characterized by value pairs. Receives bin b and associated indications of the probability model cb from the binarization module and passes the value

LPB and LPB 'probability-indicated probability model for the bin coding output module and probability quantizer, respectively. Then, the appropriate probability model '-^ΣΞ is updated with the value of the received bin b.

[0195] The bin coding output module receives bin b and associated LPB values' from the binarization module and probability estimator and the allocation module, and sends the coding _from going? - hAh, bin b^cthat are obtained by the probability quantizer. The probability quantizer forwards each encoding bin b^c one of the K binary encoders. It contains information about the LPB probability range of the quantization interval {Ik}.

The LPB probability, which is associated with the coding bin bc and received from the probability estimator and allocation module, is derived from comparing with the limits of the interval {pk} and the index of the probability interval k, for which "Then the coding bin b^c is passed to the associated binary converter.

[0196] Each of the binary encoders K consists of a bin buffer and a bin encoder. The bin buffer receives the encoding bin b^c from the probability quantizer and stores them in coding order. The bin encoder introduces specific V2V mappings and compares the bin sequence in the bin buffer with the bin sequences that are associated with the code words. If the bin sequence in the bin buffer equals one of these bin sequences, the bin encoder deletes the bin sequence {b^c} from the bin buffer and write the associated code word ({b^c}) to the corresponding code word stream. At the end of the coding process for the symbol sequence for all binary encoders for which the bin buffers are not empty, the ending codeword is written as described in sec. 4.3.

[0197] The received K code word streams may be separately transmitted, packaged, or stored, or may be interleaved (see section 6.2) for transmission or storage.

[0198] In the decoder, each of the K binary decoders composed of the bin decoder and the bin buffer receive one code stream. The bin decoder reads the code words ({b^c}) from the codeword stream and inserts the associated bin sequence {b^c}, in coding order, to the bin buffer.

[0199] The decoding of the symbol sequence is driven by the base syntax. Requests with the S symbol are sent together with the cs symbol category to the binarization module. The binarization module processes these symbol requests into a bin request. The bin request is associated with the cb probability model designation, which is obtained in the same way as in the encoder and sent to the probability estimator and the allocation module. The probability estimator and allocation module work like their counterpart in the encoder. Based on the indications of the probability model cb, he identifies the probability model and transmits his LPB value and LPB probability - = to the bin output module and probability quantizer, respectively.

[0200] The quantizer probability determines one of the K double decoder based on the LPB probability pLPB, in the same way as the double encoder is determined on the encoder side, removes the first bin bc coding, in coding order, with the appropriate bin buffer, and passes it to driver bin. The bin driver receives the bin bc coding and associates the LPB b LPB values ​​with the probability of the quantizer and the probability of the estimator and the allocation module, respectively, and determines the values ​​of bin b = bcCkb LPB. As a final response to the requested bin sent by the binarization module, the bin driver sends the decoded bin b values ​​to the binarization module and the estimator probability and allocation module.

[0201] In the probability of the estimator and the allocation module, the decoded value bin b is used to update the probability model {b LPB, p LPB}, which was selected by the associated cb values, in the same way as on the encoder side. Finally, the binarization module adds the received bin b to the bin s sequence that has already been received for the desired symbol and compares this bin sequence s with the bin sequence which is associated with the value symbol by the γ °% binary scheme. If the bin s sequence matches one of the bin sequences, the corresponding decode s symbol is the output of the final response to the desired symbol. Otherwise, the binarization module sends another request until the s symbol is decoded.

[0202] Decoding of the symbol sequence is terminated if no desired symbol is obtained, which is driven by syntax. Bin coding b^c it can be included in bin buffers at the end of entropy decoding (as a result of terminating codewords) and removed.

[0203] Having described and defined certain PIPE and PIPE decoders with reference to Figures 3 to 13 and having a mathematical background included in general PIPE coding with respect to Figures 14 to 19, with reference to Figures 20 to 24, more detailed description coding and decoding entropy devices. The following examples of Figures 22 to 24 not only interleave a PIPE encoded continuous bit stream with each other, but interleave with a VLC bit stream and a PIPE encoded bit stream. For comparison, PIPE encoders and PIPE interleavers for PIPE encoded bit streams, shown in Figures 7 to 13, only provide separate PIPE interleaving of the encoded bit streams. As already indicated above, the same can also be used to obtain a completely interleaved bit stream by using another pair and interleaver 134 and 228, respectively (see Figure 1 and 2), such as, for example, by using interleaving bit stream as are shown in Figures 5 and 6. However, the possibilities described then perform interleaving at both VLC bit streams as well as coded PIPE bit streams using, in other words, one-step interleaver / deinterleaver 128 and 230, respectively.

[0204] Before describing in detail the case where VLC and PIPE encoded symbols are intertwined in the center of the bit stream to achieve a more appropriate compromise between complexity and coding efficiency, and the basic structure without interleaving is described with reference to Figures 20 and 21.

[0205] The structure of the entropy coding apparatus of Figure 1a is shown in Figure 20. The entropy coding apparatus translates the stream of source symbols 1a suitable for the combination of VLC coded and PIPE coded source symbols in Figures 1 and 2, i.e. 106 and 218, respectively, for a set of two or more partial bit streams 12, 12a, with a bit stream 12a corresponding to bit streams 112 and 206 in Figures 1 and 2. [0206] As already noted above, each source symbol 1a may have a related hint that determines whether the source symbol is encoded using standard VLC codes within VLC encoder 22a that corresponds to VLC encoder 102 in Figure 1, or whether the source symbol is to be encoded with PIPE coding concept. As already described above with reference to Figures 1 and 2, this tip may not be transmitted exactly to the decoding page. Rather, the associated hint may be derived from the type or category of source symbols.

[0207] The encoded VLC symbols 1b are encoded with a standard VLC encoder which, when enabled, may depend on the just indicated categories of symbol or the type of symbol using the VLC encoder 22a. The corresponding code words 11 a are stored in a separate partial bit stream 12 a. The encoded non-VLC symbols 1 are encoded using PIPE encoding as described above with reference to Figures 1 and 3, for example, where multiple partial bit streams 12 are obtained. Some of the source symbols 1a may already be binarized in a way that consists of two parts as already indicated above with reference to Figure 1a. One of these parts can be encoded with the PIPE method and written to the respective partial bit streams 12. The other part of the bin sequence can be encoded with standard VLC codes and written to the corresponding partial bit streams 12a.

[0208] A basic device suitable for entropy decoding to Figure 20 is shown in Figure 21.

[0209] The decoder performs inverse operations relative to the encoder of Figure 20, such that the previously coded source symbol sequences 27, 27a are decoded a set of two or more partial bit streams (24,24a). The decoder includes two different flow processes: the flow for the desired data that repeats the data flowing from the encoder, and the data flow, which is represented by the reverse flow from the decoder. In the illustration in Figure 21, the dashed arrows represent the desired flow, while the solid arrows represent flow data. The decoder building blocks are practically a mapping of the encoder building blocks, but they introduce reverse operations.

[0210] Each desired symbol 13a may be associated with an indication which determines whether the source symbol is encoded using the standard VLC codes or with the PIPE encoding concept. As already indicated above with respect to Figure 20, result from regulations or the syntax analysis of the syntax elements represented by its source symbol. For example, with reference to Figures 1 and 2, it has been described that different types of syntax elements may be associated with different coding schemes, i.e., coding or PIPE coding. The same can be used for different parts of binarization, or more generally, for other assay syntax elements. If the symbol is VLC encoded, the request is given to the VLC decoder 22a and the VCL code word 23a is read from a separate partial bit stream 24a. The corresponding decoding symbol 27a is the output. If the symbol is encoded with PIPE, the symbol 27 is decoded from a set of partial bit streams 24 as described above with reference to Figure 4, for example.

[0211] Some source symbols may be binarized in a way in which binarization consists of two parts. One of these parts is the PIPE encoded approach and appropriately decoded from the associated partial bit streams 24. And another part of the bin sequence is encoded with VLC codes standard and is decoded with the VLC decoder 22a so that the corresponding code words 23a are read from the corresponding partial bit stream 24a.

Submission and multiplexing of partial bit streams (VLC coded and PIPE encoded) [0212] Partial bit streams 12, 12a which are created by the encoder can be transmitted separately, or they can be multiplexed into single bit streams or code words of partial bit streams entwined in single bit streams.

[0213] Each partial bit stream for data quality may be written to one data packet. The amount of data can be an arbitrary set of source symbols such as a still image, file or video sequence, a piece of a still image, a piece of a field or frame of a video sequence, or a frame of sound samples, etc.

[0214] Two or more partial bit streams 12, 12a for data quality or all partial bit streams for data quantity can be multiplexed into one data packet. The data packet structure including the multiplexed partial bit streams may be as shown in Figure 5.

[0215] Data packet 300 consists of a header and one data portion of each individual bit stream (for the amount of data tested). Header 301 of the data packet includes indications for the (remaining) data packet to be split in the data stream segment 302. In addition to partition indications, the header may contain additional information. An indication for splitting a data packet may be the distribution of the beginning of the data segment in units of bits or bytes, or a multiple of the number of bits or a multiple of the number of bytes. The position of the beginning of the data segment may be encoded in absolute terms, in the header of the data packet, either relative to the beginning of the data packet or relative to the end of the header or relative to the beginning of the previous data packet. The position of the beginning of the data segments can be differential coded, i.e. only the difference between the actual beginning of the data segment and the forecasting of the beginning of the data segment are coded. Prediction can be based on information already known or provided, such as the overall size of the data packet, header size, number of data segments in the data packet, location of the beginning of the preceding data segment. The start location of the first data packet may not be coded, but inferred from the size of the data packets in the header. On the decoder side, the transmitted partition indications are used to determine the beginning of the data segment. The data segments are then used as the partial bit stream, 12, 12a and the data contained in the data segments are fed to the respective VLC bin decoders and decoders in sequential order.

Code word interleaving (PIPE VLC code) [0216] In some applications, the multiplexing of partial bit streams described above (for the number of source symbols) described above in one data packet may have the following disadvantages: on the one hand for small data packets, the number of bits for auxiliary information, which are required for split signaling may become significant compared to the actual data of the partial bit streams that will ultimately reduce coding performance. On the other hand, non-multiplexing is not suitable for applications that require low latency (e.g. for video conferencing applications). Due to the multiplexing described, the encoder cannot start transmitting the data packet until the partial streams are completely formed, since the start location is not known in advance. Also, generally, the decoder must wait until it receives the beginning of the last data slice before decoding the data packet. For applications like in video conferencing systems, these delays can be added to the additional general system delay of several video images (in particular for bit rates that are close to the transmission rate and for the encoder / decoder that require almost the time interval between two image encoding / decoding images) that are key to these applications. In order to overcome these drawbacks in some applications, the encoder may be configured in such a way that the codewords that are generated by two or more transducers (bin encoder) and VLC encoder are interleaved into one bit stream. The stream of interleaved code bits can be sent directly to the decoder (ignoring the slight buffer delay, see below). On the decoder side, two or more bin decoders and a VLC codeword decoder read directly from the bit stream in decoding order; decoding can start from the first bit received. In addition, side information for multiplexing (or interleaving) partial bit streams is not required.

[0217] The basic structure of the code interleaver transmitter is shown in Figure 22. Bin encoders 10 and the VLC encoder 10a do not write the code word directly into partial bit streams, but binds to one code word buffer 29 from which the code words are written in stream 34 for encoding. The transmitters bin 10 sends a request for one or several new buffer code word entries 28 to code word buffer 29, and then sends code words 30 to code word buffer 29, which are stored in reserved buffer entries. VLC encoder 10a directly writes VLC code words 30a to code word buffer 29 (generally of variable length). The codewords 31 of the codeword buffer 29 are accessible by writing codewords 32, which write respective bits 33 to the generated bit stream 34. The code buffer 29 acts as the first input buffer first output; codeword entries that are reserved in advance have been previously written to the bit stream.

[0218] The code word buffer may be used as follows. If the new bin 7 is sent to the specified bin 8 buffer and the number of stored bin in the buffer is zero and there are currently no entries in the buffer of the bin coder codeword that is connected to the given bin buffer, the connected bin coder 10 sends a request to the codeword buffer , as a result of which one or more codeword entries are reserved in codeword buffer 29 for the given bin encoder 10. The codeword entry may have a variable number of bits; the upper limit number of bits in the buffer is usually given by the maximum code word size for the corresponding bin encoder. The next word or subsequent code words that are produced by the bin encoder (for which the code word or code words have been reserved) are stored in the reserved entry or code word buffer entries. If all reserved entries in the code word buffer for a given bin encoder are filled and the next bin is sent to the bin buffer that is connected to the specified bin encoder, one or more new code words are reserved in the code word buffer especially the bin encoder etc. The VLC encoder 10a directly writes the code words 30a to the next free buffer input of the code word 29, i.e. for the VLC encoder the codeword is reserved and stored in the codeword and executed at once. The code buffer 29 represents in a particular manner the first buffer at the input, the first at the output. Buffer entries are reserved in order. The code words for which the corresponding buffer entries were previously reserved were previously written to the bit stream. Code entry 32 checks the state of code word buffer 29, either continuously or after coded word 30 stored in code word buffer 29. If the first buffer entry contains the complete code word (i.e., the buffer entry is not restricted but contains the code word), appropriate code words 31 and the corresponding buffer entry are removed from buffer 20 and bits of code word 33 are recorded in the bit stream. This process is repeated until the first buffer entry does not contain a codeword (i.e. it is reserved or free). At the end of the decoding process, that is, if all the symbols of the source of the tested data have been processed, the code buffer should be flushed. For this rinsing process, each bin buffer / bin encoder is used as a first step: If the bin buffer contains bins, bins with individual arbitrary or arbitrary values ​​are added until the resulting bin sequence represents the bin sequence that is associated with the code word (as noted above, one of the preferred ways to add bin is to add bin values ​​that cause the shortest possible code words - or one of them - which is associated with the bin sequence, which contains up to the initial contents of the bin buffer as a prefix), this codeword is written to the next buffer write reserved for the corresponding bin encoder (and the corresponding) buffer bin is flushed. If more than one buffer entry has been reserved for one or more bin encoders, the code buffer may still contain reserved code word entries. In this case, the codeword entries are filled out arbitrarily, but valid for the respective bin encoders. The shortest valid code word or one of the shortest valid code words (if there are many) can be inserted. The VLC encoder does not require termination. Finally all other code words in the code word buffer are saved in the stream.

[0219] Two examples regarding the status of the code word buffer are shown in Figure 23. In example (a), the code buffer contains 4 positions that are filled with the code word (two of them are VLC entries) and 3 reserved entries. In addition, the next free buffer entry is marked. The first entry is filled with a code word (i.e. bin 2 encoder simply wrote the code word for the previously reserved entry). In the next step, this codeword will be removed from the codeword buffer and written to the stream. Then, the first reserved encoder code bin 3 is the first buffer input, but the entry cannot be removed from the codeword buffer, because it is only reserved, but it has not been saved with the codeword in this position. In example (B), the code buffer contains 4 entries that are filled with the code word (one of them is an entry in the VLC buffer) and 4 reserved entries. The first entry is marked as reserved, and thus the codeword entry cannot write the codeword to the bit stream. Although 4 code words are contained in the code word buffer, the code entry must wait until the code words are written in the first buffer input reserved for the bin encoder 3. It should be noted that the code words must be written in the order in which they were reserved to the possibility of reversing this process in the decoder (see below). And in addition, note that the entry in the VLC buffer is always filled, because the reserves and codeword writing are performed simultaneously.

[0220] The basic structure of the code word interleaver decoder is shown in Fig. 24. The decoders bin 22 and VLC decoder 2a do not read the code words directly from separate partial bit streams, but are connected to a bit buffer 38, from which the code words 37, 37a are read in the coding order. It should be noted that bit buffer 38 is not required because the code words can be read directly from the bit stream. The bit buffer 38 is mainly included in the illustration to clearly separate the various aspects of the process chain. Bits 39 of the bit stream 40 with the interleaved code words are sequentially inserted in the bit buffer 38, which is a First-In-First-out buffer. If a given bin decoder 22 receives a request for one or more bin sequences 35, the bin decoder 22 reads one or more code words 37 from bit buffer 38 via bit request 36. The decoder can immediately decode the source symbols. Similarly, if the VLC decoder 22a receives a request for a new symbol 19a, it reads the corresponding VLC code words 37a from bit buffer 38 and returns the decoded symbol 27a. It should be noted that the encoder (as described above) must ensure through a properly functioning codeword buffer that the codewords are written in the same order to the bit stream in which they are requested by the bin decoders. At the decoder, the entire decoding process is triggered by source symbol requests. The parameters as the number of code words that are reserved in the encoder by the specified bin encoder and the number of code words that are read by the corresponding bin decoder must be the same.

Variable-length interleaving code words with a small delay limitation [0221] The described code word interleaving does not require that any sub-compartment information be sent as auxiliary information. And because the code words are interleaved in the bit stream, the delay is generally small. However, there is no guarantee that especially the delay limitation (e.g. determined by the maximum number of bits that are stored in the code word buffer) is observed. In addition, the required buffer size for the codeword buffer can theoretically be very large. Considering the example shown in Fig. 23 (b), it may happen that no further bin is sent to bin 3 buffer, and thus bin 3 encoder will not send any new code words to the code word buffer until the rinsing process at the end of the data packet is applied. Then, all code words for bin encoders 1 and 2 must wait until the end of the data packet before they are written to the bit stream. This disadvantage can be circumvented by adding another mechanism to the encoding process (and also to the decoding process, as described later). The basic concept of this additional mechanism is that if the measurement related to the delay or upper delay (see below) exceeds the specified threshold value, the first reserved buffer entry is filled by flushing the appropriate bin buffer (using a similar mechanism as at the end of the data packet) . Due to this mechanism, the number of pending buffer entries is reduced until the associated delay value is less than the specified threshold value. On the decoder side, the bin that has been inserted on the encoder side must be removed to fulfill the delay limit. For this bin rejection, essentially the same mechanism as in the encoder can be used.

[0222] After the bit stream interleaving options of the VLC and PIPE coding described in detail, the rest of the description again focuses on the aforementioned syntax broken down into source symbols as mentioned with reference to Figs. 1b, 1c and 2b. For illustrative purposes, it is assumed in the following description that the syntactic elements distributed in this manner are of an absolute level of the transformation coefficient. However, this is just an example, and other types of syntax elements may also be supported. In particular, the following absolute levels coding by separation and using different image entropy codes and video block encoders are described.

[0223] For example, images from video sequences are usually split into blocks. Blocks and color components of blocks are predicted by either compensated motion predictions or intra predictions. The blocks can have different sizes and can be either square or rectangular. All block samples or block color components are predicted using the same set of prediction parameters, such as reference indicators (identification of reference image in already coded image sets), motion parameters (determination of the value for moving blocks between the reference image and the current image), parameters determining interpolation filter, spatial prediction modes, etc. Motion parameters can be represented by horizontal and vertical motion vectors or higher moving target parameters such as affine motion parameters consisting of 6 components. It is also possible that more than one set of prediction parameters (such as reference indicators and motion parameters) are associated with a single block. In this case, for each set of prediction parameters, one intermediate signal generated by the block or color components of the block is generated, and the final signal is generated from the weighted sum of the intermediate prediction signals. The weighting parameters and potentially also the offset constant (which is added to the weighted sum) can be either set on the image or in the reference image or set of reference images, or can be included in the set of prediction parameters of the respective block. Similarly, photographs are often disassembled into blocks and blocks are predicted by intra-prediction (which may be within intraprace or simple intra-prediction that defines the constituent element of a solid block). For corners, the signal prediction can be zero.

[0224] The difference between the original blocks and the color components of the original blocks and the corresponding prediction signals, also referred to as residual signal, is usually transformed and quantized. Two-dimensional transformation is applied to the residual signal and the obtained transformation coefficients are quantized. For this coding transformation, the blocks or color components of the blocks for which a specific set of prediction parameters has been used can be further divided before the transformation is applied. Transform blocks can be equal to or smaller than blocks that are used for prediction. It is also possible that the transformation blocks include more than one of the blocks that are used for prediction. Different transformation blocks in one image or photo from a video sequence can have different sizes and transformation blocks can represent square or rectangular blocks.

[0225] All these prediction and residue parameters can form a stream of syntaxes 138 and 226, respectively.

[0226] The resulting quantized transformation coefficients, also referred to as transformation coefficient levels, can then be transmitted using entropy coding according to any of the above coding schemes. To this end, a block of transform coefficient levels can be mapped to a vector (i.e. ordered) transform coefficient values ​​using scans, where different scans can be used for different blocks. A zigzag scan is often used. For blocks that contain only samples with one interlaced field of the frame (these blocks can be blocks of coded field blocks or fields in coded frames), it is also common to use another scan specifically designed for field blocks. A possible coding scheme for coding the obtained ordered sequence of transformation coefficients is carried out at the coding level. Typically, many transform coefficient levels are zero, and a set of consecutive transform coefficient levels that are equal to zero can be effectively represented by coding the number of consecutive transform coefficient levels that are equal to zero (run) by the appropriate syntax element. For the remaining (non-zero) transformation coefficients, the actual level is coded in the form of appropriate syntax elements. There are various alternatives at the coding level. Run before a non-zero coefficient and the level of a non-zero transformation coefficient can be coded with each other using a single syntactic element. Often, special end-of-block syntax elements that are sent after the last non-zero transform coefficients are included. Or it is possible to first encode a number of nonzero transform coefficient levels, and depending on that number, levels and starts are encoded.

[0227] A slightly different approach is used in the highly efficient CABAC H.264 / AVC entropy coding. In this case, the coding of the transform coefficient levels is divided into three stages. In the first stage, the binary syntax coded_block_flag is sent for each transformation block, which signals whether the transformation block has significant transformation coefficients (i.e. transformation coefficients that are from zero). If this element indicates that significant levels of transformation coefficients are present, a significant map with binary values ​​is coded, which determines which of the transformation coefficient levels are zero. And then in reverse scan order, the values ​​of nonzero transform coefficient levels are encoded. The meaningful map is encoded in the stream of syntax 138 as follows. For each coefficient in the order of scanning, the significant_coeff_flag binary syntax is coded, which determines whether the level of the corresponding transform coefficient is not zero. If the significant_coeff_flag bin is one, that is, if a non-zero transform coefficient level exists at this scan position, the further binary syntax last_significant_coeff_flag is encoded. This bin indicates whether the current significant transform coefficient level is the last significant transform coefficient level in the block, or whether there are further significant transform coefficient levels appear for scanning. If the last_significant_coeff flag means that no further significant transformation coefficients appear, no further syntax elements are coded to determine the significant map for the block. In the next step, the values ​​of significant transform coefficient levels are coded, whose locations in the block are already determined by the significant map. The values ​​of significant transform coefficient levels are coded in reverse scan order using the following three syntax elements. The binary syntax element coeff_abs_greater_one determines whether the absolute value of a significant transform coefficient level is greater than one. If the binary syntax element coeff_abs_greater_one indicates that the absolute value is greater than one, a further syntax element coeff_abs_level_minus_two is sent which specifies the absolute value of the transform coefficient level minus two. This is the type of syntax that can be processed according to Figs. 1b, 1c and 2b. Finally, the binary syntax element coeff_sign_flag, which specifies the sign of the transform coefficient value, is coded for each significant transform coefficient level. It should be noted that the syntactic elements that are associated with a significant map are encoded in the order of scanning, where the syntactic elements that are associated with the current values ​​of transform coefficient levels are encoded in the reverse scan order allowing the use of more favorable context models. It is also possible that the adaptive scan pattern is used for a meaningful map as in the first Test-Model H.265 / HEVC. Another concept is used to encode with absolute levels of transformation coefficients in transformation blocks larger than 4x4 in the first TestModel H.265 / HEVC. For transformation blocks larger than 4x4, the larger transformation block is divided into 4x4 blocks and 4x4 blocks are coded in the order of scanning, and for each of the 4x4 blocks the reverse scan order is used.

[0228] In CABAC H.264 / AVC entropic coding, all syntax elements regarding transform coefficient levels are encoded by binary probability modeling. The non-binary syntax element coeff_abs_level_minus_two, for example, is first binarized, that is, it is mapped to a binary decision sequence (bins), and these bins are sequentially coded. Binary syntax elements significant_coeff_flag, last_significant_coeff_flag, coeff_abs_greater_one and coeff_sign_flag are directly coded. Each encoded bin (including binary syntax elements) is associated with a context. The context represents the probability model for the encoded bin class. The probability measurement for one of the two possible bin values ​​is estimated for a given situation based on the values ​​from the bin that have already been coded in the appropriate context. For several bins related to transformation coding, the context that is used for coding is selected based on already sent syntax elements, or based on location within the block.

[0229] After coding the significant map, the block is processed in reverse scan order. As mentioned earlier, another concept is used in the first Test-Model H.265 / HEVC. The transformation blocks larger than 4x4 are divided into 4x4 blocks and the resulting 4x4 blocks are processed in the order of scanning, while the 4x4 block coefficients are coded in the reverse order of scanning. The following description applies to all 4x4 blocks in the first Test-Model H.265 / HEVC and H.264 / AVC, as well as 8x8 blocks in H.264 / AVC and this description can also be used to build syntax stream 138 and 226, respectively.

[0230] If the scanning position is significant, i.e. the ratio is non-zero, the binary syntax coeff_abs_greater_one is sent in stream 138. Initially (in block), the second context model of the respective context model set for the syntax element coeff_abs_greater_one is selected. If the encoded value of each syntax element coeff_abs_greater_one within a block is one (i.e. the absolute factor is greater than 2), context modeling switches back to the first context model of the set and uses that context model to the end of the block. Otherwise (the coded values ​​of coeff_abs_greater_one in the block are zero, and the respective absolute levels of coefficients equal to one) the contextual model is selected depending on the number of syntax elements coeff_abs_greater_one equal to zero, which were processed in reverse scanning of the block concerned. The choice of the context model for the syntax element coeff_abs_greater_one can be represented by the following equation, in which the indicator of the current context model CI + 1 is selected based on the previous index C of the context model, and the value of the previously encoded syntax element coeff_abs_greater_one, which is represented by bint in the equation. For the first syntax element coeff_abs_greater_one within a block, the context model pointer is equal to Ci = 1.

<img file="PL2768145T3_D0031.tif" />

[0231] The second syntax element for coding absolute transform coefficient levels, coeff_abs_level_minus_two is only coded when the coeff_abs_greater_one syntax element for the same scan position is equal to one. The non-binary syntax element coeff_abs_level_minus_two is binarized for the bin sequence and for the first bin of this binarization; the contextual model indicator is selected as described below. Other bins from binarization are coded with fixed contexts. The context of the first bin from binarization is selected as follows. For the first syntax element coeff_abs_level_minus_two, the first context model set of context models for the first bin of the syntax element coeff_abs_level_minus_two is selected, the corresponding context model indicator is C1 = 0. For each subsequent first bin of the syntactic element coeff_abs_level_minus_two, the context model switches to the next context model in the set, where the number of context models in the set is limited to 5. The choice of the context model can be expressed by the following formula, where the indicator of the current context model CI + 1 selects based on the previous model of the CI index context.

<img file="PL2768145T3_D0032.tif" />

[0232] As mentioned earlier, in the first syntax coeff_abs_remain_minus_two within a block, the context model pointer is equal to C1 = 0.

Note that different sets of context models can be defined for the syntax elements coeff_abs_greater_one and coeff_abs_remain_minus_two. Also remember that the first Test-Model H.265 / HEVC converting blocks larger than 4x4 can be divided into 4x4 blocks. Split 4x4 blocks can be processed for scanning and split for each 4x4 block, the context set can be obtained based on the number of coefficients greater than one in the previous 4x4 block. For the first 4x4 block a transformation block larger than 4x4 and for the source 4x4 transformation blocks a separate context set can be used.

[0233] This means that as soon as in the following description, context-based coding is applied to each of the source symbols to which coeff_abs_greater_one and coeff_abs_remain_minus_two can be distributed as follows, after which these contextual outputs can be used by allocation module 114 and 212 and VLC en / decoder 102 and 202, for example.

[0234] To reduce the complexity in terms of the number of bins processed by CABAC or PIPE compared to the beginning of the technology, as well as in terms of computational complexity or also to increase coding efficiency, the following explanation describes the approach to encoding absolute values ​​using different codes of variable length for different partitions 1401 to 1403 in photo and video encoders and decoders. However, the option below can be used for all types of absolute levels for photo and video encoders, such as differences in motion vector or adaptive loop filter coefficients. When coding the levels of transformation coefficients is performed as described below, the coding of the significant map may remain as in the first Test-Model of H.265 / HEVC, or as described above, or the coding of the significant map may also be performed as in H.264 / AVC, or otherwise.

[0235] As described above, the absolute transformation level encoding is performed in multiple partitions 1401-3. The coding scheme for example is illustrated in Fig. 1b with three partitions 1401-3. Schema boundaries 142 and 144 are variable, as a result of varying partition sizes. The coding scheme is carried out as follows.

[0236] The first entropy code is used to encode the first element or symbol of the source, i.e. the absolute level of the transformation coefficient (z) when it is less than limit1 or limit1 if it is not. If the absolute transformation coefficient level is greater than or equal to the limit1 limit of the first partition 1401, then the limit1 (142) of the first partition (1401) is subtracted from the absolute level of the transformation coefficient and the obtained value z 'is encoded with the second entropy code. If the remaining absolute transformation coefficient level z 'is greater than or equal to the limit2-limit1 limit of the second partition 1402, then the limit2-limit1 limit of the second partition is again subtracted from the absolute transformation coefficient level z' and the obtained value is encoded with the third entropy code. In general, when the partition boundary is reached, the entropy code of the next partition to the boundary is used to encode the value resulting from the absolute level of the transformation coefficient minus the boundary of the corresponding partition.

[0237] Entropy codes may be simple variable length codes like run length codes or lookup tables (eg, Huffman code) or more complex entropic codes using probability models like CABAC or PIPE. The number of partitions and the partition boundary can vary, depending on the current syntax element. The concept of partitioning shown in Fig. 1b has the following advantages. In the following, we use absolute transformation coefficients, for example, but it should be understood that they can be replaced by any other syntactic element. For example, the probability distribution of absolute levels of the transformation coefficient may be approximately a geometric distribution. Therefore, entropy codes optimized for geometric distributions can be used to encode absolute transform coefficient levels. But such a model is not always locally optimal, even if contextual modeling and probability selection model is used. For example, for a given transform block, local absolute transform coefficient levels proceed with a distribution that is not geometric at all if it contains the same amount of very small and medium range of transform coefficient levels, and the model may be true (with some accuracy) for a particular the number of blocks in the image or video or due to the laws of large numbers. For this case, the geometric distribution is not a suitable model. In addition, when assessing absolute levels of the transformation coefficient with large values, the distribution of these large values ​​are often uniform. The concept of partitioning allows different probability models for different absolute levels of transformation coefficients. For lower absolute values, more complex entropy codes can be used for higher performance, while at high absolute levels less complex entropy codes can be used to reduce complexity. [0238] As indicated above, entropy codes suitable for different partitions are used. Three types of entropy codes can be used. The first entropy code uses PIPE. However, it should be noted that according to an alternative, an entropy coding method like CABAC or any other arithmetic encoder may be used alternatively. That is, the first symbols s1 (see Fig. 2b) can be encoded by PIPE path encoding. The subdivision module 100 and the reconnect module 220 operate respectively.

[0239] For the second type, Golomb Codes and some truncated variants involving subsets (e.g., Golomb-Rice codes) may be used. That is, the second symbols s2 (see Fig. 2b) can be encoded by such VLC codes in a VLC 102/202 encoder / decoder. The sub-compartment module 100 and the reassembly module 220 operate respectively.

[0240] Exponential-Golomb codes are used like the third type. That is, the third s3 symbols (see Fig. 2b) can be encoded by such VLC Codes in VLC 102/202 Encoder / decoder.

The sub-compartment module 100 and the reassembly module 220 operate respectively. Different VLC codes and different combinations of VLC and PIPE or VLC and arithmetic codes are possible. [0241] While the first code is more complex but provides better compression efficiency, the second entropy codes represent a reasonable compromise between complexity and efficiency. Recent entropy codes, e.g. Exponential-Golomb codes, are very few complex. In the following, the coding of various sub-ranges is described.

[0242] If a sub-compartment such as the 1401 sub-compartment, such as the s1 symbol, is to be entropy coded using an entropy encoder using probability models like the PIPE 104 encoder (again, the CABAC encoder or any other arithmetic encoder can be used alternatively not described here), the sub-compartment module 120 routes the same to the PIPE encoder 104. First, non-binary levels of absolute transformation coefficient can be binarized in symbilizer 122 using the binarization method. binary maps of binary specified levels of absolute transformation coefficient to binary bin sequences. Each bin of the bin stream is coded from the context selected by the allocation module 114. Contextual modeling can be done for the first bin and fixed for the next bin sequence of bin as coeff_abs_level_minus_two in H.264 / AVC or different context modeling can be used for each bin of the bin stream. Note that binarization can be variable-length code like Golomb or Exponential-Golomb codes or other variable-length codes.

[0243] Then, a sub-compartment such as the 1402 sub-compartment or the s2 symbols can be encoded with the Golomb code, here at the VLC encoder 102 and respectively decoded at the VLC decoder. Golomb codes are a set of entropy codes designed for a geometrically arranged source. If the order of the Golomb code is zero, the Golomb code is also known as unary code. The unary code is associated with binarization coeff_abs_level_minus_two in H.264 / AVC. Golomb codes are structured as follows. For a specific Golomb parameter k, the value of n is divided by the Golomb parameter k using total division and the remainder r is calculated.

<img file="PL2768145T3_D0033.tif" />

r = n- pk [0244] After deriving the parameters defined by the formulas above, the value of n can be coded from two parts. The first part, also referred to as the prefix part, is the unary code. The obtained p + 1 value determines the number of ones and the ending zero or vice versa. The remaining value, also referred to as the rest of the part and marked as r, is represented with the truncated binary code. Golomb-Rice codes are used to encode source symbols such as s2 source symbols of Golomb-Rice codes being a subset of codes

Golomb'a. Also, when using such entropy codes for subbands 1401-3 containing a boundary, such as the alphabet of subbase 1402, the corresponding source symbols (such as s2 source symbols) are limited, and the Golomb-Rice code can be modified so that coding efficiency can be improved . The Golomb-Rice code parameter can be fixed or variable. If the parameter is variable, the parameter can be estimated as part of the context modeling stage. For example, if the source symbol s2 enters the VLC encoder 102, the latter may specify a Golomb-Rice code parameter from the s2 context. Golomb-Rice codes are Golomb codes with parameters up to the power of two. Thus, they are based on division and multiplication by two and thus can be implemented efficiently in binary architecture with move and add operations. The relationship between the Golomb-Rice parameter and the Golomb parameter is therefore kGOLOMB = 2^rotations. In the case of the Golomb-Rice code, the rest of the part is exactly a binary representation of the rest of the value. For the Golomb-Rice parameter of zero, the obtained code is identical to the unary code and there is no rest part. For a parameter of one, the rest of the part consists of one bin with two input symbols sharing the same unary prefix. Below are some sample tables for selected parameters selected Golomb-Rice.

<td>Value</td><td>Prefix</td><td>Pos.</td><td>Telephone</td><td>Pos.</td><td>Prefix</td><td>Pos.</td><td>Prefix</td><td>Pos.</td>

<td></td><td colspan="2">k = 0</td><td colspan="2">k = 1</td><td colspan="2">k = 2</td><td colspan="2">k = 3</td>

<td> 0</td><td> 0</td><td></td><td> 0</td><td> 0</td><td> 0</td><td> 00</td><td> 0</td><td> 000</td>

<td> 1</td><td> 10</td><td></td><td> 0</td><td> 1</td><td> 0</td><td> 01</td><td> 0</td><td> 001</td>

<td> 2</td><td> 110</td><td></td><td> 10</td><td> 0</td><td> 0</td><td> 10</td><td> 0</td><td> 010</td>

<td> 3</td><td> 1110</td><td></td><td> 10</td><td> 1</td><td> 0</td><td> 11</td><td> 0</td><td> 011</td>

<td> 4</td><td> 11110</td><td></td><td> 110</td><td> 0</td><td> 10</td><td> 00</td><td> 0</td><td> 100</td>

<td> 5</td><td> 111110</td><td></td><td> 110</td><td> 1</td><td> 10</td><td> 01</td><td> 0</td><td> 101</td>

<td> 6</td><td> 1111110</td><td></td><td> 1110</td><td> 0</td><td> 10</td><td> 10</td><td> 0</td><td> 110</td>

<td> 7</td><td> 11111110</td><td></td><td> 1110</td><td> 1</td><td> 10</td><td> 11</td><td> 0</td><td> 111</td>

<td> 8</td><td> 111111110</td><td></td><td> 11110</td><td> 0</td><td> 110</td><td> 00</td><td> 10</td><td> 000</td>

<td> 9</td><td> 1111111110</td><td></td><td> 11110</td><td> 1</td><td> 110</td><td> 01</td><td> 10</td><td> 001</td>

<td> 10</td><td> 11111111110</td><td></td><td> 111110</td><td> 0</td><td> 110</td><td> 10</td><td> 10</td><td> 010</td>

<td> 11</td><td> 111111111110</td><td></td><td> 111110</td><td> 1</td><td> 110</td><td> 11</td><td> 10</td><td> 011</td>

<td> 12</td><td> 1111111111110</td><td></td><td> 1111110</td><td> 0</td><td> 1110</td><td> 00</td><td> 10</td><td> 100</td>

<td> 13</td><td> 11111111111110</td><td></td><td> 1111110</td><td> 1</td><td> 1110</td><td> 01</td><td> 10</td><td> 101</td>

[0245] Given the sub-range range such as, for example, boundary2-boundary1 for sub-interval 1402 and the Golomb-Rice code parameter, the chamfering can be done as follows.

The Golomb-Rice parameter describes the number of bins required to represent the rest of the part and two to the power of the parameter value describes the number of values ​​that can be represented with the same prefix. These values ​​form a prefix group. For example, for parameters zero, only one prefix can represent one specific value, while for parameter three, eight input values ​​share the same prefix and thus the prefix group contains eight values ​​for parameter three. For a limited source alphabet, and taking into account the Golomb-Rice code, the last prefix bin can be omitted for the values ​​in the last prefix group to give the prefix code with a fixed length.

[0246] For example, the range may be nine and the Golomb-Rice parameter is two. For this example case, the number of values ​​that can be represented by the same prefix is ​​four. The maximum value is nine, which also indicates that the limit is exceeded and the next entropy code of the next sub-compartment must be used. In this example case, the values ​​from 0-3 have the prefix 0, the values ​​from 4 - 7 have the prefix 10 and 8 9 the prefix 110. Since the values ​​8 - 9 formed the last prefix group, and the remaining zero can be omitted and the values ​​8 - 9 can be represented by 11. in other words, it is to be imagined that the source symbol s2 was introduced into the VLC encoder 102 with the number of possible values ​​of s2 constituting 9 (= boundary2-granical + 1) and the Golomb-Rice parameter for this source symbol is two. Then, the corresponding Golomb-Rice code word will come from the VLC encoder 102 for this source symbol that has the prefix as just described. For the rest of the codeword part, the truncated code can be obtained as follows by the VLC 102 encoder. Normally, the Golomb-Rice code parameter indicates the bin number of the remainder of the part. In the present case, not all bin residues need to be coded. For the truncated case, all values ​​with the specified prefix (e.g. the prefix bin is omitted) are counted. Note that the calculated value is always less than or equal to the maximum number of prefix values ​​because the code is truncated. If it is possible to cut the rest of the part, the truncated rest of the part for the last prefix group can be output in the following steps. The first, largest number l to the power of two less than or equal to the calculated number is obtained. Then, in the second stage, the smallest number h to the power of two greater than the counted number is obtained. The first value l describes the number of values ​​in the prefix group with the remaining bin h. All the rest of these values ​​start at 0, followed by a binary representation of the rest limited to the number of values ​​in the remaining group. For the remaining value of the last prefix group, now treated as a new prefix group, the same procedure is performed except for the received values ​​forming the first remaining group, the rest starts from 1. This procedure is carried out until all residues are obtained. As an example, the range is 14 and the parameter is three. The first prefix group contains values ​​from 0 - 7 and the second prefix group values ​​from 8 - 13. The second prefix group contains six values. The parameters are l = 2 and h = 3. Also, the first four values ​​of the prefix groups are represented by the remainder of the three bin (remaining zero and binary representation to distinguish four values). For the last two values, the same procedure is carried out again. The parameters are l = 1 and h = 2. The rest of the last two values ​​can now be represented as 10 and 11. Another example of showing the method is the Golomb-Rice parameter of four and a range of ten. For this example, the parameters are l = 3 and h = 4. With these parameters, the truncated residuals of the part for the first eight values ​​are represented by four bins. The other two values ​​have the same remainder parts as in the previous example. If the range is nine for the previous example, the parameter for the second string is l = 0 and h = 1. The rest part of only one value that remains is 1.

[0247] The third type of entropy codes may be Exponential-Golomb codes. They can be used for equal probable distributions (e.g. with zero parameter) such as s3 source symbols. That is, the VLC encoder / decoder pair may be responsible for their encoding. As indicated above, higher levels of absolute transformation ratio are often evenly distributed. More specifically, the Exponential-Golomb zero-order code can be used to encode the last sub-compartment 1403. The origin and thus the boundary 144 with the previous sub-compartment 1402 can be variable. The location of the boundary 144 can be adjusted by the VLC 102/200 encoder / decoder depending on the previously encoded / decoded source symbols 106, 108 and / or 110 or syntax elements 138 (either 218, 204 and / or 208 or syntax elements 226).

[0248] The number of sub-compartments may be three as shown in Fig. 1b and the limits 142 and 144 may be variable. For the first sub-compartment 1401, PIPE encoding can be used as discussed above. However, alternatively CABAC can also be used. in this case, the PIPE encoder / decoder pair would be replaced by the encoder / decoder pair of binary arithmetic coding. truncated Golomb-Rice codes can be used for the second 1402 sub-compartment and the zero-row Exponential-Golomb code can be used for the last 1403 sub-compartment.

[0249] The number of sub compartments may be equal to two. The first sub-compartment 1401 can use CABAC or PIPE. The second sub-compartment may use Golomb-Rice's code such as 1402.

[0250] The number of sub-ranges may be equal to three while both limits 142 and 144 are variable. For example, for the first sub-compartment 1401, CABAC or PIPE is used, while the second sub-compartment 1402 can use the Golomb-Rice truncated code and the third sub-compartment 1403 uses the zero-order Exponential-Golomb code.

[0251] The boundary 142 of the first sub-compartment 1401 using CABAC or PIPE, which uses adaptive probability models, can be two. Contextual modeling for the first bin can be carried out as described for coeff_abs_ larger_one as described above and contextual modeling for the second bin can be performed as described for coeff_abs_level_minus_two in H.264 / AVC as also described above. The latter contextual determination would be determined by allocation modules 114 and 212, respectively. The boundary 142 of the first subpart 1401 using entropy coding which uses probability modeling (e.g., PIPE or CABAC) can be two, and contextual modeling for both the first and second bin can be done as described for coeff_abs_ increases_one in H.264 / AVC as described above. The context set as described for coeff_abs_ increases_one can be evaluated separately for the second bin.

[0252] The Golomb-Rice truncated code set can be used as entropy codes of the second sub-compartment 1402. The boundary 144 of the second sub-compartment defining the beginning of the third sub-compartment 1403 depending on this entropy code parameter can be variable. Also, the Golomb-Rice parameter can be limited by three and the parameter selection can be made as contextual modeling for coeff_abs_level_minus_two in H.264 / AVC. The boundary-boundary2 range may be variable and may depend on the Golomb-Rice parameter. If parameter is zero, range is 8. For parameter one, range is 10. For parameter two, range is 12 and for parameter three, range is 16. In this example, the Golomb-Rice parameter can be set to zero at the beginning of the transformation coefficient block. For each coded level of transformation coefficient in a block greater than or equal to the first limit, the corresponding Golomb-Rice code is used. After the encoding (or decoding) level, the following evaluation is performed to update the Golomb-Rice parameter to encode (or decode) the next level greater than or equal to the first boundary. Note that the Golomb-Rice parameter cannot be lowered by using this form of customization.

[0253] The parameter adjustment principle can be summarized as follows, where kl + 1 is the Golomb-Rice parameter to be used for coding the next level of value and the value is the previously coded value with the corresponding Golomb-Rice parameter of the kl

<img file="PL2768145T3_D0034.tif" />

^rabout

Λ value _f e [0,1] ak_t <1 value _t e [2.3] ak, <2 value_t e [4,5] Λ k, <3 (QQ) value _f > 5 A k_t <4 otherwise [0254] In a preferred embodiment, the set of truncated Golomb-Rice codes can be used as entropy codes of the second sub-compartment 1402. The boundary 144 of the second sub-compartment 1402 defining the beginning of the third sub-compartment 1403 depending on this entropy code parameter can be variable . Also in this preferred embodiment, the Golomb-Rice parameter may be limited by three and the parameter selection may be made as contextual modeling for coeff_abs_level_minus_two in H.264 / AVC. The range can be variable and depend on the Golomb-Rice parameter. If the parameter is zero, the range is 8. For parameter one, range is 10. For parameter two, range is 12 and for parameter three, range is 16. In this preferred embodiment, the Golomb-Rice parameter is set to zero at the beginning of the block. The Golomb-Rice parameter adjustment is performed as described by equation (QQ). Note that the parameter cannot be lowered by using this form of customization.

[0255] In another preferred embodiment, the set of Golomb-Rice truncated codes can be used as entropy codes of the second sub-compartment 1402. The boundary 144 of the second sub-compartment 1402 defining the beginning of the third sub-compartment 1403 depending on this entropy code parameter can be determined. Also in this preferred embodiment, the Golomb-Rice parameter can be limited to three and the parameter selection can be done as contextual modeling for coeff_abs_level_minus_two in H.264 / AVC. The range of the second sub-compartment 1402 can be set to 14. In this preferred embodiment, the Golomb-Rice parameter can be set to zero at the beginning of the block. Customization of the GolombRice parameter is performed as described by equation (QQ). Note that the parameter cannot be lowered by using this form of customization.

[0256] In another preferred embodiment, the Golomb-Rice truncated code set can be used as entropy codes of the second sub-compartment 1402. The boundary 144 of the second sub-compartment 1402 defining the beginning of the third sub-compartment 1403 depending on this entropy code parameter can be variable. Also in this preferred embodiment, the Golomb-Rice parameter can be limited to three and the parameter selection can be made as contextual modeling for coeff_abs_level_minus_two in H.264 / AVC. The range can be variable and depend on the Golomb-Rice parameter. If the parameter can be zero, the range can be 8. For parameter one, the range can be 10. For parameter two, the range can be 12 and for parameter three, the range can be 16. In this preferred embodiment, the Golomb-Rice parameter may be set to zero for the beginning of the block. The Golomb-Rice parameter adjustment is performed as described by equation (QQ). Note that the parameter cannot be lowered by using this form of customization. And it should also be noted that direct switching, e.g. from zero to three, is possible. In this preferred embodiment, part of the Golomb-Rice'as code prefix is ​​encoded with entropy codes using probability models. Contextual modeling can be done as for coeff_abs_level_minus_two in H.264 / AVC.

[0257] In another preferred embodiment, the determined Golomb-Rice parameter may be used to encode all transform coefficient levels in the current transform block. In this embodiment, the best parameter of the previous block can be calculated and used for the current transform block. For this embodiment, the range can be set by 14.

[0258] In another preferred embodiment, the determined Golomb-Rice parameter may be used to encode all transform coefficient levels in the current transform block. In this embodiment, the best parameter of the previous block can be calculated and used for the current transform block. For this embodiment, the range may be variable as described above.

[0259] In a further preferred embodiment, it is judged whether the already coded (or decoded) neighborhood of the current scan indicator contains absolute transformation ratio levels greater than the previous boundary. for this preferred embodiment, the best parameter can be obtained by using neighbors in the local causal template.

[0260] Thus, the abovementioned embodiments have, inter alia, described an entropy coding device comprising a decomposition module 136 configured to convert a sequence of 138 syntactic elements into a sequence of 106 source symbols 106 by individually decomposing at least a subset of syntactic elements into the appropriate number of n source symbols si z = 1 ... n, where the appropriate number of n source symbols depends on which of the N sequence 1401-3 intervals over which the range of values ​​of the respective syntactic elements is divided, the value of the respective syntactic elements falls, so that the sum of the values ​​of the corresponding number of source symbols s is provided from , and, if n> 1, for all i = 1 ... n-1, the value of si corresponds to the range of the ith interval; sub-compartment module 100 configured to divide the sequence of 106 source symbols into a first sub-sequence of 108 source symbols and a second sub-sequence of 110 source symbols such that all source symbols sx zx being part of the first subset {1 ... n} are contained in the first under sequence 108 and all source symbols of the syzya being part of the second subset {1 ... n} being separated from the first subset are contained in the second subsection 110; a VLC encoder 102 configured to wisely encode source symbols of the first sub-sequence 108 with respect to the symbol; and PIPE or arithmetic encoder 104 configured to encode a second sub-sequence of 110 source symbols.

[0261] The values ​​from the sub-group of syntax elements may be integer values. The second subset may be {1} with a sequence of N intervals being arranged such that the p-th sub-interval covers higher values ​​of the range of values ​​than the q-th sub-interval for all p, qe {1..n} with p> q. N can be 3. The first subset can be {2.3} with the VLC encoder (102) configured to use the Golomb-Rice code to encode s2 source symbols wisely with the symbol, and the Exp-Golomb code to wisely encode the symbol with respect to the symbol source symbols s3. More generally, 2 may be part of the first subset with the VLC (102) encoder being configured to use the Golomb-Rice code to encode s2 source symbols wisely with respect to the symbol and adjust the Golomb-Rice parameter, i.e. k, Golomb-Rice code according to previously encoded source symbols. The decomposition module can be configured to adapt one or more boundaries between sub-compartments according to pre-coded source symbols. Both customizations can be combined. That is, the positions of the boundaries limiting the second sub-compartment can be adjusted such that they are spaced apart such that the length of the Golomb-Rice code, i.e. the number of its codewords, corresponds to (or assigns) the width of the second sub-compartment. The boundary between the separation of the first and the second sub-compartment may be adjusted according to a different context dependency, and in this case the adjustment of k may determine the position of the border separating the second and third sub-compartment by the length of the Golomb-Rice code and the width of the second sub-compartment, respectively. By combining the k customization so that the width of the second sub-compartment matches the length of the Golomb-Rice code, the code efficiency is optimally utilized. adapting k to the syntax element statistics allows you to adjust the width of the second sub-compartment so that the third sub-compartment can cover as much as possible so as to limit the overall coding complexity because less complex code can be used for the third sub-compartment, such as the Exp-Golomb code . In addition, the length of the first sub-compartment may be limited to them {1, 2, 3} of the possible value of the syntax element, such as the lowest three levels. The considered syntax elements may be coded differently or constitute a residual prediction, as is the case in the above example levels of the transformation coefficient that represents the residual prediction. The first source symbols si can be symbolized / desymbolized by using truncated unary code with the resulting bin j being - partly or all of them - encoded with context adaptation or not as indicated above.

[0262] A syntax subgroup may include absolute transformation coefficient levels of the absolute transformation coefficients of the image transformation blocks with the absolute transformation coefficient levels of the respective transformation block being arranged in a sequence (138) of the syntactic elements according to the scanning path leading through the absolute transformation coefficients of the respective transformation blocks, the decomposition module can be configured, to adjust one or more boundaries between sub-compartments when decomposing the absolute transformation coefficient levels of the absolute transformation coefficients of the respective transformation block which depends on these already coded levels of the absolute transformation coefficient of the absolute transformation coefficients of the respective transformation blocks preceding the scan order or depends on the position of the absolute level the transformation coefficient to be currently distributed in the order of scanning, or based on the assessment of already reconstructed levels of the absolute transformation coefficient adjacent - either spatially or in the scan order - the position of the absolute transformation coefficient to be currently distributed.

[0263] In addition, the above-mentioned embodiments inter alia describe an entropy decoding device comprising a VLC decoder 200 configured to wisely reconstruct with reference to the code word the source symbols of the first sub-sequence of 204 source symbols from the code words of the first bit stream 206; PIPE or arithmetic decoder 202 configured to reconstruct a second sub-sequence of 208 source symbols; composition module 224 configured to assemble a sequence of 226 syntax elements with a first subsection of 204 source symbols and a second subsection of 208 source symbols by individually assembling each syntax element with the appropriate number of source symbols, wherein the composition module is configured to, for at least a subset of syntax elements . determine the appropriate number of n source symbols si zi = 1 ... n depending on which of the sequence N of 1401-3 ranges into which the range of values ​​of the relevant syntactic elements is divided, the value of the relevant syntactic elements is contained by adding the values ​​of the appropriate number of symbols source si from 1 to n as long as the value of si corresponds to the range of the ith interval so as to obtain the value of the syntax element z, where composition module 224 is configured, to recover all source symbols sx zx that is part of the first subset {1 ... n} with the first subsection (204) and all source symbols sys as the element of the second subset {1 ... n} being separated to the first subset with the second subsection 208. Values ​​from a subgroup of syntactic elements can be integer values. The second subset may be {1} with a sequence of N intervals being arranged such that the p-th sub-compartment covers higher values ​​of the range of values ​​than the q-th sub-interval for all p, qe {1..n} of p> q. N can be 3. The first subset can be {2,3} with the VLC 200 decoder being configured to use Golomb-Rice code to reconstruct s2 source symbols wisely with respect to the code word, and ExpGolomb code to reconstruct symbols wisely with respect to the code word source s3. more generally, 2 may be part of the first subset of the VLC 102 decoder being configured to use the Golomb-Rice code to reconstruct s2 source symbols wisely with respect to the code word, and to adjust the Golomb-Rice parameter of the GolombRice code as previously reconstructed source symbols. The entropy decoding apparatus may further include a reassembly module 220 configured to recombine the first source symbol sub-sequence 204 and the second source symbol sub-sequence to obtain a sequence of 218 source symbols. The syntax elements can be of a different type and the composition module can be configured to perform individual folding which depends on this type of syntax. Subsets of syntax elements may include absolute transformation coefficient levels of the absolute transformation coefficients of the image transformation blocks with the absolute transformation coefficient levels of the respective transformation block being arranged in a sequence of 138 syntactic elements according to the scan path leading through the absolute transformation coefficients of the respective transformation blocks, wherein the composition module can be configured to adjust one or more boundaries between sub-compartments when assembling the absolute transformation coefficient levels of the absolute transformation coefficients of the respective transformation block, which depends on these reconstructed levels of the absolute transformation coefficient of the absolute transformation coefficients of the respective transformation blocks preceding the scan order or depends on this position of the absolute transformation coefficient which is currently to be submitted in the scan order, or based on the estimation of the already reconstructed levels of the absolute transformation coefficient adjacent to either spatially or in the order of scanning - the position of the absolute transformation coefficient to be assembled at present.

[0264] Regarding the combination of PIPE encoding with VLC encoding using the decomposition of Fig. 1b, it should be noted that to repeat certain aspects in other words.

[0265] Described symbol sequence mapping for bit stream and inverse mapping. Each symbol has a parameter (y) associated with it, which is simultaneously known in the encoder and decoder. The entropy codec contains a lot of FIFO buffer, first on input, first on output with each of them assigned to subsets of parameter (s) that are associated with symbols. For a given symbol parameter (s), the encoder assigns the symbol to the appropriate FIFO buffer. Because the encoder assignment rule is known in the decoder, the decoder reads from the FIFO buffer to which the encoder has assigned the symbol.

[0266] Some syntax elements are encoded using standard variable-length codes and are written to the specified buffer. Other syntax elements are encoded using the PIPE coding concept. Here, the symbols are first binarized and the resulting bin is classified based on related probability estimates. The probability estimate can be predetermined or derived from a measurement that can be performed simultaneously in the encoder and the decoder. The specified FIFO buffer contains symbols with estimated probability values ​​belonging to a subset of probabilities that are selected so that entropy coding can be improved. The improvement achieved by combining the PIPE concept with VLC is the reduction of complexity while ensuring high coding efficiency. The symbols for which the standard VLC code is suitable for coding are from a simple and low-complex VLC approach, and the other symbols for which the transmission speed will be significantly increased by their coding with the VLC code are encoded with the more sophisticated PIPE concept.

[0267] Thus, in order to further reduce the complexity of entropy coding, the symbols were divided into two categories. The first category symbols can be well represented with VLC codes and do not require more complex PIPE encoding, while the second category symbols cannot be effectively represented with VLC codes and the PIPE encoding for these symbols significantly reduces the required bit rate.

[0268] Although certain aspects have been described with respect to the device, it is obvious that these aspects also provide a description of the corresponding method, where the block or device corresponds to the method step or feature of the method step. Similarly, aspects described in the context of a method step also describe the respective block or element or function of the respective device. Some or all of the method steps may be performed by (or using) a hardware device, such as, for example, a microprocessor, programmable computer or electronic system. In some embodiments, one or more of the most important steps of the method may be performed by such a device.

[0269] The encoded / compressed signals of the invention may be recorded on a digital data carrier or may be transmitted in a transmission medium such as a wireless transmission medium or a wired transmission medium such as the Internet.

[0270] Depending on some implementation requirements, embodiments of the invention can be implemented in hardware or in software. The implementation can be carried out using a digital data carrier, e.g. floppy disk, DVD, BlueRay, CD, ROM, PROM, EPROM, EEPROM or flash memory, having on them electronically readable control signals that cooperate (or are able to cooperate) in a programmable computer system such that a suitable method is performed. Therefore, the digital storage medium can be readable by a computer.

[0271] Some embodiments of the invention include a data carrier having electronically readable control signals that are able to interact with a programmable computer system such that one of the methods described herein is performed.

[0272] In general, embodiments of the present invention may be implemented as a computer program product with a program code, the program code operating to perform one of the methods when the computer program is running on a computer. The program code may, for example, be saved on a machine-readable medium. [0273] Other embodiments include a computer program for performing one of the methods described herein, recorded on a machine readable medium.

[0274] In other words, an embodiment of the method of the invention is thus a computer program comprising the program code for performing one of the methods described herein when the computer program is running on the computer.

[0275] a further embodiment of the methods according to the invention is thus in the form of a data carrier (or digital data carrier or computer readable medium) containing a computer program stored therein for performing one of the methods described herein.

[0276] A further embodiment of the method according to the invention is thus in the form of a data stream or signal sequence constituting a computer program for performing one of the methods described herein. The data stream or signal sequence may for example be configured to be transmitted via a data communication connection, for example via the Internet.

[0277] Another embodiment includes processing components, for example a computer or programmable logic device, configured or adapted to perform one of the methods described herein.

[0278] Another embodiment includes a computer having a computer program installed on it for performing one of the methods described herein.

[0279] In some embodiments, the programmable logic device (e.g., programmable logic gate table) may be used to perform some or all of the functionality of the methods described herein. In some embodiments, a directly programmable logic gate table may cooperate with a microprocessor to perform one of the methods described herein. In general, the methods are preferably performed using any hardware device.

[0280] The above described embodiments are merely illustrative of the principles of the present invention. It is understood that modifications and variants of the solutions and details described herein will become apparent to other specialists in the field. The assumption is that the limitation occurs only by the scope of the appended claims, and not by the specific details provided herein only to describe and explain individual embodiments.

GE Video Compression, LLC; United States of America Representative:

EP2768145

14117/16