1. Introduction

Binary arithmetic coding is a data compression method that generates compressed data as a finite-precision fraction which identifies an interval on the number line. Each picture element (pel) is encoded or decoded on the basis of a probability estimate which determines where the binary arithmetic coder splits the interval into two subintervals. The value of the pel determines which subinterval becomes the new interval. When the size of the new interval drops below a minimum value, Amin, renormalization shifts the precision until it is greater than or equal to the minimum size. With each shift, a bit is produced for the compressed data stream.

Some conventions have to be established about the order of the symbols. For example, the lower interval can be assigned to a 0 and the upper interval assigned to the 1. Alternatively, the lower interval can be assigned to the more probable symbol (MPS) or the less probable symbol (LPS); or the largest subinterval can always be assigned to the more probable symbol. Hardware conventions choose the upper interval as the MPS and the lower interval as the LPS. Software conventions select the lower interval as the MPS and the upper interval as the LPS.

Adaptive binary arithmetic coding uses information about the surrounding pels, the context, to modify the probability estimate. In fact, separate probability estimates are maintained for all possible contexts. A model generates context-pel pairs for the binary arithmetic coder based upon a template. The model must provide the same context for encoding and decoding. The probability estimate of a given context may be changed only when a renormalization is required.

IBM Adaptive Bilevel Image Compression (ABIC) employs the Q-coder for its adaptive binary arithmetic coder [1,2]. The Q-coder was designed with parallel hardware conventions. Its model template consists of seven fixed, nearby pels. For each context, the expected symbol (0 or 1) and an indication of the estimated probability of the unlikely symbol are stored. After initialization of the 128 contexts, the context-decision/pel pairs are input into the binary arithmetic encoder to produce the compressed data stream. The international Joint Bi-level Image Experts Group created the international standard commonly known as JBIG, which employs a software-convention-based arithmetic coder, the QM-coder [3]. The JBIG sequential model template consists of ten nearby pels, one of which can move, creating 1024 probability-estimation contexts to track. Further details regarding ABIC and JBIG models and architectures are available in companion papers [4,5].

Figure 1(a) illustrates the Q-coder hardware-optimized symbol-ordering conventions. The C register (C) holds the least significant bits of the compressed data and points to the base of the less-probable-symbol (LPS) interval. The LPS probability estimate Qe is the size of the LPS interval. The split between the LPS and the more-probable-symbol (MPS) intervals is at C + Qe and belongs to the MPS interval. The complete interval size is held in the A register (A). The sum, C + A, points to the top of the interval and is not part of the MPS segment. The dashed line at C + A - 1 shows the largest value that C can reach.

Figure 1

The software-optimized version of the Q-coder in Reference [6] kept the symbol-order conventions shown in Figure 1(a). Extra cycles to identically match the hardware output always occurred outside the inner loops. The hardware-optimized Q-coder-compressed data stream was constructed while the code stream was pointing to the top of the MPS interval. During the termination procedure, the data stream was moved to the bottom of the LPS segment and thus matched the hardware-generated compressed data. The hardware bit-stuffing conventions were carefully duplicated in the software algorithm.

When the International Organization for Standardization and the International Electrotechnical Commission (ISO/IEC) and the International Telecommunications Union--Terminal Sector (ITU-T), formerly known as the Consultative Committee of the International Telephone and Telegraph (CCITT), working jointly as JBIG with the Joint Photographic Experts Group (JPEG) [7,8], arrived at a common QM-coder, it was defined in terms of a different optimal software convention. Figure 1(b) shows the JBIG/JPEG QM-coder conventions. For the QM-coder, the MPS interval occupied the lower portion of the number line. The point between the interval was assigned to the upper LPS interval. The code stream pointed to the base of the lower MPS interval.

The QM-coder, derived from ABIC, was designed with serial software conventions that make sharing of hardware difficult. However, the basic concept of the conversion of software-optimized arithmetic coding into hardware-optimized structures is known [9,10]. Figure 1(c) shows a hardware-optimized QM-coder, in which the MPS over LPS (MPS/LPS) convention is used. The last valid value of the interval in Figure 1(b), C + A - 1, is mapped to the base of the LPS interval in Figure 1(c). The base of the LPS interval, C + A - Qe, maps to C + Qe - 1, which is the top of the LPS interval. Finally, the base of the MPS interval becomes the last valid value included in the MPS interval, C + A - 1.

This switch in conventions makes it possible to merge the Q-coder and the QM-coder in logic, adopting hardware conventions. The rest of this paper describes in detail how the two arithmetic coders were merged into the Qx-coder. Section 2 discusses more of their differences that must be resolved in the definition of the Qx-coder. Section 3 defines the Qx-coder and illustrates the integration of the Q-coder and QM-coder. Section 4 focuses upon a unique hardware solution to the encoder's termination technique for the JBIG-compressed data stream known as CLEARBITS. Section 5 discusses the various probability estimators and casts them into a common format. Section 6 summarizes the differences between the Q-coder and QM-coder, and the solutions provided by the Qx-coder. The Appendix contains detailed flowcharts implementing the Qx-coder encoder and decoder, and their descriptions.

2. Differences between the Q-coder and the QM-coder

Resolving the fundamental differences between hardware and software conventions is an essential first step in creating the merged Qx-coder. In addition, several other issues must be resolved: register precision, probability-estimation table, carry-over resolution, termination procedures, and byte stuffing.

The Q-coder Qe values have 12 bits of precision. The A register needs a 13th bit. This most significant bit is key to the renormalization-driven probability-estimation process. Whenever A drops below 0x1000, the index I of the MPS probability Qe is changed for the context CX just encoded/decoded.

The QM-coder Qe values have 15 bits of precision. The 16th bit in the A register drives the probability-estimation process. Whenever A drops below 0x8000, the index I is changed for the current context CX. During initialization a 17th bit can be needed for the A register.

To ensure that carries out of the C register could not affect more than the most recently generated compressed byte in the encoder, the Q-coder uses bit stuffing. After every 0xFF byte (aligned on byte boundaries), an extra bit is stuffed into the most significant bit of the next byte. The resolution of any carries that land in the stuffed-bit position is done in the decoder. The newly encoded compressed byte is extracted from the C register in such a way that at most one carry can propagate into it [9].

The QM-encoder is designed to wait to output compressed bytes until any carries have been resolved in the encoder. A stack counter (SC) records the number of buffered 0xFF bytes. This counter typically contains small counts in the range of 1 to 3. However, it could potentially hold the entire compressed data stream and create a severe latency problem [11]. Since carries are resolved in the encoder, bit stuffing is not needed. However, byte stuffing of 0x00 bytes after every compressed 0xFF byte is used to prevent the accidental generation of marker codes.

During the termination of Q-coding, the bits remaining in the C register are shifted into the data stream. This has the nice property that the C register returns to 0x0000 when decoding has completed; otherwise, a nonzero value indicates that errors have occurred.

Since trailing 0x00 bytes may be discarded before the marker codes ending a JBIG stripe or image, the termination procedure for the QM-coder is not a simple flushing of the C register. Instead, the procedure CLEARBITS finds a point inside the interval with the most trailing 0 bits.

3. Qx-coder defined

The Qx-coder takes advantage of the fact that the Q-coder and QM-coder are both finite-precision arithmetic coders and use renormalization-driven probability estimation. The Q-coder hardware-optimized symbol order was chosen. This meant that the QM-coder had to be converted to hardware conventions without modifying the compressed-data bit streams. This was accomplished by inverting the symbol order, as shown in Figure 1(c) and then inverting the compressed data as the bytes are output.

The Qx-coder had to choose a register alignment. The QM and Q entries in Table 1 and Table 2 show the encoder and decoder register assignments as given in References [3] and [6], respectively. Since the precision of the Qe values is 12 bits for the Q-coder and 15 bits for the QM-coder, it was natural to shift the Q-coder values left three bits in the register to line them up with the more significant bits of the QM-coder values. This creates a common Amin value for triggering renormalizations. Table 1 shows that this aligns the output byte, bbbbbbbb, nicely.

The extra spacer bit, s, in the Q-coder was a concern until it was realized that the spacer-bit definition changed between the documentation of the Q-coder and the QM-coder. The Q-coder documentation had as many xs as the precision of the Qe values. The QM-coder documentation has one more x than the precision of its Qe values, so by the more recent definition, both have just three spacer bits. The flag bits f in the most significant byte of the Q-coder C register are not needed because a counter CT keeps track of when to output bytes. The carry bit c is shown to the left of the output byte position. If the previous byte was a 0xFF, the carry bit will be the most significant bit of the output byte at the stuffed-bit position.

The A register has to be kept in alignment with the C register and therefore is also shifted left three bits for the Q-coder in the Qx-coder. It still fits in a 16-bit register. The extra 17th bit of precision in the QM-coder was dropped. The JBIG specification explicitly states that the 17th bit can be avoided if initialization to 0x0000 produces the same output after the first subtraction as initialization to 0x10000 in the low-order 16 bits.

The decoder uses these same definitions of the A register and the Amin value. The entire renormalization-driven probability-estimation process is identical between encoder and decoder. Table 2 shows the decoder register assignments. The Q-coder registers are again shifted left three bits to align them with the QM-coder. The flag bits f in the least significant byte of the Q-coder Clow register are not needed because a counter CT identifies when to input another compressed data byte. The Q-coder input byte bits n are relabeled as b bits and are also shifted left three bits. The three bbb bits in the Chigh register do not disturb the decoding process because all tests against Chigh are "greater than or equal to" comparisons.

The QM-coder always has marker codes that follow the arithmetic-coded compressed data. Trailing 0x00 bytes may have been removed, so any missing data is filled in as 0x00 bytes. The Q-coder expects sufficient bits to completely decode the final decision in the compressed data stream. Since there are no marker codes, the end of compressed data will not always be known. To prevent waiting for nonexistent data upon a request for more data three shifts before the termination of compression, the Q-coder data is shifted up in the C register.

4. Hardware-optimized CLEARBITS

Since the Qx-coder selected the Q-coder symbol-ordering conventions, the flushing of the C register to terminate Q-coding basically remained unchanged. However, the QM-coder software-optimized CLEARBITS procedure, designed to clear the most trailing bits, had to be converted to a hardware-optimized procedure CLEARBITSx designed to set the most trailing bits to 1. Then the output inversion process would clear those bits.

Figure 2 gives the QM-coder CLEARBITS procedure derived from Figure 29 in Reference [3]. A variable T (TEMP in the JBIG specification) is set to the top of the valid interval (T = A - 1 + C), and then its 16 least significant bits are cleared (T = T AND 0xFFFF0000). If T is no longer in the interval (T < C), 0x8000 is added back into T before setting C to T. This serial software approach is awkward in hardware.

Figure 2

Figures 1(b) and 1(c) show that the software-optimized upper point in the interval, (C + A - 1), is mapped directly to C. So a CLEARBITSx procedure with hardware conventions must set as many bits of C to 1 as possible, and, if the result is too large for the valid interval, decrement it by 0x8000. Figure 3 defines this CLEARBITSx procedure. For the CLEARBITSx shown in Figure 3, let Chigh and Clow be the nonoverlapping most significant and least significant 16 bits of C, respectively. Since A uses only 16 bits, A equals Alow. Substituting these new definitions for C and A and eliminating the temporary variable T produces an alternate simplified CLEARBITSx, given in Figure 4.

Figure 3 Figure 4

Since Alow (after any required renormalizations) is always greater than or equal to 0x8000, the test is reduced to a bit test on C[15]. If the most significant bit of Clow is set (C[15] = 1), the test will always fail. If that bit is zero, the 15 low-order bits of A are added into C to allow a potential carry to set C[15]. The 15 low-order bits of C are set to 1s. The simplicity of this hardware is shown in Figure 5. A flowchart version of this figure is used for CLEARBITSx in Figure 16, shown later.

Figure 5

5. Probability estimation

The Q-coder and the QM-coder are both renormalization-driven probability estimators [3,7,8,12]. Instead of collecting statistics on the occurrence of 0 and 1 decisions for each context CX and calculating probabilities, predetermined probabilities are referenced in a probability-estimation table. An index (I) into the probability-estimation table is saved at each context. From this index, the Qe value can be generated. The Qx-coder has unique probability-estimation tables for the Q-coder and the QM-coder. Formats for these tables are presented in Table 3 and Table 4. A third table, nicknamed the JPEG-FA table for its reuse of Qe values in two "fast attack" paths, is presented in Table 5 [8].

An entry in the probability estimation table consists of a current index, I, a probability estimate, Qe, two possible next indices, NMPS and NLPS, and a SWITCH value. As each decision is processed, the index is changed any time a renormalization is required. For renormalizations triggered by the coding of an MPS, the NMPS gives the new index. Renormalizations are always required after the coding of an LPS. The NLPS gives the new index for this case. In addition, on an LPS renormalization, the sense of the MPS bit stored at each context may have to be switched, as indicated by a 1 in the SWITCH column.

In Table 4, many of the Qe values are used at most once per context because they are part of the initial learning. Only 46 entries are part of the nontransient QM estimation state machine. The gaps in Table 4 show where the Qe values break a monotonically decreasing pattern. At these breaks, the NMPS index is not an increment of 1 away from the current index.

The JPEG-FA table has a much simpler initial learning structure. It is a variant of the Q-coder table extended to 15-bit precision. The JBIG committee has selected this table for the MQ-coder used in the new JBIG-2 lossy and lossless compression algorithm [13]. The MQ-coder follows the hardware conventions of the Q-coder with bit stuffing, but always assigns the MPS to the largest subinterval (conditional exchange), as is done in the QM-coder. Since probability estimates have fifteen bits of precision, the three trailing zeros of the Q-coder in the Qx-coder are replaced with real data.

6. Summary

The hardware-optimized Q-coder and the software-optimized QM-coder are merged into a common hardware-optimized Qx-coder. The Q-coder 13-bit A register located in the Qx-coder corresponds to the high-order 13 bits of the 16-bit QM-coder A register. Similarly, the Q-coder C register in the Qx-coder is shifted left three bits in the QM-coder C register. This allows the output byte to be co-located in the hardware. The QM-coder hardware-optimized compressed data is inverted at the output to create the identical QM-coder software-optimized compressed data. The CLEARBITSx procedure is optimized for hardware and can be executed in one cycle compared to the CLEARBITS and Clear_final_bits procedures given in the JBIG and JPEG standards respectively, which take several cycles. Both Q-coder bit stuffing and QM-coder byte stuffing are implemented.

Table 6 summarizes the differences between the Q-coder and the QM-coder and the solution chosen for the Qx-coder. A complete set of flowcharts for the Qx-coder are presented and discussed in the Appendix. Test sequences for the Q-coder are found in [6]; test sequences for the QM-coder are found in Table 26 of [3] and Annex K of [7] and [8]. More details about the rest of the ABIC/JBIG ASIC core which implements the Qx-coder architecture are found in companion papers [4,5] and on the IBM Blue Logic Internet site [14].

Appendix: Description of the Qx-coder flowcharts

Figures 6 to 25 show flowcharts for the merged Qx-coder. A bold-faced name in a flowchart block indicates that a more detailed description of a procedure with that name can be found in the flowcharts. All tests in the flowcharts are logical, unsigned comparisons.

The definitions used in the flowcharts are as follows:

A	A 16-bit register containing the current interval.
ABIC	A status flag selecting the Q-coder from the ABIC algorithm or the QM-coder from the JBIG algorithm. It also selects which probability-estimation table to use. If the ABIC status flag is 0, Qe, NMPS, NLPS, and SWITCH are taken from the QM-coder values in Table 3. If the ABIC status flag is 1, these values are taken from Table 3.
AND	The AND logical operator.
B	The latest compressed byte output in the encoder or compressed byte input in the decoder.
C	A register containing the least significant bits of the encoder's compressed data and the most significant bits of the decoder's compressed data.
CD	The compressed data, including stuffed bytes/bits.
Chigh	The 16 high-order bits of C.
COUNT	The number of extra bits flushed for ABIC to guarantee that the decoder has enough bits to completely decode all decisions.
CT	The counter that identifies byte boundaries and, therefore, when to output or input bytes of compressed data.
CX	The context generated by the model. The model unit provides the same context to the encoder and decoder for a given decision.
D	The binary decision to be coded (0/1). In the encoder it is determined by the model unit; in the decoder, it is output from the Qx-decoder.
"Finished"	A status flag. For ABIC it is set when all of the lines have been encoded or decoded. For JBIG it is set when all of the lines in a stripe have been encoded or decoded.
"First stripe of this layer or forced reset"	A status flag that selects either initializing the statistics or preserving them.
I(CX)	The index of the current probability estimate for context CX.
MPS(CX	The sense of the more probable symbol (0/1) for the given context CX.
NLPS[I(CX)]	The next index for context CX after coding an LPS.
NMPS[I(CX)]	The next index for context CX after coding an MPS that triggered a renormalization.
Qe[I(CX)]	The current estimate of the less probable symbol probability.
SC	The stack counter used only during QM-coding.
SWITCH[I(CX)]	The switch flag which indicates that the sense of MPS(CX) must be switched after coding an LPS.
T	A temporary variable used for intermediate results.
XOR	The EXCLUSIVE-OR logical operator.
<<	The binary shift left logical operator.
>>	The binary shift right logical operator.

Figure 6 is a block diagram showing the inputs and output to the Qx-encoder, ENCODERx. Figures 7 to 17 illustrate in greater detail the functional block in Figure 6. Figure 18 is a block diagram showing the inputs and output to the Qx-decoder, DECODERx. Figures 19 to 25 show more details of this decoder.

Figure 6

Table 7 compares the Qx-coder flowchart symbols with the notation used for the QM-coder as documented in the JBIG standard [3], with the notation used for the Q-coder [6], and with the notation used for the QM-coder as documented in the JPEG standard [7,8].

Figure 6 shows a simple block diagram of the Qx-coder binary adaptive arithmetic encoder. The decision (D) and context (CX) pairs are processed together in the procedure ENCODERx to produce compressed data (CD) output. Both D and CX are provided by the model unit (not shown). CX selects the probability estimate to use during the coding of D. For a compression ratio of 10:1, about 80 decisions are coded before a byte of compressed data is output.

ENCODERx (Figure 7) initializes the Qx-coder through the INITENCx procedure. CX and D pairs are read and passed on to ENCODEx until all pairs have been read. Bytes of compressed data are output when no longer modifiable. When all of the CX and D pairs have been read (Finished?), FLUSHx concatenates the contents of the C register to the compressed data stream for ABIC and clears as many bits as possible for JBIG.

Figure 7

INITENCx (Figure 8) initializes the probability-estimation tables to either the ABIC values (Table 3) or the JBIG values (Table 4). For all ABIC images, the index I(CX) for the less-probable-symbol probability estimate for all contexts is set to 0, and the more-probable-symbol MPS(CX) for all contexts is also set to 0. This is also true for the first stripe of all JBIG images and any images that use a forced reset between stripes. If a JBIG image does not reset the contexts between stripes, the context indices and MPS remain as they were at the end of the previous stripe at the same level.

Figure 8

INITENCx initializes B to 0x80 and C to 0. For ABIC images, A is initialized to 0x8000, and the byte boundary counter (CT) is initialized to 12. For JBIG images, A is initialized to 0x0000, and CT is initialized to 11. The stack counter is also used for JBIG images, and it is initialized to 0. If A were more than 16 bits for JBIG, it would be initialized to 0x10000. A note in the JBIG specification clarifies that 16 bits is sufficient if the effect of the initial subtraction from 0x0000 is the same as the initial subtraction from 0x10000.

ENCODEx (Figure 9) uses the context CX and decision D pair. It compares D with the more probable symbol for CX, MPS(CX). If they are equal, the decision is coded as a more probable symbol in CODEMPSx. Otherwise, the decision is coded as a less probable symbol in CODELPSx.

Figure 9

CODELPSx (Figure 10) codes a less probable symbol. If the algorithm is ABIC, C remains the same, and A is set to Qe[I(CX)]. If the algorithm is JBIG, A is decremented by Qe[I(CX)] and compared to Qe[I(CX)] in the conditional exchange test. If A is less than Qe[I(CX)], C is incremented by Qe[I(CX)]; otherwise, C remains the same and A is set to Qe[I(CX)]. Next, if SWITCH(CX) is set, the more probable symbol for the current context is switched to the opposite symbol. The index into the probability-estimation table for context CX, I(CX), is updated with NLPS[I(CX)], and RENORMEx is called.

Figure 10

CODEMPSx (Figure 11) codes a more probable symbol. A is reduced by the LPS probability, Qe[I(CX)]. If A is not below 0x8000, C is incremented by Qe[I(CX)] and CODEMPSx is complete. If A drops below 0x8000 and the algorithm is ABIC, C is increased by Qe[I(CX)]. If A drops below 0x8000 and the algorithm is JBIG, A is tested to see whether a conditional exchange is required (A < Qe[I(CX)]). If A is less than Qe[I(CX)], C remains the same, and A is set to Qe[I(CX)]; otherwise, C is incremented by Qe[I(CX)]. I(CX) is then updated with the value stored in NMPS[I(CX)], and RENORMEx is called. RENORMEx (Figure 12) left-shifts A and C until A is greater than or equal to 0x8000. After each shift, CT is decremented and then tested. If CT equals 0, BYTEOUTx is called.

Figure 11 Figure 12

BYTEOUTx (Figure 13) first checks which algorithm is being used. If the algorithm is ABIC, BITSTUFFx is called, and BYTEOUTx is complete. If the algorithm is JBIG, the temporary variable T is assigned C right-shifted by 19. If T is greater than 0xFF, a carry has occurred, and the byte in the output buffer, B, is incremented, inverted, and written to the compressed data stream. Then, the two bytes 0xFF00 are written into the compressed data stream SC times (including no times if SC is still zero). The propagation of the carry through the counted 0xFF bytes converted them to 0x00 bytes. However, the inversion process restores them to 0xFF, and byte stuffing causes each 0xFF byte to be followed immediately by a stuffed 0x00 byte. SC is set to 0, and B is assigned the least significant eight bits of T.

Figure 13

If the test to see whether T is greater than 0xFF failed, then, if T is equal to 0xFF, the stack counter SC is incremented. Otherwise, B is tested for equality with 0x00. If so, the pair of bytes 0xFF00 are written into the compressed data stream; otherwise B is inverted and written. The byte 0x00 is written SC times; SC is set to 0, and B is set to T. Finally, the byte placed in the output buffer and the carry bit are removed from C by masking off the leftmost significant nine bits. CT is set to 8.

BITSTUFFx (Figure 14) tests to see whether the byte in the output buffer, B, is equal to 0xFF. If it is, B is written to the compressed data stream and then set to the seven most significant bits of C. These bits are then cleared from C, and CT is set to 7, indicating that bit stuffing has occurred. If B was not 0xFF, C is tested for a carry. If there was a carry, B is incremented and tested again. If B is now equal to 0xFF, the carry bit is removed from C; B is written and assigned the seven most significant bits of C; the seven most significant bits are cleared from C; and CT is set to 7. If B is not equal to 0xFF or no carry was set in C, B is written and assigned the eight most significant bits of C; the eight most significant bits of C are cleared, and CT is set to 8.

Figure 14

FLUSHx (Figure 15) first tests which algorithm is being used. If the algorithm is ABIC, COUNT is set to 24. COUNT is then decremented by CT; C is left-shifted by CT; and BYTEOUTx is called. These three steps are repeated while COUNT is greater than 0. Once COUNT is less than or equal to 0, if CT equals 7, 0x00 is written to output the trailing stuffed bit. If the algorithm is JBIG, CLEARBITSx and FINALWRITESx are called. If desired, any trailing 0x00 bytes at the end of CD may also be removed. FLUSHx is completed for both algorithms when the first byte in CD is removed.

Figure 15

CLEARBITSx (Figure 16) tests bit 15 of C. If bit 15 is 0, the sum of C and A masked with 0x7FFF will not carry into bit 16 of C, and the addition can be performed. The addition determines whether bit 15 of C will be set to 0 or 1. In either case, the 15 least significant bits of C are then set to 0x7FFF.

Figure 16

FINALWRITESx (Figure 17) left-shifts C by CT. If C is greater than 0x8000000, a carry exists. The byte in the output buffer, B, is incremented, inverted, and written; and the pair of bytes 0xFF00 is written SC times. If a carry does not exist, B is tested for equality with 0x00. If so, the pair of bytes 0xFF00 are written into the compressed data stream; otherwise B is inverted and written. The byte 0x00 is written SC times. Finally, the most significant 16 bits of the C register, not including the carry bit, are inverted and written.

Figure 17

Figure 18 shows a simple block diagram of a binary adaptive arithmetic decoder. The compressed data CD and a context CX from the decoder's model unit (not shown) are input to the arithmetic decoder, DECODERx. The decoder's output is the decision D. The encoder and decoder model units must supply exactly the same context CX for each given decision.

Figure 18

DECODERx (Figure 19) initializes the Qx-coder through INITDECx. Contexts, CX, and bytes of compressed data (as needed) are read and passed on to DECODEx until all contexts have been read. When all contexts have been read, the coded data has been decompressed.

Figure 19

INITDECx (Figure 20) initializes the probability-estimation tables to either the ABIC values (Table 3) or the JBIG values (Table 4). For all ABIC images, the index of the MPS probability estimate I(CX) and the more probable symbol MPS(CX) for all contexts are both set to 0. This is also true for the first stripe of all JBIG images and any images that use a forced reset between stripes. If a JBIG image does not reset the contexts between stripes, the context indices and more probable symbols remain as they were at the end of the previous stripe of this layer. B is initialized to 0x80. C is initialized to 0. BYTEINx is called to read in a byte of compressed data. C is left-shifted by 8. BYTEINx is called to read in another byte of coded data. For ABIC images, C is left-shifted by 4; CT is decremented by 4; and A is initialized to 0x8000. For JBIG images, C is left-shifted by 8; BYTEINx is called a third time; and A is initialized to 0. For implementations in which A has more than 16 bits, it is initialized to 0x10000.

Figure 20

DECODEx (Figure 21) decrements A by Qe[I(CX)]. If Chigh is less than Qe[I(CX)], LPS_EXCHANGEx and RENORMDx are called, and DECODEx completes. If Chigh is greater than or equal to Qe[I(CX)], Chigh is decremented by Qe[I(CX)]. If A is less than 0x8000, MPS_EXCHANGEx and RENORMDx are called; otherwise, the decision, D, is set to MPS(CX). D is returned to the calling DECODERx routine.

Figure 21

LPS_EXCHANGEx (Figure 22) tests which algorithm is used. If the algorithm is ABIC, A is set to Qe[I(CX)] and D is set to the LPS value, i.e., 1 - MPS(CX). If SWITCH[I(CX)] is set, MPS(CX) is inverted. The index, I(CX), is updated with NLPS[I(CX)]. The decoded decision D is returned to the calling routine.

Figure 22

If the algorithm is JBIG, A is tested against Qe[I(CX)]. If A is greater than or equal to Qe[I(CX)], the ABIC path is taken as above; otherwise, A is set to Qe[I(CX)], D is set to MPS(CX), and the I(CX) is updated with NMPS[I(CX)]. The decoded decision D is returned to the calling routine.

MPS_EXCHANGEx (Figure 23) tests which algorithm is used. If the algorithm is ABIC, D is set to MPS(CX). The index, I(CX), is updated with NMPS[I(CX)]. The decoded decision D is returned to the calling routine.

Figure 23

If the algorithm is JBIG, A is tested against Qe[I(CX)]. If A is greater than or equal to Qe[I(CX)], the ABIC path is taken as above; otherwise, D is set to the LPS value, 1 - MPS(CX). If SWITCH[I(CX)] is set, MPS(CX) is inverted. The index, I(CX), is updated with NLPS[I(CX)]. The decoded decision D is returned to the calling routine.

RENORMDx (Figure 24) left-shifts A and C and decrements CT until A is greater than or equal to 0x8000. Before each shift, if CT is 0, BYTEINx is called to read in another byte of compressed data. Once A is greater than or equal to 0x8000, if the algorithm is JBIG and CT equals 0, BYTEINx is called again.

Figure 24

BYTEINx (Figure 25) tests which algorithm is used. If the algorithm is ABIC, bit stuffing is used. For bit unstuffing, B is tested. If B is 0xFF, one byte of compressed data is read from CD, and B is set equal to it. C is incremented by B left-shifted 12 bits. The counter CT is set equal to 7, indicating that the byte includes a stuffed bit. If B is not equal to 0xFF, one byte of compressed data is read from CD, and B is set equal to it. C is incremented by B left-shifted 11 bits. The counter CT is set to 8, indicating that eight bits are to be processed before another byte of compressed data is needed.

Figure 25

If the algorithm is not ABIC, a test is done to see whether all of the compressed data has been read from CD. If all the data has been read, B is set equal to 0x00. If not, a new byte is read from CD, and B is set equal to it. If B is equal to 0xFF, the next byte is read from CD. Once B is set, increment C by an inverted B left-shifted by eight bits. CT is set to 8.

Acknowledgments

The authors thank S. H. Burroughs for his persistence in asking whether merging a Q-coder and a QM-coder in VLSI was practical, the Xionics Corporation for demonstrating a market for the Qx-coder, and their colleagues, P. S. Colyer, F. A. Kampf, and K. M. Marks, for helpful discussions. In addition, they thank their managers, J. A. Oleszkiewicz, F. C. Mintzer, and T. R. Lattrell, for encouragement and support of this work; W. B. Pennebaker for his invaluable contributions to the pioneering work on hardware- and software-optimized arithmetic coding structures; R. B. Arps and G. G. Langdon, who played significant roles in laying the foundation of the hardware ABIC; and C. Constantinescu for rapid code updates to the software that was used to validate the design. The Q-coder work was done as a collaboration between the IBM Thomas J. Watson and Almaden Research Centers.

References

Received February 3, 1998; accepted for publication May 21, 1998