`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 assignmentof the sub-intervals
`such that the MPSis 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 codedat a cost of muchless 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 knownto 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 5. 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 proceduresuse fixed precisioninteger 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’ < A < X’10000" by doubling it whenever its integer value falls below X’8000’. This is equivalent to
`keeping A in the decimal range 0.75 < 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-over into the entropy-coded segmentis 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
`markersin the entropy-coded segment.
`
`Keeping A in the range 0.75 < 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 valueof A is of orderunity, these can be approximated by
`
`Qe(S)
`A— Qe(S)
`
`Probability sub-interval for the LPS;
`Probability sub-interval for the MPS.
`
`Wheneverthe LPSis coded, the value of A — Qe(S)is addedto 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 Ree. T.81 (1992 E)
`
`55
`
`HUAWEI EX. 1016 - 251/714
`
`HUAWEI EX. 1016 - 251/714
`
`
`
`ISO/IEC 10918-1 : 1993(E)
`
`D.1.3
`
`Encoder code register conventions
`
`
`
`The flow charts in this annex assumethe register structures for the encoder as shown in Table D.2.
`
`Table D.2 - Encoderregister connections
`
`aaaaaaaa
`
`C-register
`
`A-register
`
`0000cbbb,
`
`00000000,
`
`bbbbbsss,
`
`00000000,
`
`XXXXXXKX,
`
`aaaaaaaa,
`
`XXXXXXXXK
`
`The “a” bits are the fractional bits in the A-register (the current probability interval value) and the “x” bits are the
`fractionalbits 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. Exceptat the timeofinitialization, 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-overand 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 1-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 $ is determined by thestatistical model andis, 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.
`
`No
`
`Code_LPS(S)
`
` Code_1(S)
`
`Yes
`
`Code_MPS(S)
`
`TISO1800-93/d039
`
`Figure D.1 - Code_1(S) procedure
`
`56
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 252/714
`
`HUAWEI EX. 1016 - 252/714
`
`
`
`
`
`
`
`: 1993(E)
`
`Code_0(S)
`
`
`
`Code_LPS(S)
`Code_MPS(8)
`
`
`TISO1030-93/d040
`
`|
`
`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
`symbolor 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(S) procedure normally consists of the addition of the MPS sub-interval A — Qe(S) tothe 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).
`
`CCITTRec. T.81 (1992 E)
`
`57
`
`HUAWEI EX. 1016 - 253/714
`
`HUAWEI EX. 1016 - 253/714
`
`
`
`ISO/IEC 10918-1 : 1993(E)
`
`
`
`Code_LPS(S)
`
`Renorm_e
`
` Estimate_Qe(S)_after_LPS
`
`TISO1040-99/d041
`
`Figure D.3 - Code_LPS(S) procedure with conditional MPS/LPS exchange
`
`58
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 254/714
`
`HUAWEI EX. 1016 - 254/714
`
`
`
`WY
`
`Code_MPS(S)
`
`Estimate_Qe(S)_after_MPS
`
`Renorm_e
`
`" WIEC 10918-1 : 1993(E)
`
`
`
`
`
`TISO1050-93/d042
`
`Figure D.4 - Code_MPS(S)procedure with conditional MPS/LPS exchange
`
`D.1.5
`
`Probability estimation in the encoder
`
`D.1.5.1 Probability estimation state machine
`
`The probability estimation state machine consists of a numberof 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_LPSgives 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 MPSare kept for each context-index S. The sense
`of the MPS is changed wheneverthe entry in the Switch_MPSis one.
`
`The probability estimation state machine is given in Table D.3. Initialization of the arithmetic coder is always with
`an MPSsenseof zero and a Qeindex of zero in Table D.3.
`
`The Qe vaiues listed in Table D.3 are expressed as hexadecimal integers. To approximately convert the 15-bit integer
`representation of Qe to a decimalprobability, divide the Qe values by (4/3) x (X’ 8000’).
`
`CCITT Rec. T.81 (1992 E)
`
`59
`
`HUAWEI EX. 1016 - 255/714
`
`HUAWEI EX. 1016 - 255/714
`
`
`
` ISO/IEC 10918-1 ; 1993(E)
`
`Table D.3 — Qe values and probability estimation state machine
`
`
`Index Switch|IndexQe Qe Next_ Index
`
`
`
`
`
`_Value _LPS|_MPS MPS Value
`
`
`
`
`
`
`
`
`
`0
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`13
`14
`15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`26
`27
`28
`29
`30
`31
`32
`33
`34
`35
`36
`37
`38
`39
`40
`41
`42
`43
`44
`45
`46
`47
`48
`49
`50
`51
`52
`53
`54
`55
`56
`
`
`
`X’SAID’
`X’2586’
`XxX1114
`X’080B’
`X’03D8"
`X’01LDA’
`X°00ES’
`X°006F”
`X’0036’
`X’001A'
`X’000D’
`X’0006"
`X’0003’
`X’0001’
`X’5A7TF’
`X’3F25°
`X?2CF2’
`X’207C’
`X’17B9’
`X’1182’
`X’OCEF’
`X’O9AL’
`X’072P
`&’055C’
`x’ 0406’
`X’0303'
`X’0240°
`X’OIBI’
`X’0144’
`X’ 00F5’
`X’00B7’
`X’008A’
`X’0068’
`X’004F’
`X’003B’
`X'002C’
`X’5AE1’
`X’484C’
`X°3A0D’
`X’2EF1’
`X’261F
`X’1F33’
`X’19A8’
`X71518’
`X°1177’
`X’0E74’
`X’0BFB’
`X’09F8’
`X’0861’
`X’0706’
`X’05CD’
`X’04DE’
`X°040F’
`X’0363’
`X’02D4’
`X’025C’
`X’01F8’
`
`
`
`1
`14
`16
`18
`20
`23
`25
`28
`30
`33
`35
`9
`10
`12
`15
`36
`38
`39
`40
`42
`43
`45
`46
`48
`49
`51
`52
`54
`56
`57
`59
`60
`62
`63
`32
`33
`37
`64
`65
`67
`68
`69
`70
`72
`73
`74
`75
`77
`78
`79
`48
`50
`50
`51
`52
`53
`54
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`ll
`12
`13
`13
`15
`16
`17
`18
`19
`20
`21
`22
`23
`24
`25
`26
`27
`28
`29
`30
`31
`32
`33
`34
`35
`9
`37
`38
`39
`40
`41
`42
`43
`44
`45
`46
`47
`48
`49
`50
`51
`52
`53
`54
`55
`56
`57
`
`1
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`1
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`1
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`
`57
`58
`59
`60
`61
`62
`63
`64
`65
`66
`67
`68
`69
`70
`71
`72
`73
`74
`75
`76
`TT
`78
`719
`80
`81
`82
`83
`84
`85
`86
`87
`88
`89
`90
`91
`92
`93
`94
`95
`96
`o7
`98
`99
`100
`101
`102
`103
`104
`105
`106
`107
`108
`109
`110
`111]
`112
`
`XO1AY
`X’0160’
`0125’
`X’00F6’
`X’00CB’
`X’00AB’
`X’008F
`X’5B12’
`X’4D04"
`X’°412C’
`&’37D8"
`X?2FE8’
`X°293C’
`X°2379"
`X’1EDF’
`X’1AA9’
`X’174E"
`xX’ 1424"
`xX119C’
`X’0F6B’
`X’ODS!’
`X’0BB6’
`X’0A40’
`X?5832’
`xX’4D1IC’
`X’438E’
`X’3BDD'
`X734EE’
`X’ 2EAE’”
`X°299A’
`2516
`X’5570°
`X’4ACAD’
`X’44D9’
`X"3E22’
`X'3824"
`X’32B4’
`X’2E17’
`X’56A8’
`K’4F46°
`X’47ES’
`X’41CP
`X'3C3D’
`X’375E’
`XK’ 5231’
`X’4COF’
`X°4639°
`K’415E
`X’5627’
`X’50E7’
`X’4B85’
`5597’
`K’504F
`X’5A10’
`K’ 5522’
`X’59EB’
`
`55
`56
`57
`58
`59
`61
`61
`65
`80
`81
`82
`83
`84
`86
`87
`87
`72
`72
`74
`74
`75
`TI
`Ti
`80
`88
`89
`90
`91
`92
`93
`86
`88
`95
`96
`97
`99
`99
`93
`95
`101
`102
`103
`104
`99
`105
`106
`107
`103
`105
`108
`109
`110
`111
`110
`112
`112
`
`58
`59
`60
`61
`62
`63
`32
`65
`66
`67
`68
`69
`70
`71
`72
`73
`74
`75
`76
`77
`78
`79
`48
`81
`82
`83
`84
`85
`86
`87
`71
`89
`90
`91
`92
`93
`94
`86
`96
`97
`98
`99
`100
`93
`102
`103
`104
`99
`106
`107
`103
`109
`107
`111
`109
`141
`
`-
`
`0
`0
`0
`0
`0
`0
`0
`1
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`1
`0
`0
`0}
`0
`0
`0
`0
`1
`0
`0
`0
`0
`0
`0
`I
`0
`0
`0
`0
`0
`0
`0
`0
`0
`1
`0
`0
`0
`0
`1
`0
`1
`
`=
`
`60
`
`CCITTRec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 256/714
`
`HUAWEI EX. 1016 - 256/714
`
`
`
`D.1.5.2. Renormalization driven estimation
`
` “TEC 10918-1 : 1993(E)
`
`The changein 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 wheneverthe 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 renormalization is required, Next_Index_MPS gives the new index for the LPS probability estimate. If
`Switch_MPSis 1 for the old index, the MPS symbol sense mustbe 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
`Index(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
`
`Qe(S) = Qe_Value(l) TISO1060-99/d043
`
`1 = index(S)
`| = Next_Index_MPS(1)
`Index(S) =1
`
`Figure D.5 — Probability estimation on MPS renormalization path
`
`CCITTRee. T.81 (1992 E)
`
`61
`
`HUAWEI EX. 1016 - 257/714
`
`HUAWEI EX. 1016 - 257/714
`
`
`
`ISO/IEC 10918-1 : 1993(E)
`
`D.1.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(D)is 1, the sense of MPS(S) mustbe inverted.
`
` Estimate_Qe(S)_
`
`after_LPS
` MPS(S) = 1 — MPS(S)
`Qa(S) = Qe_Valua(l)
`
` I = Next_Index_LPS(|)
`
`Index(S) = |
`
` 71S01070-03/d044
`
`Figure D.6 — Probability estimation on LPS renormalization path
`
`D.1.6
`
`Renormalization in the encoder
`
`The Renorm_e procedure for the encoder renormalization is shown in Figure D.7. Both the probability interval register A
`and the coderegister C are shifted, one bit at a time. The numberofshifts is counted in the counter CT; when CTis zero,
`a byte of compressed data is removed from C by the procedure Byte_out and CTis reset to 8. Renormalization continues
`until A is no longer less than X’8000’.
`
`62
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 258/714
`
`HUAWEI EX. 1016 - 258/714
`
`
`
`
`
`
`
`: 1993(E)
`
` Renorm_e
`
`
` A=SLLA1
`C=SLLC1
`CT=CT-1
`
`Byte_out
`
`
`
`A<X’8000°
`
`
`
`? TISO1080-9a/d045
`
`Figure D.7 — Encoder renormalization procedure
`
`The Byte_out. procedure used in Renorm_e is shownin 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 BPis the entropy-coded segmentpointer 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 upperlimit for the value of ST is bounded only by the total entropy-coded segmentsize, 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 systemsfor handling the burst of output data which occurs whenthe carry is resolved.
`
`CCITT Rec. T.81 (1992 E)
`
`63
`
`HUAWEI EX. 1016 - 259/714
`
`HUAWEI EX. 1016 - 259/714
`
`
`
`ISO/TEC 10918-1 : 1993(E)
`
`
`
`
`
`
`
`_
`ST=ST+1
`
`Output_stacked_
`X'EF's
`
`T=SRLC19
`
`
`C=CAND X’7FFFF’ TISO1090-93/d046
`
`Output_stacked_
`
`zeros
`
`BP=BP+1
`BP=BP +1
`
`B=T
`
`
`
`
`Figure D.8 — Byte_out procedure for encoder
`
`Whenthestack 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 boundonSTthis 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 ignoredifit is set.
`
`64
`
`CCITT Ree. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 260/714
`
`HUAWEI EX. 1016 - 260/714
`
`
`
`
` (AEC 10918-1 : 1993(E)
`If a carry has not occurred, the output byteis tested to seeif it is X’FF’. If so, the stack count ST is incremented, as the
`output must be delayed until the carry-overis 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’.
`
`The procedures used by Byte_outare defined in Figures D.9 through D.11.
`
`
`Output_stacked_
`zeros
`
`
`
`B=0
`
`ST=ST-1
`
`TISO1810-93/d047
`
`
`Figure D.9 — Output_stacked_zeros procedurefor encoder
`
`
`Output_stacked_
`X'FF’s
`
`BP =BP +1
`
`
`
`
`
`
`TISO1 100-99/d048
`
`Figure D.10 — Output_stacked_X’FF’s procedure for encoder
`
`CCITT Rec. T.81 (1992 E)
`
`65
`
`HUAWEI EX. 1016 - 261/714
`
`HUAWEI EX. 1016 - 261/714
`
`
`
`ISO/IEC 10918-1 : 1993(E)
`
`
`
`B=0 TISO1110-94/d049
`
`BP=BP+1
`
`Figure D.11 — Stuff_0 procedure for encoder
`
`D.1.7
`
`Initialization of the encoder
`
`The Initenc procedureis used to start the arithmetic coder. The basic steps are shown in Figure D.12.
`
`Initenc
`
`BP =BPST-1 TISO1120-93/d050
`
`Initialize statistics areas
`ST=0
`A= X’10000”
`(see Note below)
`c=0
`cT=11
`
`Figure D.12 — Initialization of the encoder
`
`66
`
`CCITTRec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 262/714
`
`HUAWEI EX. 1016 - 262/714
`
`
`
`
`The probability estimation tables are defined by Table D.3. The statistics areas are initialized to an MPS sense of 0 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 whenAis initialized to X’10000’ three
`spacerbits plus eight outputbits in C mustbefilled before the first byte is removed. Note that BPis initialized to pointto
`the byte before the start of the entropy-coded segment (which is at BPST). Notealso that the statistics areas are initialized
`for all values of context-index S to MPS(S) = 0 and Index(S) = 0.
`
`‘O/TEC 10918-1 : 1993(E)
`
`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 registeris 16 bits, it is initialized to
`Zero.
`
`D.1.8
`
`Termination of encoding
`
`The Flush procedure is used to terminate the arithmetic encoding procedures and prepare the entropy-coded segmentfor
`the addition of the X’FF’ prefix of the marker which follows the arithmetically coded data. Figure D.13 showsthis flush
`procedure. Thefirst step in the procedureis to set as many low orderbits 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.
`
`Discard_final_zeros TISO1190-93/d051
`
`Clear_final_bits
`
`C=SLLCCT
`
`Byte_out
`
`Figure D.13 — Flush procedure
`
`CCITT Rec. T.81 (1992 E)
`
`67
`
`HUAWEI EX. 1016 - 263/714
`
`HUAWEI EX. 1016 - 263/714
`
`
`
`
`
`Oo
`(E)
`CY
`
`oe
`ISO/IEC 10918-1 : 1993(E
`for
`Anytrailing 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 markeris
`used, the decoder will intercept it in time to correctly terminate the decoding procedure.
`
`Clear_final_bits
`
`T=C+A-1
`T=TAND
`X’FFFFOO00’
`
`T=T+x'8000" TISO1140-93/d052
`
`Figure D.14 — Clear_final_bits procedure in Flush
`
`68
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 264/714
`
`HUAWEI EX. 1016 - 264/714
`
`
`
`TEC 10918-1 : 1993(E)
`
`
`
`
`
` BP <BPST
`
` Discard_final_zeros
`?
`
`BP=BP+1 ;
`
`
`Yes
`
`TISO1150-93/d053
`
`Figure D.15 — Discard_final_zeros procedure in Flush
`
`D.2
`
`Arithmetic decoding procedures
`
`Twoarithmetic decoding procedures are used for arithmetic decoding (see Table D.4).
`
`The “Decode(S)” procedure decodes the binary decision for a given context-index S and retumsa value ofeither 0 or1. 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 a binary decision with context-index S
` Initdec
`
`Initialize the decoder
`
`
`
`Decode(S)
`
`CCITT Rec. T.81 (1992 E)
`
`69
`
`HUAWEI EX. 1016 - 265/714
`
`HUAWEI EX. 1016 - 265/714
`
`
`
`ISO/TEC 10918-1 : 1993(E)
`
`
`
`D.2.1_—Binary arithmetic decoding principles
`
`Theprobability interval subdivision and sub-interval ordering defined for the arithmetic encoding procedures also apply to
`the arithmetic decoding procedures.
`
`Sincethe 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 addedto 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, Whentheinterval sizes are inverted in the decoder, the sense of the symbol decoded
`mustbe 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 addedto the code register, the decodersubtracts from the
`coderegister.
`
`D.2.3.
`
`Decoder code register conventions
`
`The flow charts given in this section assumetheregister structures for the decoder as shown in Table D.5:
`
`Table D.5 — Decoder register conventions
`
`aaaaaaaa
`
`Cx register
`
`C-low
`
`A-register
`
`XXXXXXXX,
`
`bbbbbbbb,
`
`aaaaaaaa,
`
`XXXXXXXX
`
`00000000
`
`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 onebinary decision at a time. After decoding the decision, the decoder subtracts any amountfrom
`the code register that the encoder added. The amountleft 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 shownin Figure D.16 the coderegister 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).
`
`70
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 266/714
`
`HUAWEI EX. 1016 - 266/714
`
`
`
`
`
`
`“S)YTEC 10918-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).
`
`(S)
`
`A < X’8000”
`
`
`D = Cond_MPS_exchange(S)
`Renorm_d
`
`D=MPS(S)
`
`
`
`
`
`
`
`
`
`
`D = Cond_LPS_exchange(S)
`Renorm_d
`
`TISO1160-93/d054
`
`Figure D.16 — Decode(S) procedure
`
`For the MPS path of the decoder the conditional exchange procedure is given in Figure D.18.
`
`CCITTRec. T.81 (1992 E)
`
`71
`
`HUAWEI EX. 1016 - 267/714
`
`HUAWEI EX. 1016 - 267/714
`
`
`
`
`
`ISO/IEC 10918-1 : 1993(E)
`
`
`
`
`
`Cond_LPS_
`exchange(S)
`
`
`
`
`
`
`D=1-—MPS(S)
`
`D =MPS(s)
`Cx=Cx-A
`Cx=Cx-A
`
`A=Qe(8)
`A= Qe(S)
`
`
`
`
`
`
`Estimate_Qe(S)_
`Estimate_Qe(S)_
`after_LPS
`after_MPS
`
`
`
`Return D
`
`TISO1170-93/d055
`
`Figure D.17 - Decoder LPS path conditional exchange procedure
`
`
`
`Cond_MPS_
`exchange(S)
`
`
`
`
`
`D=1—MPS(S)
`
`D =MPS(S)
`
`after_LPS
`Estimate_Qe(S)_
`after_MPS Estimate_Qe(S)_
`
`
`TISO1 180-93/d056
`
`Figure D.18 - Decoder MPS path conditional exchange procedure
`
`72
`
`CCITT Rec. T.81 (1992 E)
`
`HUAWEI EX . 1016 - 268/714
`
`HUAWEI EX. 1016 - 268/714
`
`
`
`
`ae
`
`
`
`WIEC 10918-1 : 1993(E)
`
`D.2.5
`
`Probability estimation in the decoder
`
`The procedures defined for obtaining a new LPS probability estimate in the encoderare also used in the decoder.
`
`D.2.6
`
`Renormalization in the decoder
`
`The Renorm_d procedure for the decoder renormalization is shown in Figure D.19. CT is a counter which keeps track of
`the numberof compressed bits in the C-low section ofthe C-register. When CTis zero, a new byte is inserted into C-low
`by the procedure Byte_in and CTis reset to 8.
`
`Both the probabilityinterval register A and the coderegister C are shifted, one bit at a time, until A is no longerless than
`X’8000’.
`
`Renorm_d
`
`A <X’8000’
`?
`
`
`
`TISO1190-93/d057
`
`Figure D.19 — Decoder renormalization procedure
`
`CCITT Rec. T.81 (1992 E)
`
`73
`
`HUAWEI EX. 1016 - 269/714
`
`HUAWEI EX. 1016 - 269/714
`
`
`
`‘@)
`ISO/IEC 10918-1 : 1993(E)
`é
`
`co
`\
`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 procedureis 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 enoughto contain the entire segment.
`
`B is the byte pointed to by the entropy-coded segment pointer BP. BPis 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.
`
`BP = BP +1
`
`
`
`
`
` C=C+SiLB8
` Unstuff_O
`
`TISO1200-99/d058
`
`Figure D.20 — Byte_in procedure for decoder
`
`74
`
`CCITT Ree. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 270/714
`
`HUAWEI EX. 1016 - 270/714
`
`
`
` Gp (TEC 10918-1 : 1993(E)
`
`The Unstuff_0 procedure is shownin 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. If so, B contains a stuffed byte which must be skipped. The zero B is
`ignored, and the X’FF’ B value which precededit is inserted in the C-register.
`
`If the value of B after a-X’FF’ byte is not zero, then a marker has been detected. The markeris interpreted as required and
`the entropy-coded segment pointer is adjusted (“Adjust BP” in Figure D.21) so that 0-bytes will be fed to the decoder
`until decoding is complete.One way of accomplishingthis is to point BP to the byte preceding the marker which follows
`the entropy-coded segment.
`
`Unstuff_O
`
`
`
`
`BP =BP+1
`
`
`
`
`Adjust BP
` C=C OR X’FFQ0’
`
`Interpret_marker
`
`TISO1210-93/d059
`
`Figure D.21 ~ Unstuff_0 procedure for decoder
`
`CCITTRec. T.81 (1992 E)
`
`75
`
`HUAWEI EX. 1016 - 271/714
`
`HUAWEI EX. 1016 - 271/714
`
`
`
`
`
`
`
`
`ISO/TEC 10918-1 : 1993(E)
`
`D.2.7
`
`Initialization of the decoder
`
`
`
`The Initdec procedureis used to start the arithmetic decoder. The basic steps are shownin Figure D.22.
`
`
`Initdec
`
`
`Initialize statistics areas
`
`BP =BPST-—1
`
`A=X'0000'
`(see Note below)
`G=0
`
` TISO1220-93/d060
`
`Figure D.22 — Initialization of the decoder
`
`The estimation tables are defined by Table D.3. Thestatistics areas are initialized to an MPS sense of 0 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, andtheinterval register is set to the same starting value as in the encoder. _
`Thefirst byte of compressed data is fetched and shifted into Cx. The second byte is then fetched and shifted into Cx. The
`countis set to zero, so that a new byte of data will be fetched by 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).
`
`716
`
`CCITTRee. T.81 (1992 E)
`
`HUAWEI EX. 1016 - 272/714
`
`HUAWEI EX. 1016 - 272/714
`
`
`
`
`
`Annex E
`
`(2p /TEC 10918-1 : 1993(E)
`
`Encoderand decodercontrol procedures
`
`(This annex formsan integral part of this Recommendation| 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 proceduresfor the hierarchical processes are specified in Annex J.
`
`NOTES
`
`There.is no requirementin this Specification that any encoder or decoder shall implement the procedures in precisely
`1
`the mannerspecified by the flow charts in this annex. It is necessary only that an. encoder or decoder implementthe function specified
`in this annex. Thesole 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 compliancetests specified in P