当前位置:首页 >> 理学 >>

计算机科学导论原书第二版答案第十五章


CHAPTER 15

Data Compression
(Solutions to Practice Set)

Review Questions
1. The two categories of data compression methods are lossless and lossy. 2. Lossless compression preserves the integrity of the data; in lossy compression, some of the data is lost in the compression/decompression process. 3. Run length encoding is a lossless compression method in which repeated occurrences of a symbol are replaced by one occurrence of the symbol followed by the number of occurrences. 4. Lempel-Ziv (LZ) encoding is a type of dictionary-based, lossless compression method in which a dictionary is constructed during encoding. During decoding, the dictionary is reconstructed from the received data. During encoding or decoding, the already-encountered strings can be substituted by their index in the dictionary to reduce the amount of information transmitted. 5. Huffman coding uses the frequency of the characters in the file to construct a tree. The tree is then used to generate codes for each character with the more frequent characters having shorter codes than the less frequent characters. 6. The dictionary in LZ encoding consists of indexed entries that refer to substrings in the original file. These indices are used to refer to future occurrences of these substrings. 7. In Huffman coding, both the sender and receiver must have a copy of the same code in order for the decoded file to match the encoded file. In LZ encoding, the dictionary is generated from the data itself. 8. The three lossy compressions are JPEG, MPEG, and MP3. 9. JPEG is used to compress images while MPEG is used to compress video. 10. MPEG uses a method similar to JPEG to compress the individual frames of video. Whereas, JPEG uses only spatial compression, MPEG uses both spatial and temporal compression. 11. Blocking is the act of dividing the image into 8 × 8 blocks in order to reduce the number of calculations.
1

2

12. DCT changes the 64-pixel values in each block so that the relative relationships between pixels are kept but the redundancies are removed. 13. Quantization of the T table reduces the number of bits needed for encoding each value. 14. A motion picture is a rapid flow of a set of frames where each frame is a picture. 15. Spatial compression is the compression of each frame by using a modified version of JPEG; temporal compression is the removal of redundant frames in MPEG. 16. I-frames (intracoded frames) are complete, independent frames and are not related to any other frames. P-frames (predicted frames) contain only the changes from the preceding I-frame or P-frame. B-frames (bidirectional frames) are relative to the preceding and following I-frame or P-frame.

Multiple-Choice Questions
17. b 23. a 29. c 18. a 24. b 30. c 19. d 25. c 20. a 26. d 21. d 27. b 22. d 28. a

Exercises
31. 10010 00000 11111 11001 01111 00000 00000 32. 00000 01000 11111 01110 00000 00000 33. Different codes result from different ways of organizing the tree. One possible tree with the resulting code is shown Figure S15.33. Figure S15.33 Exercise 33
102

1
61

A: 000 E: 10 B: 1111 F: 110 C: 001 G: 1110 D: 01 0 A 12

0
41

1 0
30

0
21

1 D 20 E 31

0 F 14

1 0 G 8
16

1 C 9

1 B 8

34. Different codes result from different ways of constructing the tree. One possible tree with the resulting code is shown in Figure S15.34. 35. This can be a Huffman code. The shorter codes is not the prefix of any of the two longer codes. The tree is shown in Figure S15.35.

3

Figure S15.34 Exercise 34
10 A: 000 B: 001 C: 010 D: 011 E: 1000 F: 1001 G: 1010 H: 1011 I: 110 G: 111 0 0 0 0 A 1 2 1 B 1 4 0 C 1 1 2 1 D 1 0 E 1 0 2 1 F 1 4 1 0 G 1 2 1 H 1 0 I 1 2 1 J 1

1 6 1

Figure S15.35
A: 0 B: 10 C: 11 1 0 A 0 B 1 C

36. This cannot be a Huffman code. The longer codes all start with one of the shorter codes. For instance, if the receiver receives one 0, it cannot tell if this single zero is an A or the beginning of a C (00) or the beginning of a D (01). 37. 100 0101 0101 000 1100 38. ABBAAACCA 39. Encoding is shown in Figure 15.39a. Figure S15.39a Exercise 39 part a
Uncompressed B B B B, A B A AB B, A, 2B B A AB BB B, A, 2B, 1B B A AB BB BA B, A, 2B, 1B, 1A B A AB BB BA AC B, A, 2B, 2B, 1A, 2C B A AB BB BA AC AA AA AA B, A, 2B, 1B, 1A, 2C, 2A A A AB BB BA AC AABBBBAACAA ABBBBAACAA BBBAACAA BAACAA ACAA BAABBBBAACAA

B

BAABBBBAACAA

Compressed

B, A, 2B, 1B, 1A, 2C, 2A

Decoding is shown in Figure 15.39b.

4

Figure S15.39b

Exercise 39 part b
Compressed

B, A, 2B, 1B, 1A, 2C, 2A

B B B BA B A AB BAAB B A AB BB BAABBB B A AB BB BA BAABBBBA B A AB BB BA AC BAABBBBAAC B A AB BB BA AC AA BAABBBBAACAA A

B A 2B 1B 1A 2C 2A

B, A, 2B, 1B, 1A, 2C, 2A A, 2B, 1B, 1A, 2C, 2A 2B, 1B, 1A, 2C, 2A 1B, 1A, 2C, 2A

1A, 2C, 2A 2C, 2A 2A

Uncompressed

BAABBBBAACAA

40. Figure S15.40 shows the dictionary. Figure S15.40 Exercise 40
Uncompressed
A B AB ABB AA ... 1A A B AB ABB AA AAB ... 1A, 5B A B AB ABB AA AAB BC .... 1A, 5B, 2C A B AB ABB AA AAB BC ... 1A, 5B, 2C, C A B AB ABB AA AAB BC ... 1A, 5B, 2C, C, 8B A B AB ABB AA AAB BC ... 1A, 5B, 2C, C, 8B, 2B C

... AAAABBCCCBBB ...

AA AAB

AAAABBCCCBBB ... AABBCCCBBB ... BCCCBBB ... CCBBB ... CBBB ... BB ...

BC C
C CB

CB
C CB BB

BB

Compressed

...1A, 5B, 2C, C, 8B, 2B ...

Note that if the dictionary contains ABB, it must also have A, B, AB.

5

41. Calculations are
T(0, 0) T(0, 1) T(1, 0) T(1, 1)

= = = =

1/16 [16 + 32 + 128 + 48] 1/16 [0.94 (64) + 0.90 (32) + 0.85 (128) + 0.80 (48)] 1/16 [0.90 (64) + 0.85 (32) + 0.80 (128) + 0.75 (48)] 1/16 [0.85 (64) + 0.80 (32) + 0.75 (128) + 0.70 (48)]

= = = =

17.00 14.08 13.59 13.10


相关文章:
计算机科学导论原书第二版答案第十五章.pdf
计算机科学导论原书第二版答案第十五章 - CHAPTER 15 Data Com
计算机科学导论原书第二版答案第十四章.pdf
计算机科学导论原书第二版答案第十四章 - CHAPTER 14 Database
计算机科学导论原书第二版答案第十六章.pdf
计算机科学导论原书第二版答案第十六章 - CHAPTER 16 Security
计算机科学导论原书第二版答案第十八章.pdf
计算机科学导论原书第二版答案第十八章 - CHAPTER 18 Artifici
计算机科学导论原书第二版答案第二章.pdf
计算机科学导论原书第二版答案第 - CHAPTER 2 Number Sys
计算机科学导论原书第二版答案第十二章.pdf
计算机科学导论原书第二版答案第十二章 - CHAPTER 12 Abstract
计算机科学导论原书第二版答案第十三章.pdf
计算机科学导论原书第二版答案第十三章 - CHAPTER 13 File Str
计算机科学导论原书第二版答案第十一章.pdf
计算机科学导论原书第二版答案第十一章 - CHAPTER 11 Data Str
计算机科学导论原书第二版答案第十七章.pdf
计算机科学导论原书第二版答案第十七章 - CHAPTER 17 Theory o
计算机科学导论原书第二版答案第九章.pdf
计算机科学导论原书第二版答案第九章 - CHAPTER 9 Programmin
计算机科学导论原书第二版答案第七章.pdf
计算机科学导论原书第二版答案第七章 - CHAPTER 7 Operating
计算机科学导论习题答案.pdf
计算机科学导论习题答案_IT/计算机_专业资料。计算机科学导论习题答案 原书第二版 英文 CHAPTER 1 Introduction (Solutions to Practice Set) Review Questions 1. ...
计算机科学导论答案.doc
计算机科学导论答案_哲学_高等教育_教育专区。计算机科学导论答案 2011 年计算机导论修订第二版课后练习答案 第一章 一、简答题 1、什么是计算机? 计算机系统是一种...
计算机科学导论第2次作业答案[1].doc
计算机科学导论第2次作业答案[1] - 《计算机科学导论第 2 次作业答案 (第 8 章第 15 章) 一、选择题 1.与批处理系统相比较,分时系统的最大优点在于(...
计算机科学导论第2章-答案.doc
计算机科学导论第2章-答案 - 第 2 章 计算机体系结构与组织 习题(答案) 一. 选择题 1.D 5.C 6.B 10.C 11.A 15.A 16.A 17.B 18.A 12.C 13....
计算机科学导论习题答案.doc
计算机科学导论习题答案_工学_高等教育_教育专区。...D 第二章略 第三章 数的表示 1. 将十进制转换...(4)定义方法 6 见导论书 165 页 7 见导论书 ...
计算机科学导论习题答案.txt
计算机科学导论习题答案 - 计算机科学导论习题答案 第一章 一.选择题 1-5 A D B D D 二.填空题 【1】 处理信息快、存储容量大、可靠性高、准确性高 【2...
计算机科学导论 (第二版 清华大学出版社)第12章 社会和....doc
计算机科学导论 (第二版 清华大学出版社)第12章 社会和职业问题(答案)_工学_高等教育_教育专区。第二版 清华大学出版社 第12 章 社会和职业问题习题(答案) ...
《计算机科学导论》课后练习(翻译).doc
计算机科学导论》课后练习(翻译)_理学_高等教育_...也就是在第二代计算机末期和第三代 计算机初期出现...A.位图 B.矢量图 C.余码系统 D.答案 A 或 B...
大学计算机基础课课本计算机科学导论课后答案.doc
大学计算机基础课课本计算机科学导论课后答案_理学_高等教育_教育专区。自己综合汇总的计算机科学导论第二版课后答案 以下答案多方资料做的,仅供参考。 第一章 绪论 ...