Zero-run-length encoder with shift register

• US 5,764,357 A
• Filed: 04/12/1996
• Issued: 06/09/1998
• Est. Priority Date: 04/12/1996
• Status: Expired due to Term

• Current Assignee: Callahan Cellular LLC (Intellectual Ventures LLC)
• Original Assignee: VLSI Technology, Inc. (Koninklijke Philips N.V.)
• Inventors: Dockser, Kenneth A.
• Primary Examiner(s): LEE, TOMMY D
• Application Number:
  US08/631,264
• Time in Patent Office: 788 Days
• Field of Search: 358/261.1, 358/427, 358/261.4, 358/426, 358/431, 358/530, 358/539, 382/232, 382/234, 382/245, 382/246, 341/59, 341/63, 341/65, 341/67
• US Class Current: 382/246
• CPC Class Codes: H04N 1/415 in which the picture-elements are subdivided or grouped into fixed one-dimensional or two-dimensional blocks
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

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.

Claims

1. A zero-run-length encoder comprising:

memory having addressable memory locations for collectively storing a respective series of input values, said memory having an address input for receiving a present address value corresponding to one of said memory locations, said memory having a memory output from which it provides the input value stored at said memory location;

a shift register having bit positions corresponding to respective ones of said memory locations, said shift register having a leading section of bit positions and a trailing section of bit positions, said shift register having a shift value input for receiving a shift value, said shift register shifting indications stored in said bit positions so that at least some indications stored in said trailing section are moved to said leading section;

zero-detection logic for storing zero-versus-nonzero indications in said shift register, said zero-detection logic storing at each bit position an indication whether or not the input value stored at the respective memory location is zero or nonzero, said zero indictor logic being coupled to said memory for determining said indications, said zero indicator logic being coupled to said shift register for storing said indications therein;

a value generator for generating a code value, a shift value, and an offset value as a function of the number of leading zeroes in said leading section of said shift register, said value generator being coupled to said shift register;

an accumulator for adding said offset value to a previous address value to obtain said present address value, said accumulator being coupled to said address input of said memory for providing said present address value thereto; and

an entropy encoder for providing an output code as a function of the input value provided at said memory output and said code value, said entropy encoder being coupled to said memory output and said value generator.

2. A zero-run-length encoding method comprising:

a) storing a series of input values in a memory with addressable memory locations;

b) storing indications whether or not the input value stored in each of said memory locations is zero in respective bit positions of a shift register having leading and trailing sections;

c) generating a code value, a shift value, and an offset value as a function of the number of leading zeroes in said leading section of said shift register;

d) adding said offset value to a previous address value to yield a present address value;

e) generating an entropy code as a function of said code value and of the input value stored at the memory location addressed by said present address value; and

f) shift the indications stored in said shift register as a function of said shift value in the direction from said trailing section to said leading section, and returning to step c.

3. A method as recited in claim 2 further characterized in that in step f, bit positions of said shift register vacated by a shift are filled with zero indications.

4. A method as recited in claim 2 further comprising a step of determining when said shift register contains only zero indications and, in that event, returning to step a.