`
`
` OME10918-1 : 1993(E)
`rd
`
`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 MPSsub-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 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 proceduresuse fixed precision integer arithmetic and an integer representation offractional values in which
`78000’ 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 procedureis 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
`markers in 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 value ofA 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 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 theinterval 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 avoidthis 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.
`
`Whenevera 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)
`
`55
`
`OLYMPUS EX.1016 - 251/714
`
`OLYMPUS EX. 1016 - 251/714
`
`

`

`ISO/IEC 10918-1 : 1993(E)
`
`D.1.3.
`
`Encoder coderegister conventions
`
`
`
`The flow charts in this annex assume the register structures for the encoder as shownin Table D.2.
`
`Table D.2 — Encoderregister connections
`
`aaaaaaaa
`
`C-register
`
`A-register
`
`0000cbbb,
`
`00000000,
`
`bbbbbsss,
`
`00000000,
`
`XXXXXXXX,
`
`aaaaaaaa,
`
`XXXXXXXK
`
`fray
`“x” bits are the
`The “a” bits are the fractional bits in the A-register (the current probability interval value) and 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 time ofinitialization, 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 describedin 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 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(8)
`Code_LPS(S)
`
`|
`
`Code_MPS(S)
`
`|
`
`TISO1800-93/d039
`
`Figure D.1 - Code_1(S) procedure
`
`56
`
`CCITTRee. T.81 (1992 E)
`
`OLYMPUS EX.1016 - 252/714
`
`OLYMPUS EX. 1016 - 252/714
`
`

`

`
`
` “MTEC 10918-1 : 1993(E)
`NY
`
`
`71801 030-93/d040
`
`Cede_LPS(S)
`CGode_MPS(S)
`
`
`|
`
`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
`symbolorthe 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 MPSsub-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 occurunless 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 Ree. T.81 (1992 E)
`
`37
`
`OLYMPUS EX.1016 - 253/714
`
`OLYMPUS EX. 1016 - 253/714
`
`

`

`ISO/IEC 10918-1 : 1993(E)
`
`
`
`
`
`Code_LPS(S)
`
`
`
`
`
`
`
`
`C=C+a
`
`A=Qe(S)
`
`
`
`Estimate_Qe(S)_after_LPS
`Renorm_e
`
`TISO1040-93/d041
`
`Figure D.3 - Code_LPS(S) procedure with conditional MPS/LPS exchange
`
`58
`
`CCITTRec. T.81 (1992 E)
`
`OLYMPUS EX.1016 - 254/714
`
`OLYMPUS EX. 1016 - 254/714
`
`

`

`Code_MPS(S)
`
`
`
`
`A=A-Qe(S)
`
`A < X8000’
`?
`
`
`
`
`Renorm_e
`
`: 1993(E)
`
`Estimate_Qe(S)_after_MPS
`
`TISO1050-93/d042
`
`
`Figure D.4 - Code_MPS(S)procedurewith 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 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
`Qevalue and two Next_Index values. The Next_Index_MPSgives 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 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 Qe indexof 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 decimalprobability, divide the Qe values by (4/3) x (X’8000”).
`
`CCITT Rec. T.81 (1992 E)
`
`59
`
`OLYMPUS EX.1016 - 255/714
`
`OLYMPUS EX. 1016 - 255/714
`
`

`

`ISO/TEC 10918-1 : 1993(E)
`
`
`Table D.3 - Qe values and probability estimation state machine
`
`
`
`Next_Index
`
`
`
`
`
`
`
`ecoceceocoeococesoocococoScorcoceseooooSsOoCOoOscCOCOCOOOCOHSceCOMeOSCSoOCOOOH
`
`
`
`
`
`
`
`Index
`
`0
`I
`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
`4i
`42
`43
`44
`45
`46
`47
`48
`49
`50
`51
`52
`53
`54
`55
`56
`
`
`
`
`
`SAID’
`X’2586"
`X14
`X’080B’
`X’03D8’
`X°01DA’
`X’00ES5’
`X’006F”
`X’ 0036"
`X’001A’
`X’000D’
`x’0006°
`X’0003”
`X’°0001"*
`X’5A7P’
`X’3F25°
`X’2CF2’
`X’207C’
`K’17B9"
`X’ 1182’
`X’0CEF”
`X’09AL’
`X’072F”
`X’055C’
`X’0406’
`X’ 0303’
`&’0240’
`X’0IBL’
`X’0144’
`X’00FS”
`X’00B7’
`X’008A’
`X’ 0068’
`X'004E”
`X’003B’
`X’002C’
`X’SAEL’
`X’484C’
`X°3A0D’
`X’2EF1’
`X’261FP’
`X77 1833’
`K’19A8”
`X’1518’
`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’
`
`10
`12
`15
`36
`38
`39
`40
`42
`43
`45
`46
`48
`49
`31
`52
`54
`56
`57
`59
`60
`62
`63
`32
`33
`37
`64
`65
`67
`68
`69
`70
`72
`73
`74
`15
`77
`78
`79
`48
`50
`50
`51
`52
`53
`54
`
`43
`44
`45
`46
`47
`48
`49
`50
`51
`52
`53
`54
`35
`56
`57
`
`111
`112
`
`
` XOIAY?
`
`X’0160"
`X70125°
`X’00F6’
`X’00CB’
`X’00AB’
`X’008F’
`X’SB12’
`X’4D04’
`X’412C’
`X’37D8”
`X’2FES’
`X’293C’
`X"2379"
`X’1EDF’
`x’ 1AA9"
`X’174E"
`X’1424"
`x11I9C
`X’OF6B’
`X’0D5V
`X'0BB6’
`X’0A40°
`X75832’
`X'4D1C’
`X’438E’
`X°3BDD”"
`X°34EE’
`X°2EAE’
`X’299A’
`X’2516"
`X75570°
`X’4CA9’
`X’44D9"
`X’3E22’
`X73824
`X’32B4’
`X’2E17
`X’56A8"
`X°4F46°
`X’47ES’
`X’41CP
`X°3C3D"
`X’375E’
`X’5231”
`X’4COP’
`"4639"
`X’415E
`X°5627’
`X’50E7
`X’4B85’
`X’5597°
`X’504F
`X’SA10’
`X’5522”
`X’S9EB’
`
`59
`60
`61
`62
`63
`32
`65
`66
`67
`68
`69
`70
`71
`72
`73
`74
`75
`76
`77
`78
`719
`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
`lil
`109
`Vii
`
`56
`57
`58
`59
`61
`61
`65
`80
`81
`82
`83
`84
`86
`87
`87
`72
`72
`74
`74
`75
`77
`V7
`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
`lil
`110
`112
`112
`
`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)
`
`OLYMPUS EX.1016 - 256/714
`
`OLYMPUS EX. 1016 - 256/714
`
`

`

`D.1.5.2 Renormalization driven estimation
`
`
`“IEC 10918-1 : 1993(E)
`
`The changein state in Table D.3 occurs only when the arithmetic coderinterval register is renormalized. This must always
`be doneafter 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 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 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
`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)_
`afterMPS
`
`Qe(S) = Qe_Value(l) 11S01060-93/d043
`
`| = Index(S)
`| = Next_Index_MPS(I}
`Index(S) =|
`
`Figure D.5 - Probability estimation on MPS renormalization path
`
`CCITT Rec. T.81 (1992 E)
`
`61
`
`OLYMPUS EX.1016 - 257/714
`
`OLYMPUS 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()is I, the sense of MPS(S) must be inverted.
`
`
`Estimate_Qe(S}_
`
`
`
`
`
`after_LPS ( = Index(S)
`
`MPS(S) = 1—MPS(S)
`
`
` [ = Next_Index_LPS()
`
`Index(S) = |
`Qa(S) = Qe_Value(l)
`
` 71801070-94/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 code register C are shifted, one bit at a time. The numberofshifts 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 longerless than X’8000’.
`
`62
`
`CCITT Ree. T.81 (1992 E)
`
`OLYMPUS EX.1016 - 258/714
`
`OLYMPUS EX. 1016 - 258/714
`
`

`

`: 1993(E)
`
`Renorm_e
`
`A=SLLA1
`C=SLLC1
`CcT=CT-1
`
`2 TISO1080-99/d045
`
`
`
`Byte_out
`
`A<xX’8000"
`
`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 enoughto 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 boundedonly 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 when thecarry is resolved.
`
`CCITTRec. T.81 (1992 E)
`
`63
`
`OLYMPUS EX.1016 - 259/714
`
`OLYMPUS EX. 1016 - 259/714
`
`

`

`ISO/IEC 10918-1 : 1993(E)
`
`
`
`
`
`
`zeros
`
`B=T
`
`Output_stacked_
`
`BP=BP +1
`B=T
`
`T=SRLC19
`
`
`
`
`_
`ST=ST+1
`
`Output_stacked_
`X'FF’s
`
`BP =BP +1
`
`G=C AND X’7FFFF’
`
`71IS801090-99/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 addedto the final stuffed zero, thereby converting the final X’FFO0O’ 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_O procedure stuffs a zero byte wheneverthe 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 ignoredif it is set.
`
`64
`
`CCITTRee. T.81 (1992 E)
`
`OLYMPUS EX.1016 - 260/714
`
`OLYMPUS EX. 1016 - 260/714
`
`

`

`
`If a carry has not occurred, the output byte is tested to seeifit 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’.
`
` @STEC 10918-1 : 1993(E)
`eo
`
`The procedures used by Byte_outare defined in Figures D.9 through D.11.
`
`
`Output_stacked_
`zeros
`
`
`
`TISO1810-93/d047
`
`Figure D.9 — Output_stacked_zeros procedure for encoder
`
`
`Output_stacked_
`X'FF's
`
`
`
`TISO1 100-93/d048
`
`Figure D.10 -— Output_stacked_X’FF’s procedurefor encoder
`
`CCITT Rec. T.81 (1992 E)
`
`65
`
`OLYMPUS EX.1016 - 261/714
`
`OLYMPUS EX. 1016 - 261/714
`
`

`

`ISO/IEC 10918-1 : 1993(E)
`
`
`
`Stuff_o TISO1 110-99/d049
`
`Figure D.11 — Stuff_0 procedure for encoder
`
`D.17
`
`Initialization of the encoder
`
`The Initenc procedureis usedto start the arithmetic coder. The basic steps are shownin Figure D.12.
`
`initenc
`
`BP =BPST—-1 71S01120-93/d050
`
`Initialize statistics areas
`ST=0
`A=X’10000'
`(see Note below)
`Cc=0
`cT=11
`
`Figure D.12 — Initialization of the encoder
`
`66
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS EX.1016 - 262/714
`
`OLYMPUS EX. 1016 - 262/714
`
`

`

`(pnec 10918-1 : 1993(E)
`
` ie
`The probability 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. 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 whenAisinitialized to X’ 10000’ three
`spacerbits plus eight outputbits in C must befilled before thefirst byte is removed. Note that BPis initialized to pointto
`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.
`
`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 showsthis flush
`procedure. Thefirst step in the procedure is to set as many low orderbits of the code register to zero as possible without
`pointing outside ofthe 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 orderbits in C are guaranteed to be zero, and thesetrailing zero bits shall not be written to the entropy-
`coded segment.
`
`Discard_final_zeros ‘TISO1130-93/d051
`
`Clear_final_bits
`
`C=SLLCCT
`
`Byte_out
`
`Figure D.13 — Flush procedure
`
`CCITT Rec. T.81 (1992 E)
`
`67
`
`OLYMPUS EX.1016 - 263/714
`
`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.
`
`owed by a marker. For this reason, the final zero bits needed to complete decoding
`Entropy coded segments are always fo
`hen the decoder encounters a marker, zero bits shall be
`shall not be included in the entropy coded segment. Instead, w!
`This convention guarantees that when a DNL markeris
`supplied to the decoding procedure until decoding is complete.
`used, the decoderwill interceptit in time to correctly terminate the decoding procedure.
`
`Clear_final_bits
`
`T=C+A-1
`T=TAND
`X’FFFFOOOO"
`
`T=T +x'8000° TISO1140-93/d052
`
`Figure D.14 — Clear_final_bits procedurein Flush
`
`68
`
`CCITT Rec. T.81 (1992 E)
`
`OLYMPUS EX.1016 - 264/714
`
`OLYMPUS EX. 1016 - 264/714
`
`

`

`
`
`BP <BPST
`9
`
`
`BP=BP+1 m T1S01150-93/d053
`
` mo IEC 10918-1 : 1993(E)
`
`Discard_final_zeros
`
`Yes
`
`Figure D.15 — Discard_final_zeros procedure in Flush
`
`D.2
`
`Arithmetic decoding procedures
`
`Twoarithmetic decoding proceduresare used for arithmetic decoding (see Table D.4).
`
`The “Decode(S)” procedure decodes the binary decision for a given context-index S$ and returnsa valueof either 0 or1. It
`is the inverse of the “Code_O(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
`
`—
`
`Initialize the decoder
`
`Procedure
`
`Decode(S)
`Initdec
`
`Decodea binary decision with context-index 5
`
`CCITT Rec. T.81 (1992 E)
`
`69
`
`OLYMPUS EX.1016 - 265/714
`
`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 forthe 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 addedto the code register, the decoder subtracts from the
`coderegister.
`
`D.2.3.
`
`Decoder code register conventions
`
`The flow charts given in this section assumethe register 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,
`
`XXXXXXXK
`
`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 one binary decision at a time. After decoding the decision, the decoder subtracts any amount from
`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 thefirst test in the decode
`procedure shown in Figure D.16 the code register is compared to the size of the MPSsub-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
`
`CCITTRee. T.81 (1992 E)
`
`OLYMPUS EX.1016 - 266/714
`
`OLYMPUS EX. 1016 - 266/714
`
`

`

`
`‘ ”
`wa
`
`
`!AOVTEC 10918-1 : 1993(E)
`NY
`
`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 decoderis identical
`to the probability estimation in the encoder (Figures D.5 and D.6).
`
`
`
`
`
`
`
`D = MPS(S)
`
`
`D = Cond_LPS_exchange(S)
`Renoarm_d
`
`TISO1 160-92/d054
`
`
`A < X’8000’
`
`
`
`D = Cond_MPS_exchange(S)
`Renorm_d
`
`Figure D.16 — Decode(S) procedure
`
`For the MPS path of the decoder the conditional exchange procedureis given in Figure D,18.
`
`CCITT Rec. T.81 (1992 E)
`
`71
`
`OLYMPUS EX.1016 - 267/714
`
`OLYMPUS EX. 1016 - 267/714
`
`

`

`
`
`ISO/IEC 10918-1 : 1993(E)
`
`
`
`Cond_LPS_
`exchange(S)
`
`
`
`
`
`D=1-MPS(8)
`
`D = MPS(S)
`Cx=Ox-A
`Cx=Cx-A
`
`
`A= Qe(S)
`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)
`
`
`2
`
`D = MPS(S)
` D=1-MPS{(S)
`
`Estimate_Qe(S)_
`
`Estimate_Qe(S)_
`after_LPS
`
`
`after_MPS
`
`
`TISO1 180-93/d056
`
`Figure D.18 - Decoder MPSpath conditional exchange procedure
`
`72
`
`CCITT Ree. T.81 (1992 E)
`
`OLYMPUS EX.1016 - 268/714
`
`OLYMPUS EX. 1016 - 268/714
`
`

`

`
`Probability estimation in the decoder
`
`D.2.5
`
`
`“TEC 10918-1 : 1993(E)
`
`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 procedurefor the decoder renormalizationis 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 CTis reset to 8.
`
`Both the probabilityinterval register A and the code register C are shifted, one bit at a time, until A is no longer less than
`X’8000’.
`
`Renorm_d
`
`
`
`A=SLLA1
`
`C=SLLC1
`
`CT=CT-1
`
`A< X’8000'
`?
`
`No
`
`
`
`TISO1 190-93/d057
`
`Figure D.19 — Decoder renormalization procedure
`
`CCITTRec. T.81 (1992 E)
`
`73
`
`OLYMPUS EX.1016 - 269/714
`
`OLYMPUS EX. 1016 - 269/714
`
`

`

`ISO/IEC 10918-1 : 1993(E)
`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°’ FP’, it is inserted into the high order8 bits of C-low.
`
`BP =BP+1
`
` Unstuff_0
`
` C=C+SiLB8
`
`
`
`
`
`TISO1200-93/d058
`
`Figure D.20 — Byte_in procedure for decoder
`
`74
`
`CCITT Ree. T.81 (1992 E)
`
`OLYMPUS EX. 1016 - 270/714
`
`OLYMPUS EX. 1016 - 270/714
`
`

`

` SO/TEC 10918-1 : 1993(E)
`
`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. 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.
`
`BP =BP+1
`
`Adjust BP
` C=C OR X’FFO0"
`
`Interpret_marker
`
`
`
`
`
`
`
`
`TISO121 0-93/d0s9
`
`Figure D.21 ~ Unstuff_0 procedurefor decoder
`
`CCITT Rec. T.81 (1992 E)
`
`75
`
`OLYMPUS EX. 1016 - 271/714
`
`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
`BP =BPST-1
`A= X'0000°
`(see Note below)
`
`C=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 theninitialized to.point to the byte before
`the start of the entropy-coded segment at BPST,andtheinterval registeris set to the samestarting value as in the encoder.
`Thefirst byte of compressed data is fetched and shifted into Cx. The second byteis 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,
`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.
`
`D3
`
`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 sameas for parameters (see B.1.1.1).
`:
`
`76
`
`CCITTRec. T.81 (1992 E)
`
`OLYMPUS EX.1016 - 272/714
`
`OLYMPUS EX. 1016 - 272/714
`
`

`

`
`
`Annex E |
`
`(> /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 procedures for the hierarchical processes are specified in Annex J.
`
`NOTES
`
`There.is no requirementin this Specification that any encoder or decoder shall implement the proceduresin 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. 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 compliancetests specified in Part 2.
`
`2
`
`Implementation-specific setup steps are not indicated in this annex and may be necessary.
`
`E.1
`
`Encodercontrol procedures
`
`E.1.1
`
`Control procedure for encoding an image
`
`The encoder control procedure for encoding an image is shownin Figure E.1.
`
`Encode_image
`
`Append SO! marker
`
`Encode_frame
`
`Append EO! marker
`
`71801220-99/d061
`
`Figure E.1 — Control