10918-1 : 1993(E)
`The subdivision of the current probability interval would ideally require a multiplication of the interval by the probability
`estimate for the LPS. Because this subdivision is done approximately, it is possible for the LPS sub-interval to be larger
`than the MPS sub-interval. When that happens a “conditional exchange” interchanges the assignment of the sub-intervals
`such that the MPS is given the larger sub-interval.
`
`Since the encoding procedure involves addition of binary fractions rather than concatenation of integer code words, the
`more probable binary decisions can sometimes be coded at a cost of much less than one bit per decision.
`
`D.1.1.2 Conditioning of probability estimates
`
`An adaptive binary arithmetic coder requires a statistical model — a model for selecting conditional probability estimates to
`be used in the coding of each binary decision. When a given binary decision probability estimate is dependent on a
`particular feature or features (the context) already coded,
`it is “conditioned” on that feature. The conditioning of
`probability estimates on previously coded decisions must be identical in encoder and decoder, and therefore can use only
`information known to both.
`
`Each conditional probability estimate required by the statistical model is kept in a separate storage location or “bin"
`identified by a unique context-index S. The arithmetic coder is adaptive, which means that the probability estimates at
`each context-index are developed and maintained by the arithmetic coding system on the basis of prior coding decisions
`for that context-index.
`
`D.1.2
`
`Encoding conventions and approximations
`
`The encoding procedures use fixed precision integer arithmetic and an integer representation of fractional values in which
`X’8000’ can be regarded as
`the decimal value 0.75. The probability interval, A,
`is kept
`in the integer
`range X’8000’ SA <X’lO00O’ by doubling it whenever its integer value falls below X’8000’. This is equivalent to
`keeping A in the decimal range 0.75 S A < 1.5. This doubling procedure is called renormalization.
`
`The code register, C, contains the trailing bits of the bit stream. C is also doubled each time A is doubled. Periodically
`— to keep C from overflowing — a byte of data is removed from the high order bits of the C-register and placed in the
`entropy-coded segment.
`
`Carry—overinto the entropy-coded segment is limited by delaying X’FF’ output bytes until the carry-over is resolved. Zero
`bytes are stuffed after each X’FF’ byte in the entropy-coded segment in order to avoid the accidental generation of
`markers in the entropy-coded segment.
`
`Keeping A in the range 0.75 S A < 1.5 allows a simple arithmetic approximation to be used in the probability interval
`subdivision. Normally, if the current estimate of the LPS probability for context-index S is Qe(S), precise calculation of
`the sub-intervals would require:
`
`Probability sub-interval for the LPS;
`Qe(S) X A
`A — (Qe(S) X A) Probability sub-interval for the MPS.
`
`Because the decimal value of A is of order unity, these can be approximated by
`
`Qe(S)
`A — Qe(S)
`
`Probability sub-interval for the LPS;
`Probability sub-interval for the MPS.
`
`Whenever the LPS is coded, the value of A — Qe(S) is added to the code register and the probability interval is reduced to
`Qe(S). Whenever the MPS is coded, the code register is left unchanged and the interval is reduced to A — Qe(S). The
`precision range required for A is then restored, if necessary, by renormalization of both A and C.
`
`With the procedure described above, the approximations in the probability interval subdivision process can sometimes
`make the LPS sub-interval larger than the MPS sub-interval. If, for example, the value of Qe(S) is 0.5 and A is at the
`minimum allowed value of 0.75, the approximate scaling gives one-third of the probability interval to the MPS and two-
`thirds to the LPS. To avoid this size inversion, conditional exchange is used. The probability interval is subdivided using
`the simple approximation, but the MPS and LPS sub-interval assignments are exchanged whenever the LPS sub-interval is
`larger than the MPS sub-interval. This MPS/LPS conditional exchange can only occur when a renormalization will be
`needed.
`
`Each binary decision uses a context. A context is the set of prior coding decisions which determine the context-index, S,
`identifying the probability estimate used in coding the decision.
`
`Whenever a renormalization occurs, a probability estimation procedure is invoked which determines a new probability
`estimate for the context currently being coded. No explicit symbol counts are needed for the estimation. The relative
`probabilities of renormalization after coding of LPS and MPS provide, by means of a table-based probability estimation
`state machine, a direct estimate of the probabilities.
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 251/714
`
`

`
`ISO/IEC 10918-1 : 1993(E)
`
`D.1.3
`
`Encoder code register conventions
`
`The flow charts in this annex assume the register structures for the encoder as shown in Table D.2.
`
`Table D.2 — Encoder register connections
`
`C-register
`
`A-register
`
`0000cbbb,
`
`00000000,
`
`bbbbbsss,
`
`00000000,
`
`xxxxxxxx,
`
`aaaaaaaa,
`
`xxxxxxxx
`
`aaaaaaaa
`
`The “a” bits are the fractional bits in the A-register (the current probability interval value) and the “x” bits are the
`fractional bits in the code register. The “s” bits are optional spacer bits which provide useful constraints on carry-over. and
`the “b” bits indicate the bit positions from which the completed bytes of data are removed from the C-register. The “c" bit
`is a carry bit. Except at the time of initialization, bit 15 of the A-register is always set and bit 16 is always clear (the LSB
`is bit 0).
`
`These register conventions illustrate one possible implementation. However, any register conventions which allow
`resolution of carry-over in the encoder and which produce the same entropy-coded segment may be used. The handling of
`carry-over and the byte stuffing following X’FF’ will be described in a later part of this annex.
`
`D.1.4
`
`Code_1(S) and Code_0(S) procedures
`
`When a given binary decision is coded, one of two possibilities occurs —either a l-decision or a 0-decision is coded.
`Code_1(S) and Code_0(S) are shown in Figures D.1 and D.2. The Code_1(S) and Code_0(S) procedures use probability
`estimates with a context-index S. The context-index S is determined by the statistical model and is, in general, a function
`of the previous coding decisions; each value of S identifies a particular conditional probability estimate which is used in
`encoding the binary decision.
`
`Code_1(S)
`
`No
`
`Yes
`
`I I
`
`T|S01800-93/d039
`
`Figure D.1 — Code_1(S) procedure
`
`CCITT Rec. T.8~1 (1992 E)
`
`HUAWEI EX. 1016 - 252/714
`
`

`
`‘\_/
`)/IEC 10918-1 : 1993(E)
`
`Code_O(S)
`
`No
`
`Yes
`
`Code_LPS(S
`
`)
`
`Code_MPS(S)
`
`I
`
`TISOI 030-93/d04O
`
`Figure D.2 — Code_0(S) procedure
`
`The context-index S selects a storage location which contains Index(S), an index to the tables which make up the
`probability estimation state machine. When coding a binary decision, the symbol being coded is either the more probable
`symbol or the less probable symbol. Therefore, additional information is stored at each context-index identifying the sense
`of the more probable symbol, MPS(S).
`
`For simplicity, the flow charts in this subclause assume that the context storage for each context-index S has an additional
`storage field for Qe(S) containing the value of Qe(Index(S)). If only the value of Index(S) and MPS(S) are stored, all
`references to Qe(S) should be replaced by Qe(Index(S)).
`
`The Code_LPS(Sl procedure normally consists of the addition of the MPS sub-interval A — Qe(S) toithe bit stream and a
`scaling of the interval to the sub-interval, Qe(S). It is always followed by the procedures for obtaining a new LPS
`probability estimate (Estimate_Qe(S)_after_LPS) and renormalization (Renorm_e) (see Figure D.3).
`
`However, in the event that the LPS sub-interval is larger than the MPS sub-interval, the conditional MPS/LPS exchange
`occurs and the MPS sub-interval is coded.
`
`The Code_MPS(S) procedure normally reduces the size of the probability interval to the MPS sub-interval. However, if
`the LPS sub-interval is larger than the MPS sub-interval, the conditional exchange occurs and the LPS sub-interval is
`coded instead. Note that conditional exchange cannot occur unless the procedures for obtaining a new LPS probability
`estimate (Estimate_Qe(S)_after_MPS) and renormalization (Renorm_e) are required after the coding of the symbol (see
`Figure D.4).
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 253/714
`
`

`
`ISO/IEC 10918-1 2 1993(E)
`
`Code_LPS(S)
`
`Estimaie_Qe(S)_afler_LPS
`Henorm_e
`
`T|SO1040-93Id041
`
`Figure D.3 -— Code_LPS(S) procedure with conditional MPSILPS exchange
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 254/714
`
`

`
`/rec 10913-1 : 19930:)
`
`; C
`
`ode__MPS(S)
`
`A=A—oam
`
`:2
`
`Estimate_Qe(S)_afler_MPS
`Flenorm_e
`
`TlSO1050-93/d042
`
`Figure D.4 - Code_MPS(S) procedure with conditional MPS/LPS exchange
`
`D.1.5
`
`Probability estimation in the encoder
`
`D.1.S.1 Probability estimation state machine
`
`The probability estimation state machine consists of a number of sequences of probability estimates. These sequences are
`interlinked in a manner which provides probability estimates based on approximate symbol counts derived from the
`arithmetic coder renormalization. Some of these sequences are used during the initial “learning” stages of probability
`estimation; the rest are used for “steady state” estimation.
`
`Each entry in the probability estimation state machine is assigned an index, and each index has associated with it a
`Qe value and two Next_Index values. The Next_Index__MPS gives the index to the new probability estimate after an MPS
`renormalization; the Next_Index_LPS gives the index to the new probability estimate after an LPS renormalization. Note
`that both the index to the estimation state machine and the sense of the MPS are kept for each context-index S. The sense
`of the MPS ischanged whenever the entry in the Switch_MPS is one.
`
`The probability estimation state machine is given in Table D.3. Initialization of the arithmetic coder is always with
`an MPS sense of zero and a Qe index of zero in Table D.3.
`
`The Qe values listed in Table D.3 are expressed as hexadecimal integers. To approximately convert the 15-bit integer
`representation of Qe to a decimal probability, divide the Qe values by (4/3) X (X’8000’).
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 255/714
`
`

`
`ISO/IEC 10918-1 : 1993(E)
`
`Table D.3 — Qe values and probability estimation state machine
`
`_Va11l6
`
`X’0lA4’
`X’0160‘
`x’o125’
`X’00F6’
`X’00CB’
`X’0OAB’
`X‘0O8F’
`X’5B12’
`X’4D04’
`x'412c'
`X’37D8’
`X’2FE8’
`x’293c’
`x'2379*
`X’ IEDF’
`X’1AA9’
`x’ 174E’
`x’1424'
`x'119c’
`X’OF6B’
`X’0D51’
`X’0BB6’
`X'0A40’
`x'5332’
`X’4D1C’
`X’438E’
`X’3BDD'
`X’34EE’
`X’2EAE’
`X’299A’
`X’ 2516’
`x'5570'
`X’4CA9’
`X’44D9’
`X’3E22’
`X‘3824'
`X‘32B4’
`X'2E17’
`X’56A8’
`X’4F46’
`X’47E5’
`X'41CF’
`X'3C3D’
`X'375E’
`x'5231'
`x’4c01=’
`X‘4639'
`X’415E’
`X’5627’
`X’50E7’
`X’4B85’
`X’5597'
`X’504F’
`X’5A10’
`x*s522'
`X’59EB’
`
`N
`
`Id
`
`.
`
`_Value
`
`_LPS
`
`_MPS
`
`_M1’S
`
`X’5AlD’
`X’2586’
`}('I114’
`X’080B'
`X’03D8'
`X’OlDA'
`X’00E5’
`X’006F’
`X’O036’
`X’00lA'
`X’O00D’
`XWW€
`X’0OO3’
`X’0001’
`X’5A7F’
`X’3F25’
`WNW’
`X’207C’
`X’ l7B9‘
`)(’1l82’
`X’0CEF’
`X’O9Al’
`X’O72F’
`X'O55C‘
`X’0406'
`X’0303'
`X’(]240'
`X’O1Bl’
`XMM’
`X’00F5’
`X’00B7'
`XW%’
`X’0068’
`X‘0O4E'
`X’0O3B’
`X’002C’
`X3AEY
`X’484C’
`XGAOD’
`X’2EF1’
`X'261F’
`X’ 1F33’
`X19AW
`1(’1518’
`}(’1177’
`X’0E74’
`WWW’
`X’09F8’
`X’0861’
`X’0706’
`X’05CD’
`X’04DE’
`X’040F’
`X'0363’
`X’O2D4’
`X’025C'
`X’01F8'
`
`NNmHHHH——_~__N—ommqamAuN~oewqomAmN_o
`mmmmwummmmpmmmmOo\lO\(.I|.Bu)t\J»dO\'3OO\lO\LII-I3
`
`NU»)
`
`-P-S3-¥>~bU)U-JIUD-O\D
`
`-I5A
`
`mmmmmmmbAhA#mmAmN~o@wqmm
`
`oooooooooooooooooocowoooooooocooooccoooooo—oooocoooooooo~
`
`uwm\:axu:.h.uaN-—o\ooo\1c\<.n4:.m3tg\ooo\Ixoaggfia8%§:1)g8n§Bg»‘3‘5J’\3;':I"3'\’L7:;$5:E\goo\;a,u..,,,l,,N,_..
`
`ummmmmmmAAAAAAA
`
`CCITT Rec. T.81 (1992 E)
`
`woHoooowooooooooo~ooooco~ocooooo—ooooooooooooooowooooooo
`
`HUAWEI EX. 1016 - 256/714
`
`

`
`D.1.5.2 Renormalization driven estimation
`
`/nac 10918-1 : 1993(E)
`
`The change in state in Table D.3 occurs only when the arithmetic coder interval register is renormalized. This must always
`be done after coding an LPS, and whenever the probability interval register is less than X'8000' (0.75 in decimal notation)
`after coding an MPS.
`
`When the LPS renormalization is required, Next_Index_LPS gives the new index for the LPS probability estimate. When
`the MPS renonnalization is required, Next_Index_MPS gives the new index for the LPS probability estimate. If
`Switch_MPS is 1 for the old index, the MPS symbol sense must be inverted after an LPS.
`
`D.1.5.3 Estimation following renormalization after MPS
`
`The procedure for estimating the probability on the MPS renormalization path is given in Figure D.5. Index(S) is part of
`the information stored for context-index S. The new value of Index(S) is obtained from Table D.3 from the column labeled
`Next__Index_MPS, as that is the next index after an MPS renormalization. This next index is stored as the new value of
`lndex(S) in the context storage at context-index S, and the value of Qe at this new Index(S) becomes the new Qe(S).
`MPS(S) does not change.
`
`Estimate_Qe(S)_
`after_MPS
`
`I = Index(S)
`I = Next_Index_MPS(l)
`lndex(S) = I
`Qe(S) = Qe_Value(|)
`
`T1SO106l}93/dO43
`
`Figure D.5 — Probability estimation on MPS renormalization path
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 257/714
`
`

`
`ISO/IEC 10918-1 : 1993(E)
`D.l.5.4 Estimation following renormalization after LPS
`
`The procedure for estimating the probability on the LPS renormalization path is shown in Figure D.6. The procedure is
`similar to that of Figure D.5 except that when Switch_MPS(I) is 1, the sense of MPS(S) must be inverted.
`
`Estimate_Qe(S)_
`after_LPS
`
`I = |ndex(S)
`
`MPS(S) = 1- MPS(S)
`
`I = Next_|ndex_LPS(|)
`|ndex(S) = I
`Qe(S) = Qe_Va|ue(|)
`
`TlSO1070-93Id044
`
`Figure D.6 — Probability estimation on LPS renormalization path
`
`D.1.6
`
`Renormalization in the encoder
`
`The Renorrn_e procedure for the encoder renormalization is shown in Figure D.7. Both the probability interval register A
`and the code register C are shifted, one bit at a time. The number of shifts is counted in the counter CT; when CT is zero,
`a byte of compressed data is removed from C by the procedure Byte_out and CT is reset to 8. Renormalization continues
`until A is no longer less than X’8000’.
`
`CCITT Rec. T.8l (1992 E)
`
`HUAWEI EX. 1016 - 258/714
`
`

`
`‘
`
`/IEC 10918-1 : l993(E)
`
`Renorm_e
`
`A=SLLA‘l
`C=SLLC1
`CT=CT—1
`
`A < X’8000’
`?
`
`11801080-93Id045
`
`Figure D.7 — Encoder renormalization procedure
`
`The Byte_out procedure used in Renorm_e is shown in Figure D.8. This procedure uses byte—stuffing procedures which
`prevent accidental generation of markers by the arithmetic encoding procedures. It also includes an example of a
`procedure for resolving carry-over. For simplicity of exposition, the buffer holding the entropy-coded segment is assumed
`to be large enough to contain the entire segment.
`
`In Figure D.8 BP is the entropy-coded segment pointer and B is the compressed data byte pointed to by BP. T in Byte_out
`is a temporary variable which is used to hold the output byte and carry bit. ST is the stack counter which is used to count
`X’FF’ output bytes until any carry-over through the X’FF’ sequence has been resolved. The value of ST rarely exceeds 3.
`However, since the upper limit for the value of ST is bounded only by the total entropy-coded segment size, a precision of
`32 bits is recommended for ST.
`
`Since large values of ST represent a latent output of compressed data, the following procedure may be needed in high
`speed synchronous encoding systems for handling the burst of output data which occurs when the carry is resolved.
`
`CCITT Rec. T.81 (1992 E)
`
`63
`
`HUAWEI EX. 1016 - 259/714
`
`

`
`ISO/IEC 10918-1 2 1993(E)
`
`T=SFlLC19
`
`Output_stacked_
`zeros
`
`_
`ST " ST + 1
`
`Output_stacked_
`X’FF's
`
`C = C AND X’7FFFF’
`
`11801090-93/d046
`
`Figure D.8 — Byte_out procedure for encoder
`
`When the stack count reaches an upper bound determined by output channel capacity, the stack is emptied and the stacked
`X’FF' bytes (and stuffed zero bytes) are added to the compressed data before the carry-over is resolved. If a carry-over
`then occurs, the carry is added to the final stuffed zero, thereby converting the final X’FFOO’ sequence to the X‘FFO1’
`temporary private marker. The entropy-coded segment must then be post-processed to resolve the carry—over and remove
`the temporary marker code. For any reasonable bound on ST this post processing is very unlikely.
`
`Referring to Figure D.8, the shift of the code register by 19 bits aligns the output bits with the low order bits of T. The
`first test then determines if a carry-over has occurred. If so, the carry must be added to the previous output byte before
`advancing the segment pointer BP. The Stuff_0 procedure stuffs a zero byte whenever the addition of the carry to the data
`already in the entropy—coded segments creates a X’FF’ byte. Any stacked output bytes - converted to zeros by the carry-
`over — are then placed in the entropy—coded segment. Note that when the output byte is later transferred from T to the
`entropy-coded segment (to byte B), the carry bit is ignored if it is set.
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 260/714
`
`

`
`Ifa cany has not occurred, the output byte is tested to see if it is X’FF’. If so, the stack count ST is incremented, as the
`output must be delayed until the carry-over is resolved. If not, the carry-over has been resolved, and any stacked X’FF’
`bytes must then be placed in the entropy-coded segment. Note that a zero byte is stuffed following each X’FF’.
`
`\=;::}DlIEC 10918-1 : 1993(E)
`
`The procedures used by Byte_out are defined in Figures D.9 through D.11.
`
`Output_stacked_
`zeros
`
`TlS01810-93/dO47
`
`Figure D.9 — Output_stacked_zeros procedure for encoder
`
`Output_stacked_
`X’FF's
`
`11501 100-93/dD48
`
`Figure D.10 — Output_stacked_X’FF’s procedure for encoder
`
`CCITT Rec. T.8l (1992 E)
`
`HUAWEI EX. 1016 - 261/714
`
`

`
`ISO/IEC 10913-1 : 1993(E)
`
`T|S01110-93/(1049
`
`Figure D.11 — Stuff_0 procedure for encoder
`
`D.1.7
`
`Initialization of the encoder
`
`The Initenc procedure is used to start the arithmetic coder. The basic steps are shown in Figure D.12.
`
`lnitenc
`
`Initialize statistics areas
`ST = D
`A = X’1000O’
`(see Note below)
`C = 0
`CT = 11
`BP = BPST — 1
`
`TISO1 120-93/(1050
`
`Figure D.12 — Initialization of the encoder
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 262/714
`
`

`
`/IEC 10918-1 : l993(E)
`:‘?.“;'
`_.
`The probability estimation tables are defined by Table D.3. The statistics areas are initialized to an MPS sense of O and a
`Qe index of zero as defined by Table D.3. The stack ‘count (ST) is cleared, the code register (C) is cleared, and the interval
`register is set to X’10000’. The counter (CT) is set to 11, reflecting the fact that when A is initialized to X’l0OOO’ three
`spacer bits plus eight output bits in C must be filled before the first byte is removed. Note that BP is initialized to point to
`the byte before the start of the entropy-coded segment (which is at BPST). Note also that the statistics areas are initialized
`for all values of context-index S to MPS(S) = O and Index(S) = 0.
`
`the precision of
`in both Initenc and Initdec.
`initialized to X’10000’
`is
`NOTE— Although the probability interval
`the probability interval register can still be limited to 16 bits. When the precision of the interval register is 16 hits, it is initialized to
`ZBIO.
`
`D.1.8
`
`Termination of encoding
`
`The Flush procedure is used to terminate the arithmetic encoding procedures and prepare the entropy-coded segment for
`the addition of the X’FF’ prefix of the marker which follows the arithmetically coded data. Figure D.13 shows this flush
`procedure. The first step in the procedure is to set as many low order bits of the code register to zero as possible without
`pointing outside of the final interval. Then, the output byte is aligned by shifting it left by CT bits; Byte_out then removes
`it from C. C is then shifted left by 8 bits to align the second output byte and Byte_out is used a second time. The
`remaining low order bits in C are guaranteed to be zero, and these trailing zero bits shall not be written to the entropy-
`coded segment.
`
`C|ear_finaI_bits
`
`C=SLLC CT
`
`C=SLLC8
`
`Byte_out
`Discard_final_zeros
`
`TISO1 130-93/dO51
`
`Figure D.13 —— Flush procedure
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 263/714
`
`

`
`ISO/IEC 10918-1 : 199303)
`
`\../
`
`Any trailing zero bytes already written to the entropy-coded segment and not preceded by a X’FF’ may, optionally, be
`discarded. This is done in the Discard_final_zeros procedure. Stuffed zero bytes shall not be discarded.
`
`Entropy coded segments are always followed by a marker. For this reason, the final zero bits needed to complete decoding
`shall not be included in the entropy coded segment. Instead, when the decoder encounters a marker, zero bits shall be
`supplied to the decoding procedure until decoding is complete. This convention guarantees that when a DNL marker is
`used, the decoder will intercept it in time to correctly terminate the decoding procedure.
`
`C|ear_fina|_bils
`
`T = C + A — 1
`T = T AND
`X’FFFFOO0O‘
`
`T = T + X'8000’
`
`T|SO1140-G3/dU52
`
`Figure D.14 — Clear_final_bits procedure in Flush
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 264/714
`
`

`
`/IEC 10918-1 : 1993(E)
`
`Discard_final_zeros
`
`BP < BPST
`?
`
`TlSO1150-93/d053
`
`Figure D.15 — Discard_linal_zeros procedure in Flush
`
`D.2
`
`Arithmetic decoding procedures
`
`Two arithmetic decoding procedures are used for arithmetic decoding (see Table D.4).
`
`The “Decodc(S)” procedure decodes the binary decision for a given context—index S and returns a value of either 0 or 1. It
`is the inverse of the “Code_0(S)” and “Code__1(S)” procedures described in D.1. “Initdec” initializes the arithmetic
`coding entropy decoder.
`
`Table D.4 — Procedures for binary arithmetic decoding
`
`Procedure
`
`Decode(S)
`
`Initdec
`
`Decode a binary decision with context-index S
`
`Initialize the decoder
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 265/714
`
`

`
`ISO/IEC 10918-1 : 1993(E)
`D.2.1
`Binary arithmetic decoding principles
`
`The probability interval subdivision and sub-interval ordering defined for the arithmetic encoding procedures also apply to
`the arithmetic decoding procedures.
`
`Since the bit stream always points within the current probability interval, the decoding process is a matter of determining,
`for each decision, which sub-interval is pointed to by the bit stream. This is done recursively, using the same probability
`interval sub-division process as in the encoder. Each time a decision is decoded, the decoder subtracts from the bit stream
`any interval the encoder added to the bit stream. Therefore, the code register in the decoder is a pointer into the current
`probability interval relative to the base of the interval.
`
`If the size of the sub-interval allocated to the LPS is larger than the sub-interval allocated to the MPS, the encoder invokes
`the conditional exchange procedure. When the interval sizes are inverted in the decoder, the sense of the symbol decoded
`must be inverted.
`
`D.2.2
`
`Decoding conventions and approximations
`
`The approximations and integer arithmetic defined for the probability interval subdivision in the encoder must also be
`used in the decoder. However, where the encoder would have added to the code register, the decoder subtracts from the
`code register.
`
`D.2.3
`
`Decoder code register conventions
`
`The flow charts given in this section assume the register structures for the decoder as shown in Table D.5:
`
`Table D.5 - Decoder register conventions
`
`Cx register
`
`C-low
`
`A-register
`
`xxxxxxxx,
`
`bbbbbbbb,
`
`aaaaaaaa,
`
`xxxxxxxx
`
`00000000
`
`aaaaaaaa
`
`Cx and C-low can be regarded as one 32-bit C-register, in that renormalization of C shifts a bit of new data from bit 15 of
`C-low to bit 0 of Cx. However, the decoding comparisons use Cx alone. New data are inserted into the “b” bits of C-low
`one byte at a time.
`
`NOTE —The comparisons shown in the various procedures use arithmetic comparisons, and therefore assume precisions
`greater than 16 bits for the variables. Unsigned (logical) comparisons should be used in 16-bit precision implementations.
`
`D.2.4
`
`The decode procedure
`
`The decoder decodes one binary decision at a time. After decoding the decision, the decoder subtracts any amount from
`the code register that the encoder added. The amount left in the code register is the offset from the base of the current
`probability interval to the sub-interval allocated to the binary decisions not yet decoded. In the first test in the decode
`procedure shown in Figure D.16 the code register is compared to the size of the MPS sub-interval. Unless a conditional
`exchange is needed, this test determines whether the MPS or LPS for context—index S is decoded. Note that the LPS for
`context—index S is given by 1 — MPS(S).
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 266/714
`
`

`
`‘-...2’
`
`'
`
`~
`
`lIEC10918-1:1993(E)
`
`the
`When a renormalization is needed, the MPS/LPS conditional exchange may also be needed. For the LPS path,
`conditional exchange procedure is shown in Figure D.17. Note that the probability estimation in the decoder is identical
`to the probability estimation in the encoder (Figures D.5 and D.6).
`
`A < X’8000’
`
`D = Cond_M PS_exchange(S)
`Renorm_d
`
`D = Cond_LPS_exchange(S)
`Renorm_d
`
`T|SO1160-93Id054
`
`Figure D.16 — Decode(S) procedure
`
`For the MPS path of the decoder the conditional exchange procedure is given in Figure D.18.
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 267/714
`
`

`
`ISO/IEC 10918-1 : 1993(E)
`
`Cond_LPS_
`exchange(S)
`
`D =1 — MPS(S)
`Cx = Cx -A
`A = Qe(S)
`
`Estimate_Qe(S)_
`after_MPS
`
`Estimate_Qe(S)_
`after_LPS
`
`T1SO1170-93/dD55
`
`Figure D.17 — Decoder LPS path conditional exchange procedure
`
`Cond_MPS_
`exchange(S)
`
`D = MPS(S)
`
`Estimate_Qe(S)_
`after_LPS
`
`Es1imate_Qe(S)_
`after_MPS
`
`TlS011B0—93/d056
`
`Figure D.18 — Decoder MPS path conditional exchange procedure
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 268/714
`
`

`
`D.2.5
`
`Probability estimation in the decoder
`
`The procedures defined for obtaining a new LPS probability estimate in the encoder are also used in the decoder.
`
`/IEC 10918-1 : l993(E)
`
`D.2.6
`
`Renormalization in the decoder
`
`The Renorm_d procedure for the decoder renormalization is shown in Figure D.l9. CT is a counter which keeps track of
`the number of compressed bits in the C-low section of the C—register. When CT is zero, a new byte is inserted into C-low
`by the procedure Byte_in and CT is reset to 8.
`
`Both the probabilitylinterval register A and the code register C are shifted, one bit at a time, until A is no longer less than
`X’ 8000’.
`
`A=SLLA1
`C=SLLC1
`CT=CT—1
`
`A < X’8000’
`?
`
`No
`
`T|SO1190-93Id057
`
`Figure D.19 — Decoder renormalization procedure
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 269/714
`
`

`
`ISOIIEC 10913-1 : 19930:)
`
`tV
`
`\
`
`The Byte_in procedure used in Renorm_d is shown in Figure D.20. This procedure fetches one byte of data,
`compensating for the stuffed zero byte which follows any X’FF’ byte. It also detects the marker which must follow the
`entropy-coded segment. The C-register in this procedure is the concatenation of the Cx and C-low registers. For simplicity
`of exposition, the buffer holding the entropy-coded segment is assumed to be large enough to contain the entire segment.
`
`B is the byte pointed to by the entropy-coded segment pointer BP. BP is first incremented. If the new value of B is not a
`X’FF’, it is inserted into the high order 8 bits of C-low.
`
`Unsluff_0
`
`C = C + SLL B 8
`
`'|'lSO12DO-93/E1058
`
`Figure D.20 — Byte_in procedure for decoder
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 270/714
`
`

`
`The Unstuff_0 procedure is shown in Figure D.21. If the new value of B is X’FF’, BP is incremented to point to the next
`byte and this next B is tested to see if it is zero. Ifpso, B contains a stuffed byte which must be skipped. The zero B is
`ignored, and the X’FF’ B value which preceded it is inserted in the C-register.
`
`/IEC 10918-1 : 1993(E)
`
`If the value of B after a X’ FF’ byte is not zero, then a marker has been detected. The marker is interpreted as required and
`the entropy-coded segment pointer is adjusted (“Adjust BP” in Figure D.21) so that O-bytes will be fed to the decoder
`until decoding is comp1ete..One way of accomplishing this is to point BP to the byte preceding the marker which follows
`the entropy—coded segment.
`
`Unstuff_0
`
`.
`_
`C _ C OR X FFO0
`
`.
`
`|nterpret_marker
`Adjust BF,
`
`11501210-93ldO59
`
`Figure D.21 — Unstuff_0 procedure for decoder
`
`CCITT Rec. T.8l (1992 E)
`
`75
`
`HUAWEI EX. 1016 - 271/714
`
`

`
`ISO/IEC 10918-1 : l993(E)
`
`D.2.7
`
`Initialization of the decoder
`
`The Initdec procedure is used to start the arithmetic decoder. The basic steps are shown in Figure D22.
`
`Initdec
`
`Initialize statistics areas
`BP = BPST — 1
`A = X'0000'
`(see Note below)
`C = O
`
`C=SLLC8
`
`C=SLLC8
`GT=O
`
`T|SOi 220-93/S1050
`
`Figure D.22 '— Initialization of the decoder
`
`The estimation tables are defined by Table D.3. The statistics areas are initialized to an MPS sense of O and a Qe index of
`zero as defined by Table D.3. BP, the pointer to the entropy-coded segment, is then initialized to. point to the byte before
`the start of the entropy-coded segment at BPST, and the interval register is set to the same starting value as in the encoder. _
`The first byte of compressed data is fetched and shifted into Cx. The second byte is then fetched and shifted into Cx. The
`count is set to zero, so that a new byte of data will be fetchedby Renorm_d.
`
`the precision of
`in both Initenc and Initdec,
`is initialized to X’10000’
`NOTE — Although the probability interval
`the probability interval register can still be limited to 16 bits. When the precision of the interval register is 16 bits, it is initialized to
`zero.
`
`D.3
`
`Bit ordering within bytes
`
`The arithmetically encoded entropy-coded segment is an integer of variable length. Therefore, the ordering of bytes and
`the bit ordering within bytes is the same as for parameters (see B.1.1 .1).
`-
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 272/714
`
`

`
`Annex E
`
`/IEC 10918-1 : 1993(E)
`
`Encoder and decoder control procedures
`
`(This annex forms an integral part of this Recommendation I International Standard)
`
`This annex describes the encoder and decoder control procedures for the sequential, progressive, and lossless modes of
`operation.
`
`The encoding and decoding control procedures for the hierarchical processes are specified in Annex J.
`
`NOTES
`
`There. is no requirement in this Specification that any encoder or decoder shall implement the procedures in precisely
`1
`the manner specified by the flow charts in this annex. It is necessary only that an encoder or decoder implement the lunction specified
`in this annex. The sole criterion for an encoder or decoder to be considered in compliance with this Specification is that it satisfy the
`requirements given in clause 6 (for encoders) or clause 7 (for decoders), as determined by the compliance tests specified in Part 2.
`
`2
`
`Implementation-specific setup steps are not indicated in this annex and may be necessary.
`
`E.1
`
`Encoder control procedures
`
`E.1.1
`
`Control procedure for encoding an image
`
`The encoder control procedure for encoding an image is shown in Figure E.1.
`
`_ Encode_image
`
`Append SOI marker
`
`Encode__frarne
`
`Append EOI marker
`
`'l1S01230-93/11051
`
`Figure E.1 — Control procedure for encoding an image
`
`CCITT Rec. T.81 (1992 E)
`
`77
`
`HUAWEI EX. 1016 - 273/714
`
`

`
`ISO/[EC 10918-1 : l993(E)
`
`E.1.2
`
`Control procedure for encoding a frame
`
`In all cases where markers are appended to the compressed data, optional X’FF’ fill bytes may precede the marker.
`
`The control procedure for encoding a frame is oriented around the scans in the frame. The frame header is first appended,
`and then the scans are coded. Table specifications and other marker segments may precede the SOF,, marker, as indicated
`by [tables/miscellaneous] in Figure E.2.
`
`Figure E.2 shows the encoding process frame control procedure.
`
`Encode_frame
`
`[Append tables/miscellaneous]
`Append SOF,. marker and rest
`of frame header
`
`Encode_scan
`
`|
`
`[Append DNL
`segment]
`
`More scans
`?
`
`T|S01240-93/dO62
`
`Figure E.2 — Control procedure for encoding a frame
`
`E.1.3
`
`Control procedure for encoding a scan
`
`A scan consists of a single pass through the data of each component in the scan. Table specifications and other marker
`segments may precede the SOS marker. If more than one component is coded in the scan, the data are interleaved. If
`restart is enabled, the data are segmented into restart intervals. Ifrestart is enabled, a RSTm marker is placed in the coded
`data between restart intervals. If restart is disabled, the control procedure is the same, except that the ‘entire scan contains a
`single restart interval. The compressed image data generat