《BS-ISO-IEC-15200-1996.pdf》由会员分享，可在线阅读，更多相关《BS-ISO-IEC-15200-1996.pdf（18页珍藏版）》请在三一文库上搜索。
1、BRITISH STANDARD BS ISO/IEC 15200:1996 Information technology Adaptive Lossless Data Compression algorithm (ALDC) ICS 35.040 Licensed Copy: sheffieldun sheffieldun, na, Wed Nov 22 07:23:40 GMT+00:00 2006, Uncontrolled Copy, (c) BSI BS ISO/IEC 15200:1996 This British Standard, having been prepared un
2、der the direction of the DISC Board, was published under the authority of the Standards Board and comes into effect on 15 July 1997 BSI 03-1999 ISBN 0 580 27749 6 National foreword This British Standard reproduces verbatim ISO/IEC 15200:1996 and implements it as the UK national standard. The UK part
3、icipation in its preparation was entrusted to Technical Committee IST/4, Magnetic and optical media for digital data, which has the responsibility to: aid enquirers to understand the text; present to the responsible international/European committee any enquiries on the interpretation, or proposals f
4、or change, and keep the UK interests informed; monitor related international and European developments and promulgate them in the UK. A list of organizations represented on this committee can be obtained on request to its secretary. Cross-references The British Standards which implement internationa
5、l or European publications referred to in this document may be found in the BSI Standards Catalogue under the section entitled “International Standards Correspondence Index”, or using the “Find” facility of the BSI Standards Electronic Catalogue. A British Standard does not purport to include all th
6、e necessary provisions of a contract. 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,
7、 the ISO/IEC title page, pages ii to iv, pages 1 to 9 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. Amendments issued since publication Amd. No.DateComments Lice
8、nsed Copy: sheffieldun sheffieldun, na, Wed Nov 22 07:23:40 GMT+00:00 2006, Uncontrolled Copy, (c) BSI BS ISO/IEC 15200:1996 BSI 03-1999i Contents Page National forewordInside front cover Text of ISO/IEC 152001 Licensed Copy: sheffieldun sheffieldun, na, Wed Nov 22 07:23:40 GMT+00:00 2006, Uncontrol
9、led Copy, (c) BSI ii blank Licensed Copy: sheffieldun sheffieldun, na, Wed Nov 22 07:23:40 GMT+00:00 2006, Uncontrolled Copy, (c) BSI Licensed Copy: sheffieldun sheffieldun, na, Wed Nov 22 07:23:40 GMT+00:00 2006, Uncontrolled Copy, (c) BSI BS ISO/IEC 15200:1996 ii BSI 03-1999 Contents Page Foreword
10、iii Introduction1 1Scope1 2Conformance1 3Normative Reference1 4Definitions1 4.1Compressed Data Stream1 4.2Copy Pointer1 4.3Current Address1 4.4Data Byte1 4.5Displacement Field1 4.6End Marker1 4.7History Buffer1 4.8Literal2 4.9Matching String2 4.10Match Count2 4.11Match Count Field2 4.12Pad Bits2 5Co
11、nventions and Notations2 5.1Representation of numbers2 5.2Names2 6ALDC compression algorithm2 6.1Encoding description for a 512-byte History Buffer2 6.2Description of the Compressed Data Stream3 Annex A (informative) ALDC encoding format4 Annex B (informative) ALDC Overview5 Annex C (informative) AL
12、DC Encoding Flow Chart6 Annex D (informative) Bibliography9 Table 1 Match Count Field3 Descriptors: Data processing, information interchange, data compression, coded representation, algorithms. Licensed Copy: sheffieldun sheffieldun, na, Wed Nov 22 07:23:40 GMT+00:00 2006, Uncontrolled Copy, (c) BSI
13、 BS ISO/IEC 15200:1996 BSI 03-1999iii Foreword ISO (the International Organization for Standardization) and IEC (the International Electrotechnical Commission) form the specialized system for worldwide standardization. National bodies that are members of ISO or IEC participate in the development of
14、International Standards through technical committees established by the respective organization to deal with particular fields of technical activity. ISO and IEC technical committees collaborate in fields of mutual interest. Other international organizations, governmental and non-governmental, in li
15、aison 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 Standards adopted by the joint technical committee are circulated to national bodies for voting. Publication as an
16、International Standard requires approval by at least 75 % of the national bodies casting a vote. International Standard ISO/IEC DIS 15200 was prepared by ECMA (as ECMA-222) and was adopted, under a special “fast-track procedure”, by Joint Technical Committee ISO/IEC JTC 1, Information technology, in
17、 parallel with its approval by national bodies of ISO and IEC. Annex A to Annex D are for information only. Licensed Copy: sheffieldun sheffieldun, na, Wed Nov 22 07:23:40 GMT+00:00 2006, Uncontrolled Copy, (c) BSI iv blank Licensed Copy: sheffieldun sheffieldun, na, Wed Nov 22 07:23:40 GMT+00:00 20
18、06, Uncontrolled Copy, (c) BSI BS ISO/IEC 15200:1996 BSI 03-19991 Introduction In the past decades ISO/IEC have published numerous International Standards for magnetic tapes, magnetic tape cassettes and cartridges, as well as for optical disk cartridges. Those media developed recently have a very hi
19、gh physical recording density. In order to make optimal use of the resulting data capacity, lossless compression algorithms have been designed which allow a reduction of the number of bits required for the representation of user data. These compression algorithms are registered by ECMA, the Internat
20、ional Registration Authority established by ISO/IEC. The registration consists in allocating to each registered algorithm a numerical identifier which will be recorded on the medium and, thus, indicate which compression algorithm(s) has been used. This International Standard is the third one for los
21、sless compression algorithms. The two previous International Standards are: ISO/IEC 11558:1992, Information technology Data compression for information interchange Adaptive coding with embedded dictionary DCLZ algorithm. ISO/IEC 12042:1993, Information technology Data compression for information int
22、erchange Binary arithmetic coding algorithm. 1 Scope This International Standard specifies a lossless compression algorithm to reduce the number of bytes required to represent data. The algorithm is known as Adaptive Lossless Data Compression algorithm (ALDC). The numerical identifiers according to
23、ISO/IEC 11576 allocated to this algorithm are: ALDC 512-Byte History Buffer: 3 ALDC 1024-Byte History Buffer: 4 ALDC 2048-Byte History Buffer: 5 2 Conformance A compression algorithm shall be in conformance with this International Standard if its output data stream satisfies the requirements of this
24、 International Standard. 3 Normative Reference The following standard contains provisions which, through reference in this text, constitute provisions of this International Standard. At the time of publication, the edition indicated was valid. All standards are subject to revision, and parties to ag
25、reements based on this International Standard are encouraged to investigate the possibility of applying the most recent edition of the standard indicated below. Members of IEC and ISO maintain registers of currently valid International Standards. ISO/IEC 11576:1993, Information technology Procedure
26、for the registration of algorithms for the lossless compression of data. 4 Definitions For the purposes of this International Standard, the following definitions apply. 4.1 Compressed Data Stream the output stream after encoding 4.2 Copy Pointer a part of the Compressed Data Stream which represents
27、a group of two or more consecutive bytes for which there already exists an identical group in the History Buffer. It comprises a Length Code Field and a Displacement Field 4.3 Current Address the location within the History Buffer where the Data Byte is written 4.4 Data Byte the current byte of inco
28、ming data which is written into the History Buffer and is compared to all data bytes previously written into the History Buffer 4.5 Displacement Field that part of the Copy Pointer which specifies the location within the History Buffer of the first byte of a Matching String 4.6 End Marker a string o
29、f 12 ONEs indicating the end of the Compressed Data Stream 4.7 History Buffer a data structure where incoming data bytes are stored for use in the compression and decompression process Licensed Copy: sheffieldun sheffieldun, na, Wed Nov 22 07:23:40 GMT+00:00 2006, Uncontrolled Copy, (c) BSI BS ISO/I
30、EC 15200:1996 2 BSI 03-1999 4.8 Literal a Data Byte for which no match was found in the History Buffer 4.9 Matching String a sequence of bytes in the incoming data which is identical with a sequence of bytes in the History Buffer 4.10 Match Count the number of bytes in a Matching String 4.11 Match C
31、ount Field that part of the Copy Pointer which specifies the number of consecutive bytes for which a match was found in the History Buffer 4.12 Pad Bits bits set to ZERO and included in the Compressed Data Stream, as required, to maintain an 8-bit byte boundary 5 Conventions and Notations 5.1 Repres
32、entation of numbers The following conventions and notations apply in this International Standard, unless otherwise stated. The setting of binary bits is denoted by ZERO and ONE. Numbers in binary notation and bit combinations are represented by ZEROs and ONEs with the most significant bit to the lef
33、t. All other numbers shall be in decimal form. 5.2 Names The names of entities are given with a capital initial letter. 6 ALDC compression algorithm An overview of the ALDC encoding process is given in Annex B, and a flow chart is contained in Annex C. 6.1 Encoding description for a 512-byte History
34、 Buffer At the start of encoding, all bytes of the History Buffer shall be reset to all ZEROs. Data bytes shall be stored in sequence in the History Buffer, starting with a Current Address of 0. The encoder processes the incoming data stream one byte at a time. The current byte being processed is re
35、ferred to as the Data Byte. When a Data Byte is received from the input data stream, it shall be written into the History Buffer at the Current Address. Then the Current Address shall be incremented by 1. If it exceeds the maximum address, which is 511 for a History Buffer size of 512 bytes, it shal
36、l be reset to 0. Step 1 The Data Byte shall be compared with each byte previously written into the History Buffer to identify any identical bytes. Step 2 If the Data Byte does not match any byte in the History Buffer, the process shall continue at Step 6. If the Data Byte matches one or more bytes i
37、n the History Buffer, for every matching byte it shall be noted whether this matching byte is a continuation of a previous sequence of matching bytes or not. If it is not a continuation, the Displacement Field of the matching byte shall be noted and recorded as having a Match Count of one byte. If t
38、he matching byte is a continuation of a previous string, the Match Count for that string shall be incremented by 1. Step 3 If a Match Count equals 271, the corresponding bytes shall be identified by a Copy Pointer, which shall be added to the Compressed Data Stream. Its Match Count Field and Displac
39、ement Field shall be specified as defined in 6.2. The next Data Byte shall then be read and the process shall continue at Step 1. If there is no more data to be read, the process shall continue at Step 7. NOTEThe value of 271 was chosen for implementation reasons. Step 4 If the Match Count has not r
40、eached 271, any pending Matching Strings shall be checked to see if any are continued by the Data Byte. If none of the previous Matching Strings is continued and if any of the previous Matching Strings consists of two or more bytes, that Matching String having the lowest Displacement Field shall be
41、identified by a Copy Pointer, which shall be added to the Compressed Data Stream. The next Data Byte shall then be read. If there is no more data to be read, the process shall continue at Step 7. Licensed Copy: sheffieldun sheffieldun, na, Wed Nov 22 07:23:40 GMT+00:00 2006, Uncontrolled Copy, (c) B
42、SI BS ISO/IEC 15200:1996 BSI 03-19993 If no previous Matching Strings are continued and the previous matches were only 1-byte matches, the previous 1-byte match shall be identified as a Literal and shall be added to the Compressed Data Stream as defined in 6.2. The next Data Byte shall then be read.
43、 If there is no more data to be read, the process shall continue at Step 7. Step 5 If there are no Matching Strings with a Match Count of 271 and there is the continuation of at least 1 previous Matching String, the next Data Byte shall be read. The process shall continue at Step 1. If there is no m
44、ore data to be read, the pending Matching String shall be identified as a Copy Pointer, which shall be added to the Compressed Data Stream. The process shall then continue at Step 7. Step 6 If the Data Byte does not match any bytes of the History Buffer, a check shall be made for any previous Matchi
45、ng Strings that may be pending. If there are any previous Matching Strings of two or more bytes, they shall be identified by a Copy Pointer, which shall be added to the Compressed Data Stream. Then the Data Byte that did not match shall be added to the Compressed Data Stream as a Literal. The next D
46、ata Byte shall be read and the process shall continue at Step 1. If there is no more data to be read, the process shall continue at Step 7. If there are no pending Matching Strings of two or more bytes and there are any pending 1-byte matches, the byte preceding the Data Byte shall be identified as
47、a Literal, which shall be added to the Compressed Data Stream. Then the Data Byte that did not find a match shall be identified as a Literal, which shall be added to the Compressed Data Stream. The next Data Byte shall be read and the process shall continue at Step 1. If there is no more data to be
48、read, the process shall continue at Step 7. Step 7 An End Marker shall be added to the Compressed Data Stream and Pad Bits shall be included as required. This ends the encoding process. 6.2 Description of the Compressed Data Stream As described above, the processing of the input data generates as it
49、s output the Compressed Data Stream. The completed Compressed Data Stream shall consist of: Literals, each preceded by a bit set to ZERO. Copy Pointers, each preceded by a bit set to ONE. An End Marker preceded by a bit set to ONE. Pad Bits. Once all data has been read, the Compressed Data Stream shall be terminated by a bit set to ONE, followed by an End Marker, followed by Pad Bits. During the encoding, if more than one Matching String of the same Match Count is found, the Copy Pointer with the lowest Displacement Field shall be use