Random Access Decompression using Binary Arithmetic Coding

We present an algorithm based on arithmetic coding that allows decompression to start at any point in the compressed file. This random access requirement poses some restrictions on the implementation of arithmetic coding and on the model used. Our main application area is executable code compression for computer systems where machine instructions are decompressed on-the-fly before execution. We focus on the decompression side of arithmetic coding and we propose a fast decoding scheme based on finite state machines. Furthermore, we present a method to decode multiple bits per cycle, while keeping the size of the decoder small. 1 Introduction There are some applications where decompression cannot be sequential and batch mode. An example is code compression for embedded systems where in order to save memory space, executable programs are stored in compressed format in memory and are decompressed during execution [14] [10] [2] [9]. Clearly, as programs execute nonlinearly due to jumps, d..