Zero-run-length encoder with shift register

Abstract

A zero-run-length encoder for a JPEG compression system comprises an addressable memory for storing 63 input values (quantized AC DCT coefficients), zero-detection logic, a shift register, a value generator, an accumulator, a Huffman encoder, done-detection logic, and last-value-detection logic. For each input value, the zero-detection logic stores zero/nonzero indications in a respective bit position of the shift register. The value generator includes a leading-zero counter that determines the number of leading zeroes in the leading fifteen bit positions of the shift register. This count is used to determine an offset value which is added to a previous address value (initially zero) to yield a present address value. The present address value is used to select a memory location from which an input value is read from memory into the Huffman encoder. The Huffman encoder generates an output code as a function of the addressed input value and the leading zero count. The leading zero count is also used as a basis for the amount the contents of the shift register are shifted to begin the next code cycle. The done-detection logic determines when the shift register contains only zeroes; in that case, the input cycle ends, the accumulator is reset to zero and a new set of input values can be accepted. In addition, the done indication results in an EOB ('end of block') code being generated unless the last-value-detection logic indicates that the present address corresponds to the last (highest order term) input value. The action of the shift register allows the zero-run-length encoder to skip cycles in which zero input values would be processed. Thus, simple, high performance hardware zero-run-length encoding is achieved.