Variable length encoding method and variable length decoding met

Details Variable length encoding method and variable length decoding met Variable length encoding method and variable length decoding met

1989-11-30

1991-06-04

Shoop, Jr., William M.

Coded data generation or conversion

Digital code to digital code converters

To or from variable length codes

341 79, H03M 740

Patent

active

050217828

DESCRIPTION:

BRIEF SUMMARY
The invention relates to a variable length encoding method and a variable length decoding method, and to an encoding device and a decoding device for the implementation of this method.
A digitized signal is constituted from samples which can assume a finite number of values. These values are events each having a certain probability which is in general different for each value. It is known to encode events having unequal probabilities by means of predetermined code words having variable length, by representing the statistically most frequent events with short code words and by representing the least frequent events with longer code words. This type of encoding is known as entropic encoding. The code words are binary words which are transmitted in serial from without discontinuities. In order to be able to decode these code words, it is necessary to be able to distinguish them from each other despite their variable length.
The correspondence between the code words and the events can be represented graphically by a diagram called an encoding tree. This encoding tree comprises a root and branching branches constituted of segments. Each segment is associated with a binary 0 or binary 1 value. The encoding tree enables a binary word to be associated with an event as a function of its probability by following the tree from its root to the end of a branch, this end being associated with an event. The code word corresponding to an event is constituted by a series of bits associated with the different segments which are passed through in order to move from the root to the end of the branch in question.
Conversely, an event can be recovered by means of the same tree, by starting from the root and following a first segment corresponding to the value of the first bit of the code word, then a second segment corresponding to the value of the second bit of the code word etc. . . . , until arrival at the end of a branch, this end corresponding to an event which is the event to be decoded.
It is known to embody an encoding device and a decoding device implementing this type of variable length code by means of a read only memory for the encoding and a read only memory for the decoding. The encoding memory contains code words at addresses constituted by the values to be encoded. The decoding memory contains the events at addresses constituted by the code words.
An application of Huffmann encoding consists, for example, in encoding coefficients resulting from the encoding of a picture by the cosine transformation. The coefficients have values represented in 12 bits, for example. The encoding read only memory therefore comprises a 12-bit address input and a 16-bit data output, if the code has a maximum length fixed at 16 bits, giving a capacity of 4 kilowords (16-bit words). The decoding read only memory therefore comprises a 16-bit address input and a 12-bit data output, giving a capacity of 64 kilowords (12-bit words). the capacity of the necessary read only memories is therefore relatively large and results in a high production cost. Furthermore, the dynamic range of the values to be encoded is limited by this capacity.
The choice of code words consists in carrying out a statistical study of the values of the transformation coefficients of a typical series of pictures; then in determining the optimum code words by applying an algorithm which is described in particular in the French patent application No. 2,600,226 filed by the Applicant.
This algorithm enables an optimum Huffmann code to be obtained for events having well-determined statistical characteristics, but there is a large number of other encoding trees enabling a same series of events to be encoded with an non-optimum cost.
The device used for carrying out such an optimized Huffmann encoding is a read only memory since there is no simple mathematical relationship between the binary words representing the events at the input of the encoding device and the binary code words at the output of the encoding device. For the same reason, the decoding device is constituted

REFERENCES:
patent: 3918047 (1975-11-01), Denes
patent: 4188669 (1980-02-01), Rauscher
patent: 4553130 (1985-11-01), Kato
IBM Technical Disclosure Bulletin, vol. 16, No. 2, Jul. 1973, (New York, U.S.), D. C. Van Voorhis: "Construction of Codes with Bounded Code-Word Lengths", pp. 487-488.
IBM Technical Disclosure Bulletin, vol. 24, No. 3, Aug. 1981, (New York, U.S.), I. Jones: "Variable Length Code-Work Encoder/Decoder", pp. 1514-1515.

Affiliated with

Also associated with

Rating

Variable length encoding method and variable length decoding met 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 encoding method and variable length decoding met, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable length encoding method and variable length decoding met will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1029330