3.10 Variable Length Coding

VLC, also called entropy coding, is a technique whereby each event is assigned a code that may have a different number of bits. To obtain compression, short codes are assigned to frequently occurring events and long codes are assigned to infrequent events. The expectation is that the average code length will be less than the fixed code length that would otherwise be required. If all events are equally likely, or nearly so, then VLC will not provide compression.

All codes considered must be uniquely decodable; that is, there must be only one way that a concatenation of VLCs can be decoded. In addition, it is highly desirable that the code be instantaneous; that is, each code word can be decoded without reference to subsequent code words. Taken together, these requirements mean that no code word can be the beginning of another code word. For example, we may not have 01 and 0110 as code words, since the second code word starts with the first code word. In decoding, it is not known whether 01 is the first code word or just the start of the second code word.

A major advantage of VLC is that it does not degrade the signal quality in any way. The reconstituted signal will exactly match the input signal so that if the signal is adequately described by a series of events, using VLCs to communicate them to the decoder will not change the events. Therefore the system is transparent to...