Variable-length encoder and decoder using symbol/code-word...

Details Variable-length encoder and decoder using symbol/code-word... Variable-length encoder and decoder using symbol/code-word...

2000-07-28

2002-11-26

Williams, Howard L. (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from variable length codes

C341S065000

Reissue Patent

active

RE037912

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a variable-length encoding/decoding system for video data. More particularly, it relates to a variable-length encoding/decoding system which re-associates a predetermined relation between a symbol and a code-word based on the frequency of occurrence of symbols to be variable-length coded (VLC), to thereby increase encoding efficiency.
2. Description of the Prior Art Recently, video and audio equipment employing digital signal processing methods have increased, and have been briskly developed. Therefore, many studies have been initiated relating to encoding a video and audio signal into a digital signal. Since an encoded video signal requires a large amount of digital data, various methods have been suggested to compress the encoded digital data prior to storing it on a recording medium. Among the various compression methods are a transform coding method, vector-quantization method, differential pulse coded modulation (DPCM), and variable-length coding method. Such coding methods are used to remove redundant data contained in a digital signal and, thus, reduce the total amount of transmitted or recorded data.
The VLC method is a technique to convert symbols in the form of [run,level], obtained through discrete cosine transform (DCT), quantization and zigzag scan operations, into corresponding code words by using a VLC table.
FIG. 1
shows one example of a VLC table. According to the [run,level] data of the symbols shown in
FIG. 1
at the right-hand side of the table, code words having different lengths are associated with the respective symbols. Huffman coding is a method of associating symbols and code words based on the frequency of occurrence of the symbols. That is, Huffman coding is a data compression method in which, considering the frequency of occurrence of a symbol, a code word having a short length is associated with a symbol having a high frequency of occurrence, while a code word having a longer length is associated with a symbol having a lower frequency of occurrence. A typical example of an apparatus implementing the above method is illustrated in FIG.
2
.
FIG. 2
shows a conventional variable-length encoder, and
FIG. 3
depicting a conventional variable-length decoder. The variable-length encoder of
FIG. 2
comprises an encoder
1
and VLC table
2
. The variable-length decoder of
FIG. 3
comprises a decoder
3
and variable length decode (VLD) table
4
which is the same as to VLC table
2
. When a symbol is input, encoder
1
locates a code word corresponding to the input symbol among the code words input from VLC table
2
, and outputs the corresponding code word. Decoder
3
locates a symbol corresponding to the input code word from VLD table
4
, and outputs the corresponding symbol, to thereby restore the original symbol input to the variable-length encoder.
However, if there is difference between the frequency of occurrence of symbols used in constructing VLC table
2
and the corresponding VLD table
4
, and that of symbols currently used in VLC coding, optimum variable-length coding can not be achieved. In other words, if the characteristics of an image to be currently variable-length coded are different from those of an image used when a code table is designed, a previously generated VLC table
2
and VLD table
4
cannot be changed to accommodate the differing characteristics. Thus, such an encoder/decoder and method do not fully accomplish the object of compressing the entire amount of data to be stored or transmitted.
SUMMARY OF THE INVENTION
Therefore, it is an object of the present invention to provide a variable-length encoder in which, even though the symbol/code-word association of a previously generated code table is used, the frequency of occurrence of the currently input symbols is measured in order to re-associate the symbols to the appropriate code words. Such a re-association provides that the amount of data to be consumed is minimized even when symbols are input that have a different frequency of occurrence from that of symbols considered when the code table is generated.
Another object of the present invention is to provide a variable-length decoder for restoring the original symbols represented by the code words obtained by variable-length coding, in which a symbol corresponding to an input code word is searched for in a previously generated decode table according to symbol/code-word re-association control information, to thereby decode the corresponding symbol.
To accomplish the first object of the present invention, there is provided a variable-length encoder using symbol/code-word re-association of a code table comprising a first storing means for storing previously generated code table, a first re-associating means for generating re-associated code table and re-association information indicative of the relation between a symbol and a corresponding code word from the previously generated code table stored in the first storing means, based on the frequency of occurrence of externally applied symbols during a predetermined time period, a delay for delaying and outputting the same symbols as those input to the first re-associating means during the predetermined time period, a re-association information storing means for storing the re-associated code table and re-association information and sequentially outputting the re-association information, variable-length coding means for receiving the delayed symbols and generating the sequentially outputting code words according to the re-associated code table stored in the re-association information storing means, and means for multiplexing and outputting the re-association information from the re-association information storing means and outputting the code words output from the variable-length coding means.
To accomplish the second object of the present invention, there is provided a variable length decoder using symbol/code-word re-association of a code table comprising a second storing means for storing the same code table as that previously generated and stored in the first storing means, demultiplexing means for receiving data output from the means for multiplexing, dividing and outputting re-association information and code words, a second re-association means for receiving the re-association information from the demultiplexing means, re-associating a corresponding symbol/code-word relation, and storing re-associated code table, and variable-length decoding means for decoding an input code word based on the code table information stored in the second re-associating means to thereby generate a symbol.


REFERENCES:
patent: 4839724 (1989-06-01), Keesen et al.
patent: 4957724 (1990-09-01), DeWith
patent: 5253053 (1993-10-01), Chu et al.
patent: 0613303 (1994-08-01), None
patent: 0273130 (1998-07-01), None
patent: 2-124644 (1990-05-01), None
patent: 2-302127 (1990-12-01), None
patent: 3-14366 (1991-01-01), None
patent: 4-239225 (1992-08-01), None
patent: 6-61869 (1994-03-01), None
patent: 6-225286 (1994-08-01), None

Affiliated with

Also associated with

Rating

Variable-length encoder and decoder using symbol/code-word... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Variable-length encoder and decoder using symbol/code-word..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable-length encoder and decoder using symbol/code-word... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2953804