Overview
ISO/IEC 12042:1993, "Information technology - Data compression for information interchange - Binary arithmetic coding algorithm," defines a lossless binary arithmetic coding algorithm intended for interoperable data interchange. The standard specifies a one-pass, adaptive encoding technique that reduces the number of bits required to represent information (data compression) while guaranteeing exact recovery of the original Logical Data Record (LDR). The algorithm is registered in the international algorithm register with identifier 16.
Key topics and technical requirements
- Compression type: Lossless data compression using binary arithmetic coding.
- Data unit definitions: Logical Data Record (LDR), block (typically 512 bytes), Code Block, Code String, trailer, and input event (bit or byte depending on mode).
- Encoder architecture: Eight encoders (numbered 0–7) accept sequential 512‑byte blocks; encoders cycle for records longer than 4 096 bytes.
- Adaptive tables: Each encoder maintains 256 Table Pairs (first 255 for normal use; the 256th is the Unique Table Pair for Run Mode). Table Pairs store an Estimated Value (EV, 0 or 1) and a K parameter (1–4) that measures probability. All EVs initialize to 0 and all Ks to 1 prior to encoding.
- Two operating modes:
- Normal Mode - byte-by-byte processing with bit-wise arithmetic coding; uses Table Pairs selected by previously encoded bits.
- Run Mode - activated when repeated identical bytes occur; uses the Unique Table Pair to exploit runs of identical bytes and can switch back to Normal Mode.
- Arithmetic coding internals: Uses fractional binary Current Value (CV) and Width to generate output bits; rules defined for when input matches EV vs. when it does not, including shifting, appending bits, and updating K/EV with a small counter.
- Output formatting: Encoders produce Code Blocks padded to byte boundaries and terminated with a two‑byte trailer (Trailer Byte 1 = 0xFF; Trailer Byte 2 contains flags and pad-bit counts). Pad byte 0x00 may be appended to ensure even byte counts.
- Conformance: Implementations must satisfy the mandatory requirements in the standard; normative references include algorithm registration procedures.
Applications
- Interchangeable compression for high‑density recording media (magnetic tape, optical cartridge) and archival systems where lossless compression and interoperability are required.
- Embedded or stand‑alone compressors/decoders in storage hardware, backup systems, media interchange formats, and software codecs that must follow an international standard for binary arithmetic coding.
- Use cases that benefit from adaptive, run‑aware compression such as repetitive-byte data streams, telemetry, and legacy data formats.
Who should use this standard
- Codec and compression algorithm implementers and integrators
- Storage system and media manufacturers aiming for interoperable compressed formats
- Archivists and data interchange developers requiring normative, registered compression algorithms
- Standards bodies and testing laboratories verifying conformance to registered lossless compression schemes
Related standards
- ISO/IEC 11558 - Adaptive Coding with Embedded Dictionary (BCLZ algorithm) - earlier in the same series.
- ISO/IEC 11576:1993 - Procedure for registration of algorithms for lossless compression of data (referenced for registration and conformance).
Keywords: ISO/IEC 12042:1993, binary arithmetic coding algorithm, lossless data compression, data interchange standard, Table Pair, Run Mode, Code Block, Logical Data Record.
Open preview (PDF)Information technology — Data compression for information interchange — Binary arithmetic coding algorithm
