KR100195716B1 - A variable length decoder - Google Patents

Abstract

The present invention relates to a variable length decoder, comprising: a variable length decoder core (20) for barrel-shifting a variable length coded bit string by the length of a variable length code and cutting the variable length code into a maximum length of the variable length code; A zero detector (23) for checking whether a predetermined constant bit of the variable length code output from the variable length decoder core (20) is 0 or 1 and outputting a control signal according to the result; A code multiplexer (24) for outputting only a part of the variable length code output from the variable length decoder core (20) according to the control signal of the zero detector (23); A control unit 25 for receiving a variable length code and header information output from the variable length decoder core 20 and outputting a table selection signal; The variable length code input from the code multiplexer 24 is decoded through each PLA table according to the control signal output from the zero detection unit 23, and each of the table selection signals input from the control unit 25 is decoded. By selecting any one of the values decoded through the PLA table, input information of a variable length code is input to the variable length decoder core 20, and header information is input to the controller 25, while (run, level) The value comprises a table portion 30 cffur through the buffer 27 to the line-length decoder 29, which not only can significantly reduce the fanout of the output stage of the variable length decoder core, but also variable length decoding. Can be done quickly, and the size of the PLA table can be reduced. .

Description

Variable length decoder

1 is a schematic block diagram of an image encoder.

2 is a schematic block diagram of an image decoder.

3 is a schematic block diagram of a conventional variable length decoder.

4 is a schematic block diagram of a variable length decoder according to the present invention.

* Explanation of symbols for main parts of the drawings

20: variable length decoder core 23: zero detection unit

24: code multiplexer 25: control unit

27: buffer 29: line-length decoder

30: table part

The present invention relates to a variable length decoder for variable length decoding a bit stream that is variable length coded and transmitted by a variable length encoder of an image encoder, and more particularly, to a variable length decoder having an improved speed of variable length decoding.

The modern society is also called an information society. Since the amount of information to be processed is increasing day by day, data must be compressed to effectively use the existing transmission band.

In particular, in the case of digital video signals, since the amount of information is very large, it is essential to compress the video data in order to more efficiently store, retrieve, and transmit information.

For this reason, many compression techniques for image data have been developed. To summarize the compression of image data, the amount of data required to display an image is reduced by eliminating spatial, temporal redundancy, and statistical redundancy.

The image data compression method can be classified into loss coding and lossless coding according to whether information is lost or not, and intraframe coding and temporal redundancy present in a video to remove spatial redundancy present in still images. It can be divided into interframe encoding to remove.

Intra-frame coding to remove spatial redundancy includes discrete cosine transform coding (DCT) and quantization, which are constants of change encoding, and an example of inter-frame coding to remove the temporal redundancy, includes two temporally adjacent screens. Motion estimation / compensation coding, which removes temporal redundancy by estimating and compensating for motion, may be used.

In addition, by performing entropy coding on coefficient values that have undergone the discrete cosine coding (DCT) and quantization, statistical redundancy is removed.

That is, the entropy coding refers to a lossless coding algorithm for minimizing the bit generation rate by using a statistical property that a frequency of occurrence of quantized pixels is distributed differently and if their entropy is smaller than B, a code smaller than Bbpp exists.

These entropy coding techniques include Variable Lengh Coding (VLC), Run Lengh Coding (RLC), and Bit Plane Coding (BPC). However, variable length coding and line length coding are the most widely used.

The variable length coding is a technique of minimizing the bit generation rate by allocating small bits to frequently generated symbols and many bits to low frequency symbols according to the probability distribution of the encoded symbols.

There are many kinds of such variable length coding, but Huffman coding that is easy to implement is most widely used.

In addition, the line length coding is mainly used to increase the compression efficiency of transform coding such as Discrete Cosine Coding (DCT). The transformed DCT coefficients are generally concentrated at a low energy frequency and high frequency components are almost As it has a value close to zero, it performs a zig-zag scan to produce as long a zero-dimensional data column as possible, and then generates a two-dimensional symbol consisting of a continuous number of zeros and a non-zero coefficient value immediately following it. To make.

FIG. 1 is a block diagram schematically showing the configuration of a general video encoder and is used in many standardized encoders such as H.261, MPEG-1, and MPEG-2.

That is, the discrete cosine transforming unit (DCT) 1 outputs a discrete cosine transform coefficient by performing a discrete cosine transform on a block of 8x8 pixels, for example, to remove the correlation between pixels. The discrete cosine transform coefficients of the inter-frame difference image output from the discrete cosine transforming unit 11 are quantized at a predetermined quantization interval and output.

The DCT coefficients quantized by the quantizer 2 are converted into a one-dimensional data string through a zig-zag scanning process, input to a line length encoder 3, and the line length encoder 3 is output through a zig-zag scanning process. The resulting data stream is a two-dimensional (run, level) consisting of a continuous number of zeros and a non-zero coefficient value immediately following it.

The length coded data in the length coder 3 is variable length coded by the Huffman table in the variable length coder 4 and then output to a video buffer (not shown).

At this time, the DC coefficient and the AC coefficient among the DCT coefficients are distinguished and encoded in another method. Usually, since DC value of each block has much correlation with DC value of neighboring block, DC value of previous block has much correlation with DC value of neighboring block. Therefore, the difference value is encoded by calculating the difference with DC value of previous block. The DC of the first block is encoded by obtaining a difference from 128 which is an intermediate value of the variable range of the DC value. The DC difference values thus obtained are encoded through one-dimensional variable length coding.

That is, the DC coefficient is divided into DC size (dct_dc_size) and DC difference (dct_dc-differential) to be variable length coded. If DC size (dct_dc_size) is 0, only a code of DC size (dct_dc_size) is transmitted. After that, the DC difference (dct_dc-differential) is transmitted by the number of bits of the DC size (dct_dc_size).

AC also reorders the coefficients for more efficient data compression by taking advantage of the fact that the AC coefficient near the DC coefficient in the DCT region is not zero, and that falling from DC has a higher probability of zero. -Align in one dimension by means of a zag scan. Here, zero-run and zero-level coefficients are expressed in two dimensions (run and level).

For example, a zig-zag scan results in aligned DCT coefficients such as 30,2,0,0, -8,0,0,0,9 ... ), (0, 2), (2, -8), (3, 9) ...

And if the zig-zag scanned coefficients continue to end after some position, add an end of block (EOB) sign indicating the end of the block.

In this way, the line length coded data is variable length coded by the Huffman table.

In addition, when there are no coefficients to be transmitted in intercode, this is called skipped macroblock. Information data indicating how many skipped macroblock blocks are continued, and information data indicating whether the blocks to which the macroblock belongs is coded. It is transmitted to the decoder through the video buffer (not shown).

On the other hand, the video data transmitted through the compression process as described above is restored to the original data in the video decoder, such a video decoder is to implement the video encoder in reverse.

That is, FIG. 2 is a schematic block diagram of a general image decoder, and includes a variable length decoder 5 for performing variable length decoding on the encoded data and outputting the image data output from the variable length decoder 5. A line length decoder 6 for performing line length decoding on the line; An inverse scanning unit 7 which scans the data output from the line length decoder 6 in reverse and outputs an 8x8 frequency coefficient block; An inverse quantizer 8 for performing inverse quantization on the 8x8 frequency coefficient block output from the inverse scanning unit 7 and outputting the inverse quantizer; And an inverse discrete cosine transform section 9 for performing an inverse DCT on the 8x8 frequency coefficient block output from the inverse quantizer 8 and outputting an 8x8 pixel block.

In the video decoder as described above, the variable length decoder 5 performs variable length coding in reverse by extracting the variable length coded DCT coefficients from the coded bit stream, and then outputs the result to the line length decoder 6, and the line length. The decoder 6 performs line length decoding on the data output from the variable length decoder 5 and outputs it to the inverse scanning unit 7.

That is, the data input to the line length decoder 6 basically has a run and a level, and the gun represents a length of zero, and the level is a value following the zero as much as the run length. to be.

In addition, the inverse scanning unit 7 converts the one-dimensional DCT coefficients output from the line length decoder 6 into two dimensions again according to the scanning method.

The DCT coefficients output in two dimensions as described above are inversely quantized by the inverse quantizer 8 to be restored to the actual DCT coefficient values, and then inverse discrete cosine transformed by the inverse discrete cosine transforming unit 9 to be output as an 8x8 pixel block. Will be.

In this case, the variable length encoder 4 shown in FIG. 1 can be easily performed by finding a source symbol in a code table and generating a corresponding bit string. The variable length decoding process performed by the variable length decoder 5 is very difficult.

That is, since the variable length coded bit string is sequential, the next variable length code can be decoded only after one variable length code is decoded, so that pipeline or parallel processing is difficult.

In addition, since the variable length coded bit strings have different lengths of the variable length words, when the input speed of the bit string is constant, the output speed is variable, and when the output speed is constant, the input speed of the bit string is variable. Therefore, buffer control or stall processing according to the difference in processing speed is required.

On the other hand, the apparatus for decoding a stream of variable length code can be largely divided into sequential decoding and parallel decoding. In particular, sequential decoding is a method of decoding a bit sequence sequentially from the front, and is a constant speed input structure, a constant speed output structure, a variable input / output It can be divided into structures.

Among them, the variable length decoder of the constant speed output structure is proposed by M, T Sum of Bell Core, and the input bit string is cut by the maximum length (17 bits) of the variable length code and read into the ROM / PLA (Read Only Memory / Programmable Logic Array) table. After finding the variable length code by inputting, it shifts the barrel shifter by the length of the variable length code found and then finds the next code word. (Bell Core, U, S, A Patent no 5173695, 5245338)

As shown in FIG. 3, the variable length decoder of the above-described method has a variable length that barrel-shifts the variable length coded bit string by the length of the variable length code and cuts it to the maximum length (17 bits) of the variable length code. A decoder core 20; A controller 25 for receiving a variable length code and header information output from the variable length decoder core 20 and outputting a cable select signal; each variable length code input from the variable length decoder core 20 Simultaneously decoding through a table and selecting any one of the values decoded through each PLA table according to the table selection signal input from the controller 25, the length information of the variable length code is sent to the variable length decoder core 20. And a table unit 30 for inputting header information to the control unit 25 and a (run, level) value for outputting the buffer 27 to the line-length decoder 29 for xd. .

That is, the variable length decoder core 20 cuts and outputs only the maximum length (17 bits) of the length code when the bit string output through the system decoder (not shown) is output, and the variable input from the table unit 30 is output. The barrel is shifted by the length of the length code and then cut and output by the maximum length (17 bits) of the variable length code.

The control unit 25 receives the 17-bit variable length code output from the variable length decoder core 20 and the 6-bit header information output from the table unit 30 and receives the variable length decoder core 20 from the variable length decoder core 20. It is to find out which PLA table among the PLA tables of the table unit 30 corresponds to the output variable length code, and outputs a 3-bit table selection signal to the table unit 30 to select the corresponding PLA table.

The table unit 30 simultaneously decodes the 17-bit variable length code inputted from the variable length decoder core 20 through each PLA table, and sets up each PLA table according to the table selection signal inputted from the control unit 25. Select and output one of the decrypted values.

In this case, if the value decoded through each PLA table of the table unit 30 is the length information (5 bits) of the variable length code, it is input to the variable length decoder core 20, and if the header information (6 bits), the controller ( 25) and (run, level) values are output to the line-length decoder 29 through the buffer 27.

At this time, the PLA table is composed of six tables such as MBA, MTYPE, DC, MVD, CBP, TOEFF, etc., and receives length information from 2 bits up to 17 bits and outputs length information.

The header information is output from a table of MBA, MTYPE, DC, MVD, CBP, etc., and is a value obtained by decoding a header of a macro block.

In the TOEFF table, the number of input bits is large, but the number of bits to output is large and the number of codes in the table is 227.

In the conventional variable length decoder, the variable length code output from the variable length decoder core 20 passes through each PLA table of the table unit 30 and the natural time generated through each PLA table. In addition to the large delay that occurs when MULTI PLEXING is output, the variable length code is inputted to all PLA tables, so that too many fanouts are applied to the variable length codes inputted to each PLA table. do.

Thus, there was a problem that the output gates driving each PLA table had a considerably large time delay.

In particular, since the upper 8 bits of the variable length code are input to almost all tables, there is a big problem with fanout in this part.

Accordingly, an object of the present invention is to provide a variable length decoder which not only reduces the fanout of the output stage of the variable length decoder core but also improves the variable length decoding speed by solving the above-described problems. .

The variable length decoder according to the present invention for achieving the above object comprises: a variable length decoder core for barrel-shifting the variable length coded bit string by the length of the variable length code and cutting the variable length code into a maximum length of the variable length code; A zero detection unit which checks whether a predetermined constant bit of the variable length code output from the variable length decoder core is 0 or 1 and outputs a control signal according to the result; A code multiplexer for outputting only a part of the variable length code output from the variable length decoder core according to the control signal of the zero detector; A controller for receiving a variable length code and header information output from the variable length decoder core and outputting a table selection signal; The variable length code input from the code multiplexer is decoded through each PLA table according to the control signal output from the zero detection unit, and any one of values decoded through each PLA table according to the table selection signal input from the control unit. Selecting a value, the length information of the variable length code is input to the variable length decoder core, the header information is input to the controller, and the (run, level) value includes a table unit for outputting to the line-length decoder through a buffer. Characterized in that configured.

Hereinafter, with reference to the accompanying drawings will be described in detail the present invention.

FIG. 4 is a schematic configuration diagram of a length decoder according to the present invention. The variable length decoder according to the present invention barrel-shifts a variable length coded bit string by the length of a variable length code (17 bits). A variable length decoder core 20 which is cut out and outputted into a; A zero detector (23) for checking whether a predetermined constant bit of the variable length code output from the variable length decoder core (20) is 0 or 1 and outputting a control signal according to the result; A code multiplexer (24) for outputting only a part of the variable length code output from the variable length decoder core (20) according to the control signal of the zero detector (23); A control unit 25 for receiving a variable length code and header information output from the variable length decoder core 20 and outputting a table selection signal; The variable length code input from the code multiplexer 24 is decoded through each PLA table according to the control signal output from the zero detector 23, and according to the table selection signal input from the controller 25. By selecting any one of the values decoded through the PLA table, the length information of the variable length code is input to the variable length decoder core 20, and the header information is input to the controller 25, while (run, level) The value is configured to include a table portion 30 which outputs to the line-length decoder 29 via the buffer 27.

At this time, the zero detecting unit 23 checks the upper 8 bits of the 17-bit variable length code output from the variable length decoder core 20 and outputs a control signal of 1 when the upper 4 bits are all 0. When the upper 8 bits are all 0, 10 control signals are output. When the upper 4 bits are all 1, 11 control signals are output. Otherwise, the control signals of 0 are output. .

When the control signal of 1 or 11 is inputted from the zero detector 23, the code multiplexer 24 selects [12: 4] of the 17 bits of the variable length code output from the variable length decoder core 20. When 9 bits are output and 10 control signals are input from the zero detector 23, the lower 9 bits are output from the 17 bits of the variable length code output from the variable length decoder core 20, and the zero detector 23 is output. When a control signal of 0 is inputted from the control unit, the upper 9 bits of the 17-bit variable length code output from the variable length decoder core 20 are output.

The table unit 30 is configured to output a run value of 5 bits and a level value of 6 bits, while inputting header information to the controller 25 via a level path.

Referring to the operation and effects of the variable length decoder according to the present invention configured as described above in detail as follows.

The variable length decoder core 20 cuts and outputs the system-decoded bit stream by the maximum length (17 bits) of the variable length code through a system decoder (not shown).

Then, the barrel is shifted by the length of the variable length code inputted from the table unit 30, and then cut and output by the maximum length (17 bits) of the variable length code again.

The controller 25 receives the 17-bit variable length code output from the variable length decoder core 20 and the header information output from the table unit 30, and outputs the variable output from the variable length decoder core 20. It finds out which PLA table among the PLA tables of the table unit 30, and outputs a 3-bit table selection signal to the table unit 30 to select the corresponding PLA table.

On the other hand, the zero detection unit 23 checks the upper 8 bits of the 17-bit variable length code output from the variable-length decoder core 20, and outputs a control signal of 1 when the upper 4 bits are all 0, If the upper 8 bits are all 0, 10 control signals are output. If the upper 4 bits are all 1, 11 control signals are output. If the upper 4 bits are all 1, the control signals of 0 are output.

When the control signal of 1 or 11 is inputted from the zero detector 23, the code multiplexer 24 selects [12: 4] from among the 17 bits of the variable length code output from the variable length decoder core 20. When 9 bits are output and 10 control signals are input from the zero detector 23, the lower 9 bits are output from the 17 bits of the variable length code output from the variable length decoder core 20, and the zero detector 23 is output. When a control signal of 0 is input from the N-th output signal, the upper 9 bits of the 17-bit variable length code output from the variable length decoder core 20 are output.

In addition, the table unit 30 decodes the 9-bit variable length code input from the code multiplexer 24 through each PLA table according to the control signal output from the zero detection unit 23 and controls the control unit ( According to the table selection signal input in step 25), one of the values decoded through each PLA table is selected, and the length information (5 bits) of the variable length code is input to the variable length decoder core 20, and the header information ( 6 bits) are inputted to the controller 25, while run (RUN: 5 bits) and level (LEVEL: 7 bits) values are output to the line-length decoder 29 through the buffer 27.

At this time, the PLA table is composed of six tables such as MBA, MTYPE, DC, MVD, CBP, TCOEFF, etc., and receives length information from 2 bits up to 17 bits and outputs length information.

The header information is output from a table such as MBA, MTYPE, DC, MVD, CBP, etc., and is a value obtained by decoding a header of a macro block.

In the TCOEFF table, run and level values are output along with the length.

At this time, the table unit 30 is configured to output a run value of 5 bits and a level value of 7 bits, while decoding the header of the macro block output from each PLA table such as the MBA. A value is input to the controller 25 via the path of the level.

As described above, according to the present invention, not only the fanout of the output stage of the variable length decoder core can be significantly reduced, but also the variable length decoding can be performed quickly, and the size of the PLA table can be reduced.

Claims (7)

A variable length decoder core 20 for barrel-shifting the variable length coded bit string by the length of the variable length code and cutting the variable length code into a maximum length of the variable length code; A zero detector (23) for checking whether a predetermined constant bit of the variable length code output from the variable length decoder core (20) is 0 or 1 and outputting a control signal according to the result; A code multiplexer (24) for outputting only a part of the variable length code output from the variable length decoder core (20) according to the control signal of the zero detector (23); A controller 25 for receiving a variable length code and header information output from the variable length decoder core 20 and outputting a table selection signal; The variable length code input from the code multiplexer 24 is decoded through each PLA table according to the control signal output from the zero detection unit 23, and the table selection signal input from the control unit 25 is decoded. By selecting any one of the values decoded through the PLA table, the length information of the variable length code is input to the variable length decoder core 20, and the hair information is input to the controller 25, while (run, level) A variable length decoder configured to include a table 30 for outputting a value to a line-length decoder 29 through a buffer 27. The zero-detector 23 checks the upper 8 bits of the 17-bit variable length codes output from the variable length decoder core 20, and controls 1 if the upper 4 bits are all zeros. Outputs a signal, outputs 10 control signals if the upper 8 bits are all 0, outputs 11 control signals if all the upper 4 bits are 1, and outputs a control signal of 0 for all but the above. Variable length decoder, characterized in that the output. The variable multiplexer of claim 1, wherein the code multiplexer (24) is selected from the 17-bit variable length code output from the variable length decoder core (20) when a control signal of 1 or 11 is input from the zero detector (23). 12: 4] A variable length decoder characterized in that for outputting 9 bits. 2. The code multiplexer 24 according to claim 1, wherein the code multiplexer 24 receives the lower 9 bits of the 17-bit variable length code output from the variable-length decoder core 20 when 10 control signals are input from the zero detector 23. Variable length decoder, characterized in that for outputting. 2. The code multiplexer 24 according to claim 1, wherein the code multiplexer 24, when zero control signal is input from the zero detector 23, is the upper 9 bits of the 17-bit variable length code output from the variable length decoder core 20. Variable length decoder, characterized in that for outputting. The variable length decoder according to claim 1, wherein the table (30) outputs a 5-bit run value and a 7-bit level value. The variable length decoder of claim 1, wherein the table unit (30) inputs header information to the control unit (25) through a path of a level.