ISO IEC 12042-1993 Information technology data compression for information interchange binary arithmetic coding algorithm《信息技术 信息交换用数据压缩 二进制运算编码算法》.pdf

1、INTERNATIONAL STANDARD ISOJIEC 12042 First edition 1993-12-15 Information technology - Data compression for information interchange - Binary arithmetic coding algorithm Technologies de Iinformation - Compression de don in Run Mode it is a byte; in Normal Mode it is a bit. 6.6 Logical Data Record: Th

2、e data entity that is the input to the data compressor. 6.7 trailer: data appended to a block after. compression and addition of pad bits. 6.8 Unique Table Pair: The last of the 256 Table Pairs. used only in Run Mode. 7 List of acronyms cv Current Value EV l3timated Value LDR Logical Data Record TIJ

3、 Table Pair 8 Compression algorithm 8.1 General The LDR is transformed to a Code String by a one-pass, adaptive encoding technique designed to provide lossless data compression. By the use of a suitable decoding technique the exact original LDR can be recovered from the Code String. 8.2 Encoders The

4、 LDR shall be divided into 512-byte blocks, except for the last block, which may be of any length less than, or equal to, 512 bytes. The blocks shall be routed sequentially to eight encoders, numbered from 0 to 7, commencing with encoder 0. If the LDR contains more than 4 096 bytes the compressor sh

5、all return to encoder 0 and repeat the process (see figure 2). 8.3 Formation of a Code Block The output of each encoder is a Code Block (see figure 1). I I 1 Pad bits Compressed Block 1 for last 1 data 1 byte Trailer Trailer Byte 1 Byte 2 0 Pad Byte if byte count odd (W Figure 1 - Code Block lso/lEc

6、 12842: 1993 (E) Since the degree of compression achieved in an encoder depends upon the relative frequency of the bit patterns in the LDR, and upon the presence of sequences of identical bytes, the length of the Compressed Block cannot be predicted. Pad bits set to ZERO shall be added at the end to

7、 form an integral number of g-bit bytes. The Code Block shall be completed by appending a trailer. The trailer shall consist of two Trailer Bytes possibly followed by a Pad Byte. Trailer Byte 1 shall be set to (FF). Trailer Byte 2 Bits 1 to4 shall be set to 1100 if the Code Block has been generated

8、from the last block of the LDR. shall be 1001 for all other Code Blocks. Bit 5 shall be set to ZERO if the number of bytes after encoding is even. shall be set to ONE if the number of bytes after encoding is odd. Bits6to8 shall specify the number of pad bits that have been added to form an integral

9、number of bytes. If the number of bytes in the Compressed Block plus the pad bits, is odd, a Pad Byte set to (00) shall be appended after Trailer Byte 2 to give an even number of bytes. 8.4 Code String The Code String shall be assembled from the outputs of the encoders, with the first portion being

10、that generated by encoder 0, the second that generated by encoder 1, and so on (see figure 2). 8.5 Table Pairs Each encoder shall be allocated a table of 256 pairs of numbers, numbered from 1 to 256. The first number of each Table Pair shall be the estimated value (EV) of the Input Event to be encod

11、ed; it shall be 1 or 0. The second number (K) shall be a measure of the probability of the Input Event being equal to the EV. K shall have the value 1, 2, 3 or 4, with the probability shown in table I. Table l- Probability values of K I K I Probability 111 l-2 2 2-4 3 4-8 4 8- 16 The probabilities s

12、hall be a measure of how much more likely it is that the value of the Input Event is equal to the EV rather than being unequal (e.g. for K=2 the probability that the Input Event is equal to the EV shall be 2 to 4 limes as great as the probability that it would not be equal). Before commencing the en

13、coding of the LDR alI EVs shall be set to ZERO and all values of K shall be set to ONE. 8.6 Encoding The data shall first be examined on a byte basis. Bytes shall be fetched sequentially from the block, starting with the first byte, and compared with the previous byte. The fust byte in a block shall

14、 be compared with (40). Run Mode (see 8.6.2) shall be disabled when the first byte is fetched. If the current byte differs from the previous byte and Run Mode is not enabled, then the byte shall be encoded, bit by bit, in Normal Mode (see 8.6.1). If the current byte differs from the previous byte an

15、d Run Mode is enabled, then encoding shall proceed as defined in 8.6.2.2. 3 IsOhEC 12042: 1993 (E) If the two bytes are identical and Run Mode is not enabled, then Run Mode shall be enabled and the byte shall be encoded, bit by bit, in Normal Mode. If the two bytes are identical and Run Mode is enab

16、led, then encoding shall proceed as defined in 8.6.2.1. 8.6.1 Normal Mode The first (most significant) bit of the byte shall be compared with the EV in the fmt Table Pair. Depending upon the result of this comparison, one of two actions, which are described in 8.6.1.1, shall result. The choice of wh

17、ich Table Pair to select for the remaining bits of the byte shall be determined by the bits previously encoded in the byte. The first bit of each byte shall always use the first Table Pair. The second bit shall use the second or third Table Pair, depending upon whether the first bit was ZERO or ONE,

18、 respectively. The third bit shall use one of the next four Table Pairs depending upon the first two bits. The fourth Table Pair shall be used if the first two bits were 00, and so on (see figure 3). This procedure requires the first 255 Table Pairs. The remaining Table Pair is the Unique Table Pair

19、: it shall be used in the Run Mode only (see 8.6.2). The process of encoding is then performed in two stages: - The bit is encoded as in 8.6.1.1. - The values of K and EV are revised as described in 8.6.1.2. 8.6.1.1 Bit encoding Two values shall be developed during the bit comparison portion of the

20、compression process. Both are fractional binary numbers to four binary places. One value, termed the Current Value (CV), shall be used to generate the output (Code Block). The second value, termed the Width, shall have values in the range O,OOtXl to 1,llll. For each block the CV shall be initialized

21、 to O,OOOO and the Width value shall be initialized lo 1.0000. Each Input Event shall cause the two values to be modified according lo the following rules: 9 The Input Event is equal to the EV The CV shall be increased by 2-K The Width shall be decreased by 2-K where K is the measure of the probabil

22、ity of the Input Event (see 8.5). If the Code Block is not null the bit to the left of the point in the CV shall be logically added to the last bit appended to the Code Block and replaced in the CV by a ZERO. If this addition causes the most recently generated complete byte in the Code Block to beco

23、me (FF), then (0) shall be appended to the Code Block at the end of that byte to prevent a cany from propagating beyond the last complete byte. If the Code Block is null the bit to the left of the point in the CV will already be a ZERO. The Width shall then be compared with 1 ,OOOO. If it is equal t

24、o, or greater than, l,OOOO, then the Table Pair shall be revised (see 8.6.1.2) and the next bit fetched for encoding. If it is less than 1,0000, then all the bits of the Width shall be shifted left one position: the leftmost bit, set to ZERO, shall be dropped, and the rightmost position shall be fil

25、led with a ZERO. The bit in the first position to the right of the point in the CV shall be appended to the encoder output as part of the Code Block. The remaining bits to the right of the point in the CV shall be shifted left one position and the rightmost position shall be filled with a ZERO. To p

26、revent a carry from propagating beyond the last complete byte, each byte in the Code Block shall be examined as it is completed. If it equals (FF) then (0) shall be appended to the Code Block. lsomc 12042: 1993 (E) ii) The Input Event is not equal to the EV. The Width shall be reset to 1,fKKlO. The

27、K bits to the right of the point in the CV shall be shifted out and appended to the Code Block, the leftmost bit first. As each bit is appended to the Code Block a check shall be made to determine whether a byte boundary has been reached. If it has, then the byte just completed shall be checked: if

28、it equals (FF) then (0) shall be appended to the Code Block. The rightmost K bit positions of the CV shall be set lo ZEROS. 8.6.1.2 Revision of K and EV (see figure 4) As each Input Event is compared with the EV the values of K and the EV for that Table Pair shall be amended. A four-stage binary cou

29、nter (MC counter) shall be set to 0000 at the beginning of each block and incremented as described below. 0 The Input Event is equal to the EV K shah be incremented according to table 2, where bits marked X shall be ignored. Table 2 - Rules for incrementing K Current value stale of New value ofK Cou

30、nter ofK 1 XX11 2 2 Xl11 3 3 1111 4 4 4 For all other states of the counter K shall be unchanged. The counter shall then be incremented by 1. If the counter value was 1111 incrementing by 1 shall result in a counter value of 0000. ii) The EV shall be unchanged. The Input Event is not equal to the EV

31、 For K greater than 1 : The value of K shall be decremented by 1 the counter shall not be incremented the EV shall be unchanged For K equal to 1 : the value of K shall be unchanged the counter shall not be incremented the EV shall be inverted 8.6.2 Run Mode Run Mode shall have been enabled if the la

32、st two bytes to be encoded were identical. 8.6.2.1 If the current byte is identical with these two bytes, then the Unique Table Pair is selected and the EV is compared with ONE, the values of the Width, CV. K and EV are amended, as defined in 8.6.1.1 and 8.6.1.2. This may result in the Code Block being extended.