Information Technology Reference
In-Depth Information
transmitted with short wordlength symbols. As the probability of a code value falls, it will be allocated longer
wordlength. [ 5 ]
The Huffman code is used in conjunction with a number of compression techniques and is shown in Figure 1.6 .
Figure 1.6: The Huffman code achieves compression by allocating short codes to frequent values. To aid
deserializing the short codes are not prefixes of longer codes.
The input or source codes are assembled in order of descending probability. The two lowest probabilities are
distinguished by a single code bit and their probabilities are combined. The process of combining probabilities is
continued until unity is reached and at each stage a bit is used to distinguish the path. The bit will be a zero for the
most probable path and one for the least. The compressed output is obtained by reading the bits which describe
which path to take going from right to left.
In the case of computer data, there is no control over the data statistics. Data to be recorded could be instructions,
images, tables, text files and so on; each having their own code value distributions. In this case a coder relying on
fixed source statistics will be completely inadequate. Instead a system is used which can learn the statistics as it
goes along. The Lempel- Ziv-Welch (LZW) lossless codes are in this category. These codes build up a conversion
table between frequent long source data strings and short transmitted data codes at both coder and decoder and
initially their compression factor is below unity as the contents of the conversion tables are transmitted along with
the data. However, once the tables are established, the coding gain more than compensates for the initial loss. In
some applications, a continuous analysis of the frequency of code selection is made and if a data string in the table
is no longer being used with sufficient frequency it can be deselected and a more common string substituted.
Lossless codes are less common for audio and video coding where perceptive codes are permissible. The
perceptive codes often obtain a coding gain by shortening the wordlength of the data representing the signal
waveform. This must increase the noise level and the trick is to ensure that the resultant noise is placed at
frequencies where human senses are least able to perceive it. As a result although the received signal is
measurably different from the source data, it can appear the same to the human listener or viewer at moderate
compressions factors. As these codes rely on the characteristics of human sight and hearing, they can only be fully
tested subjectively.
The compression factor of such codes can be set at will by choosing the wordlength of the compressed data.
Whilst mild compression will be undetectable, with greater compression factors, artifacts become noticeable. Figure
1.5 shows that this is inevitable from entropy considerations.
[ 5 ] Huffman, D.A. A method for the construction of minimum redundancy codes. Proc. IRE , 40 1098-1101 (1952)
1.7 Video compression
Video signals exist in four dimensions: these are the attributes of the pixel, the horizontal and vertical spatial axes
and the time axis. Compression can be applied in any or all of those four dimensions. MPEG assumes an eight-bit
colour difference signal as the input, requiring rounding if the source is ten-bit. The sampling rate of the colour
signals is less than that of the luminance. This is done by downsampling the colour samples horizontally and
generally vertically as well. Essentially an MPEG system has three parallel simultaneous channels, one for
luminance and two colour difference, which after coding are multiplexed into a single bitstream.
 
Search WWH ::




Custom Search