《ANSI-INCITS-225-1992-R1999.pdf》由会员分享，可在线阅读，更多相关《ANSI-INCITS-225-1992-R1999.pdf（18页珍藏版）》请在三一文库上搜索。
1、ANSI INCITS 225-1992 (R1999) (formerly ANSI X3.1992 (R1999) for Information Systems Compaction Algorithm Binary Arithmetic Coding Copyright American National Standards Institute Provided by IHS under license with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resale, 05/09/2007 0
2、0:05:58 MDTNo reproduction or networking permitted without license from IHS -,-,- American National Standard Approval of an American National Standard requires review by ANSI that the requirements for due process, consensus, and other criteria for approval have been met by the standards developer. C
3、onsensus is established when, in the judgment of the ANSI Board of Standards Review, substantial agreement has been reached by directly and materially affected interests. Substantial agreement means much more than a simple majority, but not necessarily unanimity. Consensus requires that all views an
4、d objections be considered, and that a concerted effort be made toward their resolution. The use of American National Standards is completely voluntary; their existence does not in any respect preclude anyone, whether he has approved the standards or not, from manufacturing, marketing, purchasing, o
5、r using products, processes, or procedures not conforming to the standards. The American National Standards Institute does not develop standards and will in no circumstances give an interpretation of any American National Standard. Moreover, no person shall have the right or authority to issue an in
6、terpretation of an American National Standard in the name of the American National Standards Institute. Requests for interpretations should be addressed to the secretariat or sponsor whose name appears on the title page of this standard. CAUTION NOTICE: This American National Standard may be revised
7、 or withdrawn at any time. The procedures of the American National Standards Institute require that action be taken periodically to reaffirm, revise, or withdraw this standard. Purchasers of American National Standards may receive current information on all standards by calling or writing the Americ
8、an National Standards Institute. Published by American National Standards Institute 11 West 42nd Street, New York, New York 10036 Copyright 1992 by Information Technology Industry Council (ITI) All rights reserved. No part of this publication may be reproduced in any form, in an electronic retrieval
9、 system or otherwise, without prior written permission of ITI, 1250 Eye Street NW, Washington, DC 20005. Printed in the United States of America Copyright American National Standards Institute Provided by IHS under license with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resal
10、e, 05/09/2007 00:05:58 MDTNo reproduction or networking permitted without license from IHS -,-,- ANSI X3.225-1992 American National Standard for Information Systems Compact Algorithm Binary Arithmetic Coding Secretariat Computer and Business Equipment Manufacturers Association Approved American Nati
11、onal Standards Institute, Inc. Copyright American National Standards Institute Provided by IHS under license with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resale, 05/09/2007 00:05:58 MDTNo reproduction or networking permitted without license from IHS -,-,- ii Contents Page
12、Foreword .iii 1Scope and purpose 1 2Normative references.1 3Definitions .1 4Environment and safety2 5Algorithm identifier.2 6Compaction algorithm 2 Figure 1Code block.3 Annexes APseudo code description of algorithm6 BBibliography.12 Copyright American National Standards Institute Provided by IHS und
13、er license with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resale, 05/09/2007 00:05:58 MDTNo reproduction or networking permitted without license from IHS -,-,- iii Foreword(This foreword is not part of American National Standard X3.225-1992.) This standard presents requireme
14、nts for compacting data to be used for information interchange among processing systems, communication sys- tems, and associated equipment. This standard deals solely with compact- ing data. The X3B5 Subcommittee on Magnetic Tape, which developed this standard, consists of experienced and qualified
15、specialists on manufactur- ing magnetic tape, on recording digital information on magnetic tape, and on the compaction algorithms used to process the digital information. This algorithm represents a significant advancement in the way data is recorded on magnetic media, providing higher data rates an
16、d greater volumetric effi- ciency. In the development of this standard careful consideration was given to current practices, existing equipment and supplies, and the broadest possible acceptance, and to providing a basis for future improvements in the use of the algorithm. The standard contains spec
17、ifications for a compaction algorithm. The text of this standard differs from the corresponding ISO and ECMA standards, International Standard for Information technology Data compression for information interchange Binary arithmetic coding algorithm, ISO 12042, and Data compression for information i
18、nterchange Binary arithmetic algo- rithm, ECMA 159. However, it is the intent of this standard to be technical- ly the same. There are two annexes in this standard. Both annex A and B are informa- tive and are not considered part of this standard. Requests for interpretation, suggestions for improve
19、ment or addenda, or defect reports are welcome. They should be sent to the X3 Secretariat, Computer and Business Equipment Manufacturers Association, 1250 Eye Street, NW, Suite 200, Washington, DC 20005. This standard was processed and approved for submittal to ANSI by Accredited Standards Committee
20、 on Information Processing Systems, X3. Committee approval of the standard does not necessarily imply that all members voted for its approval. At the time it approved this standard, the X3 Committee had the following members: Copyright American National Standards Institute Provided by IHS under lice
21、nse with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resale, 05/09/2007 00:05:58 MDTNo reproduction or networking permitted without license from IHS -,-,- iv Harold L. Book Peter Bramhall James T. Craze Mike Deese Robert F. Driscal Gary R. Early James A. Eggebeen Arthur Freema
22、n Michael Galata Dana S. Grubb Kirk Handley Michael L. Helsel Hakan Hemdal Harry C. Hinz, Jr. David M. Hudson Kyriacos Joannou Randy Kerns Bill King Richard Lee Jack Marion Kazuyuki Masukane William Mealey Bill Medlinski T. Mitsutomi Gary D. Moeller Tom Molstad Gerrit Nijssen Pete Passaretti Keith P
23、ollock Ed Rhodes Maritza Robbennolt Howard Robinson Arnold J. Roccati Joe Shimizu Herman Strass James V. Tierney, III Henry G. Tobin Charles Wellington Douglas Whiting David M. Wilson Kirk D. Wilson James W. Wolf Kei Yamashita Joseph S. Zajaczkowski Bob Abe (Alt.) Robert B. Anthony (Alt.) Leonard Ba
24、dour (Alt.) Tom Behrens (Alt.) David Berry (Alt.) Michael L. Bolt (Alt.) Anthony B. Bova (Alt.) James U. Chesnutt (Alt.) James Chu (Alt.) Louis C. Domshy (Alt.) David J. Donald (Alt.) Chuck Fannin (Alt.) Howard Flagg (Alt.) John Fleming (Alt.) Lonnie Ford (Alt.) Shoji Fujiwara (Alt.) Jerry Ganske (A
25、lt.) Clint R. Gaylord (Alt.) Kunio Goto (Alt.) Larry Jacob (Alt.) Matt Jacobs (Alt.) Paul Jahnke (Alt.) Tony Jasionowski (Alt.) Don Jeffares (Alt.) Ross Johnston (Alt.) Bob Keesy (Alt.) George Klechefski (Alt.) Steve Krupa (Alt.) Carl Labmeier (Alt.) Stephen Leader (Alt.) Demetrios Lignos (Alt.) Geo
26、rge McBride (Alt.) Jim McDonald (Alt.) Judson A. McDowell (Alt.) David McFarland (Alt.) Tony Merdian (Alt.) Charles B. Meyer (Alt.) David R. Mills (Alt.) Toshimi Miyao (Alt.) Robert Monsour (Alt.) Donald E. Morgan (Alt.) Eddie T. Morioka (Alt.) Robert Morris (Alt.) Yoshikazu Nakamura (Alt.) Gary Nel
27、son (Alt.) Roy Nelson (Alt.) John Neumann (Alt.) Jack Niebell (Alt.) Kentaro Odaka (Alt.) Roger E. Olson (Alt.) Anthony OSullivan (Alt.) Terry L. Parsons (Alt.) Edward W. Prohaska (Alt.) Bob Richmond (Alt.) Richard Silva (Alt.) Robert L. Simpson (Alt.) Leif Skaar (Alt.) Jun Takayama (Alt.) Gerald Ta
28、ylor (Alt.) Joseph Trost (Alt.) Gavin Villapiano (Alt.) Michael Warman (Alt.) Mark Williamson (Alt.) Dick Woo (Alt.) Ken Wood (Alt.) Technical Committee X3B5 on Digital Magnetic Tape, which developed this standard, had the following members: Richard T. Steinbrenner, Chair Samuel D. Cheatham, Vice-Ch
29、air Copyright American National Standards Institute Provided by IHS under license with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resale, 05/09/2007 00:05:58 MDTNo reproduction or networking permitted without license from IHS -,-,- 1 Scope and purpose 1.1 Scope This standard
30、provides the information neces- sary to ensure interchangeability of compact- ed data between information processing sys- tems, communication systems, and associated equipment using standard code as agreed upon by the interchange parties. This stan- dard deals solely with the requirements for using
31、the compaction algorithm. CAUTION The users attention is called to the possibility that compliance with this standard may require use of an invention covered by patent rights. By publication of this standard, no position is taken with respect to the validity of this claim or of any patent rights in
32、connection therewith. However, the patent holder has filed a statement of willingness to grant a license under these rights on reasonable and nondiscriminatory terms and conditions to applicants desiring to obtain such a license. Details may be obtained from the publish- er. No representation or war
33、ranty is made or implied that this is the only license that may be required to avoid infringement in the use of this standard. 1.2 Purpose This standard defines the requirements nec- essary to ensure interchange. It is distinct from a specification in that it delineates a min- imum number of restric
34、tions consistent with compatibility in interchange transactions. Wherever feasible, quantitative requirements that shall be met or exceeded in order to com- ply with this standard are given. In all cases, including those in which quantitative limits for requirements falling within the scope of this
35、standard are not stated but left to agreement between interchange parties, standard test methods and measurement procedures shall be used to determine such limits. Except as indicated above, interchange par- ties complying with the applicable standards should be able to achieve compatibility with- o
36、ut the need for additional exchange of tech- nical information. 1.3 Conformance A binary arithmetic coding algorithm conforms to this standard if it satisfies all mandatory requirements of this standard. 2 Normative references The following standard contains provisions which, through reference in th
37、is text, constitute provisions of this American National Standard. At the time of publication, the edition indicated was valid. All standards are subject to revision, and parties to agreements based on this American National Standard are encouraged to investigate the possibility of applying the most
38、 recent edition of the standard indicated below. ANSI X3.172-1990, Information systems Dictionary for information processing systems 3 Definitions The following definitions, listed in alphabetical order, and those given in the ANSI X3.172, apply to this standard: 3.1 block: A sequential 512-byte por
39、tion of the logical data record. The logical data record is compacted on block boundaries. 3.2 code block: The encoded block with a trailer appended. 1 American National Standard for Information Systems Compaction Alogorithm Binary Arithmetic Coding AMERICAN NATIONAL STANDARD ANSI X3.225-1992 Copyri
40、ght American National Standards Institute Provided by IHS under license with ANSI Licensee=USN Ship Repair Facility Yokosuka/9961031100 Not for Resale, 05/09/2007 00:05:58 MDTNo reproduction or networking permitted without license from IHS -,-,- 4 Environment and safety Not applicable 5 Algorithm id
41、entifier This algorithm shall be identified as 1016. An international registration authority for data transformations is in the process of being established. When the authority has been established, it will be identified in this stan- dard. 3.3code string:The encoded logical data record. The code st
42、ring comprises one or more code blocks appended in the order cor- responding to the original sequence of the blocks. 3.4data record, logical:The data entity that is the input to the data compactor. Usually provided by the host computer and may contain one or several host data records, depending on t
43、he host blocking factors. 3.5encoding:Process of generating code blocks from blocks. 3.6trailer:Bytes appended to the end of a code block. ANSI X3.225-1992 2 6 Compaction algorithm 6.1 General The logical data record is transformed to a code string by a one-pass, adaptive encoding tech- nique design
44、ed to provide lossless data compaction. The code string can be decompacted by a decoding technique to recover the exact logical data record that was originally transformed. The data compactor is comprised of eight identical encoders, numbered from 0 to 7. Eight tables, one for each encoder, are each
45、 set up with 256 pairs of entries. The first value of each pair is the esti- mated value of the input event to be encoded (0 or 1 binary) while the second value (K) is an approximate probability measure of the input event being equal to the estimated value. Kcan vary from 1 to 4 with the approximate
46、 probability shown in the table below. The probabilities are a measure of how much more likely it is that the input event to be encoded is equal to the estimated value rather than being unequal (i.e., for K= 2, the probability that the input event is equal to the estimated value is approximately 2 t
47、o 4 times as great as the probability that it will not be equal to the estimated value). KApproximate probability 112 224 348 4816 Prior to beginning the compacting of each logical data record, the tables are preset with all first values being 0 and all probabilities being 1. The logical data record
48、 is divided into 512-byte blocks, except for the last block which may be any length less than or equal to 512 bytes. The blocks are routed sequentially to the eight encoders, starting with encoder 0. If the logical data record contains more than 4096 bytes, the compactor returns to encoder 0 and repeats the process. The code string is assembled in the same order, with the first portion being that generated by encoder 0, the second by encoder 1, and so on. The output of each encoder is a code block. See figure 1. The first bit of the first code block is the