Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist

Подождите немного. Документ загружается.

Overview of data compression standards 597

CRC trailer for error correction. The archive freeware IZArc supports an impressive list

of archive ﬁle formats, including applications for CD and DVD images. It also pro-

vides 256-bit AES encryption, repairing corrupted archives, and several other advanced

features.

Understandably, the achievable compression rate of any ﬁle-archiving programs is

strongly dependent on the dataﬁle type (e.g., text, slides, tabulated data, HTML web page,

executables, etc.) and anything of a different format that the ﬁle might also contain (e.g.,

raw or uncompressed pictures, equation ﬁelds, and other types of embedded additions).

An approximate comparison is shown in.

This study indicates that pure text ﬁles can

be zipped down to 19–27% of their original sizes (compression rates of 73–81%), the

leaders seemingly being 7-ZIP and RAR, with 19–20% rates. For executables, 7-ZIP

champions with 27% squeezing (the other competitors conﬁned to 36–40% ratios), and

for raw images this performance is reduced to 50–60%. These ﬁgures must, however,

be weighted against the coding and decoding times, obviously coming with a higher tax

for the champions, but not systematically. Thus, each case is a tricky matter of ﬁnding

the right trade-off between minimal archival size, the time required to squeeze the ﬁle,

and the time taken to recover the data as uncompressed. Ideally, compression should be

performed as a systematic background routine, in such a way as not to slow down other

computer tasks.

The external and permanent storage of computer ﬁles is popularly based on the CD-

ROM (compact-disk, read-only memory),

which is wholly similar to the previously

described audio-CD, both in terms of looks and storage space (700–800 Mbytes). A

key difference is that the CD-ROM is primarily designed for computer data and, hence,

it includes the function of error-correction, which is achieved through Reed–Solomon

(RS) encoding (see Chapter 11). The CD-ROM can be “burnt” according to three preset

modes: audio (for music tracks or copying audio-CDs), and mode 1 and mode 2 for PC

data. The CD-ROM has 333 000 sectors of 2352 bytes length (which gives a capacity

783.2 Mbytes). In the audio mode, no error correction is used, thus, the full sector

length (2352 bytes) can be used for storing audio ﬁles. Both mode 1 and mode 2 use

a 16-byte header in each sector, for the purposes of synchronization and identiﬁcation.

Unlike in mode-1, mode-2 does not include error correction, which leaves 2352 − 16 =

2336 bytes for payload. In mode 1, the 288-byte trailer for error correction leaves a

payload of 2336 −288 = 2048 bytes. CD-ROMs are characterized by three different

possible read and write speeds: A = write-once, B = rewrite and C = read-only. By

deﬁnition, the 1×speed rating corresponds to 150 kbyte/s. Thus, a 32×write-only speed

corresponds to 4.8 Mbyte/s. A 700 Mbyte CD-ROM can, thus, be copied in approximately

700/4.8 = 146 s or approximately 2 min 30 s. The different speed ratings for the A, B,

and C functions are then identiﬁed under the generic label A×, B×, C×, for instance

12×, 10×, 32×.

See, for instance: http://en.wikipedia.org/wiki/Izarc; www.izarc.org/.

See, for instance: http://en.wikipedia.org/wiki/Comparison_of_ﬁle_archivers.

See, for instance: http://en.wikipedia.org/wiki/CD-ROM.

See, for instance: http://en.wikipedia.org/wiki/Izarc; www.izarc.org/.

598 Appendix G

100

Figure G3 Effect of JPEG compression from 0% to 100% with close-ups shown at right.

Images

With the development and popularity of digital photography, and the multiplication

of Internet websites, the compression of images is playing an increasingly important

role. Not only does it save memory space, but its also make it possible to speed up

the downloading of web pages or email picture attachments, up to the point of instant

gratiﬁcation. The most commonly used standard, JPEG, is the creation of the Joint

Photographic Expert Group, which was launched in the mid 1980s under the ISO

standardization body.

The JPEG standard, which is deﬁned through various ﬁlename

extensions .jpg,.jpeg,.jpe,.jﬁf, and .jif,isalossy compression codec. This feature is

illustrated in Fig. G3. The original ﬁle size corresponding to the top-left image (as

converted for simplicity into a grayscale one) is 683 kbyte. Compressing the same image

through a photo editor by command factors of 50%, 75%, and 100% reduced the ﬁle

size to 102 kbyte, 65 kbyte, and 15 kbyte, respectively. A look at the close-ups reveals

that the effect of lossy compression is not noticeable at a 50% factor (nicely, the ﬁle

size has, however, been reduced to 15% of the original). At a 75% factor and above, the

loss of pixel information becomes apparent, to the point of yielding an image of poor

quality, with observed “blocky and blurry” artifacts. Clearly, the amount of compression

is a matter of subjectively determining the trade-off between ﬁle size and image quality,

which depends on the ﬁnal application, for instance either a screen wallpaper, a web

banner, or a ﬁle icon.

See, for instance: http://en.wikipedia.org/wiki/JPEG; www.imaging.org/resources/jpegtutorial/index.cfm.

Overview of data compression standards 599

4:4:4

4:2:2 4:2:0

Figure G4 Compressing the two 8 × 8 chroma blocks of 4:4:4, resulting in

size (4:2:2) and

size (4:2:0) reductions.

It is beyond the scope of this appendix to run into the complex details of image

analysis and the JPEG encoding algorithm. Here, I shall just provide a brief summary of

the main concepts and features of JPEG. Digital images are made of two-dimensional

(2D) pixel arrays, sometimes referred to as bitmaps. Each pixel is deﬁned through

3 × 8 = 24-bit codewords, with eight bits deﬁning the intensity of each of the red, blue,

and green (RBG) components, on a 0–255 scale. This code makes up to 256 ×256 ×

256 = 16 777.216 or about 16.7 million possible colors! This original pixel is then

analyzed and decomposed into a new color space, which considers three components:

one for luminance (or brightness, or “luma”), and two for chrominance (or “chroma”).

Chrominance is another way of labeling colors according to their hue (position in a

linear color scale) and saturation (intensity). The reason for such a conversion is that the

luminance and chrominance data offer more possibilities for compression, as we shall

see. The JPEG algorithm ﬁrst transforms the 2D-RBG pixel array into three 2D arrays,

one for luminance and two for chrominance. Each of these arrays is then decomposed into

blocks of 64 pixels, which equivalently form 8 ×8 pixel arrays (each pixel being eight

bits). As the human eye sees more details in luminance, it is possible to throw out some

information in the chrominance blocks. This is referred to as downsampling or chroma

subsampling.

There exist many different possibilities of achieving downsampling, of

which I will only mention two. Let us name 4:4:4 the original three-block set, as shown

in Fig. G4. As seen from the ﬁgure, halving the horizontal data in the last two 8 × 8

(chroma) blacks results in a set called 4:2:2, which is one-third smaller.

Halving the

chroma data in both horizontal and vertical directions results in the set 4:2:0, which is

one-half smaller. This 4:2:0 compression is the scheme used in most JPEG images, and

also in digital video (DV) and high-deﬁnition DV (HDV), in MPEG (including MPEG-2

for the digital video disk or DVD).

However, the JPEG compression algorithm does not stop there! The 8 ×8 blocks (or

their reduced versions) are then submitted to discrete cosine transform (DCT), which

is analogous to a 2D discrete Fourier transform.

The DCT maps each block into its

frequency version containing the Fourier coefﬁcients. The coefﬁcients are then subjected

to a quantizer, which uses variable step or “quantum” sizes (smaller for low frequencies,

and the reverse). Each coefﬁcient is scanned through a zigzag pattern, then divided by

See for instance: http://en.wikipedia.org/wiki/YUV_4:2:2.

The ﬁgure does not have the purpose of explaining how the halving in both horizontal and vertical directions

is actually performed.

See: www.imaging.org/resources/jpegtutorial/jpgdct1.cfm; http://en.wikipedia.org/wiki/Discrete_cosine_

transform; http://rnvs.informatik.tu-chemnitz.de/∼jan/MPEG/HTML/mpeg_tech.html.

600 Appendix G

its quantum size and the result rounded off to an integer. It is not unusual that more

than half of the resulting coefﬁcients end up being zero. Then it is possible to further

compress the blocks through run-length encoding (RLE), as described earlier with

sound compression. The RLE algorithm outputs the number of previous zeros and the

nonzero coefﬁcient amplitude, forming a sequence of pairs. Each pair is then encoded

through a lossless, variable-length codeword such as generated by Huffman coding (see

Chapter 9). The more powerful arithmetic coding (see Chapter 10) is also possible, but

is covered by patents. On completion, JPEG writes an end-of-block codeword, and after

processing the three blocks, an end-of-sequence codeword. Decoding the JPEG image

is basically the same succession of operation in the inverse-function order.

The JPEG standard later evolved to JPEG-2000 (ﬁlename extensions .jp2 and .j2c).

The key difference from the former JPEG is the use of the discrete wavelet transform

(DWT) algorithm

instead of DCT. The interest of DWT is not only the possibility of

achieving greater compression rates (typically 20% higher) while making imperceptible

the characteristic “blocky and blurry” artifacts of the JPEG described earlier. As a major

optional feature, JPEG2000 also provides lossless compression, owing to the reversibility

of DWT. The long list of many other beneﬁts can be explored in the references given in

the footnotes.

What about other image-coding standards? Let me brieﬂy describe ﬁrst GIF and

PNG. Short for graphic interchange format,

GIF (ﬁlename extension .gif)isalossless

image-compression codec, which is also popular in websites. Its inherent simplicity

stems from the limited palette of 256 (eight-bit) preset colors extracted from the 24-bit

RBG space. While such a palette is too limited for image-photography applications, it is

fully adequate for continuous-color pictures, such as line-art, graphics, and logos, and all

sorts of animations or advertising, which abound in Internet pages or email attachments,

such as e-cards. The key feature of GIF is the use of Lempel–Ziv–Welch (LZW) for

compression algorithm, see description in Chapter 10, which is far more efﬁcient than

run-length encoding (RLE). As LZW turned out later to be bound to certain patents

(the issue having become obsolete, from 2006), the PNG format, short for portable

network graphics,

was then developed as freeware, eventually to become the third most-

preferred image ﬁle for Internet use, despite varieties in web-browser support, versions,

and related compatibility problems. Like its GIF predecessor, PNG (ﬁlename extension

.png)isalossless image-compression codec. Its RBG color palette is, however, increased

from 24 bits to 32 bits and 48 bits. One of the interesting features of PNG is object

transparency (also available to some more limited extent in GIF), i.e., the possibility

of making certain image objects appear translucent over their background, as achieved

through a supplementary “alpha” channel. The core PNG compression algorithm is

based on the license-free DEFLATE which, as we have seen earlier, combines LZ77 and

See, for instance: http://en.wikipedia.org/wiki/JPEG_2000. See also, the JPEG-2000 ofﬁcial website:

www.jpeg.org/jpeg2000/.

See, for instance: http://en.wikipedia.org/wiki/Wavelet; http://en.wikipedia.org/wiki/Discrete_wavelet_

transform.

See, for instance: http://en.wikipedia.org/wiki/GIF.

See, for instance: http://en.wikipedia.org/wiki/Portable_Network_Graphics.

Overview of data compression standards 601

Huffman coding. Under its MNG extension, PNG also supports graphic animation,

although it is more complex and not widely supported on the Internet.

Two other image formats are TIFF (tagged image ﬁle format)

and BMP (short for

bitmap)

. In short, TIFF (ﬁlename extension .tiff) was originally designed as a common

standard for image scanners; with a 32-bit uncompressed format albeit with the option

of lossless LZW (Lempel–Ziv–Welch) compression. Its speciﬁcity, hence, its name, is

the capability of handling multiple images and data in a single ﬁle with as many header

“tags.” The format BMP (ﬁlename extensions .bmp or .dib) offers a variety of coloring

depths (1, 2, 4, 8, 16, or 32 bits) with an uncompressed image format. Owing to their

redundancy, BMP ﬁles lend themselves to efﬁcient lossless compression, for instance

through ZIP (see above).

Video

The most generic standard to encode video data is known as MPEG (short for

motion pictures expert group),

more accurately deﬁned under MPEG-1, MPEG-2, and

MPEG-4. It is beyond the scope of this overview to approach such standards in the

appropriate level of detail but, as in the previous sections, I shall focus on the key

features and on the central role of data compression algorithms.

MPEG-1

This is the early standard for digital video (DV), and is also videoCD/DVD compat-

ible (see later).

It achieves audio and video multiplexing, synchronization, and data

compression. The video quality is primarily deﬁned according to the pixel resolution

of the 2D image frame, namely 352 × 240 (NTSC system, used in North America)

and 352 ×288 (PAL-SECAM system, used in Europe). The corresponding frame rates

are 29.97 ≈ 30 frame/s and 25 frame/s, respectively. There are four types of MPEG-1

frame: I, for intra-coded frames, which are individually compressed; P, for predictive

frames, which code the frame image as a difference from that of the previous one in

the sequence, B, for bidirectionally predictive frames, which codes the image as a dif-

ference from both the previous and the next image, and D, which uses block coding on

an average image from several successive frames. This type of low-quality resolution is

only used for fast-forwarding visualization. A group of pictures (GOP)

is then typi-

cally formed by the 12-frame sequence IBBPBBPBBPBB, which always begins with an

I-frame. The above sequencing makes it possible to encode movie pictures at rates

See, for instance: http://en.wikipedia.org/wiki/Multiple-image_Network_Graphics.

See, for instance: http://en.wikipedia.org/wiki/Tagged_Image_File_Format.

See, for instance: http://en.wikipedia.org/wiki/Windows_bitmap.

See: www.mpeg.org; www.chiariglione.org/mpeg/.

See, for instance: http://en.wikipedia.org/wiki/MPEG-1; www.chiariglione.org/mpeg/standards/mpeg-

1/mpeg-1.htm.

See, for instance: http://en.wikipedia.org/wiki/Group_of_pictures; http://rnvs.informatik.tu-chemnitz.

de/∼jan/MPEG/HTML/mpeg_tech.html.

602 Appendix G

between 1.2 Mbit/s and 1.5 Mbit/s. A main drawback of MPEG-1 is that it is based on

the principle of progressive (or noninterlaced) image scanning. Images are scanned line

by line, which provides good vertical resolution, but does not allow for smooth motion

restitution in the case of fast-changing scenes. As seen earlier, in the sound compression

section, MPEG-1 remains the underlying standard for the most popular MP3 (short for

MPEG-1/2 layer 3).

MPEG-2

This comes as an enhancement of MPEG-1 in both audio and video.

To recall from

the previous section on sound, the MPEG-2 audio layer 3 is also an underlying standard

for MP3, which allows us here to encode more than just one stereo track. As for the

video, just like in MPEG-1, the I-frames are processed according to the JPEG image-

compression algorithm (see previous description in the image section). The P-frame

offers more compression potential than the I-frame, because it only encodes succes-

sive image differences. The comparison algorithm considers macroblocks of 16 ×16

pixels. The differences are then described by the translation of similar groups of pix-

els within these macroblocks, characterized by a “motion vector.” If the algorithm

fails satisfactorily to code the transition with the appropriate motion vector and addi-

tional predictive corrections, then the output frame is an unaltered I-frame. The B-

frame encoding works according to the same principle as the P-frame, except that it

uses the information of the two surrounding images. A supplemental feature is that

(unless otherwise speciﬁed) frames are interlaced on display or scanning (unlike in

MPEG-1), which allows smooth transitions in the case of fast-moving pictures. Here,

we shall overlook the supplemental notions of “transport stream” and “program stream,”

which are more application focused. In terms of image resolution, frame rate and bit

rate, MPEG-2 offers a broad variety of possible conﬁgurations. One ﬁrst refers to an

MPEG-2:

Proﬁle, through (a) the type of frames in the GOP [I-P or I-P-B], (b) the JPEG luma

or chroma sampling [4:2:0 or 4:2:2] used for the images, and (c) the stream range [1,

1–2, or 1–3]. The simplest proﬁle, called SP, is thus deﬁned by [I, P][4:2:0][1], and

the highest one, called HP, by [I, P, B][4:2:2][1–3];

Level, through (a) the number of pixels per line [325 to 1920], (b) the number of

lines [288 to 1152], at a rate of 30 frames per second. The lowest level, called LL, is

[352][288], and the highest one, called HL, is [1920][1152].

Proﬁle@level, through (a) the 2D motion-picture pixel resolution [176 × 144

to 1920 ×1080 with many intermediate variants], (b) the frame rate [15 to 60],

lowest option, called SP@LL, is, thus, [176 ×144][15][4:2:0][0.096], while the high-

est one (a potential for future applications), called 422P@HL, is either [1920 ×

1080][30][4:2:2][300] or [1280 ×720][60][4:2:2][300].

See, for instance: http://en.wikipedia.org/wiki/MPEG-2.

Overview of data compression standards 603

It is clear that each of the standard proﬁle@level options has been designed to meet spe-

ciﬁc consumer-electronics applications and requirements, such as: wireless mobile hand-

sets (3G cellular telephony), personal digital assistants (PDA), set-top boxes (STB), dig-

ital versatile disk (DVD), digital video broadcast (DVB), high-deﬁnition video (HDV),

high-deﬁnition television (HDTV), and many other professional-imaging applications,

present and future. A key application of MPEG-2, which is interesting to consider here

as an illustrative example, is the DVD.

As users know, commercial DVDs now come in

several capacity options, including read-and-write versions (known as DVD ± R, DVD

±RW, DVD-RAM),

namely, 4.7/9.4 Gbytes (single-layer) and 8.5/17.1 Gbytes (double

layer). The video channel has a variable bit rate that peaks at 9.8 Mbit/s, yielding a total

bit rate (audio +video) varying between 300 kbit/s and 10.08 Mbit/s. A 4.7 Gbyte DVD

can store movies with 90 −120 min running times.

MPEG-4

This is a format patented by ISO/IEC, which includes no less than 23 standards or

“parts.”

These allow for audio and video compression enhancement and a wide range

of novel multimedia applications, including object-oriented coding, virtual-reality mod-

eling, user graphic interactivity, computer-generated video and audio, and digital rights

management and protection. The MPEG-4 audio codec, which is described in Part 3,

is referred to as advanced audio coding (AAC).

The key intent of AAC is to provide

better sound compression without affecting quality, or better quality with a given stream

rate. The claim is that in sound quality a 48 kbit/s AAC stream would outperform a

128 kbit/s MP3 stream, while the consensus concerns more the AAC superiority over

any other 32–64 kbit/s audio codec, and its improved compression with respect to MP3.

The MPEG-4 video codecs are described in Part 2 and Part 10. The ﬁrst (Part 2) concerns

image compression through DCT in view of the simplest implementation “proﬁles,” see

further. The second (Part 10), is also referred to as H.264 (the ITU-T denomination) or

advanced video coding (AVC).

The key intent of this advanced codec is to reduce the

bit rate without affecting the picture’s end quality. This is enabled by several feature, of

which only a few can be mentioned or make sense within the scope of this overview.

For instance, inter-picture prediction is not limited to B-frames (as in MPEG-2) but up

to 32 neighboring reference frames. A variable macroblock size ranging from 4 ×4to

16 × 16 enables more precise mapping and tracking of moving regions in still back-

grounds. Compression is introduced by context-adaptive binary arithmetic coding and

variable-length (Huffman) coding (Chapter 10), referred to as CABAC and CAVLC,

See, for instance: http://en.wikipedia.org/wiki/DVD.

See, for instance: http://en.wikipedia.org/wiki/DVD_Formats.

See, for instance: http://en.wikipedia.org/wiki/MPEG-4; www.chiariglione.org/mpeg/standards/mpeg-4/

mpeg-4.htm; www.apple.com/quicktime/technologies/mpeg4/.

See, for instance: http://en.wikipedia.org/wiki/MPEG-4_Part_3; www.mpeg.org.

See, for instance: http://en.wikipedia.org/wiki/H.264.

604 Appendix G

respectively, which are completed by default with exponential-Golomb coding.

The

key result is that the combined features of H.264/AVC make it possible to obtain the

same quality as MPEG-2 at half the bit rate or even less. As with MPEG-2, there exist a

range of “proﬁles” and “levels” adapted for each consumer-electronics or professional

application: 3G mobile, video telephony, videoconferencing, broadcast television, Inter-

net video streaming, CD storage, etc. The controversial format DivX, which has been

dubbed “the MP3 of video,” was designed in early 2000. It capitalizes on the afore-

mentioned MPEG-4 Part 2 video compression features, balancing video quality against

ﬁle size.

The end result is the possibility of squeezing an entire DVD content into a

(700–800 Mbyte) data CD, without perceptible loss of quality.

See, for instance: http://en.wikipedia.org/wiki/Exponential-Golomb_coding.

See, for instance: http://en.wikipedia.org/wiki/DivX.

Appendix H (Chapter 10) Arithmetic

coding algorithm

In this appendix, I derive a generic algorithm

to compute the real intervals [u,v)

corresponding to the arithmetic coding of any string of N symbols deﬁned by a

...a

where a

belongs to the n-events source X ={x

, x

,...,x

}with associated probability

distribution p

={p(x

) ... p(x

)}. I will use index k to designate the symbol position

in the string, and index i to designate the value x

of this symbol. By convention, the

symbol x

is exclusively used for signaling string termination. For easier reading, I shall

use the notation u,v to designate the intervals instead of the cumbersome [u,v).

To build the algorithm, consider ﬁrst the simple example of a source X ={x

, x

}

and strings with lengths up to N = 2. According to the arithmetic coding, and as shown

in Fig. H1, the initial interval I = [0, 1) ≡0, 1 is divided into the three subintervals

=0, p(x

), (H1)

=p(x

), p(x

) + p(x

), (H2)

=p(x

) + p(x

), 1, (H3)

with I

+ I

= I .

By convention, all complete strings should end with the symbol x

. The three possible

strings are, therefore, x

, x

, and x

. Figure H1 shows how each of the intervals I

and I

is divided in turn into three subintervals (I

, I

and I

, I

). The

subintervals of interest for complete strings, I

, I

, and I

, are highlighted in Fig. H1.

For future use, we deﬁne the interval width of I =u,vas w(I ) = v − u. In particular,

w(I ) = 1, (H4)

w(I

) = p(x

), (H5)

w(I

) = p(x

). (H6)

The single-symbol string, x

, which, according to our convention, is useless or has zero

message payload, is, thus, deﬁned by the interval I

=u,v. The start and stop (values

of this interval are, according to Eq. (H3):



u = p(x

) + p(x

)

v = p(x

) + p(x

(H7)

D. J. C. MacKay, A Short Course in Information Theory (1995), www.inference.phy.cam.ac.uk/mackay/info-

theory/course.html; see also D. J. C. MacKay, Information Theory, Inference and Learning Algorithms

(Cambridge, UK: Cambridge University Press, 2003), p. 113.

606 Appendix H

)()(

xpxp

)(

Figure H1 Source and strings to build algorithm from successive subinternal division.

Although it looks a bit useless and complicated, it is accurate to rewrite the deﬁnition in

Eq. (H7) in the general form:











u(I

) = p(x

|s) p(s) + p(x

|s) p(s) ≡ u(I ) +w(I )



i=1

p(x

|s)

v(I

) = p(x

|s) p(s) + p(x

|s) p(s) ≡ u(I ) +w(I )



i=1

p(x

|s),

(H8)

where the argument s refers to all preceding symbols in the string (since there are none

here, p(s) = 1 = w(I ) and p(x

1,2,3

|s) ≡ p(x

1,2,3

)), where u(I ) = 0 is the start value of

the interval corresponding to all preceding symbols (I ).

Consider next the interval I

, which is the last subdivision of I

and corresponds to

the string x

,asshowninFig. H1. Consistently with the subdivision, the start and the

stop values of this interval are:



u = p(x

) + p(x

)p(x

) + p(x

)p(x

)

v = p(x

) + p(x

)p(x

) + p(x

)p(x

) + p(x

)p(x

(H9)

which can be rewritten in the form:











u(I

) ≡ u(I

) + w(I

)



i=1

p(x

)

v(I

) = u(I

) + w(I

)



i=1

p(x

(H10)