《BS-ISO-IEC-12042-1993.pdf》由会员分享,可在线阅读,更多相关《BS-ISO-IEC-12042-1993.pdf(26页珍藏版)》请在三一文库上搜索。
1、BRITISH STANDARD BS ISO/IEC 12042:1993 Implementation of ISO/IEC 12042:1993 Information technology Data compression for information interchange Binary arithmetic coding algorithm UDC 681.3.04:519.688 Licensed Copy: sheffieldun sheffieldun, na, Tue Nov 21 10:08:31 GMT+00:00 2006, Uncontrolled Copy, (
2、c) BSI BS ISO/IEC 12042:1993 This British Standard, having been prepared under the direction of the Information Systems Technology Standards Policy Committee, was published under the authority of the Standards Board and comes into effect on 15 March 1994 BSI 01-2000 The following BSI references rela
3、te to the work on this standard: Committee reference IST/4 Draft for comment 92/63403 DC ISBN 0 580 23068 6 Committees responsible for this British Standard The preparation of this British Standard was entrusted by the Information Systems Technology Standards Policy Committee (IST/-) to Technical Co
4、mmittee IST/4, upon which the following bodies were represented: British Computer Society ICI Imagedata Institute of Quality Assurance Institution of Electrical Engineers International Computers Limited Kodak Limited Amendments issued since publication Amd. No.DateComments Licensed Copy: sheffieldun
5、 sheffieldun, na, Tue Nov 21 10:08:31 GMT+00:00 2006, Uncontrolled Copy, (c) BSI BS ISO/IEC 12042:1993 BSI 01-2000i Contents Page Committees responsibleInside front cover National forewordii Forewordiii Text of ISO/IEC 120421 Licensed Copy: sheffieldun sheffieldun, na, Tue Nov 21 10:08:31 GMT+00:00
6、2006, Uncontrolled Copy, (c) BSI BS ISO/IEC 12042:1993 ii BSI 01-2000 National foreword This British Standard reproduces verbatim ISO/IEC 12042:1993 and implements it as the UK national standard. This British Standard is published under the direction of the Information Systems Technology Standards P
7、olicy Committee whose Technical Committee IST/4 has the responsibility to: aid enquirers to understand the text; present to the responsible international committee any enquiries on interpretation, or proposals for change, and keep UK interests informed; monitor related international and European dev
8、elopments and promulgate them in the UK. NOTEInternational and European Standards, as well as overseas standards, are available from Customer Services, Publications, BSI, Linford Wood, Milton Keynes, MK14 6LE. A British Standard does not purport to include all the necessary provisions of a contract.
9、 Users of British Standards are responsible for their correct application. Compliance with a British Standard does not of itself confer immunity from legal obligations. Summary of pages This document comprises a front cover, an inside front cover, pages i and ii, the ISO/IEC title page, pages ii to
10、iv, pages 1 to 16 and a back cover. This standard has been updated (see copyright date) and may have had amendments incorporated. This will be indicated in the amendment table on the inside front cover. Licensed Copy: sheffieldun sheffieldun, na, Tue Nov 21 10:08:31 GMT+00:00 2006, Uncontrolled Copy
11、, (c) BSI Licensed Copy: sheffieldun sheffieldun, na, Tue Nov 21 10:08:31 GMT+00:00 2006, Uncontrolled Copy, (c) BSI ISO/IEC 12042:1993(E) ii BSI 01-2000 Contents Page Forewordiii Introduction1 1Scope1 2Normative references1 3Conformance1 4Conventions and notations1 5Algorithm identifier1 6Definitio
12、ns1 6.1block1 6.2code block2 6.3code string2 6.4encoding2 6.5input event2 6.6logical data record2 6.7trailer2 6.8unique table pair2 7List of acronyms2 8Compression algorithm2 8.1General2 8.2Encoders2 8.3Formation of a Code Block2 8.4Code String3 8.5Table Pairs3 8.6Encoding4 8.6.1 Normal Mode4 8.6.2
13、Run Mode5 8.7Completion of the encoding of a block6 Annex A (informative) Example of a binary arithmetic coding algorithm9 Figure 1 Code Block3 Figure 2 Sequence of encoding6 Figure 3 Choice of Table Pairs7 Figure 4 Determination of K8 Table 1 Probability values of K3 Table 2 Rules for incrementing
14、K5 Licensed Copy: sheffieldun sheffieldun, na, Tue Nov 21 10:08:31 GMT+00:00 2006, Uncontrolled Copy, (c) BSI ISO/IEC 12042:1993(E) BSI 01-2000iii Foreword ISO (the International Organization for Standardization) and IEC (the International Electrotechnical Commission) form the specialized system for
15、 worldwide standardization. National bodies that are members of ISO or IEC participate in the development of International Standards through technical committees established by the respective organization to deal with particular fields of technical activity. ISO and IEC technical committees collabor
16、ate in fields of mutual interest. Other international organizations, governmental and non-governmental, in liaison with ISO and IEC, also take part in the work. In the field of information technology, ISO and IEC have established a joint technical committee, ISO/IEC JTC 1. Draft International Standa
17、rds adopted by the joint technical committee are circulated to national bodies for voting. Publication as an International Standard requires approval by at least 75 % of the national bodies casting a vote. International Standard ISO/IEC 12042 was prepared by the European Computer Manufacturers Assoc
18、iation (as Standard ECMA-159) and was adopted, under a special “fast-track procedure”, by Joint Technical Committee ISO/IEC JTC 1, Information technology, in parallel with its approval by national bodies of ISO and IEC. Annex A of this International Standard is for information only. Licensed Copy: s
19、heffieldun sheffieldun, na, Tue Nov 21 10:08:31 GMT+00:00 2006, Uncontrolled Copy, (c) BSI iv blank Licensed Copy: sheffieldun sheffieldun, na, Tue Nov 21 10:08:31 GMT+00:00 2006, Uncontrolled Copy, (c) BSI ISO/IEC 12042:1993(E) BSI 01-20001 Introduction In the past decades numerous International St
20、andards for magnetic tapes, magnetic tape cassettes and cartridges, as well as for optical disk cartridges have been published. Media developed recently have a very high physical recording density. In order to make an optimal use of the resulting data capacity, compression algorithms have been desig
21、ned which allow a reduction of the number of bits required for the representation of user data in coded form. These compression algorithms are registered by an International Registration Authority set up by ISO/IEC. The registration will consist in allocating to each registered algorithm a numerical
22、 identifier which will be recorded on the medium and, thus, indicate which compression algorithm(s) has been used. The first International Standard for compression algorithms was: ISO/IEC 11558, Information technology -Data Compression for Information Interchange Adaptive Coding with Embedded Dictio
23、nary DCLZ Algorithm This International Standard is the next one of this series. 1 Scope This International Standard specifies an algorithm for the reduction of the number of bits required to represent information. This process is known as data compression. The algorithm uses binary arithmetic coding
24、. The algorithm provides lossless compression and is intended for use in information interchange. 2 Normative references The following standards contain provisions which, through reference in this text, constitute provisions of this International Standard. At the time of publication, the editions in
25、dicated were valid. All standards are subject to revision, and parties to agreements based on this International Standard are encouraged to investigate the possibility of applying the most recent editions of the standards listed below. Members of IEC and ISO maintain registers of currently valid Int
26、ernational Standards. ISO/IEC 11576:1993, Information technology Procedure for the registration of algorithms for the lossless compression of data. International Register of Algorithms for Lossless Compression of Data, in accordance with ISO/IEC 11576. 3 Conformance A compression algorithm shall be
27、in conformance with this International Standard if it satisfies all mandatory requirements of this International Standard. 4 Conventions and notations The following conventions and notations apply in this International Standard unless otherwise stated: In each field the bytes shall be arranged with
28、Byte 1, the most significant, first. Within each byte the bits shall be arranged with Bit 1, the most significant bit, first and Bit 8, the least significant bit, last. Letters and digits in parentheses represent numbers in hexadecimal notation. The setting of bits is denoted by ZERO or ONE. Numbers
29、 in binary notation and bit combinations are represented by strings of ZEROs and ONEs. Numbers in binary notation and bit combinations are shown with the most significant bit to the left. 5 Algorithm identifier The numeric identifier of this algorithm in the International Register shall be 16. 6 Def
30、initions For the purposes of this International Standard, the following definitions apply. 6.1 block a portion of the Logical Data Record, usually having a length of 512 bytes (see 8.2) Licensed Copy: sheffieldun sheffieldun, na, Tue Nov 21 10:08:31 GMT+00:00 2006, Uncontrolled Copy, (c) BSI ISO/IEC
31、 12042:1993(E) 2 BSI 01-2000 6.2 code block a block after compression with a trailer appended 6.3 code string the encoded Logical Data Record 6.4 encoding the process of generating Code Blocks from blocks 6.5 input event the sample of the input to an encoder currently being examined; in Run Mode it
32、is a byte; in Normal Mode it is a bit 6.6 logical data record the 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 8 Com
33、pression 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 LDR shall be div
34、ided 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 shall return to enc
35、oder 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). CVCurrent Value EVEstimated Value LDRLogical Data Record TPTable Pair Licensed Copy: sheffieldun sheffieldun, na, Tue Nov 21 10:08:31 GMT+00:00 2006, Uncontrolled Co
36、py, (c) BSI ISO/IEC 12042:1993(E) BSI 01-20003 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 ZER
37、O shall be added at the end to form an integral number of 8-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. If the number of bytes in the Compressed Block plus the pad bits, is odd, a Pad Byte set to
38、 (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 that generated by encoder 0, the second that generated by encoder 1, and so on (see Figure 2). 8.5 Table Pai
39、rs Each encoder shall be allocated a table of 256 pairs of numbers, numbered from 1 to 256. The fast number of each Table Pair shall be the estimated value (EV) of the Input Event to be encoded; it shall be 1 or 0. The second number (K) shall be a measure of the probability of the Input Event being
40、equal to the EV. K shall have the value 1, 2, 3 or 4, with the probability shown in Table 1. Table 1 Probability values of K The probabilities shall 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 probabili
41、ty that the Input Event is equal to the EV shall be 2 to 4 times as great as the probability that it would not be equal). Before commencing the encoding of the LDR all EVs shall be set to ZERO and all values of K shall be set to ONE. Compressed Block Pad bits for last data byte Trailer Byte 1 (FF) T
42、railer Byte 2 Pad Byte if byte count odd (00) Figure 1 Code Block Trailer Byte 1shall be set to (FF). Trailer Byte 2 Bits 1 to 4shall be set to 1 100 if the Code Block has been generated from the last block of the LDR. shall be 1 001 for all other Code Blocks. Bit 5shall be set to ZERO if the number
43、 of bytes after encoding is even. shall be set to ONE if the number of bytes after encoding is odd. Bits 6 to 8shall specify the number of pad bits that have been added to form an integral number of bytes. KProbability 11 2 22 4 34 8 48 16 Licensed Copy: sheffieldun sheffieldun, na, Tue Nov 21 10:08
44、:31 GMT+00:00 2006, Uncontrolled Copy, (c) BSI ISO/IEC 12042:1993(E) 4 BSI 01-2000 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 first byte in a block shall be
45、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 and Ru
46、n Mode is enabled, then encoding shall proceed as defined in 8.6.2.2. 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 enabled, then encoding shall proc
47、eed 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 first 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 which Table Pair to select fo
48、r 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, respectively. The third bi
49、t 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; 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
链接地址:https://www.31doc.com/p-3750099.html