i
`‘
`x;
`
`'
`
`/IEC 10918-1 : 1993(E)
`
`The subdivision of the current probability intervzd 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 MP5 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’10000' 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.
`
`Carryvover into 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:
`
`
`
`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 MP8 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 MP8 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.
`
`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 MP8 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.
`
`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 MP5 provide, by means of a table-based probability estimation
`state machine, a direct estimate of the probabilities.
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS 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 D2 — Encoder register connections
`
`C-register
`
`A-register
`
`OOOOCbbb,
`
`00000000,
`
`bbbbbsss,
`
`00000000,
`
`xxxxxxxx,
`
`anaaaaaa,
`
`xxxxxxxx
`
`aaaaaaaa
`
`u a:
`
`x bits are the
`The “3.” bits are the fractional bits in the A-register (the current probability interval value) and the
`fractional bits in the code register. The “5” 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).
`
`CCITT Rec. T.8'1 (1992 E)
`
`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_l(S) and Code_O(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_l(S) and Code_O(S) are shown in Figures DI and D2. The Code_l (S) and Code_O(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_l(S)
`
`No
`
`Yes
`
`I COde11801800-93/d039
`
`Figure D.1 — Code_l(S) procedure
`
`OLYMPUS EX. 1016 - 252/714
`
`

`

`'~.._/
`)IIEC 10918-1 : 1993(E)
`
`No
`
`Yes
`
`I cedeTlSDi DGD-SWdOISO
`
`Figure D.2 — Code_0(S) procedure
`
`
`
`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 (Renorrn_e) are required after the coding of the symbol (see
`Figure D.4).
`
`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(lndex(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) tovthe 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 D3).
`
`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.
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS EX. 1016 - 253/714
`
`

`

`ISO/[EC 10918-1 : 199302)
`
`Code_LPS(S)
`
`CCITT Rec. T.81 (1992 E)
`
`Figure D.3 - Code_LPS(S) procedure with conditional MPS/LPS exchange
`
`Estimate_Qe(S)_after_LPS
`Renorm_e
`
`TISOi MOSS/d0“
`
`OLYMPUS EX. 1016 - 254/714
`
`

`

`[IEC 10918-1: 1993(E)
`
`Code_MPS(S)
`
`Estimate_Qe(S)_afler_MPS
`Renorm_e
`
`T1501050-93/d042
`
`Figure D.4 - Code_MPS(S) procedure with conditional MPS/LPS exchange
`
`
`
`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 MP8
`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 MP8 is changed whenever the entry in the Switch_MPS is one.
`
`D.1.5
`
`Probability estimation in the encoder
`
`D.].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.
`
`The probability estimation state machine is given in Table D.3. Initialization of the arithmetic coder is always with
`an MP8 sense of zero and a Qe index of zero in Table D3.
`
`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’SOOO’).
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS EX. 1016 - 255/714
`
`

`

`
`HOHOOOOHOOOCOODOOb-‘O0CCOOI—OOOOOOOHOOOOCOOOOOOOOOOHOOOOOOO
`OODOOOOOOOOOOOOOOOOOi-IDOOCOCOCO00COCOCOOOODHOOOOOOOOOOOOOH
`
`
`
`
`
`
`
`
`
`Next_ Index
`
`
`
`
`
`X’01A4’
`X'0160'
`X’0125’
`X'00F6’
`X’OOCB’
`X’OOAB’
`X‘OOSF’
`X’5B12’
`X’4D04’
`X’412C’
`X’37D8’
`X’ZFES’
`X’293C’
`X'2379’
`X’ 1EDF’
`X’IAA9’
`X’ 174E’
`X’ 1424'
`X’ 1 19C’
`X’0F6B'
`X’ODSI’
`X'OBB6’
`X'OA40’
`X'5832’
`X’4D1C’
`X’438E’
`X’3BDD’
`X’34EE’
`X’ZEAE’
`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'4COF’
`X’4639’
`X'415E’
`X'5627’
`X’50E7’
`X’4B85’
`X’5597’
`X'504F’
`X’SAIO’
`X’5522’
`X’59EB’
`
`
`
`
`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
`4S
`46
`47
`48
`49
`50
`51
`52
`53
`54
`55
`56
`57
`
`40
`42
`43
`45
`46
`48
`49
`51
`52
`54
`56
`S7
`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
`
`ISO/IEC 10918-1 : 1993(E)
`
`Table D.3 — Qe values and probability estimation state machine
`
`
`
`
`
`
`
`Ommflc‘m-PUJNHOOOONONUIAMNr—O
`
`NH-~_.—»—n—.—.—
`
`NNNUN:—
`
`24
`25
`26
`27
`
`WNN0000
`
`b3 ._‘
`
`AmwmwmumuOWOOQONUI-BWN
`
`#4:»WNH
`##bGUI-A
`##h0004
`'JILIILIINHOU!l)!
`UIUIUIQUI-Ph
`
`X‘5A1D‘
`X’2586'
`X’1114’
`X’OSOB’
`X’03D8’
`X’OlDA’
`X‘OOES'
`X’006F’
`X’OO36'
`X’OOIA'
`X’OOOD’
`X’0006’
`X’0003’
`X’OOOI’
`X’5A7F’
`X'3F25’
`X’ZCFZ’
`X’207C’
`X‘ 17B9’
`X’1182’
`X’OCEF’
`X’09A1’
`X’072F’
`X'055C’
`X’0406’
`X’0303'
`X’0240’
`X’DlBl’
`X’0144'
`X’DOFS’
`X’00B7’
`X’008A’
`X’0068’
`X‘004E’
`X’003B’
`X’OOZC’
`X’SAEI’
`X’484C’
`X’EAOD’
`X’ZEFI’
`X'261F’
`X’ 11:33Y
`X’ 19A8’
`X’ 1518’
`X’1177’
`X’0E74'
`X’OBFB’
`X'09F8’
`X’0861’
`X’07D6’
`X’OSCD'
`X’O4DE’
`X’040F’
`X’0363’
`X’02D4'
`X’025C’
`X’01F8’
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS EX. 1016 - 256/714
`
`

`

`D.1.5.2 Renormalization driven estimation
`
`/IEC 10918-1 : 1993(E)
`
`The change in state in Table D3 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 MP8.
`
`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_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 MP8
`
`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 BS from the column labeled
`Next_Index_MPS, as that is the next index after an MP8 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 lndex(S) becomes the new Qe(S).
`MPS(S) does not change.
`
`
`
`Estimale_Qe(S)_
`after_MPS
`
`I = lndex(S)
`I = Next_Index_MPSU)
`lndex(S) = |
`Qe(S) = Qe_Value(l)
`
`7130106093160“!
`
`Figure D.5 — Probability estimation on MP8 renormalization path
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS EX. 1016 - 257/714
`
`

`

`ISO/[EC 10918-1 : 1993(E)
`
`D.1.S.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 l, the sense of MP8 (S) must be inverted.
`
`Estimate_Qe( )_
`afler_LPS
`
`MPS(S) = 1— MPS(S)
`
`l = Next_|ndex_LPS(I)
`|ndex(S) = |
`Qe(S) = Qe_Va|ue(l)
`
`USOiO70-93/d044
`
`Figure D.6 - Probability estimation on LPS renormalization path
`
`
`
`The Renorm_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. Renorrnalization continues
`until A is no longer less than X’SOOO’.
`
`D.1.6
`
`Renormalization in the encoder
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS EX. 1016 - 258/714
`
`

`

`[IEC 10918-1 : 1993(E)
`
`Flenon'n_e
`
`A=SLLA1
`C=SLL01
`CT=CT—1
`
`A < X’BOOO‘
`?
`
`
`
`
`
`In Figure D.8 BP is the entropy—coded segment pointer and B is the compressed data byte pointed to by BP. T in Bytc_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.
`
`TISOl 080-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.
`
`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)
`
`OLYMPUS EX. 1016 - 259/714
`
`

`

`ISO/[EC 10918-1 : 1993(E)
`
`T=SHLC19
`
`Output~stacked_
`zeros
`
`_
`ST ~ ST + 1
`
`Output_stacked_
`X,FF,S
`
`C = C AND X’7FFFF’
`
`11501090-93/(1046
`
`Figure D.8 — Byte_0ut procedure for encoder
`
`
`
`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.
`
`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’FFOl’
`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.
`
`CCITT Rec. T31 (1992 E)
`
`OLYMPUS EX. 1016 - 260/714
`
`

`

`‘Q
`'33/IEC 10918-1 : 1993(E)
`
`The proaedures used by Byte_out are defined in Figures D.9 through D.] 1.
`
`Output_stacked_
`zeros
`
`If a carry 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’.
`
`CCITT Rec. T.81 (1992 E)
`
`11501 310-93/d047
`
`Figure D.9 —- Output_stacked_zeros procedure for encoder
`
`Output_stacked_
`X‘FF' s
`
`TlSO1100-93/d048
`
`Figure D.1l) — 0utput_stacked_X’FF’s procedure for encoder
`
`OLYMPUS EX. 1016 - 261/714
`
`

`

`ISO/IEC 10918-1 : 1993(E)
`
`TISOi HOSE/c1049
`
`Figure D.11 — Stuff_0 procedure for encoder
`
`
`
`Initialize statistics areas
`ST = 0
`A = X’10000'
`(see Note below)
`C = 0
`CT = 11
`BP = BPST — 1
`
`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.
`
`initenc
`
`TISD1120-SE/d050
`
`Figure D.12 — Initialization of the encoder
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS EX. 1016 - 262/714
`
`

`

`c/
`
`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 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 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.
`
`10918-1 : 1993(E)
`The probability estimation tables are defined by Table D.3. The statistics areas are initialized to an MP5 sense of 0 and a
`Qe index of zero as defined by Table D3. The stack count (ST) is cleared, the code register (C) is cleared, and the interval
`register is set to X’lOOOO’. The counter (CT) is set to 11. reflecting the fact that when A is initialized to X’IOOOO’ three
`spacer bits plus eight output bits in C must be filled before the first byte is removed. Note that HP 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) = 0 and Index(S) = 0.
`
`CCITT Rec. T.81 (1992 E)
`
`Clear_final_bits
`
`C=SLLCCT
`
`C=SLLCB
`
`Byte_out
`Discard_tinaLzeros
`
`TISO1 130-93/d051
`
`Figure D.13 - Flush procedure
`
`OLYMPUS EX. 1016 - 263/714
`
`

`

`ISO/IEC 10918-1 : 1993(E)
`
`_,
`
`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 aDNL marker is
`used, the decoder will intercept it in time to correctly terminate the decoding procedure.
`
`
`
`Clear_final_bits
`
`T=C+A—1
`T = T AND
`X’FFFFOOOO’
`
`T = T + X’BOOO'
`
`11301140433/d052
`
`Figure D.l4 — Clear_final_bits procedure in Flush
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS EX. 1016 - 264/714
`
`

`

`IIEC 10918-1 : 1993(E)
`
`Discard_final_zeros
`
`BP<BPST
`’7
`
`T1501 150-93/d053
`
`Figure D.15 — Discard_l'mal_zeros procedure in Flush
`
`
`
`The “Decode(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.
`
`D.2
`
`Arithmetic decoding procedures
`
`Two arithmetic decoding procedures are used for arithmetic decoding (see Table D.4).
`
`Table D.4 - Procedures for binary arithmetic decoding
`
`Procedure
`
`Decode a binary decision with context-index S
`Initialize the decoder
`
`CCITT Rec. T31 (1992 E)
`
`OLYMPUS 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.
`
`
`
`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 MP3 or LPS for context—index S is decoded. Note that the LPS for
`context-index S is given by 1 — MPS(S).
`
`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 D5 — 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
`Glow 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
`
`CCITT Rec. T31 (1992 E)
`
`OLYMPUS EX. 1016 - 266/714
`
`

`

`t 35;;
`kw»!
`
`:5.
`\N/
`
`IIEC 10918-1 : 1993(E)
`
`A < X'BOOO'
`
`D = Cond_M PS_exchange(S)
`Renorm_d
`
`D = MPS(S)
`
`D = Cond_LPS_exchange(S)
`Flenorm_d
`
`TISO11EO-93Id054
`
`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 D6).
`
`
`
`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)
`
`OLYMPUS EX. 1016 - 267/714
`
`

`

`ISO/IEC 10918-1 : 1993(E)
`
`Cond_LPS_
`exchange(S)
`
`D = MPS(S)
`Cx=Cx-A
`A = Qe(S)
`
`D =1 — MPS(S)
`Cx=Cx—A
`A = Qe(S)
`
`Estimate_Qe(S)_
`after_MPS
`
`Estimale_Qe(S)_
`after_LPS
`
`
`
`Figure D.18 — Decoder MPS path conditional exchange procedure
`
`T501 170-93/d055
`
`Figure D.17 — Decoder LPS path conditional exchange procedure
`
`Cond_MPS_
`exchange(S)
`
`D=1—MPS(S)
`
`D=MPS(S)
`
`Estimate__Qe(S)_
`afler_LPS
`
`Estimate_Qe(S)_
`afier_MPS
`
`TISOI 180—93/d056
`
`CCITT Rec. T81 (1992 E)
`
`OLYMPUS 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.
`
`IIEC 10918-1 :1993(E)
`
`D.2.6
`
`Renormalization in the decoder
`
`Both the probability'interval register A and the code register C are shifted, one bit at a time, until A is no longer less than
`X’ 8000’.
`
`The Renorm_d procedure for the decoder renormalization is shown in Figure D.19. 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.
`
`
`
`A=SLLA1
`C=SLLC1
`CT=CT—1
`
`TlSO1 190-93Id057
`
`Figure D.19 — Decoder renormalization procedure
`
`CCITT Rec. T.81 (1992 E)
`
`73
`
`OLYMPUS EX. 1016 - 269/714
`
`

`

`ISO/IEC 10918-1 : 1993(E)
`
`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.
`
`UnstuiLO
`
`C = C + SLL B 8
`
`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.
`
`
`
`TlSO1200-93lt1058
`
`Figure D.le — Byte_in procedure for decoder
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS EX. 1016 - 270/714
`
`

`

`The Unstuff_0 procedure is shown in Figure D.21. Ifthe 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. Ifso, 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.
`
`t
`_
`C — 0 OR X FFOO
`
`.
`
`|nterpret_marker
`Adjust BP
`
`1150121 0-93/d059
`
`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 D21) so that 0-bytes will be fed to the decoder
`until decoding is completc.,0ne way of accomplishing this is to point BP to the byte preceding the marker which follows
`the entropy-coded segment.
`
`75
`
`Figure D.21 — Unstuff_0 procedure for decoder
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS EX. 1016 - 271/714
`
`

`

`ISO/IEC 10918-1 : 1993(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 D.22.
`
`Initialize statistics areas
`BF = BPST - 1
`A = X'OOOO’
`(see Note below)
`C = O
`
`C=SLLC8
`
`C=SLLCB
`GT=0
`
`TlSOiZZD—SSMDGO
`
`Figure D.22 — Initialization of the decoder
`
`CCITT Rec. T.81 (1992 E)
`
`The estimation tables are defined by Table D3. The statistics areas are initialized to an MP3 sense of O and a Qe index of
`zero as defined by Table D3. BP, the pointer to the entropyfeoded Segment, is then initialized topoint 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 fetched by Renorm_d.
`
`the precision of
`in both Initenc and Initdec,
`initialized to X’IOOOO’
`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 bits, it is initialized to
`ZBl'Or
`
`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).
`-
`
`OLYMPUS 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 | 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
`
`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.
`
`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 flmction 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.
`
`77
`
`Encode_image
`
`Append SOI marker
`
`Encodejrarne
`
`Append EOI marker
`
`neo1230-ea/d061
`
`Figure E.1 — Control procedure for encoding an image
`
`CCITT Rec. T31 (1992 E)
`
`OLYMPUS EX. 1016 - 273/714
`
`

`

`ISO/[EC 10918-1 : 1993(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 SOFn marker, as indicated
`by [tables/miscellaneous] in Figure E2.
`
`Figure E.2 shows the encoding process frame control procedure.
`
`CCITT Rec. T31 (1992 E)
`
`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 generated by a scan is always followed by a marker, either the E01
`marker or the marker of the next marker segment.
`
`Encode_fram