Variable Length Coding With Three-Field Codes

The present invention relates to variable length coding (VLC). Variable length coding is a widely-used method in data compression, especially, in the applications of video data communication and storage. Many international standards have adopted this technique in video data compression, for example, JPEG, MPEG, CCITT H.261 and so on.

Various implementation methods have been proposed for variable length coding. Most of those methods implement the coding with two-field codes. That is, a code is represented by a code word and a code length.

However, in this invention, a three-field representation is used for each variable length code. In comparison with the two-field representation, the three-field representation not only reduces the storage requirements of the code book but also reduces the hardware or cost to implement a variable length encoder. Moreover, the inventive variable length coding technique can be implemented using either a parallel VLC encoder or a serial VLC encoder.

In variable length coding, source symbols of a fixed length are encoded with codes of a variable length. Variable length coding is a widely used technique for lossless data compression. VLC has become part of some international standards for various applications, for example, still image coding, video image coding, facsimile coding, and so on.

The variable length coding technique encodes the frequently occurring fixed length source symbols with shorter codes and the infrequently occurring fixed length source symbols with longer codes. Thus, the VLC takes the advantage of a non-uniform distribution in the occurrence of the fixed length source symbols. In general, the length of the code for a fixed length source symbol is designed to be inversely proportional to the probability of the occurrence of the symbol. The most well-known example of a variable length code is the Huffman code.

As the codes are of non-equal length, the encoder should concatenate those codes to form a bit stream without gaps. This may be accomplished using a serial encoder or a parallel encoder. A serial encoder outputs one bit at a time. A parallel encoder outputs a group of bits (e.g., eight) at a time, in parallel. A parallel encoder generally contains circuitry for rearranging the variable length code words into groups of, e.g., eight bits. Conventional VLC techniques are disclosed in M. Stroppiana, L. Ronchetti, Device for reducing the redundancy in blocks of digital video data in DCT encoding U.S. Pat. No. 5006930, 1991.4.9., F. Azadegan, E. Fisch, Method and apparatus for digitally processing a high definition television augmentation signal U.S. Pat. No. 5128758, 1992.7.7., S. M. Lei, M. T. Sun, An Entropy Coding System for Digital HDTV Application, IEEE Trans. on Circuit and system for Video tech., vol. CASV-1, no. 1, pp. 147-155, Feb. 1991, F. Azadegan, Method and apparatus for digitally processing a high definition television augmentation signal, U.S. Pat. No. 5,179,442, 1993.1.12., G. J. Kustka, Variable length decoder, U.S. Pat. No. 5226082, 1993.7.6., K. C. Chu, etc., Variable length decoding using lookup tables, U.S. Pat. No. 5,253,053, 1993.10.12., H. Brusewitz, Method and means for variable length coding, U.S. Pat. No. 492,2510, 1990.5.1., F. Mikami, Variable-length coding/decoding device, U.S. Pat. No. 4,985,700, 1991.1,15., N. Shirota Coding and decoding apparatus of variable length data U.S. Pat. No. 5162795, 1992.11.10., which are incorporated herein by reference.

In most variable length coding systems, the variable length codes are represented by two-field codes. One field stores the code word and the other field records the corresponding code-length. FIG. 1 provides a variable length code for the transform coefficients in CCITT recommendation H.261. There are 127 fixed length source symbols. Each source symbol has two fields designated run and level. The level may be a positive or a negative value. A variable length code is associated with each source symbol. The "s" is "zero" or "one" depending on whether the level is a positive or negative quantity.

FIG. 2 is a table which shows a two-field code associated with each of the fixed length source symbols. One field is the code word length and the other field is the variable length code word itself.

FIG. 3 is a conventional variable length parallel encoder for implementing a codebook using a two-field representation such as shown in FIG. 1 and FIG. 2. The encoder 10 of FIG. 3 comprises two basic sections. The section 12 is a memory or other translation device which receives fixed length source codewords of n bits and outputs the variable length codes in a two field representation. The section 22 concatenates the variable length code words and arranges the variable length code words in groups of, e.g., eight bits for transmission.

In the illustrative encoder 10 of FIG. 3, the translation device 12 is a PLA. The PLA 12 comprises an AND plane 14 which receives the source symbols at the input 15. There are two OR-planes 16 and 18 in the PLA 12. The OR-plane 16 is for outputting the code word and the OR-plane 18 is for outputting the code length. The code word generated by the OR-plane 16 is latched in the register W.sub.o. The code length generated by the OR-plane 18 is latched by the register L.sub.o.

The output of the encoder is obtained from the register W.sub.2 at the output 20. It should be noted that the variable length code words are chosen so that no shorter code comprises a subset of the bits in a longer code. For this reason, a decoder cannot "mistakenly" recognize and decode a shorter code when it is supposed to receive a longer code. Thus, it is not necessary to explicitly transmit the code length information with each variable length code word. Rather, the code length information is used by the circuitry 22 in the encoder 10 to concatenate the variable length code words in groups of bits which are stored in parallel in the register W.sub.2.

The circuitry 22 comprises the barrel shifter BS.sub.1, the barrel shifter BS.sub.2, the code length accumulation circuit 19, and the registers W.sub.1 and W.sub.2. The code length accumulation circuit accumulates the code lengths latched in the register L.sub.0 in each cycle. The barrel shifters BS.sub.1 and BS.sub.2 operate as follows. In each cycle, the contents of W.sub.1 and W.sub.0 are concatenated and left shifted in the combined W.sub.1 W.sub.0 window by BS.sub.1 by a number of spaces determined by L.sub.0. The left most eight bits in the W.sub.1 W.sub.0 window are then written into W.sub.1. The code length accumulation circuit cumulates the contents of L.sub.0 over successive cycles by performing a sum of all code lengths stored in L.sub.0 (.SIGMA.L.sub.0) modulo W where W is the maximum length of the variable length code word (e.g. eight). The value .SIGMA. L.sub.0 mod W on a cycle i is the occupancy of the register W.sub.1 on cycle c+1. In determining .SIGMA. L.sub.0 mod W, the accumulation circuit periodically counts through overflow, i.e., W.

The accumulation circuit 19 outputs an appropriate shift count for the barrel shifter BS.sub.2. In the event the accumulation circuit 19 has not counted through overflow, BS.sub.2 is not enabled. Instead, the entire new variable length code will be shifted into, and concatenated with, the contents of W.sub.1. In the event the accumulation circuit has counted through overflow on a cycle i+1, BS.sub.2 is enabled and provided with the shift count 8 minus the value .SIGMA. L.sub.0 modulus 8 determined for the cycle i. As a result, BS.sub.2 outputs the W=8 left most bits of the shifted window W.sub.1 W.sub.0 for storage in the register W.sub.2, The outputted W=8 bits includes the contents of the register W.sub.1 on the cycle i followed by at least one bit of the new variable length code in W.sub.0 concatenated thereto.

In each cycle where the accumulator circuit cycles through zero, it outputs a control signal to BS.sub.2 to control the shift from window W.sub.1 W.sub.0 to W.sub.2. Thus, this shift will only take place if the window W.sub.1 W.sub.0 contains at least W=8 bits.

FIG. 4 is a table which shows the values of W.sub.0, W.sub.1, W.sub.2, L.sub.0, and .SIGMA. L.sub.0 mod W in an example where W=8 for each of five cycles.

The example encoder shown in FIG. 3 is a conventional parallel encoder. The encoder complexity will depend on the code book. Let the code book length be N and the longest code-length be W. The bit number to represent the code-length will be .left brkt-top.l=log.sub.2 W.right brkt-top. where .left brkt-top.x.right brkt-top. ceiling or least integer less than or equal to x. Let the fixed length source symbol input to the PLA 12 be n bits. We can estimate the gate count required by the components in the encoder of FIG. 3 roughly as follows.

PLA: (n+W+l) N.times.1 gates

registers: (3W+l).times.8 gates

barrel shifters: {2[W+2W]W/2+2Wl}.times.1 gates

accumulator: l.times.8+l.times.9 gates

Totally, the number of gates required by this conventional encoder (which uses a two-field representation for each variable length codeword) is approximately

Therefore, the system complexity (or cost) is approximately proportional to the square of W. As the longest code length increases, the complexity of the encoder will increase. Consider the case where W=14, N=127, n=9, and l=4. In this case T.sub.0 =4565.

In view of the foregoing, it is an object of the invention to provide a VLC encoding technique which utilizes an encoder of reduced complexity.

It is also an object of the invention to provide a VLC encoding technique which reduces the storage requirements of a VLC code book.

This and other objects are achieved by the present invention. An examination of each variable length code in a typical code book or variable length code table reveals that each variable length code can be divided into three constituent fields. In particular, each variable length code word can be divided into a vacant code, followed by a separator bit and a prime code. The vacant code is a variable length sequence of bits which are all the same logic bit value, i.e., all logic `1` or all logic `0`. The prime code is also a variable length sequence of bits. However, the logic bit values of the prime code can vary. The separator bit is the opposite logic bit value as is contained in the vacant code.

Such a decomposition of the variable length codes into three fields allows for compaction of the variable length code book or table.

According to one embodiment of the invention, a method for variable length encoding a fixed length code word comprises the step of converting a fixed length source symbol into a prime code, a prime code length and a vacant code length. For instance, the fixed length source symbol can be received at a PLA which is programmed to produce a unique combination of prime code, prime code length and vacant code length for each possible fixed length source symbol. The prime code, prime code length and vacant code length are then converted to a variable length code. For instance, in a given variable length code book or table, the logic bit value used to form the vacant code is predetermined. A vacant code can thus easily be generated from the vacant code length. The vacant code is concatenated to an appropriate logic bit value separator bit and then to the prime code to produce the variable length code.

The foregoing may be accomplished in a serial encoder or a parallel encoder .

FIG. 1 is table which associates a variable length code word with each of a plurality of fixed length source symbols.

FIG. 2 is a table which associates a two field representation of a variable length code with each of a plurality of fixed length source symbols.

FIG. 3 is a conventional parallel encoder which implements a variable length code table using a two field representation for each variable length code.

FIG. 4 is a table which illustrates the operation of the encoder of FIG. 3.

FIG. 5 is a table which associates a three field representation of a variable length code with each of a plurality of fixed length source symbols, according to an embodiment of the invention.

FIG. 6 is a parallel variable length encoder which implements a variable length code table using a three field representation for each variable length code, according to an embodiment of the invention.

In order to understand the invention, it is useful to consider how three fields may be used to represent each VLC code word. FIG. 5 is a table which implements the variable length code of FIG. 2 but using a three-field, rather than a two-field, representation. The variable length code words of FIG. 5 require a maximum of only 12 bits when the three field representation is used. This contrast with a maximum of 18 bits for the two field representation of FIG. 2.

To explain the three fields representation, it is useful to define the terms prime code and vacant code. A variable length code usually has a string of leading zeros (or leading ones). The leading part can be called vacant code. Following the vacant code, the first bit (which can be referred to as a separator bit) must be the opposite logic bit value as the vacant code. That is, if the vacant code is a string of leading zeros, the separator bit is one and if the vacant code is a string of leading ones, the separator bit is zero. Following the separator bit, there is part of a code called prime code. These are illustrated as follows:

Some code sets may begin with a string of leading ones. They can also be partitioned into vacant code and prime code separated by a separator bit. (The separator bit always has the opposite polarity of the bits in the vacant code). For example:

Taking this into account, it is noted that according to the invention, a variable length code can be represented by a triplet of prime code, prime code length (including one bit position for the separator bit) and a vacant code length, instead of a pair of codeword and code length. With this three-field representation, the storage requirements of a code book can be reduced; also the encoder can be reduced in complexity.

FIG. 6 schematically illustrates a variable length encoder 100 which utilizes the three field representation for variable length coder. The variable length encoder 100 comprises a first section 110 which comprises a translation circuit which receives fixed length source symbols at an input 112 and outputs variable length codes in a three-field representation.

Specifically, the translation circuit 110 comprises a PLA having an AND-plane 114 and three OR-planes 115, 117, 119 which output the three field representation of each variable length code. The OR-plane 115 outputs a prime code. The OR-plane 117 outputs a prime code length. The OR-plane 119 outputs a vacant code length.

The encoder 100 also comprises a second section 120. The circuitry of section 120 converts the three-field representations of variable length code words into the variable length codewords themselves and concatenates the variable length codewords. The circuitry 120 operates as follows.

Suppose a fixed length source symbol arrives at input 112, which fixed length source symbol has the variable length code `00011101`, including a three bit vacant code `000`, a separator bit of `1` and a four bit prime code `1101`. Furthermore, suppose the value `101111` is currently stored in the register W.sub.1.

First, the fixed length source symbol causes the PLA 110 to output the vacant code length of 3, the prime code length of 5 and the prime code of `1101`. (The prime code length is the length of the prime code and separator bit). The vacant code length and prime code length are added together in the adder circuit 122 to produce the total length 8 which is stored in register L.sub.0. Meanwhile, the prime code length is inputted to a barrel shifter BS.sub.3 which shifts a separator bit, in this case logic `1`, five bit positions to the left. The barrel shifter BS.sub.3 is controlled to mask out each other bit of the input thereby producing a byte containing zero valued bits, except for the bit position designated by the prime code length, in this case, the 5.sup.th bit position from the right, which contains the separator bit. The barrel shifter BS.sub.3 therefore outputs the value `00010000`. The value `00010000` outputted by the barrel shifter BS.sub.3 is logically OR'ed with the prime code outputted from the PLA in the OR circuit OR.sub.3 to produce the value `00011101`. This value `00011101` is stored in the register W.sub.0.

In this manner the separator bit is appended to the prime code.

The value `xx101111` (where "x" indicates "don't care" bits) stored in the register W.sub.1 is outputted to a barrel shifter BS.sub.1 as an eight bit window of the barrel shifter BS.sub.1. The barrel shifter BS.sub.1 receives the length stored in the register L.sub.0 as a shift count, in this case, 8. The barrel shifter BS.sub.1 is operated to left shift its input a number of bit positions as designated by the shift count inputted thereto and to output the eight rightmost bits of the shifted result. When left shifting, the logic bit value `0` is inserted into the vacated right most bit positions. Therefore, the window `xx101111` is left shifted 8 bit positions to produce `xx101111 00000000`, of which `00000000` is outputted from the barrel shifter BS.sub.1.

The value `00000000` outputted from the barrel shifter BS.sub.1 is inputted to OR gate OR.sub.1 which also receives the value `00011101` stored in W.sub.0 as an input. The OR gate OR.sub.1 logically OR's these two values `00000000` and `00011101` to produce the value `00011101` which is stored in the register W.sub.1, thereby overwriting the contents previously stored therein. As will be discussed in greater detail below, the first two bits of the value `00011101` are simultaneously concatenated with the former contents of the register W.sub.1 for shifting out. Thus, there may be overlapping bits that are stored in both the registers W.sub.1 and W.sub.2. For purposes of clarity, the overlapping bits in register W.sub.1 are treated as "don't care" bits since they will be discarded. Thus, as a matter of notation, the register W.sub.1 is said to store the value `xx011101`.

Meanwhile, the code length 8 stored in register L.sub.0 is also outputted to an accumulation circuit 124. The accumulation circuit 124 determines a total modulo 8 sum of the lengths of all variable length codes produced in the inventive circuit, i.e., .SIGMA. L.sub.0 modulo W=8. For instance, assume that the previously determined variable length code had a length of 6. Therefore, the total modulo 8 length is 6 (8+6 mod 8=6). The modulo 8 count indicates two things:

(1) whether or not the concatenation of the current variable length code to the contents of the register W.sub.1 comprises at least W=8 bits (which W=8 bits can be transferred into the register W.sub.2), and

(2) during the cycle i, the occupancy of the register W.sub.1 for the next cycle i+1.

In this case, six bits were previously stored in the register W.sub.1 and another eight bit variable length code was produced. Since the variable length codes are concatenated and outputted in eight bit units, eight of the fourteen bits will be outputted and six bits will remain in the register W.sub.1. As discussed in greater detail below, the eight bits to be outputted will include the six bits `101111` previously stored in the register W.sub.1 concatenated to the first two bits `00` of the current variable length code `000111101` most recently formed.

The accumulation circuit determines that there are at least W=8 bits available for output whenever the modulo eight accumulation circuit counts through overflow (i.e., W). In such a case, the accumulation circuit outputs a control signal for enabling the barrel shifters BS.sub.2 and BS.sub.4.

Furthermore, the accumulation circuit 124 outputs an appropriate shift count for the barrel shifters BS.sub.2 and BS.sub.4. In the event the accumulation circuit has not counted through overflow, BS.sub.2 and BS.sub.4 are not enabled. However, in the event the accumulation circuit has counted through overflow in a cycle i+1, the shift count is the difference of 8 minus .SIGMA. L.sub.0 modulo 8 for cycle i.

Note that this manner of operation reflects the sum of the occupancy of the register W.sub.1 plus the length of the current variable length code. .SIGMA. L.sub.0 modulo W on a cycle i is the occupancy of W.sub.1 on cycle i+1. If in determining .SIGMA. L.sub.0 modulo W on cycle i+1, the accumulation circuit does not count through overflow, then the concatenation of the current variable length code to the contents of W.sub.1 is less than W=8 bits long. If in determining .SIGMA. L.sub.0 modulo W on cycle i+1, the accumulation circuit counts through overflow, then the concatenation of the current variable length code to the contents of W.sub.1 contains at least W=8 bits. Therefore, by enabling BS.sub.2 and BS.sub.4, the W=8 bits including the contents of W.sub.1 followed by at least some of the bits of the current variable length code concatenated thereto are transferred to the register W.sub.2. (The remaining bits of the current variable length code not transferred are stored in W.sub.1 by BS.sub.1 and OR.sub.1) However, in order to shift the window W.sub.1 W.sub.0 to output W=8 bits, the window W.sub.1 W.sub.0 must be shifted by a number of bits equal to W less the occupancy of W.sub.1 on cycle i or 8-.SIGMA.L.sub.0 modulo 8 for cycle i.

In this case, the accumulation circuit counts through overflow so the bits `xx101111` in W.sub.1 will be concatenated with at least some of the bits of the recently generated variable length code `00011101`. In particular, the accumulation circuit indicates that the occupancy of W.sub.1 on the previous cycle i was 6. Therefore, 8-6 or 2 bits must be concatenated with the value `xx101111` prior to transfer to the register W.sub.2. The accumulation circuit therefore outputs 2 to the barrel shifters BS.sub.2 and BS.sub.4.

The barrel shifter BS.sub.2 receives the value `xx101111` outputted from the register W.sub.1. The barrel shifter BS.sub.2 left shifts the received byte a number of bit positions as indicated by the shift count received from the accumulation circuit, i.e., 2, and outputs the shifted byte of the shifted window. BS.sub.2 shifts in zeros into the vacated right most bit positions. Thus, the barrel shifter BS.sub.2 outputs the value `10111100`.

The barrel shifter BS.sub.4 receives a sixteen bit window comprising `00000000` as the left most byte and the variable length code `00011101` as the right most byte. The barrel shifter BS.sub.4 left shifts the window a number of bit positions as indicated by the shift count received from the accumulation circuit, i.e., 2, and outputs the leftmost byte of the shifted window. Thus, the barrel shifter BS.sub.4 outputs the value `00000000` comprising the six least significant bits `000000` of the leftmost byte `00000000` of the window and the two most significant bits `00` of the rightmost byte `00011101` of the window.

The values produced by the barrel shifter BS.sub.4, i.e., `00000000` and the barrel shifter BS.sub.2, i.e., `10111100` are inputted to OR gate OR.sub.2 where they are logically OR'ed. This produces the result `10111100` comprising the six bits of the register W.sub.1 and the first two bits of the variable length code `00011101`. This produced value `10111100` is then stored in the register W.sub.2 and the prior contents of the register W.sub.2 are outputted.

Note that part of the variable length code 00011101 which is produced (namely, the two most significant bits `00`) is immediately concatenated with previous data stored in the register W.sub.1 for output via the register W.sub.2. Thus, there is an overlap in the register W.sub.1 of the two most significant bits which have already been outputted. However, these bits are discarded in the next shift operation and can be treated as "don't care" bits as indicated above.

The complexity of the inventive encoder 100 of FIG. 6 may be determined and compared with the complexity of the conventional encoder of FIG. 3. Let the length of the considered code book be N and its longest code length be W. If the maximum prime code length is W.sub.p, the bit number to represent the prime code length will be l.sub.p =.left brkt-top.log.sub.2 W.sub.p .right brkt-top.. Also, let the vacant code length be represented by l.sub.v bits and the data input to PLA be n bits. We can estimate that gate count required by those components roughly as follows.

PLA: (n+W.sub.p +l.sub.p +l.sub.v) N.times.1 gates

registers: (2W+W.sub.p +l).times.8 gates

barrel shifters: (2W(W-1)+2(W-1)+Wp.sup.2 +Wp.sup.2 /2+2W.sub.p l.sub.l).times.1 gates

accumulator: l.times.8+l.times.9 gates

adder: max (l.sub.p, l.sub.v).times.9 gates

OR gates: 3 (W.sub.p +1).times.1 gates

Totally, the number of gates required for the improved system is approximately

Then, the comparison of the complexity of the conventional approach and the improved approach can be expressed by

In most of the cases, the W.sub.p +l.sub.p +l.sub.v will be less than W+l. Also, W.sub.p .sup.2 is much less than W.sup.2. Therefore, in most of the cases, the invention method will be more cost-effective than the conventional method.

Consider the code book shown in FIG. 5 as an example. These parameters will be as follows.

W=14

N=127

n=9

l=4

W.sub.p =6

l.sub.p =3

l.sub.o =4

Then,

T.sub.0 =4565

and

T.sub.1 =3603

It can be seen that about 25% of the gate count can be saved.

In short, a new variable length coding technique is disclosed. Each code word is represented by three fields rather than the conventional two fields. As shown above, the inventive method can reduce the implementation cost of a parallel variable length encoder. The example given above shows that the invention can save 25% of the encoder circuit. However, the percentage is dependent on the code book. When the code book is large, the percentage will become more significant than for that of small code book. The inventive technique is applicable to a variety of video encoding standards. The storage requirements for the codebook are reduced. Moreover, the inventive technique can be implemented in serial as well as parallel encoders.

Finally, the above-described embodiments of the invention are intended to be illustrative only. Numerous alternative embodiments may be devised by those skilled in the art without departing from the scope of the following claims.