3 Compression3.1 Detail: 2-D Discrete Cosine Transform*3.2 Detail: LZW CompressionChapter 3CompressionIn Chapter 1 we examined the fundamental unit of information, the bit, and its various abstract represen-tations: the mathematical bit, the classical bit, and the quantum bit.A single bit is useful if exactly two answers to a question are possible. Examples include the result of acoin toss (heads or tails), the gender of a person (male or female), the verdict of a jury (guilty or not guilty),and the truth of an assertion (true or false). Most situations in life are more complicated. In Chapter 2we considered some of the issues surrounding the representation of complex objects by arrays of bits. Themapping between the objects to be represented (the symbols) and the array of bits used for this purpose isknown as a code.In our never-ending quest for improvement, we were led to representations of single bits that are stronger,smaller, faster, and cheaper. Following this route led to fundamental limitations imposed by quantummechanics. In a similar way, we want codes that are stronger and smaller. In this chapter we will considertechniques of compression that can be used for generation of particularly efficient representations.In Chapter 2 we looked at this general sort of a system, in which objects are encoded into bit strings, theseare transported (in space and/or time) to a decoder, which then recreates the original objects. Typicallythe same code is used for a succession of objects one after another.CoderChannelDecoder- - - -(Arrays of Bits) (Arrays of Bits)Input(Symbols)Output(Symbols)Figure 3.1: Generalized communication systemThe role of data compression is to convert the string of bits representing a succession of symbols into ashorter string for more economical transmission, storage, or processing. The result is this system, with botha compressor and an expander. Ideally, the expander would exactly reverse the action of the compressor sothat the coder and decoder could be unchanged.Author: Paul Penfield, Jr.Version 1.1.0, February 12, 2004. Copyrightc 2004 Massachusetts Institute of TechnologyURL: http://www-mtl.mit.edu/Courses/6.050/notes/chapter3.pdfstart: http://www-mtl.mit.edu/Courses/6.050/notes/index.htmlback: http://www-mtl.mit.edu/Courses/6.050/notes/chapter2.pdfnext: http://www-mtl.mit.edu/Courses/6.050/notes/chapter4.pdf2627Source EncoderCompressorChannelExpanderSource Decoder- - - - - -Input Output(Symbols) (Symbols)(Arraysof Bits)(Arraysof Bits)(Arraysof Bits)(Arraysof Bits)Figure 3.2: More elaborate communication systemThis approach might seem surprising. Is there any reason to believe that the same information could becontained in a smaller number of bits? There are two types of compression, relying on different approaches:• Lossless or reversible compression, which can only be done if the original code was inefficient, forexample by not taking into account the fact that some symbols are more frequently used than others,or by having unused bit patterns.• Lossy or irreversible compression, in which the original symbol, or its coded representation, cannotbe reconstructed exactly, but instead the expander pro duces an approximation that is ”good enough”[This version of Chapter 3 is a draft that is not yet complete. Two detail sections have been written so farand are attached. There is more to come.]3.1 Detail : 2-D Discrete Cosine Transform∗283.1 Detail: 2-D Discrete Cosine Transform∗The Discrete Cosine Transform (DCT) is one of many transforms that takes its input and transforms it intoa linear combination of weighted basis functions. These basis functions are commonly the frequency, likesine waves. The 2-D Discrete Cosine Transform is just a one dimensional DCT applied twice, once in thex direction, and again in the y direction. One can imagine the computational complexity of doing so for alarge image. Thus, many algorithms, such as the Fast Fourier Transform (FFT), have been c reated to speedthe computation.The 2 dimensional DCT is defined to beY = CTXC (3.1)where X is an N×N image block, Y contains the N×N DCT coefficients, and C is an N×N matrix definedasCmn= kncos(2m + 1)nπ2Nwhere kn=p1/N if n = 0p2/N otherwise(3.2)where m, n = 0, 1, . . . (N − 1).Below is the matrix C which are the basis functions of an 8×8 DCT from which weighted values of eachbasis function (image block) can be added or subtracted from each other to produce an 8×8 image. We referto these values as DCT coefficients. When you apply the DCT to an 8×8 image, it will yield an 8×8 matrixof we ighted values corres ponding to how much of each basis function is present in the original image.Figure 3.3: Discrete Consine Transform 8×8 Basis∗This section is based on notes written by Joseph C. Huang, February 25, 2000.3.1 Detail : 2-D Discrete Cosine Transform∗29One can see from obse rvation that an 8×8 image that just contains one shade of gray will consist only of awe ighted value for the upper left hand DCT basis function (the DCT basis function which has no frequenciesin the x or y direction).The following is the MATLAB code to generate the basis functions as shown above for the 4×4, 8×8,and 16×16 DCT.for N = [4 8 16]; % N is the size of the NxN block being DCTed.% For this code, it does a 4x4, 8x8, and 16x16% Create CC = zeros(N,N);for m = 0:1:N-1for n = 0:1:N-1if n == 0k = sqrt(1/N);elsek = sqrt(2/N);endC(m+1,n+1) = k*cos( ((2*m+1)*n*pi) / (2*N));endend% Get Basis Functionsfigure;colormap(’gray’);for m = 0:1:N-1for n = 0:1:N-1subplot(N,N,m*N+n+1);Y = [zeros(m,N);zeros(1,n) 1 zeros(1,N-n-1);zeros(N-m-1,N)];X = C’*Y*C;imagesc(X);axis square;axis off;endendendFigure 3.4: Discrete Cosine Transform Matlab CodeThere is also an Inverse DCT which just takes the DCT coefficients and multiplies them with the basisfunctions and adds all of them together. Surprisingly, the IDCT is very similar to the DCT. Using linearalgebra, one can produce the inverse C matrix and apply it to Y to yield X.3.2 Detail : LZW Compression 303.2 Detail: LZW CompressionThere are several compression algorithms that use a “dictionary,” or code book, known to the coder andthe decoder, which is generated during the coding and decoding pro ce sse s. Many of these build on workreported in 1967 by Abraham Lempel and Jacob Ziv, and are known as “Lempel-Ziz” encoders. In essense,these coders replace repeated occurrences of a string by references to an earlier occurrence. The