ANSI INCITS 225-1992 Information Systems C Compaction Algorithm C Binary Arithmetic Coding.pdf

1、ANSI INCITS 225-1992 (R2004)(formerly ANSI X3.1992 (R1999) for Information Systems Compaction Algorithm Binary Arithmetic CodingAmericanNationalStandardApproval of an American National Standard requires review by ANSI that therequirements for due process, consensus, and other criteria for approval h

2、avebeen met by the standards developer.Consensus is established when, in the judgment of the ANSI Board of StandardsReview, substantial agreement has been reached by directly and materiallyaffected interests. Substantial agreement means much more than a simplemajority, but not necessarily unanimity.

3、 Consensus requires that all views andobjections be considered, and that a concerted effort be made toward theirresolution.The use of American National Standards is completely voluntary; their existencedoes not in any respect preclude anyone, whether he has approved the standardsor not, from manufac

4、turing, marketing, purchasing, or using products, processes,or procedures not conforming to the standards.The American National Standards Institute does not develop standards and will inno circumstances give an interpretation of any American National Standard.Moreover, no person shall have the right

5、 or authority to issue an interpretation ofan American National Standard in the name of the American National StandardsInstitute. Requests for interpretations should be addressed to the secretariat orsponsor whose name appears on the title page of this standard.CAUTION NOTICE: This American National

6、 Standard may be revised orwithdrawn at any time. The procedures of the American National StandardsInstitute require that action be taken periodically to reaffirm, revise, or withdrawthis standard. Purchasers of American National Standards may receive currentinformation on all standards by calling o

7、r writing the American National StandardsInstitute.Published byAmerican National Standards Institute11 West 42nd Street, New York, New York 10036Copyright 1992 by Information Technology Industry Council (ITI)All rights reserved.No part of this publication may be reproduced in anyform, in an electron

8、ic retrieval system or otherwise,without prior written permission of ITI, 1250 Eye Street NW,Washington, DC 20005.Printed in the United States of AmericaANSIX3.1992 (R1999) American National Standardfor Information Systems Compact Algorithm Binary Arithmetic CodingSecretariatComputer and Business Eq

9、uipment Manufacturers AssociationApproved American National Standards Institute, Inc.iiContentsPageForeword .iii1 Scope and purpose 12 Normative references.13 Definitions .14 Environment and safety25 Algorithm identifier .26 Compaction algorithm 2Figure1 Code block.3AnnexesA Pseudo code description

10、of algorithm6B Bibliography.12iiiForeword (This foreword is not part of American National Standard X3.225-1992.)This standard presents requirements for compacting data to be used forinformation interchange among processing systems, communication sys-tems, and associated equipment. This standard deal

11、s solely with compact-ing data. The X3B5 Subcommittee on Magnetic Tape, which developed thisstandard, consists of experienced and qualified specialists on manufactur-ing magnetic tape, on recording digital information on magnetic tape, andon the compaction algorithms used to process the digital info

12、rmation. Thisalgorithm represents a significant advancement in the way data is recordedon magnetic media, providing higher data rates and greater volumetric effi-ciency. In the development of this standard careful consideration was givento current practices, existing equipment and supplies, and the

13、broadestpossible acceptance, and to providing a basis for future improvements inthe use of the algorithm. The standard contains specifications for a compaction algorithm. The textof this standard differs from the corresponding ISO and ECMA standards,International Standard for Information technology

14、Data compression forinformation interchange Binary arithmetic coding algorithm, ISO 12042,and Data compression for information interchange 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 anne

15、x A and B are informa-tive and are not considered part of this standard. Requests for interpretation, suggestions for improvement or addenda, ordefect reports are welcome. They should be sent to the X3 Secretariat,Computer and Business Equipment Manufacturers Association, 1250 EyeStreet, NW, Suite 2

16、00, Washington, DC 20005.This standard was processed and approved for submittal to ANSI byAccredited Standards Committee on Information Processing Systems, X3.Committee approval of the standard does not necessarily imply that allmembers voted for its approval. At the time it approved this standard,

17、theX3 Committee had the following members:ivHarold L. BookPeter BramhallJames T. CrazeMike DeeseRobert F. DriscalGary R. EarlyJames A. EggebeenArthur FreemanMichael GalataDana S. GrubbKirk HandleyMichael L. HelselHakan HemdalHarry C. Hinz, Jr.David M. HudsonKyriacos JoannouRandy KernsBill KingRichar

18、d LeeJack MarionKazuyuki Masukane William MealeyBill MedlinskiT. MitsutomiGary D. MoellerTom MolstadGerrit NijssenPete PassarettiKeith PollockEd RhodesMaritza RobbennoltHoward RobinsonArnold J. RoccatiJoe ShimizuHerman StrassJames V. Tierney, IIIHenry G. TobinCharles WellingtonDouglas WhitingDavid M

19、. WilsonKirk D. WilsonJames W. WolfKei Yamashita Joseph S. Zajaczkowski Bob Abe (Alt.)Robert B. Anthony (Alt.)Leonard Badour (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

20、 Fannin (Alt.)Howard Flagg (Alt.)John Fleming (Alt.)Lonnie Ford (Alt.)Shoji Fujiwara (Alt.)Jerry Ganske (Alt.)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

21、(Alt.)Steve Krupa (Alt.)Carl Labmeier (Alt.)Stephen Leader (Alt.)Demetrios Lignos (Alt.)George 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

22、.)Eddie T. Morioka (Alt.)Robert Morris (Alt.)Yoshikazu Nakamura (Alt.)Gary Nelson (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.)Rob

23、ert L. Simpson (Alt.)Leif Skaar (Alt.)Jun Takayama (Alt.)Gerald Taylor (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 developedthis standard, had the following members:R

24、ichard T. Steinbrenner, ChairSamuel D. Cheatham, Vice-Chair1 Scope and purpose1.1 ScopeThis standard provides the information neces-sary to ensure interchangeability of compact-ed data between information processing sys-tems, communication systems, and associatedequipment using standard code as agre

25、edupon by the interchange parties. This stan-dard deals solely with the requirements forusing the compaction algorithm.CAUTION The users attention is called to thepossibility that compliance with this standard mayrequire use of an invention covered by patentrights. By publication of this standard, n

26、o positionis taken with respect to the validity of this claim orof any patent rights in connection therewith.However, the patent holder has filed a statementof willingness to grant a license under these rightson reasonable and nondiscriminatory terms andconditions to applicants desiring to obtain su

27、ch alicense. Details may be obtained from the publish-er. No representation or warranty is made orimplied that this is the only license that may berequired to avoid infringement in the use of thisstandard. 1.2 Purpose This standard defines the requirements nec-essary to ensure interchange. It is dis

28、tinctfrom a specification in that it delineates a min-imum number of restrictions consistent withcompatibility in interchange transactions.Wherever feasible, quantitative requirementsthat shall be met or exceeded in order to com-ply with this standard are given. In all cases,including those in which

29、 quantitative limits forrequirements falling within the scope of thisstandard are not stated but left to agreementbetween interchange parties, standard testmethods and measurement procedures shallbe used to determine such limits. Except as indicated above, interchange par-ties complying with the app

30、licable standardsshould be able to achieve compatibility with-out the need for additional exchange of tech-nical information.1.3 Conformance A binary arithmetic coding algorithm conformsto this standard if it satisfies all mandatoryrequirements of this standard. 2 Normative referencesThe following s

31、tandard contains provisionswhich, through reference in this text, constituteprovisions of this American National Standard.At the time of publication, the edition indicatedwas valid. All standards are subject to revision,and parties to agreements based on thisAmerican National Standard are encouraged

32、 toinvestigate the possibility of applying the mostrecent edition of the standard indicated below. ANSI X3.172-1990, Information systems Dictionary for information processing systems3 DefinitionsThe following definitions, listed in alphabeticalorder, and those given in the ANSI X3.172,apply to this

33、standard:3.1 block: A sequential 512-byte portion ofthe logical data record. The logical datarecord is compacted on block boundaries.3.2 code block: The encoded block with atrailer appended.1American National Standardfor Information Systems Compaction Alogorithm Binary Arithmetic CodingAMERICAN NATI

34、ONAL STANDARD ANSI X3.225-19924 Environment and safety Not applicable5 Algorithm identifierThis algorithm shall be identified as 1016.An international registration authority for datatransformations is in the process of beingestablished. When the authority has beenestablished, it will be identified i

35、n this stan-dard.3.3 code string: The encoded logical datarecord. The code string comprises one ormore code blocks appended in the order cor-responding to the original sequence of theblocks.3.4 data record, logical: The data entitythat is the input to the data compactor.Usually provided by the host

36、computer andmay contain one or several host data records,depending on the host blocking factors.3.5 encoding: Process of generating codeblocks from blocks. 3.6 trailer: Bytes appended to the end of acode block.ANSI X3.225-199226 Compaction algorithm6.1 General The logical data record is transformed

37、to a code string by a one-pass, adaptive encoding tech-nique designed to provide lossless data compaction. The code string can be decompacted by adecoding technique to recover the exact logical data record that was originally transformed. Thedata compactor is comprised of eight identical encoders, n

38、umbered from 0 to 7. Eight tables, onefor each encoder, are each 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 anapproximate probability measure of the input event being equal to t

39、he estimated value. K can varyfrom 1 to 4 with the approximate probability shown in the table below. The probabilities are ameasure of how much more likely it is that the input event to be encoded is equal to the estimatedvalue rather than being unequal (i.e., for K = 2, the probability that the inp

40、ut event is equal to theestimated value is approximately 2 to 4 times as great as the probability that it will not be equal tothe estimated value). K Approximate probability1 122 243 484 816Prior to beginning the compacting of each logical data record, the tables are preset with all firstvalues bein

41、g 0 and all probabilities being 1.The logical data record is divided into 512-byte blocks, except for the last block which may beany length less than or equal to 512 bytes. The blocks are routed sequentially to the eightencoders, starting with encoder 0. If the logical data record contains more than

42、 4096 bytes, thecompactor returns to encoder 0 and repeats the process. The code string is assembled in thesame 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

43、 block is thefirst bit of the code string. Since the compaction achieved depends on the relative frequency ofthe bit patterns in the logical data record and the presence of sequences of like bytes, the lengthof the code block cannot be predicted in advance. Trailer bytes are appended to form the com

44、-plete code blocks and to assist in the decompaction process.The trailer is composed of 2 bytes. The first byte is FF16. The second byte, bits 03, are 11002ifthis code block was generated from the last block of the data record. Otherwise, it is 10012. Bit 4is set to 02if the code block, as encoded,

45、is an even number of bytes. Otherwise, it is set to a 12.Bits 57 are set equal to the binary number of ZEROs that were added to the last byte of the codeblock to form an 8-bit byte. The code block shall end on an even byte boundary. A byte equal to0016is appended to the code block after the trailer

46、is added, if necessary, to make the code blockbyte count even.The sequence of bytes within all data structures and the position and significance of the bits with-in the bytes shall be as follows:Byte sequence 1 2 3NBits 0 to 7 8 to 15 16 to 238N to 8N+7where the leftmost bits within a byte and the l

47、eftmost bytes are the most significant and the right-most bits within a byte and the rightmost bytes are the least significant.6.2 EncodingBlock encoding is described in 6.2.1 to 6.3. The data is compacted on a byte basis within a block.Each byte is sequentially fetched from the block, starting with

48、 the first (most significant) byte, andcompared with the previous byte. The first byte in a block is compared to 4016. If the current byteis different than the previous byte and run mode is not enabled, then the byte is encoded, bit bybit, in normal mode. See 6.2.1 and 6.2.4 for more information on

49、normal mode and run mode,respectively. After the last byte of the block has been encoded, the encoding process is complet-ed by flushing the remaining compacted data from the encoder. 6.2.1 Byte encoding Normal modeWhen the current byte is to be encoded in normal mode, the following process occurs on a bit-by-bit basis. The most significant bit of the byte is encoded first and the least significant bit of thebyte is encoded last. Once the first bit of the byte is ready to be encoded, the first table pair forthe encoder is called, and the bit to be